This paper centers around a simple yet crucial question for everyday users: How should one choose their delegated validators within proof-of-stake (PoS) protocols, particularly in the context of Ethereum 2.0? This has been a long-overlooked gap, as existing studies have primarily focused on inter-committee (validator set) behaviors and activities, while neglecting the dynamic formation of committees, especially for individual stakeholders seeking reliable validators. Our study bridges this...

Optimal simple rules for the monetary policy of the first stochastically dominant crypto-currency are derived in a Dynamic Stochastic General Equilibrium (DSGE) model, in order to provide optimal responses to changes in inflation, output, and other sources of uncertainty. The optimal monetary policy stochastically dominates all the previous crypto-currencies, thus the efficient portfolio is to go long on the stochastically dominant crypto-currency: a strategy-proof arbitrage featuring a...

One of the most fundamental results in game theory is that every finite strategic game has a Nash equilibrium, an assignment of (randomized) strategies to players with the stability property that no individual player can benefit from deviating from the assigned strategy. It is not known how to efficiently compute such a Nash equilibrium --- the computational complexity of this task is characterized by the class PPAD, but the relation of PPAD to other problems and well-known complexity...

Fair exchange is a fundamental primitive enabled by blockchains, and is widely adopted in applications such as atomic swaps, payment channels, and DeFi. Most existing designs of blockchain-based fair exchange protocols consider only the participating users as strategic players, and assume the miners are honest and passive. However, recent works revealed that the fairness of commonly deployed fair exchange protocols can be broken entirely in the presence of user-miner collusion. In...

