DSpace 7
Digital Library for School of Computing, National University of Singapore.
- For NUS staff and students, please use Chrome browser only and select "Log in with OIDC" under "Log in".
- Please email technical problems to combx100@nus.edu.sg.
Communities in DSpace
Select a community to browse its collections.
Recent Submissions
Item
LYRATA: Proof-of-Useful-Bandwidth Blockchain Against Persistent Adversaries
(2026-11-05) Ruomu Hou; Yucheng Sun; Haifeng Yu
Permissionless blockchains are subject to sybil attacks. They typically rely on Proof-of-X (such as Proof-of-Work), for sybil defense. Here "X" is a resource which the adversary only has limited supply. While effective, such Proof-of-X systems often result in significant resource waste. To avoid such waste, thiswork explores sybil defense based on in-protocol bandwidth consumption. Here in-protocol bandwidth consumption refers to bandwidth that is already consumed by the blockchain for providing the basic functionality of a distributed ledger.
As our main contribution, this work proposes a novel blockchain LYRATA, with a simple yet elegant design. To our knowledge, LYRATA is the very first blockchain that can i) minimize resource waste by exploiting in-protocol bandwidth consumption, and ii) offer strong security guarantees under standard persistent adversaries. We have further implemented a research prototype of LYRATA. Our experimental results show that LYRATA also offers good practical end-to-end performance.
Item
Heavy-coin Committee Selection for the Decentralized Era
(2026-08-20) Yucheng Sun; Haifeng Yu
Committee selection is a fundamental building block for enabling blockchains to scale. Most blockchains use the canonical design for committee selection, where committee members are chosen uniformly randomly, weighted by the stake of each node. Several recent breakthrough works [24, 45] interestingly show that the canonical design is not the only way to go. These works show that by deterministically including certain nodes in the committee, we can significantly reduce the committee size needed.
These recent designs [24, 45] however are meaningful only under highly-centralized stake distributions. If the stake distribution is more decentralized (i.e., with less wealth concentration), then they quickly degrade to the canonical design. As the central contribution of this work, we propose a novel heavy-coin committee selection scheme or HC scheme. For more decentralized distributions, our HC scheme is the first and only design that can do better than the classic canonical design. For other (highly-centralized) distributions, our HC scheme retains the benefits of the best existing design.
Item
Committee Selection with Non-Proportional Weights
(2025-08-01) Yucheng, Sun; Haifeng, Yu; Ruomu, Hou
Committees are extensively used in the designs of various Proof-of-Stake (PoS) blockchains. A committee is simply a randomly selected subset of the parties/nodes in the system. Ideally, the committee should i) be as small as possible, and ii) properly represent the entire system, in terms of the corruption ratio. Existing committee selection schemes all follow the principle of proportionality, which says that a committee member should neither over-represent nor under-represent the stake it holds.
In this work, highly surprisingly, we discover that proportionality actually leads to sub-optimal designs. Namely, better security and smaller committee size can be achieved when parties overrepresent/under-represent their stakes. We then explore such nonproportional designs, and show that they can help to reduce error by many orders of magnitude, under realistic settings and real-world stake distributions of 6 major cryptocurrencies.
Item
Robust and Low-degree Overlay for Secure Flooding Against Resource-bounded Adversaries
(2024-09-17) Yucheng Sun; Ruomu Hou; Haifeng Yu
The security of large-scale blockchains relies on successful message flooding among the honest parties, on an overlay topology. The crux of doing such flooding successfully is to have a robust and low-degree overlay topology: Robust means that even if the malicious parties all refuse to relay messages, the remaining honest parties should still constitute a connected component in the overlay network. Low-degree means that the nodes in the overlay network should have relatively small node degrees. The central challenge of designing such robust and low-degree topology is that in permissionless blockchain context, the adversary is often bounded by resource (such as computation power or stake), rather than by the total number of malicious parties. We show that existing works of designing robust overlay against such resource-bounded adversaries all require excessively large node degrees (e.g., 25000 or more under real-world settings). As our main contribution, we propose a novel LOR overlay topology that is robust against such resource- bounded adversaries. Our design is the very first such design with practically-feasible node degrees (e.g., 200 to 400 under real-world settings
Item
Using Multi-dimensional Quorums for Optimal Resilience in Multi-resource Blockchains
(2023-09-01) Yucheng Sun; Ruomu Hao; Haifeng Yu
Permissionless blockchains commonly use resource challenges to defend against sybil attacks. For example, popular resource challenge designs include Proof-of-Work and Proof-of-Stake. It is well-known that simultaneously exploiting multiple resources can help make a permissionless blockchain more robust. Existing efforts along this direction, however, all fail to provide a complete answer to the central question of how to combine PoW and PoS, or multiple resources in general, to achieve optimal resilience. As our central contribution, this work gives complete answers to this central question.