From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 15 Apr 2026 14:35:24 -0700 Received: from mail-oa1-f58.google.com ([209.85.160.58]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wD7tI-0002Vg-3G for bitcoindev@gnusha.org; Wed, 15 Apr 2026 14:35:24 -0700 Received: by mail-oa1-f58.google.com with SMTP id 586e51a60fabf-423780ec681sf1487191fac.0 for ; Wed, 15 Apr 2026 14:35:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1776288914; x=1776893714; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=JTYarfFLrZ3KwD9DXDY9wPpiM1UWrHcvTbhWZNJlplU=; b=TytBgTVsEH/6XpEwaw0e+gus5UHv/E07zfJNnCIzm5wQmJPTWNWfzpif5SjwrBNjYW RLlqZT4zkByIljkufxpP+ThvANzBdIZclNK3QYBl+rG3l43uDozLukzafoPPMn4kPtEX 5BICO1L2eWjzy1fTgrU6A4m6zL2rjSZRznH3/JKqkC7aWlBexkLxTjmRfY0y/3qLmQr4 6/4vHQvol8ConqMZtzjyJRkKvkrPEntF/U0tNLT72VPNBgOab9otA8TgqX2vRcXMA9zl f7ffWee06f52OQi25doZcdtmeypV3yC5gMZ8GAjpSl+1jpEIyBC/9F/kXfndaTAoXjZY luNg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1776288914; x=1776893714; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=JTYarfFLrZ3KwD9DXDY9wPpiM1UWrHcvTbhWZNJlplU=; b=T4YY9XrORkiXpwua39/Kuo0k4ndHyjUzIfasBDDBRRNf4XPP0snTcn+1bg4rXmVy2+ PCeA5T+tutSnajND9TOzD00Z0Ihb7FgWipl9Jmk6b757fnoSz4/ksY+JZPnyx7U4ZH1/ kJnTMmL68MtT90nDGaA3GfAIIqFKZtcgmzGzEcTE9h2M3hOsU8AxOzPB08PrXRSJDIX5 y9UiigLQTXnQgRtutwx7A/ipc/ltAbuU2t+gavw0Y66pvj8FUzIgLJTCqZfTB4YaEyT3 O2YOfqGl7ByD1lHgu5cd7Hjoya+7lplNx02VeNnjvpS9gmJpNeUSq4flXv1nSsNAAqfX b4+g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1776288914; x=1776893714; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=JTYarfFLrZ3KwD9DXDY9wPpiM1UWrHcvTbhWZNJlplU=; b=XBbDOmPct7aNsXi7PdsNVPo3ulrSWfaScaeVzV/xPJl433lPBRacDsW0aLI/WtgbdT ewc5THYNnH5P5N8o8ram3eBFmnIzaf3lK+17UKoxcdNjZPDZci8Kw4x5n0DsgXn62vOc wASzCbO4I/x5WTcrVrsVhL4o/+6oLurGEYWipNXygIIlDMEqT5CUIGsC/dKxu1bqSkIP Gx+Iq1mbddI5PdMJVvKyLj/4jG3Fup9l8Zb2T692JsHWCRV22BHCEqWXJgLkdEsHasuH +otfAU/Z3tdL/k0EJWJELEbwXymcLHgFrtjU7MEmAK+zHy2KMr6N2FPr/VT5sPiWYZHS R3Lw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ85jxvQMO35ej6UGnozYqfHt6ymw3xRl1VSjxNcYoHosYZq23pSm/t+iwMhKVSjHhoLLcd5KS1mqtJK@gnusha.org X-Gm-Message-State: AOJu0YxE0sFMM4N/RWwkefLHsX5MkhmBZN16OmyFUakDiEllqlzD5A08 roMzVF8TJAyrWiVWXa1vRLl0q/RmSzqIA8l4Fvw/baDUjmRmoCCj+pWJ X-Received: by 2002:a05:6870:2c47:b0:417:a88e:6115 with SMTP id 586e51a60fabf-42612e546f9mr1731246fac.8.1776288913481; Wed, 15 Apr 2026 14:35:13 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiJQHE+BRO3UC9JVDygn96EYT1efByEUKfTAf8vZf86BQA==" Received: by 2002:a05:6870:1681:b0:41c:65ea:68a1 with SMTP id 586e51a60fabf-4280bda07bels132052fac.0.-pod-prod-03-us; Wed, 15 Apr 2026 14:35:09 -0700 (PDT) X-Received: by 2002:a05:6808:654a:b0:479:3a08:b4ff with SMTP id 5614622812f47-4793a08d1bfmr5860315b6e.7.1776288909027; Wed, 15 Apr 2026 14:35:09 -0700 (PDT) Received: by 2002:a05:690c:5512:20b0:7b3:443:26a9 with SMTP id 00721157ae682-7b8ae4839cfms7b3; Wed, 15 Apr 2026 14:34:13 -0700 (PDT) X-Received: by 2002:a05:690c:e3ed:b0:7b3:3a49:756 with SMTP id 00721157ae682-7b33a492721mr141517707b3.25.1776288852679; Wed, 15 Apr 2026 14:34:12 -0700 (PDT) Date: Wed, 15 Apr 2026 14:34:12 -0700 (PDT) From: Boris Nagaev To: Bitcoin Development Mailing List Message-Id: <2482176b-1ad7-4216-b1e7-2c03265425een@googlegroups.com> In-Reply-To: References: <02378fd1-17a4-47aa-89fa-ee87626def65n@googlegroups.com> Subject: Re: [bitcoindev] Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_140794_1423171124.1776288852002" X-Original-Sender: bnagaev@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_140794_1423171124.1776288852002 Content-Type: multipart/alternative; boundary="----=_Part_140795_659489989.1776288852002" ------=_Part_140795_659489989.1776288852002 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Laolu, Abubakar, Conduition, list, Does this idea extend to MuSig2 or FROST outputs, assuming the relevant=20 parties cooperate during proving (or use some MPC) and collectively know=20 the underlying seeds / secret material? For MuSig2, I can imagine a proof that each participant key came from a=20 BIP32 seed/path. For FROST, I am less sure what the analogous proof statement would be. At least to me, MuSig2 seems like it may be within reach. I would be very= =20 interested if someone has a concrete sketch in mind. Best, Boris On Tuesday, April 14, 2026 at 10:54:51=E2=80=AFAM UTC-5 conduition wrote: Hi Abubakar, Awesome point! A single STARK could be used to prove you knew an xpriv=20 which derives the xpriv at m/352'/coin'/account'=E2=80=8B. Then any verifie= r could=20 easily derive the private scan/spend keys m/352'/coin'/account'/0'/0=E2=80= =8B or=20 m/352'/coin'/account'/1'/0=E2=80=8B, then replicate the ECDH process (with = some=20 BIP352-specific tweaks that the spender can provide), and add the result=20 together. This reproduces the private key of the SP taproot output being=20 spent, proving the spender is authentic. With proper labeling of input metadata, this procedure could cover every=20 UTXO in a silent payment wallet, because the scan/spend keys are common to= =20 every derived output-specific address. Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BIP-32= =20 still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2=80=94 = as long as the pubkey=20 has never previously appeared on-chain. A zk-STARK proof should apply here= =20 too? The prover argues for the correctness of HASH160(k=C2=B7G) =3D h, wher= e k is=20 the private key scalar and k=C2=B7G is the elliptic-curve point, without ev= er=20 revealing k or the pubkey. This would allow recovery of a broader set of=20 funds. I agree this type of thing would also be useful, but it is harder to argue= =20 security for this than for BIP32 xpriv ownership. Typically, xpubs and xprivs are not shared on-chain, and wallets usually=20 treat them with greater care since xpubs compromise privacy, and xprivs=20 compromise security. Hashed address pubkeys on the other hand are commonly shared on-chain and= =20 almost never treated as sensitive. So it seems likely that if we DO permit= =20 spending using a ZK proof of knowledge of k=E2=80=8B such that HASH160(k*G)= =3D h=E2=80=8B,=20 then some non-negligible fraction of those coins will still be vulnerable= =20 to a CRQC because k*G=E2=80=8B may be known to the attacker, which to a CRQ= C is=20 equivalent to knowing k=E2=80=8B.=20 To mitigate, a verifier would need to reject such proofs when someone tries= =20 to spend coins locked to such an "exposed pubkey" address. Since bitcoin=20 nodes do not maintain an address index, they don't intrinsically know which= =20 addresses have exposed pubkeys or not. We would have to compose a list of= =20 such addresses, and since that list changes over time, it would need to be= =20 updated by nodes in real-time when indexing transactions. This list will=20 almost certainly be incomplete, because we don't have any record of pubkeys= =20 exposed off-chain (e.g. by hardware wallets, by xpubs shared in multi-party= =20 protocols, by lost TXs in orphaned blocks). This idea also collides very unfortunately with the BIP32 xpriv proof of=20 knowledge. With the faster proof style i suggested to modify Laolu's=20 original one, a spender immediately gives up knowledge of their=20 account-level xpriv to the CRQC when publishing a TX. Even if the spender= =20 was using a hashed-address with a hidden pubkey, the CRQC now knows the=20 secret key k=E2=80=8B for that address, and could use it to forge a proof t= hat h =3D=20 HASH160(k*G)=E2=80=8B to attempt to double-spend/RBF the authentic transact= ion. So we can't just add hashed-address proofs alongside BIP32 xpriv proofs.=20 They'd have to be mutually exclusive: A verifier would accept a BIP32 xpriv= =20 proof if and only if the address is on the "exposed pubkey" list. The=20 verifier would accept a hashed-address proof if and only if the address is= =20 NOT on the "exposed pubkey" list. It's definitely *feasible*, it's just=20 hard to do both safely. This is also difficult to motivate, as we lack hard statistics about the=20 relevant portion of the Bitcoin supply that we could use hashed-address=20 proofs (but not BIP32 proofs) to rescue: Those UTXOs which fall into the=20 venn-diagram overlap of "Not using BIP32" and "Not exposed-pubkey". BIP32= =20 was introduced in 2012, whereas P2PKH was introduced in 2009, so clearly=20 there must be *some* overlap, but how much? I suppose one could estimate by= =20 indexing all the P2PKH UTXOs received before BIP32 was published, and=20 counting what portion of them still have (probably) hidden public keys.=20 This would be useful research for anyone with the time and a working node. regards, conduition On Monday, April 13th, 2026 at 2:21 PM, sadiq Ismail = =20 wrote: Hi Laolu, list, Nice work. The scheme extends to BIP-352 (Silent Payments). The BIP-352 receiver=20 reconstructs the output P using their private scan key, public spend key,= =20 and public information from the spending transaction A. See BIP-352 Scanning. BIP-352 recommends but does not mandate BIP-32 for=20 deriving the scan and spend keys, but specifies the following derivation=20 paths when BIP-32 is used: b_scan =3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0) b_spend =3D BIP32Derive(s, m/352'/coin_type'/account'/0'/0) For all silent payment addresses generated using BIP-32, your technique=20 applies. The prover produces a zk-STARK proof that the program=20 BIP32Derive(s, p_scan) and BIP32Derive(s, p_spend) were run correctly,=20 and that the resulting keys reconstruct the on-chain output P using along= =20 with A.=20 As you highlighted txid is not committed in the proof currently, the=20 argument is replayable. The current POC does not bind to where the coins=20 go. Anyone who observes the chain could copy it and attach it to a=20 different transaction, spending the same UTXO to a different address. Worse= =20 for silent payment, because all user UTXO have the same secret=20 BIP32Derive(s, p_scan) and BIP32Derive(s, p_spend) except for A. The zk-STARK proof? or this mechanism should definitely be bound to the=20 spending transaction and the input being spent.=20 Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BIP-32= =20 still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2=80=94 = as long as the pubkey=20 has never previously appeared on-chain. A zk-STARK proof should apply here= =20 too? The prover argues for the correctness of HASH160(k=C2=B7G) =3D h, wher= e k is=20 the private key scalar and k=C2=B7G is the elliptic-curve point, without ev= er=20 revealing k or the pubkey. This would allow recovery of a broader set of=20 funds. If it were decided that classical signatures for these output types= =20 are invalidated and only a valid zk-STARK proof is required to spend,=20 anyone who holds the original secret can unlock their funds.=20 P.S. I am not for or against disabling valid spend paths post-quantum, just= =20 discussing the technical possibilities. Best, Abubakar Sadiq On Friday, 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=20 SHA256 and one modular addition on my CPU back in the day took like 20=20 seconds. Your GPU is coming in clutch for this. I best RISC0 has also=20 improved quite a bit since then. I think the next optimization step would be pre-seeding the two SHA512=20 midstates from the host, so you only need to prove two SHA512 compression= =20 calls instead of four. Intuitively I expect this would at best halve your= =20 prover time from 2sec, to probably a little over 1sec, and your verifier=20 time will probably drop as well since that also seems to scale with circuit= =20 complexity.=20 I think I have two half-decent arguments now as to why this won't affect=20 security:=20 First, even if a fraudulent prover is *handed the correct midstates to use*= ,=20 the prover would still have to do the hard work of finding the parent=20 secret key needed as a witness. This is at least the same difficulty as=20 finding the parent sk=E2=80=8B=E2=80=8B if we just hashed it without a chai= ncode at all,=20 using two bare SHA512 calls - the only thing that changes is the midstate,= =20 and the SHA512 input length suffix. Starting from a different midstate=20 doesn't magically give the attacker a head-start in a 256-bit search space= =20 looking for sk=E2=80=8B. A frauduent prover would know the child secret key= k =3D sk=20 + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't know int(I[32:]) or sk= =E2=80=8B so they cannot=20 solve for either. Nominally, the fraudulent prover wouldn't even know the correct midstates,= =20 so their task is strictly harder.=20 Secondly, here's another argument as to why finding the midstates in the=20 first place should also be hard.=20 Any adversary who could solve this problem by finding the right midstates= =20 could be used as an oracle to prove the existence of partial 2-cycles in=20 SHA512.=20 - Given a SHA512 hash I=E2=80=8B=E2=80=8B, set sk =3D int(I[32:])=E2=80= =8B=E2=80=8B=E2=80=8B - Compute k =3D sk + sk % n=E2=80=8B - Use the black-box fraudulent prover on the child key k=E2=80=8B=E2=80= =8B to find=20 correct midstates such that=20 =20 I =3D=3D SHA512( || SHA512( || 0x00 || sk || i))=E2= =80=8B=E2=80=8B=E2=80=8B k =3D=3D int(I[32:]) + sk % n=E2=80=8B =3D=3D sk + sk % n=E2=80=8B=E2=80=8B Remember that sk =3D int(I[32:])=E2=80=8B=E2=80=8B. Thus for these conditio= ns to hold, the=20 proof forger must be able to find not just the correct midstates, but also= =20 midstates which give a 2-stage partial hash cycle so that: I =3D=3D SHA512( || SHA512( || 0x00 || I[32:] || i))= =E2=80=8B This seems unlikely or at least very difficult. regards, conduition On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun < lao...@gmail.com> wrote: Hi Condution,=20 So I implemented both variants of your idea. My intuition was right in that= =20 it doesn't do much to reduce the size of the final succinct size, but the fina= l xpriv variant resulted in a significant reduction in both proving time, and also memory usage. I also re-ran the original succint proof for the origina= l Taproot claim and got a better value for the final proof time (def need a better benchmark env+set up!). Here's a breakdown of the resource requirements 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 * 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 * 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 So we can see that the succinct proof sizes are all about the same. However= =20 the xpriv variant can be proved directly in just 2 seconds on my machine! It=20 also requires just 3 GB of memory for the proof as well. I've created some additional supporting documentation to detail exactly wha= t 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/1c89fdb398180a2b3eff7761b7f4b= 233d455c6c9/README.md#reduced-proof-variants *=20 https://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a517= 1f5e06fa840/docs/claim.md#reduced-variant-claims Once again, thanks for the great ideas! I wonder if we can improve on this round of proof golf further before reaching down a lower level with some=20 sort of AIR compiler =F0=9F=A4=94. -- Laolu On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osuntokun wrote: Hi Conduition, > 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: 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" receipt type, I wa= s 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.=20 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 final succinct receipt of either of the proof variants. Based on my current intuition w.r.t the lower level details, I think the final succinct proof size would be on the same order of magnitude re size. However, this can still be a win as then this would provide potential futur= e users with a less resource intensive proof, which can then be aggregated/rolled up into a final succinct proof in a batched manner. 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 doing any EC operations at all for the final statement. ---- Re the commit/reveal approach, to be honest I'm not fully caught 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 thread so I ca= n digest it and develop a proper opinion, then get back to you re comparisons! -- Laolu On Wed, Apr 8, 2026 at 1:23=E2=80=AFPM conduition wrot= e: Oh, I've been a fool, a foolish fool. We don't even need to do point multiplication in the circuit at all. I'm amending my prior suggestion slightly: The circuit (guest program)=20 could take in an xpriv (e.g. at m/86'/0'=E2=80=8B) and output a *child xpri= v *(e.g.=20 at m/86'/0'/0'=E2=80=8B) to the journal (instead of outputting a child *xpu= b*).=20 This is safe because remember, EC spending has been disabled in this=20 context, and to a quantum attacker, an xpub is computationally equivalent= =20 to its xpriv. So why bother hiding it? The child xpriv doesn't give an=20 observer anything they can't already do with the equivalent xpub.=20 The guest program then is basically the BIP32 CKDpriv algorithm, restricted= =20 to a single hardened derivation step. The verifier gets the child xpriv,=20 but can't use it to forge new proofs. Honest verifiers use the xpriv to=20 derive the child address(es) as suggested in my last message, to=20 authenticate spending. Designing the guest program like this will massively reduce your circuit=20 complexity, because EC point multiplication is *wayyyyy* harder for the=20 RISC0 compiler to arithmetize than a simple hash function. In my prior work= =20 with RISC0 , I made a guest=20 program which ran a SHA256 hash and an EC point multiplication. I found=20 that pruning EC point arithmetic from my guest program improved prover=20 runtime by a factor of over 100x. If I am not fever-dreaming and this is indeed possible, then the new=20 circuit's complexity will be dominated not by point multiplication, but by= =20 the HMAC-SHA512 call. Our new task is then to figure out how much we can=20 internally optimize the HMAC-SHA512 call for STARK proving. Here's a few=20 ideas. If you bust open HMAC-SHA512, it looks like this: HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x36) || msg))= =E2=80=8B=20 ...where in the context of BIP32 hardened CKD, the HMAC key K=E2=80=8B is t= he=20 chaincode (padded with zeros to 128 bytes) and msg =3D (0x00 || sk || i) is= =20 the parent secret key and child index.=20 Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we need a = total of 4 SHA512=20 compression calls:=20 1. to compress (K=E2=8A=950x36)=E2=80=8B 2. to compress the msg=E2=80=8B (and SHA512 padding/length) 3. to compress (K=E2=8A=950x5c), and=20 4. a final compression call to tie it all together.=20 The output of that last compression call is partitioned into the child=20 chaincode, and a key delta which is added to the parent secret key (modulo= =20 the curve order), producing the child EC secret key. This last step is=20 arithmetically simple; the SHA512 calls are where most of the arithmetic=20 complexity lies. The question then becomes, which of these compression calls can be done=20 outside the circuit, and which are truly essential for security?=20 Note how the parent secret key is the most important piece for soundness.= =20 The circuit needs to prove the parent secret key existed in the hash=20 function preimage, and is correctly related to the child secret key via=20 modular addition. So compression call (2) seems unavoidable. The others are= =20 less rigid. I'd argue that if we really dig into the hard relation we're trying to=20 prove here, we can reduce it to this statement: Given a child xpriv with secret key k=E2=80=8B, chaincode c=E2=80=8B and in= dex i=E2=80=8B, I know a=20 preimage x*=E2=80=8B and secret key *sk=E2=80=8B such that: I <- SHA512( || SHA512( || 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 =E2=80=8B slots are arbitrary, and we know in BIP3= 2 they=20 are always exactly one-block long, it seems easy to throw out the=20 compression calls (1) and (3). The host can precompute the relevant SHA512= =20 midstates outside the circuit, and pass the midstates into the guest=20 program as secret inputs. The tradeoff is that this permits malicious=20 provers the flexibility of choosing their starting midstates (though hash= =20 input length can be fixed at 192 bytes). I'm not entirely sure if this=20 meaningfully weakens the verifier's soundness. Ethan Heilman might have=20 opinions on this, he knows a lot more about attacking hash functions than I= =20 do. Intuitively, I doubt sampling random SHA512 midstates is that much=20 better than sampling a random HMAC key (chaincode) K=E2=80=8B and computing= the=20 resulting midstates. This reduces our circuit to, i think, the minimum acceptable security floor= =20 for provers: two SHA512 compression calls, which commit to a parent secret= =20 key. regards, conduition On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via Bitcoin=20 Development Mailing List wrote: Hi Laolu, Great work getting this working in the real world. I've heard many people= =20 on delving and the mailing list conjecture based on this idea, but you're= =20 the first person i've seen who's willing to put their money where their=20 mouth is, and actually build a prototype. Bravo! It seems to me the circuit (guest program) could be simplified. Notice how = the=20 guest code computes the entire HD wallet key path=20 ,=20 including hardened *and *non-hardened derivation steps, and also computes= =20 the taproot output key with key-tweaking. I'd argue these steps are=20 extraneous to the core hard relation you want the STARK to prove, and could= =20 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=20 which derives this taproot output key"*. You need only prove this much more= =20 general statement (2): *"I know a BIP32 xpriv which derives this xpub via= =20 one or more hardened steps"*. The latter statement (2) still cannot be=20 forged by a quantum adversary even if they know your account-level xpub,=20 but it entails far less computation to prove and verify. The rest of the=20 original statement (1) can be done externally outside the circuit. Example. If i have a wallet with a taproot address at m/86'/0'/0'/1/2=E2=80= =8B, I=20 could prove I know the xpriv at m/86'/0'=E2=80=8B which derives the xpub at= =20 m/86'/0'/0'=E2=80=8B. Then I provide the remaining key path elements /1/2= =E2=80=8B in the=20 witness. Note, i *do not* mean we *derive* the xpriv at m/86'/0'=E2=80=8B i= nside=20 the guest program. I mean the prover derives m/86'/0'=E2=80=8B first (in th= e host),=20 and *then writes that xpriv into the guest program's inputs*. The guest=20 program derives and outputs the xpub at m/86'/0'/0'=E2=80=8B. The verifier = may=20 check the STARK output (xpub) is correctly computed, then use the given=20 key-path to manually derive the taproot address from the xpub themselves,= =20 outside the circuit, and validate *that address* against the UTXO i'm=20 spending. The verifier thus has confirmed the prover knew an xpriv which=20 (through a hardened derivation step) derives the correct taproot output key= . This change significantly reduces the size of the circuit. From a glance, I= =20 see the original guest program performs 6 HMAC-SHA512 calls (1 for the=20 master key, 5 for the BIP32 derivation steps), two SHA256 compression calls= =20 (for the taptweak hash), and two point multiplications. With this=20 simplified variant, we are invoking only a single HMAC-SHA512 call and a=20 single point multiplication. I can't say for sure, but I expect this will= =20 improve your proof size and runtime significantly. This change also makes the circuit more generally applicable to other=20 rescue contexts. For instance, it could be applied to BIP340 xonly keys=20 inside a taproot script tree, or in a P2(W)SH address to an ECDSA public=20 key, or to P2(W)PKH addresses. Concerned about publishing xpubs? Remember that we are assuming regular EC= =20 spending is locked in this context, so it is safe-ish to share account=20 xpubs with quantum attackers. At best the xpub can be used for surveillance= =20 but not forgery. If one would prefer not to share the account-level xpub=20 on-chain for privacy reasons, the proof could be extended to also derive=20 the unhardened child xpub at /1/2=E2=80=8B inside the guest program (but we= still=20 do not need to do the taproot key tweaking in the guest program). We should also talk scaling efficiency. Given the cost of STARKs, this=20 style of proof should be able to authorize spends for more than one UTXO.= =20 Say you have a wallet with 10 different UTXOs held by distinct addresses in= =20 the same BIP44 account. One single STARK proof could authorize spending all= =20 10 of them, by simply committing all 10 input signature hashes into the=20 journal, and labeling the inputs with the corresponding 10 BIP32 key paths= =20 somehow. The verifier would need to check the proof only once and not 10=20 times. The 10 UTXO spends could be validated using the common xpub from the= =20 STARK proof's journal. For a slightly related work proving a similar relation for hashed=20 addresses, using different STARK technology stacks, see this delving post= =20 . However, all this said, my personal preference for long-term procrastinator= =20 rescue is still for commit/reveal strategies which prove essentially the=20 same statement about BIP32 in a two-step procedure. They get the job done= =20 with much lighter cryptographic machinery and much smaller witnesses: a few= =20 hundred bytes over two transactions, compared to a few million bytes in one= =20 transaction with STARKs. Boris Nagaev and I discussed this on the list a=20 while back . That=20 said, commit/reveal requires more careful design and seems to demand the=20 use of external quantum-safe coins to make the commitment in the first=20 place, so perhaps the cost would be worth it to some people? IDK. What do= =20 you think of commit/reveal compared to STARKs for this purpose? regards, conduition On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun < lao...@gmail.com> wrote: Hi y'all, I found some spare time this last weekend to dust off a little side project I started last August: extend TinyGo [1] to be able to produce RISC-V ELF binaries capable of being run as a guest on the risc0 platform to generate zk-STARK proofs of arbitrary programs. Initially, I didn't really have a clear end target application, it was mainly a technical challenge to force me to learn a bit more about the RISC-V platform, and also 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 Taproot output public key was generated using BIP-32, via a given BIP-86 derivation path. More formally: ```math \mathcal{R} =3D \left\lbrace\; (\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{s,\,=20 \mathbf{p}}_{\textsf{witness}}) \;\middle|\; \begin{aligned} K &=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,\, \mathbf{p})\big= r)=20 \\ C &=3D \textsf{SHA256}\bigl(\texttt{"bip32-pq-zkp:path:v1"} \;\|\;=20 \mathbf{p}\bigr) \end{aligned} \;\right\rbrace ``` where $K$ is the Taproot output key, $C$ is the path commitment, $s$ is the BIP-32 seed, and $\mathbf{p}$ is the derivation path. I was able to get everything working e2e over the weekend, after making some tweaks 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 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 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 provably 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 Signature scheme) to provide a post-quantum proof of secret information a quantum attacker wouldn't be able to easily obtain. * The downside of that is that it reveals the secret BIP 32 seed, exposing other 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 proof that a Taproot output public key was generated via BIP-32 invocation of a BIP-86 derivation path. * In the future a variant of this scheme can be used to enable wallets that generated the private keys 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 quantum signature scheme. To achieve this end, I needed to create/fork a series of repos: * tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm * A fork of TinyGo that supports the flavor of RISC-V (rv32im) that risc0 requires to generate/execute a guest program to later be proved by the host. * risc0: https://github.com/Roasbeef/risc0 * 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-zkvm * 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 generate 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 generates a trace to later be proved. This is achieved via a C FFI compat layer between Go and the original Rust host/proving/verification code. * bip-32-pq-zkp: https://github.com/Roasbeef/bip32-pq-zkp * The project that packages everything 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 seconds or so to generate+proof, including execution. 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 memory. 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 within 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-zkvm/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 up until now, and feel free to return back to the _The Net of a Million Lies_, or as better known in our Universe: Monitoring the Situation and/or slopfotainment! =F0=9F=AB=A1 ## Motivation + Background As commonly known, in the case of an adversary that possesses a quantum computer capable of breaking classical asymmetric cryptography, any coins stored 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 publish the public key plainly in the pkScript. As detailed in [3], for Taproot outputs, a widely circulated plan is roughly to: disable the _keyspend_ path (requires a simple signature), enforcing a new rule that all Taproot spends must then flow through the script path. Spending via the script path requires an opening of the Taproot commitment (C =3D I + H(I || H(M))), which was shown to be binding= =20 even under classic assumptions, as H(M) (tapscript merkle root) is still a collision-resistant function. That means any UTXO that _does_ commit to a script path has a future escape hatch _if_ such a softfork would need to be deployed in 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 this existing proposal, those wallets would basically be locked forever. The goal of this work is to demonstrate a practical solution (discussed 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-STARKs, as they're plausibly post quantum since they rely only on symmetric cryptography: layers of merkle trees over an execution trace, along with 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 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') produce= s the same master key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) is the best known quantum collision finder, and it runs in time proportional to th= e 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 generated a wallet using BIP-32, you possess _another_ secret that a quantum adversary can't efficiently reconstruct! This demo focuses on the Taproot case, but the rough approach also applies to any other output generated via BIP-32. BIP 32 was originally published i= n 2012, over 14 years ago. So safe to say that _most_ wallets were generated under this scheme. However, 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 held today in outputs generated with Bitcoin Core's origina= l 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 proving system that takes a RISC-V ELF binary generated by a guest program (any program generating using their flavor of rv32im can be proved), executes that in a host environment, generates a trace, then produces a STARK proof 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 finally prove+verify it using their system. 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! 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-use them, first for this demo, then also in the future for other projects. TinyGo is a special Go compiler based on LLVM, that targets mostly embedded environments. You can use it to generate go programs that can run on micro controllers, or on web assembly (producing a smaller binary than if you used the normal stdlib path). TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V that risc0 relies on. So the first step here was to create a new target definition for TinyGo: riscv32-unknown-none, which uses base integer + multiply/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 memory 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 growHeap()). When I tried to get this working last year, I had to also implement a numbe= r of kernel syscalls (called ecalls in the platform [7]) to handle: read+writ= e to stdin/stdout, halting, and the journaling mechanism (the transcript of execution committed to), which basically implement the kernel that the gues= t executes in. Fast forward to 2026, and after pulling the latest version of the repo, I realized that they now make a libzkvm_platform.a, which package= s up the kernel nicely to be linked against. So I threw out my custom kernel 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 proved) 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 represented with the following JSON artifact: ``` { "schema_version": 1, "image_id":=20 "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690", "claim_version": 1, "claim_flags": 1, "require_bip86": true, "taproot_output_key":=20 "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992b288ee6", "path_commitment":=20 "4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b", "journal_hex":=20 "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992b= 288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b", "journal_size_bytes": 72, "proof_seal_bytes": 1797880, "receipt_encoding": "borsh" } ```` The `image_id` is basically a hash 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 t= o 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 public claim. Assuming you've built the project, then you can generate the proof (even passing in an arbitrary BIP-32 seed and derivation path with) ``` make prove GO_GOROOT=3D/path/to/go1.24.4 ``` Then verify it with: ``` make verify GO_GOROOT=3D/path/to/go1.24.4 ``` The default prove target writes: * ./artifacts/bip32-test-vector.receipt * ./artifacts/bip32-test-vector.claim.json The receipt is the STARK proof artifact. claim.json is the stable, human-readable description of the public statement being proved. ## Application to a Future Keyspend Disabling Soft fork As mentioned above, assuming the community is forced to deploy a keyspend disabling soft fork in the future, we can also deploy some variant of this proof to enable both BIP-86 wallets, and also any BIP-32 wallet, to sweep their funds into a new PQ output. In 2026, we've shown 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 adds overhead which increase the total amount of steps, and therefore the size of the proof. A production grade deployment would likely instead hand roll a custom STARK proof for this exact statement, to achieve a faster and smaller proof). # Future Work In terms of future work, there're a number of interesting following up projects that can be pursued from here. One basic one is that the current proof doesn't actually commit to a spending txid and/or sighash. That can be trivially incorporated into the proof. Going a step further, the execution of the guest program can even _generate_ a valid schnorr signature to permit spending. Looking to the memory+computational requirements necessary to generate the proof, I've left two low hanging fruits: 1. First, we can speed up the Elliptic Curve operations the proof requires (scalar base mult, then addition, or more performantly Double Scalar Multiplication via the Strauss-Shamir trick). For this we can use the syscalls/precompile in the risc0 env for big integer arithmetic: sys_bigint and sys_bigint2. With this, the guest calls into the kernel to use an optimized/accelerated circuit for the modular arithmetic, reducing 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_integrity+sys_verify_integrity2. We can then assembled a series of these proofs into a _single_ statement, which can save block space by aggregating N proofs into a single proof. -- Laolu [1]: https://tinygo.org/ [2]: https://risczero.com/ [3]: https://eprint.iacr.org/2025/1307 [4]: https://eprint.iacr.org/2023/362 [5]: https://microsoft.github.io/Picnic/ [6]: https://en.wikipedia.org/wiki/BHT_algorithm [7]: https://github.com/Roasbeef/go-zkvm/blob/main/docs/ecall-reference.md --=20 You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com. To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sg= eHVUANx9w6TVwUf_AYcd_qQ%40mail.gmail.com . --=20 You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com. To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBfPvG58g= LcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNE= Yg%3D%40proton.me . --=20 You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com. To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs9tps%3DbsMQyA%2BHvhK-u%= 2BXqRwWtjTq8WXZi%2BcveAVwPi9A%40mail.gmail.com . --=20 You received this message because you are subscribed to the Google Groups= =20 "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an= =20 email to bitcoindev+...@googlegroups.com. To view this discussion visit=20 https://groups.google.com/d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee8762= 6def65n%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/= 2482176b-1ad7-4216-b1e7-2c03265425een%40googlegroups.com. ------=_Part_140795_659489989.1776288852002 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Laolu, Abubakar, Conduition, list,

