[Halo2-Dev] Poseidon Hash Circuit

## 1. Overview In this article, we will explore how to implement circuits, the subject of proof in zero-knowledge proof protocols. There are various projects implementing zero-knowledge proof protocols, and among them, we will focus on understanding the design approach of the halo2 library, which utilizes lookup tables and custom gates for circuit construction. As a first step, let's analyze [Scroll's poseidon hash circuit](https://github.com/scroll-tech/poseidon-circuit) in halo2, which effectively utilizes custom gates, with particular emphasis on the crucial operation of Poseidon hash, the permutation. $\quad$ $\quad$ ## 2. Parameters and Basic Settings ### Recap ![](https://hackmd.io/_uploads/S1sFHvj-a.png) - $r$ stands for rate, representing the throughput equivalent to the length of data blocks, where data is processed in rate units. - $c$ stands for capacity, indicating higher security levels with larger values but potentially slower processing speed. - Number of rounds: In the sponge construction, permutation is applied iteratively over several rounds, and this parameter defines the number of iterations. - State: An intermediate calculation result updated during the permutation process. The length of the state is $t = r + c$, and its values change as rounds progress. $\quad$ ### Settings The following parameters can be configured in various combinations. However, when changing values, it's crucial to consider security. - S-box defined as $S(x) = x^5$ is used. - $R_f$ (Full Rounds) = $8$, $R_p$ (Partial Rounds) = $57$ - Capacity $c = 1$ - Rate $r = 2$ - Width ($t$) $= 3$ elements (Rate + Capacity) The number of rounds is configured as follows: $4$ half of full rounds ($R_f/2$) are followed by $57$ partial rounds $R_p$, and $4$ half of full rounds conclude the sequence. $\quad$ ### Notation In the notation used below, the index $k$ is defined within the range of $0\leq k< t$ for width $t$: - $\vec{s}[k]$: An advice column composed of states. - $s_i[k]$: The $i$-th state at the $k$-th round. - ${\vec{rc}}_{a}[k],{\vec{rc}}_{b}[k]$: Fixed columns composed of round constants. - $rc_i[k]$: The round constant for the $i$-th round. - $M, N$: MDS matrix and its inverse, defined as $t\times t$ matrices for width $t$. - $\vec{m_k} = (m_k[0], m_k[1],..., m_k[t-1])$: The $k$-th row vector of the $t\times t$ MDS matrix. - ${\vec{n}_k} = ({n}^{-1}_k[0], {n}^{-1}_k[1],..., {n}^{-1}_k[t-1])$: The $k$-th row vector of the $t\times t$ MDS inverse matrix. - ${\vec{s}}_{tmp}$: An advice column used only in partial rounds. - $\vec{s}_f, \vec{s}_{2p}, \vec{s}_{p}, \vec{s}_{paa}$: Selector columns consisting of $0$s and $1$s. $\quad$ ## 3. Circuit Design ### Gates Constituting Permutation Operations Here, I've presented the gates defined in the code in tabular form. Pink denotes the advice column, and light blue denotes the fixed column. In the tables below, ${{\vec{s}[0], \vec{s}[1], \vec{s}[2]}}$ represents the columns of states for a width $= 3$, and ${{\vec{rc_a}[0], \vec{rc_a}[1], \vec{rc_a}[2]}}$ and ${{\vec{rc_b}[0], \vec{rc_b}[1], \vec{rc_b}[2]}}$ represent vectors of round constants. The initial state is defined as ${{s_0[0], s_0[1], s_0[2]}}$, and the round constants added to it are $\color{#87AAB3}{{rc_0[0], rc_0[1], rc_0[2]}}$. $\quad$ - `full round` The first round of permutation starts with a full round. The table below depicts the regions of values defined relative to the selector $\vec{s}_f$. | $\color{#DAA7AA}{{\vec{s}[0]}}$ | $\color{#DAA7AA}{{\vec{s}[1]}}$ | $\color{#DAA7AA}{{\vec{s}[2]}}$ | $\color{#87AAB3}{{\vec{rc_a}[0]}}$ | $\color{#87AAB3}{{\vec{rc_a}[1]}}$ | $\color{#87AAB3}{{\vec{rc_a}[2]}}$ | $\color{#87AAB3}{{\vec{s}_f}}$ | | --- | --- | --- | --- | --- | --- | --- | | $\color{#DAA7AA}{{s_i[0]}}$ | $\color{#DAA7AA}{{s_i[1]}}$ | $\color{#DAA7AA}{{s_i[2]}}$ | $\color{#87AAB3}{{rc_i[0]}}$ | $\color{#87AAB3}{{rc_i[1]}}$ | $\color{#87AAB3}{{rc_i[2]}}$ | $\color{#87AAB3}{{v}}$ | | $\color{#DAA7AA}{{s_{i+1}[0]}}$ | $\color{#DAA7AA}{{s_{i+1}[1]}}$ | $\color{#DAA7AA}{{s_{i+1}[2]}}$ | | | | | To express the operation to be applied to the state of round $i$ in the full round, we define an expression as follows: $$ \begin{matrix} expr_k = \sum_{j=0..2}\{(s_i[j]+rc_i[j])^5*m_k[j]\} \end{matrix} $$ Then, $expr_k$ represents the constraint that must be satisfied to compute the state for round $i+1$. The constraints for the full round, defined in conjunction with the selector $\vec{s}_f$, can be expressed as follows, where we denote the value held by $\vec{s}_f$ as $v$: $$ \begin{matrix} v*(expr_0-s_{i+1}[0])=0\\ \quad \\ v*(expr_1-s_{i+1}[1])=0\\ \quad \\ v*(expr_2-s_{i+1}[2])=0 \end{matrix} $$ $\quad$ These equations imply that when $v=1$, $expr_k$ and $s_{i+1}[k]$ must be equal for $k=0,1,2$. If this condition is met, it confirms that the result of the full round operation has been correctly assigned to $s_{i+1}[k]$. - `partial round signle` This gate expresses almost identical to `full round`, with the difference being that the $x^5$ operation is only applied to the first state. | $\color{#DAA7AA}{{\vec{s}[0]}}$ | $\color{#DAA7AA}{{\vec{s}[1]}}$ | $\color{#DAA7AA}{{\vec{s}[2]}}$ | $\color{#87AAB3}{{\vec{rc}_a[0]}}$ | $\color{#87AAB3}{{\vec{rc}_a[1]}}$ | $\color{#87AAB3}{{\vec{rc}_a[2]}}$ | $\color{#87AAB3}{{\vec{s}_p}}$ | | --- | --- | --- | --- | --- | --- | --- | | $\color{#DAA7AA}{{s_i[0]}}$ | $\color{#DAA7AA}{{s_i[1]}}$ | $\color{#DAA7AA}{{s_i[2]}}$ | $\color{#87AAB3}{{a_i[0]}}$ | $\color{#87AAB3}{{a_i[1]}}$ | $\color{#87AAB3}{{a_i[2]}}$ | $\color{#87AAB3}{v}$ || | $\color{#DAA7AA}{{s_{i+1}[0]}}$ | $\color{#DAA7AA}{{s_{i+1}[1]}}$ | $\color{#DAA7AA}{{s_{i+1}[2]}}$ | | | | | The gate for the partial round single is defined in conjunction with the selector $\vec{s}_p$. In this case, to compute the next round's state, the operation is as follows: $$ \begin{matrix} expr_k =(s_i[0]+a_i[0])^5*m_k[0] + (s_i[1]+a_i[1])*m_k[1] +(s_i[2]+a_i[2])*m_k[2] \end{matrix} $$ Constraints are defined with the selector $\vec{s}_p$, and similarly, when we denote the value held by $\vec{s}_p$ as $v$, the constraints for the gate are as follows: $$ \begin{matrix} v*(expr_0-s_{i+1}[0])\\ \quad \\ v*(expr_1-s_{i+1}[1])\\ \quad \\ v*(expr_2-s_{i+1}[2]) \end{matrix} $$ - `partial round` In `partial round` circuit, constraints for two rounds are addressed at one row. To accomplish this, an additional advice column $\vec{s}_{tmp}$ and a fixed column $\vec{rc}_b[k]$ are allocated to apply constraints. $\vec{rc}_a[k]$ represents the constants for round $i$, while $\vec{rc}_b[k]$ designates the positions for the constants in round $i+1$. The primary goal is to reduce number of rows in the table form while ensuring the circuit meets the required constraints. By designing constraints carefully, it is possible to achieve desired results with fewer gate operations. | $\color{#DAA7AA}{{\vec{s}[0]}}$ | $\color{#DAA7AA}{{\vec{s}[1]}}$ | $\color{#DAA7AA}{{\vec{s}[2]}}$ | $\color{#DAA7AA}{{\vec{s}_{tmp}}}$ | $\color{#87AAB3}{{\vec{rc}_a[0]}}$ | $\color{#87AAB3}{{\vec{rc}_a[1]}}$ | $\color{#87AAB3}{{\vec{rc}_a[2]}}$ | $\color{#87AAB3}{{\vec{rc}_b[0]}}$ | $\color{#87AAB3}{{\vec{rc}_b[1]}}$ | $\color{#87AAB3}{{\vec{rc}_b[2]}}$ | $\color{#87AAB3}{{\vec{s}_{2p}}}$ | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | $\color{#DAA7AA}{{s_i[0]}}$ | $\color{#DAA7AA}{{s_i[1]}}$ | $\color{#DAA7AA}{{s_i[2]}}$ | $\color{#DAA7AA}{{t_i}}$ | $\color{#87AAB3}{{a_i[0]}}$ | $\color{#87AAB3}{{a_i[1]}}$ | $\color{#87AAB3}{{a_i[2]}}$ | $\color{#87AAB3}{{b_i[0]}}$ | $\color{#87AAB3}{{b_i[1]}}$ | $\color{#87AAB3}{{b_i[2]}}$ | $\color{#87AAB3}{v}$ | | $\color{#DAA7AA}{{s_{i+2}[0]}}$ | $\color{#DAA7AA}{{s_{i+2}[1]}}$ | $\color{#DAA7AA}{{s_{i+2}[2]}}$ | | | | | | | | | The partial round gates are defined based on the relative positions of the selector $\vec{s}_{2p}$, allowing multiple round constraints to be defined in a single row. These constraints produce equations that take the state at round $i$ as input and generate constraints for the state at round $i+2$. To do this, we define intermediate values needed to express the constraints. Let $t_i = (s_i[0] + a_i[0])^5$ represent the result of applying the nonlinear operation to the first state of round $i$. Then, we define the intermediate values required for defining partial round gates as follows: $\quad$ $\quad$ $$ \begin{matrix} mid_k = t_i*m_k[0] + (s_i[1]+a_i[1])*m_k[1] +(s_i[2]+a_i[2])*m_k[2]\\ \quad \\ next_k = s_{i+2}[0]*n_k[0] + s_{i+2}[1]*n_k[1] + s_{i+2}[2]*n_k[2] \end{matrix} $$ $\quad$ Here, $mid_k$ corresponds to the value associated with $s_{i+1}[k]$, while $next_k$ represents the state after adding the round constant to $s_{i+1}[k]$ and applying the nonlinear operation only to the first component. These values are related to $s_{i+1}[k]$ as follows: $\quad$ $$ \begin{matrix} next_0 = (s_{i+1}[0]+b_{i}[0])^5 \\ \quad \\ next_1 = s_{i+1}[1]+b_i[1] \\ \quad \\ next_2 = s_{i+1}[2]+b_i[2] \end{matrix} $$ $\quad$ The selector $\vec{s}_{2p}$ for the partial round in the current row is denoted as $v$, and the constraints for the gate are defined as: $\quad$ $$ \begin{matrix} v*(t_i - (s_i[0]+a_i[0])^5)=0\\ \quad \\ v*((mid_0+b_i[0])^5-next_0)=0\\ \quad \\ v*((mid_1+b_i[1])-next_1)=0\\ \quad \\ v*((mid_2+b_i[2])-next_2)=0 \end{matrix} $$ $\quad$ Under the condition $v=1$, these constraints can be added to the circuit, significantly reducing the number of rows compared to using only `partial round single` gates. $\quad$ ### Combining All Constraints The order of gate calls are as follows: 1. [Full Round] * 4 2. [Partial Round] * 28 3. [Partial Round Single] * 1 4. [Full Round] * 4 | $\textsf{row}$ | $\color{#DAA7AA}{\vec{s}[0]}$ | $\color{#DAA7AA}{\vec{s}[1]}$ | $\color{#DAA7AA}{\vec{s}[2]}$ | $\color{#DAA7AA}{\vec{s}_{tmp}}$ | $\color{#87AAB3}{\vec{rc}_a[0]}$ | $\color{#87AAB3}{\vec{rc}_a[1]}$ | $\color{#87AAB3}{\vec{rc}_a[2]}$ | $\color{#87AAB3}{\vec{rc}_b[0]}$ | $\color{#87AAB3}{\vec{rc}_b[1]}$ | $\color{#87AAB3}{\vec{rc}_b[2]}$ | $\color{#87AAB3}{\vec{s}_{f}}$ | $\color{#87AAB3}{\vec{s}_{2p}}$ | $\color{#87AAB3}{\vec{s}_p}$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $0$ | $\color{#DAA7AA}{s_0[0]}$ | $\color{#DAA7AA}{s_0[1]}$ | $\color{#DAA7AA}{s_0[2]}$ | $\color{#DAA7AA}{-}$ | $\color{#87AAB3}{rc_0[0]}$ | $\color{#87AAB3}{rc_0[1]}$ | $\color{#87AAB3}{rc_0[2]}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{1}$ | $\color{#87AAB3}{0}$ | $\color{#87AAB3}{0}$ | | $1$ |$\color{#DAA7AA}{s_1[0]}$ | $\color{#DAA7AA}{s_1[1]}$ | $\color{#DAA7AA}{s_1[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_1[0]}}$ | $\color{#87AAB3}{{rc_1[1]}}$ | $\color{#87AAB3}{{rc_1[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{1}$ | $\color{#87AAB3}{0}$ | $\color{#87AAB3}{0}$ | | $2$ |$\color{#DAA7AA}{s_2[0]}$ | $\color{#DAA7AA}{s_2[1]}$ | $\color{#DAA7AA}{s_2[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_2[0]}}$ | $\color{#87AAB3}{{rc_2[1]}}$ | $\color{#87AAB3}{{rc_2[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{1}$ | $\color{#87AAB3}{0}$ | $\color{#87AAB3}{0}$ | | $3$ |$\color{#DAA7AA}{s_3[0]}$ | $\color{#DAA7AA}{s_3[1]}$ | $\color{#DAA7AA}{s_3[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_3[0]}}$ | $\color{#87AAB3}{{rc_3[1]}}$ | $\color{#87AAB3}{{rc_3[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{1}$ | $\color{#87AAB3}{0}$ | $\color{#87AAB3}{0}$ | | $4$ |$\color{#DAA7AA}{s_4[0]}$ | $\color{#DAA7AA}{s_4[1]}$ | $\color{#DAA7AA}{s_4[2]}$ | $\color{#DAA7AA}{{t_4}}$ | $\color{#87AAB3}{{rc_4[0]}}$ | $\color{#87AAB3}{{rc_4[1]}}$ | $\color{#87AAB3}{{rc_4[2]}}$ | $\color{#87AAB3}{{rc_5[0]}}$ | $\color{#87AAB3}{{rc_5[1]}}$ | $\color{#87AAB3}{{rc_5[2]}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{1}}$ | $\color{#87AAB3}{{0}}$ | | $5$ |$\color{#DAA7AA}{s_6[0]}$ | $\color{#DAA7AA}{s_6[1]}$ | $\color{#DAA7AA}{s_6[2]}$ | $\color{#DAA7AA}{{t_6}}$ | $\color{#87AAB3}{{rc_6[0]}}$ | $\color{#87AAB3}{{rc_6[1]}}$ | $\color{#87AAB3}{{rc_6[2]}}$ | $\color{#87AAB3}{{rc_7[0]}}$ | $\color{#87AAB3}{{rc_7[1]}}$ | $\color{#87AAB3}{{rc_7[2]}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{1}}$ | $\color{#87AAB3}{{0}}$ | | $...$ | $\color{#DAA7AA}{{...}}$ | $\color{#DAA7AA}{{...}}$ | $\color{#DAA7AA}{{...}}$ | $\color{#DAA7AA}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | $\color{#87AAB3}{{...}}$ | | $31$ | $\color{#DAA7AA}{s_{58}[0]}$ | $\color{#DAA7AA}{s_{58}[1]}$ | $\color{#DAA7AA}{s_{58}[2]}$ | $\color{#DAA7AA}{{t_{58}}}$ | $\color{#87AAB3}{{rc_{58}[0]}}$ | $\color{#87AAB3}{{rc_{58}[1]}}$ | $\color{#87AAB3}{{rc_{58}[2]}}$ | $\color{#87AAB3}{{rc_{59}[0]}}$ | $\color{#87AAB3}{{rc_{59}[1]}}$ | $\color{#87AAB3}{{rc_{59}[2]}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{1}}$ | $\color{#87AAB3}{{0}}$ | | $32$ |$\color{#DAA7AA}{s_{60}[0]}$ | $\color{#DAA7AA}{s_{60}[1]}$ | $\color{#DAA7AA}{s_{60}[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_{60}[0]}}$ | $\color{#87AAB3}{{rc_{60}[1]}}$ | $\color{#87AAB3}{{rc_{60}[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{1}}$ | | $33$ |$\color{#DAA7AA}{s_{61}[0]}$ | $\color{#DAA7AA}{s_{61}[1]}$ | $\color{#DAA7AA}{s_{61}[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_{61}[0]}}$ | $\color{#87AAB3}{{rc_{61}[1]}}$ | $\color{#87AAB3}{{rc_{61}[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{{1}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{0}}$ | | $...$ | $\color{#DAA7AA}{...}$ | $\color{#DAA7AA}{...}$ | $\color{#DAA7AA}{...}$ | $\color{#DAA7AA}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{...}$ | $\color{#87AAB3}{..}$ | $\color{#87AAB3}{...}$ | | $36$ |$\color{#DAA7AA}{s_{64}[0]}$ | $\color{#DAA7AA}{s_{64}[1]}$ | $\color{#DAA7AA}{s_{64}[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{{rc_{64}[0]}}$ | $\color{#87AAB3}{{rc_{64}[1]}}$ | $\color{#87AAB3}{{rc_{64}[2]}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{{1}}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{0}}$ | | $37$ |$\color{#DAA7AA}{s_{65}[0]}$ | $\color{#DAA7AA}{s_{65}[1]}$ | $\color{#DAA7AA}{s_{65}[2]}$ | $\color{#DAA7AA}{{-}}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{-}$ | $\color{#87AAB3}{0}$ | $\color{#87AAB3}{{0}}$ | $\color{#87AAB3}{{0}}$ | $\quad$ The table above is filled with intermediate values generated during the permutation process, where ${s_i[k]}$ and ${rc_i[k]}$ represent the state and round constants in round $i$, respectively. ${\vec{s}_{tmp}}$ and ${\vec{rc}_b[k]}$ are advice columns and fixed columns allocated only during the `partial round`. The order in which the table values are filled depends on the progress of the rounds and follows this sequence: - The initial full round fills rows 0-3. - Partial rounds fill rows 4-32. - The final full round fills rows 33-36. Row 37 contains ${s_{65}[0], s_{65}[1], s_{65}[2]}$, which is the output of the permutation operation. The final table, including output rows, consists of 38 rows, 4 advice columns, and 9 fixed columns. $\quad$ ## 4. Code Analysis ### 1) Spec - `Spec` & `Mds` ```rust // Type for MDS and its inverse, which are square matrices of dimension T by T. pub(crate) type Mds<F, const T: usize> = [[F; T]; T]; // Define parameters for the Poseidon permutation. pub trait Spec<F: FieldExt, const T: usize, const RATE: usize>: fmt::Debug { fn full_rounds() -> usize; fn partial_rounds() -> usize; fn sbox(val: F) -> F; // If you hardcode constants(), this function is not required fn secure_mds() -> usize; // Generate (round_constants, mds, mds^-1) based on the specified parameters // You can also hardcode this if needed fn constants() -> (Vec<[F; T]>, Mds<F, T>, Mds<F, T>) { let r_f = Self::full_rounds(); let r_p = Self::partial_rounds(); let mut grain = grain::Grain::new(SboxType::Pow, T as u16, r_f as u16, r_p as u16); let round_constants = (0..(r_f + r_p)) .map(|_| { let mut rc_row = [F::zero(); T]; for (rc, value) in rc_row .iter_mut() .zip((0..T).map(|_| grain.next_field_element())) { *rc = value; } rc_row }) .collect(); let (mds, mds_inv) = mds::generate_mds::<F, T>(&mut grain, Self::secure_mds()); (round_constants, mds, mds_inv) } } ``` The `Spec` trait is short for specification and is used to define various parameters for the Poseidon permutation, such as the number of full and partial rounds, the `sbox` function, and the `Mds` matrices. The `constants` function, when called, returns the tuple`(round_constants, mds, mds^-1)`. `(round_constants, mds, mds^-1)`(which refers Round constants and MDS matrices, along with their inverses) are determined based on the width($T$), $R_f$, and $R_p$, and they can either be precomputed and hardcoded or calculated on the fly. $\quad$ ### 2) Pow5Chip Pow5Chip implements a permutation circuit consisting of the follwing rounds: [0-3 rows]: 4 * full rounds [4-31 rows]: 28 * (2 partial rounds) [32 rows]: 1 partial round [4-7 rows]: 4 * full rounds $\quad$ - `Pow5Config` ```rust pub struct Pow5Config<F: FieldExt, const WIDTH: usize, const RATE: usize> { pub(crate) state: [Column<Advice>; WIDTH], partial_sbox: Column<Advice>, rc_a: [Column<Fixed>; WIDTH], rc_b: [Column<Fixed>; WIDTH], s_full: Selector, s_partial: Selector, s_partial_single: Selector, s_pad_and_add: Selector, half_full_rounds: usize, half_partial_rounds: usize, alpha: [u64; 4], round_constants: Vec<[F; WIDTH]>, m_reg: Mds<F, WIDTH>, m_inv: Mds<F, WIDTH>, } ``` The values that make up the `Pow5Config` are as follows: `Advice` and `Fixed` represent the input and output values of each gate, while `Selector` is composed of values of 0 and 1, serving as switches to control whether to verify or skip the constraints of the gate. Other values are used either as `Fixed` or for defining the gates themselves. (Scroll implementation includes the `s_pad_and_add` selector, which is used to impose constraints on input padding, but it won't be covered in this article.) $\quad$ - `full round` ```rust meta.create_gate("full round", |meta| { let s_full = meta.query_selector(s_full); (0..WIDTH) .map(|next_idx| { let state_next = meta.query_advice(state[next_idx], Rotation::next()); let expr = (0..WIDTH) .map(|idx| { let state_cur = meta.query_advice(state[idx], Rotation::cur()); let rc_a = meta.query_fixed(rc_a[idx], Rotation::cur()); pow_5(state_cur + rc_a) * m_reg[next_idx][idx] }) .reduce(|acc, term| acc + term) .expect("WIDTH > 0"); s_full.clone() * (expr - state_next) }) .collect::<Vec<_>>() }); ``` The `create_gate` function for the `full round` defines gates for the full rounds as explained in Section 3. The `s_full` serves as a selector for the gates defined as full rounds. `state_cur` and `state_next` reference the advice column, while `rc_a` references the fixed column. `m_reg` represents internal values within the gate that are independent of input and output. $\quad$ - `partial round single` ```rust meta.create_gate("partial round single", |meta| { let s_partial_single = meta.query_selector(s_partial_single); (0..WIDTH) .map(|next_idx| { let state_next = meta.query_advice(state[next_idx], Rotation::next()); let cur_0 = meta.query_advice(state[0], Rotation::cur()); let rc_a0 = meta.query_fixed(rc_a[0], Rotation::cur()); let expr = pow_5(cur_0 + rc_a0) * m_reg[next_idx][0]; let expr = expr + (1..WIDTH) .map(|idx| { let state_cur = meta.query_advice(state[idx], Rotation::cur()); let rc_a = meta.query_fixed(rc_a[idx], Rotation::cur()); (state_cur + rc_a) * m_reg[next_idx][idx] }) .reduce(|acc, term| acc + term) .expect("WIDTH > 0"); s_partial_single.clone() * (expr - state_next) }) .collect::<Vec<_>>() }); ``` The `s_partial_single` serves as the selector for the gates defined as `partial round single`. `cur_0` and `rc_a0` respectively reference the advice column for the first state where the non-linear operation is applied, and the corresponding fixed column for the round constant. Similar to before, `m_reg` is used internally within the gate, ultimately defining the same constraint expressions as explained in Section 3. $\quad$ - `partial round` ```rust meta.create_gate("partial rounds", |meta| { let cur_0 = meta.query_advice(state[0], Rotation::cur()); let mid_0 = meta.query_advice(partial_sbox, Rotation::cur()); let rc_a0 = meta.query_fixed(rc_a[0], Rotation::cur()); let rc_b0 = meta.query_fixed(rc_b[0], Rotation::cur()); let s_partial = meta.query_selector(s_partial); use halo2_proofs::plonk::VirtualCells; let mid = |idx: usize, meta: &mut VirtualCells<F>| { let mid = mid_0.clone() * m_reg[idx][0]; (1..WIDTH).fold(mid, |acc, cur_idx| { let cur = meta.query_advice(state[cur_idx], Rotation::cur()); let rc_a = meta.query_fixed(rc_a[cur_idx], Rotation::cur()); acc + (cur + rc_a) * m_reg[idx][cur_idx] }) }; let next = |idx: usize, meta: &mut VirtualCells<F>| { (0..WIDTH) .map(|next_idx| { let next = meta.query_advice(state[next_idx], Rotation::next()); next * m_inv[idx][next_idx] }) .reduce(|acc, next| acc + next) .expect("WIDTH > 0") }; let partial_round_linear = |idx: usize, meta: &mut VirtualCells<F>| { let rc_b = meta.query_fixed(rc_b[idx], Rotation::cur()); mid(idx, meta) + rc_b - next(idx, meta) }; std::iter::empty() // state[0] round a .chain(Some(pow_5(cur_0 + rc_a0) - mid_0.clone())) // state[0] round b .chain(Some(pow_5(mid(0, meta) + rc_b0) - next(0, meta))) .chain((1..WIDTH).map(|idx| partial_round_linear(idx, meta))) .map(|exp| s_partial.clone() * exp) .collect::<Vec<_>>() }); ``` In the final part of gate definitions, variables defined within closures are chained together to generate the ultimate constraint expressions. - first chain function: It defines the difference between `mid_0` and the result of the non-linear operation. - Second chain function: It calls the first components of the closures `mid` and `next`. The operations defined within each closure are as follows: - `mid`: When the closure is called, it returns the state obtained by performing one partial round using the previously obtained value `mid_0`. In other words, it returns the state of the next round, which is $i+1$ round, given the current round $i$. - `next`: When the closure is called, it references the state corresponding to the `next``()` index, representing the values before performing the MDS operation. Here, `next``()` refers to the row immediately following the current row. As a result, in the second chain, it calculates the difference between the value obtained by performing the operations required to get the result for the next partial round on the first state of round $i+1$ (excluding the MDS matrix multiplication) and the value after applying the inverse operation of the MDS matrix to the first state of round $i+2$. - Third chain function: In `partial_round_linear`, it calls the components of `mid` and `next` except for the first components. It calls `mid` to add the round constants to the states of round $i+1$, and `next` to calculate the difference between the values. Furthermore, in the final `map` function, it defines the expressions for each operation in the chains that are connected, multiplied by `s_partial`, as the final vector. ## 5. Summary In this article, we've delved into the design approach for Scroll's Poseidon hash implementation code, focusing on how the circuit was constructed. Notably, it separated `partial round single` and `partial round` gates to define them differently. To express constraints for two rounds within a single row in `partial round`, an additional advice column and three fixed columns were introduced. This resulted in an increase of four columns but a reduction of $26$ rows. In the `partial round`, constraints for two rounds are expressed in a single row. To achieve this, the operations $ARC$, $s$-$box$, and $MDS$ for the $i$th round are stored as $mid_k$, while the state vector for the $i+2$ round utilizes the inverse operation of $MDS$ to establish connections with the $i+1$ round, thereby verifying the constraints. As a consequence, we introduced an additional advice column and three fixed columns. This resulted in an increase of 4 columns, but we managed to decrease by 26 rows. When using Halo2, the number of columns generally scales with proof size, while the number of rows influences the degree of polynomials during proof generation, affecting proof creation time. Therefore, the introduction of `partial round` gates is expected to increase proof size but reduce proof creation tㅑme. In environments where proof creation time significantly impacts performance, such optimization strategies are essential. The optimized design version of Scroll's Poseidon hash considers these aspects, and we'll delve into the details in the next post.