From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 17 Apr 2026 10:56:47 -0700 Received: from mail-oo1-f57.google.com ([209.85.161.57]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wDnQo-00016X-Ft for bitcoindev@gnusha.org; Fri, 17 Apr 2026 10:56:47 -0700 Received: by mail-oo1-f57.google.com with SMTP id 006d021491bc7-688b73cc616sf744154eaf.0 for ; Fri, 17 Apr 2026 10:56:42 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1776448596; cv=pass; d=google.com; s=arc-20240605; b=T++yOX1NAOvRgKa0qvqSgfgFktOX/zy+HlHaILi40kdqZh4ya+618OkLygGvKYeNo+ nHbh67rA9j7j0t8d37HPQ5S354uD/mNeju+mVhQ/lG0NpJNeeosqcrV76yTEV2nxI4Ki CQ8fMWCo/3Z1y4dU+GAVQsPil+UdTzmqb37DUPnAD8w8r1YKHcosKts0KRrGJF2CnOzt 1SSJqEY1RpGxnje//fMzfifETaeRSE0mNZXl+mi9akQ4mXU7mNK+PvyXpwhBTwlAw+0K /S9wpI9k6z9jQ30k404ju9oacmoKHEJcenE0ulxtGAbiHOGf/KbCXaDfHXB8UXK95uZM Sviw== 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=cC91jidAJUitOgdLK2b/Wanx7sqXWIxZJhuXqfYgwAg=; fh=F9YOIXydhtozIGHdgKtgXjauHGeWWP5ClzI55RULI/g=; b=ACdF/bs+tyLrZfCSYZUx9AtqSabNSQ03G0NeZRNtnFIR4yNQQwwL7NJ+odqX9e9ulk DKWjf7FohvZJM3ujiqSEb5I0NeOD9D3WGtraT5Nj6h0HgyNmn3M4z3iCZLuUL7v2WvuX yjeQNeFWwwOe4elgh1GINtVq4WSvkB4iru1zdhm5SPu/ShnzSeRmUlKsmnDQ1Q2ZkWvV 0MSYMz13/5eddajoX+UjQ2tZ+KLVDl6iPZGkFyVfliUKPCtCBX/Sr4dizkSjqOGuLMbu mPnr0RFm0cSU+hGT0+zmw6lxKcTskJ/8m1pa5LdO1lQ2v+0UrSXqx7RHur9hWUZf00KA K2uw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=k4CMw6LW; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.101 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=20251104; t=1776448596; x=1777053396; 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=cC91jidAJUitOgdLK2b/Wanx7sqXWIxZJhuXqfYgwAg=; b=w2otQQBJeR79C30eDIJajkpHOnLBBsIEWjn1qtTR4YyXnPpio6YP5rxhNOp266Qr9n RZObd7OKcR2GAMaAMyZBC0zOw7pwDHnR78LNSnk4reVz0sOixEn1v2y+fApsU8DRlrWV dWhZy4AwRKy/JTov9yFR+J13bpCg7HSQX5XyAWxI83Oeq/uwNeQYy3aYCIhzlRSuO6WT vc0qR2v4wROfIMXz0q7HLP5zdvs5gcIJdlS6k6HxPXDPw2CtLphOe7VoKjMfkvtNdQKT WWaMRJKUsgVruh/6frXJwteFYq7fgVbhdopx8ixyhEU7dRLG4JeGX9ZewcHHTsoRo7Ro QZRQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1776448596; x=1777053396; 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=cC91jidAJUitOgdLK2b/Wanx7sqXWIxZJhuXqfYgwAg=; b=VNbBIvPWidjfwTCSAAsmMdGqZoG0sMZDvonvGhx02PVtaaino8FGdG3+tQR/yjtfwp 0wUCaemjAfmvfet0KeEoeXLFxjpr4FGuvunXAqtYKPWTpesM1j0svLGz6l2V0J5qDFSW ygAt8j5nXGPzYaUAi9FGvmLBw5+F0w0GyZZ1wDwRc6ZMaeNmj4rvmDftrLRC8r0ygDsM HYh9Cr/Bwylw2uMcXqQH4TGFmvQv5NdnfYzk5ghNQlTtEZ4Fh0QFpZUn8M1VMNfK8Jzs n97B32+e1Wi2nYDj584IZ0dgZ2aYeVezCn2inJiB8QhZYpzLvvjF9BueTaLlhM6M44a3 lQ0Q== X-Forwarded-Encrypted: i=2; AFNElJ+4DDIP+6c0yrA7TloWQHvScKXjobBgHMv7CFNxAdJknDcP3DFO/4+VMxEabi2vLpVXVvYaNPftWWjr@gnusha.org X-Gm-Message-State: AOJu0YwgWgfMXdEAsQEoofQdzntCY3JnSWk7tBR8Ci9ZcpJSS4rM+tLo PTsmgRzFJ3oAChlCHWsaQtckNa2WPnbKSZ92YAL6OG6uwxCXRIUlo5WZ X-Received: by 2002:a05:6820:210e:b0:67d:f53c:9ede with SMTP id 006d021491bc7-69462f5600bmr2147518eaf.60.1776448595973; Fri, 17 Apr 2026 10:56:35 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiL4eHgmnz8E4IFc7n5wbBeWL67a6Wwkk/j+rWwpMKVrKQ==" Received: by 2002:a05:6820:16aa:b0:67d:f8ba:e4b7 with SMTP id 006d021491bc7-6943d3a40c2ls1170795eaf.2.-pod-prod-04-us; Fri, 17 Apr 2026 10:56:31 -0700 (PDT) X-Received: by 2002:a05:6808:1496:b0:469:fc2a:d42 with SMTP id 5614622812f47-4799cb33253mr1982565b6e.44.1776448591213; Fri, 17 Apr 2026 10:56:31 -0700 (PDT) Received: by 2002:a05:600c:1c20:b0:488:965a:b7a8 with SMTP id 5b1f17b1804b1-488fbcf6c7fms5e9; Fri, 17 Apr 2026 09:43:45 -0700 (PDT) X-Received: by 2002:a05:600c:4515:b0:488:a4d6:69ad with SMTP id 5b1f17b1804b1-488fb790b84mr54528935e9.27.1776444223444; Fri, 17 Apr 2026 09:43:43 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1776444223; cv=none; d=google.com; s=arc-20240605; b=S3UuqP6/1yKu84Lb9Bq6loCB9SQ5TjiXu1Y9um2pdDeudcA1sepln+597FXPeVe7XH DLyendHb7/0O9Ti18Xvf/KpXn8u69thjpsTJnwX83lZmu7omFgLWbI9iwFI7vxLUr5WD WJ082CoP/rBBSMH5snK6YQHM4/Xjuw9I5i97+CVSx8eiCP8UYMDRT1OWR6WmZNap4Ef9 C8ZjkqrRW3KdirzGcsH12//4AE1UDh9O6gsB4Fyq1oaic5VyJeHOKrpsTan+RKMZNo4X NOe4/VEVVCfAKTb7pvLV53uOMAUfn8DpgXDBbW4woCYD7ZOcxzSyC3VU/i1XaFuUVEF7 b46g== 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=pd0QNLGILbUsEhr8F5FxrWIpo6BZzbrxc1xxaDmU3D8=; fh=6b1pLcW6tcZ6I7AhOCDpUTdU/HBZRb+DjIxd1ga4+Sc=; b=X3mWEG1YfYLXouSqH5dGOkFxjBfSSY3XbLHelkgeROPc2yxnOhcXy943/1TvyLlFjI C9YOAq8wHMNMWdiJ6ighGU3Cors/gyS+jbHfkjq2ixB0a/TXFoiCKUhpM9R8U5OEj+NK t5E6VG1llX3Mf4wZDbgS7vhebxbFZJxZjkoZVSHhD8XK3SEIYU5QAgqEDL3fUeqWOeuF +4KaxwRHdiqzuaW5zgFwcS2OxEGFZk7rcFMPFH3ESQpnJllGf0LxJn7AlTqaWniZXzWM /WGGWwdp8jEznuQYlOfTooDlUfNjnaiT7O98OnHQ6YZ+rctb3V94ZDuuI7dg+o8W7kPg qpwA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=k4CMw6LW; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.101 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-106101.protonmail.ch (mail-106101.protonmail.ch. [79.135.106.101]) by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-488fb77bdb8si177585e9.3.2026.04.17.09.43.42 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 17 Apr 2026 09:43:43 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 79.135.106.101 as permitted sender) client-ip=79.135.106.101; Date: Fri, 17 Apr 2026 16:43:33 +0000 To: Boris Nagaev From: "'conduition' via Bitcoin Development Mailing List" Cc: Bitcoin Development Mailing List Subject: Re: [bitcoindev] Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge Message-ID: In-Reply-To: <2482176b-1ad7-4216-b1e7-2c03265425een@googlegroups.com> References: <02378fd1-17a4-47aa-89fa-ee87626def65n@googlegroups.com> <2482176b-1ad7-4216-b1e7-2c03265425een@googlegroups.com> Feedback-ID: 72003692:user:proton X-Pm-Message-ID: 5dd66d75f2ac41998447c094e1ab15d89aef04f9 MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------1c8c98f29fc9c5b22be7584a0f0687b05ddf0da81877e967ed88fbf615138a5d"; 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=k4CMw6LW; spf=pass (google.com: domain of conduition@proton.me designates 79.135.106.101 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.5 (+) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --------1c8c98f29fc9c5b22be7584a0f0687b05ddf0da81877e967ed88fbf615138a5d Content-Type: multipart/mixed;boundary=---------------------99421436611be78833abedda48d60b49 -----------------------99421436611be78833abedda48d60b49 Content-Type: multipart/alternative;boundary=---------------------3061c550b94548b7fb54191d629abdaf -----------------------3061c550b94548b7fb54191d629abdaf Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" Hey Boris, good to hear from you! Great questions. I think MuSig2 might actually be possible to rescue even without BIP32, sin= ce the MuSig2 key aggregation scheme is a one-way function which a CRQC can= not reverse. So you don't even need a BIP32 proof to rescue it, technically= , though as we'll see BIP32 is still desirable if we can use it. A MuSig2 key is kind of like a hashed address. If EC spending is disabled, = then you just need to prove knowledge of the secret keys which reproduce th= e address.=C2=A0 Example aggregation of a MuSig2 key `X` using two peer pubkeys A and B: A =3D a * G B =3D b * G `X =3D A * int(H(A, A || B)) + B * int(H(B, A || B))` If you can prove knowledge of `a` and `b`=C2=A0in a way that also commits t= hat proof to a spending transaction, then you can spend `X` but a CRQC cann= ot. For example: 1. With a ZK-STARK, the MuSig peers could cooperate to prove they know a co= rrect `(a, b)` pair which produce pubkeys `(A, B)` such that: `x =3D a * int(H(A, A || B)) + b * int(H(B, A || B))` ...where the group secret key=C2=A0`x` is written to the public output of t= he proof. A verifier could then recompute `X =3D x * G` outside the circuit= to validate a spend. Creating this proof demands we arithmetize two curve = point multiplications and two hash function invocations, i.e. one mult and = one hash per MuSig2 participant. Another downside is this=C2=A0would requir= e participants to trust each other and share private keys (or use MPC to bu= ild the proof). 2. Alternatively, we can sacrifice performance to reduce trust. Prove you k= now a correct set of pubkeys=C2=A0`(A, B)`=C2=A0such that they recompute `X= ` using MuSig key aggregation, and then prove you know a BIP340 signature f= rom=C2=A0`X` on a given transaction. This is similar to what=C2=A0Kurbatov = did in this recent post exploring STARKs for rescuing hashed addresses=C2= =A0without the need to export secret keys from secure signing devices. This= approach would let you prove a similar statement without=C2=A0the need to = share privkeys between peers, at the cost of one extra point multiplication= and an extra hash invocation - These are needed to verify a Schnorr signat= ure in the circuit. Both proofs are hard for an external QC to forge without knowing `A` and `B= `, and neither can be forged by non-quantum peers in the MuSig group. Thoug= h, if there is a quantum adversary in the MuSig group, the group is screwed= in either case. It'll still be very expensive to generate either proof, an= d circuit complexity will scale linearly with the number of MuSig2 signers.= I think commit/reveal would be a better choice in this situation. But... if the MuSig2 peer pubkeys `A` and `B` were derived using a hardened= BIP32 step or some other hash-based algorithm though, then we could reuse = Laolu's techniques to create a BIP32 proof which is secure even against Qua= ntum attackers inside the MuSig group.=C2=A0 Peers could provide one BIP32 xpriv proof showing hardened derivation for e= ach contributory secret key `a` and `b`, and then let the verifier recomput= e `A, B`=C2=A0and `X` in software. The resulting circuit would be much fast= er and more efficient, because you only need to arithmetize one HMAC call p= er peer; no point multiplication needed. A quantum attacker in the MuSig gr= oup cannot forge any of their peers' proofs either, since they do not know = the preimages their peers used to generate their keys. Though you'd need on= e separate proof for every signer in the MuSig group, so it'd probably be w= ise to aggregate the proofs together, especially for larger groups. ------------ As for FROST, I think that will be a harder problem. It depends on how the = threshold master key was constructed: Trusted dealer, or distributed keygen= (DKG). With a trusted dealer, then it depends how the dealer generated the master = key.=C2=A0If the dealer used BIP32 and still have the seed, then peers coul= d ask the dealer to follow Laolu's techniques. If the dealer discarded the = seed or if they didn't use some quantum-hard function on a (remembered) sec= ret input to generate the key, then I think hope is lost. If the FROST key was generated using a DKG protocol, then unfortunately I d= on't think there is any quantum-hard asymmetry we can rely on there at all.= FROST DKG doesn't use hash functions, it is all algebraic. A valid DKG exe= cution for any secp256k1 point=C2=A0can be easily simulated by a quantum at= tacker, since they can compute the FROST group secret key and then break it= up into valid DKG shares. It would maybe=C2=A0be possible to rescue if ALL= the DKG participants generate their shares using a deterministic hash of s= ecret input, because that'd be impossible for a QC to simulate and forge. B= ut IDK of any FROST implementations which do it that way. regards, conduition On Wednesday, April 15th, 2026 at 3:35 PM, Boris Nagaev = wrote: > Hi Laolu, Abubakar, Conduition, list, >=20 > Does this idea extend to MuSig2 or FROST outputs, assuming the relevant p= arties cooperate during proving (or use some MPC) and collectively know the= underlying seeds / secret material? >=20 > For MuSig2, I can imagine a proof that each participant key came from a B= IP32 seed/path. > For FROST, I am less sure what the analogous proof statement would be. >=20 > At least to me, MuSig2 seems like it may be within reach. I would be very= interested if someone has a concrete sketch in mind. >=20 > Best, > Boris >=20 > On Tuesday, April 14, 2026 at 10:54:51=E2=80=AFAM UTC-5 conduition wrote: >=20 > > Hi Abubakar, > >=20 > > Awesome point! A single STARK could be used to prove you knew an xpriv = which derives the xpriv at m/352'/coin'/account'. Then any verifier could e= asily derive the private scan/spend keys m/352'/coin'/account'/0'/0 or m/35= 2'/coin'/account'/1'/0, then replicate the ECDH process (with some BIP352-s= pecific tweaks that the spender can provide), and add the result together. = This reproduces the private key of the SP taproot output being spent, provi= ng the spender is authentic. > >=20 > > With proper labeling of input metadata, this procedure could cover ever= y UTXO in a silent payment wallet, because the scan/spend keys are common t= o every derived output-specific address. > >=20 > >=20 > > > Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BI= P-32 still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2= =80=94 as long as the pubkey has never previously appeared on-chain. A zk-S= TARK proof should apply here too? The prover argues for the correctness of = HASH160(k=C2=B7G) =3D h, where k is the private key scalar and k=C2=B7G is = the elliptic-curve point, without ever revealing k or the pubkey. This woul= d allow recovery of a broader set of funds. > >=20 > >=20 > >=20 > > I agree this type of thing would also be useful, but it is harder to ar= gue security for this than for BIP32 xpriv ownership. > >=20 > >=20 > > Typically, xpubs and xprivs are not shared on-chain, and wallets usuall= y treat them with greater care since xpubs compromise privacy, and xprivs c= ompromise security. > >=20 > >=20 > > Hashed address pubkeys on the other hand are commonly shared on-chain a= nd almost never treated as sensitive. So it seems likely that if we DO perm= it spending using a ZK proof of knowledge of k such that HASH160(k*G) =3D h= , then some non-negligible fraction of those coins will still be vulnerable= to a CRQC because k*G may be known to the attacker, which to a CRQC is equ= ivalent to knowing k. > >=20 > > To mitigate, a verifier would need to reject such proofs when someone t= ries to spend coins locked to such an "exposed pubkey" address. Since bitco= in nodes do not maintain an address index, they don't intrinsically know wh= ich addresses have exposed pubkeys or not. We would have to compose a list = of such addresses, and since that list changes over time, it would need to = be updated by nodes in real-time when indexing transactions. This list will= almost certainly be incomplete, because we don't have any record of pubkey= s exposed off-chain (e.g. by hardware wallets, by xpubs shared in multi-par= ty protocols, by lost TXs in orphaned blocks). > >=20 > > This idea also collides very unfortunately with the BIP32 xpriv proof o= f knowledge. With the faster proof style i suggested to modify Laolu's orig= inal one, a spender immediately gives up knowledge of their account-level x= priv to the CRQC when publishing a TX. Even if the spender was using a hash= ed-address with a hidden pubkey, the CRQC now knows the secret key k for th= at address, and could use it to forge a proof that h =3D HASH160(k*G) to at= tempt to double-spend/RBF the authentic transaction. > >=20 > > So we can't just add hashed-address proofs alongside BIP32 xpriv proofs= . They'd have to be mutually exclusive: A verifier would accept a BIP32 xpr= iv proof if and only if the address is on the "exposed pubkey" list. The ve= rifier would accept a hashed-address proof if and only if the address is NO= T on the "exposed pubkey" list. It's definitely feasible, it's just hard to= do both safely. > >=20 > > This is also difficult to motivate, as we lack hard statistics about th= e relevant portion of the Bitcoin supply that we could use hashed-address p= roofs (but not BIP32 proofs) to rescue: Those UTXOs which fall into the ven= n-diagram overlap of "Not using BIP32" and "Not exposed-pubkey". BIP32 was = introduced in 2012, whereas P2PKH was introduced in 2009, so clearly there = must be some overlap, but how much? I suppose one could estimate by indexin= g all the P2PKH UTXOs received before BIP32 was published, and counting wha= t portion of them still have (probably) hidden public keys. This would be u= seful research for anyone with the time and a working node. > >=20 > > regards, > > conduition > >=20 > > On Monday, April 13th, 2026 at 2:21 PM, sadiq Ismail wrote: > >=20 > > > Hi Laolu, list, > > >=20 > > > Nice work. > > >=20 > > > The scheme extends to BIP-352 (Silent Payments). The BIP-352 receiver= reconstructs the output P using their private scan key, public spend key, = and public information from the spending transaction A. > > > See BIP-352 Scanning. BIP-352 recommends but does not mandate BIP-32 = for deriving the scan and spend keys, but specifies the following derivatio= n paths when BIP-32 is used: > > >=20 > > > b_scan =3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0) > > > b_spend =3D BIP32Derive(s, m/352'/coin_type'/account'/0'/0) > > >=20 > > > For all silent payment addresses generated using BIP-32, your techniq= ue applies. The prover produces a zk-STARK proof that the program BIP32Deri= ve(s, p_scan) and BIP32Derive(s, p_spend) were run correctly, > > > and that the resulting keys reconstruct the on-chain output P using a= long with A. > > >=20 > > > As you highlighted txid is not committed in the proof currently, the = argument is replayable. The current POC does not bind to where the coins go= . Anyone who observes the chain could copy it and attach it to a different = transaction, spending the same UTXO to a different address. Worse for silen= t payment, because all user UTXO have the same secret BIP32Derive(s, p_scan= ) and BIP32Derive(s, p_spend) except for A. > > > The zk-STARK proof? or this mechanism should definitely be bound to t= he spending transaction and the input being spent. > > >=20 > > > Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BI= P-32 still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2= =80=94 as long as the pubkey has never previously appeared on-chain. A zk-S= TARK proof should apply here too? The prover argues for the correctness of = HASH160(k=C2=B7G) =3D h, where k is the private key scalar and k=C2=B7G is = the elliptic-curve point, without ever revealing k or the pubkey. This woul= d allow recovery of a broader set of funds. If it were decided that classic= al signatures for these output types are invalidated and only a valid zk-ST= ARK proof is required to spend, anyone who holds the original secret can un= lock their funds. > > >=20 > > > P.S. I am not for or against disabling valid spend paths post-quantum= , just discussing the technical possibilities. > > >=20 > > > Best, > > > Abubakar Sadiq > > > On Friday, April 10, 2026 at 7:47:09=E2=80=AFPM UTC+2 conduition wrot= e: > > >=20 > > > > Ah! Amazing work! 2 seconds to prove is really crazy. Proving a sin= gle SHA256 and one modular addition on my CPU back in the day took like 20 = seconds. Your GPU is coming in clutch for this. I best RISC0 has also impro= ved quite a bit since then. > > > > I think the next optimization step would be pre-seeding the two SHA= 512 midstates from the host, so you only need to prove two SHA512 compressi= on calls instead of four. Intuitively I expect this would at best halve you= r prover time from 2sec, to probably a little over 1sec, and your verifier = time will probably drop as well since that also seems to scale with circuit= complexity. > > > >=20 > > > > I think I have two half-decent arguments now as to why this won't a= ffect security: > > > >=20 > > > > First, even if a fraudulent prover is handed the correct midstates = to use, the prover would still have to do the hard work of finding the pare= nt secret key needed as a witness. This is at least the same difficulty as = finding the parent sk if we just hashed it without a chaincode at all, usin= g two bare SHA512 calls - the only thing that changes is the midstate, and = the SHA512 input length suffix. Starting from a different midstate doesn't = magically give the attacker a head-start in a 256-bit search space looking = for sk. A frauduent prover would know the child secret key k =3D sk + int(I= [32:]) % n, but they don't know int(I[32:]) or sk so they cannot solve for = either. > > > >=20 > > > >=20 > > > > Nominally, the fraudulent prover wouldn't even know the correct mid= states, so their task is strictly harder. > > > >=20 > > > > Secondly, here's another argument as to why finding the midstates i= n the first place should also be hard. > > > >=20 > > > >=20 > > > > Any adversary who could solve this problem by finding the right mid= states could be used as an oracle to prove the existence of partial 2-cycle= s in SHA512. > > > >=20 > > > >=20 > > > > - Given a SHA512 hash I, set sk =3D int(I[32:]) > > > > - Compute k =3D sk + sk % n > > > > - Use the black-box fraudulent prover on the child key k to find = correct midstates such that > > > > =20 > > > >=20 > > > >=20 > > > >=20 > > > > I =3D=3D SHA512( || SHA512( || 0x00 || sk || = i)) > > > > k =3D=3D int(I[32:]) + sk % n > > > > =3D=3D sk + sk % n > > > >=20 > > > >=20 > > > > Remember that sk =3D int(I[32:]). Thus for these conditions to hold= , the proof forger must be able to find not just the correct midstates, but= also midstates which give a 2-stage partial hash cycle so that: > > > >=20 > > > >=20 > > > > I =3D=3D SHA512( || SHA512( || 0x00 || I[32:]= || i)) > > > >=20 > > > >=20 > > > > This seems unlikely or at least very difficult. > > > >=20 > > > >=20 > > > > regards, > > > > conduition > > > >=20 > > > > On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun wrote: > > > >=20 > > > > > Hi Condution, > > > > >=20 > > > > > So I implemented both variants of your idea. My intuition was rig= ht in that it > > > > > doesn't do much to reduce the size of the final succinct size, bu= t the final > > > > > xpriv variant resulted in a significant reduction in both proving= time, and > > > > > also memory usage. I also re-ran the original succint proof for t= he original > > > > > Taproot claim and got a better value for the final proof time (de= f need a > > > > > better benchmark env+set up!). > > > > >=20 > > > > > Here's a breakdown of the resource requirements for the various p= roofs: > > > > > * Full Taproot > > > > > image ID: > > > > > 8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690 > > > > > composite: > > > > > seal 1797880 > > > > > prove 49.32s > > > > > verify 0.10s > > > > > peak RSS 11907399680 > > > > > succinct: > > > > > seal 222668 > > > > > prove 64.30s > > > > > verify 0.03s > > > > > peak RSS 11927207936 > > > > >=20 > > > > > * Hardened xpub > > > > > image ID: > > > > > ad4ebc0ef6ce51e0f581cc8d14742a5b97738e9decd3fe2b0f1746de5bad9617 > > > > > composite: > > > > > seal 513680 > > > > > prove 14.63s > > > > > verify 0.04s > > > > > peak RSS 11783503872 > > > > > succinct: > > > > > seal 222668 > > > > > prove 17.29s > > > > > verify 0.02s > > > > > peak RSS 11782307840 > > > > >=20 > > > > > * Hardened xpriv > > > > > image ID: > > > > > 8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0df0849 > > > > > composite: > > > > > seal 234568 > > > > > prove 1.98s > > > > > verify 0.02s > > > > > peak RSS 3144171520 > > > > > succinct: > > > > > seal 222668 > > > > > prove 2.84s > > > > > verify 0.02s > > > > > peak RSS 3145990144 > > > > >=20 > > > > > So we can see that the succinct proof sizes are all about the sam= e. However the > > > > > xpriv variant can be proved directly in just 2 seconds on my mach= ine! It also > > > > > requires just 3 GB of memory for the proof as well. > > > > >=20 > > > > > I've created some additional supporting documentation to detail e= xactly what > > > > > the new proofs do and their results: > > > > >=20 > > > > > * https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/reduced= -variants.md > > > > >=20 > > > > > * https://github.com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398180a2b3= eff7761b7f4b233d455c6c9/README.md#reduced-proof-variants > > > > >=20 > > > > > * https://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83e= f4019974a5171f5e06fa840/docs/claim.md#reduced-variant-claims > > > > >=20 > > > > >=20 > > > > > Once again, thanks for the great ideas! I wonder if we can improv= e on this > > > > > round of proof golf further before reaching down a lower level wi= th some sort > > > > > of AIR compiler =F0=9F=A4=94. > > > > >=20 > > > > > -- Laolu > > > > >=20 > > > > > On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osuntokun wrote: > > > > >=20 > > > > > > Hi Conduition, > > > > > >=20 > > > > > > > You need only prove this much more general statement (2): "I = know a BIP32 > > > > > > > xpriv which derives this xpub via one or more hardened steps"= . > > > > > >=20 > > > > > > > I'm amending my prior suggestion slightly: The circuit (guest= program) > > > > > > > could take in an xpriv (e.g. at m/86'/0') and output a child = xpriv > > > > > > > (e.g. at m/86'/0'/0') to the journal (instead of outputting a= child > > > > > > > xpub). > > > > > >=20 > > > > > > That's an excellent insight! > > > > > >=20 > > > > > > As mentioned in my recent reply, with risc0's "succinct" receip= t type, I was > > > > > > able to get the proof size down to 220 KB, at the cost of 3.5x = longer total > > > > > > proving time. > > > > > >=20 > > > > > > Your proposal definitely reduces the complexity of the core sta= tement to be > > > > > > proved, which would speed up the proving time for the normal > > > > > > default/composite receipt type. > > > > > >=20 > > > > > > I'll try to hack this up, and then run a head to head compariso= n to see this > > > > > > simpler statement actually results in a smaller proof then the = final > > > > > > succinct receipt of either of the proof variants. Based on my c= urrent > > > > > > intuition w.r.t the lower level details, I think the final succ= inct proof > > > > > > size would be on the same order of magnitude re size. > > > > > >=20 > > > > > > However, this can still be a win as then this would provide pot= ential future > > > > > > users with a less resource intensive proof, which can then be > > > > > > aggregated/rolled up into a final succinct proof in a batched m= anner. > > > > > >=20 > > > > > > This line of optimization is also more interesting if one were = to look at > > > > > > hand rolling a custom AIR to avoid the overhead that the RISC-V= emulation > > > > > > adds to the rirsc0 proof chain, given that it entirely skips do= ing any EC > > > > > > operations at all for the final statement. > > > > > >=20 > > > > > > ---- > > > > > >=20 > > > > > > Re the commit/reveal approach, to be honest I'm not fully caugh= t up on that > > > > > > proposal. That original thread got pretty long, so I dropped of= after a > > > > > > point =F0=9F=98=85. I'll revisit that specific branch of the th= read so I can digest it > > > > > > and develop a proper opinion, then get back to you re compariso= ns! > > > > > >=20 > > > > > > -- Laolu > > > > > >=20 > > > > > > On Wed, Apr 8, 2026 at 1:23=E2=80=AFPM conduition wrote: > > > > > >=20 > > > > > > > Oh, I've been a fool, a foolish fool. > > > > > > >=20 > > > > > > > We don't even need to do point multiplication in the circuit = at all. > > > > > > >=20 > > > > > > > I'm amending my prior suggestion slightly: The circuit (guest= program) could take in an xpriv (e.g. at m/86'/0') and output a child xpri= v (e.g. at m/86'/0'/0') to the journal (instead of outputting a child xpub)= . > > > > > > >=20 > > > > > > > This is safe because remember, EC spending has been disabled = in this context, and to a quantum attacker, an xpub is computationally equi= valent to its xpriv. So why bother hiding it? The child xpriv doesn't give = an observer anything they can't already do with the equivalent xpub. > > > > > > >=20 > > > > > > > The guest program then is basically the BIP32 CKDpriv algorit= hm, restricted to a single hardened derivation step. The verifier gets the = child xpriv, but can't use it to forge new proofs. Honest verifiers use the= xpriv to derive the child address(es) as suggested in my last message, to = authenticate spending. > > > > > > >=20 > > > > > > > Designing the guest program like this will massively reduce y= our circuit complexity, because EC point multiplication is wayyyyy harder f= or the RISC0 compiler to arithmetize than a simple hash function. In my pri= or work with RISC0, I made a guest program which ran a SHA256 hash and an E= C point multiplication. I found that pruning EC point arithmetic from my gu= est program improved prover runtime by a factor of over 100x. > > > > > > >=20 > > > > > > > If I am not fever-dreaming and this is indeed possible, then = the new circuit's complexity will be dominated not by point multiplication,= but by the HMAC-SHA512 call. Our new task is then to figure out how much w= e can internally optimize the HMAC-SHA512 call for STARK proving. Here's a = few ideas. > > > > > > >=20 > > > > > > > If you bust open HMAC-SHA512, it looks like this: > > > > > > >=20 > > > > > > > HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=95= 0x36) || msg)) > > > > > > >=20 > > > > > > > ...where in the context of BIP32 hardened CKD, the HMAC key K= is the chaincode (padded with zeros to 128 bytes) and msg =3D (0x00 || sk = || i) is the parent secret key and child index. > > > > > > >=20 > > > > > > > Since len(K) =3D 128 is the SHA512 block size, we need a tota= l of 4 SHA512 compression calls: > > > > > > >=20 > > > > > > > 1. to compress (K=E2=8A=950x36) > > > > > > > 2. to compress the msg (and SHA512 padding/length) > > > > > > > 3. to compress (K=E2=8A=950x5c), and > > > > > > > 4. a final compression call to tie it all together. > > > > > > >=20 > > > > > > >=20 > > > > > > > The output of that last compression call is partitioned into = the child chaincode, and a key delta which is added to the parent secret ke= y (modulo the curve order), producing the child EC secret key. This last st= ep is arithmetically simple; the SHA512 calls are where most of the arithme= tic complexity lies. > > > > > > >=20 > > > > > > > The question then becomes, which of these compression calls c= an be done outside the circuit, and which are truly essential for security? > > > > > > >=20 > > > > > > > Note how the parent secret key is the most important piece fo= r soundness. The circuit needs to prove the parent secret key existed in th= e hash function preimage, and is correctly related to the child secret key = via modular addition. So compression call (2) seems unavoidable. The others= are less rigid. > > > > > > >=20 > > > > > > > I'd argue that if we really dig into the hard relation we're = trying to prove here, we can reduce it to this statement: > > > > > > >=20 > > > > > > > Given a child xpriv with secret key k, chaincode c and index = i, I know a preimage x and secret key sk such that: > > > > > > >=20 > > > > > > >=20 > > > > > > > I <- SHA512( || SHA512( || 0x00 || sk |= | i)) > > > > > > > c =3D=3D I[:32] > > > > > > > k =3D=3D int(I[32:]) + sk % n > > > > > > >=20 > > > > > > > Seeing as the slots are arbitrary, and we know in= BIP32 they are always exactly one-block long, it seems easy to throw out t= he compression calls (1) and (3). The host can precompute the relevant SHA5= 12 midstates outside the circuit, and pass the midstates into the guest pro= gram as secret inputs. The tradeoff is that this permits malicious provers = the flexibility of choosing their starting midstates (though hash input len= gth can be fixed at 192 bytes). I'm not entirely sure if this meaningfully = weakens the verifier's soundness. Ethan Heilman might have opinions on this= , he knows a lot more about attacking hash functions than I do. Intuitively= , I doubt sampling random SHA512 midstates is that much better than samplin= g a random HMAC key (chaincode) K and computing the resulting midstates. > > > > > > >=20 > > > > > > >=20 > > > > > > > This reduces our circuit to, i think, the minimum acceptable = security floor for provers: two SHA512 compression calls, which commit to a= parent secret key. > > > > > > >=20 > > > > > > >=20 > > > > > > >=20 > > > > > > >=20 > > > > > > > regards, > > > > > > > conduition > > > > > > > On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via B= itcoin Development Mailing List wrote: > > > > > > >=20 > > > > > > > > Hi Laolu, > > > > > > > > Great work getting this working in the real world. I've hea= rd many people on delving and the mailing list conjecture based on this ide= a, but you're the first person i've seen who's willing to put their money w= here their mouth is, and actually build a prototype. Bravo! > > > > > > > >=20 > > > > > > > > It seems to me the circuit (guest program) could be simplif= ied. Notice how the guest code computes the entire HD wallet key path, incl= uding hardened and non-hardened derivation steps, and also computes the tap= root output key with key-tweaking. I'd argue these steps are extraneous to = the core hard relation you want the STARK to prove, and could be safely rem= oved to reduce proof size and improve performance. > > > > > > > >=20 > > > > > > > > In reality, you needn't go so far as to prove (1) "I know a= BIP39 seed which derives this taproot output key". You need only prove thi= s much more general statement (2): "I know a BIP32 xpriv which derives this= xpub via one or more hardened steps". The latter statement (2) still canno= t be forged by a quantum adversary even if they know your account-level xpu= b, but it entails far less computation to prove and verify. The rest of the= original statement (1) can be done externally outside the circuit. > > > > > > > >=20 > > > > > > > > Example. If i have a wallet with a taproot address at m/86'= /0'/0'/1/2, I could prove I know the xpriv at m/86'/0' which derives the xp= ub at m/86'/0'/0'. Then I provide the remaining key path elements /1/2 in t= he witness. Note, i do not mean we derive the xpriv at m/86'/0' inside the = guest program. I mean the prover derives m/86'/0' first (in the host), and = then writes that xpriv into the guest program's inputs. The guest program d= erives and outputs the xpub at m/86'/0'/0'. The verifier may check the STAR= K output (xpub) is correctly computed, then use the given key-path to manua= lly derive the taproot address from the xpub themselves, outside the circui= t, and validate that address against the UTXO i'm spending. The verifier th= us has confirmed the prover knew an xpriv which (through a hardened derivat= ion step) derives the correct taproot output key. > > > > > > > >=20 > > > > > > > > This change significantly reduces the size of the circuit. = >From a glance, I see the original guest program performs 6 HMAC-SHA512 call= s (1 for the master key, 5 for the BIP32 derivation steps), two SHA256 comp= ression calls (for the taptweak hash), and two point multiplications. With = this simplified variant, we are invoking only a single HMAC-SHA512 call and= a single point multiplication. I can't say for sure, but I expect this wil= l improve your proof size and runtime significantly. > > > > > > > >=20 > > > > > > > > This change also makes the circuit more generally applicabl= e to other rescue contexts. For instance, it could be applied to BIP340 xon= ly keys inside a taproot script tree, or in a P2(W)SH address to an ECDSA p= ublic key, or to P2(W)PKH addresses. > > > > > > > >=20 > > > > > > > > Concerned about publishing xpubs? Remember that we are assu= ming regular EC spending is locked in this context, so it is safe-ish to sh= are account xpubs with quantum attackers. At best the xpub can be used for = surveillance but not forgery. If one would prefer not to share the account-= level xpub on-chain for privacy reasons, the proof could be extended to als= o derive the unhardened child xpub at /1/2 inside the guest program (but we= still do not need to do the taproot key tweaking in the guest program). > > > > > > > >=20 > > > > > > > > We should also talk scaling efficiency. Given the cost of S= TARKs, this style of proof should be able to authorize spends for more than= one UTXO. Say you have a wallet with 10 different UTXOs held by distinct a= ddresses in the same BIP44 account. One single STARK proof could authorize = spending all 10 of them, by simply committing all 10 input signature hashes= into the journal, and labeling the inputs with the corresponding 10 BIP32 = key paths somehow. The verifier would need to check the proof only once and= not 10 times. The 10 UTXO spends could be validated using the common xpub = from the STARK proof's journal. > > > > > > > >=20 > > > > > > > > For a slightly related work proving a similar relation for = hashed addresses, using different STARK technology stacks, see this delving= post. > > > > > > > >=20 > > > > > > > > However, all this said, my personal preference for long-ter= m procrastinator rescue is still for commit/reveal strategies which prove e= ssentially the same statement about BIP32 in a two-step procedure. They get= the job done with much lighter cryptographic machinery and much smaller wi= tnesses: a few hundred bytes over two transactions, compared to a few milli= on bytes in one transaction with STARKs. Boris Nagaev and I discussed this = on the list a while back. That said, commit/reveal requires more careful de= sign and seems to demand the use of external quantum-safe coins to make the= commitment in the first place, so perhaps the cost would be worth it to so= me people? IDK. What do you think of commit/reveal compared to STARKs for t= his purpose? > > > > > > > >=20 > > > > > > > > regards, > > > > > > > > conduition > > > > > > > > On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntok= un wrote: > > > > > > > >=20 > > > > > > > > > Hi y'all, > > > > > > > > >=20 > > > > > > > > > I found some spare time this last weekend to dust off a l= ittle side project > > > > > > > > > I started last August: extend TinyGo [1] to be able to pr= oduce RISC-V ELF > > > > > > > > > binaries capable of being run as a guest on the risc0 pla= tform to generate > > > > > > > > > zk-STARK proofs of arbitrary programs. Initially, I didn'= t really have a > > > > > > > > > clear end target application, it was mainly a technical c= hallenge to force > > > > > > > > > me to learn a bit more about the RISC-V platform, and als= o the host/guest > > > > > > > > > architecture of risc0. Fast forward ~9 months later, and = an initial killer > > > > > > > > > use case popped into my mind: a zk-STARK proof that a Tap= root output public > > > > > > > > > key was generated using BIP-32, via a given BIP-86 deriva= tion path. > > > > > > > > >=20 > > > > > > > > > More formally: > > > > > > > > > ```math > > > > > > > > > \mathcal{R} =3D \left\lbrace\; > > > > > > > > > (\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{s,\= , \mathbf{p}}_{\textsf{witness}}) > > > > > > > > > \;\middle|\; > > > > > > > > > \begin{aligned} > > > > > > > > > K &=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,= \, \mathbf{p})\bigr) \\ > > > > > > > > > C &=3D \textsf{SHA256}\bigl(\texttt{"bip32-pq-zkp:path:v1= "} \;\|\; \mathbf{p}\bigr) > > > > > > > > > \end{aligned} > > > > > > > > > \;\right\rbrace > > > > > > > > > ``` > > > > > > > > >=20 > > > > > > > > > where $K$ is the Taproot output key, $C$ is the path comm= itment, $s$ is the > > > > > > > > > BIP-32 seed, and $\mathbf{p}$ is the derivation path. > > > > > > > > >=20 > > > > > > > > >=20 > > > > > > > > > I was able to get everything working e2e over the weekend= , after making > > > > > > > > > some tweaks to my initial architectural game plan! > > > > > > > > >=20 > > > > > > > > > The TL;DR is that: > > > > > > > > >=20 > > > > > > > > > * Given that the Taproot commitment scheme is post-quantu= m secure [3], in > > > > > > > > > the future we can deploy a soft fork to _disable_ the key= spend path, > > > > > > > > > and force all Taproot spends to instead flow through the = script path > > > > > > > > > (not my idea, commonly discussed amongst developers, not = sure who > > > > > > > > > proposed it first). At that point, Taproot starts to rese= mble BIP-360. > > > > > > > > >=20 > > > > > > > > > * That works for script path spends, but then leaves all = the BIP-86 > > > > > > > > > wallets in a bad position, as they generated outputs that= provably > > > > > > > > > don't commit to a script path at all. > > > > > > > > >=20 > > > > > > > > > * A 2023 paper (Protecting Quantum Procrastinators with S= ignature > > > > > > > > > Lifting: A Case Study in Cryptocurrencies [4]) proposed a= solution to this, > > > > > > > > > namely _seed lifting_ (use BIP-32 as the one-way function= to the > > > > > > > > > Picnic PQ Signature scheme) to provide a post-quantum pro= of of secret > > > > > > > > > information a quantum attacker wouldn't be able to easily= obtain. > > > > > > > > >=20 > > > > > > > > > * The downside of that is that it reveals the secret BIP = 32 seed, > > > > > > > > > exposing other non migrated UTXOs of a user. > > > > > > > > >=20 > > > > > > > > > * With this project I've cobbled together a series of pro= jects to be able > > > > > > > > > to generate a zk-STARK proof that a Taproot output public= key was > > > > > > > > > generated via BIP-32 invocation of a BIP-86 derivation pa= th. > > > > > > > > >=20 > > > > > > > > > * In the future a variant of this scheme can be used to e= nable wallets > > > > > > > > > that generated the private keys via BIP-86, to have a pos= t quantum safe > > > > > > > > > exit path in case they don't bother moving their coins in= time to the > > > > > > > > > yet-to-be-decided post quantum signature scheme. > > > > > > > > >=20 > > > > > > > > > To achieve this end, I needed to create/fork a series of = repos: > > > > > > > > >=20 > > > > > > > > > * tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm > > > > > > > > > * A fork of TinyGo that supports the flavor of RISC-V (rv= 32im) that > > > > > > > > > risc0 requires to generate/execute a guest program to lat= er be proved > > > > > > > > > by the host. > > > > > > > > >=20 > > > > > > > > > * risc0: https://github.com/Roasbeef/risc0 > > > > > > > > > * Mostly a bug fix to their c-guest example, along with s= ome > > > > > > > > > additional documentation on how to get things running. Th= e repo is > > > > > > > > > unmodified other than that. Recent updates to the repo ma= de the > > > > > > > > > entire process much easier (Go guest+host), more on that = later. > > > > > > > > >=20 > > > > > > > > > * go-zkvm: https://github.com/Roasbeef/go-zkvm > > > > > > > > > * Go utilities to take a RISC-V ELf binary produced by ti= nygo-zkvm, and > > > > > > > > > package it in the expected R0BF format, which combines th= e user > > > > > > > > > generated RISC-V ELF (the thing that is executed to gener= ate the > > > > > > > > > proof) along with the v1compat ELF kernel, which is risc0= 's execution > > > > > > > > > environment. > > > > > > > > >=20 > > > > > > > > > * This also includes a Go host package, which loads the g= uest program, > > > > > > > > > executes it, and generates a trace to later be proved. Th= is is > > > > > > > > > achieved via a C FFI compat layer between Go and the orig= inal Rust > > > > > > > > > host/proving/verification code. > > > > > > > > >=20 > > > > > > > > > * bip-32-pq-zkp: https://github.com/Roasbeef/bip32-pq-zkp > > > > > > > > > * The project that packages everything together, this con= tains the: > > > > > > > > > * Guest Go program that defines the secret witness and > > > > > > > > > claim/constraints of the proof. > > > > > > > > >=20 > > > > > > > > > * The C FFI wrapper around the OG Rust host, which is use= d to load > > > > > > > > > the guest program, execute it, generate a trace, then fin= ally > > > > > > > > > generate a proof. > > > > > > > > >=20 > > > > > > > > > Details of the final proof as generated on my Mac Book (A= pple Silicon M4 > > > > > > > > > Max, 128 GB of RAM): > > > > > > > > > * Takes ~55 seconds or so to generate+proof, including ex= ecution. This > > > > > > > > > uses Metal for GPU acceleration on the platform. > > > > > > > > > * Uses ~12 GB of ram. > > > > > > > > > * Final proof size is ~1.7 MB. > > > > > > > > > * Verification takes ~1.8 seconds, and uses ~32 MB of mem= ory. > > > > > > > > >=20 > > > > > > > > > On several layers, this demo is far from optimized (more = on that later), > > > > > > > > > this is meant to serve as a PoC to demonstrate that with = the latest > > > > > > > > > software+hardware, a proof of this complexity is well wit= hin reach. > > > > > > > > >=20 > > > > > > > > > For those curious re the e2e details I've generated this = tutorial that > > > > > > > > > explains the entire system top to bottom: > > > > > > > > > https://github.com/Roasbeef/go-zkvm/blob/main/docs/tutori= al.md. > > > > > > > > >=20 > > > > > > > > > If you got to this point in this mail, and don't care abo= ut the lower level > > > > > > > > > details, thanks for reading up until now, and feel free t= o return back to > > > > > > > > > the _The Net of a Million Lies_, or as better known in ou= r Universe: > > > > > > > > > Monitoring the Situation and/or slopfotainment! =F0=9F=AB= =A1 > > > > > > > > >=20 > > > > > > > > > ## Motivation + Background > > > > > > > > >=20 > > > > > > > > > As commonly known, in the case of an adversary that posse= sses a quantum > > > > > > > > > computer capable of breaking classical asymmetric cryptog= raphy, any coins > > > > > > > > > stored in UTXOs with a known public key are vulnerable. T= his is the case > > > > > > > > > for any P2PK outputs from waaaay back, and also any other= outputs that have > > > > > > > > > revealed their public key. Pubkey reveal might happen due= to address re-use > > > > > > > > > (spending from the same script twice), or Taproot outputs= , which publish > > > > > > > > > the public key plainly in the pkScript. > > > > > > > > >=20 > > > > > > > > > As detailed in [3], for Taproot outputs, a widely circula= ted plan is > > > > > > > > > roughly to: disable the _keyspend_ path (requires a simpl= e signature), > > > > > > > > > enforcing a new rule that all Taproot spends must then fl= ow through the > > > > > > > > > script path. Spending via the script path requires an ope= ning of the > > > > > > > > > Taproot commitment (C =3D I + H(I || H(M))), which was sh= own to be binding even > > > > > > > > > under classic assumptions, as H(M) (tapscript merkle root= ) is still a > > > > > > > > > collision-resistant function. > > > > > > > > >=20 > > > > > > > > > That means any UTXO that _does_ commit to a script path h= as a future escape > > > > > > > > > hatch _if_ such a softfork would need to be deployed in t= he future. > > > > > > > > > However, what about all the other wallets that use BIP 86= , and don't commit > > > > > > > > > to a script path at all? Under a strict version of this e= xisting > > > > > > > > > proposal, those wallets would basically be locked forever= . > > > > > > > > >=20 > > > > > > > > > The goal of this work is to demonstrate a practical solut= ion (discussed > > > > > > > > > against devs, but never implemented AFAICT): generate a z= k proof that an > > > > > > > > > output was generated using BIP-86. For the zk-Proof, we s= elect zk-STARKs, > > > > > > > > > as they're plausibly post quantum since they rely only on= symmetric > > > > > > > > > cryptography: layers of merkle trees over an execution tr= ace, along with > > > > > > > > > some novel sampling/error-correction algorithms. > > > > > > > > >=20 > > > > > > > > > At this point, you may be asking: "if the quantum adversa= ry can derive the > > > > > > > > > private key to a random taproot public key, then how exac= tly does this > > > > > > > > > help?". The answer lies in the structure of BIP-32! BIP-3= 2 takes an initial > > > > > > > > > 128-512-bit seed (with BIP-39, either 12 or 24 words), th= en runs it through > > > > > > > > > HMAC-SHA512 keyed by "Bitcoin seed" to produce the master= extended private > > > > > > > > > key. An adversary who wants to forge this proof needs to = find a _colliding_ > > > > > > > > > seed: a different seed s' such that HMAC-SHA512("Bitcoin = seed", s') produces > > > > > > > > > the same master key. The BHT algorithm (Brassard-Hoyer-Ta= pp [6]) is the > > > > > > > > > best known quantum collision finder, and it runs in time = proportional to the > > > > > > > > > cube root of the output space: 2^(n/3). For HMAC-SHA512's= 512-bit output, > > > > > > > > > that's ~2^171 quantum operations, well above even NIST's = highest > > > > > > > > > post-quantum security category. Therefore, if you generat= ed a wallet using > > > > > > > > > BIP-32, you possess _another_ secret that a quantum adver= sary can't > > > > > > > > > efficiently reconstruct! > > > > > > > > >=20 > > > > > > > > > This demo focuses on the Taproot case, but the rough appr= oach also applies > > > > > > > > > to any other output generated via BIP-32. BIP 32 was orig= inally published in > > > > > > > > > 2012, over 14 years ago. So safe to say that _most_ walle= ts were generated > > > > > > > > > under this scheme. However, Bitcoin Core only officially = adopted BIP-32 in > > > > > > > > > 2016/2018, moving away from their existing key pool struc= ture. I can't say > > > > > > > > > how much BTC is held today in outputs generated with Bitc= oin Core's original > > > > > > > > > key pool, but if you have coins generated via that mechan= ism, you may want > > > > > > > > > to consider migrating them to a BIP-32 wallet. > > > > > > > > >=20 > > > > > > > > > ## TinyGo + RISC-V + risc0 > > > > > > > > >=20 > > > > > > > > > Now for some of the lower level details. risc0 is a STARK= based proving > > > > > > > > > system that takes a RISC-V ELF binary generated by a gues= t program (any > > > > > > > > > program generating using their flavor of rv32im can be pr= oved), executes > > > > > > > > > that in a host environment, generates a trace, then produ= ces a STARK proof > > > > > > > > > from that. > > > > > > > > >=20 > > > > > > > > > Today you can take some subset of Rust, compile it to an = ELF using their > > > > > > > > > toolchain, then execute it, generate a trace, to finally = prove+verify it > > > > > > > > > using their system. > > > > > > > > >=20 > > > > > > > > > This demo took a bit of a round about journey to achieve = this, as after > > > > > > > > > all, the journey is most of the fun, ain't it! > > > > > > > > >=20 > > > > > > > > > For the past 10 years or so, my Bitcoin stack of choice (= lnd/btcsuite) uses > > > > > > > > > a series of Go libraries, so I wanted to be able to re-us= e them, first for > > > > > > > > > this demo, then also in the future for other projects. > > > > > > > > >=20 > > > > > > > > > TinyGo is a special Go compiler based on LLVM, that targe= ts mostly embedded > > > > > > > > > environments. You can use it to generate go programs that= can run on > > > > > > > > > micro controllers, or on web assembly (producing a smalle= r binary than if > > > > > > > > > you used the normal stdlib path). > > > > > > > > >=20 > > > > > > > > > TinyGo supports RISC-V, but _not_ the 32-bit variant of R= ISC-V that risc0 > > > > > > > > > relies on. So the first step here was to create a new tar= get definition for > > > > > > > > > TinyGo: riscv32-unknown-none, which uses base integer + m= ultiply/divide > > > > > > > > > instructions with no compressed instructions, which uses = 4 KB stacks for > > > > > > > > > each task. From there, I created a new linker script > > > > > > > > > (`targets/riscv32im-risc0-zkvm-elf.ld`) which created a m= emory layer > > > > > > > > > identical to what risc0 expects. The final component was = a new runtime > > > > > > > > > (`src/runtime/runtime_zkvm.go`), which implemented a few = platform specific > > > > > > > > > syscalls for risc0 (putchar(), exit(), ticks(), and growH= eap()). > > > > > > > > >=20 > > > > > > > > > When I tried to get this working last year, I had to also= implement a number > > > > > > > > > of kernel syscalls (called ecalls in the platform [7]) to= handle: read+write > > > > > > > > > to stdin/stdout, halting, and the journaling mechanism (t= he transcript of > > > > > > > > > execution committed to), which basically implement the ke= rnel that the guest > > > > > > > > > executes in. Fast forward to 2026, and after pulling the = latest version of > > > > > > > > > the repo, I realized that they now make a libzkvm_platfor= m.a, which packages > > > > > > > > > up the kernel nicely to be linked against. So I threw out= my custom kernel > > > > > > > > > code, and slotted that in instead. > > > > > > > > >=20 > > > > > > > > > The final component is a C FFI layer that enables me to u= se _both_ a Go > > > > > > > > > guest (the program to be proved) and a Go host (the thing= that executes the > > > > > > > > > program and generates the final proof). > > > > > > > > >=20 > > > > > > > > > ## BIP-32+Taproot zk-STARK Proof > > > > > > > > >=20 > > > > > > > > > With basic proofs working (like the classic: I know the f= actorization of a > > > > > > > > > number `n`), I was unblocked to generate the actual proof= . The claim/proof > > > > > > > > > is represented with the following JSON artifact: > > > > > > > > > ``` > > > > > > > > > { > > > > > > > > > "schema_version": 1, > > > > > > > > > "image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c8= 4bfac077cbe70907a690", > > > > > > > > > "claim_version": 1, > > > > > > > > > "claim_flags": 1, > > > > > > > > > "require_bip86": true, > > > > > > > > > "taproot_output_key": "00324bf6fa47a8d70cb5519957dd54a02b= 385c0ead8e4f92f9f07f992b288ee6", > > > > > > > > > "path_commitment": "4c7de33d397de2c231e7c2a7f53e5b581ee3c= 20073ea79ee4afaab56de11f74b", > > > > > > > > > "journal_hex": "010000000100000000324bf6fa47a8d70cb551995= 7dd54a02b385c0ead8e4f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3= c20073ea79ee4afaab56de11f74b", > > > > > > > > > "journal_size_bytes": 72, > > > > > > > > > "proof_seal_bytes": 1797880, > > > > > > > > > "receipt_encoding": "borsh" > > > > > > > > > } > > > > > > > > > ```` > > > > > > > > >=20 > > > > > > > > > The `image_id` is basically a hash of the ELF, so you kno= w what the prover > > > > > > > > > executed. There are then a few flags that control the cla= im version and > > > > > > > > > whether BIP-86 derivation is a part of the proof. BIP-86 = was only adopted > > > > > > > > > post-Taproot, so if you have an existing BIP-44 path, you= can instead opt to > > > > > > > > > claim that instead. The Taproot key we're generating the = proof against is > > > > > > > > > also part of the _public data_, as it sits plainly on the= chain for all to > > > > > > > > > see. We then also include a `path_commitment`, which is a= commitment to the > > > > > > > > > exact BIP 86 path that the prover used. Finally, we also = commit to the > > > > > > > > > journal hex, which is basically a commitment to the publi= c claim. > > > > > > > > >=20 > > > > > > > > > Assuming you've built the project, then you can generate = the proof (even > > > > > > > > > passing in an arbitrary BIP-32 seed and derivation path w= ith) > > > > > > > > > ``` > > > > > > > > > make prove GO_GOROOT=3D/path/to/go1.24.4 > > > > > > > > > ``` > > > > > > > > >=20 > > > > > > > > > Then verify it with: > > > > > > > > > ``` > > > > > > > > > make verify GO_GOROOT=3D/path/to/go1.24.4 > > > > > > > > > ``` > > > > > > > > >=20 > > > > > > > > > The default prove target writes: > > > > > > > > > * ./artifacts/bip32-test-vector.receipt > > > > > > > > > * ./artifacts/bip32-test-vector.claim.json > > > > > > > > >=20 > > > > > > > > > The receipt is the STARK proof artifact. claim.json is th= e stable, > > > > > > > > > human-readable description of the public statement being = proved. > > > > > > > > >=20 > > > > > > > > > ## Application to a Future Keyspend Disabling Soft fork > > > > > > > > >=20 > > > > > > > > > As mentioned above, assuming the community is forced to d= eploy a keyspend > > > > > > > > > disabling soft fork in the future, we can also deploy som= e variant of > > > > > > > > > this proof to enable both BIP-86 wallets, and also any BI= P-32 wallet, to > > > > > > > > > sweep their funds into a new PQ output. > > > > > > > > >=20 > > > > > > > > > In 2026, we've shown that this is achievable using 2 year= old consumer > > > > > > > > > hardware. I don't doubt that the upcoming advancements (e= g: photonics, new > > > > > > > > > flavor of high bandwidth memory, etc) in hardware (driven= by the fierce AI > > > > > > > > > race) will make such a proof even more feasible. > > > > > > > > >=20 > > > > > > > > > One thing to note is that this proof has a few layers of = indirection, > > > > > > > > > mainly the RISC-V layer that adds overhead which increase= the total amount > > > > > > > > > of steps, and therefore the size of the proof. A producti= on grade > > > > > > > > > deployment would likely instead hand roll a custom STARK = proof for this > > > > > > > > > exact statement, to achieve a faster and smaller proof). > > > > > > > > >=20 > > > > > > > > > # Future Work > > > > > > > > >=20 > > > > > > > > > In terms of future work, there're a number of interesting= following up > > > > > > > > > projects that can be pursued from here. > > > > > > > > >=20 > > > > > > > > > One basic one is that the current proof doesn't actually = commit to a > > > > > > > > > spending txid and/or sighash. That can be trivially incor= porated into the > > > > > > > > > proof. Going a step further, the execution of the guest p= rogram can even > > > > > > > > > _generate_ a valid schnorr signature to permit spending. > > > > > > > > >=20 > > > > > > > > > Looking to the memory+computational requirements necessar= y to generate the > > > > > > > > > proof, I've left two low hanging fruits: > > > > > > > > >=20 > > > > > > > > > 1. First, we can speed up the Elliptic Curve operations t= he proof requires > > > > > > > > > (scalar base mult, then addition, or more performantly Do= uble Scalar > > > > > > > > > Multiplication via the Strauss-Shamir trick). For this we= can use the > > > > > > > > > syscalls/precompile in the risc0 env for big integer arit= hmetic: > > > > > > > > > sys_bigint and sys_bigint2. With this, the guest calls in= to the kernel > > > > > > > > > to use an optimized/accelerated circuit for the modular a= rithmetic, > > > > > > > > > reducing cycles, steps, and thus proof size. > > > > > > > > >=20 > > > > > > > > > 2. Second right now, the entire claim is a single proof. = Instead, we can > > > > > > > > > first break that up using their recursive proof/compositi= on syscalls: > > > > > > > > > sys_verify_integrity+sys_verify_integrity2. We can then a= ssembled a > > > > > > > > > series of these proofs into a _single_ statement, which c= an save block > > > > > > > > > space by aggregating N proofs into a single proof. > > > > > > > > >=20 > > > > > > > > > -- Laolu > > > > > > > > >=20 > > > > > > > > > [1]: https://tinygo.org/ > > > > > > > > >=20 > > > > > > > > > [2]: https://risczero.com/ > > > > > > > > >=20 > > > > > > > > > [3]: https://eprint.iacr.org/2025/1307 > > > > > > > > >=20 > > > > > > > > > [4]: https://eprint.iacr.org/2023/362 > > > > > > > > >=20 > > > > > > > > > [5]: https://microsoft.github.io/Picnic/ > > > > > > > > >=20 > > > > > > > > > [6]: https://en.wikipedia.org/wiki/BHT_algorithm > > > > > > > > >=20 > > > > > > > > > [7]: https://github.com/Roasbeef/go-zkvm/blob/main/docs/e= call-reference.md > > > > > > > > >=20 > > > > > > > > > -- > > > > > > > > > You received this message because you are subscribed to t= he Google 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/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TVwUf_AYcd_qQ%40m= ail.gmail.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 fr= om it, send an email to bitcoindev+...@googlegroups.com. > > > > > > > > To view this discussion visit https://groups.google.com/d/m= sgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8u= UyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNEYg%3D%40proton.me. > > > > >=20 > > > > > -- > > > > > You received this message because you are subscribed to the Googl= e Groups "Bitcoin Development Mailing List" group. > > > > > To unsubscribe from this group and stop receiving emails from it,= send an email to bitcoindev+...@googlegroups.com. > > > >=20 > > > > > To view this discussion visit https://groups.google.com/d/msgid/b= itcoindev/CAO3Pvs9tps%3DbsMQyA%2BHvhK-u%2BXqRwWtjTq8WXZi%2BcveAVwPi9A%40mai= l.gmail.com. > > >=20 > > > -- > > > 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. > >=20 > > > To view this discussion visit https://groups.google.com/d/msgid/bitco= indev/02378fd1-17a4-47aa-89fa-ee87626def65n%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= email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/2482176b-1ad7-4216-b1e7-2c03265425een%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/= HGkQFMrHgWdd2wMH_rfcA_TrpBdZOqINcFWSamzCvVvtfh_gu7-tH86u1ufHKDftQrKfrY1h5Aa= Juhf24PPz2ZN4a6rUdpvMva4Y_tHY2Ek%3D%40proton.me. -----------------------3061c550b94548b7fb54191d629abdaf Content-Type: multipart/related;boundary=---------------------91c9a8c9f4380939340a74708d408240 -----------------------91c9a8c9f4380939340a74708d408240 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hey Boris, = good to hear from you! Great questions.

I think MuSig2 might actually be possible = to rescue even without BIP32, since the MuSig2 key aggregation scheme is a = one-way function which a CRQC cannot reverse. So you don't even need a BIP3= 2 proof to rescue it, technically, though as we'll see BIP32 is still desir= able if we can use it.

A MuSig2 key is kind of like a hashed address. If EC spendi= ng is disabled, then you just need to prove knowledge of the secret keys wh= ich reproduce the address. 

Example aggregation of a MuSig2 key X=E2=80=8B using two peer pubkeys A and B:

A =3D a * G
B =3D b * G
X =3D A * int(H(A, A = || B)) + B * int(H(B, A || B))=E2=80=8B

If you can prove knowledge of a=E2=80=8B and b=E2=80=8B in a way that also comm= its that proof to a spending transaction, then you can spend X= =E2=80=8B but a CRQC cannot.

For example:

1. With a ZK= -STARK, the MuSig peers could cooperate to prove they know a correct = (a, b)=E2=80=8B pair which produce pubkeys (A, B)=E2=80= =8B such that:

x =3D= a * int(H(A, A || B)) + b * int(H(B, A || B))=E2=80=8B

...where the group secret key x= =E2=80=8B is written to the public output of the proof. A verifier c= ould then recompute X =3D x * G=E2=80=8B outside the circuit t= o validate a spend. Creating this proof demands we arithmetize two curve po= int multiplications and two hash function invocations, i.e. one mult and on= e hash per MuSig2 participant. Another downside is this would r= equire participants to trust each other and share private keys (or use MPC = to build the proof).

2. Alternatively, we can sacrifice performance = to reduce trust. Prove you know a correct set of pubkeys (A, B)<= /code>=E2=80=8B such that they recompute X=E2=80=8B using= MuSig key aggregation, and then prove you know a BIP340 signature from&nbs= p;X=E2=80=8B on a given transaction. This is similar to what&n= bsp;Kurbatov did in this recent post exploring STARKs for re= scuing hashed addresses without the need to export secret keys fro= m secure signing devices. This approach would let you prove a similar state= ment without the need to share privkeys between peers, at the c= ost of one extra point multiplication and an extra hash invocation - These = are needed to verify a Schnorr signature in the circuit.

Both proofs are hard for = an external QC to forge without knowing A=E2=80=8B and B= =E2=80=8B, and neither can be forged by non-quantum peers in the MuS= ig group. Though, if there is a quantum adversary in the MuSig group= , the group is screwed in either case. It'll still be very expensive to gen= erate either proof, and circuit complexity will scale linearly with the num= ber of MuSig2 signers. I think commit/reveal would be a better choice in th= is situation.

But... if the MuSig2 peer pub= keys A=E2=80=8B and B=E2=80=8B were derived using= a hardened BIP32 step or some other hash-based algorithm though, then we c= ould reuse Laolu's techniques to create a BIP32 proof which is secure even = against Quantum attackers inside the MuSig group. 
Peers could provide one BIP32 xpriv proof showing harde= ned derivation for each contributory secret key a=E2=80=8B and= b=E2=80=8B, and then let the verifier recompute A, B and X=E2=80=8B in software. The resulting circuit wo= uld be much faster and more efficient, because you only need to arithmetize= one HMAC call per peer; no point multiplication needed. A quantum attacker= in the MuSig group cannot forge any of their peers' proofs either, since t= hey do not know the preimages their peers used to generate their keys. Thou= gh you'd need one separate proof for every signer in the MuSig group, so it= 'd probably be wise to aggregate the proofs together, especially for larger= groups.

= ------------

As for FROST, I think that will be a harder p= roblem. It depends on how the threshold master key was constructed: Trusted= dealer, or distributed keygen (DKG).

With a trusted dealer, then = it depends how the dealer generated the master key. If the dealer used BIP32 and still hav= e the seed, then peers could ask the dealer to follow Laolu's techniques. I= f the dealer discarded the seed or if they didn't use some quantum-hard fun= ction on a (remembered) secret input to generate the key, then I think hope= is lost.

If the FROST key was generated using a DKG protocol, the= n unfortunately I don't think there is any quantum-hard asymmetry we can re= ly on there at all. FROST DKG doesn't use hash functions, it is all algebra= ic. A valid DKG execution for any secp256k1 point can be= easily simulated by a quantum attacker, since they can compute the FROST = group secret key and then break it up into valid DKG shares. It would ma= ybe be possible to rescue if ALL the DKG participants generate the= ir shares using a deterministic hash of secret input, because that'd be imp= ossible for a QC to simulate and forge. But IDK of any FROST implementation= s which do it that way.

=
regards,
conduitio= n
On Wednesday, April 15th, 2026 at 3:35 PM, Boris Nagaev <bnagaev= @gmail.com> wrote:
Hi Laolu, Abubakar, Conduition, list,

Does this idea ext= end to MuSig2 or FROST outputs, assuming the relevant parties cooperate dur= ing proving (or use some MPC) and collectively know the underlying seeds / = secret material?

For MuSig2, I can imagine a proof that each partici= pant key came from a BIP32 seed/path.
For FROST, I am less sure what the= analogous proof statement would be.

At least to me, MuSig2 seems li= ke it may be within reach. I would be very interested if someone has a conc= rete sketch in mind.

Best,
Boris

On Tuesday, April 14, 2026 at 10:54:51=E2=80=AFAM UTC-5 con= duition wrote:
Hi Abubakar,

Awesome point! A sin= gle STARK could be used to prove you knew an xpriv which derives the xpriv = at m/352'/coin'/account'=E2=80=8B. Then any verifier could eas= ily derive the private scan/spend keys m/352'/coin'/account'/0'/0=E2=80=8B or m/352'/coin'/account'/1'/0=E2=80=8B, then repl= icate the ECDH process (with some BIP352-specific tweaks that the spender can p= rovide), and add the result together. This reproduces the private ke= y of the SP taproot output being spent, proving the spender is authentic.

=
With = proper labeling of input metadata, this procedure could cover every UTXO in= a silent payment wallet, because the scan/spend keys are common to every d= erived output-specific address.

Curious why not generalise beyond BIP-32? P2PKH = and P2WPKH without BIP-32 still commit to an unrevealed secret =E2=80=94 HA= SH160(k=C2=B7G) =E2=80=94 as long as the pubkey has never previously appear= ed on-chain. A zk-STARK proof should apply here too? The prover argues for = the correctness of HASH160(k=C2=B7G) =3D h, where k is the private key scal= ar and k=C2=B7G is the elliptic-curve point, without ever revealing k or th= e pubkey. This would allow recovery of a broader set of funds.

I agree this type of thing would also be useful, bu= t it is harder to argue security for this than for BIP32 xpriv ownership.
=
Typically, xpubs and xprivs are not shared on-chain, and = wallets usually treat them with greater care since xpubs compromise privacy= , and xprivs compromise security.

Hashed address pubkeys on th= e other hand are commonly shared on-chain and almost never treated as sensi= tive. So it seems likely that if we DO permit spending using a ZK proof of = knowledge of k=E2=80=8B such that HASH160(k*G) =3D h=E2=80=8B, then some non-negligible fraction of those coins will still b= e vulnerable to a CRQC because k*G=E2=80=8B may be known to th= e attacker, which to a CRQC is equivalent to knowing k=E2=80= =8B.
=
T= o mitigate, a verifier would need to reject such proofs when someone tries = to spend coins locked to such an "exposed pubkey" address. Since bitcoin no= des do not maintain an address index, they don't intrinsically know which a= ddresses have exposed pubkeys or not. We would have to compose a list of su= ch addresses, and since that list changes over time, it would need to be up= dated by nodes in real-time when indexing transactions. This list will almo= st certainly be incomplete, because we don't have any record of pubkeys exp= osed off-chain (e.g. by hardware wallets, by xpubs shared in multi-party pr= otocols, by lost TXs in orphaned blocks).

This idea also collides very unfortunate= ly with the BIP32 xpriv proof of knowledge. With the faster proof style i s= uggested to modify Laolu's original one, a spender immediately gives up kno= wledge of their account-level xpriv to the CRQC when publishing a TX. Even = if the spender was using a hashed-address with a hidden pubkey, the CRQC no= w knows the secret key k=E2=80=8B for that address, and could = use it to forge a proof that h =3D HASH160(k*G)=E2=80=8B to at= tempt to double-spend/RBF the authentic transaction.

So we can't just add hashed-a= ddress proofs alongside BIP32 xpriv proofs. They'd have to be mutually excl= usive: A verifier would accept a BIP32 xpriv proof if and only if the addre= ss is on the "exposed pubkey" list. The verifier would accept a hashed-addr= ess proof if and only if the address is NOT on the "exposed pubkey" list. I= t's definitely feasible, it's just hard to do both safely.

This is also dif= ficult to motivate, as we lack hard statistics about the relevant portion o= f the Bitcoin supply that we could use hashed-address proofs (but not BIP32= proofs) to rescue: Those UTXOs which fall into the venn-diagram overlap of= "Not using BIP32" and "Not exposed-pubkey". BIP32 was introduced in 2012, = whereas P2PKH was introduced in 2009, so clearly there must be some = overlap, but how much? I suppose one could estimate by indexing all the P2P= KH UTXOs received before BIP32 was published, and counting what portion of = them still have (probably) hidden public keys. This would be useful researc= h for anyone with the time and a working node.

regards,
conduition
On Monday, April 13th, 2026 at 2:21 PM, sadiq Ismail <ask= 4ism...@gmail.com> wrote:
Hi Laolu, list,

Nice work.

The scheme extends to = BIP-352 (Silent Payments). The BIP-352 receiver reconstructs the output P u= sing their private scan key, public spend key, and public information from = the spending transaction A.
See BIP-352 Scanning. BIP-352 recommends but= does not mandate BIP-32 for deriving the scan and spend keys, but specifie= s the following derivation paths when BIP-32 is used:

b_scan = =3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0)
b_spend =3D BIP3= 2Derive(s, m/352'/coin_type'/account'/0'/0)

