Loading...
シリーズ: Zcashの第一原理から . 記事2 . 楕円曲線 対象読者: 新規参入者。記事1（有限体）で紹介された、素数を法とする算術のみを仮定します。他の背景知識は不要です。 得られるもの: 楕円曲線の直感的かつ正確なイメージ、それらが有用になる「トラップドア」、そしてZcashがそれらを鍵とコミットメントにどのように変換するか。
記事1は算術のための完璧な遊園地として有限体を提供しました。しかし、単なる数値の場では、鍵や記事0で紹介された「封筒」を作成するには不十分です。Zcashは、特定の一種の片道性を持つオブジェクトが必要です：前向きに計算するのは簡単ですが、逆向きにすることは実質的に不可能です。そのオブジェクトが楕円曲線です。この記事では、代数よりも直感から構築し、説明します。
すべてのプライバシー系システムは片道の通りが必要です：前向きに進むのは簡単で、逆向きに進ぶことは実質的に不可能な操作です。
その理由を以下に示します。あなたの秘密鍵は隠す必要のある数値です。あなたの公開鍵（およびアドレス）はそれから導出され、世界中に公開されます。システム全体のセキュリティは1つの事実に依存しています：公開鍵が与えられても、誰も秘密鍵に戻ることはできない。もしできれば、あなたの資産を無断で使用できるようになります。
したがって、以下のような数学的操作が必要です：
単純な有限体の乗算では十分ではありません；除算で即座に逆転されます（それが記事1の目的でした）。何か「元に戻す」ボタンがないものが必要です。楕円曲線はまさにそれであり、加えてその点がコミットメントを構築するのに最適な方法で組み合わさっています。ではどうやって実現しているのか見てみましょう。
暗号学を一時忘れてください。楕円曲線とは、以下の式を満たす点(x, y)の集合です：
y^2 = x^3 + ax + b
普通の数値では滑らかで湾曲した曲線に見え、多くの場合、丸いループと二つの尾を持つことがあります：
驚くべき点はここです：この曲線上の2つの点を加算して、同じ曲線上の3つ目の点を得ることができる。これは通常の座標の加算ではありません。幾何学的なルールであり、言葉よりも視覚的に理解しやすいものです。
P + Qを加算するには：
PとQを通る直線を描きます。R*と呼びます。R*を反転させます。この反射が答えです、P + Q。
P + P（2Pと書く）を計算するには、もう一つの点がないため、代わりにPでの接線を使用し、その後も「第3交点、そして反転」のレシピに従います。
これが全体の操作です。二つの幾何学的なルールだけです。それにより、楕円曲線上の点は数学的に**群（group）**と呼ばれる構造を形成します：よく振る舞う「加算」を持つ集合で、ゼロも存在します。
すべての数値システムには0が必要です。これは加算しても何も変化しないものです。楕円曲線上では、特別な追加の点である無限遠点(O)がその役割を果たします。それを「無限に上にある」と想像し、垂直線が交わる場所と見なすことができます。Oを任意の点に加算しても変化しません。これは0と同じです。
上の滑らかな曲線は直感です。しかしZcashは実数を使用していません（それらは丸められ、サイズが漏れると記事1で述べました）。代わりに、有限体上での楕円曲線を使用します：同じ式y^2 = x^3 + ax + bですが、すべての算術は素数を法として行われます。
そうすると、美しい曲線は分離した点の散らばりに崩れます。それぞれ(x, y)が方程式mod pを満たす点ごとに1つの点があります。曲線のような見た目は完全に失われますが、重要なのは以下の点です：
弦と接線ルールの代数は依然として完璧に機能します。同じ式で幾何的に
P + Qを求めたものが今や有限体算術を使って計算されます。点は依然として群を形成し、同じ0（無限遠点）を持っています。
小さな完全な例を使って実際に確認しましょう。
y^2 = x^3 + 2x + 2を有限体F_17上にとります。すべての有効な点を計算すると、18点があり、無限遠点を加えると合計で19点になります。いくつかは以下の通りです：
(0,6) (0,11) (3,1) (3,16) (5,1) (5,16) (6,3) (6,14) (7,6) (7,11) ...
今、点G = (5, 1)を選び、それを自分自身に繰り返し加算してみましょう。以下は実際に計算された結果です（推測ではなく）：
| ステップ | 点 | ステップ | 点 |
|---|---|---|---|
1G | (5, 1) | 11G | (13, 10) |
2G | (6, 3) | 12G | (0, 11) |
3G | (10, 6) | 13G | (16, 4) |
4G | (3, 1) | 14G | (9, 1) |
5G | (9, 16) | 15G | (3, 16) |
6G | (16, 13) | 16G | (10, 11) |
7G | (0, 6) | 17G | (6, 14) |
注意すべき2つの点：
Oに到達し、その後永遠に繰り返す。開始点Gは全体の群を生成するので、「ジェネレータ」と呼ばれる。1G + 2G = (5,1) + (6,3) = (10,6)、これは正確に3Gです。加算は内部的に一貫しており、群が要求する通りです。1G, 2G, 3G, ...という表がすべての中心です。点を自分自身に繰り返し加算することをスカラー倍算と呼びます：点kGは"Gを自分自身にk回加算"を意味します。
今、魔法の時間です。2つの方向を比較してみましょう：
| 方向 | 質問 | 難易度 |
|---|---|---|
| 前向き | kとGが与えられたらkGを計算する | 簡単。天文的な巨大なkでも、double-and-addというトリックで数百ステップで到達可能 |
| 逆向き | GとkGが与えられたらkを復元する | 実質的に不可能。現実の暗号曲線上では |
この非対称性はセクション1で必要とした片道の通りです。逆方向の問題（「どのkがこの点を作ったか？」）は**楕円曲線離散対数問題（ECDLP）**と呼ばれ、Zcashが使用する曲線上では宇宙の熱死以前に解決法が見つかることはないということが知られています。
我々の玩具
F_17曲線では表からkを読み取ることができた。なぜなら、そこには19点しかないからです。現実の曲線は約2^(255)点を持っています。表の行数は宇宙にある原子の数より多くなりますので、「読み取る」ことは不可能です。この小ささが玩具曲線を学びやすくする理由であり、同時にセキュリティに不適切な理由でもあります。
これで、実際の暗号鍵を説明するために必要なすべての要素を持っています。驚くほど簡単です：
秘密の数
kを選択し、点kGを公開するだけ。kはあなたのプライベートキー。kGはあなたのパブリックキー。片道の通り（ECDLP）により、誰もkGからkに戻ることはできないことが保証されています。
この単純なアイデア、「パブリックキーは固定されたジェネレータに秘密スカラーをかけたもの」というのは、Zcashの支出鍵、ビューングキー、アドレスの種です。完全なキーツリーはさらに構造を追加しますが、すべての枝はこの根から伸びています。
記事0で紹介された「封筒」（コミットメント）は内容を隠しながらも作成を偽装できない必要がありました。楕円曲線はそのようなものを簡単に構築する方法を提供します。2つの固定されたパブリックジェネレータ点GとH、秘密値v、ランダムなブラインド数rを取り、以下のように形成します：
Commitment = v.G + r.H
これはペドレンスコミットメントであり、求めた2つの性質を備えています：
rは結果を全体の曲線に広げるので、点はvについて何の情報をも明らかにしません。(v, r)を見つけることは不可能なので、コミットした内容を変更することはできません。この性質の一つが後で非常に価値あるものになります：これらのコミットメントは加算可能です。v_1へのコミットメントとv_2へのコミットメントを加えると、v_1 + v_2への有効なコミットメントになります。この「ホモモルフィック」の性質により、Zcashは後で取引に入る金額が出ていく金額と等しいことを証明できますが、どの金額も明らかにしません。これは記事6で詳しく説明します。
指紋は具体的かつ検証可能です。
| Zcashの設計 | 使用する曲線 | 役割 |
|---|---|---|
| Sapling（古い） | BLS12-381と埋め込まれた曲線Jubjub | BLS12-381は証明システムを担い、JubjubはBLS12-381のスカラー場上に構築されており、ゼロ知識証明内で鍵やコミットメント操作が安価に行えるようにする |
| Orchard（現在） | PallasとVesta（「Pasta」サイクル） | PallasはOrchardの鍵とコミットメントを担い、Pallas/Vestaのペアリングは高度な証明を効率的に行うために特別に設計されている |
一つの曲線が別の曲線の場に埋め込まれる理由や、「2つの曲線」からなるサイクルがなぜ役立つのかは現実的で重要ですが、それは証明システムに関する記事に属します。今はこの点を理解するだけでも十分です：すべてのZcashの鍵はジェネレータ倍算されたスカラーであり、すべてのコミットメントは曲線上の点の和であることが確実です。
いくつかの簡略化により読みやすさを保っています。短いWeierstrass形式（y^2 = x^3 + ax + b）を使用しました；Zcashの曲線は多くの場合、効率と安全性のために他の同等の形式（Jubjubはtwisted Edwards曲線）で書かれていますが、群の概念は同じです。正確な点加算公式を定義していません（それは「第3交点、その後反射」の代数バージョンです）。また、「ペアリング」や「コファクター」などの細かい点も見送っていますが、これらは証明システムに関する記事で重要になります。これらは直感を変えませんが、それを鋭くします。
y^2 = x^3 + ax + bを満たす点の集合で、その点は幾何学的な弦と接線ルールにより加算可能であり、特別な**無限遠点（O）**がゼロとして機能します。y^2 = x^3 + 2x + 2をF_17上にとると19点があり、G = (5,1)はそれらすべてを生成する。）kGは計算が簡単だが逆転は困難：ECDLP。それがトラップドアです。k, 公開鍵kG. コミットメント: ペドレンス形式v.G + r.H、隠蔽性と束縛性を持ち、加算可能。| 項目 | 普通語での意味 |
|---|---|
| Elliptic curve | y^2 = x^3 + ax + bを満たす点の集合で、特別な「加算」が存在する |
| Point addition | 弦と接線ルール：2つの点を通る直線を引く、第3の交点を取り、反射する |
Point at infinity (O) | 曲線の「ゼロ」；これを加えると変化しない |
Generator (G) | マルチプルが最終的に全体の群をカバーするベースポイント |
Scalar multiplication (kG) | Gを自分自身にk回加算すること；前向きには簡単、逆転は困難 |
| ECDLP | kGからkを復元する難しい問題；セキュリティの基礎 |
| Pedersen commitment | v.G + r.H；隠蔽性と束縛性を持ち、加算可能な封筒 |
なぜ曲線ではなく単に大きな数mod素数を使用しないのか？ どちらも片道の通りを提供できますが、楕円曲線はより小さな鍵と高速な操作で同じセキュリティを達成し、点の算術はコミットメントに最適です。
ECDLPは証明されて困難なのか？ 証明されていないが、数十年間の努力により選ばれた曲線上では効率的な攻撃法が見つかっていません。セキュリティはその検証済みの仮定に依存しています。
量子コンピュータでこのシステムを破ることは可能か？ 十分な大きさの量子コンピュータがあればECDLPを破ることができます。これは業界全体にとって長期的な懸念であり、活発な研究領域です；現在の曲線は古典コンピュータに対してセキュアです。
なぜZcashは複数の曲線を使用するのか？ 異なる役割があります。一つの曲線はゼロ知識証明システムを担い、もう一つ（最初の場に埋め込まれた）は証明内の鍵とコミットメント操作を効率的に行うためです。次の記事でそのペアリングがなぜ重要なのか説明します。
セクション3の検証済み表を使用して、我々の玩具曲線では9G + 10Gは何か？そして答えは何を教えてくれるのか？（下に回答があります。）
9 + 10 = 19であり、19G = O、無限遠点であることが確認されています。したがって9G + 10G = Oです。これは10Gが9Gの負（加法逆元）であることを意味します：2つの点が「ゼロ」点に加算される。曲線上では、点の負はx軸をまたいで鏡像であり、実際9G = (7,6)と10G = (7,11)は同じxを持ち、y値の和は17 = 0 (mod 17)です。構造は完全に一貫しており、これは「それは群である」が保証するものです。
記事3 . ハッシュとコミットメント：「魔法の封筒」を正しく開きます。今では曲線上の点からコミットメントを構築する方法を見ました；次に、隠蔽性と束縛性が本当に何を意味するのか、ハッシュ関数に出会って、すべてのZcash支払いに根ざすノートコミットメントと結びつけます。
ZecHub向けの Zcash from First Principles シリーズの一部。CC BY-SA 4.0ライセンス。
8G |
| (13, 7) |
18G |
| (5, 16) |
9G | (7, 6) | 19G | O（無限遠） |
10G | (7, 11) |