区块链中的数学 - Baby Jubjub Elliptic Curve

  • blocksight
  • 更新于 2021-08-01 11:01
  • 阅读 4434

本文将介绍一种新的椭圆曲线实例-- Baby Jubjub Elliptic Curve。

写在前面

上一篇介绍了plookup协议核心思想,本文将介绍一种新的椭圆曲线实例-- Baby Jubjub Elliptic Curve。

定义

验证zk-SNARK proof需要使用椭圆曲线配对操作,以太坊中使用了BN254(alt_bn128)曲线,阶是素数r, 可以生成并验证F_r域内的运算电路证明。 Baby Jubjub Elliptic Curve 直接定义在有限域F_r上, 应用于Fr范围算术电路中,包括一些密码学原语实现过程( Pedersen 哈希等)。

曲线参数

方程:扭曲爱德华曲线方程$ax^2+y^2=1+dx^2y^2$

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

方程参数:

a = 168700 d = 168696

阶n = 21888242871839275222246405745257275088614511777268538073601725287587578984328 n = h x l 其中h = 8 ,l = 2736030358979909402780800718157159386076813972158567259200215660948447373041

基点G = (x,y): x = 995203441582195749578291179787384436505546430278305826713579947235728471134 y = 5472060717959818805561601436314318772137091100104008585924551046643952123905

子群l生成元B = (x,y): x = 5299619240641551281634865583518297030282874472190772894086521144482721001553 y = 16950150798460657717958625567821834550301663161624707787222815936182638968203

P + Q

Baby Jubjub任意两点P1 = (x1, y1), P2 = (x2, y2) , P1 + P2 = (x3, y3) 如下计算:

x3 = (x1y2 + y1x2)/(1 + dx1x2y1y2) y3 = (y1y2 - ax1x2)/(1 - dx1x2y1*y2)

就是扭曲爱德华曲线的运算规则,注意不需要区分两点是否相同。

Montgomery形式及转换

扭曲爱德华曲线双向有理映射到Montgomery形式,可以用Montgomery方程式:$By^2=x^3+Ax^2+x$ 其中A = 168698, B = 1, G = (7, 4258727773875940690362607550498304598101071202821725296872974770776423442226)

子群基点B = (7117928050407583618111176421555214756675765419608405867398403713213306743542, 14577268218881899420966779687690205425227431577728659819975198491127179315626)

两种形式可以相互转换(双向有理映射):

令(u, v) 表示Montomgery 点,(x, y) 扭曲爱德华曲线点,

Montgomery –> Twisted Edwards:(u, v) --> (x, y)

x = u/v y = (u-1)/(u+1)

Twisted Edwards –> Montgomery: (x, y) --> (u, v)

u = (1+y)/(1-y) v = (1+y)/((1-y)x)

小结

本文介绍Baby Jubjub椭圆曲线基本知识,作为一个knowledge base使用,是为zk snark电路设计友好的曲线,工程实现已有Rust,Js,Solidity等,可在参考文中找到Git地址。本文参考: https://eips.ethereum.org/EIPS/eip-2494 https://iden3-docs.readthedocs.io/en/latest/_downloads/33717d75ab84e11313cc0d8a090b636f/Baby-Jubjub.pdf


原文链接:https://mp.weixin.qq.com/s/NIfhpO1vKlsdfod5YJNYkw 欢迎关注公众号:blocksight


相关阅读

区块链中的数学(四十七) 扭曲爱德华曲线

区块链中的数学 -- MultiSet check& Schwartz–Zippel lemma MultiSet check& Schwartz–Zippel lemma

相关plonk系列视频

区块链中的数学 -盲签名(Blind Signature) 盲签名原理

区块链中的数学 - RSA累加器的非成员证明 RSA Accumulator非成员证明以及区块链应用

区块链中的数学 - Kate承诺batch opening Kate承诺批量证明

区块链中的数学 - 多项式承诺 多项式知识和承诺

区块链中的数学 - Pedersen密钥共享 Pedersen 密钥分享

区块链中的数学 - Pedersen承诺 密码学承诺--Pedersen承诺

区块链中的数学 - BLS门限签名 BLS m of n门限签名

区块链中的数学 - BLS密钥聚合 BLS密钥聚合

区块链中的数学-Uniwap自动化做市商核心算法解析 Uniwap核心算法解析(中)

点赞 0
收藏 2
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
blocksight
blocksight
江湖只有他的大名,没有他的介绍。