BitVMの原理解析とその最適化の考察

業界速報

2024-03-25 18:19:17

コレクション

BitVM技術の探索はまだ始まったばかりで、今後はビットコインの拡張を実現し、ビットコインエコシステムを繁栄させるために、さらなる最適化の方向性を探求し実践していく予定です。

共有する

WeChatでQRコードをスキャン

原文标题：BitVM とその最適化に関する考察

原文作者: lynndell, mutourend.

1.はじめに

ビットコインは、分散型で安全かつ信頼できるデジタル資産です。しかし、支払いおよびその他のアプリケーションのスケーラブルなネットワークになるには重大な制限があります。ビットコインのスケーラビリティの問題は、その誕生以来注目されてきました。ビットコインのUTXOモデルは、各取引を独立したイベントとして扱い、状態を持たないシステムを生じさせ、複雑で状態に依存する計算を実行する能力が欠如しています。したがって、ビットコインは単純なスクリプトやマルチシグ取引を実行できますが、状態を持つブロックチェーンプラットフォームで一般的な複雑で動的な契約の相互作用を促進するのが難しいです。この問題は、ビットコイン上で構築された分散型アプリケーション（dApps）や複雑な金融ツールの範囲を著しく制限しており、状態モデルプラットフォームは機能豊富なスマートコントラクトを展開および実行するためのより多様な環境を提供します。

ビットコインのスケーラビリティに関しては、主に状態チャネル、サイドチェーン、クライアント検証などの技術があります。その中で、状態チャネルは安全で多様な支払いソリューションを提供しますが、任意の複雑な計算を検証する能力には限界があります。この制限は、複雑で条件付きのロジックや相互作用が必要なさまざまなシナリオでの適用を減少させます。サイドチェーンは広範なアプリケーションをサポートし、ビットコインの機能を超えた多様性を提供しますが、セキュリティは低くなります。このセキュリティの差は、サイドチェーンが独立したコンセンサスメカニズムを採用しているためであり、これらのメカニズムはビットコインのコンセンサスメカニズムの堅牢性には及びません。クライアント検証は、ビットコインのUTXOモデルを使用してより複雑な取引を処理できますが、ビットコインとの双方向の検証および制約能力がないため、そのセキュリティはビットコインよりも低くなります。クライアント検証プロトコルのオフチェーン設計は、サーバーまたはクラウドインフラストラクチャに依存しており、これが集中化を引き起こしたり、妥協されたサーバーを通じて潜在的な検閲を引き起こす可能性があります。クライアント検証のオフチェーン設計は、ブロックチェーンインフラストラクチャにさらなる複雑性をもたらし、スケーラビリティの問題を引き起こす可能性があります。

2023年12月、ZeroSyncプロジェクトの責任者であるRobin Linusは、「BitVM：ビットコイン上で何でも計算する」というタイトルのホワイトペーパーを発表し、ビットコインのプログラマビリティを向上させるための考察を引き起こしました。この論文は、ビットコインネットワークのコンセンサスを変更することなく、チューリング完全なビットコイン契約ソリューションを実現する方法を提案し、複雑な計算をビットコイン上で検証できるようにします。BitVMは、ビットコインスクリプトとTaprootを最大限に活用し、楽観的ロールアップを実現します。Lamport署名（別名ビットコミットメント）に基づいて、ビットコインの2つのUTXO間にリンクを構築し、状態を持つビットコインスクリプトを実現します。Taprootアドレス内に大規模なプログラムをコミットし、オペレーターと検証者が大量のオフチェーン相互作用を行い、オンチェーンでの足跡は非常に小さくなります。両者が協力すれば、任意の複雑な状態を持つオフチェーン計算を実行でき、オンチェーンに痕跡を残すことはありません。両者が協力しない場合、争いが発生した際にはオンチェーンで実行する必要があります。したがって、BitVMはビットコインの潜在的なユースケースを大幅に拡大し、ビットコインを通貨としてだけでなく、さまざまな分散型アプリケーションや複雑な計算タスクの検証プラットフォームとしても機能させることができます。

