arrabbiata/
column.rs

1use crate::{challenge::ChallengeTerm, interpreter::Instruction};
2use kimchi::circuits::expr::{CacheId, ConstantExpr, Expr, FormattedOutput};
3use std::collections::HashMap;
4use strum_macros::{EnumCount as EnumCountMacro, EnumIter};
5
6use crate::NUMBER_OF_COLUMNS;
7
8/// This enum represents the different gadgets that can be used in the circuit.
9/// The selectors are defined at setup time, can take only the values `0` or
10/// `1` and are public.
11// IMPROVEME: should we merge it with the Instruction enum?
12// It might not be that obvious to do so, as the Instruction enum could be
13// defining operations that are not "fixed" in the circuit, but rather
14// depend on runtime values (e.g. in a zero-knowledge virtual machine).
15#[derive(Debug, Clone, Copy, PartialEq, EnumCountMacro, EnumIter, Eq, Hash)]
16pub enum Gadget {
17    /// A dummy gadget, doing nothing. Use for padding.
18    NoOp,
19
20    /// The gadget defining the app.
21    ///
22    /// For now, the application is considered to be a one-line computation.
23    /// However, we want to see the application as a collection of reusable
24    /// gadgets.
25    ///
26    /// See `<https://github.com/o1-labs/proof-systems/issues/3074>`
27    App,
28    // Elliptic curve related gadgets
29    EllipticCurveAddition,
30    EllipticCurveScaling,
31    /// The following gadgets implement the Poseidon hash instance described in
32    /// the top-level documentation. In the current setup, with
33    /// [crate::NUMBER_OF_COLUMNS] columns, we can compute 5 full
34    /// rounds per row.
35    ///
36    /// We split the Poseidon gadget in 13 sub-gadgets, one for each set of 5
37    /// full rounds and one for the absorbtion. The parameter is the starting
38    /// round of Poseidon. It is expected to be a multiple of five.
39    ///
40    /// Note that, for now, the gadget can only be used by the verifier circuit.
41    PoseidonFullRound(usize),
42    /// Absorb [PlonkSpongeConstants::SPONGE_WIDTH - 1] elements into the
43    /// sponge. The elements are absorbed into the last
44    /// [PlonkSpongeConstants::SPONGE_WIDTH - 1] elements of the permutation
45    /// state.
46    ///
47    /// The values to be absorbed depend on the state of the environment while
48    /// executing this instruction.
49    ///
50    /// Note that, for now, the gadget can only be used by the verifier circuit.
51    PoseidonSpongeAbsorb,
52}
53
54/// Convert an instruction into the corresponding gadget.
55impl From<Instruction> for Gadget {
56    fn from(val: Instruction) -> Gadget {
57        match val {
58            Instruction::NoOp => Gadget::NoOp,
59            Instruction::PoseidonFullRound(starting_round) => {
60                Gadget::PoseidonFullRound(starting_round)
61            }
62            Instruction::PoseidonSpongeAbsorb => Gadget::PoseidonSpongeAbsorb,
63            Instruction::EllipticCurveScaling(_i_comm, _s) => Gadget::EllipticCurveScaling,
64            Instruction::EllipticCurveAddition(_i) => Gadget::EllipticCurveAddition,
65        }
66    }
67}
68
69#[derive(Debug, Clone, Copy, PartialEq)]
70pub enum Column {
71    Selector(Gadget),
72    PublicInput(usize),
73    X(usize),
74}
75
76/// Convert a column to a usize. This is used by the library [mvpoly] when we
77/// need to compute the cross-terms.
78/// For now, only the private inputs and the public inputs are converted,
79/// because there might not need to treat the selectors in the polynomial while
80/// computing the cross-terms (FIXME: check this later, but pretty sure it's the
81/// case).
82///
83/// Also, the [mvpoly::monomials] implementation of the trait [mvpoly::MVPoly]
84/// will be used, and the mapping here is consistent with the one expected by
85/// this implementation, i.e. we simply map to an increasing number starting at
86/// 0, without any gap.
87impl From<Column> for usize {
88    fn from(val: Column) -> usize {
89        match val {
90            Column::X(i) => i,
91            Column::PublicInput(i) => NUMBER_OF_COLUMNS + i,
92            Column::Selector(_) => unimplemented!("Selectors are not supported. This method is supposed to be called only to compute the cross-term and an optimisation is in progress to avoid the inclusion of the selectors in the multi-variate polynomial."),
93        }
94    }
95}
96
97pub type E<Fp> = Expr<ConstantExpr<Fp, ChallengeTerm>, Column>;
98
99impl From<Gadget> for usize {
100    fn from(val: Gadget) -> usize {
101        match val {
102            Gadget::NoOp => 0,
103            Gadget::App => 1,
104            Gadget::EllipticCurveAddition => 2,
105            Gadget::EllipticCurveScaling => 3,
106            Gadget::PoseidonSpongeAbsorb => 4,
107            Gadget::PoseidonFullRound(starting_round) => {
108                assert_eq!(starting_round % 5, 0);
109                5 + starting_round / 5
110            }
111        }
112    }
113}
114
115// Code to allow for pretty printing of the expressions
116impl FormattedOutput for Column {
117    fn latex(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
118        match self {
119            Column::Selector(sel) => match sel {
120                Gadget::NoOp => "q_noop".to_string(),
121                Gadget::App => "q_app".to_string(),
122                Gadget::EllipticCurveAddition => "q_ec_add".to_string(),
123                Gadget::EllipticCurveScaling => "q_ec_mul".to_string(),
124                Gadget::PoseidonSpongeAbsorb => "q_pos_sponge_absorb".to_string(),
125                Gadget::PoseidonFullRound(starting_round) => {
126                    format!("q_pos_full_round_{}", starting_round)
127                }
128            },
129            Column::PublicInput(i) => format!("pi_{{{i}}}").to_string(),
130            Column::X(i) => format!("x_{{{i}}}").to_string(),
131        }
132    }
133
134    fn text(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
135        match self {
136            Column::Selector(sel) => match sel {
137                Gadget::NoOp => "q_noop".to_string(),
138                Gadget::App => "q_app".to_string(),
139                Gadget::EllipticCurveAddition => "q_ec_add".to_string(),
140                Gadget::EllipticCurveScaling => "q_ec_mul".to_string(),
141                Gadget::PoseidonSpongeAbsorb => "q_pos_sponge_absorb".to_string(),
142                Gadget::PoseidonFullRound(starting_round) => {
143                    format!("q_pos_full_round_{}", starting_round)
144                }
145            },
146            Column::PublicInput(i) => format!("pi[{i}]"),
147            Column::X(i) => format!("x[{i}]"),
148        }
149    }
150
151    fn ocaml(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
152        // FIXME
153        unimplemented!("Not used at the moment")
154    }
155
156    fn is_alpha(&self) -> bool {
157        // FIXME
158        unimplemented!("Not used at the moment")
159    }
160}
arrabbiata/column.rs

arrabbiata/
column.rs
