arrabbiata/
column.rs

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

arrabbiata/
column.rs
