From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 13 Apr 2026 12:21:58 -0700 Received: from mail-qv1-f63.google.com ([209.85.219.63]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wCMr3-0007HF-OK for bitcoindev@gnusha.org; Mon, 13 Apr 2026 12:21:58 -0700 Received: by mail-qv1-f63.google.com with SMTP id 6a1803df08f44-8a16036c90esf65452216d6.2 for ; Mon, 13 Apr 2026 12:21:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1776108107; x=1776712907; 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=ueXoUI1qRDaWS5RLJ63qxWR1ilcH+gXsQMwstknvPOI=; b=BN4fTMfJ1qjuG+lH6o1YygaZCkoMNds1Dj0j29wmds2BZG1rwXqhmaoOSaUHhg1/Xp svf2mHmgfgyha+0rfLXdNt4xiJ4i2tqlaaZR8673RaRnN3PcWUnOqr9sJRBY2vjkClDV qrXKq1551NaMHqCtBjInjsnxg4nm8LIsUUBl72EZj1EudIlICT5Co1jdcWBf07r4VZtv bx/kuBkOAnyQmHiDDVbk89F0865LUZadZy4c/yuHvQEytXGM5SsPMfhYDnP7AVkvy/uv D/EbMn8sBUgCnYF4MMRE/dg25qfMD1LDcVyMrD3gN9OE6MMBwQPj+E6x2pgN+jv7TUel 2BWw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1776108107; x=1776712907; 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=ueXoUI1qRDaWS5RLJ63qxWR1ilcH+gXsQMwstknvPOI=; b=n5G9kpL2UzkGh0YcrlzOEe5LdkqKOrG32tIjHUbPwiEwjMPlJ9DPZQpFJVPYHEtNF7 VEs/yKfSpDescvDFL6s3arb7bYKacECfFeG0xG7Std8ExqyJ0jtW6zf1OfVCy9WCUmFn xdicdT4Q9Mk/RCClI4FDFEFX/ibPbXa3pH5K5UEHWs033+e5RHJMs1qSgmUoEZST4dgY T2OAaOTidD6Hrbt8WKzpQLwCn94yoaRS+Zi1rOFEv5reRQ5W/AeNGFG+FK9UFsE0W3Mx hvKtBUXi9qqR8N1dHfWJ0HSqFK1xayyMtQufF0BbycmleeV2xbaOJbCbV/byUtTSSjlK PgLg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1776108107; x=1776712907; 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=ueXoUI1qRDaWS5RLJ63qxWR1ilcH+gXsQMwstknvPOI=; b=q/zDUmNTaVPMJY0c7foPAK+lx+nMB3kpJwcMXqPWCPzbpTXJyx3+nVhwIYgWeFiQbv +kIbV3WNqui52C7A+wYvTzL/m9TIwUYDdGAlErv0ruNLJ43zmK2qeld0jac35oMDOJZR 5WM5ToLmSqGxnBu/tcqQ6vuCXGdQ5z9kiLiRuZCVCbcJne9AKuRh1Mm89X8W09JJvtHk iGCawAwwH2mBvP1y3IwAXhtw8c1/aSvPBL4knnh4H/ZECVzUqUJ+zLO5X8XpZR3rM0sF YonRe1WzrkX9XV+clxpZHx+46MXqoQEkJpQsZGeiXJlNBFpfbfc9/aMCnCWttk5FH4Gw xVaw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ/ZyUpusbGFjjvq1FEopxcLAUgklALYmuoqJXiEKPkSfvwvEz/avTP9BpT0lwpJxwCD/Bef3/uvkH5n@gnusha.org X-Gm-Message-State: AOJu0YzxqoCcXazX0ZFMMBFgJbzSeoigliJcYW6XRZxwM1oetpLJijhk Nma+lP9veu1u4LpwSXOkso9gqqp4Ji/atep4wrkOehB7TvhdRZhgWyxH X-Received: by 2002:a05:6214:588e:b0:8ac:b088:439a with SMTP id 6a1803df08f44-8acb0884aa5mr70151666d6.0.1776108106943; Mon, 13 Apr 2026 12:21:46 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiJoy2/3ghAvmlbfYuWG7LlmbJoMpRsyShvKNHBwdPMbwQ==" Received: by 2002:ad4:414a:0:b0:89c:9f75:32ae with SMTP id 6a1803df08f44-8ac8352b53cls10006466d6.2.-pod-delta-02-us; Mon, 13 Apr 2026 12:21:40 -0700 (PDT) X-Received: by 2002:a05:620a:3189:b0:8cf:d68a:9aa2 with SMTP id af79cd13be357-8ddcf7ae077mr1436931485a.6.1776108100238; Mon, 13 Apr 2026 12:21:40 -0700 (PDT) Received: by 2002:a05:690c:d91:b0:7b3:443:26a9 with SMTP id 00721157ae682-7b304434911ms7b3; Mon, 13 Apr 2026 04:46:12 -0700 (PDT) X-Received: by 2002:a05:690c:61c4:b0:79c:2b01:32a3 with SMTP id 00721157ae682-7af728237admr88491187b3.8.1776080770917; Mon, 13 Apr 2026 04:46:10 -0700 (PDT) Date: Mon, 13 Apr 2026 04:46:10 -0700 (PDT) From: sadiq Ismail To: Bitcoin Development Mailing List Message-Id: <02378fd1-17a4-47aa-89fa-ee87626def65n@googlegroups.com> In-Reply-To: References: 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_522022_298376419.1776080770461" X-Original-Sender: ask4ismailsadiq@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_522022_298376419.1776080770461 Content-Type: multipart/alternative; boundary="----=_Part_522023_432937858.1776080770461" ------=_Part_522023_432937858.1776080770461 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 circu= it=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=20 > use*, the prover would still have to do the hard work of finding the=20 > parent secret key needed as a witness. This is at least the same difficul= ty=20 > as finding the parent sk=E2=80=8B=E2=80=8B if we just hashed it without a= chaincode at=20 > all, using two bare SHA512 calls - the only thing that changes is the=20 > midstate, and the SHA512 input length suffix. Starting from a different= =20 > midstate doesn't magically give the attacker a head-start in a 256-bit=20 > search space looking for sk=E2=80=8B. A frauduent prover would know the c= hild=20 > secret key k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't k= now int(I[32:]) or=20 > sk=E2=80=8B so they cannot 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 condit= ions to hold, the=20 > proof forger must be able to find not just the correct midstates, but als= o=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=20 > that it > doesn't do much to reduce the size of the final succinct size, but the=20 > final > xpriv variant resulted in a significant reduction in both proving time, a= nd > also memory usage. I also re-ran the original succint proof for the=20 > original > 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 <(314)%20417-1520> > succinct: > seal 222668 > prove 2.84s > verify 0.02s > peak RSS 3145990144 <(314)%20599-0144> > > So we can see that the succinct proof sizes are all about the same.=20 > However 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= =20 > 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/1c89fdb398180a2b3eff7761b7f= 4b233d455c6c9/README.md#reduced-proof-variants > > *=20 > https://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5= 171f5e06fa840/docs/claim.md#reduced-variant-claims > > > Once again, thanks for the great ideas! I wonder if we can improve on thi= s > 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 =20 > wrote: > >> Hi Conduition, >> >> > You need only prove this much more general statement (2): "I know a=20 >> 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= =20 >> was >> able to get the proof size down to 220 KB, at the cost of 3.5x longer=20 >> total >> proving time. >> >> Your proposal definitely reduces the complexity of the core statement to= =20 >> 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= =20 >> this >> 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 proo= f >> size would be on the same order of magnitude re size. >> >> However, this can still be a win as then this would provide potential=20 >> future >> 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 a= t >> hand rolling a custom AIR to avoid the overhead that the RISC-V emulatio= n >> adds to the rirsc0 proof chain, given that it entirely skips doing any E= C >> operations at all for the final statement. >> >> ---- >> >> Re the commit/reveal approach, to be honest I'm not fully caught up on= =20 >> 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= can digest=20 >> 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 w= rote: >> >>> 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 = xpriv *(e.g.=20 >>> at m/86'/0'/0'=E2=80=8B) to the journal (instead of outputting a child = *xpub*).=20 >>> >>> This is safe because remember, EC spending has been disabled in this=20 >>> context, and to a quantum attacker, an xpub is computationally equivale= nt=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,=20 >>> restricted to a single hardened derivation step. The verifier gets the= =20 >>> child xpriv, but can't use it to forge new proofs. Honest verifiers use= the=20 >>> xpriv to 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 circui= t=20 >>> complexity, because EC point multiplication is *wayyyyy* harder for the= =20 >>> RISC0 compiler to arithmetize than a simple hash function. In my prior= =20 >>> work with RISC0 , I made a= =20 >>> guest program which ran a SHA256 hash and an EC point multiplication. I= =20 >>> found that pruning EC point arithmetic from my guest program improved= =20 >>> prover 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 ca= n=20 >>> internally optimize the HMAC-SHA512 call for STARK proving. Here's a fe= w=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) || m= sg))=E2=80=8B=20 >>> >>> ...where in the context of BIP32 hardened CKD, the HMAC key K=E2=80=8B = is the=20 >>> chaincode (padded with zeros to 128 bytes) and msg =3D (0x00 || sk || i= )=20 >>> is 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 nee= d a total of 4=20 >>> SHA512 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 (mod= ulo=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 arithmeti= c=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=20 >>> soundness. The circuit needs to prove the parent secret key existed in = the=20 >>> hash function preimage, and is correctly related to the child secret ke= y=20 >>> via modular addition. So compression call (2) seems unavoidable. The ot= hers=20 >>> are 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 an= d index i=E2=80=8B, I=20 >>> know a 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 = BIP32=20 >>> they 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 SHA= 512=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 ha= sh=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 th= an 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 compu= ting the=20 >>> resulting midstates. >>> >>> This reduces our circuit to, i think, the minimum acceptable security= =20 >>> floor for provers: two SHA512 compression calls, which commit to a pare= nt=20 >>> secret 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=20 >>> people on delving and the mailing list conjecture based on this idea, b= ut=20 >>> you're the first person i've seen who's willing to put their money wher= e=20 >>> their mouth is, and actually build a prototype. Bravo! >>> >>> It seems to me the circuit (guest program) could be simplified. Notice= =20 >>> how the guest code computes the entire HD wallet key path=20 >>> ,=20 >>> including hardened *and *non-hardened derivation steps, and also=20 >>> computes the taproot output key with key-tweaking. I'd argue these step= s=20 >>> are extraneous to the core hard relation you want the STARK to prove, a= nd=20 >>> 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= =20 >>> which derives this taproot output key"*. You need only prove this much= =20 >>> more general statement (2): *"I know a BIP32 xpriv which derives this= =20 >>> xpub via one or more hardened steps"*. The latter statement (2) still= =20 >>> cannot be forged by a quantum adversary even if they know your=20 >>> account-level xpub, but it entails far less computation to prove and=20 >>> verify. The rest of the original statement (1) can be done externally= =20 >>> outside the circuit. >>> >>> Example. If i have a wallet with a taproot address at m/86'/0'/0'/1/2= =E2=80=8B,=20 >>> I could prove I know the xpriv at m/86'/0'=E2=80=8B which derives the x= pub at=20 >>> m/86'/0'/0'=E2=80=8B. Then I provide the remaining key path elements /1= /2=E2=80=8B in=20 >>> the witness. Note, i *do not* mean we *derive* the xpriv at m/86'/0'=E2= =80=8B=20 >>> inside the guest program. I mean the prover derives m/86'/0'=E2=80=8B f= irst (in=20 >>> the host), and *then writes that xpriv into the guest program's inputs*= .=20 >>> The guest program derives and outputs the xpub at m/86'/0'/0'=E2=80=8B.= The=20 >>> verifier may check the STARK output (xpub) is correctly computed, then = use=20 >>> the given key-path to manually derive the taproot address from the xpub= =20 >>> themselves, outside the circuit, and validate *that address* against=20 >>> the UTXO i'm spending. The verifier thus has confirmed the prover knew = an=20 >>> xpriv which (through a hardened derivation step) derives the correct=20 >>> taproot output key. >>> >>> This change significantly reduces the size of the circuit. From a=20 >>> glance, I see the original guest program performs 6 HMAC-SHA512 calls (= 1=20 >>> for the master key, 5 for the BIP32 derivation steps), two SHA256=20 >>> compression calls (for the taptweak hash), and two point multiplication= s.=20 >>> With this simplified variant, we are invoking only a single HMAC-SHA512= =20 >>> call and a single point multiplication. I can't say for sure, but I exp= ect=20 >>> this will 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 publi= c=20 >>> key, or to P2(W)PKH addresses. >>> >>> Concerned about publishing xpubs? Remember that we are assuming regular= =20 >>> EC spending is locked in this context, so it is safe-ish to share accou= nt=20 >>> xpubs with quantum attackers. At best the xpub can be used for surveill= ance=20 >>> but not forgery. If one would prefer not to share the account-level=20 >>> xpub on-chain for privacy reasons, the proof could be extended to also= =20 >>> derive the unhardened child xpub at /1/2=E2=80=8B inside the guest prog= ram (but=20 >>> we still do not need to do the taproot key tweaking in the guest progra= m). >>> >>> 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 UTX= O.=20 >>> Say you have a wallet with 10 different UTXOs held by distinct addresse= s 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=20 >>> paths somehow. The verifier would need to check the proof only once and= =20 >>> not 10 times. The 10 UTXO spends could be validated using the common xp= ub=20 >>> from the 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=20 >>> post . >>> >>> However, all this said, my personal preference for long-term=20 >>> procrastinator rescue is still for commit/reveal strategies which prove= =20 >>> essentially the same statement about BIP32 in a two-step procedure. The= y=20 >>> get the job done with much lighter cryptographic machinery and much sma= ller=20 >>> witnesses: a few hundred bytes over two transactions, compared to a few= =20 >>> million bytes in one transaction with STARKs. Boris Nagaev and I=20 >>> discussed this on the list a while back=20 >>> . That said,=20 >>> commit/reveal requires more careful design and seems to demand the use = of=20 >>> external quantum-safe coins to make the commitment in the first place, = so=20 >>> perhaps the cost would be worth it to some people? IDK. What do you thi= nk=20 >>> 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=20 >>> project >>> I started last August: extend TinyGo [1] to be able to produce RISC-V E= LF >>> binaries capable of being run as a guest on the risc0 platform to=20 >>> 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=20 >>> force >>> me to learn a bit more about the RISC-V platform, and also the host/gue= st >>> architecture of risc0. Fast forward ~9 months later, and an initial=20 >>> killer >>> use case popped into my mind: a zk-STARK proof that a Taproot output=20 >>> 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,\,=20 >>> \mathbf{p})\bigr) \\ >>> 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= =20 >>> 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= =20 >>> 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 ab= le >>> 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 M= 4 >>> 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= =20 >>> 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 coi= ns >>> stored in UTXOs with a known public key are vulnerable. This is the cas= e >>> for any P2PK outputs from waaaay back, and also any other outputs that= =20 >>> have >>> revealed their public key. Pubkey reveal might happen due to address=20 >>> re-use >>> (spending from the same script twice), or Taproot outputs, which publis= h >>> 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 bind= ing=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=20 >>> 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=20 >>> 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 a= n >>> output was generated using BIP-86. For the zk-Proof, we select zk-STARK= s, >>> 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= =20 >>> 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=20 >>> initial >>> 128-512-bit seed (with BIP-39, either 12 or 24 words), then runs it=20 >>> through >>> HMAC-SHA512 keyed by "Bitcoin seed" to produce the master extended=20 >>> private >>> key. An adversary who wants to forge this proof needs to find a=20 >>> _colliding_ >>> seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s')=20 >>> produces >>> the same master key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) is the >>> best known quantum collision finder, and it runs in time proportional t= o=20 >>> the >>> cube root of the output space: 2^(n/3). For HMAC-SHA512's 512-bit outpu= t, >>> that's ~2^171 quantum operations, well above even NIST's highest >>> post-quantum security category. Therefore, if you generated a wallet=20 >>> 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=20 >>> applies >>> to any other output generated via BIP-32. BIP 32 was originally=20 >>> published in >>> 2012, over 14 years ago. So safe to say that _most_ wallets were=20 >>> generated >>> under this scheme. However, Bitcoin Core only officially adopted BIP-32= =20 >>> in >>> 2016/2018, moving away from their existing key pool structure. I can't= =20 >>> say >>> how much BTC is held today in outputs generated with Bitcoin Core's=20 >>> original >>> key pool, but if you have coins generated via that mechanism, you may= =20 >>> 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), execute= s >>> that in a host environment, generates a trace, then produces a STARK=20 >>> proof >>> from that. >>> >>> Today you can take some subset of Rust, compile it to an ELF using thei= r >>> toolchain, then execute it, generate a trace, to finally prove+verify i= t >>> 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)= =20 >>> uses >>> a series of Go libraries, so I wanted to be able to re-use them, first= =20 >>> for >>> this demo, then also in the future for other projects. >>> >>> TinyGo is a special Go compiler based on LLVM, that targets mostly=20 >>> 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 ris= c0 >>> relies on. So the first step here was to create a new target definition= =20 >>> for >>> TinyGo: riscv32-unknown-none, which uses base integer + multiply/divide >>> instructions with no compressed instructions, which uses 4 KB stacks fo= r >>> 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=20 >>> specific >>> syscalls for risc0 (putchar(), exit(), ticks(), and growHeap()). >>> >>> When I tried to get this working last year, I had to also implement a= =20 >>> number >>> of kernel syscalls (called ecalls in the platform [7]) to handle:=20 >>> read+write >>> to stdin/stdout, halting, and the journaling mechanism (the transcript = of >>> execution committed to), which basically implement the kernel that the= =20 >>> guest >>> executes in. Fast forward to 2026, and after pulling the latest version= =20 >>> of >>> the repo, I realized that they now make a libzkvm_platform.a, which=20 >>> packages >>> up the kernel nicely to be linked against. So I threw out my custom=20 >>> 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= =20 >>> the >>> program and generates the final proof). >>> >>> ## BIP-32+Taproot zk-STARK Proof >>> >>> With basic proofs working (like the classic: I know the factorization o= f=20 >>> a >>> number `n`), I was unblocked to generate the actual proof. The=20 >>> 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 >>> "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f= 992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b"= , >>> "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=20 >>> 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 adopt= ed >>> post-Taproot, so if you have an existing BIP-44 path, you can instead= =20 >>> 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= =20 >>> to >>> see. We then also include a `path_commitment`, which is a commitment to= =20 >>> 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 (eve= n >>> 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 keyspe= nd >>> 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, t= o >>> 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,= =20 >>> new >>> flavor of high bandwidth memory, etc) in hardware (driven by the fierce= =20 >>> 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=20 >>> 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 t= he >>> proof. Going a step further, the execution of the guest program can eve= n >>> _generate_ a valid schnorr signature to permit spending. >>> >>> Looking to the memory+computational requirements necessary to generate= =20 >>> the >>> proof, I've left two low hanging fruits: >>> >>> 1. First, we can speed up the Elliptic Curve operations the proof=20 >>> 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 ca= n >>> 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]:=20 >>> https://github.com/Roasbeef/go-zkvm/blob/main/docs/ecall-reference.md >>> >>> --=20 >>> You received this message because you are subscribed to the Google=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO= 14sgeHVUANx9w6TVwUf_AYcd_qQ%40mail.gmail.com >>> . >>> >>> >>> --=20 >>> You received this message because you are subscribed to the Google=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBfPv= G58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9X= EXNEYg%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 "= 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/= 02378fd1-17a4-47aa-89fa-ee87626def65n%40googlegroups.com. ------=_Part_522023_432937858.1776080770461 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Laolu, list,

