Adds an R1CS implementation to the poseidon-permutation crate which poseidon377 now uses
Expected number of constraints
Looking at the paper, Table 1, we see various instantiations of Poseidon and the number of R1CS constraints per permutation:
For example in the first row we see that POSEIDON-80 has the following:
Arity: 2:1
R_F = 8
R_P = 33
Sbox = $x^5$, i.e. $\alpha = 5$
R1CS/perm. = 171
The arity means that the length of the state word row vector $\vec{w}$ is 3 (arity is rate:capacity, so 2 (rate) + 1 (capacity) = 3). The number of constraints added in the full rounds is:
For Poseidon377 using the same arity as the above case, but with our numbers of $\alpha=17, R_F = 8, R_P = 31$ for a test circuit doing a 2:1 hash, we have the R1CS constraint cost in the full rounds as:
So we expect 275, but currently have 270 in a test circuit doing the 2:1 hash exposed in the poseidon377 crate. The difference comes from the first full round, wherein we only add 10 constraints. This happens because the very first sbox is operating on a state words row vector where the first element is a constant, and the subsequent elements are the (witnessed) input words. If you modify the first element to also be a witness input word, you get 275 constraints as expected.
Closes #30
This PR:
poseidon-permutationcrate whichposeidon377now usesExpected number of constraints
Looking at the paper, Table 1, we see various instantiations of Poseidon and the number of R1CS constraints per permutation:
For example in the first row we see that POSEIDON-80 has the following:
2:1The arity means that the length of the state word row vector $\vec{w}$ is 3 (arity is rate:capacity, so 2 (rate) + 1 (capacity) = 3). The number of constraints added in the full rounds is:
$R_F (|\vec{w}| \lceil log_2{\alpha} \rceil) = 8 \times 3 \times 3 = 72$
Partial rounds:
$R_P \lceil log_2{\alpha} \rceil = 33 \times 3 = 99$
This gets us to the reported 171 from Table 1.
Poseidon377
For Poseidon377 using the same arity as the above case, but with our numbers of $\alpha=17, R_F = 8, R_P = 31$ for a test circuit doing a 2:1 hash, we have the R1CS constraint cost in the full rounds as:
$R_F (|\vec{w}| \lceil log_2{\alpha} \rceil) = 8 \times 3 \times 5 = 120$
In the partial rounds:
$R_P \lceil log_2{\alpha} \rceil = 31 \times 5 = 155$
So we expect 275, but currently have 270 in a test circuit doing the 2:1 hash exposed in the
poseidon377crate. The difference comes from the first full round, wherein we only add 10 constraints. This happens because the very first sbox is operating on a state words row vector where the first element is a constant, and the subsequent elements are the (witnessed) input words. If you modify the first element to also be a witness input word, you get 275 constraints as expected.