From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 10 Apr 2026 10:47:20 -0700 Received: from mail-oo1-f61.google.com ([209.85.161.61]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wBFwq-00005B-Hq for bitcoindev@gnusha.org; Fri, 10 Apr 2026 10:47:20 -0700 Received: by mail-oo1-f61.google.com with SMTP id 006d021491bc7-672c40f3873sf6128180eaf.2 for ; Fri, 10 Apr 2026 10:47:15 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1775843230; cv=pass; d=google.com; s=arc-20240605; b=bEQGlxD8CrDsZ0ZF58fnQc7SeauDtLd5QOBP8MKJELhRDWwSGS3AOqJu+sgf8ZUInf Ondb95sEd5qUgO0tZiITaSqqhvQToBm26NCCFEhfuzXPNUQ9MveTerf86v8bt8MorZ19 nDnskaCv4hIx87MVJdFp3QTBXnrEZp6XSBTMdr8VVRtYnW/AfrDSLN8RzlpScXQzgE98 YHiXjsX8OOdI7OycnyWLtEDdsFSrzTs8h9CmzJZWIbhmEbLHHI6QyouzyZw6rBskbX50 XsEwBaCVzYbZJVcBR4+bxsChimn9JB2qySKSG/xBz7GqFbpFaIdY4bfYlXoa0zzgESSo Cu/A== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:mime-version:feedback-id :references:in-reply-to:message-id:subject:cc:from:to:date :dkim-signature; bh=ScN6czlc7i0uLzdoOMbDJnPuWv4JeUsodUJ7gim5WKY=; fh=d/zSPucf3Y2MIxGHKzTvTbtpP1Wv78mbirrtF71cVAU=; b=VZQ6cJJLeNGkTuh6StP+WByyrhvTrVBUUFlLQK0Z5gSQRqEe4zzbFLk4nVFXFH/Qp1 vPyq1EU+gNNnRc54mMKpWTWzX2op1WEg4UqnDmAizN9BSOsAJWtd9Vswu96sz7SkoNZl eRN76OwnopQpJ9XSsk8UDXSG/TRwSQmJrVYcXmmtV4j2ZPU03f+CH0XHDBeMglUXwLaW 9ge3VYBZqPqKRE/pANIzGhREayXp1RSVV/403mx74PAVrFUWpD2ZNxnGTGN2qffIwG1e 21R1PKc0KHfDHCqbQJFnL/SEWbRvyop2j5KrLRKtRXOF+aUDY0T5oDyd5aBKweYYI2dJ vZKA==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b="VgHE1t/u"; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.167 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1775843230; x=1776448030; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:from:to:cc:subject:date:message-id:reply-to; bh=ScN6czlc7i0uLzdoOMbDJnPuWv4JeUsodUJ7gim5WKY=; b=disFwvDtL+9UNVAzSCDxwLiUucnGBuAf9OTEt5d2MJOJDOwwwu8+e6dS5bYBAPgXmG S2pv0/hWVN/vkbnMNsw59vvHqBJNG91t7ejK6taAF+C+mhhLZBYxLTAo13pjgRsE06h8 AV4kLoMbgQMFITsqAnpU3QT3uyhwPxCVgFO7xyFtmTqE31jf++676pts+wuzgdr9Ey6g mABApS2TEw27XIFUBZY7GKf81gzcmMZpEU03PkEq6Gclq9j37Wtvfojm2UXofzZ6wMzf 3hn1mQgITEEit4l4PHYHd6fXo73oU9HJ09V51LMBbA01jM4tsYmuFU0ShfWR4wzErwHV tsSg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1775843230; x=1776448030; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:mime-version :feedback-id:references:in-reply-to:message-id:subject:cc:from:to :date:x-beenthere:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=ScN6czlc7i0uLzdoOMbDJnPuWv4JeUsodUJ7gim5WKY=; b=YqxaxT3GlJmLTGe/ZGT2ai6vJQQxVsqtKcr7mysIMPHnMS+iHUYjTg89eu1nFATWvG nuYOPkY0LNrQseFPGUoiWI/nnqtPLOFxQdX4kCbqrlZpWitxg3Jp39Cn+Ee9Zi8eoCr6 UpfIGJMYaULsfMyO8T1B3Hd/g84zuL4ogdcuM8H/D3ZMV2yzV3jdz9R/NupB7ujdkqk8 QW2sAcyNwIasHYaV7bnqVZ3Uax1O9eFdlk4J0lPfwQNsIcpZ41cSkDPO0qLwOTM4Ai2J 221waeduIhFtsKFs4XVrBECTLWiUmijMYlPOqvPS126b9qxDcXcj3L3V2cNPY0r8rSNc UdmA== X-Forwarded-Encrypted: i=2; AJvYcCUa4NR3dw3tfZkZtgo+lNFpK0EhhMn6iRDIzxj0P9a1B+zZTBz87J90fQo44pxvTyYSc1whT2TrXJSs@gnusha.org X-Gm-Message-State: AOJu0YxgtPVU2MopUpZvmw8uu+KjBSaGB7hy6Q8fTOfYNCnoiBVwMS4t 1sA35+dbge1OfLrsyP18yyCJdgcK+hn4UpKCHiQqQ5EfLII2mLGgSlaT X-Received: by 2002:a05:6820:2907:b0:683:c005:54fa with SMTP id 006d021491bc7-68be80deb43mr1974119eaf.41.1775843229510; Fri, 10 Apr 2026 10:47:09 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiLiQ+9ZHEz1S0zhz4eFLgI0tvjAoiRuyYuXCZfMKVvixg==" Received: by 2002:a05:6820:16a5:b0:688:c001:f814 with SMTP id 006d021491bc7-68bc21e6779ls779287eaf.1.-pod-prod-08-us; Fri, 10 Apr 2026 10:47:03 -0700 (PDT) X-Received: by 2002:a05:6808:1b0f:b0:470:434b:aec4 with SMTP id 5614622812f47-4789d03c45emr2452425b6e.12.1775843223310; Fri, 10 Apr 2026 10:47:03 -0700 (PDT) Received: by 2002:a05:600c:47d3:b0:488:963a:630a with SMTP id 5b1f17b1804b1-488cf306c28ms5e9; Fri, 10 Apr 2026 09:28:53 -0700 (PDT) X-Received: by 2002:a05:600c:3b24:b0:480:2521:4d92 with SMTP id 5b1f17b1804b1-488d687adb3mr50705995e9.24.1775838531504; Fri, 10 Apr 2026 09:28:51 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1775838531; cv=none; d=google.com; s=arc-20240605; b=hFi2GsObKYVqyCJyIY8bWzy8GQ6PsBl+Gq0p++abwzqkGwaeI4dHTCRKQTWn7nbzp/ ytL7myt0EW9ldAASWFAaaPH4Q77wGK61xtaNxgrNZpOR4Ud2RvNTthFm3Rye+8zU2/iz sVqC4c88ukHj8Nod97uIpDMOln++TTy3PY7JjWVdWrNucP1cBRK5tZ2p+lb9qzf9mobC GsK3nO8E8SMUD8XObyRuCtQYGb9kd/wBG66hABoFpc6P9T3H3WRs6Vai7DnRVOVRxIi6 FdTxsxz+BRTLthXfMnf+pzCWKbIkpJ2492/qTkfjqsZ50DaO0YDjjVLD1TINxfRfC3+1 qNLg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=mime-version:feedback-id:references:in-reply-to:message-id:subject :cc:from:to:date:dkim-signature; bh=iEzk+2GN4iaJX1CqVLxoLCREMPHXP848wDutA9sw1Ug=; fh=CNTb87jy3GNs5uozchLglwf0rB342Ocv9OeI2RgMvv8=; b=TzxBhSN3wVHuEwm4z7NbtubVMsuStMHVeRLmyd2qtbnQNB7NagnCXkJWqSRCI7i1bE PJReDgxTSisQ29IphJR3+MmbT9dEIOyFMfGF6C4qMhetViwZrxl4jHS+ey+lwBUmO6SM Doqj0vq8c6aLUsWPyW6HGF3Z9oB5d6URGi+2wEeJ3ym7sF/SINHcw0B7FMJDpHMbL/9T 9mFk1oII3tBE2uCqTSyeRyPnFkCSHS08ZeO1q1Jr2xy/67uDKIxw1vto9Jr7BrF10HEu 9bY5ewy6mvRXqat8SK8I5YfemzI0qPsoxefrFvgblIOi0QoCqIhlINsxUfkfkto5ExvU 8B0w==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b="VgHE1t/u"; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.167 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-43167.protonmail.ch (mail-43167.protonmail.ch. [185.70.43.167]) by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-488d67a4642si333205e9.1.2026.04.10.09.28.51 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 10 Apr 2026 09:28:51 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 185.70.43.167 as permitted sender) client-ip=185.70.43.167; Date: Fri, 10 Apr 2026 16:28:45 +0000 To: Olaoluwa Osuntokun From: "'conduition' via Bitcoin Development Mailing List" Cc: Bitcoin Development Mailing List Subject: Re: [bitcoindev] Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge Message-ID: In-Reply-To: References: Feedback-ID: 72003692:user:proton X-Pm-Message-ID: 4a8555e8447829d84bfadd143f3472732f5715b9 MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------be331b9834f7a8b1f7b49b5e049164d91e760486cb8da8ba624e0199799dd32b"; charset=utf-8 X-Original-Sender: conduition@proton.me X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b="VgHE1t/u"; spf=pass (google.com: domain of conduition@proton.me designates 185.70.43.167 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me X-Original-From: conduition Reply-To: conduition Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -1.0 (-) This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --------be331b9834f7a8b1f7b49b5e049164d91e760486cb8da8ba624e0199799dd32b Content-Type: multipart/mixed;boundary=---------------------73cbe1bef66504fb597ed057fe711656 -----------------------73cbe1bef66504fb597ed057fe711656 Content-Type: multipart/alternative;boundary=---------------------f115dbdf5cca6640c154bf4a380c8d97 -----------------------f115dbdf5cca6640c154bf4a380c8d97 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" Ah! Amazing work! 2 seconds to prove is really crazy. Proving a single SHA2= 56 and one modular addition on my CPU back in the day took like 20 seconds.= Your=C2=A0GPU is coming in clutch for this. I best RISC0 has also improved= quite a bit since then. I think the next optimization step would be pre-seeding the two SHA512 mids= tates from the host, so you only need to prove two SHA512 compression calls= instead of four. Intuitively I expect this would at best halve your prover= time from 2sec, to probably a little over 1sec, and your verifier time wil= l probably drop as well since that also seems to scale with circuit complex= ity.=C2=A0 I think I have two half-decent arguments now as to why this won't affect se= curity:=C2=A0 First, even if a fraudulent prover is=C2=A0handed the correct midstates to = use, the prover would still have to do the hard work of finding the parent = secret key needed as a witness. This is at least the same difficulty as fin= ding the parent `sk` if we just hashed it without a chaincode at all, using= two bare SHA512 calls - the only thing that changes is the midstate, and t= he SHA512 input length suffix.=C2=A0Starting from a different midstate does= n't magically give the attacker a head-start in a 256-bit search space look= ing for `sk`.=C2=A0A=C2=A0frauduent prover would know the child secret key= =C2=A0`k =3D sk + int(I[32:]) % n`, but they don't know=C2=A0`int(I[32:])`= =C2=A0or=C2=A0`sk` so they cannot solve for either. Nominally, the fraudulent prover wouldn't even know the correct midstates, = so their task is strictly harder. Secondly, here's another argument as to why finding the midstates in the fi= rst place should also be hard.=C2=A0 Any adversary who could solve this problem by finding the right midstates c= ould be used as an oracle to prove the existence of partial 2-cycles in SHA= 512.=C2=A0 - Given a SHA512 hash=C2=A0`I`, set `sk =3D int(I[32:])` - Compute=C2=A0`k =3D sk + sk % n` - Use the black-box fraudulent prover on the child key=C2=A0`k` to find c= orrect midstates such that=C2=A0 =20 ` ` `` `I =3D=3D SHA512( || SHA512( || 0x00 || sk || i))`= `` `k =3D=3D int(I[32:]) + sk % n` =C2=A0 `=3D=3D sk + sk % n` Remember that `sk =3D int(I[32:])`.=C2=A0Thus for these conditions to hold,= the proof forger must be able to find not just the correct midstates, but = also midstates which give a 2-stage partial hash cycle so that: `I =3D=3D SHA512( || SHA512( || 0x00 || I[32:] || i))= ` This seems unlikely or at least very difficult. regards, conduition On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun wrote: > Hi Condution, >=20 > So I implemented both variants of your idea. My intuition was right in th= at it > doesn't do much to reduce the size of the final succinct size, but the fi= nal > 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 origi= nal > Taproot claim and got a better value for the final proof time (def need a > better benchmark env+set up!). >=20 > 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 >=20 > * Hardened xpub > image ID: > ad4ebc0ef6ce51e0f581cc8d14742a5b97738e9decd3fe2b0f1746de5bad9617 > composite: > seal 513680 > prove 14.63s > verify 0.04s > peak RSS 11783503872 > succinct: > seal 222668 > prove 17.29s > verify 0.02s > peak RSS 11782307840 >=20 > * Hardened xpriv > image ID: > 8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0df0849 > composite: > seal 234568 > prove 1.98s > verify 0.02s > peak RSS 3144171520 > succinct: > seal 222668 > prove 2.84s > verify 0.02s > peak RSS 3145990144 >=20 > So we can see that the succinct proof sizes are all about the same. Howev= er 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. >=20 > I've created some additional supporting documentation to detail exactly w= hat > 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 >=20 >=20 > 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 = sort > of AIR compiler =F0=9F=A4=94. >=20 > -- Laolu >=20 > On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osuntokun wrote: >=20 > > Hi Conduition, > >=20 > > > You need only prove this much more general statement (2): "I know a B= IP32 > > > xpriv which derives this xpub via one or more hardened steps". > >=20 > > > I'm amending my prior suggestion slightly: The circuit (guest program= ) > > > could take in an xpriv (e.g. at m/86'/0') and output a child xpriv > > > (e.g. at m/86'/0'/0') to the journal (instead of outputting a child > > > xpub). > >=20 > > That's an excellent insight! > >=20 > > As mentioned in my recent reply, with risc0's "succinct" receipt type, = I was > > able to get the proof size down to 220 KB, at the cost of 3.5x longer t= otal > > proving time. > >=20 > > Your proposal definitely reduces the complexity of the core statement t= o 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= 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 pro= of > > size would be on the same order of magnitude re size. > >=20 > > However, this can still be a win as then this would provide potential f= uture > > users with a less resource intensive proof, which can then be > > aggregated/rolled up into a final succinct proof in a batched manner. > >=20 > > This line of optimization is also more interesting if one were to look = at > > hand rolling a custom AIR to avoid the overhead that the RISC-V emulati= on > > adds to the rirsc0 proof chain, given that it entirely skips doing any = EC > > operations at all for the final statement. > >=20 > > ---- > >=20 > > Re the commit/reveal approach, to be honest I'm not fully caught up on = that > > proposal. That original thread got pretty long, so I dropped of after a > > point =F0=9F=98=85. I'll revisit that specific branch of the thread so = I can digest it > > and develop a proper opinion, then get back to you re comparisons! > >=20 > > -- Laolu > >=20 > > On Wed, Apr 8, 2026 at 1:23=E2=80=AFPM conduition wrote: > >=20 > > > Oh, I've been a fool, a foolish fool. > > >=20 > > > We don't even need to do point multiplication in the circuit at all. > > >=20 > > > I'm amending my prior suggestion slightly: The circuit (guest program= ) could take in an xpriv (e.g. at `m/86'/0'`) and output a child xpriv (e.g= . at `m/86'/0'/0'`) to the journal (instead of outputting a child xpub). > > >=20 > > > This is safe because remember, EC spending has been disabled in this = context, and to a quantum attacker, an xpub is computationally equivalent t= o its xpriv. So why bother hiding it? The child xpriv doesn't give an obser= ver anything they can't already do with the equivalent xpub. > > >=20 > > > The guest program then is basically the BIP32 CKDpriv algorithm, rest= ricted to a single hardened derivation step. The verifier gets the child xp= riv, but can't use it to forge new proofs. Honest verifiers use the xpriv t= o derive the child address(es) as suggested in my last message, to authenti= cate spending. > > >=20 > > > Designing the guest program like this will massively reduce your circ= uit complexity, because EC point multiplication is wayyyyy harder for the R= ISC0 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 = multiplication. I found that pruning EC point arithmetic from my guest prog= ram improved prover runtime by a factor of over 100x. > > >=20 > > > If I am not fever-dreaming and this is indeed possible, then the new = circuit's complexity will be dominated not by point multiplication, but by = the HMAC-SHA512 call. Our new task is then to figure out how much we can in= ternally optimize the HMAC-SHA512 call for STARK proving. Here's a few idea= s. > > >=20 > > > If you bust open HMAC-SHA512, it looks like this: > > >=20 > > > `HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x36) |= | msg))` > > >=20 > > > ...where in the context of BIP32 hardened CKD, the HMAC key `K` is th= e chaincode (padded with zeros to 128 bytes) and `msg =3D (0x00 || sk || i)= ` is the parent secret key and child index. > > >=20 > > > Since `len(K) =3D 128` is the SHA512 block size, we need a total of 4= SHA512 compression calls: > > >=20 > > > 1. to compress `(K=E2=8A=950x36)` > > > 2. to compress the `msg` (and SHA512 padding/length) > > > 3. to compress (K=E2=8A=950x5c), and > > > 4. a final compression call to tie it all together. > > >=20 > > >=20 > > > The output of that last compression call is partitioned into the chil= d chaincode, and a key delta which is added to the parent secret key (modul= o the curve order), producing the child EC secret key. This last step is ar= ithmetically simple; the SHA512 calls are where most of the arithmetic comp= lexity lies. > > >=20 > > > The question then becomes, which of these compression calls can be do= ne outside the circuit, and which are truly essential for security? > > >=20 > > > Note how the parent secret key is the most important piece for soundn= ess. The circuit needs to prove the parent secret key existed in the hash f= unction preimage, and is correctly related to the child secret key via modu= lar addition. So compression call (2) seems unavoidable. The others are les= s rigid. > > >=20 > > > I'd argue that if we really dig into the hard relation we're trying t= o prove here, we can reduce it to this statement: > > >=20 > > > Given a child xpriv with secret key `k`, chaincode `c` and index `i`,= I know a preimage `x` and secret key `sk` such that: > > > ` ` > > > `I <- SHA512( || SHA512( || 0x00 || sk || i)`) > > > `c =3D=3D I[:32]` > > > `k =3D=3D int(I[32:]) + sk % n` > > >=20 > > > Seeing as the `` slots are arbitrary, and we know in BIP32= they are always exactly one-block long, it seems easy to throw out the com= pression calls (1) and (3). The host can precompute the relevant SHA512 mid= states outside the circuit, and pass the midstates into the guest program a= s secret inputs. The tradeoff is that this permits malicious provers the fl= exibility of choosing their starting midstates (though hash input length ca= n be fixed at 192 bytes). I'm not entirely sure if this meaningfully weaken= s the verifier's soundness. Ethan Heilman might have opinions on this, he k= nows a lot more about attacking hash functions than I do. Intuitively, I do= ubt sampling random SHA512 midstates is that much better than sampling a ra= ndom HMAC key (chaincode) `K` and computing the resulting midstates. > > >=20 > > >=20 > > > This reduces our circuit to, i think, the minimum acceptable security= floor for provers: two SHA512 compression calls, which commit to a parent = secret key. > > >=20 > > >=20 > > >=20 > > >=20 > > > regards, > > > conduition > > > On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via Bitcoin D= evelopment Mailing List wrote: > > >=20 > > > > Hi Laolu, > > > > Great work getting this working in the real world. I've heard many = people on delving and the mailing list conjecture based on this idea, but y= ou're the first person i've seen who's willing to put their money where the= ir mouth is, and actually build a prototype. Bravo! > > > >=20 > > > > It seems to me the circuit (guest program) could be simplified. Not= ice how the guest code computes the entire HD wallet key path, including ha= rdened and non-hardened derivation steps, and also computes the taproot out= put key with key-tweaking. I'd argue these steps are extraneous to the core= hard relation you want the STARK to prove, and could be safely removed to = reduce proof size and improve performance. > > > >=20 > > > > In reality, you needn't go so far as to prove (1) "I know a BIP39 s= eed which derives this taproot output key". You need only prove this much m= ore general statement (2): "I know a BIP32 xpriv which derives this xpub vi= a one or more hardened steps". The latter statement (2) still cannot be for= ged by a quantum adversary even if they know your account-level xpub, but i= t entails far less computation to prove and verify. The rest of the origina= l statement (1) can be done externally outside the circuit. > > > >=20 > > > > Example. If i have a wallet with a taproot address at `m/86'/0'/0'/= 1/2`, I could prove I know the xpriv at `m/86'/0'` which derives the xpub a= t `m/86'/0'/0'`. Then I provide the remaining key path elements /`1/2` in t= he witness. Note, i do not mean we derive the xpriv at `m/86'/0'` inside th= e guest program. I mean the prover derives `m/86'/0'` first (in the host), = and then writes that xpriv into the guest program's inputs. The guest progr= am derives and outputs the xpub at `m/86'/0'/0'`. The verifier may check th= e STARK output (xpub) is correctly computed, then use the given key-path to= manually derive the taproot address from the xpub themselves, outside the = circuit, and validate that address against the UTXO i'm spending. The verif= ier thus has confirmed the prover knew an xpriv which (through a hardened d= erivation step) derives the correct taproot output key. > > > >=20 > > > > This change significantly reduces the size of the circuit. From a g= lance, I see the 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 sim= plified variant, we are invoking only a single HMAC-SHA512 call and a singl= e point multiplication. I can't say for sure, but I expect this will improv= e your proof size and runtime significantly. > > > >=20 > > > > This change also makes the circuit more generally applicable to oth= er 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 ke= y, or to P2(W)PKH addresses. > > > >=20 > > > > Concerned about publishing xpubs? Remember that we are assuming reg= ular EC spending is locked in this context, so it is safe-ish to share acco= unt xpubs with quantum attackers. At best the xpub can be used for surveill= ance but not forgery. If one would prefer not to share the account-level xp= ub on-chain for privacy reasons, the proof could be extended to also derive= the unhardened child xpub at `/1/2` inside the guest program (but we still= do not need to do the taproot key tweaking in the guest program). > > > >=20 > > > > We should also talk scaling efficiency. Given the cost of STARKs, t= his style of proof should be able to authorize spends for more than one UTX= O. Say you have a wallet with 10 different UTXOs held by distinct addresses= in the same BIP44 account. One single STARK proof could authorize spending= all 10 of them, by simply committing all 10 input signature hashes into th= e journal, and labeling the inputs with the corresponding 10 BIP32 key path= s somehow. The verifier would need to check the proof only once and not 10 = times. The 10 UTXO spends could be validated using the common xpub from the= STARK proof's journal. > > > >=20 > > > > For a slightly related work proving a similar relation for hashed a= ddresses, using different STARK technology stacks, see this delving post. > > > >=20 > > > > However, all this said, my personal preference for long-term procra= stinator rescue is still for commit/reveal strategies which prove essential= ly 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 hundred bytes over two transactions, compared to a few million bytes= in one transaction with STARKs. Boris Nagaev and I discussed this on the l= ist a while back. That said, commit/reveal requires more careful design and= seems to demand the use of external quantum-safe coins to make the commitm= ent in the first place, so perhaps the cost would be worth it to some peopl= e? IDK. What do you think of commit/reveal compared to STARKs for this purp= ose? > > > >=20 > > > > regards, > > > > conduition > > > > On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun wrote: > > > >=20 > > > > > Hi y'all, > > > > >=20 > > > > > I found some spare time this last weekend to dust off a little si= de project > > > > > I started last August: extend TinyGo [1] to be able to produce RI= SC-V ELF > > > > > binaries capable of being run as a guest on the risc0 platform to= generate > > > > > zk-STARK proofs of arbitrary programs. Initially, I didn't really= have a > > > > > clear end target application, it was mainly a technical challenge= to force > > > > > me to learn a bit more about the RISC-V platform, and also the ho= st/guest > > > > > architecture of risc0. Fast forward ~9 months later, and an initi= al killer > > > > > use case popped into my mind: a zk-STARK proof that a Taproot out= put public > > > > > key was generated using BIP-32, via a given BIP-86 derivation pat= h. > > > > >=20 > > > > > More formally: > > > > > ```math > > > > > \mathcal{R} =3D \left\lbrace\; > > > > > (\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{s,\, \mathb= f{p}}_{\textsf{witness}}) > > > > > \;\middle|\; > > > > > \begin{aligned} > > > > > K &=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,\, \math= bf{p})\bigr) \\ > > > > > C &=3D \textsf{SHA256}\bigl(\texttt{"bip32-pq-zkp:path:v1"} \;\|\= ; \mathbf{p}\bigr) > > > > > \end{aligned} > > > > > \;\right\rbrace > > > > > ``` > > > > >=20 > > > > > where $K$ is the Taproot output key, $C$ is the path commitment, = $s$ is the > > > > > BIP-32 seed, and $\mathbf{p}$ is the derivation path. > > > > >=20 > > > > >=20 > > > > > I was able to get everything working e2e over the weekend, after = making > > > > > some tweaks to my initial architectural game plan! > > > > >=20 > > > > > The TL;DR is that: > > > > >=20 > > > > > * Given that the Taproot commitment scheme is post-quantum secure= [3], in > > > > > the future we can deploy a soft fork to _disable_ the keyspend pa= th, > > > > > and force all Taproot spends to instead flow through the script p= ath > > > > > (not my idea, commonly discussed amongst developers, not sure who > > > > > proposed it first). At that point, Taproot starts to resemble BIP= -360. > > > > >=20 > > > > > * That works for script path spends, but then leaves all the BIP-= 86 > > > > > wallets in a bad position, as they generated outputs that provabl= y > > > > > don't commit to a script path at all. > > > > >=20 > > > > > * A 2023 paper (Protecting Quantum Procrastinators with Signature > > > > > Lifting: A Case Study in Cryptocurrencies [4]) proposed a solutio= n 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 se= cret > > > > > information a quantum attacker wouldn't be able to easily obtain. > > > > >=20 > > > > > * The downside of that is that it reveals the secret BIP 32 seed, > > > > > exposing other non migrated UTXOs of a user. > > > > >=20 > > > > > * With this project I've cobbled together a series of 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. > > > > >=20 > > > > > * In the future a variant of this scheme can be used to enable wa= llets > > > > > that generated the private keys via BIP-86, to have a post quantu= m safe > > > > > exit path in case they don't bother moving their coins in time to= the > > > > > yet-to-be-decided post quantum signature scheme. > > > > >=20 > > > > > To achieve this end, I needed to create/fork a series of repos: > > > > >=20 > > > > > * tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm > > > > > * A fork of TinyGo that supports the flavor of RISC-V (rv32im) th= at > > > > > risc0 requires to generate/execute a guest program to later be pr= oved > > > > > by the host. > > > > >=20 > > > > > * 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 i= s > > > > > unmodified other than that. Recent updates to the repo made the > > > > > entire process much easier (Go guest+host), more on that later. > > > > >=20 > > > > > * go-zkvm: https://github.com/Roasbeef/go-zkvm > > > > > * Go utilities to take a RISC-V ELf binary produced by tinygo-zkv= m, 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 execu= tion > > > > > environment. > > > > >=20 > > > > > * This also includes a Go host package, which loads the guest pro= gram, > > > > > executes it, and generates a trace to later be proved. This is > > > > > achieved via a C FFI compat layer between Go and the original Rus= t > > > > > host/proving/verification code. > > > > >=20 > > > > > * bip-32-pq-zkp: https://github.com/Roasbeef/bip32-pq-zkp > > > > > * The project that packages everything together, this contains th= e: > > > > > * Guest Go program that defines the secret witness and > > > > > claim/constraints of the proof. > > > > >=20 > > > > > * The C FFI wrapper around the OG Rust host, which is used to loa= d > > > > > the guest program, execute it, generate a trace, then finally > > > > > generate a proof. > > > > >=20 > > > > > Details of the final proof as generated on my Mac Book (Apple Sil= icon M4 > > > > > Max, 128 GB of RAM): > > > > > * Takes ~55 seconds or so to generate+proof, including execution.= This > > > > > uses Metal for GPU acceleration on the platform. > > > > > * Uses ~12 GB of ram. > > > > > * Final proof size is ~1.7 MB. > > > > > * Verification takes ~1.8 seconds, and uses ~32 MB of memory. > > > > >=20 > > > > > On several layers, this demo is far from optimized (more on that = later), > > > > > this is meant to serve as a PoC to demonstrate that with the late= st > > > > > software+hardware, a proof of this complexity is well within reac= h. > > > > >=20 > > > > > For those curious re the e2e details I've generated this tutorial= that > > > > > explains the entire system top to bottom: > > > > > https://github.com/Roasbeef/go-zkvm/blob/main/docs/tutorial.md. > > > > >=20 > > > > > If you got to this point in this mail, and don't care about the l= ower 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 Univer= se: > > > > > Monitoring the Situation and/or slopfotainment! =F0=9F=AB=A1 > > > > >=20 > > > > > ## Motivation + Background > > > > >=20 > > > > > As commonly known, in the case of an adversary that possesses a q= uantum > > > > > computer capable of breaking classical asymmetric cryptography, a= ny coins > > > > > stored in UTXOs with a known public key are vulnerable. This is t= he case > > > > > for any P2PK outputs from waaaay back, and also any other outputs= that have > > > > > revealed their public key. Pubkey reveal might happen due to addr= ess re-use > > > > > (spending from the same script twice), or Taproot outputs, which = publish > > > > > the public key plainly in the pkScript. > > > > >=20 > > > > > As detailed in [3], for Taproot outputs, a widely circulated plan= is > > > > > roughly to: disable the _keyspend_ path (requires a simple signat= ure), > > > > > enforcing a new rule that all Taproot spends must then flow throu= gh the > > > > > script path. Spending via the script path requires an opening of = the > > > > > Taproot commitment (C =3D I + H(I || H(M))), which was shown to b= e binding even > > > > > under classic assumptions, as H(M) (tapscript merkle root) is sti= ll a > > > > > collision-resistant function. > > > > >=20 > > > > > That means any UTXO that _does_ commit to a script path has a fut= ure escape > > > > > hatch _if_ such a softfork would need to be deployed in the futur= e. > > > > > However, what about all the other wallets that use BIP 86, and do= n't commit > > > > > to a script path at all? Under a strict version of this existing > > > > > proposal, those wallets would basically be locked forever. > > > > >=20 > > > > > The goal of this work is to demonstrate a practical solution (dis= cussed > > > > > against devs, but never implemented AFAICT): generate a zk proof = that an > > > > > output was generated using BIP-86. For the zk-Proof, we select zk= -STARKs, > > > > > as they're plausibly post quantum since they rely only on symmetr= ic > > > > > cryptography: layers of merkle trees over an execution trace, alo= ng with > > > > > some novel sampling/error-correction algorithms. > > > > >=20 > > > > > At this point, you may be asking: "if the quantum adversary can d= erive the > > > > > private key to a random taproot public key, then how exactly does= this > > > > > help?". The answer lies in the structure of BIP-32! BIP-32 takes = an initial > > > > > 128-512-bit seed (with BIP-39, either 12 or 24 words), then runs = it through > > > > > HMAC-SHA512 keyed by "Bitcoin seed" to produce the master extende= d private > > > > > key. An adversary who wants to forge this proof needs to find a _= colliding_ > > > > > seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s= ') produces > > > > > the same master key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) = is the > > > > > best known quantum collision finder, and it runs in time proporti= onal to the > > > > > cube root of the output space: 2^(n/3). For HMAC-SHA512's 512-bit= output, > > > > > that's ~2^171 quantum operations, well above even NIST's highest > > > > > post-quantum security category. Therefore, if you generated a wal= let using > > > > > BIP-32, you possess _another_ secret that a quantum adversary can= 't > > > > > efficiently reconstruct! > > > > >=20 > > > > > This demo focuses on the Taproot case, but the rough approach als= o applies > > > > > to any other output generated via BIP-32. BIP 32 was originally p= ublished in > > > > > 2012, over 14 years ago. So safe to say that _most_ wallets were = generated > > > > > under this scheme. However, Bitcoin Core only officially adopted = BIP-32 in > > > > > 2016/2018, moving away from their existing key pool structure. I = can't say > > > > > how much BTC is held today in outputs generated with Bitcoin Core= 's original > > > > > key pool, but if you have coins generated via that mechanism, you= may want > > > > > to consider migrating them to a BIP-32 wallet. > > > > >=20 > > > > > ## TinyGo + RISC-V + risc0 > > > > >=20 > > > > > Now for some of the lower level details. risc0 is a STARK based p= roving > > > > > system that takes a RISC-V ELF binary generated by a guest progra= m (any > > > > > program generating using their flavor of rv32im can be proved), e= xecutes > > > > > that in a host environment, generates a trace, then produces a ST= ARK proof > > > > > from that. > > > > >=20 > > > > > Today you can take some subset of Rust, compile it to an ELF usin= g their > > > > > toolchain, then execute it, generate a trace, to finally prove+ve= rify it > > > > > using their system. > > > > >=20 > > > > > This demo took a bit of a round about journey to achieve this, as= after > > > > > all, the journey is most of the fun, ain't it! > > > > >=20 > > > > > For the past 10 years or so, my Bitcoin stack of choice (lnd/btcs= uite) 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. > > > > >=20 > > > > > TinyGo is a special Go compiler based on LLVM, that targets mostl= y 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). > > > > >=20 > > > > > TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V th= at risc0 > > > > > relies on. So the first step here was to create a new target defi= nition for > > > > > TinyGo: riscv32-unknown-none, which uses base integer + multiply/= divide > > > > > instructions with no compressed instructions, which uses 4 KB sta= cks for > > > > > each task. From there, I created a new linker script > > > > > (`targets/riscv32im-risc0-zkvm-elf.ld`) which created a memory la= yer > > > > > identical to what risc0 expects. The final component was a new ru= ntime > > > > > (`src/runtime/runtime_zkvm.go`), which implemented a few platform= specific > > > > > syscalls for risc0 (putchar(), exit(), ticks(), and growHeap()). > > > > >=20 > > > > > When I tried to get this working last year, I had to also impleme= nt a number > > > > > of kernel syscalls (called ecalls in the platform [7]) to handle:= read+write > > > > > to stdin/stdout, halting, and the journaling mechanism (the trans= cript of > > > > > execution committed to), which basically implement the kernel tha= t the guest > > > > > executes in. Fast forward to 2026, and after pulling the latest v= ersion of > > > > > the repo, I realized that they now make a libzkvm_platform.a, whi= ch packages > > > > > up the kernel nicely to be linked against. So I threw out my cust= om kernel > > > > > code, and slotted that in instead. > > > > >=20 > > > > > 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 ex= ecutes the > > > > > program and generates the final proof). > > > > >=20 > > > > > ## BIP-32+Taproot zk-STARK Proof > > > > >=20 > > > > > With basic proofs working (like the classic: I know the factoriza= tion of a > > > > > number `n`), I was unblocked to generate the actual proof. The cl= aim/proof > > > > > is represented with the following JSON artifact: > > > > > ``` > > > > > { > > > > > "schema_version": 1, > > > > > "image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077= cbe70907a690", > > > > > "claim_version": 1, > > > > > "claim_flags": 1, > > > > > "require_bip86": true, > > > > > "taproot_output_key": "00324bf6fa47a8d70cb5519957dd54a02b385c0ead= 8e4f92f9f07f992b288ee6", > > > > > "path_commitment": "4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea7= 9ee4afaab56de11f74b", > > > > > "journal_hex": "010000000100000000324bf6fa47a8d70cb5519957dd54a02= b385c0ead8e4f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea= 79ee4afaab56de11f74b", > > > > > "journal_size_bytes": 72, > > > > > "proof_seal_bytes": 1797880, > > > > > "receipt_encoding": "borsh" > > > > > } > > > > > ```` > > > > >=20 > > > > > The `image_id` is basically a hash of the ELF, so you know what t= he prover > > > > > executed. There are then a few flags that control the claim versi= on and > > > > > whether BIP-86 derivation is a part of the proof. BIP-86 was only= adopted > > > > > post-Taproot, so if you have an existing BIP-44 path, you can ins= tead opt to > > > > > claim that instead. The Taproot key we're generating the proof ag= ainst is > > > > > also part of the _public data_, as it sits plainly on the chain f= or all to > > > > > see. We then also include a `path_commitment`, which is a commitm= ent to the > > > > > exact BIP 86 path that the prover used. Finally, we also commit t= o the > > > > > journal hex, which is basically a commitment to the public claim. > > > > >=20 > > > > > Assuming you've built the project, then you can generate the proo= f (even > > > > > passing in an arbitrary BIP-32 seed and derivation path with) > > > > > ``` > > > > > make prove GO_GOROOT=3D/path/to/go1.24.4 > > > > > ``` > > > > >=20 > > > > > Then verify it with: > > > > > ``` > > > > > make verify GO_GOROOT=3D/path/to/go1.24.4 > > > > > ``` > > > > >=20 > > > > > The default prove target writes: > > > > > * ./artifacts/bip32-test-vector.receipt > > > > > * ./artifacts/bip32-test-vector.claim.json > > > > >=20 > > > > > The receipt is the STARK proof artifact. claim.json is the stable= , > > > > > human-readable description of the public statement being proved. > > > > >=20 > > > > > ## Application to a Future Keyspend Disabling Soft fork > > > > >=20 > > > > > As mentioned above, assuming the community is forced to deploy a = keyspend > > > > > disabling soft fork in the future, we can also deploy some varian= t of > > > > > this proof to enable both BIP-86 wallets, and also any BIP-32 wal= let, to > > > > > sweep their funds into a new PQ output. > > > > >=20 > > > > > In 2026, we've shown that this is achievable using 2 year old con= sumer > > > > > hardware. I don't doubt that the upcoming advancements (eg: photo= nics, new > > > > > flavor of high bandwidth memory, etc) in hardware (driven by the = fierce AI > > > > > race) will make such a proof even more feasible. > > > > >=20 > > > > > One thing to note is that this proof has a few layers of indirect= ion, > > > > > mainly the RISC-V layer that adds overhead which increase the tot= al amount > > > > > of steps, and therefore the size of the proof. A production grade > > > > > deployment would likely instead hand roll a custom STARK proof fo= r this > > > > > exact statement, to achieve a faster and smaller proof). > > > > >=20 > > > > > # Future Work > > > > >=20 > > > > > In terms of future work, there're a number of interesting followi= ng up > > > > > projects that can be pursued from here. > > > > >=20 > > > > > One basic one is that the current proof doesn't actually commit t= o a > > > > > spending txid and/or sighash. That can be trivially incorporated = into the > > > > > proof. Going a step further, the execution of the guest program c= an even > > > > > _generate_ a valid schnorr signature to permit spending. > > > > >=20 > > > > > Looking to the memory+computational requirements necessary to gen= erate the > > > > > proof, I've left two low hanging fruits: > > > > >=20 > > > > > 1. First, we can speed up the Elliptic Curve operations the proof= requires > > > > > (scalar base mult, then addition, or more performantly Double Sca= lar > > > > > 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 k= ernel > > > > > to use an optimized/accelerated circuit for the modular arithmeti= c, > > > > > reducing cycles, steps, and thus proof size. > > > > >=20 > > > > > 2. Second right now, the entire claim is a single proof. Instead,= we can > > > > > first break that up using their recursive proof/composition sysca= lls: > > > > > 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. > > > > >=20 > > > > > -- Laolu > > > > >=20 > > > > > [1]: https://tinygo.org/ > > > > >=20 > > > > > [2]: https://risczero.com/ > > > > >=20 > > > > > [3]: https://eprint.iacr.org/2025/1307 > > > > >=20 > > > > > [4]: https://eprint.iacr.org/2023/362 > > > > >=20 > > > > > [5]: https://microsoft.github.io/Picnic/ > > > > >=20 > > > > > [6]: https://en.wikipedia.org/wiki/BHT_algorithm > > > > >=20 > > > > > [7]: https://github.com/Roasbeef/go-zkvm/blob/main/docs/ecall-ref= erence.md > > > > >=20 > > > > > -- > > > > > You received this message because you are subscribed to the Googl= e Groups "Bitcoin Development Mailing List" group. > > > > > To unsubscribe from this group and stop receiving emails from it,= send an email to bitcoindev+unsubscribe@googlegroups.com. > > > > > To view this discussion visit https://groups.google.com/d/msgid/b= itcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TVwUf_AYcd_qQ%40mail.gmai= l.com. > > > >=20 > > > > -- > > > > You received this message because you are subscribed to the Google = Groups "Bitcoin Development Mailing List" group. > > > > To unsubscribe from this group and stop receiving emails from it, s= end an email to bitcoindev+unsubscribe@googlegroups.com. > > > > To view this discussion visit https://groups.google.com/d/msgid/bit= coindev/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCn= EFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNEYg%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= email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/CAO3Pvs9tps%3DbsMQyA%2BHvhK-u%2BXqRwWtjTq8WXZi%2BcveAVwPi9A%40mail.gmail.= com. --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= CkPcHkjNkIGvlPHuD5JGQJNLKp09px52qracp24h3tdJFiKpd_gMzUEp5vl-p-88B1WCmn2j2XN= 8XxLp3v-YwRlG1CclK8jiLB5MLEV6Fls%3D%40proton.me. -----------------------f115dbdf5cca6640c154bf4a380c8d97 Content-Type: multipart/related;boundary=---------------------648012c67768951df0e27ebd0d4e6d96 -----------------------648012c67768951df0e27ebd0d4e6d96 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Ah! Amazing work! 2 seconds t= o prove is really crazy. Proving a single SHA256 and one modular addition o= n my CPU back in the day took like 20 seconds. Your GPU is coming in clutch for t= his. I best RISC0 has also improved quite a bit since then.
I think the next optimization step would be pre-seeding t= he two SHA512 midstates from the host, so you only need to prove two SHA512= compression calls instead of four. Intuitively I expect this would at best= halve your prover time from 2sec, to probably a little over 1sec, and your= verifier time will probably drop as well since that also seems to scale wi= th circuit complexity. 

<= div style=3D"scrollbar-width:thin;scrollbar-color:rgba(0, 0, 0, 0.35) rgba(= 0, 0, 0, 0)">I think I have= two half-decent arguments now as to why this won't affect security: <= /span>

First, even if a fraudulent prover is handed the correct midstat= es to use, the p= rover would still have to do the hard work of finding the parent secret key= needed as a witness. This is at least the same difficulty as finding the p= arent sk=E2=80=8B=E2=80=8B if we just hashed it without a chaincode at all, usin= g two bare SHA512 calls - the only thing that changes is the midstate, and = the SHA512 input length suffix. Starting from a different midstate doe= sn't magically give the attacker a head-start in a 256-bit search space loo= king for sk=E2=80=8B. A frauduent prover would know the = child secret key k =3D sk + int(I[32:]) % n=E2= =80=8B=E2=80= =8B, but they don't know int(I[32:]) or sk=E2=80=8B so they cannot solve for= either.

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

Secondly, here's another argument as to why finding the midstate= s in the first place should also be hard. 
<= span style=3D"font-family: Arial, sans-serif;">
Any adversary who could= solve this problem by finding the right midstates could be used as an orac= le to prove the existence of partial 2-cycles in SHA512. 
=

  • Given a SHA51= 2 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<= span style=3D"font-family: Arial, sans-serif;"> k= =E2=80=8B=E2=80= =8B to find correct midstates such that 

I =3D=3D SHA512(<something> || SHA512(<something&g= t; || 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 condi= tions to hold, the proof forger must be able to find not just the correct m= idstates, but also midstates which give a 2-stage partial hash cycle so tha= t:

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

This= seems unlikely or at least very difficult.

<= /span>
<= font face=3D"Arial, sans-serif" style=3D"scrollbar-width:thin;scrollbar-col= or:rgba(0, 0, 0, 0.35) rgba(0, 0, 0, 0)">regards,
conduition
On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun <lao= lu32@gmail.com> wrote:
Hi Condution,

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

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

* Hardened xpriv
image I= D:
8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0df084= 9
composite:
seal 234568
prove 1.98s
veri= fy 0.02s
peak RSS 3144171520
succinct:
seal 222668=
prove 2.84s
verify 0.02s
peak RSS 3145990144
So we can see that the succinct proof sizes are all about the same. Ho= wever the
xpriv variant can be proved directly in just 2 seconds on my m= achine! It also
requires just 3 GB of memory for the proof as well.
<= br>I've created some additional supporting documentation to detail exactly = what
the new proofs do and their results:

* https://github.com/Roasbee= f/bip32-pq-zkp/blob/main/docs/reduced-variants.md

* https://github.com/Roasbeef/bip32-pq-zkp/blob/1c= 89fdb398180a2b3eff7761b7f4b233d455c6c9/README.md#reduced-proof-variants=

* https://github.com/Roa= sbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a5171f5e06fa840/docs/claim= .md#reduced-variant-claims


Once again, thanks for the great = ideas! I wonder if we can improve on this
round of proof golf further be= fore 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 <laolu32@gmail.com&= gt; wrote:
Hi Conduition,

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

> I'm amending my prior su= ggestion slightly: The circuit (guest program)
> could take in an xpr= iv (e.g. at m/86'/0') and output a child xpriv
> (e.g. at m/86'/0'/0'= ) to the journal (instead of outputting a child
> xpub).

That= 's an excellent insight!

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

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

I'll try to hack this up, and then run a head to head = comparison to see this
simpler statement actually results in a smaller p= roof then the final
succinct receipt of either of the proof variants. Ba= sed on my current
intuition w.r.t the lower level details, I think the f= inal 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 potent= ial 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 loo= k at
hand rolling a custom AIR to avoid the overhead that the RISC-V emu= lation
adds to the rirsc0 proof chain, given that it entirely skips doin= g any EC
operations at all for the final statement.

----

R= e the commit/reveal approach, to be honest I'm not fully caught up on that<= br>proposal. That original thread got pretty long, so I dropped of after a<= br>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 com= parisons!

-- Laolu


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

We don't eve= n need to do point multiplication in the circuit at all.

I'm amending my prior suggestion sl= ightly: 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/8= 6'/0'/0'=E2=80=8B) to the journal (instead of outputting a child = xpub).

This = is safe because remember, EC spending has been disabled in this context, an= d 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 anythin= g they can't already do with the equivalent xpub.

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

Designing the guest program like this will massiv= ely reduce your circuit complexity, because EC point multiplication is w= ayyyyy 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 SHA= 256 hash and an EC point multiplication. I found that pruning EC point arit= hmetic from my guest program improved prover runtime by a factor of over 10= 0x.

If I am not f= ever-dreaming and this is indeed possible, then the new circuit's complexit= y will be dominated not by point multiplication, but by the HMAC-SHA512 cal= l. Our new task is then to figure out how much we can internally optimize t= he HMAC-SHA512 call for STARK proving. Here's a few ideas.

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

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

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

Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80= =8B block size, we need a total of 4 SHA512 compression calls:
  1. to compress (K=E2=8A=950x36)=E2=80=8B
  2. to compress the msg= =E2=80=8B (and SHA512 padding/length)
  3. to compress (K=E2=8A=950x5c), and
  4. a final compression call to tie it all together.
The output of that = last compression call is partitioned into the child chaincode, and a key de= lta which is added to the parent secret key (modulo the curve order), producing t= he child EC secret key. This last step is arithmetically simple; the SHA512= calls are where most of the arithmetic complexity lies.

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

Note how the parent secret key is the most important = piece for soundness. The circuit needs to prove the parent secret key exist= ed in the hash function preimage, and is correctly related to the child sec= ret key via modular addition. So compression call (2) seems unavoidable. Th= e others are less rigid.

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

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(<somet= hing> || 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 on= e-block long, it seems easy to 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. The tradeoff is that= this permits malicious provers the flexibility of choosing their starting = midstates (though hash input length can be fixed at 192 bytes). I'm not ent= irely sure if this meaningfully weakens the verifier's soundness. Ethan Hei= lman might have opinions on this, he knows a lot more about attacking hash = functions than I do. Intuitively, I doubt sampling random SHA512 midstates = is that much better than sampling a random HMAC key (chaincode) K=E2=80=8B and computing the resulting midstates.

Th= is reduces our circuit to, i think, the minimum acceptable security floor f= or provers: two SHA512 compression calls, which commit to a parent secret k= ey.


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

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

It seems to me the circuit (guest pro= gram) could be simplified. Notice how the guest code computes the entire HD wallet key path, includi= ng hardened and non-hardened derivation st= eps, 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 STARK to = prove, and could be safely removed to reduce proof size and improve perform= ance.

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

Example. If i have a wallet = with a taproot address at m/86'/0'/0'/1/2=E2=80= =8B, I could prove I know the xpriv at m/86'/0'= =E2=80=8B which derives the xpub at m/86'/0'/0'= =E2=80=8B. Then I provide the remaining key path elements /1/2= =E2=80=8B in the witness. Note, i do not mean we der= ive the xpriv at m/86'/0'=E2=80=8B inside the= guest program. I mean the prover derives m/86'/0'=E2=80=8B first (in the host), and then writes that xpriv = into the guest program's inputs. The guest program derives and outputs = the xpub at m/86'/0'/0'=E2=80=8B. The verifier ma= y check the STARK output (xpub) is correctly computed, then use the given k= ey-path to manually derive the taproot address from the xpub themselves, ou= tside the circuit, and validate that address against th= e UTXO i'm spending. The verifier thus has confirmed the prover knew an xpr= iv which (through a hardened derivation step) derives the correct taproot o= utput key.

This change significantly reduces the s= ize of the circuit. From a glance, I see the original guest program perform= s 6 HMAC-SHA512 calls (1 for the master key, 5 for the BIP32 derivation ste= ps), two SHA256 compression calls (for the taptweak hash), and two point mu= ltiplications. With this simplified variant, we are invoking only a single = HMAC-SHA512 call and a single point multiplication. I can't say for sure, b= ut I expect this will improve your proof size and runtime significantly.

This change also makes the circuit more generally ap= plicable to other rescue contexts. For instance, it could be applied to BIP= 340 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 publishing= xpubs? Remember that we are assuming regular EC spending is locked in this= context, so it is safe-ish to share account xpubs with quantum attackers. = At best the xpub can be used for surveillance but not forgery. If on= e would prefer not to share the account-level xpub on-chain for privacy rea= sons, the proof could be extended to also derive the unhardened child xpub = at /1/2=E2=80=8B insi= de the guest program (but we still do not need to do the taproot key tweaki= ng in the guest program).

We should als= o talk scaling efficiency. Given the cost of STARKs, this style of proof sh= ould be able to authorize spends for more than one UTXO. Say you have a wal= let with 10 different UTXOs held by distinct addresses in the same BIP44 ac= count. One single STARK proof could authorize spending all 10 of them, by s= imply committing all 10 input signature hashes into the journal, and labeli= ng the inp= uts with t= he = corresponding 10 BIP32 key paths somehow. The verifier would = need to check the proof only once and not 10 times. The 10 UTXO spends coul= d be validated using the common xpub from the STARK proof's journal.
<= div>
For a slightly related work proving a similar relation f= or 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 d= iscussed this on the list a while back. That said, commit/reveal requir= es more careful design 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 some people? IDK. What do you think of commit/reveal compar= ed to STARKs for this purpose?

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## Motivation + Background

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

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

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

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

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

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

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

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

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

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

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

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

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

## BIP-32+Taproot zk-STARK Proof

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

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

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

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

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

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

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

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

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

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

# Future Work

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

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

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

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

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

-- Laolu

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

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

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

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

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

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

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

--
You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googl= egroups.com.
To view this discussion visit https://grou= ps.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TV= wUf_AYcd_qQ%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googl= egroups.com.
To view this discussion visit https://groups.google.com/d/msgid/b= itcoindev/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxL= CnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9XEXNEYg%3D%40proton.me.

--
You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https:= //groups.google.com/d/msgid/bitcoindev/CAO3Pvs9tps%3DbsMQyA%2BHvhK-u%2BXqRw= WtjTq8WXZi%2BcveAVwPi9A%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CkPcHk= jNkIGvlPHuD5JGQJNLKp09px52qracp24h3tdJFiKpd_gMzUEp5vl-p-88B1WCmn2j2XN8XxLp3= v-YwRlG1CclK8jiLB5MLEV6Fls%3D%40proton.me.
-----------------------648012c67768951df0e27ebd0d4e6d96-- -----------------------f115dbdf5cca6640c154bf4a380c8d97-- -----------------------73cbe1bef66504fb597ed057fe711656 Content-Type: application/pgp-keys; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc" LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4ak1FWkRub0tSWUpLd1lCQkFI YVJ3OEJBUWRBcnBZYWFjZDgwcXdocmNaQW9VbW9NSHNWS21iZWlPZUEKcFhXbk1ybFdPZkxOSzJO dmJtUjFhWFJwYjI1QWNISnZkRzl1TG0xbElEeGpiMjVrZFdsMGFXOXVRSEJ5CmIzUnZiaTV0WlQ3 Q2pBUVFGZ29BUGdXQ1pEbm9LUVFMQ1FjSUNaQjRLV3p0aFBhenhRTVZDQW9FRmdBQwpBUUlaQVFL YkF3SWVBUlloQkVkSWthMENNdHJMZGcxM2EzZ3BiTzJFOXJQRkFBQTZhQUVBM1RmNHdqSVoKYnox K0diS0h4K09WQytNUXlVdi84RStoWUpjTE5QZnA0NEFBLzNiak5OTXN4WHdJTGZEM0xManNVVWFo CitBV2JyblVjVUFqQ2R1d3hUT01LempnRVpEbm9LUklLS3dZQkJBR1hWUUVGQVFFSFFDSXYxZW5J MU5MbAo3Zm55RzlVWk1wQ3ZsdG5vc0JrTmhQUVZxT3BXL3RKSkF3RUlCOEo0QkJnV0NBQXFCWUpr T2VncENaQjQKS1d6dGhQYXp4UUtiREJZaEJFZElrYTBDTXRyTGRnMTNhM2dwYk8yRTlyUEZBQUFR TFFEL2NCR2kwUDdwCkZTTkl2N1B6OVpkeUNVQjhzTy90dWZkV3NjQkNZK2ZMYTV3QkFNK0hTL3Jp S014RGt0TkhLakRGc2EvUgpEVDFxUGNBYXZCaXc2dDZ4Ti9jRgo9Y3d5eAotLS0tLUVORCBQR1Ag UFVCTElDIEtFWSBCTE9DSy0tLS0tCg== -----------------------73cbe1bef66504fb597ed057fe711656-- --------be331b9834f7a8b1f7b49b5e049164d91e760486cb8da8ba624e0199799dd32b Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmnZJS4JEHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmeYrJqCgTGWmT7QHUR/REh3w1moVGl9DYH7m7eB 7niGdxYhBEdIka0CMtrLdg13a3gpbO2E9rPFAAA1hQEAhUuJ5JTu+EGqaPOF ShPwuIj6+o4y1up720xMmUZcx4QA/RbXBid6Ta+EuZd1il0O5b7I1XwudXuC ArjFwGJGINYJ =FLmv -----END PGP SIGNATURE----- --------be331b9834f7a8b1f7b49b5e049164d91e760486cb8da8ba624e0199799dd32b--