When: Friday (Mar 28), 11:00-noon

Where: AKW200, Arthur K. Watson Hall, 51 Prospect St, New Haven, CT 06511, US

Speaker: Fatima Elsheimy (Yale)

Title: Early Stopping Byzantine Agreement

Abstract: Early stopping agreement protocols ensure termination based on the actual number of malicious parties encountered during execution, $f \leq t$, rather than assuming the worst-case corruption bound of $t < n$. The fundamental lower bound on round complexity for such protocols is $\min{f+2, t+1}$ rounds. In this talk, I will provide a comprehensive overview of techniques for achieving early stopping in different settings: the information-theoretic setting, which tolerates up to $t < n/3$, and the authenticated setting, which tolerates up to $t < n/2$ and how it can be extended to tolerate $t < n$ corruptions. I will also discuss recent advancements in this area and highlight key open problems that remain unresolved.

Livestream: https://yale.zoom.us/j/98568157789?pwd=crh9MncYfb8xHncO2oFn64Or5b3ePm.1 (Password: 355488, Telephone：203-432-9666 or 646 568 7788)

When: Friday (Apr 4), 11:00-noon

Where: AKW200, Arthur K. Watson Hall, 51 Prospect St, New Haven, CT 06511, US

Speaker: Nir Chemaya (UC Santa Barbara)

Title: CLVR Ordering of Transactions on AMMs

Abstract: Trading on decentralized exchanges via an Automated Market Maker (AMM) mechanism has been massively adopted, with a daily trading volume reaching $1B. This trading method has also received close attention from researchers, central banks, and financial firms, who have the potential to adopt it to traditional financial markets such as foreign exchanges and stock markets. A critical challenge of AMM-powered trading is that transaction order has high financial value, so a policy or method to order transactions in a "good" (optimal) manner is vital. We offer economic measures of both price stability (low volatility) and inequality that inform how a "social planner" should pick an optimal ordering. We show that there is a trade-off between achieving price stability and reducing inequality, and that policymakers must choose which to prioritize. In addition, picking the optimal order can often be costly, especially when performing an exhaustive search over trade orderings (permutations). As an alternative we provide a simple algorithm, Clever Look-ahead Volatility Reduction (CLVR). This algorithm constructs an ordering which approximately minimizes price volatility with a small computation cost. We also provide insight into the strategy changes that may occur if traders are subject to this sequencing algorithm.

Links: https://arxiv.org/abs/2408.02634

Bio: Nir is currently a postdoc with Dahlia Malkhi at UC Santa Barbara (UCSB), and an incoming economics professor at Ben-Gurion University. His research interests include finance, blockchain and experimental and behavioral economics.

When: Friday (Apr 11)

Where: The 2nd Yale Symposium on Privacy, Accountability, Verification and Economics of Blockchain Systems (PAVE)

Speaker: Fahad Saleh (University of Florida)

Title: An Economic Model of the L1-L2 Interaction

Abstract: We provide an economic model of the interaction between a Layer-1 (L1) blockchain and an associated Layer-2 (L2). Our main finding is that, even when the L1 blockchain features value-creating decentralized applications (dApps), there nevertheless exist realistic conditions such that both L1 blockchain investment and L1 cryptoasset market value vanish over time. These results arise when the L2 becomes sufficiently attractive for investment relative to the L1, a situation that would occur if developers focus exclusively on improving L2s while ignoring the L1. Crucially, our results establish that, even if L2s are intended as the primary vehicle for scaling, developers must nonetheless continue to improve the L1 to avoid an adverse outcome for the L1.

Bio: Fahad is an Associate Professor at the University of Florida and a Visiting Associate Professor at the Massachusetts Institute of Technology. His research focuses primarily on economic analysis associated with permissionless blockchains and differs from work in computer science particularly in that it studies outcomes when investment capital is determined endogenously based on participants being rational investors. Specifically, some of Fahad's work examines blockchain security when mining or staking investments are determined endogenously based on optimal investor behavior. Moreover, other parts of Fahad's work analyzes economic outcomes for decentralized applications (e.g., decentralized exchanges and decentralized lending protocols) and this work determines liquidity endogenously based on the opportunity cost of capital rather than taking liquidity as given. Fahad's work has been published in the top business school journals including Management Science and the Review of Financial Studies. Additionally, Fahad serves on the editorial board of Management Science, is the lead organizer of the Crypto and Blockchain Economic Research (CBER) Forum and is a fellow of the FinTech Initiative at Cornell University. Fahad holds a PhD in Finance from the New York University Stern School of Business. He also holds graduate and undergraduate degrees in engineering from Columbia University and Cornell University respectively.

When: Friday (Apr 25), 11:00-noon

Where: AKW200, Arthur K. Watson Hall, 51 Prospect St, New Haven, CT 06511, US

