From: Robin Linus <robin@zerosync•org>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: [bitcoin-dev] Implementing Blake3 in Bitcoin Script
Date: Wed, 8 Nov 2023 00:22:44 +0100 [thread overview]
Message-ID: <91D40E43-526E-42BC-BBBF-AABBD4F158F4@zerosync.org> (raw)
[-- Attachment #1: Type: text/plain, Size: 2518 bytes --]
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/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b3953309ffad6055f4b0?expand <https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b3953309ffad6055f4b0?expand> If you're curious, here you can find the source code: https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake3.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 <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,
- Robin
Co-Founder and President
ZeroSync
6300 Zug
Switzerland
https://zerosync.org | https://twitter.com/zerosync_
[-- Attachment #2: Type: text/html, Size: 4367 bytes --]
reply other threads:[~2023-11-07 23:22 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=91D40E43-526E-42BC-BBBF-AABBD4F158F4@zerosync.org \
--to=robin@zerosync$(echo .)org \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox