From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 08 Apr 2026 13:30:57 -0700 Received: from mail-oa1-f62.google.com ([209.85.160.62]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wAZY5-0005VS-NE for bitcoindev@gnusha.org; Wed, 08 Apr 2026 13:30:56 -0700 Received: by mail-oa1-f62.google.com with SMTP id 586e51a60fabf-4236c3b8f32sf589050fac.0 for ; Wed, 08 Apr 2026 13:30:52 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1775680246; cv=pass; d=google.com; s=arc-20240605; b=lEx4aUfW8tbE2vLHvigEt1JQ/mzZxuMSh5ZGfFqhrcXUTspJHWlMy0LDj8IeZsrd5I yB5J07jzytH0nqopdq+T6WMwJhq5uZUeUcGLIYFxTkhFSK8CKt+BYs/xCC6Inow8Mhcg L75M8LsS3z3VNxMv0Hkh8QlxTm/IoYVzCd1p0FCfsH44E7Ln6w+0doCn+3TBTURUsCu1 sbavd0ANjQcCTvvyAYis//S72PR4jPCm57t93BI7Qqifn+jomI3VroRIFBIM69CbHFhf nnd7m09Bw3sc0NRKMwXY03cXJLGieBpW1oNWmRGdvglUfjc3YabXKXnzzWxCJlLKsR7x ichQ== 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=1oInKWbucmD+o0NJlQrLDXjbmHmly/lrK8FCJSmDlgU=; fh=iKt9d7/mRJ46mRXfv7/ou18JFhPYdTLNnBDn6PYmk74=; b=AhNGHQZSFiFPdYq4IPqmyO5rawRcfQ0VBbbHjU2PKOqDJEF8A3Y18Omg0MwzVPGjUc 381G+zMVDSVbHuRINJO4DOAWj9KoRNTPa39RWD2CWnMCRyBAQk+y/5iv2SGbgSwcgz8K ckuPahJQ1nRnwsb1o4o10hpStFgJueNLEYgWPxrjsuOcz/hnpke+S2UhPupegWQ11xlA /XTuWw4VLqeFD0N3wELHd4wqmegItN8miVzYNtuDGOuQTR+UXVyQikwHFVBlHsg4YH9W Cbzl150TxeAAOVUCS4TtPKJmcnKWleTeEsjWv6UQ6f4I7yEfDCte4UgQ7CuwPmB62Kun JBDA==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=WoJFeG1i; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.30 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=1775680246; x=1776285046; 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=1oInKWbucmD+o0NJlQrLDXjbmHmly/lrK8FCJSmDlgU=; b=PgObAcSFIE/tjwc8rqKmoa0L1m8r7Lzpdx6wnUe/SVlUD9leunV2nfiLzRe2cPC4u/ KKPdpit4qojYl7DCe8s/Y3EHzkDd76rYOZ11kETQ/x/WgYg1phwjdALd1vYy8I08QgGT 5c38NUv6hqv9lXaYa48hZUJyTHY4Bh9uLcY9055AoBrod6d0dXU3p8/qJ1vW2Ns3tJ+8 yBr/meLG7wjh/Eyj6Deg9U5FdH8m3OYKa6+FxUHtYnY1Vm1Iei3CSJch9KL4Zr9UPtU9 TWv3w984k8lbmEdx7DGAprIQjVEFIZqilkwC9FBVaYmvwA3ymSeNOekqWlSaTgaKXg4E +K6w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1775680246; x=1776285046; 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=1oInKWbucmD+o0NJlQrLDXjbmHmly/lrK8FCJSmDlgU=; b=NH4KMIBZEBcd8rSBMNPpi1Dl0ThnLGWg3fFgntKIIxKvZQ/r5VKrETRT1L29MTjAfd ay59ytj/rNYrWvqdLo8f44mKHUxcbosL/vR73/VbJqhKss+QWYn2o3H6ZHKGGXg3HHRa NwykNDONy5Bh9DWAhM2f1TjlAChq/WU0KwE5pD/RTlBfzB7Ssv+ESZy9tIO5EMmCsQLn 6su6oWBgzZ2ZlJOpj555NsYbHeee9WTj2dw7Cr+o9qMYpIluPZcqmAvDO9ZWFq79A3bm XqdkIdURTvXJY2+en6TFj/bnvxxhbY1+PzmPC1LL/IINsRh571qi3BGmKOBPNLmZeRLY qqjA== X-Forwarded-Encrypted: i=2; AJvYcCXWOuAg65oA6BDX/iHkfCQ+dP8qZqV0YyxVqyMALXwfdCNl7D2s+0z7mXc9pwxr/Ni8LtVBdIzdXHGp@gnusha.org X-Gm-Message-State: AOJu0Yx2HF4/XImxK/7bcapaErXgYEQ6EyH8+Z6n4r8IPr4qB4lScm8H 6pckcUeulP5KCkYpTVAgIhAQ74mx6QovwdtFxzlo6LWGr14PQuSKR/sn X-Received: by 2002:a05:6870:241e:b0:41c:43bb:7f25 with SMTP id 586e51a60fabf-423bcfffc99mr493772fac.19.1775680245973; Wed, 08 Apr 2026 13:30:45 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AYAyTiKjDgP5EofPJx4Rb2Q5/IIhH4OGbB7Y03LVQ7K4b8CEiA==" Received: by 2002:a05:6871:f:b0:41c:6a62:2ef1 with SMTP id 586e51a60fabf-4239ef7daf3ls315998fac.2.-pod-prod-00-us-canary; Wed, 08 Apr 2026 13:30:41 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCU4FD6n7APZ3eOxYsv8ruYwyjhxWkx7EIDAGg/Pa+bWJF/66tv+3pSl+ReevFX8USMJu3jYqsQSvjoI@googlegroups.com X-Received: by 2002:a05:6808:150c:b0:45f:103c:2483 with SMTP id 5614622812f47-4772d1addafmr462185b6e.23.1775680240908; Wed, 08 Apr 2026 13:30:40 -0700 (PDT) Received: by 2002:a05:6808:628c:b0:46b:22a1:35fc with SMTP id 5614622812f47-4775d81d877msb6e; Wed, 8 Apr 2026 13:23:09 -0700 (PDT) X-Forwarded-Encrypted: i=2; AJvYcCUp73OKfBd6Q1joHha9RCtOFPbOKXs2axKekQ9IMKyOBZ4Haho+GqEdChJ1SeYNjBATDrE95vI/Iuea@googlegroups.com X-Received: by 2002:a05:6a20:7d9b:b0:39f:bf86:5303 with SMTP id adf61e73a8af0-39fc928ca54mr764984637.8.1775679787974; Wed, 08 Apr 2026 13:23:07 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1775679787; cv=none; d=google.com; s=arc-20240605; b=eZWBk+cY3tvGtB153Pb0rb2Ue/r1PM4Y3NbCoNACySU3RnwGY/D4NdSs91bIAstZUs 5tXKnO5fNeGMdlFwIZQOD/xP6VR2VKEdgSQINjpLQ9fYwEmuqpOLS016Ra4YNfMYamKH dDMPriLXQYD2g816wyoIFiz/k4qlmT/K6lwMPgN8wuLZPO0W71QzWgAUXm8uNDjzN9KG I6yG/YnXq9OAfR03KmXyhQD86Z16PwMLqmIUKP6+XDeX8iTnzEG0H794eV47a9ViieuH 6ED5DnxgQ0rhJ9oNdeoDMUmtIL+Ju/Zd1JKplaVP+fJj8bPTOAuflznzJ6KtKp28u2fL uJKA== 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=+atn7QoF3DAXOXmt+W7BO1DTNGISX9nEiZunIOcZyqI=; fh=Pa/dvSGTsQAhN5ZODUKlhpb851p9vHqA0zVhAMfMNak=; b=H2JMfs+vR7zZLyDfJCXxuA3Kw+jx5R0Kgwz1V+GtjzKx57fpNAN8kWKqHT85TlCmgk 0aBdOVa8a1NZq4SJoXthSJU/BF/YL/O+Bje30xwRghvgdB7r5e7vyiX+icAG7nZCSBFI T5Tg/GNqdWl9x4HbU/wqv7dYvhyAUP9iQQPzXhGGEbTQbZi0TF6qbC89D12v78LY/gQg LtttAIx/U2ac6tGhaYeQw7cdoYNtjqtHL8NfkCGWcLmR3TcKqhi1ifgVDQmhAPKrPYn1 RRUMhGLXUz49GZd17WvRSdviBvtwdLsu9IUY2nJX9KjciyBweETfB+zJdDZpcPMnoMXx z6SQ==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@proton.me header.s=protonmail header.b=WoJFeG1i; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.30 as permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me Received: from mail-24430.protonmail.ch (mail-24430.protonmail.ch. [109.224.244.30]) by gmr-mx.google.com with ESMTPS id 41be03b00d2f7-c76dd3f63fasi498088a12.2.2026.04.08.13.23.07 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 08 Apr 2026 13:23:07 -0700 (PDT) Received-SPF: pass (google.com: domain of conduition@proton.me designates 109.224.244.30 as permitted sender) client-ip=109.224.244.30; Date: Wed, 08 Apr 2026 20:23:01 +0000 To: conduition From: "'conduition' via Bitcoin Development Mailing List" Cc: Olaoluwa Osuntokun , 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: 8e6485ea0b9ce390f83561c2b27af4216dfa1908 MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------acd6237011109bbcfa85eb402c7acd2d6a9ddf4638b845ccdd3cfdc5234a57a2"; 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=WoJFeG1i; spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.30 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) --------acd6237011109bbcfa85eb402c7acd2d6a9ddf4638b845ccdd3cfdc5234a57a2 Content-Type: multipart/mixed;boundary=---------------------439b990bca872743655074b3f36d9a69 -----------------------439b990bca872743655074b3f36d9a69 Content-Type: multipart/alternative;boundary=---------------------0b1e3f3e6feedf4e90e708c0ea08f705 -----------------------0b1e3f3e6feedf4e90e708c0ea08f705 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="UTF-8" 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) coul= d take in an xpriv (e.g. at `m/86'/0'`) and output a child xpriv (e.g. at= =C2=A0`m/86'/0'/0'`) to the journal (instead of outputting a child xpub).= =C2=A0 This is safe because remember, EC spending has been disabled in this contex= t, and to a quantum attacker, an xpub is computationally equivalent to its = xpriv. So why bother hiding it? The child xpriv doesn't give an observer an= ything they can't already do with the equivalent xpub.=C2=A0 The guest program then is basically the BIP32 CKDpriv algorithm, restricted= to a single hardened derivation step. The verifier gets the child xpriv, b= ut can't use it to forge new proofs. Honest verifiers use the xpriv to deri= ve the child address(es) as suggested in my last message, to authenticate s= pending. Designing the guest program like this will massively reduce your circuit co= mplexity, because EC point multiplication is wayyyyy harder for the RISC0 c= ompiler to arithmetize than a simple hash function. In my prior work with R= ISC0, I made a guest program which ran a SHA256 hash and an EC point multip= lication. I found that pruning EC point arithmetic from my guest program im= proved prover runtime by a factor of over 100x. If I am not fever-dreaming and this is indeed possible, then the new circui= t's complexity will be dominated not by point multiplication, but by the HM= AC-SHA512 call. Our new task is then to figure out how much we can internal= ly optimize the HMAC-SHA512 call for STARK proving. Here's a few ideas. If you bust open HMAC-SHA512, it looks like this: `HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x36) || msg)= )`=C2=A0 ...where in the context of BIP32 hardened CKD, the HMAC key=C2=A0`K` 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` is the SHA512 block size, we need a total of 4 SHA51= 2 compression calls:=C2=A0 1. to compress `(K=E2=8A=950x36)` 2. to compress the `msg` (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 output of that last compression call is partitioned into the child chai= ncode, 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 arithmet= ically simple; the SHA512 calls are where most of the arithmetic complexity= lies. The question then becomes, which of these compression calls can be done out= side the circuit, and which are truly essential for security?=C2=A0 Note how the parent secret key is the most important=C2=A0piece for soundne= ss. The circuit needs to prove the parent secret key existed in the hash fu= nction preimage, and is correctly related to the child secret key via modul= ar addition. So compression call (2) seems unavoidable. The others are less= rigid. I'd argue that if we really dig into the hard relation we're trying to prov= e here, we can reduce it to this statement: Given a child xpriv with secret key `k`, chaincode `c` and index `i`,=C2=A0= I know a preimage `x` and secret key `sk`=C2=A0such that: ` ` `I <- SHA512( || SHA512( || 0x00 || sk || i)`) `c =3D=3D I[:32]` `k =3D=3D int(I[32:]) + sk % n` Seeing as the `` slots are arbitrary, and we know in BIP32 they = are always exactly one-block long,=C2=A0it seems easy to throw out the comp= ression calls (1) and (3). The host can precompute the relevant SHA512 mids= tates outside the circuit, and pass the midstates into the guest program as= secret inputs.=C2=A0The tradeoff is that this=C2=A0permits malicious prove= rs the flexibility of choosing their starting midstates (though hash input = length can be fixed at 192 bytes). I'm not entirely sure if this meaningful= ly weakens the verifier's soundness. Ethan Heilman might have opinions on t= his, he knows a lot more about attacking hash functions than I do. Intuitiv= ely, I doubt sampling random SHA512 midstates is that much better than samp= ling a random HMAC key (chaincode)=C2=A0`K` and computing the resulting mid= states. 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. regards, conduition On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via Bitcoin Develop= ment Mailing List wrote: > Hi=C2=A0Laolu, > 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 mou= th is, and actually build a prototype. Bravo! >=20 > It seems to me the circuit (guest program) could be simplified. Notice ho= w=C2=A0the guest code computes the entire HD wallet key path, including har= dened=C2=A0and=C2=A0non-hardened derivation steps, and also computes the ta= proot 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 re= moved to reduce proof size and improve performance. >=20 > In reality, you needn't go so far as to prove (1)=C2=A0"I know a BIP39 se= ed which derives this taproot output key". You need only prove this much mo= re general statement (2):=C2=A0"I know a BIP32 xpriv which derives this xpu= b 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, b= ut it entails far less computation to prove and verify. The rest of the ori= ginal statement (1) can be done externally outside the circuit. >=20 > Example. If i have a wallet with a taproot address at=C2=A0`m/86'/0'/0'/1= /2`, I could prove I know the xpriv at=C2=A0`m/86'/0'` which derives the xp= ub at=C2=A0`m/86'/0'/0'`. Then I provide the remaining key path elements /`= 1/2` in the witness. Note, i=C2=A0do not=C2=A0mean we=C2=A0derive=C2=A0the = xpriv at=C2=A0`m/86'/0'` inside the guest program. I mean the prover derive= s=C2=A0`m/86'/0'` first (in the host), and=C2=A0then writes that xpriv into= the guest program's inputs.=C2=A0The guest program derives and outputs the= xpub at=C2=A0`m/86'/0'/0'`.=C2=A0The verifier may check the 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 val= idate=C2=A0that address=C2=A0against the UTXO i'm spending. The verifier th= us has confirmed the prover knew an xpriv which (through a hardened derivat= ion step) derives the correct taproot output key. >=20 > This change significantly reduces the size of the circuit. From a glance,= I see the original guest program performs 6 HMAC-SHA512 calls (1 for the m= aster key, 5 for the BIP32 derivation steps), two SHA256 compression calls = (for the taptweak hash), and two point multiplications. With this simplifie= d variant, we are invoking only a single HMAC-SHA512 call and a single poin= t multiplication. I can't say for sure, but I expect this will improve your= proof size and runtime significantly. >=20 > This change also makes the circuit more generally applicable to other res= cue contexts. For instance, it could be applied to BIP340 xonly keys inside= a taproot script tree, or in a P2(W)SH address to an ECDSA public key, or = to P2(W)PKH addresses. >=20 > Concerned about publishing xpubs? Remember that we are assuming regular E= C spending is locked in this context, so it is safe-ish to share account xp= ubs with quantum attackers. At best the xpub can be used for surveillance b= ut not forgery. If one would prefer not to share the account-level xpub on-= chain for privacy reasons, the proof could be extended to also derive the u= nhardened child xpub at=C2=A0`/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, this st= yle of proof should be able to authorize spends for more than one UTXO. Say= you have a wallet with 10 different UTXOs held by distinct addresses in th= e same BIP44 account. One single STARK proof could authorize spending all 1= 0 of them, by simply committing all 10 input signature hashes into the jour= nal, and labeling the inputs with=C2=A0the=C2=A0corresponding 10 BIP32 key = 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. >=20 > For a slightly related work proving a similar relation for hashed address= es, using different STARK technology stacks,=C2=A0see this delving post. >=20 > However, all this said, my personal preference for long-term procrastinat= or rescue 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= hundred bytes over two transactions, compared to a few million bytes in on= e transaction with STARKs.=C2=A0Boris Nagaev and I discussed this on the li= st 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 commitme= nt in the first place, so perhaps the cost would be worth it to some people= ? IDK. What do you think of commit/reveal compared to STARKs for this purpo= se? >=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 side pro= ject > > 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 gener= ate > > zk-STARK proofs of arbitrary programs. Initially, I didn't really have = a > > clear end target application, it was mainly a technical challenge to fo= rce > > 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 kil= ler > > use case popped into my mind: a zk-STARK proof that a Taproot output pu= blic > > key was generated using BIP-32, via a given BIP-86 derivation path. > >=20 > > More formally: > > ```math > > \mathcal{R} =3D \left\lbrace\; > > (\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrace{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-zkp:path:v1"} \;\|\; \mat= hbf{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 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. > >=20 > > * 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. > >=20 > > * A 2023 paper (Protecting Quantum Procrastinators with Signature > > Lifting: A Case Study in Cryptocurrencies [4]) proposed a solution to t= his, > > 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. > >=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 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. > >=20 > > * 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. > >=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) that > > risc0 requires to generate/execute a guest program to later be proved > > 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 is > > 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-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. > >=20 > > * 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. > >=20 > > * 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. > >=20 > > * 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. > >=20 > > 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. > >=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 latest > > software+hardware, a proof of this complexity is well within reach. > >=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 lower l= evel > > 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 > >=20 > > ## Motivation + Background > >=20 > > 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 = have > > revealed their public key. Pubkey reveal might happen due to address re= -use > > (spending from the same script twice), or Taproot outputs, which publis= h > > 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 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 even > > under classic assumptions, as H(M) (tapscript merkle root) is still a > > collision-resistant function. > >=20 > > That means any UTXO that _does_ commit to a script path has a future es= cape > > 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 co= mmit > > 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 (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. > >=20 > > 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 ini= tial > > 128-512-bit seed (with BIP-39, either 12 or 24 words), then runs it thr= ough > > HMAC-SHA512 keyed by "Bitcoin seed" to produce the master extended priv= ate > > key. An adversary who wants to forge this proof needs to find a _collid= ing_ > > seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s') pro= duces > > 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 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 us= ing > > 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 also appl= ies > > to any other output generated via BIP-32. BIP 32 was originally publish= ed in > > 2012, over 14 years ago. So safe to say that _most_ wallets were genera= ted > > 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 ori= ginal > > key pool, but if you have coins generated via that mechanism, you may w= ant > > 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 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 pr= oof > > from that. > >=20 > > 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. > >=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/btcsuite) = uses > > a series of Go libraries, so I wanted to be able to re-use them, first = for > > this demo, then also in the future for other projects. > >=20 > > TinyGo is a special Go compiler based on LLVM, that targets mostly embe= dded > > 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 that ris= c0 > > relies on. So the first step here was to create a new target definition= for > > TinyGo: riscv32-unknown-none, which uses base integer + multiply/divide > > instructions with no compressed instructions, which uses 4 KB stacks 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 speci= fic > > syscalls for risc0 (putchar(), exit(), ticks(), and growHeap()). > >=20 > > When I tried to get this working last year, I had to also implement a n= umber > > of kernel syscalls (called ecalls in the platform [7]) to handle: read+= write > > to stdin/stdout, halting, and the journaling mechanism (the transcript = of > > execution committed to), which basically 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 pac= kages > > up the kernel nicely to be linked against. So I threw out my custom ker= nel > > 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 executes= 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 factorization o= f a > > number `n`), I was unblocked to generate the actual proof. The claim/pr= oof > > is represented with the following JSON artifact: > > ``` > > { > > "schema_version": 1, > > "image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe709= 07a690", > > "claim_version": 1, > > "claim_flags": 1, > > "require_bip86": true, > > "taproot_output_key": "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92= f9f07f992b288ee6", > > "path_commitment": "4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4af= aab56de11f74b", > > "journal_hex": "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0= ead8e4f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4a= faab56de11f74b", > > "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 the pro= ver > > 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 o= pt 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 the prover used. Finally, we also commit to the > > journal hex, which is basically a commitment to the public claim. > >=20 > > 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 > > ``` > >=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 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. > >=20 > > In 2026, we've shown that this is achievable using 2 year old consumer > > hardware. I don't doubt that the upcoming advancements (eg: photonics, = new > > flavor of high bandwidth memory, etc) in hardware (driven by the fierce= AI > > race) will make such a proof even more feasible. > >=20 > > One thing to note is that this proof has a few layers of indirection, > > mainly the RISC-V layer that adds overhead which increase the total amo= unt > > of steps, and therefore the size of the proof. A production grade > > deployment would likely instead hand roll a custom STARK proof for 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 following up > > projects that can be pursued from here. > >=20 > > 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. > >=20 > > Looking to the memory+computational requirements necessary to generate = the > > proof, I've left two low hanging fruits: > >=20 > > 1. First, we can speed up the Elliptic Curve operations the proof requi= res > > (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. > >=20 > > 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. > >=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-reference= .md > >=20 > > -- > > You received this message because you are subscribed to the Google Grou= ps "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/bitcoin= dev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TVwUf_AYcd_qQ%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= email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit https://groups.google.com/d/msgid/bitcoinde= v/ciibnh-b0x-rLwA8pY5NURBfPvG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcr= RCTM39N2AYEy0Db2H_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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= MIvoK2GkNbJJsK2fXOzHNffNuJGsnNnMpTgQczthUnChXesJMxi249BDV6b5DkIQfvGpBNgDdp5= qATbc1tGsUWPHXraBwaosU4Y_09m5pLY%3D%40proton.me. -----------------------0b1e3f3e6feedf4e90e708c0ea08f705 Content-Type: multipart/related;boundary=---------------------758cb83c097b03072091825438a967a3 -----------------------758cb83c097b03072091825438a967a3 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Oh, I've be= en a fool, a foolish fool.

We don't even need to do point multiplication in the ci= rcuit 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 outp= ut a child xpriv (e.g. at m/86'/0'/0'=E2=80=8B) to= the journal (instead of outputting a child xpub). 

