Clearmatics Libsnark  0.1
C++ library for zkSNARK proofs
memory_masking_gadget.tcc
Go to the documentation of this file.
1 /** @file
2  *****************************************************************************
3 
4  Implementation of interfaces for the TinyRAM memory masking gadget.
5 
6  See memory_masking_gadget.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 MEMORY_MASKING_GADGET_TCC_
15 #define MEMORY_MASKING_GADGET_TCC_
16 
17 namespace libsnark
18 {
19 
20 template<typename FieldT>
21 memory_masking_gadget<FieldT>::memory_masking_gadget(
22  tinyram_protoboard<FieldT> &pb,
23  const doubleword_variable_gadget<FieldT> &dw_contents_prev,
24  const dual_variable_gadget<FieldT> &subaddress,
25  const pb_linear_combination<FieldT> &subcontents,
26  const pb_linear_combination<FieldT> &access_is_word,
27  const pb_linear_combination<FieldT> &access_is_byte,
28  const doubleword_variable_gadget<FieldT> &dw_contents_next,
29  const std::string &annotation_prefix)
30  : tinyram_standard_gadget<FieldT>(pb, annotation_prefix)
31  , dw_contents_prev(dw_contents_prev)
32  , subaddress(subaddress)
33  , subcontents(subcontents)
34  , access_is_word(access_is_word)
35  , access_is_byte(access_is_byte)
36  , dw_contents_next(dw_contents_next)
37 {
38  /*
39  Indicator variables for access being to word_0, word_1, and
40  byte_0, byte_1, ...
41 
42  We use little-endian indexing here (least significant
43  bit/byte/word has the smallest address).
44  */
45  is_word0.allocate(pb, FMT(this->annotation_prefix, " is_word0"));
46  is_word1.allocate(pb, FMT(this->annotation_prefix, " is_word1"));
47  is_subaddress.allocate(
48  pb,
49  2 * pb.ap.bytes_in_word(),
50  FMT(this->annotation_prefix, " is_sub_address"));
51  is_byte.allocate(
52  pb,
53  2 * pb.ap.bytes_in_word(),
54  FMT(this->annotation_prefix, " is_byte"));
55 
56  /*
57  Get value of the dw_contents_prev for which the specified entity
58  is masked out to be zero. E.g. the value of masked_out_bytes[3]
59  will be the same as the value of dw_contents_prev, when 3rd
60  (0-indexed) byte is set to all zeros.
61  */
62  masked_out_word0.assign(
63  pb,
64  (FieldT(2) ^ pb.ap.w) *
65  pb_packing_sum<FieldT>(pb_variable_array<FieldT>(
66  dw_contents_prev.bits.begin() + pb.ap.w,
67  dw_contents_prev.bits.begin() + 2 * pb.ap.w)));
68  masked_out_word1.assign(
69  pb,
70  pb_packing_sum<FieldT>(pb_variable_array<FieldT>(
71  dw_contents_prev.bits.begin(),
72  dw_contents_prev.bits.begin() + pb.ap.w)));
73  masked_out_bytes.resize(2 * pb.ap.bytes_in_word());
74 
75  for (size_t i = 0; i < 2 * pb.ap.bytes_in_word(); ++i) {
76  /* just subtract out the byte to be masked */
77  masked_out_bytes[i].assign(
78  pb,
79  (dw_contents_prev.packed -
80  (FieldT(2) ^ (8 * i)) *
81  pb_packing_sum<FieldT>(pb_variable_array<FieldT>(
82  dw_contents_prev.bits.begin() + 8 * i,
83  dw_contents_prev.bits.begin() + 8 * (i + 1)))));
84  }
85 
86  /*
87  Define masked_out_dw_contents_prev to be the correct masked out
88  contents for the current access type.
89  */
90 
91  pb_linear_combination_array<FieldT> masked_out_indicators;
92  masked_out_indicators.emplace_back(is_word0);
93  masked_out_indicators.emplace_back(is_word1);
94  masked_out_indicators.insert(
95  masked_out_indicators.end(), is_byte.begin(), is_byte.end());
96 
97  pb_linear_combination_array<FieldT> masked_out_results;
98  masked_out_results.emplace_back(masked_out_word0);
99  masked_out_results.emplace_back(masked_out_word1);
100  masked_out_results.insert(
101  masked_out_results.end(),
102  masked_out_bytes.begin(),
103  masked_out_bytes.end());
104 
105  masked_out_dw_contents_prev.allocate(
106  pb, FMT(this->annotation_prefix, " masked_out_dw_contents_prev"));
107  get_masked_out_dw_contents_prev.reset(new inner_product_gadget<FieldT>(
108  pb,
109  masked_out_indicators,
110  masked_out_results,
111  masked_out_dw_contents_prev,
112  FMT(this->annotation_prefix, " get_masked_out_dw_contents_prev")));
113 
114  /*
115  Define shift so that masked_out_dw_contents_prev + shift * subcontents =
116  dw_contents_next
117  */
118  linear_combination<FieldT> shift_lc =
119  is_word0 * 1 + is_word1 * (FieldT(2) ^ this->pb.ap.w);
120  for (size_t i = 0; i < 2 * this->pb.ap.bytes_in_word(); ++i) {
121  shift_lc = shift_lc + is_byte[i] * (FieldT(2) ^ (8 * i));
122  }
123  shift.assign(pb, shift_lc);
124 }
125 
126 template<typename FieldT>
127 void memory_masking_gadget<FieldT>::generate_r1cs_constraints()
128 {
129  /* get indicator variables for is_subaddress[i] by adding constraints
130  is_subaddress[i] * (subaddress - i) = 0 and \sum_i is_subaddress[i] = 1
131  */
132  for (size_t i = 0; i < 2 * this->pb.ap.bytes_in_word(); ++i) {
133  this->pb.add_r1cs_constraint(
134  r1cs_constraint<FieldT>(is_subaddress[i], subaddress.packed - i, 0),
135  FMT(this->annotation_prefix, " is_subaddress_%zu", i));
136  }
137  this->pb.add_r1cs_constraint(
138  r1cs_constraint<FieldT>(1, pb_sum<FieldT>(is_subaddress), 1),
139  FMT(this->annotation_prefix, " is_subaddress"));
140 
141  /* get indicator variables is_byte_X */
142  for (size_t i = 0; i < 2 * this->pb.ap.bytes_in_word(); ++i) {
143  this->pb.add_r1cs_constraint(
144  r1cs_constraint<FieldT>(
145  access_is_byte, is_subaddress[i], is_byte[i]),
146  FMT(this->annotation_prefix, " is_byte_%zu", i));
147  }
148 
149  /* get indicator variables is_word_0/is_word_1 */
150  this->pb.add_r1cs_constraint(
151  r1cs_constraint<FieldT>(
152  access_is_word,
153  1 - subaddress.bits[this->pb.ap.subaddr_len() - 1],
154  is_word0),
155  FMT(this->annotation_prefix, " is_word_0"));
156  this->pb.add_r1cs_constraint(
157  r1cs_constraint<FieldT>(
158  access_is_word,
159  subaddress.bits[this->pb.ap.subaddr_len() - 1],
160  is_word1),
161  FMT(this->annotation_prefix, " is_word_1"));
162 
163  /* compute masked_out_dw_contents_prev */
164  get_masked_out_dw_contents_prev->generate_r1cs_constraints();
165 
166  /*
167  masked_out_dw_contents_prev + shift * subcontents = dw_contents_next
168  */
169  this->pb.add_r1cs_constraint(
170  r1cs_constraint<FieldT>(
171  shift,
172  subcontents,
173  dw_contents_next.packed - masked_out_dw_contents_prev),
174  FMT(this->annotation_prefix, " mask_difference"));
175 }
176 
177 template<typename FieldT>
178 void memory_masking_gadget<FieldT>::generate_r1cs_witness()
179 {
180  /* get indicator variables is_subaddress */
181  for (size_t i = 0; i < 2 * this->pb.ap.bytes_in_word(); ++i) {
182  this->pb.val(is_subaddress[i]) =
183  (this->pb.val(subaddress.packed) == FieldT(i)) ? FieldT::one()
184  : FieldT::zero();
185  }
186 
187  /* get indicator variables is_byte_X */
188  for (size_t i = 0; i < 2 * this->pb.ap.bytes_in_word(); ++i) {
189  this->pb.val(is_byte[i]) =
190  this->pb.val(is_subaddress[i]) * this->pb.lc_val(access_is_byte);
191  }
192 
193  /* get indicator variables is_word_0/is_word_1 */
194  this->pb.val(is_word0) =
195  (FieldT::one() -
196  this->pb.val(subaddress.bits[this->pb.ap.subaddr_len() - 1])) *
197  this->pb.lc_val(access_is_word);
198  this->pb.val(is_word1) =
199  this->pb.val(subaddress.bits[this->pb.ap.subaddr_len() - 1]) *
200  this->pb.lc_val(access_is_word);
201 
202  /* calculate shift and masked out words/bytes */
203  shift.evaluate(this->pb);
204  masked_out_word0.evaluate(this->pb);
205  masked_out_word1.evaluate(this->pb);
206  masked_out_bytes.evaluate(this->pb);
207 
208  /* get masked_out dw/word0/word1/bytes */
209  get_masked_out_dw_contents_prev->generate_r1cs_witness();
210 
211  /* compute dw_contents_next */
212  this->pb.val(dw_contents_next.packed) =
213  this->pb.val(masked_out_dw_contents_prev) +
214  this->pb.lc_val(shift) * this->pb.lc_val(subcontents);
215  dw_contents_next.generate_r1cs_witness_from_packed();
216 }
217 
218 } // namespace libsnark
219 
220 #endif // MEMORY_MASKING_GADGET_TCC_
Generated on Wed Jan 25 2023 11:05:57 for Clearmatics Libsnark by   doxygen 1.8.17