Technical review of the Poseidon hash circuit

[qpzm]

I tried to solve these issues by understanding the Poseidon hash circuit.

Questions

1. Is the capacity length enough?
2. How to calculate the round parameters, like R_f and R_p?
3. What is the maximum length of currencies, N_CURRENCIES?
4. Why should the width be 2?

1. Capacity of c bits

p = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001 is the scalar field of the BN254 curve.
Let the width as t and the number of bits of a field element as n. capacity in bits c is calculated as follows.
The field element is 254 bits long and saved in 256 bits, so n = 256.

• Suppose p < 2^n
• N = n * t
  • N is the size of the permutation
• r = N − 2s bits per call
  • s is a desired security level s

we set the capacity to 2M and denote by POSEIDON-M a hash function that provides M bits of security against collision and preimage attacks.
Reference: Poseidon hash paper, Section 2.1

In generate_params.py, M is defined as 128, which corresponds to a 255-bit capacity, i.e., one field element.
Therefore, capacity = 1 and rate = t - 1 is enough.

https://github.com/summa-dev/summa-solvency/blob/d6e85c9affebef338846d5fb13e40eb8ab657811/zk_prover/src/circuits/merkle_sum_tree.rs#L242-L245

2. Round parameters

calc_round_numbers.py is based on the script used in the poseidon hash paper G Selecting Number of Rounds in General Case.
The number of full rounds R_f and the number of partial rounds R_p are the same for the width = 2 settings in the table.

According to the paper, S-box alpha = 5 is suitable for the BN254 curve.

S-box x^5 is suitable for two of the most popular prime fields in ZK applications, concretely the prime
subfields of the scalar field of the BLS12-381 and BN254 curves
Reference: Section 2.3

3. The maximum length of currencies, N_CURRENCIES

Constant-Input-Length Hashing. The capacity value is length · (2^64) + (o − 1) where o is the output length.
The padding consists of the field elements being 0.
Reference: Poseidon hash paper, Section 4.2 Domain Separation for POSEIDON

Poseidon is defined to map strings over F_p elements to o field elements according to the paper Section 2.

In our case, one field element, namely 256 bits are enough to represent 2^256 - 255 / (2^64) currencies.

• Both entry_chip and middle_chip returns only one field elements so o = 1.
• For the middle_chip, length = N_CURRENCIES + 2.
• capacity = length * (2^64) + 255

4. The optimistic rate of the poseidon hash

In merkle trees, the paper recommends to set the rate equal to the max number of child nodes in the tree.
In summa-solvency case, it is WIDTH=3, RATE=2. However, we have N_CURRENCIES more fields of the sum of currencies to hash. This raises a question about the best rate of the poseidon hash.

The code went through two updates.

• Update WIDTH=7, rate=6 -> WIDTH=3, RATE= 2
  • https://github.com/summa-dev/summa-solvency/pull/67/files#diff-a27e86b14a534341e580d33b415de7c620463165d491a6679b27f385b8d1d9d3L7-R7
• Update to WIDTH=2, rate=1
  • summa-dev/summa-solvency@21c54ac

The purpose seems to be not to increase the number of advice columns from 3 due to the poseidon hash.
https://github.com/summa-dev/summa-solvency/blob/d6e85c9affebef338846d5fb13e40eb8ab657811/zk_prover/src/circuits/merkle_sum_tree.rs#L160-L161

ETC

• In halo2_gadgets/src/poseidon/pow5.rs, tests are done using pasta curve, but summa uses bn254 curve. I tried writing tests but the fields are not public outside the crate, so zk_prover/src/poseidon/hash.rs cannot access and assert them.

#[derive(Clone, Debug)]
pub struct Pow5Config<F: Field, const WIDTH: usize, const RATE: usize> {
    pub(crate) state: [Column<Advice>; WIDTH],

https://github.com/privacy-scaling-explorations/poseidon-gadget/blob/main/src/poseidon/pow5.rs#L22

These are tests using pasta curve.
https://github.com/privacy-scaling-explorations/poseidon-gadget/blob/main/src/poseidon/pow5.rs#L599

Reference

• Poseidon hash paper: https://eprint.iacr.org/2019/458.pdf