しかし、BitVM技術はビットコインのスケーラビリティにおいて非常に優れていますが、まだ初期段階にあり、効率とセキュリティに関していくつかの問題があります。例えば：（1）チャレンジと応答には複数回の相互作用が必要で、手数料が高く、チャレンジサイクルが長い；（2）Lamportの一回限りの署名データが長く、データの長さを短縮する必要がある；（3）ハッシュ関数の複雑さが高く、ビットコインフレンドリーなハッシュ関数が必要で、手数料を削減する；（4）既存のBitVM契約は大規模であり、ビットコインブロックの容量は限られているため、scriptless scriptsを利用してScriptless Scripts BitVMを実現し、ビットコインブロックのスペースを節約し、同時にBitVMの効率を向上させる；（5）既存のBitVMは許可モデルを採用しており、連合メンバーのみがチャレンジを開始でき、2者間に限定されているため、permissionlessの多者チャレンジモデルに拡張し、信頼仮定をさらに小さくする必要があります。これに対して、本論文ではBitVMの効率とセキュリティをさらに向上させるためのいくつかの最適化のアイデアを提案します。

2.BitVMの原理

BitVMはビットコインのオフチェーン契約として位置付けられ、ビットコイン契約機能の推進を目指しています。現在のビットコインスクリプトは完全に無状態であるため、ビットコインスクリプトが実行されると、その実行環境は各スクリプトの後にリセットされます。スクリプト1とスクリプト2が同じx値を持つ原生的な方法は存在せず、ビットコインスクリプトはその方法を原生的にサポートしていません。しかし、既存のopcodesを利用して、Lamportの一回限りの署名を通じてビットコインスクリプトを状態を持たせることができます。たとえば、script 1とscript 2のxを同じ値に強制することができます。参加者が相互に矛盾するx値に署名した場合、罰則を科すことができます。BitVMプログラムの計算はオフチェーンで行われ、計算結果の検証はオンチェーンで行われます。現在のビットコインブロックは1MBの制限があり、計算の検証が過度に複雑な場合、OP技術を利用してチャレンジ応答モードを採用し、より高い複雑さの計算検証をサポートします。

Optimistic RollupやMATT提案（Merkelize All The Things）に似て、BitVMシステムは詐欺証明とチャレンジ-応答プロトコルに基づいていますが、ビットコインのコンセンサスルールを変更する必要はありません。BitVMの基盤となる原語はシンプルで、主にハッシュロック、タイムロック、大規模なTaprootツリーに基づいています。

証明者はバイト単位でコミットしますが、オンチェーンでのすべての計算を検証することは非常に高価です。したがって、検証者は証明者の虚偽の主張を簡潔に反駁するために、一連の巧妙に設計されたチャレンジを実行します。証明者と検証者は、争いを解決するために一連のチャレンジと応答取引を事前に署名し、ビットコイン上での一般的な計算検証を可能にします。

BitVMの重要なコンポーネントは以下の通りです：

回路コミットメント：証明者と検証者はプログラムを大規模なバイナリ回路にコンパイルします。証明者はTaprootアドレス内でその回路をコミットし、そのアドレス下の各リーフスクリプトは、その回路内の各論理ゲートに対応します。コアはビットコミットメントに基づいて論理ゲートコミットメントを実現し、回路コミットメントを実現します。
チャレンジと応答：証明者と検証者は、チャレンジ-応答ゲームを実現するために一連の取引を事前に署名します。理想的には、この相互作用はオフチェーンで行われ、証明者が協力しない場合はオンチェーンで実行されることもあります。
曖昧な罰則：証明者が不正確な主張を行った場合、検証者がチャレンジに成功すると、証明者の預金を奪うことができ、証明者の悪行を挫くことができます。

3.BitVMの最適化

3.1 ZKに基づくOP相互作用回数の削減

現在、2つの主要なロールアップがあります：ZKロールアップとOPロールアップ。ZKロールアップは、ZK証明の有効性検証に依存しており、正しく実行された暗号証明であり、その安全性は計算の複雑さの仮定に依存しています。OPロールアップは、詐欺証明に依存しており、提出された状態がすべて正しいと仮定し、チャレンジサイクルを通常7日間設定します。その安全性は、システム内に少なくとも1つの誠実な当事者が不正確な状態を検出し、詐欺証明を提出できると仮定しています。BitVMのチャレンジプログラムの最大ステップ数を2^{32}と仮定すると、必要なメモリは2^{32} * 4バイト、約17GBです。最悪の場合、約40ラウンドのチャレンジと応答が必要で、約半年の時間がかかり、総スクリプトは約150KBです。この場合、インセンティブは非常に不足していますが、実際にはほとんど発生しません。

