A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction

Source: arXiv:2606.18966 · Published 2026-06-17 · By Amos Brocco

TL;DR

This paper addresses a significant gap in Conflict-free Replicated Data Types (CRDTs), which ensure strong eventual consistency but typically assume honest participants and do not handle Byzantine (arbitrary or malicious) behavior well. Instead of relying on rejecting or excluding malicious updates via validation alone, the author proposes deterministic state reconstruction, where all received updates are incorporated, but only a deterministic subset contributes to the visible state. This approach guarantees convergence even under arbitrary update injection and equivocation without requiring global agreement on update validity.

The work is instantiated in Melda, a delta-state CRDT for JSON documents that operates as a non-intrusive overlay on application data. Melda organizes immutable updates as causally linked delta blocks and reconstructs the application state deterministically by resolving a revision tree and causal dependencies. The paper formalizes this model and proves that replicas applying the same set of updates reach the same state despite Byzantine faults such as equivocation, omission, or message reordering. It extends Melda with pluggable security layers for authentication, authorization, and encryption without breaking convergence. Overall, this decouples update dissemination and agreement from state derivation, enabling Byzantine tolerance via deterministic interpretation rather than validation or exclusion alone.

Key findings

• Deterministic validation of delta blocks depends only on update content, declared dependencies, and local trust policies, ensuring identical acceptance decisions across replicas (Lemma 4.1).
• Causal applicability—deciding when an update can be applied—is deterministic, relying on availability of anchors and validity, so replicas apply updates consistently once they share the same set (Lemma 4.2).
• The delta block dependency graph is acyclic due to monotonic indexing, preventing cycles and ensuring validation terminates (Lemma 4.3).
• State reconstruction is deterministic and order-independent, based on a topological order of accepted updates, guaranteeing convergence under arbitrary and equivocated update injection (Lemma 4.4).
• Adversarial nodes can inject arbitrary updates, including malformed or conflicting ones, but these are either filtered by validation or deterministically incorporated without causing divergence.
• Authentication, authorization, and confidentiality can be layered as refinements of validity predicates without breaking convergence or requiring global coordination.
• Melda supports opportunistic asynchronous synchronization, allowing replicas to operate offline and independently commit and later incorporate remote updates without coordination.

Threat model

The adversary controls an arbitrary number of replicas in a decentralized asynchronous network and can inject, modify, reorder, delay, or drop messages, including generating malformed or conflicting delta blocks (equivocation). The adversary cannot break cryptographic primitives like collision-resistant hashing or forge digital signatures when authentication is enabled. Correct replicas form a connected component guaranteeing eventual delivery of correct updates. The adversary has no ability to coordinate global consensus or circumvent deterministic validation and applicability checks.

Methodology — deep read

The core threat model assumes a decentralized asynchronous system with unreliable networks and Byzantine adversaries controlling arbitrary nodes. Such adversaries may inject arbitrary delta blocks, reorder, drop, or delay messages, equivocate by sending conflicting updates to different peers, or produce malformed data. They cannot break cryptographic assumptions such as collision-resistant hashes or unforgeable signatures (when authentication is enabled).

Melda uses a delta-state CRDT design operating on immutable JSON object versions identified by cryptographic hashes and organized into revision trees. Updates are propagated as immutable delta blocks referencing prior deltas (anchors), each assigned a monotonically increasing index enforcing causal partial order and acyclicity. This causal structure underpins deterministic validation and applicability decisions.

Upon receipt, replicas perform deterministic validation: checking well-formed structure, hash integrity, availability of anchors and data packs, monotonic index, and optionally authentication signatures and authorization policies. Only validated updates are accepted. Applicability depends on whether all anchors have been applied, ensuring causal consistency.

State reconstruction recursively resolves references from the root JSON object through winning revisions deterministically chosen based on revision trees and merges. Concurrent updates are handled by selecting or merging revisions deterministically. Replicas deterministically ignore delta blocks that are not causally reachable from the root.

Melda supports adapters that modularly interface with storage and transport layers, enabling pluggable encryption, signing, compression, and policy enforcement without impacting core semantics. The security extension adds deterministic signature verification and policy filters, refining validity but allowing propagation of all updates to preserve availability.