For all silent payment a= ddresses generated using BIP-32, your technique applies. The prover produce= s a zk-STARK proof that the program BIP32Derive(s, p_scan) and BIP32Derive(= s, p_spend) were run correctly,
and that the resulting keys reconstruct= the on-chain output P using along with A.

As you highlighted = txid is not committed in the proof currently, the argument is replayable. T= he current POC does not bind to where the coins go. Anyone who observes the= chain could copy it and attach it to a different transaction, spending the= same UTXO to a different address. Worse for silent payment, because all us= er UTXO have the same secret BIP32Derive(s, p_scan) and BIP32Derive(s, p_sp= end) except for A.
The zk-STARK proof? or this mechanism should d= efinitely be bound to the spending transaction and the input being spent. <= br>
Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without B= IP-32 still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2= =80=94 as long as the pubkey has never previously appeared on-chain. A zk-S= TARK proof should apply here too? The prover argues for the correctness of = HASH160(k=C2=B7G) =3D h, where k is the private key scalar and k=C2=B7G is = the elliptic-curve point, without ever revealing k or the pubkey. This woul= d allow recovery of a broader set of funds. If it were decided that classic= al signatures for these output types are invalidated and only a valid zk-ST= ARK proof is required to spend, anyone who holds the original secret can un= lock their funds.

