From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 28 Apr 2026 18:22:01 -0700 Received: from mail-oa1-f63.google.com ([209.85.160.63]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1wHtcj-0004xT-SD for bitcoindev@gnusha.org; Tue, 28 Apr 2026 18:22:01 -0700 Received: by mail-oa1-f63.google.com with SMTP id 586e51a60fabf-423145d81c7sf19973502fac.2 for ; Tue, 28 Apr 2026 18:21:57 -0700 (PDT) ARC-Seal: i=3; a=rsa-sha256; t=1777425712; cv=pass; d=google.com; s=arc-20240605; b=JDMTMHVkrB7mokccvkFOEBKJxaTyDrPfFu5Mg3l/XWnVfWuL17v2UadR0s+sN9ZoE7 AhfsebHDhtTdVf5p6imMGIr/B9srgAtD2Hs2OoNiVsPThc5ZT8ti8FlqbXRWnBPJBM6v GlL0D8hPrUgoLr1LngPDceIq7ZWVeQFCC6u2qxL4TOyW1brlNd9au14P9ygvmYnBc+Gx PtXUIFNXYIUDtCz8Fa/8/BE/ep8q3NlHNgxYhyW7ho8yHqVTuiZ95fPiuVcNTPlVEs+u Pt5j6gwY+LXflNM/AQlpRxtwpNEGSJLNWh5ubH2hOQwVv1q2QYEVu8NVdwzjYvt7wYK2 bOKA== 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=lYsP+BUp7HtykXkvgnrSNuzGzHewF/MEthD9BSkApQ8=; fh=K4eZTZ3XMUl3lbvRDgSzhrPu6IXZ4wFoRAb75xW2x4U=; b=gUvESB4c1fzSx7dIRbtDXIzrNSMsASS0d8YkABxz//vo94ypuyvANZ+MGLenSLMfT4 pSVmOMvkWdV89F82S1ag3rtRkDree1aCXLBkP4TP4KMyLAlzu2UNwGfcGP4tb7tJLElc uwoXZKonKqxhOnDywJm2Cl4KVAnPnk9MSiOerKG0XyahzqbdxPfcbj44bXXtdc0kOdbs n+JY0uV3qqMAXj2Z7IIZ7LWfxP2oH9uLvhB8GeBUrQt1w2QOPHv/L8vPNU05TfuOaeZl XdeGw9OFvp5r3wK8KKbEnjfbRtYiliafsRLVcFvw/iyJNkrUTo4MWgVjm7409MvmpNrA V1+Q==; darn=gnusha.org ARC-Authentication-Results: i=3; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=gEWQMEOT; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b130 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=1777425712; x=1778030512; 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=lYsP+BUp7HtykXkvgnrSNuzGzHewF/MEthD9BSkApQ8=; b=UTYVQQizT5c61TqLn3Te4FTKmdo1y6J/3zfPiRV6xAkdeffo9p+xIGVzjFMKp0Wb5/ wrFCvqfYoA5kG0hcfDD7Yn6ucTzs0Vkv51YLNAh5cFqftRbjmUTmhtmf/3qhme+PaelO uivMzUULMpnH3BxQVZgIJ4oJh3Q4YDZjytmh/q9XCgZL7maawLQSh9faZPCE1TnYikZZ h+9PpWgB6xu1Tt9DGESRz8K8SaSKELRTGwKCVcSTzd3WL31J9tDO9LLku4pQ53LWSZJG xk9wANyx2JQIb97h7ZY5amwJsDdR4WF4FHiuvk0rRV2dmHMKg0EPztHhGgrB91Qj5iCD gKyA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1777425712; x=1778030512; 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=lYsP+BUp7HtykXkvgnrSNuzGzHewF/MEthD9BSkApQ8=; b=QAhafwbkGq+MS+hYOBJsh7diVpvxp8RMGdPHJdNqxC4xngm3vveQrLYi+jnJbA7YZv stlSzErxR2ruRMDsu/lwbp5gevF3bC0+tyDBEBX2kYR9Z/QHnD+gR3bA3cm5JXg2+7c2 iCbZFwS8lno6HCW+7tcRUuMRaPM5ravP+VxCY1Mc5zvXFuTX62l35Oe1NeZPmv0QZb31 e5esq0by0sF9VlFB5I3AoeKJgL7Y83uSXoGV/zNwxWxHgSruXU6In6JWKehO+OTKWHKC a/JCuIi/Xv2ogCe7QEXcVxrT5lhHyHdAAXGJzF0uwZXmHWABdiOswX1wdl633mVeS4Ug eujg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1777425712; x=1778030512; 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=lYsP+BUp7HtykXkvgnrSNuzGzHewF/MEthD9BSkApQ8=; b=EuXZvIuMSVAa8SjzIb/H5gNrvgS/bit+2rETCagIy6xJxwAFamBlBhWTj34PK+T6Vi wAmCAOlz8XU0JIj2W6BgH9R5vT8jjU1HkT4qIbEKGHbWFxUcaxaMq/nwppCA1HTVzjvQ HLkx5KTQZfKC0lnsq5irGjDb799TEVwayb0mK85gVyWjkrb5EgpZ+SOD1G69W9o2X3P0 x7OLNAlrgN9g86h54EJHb72gX00tKR4U8fYodQEx/NonfO1x0d6G+YSVWCEg1FsXF8Dv tg7737DNFBgIFb14TeDFkAjhWwE2mm5VnIdGkKsTHR3j9UQR4QdydM2imIY3cf64XOj8 WwYA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=3; AFNElJ/K+pzcr+exzJoDkWAUdbedXz6fNZcXG5ZGhCgqEjSxowTXuWItzve1ueRpWNE92NGpHntJbBc9iFiv@gnusha.org X-Gm-Message-State: AOJu0Yx9h38aSopy+b/8aCT4+1MGJMIpTiDqe/kWDsYcpWuvsa4NjuxA HSqCM2KINhf5vU20XnBfZlwVmsFNVZ1jK2EQANxXF02C763vyDqnXoWo X-Received: by 2002:a05:6820:1b14:b0:696:2674:8a1a with SMTP id 006d021491bc7-6965cb85281mr3028651eaf.48.1777425711629; Tue, 28 Apr 2026 18:21:51 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AUV6zMP2vDu9yds1ZqdzqS1Y+jvlDFv/n77uSxK8iO7zQ+KCWg==" Received: by 2002:a05:6820:1626:b0:681:a657:a767 with SMTP id 006d021491bc7-6961e64c8b6ls3642432eaf.1.-pod-prod-05-us; Tue, 28 Apr 2026 18:21:47 -0700 (PDT) X-Received: by 2002:a05:6808:144f:b0:469:fc59:b128 with SMTP id 5614622812f47-47c28f71b3fmr3015531b6e.25.1777425706996; Tue, 28 Apr 2026 18:21:46 -0700 (PDT) Received: by 2002:a05:620a:12c5:b0:8d6:1bc4:a7bc with SMTP id af79cd13be357-8e7920843bems85a; Tue, 28 Apr 2026 18:16:30 -0700 (PDT) X-Received: by 2002:a05:620a:460f:b0:8cd:b626:cdf1 with SMTP id af79cd13be357-8f7d9902bd8mr746411485a.46.1777425390267; Tue, 28 Apr 2026 18:16:30 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1777425390; cv=pass; d=google.com; s=arc-20240605; b=Y+pATPaB+VX0/P0pVEIspRK2g+2fbRaKHV9R6mevEUcQJCkrWIsCb/osy37abMtrTz h/4U0R8gV6e3PouBe2ETy/4Nx4yv/pN6WIp0tnzFYqIDXlmVp1bnjEw2iMcnjV2vUo7C wTMkTsAWaXveiYuC006crzwj9P9vZBaYGjafzj39eFcxU+eq+49VGX6bthVvJAhnF6+V BrNAXBQlkaFyPCA9UQKaOBiLVHmvRgGL2IxOY9gHyEb2dDFj7w89S8iRd7n3ANiKcfCj ehgl50y8Qr8UM7AuN03ipQK8znWiVgN4jVA9mzJhCxZ+pVswEs9qtyV9JQBgjsDQzbNo 16Dg== 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=odfIgeo2UN+SaZRTuHMjRYYEm5U5CfiMx/LoyNF6G44=; fh=apggEuJgW4uaLwt6WMeOWmRsxbdevZ9R4Mlfs7LDMYo=; b=L0xhrehD697PN6GDU0C0B2x5FSJQo26yTuFLi/PwtKvbouPS/5SoNxHNXASSzR1amP FTyGC1qnzUBqyg52FBVCn9WugjX7EVJJNMJYC/4d5aM7706V8W2fIpfJLPcaLncpn4jU kX3x44523I2E01pF1DcyDjPMsv8Z7jqAXwVWSqBKkA8IUgjtr5orP//oCAD+GoOFrUtz b8VcaE29ZeycLx6F4mhF0w1IpDnaHnFTXThC3IejMy6/rLxPv5IhdGinz2ryj+hZlgHx DwsiLCmImFkVikCQzqPxyXzq5jEHh8beQHmj2M0y1jPmc8xiwkb4TnQgeRZmvsoOOOKY 1yxw==; dara=google.com ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20251104 header.b=gEWQMEOT; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b130 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-xb130.google.com (mail-yx1-xb130.google.com. [2607:f8b0:4864:20::b130]) by gmr-mx.google.com with ESMTPS id 6a1803df08f44-8b3ef79714dsi261326d6.3.2026.04.28.18.16.30 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 28 Apr 2026 18:16:30 -0700 (PDT) Received-SPF: pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b130 as permitted sender) client-ip=2607:f8b0:4864:20::b130; Received: by mail-yx1-xb130.google.com with SMTP id 956f58d0204a3-651bf695701so10908921d50.2 for ; Tue, 28 Apr 2026 18:16:30 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1777425390; cv=none; d=google.com; s=arc-20240605; b=T+FefQM048HeTGJFS9MN4EUF/LTKgviSZ/JYPCcs8Bbkp1MH1Fy4mRLaA2rYiYlfB7 EDQ1ZoxG55b0B2K7TIlvq0fxl8/sMwNUWsI4iIxxWq6ufrEwbYwr2cwfnhgg9bjE5GOa mccdyhaZUzNiO++DzT0tRqxw6UtTjUKgxZUmR3uOFOqIy2QUQVUfl0xLIPZgWst7cN+k 4F4YarG9KFQdF7GrASQUoII87Rngpq1KZUe9QUi/YuBxh5xgJqyoWmqL+GshkYttmRfF BW9nVnGFrz/7dZDqVOWxqYeu+wyoY9Kbb79c6mD5qnYdAm41WzzYHOMsGZKGy2votudM Dn4g== 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=odfIgeo2UN+SaZRTuHMjRYYEm5U5CfiMx/LoyNF6G44=; fh=apggEuJgW4uaLwt6WMeOWmRsxbdevZ9R4Mlfs7LDMYo=; b=JWAeG3VPixbxK7z/tkiSJ1g5BDrZjuu0MFPm7I5TDsAs6nF7fDC14tcr5s+aH9fpb1 LFthHGdZPHzXVxjpaMqmyhZVu+LYiawKHfsQYuZHGqSmMEHUe75q21lUd3UFbb33e2cP gaj71Yu4NbMv0vLNYojDpG5lwoo2fmveujQreaF3VSnova4KwsE0vHLZKLCIHpW5+o2Z sq5D89QBOIlPPXKb70MPRAvipO9uuULPyG0WLgM+9oK2cWqONwVnsmJhtBgaIUTIfhWE aOnXIgLO3z7ul46hQXtAfsTBcIMjcsjCMPw59y2oqA37rkyRFhxmj7xmk5941Sv4lB3k hCkQ==; dara=google.com ARC-Authentication-Results: i=1; mx.google.com; arc=none X-Gm-Gg: AeBDietqElPOX4ZJyi6hTHgHeO2t/XfdrVwmEvBqZvBGDej/obD7NPTyOWaCwqhCRo9 /7HEndWTm0KTi6LSTfZ+B1hIFcg0sqYB/v0Vxyd/K327sIpEArr2Ox1+xwxacMM+hpXwWecNZQX 9WAURHgK+RjVFw0/wIAC3/RbwAkJ6DtTqa6fEWmqz68zSMyv47PUJH1jq54W9fMD5JWdEA9fPU3 YouHegKTEXiul84/QMIv5IroJCCdbiP2wYUUakQkbFg/HV/oO3DU4SPUHN2uQI5/r9m8TfZXCpp sG/srKhtEspU+Xfdror7+0o1My+KaXutA4rCSvwBIGqdqGatEis= X-Received: by 2002:a05:690e:1504:b0:650:379f:3580 with SMTP id 956f58d0204a3-65beed77929mr4361810d50.21.1777425389331; Tue, 28 Apr 2026 18:16:29 -0700 (PDT) MIME-Version: 1.0 References: <02378fd1-17a4-47aa-89fa-ee87626def65n@googlegroups.com> In-Reply-To: <02378fd1-17a4-47aa-89fa-ee87626def65n@googlegroups.com> From: Olaoluwa Osuntokun Date: Tue, 28 Apr 2026 18:16:17 -0700 X-Gm-Features: AVHnY4L6yjZWzYmtwmt8ojQJDuQ3k4jRcr1bwzYJadOltBaUtJfutYkc0P8FnMM Message-ID: Subject: Re: [bitcoindev] Post-Quantum BIP-86 Recovery via zk-STARK Proof of BIP-32 Seed Knowledge To: sadiq Ismail Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000f2291406508f18e5" 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=gEWQMEOT; arc=pass (i=1); spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::b130 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 (/) --000000000000f2291406508f18e5 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Sadiq, > The scheme extends to BIP-352 (Silent Payments) Yup, as shown in my latest post, we can batch aggregate multiple claims into a single proof. If this were to be deployed at some point in the future, devs would be able to scower wallets/protocol/codebases for other recovery proofs/claims that could be added. > The zk-STARK proof? or this mechanism should definitely be bound to the > spending transaction and the input being spent. Def, this would be it would be straight forward to bind the proof to a give= n wtxid/sighash. > Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BIP-32 > still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2=80= =94 as long as the pubkey > has never previously appeared on-chain. A zk-STARK proof should apply her= e > too? No fundamental reason, just I decided to focus the initial demo on P2TR. On= e could easily swap in this section where the Taproot Output key is derived with another script type instead [1]. [1]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/bip32/taproot.go#L91-L94 -- Laolu On Mon, Apr 13, 2026 at 12:21=E2=80=AFPM sadiq Ismail wrote: > Hi Laolu, list, > > Nice work. > > The scheme extends to BIP-352 (Silent Payments). The BIP-352 receiver > reconstructs the output P using their private scan key, public spend key, > and public information from the spending transaction A. > See BIP-352 Scanning. BIP-352 recommends but does not mandate BIP-32 for > deriving the scan and spend keys, but specifies the following derivation > paths when BIP-32 is used: > > b_scan =3D BIP32Derive(s, m/352'/coin_type'/account'/1'/0) > b_spend =3D BIP32Derive(s, m/352'/coin_type'/account'/0'/0) > > For all silent payment addresses generated using BIP-32, your technique > applies. The prover produces a zk-STARK proof that the program > BIP32Derive(s, p_scan) and BIP32Derive(s, p_spend) were run correctly, > and that the resulting keys reconstruct the on-chain output P using along > with A. > > As you highlighted txid is not committed in the proof currently, the > argument is replayable. The current POC does not bind to where the coins > go. Anyone who observes the chain could copy it and attach it to a > different transaction, spending the same UTXO to a different address. Wor= se > for silent payment, because all user UTXO have the same secret > BIP32Derive(s, p_scan) and BIP32Derive(s, p_spend) except for A. > The zk-STARK proof? or this mechanism should definitely be bound to the > spending transaction and the input being spent. > > Curious why not generalise beyond BIP-32? P2PKH and P2WPKH without BIP-32 > still commit to an unrevealed secret =E2=80=94 HASH160(k=C2=B7G) =E2=80= =94 as long as the pubkey > has never previously appeared on-chain. A zk-STARK proof should apply her= e > too? The prover argues for the correctness of HASH160(k=C2=B7G) =3D h, wh= ere k is > the private key scalar and k=C2=B7G is the elliptic-curve point, without = ever > revealing k or the pubkey. This would allow recovery of a broader set of > funds. If it were decided that classical signatures for these output type= s > are invalidated and only a valid zk-STARK proof is required to spend, > anyone who holds the original secret can unlock their funds. > > P.S. I am not for or against disabling valid spend paths post-quantum, > just discussing the technical possibilities. > > Best, > Abubakar Sadiq > On Friday, April 10, 2026 at 7:47:09=E2=80=AFPM UTC+2 conduition wrote: > >> Ah! Amazing work! 2 seconds to prove is really crazy. Proving a single >> SHA256 and one modular addition on my CPU back in the day took like 20 >> seconds. Your GPU is coming in clutch for this. I best RISC0 has also >> improved quite a bit since then. >> >> I think the next optimization step would be pre-seeding the two SHA512 >> midstates from the host, so you only need to prove two SHA512 compressio= n >> calls instead of four. Intuitively I expect this would at best halve you= r >> prover time from 2sec, to probably a little over 1sec, and your verifier >> time will probably drop as well since that also seems to scale with circ= uit >> complexity. >> >> I think I have two half-decent arguments now as to why this won't affect >> security: >> >> First, even if a fraudulent prover is *handed the correct midstates to >> use*, the prover would still have to do the hard work of finding the >> parent secret key needed as a witness. This is at least the same difficu= lty >> as finding the parent sk=E2=80=8B=E2=80=8B if we just hashed it without = a chaincode at >> all, using two bare SHA512 calls - the only thing that changes is the >> midstate, and the SHA512 input length suffix. Starting from a different >> midstate doesn't magically give the attacker a head-start in a 256-bit >> search space looking for sk=E2=80=8B. A frauduent prover would know the = child >> secret key k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't = know int(I[32:]) or >> sk=E2=80=8B so they cannot solve for either. >> >> Nominally, the fraudulent prover wouldn't even know the correct >> midstates, so their task is strictly harder. >> >> Secondly, here's another argument as to why finding the midstates in the >> first place should also be hard. >> >> Any adversary who could solve this problem by finding the right midstate= s >> could be used as an oracle to prove the existence of partial 2-cycles in >> SHA512. >> >> >> - Given a SHA512 hash I=E2=80=8B=E2=80=8B, set sk =3D int(I[32:])=E2= =80=8B=E2=80=8B=E2=80=8B >> - Compute k =3D sk + sk % n=E2=80=8B >> - Use the black-box fraudulent prover on the child key k=E2=80=8B=E2= =80=8B to find >> correct midstates such that >> >> >> I =3D=3D SHA512( || SHA512( || 0x00 || sk || i))= =E2=80=8B=E2=80=8B=E2=80=8B >> k =3D=3D int(I[32:]) + sk % n=E2=80=8B >> =3D=3D sk + sk % n=E2=80=8B=E2=80=8B >> >> Remember that sk =3D int(I[32:])=E2=80=8B=E2=80=8B. Thus for these condi= tions to hold, the >> proof forger must be able to find not just the correct midstates, but al= so >> midstates which give a 2-stage partial hash cycle so that: >> >> I =3D=3D SHA512( || SHA512( || 0x00 || I[32:] || i= ))=E2=80=8B >> >> This seems unlikely or at least very difficult. >> >> regards, >> conduition >> On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun < >> lao...@gmail.com> wrote: >> >> 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= xpub >>>> 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 Group= s >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n >> email to bitcoindev+...@googlegroups.com. >> >> To view this discussion visit >> https://groups.google.com/d/msgid/bitcoindev/CAO3Pvs9tps%3DbsMQyA%2BHvhK= -u%2BXqRwWtjTq8WXZi%2BcveAVwPi9A%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+unsubscribe@googlegroups.com. > To view this discussion visit > https://groups.google.com/d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee87= 626def65n%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/= CAO3Pvs8ORzYxaNfDZUHdcuimN7NS5ce-Xz0cUa92%3DGnhMdD8gg%40mail.gmail.com. --000000000000f2291406508f18e5 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Sadiq,

> The scheme extends to BIP-352 (= Silent Payments)

Yup, as shown in my latest post, we can batch aggre= gate multiple claims into a
single proof. If this were to be deployed at= some point in the future, devs
would be able to scower wallets/protocol= /codebases for other recovery
proofs/claims that could be added.

= > The zk-STARK proof? or this mechanism should definitely be bound to th= e
> spending transaction and the input being spent.

Def, this= would be it would be straight forward to bind the proof to a given
wtxi= d/sighash.

> Curious why not generalise beyond BIP-32? P2PKH and = P2WPKH without BIP-32
> still commit to an unrevealed secret =E2=80= =94 HASH160(k=C2=B7G) =E2=80=94 as long as the pubkey
> has never pre= viously appeared on-chain. A zk-STARK proof should apply here
> too? =

No fundamental reason, just I decided to focus the initial demo on = P2TR. One
could easily swap in this section where the Taproot Output key= is derived with
another script type instead [1].

[1]: https://github.com/Roasbeef/bip32-pq-zkp/blob/main/bip32/taproot.go#L= 91-L94

-- Laolu


On Mon, Apr 1= 3, 2026 at 12:21=E2=80=AFPM sadiq Ismail <ask4ismailsadiq@gmail.com> wrote:
Hi Laolu, list,

Nice work.
The scheme extends to BIP-352 (Silent Payments). The BIP-352 receiver= reconstructs the output P using their private scan key, public spend key, = and public information from the spending transaction A.
See BIP-352 Scan= ning. BIP-352 recommends but does not mandate BIP-32 for deriving the scan = and spend keys, but specifies the following derivation paths when BIP-32 is= used:

=C2=A0 =C2=A0 b_scan =C2=A0=3D BIP32Derive(s, m/352'/coin= _type'/account'/1'/0)
=C2=A0 =C2=A0 b_spend =3D BIP32Derive(= s, m/352'/coin_type'/account'/0'/0)

For all silent p= ayment addresses generated using BIP-32, your technique applies. The prover= produces a zk-STARK proof that the program BIP32Derive(s, p_scan) and BIP3= 2Derive(s, p_spend) were run correctly,
and that the resulting keys rec= onstruct the on-chain output P using along with A.=C2=A0

As you= highlighted txid is not committed in the proof currently, the argument is = replayable. The current POC does not bind to where the coins go. Anyone who= observes the chain could copy it and attach it to a different transaction,= spending the same UTXO to a different address. Worse for silent payment, b= ecause all user UTXO have the same secret BIP32Derive(s, p_scan) and BIP32D= erive(s, p_spend) except for A.
The zk-STARK proof? or this mecha= nism should definitely be bound to the spending transaction and the input b= eing spent.=C2=A0

Curious why not generalise beyond BIP-32? P2PKH an= d P2WPKH without BIP-32 still commit to an unrevealed secret =E2=80=94 HASH= 160(k=C2=B7G) =E2=80=94 as long as the pubkey has never previously appeared= on-chain. A zk-STARK proof should apply here too? The prover argues for th= e correctness of HASH160(k=C2=B7G) =3D h, where k is the private key scalar= and k=C2=B7G is the elliptic-curve point, without ever revealing k or the = pubkey. This would allow recovery of a broader set of funds. If it were dec= ided that classical signatures for these output types are invalidated and o= nly a valid zk-STARK proof is required to spend, anyone who holds the origi= nal secret can unlock their funds.=C2=A0

P.S. I am= not for or against disabling valid spend paths post-quantum, just discussi= ng the technical possibilities.

Best,
Abubakar Sadiq
On Friday, April= 10, 2026 at 7:47:09=E2=80=AFPM UTC+2 conduition wrote:
= Ah! Amazing work! 2 seconds to prove is really crazy. Proving a single SHA2= 56 and one modular addition on my CPU back in the day took like 20 seconds.= Your=C2=A0GPU is coming in clutch for this= . I best RISC0 has also improved quite a bit since then.
=
I think the nex= t optimization step would be pre-seeding the two SHA512 midstates from the = host, so you only need to prove two SHA512 compression calls instead of fou= r. Intuitively I expect this would at best halve your prover time from 2sec= , to probably a little over 1sec, and your verifier time will probably drop= as well since that also seems to scale with circuit complexity.=C2=A0

I = think I have two half-decent arguments now as to why this won't affect = security:=C2=A0

First, even if a fraudulent prover is=C2=A0handed the correct midstates to use, the prover would still have to do the= hard work of finding the parent secret key needed as a witness. This is at= least the same difficulty as finding the parent sk=E2= =80=8B=E2=80=8B if we just hashed it wit= hout a chaincode at all, using two bare SHA512 calls - the only thing that = changes is the midstate, and the SHA512 input length suffix.=C2=A0Starting = from a different midstate doesn't magically give the attacker a head-st= art in a 256-bit search space looking for sk=E2=80=8B.=C2=A0A=C2=A0frauduent prover would = know the child secret key=C2=A0k =3D sk + int(I[32:]) % n=E2=80=8B=E2=80=8B, but they don't kn= ow=C2=A0= int(I[32:])=C2=A0or=C2=A0sk=E2=80=8B so they cannot so= lve for either.

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

Secondly, here's another arg= ument as to why finding the midstates in the first place should also be har= d.=C2=A0

=
Any adversar= y who could solve this problem by finding the right midstates could be used= as an oracle to prove the existence of partial 2-cycles in SHA512.=C2=A0

  • Given a SHA512 hash=C2=A0I=E2=80=8B= =E2=80=8B, set <= code>sk =3D int(I[32:])=E2=80=8B=E2=80=8B=E2=80=8B
  • Compute=C2=A0k =3D sk + sk % n=E2=80=8B
  • Use the black-box fraudulent prover on the child ke= y=C2=A0k=E2=80=8B=E2=80=8B to = find correct midstates such that=C2=A0

I =3D=3D SHA512(<something> || SHA512(<something= > || 0x00 || sk || i))=E2=80=8B=E2=80=8B=E2=80=8B
k =3D=3D int(I[32:= ]) + sk % n=E2=80=8B
=C2=A0 =3D=3D sk + sk % n=E2=80=8B=E2=80=8B
<= /span>

= Remember that sk =3D int(I[32:])=E2=80=8B=E2=80=8B.=C2=A0Thus for these conditions= to hold, the proof forger must be able to find not just the correct midsta= tes, but also midstates which give a 2-stage partial hash cycle so that:

I =3D=3D SHA512(<something> || SHA512(<somet= hing> || 0x00 || I[32:] || i))=E2=80=8B
=
This seems = unlikely or at least very difficult.

regards,=
conduition
On Thursday, April 9th, 2026 at 5:56 PM, Olaoluwa Osuntokun <lao...@gmail.com> wrote:
Hi Condution,

So I implemented both va= riants of your idea. My intuition was right in that it
doesn't do mu= ch to reduce the size of the final succinct size, but the final
xpriv va= riant resulted in a significant reduction in both proving time, and
also= memory usage. I also re-ran the original succint proof for the originalTaproot claim and got a better value for the final proof time (def need a<= br>better benchmark env+set up!).

Here's a breakdown of the reso= urce requirements for the various proofs:
* Full Taproot
image = ID:
8a6a2c27dd54d8fa0f99a332b57cb105f88472d977c84bfac077cbe70907a6= 90
composite:
seal 1797880
prove 49.32s
v= erify 0.10s
peak RSS 11907399680
succinct:
seal 22= 2668
prove 64.30s
verify 0.03s
peak RSS 11927207= 936

* Hardened xpub
image ID:
ad4ebc0ef6ce51e0f581cc= 8d14742a5b97738e9decd3fe2b0f1746de5bad9617
composite:
seal = 513680
prove 14.63s
verify 0.04s
peak RSS 117835= 03872
succinct:
seal 222668
prove 17.29s
= verify 0.02s
peak RSS 11782307840

* Hardened xpriv
= image ID:
8401a36e4f54cb2beaf9ac7677603806cf9d775e90ef5a70168045a= 3c0df0849
composite:
seal 234568
prove 1.98s
= verify 0.02s
peak RSS 3144171520
= succinct:
seal 222668
prove 2.84s
verify 0.02s peak RSS 3145990144

So we can see that t= he succinct proof sizes are all about the same. However the
xpriv varian= t can be proved directly in just 2 seconds on my machine! It also
requir= es just 3 GB of memory for the proof as well.

I've created some = additional supporting documentation to detail exactly what
the new proof= s do and their results:

* https://github.com/Roasbeef/bip32-pq-zkp/blob/m= ain/docs/reduced-variants.md

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

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


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

<= /div>
-- Laolu

On Thu, Apr 9, 2026 at 1:53=E2=80=AFPM Olaoluwa Osu= ntokun <lao...@gmail.com>= wrote:
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> wrot= e:
Oh, I've been a fool, a f= oolish fool.

We d= on't even need to do point multiplication in the circuit at all.
<= div style=3D"font-family:Arial,sans-serif;font-size:14px">
I'm amending my pri= or suggestion slightly: The circuit (guest program) could take in an xpriv = (e.g. at m/86'/0'=E2=80=8B) and output a child xpri= v (e.g. at m/86'/0'/0'=E2=80=8B) to the journa= l (instead of outputting a child xpub).