The evaluation is primarily formal and theoretical, with proofs showing that any two correct replicas that observe the same set of delta blocks reconstruct the same state despite Byzantine faults. Key lemmas prove deterministic validation (4.1), applicability (4.2), acyclicity (4.3), and deterministic reconstruction (4.4). The system tolerates equivocation, omission, and arbitrary injection, where divergent Byzantine values either become consistently ignored or consistently incorporated leading to identical states.

An end-to-end example is described where conflicting array updates are merged deterministically by elevating arrays to first-class objects with independent versioning histories. This elides lost concurrent updates that would occur in simpler last-writer-wins schemes.

While no large-scale empirical tests are presented, Melda's implementation is open source. The approach focuses on proof-of-concept formal guarantees instead of performance benchmarks or adversarial attack simulation. The design supports composability with external dissemination or consensus protocols to achieve Byzantine-resilient replication at scale.

Technical innovations

• Introduction of deterministic state reconstruction in CRDTs where convergence is guaranteed by deterministic interpretation rather than rejecting updates.
• A non-intrusive delta-state JSON CRDT (Melda) that operates on existing application data models without requiring data model changes.
• A causal delta block structure with monotonic indexing enforcing acyclicity and enabling deterministic validation and applicability.
• Decoupling of update dissemination from state derivation, allowing Byzantine tolerance without requiring global agreement on update validity.
• Composable pluggable security adapter layer for authentication, authorization, and encryption integrated without affecting convergence guarantees.

Baselines vs proposed

• Traditional validation-based CRDT (Kleppmann [9]): relies on update acceptance/rejection to ensure convergence under Byzantine faults vs Melda: deterministic reconstruction achieves convergence without rejecting updates.
• Equivocation-tolerant CRDTs (Jacob et al.): accept equivocated updates as concurrent vs Melda: includes equivocation but uses deterministic projection to avoid divergence.
• Blocklace (Blocklace [1]): detects and bounds faults via signature and exclusion vs Melda: no fault exclusion but deterministic interpretation ensures consistency.

Limitations

• No empirical performance evaluation or benchmarks; impact of Byzantine flooding on storage and throughput not measured.
• Security guarantees depend on trust configuration consistency; differing policies may yield different views of state among replicas.
• Does not prevent Byzantine nodes from injecting unbounded numbers of irrelevant or malicious updates, potentially reducing efficiency.
• No explicit adversarial resilience tests against active attacks such as targeted equivocation, replay, or denial-of-service.
• Focuses on deterministic convergence guarantees rather than system recovery or fault remediation mechanisms.

Open questions / follow-ons

• How does Melda perform under large-scale Byzantine flooding attacks impacting resource consumption?
• How to integrate Melda's deterministic reconstruction with external consensus for global agreement on update sets?
• How effective are different policy configurations in balancing security and availability in practical deployments?
• What are the latency and bandwidth tradeoffs in Melda's opportunistic synchronization under intermittent connectivity?

Why it matters for bot defense

For bot-defense and CAPTCHA applications leveraging distributed or replicated data stores, Melda provides a formal framework to tolerate Byzantine nodes that may inject arbitrary or malformed updates. Its deterministic reconstruction guarantees that client-facing replicas will converge to a consistent state despite adversarial tampering with update streams, aiding integrity of replicated data without requiring expensive coordination or rejection-based filtering. The model allows security layers such as authentication and authorization to be applied modularly, enabling role-based access control without breaking convergence guarantees.

Bot-defense engineers facing adversarial network conditions or potentially malicious participants can appreciate that this approach decouples agreement on update validity from state consistency. Instead of costly synchronous validation or global consensus, the system tolerates arbitrary injected and equivocated updates by ensuring consistent interpretation. While no direct CAPTCHA interaction is presented, Melda's concepts could inspire robust decentralized data synchronization and state integrity designs for challenges relying on distributed verification or consensus across untrusted peers.

Cite

@article{arxiv2606_18966,
  title={ A Composable CRDT Layer for Byzantine-Resilient Deterministic Reconstruction },
  author={ Amos Brocco },
  journal={arXiv preprint arXiv:2606.18966},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.18966}
}

Read the full paper

• arXiv:2606.18966 (abstract)
• arXiv:2606.18966 (PDF)