path: root/fb/e76f7927f8089024e7e65d20a3c6b5604f1c6e

Delivery-date: Wed, 28 May 2025 14:54:29 -0700
Received: from mail-qv1-f57.google.com ([209.85.219.57])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBCYMD7OS6ECBBCMM33AQMGQEKZ3HXWY@googlegroups.com>)
	id 1uKOjD-0001aE-GY
	for bitcoindev@gnusha.org; Wed, 28 May 2025 14:54:29 -0700
Received: by mail-qv1-f57.google.com with SMTP id 6a1803df08f44-6eeb5e86c5fsf4172846d6.1
        for <bitcoindev@gnusha.org>; Wed, 28 May 2025 14:54:27 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1748469261; cv=pass;
        d=google.com; s=arc-20240605;
        b=D/yKfzb9AQXPY98qO4PEIoawvp8wUHuUXzxzj/Ujm2qCfBxnb0mZLcJ/J5VCBhiKPq
         jpdRNc+wOl6qA5Mm2znftF0U1xwEc1aC4p3fDpZZIUfV8iENatz33J4sDf5mGlvBMqqE
         ISoZ1sIt3uqYOt6ODi2MCpVTBRE2pPrv4OiSqh4gUPOejqsNyjeRYI5CKnVp1Meu08B1
         DYKE83i2NZ7jYU4QrDH/Bol80HkvATEdD+6h01VH27yYEY+y3M2pnHIXA7mdviyXoZov
         yUyO63o9jM/7g9ynPMzUFmWAcslxPy2eZnN8cIkTp1MrJ1fQb71+mVE8Q6xAxVwQmW1c
         jIWA==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:content-transfer-encoding:cc:to
         :subject:message-id:date:from:in-reply-to:references:mime-version
         :sender:dkim-signature:dkim-signature;
        bh=5lmsUarp3HMYFDk3Hi66Jm8mZ2/zMthGp3T2Ep47ReE=;
        fh=10zPvtAyhPzcWdSJH2RA9P9etUw4dYp3Y9dVdNJ0oyI=;
        b=agYW5u6CAWNDKi8lL6NkyxK+8tLLNxrMSbr0kPBLflXv2IpE62scBa88BeVuAhSEQZ
         VXa3w0a4jbLE+00zNwd5usxXIYFomA7Fe0QsEPgPpUrXEn0e5HiSc0rui7fTMUz1Ibkx
         DFnVp6nUOdFgmiQSdzQyUf6rHwDsKqgeYtDq+iIIPGUvF1cOGCzlvFICyEYLDWZ5kyZX
         HxvTjO/cgHlGaFiUnwpPGx5lWi5So/vEpQbhpvBRbRuO5HXfHWo5bSagvQSoLEH8vZTZ
         49kQg/RO7fXay4pvz/0YTDPNi6E0vXsFBozzXrJ/d5dlKttt+1f6okwkFKI5fobiLJrT
         Kvew==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=miMM8mlD;
       spf=pass (google.com: domain of bnagaev@gmail.com designates 2607:f8b0:4864:20::532 as permitted sender) smtp.mailfrom=bnagaev@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1748469261; x=1749074061; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:content-transfer-encoding:cc:to:subject
         :message-id:date:from:in-reply-to:references:mime-version:sender
         :from:to:cc:subject:date:message-id:reply-to;
        bh=5lmsUarp3HMYFDk3Hi66Jm8mZ2/zMthGp3T2Ep47ReE=;
        b=J97yqUM4ZT49+TKE/AWkgKE42tc6K+PDZIsphN4P6YYKy2sn1hT/KjPQ5BRdZ7Haj+
         K2618O+PW3x9jTETf6D0z0Iw8OjYuzr4LyT2qK/ZWhcOqluiGF/ujjEHP3YKkEy8oaqP
         GbC+oZ+PeDZ0jarJLGS/25foaCw5CgmZuxIjD4GG3pIvGbpkLwQmHyOYPE4f6O9d72T8
         m1YsBuPrPF5aT7wLt+MUygxsa01xFMl7udBZmuwJ+5L9werorRVfIqb/dYfVLQgWQqL2
         z39nELpOdZou7YfX1fak7pQReaVU1jAD/rNVRMOKFO4llB9TIAwh2Rpasp/tLBJoPguW
         PeCA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1748469261; x=1749074061; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:content-transfer-encoding:cc:to:subject
         :message-id:date:from:in-reply-to:references:mime-version:from:to:cc
         :subject:date:message-id:reply-to;
        bh=5lmsUarp3HMYFDk3Hi66Jm8mZ2/zMthGp3T2Ep47ReE=;
        b=X1MECWPkER2IqNxBAlgUu1bzBsAJReiowpvXH9kEdhphsoHqJTM035wNkpYiSgVQ1d
         7WX0iTBLkB/D2CblMab6rnUx13bZ1mxCWmCgcNjwNSEupYLKliTXMX+uSXGQIxwuGE+t
         lLBSQTYAtYxzcT7m2spya634eJnWRNpZHwNoJmvGEwV4bMqGkuMdLcIY7F4SRSAfHK7z
         Ay1O4r4VuJYs1yd4OsPFrMI9Ctk4+kkI+ch7p6figUG5RtG7C5SVqxT3teTRN3bhpPUE
         wKN5KV539VUBtsUQKv+LaovbpRZNWq6Ja3bw2fZyQOnnIPrQI9QFVBtCSeW3+2A+AbjG
         ovZg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1748469261; x=1749074061;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:content-transfer-encoding:cc:to:subject
         :message-id:date:from:in-reply-to:references:mime-version
         :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date
         :message-id:reply-to;
        bh=5lmsUarp3HMYFDk3Hi66Jm8mZ2/zMthGp3T2Ep47ReE=;
        b=q/wmPQTITeCrhrQHCqmjSCnpYR7mT2R819qpVRcw6GfsCtVQ+ymnT68AIGbq1NbFhL
         XPW3/fF3hFrVFIbiO/42f9Ih1kgpZ6tHP3F3pw7L87Tol6RjOh1lErAj7PYckli5aRis
         QiAna//r6zAp7LN8YYderq++2R2lvOvFIPQwakN8JpgUwBZE+79me8109Ske9TktkEXL
         VmubAvzh6EdwXCPO/GAcogBro3sryGSkvSOK2ANqhPu3rZARHlqszH5hxmVcOK6MlK77
         SrRMJgU1tZt4H+1StMlQOFHecWbyEOyeKy2pMa9MzHjynoXP/eGzfFNeDuVOlr0E7kRv
         ntJA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCUg1UBAp0a+UXOHUM46IMf5yE0rfZfpSquPxoQVtk5dob3PyCDzpplnykMm/63FXgFEvTPpkGgimdFw@gnusha.org