Does this idea extend to M= uSig2 or FROST outputs, assuming the relevant parties cooperate during prov= ing (or use some MPC) and collectively know the underlying seeds / secret m= aterial?

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

At least to me, MuSig2 seems = like it may be within reach. I would be very interested if someone has a co= ncrete sketch in mind.

Best,
Boris

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

<= /div>
Awesom= e point! A single STARK could be used to prove you knew an xpriv which deri= ves the xpriv at m/352'/coin'/account'=E2=80=8B. Then any veri= fier could easily derive the private scan/spend keys=C2=A0m/352'/coin= '/account'/0'/0=E2=80=8B or m/352'/coin'/account'/1'/0= =E2=80=8B, then replicate the ECDH process (with some BIP352-specific tweaks th= at the spender can provide), and add the result together. This repro= duces the private key of the SP taproot output being spent, proving the spe= nder is authentic.

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

Curious why not generali= se beyond BIP-32? P2PKH and P2WPKH without BIP-32 still commit to an unreve= aled secret =E2=80=94 HASH160(k=C2=B7G) =E2=80=94 as long as the pubkey has= never previously appeared 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 scalar and k=C2=B7G is the elliptic-curve point, withou= t ever revealing k or the pubkey. This would allow recovery of a broader se= t of funds.

I agree this type of th= ing would also be useful, but 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 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=E2=80=8B such t= hat HASH160(k*G) =3D h=E2=80=8B, then some non-negligible frac= tion of those coins will still be vulnerable to a CRQC because k*G=E2=80=8B may be known to the attacker, which to a CRQC is equivalent t= o knowing k=E2=80=8B.=C2=A0

To mitigate, a verifier would need to r= eject such proofs when someone tries to spend coins locked to such an "expo= sed pubkey" address. Since bitcoin nodes do not maintain an address index, = they don't intrinsically know which addresses have exposed pubkeys or not. = We would have to compose a list of such addresses, and since that list chan= ges over time, it would need to be updated by nodes in real-time when index= ing transactions. This list will almost certainly be incomplete, because we= don't have any record of pubkeys exposed off-chain (e.g. by hardware walle= ts, by xpubs shared in multi-party protocols, by lost TXs in orphaned block= s).
T= his idea also collides very unfortunately with the BIP32 xpriv proof of kno= wledge. With the faster proof style i suggested to modify Laolu's original = one, a spender immediately gives up knowledge of their account-level xpriv = to the CRQC when publishing a TX. Even if the spender was using a hashed-ad= dress with a hidden pubkey,=C2=A0the CRQC now knows the secret key=C2=A0k=E2=80=8B for that address, and could use it to forge a proof th= at h =3D HASH160(k*G)=E2=80=8B to attempt to double-spend/RBF = the authentic transaction.

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 xpriv proof if and only if the address is on the "exposed pu= bkey" list. The verifier would accept a hashed-address proof if and only if= the address is NOT on the "exposed pubkey" list. It's definitely feasib= le, it's just hard to do both safely.

