Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 602B7C0032 for ; 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 ; 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 ; 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 ; 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 ) 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 ) id 1r0VPB-000LL7-5r for bitcoin-dev@lists.linuxfoundation.org; Wed, 08 Nov 2023 00:22:45 +0100 From: Robin Linus 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 = 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 = 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 = 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
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/d8a091a7f5ffa4993681b3df688968fd274= bc76897b8b3953309ffad6055f4b0?expand If you're curious, here = you can find the source code: https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake= 3.js 

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. 

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 I= n 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=

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, 
- Robin




Co-Founder and President

ZeroSync
6300 = Zug
Switzerland

= --Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA--