What a lovely hat

The GHOST protocol has been proposed as an improvement to the Nakamoto consensus mechanism that underlies Bitcoin. In contrast to the Nakamoto fork-choice rule, the GHOST rule justifies selection of a chain with weights computed over subtrees rather than individual paths. This mechanism has been adopted by a variety of consensus protocols, and is a part of the currently deployed protocol supporting Ethereum. We establish an exact characterization of the security region of the GHOST...

As the first proof-of-work (PoW) permissionless blockchain, Bitcoin aims at maintaining a decentralized yet consistent transaction ledger as protocol participants (“miners”) join and leave as they please. This is achieved by means of a subtle PoW difficulty adjustment mechanism that adapts to the perceived block generation rate, and important steps have been taken in previous work to provide a rigorous analysis of the conditions (such as bounds on dynamic participation) that are sufficient...

We study selfish mining attacks in longest-chain blockchains like Bitcoin, but where the proof of work is replaced with efficient proof systems -- like proofs of stake or proofs of space -- and consider the problem of computing an optimal selfish mining attack which maximizes expected relative revenue of the adversary, thus minimizing the chain quality. To this end, we propose a novel selfish mining attack that aims to maximize this objective and formally model the attack as a Markov...

Designing light clients for Proof-of-Work blockchains has been a foundational problem since Nakamoto's SPV construction in the Bitcoin paper. Over the years, communication was reduced from O(C) down to O(polylog(C)) in the system's lifetime C. We present Blink, the first provably secure O(1) light client that does not require a trusted setup.

In recent years, many blockchain systems have progressively transitioned to proof-of-stake (PoS) con- sensus algorithms. These algorithms are not only more energy efficient than proof-of-work but are also well-studied and widely accepted within the community. However, PoS systems are susceptible to a particularly powerful "long-range" attack, where an adversary can corrupt the validator set retroactively and present forked versions of the blockchain. These versions would still be acceptable...

We investigate the feasibility of permissionless consensus (aka Byzantine agreement) under standard assumptions. A number of protocols have been proposed to achieve permissionless consensus, most notably based on the Bitcoin protocol; however, to date no protocol is known that can be provably instantiated outside of the random oracle model. In this work, we take the first steps towards achieving permissionless consensus in the standard model. In particular, we demonstrate that worst-case...

It has been shown that the selfish mining attack enables a miner to achieve an unfair relative revenue, posing a threat to the progress of longest-chain blockchains. Although selfish mining is a well-studied attack in the context of Proof-of-Work blockchains, its impact on the longest-chain Proof-of-Stake (LC-PoS) protocols needs yet to be addressed. This paper involves both theoretical and implementation-based approaches to analyze the selfish proposing attack in the LC-PoS protocols. We...

The use of MPC-in-the-Head (MPCitH)-based zero-knowledge proofs of knowledge (ZKPoK) to prove knowledge of a preimage of a one-way function (OWF) is a popular approach towards constructing efficient post-quantum digital signatures. Starting with the Picnic signature scheme, many optimized MPCitH signatures using a variety of (candidate) OWFs have been proposed. Recently, Baum et al. (CRYPTO 2023) showed a fundamental improvement to MPCitH, called VOLE-in-the-Head (VOLEitH), which can...

We propose a modification to the fork choice rule of proof-of-work blockchains. Instead of choosing the heaviest chain, we choose the chain with the most intrinsic work. The intrinsic work of a block is roughly the number of zeroes at the front of its hash. This modification allows us to safely speed up the protocol, yielding a roughly 40% improvement in confirmation delay as compared to Bitcoin for adversaries close to 10%. Our modification is at the level of the proof-of-work inequality,...

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the...

In the traditional consensus problem (aka Byzantine agreement), parties are required to agree on a common value despite the malicious behavior of some of them, subject to the condition that if all the honest parties start the execution with the same value, then that should be the outcome. This problem has been extensively studied by both the distributed computing and cryptographic protocols communities. With the advent of blockchains, whose main application—a distributed ledger—essentially...

