💻 computer science

Distance-Preserving Digests: A Primitive for BFT Consensus

This paper introduces "distance-preserving digests," a primitive using commutative vector sums instead of collision-resistant hashes to enable efficient, single-round finality and scalable tree-structured BFT consensus by allowing validators to measure state disagreement and verify consistency without full state synchronization.

Original authors: Ryan Patrick Mercier

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ryan Patrick Mercier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive group of people trying to agree on a single list of rules for a game. In the world of blockchain and secure networks, this group is called a "consensus protocol." For decades, the standard way to check if everyone agrees has been like comparing two people's lists by turning them into a single, unbreakable code (a "hash").

Here is the problem with that old method: It destroys nuance.

If Person A has 19 out of 20 correct items, and Person B has all 20 correct, the old method says their codes are completely different. It's like saying a list with one typo is just as "wrong" as a list with no items at all. Because the system can't tell the difference between "almost perfect" and "completely broken," it forces everyone to stop, re-send their entire lists, and wait for a perfect match before moving forward. This is slow, expensive, and requires huge groups of people to be safe.

This paper introduces a new tool called Distance-Preserving Digests. Think of it as a "fuzzy match" system that lets the group see how close they are to agreement, rather than just asking "Are we identical?"

The Core Idea: The "Vector Sum" Analogy

Instead of turning a list of transactions into a single, rigid code, the paper suggests turning each transaction into a tiny arrow (a vector) in an 8-dimensional space.

The Old Way: If you miss one item, your code changes completely.
The New Way: If you miss one item, your "arrow" moves just a tiny bit away from the center. If you miss ten items, it moves further away.

This allows the system to measure distance.

Distance = 0: Everyone has the exact same list.
Distance = Tiny: Everyone is missing just one or two items (maybe due to a slow internet connection).
Distance = Huge: Someone is lying or has a completely different list.

Three Big Improvements

The paper claims this simple change solves three major headaches in blockchain design:

1. The "Fast Lane" for Agreement

Old Way: Even if everyone agrees perfectly, the system must run three slow rounds of voting to be sure.
New Way: Because the system can see that everyone is very close (distance is near zero), it can instantly say, "Okay, you all agree!" and finalize the decision in one round. It's like a teacher seeing a class is 99% ready and saying, "Great, let's move on," instead of waiting for a formal vote.

2. Smaller, Deeper Teams

Old Way: To be safe, groups (committees) had to be huge (e.g., 128 people). If a small group had even a few liars, the whole group might fail.
New Way: Because the system can spot the liars by their "distance" (they will be far away from the group average), it can kick them out immediately. This means you can have much smaller groups (e.g., 10 people) and still be safe. You can also build deeper "trees" of these groups, making the network scale much better.

3. Fixing Cross-Chain Messes

Old Way: When two different parts of a blockchain need to talk to each other, they usually have to send a message for every single transaction to check if they match. This is like checking every single brick in two different walls to see if they are the same.
New Way: They just exchange their "distance summaries." If the summaries match, great. If they don't, the system uses a special "Bloom Filter" (like a quick checklist) to find exactly which few bricks are different and only fixes those. This cuts the communication cost by 99% in many cases.

How It Works (The Two-Phase Process)

The paper describes a protocol called Proxima that uses this tool in two steps:

Phase 1 (The "Fuzzy" Check): Everyone sends their summary. The system calculates the distance. If everyone is close, it skips the rest and finalizes immediately. If some people are far away, the system asks only those specific people to send their missing data (using the Bloom Filter trick).
Phase 2 (The "Hard" Check): Once the group is aligned, everyone signs a final, unbreakable certificate. This ensures that even if someone tried to trick the system in Phase 1, they can't forge the final signature.

The Results

The paper compares this new system (Proxima) against the current industry standard (HotStuff):

Speed: On a single computer core, Proxima is roughly 20 times faster (0.9 seconds vs. 18 seconds) because it skips unnecessary rounds.
Efficiency: With 100,000 validators, Proxima sends 2.2 times fewer messages than the old system.
Safety: The math proves that as long as less than 33% of the group is malicious, the system cannot be tricked into accepting two different rules at the same time.

The Bottom Line

This paper proposes swapping out a "rigid, all-or-nothing" checking system for a "flexible, distance-measuring" one. By realizing that "almost right" is actually useful information, the system can move faster, use smaller teams, and communicate much less, all while keeping the same high level of security.

Technical Summary: Distance-Preserving Digests for BFT Consensus

1. Problem Statement

Byzantine Fault Tolerant (BFT) consensus protocols, including HotStuff, PBFT, and Ethereum 2.0, rely on collision-resistant hashes (e.g., SHA-256) to compare validator states. While effective for preventing forgery, this approach destroys "distance" information. If two validators agree on 19 out of 20 transactions, their hashes are completely unrelated, indistinguishable from validators sharing no transactions. This limitation imposes three structural constraints on BFT literature:

Mandatory State Synchronization: Validators must fully synchronize state before voting, as hashes cannot measure partial agreement.
Unmeasurable Agreement Quality: Protocols cannot detect unanimous agreement until all voting rounds are complete, forcing fixed multi-round latencies even in ideal conditions.
Large Hierarchical Committees: To ensure safety in tree-structured consensus, leaf groups must be large enough (e.g., 128 validators in Ethereum) to independently satisfy the $2N/3$ Byzantine tolerance threshold, limiting tree depth and scalability.

