path: root/48/bc20e8798e6161c98f3ff38673d44c0e054e34

Delivery-date: Mon, 02 Jun 2025 11:41:48 -0700
Received: from mail-yb1-f186.google.com ([209.85.219.186])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDI23FE35EIBBXXA67AQMGQEOXHGOVQ@googlegroups.com>)
	id 1uMA6T-0002hq-AL
	for bitcoindev@gnusha.org; Mon, 02 Jun 2025 11:41:48 -0700
Received: by mail-yb1-f186.google.com with SMTP id 3f1490d57ef6-e742cabfcc0sf6850720276.1
        for <bitcoindev@gnusha.org>; Mon, 02 Jun 2025 11:41:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1748889699; x=1749494499; 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=ICNtWJqhMu9+Zs8hdxO7BQriu5oU8Ra1McfQFGTl2jw=;
        b=YoHq/aAGcrdOVgqzKbzwlrSF+IAYokqIbzGClh4oLFe4pPGnGlgZe9eP2s46FigrpH
         B7TRAvOrA6Dt6kL+ZX+xT/I0aVwcfe6L36YkXlwizqT4Ia4LludrSykidyiwASsSxWH3
         iwJMr0rHQT+yeZVZkegYPDxaptx1QgupEKdtb6xeFtnECyxpCMuo1KAfO1AYskJdpKJz
         FQy7ET1U47S9uqViSLZl/xiWPb3oOjtIvO0SrmEaBp/Pwf8NigSLS0DFKyuWJjLPVNFY
         QpVUbtIY1ZOW0awRwF6Bvq4/3K69+7h0yeIBYh/g+ncmqF6WVkaksjckPi3zph42Ou4O
         bMDg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1748889699; x=1749494499; 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=ICNtWJqhMu9+Zs8hdxO7BQriu5oU8Ra1McfQFGTl2jw=;
        b=X56Z96GHvrDgq/e+lgNdNls1VP7Bc74QmhsIYd4hadk43KJI22vpCYgVwq3ATSumOV
         rfnORaVO8SaB0t6bIwXc3/+AyP3TQ74fbDm4sR7rIx27mhiEmWU4W/MFZREh2rd1JQoC
         kEYe00WgpiDT8Mb5J9jVL/wtCZeTMe4e+xChz+tcj+4J/X966YpU//fDKeR87vBRUjzW
         bCsVVGeurrYDQqyUT8F6Rvdhxj2dfiWaOYiCfc9pdhjMmpFf9tWP9FfweHyMEJ7cGJEg
         xU9a5uX9Uyi5HSKh/T92XCJuimA7hOrOOUMxYV33wXuH+hh5K+CmUQJ7oGzjT6sQesDr
         LEgA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1748889699; x=1749494499;
        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=ICNtWJqhMu9+Zs8hdxO7BQriu5oU8Ra1McfQFGTl2jw=;
        b=dq59XyP2yqdnoL7jsOkLudZBnDb3AVlZxWeYc+ziwmC2Lu63J2P6mqVCLiVzyJvL0F
         2QHcemzFmjo93jz2IIWx5KF+3TWHPqYtsBuSquIc0uCKHWbIUecAGuofJQFT0Bs9Q2OB
         af+jEOGyOdXonmFPf0ND6azP2Dt7eAQTvwzcTVqzuab7yVF3tXfYTeHZEdxNAH4vWbVt
         IZDQUfFf7yoS5aOmdn4ZfFjPbJGkibRW5jLVKXd1eZhDMvWyQctsFM4bRJLBH8vRcSC5
         4H7ztXqTBrvN0tnC9zwcQZbN1LvLYTg6LwQhN2o5bBzIZSOvRJaO+FiOHWpSjjSmdB46
         NWdQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCXNQyCT6LHsZ/R5XMLZVg0hNRIS0nh610R4l51g4vX4iajPTmJOKGWIMlUawqkqyARgjvQthGg2WE9a@gnusha.org
X-Gm-Message-State: AOJu0YzmHeOoiwTkMe/4mzmnuBViLmgS2eD5ARZBkHomOd/snDm/nF3e
	RSEoGBnMNhkiSz33oilwBw/LxmMheI+1jIcSxs9zK+YyBOiK/ZB1mg3M
X-Google-Smtp-Source: AGHT+IHF4dKrTkdEyAmxGBmLv9AFAf5QPCY3rhEVwxgshUQKBzb6JB3Y0X8bFrnKLTKImJGMAJfrTg==
X-Received: by 2002:a05:6902:26c5:b0:e7d:585d:6aac with SMTP id 3f1490d57ef6-e7f82175d22mr17558618276.39.1748889699350;
        Mon, 02 Jun 2025 11:41:39 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZc0pNC0Fjt9PvuUw3VobucFf3MmjRbCxVph0OenMqhcUA==
Received: by 2002:a25:b288:0:b0:e7d:622d:9dd6 with SMTP id 3f1490d57ef6-e7f6f6a178fls4581972276.0.-pod-prod-06-us;
 Mon, 02 Jun 2025 11:41:34 -0700 (PDT)
X-Received: by 2002:a05:690c:6484:b0:70e:1771:c152 with SMTP id 00721157ae682-71057d23372mr197821967b3.30.1748889694165;
        Mon, 02 Jun 2025 11:41:34 -0700 (PDT)
