1//! This module implements various low-level gadgets
  2use crate::traits::Group;
  3use bellperson::{
  4  gadgets::{
  5    boolean::{AllocatedBit, Boolean},
  6    num::AllocatedNum,
  7    Assignment,
  8  },
  9  ConstraintSystem, LinearCombination, SynthesisError,
 10};
 11use bellperson_nonnative::mp::bignat::{nat_to_limbs, BigNat};
 12use ff::{Field, PrimeField, PrimeFieldBits};
 13use num_bigint::BigInt;
 14
 15/// Gets as input the little indian representation of a number and spits out the number
 16pub fn le_bits_to_num<Scalar, CS>(
 17  mut cs: CS,
 18  bits: Vec<AllocatedBit>,
 19) -> Result<AllocatedNum<Scalar>, SynthesisError>
 20where
 21  Scalar: PrimeField + PrimeFieldBits,
 22  CS: ConstraintSystem<Scalar>,
 23{
 24  // We loop over the input bits and construct the constraint
 25  // and the field element that corresponds to the result
 26  let mut lc = LinearCombination::zero();
 27  let mut coeff = Scalar::one();
 28  let mut fe = Some(Scalar::zero());
 29  for bit in bits.iter() {
 30    lc = lc + (coeff, bit.get_variable());
 31    fe = bit.get_value().map(|val| {
 32      if val {
 33        fe.unwrap() + coeff
 34      } else {
 35        fe.unwrap()
 36      }
 37    });
 38    coeff = coeff.double();
 39  }
 40  let num = AllocatedNum::alloc(cs.namespace(|| "Field element"), || {
 41    fe.ok_or(SynthesisError::AssignmentMissing)
 42  })?;
 43  lc = lc - num.get_variable();
 44  cs.enforce(|| "compute number from bits", |lc| lc, |lc| lc, |_| lc);
 45  Ok(num)
 46}
 47
 48/// Allocate a variable that is set to zero
 49pub fn alloc_zero<F: PrimeField, CS: ConstraintSystem<F>>(
 50  mut cs: CS,
 51) -> Result<AllocatedNum<F>, SynthesisError> {
 52  let zero = AllocatedNum::alloc(cs.namespace(|| "alloc"), || Ok(F::zero()))?;
 53  cs.enforce(
 54    || "check zero is valid",
 55    |lc| lc,
 56    |lc| lc,
 57    |lc| lc + zero.get_variable(),
 58  );
 59  Ok(zero)
 60}
 61
 62/// Allocate a variable that is set to one
 63pub fn alloc_one<F: PrimeField, CS: ConstraintSystem<F>>(
 64  mut cs: CS,
 65) -> Result<AllocatedNum<F>, SynthesisError> {
 66  let one = AllocatedNum::alloc(cs.namespace(|| "alloc"), || Ok(F::one()))?;
 67  cs.enforce(
 68    || "check one is valid",
 69    |lc| lc + CS::one(),
 70    |lc| lc + CS::one(),
 71    |lc| lc + one.get_variable(),
 72  );
 73
 74  Ok(one)
 75}
 76
 77/// Allocate a scalar as a base. Only to be used is the scalar fits in base!
 78pub fn alloc_scalar_as_base<G, CS>(
 79  mut cs: CS,
 80  input: Option<G::Scalar>,
 81) -> Result<AllocatedNum<G::Base>, SynthesisError>
 82where
 83  G: Group,
 84  <G as Group>::Scalar: PrimeFieldBits,
 85  CS: ConstraintSystem<<G as Group>::Base>,
 86{
 87  AllocatedNum::alloc(cs.namespace(|| "allocate scalar as base"), || {
 88    let input_bits = input.unwrap_or_else(G::Scalar::zero).clone().to_le_bits();
 89    let mut mult = G::Base::one();
 90    let mut val = G::Base::zero();
 91    for bit in input_bits {
 92      if bit {
 93        val += mult;
 94      }
 95      mult = mult + mult;
 96    }
 97    Ok(val)
 98  })
 99}
