Halo中的elliptic curve cycle

1. 引言

Bowe等人2019年论文《Halo: Recursive Proof Composition without a Trusted Setup》。

该论文中的部分verification operation是由group operation主导的。若使用任意的elliptic curve E E E over base field F p \mathbb{F}_p Fp​，则考虑安全因素，得要求group的prime order q ≠ p q\neq p q​=p。本文协议需要基于scalar field F q \mathbb{F}_q Fq​来表达arithmetic circuit satisfaction，而模拟 F p \mathbb{F}_p Fp​ arithmetic over a distinct field is expensive。 Ben-Sasson等人2014年论文《Scalable Zero Knowledge via cycles of elliptic curves》中指出，通过寻找“2-cycle” E p , E q E_p,E_q Ep​,Eq​ of elliptic curves，来分别构建base fields F p \mathbb{F}_p Fp​和 F q \mathbb{F}_q Fq​，其中 # E p = q \#E_p=q #Ep​=q、 # E q = p \#E_q=p #Eq​=p。这样就允许proofs constructed using the group E p E_p Ep​ to efficiently reason about proofs constructed over E q E_q Eq​，反之亦然，as the group operations needed to verify proofs consist of operations in each proving system’s native field。 与Ben-Sasson中寻找pairing-friendly elliptic curve groups不同，Halo论文中寻找的是普通的（非pairing-friendly的）secure 2-cycle elliptic curves。

参看博客 FFT rust代码实现 中指出，为了能用FFT来做多项式乘法，factor(p-1) = 2^s*t，其中的2^s值代表允许的多项式的最高阶数。generator=primitive_root(p)【generator为 ( p − 1 ) (p−1) (p−1)-th root of unity，有限域内任意 x x x，其 x ( p − 1 ) = 1 x^{(p-1)}=1 x(p−1)=1恒成立】， 2 s 2^s 2s-th root of unity的计算方式为power_mod(generator, t, p)。而Curver25519的scalar field Fr的s值仅为2且generator无返回（无论是基于magma还是sagemath）。所以在需要表示多项式相乘的场景下，其并不适用。

本文需要查找：

• 具有高 s s s值的scalar field 曲线（ f a c t o r ( p − 1 ) = 2 1 s ∗ t 1 , f a c t o r ( q − 1 ) = 2 2 s ∗ t 2 factor(p-1)=2^s_1*t_1, factor(q-1)=2^s_2*t_2 factor(p−1)=21s​∗t1​,factor(q−1)=22s​∗t2​），以便于可使用radix-2 FFTs来加速多项式乘积运算。
• 两条曲线应有field elements 的multiplicative order为3，即需满足 f a c t o r ( p − 1 ) = 2 1 s ∗ 3 ∗ t 1 , f a c t o r ( q − 1 ) = 2 2 s ∗ 3 ∗ t 2 factor(p-1)=2^s_1*3*t_1, factor(q-1)=2^s_2*3*t_2 factor(p−1)=21s​∗3∗t1​,factor(q−1)=22s​∗3∗t2​，以便可使用curve endomorphisms来优化circuit。
• 要求 g c d ( p − 1 , 5 ) = g c d ( q − 1 , 5 ) = 1 gcd(p-1,5)=gcd(q-1,5)=1 gcd(p−1,5)=gcd(q−1,5)=1，以便允许实例化the Rescue hash function with α = 5 \alpha=5 α=5。

最终找到的2-cycle 曲线为Tweedledum和Tweedledee：（构建细节参见 https://github.com/daira/tweedle）

sage: p=2^254+4707489545178046908921067385359695873
sage: q=2^254+4707489544292117082687961190295928833
sage: factor(p-1)
2^33 * 3 * 5179 * 216901160674121772178243990852639108850176422522235334586122689
sage: factor(q-1)
2^34 * 3 * 4322432633228119 * 129942003317277863333406104563609448670518081918257
sage: gcd(p-1,5)
1
sage: gcd(q-1,5)
1

Tweedledum和Tweedledee具有126-bit security against Pollard rho attacks，其中已考虑了the additional endomorphisms可能可用于加速Pollard rho和discrete log algorithms的影响。

目前，基于Tweedledum和Tweedledee的加法运算还有缺陷：如无法add two points with the same x x x-coordinate。在实际使用时，要注意做相应的加法判断。根据 ZCash Issue 3924 – Faster variable-base scalar multiplication in zk-SNARK circuits 中讨论指出，实际circuit中的运算以scalar multiplication为主，小心调用加法运算的话，仍可满足要求。基于其它场景使用Tweedledum和Tweedledee的有缺陷加法运算时，需要额外注意。 constant-time formulae for prime-order short Weierstrass curves可参考[34][35]论文进行实现。 recommend that fault attacks on the prover be addressed by validating the proof immediately after creating it。

