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