REVIEW 5 minor 9 references
Memory-Exhaustion Attack on the Blocklace Byzantine-Repelling Conflict-Free Replicated Data Type
T0 review · 0 major / 5 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read The blocklace Byzantine-repelling CRDT can be forced to replicate an arbitrarily large number of useless updates—up to the size of the identifier space—by attackers that mint fresh self-incriminating identities, so practical deployments nee
desk verdict A short, sound attack paper that exposes a real gap in the blocklace's memory-bounding claim; the logic is simple and correct given the quoted acceptance rule, with the author honestly noting the need for extra identity restrictions in practice. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the Byzantine Repellance Acceptance Invariant (Definition 3.1), the rule that defines which updates a correct blocklace node will replicate: a new update and its causal history can be merged locally iff either it reveals a previously unknown node behaving byzantine, or it comes from an apparently correct node and supplies evidence of all locally known byzantine nodes. This invariant is what is supposed to make the blocklace byzantine-repelling, but it is also the attack's entry point. Because disjunct (1) holds for any update that exposes a new misbehaving node, and because the attacker controls the identity, the invariant treats self-incrimination as valid incrimi
What would settle it
Run a correct blocklace node under the original acceptance invariant with no additional identity restrictions, let an adversary mint fresh identities and submit one self-incriminating update per identity, and observe whether the node's stored update count grows without bound. If the node stops storing these updates short of exhausting memory, the attack as described fails.
Extended reading notes
Core claim
The discovery is an attack on the Byzantine Repellance Acceptance Invariant (Definition 3.1), the replication gate of the blocklace. That invariant admits a new update and its causal history if either (1) the update reveals a new byzantine node, or (2) it is signed by a node not yet known to be byzantine and its history contains evidence against every byzantine node locally known. The attack exploits disjunct (1): an attacker generates a new identity and has that identity incriminate itself by producing an invalid or equivocating update; because disjunct (1) does not check the author, a correct node accepts and stores it. By repeating with new identities—possibly in parallel, and possibly at
Load-bearing premise
The attack's load-bearing premise is that attackers can create new identities cheaply and unlimitedly, and that correct nodes will accept and store any update that incriminates a previously unknown node.
Editorial extensions
If this is right
- A correct node using the original replication rule can have all of its local storage consumed by attacker-generated self-incriminating updates, blocking updates from correct participants.
- The blocklace's 'finite harm' guarantee is quantified by the number of identities accepted by a correct node, not by the number of updates a byzantine participant can create; in a permissionless identifier space this bound is practically useless.
- The attack is not limited to invalid updates: because evidence only needs to be transitively reachable, an attacker can also smuggle arbitrary data or large files into a correct node's store.
- If disjunct (1) were removed from the invariant, the attack still goes through as long as colluders propagate the self-incriminating evidence through their own valid updates.
- Practical deployments of a blocklace must add a mechanism that restricts which identifiers are worth replicating from, such as interest-driven or reputation-based admission, or the system is vulnerable to memory exhaustion.
Reading between the lines
- I would expect the same vulnerability to appear in any replication rule that eagerly stores all evidence of misbehavior from arbitrary identities; the general design lesson is that evidence collection needs a cost or trust anchor in addition to authenticity.
- A quantitative version of this attack would model the trade-off between identifier issuance cost and per-update storage cost; if identities are cheaper than the memory an update can force, exhaustion is inevitable, and the break-even point gives a concrete deployment constraint.
- A testable extension would modify the acceptance invariant to require that incriminating evidence be signed by a node already trusted (or previously correct), rather than by the self-incriminating identity itself, and check whether the byzantine-repellence property is preserved.
- Combining the attack with a proof-of-work requirement would slow memory growth but, as the paper notes, would not bound total consumption over an unbounded identifier space; an externally enforced identity scarcity seems necessary.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper analyzes the Byzantine-repellance criterion of the blocklace CRDT [1], which is intended to bound the number of updates that correct nodes replicate. It observes that the acceptance invariant (Def. 3.1) permits merging any update whose causal history reveals a new Byzantine node (disjunct (1)). An attacker can mint fresh identities, have each identity self-incriminate by producing an invalid or equivocating update, and deliver these updates to correct nodes; each such update is accepted and consumes memory. Repeating the process exhausts the storage of correct nodes, up to the size of the identifier space. The paper argues that this is a Sybil-like attack, that it does not invalidate the original 'Finite Harm' theorem (which is per-node), and that practical deployments need additional identity restrictions such as interest-driven replication. The paper is essentially an attack note with an informal argument and a high-level mitigation.
Significance. If the quoted acceptance invariant is the complete replication rule of the original blocklace, the attack is correct. The reasoning is simple and transparent: disjunct (1) only requires a strict increase in the set of known Byzantine nodes, and a self-incriminating update from a fresh identity satisfies this condition. The paper's strength is that it derives the attack from the protocol's own definition, not from external assumptions, and it explicitly acknowledges the practical caveat that identity restrictions would mitigate the problem. The paper does not overclaim: it preserves the original Finite Harm theorem and identifies the limitation as the unbounded identifier space. The contribution is modest but useful for anyone deploying or building on the blocklace. The manuscript would benefit from a formal statement of the memory-growth argument and an exact quotation of the original invariant, but these are local improvements rather than substantive flaws.
minor comments (5)
- [Section 3, Def. 3.1] The attack rests entirely on the quoted acceptance invariant. To make the paper fully verifiable, please provide a direct quotation or precise equation/page reference from [1] rather than a paraphrase. This is not a substantive doubt, but it would remove the only external dependency of the argument.
- [Abstract and Section 1] Minor editorial issues: 'successfully achieve' should be 'successfully achieves'; the spelling of 'repellance'/'repellant' is inconsistent; 'inside,just' is missing a space. These should be corrected.
- [Section 4] The central claim is stated informally. Please state it as a precise lemma, e.g., with an identifier space of size N, a correct node can be forced to replicate at least N attacker-generated updates, each of size at least one block. This would make the 'arbitrarily large' claim rigorous.
- [Section 5] The sentence 'The main result still holds' followed by 'only once an attacker stops using new identifiers' is slightly misleading. Clarify that Finite Harm is per-identity and therefore does not contradict the attack; the current wording may confuse readers.
- [Acknowledgments] The phrase 'allowing us to claim sole authorship' is unusual and reads as a self-referential joke. It is out of place in a formal paper and should be removed or rewritten.
Circularity Check
No significant circularity: the attack is a direct application of the quoted acceptance invariant, not an assumption of its conclusion, and the only self-citations are in related work/mitigation.
full rationale
The paper's central claim is that the blocklace acceptance invariant (Def. 3.1) allows unbounded memory consumption because disjunct (1) admits any update that reveals a new byzantine identity, and an attacker can mint new self-incriminating identities. This is not circular: the acceptance invariant is quoted from the analyzed protocol [1] as the object of study, and the attack constructs a scenario that satisfies its conditions. The paper does not fit parameters, rename the conclusion into the premise, or invoke a uniqueness theorem. Its self-citations ([6], [8]) appear only in related work and mitigation context and are not load-bearing for the attack. The paper explicitly acknowledges the need for out-of-band identifier restrictions (Section 6), which is a practical caveat rather than a circularity. The derivation chain is self-contained: by Def. 3.1, byz(B' \ {b}) ⊂ byz(B') when a fresh identity incriminates itself, so the update is accepted; repeating with fresh identities exhausts memory. This is a valid attack analysis, not a case of the conclusion being assumed.
Assumptions & free parameters
assumptions (4)
- domain assumption Byzantine Repellance Acceptance Invariant (Definition 3.1): an update is accepted iff it incriminates a new byzantine node, or it is from a correct node and includes evidence against all locally known byzantine nodes.
- domain assumption Attackers can generate arbitrarily many new valid identifiers and sign updates with them (Sybil assumption).
- domain assumption Correct nodes will accept and permanently store every update that satisfies the Acceptance Invariant, regardless of the source's reputation or prior interaction.
- domain assumption The attacker can deliver updates to correct nodes over the network.
Cite this review
Pith. "Pith review of Memory-Exhaustion Attack on the Blocklace Byzantine-Repelling Conflict-Free Replicated Data Type." pith.science (2026). https://pith.science/paper/L3XN72YT
@misc{pith2026260715185,
author = {Pith},
title = {Pith review of: Memory-Exhaustion Attack on the Blocklace Byzantine-Repelling Conflict-Free Replicated Data Type},
year = {2026},
howpublished = {\url{https://pith.science/paper/L3XN72YT}},
note = {Machine review of arXiv:2607.15185}
}
read the original abstract
The blocklace is a directed acyclic graph encoding the causal relationship between authenticated updates produced by participating nodes. Compared to previous approaches, it adds restrictions on what can be replicated: a new update and its causal history is replicated locally if and only if either 1) it reveals a new node behaving arbitrarily (byzantine), or 2) it was signed by a node that still appears to be correct and the new updates provide evidence incriminating at least the set of nodes locally known to have behaved arbitrarily. The restrictions purport to limit the replication of arbitrary updates, even in the presence of colluders that never produce incriminating evidence, so that only a finite number will eventually be replicated by correct nodes. While the original description of the replication behaviour successfully achieve this aim, we show that this finite number can be made arbitrarily large, up to the size of the identifier space used to authenticate messages. This effectively enables malicious nodes to overwhelm correct nodes with arbitrary and useless updates. Practical deployments therefore require additional restrictions on the set of identifiers that will be accepted by correct nodes.
Reference graph
Works this paper leans on
-
[1]
Paulo Sérgio Almeida and Ehud Shapiro. 2025. The Blocklace: A Byzantine-repelling and Universal Conflict-free Replicated Data Type (v4). arXiv:2402.08068v4 [cs.DC]
arXiv 2025
-
[2]
Carlos Baquero, Francisco Maia, Abel Dantas, Antonio Fernández Anta, Davide Frey, César Sánchez, and Timothé Albouy. 2026. Bounding Byzantine Impact in Open CRDT Systems. InProceedings of the 13th International Workshop on Principles and Practice of Consistency for Distributed Data (PaPoC ’26). ACM, New York, NY, USA, 17–24. doi:10.1145/3806077.3806698
arXiv 2026
-
[3]
John R. Douceur. 2002. The Sybil Attack. InPeer-to-Peer Systems, Peter Druschel, Frans Kaashoek, and Antony Rowstron (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 251–260
2002
-
[4]
Florian Jacob, Luca Becker, Jan Grashöfer, and Hannes Hartenstein. 2020. Matrix Decomposition: Analysis of an Access Control Approach on Transaction-based DAGs without Finality. InProceedings of the 25th ACM Symposium on Access Control Models and Technologies(Barcelona, Spain)(SACMAT ’20). ACM, New York, NY, USA, 81–92. doi:10.1145/3381991.3395399
arXiv 2020
-
[5]
Florian Jacob and Hannes Hartenstein. 2024. Logical Clocks and Monotonicity for Byzantine-Tolerant Replicated Data Types. InProceedings of the 11th Workshop on Principles and Practice of Consistency for Distributed Data(Athens, Greece)(PaPoC ’24). ACM, New York, NY, USA, 37–43. doi:10.1145/3642976.3653034
arXiv 2024
-
[6]
Anne-Marie Kermarrec, Erick Lavoie, and Christian Tschudin. 2021. Gossiping with Append-Only Logs in Secure-Scuttlebutt. InProceedings of the 1st Interna- tional Workshop on Distributed Infrastructure for Common Good(Delft, Nether- lands)(DICG’20). ACM, New York, NY, USA, 19–24. doi:10.1145/3428662.3428794
arXiv 2021
-
[7]
Martin Kleppmann and Heidi Howard. 2020. Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases. arXiv:2012.00472 [cs.DC]
arXiv 2020
-
[8]
Erick Lavoie. 2023. 2P-BFT-Log: 2-Phase Single-Author Append-Only Log for Adversarial Environments. arXiv:2307.08381 [cs.DC]
arXiv 2023
Show all 9 references
-
[9]
Hector Sanjuan, Samuli Poyhtari, Pedro Teixeira, and Ioannis Psaras. 2020. Merkle- CRDTs: Merkle-DAGs meet CRDTs. arXiv:2004.00107 [cs.NI]
2020 arXiv
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.