From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 30 Apr 2026 16:52:20 -0700 Received: from mail-oi1-f188.google.com ([209.85.167.188]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wIbB2-00015g-AF for bitcoindev@gnusha.org; Thu, 30 Apr 2026 16:52:20 -0700 Received: by mail-oi1-f188.google.com with SMTP id 5614622812f47-467e226743esf2406806b6e.0 for ; Thu, 30 Apr 2026 16:52:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1777593130; x=1778197930; 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=Po/i7KyV5v3QYdo4iaGfGpkqqEOQrlxkdAoOhDdb8hM=; b=mw0QTWrVmZglofVIQnwoDcWYNDrYKZ4CrfyRea/5pt571v4u7gyji7263pk/tuiYZ7 rB8aIfXpdrK/qj9Vdunin7kB8FYWMsQ2f+xOYm0/JixZqKfD5rf6v+QKhLvTqYpSvTx7 QlgU2KVhm2b3RDm1apI2e9p9WjmvjYXZOyqOYdJ1aaOg4XY9YrL6I2gi1NVAzHZMUYHZ SdQqP6qETqRVO5INKgu1lP6kdwSQJtC9l8oGOUUTObRU9FjgKfD2u1ap7TCpFGUsgQyj N/Xc5QWLQCEudT/DrrGcTMfd5IGN3FZ3Nhq2IzoO2gsJw4erv+0nZ5hiWGBYhHyvHdeo Kjsw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1777593130; x=1778197930; 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=Po/i7KyV5v3QYdo4iaGfGpkqqEOQrlxkdAoOhDdb8hM=; b=gHkij+f2ugQwDfKvXl7wo8PglVzaoRCgelF7Ttej/MBX26l7FXCHewnEQtHVbw0yhb vOTaQyeZbw511FkLsq90ezX7jYwWN+lOU9fchv2kyveXNWoQlgsGa7Ni/FLKyLhJ8PTz w1bf0o91D5Ocq0+9uPxM3MY7a5Lpf51KVDgbnVG+FuHQ33fJ2+yIg9jZbXAHtDZ9xFY5 ev30Qa+XDXlHXoPMXJmailt8fnhPvjBSrLJ+5LRxpPfRtDPmokCArb5Sn6xjAOCpxa+6 h2fo9yeMv3ll2xV3WMsFwVcmeEO5pt5LPARs7w5kxV6hLB98MLKCBkgC+fc103o9nIT0 y3sA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777593130; x=1778197930; 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=Po/i7KyV5v3QYdo4iaGfGpkqqEOQrlxkdAoOhDdb8hM=; b=CRmwI6IZr1WobhmRbGyDty3VEzbyii3strlCTDJUbV74MY1fYz17XebV/hh9aAbeKW 6gsYBdV4jhQac4kFV3aopf1wwVcmC4O/SLL0EaFGfPETLzXvRJdSISSURQBXsuqisOmE oMFcP2XMzIer0Uu+Y8s21CvyRcdXCZ1V0S/yAvExYzUK5kko0/ZRU8CcDdhRiJvyFE85 eW1HfO2x0Md3DPyUYW8JvfxUx9Q+/xnRPN2z6JFflGL0BT+ulp/mtO9l5vd+EhTLKK42 UIIHcthiSdoNyTbzV92eKyGwxvhuwfqObsMbIMBeFKIdToX1KtoU23jc8ZYF++5vy/tu /bbw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ9NP570BwizY8wQEg1ndmiJAAdugJosxKq3kDnuG/pbMDXtbsS/OqdN0ExR8utUXzhG3DuJZyst5Orr@gnusha.org X-Gm-Message-State: AOJu0YycOPjegyb1iy6Yt/k0KgQw+MzqvSnAGLuuA26+1EtdAsmP88wZ fn3g2sNuhOhubmTWjnN+04ksZ1/duhTMjnFMeG7beI5N0gI47XQvcBnO X-Received: by 2002:a05:6808:1809:b0:47b:d07b:ec9b with SMTP id 5614622812f47-47c60f47387mr2627633b6e.24.1777593129726; Thu, 30 Apr 2026 16:52:09 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AUV6zMOhWif/g5Us+RhSCAA9vbc7vNCw0UwOIGqk62o00QXTtw==" Received: by 2002:a05:6870:e98a:b0:430:b76:607f with SMTP id 586e51a60fabf-4340b4f5b7bls693438fac.2.-pod-prod-00-us-canary; Thu, 30 Apr 2026 16:52:05 -0700 (PDT) X-Received: by 2002:a05:6808:1829:b0:45f:103c:2483 with SMTP id 5614622812f47-47c620f6664mr1919187b6e.23.1777593125053; Thu, 30 Apr 2026 16:52:05 -0700 (PDT) Received: by 2002:a05:690c:c3e2:b0:7ba:f1b3:9504 with SMTP id 00721157ae682-7bd6653f53cms7b3; Thu, 30 Apr 2026 16:17:34 -0700 (PDT) X-Received: by 2002:a05:690c:c509:b0:7b1:9036:a23a with SMTP id 00721157ae682-7bd55ed6e53mr34760897b3.14.1777591053636; Thu, 30 Apr 2026 16:17:33 -0700 (PDT) Date: Thu, 30 Apr 2026 16:17:33 -0700 (PDT) From: Alex To: Bitcoin Development Mailing List Message-Id: <49236a10-94ea-440a-9b53-63ae2c7ac964n@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_8216_1372975127.1777591053148" X-Original-Sender: alexhultman@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_8216_1372975127.1777591053148 Content-Type: multipart/alternative; boundary="----=_Part_8217_201299178.1777591053148" ------=_Part_8217_201299178.1777591053148 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > STARKs don't take multiple seconds to verify. You can run the code in my= =20 repo > to see, it verifies in tens of milliseconds [1]. And > Verification takes ~1.8 seconds are not logically consistent. Your original statement was 1.8 seconds and I= =20 referred to it as such, but now you say it's tens of milliseconds.=20 Technically 1.8 seconds is some multiple of tens of milliseconds, true, but= =20 I was referring to your original statement of 1.8 seconds. The core point is that; exposing the complexity that is STARK verification= =20 in Bitcoin nodes, where 1.8 seconds of CPU-time is expected (as per your=20 original statement), this is a gaping flesh wound in terms of DOS attack=20 surface. Further on, the same argument regarding standardization of zkVMs or=20 Circuits is highly problematic and complex, a bug in such a Circuit cannot= =20 be fixed without scrambling the verification and there is no way so=20 standardize it other than through arbitrary code versioning. Whether you recursively prove a proof and so on is irrelevant to the=20 complexity and DOS question. You could make a STARK that certified the=20 entire Bitcoin chain in a few KB of data, but the complexity and DOS attack= =20 surface for such a recursive proof is just as galactic as 1 single proof. The point is that, if you expose STARK verifications anyone can send highly= =20 costly STARKs that take multiple seconds of CPU time (a DOS attack). onsdag 29 april 2026 kl. 03:21:51 UTC+2 skrev Olaoluwa Osuntokun: > Hi Sadiq, > > > > The scheme extends to BIP-352 (Silent Payments) > > Yup, as shown in my latest post, we can batch aggregate multiple claims= =20 > into a > single proof. If this were to be deployed at some point in the future, de= vs > would be able to scower wallets/protocol/codebases for other recovery > proofs/claims that could be added. > > > > The zk-STARK proof? or this mechanism should definitely be bound to the > > spending transaction and the input being spent.=20 > > Def, this would be it would be straight forward to bind the proof to a=20 > given > wtxid/sighash. > > > > 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=20 > pubkey > > has never previously appeared on-chain. A zk-STARK proof should apply= =20 > here > > too?=20 > > No fundamental reason, just I decided to focus the initial demo on P2TR.= =20 > One > could easily swap in this section where the Taproot Output key is derived= =20 > with > another script type instead [1].=20 > > [1]:=20 > https://github.com/Roasbeef/bip32-pq-zkp/blob/main/bip32/taproot.go#L91-L= 94 > > -- Laolu > > > On Mon, Apr 13, 2026 at 12:21=E2=80=AFPM 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 alon= g=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. Wo= rse=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-3= 2=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 he= re=20 >> too? The prover argues for the correctness of HASH160(k=C2=B7G) =3D h, w= here k is=20 >> the private key scalar and k=C2=B7G is the elliptic-curve point, without= ever=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 typ= es=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,= =20 >> 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 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 compressi= on=20 >>> calls instead of four. Intuitively I expect this would at best halve yo= ur=20 >>> prover time from 2sec, to probably a little over 1sec, and your verifie= r=20 >>> time will probably drop as well since that also seems to scale with cir= cuit=20 >>> complexity.=20 >>> >>> I think I have two half-decent arguments now as to why this won't affec= t=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 diffic= ulty=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= child=20 >>> secret key k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't= know int(I[32:])=20 >>> or sk=E2=80=8B so they cannot solve for either. >>> >>> Nominally, the fraudulent prover wouldn't even know the correct=20 >>> midstates, so their task is strictly harder.=20 >>> >>> Secondly, here's another argument as to why finding the midstates in th= e=20 >>> first place should also be hard.=20 >>> >>> Any adversary who could solve this problem by finding the right=20 >>> midstates could be used as an oracle to prove the existence of partial= =20 >>> 2-cycles in 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 cond= itions to hold,=20 >>> the proof forger must be able to find not just the correct midstates, b= ut=20 >>> also 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,= =20 >>> and >>> 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! I= t=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-variant= s.md >>> >>> *=20 >>> https://github.com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398180a2b3eff7761b= 7f4b233d455c6c9/README.md#reduced-proof-variants >>> >>> *=20 >>> https://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974= a5171f5e06fa840/docs/claim.md#reduced-variant-claims >>> >>> >>> Once again, thanks for the great ideas! I wonder if we can improve on= =20 >>> this >>> round of proof golf further before reaching down a lower level with som= e=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 progra= m) >>>> > 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,= =20 >>>> I 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= =20 >>>> 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 se= e=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=20 >>>> 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= =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= =20 >>>> at >>>> hand rolling a custom AIR to avoid the overhead that the RISC-V=20 >>>> emulation >>>> adds to the rirsc0 proof chain, given that it entirely skips doing any= =20 >>>> EC >>>> 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=20 >>>> 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 = 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= )=20 >>>>> could take in an xpriv (e.g. at m/86'/0'=E2=80=8B) and output a *chil= d xpriv *(e.g.=20 >>>>> at m/86'/0'/0'=E2=80=8B) to the journal (instead of outputting a chil= d *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 equiva= lent=20 >>>>> to its xpriv. So why bother hiding it? The child xpriv doesn't give a= n=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 th= e=20 >>>>> child xpriv, but can't use it to forge new proofs. Honest verifiers u= se 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=20 >>>>> circuit complexity, because EC point multiplication is *wayyyyy*=20 >>>>> harder for the RISC0 compiler to arithmetize than a simple hash funct= ion.=20 >>>>> In my prior work with RISC0=20 >>>>> , I made a guest program= =20 >>>>> which ran a SHA256 hash and an EC point multiplication. I found that= =20 >>>>> pruning EC point arithmetic from my guest program improved prover run= time=20 >>>>> 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, b= ut 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 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 n= eed 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 chil= d=20 >>>>> chaincode, and a key delta which is added to the parent secret key (m= odulo=20 >>>>> the curve order), producing the child EC secret key. This last step= =20 >>>>> is arithmetically simple; the SHA512 calls are where most of the arit= hmetic=20 >>>>> complexity lies. >>>>> >>>>> The question then becomes, which of these compression calls can be=20 >>>>> done 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 i= n the=20 >>>>> hash function preimage, and is correctly related to the child secret = key=20 >>>>> via modular addition. So compression call (2) seems unavoidable. The = others=20 >>>>> are less rigid. >>>>> >>>>> I'd argue that if we really dig into the hard relation we're trying t= o=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 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 i= n BIP32=20 >>>>> they are always exactly one-block long, it seems easy to throw out th= e=20 >>>>> compression calls (1) and (3). The host can precompute the relevant S= HA512=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 thi= s=20 >>>>> meaningfully weakens the verifier's soundness. Ethan Heilman might ha= ve=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 muc= h=20 >>>>> better than sampling a random HMAC key (chaincode) K=E2=80=8B and com= puting=20 >>>>> the 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 pa= rent=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,= but=20 >>>>> you're the first person i've seen who's willing to put their money wh= ere=20 >>>>> their mouth is, and actually build a prototype. Bravo! >>>>> >>>>> It seems to me the circuit (guest program) could be simplified. Notic= e=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 st= eps=20 >>>>> are extraneous to the core hard relation you want the STARK to prove,= and=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=20 >>>>> seed which derives this taproot output key"*. You need only prove=20 >>>>> this much more general statement (2): *"I know a BIP32 xpriv which=20 >>>>> derives this xpub via one or more hardened steps"*. The latter=20 >>>>> statement (2) still cannot be forged by a quantum adversary even if t= hey=20 >>>>> know your account-level xpub, but it entails far less computation to = prove=20 >>>>> and verify. The rest of the original statement (1) can be done extern= ally=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= xpub 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= first=20 >>>>> (in the host), and *then writes that xpriv into the guest program's= =20 >>>>> inputs*. The guest program derives and outputs the xpub at m/86'/0'/0= '=E2=80=8B.=20 >>>>> The verifier may check the STARK output (xpub) is correctly computed,= then=20 >>>>> use the given key-path to manually derive the taproot address from th= e xpub=20 >>>>> themselves, outside the circuit, and validate *that address* against= =20 >>>>> the UTXO i'm spending. The verifier thus has confirmed the prover kne= w 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 multiplicati= ons.=20 >>>>> With this simplified variant, we are invoking only a single HMAC-SHA5= 12=20 >>>>> call and a single point multiplication. I can't say for sure, but I e= xpect=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 ke= ys=20 >>>>> inside a taproot script tree, or in a P2(W)SH address to an ECDSA pub= lic=20 >>>>> key, or to P2(W)PKH addresses. >>>>> >>>>> Concerned about publishing xpubs? Remember that we are assuming=20 >>>>> regular EC spending is locked in this context, so it is safe-ish to s= hare=20 >>>>> account xpubs with quantum attackers. At best the xpub can be used fo= r=20 >>>>> surveillance but not forgery. If one would prefer not to share the=20 >>>>> account-level xpub on-chain for privacy reasons, the proof could be= =20 >>>>> extended to also derive the unhardened child xpub at /1/2=E2=80=8B in= side the=20 >>>>> guest program (but we still do not need to do the taproot key tweakin= g in=20 >>>>> the guest program). >>>>> >>>>> We should also talk scaling efficiency. Given the cost of STARKs, thi= s=20 >>>>> style of proof should be able to authorize spends for more than one U= TXO.=20 >>>>> Say you have a wallet with 10 different UTXOs held by distinct addres= ses in=20 >>>>> the same BIP44 account. One single STARK proof could authorize spendi= ng all=20 >>>>> 10 of them, by simply committing all 10 input signature hashes into t= he=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= =20 >>>>> and not 10 times. The 10 UTXO spends could be validated using the com= mon=20 >>>>> xpub 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 pro= ve=20 >>>>> essentially the same statement about BIP32 in a two-step procedure. T= hey=20 >>>>> get the job done with much lighter cryptographic machinery and much s= maller=20 >>>>> witnesses: a few hundred bytes over two transactions, compared to a f= ew=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 us= e 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 t= hink=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= =20 >>>>> ELF >>>>> 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 hav= e=20 >>>>> 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=20 >>>>> host/guest >>>>> 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$= =20 >>>>> is the >>>>> BIP-32 seed, and $\mathbf{p}$ is the derivation path. >>>>> >>>>> >>>>> I was able to get everything working e2e over the weekend, after maki= ng >>>>> some tweaks to my initial architectural game plan! >>>>> >>>>> The TL;DR is that: >>>>> >>>>> * Given that the Taproot commitment scheme is post-quantum secure [3]= ,=20 >>>>> 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= =20 >>>>> 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 wallet= s >>>>> that generated the private keys via BIP-86, to have a post quantum sa= fe >>>>> 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, a= nd >>>>> 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= =20 >>>>> M4 >>>>> Max, 128 GB of RAM): >>>>> * Takes ~55 seconds or so to generate+proof, including execution. Thi= s >>>>> 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=20 >>>>> 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 tha= t >>>>> 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 bac= k=20 >>>>> 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 quant= um >>>>> computer capable of breaking classical asymmetric cryptography, any= =20 >>>>> coins >>>>> stored in UTXOs with a known public key are vulnerable. This is the= =20 >>>>> case >>>>> for any P2PK outputs from waaaay back, and also any other outputs tha= t=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=20 >>>>> 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 t= he >>>>> 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=20 >>>>> binding 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 (discuss= ed >>>>> against devs, but never implemented AFAICT): generate a zk proof that= =20 >>>>> an >>>>> output was generated using BIP-86. For the zk-Proof, we select=20 >>>>> zk-STARKs, >>>>> as they're plausibly post quantum since they rely only on symmetric >>>>> cryptography: layers of merkle trees over an execution trace, along= =20 >>>>> with >>>>> some novel sampling/error-correction algorithms. >>>>> >>>>> At this point, you may be asking: "if the quantum adversary can deriv= e=20 >>>>> the >>>>> private key to a random taproot public key, then how exactly does thi= s >>>>> 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 t= he >>>>> best known quantum collision finder, and it runs in time proportional= =20 >>>>> to the >>>>> cube root of the output space: 2^(n/3). For HMAC-SHA512's 512-bit=20 >>>>> output, >>>>> 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=20 >>>>> BIP-32 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 provi= ng >>>>> system that takes a RISC-V ELF binary generated by a guest program (a= ny >>>>> program generating using their flavor of rv32im can be proved),=20 >>>>> executes >>>>> 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=20 >>>>> their >>>>> toolchain, then execute it, generate a trace, to finally prove+verify= =20 >>>>> it >>>>> using their system. >>>>> >>>>> This demo took a bit of a round about journey to achieve this, as aft= er >>>>> 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, firs= t=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 tha= n=20 >>>>> if >>>>> you used the normal stdlib path). >>>>> >>>>> TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V that= =20 >>>>> risc0 >>>>> relies on. So the first step here was to create a new target=20 >>>>> definition for >>>>> TinyGo: riscv32-unknown-none, which uses base integer + multiply/divi= de >>>>> instructions with no compressed instructions, which uses 4 KB stacks= =20 >>>>> 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 runtim= e >>>>> (`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 transcrip= t=20 >>>>> of >>>>> execution committed to), which basically implement the kernel that th= e=20 >>>>> guest >>>>> executes in. Fast forward to 2026, and after pulling the latest=20 >>>>> version 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=20 >>>>> 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= =20 >>>>> of 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 >>>>> "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f0= 7f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74= b", >>>>> "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 a= nd >>>>> whether BIP-86 derivation is a part of the proof. BIP-86 was only=20 >>>>> adopted >>>>> 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 agains= t=20 >>>>> is >>>>> also part of the _public data_, as it sits plainly on the chain for= =20 >>>>> all to >>>>> see. We then also include a `path_commitment`, which is a commitment= =20 >>>>> to the >>>>> exact BIP 86 path that the prover used. Finally, we also commit to th= e >>>>> journal hex, which is basically a commitment to the public claim. >>>>> >>>>> Assuming you've built the project, then you can generate the proof=20 >>>>> (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=20 >>>>> 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,= =20 >>>>> to >>>>> sweep their funds into a new PQ output. >>>>> >>>>> In 2026, we've shown that this is achievable using 2 year old consume= r >>>>> hardware. I don't doubt that the upcoming advancements (eg: photonics= ,=20 >>>>> new >>>>> flavor of high bandwidth memory, etc) in hardware (driven by the=20 >>>>> 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= =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 th= is >>>>> exact statement, to achieve a faster and smaller proof). >>>>> >>>>> # Future Work >>>>> >>>>> In terms of future work, there're a number of interesting following u= p >>>>> 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= =20 >>>>> the >>>>> proof. Going a step further, the execution of the guest program can= =20 >>>>> even >>>>> _generate_ a valid schnorr signature to permit spending. >>>>> >>>>> Looking to the memory+computational requirements necessary to generat= e=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 kerne= l >>>>> 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= =20 >>>>> 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 bloc= k >>>>> 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, sen= d=20 >>>>> an email to bitcoindev+...@googlegroups.com. >>>>> To view this discussion visit=20 >>>>> https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3a= cO14sgeHVUANx9w6TVwUf_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, sen= d=20 >>>>> an email to bitcoindev+...@googlegroups.com. >>>>> To view this discussion visit=20 >>>>> https://groups.google.com/d/msgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBf= PvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg= 9XEXNEYg%3D%40proton.me >>>>> . >>>>> >>>>> >>>>> --=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/CAO3Pvs9tps%3DbsMQyA%2BHvh= K-u%2BXqRwWtjTq8WXZi%2BcveAVwPi9A%40mail.gmail.com >>> . >>> >>> >>> --=20 >> You received this message because you are subscribed to the Google Group= s=20 >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n=20 >> email to bitcoindev+...@googlegroups.com. >> > To view this discussion visit=20 >> https://groups.google.com/d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee8= 7626def65n%40googlegroups.com=20 >> >> . >> > --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 49236a10-94ea-440a-9b53-63ae2c7ac964n%40googlegroups.com. ------=_Part_8217_201299178.1777591053148 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > STARKs don't take multiple seconds to verify= . You can run the code in my repo
> to see, it verifies in tens of = milliseconds [1].

And
= >=C2=A0 Verification takes ~1.8 seconds
=
are not logically consi= stent. Your original statement was 1.8 seconds and I referred to it as such= , but now you say it's tens of milliseconds. Technically 1.8 seconds is som= e multiple of tens of milliseconds, true, but I was referring=C2=A0to your = original statement of 1.8 seconds.

The core point is that; exposing the complexity= that is STARK verification in Bitcoin nodes, where 1.8 seconds of CPU-time= is expected (as per your original statement), this is a gaping flesh wound= in terms of DOS attack surface.

Further=C2=A0on, the same argum= ent regarding standardization of zkVMs or Circuits is highly problematic an= d complex, a bug in such a Circuit=C2=A0cannot be fixed without scrambling = the verification and there is no way so standardize it other than through a= rbitrary code versioning.

Whether you recursively prove a proof = and so on is irrelevant to the complexity and DOS question. You could make = a STARK that certified=C2=A0the entire Bitcoin chain in a few KB of data, b= ut the complexity and DOS attack surface for such a recursive proof is just= as galactic as 1 single proof.

The point is that, if you expose= STARK verifications anyone can send highly costly STARKs that take multipl= e seconds of CPU time (a DOS attack).

onsdag 29 april 2026 kl. 03:21:51 U= TC+2 skrev Olaoluwa Osuntokun:
Hi Sadiq,


> The scheme extends to BIP-352 (Silent Payments)
Yup, as shown in my latest post, we can = batch aggregate multiple claims into a
single proof. If this were to be = deployed at some point in the future, devs
would be able to scower walle= ts/protocol/codebases for other recovery
proofs/claims that could be add= ed.


> The zk-STARK proof? or th= is mechanism should definitely be bound to the
> spending transaction= and the input being spent.

Def, = this would be it would be straight forward to bind the proof to a given
= wtxid/sighash.


> Curious why no= t generalise beyond BIP-32? P2PKH and P2WPKH without BIP-32
> still c= ommit 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 p= roof should apply here
> too?

No fundamental reason, just I decided to focus the initial demo on P2TR.= One
could easily swap in this section where the Taproot Output key is d= erived with
another script type instead [1].

[1]: https://github.com/Roasbeef/bip32-p= q-zkp/blob/main/bip32/taproot.go#L91-L94

-- Laolu

<= /div>
On Mon, Apr 13, 2026 at 12:21=E2=80=AFPM sa= diq Ismail <ask4ism...@gmail.= com> wrote:
Hi Laolu, list,

Nice work.
The scheme extends to BIP-352 (Silent Payments). The BIP-352 receiver rec= onstructs the output P using their private scan key, public spend key, and = public information from the spending transaction A.
See BIP-352 Scanning= . BIP-352 recommends but does not mandate BIP-32 for deriving the scan and = spend keys, but specifies the following derivation paths when BIP-32 is use= d:

=C2=A0 =C2=A0 b_scan =C2=A0=3D BIP32Derive(s, m/352'/coin_typ= e'/account'/1'/0)
=C2=A0 =C2=A0 b_spend =3D BIP32Derive(s, m= /352'/coin_type'/account'/0'/0)

For all silent payme= nt addresses generated using BIP-32, your technique applies. The prover pro= duces a zk-STARK proof that the program BIP32Derive(s, p_scan) and BIP32Der= ive(s, p_spend) were run correctly,
and that the resulting keys reconst= ruct the on-chain output P using along with A.=C2=A0

As you hig= hlighted txid is not committed in the proof currently, the argument is repl= ayable. The current POC does not bind to where the coins go. Anyone who obs= erves the chain could copy it and attach it to a different transaction, spe= nding the same UTXO to a different address. Worse for silent payment, becau= se all user UTXO have the same secret BIP32Derive(s, p_scan) and BIP32Deriv= e(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.=C2=A0

Curious why not generalise beyond BIP-32? P2PKH and P2= WPKH 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 apply here too? The prover argues for the co= rrectness of HASH160(k=C2=B7G) =3D h, where k is the private key scalar and= k=C2=B7G is the elliptic-curve point, without ever revealing k or the pubk= ey. This would allow recovery of a broader set of funds. If it were decided= that classical signatures for these 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 t= he 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 SHA256 = and one modular addition on my CPU back in the day took like 20 seconds. Yo= ur=C2=A0GPU is coming in clutch for this. I= best RISC0 has also improved quite a bit since then.
I think the next o= ptimization step would be pre-seeding the two SHA512 midstates from the hos= t, 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, t= o probably a little over 1sec, and your verifier time will probably drop as= well since that also seems to scale with circuit complexity.=C2=A0<= /div>

I thi= nk I have two half-decent arguments now as to why this won't affect sec= urity:=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 leas= t the same difficulty 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 change= s is the midstate, and the SHA512 input length suffix.=C2=A0Starting 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.=C2=A0A=C2=A0frauduent prover would know t= he 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 Conduition,

> Y= ou need only prove this much more general statement (2): "I know a BIP= 32
> xpriv which derives this xpub via one or more hardened steps&quo= t;.

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

That's an e= xcellent insight!

As mentioned in my recent reply, with risc0's= "succinct" receipt type, I was
able to get the proof size dow= n 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
p= roved, which would speed up the proving time for the normal
default/comp= osite receipt type.

I'll try to hack this up, and then run a he= ad to head comparison to see this
simpler statement actually results in = a smaller proof then the final
succinct receipt of either of the proof v= ariants. 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 magnit= ude re size.

However, this can still be a win as then this would pro= vide potential future
users with a less resource intensive proof, which = can then be
aggregated/rolled up into a final succinct proof in a batche= d 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 cau= ght up on that
proposal. That original thread got pretty long, so I drop= ped of after a
point =F0=9F=98=85. I'll revisit that specific branch= of the thread so I can digest it
and develop a proper opinion, then get= back to you re comparisons!

-- Laolu


On Wed, Apr 8, 20= 26 at 1:23=E2=80=AFPM conduition <
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 circuit (guest= program) could take in an xpriv (e.g. at m/86'/0'=E2= =80=8B) and output a child xpriv (e.g. at m/86'/0'/0&#= 39;=E2=80=8B) to the journal (instead of outputting a child xpub<= /i>).

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

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

Designing the guest program like this will= massively reduce your circuit complexity, because EC point multiplication = is wayyyyy harder for the RISC0 compiler to arithmetize than a simpl= e hash function. In my prior work w= ith RISC0, I made a guest program which ran a SHA256 hash and an EC poi= nt multiplication. I found that pruning EC point arithmetic from my guest p= rogram improved prover runtime by a factor of over 100x.

If I am not fever-dreaming and this= is indeed possible, then the new circuit's complexity will be dominate= d 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 cal= l for STARK proving. Here's a few ideas.

If you bust open HMAC-SHA512, it looks like thi= s:

HMAC_SHA= 512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x3= 6) || 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 byte= s) and msg =3D (0x00 || sk || i) is the parent secret key and = child index.

Sin= ce 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 SHA= 512 padding/length)
  3. (K=E2=8A=950x5c), and
  4. a = final compression call to tie it all together.

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

The question then becomes, which of these c= ompression calls can be done outside the circuit, and which are truly essen= tial 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 func= tion preimage, and is correctly related to the child secret key via modular= addition. So compression call (2) seems unavoidable. The others are less r= igid.

<= /div>
I'd arg= ue that if we really dig into the hard relation we're trying to prove h= ere, we can reduce 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 sk=E2=80=8B such that:=

I <- SHA512(<something> || SHA512(<something> || 0= x00 || 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 ar= e arbitrary, and we know in BIP32 they are always exactly one-block long, i= t seems easy to throw out the compression calls (1) and (3). The host can p= recompute the relevant SHA512 midstates outside the circuit, and pass the m= idstates into the guest program as secret inputs. The tradeoff is that this permits m= alicious provers the flexibility of choosing their starting midstates (thou= gh hash input length can be fixed at 192 bytes). I'm not entirely sure = if this meaningfully weakens the verifier's soundness. Ethan Heilman mi= ght have opinions on this, he knows a lot more about attacking hash functio= ns 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 resulting midstates.

This red= uces our circuit to, i think, the minimum acceptable security floor for pro= vers: two SHA512 compression calls, which commit to a parent secret key.


re= gards,
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 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 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 bitcoindev+...@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 bitcoindev+...@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 bitcoindev+...@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 bitcoindev+...@googlegro= ups.com.
To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee87626def6= 5n%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/49236a10-94ea-440a-9b53-63ae2c7ac964n%40googlegroups.com.
------=_Part_8217_201299178.1777591053148-- ------=_Part_8216_1372975127.1777591053148--