[ERC2494] zk-SNARK回路で高速動作するBaby Jubjub曲線の仕組みを理解しよう！

はじめに

『DApps開発入門』という本や色々記事を書いているかるでねです。

今回は、Ethereumの zk-SNARK 回路内で楕円曲線暗号を安全かつ効率的に利用するために、「Baby Jubjub」を提案しているERC2494についてまとめていきます！

以下にまとめられているものを翻訳・要約・補足しながらまとめていきます。

ERC-2494: Baby Jubjub Elliptic CurveEthereum Improvement Proposals

他にも様々なEIPについてまとめています。

Notion | Where teams and agents work togetherMade in Notion, the connected workspace where AI agents and teams organize docs, projects and knowledge together.Notion

概要

ERC2494では、Ethereumのzk-SNARK回路内で利用できる新しい楕円曲線「Baby Jubjub」を定義しています。現在Ethereumではzk-SNARKの検証に alt_bn128（BN254）曲線を使用していますが、この曲線はzk-SNARK証明の生成・検証には適している一方で、zk-SNARK回路の内部で楕円曲線暗号を実装することはできません。 Baby Jubjub は、BN254 の素数階 $r$ 上に定義された楕円曲線であり、回路内部で楕円曲線ベースの暗号処理（例：Pedersen ハッシュや EdDSA 署名）を可能にします。これにより、Ethereum のスマートコントラクトでゼロ知識証明を活用した高度な暗号機能を構築できるようになります。

動機

ブロックチェーンが広く利用されない要因のひとつに、スケーラビリティ（処理能力）とプライバシー（取引内容の秘匿）の課題があります。ゼロ知識証明（ZKP）を用いれば、これらの課題を同時に解決することが可能です。特に zk-SNARK は以下の特徴を持ち、Ethereum上での利用に適しています。

非対話型（やり取りが一度で完結）
証明サイズが非常に小さい
検証が高速

スマートコントラクトは zk-SNARK の検証者として機能できるため、誰でもオフチェーンで証明を作成してトランザクションとして送ることで、コントラクトが自動的に検証を行い結果に応じた処理を実行できます。これにより、プライバシー保護やスケーラビリティの向上が期待されます。

しかし、既存のEthereumの zk-SNARK 実装に使われる BN254 曲線は、証明検証には対応しているものの、回路内部での楕円曲線演算（Pedersen ハッシュや EdDSA 署名など）には使えません。これは、内部演算に必要な曲線が、zk-SNARK 回路と同じ有限体 $F_r$ 上に定義されていないためです。そこで提案されたのが Baby Jubjub です。この曲線は $F_r$ 上に定義されており、zk-SNARK 回路内部での楕円曲線暗号処理を可能にします。結果として、zk-Rollupのようなスケーラビリティ向上技術や、秘密情報を保護したトランザクション処理など、より高度なZKP活用が可能になります。

仕様

定義

Baby Jubjub は、有限体 $F_r$ 上に定義された「**ねじれ Edwards 曲線（twisted Edwards curve）`」です。有限体 $F_r$ とは、 $r$ 個の要素を持つ素数位数の有限集合であり、四則演算がすべて定義されています。この提案では、以下の非常に大きな素数を採用しています。

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

曲線は以下の式で表されます。

a x^2 + y^2 = 1 + d x^2 y^2

ここで $a = 168700$ 、 $d = 168696$ です。この曲線上の $F_r$ 上での有理点（座標が $F_r$ の元である点）の集合が Baby Jubjub です。

曲線の位数（Order）

Baby Jubjub 曲線上の全ての点の集合は、以下の位数（点の総数）を持ちます。

n = 21888242871839275222246405745257275088614511777268538073601725287587578984328

この $n$ は以下のように因数分解されます。

n = h \times l

ここで、コファクタ $h$ は、位数 $n$ を素数 $l$ で割ったときの倍率であり、曲線の構造上の性質を示します。

$h = 8$ （コファクタ）
$ l = 2736030358979909402780800718157159386076813972158567259200215660948447373041$（251ビットの素数）

ジェネレーターポイント（Generator Point）

曲線全体の $n$ 個の点を生成できる点 $G$ が定義されています。

G_x = 995203441582195749578291179787384436505546430278305826713579947235728471134

G_y = 5472060717959818805561601436314318772137091100104008585924551046643952123905

この点から反復的に加算を行うことで、曲線上のすべての点を得られます。

ベースポイント（Base Point）

曲線の部分集合の中で、位数 $l$ の点（ $l \times P = O$ を満たす点）を生成する基準点 $B$ も定義されています。

B_x = 5299619240641551281634865583518297030282874472190772894086521144482721001553

B_y = 16950150798460657717958625567821834550301663161624707787222815936182638968203

この点は、暗号アルゴリズム（例：EdDSA）の基準として利用されます。

演算方法（Arithmetic）

Baby Jubjub 上の点同士の加算は、座標 $(x_1, y_1)$ 、 $(x_2, y_2)$ を用いて以下の式で計算されます。

x_3 = \frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2}

y_3 = \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2}

この式は加算と倍算の両方に使えるため、計算実装が簡略化されます。また、すべての演算は有限体 $F_r$ 上で行われます。

この仕様によって、Baby Jubjub は zk-SNARK 回路内部で効率的かつ安全に楕円曲線演算を行える基盤となります。特にPedersenハッシュや EdDSA のような暗号処理において、Ethereumの既存の alt_bn128 では不可能だった機能を実現できるようになります。

補足

Baby Jubjub の設計は、zk-SNARK の回路内部で楕円曲線暗号を安全かつ効率的に実装するために行われました。曲線の選定では「曲線の形式」、「生成プロセス」、「安全性基準」という3つの要素が重視されています。

曲線の形式

Baby Jubjub は「ねじれ Edwards 曲線（twisted Edwards curve）」であり、これはモンゴメリ曲線（Montgomery curve）と有理同値（birationally equivalent）です。この形式が選ばれた理由は以下の通りです。

まず、EdDSA（Edwards-curve Digital Signature Algorithm）は twisted Edwards 曲線を基盤としており、この形式を採用することで署名アルゴリズムの実装が容易になります。さらに、twisted Edwards 曲線は点の加算に「完全な1つの計算式」を利用できるため、回路内での群演算が非常に効率的に行えます。また、この曲線はモンゴメリ曲線に変換可能であり、モンゴメリ形式では点の加算や倍算をさらに高速に行えます。そのため、回路外での計算はモンゴメリ形式で行い、回路内では twisted Edwards 形式で効率化する、といった使い分けが可能になります。

曲線の生成プロセス

Baby Jubjub は、暗号プロトコルにおいて重要な「バックドア（意図的な脆弱性）を排除する」ため、生成過程を透明かつ決定的（deterministic）に設計しています。この生成プロセスはRFC7748の付録A.1で定義されている条件に基づき、誰でも再現できる手順で実行されました。具体的には、素数 $p \equiv 1 \mod 4$ を入力として、以下の条件を満たす最小の $A > 0$ を探索します。

$A - 2$ が4の倍数
コファクタ8のモンゴメリ曲線 $y^2 = x^3 + Ax^2 + x$ が得られる

今回の入力は、Ethereumが zk-SNARK 検証で使用している alt_bn128 曲線の位数であり、この計算結果から $A = 168698$ が得られました。

r = 2188824287\ldots95617

これをモンゴメリ形式から twisted Edwards 形式へ変換し、SAGEライブラリを使って位数 $n = 8 \times l$ を確認しました。

生成された曲線から、位数 $n$ の点で最小の正の $x$ 座標を持つ点をジェネレータ $G$ として選び、ベースポイント $B$ は $B = 8 \times G$ として位数 $l$ を持つ点としました。

安全性基準

Baby Jubjub は、既知の楕円曲線攻撃手法に対して安全であることが求められます。そのため、この曲線はSafeCurvesプロジェクトの安全性基準を満たすことが条件とされました。SafeCurvesは楕円曲線に対する既知の最良の攻撃手法を網羅的にテストする基準として知られており、Baby Jubjub がこの基準を満たしていることが確認されています。

互換性

Baby Jubjub は「**ねじれ Edwards 曲線（Twisted Edwards）((」ですが、この曲線は数学的に別の曲線形式に変換（有理同値変換）することができます。これまで Baby Jubjub は主に3つの形式で利用されてきました。

標準の Twisted Edwards 形式
Montgomery 形式
簡約 Twisted Edwards 形式（Reduced Twisted Edwards Form）

これらは同じ曲線を異なる座標系で表現したものであり、相互に変換するための明確な数式（変換式）が定義されています。

曲線の3つの形式

`Twisted Edwards` 形式（標準）

方程式は以下の形です。

a x^2 + y^2 = 1 + d x^2 y^2

パラメータは $a = 168700$ 、 $d = 168696$ です。この形式は Baby Jubjub の標準的な表現で、ジェネレータポイント（全ての点を生成できる点）と、位数 $l$ の部分群を生成するベースポイントが定義されています。

`Montgomery` 形式

方程式は次以下の形です。

B y^2 = x^3 + A x^2 + x

パラメータは $A = 168698$ 、 $B = 1$ です。 Montgomery 形式は楕円曲線演算（特に倍算）を効率的に行えるため、回路外での計算や一部のアルゴリズムに向いています。

簡約 `Twisted Edwards` 形式

方程式は以下の形です。

a' x^2 + y^2 = 1 + d' x^2 y^2

パラメータは $a' = -1$ 、であり、標準形式の座標をスケーリングした表現です。この形式は一部の暗号アルゴリズムで効率向上のために利用されます。

d' = 12181644023421730124874158521699555681764249180949974110617291017600649128846

形式間の変換

3つの形式は座標変換によって相互に変換可能です。変換時には、Montgomery 形式の座標を $(u, v)$ 、標準 Twisted Edwards 形式を $(x, y)$ 、簡約 Twisted Edwards 形式を $(x', y')$ として扱います。

変換の中でスケーリング係数 $f$ が用いられる場合があります。

f = 6360561867910373094066688120553762416144456282423235903351243436111059670888

負の値は以下の通りです。

-f = 15527681003928902128179717624703512672403908117992798440346960750464748824729

主な変換は以下の通りです。

Montgomery → Twisted Edwards

x = u / v,\quad y = (u - 1) / (u + 1)

Twisted Edwards → Montgomery

u = (1 + y) / (1 - y),\quad v = (1 + y) / ((1 - y)x)

Montgomery → 簡約 Twisted Edwards

x' = u \cdot (-f) / v,\quad y' = (u - 1) / (u + 1)

簡約 Twisted Edwards → Montgomery

u = (1 + y') / (1 - y'),\quad v = (-f) \cdot (1 + y') / ((1 - y') x')

Twisted Edwards → 簡約 Twisted Edwards

x' = x \cdot (-f),\quad y' = y

簡約 Twisted Edwards → Twisted Edwards

x = x' / (-f),\quad y = y'

このように Baby Jubjub は、同じ数学的構造を保ちながら複数の形式に変換でき、利用するアルゴリズムや実行環境に応じて最適な形式を選択することができます。これにより、回路内外での処理効率を高めつつ、既存の実装や異なるライブラリとの互換性も確保できます。

セキュリティ

Baby Jubjub の安全性は、楕円曲線暗号の安全基準として広く知られるSafeCurvesの評価基準に基づいて検証されています。この基準は、既知の攻撃手法に対する耐性や、暗号実装における安全性の確保を目的としています。以下では、Baby Jubjub に対して行われた主要な安全性チェックを解説します。

曲線パラメータの検証

まず、仕様に記載されているパラメータが有限体 $F_r$ 上で有効な楕円曲線を定義していることを確認しています。具体的には、以下の条件を満たすことが検証されています。

$r$ が素数であること。
$a$ および $d$ の値が、楕円曲線の方程式を正しく定義すること。
コファクタ $h$ と素数 $l$ の積が曲線の位数 $n$ に等しいこと。
ジェネレータポイント $G$ が曲線全体の生成元であること。
$l$ が素数であり、ベースポイント $B$ の位数が $l$ であること。

離散対数問題の難易度

楕円曲線暗号の安全性は、楕円曲線離散対数問題（ECDLP）の難しさに依存します。 Baby Jubjub では、以下の既知の攻撃手法に対して十分な耐性があることが確認されています。

Rho 法
- 計算コストが $0.886 \times \sqrt{l}$ 回の加算であり、その計算量が $2^{100}$ 以上になること。
加法的・乗法的移転攻撃
- 埋め込み次数（embedding degree）が少なくとも $(l - 1) / 100$ 以上であること。
高判別式攻撃
- 複素乗法体の判別式 $D$ が $2^{100}$ より大きいこと。

楕円曲線暗号実装における安全性

Baby Jubjub は、暗号実装に必要な各種安全性要件も満たしています。

Montgomery Ladder
- 安全なスカラー倍算手法であるMontgomery Ladderをサポートし、サイドチャネル攻撃への耐性を確保しています。
Twist 安全性
- 小さな部分群攻撃、無効曲線攻撃、ツイスト攻撃に対して安全です。
完全性（Completeness）
- 加算や倍算の計算式が「完全式（complete formula）」であり、入力によって例外が発生しないことを確認しています。
識別不能性（Indistinguishability）
- 楕円曲線上の点を、ランダムな文字列と区別できない形に変換できる写像が利用可能であること。

引用

Barry WhiteHat (@barryWhiteHat), Marta Bellés (@bellesmarta), Jordi Baylina (@jbaylina), "ERC-2494: Baby Jubjub Elliptic Curve [DRAFT]," Ethereum Improvement Proposals, no. 2494, January 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2494.