TechFlow Logo
ログイン/ 登録
ETHガス
Gwei
恐怖
gas
ビットコインにおける汎用計算の道:ビットコインのスケーリングのためのSTARKの構想

ビットコインにおける汎用計算の道:ビットコインのスケーリングのためのSTARKの構想

2024.07.29
共有先
本稿では、ビットコイン上で汎用計算を実現するタスクと、それに含まれる各ステップについて議論する。

執筆:StarkWare

翻訳:Starknet 中文コミュニティ

1. はじめに

本稿では、ビットコイン上で汎用計算を実現するという課題と、その実現に必要なステップについて考察します。実際、任意のロジックをビットコインスクリプト上で計算できるようにすることは魅力的な目標です。なぜなら、これによりビットコインはノンカストディアプリケーションや分散型金融の領域へと進出できるからです。

かつて、二つの重大な制限 —— ビットコインスクリプトの長さ制限とオペコードの表現力不足 —— のため、ビットコイン上での汎用計算は事実上不可能と考えられていました。前者は短いスクリプト以外の取引を禁止しており、後者はスクリプトオペコードが計算可能な内容を制限しています。この二つの制約は、多くのアプリケーションがこれらの条件下で実現できないという厳しい状況をもたらしました。

しかし近年、状況は大きく改善されています。実際に、2021年のTaprootアップグレードによってスクリプト長の制限が撤廃され、ビットコインスクリプトは大幅に長くすることが可能になりました(実際には、Taprootスクリプトではスクリプトの一部のみをオンチェーンで支払うことも可能ですが、本稿ではこの機能には触れません)。また、オペコードの表現力不足を解決するために、単一のシンプルなオペコードが無限の表現力を効果的に実現できることもわかりました。

そのオペコードがOP_CATであり、これは2012年からビットコインスクリプト内で無効化されています。非常にシンプルなオペコードで、スタック上の要素を連結するだけのものであり、ソフトフォークによって非侵襲的にビットコイン上でアクティブ化でき、わずか13行のコードで実装可能です。この一見地味なオペコードからこれほど大きな力が生まれるとは信じがたいことですが、本稿の主目的はまさにその点を詳しく説明することにあります。

以下では、ビットコインにおける計算プロセスについて、その実現方法と制限から深く掘り下げます。

次に、CovenantとSTARK証明という二つのツールを概観し、これらがビットコインスクリプト内で動作すれば、ビットコイン上で汎用計算が可能になることを示します。さらに本稿では、STARK証明のおかげで、このような計算にさらに有益な属性を与えることができることを論じます。

  • 拡張性 — オンチェーン取引処理と計算が可能になり、手数料は極めて低くなる。

  • 表現力 — ロジックはビットコインスクリプトよりも強力な異なるプログラミング言語で記述できる。これはビットコインプログラミングの人間的使いやすさと安全性にとって極めて重要である。

  • オンチェーン安全性 — 計算の種類に関わらず、ビットコインスクリプトは委託された計算の数学的証明のみを検証する。

  • 柔軟性 — ビットコイン上の計算はグローバルな状態を保存できるため、多数のアプリケーションが実現可能になる。

最後に、OP_CATがどのようにして上記のツールを実現するのか、そして我々が行った取り組みや今後の方向性についても述べます。

注意:本稿では技術的な詳細を簡略化し、明確な思考モデルを提供することを目的としています。実際に提示されたアイデアを実装する際には、「細部が鍵となる」ことに留意してください。

2. UTXOモデルとロックスクリプト

本節では、各UTXOがロックスクリプトによって保護されるビットコインのUTXOモデルについて簡単に概観します。すでにご存知の方は次の節に進んでください。

ビットコイン取引を理解する第一歩は、図1に示すように、それらが未使用取引出力(UTXO)モデルに基づいて構成・処理されていることに気づくことです。ビットコイン取引は複数の入力と出力を有することができ、各出力は別の取引によって消費可能な一定量のビットコインを表します。対応して、取引の入力は別のビットコイン取引の出力の消費を意味します。もちろん、入力のビットコイン総額と出力のビットコイン総額はほぼ等しくなければなりません(差額はマイナーへの手数料となります)。

図1:UTXOモデルにおける取引。各取引の入力および出力は一定量のビットコインに関連付けられ、出力の合計金額は入力の金額を超えてはならない。未使用取引出力(UTXO)は青色で示されている。

各取引出力はロックスクリプト(scriptPubKey)によってロックされており、これは与えられた入力(scriptSig)を受け入れまたは拒否します(これは支出者によって提供されます)。したがって、ある未使用取引出力(UTXO)から資金を移動したい場合は、正しいscriptSigを生成し、そのUTXOを自身が作成する取引の入力として含める必要があります。

