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