diff options
| author | Robin Linus <robin@zerosync.org> | 2023-11-08 00:22:44 +0100 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-11-07 23:22:49 +0000 |
| commit | 7e133513921145363880ce10ceb97c7a8f47b796 (patch) | |
| tree | 4b5d7ece1881102779d45620fd59e3d1c51c1e98 | |
| parent | 8cc918978ac04e12100568abbcc596ee29ddb09a (diff) | |
| download | pi-bitcoindev-7e133513921145363880ce10ceb97c7a8f47b796.tar.gz pi-bitcoindev-7e133513921145363880ce10ceb97c7a8f47b796.zip | |
[bitcoin-dev] Implementing Blake3 in Bitcoin Script
| -rw-r--r-- | 43/5dbf33a825468eda34eeafc92ad1535cabe794 | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/43/5dbf33a825468eda34eeafc92ad1535cabe794 b/43/5dbf33a825468eda34eeafc92ad1535cabe794 new file mode 100644 index 000000000..d05dc3fed --- /dev/null +++ b/43/5dbf33a825468eda34eeafc92ad1535cabe794 @@ -0,0 +1,208 @@ +Return-Path: <robin@zerosync.org> +Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 602B7C0032 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 7 Nov 2023 23:22:49 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp3.osuosl.org (Postfix) with ESMTP id 33F7960A5B + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 7 Nov 2023 23:22:49 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 33F7960A5B +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -1.899 +X-Spam-Level: +X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, + SPF_PASS=-0.001] autolearn=ham autolearn_force=no +Received: from smtp3.osuosl.org ([127.0.0.1]) + by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id 0icVBd7MvRhJ + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 7 Nov 2023 23:22:47 +0000 (UTC) +Received: from www382.your-server.de (www382.your-server.de [78.46.146.228]) + by smtp3.osuosl.org (Postfix) with ESMTPS id B6D11608A5 + for <bitcoin-dev@lists.linuxfoundation.org>; + Tue, 7 Nov 2023 23:22:47 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B6D11608A5 +Received: from sslproxy01.your-server.de ([78.46.139.224]) + by www382.your-server.de with esmtpsa (TLS1.3) tls TLS_AES_256_GCM_SHA384 + (Exim 4.94.2) (envelope-from <robin@zerosync.org>) + id 1r0VPB-000AtV-C8 + for bitcoin-dev@lists.linuxfoundation.org; Wed, 08 Nov 2023 00:22:45 +0100 +Received: from [2001:9e8:8a6a:7000:3470:5b98:b585:72ae] (helo=smtpclient.apple) + by sslproxy01.your-server.de with esmtpsa + (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.92) + (envelope-from <robin@zerosync.org>) id 1r0VPB-000LL7-5r + for bitcoin-dev@lists.linuxfoundation.org; Wed, 08 Nov 2023 00:22:45 +0100 +From: Robin Linus <robin@zerosync.org> +Content-Type: multipart/alternative; + boundary="Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA" +Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) +Message-Id: <91D40E43-526E-42BC-BBBF-AABBD4F158F4@zerosync.org> +Date: Wed, 8 Nov 2023 00:22:44 +0100 +To: bitcoin-dev@lists.linuxfoundation.org +X-Mailer: Apple Mail (2.3654.120.0.1.13) +X-Authenticated-Sender: robin@zerosync.org +X-Virus-Scanned: Clear (ClamAV 0.103.10/27086/Tue Nov 7 09:39:18 2023) +X-Mailman-Approved-At: Tue, 07 Nov 2023 23:47:30 +0000 +Subject: [bitcoin-dev] Implementing Blake3 in Bitcoin Script +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.15 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Tue, 07 Nov 2023 23:22:49 -0000 + + +--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA +Content-Transfer-Encoding: quoted-printable +Content-Type: text/plain; + charset=us-ascii + +Good morning mailing list, + +We implemented a hash function in Bitcoin Script to verify Merkle = +inclusion proofs in the BitVM. This allows the VM to have sheer infinite = +memory, which doesn't have to get represented in expensive bit = +commitments. + +The following transaction demonstrates on-chain a Blake3 hash lock, = +which is unlocked by providing the preimage in the unlocking script: = +https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b3= +953309ffad6055f4b0?expand = +<https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b= +3953309ffad6055f4b0?expand> If you're curious, here you can find the = +source code: = +https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake3.js=20 + +We chose Blake3 as it seems to be one of the most simple modern hash = +functions in terms of instruction count. We implemented only a single = +round performed over a 64 byte message, because that's sufficient for us = +to verify Merkle paths. Our implementation represents u32 words as 4 = +separate bytes on the stack, because that seemed to be the optimal = +tradeoff to implement u32 addition, u32 bitwise XOR, and u32 bitwise = +rotations, as required for Blake3.=20 + +We used JavaScript as templating language, to assemble complex programs = +from relatively simple opcodes. You can find the implementation of our = +u32 opcodes here: https://github.com/BitVM/BitVM/tree/main/opcodes/u32 = +<https://github.com/BitVM/BitVM/tree/main/opcodes/u32> In particular, = +for the bitwise XOR we used some cool hacks with a lookup table for a = +helper function: = +https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md = +<https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md> + +Furthermore, we added a simple memory management, which allows us to = +have identifiers for variables, which we can read and write, and keep = +track of them while they're moved on the stack. For example, this allows = +us to implement the permutations of the Blake state simply by relabeling = +the identifiers of variables, instead of actually moving them around on = +the stack. + +In total, the script is about 100kB or 25k vBytes. That's fine for now = +to build a toy-version of BitVM, but the actual plan is to split up the = +Blake code, such that verifier and prover can reduce the required = +onchain data significantly by bisecting the execution in a = +challenge-response game instead of executing it fully. + + +Cheers,=20 +- Robin + + + + +Co-Founder and President + +ZeroSync +6300 Zug +Switzerland + +https://zerosync.org | https://twitter.com/zerosync_ + + +--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA +Content-Transfer-Encoding: quoted-printable +Content-Type: text/html; + charset=us-ascii + +<html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; = +-webkit-line-break: after-white-space;" class=3D""><div class=3D"">Good = +morning mailing list,</div><div class=3D""><br class=3D""></div><div = +class=3D"">We implemented a hash function in Bitcoin Script to verify = +Merkle inclusion proofs in the BitVM. This allows the VM to have sheer = +infinite memory, which doesn't have to get represented in expensive bit = +commitments.</div><div class=3D""><br class=3D""></div><div class=3D"">The= + following transaction demonstrates on-chain a Blake3 hash lock, which = +is unlocked by providing the preimage in the unlocking script: <a = +href=3D"https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc7= +6897b8b3953309ffad6055f4b0?expand" = +class=3D"">https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274= +bc76897b8b3953309ffad6055f4b0?expand</a> If you're curious, here = +you can find the source code: <a = +href=3D"https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake3.j= +s" = +class=3D"">https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake= +3.js</a> </div><div class=3D""><br class=3D""></div><div = +class=3D"">We chose Blake3 as it seems to be one of the most simple = +modern hash functions in terms of instruction count. We implemented only = +a single round performed over a 64 byte message, because that's = +sufficient for us to verify Merkle paths. Our implementation represents = +u32 words as 4 separate bytes on the stack, because that seemed to be = +the optimal tradeoff to implement u32 addition, u32 bitwise XOR, and u32 = +bitwise rotations, as required for Blake3. </div><div class=3D""><br = +class=3D""></div><div class=3D"">We used JavaScript as templating = +language, to assemble complex programs from relatively simple opcodes. = +You can find the implementation of our u32 opcodes here: <a = +href=3D"https://github.com/BitVM/BitVM/tree/main/opcodes/u32" = +class=3D"">https://github.com/BitVM/BitVM/tree/main/opcodes/u32</a> I= +n particular, for the bitwise XOR we used some cool hacks with a lookup = +table for a helper function: <a = +href=3D"https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md" = +class=3D"">https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md= +</a></div><div class=3D""><br class=3D""></div><div = +class=3D"">Furthermore, we added a simple memory management, which = +allows us to have identifiers for variables, which we can read and = +write, and keep track of them while they're moved on the stack. For = +example, this allows us to implement the permutations of the Blake state = +simply by relabeling the identifiers of variables, instead of actually = +moving them around on the stack.</div><div class=3D""><br = +class=3D""></div><div class=3D"">In total, the script is about 100kB or = +25k vBytes. That's fine for now to build a toy-version of BitVM, but the = +actual plan is to split up the Blake code, such that verifier and prover = +can reduce the required onchain data significantly by bisecting the = +execution in a challenge-response game instead of executing it = +fully.</div><div class=3D""><br class=3D""></div><div class=3D""><br = +class=3D""></div>Cheers, <div class=3D""><span style=3D"caret-color: = +rgb(0, 0, 0); color: rgb(0, 0, 0);" class=3D"">- Robin</span></div><div = +class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: = +rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div = +class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: = +rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div = +class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: = +rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div = +class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: = +rgb(0, 0, 0);" class=3D""><br class=3D""></span></font><div = +class=3D""><div dir=3D"auto" style=3D"caret-color: rgb(0, 0, 0); color: = +rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: = +0px; text-transform: none; white-space: normal; word-spacing: 0px; = +-webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: = +break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" = +class=3D""><div>Co-Founder and President</div><div><br = +class=3D"">ZeroSync</div><div>6300 = +Zug</div><div>Switzerland</div><div><br class=3D""><a = +href=3D"https://zerosync.org" class=3D"">https://zerosync.org</a> | <a = +href=3D"https://twitter.com/zerosync_" = +class=3D"">https://twitter.com/zerosync_</a><br class=3D""></div></div> +</div> +<br class=3D""></div></body></html>= + +--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA-- + |