BitVMのチャレンジ回数を削減するためにゼロ知識証明を使用し、BitVMの効率を向上させることを検討します。ゼロ知識証明理論によれば、データDataがアルゴリズムFを満たす場合、証明proofは検証アルゴリズムVerifyを満たし、検証アルゴリズムはTrueを出力します。データDataがアルゴリズムFを満たさない場合、証明proofも検証アルゴリズムVerifyを満たさず、検証アルゴリズムはFalseを出力します。BitVMシステムでは、チャレンジャーが証明者が提出したデータを認めない場合、チャレンジを開始します。

アルゴリズムFについては、二分法で分解し、2^n回必要と仮定すると、エラー点を見つけることができます。アルゴリズムの複雑さが高すぎる場合、nが大きくなり、完了するまでに時間がかかります。しかし、ゼロ知識証明の検証アルゴリズムVerifyの複雑さは固定されており、公開証明proofと検証アルゴリズムVerifyの全過程を通じて、出力がFalseであることがわかります。ゼロ知識証明の利点は、検証アルゴリズムVerifyを開くために必要な計算の複雑さを低くすることであり、元のアルゴリズムFを開くための二分法よりもはるかに低くなります。したがって、ゼロ知識証明を利用して、BitVMのチャレンジは元のアルゴリズムFではなく、検証アルゴリズムVerifyに対して行われ、チャレンジのラウンド数を削減し、チャレンジサイクルを短縮します。

最後に、ゼロ知識証明の有効性と詐欺証明は異なる安全仮定に依存していますが、両者を組み合わせてZK詐欺証明を構築し、オンデマンドZK証明を実現できます。フルZKロールアップとは異なり、各単一の状態変化のためにZK証明を生成する必要はなく、オンデマンドモデルでは、チャレンジがある場合にのみZK証明が必要であり、全体のロールアップ設計は依然として楽観的です。したがって、生成された状態が有効であると仮定され、誰かがその状態に対してチャレンジするまで有効と見なされます。ある状態にチャレンジがなければ、ZK証明を生成する必要はありません。しかし、参加者がチャレンジを開始した場合、チャレンジブロック内のすべての取引の正確性に対してZK証明を生成する必要があります。将来的には、単一の論争のある命令に対してZK詐欺証明を生成し、常にZK証明を生成する計算コストを回避することを探求します。

3.2 ビットコインフレンドリーな一回限りの署名

ビットコインネットワークでは、コンセンサスルールに従った取引が有効な取引ですが、コンセンサスルールに加えて、standardnessルールも追加されています。ビットコインノードは、標準取引のみを中継し、有効だが非標準の取引は、鉱夫と協力することでのみパッケージ化されます。

コンセンサスルールによれば、レガシー（すなわち非Segwit）取引の最大サイズは1MBであり、ブロック全体を満たすことができます。しかし、レガシー取引のstandardnessの上限は100kBです。コンセンサスルールによれば、Segwit取引の最大サイズは4MBであり、weight limitです。しかし、Segwit取引のstandardnessの上限は400kBです。

Lamport署名はBitVMの基礎コンポーネントであり、署名と公開鍵の長さを短縮し、取引データを減少させ、手数料を削減するのに役立ちます。Lamportの一回限りの署名はハッシュ関数（例えば、一方向の置換関数f）を使用する必要があります。Lamportの一回限りの署名スキームでは、メッセージの長さはvビット、公開鍵の長さは2vビット、署名の長さも2vビットです。署名と公開鍵が長いため、大量のストレージガスを消費します。したがって、署名と公開鍵の長さを短縮するために、類似の機能を持つ署名スキームを探す必要があります。Lamportの一回限りの署名と比較して、Winternitzの一回限りの署名は署名と公開鍵の長さを大幅に短縮しますが、署名と検証の計算の複雑さが増加します。

Winternitzの一回限りの署名スキームでは、特殊な関数Pを使用してvビットのメッセージを長さnのベクトルsにマッピングします。sの各要素の値は{0,…, d}です。Lamportの一回限りの署名スキームはd=1の特殊な場合のWinternitzの一回限りの署名スキームです。Winternitzの一回限りの署名スキームでは、n、d、vの関係は次のようになります：n ≈ v / log2(d + 1)。d=15の場合、n ≈ (v / 4) + 1です。n個の要素を含むWinternitz署名は、Lamportの一回限りの署名スキームの公開鍵の長さと署名の長さを4倍短くします。しかし、検証の複雑さは4倍増加します。BitVMではd=15、v=160、f=ripemd160(x)を使用してWinternitzの一回限りの署名を実現し、ビットコミットメントのサイズを50％削減し、BitVMの取引手数料を少なくとも50％削減します。将来的には、既存のWinternitzビットコインスクリプトの実装を最適化し、ビットコインスクリプトで表現されたよりコンパクトな一回限りの署名スキームを探求します。

