From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 13 Apr 2026 12:21:57 -0700 Received: from mail-qv1-f59.google.com ([209.85.219.59]) 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-0007HD-Lr for bitcoindev@gnusha.org; Mon, 13 Apr 2026 12:21:57 -0700 Received: by mail-qv1-f59.google.com with SMTP id 6a1803df08f44-8aca4660827sf54479116d6.3 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=n42osqCqzudLblW0GO1Vz7QTkBPKSx3h8rtdnHlQITs=; b=XLiEirnUlRIgfIL/pjeGlkD/wQcjV4djpsHE1a7uAITNt1r0Io0frdU3hjDoaZhUcH VG7Nmjb3CBAvdMp3183BZ2KxycyJL3xUhKPpzoHC38L5DfUxbE70ho8AHJw4cYD1AhvV u0dvODbBGXwgmY5u2RQxH92QF+RuR+svX98pYPTKC97k4FCsCxpd+BJWNSLNff/nQiB4 JO6TQeQ9PSCp4sOsbM0umy8xwkl9bp2ngPTfN/hbVbzYHPpT7q+9pA/E3meKV+rR1Wmd 5bY7xy70WFwPX3sSRG17aVmfUpY/8bKv16XBoxqilAydNiQ0dPY/Uf2mjNbF+ZBo2wBU vRbw== 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=n42osqCqzudLblW0GO1Vz7QTkBPKSx3h8rtdnHlQITs=; b=adxDN/HJoQtuHKG6jshWRXbZlsSCOHaniyLnOEMoxHPU0d9OyTj6Xf7PJhxPjRCLFG sJj9omspZThH/e3uK9oTVlx2BvLjWSfAqXbfJnsGcu1e4euf2IuiSaiFL+bVFLFrwN7Q 5YoxkZK/uyTLeAK5z1tevyyPORLKpagMWurbCyauyswD+UYcF5vpC6l1D9QFQEyDRIQV kNanr1RsY2HHmZ1zeba/DgF9+wbooIhxc3XzRG1SUbJyctP8/6fZ27F6hW+C1qsWpFSS MJbva/cOo7cxN3l/8QGfg+0PamQoD5O8WbeZCshLBpjqU9Rv8ArhVFf+SEmV78B7Bycp /NGg== 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=n42osqCqzudLblW0GO1Vz7QTkBPKSx3h8rtdnHlQITs=; b=WtBAKyGziUlmxhWXTof0zhzIGbCis+AvRl0PnDkL94Kbo7rXme9hg0aun03WR8rK5H I/E+njrLpkggsYIeMxjCyozN8Cgxtjkyp4rVyq2KWvHfukg+YKWCoeuFxRE+Cd3IcPWD kUGghR1Jb/y32GBpH8us+du7XYv2Y5nAst/2j8URyLhFAGPfI40HK7e+Rs4lx8r6RAYE HCiPJiQMQCVlcoFyTNWYtQOQBMJ3SE4xzt60vzT1OICMbZD4i7Naqv/cGYTe4sGmWMoj 3c9lYy3dkj4R5PfjGMu66WX5ym3FQhCpAtUk37OMgrhQOBwATr4PXY7V2v5NPoK3BaBp dd6Q== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ+LIlmerV7P8+43GI2dn8dtMgEElXbuyfQLY9eFz+QQcmCy7V6s6rTe9PF/uw7HA4rznSX3hD1fAKPI@gnusha.org X-Gm-Message-State: AOJu0YzjRhn9aRoi17MGS9fGcNMG20XQ3QBBf9JF1w5o82HOIvqdSHP0 vuBG0gixVSk6c286ZQMAyntQBOI5aSN/lS0ZIT2O6j1/vtsJ3vgu5w1z X-Received: by 2002:a05:6214:2587:b0:8ac:b4b3:3ce2 with SMTP id 6a1803df08f44-8acb4b3421fmr53778446d6.41.1776108106486; Mon, 13 Apr 2026 12:21:46 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiKa3gGN0czS1S195fnMpLMEN/e1ZwJDKj2ddsB66X4Ljg==" Received: by 2002:ac8:5a10:0:b0:509:2a0e:163b with SMTP id d75a77b69052e-50dd50f60cdls66890231cf.1.-pod-prod-07-us; Mon, 13 Apr 2026 12:21:40 -0700 (PDT) X-Received: by 2002:a05:620a:44cf:b0:8cf:dc6a:18c6 with SMTP id af79cd13be357-8ddcf6b5c80mr2199536885a.50.1776108100239; Mon, 13 Apr 2026 12:21:40 -0700 (PDT) Received: by 2002:a05:690c:4c01:b0:79a:e1a5:fe7e with SMTP id 00721157ae682-7ae240f9947ms7b3; Fri, 10 Apr 2026 02:35:52 -0700 (PDT) X-Received: by 2002:a05:690c:c513:b0:79f:3b8c:a818 with SMTP id 00721157ae682-7af715776b8mr24969247b3.31.1775813750989; Fri, 10 Apr 2026 02:35:50 -0700 (PDT) Date: Fri, 10 Apr 2026 02:35:50 -0700 (PDT) From: Alex To: Bitcoin Development Mailing List Message-Id: 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_77606_470629128.1775813750313" 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_77606_470629128.1775813750313 Content-Type: multipart/alternative; boundary="----=_Part_77607_473905374.1775813750313" ------=_Part_77607_473905374.1775813750313 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I guess my first response got moderated because I was too negative, so here= =20 is the retry: * 1.7 MB is not realistically useful for anything. It's so big that, even= =20 the biggest PQC signatures are orders of magnitude smaller and if you do=20 some basic napkin math you can see that it's realistically never going to= =20 be useful (it would takes decades for people to migrate and it would cost= =20 you more than your entire portfolio to move the funds). Therefore it is=20 realistically unusable. * The sheer complexity of ZK-STARK proofs and their multi-second=20 verification cost is practically never going to land in Bitcoin - for=20 reference - just look at OP_CAT, a 12 line addition that has been stuck in= =20 review for years. Realistically, a multi-million line VM tied to a specific= =20 CPU architecture is absolutely never going to land in Bitcoin just from its= =20 sheer complexity and attack surface it introduces. Therefore it is nothing= =20 more than esoteric make belief, if we are being realistic. For the layman, it is also a lazy way to offload the PQC problem to the=20 future "ah but we just put a ZK proof and we're done" as if ZK proofs are= =20 readily available commodities - they are not. It's not that simple, for the= =20 complexity reasons above. We need slim security assumptions, such as the=20 SHRINCS hash based signatures and we need them now, so that we can migrate= =20 billions of ETF funds already. ZK-STARKs are the new "silver bullet" but realistically, Bitcoin is so=20 ossified (as evident by the multi-year delay for OP_CAT) that discussions= =20 regarding it is, well, esoteric distractions. Also it makes no sense to deny SQIsign based on "it's too complex, we don't= =20 know if the security assumptions hold" and then with the other hand argue= =20 that "let's shove this multi million line CPU VM into Bitcoin and put 1.7= =20 MB proofs that take multiple seconds to verify (that alone is a MAJOR DOS= =20 attack surface) You get my point? It's so easy to say "ZK this, ZK that" but the sheer=20 massive complexity it brings is a gaping flesh wound in terms of attack=20 surface. torsdag 9 april 2026 kl. 23:56:07 UTC+2 skrev Olaoluwa Osuntokun: > 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= ) is=20 >>> the parent secret key and child index.=20 >>> >>> Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we 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*= . The=20 >>> 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 "= 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/= bd1f1379-fffa-4a93-a747-c449c2f7265cn%40googlegroups.com. ------=_Part_77607_473905374.1775813750313 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I guess my first response got moderated because I was too negative, so here= is the retry:

* 1.7 MB is not realistically useful for anything= . It's so big that, even the biggest PQC signatures are orders of magnitude= smaller and if you do some basic napkin math you can see that it's realist= ically never going to be useful (it would takes decades for people to migra= te and it would cost you more than your entire portfolio to move the funds)= . Therefore it is realistically unusable.
* The sheer complexity of ZK= -STARK proofs and their multi-second verification cost is practically never= going to land in Bitcoin - for reference - just look at OP_CAT, a 12 line = addition that has been stuck in review for years. Realistically, a multi-mi= llion line VM tied to a specific CPU architecture is absolutely never going= to land in Bitcoin just from its sheer complexity and attack surface it in= troduces. Therefore it is nothing more than esoteric make belief, if we are= being realistic.

For the layman, it is also a lazy way to offlo= ad the PQC problem to the future "ah but we just put a ZK proof and we're d= one" as if ZK proofs are readily available commodities - they are not. It's= not that simple, for the complexity reasons above. We need slim security a= ssumptions, such as the SHRINCS hash based signatures and we need them now,= so that we can migrate billions of ETF funds already.

ZK-STARKs= are the new "silver bullet" but realistically, Bitcoin is so ossified (as = evident by the multi-year delay for OP_CAT) that discussions regarding it i= s, well, esoteric distractions.

