有限体: 暗号が生きる数の体系

Annkkitaaaによるオリジナル研究

"巻き戻り"がZcashの秘密の基礎

シリーズ: Zcashから第一原理へ . 第1回. 有限体 対象読者: 新規参入者。通常の学校で習う算数（加減乗除）のみを仮定し、暗号技術や高度な数学の知識は不要。 得られるもの: 有限体に対する直感的かつ正確な理解、暗号技術者がなぜこれを用いるのか、そしてZcash内でどこに使われているか。

記事0では5つのキャラクターに出会いました: ノート、コミットメント、ノートコミットメントツリー、ヌリファイア、ゼロ知識証明。未解決の疑問がありました:すべての鍵や秘密のレシピはどこから来るのか? それらは数値から来ます。しかし、あなたが育ってきた普通の数値ではありません。特殊で自立した数体系、有限体というものです。Zcashにあるほぼすべての暗号技術はこれに構築されています。

この記事ではそのアイデアをゆっくりと説明します。約束通り、直感から始めます。公式はそれ自身が価値を証明するまで使わないでしょう。

1. なぜあなたが気にすべきなのか?

暗号技術にとって普通の数値には問題があります: 無限に存在し、情報が漏れてしまうからです。

ある数値が大きくなるときに何が起こるか想像してください。もし私が秘密の計算が8,142,067を生み出したと伝えたなら、あなたはすでに多くのことを知っています: それは七桁の数値で、奇数であり、「ある程度大きい」ものです。大きさはヒントです。そしてヒントはプライバシー系システムが与えてはいけないものです。

暗号技術は以下のような数体系を望んでいます:

• 有限個の値があり、コンピュータがそれらを正確に保存でき、丸め誤差やオーバーフローがない。
• 値が大きさを漏らさない。システムには「より大きい」という概念が実際には存在しないから。
• 加算、減算、乗算、除算が自由かつ逆転可能に行える。暗号技術のレシピは実際の代数が必要だから。
• 空間を天文的な規模にまで大きくできる。それによって推測は不可能になる。

この希望リストには名前があります。それは有限体です。1文字も書く前に、その直感を構築しましょう。

2. 直感: 時計

あなたは毎日使っている有限体です。それは壁にある時計です。

12時間の時計では数値が巻き戻る。10時から5時間を加えると、「15時」にはなりません。「3時」になります。時計には12つの位置しかなく、上にカウントしすぎるとスタートに戻ります。

この3つが起こったことで、この記事の要点が明らかになりました:

1. 世界は有限です。正確に12個の位置があり、どれだけ数えても変わりません。
2. 加算は依然として機能します。時間の加算をいつでも行えるし、常に有効な時計の位置に落ち着きます。
3. 大きさが意味を持たなくなりました。「3時」は3時間か15時間か27時間を数えたのかを教えてくれません。巻き戻りによって大きさの情報を消去しました。この情報の削除こそ、プライバシーに優しい性質です。

この巻き戻し算には公式的な名前があります: モジュラ算術。時計は「mod 12」で動作し、「mod 12」と書かれます。数学者たちは0からカウントを開始するのが好きなので、実際の「mod 12」の時計は0, 1, 2, ..., 11の位置を持っています。mod 7の時計なら0から6です。

唯一のルール: pで計算するときは、普通の算術を行い、その後pで割り、余りだけを保持します。 mod 7の例: 5 + 4 = 9, 9は7で割ると余りが2になるので、5 + 4 = 2 (mod 7)。

3. 時計から体へ

時計では加算できます。体はそのアップグレード: 加減乗除すべてが動作する数体系です。特に難しい除算も可能です。

非公式に、体とは「数」の任意の集合で、**加算、減算、乗算、除算（ゼロ以外で）**が可能であり、すべての慣れ親しんだルールが依然として成り立つものです: 加算や乗算の順序は関係ない、括弧を再グループ化できる、0と1があり、それぞれの数には負数と（ゼロ以外では）逆数がある。

有理数は体です。実数も体です。我々が望むのは有限なものです。

ここに主要な結果があります、そしてそれは美しいものです:

すべての整数 0, 1, ..., p-1 を取って、すべての算術を mod p で行う。もし p が素数なら、その結果は有限体になる。それを F_p（「F サブ p」と読む）と書く。

したがって、mod 7 の時計風算術を使った F_7 = {0, 1, 2, 3, 4, 5, 6} は本物の有限体です。実際に見てみましょう。

F_7における乗算（確認済み）

各行の要素は (行 x 列) mod 7:

1から6の行を見てください: 各行は非ゼロ値 1..6 をそれぞれ一度だけ含んでいます。この「繰り返し無く、欠けもしない」パターンが体の指紋です。

除算: 素数が必要な魔法

除算とは「逆数をかけること」です。F_7では、数値 a の逆数（または逆元）は a^(-1) で、a x a^(-1) = 1 を満たします。表から直接読み取れます:

一つ確認: 2 x 4 = 8 = 1 (mod 7)。したがって、F_7での「2で除算」は「4をかける」ということです。すべての非ゼロ要素にパートナーがあります。それがF_7が体である理由です。

4. モジュラスが素数でなければならない理由

これは記事で最も重要なアイデアなので、抽象的なものではなく具体的なものにしてみましょう。

mod 6（6は素数ではない）を使って「体」を無理やり作ってみた場合に何が破綻するか見てください:

2 x x = 1 (mod 6) を満たすような x は存在しますか? 全てをチェック: 2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4. 答え1は一度も現れない。したがって、2にはmod 6での逆数がない。さらに悪いことに、2 x 3 = 6 = 0 (mod 6)：二つの非ゼロの数値をかけてゼロになる。

この第二文は算術にとって大惨事です。二つの非ゼロの数値がゼロに（零因子と呼ばれる）なって除算が破綻し、除算が破綻したシステムは体ではありません。これは6が2 x 3というように因数分解できるから起こります。

素数とは定義上このような因数を持たないものです。したがって、mod 素数では零因子は現れず、すべての非ゼロ要素に明確な逆数があり、構造は適切な体になります。

あなたの記事で使えるワンライナー: 素数モジュラスを入力すると、正確な除算が出力される。

5. 学ぶ価値のある唯一の公式: コンピュータが逆数を見つける方法

F_7では逆数を表から読み取っていましたが、Zcashで使われる素数は数百桁あり、表は不可能です。古典的なショートカットがあります、そしてこれはこの記事に登場する唯一の公式です。

フェルマーの小定理は、素数 p と任意の非ゼロ a に対して以下を示します:

a^(p-1) = 1   (mod p)

これを変形（aの一つの因子を取り除く）すると逆数が無料で得られます:

a^(-1) = a^(p-2)   (mod p)

F_7 (p = 7, p - 2 = 5) でテスト: 2の逆数は 2^5 = 32 = 4 (mod 7) です。実際、表では 2^(-1) = 4 と示されていました。コンピュータは巨大なべき乗を非常に高速に計算できるので、これにより「逆数を見つける」操作は、巨大な素数でも正確で迅速になります。

これを覚える必要はありません。有限体での除算は速くかつ正確な操作であることを知っていれば十分です。それが暗号技術者がこの上に構築する理由です。

6. 暗号技術が有限体を愛した理由

直感を組み合わせて、以下のように一ページで説明します。

有限体とは一言で言えば、完璧に閉じた、完璧に正確な、完璧に巨大な算術の遊園地です。Zcashにあるすべてはこれの中から構築されています。

7. Zcash内でどこに存在するか

「Zcashは有限体を使用している」ということを信じる必要はありません。ここに具体的なマップがあります（より深い仕組みは後の記事で、ここでは指紋が実際に存在することを示すだけです）。

• Sapling（古いシールド設計）はBLS12-381という曲線を使って証明を構築し、その基本体は381ビットの素数を使用しています。すべての座標、鍵、証明要素はこの素数に基づく有限体の要素です。
• Orchard（現在のシールド設計）はPallasとVesta（「Pasta」曲線）というペアを使っており、その場は約255ビットの素数を使用しています。
• 記事0で紹介されたノートコミットメント、ヌリファイア、そしてゼロ知識証明内の数値はすべて、これらの有限体の要素です。プロトコルが「このコミットメントを計算する」と言うときは、「その素数を使ってこの算術を行う」ことを意味します。

したがって、記事0の未解決の質問「秘密のレシピはどこから来るのか?」への答えはここから始まります: すべては有限体での算術から始まる。次の記事ではこの体を使って実際のオブジェクト、楕円曲線上の点（鍵やコミットメントになるもの）を構築します。

8. 正直な免責事項

新規参入者に親しみやすいようにいくつかの真実を簡略化しました。有限体はF_pだけでなく、p^n個の要素を持つもの（拡張体と呼ばれる）も存在します。それらはSaplingの証明システムが依存する「ペアリング」に重要です。また、完全な体の公理リストや、この規模の素数を選ぶ方法や検証方法を省略しました。これらはあなたが持っている直感を変えません。それを精緻化します。後の記事が必要になったら、その精度を取り戻します。

9. 要約

• 暗号技術は有限、正確、大きさに無関心、完全に逆転可能、巨大な数体系を必要とします。そのシステムは有限体です。
• 直感は時計: モジュラ算術で「巻き戻る」算術であり、「大きさ」を消去するという利点があります。
• 0..p-1の数値を使って素数pでのmod算術を行うと、実際の体F_pが得られ、除算も可能になります。なぜならすべての非ゼロ要素に逆数があるからです。
• モジュラスは必ず素数でなければならない: 合成数のモジュラスは零因子（例: 2 x 3 = 0 mod 6）を作り出し、除算を破綻させます。
• コンピュータはフェルマーの小定理(a^(-1) = a^(p-2))を使って逆数を高速に見つけ出します。
• Zcashでは、すべての鍵、コミットメント、ヌリファイア、証明要素は最終的に大きな有限体（Orchardでは255ビットのPasta体、SaplingのBLS12-381では381ビットの体）の要素です。

用語集

FAQ

なぜ普通の整数や小数を使わないのか? 小数は丸められたり漂ったりする。整数は無限に大きく成長し、大きさを漏らす。有限体は正確、限定的、大きさに無関心であり、暗号技術が必要とする特性です。

「巻き戻り」は情報の損失を引き起こすのか? 意図的にそうしています。中間値の大きさを消去することはプライバシーにとって特徴であり、欠点ではありません。

より大きな素数は常に安全なのか? 概ね、より大きな体は多くの可能性があり、推測が困難になりますが、セキュリティは全体構造に依存し、体サイズだけでは決まりません。後の記事で詳しく説明します。

なぜZcashでは255ビットや381ビットの素数を使用しているのか? それらは証明システムに適した構造と効率を持つ曲線を構築するために選ばれています。その「適切な構造」について、次の二つの記事で説明します。

直感をテスト

F_7では 5 - 6 は?（答え: {0,...,6} 内に残るように巻き戻すことを忘れないでください。）(下記に答えがあります。)

次のステップ

記事2 . 楕円曲線: 我々が構築した有限体を使って、点を「加える」ことができる奇妙な種類の曲線を描きます。それらの点はZcashの鍵やコミットメントになり、プライバシー系全体を可能にする片道トラップドアを隠します。いつものように、直感から始めます。

ZecHub向けの Zcash from First Principles シリーズの一部。CC BY-SA 4.0ライセンス。