This is safe because remember, EC spending h= as been disabled in this context, and to a quantum attacker, an xpub is com= putationally equivalent to its xpriv. So why bother hiding it? The child xp= riv doesn't give an observer anything they can't already do with th= e equivalent xpub.

The guest program then is basically the BIP32 CKDpriv algorithm, restric= ted to 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 derive the child address(es) as suggested in my last message, to authent= icate spending.

D= esigning the guest program like this will massively reduce your circuit com= plexity, because EC point multiplication is wayyyyy harder for the R= ISC0 compiler to arithmetize than a simple hash function. In my prior work with R= ISC0, I made a guest program which ran a SHA256 hash and an EC point mu= ltiplication. I found that pruning EC point arithmetic from my guest progra= m improved prover runtime by a factor of over 100x.

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

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

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

...where in the context of BIP32 hardened CKD, the HMAC key = K=E2=80=8B is the chaincode (padded with zeros to 128 bytes) a= nd msg =3D (0x00 || sk || i) is the parent secret key and chil= d index.
<= br>
Since <= code>len(K) =3D 128=E2=80=8B is the SHA512=E2=80=8B block size, we n= eed 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 fina= l 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 th= e parent secret key (modulo the curve order), producing the child EC secret key. = This last step is arithmetically simple; the SHA512 calls are where most of= the arithmetic complexity lies.