Also it makes no sense to deny S= QIsign based on "it's too complex, we don't know if the security assumption= s hold" and then with the other hand argue that "let's shove this multi mil= lion line CPU VM into Bitcoin and put 1.7 MB proofs that take multiple seco= nds to verify (that alone is a MAJOR DOS attack surface)

You get= my point? It's so easy to say "ZK this, ZK that" but the sheer massive com= plexity it brings is a gaping flesh wound in terms of attack surface.
torsdag 9 april= 2026 kl. 23:56:07 UTC+2 skrev Olaoluwa Osuntokun:
Hi Condution,=C2=A0<= br>
So I implemented both variants of your idea. My intuition was right = in that it
doesn't do much to reduce the size of the=C2=A0final succ= inct=C2=A0size, but the final
xpriv variant resulted in a significant re= duction in both proving time, and
also memory usage. I also re-ran the o= riginal succint proof for the original
Taproot claim and got a better va= lue for the final proof time (def need a
better benchmark env+set up!).<= br>
Here's a breakdown of the resource requirements for the various = proofs:
=C2=A0 * Full Taproot
=C2=A0 =C2=A0 image ID:
=C2=A0 =C2= =A0 =C2=A0 8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690=
=C2=A0 =C2=A0 composite:
=C2=A0 =C2=A0 =C2=A0 seal 1797880
=C2=A0= =C2=A0 =C2=A0 prove 49.32s
=C2=A0 =C2=A0 =C2=A0 verify 0.10s
=C2=A0 = =C2=A0 =C2=A0 peak RSS 11907399680
=C2=A0 =C2=A0 succinct:
=C2=A0 =C2= =A0 =C2=A0 seal 222668
=C2=A0 =C2=A0 =C2=A0 prove 64.30s
=C2=A0 =C2= =A0 =C2=A0 verify 0.03s
=C2=A0 =C2=A0 =C2=A0 peak RSS 11927207936
=C2=A0 * Hardened xpub
=C2=A0 =C2=A0 image ID:
=C2=A0 =C2=A0 ad4ebc0= ef6ce51e0f581cc8d14742a5b97738e9decd3fe2b0f1746de5bad9617
=C2=A0 =C2=A0 = composite:
=C2=A0 =C2=A0 =C2=A0 seal 513680
=C2=A0 =C2=A0 =C2=A0 prov= e 14.63s
=C2=A0 =C2=A0 =C2=A0 verify 0.04s
=C2=A0 =C2=A0 =C2=A0 peak = RSS 11783503872
=C2=A0 =C2=A0 succinct:
=C2=A0 =C2=A0 =C2=A0 seal 222= 668
=C2=A0 =C2=A0 =C2=A0 prove 17.29s
=C2=A0 =C2=A0 =C2=A0 verify 0.0= 2s
=C2=A0 =C2=A0 =C2=A0 peak RSS 11782307840

=C2=A0 * Hardened xp= riv
=C2=A0 =C2=A0 image ID:
=C2=A0 =C2=A0 =C2=A0 8401a36e4f54cb2beaf9= ac7677603806cf9d775e90ef5a70168045a3c0df0849
=C2=A0 =C2=A0 composite:=C2=A0 =C2=A0 =C2=A0 seal 234568
=C2=A0 =C2=A0 =C2=A0 prove 1.98s
= =C2=A0 =C2=A0 =C2=A0 verify 0.02s
=C2=A0 =C2=A0 =C2=A0 peak RSS 3144171520
=C2=A0 =C2=A0 succinct:
=C2=A0 =C2=A0 =C2=A0 = seal 222668
=C2=A0 =C2=A0 =C2=A0 prove 2.84s
=C2=A0 =C2=A0 =C2=A0 ver= ify 0.02s
=C2=A0 =C2=A0 =C2=A0 peak RSS 3145990144
So we can see that the succinct proof sizes are all about the same. H= owever the
xpriv variant can be proved directly in just 2 seconds on my = machine! It also
requires just 3 GB of memory for the proof as well.
=
I've created some additional supporting documentation to detail exa= ctly what
the new proofs do and their results:

