path: root/fc/c78c956a736451fd5f74623a7ebc9d726610c9

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 <bitcoindev+bncBDI23FE35EIBBUGX5TAQMGQEGAE6Q3A@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <6ca6d847-1b15-48fd-89e1-09c4d5e42e38n@googlegroups.com>
In-Reply-To: <cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com>
References: <cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com>
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: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
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
> <https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saar=
land.de/>
>
> 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

<div>Hi Tadge, list,</div><div><br /></div><div>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.</div><div><br /></div><div>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.</div><div><br /></div><div>Cheers,<br />AdamISZ/waxwing<=
/div><br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr=
">On Wednesday, May 28, 2025 at 2:28:25=E2=80=AFPM UTC-3 Tadge Dryja wrote:=
<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; =
border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">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&#39;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.<br><br>Since people disagree on how likely =
QCs are to arrive, and what the timing would be if they do, it&#39;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.<br><br>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&#39;t =
defined a PQ signature scheme and everyone&#39;s still got P2WPKH outputs.<=
br><br>Most of this is similar to Tim Ruffing&#39;s proposal from a few yea=
rs ago here:<br><a href=3D"https://gnusha.org/pi/bitcoindev/1518710367.3550=
.111.camel@mmci.uni-saarland.de/" target=3D"_blank" rel=3D"nofollow" data-s=
aferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://gnusha=
.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/&amp;sour=
ce=3Dgmail&amp;ust=3D1748792617357000&amp;usg=3DAOvVaw0p7sryoCJMlt8rgBvlvDy=
d">https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/</=
a><br><br>The main difference is that this scheme doesn&#39;t use encryptio=
n, but a smaller hash-based commitment, and describes activation as a soft =
fork. =C2=A0I&#39;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.<br>=
<br>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<br><br>What to do with all the k=
eys that are known is another issue and independent of the scheme in this p=
ost (it&#39;s compatible with both burning them and leaving them to be stol=
en)<br><br>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.<br><br>&quot;Pubkey&qu=
ot; can also be substituted with &quot;script&quot; 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.<br><br>## A simple scheme to show an attack<br><br>The simplest =
commit/reveal scheme would be one where after activation, for any transacti=
on with an EC signature in it, that transaction&#39;s txid must appear in a=
 earlier transaction&#39;s OP_RETURN output.<br><br>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.<br><br>One problem with this scheme is that up=
on seeing the full transaction, the attacker can compute the user&#39;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&#39;s transaction=
, they can steal the coins.<br><br>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&#39;s transac=
tion from being confirmed for 100 blocks after it showed up in the attacker=
&#39;s mempool. =C2=A0The tradeoff is that longer periods give better safet=
y at the cost of more delay in spending.<br><br>This scheme, while problema=
tic, is better than nothing! =C2=A0But it&#39;s possible to remove this tim=
ing tradeoff.<br><br><br>## A slightly more complex scheme with (worse) pro=
blems<br><br>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&quot; consensus rule. =C2=A0Only the first commitment point=
ing to an outpoint works.<br><br>So if nodes see two OP_RETURN commitments =
in their sequence of confirmed transactions:<br><br>C1 =3D outpoint1, txid1=
<br>C2 =3D outpoint1, txid2<br><br>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.<br><br>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.<br><br>We want to retain the &quot;first seen&quot; 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.<br><br><br>The actual commitment scheme<br><br><br>We define s=
ome hash function h(). =C2=A0We&#39;ll use SHA256 for the hashing, but it n=
eeds to be keyed with some tag, for example &quot;Alas poor Koblitz curve, =
we knew it well&quot;.<br><br>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.<br><br>An effici=
ent commitment is:<br><br>C =3D =C2=A0h(pubkey), h(pubkey, txid), txid<br><=
div>(to label things: C =3D AID, SDP, CTXID)</div><div><br></div>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&#39;ll call these &q=
uot;address ID&quot; (AID), sequence dependent proof (SDP), and the commitm=
ent txid (CTXID).<br><br>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. <br><br>When the user&#39;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.<br><br>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.<br><br>If a node sees multiple commitments all claiming the sam=
e AID, it must store all of them. =C2=A0Once the AID&#39;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).<br><br>As an example, consider a sequence of 3 commitments:<br><br>C1=
 =3D h(pubkey), h(pubkey&#39;, txid1), txid1<br>C2 =3D h(pubkey), h(pubkey,=
 txid2), txid2<br>C3 =3D h(pubkey), h(pubkey, txid3), txid3<br><br>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&#39;t know the pubkey, so while they can copy the AID hash, they have to=
 make something up for the SDP.<br><br>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.<br><br>Nodes can reject transactions tx1 and tx3. =