This is safe becau= se remember, EC spending has been disabled in this context, and to a quantu= m attacker, an xpub is computationally equivalent to its xpriv. So why both= er hiding it? The child xpriv doesn't give an observer anything they can't = already do with the equivalent xpub. 

The guest program then is basically the= BIP32 CKDpriv algorithm, restricted to a single hardened derivation step. = The verifier gets the child xpriv, but can't use it to forge new proofs. Ho= nest verifiers use the xpriv to derive the child address(es) as suggested i= n my last message, to authenticate spending.

Designing the guest program like this= will massively reduce your circuit complexity, because EC point multiplica= tion 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 multiplication. I = found that pruning EC point arithmetic from my guest program improved prove= r runtime by a factor of over 100x.

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

If you bust open HMAC-SHA512, it looks like this:
<= div style=3D"font-family: Arial, sans-serif; font-size: 14px;">
HMAC_SH= A512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x= 36) || msg))=E2=80=8B 

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

Since len(K) =3D 128=E2= =80=8B is the SHA512=E2=80=8B block size, we need a total of 4 SHA512 compr= ession 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 i= nto 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 arithmeticall= y simple; the SHA512 calls are where most of the arithmetic complexity lies= .

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

Note how= the parent secret key is the most important piece for soundness. The = circuit needs to prove the parent secret key existed in the hash function p= reimage, and is correctly related to the child secret key via modular addit= ion. So compression call (2) seems unavoidable. The others are less rigid.<= /div>

I'd arg= ue 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(<something> = || 0x00 || sk || i)=E2=80=8B)
c =3D=3D I[:32]=E2=80=8B
<= div style=3D"font-family: Arial, sans-serif; font-size: 14px;">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 exa= ctly one-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 entirely sure if this meaningfully weak= ens the verifier's soundness. Ethan Heilman 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.

This redu= ces our circuit to, i think, the minimum acceptable security floor for prov= ers: two SHA512 compression calls, which commit to a parent secret key.

=

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

Great work getting this working in the real world. I've hear= d 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 wh= ere their mouth is, and actually build a prototype. Bravo!

It seems to me the circuit (guest prog= ram) could be simplified. Notice how the guest code computes the entire HD wallet key path= , including hardened and non-hardened derivation steps, and also computes the taproot output key w= ith key-tweaking. I'd argue these steps are extraneous to the core hard rel= ation you want the STARK to prove, and could be safely removed to reduce pr= oof size and improve performance.

In reality, you needn't go so far as to prove (1) "I know a BIP39 seed which derives this taproot output key". You ne= ed only prove this much more general statement (2): "I kno= w 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 ev= en if they know your account-level xpub, but it entails far less computatio= n to prove and verify. The rest of the original statement (1) can be done e= xternally 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 t= he 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<= /code>=E2=80=8B in the witness. Note, i do not&n= bsp;mean we derive 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 write= s that xpriv into the guest program's inputs. The guest program de= rives and outputs the xpub at m/86'/0'/0'<= /code>=E2=80=8B. The verifier may check the STARK output (xpub) is cor= rectly computed, then use the given key-path to manually derive the taproot= address from the xpub themselves, outside the circuit, and validate&= nbsp;that address against the UTXO i'm spending= . The verifier thus has confirmed the prover knew an xpriv which (through a= hardened derivation step) derives the correct taproot output key.

