From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 02 Jun 2025 13:03:45 -0700 Received: from mail-oo1-f61.google.com ([209.85.161.61]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uMBNn-0005DB-62 for bitcoindev@gnusha.org; Mon, 02 Jun 2025 13:03:45 -0700 Received: by mail-oo1-f61.google.com with SMTP id 006d021491bc7-60beb61fc3bsf956634eaf.0 for ; Mon, 02 Jun 2025 13:03:43 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1748894617; cv=pass; d=google.com; s=arc-20240605; b=KOQw7Iq88wPx4kQEIu3ScaOcSFXafuLZOVjn99CmxA6knDrm34Qkd3SxZ3P5MYfJHO g0QFJYqzIzBGdK6wDUAI1Pv0VMdkcim5FLAW90cAzC0tT2j468apNotsH32K9eYC9t5q AqeMk91KBONW4m+A0dt6ruVfOCpiG8ClJ5gZ1Fe2sTUyNybC6Q8wfd6zk1dWlxSZ+1ll zjWF4FT97xfM5RFFC6/GHOYlW6ZnOQ5RgP7liz20w4RC1TsQolBAuOvjLOB6d6IF2dWp pwzW17QK1PhoReKdmO6yVJfKM2xIAUloolYk4hrqRAHlo2GK3OO1IhTGcahOI+xh1wF5 oRNQ== 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:reply-to:mime-version:feedback-id :references:in-reply-to:message-id:subject:cc:from:to:date :dkim-signature; bh=6e6HMTeGazh/nYfHVanqJqdpgki5b9NHQE7ClnHwn0Q=; fh=nZSg11QRlw5Lkvr705CzbOUr3g84YT9K1cQHJhJWv+0=; b=ivIcHQM3Fqr0hptVascyrWut1PYJt6rf0KYfaqNq2erkxz5gB7X9yrSJ+oJnts6ifA uWaxtePpDkQuLrhQY//TuEmC2jD8aXmL0uTmCaDFGraDFXj+qiFk0Dn82Q0uxygmqtu2 reSEw8qloYeEBDc7ct6v/BcIaius/Ci99tRMdegzlhmGi5s55PJss0fMX1mr2PU7Iyh/ 4+9zp1cIhxXQCM5SfssnPQJkdkbgbDycbNQkRa1qrDw4GCT3QzPV1dUqB5czM4CCKRM9 K+mKbqJeeXv9FJJb0bc9GKuyGHRqOtn7BZhAN8ldxCo9ieRsWYI4MhuGmziLxgOukCxV YtTg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=l8jjWqVi; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1748894617; x=1749499417; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:from:to:cc:subject:date:message-id:reply-to; bh=6e6HMTeGazh/nYfHVanqJqdpgki5b9NHQE7ClnHwn0Q=; b=rdE48fS2WuJML5szhK19mxSTc9R6x6dMl8OGYO9Joa0rlSi6cahQRK7oySNyIYqnDk AH/9ohOTe8eawpTT19K8TQBiEKYjju5bGBPEQFnGNtXa8ZkUtJeg1akE19GIMEIC8SyU /AphFikcVyWn07LzmXRzLLKvU0bFhgSX5ahxj5SIkWx8saEm3KKd0rCHguiYtZcKzCpu gIv7ZrjCjuGRJL9QfjE44pggS1bk29foITTY2SuNWA7t3B4iF3EleBvHPRW4spZptrsd E39vd4zcZNtImEaiR/Elw7HtX+MzLpok4mrLpAMFzmfdS9HVjJrkr4I4EQrnm7H+thoY 5dXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1748894617; x=1749499417; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:x-beenthere:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=6e6HMTeGazh/nYfHVanqJqdpgki5b9NHQE7ClnHwn0Q=; b=cMUEA1kYb+Pnvk6iZ20xgb7xELZa67yGd58+D8bXd+syJBE+YBHCih8c2KPnZ4Q+FI qAOKmiu/9mIDVJSsXhv9fIznGffa621eCXXBXrzS+r0H+dkd0Ru5Ivq7DqTL3fJacxDb Nqhn9DVKe1SUJ+LnhcnPrA6YWG7qCxY/SFKXHQwcQjCpMt1l2S/UXMjYeigFIv2Tl9oS KO+O1c8poGUilV9lmOI2a5Nj78VEN/+Qo2FKFNsghljc5Unx3vgMlxxLCvupp+OuwSPN TQzCsF4y/6lHuEPUX0REWcLB3Cv4S6bXGVW1fiD+URYRuBC8qdqlmg5+2ejDEv1unG53 xVfg== X-Forwarded-Encrypted: i=2; AJvYcCXmB0oHuQbxAjU+n83pNQ6tx0tPQfUcPwEFjFYxEt3nlj0ul+LOPkj3wqOgwbVMVt70D7kvxTzBixOc@gnusha.org X-Gm-Message-State: AOJu0Yx5nFZ/ORzdc2VOKcr0PR2tseCqrkP+070anwvX5K6IVZewHoeb 84RahpOkZvibbk3fLML0+WFG01jcxJgMjfwIIivW9vdZmU8LM80BWNmn X-Google-Smtp-Source: AGHT+IGA/LhO1FUu4V4KVtWXjxUFBjnuimkAXTJl6Y0EDSRPb2ektunqy6mYVbg7JHjfhNkx91MLyw== X-Received: by 2002:a05:6820:2a18:b0:60e:d5d3:c3cd with SMTP id 006d021491bc7-60efb69a53cmr162986eaf.2.1748894617588; Mon, 02 Jun 2025 13:03:37 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZebRm6vHsR+bOW4UipGhrD2Gcn4RtnrXQNRNiw9MIvzNA== Received: by 2002:a4a:e614:0:b0:604:8bd0:c016 with SMTP id 006d021491bc7-60be548c60bls1783177eaf.2.-pod-prod-01-us; Mon, 02 Jun 2025 13:03:34 -0700 (PDT) X-Received: by 2002:a05:6808:6410:b0:406:780c:20ab with SMTP id 5614622812f47-4067966dfafmr8072861b6e.6.1748894614432; Mon, 02 Jun 2025 13:03:34 -0700 (PDT) Received: by 2002:a05:600c:4fc4:b0:450:ce23:93de with SMTP id 5b1f17b1804b1-450d6b2f057ms5e9; Mon, 2 Jun 2025 12:34:16 -0700 (PDT) X-Received: by 2002:a05:600c:1c8d:b0:440:6a5f:c308 with SMTP id 5b1f17b1804b1-450d880cc58mr104326605e9.13.1748892854320; Mon, 02 Jun 2025 12:34:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1748892854; cv=none; d=google.com; s=arc-20240605; b=BTr+LEsHbDGlK4d9ZdaMB22Ri7YUYBxIWdxl/tgfezoeOlYaKapVhjMQgGydOSs54y 1m8q6Ezl95kY7nYDSJ8fPsSgdyfFqFf9kHBrIVo60owhvtn+vr5DuCnv6fps40S7LOgC CejYSVU0QsazphqyTeABa7EopAKpwzYr3BuTctYj8gIppwyw+C9mrVHl9bCzr+rcB4lQ +TDxJ03cyZjc1QIi1KQ/7JA8UdCrGe0ZM7Kyf2rmXAYSIpJQWaiN2zSGkpzC1qAYfRJF jVpGEus4jz1earn8ZqaIbn30FA9DK/LdHcsJkIWqqqiG6qkZNwAuh7So6s6nVv9+5j2F 5oBg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=mime-version:feedback-id:references:in-reply-to:message-id:subject :cc:from:to:date:dkim-signature; bh=cw4k9sf/y7JEbklH8CJNeQyKKpCvY25HVj9MID/xosU=; fh=zwD6MnSx31+wTUYXvjlRY9wKEAVfUFCZok1hjFoWcUg=; b=Cm5Kipm/EYDmdfjnw9IqwH9U5tnARfHbB8hBs3v2itrKZ0beknn094ktt3Pz0fZ8uM 5d7RZSkSCxMmnGtCaZgI4pMHkp0VYTL9VnhGJEgw1RUd28X7EFPS/PMbBALWUZPJq1bt 6i59yz6yOudK2sO0ss8yT/GEU1tGmmppWxVLPSne4v0QQtLJVCnlGyxNtiMgRvF7GqXW MLOyYioDvLtDBP/lRm8P+34D1KC+JAQ0RiAMAwVeQBT8y51FM57IsT1GcXEtgYHcWse4 4wccoxYU5ctzfxAIF9Fni+xFvEJK48M6uQSRE+rsW94EEWu7CPYo0C+MV+cqwTpR8ycl ZK9Q==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=l8jjWqVi; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch. [185.70.43.22]) by gmr-mx.google.com with ESMTPS id ffacd0b85a97d-3a4f009456bsi333188f8f.8.2025.06.02.12.34.14 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 02 Jun 2025 12:34:14 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) client-ip=185.70.43.22; Date: Mon, 02 Jun 2025 19:34:09 +0000 To: waxwing/ AdamISZ From: "'conduition' via Bitcoin Development Mailing List" Cc: Bitcoin Development Mailing List Subject: Re: [bitcoindev] Post-Quantum commit / reveal Fawkescoin variant as a soft fork Message-ID: In-Reply-To: <402db6ba-2497-4aab-9f84-0d66b4b8efccn@googlegroups.com> References: <402db6ba-2497-4aab-9f84-0d66b4b8efccn@googlegroups.com> Feedback-ID: 72003692:user:proton X-Pm-Message-ID: 4abbb5a99de530735db6c8b6246c64ae5d28bdaa MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------a516181af16c70203e5c040e5d627d79d8e28aecb610309c0b462e3bf2fb01ac"; charset=utf-8 X-Original-Sender: conduition@proton.me X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=l8jjWqVi; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me X-Original-From: conduition Reply-To: conduition 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: -1.0 (-) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --------a516181af16c70203e5c040e5d627d79d8e28aecb610309c0b462e3bf2fb01ac Content-Type: multipart/mixed;boundary=---------------------248a9323a46e854f4e30924f652f1d17 -----------------------248a9323a46e854f4e30924f652f1d17 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" Hi list, One problem I see with Tadge's commit/reveal approach is that verifying nodes must have an ordering over ALL commitments, including those which haven't yet been opened. We need every commitment to be visible on-chain to know if a different commitment for the same pubkey was published=20 earlier. This prevents commitment aggregation, and it means we would need one OP_RETURN output to publish a commitment for every legacy UTXO rescued by Tadge's protocol. Let me demonstrate by trying to scale Tadge's proposal with aggregated commitments. For instance, instead of directly publishing C =3D (AID, SDP, CTXID) in an OP_RETURN, we might publish a merkle tree root which is derived from a list of such commitments. Nodes store all such merkle roots in a DB. When spending an EC UTXO, we reveal the pubkey along with a merkle proof for the commitment. The node computes the merkle root from the proof+pubkey+TXID, and then checks the database to verify the commitment is sufficiently old. This won't be secure though. The verifying nodes have no way of checking if this specific commitment was the FIRST valid commitment for the relevant pubkey/AID. There might be another commitment hidden in the same merkle tree, or in an earlier one. Maybe someone else has a better way to scale this commit/reveal protocol, but unless that's possible, I think Martin's idea [0] has better potential because we can rescue multiple EC outputs at once with a single quantum-resistant UTXO. As waxwing noted though, we need to better define the commitment protocol there, including whether to use a post-quantum taproot-like construction, or an inscription-like envelope with P2SH and a post-quantum checksig opcode. I'd suggest we move further discussion on that to the relevant thread [0]. [0]: https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/qN-pAMS7AgAJ I do recognize that Tadge's proposal has the advantage of not needing any quantum-resistant signing algos, which won't be available on BTC for a long time... but if we don't have a QR signing algo, then where are you even trying to move your coins to? I agree with waxwing that we should not pin down our PQ signing algo yet, but we should assume one will eventually be available. Otherwise why should we bother at all. regards, conduition On Monday, June 2nd, 2025 at 2:41 PM, waxwing/ AdamISZ = wrote: > Hi Boris, list, >=20 > > 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. >=20 > There's some nuances here that seem quite interesting. If an output commi= ts (in a quantum-resistant way, i.e. hashing let's say) only to a pubkey, a= nd not a pubkey plus spending-transaction, then, in the general case, that = has the weakness that the commitment can be replicated, in another commitme= nt tx, at the time of insertion of commitment into the blockchain; so that = if the tiebreaker is "first commitment in the block(chain)" an attacker can= mess with you. In your case you refer to "a QR output that commits to the = hash of a pubkey inside a taproot leaf" but I'm finding it a tiny bit uncle= ar what you mean there. Taproot itself isn't quantum resistant (QR), so Q = =3D P + H(P,S)G is not QR even if P is NUMS. Whereas you might mean: that s= ame system but with keypath spending invalidated, so it's QR because of the= hash function, but also, the tapleaf contains a QR or PQC signing scheme i= n it (I guess this is what you actually mean). Or, you might mean something= that is structurally the same as taproot but not using secp/BIP340, but in= stead a PQC scheme with a homomorphism so that that same design can be reus= ed; call that "taproot2" .. though I don't think I've heard people talking = about that. >=20 > Then there's what I think you focus on: the commitment is hidden. To othe= r readers, in case of confusion: I believe the *real* point here is not "no= body knows you committed something" though that may be practically signific= ant, it's instead "nobody knows the exact commitment value (hash) you used"= . >=20 > So, I believe that's a correct/valid point that actually *doesn't* depend= on which "version" of taproot as per above. Focusing on current-taproot-bu= t-script-path-only-with-QR-in-tapleaf: we have a protection that the quantu= m attacker cannot find the S in the (P,S) tuple (indeed, they cannot even k= now the H in P + H(P,S)G). This commitment is *not* literally perfectly hid= ing as in a properly formed Pedersen commitment ([1]) but I do think you ha= ve the normal preimage resistance against revelation as expected even in po= st-quantum. So that prevents the "copy the commitment" problem I started ou= t by mentioning. [2] >=20 > If "taproot2" instead then we have something for which even the keypath i= sn't crackable so I guess it's obvious. >=20 > > 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. >=20 > Again, I believe you're right here, but we should try to unpack what's di= fferent; because the "reveal" step of commit-reveal is accompanied by the Q= R signing event of the pre-existing QR output, we have a sane security mode= l, so there's no need to commit to the transaction in the preliminary step,= as far as I can tell. >=20 > > More efficient use of block space >=20 > Makes sense. >=20 > I think the only downside I see here is that the initial commitment step = requires the PQC scheme to actually exist. That may not seem like a big dea= l, but I have a suspicion it actually will be. I think a protocol in which = we just rely on existing hash primitives and put off the PQC scheme choosin= g event may be necessary .. though I could be for sure wrong, in more than = one way, in saying that. >=20 > Apart from that point I think this scheme seems good (as you mention, it = has the virtue of not requiring new databases etc which is pretty huge). >=20 > Cheers, > AdamISZ/waxwing >=20 > [1] In these analyses, I think it's common to overlook a potentially cruc= ial point: the utxo set is enumerable in practical time, so we must always = remember that we can check our calculations against existing addresses, eve= n if they are hash-covered keys. >=20 > [2] The only caveat is if you're considering the possibility of the attac= ker knowing the key in advance of even the commitment step; generally, that= 's "game over", but i know that there is some attempt to analyze that case = in some places, too. Not here. >=20 > On Wednesday, May 28, 2025 at 6:54:21=E2=80=AFPM UTC-3 Nagaev Boris wrote= : >=20 > > Hi Tadge, > >=20 > > Thanks for writing this up! The proposal is very thoughtful, and it's > > great to see concrete work on post-quantum commit/reveal schemes. > >=20 > > 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. > >=20 > > https://groups.google.com/g/bitcoindev/c/jr1QO95k6Uc/m/lsRHgIq_AAAJ > >=20 > > This approach has a few potential advantages: > >=20 > > 1. No need for nodes to track a new commitment store > >=20 > > 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. > >=20 > > 2. Commitment can be made before the transaction is known > >=20 > > 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. > >=20 > > 3. More efficient use of block space > >=20 > > 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. > >=20 > > 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. > >=20 > > Best, > > Boris > >=20 > > On Wed, May 28, 2025 at 2:28=E2=80=AFPM Tadge Dryja = wrote: > > > > > > One of the tricky things about securing Bitcoin against quantum compu= ters is: do you even need to? Maybe quantum computers that can break secp25= 6k1 keys will never exist, in which case we shouldn't waste our time. Or ma= ybe 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 t= iming would be if they do, it's hard to get consensus on changes to bitcoin= that disrupt the properties we use today. For example, a soft fork introdu= cing a post-quantum (PQ) signature scheme and at the same time disallowing = new secp256k1 based outputs would be great for strengthening Bitcoin agains= t an oncoming QC. But it would be awful if a QC never appears, or takes dec= ades 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 worki= ng after a QC shows up, even if we haven't defined a PQ signature scheme an= d everyone's still got P2WPKH outputs. > > > > > > Most of this is similar to Tim Ruffing's proposal from a few years ag= o here: > > > https://gnusha.org/pi/bitcoindev/1518710367.3...@mmci.uni-saarland.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 how i= t can be implemented in bitcoin nodes as a soft fork. > > > > > > This scheme only works for keys that are pubkey hashes (or script has= hes) 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 sp= ends would no longer be secure. > > > > > > What to do with all the keys that are known is another issue and inde= pendent 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. We a= lso assume the attacker has some mining power or influence over miners for = their attacks; maybe not reliably, but they can sometimes get a few blocks = in a row with the transactions they want. > > > > > > "Pubkey" can also be substituted with "script" for P2SH and P2WSH out= put 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= , for any transaction with an EC signature in it, that transaction's txid m= ust 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 whil= e, broadcast the transaction. Nodes would check that the txid matches a pre= viously 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 commitm= ent with a different txid for a transaction where the attacker gets all the= coins. If the attacker can get their commitment and spending transaction i= n 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 woul= d have to prevent the user's transaction from being confirmed for 100 block= s after it showed up in the attacker's mempool. The tradeoff is that longer= periods give better safety at the cost of more delay in spending. > > > > > > This scheme, while problematic, is better than nothing! But it's poss= ible 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 be= ing spent, and the txid that was going to spend it, we could add a "first s= een" consensus rule. Only the first commitment pointing to an outpoint work= s. > > > > > > So if nodes see two OP_RETURN commitments in their sequence of confir= med transactions: > > > > > > C1 =3D outpoint1, txid1 > > > C2 =3D outpoint1, txid2 > > > > > > They can ignore C2; C1 has already laid claim to outpoint1, and the t= ransaction identified by txid1 is the only transaction that can spend outpo= int1. > > > > > > If the user manages to get C1 confirmed first, this is great, and eli= minates the timing problem in the txid only scheme. But this introduces a d= ifferent 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 bit= s 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 i= nvalid commitment is one where there is no transaction described by the txi= d. A more general way to classify a commitment as invalid is a commitment m= ade without knowledge of the (secret) pubkey. Knowledge of the pubkey is wh= at security of coins is now hinging on. > > > > > > > > > The actual commitment scheme > > > > > > > > > We define some hash function h(). We'll use SHA256 for the hashing, b= ut 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 bi= tcoin output script, which instead is RIPEMD160(SHA256(pubkey)), or in bitc= oin terms, HASH160(pubkey). Due to the hash functions being different, A = =3D HASH160(pubkey) and B =3D h(pubkey) will be completely different, and n= obody 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 w= hich will be signed for, a proof of knowledge of the pubkey which commits t= o a transaction, and an the txid of the spending transaction. We'll call th= ese "address ID" (AID), sequence dependent proof (SDP), and the commitment = txid (CTXID). > > > > > > For those familiar with the proposal by Ruffing, the SDP has a simila= r function to the authenticated encryption part of the encrypted commitment= . Instead of using authenticated encryption, we can instead just use an HMA= C-style authentication alone, since the other data, the CTXID, is provided. > > > > > > When the user's wallet creates a transaction, they can feed that tran= saction into a commitment generator function which takes in a transaction, = extracts the pubkey from the tx, computes the 3 hashes, and returns the 3-h= ash commitment. Once this commitment is confirmed, the user broadcasts the = transaction. > > > > > > Nodes verify the commitment by using the same commitment generator fu= nction 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 mus= t store all of them. Once the AID's pubkey is known, the node can distingui= sh which commitments are valid, which are invalid, and which is the first s= een 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 cr= eates C1, committing to a different txid where they control the outputs, an= d confirms it first. This attacker may know the outpoint being spent, and m= ay 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 so= mething up for the SDP. > > > > > > The user gets C2 confirmed after C1. They then reveal tx2 in the memp= ool, 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 tha= t the SDP doesn't match the data in the transaction, so it's an invalid com= mitment. For tx3, they will see that it is valid, but by seeing tx3 they wi= ll also be able to determine that C2 is a valid commitment (since pubkey is= revealed in tx3) which came prior to C3, making C2 the only valid commitme= nt 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 a= ll (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 tran= saction, and look up if it matches an AID they have stored. If not, the tra= nsaction is dropped. If the AID does match, the node can now "clean out" an= AID entry, eliminating all but the first valid commitment, and marking tha= t AID as final. If the txid seen matches the remaining commitment, the tran= saction is valid; if not, the transaction is dropped. > > > > > > After the transaction is confirmed the AID entry can be deleted. Dele= ting the entries frees up space, and would allow another round to happen wi= th 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 des= troy coins rather than allow them to be stolen. That's a tradeoff, and I pe= rsonally 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. 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 sat= isfy 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 means = that either SHA256 preimage resistance is broken (which we're assuming isn'= t the case) or someone can create valid signatures for arbitrary elliptic c= urve 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 re= quirements 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 n= ew rules. > > > > > > Wallets not aware of the new rules, however, are very dangerous, as t= hey may try to broadcast signed transactions without any commitment. Nodes = that see such a transaction should drop the tx, and if possible tell the wa= llet that they are doing something which is now very dangerous! On the open= p2p network this is not really enforceable, but people submitting transact= ions 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 h= olding bitcoin, that in the face of a sudden QC, even with minimal preparat= ion 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 new= transaction and get their commitment in first on the new chain. This seems= unavoidable with commit/reveal schemes, and it's up to the user how long t= hey 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 a= ctivates, there's only one type of transaction that can reliably get the OP= _RETURN outputs confirmed: coinbase transactions. Getting commitments to th= e miners and paying them out of band is not great, but is possible and we s= ee this kind of activity today. Users wouldn't need to directly contact min= ers: anyone could aggregate commitments, create a large transaction with ma= ny OP_RETURN outputs, and then get a miner to commit to that parent transac= tion. Users don't need to worry about committing twice as identical commitm= ents would be a no op. > > > > > > - Spam > > > Anyone can make lots of OP_RETURN commitments which are just random n= umbers, 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 reall= y a problem, nodes could requiring the commitment outputs to have a non-0 a= mount 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 w= ill need to spend all the UTXOs at once. The commitment scheme can deal wit= h 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 k= nowing each others' unhashed pubkeys. This isn't how existing multisig outp= uts work, and in fact the current trend is the opposite with things like Mu= sig2, 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 sche= me. > > > > > > - 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 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 hi= gh fees in comparison to the old p2wpkh output types. It's possible that 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 pai= rs. 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, with a smaller commitment that can be done as a soft fork. I hope someth= ing 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 tak= e 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 Fawksc= oin 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 how= it could be done in a soft fork which doesn't look too bad to implement. > > > > > > I've also heard of some more complex schemes involving zero knowledge= proofs, proving things like BIP32 derivations, but I think this gives some= pretty good properties without needing anything other than good old SHA256= . > > > > > > Hope this is useful & wonder if people think something like this woul= d be a good idea. > > > > > > -Tadge > > > > > > -- > > > You received this message because you are subscribed to the Google Gr= oups "Bitcoin Development Mailing List" group. > > > To unsubscribe from this group and stop receiving emails from it, sen= d an email to bitcoindev+...@googlegroups.com. > > > To view this discussion visit https://groups.google.com/d/msgid/bitco= indev/cc2f8908-f6fa-45aa-93d7-6f926f9ba627n%40googlegroups.com. > >=20 > >=20 > >=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= email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/402db6ba-2497-4aab-9f84-0d66b4b8efccn%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/= G4RQ-XfZ50oMGil2qiIgdMQoYlZ_lPG7asIo2e0vyKGjfWBn6diRJXbjNqtUTEw1fSeux01_BxW= qUJpKhiP-i1q6EU_RawfqrFeUutkFDDY%3D%40proton.me. -----------------------248a9323a46e854f4e30924f652f1d17 Content-Type: application/pgp-keys; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4ak1FWkRub0tSWUpLd1lCQkFI YVJ3OEJBUWRBcnBZYWFjZDgwcXdocmNaQW9VbW9NSHNWS21iZWlPZUEKcFhXbk1ybFdPZkxOSzJO dmJtUjFhWFJwYjI1QWNISnZkRzl1TG0xbElEeGpiMjVrZFdsMGFXOXVRSEJ5CmIzUnZiaTV0WlQ3 Q2pBUVFGZ29BUGdXQ1pEbm9LUVFMQ1FjSUNaQjRLV3p0aFBhenhRTVZDQW9FRmdBQwpBUUlaQVFL YkF3SWVBUlloQkVkSWthMENNdHJMZGcxM2EzZ3BiTzJFOXJQRkFBQTZhQUVBM1RmNHdqSVoKYnox K0diS0h4K09WQytNUXlVdi84RStoWUpjTE5QZnA0NEFBLzNiak5OTXN4WHdJTGZEM0xManNVVWFo CitBV2JyblVjVUFqQ2R1d3hUT01LempnRVpEbm9LUklLS3dZQkJBR1hWUUVGQVFFSFFDSXYxZW5J MU5MbAo3Zm55RzlVWk1wQ3ZsdG5vc0JrTmhQUVZxT3BXL3RKSkF3RUlCOEo0QkJnV0NBQXFCWUpr T2VncENaQjQKS1d6dGhQYXp4UUtiREJZaEJFZElrYTBDTXRyTGRnMTNhM2dwYk8yRTlyUEZBQUFR TFFEL2NCR2kwUDdwCkZTTkl2N1B6OVpkeUNVQjhzTy90dWZkV3NjQkNZK2ZMYTV3QkFNK0hTL3Jp S014RGt0TkhLakRGc2EvUgpEVDFxUGNBYXZCaXc2dDZ4Ti9jRgo9Y3d5eAotLS0tLUVORCBQR1Ag UFVCTElDIEtFWSBCTE9DSy0tLS0tCg== -----------------------248a9323a46e854f4e30924f652f1d17-- --------a516181af16c70203e5c040e5d627d79d8e28aecb610309c0b462e3bf2fb01ac Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0Fgmg9/KEJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmeTsEW8oheCCQWGsl0ZDt+YYrdSJcKPYncTK+s8 O/h+qhYhBEdIka0CMtrLdg13a3gpbO2E9rPFAADBNAEA0qOeqc3NCAhMVWtS j5P/w4Vvx1DJufO572TIPCcI7OoBAIgjF5EKgliTlRqVtmqis812SzUs1AD3 dnlr31e37sEN =Wgkt -----END PGP SIGNATURE----- --------a516181af16c70203e5c040e5d627d79d8e28aecb610309c0b462e3bf2fb01ac--