This is also difficult to motivate, as= we lack hard statistics about the relevant portion of the Bitcoin supply t= hat we could use hashed-address proofs (but not BIP32 proofs) to rescue: Th= ose UTXOs which fall into the venn-diagram overlap of "Not using BIP32" and= "Not exposed-pubkey". BIP32 was introduced in 2012, whereas P2PKH was intr= oduced in 2009, so clearly there must be=C2=A0some=C2=A0overlap, but= how much? I suppose one could estimate by indexing all the P2PKH UTXOs rec= eived before BIP32 was published, and counting what portion of them still h= ave (probably) hidden public keys. This would be useful research for anyone= with the time and a working node.

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

Nice work.

The scheme ext= ends to BIP-352 (Silent Payments). The BIP-352 receiver reconstructs the ou= tput P using their private scan key, public spend key, and public informati= on from the spending transaction A.
See BIP-352 Scanning. BIP-352 reco= mmends but does not mandate BIP-32 for deriving the scan and spend keys, bu= t specifies the following derivation paths when BIP-32 is used:

= b_scan =3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0)
b_= spend =3D BIP32Derive(s, m/352'/coin_type'/account'/0'/0)

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

=
As you highlighted txid is not committed in the proof currently, the a= rgument 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 t= ransaction, spending the same UTXO to a different address. Worse for silent= 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 the spending transaction and = the input being spent.

