取引所DEX+

ゴールドバー＆BTC Giveaway2000g

この記事のセクションでは、ブロックチェーンマイニングを敵対的な「自然」と将来のトランザクションに関する不完全な知識を持つマイナーとの間のゲームとしてモデル化しています。最も高い手数料を提供するトランザクションを優先する貪欲割り当て関数（Greedy Allocation Function）を紹介し、割引率と敵対的なスケジューリングがマイナーのパフォーマンスにどのように影響するかを探ります。競争比率分析を使用して、単純な貪欲戦略でさえも最悪のケースシナリオに対してほぼ最適な結果をもたらすことができることを示しています — これはビットコインとイーサリアムブロックチェーンの実世界のマイナーが同様のヒューリスティックに頼る理由についての洞察を提供しています。この記事のセクションでは、ブロックチェーンマイニングを敵対的な「自然」と将来のトランザクションに関する不完全な知識を持つマイナーとの間のゲームとしてモデル化しています。最も高い手数料を提供するトランザクションを優先する貪欲割り当て関数（Greedy Allocation Function）を紹介し、割引率と敵対的なスケジューリングがマイナーのパフォーマンスにどのように影響するかを探ります。競争比率分析を使用して、単純な貪欲戦略でさえも最悪のケースシナリオに対してほぼ最適な結果をもたらすことができることを示しています — これはビットコインとイーサリアムブロックチェーンの実世界のマイナーが同様のヒューリスティックに頼る理由についての洞察を提供しています。

ブロックチェーンネットワークにおける貪欲アルゴリズムがマイナー報酬をどのように形成するか

2025/10/14 03:54

リンク一覧

概要と1. はじめに

1.1 私たちのアプローチ

1.2 私たちの結果とロードマップ

1.3 関連研究

モデルとウォームアップと2.1 ブロックチェーンモデル

2.2 マイナー

2.3 ゲームモデル

2.4 ウォームアップ：貪欲な割り当て関数
決定論的なケースと3.1 決定論的上限

3.2 即時性バイアスのある割り当て関数クラス
ランダム化されたケース
議論と参考文献

A. セクション2、3の欠落した証明
B. セクション4の欠落した証明
C. 用語集

2.3 ゲームモデル

我々は敵対者とマイナーの間のゲームを検討します。この視点は、マイナーが現在知られているトランザクションを次のブロックに割り当てる際に、将来のトランザクションに関する不完全な知識によってマイナーがどれだけの収益を失う可能性があるかを定量化することを目的としています。この点で、システム内のアクティブなユーザーは、最悪のケースのトランザクションスケジュールを作成する全知の「自然」的な敵対者と考えることができます。割り当て関数は、敵対者によって送信される将来のトランザクションについての知識を持たないため、以前のトランザクションによって明らかにされた部分的な情報に基づく最適な計画が最良の行動方針ではない可能性があります。しかし、やや驚くべきことに、後に我々はそれが実際にそうであることを示します。マイナーの割引率が与えられると、最大の手数料を持つトランザクションと最低のTTLを持つトランザクションを含めることの間に概念的な緊張があります。したがって、割り当て関数xの品質は、最悪のケースの敵対的なψに直面したときに、それを最良の可能な関数x'と比較することによって定量化されます。結果として得られる量はxの競争率と呼ばれます。パケットスケジューリングに関する文献との互換性を保つために、我々は競争率を、その逆ではなく、可能な限り最良のオフラインパフォーマンスを割り当て関数のオンラインパフォーマンスで割ったものとして定義します。したがって、Rx ≥ 1となります。上限は、良いパフォーマンスを保証する割り当て関数を見つけることによって達成され、下限は、どの割り当て関数もより良いパフォーマンスを保証できないことを示すことによって達成されます。

\ \

\ \ \

2.4 ウォームアップ：貪欲な割り当て関数

貪欲な割り当て関数は、定義2.6で定義されており、おそらくパケットスケジューリング問題の古典的なアルゴリズムであり、割引なしのケースについて以前の文献で探求されました。さらに、経験的証拠は、ほとんどのマイナーが貪欲にトランザクションをブロックに割り当てていることを示唆しています。以前の研究では、ビットコインとイーサリアムにおいて、より高い手数料を支払うトランザクションは一般的にmempoolの待機時間が短く、つまりブロックに比較的迅速に含まれることが示されています[MACG20; PORH22; TFWM21; LLNZZZ22]。実際、Bitcoin Core（ビットコインクライアントの参照実装）とgeth（イーサリアムの最も人気のある実行クライアント）のデフォルトのトランザクション選択アルゴリズムは、両方のデフォルトの動作はオーバーライドできるものの、手数料に基づいてトランザクションを優先します。したがって、このアプローチのパフォーマンスを確認することは興味深いことです。

\ 定義2.6（貪欲な割り当て関数）。あるトランザクションセットSが与えられた場合、貪欲な割り当て関数はTTLを無視して、セットSに存在する最も高い手数料を支払うトランザクションを選択します：

\ 同じ手数料を持つ複数のトランザクションがある場合、最も低いTTLを持つものが優先されます。

\ 例2.7では、貪欲なアルゴリズムのパフォーマンスが割引率にどのように依存するかを説明します。

\ 例2.7。 以下の敵対者ψが与えられた場合の貪欲なアルゴリズムのパフォーマンスを検討します。

\ ψによって定義されたトランザクションスケジュールは図1に描かれています。ターン1で、敵対者は2つのトランザクションをブロードキャストします：ターンの終わりに期限切れになり、手数料が2の(1, 2)と、手数料が4で次のターンの終わりに期限切れになる(2, 4)です。貪欲なアルゴリズムは高い手数料のトランザクションを優先するため、(2, 4)を割り当て、他のトランザクションは期限切れになります。次のターンでは、敵対者はTTLが2で手数料が6の単一のトランザクションをブロードキャストします。これはそのターンで貪欲なアルゴリズムが利用できる唯一のものであるため、割り当てられます。ステップ3では、敵対者はトランザクションを発行せず、ステップ4では、トランザクション(1, 8)がブロードキャストされ、貪欲なアルゴリズムによって割り当てられます。

\ レンマ2.8では、割引率の関数として貪欲なアルゴリズムの競争率の境界を設定します。

:::info 著者：

(1) Yotam Gafni、ワイツマン研究所 (yotam.gafni@gmail.com)；

(2) Aviv Yaish、エルサレムヘブライ大学 (aviv.yaish@mail.huji.ac.il)。

:::

:::info この論文はarxivで入手可能であり、CC BY 4.0 DEEDライセンスの下で提供されています。

:::

免責事項：このサイトに転載されている記事は、公開プラットフォームから引用されており、情報提供のみを目的としています。MEXCの見解を必ずしも反映するものではありません。すべての権利は原著者に帰属します。コンテンツが第三者の権利を侵害していると思われる場合は、削除を依頼するために service@support.mexc.com までご連絡ください。MEXCは、コンテンツの正確性、完全性、適時性について一切保証せず、提供された情報に基づいて行われたいかなる行動についても責任を負いません。本コンテンツは、財務、法律、その他の専門的なアドバイスを構成するものではなく、MEXCによる推奨または支持と見なされるべきではありません。