pith. sign in

arxiv: 2605.15329 · v1 · pith:Z2GXCAU2new · submitted 2026-05-14 · 💻 cs.CR

Distance-Preserving Digests: A Primitive for BFT Consensus

Ryan Patrick Mercier This is my paper

Pith reviewed 2026-05-19 14:53 UTC · model grok-4.3

classification 💻 cs.CR
keywords distance-preserving digestsBFT consensusvector-sum digestsByzantine fault tolerancetransaction digeststree-structured consensuscross-shard verificationfinality latency
0
0 comments X

The pith

Replacing collision-resistant hashes with 8D vector-sum digests lets BFT protocols measure agreement early and use smaller committees while keeping safety.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tries to establish that standard hashes destroy useful distance information between validator states, which forces BFT designs to synchronize fully before voting and to use large independent committees. By switching to commutative vector sums in 8-dimensional space as digests, distances become proportional to actual transaction disagreements, weighted means become exact, and set differences become detectable. A sympathetic reader would care because this removes three longstanding constraints in the field: pre-vote synchronization, late agreement measurement, and the need for oversized hierarchical groups. If correct, the change supports single-round finality on agreement, tree structures with groups of ten validators, and cheap cross-shard checks, all while a safety argument shows fewer than N/3 faulty validators cannot produce conflicting final decisions.

Core claim

The central claim is that distance-preserving transaction digests built from commutative vector sums in 8-dimensional space supply three properties hashes lack: distance scales with disagreement, weighted means are exact, and set differences are identifiable via bloom-filter differences. These properties enable a two-phase protocol that reaches finality in one round when validators agree, tree-structured consensus using groups of only ten validators, and cross-shard consistency checks at 128 bytes per shard pair. The paper proves that fewer than N/3 Byzantine validators cannot cause conflicting finalization, and this guarantee holds independently of Phase-1 clustering or tree topology.

What carries the argument

The 8-dimensional vector-sum construction for transaction digests, which produces distances proportional to disagreement and exact weighted means for arbitrary transaction sets.

If this is right

  • Validators can measure agreement quality before counting votes and therefore avoid full state synchronization before each round.
  • Tree-structured consensus becomes safe with groups of ten validators instead of the larger sizes needed for independent BFT inside each subtree.
  • Cross-shard consistency can be verified with a fixed 128-byte digest per shard pair rather than per-transaction coordination.
  • At 100,000 validators the protocol uses 2.2 times fewer messages than HotStuff as a direct structural consequence.
  • Single-core finality latency drops to 0.9 seconds while the multi-core gap with prior protocols narrows but remains positive.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same digest could be used in any distributed system that must detect partial state agreement without waiting for full votes.
  • Live networks could dynamically resize committees once measured distances fall below a chosen threshold.
  • Lower-dimensional variants might be tested on real transaction traces to see whether eight dimensions are necessary for typical workloads.

Load-bearing premise

The specific 8-dimensional vector-sum construction actually produces distances proportional to disagreement and exact weighted means for arbitrary transaction sets.

What would settle it

An explicit counter-example in which two transaction sets differing in five items yield a vector-sum distance indistinguishable from sets differing in fifty items, or a simulation run in which fewer than N/3 Byzantine validators produce two conflicting final decisions.

Figures

Figures reproduced from arXiv: 2605.15329 by Ryan Patrick Mercier.