デフォルトでは、ロックスクリプトはハードコードされた公開鍵に基づいてデジタル署名を検証するだけであり、これがロックされたビットコインの所有権を定義します。より一般的に言えば、UTXOがあるときは常に、正しいscriptSigを提供できる者が、対応するロックスクリプトの背後にあるビットコインの所有者であると言えます。したがって、各ビットコイン所有者の総残高は、その所有者に関連するすべてのUTXOの累積によって決定されます(例えば、同じ人物がデジタル署名を行ったすべてのUTXO)。

3. ビットコインスクリプトの制限

前節では、ロックスクリプトの一般的な枠組みと、それがビットコイン取引およびビットコイン自体とどう関係しているかを概観しました。本節では、ロックスクリプト自体とその構成要素に焦点を当てます。

ビットコインのロックスクリプトはForthに似たスタックベースの言語で書かれ、これを「ビットコインスクリプト」と呼びます。ビットコインスクリプトにはループがないため、スクリプトの実行時間はその長さに比例するため、オペコードの数でスクリプトのコストを測定します。図2では、二つの入力値の和が12であるかをチェックする簡単なプログラムの模式図を示しています。

図2*:二つの入力値の和が12であるかをチェックする単純なプログラム。プログラムの実行は、scriptSigとロックスクリプト自体を結合し、左から右へオペコードを処理することで行われる。scriptSigはスタックに要素をプッシュするだけである。(a) 計算の最初のステップ。(b)* 計算途中。(c) 計算の最終ステップ(ロックスクリプトが入力を承認)。

ここで強調すべきは、ビットコインスクリプトには多くの制限があり、これにより簡単なロジックの開発さえ非常に困難、あるいはまったく不可能になることです。これらの制限には以下が含まれます。

  • スタックサイズは最大1000要素まで。

  • 乗算オペコードがない(事実上、31バイト整数の乗算でも約1万4千個のオペコードが必要)。

  • Pay2Taproot出力タイプ(Taprootアップグレード後)では、単一取引に収容可能なオペコードの総数はブロック全体を埋める程度の約400万個まで、他の出力タイプではわずか1万個。

  • 算術演算(加算、減算)は4バイト要素に限定される。

最後に述べた4バイト制限は特に問題です。つまり、暗号操作に必要な20バイト以上の長い要素を変更できないということです。

例えば、データを連結して暗号操作を適用するという非常に一般的な操作は、暗号オペコードを無視し、4バイト要素の配列で表されるデータに対する操作としてシミュレートする以外では不可能です。後者の方法はコストが非常に高く、単一のハッシュ操作をシミュレートするのに数十万のオペコードが必要になる可能性があります。

最後に、ビットコインスクリプトの開発は難しく、コードが自然とエラーや脆弱性を生み出しやすいことも指摘しておきます。

4. ビットコインスクリプトにおける状態保持の課題

前節ではビットコインスクリプトにはまだ多くの不足があることを示しましたが、私たちが考える最大の制限は、支出者の入力しか読み取れないという点です。これは二つの深刻な制限を意味します。

  • ビットコインスクリプトは状態を持たない。つまり、ストレージユニットのデータを読み書きできない。イーサリアム仮想マシンに例えるなら、SLOAD/SSTOREのようなオペコードがなく、これは汎用計算の基本機能である。

  • ビットコインスクリプトはビットコインの支出方法を強制できない(少数の例外を除く)。これはCovenantで解決可能で、Covenantはロックスクリプトにその能力を与える。(例として、オンチェーン金庫を想像できます。これは支出を許可されたアドレスを制限することで機能します。もっと広く言えば、Covenantは非常に強力なツールで、幅広い応用が可能である。)

その後、Covenantを構築することで、状態性を得られることを見ていきます。直感的には、Covenantを使って取引データ自体にストレージの読み書きを模倣できるからです。

実際、上記の内容ではビットコインスクリプトとその複雑性の全貌を網羅していません。しかし少なくとも、ビットコインスクリプトの記述は容易ではないことは確かです。ビットコインスクリプトには非常に厳格な制限があります。

  • スタックサイズは1000要素を超えないこと。

  • 乗算などの単純な操作を多数のオペコードでシミュレートしなければならない。一般に、煩雑なビットコインスクリプト言語でロジックを記述する必要がある。

  • 4バイト形式でエンコードされた要素で操作しなければならない。特に、暗号オペコードの入力に対して操作や変更ができない。

  • ロジックは状態を保存できず、単一の取引に適応しなければならない。

  • 認証後、ロジックはビットコインの支出方法を制御できない。

