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