Nodes (i.e., computers) in a distributed system communicate with each other, either directly or indirectly through intermediate nodes. Such a structure corresponds to an overlay topology, which can be viewed as a graph.
For security, distributed systems (e.g., blockchains) typically need the topology to be robust. Being robust means that nodes can successfully propagate messages to others (directly or indirectly), even if malicious nodes refuse to help relay messages. In other words, we want the subgraph corresponding to the part of the topology that contains all the honest nodes to be a connected component.
This basic problem, interestingly, becomes rather tricky in certain contexts. For example, in Proof-of-Stake (PoS) blockchain, different nodes have different amounts of stake (i.e., the cryptocurrencies a node has). The attacker can easily create a huge number of nodes, each with a rather small amount of stake, at low cost. Consequently, most of the nodes in the topology can be malicious, and the fraction of malicious nodes in the topology may even approach 1.0. (Note that one cannot simply treat nodes whose stake is below a certain threshold t as malicious. The reason is that the adversary is adaptive, and can then create malicious nodes with 1.1t stake.) This makes it rather challenging to design a robust topology, and there have been no practical solutions for the problem.
Our work uses a simple yet elegant idea to overcome this key challenge, by using bounded-disparity group. The basic intuition is that the above challenge is caused by nodes having different amount of stake, or conceptually, by the disparity among the nodes. If nodes all have similar amount of stake, then the problem is much easier to solve. Hence we first partition the nodes into groups, so that nodes in the same group all have similar stake (e.g., within a factor of 2 of each other). We can such a group as bounded-disparity group, in the sense that the disparity among the nodes in the group is properly bounded.
Next we design proper intra-group topology to make the nodes within a group connected, and proper inter-group topology to connect all the groups. The intra-group topology design is made possible by the bounded-disparity of the group. Specifically, a key technical challenge we need to overcome is that the attacker may focus on a given group, and can corrupt most of the nodes in that group. This will cause the topology (among the honest nodes) in that group to become disconnected. The bounded-disparity nature of the group addresses this challenge: Since the disparity is bounded, if the attacker indeed corrupts most of the nodes in that group, then it necessarily corrupts most of the stake in that group. This means that the remaining honest stake in the group is rather small. One can then use other techniques to deal with that small amount of honest stake.
Our results show that our design gives practical and robust topologies under real-world stake distributions of various popular cryptocurrencies such as Ethereum, Solana, Cardano, Dogecoin, Bitcoin, and Bitcoin-Cash.
Find out more about this work in: