Dahlia Malkhi

Robert McLaughlin, Nir Chemaya, Dingyue Liu et al.

This paper introduces a trade ordering rule that aims to reduce intra-block price volatility in Automated Market Maker (AMM) powered decentralized exchanges. The ordering rule introduced here, Clever Look-ahead Volatility Reduction (CLVR), operates under the (common) framework in decentralized finance that allows some entities to observe trade requests before they are settled, assemble them into "blocks", and order them as they like. On AMM exchanges, asset prices are continuously and transparently updated as a result of each trade and therefore, transaction order has high financial value. CLVR aims to order transactions for traders' benefit. Our primary focus is intra-block price stability (minimizing volatility), which has two main benefits for traders: it reduces transaction failure rate and allows traders to receive closer prices to the reference price at which they submit their transactions accordingly. We show that CLVR constructs an ordering which approximately minimizes price volatility with a small computation cost and can be trivially verified externally.

Ofir Dvir, Kali Hale, Javin Zipkin et al.

We introduce baseSPIDER and SPIDER, private information retrieval (PIR) schemes that embody two technical advancements. The baseSPIDER protocol operates with a single server and a stateful client that performs pre-processing and stores hints for future queries. In this setting, baseSPIDER introduces a new approach that matches the asymptotically optimal communication complexity of state-of-the-art schemes while improving constant factors--an advantage that is particularly significant for databases with large entries. In addition, baseSPIDER offers a conceptually simpler design relative to prior protocols. SPIDER operates over a default database interface and requires no cooperation from the server at any stage. To our knowledge, SPIDER is the first single-server PIR construction of this design, achieving privacy without specialized APIs, auxiliary server state, or protocol-specific interaction beyond conventional indexed access. SPIDER is built via a simple transformation of baseSPIDER to the default server setting, eliminating deployment barriers and enabling immediate applicability to existing systems. This transformation can be applied more broadly to three recent PIR solutions, adapting them for use in the default-server paradigm and yielding solutions of independent interest. SPIDER compares to the resulting modified solutions by exhibiting a simpler design while incurring higher client computational work.

Aviv Yaish, Nir Chemaya, Dahlia Malkhi et al.

Inequality measures such as the Gini coefficient are used to inform and motivate policymaking, and are increasingly applied to digital platforms. We analyze how measures fare in pseudonymous settings that are common in the digital age. One key challenge of such environments is the ability of actors to create fake identities under fictitious false names, also known as ``Sybils.'' While some actors may do so to preserve their privacy, we show that this can hamper inequality measurements: it is impossible for measures satisfying the literature's canonical set of desired properties to assess the inequality of an economy that may harbor Sybils. We characterize the class of all Sybil-proof measures, and prove that they must satisfy relaxed version of the aforementioned properties. Furthermore, we show that the structure imposed restricts the ability to assess inequality at a fine-grained level. We then apply our results to prove that popular measures are not Sybil-proof, with the famous Gini coefficient being but one example out of many. Finally, we examine dynamics leading to the creation of Sybils in digital and traditional settings.

Rithwik Kerur, Pasindu Tennage, Philipp Jovanovic et al.

This paper introduces Nemo-Nemo, a practical crash-fault tolerant (CFT) consensus protocol designed to outperform existing protocols in wide-area networks by bridging design principles from the CFT and Byzantine-fault tolerant (BFT) worlds. By structuring command propagation through a causally ordered DAG, Nemo-Nemo allows all consensus replicas to propose commands with a naturally self-regulating communication regime. By exploiting multi-leader architecture, Nemo-Nemo avoids the performance bottleneck inherent to single-leader protocols. By separating command dissemination from consensus logic, Nemo-Nemo handles challenging network conditions even when consensus commits are stalled. Moreover, leader proposals that miss a deadline are never dropped, but deterministically deferred and executed later, preserving throughput under transient network delays. And by enabling Nemo-Nemo to commit on a DAG in just two network hops, it matches the latency of existing CFT systems, while achieving significantly higher throughput. The result is a robust, deployable system: the first DAG-based CFT consensus protocol proven to exceed state-of-the-art wide-area network performance in both speed and resilience.

Zhuolun Xiang, Dahlia Malkhi, Kartik Nayak et al.

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.

Rithwik Kerur, Divyakant Agrawal, Michael K. Reiter et al.

Spreading and storing erasure-coded data in distributed systems effectively is challenging in real settings. Practical deployments must contend with unpredictable network latencies, particularly when information dispersal is integrated into consensus protocols, a prominent and latency-sensitive use case. Existing approaches address this challenge through timeout-based dissemination and adaptive communication or storage decisions driven by acknowledgments during dissemination. However, these designs focus almost exclusively on dissemination-time efficiency, complicate recovery with reconstruction procedures that require metadata that can differ per consensus value, and rely on a centralized leader to make storage decisions for all nodes. This paper introduces \textbf{Rafture}, a novel information dispersal algorithm, and its integration in a consensus protocol, that overcomes these limitations. Rafture is the first information dispersal solution to incorporate post-dissemination pruning, allowing systems to adapt storage costs after dissemination completes. It employs a simple, fixed-threshold erasure code while varying distinct fragment assignment along a second dimension. This ensures that reconstruction is always possible from $F+1$ fragments using the same interpolation method and no additional metadata. Rafture further enables nodes to adapt autonomously based on locally observed information, eliminating the need for global coordination. We evaluate Rafture in highly dynamic network settings and show that it simplifies recovery while significantly improving long-term storage consumption under variable network conditions.

