From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 04 Jun 2025 11:40:40 -0700 Received: from mail-yb1-f187.google.com ([209.85.219.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uMt2U-00008a-Lq for bitcoindev@gnusha.org; Wed, 04 Jun 2025 11:40:39 -0700 Received: by mail-yb1-f187.google.com with SMTP id 3f1490d57ef6-e7d971b6398sf240966276.2 for ; Wed, 04 Jun 2025 11:40:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1749062433; x=1749667233; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=+Z5rawu53vjeV7Fx33sVG4S4wMKcjNsa31Bh4KTHCaQ=; b=df/23Jf6PoXhGw766Gmab7E9gD5anyRG1F3whhSmML/hY8BOOQnKSNjFC/eR/fIYcx vFqJmRyMWeFdH9jfbiAHjzJsScKrKuGuBE2TqA98QB2jutd2Sxqb5Rt//wdSGt3G+FOm KMtdEAW2NUMpfwDJz1FV5nYS3TtKlp4MoKmMVUpccwtuv9TcVEGv3ke4Uut9tDIRJiDm hkK2b2J82S8cFasVbi3MDYF7RuRkJ9J3ogxWcJLe8Xtrq9UHh4DUqKRYjG8TULk0qDJL qwEWNs/zSz8gvUtGLgs+Q8YIkvHrp/o4DctqDrEiaDBA0wQkqmqMgJSFVOg3yNtUCaUm Pi6Q== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749062433; x=1749667233; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=+Z5rawu53vjeV7Fx33sVG4S4wMKcjNsa31Bh4KTHCaQ=; b=E4QhQDLsOwNnMewbYTYziQyB/qqWAbjtHHgAK3lPCGplFUUD/my4za0Yyk4lI9S8dD QJFY5UEfy49BJHfzPhgXGcSXWLYqY3uHbDFQZZdqcYwdL8232osnayCkcaIliykKdCDu Npo7+uU8VXwGi1fYuqb7LcyHqbMgF8TfWZV1TuEKAXbkpJeU33CcJGhdJitmD7YBHxsT YU3aGK9D2+xTX5wieNM8ITmVJko/bU4LO1s+NxVNmqpyCaTLGdAuS2epBWNhBRVZLqqT bgE8DYrrX+N5ipCH+jgLUBwu46ldp5heDbRj2pgGWsabmDNxDni/x4KvXr0tvRqC8ka+ 3X+w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749062433; x=1749667233; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=+Z5rawu53vjeV7Fx33sVG4S4wMKcjNsa31Bh4KTHCaQ=; b=AzQTsAeVnIc7ukc6jEFHCheeoO2KuIeOGfjf/TR9ViJ0y7616w6Ezy9s7jSet7fymx NM154lbQxHR9V1O/9PBwwJa0TbPQt+xyB6Bwo7MAhx8tPXK5Rl/kv2s3NO2/CcfpuawT mKl3EsqO8ERKR2UKLiI6yEAi9X6LSMwdLlbAvyjHVrz/HYeaYI1AOGWxLoJHpIm0REV+ QvN3zpDO+W/RaQnoxADcnpFHGbbWzyvFkfw/S+DE3tWqSayhoNBUfKE369AGZRkXHG/C 4PZJrFeR/qWRPmFWEICNV7tZHQIm+MpoLPhoedQ/ID6weHDih3piT1wHjpbL/B/77iEH E4/Q== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCW7vOyIg7zLC9e7X/KmtnO0lUE6NGgCL/KTWqV3/++vB4Fz5MFxBgLL533bg96rp3hC6PbDkwOzqStY@gnusha.org X-Gm-Message-State: AOJu0Yw9Vd8DyBigREPknw0lANd62FbYi2c1vz6h9ty8dK34rbW09Ewx QBJ1o6/zyIKoy6tC/Tp8i4E5cnnz8obuxzhGZWLXkgT86eGk2IXt2UOq X-Google-Smtp-Source: AGHT+IH1jVYjureISzzW1bzpOa/K3+BP5X5eUvUcPPiDWsNKpZ/DnMAyZnsOVO8O2JFu9fYdYqwKkA== X-Received: by 2002:a05:6902:1549:b0:e81:78f7:5521 with SMTP id 3f1490d57ef6-e8179c3b5bcmr5231815276.6.1749062432615; Wed, 04 Jun 2025 11:40:32 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcaf7KWKP7nGOJaR48LpeYTwqKYUEsjBCkGZmJS2Y0lzA== Received: by 2002:a25:3f83:0:b0:e7d:cab1:1366 with SMTP id 3f1490d57ef6-e8188a1ac8fls89624276.1.-pod-prod-08-us; Wed, 04 Jun 2025 11:40:29 -0700 (PDT) X-Received: by 2002:a05:690c:688b:b0:70e:1ef7:6f21 with SMTP id 00721157ae682-710d99fd5c5mr54522237b3.5.1749062429062; Wed, 04 Jun 2025 11:40:29 -0700 (PDT) Received: by 2002:a05:690c:243:b0:70e:2cf8:9db8 with SMTP id 00721157ae682-710d716ada7ms7b3; Wed, 4 Jun 2025 11:38:20 -0700 (PDT) X-Received: by 2002:a05:690c:4c05:b0:70c:c013:f26 with SMTP id 00721157ae682-710d9e16ca8mr49153177b3.33.1749062299633; Wed, 04 Jun 2025 11:38:19 -0700 (PDT) Date: Wed, 4 Jun 2025 11:38:19 -0700 (PDT) From: Boris Nagaev To: Bitcoin Development Mailing List Message-Id: <44b5aa4c-a71b-49ed-beee-071140b16aacn@googlegroups.com> In-Reply-To: <5d9f6ac9-a623-4636-8a91-ee7c057bc08an@googlegroups.com> References: <2c3b7e1c-95dd-4773-a88f-f2cdb37acf4a@gmail.com> <33f67e84-5d1c-4c14-80b9-90a3fec3cb36@gmail.com> <5e393f57-ac87-40fd-93ef-e1006accdb55n@googlegroups.com> <5d9f6ac9-a623-4636-8a91-ee7c057bc08an@googlegroups.com> Subject: Re: [bitcoindev] Pre-emptive commit/reveal for quantum-safe migration (poison-pill) MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_100894_1909946159.1749062299138" X-Original-Sender: bnagaev@gmail.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 (/) ------=_Part_100894_1909946159.1749062299138 Content-Type: multipart/alternative; boundary="----=_Part_100895_252217700.1749062299138" ------=_Part_100895_252217700.1749062299138 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Leo, I think it is possible to provide privacy for Satoshi and also reduce the= =20 size of a weak announcement (strong announcements can already be small:=20 just a txid or a Merkle root of many txids). Importantly, we cannot include the whole signed transaction in the weak=20 announcement. Doing so would leak the EC public key immediately, allowing= =20 an attacker to create their own valid weak announcement. We must avoid=20 revealing the public key until the actual spending transaction is broadcast= . We need a scheme where the EC public key is not leaked in a weak=20 announcement, but the legitimate owner can verify it, while no one else=20 can. Also, once the EC public key is revealed, anyone should be able to=20 verify a past weak announcement (to validate the transaction when it is=20 broadcast). This reduces to the following requirement: we need a proof of= =20 knowledge of the EC public key that can be verified if the public key is=20 known and provides no information otherwise. I think this is called a zero-knowledge proof. One simple approach could be= =20 to apply a tagged hash function to the concatenation of the EC public key= =20 and the future wTXID, and include this in the weak announcement. The=20 structure would be: - UTXO (previous TXID and output index) - future spending wTXID - proof :=3D tagged_hash(EC public key || wTXID) The wTXID is included in the concatenation to bind the proof to a=20 particular future transaction. Otherwise, someone could copy a weak=20 announcement and substitute their own wTXID. Satoshi could publish a strong announcement now and then monitor all weak= =20 announcements involving his UTXOs. If someone publishes a weak announcement= =20 for one of his coins, he could verify the "proof" field. If it is valid, it= =20 would mean someone has cracked his key with a quantum computer, and he=20 would need to use his strong announcement immediately to reclaim the funds= =20 before the attacker does. Best, Boris On Wednesday, June 4, 2025 at 2:40:53=E2=80=AFPM UTC-3 Leo Wandersleb wrote= : Hi Boris, the announcements, weak and strong would have to not be transactions yet to= =20 be compatible with legacy nodes and thus keep it a soft-fork. They could be= =20 OP_RETURN data. Only after the 144 blocks, the upgraded full nodes would=20 allow the inclusion of the actual transaction. This would mean the=20 transaction would be both in full in the OP_RETURN strong announcement and= =20 without the witness part later, so it would be a bit expensive this way but= =20 maybe we can do better? A node that gets updated would have to re-index all the blockchain to find= =20 announcements if we don't introduce a time frame for actually using the=20 announcements. We could also say that any announcement has to be used=20 within another 1000 blocks. Then the upgrading node would have to re-index= =20 the last 1000 blocks. The legitimate owner of a UTXO might wait for an attack for privacy=20 reasons. My proposal would allow Satoshi himself to make all his UTXOs=20 quantum safe without any of us learning about him being active. He could=20 add one 64B OP_RETURN in 2027 and when QC becomes an issue, we would learn= =20 about him having been active in 2027 in 2040 when actually somebody tried= =20 to attack and not in 2027 when people started to panic because of imminent= =20 quantum breakthroughs. Hmm ... a problem is the weak announcement doesn't require keys, so anybody= =20 could provoke Satoshi to come forward. Maybe we have to add key ownership= =20 as a requirement for the "weak" announcement, too. So it should also=20 contain a serialized transaction. Best, Leo On Wednesday, 4 June 2025 at 04:15:59 UTC+2 Nagaev Boris wrote: Hi Leo,=20 Thanks for the clarifications, much appreciated!=20 I have a couple of questions:=20 1. How is a weak announcement stored in the blockchain and in the UTXO set?= =20 I assume it must be a transaction, correct? And it should somehow mark=20 the UTXO as planned to be spent for 144 blocks?=20 How would older (non-upgraded) nodes interpret a transaction=20 containing a weak announcement? Would they just skip over it without=20 any special processing?=20 If so, is there a problem for nodes that upgrade after the fork: would=20 they have to reprocess all blocks since the fork to find and index all=20 missed weak announcements?=20 2. In the case of reclaiming a UTXO after a weak announcement by an=20 attacker: why would the legitimate owner wait for a weak announcement=20 at all?=20 If the EC public key was already leaked, it seems they should publish=20 a strong announcement themselves rather than wait. If the EC public=20 key wasn't leaked, there's nothing to worry about even if someone=20 publishes a weak announcement: they are most likely bluffing, since=20 they wouldn't have the actual public key.=20 Best,=20 Boris=20 On Tue, Jun 3, 2025 at 3:29=E2=80=AFPM Leo Wandersleb = wrote:=20 >=20 > Hi conduition,=20 >=20 > Thanks for your careful analysis - excellent catches.=20 >=20 > You're absolutely right about the txid vulnerability. The commitment must= =20 be to the complete transaction including witness data (wTXID or equivalent)= =20 to prevent an attacker from pre-committing to unsigned transactions. This= =20 is essential - otherwise an attacker could indeed enumerate the UTXO set=20 and create commitments without knowing the private keys.=20 >=20 > Regarding updates: You're correct that frequent updates would be needed= =20 as wallets receive new UTXOs. However, I don't see this as a major issue -= =20 users could batch their commitments periodically (say, monthly) rather than= =20 after every transaction. The scheme is particularly important for existing= =20 UTXOs that already have exposed pubkeys (old P2PK, reused addresses, etc.).= =20 For new UTXOs, wallets should ideally migrate to quantum-safe addresses=20 once available. OpenTimestamps aggregation would indeed help with scaling= =20 and provide plausible deniability about the number of UTXOs being=20 protected.=20 >=20 > The time delay serves a different purpose than you might expect. It's not= =20 about preventing commitment forgery after pubkey exposure, but rather about= =20 allowing priority based on commitment age when multiple parties claim the= =20 same UTXO:=20 >=20 > 1. Weak announcement starts the 144-block window=20 > 2. During this window, anyone with a strong commitment can reveal it=20 > 3. The oldest valid commitment wins=20 >=20 > This creates the "poison pill" effect: an attacker might crack a key and= =20 try to spend a UTXO, but if the original owner has an older commitment,=20 they can reclaim it during the window. The uncertainty about which UTXOs=20 have poison pills makes attacking large "lost" UTXOs risky - hence less=20 disruptive to the network.=20 >=20 > The delay essentially allows a "commitment priority contest" where age=20 determines the winner, protecting users who prepared early while still=20 allowing these users to not move their funds.=20 >=20 > Best,=20 >=20 > Leo=20 >=20 > --=20 > You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group.=20 > To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com.=20 > To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/5e393f57-ac87-40fd-93ef-e1006a= ccdb55n%40googlegroups.com.=20 --=20 Best regards,=20 Boris Nagaev=20 --=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/= 44b5aa4c-a71b-49ed-beee-071140b16aacn%40googlegroups.com. ------=_Part_100895_252217700.1749062299138 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Leo,

I think it is possible to provide privacy for Satoshi an= d also reduce the size of a weak announcement (strong announcements can alr= eady be small: just a txid or a Merkle root of many txids).

Importantly, we cannot include the whole signed transaction in = the weak announcement. Doing so would leak the EC public key immediately, a= llowing an attacker to create their own valid weak announcement. We must av= oid revealing the public key until the actual spending transaction is broad= cast.

We need a scheme where the EC public key is not= leaked in a weak announcement, but the legitimate owner can verify it, whi= le no one else can. Also, once the EC public key is revealed, anyone should= be able to verify a past weak announcement (to validate the transaction wh= en it is broadcast). This reduces to the following requirement: we need a p= roof of knowledge of the EC public key that can be verified if the public k= ey is known and provides no information otherwise.

I think this = is called a zero-knowledge proof. One simple approach could be to apply a t= agged hash function to the concatenation of the EC public key and the futur= e wTXID, and include this in the weak announcement. The structure would be:=
  • =C2=A0 =C2=A0 UTXO (previous TXID and output index)
  • = =C2=A0 =C2=A0 future spending wTXID
  • =C2=A0 =C2=A0 proof :=3D tagged= _hash(EC public key || wTXID)
The wTXID is included in the concate= nation to bind the proof to a particular future transaction. Otherwise, som= eone could copy a weak announcement and substitute their own wTXID.
Satoshi could publish a strong announcement now and then monitor all we= ak announcements involving his UTXOs. If someone publishes a weak announcem= ent for one of his coins, he could verify the "proof" field. If it is valid= , it would mean someone has cracked his key with a quantum computer, and he= would need to use his strong announcement immediately to reclaim the funds= before the attacker does.

Best,
Boris

On Wednesday, June 4, 2025 at 2:40:53=E2=80=AFPM UTC-3 Leo Wa= ndersleb wrote:
Hi Boris,
the announcements, weak and strong would have to not be = transactions yet to be compatible with legacy nodes and thus keep it a soft= -fork. They could be OP_RETURN data. Only after the 144 blocks, the upgrade= d full nodes would allow the inclusion of the actual transaction. This woul= d mean the transaction would be both in full in the OP_RETURN strong announ= cement and without the witness part later, so it would be a bit expensive t= his way but maybe we can do better?

A node that = gets updated would have to re-index all the blockchain to find announcement= s if we don't introduce a time frame for actually using the announcements. = We could also say that any announcement has to be used within another 1000 = blocks. Then the upgrading node would have to re-index the last 1000 blocks= .

The legitimate owner of a UTXO might wait for = an attack for privacy reasons. My proposal would allow Satoshi himself to m= ake all his UTXOs quantum safe without any of us learning about him being a= ctive. He could add one 64B OP_RETURN in 2027 and when QC becomes an issue,= we would learn about him having been active in 2027 in 2040 when actually = somebody tried to attack and not in 2027 when people started to panic becau= se of imminent quantum breakthroughs.
Hmm ... a problem is the we= ak announcement doesn't require keys, so anybody could provoke Satoshi to c= ome forward. Maybe we have to add key ownership as a requirement for the "w= eak" announcement, too. So it should also contain a serialized transaction.=

Best,

Leo

On Wednesday, 4 June 2025 at 04:15= :59 UTC+2 Nagaev Boris wrote:
lwand...@gmail.com> wrote:
>
> Hi conduition,
>
> Thanks for your careful analysis - excellent catches.
>
> You're absolutely right about the txid vulnerability. The commit= ment must be to the complete transaction including witness data (wTXID or e= quivalent) to prevent an attacker from pre-committing to unsigned transacti= ons. This is essential - otherwise an attacker could indeed enumerate the U= TXO set and create commitments without knowing the private keys.
>
> Regarding updates: You're correct that frequent updates would be= needed as wallets receive new UTXOs. However, I don't see this as a major = issue - users could batch their commitments periodically (say, monthly) rat= her than after every transaction. The scheme is particularly important for = existing UTXOs that already have exposed pubkeys (old P2PK, reused addresse= s, etc.). For new UTXOs, wallets should ideally migrate to quantum-safe add= resses once available. OpenTimestamps aggregation would indeed help with sc= aling and provide plausible deniability about the number of UTXOs being pro= tected.
>
> The time delay serves a different purpose than you might expect.= It's not about preventing commitment forgery after pubkey exposure, but ra= ther about allowing priority based on commitment age when multiple parties = claim the same UTXO:
>
> 1. Weak announcement starts the 144-block window
> 2. During this window, anyone with a strong commitment can revea= l it
> 3. The oldest valid commitment wins
>
> This creates the "poison pill" effect: an attacker might crack a= key and try to spend a UTXO, but if the original owner has an older commit= ment, they can reclaim it during the window. The uncertainty about which UT= XOs have poison pills makes attacking large "lost" UTXOs risky - hence less= disruptive to the network.
>
> The delay essentially allows a "commitment priority contest" whe= re age determines the winner, protecting users who prepared early while sti= ll allowing these users to not move their funds.
>
> Best,
>
> Leo
>
> --
> You received this message because you are subscribed to the Goog= le Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it= , send an email to bitcoindev+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/b= itcoindev/5e393f57-ac87-40fd-93ef-e1006accdb55n%40googlegroups.com.



--=20
Best regards,
Boris Nagaev

--
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/bitcoind= ev/44b5aa4c-a71b-49ed-beee-071140b16aacn%40googlegroups.com.
------=_Part_100895_252217700.1749062299138-- ------=_Part_100894_1909946159.1749062299138--