From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 28 Apr 2026 18:21:57 -0700 Received: from mail-ot1-f56.google.com ([209.85.210.56]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wHtcf-0004xM-Tk for bitcoindev@gnusha.org; Tue, 28 Apr 2026 18:21:57 -0700 Received: by mail-ot1-f56.google.com with SMTP id 46e09a7af769-7dbe76e3abcsf28240153a34.0 for ; Tue, 28 Apr 2026 18:21:53 -0700 (PDT) ARC-Seal: i=3; a=rsa-sha256; t=1777425707; cv=pass; d=google.com; s=arc-20240605; b=fAbTKPYLZprJiI7qqjGUCdQniF3ZT1u7LutM78DZ/1FVhT5mZZFLhvmN+m7ZBe6mTQ kKdqGZbf+ojT8uxxTffty8FREJajOG5eSnHQVqyVAdccWtBB2gkUxcxsj3i1drcd/5aL 8H1jJdeeJCFr+ny5DmODaBSorLN4pRaAkfPBCEjYr5TDy9ILH/ganZGAhr5JnCJI4klP tidTfY7/l8KaLyjuH6XHpfTp7P5G5pYpMXmRlQsLQi4LPKKah5GUxKa0TulBVkqx3A6M 3h29E2zgSEKukhEsMA1IsBMxY54M57nTinWBy883c2azE79z3zYEJcWRqjvbzjdO9lgQ cnyQ== ARC-Message-Signature: i=3; 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=A99MB8bk58l4+StBlTnUfHE0ShFMpgkmM90NO2r1+qw=; fh=xjlfdfrjygLElwwPe342Zem2XO7rWSZvFrG6qML1NjE=; b=Dg/uFt2H8dO+hGfV6l6NMDEQ79vKWI4dt9E39+01YNWGmz56P50m9Vzs9xYP/78rSy QJzqwD4H8eL5DRjXhdtAL+ZlEsN+DRecSYf7EGecWfUvBbbbpA3FJb8NiW4qlnqS4CT5 X4KqIBmHK2uqJx6NWY8FTL0zh6w5SozRYtBC8NC6SoR9gsWOGTmQ5BTPZOU70biuLJWx ysM8oKLeG4BWu5XVtO9HzpBMGf2QiCgavLMMup1CWV2+eWOiuB2NaF2sC/5+Q4G87xvT lDHoBiytlawz7kE8mmsxVQkMTd2hZSPyuXOcmfOV+iR9IQybemz/NQgDCUPEf9TlVxXZ SACw==; darn=gnusha.org ARC-Authentication-Results: i=3; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=MvtiaXNB; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b12f as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1777425707; x=1778030507; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=A99MB8bk58l4+StBlTnUfHE0ShFMpgkmM90NO2r1+qw=; b=IVZMDGf5bGoBFmnUn5esaJbKiQnxbDXtYZ9PT5yKxfIF0C3Omu6gTezJNFNm5cmJwD YxcoDCR97eoGHOaGnLw6JJ4ZaWC6ly3bK3U+BJbmI/8MguSS/MM2ptOKcPHGzIg5XrRh DcxBtWjw82xgUfer+pcd1KvtYRzuHy2E04/sVzJm1VWpn+v+79orcX7y2vYvfRqsb2J/ ucpioMtQGNUeC+a0Y/j/JtMLsapGQtH1Jo69cO0+Pllysyi+bm/lYSn83hoWOVN3TIJ8 bvIg9XX/Si0PLY7hLhw0JTJxpir2vNJifiPe6jFrosH1+GGm9x5F0K7zxqJrv8kWOr3V rlhw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1777425707; x=1778030507; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=A99MB8bk58l4+StBlTnUfHE0ShFMpgkmM90NO2r1+qw=; b=WH9Up/HNE6HZqhZfq1Vjx1cg6TiXhCKcbxNRvpAHUlGMO10Y7gojPmB+JABNAhKuNj AQoLJDEN9dvsiNjCF7KljHLeVdMFQ/WxgWreMhFvGD7g4EH6jFOD1QJelKAGl2Sc069q oXHZggDFnp5l6Cb8RuA9gdVNBP5aB8UE6Nd+MfaqVpSVz/m257lkj1NmtO3j/M3R3wso foiTp4NsQ0LSuVoTAqrtJCX/7st/rrfISE5So1mgV5IfAhSUUGYsQY+gLb7jr0xLQmFA xvgDieuqnRVjhQACjfc/LvSYbu9728wCSiTRrNEiZzgjoo62LGWm19cy0Muse22GmBjG TWzQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777425707; x=1778030507; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-gm-gg:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=A99MB8bk58l4+StBlTnUfHE0ShFMpgkmM90NO2r1+qw=; b=skGXrAP/rkDmckCPcHC/eNr68AHOLFydZMjkn0metbs2wuir+2IZdlBOAYJ+kyyZsR Y7uQ6eolz4CKkJUS9Yg55+RCpPHcFDTj1ztJt8IA9VeodXjH3eiixtyC3n4aLczbOKEO z9jCKJvrYGVIBsEdaXStb2NuNo9HlLzM3nN5GmVKwRH8St6LfZOiiQWVuu57dmQGJhI5 hOnfFq7fvSNUbAq54Qv1SmiOGzFb4Ngcm7Rli8yAMIurgOXGNxoXfqsv0nLmAlcwJTx4 +UG89DLe8nTRjfV/egGe4R01ZWWLCjUw0H2H5OTmmqQlz21meRaa1P/2vOldtXOWaK/2 CkQw== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=3; AFNElJ/Ed6UFosmOYvsJv3AEA0xCZ7YVZeTy31+a92qs8FVVmg8/NILte69beUvOX3iPhB7fUG7I2PQ8bb//@gnusha.org X-Gm-Message-State: AOJu0Yx7KbdHlXmgL+Mc1nZ3sU37V2FXP8BjwBu3aTvZkNDDUy5qY4hW TbMtnYSKzVHO666ogUkoLEBSKwCr6Jii0hUVc4FjxhqSgVUu5ehS0x4n X-Received: by 2002:a05:6820:1688:b0:694:9a8a:2ce with SMTP id 006d021491bc7-6966837c609mr935952eaf.8.1777425706972; Tue, 28 Apr 2026 18:21:46 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AUV6zMN3/BIsdJOaxmKt2guY9xU1y6bihk15o1o5a9NZuspFLg==" Received: by 2002:a05:6820:60d:b0:696:6db8:d1af with SMTP id 006d021491bc7-6966db8dafdls1122eaf.1.-pod-prod-09-us; Tue, 28 Apr 2026 18:21:42 -0700 (PDT) X-Received: by 2002:a05:6808:181c:b0:467:2375:58c9 with SMTP id 5614622812f47-47c3dc4690fmr1012812b6e.45.1777425702112; Tue, 28 Apr 2026 18:21:42 -0700 (PDT) Received: by 2002:a54:4898:0:b0:479:9f23:6621 with SMTP id 5614622812f47-4799f236c9emsb6e; Tue, 28 Apr 2026 18:07:33 -0700 (PDT) X-Received: by 2002:a05:7300:72d5:b0:2e6:e77d:7bcf with SMTP id 5a478bee46e88-2ed198bf3f5mr903128eec.22.1777424852009; Tue, 28 Apr 2026 18:07:32 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1777424852; cv=pass; d=google.com; s=arc-20240605; b=OO7WJxmQanzTIp/4vOlGqtVK7yblUQrG/9QPmIH3kP4QjspRFkLK/Dd9EgQ8GNJWyZ 3dKtvO/PN3VCXzY4mdXEoZCor4fh/iCTfmfRCbKIJbnw9VIxAS/0p4Np4l5N2Eq2FDMc NtkzXTjH/T7axKSMXi+9n5eMQ0p5U46Tnsn1UQ/PJcqPU+B21Tq6nOTUiOqnhiojxDoc vhVPnTfISKJPBTQtojZxj6JQTBlJ5I4lnLnwq/x5RyOxlFTcloD05Z3NGk/7UWXQQn1d OeTSPgLl7+io6PPjkfGgHOwdeIITzyxynYhk6nlnY/Fw32pPSWfKIMDl9NejkrGFsGZU QXRg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=w9HufxB1tHEcmD8cvtCAbZVB1D1OSZ1b7IcTA96NqCg=; fh=/N7hLAnjazzpj1blspkoIYUbVf3N/Xvk2Re0f9S4crY=; b=kC+GpTMSV9Zzif1TrJAmPBqoRG8mNox4PhXpTKKWOeRCcAKT+6QO6+uDTWTOlYt8Ac G1Pg7mPr03HofiPdbwAyUguHDsGwhoHPuQ/2bufVkb4GpvG+1LFLaJMsGDG7GdRDMh1Q Qw1lMSWmnk3n6+PuTR2KKC6UrQudfiIaYHttnGetxmWRPwYmn9+pAiKeRBVhSxNpVugo f8RWCUrX9LTERlT7q4KKJQOgPQgXbboaS4cS6lD/wtZB0/+78Pr8nZsGuo+IVD1iYeT8 e3LXvjNRPhRAqtKENvuUnaYbsEpwoxh4IQoWhPP5ELzk7QKVWPDyTmtXifEfKrdx0W9w Ct6w==; dara=google.com ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=MvtiaXNB; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b12f as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-yx1-xb12f.google.com (mail-yx1-xb12f.google.com. [2607:f8b0:4864:20::b12f]) by gmr-mx.google.com with ESMTPS id 5a478bee46e88-2ed1be7978bsi21385eec.0.2026.04.28.18.07.31 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 28 Apr 2026 18:07:31 -0700 (PDT) Received-SPF: pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b12f as permitted sender) client-ip=2607:f8b0:4864:20::b12f; Received: by mail-yx1-xb12f.google.com with SMTP id 956f58d0204a3-65890a6ca20so3264316d50.0 for ; Tue, 28 Apr 2026 18:07:31 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1777424851; cv=none; d=google.com; s=arc-20240605; b=D7kBJujj36BtgPooL+DjFEKZLPUU3Pobl2mYEng3+JXM1sIeUfo+AmNg757wNp0pvM cAe37zrWe9moyThU5MqLbP1H0PjoILWNKQc6ZVQnZTl3GEbbaP4tynbGnR36yV7f+chQ cfS55lmeUiEVCg1Pc6lqumdZgCyZswBE0bHPEYhJCte4GFaWOiEc/VADzwxfJkQUMN9q UxATeJDkBEPtHN7PTe90uud8u+80inyXbjg39GEMjhXdXA+Y5dIkB19RI9LOLUV/LXeb vqdJe3U6Xo/ReHO6LOJNbgNJPxYVyxrJ7eMjNhYAiCBD9ZFiv6gAhawqc+6xIRQcpXRd rACA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=w9HufxB1tHEcmD8cvtCAbZVB1D1OSZ1b7IcTA96NqCg=; fh=/N7hLAnjazzpj1blspkoIYUbVf3N/Xvk2Re0f9S4crY=; b=d2g+3v1Ycbx6zlu0z14mrywHBo3jBl5JcAOt3dL+xTqN5J0A8qYU+UKb+mzTpvMWng uAlACBJ3n650eSgSUPreWdO0tXICb92o0UTIDUTN4IAHQ2oKr4gK5JWllnZkb/pXsFBQ 0PQd2xkXFqZqABK03873KKHMT3mJp7Mw5b0TfNX+ysTdFWDFcuRNrGgDcelaDefR4QNk YEl7rQoFyzevJqFGHE6zyqtTOOydJ84IMIfyYIL+IpsF35SrpWVjOTtx3k4IAIiTxPk6 4wlRPEbSQ1mkSXvQ6ryuX2/wT2UX58qfQOjzmQOcxRW+OJOxbmN6j9bEhR1oMD19EKNO lRMA==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; arc=none X-Gm-Gg: AeBDieu+64KiJVa71616AS4dh5iyCenwlVX65BabIYZnM409y6Dm88F0cFrWpe9FnNy euQvxgR+dycC2bdHXki9OW2OW0OKGIv6uGiYJIaThLuHzT1VVbYBBxEouj+CGL+c01V8E8eE8xM 0X5bU9i8EzL1ZcKIEPjSzUXaE6BRGbdHV6U6iAmpTUVSHBeIEjRGC9refspYaVDv0XLBopeOAvb xp8PxO9ukCz66p+Fj4VnWoMQOy8oCjp+489MDSJw16JmM7iYFO4Hv2vPg79zR0afShVGZYpSzS2 +A5AZwRMNaJHUEFBZcqaPA3MthcybPFR5jhYev6m06OI5Fv5uwk= X-Received: by 2002:a53:d782:0:b0:64e:e82e:8413 with SMTP id 956f58d0204a3-65bfb5caa63mr1780558d50.1.1777424850537; Tue, 28 Apr 2026 18:07:30 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Olaoluwa Osuntokun Date: Tue, 28 Apr 2026 18:07:19 -0700 X-Gm-Features: AVHnY4I3xh8_Mj0SBc04ETfZPtHHyhxrdNcFr1nLds4R9XgqSVGh_3HtKmZeLQM Message-ID: Subject: Re: [bitcoindev] Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge To: Alex Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000d4d3ec06508ef8e9" X-Original-Sender: laolu32@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=MvtiaXNB; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b12f as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) --000000000000d4d3ec06508ef8e9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi ALex, > 1.7 MB is not realistically useful for anything > It's so big that, even the biggest PQC signatures are orders of magnitude > smaller and if you do some basic napkin math you can see that it's > realistically never going to be useful See my latest posts on this thread. It's possible to have only a single 200 KB proof per block. Also, I think you misunderstand. This isn't a replacement for PQC signature= s (proactive soft fork). This is a rescue scheme (reactive soft fork) that ma= y allow the rightful owners of coins to recover them in the future if they la= g behind the eventual proactive soft fork to add in new signature schemes. > The sheer complexity of ZK-STARK proofs and their multi-second verification > cost is practically never going to land in Bitcoin STARKs don't take multiple seconds to verify. You can run the code in my repo to see, it verifies in tens of milliseconds [1]. > Realistically, a multi-million line VM tied to a specific CPU architecture is > absolutely never going to land in Bitcoin just from its sheer complexity and > attack surface it introduces Did you read my original post? I'm not advocating we adopt this architectur= e verbatim. This is just a demo to show what can be done. If this were to be seriously proposed, it's more likely that a hand rolled circuit for our specific claim would be used. The simplest claim as shown earlier in this thread comes down to a few hash function invocations. [1]: https://github.com/Roasbeef/bip32-pq-zkp -- Laolu On Mon, Apr 13, 2026 at 12:21=E2=80=AFPM Alex wrote= : > I guess my first response got moderated because I was too negative, so > here is the retry: > > * 1.7 MB is not realistically useful for anything. It's so big that, even > the biggest PQC signatures are orders of magnitude smaller and if you do > some basic napkin math you can see that it's realistically never going to > be useful (it would takes decades for people to migrate and it would cost > you more than your entire portfolio to move the funds). Therefore it is > realistically unusable. > * The sheer complexity of ZK-STARK proofs and their multi-second > verification cost is practically never going to land in Bitcoin - for > reference - just look at OP_CAT, a 12 line addition that has been stuck i= n > review for years. Realistically, a multi-million line VM tied to a specif= ic > CPU architecture is absolutely never going to land in Bitcoin just from i= ts > sheer complexity and attack surface it introduces. Therefore it is nothin= g > more than esoteric make belief, if we are being realistic. > > For the layman, it is also a lazy way to offload the PQC problem to the > future "ah but we just put a ZK proof and we're done" as if ZK proofs are > readily available commodities - they are not. It's not that simple, for t= he > complexity reasons above. We need slim security assumptions, such as the > SHRINCS hash based signatures and we need them now, so that we can migrat= e > billions of ETF funds already. > > ZK-STARKs are the new "silver bullet" but realistically, Bitcoin is so > ossified (as evident by the multi-year delay for OP_CAT) that discussions > regarding it is, well, esoteric distractions. > > Also it makes no sense to deny SQIsign based on "it's too complex, we > don't know if the security assumptions hold" and then with the other hand > argue that "let's shove this multi million line CPU VM into Bitcoin and p= ut > 1.7 MB proofs that take multiple seconds to verify (that alone is a MAJOR > DOS attack surface) > > You get my point? It's so easy to say "ZK this, ZK that" but the sheer > massive complexity it brings is a gaping flesh wound in terms of attack > surface. > torsdag 9 april 2026 kl. 23:56:07 UTC+2 skrev Olaoluwa Osuntokun: > >> Hi Condution, >> >> So I implemented both variants of your idea. My intuition was right in >> that it >> doesn't do much to reduce the size of the final succinct size, but the >> final >> xpriv variant resulted in a significant reduction in both proving time, >> and >> also memory usage. I also re-ran the original succint proof for the >> original >> Taproot claim and got a better value for the final proof time (def need = a >> better benchmark env+set up!). >> >> Here's a breakdown of the resource requirements for the various proofs: >> * Full Taproot >> image ID: >> 8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690 >> composite: >> seal 1797880 >> prove 49.32s >> verify 0.10s >> peak RSS 11907399680 >> succinct: >> seal 222668 >> prove 64.30s >> verify 0.03s >> peak RSS 11927207936 >> >> * Hardened xpub >> image ID: >> ad4ebc0ef6ce51e0f581cc8d14742a5b97738e9decd3fe2b0f1746de5bad9617 >> composite: >> seal 513680 >> prove 14.63s >> verify 0.04s >> peak RSS 11783503872 >> succinct: >> seal 222668 >> prove 17.29s >> verify 0.02s >> peak RSS 11782307840 >> >> * Hardened xpriv >> image ID: >> 8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c0df0849 >> composite: >> seal 234568 >> prove 1.98s >> verify 0.02s >> peak RSS 3144171520 <(314)%20417-1520> >> succinct: >> seal 222668 >> prove 2.84s >> verify 0.02s >> peak RSS 3145990144 <(314)%20599-0144> >> >> So we can see that the succinct proof sizes are all about the same. >> However the >> xpriv variant can be proved directly in just 2 seconds on my machine! It >> also >> requires just 3 GB of memory for the proof as well. >> >> I've created some additional supporting documentation to detail exactly >> what >> the new proofs do and their results: >> >> * >> https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/reduced-variants= .md >> >> * >> https://github.com/Roasbeef/bip32-pq-zkp/blob/1c89fdb398180a2b3eff7761b7= f4b233d455c6c9/README.md#reduced-proof-variants >> >> * >> https://github.com/Roasbeef/bip32-pq-zkp/blob/438c548ca9b49d83ef4019974a= 5171f5e06fa840/docs/claim.md#reduced-variant-claims >> >> >> Once again, thanks for the great ideas! I wonder if we can improve on th= is >> round of proof golf further before 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 >> wrote: >> >>> Hi Conduition, >>> >>> > You need only prove this much more general statement (2): "I know a >>> BIP32 >>> > xpriv which derives this xpub via one or more hardened steps". >>> >>> > I'm amending my prior suggestion slightly: The circuit (guest program= ) >>> > could take in an xpriv (e.g. at m/86'/0') and output a child xpriv >>> > (e.g. at m/86'/0'/0') to the journal (instead of outputting a child >>> > xpub). >>> >>> That's an excellent insight! >>> >>> As mentioned in my recent reply, with risc0's "succinct" receipt type, = I >>> was >>> able to get the proof size down to 220 KB, at the cost of 3.5x longer >>> total >>> proving time. >>> >>> 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. >>> >>> 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. >>> >>> However, this can still be a win as then this would provide potential >>> future >>> users with a less resource intensive proof, which can then be >>> aggregated/rolled up into a final succinct proof in a batched manner. >>> >>> This line of optimization is also more interesting if one were to look = at >>> hand rolling a custom AIR to avoid the overhead that the RISC-V emulati= on >>> adds to the rirsc0 proof chain, given that it entirely skips doing any = EC >>> operations at all for the final statement. >>> >>> ---- >>> >>> Re the commit/reveal approach, to be honest I'm not fully caught up on >>> 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! >>> >>> -- Laolu >>> >>> >>> On Wed, Apr 8, 2026 at 1:23=E2=80=AFPM conduition = wrote: >>> >>>> Oh, I've been a fool, a foolish fool. >>>> >>>> We don't even need to do point multiplication in the circuit at all. >>>> >>>> I'm amending my prior suggestion slightly: The circuit (guest program) >>>> could take in an xpriv (e.g. at m/86'/0'=E2=80=8B) and output a *child= xpriv *(e.g. >>>> at m/86'/0'/0'=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, and to a quantum attacker, an xpub is computationally equival= ent >>>> to its xpriv. So why bother hiding it? The child xpriv doesn't give an >>>> observer anything they can't already do with the equivalent xpub. >>>> >>>> The guest program then is basically 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. Honest verifiers us= e the >>>> xpriv to derive the child address(es) as suggested in my last message,= to >>>> authenticate spending. >>>> >>>> Designing the guest program like this will massively reduce your >>>> circuit complexity, because EC point multiplication is *wayyyyy* >>>> harder for the RISC0 compiler to arithmetize than a simple hash functi= on. >>>> 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 prover runtime by a factor of over 100x. >>>> >>>> If I am not fever-dreaming and this is indeed possible, then the new >>>> circuit's complexity will be dominated not by point multiplication, bu= t by >>>> the HMAC-SHA512 call. Our new task is then to figure out how much we c= an >>>> internally optimize the HMAC-SHA512 call for STARK proving. Here's a f= ew >>>> ideas. >>>> >>>> If you bust open HMAC-SHA512, it looks like this: >>>> >>>> HMAC_SHA512 =3D SHA512((K=E2=8A=950x5c) || SHA512((K=E2=8A=950x36) || = msg))=E2=80=8B >>>> >>>> ...where in the context of BIP32 hardened CKD, the HMAC key K=E2=80=8B= is the >>>> chaincode (padded with zeros to 128 bytes) and msg =3D (0x00 || sk || = i) is >>>> the parent secret key and child index. >>>> >>>> Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we ne= ed 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 delta which is added to the parent secret key (mo= dulo >>>> the curve order), producing the child EC secret key. This last step is >>>> arithmetically simple; the SHA512 calls are where most of the arithmet= ic >>>> complexity lies. >>>> >>>> The question then becomes, which of these compression calls can be don= e >>>> 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 preimage, and is correctly related to the child secret k= ey >>>> via modular addition. So compression call (2) seems unavoidable. The o= thers >>>> 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 a= nd index i=E2=80=8B, I >>>> know a preimage x*=E2=80=8B and secret key *sk=E2=80=8B such that: >>>> >>>> I <- SHA512( || SHA512( || 0x00 || sk || i)=E2= =80=8B) >>>> c =3D=3D I[:32]=E2=80=8B >>>> k =3D=3D int(I[32:]) + sk % n=E2=80=8B >>>> >>>> Seeing as the =E2=80=8B slots are arbitrary, and we know in= BIP32 >>>> they are always exactly one-block long, it seems easy to throw out the >>>> compression calls (1) and (3). The host can precompute the relevant SH= A512 >>>> 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 h= ash >>>> input length can be fixed at 192 bytes). I'm not entirely sure if this >>>> meaningfully weakens the verifier's soundness. Ethan Heilman might hav= e >>>> opinions on this, he knows a lot more about attacking hash functions t= han I >>>> do. Intuitively, I doubt sampling random SHA512 midstates is that much >>>> better than sampling a random HMAC key (chaincode) K=E2=80=8B and comp= uting >>>> the resulting midstates. >>>> >>>> This reduces our circuit to, i think, the minimum acceptable security >>>> floor for provers: two SHA512 compression calls, which commit to a par= ent >>>> secret key. >>>> >>>> >>>> regards, >>>> conduition >>>> On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via Bitcoin >>>> Development Mailing List 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 whe= re >>>> their mouth is, and actually build a prototype. Bravo! >>>> >>>> It seems to me the circuit (guest program) 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 with key-tweaking. I'd argue these ste= ps >>>> 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. >>>> >>>> In reality, you needn't go so far as to prove (1) *"I know a BIP39 >>>> seed which derives this taproot output key"*. You need only prove this >>>> much more general statement (2): *"I know a BIP32 xpriv which derives >>>> this xpub via one or more hardened steps"*. The latter statement (2) >>>> still cannot be forged by a quantum adversary even if they know your >>>> account-level xpub, but it entails far less computation to prove 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 *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 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 may check the STARK output (xpub) is correctly computed, then= use >>>> the given key-path to manually derive the taproot address from the xpu= b >>>> themselves, outside the circuit, and validate *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 reduces 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 derivation steps), two SHA256 >>>> compression calls (for the taptweak hash), and two point multiplicatio= ns. >>>> With this simplified variant, we are invoking only a single HMAC-SHA51= 2 >>>> call and a single point multiplication. I can't say for sure, but I ex= pect >>>> this will improve your proof size and runtime significantly. >>>> >>>> This change also makes the circuit more generally applicable to other >>>> rescue contexts. For instance, it could be applied to BIP340 xonly key= s >>>> inside a taproot script tree, or in a P2(W)SH address to an ECDSA publ= ic >>>> key, or to P2(W)PKH addresses. >>>> >>>> Concerned about publishing xpubs? Remember that we are assuming regula= r >>>> 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 surveil= lance >>>> but not forgery. If one would prefer not to share the account-level >>>> xpub on-chain for privacy reasons, the proof could be extended to 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 UT= XO. >>>> Say you have a wallet with 10 different UTXOs held by distinct address= es in >>>> the same BIP44 account. One single STARK proof could authorize spendin= g 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 >>>> 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 comm= on >>>> xpub from the STARK proof's journal. >>>> >>>> For a slightly related work proving a similar relation for hashed >>>> addresses, using different STARK technology stacks, see this delving >>>> post . >>>> >>>> However, all this said, my personal preference for long-term >>>> procrastinator rescue is still for commit/reveal strategies which prov= e >>>> essentially the same statement about BIP32 in a two-step procedure. Th= ey >>>> get the job done with much lighter cryptographic machinery and much sm= aller >>>> witnesses: a few hundred bytes over two transactions, compared to a fe= w >>>> million bytes in one transaction with STARKs. Boris Nagaev and 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 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 th= ink >>>> of commit/reveal compared to STARKs for this purpose? >>>> >>>> regards, >>>> conduition >>>> >>>> On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun < >>>> lao...@gmail.com> wrote: >>>> >>>> Hi y'all, >>>> >>>> I found some spare time this last weekend to dust off a little side >>>> project >>>> I started last August: extend TinyGo [1] to be able to produce RISC-V >>>> ELF >>>> binaries capable of being run as a guest on the risc0 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 >>>> host/guest >>>> architecture of risc0. Fast forward ~9 months later, and 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 \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"} \;\|\; >>>> \mathbf{p}\bigr) >>>> \end{aligned} >>>> \;\right\rbrace >>>> ``` >>>> >>>> where $K$ is the Taproot output key, $C$ is the path commitment, $s$ i= s >>>> the >>>> BIP-32 seed, and $\mathbf{p}$ is the derivation path. >>>> >>>> >>>> I was able to get everything working e2e over the weekend, after makin= g >>>> some tweaks to my initial architectural game plan! >>>> >>>> The TL;DR is that: >>>> >>>> * Given that the Taproot commitment scheme is post-quantum secure [3], >>>> in >>>> the future we can deploy a soft fork to _disable_ the keyspend path, >>>> and force all Taproot spends to instead flow through the script path >>>> (not my idea, commonly discussed amongst developers, not sure who >>>> proposed it first). At that point, Taproot starts to resemble BIP-360. >>>> >>>> * That works for script path spends, but then leaves all the BIP-86 >>>> wallets in a bad position, as they generated outputs that provably >>>> don't commit to a script path at all. >>>> >>>> * A 2023 paper (Protecting Quantum Procrastinators with Signature >>>> Lifting: A Case Study in Cryptocurrencies [4]) proposed a solution to >>>> this, >>>> namely _seed lifting_ (use BIP-32 as the one-way function to the >>>> Picnic PQ Signature scheme) to provide a post-quantum proof of secret >>>> information a quantum attacker wouldn't be able to easily obtain. >>>> >>>> * The downside of that is that it reveals the secret BIP 32 seed, >>>> exposing other non migrated UTXOs of a user. >>>> >>>> * With this project I've cobbled together a series of projects to be >>>> able >>>> to generate a zk-STARK proof that a Taproot output public key was >>>> generated via BIP-32 invocation of a BIP-86 derivation path. >>>> >>>> * In the future a variant of this scheme can be used to enable wallets >>>> that generated the private keys via BIP-86, to have a post quantum saf= e >>>> exit path in case they don't bother moving their coins in time to the >>>> yet-to-be-decided post quantum signature scheme. >>>> >>>> To achieve this end, I needed to create/fork a series of repos: >>>> >>>> * tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm >>>> * A fork of TinyGo that supports the flavor of RISC-V (rv32im) that >>>> risc0 requires to generate/execute a guest program to later be proved >>>> by the host. >>>> >>>> * risc0: https://github.com/Roasbeef/risc0 >>>> * Mostly a bug fix to their c-guest example, along with some >>>> additional documentation on how to get things running. The repo is >>>> unmodified other than that. Recent updates to the repo made the >>>> entire process much easier (Go guest+host), more on that later. >>>> >>>> * go-zkvm: https://github.com/Roasbeef/go-zkvm >>>> * Go utilities to take a RISC-V ELf binary produced by tinygo-zkvm, an= d >>>> package it in the expected R0BF format, which combines the user >>>> generated RISC-V ELF (the thing that is executed to generate the >>>> proof) along with the v1compat ELF kernel, which is risc0's execution >>>> environment. >>>> >>>> * This also includes a Go host package, which loads the guest program, >>>> executes it, and generates a trace to later be proved. This is >>>> achieved via a C FFI compat layer between Go and the original Rust >>>> host/proving/verification code. >>>> >>>> * bip-32-pq-zkp: https://github.com/Roasbeef/bip32-pq-zkp >>>> * The project that packages everything together, this contains the: >>>> * Guest Go program that defines the secret witness and >>>> claim/constraints of the proof. >>>> >>>> * The C FFI wrapper around the OG Rust host, which is used to load >>>> the guest program, execute it, generate a trace, then finally >>>> generate a proof. >>>> >>>> Details of the final proof as generated on my Mac Book (Apple Silicon = 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. >>>> >>>> On several layers, this demo is far from optimized (more on that later= ), >>>> this is meant to serve as a PoC to demonstrate that with the latest >>>> software+hardware, a proof of this complexity is well within reach. >>>> >>>> For those curious re the e2e details I've generated this tutorial that >>>> explains the entire system top to bottom: >>>> https://github.com/Roasbeef/go-zkvm/blob/main/docs/tutorial.md. >>>> >>>> If you got to this point in this mail, and don't care about the lower >>>> level >>>> details, thanks for reading up until now, and feel free to return back >>>> to >>>> the _The Net of a Million Lies_, or as better known in our Universe: >>>> Monitoring the Situation and/or slopfotainment! =F0=9F=AB=A1 >>>> >>>> ## Motivation + Background >>>> >>>> As commonly known, in the case of an adversary that possesses a quantu= m >>>> computer capable of breaking classical asymmetric cryptography, any >>>> coins >>>> stored in UTXOs with a known public key are vulnerable. This is the ca= se >>>> 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 publi= sh >>>> the public key plainly in the pkScript. >>>> >>>> As detailed in [3], for Taproot outputs, a widely circulated plan is >>>> roughly to: disable the _keyspend_ path (requires a simple signature), >>>> enforcing a new rule that all Taproot spends must then flow through th= e >>>> 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 >>>> binding even >>>> under classic assumptions, as H(M) (tapscript merkle root) is still a >>>> collision-resistant function. >>>> >>>> That means any UTXO that _does_ commit to a script path has a future >>>> escape >>>> hatch _if_ such a softfork would need to be deployed in the future. >>>> However, what about all the other wallets that use BIP 86, and don't >>>> commit >>>> to a script path at all? Under a strict version of this existing >>>> proposal, those wallets would basically be locked forever. >>>> >>>> The goal of this work is to demonstrate a practical solution (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-STARKs, >>>> as they're plausibly post quantum since they rely only on symmetric >>>> cryptography: layers of merkle trees over an execution trace, along wi= th >>>> 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 >>>> 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 th= e >>>> best known quantum collision finder, and it runs in time proportional >>>> to the >>>> cube root of the output space: 2^(n/3). For HMAC-SHA512's 512-bit >>>> output, >>>> that's ~2^171 quantum operations, well above even NIST's highest >>>> post-quantum security category. Therefore, if you generated a wallet >>>> using >>>> BIP-32, you possess _another_ secret that a quantum adversary can't >>>> efficiently reconstruct! >>>> >>>> This demo focuses on the Taproot case, but the rough approach also >>>> 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. However, Bitcoin Core only officially adopted BIP-3= 2 >>>> 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. >>>> >>>> ## TinyGo + RISC-V + risc0 >>>> >>>> Now for some of the lower level details. risc0 is a STARK based provin= g >>>> system that takes a RISC-V ELF binary generated by a guest program (an= y >>>> program generating using their flavor of rv32im can be proved), execut= es >>>> that in a host environment, generates a trace, then produces a STARK >>>> proof >>>> from that. >>>> >>>> Today you can take some subset of Rust, compile it to an ELF using the= ir >>>> toolchain, then execute it, generate a trace, to finally prove+verify = it >>>> using their system. >>>> >>>> This demo took a bit of a round about journey to achieve this, as afte= r >>>> all, the journey is most of the fun, ain't it! >>>> >>>> For the past 10 years or so, my Bitcoin stack of choice (lnd/btcsuite) >>>> uses >>>> a series of Go libraries, so I wanted to be able to re-use them, first >>>> for >>>> this demo, then also in the future for other projects. >>>> >>>> TinyGo is a special Go compiler based on LLVM, that targets mostly >>>> embedded >>>> environments. You can use it to generate go programs that can run on >>>> micro controllers, or on web assembly (producing a smaller binary than >>>> if >>>> you used the normal stdlib path). >>>> >>>> TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V that >>>> risc0 >>>> relies on. So the first step here was to create a new target definitio= n >>>> for >>>> TinyGo: riscv32-unknown-none, which uses base integer + multiply/divid= e >>>> instructions with no compressed instructions, which uses 4 KB stacks f= or >>>> 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 >>>> specific >>>> syscalls for risc0 (putchar(), exit(), ticks(), and growHeap()). >>>> >>>> When I tried to get this working last year, I had to also implement a >>>> number >>>> of kernel syscalls (called ecalls in the platform [7]) to handle: >>>> read+write >>>> to stdin/stdout, halting, and the 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 versio= n >>>> of >>>> the repo, I realized that they now make a libzkvm_platform.a, which >>>> packages >>>> up the kernel nicely to be linked against. So I threw out my custom >>>> kernel >>>> code, and slotted that in instead. >>>> >>>> The final component is a C FFI layer that enables me to use _both_ a G= o >>>> guest (the program to be proved) and a Go host (the thing that execute= s >>>> the >>>> program and generates the final proof). >>>> >>>> ## BIP-32+Taproot zk-STARK Proof >>>> >>>> With basic proofs working (like the classic: I know the factorization >>>> of a >>>> number `n`), I was unblocked to generate the actual proof. The >>>> claim/proof >>>> is represented with the following JSON artifact: >>>> ``` >>>> { >>>> "schema_version": 1, >>>> "image_id": >>>> "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690", >>>> "claim_version": 1, >>>> "claim_flags": 1, >>>> "require_bip86": true, >>>> "taproot_output_key": >>>> "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992b288ee6", >>>> "path_commitment": >>>> "4c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b", >>>> "journal_hex": >>>> "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07= f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b= ", >>>> "journal_size_bytes": 72, >>>> "proof_seal_bytes": 1797880, >>>> "receipt_encoding": "borsh" >>>> } >>>> ```` >>>> >>>> The `image_id` is basically a hash of the ELF, so you know what the >>>> prover >>>> executed. There are then a few flags that control the claim version an= d >>>> 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 _public data_, as it sits plainly on the chain for al= l >>>> to >>>> see. We then also include a `path_commitment`, which is a commitment t= o >>>> the >>>> exact BIP 86 path that the prover used. Finally, we also commit to the >>>> journal hex, which is basically a commitment to the public claim. >>>> >>>> Assuming you've built the project, then you can generate the proof (ev= en >>>> passing in an arbitrary BIP-32 seed and derivation path with) >>>> ``` >>>> make prove GO_GOROOT=3D/path/to/go1.24.4 >>>> ``` >>>> >>>> Then verify it with: >>>> ``` >>>> make verify GO_GOROOT=3D/path/to/go1.24.4 >>>> ``` >>>> >>>> The default prove target writes: >>>> * ./artifacts/bip32-test-vector.receipt >>>> * ./artifacts/bip32-test-vector.claim.json >>>> >>>> The receipt is the STARK proof artifact. claim.json is the stable, >>>> human-readable description of the public statement being proved. >>>> >>>> ## Application to a Future Keyspend Disabling Soft fork >>>> >>>> As mentioned above, assuming the community is forced to deploy a >>>> keyspend >>>> disabling soft fork in the future, we can also deploy some variant of >>>> this proof to enable both BIP-86 wallets, and also any BIP-32 wallet, = to >>>> sweep their funds into a new PQ output. >>>> >>>> In 2026, we've shown that this is achievable using 2 year old consumer >>>> hardware. I don't doubt that the upcoming advancements (eg: photonics, >>>> new >>>> flavor of high bandwidth memory, etc) in hardware (driven by the fierc= e >>>> AI >>>> race) will make such a proof even more feasible. >>>> >>>> One thing to note is that this proof has a few layers of indirection, >>>> mainly the RISC-V layer that adds overhead which increase the total >>>> amount >>>> of steps, and therefore the size of the proof. A production grade >>>> deployment would likely instead hand roll a custom STARK proof for thi= s >>>> exact statement, to achieve a faster and smaller proof). >>>> >>>> # Future Work >>>> >>>> In terms of future work, there're a number of interesting following up >>>> projects that can be pursued from here. >>>> >>>> One basic one is that the current proof doesn't actually commit to a >>>> spending txid and/or sighash. That can be trivially incorporated into >>>> the >>>> proof. Going a step further, the execution of the guest program can ev= en >>>> _generate_ a valid schnorr signature to permit spending. >>>> >>>> Looking to the memory+computational requirements necessary to generate >>>> the >>>> proof, I've left two low hanging fruits: >>>> >>>> 1. First, we can speed up the Elliptic Curve operations the proof >>>> requires >>>> (scalar base mult, then addition, or more performantly Double Scalar >>>> Multiplication via the Strauss-Shamir trick). For this we can use the >>>> syscalls/precompile in the risc0 env for big integer arithmetic: >>>> sys_bigint and sys_bigint2. With this, the guest calls into the kernel >>>> to use an optimized/accelerated circuit for the modular arithmetic, >>>> reducing cycles, steps, and thus proof size. >>>> >>>> 2. Second right now, the entire claim is a single proof. Instead, we c= an >>>> first break that up using their recursive proof/composition syscalls: >>>> sys_verify_integrity+sys_verify_integrity2. We can then assembled a >>>> series of these proofs into a _single_ statement, which can save block >>>> space by aggregating N proofs into a single proof. >>>> >>>> -- Laolu >>>> >>>> [1]: https://tinygo.org/ >>>> >>>> [2]: https://risczero.com/ >>>> >>>> [3]: https://eprint.iacr.org/2025/1307 >>>> >>>> [4]: https://eprint.iacr.org/2023/362 >>>> >>>> [5]: https://microsoft.github.io/Picnic/ >>>> >>>> [6]: https://en.wikipedia.org/wiki/BHT_algorithm >>>> >>>> [7]: >>>> https://github.com/Roasbeef/go-zkvm/blob/main/docs/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 email to bitcoindev+...@googlegroups.com. >>>> To view this discussion visit >>>> https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs_PciUi%2BzBrCps3ac= O14sgeHVUANx9w6TVwUf_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 email to bitcoindev+...@googlegroups.com. >>>> To view this discussion visit >>>> https://groups.google.com/d/msgid/bitcoindev/ciibnh-b0x-rLwA8pY5NURBfP= vG58gLcS7yPLIIkFV5IzA1k-PTsPZqYU8uUyQRxLCnEFhGcrRCTM39N2AYEy0Db2H_UwIse3Hg9= XEXNEYg%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 > email to bitcoindev+unsubscribe@googlegroups.com. > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/bd1f1379-fffa-4a93-a747-c449= c2f7265cn%40googlegroups.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/= CAO3Pvs8ErTm%2Bzxx4bkF5F-22pt%2BuFzY6S6CdLsn04sS3Tvcmrg%40mail.gmail.com. --000000000000d4d3ec06508ef8e9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi ALex,

> 1.7 MB is not realistically use= ful for anything
> It's so big that, even the biggest PQC signatu= res are orders of magnitude
> smaller and if you do some basic napkin= math you can see that it's
> realistically never going to be use= ful

See my latest posts on this thread. It's possible to have on= ly a single 200 KB
proof per block.

Also, I think you misunderst= and. This isn't a replacement for PQC signatures
(proactive soft for= k). This is a rescue scheme (reactive soft fork) that may
allow the righ= tful owners of coins to recover them in the future if they lag
behind th= e eventual proactive soft fork to add in new signature schemes.

>= The sheer complexity of ZK-STARK proofs and their multi-second verificatio= n
> cost is practically never going to land in Bitcoin

STARKs= don't take multiple seconds to verify. You can run the code in my repo=
to see, it verifies in tens of milliseconds [1].

> Realistica= lly, a multi-million line VM tied to a specific CPU architecture is
>= absolutely never going to land in Bitcoin just from its sheer complexity a= nd
> attack surface it introduces

Did you read my original pos= t? I'm not advocating we adopt this architecture
verbatim. This is j= ust a demo to show what can be done. If this were to be
seriously propos= ed, it's more likely that a hand rolled circuit for our
specific cla= im would be used. The simplest claim as shown earlier in this
thread com= es down to a few hash function invocations.

[1]: https://github.com/Roasbeef/bip32-pq-zkp<= /a>

-- Laolu


On Mon, Apr 13, 2026 at 12:21=E2=80=AFPM Alex <alexhultman@gmail.com> wrote:=
I guess my firs= t response got moderated because I was too negative, so here is the retry:<= br>
* 1.7 MB is not realistically useful for anything. It's so big t= hat, even the biggest PQC signatures are orders of magnitude smaller and if= you do some basic napkin math you can see that it's realistically neve= r going to be useful (it would takes decades for people to migrate and it w= ould cost you more than your entire portfolio to move the funds). Therefore= it is realistically unusable.
* The sheer complexity of ZK-STARK proofs= and their multi-second verification cost is practically never going to lan= d in Bitcoin - for reference - just look at OP_CAT, a 12 line addition that= has been stuck in review for years. Realistically, a multi-million line VM= tied to a specific CPU architecture is absolutely never going to land in B= itcoin just from its sheer complexity and attack surface it introduces. The= refore it is nothing more than esoteric make belief, if we are being realis= tic.

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

ZK-STARKs ar= e the new "silver bullet" but realistically, Bitcoin is so ossifi= ed (as evident by the multi-year delay for OP_CAT) that discussions regardi= ng it is, well, esoteric distractions.

Also it makes no sense to den= y SQIsign based on "it's too complex, we don't know if the sec= urity assumptions hold" and then with the other hand argue that "= let's shove this multi million line CPU VM into Bitcoin and put 1.7 MB = proofs that take multiple seconds to verify (that alone is a MAJOR DOS atta= ck surface)

You get my point? It's so easy to say "ZK this,= ZK that" but the sheer massive complexity it brings is a gaping flesh= wound in terms of attack surface.
torsdag 9 april 2026 kl. 23:56:07 UTC+2 skrev Olao= luwa Osuntokun:
=
Hi Condution,=C2=A0

So I implemented both variants = of your idea. My intuition was right in that it
doesn't do much to r= educe the size of the=C2=A0final succinct=C2=A0size, but the final
xpriv= variant resulted in a significant reduction in both proving time, and
a= lso memory usage. I also re-ran the original succint proof for the original=
Taproot claim and got a better value for the final proof time (def need= a
better benchmark env+set up!).

Here's a breakdown of the r= esource requirements for the various proofs:
=C2=A0 * Full Taproot
= =C2=A0 =C2=A0 image ID:
=C2=A0 =C2=A0 =C2=A0 8a6a2c27dd54d8fa0f99a332b57= cb105f88472d977c84bfac077cbe70907a690
=C2=A0 =C2=A0 composite:
=C2=A0= =C2=A0 =C2=A0 seal 1797880
=C2=A0 =C2=A0 =C2=A0 prove 49.32s
=C2=A0 = =C2=A0 =C2=A0 verify 0.10s
=C2=A0 =C2=A0 =C2=A0 peak RSS 11907399680
= =C2=A0 =C2=A0 succinct:
=C2=A0 =C2=A0 =C2=A0 seal 222668
=C2=A0 =C2= =A0 =C2=A0 prove 64.30s
=C2=A0 =C2=A0 =C2=A0 verify 0.03s
=C2=A0 =C2= =A0 =C2=A0 peak RSS 11927207936

=C2=A0 * Hardened xpub
=C2=A0 =C2= =A0 image ID:
=C2=A0 =C2=A0 ad4ebc0ef6ce51e0f581cc8d14742a5b97738e9decd3= fe2b0f1746de5bad9617
=C2=A0 =C2=A0 composite:
=C2=A0 =C2=A0 =C2=A0 se= al 513680
=C2=A0 =C2=A0 =C2=A0 prove 14.63s
=C2=A0 =C2=A0 =C2=A0 veri= fy 0.04s
=C2=A0 =C2=A0 =C2=A0 peak RSS 11783503872
=C2=A0 =C2=A0 succ= inct:
=C2=A0 =C2=A0 =C2=A0 seal 222668
=C2=A0 =C2=A0 =C2=A0 prove 17.= 29s
=C2=A0 =C2=A0 =C2=A0 verify 0.02s
=C2=A0 =C2=A0 =C2=A0 peak RSS 1= 1782307840

=C2=A0 * Hardened xpriv
=C2=A0 =C2=A0 image ID:
=C2= =A0 =C2=A0 =C2=A0 8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a3c= 0df0849
=C2=A0 =C2=A0 composite:
=C2=A0 =C2=A0 =C2=A0 seal 234568
= =C2=A0 =C2=A0 =C2=A0 prove 1.98s
=C2=A0 =C2=A0 =C2=A0 verify 0.02s
= =C2=A0 =C2=A0 =C2=A0 peak RSS 3144171520
=C2=A0 =C2= =A0 succinct:
=C2=A0 =C2=A0 =C2=A0 seal 222668
=C2=A0 =C2=A0 =C2=A0 p= rove 2.84s
=C2=A0 =C2=A0 =C2=A0 verify 0.02s
=C2=A0 =C2=A0 =C2=A0 pea= k RSS 3145990144

So we can see that the succinct= proof sizes are all about the same. However the
xpriv variant can be pr= oved directly in just 2 seconds on my machine! It also
requires just 3 G= B of memory for the proof as well.

I've created some additional = supporting documentation to detail exactly what
the new proofs do and th= eir results:

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

=C2=A0 * https://github.com/Roasbeef/bip32-p= q-zkp/blob/1c89fdb398180a2b3eff7761b7f4b233d455c6c9/README.md#reduced-proof= -variants

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


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

-- Laolu

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

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

> I'm amending = my prior suggestion slightly: The circuit (guest program)
> could tak= e 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 ch= ild
> xpub).

That's an excellent insight!

As ment= ioned in my recent reply, with risc0's "succinct" receipt typ= e, I was
able to get the proof size down to 220 KB, at the cost of 3.5x = longer total
proving time.

Your proposal definitely reduces the c= omplexity of the core statement to be
proved, which would speed up the p= roving time for the normal
default/composite receipt 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 proof then the finalsuccinct receipt of either of the proof variants. Based on my current
i= ntuition w.r.t the lower level details, I think the final succinct proofsize would be on the same order of magnitude re size.

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

This line of opt= imization is also more interesting if one were to look at
hand rolling a= custom AIR to avoid the overhead that the RISC-V emulation
adds to the = rirsc0 proof chain, given that it entirely skips doing any EC
operations= at all for the final statement.

----

Re the commit/reveal ap= proach, 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!
<= br>-- Laolu


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

We don't even need t= o do point multiplication in the circuit at all.

I'm amending my prior suggestion slight= ly: The circuit (guest program) could take in an xpriv (e.g. at m/86&= #39;/0'=E2=80=8B) and output a child xpriv (e.g. at=C2=A0= m/86'/0'/0'=E2=80=8B) to the journal (instead of o= utputting a child xpub).=C2=A0

This is safe because remember, EC spending has been di= sabled in this context, and to a quantum attacker, an xpub is computational= ly equivalent to its xpriv. So why bother hiding it? The child xpriv doesn&= #39;t give an observer anything they can't already do with the equivale= nt xpub.=C2=A0

Th= e guest program then is basically the BIP32 CKDpriv algorithm, restricted t= o a single hardened derivation step. The verifier gets the child xpriv, but= can't use it to forge new proofs. Honest verifiers use the xpriv to de= rive the child address(es) as suggested in my last message, to authenticate= spending.
=
Design= ing the guest program like this will massively reduce your circuit complexi= ty, because EC point multiplication is wayyyyy harder for the RISC0 = compiler to arithmetize than a simple hash function. In my prior work with RISC0, I made a gues= t program which ran a SHA256 hash and an EC point multiplication. I found t= hat pruning EC point arithmetic from my guest program improved prover runti= me by a factor of over 100x.

If I am not fever-dreaming and this is indeed possible, then th= e new circuit's complexity will be dominated not by point multiplicatio= n, but by the HMAC-SHA512 call. Our new task is then to figure out how much= we can internally optimize the HMAC-SHA512 call for STARK proving. Here= 9;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=C2=A0

.= ..where in the context of BIP32 hardened CKD, the HMAC key=C2=A0K=E2=80=8B is the chaincode (padded with zeros to 128 bytes) and ms= g =3D (0x00 || sk || i)=C2=A0is the parent secret key and child inde= x.=C2=A0
Since len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we ne= ed a total of 4 SHA512 compression calls:=C2=A0
  1. to compress (K=E2=8A=950x36)=E2=80=8B
  2. to compress the msg=E2=80=8B (and SHA= 512 padding/length)
  3. (K=E2=8A=950x5c), and=C2=A0
  4. a final compression call to tie it all together.=C2=A0
    5. =

<= /div>
The output of that la= st compression call is partitioned into the child chaincode, and a key delt= a which is added to the parent secret key (modulo the curve order), producing the c= hild EC secret key. This last step is arithmetically simple; the SHA512 cal= ls are where most of the arithmetic complexity lies.

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

Note how the parent secret key is the most importa= nt=C2=A0piece for soundness. The circuit needs to prove the parent secret k= ey existed in the hash function preimage, and is correctly related to the c= hild secret key via modular addition. So compression call (2) seems unavoid= able. The 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,=C2=A0I know = a preimage x=E2=80=8B and secret key = sk=E2=80=8B=C2=A0such that:

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

Seeing as the &l= t;something>=E2=80=8B slots are arbitrary, and we know in BIP32 t= hey are always exactly one-block long,=C2=A0it 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 progra= m as secret inputs.=C2=A0The tradeoff is that this=C2=A0permits 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= weakens the verifier's soundness. Ethan Heilman might have opinions on= this, he knows a lot more about attacking hash functions than I do. Intuit= ively, I doubt sampling random SHA512 midstates is that much better than sa= mpling a random HMAC key (chaincode)=C2=A0K=E2=80=8B and compu= ting the resulting midstates.

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


<= /span>
regards,
conduition
On Wednesday, April 8th, 2026 at 12:09 PM, 'conduition' via= Bitcoin Development Mailing List <bitco...@googlegr= oups.com> wrote:
Hi=C2=A0Laolu,

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

It seems to me t= he circuit (guest program) could be simplified. Notice how=C2=A0the guest code computes the entire HD wa= llet key path, including hardened=C2=A0and=C2=A0<= /span>non-hardened derivation steps, and also computes the taproot outp= ut key with key-tweaking. I'd argue these steps are extraneous to the c= ore hard relation you want the STARK to prove, and could be safely removed = to reduce proof size and improve performance.

In r= eality, you needn't go so far as to prove (1)=C2=A0"I know a BI= P39 seed which derives this taproot output key". You need only pro= ve this much more general statement (2):=C2=A0"I know a BIP32 xpriv= which derives this xpub via one or more hardened steps". The latt= er statement (2) still cannot be forged by a quantum adversary even if they= know your account-level xpub, but it entails far less computation to prove= and verify. The rest of the original statement (1) can be done externally = outside the circuit.

Example. If i have a wallet w= ith a taproot address at=C2=A0m/86'/0'/0'/1/= 2=E2=80=8B, I could prove I know the xpriv at=C2=A0m/86'/0'=E2=80=8B which derives the xpub at=C2=A0m/86'/0'/0'=E2=80=8B. Then I provide the remai= ning key path elements /1/2=E2=80=8B in the witness. Note, i= =C2=A0do not=C2=A0mean we=C2=A0derive=C2=A0the x= priv at=C2=A0m/86'/0'=E2=80=8B inside the= guest program. I mean the prover derives=C2=A0m/86'= /0'=E2=80=8B first (in the host), and=C2=A0then = writes that xpriv into the guest program's inputs.=C2=A0The guest p= rogram derives and outputs the xpub at=C2=A0m/86'/0&= #39;/0'=E2=80=8B.=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 s= pending. The verifier thus has confirmed the prover knew an xpriv which (th= rough a hardened derivation step) derives the correct taproot output key.

This change significantly reduces the size of the c= ircuit. From a glance, I see the original guest program performs 6 HMAC-SHA= 512 calls (1 for the master key, 5 for the BIP32 derivation steps), two SHA= 256 compression calls (for the taptweak hash), and two point multiplication= s. 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 exp= ect this will improve your proof size and runtime significantly.
=
This change also makes the circuit more generally applicable= to other rescue contexts. For instance, it could be applied to BIP340 xonl= y keys inside a taproot script tree, or in a P2(W)SH address to an ECDSA pu= blic 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 one would = prefer not to share the account-level xpub on-chain for privacy reasons, th= e proof could be extended to also derive the unhardened child xpub at=C2=A0= /1/2=E2=80=8B inside = the guest program (but we still do not need to do the taproot key tweaking = in the guest program).

We should also t= alk scaling efficiency. Given the cost of STARKs, this style of proof shoul= d be able to authorize spends for more than one UTXO. Say you have a wallet= with 10 different UTXOs held by distinct addresses in the same BIP44 accou= nt. One single STARK proof could authorize spending all 10 of them, by simp= ly committing all 10 input signature hashes into the journal, 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 spen= ds could be validated using the common xpub from the STARK proof's jour= nal.

For a slightly related work proving a similar= relation for hashed addresses, using different STARK technology stacks,=C2= =A0see this delving post.
However, all this said, my personal preference for long-term p= rocrastinator rescue is still for commit/reveal strategies which prove esse= ntially the same statement about BIP32 in a two-step procedure. They get th= e job done with much lighter cryptographic machinery and much smaller witne= sses: a few hundred bytes over two transactions, compared to a few million = bytes in one transaction with STARKs.=C2=A0Boris Nagaev and 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 quantum-safe coins to make the commitment in the first place, so p= erhaps the cost would be worth it to some people? IDK. What do you think of= commit/reveal compared to STARKs for this purpose?
=
regards,
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <<= a rel=3D"nofollow">lao...@gmail.com> wrote:
Hi y'all= ,

I found some spare time this last weekend to dust off a little sid= e project
I started last August: extend TinyGo [1] to be able to produce= RISC-V ELF
binaries capable of being run as a guest on the risc0 platfo= rm to generate
zk-STARK proofs of arbitrary programs. Initially, I didn&= #39;t really have a
clear end target application, it was mainly a techni= cal challenge to force
me to learn a bit more about the RISC-V platform,= and also the host/guest
architecture of risc0. Fast forward ~9 months l= ater, and an initial killer
use case popped into my mind: a zk-STARK pro= of that a Taproot output public
key was generated using BIP-32, via a gi= ven BIP-86 derivation path.

More formally:
```math
\mathcal{R}= =3D \left\lbrace\;
(\overbrace{K,\, C}^{\textsf{public}} ;\; \underbrac= e{s,\, \mathbf{p}}_{\textsf{witness}})
\;\middle|\;
\begin{aligned} K &=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP32Derive}(s,\, \mathbf= {p})\bigr) \\
C &=3D \textsf{SHA256}\bigl(\texttt{"bip32-pq-z= kp:path:v1"} \;\|\; \mathbf{p}\bigr)
\end{aligned}
\;\right\rbra= ce
```

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

I was able to get everything working e2e over the weekend, after= making
some tweaks to my initial architectural game plan!

The TL= ;DR is that:

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

* That works for script path spends, but t= hen leaves all the BIP-86
wallets in a bad position, as they generat= ed outputs that provably
don't commit to a script path at all.
* A 2023 paper (Protecting Quantum Procrastinators with Signature Lifting: A Case Study in Cryptocurrencies [4]) proposed a solution to= this,
namely _seed lifting_ (use BIP-32 as the one-way function to = the
Picnic PQ Signature scheme) to provide a post-quantum proof of s= ecret
information a quantum attacker wouldn't be able to easily = obtain.

* The downside of that is that it reveals the secret BIP 3= 2 seed,
exposing other non migrated UTXOs of a user.

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

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

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

* tinygo-zk= vm: https://github.com/Roasbeef/tinygo-zkvm=
* A fork of TinyGo that supports the flavor of RISC-V (rv32im) = that
risc0 requires to generate/execute a guest program to later b= e proved
by the host.

* risc0: = https://github.com/Roasbeef/risc0
* Mostly a bug fix to their c-= guest example, along with some
additional documentation on how to = get things running. The repo is
unmodified other than that. Recent= updates to the repo made the
entire process much easier (Go guest= +host), more on that later.

* go-zkvm: https://github.com/Roasbeef/go-zkvm
* Go utilities to take a RI= SC-V ELf binary produced by tinygo-zkvm, and
package it in the exp= ected R0BF format, which combines the user
generated RISC-V ELF (t= he thing that is executed to generate the
proof) along with the v1= compat ELF kernel, which is risc0's execution
environment.
=
* This also includes a Go host package, which loads the guest progr= am,
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.

* 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
cla= im/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, 1= 28 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.
* Verifica= tion takes ~1.8 seconds, and uses ~32 MB of memory.

On several layer= s, this demo is far from optimized (more on that later),
this is meant t= o serve as a PoC to demonstrate that with the latest
software+hardware, = a proof of this complexity is well within reach.

For those curious r= e the e2e details I've generated this tutorial that
explains the ent= ire system top to bottom:
https://github.com/Roasbeef/go-zkvm/blob/main/docs/tutorial.md= .

If you got to this point in this mail, and don't care about th= e lower 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 o= ur Universe:
Monitoring the Situation and/or slopfotainment! =F0=9F=AB= =A1

## Motivation + Background

As commonly known, in the case= of an adversary that possesses a quantum
computer capable of breaking c= lassical asymmetric cryptography, any coins
stored in UTXOs with a known= public key are vulnerable. This is the case
for any P2PK outputs from w= aaaay back, and also any other outputs that have
revealed their public k= ey. Pubkey reveal might happen due to address re-use
(spending from the = same script twice), or Taproot outputs, which publish
the public key pla= inly in the pkScript.

As detailed in [3], for Taproot outputs, a wid= ely 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 wa= s shown to be binding even
under classic assumptions, as H(M) (tapscript= merkle root) is still a
collision-resistant function.

That means= any UTXO that _does_ commit to a script path has a future escape
hatch = _if_ such a softfork would need to be deployed in the future.
However, w= hat about all the other wallets that use BIP 86, and don't commit
to= a script path at all? Under a strict version of this existing
proposal,= those wallets would basically be locked forever.

The goal of this w= ork is to demonstrate a practical solution (discussed
against devs, but = never implemented AFAICT): generate a zk proof that an
output was genera= ted using BIP-86. For the zk-Proof, we select zk-STARKs,
as they're = plausibly post quantum since they rely only on symmetric
cryptography: l= ayers of merkle trees over an execution trace, along with
some novel sam= pling/error-correction algorithms.

At this point, you may be asking:= "if the quantum adversary can derive the
private key to a random t= aproot public key, then how exactly does this
help?". The answer li= es 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 k= eyed by "Bitcoin seed" to produce the master extended 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&= quot;, 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 proportional 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. Ther= efore, if you generated a wallet using
BIP-32, you possess _another_ sec= ret that a quantum adversary can't
efficiently reconstruct!

T= his demo focuses on the Taproot case, but the rough approach also appliesto 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 gen= erated
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 Bi= tcoin 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 wall= et.

## TinyGo + RISC-V + risc0

Now for some of the lower leve= l 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), executes
that in a host environment, g= enerates a trace, then produces a STARK proof
from that.

Today yo= u can take some subset of Rust, compile it to an ELF using their
toolcha= in, then execute it, generate a trace, to finally prove+verify it
using = their system.

This demo took a bit of a round about journey to achie= ve this, as after
all, the journey is most of the fun, ain't it!
=
For the past 10 years or so, my Bitcoin stack of choice (lnd/btcsuite) = uses
a series of Go libraries, so I wanted to be able to re-use them, fi= rst for
this demo, then also in the future for other projects.

Ti= nyGo is a special Go compiler based on LLVM, that targets mostly embeddedenvironments. You can use it to generate go programs that can run on
m= icro controllers, or on web assembly (producing a smaller binary than ifyou used the normal stdlib path).

TinyGo supports RISC-V, but _not_= the 32-bit variant of RISC-V that risc0
relies on. So the first step he= re was to create a new target definition for
TinyGo: riscv32-unknown-non= e, which uses base integer + multiply/divide
instructions with no compre= ssed instructions, which uses 4 KB stacks for
each task. From there, I c= reated a new linker script
(`targets/riscv32im-risc0-zkvm-elf.ld`) which= created a memory layer
identical to what risc0 expects. The final compo= nent was a new runtime
(`src/runtime/runtime_zkvm.go`), which implemente= d a few platform specific
syscalls for risc0 (putchar(), exit(), ticks()= , and growHeap()).

