Nova/src/gadgets/nonnative/util.rs
src/gadgets/nonnative/util.rsRaw
1use super::{BitAccess, OptionExt};
2use bellperson::{
3 gadgets::num::AllocatedNum,
4 {ConstraintSystem, LinearCombination, SynthesisError, Variable},
5};
6use byteorder::WriteBytesExt;
7use ff::PrimeField;
8use num_bigint::{BigInt, Sign};
9use std::convert::From;
10use std::io::{self, Write};
11
12#[derive(Clone)]
13/// A representation of a bit
14pub struct Bit<Scalar: PrimeField> {
15 /// The linear combination which constrain the value of the bit
16 pub bit: LinearCombination<Scalar>,
17 /// The value of the bit (filled at witness-time)
18 pub value: Option<bool>,
19}
20
21#[derive(Clone)]
22/// A representation of a bit-vector
23pub struct Bitvector<Scalar: PrimeField> {
24 /// The linear combination which constrain the values of the bits
25 pub bits: Vec<LinearCombination<Scalar>>,
26 /// The value of the bits (filled at witness-time)
27 pub values: Option<Vec<bool>>,
28 /// Allocated bit variables
29 pub allocations: Vec<Bit<Scalar>>,
30}
31
32impl<Scalar: PrimeField> Bit<Scalar> {
33 /// Allocate a variable in the constraint system which can only be a
34 /// boolean value.
35 pub fn alloc<CS>(mut cs: CS, value: Option<bool>) -> Result<Self, SynthesisError>
36 where
37 CS: ConstraintSystem<Scalar>,
38 {
39 let var = cs.alloc(
40 || "boolean",
41 || {
42 if *value.grab()? {
43 Ok(Scalar::one())
44 } else {
45 Ok(Scalar::zero())
46 }
47 },
48 )?;
49
50 // Constrain: (1 - a) * a = 0
51 // This constrains a to be either 0 or 1.
52 cs.enforce(
53 || "boolean constraint",
54 |lc| lc + CS::one() - var,
55 |lc| lc + var,
56 |lc| lc,
57 );
58
59 Ok(Self {
60 bit: LinearCombination::zero() + var,
61 value,
62 })
63 }
64}
65
66pub struct Num<Scalar: PrimeField> {
67 pub num: LinearCombination<Scalar>,
68 pub value: Option<Scalar>,
69}
70
71impl<Scalar: PrimeField> Num<Scalar> {
72 pub fn new(value: Option<Scalar>, num: LinearCombination<Scalar>) -> Self {
73 Self { value, num }
74 }
75 pub fn alloc<CS, F>(mut cs: CS, value: F) -> Result<Self, SynthesisError>
76 where
77 CS: ConstraintSystem<Scalar>,
78 F: FnOnce() -> Result<Scalar, SynthesisError>,
79 {
80 let mut new_value = None;
81 let var = cs.alloc(
82 || "num",
83 || {
84 let tmp = value()?;
85
86 new_value = Some(tmp);
87
88 Ok(tmp)
89 },
90 )?;
91
92 Ok(Num {
93 value: new_value,
94 num: LinearCombination::zero() + var,
95 })
96 }
97
98 pub fn fits_in_bits<CS: ConstraintSystem<Scalar>>(
99 &self,
100 mut cs: CS,
101 n_bits: usize,
102 ) -> Result<(), SynthesisError> {
103 let v = self.value;
104
105 // Allocate all but the first bit.
106 let bits: Vec<Variable> = (1..n_bits)
107 .map(|i| {
108 cs.alloc(
109 || format!("bit {}", i),
110 || {
111 let r = if *v.grab()?.get_bit(i).grab()? {
112 Scalar::one()
113 } else {
114 Scalar::zero()
115 };
116 Ok(r)
117 },
118 )
119 })
120 .collect::<Result<_, _>>()?;
121
122 for (i, v) in bits.iter().enumerate() {
123 cs.enforce(
124 || format!("{} is bit", i),
125 |lc| lc + *v,
126 |lc| lc + CS::one() - *v,
127 |lc| lc,
128 )
129 }
130
131 // Last bit
132 cs.enforce(
133 || "last bit",
134 |mut lc| {
135 let mut f = Scalar::one();
136 lc = lc + &self.num;
137 for v in bits.iter() {
138 f = f.double();
139 lc = lc - (f, *v);
140 }
141 lc
142 },
143 |mut lc| {
144 lc = lc + CS::one();
145 let mut f = Scalar::one();
146 lc = lc - &self.num;
147 for v in bits.iter() {
148 f = f.double();
149 lc = lc + (f, *v);
150 }
151 lc
152 },
153 |lc| lc,
154 );
155 Ok(())
156 }
157
158 /// Computes the natural number represented by an array of bits.
159 /// Checks if the natural number equals `self`
160 pub fn is_equal<CS: ConstraintSystem<Scalar>>(
161 &self,
162 mut cs: CS,
163 other: &Bitvector<Scalar>,
164 ) -> Result<(), SynthesisError> {
165 let allocations = other.allocations.clone();
166 let mut f = Scalar::one();
167 let sum = allocations
168 .iter()
169 .fold(LinearCombination::zero(), |lc, bit| {
170 let l = lc + (f, &bit.bit);
171 f = f.double();
172 l
173 });
174 let sum_lc = LinearCombination::zero() + &self.num - ∑
175 cs.enforce(|| "sum", |lc| lc + &sum_lc, |lc| lc + CS::one(), |lc| lc);
176 Ok(())
177 }
178
179 /// Compute the natural number represented by an array of limbs.
180 /// The limbs are assumed to be based the `limb_width` power of 2.
181 /// Low-index bits are low-order
182 pub fn decompose<CS: ConstraintSystem<Scalar>>(
183 &self,
184 mut cs: CS,
185 n_bits: usize,
186 ) -> Result<Bitvector<Scalar>, SynthesisError> {
187 let values: Option<Vec<bool>> = self.value.as_ref().map(|v| {
188 let num = *v;
189 (0..n_bits).map(|i| num.get_bit(i).unwrap()).collect()
190 });
191 let allocations: Vec<Bit<Scalar>> = (0..n_bits)
192 .map(|bit_i| {
193 Bit::alloc(
194 cs.namespace(|| format!("bit{}", bit_i)),
195 values.as_ref().map(|vs| vs[bit_i]),
196 )
197 })
198 .collect::<Result<Vec<_>, _>>()?;
199 let mut f = Scalar::one();
200 let sum = allocations
201 .iter()
202 .fold(LinearCombination::zero(), |lc, bit| {
203 let l = lc + (f, &bit.bit);
204 f = f.double();
205 l
206 });
207 let sum_lc = LinearCombination::zero() + &self.num - ∑
208 cs.enforce(|| "sum", |lc| lc + &sum_lc, |lc| lc + CS::one(), |lc| lc);
209 let bits: Vec<LinearCombination<Scalar>> = allocations
210 .clone()
211 .into_iter()
212 .map(|a| LinearCombination::zero() + &a.bit)
213 .collect();
214 Ok(Bitvector {
215 allocations,
216 values,
217 bits,
218 })
219 }
220
221 pub fn as_allocated_num<CS: ConstraintSystem<Scalar>>(
222 &self,
223 mut cs: CS,
224 ) -> Result<AllocatedNum<Scalar>, SynthesisError> {
225 let new = AllocatedNum::alloc(cs.namespace(|| "alloc"), || Ok(*self.value.grab()?))?;
226 cs.enforce(
227 || "eq",
228 |lc| lc,
229 |lc| lc,
230 |lc| lc + new.get_variable() - &self.num,
231 );
232 Ok(new)
233 }
234}
235
236impl<Scalar: PrimeField> From<AllocatedNum<Scalar>> for Num<Scalar> {
237 fn from(a: AllocatedNum<Scalar>) -> Self {
238 Self::new(a.get_value(), LinearCombination::zero() + a.get_variable())
239 }
240}
241
242fn write_be<F: PrimeField, W: Write>(f: &F, mut writer: W) -> io::Result<()> {
243 for digit in f.to_repr().as_ref().iter().rev() {
244 writer.write_u8(*digit)?;
245 }
246
247 Ok(())
248}
249
250/// Convert a field element to a natural number
251pub fn f_to_nat<Scalar: PrimeField>(f: &Scalar) -> BigInt {
252 let mut s = Vec::new();
253 write_be(f, &mut s).unwrap(); // f.to_repr().write_be(&mut s).unwrap();
254 BigInt::from_bytes_le(Sign::Plus, f.to_repr().as_ref())
255}
256
257/// Convert a natural number to a field element.
258/// Returns `None` if the number is too big for the field.
259pub fn nat_to_f<Scalar: PrimeField>(n: &BigInt) -> Option<Scalar> {
260 Scalar::from_str_vartime(&format!("{}", n))
261}