From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 28 Apr 2026 18:02:56 -0700 Received: from mail-oa1-f59.google.com ([209.85.160.59]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wHtKI-0004lt-AO for bitcoindev@gnusha.org; Tue, 28 Apr 2026 18:02:56 -0700 Received: by mail-oa1-f59.google.com with SMTP id 586e51a60fabf-42393e9b4aesf10501914fac.0 for ; Tue, 28 Apr 2026 18:02:54 -0700 (PDT) ARC-Seal: i=3; a=rsa-sha256; t=1777424568; cv=pass; d=google.com; s=arc-20240605; b=ddmKQuhTLxo80b4R/zJod3x11DKjlz/k3PPb8isMDshkhczCkeikJxc+D2KApCIxaV 6P+M2iJg2mOuzphd0ZSpwfblVVec0Q2RfQQ6NsOfvt2zP5XE9r8C7xbtsT+A4rs9bGUC MkmfOTvIPTQFhhgIpYE7/QngKx/dmIwpWD+23R9KF8ziTHmk8CiFgKipSSn8O8UtAGV9 PQ71f4QobtJ/QQQkGIba89Ai7ixlhVCDKXh2jzRmTsUU12RSvKr6csnxTCkinrPrkOhy Ofkm9A4eOdoMkXHbeq6s9Bxcmkfr70jZIqqwZt31N7LA9z5k/6BL0/wOQzF7sz4wRDa3 G/7A== 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:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=6ErX254/CjnmQHPFdJd5YG/EsVNewQigTeZlO0SJ8CI=; fh=GNOWbHRpPlDSecw1vNBgK+t1PEQfyymbYRgKgDWiXSI=; b=KqJZGWXw0zMOK93NoFAu0+kdDZvU9j5B4BX1m3QgyIJ5eEwEeSnzIfi4nxpJE6IU9p LnZUi8S1biDvXUHiDiQvdcsLyngSXZsgVbS1xkpvahgpjXyxar6pKJ/OnCtC7ZIomZL/ w13o+7q/sMbSJdbgilWs/swONCPhBIMUy36lP2fUcdG2EW6JjoRjS/xgxu4mNW6djvTC yXz2XIxJcyQJoJXeyyX+GxDyvr1DvXwiv1NHC4BLpBBXX8BeAx4mQu67t/bwdQT64NZS sLdDroUqn4cVgG4FfAiXi9xcEUdQIKnWj8cO7fL6VlqUDBkidIa2Im4K3ELlk6Ll4vzQ 0GDw==; darn=gnusha.org ARC-Authentication-Results: i=3; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=HnhnxBON; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b129 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=1777424568; x=1778029368; 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:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=6ErX254/CjnmQHPFdJd5YG/EsVNewQigTeZlO0SJ8CI=; b=eyP6qBfBDy699qtRE2r0lLlP/Hj0AwWeYjSixN5LZ1KqEsqAIO+edzsZ3xBcXhYSAQ 6vhgRYfyssTSUD1DvoZyYDOlRdVw65I10qM96Qz0oMCLtfIgOdfqLh2Fr2C94N4y1JJO lnwgEbTNNBcCsIhp6rgt+R69GPmnC5jHneMscLhAlVpJ28eGcL8hwlKuXAF+tu+2yWEY PPggaYGyyAHh1OX7Bb/zk+Mv4itaLp5yY79IQgQoUjJkU3QtUT1d+KntULJcLxX0Id8o Pfk0dP+2vej+hR+hiteoUsz7+5M1htqPFD4EDQDtxe64Tfr5NAPrm1RGtFaMZ9KAckMf hx5A== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1777424568; x=1778029368; 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:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=6ErX254/CjnmQHPFdJd5YG/EsVNewQigTeZlO0SJ8CI=; b=PBvnYyTORZXb9mB/RqfOnFMX/KhC/5uHCTJ1Gk1MDbr1z2Lrfon6o65qOjjzK0Q1kB OBbrGb3B4tnnn1bqYzDglBXQo+XnwfILI4rKxnVsq2nwO8uj7IwubjlkBO39efSyPa6v lmFqVcWFnBOTG4+BKd8Xv3QeNcTShf9cZUL3+5V7RAXYCoelkRGvleyULc51nFG/boXd i3iqey0O6+mOdfsWvbYc5ZBoW5UQH1nVNB2yw5iHuj56F+qG2J3dyOaKkP1sabWwY0ot EIH9iEpsVnRCFmNF6KMlLMS9wjhcmVtyF/nVRXK8pUFTGZ154GXC9efvWThu+It03pIF Vc9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777424568; x=1778029368; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender: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=6ErX254/CjnmQHPFdJd5YG/EsVNewQigTeZlO0SJ8CI=; b=EdIA3MzEPi4z4AciBB7Zp6FrYUC4uFaO4/VR0YlS9NqXDb4v29yVP3WwrHUQ9R+apW adn6H1cAi5WMIUQNhPL3mf9gQEhK5QU+763yf1nWxUShCsGOljFV4L8sf8r5z7W+bJEd H4diFNN3OEZ9O6tuTjZracuaTpDSJpgUpCHd34vbBgQChPjXnA5HcNdTqesG2QF/TSAP uovJe6o04ZD8WCs6P5OtilR+y9GxewfDbGrYhRAiaprEFw8u8L8xdWKiozIn6JBgoajb vnvo+PpyhfiutviYxmIGvN3316ACx/R/LO+U+4p3watfDAJL8pX6GvCeq64NqwDo8oB5 DrZQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=3; AFNElJ85oSfXnPT1UP8QruWypm1YRHpojhKUlwhHG9qbHiDUlhpl72Zpnn1RgfpH1De+juUas6hNsNGfjoVf@gnusha.org X-Gm-Message-State: AOJu0YxvPrQ3LOHLfMVcC0o9Ib2f5sB3kc/n8emkPRY968Bk2JjUfyGR axhIayx5XiwfDsl1tbSVwau+uIC1/s6JYQW1DkqGT4I+ge37nJ3LlaR8 X-Received: by 2002:a05:6871:890:b0:42f:d844:7d0b with SMTP id 586e51a60fabf-433f3877800mr2999586fac.6.1777424567965; Tue, 28 Apr 2026 18:02:47 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AUV6zMPQ/ZMoSqSBwMzyUwK7tUEfDzchJM+9KRLd+wl/HM4fXw==" Received: by 2002:a05:6870:4d4:b0:41c:583a:b50 with SMTP id 586e51a60fabf-4280c61dc27ls4393935fac.1.-pod-prod-04-us; Tue, 28 Apr 2026 18:02:42 -0700 (PDT) X-Received: by 2002:a05:6808:f8e:b0:479:dc28:b71f with SMTP id 5614622812f47-47c2914132cmr2749452b6e.40.1777424562388; Tue, 28 Apr 2026 18:02:42 -0700 (PDT) Received: by 2002:a05:690c:3687:b0:7ba:f5aa:4ab8 with SMTP id 00721157ae682-7baf5aa5779ms7b3; Tue, 28 Apr 2026 17:58:42 -0700 (PDT) X-Received: by 2002:a05:690e:1289:b0:651:b7e7:eff3 with SMTP id 956f58d0204a3-65beed93be7mr5067715d50.19.1777424322185; Tue, 28 Apr 2026 17:58:42 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1777424322; cv=pass; d=google.com; s=arc-20240605; b=BndiZ85Wu5+TXyRtHEewRObG5tPeVRTFDAvYPRMOTF0CiXQ9ufm8dO43/4Jo9CrXaO 7/1YeuZTxafhh3G9snv9bU4AcVcrDINBayMHVwwehiUV6EioyU8uGrpnHB85cZ3fWlDn 6bnKFFUKpPNl8ytpUT2WpZzN/VWUYQRTqWC+qcLKkZVPx0xWQ1X0nY1vjmwgdBybImvM eoygnBKUauQkI2ggrzVBnK0rlrI9KcFyF/oVZkHQLgnyNxHsnX3+lA/KiAVIoc76okng Zz189E5qhHDnDWWxl3tfv2hLnCfBJxG7W+ydNwL7jJVsNVY7/OTsHuV8bODV9neojl6K 8q1A== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :dkim-signature; bh=3gXS2FoiscIU7rw6YP46P2xwPfXF7WisiEPdm+9HztM=; fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=; b=PEk5kAeq7h7s7MsJ5S0zwK55L6jPYf6tbcy9Zqy3VKQ/cuMRDnVmMKHd1c45/3NCg7 0r0gYTKczNjb42MCx+NeJaPjMPt4Us2B00Rn4fYBuQ/eKH0ytAXMPwj4N/sjBmW7H+ZK BmlSK3sZHAnKj0FbBD6UlbdfN8bMMc8ALIiUqdFV1EJi09n0zGCgRy78h5dXbCGoUG90 +aIgEtAl4p6au+RvjrsLqd+znf3mcT3pxJL9tGVcZ0HS9oZDRKr4xWNMH2xJnPSPOAd8 1EeAD1sQjKxp83eFR5zBCX2nloVp8LbodSgO6Id5b25QW2YPWKGOo4ZSaexeRpUhMVdf V/Qg==; dara=google.com ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=HnhnxBON; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b129 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-xb129.google.com (mail-yx1-xb129.google.com. [2607:f8b0:4864:20::b129]) by gmr-mx.google.com with ESMTPS id 956f58d0204a3-65bff82a657si23373d50.7.2026.04.28.17.58.42 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 28 Apr 2026 17:58:42 -0700 (PDT) Received-SPF: pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b129 as permitted sender) client-ip=2607:f8b0:4864:20::b129; Received: by mail-yx1-xb129.google.com with SMTP id 956f58d0204a3-6501418152cso11615112d50.0 for ; Tue, 28 Apr 2026 17:58:42 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1777424321; cv=none; d=google.com; s=arc-20240605; b=UXc9zJXMPW2ROePHHiQQJqUZdrFU+TCLGUSS2KWzVfvjKIv1vBV6KYx1ojfdbiTgCb vECaWEWe2F3kg5irubq7ax3MukLd5Xls3OQYU6neyJL9wEDk73fpwMGYzJeFvzOdt7Jl IrDutB6FBkwdJhsnpjka53g3ml3myJd9nWQ4QBdiYRV1HG4mo6JfXzX3rBVRW1bpD9wa XkRjM503rB9G47xnb9ku8C3xZ8pk+NuX2TrdEITWCgPZ5VgFrnE4Hj4KqaMQurajSnMu 1OdtmbosOQx1FF/bF/KgA28jmaZmyH6lrtmbukvHGW1u1L7rrmKwPDFnspH37GbH13gb 9xKA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :dkim-signature; bh=3gXS2FoiscIU7rw6YP46P2xwPfXF7WisiEPdm+9HztM=; fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=; b=WhYwwxba9PQRtznOYAZq6vT5p78kMyyeXGlWLPc523IEcW/v9ZlKmJQhVZLQolmfSq fjH77BlFo/PLLEO95HdlIvfteNm6jspuRniy5qqKwLyM6WaJ36VKrajfFpn7x4mPNQ4h r8/FhcX1mBwPu7spxe9aunLJrZk5vXgPvBtRaR4EvibcKXvoqPTHGechIGQhceLnQ7eB iWukC0JEfsaaEq3XfK/SjGbTXgDhdVEfHX/HEMv2VuKBNsv7W8F9c/tayOU27l/eUIbd EdGuEr464Mcy2cifB1ADvYsmLgPDEprXfaK3BmI77TUw2eGWvX3TH16Z6+/oxrrcqkCR zBVA==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; arc=none X-Gm-Gg: AeBDieuOS7DDP0rWzD+t81BSMgla8kPHQn+OWcQ/zrixz6RvO/66fPTB5JEKvZjp5/a f9HRlli3P5o2Q8pqwAhRH5rNV/qifwWCyE9YB5/Uo7Ykahmf8T0Yv+EloUHlTIIWEg2vSvTF07v Jh9417R+S3HI4vrtZevAvbfHgeCsX8sArmLdhL+brPdkuxJOAUKfCcr6UoTiY6jXdl8kre3hP3Y 7Z3pnC6Z0NDokx8sHllDO6hkAO3JefW7UxyL1XvNt/EcCO23Uh4LSLJAqDAWME1wIjpvrq2HvR8 2e8TUcMpa2khhgZFIMSMKy0md59gPpesT1QBKTl/aJHYfizRk7U= X-Received: by 2002:a05:690e:140f:b0:651:8abe:ce65 with SMTP id 956f58d0204a3-65beed9381bmr5362361d50.18.1777424319702; Tue, 28 Apr 2026 17:58:39 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Olaoluwa Osuntokun Date: Tue, 28 Apr 2026 17:58:28 -0700 X-Gm-Features: AVHnY4KC_ZQsInAKWRwaD2dnF5kZ_c3f-HkGJzm_QCKSpujjcRkP0kLaSE6B8xw Message-ID: Subject: [bitcoindev] Re: Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge To: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="00000000000030ec8f06508ed9e7" 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=HnhnxBON; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b129 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 (/) --00000000000030ec8f06508ed9e7 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi y'all, Bit of a late update, but a few weeks ago, after some prodding on Twitter b= y instagibbs, I extended the demo to ask cover batch+incremental proof aggregation. This is important as it enables an untrusted 3rd party to aggregate several proofs into one, potentially saving a massive around of block space. For this, we continue to leverage risc0's "succinct" receipt type (uses a special recursion circuit [2] to make an effectively constant sized proof of ~200 KB), which means that no matter how many proofs are aggregated, the _final_ proof is still ~200 KB. The magic that makes this work is a special batch verified guest program that: * reads as input in a series of claims (fixed size output of a proof) * uses the risc0's recursion gadget to assert that they're all valid proofs * then finally constructs a merkle tree (sha2 right now, likely faster if Poseidon used) that commits to each claim * outputs a new batch proof claim Given a series fixed sized claims (eg: could be part of the annex in a future transaction), a verifier can verify the aggregated proof, then verify that after manually reconstructing the merkle tree, the claimed hash matches up (similar to wtxid commitment validation). Alternatively, if all the claims aren't available, one could receive a merkle proof of an individual claim (proving that the statement was part of the proved batch). For those curiou= s about lower level details, see this doc [3]. Heterogeneous claim aggregation is supported (combine both distinct leaves and another batch root). This means that all the statements aggregated don't need to be _identical_. Instead, the claim just needs to be known by the special guest program that does the proof aggregation [1]. This would permit the original bip-32 taproot proof to be aggregated with Conduition's xpriv/xpub claims, and any other rescue proofs we devise in the future (eg: Electrum's seed format [4]). One downside with the current scheme is that each time an existing batch and a new leaf are aggregated, the total size of claim tree grows, requiring more bytes to prove final inclusion of a leaf. Here's an example to illustrate this quirk: * Claims {a, b, c} are aggregated into a merkle tree X =3D {a, b, c} * A new claim d, is then aggregated with that tree X, giving us tree Z = =3D {d, X} * This additional layer now adds extra intermediate branches to the merkl= e proof that claim a was properly included. I sketched out two alternative approaches in the repo, namely consideration of switching to either a Sparse Merkle Tree (SMT), or a Merkle Mountain Range (MMR) [5][6]. Finally, here's some initial perf numbers [7]. These results focus on just flat aggregation, so aggregating a series of leaves into a new root: * aggregating 2 leaves: * prove time: 5 seconds * prover RAM: 3 GB * verify time: 20 ms * aggregating 4 leaves: * prove time: 9 seconds * prover RAM: 6 GB * verify time: 20 ms * aggregating 8 leaves: * prove time: 17 seconds * prover RAM: 11 GB * verify time: 40 ms * aggregating 16 leaves: * prove time: 33 seconds * prover RAM: 11 GB * verify time: 40 ms The cool thing about this architecture is that it's basically a zk Map Reduce. The batch aggregation can be done on many machines/cores in parallel, with aggregation happening in chunks. Aggregation could even first occur on the input/transaction level as well. [1]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/batch-merkle-system= .md [2]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/recursive-proving.m= d [3]: https://github.com/Roasbeef/bip32-pq-zkp/blob/d6e9ee2f806f69c4307eeed9394aa= a8ac4beaabe/guest_batch/main.go#L61-L70 [4]: https://electrum.readthedocs.io/en/latest/seedphrase.html [5]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/mmr-accumulator-ske= tch.md [6]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/sparse-accumulator-= plan.md [7]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/batch-aggregation.m= d#scaling-results -- Laolu On Thu, Apr 9, 2026 at 1:33=E2=80=AFPM Olaoluwa Osuntokun wrote: > Thanks to Luke Childs, I was able to reduce the size of the proof from 1.= 8 > MB, > to 200 KB. The trade off is that it now takes round 180 seconds to prove > vs 50 > seconds. The space optimization vector here is utilizing a layer of > recursion, > so first the main proof is generated, then a proof that a verified would > accept > _that_ proof is generated. IIUC, this can be used to compress a proof a > high > complexity into an effectively constant sized statement of proof > acceptance. > > Relevant commits for the curious: > * > https://github.com/Roasbeef/go-zkvm/compare/f691458110b6b551a20ab36d15de9= 8dfb6813d8c...77420055510acfc2f0bee2dcf2313365dee927e8 > * > https://github.com/Roasbeef/bip32-pq-zkp/compare/aae0a1a763eed6bfab8660bc= fb8f938f91b10c10...4dcb731e4fc97f84e52c85d2768dc41612c71027 > > > I added some sketch notes to the repo re constructing an aggregated proof > via > composition of a merkle tree of individual statements (would enable a > single > proof in a block for all the statements): > > https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/claim.md#future-r= ecursive-composition-sketch > . > > -- Laolu > > On Tue, Apr 7, 2026 at 8:39=E2=80=AFPM Olaoluwa Osuntokun > 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 EL= F >> binaries capable of being run as a guest on the risc0 platform to genera= te >> zk-STARK proofs of arbitrary programs. Initially, I didn't really have a >> clear end target application, it was mainly a technical challenge to for= ce >> me to learn a bit more about the RISC-V platform, and also the host/gues= t >> architecture of risc0. Fast forward ~9 months later, and an initial kill= er >> 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$ is >> the >> BIP-32 seed, and $\mathbf{p}$ is the derivation path. >> >> >> I was able to get everything working e2e over the weekend, after making >> some tweaks to my initial architectural game plan! >> >> The TL;DR is that: >> >> * Given that the Taproot commitment scheme is post-quantum secure [3], >> in >> the future we can deploy a soft fork to _disable_ the keyspend path, >> and force all Taproot spends to instead flow through the script path >> (not my idea, commonly discussed amongst developers, not sure who >> proposed it first). At that point, Taproot starts to resemble BIP-36= 0. >> >> * 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 t= o >> 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 secre= t >> 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 >> safe >> exit path in case they don't bother moving their coins in time to th= e >> yet-to-be-decided post quantum signature scheme. >> >> To achieve this end, I needed to create/fork a series of repos: >> >> * tinygo-zkvm: https://github.com/Roasbeef/tinygo-zkvm >> * A fork of TinyGo that supports the flavor of RISC-V (rv32im) that >> risc0 requires to generate/execute a guest program to later be >> proved >> by the host. >> >> * risc0: https://github.com/Roasbeef/risc0 >> * Mostly a bug fix to their c-guest example, along with some >> additional documentation on how to get things running. The repo is >> unmodified other than that. Recent updates to the repo made the >> entire process much easier (Go guest+host), more on that later. >> >> * go-zkvm: https://github.com/Roasbeef/go-zkvm >> * Go utilities to take a RISC-V ELf binary produced by tinygo-zkvm, >> and >> package it in the expected R0BF format, which combines the user >> generated RISC-V ELF (the thing that is executed to generate the >> proof) along with the v1compat ELF kernel, which is risc0's >> execution >> environment. >> >> * This also includes a Go host package, which loads the guest progra= m, >> 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 t= o >> the _The Net of a Million Lies_, or as better known in our Universe: >> Monitoring the Situation and/or slopfotainment! =F0=9F=AB=A1 >> >> ## Motivation + Background >> >> As commonly known, in the case of an adversary that possesses a quantum >> computer capable of breaking classical asymmetric cryptography, any coin= s >> stored 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 publish >> the public key plainly in the pkScript. >> >> As detailed in [3], for Taproot outputs, a widely circulated plan is >> roughly to: disable the _keyspend_ path (requires a simple signature), >> enforcing a new rule that all Taproot spends must then flow through 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 bindi= ng >> 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 (discussed >> 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 with >> some novel sampling/error-correction algorithms. >> >> At this point, you may be asking: "if the quantum adversary can derive t= he >> 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 priva= te >> key. An adversary who wants to forge this proof needs to find a >> _colliding_ >> seed: a different seed s' such that HMAC-SHA512("Bitcoin seed", s') >> produces >> the same master key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) is the >> best known quantum collision finder, and it runs in time 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 usi= ng >> 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 appli= es >> to any other output generated via BIP-32. BIP 32 was originally publishe= d >> in >> 2012, over 14 years ago. So safe to say that _most_ wallets were generat= ed >> 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 s= ay >> 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 wa= nt >> to consider migrating them to a BIP-32 wallet. >> >> ## TinyGo + RISC-V + risc0 >> >> Now for some of the lower level details. risc0 is a STARK based proving >> system that takes a RISC-V ELF binary generated by a guest program (any >> program generating using their flavor of rv32im can be proved), executes >> 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 finally prove+verify it >> using their system. >> >> This demo took a bit of a round about journey to achieve this, as after >> all, the journey is most of the fun, ain't it! >> >> For the past 10 years or so, my Bitcoin stack of choice (lnd/btcsuite) >> uses >> a series of Go libraries, so I wanted to be able to re-use them, first f= or >> 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 i= f >> you used the normal stdlib path). >> >> TinyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V that risc= 0 >> 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 for >> each task. From there, I created a new linker script >> (`targets/riscv32im-risc0-zkvm-elf.ld`) which created a memory layer >> identical to what risc0 expects. The final component was a new runtime >> (`src/runtime/runtime_zkvm.go`), which implemented a few platform specif= ic >> 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 o= f >> 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 >> packages >> up the kernel nicely to be linked against. So I threw out my custom kern= el >> code, and slotted that in instead. >> >> The final component is a C FFI layer that enables me to use _both_ a Go >> guest (the program to be proved) and a Go host (the thing that executes >> 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/pro= of >> 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": >> "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f9= 92b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de11f74b", >> "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 prov= er >> 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 adopte= d >> post-Taproot, so if you have an existing BIP-44 path, you can instead op= t >> to >> claim that instead. The Taproot key we're generating the proof against i= s >> 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. >> >> Assuming you've built the project, then you can generate the proof (even >> passing in an arbitrary BIP-32 seed and derivation path with) >> ``` >> make prove GO_GOROOT=3D/path/to/go1.24.4 >> ``` >> >> Then verify it with: >> ``` >> make verify GO_GOROOT=3D/path/to/go1.24.4 >> ``` >> >> The default prove target writes: >> * ./artifacts/bip32-test-vector.receipt >> * ./artifacts/bip32-test-vector.claim.json >> >> The receipt is the STARK proof artifact. claim.json is the stable, >> human-readable description of the public statement being proved. >> >> ## Application to a Future Keyspend Disabling Soft fork >> >> As mentioned above, assuming the community is forced to deploy a keyspen= d >> 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, n= ew >> 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 adds overhead which increase the total amou= nt >> of steps, and therefore the size of the proof. A production grade >> deployment would likely instead hand roll a custom STARK proof for this >> exact statement, to achieve a faster and smaller proof). >> >> # Future Work >> >> In terms of future work, there're a number of interesting following up >> projects that can be pursued from here. >> >> One basic one is that the current proof doesn't actually commit to a >> spending txid and/or sighash. That can be trivially incorporated into th= e >> proof. Going a step further, the execution of the guest program can even >> _generate_ a valid schnorr signature to permit spending. >> >> Looking to the memory+computational requirements necessary to generate t= he >> 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 th= e >> syscalls/precompile in the risc0 env for big integer arithmetic: >> sys_bigint and sys_bigint2. With this, the guest calls into the kern= el >> to use an optimized/accelerated circuit for the modular arithmetic, >> reducing cycles, steps, and thus proof size. >> >> 2. Second right now, the entire claim is a single proof. Instead, we ca= n >> first break that up using their recursive proof/composition syscalls= : >> sys_verify_integrity+sys_verify_integrity2. We can then assembled a >> series of these proofs into a _single_ statement, which can save blo= ck >> 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 >> >> --=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/= CAO3Pvs-ToXzNDRUa3ZtnEz2t1CN-nPG-8Xt5wNmRE%2BR6Dy1fVQ%40mail.gmail.com. --00000000000030ec8f06508ed9e7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi y'all,

Bit of a late update, but a few = weeks ago, after some prodding on Twitter by
instagibbs, I extended the = demo to ask cover batch+incremental proof
aggregation.

This is im= portant as it enables an untrusted 3rd party to aggregate several
proofs= into one, potentially saving a massive around of block space. For this,we continue to leverage risc0's "succinct" receipt type (use= s a special
recursion circuit [2] to make an effectively constant sized = proof of ~200 KB),
which means that no matter how many proofs are aggreg= ated, the _final_ proof is
still ~200 KB.

The magic that makes th= is work is a special batch verified guest program that:
=C2=A0 * reads a= s input in a series of claims (fixed size output of a proof)
=C2=A0 * us= es the risc0's recursion gadget to assert that they're all valid pr= oofs
=C2=A0 * then finally constructs a merkle tree (sha2 right now, lik= ely faster if
=C2=A0 =C2=A0 Poseidon used) that commits to each claim=C2=A0 * outputs a new batch proof claim

Given a series fixed sized= claims (eg: could be part of the annex in a future
transaction), a veri= fier can verify the aggregated proof, then verify that
after manually re= constructing the merkle tree, the claimed hash matches up
(similar to wt= xid commitment validation). Alternatively, if all the claims
aren't = available, one could receive a merkle proof of an individual claim
(prov= ing that the statement was part of the proved batch). For those curious
= about lower level details, see this doc [3].

Heterogeneous claim agg= regation is supported (combine both distinct leaves and
another batch ro= ot). This means that all the statements aggregated don't need
to be = _identical_. Instead, the claim just needs to be known by the special
gu= est program that does the proof aggregation [1]. This would permit the
o= riginal bip-32 taproot proof to be aggregated with Conduition's xpriv/x= pub
claims, and any other rescue proofs we devise in the future (eg: Ele= ctrum's
seed format [4]).

One downside with the current schem= e is that each time an existing batch and a
new leaf are aggregated, the= total size of claim tree grows, requiring more
bytes to prove final inc= lusion of a leaf. Here's an example to illustrate this
quirk:
=C2= =A0 * Claims {a, b, c} are aggregated into a merkle tree X =3D {a, b, c}=C2=A0 * A new claim d, is then aggregated with that tree X, giving us tre= e Z =3D {d, X}
=C2=A0 * This additional layer now adds extra intermediat= e branches to the merkle
=C2=A0 =C2=A0 proof that claim a was properly i= ncluded.

I sketched out two alternative approaches in the repo, name= ly consideration of
switching to either a Sparse Merkle Tree (SMT), or a= Merkle Mountain Range
(MMR) [5][6].

Finally, here's some ini= tial perf numbers [7]. These results focus on just flat
aggregation, so = aggregating a series of leaves into a new root:
=C2=A0 * aggregating 2 l= eaves:
=C2=A0 =C2=A0 * prove time: 5 seconds
=C2=A0 =C2=A0 * prover R= AM: 3 GB
=C2=A0 =C2=A0 * verify time: 20 ms

