ゼロ知識の証拠は、その背後にある数学が非常に先進的であるため、しばしば神秘的であるように見える。 私たちはこの混乱を取り除き、ゼロ知識の証拠が実際に何をしているのかをすべての人に理解させたいと考えています。 この記事では、多くのゼロ知識証明システムで使用される重要なビルドブロックを紹介します。 その後、我々は説明 , polynomial commitment schemesの最も一般的かつ実用的なタイプの1つです。 polynomial commitment schemes KZG 次に、How We Describe , and how 最後に、zk-rollups と Proto-Danksharding がどのようにスムーズかつ効率的に協力できるかを示します。 . KZG is used inside zk-rollups Ethereum also uses KZG in Proto-Danksharding both systems use polynomial commitment schemes Why are we talking about polynomials? ポリノミールは、大きなまたは複雑なオブジェクトを効率的に表すことを可能にするので、強力な数学ツールです。 一般的な例は、単一のポリノミールを使用してフィールド要素vのn次元ベクターを表すことです。 たとえば、3次元ベクターv = [2, 0, 6] は、ポリノミールによってコードされることができます。 なぜなら、プラグインの価値観は、 で、 そして、 一般的に、任意のnポイントを考慮すると、最大でn − 1で、これらすべてを通過する程度のユニークなポリノミールが常に存在する。 φ(x) = 4x² − 14x + 12 φ(1) = 2 φ(2) = 0 φ(3) = 6 この多角形を構築するプロセスは多角形インターポレーションと呼ばれ、最も広く使用される技術の1つは , which provides a direct formula for building the polynomial from the given points. Using this method, we now know how to build a polynomial of degree at most . LAGRANGE INTERPOLATION n − 1 from exactly n constraints 前回のセクションでは、あなたが知っているなら、 , you can always determine one unique polynomial whose degree is at most 今、私たちはさらに一歩進み、理解したい。 実際には、これらのn点の座標からこの多角形を見つける。 n points n − 1 どう これを行うための1つの一般的で簡単な方法は、ラグランジのインターポーレーションと呼ばれています。公式は複雑に見えるかもしれませんが、基本的なアイデアは非常に単純です。 たとえば、私たちはポリノミアムを探したいと仮定します。 グレードの最大2(すなわち、平方ポリノミアム)です。これを行うには、正確に3点が必要であり、ポリノミアムはこれらの3つの制約を満たす必要があります。これらの3点の座標を使用して、ラグランジのインターポーレーションは、それらに完璧に合う正確なポリノミアムを構築します。 P φ(1) = 2 φ(2) = 0 φ(3) = 6 そのために、我々は3つのサブポリノミール(制約ごとに1つ)を構築する。 , and レベル 最多 . P₁ P₂ P₃ 2 これらの3つのサブポリノミールは、これらのサブ制限に従わなければならない: x P₁(x) P₂(x) P₃(x) 1 2 0 0 2 0 0 0 3 0 0 6 1 2 0 0 2 0 0 0 3 0 0 6 sub-polynomial を評価する あらゆる制約に限らず、一つ一つ。 0 最後に、我々は設定: P(x) = P₁(x) + P₂(x) + P₃(x) 早速、前回のタブを参照して、 すべての制約を尊重する: P P(1) = P₁(1) + P₂(1) + P₃(1) = 2 + 0 + 0 = 2 P(2) = P₁(2) + P₂(2) + P₃(2) = 0 + 0 + 0 = 0 P(3) = P₁(3) + P₂(3) + P₃(3) = 0 + 0 + 6 = 6 ただ、これを確認したばかりです。 3つの制約を尊重し、今すぐ構築しましょう。 , and . P P₁ P₂ P₃ Building P₁ Using the , we can define P₁ as: factorised form P₁(x) = A(x − 2)(x − 3) すでに制約を満たしている: P₁ P₁(2) = P₁(3) = 0 さあ、見つけてみよう 例えば: A P₁(1) = 2 We have the following equation: P₁(1) = A(1 - 2)(1 - 3) = 2 私たちに与えるもの: A = 2 そして最後に: P₁(x) = 2(x − 2)(x − 3) 現在は3つの制限を満たしている。 P₁ P2の建物 Using the We can define AS : 工場形態 P2 P₂(x) = B(x - 1)(x − 3) すでに制約を満たしている: P2 P₂(1) = P₂(3) = 0 さあ、見つけてみよう 例えば: B P₂(2) = 0 次のような方程式があります。 P₂(2) = B(2 − 1)(2 − 3) = 0 私たちに与えるもの: B = 0 そして最後に: P₁(x) = 0(x − 1)(x − 3) = 0 現在は3つの制限を満たしている。 P₂ Building . P3 使用する The , we can define AS : 工場形態 P3 P₃(x) = C(x − 1)(x − 2) すでに制約を満たしている: P₃ P₃(1) = P₃(2) = 0 さあ、見つけてみよう 例えば: C P₃(3) = 6 次のような方程式があります。 P₃(3) = C(3 - 1)(3 - 2) = 6 私たちに与えるもの: C = 3 そして最後に: P₃(x) = 3(x - 1)(x - 2) 現在は3つの制限を満たしている。 P₃ Building P As previously seen, P(x) = P₁(x) + P₂(x) + P₃(x) Replacing , and by their respective expression, we get: P₁ P₂ P₃ P(x) = (x - 2)(x - 3) + 0 + 3(x - 1)(x - 2) P(x) = (x² - 5x + 6) + 3(x² - 3x + 2) P(x) = x² - 5x + 6 + 3x² - 9x + 6 P(x) = 4x² - 14x + 12 After expansion and simplification, we obtain: P(x) = 4x² - 14x + 12 チェックP 早速、これをチェックしましょう。 3つの制約を尊重する: P P(1) = 4(1²) - 14(1) + 12 = 4 - 14 + 12 = 2 P(2) = 4(2²) - 14(2) + 12 = 16 - 28 + 12 = 0 P(3) = 4(3²) - 14(3) + 12 = 36 - 48 + 12 = 6 What are polynomial commitment schemes, and why are they useful? Polynomial commitment schemes are special tools that let someone commit to an entire polynomial without showing what the polynomial actually is. They work similar to normal commitment schemes, where a person commits to a message and later reveals it. 彼らは通常の commitment schemesと同様に働き、誰かがメッセージにコミットし、後にそれを明らかにします。 , meaning you cannot change the message after committing, and Polynomial commitments follow the same rules, but instead of committing to one message, you commit to a whole polynomial with many coefficients. 複数のコミットメントは、同じルールに従いますが、一つのメッセージにコミットする代わりに、あなたは多くの係数を持つ全体の複数のコミットメントにコミットします。 binding hiding ポリノミクスの強力な部分は、あなたが後で特定の点でポリノミクスの価値を証明することができ、全体のポリノミクスを明らかにすることなく、例えば、誰かが彼らの秘密のポリノミクスの価値を証明したい場合 価値がある AT , they can do so without exposing the rest of the polynomial. They simply give a short proof that shows 検証は真実であり、検証者は以前の約束を用いて検証することができる。検証者は複数語そのものについて何も学ばない。この機能はゼロ知識の証拠において非常に有用であり、目的は追加の情報を明らかにすることなく何かが真実であることを証明することである。 ϕ(x) 66 x = 4 “ϕ(4) = 66” Another reason polynomial commitments are useful is that the commitment is much smaller than the polynomial. A polynomial may have hundreds or thousands of values, but the commitment can be just a single small group element, like 48 bytes. This is extremely important for blockchains, where storing or posting large data is expensive. By compressing a large polynomial into one tiny commitment, systems like and 多くのスペースを節約し、コストを削減することができます。 zk-rollups Proto-Danksharding これを理解しやすくするために、アリスは、 φ(x) = 3x2 + 5x + 2 のような秘密のポリノミルを持っていることを想像してください。彼女はポリノミルを明らかにしたくないが、ボブは、 φ(4) = 66 という証拠を欲しがっている。アリスは、ポリノミルへのコミットメントスケジュールを使用してポリノミルにコミットし、ボブにコミットメントを送ります。その後、彼女は値66だけを明らかにし、この値が x = 4 に正しいことを示す短い証拠を提供します。ボブは、コミットメントに対する証拠をチェックし、ポリノミルについて他の何も学ぶことなく説得されます。これがポリノミルコミットメントが現代の暗号 KZG Polynomial Commitment KZG Polynomial Commitment(KZG ポリノミアルコミットメント) 1. Commitment トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > トップ > )とその内容はプライベートに留まります( ( ) binding hiding 2. Evaluation 次に、試験者は、ポリノミーについて何かを証明しようとします。 したがって、彼らは x 点を選び、それをポリノミアルに接続し、その答えを計算します。 . 彼らはこの値のみ y を送信し、その値が約束されたポリノミアから来たことを示す小さな証拠を加え、実際のポリノミアはすべての時間に隠され、これは試験器が全体のポリノミアを暴露することなく、1つの点でポリノミアの行動を正しく示すことを可能にします。 明らかにせずに y=P(x) 3. Verification 最後に、検証者は、値が 本当にポイントで約束されたポリノミアルに匹敵する . Using the commitment and the proof, the verifier performs a cryptographic check. If everything is valid, the verifier knows 検証者が嘘をついたり、詐欺を試みた場合、検証のステップはそれを捕らえるでしょう。 y x P(x)=y KZG Polynomial Commitment Scheme KZG Polynomial Commitment Scheme(KZG)について KZGは . four main steps Step 1 - Trusted Setup システムが稼働する前に一度の設定です。 エリプト曲線グループG(サポートカップリング)のジェネレーターgを選択します。 polynomial の最大度 l を選択します。 Pick a secret random value: τ ∈ Fp Compute and publish: (g, g^τ, g^(τ^2), ...., g^(τ^l)) Only these powers of are public. gᵗ The value τ must remain secret forever. If someone knows τ, they can forge proofs. Step 2 - Commit to a Polynomial Suppose we have the polynomial: ϕ(x) = ∑ᵢ₌₀ˡ ϕᵢ xⁱ We want to compute the commitment: C = g^{ϕ(τ)} Although the committer cannot compute directly since he doesn’t know , he can compute it using the output of the setup g^{ϕ(τ)} τ τ Step 3 - Create a Proof for Evaluation ϕ(a)=b それを証明するために: ϕ(a)=b Polynomial Quotient を計算する: q(x) = ϕ(x) - b / x - a これは、評価が正しい場合にのみ有効です。 次に、証拠を計算します: π = g^{q(τ)} This is the KZG evaluation proof. Step 4 - Verification 与えられた: Commitment C = g^{ϕ(τ)} Proof π = g^{q(τ)} 評価証明 φ(a)=b 検査員がチェックする: e(c/g^b,g) = e(π,g^τ/g^a) ここ e( ⋅ , ⋅ )は a . Bilinear Pairingについて This equation is equivalent to verifying: q(τ) = ϕ(τ) - b /τ - a ペアリングチェックが実行された場合、評価は正しいと認められる。 ペアリングチェックの簡潔な説明 ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆ RHS: = (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) 等式は、 φ(τ)−b = q(τ)(τ−a)を意味し、q(x)が正しく形成された場合に φ(a)=bを強制する τで評価される割合のアイデンティティである。 ペアリングチェックの簡潔な説明 LHS : = ♪ ☆☆☆☆☆☆☆☆☆☆☆ e(C/g^b, g) e(g,g)ϕ RHS: = ♪ (π = g^{q(τ)}) e(π, g^τ/g^a) e(g,g)q(τ)⋅(τ−a) Equality implies , the quotient identity evaluated at 強要するもの もし 正しく作られました(^^) ) ϕ(τ)−b = q(τ)(τ−a) τ ϕ(a)=b q(x) q(x) = ϕ(x) - b / x - a Use Cases: ZKロールアップ zk-rollups では、 Layer 2 (L2) で行われた作業が正しいことを証明しなければなりません。これを行うには、計算のすべてのステップが大きなテーブル(2D マトリックス)に変換されます。 このテーブルの各列は、計算の一部を表し、各列は多角形に変換することができるので、巨大なマトリックスを直接処理する代わりに、私たちは多角形のリストで作業します。計算の正確性は、これらの多角形の間の数学的ルールを使用して記述することができます。例えば、テーブルの3つの列が3つの多角形を表します。 世代証人 A(x) B(x) c(x) A rule might say that a(x)⋅b(x)−c(x)=0 これは、「第1の複数が第2に倍増するには、第3に等しくなければならない」という意味です。 列 1 × 列 2 は列 3 を生成する必要があります。 このルールをxのあらゆる可能な値(遅いもの)にチェックする代わりに、zk-rollups は数つのランダムな点でしかそれをチェックしません。 長いリストがルールに一致するかどうかを確認したい場合は、各項目を比較する必要はありません - いくつかのランダムな項目をチェックすると、通常、関係全体が有効かどうかを教えてください。 Example: ロールアップは、L2の計算を記述するすべてのポリノミールにコミットします(暗号箱の中に閉じ込めるようなものです)。後で、検証者は、特定のランダムポイントでこれらのポリノミールの値を尋ねることができます。それらの値と約束で、検証者は、正確性のルールが保持されているかどうかを検証します。 Ethereum’s Proto-Danksharding (EIP-4844)は、ロールアップがEthereumのレイヤー1にデータを公開することをより安くするように設計されたアップグレードです。 このタイプのトランザクションには、Aと呼ばれる大きなデータが含まれます。 (約128kB) このブロブは、 smart contracts or the execution layer. smart contracts can only see a ブロブではなく、ブロブそのもの。 タグ:Thanksharding ブロック トランザクション ブロブ not commitment 今の質問は、 One option is to take the blob and just しかし、ハッシュは限られている:ハッシュだけを保存する場合、その後、全体のブロブを明らかにすることなく、ブロブ内のデータについて何も証明することはできません。 Ethereumはこのブロブへのコミットメントをどのように生み出すべきでしょうか。 hash it 代わりに、私たちはブロブをポリノミールとして扱うことができます(以前は、ベクトルやデータをポリノミールとして表す方法を説明しました)。 such as KZG, Ethereum can commit to the blob in a way that not only hides the data, but also allows verification of certain properties . polynomial commitment scheme 全ブロックをダウンロードせずに この能力は、いわゆる DASは、検証者がブロブが利用可能か、正しいかを確認することを可能にする。 代わりに、検証者はわずかなランダムなパーツのみをダウンロードします。複数の約束の背後にある数学のおかげで、十分なランダムサンプルが正しい場合、検証者は全体のブロブが利用可能であることを非常に確信することができます(DASはProto-Dankshardingの最初のバージョンには含まれていませんが、Ethereumが「完全なDanksharding」に向かって進むとすぐに追加されます)。 (DAS) Data Availability Sampling without downloading all 128 kB Data Availability Sampling Ethereumが選ぶ 研究者らはいくつかのスケジュールを比較し、KZGは短期および中期にEthereumのロードマップのための効率性、証拠サイズ、およびシンプルさの最高のバランスを提供すると結論付けました。 KZG How zk-rollups and Ethereum’s Proto-Danksharding interact zk-rollupsとEthereumのProto-Dankshardingは別々のシステムのように見えるかもしれませんが、どちらもKZGのコミットメントを使用して、スロールはLayer 2で行われた計算にKZGを使用し、EthereumはKZGを使用してLayer 1に投稿された大きなデータブロブにコミットします。 When Scroll finishes processing a batch of L2 transactions and computes a new state root, it must publish three things on Ethereum’s L1: T - L2 取引のリスト Si - これらのトランザクションが適用された後、新しい状態のルート π - 新しい状態の根が正しいことを示す証拠。 Ethereumは2つのことを確認する必要があります。 that the new state root is valid (meaning the transactions were executed correctly), and Sᵢ したがって、トランザクションリストT は正確にその状態の root を生成するために使用されるものであるため、トランザクションリストT を証拠 π とつなげる方法がある必要があります。 Ethereumストア Aとして つまり、検証者はAにしかアクセスできないということです。 to that blob - let’s call this commitment 一方、証拠は also contains KZG commitments to various polynomials used during the computation, including the polynomial that represents the transaction list. That polynomial has its own commitment inside the proof—call it . T データブロック KZG commitment Cₜ π Cₚ 現在、KZGの2つのコミットメントがあります( ブロックと (その証拠から) 同じポリノミック φt (トランザクションリストのポリノミック表示) を表します。 and really refer to the same data. Cₜ Cₚ should Cₜ Cₚ これを実行するには、Aと呼ばれる技術を用いる。 アイデアはシンプル: proof of equivalence 同等性の証明 ランダムに似た valuez = hash(Ct Cp)を選択すると、これらの2つの約束に対して z が予測不能でユニークになります。 Both commitments are then “opened” at the point z, each producing a value . That is, prove that: a ϕₜ(z) = a under commitment , and Cₜ ϕₜ(z) = a under commitment . Cₚ 両方の約束が同じランダムポイントで同じ値を付与する場合、非常に高い確率で、それらは同じ多角形を表します。 : Imagine two people, each claiming they have the same secret polynomial. Instead of revealing the whole polynomial, each evaluates it at a random point-say x = 103. If both evaluations match, the chance of them having two different polynomials that coincidentally agree at that exact random point is astronomically small. Example : ふたりの人が、それぞれ同じ秘密の多角形を持っていると主張することを想像してください. 全体の多角形を明らかにする代わりに、それぞれがランダムな点でそれを評価します-say x = 103. If both evaluations match, the chance of them having two different polynomials that coincidentally agree at that exact random point is astronomically small. 両方の評価が一致する場合、彼らがその正確なランダムな点で偶然一致する2つの異なる多角形を持っている可能性は天文学的に小さい。 Example この同じ論理により、Ethereumは、証明書で使用された取引リストを確認することができます。 ブロブに掲載された取引リストと同じです。 π 良いボーナスは、この等価性チェックは、2つの約束が使用する場合でも機能するということです。 たとえば、一つはKZGであり、もう一つはFRIであり、両方のコミットメントが一つの点で開放をサポートしている限り、検証者はそれらを比較することができ、このアプローチを非常に柔軟にすることができます。 異なる 異なる Erasure Coding With Polynomials KZGとPeerDASの両方で使用される別の強力なコンセプトは、 . This technique allows data to be recovered even if parts of it are missing. Using polynomials, we can take a small set of original values and extend them into a longer set by evaluating the polynomial at additional points. The key property is that これが、Ethereumのデータ可用性サンプリング(DAS)の働き方です:ノードは、データのすべての部分を必要としませんが、オリジナル情報を高確率で再構築できるランダムサンプルだけです。 erasure coding if the degree stays the same, the original data can be recovered from subset of enough points どんな どんな なぜポリノミックな約束が必要なのか。 なぜポリノミックな約束が必要なのか。 Using polynomials and erasure codes solves many problems, but creates a new one: How do we prove that a piece of data truly belongs to the committed polynomial? This is where KZGのコミットメントは、以下のことを可能にします。 KZG polynomial commitments a polynomial with a single small group element 単一の小グループ要素 a data point is one of the polynomial's evaluations. データポイントがポリノミールの評価の1つであることを証明する。 polynomial をダウンロードしたり再構築したりすることなく証拠を検証する この属性はEthereumのスケーリングロードマップに不可欠であるため、検証者はブロブデータのメガバイトを読み取ることなく、効率的にデータの可用性を検証する必要があります。 and polynomials を使用してデータを分割する で、 そして、 各ブロブは、その評価がデータを満たすポリノミールとして扱われます。データが拡張され、列に整理されると、検証者は小さな部分だけを受け取りますが、ポリノミール構造は、すべての部分が一貫していることを保証します。 各証拠は、特定のセルがブロックヘッダーで行なわれたポリノミアルに対応することを確認します。 ピアス タグ:Thanksharding columns cells blobs KZG proofs 複数のコミットメントのおかげで、Ethereumはデータの可用性を安全にスケールできますが、個々のノードの負荷を劇的に減らすことができます。 ピアス エイプ4844 次に、PeerDASがどのように機能するか、KZGのコミットメントがどのように重要な役割を果たすか、および削除コードがネットワークが欠落したデータを回復することを可能にする方法を詳しく見ていきます。 次に、PeerDASがどのように機能するか、KZGのコミットメントがどのように重要な役割を果たすか、および削除コードがネットワークが欠落したデータを回復することを可能にする方法を詳しく見ていきます。
