From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 28 May 2025 11:31:27 -0700 Received: from mail-oo1-f59.google.com ([209.85.161.59]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uKLYi-0004HS-RD for bitcoindev@gnusha.org; Wed, 28 May 2025 11:31:27 -0700 Received: by mail-oo1-f59.google.com with SMTP id 006d021491bc7-6061f07465fsf80670eaf.1 for ; Wed, 28 May 2025 11:31:24 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1748457079; cv=pass; d=google.com; s=arc-20240605; b=Ir6g44Nr7ech3tg15GTt5A/1wYV23sLdP5p8hHgy1PNiGHbl+n8/75THiJrJyJx//q +mE/Mak9QRC8ix7fpAX1N0mVs0jeB3/ioEgL93lPJbDJgK2PSoDRB7157ukcz3wLd4Cd PWugwtsNNfTRtuL6xrYC7L1K02zElr0rz6nqKisrC1/Gy32UcWREPS4Hj0EpMCEerEpn VHRC4AvGqa78HZ2dFPj+xukWCeDP/8r7uyXM5n0nnf2ORBs91WSbQA9WiRY+T86sSzgE VBpMRl1ztU8ZKUfADK/VFGfFYvEtnkaRaC4hn2ZbXe63JZUCCszaYSpPFo9gSCfnA5rg tVrw== 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=Dbnys7YHSZj9eO5Gu7wJbaH5j4lD47lrYzWmYRwDOqk=; fh=LFVEkA53n81Lwht0XfIFIeZ36xNoR1n/HVxLpauNGmU=; b=MZR6l5IhJprUVa4dpC0ipoS3UuEystMCESGm3l9NhAHUgKVovOs0J5g1PLYLRZYhyq lVs1YTwtNQPFuEGuwMmkmo7rGq4ChCX2fsr3IQ5JhaOfnaTQbkDgA7Xf3qpIVJ9RrgJs nqSYimYQdFzWf4+JmDnlybwl8LYeGPur2sdWKajByqUYBdLpw9stpccX1zSxWibrVcL4 gAxzYA+Ggc7mlIsREqU3PyL6aBUjPXDeRu4NdQchB+nVhxsDMXYpDjJlvnihspwidKiX QwivnC383wp4Qi8cg389yUJ0leIZme/E8oQm+N/DMC6EKN6tQTMgonND+yXAKF9s9TLw Fceg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=LojVYXPh; spf=pass (google.com: domain of sergio.d.lerner@gmail.com designates 2607:f8b0:4864:20::42b as permitted sender) smtp.mailfrom=sergio.d.lerner@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=1748457079; x=1749061879; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=Dbnys7YHSZj9eO5Gu7wJbaH5j4lD47lrYzWmYRwDOqk=; b=B1BD7wR4NKJNVros5tj9eXPJA7mgHmdxcU5yljLeJz6R/tUe26ClnSSWKNrm3aRCvc k3/Fj6aQ9S9R3CDZYEyG5mcjTk9gLpaeJbN/NXXL/qGWbLV2pKBNavlWdXW7HC2enYdD rSNdF8V/c5XCt/BtvpsCYzl0qCpzR6TMRtk04Y/xRUhWB60KN/qVal8soRgJUUdfk6SV Q329OzYrCaDIy1WJEi0kDENKvl0Bk7MYHCdMye7BxR5mXXdqGNA0VCjLFrhjsywpODlE IN48pCG4dFRyM47FYXYpWr5bV/Ujhh3KTjHGnnrwdMSSt3cNmWD8WvenKyTBScnWiKLp uWkA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1748457079; x=1749061879; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=Dbnys7YHSZj9eO5Gu7wJbaH5j4lD47lrYzWmYRwDOqk=; b=PC+lqld+YaO60dUYoYgS5/lRAXINbN5BtcZ+7s+KCiehEPblHaZrXQ15Vh8sSVvqXv XkHP5CTDYob2tKAGStd/fHZ8d4FkUsUvAMOx/UF1abRt2st7aoRWSJOrr7jCnGy1t/lI jV2zLA/uhePgxMPPpwLWTwO381l3lQKEC6N0DsXaulpmcThBzuhAVQh2IWetKMqtzMht 1kolf/PM0wIrwGey1BREM382gNUw8YRIODs6FDMPur6d5as6GgijjgaODEsW8fiG7fUE 2NkWy/4elN90R7uyiUHDmp420R3uYBu9lLalH4yCRK/bS0PIdW+1hXXbBqeGHSz3Ok/1 D3cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748457079; x=1749061879; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender: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=Dbnys7YHSZj9eO5Gu7wJbaH5j4lD47lrYzWmYRwDOqk=; b=rJGkBzBq8mlj9z7pjS1Fk/u1Gd3mh1h2f7uim2Xa4a6ZdY6y95OXDwwDh55Ckgq5Zj 7tuJIKFmrv/b7hBQund5r7yPtijIaXWjCSfmEpbLzBXLFHG0+ECBDkcGRZ8CXWQCy2ae baZD2Ua7Z5KEnipR5l5bgEQNLZy2xnyidcLLQC61F/34aCd4fXvBkMmWrxSJFV/TCewI 2CpNT1del3P4dQgqqriypOoXiKkplDDNgJmG/7goEmuAcZMnFkQjOTYIOs+/2xRg+pVy 4B1cX9sRCa0r18Oz2METWghtCLKVezxmpUIjJUzipUkwT8/bNCXaBRlm66ZYgFp7nv9/ +47g== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWS6ycbdO7CNEiibJ5pHoOxVm6V+sVVna4AQpqDPrwF/So92cyv/JUh70tmNXWyIrzI4urzJn7XsQH8@gnusha.org X-Gm-Message-State: AOJu0Yw/gM8F9vJL7fh6o9uF3jd0JH9jxUuxxLQe8Tj25m+xgGfALKST FAYtPlG9l4tK/SgUZEcnjMDSAuUw0d9H/5OgUgNVFu3AH4xLBMOFn3dD X-Google-Smtp-Source: AGHT+IGUJWcKsVMsADbK05JezU1SybQVPVmqxU4jshPd9fhCeDyO9TQYkSTJyb6NfIwTPa4lGOKqnw== X-Received: by 2002:a05:6820:179a:b0:609:def7:b3a0 with SMTP id 006d021491bc7-60b9fbddbd2mr9369204eaf.5.1748457078648; Wed, 28 May 2025 11:31:18 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZeYq8cZJVesCDqX6rDDFLmL9Byuw/n4/7Y3ZeXsz2OE5g== Received: by 2002:a05:6820:2e41:b0:60a:248:c91 with SMTP id 006d021491bc7-60be52e8401ls36120eaf.0.-pod-prod-02-us; Wed, 28 May 2025 11:31:13 -0700 (PDT) X-Received: by 2002:a05:6808:22a1:b0:3f4:1c2:874a with SMTP id 5614622812f47-40646845960mr10997438b6e.24.1748457073523; Wed, 28 May 2025 11:31:13 -0700 (PDT) Received: by 2002:a05:6808:82c7:b0:3f6:a384:eb6f with SMTP id 5614622812f47-404da00d5efmsb6e; Wed, 28 May 2025 11:20:46 -0700 (PDT) X-Received: by 2002:a17:90b:1d81:b0:311:c970:c9bc with SMTP id 98e67ed59e1d1-311c970d1fcmr8038546a91.30.1748456444820; Wed, 28 May 2025 11:20:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1748456444; cv=none; d=google.com; s=arc-20240605; b=B8M7UujdcUNs7jkqqrdy6GdvPRbZ6gJXIzWeOSHWzeDUnu40tf3GrsCEBWqQKtlh5o 7Q8w0UlbdLAl3RBoz0PNN3eSdESIdCkIaTnrhm6dwUl6Xuix/i0WqI5KnTDQ7+kpLVKJ jz9jo32yRfE57T27zUFfmrcaYpZJSbgqGUZE3gLtpj55V3FBdfgH34fZdS6GtEjD68EF ONZJzthRcElayEjlEiqKaHx0zsaXvTWUHjrQy4FOWKoGs4ijvWnv/FPFi9fZ0uU6N54h lZzv/oopVPTHXzfneNb8pjjlPszkwgDFBoV23yXh18/u6TuTAzf3VsFZp9p+IEZh93WW h5Lg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=r29MSgj65lVGLfPeBLrVYzV1kkHeVezDovczKW8jpI4=; fh=iL9DSYpC5RGeithzN5d/JVKj3o11LZT+9z7PU5q/3vc=; b=UYNmEQN6CCXAFeYNgrvs/8vGzloVfvLnzgwTxQAlwGnVbte7dIBT/ZjgV1CUjr45eY guNLq+p1ALzFcqOEphknDDZjp9aUFSfy5nA3rxmdCH5BdwMb4R7Ic3OHTYhznoUrdnZo 8ytJ7ZTc03LDCN/TjqnJ2eFoo/Y/GGm705DwLkHAnCV6eFidtWDKDo0KrllUt/C1qP4F Ffqg+VjBGmXYq8d2fw9ENAAzDM80Nl93HyQ2fY7F1dVNdC7ja/x1Fp3/AVSHm8Ydq6ZI tZAoYbCdwffHU5nPbrYWWwsweyGOKxR2fsJlA/1/XHk5rbaYhme9qTq/38uqTsMnBdF3 UHjg==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=LojVYXPh; spf=pass (google.com: domain of sergio.d.lerner@gmail.com designates 2607:f8b0:4864:20::42b as permitted sender) smtp.mailfrom=sergio.d.lerner@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-pf1-x42b.google.com (mail-pf1-x42b.google.com. [2607:f8b0:4864:20::42b]) by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-311e45b3d5esi151168a91.3.2025.05.28.11.20.44 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 28 May 2025 11:20:44 -0700 (PDT) Received-SPF: pass (google.com: domain of sergio.d.lerner@gmail.com designates 2607:f8b0:4864:20::42b as permitted sender) client-ip=2607:f8b0:4864:20::42b; Received: by mail-pf1-x42b.google.com with SMTP id d2e1a72fcca58-739b3fe7ce8so30174b3a.0 for ; Wed, 28 May 2025 11:20:44 -0700 (PDT) X-Gm-Gg: ASbGncvYsI5pVkA2ywXccWaxcIhSjVmv4yEgzZ8gXlMQ4mKSdzQUAcATXiTHMVaFgEX Dk8oXXxowSZd9Y9rQLSXbpHYevvlYySrCnsk35V8pvkZ4337u9uYLWX6fGpfOchHBb4xI0S1dxn c8Qd9g0KTTRs8Un6+CDNYgOw9HHojXD4oG X-Received: by 2002:a05:6a00:3d02:b0:73d:ff02:8d83 with SMTP id d2e1a72fcca58-745fde794bfmr27867435b3a.3.1748456444188; Wed, 28 May 2025 11:20:44 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Sergio Demian Lerner Date: Wed, 28 May 2025 11:20:07 -0700 X-Gm-Features: AX0GCFsgo2vCqOICPxkWhPlIgQaOv5dH0BLygTTi-poccGSVKH6JBpnTgn92f78 Message-ID: Subject: Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork To: Tadge Dryja Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="00000000000042daf70636363d68" X-Original-Sender: sergio.d.lerner@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=LojVYXPh; spf=pass (google.com: domain of sergio.d.lerner@gmail.com designates 2607:f8b0:4864:20::42b as permitted sender) smtp.mailfrom=sergio.d.lerner@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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) --00000000000042daf70636363d68 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Without in-depth reading of your e-mail, but related to Fawkescoin, you can read Mave paper from 2012 , which addressed DoS problems that exist in Fawkescoin. https://bitslog.com/wp-content/uploads/2012/04/mave1.pdf regards On Wed, May 28, 2025 at 10:28=E2=80=AFAM Tadge Dryja wrot= e: > One of the tricky things about securing Bitcoin against quantum computers > is: do you even need to? Maybe quantum computers that can break secp256k= 1 > keys will never exist, in which case we shouldn't waste our time. Or may= be > 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 = an > 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 > *after* the QC shows up. With commit / reveal schemes Bitcoin can keep > working after a QC shows up, even if we haven't defined a PQ signature > scheme and everyone's still got P2WPKH outputs. > > Most of this is similar to Tim Ruffing's proposal from a few years ago > here: > > https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarl= and.de/ > > The main difference is that this scheme doesn't use encryption, but a > smaller hash-based commitment, and describes activation as a soft fork. > I'll define the two types of attacks, a commitment scheme, and then say h= ow > it can be implemented in bitcoin nodes as a soft fork. > > This scheme only works for keys that are pubkey hashes (or script hashes) > with pubkeys that are unknown to the network. It works with taproot as > well, but there must be some script-path in the taproot key, as keypath > spends would no longer be secure. > > What to do with all the keys that are known is another issue and > independent of the scheme in this post (it's compatible with both burning > them and leaving them to be stolen) > > For these schemes, we assume there is an attacker with a QC that can > compute a quickly compute a private key from any secp256k1 public key. W= e > also assume the attacker has some mining power or influence over miners f= or > their attacks; maybe not reliably, but they can sometimes get a few block= s > in a row with the transactions they want. > > "Pubkey" can also be substituted with "script" for P2SH and P2WSH output > types and should work about the same way (with caveats about multisig). > The equivalent for taproot outputs would be an inner key proving a script > path. > > ## A simple scheme to show an attack > > The simplest commit/reveal scheme would be one where after activation, 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 > output somehow (paying a miner out of band, etc), then after waiting a > while, broadcast the transaction. Nodes would check that the txid matche= s > a previously 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 > coins. If the attacker can get their commitment and spending transaction > in before the user's transaction, they can steal the coins. > > In order to mitigate this problem, a minimum delay can be enforced by > consensus. A minimum delay of 100 blocks would mean that the attacker > would have to prevent the user's transaction from being confirmed for 100 > blocks after it showed up in the attacker's mempool. The tradeoff is tha= t > 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 > 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 see= n" > 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 > transaction identified by txid1 is the only transaction that can spend > outpoint1. > > If the user manages to get C1 confirmed first, this is great, and > eliminates the timing problem in the txid only scheme. But this introduc= es > 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 so= me > bits in the txid field, freezing the outpoint forever. > > We want to retain the "first seen" rule, but we want to also be able to > discard invalid commitments. In a bit flipping attack, we could say an > invalid commitment is one where there is no transaction described by the > txid. A more general way to classify a commitment as invalid is a > commitment made without knowledge of the (secret) pubkey. Knowledge of t= he > pubkey is what security of coins is now hinging on. > > > The actual commitment scheme > > > We define some hash function h(). We'll use SHA256 for the hashing, but > it needs to be keyed with some tag, for example "Alas poor Koblitz curve, > we knew it well". > > Thus h(pubkey) is not equal to the pubkey hash already used in the 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 > HASH160(pubkey) and B =3D h(pubkey) will be completely different, and nob= ody > should be able to determine if A and B are hashes of the same pubkey > 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 > 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 the= se > "address ID" (AID), sequence dependent proof (SDP), and the commitment tx= id > (CTXID). > > For those familiar with the proposal by Ruffing, the SDP has a similar > function to the authenticated encryption part of the encrypted commitment= . > Instead of using authenticated encryption, we can instead just use an > HMAC-style authentication alone, since the other data, the CTXID, is > provided. > > When the user's wallet creates a transaction, they can feed that > transaction into a commitment generator function which takes in a > transaction, extracts the pubkey from the tx, computes the 3 hashes, and > returns the 3-hash commitment. Once this commitment is confirmed, the us= er > broadcasts the transaction. > > Nodes verify the commitment by using the same commitment generator > function and checking if it matches the first valid commitment for that > AID, in which case the tx is confirmed. > > If a node sees multiple commitments all claiming the same AID, it must > store all of them. Once the AID's pubkey is known, the node can > distinguish which commitments are valid, which are invalid, and which is > the first seen valid commitment. Given the pubkey, nodes can determine > commitments to be invalid by checking if SDP =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 > 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 th= ey > don't know the pubkey, so while they can copy the AID hash, they have to > make something up for the SDP. > > The user gets C2 confirmed after C1. They then reveal tx2 in the mempool= , > but before it can be confirmed, the attacker gets C3 confirmed. C3 is a > valid commitment made with knowledge of the pubkey. > > Nodes can reject transactions tx1 and tx3. For tx1, they will see that > the SDP doesn't match the data in the transaction, so it's an invalid > commitment. For tx3, they will see that it is valid, but by seeing tx3 > they will also be able to determine that C2 is a valid commitment (since > pubkey is revealed in tx3) which came prior to C3, making C2 the only val= id > commitment for that AID. > > > ## Implementation > > Nodes would keep a new key/value store, similar to the existing UTXO set. > The indexing key would be the AID, and the value would be the set of all > (SDP, CTXID) pairs seen alongside that AID. Every time an commitment is > seen in an OP_RETURN, nodes store the commitment. > > When a transaction is seen, nodes observe the pubkey used in the > transaction, and look up if it matches an AID they have stored. If not, > the transaction is dropped. If the AID does match, the node can now "cle= an > out" an AID entry, eliminating all but the first valid commitment, and > marking that AID as final. If the txid seen matches the remaining > commitment, the transaction is valid; if not, the transaction is dropped. > > After the transaction is confirmed the AID entry can be deleted. 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 > destroy coins rather than allow them to be stolen. That's a tradeoff, an= d > I personally guess it's probably not worth retaining that data but don't > have a strong opinion either way. > > Short commitments: > > Since we're not trying to defend against collision attacks, I think all 3 > hashes can be truncated to 16 bytes. The whole commitment could be 48 > bytes long. Without truncation the commitments would be 96 bytes. > > > ## Activation > > The activation for the commit/reveal requirement can be triggered by a > proof of quantum computer (PoQC). > > A transaction which successfully spends an output using tapscript: > > OP_SHA256 OP_CHECKSIG > > is a PoQC in the form of a valid bitcoin transaction. In order to 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 > that signature is valid. If such a pair of data elements exists, it mean= s > that either SHA256 preimage resistance is broken (which we're assuming > isn't the case) or someone can create valid signatures for arbitrary > elliptic curve points, ie a cryptographically relevant quantum computer (= or > any other process which breaks the security of secp256k1 signatures) > > Once such a PoQC has been observed in a confirmed transaction, the > requirements for the 3-hash commitment scheme can be enforced. This is a > soft fork since the transactions themselves look the same, the only > requirement is that some OP_RETURN outputs show up earlier. Nodes which > are not aware of the commitment requirement will still accept all > transactions with the new rules. > > Wallets not aware of the new rules, however, are very dangerous, as they > may try to broadcast signed transactions without any commitment. Nodes > that see such a transaction should drop the tx, and if possible tell the > wallet that they are doing something which is now very dangerous! On the > open p2p network this is not really enforceable, but people submitting > transactions to their own node (eg via RPC) can at least get a scary erro= r > message. > > > ## Issues > > My hope is that this scheme would give some peace of mind to people > holding bitcoin, that in the face of a sudden QC, even with minimal > preparation their coins can be safe at rest and safely moved. It also > suggests some best practices for users and wallets to adopt, before any > software changes: Don't reuse addresses, and if you have taproot outputs, > include some kind of script path in the outer key. > > There are still a number of problems, though! > > - Reorgs can steal coins. An attacker that observes a pubkey and can > reorg back to before the commitment can compute the private key, sign a n= ew > transaction and get their commitment in first on the new chain. This see= ms > unavoidable with commit/reveal schemes, and it's up to the user how long > they wait between confirming the commitment and revealing the transaction= . > > - How to get op_returns in > If there are no PQ signature schemes activated in bitcoin when this > activates, there's only one type of transaction that can reliably get the > OP_RETURN outputs confirmed: coinbase transactions. Getting commitments = to > the miners and paying them out of band is not great, but is possible and = we > see this kind of activity today. Users wouldn't need to directly contact > miners: anyone could aggregate commitments, create a large transaction wi= th > many OP_RETURN outputs, and then get a miner to commit to that parent > transaction. Users don't need to worry about committing twice as identic= al > commitments would be a no op. > > - Spam > Anyone can make lots of OP_RETURN commitments which are just random > numbers, forcing nodes to store these commitments in a database. That's > not great, but isn't much different from how bitcoin works today. If it'= s > really a problem, nodes could requiring the commitment outputs to have a > non-0 amount of bitcoin, imposing a higher cost for the commitments than > other OP_RETURN outputs. > > - Multiple inputs > If users have received more than one UTXO to the same address, they will > need to spend all the UTXOs at once. The commitment scheme can deal with > only the first pubkey seen in the serialized transaction. > > - Multisig and Lightning Network > If your multisig counterparties have a QC, multisig outputs become 1 of > N. Possibly a more complex commit / reveal scheme could deal with multip= le > keys, but the keys would all have to be hashed with counterparties not > knowing each others' unhashed pubkeys. This isn't how existing multisig > outputs work, and in fact the current trend is the opposite with things > like Musig2, FROST and ROAST. If we're going to need to make new signing > software and new output types it might make more sense to go for a PQ > signature scheme. > > - Making more p2wpkhs > You don't have to send to a PQ address type with these transactions -- 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 > being worked on, or if the PQ schemes are more costly to verify and have > high fees in comparison to the old p2wpkh output types. It's possible th= at > in such a scenario a few high-cost PQ transactions commit to many smaller > EC transactions. If this actually gets adoption though, we might as well > drop the EC signatures and just make output scripts into raw hash / > preimage pairs. It could make sense to cover some non-EC script types wi= th > the same 3-hash commitment requirement to enable this. > > ## Conclusion > > This PQ commit / reveal scheme has similar properties to Tim Ruffing's, > with a smaller commitment that can be done as a soft fork. I hope > something like this could be soft forked with a PoQC activation trigger, = so > that if a QC never shows up, none of this code gets executed. And people > who take a couple easy steps like not reusing addresses (which they shoul= d > anyway for privacy reasons) don't have to worry about their coins. > > Some of these ideas may have been posted before; I know of the Fawkscoin > paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent > discussion which linked to Ruffing's proposal. Here I've tried to show h= ow > it could be done in a soft fork which doesn't look too bad to implement. > > I've also heard of some more complex schemes involving zero knowledge > proofs, proving things like BIP32 derivations, but I think this gives som= e > 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 > a good idea. > > -Tadge > > -- > You received this message because you are subscribed to the Google Groups > "Bitcoin Development Mailing List" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f92= 6f9ba627n%40googlegroups.com > > . > --=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/= CAKzdR-rLT-QDoawED%3Dwf1DQKfYcVa_LPWBbHbK5GzekGhAFvZg%40mail.gmail.com. --00000000000042daf70636363d68 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Without in-depth reading of your e-mail, but related to Fa= wkescoin, you can read Mave paper from 2012 , which addressed DoS problems = that exist in Fawkescoin.


regards

On Wed, May 28, 2025 at 10:28=E2=80=AFAM Tadge Dryja <rx@awsomnet.org> wrote:
One of the tricky things about s= ecuring Bitcoin against quantum computers is: do you even need to?=C2=A0 Ma= ybe quantum computers that can break secp256k1 keys will never exist, in wh= ich case we shouldn't waste our time.=C2=A0 Or maybe they will exist, i= n not too many years, and we should spend the effort to secure the system a= gainst QCs.

Since people disagree on how likely QCs are to arrive, a= nd what the timing would be if they do, it's hard to get consensus on c= hanges to bitcoin that disrupt the properties we use today.=C2=A0 For examp= le, a soft fork introducing a post-quantum (PQ) signature scheme and at the= same time disallowing new secp256k1 based outputs would be great for stren= gthening Bitcoin against an oncoming QC.=C2=A0 But it would be awful if a Q= C never appears, or takes decades to do so, since secp256k1 is really nice.=

So it would be nice to have a way to not deal with this issue until= *after* the QC shows up.=C2=A0 With commit / reveal schemes Bitcoin can ke= ep working after a QC shows up, even if we haven't defined a PQ signatu= re scheme and everyone's still got P2WPKH outputs.

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

The main difference is tha= t this scheme doesn't use encryption, but a smaller hash-based commitme= nt, and describes activation as a soft fork.=C2=A0 I'll define the two = types of attacks, a commitment scheme, and then say how it can be implement= ed 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.=C2=A0 It works with taproot as well, but there must be some sc= ript-path in the taproot key, as keypath spends would no longer be secure. = =C2=A0

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

For these schemes, we ass= ume there is an attacker with a QC that can compute a quickly compute a pri= vate key from any secp256k1 public key.=C2=A0 We also assume the attacker h= as 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 transac= tions they want.

"Pubkey" can also be substituted with &qu= ot;script" for P2SH and P2WSH output types and should work about the s= ame way (with caveats about multisig).=C2=A0 The equivalent for taproot out= puts would be an inner key proving a script path.

## A simple scheme= to show an attack

The simplest commit/reveal scheme would be one wh= ere after activation, for any transaction with an EC signature in it, that = transaction's txid must appear in a earlier transaction's OP_RETURN= output.

When a user wants to spend their coins, they first sign a t= ransaction as they would normally, compute the txid, get that txid into an = OP_RETURN output somehow (paying a miner out of band, etc), then after wait= ing a while, broadcast the transaction.=C2=A0 Nodes would check that the tx= id matches a previously seen commitment, and allow the transaction.

= One problem with this scheme is that upon seeing the full transaction, the = attacker can compute the user's private key, and create a new commitmen= t with a different txid for a transaction where the attacker gets all the c= oins.=C2=A0 If the attacker can get their commitment and spending transacti= on in before the user's transaction, they can steal the coins.

I= n order to mitigate this problem, a minimum delay can be enforced by consen= sus.=C2=A0 A minimum delay of 100 blocks would mean that the attacker would= have to prevent the user's transaction from being confirmed for 100 bl= ocks after it showed up in the attacker's mempool.=C2=A0 The tradeoff i= s that longer periods give better safety at the cost of more delay in spend= ing.

This scheme, while problematic, is better than nothing!=C2=A0 B= ut it's possible to remove this timing tradeoff.


## A slight= ly 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= .=C2=A0 Only the first commitment pointing to an outpoint works.

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

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

T= hey can ignore C2; C1 has already laid claim to outpoint1, and the transact= ion identified by txid1 is the only transaction that can spend outpoint1.
If the user manages to get C1 confirmed first, this is great, and eli= minates the timing problem in the txid only scheme.=C2=A0 But this introduc= es a different problem, where an attacker -- in this case any attacker, eve= n one without a QC -- who can observe C1 before it is confirmed can flip so= me 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 dis= card invalid commitments.=C2=A0 In a bit flipping attack, we could say an i= nvalid commitment is one where there is no transaction described by the txi= d.=C2=A0 A more general way to classify a commitment as invalid is a commit= ment made without knowledge of the (secret) pubkey.=C2=A0 Knowledge of the = pubkey is what security of coins is now hinging on.


The actual c= ommitment scheme


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

Thus h= (pubkey) is not equal to the pubkey hash already used in the bitcoin output= script, which instead is RIPEMD160(SHA256(pubkey)), or in bitcoin terms, H= ASH160(pubkey).=C2=A0 Due to the hash functions being different, A =3D HASH= 160(pubkey) and B =3D h(pubkey) will be completely different, and nobody sh= ould be able to determine if A and B are hashes of the same pubkey without = knowing pubkey itself.

An efficient commitment is:

C =3D =C2= =A0h(pubkey), h(pubkey, txid), txid
(to label things: C =3D AID, SD= P, CTXID)

This commitment includes 3 elements: a differ= ent hash of the pubkey which will be signed for, a proof of knowledge of th= e pubkey which commits to a transaction, and an the txid of the spending tr= ansaction.=C2=A0 We'll call these "address ID" (AID), sequenc= e dependent proof (SDP), and the commitment txid (CTXID).

For those = familiar with the proposal by Ruffing, the SDP has a similar function to th= e authenticated encryption part of the encrypted commitment.=C2=A0 Instead = of using authenticated encryption, we can instead just use an HMAC-style au= thentication alone, since the other data, the CTXID, is provided.

W= hen the user's wallet creates a transaction, they can feed that transac= tion into a commitment generator function which takes in a transaction, ext= racts the pubkey from the tx, computes the 3 hashes, and returns the 3-hash= commitment.=C2=A0 Once this commitment is confirmed, the user broadcasts t= he transaction.

Nodes verify the commitment by using the same commit= ment generator function and checking if it matches the first valid commitme= nt for that AID, in which case the tx is confirmed.

If a node sees m= ultiple commitments all claiming the same AID, it must store all of them.= =C2=A0 Once the AID's pubkey is known, the node can distinguish which c= ommitments are valid, which are invalid, and which is the first seen valid = commitment.=C2=A0 Given the pubkey, nodes can determine commitments to be i= nvalid by checking if SDP =3D h(pubkey, CTXID).

As an example, consi= der a sequence of 3 commitments:

C1 =3D h(pubkey), h(pubkey', tx= id1), 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 c= ommit C2.=C2=A0 But an attacker creates C1, committing to a different txid = where they control the outputs, and confirms it first.=C2=A0 This attacker = may know the outpoint being spent, and may be able to create a transaction = and txid that could work.=C2=A0 But they don't know the pubkey, so whil= e they can copy the AID hash, they have to make something up for the SDP.
The user gets C2 confirmed after C1.=C2=A0 They then reveal tx2 in th= e mempool, but before it can be confirmed, the attacker gets C3 confirmed.= =C2=A0 C3 is a valid commitment made with knowledge of the pubkey.

N= odes can reject transactions tx1 and tx3.=C2=A0 For tx1, they will see that= the SDP doesn't match the data in the transaction, so it's an inva= lid commitment.=C2=A0 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.


## Implementation

Nodes wou= ld keep a new key/value store, similar to the existing UTXO set.=C2=A0 The = indexing key would be the AID, and the value would be the set of all (SDP, = CTXID) pairs seen alongside that AID.=C2=A0 Every time an commitment is see= n in an OP_RETURN, nodes store the commitment.

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

After the tr= ansaction is confirmed the AID entry can be deleted.=C2=A0 Deleting the ent= ries frees up space, and would allow another round to happen with the same = pubkey, which would lead to theft.=C2=A0 Retaining the entries takes up mor= e space on nodes that can't be pruned, and causes pubkey reuse to destr= oy coins rather than allow them to be stolen.=C2=A0 That's a tradeoff, = and I personally guess it's probably not worth retaining that data but = don't have a strong opinion either way.

Short commitments:
Since we're not trying to defend against collision attacks, I think a= ll 3 hashes can be truncated to 16 bytes.=C2=A0 The whole commitment could = be 48 bytes long.=C2=A0 Without truncation the commitments would be 96 byte= s.


## Activation

The activation for the commit/reveal req= uirement can be triggered by a proof of quantum computer (PoQC).

A t= ransaction which successfully spends an output using tapscript:

OP_S= HA256 OP_CHECKSIG

is a PoQC in the form of a valid bitcoin transacti= on.=C2=A0 In order to satisfy this script, the spending transaction needs t= o provide 2 data elements: a signature, and some data that when hashed resu= lts in a pubkey for which that signature is valid.=C2=A0 If such a pair of = data elements exists, it means that either SHA256 preimage resistance is br= oken (which we're assuming isn't the case) or someone can create va= lid signatures for arbitrary elliptic curve points, ie a cryptographically = relevant quantum computer (or any other process which breaks the security o= f secp256k1 signatures)

Once such a PoQC has been observed in a conf= irmed transaction, the requirements for the 3-hash commitment scheme can be= enforced.=C2=A0 This is a soft fork since the transactions themselves look= the same, the only requirement is that some OP_RETURN outputs show up earl= ier.=C2=A0 Nodes which are not aware of the commitment requirement will sti= ll accept all transactions with the new rules. =C2=A0

Wallets not aw= are of the new rules, however, are very dangerous, as they may try to broad= cast signed transactions without any commitment.=C2=A0 Nodes that see such = a transaction should drop the tx, and if possible tell the wallet that they= are doing something which is now very dangerous!=C2=A0 On the open p2p net= work this is not really enforceable, but people submitting transactions to = their own node (eg via RPC) can at least get a scary error message.

=
## Issues

My hope is that this scheme would give some peace of m= ind to people holding bitcoin, that in the face of a sudden QC, even with m= inimal preparation their coins can be safe at rest and safely moved.=C2=A0 = It also suggests some best practices for users and wallets to adopt, before= any software changes: Don't reuse addresses, and if you have taproot o= utputs, include some kind of script path in the outer key.

There are= still a number of problems, though!

- Reorgs can steal coins.=C2=A0= An attacker that observes a pubkey and can reorg back to before the commit= ment can compute the private key, sign a new transaction and get their comm= itment in first on the new chain.=C2=A0 This seems unavoidable with commit/= reveal schemes, and it's up to the user how long they wait between conf= irming the commitment and revealing the transaction.

- How to get op= _returns in
If there are no PQ signature schemes activated in bitcoin wh= en this activates, there's only one type of transaction that can reliab= ly get the OP_RETURN outputs confirmed: coinbase transactions.=C2=A0 Gettin= g commitments to the miners and paying them out of band is not great, but i= s possible and we see this kind of activity today.=C2=A0 Users wouldn't= need to directly contact miners: anyone could aggregate commitments, creat= e a large transaction with many OP_RETURN outputs, and then get a miner to = commit to that parent transaction.=C2=A0 Users don't need to worry abou= t committing twice as identical commitments would be a no op.

<= /div>
- Spam
Anyone can make lots of OP_RETURN commitments wh= ich are just random numbers, forcing nodes to store these commitments in a = database.=C2=A0 That's not great, but isn't much different from how= bitcoin works today.=C2=A0 If it's really a problem, nodes could requi= ring the commitment outputs to have a non-0 amount of bitcoin, imposing a h= igher cost for the commitments than other OP_RETURN outputs.

=
- Multiple inputs
If users have received more than one UTXO to the= same address, they will need to spend all the UTXOs at once.=C2=A0 The com= mitment scheme can deal with only the first pubkey seen in the serialized t= ransaction.

- Multisig and Lightning Network
If your multisig cou= nterparties have a QC, multisig outputs become 1 of N.=C2=A0 Possibly a mor= e complex commit / reveal scheme could deal with multiple keys, but the key= s would all have to be hashed with counterparties not knowing each others&#= 39; unhashed pubkeys.=C2=A0 This isn't how existing multisig outputs wo= rk, and in fact the current trend is the opposite with things like Musig2, = FROST and ROAST.=C2=A0 If we're going to need to make new signing softw= are and new output types it might make more sense to go for a PQ signature = scheme.

- Making more p2wpkhs
You don't have to send to a PQ = address type with these transactions -- you can send to p2wpkh and do the w= hole commit/reveal process again when you want to spend.=C2=A0 This could b= e helpful if PQ signature schemes are still being worked on, or if the PQ s= chemes are more costly to verify and have high fees in comparison to the ol= d p2wpkh output types.=C2=A0 It's possible that in such a scenario a fe= w high-cost PQ transactions commit to many smaller EC transactions.=C2=A0 I= f this actually gets adoption though, we might as well drop the EC signatur= es and just make output scripts into raw hash / preimage pairs.=C2=A0 It co= uld make sense to cover some non-EC script types with the same 3-hash commi= tment requirement to enable this.

## Conclusion

This PQ commi= t / reveal scheme has similar properties to Tim Ruffing's, with a small= er commitment that can be done as a soft fork.=C2=A0 I hope something like = this could be soft forked with a PoQC activation trigger, so that if a QC n= ever shows up, none of this code gets executed.=C2=A0 And people who take a= couple easy steps like not reusing addresses (which they should anyway for= privacy reasons) don't have to worry about their coins.

Some of= these ideas may have been posted before; I know of the Fawkscoin paper (https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf) and the recent disc= ussion which linked to Ruffing's proposal.=C2=A0 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 involv= ing zero knowledge proofs, proving things like BIP32 derivations, but I thi= nk this gives some pretty good properties without needing anything other th= an 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 &= quot;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.googl= e.com/d/msgid/bitcoindev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegrou= ps.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/= msgid/bitcoindev/CAKzdR-rLT-QDoawED%3Dwf1DQKfYcVa_LPWBbHbK5GzekGhAFvZg%40ma= il.gmail.com.
--00000000000042daf70636363d68--