Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
sha256_components.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for gadgets for the SHA256 message schedule and
5  round function.
6 
7  See sha256_components.hpp .
8 
9  *****************************************************************************
10  * @author This file is part of libsnark, developed by SCIPR Lab
11  * and contributors (see AUTHORS).
12  * @copyright MIT license (see LICENSE file)
13  *****************************************************************************/
14 
15 #ifndef SHA256_COMPONENTS_TCC_
16 #define SHA256_COMPONENTS_TCC_
17 
18 namespace libsnark
19 {
20 
21 const unsigned long SHA256_K[64] = {
22  0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1,
23  0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3,
24  0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786,
25  0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
26  0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147,
27  0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13,
28  0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b,
29  0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
30  0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a,
31  0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208,
32  0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2};
33 
34 const unsigned long SHA256_H[8] = {
35  0x6a09e667,
36  0xbb67ae85,
37  0x3c6ef372,
38  0xa54ff53a,
39  0x510e527f,
40  0x9b05688c,
41  0x1f83d9ab,
42  0x5be0cd19};
43 
44 template<typename FieldT>
45 pb_linear_combination_array<FieldT> SHA256_default_IV(protoboard<FieldT> &pb)
46 {
47  pb_linear_combination_array<FieldT> result;
48  result.reserve(SHA256_digest_size);
49 
50  for (size_t i = 0; i < SHA256_digest_size; ++i) {
51  int iv_val = (SHA256_H[i / 32] >> (31 - (i % 32))) & 1;
52 
53  pb_linear_combination<FieldT> iv_element;
54  iv_element.assign(pb, iv_val * ONE);
55  iv_element.evaluate(pb);
56 
57  result.emplace_back(iv_element);
58  }
59 
60  return result;
61 }
62 
63 template<typename FieldT>
64 sha256_message_schedule_gadget<FieldT>::sha256_message_schedule_gadget(
65  protoboard<FieldT> &pb,
66  const pb_variable_array<FieldT> &M,
67  const pb_variable_array<FieldT> &packed_W,
68  const std::string &annotation_prefix)
69  : gadget<FieldT>(pb, annotation_prefix), M(M), packed_W(packed_W)
70 {
71  W_bits.resize(64);
72 
73  pack_W.resize(16);
74  for (size_t i = 0; i < 16; ++i) {
75  W_bits[i] = pb_variable_array<FieldT>(
76  M.rbegin() + (15 - i) * 32, M.rbegin() + (16 - i) * 32);
77  pack_W[i].reset(new packing_gadget<FieldT>(
78  pb,
79  W_bits[i],
80  packed_W[i],
81  FMT(this->annotation_prefix, " pack_W_%zu", i)));
82  }
83 
84  /* NB: some of those will be un-allocated */
85  sigma0.resize(64);
86  sigma1.resize(64);
87  compute_sigma0.resize(64);
88  compute_sigma1.resize(64);
89  unreduced_W.resize(64);
90  mod_reduce_W.resize(64);
91 
92  for (size_t i = 16; i < 64; ++i) {
93  /* allocate result variables for sigma0/sigma1 invocations */
94  sigma0[i].allocate(pb, FMT(this->annotation_prefix, " sigma0_%zu", i));
95  sigma1[i].allocate(pb, FMT(this->annotation_prefix, " sigma1_%zu", i));
96 
97  /* compute sigma0/sigma1 */
98  compute_sigma0[i].reset(new small_sigma_gadget<FieldT>(
99  pb,
100  W_bits[i - 15],
101  sigma0[i],
102  7,
103  18,
104  3,
105  FMT(this->annotation_prefix, " compute_sigma0_%zu", i)));
106  compute_sigma1[i].reset(new small_sigma_gadget<FieldT>(
107  pb,
108  W_bits[i - 2],
109  sigma1[i],
110  17,
111  19,
112  10,
113  FMT(this->annotation_prefix, " compute_sigma1_%zu", i)));
114 
115  /* unreduced_W = sigma0(W_{i-15}) + sigma1(W_{i-2}) + W_{i-7} + W_{i-16}
116  * before modulo 2^32 */
117  unreduced_W[i].allocate(
118  pb, FMT(this->annotation_prefix, " unreduced_W_%zu", i));
119 
120  /* allocate the bit representation of packed_W[i] */
121  W_bits[i].allocate(
122  pb, 32, FMT(this->annotation_prefix, " W_bits_%zu", i));
123 
124  /* and finally reduce this into packed and bit representations */
125  mod_reduce_W[i].reset(new lastbits_gadget<FieldT>(
126  pb,
127  unreduced_W[i],
128  32 + 2,
129  packed_W[i],
130  W_bits[i],
131  FMT(this->annotation_prefix, " mod_reduce_W_%zu", i)));
132  }
133 }
134 
135 template<typename FieldT>
136 void sha256_message_schedule_gadget<FieldT>::generate_r1cs_constraints()
137 {
138  for (size_t i = 0; i < 16; ++i) {
139  pack_W[i]->generate_r1cs_constraints(
140  false); // do not enforce bitness here; caller be aware.
141  }
142 
143  for (size_t i = 16; i < 64; ++i) {
144  compute_sigma0[i]->generate_r1cs_constraints();
145  compute_sigma1[i]->generate_r1cs_constraints();
146 
147  this->pb.add_r1cs_constraint(
148  r1cs_constraint<FieldT>(
149  1,
150  sigma0[i] + sigma1[i] + packed_W[i - 16] + packed_W[i - 7],
151  unreduced_W[i]),
152  FMT(this->annotation_prefix, " unreduced_W_%zu", i));
153 
154  mod_reduce_W[i]->generate_r1cs_constraints();
155  }
156 }
157 
158 template<typename FieldT>
159 void sha256_message_schedule_gadget<FieldT>::generate_r1cs_witness()
160 {
161  for (size_t i = 0; i < 16; ++i) {
162  pack_W[i]->generate_r1cs_witness_from_bits();
163  }
164 
165  for (size_t i = 16; i < 64; ++i) {
166  compute_sigma0[i]->generate_r1cs_witness();
167  compute_sigma1[i]->generate_r1cs_witness();
168 
169  this->pb.val(unreduced_W[i]) =
170  this->pb.val(sigma0[i]) + this->pb.val(sigma1[i]) +
171  this->pb.val(packed_W[i - 16]) + this->pb.val(packed_W[i - 7]);
172  mod_reduce_W[i]->generate_r1cs_witness();
173  }
174 }
175 
176 template<typename FieldT>
177 sha256_round_function_gadget<FieldT>::sha256_round_function_gadget(
178  protoboard<FieldT> &pb,
179  const pb_linear_combination_array<FieldT> &a,
180  const pb_linear_combination_array<FieldT> &b,
181  const pb_linear_combination_array<FieldT> &c,
182  const pb_linear_combination_array<FieldT> &d,
183  const pb_linear_combination_array<FieldT> &e,
184  const pb_linear_combination_array<FieldT> &f,
185  const pb_linear_combination_array<FieldT> &g,
186  const pb_linear_combination_array<FieldT> &h,
187  const pb_variable<FieldT> &W,
188  const long &K,
189  const pb_linear_combination_array<FieldT> &new_a,
190  const pb_linear_combination_array<FieldT> &new_e,
191  const std::string &annotation_prefix)
192  : gadget<FieldT>(pb, annotation_prefix)
193  , a(a)
194  , b(b)
195  , c(c)
196  , d(d)
197  , e(e)
198  , f(f)
199  , g(g)
200  , h(h)
201  , W(W)
202  , K(K)
203  , new_a(new_a)
204  , new_e(new_e)
205 {
206  /* compute sigma0 and sigma1 */
207  sigma0.allocate(pb, FMT(this->annotation_prefix, " sigma0"));
208  sigma1.allocate(pb, FMT(this->annotation_prefix, " sigma1"));
209  compute_sigma0.reset(new big_sigma_gadget<FieldT>(
210  pb,
211  a,
212  sigma0,
213  2,
214  13,
215  22,
216  FMT(this->annotation_prefix, " compute_sigma0")));
217  compute_sigma1.reset(new big_sigma_gadget<FieldT>(
218  pb,
219  e,
220  sigma1,
221  6,
222  11,
223  25,
224  FMT(this->annotation_prefix, " compute_sigma1")));
225 
226  /* compute choice */
227  choice.allocate(pb, FMT(this->annotation_prefix, " choice"));
228  compute_choice.reset(new choice_gadget<FieldT>(
229  pb, e, f, g, choice, FMT(this->annotation_prefix, " compute_choice")));
230 
231  /* compute majority */
232  majority.allocate(pb, FMT(this->annotation_prefix, " majority"));
233  compute_majority.reset(new majority_gadget<FieldT>(
234  pb,
235  a,
236  b,
237  c,
238  majority,
239  FMT(this->annotation_prefix, " compute_majority")));
240 
241  /* pack d */
242  packed_d.allocate(pb, FMT(this->annotation_prefix, " packed_d"));
243  pack_d.reset(new packing_gadget<FieldT>(
244  pb, d, packed_d, FMT(this->annotation_prefix, " pack_d")));
245 
246  /* pack h */
247  packed_h.allocate(pb, FMT(this->annotation_prefix, " packed_h"));
248  pack_h.reset(new packing_gadget<FieldT>(
249  pb, h, packed_h, FMT(this->annotation_prefix, " pack_h")));
250 
251  /* compute the actual results for the round */
252  unreduced_new_a.allocate(
253  pb, FMT(this->annotation_prefix, " unreduced_new_a"));
254  unreduced_new_e.allocate(
255  pb, FMT(this->annotation_prefix, " unreduced_new_e"));
256 
257  packed_new_a.allocate(pb, FMT(this->annotation_prefix, " packed_new_a"));
258  packed_new_e.allocate(pb, FMT(this->annotation_prefix, " packed_new_e"));
259 
260  mod_reduce_new_a.reset(new lastbits_gadget<FieldT>(
261  pb,
262  unreduced_new_a,
263  32 + 3,
264  packed_new_a,
265  new_a,
266  FMT(this->annotation_prefix, " mod_reduce_new_a")));
267  mod_reduce_new_e.reset(new lastbits_gadget<FieldT>(
268  pb,
269  unreduced_new_e,
270  32 + 3,
271  packed_new_e,
272  new_e,
273  FMT(this->annotation_prefix, " mod_reduce_new_e")));
274 }
275 
276 template<typename FieldT>
277 void sha256_round_function_gadget<FieldT>::generate_r1cs_constraints()
278 {
279  compute_sigma0->generate_r1cs_constraints();
280  compute_sigma1->generate_r1cs_constraints();
281 
282  compute_choice->generate_r1cs_constraints();
283  compute_majority->generate_r1cs_constraints();
284 
285  pack_d->generate_r1cs_constraints(false);
286  pack_h->generate_r1cs_constraints(false);
287 
288  this->pb.add_r1cs_constraint(
289  r1cs_constraint<FieldT>(
290  1,
291  packed_h + sigma1 + choice + K + W + sigma0 + majority,
292  unreduced_new_a),
293  FMT(this->annotation_prefix, " unreduced_new_a"));
294 
295  this->pb.add_r1cs_constraint(
296  r1cs_constraint<FieldT>(
297  1, packed_d + packed_h + sigma1 + choice + K + W, unreduced_new_e),
298  FMT(this->annotation_prefix, " unreduced_new_e"));
299 
300  mod_reduce_new_a->generate_r1cs_constraints();
301  mod_reduce_new_e->generate_r1cs_constraints();
302 }
303 
304 template<typename FieldT>
305 void sha256_round_function_gadget<FieldT>::generate_r1cs_witness()
306 {
307  compute_sigma0->generate_r1cs_witness();
308  compute_sigma1->generate_r1cs_witness();
309 
310  compute_choice->generate_r1cs_witness();
311  compute_majority->generate_r1cs_witness();
312 
313  pack_d->generate_r1cs_witness_from_bits();
314  pack_h->generate_r1cs_witness_from_bits();
315 
316  this->pb.val(unreduced_new_a) =
317  this->pb.val(packed_h) + this->pb.val(sigma1) + this->pb.val(choice) +
318  FieldT(K) + this->pb.val(W) + this->pb.val(sigma0) +
319  this->pb.val(majority);
320  this->pb.val(unreduced_new_e) =
321  this->pb.val(packed_d) + this->pb.val(packed_h) + this->pb.val(sigma1) +
322  this->pb.val(choice) + FieldT(K) + this->pb.val(W);
323 
324  mod_reduce_new_a->generate_r1cs_witness();
325  mod_reduce_new_e->generate_r1cs_witness();
326 }
327 
328 } // namespace libsnark
329 
330 #endif // SHA256_COMPONENTS_TCC_
Generated on Wed Jan 25 2023 11:05:58 for Clearmatics Libsnark by   doxygen 1.8.17