This article first appeared on Medium.
MiMC is a “ZK-friendly” hash function, for which efficient Zero Knowledge Proofs (ZKP) can be generated.
Previously we discussed that ZKP can be applied to any mathematical function using zk-SNARK. Internally, the function must be converted into a circuit, where only addition and multiplication operations are allowed. While all functions can be converted in theory, in practice the circuit of some functions is smaller and their ZKP is less expensive than those of others. For example, SHA256 requires a lot of bitwise operations and is therefore among the most expensive in terms of circuit size.
The MiMC hash function is specifically designed to minimize the circuit size and hence the ZKP cost by using only additions and multiplications. It doesn’t, while making it extremely expensive to reverse-engineer the hash pre-image.
Hash function can be found in many applications such as commitment schema, signature and Merkle trees. MiMC is a good candidate hash function when efficient ZKP is needed.
To hash a single number Xthe following function is calculated:
r is the number of turns, Fᵢ is the round function for round I and k This is the key. ∘ is the composition of the function.
Fᵢ is defined as:
cᵢ are the round constants and c₀=0.
r rounds of MiMC: Eₖ(x)
Here is an implementation of MiMC:
chop() in line 1 calculates Eₖ(X). multiHash() hashes an arbitrarily long input xswhere the intermediate result back is introduced in the next iteration at line 17. All operations are defined in the module P.
A test can also be found here.
Watch: Presentation of the BSV Global Blockchain Convention, Smart Contracts and Computation on BSV
New to Bitcoin? Discover CoinGeek bitcoin for beginners section, the ultimate resource guide to learn about bitcoin – as originally envisioned by Satoshi Nakamoto – and blockchain.