Smart contracts, the stateful programs running on blockchains, often rely on reports. Publishers are paid to publish these reports on the blockchain. Designing protocols that incentivize timely reporting is the prevalent reporting problem. But existing solutions face a security-performance trade-off: Relying on a small set of trusted publishers introduces centralization risks, while allowing open publication results in an excessive number of reports on the blockchain. We identify the root cause of this trade-off to be the standard symmetric reward design, which treats all reports equally. We prove that no symmetric-reward mechanism can overcome the trade-off. We present Personal Random Rewards for Reporting (Prrr), a protocol that assigns random heterogeneous values to reports. We call this novel mechanism-design concept Ex-Ante Synthetic Asymmetry. To the best of our knowledge, Prrr is the first game-theoretic mechanism (in any context) that deliberately forms participant asymmetry. Prrr employs a second-price-style settlement to allocate rewards, ensuring incentive compatibility and achieving both security and efficiency. Following the protocol constitutes a Subgame-Perfect Nash Equilibrium, robust against collusion and Sybil attacks. Prrr is applicable to numerous smart contracts that rely on timely reports.

Blockchain security is threatened by selfish mining, where a miner (operator) deviates from the protocol to increase their revenue. Selfish mining is exacerbated by adverse conditions: rushing (network propagation advantage for the selfish miner), varying block rewards due to block contents, called miner extractable value (MEV), and petty-compliant miners who accept bribes from the selfish miner. The state-of-the-art selfish-mining-resistant blockchain protocol, Colordag, does not treat these adverse conditions and was proven secure only when its latency is impractically high. We present MAD-DAG, Mutually-Assured-Destruction Directed-Acyclic-Graph, the first practical protocol to counter selfish mining under adverse conditions. MAD-DAG achieves this thanks to its novel ledger function, which discards the contents of equal-length chains competing to be the longest. We analyze selfish mining in both Colordag and MAD-DAG by modeling a rational miner using a Markov Decision Process (MDP). We obtain a tractable model for both by developing conservative reward rules that favor the selfish miner to yield an upper bound on selfish mining revenue. To the best of our knowledge, this is the first tractable model of selfish mining in a practical DAG-based blockchain. This enables us to obtain a lower bound on the security threshold, the minimum fraction of computational power a miner needs in order to profit from selfish mining. MAD-DAG withstands adverse conditions under which Colordag and Bitcoin fail, while otherwise maintaining comparable security. For example, with petty-compliant miners and high levels of block reward variability, MAD-DAG's security threshold ranges from 11% to 31%, whereas both Colordag and Bitcoin achieve 0% for all levels.

Blockchains implement decentralized monetary systems and applications. Recent advancements enable what we call tethering a blockchain to a primary blockchain, securing the tethered chain by nodes that post primary-chain tokens as collateral. The collateral ensures nodes behave as intended, until they withdraw it. Unlike a Proof of Stake blockchain which uses its own token as collateral, using primary-chain tokens shields the tethered chain from the volatility of its own token. State-of-the-art tethered blockchains either rely on centralization, or make extreme assumptions: that all communication is synchronous, that operators remain correct even post-withdrawal, or that withdrawals can be indefinitely delayed by tethered-chain failures. We prove that with partial synchrony, there is no solution to the problem. However, under the standard assumptions that communication with the primary chain is synchronous and communication among the tethered chain nodes is partially synchronous, there is a solution. We present a tethered-chain protocol called Aegis. Aegis uses references from its blocks to primary blocks to define committees, checkpoints on the primary chain to perpetuate decisions, and resets to establish new committees when previous ones become obsolete. It ensures safety at all times and rapid progress when latency among Aegis nodes is low.

Many blockchain-based decentralized services require their validators (operators) to deposit stake (collateral), which is forfeited (slashed) if they misbehave. Restaking networks let validators secure multiple services by reusing stake. These networks have quickly gained traction, leveraging over 20 billion in stake. However, restaking introduces a new attack vector where validators can coordinate to misbehave across multiple services simultaneously, extracting digital assets while forfeiting their stake only once.

A myriad of authentication mechanisms embody a continuous evolution from verbal passwords in ancient times to contemporary multi-factor authentication: Cryptocurrency wallets advanced from a single signing key to using a handful of well-kept credentials, and for online services, the infamous "security questions'' were all but abandoned. Nevertheless, digital asset heists and numerous identity theft cases illustrate the urgent need to revisit the fundamentals of user authentication.

