Memory-Exhaustion Attack on the Blocklace Byzantine-Repelling Conflict-Free Replicated Data Type
Distributed, Parallel, and Cluster Computing
Summary
The authors study a system called 'blocklace' used to track updates in a network where some nodes might act badly. They show that while blocklace limits which updates get copied to stop bad behavior, it can still be overwhelmed by many useless updates if the bad nodes use many different identities. This means the originally proposed limits aren't enough to prevent flooding attacks. The authors suggest that real-world use of blocklace needs extra rules about which node identities are trusted to keep the system manageable.
Authors
Erick Lavoie
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.