halo2_proofs/
circuit.rs

Help
1//! Traits and structs for implementing circuit components.
2
3use std::{convert::TryInto, fmt, marker::PhantomData};
4
5use ff::Field;
6
7use crate::{
8    arithmetic::FieldExt,
9    plonk::{Advice, Any, Assigned, Column, Error, Fixed, Instance, Selector, TableColumn},
10};
11
12pub mod floor_planner;
13pub use floor_planner::single_pass::SimpleFloorPlanner;
14
15pub mod layouter;
16
17/// A chip implements a set of instructions that can be used by gadgets.
18///
19/// The chip stores state that is required at circuit synthesis time in
20/// [`Chip::Config`], which can be fetched via [`Chip::config`].
21///
22/// The chip also loads any fixed configuration needed at synthesis time
23/// using its own implementation of `load`, and stores it in [`Chip::Loaded`].
24/// This can be accessed via [`Chip::loaded`].
25pub trait Chip<F: FieldExt>: Sized {
26    /// A type that holds the configuration for this chip, and any other state it may need
27    /// during circuit synthesis, that can be derived during [`Circuit::configure`].
28    ///
29    /// [`Circuit::configure`]: crate::plonk::Circuit::configure
30    type Config: fmt::Debug + Clone;
31
32    /// A type that holds any general chip state that needs to be loaded at the start of
33    /// [`Circuit::synthesize`]. This might simply be `()` for some chips.
34    ///
35    /// [`Circuit::synthesize`]: crate::plonk::Circuit::synthesize
36    type Loaded: fmt::Debug + Clone;
37
38    /// The chip holds its own configuration.
39    fn config(&self) -> &Self::Config;
40
41    /// Provides access to general chip state loaded at the beginning of circuit
42    /// synthesis.
43    ///
44    /// Panics if called before `Chip::load`.
45    fn loaded(&self) -> &Self::Loaded;
46}
47
48/// Index of a region in a layouter
49#[derive(Clone, Copy, Debug)]
50pub struct RegionIndex(usize);
51
52impl From<usize> for RegionIndex {
53    fn from(idx: usize) -> RegionIndex {
54        RegionIndex(idx)
55    }
56}
57
58impl std::ops::Deref for RegionIndex {
59    type Target = usize;
60
61    fn deref(&self) -> &Self::Target {
62        &self.0
63    }
64}
65
66/// Starting row of a region in a layouter
67#[derive(Clone, Copy, Debug, PartialEq, Eq)]
68pub struct RegionStart(usize);
69
70impl From<usize> for RegionStart {
71    fn from(idx: usize) -> RegionStart {
72        RegionStart(idx)
73    }
74}
75
76impl std::ops::Deref for RegionStart {
77    type Target = usize;
78
79    fn deref(&self) -> &Self::Target {
80        &self.0
81    }
82}
83
84/// A pointer to a cell within a circuit.
85#[derive(Clone, Copy, Debug)]
86pub struct Cell {
87    /// Identifies the region in which this cell resides.
88    region_index: RegionIndex,
89    /// The relative offset of this cell within its region.
90    row_offset: usize,
91    /// The column of this cell.
92    column: Column<Any>,
93}
94
95/// An assigned cell.
96#[derive(Clone, Debug)]
97pub struct AssignedCell<V, F: Field> {
98    value: Option<V>,
99    cell: Cell,
100    _marker: PhantomData<F>,
101}
102
103impl<V, F: Field> AssignedCell<V, F> {
104    /// Returns the value of the [`AssignedCell`].
105    pub fn value(&self) -> Option<&V> {
106        self.value.as_ref()
107    }
108
109    /// Returns the cell.
110    pub fn cell(&self) -> Cell {
111        self.cell
112    }
113}
114
115impl<V, F: Field> AssignedCell<V, F>
116where
117    for<'v> Assigned<F>: From<&'v V>,
118{
119    /// Returns the field element value of the [`AssignedCell`].
120    pub fn value_field(&self) -> Option<Assigned<F>> {
121        self.value().map(|v| v.into())
122    }
123}
124
125impl<F: Field> AssignedCell<Assigned<F>, F> {
126    /// Evaluates this assigned cell's value directly, performing an unbatched inversion
127    /// if necessary.
128    ///
129    /// If the denominator is zero, the returned cell's value is zero.
130    pub fn evaluate(self) -> AssignedCell<F, F> {
131        AssignedCell {
132            value: self.value.map(|v| v.evaluate()),
133            cell: self.cell,
134            _marker: Default::default(),
135        }
136    }
137}
138
139impl<V: Clone, F: Field> AssignedCell<V, F>
140where
141    for<'v> Assigned<F>: From<&'v V>,
142{
143    /// Copies the value to a given advice cell and constrains them to be equal.
144    ///
145    /// Returns an error if either this cell or the given cell are in columns
146    /// where equality has not been enabled.
147    pub fn copy_advice<A, AR>(
148        &self,
149        annotation: A,
150        region: &mut Region<'_, F>,
151        column: Column<Advice>,
152        offset: usize,
153    ) -> Result<Self, Error>
154    where
155        A: Fn() -> AR,
156        AR: Into<String>,
157    {
158        let assigned_cell = region.assign_advice(annotation, column, offset, || {
159            self.value.clone().ok_or(Error::Synthesis)
160        })?;
161        region.constrain_equal(assigned_cell.cell(), self.cell())?;
162
163        Ok(assigned_cell)
164    }
165}
166
167/// A region of the circuit in which a [`Chip`] can assign cells.
168///
169/// Inside a region, the chip may freely use relative offsets; the [`Layouter`] will
170/// treat these assignments as a single "region" within the circuit.
171///
172/// The [`Layouter`] is allowed to optimise between regions as it sees fit. Chips must use
173/// [`Region::constrain_equal`] to copy in variables assigned in other regions.
174///
175/// TODO: It would be great if we could constrain the columns in these types to be
176/// "logical" columns that are guaranteed to correspond to the chip (and have come from
177/// `Chip::Config`).
178#[derive(Debug)]
179pub struct Region<'r, F: Field> {
180    region: &'r mut dyn layouter::RegionLayouter<F>,
181}
182
183impl<'r, F: Field> From<&'r mut dyn layouter::RegionLayouter<F>> for Region<'r, F> {
184    fn from(region: &'r mut dyn layouter::RegionLayouter<F>) -> Self {
185        Region { region }
186    }
187}
188
189impl<'r, F: Field> Region<'r, F> {
190    /// Enables a selector at the given offset.
191    pub(crate) fn enable_selector<A, AR>(
192        &mut self,
193        annotation: A,
194        selector: &Selector,
195        offset: usize,
196    ) -> Result<(), Error>
197    where
198        A: Fn() -> AR,
199        AR: Into<String>,
200    {
201        self.region
202            .enable_selector(&|| annotation().into(), selector, offset)
203    }
204
205    /// Assign an advice column value (witness).
206    ///
207    /// Even though `to` has `FnMut` bounds, it is guaranteed to be called at most once.
208    pub fn assign_advice<'v, V, VR, A, AR>(
209        &'v mut self,
210        annotation: A,
211        column: Column<Advice>,
212        offset: usize,
213        mut to: V,
214    ) -> Result<AssignedCell<VR, F>, Error>
215    where
216        V: FnMut() -> Result<VR, Error> + 'v,
217        for<'vr> Assigned<F>: From<&'vr VR>,
218        A: Fn() -> AR,
219        AR: Into<String>,
220    {
221        let mut value = None;
222        let cell =
223            self.region
224                .assign_advice(&|| annotation().into(), column, offset, &mut || {
225                    let v = to()?;
226                    let value_f = (&v).into();
227                    value = Some(v);
228                    Ok(value_f)
229                })?;
230
231        Ok(AssignedCell {
232            value,
233            cell,
234            _marker: PhantomData,
235        })
236    }
237
238    /// Assigns a constant value to the column `advice` at `offset` within this region.
239    ///
240    /// The constant value will be assigned to a cell within one of the fixed columns
241    /// configured via `ConstraintSystem::enable_constant`.
242    ///
243    /// Returns the advice cell.
244    pub fn assign_advice_from_constant<VR, A, AR>(
245        &mut self,
246        annotation: A,
247        column: Column<Advice>,
248        offset: usize,
249        constant: VR,
250    ) -> Result<AssignedCell<VR, F>, Error>
251    where
252        for<'vr> Assigned<F>: From<&'vr VR>,
253        A: Fn() -> AR,
254        AR: Into<String>,
255    {
256        let cell = self.region.assign_advice_from_constant(
257            &|| annotation().into(),
258            column,
259            offset,
260            (&constant).into(),
261        )?;
262
263        Ok(AssignedCell {
264            value: Some(constant),
265            cell,
266            _marker: PhantomData,
267        })
268    }
269
270    /// Assign the value of the instance column's cell at absolute location
271    /// `row` to the column `advice` at `offset` within this region.
272    ///
273    /// Returns the advice cell, and its value if known.
274    pub fn assign_advice_from_instance<A, AR>(
275        &mut self,
276        annotation: A,
277        instance: Column<Instance>,
278        row: usize,
279        advice: Column<Advice>,
280        offset: usize,
281    ) -> Result<AssignedCell<F, F>, Error>
282    where
283        A: Fn() -> AR,
284        AR: Into<String>,
285    {
286        let (cell, value) = self.region.assign_advice_from_instance(
287            &|| annotation().into(),
288            instance,
289            row,
290            advice,
291            offset,
292        )?;
293
294        Ok(AssignedCell {
295            value,
296            cell,
297            _marker: PhantomData,
298        })
299    }
300
301    /// Assign a fixed value.
302    ///
303    /// Even though `to` has `FnMut` bounds, it is guaranteed to be called at most once.
304    pub fn assign_fixed<'v, V, VR, A, AR>(
305        &'v mut self,
306        annotation: A,
307        column: Column<Fixed>,
308        offset: usize,
309        mut to: V,
310    ) -> Result<AssignedCell<VR, F>, Error>
311    where
312        V: FnMut() -> Result<VR, Error> + 'v,
313        for<'vr> Assigned<F>: From<&'vr VR>,
314        A: Fn() -> AR,
315        AR: Into<String>,
316    {
317        let mut value = None;
318        let cell =
319            self.region
320                .assign_fixed(&|| annotation().into(), column, offset, &mut || {
321                    let v = to()?;
322                    let value_f = (&v).into();
323                    value = Some(v);
324                    Ok(value_f)
325                })?;
326
327        Ok(AssignedCell {
328            value,
329            cell,
330            _marker: PhantomData,
331        })
332    }
333
334    /// Constrains a cell to have a constant value.
335    ///
336    /// Returns an error if the cell is in a column where equality has not been enabled.
337    pub fn constrain_constant<VR>(&mut self, cell: Cell, constant: VR) -> Result<(), Error>
338    where
339        VR: Into<Assigned<F>>,
340    {
341        self.region.constrain_constant(cell, constant.into())
342    }
343
344    /// Constrains two cells to have the same value.
345    ///
346    /// Returns an error if either of the cells are in columns where equality
347    /// has not been enabled.
348    pub fn constrain_equal(&mut self, left: Cell, right: Cell) -> Result<(), Error> {
349        self.region.constrain_equal(left, right)
350    }
351}
352
353/// A lookup table in the circuit.
354#[derive(Debug)]
355pub struct Table<'r, F: Field> {
356    table: &'r mut dyn layouter::TableLayouter<F>,
357}
358
359impl<'r, F: Field> From<&'r mut dyn layouter::TableLayouter<F>> for Table<'r, F> {
360    fn from(table: &'r mut dyn layouter::TableLayouter<F>) -> Self {
361        Table { table }
362    }
363}
364
365impl<'r, F: Field> Table<'r, F> {
366    /// Assigns a fixed value to a table cell.
367    ///
368    /// Returns an error if the table cell has already been assigned to.
369    ///
370    /// Even though `to` has `FnMut` bounds, it is guaranteed to be called at most once.
371    pub fn assign_cell<'v, V, VR, A, AR>(
372        &'v mut self,
373        annotation: A,
374        column: TableColumn,
375        offset: usize,
376        mut to: V,
377    ) -> Result<(), Error>
378    where
379        V: FnMut() -> Result<VR, Error> + 'v,
380        VR: Into<Assigned<F>>,
381        A: Fn() -> AR,
382        AR: Into<String>,
383    {
384        self.table
385            .assign_cell(&|| annotation().into(), column, offset, &mut || {
386                to().map(|v| v.into())
387            })
388    }
389}
390
391/// A layout strategy within a circuit. The layouter is chip-agnostic and applies its
392/// strategy to the context and config it is given.
393///
394/// This abstracts over the circuit assignments, handling row indices etc.
395///
396pub trait Layouter<F: Field> {
397    /// Represents the type of the "root" of this layouter, so that nested namespaces
398    /// can minimize indirection.
399    type Root: Layouter<F>;
400
401    /// Assign a region of gates to an absolute row number.
402    ///
403    /// Inside the closure, the chip may freely use relative offsets; the `Layouter` will
404    /// treat these assignments as a single "region" within the circuit. Outside this
405    /// closure, the `Layouter` is allowed to optimise as it sees fit.
406    ///
407    /// ```ignore
408    /// fn assign_region(&mut self, || "region name", |region| {
409    ///     let config = chip.config();
410    ///     region.assign_advice(config.a, offset, || { Some(value)});
411    /// });
412    /// ```
413    fn assign_region<A, AR, N, NR>(&mut self, name: N, assignment: A) -> Result<AR, Error>
414    where
415        A: FnMut(Region<'_, F>) -> Result<AR, Error>,
416        N: Fn() -> NR,
417        NR: Into<String>;
418
419    /// Assign a table region to an absolute row number.
420    ///
421    /// ```ignore
422    /// fn assign_table(&mut self, || "table name", |table| {
423    ///     let config = chip.config();
424    ///     table.assign_fixed(config.a, offset, || { Some(value)});
425    /// });
426    /// ```
427    fn assign_table<A, N, NR>(&mut self, name: N, assignment: A) -> Result<(), Error>
428    where
429        A: FnMut(Table<'_, F>) -> Result<(), Error>,
430        N: Fn() -> NR,
431        NR: Into<String>;
432
433    /// Constrains a [`Cell`] to equal an instance column's row value at an
434    /// absolute position.
435    fn constrain_instance(
436        &mut self,
437        cell: Cell,
438        column: Column<Instance>,
439        row: usize,
440    ) -> Result<(), Error>;
441
442    /// Gets the "root" of this assignment, bypassing the namespacing.
443    ///
444    /// Not intended for downstream consumption; use [`Layouter::namespace`] instead.
445    fn get_root(&mut self) -> &mut Self::Root;
446
447    /// Creates a new (sub)namespace and enters into it.
448    ///
449    /// Not intended for downstream consumption; use [`Layouter::namespace`] instead.
450    fn push_namespace<NR, N>(&mut self, name_fn: N)
451    where
452        NR: Into<String>,
453        N: FnOnce() -> NR;
454
455    /// Exits out of the existing namespace.
456    ///
457    /// Not intended for downstream consumption; use [`Layouter::namespace`] instead.
458    fn pop_namespace(&mut self, gadget_name: Option<String>);
459
460    /// Enters into a namespace.
461    fn namespace<NR, N>(&mut self, name_fn: N) -> NamespacedLayouter<'_, F, Self::Root>
462    where
463        NR: Into<String>,
464        N: FnOnce() -> NR,
465    {
466        self.get_root().push_namespace(name_fn);
467
468        NamespacedLayouter(self.get_root(), PhantomData)
469    }
470}
471
472/// This is a "namespaced" layouter which borrows a `Layouter` (pushing a namespace
473/// context) and, when dropped, pops out of the namespace context.
474#[derive(Debug)]
475pub struct NamespacedLayouter<'a, F: Field, L: Layouter<F> + 'a>(&'a mut L, PhantomData<F>);
476
477impl<'a, F: Field, L: Layouter<F> + 'a> Layouter<F> for NamespacedLayouter<'a, F, L> {
478    type Root = L::Root;
479
480    fn assign_region<A, AR, N, NR>(&mut self, name: N, assignment: A) -> Result<AR, Error>
481    where
482        A: FnMut(Region<'_, F>) -> Result<AR, Error>,
483        N: Fn() -> NR,
484        NR: Into<String>,
485    {
486        self.0.assign_region(name, assignment)
487    }
488
489    fn assign_table<A, N, NR>(&mut self, name: N, assignment: A) -> Result<(), Error>
490    where
491        A: FnMut(Table<'_, F>) -> Result<(), Error>,
492        N: Fn() -> NR,
493        NR: Into<String>,
494    {
495        self.0.assign_table(name, assignment)
496    }
497
498    fn constrain_instance(
499        &mut self,
500        cell: Cell,
501        column: Column<Instance>,
502        row: usize,
503    ) -> Result<(), Error> {
504        self.0.constrain_instance(cell, column, row)
505    }
506
507    fn get_root(&mut self) -> &mut Self::Root {
508        self.0.get_root()
509    }
510
511    fn push_namespace<NR, N>(&mut self, _name_fn: N)
512    where
513        NR: Into<String>,
514        N: FnOnce() -> NR,
515    {
516        panic!("Only the root's push_namespace should be called");
517    }
518
519    fn pop_namespace(&mut self, _gadget_name: Option<String>) {
520        panic!("Only the root's pop_namespace should be called");
521    }
522}
523
524impl<'a, F: Field, L: Layouter<F> + 'a> Drop for NamespacedLayouter<'a, F, L> {
525    fn drop(&mut self) {
526        let gadget_name = {
527            #[cfg(feature = "gadget-traces")]
528            {
529                let mut gadget_name = None;
530                let mut is_second_frame = false;
531                backtrace::trace(|frame| {
532                    if is_second_frame {
533                        // Resolve this instruction pointer to a symbol name.
534                        backtrace::resolve_frame(frame, |symbol| {
535                            gadget_name = symbol.name().map(|name| format!("{:#}", name));
536                        });
537
538                        // We are done!
539                        false
540                    } else {
541                        // We want the next frame.
542                        is_second_frame = true;
543                        true
544                    }
545                });
546                gadget_name
547            }
548
549            #[cfg(not(feature = "gadget-traces"))]
550            None
551        };
552
553        self.get_root().pop_namespace(gadget_name);
554    }
555}
halo2_proofs/circuit.rs

halo2_proofs/
circuit.rs