3.3 ビットコインフレンドリーなハッシュ関数

コンセンサスルールによれば、P2TRスクリプトの最大サイズは10kBであり、P2TRスクリプトウィットネスの最大サイズは最大Segwit取引サイズと同じく4MBです。しかし、P2TRスクリプトウィットネスのstandardnessの上限は400kBです。

現在のビットコインネットワークではOP_CATがサポートされておらず、文字列を連結してMerkleパスの検証を行うことができません。したがって、既存のビットコインスクリプトを使用して、スクリプトサイズとスクリプトウィットネスサイズが最適な方法で、ビットコインフレンドリーなハッシュ関数を実現し、Merkle inclusion proofの検証機能をサポートする必要があります。

BLAKE3はBLAKE2ハッシュ関数の最適化版であり、Bao treeモードを導入しています。BLAKE2 s-basedと比較して、圧縮関数のラウンド数は10から7に減少しました。BLAKE3ハッシュ関数は、その入力を1024バイトサイズの連続チャンクに分割し、最後のチャンクは短くなる可能性がありますが、空ではありません。チャンクが1つだけの場合、そのチャンクはルートノードであり、その木の唯一のノードです。これらのチャンクをバイナリツリーのリーフノードとして配置し、各チャンクを独立して圧縮します。

BitVMをMerkle inclusion proofの検証シーンで使用する場合、ハッシュ計算の入力は2つの256ビットハッシュ値を連結したものであり、ハッシュ計算の入力は64バイトです。BLAKE3ハッシュ関数を使用する場合、この64バイトは単一のチャンク内に配置でき、全体のBLAKE3ハッシュ計算は単一のチャンクに対して圧縮関数を1回適用するだけで済みます。BLAKE3の圧縮関数では、7回のラウンド関数と6回の置換関数を実行する必要があります。

現在、BitVMではu32値に基づくXOR、モジュラー加算、ビット右シフトなどの基本的な演算が完了しており、ビットコインスクリプトで実装されたBLAKE3ハッシュ関数を簡単に組み立てることができます。スタック内の4つの分離されたバイトを使用してu32ワードを表現し、BLAKE3に必要なu32加算、u32ビット単位のXOR、およびu32ビット単位の回転を実現します。現在、BLAKE3ハッシュ関数のビットコインスクリプトは約100kBであり、トイバージョンのBitVMを構築するのに十分です。

さらに、これらのBLAKE3コードを分割することで、検証者と証明者がチャレンジ-応答ゲームの実行を完全に実行するのではなく、2つに分けることで、必要なオンチェーンデータを大幅に削減できます。最後に、ビットコインスクリプトでKeccak-256、Grøstlなどのハッシュ関数を実装し、最もビットコインフレンドリーなハッシュ関数を選択し、他の新しいビットコインフレンドリーなハッシュ関数を探求します。

3.4 Scriptless Scripts BitVM

Scriptless Scriptsは、Schnorr署名を使用してオフチェーンでスマートコントラクトを実行する方法です。Scriptless Scriptsの概念はMimblewimbleから生まれ、カーネルおよびその署名を除いて、永続的なデータを保存しません。

Scriptless Scriptsの利点は、機能、プライバシー、効率です。

機能：Scriptless Scriptsはスマートコントラクトの範囲と複雑さを増加させることができます。ビットコインスクリプトの能力は、ネットワークで有効化されているOP_CODESの数に制限されますが、Scriptless Scriptsはスマートコントラクトの仕様と実行をオンチェーンから、設計された契約参加者の議論に移行し、新しいオペコードを有効にするためにビットコインネットワークのフォークを待つ必要がありません。
プライバシー：スマートコントラクトの仕様と実行をオンチェーンからオフチェーンに移行することで、プライバシーが向上します。オンチェーンでは、契約の多くの詳細がネットワーク全体に共有され、これには参加者の数やアドレス、送金額などの詳細が含まれます。スマートコントラクトをオフチェーンに移すことで、ネットワークは参加者が契約条件が満たされ、関連する取引が有効であることに同意したことを知るだけです。
効率：Scriptless Scriptsは、オンチェーンの検証とストレージのデータ量を最小限に抑えます。スマートコントラクトをオフチェーンに移すことで、全ノードの管理コストが削減され、ユーザーの取引手数料も削減されます。

