From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sat, 31 May 2025 09:18:37 -0700 Received: from mail-yb1-f183.google.com ([209.85.219.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uLOuo-0004gB-Iv for bitcoindev@gnusha.org; Sat, 31 May 2025 09:18:37 -0700 Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e742cabfcc0sf4376116276.1 for ; Sat, 31 May 2025 09:18:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1748708308; x=1749313108; 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:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=6gMRpD0GzaH/lYpl285NTyLT/ze5XI9nXTnacW3FJKY=; b=f/Qk88hQiV2yh0nZojrDofCVL1JyRugxZJQMjCf6iPxJjECPFNimuLjYstKS1wBNuu aO23LWhRvLUgLHeWGvUQzQ+1dbGsJakt1+eULHEZlSgyW8tZjADLOXnd3KnaohVigvWb tkjJHSTK8ty7BKKaf+ktskoqXOLcv2pPsxSW0IugLjn7rJbOXBIAzNzNeK46o4PzC45s 21k4C5xK3RBDuuYm9Ea944f0PY14jtm7PE3LQ/2Mh7T7qoPJaUVXaspNCBBa/pEtHkFA KNhzy5M0Zl46ZbtPlYf/B9S+LLoso9JEtNXJo84sIMb1Bd/nuQioyaBO5rWrCu5GQ7BK 2rhA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1748708308; x=1749313108; 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:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=6gMRpD0GzaH/lYpl285NTyLT/ze5XI9nXTnacW3FJKY=; b=DkfC18/TGgzivFMPYCUg4TgWmkRiM9ps8dEE7pmS5VbTGFIlkr6wkUlMKpM68n4xHp oaam6vw7/sjHscKaqgjYZ5KnYQGiqyZv692HXeZ61fNOhUXJ06pDwttdUmTbsVPm2WkO jl+dk1vwsI5qMXgFGf27E5wNYcntg7U4USVsY2FKDudzi/D+RXXvLg232aEDqQBLt5bE 8IJtPRjq7Y/ClWCQo09V6Cb/HlWKpf+MOW2D2EVoEmAGFZHFsUialSi7gz1QJr7h7ACh quDLDNFX8EQ2w6uuFqPS6OGqg7goTBh518YTfa6tMh1swRQhuVR+whko84GrOudIag1P KMaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748708308; x=1749313108; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=6gMRpD0GzaH/lYpl285NTyLT/ze5XI9nXTnacW3FJKY=; b=tXIxY++8AzhWgRl27ximbcu+SW8QIsYC3gmO8by2AYuzPqqxfpHXmpKLzWjgCvqGcI NBiHOlOhEldrjctHe7iQD17dD+Iak2vell/GEF1tYUu5AlDgDDpVF8B3sBny0DUGasbO ML0MXKUfTOhOXiPrRo3DtcgWXSMmXyN5T/AFY3zGCbk07N2eAEzJ/kIwTWl0GLq2K9/F hVEi4iK8K3TPpwH5Lw2HLVm7pqxBnA24IfL+Pjy8/bBNwYOVxYvxB3JMr+hEtcVHOcjt dT1qupI30ZR2O1xgS7GS3lsIglZkEfamvWnFj5pDIUNGhCSmslgX49j9NQGXiMp0BhBs CH+w== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXRrmU3HKMPg48BEXNzNwP/Lu2C9kMXY5/RpdnIYqot/TO5nlffRFK3etfIBOWPDHYvU994dAtcHB7c@gnusha.org X-Gm-Message-State: AOJu0Yz+M07Yla1AA0dGhilu1wDN/7G55TJfv4erNIpZu148qqs6Ga/5 EvP3w3Zt8b29MFZuspuC+fbWOG2WOnQWs6+YrprvGbZHCTEQ7IIOythu X-Google-Smtp-Source: AGHT+IEZw0Ncv9//h8QMFFxuH3Vk8RPvxwfuK+zFJ6pLF1s83DNYYbXfhSfJ/0nLJ6RwNEAih1ED+A== X-Received: by 2002:a05:6902:2487:b0:e7f:263e:42c8 with SMTP id 3f1490d57ef6-e7f821a3ae2mr10138888276.40.1748708308132; Sat, 31 May 2025 09:18:28 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZc/pFf2CA4GblUVHkc93PSL2JBylcBLkd3MutjIgXrITw== Received: by 2002:a25:abc2:0:b0:e7d:cd62:3589 with SMTP id 3f1490d57ef6-e7f6f7eea1cls3139054276.2.-pod-prod-04-us; Sat, 31 May 2025 09:18:23 -0700 (PDT) X-Received: by 2002:a05:690c:4907:b0:70d:f07c:f593 with SMTP id 00721157ae682-710504bb2d6mr95779097b3.6.1748708303704; Sat, 31 May 2025 09:18:23 -0700 (PDT) Received: by 2002:a05:690c:6083:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-70f980e43fams7b3; Sat, 31 May 2025 09:07:44 -0700 (PDT) X-Received: by 2002:a05:690c:450c:b0:70c:d322:872c with SMTP id 00721157ae682-710502d15f1mr88041637b3.1.1748707663551; Sat, 31 May 2025 09:07:43 -0700 (PDT) Date: Sat, 31 May 2025 09:07:43 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <6ca6d847-1b15-48fd-89e1-09c4d5e42e38n@googlegroups.com> In-Reply-To: References: Subject: [bitcoindev] Re: Post-Quantum commit / reveal Fawkescoin variant as a soft fork MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_10722_1746068246.1748707663203" X-Original-Sender: ekaggata@gmail.com 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.5 (/) ------=_Part_10722_1746068246.1748707663203 Content-Type: multipart/alternative; boundary="----=_Part_10723_271167117.1748707663203" ------=_Part_10723_271167117.1748707663203 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Tadge, list, Appreciate this writeup. I found that the discursive detail avoided some=20 confusions I had with Tim's and Adam's earlier descriptions, though there= =20 are clearly a ton of subtle differences in the various designs. Anyway, one detail: you have h(pubkey), h(pubkey,txid), txid. You note=20 earlier that h should be tagged for domain separation purposes. But if you= =20 meant literally the same h for the first two components of the tuple,=20 there's a flaw, depending on h; length extension attacks could allow the=20 creation of h(pubkey,txid') without knowing pubkey. I'm going to ignore the= =20 trickier question of whether that matters based on how txid is derived from= =20 a transaction (given txid vs wtxid, I guess it actually really does).=20 Presumably just use h2 which differs from h, either a different hash or a= =20 different prefix, to avoid this. And/or swapping h(txid,pubkey) etc.=20 Obviously using h() that is not susceptible to LEA avoids the Q being=20 raised, but that may be more or less easy in Bitcoin-land. Cheers, AdamISZ/waxwing On Wednesday, May 28, 2025 at 2:28:25=E2=80=AFPM UTC-3 Tadge Dryja wrote: > One of the tricky things about securing Bitcoin against quantum computers= =20 > is: do you even need to? Maybe quantum computers that can break secp256k= 1=20 > keys will never exist, in which case we shouldn't waste our time. Or may= be=20 > they will exist, in not too many years, and we should spend the effort to= =20 > secure the system against QCs. > > Since people disagree on how likely QCs are to arrive, and what the timin= g=20 > would be if they do, it's hard to get consensus on changes to bitcoin tha= t=20 > disrupt the properties we use today. For example, a soft fork introducin= g=20 > a post-quantum (PQ) signature scheme and at the same time disallowing new= =20 > secp256k1 based outputs would be great for strengthening Bitcoin against = an=20 > oncoming QC. But it would be awful if a QC never appears, or takes decad= es=20 > to do so, since secp256k1 is really nice. > > So it would be nice to have a way to not deal with this issue until=20 > *after* the QC shows up. With commit / reveal schemes Bitcoin can keep= =20 > working after a QC shows up, even if we haven't defined a PQ signature=20 > scheme and everyone's still got P2WPKH outputs. > > Most of this is similar to Tim Ruffing's proposal from a few years ago=20 > here: > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/=20 > > > The main difference is that this scheme doesn't use encryption, but a=20 > smaller hash-based commitment, and describes activation as a soft fork.= =20 > I'll define the two types of attacks, a commitment scheme, and then say= =20 > 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)= =20 > with pubkeys that are unknown to the network. It works with taproot as= =20 > well, but there must be some script-path in the taproot key, as keypath= =20 > spends would no longer be secure. =20 > > What to do with all the keys that are known is another issue and=20 > independent of the scheme in this post (it's compatible with both burning= =20 > them and leaving them to be stolen) > > For these schemes, we assume there is an attacker with a QC that can=20 > compute a quickly compute a private key from any secp256k1 public key. W= e=20 > also assume the attacker has some mining power or influence over miners f= or=20 > their attacks; maybe not reliably, but they can sometimes get a few block= s=20 > in a row with the transactions they want. > > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output= =20 > types and should work about the same way (with caveats about multisig).= =20 > The equivalent for taproot outputs would be an inner key proving a scrip= t=20 > path. > > ## A simple scheme to show an attack > > The simplest commit/reveal scheme would be one where after activation, fo= r=20 > any transaction with an EC signature in it, that transaction's txid must= =20 > appear in a earlier transaction's OP_RETURN output. > > When a user wants to spend their coins, they first sign a transaction as= =20 > they would normally, compute the txid, get that txid into an OP_RETURN=20 > output somehow (paying a miner out of band, etc), then after waiting a=20 > while, broadcast the transaction. Nodes would check that the txid matche= s=20 > a previously seen commitment, and allow the transaction. > > One problem with this scheme is that upon seeing the full transaction, th= e=20 > attacker can compute the user's private key, and create a new commitment= =20 > with a different txid for a transaction where the attacker gets all the= =20 > coins. If the attacker can get their commitment and spending transaction= =20 > in before the user's transaction, they can steal the coins. > > In order to mitigate this problem, a minimum delay can be enforced by=20 > consensus. A minimum delay of 100 blocks would mean that the attacker=20 > would have to prevent the user's transaction from being confirmed for 100= =20 > blocks after it showed up in the attacker's mempool. The tradeoff is tha= t=20 > longer periods give better safety at the cost of more delay in spending. > > This scheme, while problematic, is better than nothing! But it's possibl= e=20 > 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= =20 > spent, and the txid that was going to spend it, we could add a "first see= n"=20 > consensus rule. Only the first commitment pointing to an outpoint works. > > So if nodes see two OP_RETURN commitments in their sequence of confirmed= =20 > transactions: > > C1 =3D outpoint1, txid1 > C2 =3D outpoint1, txid2 > > They can ignore C2; C1 has already laid claim to outpoint1, and the=20 > transaction identified by txid1 is the only transaction that can spend=20 > outpoint1. > > If the user manages to get C1 confirmed first, this is great, and=20 > eliminates the timing problem in the txid only scheme. But this introduc= es=20 > a different problem, where an attacker -- in this case any attacker, even= =20 > one without a QC -- who can observe C1 before it is confirmed can flip so= me=20 > 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= =20 > discard invalid commitments. In a bit flipping attack, we could say an= =20 > invalid commitment is one where there is no transaction described by the= =20 > txid. A more general way to classify a commitment as invalid is a=20 > commitment made without knowledge of the (secret) pubkey. Knowledge of t= he=20 > 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= =20 > it needs to be keyed with some tag, for example "Alas poor Koblitz curve,= =20 > we knew it well". > > Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoi= n=20 > output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin= =20 > terms, HASH160(pubkey). Due to the hash functions being different, A =3D= =20 > HASH160(pubkey) and B =3D h(pubkey) will be completely different, and nob= ody=20 > should be able to determine if A and B are hashes of the same pubkey=20 > without knowing pubkey itself. > > An efficient commitment is: > > C =3D h(pubkey), h(pubkey, txid), txid > (to label things: C =3D AID, SDP, CTXID) > > This commitment includes 3 elements: a different hash of the pubkey which= =20 > will be signed for, a proof of knowledge of the pubkey which commits to a= =20 > transaction, and an the txid of the spending transaction. We'll call the= se=20 > "address ID" (AID), sequence dependent proof (SDP), and the commitment tx= id=20 > (CTXID). > > For those familiar with the proposal by Ruffing, the SDP has a similar=20 > function to the authenticated encryption part of the encrypted commitment= .=20 > Instead of using authenticated encryption, we can instead just use an=20 > HMAC-style authentication alone, since the other data, the CTXID, is=20 > provided.=20 > > When the user's wallet creates a transaction, they can feed that=20 > transaction into a commitment generator function which takes in a=20 > transaction, extracts the pubkey from the tx, computes the 3 hashes, and= =20 > returns the 3-hash commitment. Once this commitment is confirmed, the us= er=20 > broadcasts the transaction. > > Nodes verify the commitment by using the same commitment generator=20 > function and checking if it matches the first valid commitment for that= =20 > AID, in which case the tx is confirmed. > > If a node sees multiple commitments all claiming the same AID, it must=20 > store all of them. Once the AID's pubkey is known, the node can=20 > distinguish which commitments are valid, which are invalid, and which is= =20 > the first seen valid commitment. Given the pubkey, nodes can determine= =20 > commitments to be invalid by 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. But an attacker=20 > creates C1, committing to a different txid where they control the outputs= ,=20 > and confirms it first. This attacker may know the outpoint being spent,= =20 > and may be able to create a transaction and txid that could work. But th= ey=20 > don't know the pubkey, so while they can copy the AID hash, they have to= =20 > make something up for the SDP. > > The user gets C2 confirmed after C1. They then reveal tx2 in the mempool= ,=20 > but before it can be confirmed, the attacker gets C3 confirmed. C3 is a= =20 > valid commitment made with knowledge of the pubkey. > > Nodes can reject transactions tx1 and tx3. For tx1, they will see that= =20 > the SDP doesn't match the data in the transaction, so it's an invalid=20 > commitment. For tx3, they will see that it is valid, but by seeing tx3= =20 > they will also be able to determine that C2 is a valid commitment (since= =20 > pubkey is revealed in tx3) which came prior to C3, making C2 the only val= id=20 > commitment for that AID. > > > ## Implementation > > Nodes would keep a new key/value store, similar to the existing UTXO set.= =20 > The indexing key would be the AID, and the value would be the set of all= =20 > (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is= =20 > seen in an OP_RETURN, nodes store the commitment. > > When a transaction is seen, nodes observe the pubkey used in the=20 > transaction, and look up if it matches an AID they have stored. If not,= =20 > the transaction is dropped. If the AID does match, the node can now "cle= an=20 > out" an AID entry, eliminating all but the first valid commitment, and=20 > marking that AID as final. If the txid seen matches the remaining=20 > commitment, the transaction is valid; if not, the transaction is dropped. > > After the transaction is confirmed the AID entry can be deleted. Deletin= g=20 > the entries frees up space, and would allow another round to happen with= =20 > the same pubkey, which would lead to theft. Retaining the entries takes = up=20 > more space on nodes that can't be pruned, and causes pubkey reuse to=20 > destroy coins rather than allow them to be stolen. That's a tradeoff, an= d=20 > I personally guess it's probably not worth retaining that data but don't= =20 > have a strong opinion either way. > > Short commitments: > > Since we're not trying to defend against collision attacks, I think all 3= =20 > hashes can be truncated to 16 bytes. The whole commitment could be 48=20 > bytes long. Without truncation the commitments would be 96 bytes. > > > ## Activation > > The activation for the commit/reveal requirement can be triggered by a=20 > 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 satisf= y=20 > this script, the spending transaction needs to provide 2 data elements: a= =20 > signature, and some data that when hashed results in a pubkey for which= =20 > that signature is valid. If such a pair of data elements exists, it mean= s=20 > that either SHA256 preimage resistance is broken (which we're assuming=20 > isn't the case) or someone can create valid signatures for arbitrary=20 > elliptic curve points, ie a cryptographically relevant quantum computer (= or=20 > any other process which breaks the security of secp256k1 signatures) > > Once such a PoQC has been observed in a confirmed transaction, the=20 > requirements for the 3-hash commitment scheme can be enforced. This is a= =20 > soft fork since the transactions themselves look the same, the only=20 > requirement is that some OP_RETURN outputs show up earlier. Nodes which= =20 > are not aware of the commitment requirement will still accept all=20 > transactions with the new rules. =20 > > Wallets not aware of the new rules, however, are very dangerous, as they= =20 > may try to broadcast signed transactions without any commitment. Nodes= =20 > that see such a transaction should drop the tx, and if possible tell the= =20 > wallet that they are doing something which is now very dangerous! On the= =20 > open p2p network this is not really enforceable, but people submitting=20 > transactions to their own node (eg via RPC) can at least get a scary erro= r=20 > message. > > > ## Issues > > My hope is that this scheme would give some peace of mind to people=20 > holding bitcoin, that in the face of a sudden QC, even with minimal=20 > preparation their coins can be safe at rest and safely moved. It also=20 > suggests some best practices for users and wallets to adopt, before any= =20 > software changes: Don't reuse addresses, and if you have taproot outputs,= =20 > 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=20 > reorg back to before the commitment can compute the private key, sign a n= ew=20 > transaction and get their commitment in first on the new chain. This see= ms=20 > unavoidable with commit/reveal schemes, and it's up to the user how long= =20 > 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=20 > activates, there's only one type of transaction that can reliably get the= =20 > OP_RETURN outputs confirmed: coinbase transactions. Getting commitments = to=20 > the miners and paying them out of band is not great, but is possible and = we=20 > see this kind of activity today. Users wouldn't need to directly contact= =20 > miners: anyone could aggregate commitments, create a large transaction wi= th=20 > many OP_RETURN outputs, and then get a miner to commit to that parent=20 > transaction. Users don't need to worry about committing twice as identic= al=20 > commitments would be a no op. > > - Spam > Anyone can make lots of OP_RETURN commitments which are just random=20 > numbers, forcing nodes to store these commitments in a database. That's= =20 > not great, but isn't much different from how bitcoin works today. If it'= s=20 > really a problem, nodes could requiring the commitment outputs to have a= =20 > non-0 amount of bitcoin, imposing a higher cost for the commitments than= =20 > other OP_RETURN outputs. > > - Multiple inputs > If users have received more than one UTXO to the same address, they will= =20 > need to spend all the UTXOs at once. The commitment scheme can deal with= =20 > 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= .=20 > Possibly a more complex commit / reveal scheme could deal with multiple= =20 > keys, but the keys would all have to be hashed with counterparties not=20 > knowing each others' unhashed pubkeys. This isn't how existing multisig= =20 > outputs work, and in fact the current trend is the opposite with things= =20 > like Musig2, FROST and ROAST. If we're going to need to make new signing= =20 > software and new output types it might make more sense to go for a PQ=20 > signature scheme. > > - Making more p2wpkhs > You don't have to send to a PQ address type with these transactions -- yo= u=20 > can send to p2wpkh and do the whole commit/reveal process again when you= =20 > want to spend. This could be helpful if PQ signature schemes are still= =20 > being worked on, or if the PQ schemes are more costly to verify and have= =20 > high fees in comparison to the old p2wpkh output types. It's possible th= at=20 > in such a scenario a few high-cost PQ transactions commit to many smaller= =20 > EC transactions. If this actually gets adoption though, we might as well= =20 > drop the EC signatures and just make output scripts into raw hash /=20 > preimage pairs. It could make sense to cover some non-EC script types wi= th=20 > the same 3-hash commitment requirement to enable this. > > ## Conclusion > > This PQ commit / reveal scheme has similar properties to Tim Ruffing's,= =20 > with a smaller commitment that can be done as a soft fork. I hope=20 > something like this could be soft forked with a PoQC activation trigger, = so=20 > that if a QC never shows up, none of this code gets executed. And people= =20 > who take a couple easy steps like not reusing addresses (which they shoul= d=20 > 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= =20 > paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent= =20 > discussion which linked to Ruffing's proposal. Here I've tried to show h= ow=20 > it could be done in a soft fork which doesn't look too bad to implement.= =20 > > I've also heard of some more complex schemes involving zero knowledge=20 > proofs, proving things like BIP32 derivations, but I think this gives som= e=20 > pretty good properties without needing anything other than good old SHA25= 6. > > Hope this is useful & wonder if people think something like this would be= =20 > a good idea. > > -Tadge > > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 6ca6d847-1b15-48fd-89e1-09c4d5e42e38n%40googlegroups.com. ------=_Part_10723_271167117.1748707663203 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Tadge, list,

Appreciate this writeup. I = found that the discursive detail avoided some confusions I had with Tim's a= nd Adam's earlier descriptions, though there are clearly a ton of subtle di= fferences in the various designs.

Anyway, one de= tail: you have h(pubkey), h(pubkey,txid), txid. You note earlier that h sho= uld be tagged for domain separation purposes. But if you meant literally th= e same h for the first two components of the tuple, there's a flaw, dependi= ng on h; length extension attacks could allow the creation of h(pubkey,txid= ') without knowing pubkey. I'm going to ignore the trickier question of whe= ther that matters based on how txid is derived from a transaction (given tx= id vs wtxid, I guess it actually really does). Presumably just use h2 which= differs from h, either a different hash or a different prefix, to avoid th= is. And/or swapping h(txid,pubkey) etc. Obviously using h() that is not sus= ceptible to LEA avoids the Q being raised, but that may be more or less eas= y in Bitcoin-land.

Cheers,
AdamISZ/waxwing<= /div>
On Wednesday, May 28, 2025 at 2:28:25=E2=80=AFPM UTC-3 Tadge Dryja wrote:=
One of the t= ricky things about securing Bitcoin against quantum computers is: do you ev= en need to? =C2=A0Maybe quantum computers that can break secp256k1 keys wil= l never exist, in which case we shouldn't waste our time. =C2=A0Or mayb= e 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 t= o get consensus on changes to bitcoin that disrupt the properties we use to= day. =C2=A0For example, a soft fork introducing a post-quantum (PQ) signatu= re scheme and at the same time disallowing new secp256k1 based outputs woul= d be great for strengthening Bitcoin against an oncoming QC. =C2=A0But it w= ould be awful if a QC never appears, or takes decades to do so, since secp2= 56k1 is really nice.

So it would be nice to have a way to not deal w= ith this issue until *after* the QC shows up. =C2=A0With commit / reveal sc= hemes 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.<= br>
Most of this is similar to Tim Ruffing's proposal from a few yea= rs ago here:
https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/

The main difference is that this scheme doesn't use encryptio= n, but a smaller hash-based commitment, and describes activation as a soft = fork. =C2=A0I'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 hashe= s) with pubkeys that are unknown to the network. =C2=A0It works with taproo= t as well, but there must be some script-path in the taproot key, as keypat= h spends would no longer be secure. =C2=A0

