💻 computer science

FairDAG: Consensus Fairness over Multi-Proposer Causal Design

Dieses Paper stellt FairDAG vor, ein neuartiges Framework, das Fairness-Protokolle mit einem DAG-basierten Konsens integriert, um die Durchsatz- und Manipulationsbeschränkungen bestehender Leader-basierter Systeme zu überwinden und dadurch eine überlegene Fairness bei der Transaktionsreihenfolge sowie eine höhere Performance in Blockchain-Netzwerken zu erreichen.

Ursprüngliche Autoren: Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

Veröffentlicht 2026-01-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Dakai Kang, Junchao Chen, Tien Tuan Anh Dinh, Mohammad Sadoghi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich einen geschäftigen digitalen Marktplatz vor, auf dem tausende Menschen gleichzeitig versuchen, Artikel zu kaufen und zu verkaufen. In diesem Marktplatz ist die Reihenfolge, in der Transaktionen stattfinden, von enormer Bedeutung. Wenn Sie einen seltenen Gegenstand vor jemand anderem kaufen, erhalten Sie ihn; wenn Sie ihn nach jemand anderem kaufen, könnten Sie leer ausgehen oder mehr bezahlen müssen.

In der Welt der Blockchain (der Technologie hinter Kryptowährungen) gibt es ein Problem: Die Person, die für die Entscheidung über die Reihenfolge dieser Transaktionen zuständig ist (der „Block Proposer“), kann ein Betrüger sein. Sie kann sich die Liste ansehen, eine profitable Bewegung entdecken und die Schlange so umstellen, dass sie selbst Geld verdient, indem sie ehrliche Menschen nach hinten drängt. Das ist wie ein Kassierer in einem Geschäft, der sieht, dass ein VIP-Kunde kommt, und ihn die Schlange abkürzen lässt, oder schlimmer noch, die Schlange so umstellt, dass er zuerst den letzten Artikel an seinen Freund verkaufen kann.

Bestehende Lösungen versuchten, dies zu lösen, indem sie einen einzelnen „Chef-Kassierer“ (einen Leader) einsetzten, der alle Präferenzen sammelte und die Reihenfolge bestimmte. Dies schuf jedoch zwei neue Probleme:

Der Flaschenhals: Wenn der Chef-Kassierer langsam ist oder überfordert wird, verlangsamt sich der gesamte Laden.
Der Betrug: Wenn dieser Chef-Kassierer ein Betrüger ist, kann er die Schlange immer noch manipulieren, da er der Einzige ist, der die Liste hält.

Hier kommt FairDAG: Die „Gruppen-Schlange“-Lösung

Das Paper stellt FairDAG vor, eine neue Art, diesen Marktplatz zu organisieren. Anstatt sich auf einen einzelnen Chef-Kassierer zu verlassen, nutzt FairDAG ein Multi-Proposer-System. Stellen Sie sich das wie ein riesiges, miteinander vernetztes Geflecht von Kassierern (Replikas) vor, die gleichzeitig ihre eigenen Listen laut herausrufen.

So funktioniert es, unter Verwendung einfacher Analogien:

1. Das Netz des Vertrauens (DAG)

Anstatt einer einzelnen Schlange stellen Sie sich ein Spinnennetz vor (einen gerichteten azyklischen Graphen, oder Directed Acyclic Graph, DAG). Jedes Mal, wenn ein Kassierer eine Liste von Transaktionen schreibt, schickt er diese nicht einfach an eine einzige Person; er hängt seine Liste an die Listen mehrerer anderer Kassierer an, von denen er vor kurzem gehört hat.

Warum das hilft: Wenn ein Kassierer versucht, eine Transaktion zu verstecken oder zu betrügen, stellt das Netz sicher, dass die Listen aller anderen schließlich zusammenlaufen und bestätigen, was wirklich passiert ist. Man kann einen Faden aus dem Netz nicht einfach löschen, ohne dass die gesamte Struktur es bemerkt.

2. Zwei Wege, um fair zu sein

Das Paper schlägt zwei spezifische „Regeln“ vor, wie die Schlange sortiert werden soll, je nachdem, wie streng man sein möchte:

FairDAG-AB (Die absolute Regel): Dies ist wie eine strikte „Wer zuerst kommt, mahlt zuerst“-Regel. Wenn alle vereinbaren, dass Person A vor Person B ankam, dann muss Person A zuerst kommen. Das System berechnet eine spezifische „Ticketnummer“ für jede Transaktion basierend darauf, wann ehrliche Kassierer sie gesehen haben. Selbst wenn ein Betrüger versucht, das Kartenspiel zu mischen, stellt die Mathematik sicher, dass die ehrlichen Ticketnummern gewinnen.
FairDAG-RL (Die relative Regel): Dies ist etwas flexibler, wie eine „Gruppierungs“-Regel. Manchmal ist es unmöglich genau zu wissen, wer zuerst ankam (wie wenn zwei Personen gleichzeitig durch eine Tür gehen). Anstatt um die exakte Sekunde zu kämpfen, gruppiert diese Regel sie zusammen. Wenn 90 % der ehrlichen Kassierer Person A vor Person B gesehen haben, dann geht A vor B. Wenn es ein Unentschieden ist, werden sie in derselben „Charge“ (Batch) zusammengefasst. Dies ist schneller und bewältigt chaotische Situationen besser.

3. Die Betrüger besiegen

Das Paper zeigt, dass FairDAG, da es ein Web aus vielen Kassierern anstelle eines einzelnen Leaders verwendet:

Betrüger können nichts verstecken: Ein Betrüger kann die Listen ehrlicher Menschen nicht einfach ignorieren, da die Netzwerkstruktur erzwingt, dass diese Listen schließlich enthalten werden.
Geschwindigkeit: Da alle ihre Listen gleichzeitig herausrufen, bleibt das System nicht stecken, während es auf eine langsame Person wartet. Es verarbeitet Transaktionen viel schneller als die alten „Single-Leader“-Systeme.

Die Ergebnisse

Die Autoren haben ihr System gegen ältere Methoden (wie Pompe und Themis) getestet. Sie fanden heraus:

Es ist schneller: FairDAG bewältigt mehr Transaktionen pro Sekunde (Durchsatz), weil es keinen einzelnen Flaschenhals gibt.
Es ist fairer: Selbst wenn Betrüger versuchen, die Reihenfolge zu manipulieren (indem sie Listen umkehren oder bestimmte Transaktionen verzögern), hält FairDAG die Reihenfolge viel besser ein als die alten Systeme.
Es ist robust: Selbst wenn das Internet langsam ist oder einige Kassierer langsam reagieren, bewegt sich das System weiter, ohne abzustürzen.

Zusammenfassend

FairDAG ist wie der Ersatz eines einzelnen, leicht bestechlichen Managers durch ein demokratisches, vernetztes Team von Arbeitern. Indem alle ihre Listen gleichzeitig herausrufen und diese Listen zu einem Netz verweben, wird es für einen böswilligen Akteur nahezu unmöglich, die Reihenfolge zu manipulieren, während das System gleichzeitig schnell bleibt. Es löst die „Reihenfolge-Manipulationskrise“, indem es das System zu groß und zu vernetzt macht, als dass ein einzelner Betrüger es kontrollieren könnte.

Technisches Resümee: FairDAG: Konsens-Fairness über Multi-Proposer-kausalen Designs

1. Problemstellung

Der Aufstieg von dezentralisierten Finanzen (DeFi) hat eine kritische Schwachstelle in der Transaktionsreihenfolge von Blockchains aufgezeigt: Maximal Extractable Value (MEV). Adversarielle Block-Proposer können die Reihenfolge von Transaktionen manipulieren, um Front-Running, Sandwich-Angriffe oder Liquidationsmanipulationen auszuführen und so Gewinne auf Kosten anderer Teilnehmer zu extrahieren.

Bestehende Fairness-Protokolle wie Pompe und Themis versuchen dies zu mildern, indem sie lokale Transaktionsreihenfolgen aus einem Quorum von Repliken aggregieren, um eine globale Ordnung abzuleiten. Diese Protokolle beruhen jedoch auf Leader-basiertem Konsens (z. B. PBFT, HotStuff). Diese Architektur führt zu zwei primären Einschränkungen:

Single-Point-of-Failure-Engpass: Ein einzelner Leader sammelt lokale Ordnungen. Wenn der Leader b Byzantinisch ist, kann er lokale Ordnungen selektiv sammeln, um die endgültige Sequenz zu manipulieren oder Transaktionen zu zensieren. Selbst wenn er ehrlich ist, stellt ein einzelner Leader einen Leistungsengpass dar, da die Nachrichtenkomplexität mit der Anzahl der Teilnehmer quadratisch wächst.
Anfälligkeit für Manipulation: Ein Byzantinischer Leader kann lokale Ordnungen von bestimmten korrekten Repliken ausschließen, wodurch die effektive Quorumgröße reduziert wird und es einfacher wird, Transaktionsabhängigkeiten zu manipulieren oder spezifische Transaktionen zu verzögern.