注意： https://github.com/zcash/halo2/ 中实现的才是Tweedledum和Tweedledee曲线。 https://github.com/ebfull/halo 中实现的是另外的曲线，具体参见 博客Halo——zcash新的零知识证明机制，无需Trusted Setup 第2.1节的Sage脚本。 2. 基于Endomorphism的优化

Tweedledum和Tweedledee曲线具有endomorphism属性： ϕ ( ( x , y ) ) = ( ζ p x , y ) \phi((x,y))=(\zeta_p x,y) ϕ((x,y))=(ζp​x,y)，其中 ϕ ( P ) = ϕ ( ( x , y ) ) = [ ζ q ] P \phi(P)=\phi((x,y))=[\zeta_q]P ϕ(P)=ϕ((x,y))=[ζq​]P。 具体表示为如下sage脚本中的ZETA_Q*P==E0(ZETA_P*P_X,P_Y)和ZETA_P*Q==E1(ZETA_Q*Q_X,Q_Y)。

sage: p=2^254+4707489545178046908921067385359695873
sage: q=2^254+4707489544292117082687961190295928833
sage: E0=EllipticCurve(GF(p),[0,0,0,0,5])
sage: E1=EllipticCurve(GF(q),[0,0,0,0,5])
sage: p==E1.cardinality()
True
sage: q==E0.cardinality()
True
sage: P=E0.random_point()
sage: P
(25415224292215053840310240764851735169556717411553406219487045218995850661949 : 4829591991374067821915488208957431679276929647073667653556404306802668725390 : 1)
sage: P_X=P[0]
sage: P_X
25415224292215053840310240764851735169556717411553406219487045218995850661949
sage: P_Y=P[1]
sage: P_Y
4829591991374067821915488208957431679276929647073667653556404306802668725390
sage: ZETA_P=0x1508415ab5e97c949bebc9146ef83d9a7881fb239ba41a268598abb3a410c9c8
sage: ZETA_Q=0x36c66d3a1e049a5887ad8b5ff9731ffe69cf8de720e52ec14394c2bd148fa4fd
sage: ZETA_Q*P==E0(ZETA_P*P_X,P_Y)
True
sage:
sage: Q=E1.random_point()
sage: Q
(5773639204296723226175041348081614707458447404838782763177823928351008544900 : 25210718496048380236355065626215601675438375804308336026355938934156423688663 : 1)
sage: Q_X=Q[0]
sage: Q_Y=Q[1]
sage: Q_X
5773639204296723226175041348081614707458447404838782763177823928351008544900
sage: Q_Y
25210718496048380236355065626215601675438375804308336026355938934156423688663
sage: ZETA_P*Q==E1(ZETA_Q*Q_X,Q_Y)
True
sage:

也就是说，verifier challenge r ∈ { 0 , 1 } λ r\in\{0,1\}^{\lambda} r∈{0,1}λ，与直接将 r r r解析为a scalar然后perform a scalar multiplication of a F p \mathbb{F}_p Fp​-rational point P P P不同，借助endomorphism特性，借助如下算法来multiply by a scalar that is dependent on r r r： https://github.com/zcash/halo2/中相应算法代码实现为：【注意 r 2 i , r 2 i + 1 ∈ { 0 , 1 } r_{2i},r_{2i+1}\in \{0,1\} r2i​,r2i+1​∈{0,1}，所以 S i ∈ { P , − P , ϕ ( P ) , ϕ ( − P ) } S_i\in\{P,-P,\phi(P),\phi(-P)\} Si​∈{P,−P,ϕ(P),ϕ(−P)}，其中 ϕ ( − P ) = [ − ζ q ] P \phi(-P)=[-\zeta_q]P ϕ(−P)=[−ζq​]P】

/// This algorithm applies the mapping of Algorithm 1 from the
/// [Halo](https://eprint.iacr.org/2019/1021) paper.
pub fn get_challenge_scalar(challenge: Challenge) -> F {
    let mut acc = (F::ZETA + F::one()).double();

    for i in (0..64).rev() {
        // 若r_{2i}=0,则 should_negate=true；否则should_negate=false。
        // 若r_{2i+1}=0，则should_endo=false；否则should_endo=true。
        let should_negate = ((challenge.0 >> ((i > (i