In this Part, we will walk through the mimc7.py example.
Chapter 1: MiMC7 Concepts#
MiMC7 is a zk-friendly hash function. By “zk-friendly” we mean that the function is designed to minimize circuit size for zero knowledge proofs by using only additions and multiplications. Other common non-zk-friendly hash functions such as SHA256 requires many bit operations and therefore can be very costly in terms of circuit size.
MiMC7’s algorithm is very simple. It’s composed of 3 variables. \(x\) is the input and also the result after each round of calculations. \(k\) is the key and doesn’t change across the rounds. \(c_i\) is the round constant and is a pre-determined list of numbers distinct for each round. In each round, we perform the following calculation, where the output \(F_i(x)\) for one round is the input \(x\) for the next round:
$F_i(x) = (x + k + c_i)^7$
After all rounds, we calculate the output as the result from the final round plus \(k\):
$Output = F_{91}(x) + k$
There are 91 rounds in total in MiMC7 and therefore 91 \(c_i\) constants. In Chiquito, to express this mathematical relationship, it’s intuitive to construct 3 signals for \(x\), \(k\) and \(c_i\). Furthermore, for better expression of the MiMC7 equation, we create two more signals \(xkc\) and \(y\), where \(xkc = x + k + c_i\) and \(y = xkc^7\). Note that in this tutorial we refer to the 91 rounds as the 0th through 90th rounds or 0th through 90th rows. The output calculation is referred to as the output round or output row.
For a better feel of the calculation, we plug in some numbers. Set our input message \(x\) to 0 for the 0th round, the key \(k\) to 1 for all rounds. Round constants \(c_i\) are usually huge but for this toy example let’s just assume \(c_0 = 0\), \(c_1 = 1\), \(c_2 = 2\), \(c_3 = 0\) for the 0th through 3rd rounds.
Therefore, for the 0th round, we have:
\(x = 0\)
\(k = 1\)
\(c_0 = 0\)
\(xkc = 0 + 1 + 0 = 1\)
\(y = xkc^7 = 1^7 = 1\)
For the 1st round, we have:
\(x = 1\)
\(k = 1\)
\(c_1 = 1\)
\(xkc = 1 + 1 + 1 = 3\)
\(y = xkc^7 = 3^7 = 2183\)
For the 2nd round, we have:
\(x = 2183\)
\(k = 1\)
\(c_2 = 2\)
\(xkc = 2183 + 1 + 2 = 2186\)
\(y = xkc^7 = 2186^7 = 238534446168822298080896\)
For the 3rd round, we have:
\(x = 238534446168822298080896\)
\(k = 1\)
\(c_3 = 0\)
\(xkc = 238534446168822298080896 + 1 + 0 = 238534446168822298080897\)
\(y = xkc^7 = 238534446168822298080897^7 \mod p = 13936292545083981204475079684474676334933008887368755327375281694396644515858\)
Note that due to the exponentiate by 7 nature, MiMC7 round outputs get blown up very quickly. Therefore, all variables are calculated mod p on a prime field, where p is the field modulus. Plugging in these numbers, we have the following signal table:
Round |
Signals |
||||
|---|---|---|---|---|---|
x |
k |
c |
xkc |
y |
|
0th |
0 |
1 |
1 |
1 |
1 |
1st |
1 |
1 |
1 |
3 |
2183 |
2nd |
2183 |
1 |
2 |
2186 |
2385…0896 |
3rd |
2385…0896 |
1 |
0 |
2385…0897 |
1393…5858 |
4th-89th |
… |
… |
… |
… |
… |
90th |
… |
… |
… |
… |
\(y_90\) |
output |
\(x_{91} = y_{90}\) |
1 |
n.a. |
n.a. |
\(output = x_{91} + k\) |
For these signals, we need the following constraints:
x + k + c = xkc
xkc^7 = y
y = x in the next row
k = k in the next row
For the output row, we only constrain that:
output = x + k
Therefore, we would need 2 step types: MiMC7Step for the 0th through 90th rounds, and MiMC7LastStep for the output round. Additionally, because x and k are sometimes referred to as their rotation in the next step, they are declared as forward signals. All other signals are declared as internal signals. Finally, constraints that involve rotated signals (for example, signals in their next steps) are declared as transition constraints.
Step Type |
Round |
Signals |
Setups |
||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
x |
k |
c |
xkc |
y |
output |
constraint 1 |
constraint 2 |
transition 1 |
transition 2 |
||
MiMC7Step |
0th |
0 |
1 |
1 |
1 |
1 |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7Step |
1st |
1 |
1 |
1 |
3 |
2183 |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7Step |
2nd |
2183 |
1 |
2 |
2186 |
2385…0896 |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7Step |
3rd |
2385…0896 |
1 |
0 |
2385…0897 |
1393…5858 |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7Step |
4th-89th |
… |
… |
… |
… |
… |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7Step |
90th |
… |
… |
… |
… |
\(y_{90}\) |
n.a. |
x+k+c==xkc |
xkc^7==y |
y==x.next |
k==k.next |
MiMC7LastStep |
output |
\(x_{91} = y_{90}\) |
1 |
n.a. |
n.a. |
\(output = x_{91} + k\) |
n.a. |
n.a. |
n.a. |
n.a. |
output==x+k |
With these, we are ready to construct our first attempt of the MiMC7 circuit.