あなたが必要とするもの:
- コンピュータサイエンスの背景
- イーサリアムの基本
- 微積分の基礎(制約の最適化)
あなたが得るもの:
- ゼロ知識SNARKの基本
- マークルの木の基本
- EthereumがSNARKのおかげでXNUMX秒あたり数千のトランザクションにスケーリングする方法
SNARKを使用すると、証明者は検証者に、Wを明かさずに、共有/既知の入力Xを使用して問題Fに対する解Wがあることを検証者に証明できます。
問題の解決策を見つけるには、大量の計算能力とメモリが必要になる場合があります。
つまり、検証者は基本的に、証明者が適切に機能している(そして解決策を見つけた)ことを100%確信できます。 解決策を確認するために自分で仕事をやり直すことも、解決策を知ることもありません。 魔法です!
プロセスには3つのステップがあります。
- セットアップ —問題F(XNUMX次算術プログラムとして表現する必要があります。以下を参照)は、SNARKに対して準備されています。 このプロセスは非常にメモリが多く、問題の複雑さに応じて計算負荷が高くなります(→入力と制約の数→制約充足問題の行列の次元)。 セットアップの出力は次のフェーズで使用されるため、セットアップを行うプレーヤー(Verifier自体である場合もあります)は、すべての関係者から信頼されている必要があります。 セットアップは通常、 ライブラリスナーク、C ++ライブラリであり、zkSNARKの最も一般的な実装です。
- 判明 —共有入力Xの問題Fの解Wを持っている証明者(多分彼女はそれを見つけるために大量のCPUとメモリを費やした!)は、 ライブラリスナーク との出力 証明を作成するフェーズ𝚷。 このプロセスは、明らかにメモリが多く、コンピューティングに負荷がかかります(上記のように、問題の複雑さによって異なります)。 出力のサイズ(つまり、証明𝚷)は、問題の複雑さに関係なく、簡潔で一定です。 証明者は、出力を使用するため、セットアップ段階を誰が行ったかを信頼する必要があります…
- 確認中 —ベリファイア—セットアップフェーズの出力を入力として与え、共有入力Xと証明𝚷 –証明をチェックします。 検証が成功した場合、証明者はWを明かさずに、問題Fに対する解決策Wを見つけたことを検証者に証明することができました。 良い点は、Proofが簡潔で常に同じ長さであるだけでなく、検証プロセスが高速であり、メモリ/コンピューティングに負荷をかけないことです。 以前のXNUMXつのフェーズとは異なり...検証はスマートフォンでミリ秒単位で簡単に実行できます。
良い要約(source):
これはどうして起こりますか? まあ、それはマーリンの魔法です! この背後にある数学を取得したい場合は、 ここから始めます.
ソフトウェアをXNUMX次算術プログラムに変換するにはどうすればよいですか?
上記のように、セットアップフェーズの問題FはXNUMX次算術プログラムである必要があります。 ゲームのルールは厳しいです:
- ソフトウェアの入力は数値でなければなりません。 もの(配列、文字列など)を数値に変換します。 それは取るに足らないことです。
- 「二次的に制約された方程式系」とは、次のことを意味します。
ここで、xは入力のn次元ベクトル、mは制約の数(つまり、システムの方程式の数)、Cはn行n列の係数行列、qはn次元の係数ベクトルです。 マトリックスとベクトルが気に入らない場合は、n = 3およびm = 2の場合(3つの入力、2つの制約)を次に示します。
- 実装は演算回路です。つまり、結果は 問題が解決しました (システムが解かれる、つまりすべての多項式が0に等しい)または 問題は解決していません (他のすべての場合)。 つまり、「これらの入力は、この問題の解決策のXNUMXつではありません」です。
- C₁、C₂、…、C𝚖、q₁、q₂、…、q𝚖係数は、システムの制約です。 これが基本的にソフトウェアを定義するものです。 それらを変更すると…別のソフトウェアが手に入ります! SNARKの動作に戻ると、C₁、C₂、…、C𝚖、q₁、q₂、…、q𝚖はセットアップフェーズの入力です。 したがって、セットアップ段階の出力(証明と検証に必要)は、C₁、C₂、…、C𝚖、q₁、q₂、…、q𝚖に厳密に関連し、その問題に対してのみ機能します。 それらを変更した場合、別のソフトウェア/問題を定義しているため、セットアップフェーズを再実行する必要があります。 x₁、x₂、…、x𝗇は変数です(つまり、システムの解を得るために推測する必要があるもの)。 したがって、「Dear Prover、共有/パブリック入力Xを使用した問題Fの秘密の解Wを見つけてもらえますか?」という場合、たとえば「Dear Prover、システムを解くx₁、x₂、…、x𝗇の値を見つけることができますたとえば、x₇= 2393、x₅₂₆= 5647?」 共有/パブリック入力に制約されているx₇とx₅₂₆を除いて、すべてのx𝗇で必要なことを実行できます。
タフな人生ですが、あなたは生き残ることができます...ループが必要な場合は、同じ操作を何度も繰り返して展開することができます。 または、たとえばx₁⁴x₂⁵が必要な場合は、新しい入力x₃=x₁⁴x₂⁵を定義し、制約でx₃を使用します。 変数と制約を追加することがすべてです… 非常に単純なソフトウェアであっても、数億または数十億の入力と制約に簡単に到達できます。
もっと知りたい? 読んだ こちら。 そしてまた、この基本をチェックしてください code_to_r1cs.py イーサリアム/研究から。
マークルツリーとは
ハッシュ関数は、任意のサイズの入力を固定サイズの出力にマップするルールです。 「Woody Allen」を「Woen」に、「Paul McCartney」を「Paey」に変換する、かなり役に立たないハッシュ関数「最初のXNUMXつと最後のXNUMXつの文字を連結する」を発明できました。
マークルツリーは、すべての親が1人の息子のハッシュであるデータ構造です。 一番上にはルートがあり、これはレベルXNUMXのXNUMX人の息子のハッシュです。一番下では、すべての葉が外部入力のハッシュです。
架空の「Woody Allen」→「Woen」ハッシュ関数を使用します。
リーフが変更されると、変更はルートまで伝搬されます。 ANTHONYが変更されると、ANNY(リーフ)、CENY、およびCECO(ルート)も変更されます。 葉が変わると、ルートも変わります。
ルートを再計算するのにツリー全体は必要ありません。 この例では、ANTHONYが変更され、JACOとCECILYの両方を知っている場合、JAMES、MARCO、JAES、MACOを完全に無視しても、ルートを簡単に再計算できます。 巨大な木の場合、これは多くの時間を節約します!
だから何?
マークルツリーは、データの整合性チェックに最適です。 通常は、どちらが有効なルートであるかを知っており、受信したデータがそのルートと一致することを確認します。 例:地球上の人の名前のデータセット全体(時間がない、帯域幅がない、またはデータがまったくない)を提供できない信頼できる当事者は、ルート(例: 「CECO」)。 あとがき:何千もの信頼できない関係者から、葉の番号を参照して数百万の名を受け取ります。 さて、あなたは正しいルートを持っているので、誰が信頼できるのか、誰があなたに偽のデータを与えているのかを確認できます...
マークルの木もあなたの人生の一部です! 3GBのTorrentファイルをダウンロードすると、ファイルは数百万の小さなチャンクに分割されます。 すべてのチャンクのハッシュはリーフに格納されます。 どちらがツリーの有効なルートであるかがわかっているので、誰かがファイルのチャンクを受け取るたびに、それが正しいかどうかを確認できます。 そうでない場合は、同じチャンクを他の誰かに尋ねることができます。
ツリー全体またはすべての葉をまだダウンロードしていない場合でも、これを行うことができます。ルートがCECOであり、JACOを信頼していることがわかっている場合... ANTHONYチャンクを受け取ったら、ダウンロードしていない場合でもそれを確認できます。まだチャンクMARCOとJAMES。
マークルツリーが分散型台帳テクノロジで役立つ理由は簡単です。コンセンサスプロトコル(低速で高価)を使用するのは、ルート上のコンセンサスに到達するためだけです。 次に、ネットワークの信頼されていないノードは、効率的かつ直接データを共有できます。また、ルートとの整合性チェックにより、安全かつ健全にスリープできます。
神がイーサリアムにセキュリティ、スケーラビリティ、および分散化から2つの超大国を選択するように依頼したとき…イーサリアムはスケーラビリティを犠牲にしました。 実際、「8秒あたりのトランザクション数」には強い制限はありません。この制限は、各ブロックのガスの量に関係します。つまり、各ブロックで実行できる操作の量です。 この制限はXNUMX万ガスです。 これは、多くの「小さな」トランザクション(トランザクションに添付されたデータがない、そのデータに対して実行される操作がない)または少数の大きなトランザクションを意味する可能性があります。 トランザクションをサブミットするイーサリアムのノードと、より多くを支払うトランザクションをブロックに含めるイーサリアムのマイナーの責任です。
ブロックが採掘されます あらゆる 〜15秒。 これは、32分あたり約XNUMX万個のガスを意味します。これは、Ethereumのdappsを主流にしたい場合には十分ではありません。
ちなみに、EthereumとVisaの面倒な比較はやめましょう。 集中システムは 常に イーサリアムよりも高速である…設計上! 彼らはさまざまなことを行い、さまざまな状況でそれらを必要とします。 地方分権や信用のない環境が必要ない場合は、もちろんVisaを選択する必要があります。 要するに: ブレンダーが洗濯機よりも速く回転するという事実は、ブレンダーでズボンをきれいにするという意味ではありません!
パズルを組み立てよう! SNARKのおかげで、XNUMXつの大きなトランザクションで多くの小さなトランザクションを「圧縮」できると想像してください。 この大きなトランザクションで消費されたガスが小さなトランザクションで消費されたガスの合計より少ない場合、それはガスを節約していることを意味します。
そして、ガスを節約するとは、
- トランザクション全体に費やすユーザーが少ない→これはエコシステム全体の推進力になる
- より多くのものをブロックに入れることができる→ブレンダーより速く回転するイーサリアム!
システムを教えてください。
トランザクションとスマートコントラクトを集約するユーザー、またはXNUMX人以上のリレーがいます。
- このゲームを喜んでプレイするユーザーは、イーサ(またはトークン)を公に監査されたスマートコントラクトに送信します。 新しいプレーヤーごとに、マークルツリーの新しいリーフが作成されます。 リーフには、Etherの所有者に関する情報(公開鍵でもある彼女/彼のアドレス)、Etherとナンスの量(そのアカウントのトランザクションのカウンター、リーフが追加されると0)が含まれます。
- AがEther to Bを送信したい場合(両方ともスマートコントラクトにリーフ/アカウントが必要)、Aはトランザクションをパックします。これには、 からアカウント、 〜へ アカウント、 使節 fromアカウントの 量 転送されるエーテルとの 署名 トランザクションの(「from」アカウントの秘密鍵で署名されていることは明らかです)。 その後、彼女/パックされたトランザクションを中継者に送信します。
- リレー機能は、指定された時間枠(XNUMX時間など)で受信したすべてのトランザクションを集計し、新しいバランスの金額でマークルツリーを更新し、すべての署名と新しいマークルツリーのルートが有効であることを証明するSNARK証明を作成します。 最終的に、中継者は新しい状態と証明をスマートコントラクトに送信します。
- スマートコントラクトは、チェーンのプルーフを検証します。 有効な場合、コントラクトの内部メモリに新しい状態のマークルツリーのルートを保存します。
基本的に、マークルツリーのルートは、すべてのアカウントの状態全体を表します。 また、送信する新しいルートによって要約された新しい状態につながるトランザクションの署名の有効性を証明できない限り、それを変更する(=お金を盗む)ことはできません。
簡単に言えば、Coinbaseとは異なり、Coinbaseとは異なり、署名なしでは何もできない中継者を信頼する必要がなく、ユーザーはCoinbaseのように超高速でほぼ無料のトランザクションを利用できます。
それは非管理側鎖であり、その状態はマークルツリールートによって要約されます。
上記でSNARKについて学んだことと、スケーリングについて話し合ったことを結び付けましょう。 それにはさまざまな方法があります。 2つのレシピを比較します:Vitalik's バージョン とbarryWhiteHatの バージョン.
セットアップは…
プロジェクトを開始し、スマートコントラクトも作成する人。 監査可能であればあるほど良いです。彼女/彼を信頼するべきです…それは 信頼できるセットアップ!
スマートコントラクトで節約できます…
2つのマークルルート(bytes32値):最初のツリーには、アカウントのアドレス(公開署名)、XNUMX番目のアカウントの残高とノンスが含まれます
証明は…
リレー
中継者はスマートコントラクトに送信します…
- 新しい状態の2つのマークルルート(アドレスツリーとバランス+ナンスツリー)
- 署名なしのトランザクションのリスト。 「各トランザクションは68バイトあたり68ガスかかります。 したがって、通常の送金の場合、限界費用は3 * 68(から)+ 3 * 68(から)+ 1 * 68(料金)+ 4 * 4 + 2 * 68(金額)+ 2 * 892になると予想できます。 (ノンス)、またはXNUMXガス」
PROVINGプロセスの既知の入力は…
- 2つの古い状態のマークルの根
- 2つの新しい状態のマークルの根
- 取引リスト
証明プロセスはそれを証明します…
与えられた
- 2つの古い状態のマークルルート(既にコントラクトに格納されています)
- 2つの新しい状態のマークルルート(aggr。トランザクションで送信)
- トランザクションリスト(aggr。トランザクションで送信)
…リレーには、これらのトランザクションで2つの古いルートを持つ状態から2つの新しいルートを持つ状態に移動するための有効な署名があります。
確認は次の方法で行われます…
スマートコントラクト(必要に応じて、堅牢性、Vyperでコーディング!)
プロセスの既知の入力を確認しています…
同じPROVINGのプロセスの既知の入力は、明らかに…!
スケーラビリティの制限
集約されたすべてのトランザクションは、SNARK検証に650kガスを使用します(固定費)プラス〜900ガス 限界費用 トランザクションごと(データの送信にはコストがかかります!)。 したがって、ブロック全体を使用すると、リレーは最大で集約できます。
つまり、 544秒あたり〜XNUMX tx
バリーホワイトハット バージョン
セットアップは…
プロジェクトを始める人。
スマートコントラクトで節約できます…
1現在の状態のマークルルート。 すべての葉は、アカウントのハッシュされた状態です。
したい 作ります アカウント?
状態= AccountState(pubkey、balance、nonce)
state.index = self._tree.append(state.hash())
証明は…
リレー
中継者はスマートコントラクトに送信します…
- 証明𝚷
- 新しい状態のマークルルート
- 証明𝚷
PROVINGプロセスの既知の入力は…
- 古い状態のマークルルート
- 新しい状態のマークルルート
証明プロセスはそれを証明します…
与えられた
- 古いマークルルート(既にコントラクトに格納されています)
- 新しいマークルルート(aggr。トランザクションのセンチ)
…中継者は、古いルートを持つ状態から新しいルートを持つ状態に移動するための有効な署名を持つトランザクションのリストを持っています
確認は次の方法で行われます…
スマートコントラクト(必要に応じて、堅牢性、Vyperでコーディング!)
プロセスの既知の入力を確認しています…
同じPROVINGのプロセスの既知の入力は、明らかに…!
スケーラビリティの制限
中継者はトランザクションのデータをスマートコントラクト(コストがかかる)に送信しないため、制限は実際にはSNARKの証明を検証するためのガスの量です。
ハワード・ウーについて言及する 分散システムでのSNARKのPROVINGフェーズの実行について、barryWhiteHat 楽観的に 巨大なSNARK(16666億の制約!)で1トランザクションを確認することが可能であると述べています。
バリーホワイトハットも 考える 500kガスでチェーン上の証明を検証することが可能です。つまり、ブロックごとに16のSNARK(8万/ 500k)を配置できます。 1.07秒あたり最大17,832のSNARK ...つまり、XNUMX秒あたり〜XNUMX tx (16,666 * 1.07)。
無限の彼方へ
- きらめくものはすべてゴールド/ 1ではありません。証明段階で必要な計算能力とメモリの量は、文字通り衝撃的です。 特にbarryWhiteHatのバージョンでは、複雑さの一部がチェーンから外されます。 バリー書き込み 「7 GBのRAMと20 GBのスワップスペースを備えたラップトップでは、20秒あたりXNUMXのトランザクションを集約するのに苦労しています。」。 まあ、目標が毎秒17,832 txなら…笑 これにより、重要な並列計算の課題が生じます。 しかし、トランザクションあたりの平均$コストが通常のSNARKなしのオプションよりはるかに安い場合、ゲームはキャンドルの価値があります。
- きらめくものはすべて金ではありません。2.関連するデータ可用性の問題があります。 ツリーのルートのみがコントラクトに保存されるため、ツリーのバージョン全体(または同じ、トランザクション履歴全体)が常に利用可能であることを確認する必要があります。 データが利用できない場合、有効な署名付きトランザクションがあっても、中継者は古い状態→トランザクション→新しい状態を証明できないため、何もできません。
- リレーが信頼できず、契約のEtherが外部で同じEtherの価値を持つようにするには(流動性の問題)…ユーザーは、(特定の)リレーに依存することなく、必要なときにスマートコントラクトからお金を引き出せる必要があります。 どうやって? これは、この101の投稿の範囲外ですが、囲まれたリンクでこれについて読むことができます。
- 現在の状態(アドレス、残高、ノンス)をマークルツリーでどのように処理できるかについて、もっと知りたいですか? 葉の追加、更新など? チェックアウト このライブラリ (テストファイル こちら)これを使用する モジュール。 HarryRに感謝します。
- 個人のEthereum-SNARKs環境をセットアップしたいですか? C ++でオフチェーンから始めましょう(セットアップ、証明、検証) こちら。 その後、Zokratesを使用してEthereumに移動できます(忘れないでください、検証のみがチェーンで行われます!)。レポ 始めるためのドキュメント).
- マークルツリーの代わりにRSAアキュムレータを使用するのはどうですか? グーグル 「rsa accumulators ethereum」 始めること…
お楽しみください!
Twitter @マルコデロッシ
- 7
- すべて
- 間で
- 賃貸条件の詳細・契約費用のお見積り等について
- の基礎
- 10億
- 例
- 変化する
- 小切手
- coinbase
- コンピューティング
- コンセンサス
- 縮小することはできません。
- コスト
- 電流プローブ
- 現在の状態
- DApps
- データ
- データセット
- 地方分権化
- 次元
- 分散元帳
- 分散型元帳技術
- 環境
- エーテル
- イーサリアム
- EU
- EV
- 偽
- 最後に
- 名
- 無料版
- function
- ゲーム
- GAS
- GitHubの
- 与え
- ゴールド
- 良い
- でログイン
- 素晴らしい
- ガイド
- ハッシュ
- こちら
- ハイ
- history
- 認定条件
- hr
- HTTPS
- 巨大な
- 何百
- ia
- index
- 情報
- IP
- IT
- ジョブ
- キー
- ノートパソコン
- 大
- つながる
- 元帳
- レベル
- LG
- 図書館
- 流動性
- リスト
- 主流
- ゲレンデマップ
- ミディアム
- 百万
- 鉱夫
- お金
- ヶ月
- 一番人気
- 名
- ネットワーク
- ノード
- 番号
- 業務執行統括
- 注文
- その他
- 所有者
- 支払う
- のワークプ
- プレイヤー
- 人気
- 電力
- プライベート
- 秘密鍵
- 演奏曲目
- プロジェクト
- 証明
- 証明する
- 公共
- 公開鍵
- 再生タイヤ
- RSA
- ルール
- ランニング
- 安全な
- 節約
- スケーラビリティ
- 規模
- スケーリング
- 科学
- セキュリティ
- セッションに
- シェアする
- shared
- ショート
- 簡単な拡張で
- サイズ
- 眠る
- スマート
- スマート契約
- スマートフォン
- So
- ソフトウェア
- 固い
- ソリューション
- 解決する
- スペース
- 支出
- start
- 開始
- 都道府県
- 米国
- 成功した
- システム
- テクノロジー
- test
- 時間
- トークン
- top
- 急流
- トランザクション
- 取引
- 信頼
- 更新版
- users
- 値
- Verification
- ビザ
- W
- 誰
- 言葉
- 仕事
- 作品
- 価値
- X