Using an arithmetic hash in the LBT

[bpfarmer]

It looks like the Local Balance Tree uses Keccak as the hash function.

https://github.com/AggLayer/pessimistic-proof/blob/4ee985eae4d8ed85a48e46d8e83fe49dee383d77/pessimistic_proof/src/local_balance_tree.rs#L133

I don't think that this is strictly necessary, as we never need to access the LBT within the EVM. I think that using an arithmetic hash function should be much more efficient than using keccak here.

[puma314]

Actually in our zkVM, we haven't found a ton of gains from an arithmetic hash function (since it still translates to lots of RISC-V cycles and even if we were to precompile it, I think there might still be a lot of cycles). You could try sha256 and see if that cycle count is better.

[bpfarmer]

Interesting. My proposal would be to switch to an arithmetic-friendly hash function and write a precompile that verifies a path, not just a single hash. My intuition would be that this would yield non-trivial cost reduction, though maybe not with SP1.

Note that the LBTs should be relatively low-depth, but if we add nullifier sets, these trees will have much greater depth (log_2(number_of_chains) + fixed_LET_depth) and should represent a much larger potential cost savings.

Proving times are pretty high for what we're doing - do we have any profiling that shows where the cost is coming from?