さらに、上記の制限に従ってコードを記述すると、エラーや脆弱性が発生しやすくなります。

非常に単純なアプリケーション(例:支払い)は上記の制限を満たせますが、少しでも複雑なアプリケーションは障壁にぶつかります。以下では、CovenantとSTARK証明がこれらの制限を打破する方法を学びます。さらに、OP_CATがビットコインスクリプトに上記の機能を実現するのにどう貢献するかも議論します。

5. Covenantによるビットコイン上でのスマートコントラクト

本節では、ビットコインのCovenantがどのようにロジックの状態を保持するか、そしてより一般的に、ビットコイン上の「スマートコントラクト」とはどのようなものかを解説します。ここで言うスマートコントラクトとは、一連の関数を含む何らかの状態を持つロジックであり、事前に定義されたルールに従って関数を呼び出すことで、状態を別の有効な状態に遷移させることができます。

より具体的には、ビットコインコントラクトには以下の機能が必要です。

  • 永続的なロジックと状態

  • ロジック/状態の変化を制御する能力

前述の通り、上記の機能はCovenantによって実現可能です。思い出してください。デフォルトでは、ロックスクリプトは直接の入力データ(scriptSig)しか読めません。しかし、Covenantを使うと、ロックスクリプトは支出者取引のすべてのデータフィールドと、ロックスクリプトが存在する取引のデータフィールド、さらには他の取引のデータも読めるようになります。図3は、Covenant使用時にロックスクリプトがアクセス可能なさまざまな部分を示しています。

図3:ロックスクリプト(鍵で可視化)がアクセス可能ないくつかのデータフィールド(赤矢印)。支出者取引のデータフィールドに加え、ロックスクリプトが存在する取引(tx1)のデータフィールド、および支出者取引が同時に消費する別の取引(tx2)のデータフィールドにもアクセス可能。

上述のCovenantがあれば、ビットコイン上で汎用スマートコントラクトを構築できると私たちは考えます。実際、一般的な方法は取引データ自体に状態をエンコードし、その新しい値への遷移の有効性をチェックすることです。そのため、取引は二つの出力を持つことになります。

  • 第一の出力はコントラクトのロジック(ロックスクリプト経由)とコントラクトにロックされた資金を保持。

  • 第二の出力はスマートコントラクトの現在の状態を保持。このUTXOのロックスクリプトは状態のみを保持し、決して消費されることはない(ロックされたビットコインは実質的に0)。

ロックスクリプトのロジックは以下のルールを実行します。

  • 支出者取引は完全に同じ形式でなければならない(二つの出力のみで、すべての資金が第一の出力にロックされている)。

  • 第一の出力は同じロックスクリプトロジックでなければならない。

  • 第二の出力は有効な状態でなければならない。

  • 現在のロックスクリプトに提供された入力は、現在の状態から新しい状態への遷移が有効であることをロックスクリプトに信じさせるものでなければならない(有効性はロジック設計者が定義)。

図4はこの構造の模式図です。Weikeng Chenが述べたように、この構造には正式な名称を提案しようとする動きが多数ありますが、「状態守車(state caboose)」が有力な候補として浮上しています。守車(caboose)とは貨物列車の末尾に連結される鉄道車両で、乗務員の専用車両および作業スペースです。

図4:Covenantを用いてビットコイン上に実装されたスマートコントラクト。「状態守車」デザインパターンに従う。ロックスクリプトは、支出者取引が同じ形式とロックスクリプトを持ち、前の状態Sから有効な新しい状態S'への遷移が有効であることを保証する。

簡単な例として、単純なカウンタースマートコントラクトを想像できます。このコントラクトの状態は、支出者が提供する値で常に増分され、実質的に「累積」関数を呼び出します。このカウンタースマートコントラクトを図5に示します。

図5:入力(scriptSig)を加算することで状態に累積していく単純なスマートコントラクト。

最後に、ユーザーが「コントラクトを呼び出し」、コントラクトを新しい有効な状態に遷移させるには、毎回新しい支出者取引を作成する必要があることを指摘します。イーサリアムスマートコントラクトとは異なり、ビットコインスマートコントラクトは本質的に逐次的であり、取引は現在の状態と新しい状態の両方をコミットしなければなりません。ビットコイン上でスマートコントラクトを構築する際には、この逐次的特性を考慮する必要があります。この制限を緩和するスキームも存在しますが、本稿ではそれらには触れません。

