ivc/poseidon_8_56_5_3_2/
columns.rs

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

ivc/poseidon_8_56_5_3_2/
columns.rs