Filip Rezabek, Dahlia Malkhi, Amir Yahalom

The emergence of decentralized satellite networks creates a pressing need for trust architectures that operate without physical access to hardware, without pre-provisioned vendor secrets, and without dependence on a single manufacturer's attestation service. Terrestrial TEEs are insufficient: hardware-based designs are susceptible to physical attacks, and most platforms root their attestation chains in secrets provisioned during manufacturing, creating a pre-launch trust window and single-vendor dependency that cannot be independently audited. We present Space Fabric, an architecture that provides the missing trust foundation for orbital computing by relocating the trusted computing stack to satellite infrastructure, exploiting post-launch physical inaccessibility as a tamper barrier unattainable by terrestrial deployments. Our Satellite Execution Assurance Protocol binds workload execution to a specific satellite via a Byzantine-tolerant endorsement quorum of distributed ground stations, certifying not only \emph{what} executes inside the TEE but also \emph{where}. All cryptographic secrets are generated within co-located secure elements after launch, with no signing keys accessible on Earth at any point. To reduce single-vendor dependence, Space Fabric distributes its trust anchor across two independent secure elements, an NXP SE050 and a TROPIC01, both of which must co-sign attestation evidence. We implement Space Fabric on a USB Armory Mk II with ARM TrustZone, verify attestation end-to-end using Veraison, and provide a security analysis with satisfaction arguments and impossibility bounds under a strong adaptive adversary.

Shehar Bano, Alberto Sonnino, Andrey Chursin et al.

This paper presents Twins, an automated unit test generator of Byzantine attacks. Twins implements three types of Byzantine behaviors: (i) leader equivocation, (ii) double voting, and (iii) losing internal state such as forgetting 'locks' guarding voted values. To emulate interesting attacks by a Byzantine node, it instantiates twin copies of the node instead of one, giving both twins the same identities and network credentials. To the rest of the system, the twins appear indistinguishable from a single node behaving in a 'questionable' manner. Twins can systematically generate Byzantine attack scenarios at scale, execute them in a controlled manner, and examine their behavior. Twins scenarios iterate over protocol rounds and vary the communication patterns among nodes. Twins runs in a production setting within DiemBFT where it can execute 44M Twins-generated scenarios daily. Whereas the system at hand did not manifest errors, subtle safety bugs that were deliberately injected for the purpose of validating the implementation of Twins itself were exposed within minutes. Twins can prevent developers from regressing correctness when updating the codebase, introducing new features, or performing routine maintenance tasks. Twins only requires a thin wrapper over DiemBFT, we thus envision other systems using it. Building on this idea, one new attack and several known attacks against other BFT protocols were materialized as Twins scenarios. In all cases, the target protocols break within fewer than a dozen protocol rounds, hence it is realistic for the Twins approach to expose the problems.

Dahlia Malkhi, Kartik Nayak, Ling Ren

This paper introduces Flexible BFT, a new approach for BFT consensus solution design revolving around two pillars, stronger resilience and diversity. The first pillar, stronger resilience, involves a new fault model called alive-but-corrupt faults. Alive-but-corrupt replicas may arbitrarily deviate from the protocol in an attempt to break safety of the protocol. However, if they cannot break safety, they will not try to prevent liveness of the protocol. Combining alive-but-corrupt faults into the model, Flexible BFT is resilient to higher corruption levels than possible in a pure Byzantine fault model. The second pillar, diversity, designs consensus solutions whose protocol transcript is used to draw different commit decisions under diverse beliefs. With this separation, the same Flexible BFT solution supports synchronous and asynchronous beliefs, as well as varying resilience threshold combinations of Byzantine and alive-but-corrupt faults. At a technical level, Flexible BFT achieves the above results using two new ideas. First, it introduces a synchronous BFT protocol in which only the commit step requires to know the network delay bound and thus replicas execute the protocol without any synchrony assumption. Second, it introduces a notion called Flexible Byzantine Quorums by dissecting the roles of different quorums in existing consensus protocols.

Soumya Basu, Alin Tomescu, Ittai Abraham et al.

This paper introduces a new way to incorporate verifiable secret sharing (VSS) schemes into Byzantine Fault Tolerance (BFT) protocols. This technique extends the threshold guarantee of classical Byzantine Fault Tolerant algorithms to include privacy as well. This provides applications with a powerful primitive: a threshold trusted third party, which simplifies many difficult problems such as a fair exchange. In order to incorporate VSS into BFT, we introduced sAVSS, a framework that transforms any VSS scheme into an asynchronous VSS scheme with constant overhead. By incorporating Kate et al.'s scheme into our framework, we obtain an asynchronous VSS that has constant overhead on each replica -- the first of its kind. We show that a key-value store built using BFT replication and sAVSS supports writing secret-shared values with about a 30% - 50% throughput overhead with less than 35 millisecond request latencies.

Ittai Abraham, Dahlia Malkhi, Kartik Nayak et al.

The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.