When I tried to get this working last year, I had= to also implement a number
of kernel syscalls (called ecalls in the pla= tform [7]) to handle: read+write
to stdin/stdout, halting, and the journ= aling mechanism (the transcript of
execution committed to), which basica= lly implement the kernel that the guest
executes in. Fast forward to 202= 6, and after pulling the latest version of
the repo, I realized that the= y now make a libzkvm_platform.a, which packages
up the kernel nicely to = be linked against. So I threw out my custom kernel
code, and slotted tha= t in instead.

The final component is a C FFI layer that enables me t= o use _both_ a Go
guest (the program to be proved) and a Go host (the th= ing that executes the
program and generates the final proof).

## = BIP-32+Taproot zk-STARK Proof

With basic proofs working (like the cl= assic: I know the factorization of a
number `n`), I was unblocked to gen= erate the actual proof. The claim/proof
is represented with the followin= g JSON artifact:
```
{
"schema_version": 1,
"= ;image_id": "8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077= cbe70907a690",
"claim_version": 1,
"claim_fla= gs": 1,
"require_bip86": true,
"taproot_outpu= t_key": "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f99= 2b288ee6",
"path_commitment": "4c7de33d397de2c231e= 7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b",
"journal_hex= ": "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4= f92f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56= de11f74b",
"journal_size_bytes": 72,
"proof_s= eal_bytes": 1797880,
"receipt_encoding": "borsh&qu= ot;
}
````

The `image_id` is basically a hash of the ELF, so y= ou know what the prover
executed. There are then a few flags that contro= l 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-4= 4 path, you can instead opt to
claim that instead. The Taproot key we= 9;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 `pat= h_commitment`, which is a commitment to the
exact BIP 86 path that the p= rover used. Finally, we also commit to the
journal hex, which is basical= ly a commitment to the public claim.

Assuming you've built the p= roject, then you can generate the proof (even
passing in an arbitrary BI= P-32 seed and derivation path with)
```
make prove GO_GOROOT=3D/path/= to/go1.24.4
```

Then verify it with:
```
make verify GO_GOR= OOT=3D/path/to/go1.24.4
```

The default prove target writes:
= * ./artifacts/bip32-test-vector.receipt
* ./artifacts/bip32-test-vect= or.claim.json

The receipt is the STARK proof artifact. claim.json is= the stable,
human-readable description of the public statement being pr= oved.

## Application to a Future Keyspend Disabling Soft fork
As mentioned above, assuming the community is forced to deploy a keyspend<= br>disabling soft fork in the future, we can also deploy some variant ofthis proof to enable both BIP-86 wallets, and also any BIP-32 wallet, tosweep their funds into a new PQ output.

In 2026, we've shown t= hat this is achievable using 2 year old consumer
hardware. I don't d= oubt that the upcoming advancements (eg: photonics, new
flavor of high b= andwidth memory, etc) in hardware (driven by the fierce AI
race) will ma= ke such a proof even more feasible.

One thing to note is that this p= roof has a few layers of indirection,
mainly the RISC-V layer that adds = overhead which increase the total amount
of steps, and therefore the siz= e of the proof. A production grade
deployment would likely instead hand = roll a custom STARK proof for this
exact statement, to achieve a faster = and smaller proof).

# Future Work

In terms of future work, th= ere're a number of interesting following up
projects that can be pur= sued from here.

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

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

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

2. Second right= now, the entire claim is a single proof. Instead, we can
first brea= k that up using their recursive proof/composition syscalls:
sys_veri= fy_integrity+sys_verify_integrity2. We can then assembled a
series o= f these proofs into a _single_ statement, which can save block
space= by aggregating N proofs into a single proof.

-- Laolu

[1]: <= a href=3D"https://tinygo.org/" rel=3D"noreferrer nofollow noopener" target= =3D"_blank">https://tinygo.org/

[2]: https://riscz= ero.com/

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

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

[5]: https://microsoft.git= hub.io/Picnic/

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

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

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+...@googlegroups= .com.
To view this discussion visit https://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 &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+...@googlegroups= .com.
To view this discussion visit https://groups.google.com/d/msgid/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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/bd1f1379-fffa-4a93-a747-c449c2f7265cn%40googlegrou= ps.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/CAO3Pvs8ErTm%2Bzxx4bkF5F-22pt%2BuFzY6S6CdLsn04sS3Tvcmrg%= 40mail.gmail.com.
--000000000000d4d3ec06508ef8e9--