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 "bitify.circom";
 22  include "aliascheck.circom";
 23  include "compconstant.circom";
 24  include "babyjub.circom";
 25  
 26  
 27  function sqrt(n) {
 28  
 29      if (n == 0) {
 30          return 0;
 31      }
 32  
 33      // Test that have solution
 34      var res = n ** ((-1) >> 1);
 35  //        if (res!=1) assert(false, "SQRT does not exists");
 36      if (res!=1) return 0;
 37  
 38      var m = 28;
 39      var c = 19103219067921713944291392827692070036145651957329286315305642004821462161904;
 40      var t = n ** 81540058820840996586704275553141814055101440848469862132140264610111;
 41      var r = n ** ((81540058820840996586704275553141814055101440848469862132140264610111+1)>>1);
 42      var sq;
 43      var i;
 44      var b;
 45      var j;
 46  
 47      while ((r != 0)&&(t != 1)) {
 48          sq = t*t;
 49          i = 1;
 50          while (sq!=1) {
 51              i++;
 52              sq = sq*sq;
 53          }
 54  
 55          // b = c ^ m-i-1
 56          b = c;
 57          for (j=0; j< m-i-1; j ++) b = b*b;
 58  
 59          m = i;
 60          c = b*b;
 61          t = t*c;
 62          r = r*b;
 63      }
 64  
 65      if (r < 0 ) {
 66          r = -r;
 67      }
 68  
 69      return r;
 70  }
 71  
 72  
 73  template Bits2Point() {
 74      signal input in[256];
 75      signal output out[2];
 76  }
 77  
 78  template Bits2Point_Strict() {
 79      signal input in[256];
 80      signal output out[2];
 81  
 82      var i;
 83  
 84      // Check aliasing
 85      component aliasCheckY = AliasCheck();
 86      for (i=0; i<254; i++) {
 87          aliasCheckY.in[i] <== in[i];
 88      }
 89      in[254] === 0;
 90  
 91      component b2nY = Bits2Num(254);
 92      for (i=0; i<254; i++) {
 93          b2nY.in[i] <== in[i];
 94      }
 95  
 96      out[1] <== b2nY.out;
 97  
 98      var a = 168700;
 99      var d = 168696;
100  
101      var y2 = out[1] * out[1];
102  
103      var x = sqrt(   (1-y2)/(a - d*y2)  );
104  
105      if (in[255] == 1) x = -x;
106  
107      out[0] <-- x;
108  
109      component babyCheck = BabyCheck();
110      babyCheck.x <== out[0];
111      babyCheck.y <== out[1];
112  
113      component n2bX = Num2Bits(254);
114      n2bX.in <== out[0];
115      component aliasCheckX = AliasCheck();
116      for (i=0; i<254; i++) {
117          aliasCheckX.in[i] <== n2bX.out[i];
118      }
119  
120      component signCalc = CompConstant(10944121435919637611123202872628637544274182200208017171849102093287904247808);
121      for (i=0; i<254; i++) {
122          signCalc.in[i] <== n2bX.out[i];
123      }
124  
125      signCalc.out === in[255];
126  }
127  
128  
129  template Point2Bits() {
130      signal input in[2];
131      signal output out[256];
132  
133  
134  }
135  
136  template Point2Bits_Strict() {
137      signal input in[2];
138      signal output out[256];
139  
140      var i;
141  
142      component n2bX = Num2Bits(254);
143      n2bX.in <== in[0];
144      component n2bY = Num2Bits(254);
145      n2bY.in <== in[1];
146  
147      component aliasCheckX = AliasCheck();
148      component aliasCheckY = AliasCheck();
149      for (i=0; i<254; i++) {
150          aliasCheckX.in[i] <== n2bX.out[i];
151          aliasCheckY.in[i] <== n2bY.out[i];
152      }
153  
154      component signCalc = CompConstant(10944121435919637611123202872628637544274182200208017171849102093287904247808);
155      for (i=0; i<254; i++) {
156          signCalc.in[i] <== n2bX.out[i];
157      }
158  
159      for (i=0; i<254; i++) {
160          out[i] <== n2bY.out[i];
161      }
162      out[254] <== 0;
163      out[255] <== signCalc.out;
164  }