Speaker: Lei Yang (MegaLabs)

Title: Practical Rateless Set Reconciliation

Abstract:  Set reconciliation, where two parties hold fixed-length bit strings and run a protocol to learn the strings they are missing from each other, is a fundamental task in many distributed systems. We present Rateless Invertible Bloom Lookup Tables (Rateless IBLT), the first set reconciliation protocol, to the best of our knowledge, that achieves low computation cost and near-optimal communication cost across a wide range of scenarios: set differences of one to millions, bit strings of a few bytes to megabytes, and workloads injected by potential adversaries. Rateless IBLT is based on a novel encoder that incrementally encodes the set difference into an infinite stream of coded symbols, resembling rateless error-correcting codes. We compare Rateless IBLT with state-of-the-art set reconciliation schemes and demonstrate significant improvements. Rateless IBLT achieves 3--4x lower communication cost than non-rateless schemes with similar computation cost, and 2--2000x lower computation cost than schemes with similar communication cost. We show the real-world benefits of Rateless IBLT by applying it to synchronize the state of the Ethereum blockchain, and demonstrate 5.6x lower end-to-end completion time and 4.4x lower communication cost compared to the system used in production. 

Links: https://dl.acm.org/doi/10.1145/3651890.3672219

Bio: Lei Yang is a cofounder and the CTO of Mega Labs, a startup that is building MegaETH, the first real-time blockchains. He recently finished his PhD on distributed consensus and networking at MIT CSAIL advised by Mohammad Alizadeh. He also holds an SM from MIT and a BS from Peking University on Computer Science.

When: Friday (May 9), 11:00-noon

Where: DL431, Dunham Lab, 10 Hillhouse Ave, New Haven, CT 06511, US

Speaker: Akaki Mamageishvili (Offchain Labs)

Title: Economic Censorship Games in Fraud Proofs

Abstract: Optimistic rollups rely on fraud proofs -- interactive protocols executed on Ethereum to resolve conflicting claims about the rollup's state -- to scale Ethereum securely. To mitigate against potential censorship of protocol moves, fraud proofs grant participants a significant time window, known as the challenge period, to ensure their moves are processed on chain. Major optimistic rollups today set this period at roughly one week, mainly to guard against strong censorship that undermines Ethereum's own crypto-economic security. However, other forms of censorship are possible, and their implication on optimistic rollup security is not well understood. This paper considers economic censorship attacks, where an attacker censors the defender's transactions by bribing block proposers. At each step, the attacker can either censor the defender -- depleting the defender's time allowance at the cost of the bribe -- or allow the current transaction through while conserving funds for future censorship. We analyze three game theoretic models of these dynamics and determine the challenge period length required to ensure the defender's success, as a function of the number of required protocol moves and the players' available budgets.

Link: https://doi.org/10.48550/arXiv.2502.20334

Bio: Akaki has a Ph.D. in theoretical computer science from ETH Zurich. After graduation, he worked as a postdoc and then senior researcher in microeconomics at ETH Zurich. Currently, he is a Senior Research Scientist at Offchain, where he works on optimization and design of rollup protocols.

Livestream: https://yale.zoom.us/j/91845729610?pwd=y8AQTzgJlbz4gfkPaL90Aji8pA72Io.1 (Password: 466922, Telephone：203-432-9666 or 6465687788)

When: Wednesday (Mar 19), 2pm

Where: DL220, Dunham Lab, 10 Hillhouse Ave, New Haven, CT 06511, US

Speaker: Ferhat Erata (Yale)

Title: Learning Randomized Reductions and Program Properties for Security, Privacy, and Side-Channel Resilience (PhD dissertation defense)

Abstract: Modern computing systems face multifaceted challenges in security, privacy, and leakage resilience. This dissertation makes four key contributions to addressing these challenges. First, it focuses on analyzing side-channel vulnerabilities in low-level cryptographic code and quantum computers using symbolic AI techniques. I introduce novel symbolic register analyses to automatically detect power side-channel vulnerabilities in constant-time cryptographic implementations. Additionally, I demonstrate an algebraic reconstruction method to reverse-engineer quantum circuits from power traces, aiming to extract proprietary information from these circuits. Second, my research explores learning randomized reductions. Informally, a randomized self-reduction allows computing a function’s value at a specific point by evaluating it on randomized inputs. Here, I present a new framework that dynamically infers such properties from implementations using machine learning. Third, the dissertation demonstrates practical applications of these randomized reductions in compiling effective countermeasures against power side-channel and fault injection attacks. It also develops protocols for leakage-resilient machine learning and private quantum computations. Finally, it investigates learning-based methods for partitioning propositional encodings of combinatorial security analysis problems within the cube-and-conquer paradigm, which splits large SAT instances into smaller, more tractable subproblems. We train transformer models to learn branching heuristics within SAT-solving frameworks. Together, these contributions advance automated security analysis and resilience across classical and quantum domains.
Advisors: Ruzica Piskac, Jakub Szefer (co-advisor). Committee: Zhong Shao, Shafi Goldwasser (UC Berkeley), Byron Cook (AWS), Scott Shapiro.

