I am a researcher at Acompany, a privacy-tech startup based in Japan. Prior to joining Acompany, I was a visiting research scholar and PhD student in Computer Science at University of Illinois Urbana-Champaign.
I am honored to have received the Tsujii Shigeo Security Paper Award 2022 and the Illinois Distinguished Fellowship. I serve as a program committee member of ACM CCS 2024.
I am generally interested in distributed computing and cryptography. One of the main topics is distributed consensus, an underlying technology of Bitcoin, and what people call blockchain. Consensus is a decade-old problem, and Bitcoin is often considered just another solution to the classical consensus problem. However, Bitcoin’s consensus mechanism takes a completely different approach from classic solutions and comes with several unique features, such as dynamic participation support, higher fault tolerance under asynchronous clocks, and efficient communication using sparse gossip networks. My interest is exploring the intersection of Bitcoin and classic solutions aiming at achieving the best of both worlds. Here are some of my recent works.
Sleepy BFT. One of the most interesting features that makes the Bitcoin protocol unique is its support for dynamic and unknown participation, where nodes can spontaneously join/leave the network at will without prior notice. Traditional protocols do not work in this dynamic setting, as they require votes from a fixed quorum of nodes to make progress. To adapt the classic quorum-based approach to the dynamic setting, we have introduced a new technique we call time-shifted quorum. Time-shifted quorum allows each node to dynamically define the quorum threshold based on the node’s perceived participation level while preserving important properties of classic static quorums. This achieves the best of both: constant latency of classical protocols and dynamic participation support of Bitcoin. Part of this work is published in ACM CCS 2022 and ACM CCS 2023.
Multi-threshold BFT. Consensus protocols in general assume a bound f on the number of corrupt nodes (i.e., those controlled by an attacker). Classic consensus protocols assume f < n/3, which is known to be the theoretical limit for tolerating occasional network failure. One strength of Bitcoin is its higher fault tolerance f < n/2, but it assumes a perfectly synchronous network. In other words, they are on the two extremes. Can we circumvent this trade-off and enjoy the best of both worlds? Our recent work shows, that with small modifications, classic protocols that tolerate n/3 corruption under asynchronous networks can still tolerate up to 2n/3 corruption when the network is synchronous. In other words, an attacker needs to control a very large fraction (2/3) of nodes or control 1/3 plus the entire network, to successfully mount the attack. This work is published in ACM CCS 2021.
Optimal communication BA/BB. Bitcoin is the first practical synchronous protocol, and it inspired several follow-up works that leverage synchronous communication for higher fault tolerance. All existing synchronous protocols share a common step: forwarding messages to all other nodes. This step helps detect conflicting views among nodes and prevents disagreement. However, it increases the overall communication by a factor of n compared to classical asynchronous protocols where nodes send their own belief only. To fill this gap, we introduce a new technique that utilizes an expander graph to forward messages efficiently yet being able to detect conflicting views among nodes. Remarkably, this technique also resolves a long-standing open question on the optimal communication complexity of Byzantine broadcast/agreement, namely the tightness of Dolev-Reischuk lower bound. We have also applied this technique to design a broadcast channel, a primitive often used in cryptography, with optimal communication. These works are published in DISC 2021 and ACM PODC 2023.
I am recently expanding my research interest to cryptography for distributed computing. Here is one recent work.
On the Security of KZG Commitment for VSS. with Sourav Das and Ling Ren @ACM CCS 2023
Towards Practical Sleepy BFT. with Dahlia Malkhi and Ling Ren @ACM CCS 2023
On the Amortized Communication Complexity of Byzantine Broadcast. with Ling Ren, Elaine Shi, Jun Wan, and Zhuolun Xiang. @ACM PODC 2023.
Constant Latency in Sleepy Consensus. with Ling Ren. @ACM CCS 2022.
Multi-Threshold Byzantine Fault Tolerance. with Ling Ren @ACM CCS 2021
Optimal Communication Complexity of Authenticated Byzantine Agreement. with Ling Ren @DISC 2021