💻 computer science

Distance-Preserving Digests: A Primitive for BFT Consensus

Dit artikel introduceert "afstandbehoudende samenvattingen", een primitief dat commutatieve vectorsommen in plaats van botsingsbestendige hashes gebruikt om efficiënte, enkelrondevoltooing en schaalbare boomgestructureerde BFT-consensus mogelijk te maken door validators in staat te stellen meningsverschillen in de staat te meten en consistentie te verifiëren zonder volledige staatssynchronisatie.

Oorspronkelijke auteurs: Ryan Patrick Mercier

Gepubliceerd 2026-05-18

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ryan Patrick Mercier

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je een enorme groep mensen voor die probeert overeen te komen over één enkele lijst met regels voor een spel. In de wereld van blockchain en beveiligde netwerken wordt deze groep een "consensusprotocol" genoemd. Decennialang was de standaardmanier om te controleren of iedereen het eens is, vergelijkbaar met het vergelijken van twee mensen' lijsten door ze om te zetten in één enkele, onbreekbare code (een "hash").

Hier is het probleem met die oude methode: Het vernietigt nuance.

Als persoon A 19 van de 20 juiste items heeft en persoon B alle 20 juist heeft, zegt de oude methode dat hun codes volledig verschillend zijn. Het is alsof je zegt dat een lijst met één typefout net zo "fout" is als een lijst zonder enige items. Omdat het systeem het onderscheid niet kan maken tussen "bijna perfect" en "volledig kapot", dwingt het iedereen om te stoppen, hun volledige lijsten opnieuw te sturen en te wachten op een perfecte overeenkomst voordat ze verder gaan. Dit is traag, duur en vereist enorme groepen mensen om veilig te zijn.

Dit artikel introduceert een nieuw hulpmiddel genaamd Afstandsbehoudende Digests. Denk hierbij aan een "vage match"-systeem dat de groep laat zien hoe dicht ze bij overeenstemming zijn, in plaats van alleen te vragen "Zijn we identiek?".

Het Kernidee: De "Vector Som"-Analogie

In plaats van een lijst met transacties om te zetten in één enkele, stijve code, stelt het artikel voor om elke transactie om te zetten in een klein pijltje (een vector) in een 8-dimensionale ruimte.

De Oude Manier: Als je één item mist, verandert je code volledig.
De Nieuwe Manier: Als je één item mist, beweegt je "pijltje" slechts een klein beetje van het centrum af. Als je tien items mist, beweegt het verder weg.

Dit stelt het systeem in staat om afstand te meten.

Afstand = 0: Iedereen heeft exact dezelfde lijst.
Afstand = Klein: Iedereen mist slechts één of twee items (misschien door een trage internetverbinding).
Afstand = Enorm: Iemand liegt of heeft een volledig andere lijst.

Drie Grote Verbeteringen

Het artikel beweert dat deze simpele verandering drie grote hoofdpijndossiers in blockchain-ontwerp oplost:

1. De "Snelle Strook" voor Overeenstemming

Oude Manier: Zelfs als iedereen perfect overeenkomt, moet het systeem drie trage rondes van stemming uitvoeren om zeker te zijn.
Nieuwe Manier: Omdat het systeem kan zien dat iedereen zeer dicht bij elkaar zit (afstand is bijna nul), kan het direct zeggen: "Oké, jullie zijn het allemaal eens!" en de beslissing in één ronde definitief maken. Het is alsof een leraar ziet dat een klas 99% klaar is en zegt: "Geweldig, laten we doorgaan", in plaats van te wachten op een formele stemming.

2. Kleinere, Diepere Teams

