前序博客有：
- Halo中的elliptic curve cycle
- Halo——zcash新的零知识证明机制，无需Trusted Setup
- Halo2学习笔记——背景资料之Elliptic curves（5）
本文主要考虑的是 Gallant等人2001年论文 Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms 中提到的曲线： E ( F p ) : y 2 = x 3 + b E(\mathbb{F}_p):\ y^2=x^3+b E(Fp): y2=x3+b 其中 p p p为素数，满足 p ≡ 1 m o d 3 p\equiv 1 \mod 3 p≡1mod3，即 3 ∣ p − 1 3|p-1 3∣p−1。 曲线 E ( F p ) E(\mathbb{F}_p) E(Fp)具有prime order q q q。该曲线上的所有非 O \mathcal{O} O点都称为 F p \mathbb{F}_p Fp-rational points ( x , y ) (x,y) (x,y)。取该曲线基点 G G G。 scalar multiplication [ k ] G [k]G [k]G 中的scalar值 k ∈ F q k\in\mathbb{F}_q k∈Fq。
1.1 endomorphism定义因 3 ∣ p − 1 3|p-1 3∣p−1，即 F p \mathbb{F}_p Fp 有 a primitive cube root of unity，若 ζ p ∈ F p \zeta_p\in \mathbb{F}_p ζp∈Fp为an element of order 3（即 ζ p 3 = 1 m o d p \zeta_p^3=1\mod p ζp3=1modp），则椭圆曲线 y 2 = x 3 + b y^2=x^3+b y2=x3+b上的point ( x , y ) (x,y) (x,y) 存在2个cousin points： ( ζ p x , y ) (\zeta_px,y) (ζpx,y)和 ( ζ p 2 x , y ) (\zeta_p^2x,y) (ζp2x,y)。
由于 ζ p 3 = 1 m o d p \zeta_p^3=1\mod p ζp3=1modp，有 o r d e r ( ζ p ) = 3 order(\zeta_p)=3 order(ζp)=3，以及 ζ p 2 + ζ p + 1 ≡ 0 m o d p \zeta_p^2+\zeta_p+1\equiv 0 \mod p ζp2+ζp+1≡0modp。
使用map ( x , y ) ↦ ( ζ p x , y ) (x,y)\mapsto (\zeta_px,y) (x,y)↦(ζpx,y)即为 应用an endomorphism over the curve，则对曲线 E ( F P ) E(\mathbb{F}_P) E(FP)的endomorphism定义为： ϕ ( x , y ) ↦ ( ζ p x , y ) , ϕ ( O ) = O \phi(x,y)\mapsto(\zeta_px,y), \phi(\mathcal{O})=\mathcal{O} ϕ(x,y)↦(ζpx,y),ϕ(O)=O 具有如下属性： ϕ ( P 1 + P 2 ) = ϕ ( P 1 ) + ϕ ( P 2 ) , ∀ P 1 , P 2 ∈ E ( F p ) \phi(P_1+P_2)=\phi(P_1)+\phi(P_2),\forall P_1,P_2\in E(\mathbb{F_p}) ϕ(P1+P2)=ϕ(P1)+ϕ(P2),∀P1,P2∈E(Fp) ( ϕ 2 + ϕ + 1 ) ( P ) = O , ∀ P ∈ E (\phi^2+\phi+1)(P)=\mathcal{O},\forall P\in E (ϕ2+ϕ+1)(P)=O,∀P∈E【因为 ( ϕ 2 + ϕ + 1 ) ( P ) = ϕ 2 ( P ) + ϕ ( P ) + 1 ( P ) = ( ζ p 2 x , y ) + ( ζ p x , y ) + ( x , y ) = ( − ζ p 2 x − ζ p x , − y ) + ( x , y ) = ( x , − y ) + ( x , y ) = O (\phi^2+\phi+1)(P)=\phi^2(P)+\phi(P)+1(P)=(\zeta_p^2x,y)+(\zeta_px,y)+(x,y)=(-\zeta_p^2x-\zeta_px,-y)+(x,y)=(x,-y)+(x,y)=\mathcal{O} (ϕ2+ϕ+1)(P)=ϕ2(P)+ϕ(P)+1(P)=(ζp2x,y)+(ζpx,y)+(x,y)=(−ζp2x−ζpx,−y)+(x,y)=(x,−y)+(x,y)=O】
若 ζ q ∈ F q \zeta_q\in\mathbb{F}_q ζq∈Fq为an element of order 3 （即 ζ q 3 = 1 m o d q \zeta_q^3=1\mod q ζq3=1modq，也即 ζ q 2 + ζ q + 1 ≡ 0 m o d q \zeta_q^2+\zeta_q+1\equiv 0 \mod q ζq2+ζq+1≡0modq），则有： ϕ ( P ) = ϕ ( x , y ) = [ ζ q ] P = ( ζ p x , y ) , ζ p ≡ 1 m o d p , ζ q 3 ≡ 1 m o d q , ∀ P ∈ E ( F p ) \phi(P)=\phi(x,y)=[\zeta_q]P=(\zeta_px,y),\zeta_p\equiv 1\mod p,\zeta_q^3\equiv 1\mod q, \forall P\in E(\mathbb{F}_p) ϕ(P)=ϕ(x,y)=[ζq]P=(ζpx,y),ζp≡1modp,ζq3≡1modq,∀P∈E(Fp)
对于任意的scalar值 k ∈ F q k\in\mathbb{F}_q k∈Fq，为计算scalar multiplication [ k ] P [k]P [k]P：
- 1）可将 k k k分解为 k = k 1 + k 2 ζ q m o d q k=k_1+k_2\zeta_q\mod q k=k1+k2ζqmodq
- 2）有 [ k ] P = [ k 1 ] P + [ k 2 ζ q ] P = [ k 1 ] P + [ k 2 ] Q [k]P=[k_1]P+[k_2\zeta_q]P=[k_1]P+[k_2]Q [k]P=[k1]P+[k2ζq]P=[k1]P+[k2]Q，从而转换为fixed point multiplication，可根据 P = ( x , y ) P=(x,y) P=(x,y)预计算 Q = ( ζ p x , y ) Q=(\zeta_px,y) Q=(ζpx,y)。
可借助endomorphism实现：
- 1）recursive zkSNARKs加速：实现partial proof verification
- 2）ECDSA验签加速
Halo论文中构建的ZKP算法，其Verifier保持为logarithmic-size state，并执行logarithmic-time operations来partially verify each proof in sequence。 在对a proof进行partial verification时，大部分的计算压力源自group operations。若选择任意的椭圆曲线 E E E over base field F p \mathbb{F}_p Fp，基于安全性考虑，该曲线的group order为素数 q q q，必然有 q ≠ p q\neq p q=p。为此，在构建ZKP时，是基于scalar field q \mathbb{q} q来表达arithmetic circuit satisfaction的，使得模仿另一域 F p \mathbb{F}_p Fp的计算将是昂贵的，从而成为ZKP协议中的一个效率挑战问题。为解决该效率问题，在Ben-Sasson等人2014年论文 Scalable Zero Knowledge via cycles of elliptic curves 中指出，可通过构建2-cycle curve E p , E q E_p,E_q Ep,Eq，其base field分别为 F p 和 F q \mathbb{F}_p和\mathbb{F}_q Fp和Fq，使得 # E p = q , # E q = p \#E_p=q, \#E_q=p #Ep=q,#Eq=p。
假设
r
⃗
∈
{
0
,
1
}
λ
\vec{r}\in\{0,1\}^{\lambda}
r
∈{0,1}λ为a verifier challenge，在 Halo论文 中，并不会直接将
r
⃗
\vec{r}
r
解析为a scalar值并对某
F
p
\mathbb{F}_p
Fp-rational point
P
P
P进行scalar multiplication运算，而是借助endomorphism属性，取一个基于
r
⃗
\vec{r}
r
生成的scalar值进行相应的运算，即在Halo论文中，将
[
r
⃗
]
P
[\vec{r}]P
[r
]P运算替换为了： 
该算法中，
r
⃗
\vec{r}
r
的每个bit，可以3.5个multiplication constraints来表示，当采用2-cycle curve，
λ
=
128
,
n
:
{
0
,
1
}
λ
↦
I
\lambda=128,n:\{0,1\}^{\lambda}\mapsto \mathbb{I}
λ=128,n:{0,1}λ↦I时，该算法等价为计算
[
n
(
r
⃗
)
]
P
[n(\vec{r})]P
[n(r
)]P： 
详细见博客 Acceleration of ECDSA Verification with Endomorphism Mapping of secp256k1，借助secp256k1的endomorphism属性，ECDSA验签速度提升了约40%。
参考资料[1] About the endomorphism-based optimization in halo [2] Acceleration of ECDSA Verification with Endomorphism Mapping of secp256k1 [3] Gallant等人2001年论文 Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms
