ecgadget.hpp 46 KB

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