use core::cmp::max;
use core::ops::{Add, Mul};
use ff::Field;
use std::{
convert::TryFrom,
ops::{Neg, Sub},
};
use super::{lookup, permutation, Error};
use crate::circuit::Layouter;
use crate::{circuit::Region, poly::Rotation};
mod compress_selectors;
pub trait ColumnType:
'static + Sized + Copy + std::fmt::Debug + PartialEq + Eq + Into<Any>
{
}
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct Column<C: ColumnType> {
index: usize,
column_type: C,
}
impl<C: ColumnType> Column<C> {
#[cfg(test)]
pub(crate) fn new(index: usize, column_type: C) -> Self {
Column { index, column_type }
}
pub(crate) fn index(&self) -> usize {
self.index
}
pub(crate) fn column_type(&self) -> &C {
&self.column_type
}
}
impl<C: ColumnType> Ord for Column<C> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
match (self.column_type.into(), other.column_type.into()) {
(Any::Instance, Any::Instance)
| (Any::Advice, Any::Advice)
| (Any::Fixed, Any::Fixed) => self.index.cmp(&other.index),
(Any::Instance, Any::Advice)
| (Any::Advice, Any::Fixed)
| (Any::Instance, Any::Fixed) => std::cmp::Ordering::Less,
(Any::Fixed, Any::Instance)
| (Any::Fixed, Any::Advice)
| (Any::Advice, Any::Instance) => std::cmp::Ordering::Greater,
}
}
}
impl<C: ColumnType> PartialOrd for Column<C> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct Advice;
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct Fixed;
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct Instance;
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub enum Any {
Advice,
Fixed,
Instance,
}
impl ColumnType for Advice {}
impl ColumnType for Fixed {}
impl ColumnType for Instance {}
impl ColumnType for Any {}
impl From<Advice> for Any {
fn from(_: Advice) -> Any {
Any::Advice
}
}
impl From<Fixed> for Any {
fn from(_: Fixed) -> Any {
Any::Fixed
}
}
impl From<Instance> for Any {
fn from(_: Instance) -> Any {
Any::Instance
}
}
impl From<Column<Advice>> for Column<Any> {
fn from(advice: Column<Advice>) -> Column<Any> {
Column {
index: advice.index(),
column_type: Any::Advice,
}
}
}
impl From<Column<Fixed>> for Column<Any> {
fn from(advice: Column<Fixed>) -> Column<Any> {
Column {
index: advice.index(),
column_type: Any::Fixed,
}
}
}
impl From<Column<Instance>> for Column<Any> {
fn from(advice: Column<Instance>) -> Column<Any> {
Column {
index: advice.index(),
column_type: Any::Instance,
}
}
}
impl TryFrom<Column<Any>> for Column<Advice> {
type Error = &'static str;
fn try_from(any: Column<Any>) -> Result<Self, Self::Error> {
match any.column_type() {
Any::Advice => Ok(Column {
index: any.index(),
column_type: Advice,
}),
_ => Err("Cannot convert into Column<Advice>"),
}
}
}
impl TryFrom<Column<Any>> for Column<Fixed> {
type Error = &'static str;
fn try_from(any: Column<Any>) -> Result<Self, Self::Error> {
match any.column_type() {
Any::Fixed => Ok(Column {
index: any.index(),
column_type: Fixed,
}),
_ => Err("Cannot convert into Column<Fixed>"),
}
}
}
impl TryFrom<Column<Any>> for Column<Instance> {
type Error = &'static str;
fn try_from(any: Column<Any>) -> Result<Self, Self::Error> {
match any.column_type() {
Any::Instance => Ok(Column {
index: any.index(),
column_type: Instance,
}),
_ => Err("Cannot convert into Column<Instance>"),
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Selector(pub(crate) usize, bool);
impl Selector {
pub fn enable<F: Field>(&self, region: &mut Region<F>, offset: usize) -> Result<(), Error> {
region.enable_selector(|| "", self, offset)
}
pub fn is_simple(&self) -> bool {
self.1
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
pub struct TableColumn {
inner: Column<Fixed>,
}
impl TableColumn {
pub(crate) fn inner(&self) -> Column<Fixed> {
self.inner
}
}
#[derive(Clone, Copy, Debug)]
pub enum Assigned<F> {
Zero,
Trivial(F),
Rational(F, F),
}
impl<F: Field> From<F> for Assigned<F> {
fn from(numerator: F) -> Self {
Assigned::Trivial(numerator)
}
}
impl<F: Field> From<(F, F)> for Assigned<F> {
fn from((numerator, denominator): (F, F)) -> Self {
Assigned::Rational(numerator, denominator)
}
}
impl<F: Field> Neg for Assigned<F> {
type Output = Assigned<F>;
fn neg(self) -> Self::Output {
match self {
Self::Zero => Self::Zero,
Self::Trivial(numerator) => Self::Trivial(-numerator),
Self::Rational(numerator, denominator) => Self::Rational(-numerator, denominator),
}
}
}
impl<F: Field> Add for Assigned<F> {
type Output = Assigned<F>;
fn add(self, rhs: Assigned<F>) -> Assigned<F> {
match (self, rhs) {
(Self::Zero, _) => rhs,
(_, Self::Zero) => self,
(Self::Trivial(lhs), Self::Trivial(rhs)) => Self::Trivial(lhs + rhs),
(Self::Rational(numerator, denominator), Self::Trivial(other))
| (Self::Trivial(other), Self::Rational(numerator, denominator)) => {
Self::Rational(numerator + denominator * other, denominator)
}
(
Self::Rational(lhs_numerator, lhs_denominator),
Self::Rational(rhs_numerator, rhs_denominator),
) => Self::Rational(
lhs_numerator * rhs_denominator + lhs_denominator * rhs_numerator,
lhs_denominator * rhs_denominator,
),
}
}
}
impl<F: Field> Add<F> for Assigned<F> {
type Output = Assigned<F>;
fn add(self, rhs: F) -> Assigned<F> {
self + Self::Trivial(rhs)
}
}
impl<F: Field> Sub for Assigned<F> {
type Output = Assigned<F>;
fn sub(self, rhs: Assigned<F>) -> Assigned<F> {
self + (-rhs)
}
}
impl<F: Field> Sub<F> for Assigned<F> {
type Output = Assigned<F>;
fn sub(self, rhs: F) -> Assigned<F> {
self + (-rhs)
}
}
impl<F: Field> Mul for Assigned<F> {
type Output = Assigned<F>;
fn mul(self, rhs: Assigned<F>) -> Assigned<F> {
match (self, rhs) {
(Self::Zero, _) | (_, Self::Zero) => Self::Zero,
(Self::Trivial(lhs), Self::Trivial(rhs)) => Self::Trivial(lhs * rhs),
(Self::Rational(numerator, denominator), Self::Trivial(other))
| (Self::Trivial(other), Self::Rational(numerator, denominator)) => {
Self::Rational(numerator * other, denominator)
}
(
Self::Rational(lhs_numerator, lhs_denominator),
Self::Rational(rhs_numerator, rhs_denominator),
) => Self::Rational(
lhs_numerator * rhs_numerator,
lhs_denominator * rhs_denominator,
),
}
}
}
impl<F: Field> Mul<F> for Assigned<F> {
type Output = Assigned<F>;
fn mul(self, rhs: F) -> Assigned<F> {
self * Self::Trivial(rhs)
}
}
impl<F: Field> Assigned<F> {
pub fn numerator(&self) -> F {
match self {
Self::Zero => F::zero(),
Self::Trivial(x) => *x,
Self::Rational(numerator, _) => *numerator,
}
}
pub fn denominator(&self) -> Option<F> {
match self {
Self::Zero => None,
Self::Trivial(_) => None,
Self::Rational(_, denominator) => Some(*denominator),
}
}
pub fn invert(&self) -> Self {
match self {
Self::Zero => Self::Zero,
Self::Trivial(x) => Self::Rational(F::one(), *x),
Self::Rational(numerator, denominator) => Self::Rational(*denominator, *numerator),
}
}
pub fn evaluate(self) -> F {
match self {
Self::Zero => F::zero(),
Self::Trivial(x) => x,
Self::Rational(numerator, denominator) => {
if denominator == F::one() {
numerator
} else {
numerator * denominator.invert().unwrap_or(F::zero())
}
}
}
}
}
pub trait Assignment<F: Field> {
fn enter_region<NR, N>(&mut self, name_fn: N)
where
NR: Into<String>,
N: FnOnce() -> NR;
fn exit_region(&mut self);
fn enable_selector<A, AR>(
&mut self,
annotation: A,
selector: &Selector,
row: usize,
) -> Result<(), Error>
where
A: FnOnce() -> AR,
AR: Into<String>;
fn query_instance(&self, column: Column<Instance>, row: usize) -> Result<Option<F>, Error>;
fn assign_advice<V, VR, A, AR>(
&mut self,
annotation: A,
column: Column<Advice>,
row: usize,
to: V,
) -> Result<(), Error>
where
V: FnOnce() -> Result<VR, Error>,
VR: Into<Assigned<F>>,
A: FnOnce() -> AR,
AR: Into<String>;
fn assign_fixed<V, VR, A, AR>(
&mut self,
annotation: A,
column: Column<Fixed>,
row: usize,
to: V,
) -> Result<(), Error>
where
V: FnOnce() -> Result<VR, Error>,
VR: Into<Assigned<F>>,
A: FnOnce() -> AR,
AR: Into<String>;
fn copy(
&mut self,
left_column: Column<Any>,
left_row: usize,
right_column: Column<Any>,
right_row: usize,
) -> Result<(), Error>;
fn fill_from_row(
&mut self,
column: Column<Fixed>,
row: usize,
to: Option<Assigned<F>>,
) -> Result<(), Error>;
fn push_namespace<NR, N>(&mut self, name_fn: N)
where
NR: Into<String>,
N: FnOnce() -> NR;
fn pop_namespace(&mut self, gadget_name: Option<String>);
}
pub trait FloorPlanner {
fn synthesize<F: Field, CS: Assignment<F>, C: Circuit<F>>(
cs: &mut CS,
circuit: &C,
config: C::Config,
constants: Vec<Column<Fixed>>,
) -> Result<(), Error>;
}
pub trait Circuit<F: Field> {
type Config: Clone;
type FloorPlanner: FloorPlanner;
fn without_witnesses(&self) -> Self;
fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config;
fn synthesize(&self, config: Self::Config, layouter: impl Layouter<F>) -> Result<(), Error>;
}
#[derive(Clone, Debug)]
pub enum Expression<F> {
Constant(F),
Selector(Selector),
Fixed {
query_index: usize,
column_index: usize,
rotation: Rotation,
},
Advice {
query_index: usize,
column_index: usize,
rotation: Rotation,
},
Instance {
query_index: usize,
column_index: usize,
rotation: Rotation,
},
Negated(Box<Expression<F>>),
Sum(Box<Expression<F>>, Box<Expression<F>>),
Product(Box<Expression<F>>, Box<Expression<F>>),
Scaled(Box<Expression<F>>, F),
}
impl<F: Field> Expression<F> {
pub fn evaluate<T>(
&self,
constant: &impl Fn(F) -> T,
selector_column: &impl Fn(Selector) -> T,
fixed_column: &impl Fn(usize, usize, Rotation) -> T,
advice_column: &impl Fn(usize, usize, Rotation) -> T,
instance_column: &impl Fn(usize, usize, Rotation) -> T,
negated: &impl Fn(T) -> T,
sum: &impl Fn(T, T) -> T,
product: &impl Fn(T, T) -> T,
scaled: &impl Fn(T, F) -> T,
) -> T {
match self {
Expression::Constant(scalar) => constant(*scalar),
Expression::Selector(selector) => selector_column(*selector),
Expression::Fixed {
query_index,
column_index,
rotation,
} => fixed_column(*query_index, *column_index, *rotation),
Expression::Advice {
query_index,
column_index,
rotation,
} => advice_column(*query_index, *column_index, *rotation),
Expression::Instance {
query_index,
column_index,
rotation,
} => instance_column(*query_index, *column_index, *rotation),
Expression::Negated(a) => {
let a = a.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
negated(a)
}
Expression::Sum(a, b) => {
let a = a.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
let b = b.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
sum(a, b)
}
Expression::Product(a, b) => {
let a = a.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
let b = b.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
product(a, b)
}
Expression::Scaled(a, f) => {
let a = a.evaluate(
constant,
selector_column,
fixed_column,
advice_column,
instance_column,
negated,
sum,
product,
scaled,
);
scaled(a, *f)
}
}
}
pub fn degree(&self) -> usize {
match self {
Expression::Constant(_) => 0,
Expression::Selector(_) => 1,
Expression::Fixed { .. } => 1,
Expression::Advice { .. } => 1,
Expression::Instance { .. } => 1,
Expression::Negated(poly) => poly.degree(),
Expression::Sum(a, b) => max(a.degree(), b.degree()),
Expression::Product(a, b) => a.degree() + b.degree(),
Expression::Scaled(poly, _) => poly.degree(),
}
}
pub fn square(self) -> Self {
self.clone() * self
}
fn contains_simple_selector(&self) -> bool {
self.evaluate(
&|_| false,
&|selector| selector.is_simple(),
&|_, _, _| false,
&|_, _, _| false,
&|_, _, _| false,
&|a| a,
&|a, b| a || b,
&|a, b| a || b,
&|a, _| a,
)
}
fn extract_simple_selector(&self) -> Option<Selector> {
let op = |a, b| match (a, b) {
(Some(a), None) | (None, Some(a)) => Some(a),
(Some(_), Some(_)) => panic!("two simple selectors cannot be in the same expression"),
_ => None,
};
self.evaluate(
&|_| None,
&|selector| {
if selector.is_simple() {
Some(selector)
} else {
None
}
},
&|_, _, _| None,
&|_, _, _| None,
&|_, _, _| None,
&|a| a,
&op,
&op,
&|a, _| a,
)
}
}
impl<F: Field> Neg for Expression<F> {
type Output = Expression<F>;
fn neg(self) -> Self::Output {
Expression::Negated(Box::new(self))
}
}
impl<F: Field> Add for Expression<F> {
type Output = Expression<F>;
fn add(self, rhs: Expression<F>) -> Expression<F> {
if self.contains_simple_selector() || rhs.contains_simple_selector() {
panic!("attempted to use a simple selector in an addition");
}
Expression::Sum(Box::new(self), Box::new(rhs))
}
}
impl<F: Field> Sub for Expression<F> {
type Output = Expression<F>;
fn sub(self, rhs: Expression<F>) -> Expression<F> {
if self.contains_simple_selector() || rhs.contains_simple_selector() {
panic!("attempted to use a simple selector in a subtraction");
}
Expression::Sum(Box::new(self), Box::new(-rhs))
}
}
impl<F: Field> Mul for Expression<F> {
type Output = Expression<F>;
fn mul(self, rhs: Expression<F>) -> Expression<F> {
if self.contains_simple_selector() && rhs.contains_simple_selector() {
panic!("attempted to multiply two expressions containing simple selectors");
}
Expression::Product(Box::new(self), Box::new(rhs))
}
}
impl<F: Field> Mul<F> for Expression<F> {
type Output = Expression<F>;
fn mul(self, rhs: F) -> Expression<F> {
Expression::Scaled(Box::new(self), rhs)
}
}
#[derive(Copy, Clone, Debug)]
pub(crate) struct PointIndex(pub usize);
#[derive(Clone, Debug)]
pub(crate) struct VirtualCell {
pub(crate) column: Column<Any>,
pub(crate) rotation: Rotation,
}
impl<Col: Into<Column<Any>>> From<(Col, Rotation)> for VirtualCell {
fn from((column, rotation): (Col, Rotation)) -> Self {
VirtualCell {
column: column.into(),
rotation,
}
}
}
#[derive(Debug)]
pub struct Constraint<F: Field> {
name: &'static str,
poly: Expression<F>,
}
impl<F: Field> From<Expression<F>> for Constraint<F> {
fn from(poly: Expression<F>) -> Self {
Constraint { name: "", poly }
}
}
impl<F: Field> From<(&'static str, Expression<F>)> for Constraint<F> {
fn from((name, poly): (&'static str, Expression<F>)) -> Self {
Constraint { name, poly }
}
}
impl<F: Field> From<Expression<F>> for Vec<Constraint<F>> {
fn from(poly: Expression<F>) -> Self {
vec![Constraint { name: "", poly }]
}
}
#[derive(Clone, Debug)]
pub(crate) struct Gate<F: Field> {
name: &'static str,
constraint_names: Vec<&'static str>,
polys: Vec<Expression<F>>,
queried_selectors: Vec<Selector>,
queried_cells: Vec<VirtualCell>,
}
impl<F: Field> Gate<F> {
pub(crate) fn name(&self) -> &'static str {
self.name
}
pub(crate) fn constraint_name(&self, constraint_index: usize) -> &'static str {
self.constraint_names[constraint_index]
}
pub(crate) fn polynomials(&self) -> &[Expression<F>] {
&self.polys
}
pub(crate) fn queried_selectors(&self) -> &[Selector] {
&self.queried_selectors
}
pub(crate) fn queried_cells(&self) -> &[VirtualCell] {
&self.queried_cells
}
}
#[derive(Debug, Clone)]
pub struct ConstraintSystem<F: Field> {
pub(crate) num_fixed_columns: usize,
pub(crate) num_advice_columns: usize,
pub(crate) num_instance_columns: usize,
pub(crate) num_selectors: usize,
pub(crate) selector_map: Vec<Column<Fixed>>,
pub(crate) gates: Vec<Gate<F>>,
pub(crate) advice_queries: Vec<(Column<Advice>, Rotation)>,
num_advice_queries: Vec<usize>,
pub(crate) instance_queries: Vec<(Column<Instance>, Rotation)>,
pub(crate) fixed_queries: Vec<(Column<Fixed>, Rotation)>,
pub(crate) permutation: permutation::Argument,
pub(crate) lookups: Vec<lookup::Argument<F>>,
pub(crate) constants: Vec<Column<Fixed>>,
pub(crate) minimum_degree: Option<usize>,
}
#[derive(Debug)]
pub struct PinnedConstraintSystem<'a, F: Field> {
num_fixed_columns: &'a usize,
num_advice_columns: &'a usize,
num_instance_columns: &'a usize,
num_selectors: &'a usize,
selector_map: &'a [Column<Fixed>],
gates: PinnedGates<'a, F>,
advice_queries: &'a Vec<(Column<Advice>, Rotation)>,
instance_queries: &'a Vec<(Column<Instance>, Rotation)>,
fixed_queries: &'a Vec<(Column<Fixed>, Rotation)>,
permutation: &'a permutation::Argument,
lookups: &'a Vec<lookup::Argument<F>>,
constants: &'a Vec<Column<Fixed>>,
minimum_degree: &'a Option<usize>,
}
struct PinnedGates<'a, F: Field>(&'a Vec<Gate<F>>);
impl<'a, F: Field> std::fmt::Debug for PinnedGates<'a, F> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
f.debug_list()
.entries(self.0.iter().flat_map(|gate| gate.polynomials().iter()))
.finish()
}
}
impl<F: Field> Default for ConstraintSystem<F> {
fn default() -> ConstraintSystem<F> {
ConstraintSystem {
num_fixed_columns: 0,
num_advice_columns: 0,
num_instance_columns: 0,
num_selectors: 0,
selector_map: vec![],
gates: vec![],
fixed_queries: Vec::new(),
advice_queries: Vec::new(),
num_advice_queries: Vec::new(),
instance_queries: Vec::new(),
permutation: permutation::Argument::new(),
lookups: Vec::new(),
constants: vec![],
minimum_degree: None,
}
}
}
impl<F: Field> ConstraintSystem<F> {
pub fn pinned(&self) -> PinnedConstraintSystem<'_, F> {
PinnedConstraintSystem {
num_fixed_columns: &self.num_fixed_columns,
num_advice_columns: &self.num_advice_columns,
num_instance_columns: &self.num_instance_columns,
num_selectors: &self.num_selectors,
selector_map: &self.selector_map,
gates: PinnedGates(&self.gates),
fixed_queries: &self.fixed_queries,
advice_queries: &self.advice_queries,
instance_queries: &self.instance_queries,
permutation: &self.permutation,
lookups: &self.lookups,
constants: &self.constants,
minimum_degree: &self.minimum_degree,
}
}
pub fn enable_constant(&mut self, column: Column<Fixed>) {
if !self.constants.contains(&column) {
self.constants.push(column);
self.enable_equality(column.into());
}
}
pub fn enable_equality(&mut self, column: Column<Any>) {
self.query_any_index(column, Rotation::cur());
self.permutation.add_column(column);
}
pub fn lookup(
&mut self,
table_map: impl FnOnce(&mut VirtualCells<'_, F>) -> Vec<(Expression<F>, TableColumn)>,
) -> usize {
let mut cells = VirtualCells::new(self);
let table_map = table_map(&mut cells)
.into_iter()
.map(|(input, table)| {
if input.contains_simple_selector() {
panic!("expression containing simple selector supplied to lookup argument");
}
let table = cells.query_fixed(table.inner(), Rotation::cur());
(input, table)
})
.collect();
let index = self.lookups.len();
self.lookups.push(lookup::Argument::new(table_map));
index
}
fn query_fixed_index(&mut self, column: Column<Fixed>, at: Rotation) -> usize {
for (index, fixed_query) in self.fixed_queries.iter().enumerate() {
if fixed_query == &(column, at) {
return index;
}
}
let index = self.fixed_queries.len();
self.fixed_queries.push((column, at));
index
}
pub(crate) fn query_advice_index(&mut self, column: Column<Advice>, at: Rotation) -> usize {
for (index, advice_query) in self.advice_queries.iter().enumerate() {
if advice_query == &(column, at) {
return index;
}
}
let index = self.advice_queries.len();
self.advice_queries.push((column, at));
self.num_advice_queries[column.index] += 1;
index
}
fn query_instance_index(&mut self, column: Column<Instance>, at: Rotation) -> usize {
for (index, instance_query) in self.instance_queries.iter().enumerate() {
if instance_query == &(column, at) {
return index;
}
}
let index = self.instance_queries.len();
self.instance_queries.push((column, at));
index
}
fn query_any_index(&mut self, column: Column<Any>, at: Rotation) -> usize {
match column.column_type() {
Any::Advice => self.query_advice_index(Column::<Advice>::try_from(column).unwrap(), at),
Any::Fixed => self.query_fixed_index(Column::<Fixed>::try_from(column).unwrap(), at),
Any::Instance => {
self.query_instance_index(Column::<Instance>::try_from(column).unwrap(), at)
}
}
}
pub(crate) fn get_advice_query_index(&self, column: Column<Advice>, at: Rotation) -> usize {
for (index, advice_query) in self.advice_queries.iter().enumerate() {
if advice_query == &(column, at) {
return index;
}
}
panic!("get_advice_query_index called for non-existent query");
}
pub(crate) fn get_fixed_query_index(&self, column: Column<Fixed>, at: Rotation) -> usize {
for (index, fixed_query) in self.fixed_queries.iter().enumerate() {
if fixed_query == &(column, at) {
return index;
}
}
panic!("get_fixed_query_index called for non-existent query");
}
pub(crate) fn get_instance_query_index(&self, column: Column<Instance>, at: Rotation) -> usize {
for (index, instance_query) in self.instance_queries.iter().enumerate() {
if instance_query == &(column, at) {
return index;
}
}
panic!("get_instance_query_index called for non-existent query");
}
pub(crate) fn get_any_query_index(&self, column: Column<Any>, at: Rotation) -> usize {
match column.column_type() {
Any::Advice => {
self.get_advice_query_index(Column::<Advice>::try_from(column).unwrap(), at)
}
Any::Fixed => {
self.get_fixed_query_index(Column::<Fixed>::try_from(column).unwrap(), at)
}
Any::Instance => {
self.get_instance_query_index(Column::<Instance>::try_from(column).unwrap(), at)
}
}
}
pub fn set_minimum_degree(&mut self, degree: usize) {
self.minimum_degree = Some(degree);
}
pub fn create_gate<C: Into<Constraint<F>>, Iter: IntoIterator<Item = C>>(
&mut self,
name: &'static str,
constraints: impl FnOnce(&mut VirtualCells<'_, F>) -> Iter,
) {
let mut cells = VirtualCells::new(self);
let constraints = constraints(&mut cells);
let queried_selectors = cells.queried_selectors;
let queried_cells = cells.queried_cells;
let (constraint_names, polys): (_, Vec<_>) = constraints
.into_iter()
.map(|c| c.into())
.map(|c| (c.name, c.poly))
.unzip();
assert!(
!polys.is_empty(),
"Gates must contain at least one constraint."
);
self.gates.push(Gate {
name,
constraint_names,
polys,
queried_selectors,
queried_cells,
});
}
pub(crate) fn compress_selectors(mut self, selectors: Vec<Vec<bool>>) -> (Self, Vec<Vec<F>>) {
assert_eq!(selectors.len(), self.num_selectors);
let mut degrees = vec![0; selectors.len()];
for expr in self.gates.iter().flat_map(|gate| gate.polys.iter()) {
if let Some(selector) = expr.extract_simple_selector() {
degrees[selector.0] = max(degrees[selector.0], expr.degree());
}
}
let max_degree = self.degree();
let mut new_columns = vec![];
let (polys, selector_assignment) = compress_selectors::process(
selectors
.into_iter()
.zip(degrees.into_iter())
.enumerate()
.map(
|(i, (activations, max_degree))| compress_selectors::SelectorDescription {
selector: i,
activations,
max_degree,
},
)
.collect(),
max_degree,
|| {
let column = self.fixed_column();
new_columns.push(column);
Expression::Fixed {
query_index: self.query_fixed_index(column, Rotation::cur()),
column_index: column.index,
rotation: Rotation::cur(),
}
},
);
let mut selector_map = vec![None; selector_assignment.len()];
let mut selector_replacements = vec![None; selector_assignment.len()];
for assignment in selector_assignment {
selector_replacements[assignment.selector] = Some(assignment.expression);
selector_map[assignment.selector] = Some(new_columns[assignment.combination_index]);
}
self.selector_map = selector_map
.into_iter()
.map(|a| a.unwrap())
.collect::<Vec<_>>();
let selector_replacements = selector_replacements
.into_iter()
.map(|a| a.unwrap())
.collect::<Vec<_>>();
fn replace_selectors<F: Field>(
expr: &mut Expression<F>,
selector_replacements: &[Expression<F>],
must_be_nonsimple: bool,
) {
*expr = expr.evaluate(
&|constant| Expression::Constant(constant),
&|selector| {
if must_be_nonsimple {
assert!(!selector.is_simple());
}
selector_replacements[selector.0].clone()
},
&|query_index, column_index, rotation| Expression::Fixed {
query_index,
column_index,
rotation,
},
&|query_index, column_index, rotation| Expression::Advice {
query_index,
column_index,
rotation,
},
&|query_index, column_index, rotation| Expression::Instance {
query_index,
column_index,
rotation,
},
&|a| -a,
&|a, b| a + b,
&|a, b| a * b,
&|a, f| a * f,
);
}
for expr in self.gates.iter_mut().flat_map(|gate| gate.polys.iter_mut()) {
replace_selectors(expr, &selector_replacements, false);
}
for expr in self.lookups.iter_mut().flat_map(|lookup| {
lookup
.input_expressions
.iter_mut()
.chain(lookup.table_expressions.iter_mut())
}) {
replace_selectors(expr, &selector_replacements, true);
}
(self, polys)
}
pub fn selector(&mut self) -> Selector {
let index = self.num_selectors;
self.num_selectors += 1;
Selector(index, true)
}
pub fn complex_selector(&mut self) -> Selector {
let index = self.num_selectors;
self.num_selectors += 1;
Selector(index, false)
}
pub fn lookup_table_column(&mut self) -> TableColumn {
TableColumn {
inner: self.fixed_column(),
}
}
pub fn fixed_column(&mut self) -> Column<Fixed> {
let tmp = Column {
index: self.num_fixed_columns,
column_type: Fixed,
};
self.num_fixed_columns += 1;
tmp
}
pub fn advice_column(&mut self) -> Column<Advice> {
let tmp = Column {
index: self.num_advice_columns,
column_type: Advice,
};
self.num_advice_columns += 1;
self.num_advice_queries.push(0);
tmp
}
pub fn instance_column(&mut self) -> Column<Instance> {
let tmp = Column {
index: self.num_instance_columns,
column_type: Instance,
};
self.num_instance_columns += 1;
tmp
}
pub fn degree(&self) -> usize {
let mut degree = self.permutation.required_degree();
degree = std::cmp::max(
degree,
self.lookups
.iter()
.map(|l| l.required_degree())
.max()
.unwrap_or(1),
);
degree = std::cmp::max(
degree,
self.gates
.iter()
.flat_map(|gate| gate.polynomials().iter().map(|poly| poly.degree()))
.max()
.unwrap_or(0),
);
std::cmp::max(degree, self.minimum_degree.unwrap_or(1))
}
pub fn blinding_factors(&self) -> usize {
let factors = *self.num_advice_queries.iter().max().unwrap_or(&1);
let factors = std::cmp::max(3, factors);
let factors = factors + 1;
factors + 1
}
pub fn minimum_rows(&self) -> usize {
self.blinding_factors() + 1 + 1 + 1 }
}
#[derive(Debug)]
pub struct VirtualCells<'a, F: Field> {
meta: &'a mut ConstraintSystem<F>,
queried_selectors: Vec<Selector>,
queried_cells: Vec<VirtualCell>,
}
impl<'a, F: Field> VirtualCells<'a, F> {
fn new(meta: &'a mut ConstraintSystem<F>) -> Self {
VirtualCells {
meta,
queried_selectors: vec![],
queried_cells: vec![],
}
}
pub fn query_selector(&mut self, selector: Selector) -> Expression<F> {
self.queried_selectors.push(selector);
Expression::Selector(selector)
}
pub fn query_fixed(&mut self, column: Column<Fixed>, at: Rotation) -> Expression<F> {
self.queried_cells.push((column, at).into());
Expression::Fixed {
query_index: self.meta.query_fixed_index(column, at),
column_index: column.index,
rotation: at,
}
}
pub fn query_advice(&mut self, column: Column<Advice>, at: Rotation) -> Expression<F> {
self.queried_cells.push((column, at).into());
Expression::Advice {
query_index: self.meta.query_advice_index(column, at),
column_index: column.index,
rotation: at,
}
}
pub fn query_instance(&mut self, column: Column<Instance>, at: Rotation) -> Expression<F> {
self.queried_cells.push((column, at).into());
Expression::Instance {
query_index: self.meta.query_instance_index(column, at),
column_index: column.index,
rotation: at,
}
}
pub fn query_any(&mut self, column: Column<Any>, at: Rotation) -> Expression<F> {
match column.column_type() {
Any::Advice => self.query_advice(Column::<Advice>::try_from(column).unwrap(), at),
Any::Fixed => self.query_fixed(Column::<Fixed>::try_from(column).unwrap(), at),
Any::Instance => self.query_instance(Column::<Instance>::try_from(column).unwrap(), at),
}
}
}