edwards25519 curve表示为：
−
x
2
+
y
2
=
1
+
d
x
2
y
2
,
d
=
−
(
121665
/
121666
)
,
q
=
2
255
−
19
-x^2+y^2=1+dx^2y^2,d=-(121665/121666),q=2^{255}-19
−x2+y2=1+dx2y2,d=−(121665/121666),q=2255−19
⇒
x
2
=
(
y
2
−
1
)
/
(
d
y
2
+
1
)
(
m
o
d
q
)
\Rightarrow x^2=(y^2-1)/(dy^2+1)\ (mod\ q)
⇒x2=(y2−1)/(dy2+1) (mod q)
0. 为何edwards curve point可以压缩
根据论文《Twisted Edwards Curves Revisited》有：
可知
(
−
x
,
y
)
+
(
x
,
y
)
=
(
0
,
1
)
=
∞
(-x,y)+(x,y)=(0,1)=\infty
(−x,y)+(x,y)=(0,1)=∞
所以，
(
0
,
1
)
(0,1)
(0,1)不在
F
p
F_p
Fp subgroup中（其中，对于Curve25519，
p
=
8
q
,
q
=
2
252
+
27742317777372353535851937790883648493
p=8q,q=2^{252} + 27742317777372353535851937790883648493
p=8q,q=2252+27742317777372353535851937790883648493）。
因此：
(
−
x
,
y
)
和
(
x
,
y
)
(-x,y)和(x,y)
(−x,y)和(x,y)不可以同时在同一个subgroup中，于是可以直接取
y
y
y坐标和
x
x
x坐标的符号位来表示唯一点。
以上内容参考https://ethresear.ch/t/some-snarky-tricks-from-ethboston-zeropool-under-the-hood/6115：（dalek-Curve25519中的压缩算法采用是
(
−
x
,
y
)
和
(
x
,
y
)
(-x,y)和(x,y)
(−x,y)和(x,y)，github.com/snjax/circomlib中采用的压缩算法是
(
x
,
y
)
和
(
x
,
−
y
)
(x,y)和(x,-y)
(x,y)和(x,−y)）。
1. compression压缩算法
将edwards25519的point
(
x
,
y
)
(x,y)
(x,y)，其中每个
x
,
y
x,y
x,y均可以little-endian数组[u8;32]表示，表示一个point 需要2个[u8;32]数组。
通过压缩算法，可用一个[u8;32]数组来表示point
(
x
,
y
)
(x,y)
(x,y)。具体的压缩算法为：
E
n
c
(
x
,
y
)
=
(
y
∣
x
<
<
255
)
Enc(x,y)=(y|x<<255)
Enc(x,y)=(y∣x