The question then becomes, which of these compre= ssion calls can be done outside the circuit, and which are truly essential = for security?

No= te 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 key via modular addi= tion. So compression call (2) seems unavoidable. The others are less rigid.=

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

Given a child xpriv with= secret key k=E2=80=8B, chaincode c=E2=80=8B and index i=E2=80=8B, I know a preimage x=E2=80=8B and secret key sk=E2=80=8B such that:
<= code>I <- SHA512(<something> || SHA512(<something> || 0x00 |= | sk || i)=E2=80=8B)
c =3D=3D I[:32]=E2=80=8B
k =3D=3D int(I[32:]) + sk= % n=E2=80=8B

Seeing as the <something>=E2=80=8B slots are arb= itrary, and we know in BIP32 they are always exactly one-block long, it see= ms easy to throw out the compression calls (1) and (3). The host can precom= pute the relevant SHA512 midstates outside the circuit, and pass the midsta= tes into the guest program as secret inputs. The tradeoff is that this permits malici= ous provers the flexibility of choosing their starting midstates (though ha= sh input length can be fixed at 192 bytes). I'm not entirely sure if th= is meaningfully weakens the verifier's soundness. Ethan Heilman might h= ave opinions on this, he knows a lot more about attacking hash functions th= an I do. Intuitively, I doubt sampling random SHA512 midstates is that much= better than sampling a random HMAC key (chaincode) K=E2=80=8B= and computing the resulting midstates.

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


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

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