Figure 1
Figure 1. Figure 1: SHA-256 is distance-destroying; dropping even one transaction produces a completely unrelated hash. Transaction vectors are distance-preserving; [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two-phase Proxima protocol with optimistic fast path. Phase 1 exchanges 64-byte digests and 25-byte bloom filters; the aggregator clusters validators [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 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. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Fast path probability as a function of partial-observation rate and honest validator count. Fast path dominates on good networks and decays with [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Message complexity scaling across validator counts. Proxima Tree and Flat both grow linearly but at a lower slope than HotStuff. PBFT is plotted [PITH_FULL_IMAGE:figures/full_fig_p006_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Message distribution across tree levels at multiple scales. Level 0 (leaves) dominates because every validator sends its vector to a leaf leader. Internal [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: BLS aggregation bottleneck. Flat and HotStuff processing grows linearly with [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Total finality latency combining BLS processing and cross-region network RTT. Left: latency vs [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Byzantine tolerance and cost scaling. All three protocols achieve [PITH_FULL_IMAGE:figures/full_fig_p009_9.png] view at source ↗
read the original abstract

Every BFT consensus protocol uses collision-resistant 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 8-dimensional 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.2x 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper introduces distance-preserving transaction digests based on commutative 8-dimensional vector sums as a replacement for collision-resistant hashes in BFT consensus. This primitive is claimed to provide distance proportional to disagreement, exact weighted means, and identifiable set differences. It is applied to a two-phase protocol (Proxima) for single-round finality on agreement, tree-structured consensus with groups of size 10, and efficient cross-shard verification. The manuscript asserts a safety proof that fewer than N/3 Byzantine validators cannot produce conflicting finalization independent of Phase-1 clustering or tree topology, along with performance results at N=100,000 showing 2.2x fewer messages than HotStuff and lower latency.

Significance. If the distance-proportionality and exact-mean properties can be established rigorously for arbitrary transaction sets and the safety proof verified, the primitive could enable meaningfully more efficient large-scale BFT designs by reducing synchronization overhead and permitting smaller hierarchical committees. The reported structural message savings would be of interest to blockchain and distributed-systems practitioners.

major comments (2)
  1. [Abstract] Abstract: The safety theorem asserts that fewer than N/3 Byzantine validators cannot cause conflicting finalization independent of Phase 1 clustering. This independence requires that small Euclidean distance between 8D vector sums implies small symmetric difference on the underlying transaction sets. The construction (fixed vector per transaction, commutative sum) admits distinct sets with identical sums once the number of transactions exceeds 8, because R^8 permits non-trivial linear dependencies; a Byzantine validator can therefore produce a digest that passes distance filtering while disagreeing on many transactions, violating the premise of the clustering-independent safety argument.
  2. [Abstract] Abstract: The claims that the primitive yields 'distance proportional to disagreement,' 'exact weighted means,' and 'set differences identifiable via bloom filter diff' for arbitrary transaction sets are stated without derivation, security assumptions, or proof sketch. These properties are load-bearing for both the distance-filtering step in Proxima and the cross-shard verification application.
minor comments (1)
  1. [Abstract] The performance numbers (2.2x message reduction, 0.9 s vs 18 s single-core finality) are presented without reference to the underlying communication model, workload, or simulation parameters that would allow verification of the 'structural property' claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on the safety argument and the need for explicit derivations of the primitive's properties. The comments correctly highlight areas where additional rigor is required. We respond point-by-point below, indicating the revisions we will incorporate.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The safety theorem asserts that fewer than N/3 Byzantine validators cannot cause conflicting finalization independent of Phase 1 clustering. This independence requires that small Euclidean distance between 8D vector sums implies small symmetric difference on the underlying transaction sets. The construction (fixed vector per transaction, commutative sum) admits distinct sets with identical sums once the number of transactions exceeds 8, because R^8 permits non-trivial linear dependencies; a Byzantine validator can therefore produce a digest that passes distance filtering while disagreeing on many transactions, violating the premise of the clustering-independent safety argument.

    Authors: The referee correctly notes that in R^8, linear dependence relations among more than eight transaction vectors can produce distinct sets with identical sums. This is a valid observation that could allow a digest collision with large symmetric difference. In the revised manuscript we will add an explicit assumption that transaction vectors are assigned via a deterministic but generic mapping (e.g., a fixed random projection seeded by transaction content) and provide a probabilistic bound showing that the probability of a non-trivial dependence for sets of practical size is negligible. The safety theorem will be restated to hold with high probability over this vector assignment, thereby restoring the clustering-independent guarantee under the stated assumption. We will also include a short counter-example discussion to make the limitation transparent. revision: partial

  2. Referee: [Abstract] Abstract: The claims that the primitive yields 'distance proportional to disagreement,' 'exact weighted means,' and 'set differences identifiable via bloom filter diff' for arbitrary transaction sets are stated without derivation, security assumptions, or proof sketch. These properties are load-bearing for both the distance-filtering step in Proxima and the cross-shard verification application.

    Authors: We agree that the three properties require explicit derivation. They follow directly from the linearity and commutativity of the vector-sum operation together with the Euclidean norm, but the manuscript omitted the short algebraic steps. In the revision we will insert a dedicated subsection (or appendix) that (i) proves distance proportionality under the generic-vector assumption, (ii) shows that the weighted mean of two digests is exactly the digest of the weighted union, and (iii) explains how a Bloom-filter difference on the underlying sets can be recovered from the vector difference when the sets are small. The necessary security assumption (vectors in general position) will be stated clearly. revision: yes

Circularity Check

0 steps flagged

No circularity: safety proof rests on asserted properties of the new 8D vector-sum primitive rather than reducing to fitted inputs or self-citations.

full rationale

The paper defines a commutative vector-sum construction in R^8 as the core primitive, asserts three properties (distance proportional to disagreement, exact weighted means, bloom-filter diff), and then proves safety for the BFT protocol (fewer than N/3 Byzantine validators cannot cause conflicting finalization) while stating that the proof holds independently of Phase-1 clustering or tree topology. No equations, parameters, or results are shown to be fitted to data and then re-labeled as predictions. No self-citations appear as load-bearing steps for uniqueness theorems or ansatzes. The derivation chain is therefore self-contained: the primitive is introduced as new, its properties are taken as given for the subsequent protocol analysis, and the safety claim does not reduce by construction to those inputs. Any question about whether distinct transaction sets can share the same 8D sum is a matter of whether the asserted properties actually hold, not a circularity in the logical steps presented.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The approach rests on standard properties of vector addition plus the new 8D construction whose distance and averaging properties are asserted but not derived in the visible text.

free parameters (1)
  • embedding dimension
    The choice of exactly 8 dimensions for the vector space is stated without derivation or sensitivity analysis in the abstract.
axioms (1)
  • standard math Vector addition over the chosen field is commutative and associative.
    Required for the digest to be independent of transaction order.
invented entities (1)
  • distance-preserving digest no independent evidence
    purpose: Replace collision-resistant hashes while retaining proportional distance and exact weighted means.
    New primitive introduced by the paper; no independent evidence supplied in the abstract.

pith-pipeline@v0.9.0 · 5796 in / 1174 out tokens · 94033 ms · 2026-05-19T14:53:27.840872+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/Breath1024.lean period8 echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    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.

  • IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Safety is proved: fewer than N/3 Byzantine validators cannot cause conflicting finalization, independent of Phase 1 clustering or tree topology.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    HotStuff: BFT Consensus with Linearity and Responsiveness,

    M. Yin, D. Malkhi, M. K. Reiter, G. Golan-Gueta, and I. Abraham, “HotStuff: BFT Consensus with Linearity and Responsiveness,” inProc. PODC, 2019

    work page 2019

  2. [2]

    Practical Byzantine Fault Tolerance,

    M. Castro and B. Liskov, “Practical Byzantine Fault Tolerance,” inProc. OSDI, 1999

    work page 1999

  3. [3]

    Short Signatures from the Weil Pairing,

    D. Boneh, B. Lynn, and H. Shacham, “Short Signatures from the Weil Pairing,”J. Cryptol., vol. 17, no. 4, pp. 297–319, 2004

    work page 2004

  4. [4]

    blst: BLS12-381 signature library,

    Supranational, “blst: BLS12-381 signature library,” https://github.com/ supranational/blst

    work page

  5. [5]

    Ethereum 2.0 Beacon Chain Specification,

    Ethereum Foundation, “Ethereum 2.0 Beacon Chain Specification,” https://github.com/ethereum/consensus-specs

    work page

  6. [6]

    Lighthouse Update #27: BLS library performance,

    Sigma Prime, “Lighthouse Update #27: BLS library performance,” https: //lighthouse-blog.sigmaprime.io/update-27.html, 2020

    work page 2020

  7. [7]

    Eth2 Quick Update No. 8,

    Ethereum Foundation, “Eth2 Quick Update No. 8,” https://blog. ethereum.org/2020/05/12/eth2-quick-update-no-8, 2020

    work page 2020

  8. [8]

    Pragmatic Signature Aggregation with BLS,

    J. Drake, “Pragmatic Signature Aggregation with BLS,” https://ethresear. ch/t/pragmatic-signature-aggregation-with-bls/2105, ethresear.ch, 2018

    work page 2018

  9. [9]

    Tendermint: Byzantine Fault Tolerance in the Age of Blockchains,

    E. Buchman, “Tendermint: Byzantine Fault Tolerance in the Age of Blockchains,” Ph.D. dissertation, University of Guelph, 2016

    work page 2016

  10. [10]

    Space/Time Trade-offs in Hash Coding with Allowable Errors,

    B. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors,”Commun. ACM, vol. 13, no. 7, pp. 422–426, 1970

    work page 1970

  11. [11]

    Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,

    P. Indyk and R. Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,” inProc. STOC, 1998

    work page 1998

  12. [12]

    Consensus in the Presence of Partial Synchrony,

    C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the Presence of Partial Synchrony,”J. ACM, vol. 35, no. 2, pp. 288–323, 1988

    work page 1988

  13. [13]

    Nightshade: Near Protocol Sharding Design,

    A. Skidanov, “Nightshade: Near Protocol Sharding Design,” https: //pages.near.org/papers/nightshade/

    work page

  14. [14]

    Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation,

    R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation,” inProc. SOSP, 2021

    work page 2021

  15. [15]

    Nar- whal and Tusk: A DAG-based Mempool and Efficient BFT Consensus,

    G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Nar- whal and Tusk: A DAG-based Mempool and Efficient BFT Consensus,” inProc. EuroSys, 2022

    work page 2022

  16. [16]

    Bullshark: DAG BFT Protocols Made Practical,

    A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias, “Bullshark: DAG BFT Protocols Made Practical,” inProc. CCS, 2022

    work page 2022

  17. [17]

    Similarity Estimation Techniques from Rounding Algo- rithms,

    M. Charikar, “Similarity Estimation Techniques from Rounding Algo- rithms,” inProc. STOC, 2002

    work page 2002

  18. [18]

    On the Resemblance and Containment of Documents,

    A. Broder, “On the Resemblance and Containment of Documents,” in Proc. SEQUENCES, 1997

    work page 1997

  19. [19]

    Locality-Sensitive Hashing Scheme Based onp-Stable Distributions,

    M. Datar, N. Immorlica, P. Indyk, and V . Mirrokni, “Locality-Sensitive Hashing Scheme Based onp-Stable Distributions,” inProc. SCG, 2004

    work page 2004

  20. [20]

    Danksharding,

    Ethereum Foundation, “Danksharding,” https://ethereum.org/roadmap/ danksharding

    work page

  21. [21]

    py-ecc: Python BLS library,

    Ethereum Foundation, “py-ecc: Python BLS library,” https://github.com/ ethereum/py ecc

    work page

  22. [22]

    A Generalized Birthday Problem,

    D. Wagner, “A Generalized Birthday Problem,” inProc. CRYPTO, 2002, pp. 288–304

    work page 2002