=C2=A0 * aggregating = 4 leaves:
=C2=A0 =C2=A0 * prove time: 9 seconds
=C2=A0 =C2=A0 * prove= r RAM: 6 GB
=C2=A0 =C2=A0 * verify time: 20 ms

=C2=A0 * aggregati= ng 8 leaves:
=C2=A0 =C2=A0 * prove time: 17 seconds
=C2=A0 =C2=A0 * p= rover RAM: 11 GB
=C2=A0 =C2=A0 * verify time: 40 ms

=C2=A0 * aggr= egating 16 leaves:
=C2=A0 =C2=A0 * prove time: 33 seconds
=C2=A0 =C2= =A0 * prover RAM: 11 GB
=C2=A0 =C2=A0 * verify time: 40 ms

The co= ol thing about this architecture is that it's basically a zk Map Reduce= .
The batch aggregation can be done on many machines/cores in parallel, = with
aggregation happening in chunks. Aggregation could even first occur= on the
input/transaction level as well.

[1]: htt= ps://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs/batch-merkle-system.md=

[2]: https://github.com/Roasbeef/bip32-pq-zkp/blo= b/main/docs/recursive-proving.md

[3]: https://github.com/Roasbeef/bip32-pq-zkp/blob/d6e= 9ee2f806f69c4307eeed9394aaa8ac4beaabe/guest_batch/main.go#L61-L70
[4]: https://electrum.readthedocs.io/en/latest/seedphrase.html