P.S. I am not for or against di= sabling valid spend paths post-quantum, just discussing the technical possi= bilities.

Best,
Abubakar Sadiq
On Fri= day, April 10, 2026 at 7:47:09=E2=80=AFPM UTC+2 conduition wrote:
=
Ah! Amazing work! 2 seconds to prove is really crazy. Proving a single = SHA256 and one modular addition on my CPU back in the day took like 20 seco= nds. Your GPU is coming in clutch = for this. I best RISC0 has also improved quite a bit since then.

I th= ink the next optimization step would be pre-seeding the two SHA512 midstate= s from the host, so you only need to prove two SHA512 compression calls ins= tead of four. Intuitively I expect this would at best halve your prover tim= e from 2sec, to probably a little over 1sec, and your verifier time will pr= obably drop as well since that also seems to scale with circuit complexity.=

I think I have two half-decent arguments now as to why this won't af= fect security:

First, even if a fraudulent prover is handed the correct midstates to use, the prover would still have to d= o the hard work of finding the parent secret key needed as a witness. This = is at least the same difficulty as finding the parent sk=E2=80=8B=E2=80=8B if we just has= hed it without a chaincode at all, using two bare SHA512 calls - the only t= hing that changes is the midstate, and the SHA512 input length suffix. Star= ting from a different midstate doesn't magically give the attacker a head-s= tart in a 256-bit search space looking for sk=E2=80=8B. A frauduent prover would= know the child secret key k =3D sk + int(I[32:]) % n=E2=80= =8B=E2=80=8B, but the= y don't know int(I[32:]) or sk=E2=80=8B so they = cannot solve for either.

