BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Ling Ren

Ling Ren contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Cryptography and SecurityDistributed, Parallel, and Cluster Computing

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2022arXiv

Bitcoin's Latency--Security Analysis Made Simple

Simple closed-form upper and lower bounds are developed for the security of the Nakamoto consensus as a function of the confirmation depth, the honest and adversarial block mining rates, and an upper bound on the block propagation delay. The bounds are exponential in the confirmation depth and apply regardless of the adversary's attack strategy. The gap between the upper and lower bounds is small for Bitcoin's parameters. For example, assuming an average block interval of 10 minutes, a network delay bound of ten seconds, and 10% adversarial mining power, the widely used 6-block confirmation rule yields a safety violation between 0.11% and 0.35% probability.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Brief Note: Fast Authenticated Byzantine Consensus

Byzantine fault-tolerant (BFT) state machine replication (SMR) has been studied for over 30 years. Recently it has received more attention due to its application in permissioned blockchain systems. A sequence of research efforts focuses on improving the commit latency of the SMR protocol in the common good case, including PBFT with $3$-round latency and $n\geq 3f+1$ and FaB with $2$-round latency and $n\geq 5f+1$. In this paper, we propose an authenticated protocol that solves $2$-round BFT SMR with only $n\geq 5f-1$ replicas, which refutes the optimal resiliency claim made in FaB for needing $n \geq 5f+1$ for $2$-round PBFT-style BFT protocols. For the special case when $f=1$, our protocol needs only $4$ replicas, and strictly improves PBFT by reducing the latency by one round (even when one backup is faulty).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Good-case Latency of Byzantine Broadcast: A Complete Categorization

This paper explores the problem good-case latency of Byzantine fault-tolerant broadcast, motivated by the real-world latency and performance of practical state machine replication protocols. The good-case latency measures the time it takes for all non-faulty parties to commit when the designated broadcaster is non-faulty. We provide a complete characterization of tight bounds on good-case latency, in the authenticated setting under synchrony, partial synchrony and asynchrony. Some of our new results may be surprising, e.g., 2-round PBFT-style partially synchronous Byzantine broadcast is possible if and only if $n\geq 5f-1$, and a tight bound for good-case latency under $n/3<f<n/2$ under synchrony is not an integer multiple of the delay bound.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Efficient Cross-Shard Transaction Execution in Sharded Blockchains

Sharding is a promising blockchain scaling solution. But it currently suffers from high latency and low throughput when it comes to cross-shard transactions, i.e., transactions that require coordination from multiple shards. The root cause of these limitations arise from the use of the classic two-phase commit protocol, which involves locking assets for extended periods of time. This paper presents Rivet, a new paradigm for blockchain sharding that achieves lower latency and higher throughput for cross-shard transactions. Rivet has a single reference shard running consensus, and multiple worker shards maintaining disjoint states and processing a subset of transactions in the system. Rivet obviates the need for consensus within each worker shard, and as a result, tolerates more failures within a shard and lowers communication overhead. We prove the correctness and security of Rivet. We also propose a more realistic framework for evaluating sharded blockchains by creating a benchmark based on real Ethereum transactions. An evaluation of our prototype implementation of Rivet and the baseline two-phase commit, atop 50+ AWS EC2 instances, using our evaluation framework demonstrates the latency and throughput improvements for cross-shard transactions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Optimal Communication Complexity of Authenticated Byzantine Agreement

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with $f < n/3$ by Berman et al. but a considerable gap remains for the authenticated setting with $n/3 \le f < n/2$. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Strengthened Fault Tolerance in Byzantine Fault Tolerant Replication

Byzantine fault tolerant (BFT) state machine replication (SMR) is an important building block for constructing permissioned blockchain systems. In contrast to Nakamoto Consensus where any block obtains higher assurance as buried deeper in the blockchain, in BFT SMR, any committed block is secure has a fixed resilience threshold. In this paper, we investigate strengthened fault tolerance (SFT) in BFT SMR under partial synchrony, which provides gradually increased resilience guarantees (like Nakamoto Consensus) during an optimistic period when the network is synchronous and the number of Byzantine faults is small. Moreover, the committed blocks can tolerate more than one-third (up to two-thirds) corruptions even after the optimistic period. Compared to the prior best solution Flexible BFT which requires quadratic message complexity, our solution maintains the linear message complexity of state-of-the-art BFT SMR protocols and requires only marginal bookkeeping overhead. We implement our solution over the open-source Diem project, and give experimental results that demonstrate its efficiency under real-world scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Communication Complexity of Byzantine Agreement, Revisited

As Byzantine Agreement (BA) protocols find application in large-scale decentralized cryptocurrencies, an increasingly important problem is to design BA protocols with improved communication complexity. A few existing works have shown how to achieve subquadratic BA under an {\it adaptive} adversary. Intriguingly, they all make a common relaxation about the adaptivity of the attacker, that is, if an honest node sends a message and then gets corrupted in some round, the adversary {\it cannot erase the message that was already sent} --- henceforth we say that such an adversary cannot perform &#34;after-the-fact removal&#34;. By contrast, many (super-)quadratic BA protocols in the literature can tolerate after-the-fact removal. In this paper, we first prove that disallowing after-the-fact removal is necessary for achieving subquadratic-communication BA. Next, we show new subquadratic binary BA constructions (of course, assuming no after-the-fact removal) that achieves near-optimal resilience and expected constant rounds under standard cryptographic assumptions and a public-key infrastructure (PKI) in both synchronous and partially synchronous settings. In comparison, all known subquadratic protocols make additional strong assumptions such as random oracles or the ability of honest nodes to erase secrets from memory, and even with these strong assumptions, no prior work can achieve the above properties. Lastly, we show that some setup assumption is necessary for achieving subquadratic multicast-based BA.

0 citations0 reviewsNo code linkedOpen access