Curious why not generalise beyond BIP-32= ? P2PKH and P2WPKH without BIP-32 still commit to an unrevealed secret =E2= =80=94 HASH160(k=C2=B7G) =E2=80=94 as long as the pubkey has never previous= ly appeared on-chain. A zk-STARK proof should apply here too? The prover ar= gues 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 revealin= g k or the pubkey. This would allow recovery of a broader set of funds. If = it were decided that classical signatures for these output types are invali= dated and only a valid zk-STARK proof is required to spend, anyone who hold= s the original secret can unlock their funds.

P= .S. I am not for or against disabling valid spend paths post-quantum, just = discussing the technical possibilities.

Best,
Abubakar Sadi= q
On Friday, April 10, 2026 at 7:47:09=E2=80=AF= PM UTC+2 conduition wrote:
<= div style=3D"font-family: Arial, sans-serif; font-size: 14px;">
Ah! Amazing work! 2 seconds to pr= ove is really crazy. Proving a single 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 wou= ld be pre-seeding the two SHA512 midstates from the host, so you only need = to prove two SHA512 compression calls instead of four. Intuitively I expect= this would at best halve your prover time from 2sec, to probably a little = over 1sec, and your verifier time will probably drop as well since that als= o seems to scale with circuit complexity.

I think I have two half-d= ecent arguments now as to why this won't affect security:

First, ev= en if a fraudulent prover is handed t= he correct midstates to use, the prover would still have to do the hard work of finding the= parent secret key needed as a witness. This is at least the same difficult= y as finding the parent sk=E2=80=8B=E2=80=8B if we just hashed it without a chaincode at = all, using two bare SHA512 calls - the only thing that changes is the midst= ate, 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=E2=80=8B. A frauduent prover would know the child secret key <= span>k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they 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 correct midstates, so their ta= sk is strictly harder.

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

Any adversary who could s= olve this problem by finding the right midstates could be used as an oracle= to prove the existence of partial 2-cycles in SHA512.
  • Given a SHA512 hash= I=E2= =80=8B<= /span>=E2=80=8B, set sk =3D int(I[32:])=E2=80=8B=E2=80=8B=E2=80=8B
  • Compute k =3D sk + sk % n=E2=80=8B
    • Use the black-box fraudule= nt prover on the child key k=E2=80=8B=E2=80=8B to find correct midstates such that =

I =3D=3D SHA512(<someth= ing> || 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
=3D= =3D sk + sk % n=E2=80=8B=E2=80=8B

Remember that sk = =3D int(I[32:])=E2=80=8B=E2=80=8B. Thus for these conditions to hold, the proof forger m= ust be able to find not just the correct midstates, but also midstates whic= h give a 2-stage partial hash cycle so that:
<= br />
= I =3D=3D SHA512(<something> || SHA512(<something> || 0x00= || I[32:] || i))=E2=80=8B

<= div style=3D"font-family: system-ui, sans-serif;">This seems un= likely or at least very difficult.

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

So I implemented bot= h variants of your idea. My intuition was right in that it
doesn't do = much to reduce the size of the final succinct size, but the final
xpri= v variant resulted in a significant reduction in both proving time, and
also memory usage. I also re-ran the original succint proof for the origi= nal
Taproot claim and got a better value for the final proof time (def= need a
better benchmark env+set up!).

Here's a breakdown o= f the resource requirements for the various proofs:
* Full Taproot image ID:
8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84b= fac077cbe70907a690
composite:
seal 1797880
p= rove 49.32s
verify 0.10s
peak RSS 11907399680
= succinct:
seal 222668
prove 64.30s
verif= y 0.03s
peak RSS 11927207936

* Hardened xpub
= image ID:
ad4ebc0ef6ce51e0f581cc8d14742a5b97738e9decd3fe2b0f174= 6de5bad9617
composite:
seal 513680
prove 14.= 63s
verify 0.04s
peak RSS 11783503872
succin= ct:
seal 222668
prove 17.29s
verify 0.02s<= br /> peak RSS 11782307840

* Hardened xpriv
imag= e ID:
8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0= df0849
composite:
seal 234568
prove 1.98s verify 0.02s
peak RSS 3144171520
suc= cinct:
seal 222668
prove 2.84s
verify 0.02= s
peak RSS 3145990144

So we can see that th= e succinct proof sizes are all about the same. However the
xpriv varia= nt can be proved directly in just 2 seconds on my machine! It also
req= uires just 3 GB of memory for the proof as well.

I've created so= me additional supporting documentation to detail exactly what
the new = proofs do and their results:

* https://github.com/Roasbeef/bip32-pq-z= kp/blob/main/docs/reduced-variants.md

* https://github.com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398= 180a2b3eff7761b7f4b233d455c6c9/README.md#reduced-proof-variants
* https://github.com/Roasbee= f/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5171f5e06fa840/docs/claim.md#= reduced-variant-claims


Once again, thanks for the grea= t ideas! I wonder if we can improve on this
round of proof golf furthe= r before reaching down a lower level with some sort
of AIR compiler = =F0=9F=A4=94.

-- Laolu

On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osuntokun <= ;lao...@gmail.com> wrote:
Hi Condu= ition,

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

> I'm amending my prior suggestion slight= ly: 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 jo= urnal (instead of outputting a child
> xpub).

That's an= excellent insight!

As mentioned in my recent reply, with risc0= 's "succinct" receipt type, I was
able to get the proof size down to 2= 20 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 this
simpler statement actually resul= ts in a smaller proof then the final
succinct receipt of either of the= proof variants. Based on my current
intuition w.r.t the lower level d= etails, I think the final succinct proof
size would be on the same ord= er of magnitude re size.

However, this can still be a win as the= n this would provide potential future
users with a less resource inten= sive proof, which can then be
aggregated/rolled up into a final succin= ct proof in a batched manner.

This line of optimization is also = more interesting if one were to look at
hand rolling a custom AIR to a= void the overhead that the RISC-V emulation
adds to the rirsc0 proof c= hain, given that it entirely skips doing any EC
operations at all for = the final statement.

----

Re the commit/reveal approa= ch, to be honest I'm not fully caught up on that
proposal. That origin= al 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
an= d develop a proper opinion, then get back to you re comparisons!

-- Laolu


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 multiplicat= ion in the circuit at all.

I'm amending my prior suggestion slightly: The circui= t (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 journal (instead of outputting a child xpub).

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

The guest program then is basica= lly the BIP32 CKDpriv algorithm, restricted to a single hardened derivation= step. The verifier gets the child xpriv, but can't use it to forge new pro= ofs. Honest verifiers use the xpriv to derive the child address(es) as sugg= ested in my last message, to authenticate spending.

Designing the guest program = like this will massively reduce your circuit complexity, because EC point m= ultiplication is wayyyyy harder for the RISC0 compiler to arithmetiz= e than a simple hash function. In my prior work with RISC0, I made a guest pr= ogram which ran a SHA256 hash and an EC point multiplication. I found that = pruning EC point arithmetic from my guest program improved prover runtime b= y a factor of over 100x.

If I am not fever-dreaming and this is indeed possible,= then the new circuit's complexity will be dominated not by point multiplic= ation, but by the HMAC-SHA512 call. Our new task is then to figure out how = much we can internally optimize the HMAC-SHA512 call for STARK proving. Her= e's a few ideas.

If you bust open HMAC-SHA512, it looks like this:

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

