escalarmulany.circom
1 /* 2 Copyright 2018 0KIMS association. 3 4 This file is part of circom (Zero Knowledge Circuit Compiler). 5 6 circom is a free software: you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by 8 the Free Software Foundation, either version 3 of the License, or 9 (at your option) any later version. 10 11 circom is distributed in the hope that it will be useful, but WITHOUT 12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 14 License for more details. 15 16 You should have received a copy of the GNU General Public License 17 along with circom. If not, see <https://www.gnu.org/licenses/>. 18 */ 19 pragma circom 2.0.0; 20 21 include "montgomery.circom"; 22 include "babyjub.circom"; 23 include "comparators.circom"; 24 25 template Multiplexor2() { 26 signal input sel; 27 signal input in[2][2]; 28 signal output out[2]; 29 30 out[0] <== (in[1][0] - in[0][0])*sel + in[0][0]; 31 out[1] <== (in[1][1] - in[0][1])*sel + in[0][1]; 32 } 33 34 template BitElementMulAny() { 35 signal input sel; 36 signal input dblIn[2]; 37 signal input addIn[2]; 38 signal output dblOut[2]; 39 signal output addOut[2]; 40 41 component doubler = MontgomeryDouble(); 42 component adder = MontgomeryAdd(); 43 component selector = Multiplexor2(); 44 45 46 sel ==> selector.sel; 47 48 dblIn[0] ==> doubler.in[0]; 49 dblIn[1] ==> doubler.in[1]; 50 doubler.out[0] ==> adder.in1[0]; 51 doubler.out[1] ==> adder.in1[1]; 52 addIn[0] ==> adder.in2[0]; 53 addIn[1] ==> adder.in2[1]; 54 addIn[0] ==> selector.in[0][0]; 55 addIn[1] ==> selector.in[0][1]; 56 adder.out[0] ==> selector.in[1][0]; 57 adder.out[1] ==> selector.in[1][1]; 58 59 doubler.out[0] ==> dblOut[0]; 60 doubler.out[1] ==> dblOut[1]; 61 selector.out[0] ==> addOut[0]; 62 selector.out[1] ==> addOut[1]; 63 } 64 65 // p is montgomery point 66 // n must be <= 248 67 // returns out in twisted edwards 68 // Double is in montgomery to be linked; 69 70 template SegmentMulAny(n) { 71 signal input e[n]; 72 signal input p[2]; 73 signal output out[2]; 74 signal output dbl[2]; 75 76 component bits[n-1]; 77 78 component e2m = Edwards2Montgomery(); 79 80 p[0] ==> e2m.in[0]; 81 p[1] ==> e2m.in[1]; 82 83 var i; 84 85 bits[0] = BitElementMulAny(); 86 e2m.out[0] ==> bits[0].dblIn[0]; 87 e2m.out[1] ==> bits[0].dblIn[1]; 88 e2m.out[0] ==> bits[0].addIn[0]; 89 e2m.out[1] ==> bits[0].addIn[1]; 90 e[1] ==> bits[0].sel; 91 92 for (i=1; i<n-1; i++) { 93 bits[i] = BitElementMulAny(); 94 95 bits[i-1].dblOut[0] ==> bits[i].dblIn[0]; 96 bits[i-1].dblOut[1] ==> bits[i].dblIn[1]; 97 bits[i-1].addOut[0] ==> bits[i].addIn[0]; 98 bits[i-1].addOut[1] ==> bits[i].addIn[1]; 99 e[i+1] ==> bits[i].sel; 100 } 101 102 bits[n-2].dblOut[0] ==> dbl[0]; 103 bits[n-2].dblOut[1] ==> dbl[1]; 104 105 component m2e = Montgomery2Edwards(); 106 107 bits[n-2].addOut[0] ==> m2e.in[0]; 108 bits[n-2].addOut[1] ==> m2e.in[1]; 109 110 component eadder = BabyAdd(); 111 112 m2e.out[0] ==> eadder.x1; 113 m2e.out[1] ==> eadder.y1; 114 -p[0] ==> eadder.x2; 115 p[1] ==> eadder.y2; 116 117 component lastSel = Multiplexor2(); 118 119 e[0] ==> lastSel.sel; 120 eadder.xout ==> lastSel.in[0][0]; 121 eadder.yout ==> lastSel.in[0][1]; 122 m2e.out[0] ==> lastSel.in[1][0]; 123 m2e.out[1] ==> lastSel.in[1][1]; 124 125 lastSel.out[0] ==> out[0]; 126 lastSel.out[1] ==> out[1]; 127 } 128 129 // This function assumes that p is in the subgroup and it is different to 0 130 131 template EscalarMulAny(n) { 132 signal input e[n]; // Input in binary format 133 signal input p[2]; // Point (Twisted format) 134 signal output out[2]; // Point (Twisted format) 135 136 var nsegments = (n-1)\148 +1; 137 var nlastsegment = n - (nsegments-1)*148; 138 139 component segments[nsegments]; 140 component doublers[nsegments-1]; 141 component m2e[nsegments-1]; 142 component adders[nsegments-1]; 143 component zeropoint = IsZero(); 144 zeropoint.in <== p[0]; 145 146 var s; 147 var i; 148 var nseg; 149 150 for (s=0; s<nsegments; s++) { 151 152 nseg = (s < nsegments-1) ? 148 : nlastsegment; 153 154 segments[s] = SegmentMulAny(nseg); 155 156 for (i=0; i<nseg; i++) { 157 e[s*148+i] ==> segments[s].e[i]; 158 } 159 160 if (s==0) { 161 // force G8 point if input point is zero 162 segments[s].p[0] <== p[0] + (5299619240641551281634865583518297030282874472190772894086521144482721001553 - p[0])*zeropoint.out; 163 segments[s].p[1] <== p[1] + (16950150798460657717958625567821834550301663161624707787222815936182638968203 - p[1])*zeropoint.out; 164 } else { 165 doublers[s-1] = MontgomeryDouble(); 166 m2e[s-1] = Montgomery2Edwards(); 167 adders[s-1] = BabyAdd(); 168 169 segments[s-1].dbl[0] ==> doublers[s-1].in[0]; 170 segments[s-1].dbl[1] ==> doublers[s-1].in[1]; 171 172 doublers[s-1].out[0] ==> m2e[s-1].in[0]; 173 doublers[s-1].out[1] ==> m2e[s-1].in[1]; 174 175 m2e[s-1].out[0] ==> segments[s].p[0]; 176 m2e[s-1].out[1] ==> segments[s].p[1]; 177 178 if (s==1) { 179 segments[s-1].out[0] ==> adders[s-1].x1; 180 segments[s-1].out[1] ==> adders[s-1].y1; 181 } else { 182 adders[s-2].xout ==> adders[s-1].x1; 183 adders[s-2].yout ==> adders[s-1].y1; 184 } 185 segments[s].out[0] ==> adders[s-1].x2; 186 segments[s].out[1] ==> adders[s-1].y2; 187 } 188 } 189 190 if (nsegments == 1) { 191 segments[0].out[0]*(1-zeropoint.out) ==> out[0]; 192 segments[0].out[1]+(1-segments[0].out[1])*zeropoint.out ==> out[1]; 193 } else { 194 adders[nsegments-2].xout*(1-zeropoint.out) ==> out[0]; 195 adders[nsegments-2].yout+(1-adders[nsegments-2].yout)*zeropoint.out ==> out[1]; 196 } 197 }