When Satoshi Nakamoto introduced Bitcoin, a central tenet was that the blockchain functions as a timestamping server. In the Ethereum era, smart contracts widely assume on-chain timestamps are mostly accurate. In this paper, we prove this is indeed the case, namely that recorded timestamps do not wildly deviate from real-world time, a property we call timeliness. Assuming a global clock, we prove that all popular mechanisms for constructing blockchains (proof-of-work, longest chain...

The proof of stake (PoS) mechanism, which allows stakeholders to issue a block with a probability proportional to their wealth instead of computational power, is believed to be an energy-efficient alternative to the proof of work (PoW). The privacy concern of PoS, however, is more subtle than that of PoW. Recent research has shown that current anonymous PoS (APoS) protocols do not suffice to protect the stakeholder's identity and stake, and the loss of privacy is theoretically inherent for...

Proof-of-work (PoW) blockchain protocols based on directed acyclic graphs (DAGs) have demonstrated superior transaction confirmation performance compared to their chain-based predecessors. However, it is uncertain whether their security deteriorates in high-throughput settings similar to their predecessors, because their acceptance of simultaneous blocks and complex block dependencies presents challenges for rigorous security analysis. We address these challenges by analyzing DAG-based...

Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A recent approach utilizes the training process of deep learning as ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal...

SNACKs are succinct non-interactive arguments of chain knowledge. They allow for efficient and generic solutions to blockchain light-client bootstrapping. Abusalah et al. construct SNACKs in the random oracle model for any \emph{single-chain} blockchain from any graph-labeling proof of sequential work (PoSW) scheme. Their SNACK construction is a PoSW-like protocol over the augmented blockchain. Unlike single-chain blockchains, such as proof-of-work and proof-of-stake blockchains,...

With the emergence of Miner Extractable Value (MEV), block construction markets on blockchains have evolved into a competitive arena. Following Ethereum's transition from Proof of Work (PoW) to Proof of Stake (PoS), the Proposer Builder Separation (PBS) mechanism has emerged as the dominant force in the Ethereum block construction market. This paper presents an in-depth longitudinal study of the Ethereum block construction market, spanning from the introduction of PoS and PBS in September...

The MPC in the Head (MPCitH) paradigm has recently led to significant improvements for signatures in the code-based setting. In this paper we consider some modifications to a recent twist of MPCitH, called Hypercube-MPCitH, that in the code-based setting provides the currently best known signature sizes. By compressing the Hypercube-MPCitH five-round code-based identification scheme into three-rounds we obtain two main benefits. On the one hand, it allows us to further develop recent...

Cryptocurrencies and decentralized platforms have been rapidly gaining traction since Nakamoto's discovery of Bitcoin's blockchain protocol. Prominent systems use Proof of Work (PoW) to achieve unprecedented security for digital assets. However, the significant carbon footprint due to the manufacturing and operation of PoW mining hardware is leading policymakers to consider stark measures against them and various systems to explore alternatives. But these alternatives imply stepping away...

For Nakamoto's longest-chain consensus protocol, whose proof-of-work (PoW) and proof-of-stake (PoS) variants power major blockchains such as Bitcoin and Cardano, we revisit the classic problem of the security--performance tradeoff: Given a network of nodes with finite communication- and computation-resources, against what fraction of adversary power is Nakamoto consensus (NC) secure for a given block production rate? State-of-the-art analyses of NC fail to answer this question, because their...

Blockchain consensus algorithms for cryptocurrency consist of the proof of work and proof of stake. However, current algorithms have problems, such as huge power consumption and equality issues. We propose a new consensus algorithm that uses transaction history. This algorithm ensures equality by randomly assigning approval votes based on past transaction records. We also incorporate a mechanism for adjusting issuance volume to measure the stability of the currency's value.

We propose a single-tiered hybrid Proof-of-Work consensus protocol to encourage decentralization in bitcoin. Our new mechanism comprises coupled puzzles of which properties differ from each other; the one is the extant outsourceable bitcoin puzzle while the other is non-outsourceable. Our new protocol enables miners to solve either puzzle as they want; therefore, blocks can be generated by either puzzle. Our hybrid consensus can be successfully implemented in bitcoin, because it is...

Nakamoto's longest-chain consensus paradigm now powers the bulk of the world's cryptocurrencies and distributed finance infrastructure. An emblematic property of longest-chain consensus is that it provides probabilistic settlement guarantees that strengthen over time. This makes the exact relationship between settlement error and settlement latency a critical aspect of the protocol that both users and system designers must understand to make informed decisions. A recent line of work has...

A double auction system, where buyers and sellers trade through bids, requires a transparent and immutable mechanism to record allocation results. This demand can be met with robust ledgers that ensure persistence and liveness, as exemplified by the Bitcoin blockchain (EuroCrypt '15). While existing blockchain-aided auction systems often rely on secure smart contracts or layer-$2$ techniques, this work proposes a more fundamental approach by constructing a provably secure blockchain protocol...

The proof of work mechanism by which many blockchain-based protocols achieve consensus may be undermined by the use of quantum computing in mining—even when all cryptographic primitives are replaced with post-quantum secure alternatives. First, we offer an impossibility result: we prove that quantum (Grover) speedups in solving a large, natural class of proof-of-work puzzles cause an inevitable incentive incompatibility in mining, by distorting the reward structure of mining in...

Cryptocurrencies have become tremendously popular since the creation of Bitcoin. However, its central Proof-of-Work consensus mechanism is very power hungry. As an alternative, Proof-of-Space (PoS) was introduced that uses storage instead of computations to create a consensus. However, current PoS implementations are complex and sensitive to the Nothing-at-Stake problem, and use mitigations that affect their permissionless and decentralised nature. We introduce Proof-of-Space Search...

The permissionless clock synchronization problem asks how it is possible for a population of parties to maintain a system-wide synchronized clock, while their participation rate fluctuates --- possibly very widely --- over time. The underlying assumption is that parties experience the passage of time with roughly the same speed, but however they may disengage and engage with the protocol following arbitrary (and even chosen adversarially) participation patterns. This (classical) problem has...

We present an attack on Ethereum's consensus mechanism which can be used by miners to obtain consistently higher mining rewards compared to the honest protocol. This attack is novel in that it does not entail withholding blocks or any behavior which has a non-zero probability of earning less than mining honestly, in contrast with the existing literature. This risk-less attack relies instead on manipulating block timestamps, and carefully choosing whether and when to do so. We present...

In this work, we study the blockchain leader election problem. The purpose of such protocols is to elect a leader who decides on the next block to be appended to the blockchain, for each block proposal round. Solutions to this problem are vital for the security of blockchain systems. We introduce an efficient blockchain leader election method with security based solely on standard assumptions for cryptographic hash functions (rather than public-key cryptographic assumptions) and that does...

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners. Proof-of-Stake chains are energy-efficient, have fast finality but face several security issues: susceptibility to non-slashable long-range safety attacks, low liveness resilience and difficulty to bootstrap from low token valuation. We show that these security issues are inherent in any PoS chain without an external trusted source, and propose a new protocol, Babylon, where...

Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product...

Byzantine agreement (BA) is a fundamental primitive in distributed systems and has received huge interest as an important building block for blockchain systems. Classical byzantine agreement considers a setting where $n$ parties with fixed, known identities want to agree on an output in the presence of an adversary. Motivated by blockchain systems, the assumption of fixed identities is weakened by using a \emph{resource-based model}. In such models, parties do not have fixed known identities...

Blockchain and distributed ledger technologies have emerged as one of the most revolutionary distributed systems, with the goal of eliminating centralised intermediaries and installing distributed trusted services. They facilitate trustworthy trades and exchanges over the Internet, power cryptocurrencies, ensure transparency for documents, and much more. Committee based-blockchains are considered today as a viable alternative to the original proof-of-work paradigm, since they offer strong...

At ASIACRYPT 2012, Sasaki et al. introduced the guess-and-determine approach to extend the meet-in-the-middle (MITM) preimage attack. At CRYPTO 2021, Dong et al. proposed a technique to derive the solution spaces of nonlinear constrained neutral words in the MITM preimage attack. In this paper, we try to combine these two techniques to further improve the MITM preimage attacks. Based on the previous MILP-based automatic tools for MITM attacks, we introduce new constraints due to the...

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world...

In this work, we study and formalize security notions for algorithm substitution attacks (ASAs) on em cryptographic puzzles. Puzzles are difficult problems that require an investment of computation, memory, or some other related resource. They are heavily used as a building block for the consensus networks used by cryptocurrencies. These include primitives such as proof-of-work, proof-of-space, and verifiable delay functions (VDFs). Due to economies of scale, these networks increasingly rely...

Blockchain ``on-chain'' oracles are critical to the functioning of many Decentralized Finance (DeFi) protocols. We analyze these oracles for manipulation resistance. Specifically, we analyze the cost of manipulating on-chain time-weighted average price (TWAP) oracles that use the arithmetic mean. It has been assumed that manipulating a TWAP oracle with the well-known multi-block attack is expensive and scales linearly with the length of the TWAP. We question this assumption with two novel...

Proof-of-Stake (PoS) algorithms, implemented as foundational components of the consensus mechanism of distributed ledgers, are defective cryptosystems by nature. This paper presents intuitive arguments for why PoS, by trying to improve the energy efficiency of Proof-of-Work (PoW) when implemented as a Sybil control mechanism in distributed ledgers, introduces a set of significant new flaws. Such systems are plutocratic, oligopolistic, and permissioned.

The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover $P^*(x)$ on some theorem $x$, is able to produce a witness $w$ for $x$ with roughly the same probability that $P^*$ produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable...

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...

Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is...

Bitcoin is the most secure blockchain in the world, supported by the immense hash power of its Proof-of-Work miners, but consumes huge amount of energy. Proof-of-Stake chains are energy-efficient, have fast finality and accountability, but face several fundamental security issues: susceptibility to non-slashable long-range safety attacks, non-slashable transaction censorship and stalling attacks and difficulty to bootstrap new PoS chains from low token valuation. We propose Babylon, a...

Blockchain technology has the potential of transforming cryptography. We study the problem of round-complexity of zero-knowledge, and more broadly, of secure computation in the blockchain-hybrid model, where all parties can access the blockchain as an oracle. We study zero-knowledge and secure computation through the lens of a new security notion where the simulator is given the ability to ``time-travel” or more accurately, to look into the future states of the blockchain and use this...

We show that Bitcoin and other existing egalitarian crypto-currencies are unstable as store-of-value as they fail to track inflation of local currencies closely, and the price dynamic is purely driven by speculation. In the case of Bitcoin, we show that instead of price being based on cost of mining Bitcoin, it is the cost of mining that rapidly converges to the current price of Bitcoin. Based on rational expectations equilibrium, we argue that if the coins awarded during mining are...

Consider some user buying software or hardware from a provider. The provider claims to have subjected this product to a number of tests, ensuring that the system operates nominally. How can the user check this claim without running all the tests anew? The problem is similar to checking a mathematical conjecture. Many authors report having checked a conjecture $C(x)=\mbox{True}$ for all $x$ in some large set or interval $U$. How can mathematicians challenge this claim without performing all...

Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for...

Minimizing the energy cost and carbon footprint of the Bitcoin blockchain and related protocols is one of the most widely identified open questions in the cryptocurrency space. Substituting the proof-of-work (PoW) primitive in Nakamoto's longest chain protocol with a {\em proof of useful work} (PoUW) has been long theorized as an ideal solution in many respects but, to this day, the concept still lacks a convincingly secure realization. In this work we put forth Ofelimos, a novel PoUW-based...

With the advent of the Internet of Things (IoT), e-health has become one of the main topics of research. Due to the sensitivity of patient information, patient privacy seems challenging. Nowadays, patient data is usually stored in the cloud in healthcare programs, making it difficult for users to have enough control over their data. The recent increment in announced cases of security and surveillance breaches compromising patients' privacy call into question the conventional model, in which...

Due to the enormous energy consuming involved in the proof of work (POW) process, the resource-efficient blockchain system is urged to be released. The verifiable delay function (VDF), being slow to compute and easy to verify, is believed to be the kernel function of the next-generation blockchain system. In general, the reduction over a class group, involving many complex operations, such as the large-number division and multiplication operations, takes a large portion in the VDF. In this...

Stake-based multiparty cryptographic primitives operate in a setting where participants are associated with their stake, security is argued against an adversary that is bounded by the total stake it possesses —as opposed to number of parties— and we are interested in scalability, i.e., the complexity of critical operations depends only logarithmically in the number of participants (who are assumed to be numerous). In this work we put forth a new stake-based primitive, stake-based...

Game-theoretic analyses of cryptocurrencies and---more generally---blockchain-based decentralized ledgers offer insight on their economic robustness and behavior when even their underpinning cryptographic assumptions fail. In this work we utilize the recently proposed blockchain adaptation of the rational protocol design (RPD) framework [EUROCRYPT '18] to analyze 51% double-spending attacks against Nakamoto-style proof-of-work based cryptocurrencies. We first observe a property of the...

Nakamoto proof-of-work ledger consensus currently underlies the majority of deployed cryptocurrencies and smart-contract blockchains. While a long and fruitful line of work studying the provable security guarantees of this mechanism has succeeded to identify its exact security region---that is, the set of parametrizations under which it possesses asymptotic security---the existing theory does not provide concrete settlement time guarantees that are tight enough to inform practice. In...

Proof-of-Stake (PoS) distributed ledgers are the most common alternative to Bitcoin’s Proof-of-Work (PoW) paradigm, replacing the hardware dependency with stake, i.e., assets that a party controls. Similar to PoW’s mining pools, PoS’s stake pools, i.e., collaborative entities comprising of multiple stakeholders, allow a party to earn rewards more regularly, compared to participating on an individual basis. However, stake pools tend to increase centralization, since they are typically managed...

We put forth a keyless wallet, a cryptocurrency wallet in which money can be spent using a password alone, and no private keys are required. It requires a smart contract blockchain. We propose two schemes. In the first, the user sets a short wallet password and can spend their money at a prespecified maturity date using the password alone. Using this as a stepping stone, we propose a second scheme, in which the user uses an OTP authenticator seed to generate a long series of time-based OTP...

Blockchains maintain two types of data: Application data and consensus data. Towards long-term blockchain scalability, both of these must be pruned. While a large body of literature has explored the pruning of application data (UTXOs, account balances, and contract state), little has been said about the permanent pruning of consensus data (block headers). We present a protocol which allows pruning the blockchain by garbage collecting old blocks as they become unnecessary. These blocks can...

Several emerging proof-of-work (PoW) blockchain protocols rely on a “parallel-chain” architecture for scaling, where instead of a single chain, multiple chains are run in parallel and aggregated. A key requirement of practical PoW blockchains is to adapt to mining power variations over time (Bitcoin’s total mining power has increased by a $10^{14}$ factor over the decade). In this paper, we consider the design of provably secure parallel-chain protocols which can adapt to such mining power...

Macroeconomic policy in a blockchain system concerns the algorithm that decides the payment schedule for miners and thus its money mint rate. It governs the amounts, distributions, beneficiaries and conditions required for money supply payments to participants by the system. While most chains today employ simple policies such as a constant amount per block, several cryptocurrencies have sprung up that put forth more interesting policies. As blockchains become a more popular form of money,...

Blockchain technologies have received a great amount of attention, and its immutability is paramount to facilitate certain applications requiring persistent records. However, in many other use-cases, tremendous real-world incidents have exposed the harm of strict immutability. For example, illicit data stored in immutable blockchain poses numerous challenges for law enforcement agencies such as Interpol, and millions of dollars are lost due to the vulnerabilities of immutable smart contract....

Bitcoin Cash, created in 2017, is a “hard fork” from Bitcoin responding to the need for allowing a higher transaction volume. This is achieved by a larger block size, as well as a new difficulty adjustment (target recalculation) function(s) that acts more frequently (as opposed to Bitcoin’s difficulty adjustment happening about every two weeks), resulting in a potentially different target for each block. While seemingly achieving its goal in practice, to our knowledge there is no formal...

Over the past five years, a significant line of research has investigated the blockchain consensus problem in the general permissionless setting, where protocol nodes can leave and join dynamically. The work of Garay et al. (Eurocrypt 2015) and Pass et al. (Eurocrypt 2017) showed the security properties of consistency and liveness for Nakamoto's seminal proof-of-work protocol. However, consistency and liveness do not provide any guarantees on the relationship between the order in which...

Proof of Elapsed Time (PoET) is a Nakamoto-style consensus algorithm where proof of work is replaced by a wait time randomly generated by a trusted execution environment (TEE). PoET was originally developed by Intel engineers and contributed to Hyperledger Sawtooth, but has never been formally defined or analyzed. In particular, PoET enables consensus on a bitcoin-like scale without having to resort to mining. Proof of Luck (PoL), designed by Milutinovic et. al., is a similar (but not...

The security of PoW-based blockchains relies on the total amount of mining power and the ratio of mining power possessed by the honest miners. Loosely speaking, a system with higher mining power makes an attack more difficult. To incentivise miners joining the network and contributing their mining power, reward mechanisms are designed to provide economic profit to miners in exchange for their mining power. We identify shutdown price of mining machines as an overlooked factor that has an...

Most state machine replication protocols are either based on the 40-years-old Byzantine Fault Tolerance (BFT) theory or the more recent Nakamoto’s longest chain design. Longest chain protocols, designed originally in the Proof-of-Work (PoW) setting, are available under dynamic participation, but has probabilistic confirmation with long latency dependent on the security parameter. BFT protocols, designed for the permissioned setting, has fast deterministic confirmation, but assume a fixed...

Bitcoin is a blockchain whose immutability relies on Proof-of-Work: Before appending a new block, some so-called miner has to solve a cryptographic challenge by brute force. The blockchain is spread over a network of faithful miners, whose cumulated computing power is assumed to be so large that, among other things, it should be too expensive for an attacker to mine a secret fork $n$ blocks longer than the main blockchain, provided that $n$ is big enough. For a given targeted advance of $n$...

Proof of Work (PoW) protocols, originally proposed to circumvent DoS and email spam attacks, are now at the heart of the majority of recent cryptocurrencies. Current popular PoW protocols are based on hash puzzles. These puzzles are solved via a brute force search for a hash output with particular properties, such as a certain number of leading zeros. By considering the hash as a random function, and fixing a priori a sufficiently large search space, Grover's search algorithm gives an...

Selfish mining (SM) attack of Eyal and Sirer (2018) endangers permissionless Proof-of-Work blockchains by allowing a rational mining pool with a hash power (a) much less than 50% of the whole network to deviate from the honest mining algorithm and to steal from the fair shares of honest miners. Since then, the attack has been studied extensively in various settings, for understanding its interesting dynamics, optimizing it, and mitigating it. In this context, Heilman (14) ''Freshness...

Since its appearance in 2008, Bitcoin has attracted considerable attention. So far, it has been the most successful cryptocurrency, with the highest market capitalization. Nevertheless, due to the method it uses to append new transactions and blocks to the blockchain, based on a Proof-of-Work, Bitcoin suffers from poor scalability, which strongly limits the number of transactions per second and, hence, its adoption as a global payment layer for everyday uses. In this paper we analyze some...

Superlight blockchain clients learn facts about the blockchain state while requiring merely polylogarithmic communication in the total number of blocks. For proof-of-work blockchains, two known constructions exist: Superblock and FlyClient. Unfortunately, none of them can be easily deployed to existing blockchains, as they require consensus changes and at least a soft fork to implement. In this paper, we investigate how a blockchain can be upgraded to support superblock clients without a...

Blockchain is the distributed system allowing multiple parties to host a service. Nakamoto Consensus, also named Proof of Work (PoW), is widely used in Bitcoin and other blockchain systems. PoW is an important consensus algorithm. It solves the Byzantine Generals problem in an open network. It also protects the blockchain security from longest chain attack. World widely virtual currency mining was commonly regarded as over energy consuming. How to make use of the computation capacity...

First implemented in Bitcoin, Nakamoto Consensus (NC) is the most influential consensus protocol in cryptocurrencies despite all the alternative protocols designed afterward. Nevertheless, NC is trapped by a security-performance tradeoff. While existing efforts mostly attempt to break this tradeoff via abandoning or adjusting NC's backbone protocol, we alternatively forward the relevance of the network layer. We identify and experimentally prove that the crux resides with the prolonged block...

We propose RANDCHAIN, a Decentralised Randomness Beacon (DRB) that is the first to achieve both scalability (i.e., a large number of participants can join) and fairness (i.e., each participant controls comparable power on deciding random outputs). Unlike existing DRBs where participants are collaborative, i.e., aggregating their local entropy into a single output, participants in RANDCHAIN are competitive, i.e., competing with each other to generate the next output. The competitive design...

Distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints about the resources of an adversary relative to the resources of the nodes that follow the protocol. Given the intended long-livedness of these protocols, perhaps the most fundamental open security question currently is...

Superlight clients enable the verification of proof-of-work-based blockchains by checking only a small representative number of block headers instead of all the block headers as done in simplified payment verification (SPV). Such clients can be embedded within other blockchains by implementing them as smart contracts, allowing for cross-chain verification. One such interesting instance is the consumption of Bitcoin data within Ethereum by implementing a Bitcoin superlight client in Solidity....

Software updates for blockchain systems become a real challenge when they impact the underlying consensus mechanism. The activation of such changes might jeopardize the integrity of the blockchain by resulting in chain splits. Moreover, the software update process should be handed over to the community and this means that the blockchain should support updates without relying on a trusted party. In this paper, we introduce the notion of updatable blockchains and show how to construct...

A novel Nakamoto-like consensus was proposed by Tang et al. (ACISP 2019) to speed up the convergence (block finality) rate by determining a weight of a block in the blockchain by a tunable potential function of the block hash. However, the convergence of the scheme was evaluated only in an experimental way and a sudden utilization of another blockchain was not clearly explained. This article asymptotically analyses the convergence of Nakamoto-like consensus of Tang et al. by proposing a...

In proof-of-work based cryptocurrencies, miners invest computing power to maintain a distributed ledger. The drawback of such a consensus protocol is its immense energy consumption. Bitcoin, for example consumes as much energy as a small nation state. To prevent this waste of energy various consensus mechanism such as proof-of-space or proof-of-stake have been proposed. In proof-of-stake, block creators are selected based on the amounts of money they stake instead of their expanded...

Blockchain protocols based on variations of the longest-chain rule—whether following the proof-of-work paradigm or one of its alternatives—suffer from a fundamental latency barrier. This arises from the need to collect a sufficient number of blocks on top of a transaction-bearing block to guarantee the transaction’s stability while limiting the rate at which blocks can be created in order to prevent security-threatening forks. Our main result is a black-box security-amplifying combiner based...

We present LotMint, a permissionless blockchain, with a purposely low set bar for Proof-of-Work (PoW) difficulty. Our objective is for personal computers, cloud virtual machines or containers, even mobile devices, and hopefully future IoT devices, to become the main, widely distributed, collectively much securer, fairer, more reliable and economically sustainable mining workforce for blockchains. An immediate question arises: how to prevent the permissionless network from being flooded of...

We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Specifically, we prove that the protocol is secure if $$r_a < \frac{1}{\Delta + 1/r_h}\; ,$$ where $r_h$ is the expected number of honest proof-of-work successes in unit time, $r_a$ is the expected number of adversarial successes, and no message is delayed by more than $\Delta$ time units. In this regime, the protocol guarantees consistency and...

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a...

Today’s world is organized based on merit and value. A single global currency that’s decentralized is needed for a global economy. Bitcoin is a partial solution to this need, however it suffers from scalability problems which prevent it from being mass-adopted. Also, the deflationary nature of bitcoin motivates people to hoard and speculate on them instead of using them for day to day transactions. We propose a scalable, decentralized cryptocurrency that is based on Proof of Work. The...

Directed Acyclic Graph (DAG) is becoming an intriguing direction for distributed ledger structure due to its great potential in improving the scalability of distributed ledger systems. Among existing DAG-based ledgers, one promising category is transaction DAG, namely, treating each transaction as a graph vertex. In this paper, we propose Haootia, a novel two-layer framework of consensus, with a ledger in the form of a transaction DAG built on top of a delicately designed PoW-based backbone...

We facilitate trusted cross-blockchain state proofs by implementing a chain-relay that validates block headers from proof-of-work blockchains. While current approaches require proof sizes linear to the amount of blocks the state was built on, trusted intermediaries, or economic assumptions, we propose the utilization of off-chain computations through zkSNARKs to provide a cryptographically secure and highly scalable sidechain mechanism. Multiple block headers are included in batches and...

Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, these methods suffer from two main drawbacks. First, in a non-sharding blockchain, nodes can...

In the permissionless regime of distributed computing, participants may join and leave an internet-scale protocol execution at will. The permissionless regime poses challenges to the classical techniques used for consensus protocols, in which participants attempt to agree on a function of their inputs. For example, classical consensus techniques require bounding the numbers of honest and corrupt participants, and for honest participants to remain online throughout. Bitcoin's introduction of...

Proof of Work is a prevalent mechanism to prove investmentof time in blockchain projects. However the use of massive parallelismand specialized hardware gives an unfair advantage to a small portion ofnodes and raises environmental and economical concerns. In this paperwe provide an implementation study of two Verifiable Delay Functions, anew cryptographic primitive achieving Proof of Work goals in an unpar-allelizable way. We provide simulation results and an optimization basedon a...

We propose a framework for building Nakamoto-style proof-of-work blockchains where blocks are treated differently in the ``longest chain rule''. The crucial parameter is a weight function assigning different weights to blocks according to their hash value. Our framework enables the analysis of different weight functions while proving all statements at the appropriate level of abstraction. This allows us to quickly derive protocol guarantees for different weight functions. We exemplify the...

Nakamoto consensus, arguably the most exciting development in distributed computing in the last few years, is in a sense a recasting of the traditional state-machine-replication problem in an unauthenticated setting, where furthermore parties come and go without warning. The protocol relies on a cryptographic primitive known as proof of work (PoW) which is used to throttle message passing. Importantly, the PoW difficulty level is appropriately adjusted throughout the course of the protocol...

Blockchain-based payment systems utilize an append-only log of transactions whose correctness can be verified by any observer. In almost all of today’s implementations, verification costs grow linearly in either the number of transactions or blocks in the blockchain (often both). We propose a new distributed payment system which uses Incrementally Verifiable Computation (IVC) to enable constant-time verification. Since generating the succinct proofs needed to verify correctness is more...

Our work explores mechanisms that secure a distributed ledger in the presence of adversarial mining majorities. Distributed ledgers based on the Proof-of-Work (PoW) paradigm are typically most vulnerable when mining participation is low. During these periods an attacker can mount devastating attacks, such as double spending or censorship of transactions. We put forth the first rigorous study of checkpointing as a mechanism to protect distributed ledgers from such 51% attacks. The core idea...

The selfish mining attack allows cryptocurrency miners to mine more than their "fair share" of blocks, stealing revenue from other miners while reducing the overall security of payments. This malicious strategy has been extensively studied in Bitcoin, but far less attention has been paid to how the strategy may impact other cryptocurrencies. Because selfish mining is an attack against the difficulty adjustment algorithm (DAA) of a cryptocurrency, it may have a different effect when used...

Centralized pools and renting of mining power are considered as sources of possible censorship threats and even 51% attacks for decentralized cryptocurrencies. Non-outsourceable Proof-of-Work schemes have been proposed to tackle these issues. However, tenets in the folklore say that such schemes could potentially be bypassed by using escrow mechanisms. In this work, we propose a concrete example of such a mechanism which is using collateralized smart contracts. Our approach allows miners to...

There have been several 51% attacks on Proof-of-Work (PoW) blockchains recently, including Verge and GameCredits, but the most noteworthy has been the attack that saw hackers make off with up to $18 million after a successful double spend was executed on the Bitcoin Gold network. For this reason, the Proof-of-Stake (PoS) algorithm, which already has advantages of energy efficiency and throughput, is attracting attention as an alternative to the PoW algorithm. With a PoS, the attacker needs...

Blocks in proof-of-work (PoW) blockchains satisfy the PoW equation $H(B) \leq T$. If additionally a block satisfies $H(B) \leq T2^{-\mu}$, it is called a $\mu$-superblock. Superblocks play an important role in the construction of compact blockchain proofs which allows the compression of PoW blockchains into so-called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs). These certificates are essential for the construction of superlight clients, which are blockchain wallets that can...

The functioning of blockchain networks can be analyzed and abstracted into simple properties that allow for their usage as blackboxes in cryptographic protocols. One such abstraction is that of the growth of the blockchain over time. In this work, we build on the analysis of Garay et al. to develop an interface of functions that allow us to predict which block a submitted transaction will be added by. For cross-chain applications, we develop similar prediction functions for submitting...

This paper reports the results of survey done on the architecture and functionalities involved in blockchains. Moreover, it reports the results of comparison between proof-of-work-based blockchains, Bitcoin and Ethereum, against federated consensus-based blockchain, Ripple, and proof-of-validation-based blockchain, Tendermint, along the parameters like peer to peer network setup and maintenance, cryptocurrency involved, details of transaction execution and validation, block creation, block...

Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private correlated-randomness setup, such as a PKI, protocols can tolerate up to $t<n/3$ of the parties being malicious. The introduction of ``Nakamoto style'' consensus, based on Proof-of-Work (PoW) blockchains, put forth a somewhat different flavor of BA, showing that even a majority of corrupted parties can be tolerated as long as the majority of the ...

This paper applies biomimetic engineering to the problem of permissionless Byzantine consensus and achieves results that surpass the prior state of the art by four orders of magnitude. It introduces a biologically inspired asymmetric Sybil-resistance mechanism, Proof-of-Balance, which can replace symmetric Proof-of-Work and Proof-of-Stake weighting schemes. The biomimetic mechanism is incorporated into a permissionless blockchain protocol, Key Retroactivity Network Consensus (“KRNC”), which...

Proof-of-stake (PoS) blockchain protocols are emerging as one of the most promising alternative to the energy-consuming proof-of-work protocols. However, one particularly critical threat in the PoS setting is the well-known long-range attacks caused by secret key leakage (LRSL attack). Specifically, an adversary can attempt to corrupt the secret keys corresponding to accounts possessing substantial stake at some past moment such that double-spend or erase past transactions, violating the...

Honest majority is the key security assumption of Proof-of-Work (PoW) based blockchains. However, the recent 51% attacks render this assumption unrealistic in practice. In this paper, we challenge this assumption against rational miners in the PoW-based blockchains in reality. In particular, we show that the current incentive mechanism may encourage rational miners to launch 51% attacks in two cases. In the first case, we consider a miner of a stronger blockchain launches 51% attacks on a...