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