This change significantly reduc= es the size of the circuit. From a glance, I see the original guest program= performs 6 HMAC-SHA512 calls (1 for the master key, 5 for the BIP32 deriva= tion 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 multiplication. I can't say for= sure, but I expect this will improve your proof size and runtime significa= ntly.

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

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

We= should also talk scaling efficiency. Given the cost of STARKs, this style = of proof should be able to authorize spends for more than one UTXO. Say you= have a wallet with 10 different UTXOs held by distinct addresses in the sa= me BIP44 account. One single STARK proof could authorize spending all 10 of= them, by simply committing all 10 input signature hashes into the journal,= and labeling the inputs with the corresponding 10 BIP32 key paths somehow. The verifier wou= ld need to check the proof only once and not 10 times. The 10 UTXO spends c= ould be validated using the common xpub from the STARK proof's journal.

For a slightly related wor= k proving a similar relation for hashed addresses, using different STARK te= chnology stacks, see this delvin= g post.

However, al= l this said, my personal preference for long-term procrastinator rescue is = still for commit/reveal strategies which prove essentially the same stateme= nt about BIP32 in a two-step procedure. They get the job done with much lig= hter cryptographic machinery and much smaller witnesses: a few hundred byte= s over two transactions, compared to a few million bytes in one transaction= with STARKs. Boris Nagaev a= nd I discussed this on the list a while back. That said, commit/reveal = requires more careful design and seems to demand the use of external quantu= m-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 = compared to STARKs for this purpose?

re= gards,
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <l= aolu32@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/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

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

[5]: https://microsoft.github.io/Picni= c/

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

[7]: https://github.com/Roasbeef/go-zkvm/blob/main/do= cs/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@googlegroups.com. To view this discussion visit https://grou= ps.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3acO14sgeHVUANx9w6TV= wUf_AYcd_qQ%40mail.gmail.com.

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

--
You received this message because you are subscribed to the Google Groups &= 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/MIvoK2= GkNbJJsK2fXOzHNffNuJGsnNnMpTgQczthUnChXesJMxi249BDV6b5DkIQfvGpBNgDdp5qATbc1= tGsUWPHXraBwaosU4Y_09m5pLY%3D%40proton.me.
-----------------------758cb83c097b03072091825438a967a3-- -----------------------0b1e3f3e6feedf4e90e708c0ea08f705-- -----------------------439b990bca872743655074b3f36d9a69 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== -----------------------439b990bca872743655074b3f36d9a69-- --------acd6237011109bbcfa85eb402c7acd2d6a9ddf4638b845ccdd3cfdc5234a57a2 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: ProtonMail wrsEARYKAG0FgmnWuRMJEHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp b25zLm9wZW5wZ3Bqcy5vcmefQNI40kyO12MCjQ168/kAYKRPnPwpnBzPY2zV zDcwXxYhBEdIka0CMtrLdg13a3gpbO2E9rPFAAC0fQD/aTZVuZGL8rVjNHiS PZ79yLMT6ctyTzkGS0ulSfXqWOoBALkr58xJXw+xbvtrDgCYKtvVVqkVQ/jS sNq2GooYX0YN =bjtj -----END PGP SIGNATURE----- --------acd6237011109bbcfa85eb402c7acd2d6a9ddf4638b845ccdd3cfdc5234a57a2--