ecgadget.hpp 41 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131
  1. #include "libsnark_headers.hpp"
  2. using namespace libsnark;
  3. // There are two types of values:
  4. // _constants_ are values known at circuit generation time; they
  5. // are global constants known to everyone
  6. // _variables_ are values that change in each use of the circuit;
  7. // they have two subtypes:
  8. //
  9. // _public variables_ are values known to both the prover
  10. // and verifier but change in each use of the circuit
  11. // _private variables_ are values known only to the prover
  12. // and change in each use of the circuit
  13. // Double a constant EC point (inx,iny) to yield (outx,outy). The input
  14. // point must not be the point at infinity.
  15. template<typename FieldT>
  16. static void ec_double_point(FieldT &outx, FieldT &outy,
  17. const FieldT &inx, const FieldT &iny)
  18. {
  19. FieldT xsq = inx.squared();
  20. FieldT lambda = (xsq * 3 - 3) * (iny * 2).inverse();
  21. outx = lambda.squared() - inx * 2;
  22. outy = lambda * (inx - outx) - iny;
  23. }
  24. // Add constant EC points (inx, iny) and (addx, addy) to yield (outx, outy).
  25. // inx and addx must not be equal.
  26. template<typename FieldT>
  27. static void ec_add_points(FieldT &outx, FieldT &outy,
  28. const FieldT &inx, const FieldT &iny,
  29. const FieldT &addx, const FieldT &addy)
  30. {
  31. FieldT lambda = (addy - iny) * (addx - inx).inverse();
  32. outx = lambda.squared() - (addx + inx);
  33. outy = lambda * (inx - outx) - iny;
  34. }
  35. // Double the variable EC point (inx,iny) to yield (outx,outy). The
  36. // input point must not be the point at infinity.
  37. template<typename FieldT>
  38. class ec_double_gadget : public gadget<FieldT> {
  39. private:
  40. pb_variable<FieldT> lambda, inxsq;
  41. public:
  42. const pb_variable<FieldT> outx, outy, inx, iny;
  43. ec_double_gadget(protoboard<FieldT> &pb,
  44. const pb_variable<FieldT> &outx,
  45. const pb_variable<FieldT> &outy,
  46. const pb_linear_combination<FieldT> &inx,
  47. const pb_linear_combination<FieldT> &iny) :
  48. gadget<FieldT>(pb, "ec_double_gadget"), outx(outx), outy(outy),
  49. inx(inx), iny(iny)
  50. {
  51. // Allocate variables to protoboard
  52. // The strings (like "x") are only for debugging purposes
  53. lambda.allocate(this->pb, "lambda");
  54. inxsq.allocate(this->pb, "inxsq");
  55. }
  56. void generate_r1cs_constraints()
  57. {
  58. // inxsq = inx * inx
  59. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(inx, inx, inxsq));
  60. // 2 * iny * lambda = 3 * inxsq - 3 (a = -3 on our curve)
  61. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(2 * iny, lambda, 3 * inxsq - 3));
  62. // outx = lambda^2 - 2 * inx
  63. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, lambda, outx + 2 * inx));
  64. // outy = lambda * (inx - outx) - iny
  65. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, inx - outx, outy + iny));
  66. }
  67. void generate_r1cs_witness()
  68. {
  69. this->pb.val(inxsq) = this->pb.lc_val(inx) * this->pb.lc_val(inx);
  70. this->pb.val(lambda) = (this->pb.val(inxsq) * 3 - 3) * (this->pb.lc_val(iny) * 2).inverse();
  71. this->pb.val(outx) = this->pb.val(lambda).squared() - this->pb.lc_val(inx) * 2;
  72. this->pb.val(outy) = this->pb.val(lambda) * (this->pb.lc_val(inx) - this->pb.val(outx)) - this->pb.lc_val(iny);
  73. }
  74. };
  75. // Add the variable EC point (addx,addy) to the variable EC point
  76. // (inx,iny) to yield (outx,outy). The input point must not be the
  77. // point at infinity.
  78. template<typename FieldT>
  79. class ec_add_gadget : public gadget<FieldT> {
  80. private:
  81. pb_variable<FieldT> lambda;
  82. public:
  83. const pb_variable<FieldT> outx, outy;
  84. const pb_linear_combination<FieldT> inx, iny, addx, addy;
  85. ec_add_gadget(protoboard<FieldT> &pb,
  86. const pb_variable<FieldT> &outx,
  87. const pb_variable<FieldT> &outy,
  88. const pb_linear_combination<FieldT> &inx,
  89. const pb_linear_combination<FieldT> &iny,
  90. const pb_linear_combination<FieldT> &addx,
  91. const pb_linear_combination<FieldT> &addy) :
  92. gadget<FieldT>(pb, "ec_add_gadget"),
  93. outx(outx), outy(outy), inx(inx), iny(iny), addx(addx), addy(addy)
  94. {
  95. // Allocate variables to protoboard
  96. // The strings (like "x") are only for debugging purposes
  97. lambda.allocate(this->pb, "lambda");
  98. }
  99. void generate_r1cs_constraints()
  100. {
  101. // (addx - inx) * lambda = addy - iny
  102. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(addx - inx, lambda, addy - iny));
  103. // outx = lambda^2 - (addx + inx)
  104. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, lambda, outx + addx + inx));
  105. // outy = lambda * (inx - outx) - iny
  106. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, inx - outx, outy + iny));
  107. }
  108. void generate_r1cs_witness()
  109. {
  110. this->pb.val(lambda) = (this->pb.lc_val(addy) - this->pb.lc_val(iny)) * (this->pb.lc_val(addx) - this->pb.lc_val(inx)).inverse();
  111. this->pb.val(outx) = this->pb.val(lambda).squared() - (this->pb.lc_val(addx) + this->pb.lc_val(inx));
  112. this->pb.val(outy) = this->pb.val(lambda) * (this->pb.lc_val(inx) - this->pb.val(outx)) - this->pb.lc_val(iny);
  113. }
  114. };
  115. // Add the variable EC point P to the constant EC point (inx,iny) to
  116. // yield (outx,outy). The input point must not be the point at
  117. // infinity.
  118. template<typename FieldT>
  119. class ec_constant_add_gadget : public gadget<FieldT> {
  120. private:
  121. pb_variable<FieldT> lambda;
  122. public:
  123. const pb_variable<FieldT> outx, outy;
  124. const pb_linear_combination<FieldT> inx, iny;
  125. const FieldT Px, Py;
  126. ec_constant_add_gadget(protoboard<FieldT> &pb,
  127. const pb_variable<FieldT> &outx,
  128. const pb_variable<FieldT> &outy,
  129. const pb_linear_combination<FieldT> &inx,
  130. const pb_linear_combination<FieldT> &iny,
  131. const FieldT &Px, const FieldT &Py) :
  132. gadget<FieldT>(pb, "ec_constant_add_gadget"),
  133. outx(outx), outy(outy), inx(inx), iny(iny), Px(Px), Py(Py)
  134. {
  135. // Allocate variables to protoboard
  136. // The strings (like "x") are only for debugging purposes
  137. lambda.allocate(this->pb, "lambda");
  138. }
  139. void generate_r1cs_constraints()
  140. {
  141. // (Px - inx) * lambda = Py - iny
  142. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(Px - inx, lambda, Py - iny));
  143. // outx = lambda^2 - (Px + inx)
  144. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, lambda, outx + Px + inx));
  145. // outy = lambda * (inx - outx) - iny
  146. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(lambda, inx - outx, outy + iny));
  147. }
  148. void generate_r1cs_witness()
  149. {
  150. this->pb.val(lambda) = (Py - this->pb.lc_val(iny)) * (Px - this->pb.lc_val(inx)).inverse();
  151. this->pb.val(outx) = this->pb.val(lambda).squared() - (Px + this->pb.lc_val(inx));
  152. this->pb.val(outy) = this->pb.val(lambda) * (this->pb.lc_val(inx) - this->pb.val(outx)) - this->pb.lc_val(iny);
  153. }
  154. };
  155. // Add the constant EC point P0 or the constant EC point P1 to the
  156. // variable EC point (inx,iny) to yield (outx,outy). The input point
  157. // must not be the point at infinity. The input bit choice controls
  158. // which addition is done.
  159. template<typename FieldT>
  160. class ec_2_constant_add_gadget : public gadget<FieldT> {
  161. private:
  162. pb_linear_combination<FieldT> addx, addy;
  163. std::vector<ec_add_gadget<FieldT> > adder;
  164. public:
  165. const pb_variable<FieldT> outx, outy;
  166. const pb_linear_combination<FieldT> inx, iny;
  167. const pb_variable<FieldT> choice;
  168. const FieldT P0x, P0y, P1x, P1y;
  169. ec_2_constant_add_gadget(protoboard<FieldT> &pb,
  170. const pb_variable<FieldT> &outx,
  171. const pb_variable<FieldT> &outy,
  172. const pb_linear_combination<FieldT> &inx,
  173. const pb_linear_combination<FieldT> &iny,
  174. const pb_variable<FieldT> &choice,
  175. const FieldT &P0x, const FieldT &P0y,
  176. const FieldT &P1x, const FieldT &P1y) :
  177. gadget<FieldT>(pb, "ec_2_constant_add_gadget"),
  178. outx(outx), outy(outy), inx(inx), iny(iny), choice(choice),
  179. P0x(P0x), P0y(P0y), P1x(P1x), P1y(P1y)
  180. {
  181. // Allocate variables to protoboard
  182. addx.assign(pb, choice * (P1x-P0x) + P0x);
  183. addy.assign(pb, choice * (P1y-P0y) + P0y);
  184. adder.emplace_back(this->pb, outx, outy, inx, iny, addx, addy);
  185. }
  186. void generate_r1cs_constraints()
  187. {
  188. adder[0].generate_r1cs_constraints();
  189. }
  190. void generate_r1cs_witness()
  191. {
  192. addx.evaluate(this->pb);
  193. addy.evaluate(this->pb);
  194. adder[0].generate_r1cs_witness();
  195. }
  196. };
  197. // Add the constant EC point P0 or the variable EC point P1 to the
  198. // variable EC point (inx,iny) to yield (outx,outy). The input point
  199. // must not be the point at infinity. The input bit choice controls
  200. // which addition is done.
  201. template<typename FieldT>
  202. class ec_2_1constant_add_gadget : public gadget<FieldT> {
  203. private:
  204. pb_variable<FieldT> addx, addy;
  205. std::vector<ec_add_gadget<FieldT> > adder;
  206. public:
  207. const pb_variable<FieldT> outx, outy;
  208. const pb_linear_combination<FieldT> inx, iny;
  209. const pb_variable<FieldT> choice;
  210. const FieldT P0x, P0y;
  211. const pb_variable<FieldT> P1x, P1y;
  212. ec_2_1constant_add_gadget(protoboard<FieldT> &pb,
  213. const pb_variable<FieldT> &outx,
  214. const pb_variable<FieldT> &outy,
  215. const pb_linear_combination<FieldT> &inx,
  216. const pb_linear_combination<FieldT> &iny,
  217. const pb_variable<FieldT> &choice,
  218. const FieldT &P0x,
  219. const FieldT &P0y,
  220. const pb_variable<FieldT> &P1x,
  221. const pb_variable<FieldT> &P1y) :
  222. gadget<FieldT>(pb, "ec_2_1constant_add_gadget"),
  223. outx(outx), outy(outy), inx(inx), iny(iny), choice(choice),
  224. P0x(P0x), P0y(P0y), P1x(P1x), P1y(P1y)
  225. {
  226. // Allocate variables to protoboard
  227. addx.allocate(this->pb, "addx");
  228. addy.allocate(this->pb, "addy");
  229. adder.emplace_back(this->pb, outx, outy, inx, iny, addx, addy);
  230. }
  231. void generate_r1cs_constraints()
  232. {
  233. // Set (addx,addy) = choice ? (P0x, P0y) : (P1x, P1y)
  234. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(P1x - P0x, choice, addx - P0x));
  235. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(P1y - P0y, choice, addy - P0y));
  236. adder[0].generate_r1cs_constraints();
  237. }
  238. void generate_r1cs_witness()
  239. {
  240. bool choiceb = this->pb.val(choice) != FieldT(0);
  241. this->pb.val(addx) = choiceb ? this->pb.val(P1x) : P0x;
  242. this->pb.val(addy) = choiceb ? this->pb.val(P1y) : P0y;
  243. adder[0].generate_r1cs_witness();
  244. }
  245. };
  246. // Add the variable EC point P0 or the variable EC point P1 to the
  247. // variable EC point (inx,iny) to yield (outx,outy). The input point
  248. // must not be the point at infinity. The input bit choice controls
  249. // which addition is done.
  250. template<typename FieldT>
  251. class ec_2_add_gadget : public gadget<FieldT> {
  252. private:
  253. pb_variable<FieldT> addx, addy;
  254. std::vector<ec_add_gadget<FieldT> > adder;
  255. public:
  256. const pb_variable<FieldT> outx, outy;
  257. const pb_linear_combination<FieldT> inx, iny;
  258. const pb_variable<FieldT> choice;
  259. const pb_variable<FieldT> P0x, P0y, P1x, P1y;
  260. ec_2_add_gadget(protoboard<FieldT> &pb,
  261. const pb_variable<FieldT> &outx,
  262. const pb_variable<FieldT> &outy,
  263. const pb_linear_combination<FieldT> &inx,
  264. const pb_linear_combination<FieldT> &iny,
  265. const pb_variable<FieldT> &choice,
  266. const pb_variable<FieldT> &P0x,
  267. const pb_variable<FieldT> &P0y,
  268. const pb_variable<FieldT> &P1x,
  269. const pb_variable<FieldT> &P1y) :
  270. gadget<FieldT>(pb, "ec_2_add_gadget"),
  271. outx(outx), outy(outy), inx(inx), iny(iny), choice(choice),
  272. P0x(P0x), P0y(P0y), P1x(P1x), P1y(P1y)
  273. {
  274. // Allocate variables to protoboard
  275. addx.allocate(this->pb, "addx");
  276. addy.allocate(this->pb, "addy");
  277. adder.emplace_back(this->pb, outx, outy, inx, iny, addx, addy);
  278. }
  279. void generate_r1cs_constraints()
  280. {
  281. // Set (addx,addy) = choice ? (P0x, P0y) : (P1x, P1y)
  282. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(P1x - P0x, choice, addx - P0x));
  283. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(P1y - P0y, choice, addy - P0y));
  284. adder[0].generate_r1cs_constraints();
  285. }
  286. void generate_r1cs_witness()
  287. {
  288. bool choiceb = this->pb.val(choice) != FieldT(0);
  289. this->pb.val(addx) = choiceb ? this->pb.val(P1x) : this->pb.val(P0x);
  290. this->pb.val(addy) = choiceb ? this->pb.val(P1y) : this->pb.val(P0y);
  291. adder[0].generate_r1cs_witness();
  292. }
  293. };
  294. // Add one of the four constant EC points to the variable EC point
  295. // (inx,iny) to yield (outx,outy). The input point must not be the
  296. // point at infinity. The input bits choice0 and choice1 control which
  297. // addition is done (P{2*choice1+choice0} is added).
  298. template<typename FieldT>
  299. class ec_4_constant_add_gadget : public gadget<FieldT> {
  300. private:
  301. pb_variable<FieldT> both;
  302. pb_linear_combination<FieldT> addx, addy;
  303. std::vector<ec_add_gadget<FieldT> > adder;
  304. public:
  305. const pb_variable<FieldT> outx, outy;
  306. const pb_linear_combination<FieldT> inx, iny;
  307. const pb_variable<FieldT> choice0, choice1;
  308. const FieldT P0x, P0y, P1x, P1y, P2x, P2y, P3x, P3y;
  309. ec_4_constant_add_gadget(protoboard<FieldT> &pb,
  310. const pb_variable<FieldT> &outx,
  311. const pb_variable<FieldT> &outy,
  312. const pb_linear_combination<FieldT> &inx,
  313. const pb_linear_combination<FieldT> &iny,
  314. const pb_variable<FieldT> &choice0,
  315. const pb_variable<FieldT> &choice1,
  316. const FieldT &P0x, const FieldT &P0y,
  317. const FieldT &P1x, const FieldT &P1y,
  318. const FieldT &P2x, const FieldT &P2y,
  319. const FieldT &P3x, const FieldT &P3y) :
  320. gadget<FieldT>(pb, "ec_4_constant_add_gadget"),
  321. outx(outx), outy(outy), inx(inx), iny(iny),
  322. choice0(choice0), choice1(choice1),
  323. P0x(P0x), P0y(P0y), P1x(P1x), P1y(P1y),
  324. P2x(P2x), P2y(P2y), P3x(P3x), P3y(P3y)
  325. {
  326. // Allocate variables to protoboard
  327. both.allocate(this->pb, "both");
  328. addx.assign(this->pb, both * (P3x - P2x - P1x + P0x) + choice1 * (P2x - P0x) + choice0 * (P1x - P0x) + P0x);
  329. addy.assign(this->pb, both * (P3y - P2y - P1y + P0y) + choice1 * (P2y - P0y) + choice0 * (P1y - P0y) + P0y);
  330. adder.emplace_back(this->pb, outx, outy, inx, iny, addx, addy);
  331. }
  332. void generate_r1cs_constraints()
  333. {
  334. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(choice0, choice1, both));
  335. adder[0].generate_r1cs_constraints();
  336. }
  337. void generate_r1cs_witness()
  338. {
  339. bool c0 = this->pb.val(choice0) != FieldT(0);
  340. bool c1 = this->pb.val(choice1) != FieldT(0);
  341. this->pb.val(both) = c0 && c1;
  342. addx.evaluate(this->pb);
  343. addy.evaluate(this->pb);
  344. adder[0].generate_r1cs_witness();
  345. }
  346. };
  347. // Compute A + s*P as (outx, outy) for an accumulator A, a given
  348. // constant point P, and s given as a bit vector. The _caller_ is
  349. // responsible for proving that the elements of svec are bits. The
  350. // (constant) accumulator excess (AXS) will be updated; when all the
  351. // computations are complete, AXS should be subtracted from the
  352. // accumulator A.
  353. template<typename FieldT>
  354. class ec_constant_scalarmul_vec_accum_gadget : public gadget<FieldT> {
  355. private:
  356. FieldT Cx, Cy;
  357. pb_variable_array<FieldT> accumx, accumy;
  358. std::vector<ec_4_constant_add_gadget<FieldT> > fouradders;
  359. std::vector<ec_2_constant_add_gadget<FieldT> > twoadders;
  360. public:
  361. const pb_variable<FieldT> outx, outy;
  362. const pb_variable<FieldT> Ax, Ay;
  363. const pb_variable_array<FieldT> svec;
  364. const FieldT Px, Py;
  365. // Strategy: We compute (as compile-time constants) (powers of 2)
  366. // times P. Based on each bit of s, we add one of the constant points
  367. // C or (2^i * P) + C to the accumulator, and regardless of s, add C
  368. // to the excess.
  369. ec_constant_scalarmul_vec_accum_gadget(protoboard<FieldT> &pb,
  370. const pb_variable<FieldT> &outx,
  371. const pb_variable<FieldT> &outy,
  372. const pb_variable<FieldT> &Ax,
  373. const pb_variable<FieldT> &Ay,
  374. const pb_variable_array<FieldT> &svec,
  375. const FieldT &Px, const FieldT &Py,
  376. FieldT &AXSx, FieldT &AXSy) :
  377. gadget<FieldT>(pb, "ec_constant_scalarmul_vec_accum_gadget"),
  378. // Precomputed coordinates of C
  379. Cx(2),
  380. Cy("4950745124018817972378217179409499695353526031437053848725554590521829916331"),
  381. outx(outx), outy(outy), Ax(Ax), Ay(Ay), svec(svec), Px(Px), Py(Py)
  382. {
  383. size_t numbits = svec.size();
  384. // See loop comments below: if numbits is odd, we need (numbits-1)/2
  385. // slots. If numbits is even, we need (numbits-2)/2 slots. So
  386. // with integer truncated division, (numbits-1)/2 will be correct
  387. // in both cases. (Well, if numbits is 0 for some reason, we also want
  388. // to get 0.)
  389. size_t accumslots = 0;
  390. if (numbits > 0) {
  391. accumslots = (numbits-1)/2;
  392. }
  393. accumx.allocate(this->pb, accumslots, "accumx");
  394. accumy.allocate(this->pb, accumslots, "accumy");
  395. FieldT twoiPx = Px, twoiPy = Py;
  396. size_t i = 0, accnext = 0;
  397. while(i < numbits) {
  398. // Invariant: twoiP = 2^i * P
  399. // Invariant: i is even and accnext = i/2
  400. if (i == numbits-1) {
  401. FieldT twoiPCx, twoiPCy;
  402. ec_add_points(twoiPCx, twoiPCy, twoiPx, twoiPy, Cx, Cy);
  403. twoadders.emplace_back(this->pb,
  404. outx, outy,
  405. (i == 0 ? Ax : accumx[accnext-1]),
  406. (i == 0 ? Ay : accumy[accnext-1]),
  407. svec[i], Cx, Cy, twoiPCx, twoiPCy);
  408. // This makes i odd, but also exits the loop with
  409. // i = numbits and accnext = (numbits-1)/2
  410. i += 1;
  411. } else {
  412. // Do two bits at a time
  413. // We need to compute 2^i * a * P + C for a = 1,2,3
  414. FieldT twoi2Px, twoi2Py;
  415. FieldT twoi1PCx, twoi1PCy, twoi2PCx, twoi2PCy, twoi3PCx, twoi3PCy;
  416. ec_add_points(twoi1PCx, twoi1PCy, twoiPx, twoiPy, Cx, Cy);
  417. ec_double_point(twoi2Px, twoi2Py, twoiPx, twoiPy);
  418. ec_add_points(twoi2PCx, twoi2PCy, twoi2Px, twoi2Py, Cx, Cy);
  419. ec_add_points(twoi3PCx, twoi3PCy, twoi2Px, twoi2Py,
  420. twoi1PCx, twoi1PCy);
  421. fouradders.emplace_back(this->pb,
  422. (i == numbits-2 ? outx : accumx[accnext]),
  423. (i == numbits-2 ? outy : accumy[accnext]),
  424. (i == 0 ? Ax : accumx[accnext-1]),
  425. (i == 0 ? Ay : accumy[accnext-1]),
  426. svec[i], svec[i+1], Cx, Cy, twoi1PCx, twoi1PCy,
  427. twoi2PCx, twoi2PCy, twoi3PCx, twoi3PCy);
  428. // If i == numbits-2, we write directly to out and not accum above, and
  429. // exit the loop with i even and i == numbits and accnext = (numbits-2)/2
  430. if (i < numbits - 2) {
  431. accnext += 1;
  432. }
  433. i += 2;
  434. ec_double_point(twoiPx, twoiPy, twoi2Px, twoi2Py);
  435. }
  436. FieldT newAXSx, newAXSy;
  437. ec_add_points(newAXSx, newAXSy, AXSx, AXSy, Cx, Cy);
  438. AXSx = newAXSx;
  439. AXSy = newAXSy;
  440. }
  441. }
  442. void generate_r1cs_constraints()
  443. {
  444. for (auto&& gadget : fouradders) {
  445. gadget.generate_r1cs_constraints();
  446. }
  447. for (auto&& gadget : twoadders) {
  448. gadget.generate_r1cs_constraints();
  449. }
  450. }
  451. void generate_r1cs_witness()
  452. {
  453. for (auto&& gadget : fouradders) {
  454. gadget.generate_r1cs_witness();
  455. }
  456. for (auto&& gadget : twoadders) {
  457. gadget.generate_r1cs_witness();
  458. }
  459. }
  460. };
  461. // Compute A + s*P as (outx, outy) for an accumulator A, a given
  462. // constant point P, and s given as a field element. The (constant)
  463. // accumulator excess (AXS) will be updated; when all the computations
  464. // are complete, AXS should be subtracted from the accumulator A.
  465. template<typename FieldT>
  466. class ec_constant_scalarmul_accum_gadget : public gadget<FieldT> {
  467. private:
  468. pb_variable_array<FieldT> svec;
  469. std::vector<packing_gadget<FieldT> > packers;
  470. std::vector<ec_constant_scalarmul_vec_accum_gadget<FieldT> > vecgadget;
  471. public:
  472. const pb_variable<FieldT> outx, outy;
  473. const pb_variable<FieldT> Ax, Ay;
  474. const pb_variable<FieldT> s;
  475. const FieldT Px, Py;
  476. ec_constant_scalarmul_accum_gadget(protoboard<FieldT> &pb,
  477. const pb_variable<FieldT> &outx,
  478. const pb_variable<FieldT> &outy,
  479. const pb_variable<FieldT> &Ax,
  480. const pb_variable<FieldT> &Ay,
  481. const pb_variable<FieldT> &s,
  482. const FieldT &Px, const FieldT &Py,
  483. FieldT &AXSx, FieldT &AXSy) :
  484. gadget<FieldT>(pb, "ec_constant_scalarmul_accum_gadget"),
  485. outx(outx), outy(outy), Ax(Ax), Ay(Ay), s(s), Px(Px), Py(Py)
  486. {
  487. // Allocate variables to protoboard
  488. // The strings (like "x") are only for debugging purposes
  489. size_t numbits = FieldT::num_bits;
  490. svec.allocate(this->pb, numbits, "svec");
  491. packers.emplace_back(this->pb, svec, s);
  492. vecgadget.emplace_back(this->pb, outx, outy, Ax, Ay, svec, Px, Py, AXSx, AXSy);
  493. }
  494. void generate_r1cs_constraints()
  495. {
  496. packers[0].generate_r1cs_constraints(true);
  497. vecgadget[0].generate_r1cs_constraints();
  498. }
  499. void generate_r1cs_witness()
  500. {
  501. packers[0].generate_r1cs_witness_from_packed();
  502. vecgadget[0].generate_r1cs_witness();
  503. }
  504. };
  505. // Compute s*P as (outx, outy) for a given constant point P, and s given
  506. // as a bit vector. The _caller_ is responsible for proving that the
  507. // elements of svec are bits.
  508. template<typename FieldT>
  509. class ec_constant_scalarmul_vec_gadget : public gadget<FieldT> {
  510. private:
  511. FieldT Cx, Cy, Ax, Ay, AXSx, AXSy;
  512. pb_variable<FieldT> accinx, acciny, accoutx, accouty;
  513. std::vector<ec_constant_scalarmul_vec_accum_gadget<FieldT> > scalarmuls;
  514. std::vector<ec_constant_add_gadget<FieldT> > adders;
  515. public:
  516. const pb_variable<FieldT> outx, outy;
  517. const pb_variable_array<FieldT> svec;
  518. const FieldT Px, Py;
  519. ec_constant_scalarmul_vec_gadget(protoboard<FieldT> &pb,
  520. const pb_variable<FieldT> &outx,
  521. const pb_variable<FieldT> &outy,
  522. const pb_variable_array<FieldT> &svec,
  523. const FieldT &Px, const FieldT &Py) :
  524. gadget<FieldT>(pb, "ec_constant_scalarmul_vec_gadget"),
  525. // Precomputed coordinates of C and A
  526. Cx(2),
  527. Cy("4950745124018817972378217179409499695353526031437053848725554590521829916331"),
  528. Ax(4),
  529. Ay("1929778687269876629657252589535788315400602403700102541701561325064015752665"),
  530. outx(outx), outy(outy), svec(svec), Px(Px), Py(Py)
  531. {
  532. AXSx = Ax;
  533. AXSy = Ay;
  534. accinx.allocate(this->pb, "accinx");
  535. acciny.allocate(this->pb, "acciny");
  536. accoutx.allocate(this->pb, "accoutx");
  537. accouty.allocate(this->pb, "accouty");
  538. scalarmuls.emplace_back(pb, accoutx, accouty, accinx, acciny, svec, Px, Py, AXSx, AXSy);
  539. adders.emplace_back(pb, outx, outy, accoutx, accouty, AXSx, -AXSy);
  540. }
  541. void generate_r1cs_constraints()
  542. {
  543. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(accinx, 1, Ax));
  544. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(acciny, 1, Ay));
  545. scalarmuls[0].generate_r1cs_constraints();
  546. adders[0].generate_r1cs_constraints();
  547. }
  548. void generate_r1cs_witness()
  549. {
  550. this->pb.val(accinx) = Ax;
  551. this->pb.val(acciny) = Ay;
  552. scalarmuls[0].generate_r1cs_witness();
  553. adders[0].generate_r1cs_witness();
  554. }
  555. };
  556. // Compute s*P as (outx, outy) for a given constant point P, and s given
  557. // as a field element.
  558. template<typename FieldT>
  559. class ec_constant_scalarmul_gadget : public gadget<FieldT> {
  560. private:
  561. pb_variable_array<FieldT> svec;
  562. std::vector<packing_gadget<FieldT> > packers;
  563. std::vector<ec_constant_scalarmul_vec_gadget<FieldT> > vecgadget;
  564. public:
  565. const pb_variable<FieldT> outx, outy;
  566. const pb_variable<FieldT> s;
  567. const FieldT Px, Py;
  568. ec_constant_scalarmul_gadget(protoboard<FieldT> &pb,
  569. const pb_variable<FieldT> &outx,
  570. const pb_variable<FieldT> &outy,
  571. const pb_variable<FieldT> &s,
  572. const FieldT &Px, const FieldT &Py) :
  573. gadget<FieldT>(pb, "ec_constant_scalarmul_gadget"),
  574. outx(outx), outy(outy), s(s), Px(Px), Py(Py)
  575. {
  576. // Allocate variables to protoboard
  577. // The strings (like "x") are only for debugging purposes
  578. size_t numbits = FieldT::num_bits;
  579. svec.allocate(this->pb, numbits, "svec");
  580. packers.emplace_back(this->pb, svec, s);
  581. vecgadget.emplace_back(this->pb, outx, outy, svec, Px, Py);
  582. }
  583. void generate_r1cs_constraints()
  584. {
  585. packers[0].generate_r1cs_constraints(true);
  586. vecgadget[0].generate_r1cs_constraints();
  587. }
  588. void generate_r1cs_witness()
  589. {
  590. packers[0].generate_r1cs_witness_from_packed();
  591. vecgadget[0].generate_r1cs_witness();
  592. }
  593. };
  594. template<typename FieldT>
  595. class ec_scalarmul_gadget;
  596. // Compute A + s*P as (outx, outy) for an accumulator A, a precomputed
  597. // addition table Ptable for a variable point P, and s given as a bit
  598. // vector. The _caller_ is responsible for proving that the elements of
  599. // svec are bits. The (constant) accumulator excess (AXS) will be
  600. // updated; when all the computations are complete, AXS should be
  601. // subtracted from the accumulator A. The addition table is a variable
  602. // array of length 2*numbits (where numbits is the length of svec) such
  603. // that Ptable[2*i] and Ptable[2*i+1] are the (x,y) coordinates of
  604. // 2^i * P + C. Set Ptable_set_constraints to true (exactly once
  605. // in the event the same Ptable is reused in the same circuit) if
  606. // the Ptable is part of the private input. Set Ptable_fill_values
  607. // to true exactly once per Ptable (again, in case it it reused in the
  608. // same circuit).
  609. template<typename FieldT>
  610. class ec_scalarmul_vec_accum_gadget : public gadget<FieldT> {
  611. private:
  612. FieldT Cx, Cy;
  613. pb_variable_array<FieldT> accumx, accumy;
  614. pb_variable_array<FieldT> twoiPx, twoiPy;
  615. std::vector<ec_constant_add_gadget<FieldT> > cadders;
  616. std::vector<ec_add_gadget<FieldT> > adders;
  617. std::vector<ec_2_1constant_add_gadget<FieldT> > twoadders;
  618. public:
  619. const pb_variable<FieldT> outx, outy;
  620. const pb_variable<FieldT> Ax, Ay;
  621. const pb_variable_array<FieldT> svec;
  622. const pb_variable<FieldT> Px, Py;
  623. const pb_variable_array<FieldT> Ptable;
  624. bool Ptable_set_constraints, Ptable_fill_values;
  625. ec_scalarmul_vec_accum_gadget(protoboard<FieldT> &pb,
  626. const pb_variable<FieldT> &outx,
  627. const pb_variable<FieldT> &outy,
  628. const pb_variable<FieldT> &Ax,
  629. const pb_variable<FieldT> &Ay,
  630. const pb_variable_array<FieldT> &svec,
  631. const pb_variable<FieldT> &Px,
  632. const pb_variable<FieldT> &Py,
  633. const pb_variable_array<FieldT> &Ptable,
  634. bool Ptable_set_constraints,
  635. bool Ptable_fill_values,
  636. FieldT &AXSx, FieldT &AXSy) :
  637. gadget<FieldT>(pb, "ec_scalarmul_vec_accum_gadget"),
  638. // Precomputed coordinates of C
  639. Cx(2),
  640. Cy("4950745124018817972378217179409499695353526031437053848725554590521829916331"),
  641. outx(outx), outy(outy), Ax(Ax), Ay(Ay), svec(svec),
  642. Px(Px), Py(Py), Ptable(Ptable),
  643. Ptable_set_constraints(Ptable_set_constraints),
  644. Ptable_fill_values(Ptable_fill_values)
  645. {
  646. size_t numbits = svec.size();
  647. assert(Ptable.size() == 2*numbits);
  648. if (Ptable_set_constraints) {
  649. // Create the adders to fill the Ptable with the correct values.
  650. // Ptable[2*i] and Ptable[2*i+1] are the (x,y) coordinates of
  651. // 2^i * P + C.
  652. if (numbits > 0) {
  653. // Add P and C to get Ptable[0,1] = P+C
  654. cadders.emplace_back(this->pb, Ptable[0], Ptable[1],
  655. Px, Py, Cx, Cy);
  656. }
  657. if (numbits > 1) {
  658. // Add P and P+C to get Ptable[2,3] = 2*P+C
  659. adders.emplace_back(this->pb, Ptable[2], Ptable[3],
  660. Px, Py, Ptable[0], Ptable[1]);
  661. }
  662. if (numbits > 2) {
  663. twoiPx.allocate(this->pb, numbits-2, "twoiPx");
  664. twoiPy.allocate(this->pb, numbits-2, "twoiPy");
  665. }
  666. for (size_t i = 2; i < numbits; ++i) {
  667. // Invariant: twoiP[i] = 2^{i+1} * P
  668. // Compute 2^{i-1}*P = (2^{i-1}*P + C) - C
  669. cadders.emplace_back(this->pb,
  670. twoiPx[i-2], twoiPy[i-2],
  671. Ptable[2*(i-1)], Ptable[2*(i-1)+1],
  672. Cx, -Cy);
  673. // Compute 2^{i}*P + C = (2^{i-1}*P + C) + (2^{i-1}*P)
  674. adders.emplace_back(this->pb,
  675. Ptable[2*i], Ptable[2*i+1],
  676. Ptable[2*i-2], Ptable[2*i-1],
  677. twoiPx[i-2], twoiPy[i-2]);
  678. }
  679. }
  680. accumx.allocate(this->pb, numbits-1, "accumx");
  681. accumy.allocate(this->pb, numbits-1, "accumy");
  682. for (size_t i = 0; i < numbits; ++i) {
  683. twoadders.emplace_back(this->pb,
  684. (i == numbits-1 ? outx : accumx[i]),
  685. (i == numbits-1 ? outy : accumy[i]),
  686. (i == 0 ? Ax : accumx[i-1]),
  687. (i == 0 ? Ay : accumy[i-1]),
  688. svec[i], Cx, Cy, Ptable[2*i], Ptable[2*i+1]);
  689. FieldT newAXSx, newAXSy;
  690. ec_add_points(newAXSx, newAXSy, AXSx, AXSy, Cx, Cy);
  691. AXSx = newAXSx;
  692. AXSy = newAXSy;
  693. }
  694. }
  695. void generate_r1cs_constraints()
  696. {
  697. if (Ptable_set_constraints) {
  698. for (auto&& gadget : cadders) {
  699. gadget.generate_r1cs_constraints();
  700. }
  701. for (auto&& gadget : adders) {
  702. gadget.generate_r1cs_constraints();
  703. }
  704. }
  705. for (auto&& gadget : twoadders) {
  706. gadget.generate_r1cs_constraints();
  707. }
  708. }
  709. void generate_r1cs_witness()
  710. {
  711. if (Ptable_set_constraints) {
  712. // We also have to satisfy the constraints we set
  713. size_t numbits = Ptable.size() / 2;
  714. if (numbits > 0) {
  715. cadders[0].generate_r1cs_witness();
  716. }
  717. if (numbits > 1) {
  718. adders[0].generate_r1cs_witness();
  719. }
  720. for (size_t i = 2; i < numbits; ++i) {
  721. cadders[i-1].generate_r1cs_witness();
  722. adders[i-1].generate_r1cs_witness();
  723. }
  724. } else if (Ptable_fill_values) {
  725. // We can just compute the Ptable values manually
  726. ec_scalarmul_gadget<FieldT>::compute_Ptable(this->pb, Ptable, Px, Py);
  727. }
  728. for (auto&& gadget : twoadders) {
  729. gadget.generate_r1cs_witness();
  730. }
  731. }
  732. };
  733. // Compute A + s*P as (outx, outy) for an accumulator A, a precomputed
  734. // addition table Ptable for a variable point P, and s given as a field
  735. // element. The _caller_ is responsible for proving that the elements
  736. // of svec are bits. The (constant) accumulator excess (AXS) will be
  737. // updated; when all the computations are complete, AXS should be
  738. // subtracted from the accumulator A. The addition table is a variable
  739. // array of length 2*numbits (where numbits is the length of the FieldT
  740. // size) such that Ptable[2*i] and Ptable[2*i+1] are the (x,y)
  741. // coordinates of 2^i * P + C. Set Ptable_set_constraints to true
  742. // (exactly once in the event the same Ptable is reused in the same
  743. // circuit) if the Ptable is part of the private input. Set
  744. // Ptable_fill_values to true exactly once per Ptable (again, in case it
  745. // it reused in the same circuit).
  746. template<typename FieldT>
  747. class ec_scalarmul_accum_gadget : public gadget<FieldT> {
  748. private:
  749. pb_variable_array<FieldT> svec;
  750. std::vector<packing_gadget<FieldT> > packers;
  751. std::vector<ec_scalarmul_vec_accum_gadget<FieldT> > vecgadget;
  752. public:
  753. const pb_variable<FieldT> outx, outy;
  754. const pb_variable<FieldT> Ax, Ay;
  755. const pb_variable<FieldT> s;
  756. const pb_variable<FieldT> Px, Py;
  757. const pb_variable_array<FieldT> Ptable;
  758. bool Ptable_set_constraints, Ptable_fill_values;
  759. ec_scalarmul_accum_gadget(protoboard<FieldT> &pb,
  760. const pb_variable<FieldT> &outx,
  761. const pb_variable<FieldT> &outy,
  762. const pb_variable<FieldT> &Ax,
  763. const pb_variable<FieldT> &Ay,
  764. const pb_variable<FieldT> &s,
  765. const pb_variable<FieldT> &Px,
  766. const pb_variable<FieldT> &Py,
  767. const pb_variable_array<FieldT> &Ptable,
  768. bool Ptable_set_constraints,
  769. bool Ptable_fill_values,
  770. FieldT &AXSx, FieldT &AXSy) :
  771. gadget<FieldT>(pb, "ec_scalarmul_accum_gadget"),
  772. outx(outx), outy(outy), Ax(Ax), Ay(Ay), s(s),
  773. Px(Px), Py(Py), Ptable(Ptable),
  774. Ptable_set_constraints(Ptable_set_constraints),
  775. Ptable_fill_values(Ptable_fill_values)
  776. {
  777. // Allocate variables to protoboard
  778. // The strings (like "x") are only for debugging purposes
  779. size_t numbits = FieldT::num_bits;
  780. svec.allocate(this->pb, numbits, "svec");
  781. packers.emplace_back(this->pb, svec, s);
  782. vecgadget.emplace_back(this->pb, outx, outy, Ax, Ay, svec,
  783. Px, Py, Ptable, Ptable_set_constraints, Ptable_fill_values,
  784. AXSx, AXSy);
  785. }
  786. void generate_r1cs_constraints()
  787. {
  788. packers[0].generate_r1cs_constraints(true);
  789. vecgadget[0].generate_r1cs_constraints();
  790. }
  791. void generate_r1cs_witness()
  792. {
  793. packers[0].generate_r1cs_witness_from_packed();
  794. vecgadget[0].generate_r1cs_witness();
  795. }
  796. };
  797. // Compute s*P as (outx, outy) for a precomputed addition table Ptable
  798. // for a variable point P, and s given as a bit vector. The _caller_ is
  799. // responsible for proving that the elements of svec are bits.
  800. // The addition table is a variable array of length 2*numbits (where
  801. // numbits is the length of svec) such that Ptable[2*i] and
  802. // Ptable[2*i+1] are the (x,y) coordinates of 2^i * P + C. Set
  803. // Ptable_set_constraints to true (exactly once in the event the same
  804. // Ptable is reused in the same circuit) if the Ptable is part of the
  805. // private input. Set Ptable_fill_values to true exactly once per
  806. // Ptable (again, in case it it reused in the same circuit).
  807. template<typename FieldT>
  808. class ec_scalarmul_vec_gadget : public gadget<FieldT> {
  809. private:
  810. FieldT Cx, Cy, Ax, Ay, AXSx, AXSy;
  811. pb_variable<FieldT> accinx, acciny, accoutx, accouty;
  812. std::vector<ec_scalarmul_vec_accum_gadget<FieldT> > scalarmuls;
  813. std::vector<ec_constant_add_gadget<FieldT> > adders;
  814. public:
  815. const pb_variable<FieldT> outx, outy;
  816. const pb_variable_array<FieldT> svec;
  817. const pb_variable<FieldT> Px, Py;
  818. const pb_variable_array<FieldT> Ptable;
  819. bool Ptable_set_constraints, Ptable_fill_values;
  820. ec_scalarmul_vec_gadget(protoboard<FieldT> &pb,
  821. const pb_variable<FieldT> &outx,
  822. const pb_variable<FieldT> &outy,
  823. const pb_variable_array<FieldT> &svec,
  824. const pb_variable<FieldT> &Px,
  825. const pb_variable<FieldT> &Py,
  826. const pb_variable_array<FieldT> &Ptable,
  827. bool Ptable_set_constraints,
  828. bool Ptable_fill_values) :
  829. gadget<FieldT>(pb, "ec_scalarmul_vec_gadget"),
  830. // Precomputed coordinates of C and A
  831. Cx(2),
  832. Cy("4950745124018817972378217179409499695353526031437053848725554590521829916331"),
  833. Ax(4),
  834. Ay("1929778687269876629657252589535788315400602403700102541701561325064015752665"),
  835. outx(outx), outy(outy), svec(svec),
  836. Px(Px), Py(Py), Ptable(Ptable),
  837. Ptable_set_constraints(Ptable_set_constraints),
  838. Ptable_fill_values(Ptable_fill_values)
  839. {
  840. AXSx = Ax;
  841. AXSy = Ay;
  842. accinx.allocate(this->pb, "accinx");
  843. acciny.allocate(this->pb, "acciny");
  844. accoutx.allocate(this->pb, "accoutx");
  845. accouty.allocate(this->pb, "accouty");
  846. scalarmuls.emplace_back(pb, accoutx, accouty, accinx, acciny, svec,
  847. Px, Py, Ptable, Ptable_set_constraints, Ptable_fill_values,
  848. AXSx, AXSy);
  849. adders.emplace_back(pb, outx, outy, accoutx, accouty, AXSx, -AXSy);
  850. }
  851. void generate_r1cs_constraints()
  852. {
  853. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(accinx, 1, Ax));
  854. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(acciny, 1, Ay));
  855. scalarmuls[0].generate_r1cs_constraints();
  856. adders[0].generate_r1cs_constraints();
  857. }
  858. void generate_r1cs_witness()
  859. {
  860. this->pb.val(accinx) = Ax;
  861. this->pb.val(acciny) = Ay;
  862. scalarmuls[0].generate_r1cs_witness();
  863. adders[0].generate_r1cs_witness();
  864. }
  865. };
  866. // Compute s*P as (outx, outy) for a precomputed addition table Ptable
  867. // for a variable point P, and s given as a field element. The addition
  868. // table is a variable array of length 2*numbits (where numbits is the
  869. // length of the FieldT size) such that Ptable[2*i] and Ptable[2*i+1]
  870. // are the (x,y) coordinates of 2^i * P + C. Set Ptable_set_constraints
  871. // to true (exactly once in the event the same Ptable is reused in the
  872. // same circuit) if the Ptable is part of the private input. Set
  873. // Ptable_fill_values to true exactly once per Ptable (again, in case it
  874. // it reused in the same circuit).
  875. template<typename FieldT>
  876. class ec_scalarmul_gadget : public gadget<FieldT> {
  877. private:
  878. pb_variable_array<FieldT> svec;
  879. std::vector<packing_gadget<FieldT> > packers;
  880. std::vector<ec_scalarmul_vec_gadget<FieldT> > vecgadget;
  881. public:
  882. const pb_variable<FieldT> outx, outy;
  883. const pb_variable<FieldT> s;
  884. const pb_variable<FieldT> Px, Py;
  885. const pb_variable_array<FieldT> Ptable;
  886. bool Ptable_set_constraints, Ptable_fill_values;
  887. ec_scalarmul_gadget(protoboard<FieldT> &pb,
  888. const pb_variable<FieldT> &outx,
  889. const pb_variable<FieldT> &outy,
  890. const pb_variable<FieldT> &s,
  891. const pb_variable<FieldT> &Px,
  892. const pb_variable<FieldT> &Py,
  893. const pb_variable_array<FieldT> &Ptable,
  894. bool Ptable_set_constraints,
  895. bool Ptable_fill_values) :
  896. gadget<FieldT>(pb, "ec_scalarmul_gadget"),
  897. outx(outx), outy(outy), s(s),
  898. Px(Px), Py(Py), Ptable(Ptable),
  899. Ptable_set_constraints(Ptable_set_constraints),
  900. Ptable_fill_values(Ptable_fill_values)
  901. {
  902. // Allocate variables to protoboard
  903. // The strings (like "x") are only for debugging purposes
  904. size_t numbits = FieldT::num_bits;
  905. svec.allocate(this->pb, numbits, "svec");
  906. packers.emplace_back(this->pb, svec, s);
  907. vecgadget.emplace_back(this->pb, outx, outy, svec,
  908. Px, Py, Ptable, Ptable_set_constraints, Ptable_fill_values);
  909. }
  910. void generate_r1cs_constraints()
  911. {
  912. packers[0].generate_r1cs_constraints(true);
  913. vecgadget[0].generate_r1cs_constraints();
  914. }
  915. void generate_r1cs_witness()
  916. {
  917. packers[0].generate_r1cs_witness_from_packed();
  918. vecgadget[0].generate_r1cs_witness();
  919. }
  920. // Compute the addition table. The addition table is a variable array
  921. // of length 2*numbits such that Ptable[2*i] and Ptable[2*i+1] are the
  922. // (x,y) coordinates of 2^i * P + C.
  923. static void compute_Ptable(protoboard<FieldT> &pb,
  924. const pb_variable_array<FieldT> &Ptable,
  925. const pb_variable<FieldT> &Px,
  926. const pb_variable<FieldT> &Py)
  927. {
  928. const FieldT Cx(2);
  929. const FieldT Cy("4950745124018817972378217179409499695353526031437053848725554590521829916331");
  930. assert(Ptable.size() % 2 == 0);
  931. size_t numbits = Ptable.size() / 2;
  932. FieldT twoiPx = pb.val(Px);
  933. FieldT twoiPy = pb.val(Py);
  934. for (size_t i = 0; i < numbits; ++i) {
  935. // Invariant: (twoiPx, twoiPy) = 2^i * P
  936. // Compute 2^i * P + C
  937. FieldT twoiPCx, twoiPCy;
  938. ec_add_points(twoiPCx, twoiPCy, twoiPx, twoiPy, Cx, Cy);
  939. pb.val(Ptable[2*i]) = twoiPCx;
  940. pb.val(Ptable[2*i+1]) = twoiPCy;
  941. // Compute 2^{i+1} * P
  942. FieldT twoi1Px, twoi1Py;
  943. ec_double_point(twoi1Px, twoi1Py, twoiPx, twoiPy);
  944. twoiPx = twoi1Px;
  945. twoiPy = twoi1Py;
  946. }
  947. }
  948. };
  949. // Compute a*G + b*H as (outx, outy), given a and b as field elements.
  950. template<typename FieldT>
  951. class ec_pedersen_gadget : public gadget<FieldT> {
  952. private:
  953. pb_variable<FieldT> accinx, acciny, accmidx, accmidy, accoutx, accouty;
  954. std::vector<ec_constant_scalarmul_accum_gadget<FieldT> > mulgadgets;
  955. std::vector<ec_constant_add_gadget<FieldT> > addgadget;
  956. const FieldT Gx, Gy, Hx, Hy, Ax, Ay;
  957. public:
  958. const pb_variable<FieldT> outx, outy, a, b;
  959. ec_pedersen_gadget(protoboard<FieldT> &pb,
  960. const pb_variable<FieldT> &outx,
  961. const pb_variable<FieldT> &outy,
  962. const pb_variable<FieldT> &a,
  963. const pb_variable<FieldT> &b) :
  964. gadget<FieldT>(pb, "ec_pedersen_gadget"),
  965. outx(outx), outy(outy), a(a), b(b),
  966. // Precomputed coordinates of G, H, and A
  967. Gx(0),
  968. Gy("11977228949870389393715360594190192321220966033310912010610740966317727761886"),
  969. Hx(1),
  970. Hy("21803877843449984883423225223478944275188924769286999517937427649571474907279"),
  971. Ax(4),
  972. Ay("1929778687269876629657252589535788315400602403700102541701561325064015752665")
  973. {
  974. // Allocate variables to protoboard
  975. // The strings (like "x") are only for debugging purposes
  976. accinx.allocate(this->pb, "accinx");
  977. acciny.allocate(this->pb, "acciny");
  978. accmidx.allocate(this->pb, "accmidx");
  979. accmidy.allocate(this->pb, "accmidy");
  980. accoutx.allocate(this->pb, "accoutx");
  981. accouty.allocate(this->pb, "accouty");
  982. // Initialize the accumulator
  983. FieldT AXSx = Ax;
  984. FieldT AXSy = Ay;
  985. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(accinx, 1, Ax));
  986. this->pb.add_r1cs_constraint(r1cs_constraint<FieldT>(acciny, 1, Ay));
  987. // Initialize the gadgets
  988. mulgadgets.emplace_back(this->pb, accmidx, accmidy, accinx, acciny, a, Gx, Gy, AXSx, AXSy);
  989. mulgadgets.emplace_back(this->pb, accoutx, accouty, accmidx, accmidy, b, Hx, Hy, AXSx, AXSy);
  990. // Subtract the accumulator excess to get the result
  991. addgadget.emplace_back(this->pb, outx, outy, accoutx, accouty, AXSx, -AXSy);
  992. }
  993. void generate_r1cs_constraints()
  994. {
  995. this->pb.val(accinx) = Ax;
  996. this->pb.val(acciny) = Ay;
  997. mulgadgets[0].generate_r1cs_constraints();
  998. mulgadgets[1].generate_r1cs_constraints();
  999. addgadget[0].generate_r1cs_constraints();
  1000. }
  1001. void generate_r1cs_witness()
  1002. {
  1003. mulgadgets[0].generate_r1cs_witness();
  1004. mulgadgets[1].generate_r1cs_witness();
  1005. addgadget[0].generate_r1cs_witness();
  1006. }
  1007. };