Zeth - Zerocash on Ethereum  0.8
Reference implementation of the Zeth protocol by Clearmatics
mimc_permutation.tcc
Go to the documentation of this file.
1 // DISCLAIMER:
2 // Content taken and adapted from:
3 // https://github.com/HarryR/ethsnarks/blob/master/src/gadgets/mimc.hpp
4 
5 #ifndef __ZETH_CIRCUITS_MIMC_PERMUTATION_TCC__
6 #define __ZETH_CIRCUITS_MIMC_PERMUTATION_TCC__
7 
8 #include "libzeth/circuits/mimc/mimc_permutation.hpp"
9 
10 namespace libzeth
11 {
12 
13 template<typename FieldT, size_t Exponent, size_t NumRounds>
14 std::vector<FieldT>
15  MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::round_constants;
16 
17 template<typename FieldT, size_t Exponent, size_t NumRounds>
18 bool MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::
19  round_constants_initialized = false;
20 
21 template<typename FieldT, size_t Exponent, size_t NumRounds>
22 MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::MiMC_permutation_gadget(
23  libsnark::protoboard<FieldT> &pb,
24  const libsnark::pb_linear_combination<FieldT> &msg,
25  const libsnark::pb_linear_combination<FieldT> &key,
26  const libsnark::pb_variable<FieldT> &result,
27  const libsnark::pb_linear_combination<FieldT> &add_to_result,
28  const bool add_to_result_is_valid,
29  const std::string &annotation_prefix)
30  : libsnark::gadget<FieldT>(pb, annotation_prefix)
31 {
32  // Ensure round constants are initialized.
33  setup_sha3_constants();
34 
35  // Initialize the round gadgets
36  round_gadgets.reserve(NumRounds);
37 
38  // First round uses round_msg as an input.
39  round_results[0].allocate(
40  this->pb, FMT(this->annotation_prefix, " round_result[0]"));
41  round_gadgets.emplace_back(
42  this->pb,
43  msg,
44  key,
45  round_constants[0],
46  round_results[0],
47  FMT(this->annotation_prefix, " round[0]"));
48 
49  // Intermediate rounds use the output of the previous round and output to
50  // an intermediate variable (allocated here)
51  for (size_t i = 1; i < NumRounds - 1; i++) {
52  // Allocate intermediate round result.
53  round_results[i].allocate(
54  this->pb, FMT(this->annotation_prefix, " round_result[%zu]", i));
55 
56  // Initialize the current round gadget into the vector of round gadgets
57  // vector, picking the correct round constant.
58  round_gadgets.emplace_back(
59  this->pb,
60  round_results[i - 1],
61  key,
62  round_constants[i],
63  round_results[i],
64  FMT(this->annotation_prefix, " round[%zu]", i));
65  }
66 
67  // For last round, output to the result variable and add `key` to the
68  // result, along with any add_to_result.
69  round_results[NumRounds - 1] = result;
70 
71  if (add_to_result_is_valid) {
72  libsnark::pb_linear_combination<FieldT> key_plus_add_to_result;
73  key_plus_add_to_result.assign(this->pb, key + add_to_result);
74  round_gadgets.emplace_back(
75  this->pb,
76  round_results[NumRounds - 2],
77  key,
78  round_constants[NumRounds - 1],
79  round_results[NumRounds - 1],
80  key_plus_add_to_result,
81  FMT(this->annotation_prefix, " round[%zu]", NumRounds - 1));
82  } else {
83  round_gadgets.emplace_back(
84  this->pb,
85  round_results[NumRounds - 2],
86  key,
87  round_constants[NumRounds - 1],
88  round_results[NumRounds - 1],
89  key,
90  FMT(this->annotation_prefix, " round[%zu]", NumRounds - 1));
91  }
92 }
93 
94 template<typename FieldT, size_t Exponent, size_t NumRounds>
95 MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::MiMC_permutation_gadget(
96  libsnark::protoboard<FieldT> &pb,
97  const libsnark::pb_linear_combination<FieldT> &msg,
98  const libsnark::pb_linear_combination<FieldT> &key,
99  const libsnark::pb_variable<FieldT> &result,
100  const std::string &annotation_prefix)
101  : MiMC_permutation_gadget(
102  pb,
103  msg,
104  key,
105  result,
106  libsnark::pb_linear_combination<FieldT>(),
107  false,
108  annotation_prefix)
109 {
110 }
111 
112 template<typename FieldT, size_t Exponent, size_t NumRounds>
113 MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::MiMC_permutation_gadget(
114  libsnark::protoboard<FieldT> &pb,
115  const libsnark::pb_linear_combination<FieldT> &msg,
116  const libsnark::pb_linear_combination<FieldT> &key,
117  const libsnark::pb_variable<FieldT> &result,
118  const libsnark::pb_linear_combination<FieldT> &add_to_result,
119  const std::string &annotation_prefix)
120  : MiMC_permutation_gadget(
121  pb, msg, key, result, add_to_result, true, annotation_prefix)
122 {
123 }
124 
125 template<typename FieldT, size_t Exponent, size_t NumRounds>
126 void MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::
127  generate_r1cs_constraints()
128 {
129  // For each round, generates the constraints for the corresponding round
130  // gadget.
131  for (auto &gadget : round_gadgets) {
132  gadget.generate_r1cs_constraints();
133  }
134 }
135 
136 template<typename FieldT, size_t Exponent, size_t NumRounds>
137 void MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::
138  generate_r1cs_witness() const
139 {
140  // For each round, generates the witness for the corresponding round
141  // gadget.
142  for (auto &gadget : round_gadgets) {
143  gadget.generate_r1cs_witness();
144  }
145 }
146 
147 // The following constants correspond to the iterative computation of sha3_256
148 // hash function over the initial seed "clearmatics_mt_seed". See:
149 // client/zethCodeConstantsGeneration.py for more details
150 template<typename FieldT, size_t Exponent, size_t NumRounds>
151 void MiMC_permutation_gadget<FieldT, Exponent, NumRounds>::
152  setup_sha3_constants()
153 {
154  if (round_constants_initialized) {
155  return;
156  }
157 
158  // Constants are generated as follows (in client python env):
159  // (env) $ python
160  // >>> import zeth.core.mimc as mimc
161  // >>> import zeth.core.constants as constants
162  // >>> mimc.generate_round_constants(constants.MIMC_MT_SEED, 93)
163 
164  // The constant is set to "0" in the first round of MiMC permutation (see:
165  // https://eprint.iacr.org/2016/492.pdf)
166 
167  // For simplicity, always populate with enough constants for MaxRounds.
168  // clang-format off
169  round_constants = {
170  FieldT("0"),
171  FieldT("22159019873790129476324495190496603411493310235845550845393361088354059025587"),
172  FieldT("27761654615899466766976328798614662221520122127418767386594587425934055859027"),
173  FieldT("94824950344308939111646914673652476426466554475739520071212351703914847519222"),
174  FieldT("84875755167904490740680810908425347913240786521935721949482414218097022905238"),
175  FieldT("103827469404022738626089808362855974444473512881791722903435218437949312500276"),
176  FieldT("79151333313630310680682684119244096199179603958178503155035988149812024220238"),
177  FieldT("69032546029442066350494866745598303896748709048209836077355812616627437932521"),
178  FieldT("71828934229806034323678289655618358926823037947843672773514515549250200395747"),
179  FieldT("20380360065304068228640594346624360147706079921816528167847416754157399404427"),
180  FieldT("33389882590456326015242966586990383840423378222877476683761799984554709177407"),
181  FieldT("50122810070778420844700285367936543284029126632619100118638682958218725318756"),
182  FieldT("49246859699528342369154520789249265070136349803358469088610922925489948122588"),
183  FieldT("42301293999667742503298132605205313473294493780037112351216393454277775233701"),
184  FieldT("84114918321547685007627041787929288135785026882582963701427252073231899729239"),
185  FieldT("62442564517333183431281494169332072638102772915973556148439397377116238052032"),
186  FieldT("90371696767943970492795296318744142024828099537644566050263944542077360454000"),
187  FieldT("115430938798103259020685569971731347341632428718094375123887258419895353452385"),
188  FieldT("113486567655643015051612432235944767094037016028918659325405959747202187788641"),
189  FieldT("42521224046978113548086179860571260859679910353297292895277062016640527060158"),
190  FieldT("59337418021535832349738836949730504849571827921681387254433920345654363097721"),
191  FieldT("11312792726948192147047500338922194498305047686482578113645836215734847502787"),
192  FieldT("5531104903388534443968883334496754098135862809700301013033503341381689618972"),
193  FieldT("67267967506593457603372921446668397713655666818276613345969561709158934132467"),
194  FieldT("14150601882795046585170507190892504128795190437985555320824531798948976631295"),
195  FieldT("85062650450907709431728516509140931676564801299509460081586249478375415684322"),
196  FieldT("3190636703526705373452173482292964566521687248139217048214149162895182633187"),
197  FieldT("94697707246459731032848302079578714910941380385884087153796554334872238022178"),
198  FieldT("105237079024348272465679804525604310926083869213267017956044692586513087552889"),
199  FieldT("107666297462370279081061498341391155289817553443536637437225808625028106164694"),
200  FieldT("50658185643016152702409617752847261961811370146977869351531768522548888496960"),
201  FieldT("40194505239242861003888376856216043830225436269588275639840138989648733836164"),
202  FieldT("18446023938001439123322925291203176968088321100216399802351969471087090508798"),
203  FieldT("56716868411561319312404565555682857409226456576794830238428782927207680423406"),
204  FieldT("99446603622401702299467002115709680008186357666919726252089514718382895122907"),
205  FieldT("14440268383603206763216449941954085575335212955165966039078057319953582173633"),
206  FieldT("19800531992512132732080265836821627955799468140051158794892004229352040429024"),
207  FieldT("105297016338495372394147178784104774655759157445835217996114870903812070518445"),
208  FieldT("25603899274511343521079846952994517772529013612481201245155078199291999403355"),
209  FieldT("42343992762533961606462320250264898254257373842674711124109812370529823212221"),
210  FieldT("10746157796797737664081586165620034657529089112211072426663365617141344936203"),
211  FieldT("83415911130754382252267592583976834889211427666721691843694426391396310581540"),
212  FieldT("90866605176883156213219983011392724070678633758652939051248987072469444200627"),
213  FieldT("37024565646714391930474489137778856553925761915366252060067939966442059957164"),
214  FieldT("7989471243134634308962365261048299254340659799910534445820512869869542788064"),
215  FieldT("15648939481289140348738679797715724220399212972574021006219862339465296839884"),
216  FieldT("100133438935846292803417679717817950677446943844926655798697284495340753961844"),
217  FieldT("84618212755822467879717121296483255659772850854170590780922087915497421596465"),
218  FieldT("66815981435852782130184794409662156021404245655267602728283138458689925010111"),
219  FieldT("100011403138602452635630699813302791324969902443516593676764382923531277739340"),
220  FieldT("57430361797750645341842394309545159343198597441951985629580530284393758413106"),
221  FieldT("70240009849732555205629614425470918637568887938810907663457802670777054165279"),
222  FieldT("115341201140672997375646566164431266507025151688875346248495663683620086806942"),
223  FieldT("11188962021222070760150833399355814187143871338754315850627637681691407594017"),
224  FieldT("22685520879254273934490401340849316430229408194604166253482138215686716109430"),
225  FieldT("51189210546148312327463530170430162293845070064001770900624850430825589457055"),
226  FieldT("14807565813027010873011142172745696288480075052292277459306275231121767039664"),
227  FieldT("95539138374056424883213912295679274059417180869462186511207318536449091576661"),
228  FieldT("113489397464329757187555603731541774715600099685729291423921796997078292946609"),
229  FieldT("104312240868162447193722372229442001535106018532365202206691174960555358414880"),
230  FieldT("8267151326618998101166373872748168146937148303027773815001564349496401227343"),
231  FieldT("76298755107890528830128895628139521831584444593650120338808262678169950673284"),
232  FieldT("73002305935054160156217464153178860593131914821282451210510325210791458847694"),
233  FieldT("74544443080560119509560262720937836494902079641131221139823065933367514898276"),
234  FieldT("36856043990250139109110674451326757800006928098085552406998173198427373834846"),
235  FieldT("89876265522016337550524744707009312276376790319197860491657618155961055194949"),
236  FieldT("110827903006446644954303964609043521818500007209339765337677716791359271709709"),
237  FieldT("19507166101303357762640682204614541813131172968402646378144792525256753001746"),
238  FieldT("107253144238416209039771223682727408821599541893659793703045486397265233272366"),
239  FieldT("50595349797145823467207046063156205987118773849740473190540000392074846997926"),
240  FieldT("44703482889665897122601827877356260454752336134846793080442136212838463818460"),
241  FieldT("72587689163044446617379334085046687704026377073069181869522598220420039333904"),
242  FieldT("102651401786920090371975453907921346781687924794638352783098945209363379010084"),
243  FieldT("93452870373806728605513560063145330258676656934938716540885043830342716774537"),
244  FieldT("78296669596559313198894751403351590225284664485458045241864014863714864424243"),
245  FieldT("115089219682233450926699488628267277641700041858332325616476033644461392438459"),
246  FieldT("12503229023709380637667243769419362848195673442247523096260626221166887267863"),
247  FieldT("4710254915107472945023322521703570589554948344762175784852248799008742965033"),
248  FieldT("7718237385336937042064321465151951780913850666971695410931421653062451982185"),
249  FieldT("115218487714637830492048339157964615618803212766527542809597433013530253995292"),
250  FieldT("30146276054995781136885926012526705051587400199196161599789168368938819073525"),
251  FieldT("81645575619063610562025782726266715757461113967190574155696199274188206173145"),
252  FieldT("103065286526250765895346723898189993161715212663393551904337911885906019058491"),
253  FieldT("19401253163389218637767300383887292725233192135251696535631823232537040754970"),
254  FieldT("39843332085422732827481601668576197174769872102167705377474553046529879993254"),
255  FieldT("27288628349107331632228897768386713717171618488175838305048363657709955104492"),
256  FieldT("63512042813079522866974560192099016266996589861590638571563519363305976473166"),
257  FieldT("88099896769123586138541398153669061847681467623298355942484821247745931328016"),
258  FieldT("69497565113721491657291572438744729276644895517335084478398926389231201598482"),
259  FieldT("17118586436782638926114048491697362406660860405685472757612739816905521144705"),
260  FieldT("50507769484714413215987736701379019852081133212073163694059431350432441698257"),
261  FieldT("58260458108608505301755075857897657610125730489308125711681594839108744994599"),
262  FieldT("74417125471829501682706919197813397955210189244710764612359440617050537569714")
263  };
264  // clang-format on
265 
266  assert(round_constants.size() == MaxRounds);
267  round_constants_initialized = true;
268 }
269 
270 } // namespace libzeth
271 
272 #endif // __ZETH_CIRCUITS_MIMC_PERMUTATION_TCC__
Generated on Mon Nov 28 2022 10:29:03 for Zeth - Zerocash on Ethereum by   doxygen 1.8.17