Order-fair consensus aims to prevent a leader or block producer from exploiting transaction order, a concern amplified by front-running and MEV in decentralized finance. Existing order-fairness notions avoid some impossibilities by batching cyclic dependencies or by allowing bounded displacement, but these relaxations do not distinguish a tiny timing inversion from a large physical time gap. We revisit approximate-order-fairness (AOF), originally introduced and dismissed as too weak or impossible in prior work, in a synchronous model where parties can timestamp transaction arrivals using physical time. We show that time-aware AOF has a nontrivial feasible region: if a fraction φ of nodes receive tx at least before tx', then tx can be forced before tx' whenever > Δsync/k and φ > 1 - h/k, where h is the honest fraction and Δsync is the honest dissemination bound. We also give matching-style infeasibility constructions showing why smaller delays or lower thresholds permit Condorcet cycles. Finally, we outline how a HotStuff-style consensus layer can agree on timestamp reports while a deterministic ordering function enforces the strongest acyclic AOF constraints available in the observed execution.

Correlated equilibria are a standard solution concept in game theory and generalize Nash equilibria. In a 2-player non-cooperative game in which player i has action set A_i, a correlated equilibrium is a self-enforcing probability distribution σ over A_1 * A_2. Specifically, when a strategy profile (s_1, s_2) in A_1 * A_2 is sampled according to σ, each player i can observe their own component s_i, but not the other player's component. Knowing s_i and σ, player i cannot increase their expected payoff by defecting and playing a strategy s'_i different from s_i. Correlated equilibria are ubiquitous and crucial in mechanism design, including in the design of blockchain-based protocols which aim to incentivize honest behavior. A correlated equilibrium depends on a centralized and impartial oracle, often called the ''external signal'' in game theory literature, to sample a strategy profile and disclose each player's component to them, while keeping the other player's component secret. However, there is currently no trustless method to achieve this on the blockchain without centralization or relying on trusted third-parties. In this work, we address this challenge and provide two novel protocols, one based on oblivious transfer and the other based on zkSNARKs to replace the public signal with a smart contract. We prove that our approaches are secure and provide the desired privacy properties of a correlated equilibrium, while also being efficient in terms of gas usage and thus affordable in practice.

Decentralized random number generation is a widely-studied problem in the blockchain community and much attention has been paid to the so-called on-chain random beacons, i.e. smart contracts that generate randomness which can in turn be used in other contracts. Following the classical methodology of RANDAO, most on-chain beacons receive inputs from a large number n of participants and then aggregate them to compute a final random output. The aggregation is done in a manner that ensures the final output is uniformly random as long as at least one of the participants acts honestly. While being highly successful in providing security guarantes such as unpredictability and tamper-resistance, a major downside of these beacons is their cost. Since every participant has to call a function in the smart contract to provide their input, the total gas usage to generate a single random number is at least Ω(n). In this work, we propose a novel protocol that offloads most of the on-chain communication between the participants and the smart contract to an alternative off-chain communication with a dealer. This leads to a gas-efficient on-chain random beacon with only O(1) gas usage per generated output. Crucially, our protocol is trustless and the dealer is unable to predict or tamper with the result. We maintain the same security guarantees as previous on-chain beacons, while significantly reducing the gas usage. We also show that our protocol is secure even if all but one of the participants, potentially including the dealer, are dishonest.

Many blockchain protocols and applications require access to a reliable source of distributed random numbers. This has led to the recent interest in the study of distributed random number generation (RNG) and randomness beacons. Numerous approaches have been proposed in the literature, using different cryptographic techniques and working under different assumptions. A problem that has recently been studied is that of generating secret random numbers. There is a natural usecase for this. Suppose a casino CASSIE wishes to offer its gambling games as a smart contract. It is not viable to generate a fresh distributed random number for each bet. Instead, a secret random number should be generated at predefined intervals, e.g. each day, and used as a seed to create the randomness for the whole day. This seed should only be known to CASSIE. Moreover, at the end of the day, CASSIE should be able to disclose the seed and prove that there was no tampering. In this work, we propose a simple and novel distributed random beacon protocol that generates distributed random numbers while preserving secrecy. The generated random number can be used in DeFi applications, such as decentralized casinos, for some time, until it is published along with proof that it is indeed the output of our random beacon. In addition to achieving the desired secrecy property, our approach is also efficient and requires the same amount of computation and communication as non-secret random beacons. Our protocol can easily be implemented as a smart contract.

Proof-of-Stake blockchain protocols rely on a dis-tributed random beacon to select the next miner that is allowed to add a block to the chain. Each party's likelihood to be selected is in proportion to their stake in the cryptocurrency. Current random beacons used in PoS protocols have two fundamental limitations: either (i) they rely on pseudo-randomness, e.g. assuming that the output of a hash function is uniform, which is an unproven assumption, or (ii) they generate their randomness using a distributed protocol in which several participants are required to submit random numbers which are then used in the generation of a final random result. However, in this case, there is no guarantee that the numbers provided by the parties are truly random and there is no incentive for the parties to honestly generate uniform randomness. In this work, we provide a protocol that generates trustless and unbiased randomness for PoS and overcomes the above limitations. We provide a game-theoretic guarantee showing that it is in everyone's best interest to submit truly uniform random numbers. Hence, our approach is the first to provably incentivize honest and reliable behavior instead of simply assuming it.

Modern programmable blockchains have built-in support for smart contracts, i.e. ‍programs that are stored on the blockchain and whose state is subject to consensus. After a smart contract is deployed on the blockchain, anyone on the network can interact with it and call its functions by creating transactions. The blockchain protocol is then used to reach a consensus about the order of the transactions and, as a direct corollary, the state of every smart contract. Reaching such consensus necessarily requires every node on the network to execute all function calls. Thus, an attacker can perform DoS by creating expensive transactions and function calls that use considerable or even possibly infinite time and space. To avoid this, following Ethereum, virtually all programmable blockchains have introduced the concept of “gas”. A fixed hard-coded gas cost is assigned to every atomic operation and the user who calls a function has to pay for its total gas usage. This technique ensures that the protocol is not vulnerable to DoS attacks, but it has also had significant unintended consequences. Out-of-gas errors, i.e. ‍when a user misunderestimates the gas usage of their function call and does not allocate enough gas, are a major source of security vulnerabilities in Ethereum. We focus on the well-studied problem of automatically finding upper-bounds on the gas usage of a smart contract. This is a classical problem in the blockchain community and has also been extensively studied by researchers in programming languages and verification. In this work, we provide a novel approach using theorems from polyhedral geometry and real algebraic geometry, namely Farkas’ Lemma, Handelman’s Theorem, and Putinar’s Positivstellensatz, to automatically synthesize linear and polynomial parametric bounds for the gas usage of smart contracts. Our approach is the first to provide completeness guarantees for the synthesis of such parametric upper-bounds. Moreover, our theoretical results are independent of the underlying consensus protocol and can be applied to smart contracts written in any language and run on any blockchain. As a proof of concept, we also provide a tool, called “Asparagus” that implements our algorithms for Ethereum contracts written in Solidity. Finally, we provide extensive experimental results over 24,188 real-world smart contracts that are currently deployed on the Ethereum blockchain. We compare Asparagus against GASTAP, which is the only previous tool that could provide parametric bounds, and show that our method significantly outperforms it, both in terms of applicability and the tightness of the resulting bounds. More specifically, our approach can handle 80.56% of the functions (126,269 out of 156,735) in comparison with GASTAP’s 58.62%. Additionally, even on the benchmarks where both approaches successfully synthesize a bound, our bound is tighter in 97.85% of the cases.