=C2=A0For tx1, they will see that the SDP doesn&#39;t match the data in the=
 transaction, so it&#39;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.<br><br><br>#=
# Implementation<br><br>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.<br><br>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 &quot;clean out&quot; 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.<br><br>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&#39;t be pruned,=
 and causes pubkey reuse to destroy coins rather than allow them to be stol=
en. =C2=A0That&#39;s a tradeoff, and I personally guess it&#39;s probably n=
ot worth retaining that data but don&#39;t have a strong opinion either way=
.<br><br>Short commitments:<br><br>Since we&#39;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.<br><br><br>## Activation<br><br>The act=
ivation for the commit/reveal requirement can be triggered by a proof of qu=
antum computer (PoQC).<br><br>A transaction which successfully spends an ou=
tput using tapscript:<br><br>OP_SHA256 OP_CHECKSIG<br><br>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&#39;re assuming isn&#39;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)<br><br>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<br><br>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.<br><br><br>## Issues<br><br>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&#39;t reuse add=
resses, and if you have taproot outputs, include some kind of script path i=
n the outer key.<br><br>There are still a number of problems, though!<br><b=
r>- 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&#39;s up to the use=
r how long they wait between confirming the commitment and revealing the tr=
ansaction.<br><br>- How to get op_returns in<br>If there are no PQ signatur=
e schemes activated in bitcoin when this activates, there&#39;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&#39;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&#39;t need to worry about committing twice as identical commitment=
s would be a no op.<br><div><br></div><div>- Spam</div><div>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&#39;s not great, but =
isn&#39;t much different from how bitcoin works today.=C2=A0 If it&#39;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.</div><div><br></div>- Multiple inputs<br>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.<br><br>- Multisig and Lightnin=
g Network<br>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&#39; unhashed pubkeys. =C2=A0This isn&#39;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&#39;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.<br><br>- Making more p2wpkhs<br>Yo=
u don&#39;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&#39;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.<br><br>#=
# Conclusion<br><br>This PQ commit / reveal scheme has similar properties t=
o Tim Ruffing&#39;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&#39;t have to worry =
about their coins.<br><br>Some of these ideas may have been posted before; =
I know of the Fawkscoin paper (<a href=3D"https://jbonneau.com/doc/BM14-SPW=
-fawkescoin.pdf" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D=
"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://jbonneau.com/doc/BM14-S=
PW-fawkescoin.pdf&amp;source=3Dgmail&amp;ust=3D1748792617358000&amp;usg=3DA=
OvVaw3zL2Gng2TH5dSqAYaaAr7l">https://jbonneau.com/doc/BM14-SPW-fawkescoin.p=
df</a>) and the recent discussion which linked to Ruffing&#39;s proposal. =
=C2=A0Here I&#39;ve tried to show how it could be done in a soft fork which=
 doesn&#39;t look too bad to implement. <br><br>I&#39;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.<br><br>Hope this is useful =
&amp; wonder if people think something like this would be a good idea.<br><=
br>-Tadge<br><br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/6ca6d847-1b15-48fd-89e1-09c4d5e42e38n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/6ca6d847-1b15-48fd-89e1-09c4d5e42e38n%40googlegroups.com</a>.<br />

------=_Part_10723_271167117.1748707663203--

------=_Part_10722_1746068246.1748707663203--