This paper is subsumed by Rapidash (https://eprint.iacr.org/2022/1063). Please use Rapidash for the citation. Fair exchange is a fundamental primitive for blockchains, and is widely adopted in applications such as atomic swaps, payment channels, and DeFi. Most existing designs of blockchain-based fair exchange protocols consider only the users as strategic players, and assume honest miners. However, recent works revealed that the fairness of commonly deployed fair exchange protocols can...

The stock markets have two primary functions, that of providing liquidity and price discovery. While the market micro-structure was mostly ignored or assumed to function ideally for the purpose of asset pricing, O'Hara (Journal of Finance, 2003) has established that both liquidity and price discovery affect asset pricing, and in particular asset returns. Easley and O'Hara (Journal of Finance 2004) have demonstrated that informed investors' private information is not reflected efficiently in...

We present $\textit{Colordag}$, a blockchain protocol where following the prescribed strategy is, with high probability, a best response as long as all miners have less than $1/2$ of the mining power. We prove the correctness of Colordag even if there is an extremely powerful adversary who knows future actions of the scheduler: specifically, when agents will generate blocks and when messages will arrive. The state-of-the-art protocol, Fruitchain, is an $\varepsilon$-Nash equilibrium as long...

Interoperability is a fundamental challenge for long-envisioned blockchain applications. A mainstream approach is to use Trusted Execution Environment (TEEs) to support interoperable off-chain execution. However, this incurs multiple TEEs configured with non-trivial storage capabilities running on fragile concurrent processing environments, rendering current strategies based on TEEs far from practical. The purpose of this paper is to fill this gap and design a practical interoperability...

Cleve’s celebrated lower bound (STOC’86) showed that a de facto strong fairness notion is impossible in 2-party coin toss, i.e., the corrupt party always has a strategy of biasing the honest party’s outcome by a noticeable amount. Nonetheless, Blum’s famous coin-tossing protocol(CRYPTO’81) achieves a strictly weaker “game-theoretic” notion of fairness — specifically, it is a 2-party coin toss protocol in which neither party can bias the outcome towards its own preference; and thus the...

Outsourcing computation allows a resource limited client to expand its computational capabilities by outsourcing computation to other nodes or clouds. A basic requirement of outsourcing is providing assurance that the computation result is correct. We consider a smart contract based outsourcing system that achieves assurance by replicating the computation on two servers and accepts the computation result if the two responses match. Correct computation result is obtained by using...

Attribute-based encryption (ABE) is a cryptographic technique known for ensuring fine-grained access control on encrypted data. One of the main drawbacks of ABE is the time required to decrypt the ciphertext is considerably expensive, since it grows with the complexity of access policy. Green et al. [USENIX, 2011] provided the outsourced ABE scheme, in which most computational overhead of ciphertext decryption is outsourced from end user to the cloud. However, their method inevitably...

The inconsistency of Nash equilibrium of rational delegated computation scheme in the UC framework will lead to the lack of strict security proof of the protocols fundamentally. The consistency proof of Nash equilibrium between the ideal world and the real world has always been a challenge in the research field. In this paper, we analyze the Nash equilibrium according to the game model of rational delegated computation, and the ideal functionality for rational delegation of computation based...

We show that, relative to a random oracle, solving the END-OF-LINE problem (which is PPAD-complete) is no easier than computing the function \[f(N,x,T) = x^{2^T} \text{mod } N,\] where $N$ is an $n$-bit RSA modulus, $x\in \mathbb{Z}_N^*$ and $T\in\mathbb{N}$. It was conjectured by Rivest, Shamir and Wagner, that, unless the factorization of $N$ is known, the fastest algorithm for computing $f$ consists of $\Omega(T)$ iterated squaring operations mod $N$. Under a milder assumption, namely...

We introduce the notion of a \textit{continuous verifiable delay function} (cVDF): a function $g$ which is (a) iteratively sequential---meaning that evaluating the iteration $g^{(t)}$ of $g$ (on a random input) takes time roughly $t$ times the time to evaluate $g$, even with many parallel processors, and (b) (iteratively) verifiable---the output of $g^{(t)}$ can be efficiently verified (in time that is essentially independent of $t$). In other words, the iterated function $g^{(t)}$ is a...

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography. We show that solving the End-of-Metered-Line problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck...

Zero-Knowledge Proof-of-Identity from trusted public certificates (e.g., national identity cards and/or ePassports; eSIM) is introduced here to permissionless blockchains in order to remove the inefficiencies of Sybil-resistant mechanisms such as Proof-of-Work (i.e., high energy and environmental costs) and Proof-of-Stake (i.e., capital hoarding and lower transaction volume). The proposed solution effectively limits the number of mining nodes a single individual would be able to run while...

Blockchain and cryptocurrency are a hot topic in today’s digital world. In this paper, we create a game theoretic model in continuous time. We consider a dynamic game model of the bitcoin market, where miners or players use mining systems to mine bitcoin by investing electricity into the mining system. Although this work is motivated by BTC, the work presented can be applicable to other mining systems similar to BTC. We propose three concepts of dynamic game theoretic solutions to the model:...

A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file. In this sense a PoRep is both a proof of space (PoS) and a proof of retrievability (PoR). This paper is a foundational study of PoReps, exploring both their capabilities and their limitations. While PoReps may unconditionally demonstrate possession of data, they fundamentally...

Trust models are widely used in various computer science disciplines. The main purpose of a trust model is to continuously measure trustworthiness of a set of entities based on their behaviors. In this article, the novel notion of rational trust modeling is introduced by bridging trust management and game theory. Note that trust models/reputation systems have been used in game theory (e.g., repeated games) for a long time, however, game theory has not been utilized in the process of trust...

Asharov, Canetti, and Hazay (Eurocrypt 2011) studied how game-theoretic concepts can be used to capture the cryptographic properties of correctness, privacy, and fairness in two-party protocols for fail- stop adversaries. In this work, we further study the characterization of the cryptographic properties of specific two-party protocols, oblivious transfer (OT) and commitment, in terms of game theory. Specif- ically, for each protocol, OT and commitment, we define a two-party game between...

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting---anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions') introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15)...

We present ``Ouroboros,'' the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a ``proof of stake'' blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We also present a novel reward mechanism for incentivizing proof of stake...

The exact hardness of computing a Nash equilibrium is a fundamental open question in algorithmic game theory. This problem is complete for the complexity class \ppad. It is well known that problems in \ppad\ cannot be \np-complete unless $\np=\conp$. Therefore, a natural direction is to reduce the hardness of \ppad\ to the hardness of problems used in cryptography. Bitansky, Paneth, and Rosen [FOCS 2015] prove the hardness of \ppad\ assuming the existence of quasi-polynomially hard...

A seminal result of Cleve (STOC 1986) showed that fairness, in general, is impossible to achieve in case of two-party computation if one of them is malicious. Later, Gordon et al. (STOC 2008, JACM 2011) observed that there exist two distinct classes of functions for which fairness can be achieved. One is any function without an embedded XOR, and the other one is a particular function containing an embedded XOR. In this paper, we revisit both classes of functions in two-party computation...

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong “virtual black-box” notion...

We present a general construction of a rational secret-sharing protocol that converts any rational secret-sharing protocol to a protocol with an expected constant-round reconstruction. Our construction can be applied to protocols for synchronous channels, and preserves a strict Nash equilibrium of the original protocol. Combining with an existing protocol, we obtain the first expected constant-round protocol that achieves a strict Nash equilibrium with the optimal coalition...

We revisit the question of whether cryptographic protocols can replace correlated equilibria mediators in two-player strategic games. This problem was first addressed by Dodis, Halevi and Rabin (CRYPTO 2000), who suggested replacing the mediator with a secure protocol and proved that their solution is stable in the Nash equilibrium (NE) sense, provided that the players are computationally bounded. We show that there exist two-player games for which no cryptographic protocol can implement the...

The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. At TCC'10, Fuchsbauer \emph{et al.} introduced two equilibrium notions (computational version of strict Nash equilibrium and stability with respect to trembles) offering a computational relaxation of traditional game theory equilibria. Using trapdoor permutations, they constructed a rational $t$-out-of $n$ sharing technique satisfying these new security...

Rational secret sharing was proposed by Halpern and Teague in STOC'04. The authors show that, in a setting with rational players, secret sharing and multiparty computation are only possible if the actual secret reconstruction round remains unknown to the players. All the subsequent works use a similar approach with different assumptions. We change the direction by bridging cryptography, game theory, and reputation systems, and propose a social model for repeated rational secret sharing. We...

We consider the problem of rational secret sharing introduced by Halpern and Teague \cite{HT04}, where the players involved in secret sharing play only if it is to their advantage. This can be characterized in the form of preferences. Players would prefer to get the secret than to not get it and secondly with lesser preference, they would like as few other players to get the secret as possible. Several positive results have already been published to efficiently solve the problem of rational...

The design of rational cryptographic protocols is a recently created research area at the intersection of cryptography and game theory. In this paper, we propose a new $m$-out-of-$n$ rational secret sharing scheme requiring neither the involvement of the dealer (except during the initial share distribution) nor a trusted mediator. Our protocol leads to a Nash equilibrium surviving the iterated deletion of weakly dominated strategies for $m \geq 4$. Our construction is information...

Rational secret sharing protocols in both the two-party and multi-party settings are proposed. These protocols are built in standard communication networks and with unconditional security. Namely, the protocols run over standard point-to-point networks without requiring physical assumptions or simultaneous channels, and even a computationally unbounded player cannot gain more than $\epsilon$ by deviating from the protocol. More precisely, for the $2$-out-of-$2$ protocol the $\epsilon$ is a...

Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded players and the asymptotic nature of cryptographic security, a definition of sequential rationality for this setting has thus far eluded researchers. We propose a new framework for overcoming these obstacles, and provide the first definitions of computational solution concepts that guarantee sequential rationality....

We consider the \textit{rational secret sharing problem} introduced by Halpern and Teague\cite{ht04}, where players prefer to get the secret rather than not to get the secret and with lower preference, prefer that as few of the other players get the secret. Some positive results have been derived by Kol and Naor\cite{stoc08} by considering that players only prefer to learn. They have proposed an efficient $m$-out-of-$n$ protocol for rational secret sharing without using cryptographic...

We propose a new methodology for rational secret sharing leading to various instantiations (in both the two-party and multi-party settings) that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks. We also propose new equilibrium notions (namely, computational versions of strict Nash equilibrium and stability with respect...

We consider enhancing a sealed-bid single-item auction with \emph{privacy} concerns, our assumption being that bidders primarily care about monetary payoff and secondarily worry about exposing information about their type to other players and learning information about other players' types. To treat privacy explicitly within the game theoretic context, we put forward a novel \emph{hybrid utility} model that considers both fiscal and privacy components in the players' payoffs. We show how to...