Received: by 2002:a05:690c:6083:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-70f980e43fams7b3;
        Mon, 2 Jun 2025 10:38:12 -0700 (PDT)
X-Received: by 2002:a05:690c:23c5:b0:708:21e9:a20d with SMTP id 00721157ae682-71057c2aa92mr186204227b3.16.1748885891125;
        Mon, 02 Jun 2025 10:38:11 -0700 (PDT)
Date: Mon, 2 Jun 2025 10:38:10 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <402db6ba-2497-4aab-9f84-0d66b4b8efccn@googlegroups.com>
In-Reply-To: <CAFC_Vt6gqV-8aoTKt2it1p9LAnvaADueHnC1cM6LQojZf6fjCw@mail.gmail.com>
References: <cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com>
 <CAFC_Vt6gqV-8aoTKt2it1p9LAnvaADueHnC1cM6LQojZf6fjCw@mail.gmail.com>
Subject: Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a
 soft fork
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_16006_1455971590.1748885890774"
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_16006_1455971590.1748885890774
Content-Type: multipart/alternative; 
	boundary="----=_Part_16007_1687758839.1748885890774"

------=_Part_16007_1687758839.1748885890774
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Boris, list,

> In my scheme, a user creates a QR output that=20
commits to a hash of a pubkey inside a Taproot leaf. This commitment=20
is hidden until revealed at spend time. Later, when the user wants to=20
spend a legacy EC output, they must spend this QR output in the same=20
transaction, and it must be at least X blocks old.=20