=C2=A0 * https://github.com/Roasbeef/bi= p32-pq-zkp/blob/main/docs/reduced-variants.md

=C2=A0 * https://github= .com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398180a2b3eff7761b7f4b233d455c6c9/RE= ADME.md#reduced-proof-variants

=C2=A0 * https://github.com/Roasb= eef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5171f5e06fa840/docs/claim.m= d#reduced-variant-claims


Once again, thanks for the great id= eas! I wonder if we can improve on this
round of proof golf further befo= re reaching down a lower level with some sort
of AIR compiler =F0=9F=A4= =94.

-- Laolu

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

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

&= gt; I'm amending my prior suggestion slightly: The circuit (guest progr= am)
> 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 (inste= ad of outputting a child
> xpub).

That's an excellent ins= ight!

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

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

I'll try to hack this up, and then run a head to head c= omparison to see this
simpler statement actually results in a smaller pr= oof then the final
succinct receipt of either of the proof variants. Bas= ed on my current
intuition w.r.t the lower level details, I think the fi= nal succinct proof
size would be on the same order of magnitude re size.=

However, this can still be a win as then this would provide potenti= al future
users with a less resource intensive proof, which can then be<= br>aggregated/rolled up into a final succinct proof in a batched manner.
This line of optimization is also more interesting if one were to look= at
hand rolling a custom AIR to avoid the overhead that the RISC-V emul= ation
adds to the rirsc0 proof chain, given that it entirely skips doing= any EC
operations at all for the final statement.

----