Nice work.

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 d= oes not mandate BIP-32 for deriving the scan and spend keys, but specifies = the following derivation paths when BIP-32 is used:

=C2=A0 =C2= =A0 b_scan =C2=A0=3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0)
= =C2=A0 =C2=A0 b_spend =3D BIP32Derive(s, m/352'/coin_type'/account'/0'/0)
For all silent payment addresses generated using BIP-32, your tec= hnique applies. The prover produces a zk-STARK proof that the program BIP32= Derive(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.=C2=A0

As you highlighted txid is not committed in the p= roof currently, the argument is replayable. The current POC does not bind t= o where the coins go. Anyone who observes the chain could copy it and attac= h it to a different transaction, spending the same UTXO to a different addr= ess. Worse for silent payment, because all user UTXO have the same secret B= IP32Derive(s, p_scan) and BIP32Derive(s, p_spend) except for A.
T= he zk-STARK proof? or this mechanism should definitely be bound to the spen= ding transaction and the input being spent.=C2=A0

Curious why no= t 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 previously appeared on-chain. A zk-STARK proof should appl= y 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 poi= nt, without ever revealing k or the pubkey. This would allow recovery of a = broader set of funds. If it were decided that classical signatures for thes= e output types are invalidated and only a valid zk-STARK proof is required = to spend, anyone who holds the original secret can unlock their funds.=C2= =A0

P.S. I am not for or against disabling valid= spend paths post-quantum, just 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 sec= onds to prove is really crazy. Proving a single SHA256 and one modular addi= tion on my CPU back in the day took like 20 seconds. Your=C2=A0GPU is coming in clutch for this. I best RISC= 0 has also improved quite a bit since then.

I think the next optimizatio= n step would be pre-seeding the two SHA512 midstates from the host, so you = only need to prove two SHA512 compression calls instead of four. Intuitivel= y 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 sinc= e that also seems to scale with circuit complexity.=C2=A0
=
I think I have = two half-decent arguments now as to why this won't affect security:=C2= =A0

First, even if a fraudulent prover is=C2=A0handed the 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 sam= e difficulty as finding the parent sk=E2=80=8B=E2=80=8B if we just hashed it without a chaincod= e at all, using two bare SHA512 calls - the only thing that changes is the = midstate, and the SHA512 input length suffix.=C2=A0Starting from a differen= t midstate doesn't magically give the attacker a head-start in a 256-bi= t search space looking for sk=E2=80=8B.=C2=A0A=C2=A0frauduent prover would know = the child secret key=C2=A0k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't know=C2=A0int(I[32:])=C2=A0or=C2=A0sk=E2=80=8B so they cannot solve = for either.

No= minally, the fraudulent prover wouldn't even know the correct midstates= , so their task is strictly harder.

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

Any adversary = who could solve this problem by finding the right midstates could be used a= s an oracle to prove the existence of partial 2-cycles in SHA512.=C2=A0

  • = Given a SHA512 hash=C2=A0I= =E2=80=8B<= /span>=E2=80=8B, set sk =3D int(I[32:])=E2=80=8B=E2=80=8B=E2=80=8B
  • Compute= =C2=A0k =3D sk + sk % n=E2=80=8B
  • Use the black-box fraudulent prover on the child key= =C2=A0k=E2=80=8B=E2=80=8B to f= ind correct midstates such that=C2=A0

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

<= font face=3D"Arial, sans-serif">Remember that sk =3D int(I[32:])=E2=80=8B=E2=80=8B.=C2=A0Thus for these conditions= to hold, the proof forger must be able to find not just the correct midsta= tes, but also midstates which give a 2-stage partial hash cycle so that:

I =3D=3D SHA512(<something> || SHA512(<somet= hing> || 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,

So I implemented both va= riants of your idea. My intuition was right in that it
doesn't do mu= ch to reduce the size of the final succinct size, but the final
xpriv va= riant resulted in a significant reduction in both proving time, and
also= memory usage. I also re-ran the original succint proof for the originalTaproot claim and got a better value for the final proof time (def need a<= br>better benchmark env+set up!).

Here's a breakdown of the reso= urce requirements for the various proofs:
* Full Taproot
image = ID:
8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a6= 90
composite:
seal 1797880
prove 49.32s
v= erify 0.10s
peak RSS 11907399680
succinct:
seal 22= 2668
prove 64.30s
verify 0.03s
peak RSS 11927207= 936

* Hardened xpub
image ID:
ad4ebc0ef6ce51e0f581cc= 8d14742a5b97738e9decd3fe2b0f1746de5bad9617
composite:
seal = 513680
prove 14.63s
verify 0.04s
peak RSS 117835= 03872
succinct:
seal 222668
prove 17.29s
= verify 0.02s
peak RSS 11782307840

* Hardened xpriv
= image ID:
8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a= 3c0df0849
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 t= he succinct proof sizes are all about the same. However the
xpriv varian= t can be proved directly in just 2 seconds on my machine! It also
requir= es just 3 GB of memory for the proof as well.

I've created some = additional supporting documentation to detail exactly what
the new proof= s do and their results:

* https://github.com/Roasbeef/bip32-pq-zkp/b= lob/main/docs/reduced-variants.md

* https://githu= b.com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398180a2b3eff7761b7f4b233d455c6c9/R= EADME.md#reduced-proof-variants

* https://= github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5171f5e06fa= 840/docs/claim.md#reduced-variant-claims


Once again, thanks = for the great ideas! I wonder if we can improve on this
round of proof g= olf further before reaching down a lower level with some sort
of AIR com= piler =F0=9F=A4=94.

-- Laolu

On Thu, Apr 9, 202= 6 at 1:53=E2=80=AFPM Olaoluwa Osuntokun <lao...@gmail.com> wrote:
Hi Co= nduition,

> 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). =

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 220 KB, at the cost of 3.5x longer total
pro= ving time.

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

I'll try to hack thi= s up, and then run a head to head comparison to see this
simpler stateme= nt actually results in a smaller proof then the final
succinct receipt o= f 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 t= he same order of magnitude re size.

However, this can still be a win= as then this would provide potential future
users with a less resource = intensive proof, which can then be
aggregated/rolled up into a final suc= cinct proof in a batched manner.

This line of optimization is also m= ore interesting if one were to look at
hand rolling a custom AIR to avoi= d 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 fin= al statement.

----

Re the commit/reveal approach, to be hones= t 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 revis= it that specific branch of the thread so I can digest it
and develop a p= roper 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 multiplication in the circuit at all.

I'm amending my= prior suggestion slightly: The circuit (guest program) could take in an xp= riv (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 spendi= ng 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 chil= d xpriv doesn't give an observer anything they can't already do wit= h the equivalent xpub.

The guest program then is basically the BIP32 CKDpriv algorithm, res= tricted to a single hardened derivation step. The verifier gets the child x= priv, but can't use it to forge new proofs. Honest verifiers use the xp= riv to derive the child address(es) as suggested in my last message, to aut= henticate spending.

Designing the guest program like this will massively reduce your circuit= complexity, because EC point multiplication is wayyyyy harder for t= he RISC0 compiler to arithmetize than a simple hash function. In my prior work with RISC0, I made a guest p= rogram which ran a SHA256 hash and an EC point multiplication. I found that= pruning EC point arithmetic 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 n= ew 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 we= can internally optimize the HMAC-SHA512 call for STARK proving. Here'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, the 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 the msg=E2=80=8B (and SHA512 padding/length)<= /li>
  3. to compress (K=E2=8A=950x5c), and
  4. a final compression call to t= ie 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 c= urve order), producing the child EC secret key. This last step is arith= metically simple; the SHA512 calls are where most of the arithmetic complex= ity 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 secre= t 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 correc= tly related to the child secret key via modular addition. So compression ca= ll (2) seems unavoidable. The others are less rigid.

I'd argue that if we really dig int= o the hard relation we're trying to prove here, we can reduce it to thi= s statement:

Given a child xpriv with secret key k=E2=80=8B, chaincode <= /font>c=E2=80=8B an= d index i=E2= =80=8B, I know a preimage x=E2=80=8B = and secret key sk=E2=80=8B such that:

I <- SHA512(<= ;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 <= code><something>=E2=80=8B slots are arbitrary, and we know in = BIP32 they are always exactly one-block long, it seems easy to throw out th= e compression calls (1) and (3). The host can precompute the relevant SHA51= 2 midstates outside the circuit, and pass the midstates into the guest prog= ram as secret inputs. The tradeoff is that this permits malicious provers the flexibi= lity of choosing their starting midstates (though 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 have opinions on this, h= e knows a lot more about attacking hash functions than I do. Intuitively, I= doubt sampling random SHA512 midstates is that much better than sampling a= random HMAC key (chaincode) K=E2=80=8B and computing the resu= lting midstates.

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.

<= /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 mailing l= ist 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 actual= ly build a prototype. Bravo!

It seems to me the ci= rcuit (guest program) could be simplified. Notice how the gue= st code computes the entire HD wallet key path, including hardened and non-hardened derivation steps, and also co= mputes the taproot output key with key-tweaking. I'd argue these steps = are extraneous to the core hard relation you want the STARK to prove, and c= ould be safely removed to reduce proof size and improve performance.
<= div>
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"<= /i>. 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 computa= tion to prove and verify. The rest of the original statement (1) can be don= e externally outside the circuit.

Example. If i ha= ve a wallet with a taproot address at m/86'/0'/0= '/1/2=E2=80=8B, I could prove I know the xpriv at <= code>m/86'/0'=E2=80=8B which derives the xpub at m/86'/0'/0'=E2=80=8B. Then I provide the remaini= ng 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 inside the guest program. I mean the pr= over derives m/86'/0'=E2=80=8B first (in = the host), and then writes that xpriv into the guest progra= m's inputs. The guest program derives and outputs the xpub at= m/86'/0'/0'=E2=80=8B. The verifier may che= ck the STARK output (xpub) is correctly computed, then use the given key-pa= th to manually derive the taproot address from the xpub themselves, outside= the circuit, and validate that address against the UTX= O i'm spending. The verifier thus has confirmed the prover knew an xpri= v which (through a hardened derivation step) derives the correct taproot ou= tput key.

This change significantly reduces the si= ze of the circuit. From a glance, I see the original guest program performs= 6 HMAC-SHA512 calls (1 for the master key, 5 for the BIP32 derivation step= s), two SHA256 compression calls (for the taptweak hash), and two point mul= tiplications. With this simplified variant, we are invoking only a single H= MAC-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.=

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

Concerned about publi= shing xpubs? Remember that we are assuming regular EC spending is locked in= this context, so it is safe-ish to share account xpubs with quantum attack= ers. 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 privac= y 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 t= weaking in the guest program).

We shoul= d also talk scaling efficiency. Given the cost of STARKs, this style of pro= of should be able to authorize spends for more than one UTXO. Say you have = a wallet with 10 different UTXOs held by distinct addresses in the same BIP= 44 account. One single STARK proof could authorize spending all 10 of them,= by simply committing all 10 input signature hashes into the journal, and l= abeling th= e inputs with the corresponding 10 BIP32 key paths somehow. The verifier w= ould 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 journa= l.

For a slightly related work proving a similar r= elation for hashed addresses, using different STARK technology stacks, see this delving post.

How= ever, all this said, my personal preference for long-term procrastinator re= scue 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 machinery and much smaller witnesses: a few hund= red bytes over two transactions, compared to a few million bytes in one tra= nsaction with STARKs. Boris Nagaev and I discussed this on t= he 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?

regards,
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <<= a href rel=3D"noreferrer nofollow noopener" data-email-masked>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 produce= RISC-V ELF
binaries capable of being run as a guest on the risc0 platfo= rm to generate
zk-STARK proofs of arbitrary programs. Initially, I didn&= #39;t really have a
clear end target application, it was mainly a techni= cal 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 l= ater, and an initial killer
use case popped into my mind: a zk-STARK pro= of that a Taproot output public
key was generated using BIP-32, via a gi= ven BIP-86 derivation path.

More formally:
```math
\mathcal{R}= =3D \left\lbrace\;
(\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrac= e{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-z= kp:path:v1"} \;\|\; \mathbf{p}\bigr)
\end{aligned}
\;\right\rbra= ce
```

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

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-qu= antum secure [3], in
the future we can deploy a soft fork to _disabl= e_ the keyspend path,
and force all Taproot spends to instead flow t= hrough the script path
(not my idea, commonly discussed amongst deve= lopers, not sure who
proposed it first). At that point, Taproot star= ts to resemble BIP-360.

* That works for script path spends, but t= hen leaves all the BIP-86
wallets in a bad position, as they generat= ed 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 s= ecret
information a quantum attacker wouldn't be able to easily = obtain.

* The downside of that is that it reveals the secret BIP 3= 2 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.

* I= n 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 t= he
yet-to-be-decided post quantum signature scheme.

To achiev= e this end, I needed to create/fork a series of repos:

* tinygo-zk= vm: https://github.com/Roasbeef/tinygo-zkvm
* A fork of TinyGo t= hat 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 the= ir c-guest example, along with some
additional documentation on ho= w to get things running. The repo is
unmodified other than that. R= ecent 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 tin= ygo-zkvm, and
package it in the expected R0BF format, which combin= es the user
generated RISC-V ELF (the thing that is executed to ge= nerate the
proof) along with the v1compat ELF kernel, which is ris= c0's execution
environment.

* This also includes a = Go host package, which loads the guest program,
executes it, and g= enerates a trace to later be proved. This is
achieved via a C FFI = compat layer between Go and the original Rust
host/proving/verific= ation code.

* bip-32-pq-zkp: https://github.com/Roasbeef/bip32-p= q-zkp
* The project that packages everything together, this cont= ains 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+proo= f, 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),
th= is is meant to serve as a PoC to demonstrate that with the latest
softwa= re+hardware, a proof of this complexity is well within reach.

For th= ose curious re the e2e details I've generated this tutorial that
exp= lains 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 abou= t the lower level
details, thanks for reading up until now, and feel fre= e 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 c= ase of an adversary that possesses a quantum
computer capable of breakin= g classical asymmetric cryptography, any coins
stored in UTXOs with a kn= own public key are vulnerable. This is the case
for any P2PK outputs fro= m waaaay back, and also any other outputs that have
revealed their publi= c key. Pubkey reveal might happen due to address re-use
(spending from t= he 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 (requi= res a simple signature),
enforcing a new rule that all Taproot spends mu= st then flow through the
script path. Spending via the script path requi= res an opening of the
Taproot commitment (C =3D I + H(I || H(M))), which= was shown to be binding even
under classic assumptions, as H(M) (tapscr= ipt merkle root) is still a
collision-resistant function.

That me= ans any UTXO that _does_ commit to a script path has a future escape
hat= ch _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 committo a script path at all? Under a strict version of this existing
propos= al, those wallets would basically be locked forever.

The goal of thi= s work is to demonstrate a practical solution (discussed
against devs, b= ut never implemented AFAICT): generate a zk proof that an
output was gen= erated 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 aski= ng: "if the quantum adversary can derive the
private key to a rando= m 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 se= ed (with BIP-39, either 12 or 24 words), then runs it through
HMAC-SHA51= 2 keyed by "Bitcoin seed" to produce the master extended private<= br>key. An adversary who wants to forge this proof needs to find a _collidi= ng_
seed: a different seed s' such that HMAC-SHA512("Bitcoin se= ed", s') produces
the same master key. The BHT algorithm (Brass= ard-Hoyer-Tapp [6]) is the
best known quantum collision finder, and it r= uns 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 operatio= ns, well above even NIST's highest
post-quantum security category. T= herefore, 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 applie= s
to any other output generated via BIP-32. BIP 32 was originally publis= hed in
2012, over 14 years ago. So safe to say that _most_ wallets were = generated
under this scheme. However, Bitcoin Core only officially adopt= ed BIP-32 in
2016/2018, moving away from their existing key pool structu= re. I can't say
how much BTC is held today in outputs generated with= Bitcoin Core's original
key pool, but if you have coins generated v= ia that mechanism, you may want
to consider migrating them to a BIP-32 w= allet.

## TinyGo + RISC-V + risc0

Now for some of the lower l= evel details. risc0 is a STARK based proving
system that takes a RISC-V = ELF binary generated by a guest program (any
program generating using th= eir 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
tool= chain, then execute it, generate a trace, to finally prove+verify it
usi= ng their system.

This demo took a bit of a round about journey to ac= hieve this, as after
all, the journey is most of the fun, ain't it!<= br>
For the past 10 years or so, my Bitcoin stack of choice (lnd/btcsuit= e) 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 embedde= d
environments. You can use it to generate go programs that can run onmicro controllers, or on web assembly (producing a smaller binary than if=
you used the normal stdlib path).

TinyGo supports RISC-V, but _n= ot_ 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 com= pressed instructions, which uses 4 KB stacks for
each task. From there, = I created a new linker script
(`targets/riscv32im-risc0-zkvm-elf.ld`) wh= ich created a memory layer
identical to what risc0 expects. The final co= mponent was a new runtime
(`src/runtime/runtime_zkvm.go`), which impleme= nted a few platform specific
syscalls for risc0 (putchar(), exit(), tick= s(), and growHeap()).

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 jo= urnaling mechanism (the transcript of
execution committed to), which bas= ically implement 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 enables m= e 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 follo= wing JSON artifact:
```
{
"schema_version": 1,
&q= uot;image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac= 077cbe70907a690",
"claim_version": 1,
"claim_= flags": 1,
"require_bip86": true,
"taproot_ou= tput_key": "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07= f992b288ee6",
"path_commitment": "4c7de33d397de2c2= 31e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b",
"journal_= hex": "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead= 8e4f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaa= b56de11f74b",
"journal_size_bytes": 72,
"proo= f_seal_bytes": 1797880,
"receipt_encoding": "borsh= "
}
````

The `image_id` is basically a hash of the ELF, s= o you know what the prover
executed. There are then a few flags that con= trol the claim version and
whether BIP-86 derivation is a part of the pr= oof. BIP-86 was only adopted
post-Taproot, so if you have an existing BI= P-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 th= e prover used. Finally, we also commit to the
journal hex, which is basi= cally a commitment to the public claim.

Assuming you've built th= e project, then you can generate the proof (even
passing in an arbitrary= BIP-32 seed and derivation path with)
```
make prove GO_GOROOT=3D/pa= th/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-v= ector.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 keyspe= nd
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, t= o
sweep their funds into a new PQ output.

In 2026, we've show= n that this is achievable using 2 year old consumer
hardware. I don'= t doubt that the upcoming advancements (eg: photonics, new
flavor of hig= h 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 thi= s proof has a few layers of indirection,
mainly the RISC-V layer that ad= ds overhead which increase the total amount
of steps, and therefore the = size of the proof. A production grade
deployment would likely instead ha= nd roll a custom STARK proof for this
exact statement, to achieve a fast= er 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 trivia= lly incorporated into the
proof. Going a step further, the execution of = the guest program can even
_generate_ a valid schnorr signature to permi= t spending.

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

= 1. First, we can speed up the Elliptic Curve operations the proof requires<= br> (scalar base mult, then addition, or more performantly Double Scalar=
Multiplication via the Strauss-Shamir trick). For this we can use t= he
syscalls/precompile in the risc0 env for big integer arithmetic:<= br> sys_bigint and sys_bigint2. With this, the guest calls into the kern= el
to use an optimized/accelerated circuit for the modular arithmeti= c,
reducing cycles, steps, and thus proof size.

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

-- Laolu

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

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

[3]: = https://epri= nt.iacr.org/2025/1307

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

[5]: https://mi= crosoft.github.io/Picnic/

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

[7]: https://github.com/Roasbeef/go-zkvm/blob/main/docs/ecal= l-reference.md

--
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 bitc= oindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitco= indev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TVwUf_AYcd_qQ%40mail.gmail.co= m.

--
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 bitc= oindev+...@googlegroups.com.
To view this discussion visit https://gr= oups.google.com/d/msgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIk= FV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNEYg%3D%40pr= oton.me.

--
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 bitc= oindev+...@googlegroups.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/02378fd1-17a4-47aa-89fa-ee87626def65n%40googlegroups.com.
------=_Part_522023_432937858.1776080770461-- ------=_Part_522022_298376419.1776080770461--