There's some nuances here that seem quite interesting. If an output commits=
=20
(in a quantum-resistant way, i.e. hashing let's say) only to a pubkey, and=
=20
not a pubkey plus spending-transaction, then, in the general case, that has=
=20
the weakness that the commitment can be replicated, in another commitment=
=20
tx, at the time of insertion of commitment into the blockchain; so that if=
=20
the tiebreaker is "first commitment in the block(chain)" an attacker can=20
mess with you. In your case you refer to "a QR output that commits to the=
=20
hash of a pubkey inside a taproot leaf" but I'm finding it a tiny bit=20
unclear what you mean there. Taproot itself isn't quantum resistant (QR),=
=20
so Q =3D P + H(P,S)G is not QR even if P is NUMS. Whereas you might mean:=
=20
that same system but with keypath spending invalidated, so it's QR because=
=20
of the hash function, but also, the tapleaf contains a QR or PQC signing=20
scheme in it (I guess this is what you actually mean). Or, you might mean=
=20
something that is structurally the same as taproot but not using=20
secp/BIP340, but instead a PQC scheme with a homomorphism so that that same=
=20
design can be reused; call that "taproot2" .. though I don't think I've=20
heard people talking about that.

Then there's what I think you focus on: the commitment is hidden. To other=
=20
readers, in case of confusion: I believe the *real* point here is not=20
"nobody knows you committed something" though that may be practically=20
significant, it's instead "nobody knows the exact commitment value (hash)=
=20
you used".

So, I believe that's a correct/valid point that actually *doesn't* depend=
=20
on which "version" of taproot as per above. Focusing on=20
current-taproot-but-script-path-only-with-QR-in-tapleaf:  we have a=20
protection that the quantum attacker cannot find the S in the (P,S) tuple=
=20
(indeed, they cannot even know the H in P + H(P,S)G). This commitment is=20
*not* literally perfectly hiding as in a properly formed Pedersen=20
commitment ([1]) but I do think you have the normal preimage resistance=20
against revelation as expected even in post-quantum. So that prevents the=
=20
"copy the commitment" problem I started out by mentioning. [2]

If "taproot2" instead then we have something for which even the keypath=20
isn't crackable so I guess it's obvious.

> Since the commitment doesn't include a txid, the user can precommit to=20
the pubkey hash far in advance, before knowing the details of the=20
eventual transaction.

Again, I believe you're right here, but we should try to unpack what's=20
different; because the "reveal" step of commit-reveal is accompanied by the=
=20
QR signing event of the pre-existing QR output, we have a sane security=20
model, so there's no need to commit to the transaction in the preliminary=
=20
step, as far as I can tell.

> More efficient use of block space

Makes sense.

I think the only downside I see here is that the initial commitment step=20
requires the PQC scheme to actually exist. That may not seem like a big=20
deal, but I have a suspicion it actually will be. I think a protocol in=20
which we just rely on existing hash primitives and put off the PQC scheme=
=20
choosing event may be necessary .. though I could be for sure wrong, in=20
more than one way, in saying that.

Apart from that point I think this scheme seems good (as you mention, it=20
has the virtue of not requiring new databases etc which is pretty huge).

Cheers,
AdamISZ/waxwing

[1]  In these analyses, I think it's common to overlook a potentially=20
crucial point: the utxo set is enumerable in practical time, so we must=20
always remember that we can check our calculations against existing=20
addresses, even if they are hash-covered keys.

[2] The only caveat is if you're considering the possibility of the=20
attacker knowing the key in advance of even the commitment step; generally,=
=20
that's "game over", but i know that there is some attempt to analyze that=
=20
case in some places, too. Not here.

On Wednesday, May 28, 2025 at 6:54:21=E2=80=AFPM UTC-3 Nagaev Boris wrote:

> Hi Tadge,
>
> Thanks for writing this up! The proposal is very thoughtful, and it's
> great to see concrete work on post-quantum commit/reveal schemes.
>
> I've been exploring a related approach based on a similar
> commit/reveal idea. In my scheme, a user creates a QR output that
> commits to a hash of a pubkey inside a Taproot leaf. This commitment
> is hidden until revealed at spend time. Later, when the user wants to
> spend a legacy EC output, they must spend this QR output in the same
> transaction, and it must be at least X blocks old.
>
> https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ
>
> This approach has a few potential advantages:
>
> 1. No need for nodes to track a new commitment store
>
> Because the commitment remains hidden in a Tapleaf until the spend,
> observers (including attackers) don't see it, and nodes don't need to
> store or validate any external commitment set. The only requirement is
> that the QR output must be old enough, and Bitcoin Core already tracks
> coin age, which is needed to validate existing consensus rules.
>
> 2. Commitment can be made before the transaction is known
>
> Since the commitment doesn't include a txid, the user can precommit to
> the pubkey hash far in advance, before knowing the details of the
> eventual transaction. This allows greater flexibility: you can delay
> choosing outputs, fee rates, etc., until spend time. Only knowledge of
> the EC pubkey needs to be proven when creating the QR output.
>
> 3. More efficient use of block space
>
> Multiple EC coins can be spent together with a single QR output,
> holding EC pubkey commitments in Taproot leaves. If EC coins share the
> same EC pubkey (e.g., come from the same address), they can reuse the
> same commitment.
>
> Would love to hear your thoughts on this variant. I think this one
> might be a simpler, lower-overhead option for protecting EC outputs
> post-QC.
>
> Best,
> Boris
>
> On Wed, May 28, 2025 at 2:28=E2=80=AFPM Tadge Dryja <r...@awsomnet.org> w=
rote:
> >
> > One of the tricky things about securing Bitcoin against quantum=20
> computers is: do you even need to? Maybe quantum computers that can break=
=20
> secp256k1 keys will never exist, in which case we shouldn't waste our tim=
e.=20
> Or maybe they will exist, in not too many years, and we should spend the=
=20
> effort to secure the system against QCs.
> >
> > Since people disagree on how likely QCs are to arrive, and what the=20
> timing would be if they do, it's hard to get consensus on changes to=20
> bitcoin that disrupt the properties we use today. For example, a soft for=
k=20
> introducing a post-quantum (PQ) signature scheme and at the same time=20
> disallowing new secp256k1 based outputs would be great for strengthening=
=20
> Bitcoin against an oncoming QC. But it would be awful if a QC never=20
> 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=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 h=
ow=20
> it can be implemented in bitcoin nodes as a soft fork.
> >
> > This scheme only works for keys that are pubkey hashes (or script=20
> hashes) with pubkeys that are unknown to the network. It works with tapro=
ot=20
> as well, but there must be some script-path in the taproot key, as keypat=
h=20
> spends would no longer be secure.
> >
> > 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. We=
=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 outpu=
t=20
> types and should work about the same way (with caveats about multisig). T=
he=20
> equivalent for taproot outputs would be an inner key proving a script pat=
h.
> >
> > ## A simple scheme to show an attack
> >
> > The simplest commit/reveal scheme would be one where after activation,=
=20
> for any transaction with an EC signature in it, that transaction's txid=
=20
> must appear in a earlier transaction's OP_RETURN output.
> >
> > When a user wants to spend their coins, they first sign a transaction a=
s=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 matches=
 a=20
> previously seen commitment, and allow the transaction.
> >
> > One problem with this scheme is that upon seeing the full transaction,=
=20
> the attacker can compute the user's private key, and create a new=20
> commitment with a different txid for a transaction where the attacker get=
s=20
> all the coins. If the attacker can get their commitment and spending=20
> 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=
=20
> consensus. A minimum delay of 100 blocks would mean that the attacker wou=
ld=20
> have to prevent the user's transaction from being confirmed for 100 block=
s=20
> after it showed up in the attacker's mempool. The tradeoff is that longer=
=20
> periods give better safety at the cost of more delay in spending.
> >
> > This scheme, while problematic, is better than nothing! But it's=20
> 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 bein=
g=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 confirme=
d=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 introduce=
s=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 th=
e=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=20
> bitcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in=
=20
> bitcoin terms, HASH160(pubkey). Due to the hash functions being different=
,=20
> A =3D HASH160(pubkey) and B =3D h(pubkey) will be completely different, a=
nd=20
> nobody should be able to determine if A and B are hashes of the same pubk=
ey=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=20
> which will be signed for, a proof of knowledge of the pubkey which commit=
s=20
> to a transaction, and an the txid of the spending transaction. We'll call=
=20
> these "address ID" (AID), sequence dependent proof (SDP), and the=20
> commitment txid (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.
> >
> > 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 use=
r=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 distingui=
sh=20
> which commitments are valid, which are invalid, and which is the first se=
en=20
> valid commitment. Given the pubkey, nodes can determine commitments to be=
=20
> 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, a=
nd=20
> may be able to create a transaction and txid that could work. But they=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=20
> mempool, but before it can be confirmed, the attacker gets C3 confirmed. =
C3=20
> is a 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 th=
ey=20
> will also be able to determine that C2 is a valid commitment (since pubke=
y=20
> is revealed in tx3) which came prior to C3, making C2 the only valid=20
> commitment for that AID.
> >
> >
> > ## Implementation
> >
> > Nodes would keep a new key/value store, similar to the existing UTXO=20
> set. The indexing key would be the AID, and the value would be the set of=
=20
> all (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, t=
he=20
> transaction is dropped. If the AID does match, the node can now "clean ou=
t"=20
> an AID entry, eliminating all but the first valid commitment, and marking=
=20
> that AID as final. If the txid seen matches the remaining commitment, the=
=20
> transaction is valid; if not, the transaction is dropped.
> >
> > After the transaction is confirmed the AID entry can be deleted.=20
> Deleting the entries frees up space, and would allow another round to=20
> happen with the same pubkey, which would lead to theft. Retaining the=20
> entries takes up more space on nodes that can't be pruned, and causes=20
> pubkey reuse to destroy coins rather than allow them to be stolen. That's=
 a=20
> tradeoff, and I personally guess it's probably not worth retaining that=
=20
> 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=
=20
> 3 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=20
> satisfy this script, the spending transaction needs to provide 2 data=20
> elements: a signature, and some data that when hashed results in a pubkey=
=20
> for which that signature is valid. If such a pair of data elements exists=
,=20
> it means that either SHA256 preimage resistance is broken (which we're=20
> assuming isn't the case) or someone can create valid signatures for=20
> arbitrary elliptic curve points, ie a cryptographically relevant quantum=
=20
> computer (or any other process which breaks the security of secp256k1=20
> 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 a=
re=20
> not aware of the commitment requirement will still accept all transaction=
s=20
> with the new rules.
> >
> > Wallets not aware of the new rules, however, are very dangerous, as the=
y=20
> may try to broadcast signed transactions without any commitment. Nodes th=
at=20
> see such a transaction should drop the tx, and if possible tell the walle=
t=20
> that they are doing something which is now very dangerous! On the open p2=
p=20
> network this is not really enforceable, but people submitting transaction=
s=20
> 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=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 seem=
s=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 t=
o=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 identica=
l=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 n=
ot=20
> 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 wil=
l=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=
=20
> N. Possibly a more complex commit / reveal scheme could deal with multipl=
e=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 --=
=20
> you can send to p2wpkh and do the whole commit/reveal process again when=
=20
> you want to spend. This could be helpful if PQ signature schemes are stil=
l=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 tha=
t=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 wit=
h=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 somethi=
ng=20
> like this could be soft forked with a PoQC activation trigger, so that if=
 a=20
> QC never shows up, none of this code gets executed. And people who take a=
=20
> couple easy steps like not reusing addresses (which they should anyway fo=
r=20
> privacy reasons) don't have to worry about their coins.
> >
> > Some of these ideas may have been posted before; I know of the Fawkscoi=
n=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 ho=
w=20
> 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=
=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=
=20
> be a good idea.
> >
> > -Tadge
> >
> > --
> > You received this message because you are subscribed to the Google=20
> Groups "Bitcoin Development Mailing List" group.
> > To unsubscribe from this group and stop receiving emails from it, send=
=20
> an email to bitcoindev+...@googlegroups.com.
> > To view this discussion visit=20
> https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f92=
6f9ba627n%40googlegroups.com
> .
>
>
>
> --=20
> Best regards,
> Boris Nagaev
>

--=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/=
402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com.

------=_Part_16007_1687758839.1748885890774
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>Hi Boris, list,</div><div><br /></div><div>&gt; In my scheme, a user c=
reates a QR output that
<br />commits to a hash of a pubkey inside a Taproot leaf. This commitment
<br />is hidden until revealed at spend time. Later, when the user wants to
<br />spend a legacy EC output, they must spend this QR output in the same
<br />transaction, and it must be at least X blocks old. <br /></div><div><=
br /></div><div>There's some nuances here that seem quite interesting. If a=
n output commits (in a quantum-resistant way, i.e. hashing let's say) only =
to a pubkey, and not a pubkey plus spending-transaction, then, in the gener=
al case, that has the weakness that the commitment can be replicated, in an=
other commitment tx, at the time of insertion of commitment into the blockc=
hain; so that if the tiebreaker is "first commitment in the block(chain)" a=
n attacker can mess with you. In your case you refer to "a QR output that c=
ommits to the hash of a pubkey inside a taproot leaf" but I'm finding it a =
tiny bit unclear what you mean there. Taproot itself isn't quantum resistan=
t (QR), so Q =3D P + H(P,S)G is not QR even if P is NUMS. Whereas you might=
 mean: that same system but with keypath spending invalidated, so it's QR b=
ecause of the hash function, but also, the tapleaf contains a QR or PQC sig=
ning scheme in it (I guess this is what you actually mean). Or, you might m=
ean something that is structurally the same as taproot but not using secp/B=
IP340, but instead a PQC scheme with a homomorphism so that that same desig=
n can be reused; call that "taproot2" .. though I don't think I've heard pe=
ople talking about that.</div><div><br /></div><div>Then there's what I thi=
nk you focus on: the commitment is hidden. To other readers, in case of con=
fusion: I believe the *real* point here is not "nobody knows you committed =
something" though that may be practically significant, it's instead "nobody=
 knows the exact commitment value (hash) you used".</div><div><br /></div><=
div>So, I believe that's a correct/valid point that actually *doesn't* depe=
nd on which "version" of taproot as per above. Focusing on current-taproot-=
but-script-path-only-with-QR-in-tapleaf:=C2=A0 we have a protection that th=
e quantum attacker cannot find the S in the (P,S) tuple (indeed, they canno=
t even know the H in P + H(P,S)G). This commitment is *not* literally perfe=
ctly hiding as in a properly formed Pedersen commitment ([1]) but I do thin=
k you have the normal preimage resistance against revelation as expected ev=
en in post-quantum. So that prevents the "copy the commitment" problem I st=
arted out by mentioning. [2]</div><div><br /></div><div>If "taproot2" inste=
ad then we have something for which even the keypath isn't crackable so I g=
uess it's obvious.</div><div><br /></div><div>&gt; Since the commitment doe=
sn't include a txid, the user can precommit to
<br />the pubkey hash far in advance, before knowing the details of the
<br />eventual transaction.</div><div><br /></div><div>Again, I believe you=
're right here, but we should try to unpack what's different; because the "=
reveal" step of commit-reveal is accompanied by the QR signing event of the=
 pre-existing QR output, we have a sane security model, so there's no need =
to commit to the transaction in the preliminary step, as far as I can tell.=
</div><div><br /></div><div>&gt; More efficient use of block space</div><di=
v><br /></div><div>Makes sense.</div><div><br /></div><div>I think the only=
 downside I see here is that the initial commitment step requires the PQC s=
cheme to actually exist. That may not seem like a big deal, but I have a su=
spicion it actually will be. I think a protocol in which we just rely on ex=
isting hash primitives and put off the PQC scheme choosing event may be nec=
essary .. though I could be for sure wrong, in more than one way, in saying=
 that.</div><div><br /></div><div>Apart from that point I think this scheme=
 seems good (as you mention, it has the virtue of not requiring new databas=
es etc which is pretty huge).</div><div><br /></div><div>Cheers,</div><div>=
AdamISZ/waxwing</div><div><br /></div><div>[1]=C2=A0 In these analyses, I t=
hink it's common to overlook a
 potentially crucial point: the utxo set is enumerable in practical=20
time, so we must always remember that we can check our calculations=20
against existing addresses, even if they are hash-covered keys.</div><div><=
br /></div><div>[2] The only caveat is if you're considering the possibilit=
y of the attacker knowing the key in advance of even the commitment step; g=
enerally, that's "game over", but i know that there is some attempt to anal=
yze that case in some places, too. Not here.</div><div><br /></div><div cla=
ss=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On Wednesday, May=
 28, 2025 at 6:54:21=E2=80=AFPM UTC-3 Nagaev Boris wrote:<br/></div><blockq=
uote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px s=
olid rgb(204, 204, 204); padding-left: 1ex;">Hi Tadge,
<br>
<br>Thanks for writing this up! The proposal is very thoughtful, and it&#39=
;s
<br>great to see concrete work on post-quantum commit/reveal schemes.
<br>
<br>I&#39;ve been exploring a related approach based on a similar
<br>commit/reveal idea. In my scheme, a user creates a QR output that
<br>commits to a hash of a pubkey inside a Taproot leaf. This commitment
<br>is hidden until revealed at spend time. Later, when the user wants to
<br>spend a legacy EC output, they must spend this QR output in the same
<br>transaction, and it must be at least X blocks old.
<br>
<br><a href=3D"https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHg=
Iq_AAAJ" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https:/=
/www.google.com/url?hl=3Den&amp;q=3Dhttps://groups.google.com/g/bitcoindev/=
c/jr1QO95k6Uc/m/lsRHgIq_AAAJ&amp;source=3Dgmail&amp;ust=3D1748966593109000&=
amp;usg=3DAOvVaw0ZNyyXjgrUO01GIKdTv18H">https://groups.google.com/g/bitcoin=
dev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ</a>
<br>
<br>This approach has a few potential advantages:
<br>
<br>1. No need for nodes to track a new commitment store
<br>
<br>Because the commitment remains hidden in a Tapleaf until the spend,
<br>observers (including attackers) don&#39;t see it, and nodes don&#39;t n=
eed to
<br>store or validate any external commitment set. The only requirement is
<br>that the QR output must be old enough, and Bitcoin Core already tracks
<br>coin age, which is needed to validate existing consensus rules.
<br>
<br>2. Commitment can be made before the transaction is known
<br>
<br>Since the commitment doesn&#39;t include a txid, the user can precommit=
 to
<br>the pubkey hash far in advance, before knowing the details of the
<br>eventual transaction. This allows greater flexibility: you can delay
<br>choosing outputs, fee rates, etc., until spend time. Only knowledge of
<br>the EC pubkey needs to be proven when creating the QR output.
<br>
<br>3. More efficient use of block space
<br>
<br>Multiple EC coins can be spent together with a single QR output,
<br>holding EC pubkey commitments in Taproot leaves. If EC coins share the
<br>same EC pubkey (e.g., come from the same address), they can reuse the
<br>same commitment.
<br>
<br>Would love to hear your thoughts on this variant. I think this one
<br>might be a simpler, lower-overhead option for protecting EC outputs
<br>post-QC.
<br>
<br>Best,
<br>Boris
<br>
<br>On Wed, May 28, 2025 at 2:28=E2=80=AFPM Tadge Dryja &lt;<a href data-em=
ail-masked rel=3D"nofollow">r...@awsomnet.org</a>&gt; wrote:
<br>&gt;
<br>&gt; One of the tricky things about securing Bitcoin against quantum co=
mputers is: do you even need to?  Maybe quantum computers that can break se=
cp256k1 keys will never exist, in which case we shouldn&#39;t waste our tim=
e.  Or maybe they will exist, in not too many years, and we should spend th=
e effort to secure the system against QCs.
<br>&gt;
<br>&gt; Since people disagree on how likely QCs are to arrive, and what th=
e timing would be if they do, it&#39;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 disa=
llowing new secp256k1 based outputs would be great for strengthening Bitcoi=
n 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.
<br>&gt;
<br>&gt; So it would be nice to have a way to not deal with this issue unti=
l *after* the QC shows up.  With commit / reveal schemes Bitcoin can keep w=
orking after a QC shows up, even if we haven&#39;t defined a PQ signature s=
cheme and everyone&#39;s still got P2WPKH outputs.
<br>&gt;
<br>&gt; Most of this is similar to Tim Ruffing&#39;s proposal from a few y=
ears ago here:
<br>&gt; <a href=3D"https://gnusha.org/pi/bitcoindev/1518710367.3550.111.ca=
mel@mmci.uni-saarland.de/" target=3D"_blank" rel=3D"nofollow" data-saferedi=
recturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://gnusha.org/pi=
/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/&amp;source=3Dgm=
ail&amp;ust=3D1748966593109000&amp;usg=3DAOvVaw2mXKQz1h_qf2WMPJQACV42">http=
s://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.de/</a>
<br>&gt;
<br>&gt; The main difference is that this scheme doesn&#39;t use encryption=
, but a smaller hash-based commitment, and describes activation as a soft f=
ork.  I&#39;ll define the two types of attacks, a commitment scheme, and th=
en say how it can be implemented in bitcoin nodes as a soft fork.
<br>&gt;
<br>&gt; This scheme only works for keys that are pubkey hashes (or script =
hashes) with pubkeys that are unknown to the network.  It 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.
<br>&gt;
<br>&gt; What to do with all the keys that are known is another issue and i=
ndependent of the scheme in this post (it&#39;s compatible with both burnin=
g them and leaving them to be stolen)
<br>&gt;
<br>&gt; For these schemes, we assume there is an attacker with a QC that c=
an 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 blo=
cks in a row with the transactions they want.
<br>&gt;
<br>&gt; &quot;Pubkey&quot; can also be substituted with &quot;script&quot;=
 for P2SH and P2WSH output types and should work about the same way (with c=
aveats about multisig).  The equivalent for taproot outputs would be an inn=
er key proving a script path.
<br>&gt;
<br>&gt; ## A simple scheme to show an attack
<br>&gt;
<br>&gt; The simplest commit/reveal scheme would be one where after activat=
ion, for any transaction with an EC signature in it, that transaction&#39;s=
 txid must appear in a earlier transaction&#39;s OP_RETURN output.
<br>&gt;
<br>&gt; When a user wants to spend their coins, they first sign a transact=
ion as they would normally, compute the txid, get that txid into an OP_RETU=
RN output somehow (paying a miner out of band, etc), then after waiting a w=
hile, broadcast the transaction.  Nodes would check that the txid matches a=
 previously seen commitment, and allow the transaction.
<br>&gt;
<br>&gt; One problem with this scheme is that upon seeing the full transact=
ion, the attacker can compute the user&#39;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 trans=
action in before the user&#39;s transaction, they can steal the coins.
<br>&gt;
<br>&gt; 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&#39;s transaction from being confirmed for 1=
00 blocks after it showed up in the attacker&#39;s mempool.  The tradeoff i=
s that longer periods give better safety at the cost of more delay in spend=
ing.
<br>&gt;
<br>&gt; This scheme, while problematic, is better than nothing!  But it&#3=
9;s possible to remove this timing tradeoff.
<br>&gt;
<br>&gt;
<br>&gt; ## A slightly more complex scheme with (worse) problems
<br>&gt;
<br>&gt; 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 &quot=
;first seen&quot; consensus rule.  Only the first commitment pointing to an=
 outpoint works.
<br>&gt;
<br>&gt; So if nodes see two OP_RETURN commitments in their sequence of con=
firmed transactions:
<br>&gt;
<br>&gt; C1 =3D outpoint1, txid1
<br>&gt; C2 =3D outpoint1, txid2
<br>&gt;
<br>&gt; They can ignore C2; C1 has already laid claim to outpoint1, and th=
e transaction identified by txid1 is the only transaction that can spend ou=
tpoint1.
<br>&gt;
<br>&gt; 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.
<br>&gt;
<br>&gt; We want to retain the &quot;first seen&quot; 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 descri=
bed 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.
<br>&gt;
<br>&gt;
<br>&gt; The actual commitment scheme
<br>&gt;
<br>&gt;
<br>&gt; We define some hash function h().  We&#39;ll use SHA256 for the ha=
shing, but it needs to be keyed with some tag, for example &quot;Alas poor =
Koblitz curve, we knew it well&quot;.
<br>&gt;
<br>&gt; 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 b=
itcoin terms, HASH160(pubkey).  Due to the hash functions 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 are hashes of the same pubke=
y without knowing pubkey itself.
<br>&gt;
<br>&gt; An efficient commitment is:
<br>&gt;
<br>&gt; C =3D  h(pubkey), h(pubkey, txid), txid
<br>&gt; (to label things: C =3D AID, SDP, CTXID)
<br>&gt;
<br>&gt; This commitment includes 3 elements: a different hash of the pubke=
y which will be signed for, a proof of knowledge of the pubkey which commit=
s to a transaction, and an the txid of the spending transaction.  We&#39;ll=
 call these &quot;address ID&quot; (AID), sequence dependent proof (SDP), a=
nd the commitment txid (CTXID).
<br>&gt;
<br>&gt; For those familiar with the proposal by Ruffing, the SDP has a sim=
ilar function to the authenticated encryption part of the encrypted commitm=
ent.  Instead of using authenticated encryption, we can instead just use an=
 HMAC-style authentication alone, since the other data, the CTXID, is provi=
ded.
<br>&gt;
<br>&gt; When the user&#39;s wallet creates a transaction, they can feed th=
at transaction into a commitment generator function which takes in a transa=
ction, extracts the pubkey from the tx, computes the 3 hashes, and returns =
the 3-hash commitment.  Once this commitment is confirmed, the user broadca=
sts the transaction.
<br>&gt;
<br>&gt; Nodes verify the commitment by using the same commitment generator=
 function and checking if it matches the first valid commitment for that AI=
D, in which case the tx is confirmed.
<br>&gt;
<br>&gt; If a node sees multiple commitments all claiming the same AID, it =
must store all of them.  Once the AID&#39;s pubkey is known, the node can d=
istinguish which commitments are valid, which are invalid, and which is the=
 first seen valid commitment.  Given the pubkey, nodes can determine commit=
ments to be invalid by checking if SDP =3D h(pubkey, CTXID).
<br>&gt;
<br>&gt; As an example, consider a sequence of 3 commitments:
<br>&gt;
<br>&gt; C1 =3D h(pubkey), h(pubkey&#39;, txid1), txid1
<br>&gt; C2 =3D h(pubkey), h(pubkey, txid2), txid2
<br>&gt; C3 =3D h(pubkey), h(pubkey, txid3), txid3
<br>&gt;
<br>&gt; The user first creates tx2 and tries to commit C2.  But an attacke=
r 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&#39;t know the pubkey, so while they can copy the AID hash, they have =
to make something up for the SDP.
<br>&gt;
<br>&gt; 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.  C=
3 is a valid commitment made with knowledge of the pubkey.
<br>&gt;
<br>&gt; Nodes can reject transactions tx1 and tx3.  For tx1, they will see=
 that the SDP doesn&#39;t match the data in the transaction, so it&#39;s an=
 invalid commitment.  For tx3, they will see that it is valid, but by seein=
g tx3 they will also be able to determine that C2 is a valid commitment (si=
nce pubkey is revealed in tx3) which came prior to C3, making C2 the only v=
alid commitment for that AID.
<br>&gt;
<br>&gt;
<br>&gt; ## Implementation
<br>&gt;
<br>&gt; Nodes would keep a new key/value store, similar to the existing UT=
XO 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 commitmen=
t is seen in an OP_RETURN, nodes store the commitment.
<br>&gt;
<br>&gt; When a transaction is seen, nodes observe the pubkey used in the t=
ransaction, 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 &quot;cle=
an out&quot; an AID entry, eliminating all but the first valid commitment, =
and marking that AID as final.  If the txid seen matches the remaining comm=
itment, the transaction is valid; if not, the transaction is dropped.
<br>&gt;
<br>&gt; After the transaction is confirmed the AID entry can be deleted.  =
Deleting the entries frees up space, and would allow another round to happe=
n with the same pubkey, which would lead to theft.  Retaining the entries t=
akes up more space on nodes that can&#39;t be pruned, and causes pubkey reu=
se to destroy coins rather than allow them to be stolen.  That&#39;s a trad=
eoff, and I personally guess it&#39;s probably not worth retaining that dat=
a but don&#39;t have a strong opinion either way.
<br>&gt;
<br>&gt; Short commitments:
<br>&gt;
<br>&gt; Since we&#39;re not trying to defend against collision attacks, I =
think all 3 hashes can be truncated to 16 bytes.  The whole commitment coul=
d be 48 bytes long.  Without truncation the commitments would be 96 bytes.
<br>&gt;
<br>&gt;
<br>&gt; ## Activation
<br>&gt;
<br>&gt; The activation for the commit/reveal requirement can be triggered =
by a proof of quantum computer (PoQC).
<br>&gt;
<br>&gt; A transaction which successfully spends an output using tapscript:
<br>&gt;
<br>&gt; OP_SHA256 OP_CHECKSIG
<br>&gt;
<br>&gt; 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 elem=
ents: a signature, and some data that when hashed results in a pubkey for w=
hich that signature is valid.  If such a pair of data elements exists, it m=
eans that either SHA256 preimage resistance is broken (which we&#39;re assu=
ming isn&#39;t the case) or someone can create valid signatures for arbitra=
ry elliptic curve points, ie a cryptographically relevant quantum computer =
(or any other process which breaks the security of secp256k1 signatures)
<br>&gt;
<br>&gt; 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 require=
ment is that some OP_RETURN outputs show up earlier.  Nodes which are not a=
ware of the commitment requirement will still accept all transactions with =
the new rules.
<br>&gt;
<br>&gt; Wallets not aware of the new rules, however, are very dangerous, a=
s they may try to broadcast signed transactions without any commitment.  No=
des that see such a transaction should drop the tx, and if possible tell th=
e wallet that they are doing something which is now very dangerous!  On the=
 open p2p network this is not really enforceable, but people submitting tra=
nsactions to their own node (eg via RPC) can at least get a scary error mes=
sage.
<br>&gt;
<br>&gt;
<br>&gt; ## Issues
<br>&gt;
<br>&gt; My hope is that this scheme would give some peace of mind to peopl=
e holding bitcoin, that in the face of a sudden QC, even with minimal prepa=
ration 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 cha=
nges: Don&#39;t reuse addresses, and if you have taproot outputs, include s=
ome kind of script path in the outer key.
<br>&gt;
<br>&gt; There are still a number of problems, though!
<br>&gt;
<br>&gt; - 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&#39;s up to the user h=
ow long they wait between confirming the commitment and revealing the trans=
action.
<br>&gt;
<br>&gt; - How to get op_returns in
<br>&gt; If there are no PQ signature schemes activated in bitcoin when thi=
s activates, there&#39;s only one type of transaction that can reliably get=
 the OP_RETURN outputs confirmed: coinbase transactions.  Getting commitmen=
ts 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&#39;t need to directl=
y contact miners: anyone could aggregate commitments, create a large transa=
ction with many OP_RETURN outputs, and then get a miner to commit to that p=
arent transaction.  Users don&#39;t need to worry about committing twice as=
 identical commitments would be a no op.
<br>&gt;
<br>&gt; - Spam
<br>&gt; Anyone can make lots of OP_RETURN commitments which are just rando=
m numbers, forcing nodes to store these commitments in a database.  That&#3=
9;s not great, but isn&#39;t much different from how bitcoin works today.  =
If it&#39;s really a problem, nodes could requiring the commitment outputs =
to have a non-0 amount of bitcoin, imposing a higher cost for the commitmen=
ts than other OP_RETURN outputs.
<br>&gt;
<br>&gt; - Multiple inputs
<br>&gt; If users have received more than one UTXO to the same address, the=
y will need to spend all the UTXOs at once.  The commitment scheme can deal=
 with only the first pubkey seen in the serialized transaction.
<br>&gt;
<br>&gt; - Multisig and Lightning Network
<br>&gt; If your multisig counterparties have a QC, multisig outputs become=
 1 of N.  Possibly a more complex commit / reveal scheme could deal with mu=
ltiple keys, but the keys would all have to be hashed with counterparties n=
ot knowing each others&#39; unhashed pubkeys.  This isn&#39;t how existing =
multisig outputs work, and in fact the current trend is the opposite with t=
hings like Musig2, FROST and ROAST.  If we&#39;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.
<br>&gt;
<br>&gt; - Making more p2wpkhs
<br>&gt; You don&#39;t have to send to a PQ address type with these transac=
tions -- you can send to p2wpkh and do the whole commit/reveal process agai=
n when you want to spend.  This could be helpful if PQ signature schemes ar=
e 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&#39;s pos=
sible that in such a scenario a few high-cost PQ transactions commit to man=
y 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 wi=
th the same 3-hash commitment requirement to enable this.
<br>&gt;
<br>&gt; ## Conclusion
<br>&gt;
<br>&gt; This PQ commit / reveal scheme has similar properties to Tim Ruffi=
ng&#39;s, with a smaller commitment that can be done as a soft fork.  I hop=
e 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 peopl=
e who take a couple easy steps like not reusing addresses (which they shoul=
d anyway for privacy reasons) don&#39;t have to worry about their coins.
<br>&gt;
<br>&gt; Some of these ideas may have been posted before; I know of the Faw=
kscoin paper (<a href=3D"https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf" =
target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.goog=
le.com/url?hl=3Den&amp;q=3Dhttps://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf=
&amp;source=3Dgmail&amp;ust=3D1748966593110000&amp;usg=3DAOvVaw0uAIxjr6YlDh=
pVssHOh23F">https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf</a>) and the r=
ecent discussion which linked to Ruffing&#39;s proposal.  Here I&#39;ve tri=
ed to show how it could be done in a soft fork which doesn&#39;t look too b=
ad to implement.
<br>&gt;
<br>&gt; I&#39;ve also heard of some more complex schemes involving zero kn=
owledge proofs, proving things like BIP32 derivations, but I think this giv=
es some pretty good properties without needing anything other than good old=
 SHA256.
<br>&gt;
<br>&gt; Hope this is useful &amp; wonder if people think something like th=
is would be a good idea.
<br>&gt;
<br>&gt; -Tadge
<br>&gt;
<br>&gt; --
<br>&gt; You received this message because you are subscribed to the Google=
 Groups &quot;Bitcoin Development Mailing List&quot; group.
<br>&gt; To unsubscribe from this group and stop receiving emails from it, =
send an email to <a href data-email-masked rel=3D"nofollow">bitcoindev+...@=
googlegroups.com</a>.
<br>&gt; To view this discussion visit <a href=3D"https://groups.google.com=
/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.co=
m" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.g=
oogle.com/url?hl=3Den&amp;q=3Dhttps://groups.google.com/d/msgid/bitcoindev/=
cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%2540googlegroups.com&amp;source=3Dgma=
il&amp;ust=3D1748966593110000&amp;usg=3DAOvVaw3rtp73twsSwlRwMxPoyGS4">https=
://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba62=
7n%40googlegroups.com</a>.
<br>
<br>
<br>
<br>--=20
<br>Best regards,
<br>Boris Nagaev
<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/402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/402db6ba-2497-4aab-9f84-0d66b4b8efccn%40googlegroups.com</a>.<br />

------=_Part_16007_1687758839.1748885890774--

------=_Part_16006_1455971590.1748885890774--