Abstract: Following the invention of Bitcoin, there has been a proliferation of many permissionless blockchains. Each such chain provides a public ledger that can be written to and read from by anyone. In this multi-chain world, a natural question arises: what is the optimal security an existing blockchain, a consumer chain, can extract by only reading from and writing to ‘k’ other existing blockchains, so-called the provider chains? In this talk, we will answer this question in three ways: (1) We will first see a protocol, where an off-the-shelf PBFT-style proof-of-stake protocol (acting as a consumer chain) sends timestamps to Bitcoin (the provider chain) to reduce its stake withdrawal delay and to resolve issues such as non-slashable long-range safety attacks and low liveness resilience. (2) Applying the checkpointing method iteratively, we will then design a protocol called 'interchain timestamping', which enables a consumer chain to extract the maximum economic security from the provider chains, as quantified by the slashable safety resilience. (3) Finally, drawing an analogy with switching circuits, we will design two basic compositional operations between blockchains, serial and triangular compositions, and use these operations as building blocks to construct general overlay blockchains that read from and write to a given set of blockchains. This talk is based on the following papers: 1. Bitcoin-Enhanced Proof-of-Stake Security: Possibilities and Impossibilities (IEEE S&P 2023), 2. Interchain Timestamping for Mesh Security (ACM CCS 2023), 3. A Circuit Approach to Constructing Blockchains on Blockchains (AFT 2024).

Bio: Ertem Nusret Tas is a PhD student in Electrical Engineering at Stanford University, working with Prof. David Tse on the analysis of blockchains. He completed both his BS and MEng degrees at the Electrical Engineering and Computer Science department at MIT. His current research focuses on blockchains, consensus protocols and cryptography. He has previously completed summer internships at a16z Crypto Research, BabylonChain, Celestia and Apple. He received a distinguished paper award at ACM CCS 2024, and his papers on blockchains, consensus protocols and cryptography have appeared in top venues such as ACM CCS, IEEE S&P, Financial Cryptography (FC) and Advances in Financial Technologies (AFT).

Abstract: Polygenic Risk Scores (PRSs) estimate the likelihood of individuals to develop diseases based on their genetic variations. They are commonly considered non-sensitive information and are publicly shared with results of clinical studies or on health forums. In this talk, I will describe how PRSs can be exploited to recover genotypes of individuals and to de-anonymize them. By framing genotype recovery as the subset-sum problem with side information from population statistics, we show that it is possible to reconstruct a significant portion of an individual’s genome from their individual PRS values with 95% accuracy. Even imperfect recovery is then sufficient to identify the individual or their relatives in genealogy databases or public anonymized biobanks.

Bio: Kirill Nikitin is a postdoctoral researcher at Columbia University and the New York Genome Center working with Gamze Gürsoy on analyzing privacy leakages from genomic data. Previously, he worked as a postdoc with Vitaly Shmatikov at Cornell Tech, and he received his PhD in Computer and Communication Sciences from EPFL, where he was advised by Bryan Ford. Besides genomics privacy, he has worked on metadata protection in encrypted files and communication, private information retrieval, security of software-update systems, and blockchains. Personal website: https://nikirill.com

Abstract: I plan to divide the talk into two parts. In the first part, I will review my past and ongoing research on applying game theory and mechanism design to blockchain research, highlight two pieces of work: 1. The economic forces that simultaneously compromise and sustain decentralization; 2. The promise of Bitcoin mining to actually lower total carbon emission in the overall economy. In the second half, I will introduce my current interests in incorporating cryptography into mechanism design. I will explain how cryptography may enable the implementation of otherwise infeasible mechanisms, and envision how economic approaches may complement cryptography.If there is extra time (highly unlikely), I can dive in more other work that fall in the same theme.

Bio: Jiasun Li is currently visiting Yale CS while on sabbatical from associate professor of finance at the Costello College of Business, George Mason University. His research interest is at the intersection of economics and computer science, with focus on applying game theoretical modeling to various blockchain-related topics such as mining, distributed consensus, blockchain scaling, tokenomics. His broader interests encompass empirical studies of the blockchain ecosystem and the application of game theory and mechanism design to other topics such as security design, human-genAI interaction, and traffic control.Dr Li's research has appeared in leading business/finance journals including the Journal of Finance, Review of Financial Studies, and Management Science as well as computer science workshops including ACM Web (WWW) and Financial Cryptography (FC), among others. His ongoing research is supported by grants from the NSF CAREER Award and the Ethereum Foundation, among others. His past work has won the Chicago Quantitative Alliance (CQA) academic paper competition and Yihong Xia Best Paper Award, among other prizes. Besides academic talks at business schools/CS departments, he has also been invited to speak at the Federal Reserve, Securities and Exchange Commission, Department of Homeland Security, and International Monetary Fund (IMF). Dr Li received his Ph.D. in Finance from UCLA Anderson School of Management and B.S. in Mathematics from Fudan University in Shanghai, China.