Oude Manier: Om veilig te zijn, moesten groepen (comités) enorm groot zijn (bijvoorbeeld 128 personen). Als een kleine groep zelfs maar een paar leugenaars had, kon de hele groep falen.
Nieuwe Manier: Omdat het systeem de leugenaars kan opsporen door hun "afstand" (ze zullen ver weg zijn van het groepsgemiddelde), kan het ze direct verwijderen. Dit betekent dat je veel kleinere groepen kunt hebben (bijvoorbeeld 10 personen) en toch veilig bent. Je kunt ook diepere "bomen" van deze groepen bouwen, waardoor het netwerk veel beter schaalbaar wordt.

3. Het Oplossen van Cross-Chain Chaos

Oude Manier: Wanneer twee verschillende delen van een blockchain met elkaar moeten praten, moeten ze meestal een bericht sturen voor elke afzonderlijke transactie om te controleren of ze overeenkomen. Dit is alsof je elke enkele baksteen in twee verschillende muren controleert om te zien of ze hetzelfde zijn.
Nieuwe Manier: Ze wisselen gewoon hun "afstands-samenvattingen" uit. Als de samenvattingen overeenkomen, prima. Als ze dat niet doen, gebruikt het systeem een speciale "Bloom Filter" (zoals een snelle checklist) om precies te vinden welke enkele bakstenen verschillend zijn en corrigeert alleen die. Dit verlaagt de communicatiekosten in veel gevallen met 99%.

Hoe Het Werkt (Het Twee-Fasen Proces)

Het artikel beschrijft een protocol genaamd Proxima dat dit hulpmiddel in twee stappen gebruikt:

Fase 1 (De "Vage" Check): Iedereen stuurt hun samenvatting. Het systeem berekent de afstand. Als iedereen dicht bij elkaar zit, slaat het de rest over en maakt het direct definitief. Als sommige mensen ver weg zijn, vraagt het systeem alleen die specifieke personen om hun ontbrekende data te sturen (met behulp van de Bloom Filter-truc).
Fase 2 (De "Harde" Check): Zodra de groep uitgelijnd is, ondertekent iedereen een definitief, onbreekbaar certificaat. Dit zorgt ervoor dat, zelfs als iemand probeerde het systeem in Fase 1 te bedriegen, ze de definitieve handtekening niet kunnen vervalsen.

De Resultaten

Het artikel vergelijkt dit nieuwe systeem (Proxima) met de huidige industriestandaard (HotStuff):

Snelheid: Op één computercore is Proxima ongeveer 20 keer sneller (0,9 seconde versus 18 seconden) omdat het onnodige rondes overslaat.
Efficiëntie: Met 100.000 validators stuurt Proxima 2,2 keer minder berichten dan het oude systeem.
Veiligheid: De wiskunde bewijst dat zolang minder dan 33% van de groep kwaadaardig is, het systeem niet kan worden bedrogen om twee verschillende regels tegelijkertijd te accepteren.

De Conclusie

Dit artikel stelt voor om een "stijf, alles-of-niets" controlesysteem te vervangen door een "flexibel, afstands-metend" systeem. Door te beseffen dat "bijna goed" eigenlijk nuttige informatie is, kan het systeem sneller bewegen, kleinere teams gebruiken en veel minder communiceren, terwijl het hetzelfde hoge veiligheidsniveau behoudt.

Technische Samenvatting: Afstandbehoudende Digests voor BFT-consensus

1. Probleemstelling

Byzantine Fault Tolerant (BFT) consensusprotocollen, waaronder HotStuff, PBFT en Ethereum 2.0, vertrouwen op botsingsbestendige hashes (bijv. SHA-256) om validatorstaten te vergelijken. Hoewel dit effectief is om vervalsing te voorkomen, vernietigt deze aanpak informatie over "afstand". Als twee validators het eens zijn over 19 van de 20 transacties, zijn hun hashes volledig ongerelateerd en niet te onderscheiden van validators die geen enkele transactie delen. Deze beperking legt drie structurele beperkingen op aan de BFT-literatuur:

Verplichte Staatssynchronisatie: Validators moeten hun staat volledig synchroniseren voordat ze stemmen, aangezien hashes geen gedeeltelijke overeenkomst kunnen meten.
Onmeetbare Kwaliteit van Overeenstemming: Protocollen kunnen geen unanieme overeenstemming detecteren totdat alle stemrondes zijn voltooid, wat vaste meertrapsvertragingen oplegt, zelfs onder ideale omstandigheden.
Grote Hiërarchische Commissies: Om veiligheid te garanderen in boomgestructureerde consensus, moeten bladgroepen groot genoeg zijn (bijv. 128 validators in Ethereum) om onafhankelijk de Byzantijnse tolerantiedrempel van $2N/3$ te halen, wat de boomdiepte en schaalbaarheid beperkt.

2. Methodologie: Afstandbehoudende Digests

Het artikel introduceert een primitief genaamd Afstandbehoudende Digests om botsingsbestendige hashes te vervangen voor staatvergelijking. De constructie omvat:

Vectorisatie: Elke transactie wordt gehasht met SHA-512. De 64-byte output wordt opgesplitst in 8 segmenten.
Coördinatenmapping: Elk segment wordt behandeld als een ongetekend geheel getal, gereduceerd modulo 10.000 en gedeeld door 10.000 om een coördinaat in het bereik $[0, 1)$ te produceren.
Commutatieve Sommatie: De digest van een validator voor een set transacties $T$ is de vector som $D(T) = \sum_{tx \in T} v(tx)$ in een 8-dimensionale ruimte.

Dit primitief bezit drie eigenschappen die hashes missen:

Proportionele Afstand: De Euclidische afstand tussen twee digesten is evenredig met het aantal verschillende transacties.
Exacte Samenvatting: Het gewogen gemiddelde van een groep digesten is een exacte representatie van de geaggregeerde staat van de groep, waardoor een groep validators kan worden samengevat tot één compacte waarde (76 bytes) zonder informatieverlies.
Identificatie van Setverschillen: Wanneer digesten verschillen, stelt een Bloom-filterdiff de aggregator in staat om precies te identificeren welke transacties ontbreken in het zicht van een validator, waardoor gerichte synchronisatie mogelijk is zonder volledige staatuitwisseling.

3. Belangrijkste Bijdragen en Toepassingen

Het artikel demonstreert drie primaire toepassingen van dit primitief binnen een nieuw protocol genaamd Proxima:

A. Tweefasig BFT-protocol (Proxima)

Proxima werkt in twee fasen:

Fase 1 (Afstandsfiltering): Validators sturen digesten en Bloom-filters naar een aggregator. De aggregator clustert validators binnen een afstandsdrempel. Als de clustervariantie dicht bij nul ligt (wat wijst op hoge overeenstemming), geeft het protocol een finaliteitscertificaat in één ronde uit (snelle weg). Zo niet, dan worden ontbrekende transacties via Bloom-diff doorgestuurd.
Fase 2 (Toezegging): Clusterleden ondertekenen de blokhash met BLS-handtekeningen. De aggregator produceert een geaggregeerde handtekening.
Resultaat: In tegenstelling tot HotStuff, dat drie rondes vereist ongeacht de overeenstemming, bereikt Proxima finaliteit in één ronde wanneer validators het eens zijn.

B. Boomgestructureerde Consensus met Kleine Groepen

Omdat afstandsfiltering op individueel niveau werkt in plaats van groepsgebonden BFT te vereisen, maakt Proxima hiërarchische consensus mogelijk met kleine groepen (bijv. 10 validators).

Mechanisme: Bladleiders filteren Byzantijnse validators eruit (die ver van de referentie verwijderd zijn) en rapporteren het gewogen gemiddelde van eerlijke validators.
Resultaat: Dit elimineert de noodzaak van grote commissies (128 validators) om veiligheid te garanderen, waardoor diepere bomen mogelijk zijn (5 niveaus versus 2–3 niveaus) en de berichtcomplexiteit wordt verminderd.

