Candidate:
Chunyu
Mao
Title: Scaling
Permissioned
Blockchains
via
Sharding
Date: October
13,
2022
Time:
11:00
am
Place:
REMOTE
ATTENDANCE
Supervisor(s): Golab,
Wojciech
Abstract:
Traditional distributed systems, such as those used in banking and real estate, require a trusted third party to operate and maintain them, which is highly dependent on the reliability of the operator. Since Bitcoin was introduced by Nakamoto in 2008, blockchain technology has been considered as a promising solution to the trust issue raised by the traditional centralized approach. Blockchain is now used by most cryptocurrencies and has meaningful applications in other areas, such as logistics and supply chain management. However, scalability remains a major limitation. Various techniques are being investigated to tackle the scalability issue. Sharding is an intuitive approach to improve the scalability of blockchain systems. This thesis explores sharding techniques in permissioned blockchains.
First of all, two techniques are examined for interleaving the shards of permissioned blockchains, which are referred to as strong temporal coupling and weak temporal coupling. The analysis and experiment results show that strong coupling loses performance when different shards grow unevenly, but outperforms weak coupling in a wide-area environment due to its inherent efficiency. Weak coupling, in contrast, deals naturally with load imbalance across shards and in fact tolerates shard failures without any additional effort, but loses performance when running on a high-latency network due to the additional coordination performed.
Second, we propose Antipaxos, a leaderless consensus protocol that reaches agreement on multiple proposals with a fast path solution in the failure-free case, and falls back on a slow path to handle other cases. A new agreement problem, termed as k-Interactive Consistency is formalized first. Then, two algorithms to solve this problem are proposed under the crash failure model and Byzantine failure model, respectively. We prove the safety and liveness of the proposed algorithms, and present an experimental evaluation of their performance in the Amazon cloud. Both the crash-tolerant and Byzantine-tolerant designs reach agreement on n batches of proposals with (n2) messages. This leads to the linear complexity of each batch in one consensus cycle, rather than a single batch of proposals per cycle in conventional solutions. The experiments show that our algorithms achieve not only lower execution latency but also higher peak throughput in the failure-free case when deployed in a geo-distributed environment.
Lastly, we introduce a full sharding protocol, Geochain, for permissioned blockchains. The transaction latency is minimized by clustering participants using their geographical properties--locality. In addition, the locality is also being used to decide the transaction placement which suggests a low ratio of cross-shard transactions for applications, such as everyday banking, retail payments, and electric vehicle charging. We also propose a client-driven efficient mechanism to handle cross-shard transactions and present an analysis. This enables clients to manage their assets across different shards directly. A prototype is implemented on top of Hyperleder Fabric v2.3 and evaluated on Amazon EC2. The experiments show that our protocol doubles the peak throughput even with a high ratio of cross-shard transactions while minimizing the transaction latency.