It seems to me the ci= rcuit (guest program) could be simplified. Notice how the guest code computes the entire HD wallet key = path, including hardened and non-harde= ned derivation steps, and also computes the taproot output key with key-twe= aking. I'd argue these steps are extraneous to the core hard relation y= ou want the STARK to prove, and could be safely removed to reduce proof siz= e and improve performance.

In reality, you needn&#= 39;t go so far as to prove (1) "I know a BIP39 seed which derives t= his taproot output key". You need only prove this much more genera= l 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 whic= h 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 insid= e the guest program. I mean the prover derives m/86'= /0'=E2=80=8B first (in the host), and then write= s that xpriv into the guest program's inputs. The guest program der= ives and outputs the xpub at m/86'/0'/0'=E2=80=8B. The verifier may check the STARK output (xpub) is correctly c= omputed, then use the given key-path to manually derive the taproot address= from the xpub themselves, outside the circuit, and validate <= i>that address against the UTXO i'm spending. The verifier thus has= confirmed the prover knew an xpriv which (through a hardened derivation st= ep) derives the correct taproot output key.

This c= hange significantly reduces the size of the circuit. From a glance, I see t= he original guest program performs 6 HMAC-SHA512 calls (1 for the master ke= y, 5 for the BIP32 derivation steps), two SHA256 compression calls (for the= taptweak hash), and two point multiplications. With this simplified varian= t, we are invoking only a single HMAC-SHA512 call and a single point multip= lication. I can't say for sure, but I expect this will improve your pro= of size and runtime significantly.

This change als= o makes the circuit more generally applicable to other rescue contexts. For= instance, it could be applied to BIP340 xonly keys inside a taproot script= tree, or in a P2(W)SH address to an ECDSA public key, or to P2(W)PKH addre= sses.

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

We should also talk scaling efficiency. Given the c= ost of STARKs, this style of proof should be able to authorize spends for m= ore than one UTXO. Say you have a wallet with 10 different UTXOs held by di= stinct addresses in the same BIP44 account. One single STARK proof could au= thorize spending all 10 of them, by simply committing all 10 input signatur= e hashes into the journal, and labeling the inputs with the corresponding 10 BIP32 key paths someh= ow. The verifier would need to check the proof only once and = not 10 times. The 10 UTXO spends could be validated using the common xpub f= rom the STARK proof's journal.

For a slightly = related work proving a similar relation for hashed addresses, using differe= nt STARK technology stacks, see this delvi= ng post.

However, all this said, my personal p= reference for long-term procrastinator rescue is still for commit/reveal st= rategies which prove essentially the same statement about BIP32 in a two-st= ep procedure. They get the job done with much lighter cryptographic machine= ry and much smaller witnesses: a few hundred bytes over two transactions, c= ompared to a few 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 t= o demand the use of external quantum-safe coins to make the commitment in t= he first place, so perhaps the cost would be worth it to some people? IDK. = What do you think of commit/reveal compared to STARKs for this purpose?

regar= ds,
conduition

On Wednesday, April 8th, 2026 at 12:18 AM, Olaoluwa Osuntokun <<= a rel=3D"noreferrer nofollow noopener">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+...@googlegroups= .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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/02378fd1-17a4-47aa-89fa-ee87626def65n%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/CAO3Pvs8ORzYxaNfDZUHdcuimN7NS5ce-Xz0cUa92%3DGnhMdD8gg%40ma= il.gmail.com.
--000000000000f2291406508f18e5--