Science and Engineering of Consensus 2024

An affiliated workshop of The Science of Blockchain Conference 2024

Sponsored by:

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

• When? Tuesday, August 6th, 2024, 9:30 am to 5:00 pm
  
• Where? Emma and Georgina Bloomberg Center – Cornell Tech. New York City, USA.
  
• Registration: Attendance is free, but registration is mandatory for in-person attendance.
  If you receive an email indicating that due limited capacity you will not be able to participate in person, you will be able to attend virtually through the live stream.
  
• Livestream: Link coming soon.
  
• Contact: Workshop organized by Stanford Tse Lab. For questions, contact Ertem Nusret Tas, Srivatsan Sridhar, or David Tse.

Speakers

• Andrew Miller — UIUC and Flashbots
• David Tse — Stanford University and BabylonChain
• Erica Blum — Reed College
• Ittai Abraham — Intel Labs
• Juan Garay — Texas A&M University
• Peiyao Sheng — Princeton University
• Sandro Coretti-Drayton — Input Output Global
• Tim Roughgarden — Columbia University and a16zcrypto
• Uma Roy — Succinct labs
• Vincent Gramoli — University of Sydney and Redbelly Network

Schedule coming soon.

Abstracts

• Andrew Miller — UIUC and Flashbots
  Title: Why TEE is Important for Modern Consensus
  
  

• 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.

• Ittai Abraham — Intel Labs
  Adaptivia - what can we do against adaptive adversaries
  Blockchain scalability has several bottlenecks. In this talk I will survey the consensus bottleneck and highlight new research on how deeply it is connected to the degree of adaptivity of the adversary.

• 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.

• Peiyao Sheng — Princeton University
  Title: 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.