Tse Lab

Science and Engineering of Consensus 2024

An affiliated workshop of The Science of Blockchain Conference 2024

Sponsored by:

IC3 a16z crypto Input Output Global Redbelly Texas A&M GCRI

Last two years’ workshops: https://tselab.stanford.edu/workshop-sbc23/, https://tselab.stanford.edu/workshop-sbc22/

Program

  • 9:30:   Registration and breakfast
  • 10:30:     Welcome
  • 10:40–11:30:     Session 1
    • 10:40:     Tim RoughgardenHow Secure Is Your Restaking Network?
    • 11:05:     Vincent GramoliStrengthening Blockchain Security with Accountability
    • 11:30:     David TseBitcoin Staking
  • 12:20–2:00:     Lunch break
  • 2:00–3:15:     Session 2
    • 2:00:     Peiyao ShengTechnical Framework for Unifying DePIN Coordination
    • 2:25:     Juan GarayCompleteness Theorems for Adaptively Secure Broadcast
    • 2:50:     Andrew MillerWhy TEE is Important for Modern Consensus
  • 3:15–3:45:     Coffee break
  • 3:45–5:00:     Session 3
    • 3:45:     Erica BlumAbraxas: A Black-Box Framework for Throughput-Efficient Hybrid Asynchronous Consensus
    • 4:10:     Sandro Coretti-DraytonHigh-Throughput Blockchain Consensus under Realistic Network Assumptions
    • 4:35:     Ling RenGranular Synchrony: A New Network Timing Model for Distributed Computing
  • 5:00:     Goodbye

Abstracts

Andrew Miller --- UIUC and Flashbots
Why TEE is Important for Modern Consensus

David Tse --- Stanford University and BabylonChain
Bitcoin Staking

Erica Blum --- Reed College
Abraxas: A Black-Box Framework for Throughput-Efficient Hybrid Asynchronous Consensus
Blockchain protocols often face a tradeoff between throughput under low network delay and resilience under high network delay. Hybrid protocols (also called optimistic protocols) attempt to meet in the middle by pairing a high-throughput, low-latency “fast path” with a robust “slow path.” This talk discusses Abraxas, a recent framework that allows mixing and matching fast and slow paths via a black-box approach. Instantiating the framework with a specific choice of fast and slow paths produces a hybrid protocol with the throughput of the fast path under optimistic conditions, and the security of the slow path under arbitrary conditions. Notably, Abraxas maintains stable throughput even when the network experiences frequent “flip flopping” (alternating between the optimistic case and the general case). The talk will conclude with a discussion of takeaways from a protocol design perspective.

Juan Garay --- Texas A&M University
Completeness Theorems for Adaptively Secure Broadcast
In the context of cryptographic protocols, adaptive security refers to the ability to cope with an adversary that is able to "corrupt" participants on the fly, as the protocol executes. The advent of blockchain protocols has reignited the interest in adaptively secure broadcast, as it is by now well understood that broadcasting over a diffusion network allows an adaptive adversary to corrupt the sender depending on the message it attempts to send and change it to one of its choosing. Hirt and Zikas [Eurocrypt ’10] proved that this is an inherent limitation of broadcast when the proof technique is the so-called simulation-based—i.e., that this task is impossible against an adaptive adversary corrupting a strict majority of the parties (a task that is achievable against a static adversary).
In this talk we show that, contrary to previous perception, the above limitation of adaptively secure broadcast is not an artifact of simulation-based security, but rather an inherent issue of adaptive security. In particular, that: (1) the limitation also applies to the traditional property-based broadcast definition adapted for adaptive adversaries, and (2) unlike other impossibilities in adaptive security, this impossibility cannot be circumvented by adding a programmable random oracle, in neither setting, property-based or simulation-based.
Next, we turn to the resource-restricted cryptography (RRC) paradigm [Garay et al., Eurocrypt ’20], which has proven useful in circumventing impossibility results, and ask whether it also affects the above negative result. We answer this question in the affirmative, by showing that time-lock puzzles (TLPs)—which can be viewed as an instance of RRC—indeed allow for achieving the property-based definition and circumvent the impossibility of adaptively secure broadcast. The natural question is then, do TLPs also allow for simulation-based adaptively secure broadcast against corrupted majorities? We answer this question in the negative. Nonetheless, we show that a positive result can be achieved via a non-committing analogue of TLPs in the programmable random-oracle model. Importantly, and as a contribution of independent interest, we also present the first (limited) composition theorem in the resource-restricted setting, which is needed for the complexity-based, non-idealized treatment of TLPs in the context of other protocols.
This is joint work with Ran Cohen and Vassilis Zikas.

