DSpace 7
Digital Library for School of Computing, National University of Singapore.
- For SoC staff, please login with NUSNET email (xyz@nus.edu.sg) and password.
- For SoC student, please login with NUSNET email (xyz@u.nus.edu) and password.
- Please email technical problems to diglib@comp.nus.edu.sg.
Communities in DSpace
Select a community to browse its collections.
Recent Submissions
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.
Item
Optimistic Fast Confirmation While Tolerating Malicious Majority in Blockchains
(2023-04-06) Hou, Ruomu; Yu, Haifeng
The robustness of a blockchain against the adversary is often characterized by the maximum fraction (fmax) of adversarial power that it can tolerate. While most existing blockchains can only tolerate fmax < 0.5 or lower, there are some blockchain systems that are able to tolerate a malicious majority, namely fmax >= 0.5. A key price paid by such blockchains, however, is their large confirmation latency. This work aims to significantly reduce the confirmation latency in such blockchains, under the common case where the actual fraction f of adversarial power is relatively small. To this end, we propose a novel blockchain called FLINT. FLINT tolerates fmax >= 0.5 and can give optimistic execution (i.e., fast confirmation) whenever f is relatively small. Our experiments show that the fast confirmation in FLINT only takes a few minutes, as compared to several hours of confirmation latency in prior works.
Item
Achieving Sublinear Complexity under Constant 𝑇 in 𝑇 -interval Dynamic Networks
(2022-05-26) Hou, Ruomu; Jahja, Irvan; Sun, Yucheng; Wu, Jiyan; Yu, Haifeng
This paper considers standard {\em $T$-interval dynamic networks}, where the $N$ nodes in the network proceed in lock-step {\em rounds}, and where the topology of the network can change arbitrarily from round to round, as determined by an {\em adversary}. The adversary promises that in every $T$ consecutive rounds, the $T$ (potentially different) topologies in those $T$ rounds contain a common connected subgraph that spans all nodes.
Within such a context, we propose novel algorithms for solving some fundamental distributed computing problems such as Count/Consensus/Max.
Our algorithms are the first algorithms whose complexities do not contain an $\Omega(N)$ term, under constant $T$ values. Previous sublinear algorithms require significantly larger $T$ values.
Item
Survey on Data Quality and Provenance
(2021-11) Schmitz, Martin
This technical report summarizes research on data quality, provenance and truth discovery from the last decades. It examines opportunities to use machine learning methods to enhance data quality and provenance. This report can serve as a starting point to nd the key publications of the topics "provenance" and "data quality" and to do further research in those areas in general as well as in combination with machine learning algorithms.