From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 28 May 2025 10:28:33 -0700 Received: from mail-qv1-f57.google.com ([209.85.219.57]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uKKZr-0002Ny-4T for bitcoindev@gnusha.org; Wed, 28 May 2025 10:28:33 -0700 Received: by mail-qv1-f57.google.com with SMTP id 6a1803df08f44-6fa9d9b3e28sf2200886d6.3 for ; Wed, 28 May 2025 10:28:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1748453305; x=1749058105; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:sender:from:to:cc:subject:date :message-id:reply-to; bh=gQ6/IbPqwlBoLoczz63T/SnnW+Op0ZBIn9pCnnBUOFI=; b=SK4zIUEyD7IK9dEoFANOuBK2m5RTlpu4Ai2qsMWM0bxgv3CjYm2xIzEmeAMSQ9N8vk 1yC0sjUVwocqGZ3G+r1BEg9cMep0ebPTsdodFDxVXv0zufcOrJvvsxK/v5kHRVo4dsoj sHQox9q1nVL9Bg9GWh5UA0MzpJkCZ4dJj/MlVBQStrCDjQpgm+7zNVYn1RYpPQJecFaj +VM+N+GaMkbTNT4fpKhZ+qtB9RkW0myRWHv/iOM/wlg6EvzRcDgP8MtqvV0+1MNxq3/C ywSayjSpBIKJ+jthxXeEHmIF9RFX6hKxCBREuX3kKfBvL5VgLKvhrHxvDKBAQ37LHDUj TKkw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1748453305; x=1749058105; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:from:to:cc:subject:date:message-id :reply-to; bh=gQ6/IbPqwlBoLoczz63T/SnnW+Op0ZBIn9pCnnBUOFI=; b=k6HykX7HIco69DnDBSFFPmmGh/vm+TaO65Jk53kiqjTqSYSjM/CEyLQdfG66PSAElw v2hDdVUHxWbw65HTs1sKMshqapj8kaupG13pa08+NPRUM98Mg+7/j+JZ9xGB8jOiZDgK uqLHtjwo5mHPrOTZNXay54t9qM2mYHoVHYDjzfzZEM6SYSV6++FT9IbrHtGVfI6YeA+B U7SYzi3CaP11xFrqEAYoEx4gKaaLWlOnJWdXL+JqtcQHmZDamkSjo1HCqLxbLKPR1cfZ g5AKpA+/1PTBXrp1vea4JfXWnmyBQd2OGugwLDa3kD/2YO0tI860KExffYNIwVolUPBy jp3g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748453305; x=1749058105; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=gQ6/IbPqwlBoLoczz63T/SnnW+Op0ZBIn9pCnnBUOFI=; b=RWjiHwTV/4w+2h6YPft3cnPa5fuppyDr3T+meq3tyPkHHG7Xi0VyGzuDgtsR3B8a7D HbKCw8Lh5ZWfuEyErLJrIkhmP7uFg32dq8zy4AGglS3Sv4RKBSoQKM8/GD+pW+MlohEz rIEN2Hx1Pene/b4BSsb+q7nkni89MxKcezks6JgzKPc6FB92nNFR8JEtOh9sxdBk3xkZ 5qDM8ZufyClU9oCLV/9y9xO2Qww4EKk10gKBbfk9uuHW8eySI0VIXB4JlV20jrAMwh2q 4BnkNjYdPBfHc+/R5PjmhUzmr0PEh/3vyh0XYuvEFD8e40qzbEls6lP1BRC72HIWYj19 EJmg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWaLEeKAnzyyUxqTPmWiLRroSAGGoulOrCigoe0zgTVr5PWClt/2kBgo8xUV+IBFBPhqlbSyeE3z+z+@gnusha.org X-Gm-Message-State: AOJu0Ywecif0E90eeWZcstKHHKwSY8imRj6EF4LQvBKsMVrWlsubwnt+ FaPay0t5lHa8QwksOxuhj17OIjj9gJzmQ/TRbnb+EEiNCmz6qnoD7ScN X-Google-Smtp-Source: AGHT+IF1qs1gKnxxNFYBk71ZU1SsPW5DdIHE+Jgvg3D98daofUYecxpUIyAqeQ/ofNluRRIs+l41wA== X-Received: by 2002:a05:6214:5095:b0:6ea:d033:2846 with SMTP id 6a1803df08f44-6fa9d2b0574mr342211986d6.25.1748453305109; Wed, 28 May 2025 10:28:25 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZeoWdI07idUQ1O+OIJ94EB6eC0FqvZP1/g2a8SowOm7Bw== Received: by 2002:a05:6214:564c:b0:6fa:bd2a:c680 with SMTP id 6a1803df08f44-6fac5d8a8c9ls1333936d6.2.-pod-prod-06-us; Wed, 28 May 2025 10:28:21 -0700 (PDT) X-Received: by 2002:a05:620a:2808:b0:7c5:47c6:b888 with SMTP id af79cd13be357-7ceecc2c8fdmr2853070485a.40.1748453300896; Wed, 28 May 2025 10:28:20 -0700 (PDT) Received: by 2002:a05:620a:6114:b0:7b6:d2da:e6ae with SMTP id af79cd13be357-7cec82c48abms85a; Wed, 28 May 2025 10:14:22 -0700 (PDT) X-Received: by 2002:a05:6214:234e:b0:6f4:c423:67b4 with SMTP id 6a1803df08f44-6fa9d00782emr287836726d6.10.1748452460887; Wed, 28 May 2025 10:14:20 -0700 (PDT) Date: Wed, 28 May 2025 10:14:20 -0700 (PDT) From: Tadge Dryja To: Bitcoin Development Mailing List Message-Id: Subject: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_439988_173213702.1748452460585" X-Original-Sender: rx@awsomnet.org Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.7 (/) ------=_Part_439988_173213702.1748452460585 Content-Type: multipart/alternative; boundary="----=_Part_439989_607034305.1748452460585" ------=_Part_439989_607034305.1748452460585 Content-Type: text/plain; charset="UTF-8" One of the tricky things about securing Bitcoin against quantum computers is: do you even need to? Maybe quantum computers that can break secp256k1 keys will never exist, in which case we shouldn't waste our time. Or maybe they will exist, in not too many years, and we should spend the effort to secure the system against QCs. Since people disagree on how likely QCs are to arrive, and what the timing would be if they do, it's hard to get consensus on changes to bitcoin that disrupt the properties we use today. For example, a soft fork introducing a post-quantum (PQ) signature scheme and at the same time disallowing new secp256k1 based outputs would be great for strengthening Bitcoin against an oncoming QC. But it would be awful if a QC never appears, or takes decades to do so, since secp256k1 is really nice. So it would be nice to have a way to not deal with this issue until *after* the QC shows up. With commit / reveal schemes Bitcoin can keep working after a QC shows up, even if we haven't defined a PQ signature scheme and everyone's still got P2WPKH outputs. Most of this is similar to Tim Ruffing's proposal from a few years ago here: https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/ The main difference is that this scheme doesn't use encryption, but a smaller hash-based commitment, and describes activation as a soft fork. I'll define the two types of attacks, a commitment scheme, and then say how it can be implemented in bitcoin nodes as a soft fork. This scheme only works for keys that are pubkey hashes (or script hashes) with pubkeys that are unknown to the network. It works with taproot as well, but there must be some script-path in the taproot key, as keypath spends would no longer be secure. What to do with all the keys that are known is another issue and independent of the scheme in this post (it's compatible with both burning them and leaving them to be stolen) For these schemes, we assume there is an attacker with a QC that can compute a quickly compute a private key from any secp256k1 public key. We also assume the attacker has some mining power or influence over miners for their attacks; maybe not reliably, but they can sometimes get a few blocks in a row with the transactions they want. "Pubkey" can also be substituted with "script" for P2SH and P2WSH output types and should work about the same way (with caveats about multisig). The equivalent for taproot outputs would be an inner key proving a script path. ## A simple scheme to show an attack The simplest commit/reveal scheme would be one where after activation, for any transaction with an EC signature in it, that transaction's txid must appear in a earlier transaction's OP_RETURN output. When a user wants to spend their coins, they first sign a transaction as they would normally, compute the txid, get that txid into an OP_RETURN output somehow (paying a miner out of band, etc), then after waiting a while, broadcast the transaction. Nodes would check that the txid matches a previously seen commitment, and allow the transaction. One problem with this scheme is that upon seeing the full transaction, the attacker can compute the user's private key, and create a new commitment with a different txid for a transaction where the attacker gets all the coins. If the attacker can get their commitment and spending transaction in before the user's transaction, they can steal the coins. In order to mitigate this problem, a minimum delay can be enforced by consensus. A minimum delay of 100 blocks would mean that the attacker would have to prevent the user's transaction from being confirmed for 100 blocks after it showed up in the attacker's mempool. The tradeoff is that longer periods give better safety at the cost of more delay in spending. This scheme, while problematic, is better than nothing! But it's possible to remove this timing tradeoff. ## A slightly more complex scheme with (worse) problems If instead of just the txid, the commitment were both the outpoint being spent, and the txid that was going to spend it, we could add a "first seen" consensus rule. Only the first commitment pointing to an outpoint works. So if nodes see two OP_RETURN commitments in their sequence of confirmed transactions: C1 = outpoint1, txid1 C2 = outpoint1, txid2 They can ignore C2; C1 has already laid claim to outpoint1, and the transaction identified by txid1 is the only transaction that can spend outpoint1. If the user manages to get C1 confirmed first, this is great, and eliminates the timing problem in the txid only scheme. But this introduces a different problem, where an attacker -- in this case any attacker, even one without a QC -- who can observe C1 before it is confirmed can flip some bits in the txid field, freezing the outpoint forever. We want to retain the "first seen" rule, but we want to also be able to discard invalid commitments. In a bit flipping attack, we could say an invalid commitment is one where there is no transaction described by the txid. A more general way to classify a commitment as invalid is a commitment made without knowledge of the (secret) pubkey. Knowledge of the pubkey is what security of coins is now hinging on. The actual commitment scheme We define some hash function h(). We'll use SHA256 for the hashing, but it needs to be keyed with some tag, for example "Alas poor Koblitz curve, we knew it well". Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, HASH160(pubkey). Due to the hash functions being different, A = HASH160(pubkey) and B = h(pubkey) will be completely different, and nobody should be able to determine if A and B are hashes of the same pubkey without knowing pubkey itself. An efficient commitment is: C = h(pubkey), h(pubkey, txid), txid (to label things: C = AID, SDP, CTXID) This commitment includes 3 elements: a different hash of the pubkey which will be signed for, a proof of knowledge of the pubkey which commits to a transaction, and an the txid of the spending transaction. We'll call these "address ID" (AID), sequence dependent proof (SDP), and the commitment txid (CTXID). For those familiar with the proposal by Ruffing, the SDP has a similar function to the authenticated encryption part of the encrypted commitment. Instead of using authenticated encryption, we can instead just use an HMAC-style authentication alone, since the other data, the CTXID, is provided. When the user's wallet creates a transaction, they can feed that transaction into a commitment generator function which takes in a transaction, extracts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash commitment. Once this commitment is confirmed, the user broadcasts the transaction. Nodes verify the commitment by using the same commitment generator function and checking if it matches the first valid commitment for that AID, in which case the tx is confirmed. If a node sees multiple commitments all claiming the same AID, it must store all of them. Once the AID's pubkey is known, the node can distinguish which commitments are valid, which are invalid, and which is the first seen valid commitment. Given the pubkey, nodes can determine commitments to be invalid by checking if SDP = h(pubkey, CTXID). As an example, consider a sequence of 3 commitments: C1 = h(pubkey), h(pubkey', txid1), txid1 C2 = h(pubkey), h(pubkey, txid2), txid2 C3 = h(pubkey), h(pubkey, txid3), txid3 The user first creates tx2 and tries to commit C2. But an attacker creates C1, committing to a different txid where they control the outputs, and confirms it first. This attacker may know the outpoint being spent, and may be able to create a transaction and txid that could work. But they don't know the pubkey, so while they can copy the AID hash, they have to make something up for the SDP. The user gets C2 confirmed after C1. They then reveal tx2 in the mempool, but before it can be confirmed, the attacker gets C3 confirmed. C3 is a valid commitment made with knowledge of the pubkey. Nodes can reject transactions tx1 and tx3. For tx1, they will see that the SDP doesn't match the data in the transaction, so it's an invalid commitment. For tx3, they will see that it is valid, but by seeing tx3 they will also be able to determine that C2 is a valid commitment (since pubkey is revealed in tx3) which came prior to C3, making C2 the only valid commitment for that AID. ## Implementation Nodes would keep a new key/value store, similar to the existing UTXO set. The indexing key would be the AID, and the value would be the set of all (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is seen in an OP_RETURN, nodes store the commitment. When a transaction is seen, nodes observe the pubkey used in the transaction, and look up if it matches an AID they have stored. If not, the transaction is dropped. If the AID does match, the node can now "clean out" an AID entry, eliminating all but the first valid commitment, and marking that AID as final. If the txid seen matches the remaining commitment, the transaction is valid; if not, the transaction is dropped. After the transaction is confirmed the AID entry can be deleted. Deleting the entries frees up space, and would allow another round to happen with the same pubkey, which would lead to theft. Retaining the entries takes up more space on nodes that can't be pruned, and causes pubkey reuse to destroy coins rather than allow them to be stolen. That's a tradeoff, and I personally guess it's probably not worth retaining that data but don't have a strong opinion either way. Short commitments: Since we're not trying to defend against collision attacks, I think all 3 hashes can be truncated to 16 bytes. The whole commitment could be 48 bytes long. Without truncation the commitments would be 96 bytes. ## Activation The activation for the commit/reveal requirement can be triggered by a proof of quantum computer (PoQC). A transaction which successfully spends an output using tapscript: OP_SHA256 OP_CHECKSIG is a PoQC in the form of a valid bitcoin transaction. In order to satisfy this script, the spending transaction needs to provide 2 data elements: a signature, and some data that when hashed results in a pubkey for which that signature is valid. If such a pair of data elements exists, it means that either SHA256 preimage resistance is broken (which we're assuming isn't the case) or someone can create valid signatures for arbitrary elliptic curve points, ie a cryptographically relevant quantum computer (or any other process which breaks the security of secp256k1 signatures) Once such a PoQC has been observed in a confirmed transaction, the requirements for the 3-hash commitment scheme can be enforced. This is a soft fork since the transactions themselves look the same, the only requirement is that some OP_RETURN outputs show up earlier. Nodes which are not aware of the commitment requirement will still accept all transactions with the new rules. Wallets not aware of the new rules, however, are very dangerous, as they may try to broadcast signed transactions without any commitment. Nodes that see such a transaction should drop the tx, and if possible tell the wallet that they are doing something which is now very dangerous! On the open p2p network this is not really enforceable, but people submitting transactions to their own node (eg via RPC) can at least get a scary error message. ## Issues My hope is that this scheme would give some peace of mind to people holding bitcoin, that in the face of a sudden QC, even with minimal preparation their coins can be safe at rest and safely moved. It also suggests some best practices for users and wallets to adopt, before any software changes: Don't reuse addresses, and if you have taproot outputs, include some kind of script path in the outer key. There are still a number of problems, though! - Reorgs can steal coins. An attacker that observes a pubkey and can reorg back to before the commitment can compute the private key, sign a new transaction and get their commitment in first on the new chain. This seems unavoidable with commit/reveal schemes, and it's up to the user how long they wait between confirming the commitment and revealing the transaction. - How to get op_returns in If there are no PQ signature schemes activated in bitcoin when this activates, there's only one type of transaction that can reliably get the OP_RETURN outputs confirmed: coinbase transactions. Getting commitments to the miners and paying them out of band is not great, but is possible and we see this kind of activity today. Users wouldn't need to directly contact miners: anyone could aggregate commitments, create a large transaction with many OP_RETURN outputs, and then get a miner to commit to that parent transaction. Users don't need to worry about committing twice as identical commitments would be a no op. - Spam Anyone can make lots of OP_RETURN commitments which are just random numbers, forcing nodes to store these commitments in a database. That's not great, but isn't much different from how bitcoin works today. If it's really a problem, nodes could requiring the commitment outputs to have a non-0 amount of bitcoin, imposing a higher cost for the commitments than other OP_RETURN outputs. - Multiple inputs If users have received more than one UTXO to the same address, they will need to spend all the UTXOs at once. The commitment scheme can deal with only the first pubkey seen in the serialized transaction. - Multisig and Lightning Network If your multisig counterparties have a QC, multisig outputs become 1 of N. Possibly a more complex commit / reveal scheme could deal with multiple keys, but the keys would all have to be hashed with counterparties not knowing each others' unhashed pubkeys. This isn't how existing multisig outputs work, and in fact the current trend is the opposite with things like Musig2, FROST and ROAST. If we're going to need to make new signing software and new output types it might make more sense to go for a PQ signature scheme. - Making more p2wpkhs You don't have to send to a PQ address type with these transactions -- you can send to p2wpkh and do the whole commit/reveal process again when you want to spend. This could be helpful if PQ signature schemes are still being worked on, or if the PQ schemes are more costly to verify and have high fees in comparison to the old p2wpkh output types. It's possible that in such a scenario a few high-cost PQ transactions commit to many smaller EC transactions. If this actually gets adoption though, we might as well drop the EC signatures and just make output scripts into raw hash / preimage pairs. It could make sense to cover some non-EC script types with the same 3-hash commitment requirement to enable this. ## Conclusion This PQ commit / reveal scheme has similar properties to Tim Ruffing's, with a smaller commitment that can be done as a soft fork. I hope something like this could be soft forked with a PoQC activation trigger, so that if a QC never shows up, none of this code gets executed. And people who take a couple easy steps like not reusing addresses (which they should anyway for privacy reasons) don't have to worry about their coins. Some of these ideas may have been posted before; I know of the Fawkscoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent discussion which linked to Ruffing's proposal. Here I've tried to show how it could be done in a soft fork which doesn't look too bad to implement. I've also heard of some more complex schemes involving zero knowledge proofs, proving things like BIP32 derivations, but I think this gives some pretty good properties without needing anything other than good old SHA256. Hope this is useful & wonder if people think something like this would be a good idea. -Tadge -- You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com. ------=_Part_439989_607034305.1748452460585 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable One of the tricky things about securing Bitcoin against quantum computers i= s: do you even need to? =C2=A0Maybe quantum computers that can break secp25= 6k1 keys will never exist, in which case we shouldn't waste our time. =C2= =A0Or maybe they will exist, in not too many years, and we should spend the= effort to secure the system against QCs.

Since people disagree = on how likely QCs are to arrive, and what the timing would be if they do, i= t's hard to get consensus on changes to bitcoin that disrupt the properties= we use today. =C2=A0For example, a soft fork introducing a post-quantum (P= Q) signature scheme and at the same time disallowing new secp256k1 based ou= tputs would be great for strengthening Bitcoin against an oncoming QC. =C2= =A0But it would be awful if a QC never appears, or takes decades to do so, = since secp256k1 is really nice.

So it would be nice to have a wa= y to not deal with this issue until *after* the QC shows up. =C2=A0With com= mit / reveal schemes Bitcoin can keep working after a QC shows up, even if = we haven't defined a PQ signature scheme and everyone's still got P2WPKH ou= tputs.

Most of this is similar to Tim Ruffing's proposal from a = few years ago here:
https://gnusha.org/pi/bitcoindev/1518710367.3550.1= 11.camel@mmci.uni-saarland.de/

The main difference is that this = scheme doesn't use encryption, but a smaller hash-based commitment, and des= cribes activation as a soft fork. =C2=A0I'll define the two types of attack= s, a commitment scheme, and then say how it can be implemented in bitcoin n= odes as a soft fork.

This scheme only works for keys that are pu= bkey hashes (or script hashes) with pubkeys that are unknown to the network= . =C2=A0It works with taproot as well, but there must be some script-path i= n the taproot key, as keypath spends would no longer be secure. =C2=A0

What to do with all the keys that are known is another issue and ind= ependent of the scheme in this post (it's compatible with both burning them= and leaving them to be stolen)

For these schemes, we assume the= re is an attacker with a QC that can compute a quickly compute a private ke= y from any secp256k1 public key. =C2=A0We also assume the attacker has some= mining power or influence over miners for their attacks; maybe not reliabl= y, but they can sometimes get a few blocks in a row with the transactions t= hey want.

"Pubkey" can also be substituted with "script" for P2S= H and P2WSH output types and should work about the same way (with caveats a= bout multisig). =C2=A0The equivalent for taproot outputs would be an inner = key proving a script path.

## A simple scheme to show an attack<= br />
The simplest commit/reveal scheme would be one where after activ= ation, for any transaction with an EC signature in it, that transaction's t= xid must appear in a earlier transaction's OP_RETURN output.

Whe= n a user wants to spend their coins, they first sign a transaction as they = would normally, compute the txid, get that txid into an OP_RETURN output so= mehow (paying a miner out of band, etc), then after waiting a while, broadc= ast the transaction. =C2=A0Nodes would check that the txid matches a previo= usly seen commitment, and allow the transaction.

One problem wit= h this scheme is that upon seeing the full transaction, the attacker can co= mpute the user's private key, and create a new commitment with a different = txid for a transaction where the attacker gets all the coins. =C2=A0If the = attacker can get their commitment and spending transaction in before the us= er's transaction, they can steal the coins.

In order to mitigate= this problem, a minimum delay can be enforced by consensus. =C2=A0A minimu= m delay of 100 blocks would mean that the attacker would have to prevent th= e user's transaction from being confirmed for 100 blocks after it showed up= in the attacker's mempool. =C2=A0The tradeoff is that longer periods give = better safety at the cost of more delay in spending.

This scheme= , while problematic, is better than nothing! =C2=A0But it's possible to rem= ove this timing tradeoff.


## A slightly more complex schem= e with (worse) problems

If instead of just the txid, the commitm= ent were both the outpoint being spent, and the txid that was going to spen= d it, we could add a "first seen" consensus rule. =C2=A0Only the first comm= itment pointing to an outpoint works.

So if nodes see two OP_RET= URN commitments in their sequence of confirmed transactions:

C1 = =3D outpoint1, txid1
C2 =3D outpoint1, txid2

They can ignor= e C2; C1 has already laid claim to outpoint1, and the transaction identifie= d by txid1 is the only transaction that can spend outpoint1.

If = the user manages to get C1 confirmed first, this is great, and eliminates t= he timing problem in the txid only scheme. =C2=A0But this introduces a diff= erent problem, where an attacker -- in this case any attacker, even one wit= hout a QC -- who can observe C1 before it is confirmed can flip some bits i= n the txid field, freezing the outpoint forever.

We want to reta= in the "first seen" rule, but we want to also be able to discard invalid co= mmitments. =C2=A0In a bit flipping attack, we could say an invalid commitme= nt is one where there is no transaction described by the txid. =C2=A0A more= general way to classify a commitment as invalid is a commitment made witho= ut knowledge of the (secret) pubkey. =C2=A0Knowledge of the pubkey is what = security of coins is now hinging on.


The actual commitment= scheme


We define some hash function h(). =C2=A0We'll use = SHA256 for the hashing, but it needs to be keyed with some tag, for example= "Alas poor Koblitz curve, we knew it well".

Thus h(pubkey) is n= ot equal to the pubkey hash already used in the bitcoin output script, whic= h instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, HASH160(pubkey= ). =C2=A0Due to the hash functions being different, A =3D HASH160(pubkey) a= nd B =3D h(pubkey) will be completely different, and nobody should be able = to determine if A and B are hashes of the same pubkey without knowing pubke= y itself.

An efficient commitment is:

C =3D =C2=A0h(p= ubkey), h(pubkey, txid), txid
(to label things: C =3D AID, SDP, C= TXID)

This commitment includes 3 elements: a differen= t hash of the pubkey which will be signed for, a proof of knowledge of the = pubkey which commits to a transaction, and an the txid of the spending tran= saction. =C2=A0We'll call these "address ID" (AID), sequence dependent proo= f (SDP), and the commitment txid (CTXID).

For those familiar wit= h the proposal by Ruffing, the SDP has a similar function to the authentica= ted encryption part of the encrypted commitment. =C2=A0Instead of using aut= henticated encryption, we can instead just use an HMAC-style authentication= alone, since the other data, the CTXID, is provided.

When the = user's wallet creates a transaction, they can feed that transaction into a = commitment generator function which takes in a transaction, extracts the pu= bkey from the tx, computes the 3 hashes, and returns the 3-hash commitment.= =C2=A0Once this commitment is confirmed, the user broadcasts the transacti= on.

Nodes verify the commitment by using the same commitment gen= erator function and checking if it matches the first valid commitment for t= hat AID, in which case the tx is confirmed.

If a node sees multi= ple commitments all claiming the same AID, it must store all of them. =C2= =A0Once the AID's pubkey is known, the node can distinguish which commitmen= ts are valid, which are invalid, and which is the first seen valid commitme= nt. =C2=A0Given the pubkey, nodes can determine commitments to be invalid b= y checking if SDP =3D h(pubkey, CTXID).

As an example, consider = a sequence of 3 commitments:

C1 =3D h(pubkey), h(pubkey', txid1)= , txid1
C2 =3D h(pubkey), h(pubkey, txid2), txid2
C3 =3D h(pubkey= ), h(pubkey, txid3), txid3

The user first creates tx2 and tries = to commit C2. =C2=A0But an attacker creates C1, committing to a different t= xid where they control the outputs, and confirms it first. =C2=A0This attac= ker may know the outpoint being spent, and may be able to create a transact= ion and txid that could work. =C2=A0But they don't know the pubkey, so whil= e they can copy the AID hash, they have to make something up for the SDP.
The user gets C2 confirmed after C1. =C2=A0They then reveal tx2 i= n the mempool, but before it can be confirmed, the attacker gets C3 confirm= ed. =C2=A0C3 is a valid commitment made with knowledge of the pubkey.
=
Nodes can reject transactions tx1 and tx3. =C2=A0For tx1, they will s= ee that the SDP doesn't match the data in the transaction, so it's an inval= id commitment. =C2=A0For tx3, they will see that it is valid, but by seeing= tx3 they will also be able to determine that C2 is a valid commitment (sin= ce pubkey is revealed in tx3) which came prior to C3, making C2 the only va= lid commitment for that AID.


## Implementation

= Nodes would keep a new key/value store, similar to the existing UTXO set. = =C2=A0The indexing key would be the AID, and the value would be the set of = all (SDP, CTXID) pairs seen alongside that AID. =C2=A0Every time an commitm= ent is seen in an OP_RETURN, nodes store the commitment.

When a = transaction is seen, nodes observe the pubkey used in the transaction, and = look up if it matches an AID they have stored. =C2=A0If not, the transactio= n is dropped. =C2=A0If the AID does match, the node can now "clean out" an = AID entry, eliminating all but the first valid commitment, and marking that= AID as final. =C2=A0If the txid seen matches the remaining commitment, the= transaction is valid; if not, the transaction is dropped.

After= the transaction is confirmed the AID entry can be deleted. =C2=A0Deleting = the entries frees up space, and would allow another round to happen with th= e same pubkey, which would lead to theft. =C2=A0Retaining the entries takes= up more space on nodes that can't be pruned, and causes pubkey reuse to de= stroy coins rather than allow them to be stolen. =C2=A0That's a tradeoff, a= nd I personally guess it's probably not worth retaining that data but don't= have a strong opinion either way.

Short commitments:

Since we're not trying to defend against collision attacks, I think all 3 = hashes can be truncated to 16 bytes. =C2=A0The whole commitment could be 48= bytes long. =C2=A0Without truncation the commitments would be 96 bytes.

## Activation

The activation for the commit/revea= l requirement can be triggered by a proof of quantum computer (PoQC).
=
A transaction which successfully spends an output using tapscript:
OP_SHA256 OP_CHECKSIG

is a PoQC in the form of a valid = bitcoin transaction. =C2=A0In order to satisfy this script, the spending tr= ansaction needs to provide 2 data elements: a signature, and some data that= when hashed results in a pubkey for which that signature is valid. =C2=A0I= f such a pair of data elements exists, it means that either SHA256 preimage= resistance is broken (which we're assuming isn't the case) or someone can = create valid signatures for arbitrary elliptic curve points, ie a cryptogra= phically relevant quantum computer (or any other process which breaks the s= ecurity of secp256k1 signatures)

Once such a PoQC has been obser= ved in a confirmed transaction, the requirements for the 3-hash commitment = scheme can be enforced. =C2=A0This is a soft fork since the transactions th= emselves look the same, the only requirement is that some OP_RETURN outputs= show up earlier. =C2=A0Nodes which are not aware of the commitment require= ment will still accept all transactions with the new rules. =C2=A0
Wallets not aware of the new rules, however, are very dangerous, as they= may try to broadcast signed transactions without any commitment. =C2=A0Nod= es that see such a transaction should drop the tx, and if possible tell the= wallet that they are doing something which is now very dangerous! =C2=A0On= the open p2p network this is not really enforceable, but people submitting= transactions to their own node (eg via RPC) can at least get a scary error= message.


## Issues

My hope is that this scheme= would give some peace of mind to people holding bitcoin, that in the face = of a sudden QC, even with minimal preparation their coins can be safe at re= st and safely moved. =C2=A0It also suggests some best practices for users a= nd wallets to adopt, before any software changes: Don't reuse addresses, an= d if you have taproot outputs, include some kind of script path in the oute= r key.

There are still a number of problems, though!

= - Reorgs can steal coins. =C2=A0An attacker that observes a pubkey and can = reorg back to before the commitment can compute the private key, sign a new= transaction and get their commitment in first on the new chain. =C2=A0This= seems unavoidable with commit/reveal schemes, and it's up to the user how = long they wait between confirming the commitment and revealing the transact= ion.

- How to get op_returns in
If there are no PQ signatur= e schemes activated in bitcoin when this activates, there's only one type o= f transaction that can reliably get the OP_RETURN outputs confirmed: coinba= se transactions. =C2=A0Getting commitments to the miners and paying them ou= t of band is not great, but is possible and we see this kind of activity to= day. =C2=A0Users wouldn't need to directly contact miners: anyone could agg= regate commitments, create a large transaction with many OP_RETURN outputs,= and then get a miner to commit to that parent transaction. =C2=A0Users don= 't need to worry about committing twice as identical commitments would be a= no op.

- Spam
Anyone can make lots of= OP_RETURN commitments which are just random numbers, forcing nodes to stor= e these commitments in a database.=C2=A0 That's not great, but isn't much d= ifferent from how bitcoin works today.=C2=A0 If it's really a problem, node= s could requiring the commitment outputs to have a non-0 amount of bitcoin,= imposing a higher cost for the commitments than other OP_RETURN outputs.

- Multiple inputs
If users have received more tha= n one UTXO to the same address, they will need to spend all the UTXOs at on= ce. =C2=A0The commitment scheme can deal with only the first pubkey seen in= the serialized transaction.

- Multisig and Lightning NetworkIf your multisig counterparties have a QC, multisig outputs become 1 of = N. =C2=A0Possibly a more complex commit / reveal scheme could deal with mul= tiple keys, but the keys would all have to be hashed with counterparties no= t knowing each others' unhashed pubkeys. =C2=A0This isn't how existing mult= isig outputs work, and in fact the current trend is the opposite with thing= s like Musig2, FROST and ROAST. =C2=A0If we're going to need to make new si= gning software and new output types it might make more sense to go for a PQ= signature scheme.

- Making more p2wpkhs
You don't have to = send to a PQ address type with these transactions -- you can send to p2wpkh= and do the whole commit/reveal process again when you want to spend. =C2= =A0This could be helpful if PQ signature schemes are still being worked on,= or if the PQ schemes are more costly to verify and have high fees in compa= rison to the old p2wpkh output types. =C2=A0It's possible that in such a sc= enario a few high-cost PQ transactions commit to many smaller EC transactio= ns. =C2=A0If this actually gets adoption though, we might as well drop the = EC signatures and just make output scripts into raw hash / preimage pairs. = =C2=A0It could make sense to cover some non-EC script types with the same 3= -hash commitment requirement to enable this.

## Conclusion
=
This PQ commit / reveal scheme has similar properties to Tim Ruffing'= s, with a smaller commitment that can be done as a soft fork. =C2=A0I hope = something like this could be soft forked with a PoQC activation trigger, so= that if a QC never shows up, none of this code gets executed. =C2=A0And pe= ople who take a couple easy steps like not reusing addresses (which they sh= ould anyway for privacy reasons) don't have to worry about their coins.

Some of these ideas may have been posted before; I know of the Fawk= scoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the rece= nt discussion which linked to Ruffing's proposal. =C2=A0Here I've tried to = show how it could be done in a soft fork which doesn't look too bad to impl= ement.

I've also heard of some more complex schemes involving z= ero knowledge proofs, proving things like BIP32 derivations, but I think th= is gives some pretty good properties without needing anything other than go= od old SHA256.

Hope this is useful & wonder if people think = something like this would be a good idea.

-Tadge

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com.
------=_Part_439989_607034305.1748452460585-- ------=_Part_439988_173213702.1748452460585--