2. Methodology: Distance-Preserving Digests

The paper introduces a primitive called Distance-Preserving Digests to replace collision-resistant hashes for state comparison. The construction involves:

Vectorization: Each transaction is hashed using SHA-512. The 64-byte output is split into 8 segments.
Coordinate Mapping: Each segment is treated as an unsigned integer, reduced modulo 10,000, and divided by 10,000 to produce a coordinate in the range $[0, 1)$ .
Commutative Summation: A validator's digest for a set of transactions $T$ is the vector sum $D(T) = \sum_{tx \in T} v(tx)$ in 8-dimensional space.

This primitive possesses three properties that hashes lack:

Proportional Distance: The Euclidean distance between two digests is proportional to the number of differing transactions.
Exact Summarization: The weighted mean of a group of digests is an exact representation of the group's aggregate state, allowing a group of validators to be summarized into a single compact value (76 bytes) without information loss.
Set Difference Identification: When digests differ, a Bloom filter diff allows the aggregator to identify exactly which transactions are missing from a validator's view, enabling targeted synchronization without full state exchange.

3. Key Contributions and Applications

The paper demonstrates three primary applications of this primitive within a new protocol named Proxima:

A. Two-Phase BFT Protocol (Proxima)

Proxima operates in two phases:

Phase 1 (Distance Filtering): Validators send digests and Bloom filters to an aggregator. The aggregator clusters validators within a distance threshold. If the cluster variance is near zero (indicating high agreement), the protocol issues a single-round finality certificate (fast path). If not, it pushes missing transactions via Bloom diff.
Phase 2 (Commitment): Cluster members sign the block hash using BLS signatures. The aggregator produces an aggregate signature.
Result: Unlike HotStuff, which requires three rounds regardless of agreement, Proxima achieves single-round finality when validators agree.

B. Tree-Structured Consensus with Small Groups

Because distance filtering operates at the individual level rather than requiring group-level BFT, Proxima enables hierarchical consensus with small groups (e.g., 10 validators).

Mechanism: Leaf leaders filter out Byzantine validators (who are far from the reference) and report the weighted mean of honest validators.
Result: This eliminates the need for large committees (128 validators) to ensure safety, allowing for deeper trees (5 levels vs. 2–3 levels) and reducing message complexity.

C. Cross-Shard Consistency Verification

Digests enable constant-cost verification between shards.

Mechanism: Neighboring shards exchange digests of overlap-zone transactions. If the distance is zero, states match. If non-zero, the Bloom diff identifies specific divergent transactions for resolution.
Result: This replaces the per-transaction coordination of Two-Phase Commit (2PC) or receipt chains, reducing cross-shard overhead by 99% compared to 2PC at 95% propagation rates.

4. Results and Evaluation

The paper evaluates Proxima against HotStuff, PBFT, and Ethereum's committee structure using simulations with $N=100,000$ validators and 30% Byzantine faults.

Message Complexity: Proxima Tree uses 2.2× fewer messages than HotStuff. This is a structural property unaffected by parallelism, derived from two-phase execution, pre-filtering of Byzantine nodes, and tree routing with compact summaries.
Latency:
- Single-Core: Proxima achieves single-core finality in ~0.9 seconds (902 ms) compared to ~18 seconds for HotStuff. The tree structure distributes BLS aggregation, keeping critical-path processing low (9.9 ms).
- Multi-Core: While multi-core BLS aggregation narrows the gap (HotStuff drops to ~940 ms, Proxima Flat to ~220 ms), the tree retains an advantage in critical-path BLS time because leaf nodes process very few signatures.
Cross-Shard Overhead: At 95% propagation, digest-based verification uses 99% fewer messages than 2PC and 95% fewer than receipt-based approaches (NEAR Nightshade).
Safety: Safety is proven independent of Phase 1 clustering. Fewer than $N/3$ Byzantine validators cannot cause conflicting finalization. Phase 1 may exclude honest validators (liveness risk), but this is bounded by Hoeffding's inequality to be negligible ( $<10^{-9}$ at practical $N$ ).

5. Significance and Claims

The paper claims that distance-preserving digests remove the three fundamental constraints imposed by collision-resistant hashing in BFT. By enabling the measurement of agreement quality, the primitive allows for:

Optimistic Fast Paths: Protocols can finalize in one round when consensus is high.
Scalable Hierarchies: Consensus trees can utilize small groups (size 10) and deep structures, as safety is maintained via distance filtering rather than per-group voting.
Efficient Sharding: Cross-shard consistency can be verified at a constant cost per shard pair, scaling with actual divergence rather than total transaction volume.

The authors emphasize that while the primitive is a known application of Locality-Sensitive Hashing (LSH) in data structures, its application to Byzantine agreement is novel. The safety of the system relies on standard cryptographic assumptions (BLS signatures and SHA-512), with the distance filter serving as a liveness and optimization mechanism rather than a safety mechanism. The paper concludes that this approach offers a general improvement for any BFT protocol that compares state via hashes.