Abstract: We show that the widely-used Schnorr signature scheme meets existential unforgeability under chosen-message attack (EUF-CMA) in the random oracle model (ROM) if the circular discrete-logarithm (CDL) assumption, a new, non-interactive, and falsifiable variant of DL we introduce, holds in the underlying group. Notably, our reduction is *tight*, meaning the constructed adversary against CDL has essentially the same running time and success probability as the assumed forger. Tightness is essential for justifying the key length used in practice. To our knowledge, we are the first to exhibit such a reduction to even a non-interactive assumption. We justify CDL by showing it is as hard as DL in two carefully chosen idealized models, which idealize different aspects of the assumption.

Links: https://eprint.iacr.org/2024/1528

Bio: Adam O’Neill is an Assistant Professor in the Manning College of Information and Computer Sciences at the University of Massachusetts, Amherst. Previously, he was an Assistant Professor of Computer Science at Georgetown University. He received his Ph.D. in Computer Science at the Georgia Institute of Technology and held postdoctoral appointments at the University of Texas at Austin and Boston University. His doctoral work was recognized with the CRYPTO 2022 Test-of-Time Award.

Abstract: In this work, we try to map how arbitrage between decentralized and centralized exchanges can create incentives for reducing or increasing latency in blockchains.  Under specific price dynamics, we demonstrate that arbitrage opportunities may incentivize block producers to delay releasing a new block until certain price deviations occur. In other price dynamics, latency strategies may even become irrelevant.  We not only analyze price dynamics but also examine how factors such as transaction fees, interest rates, and the blockchain consensus mechanism shape different timing strategies. To support the model and results, we developed a more flexible framework for stopping time policies in blockchains and characterized the profit function for arbitrage in Constant Function Market Makers. To empirically assess these incentives, we examine data on Multi-Block Maximal Extractable Value (MEV), a scenario that allows more sophisticated timing strategies.

Links: https://pages.stern.nyu.edu/~jreed/papers/paper28.pdf

Bio: Gustavo Grivol is an Operations Management Ph.D. student at NYU Stern, advised by Prof. Hanna Halaburda and Prof. Josh Reed. His research focuses on applications of stochastic processes in decision making and platform design. His research interests also include social networks and blockchains.

Abstract: This paper explores the problem of preventing length leakage in oblivious data access mechanisms with passive persistent adversaries. We show that designing mechanisms that prevent both length leakage and access pattern leakage requires navigating a three-way tradeoff between storage footprint, bandwidth footprint, and the information leaked to the adversary. We establish powerful lower bounds on achievable storage and bandwidth footprints for a variety of leakage profiles, and present constructions that perfectly or near-perfectly match the lower bounds.

Abstract: In a series of works, we study Transaction Fee Mechanisms (TFMs), which determine how much fees user transactions have to pay to be processed, and the amount of fees miners can collect as revenue. We tackle the question of whether one can design "perfect" TFMs, and prove the elegant prior work does not fully address it due to relying on stricter definitions than the canonical ones. We also prove that two TFMs satisfy relaxations of the canonical definitions while enjoying good revenue. We go beyond the myopic setting of prior work and consider transactions that can expire, presenting a novel allocation strategy which outperforms the myopic greedy strategy's revenue.

Links: A partial list of the body of work covered:

• Barriers to Collusion-resistant Transaction Fee Mechanisms (EC24)

• Speculative Denial-of-Service Attacks in Ethereum (USENIXSEC24)

• Discrete & Bayesian Transaction Fee Mechanisms (MARBLE24)

• Tutorial on Transaction Fee Mechanism Design (EC24)

• Scheduling With Time Discounts (2024)

Bio: Aviv researches the economics and security of distributed systems. He is a postdoc at Yale, where he is grateful for being hosted by Prof. Fan Zhang, and co-hosted by Profs. Ben Fisch, Charalampos (Babis) Papamanthou, and Zhong Shao. He is also a visiting researcher at Innsbruck University, graciously hosted by Prof. Rainer Böhme. Previously, he had the pleasure of doing a PhD with Prof. Aviv Zohar at HUJI, where he also was a lecturer for two courses and received a teaching award. Among other honors, the CBER Forum named him one of the top PhD graduates of 23-24, and he received the CCS Distinguished Paper award, the CBER Best Paper award, two Ethereum Foundation grants, the AIANI and Ze'ev Jabotinsky fellowships, and HUJI's rector award for first-in-class MSc students.