Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
sha256_aux.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for auxiliary gadgets for the SHA256 gadget.
5 
6  See sha256_aux.hpp .
7 
8  *****************************************************************************
9  * @author This file is part of libsnark, developed by SCIPR Lab
10  * and contributors (see AUTHORS).
11  * @copyright MIT license (see LICENSE file)
12  *****************************************************************************/
13 
14 #ifndef SHA256_AUX_TCC_
15 #define SHA256_AUX_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename FieldT>
21 lastbits_gadget<FieldT>::lastbits_gadget(
22  protoboard<FieldT> &pb,
23  const pb_variable<FieldT> &X,
24  const size_t X_bits,
25  const pb_variable<FieldT> &result,
26  const pb_linear_combination_array<FieldT> &result_bits,
27  const std::string &annotation_prefix)
28  : gadget<FieldT>(pb, annotation_prefix)
29  , X(X)
30  , X_bits(X_bits)
31  , result(result)
32  , result_bits(result_bits)
33 {
34  full_bits = result_bits;
35  for (size_t i = result_bits.size(); i < X_bits; ++i) {
36  pb_variable<FieldT> full_bits_overflow;
37  full_bits_overflow.allocate(
38  pb, FMT(this->annotation_prefix, " full_bits_%zu", i));
39  full_bits.emplace_back(full_bits_overflow);
40  }
41 
42  unpack_bits.reset(new packing_gadget<FieldT>(
43  pb, full_bits, X, FMT(this->annotation_prefix, " unpack_bits")));
44  pack_result.reset(new packing_gadget<FieldT>(
45  pb, result_bits, result, FMT(this->annotation_prefix, " pack_result")));
46 }
47 
48 template<typename FieldT>
49 void lastbits_gadget<FieldT>::generate_r1cs_constraints()
50 {
51  unpack_bits->generate_r1cs_constraints(true);
52  pack_result->generate_r1cs_constraints(false);
53 }
54 
55 template<typename FieldT> void lastbits_gadget<FieldT>::generate_r1cs_witness()
56 {
57  unpack_bits->generate_r1cs_witness_from_packed();
58  pack_result->generate_r1cs_witness_from_bits();
59 }
60 
61 template<typename FieldT>
62 XOR3_gadget<FieldT>::XOR3_gadget(
63  protoboard<FieldT> &pb,
64  const pb_linear_combination<FieldT> &A,
65  const pb_linear_combination<FieldT> &B,
66  const pb_linear_combination<FieldT> &C,
67  const bool assume_C_is_zero,
68  const pb_linear_combination<FieldT> &out,
69  const std::string &annotation_prefix)
70  : gadget<FieldT>(pb, annotation_prefix)
71  , A(A)
72  , B(B)
73  , C(C)
74  , assume_C_is_zero(assume_C_is_zero)
75  , out(out)
76 {
77  if (!assume_C_is_zero) {
78  tmp.allocate(pb, FMT(this->annotation_prefix, " tmp"));
79  }
80 }
81 
82 template<typename FieldT> void XOR3_gadget<FieldT>::generate_r1cs_constraints()
83 {
84  /*
85  tmp = A + B - 2AB i.e. tmp = A xor B
86  out = tmp + C - 2tmp C i.e. out = tmp xor C
87  */
88  if (assume_C_is_zero) {
89  this->pb.add_r1cs_constraint(
90  r1cs_constraint<FieldT>(2 * A, B, A + B - out),
91  FMT(this->annotation_prefix, " implicit_tmp_equals_out"));
92  } else {
93  this->pb.add_r1cs_constraint(
94  r1cs_constraint<FieldT>(2 * A, B, A + B - tmp),
95  FMT(this->annotation_prefix, " tmp"));
96  this->pb.add_r1cs_constraint(
97  r1cs_constraint<FieldT>(2 * tmp, C, tmp + C - out),
98  FMT(this->annotation_prefix, " out"));
99  }
100 }
101 
102 template<typename FieldT> void XOR3_gadget<FieldT>::generate_r1cs_witness()
103 {
104  if (assume_C_is_zero) {
105  this->pb.lc_val(out) =
106  this->pb.lc_val(A) + this->pb.lc_val(B) -
107  FieldT(2) * this->pb.lc_val(A) * this->pb.lc_val(B);
108  } else {
109  this->pb.val(tmp) = this->pb.lc_val(A) + this->pb.lc_val(B) -
110  FieldT(2) * this->pb.lc_val(A) * this->pb.lc_val(B);
111  this->pb.lc_val(out) =
112  this->pb.val(tmp) + this->pb.lc_val(C) -
113  FieldT(2) * this->pb.val(tmp) * this->pb.lc_val(C);
114  }
115 }
116 
117 #define SHA256_GADGET_ROTR(A, i, k) A[((i) + (k)) % 32]
118 
119 /* Page 10 of http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf */
120 template<typename FieldT>
121 small_sigma_gadget<FieldT>::small_sigma_gadget(
122  protoboard<FieldT> &pb,
123  const pb_variable_array<FieldT> &W,
124  const pb_variable<FieldT> &result,
125  const size_t rot1,
126  const size_t rot2,
127  const size_t shift,
128  const std::string &annotation_prefix)
129  : gadget<FieldT>(pb, annotation_prefix), W(W), result(result)
130 {
131  result_bits.allocate(pb, 32, FMT(this->annotation_prefix, " result_bits"));
132  compute_bits.resize(32);
133  for (size_t i = 0; i < 32; ++i) {
134  compute_bits[i].reset(new XOR3_gadget<FieldT>(
135  pb,
136  SHA256_GADGET_ROTR(W, i, rot1),
137  SHA256_GADGET_ROTR(W, i, rot2),
138  (i + shift < 32 ? W[i + shift] : ONE),
139  (i + shift >= 32),
140  result_bits[i],
141  FMT(this->annotation_prefix, " compute_bits_%zu", i)));
142  }
143  pack_result.reset(new packing_gadget<FieldT>(
144  pb, result_bits, result, FMT(this->annotation_prefix, " pack_result")));
145 }
146 
147 template<typename FieldT>
148 void small_sigma_gadget<FieldT>::generate_r1cs_constraints()
149 {
150  for (size_t i = 0; i < 32; ++i) {
151  compute_bits[i]->generate_r1cs_constraints();
152  }
153 
154  pack_result->generate_r1cs_constraints(false);
155 }
156 
157 template<typename FieldT>
158 void small_sigma_gadget<FieldT>::generate_r1cs_witness()
159 {
160  for (size_t i = 0; i < 32; ++i) {
161  compute_bits[i]->generate_r1cs_witness();
162  }
163 
164  pack_result->generate_r1cs_witness_from_bits();
165 }
166 
167 template<typename FieldT>
168 big_sigma_gadget<FieldT>::big_sigma_gadget(
169  protoboard<FieldT> &pb,
170  const pb_linear_combination_array<FieldT> &W,
171  const pb_variable<FieldT> &result,
172  const size_t rot1,
173  const size_t rot2,
174  const size_t rot3,
175  const std::string &annotation_prefix)
176  : gadget<FieldT>(pb, annotation_prefix), W(W), result(result)
177 {
178  result_bits.allocate(pb, 32, FMT(this->annotation_prefix, " result_bits"));
179  compute_bits.resize(32);
180  for (size_t i = 0; i < 32; ++i) {
181  compute_bits[i].reset(new XOR3_gadget<FieldT>(
182  pb,
183  SHA256_GADGET_ROTR(W, i, rot1),
184  SHA256_GADGET_ROTR(W, i, rot2),
185  SHA256_GADGET_ROTR(W, i, rot3),
186  false,
187  result_bits[i],
188  FMT(this->annotation_prefix, " compute_bits_%zu", i)));
189  }
190 
191  pack_result.reset(new packing_gadget<FieldT>(
192  pb, result_bits, result, FMT(this->annotation_prefix, " pack_result")));
193 }
194 
195 template<typename FieldT>
196 void big_sigma_gadget<FieldT>::generate_r1cs_constraints()
197 {
198  for (size_t i = 0; i < 32; ++i) {
199  compute_bits[i]->generate_r1cs_constraints();
200  }
201 
202  pack_result->generate_r1cs_constraints(false);
203 }
204 
205 template<typename FieldT> void big_sigma_gadget<FieldT>::generate_r1cs_witness()
206 {
207  for (size_t i = 0; i < 32; ++i) {
208  compute_bits[i]->generate_r1cs_witness();
209  }
210 
211  pack_result->generate_r1cs_witness_from_bits();
212 }
213 
214 /* Page 10 of http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf */
215 template<typename FieldT>
216 choice_gadget<FieldT>::choice_gadget(
217  protoboard<FieldT> &pb,
218  const pb_linear_combination_array<FieldT> &X,
219  const pb_linear_combination_array<FieldT> &Y,
220  const pb_linear_combination_array<FieldT> &Z,
221  const pb_variable<FieldT> &result,
222  const std::string &annotation_prefix)
223  : gadget<FieldT>(pb, annotation_prefix), X(X), Y(Y), Z(Z), result(result)
224 {
225  result_bits.allocate(pb, 32, FMT(this->annotation_prefix, " result_bits"));
226  pack_result.reset(new packing_gadget<FieldT>(
227  pb, result_bits, result, FMT(this->annotation_prefix, " result")));
228 }
229 
230 template<typename FieldT>
231 void choice_gadget<FieldT>::generate_r1cs_constraints()
232 {
233  for (size_t i = 0; i < 32; ++i) {
234  /*
235  result = x * y + (1-x) * z
236  result - z = x * (y - z)
237  */
238  this->pb.add_r1cs_constraint(
239  r1cs_constraint<FieldT>(X[i], Y[i] - Z[i], result_bits[i] - Z[i]),
240  FMT(this->annotation_prefix, " result_bits_%zu", i));
241  }
242  pack_result->generate_r1cs_constraints(false);
243 }
244 
245 template<typename FieldT> void choice_gadget<FieldT>::generate_r1cs_witness()
246 {
247  for (size_t i = 0; i < 32; ++i) {
248  this->pb.val(result_bits[i]) =
249  this->pb.lc_val(X[i]) * this->pb.lc_val(Y[i]) +
250  (FieldT::one() - this->pb.lc_val(X[i])) * this->pb.lc_val(Z[i]);
251  }
252  pack_result->generate_r1cs_witness_from_bits();
253 }
254 
255 /* Page 10 of http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf */
256 template<typename FieldT>
257 majority_gadget<FieldT>::majority_gadget(
258  protoboard<FieldT> &pb,
259  const pb_linear_combination_array<FieldT> &X,
260  const pb_linear_combination_array<FieldT> &Y,
261  const pb_linear_combination_array<FieldT> &Z,
262  const pb_variable<FieldT> &result,
263  const std::string &annotation_prefix)
264  : gadget<FieldT>(pb, annotation_prefix), X(X), Y(Y), Z(Z), result(result)
265 {
266  result_bits.allocate(pb, 32, FMT(this->annotation_prefix, " result_bits"));
267  pack_result.reset(new packing_gadget<FieldT>(
268  pb, result_bits, result, FMT(this->annotation_prefix, " result")));
269 }
270 
271 template<typename FieldT>
272 void majority_gadget<FieldT>::generate_r1cs_constraints()
273 {
274  for (size_t i = 0; i < 32; ++i) {
275  /*
276  2*result + aux = x + y + z
277  x, y, z, aux -- bits
278  aux = x + y + z - 2*result
279  */
280  generate_boolean_r1cs_constraint<FieldT>(
281  this->pb,
282  result_bits[i],
283  FMT(this->annotation_prefix, " result_%zu", i));
284  this->pb.add_r1cs_constraint(
285  r1cs_constraint<FieldT>(
286  X[i] + Y[i] + Z[i] - 2 * result_bits[i],
287  1 - (X[i] + Y[i] + Z[i] - 2 * result_bits[i]),
288  0),
289  FMT(this->annotation_prefix, " result_bits_%zu", i));
290  }
291  pack_result->generate_r1cs_constraints(false);
292 }
293 
294 template<typename FieldT> void majority_gadget<FieldT>::generate_r1cs_witness()
295 {
296  for (size_t i = 0; i < 32; ++i) {
297  const long v = (this->pb.lc_val(X[i]) + this->pb.lc_val(Y[i]) +
298  this->pb.lc_val(Z[i]))
299  .as_ulong();
300  this->pb.val(result_bits[i]) = FieldT(v / 2);
301  }
302 
303  pack_result->generate_r1cs_witness_from_bits();
304 }
305 
306 } // namespace libsnark
307 
308 #endif // SHA256_AUX_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17