What to do with all the k= eys that are known is another issue and independent of the scheme in this p= ost (it's compatible with both burning them and leaving them to be stol= en)

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.= =C2=A0We 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&qu= ot; can also be substituted with "script" for P2SH and P2WSH outp= ut types and should work about the same way (with caveats about multisig). = =C2=A0The equivalent for taproot outputs would be an inner key proving a sc= ript path.

## A simple scheme to show an attack

The simplest = commit/reveal scheme would be one where after activation, for any transacti= on 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 sp= end their coins, they first sign a transaction as they would normally, comp= ute the txid, get that txid into an OP_RETURN output somehow (paying a mine= r out of band, etc), then after waiting a while, broadcast the transaction.= =C2=A0Nodes would check that the txid matches a previously seen commitment= , and allow the transaction.

One problem with this scheme is that up= on seeing the full transaction, the attacker can compute the user's pri= vate key, and create a new commitment with a different txid for a transacti= on where the attacker gets all the coins. =C2=A0If the attacker can get the= ir commitment and spending transaction in before the user's transaction= , they can steal the coins.

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

This scheme, while problema= tic, is better than nothing! =C2=A0But it's possible to remove this tim= ing tradeoff.


## A slightly more complex scheme with (worse) pro= blems

If instead of just the txid, the commitment were both the outp= oint being spent, and the txid that was going to spend it, we could add a &= quot;first seen" consensus rule. =C2=A0Only the first commitment point= ing to an outpoint works.

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

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

They can ignore C2; C1 has already laid = claim to outpoint1, and the transaction identified by txid1 is the only tra= nsaction that can spend outpoint1.

If the user manages to get C1 con= firmed first, this is great, and eliminates the timing problem in the txid = only scheme. =C2=A0But this introduces a different problem, where an attack= er -- in this case any attacker, even one without a QC -- who can observe C= 1 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. =C2=A0In a bi= t flipping attack, we could say an invalid commitment 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 without knowledge of the (sec= ret) pubkey. =C2=A0Knowledge of the pubkey is what security of coins is now= hinging on.


The actual commitment scheme


We define s= ome hash function h(). =C2=A0We'll use SHA256 for the hashing, but it n= eeds 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 has= h already used in the bitcoin output script, which instead is RIPEMD160(SHA= 256(pubkey)), or in bitcoin terms, HASH160(pubkey). =C2=A0Due to the hash f= unctions being different, A =3D HASH160(pubkey) and B =3D h(pubkey) will be= completely different, and nobody should be able to determine if A and B ar= e hashes of the same pubkey without knowing pubkey itself.

An effici= ent commitment is:

C =3D =C2=A0h(pubkey), h(pubkey, txid), txid
<= div>(to label things: C =3D AID, SDP, CTXID)

This commi= tment includes 3 elements: a different hash of the pubkey which will be sig= ned for, a proof of knowledge of the pubkey which commits to a transaction,= and an the txid of the spending transaction. =C2=A0We'll call these &q= uot;address ID" (AID), sequence dependent proof (SDP), and the commitm= ent txid (CTXID).

For those familiar with the proposal by Ruffing, t= he SDP has a similar function to the authenticated encryption part of the e= ncrypted commitment. =C2=A0Instead of using authenticated encryption, we ca= n instead just use an HMAC-style authentication alone, since the other data= , the CTXID, is provided.

When the user's wallet creates a tran= saction, they can feed that transaction into a commitment generator functio= n which takes in a transaction, extracts the pubkey from the tx, computes t= he 3 hashes, and returns the 3-hash commitment. =C2=A0Once 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 sam= e AID, it must store all of them. =C2=A0Once the AID's pubkey is known,= the node can distinguish which commitments are valid, which are invalid, a= nd which is the first seen valid commitment. =C2=A0Given the pubkey, nodes = can determine commitments to be invalid by checking if SDP =3D h(pubkey, CT= XID).

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 txid where they control the outputs, and confir= ms it first. =C2=A0This attacker may know the outpoint being spent, and may= be able to create a transaction and txid that could work. =C2=A0But they d= on'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.= =C2=A0They then reveal tx2 in the mempool, but before it can be confirmed,= the attacker gets C3 confirmed. =C2=A0C3 is a valid commitment made with k= nowledge of the pubkey.

Nodes can reject transactions tx1 and tx3. = =C2=A0For tx1, they will see that the SDP doesn't match the data in the= transaction, so it's an invalid commitment. =C2=A0For tx3, they will s= ee 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. =C2=A0The indexing key would be the AID, and the val= ue would be the set of all (SDP, CTXID) pairs seen alongside that AID. =C2= =A0Every time an commitment is seen in an OP_RETURN, nodes store the commit= ment.

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

After the transaction is confirmed the AID entry can b= e deleted. =C2=A0Deleting the entries frees up space, and would allow anoth= er round to happen with the same pubkey, which would lead to theft. =C2=A0R= etaining 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 stol= en. =C2=A0That's a tradeoff, and I personally guess it's probably n= ot worth retaining that data but don't have a strong opinion either way= .

Short commitments:

Since we're not trying to defend aga= inst 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 act= ivation for the commit/reveal requirement can be triggered by a proof of qu= antum computer (PoQC).

A transaction which successfully spends an ou= tput 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 transaction needs to provide 2 data elements: a signature, an= d some data that when hashed results in a pubkey for which that signature i= s valid. =C2=A0If such a pair of data elements exists, it means that either= SHA256 preimage resistance is broken (which we're assuming isn't t= he case) or someone can create valid signatures for arbitrary elliptic curv= e points, ie a cryptographically relevant quantum computer (or any other pr= ocess which breaks the security of secp256k1 signatures)

Once such a= PoQC has been observed in a confirmed transaction, the requirements for th= e 3-hash commitment scheme can be enforced. =C2=A0This is a soft fork since= the transactions themselves look the same, the only requirement is that so= me OP_RETURN outputs show up earlier. =C2=A0Nodes which are not aware of th= e commitment requirement will still accept all transactions with the new ru= les. =C2=A0

Wallets not aware of the new rules, however, are very da= ngerous, as they may try to broadcast signed transactions without any commi= tment. =C2=A0Nodes that see such a transaction should drop the tx, and if p= ossible tell the wallet that they are doing something which is now very dan= gerous! =C2=A0On the open p2p network this is not really enforceable, but p= eople submitting transactions to their own node (eg via RPC) can at least g= et 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. =C2=A0It also suggests some best practices for u= sers and wallets to adopt, before any software changes: Don't reuse add= resses, and if you have taproot outputs, include some kind of script path i= n the outer key.

There are still a number of problems, though!
- Reorgs can steal coins. =C2=A0An attacker that observes a pubkey and ca= n reorg back to before the commitment can compute the private key, sign a n= ew transaction and get their commitment in first on the new chain. =C2=A0Th= is seems unavoidable with commit/reveal schemes, and it's up to the use= r how long they wait between confirming the commitment and revealing the tr= ansaction.

- How to get op_returns in
If there are no PQ signatur= e schemes activated in bitcoin when this activates, there's only one ty= pe of transaction that can reliably get the OP_RETURN outputs confirmed: co= inbase transactions. =C2=A0Getting commitments to the miners and paying the= m out of band is not great, but is possible and we see this kind of activit= y today. =C2=A0Users wouldn't need to directly contact miners: anyone c= ould aggregate commitments, create a large transaction with many OP_RETURN = outputs, and then get a miner to commit to that parent transaction. =C2=A0U= sers don't need to worry about committing twice as identical commitment= s 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.=C2=A0 That's not great, but = isn't much different from how bitcoin works today.=C2=A0 If it's re= ally 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 r= eceived more than one UTXO to the same address, they will need to spend all= the UTXOs at once. =C2=A0The commitment scheme can deal with only the firs= t pubkey seen in the serialized transaction.

- Multisig and Lightnin= g Network
If your multisig counterparties have a QC, multisig outputs be= come 1 of N. =C2=A0Possibly a more complex commit / reveal scheme could dea= l with multiple keys, but the keys would all have to be hashed with counter= parties not knowing each others' unhashed pubkeys. =C2=A0This isn't= how existing multisig outputs work, and in fact the current trend is the o= pposite with things like Musig2, FROST and ROAST. =C2=A0If we're going = to need to make new signing software and new output types it might make mor= e sense to go for a PQ signature scheme.

- Making more p2wpkhs
Yo= u don't have to send to a PQ address type with these transactions -- yo= u 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 stil= l 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. =C2=A0It's poss= ible that in such a scenario a few high-cost PQ transactions commit to many= smaller EC transactions. =C2=A0If this actually gets adoption though, we m= ight as well drop the EC signatures and just make output scripts into raw h= ash / 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 t= o Tim Ruffing's, with a smaller commitment that can be done as a soft f= ork. =C2=A0I hope something like this could be soft forked with a PoQC acti= vation trigger, so that if a QC never shows up, none of this code gets exec= uted. =C2=A0And people who take a couple easy steps like not reusing addres= ses (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.p= df) and the recent 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 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 witho= ut needing anything other than good old SHA256.

Hope this is useful = & wonder if people think something like this would be a good idea.
<= br>-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/6ca6d847-1b15-48fd-89e1-09c4d5e42e38n%40googlegroups.com.
------=_Part_10723_271167117.1748707663203-- ------=_Part_10722_1746068246.1748707663203--