X-Gm-Message-State: AOJu0Yxiimk3hKBQEmxSVk0bjxdBhfqc15DaqbDVYNW+BIUpUW792bxy
	nwKWx5+YRjnMQaFpvoRuO4M58Re1pz9JmVP65DRZ2/rj+whHY7Jyq8iE
X-Google-Smtp-Source: AGHT+IF/3XtoUbPpPXZbdhbKIMkn4fP+6eDN0MoOnzemXsBLhVXLKNVJXae4WlnUwQH9ih96+8VvNg==
X-Received: by 2002:a05:6214:21a3:b0:6f4:cfb3:9de1 with SMTP id 6a1803df08f44-6fa9d2b4a7bmr348484766d6.40.1748469261339;
        Wed, 28 May 2025 14:54:21 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZe81v+y3KcUwOEPbPU5dm2PxfRy/fj5ijz9K1tQElARkg==
Received: by 2002:a05:6214:a93:b0:6fa:c3dc:b019 with SMTP id
 6a1803df08f44-6fac5d96f42ls5063356d6.1.-pod-prod-08-us; Wed, 28 May 2025
 14:54:17 -0700 (PDT)
X-Received: by 2002:a05:620a:3199:b0:7cd:92:9f48 with SMTP id af79cd13be357-7ceecbf94f5mr2871418985a.52.1748469257384;
        Wed, 28 May 2025 14:54:17 -0700 (PDT)
Received: by 2002:a05:620a:134a:b0:7c5:3b15:3956 with SMTP id af79cd13be357-7d0995fd202ms85a;
        Wed, 28 May 2025 13:25:32 -0700 (PDT)
X-Received: by 2002:a05:6102:5112:b0:4c5:904d:f358 with SMTP id ada2fe7eead31-4e4241914dcmr15299498137.23.1748463931841;
        Wed, 28 May 2025 13:25:31 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1748463931; cv=none;
        d=google.com; s=arc-20240605;
        b=VQlq9xgh6FGUnQXq2NNl1tqpNLgCg/jStODPtBhtTeZHb2RaYAkLatmeQHtLnan3Kq
         QL57SjUVShK0rBFPjPyVMW7UcHK1JNo9wAj0Jggmwa9vJZQ9ex5nRLKltcdVsARsNIz5
         jedw2p85nw5wTj5eDj6AsviygSa6OH4YPHepyPVTz0CMVoE0wlPPul01KTxN9FBGdrpT
         d9paT3PnC9b+wptnhqYSTCiqPtm4ROJubLPTuP7QjbLfkR2xuL22WduyQjEYIqpknIDW
         rTl7IDfHo1mN9Ki4x42n3YxIvBULRNYFWKD+o6WcKg/wSohWMTXALqk1RupRWLJypd/2
         FHTg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=content-transfer-encoding:cc:to:subject:message-id:date:from
         :in-reply-to:references:mime-version:dkim-signature;
        bh=pZ3nJcQhzH7aP7XkOSsA9u9N4EHb8FOqVl4AB6NGCCQ=;
        fh=iL9DSYpC5RGeithzN5d/JVKj3o11LZT+9z7PU5q/3vc=;
        b=VtEuZWCG5OkiJASGdf+cWthXWpY2QsyC7Hm36sCKavMcuox40ANWZxnU919mYKpKuA
         QsRsLbrp/3ItFSrvemrAQUB9mhv/beC116xqiSVzJH51hmO6pl+X3AwPkMlgaPJ4y/TP
         ApZsb3Erz0TvDDhP5sfWhHttXboS/t8spNsbMnM+Qu99pmhbW4WPduG0eGnkYLH6YAFq
         CPvkEQt99QzoXb3CeSMkWE0Uh25fgtOYC0g+HnwNhH5nOHUsTI4lUMwrGcu0O849FuMs
         ZHcj25MNtdonIvkWsJWc2Y9isfryU30j9WSJrj0jhS7KD7YedSu2x7VI9bxSV25zFsit
         2Ojw==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=miMM8mlD;
       spf=pass (google.com: domain of bnagaev@gmail.com designates 2607:f8b0:4864:20::532 as permitted sender) smtp.mailfrom=bnagaev@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-pg1-x532.google.com (mail-pg1-x532.google.com. [2607:f8b0:4864:20::532])
        by gmr-mx.google.com with ESMTPS id ada2fe7eead31-4e59fc3111bsi52164137.1.2025.05.28.13.25.31
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Wed, 28 May 2025 13:25:31 -0700 (PDT)
Received-SPF: pass (google.com: domain of bnagaev@gmail.com designates 2607:f8b0:4864:20::532 as permitted sender) client-ip=2607:f8b0:4864:20::532;
Received: by mail-pg1-x532.google.com with SMTP id 41be03b00d2f7-b2d46760950so246689a12.3
        for <bitcoindev@googlegroups.com>; Wed, 28 May 2025 13:25:31 -0700 (PDT)
X-Gm-Gg: ASbGncurcnwjTakv6e6Q4I9Hy/JqR9xaxI4i2K45JLavb7XT3AB4XoXLGJBhoHRybYG
	o2FxcdF8e50qzxPWvzU6U8G3JV9bxrzchh6WgPXqmcQYh8Y5f5QP+if5vtzclfBMpjsY6CO40kQ
	hY3Z9jo+bIaYe8Dru6vA7KBLEqjjC1zk+D/X1GUMK65g==
X-Received: by 2002:a17:90b:3595:b0:311:ab20:159d with SMTP id
 98e67ed59e1d1-311ab20174amr9078971a91.19.1748463930537; Wed, 28 May 2025
 13:25:30 -0700 (PDT)
MIME-Version: 1.0
References: <cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com>
In-Reply-To: <cc2f8908-f6fa-45aa-93d7-6f926f9ba627n@googlegroups.com>
From: Nagaev Boris <bnagaev@gmail.com>
Date: Wed, 28 May 2025 17:24:52 -0300
X-Gm-Features: AX0GCFsGv3VqCKwNv5E8o09PG6xH2t8UMwCDrKdVVX_tDG4Uz5eci0X92FBh5B4
Message-ID: <CAFC_Vt6gqV-8aoTKt2it1p9LAnvaADueHnC1cM6LQojZf6fjCw@mail.gmail.com>
Subject: Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a
 soft fork
To: Tadge Dryja <rx@awsomnet.org>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Original-Sender: bnagaev@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=miMM8mlD;       spf=pass
 (google.com: domain of bnagaev@gmail.com designates 2607:f8b0:4864:20::532 as
 permitted sender) smtp.mailfrom=bnagaev@gmail.com;       dmarc=pass (p=NONE
 sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.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 (/)

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 <rx@awsomnet.org> wrote=
:
>
> One of the tricky things about securing Bitcoin against quantum computers=
 is: do you even need to?  Maybe quantum computers that can break secp256k1=
 keys will never exist, in which case we shouldn't waste our time.  Or mayb=
e they will exist, in not too many years, and we should spend the effort to=
 secure the system against QCs.
>
> Since people disagree on how likely QCs are to arrive, and what the timin=
g would be if they do, it's hard to get consensus on changes to bitcoin tha=
t disrupt the properties we use today.  For example, a soft fork introducin=
g a post-quantum (PQ) signature scheme and at the same time disallowing new=
 secp256k1 based outputs would be great for strengthening Bitcoin against a=
n oncoming QC.  But it would be awful if a QC never appears, or takes decad=
es to do so, since secp256k1 is really nice.
>
> So it would be nice to have a way to not deal with this issue until *afte=
r* the QC shows up.  With commit / reveal schemes Bitcoin can keep working =
after a QC shows up, even if we haven't defined a PQ signature scheme and e=
veryone's still got P2WPKH outputs.
>
> Most of this is similar to Tim Ruffing's proposal from a few years ago he=
re:
> https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarl=
and.de/
>
> The main difference is that this scheme doesn't use encryption, but a sma=
ller hash-based commitment, and describes activation as a soft fork.  I'll =
define the two types of attacks, a commitment scheme, and then say how it c=
an be implemented in bitcoin nodes as a soft fork.
>
> This scheme only works for keys that are pubkey hashes (or script hashes)=
 with pubkeys that are unknown to the network.  It works with taproot as we=
ll, but there must be some script-path in the taproot key, as keypath spend=
s would no longer be secure.
>
> What to do with all the keys that are known is another issue and independ=
ent of the scheme in this post (it's compatible with both burning them and =
leaving them to be stolen)
>
> For these schemes, we assume there is an attacker with a QC that can comp=
ute 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 the=
ir attacks; maybe not reliably, but they can sometimes get a few blocks in =
a row with the transactions they want.
>
> "Pubkey" can also be substituted with "script" for P2SH and P2WSH output =
types and should work about the same way (with caveats about multisig).  Th=
e 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, fo=
r any transaction with an EC signature in it, that transaction's txid must =
appear in a earlier transaction's OP_RETURN output.
>
> When a user wants to spend their coins, they first sign a transaction as =
they would normally, compute the txid, get that txid into an OP_RETURN outp=
ut somehow (paying a miner out of band, etc), then after waiting a while, b=
roadcast the transaction.  Nodes would check that the txid matches a previo=
usly seen commitment, and allow the transaction.
>
> One problem with this scheme is that upon seeing the full transaction, th=
e attacker can compute the user's private key, and create a new commitment =
with a different txid for a transaction where the attacker gets all the coi=
ns.  If the attacker can get their commitment and spending transaction in b=
efore the user's transaction, they can steal the coins.
>
> In order to mitigate this problem, a minimum delay can be enforced by con=
sensus.  A minimum delay of 100 blocks would mean that the attacker would h=
ave to prevent the user's transaction from being confirmed for 100 blocks a=
fter it showed up in the attacker's mempool.  The tradeoff is that longer p=
eriods give better safety at the cost of more delay in spending.
>
> This scheme, while problematic, is better than nothing!  But it's possibl=
e to remove this timing tradeoff.
>
>
> ## A slightly more complex scheme with (worse) problems
>
> If instead of just the txid, the commitment were both the outpoint being =
spent, and the txid that was going to spend it, we could add a "first seen"=
 consensus rule.  Only the first commitment pointing to an outpoint works.
>
> So if nodes see two OP_RETURN commitments in their sequence of confirmed =
transactions:
>
> C1 =3D outpoint1, txid1
> C2 =3D outpoint1, txid2
>
> They can ignore C2; C1 has already laid claim to outpoint1, and the trans=
action identified by txid1 is the only transaction that can spend outpoint1=
.
>
> If the user manages to get C1 confirmed first, this is great, and elimina=
tes the timing problem in the txid only scheme.  But this introduces a diff=
erent problem, where an attacker -- in this case any attacker, even one wit=
hout a QC -- who can observe C1 before it is confirmed can flip some bits i=
n the txid field, freezing the outpoint forever.
>
> We want to retain the "first seen" rule, but we want to also be able to d=
iscard invalid commitments.  In a bit flipping attack, we could say an inva=
lid commitment is one where there is no transaction described by the txid. =
 A more general way to classify a commitment as invalid is a commitment mad=
e without knowledge of the (secret) pubkey.  Knowledge of the pubkey is wha=
t security of coins is now hinging on.
>
>
> The actual commitment scheme
>
>
> We define some hash function h().  We'll use SHA256 for the hashing, but =
it needs to be keyed with some tag, for example "Alas poor Koblitz curve, w=
e knew it well".
>
> Thus h(pubkey) is not equal to the pubkey hash already used in the bitcoi=
n output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin =
terms, HASH160(pubkey).  Due to the hash functions being different, A =3D H=
ASH160(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 pubkey witho=
ut 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=
 will be signed for, a proof of knowledge of the pubkey which commits to a =
transaction, and an the txid of the spending transaction.  We'll call these=
 "address ID" (AID), sequence dependent proof (SDP), and the commitment txi=
d (CTXID).
>
> For those familiar with the proposal by Ruffing, the SDP has a similar fu=
nction to the authenticated encryption part of the encrypted commitment.  I=
nstead of using authenticated encryption, we can instead just use an HMAC-s=
tyle authentication alone, since the other data, the CTXID, is provided.
>
> When the user's wallet creates a transaction, they can feed that transact=
ion into a commitment generator function which takes in a transaction, extr=
acts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash =
commitment.  Once this commitment is confirmed, the user broadcasts the tra=
nsaction.
>
> Nodes verify the commitment by using the same commitment generator functi=
on and checking if it matches the first valid commitment for that AID, in w=
hich case the tx is confirmed.
>
> If a node sees multiple commitments all claiming the same AID, it must st=
ore all of them.  Once the AID's pubkey is known, the node can distinguish =
which commitments are valid, which are invalid, and which is the first seen=
 valid commitment.  Given the pubkey, nodes can determine commitments to be=
 invalid by checking if SDP =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 creat=
es C1, committing to a different txid where they control the outputs, and c=
onfirms it first.  This attacker may know the outpoint being spent, and may=
 be able to create a transaction and txid that could work.  But they don't =
know the pubkey, so while they can copy the AID hash, they have to make som=
ething up for the SDP.
>
> The user gets C2 confirmed after C1.  They then reveal tx2 in the mempool=
, but before it can be confirmed, the attacker gets C3 confirmed.  C3 is a =
valid commitment made with knowledge of the pubkey.
>
> Nodes can reject transactions tx1 and tx3.  For tx1, they will see that t=
he SDP doesn't match the data in the transaction, so it's an invalid commit=
ment.  For tx3, they will see that it is valid, but by seeing tx3 they will=
 also be able to determine that C2 is a valid commitment (since pubkey is r=
evealed in tx3) which came prior to C3, making C2 the only valid commitment=
 for that AID.
>
>
> ## Implementation
>
> Nodes would keep a new key/value store, similar to the existing UTXO set.=
  The indexing key would be the AID, and the value would be the set of all =
(SDP, CTXID) pairs seen alongside that AID.  Every time an commitment is se=
en in an OP_RETURN, nodes store the commitment.
>
> When a transaction is seen, nodes observe the pubkey used in the transact=
ion, and look up if it matches an AID they have stored.  If not, the transa=
ction is dropped.  If the AID does match, the node can now "clean out" an A=
ID entry, eliminating all but the first valid commitment, and marking that =
AID as final.  If the txid seen matches the remaining commitment, the trans=
action is valid; if not, the transaction is dropped.
>
> After the transaction is confirmed the AID entry can be deleted.  Deletin=
g the entries frees up space, and would allow another round to happen with =
the same pubkey, which would lead to theft.  Retaining the entries takes up=
 more space on nodes that can't be pruned, and causes pubkey reuse to destr=
oy coins rather than allow them to be stolen.  That's a tradeoff, and I per=
sonally guess it's probably not worth retaining that data but don't have a =
strong opinion either way.
>
> Short commitments:
>
> Since we're not trying to defend against collision attacks, I think all 3=
 hashes can be truncated to 16 bytes.  The whole commitment could be 48 byt=
es long.  Without truncation the commitments would be 96 bytes.
>
>
> ## Activation
>
> The activation for the commit/reveal requirement can be triggered by a pr=
oof 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 this script, the spending transaction needs to provide 2 data elements: a=
 signature, and some data that when hashed results in a pubkey for which th=
at signature is valid.  If such a pair of data elements exists, it means th=
at either SHA256 preimage resistance is broken (which we're assuming isn't =
the case) or someone can create valid signatures for arbitrary elliptic cur=
ve points, ie a cryptographically relevant quantum computer (or any other p=
rocess which breaks the security of secp256k1 signatures)
>
> Once such a PoQC has been observed in a confirmed transaction, the requir=
ements for the 3-hash commitment scheme can be enforced.  This is a soft fo=
rk since the transactions themselves look the same, the only requirement is=
 that some OP_RETURN outputs show up earlier.  Nodes which are not aware of=
 the commitment requirement will still accept all transactions with the new=
 rules.
>
> Wallets not aware of the new rules, however, are very dangerous, as they =
may try to broadcast signed transactions without any commitment.  Nodes tha=
t see such a transaction should drop the tx, and if possible tell the walle=
t that they are doing something which is now very dangerous!  On the open p=
2p network this is not really enforceable, but people submitting transactio=
ns 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 holdi=
ng bitcoin, that in the face of a sudden QC, even with minimal preparation =
their coins can be safe at rest and safely moved.  It also suggests some be=
st practices for users and wallets to adopt, before any software changes: D=
on't reuse addresses, and if you have taproot outputs, include some kind of=
 script path in the outer key.
>
> There are still a number of problems, though!
>
> - Reorgs can steal coins.  An attacker that observes a pubkey and can reo=
rg back to before the commitment can compute the private key, sign a new tr=
ansaction and get their commitment in first on the new chain.  This seems u=
navoidable with commit/reveal schemes, and it's up to the user how long the=
y 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 activ=
ates, there's only one type of transaction that can reliably get the OP_RET=
URN outputs confirmed: coinbase transactions.  Getting commitments to the m=
iners and paying them out of band is not great, but is possible and we see =
this kind of activity today.  Users wouldn't need to directly contact miner=
s: anyone could aggregate commitments, create a large transaction with many=
 OP_RETURN outputs, and then get a miner to commit to that parent transacti=
on.  Users don't need to worry about committing twice as identical commitme=
nts would be a no op.
>
> - Spam
> Anyone can make lots of OP_RETURN commitments which are just random numbe=
rs, forcing nodes to store these commitments in a database.  That's not gre=
at, but isn't much different from how bitcoin works today.  If it's really =
a problem, nodes could requiring the commitment outputs to have a non-0 amo=
unt of bitcoin, imposing a higher cost for the commitments than other OP_RE=
TURN outputs.
>
> - Multiple inputs
> If users have received more than one UTXO to the same address, they will =
need to spend all the UTXOs at once.  The commitment scheme can deal with o=
nly the first pubkey seen in the serialized transaction.
>
> - Multisig and Lightning Network
> If your multisig counterparties have a QC, multisig outputs become 1 of N=
.  Possibly a more complex commit / reveal scheme could deal with multiple =
keys, but the keys would all have to be hashed with counterparties not know=
ing each others' unhashed pubkeys.  This isn't how existing multisig output=
s work, and in fact the current trend is the opposite with things like Musi=
g2, FROST and ROAST.  If we're going to need to make new signing software a=
nd new output types it might make more sense to go for a PQ signature schem=
e.
>
> - Making more p2wpkhs
> You don't have to send to a PQ address type with these transactions -- yo=
u can send to p2wpkh and do the whole commit/reveal process again when you =
want to spend.  This could be helpful if PQ signature schemes are still bei=
ng worked on, or if the PQ schemes are more costly to verify and have high =
fees in comparison to the old p2wpkh output types.  It's possible that in s=
uch a scenario a few high-cost PQ transactions commit to many smaller EC tr=
ansactions.  If this actually gets adoption though, we might as well drop t=
he EC signatures and just make output scripts into raw hash / preimage pair=
s.  It could make sense to cover some non-EC script types with the same 3-h=
ash commitment requirement to enable this.
>
> ## Conclusion
>
> This PQ commit / reveal scheme has similar properties to Tim Ruffing's, w=
ith a smaller commitment that can be done as a soft fork.  I hope something=
 like this could be soft forked with a PoQC activation trigger, so that if =
a QC never shows up, none of this code gets executed.  And people who take =
a couple easy steps like not reusing addresses (which they should anyway fo=
r privacy reasons) don't have to worry about their coins.
>
> Some of these ideas may have been posted before; I know of the Fawkscoin =
paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent dis=
cussion which linked to Ruffing's proposal.  Here I've tried to show how it=
 could be done in a soft fork which doesn't look too bad to implement.
>
> I've also heard of some more complex schemes involving zero knowledge pro=
ofs, proving things like BIP32 derivations, but I think this gives some pre=
tty good properties without needing anything other than good old SHA256.
>
> Hope this is useful & wonder if people think something like this would be=
 a good idea.
>
> -Tadge
>
> --
> You received this message because you are subscribed to the Google Groups=
 "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
 email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoinde=
v/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%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/=
CAFC_Vt6gqV-8aoTKt2it1p9LAnvaADueHnC1cM6LQojZf6fjCw%40mail.gmail.com.