ビットコインのメルケル化された抽象構文ツリーとは何ですか?
原題：『乾物 | ビットコインメルケル化抽象構文ツリーとは何ですか？ "、デイビッド・A・ハーディング著
Merklized Abstract Syntax Trees (MAST) は、トランザクション サイズの縮小、プライバシーの向上、および大規模なスマート コントラクトを可能にする、ビットコインのアップグレード案です。この記事では、MAST の理論的根拠を説明し、その潜在的な利点を説明し、このテクノロジーを組み込んだ現在の提案をいくつか要約します。
問題: 未使用のスクリプト データ
サトシ・ナカモトは、ビットコインのホワイトペーパーには書かなかった興味深い機能をビットコインに与えました。ユーザーは、公開鍵を通じてビットコインを受け取り、秘密鍵のデジタル署名とともにビットコインを支払うことに加えて、動的な公開鍵および署名として使用できるプログラム (「スクリプト」と呼ばれる) を作成することもできます。
スクリプトを指定すると、これはすべてのビットコイン ウォレットの基本操作ですが、ビットコイン ネットワークによって強制されるビットコイン プロトコルは、スクリプトが True を返さない限り、スクリプトによって制御されるビットコインを使用することを許可しません。これにより、秘密キーによる署名が必要なトランザクションを要求するなど、「負担」 (プロパティ条件) と呼ばれる、資金を使用できる条件を指定できます。
次の例のように、より複雑なプロパティ条件も可能です。この記事ではこれを使用します。アリスはいつでもビットコインを使えるようにしたいのですが、3 か月連続でビットコインを使わなかった場合 (おそらく死亡)または無能力）、彼女は兄弟のボブとチャーリーがビットコインを所有し、同意できる場所であればどこでも使用できるようにしたいと考えています。
次の条件付きスクリプトは、上記の目的を達成します。これには、アリスの公開キー (秘密キーからの署名を検証する必要がある) が含まれるだけでなく、次の条件付きロジック (タイムアウト条件、ボブとチャーリーの公開キー) も追加されます。
現在のビットコインプロトコルでは、上記のすべてのデータをブロックチェーンに追加する必要があり、アリスのビットコインが使用される際には、特定の使用行動にまったく無関係なスクリプトの部分も含まれており、これも公開する必要があります。たとえば、アリスがビットコインを使用すると、ボブとチャーリーの公開鍵も公開されます。
未使用の条件付きデータはトランザクションのサイズを増大させ、ユーザーのプライバシーを必要以上にさらすことになると同時に、検証コストではなくサイズがスマートコントラクトのサイズの主な制限要因になります。 MAST は、スクリプトの未使用部分をブロックチェーンに直接含める必要性をなくすことで、これらの状況を改善することを目指しています。
MASTの最初のアイデア
MAST 1 の背後にあるアイデアは、抽象セマンティック ツリーとマークル ツリーという 2 つの長年の概念から来ています。抽象セマンティック ツリー (AST) は、プログラムを独立した小さな部分に分割して記述する方法であり、これによりプログラムの分析と最適化が容易になります。 AST を生成するには、すべての前提が見つかるまで、すべての方程式をその前提と矢印で接続する必要があります。以下の図は、上記のサンプル スクリプトの AST です。
一方、マークル ツリーは、セットの全体像を知らなくても、要素がセットに属しているかどうかを検証するために使用できます。たとえば、ビットコインの簡易決済検証ウォレット (SPV ウォレット) はマークル ツリーを使用して、特定のトランザクションが特定のブロックに存在するかどうかを検証するため、ブロック全体をダウンロードする必要がなく、帯域幅を節約できます。
マークル ツリーを生成するには、まず各要素を 1 回ハッシュして、独自の一意の識別子を生成します。次に、これらの識別子をペアにして再度ハッシュし、識別子のペアの識別子を生成します。というように、残りの識別子が 1 つだけになるまで繰り返します。 「メルケル ルート」。コレクション全体をマークする短い識別子です。
要素がセットに属していることを確認する場合、セット全体の所有者は、その要素からマークル ルートまでのパス上のすべての識別子を提供することができます。これは、要素が実際にセット内に存在することを証明します。
つまり、AST の背後にあるテクノロジーを使用すると、プログラムを小さな部分に分割することができ、マークル ツリーを使用すると、プログラム全体を公開することなく、これらの小さな部分が実際に完全なプログラムの一部であることを検証できます。これは MAST の基本原則であり、消費者は 1 回の取引で使用されない条件をマークル証明に置き換えることができ、取引サイズの削減、プライバシーの向上、大規模な契約のサポートが可能になります。
MASTの例
上記のプロパティ条件を例として、考えられる 2 つのシナリオに対応する 2 つの添字に分割してみましょう。
アリスはいつでもビットコインを使うことができます (左側の下付き文字)
または、アリスの署名が連続 3 か月の支払いに使用される場合、ビットコインの支払いにはボブとチャーリーの署名が必要になります (下図の右側の下付き文字)。
これら 2 つの個別の添字に基づいてマークル ツリーを作成します。
このマークル ツリーのルートは、最終的にアリスの完全なプロパティ条件を特定しますが、そのサイズはわずか 32 バイトです。その後、アリスは、サブスクリプトの 1 つがマークル ルートに接続されている証明が提供され、サブルーチンが True を返した場合にのみ支出トランザクションが有効であることを示す、代替の条件付きスクリプトを使用できます。
添え字のマークル証明は、使用される添え字に応じて、次の図のように視覚的に描画されます。
メリット #1 - トランザクションの量が少なくなる
まず、複雑なプロパティ条件を持つユーザーが MAST を使用して小規模なトランザクションを作成できるようにする方法を見てみましょう。これが MAST によってもたらされる最初の利点です。
上の例では、2 つの下付き文字を持つプロパティ バーを使用しました。アリスが自分のお金を使うか、ボブとチャーリーが 3 か月待った後に一緒にお金を使うかのいずれかです。 3 番目の添え字で 3 か月と 1 日後にダンとイーディスが資金を使用できるように指定し、4 番目の添え字で 3 か月と 2 日後にフレッドとジョージが資金を使用できるようにするなど、無限に拡張されたバージョンを想像してみましょう。 。
この思考実験により、MAST の有無に応じた添字の数とブロックに追加する必要がある条件付きデータの量との関係を示す以下のグラフが得られます。
以下は対数プロットです。これは同じことを意味します。
MAST トランザクションのサイズは、最初に MAST がない同じ条件のトランザクション (2 つのサブスクリプトの条件など) よりも大きくなりますが、非 MAST トランザクションのサイズは (サブスクリプトの数に応じて) 直線的に増加します。一方、MAST トランザクションの量は対数的にのみ増加します。
データ量の節約が主な目的の場合は、さらに最適化できます。多くの不動産条件について、消費者はそのうちの 1 つをより頻繁に使用する可能性があります。たとえば、アリスは長生きしたいと考えているため、彼女が作成するマークル ツリーでは、支出条件が最上位に近くなり、他のすべての条件がツリーの最下位に配置されます。
アリスが資金を使用するとき、彼女の不動産条件に受益者が何人いるかに関係なく、取引データの量は常に最適な状況であることがわかります。また、アリスの受益者が資金を使用するとき、取引データの量も最適な状況になります。前述の標準的に構築されたマークル ツリーよりもわずか数バイト多いだけです。
アリスがどのような配置を選択しても、MAST は複数添字プロパティの条件付きトランザクションを小さくできるため、ユーザーが支払う手数料が減り、より高度なトランザクションをブロックにロードできることがわかります。
メリット #2 - プライバシーの向上
上の説明では、アリスのすべてのプロパティ スクリプトを公開しましたが、アリスが自分のビットコインを使用した場合、ブロックチェーン上では下図の左側のデータのみが表示されると想像できます。
この情報だけでは、アリス以外の誰かがここで資金を使用できるかどうか、また使用する際にどのような制約に直面する必要があるかを知る方法はありません。 MAST から、他の条件があるかもしれないと推測できますが、それは単なる推測です。アリスは、自分のマークル ツリーに他の消費可能な部分があるふりをしているだけかもしれません。
同様に、別のブランチ (つまり、上の図の右側のサブスクリプト) が表示された場合、タイムアウト前に資金を使用できるかどうかはわかりません。また、タイムアウト前に資金を使用できるかどうかもわかりません。秘密キーのみを使用できます。他にも支出条件があると推測できますが、これをブロックチェーン上で確認することはできません。
これは、未使用の不動産状態が公開されないようにするのに非常に役立ちます。たとえば、一部の販売者は、スマート コントラクトを可能な限り機密にし、潜在的な競合他社に見られたくない場合があります。これは、スマート コントラクト用に設計されていると主張しながら、実際にはこれらのコントラクトのプライバシーを提供しない一部のアルトコインとは対照的です。
また、一部のユーザーが財産に関するプライバシーをまったく気にしない場合でも、プライバシーはすべてのビットコイン ユーザーにさらなる利益をもたらす可能性があります。この記事の冒頭から、非 MAST 条件付きテンプレートを使用しているのはアリスだけであると仮定します。すべての条件が公開されるため、誰でもアリスの支出行動を追跡でき、ブロックチェーン上のこのテンプレートの使用状況を観察するだけで、アリスのプライバシーは失われます。
特定のユーザーを識別しやすくするデザインは、人々が自分のビットコインを他の人のビットコインとは異なるように扱うことも容易にします。これは「均質性の欠如」と呼ばれます。誰かがアリスの財産状況がどのようなものであるかを知っていれば、アリスが自分のビットコインを使用できないように、マイナーに賄賂を贈ったり、これらの人々の取引をパッケージ化しないよう強制したりすることができます。
アリス (またはボブとチャーリー) は依然としていくつかの障害を明らかにする必要があるため、MAST はこの問題を完全には解決できませんが、多くの複雑なプロパティ条件は少数の単純な MAST タイプの条件に解決できます。
たとえば、Alice のデフォルトの支出動作は、単一の署名を提供するだけで済む他の通常の支払い動作と同じように見えるため、Alice の MAST ベースのトランザクションは、他の MAST ベースの単一署名トランザクションと何ら変わりません。これにより、アリスのプライバシー、資金の均一性、および MAST ベースの単一署名条件を使用するすべてのユーザーの金銭的均一性が向上します。
MAST のこの利点は、ビットコインのプライバシーと均一性を向上させるための他の提案とも組み合わされる可能性があります。 Pieter Wuille と Gregory Maxwell の「Universal Threshold Tree」、Andrew Poelstra の「Scriptless Script」、Thaddeus Dryja の「Discrete Logarithm Contract」など、特定の複雑なプロパティ条件を 1 つの署名で利用可能にする提案があり、MAST はこれらと組み合わせることができます。計画。
しかし、たとえこれらのソリューションがどれもビットコインに実装できなかったとしても、MAST 自体は、現在のものと比較したり、ユーザー定義のスマート コントラクト アルトコインと比較したりして、複雑なプロパティ条件を持つユーザーに、より多くのプライバシーと互換性を提供できます。
メリット #3 - 大規模なスマート コントラクト
ビットコインは現在、個々のスクリプトに 3 つの異なるサイズ制限を設定しています: ネイキッド スクリプトのサイズは 10,000 バイト (2010 年 7 月に導入)、P2SH スクリプトのサイズは 520 バイト、segwit スクリプトのサイズは 10,000 バイトを超えることはできません。これらのサイズを上の図に示します。
無限拡張という極端なケースでも、MAST は現在のすべてのメカニズムよりも多くの条件付き分岐をサポートしていることがわかります。実際、MAST は非常に拡張性に優れているため、たとえ観測可能な宇宙のすべてのエネルギーがあったとしても、それを標準 (バランスのとれた) マークル ツリーの作成にのみ使用した場合、そのマークル証拠はわずか 8448 バイトです。このような大規模なマークル証明であっても、最新のラップトップであれば 1 ミリ秒未満で検証できます。
MAST は、未使用の添え字を処理するタスクから完全なノードを解放することで、ビットコイン スクリプトが他のいくつかの厳しい制限を回避するのにも役立ちます。この点で、MAST は、ビットコイン スマート コントラクトの長期的な設計目標をうまく維持し、拡張しました。つまり、ノードが帯域幅の料金を支払う一方で、契約の負担は可能な限り契約の参加者が負担する必要があります。メモリと処理能力は異なりますが、補償することはできないため、責任はできるだけ少なくする必要があります。
したがって、MAST の本当の成果は、ビットコイン ユーザーが (これまで以上に) 高度なコントラクトを作成できるようにすることではなく、ビットコイン ノードに新たな負担を加えることなくこの可能性を開くことです。
MAST の実装: 既存の複数の提案
これまでのところ、ビットコイン プロトコルで MAST を有効にする 2 つの方法が bitcoin-dev メーリング リストで提案されていますが、どちらもまだドラフト段階にあり、変更される可能性があります。
最初の提案は、Johnson Lau (仮名「jl2012」) によって提案された BIP114 です。これは、分離された証人に基づく拡張機能を使用するため、元の分離された証人アドレス (bech32) が MAST プロパティ条件に対するマークル ルート コミットメントになることができます。したがって、支出トランザクションはツリーから子スクリプトを選択できます。
2 番目の提案である、Mark Friedenbach (別名「maaku」) による 2 つの名前のない BIP (1、2) は、スクリプト言語の柔軟性を高め、プログラマーが MAST ベースのプロパティ条件を検証するスクリプトを作成できるようにします。フリーデンバッハ氏が好む方法で実装すると、ビットコインが現在サポートしている 3 つのスクリプト タイプ (裸のスクリプト、P2SH、および分離された証人スクリプト) のすべてでマークル証明を利用できるようになります。
これらのいくつかの提案にはそれぞれ長所と短所がありますが、いずれも上記の MAST の利点を提供します (バイト数は増加または減少する可能性があります)。それぞれソフトフォークでアクティブ化できます。
結論: MAST はいつ使用できますか?
上記では、MAST の利点を説明し、ビットコインに MAST を実装するための 2 つの提案について簡単に説明しましたが、いつ MAST を使用できるようになるかについても知りたいかもしれません。残念ながら私も知りません。
アイデアから提案、実装の完了、ソフトフォークの提案、ソフトフォークのアクティブ化に至るまでの道のりは長く、困難です。このことは、隔離された証人のアップグレードをめぐる2年間のドラマによって十分に明らかになりました。
しかし、私の観点から見ると、MAST の背後にある基本的な考え方はビットコイン技術コミュニティで幅広い支持を得ており、MAST に最も関心のある開発者は、この技術が完全に信頼できないことを誰かが証明できない限り、MAST の開発を続けるでしょう。これらの開発者がピアレビュー可能なソフト フォーク コードの提案に成功した場合、MAST をビットコイン プロトコルの一部にできるかどうかは、読者と他のビットコイン ユーザーの判断に委ねられます。
ありがとう
BIP114: Merklized Abstract Syntax Tree by Johnson Lau
Tail Call Sematics by Mark Friedenbach
MerkleBranchVerify opcode by Mark Friedenbach
Discussion at core.tech meetup by Mark Friedenbach (transcribed by Bryan Bishop)
Merklized Abstract Syntax Trees by Jeremy Rubin, Manali Naik, Nitya Subramanian
An explanation and justification of the tail-call and MBV approach to MAST by Mark Friedenbach
Making MAST Meaningful by Brian Deery
The next step to improve Bitcoin by Aaron van Wirdum
ありがとう
脚注
脚注
ラッセル・オコナーは MAST のプロトタイプを最初に説明したと信じられており、いくつかの情報源はピーター・ウィルを付け加えています。出典: Peter Todd、Gregory Maxwell (Jeremy Rubin et al. で引用)、Mark Friedenbach (個人的な通信)。
ありがとう、ジョン・ニューベリー。
元のリンク:
（以上）
(この記事には多くのハイパーリンクがあります。左下の「原文を読む」をクリックすると、EthFans Web サイトから入手できます)
元のリンク:
https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f
翻訳: ア・ジアン
翻訳: ア・ジアン