...where in the context of BIP32 hardened CKD, t= he HMAC key K=E2=80=8B is the chaincode (padded with zeros to = 128 bytes) and msg =3D (0x00 || 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 total of 4 SHA512 compression calls:
=
  1. to compress (K=E2=8A=950x36)=E2=80=8B
  2. to compress t= he msg=E2=80=8B (and SHA512 padding/length)
  3. to compress (K=E2=8A=950x5c), and
  4. a final compre= ssion call to tie it all together.

The output of that last compres= sion call is partitioned into the child chaincode, and a key delta which is= added to the parent secret key (modulo the curve order), produ= cing the child EC secret key. This last step is arithmetically simple; the = SHA512 calls are where most of the arithmetic complexity lies.
=

The = question then becomes, which of these compression calls can be done outside= the circuit, and which are truly essential for security?

Note how the parent = secret key is the most important piece for soundness. The circuit needs to = prove the parent secret key existed in the hash function preimage, and is c= orrectly related to the child secret key via modular addition. So compressi= on call (2) seems unavoidable. The others are less rigid.

I'd argue that if we= really dig into the hard relation we're trying to prove here, we can reduc= e it to this statement:

Given a child xpriv with = secret key k=E2=80=8B, chaincode c=E2=80=8B and index i=E2=80=8B, I know a preimage x=E2=80=8B and secret key s= k=E2=80=8B such that:

I <- SHA512(<something&g= t; || 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 arbitrary, and we= know in BIP32 they are always exactly one-block long, it seems easy to thr= ow out the compression calls (1) and (3). The host can precompute the relev= ant SHA512 midstates outside the circuit, and pass the midstates into the g= uest program as secret inputs. The tradeoff is that this permits malicious prov= ers the flexibility of choosing their starting midstates (though hash input= length can be fixed at 192 bytes). I'm not entirely sure if this meaningfu= lly weakens the verifier's soundness. Ethan Heilman might have opinions on = this, he knows a lot more about attacking hash functions than I do. Intuiti= vely, I doubt sampling random SHA512 midstates is that much better than sam= pling a random HMAC key (chaincode) K=E2=80=8B and computing t= he resulting midstates.
=
This reduces ou= r circuit to, i think, the minimum acceptable security floor for provers: t= wo SHA512 compression calls, which commit to a parent secret key.

<= /span>
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 = working in the real world. I've heard many people on delving and the mailin= g list conjecture based on this idea, but you're the first person i've seen= who's willing to put their money where their mouth is, and actually build = a prototype. Bravo!



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 derive the xpriv at m/86'/0'=E2=80=8B i= nside the guest program. I mean the prover derives m/86'= /0'=E2=80=8B first (in the host), and then writes th= at xpriv into the guest program's inputs. The guest program derives and= outputs the xpub at m/86'/0'/0'=E2=80=8B. The ve= rifier may check the STARK output (xpub) is correctly computed, then use th= e given key-path to manually derive the taproot address from the xpub thems= elves, outside the circuit, and validate that address a= gainst the UTXO i'm spending. The verifier thus has confirmed the prover kn= ew an xpriv which (through a hardened derivation step) derives the correct = taproot output key.



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

We should also talk scaling efficiency. Given t= he cost of STARKs, this style of proof should be able to authorize spends f= or more than one UTXO. Say you have a wallet with 10 different UTXOs held b= y distinct addresses in the same BIP44 account. One single STARK proof coul= d authorize spending all 10 of them, by simply committing all 10 input sign= ature hashes into the journal, and labeling the inputs with the corresponding 1= 0 BIP32 key paths somehow. The verifier would need to check t= he proof only once and not 10 times. The 10 UTXO spends could be validated = using the common xpub from the STARK proof's journal.


However, all= this said, my personal preference for long-term procrastinator rescue is s= till for commit/reveal strategies which prove essentially the same statemen= t about BIP32 in a two-step procedure. They get the job done with much ligh= ter cryptographic machinery 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 disc= ussed this on the list a while back. That said, commit/reveal requires = more careful design and seems to demand the use of external quantum-safe co= ins to make the commitment in the first place, so perhaps the cost would be= worth it to some people? IDK. What do you think of commit/reveal compared = to STARKs for this purpose?

regards,
conduition<= div style=3D"font-family: Arial, sans-serif; font-size: 14px;">
=
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 sid= e project
I started last August: extend TinyGo [1] to be able to produ= ce RISC-V ELF
binaries capable of being run as a guest on the risc0 pl= atform to generate
zk-STARK proofs of arbitrary programs. Initially, I= didn't really have a
clear end target application, it was mainly a te= chnical challenge to force
me to learn a bit more about the RISC-V pla= tform, and also 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 Taproot output public
key was generated using BIP-= 32, via a given BIP-86 derivation path.

More formally:
```m= ath
\mathcal{R} =3D \left\lbrace\;
(\overbrace{K,\, C}^{\textsf{p= ublic}} ;\; \underbrace{s,\, \mathbf{p}}_{\textsf{witness}})
\;\middle= |\;
\begin{aligned}
K &=3D \textsf{BIP86Taproot}\bigl(\text= sf{BIP32Derive}(s,\, \mathbf{p})\bigr) \\
C &=3D \textsf{SHA256}= \bigl(\texttt{"bip32-pq-zkp:path:v1"} \;\|\; \mathbf{p}\bigr)
\end{ali= gned}
\;\right\rbrace
```

where $K$ is the Taproot out= put key, $C$ is the path commitment, $s$ is the
BIP-32 seed, and $\mat= hbf{p}$ is the derivation path.


I was able to get everythi= ng working e2e over the weekend, after making
some tweaks to my initia= l architectural game plan!

The TL;DR is that:

* Giv= en that the Taproot commitment scheme is post-quantum secure [3], in
= the future we can deploy a soft fork to _disable_ the keyspend path,
and force all Taproot spends to instead flow through the script path<= br /> (not my idea, commonly discussed amongst developers, not sure who<= br /> 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 th= at provably
don't commit to a script path at all.

* A= 2023 paper (Protecting Quantum Procrastinators with Signature
Lif= ting: 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 proof of secret=
information a quantum attacker wouldn't be able to easily obtain.=

* The downside of that is that it reveals the secret BIP 32 s= eed,
exposing other non migrated UTXOs of a user.

* W= ith this project I've cobbled together a series of projects 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 path.

* In the future a variant of this scheme can be used to enable wallets<= br /> that generated the private keys via BIP-86, to have a post quantum= safe
exit path in case they don't bother moving their coins in ti= me to the
yet-to-be-decided post quantum signature scheme.
To achieve this end, I needed to create/fork a series of repos:
* tinygo-zkvm: https://github.com/Roa= sbeef/tinygo-zkvm
* A fork of TinyGo that supports the flavor = of RISC-V (rv32im) that
risc0 requires to generate/execute a gue= st program to later be proved
by the host.

* risc0:= https://github.com/Roasbeef/risc0
*= Mostly a bug fix to their c-guest example, along with some
addi= tional documentation on how to get things running. The repo is
u= nmodified other than that. Recent updates to the repo made the
e= ntire process much easier (Go guest+host), more on that later.

= * go-zkvm: https://github.com/Roasbeef/go-zkvm=
* Go utilities to take a RISC-V ELf binary produced by tinygo= -zkvm, and
package it in the expected R0BF format, which combine= s the user
generated RISC-V ELF (the thing that is executed to g= enerate the
proof) along with the v1compat ELF kernel, which is = risc0's execution
environment.

* This also includ= es a Go host package, which loads the guest program,
executes it= , and generates a trace to later be proved. This is
achieved via= a C FFI compat layer between Go and the original Rust
host/prov= ing/verification code.

* bip-32-pq-zkp: https://github.com/Roasbeef/bip32-pq-zkp
* The pro= ject that packages everything together, this contains the:
* Gue= st Go program that defines the secret witness and
claim/constr= aints of the proof.

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

Deta= ils of the final proof as generated on my Mac Book (Apple Silicon M4
M= ax, 128 GB of RAM):
* Takes ~55 seconds or so to generate+proof, inc= luding execution. This
uses Metal for GPU acceleration on the plat= form.
* Uses ~12 GB of ram.
* Final proof 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 (more on that later),=
this is meant to serve as a PoC to demonstrate that with the latestsoftware+hardware, a proof of this complexity is well within reach.

For those curious re the e2e details I've generated this tutorial t= hat
explains the entire system top to bottom:
https://github.com/Roasbeef/go-zkvm/blo= b/main/docs/tutorial.md.

If you got to this point in this ma= il, 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= Lies_, or as better known in our Universe:
Monitoring the Situation a= nd/or slopfotainment! =F0=9F=AB=A1

## Motivation + Background
As commonly known, in the case of an adversary that possesses a qu= antum
computer capable of breaking classical asymmetric cryptography, = any coins
stored 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 happ= en due to address re-use
(spending from the same script twice), or Tap= root outputs, which publish
the public key plainly in the pkScript.
As detailed in [3], for Taproot outputs, a widely circulated plan = is
roughly to: disable the _keyspend_ path (requires a simple signatur= e),
enforcing a new rule that all Taproot spends must then flow throug= h the
script path. Spending via the script path requires an opening of= the
Taproot commitment (C =3D I + H(I || H(M))), which was shown to b= e binding even
under classic assumptions, as H(M) (tapscript merkle ro= ot) is still a
collision-resistant function.

That means any= UTXO that _does_ commit to a script path has a future escape
hatch _i= f_ such a softfork would need to be deployed in the future.
However, w= hat 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 existing
proposal,= those wallets would basically be locked forever.

The goal of th= is work is to demonstrate a practical solution (discussed
against devs= , but never implemented AFAICT): generate a zk proof that an
output wa= s generated using BIP-86. For the zk-Proof, we select zk-STARKs,
as th= ey're plausibly post quantum since they rely only on symmetric
cryptog= raphy: layers of merkle trees over an execution trace, along with
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 a= nswer 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
H= MAC-SHA512 keyed by "Bitcoin seed" to produce the master extended privatekey. An adversary who wants to forge this proof needs to find a _collid= ing_
seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s= ') produces
the same master key. The BHT algorithm (Brassard-Hoyer-Tap= p [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 = generated a wallet using
BIP-32, you possess _another_ secret that a q= uantum adversary can't
efficiently reconstruct!

This demo f= ocuses on the Taproot case, 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. However, 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 held today in outputs generated with Bitcoi= n Core's original
key pool, but if you have coins generated via that m= echanism, you may want
to consider migrating them to a BIP-32 wallet.<= br />
## TinyGo + RISC-V + risc0

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 guest program (any
program generating usi= ng their flavor of rv32im can be proved), executes
that in a host envi= ronment, generates a trace, then produces a STARK proof
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 finally prove+v= erify it
using their system.

This demo took a bit of a roun= d about journey to achieve this, as after
all, the journey is most of = the fun, ain't it!

For the past 10 years or so, my Bitcoin stack= 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= for other projects.

TinyGo is a special Go compiler based on LL= VM, that targets mostly embedded
environments. You can use it to gener= ate go programs that can run on
micro controllers, or on web assembly = (producing a smaller binary than if
you used the normal stdlib path).<= br />
TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V t= hat risc0
relies on. So the first step here was to create a new target= definition for
TinyGo: riscv32-unknown-none, which uses base integer = + multiply/divide
instructions with no compressed instructions, which = uses 4 KB stacks for
each task. From there, I created a new linker scr= ipt
(`targets/riscv32im-risc0-zkvm-elf.ld`) which created a memory lay= er
identical to what risc0 expects. The final component was a new runt= ime
(`src/runtime/runtime_zkvm.go`), which implemented a few platform = specific
syscalls for risc0 (putchar(), exit(), ticks(), and growHeap(= )).

When I tried to get this working last year, I had to also im= plement a number
of kernel syscalls (called ecalls in the platform [7]= ) to handle: read+write
to stdin/stdout, halting, and the journaling m= echanism (the transcript of
execution committed to), which basically i= mplement the kernel 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_platform.a, which packages
up the kernel nicely to= be linked against. So I threw out my custom kernel
code, and slotted = that in instead.

The final component is a C FFI layer that enabl= es me to use _both_ a Go
guest (the program to be proved) and a Go hos= t (the thing that executes the
program and generates the final proof).=

## BIP-32+Taproot zk-STARK Proof

With basic proofs w= orking (like the classic: I know the factorization of a
number `n`), I= was unblocked to generate the actual proof. The claim/proof
is repres= ented with the following JSON artifact:
```
{
"schema_vers= ion": 1,
"image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84b= fac077cbe70907a690",
"claim_version": 1,
"claim_flags": 1, "require_bip86": true,
"taproot_output_key": "00324bf6fa47a8d70= cb5519957dd54a02b385c0ead8e4f92f9f07f992b288ee6",
"path_commitment":= "4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b",
= "journal_hex": "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead= 8e4f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaa= b56de11f74b",
"journal_size_bytes": 72,
"proof_seal_bytes": 1= 797880,
"receipt_encoding": "borsh"
}
````

The = `image_id` is basically a hash of the ELF, so you know what the prover
executed. There are then a few flags that control the claim version andwhether BIP-86 derivation is a part of the proof. BIP-86 was only adopte= d
post-Taproot, so if you have an existing BIP-44 path, you can instea= d opt to
claim that instead. The Taproot key we're generating the proo= f 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. Finall= y, we also commit to the
journal hex, which is basically a commitment = to the public claim.

Assuming you've built the project, then you= can generate the proof (even
passing in an arbitrary BIP-32 seed and = derivation path with)
```
make prove GO_GOROOT=3D/path/to/go1.24.= 4
```

Then verify it with:
```
make verify GO_GOR= OOT=3D/path/to/go1.24.4
```

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

The receipt is the STARK proof artifact.= claim.json is the stable,
human-readable description of the public st= atement being proved.

## Application to a Future Keyspend Disabl= ing Soft fork

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

In 2026, we've shown that this is achievable using 2 year old consu= mer
hardware. I don't doubt that the upcoming advancements (eg: photon= ics, 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 adds overhead which increase the total amo= unt
of steps, and therefore the size of the proof. A production grade<= br />deployment would likely instead hand roll a custom STARK proof for thi= s
exact statement, to achieve a faster and smaller proof).

= # Future Work

In terms of future work, there're a number of inte= resting following up
projects that can be pursued from here.

One basic one is that the current proof doesn't actually commit to a
spending txid and/or sighash. That can be trivially incorporated into the<= br />proof. Going a step further, the execution of the guest program can ev= en
_generate_ a valid schnorr signature to permit spending.

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

1. First, we can= speed up the Elliptic Curve operations the proof requires
(scalar= base mult, then addition, or more performantly Double Scalar
Mult= iplication via the Strauss-Shamir trick). For this we can use the
= syscalls/precompile in the risc0 env for big integer arithmetic:
s= ys_bigint and sys_bigint2. With this, the guest calls into the kernel
= to use an optimized/accelerated circuit for the modular arithmetic,
reducing cycles, steps, and thus proof size.

2. Second ri= ght now, the entire claim is a single proof. Instead, we can
first= break that up using their recursive proof/composition syscalls:
s= ys_verify_integrity+sys_verify_integrity2. We can then assembled a
= series of these proofs into a _single_ statement, which can save block
space by aggregating N proofs into a single proof.

-- Laol= u

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

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

[3]: https://eprint.iacr.org/2025/1307

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

[5]: https://microsoft.github.io/Picnic/

[6]: https://en.wikipedia.org/wiki/BHT_algorithm

[7]: https://github.com/Roasbeef/go-zkvm/blob/main/docs/ecall-reference.md<= /a>

--
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+...@go= oglegroups.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/bitcoind= ev/2482176b-1ad7-4216-b1e7-2c03265425een%40googlegroups.com.
------=_Part_140795_659489989.1776288852002-- ------=_Part_140794_1423171124.1776288852002--