ivc/poseidon_55_0_7_3_7/
interpreter.rs

1//! Implement an interpreter for a specific instance of the Poseidon inner permutation.
2//! The Poseidon construction is defined in the paper ["Poseidon: A New Hash
3//! Function"](https://eprint.iacr.org/2019/458.pdf).
4//! The Poseidon instance works on a state of size `STATE_SIZE` and is designed
5//! to work only with full rounds. As a reminder, the Poseidon permutation is a
6//! mapping from `F^STATE_SIZE` to `F^STATE_SIZE`.
7//! The user is responsible to provide the correct number of full rounds for the
8//! given field and the state.
9//! Also, it is hard-coded that the substitution is `7`. The user must verify
10//! that `7` is coprime with `p - 1` where `p` is the order the field.
11//! The constants and matrix can be generated the file
12//! `poseidon/src/pasta/params.sage`
13
14use crate::poseidon_55_0_7_3_7::columns::PoseidonColumn;
15use ark_ff::PrimeField;
16use kimchi_msm::circuit_design::{ColAccessCap, ColWriteCap, HybridCopyCap};
17use num_bigint::BigUint;
18use num_integer::Integer;
19
20/// Represents the parameters of the instance of the Poseidon permutation.
21/// Constants are the round constants for each round, and MDS is the matrix used
22/// by the linear layer.
23/// The type is parametrized by the field, the state size, and the number of full rounds.
24/// Note that the parameters are only for instances using full rounds.
25// IMPROVEME merge constants and mds in a flat array, to use the CPU cache
26// IMPROVEME generalise init_state for more than 3 elements
27pub trait PoseidonParams<F: PrimeField, const STATE_SIZE: usize, const NB_FULL_ROUNDS: usize> {
28    fn constants(&self) -> [[F; STATE_SIZE]; NB_FULL_ROUNDS];
29    fn mds(&self) -> [[F; STATE_SIZE]; STATE_SIZE];
30}
31
32/// Populates and checks one poseidon invocation.
33pub fn poseidon_circuit<
34    F: PrimeField,
35    const STATE_SIZE: usize,
36    const NB_FULL_ROUND: usize,
37    PARAMETERS,
38    Env,
39>(
40    env: &mut Env,
41    param: &PARAMETERS,
42    init_state: [Env::Variable; STATE_SIZE],
43) -> [Env::Variable; STATE_SIZE]
44where
45    PARAMETERS: PoseidonParams<F, STATE_SIZE, NB_FULL_ROUND>,
46    Env: ColWriteCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>
47        + HybridCopyCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>,
48{
49    // Write inputs
50    init_state.iter().enumerate().for_each(|(i, value)| {
51        env.write_column(PoseidonColumn::Input(i), value);
52    });
53
54    // Create, write, and constrain all other columns.
55    apply_permutation(env, param)
56}
57
58/// Apply the whole permutation of Poseidon to the state.
59/// The environment has to be initialized with the input values.
60pub fn apply_permutation<
61    F: PrimeField,
62    const STATE_SIZE: usize,
63    const NB_FULL_ROUND: usize,
64    PARAMETERS,
65    Env,
66>(
67    env: &mut Env,
68    param: &PARAMETERS,
69) -> [Env::Variable; STATE_SIZE]
70where
71    PARAMETERS: PoseidonParams<F, STATE_SIZE, NB_FULL_ROUND>,
72    Env: ColAccessCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>
73        + HybridCopyCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>,
74{
75    // Checking that p - 1 is coprime with 7 as it has to be the case for the sbox
76    {
77        let one = BigUint::from(1u64);
78        let p: BigUint = TryFrom::try_from(<F as PrimeField>::MODULUS).unwrap();
79        let p_minus_one = p - one.clone();
80        let seven = BigUint::from(7u64);
81        assert_eq!(p_minus_one.gcd(&seven), one);
82    }
83
84    let mut final_state: [Env::Variable; STATE_SIZE] =
85        core::array::from_fn(|_| Env::constant(F::zero()));
86
87    for i in 0..NB_FULL_ROUND {
88        let state: [PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>; STATE_SIZE] = {
89            if i == 0 {
90                core::array::from_fn(PoseidonColumn::Input)
91            } else {
92                core::array::from_fn(|j| PoseidonColumn::Round(i - 1, j))
93            }
94        };
95        let round_res = compute_one_round::<F, STATE_SIZE, NB_FULL_ROUND, PARAMETERS, Env>(
96            env, param, i, &state,
97        );
98
99        if i == NB_FULL_ROUND - 1 {
100            final_state = round_res
101        }
102    }
103
104    final_state
105}
106
107/// Compute one round the Poseidon permutation
108fn compute_one_round<
109    F: PrimeField,
110    const STATE_SIZE: usize,
111    const NB_FULL_ROUND: usize,
112    PARAMETERS,
113    Env,
114>(
115    env: &mut Env,
116    param: &PARAMETERS,
117    round: usize,
118    elements: &[PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>; STATE_SIZE],
119) -> [Env::Variable; STATE_SIZE]
120where
121    PARAMETERS: PoseidonParams<F, STATE_SIZE, NB_FULL_ROUND>,
122    Env: ColAccessCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>
123        + HybridCopyCap<F, PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>>,
124{
125    // We start at round 0
126    // This implementation mimicks the version described in
127    // poseidon_block_cipher in the mina_poseidon crate.
128    assert!(
129        round < NB_FULL_ROUND,
130        "The round index {:} is higher than the number of full rounds encoded in the type",
131        round
132    );
133    // Applying sbox
134    let state: Vec<Env::Variable> = elements
135        .iter()
136        .map(|x| {
137            let x_col = env.read_column(*x);
138            let x_square = x_col.clone() * x_col.clone();
139            let x_four = x_square.clone() * x_square.clone();
140            x_four.clone() * x_square.clone() * x_col.clone()
141        })
142        .collect();
143
144    // Applying the linear layer
145    let mds = PoseidonParams::mds(param);
146    let state: Vec<Env::Variable> = mds
147        .into_iter()
148        .map(|m| {
149            state
150                .clone()
151                .into_iter()
152                .zip(m)
153                .fold(Env::constant(F::zero()), |acc, (s_i, mds_i_j)| {
154                    Env::constant(mds_i_j) * s_i.clone() + acc.clone()
155                })
156        })
157        .collect();
158
159    // Adding the round constants
160    let state: Vec<Env::Variable> = state
161        .iter()
162        .enumerate()
163        .map(|(i, x)| {
164            let rc = env.read_column(PoseidonColumn::RoundConstant(round, i));
165            x.clone() + rc
166        })
167        .collect();
168
169    let res_state: Vec<Env::Variable> = state
170        .iter()
171        .enumerate()
172        .map(|(i, res)| env.hcopy(res, PoseidonColumn::Round(round, i)))
173        .collect();
174
175    res_state
176        .try_into()
177        .expect("Resulting state must be of STATE_SIZE length")
178}
ivc/poseidon_55_0_7_3_7/interpreter.rs

ivc/poseidon_55_0_7_3_7/
interpreter.rs