[5]:= https://github.com/Roasbeef/bip32-pq-zkp/blob/main/docs= /mmr-accumulator-sketch.md

[6]: https://gith= ub.com/Roasbeef/bip32-pq-zkp/blob/main/docs/sparse-accumulator-plan.md<= br>
[7]: https://github.com/Roasbeef/bip32= -pq-zkp/blob/main/docs/batch-aggregation.md#scaling-results

-- L= aolu



=
On Thu, Apr 9, 2026 at 1:33=E2=80=AFPM Olaoluwa Osuntokun <<= a href=3D"mailto:laolu32@gmail.com">laolu32@gmail.com> wrote:
= Thanks to Luke Childs, I was able to reduce the size of the proof from 1.8 = MB,
to 200 KB. The trade off is that it now takes round 180 seconds to p= rove vs 50
seconds. The space optimization vector here is utilizing a la= yer of recursion,
so first the main proof is generated, then a proof tha= t a verified would accept
_that_ proof is generated. IIUC, this can be u= sed to compress a proof a high
complexity into an effectively constant s= ized statement of proof acceptance.

Relevant commits for the curious= :
=C2=A0 * https://github.com/Roasbeef/go-zkvm/compare/f69145811= 0b6b551a20ab36d15de98dfb6813d8c...77420055510acfc2f0bee2dcf2313365dee927e8<= /a>
=C2=A0 * https://github.com/Roasbeef/bip32-pq-zkp/compa= re/aae0a1a763eed6bfab8660bcfb8f938f91b10c10...4dcb731e4fc97f84e52c85d2768dc= 41612c71027


I added some sketch notes to the repo re constru= cting an aggregated proof via
composition of a merkle tree of individual= statements (would enable a single
proof in a block for all the statemen= ts):
https://git= hub.com/Roasbeef/bip32-pq-zkp/blob/main/docs/claim.md#future-recursive-comp= osition-sketch.

-- Laolu

On Tue, Apr 7, 2026 at 8:39=E2= =80=AFPM Olaoluwa Osuntokun <laolu32@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 b= e 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. I= nitially, I didn't really have a
clear end target application, it wa= s 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 fo= rward ~9 months later, and an initial killer
use case popped into my min= d: a zk-STARK proof that a Taproot output public
key was generated using= BIP-32, via a given BIP-86 derivation path.

More formally:
```ma= th
\mathcal{R} =3D \left\lbrace\;
(\overbrace{K,\, C}^{\textsf{public= }} ;\; \underbrace{s,\, \mathbf{p}}_{\textsf{witness}})
\;\middle|\;
= \begin{aligned}
=C2=A0 K &=3D \textsf{BIP86Taproot}\bigl(\textsf{BIP= 32Derive}(s,\, \mathbf{p})\bigr) \\
=C2=A0 C &=3D \textsf{SHA256}\bi= gl(\texttt{"bip32-pq-zkp:path:v1"} \;\|\; \mathbf{p}\bigr)
\en= d{aligned}
\;\right\rbrace
```

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.


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

The TL;DR is that:

=C2=A0 * Given that the Tapr= oot commitment scheme is post-quantum secure [3], in
=C2=A0 =C2=A0 the f= uture we can deploy a soft fork to _disable_ the keyspend path,
=C2=A0 = =C2=A0 and force all Taproot spends to instead flow through the script path=
=C2=A0 =C2=A0 (not my idea, commonly discussed amongst developers, not = sure who
=C2=A0 =C2=A0 proposed it first). At that point, Taproot starts= to resemble BIP-360.

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

=C2=A0 * A 2023 paper (Protecting Quantum Proc= rastinators with Signature
=C2=A0 =C2=A0 Lifting: A Case Study in Crypto= currencies [4]) proposed a solution to this,
=C2=A0 =C2=A0 namely _seed = lifting_ (use BIP-32 as the one-way function to the
=C2=A0 =C2=A0 Picnic= PQ Signature scheme) to provide a post-quantum proof of secret
=C2=A0 = =C2=A0 information a quantum attacker wouldn't be able to easily obtain= .

=C2=A0 * The downside of that is that it reveals the secret BIP 32= seed,
=C2=A0 =C2=A0 exposing other non migrated UTXOs of a user.
=C2=A0 * With this project I've cobbled together a series of projects = to be able
=C2=A0 =C2=A0 to generate a zk-STARK proof that a Taproot out= put public key was
=C2=A0 =C2=A0 generated via BIP-32 invocation of a BI= P-86 derivation path.

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

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

=C2=A0 * tinygo-zkv= m: ht= tps://github.com/Roasbeef/tinygo-zkvm
=C2=A0 =C2=A0 * A fork of Tiny= Go that supports the flavor of RISC-V (rv32im) that
=C2=A0 =C2=A0 =C2=A0= risc0 requires to generate/execute a guest program to later be proved
= =C2=A0 =C2=A0 =C2=A0 by the host.

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

=C2=A0 * go-zk= vm: https= ://github.com/Roasbeef/go-zkvm
=C2=A0 =C2=A0 * Go utilities to take = a RISC-V ELf binary produced by tinygo-zkvm, and
=C2=A0 =C2=A0 =C2=A0 pa= ckage it in the expected R0BF format, which combines the user
=C2=A0 =C2= =A0 =C2=A0 generated RISC-V ELF (the thing that is executed to generate the=
=C2=A0 =C2=A0 =C2=A0 proof) along with the v1compat ELF kernel, which i= s risc0's execution
=C2=A0 =C2=A0 =C2=A0 environment.

=C2=A0 = =C2=A0 * This also includes a Go host package, which loads the guest progra= m,
=C2=A0 =C2=A0 =C2=A0 executes it, and generates a trace to later be p= roved. This is
=C2=A0 =C2=A0 =C2=A0 achieved via a C FFI compat layer be= tween Go and the original Rust
=C2=A0 =C2=A0 =C2=A0 host/proving/verific= ation code.

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

=C2=A0 =C2=A0 =C2=A0 * The C FFI wrapper around the OG Ru= st host, which is used to load
=C2=A0 =C2=A0 =C2=A0 =C2=A0 the guest pro= gram, execute it, generate a trace, then finally
=C2=A0 =C2=A0 =C2=A0 = =C2=A0 generate a proof.

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

On several layers, t= his demo is far from optimized (more on that later),
this is meant to se= rve as a PoC to demonstrate that with the latest
software+hardware, a pr= oof of this complexity is well within reach.

For those curious re th= e e2e details I've generated this tutorial that
explains the entire = system top to bottom:
https://github.com/Roasbeef/go-z= kvm/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 read= ing up until now, and feel free to return back to
the _The Net of a Mill= ion 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 quantumcomputer capable of breaking classical asymmetric cryptography, any coins=
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 addre= ss re-use
(spending from the same script twice), or Taproot outputs, whi= ch publish
the public key plainly in the pkScript.

As detailed in= [3], for Taproot outputs, a widely circulated plan is
roughly to: disab= le the _keyspend_ path (requires a simple signature),
enforcing a new ru= le that all Taproot spends must then flow through the
script path. Spend= ing 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-resis= tant function.

That means any UTXO that _does_ commit to a script pa= th has a future escape
hatch _if_ such a softfork would need to be deplo= yed in the future.
However, what about all the other wallets that use BI= P 86, and don't commit
to a script path at all? Under a strict versi= on of this existing
proposal, those wallets would basically be locked fo= rever.

The goal of this work is to demonstrate a practical solution = (discussed
against devs, but never implemented AFAICT): generate a zk pr= oof that an
output was generated using BIP-86. For the zk-Proof, we sele= ct zk-STARKs,
as they're plausibly post quantum since they rely only= on symmetric
cryptography: layers of merkle trees over an execution tra= ce, along with
some novel sampling/error-correction algorithms.

A= t 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 th= is
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 p= roof needs to find a _colliding_
seed: a different seed s' such that= HMAC-SHA512("Bitcoin seed", s') produces
the same master = key. The BHT algorithm (Brassard-Hoyer-Tapp [6]) is the
best known quant= um collision finder, and it runs in time proportional to the
cube root o= f the output space: 2^(n/3). For HMAC-SHA512's 512-bit output,
that&= #39;s ~2^171 quantum operations, well above even NIST's highest
post= -quantum security category. Therefore, if you generated a wallet using
B= IP-32, you possess _another_ secret that a quantum adversary can't
e= fficiently reconstruct!

This demo focuses on the Taproot case, but t= he 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, Bitco= in Core only officially adopted BIP-32 in
2016/2018, moving away from th= eir existing key pool structure. I can't say
how much BTC is held to= day 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= stack of choice (lnd/btcsuite) uses
a series of Go libraries, so I want= ed to be able to re-use them, first for
this demo, then also in the futu= re 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 (produ= cing a smaller binary than if
you used the normal stdlib path).

T= inyGo supports RISC-V, but _not_ the 32-bit variant of RISC-V that risc0relies on. So the first step here was to create a new target definition fo= r
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/ris= cv32im-risc0-zkvm-elf.ld`) which created a memory layer
identical to wha= t risc0 expects. The final component was a new runtime
(`src/runtime/run= time_zkvm.go`), which implemented a few platform specific
syscalls for r= isc0 (putchar(), exit(), ticks(), and growHeap()).

When I tried to g= et this working last year, I had to also implement a number
of kernel sy= scalls (called ecalls in the platform [7]) to handle: read+write
to stdi= n/stdout, halting, and the journaling mechanism (the transcript of
execu= tion committed to), which basically implement the kernel that the guest
= executes in. Fast forward to 2026, and after pulling the latest version of<= br>the repo, I realized that they now make a libzkvm_platform.a, which pack= ages
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 Go
guest (the program to = be proved) and a Go host (the thing that executes the
program and genera= tes the final proof).

## BIP-32+Taproot zk-STARK Proof

With b= asic proofs working (like the classic: I know the factorization of a
num= ber `n`), I was unblocked to generate the actual proof. The claim/proof
= is represented with the following JSON artifact:
```
{
=C2=A0 &quo= t;schema_version": 1,
=C2=A0 "image_id": "8a6a2c27dd= 54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a690",
=C2=A0 &qu= ot;claim_version": 1,
=C2=A0 "claim_flags": 1,
=C2=A0 = "require_bip86": true,
=C2=A0 "taproot_output_key": = "00324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92f9f07f992b288ee6"= ;,
=C2=A0 "path_commitment": "4c7de33d397de2c231e7c2a7f53= e5b581ee3c20073ea79ee4afaab56de11f74b",
=C2=A0 "journal_hex&qu= ot;: "010000000100000000324bf6fa47a8d70cb5519957dd54a02b385c0ead8e4f92= f9f07f992b288ee64c7de33d397de2c231e7c2a7f53e5b581ee3c20073ea79ee4afaab56de1= 1f74b",
=C2=A0 "journal_size_bytes": 72,
=C2=A0 "= proof_seal_bytes": 1797880,
=C2=A0 "receipt_encoding": &q= uot;borsh"
}
````

The `image_id` is basically a hash of t= he 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 ex= isting BIP-44 path, you can instead opt to
claim that instead. The Tapro= ot key we're generating the proof against is
also part of the _publi= c data_, as it sits plainly on the chain for all to
see. We then also in= clude a `path_commitment`, which is a commitment to the
exact BIP 86 pat= h that the prover used. Finally, we also commit to the
journal hex, whic= h is basically a commitment to the public claim.

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

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

The default prove target = writes:
=C2=A0 * ./artifacts/bip32-test-vector.receipt
=C2=A0 * ./art= ifacts/bip32-test-vector.claim.json

The receipt is the STARK proof a= rtifact. claim.json is the stable,
human-readable description of the pub= lic statement being proved.

## Application to a Future Keyspend Disa= bling Soft fork

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

In 2= 026, we've shown that this is achievable using 2 year old consumer
h= ardware. I don't doubt that the upcoming advancements (eg: photonics, n= ew
flavor of high bandwidth memory, etc) in hardware (driven by the fier= ce 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 R= ISC-V layer that adds overhead which increase the total amount
of steps,= and therefore the size of the proof. A production grade
deployment woul= d likely instead hand roll a custom STARK proof for this
exact statement= , to achieve a faster and smaller proof).

# Future Work

In te= rms of future work, there're a number of interesting following up
pr= ojects that can be pursued from here.

One basic one is that the curr= ent 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 spending.

Looking to the memory+computational r= equirements necessary to generate the
proof, I've left two low hangi= ng fruits:

=C2=A01. First, we can speed up the Elliptic Curve operat= ions the proof requires
=C2=A0 =C2=A0 (scalar base mult, then addition, = or more performantly Double Scalar
=C2=A0 =C2=A0 Multiplication via the = Strauss-Shamir trick). For this we can use the
=C2=A0 =C2=A0 syscalls/pr= ecompile in the risc0 env for big integer arithmetic:
=C2=A0 =C2=A0 sys_= bigint and sys_bigint2. With this, the guest calls into the kernel
=C2= =A0 =C2=A0 to use an optimized/accelerated circuit for the modular arithmet= ic,
=C2=A0 =C2=A0 reducing cycles, steps, and thus proof size.

= =C2=A02. Second right now, the entire claim is a single proof. Instead, we = can
=C2=A0 =C2=A0 first break that up using their recursive proof/compos= ition syscalls:
=C2=A0 =C2=A0 sys_verify_integrity+sys_verify_integrity2= . We can then assembled a
=C2=A0 =C2=A0 series of these proofs into a _s= ingle_ statement, which can save block
=C2=A0 =C2=A0 space by aggregatin= g 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<= br>
[5]: https://microsoft.github.io/Picnic/

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

[7]: https://git= hub.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 bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/= msgid/bitcoindev/CAO3Pvs-ToXzNDRUa3ZtnEz2t1CN-nPG-8Xt5wNmRE%2BR6Dy1fVQ%40ma= il.gmail.com.
--00000000000030ec8f06508ed9e7--