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 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 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.