Nominally, the fraudulent prover wouldn't even know the co= rrect midstates, so their task is strictly harder.

Secondly, here's a= nother argument as to why finding the midstates in the first place should a= lso be hard.

A= ny adversary who could solve this problem by finding the right midstates co= uld be used as an oracle to prove the existence of partial 2-cycles in SHA5= 12.

  • Given a SH= A512 hash I=E2=80=8B= =E2=80=8B, set sk =3D int(I[32:])=E2=80=8B<= span style=3D"font-family: Arial, sans-serif;">=E2=80=8B=E2=80=8B
  • = Compute k =3D sk + sk % n=E2=80=8B<= /span>
  • Use t= he black-box fraudulent prover on the child key k=E2=80=8B=E2=80=8B to find correct midstates su= ch that

I =3D=3D = SHA512(<something> || SHA512(<something> || 0x00 || sk || i))=E2=80=8B=E2=80=8B=E2=80=8B
k =3D=3D int(I[32:]) + sk % n=E2=80=8B<= /span>
=3D=3D sk + sk % n=E2=80=8B=E2=80=8B
=

=
Remember tha= t sk =3D int(I[32:])=E2=80=8B=E2=80=8B. Thus for these conditions to hold, the pro= of forger must be able to find not just the correct midstates, but also mid= states which give a 2-stage partial hash cycle so that:
=