C. Cross-Shard Consistentieverificatie

Digesten maken verificatie met constante kosten tussen shards mogelijk.

Mechanisme: Naburige shards wisselen digesten van transacties in overlapzones uit. Als de afstand nul is, komen de staten overeen. Als deze niet-nul is, identificeert de Bloom-diff specifieke afwijkende transacties voor oplossing.
Resultaat: Dit vervangt de transactieper-transactie coördinatie van Two-Phase Commit (2PC) of ontvangstketens, en vermindert de cross-shard overhead met 99% ten opzichte van 2PC bij propagatiesnelheden van 95%.

4. Resultaten en Evaluatie

Het artikel evalueert Proxima tegen HotStuff, PBFT en de commissiestructuur van Ethereum met simulaties met $N=100.000$ validators en 30% Byzantijnse fouten.

Berichtcomplexiteit: Proxima Tree gebruikt 2,2× minder berichten dan HotStuff. Dit is een structurele eigenschap die niet wordt beïnvloed door parallelisme, afgeleid van tweefasige uitvoering, pre-filtering van Byzantijnse knopen en boomrouting met compacte samenvattingen.
Latentie:
- Single-Core: Proxima bereikt single-core finaliteit in ~0,9 seconden (902 ms) vergeleken met ~18 seconden voor HotStuff. De boomstructuur verdeelt BLS-aggregatie, waardoor verwerking op het kritieke pad laag blijft (9,9 ms).
- Multi-Core: Hoewel multi-core BLS-aggregatie de kloof verkleint (HotStuff daalt naar ~940 ms, Proxima Flat naar ~220 ms), behoudt de boom een voordeel in BLS-tijd op het kritieke pad omdat bladknopen zeer weinig handtekeningen verwerken.
Cross-Shard Overhead: Bij 95% propagatie gebruikt digest-gebaseerde verificatie 99% minder berichten dan 2PC en 95% minder dan op ontvangst gebaseerde benaderingen (NEAR Nightshade).
Veiligheid: Veiligheid is bewezen onafhankelijk van clustering in Fase 1. Minder dan $N/3$ Byzantijnse validators kunnen geen conflicterende finalisatie veroorzaken. Fase 1 kan eerlijke validators uitsluiten (levendigheidsrisico), maar dit is begrensd door de ongelijkheid van Hoeffding tot verwaarloosbaar ( $<10^{-9}$ bij praktische $N$ ).

5. Betekenis en Claims

Het artikel beweert dat afstandbehoudende digesten de drie fundamentele beperkingen die botsingsbestendige hashing oplegt aan BFT, wegnemen. Door het meten van de kwaliteit van overeenstemming mogelijk te maken, maakt het primitief het mogelijk voor:

Optimistische Snelle Wegen: Protocollen kunnen finaliteit bereiken in één ronde wanneer consensus hoog is.
Schaalbare Hiërarchieën: Consensusbomen kunnen kleine groepen (grootte 10) en diepe structuren gebruiken, aangezien veiligheid wordt gehandhaafd via afstandsfiltering in plaats van per-groep stemming.
Efficiënte Sharding: Cross-shard consistentie kan worden geverifieerd tegen een constante kosten per shardpaar, schaalend met de werkelijke divergentie in plaats van het totale transactievolume.

De auteurs benadrukken dat hoewel het primitief een bekende toepassing is van Locality-Sensitive Hashing (LSH) in datastructuren, de toepassing op Byzantijnse overeenstemming nieuw is. De veiligheid van het systeem rust op standaard cryptografische aannames (BLS-handtekeningen en SHA-512), waarbij de afstandfilter dient als een mechanisme voor levendigheid en optimalisatie in plaats van een veiligheidsmechanisme. Het artikel concludeert dat deze aanpak een algemene verbetering biedt voor elk BFT-protocol dat staten vergelijkt via hashes.