ark_r1cs_std/alloc.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
use crate::Vec;
use ark_ff::Field;
use ark_relations::r1cs::{Namespace, SynthesisError};
use core::borrow::Borrow;
/// Describes the mode that a variable should be allocated in within
/// a `ConstraintSystem`.
#[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Copy, Clone)]
pub enum AllocationMode {
/// Indicate to the `ConstraintSystem` that the high-level variable should
/// be allocated as a constant. That is, no `Variable`s should be
/// generated.
Constant = 0,
/// Indicate to the `ConstraintSystem` that the high-level variable should
/// be allocated as a public input to the `ConstraintSystem`.
Input = 1,
/// Indicate to the `ConstraintSystem` that the high-level variable should
/// be allocated as a private witness to the `ConstraintSystem`.
Witness = 2,
}
impl AllocationMode {
/// Outputs the maximum according to the relation `Constant < Input <
/// Witness`.
pub fn max(&self, other: Self) -> Self {
use AllocationMode::*;
match (self, other) {
(Constant, _) => other,
(Input, Constant) => *self,
(Input, _) => other,
(Witness, _) => *self,
}
}
}
/// Specifies how variables of type `Self` should be allocated in a
/// `ConstraintSystem`.
pub trait AllocVar<V: ?Sized, F: Field>: Sized {
/// Allocates a new variable of type `Self` in the `ConstraintSystem` `cs`.
/// The mode of allocation is decided by `mode`.
fn new_variable<T: Borrow<V>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError>;
/// Allocates a new constant of type `Self` in the `ConstraintSystem` `cs`.
///
/// This should *not* allocate any new variables or constraints in `cs`.
#[tracing::instrument(target = "r1cs", skip(cs, t))]
fn new_constant(
cs: impl Into<Namespace<F>>,
t: impl Borrow<V>,
) -> Result<Self, SynthesisError> {
Self::new_variable(cs, || Ok(t), AllocationMode::Constant)
}
/// Allocates a new public input of type `Self` in the `ConstraintSystem`
/// `cs`.
#[tracing::instrument(target = "r1cs", skip(cs, f))]
fn new_input<T: Borrow<V>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
) -> Result<Self, SynthesisError> {
Self::new_variable(cs, f, AllocationMode::Input)
}
/// Allocates a new private witness of type `Self` in the `ConstraintSystem`
/// `cs`.
#[tracing::instrument(target = "r1cs", skip(cs, f))]
fn new_witness<T: Borrow<V>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
) -> Result<Self, SynthesisError> {
Self::new_variable(cs, f, AllocationMode::Witness)
}
/// Allocates a new constant or private witness of type `Self` in the
/// `ConstraintSystem` `cs` with the allocation mode inferred from `cs`.
/// A constant is allocated if `cs` is `None`, and a private witness is
/// allocated otherwise.
///
/// A common use case is the creation of non-deterministic advice (a.k.a.
/// hints) in the circuit, where this method can avoid boilerplate code
/// while allowing optimization on circuit size.
///
/// For example, to compute `x_var / y_var` where `y_var` is a non-zero
/// variable, one can write:
/// ```
/// use ark_ff::PrimeField;
/// use ark_r1cs_std::{alloc::AllocVar, fields::{fp::FpVar, FieldVar}, R1CSVar};
/// use ark_relations::r1cs::SynthesisError;
///
/// fn div<F: PrimeField>(x_var: &FpVar<F>, y_var: &FpVar<F>) -> Result<FpVar<F>, SynthesisError> {
/// let cs = x_var.cs().or(y_var.cs());
/// let z_var = FpVar::new_variable_with_inferred_mode(cs, || Ok(x_var.value()? / y_var.value()?))?;
/// z_var.mul_equals(y_var, x_var)?;
/// Ok(z_var)
/// }
/// ```
/// In this example, if either `x_var` or `y_var` is a witness variable,
/// then `z_var` is also a witness variable. On the other hand, `z_var`
/// is a constant if both `x_var` and `y_var` are constants (i.e., `cs`
/// is `None`), and future operations on `z_var` do not generate any
/// constraints.
///
/// (Note that we use division as an example for simplicity. You may
/// call `x_var.mul_by_inverse(y_var)?` directly, which internally works
/// similarly to the above code.)
#[tracing::instrument(target = "r1cs", skip(cs, f))]
fn new_variable_with_inferred_mode<T: Borrow<V>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
) -> Result<Self, SynthesisError> {
let ns: Namespace<F> = cs.into();
let cs = ns.cs();
let mode = if cs.is_none() {
AllocationMode::Constant
} else {
AllocationMode::Witness
};
Self::new_variable(cs, f, mode)
}
}
/// This blanket implementation just allocates variables in `Self`
/// element by element.
impl<I, F: Field, A: AllocVar<I, F>> AllocVar<[I], F> for Vec<A> {
fn new_variable<T: Borrow<[I]>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
f().and_then(|v| {
v.borrow()
.iter()
.map(|e| A::new_variable(cs.clone(), || Ok(e), mode))
.collect()
})
}
}
/// Dummy impl for `()`.
impl<F: Field> AllocVar<(), F> for () {
fn new_variable<T: Borrow<()>>(
_cs: impl Into<Namespace<F>>,
_f: impl FnOnce() -> Result<T, SynthesisError>,
_mode: AllocationMode,
) -> Result<Self, SynthesisError> {
Ok(())
}
}
/// This blanket implementation just allocates variables in `Self`
/// element by element.
impl<I, F: Field, A: AllocVar<I, F>, const N: usize> AllocVar<[I; N], F> for [A; N] {
fn new_variable<T: Borrow<[I; N]>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
f().map(|v| {
let v = v.borrow();
core::array::from_fn(|i| A::new_variable(cs.clone(), || Ok(&v[i]), mode).unwrap())
})
}
}
/// This blanket implementation just allocates variables in `Self`
/// element by element.
impl<I, F: Field, A: AllocVar<I, F>, const N: usize> AllocVar<[I], F> for [A; N] {
fn new_variable<T: Borrow<[I]>>(
cs: impl Into<Namespace<F>>,
f: impl FnOnce() -> Result<T, SynthesisError>,
mode: AllocationMode,
) -> Result<Self, SynthesisError> {
let ns = cs.into();
let cs = ns.cs();
f().map(|v| {
let v = v.borrow();
core::array::from_fn(|i| A::new_variable(cs.clone(), || Ok(&v[i]), mode).unwrap())
})
}
}