Scriptless Scriptsは、ビットコイン上で暗号プロトコルを設計する方法であり、明示的なスマートコントラクトの実行を回避します。コアのアイデアは、スクリプトを使用して機能を実現するのではなく、暗号アルゴリズムを使用して期待される機能を実現することです。アダプター署名とマルチシグ署名は、Scriptless Scriptsの原始的な構築基石です。Scriptless Scriptsを使用することで、通常の取引よりも小さな取引を実現し、取引手数料を削減できます。

Scriptless Scriptsを利用して、Schnorrのマルチシグ署名とアダプター署名を使用することで、BitVMスキームのようにハッシュ値やハッシュプリイメージを提供する必要がなく、BitVM回路内の論理ゲートコミットメントを実現することができ、BitVMスクリプトのスペースを節約し、BitVMの効率を向上させることができます。既存のScriptless ScriptsスキームはBitVMスクリプトのスペースを削減できますが、証明者とチャレンジャーが大量の相互作用を持つ必要があります。将来的には、このスキームを改善し、Scriptless Scriptsを具体的なBitVM機能モジュールに導入することを試みます。

3.5 無許可の多者チャレンジ

現在のBitVMチャレンジがデフォルトで許可を必要とする理由は、ビットコインのUTXOが一度しか実行できず、悪意のある検証者が誠実な証明者に対してチャレンジを行うことでその契約を「浪費」できるためです。現在のBitVMは2者間チャレンジモデルに制限されています。悪意のある証明者は、自分が制御する検証者を使用して同時にチャレンジを開始し、「浪費」することで悪行を成功させ、他の検証者はその行為を阻止できません。したがって、ビットコインの基盤の上に、無許可の多者OPチャレンジプロトコルを研究し、BitVMの既存の1-of-n信頼モデルを1-of-Nに拡張する必要があります。ここで、Nはnよりもはるかに大きいです。さらに、チャレンジャーと証明者が共謀したり、悪意のあるチャレンジが契約を「浪費」する問題を解決する必要があります。最終的には、信頼をより小さくするBitVMプロトコルを実現します。

無許可の多者チャレンジは、許可リストなしで誰でも参加できることを許可します。これは、ユーザーが信頼できる第三者の参加なしにL2から資金を引き出すことができることを意味します。さらに、OPチャレンジプロトコルに参加したいユーザーは、無効な引き出しを疑問視し、削除することができます。

BitVMを無許可の多者チャレンジモデルに拡張するには、以下の攻撃を解決する必要があります：

ウィッチ攻撃：攻撃者が複数の身分を偽造して争いのチャレンジに参加しても、単一の誠実な参加者が争いに勝つことができます。誠実な参加者が正しい結果を守るコストが攻撃者の数に対して線形関係にある場合、大量の攻撃者が関与する際に、誠実な参加者が争いに勝つために必要なコストは非現実的になり、ウィッチ攻撃にさらされやすくなります。論文Permissionless Refereed Tournamentsでは、ゲームのルールを変更する争いの解決アルゴリズムが提案されており、単一の誠実な参加者が争いに勝つコストが対戦相手の数に対して対数的に増加し、線形的には増加しないようにしています。
遅延攻撃：特定の悪意のある者またはグループが、資産をL1に引き出すなどの正しい結果の確認を妨げたり遅延させたりするために、何らかの戦略に従うことがあります。チャレンジャーに事前に担保を要求することで、この問題を緩和できます。チャレンジャーが遅延攻撃を行った場合、その担保を没収します。しかし、攻撃者が遅延攻撃を追求するために一定の限度内で担保を犠牲にすることを望む場合、遅延攻撃の影響を軽減するための対策が必要です。論文BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocolで提案されたアルゴリズムにより、攻撃者がどれだけの担保を失うことを望んでも、最悪の場合の攻撃は一定の上限の遅延しか引き起こさないようになります。

将来的には、ビットコインの特性に適した、上記の攻撃問題に抵抗できるBitVMの無許可多者チャレンジモデルを探求します。

4.結論

BitVM技術の探求はまだ始まったばかりであり、今後はビットコインのスケーラビリティを実現し、ビットコインエコシステムを繁栄させるためのさらなる最適化の方向性を探求し、実践していきます。

参考文献