Ling Ren --- UIUC
Granular Synchrony: A New Network Timing Model for Distributed Computing
Today's mainstream network timing models for distributed computing are synchrony, partial synchrony, and asynchrony. These models are coarse-grained and often make either too strong or too weak assumptions about the network. This talk introduces a new network timing model called granular synchrony that models the network as a mixture of synchronous, partially synchronous, and asynchronous communication links. The new model is not only theoretically interesting but also more representative of real-world networks. We present necessary and sufficient conditions for solving crash and Byzantine consensus in granular synchrony. Interestingly, consensus among n parties can be achieved against f >= n/2 crash faults or f >= n/3 Byzantine faults without resorting to full synchrony.

Peiyao Sheng --- Princeton University
Technical Framework for Unifying DePIN Coordination
Physical Infrastructure Networks (PINs) form the essential backbone of our daily lives, hosting critical services such as communication, energy, and transportation. These networks are traditionally managed by monopolistic entities, leveraging centralization to maximize economic benefits through network effects. However, the decentralized nature of physical entities demands geographical distribution of infrastructure to facilitate localized supply and demand, providing the gravity to shift PINs to Decentralized PINs.
In this talk, we will explore the transformative potential of DePINs by addressing the main challenges in establishing physical trust and coordinating siloed DePIN sectors. We will showcase three building blocks to construct consensus and bridge economic trust. The first, Proof of Backhaul, is a trust-free speed test where the challengers neither need to be trusted nor have a low latency and high throughput connection to the challenged link. This protocol is a reincarnation of classical Internet telemetry tools like ping and iperf, enhanced with Byzantine fault-tolerant properties. The second, Proof of Location, is designed to securely validate the geographic locations of network participants. It combines cryptographic techniques and Byzantine-resistant data inference with Internet measurements. The last is an incentive design called Proof of Diligence to safeguard state changes within computational tasks. These protocols are crucial for merging physical reliability with digital security, facilitating a unified and functional DePIN economy.

Sandro Coretti-Drayton --- Input Output Global
High-Throughput Blockchain Consensus under Realistic Network Assumptions
An essential characteristic of blockchain protocols is their throughput. Prior work has proposed high-throughput protocols; however, these works either fail to fully utilize the available bandwidth or rely on unrealistic network assumptions. Such assumptions often "abstract away" adversarial behaviors like protocol bursts (releasing old messages in bulk) or equivocations (sending multiple versions of the same protocol message).
In this talk, we’ll have a look at Leios, an overlay protocol designed to transform any underlying low-throughput base protocol into a high-throughput blockchain. Leios achieves $(1 − \delta)$ of the optimal capacity for any constant $\delta > 0$, while impacting latency asymptotically only by a related constant. Consequently, if the underlying protocol has constant time expected settlement, the Leios overlay retains this property. Additionally, we propose a new, more realistic network model that addresses the aforementioned shortcomings and provide an analysis of Leios within this model.

Tim Roughgarden --- Columbia University and a16zcrypto
How Secure Is Your Restaking Network?
We study the risks of validator reuse across multiple services in a restaking protocol. We characterize the robust security of a restaking network as a function of the buffer between the costs and profits from attacks. For example, our results imply that if attack costs always exceed attack profits by 10%, then a sudden loss of .1% of the overall stake (e.g., due to a software error) cannot result in the ultimate loss of more than 1.1% of the overall stake. We also provide "local" analogs of these overcollaterization conditions and robust security guarantees that apply specifically for a target service or coalition of services. All of our bounds on worst-case stake loss are the best possible. Finally, we bound the maximum-possible length of a cascade of attacks.
Our results suggest measures of risk that could be exposed to the participants in a restaking protocol. We also suggest polynomial-time computable sufficient conditions that can proxy for these measures. Joint work with Naveen Durvasula.

Vincent Gramoli --- University of Sydney and Redbelly Network
Strengthening Blockchain Security with Accountability
In this talk Vincent will present the DSN’24 best paper entitled “ZLB: a Blockchain to Tolerate Colluding Majorities” co-authored with Alejandro Ranchal-Pedrosa. Prior to this work, blockchains could, at best, tolerate a minority of failures. In particular, Vincent will describe how the behaviors of faulty blockchain nodes combined with recent advances in the theory of accountable consensus makes it possible to design a zero loss payment system, merging forks without penalising the recipients of conflicting transactions. By addressing double spending attacks, this work brings blockchains one step closer to support real world assets.