I =3D=3D SHA512(<something> || SHA512(<something>= || 0x00 || I[32:] || i))=E2=80=8B

<= /div>
This se= ems unlikely or at least very difficult.

r= egards,
conduition
=
On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun <lao...@gmail.com> wrote:
Hi Condution,

So I implemented both va= riants of your idea. My intuition was right in that it
doesn't do much t= o reduce the size of the final succinct size, but the final
xpriv varian= t resulted in a significant reduction in both proving time, and
also mem= ory usage. I also re-ran the original succint proof for the original
Tap= root claim and got a better value for the final proof time (def need a
b= etter benchmark env+set up!).

Here's a breakdown of the resource req= uirements for the various proofs:
* Full Taproot
image ID:
= 8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690
= composite:
seal 1797880
prove 49.32s
verify 0.= 10s
peak RSS 11907399680
succinct:
seal 222668
= prove 64.30s
verify 0.03s
peak RSS 11927207936
<= br> * Hardened xpub
image ID:
ad4ebc0ef6ce51e0f581cc8d14742a= 5b97738e9decd3fe2b0f1746de5bad9617
composite:
seal 513680 prove 14.63s
verify 0.04s
peak RSS 11783503872 succinct:
seal 222668
prove 17.29s
verify 0= .02s
peak RSS 11782307840

