数十年にわたり、分散システムの研究、特にビザンチン合意と状態機械レプリケーション（SMR）においては、一貫性と生存性の2つの主要な目標に焦点が当てられてきました。一貫性はすべてのノードが同じ取引のシーケンスに合意することを意味し、生存性はシステムが新しい取引を継続的に追加し続けることを保証します。しかし、これらの特性は、悪意のある行為者が受信後に取引の順序を変更することを防ぐものではありません。
パブリックブロックチェーンにおいては、従来のコンセンサス保証のギャップが深刻な問題となっています。バリデーターやブロックビルダー、シーケンサーは、ブロックの順序付けにおいて特権的な役割を悪用し、最大抽出可能価値（MEV）と呼ばれる行為を行うことがあります。この操作には、利益を得るためのフロントランニング、バックランニング、サンドイッチ取引などが含まれます。取引の実行順序はDeFiアプリケーションの有効性や収益性を左右するため、取引順序の整合性は公平性と信頼性を維持する上で極めて重要です。
この重要なセキュリティギャップに対処するために、取引順序の公平性が第三の重要なコンセンサス特性として提案されました。公平な順序付けプロトコルは、最終的な取引の順序が外部の客観的要因（例：到着時間や受信順）に依存し、敵対的な再順序付けに耐性を持つことを保証します。ブロック提案者の取引再順序付けの権限を制限することで、これらのプロトコルはブロックチェーンをより透明で予測可能、かつMEV耐性のあるものに近づけます。
最も直感的で強力な公平性の概念は、受信順序の公平性（Receive-Order-Fairness、ROF）です。これは、「最初に受信した取引が最初に出力される」という非公式な定義であり、十分な数の取引があるノードの過半数において、ある取引が別の取引よりも早く到達した場合、その順序に従って実行されるべきだと規定しています。
しかし、この「順序の公平性」を全てのノード間で実現することは、すべてのノードが瞬時に通信できると仮定しない限り、根本的に不可能です。この不可能性は、社会選択理論のコンドルセの逆説との驚くべき関連から導かれます。
コンドルセの逆説は、各ノードが内部的に取引の推移的な順序を維持していても、システム全体の優先順位が非推移的なサイクルを形成する可能性を示しています。例えば、多数のノードが取引AをBより先に受信し、別の多数がBをCより先に受信し、さらに別の多数がCをAより先に受信する場合です。このような場合、A→B→C→Aというループが形成され、すべての多数の優先順位を同時に満たす単一の一貫した順序は存在し得ません。
この逆説は、非同期ネットワークや、外部ネットワーク遅延が長すぎる同期ネットワークにおいて、完全な受信順序の公平性を実現することが不可能であることを示しています。そのため、より弱い公平性の定義、例えばバッチ順序の公平性（batch order fairness）が採用されることになります。
HederaはHashgraphコンセンサスアルゴリズムを採用し、強い受信順序の公平性（ROF）を近似しようとしています。具体的には、各取引に対して、全ノードのローカルタイムスタンプの中央値を最終的なタイムスタンプとして割り当てる方法です。
しかし、これは根本的に操作に対して脆弱です。敵対的なノードは意図的に自らのローカルタイムスタンプを歪め、2つの取引の最終的な順序を逆転させることが可能です。
例えば、5つのコンセンサスノード（A, B, C, D, E）があり、Eノードが悪意を持っているとします。2つの取引tx₁とtx₂がネットワークにブロードキャストされ、全ての善良なノードはtx₁をtx₂より先に受信します。期待される最終順序はtx₁→tx₂です。
しかし、Eノードはtx₁に遅いタイムスタンプ（例：3）を付与し、tx₂には早いタイムスタンプ（例：2）を付与します。これにより、中央値の計算結果は次のようになります。
結果として、最終的なタイムスタンプがtx₁は3、tx₂は2となり、プロトコルはtx₂→tx₁を出力し、実際の順序と逆転します。
この例は、中央値関数が一見中立的に見えながらも、実際には不公平を引き起こす原因となり得ることを示しています。Hashgraphの「公平なタイムスタンプ付け」は、暗黙の信頼に依存しており、単一の不正行為者によって簡単に操作され得るため、真の公平性を保証しません。
コンドルセの逆説による理論的な不可能性を回避するために、実用的な公平順序付けスキームは何らかの形で公平性の定義を緩和する必要があります。
Aequitasプロトコルは、ブロック順序の公平性（Block-Order-Fairness、BOF）またはバッチ順序の公平性を導入しました。BOFは、十分な数のノードがある取引txを別の取引tx′よりも先に受信した場合、txはtx′よりも前または同時にブロック内に配信されるべきだと規定します。つまり、「配信されるべき」から「遅くとも配信される」へとルールを緩和しています。
具体例として、3つのコンセンサスノード（A, B, C）と3つの取引（tx₁, tx₂, tx₃）を考えます。取引が「早く受信された」とは、少なくとも2つのノードがそれを最初に観測した場合です。
多数決を用いてグローバルな順序を決定すると、
この優先順位はループを形成し、すべてのノードの意見を同時に満たす単一の順序は存在しません。これにより、厳密なROFの実現は不可能です。
BOFは、これらの競合する取引を同じバッチまたはブロックにまとめることで解決します。具体的には、
ブロックB₁ = {tx₁, tx₂, tx₃}
とし、これらの取引は同時に発生したとみなされます。ブロック内では、ハッシュ値などの決定的な方法で順序を決定し、最終的な取引の整合性と公平性を保ちます。
この方法により、取引の順序が競合する場合でも、同じブロック内にまとめることで公平性を確保しつつ、全てのノードが一つの線形順序に合意できるようにしています。競合がなければ、より強いROFも実現可能です。
AequitasはBOFを実現しましたが、通信コストが高く、弱い生存性しか保証できないという制約もあります。弱い生存性は、取引の配信が、コンドルセサイクル全体が完了した後に保証されることを意味し、サイクルが連鎖する場合は長時間遅延する可能性があります。
これに対し、Themisプロトコルは、同じ強いBOF特性をより効率的に実現するために設計されました。Themisは、バッチの非解消（Batch Unspooling）、遅延順序付け（Deferred Ordering）、およびより強力なバッチ内保証（Stronger Intra-Batch Guarantees）という技術を用いています。
標準版のThemisは、参加者がネットワーク内のほとんどのノードとメッセージを交換する必要があり、通信コストはネットワーク参加者の二乗に比例します。しかし、最適化されたSNARK-Themisでは、暗号証明を用いて公平性を検証し、直接通信を最小限に抑えることで、通信負荷を線形に抑え、大規模ネットワークでも効率的にスケールします。
例えば、5つのノード（A–E）がtx₁, tx₂, tx₃を受信した場合、ネットワーク遅延によりローカル順序が異なることがあります。
Themisは、これらのサイクルを検出し、すべての取引を一つの強連結成分（SCC）にまとめ、バッチとして処理します。これにより、内部順序の確定を待つ間も、新しい取引の処理を継続できるため、システムのライブ性を維持し、停滞を防ぎます。
取引順序の完全な公平性は一見単純に思えます。最初にネットワークに到達した取引が最初に処理されるべきです。しかし、コンドルセの逆説が示すように、これは実際の分散システムでは実現不可能です。異なるノードは異なる順序で取引を認識し、その見解が対立した場合、妥協なしに一つの「正しい」シーケンスを構築することはできません。
HederaのHashgraphは中央値タイムスタンプを用いてこの理想に近づこうとしましたが、その方法は証明よりも信頼に依存しています。不正な参加者が中央値を歪めることで、取引の順序を逆転させることが可能であり、「公平なタイムスタンプ付け」は真の公平性を保証しません。
AequitasやThemisのようなプロトコルは、実現可能な範囲で公平性を再定義し、現実のネットワーク条件下でも順序の整合性を保つ方法を示しています。これらは、名声やバリデーターの信頼、許可制のコントロールに頼るのではなく、暗号学的証明に基づく保証を重視しています。
この内容は投資アドバイスや推奨を意図したものではありません。すべての投資や取引にはリスクが伴います。読者は自身の調査を行い、自己責任で判断してください。
本記事は一般的な情報提供を目的としており、法的または投資のアドバイスとして解釈されるべきではありません。ここに記載された意見や見解は著者個人のものであり、Cointelegraphの見解や意見を反映するものではありません。
Cointelegraphは本記事の内容や記載された製品を推奨しません。読者は、記載された製品や企業に関して自己調査を行い、自己責任で判断してください。
26.15K 人気度
64.71K 人気度
261.67K 人気度
15.28K 人気度
7.91K 人気度
取引順序における完全な公平性の不可能性
数十年にわたり、分散システムの研究、特にビザンチン合意と状態機械レプリケーション（SMR）においては、一貫性と生存性の2つの主要な目標に焦点が当てられてきました。一貫性はすべてのノードが同じ取引のシーケンスに合意することを意味し、生存性はシステムが新しい取引を継続的に追加し続けることを保証します。しかし、これらの特性は、悪意のある行為者が受信後に取引の順序を変更することを防ぐものではありません。
パブリックブロックチェーンにおいては、従来のコンセンサス保証のギャップが深刻な問題となっています。バリデーターやブロックビルダー、シーケンサーは、ブロックの順序付けにおいて特権的な役割を悪用し、最大抽出可能価値（MEV）と呼ばれる行為を行うことがあります。この操作には、利益を得るためのフロントランニング、バックランニング、サンドイッチ取引などが含まれます。取引の実行順序はDeFiアプリケーションの有効性や収益性を左右するため、取引順序の整合性は公平性と信頼性を維持する上で極めて重要です。
この重要なセキュリティギャップに対処するために、取引順序の公平性が第三の重要なコンセンサス特性として提案されました。公平な順序付けプロトコルは、最終的な取引の順序が外部の客観的要因（例：到着時間や受信順）に依存し、敵対的な再順序付けに耐性を持つことを保証します。ブロック提案者の取引再順序付けの権限を制限することで、これらのプロトコルはブロックチェーンをより透明で予測可能、かつMEV耐性のあるものに近づけます。
コンドルセの逆説と理想的な公平性の不可能性
最も直感的で強力な公平性の概念は、受信順序の公平性（Receive-Order-Fairness、ROF）です。これは、「最初に受信した取引が最初に出力される」という非公式な定義であり、十分な数の取引があるノードの過半数において、ある取引が別の取引よりも早く到達した場合、その順序に従って実行されるべきだと規定しています。
しかし、この「順序の公平性」を全てのノード間で実現することは、すべてのノードが瞬時に通信できると仮定しない限り、根本的に不可能です。この不可能性は、社会選択理論のコンドルセの逆説との驚くべき関連から導かれます。
コンドルセの逆説は、各ノードが内部的に取引の推移的な順序を維持していても、システム全体の優先順位が非推移的なサイクルを形成する可能性を示しています。例えば、多数のノードが取引AをBより先に受信し、別の多数がBをCより先に受信し、さらに別の多数がCをAより先に受信する場合です。このような場合、A→B→C→Aというループが形成され、すべての多数の優先順位を同時に満たす単一の一貫した順序は存在し得ません。
この逆説は、非同期ネットワークや、外部ネットワーク遅延が長すぎる同期ネットワークにおいて、完全な受信順序の公平性を実現することが不可能であることを示しています。そのため、より弱い公平性の定義、例えばバッチ順序の公平性（batch order fairness）が採用されることになります。
Hedera Hashgraphと中央値タイムスタンプの欠陥
HederaはHashgraphコンセンサスアルゴリズムを採用し、強い受信順序の公平性（ROF）を近似しようとしています。具体的には、各取引に対して、全ノードのローカルタイムスタンプの中央値を最終的なタイムスタンプとして割り当てる方法です。
しかし、これは根本的に操作に対して脆弱です。敵対的なノードは意図的に自らのローカルタイムスタンプを歪め、2つの取引の最終的な順序を逆転させることが可能です。
例えば、5つのコンセンサスノード（A, B, C, D, E）があり、Eノードが悪意を持っているとします。2つの取引tx₁とtx₂がネットワークにブロードキャストされ、全ての善良なノードはtx₁をtx₂より先に受信します。期待される最終順序はtx₁→tx₂です。
しかし、Eノードはtx₁に遅いタイムスタンプ（例：3）を付与し、tx₂には早いタイムスタンプ（例：2）を付与します。これにより、中央値の計算結果は次のようになります。
結果として、最終的なタイムスタンプがtx₁は3、tx₂は2となり、プロトコルはtx₂→tx₁を出力し、実際の順序と逆転します。
この例は、中央値関数が一見中立的に見えながらも、実際には不公平を引き起こす原因となり得ることを示しています。Hashgraphの「公平なタイムスタンプ付け」は、暗黙の信頼に依存しており、単一の不正行為者によって簡単に操作され得るため、真の公平性を保証しません。
実用的な保証を実現するために
コンドルセの逆説による理論的な不可能性を回避するために、実用的な公平順序付けスキームは何らかの形で公平性の定義を緩和する必要があります。
Aequitasプロトコルは、ブロック順序の公平性（Block-Order-Fairness、BOF）またはバッチ順序の公平性を導入しました。BOFは、十分な数のノードがある取引txを別の取引tx′よりも先に受信した場合、txはtx′よりも前または同時にブロック内に配信されるべきだと規定します。つまり、「配信されるべき」から「遅くとも配信される」へとルールを緩和しています。
具体例として、3つのコンセンサスノード（A, B, C）と3つの取引（tx₁, tx₂, tx₃）を考えます。取引が「早く受信された」とは、少なくとも2つのノードがそれを最初に観測した場合です。
多数決を用いてグローバルな順序を決定すると、
この優先順位はループを形成し、すべてのノードの意見を同時に満たす単一の順序は存在しません。これにより、厳密なROFの実現は不可能です。
BOFは、これらの競合する取引を同じバッチまたはブロックにまとめることで解決します。具体的には、
ブロックB₁ = {tx₁, tx₂, tx₃}
とし、これらの取引は同時に発生したとみなされます。ブロック内では、ハッシュ値などの決定的な方法で順序を決定し、最終的な取引の整合性と公平性を保ちます。
この方法により、取引の順序が競合する場合でも、同じブロック内にまとめることで公平性を確保しつつ、全てのノードが一つの線形順序に合意できるようにしています。競合がなければ、より強いROFも実現可能です。
AequitasはBOFを実現しましたが、通信コストが高く、弱い生存性しか保証できないという制約もあります。弱い生存性は、取引の配信が、コンドルセサイクル全体が完了した後に保証されることを意味し、サイクルが連鎖する場合は長時間遅延する可能性があります。
これに対し、Themisプロトコルは、同じ強いBOF特性をより効率的に実現するために設計されました。Themisは、バッチの非解消（Batch Unspooling）、遅延順序付け（Deferred Ordering）、およびより強力なバッチ内保証（Stronger Intra-Batch Guarantees）という技術を用いています。
標準版のThemisは、参加者がネットワーク内のほとんどのノードとメッセージを交換する必要があり、通信コストはネットワーク参加者の二乗に比例します。しかし、最適化されたSNARK-Themisでは、暗号証明を用いて公平性を検証し、直接通信を最小限に抑えることで、通信負荷を線形に抑え、大規模ネットワークでも効率的にスケールします。
例えば、5つのノード（A–E）がtx₁, tx₂, tx₃を受信した場合、ネットワーク遅延によりローカル順序が異なることがあります。
Themisは、これらのサイクルを検出し、すべての取引を一つの強連結成分（SCC）にまとめ、バッチとして処理します。これにより、内部順序の確定を待つ間も、新しい取引の処理を継続できるため、システムのライブ性を維持し、停滞を防ぎます。
概要
取引順序の完全な公平性は一見単純に思えます。最初にネットワークに到達した取引が最初に処理されるべきです。しかし、コンドルセの逆説が示すように、これは実際の分散システムでは実現不可能です。異なるノードは異なる順序で取引を認識し、その見解が対立した場合、妥協なしに一つの「正しい」シーケンスを構築することはできません。
HederaのHashgraphは中央値タイムスタンプを用いてこの理想に近づこうとしましたが、その方法は証明よりも信頼に依存しています。不正な参加者が中央値を歪めることで、取引の順序を逆転させることが可能であり、「公平なタイムスタンプ付け」は真の公平性を保証しません。
AequitasやThemisのようなプロトコルは、実現可能な範囲で公平性を再定義し、現実のネットワーク条件下でも順序の整合性を保つ方法を示しています。これらは、名声やバリデーターの信頼、許可制のコントロールに頼るのではなく、暗号学的証明に基づく保証を重視しています。
この内容は投資アドバイスや推奨を意図したものではありません。すべての投資や取引にはリスクが伴います。読者は自身の調査を行い、自己責任で判断してください。
本記事は一般的な情報提供を目的としており、法的または投資のアドバイスとして解釈されるべきではありません。ここに記載された意見や見解は著者個人のものであり、Cointelegraphの見解や意見を反映するものではありません。
Cointelegraphは本記事の内容や記載された製品を推奨しません。読者は、記載された製品や企業に関して自己調査を行い、自己責任で判断してください。