ivc/poseidon_55_0_7_3_2/
columns.rs

1/// The column layout will be as follow, supposing a state size of 3 elements:
2///
3/// ```text
4/// | C1 | C2 | C3 | C4  | C5  | C6  | ... | C_(k) | C_(k + 1) | C_(k + 2) |
5/// |--- |----|----|-----|-----|-----|-----|-------|-----------|-----------|
6/// |  x |  y | z  | x'  |  y' |  z' | ... |  x''  |     y''   |    z''    |
7///                | MDS \circ SBOX  |     |        MDS \circ SBOX         |
8///                |-----------------|     |-------------------------------|
9///                   Divided in 5
10///                 blocks of degree 2
11///                   constraints
12/// ```
13///
14/// where (x', y', z') = MDS(x^7, y^7, z^7), i.e. the result of the linear
15/// layer.
16///
17/// We will have, for N full rounds:
18/// - `3` input columns
19/// - `5 N * 3` round columns, indexed by the round number and the index in the
20///   state, the number of rounds.
21use kimchi_msm::columns::{Column, ColumnIndexer};
22
23#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
24pub enum PoseidonColumn<const STATE_SIZE: usize, const NB_FULL_ROUND: usize> {
25    Input(usize),
26    // nb round, state
27    // we use the constraint:
28    // y = x * x  -> x^2 -> i
29    // y' = y * y -> x^4 -> i + 1
30    // y'' = y * y' -> x^6 -> i + 2
31    // z = y'' * x -> i + 3
32    // z * MDS -> i + 4
33    // --> 5 * state, nb round
34    Round(usize, usize),
35    RoundConstant(usize, usize),
36}
37
38impl<const STATE_SIZE: usize, const NB_FULL_ROUND: usize> ColumnIndexer<usize>
39    for PoseidonColumn<STATE_SIZE, NB_FULL_ROUND>
40{
41    // - STATE_SIZE input columns
42    // - for each round:
43    //   - STATE_SIZE state columns for x^2 -> x * x
44    //   - STATE_SIZE state columns for x^4 -> x^2 * x^2
45    //   - STATE_SIZE state columns for x^6 -> x^4 * x^2
46    //   - STATE_SIZE state columns for x^7 -> x^6 * x
47    //   - STATE_SIZE state columns for x^7 * MDS(., L)
48    // - STATE_SIZE * NB_FULL_ROUND constants
49    const N_COL: usize = STATE_SIZE + 5 * NB_FULL_ROUND * STATE_SIZE;
50
51    fn to_column(self) -> Column<usize> {
52        match self {
53            PoseidonColumn::Input(i) => {
54                assert!(i < STATE_SIZE);
55                Column::Relation(i)
56            }
57            PoseidonColumn::Round(round, state_index) => {
58                assert!(state_index < 5 * STATE_SIZE);
59                // We start round 0
60                assert!(round < NB_FULL_ROUND);
61                let idx = STATE_SIZE + (round * 5 * STATE_SIZE + state_index);
62                Column::Relation(idx)
63            }
64            PoseidonColumn::RoundConstant(round, state_index) => {
65                assert!(state_index < STATE_SIZE);
66                // We start round 0
67                assert!(round < NB_FULL_ROUND);
68                let idx = round * STATE_SIZE + state_index;
69                Column::FixedSelector(idx)
70            }
71        }
72    }
73}
ivc/poseidon_55_0_7_3_2/columns.rs

ivc/poseidon_55_0_7_3_2/
columns.rs
