ZK friendly hash function MiMC Sponge

[tzilkha]

(Initially brought up in the NEAR Zero Knowledge Community Group)

From first hand experience trying to implement a ZK-SNARK application on NEAR, there seems to be a lack of resources regarding SNARK-friendly hash functions. Out of all the Rust implementations that are out there, they all exceed maximum GAS.

Popular Poseidon implementation in Rust cannot run once without exceeding GAS.

A reimplementation of some of the common SNARK-friendly hash functions and/or precompiles would be super useful for the ZK community.

As a proof of concept, we have optimized MiMC Sponge to run efficiently (can be executed more than 25 times in a single transaction), compatible with common frameworks (such as Circom, Zokrates).

[mfornet]

Out of all the Rust implementations that are out there, they all exceed maximum GAS.

I guess you have tried compiling them to wasm and executing them on NEAR. What if proper host functions are implemented so that zk primitives run natively? Potentially even that won't be enough, given the restriction that the execution must be in less than one second.

As a proof of concept, we have optimized MiMC Sponge to run efficiently (can be executed more than 25 times in a single transaction), compatible with common frameworks (such as Circom, Zokrates).

Do you have some project live or code you can share?

[tzilkha]

Yeah, tried compiling and executing them on NEAR. Could you clarify what you mean by running them natively?

Implementation of MiMC
https://github.com/tzilkha/mimc-sponge-rs

Working example
https://github.com/curryrasul/voan

I believe VOAN only hashes a few times per call, but calling it 25 times on a smart contract, either on locally/testnet works just fine.

[mfornet]

By running natively, I mean running it inside a precompile (host function). The point is that putting it inside a host function will give you the ability to run that code compiled natively to the target machine rather than running it on the wasm runtime. This is how some cryptographic primitives work today for efficiency.

[tzilkha]

Thanks for clarifying. Yes! That is what I meant in the proposal.

[MaksymZavershynskyi]

@abacabadabacaba What's your opinion?

[abacabadabacaba]

Do other blockchains implement this? If not, it will be necessary to do a thorough review of how this may be used, because presumably the apps using this will not have analogues on other blockchains.

[tzilkha]

Theres no MiMC precompile on Ethereum at the moment. Iden3 people created EVM bytecode for it - easy to use it efficiently (as seen with TornadoCash).
I know that Eli Ben Sasson started a conversation on adding Poseidon as a precompile for Ethereum - ethereum/EIPs#5988 - this discussion is live and active.
Not sure what the status is on other chains.

[snjax]

The purpose of using snark-friendly hash on VM-level is very rare: for building snark-friendly Merkle trees. Generally, most of the issues are solvable without snark-friendly hash functions on the VM side.

If you are finding a tradeoff between CPU and zk, look at sinsemilla hash - with plookup it is cheap, and on CPU side it is not very expensive.