您当前的位置: 首页 > 

mutourend

暂无认证

  • 3浏览

    0关注

    661博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

zcash的Jubjub

mutourend 发布时间:2019-06-18 19:05:54 ,浏览量:3

参考资料: [1] https://z.cash/technology/jubjub [2]https://github.com/zkcrypto/jubjub

Curve DescriptionJubjub is the twisted Edwards curve -u2 + v2 = 1 + d.u2.v2 of rational points over GF(q) with a subgroup of prime order r and cofactor 8.

q = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
r = 0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb7
d = -(10240/10241)

The choice of GF(q) is made to be the scalar field of the BLS12-381 elliptic curve construction.Jubjub is birationally equivalent to a Montgomery curve y2 = x3 + Ax2 + x over the same field with A = 40962. This value of A is the smallest integer such that (A - 2) / 4 is a small integer, A2 - 4 is nonsquare in GF(q), and the Montgomery curve and its quadratic twist have small cofactors 8 and 4, respectively. This is identical to the relationship between Curve25519 and ed25519.

Jubjub is a twisted Edwards curve of the form −x2+y2=1+dx2y2 built over the BLS12-381 scalar field, with d=−(10240/10241). Being a twisted Edwards curve, it has a complete addition law that avoids edge cases with doubling and identities, making it convenient to work with inside of an arithmetic circuit. 在这里插入图片描述

Rather than reaching for projective coordinate systems, we can leverage the fact that field inversion is “as cheap” as field multiplication inside of the zk-SNARK circuit to apply the law directly. Additionally, multiplication by constants (as in fixed-base exponentiation) is virtually free. We can leverage these properties to express conditional addition (over b) by known (x2,y2) in just five quadratic constraints: 在这里插入图片描述 In practice, we need to boolean constrain each bit of the scalar, giving a total of around 1506 multiplication gates with a scalar size of 251 bits. This is roughly 6 constraints per bit, as in Kosba(previously explored fixed-base exponentiation performance inside of zk-SNARK circuits, achieving performance of 6 constraints per bit of the scalar) et al…

It turns out that we can do better than this. Instinctively it would seem that windowed exponentiation would be expensive in this context, because you would have to resort to general point additions… 在这里插入图片描述 … in addition to a window table lookup, and the boolean constraints of the scalar bits. Constant window table lookups inside the circuit can be achieved using polynomials which vanish at the constants that aren’t being selected. As an example, given the table of constants (c0,c1,c2,c3) with bits b0 and b1, and the selected constant r can be evaluated with the constraint: 在这里插入图片描述 This technique can be applied for larger window tables, but the multiplicative depth of the evaluation increases exponentially. There happens to be a sweet spot at a window table of 4, which allows us to achieve approximately 4.2 constraints per bit.

在这里插入图片描述

关注
打赏
1664532908
查看更多评论
立即登录/注册

微信扫码登录

0.0378s