Das Paper postuliert, dass ein gut gestaltetes Fairness-Protokoll gegen die Manipulation der Ordnung resistent sein, die Anforderungen an korrekte Teilnehmer minimieren und eine hohe Performance (Durchsatz und niedrige Latenz) beibehalten muss.

2. Methodik: Das FairDAG-Framework

Die Autoren schlagen FairDAG vor, ein Framework, das die Konsensebene von der Fairnessebene entkoppelt und Fairness-Protokolle oberhalb von DAG-basierten Konsensprotokollen (z. B. Tusk, DAG-Rider, Bullshark) ausführt.

Kernarchitektur

FairDAG operiert in zwei distinkten Schichten:

DAG-Schicht (Konsens): Verwendet ein Multi-Proposer-Design, bei dem alle Repliken gleichzeitig Blöcke (Vertices) in Runden vorschlagen. Diese Vertices referenzieren vorherige Runden und bilden einen gerichteten azyklischen Graphen (DAG).
- Multi-Proposer-Design: Eliminiert den Single-Leader-Engpass, was parallele Blockvorschläge und einen höheren Durchsatz ermöglicht.
- Validitätseigenschaft: Die kausale Struktur des DAG stellt sicher, dass, wenn eine korrekte Replika einen Vertex broadcastet, alle korrekten Repliken diesen schließlich committen. Dies verhindert, dass Byzantinische Leader lokale Ordnungen von korrekten Repliken selektiv ignorieren.
Fairness-Schicht: Verarbeitet die committeten lokalen Ordnungen (Sub-DAGs) aus der DAG-Schicht, um eine endgültige, faire Transaktionsreihenfolge zu generieren.

Protokollvarianten

Das Paper führt zwei Varianten von FairDAG ein, die jeweils eine unterschiedliche Fairness-Eigenschaft garantieren:

A. FairDAG-AB (Absolute Fairness)

Ziel: Garantiert Ordering Linearizability. Wenn alle korrekten Repliken $T_1$ vor $T_2$ erhalten, muss $T_1$ vor $T_2$ geordnet werden.
Mechanismus:
- Jeder Transaktion wird ein Assigned Ordering Indicator (AOI) zugewiesen.
- Das Protokoll verwendet einen Ordering Indicator Manager (OIM), um gesehene und committe Bete Ordnung indikatoren zu verfolgen.
- Um die Latenz des DAG-Commits zu handhaben, berechnet es einen Lowest Possible AOI (LPAOI) für uncommitte Transaktionen. Eine Transaktion wird erst finalisiert, wenn ihr AOI strikt niedriger ist als der LPAOI aller anderen ausstehenden Transaktionen.
- Die endgültige Ordnung wird durch Sortierung der Transaktionen basierend auf ihren AOIs bestimmt.

B. FairDAG-RL (Relative Fairness)

Ziel: Garantiert $\gamma$ -Batch-Order-Fairness. Wenn ein Bruchteil $\gamma$ der korrekten Repliken $T_1$ vor $T_2$ erhält, dann wird $T_1$ spätestens mit $T_2$ geordnet.
Mechanismus:
- Konstruiert einen Dependency Graph, in dem Knoten Transaktionen sind und Kanten die Ordnungspräferenzen darstellen, die aus lokalen Ordnungen abgeleitet wurden.
- Schwellenwert-Optimierung: Im Gegensatz zu Leader-basierten Protokollen (Themis), die auf $n-2f$ committeten Ordnungen basieren (aufgrund potenzieller Leader-Exklusion), nutzt FairDAG die DAG-Validitätseigenschaft, um sicherzustellen, dass mindestens $n-f$ Ordnungen committet werden. Folglich erhöht es den Schwellenwert für die Kantenbildung von $\frac{n-2f}{2}$ auf $\frac{n-f}{2}$ .
- Graph-Kondensation: Das Protokoll identifiziert streng zusammenhängende Komponenten (Strongly Connected Components, SCCs) im Abhängigkeitsgraphen. Es finalisiert die Ordnung von "soliden" Knoten (solche mit ausreichenden committeten Ordnungen) und fügt "schattierte" Knoten in nachfolgende Graphen wieder hinzu, bis sie solide werden.
- Dieser Ansatz reduziert die Anzahl der korrekten Repliken, die zur Garantie von Fairness erforderlich sind (erfordert z. B. $n > 3f$ statt $n > 4f$ für $\gamma=1$ ).

3. Kernbeiträge

Neuartiges Framework: Der Vorschlag von FairDAG, dem ersten Framework, das Fairness-Protokolle mit Multi-Proposer DAG-basierten Konsens integriert und damit die Durchsatz- und Manipulationsschwachstellen von Leader-basierten Systemen adressiert.
FairDAG-AB: Ein absolutes Fairness-Protokoll, das Ordering Linearizability mittels eines adaptiven LPAOI-Mechanismus garantiert, der kompatibel mit DAG-Commit-Regeln ist.
FairDAG-RL: Ein relatives Fairness-Protokoll, das sich gegenüber Themis verbessert, indem es die DAG-Validität nutzt, um den Schwellenwert für die Konstruktion des Abhängigkeitsgraphen zu senken, wodurch die Anforderungen an korrekte Teilnehmer reduziert und die Performance gesteigert wird.
Neue DAG-Konstruktionsregeln: Einführung spezifischer Regeln (z. B. Einbeziehung schwacher Kanten für langsamere Repliken, Beibehaltung starker Kanten zu vorherigen lokalen Vertices), um sicherzustellen, dass Fairness-Eigenschaften gegenüber adversariellen Teilnehmern gewahrt bleiben.
Umfassende Evaluierung: Umfangreiche analytische Beweise für Sicherheit, Liveness und Fairness sowie experimentelle Validierung.

4. Experimentelle Ergebnisse

Die Autoren implementierten FairDAG in Apache ResilientDB und verglichen es mit Baselines: PBFT, Pompe, Themis, RCC und Tusk.

Durchsatz:
- FairDAG übertrifft Leader-basierte Fairness-Protokolle (Pompe und Themis) signifikant.
- FairDAG-AB erreichte einen 30,2 % bis 52,6 % höheren Durchsatz als Pompe.
- FairDAG-RL erreichte einen um 5,1 % bis 7,5 % höheren Durchsatz als Themis in Single-Region-Settings, wobei die Gewinne in geo-verteilten Settings auf 42,1 % anstiegen, bedingt durch die Robustheit des zugrunde liegenden DAG-Konsens.
Latenz:
- FairDAG-AB weist eine etwas höhere Latenz als Pompe auf (aufgrund der zugrunde liegenden Commit-Latenz von Tusk), bleibt aber wettbewerbsfähig.
- FairDAG-RL demonstriert eine niedrigere Latenz als Themis, wenn die Anzahl der fehlerhaften Repliken ( $f$ ) steigt, da Themis mehr korrekte Repliken benötigt, um Fairness zu garantieren, was den Overhead erhöht.
Resilienz gegenüber adversariellem Verhalten:
- Leader-Ausfall: In Experimenten, in denen der Leader fehlerhaft gemacht wurde, erlitten Pompe und Themis Durchsatzeinbußen während der View-Changes. FairDAG-Varianten zeigten aufgrund des Multi-Proposer-Designs keine Performance-Degradation.
  - Ordnungsmanipulation: Unter "Reversing Order" und "Targeted Delay" Angriffen durch Byzantinische Repliken hielten FairDAG-AB und FairDAG-RL konsistent ein höheres Verhältnis korrekt geordneter Transaktionspaare im Vergleich zu Pompe und Themis. Die Validitätseigenschaft des DAG milderte die Fähigkeit Byzantinischer Akteure effektiv ab, Ordnungen selektiv auszuschließen.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass FairDAG einen bedeutenden Fortschritt in der Blockchain-Fairness darstellt, indem es den Trade-off zwischen Performance und Fairness löst, der in Leader-basierten Systemen inhärent ist.

Resilienz: Durch die Entfernung des einzelnen Leaders verhindert FairDAG, dass Adversaries die endgültige Ordnung durch selektive Sammlung lokaler Ordnungen manipulieren.
Effizienz: Das Multi-Proposer-Design lindert den Durchsatz-Engpass, wodurch Fairness-Protokolle besser mit der Netzwerkgröße und Arbeitslast skalieren können.
Reduzierte Anforderungen: Die Validitätseigenschaft von DAGs erlaubt es FairDAG-RL, Fairness-Garantien mit weniger korrekten Teilnehmern zu erreichen als State-of-the-Art Leader-basierte Protokolle wie Themis.

Die Autoren kommen zu dem Schluss, dass FairDAG die Manipulation der Transaktionsreihenfolge durch Adversaries effektiv einschränkt und gleichzeitig eine überlegene Performance sowohl unter Normal- als auch unter adversariellen Bedingungen erzielt, was es zu einer lebensfähigen Lösung für faire Transaktionsreihenfolgen in dezentralisierten Finanzanwendungen und anderen kritischen Blockchain-Anwendungen macht.