Blocklace BR-CRDT vulnerable to memory-exhaustion attack
Attack forces correct nodes to replicate useless updates until memory is exhausted.
The Blocklace is a directed acyclic graph (DAG) that encodes causal relationships between authenticated updates from participating nodes. Its Byzantine-repelling variant adds restrictions on what can be replicated: a new update is accepted only if it reveals a new Byzantine node or if it provides incriminating evidence against known misbehaving nodes. This was meant to ensure that only a finite number of arbitrary updates are ever replicated by correct nodes, even in the presence of colluding attackers.
Erick Lavoie's analysis demonstrates a critical flaw: while the number of accepted updates remains finite, that limit can be pushed arbitrarily large—up to the size of the identifier space used to authenticate messages. This effectively enables malicious nodes to exhaust memory on all correct nodes by flooding them with seemingly legitimate but useless updates. The attack undermines the core security guarantee of the Blocklace BR-CRDT, forcing developers to impose extra restrictions on accepted identifiers in real-world deployments.
- The attack exploits the fact that the finite number of accepted updates can be enlarged up to the entire identifier space.
- Correct nodes are forced to replicate useless updates, leading to memory exhaustion.
- Practical systems must add additional restrictions on accepted identifiers to prevent this attack.
Why It Matters
Exposes a fundamental flaw in Byzantine-resistant CRDTs, demanding stricter identifier controls for production use.