まとめると、Covenantによりビットコイン上でスマートコントラクトが可能になり、理論的には計算を十分な数の取引に分割すれば、任意の長さの計算が可能になります。しかし、Covenantだけを使用しても、スタックサイズ制限、オペコード数の制限、およびビットコインスクリプト言語の制約に従ってプログラミングしなければならないという、ビットコインスクリプトの大部分の制限は依然として受けます。

以下では、STARK証明システムが、ビットコイン上の計算のブロックチェーン負荷を削減し、まったく異なる言語でスクリプトを記述できるようにすることで、上記の制限をどう緩和するかを探ります。このアプローチにより、プログラミングの効率性と安全性が大幅に向上します。

6. ビットコイン STARK 検証器

本節の目的は、ビットコイン上で計算を行う際に、ビットコインスクリプトによる実際の計算量を最小限に抑える方法を考察することです。私たちの一般的なアプローチは計算の委託で、計算をオフチェーンで行う(複数のエンティティが関与する可能性がある)もので、検証ステップのみがオンチェーンのビットコインスクリプトで行われます。

ここで問題となるのは、オフチェーンの計算が正しく実行されていることをどう保証するかです。実際、この問題の自然な解決策の一つが証明システムです。簡単に言えば、証明システムはアリス(証明者)が「証明」を提供することで、ボブ(検証者)に何らかの文の正しさを納得させる仕組みで、重要な点は以下の通りです。

  • 証明者の助けなしに比べて、検証者ははるかに少ない作業でその文を検証できる。

  • さらに、検証者は、証明者が誤った文を真であると信じ込ませることはできないという保護を受ける。

証明される文は、難問の解法から、より関連性のある計算委託の例まで、ほとんど何でも可能です。具体的には、アリスは f(x)=y をボブに証明し、ボブが f(x) を自分で計算しなくてもよいようにします(図6参照)。

図6:計算委託のための証明システム。証明者は y=f(x) を計算し、検証者にその正しさを信じさせる。重要なのは、もし y≠f(x) であれば、証明者は検証者を騙してその事実を信じさせることはできない点である。

したがって、ブロックチェーン上の計算負荷を削減する方法は、ビットコインスクリプトに証明システムの検証器を実装することです。したがって、スマートコントラクトを呼び出す際、呼び出し側は正しい状態遷移の証明を提供し、ビットコインスマートコントラクトは状態遷移の検証ではなく、その証明の正しさを検証します(図7参照)。

さらに、このアプローチには極めて重要な利点があります。それは、ビットコインスクリプトのロジックがアプリケーションの影響を受けずに固定されたままになるため、エラーの発生リスクが大幅に低下し、監査が容易になる点です。これは単純な事実に基づいています:同一の検証アルゴリズムは、あらかじめ計算する関数を知らなくても、y=f(x) の文や y=g(x) の文を検証できるのです。

図7:Covenantを用いてビットコイン上に実装されたスマートコントラクト。図4の「状態守車」デザインパターンに従うが、検証器を追加。今回は、ロックスクリプトはSからS'への遷移が有効かどうかを直接チェックせず、その遷移が正しいことの証明を検証する。

多くの証明システムが存在しますが、私たちはSTARK証明システム(STARK)を選択しました。なぜなら、以下のような魅力的な特徴を持っているからです。

  • 耐量子安全性

  • 信頼できる設定不要

  • ビットコインに新たな暗号的仮定を導入しない

  • 最も高速に拡張

  • 実戦投入済みで、1兆ドル超の決済で信頼されている

最後に、他の証明システムと比較して⬇️

STARKはビットコインに親和性が高く、その検証器コンポーネントはビットコインスクリプトで実装しやすい。本質的には、STARKが主にハッシュに基づいているため、ペアリングベースの証明と比べて代数演算が非常に少ないからです。

ビットコインスクリプトでは代数演算のコストが高いため、これがSTARKがビットコインに優しい理由を説明しています。さらに、Circle-STARK変種はフィールドが小さいため、特にビットコインに適しています。

したがって、ビットコイン検証器は比較的容易に任意の計算を検証できるため、どの種類の計算を検証するかを選べます。注目すべきは、これはある種のCPU実行であってもよいということです。さらに、CPUの上に高水準プログラミング言語を設計することもできます。そのため、StarkWareではCairoを開発しました。これはRust風で人間的使いやすさと安全性を兼ね備えたプログラミング言語で、効率的な証明と検証のために特別に設計されています。ビットコイン上でCairoの実行を証明することは大きな利点をもたらします。

まとめると、STARK検証器とCovenantを使用することで、ビットコイン上で汎用計算を実現できます。さらに、この計算には以下のような魅力的な付加的特性があります。

  • 拡張性 — オンチェーン取引処理と計算が可能になり、手数料は極めて低くなる。

  • 表現力 — ロジックはビットコインスクリプトよりも強力な異なるプログラミング言語で記述できる。これはビットコインプログラミングの人間的使いやすさと安全性にとって極めて重要である。

  • オンチェーン安全性 — 計算の種類に関わらず、ビットコインスクリプトは委託された計算の数学的証明のみを検証する。

  • 柔軟性 — ビットコイン上の計算はグローバルな状態を保存できるため、多数のアプリケーションが実現可能になる。

7. OP_CATによる連結およびその他の機能

前述の通り、OP_CATは現在無効化されているシンプルなオペコードで、ビットコインスクリプトがスタック上の要素を連結できるようにします。この単純な操作の重要性は過小評価できません。なぜなら、これによりビットコイン上でCovenantとSTARKの両方が実現できるからです。具体的には以下の通りです。

  • STARK — 実際、これは驚くべきことではありません。なぜなら、STARKは実質的にデータを連結してハッシュ計算を行うだけだからです。ハッシュ計算は代数演算とは異なり、ビットコインスクリプトのネイティブ計算なので、コストが大幅に削減されます。STARKの主要なハッシュ計算はMerkleパス検証(図8参照)とFiat-Shamir変換です。(さらに、Circle-STARK変種のフィールドサイズは31バイトで、ビットコインスクリプトの4バイト制限に適合するため、ビットコインに優しいアルゴリズムとなっています。)

  • Covenant — 2021年、Andrew Poelstraは画期的な洞察を示しました。OP_CATはいわゆるSchnorrテクニックによってビットコイン上でCovenantを実現できるというもので、SchnorrアルゴリズムはPay2Taproot出力タイプのデジタル署名です(他の出力タイプでは、Robin Linusが観察した同様のECDSAテクニックを使用可能)。要するに、Covenantを実現するには、支出者取引に関連するデータをスタックに置ける唯一のオペコードであるOP_CHECKSIGを使用する必要があります。このプロセスは単純ではありませんが、いくつかの操作を通じてすべての必要なデータにアクセスできます。

最後の点について、Pay2Taproot出力に状態を保存するにはいくつかの技術的課題があります。ただし、Pay2WitnessScriptHashなどの他の出力タイプを使用して状態を保存することも可能です。これにより、前述の図4および図5に示す「状態守車」技術が生まれ、取引に二つの出力が存在します。

図8:*Merkleパス検証。ハッシュと文字列連結操作を含む。Merkleパスの各部分(青い文字列)が連結され、対応するハッシュ処理が行われる。その後、Merkleルートとの等価性がチェックされる。OP_CATオペレーションは||と記述される。*

8. 現状と将来

Weikeng ChenとPinghzou Yuanが率いるオープンソースプロジェクトとして、私たちは共同でBitcoin Wildlife Sanctuaryの建設に努めています。主なプロジェクトは二つあります。

この取り組みを通じて、我々の目標はビットコインに効率的で安全、開発者にやさしいOP_CATスマートコントラクトをもたらすことです。これはビットコイン計算分野において有望で刺激的な展望だと考えています。

9. おわりに

まとめると、本稿を通じて以下のことがわかりました。

  • Covenantはビットコインスクリプトの強力なツールであり、ビットコイン上でスマートコントラクトを作成できる。Covenantはビットコインの機能を単なる価値移転を超えて拡張する。

  • しかし、Covenantがあっても、ビットコインスクリプトにはスタックサイズ制限や使用可能なオペコードタイプの制限など、多くの制限がある。これにより、Covenantのみで実現可能なスマートコントラクトの複雑さと表現力が制限される。

  • STARKはオフチェーン計算の実行を効果的に検証できるため、これらの制限を緩和する有望な解決策を提供する。STARKを利用することで、ビットコインスマートコントラクト内でより複雑な計算を実行し、オンチェーンの計算負荷を最小化できる。

  • Cairoは、STARKを用いた効率的な証明と検証を目的に設計されたプログラミング言語で、ビットコインスマートコントラクトに非常に適している。より複雑なスマートコントラクトの作成を可能にし、使いやすさ、機能性、安全性を向上させる。

  • OP_CATは要素を連結するためのビットコインスクリプトオペコードである。OP_CATはビットコイン上でCovenantとSTARKを実現する上で極めて重要であり、結果としてビットコインに強力な汎用計算能力をもたらす。

次回の記事では、ビットコイン上のCircle-STARK検証器についてさらに深く探ります。

本文に対するWeikeng Chen、Pingzhou Yuan、およびStarkWareチームの貴重な意見に感謝します。

Victor Kolobov