search

filecoin-project / go-f3

Golang implementation of Fast Finality in Filecoin (F3)
Apache License 2.0
6 stars 4 forks source link

Hash Function Decision #182

Closed Stebalien closed 2 months ago

Stebalien commented 2 months ago

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 commented 2 months ago

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 commented 2 months ago

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 commented 2 months ago

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 commented 2 months ago

We're using keccak256 for the merkle-trees.