Automated Market Makers (AMMs) are decentralized applications that allow users to exchange crypto-tokens without the need for a matching exchange order. AMMs are one of the most successful DeFi use cases: indeed, major AMM platforms process a daily volume of transactions worth USD billions. Despite their popularity, AMMs are well-known to suffer from transaction-ordering issues: adversaries can influence the ordering of user transactions, and possibly front-run them with their own, to extract value from AMMs, to the detriment of users. We devise an effective procedure to construct a strategy through which an adversary can maximize the value extracted from user transactions.

The security of proof-of-work blockchain protocols critically relies on incentives. Their operators, called miners, receive rewards for creating blocks containing user-generated transactions. Each block rewards its creator with newly minted tokens and with transaction fees paid by the users. The protocol stability is violated if any of the miners surpasses a threshold ratio of the computational power; she is then motivated to deviate with selfish mining and increase her rewards.Previous analyses of selfish mining strategies assumed constant rewards. But with statistics from operational systems, we show that there are occasional whales – blocks with exceptional rewards. Modeling this behavior implies a state-space that grows exponentially with the parameters, becoming prohibitively large for existing analysis tools.We present the WeRLman1framework to analyze such models. WeRLman uses deep Reinforcement Learning (RL), inspired by the state-of-the-art AlphaGo Zero algorithm. Directly extending AlphaGo Zero to a stochastic model leads to high sampling noise, which is detrimental to the learning process. Therefore, WeRLman employs novel variance reduction techniques by exploiting the recurrent nature of the system and prior knowledge of transition probabilities. Evaluating WeRLman against models we can accurately solve demonstrates it achieves unprecedented accuracy in deep RL for blockchain.We use WeRLman to analyze the incentives of a rational miner in various settings and upper-bound the security threshold of Bitcoin-like blockchains. We show, for the first time, a negative relationship between fee variability and the security threshold. The previously known bound, with constant rewards, stands at 0.25 [2]. We show that considering whale transactions reduces this threshold considerably. In particular, with Bitcoin historical fees and its future minting policy, its threshold for deviation will drop to 0.2 in 10 years, 0.17 in 20 years, and to 0.12 in 30 years. With recent fees from the Ethereum smart-contract platform, the threshold drops to 0.17. These are below the common sizes of large miners [3].

Nakamoto's consensus protocol works in a permissionless model and tolerates Byzantine failures, but only offers probabilistic agreement. Recently, the Sandglass protocol has shown such weaker guarantees are not a necessary consequence of a permissionless model; yet, Sandglass only tolerates benign failures, and operates in an unconventional partially synchronous model. We present Gorilla Sandglass, the first Byzantine tolerant consensus protocol to guarantee, in the same synchronous model adopted by Nakamoto, deterministic agreement and termination with probability 1 in a permissionless setting. We prove the correctness of Gorilla by mapping executions that would violate agreement or termination in Gorilla to executions in Sandglass, where we know such violations are impossible. Establishing termination proves particularly interesting, as the mapping requires reasoning about infinite executions and their probabilities.

Blockchain technology is responsible for the emergence of cryptocurrencies, such as Bitcoin and Ethereum. The security of a blockchain protocol relies on the incentives of its participants. Selfish mining is a form of deviation from the protocol where a participant can gain more than her fair share. Previous analyses of selfish mining make easing, non-realistic assumptions. We introduce a more realistic model with varying block rewards in the form of transaction fees. However, this comes at the cost of an intractable state space. To solve the complex model, we introduce WeRLman, a novel method based on deep Reinforcement Learning (deep RL). Using WeRLman, we show reward variability can significantly hurt blockchain security.

Consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the 'blockchain' literature, this is referred to as the permissioned setting. What differentiates Bitcoin from these previously studied protocols is that it operates in a permissionless setting, i.e. it is a protocol for establishing consensus over an unknown network of participants that anybody can join, with as many identities as they like in any role. The arrival of this new form of protocol brings with it many questions. Beyond Bitcoin, what can we prove about permissionless protocols in a general sense? How does recent work on permissionless protocols in the blockchain literature relate to the well-developed history of research on permissioned protocols in distributed computing? To answer these questions, we describe a formal framework for the analysis of both permissioned and permissionless systems. Our framework allows for "apples-to-apples" comparisons between different categories of protocols and, in turn, the development of theory to formally discuss their relative merits. A major benefit of the framework is that it facilitates the application of a rich history of proofs and techniques in distributed computing to problems in blockchain and the study of permissionless systems. Within our framework, we then address the questions above. We consider the Byzantine Generals Problem as a formalisation of the problem of reaching consensus, and address a programme of research that asks, "Under what adversarial conditions, and for what types of permissionless protocol, is consensus possible?" We prove a number of results for this programme, our main result being that deterministic consensus is not possible for decentralised permissionless protocols. To close, we give a list of eight open questions.