100
101/// interepret scalar as base
102pub fn scalar_as_base<G: Group>(input: G::Scalar) -> G::Base {
103  let input_bits = input.to_le_bits();
104  let mut mult = G::Base::one();
105  let mut val = G::Base::zero();
106  for bit in input_bits {
107    if bit {
108      val += mult;
109    }
110    mult = mult + mult;
111  }
112  val
113}
114
115/// Allocate bignat a constant
116pub fn alloc_bignat_constant<F: PrimeField, CS: ConstraintSystem<F>>(
117  mut cs: CS,
118  val: &BigInt,
119  limb_width: usize,
120  n_limbs: usize,
121) -> Result<BigNat<F>, SynthesisError> {
122  let limbs = nat_to_limbs(val, limb_width, n_limbs).unwrap();
123  let bignat = BigNat::alloc_from_limbs(
124    cs.namespace(|| "alloc bignat"),
125    || Ok(limbs.clone()),
126    None,
127    limb_width,
128    n_limbs,
129  )?;
130  // Now enforce that the limbs are all equal to the constants
131  #[allow(clippy::needless_range_loop)]
132  for i in 0..n_limbs {
133    cs.enforce(
134      || format!("check limb {}", i),
135      |lc| lc + &bignat.limbs[i],
136      |lc| lc + CS::one(),
137      |lc| lc + (limbs[i], CS::one()),
138    );
139  }
140  Ok(bignat)
141}
142
143/// Check that two numbers are equal and return a bit
144pub fn alloc_num_equals<F: PrimeField, CS: ConstraintSystem<F>>(
145  mut cs: CS,
146  a: &AllocatedNum<F>,
147  b: &AllocatedNum<F>,
148) -> Result<AllocatedBit, SynthesisError> {
149  // Allocate and constrain `r`: result boolean bit.
150  // It equals `true` if `a` equals `b`, `false` otherwise
151  let r_value = match (a.get_value(), b.get_value()) {
152    (Some(a), Some(b)) => Some(a == b),
153    _ => None,
154  };
155
156  let r = AllocatedBit::alloc(cs.namespace(|| "r"), r_value)?;
157
158  let delta = AllocatedNum::alloc(cs.namespace(|| "delta"), || {
159    let a_value = *a.get_value().get()?;
160    let b_value = *b.get_value().get()?;
161
162    let mut delta = a_value;
163    delta.sub_assign(&b_value);
164
165    Ok(delta)
166  })?;
167
168  cs.enforce(
169    || "delta = (a - b)",
170    |lc| lc + a.get_variable() - b.get_variable(),
171    |lc| lc + CS::one(),
172    |lc| lc + delta.get_variable(),
173  );
174
175  let delta_inv = AllocatedNum::alloc(cs.namespace(|| "delta_inv"), || {
176    let delta = *delta.get_value().get()?;
177
178    if delta.is_zero().unwrap_u8() == 1 {
179      Ok(F::one()) // we can return any number here, it doesn't matter
180    } else {
181      Ok(delta.invert().unwrap())
182    }
183  })?;
184
185  // Allocate `t = delta * delta_inv`
186  // If `delta` is non-zero (a != b), `t` will equal 1
187  // If `delta` is zero (a == b), `t` cannot equal 1
188  let t = AllocatedNum::alloc(cs.namespace(|| "t"), || {
189    let mut tmp = *delta.get_value().get()?;
190    tmp.mul_assign(&(*delta_inv.get_value().get()?));
191
192    Ok(tmp)
193  })?;
194
195  // Constrain allocation:
196  // t = (a - b) * delta_inv
197  cs.enforce(
198    || "t = (a - b) * delta_inv",
199    |lc| lc + a.get_variable() - b.get_variable(),
200    |lc| lc + delta_inv.get_variable(),
201    |lc| lc + t.get_variable(),
202  );
203
204  // Constrain:
205  // (a - b) * (t - 1) == 0
206  // This enforces that correct `delta_inv` was provided,
207  // and thus `t` is 1 if `(a - b)` is non zero (a != b )
208  cs.enforce(
209    || "(a - b) * (t - 1) == 0",
210    |lc| lc + a.get_variable() - b.get_variable(),
211    |lc| lc + t.get_variable() - CS::one(),
212    |lc| lc,
213  );
214
215  // Constrain:
216  // (a - b) * r == 0
217  // This enforces that `r` is zero if `(a - b)` is non-zero (a != b)
218  cs.enforce(
219    || "(a - b) * r == 0",
220    |lc| lc + a.get_variable() - b.get_variable(),
221    |lc| lc + r.get_variable(),
222    |lc| lc,
223  );
224
225  // Constrain:
226  // (t - 1) * (r - 1) == 0
227  // This enforces that `r` is one if `t` is not one (a == b)
228  cs.enforce(
229    || "(t - 1) * (r - 1) == 0",
230    |lc| lc + t.get_variable() - CS::one(),
231    |lc| lc + r.get_variable() - CS::one(),
232    |lc| lc,
233  );
234
235  Ok(r)
236}
237
238/// If condition return a otherwise b
239pub fn conditionally_select<F: PrimeField, CS: ConstraintSystem<F>>(
240  mut cs: CS,
241  a: &AllocatedNum<F>,
242  b: &AllocatedNum<F>,
243  condition: &Boolean,
244) -> Result<AllocatedNum<F>, SynthesisError> {
245  let c = AllocatedNum::alloc(cs.namespace(|| "conditional select result"), || {
246    if *condition.get_value().get()? {
247      Ok(*a.get_value().get()?)
248    } else {
249      Ok(*b.get_value().get()?)
250    }
251  })?;
252
253  // a * condition + b*(1-condition) = c ->
254  // a * condition - b*condition = c - b
255  cs.enforce(
256    || "conditional select constraint",
257    |lc| lc + a.get_variable() - b.get_variable(),
258    |_| condition.lc(CS::one(), F::one()),
259    |lc| lc + c.get_variable() - b.get_variable(),
260  );
261
262  Ok(c)
263}
264
265/// If condition return a otherwise b where a and b are BigNats
266pub fn conditionally_select_bignat<F: PrimeField, CS: ConstraintSystem<F>>(
267  mut cs: CS,
268  a: &BigNat<F>,
269  b: &BigNat<F>,
270  condition: &Boolean,
271) -> Result<BigNat<F>, SynthesisError> {
272  assert!(a.limbs.len() == b.limbs.len());
273  let c = BigNat::alloc_from_nat(
274    cs.namespace(|| "conditional select result"),
275    || {
276      if *condition.get_value().get()? {
277        Ok(a.value.get()?.clone())
278      } else {
279        Ok(b.value.get()?.clone())
280      }
281    },
282    a.params.limb_width,
283    a.params.n_limbs,
284  )?;
285
286  // a * condition + b*(1-condition) = c ->
287  // a * condition - b*condition = c - b
288  for i in 0..c.limbs.len() {
289    cs.enforce(
290      || format!("conditional select constraint {}", i),
291      |lc| lc + &a.limbs[i] - &b.limbs[i],
292      |_| condition.lc(CS::one(), F::one()),
293      |lc| lc + &c.limbs[i] - &b.limbs[i],
294    );
295  }
296  Ok(c)
297}
298
299/// Same as the above but Condition is an AllocatedNum that needs to be
300/// 0 or 1. 1 => True, 0 => False
301pub fn conditionally_select2<F: PrimeField, CS: ConstraintSystem<F>>(
302  mut cs: CS,
303  a: &AllocatedNum<F>,
304  b: &AllocatedNum<F>,
305  condition: &AllocatedNum<F>,
306) -> Result<AllocatedNum<F>, SynthesisError> {
307  let c = AllocatedNum::alloc(cs.namespace(|| "conditional select result"), || {
308    if *condition.get_value().get()? == F::one() {
309      Ok(*a.get_value().get()?)
310    } else {
311      Ok(*b.get_value().get()?)
312    }
313  })?;
314
315  // a * condition + b*(1-condition) = c ->
316  // a * condition - b*condition = c - b
317  cs.enforce(
318    || "conditional select constraint",
319    |lc| lc + a.get_variable() - b.get_variable(),
320    |lc| lc + condition.get_variable(),
321    |lc| lc + c.get_variable() - b.get_variable(),
322  );
323
324  Ok(c)
325}
326
327/// If condition set to 0 otherwise a
328pub fn select_zero_or<F: PrimeField, CS: ConstraintSystem<F>>(
329  mut cs: CS,
330  a: &AllocatedNum<F>,
331  condition: &AllocatedNum<F>,
332) -> Result<AllocatedNum<F>, SynthesisError> {
333  let c = AllocatedNum::alloc(cs.namespace(|| "conditional select result"), || {
334    if *condition.get_value().get()? == F::one() {
335      Ok(F::zero())
336    } else {
337      Ok(*a.get_value().get()?)
338    }
339  })?;
340
341  // a * (1 - condition) = c
342  cs.enforce(
343    || "conditional select constraint",
344    |lc| lc + a.get_variable(),
345    |lc| lc + CS::one() - condition.get_variable(),
346    |lc| lc + c.get_variable(),
347  );
348
349  Ok(c)
350}
351
352/// If condition set to 1 otherwise a
353pub fn select_one_or<F: PrimeField, CS: ConstraintSystem<F>>(
354  mut cs: CS,
355  a: &AllocatedNum<F>,
356  condition: &AllocatedNum<F>,
357) -> Result<AllocatedNum<F>, SynthesisError> {
358  let c = AllocatedNum::alloc(cs.namespace(|| "conditional select result"), || {
359    if *condition.get_value().get()? == F::one() {
360      Ok(F::one())
361    } else {
362      Ok(*a.get_value().get()?)
363    }
364  })?;
365
366  cs.enforce(
367    || "conditional select constraint",
368    |lc| lc + CS::one() - a.get_variable(),
369    |lc| lc + condition.get_variable(),
370    |lc| lc + c.get_variable() - a.get_variable(),
371  );
372  Ok(c)
373}