Hash Function Decision

[Stebalien]

We're settling on using merkle-trees for in several places (e.g., see #150 and #166) but we haven't settled on the hash function. This matters because, unfortunately, the EVM.

So, I'm going to suggest keccak256 to be EVM friendly, even though we don't use it anywhere else. Otherwise validating merkle-trees could get a bit expensive.

That is, unless someone has a suggestion for a different snark-friendly hash function? But I'm not aware of an efficient snark-friendly hash function.

[Kubuxu]

blake2b (or even blake3) might be a better option for snarks, I would have to look into keccak256 padding rules to check if it has the same issue as SHA2/3 where hashing 64bytes requires two invocations of compression function due to padding rules.

blake2/3 has precompile in EVM land AFAIK

[Stebalien]

If we were hashing a single large object, sha256 would be fine. But... the EVM charges 700 gas per call to the SHA2 precompile.

On the other hand, there's a KECCAK256 opcode that costs 30 gas plus 6 gas per word. So, validating a Keccak merkle-tree is much cheaper.

[Stebalien]

Note: it looks like CometBLS uses MiMC for zk compatibility. IMO, this won't matter until we create a snark-friendly power table as we're planning on doing all of our hashing outside of snarks anyways.

[Stebalien]

We're using keccak256 for the merkle-trees.