Smart Contracts and transactions allow users to implement elaborate constructions on cryptocurrency blockchains like Bitcoin and Ethereum. Many of these constructions, including operational payment channels and atomic swaps, use a building block called Hashed Time-Locked Contract (HTLC).In this work, we distill from HTLC a specification (HTLC-Spec), and present an implementation called Mutual-Assured-Destruction Hashed Time-Locked Contract (MAD-HTLC). MAD-HTLC employs a novel approach of utilizing the existing blockchain operators, called miners, as part of the design. If a user misbehaves, MAD-HTLC incentivizes the miners to confiscate all her funds. We prove MAD-HTLC’s security using the UC framework and game-theoretic analysis. We demonstrate MAD-HTLC’s efficacy and analyze its overhead by instantiating it on Bitcoin’s and Ethereum’s operational blockchains.Notably, current miner software makes only little effort to optimize revenue, since the advantage is relatively small. However, as the demand grows and other revenue components shrink, miners are more motivated to fully optimize their fund intake. By patching the standard Bitcoin client, we demonstrate such optimization is easy to implement, making the miners natural enforcers of MAD-HTLC.Finally, we extend previous results regarding HTLC vulnerability to bribery attacks. An attacker can incentivize miners to prefer her transactions by offering high transaction fees. We demonstrate this attack can be easily implemented by patching the Bitcoin client, and use game-theoretic tools to qualitatively tighten the known cost bound of such bribery attacks in presence of rational miners. We identify bribe opportunities occurring on the Bitcoin and Ethereum main networks where a few dollars bribe could yield tens of thousands of dollars in reward (e.g., $2 for over $25K).

A proof of work (PoW) blockchain protocol distributes rewards to its participants, called miners, according to their share of the total computational power. Sufficiently large miners can perform selfish mining -- deviate from the protocol to gain more than their fair share. Such systems are thus secure if all miners are smaller than a threshold size so their best response is following the protocol.

Proof-of-work (PoW) cryptocurrency blockchains like Bitcoin secure vast amounts of money. Their operators, called miners, expend resources to generate blocks and receive monetary rewards for their effort. Blockchains are, in principle, attractive targets for Denial-of-Service (DoS) attacks: There is fierce competition among coins, as well as potential gains from short selling. Classical DoS attacks, however, typically target a few servers and cannot scale to systems with many nodes. There have been no successful DoS attacks to date against prominent cryptocurrencies. We present Blockchain DoS (BDoS), the first incentive-based DoS attack that targets PoW cryptocurrencies. Unlike classical DoS, BDoS targets the system's mechanism design: It exploits the reward mechanism to discourage miner participation. Previous DoS attacks against PoW blockchains require an adversary's mining power to match that of all other miners. In contrast, BDoS can cause a blockchain to grind to a halt with significantly fewer resources, e.g., 21% as of March 2020 in Bitcoin, according to our empirical study. We find that Bitcoin's vulnerability to BDoS increases rapidly as the mining industry matures and profitability drops. BDoS differs from known attacks like Selfish Mining in its aim not to increase an adversary's revenue, but to disrupt the system. Although it bears some algorithmic similarity to those attacks, it introduces a new adversarial model, goals, algorithm, and game-theoretic analysis. Beyond its direct implications for operational blockchains, BDoS introduces the novel idea that an adversary can manipulate miners' incentives by proving the existence of blocks without actually publishing them.

Blockchains such as Bitcoin and Ethereum execute payment transactions securely, but their performance is limited by the need for global consensus. Payment networks overcome this limitation through off-chain transactions. Instead of writing to the blockchain for each transaction, they only settle the final payment balances with the underlying blockchain. When executing off-chain transactions in current payment networks, parties must access the blockchain within bounded time to detect misbehaving parties that deviate from the protocol. This opens a window for attacks in which a malicious party can steal funds by deliberately delaying other parties' blockchain access and prevents parties from using payment networks when disconnected from the blockchain.

Blockchain-based cryptocurrencies secure a decentralized consensus protocol by incentives. The protocol participants, called miners, generate (mine) a series of blocks, each containing monetary transactions created by system users. As incentive for participation, miners receive newly minted currency and transaction fees paid by transaction creators. Blockchain bandwidth limits lead users to pay increasing fees in order to prioritize their transactions. However, most prior work focused on models where fees are negligible. In a notable exception, Carlsten et al. [17] postulated that if incentives come only from fees then a mining gap would form~--- miners would avoid mining when the available fees are insufficient. In this work, we analyze cryptocurrency security in realistic settings, taking into account all elements of expenses and rewards. To study when gaps form, we analyze the system as a game we call the gap game. We analyze the game with a combination of symbolic and numeric analysis tools in a wide range of scenarios. Our analysis confirms Carlsten et al.'s postulate; indeed, we show that gaps form well before fees are the only incentive, and analyze the implications on security. Perhaps surprisingly, we show that different miners choose different gap sizes to optimize their utility, even when their operating costs are identical. Alarmingly, we see that the system incentivizes large miner coalitions, reducing system decentralization. We describe the required conditions to avoid the incentive misalignment, providing guidelines for future cryptocurrency design.

No abstract available.

No abstract available.

Read-only caches are widely used in cloud infrastructures to reduce access latency and load on backend databases. Operators view coherent caches as impractical at genuinely large scale and many client-facing caches are updated asynchronously with best-effort pipelines. Existing solutions that support cache consistency are inapplicable to this scenario since they require a round trip to the database on every cache transaction. Existing incoherent cache technologies are oblivious to transactional data access, even if the backend database supports transactions. We propose T-Cache, a novel caching policy for read-only transactions in which inconsistency is tolerable (won't cause safety violations) but undesirable (has a cost). T-Cache improves cache consistency despite asynchronous and unreliable communication between the cache and the database. We define cache-serializability, a variant of serializability that is suitable for incoherent caches, and prove that with unbounded resources T-Cache implements this new specification. With limited resources, T-Cache allows the system manager to choose a trade-off between performance and consistency. Our evaluation shows that T-Cache detects many inconsistencies with only nominal overhead. We use synthetic workloads to demonstrate the efficacy of T-Cache when data accesses are clustered and its adaptive reaction to workload changes. With workloads based on the real-world topologies, T-Cache detects 43 -- 70% of the inconsistencies and increases the rate of consistent transactions by 33 -- 58%.

An open distributed system can be secured by requiring participants to present proof of work and rewarding them for participation. The Bit coin digital currency introduced this mechanism, which is adopted by almost all contemporary digital currencies and related services. A natural process leads participants of such systems to form pools, where members aggregate their power and share the rewards. Experience with Bit coin shows that the largest pools are often open, allowing anyone to join. It has long been known that a member can sabotage an open pool by seemingly joining it but never sharing its proofs of work. The pool shares its revenue with the attacker, and so each of its participants earns less. We define and analyze a game where pools use some of their participants to infiltrate other pools and perform such an attack. With any number of pools, no-pool-attacks is not a Nash equilibrium. We study the special cases where either two pools or any number of identical pools play the game and the rest of the participants are uninvolved. In both of these cases there exists an equilibrium that constitutes a tragedy of the commons where the participating pools attack one another and earn less than they would have if none had attacked. For two pools, the decision whether or not to attack is the miner's dilemma, an instance of the iterative prisoner's dilemma. The game is played daily by the active Bit coin pools, which apparently choose not to attack. If this balance breaks, the revenue of open pools might diminish, making them unattractive to participants.

A key-value store (KVS) offers functions for storing and retrieving values associated with unique keys. KVSs have become the most popular way to access Internet-scale “cloud” storage systems. We present an efficient wait-free algorithm that emulates multi-reader multi-writer storage from a set of potentially faulty KVS replicas in an asynchronous environment. Our implementation serves an unbounded number of clients that use the storage concurrently. It tolerates crashes of a minority of the KVSs and crashes of any number of clients. Our algorithm minimizes the space overhead at the KVSs and comes in two variants providing regular and atomic semantics, respectively. Compared with prior solutions, it is inherently scalable and allows clients to write concurrently. Because of the limited interface of a KVS, textbook-style solutions for reliable storage either do not work or incur a prohibitively large storage overhead. Our algorithm maintains two copies of the stored value per KVS in the common case, and we show that this is indeed necessary. If there are concurrent write operations, the maximum space complexity of the algorithm grows in proportion to the point contention. A series of simulations explore the behavior of the algorithm, and benchmarks obtained with KVS cloud-storage providers demonstrate its practicality.

A key-value store (KVS) offers functions for storing and retrieving values associated with unique keys. KVSs have become widely used as shared storage solutions for Internet-scale distributed applications.

Low overhead analysis of large distributed data sets is necessary for current data centers and for future sensor networks. In such systems, each node holds some data value, e.g., a local sensor read, and a concise picture of the global system state needs to be obtained. In resource-constrained environments like sensor networks, this needs to be done without collecting all the data at any location, i.e., in a distributed, manner. To this end, we define the distributed classification problem, in which numerous interconnected nodes compute a classification of their data, i.e., partition these values into multiple collections, and describe each collection concisely.