* Hardened xpriv
image I= D:
8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0df084= 9
composite:
seal 234568
prove 1.98s
veri= fy 0.02s
peak RSS 3144171520
succinct:
s= eal 222668
prove 2.84s
verify 0.02s
peak RSS 3145990144

So we can see that the succinct proof sizes are al= l about the same. However the
xpriv variant can be proved directly in ju= st 2 seconds on my machine! It also
requires just 3 GB of memory for the= proof as well.

I've created some additional supporting documentatio= n to detail exactly what
the new proofs do and their results:

*= https:= //github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/reduced-variants.md
* https://github.com/Roasbeef/= bip32-pq-zkp/blob/1c89fdb398180a2b3eff7761b7f4b233d455c6c9/README.md#reduce= d-proof-variants

* ht= tps://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5171f= 5e06fa840/docs/claim.md#reduced-variant-claims


Once again, t= hanks for the great ideas! I wonder if we can improve on this
round of p= roof golf further before reaching down a lower level with some sort
of A= IR compiler =F0=9F=A4=94.

-- Laolu

On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osuntok= un <lao...@gmail.com> wro= te:
Hi C= onduition,

> You need only prove this much more general statement= (2): "I know a BIP32
> xpriv which derives this xpub via one or more= hardened steps".

> I'm amending my prior suggestion slightly: Th= e circuit (guest program)
> could take in an xpriv (e.g. at m/86'/0')= and output a child xpriv
> (e.g. at m/86'/0'/0') to the journal (ins= tead of outputting a child
> xpub).

That's an excellent insig= ht!

As mentioned in my recent reply, with risc0's "succinct" receip= t type, I was
able to get the proof size down to 220 KB, at the cost of = 3.5x longer total
proving time.

Your proposal definitely reduces = the complexity of the core statement to be
proved, which would speed up = the proving time for the normal
default/composite receipt type.

= I'll try to hack this up, and then run a head to head comparison to see thi= s
simpler statement actually results in a smaller proof then the finalsuccinct receipt of either of the proof variants. Based on my current
= intuition w.r.t the lower level details, I think the final succinct proofsize would be on the same order of magnitude re size.

However, thi= s can still be a win as then this would provide potential future
users w= ith a less resource intensive proof, which can then be
aggregated/rolled= up into a final succinct proof in a batched manner.

This line of op= timization is also more interesting if one were to look at
hand rolling = a custom AIR to avoid the overhead that the RISC-V emulation
adds to the= rirsc0 proof chain, given that it entirely skips doing any EC
operation= s at all for the final statement.

----

Re the commit/reveal a= pproach, to be honest I'm not fully caught up on that
proposal. That ori= ginal thread got pretty long, so I dropped of after a
point =F0=9F=98=85= . I'll revisit that specific branch of the thread so I can digest it
and= develop a proper opinion, then get back to you re comparisons!

-- L= aolu


On Wed, Apr 8, 2026 at 1:= 23=E2=80=AFPM conduition <condu.= ..@proton.me> wrote:
Oh, I've been= a fool, a foolish fool.

We don't even need to do point multiplication in the circ= uit at all.

I'm amending my prior suggestion slightly: The circuit (guest program)= could take in an xpriv (e.g. at m/86'/0'=E2=80=8B) and output= a child xpriv (e.g. at m/86'/0'/0'=E2=80=8B) to the jo= urnal (instead of outputting a child xpub).

This is safe because remember,= EC spending has been disabled in this context, and to a quantum attacker, = an xpub is computationally equivalent to its xpriv. So why bother hiding it= ? The child xpriv doesn't give an observer anything they can't already do w= ith the equivalent xpub.

The guest program then is basically the BIP32 CKDpriv al= gorithm, restricted to a single hardened derivation step. The verifier gets= the child xpriv, but can't use it to forge new proofs. Honest verifiers us= e the xpriv to derive the child address(es) as suggested in my last message= , to authenticate spending.

Designing the guest program like this will massively r= educe your circuit complexity, because EC point multiplication is wayyyy= y harder for the RISC0 compiler to arithmetize than a simple hash funct= ion. In my prior work with RISC0, I made a guest program which ran a SHA256 h= ash and an EC point multiplication. I found that pruning EC point arithmeti= c from my guest program improved prover runtime by a factor of over 100x.

If I am = not fever-dreaming and this is indeed possible, then the new circuit's comp= lexity will be dominated not by point multiplication, but by the HMAC-SHA51= 2 call. Our new task is then to figure out how much we can internally optim= ize the HMAC-SHA512 call for STARK proving. Here's a few ideas.

If you bust open H= MAC-SHA512, it looks like this:

HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c= ) || SHA512((K=E2=8A=950x36) || msg))=E2=80=8B <= /div>

...wher= e in the context of BIP32 hardened CKD, the HMAC key K=E2=80= =8B is the chaincode (padded with zeros to 128 bytes) and msg =3D (0x= 00 || sk || i) is the parent secret key and child index.

Since len(K= ) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we need a tota= l of 4 SHA512 compression calls:
  1. to compress (K=E2=8A=950x36)=E2=80=8B
  2. to compress the msg=E2=80=8B (and SHA5= 12 padding/length)
  3. to compress (K=E2=8A=950x5c), and
  4. a final compression call to tie it all together.

The output of that last compression call is partitioned into the child = chaincode, and a key delta which is added to the parent secret key (modulo = the curve order), producing the child EC secret key. This last st= ep is arithmetically simple; the SHA512 calls are where most of the arithme= tic complexity lies.

The question then becomes, which of these compress= ion calls can be done outside the circuit, and which are truly essential fo= r security?

Note how the parent secret key is the most important piece for soundn= ess. The circuit needs to prove the parent secret key existed in the hash f= unction preimage, and is correctly related to the child secret key via modu= lar addition. So compression call (2) seems unavoidable. The others are les= s rigid.


Given= a child xpriv with secret key k=E2=80=8B, chaincode c=E2=80=8B and index i=E2=80=8B, I kn= ow a preimage x=E2=80=8B and sec= ret key sk=E2=80=8B such that:

I <- SHA51= 2(<something> || SHA512(<something> || 0x00 || sk || i)= =E2=80=8B)
c =3D=3D I[:32]=E2=80=8B
k =3D=3D int(I[32:]) + sk % n=E2=80=8B

Seeing as the <something>=E2=80=8B slots are arb= itrary, and we know in BIP32 they are always exactly one-block long, it see= ms easy to throw out the compression calls (1) and (3). The host can precom= pute the relevant SHA512 midstates outside the circuit, and pass the midsta= tes into the guest program as secret inputs. The tradeoff is that this permits = malicious provers the flexibility of choosing their starting midstates (tho= ugh hash input length can be fixed at 192 bytes). I'm not entirely sure if = this meaningfully weakens the verifier's soundness. Ethan Heilman might hav= e opinions on this, he knows a lot more about attacking hash functions than= I do. Intuitively, I doubt sampling random SHA512 midstates is that much b= etter than sampling a random HMAC key (chaincode) K=E2=80=8B a= nd computing the resulting midstates.

Thi= s reduces our circuit to, i think, the minimum acceptable security floor fo= r provers: two SHA512 compression calls, which commit to a parent secret ke= y.


regards,
conduition
On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via Bitcoin= Development Mailing List <bitco= ...@googlegroups.com> wrote:
Hi Laolu,

Great work getting this wo= rking in the real world. I've heard many people on delving and the mailing = list conjecture based on this idea, but you're the first person i've seen w= ho's willing to put their money where their mouth is, and actually build a = prototype. Bravo!

It seems to me the circuit (gues= t program) could be simplified. Notice how the guest code computes the entire HD wallet key path, = including hardened and non-hardened deriva= tion steps, and also computes the taproot output key with key-tweaking. I'd= argue these steps are extraneous to the core hard relation you want the ST= ARK to prove, and could be safely removed to reduce proof size and improve = performance.

In reality, you needn't go so far as = to prove (1) "I know a BIP39 seed which derives this taproot output key"= . You need only prove this much more general statement (2): "I know = a BIP32 xpriv which derives this xpub via one or more hardened steps". = The latter statement (2) still cannot be forged by a quantum adversary even= if they know your account-level xpub, but it entails far less computation = to prove and verify. The rest of the original statement (1) can be done ext= ernally outside the circuit.

Example. If i have a = wallet with a taproot address at m/86'/0'/0'/1/2= =E2=80=8B, I could prove I know the xpriv at m/86'/0'=E2=80=8B which derives the xpub at m/86'/0'/0'=E2=80=8B. Then I provide the remaining key path elements /1/2=E2=80=8B in the witness. Note, i do not mean we d= erive the xpriv at m/86'/0'=E2=80=8B inside t= he guest program. I mean the prover derives m/86'/0'=E2=80=8B first (in the host), and then writes that xpri= v into the guest program's inputs. The guest program derives and output= s the xpub at m/86'/0'/0'=E2=80=8B. The verifier = may check the STARK output (xpub) is correctly computed, then use the given= key-path to manually derive the taproot address from the xpub themselves, = outside the circuit, and validate that address against = the UTXO i'm spending. The verifier thus has confirmed the prover knew an x= priv which (through a hardened derivation step) derives the correct taproot= output key.

This change significantly reduces the= size of the circuit. From a glance, I see the original guest program perfo= rms 6 HMAC-SHA512 calls (1 for the master key, 5 for the BIP32 derivation s= teps), two SHA256 compression calls (for the taptweak hash), and two point = multiplications. With this simplified variant, we are invoking only a singl= e HMAC-SHA512 call and a single point multiplication. I can't say for sure,= but I expect this will improve your proof size and runtime significantly.<= /div>

This change also makes the circuit more generally = applicable to other rescue contexts. For instance, it could be applied to B= IP340 xonly keys inside a taproot script tree, or in a P2(W)SH address to a= n ECDSA public key, or to P2(W)PKH addresses.

Concerned ab= out publishing xpubs? Remember that we are assuming regular EC spending is = locked in this context, so it is safe-ish to share account xpubs with quant= um attackers. At best the xpub can be used for surveillance but not forgery= . If one would prefer not to share the account-level xpub on-chain f= or privacy reasons, the proof could be extended to also derive the unharden= ed child xpub at /1/2=E2=80=8B inside the guest program (but we still do not need to d= o the taproot key tweaking in the guest program).

=
We should also talk scaling efficiency. Given the cost of STARKs= , this style of proof should be able to authorize spends for more than one = UTXO. Say you have a wallet with 10 different UTXOs held by distinct addres= ses in the same BIP44 account. One single STARK proof could authorize spend= ing all 10 of them, by simply committing all 10 input signature hashes into= the journal, and labeling the inputs with the corresponding 10 BIP32 key paths = somehow. The verifier would need to check the proof only once= and not 10 times. The 10 UTXO spends could be validated using the common x= pub from the STARK proof's journal.

For a slightly= related work proving a similar relation for hashed addresses, using differ= ent STARK technology stacks, see this de= lving post.

However, all this said, my persona= l preference for long-term procrastinator rescue is still for commit/reveal= strategies which prove essentially the same statement about BIP32 in a two= -step procedure. They get the job done with much lighter cryptographic mach= inery and much smaller witnesses: a few hundred bytes over two transactions= , compared to a few million bytes in one transaction with STARKs. Boris Nagaev and I discussed this on the list= a while back. That said, commit/reveal requires more careful design an= d seems to demand the use of external quantum-safe coins to make the commit= ment in the first place, so perhaps the cost would be worth it to some peop= le? IDK. What do you think of commit/reveal compared to STARKs for this pur= pose?

regards,
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <<= a rel=3D"noreferrer nofollow noopener">lao...@gmail.com> wrote:
Hi y'all,
I found some spare time this last weekend to dust off a little side pr= oject
I started last August: extend TinyGo [1] to be able to produce RIS= C-V ELF
binaries capable of being run as a guest on the risc0 platform t= o generate
zk-STARK proofs of arbitrary programs. Initially, I didn't re= ally have a
clear end target application, it was mainly a technical chal= lenge to force
me to learn a bit more about the RISC-V platform, and als= o the host/guest
architecture of risc0. Fast forward ~9 months later, an= d an initial killer
use case popped into my mind: a zk-STARK proof that = a Taproot output public
key was generated using BIP-32, via a given BIP-= 86 derivation path.

More formally:
```math
\mathcal{R} =3D \le= ft\lbrace\;
(\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{s,\, \= mathbf{p}}_{\textsf{witness}})
\;\middle|\;
\begin{aligned}
K &a= mp;=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,\, \mathbf{p})\big= r) \\
C &=3D \textsf{SHA256}\bigl(\texttt{"bip32-pq-zkp:path:v1"} = \;\|\; \mathbf{p}\bigr)
\end{aligned}
\;\right\rbrace
```

w= here $K$ is the Taproot output key, $C$ is the path commitment, $s$ is the<= br>BIP-32 seed, and $\mathbf{p}$ is the derivation path.


I was a= ble to get everything working e2e over the weekend, after making
some tw= eaks to my initial architectural game plan!

The TL;DR is that:
* Given that the Taproot commitment scheme is post-quantum secure [3], = in
the future we can deploy a soft fork to _disable_ the keyspend pa= th,
and force all Taproot spends to instead flow through the script = path
(not my idea, commonly discussed amongst developers, not sure w= ho
proposed it first). At that point, Taproot starts to resemble BIP= -360.

* That works for script path spends, but then leaves all the= BIP-86
wallets in a bad position, as they generated outputs that pr= ovably
don't commit to a script path at all.

* A 2023 paper= (Protecting Quantum Procrastinators with Signature
Lifting: A Case = Study in Cryptocurrencies [4]) proposed a solution to this,
namely _= seed lifting_ (use BIP-32 as the one-way function to the
Picnic PQ S= ignature scheme) to provide a post-quantum proof of secret
informati= on a quantum attacker wouldn't be able to easily obtain.

* The dow= nside of that is that it reveals the secret BIP 32 seed,
exposing ot= her non migrated UTXOs of a user.

* With this project I've cobbled= together a series of projects to be able
to generate a zk-STARK pro= of that a Taproot output public key was
generated via BIP-32 invocat= ion of a BIP-86 derivation path.

* In the future a variant of this= scheme can be used to enable wallets
that generated the private key= s via BIP-86, to have a post quantum safe
exit path in case they don= 't bother moving their coins in time to the
yet-to-be-decided post q= uantum signature scheme.

To achieve this end, I needed to create/for= k a series of repos:

* tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm
* A fork of TinyGo tha= t supports the flavor of RISC-V (rv32im) that
risc0 requires to ge= nerate/execute a guest program to later be proved
by the host.
=
* risc0: https://github.com/Roasbeef/risc0<= /a>
* Mostly a bug fix to their c-guest example, along with some
= additional documentation on how to get things running. The repo is unmodified other than that. Recent updates to the repo made the
= entire process much easier (Go guest+host), more on that later.
* go-zkvm: https://github.com/Roasbeef/go-zk= vm
* Go utilities to take a RISC-V ELf binary produced by tinygo= -zkvm, and
package it in the expected R0BF format, which combines = the user
generated RISC-V ELF (the thing that is executed to gener= ate the
proof) along with the v1compat ELF kernel, which is risc0'= s execution
environment.

* This also includes a Go host= package, which loads the guest program,
executes it, and generate= s a trace to later be proved. This is
achieved via a C FFI compat = layer between Go and the original Rust
host/proving/verification c= ode.

* bip-32-pq-zkp: https://git= hub.com/Roasbeef/bip32-pq-zkp
* The project that packages everyt= hing together, this contains the:
* Guest Go program that defines = the secret witness and
claim/constraints of the proof.

= * The C FFI wrapper around the OG Rust host, which is used to load
= the guest program, execute it, generate a trace, then finally
= generate a proof.

Details of the final proof as generated on my= Mac Book (Apple Silicon M4
Max, 128 GB of RAM):
* Takes ~55 second= s or so to generate+proof, including execution. This
uses Metal for = GPU acceleration on the platform.
* Uses ~12 GB of ram.
* Final p= roof size is ~1.7 MB.
* Verification takes ~1.8 seconds, and uses ~32 = MB of memory.

On several layers, this demo is far from optimized (mo= re on that later),
this is meant to serve as a PoC to demonstrate that w= ith the latest
software+hardware, a proof of this complexity is well wit= hin reach.

For those curious re the e2e details I've generated this = tutorial that
explains the entire system top to bottom:
https://github.com/Roasbeef/go-zk= vm/blob/main/docs/tutorial.md.

If you got to this point in this = mail, and don't care about the lower level
details, thanks for reading u= p until now, and feel free to return back to
the _The Net of a Million L= ies_, or as better known in our Universe:
Monitoring the Situation and/o= r slopfotainment! =F0=9F=AB=A1

## Motivation + Background

As = commonly known, in the case of an adversary that possesses a quantum
com= puter capable of breaking classical asymmetric cryptography, any coins
s= tored in UTXOs with a known public key are vulnerable. This is the case
= for any P2PK outputs from waaaay back, and also any other outputs that have=
revealed their public key. Pubkey reveal might happen due to address re= -use
(spending from the same script twice), or Taproot outputs, which pu= blish
the public key plainly in the pkScript.

As detailed in [3],= for Taproot outputs, a widely circulated plan is
roughly to: disable th= e _keyspend_ path (requires a simple signature),
enforcing a new rule th= at all Taproot spends must then flow through the
script path. Spending v= ia the script path requires an opening of the
Taproot commitment (C =3D = I + H(I || H(M))), which was shown to be binding even
under classic assu= mptions, as H(M) (tapscript merkle root) is still a
collision-resistant = function.

That means any UTXO that _does_ commit to a script path ha= s a future escape
hatch _if_ such a softfork would need to be deployed i= n the future.
However, what about all the other wallets that use BIP 86,= and don't commit
to a script path at all? Under a strict version of thi= s existing
proposal, those wallets would basically be locked forever.
The goal of this work is to demonstrate a practical solution (discusse= d
against devs, but never implemented AFAICT): generate a zk proof that = an
output was generated using BIP-86. For the zk-Proof, we select zk-STA= RKs,
as they're plausibly post quantum since they rely only on symmetric=
cryptography: layers of merkle trees over an execution trace, along wit= h
some novel sampling/error-correction algorithms.

At this point,= you may be asking: "if the quantum adversary can derive the
private key= to a random taproot public key, then how exactly does this
help?". The = answer lies in the structure of BIP-32! BIP-32 takes an initial
128-512-= bit seed (with BIP-39, either 12 or 24 words), then runs it through
HMAC= -SHA512 keyed by "Bitcoin seed" to produce the master extended private
k= ey. An adversary who wants to forge this proof needs to find a _colliding_<= br>seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s') prod= uces
the same master key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) is= the
best known quantum collision finder, and it runs in time proportion= al to the
cube root of the output space: 2^(n/3). For HMAC-SHA512's 512-= bit output,
that's ~2^171 quantum operations, well above even NIST's hig= hest
post-quantum security category. Therefore, if you generated a walle= t using
BIP-32, you possess _another_ secret that a quantum adversary ca= n't
efficiently reconstruct!

This demo focuses on the Taproot cas= e, but the rough approach also applies
to any other output generated via= BIP-32. BIP 32 was originally published in
2012, over 14 years ago. So = safe to say that _most_ wallets were generated
under this scheme. Howeve= r, Bitcoin Core only officially adopted BIP-32 in
2016/2018, moving away= from their existing key pool structure. I can't say
how much BTC is hel= d today in outputs generated with Bitcoin Core's original
key pool, but = if you have coins generated via that mechanism, you may want
to consider= migrating them to a BIP-32 wallet.

## TinyGo + RISC-V + risc0
Now for some of the lower level details. risc0 is a STARK based provingsystem that takes a RISC-V ELF binary generated by a guest program (anyprogram generating using their flavor of rv32im can be proved), executes<= br>that in a host environment, generates a trace, then produces a STARK pro= of
from that.

Today you can take some subset of Rust, compile it = to an ELF using their
toolchain, then execute it, generate a trace, to f= inally prove+verify it
using their system.

This demo took a bit o= f a round about journey to achieve this, as after
all, the journey is mo= st of the fun, ain't it!

For the past 10 years or so, my Bitcoin sta= ck of choice (lnd/btcsuite) uses
a series of Go libraries, so I wanted t= o be able to re-use them, first for
this demo, then also in the future f= or other projects.

TinyGo is a special Go compiler based on LLVM, th= at targets mostly embedded
environments. You can use it to generate go p= rograms that can run on
micro controllers, or on web assembly (producing= a smaller binary than if
you used the normal stdlib path).

TinyG= o supports RISC-V, but _not_ the 32-bit variant of RISC-V that risc0
rel= ies on. So the first step here was to create a new target definition forTinyGo: riscv32-unknown-none, which uses base integer + multiply/divideinstructions with no compressed instructions, which uses 4 KB stacks foreach task. From there, I created a new linker script
(`targets/riscv32= im-risc0-zkvm-elf.ld`) which created a memory layer
identical to what ri= sc0 expects. The final component was a new runtime
(`src/runtime/runtime= _zkvm.go`), which implemented a few platform specific
syscalls for risc0= (putchar(), exit(), ticks(), and growHeap()).

When I tried to get t= his working last year, I had to also implement a number
of kernel syscal= ls (called ecalls in the platform [7]) to handle: read+write
to stdin/st= dout, halting, and the journaling mechanism (the transcript of
execution= committed to), which basically implement the kernel that the guest
exec= utes in. Fast forward to 2026, and after pulling the latest version of
t= he repo, I realized that they now make a libzkvm_platform.a, which packages=
up the kernel nicely to be linked against. So I threw out my custom ker= nel
code, and slotted that in instead.

The final component is a C= FFI layer that enables me to use _both_ a Go
guest (the program to be p= roved) and a Go host (the thing that executes the
program and generates = the final proof).

## BIP-32+Taproot zk-STARK Proof

With basic= proofs working (like the classic: I know the factorization of a
number = `n`), I was unblocked to generate the actual proof. The claim/proof
is r= epresented with the following JSON artifact:
```
{
"schema_versi= on": 1,
"image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac= 077cbe70907a690",
"claim_version": 1,
"claim_flags": 1,
"req= uire_bip86": true,
"taproot_output_key": "00324bf6fa47a8d70cb5519957dd= 54a02b385c0ead8e4f92f9f07f992b288ee6",
"path_commitment": "4c7de33d397= de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b",
"journal_hex":= "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992= b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b", "journal_size_bytes": 72,
"proof_seal_bytes": 1797880,
"recei= pt_encoding": "borsh"
}
````

The `image_id` is basically a has= h of the ELF, so you know what the prover
executed. There are then a few= flags that control the claim version and
whether BIP-86 derivation is a= part of the proof. BIP-86 was only adopted
post-Taproot, so if you have= an existing BIP-44 path, you can instead opt to
claim that instead. The= Taproot key we're generating the proof against is
also part of the _pub= lic data_, as it sits plainly on the chain for all to
see. We then also = include a `path_commitment`, which is a commitment to the
exact BIP 86 p= ath that the prover used. Finally, we also commit to the
journal hex, wh= ich is basically a commitment to the public claim.

Assuming you've b= uilt the project, then you can generate the proof (even
passing in an ar= bitrary BIP-32 seed and derivation path with)
```
make prove GO_GOROO= T=3D/path/to/go1.24.4
```

Then verify it with:
```
make ver= ify GO_GOROOT=3D/path/to/go1.24.4
```

The default prove target wr= ites:
* ./artifacts/bip32-test-vector.receipt
* ./artifacts/bip32= -test-vector.claim.json

The receipt is the STARK proof artifact. cla= im.json is the stable,
human-readable description of the public statemen= t being proved.

## Application to a Future Keyspend Disabling Soft f= ork

As mentioned above, assuming the community is forced to deploy a= keyspend
disabling soft fork in the future, we can also deploy some var= iant of
this proof to enable both BIP-86 wallets, and also any BIP-32 wa= llet, to
sweep their funds into a new PQ output.

In 2026, we've s= hown that this is achievable using 2 year old consumer
hardware. I don't= doubt that the upcoming advancements (eg: photonics, new
flavor of high= bandwidth memory, etc) in hardware (driven by the fierce AI
race) will = make such a proof even more feasible.

One thing to note is that this= proof has a few layers of indirection,
mainly the RISC-V layer that add= s overhead which increase the total amount
of steps, and therefore the s= ize of the proof. A production grade
deployment would likely instead han= d roll a custom STARK proof for this
exact statement, to achieve a faste= r and smaller proof).

# Future Work

In terms of future work, = there're a number of interesting following up
projects that can be pursu= ed from here.

One basic one is that the current proof doesn't actual= ly commit to a
spending txid and/or sighash. That can be trivially incor= porated into the
proof. Going a step further, the execution of the guest= program can even
_generate_ a valid schnorr signature to permit spendin= g.

Looking to the memory+computational requirements necessary to gen= erate the
proof, I've left two low hanging fruits:

1. First, we = can speed up the Elliptic Curve operations the proof requires
(scala= r base mult, then addition, or more performantly Double Scalar
Multi= plication via the Strauss-Shamir trick). For this we can use the
sys= calls/precompile in the risc0 env for big integer arithmetic:
sys_bi= gint and sys_bigint2. With this, the guest calls into the kernel
to = use an optimized/accelerated circuit for the modular arithmetic,
red= ucing cycles, steps, and thus proof size.

2. Second right now, the = entire claim is a single proof. Instead, we can
first break that up = using their recursive proof/composition syscalls:
sys_verify_integri= ty+sys_verify_integrity2. We can then assembled a
series of these pr= oofs into a _single_ statement, which can save block
space by aggreg= ating N proofs into a single proof.

-- Laolu

[1]: https://tinygo.org/

[2]: https://risczero.com/

[3]: https://eprint.iacr.org/2025/1307<= /a>

[4]: https://eprint.iacr.org/2023/362

[5]: https://microsoft.github.io/Picn= ic/

[6]: https://en.wikipedi= a.org/wiki/BHT_algorithm

[7]: https://github.com/Roasbeef/go-zkvm/blob/main/d= ocs/ecall-reference.md

--
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+...@googlegroups= .com.
To view this discussion visit https://grou= ps.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TV= wUf_AYcd_qQ%40mail.gmail.com.

--
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+...@googlegroups= .com.
To view this discussion visit https://groups.google.com/d/msgid/b= itcoindev/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxL= CnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNEYg%3D%40proton.me.

--
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+...@googlegroups= .com.

--
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+...@googlegroups.com.
<= div>
To view this discussion visit https://groups.google.com/= d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee87626def65n%40googlegroups.com= .

--
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/2482176b-1ad7-4216-b1e7-2c03265425een%40googlegroups.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/HGkQFM= rHgWdd2wMH_rfcA_TrpBdZOqINcFWSamzCvVvtfh_gu7-tH86u1ufHKDftQrKfrY1h5AaJuhf24= PPz2ZN4a6rUdpvMva4Y_tHY2Ek%3D%40proton.me.
-----------------------91c9a8c9f4380939340a74708d408240-- -----------------------3061c550b94548b7fb54191d629abdaf-- -----------------------99421436611be78833abedda48d60b49 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== -----------------------99421436611be78833abedda48d60b49-- --------1c8c98f29fc9c5b22be7584a0f0687b05ddf0da81877e967ed88fbf615138a5d Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmniYyYJEHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmdMmNMxTh7tnzllp5P8NJQ+b0hUrLN/bS/703zf L+WjgBYhBEdIka0CMtrLdg13a3gpbO2E9rPFAABvLgEAuuqOhW/6oYo96Oqc gaa5BKkQ6/MMMpRNDVIXC3Fc/OQA/0puAU1776/OLQhyU+Ix+stROgzMgQbg e8fAx3zijoMI =knZ7 -----END PGP SIGNATURE----- --------1c8c98f29fc9c5b22be7584a0f0687b05ddf0da81877e967ed88fbf615138a5d--