Distance-Preserving Digests: A Primitive for BFT Consensus Ryan Mercier
arXiv:2605.15329v1 [cs.CR] 14 May 2026
School of Engineering University of Connecticut Storrs, CT, USA [email protected]
Abstract—Every BFT consensus protocol uses collisionresistant hashes to compare validator state. Collision resistance destroys distance: two validators agreeing on 19 of 20 transactions produce unrelated hashes, indistinguishable from validators sharing nothing. This forces three design constraints across the BFT literature: validators must synchronize state before voting, agreement quality cannot be measured until votes are counted, and hierarchical committees must be large enough for independent BFT, limiting tree depth. This paper introduces distance-preserving transaction digests, a primitive that replaces collision-resistant hashes with commutative vector sums in 8dimensional space. The primitive has three properties hashes lack: distance is proportional to disagreement, weighted means are exact, and set differences are identifiable via bloom filter diff. We demonstrate three applications: a two-phase BFT protocol (Proxima) that achieves single-round finality when validators agree; tree-structured consensus with groups of 10 validators (vs 128 in Ethereum), enabled because distance filtering replaces per-group BFT; and cross-shard consistency verification at 128 bytes per shard pair, replacing the per-transaction coordination of two-phase commit. Safety is proved: fewer than N/3 Byzantine validators cannot cause conflicting finalization, independent of Phase 1 clustering or tree topology. At N =100,000, Proxima Tree uses 2.2× fewer messages than HotStuff (a structural property unaffected by parallelism). Single-core finality is ∼ 0.9s vs ∼ 18s for HotStuff; multi-core BLS narrows but does not eliminate this gap. Index Terms—Byzantine fault tolerance, blockchain, consensus protocols, locality-sensitive hashing, sharding
I. I NTRODUCTION BFT consensus has been built on collision-resistant hashing since PBFT [2]. Collision resistance is the right property for preventing forgery, but the wrong property for measuring agreement. When two validators compute SHA-256 of their transaction sets and the hashes differ, the protocol learns exactly one bit of information: not identical. It cannot tell whether they differ on one transaction or half the transactions. It cannot measure how close they are to agreement. It cannot summarize a group of validators as a single compact value. These limitations are baked into every protocol that uses hashes for state comparison. HotStuff [1] runs three voting rounds even when every validator agrees perfectly, because it has no way to detect unanimous agreement until all three rounds complete. Ethereum 2.0 [5] requires committees of 128 validators because each committee must independently Code and reproduction artifacts: https://github.com/RyanMercier/Proxima
reach 2/3 consensus, and small committees fail when random assignment concentrates Byzantine validators. Crossshard transactions require multi-round coordination (two-phase commit or receipt chains) because hashes cannot verify partial overlap between shard states. This paper proposes replacing collision-resistant hashes with distance-preserving digests for state comparison in BFT protocols. The primitive is simple: hash each transaction with SHA-512, split the 64-byte output into 8 segments, treat each as a coordinate, and sum across transactions. The result is a commutative vector in 8D space where Euclidean distance is proportional to transaction disagreement. The primitive is not novel in the data-structures sense (locality-sensitive hashing dates to Indyk and Motwani [11]), but its application to BFT consensus is new. No work in the LSH literature applies it to Byzantine agreement, and no work in the consensus literature reaches for distance-preserving functions. We demonstrate that this single primitive removes all three constraints. Agreement quality is measurable in one round (enabling fast-path finality). Hierarchical groups need not reach internal BFT (enabling groups of 10 and deeper trees). Crossshard consistency is verifiable at constant cost per shard pair. We implement these as Proxima, a working BFT blockchain, and evaluate message complexity, bandwidth, and projected latency against HotStuff, PBFT, and Ethereum’s committee structure. II. S YSTEM M ODEL We consider a system of N validators, of which at most f < N/3 are Byzantine. Byzantine validators may behave arbitrarily. Honest validators follow the protocol. Network model. We assume partial synchrony [12]: there exists an unknown Global Stabilization Time (GST) after which all messages between honest validators are delivered within a known bound ∆. This is the standard model for PBFT [2], HotStuff [1], and Tendermint [9]. Cryptographic assumptions. We assume a BLS signature scheme [3] where each validator holds a private key and the corresponding public key is known to all. BLS signatures support aggregation: any party can combine N individual signatures into a single 96-byte aggregate signature. We assume the hardness of the CDH problem in the BLS12-381 pairing group [4].
Communication model. Validators communicate through an aggregator (flat mode) or through a tree of relay nodes (tree mode). The aggregator/relay role rotates each round. A Byzantine aggregator can suppress messages (affecting liveness) but cannot forge BLS signatures (safety is maintained). Adversary model. The adversary is static: it chooses which validators to corrupt before the protocol begins. The adversary has full network visibility and can coordinate Byzantine strategies. Hash function model. We model SHA-512 as producing outputs uniformly distributed over {0, 1}512 . Each 64-bit segment, when reduced modulo 10000 and divided by 10000, produces a value uniformly distributed in [0, 1). Partial observation parameter. Honest validators may receive transactions with delay relative to the proposer. We parameterize this by pmiss , the per-validator probability of having an incomplete view at proposal time. We use pmiss = 0.37 throughout, drawn from internal measurements; this is conservative relative to typical mainnet conditions. III. T HE P RIMITIVE : D ISTANCE -P RESERVING D IGESTS A. Construction Each transaction tx is hashed with SHA-512, producing 64 bytes. The output is split into 8 segments of 8 bytes each. Each segment is interpreted as an unsigned integer, reduced modulo 10000, and divided by 10000 to produce a coordinate in [0, 1): v(tx) = seg0 /10000, . . . , seg7 /10000 A validator’s digest P for a set of transactions T is the commutative sum D(T ) = tx∈T v(tx). B. Properties Property 1: Proportional distance. If validators A and B have transaction sets differing by k transactions, the Euclidean distance between D(TA ) and D(TB ) grows proportionally with k. Empirically, k = 1 gives ∼ 1.6, k = 2 gives ∼ 3.0, k = 10 gives ∼ 14.5. Property 2: Exact summarization. The weighted mean of N is an exact representation of the group: mean = P digests P i Di wi / i wi . A group of 100 validators can be summarized as one 76-byte value (64-byte weighted mean + 4-byte count + 8-byte variance) with zero information loss. This does not hold for hashes. Property 3: Set difference identification. When two digests differ, a bloom filter [10] (25 bytes at a 1% per-lookup false positive rate for 20 transactions) lets the aggregator identify which transactions are present in one set but not the other. Bloom filters admit false positives but never false negatives, so a transaction the recipient legitimately needs is never silently dropped; we analyze the false-positive direction in Section VIII-E. The aggregator diffs the bloom against the full transaction set and pushes missing transactions in a single message, eliminating the request-response round-trip of traditional state synchronization.
C. Threshold Calibration The distance threshold separating honest-with-partialobservation from Byzantine-with-fabricated-state is calibrated by Monte Carlo simulation. We generate 2000 samples of honest validators missing 1–2 transactions, compute the 99th percentile of the resulting distance distribution, and multiply by a safety margin of 1.2. D. Probabilistic Liveness Bound Safety depends only on BLS signatures (Section VIII-A) and is independent of the distance threshold. Liveness depends on the threshold including at least 2N/3 honest validators. We derive a bound. Under the SHA-512 uniformity assumption, each transaction vector v(tx) has coordinates iid Uniform[0, 1) with mean 1/2 and variance 1/12. For k missing transactions, the difference S = v(tx1 ) + · · · + v(txk ) has E[∥S∥2 ] = 8(k/12+k 2 /4) = 2k/3+2k 2 , where the k 2p term is the meanoffset contribution. By Jensen, E[∥S∥] ≤ E[∥S∥2 ], giving upper bounds 1.63, 3.06, 4.47 at k = 1, 2, 3. Monte Carlo over 50,000 trials gives empirical means 1.61, 3.03, 4.44, consistent with the bound. An honest validator with partial observation misses at most kmax = 2 transactions. From the Monte Carlo calibration, the conditional probability of exceeding threshold τ = 4.9 is at most 0.005. Accounting for pmiss = 0.37, the unconditional per-validator exclusion probability is at most p = 0.005 · 0.37 = 0.00185. Let X be the number of honest validators excluded. X is a sum of N independent indicators bounded in [0, 1] with mean µ ≤ pN . Liveness fails only if X ≥ N/3. Since p ≪ 1/3, applying Hoeffding’s inequality with t = 1/3 − p: Pr X ≥ N/3 ≤ exp(−2N t2 ) ≤ exp(−0.22N ). This is below 10−9 at N = 100 and below 10−95 at N = 1000. IV. A PPLICATION 1: BFT C ONSENSUS P ROTOCOL A. Flat Protocol Phase 1: each validator sends its digest (64 bytes) and bloom filter (25 bytes) to the aggregator (N messages). The aggregator computes the reference digest, measures each validator’s Euclidean distance from the reference, and clusters validators within the threshold. The aggregator pushes missing transactions to incomplete validators via bloom diff, then broadcasts cluster assignments. If cluster variance is near zero, the aggregator issues a single-round finality certificate (fast path). No Phase 2 needed. Phase 2: cluster members send BLS-signed hash commitments (one 96-byte message each). The aggregator produces an aggregate BLS signature (96 bytes) and a signer bitmap (N/8 bytes). The finality proof is multicast to cluster members. Finality requires 2N/3 matching commitments.
Fig. 1. SHA-256 is distance-destroying; dropping even one transaction produces a completely unrelated hash. Transaction vectors are distance-preserving; distance grows proportionally with the number of missing transactions.
Fig. 2. Two-phase Proxima protocol with optimistic fast path. Phase 1 exchanges 64-byte digests and 25-byte bloom filters; the aggregator clusters validators within threshold τ and pushes missing transactions to stragglers via bloom diff. If cluster variance is near zero the protocol finalizes in one round trip; otherwise Phase 2 collects 96-byte BLS signatures on the SHA-256 block hash, producing a 96-byte aggregate plus N/8-byte signer bitmap. HotStuff (right column) requires three voting rounds regardless of agreement because collision-resistant hashes cannot reveal cluster agreement before votes are counted.
B. Tree Protocol Leaf groups do not need internal BFT. Distance filtering operates at the individual level. A group of 10 with 5 Byzantine excludes the 5 (they are far from the reference) and reports the weighted mean of the 5 honest validators. Groups never fail. Phase 1 (bottom-up): validators are grouped into leaves of size B (default 10). Each validator sends digest and bloom to its leaf leader (N messages). The leaf leader filters by distance, pushes missing transactions via bloom diff, and sends a 76-byte summary upstream. Internal nodes aggregate child summaries (weighted mean of means is exact). The root checks the global mean against the reference. Phase 2 (top-down then up): the root broadcasts a commit request down the tree. Each validator that passed the filter sends a BLS commit up. Each internal node aggregates child signatures (BLS is associative). The root produces the final aggregate and broadcasts the finality proof back down. C. Why Phase 2 Is Necessary The distance filter cannot distinguish an honest validator missing one transaction from a Byzantine validator who replaced one transaction with fraud. Both produce distance ∼ 1.6. Phase 2 catches the fraud: the Byzantine validator must sign the correct block hash, which it does not have. D. Comparison with Ethereum Committees Ethereum 2.0 [5] uses random committees of 128 with percommittee 2/3 BFT attestation. With 30% Byzantine globally, committee failure is the probability of drawing more than G/3 Byzantine validators. For G=10: Pr[Bin(10, 0.3) ≥ 4] ≈ 35%. For G=128: Pr[Bin(128, 0.3) ≥ 43] ≈ 21%. Proxima avoids this failure mode at the per-committee level. There is no per-group vote, so no group fails in the BFT sense. Simulation with 1000 validators, 300 Byzantine (30%), groups of 10: with per-group BFT, 37 of 100 leaves fail and only 499 validators participate; with distance filtering, all 700 honest validators contribute. A leaf of entirely Byzantine validators (rare under random assignment) produces a fabricated summary, but it still has to pass the root’s distance check against the reference. TABLE I E THEREUM C OMMITTEES VS P ROXIMA
coordination message. NEAR’s Nightshade [13] reduces this with receipts: the source shard generates a receipt the destination includes in its next block. Lower latency, but receipts scale with transaction volume. B. Digest-Based Verification Digests enable a different approach. Neighboring shards exchange digests of their overlap-zone transactions once per block. If the distance is zero, both shards processed the same transactions. If nonzero, the bloom diff identifies exactly which transactions diverged, and only those require resolution. The cost is fixed per shard pair: 128 bytes. Conflict resolution scales with actual divergence, not total cross-shard volume. C. Analytical Comparison At 1000 cross-shard transactions per pair, 100 validators per shard, 95% pre-deadline propagation (Table II): TABLE II C ROSS -S HARD OVERHEAD AT 1000 TXS , 95% PROPAGATION
Method
Messages
Bandwidth
X-shard
404,000 101,000 5,052
37,750 KB 12,625 KB 987 KB
4,000 1,000 52
2PC Receipt (NEAR) Digest (95%)
Digest comparison reduces messages by 99% vs 2PC and 95% vs receipts. The 2PC count derives from 4 cross-shard messages per transaction plus 2 intra-shard BFT rounds at the destination, each costing 2N messages with N =100: 1000 · (4 + 2 · 2 · 100) = 404,000. At 100% propagation, the digest cost drops to 2 messages (the digest exchange itself); the remaining 5% are identified by bloom diff and resolved individually, which is reasonable on networks with sub-second gossip and multi-second block intervals. D. Multi-Shard Scaling At 100 shards (ring topology, 100 cross-shard txs per pair, 95% propagation): 2PC uses 4,040,000 messages; receipt uses 1,010,000; digest uses 50,502. Digest overhead scales with conflicts (5% of transactions), not total volume. E. Why This Requires Digests
Group size Security Tree depth at N =100K Groups fail (30% Byz) Summary size/group
Ethereum
Proxima
128 (BFT) Per-group 2/3 vote 2–3 levels ∼ 21% 128 votes fwd.
10 (distance) Individual distance 5 levels 0% 76 bytes
V. A PPLICATION 2: C ROSS -S HARD C ONSISTENCY A. The Problem Cross-shard transactions are the bottleneck in sharded blockchains. Two-phase commit requires 4 cross-shard messages per transaction plus intra-shard BFT consensus on each
Hash-based verification tells you identical or not-identical. Digest-based verification tells you differ-by-approximately-ktransactions. The former requires falling back to full state exchange or per-transaction coordination. The latter allows targeted resolution of only the divergent transactions. VI. A PPLICATION 3: AGREEMENT Q UALITY M EASUREMENT Digests enable two capabilities hash-based protocols cannot provide. Optimistic fast path. When all validators have complete state, the cluster variance is zero. The aggregator detects this
Fig. 3. Cross-shard overhead as a function of pre-deadline propagation rate. 2PC and receipt costs are fixed; digest cost drops sharply as propagation improves. At 95% propagation (marked), digest comparison uses 99% fewer messages than 2PC.
in one round and issues a finality certificate immediately. HotStuff still runs 3 rounds because it cannot measure agreement quality before votes are counted. The fast-path probability is approximately (1 − pmiss )N ; at pmiss = 0.05 and N = 10 honest validators (the leaf-group regime) this is ≈ 60%, rising to ≈ 90% at pmiss = 0.01. Continuous validator reputation. A validator’s average distance from the reference over time is a continuous reputation score. Honest validators average 0.3–0.5; Byzantine validators average 7.2. This is richer than binary participation tracking. VII. E VALUATION A. Message Complexity All message counts are from simulation with 30% Byzantine and 37% partial observation, tracked by incrementing a counter on each simulated send (Table III).
1K 10K 100K
The tree’s primary latency contribution is distributing BLS signature aggregation. We use published blst [4] microbenchmarks (0.05ms per aggregate-add, 1.5ms per aggregate-verify), consistent with production measurements from Ethereum consensus client implementations [6], [8] and Ethereum Foundation performance updates [7]. Network RTT uses three tiers: 1ms intra-rack (LOCAL), 80ms intra-region (REGIONAL), 200ms cross-region (GLOBAL), with one tier-appropriate RTT per protocol phase. HotStuff has four phases (PREPARE, PRE COMMIT, COMMIT , DECIDE ): 4 · 200 = 800ms. Proxima Flat has three round-trip phases (digest exchange, cluster broadcast, commit/finality): 3 · 200 = 600ms. Proxima Tree pays one LOCAL leaf hop, (L−2) REGIONAL internal hops, and one GLOBAL root hop per phase, doubled to cover both phases: 2 · (1 + 3 · 80 + 200) = 882ms at L=5 (892ms in the table after small accounting overhead). TABLE IV P ROJECTED FINALITY LATENCY AT N =100,000. T HE SINGLE - CORE FIGURES COME FROM THE MESSAGE - COUNTER SIMULATION ; THE MULTI - CORE BLS ROW IS QUALITATIVE BECAUSE PARALLELIZING NON -BLS STAGES DEPENDS ON THE DEPLOYMENT.
TABLE III M ESSAGES PER BLOCK
N
B. BLS Aggregation Bottleneck
Prox. Tree
Prox. Flat
HotStuff
PBFT
2,990 30,042 300,245
3,348 33,600 335,803
6,518 65,180 651,800
2.0M 200M ∼20G
Proxima Tree is 2.2× fewer messages than HotStuff. Message savings come from: two phases instead of three, Byzantine exclusion before Phase 2 (700 commits instead of 1000), bloom sync replacing retransmission round-trips, and tree routing replacing broadcast with compact summaries.
Tree
Flat
HotStuff
BLS (1 core) Network RTT (model) Total finality (1 core)
9.9 ms 892 ms 902 ms
3,960 ms 600 ms 4,561 ms
17,595 ms 800 ms 18,395 ms
BLS only (16 cores)
∼ 10 ms
∼ 220 ms
∼ 940 ms
On a single core the flat aggregator spends 3.96s aggregating 70,000 BLS signatures; HotStuff spends ∼ 3× that across three voting rounds. The tree distributes BLS aggregation across
Fig. 4. Fast path probability as a function of partial-observation rate and honest validator count. Fast path dominates on good networks and decays with packet loss.
Fig. 5. Message complexity scaling across validator counts. Proxima Tree and Flat both grow linearly but at a lower slope than HotStuff. PBFT is plotted on log scale due to O(N 2 ) growth.
Fig. 6. Message distribution across tree levels at multiple scales. Level 0 (leaves) dominates because every validator sends its vector to a leaf leader. Internal levels (L1+) are nearly invisible because each has branching-factor fewer nodes.
leaves, so each aggregator handles few signatures and the critical-path BLS time is 9.9ms across four levels. With multicore BLS, flat aggregation drops to ∼ 220ms and each HotStuff round to ∼ 313ms (∼ 940ms across three rounds); the tree gains nothing from extra cores because each leaf already has only ∼ 7 signatures. The tree retains a structural advantage on critical-path BLS time at any core count, but the total finality multi-core picture additionally depends on whether non-BLS stages (e.g., HotStuff’s per-validator retransmit handling) parallelize, which we cannot answer without a deployed testbed. C. Caveats Multi-threaded baselines partially close the gap. The tree’s 9.9ms BLS time requires leaf leaders on separate machines; sequential execution on one machine matches flat cost. Conversely, BLS aggregation in flat protocols parallelizes well: a 16-way split reduces flat aggregation to ∼ 220ms and each HotStuff round to ∼ 313ms. The tree gains little from extra cores. The tree retains an advantage on critical-path BLS time at any core count, but total finality on multi-core hardware additionally depends on whether non-BLS stages parallelize, which we cannot answer without a deployed testbed. The structural advantages, namely message complexity, smaller hierarchical groups, and fast-path finality, are core-countindependent. Hierarchical HotStuff variants. Kauri [14] applies tree aggregation to HotStuff. A direct comparison would isolate the distance-filtering contribution from tree aggregation. This is left as future work. Projected, not measured. All latency numbers use published blst constants and standard RTT estimates, not measurements from a deployed system. D. Byzantine Tolerance The system tolerates up to 33% Byzantine, matching the standard BFT bound. In simulation: 100% consensus success from 0% to 33%, 0% at 35% and above. As Byzantine percentage increases, Proxima gets cheaper (fewer validators in Phase 2) while HotStuff’s cost is constant. VIII. S ECURITY A NALYSIS A. Safety Theorem 1 (Safety). If fewer than N/3 validators are Byzantine, Proxima never finalizes two different blocks at the same height. Proof: Finality requires a set C of signed commitments with |C| ≥ 2N/3, all containing the same block hash h. Assume for contradiction that blocks B and B ′ both finalize at height k with commitment sets C and C ′ . Since |C| ≥ 2N/3 and |C ′ | ≥ 2N/3, their intersection |C ∩ C ′ | ≥ N/3. Every validator in the intersection signed both H(B) and H(B ′ ). An honest validator signs at most one hash per height. Therefore the intersection is entirely Byzantine. But |C ∩ C ′ | ≥ N/3 contradicts f < N/3.
Corollary 1. Phase 1 cannot compromise safety. Incorrect inclusion of a Byzantine validator means it fails to produce a valid BLS signature. Incorrect exclusion of an honest validator reduces commit count (liveness) but no incorrect block is signed. Corollary 2. Tree routing cannot compromise safety. BLS aggregation is associative. A Byzantine tree node can suppress children’s signatures (liveness) but cannot forge signatures. B. Liveness Proxima provides liveness under: (1) f < N/3 Byzantine; (2) the distance threshold includes at least 2N/3 honest validators; (3) messages are eventually delivered. Condition (2) is bounded above: the probability that more than N/3 honest validators are excluded is at most exp(−0.22N ), negligible at any practical N . Under partial synchrony, a rotating aggregator with timeout ensures progress after GST. C. Collision Resistance A random Byzantine digest must land within Euclidean threshold τ of the reference in 8D. Treating the relevant support as a cube of side R ≈ 14 (the half-block distance scale), the probability is the volume ratio of an 8-ball of radius τ to that cube, ≈ 4.06 · (τ /R)8 . At τ = 4.9 and R = 14, this is ≈ 9.1 × 10−4 , or about 0.09%. Empirically, Monte Carlo over 10,000 trials shows 0.4% of blocks have a Byzantine validator inside the threshold; the empirical figure being a few times higher than the spherical estimate is the expected sign and magnitude when the digest distribution has heavierthan-uniform tails near the threshold, and serves as a sanity check on the analytical bound. In every case Phase 2 catches it (invalid BLS commitment), so the analysis bounds liveness cost rather than safety. D. Adversarial Transaction Construction A natural concern is whether a Byzantine validator can craft a transaction set T ′ ̸= T whose digest lands within τ of the honest reference D(T ). Distance-preserving digests are deliberately not collision-resistant; a reduction to SHA512 collision resistance would prove too much. The construction is, at our parameters, computationally easy: each v(tx) is determined by SHA-512(tx) and valid transactions must be signed by accounts the adversary controls (Sybils are free in a permissionless setting, so the binding constraint is gas cost per candidate). The matching condition is roughly 8 log2 (R/τ ) ≈ 12 bits at τ = 4.9, R ≈ 14, well within laptop reach for Wagner-style k-list search [22]. Phase 1 distance filtering therefore contributes no cryptographic security. The construction is feasible; that is fine, because Phase 2 requires every cluster member to sign a BLS commitment to the SHA256 block hash H(B), and the Byzantine cannot forge a signature on H(B) where B contains T . Theorem 1 does not invoke any property of D(·). Adversarial construction therefore costs the adversary effort in exchange for no safety violation; the worst-case effect is a failed Phase 2 round, indistinguishable from any other Byzantine signature withholding.
Fig. 7. BLS aggregation bottleneck. Flat and HotStuff processing grows linearly with N ; the tree stays roughly constant because each leaf processes at most branching-factor signatures in parallel. Right panel shows the tree/flat speedup factor growing with N .
Fig. 8. Total finality latency combining BLS processing and cross-region network RTT. Left: latency vs N . At small N network RTT dominates; at large N BLS processing dominates and the tree’s advantage grows. Right: breakdown at N =100,000.
E. Bloom Filter False Positives Bloom filters admit false positives but no false negatives. A false positive causes the aggregator to skip pushing a transaction V needs; V ’s digest then exceeds τ , V is excluded from the cluster, and V does not sign in Phase 2. The signing set shrinks by one. The chain bloom FP → exclusion → no signature is wholly a liveness chain: Theorem 1 depends only on collision-resistant hashing and BLS unforgeability, not on cluster membership, so an excluded validator cannot cause a wrong block to clear 2N/3. The 1% figure is per-
lookup, not per-validator: the aggregator queries only flagged stragglers and only against O(k) candidates, where k is the digest-implied gap (typically 1–5), giving a per-validator FP rate of kp ≈ 1–5%. Filter sizing is linear in transaction count and logarithmic in target FP rate, so scaling the filter with block size to maintain a bounded per-validator rate is a free parameter choice.
Fig. 9. Byzantine tolerance and cost scaling. All three protocols achieve 100% consensus success from 0–33% Byzantine and fail at 35%+. As Byzantine percentage increases, Proxima’s message and bandwidth costs decrease because excluded validators skip Phase 2.
IX. R ELATED W ORK BFT Consensus. PBFT [2] established practical BFT with O(N 2 ) message complexity. HotStuff [1] reduced this to O(N ) using leader-based aggregation and BLS threshold signatures. Tendermint [9] provides a similar O(N ) BFT protocol. All use collision-resistant hashes for state comparison and require full state synchronization before voting. Proxima shares HotStuff’s O(N ) voting complexity but adds Phase 1 distance-based pre-filtering and bloom-based synchronization. Hierarchical BFT. Kauri [14] applies tree aggregation to HotStuff, reducing the leader bottleneck. Kauri’s tree nodes still run per-group BFT (hash-based), requiring groups large enough for Byzantine tolerance. Proxima’s distance filtering removes this requirement, enabling groups of 10 vs 128 and deeper trees (5 levels vs 2–3). Ethereum 2.0 [5] uses random committees of 128 with per-committee BFT attestation; Proxima achieves similar distributed aggregation with groups 12.8× smaller. DAG-Based Protocols. Narwhal and Tusk [15] decouple data availability from consensus via a DAG of validator proposals. Bullshark [16] builds on Narwhal with a simpler consensus rule. These protocols solve a different problem but share the property that validators may have partial views. Digests could augment DAG protocols by measuring vertex agreement quality. Locality-Sensitive Hashing. LSH was introduced by Indyk and Motwani [11] for approximate nearest-neighbor search. SimHash [17] applies it to document similarity; MinHash [18] to Jaccard similarity; p-stable LSH [19] to Lp distances. Our digest is a simple LSH scheme applied to transaction sets. The application to BFT consensus is, to our knowledge, new. Sharding. Ethereum abandoned execution sharding in favor of data-availability sharding (Danksharding [20]). NEAR’s Nightshade [13] uses receipt-based communication. Shardeum uses an address-range approach with atomic cross-shard composability. Digest-based verification offers a complementary approach: constant-cost verification per shard pair with conflict resolution only for divergent transactions.
X. I MPLEMENTATION Proxima is implemented in Python as a working BFT blockchain with account-based state, HTTP node API, interactive demo, benchmarks, and the eight evaluation figures. BLS signatures use py-ecc [21] for the live demo and hashbased mocks preserving 96-byte signature sizes for large-scale benchmarks. All message counts are tracked by incrementing a counter on each simulated send, using identical byte constants for Proxima, HotStuff, and PBFT; we cross-validated this by running both BLS settings on the small-N demo and confirming identical per-block message totals. Code is available at https://github.com/RyanMercier/Proxima. XI. L IMITATIONS AND F UTURE W ORK Projected latency. All latency numbers use published blst benchmarks and standard RTT estimates. A deployed testbed across 3+ cloud regions would validate the model. The Caveats subsection covers the multi-threaded picture in detail. No comparison against hierarchical HotStuff. A direct comparison against Kauri would isolate distance filtering from tree aggregation. This is the most important missing evaluation. Adaptive adversary. The safety proof assumes static Byzantine assignment. An adaptive adversary who corrupts validators after seeing tree assignments requires VRF-based assignment with epoch rotation, which we describe but do not evaluate. Cross-shard propagation assumption. The 95% propagation rate is consistent with the order-of-magnitude gossip propagation typical at multi-second block intervals but not validated on a sharded testbed. XII. C ONCLUSION The BFT literature uses collision-resistant hashing for state comparison. We identified three constraints this imposes (mandatory state synchronization, unmeasurable agreement quality, and large hierarchical committees) and showed that distance-preserving digests remove all three. At N =100,000, Proxima Tree uses 2.2× fewer messages than HotStuff (a structural property unaffected by parallelism) and reduces
cross-shard overhead by 99% versus 2PC at 95% propagation. Single-core latency is ∼ 900ms vs ∼ 18s for HotStuff; multicore BLS narrows the gap considerably but the tree retains an advantage on critical-path BLS time at any core count. Safety is proved. The primitive is general and applies to any BFT protocol that compares state via hashes. R EFERENCES [1] M. Yin, D. Malkhi, M. K. Reiter, G. Golan-Gueta, and I. Abraham, “HotStuff: BFT Consensus with Linearity and Responsiveness,” in Proc. PODC, 2019. [2] M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” in Proc. OSDI, 1999. [3] D. Boneh, B. Lynn, and H. Shacham, “Short Signatures from the Weil Pairing,” J. Cryptol., vol. 17, no. 4, pp. 297–319, 2004. [4] Supranational, “blst: BLS12-381 signature library,” https://github.com/ supranational/blst. [5] Ethereum Foundation, “Ethereum 2.0 Beacon Chain Specification,” https://github.com/ethereum/consensus-specs. [6] Sigma Prime, “Lighthouse Update #27: BLS library performance,” https: //lighthouse-blog.sigmaprime.io/update-27.html, 2020. [7] Ethereum Foundation, “Eth2 Quick Update No. 8,” https://blog. ethereum.org/2020/05/12/eth2-quick-update-no-8, 2020. [8] J. Drake, “Pragmatic Signature Aggregation with BLS,” https://ethresear. ch/t/pragmatic-signature-aggregation-with-bls/2105, ethresear.ch, 2018. [9] E. Buchman, “Tendermint: Byzantine Fault Tolerance in the Age of Blockchains,” Ph.D. dissertation, University of Guelph, 2016. [10] B. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, 1970. [11] P. Indyk and R. Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” in Proc. STOC, 1998. [12] C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the Presence of Partial Synchrony,” J. ACM, vol. 35, no. 2, pp. 288–323, 1988. [13] A. Skidanov, “Nightshade: Near Protocol Sharding Design,” https: //pages.near.org/papers/nightshade/. [14] R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation,” in Proc. SOSP, 2021. [15] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus,” in Proc. EuroSys, 2022. [16] A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias, “Bullshark: DAG BFT Protocols Made Practical,” in Proc. CCS, 2022. [17] M. Charikar, “Similarity Estimation Techniques from Rounding Algorithms,” in Proc. STOC, 2002. [18] A. Broder, “On the Resemblance and Containment of Documents,” in Proc. SEQUENCES, 1997. [19] M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni, “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions,” in Proc. SCG, 2004. [20] Ethereum Foundation, “Danksharding,” https://ethereum.org/roadmap/ danksharding. [21] Ethereum Foundation, “py-ecc: Python BLS library,” https://github.com/ ethereum/py ecc. [22] D. Wagner, “A Generalized Birthday Problem,” in Proc. CRYPTO, 2002, pp. 288–304.