Re= the commit/reveal approach, to be honest I'm not fully caught up on th= at
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 thre= ad so I can 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 <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 progra= m) could take in an xpriv (e.g. at m/86'/0'=E2=80=8B) = and output a child xpriv (e.g. at=C2=A0m/86'/0'/0'= =E2=80=8B) to the journal (instead of outputting a child xpub= ).=C2=A0
This is = safe because remember, EC spending has been disabled in this context, and t= o a quantum attacker, an xpub is computationally equivalent to its xpriv. S= o why bother hiding it? The child xpriv doesn't give an observer anythi= ng they can't already do with the equivalent xpub.=C2=A0

The guest program then is basic= ally the BIP32 CKDpriv algorithm, restricted to a single hardened derivatio= n step. The verifier gets the child xpriv, but can't use it to forge ne= w proofs. Honest verifiers use the xpriv to derive the child address(es) as= suggested in my last message, to authenticate spending.

Designing the guest program like th= is will massively reduce your circuit complexity, because EC point multipli= cation is wayyyyy harder for the RISC0 compiler to arithmetize than = a simple hash function. In my prior work with RISC0,= I made a guest program which ran a SHA256 hash and an EC point multiplicat= ion. I found that pruning EC point arithmetic from my guest program improve= d prover runtime by a factor of over 100x.

If I am not fever-dreaming and this is indeed pos= sible, then the new circuit's complexity will be dominated not by point= multiplication, but by the HMAC-SHA512 call. Our new task is then to figur= e out how much we can internally optimize the HMAC-SHA512 call for STARK pr= oving. Here's a few ideas.

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

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

...where in the context of BIP32 hardened CKD, the HMAC key=C2= =A0K=E2=80=8B is the chaincode (padded with zeros to 128 bytes= ) and msg =3D (0x00 || sk || i)=C2=A0is the parent secret key = and child index.=C2=A0

Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B blo= ck size, we need a total of 4 SHA512 compression calls:=C2=A0
  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=C2=A0(K=E2=8A=950x5c), and=C2=A0
  4. a final compression call to tie it all together.=C2= =A0

The ou= tput of that last compression call is partitioned into the child chaincode,= and a key delta which is added to the parent secret key (modulo the curve order= ), = producing the child EC secret key. This last step is arithmetically simple;= the SHA512 calls are where most of the arithmetic complexity lies.<= br>

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

Note how the parent secret key is the= most important=C2=A0piece for soundness. The circuit needs to prove the pa= rent secret key existed in the hash function preimage, and is correctly rel= ated to the child secret key via modular addition. So compression call (2) = seems unavoidable. The others are less rigid.

I'd argue that if we really dig into the h= ard relation we're trying to prove here, we can reduce it to this state= ment:

<= /div>
Given a child xpriv with secret key k=E2=80=8B, chaincode c=E2=80=8B and ind= ex i<= /code>=E2=80= =8B,=C2=A0I know a preimage x=E2=80= =8B and secret key sk=E2=80=8B=C2=A0such that:

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

=
Seeing= as the <something>=E2=80=8B slots are arbitrary, and we= know in BIP32 they are always exactly one-block long,=C2=A0it seems easy t= o throw out the compression calls (1) and (3). The host can precompute the = relevant SHA512 midstates outside the circuit, and pass the midstates into = the guest program as secret inputs.=C2=A0The tradeoff is that this=C2=A0permits malic= ious provers the flexibility of choosing their starting midstates (though h= ash input length can be fixed at 192 bytes). I'm not entirely sure if t= his meaningfully weakens the verifier's soundness. Ethan Heilman might = have opinions on this, he knows a lot more about attacking hash functions t= han I do. Intuitively, I doubt sampling random SHA512 midstates is that muc= h better than sampling a random HMAC key (chaincode)=C2=A0K=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=C2=A0Laolu,

Great work getting this wo= rking in the real world. I've heard many people on delving and the mail= ing list conjecture based on this idea, but you're the first person i&#= 39;ve seen who's willing to put their money where their mouth is, and a= ctually build a prototype. Bravo!

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

In reality, you needn't go so far= as to prove (1)=C2=A0"I know a BIP39 seed which derives this tapro= ot output key". You need only prove this much more general stateme= nt (2):=C2=A0"I know a BIP32 xpriv which derives this xpub via one = or more hardened steps". The latter statement (2) still cannot be = forged by a quantum adversary even if they know your account-level xpub, bu= t it entails far less computation to prove and verify. The rest of the orig= inal statement (1) can be done externally outside the circuit.
Example. If i have a wallet with a taproot address at=C2= =A0m/86'/0'/0'/1/2=E2=80=8B, I could prove = I know the xpriv at=C2=A0m/86'/0'=E2=80= =8B which derives the xpub at=C2=A0m/86'/0'/0= 9;=E2=80=8B. Then I provide the remaining key path elements /1= /2=E2=80=8B in the witness. Note, i=C2=A0do not=C2=A0mean we=C2=A0derive=C2=A0the xpriv at=C2=A0m= /86'/0'=E2=80=8B inside the guest program. I mean the prover= derives=C2=A0m/86'/0'=E2=80=8B first (in= the host), and=C2=A0then writes that xpriv into the guest = program's inputs.=C2=A0The guest program derives and outputs the xp= ub at=C2=A0m/86'/0'/0'=E2=80=8B.=C2= =A0The verifier may check the STARK output (xpub) is correctly computed, th= en use the given key-path to manually derive the taproot address from the x= pub themselves, outside the circuit, and validate=C2=A0that= address=C2=A0against the UTXO i'm spending. The verifier thus has = confirmed the prover knew an xpriv which (through a hardened derivation ste= p) derives the correct taproot output key.

This ch= ange significantly reduces the size of the circuit. From a glance, I see th= e original guest program performs 6 HMAC-SHA512 calls (1 for the master key= , 5 for the BIP32 derivation steps), two SHA256 compression calls (for the = taptweak hash), and two point multiplications. With this simplified variant= , we are invoking only a single HMAC-SHA512 call and a single point multipl= ication. I can't say for sure, but I expect this will improve your proo= f 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 addres= ses.

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

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

F= or a slightly related work proving a similar relation for hashed addresses,= using different STARK technology stacks,=C2=A0see = this delving post.

However, all this said, my = personal preference for long-term procrastinator rescue is still for commit= /reveal strategies which prove essentially the same statement about BIP32 i= n a two-step procedure. They get the job done with much lighter cryptograph= ic machinery and much smaller witnesses: a few hundred bytes over two trans= actions, compared to a few million bytes in one transaction with STARKs.=C2=A0Boris Nagaev and I discussed this on the list a while bac= k. That said, commit/reveal requires more careful design and seems to d= emand the use of external quantum-safe coins to make the commitment in the = first place, so perhaps the cost would be worth it to some people? IDK. Wha= t do you think of commit/reveal compared to STARKs for this purpose?
<= div>
regards,=
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <<= a href data-email-masked rel=3D"nofollow">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 bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/bd1f1379-fffa-4a93-a747-c449c2f7265cn%40googlegroups.com.
------=_Part_77607_473905374.1775813750313-- ------=_Part_77606_470629128.1775813750313--