An official website of the United States government
A proof of work (PoW) is an important cryptographic construct enabling a party to convince others that they invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure and thus the problem of interest is the feasibility of obtaining a sequence (chain) of such proofs. In this work, we examine the hardness of finding such chain of PoWs against quantum strategies. We prove that the chain of PoWs problem reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. Effectively, this is an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the recording technique of Zhandry (Crypto'19). As an application, we revisit the formal treatment of security of the core of the Bitcoin consensus protocol, the Bitcoin backbone (Eurocrypt'15), against quantum adversaries, while honest parties are classical and show that protocol's security holds under a quantum analogue of the classical “honest majority'' assumption. Our analysis indicates that the security of Bitcoin backbone is guaranteed provided the number of adversarial quantum queries is bounded so that each quantum query is worth O ( p − 1 / 2 ) classical ones, where p is the success probability of a single classical query to the protocol's underlying hash function. Somewhat surprisingly, the wait time for safe settlement in the case of quantum adversaries matches the safe settlement time in the classical case.
more »
« less
The Bitcoin Backbone Protocol: Analysis and Applications
Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoinbackbone, and prove three of its fundamental properties which we callCommon Prefix,Chain Quality,andChain Growthin the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the protocol participants and their interplay with the protocol parameters and the time needed for reliable message passing between honest parties in terms of computational steps. A takeaway from our analysis is that, all else being equal, the protocol’s provable tolerance in terms of the number of adversarial parties (or, equivalently, their “hashing power” in our model) decreases as the duration of a message passing round increases. Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that a proposal due to Nakamoto falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion, we describe and analyze the Bitcoin system as well as a more elaborate BA protocol and we prove them secure assuming the adversary’s hashing power is strictly less than 1/2. Instrumental to this latter result is a technique we call2-for-1 proof-of-work(PoW) that has proven to be useful in the design of other PoW-based protocols.
more »
« less
- Award ID(s):
- 2055694
- PAR ID:
- 10591196
- Publisher / Repository:
- Journal of the ACM
- Date Published:
- Journal Name:
- Journal of the ACM
- Volume:
- 71
- Issue:
- 4
- ISSN:
- 0004-5411
- Page Range / eLocation ID:
- 1 to 49
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Cryptocurrency software implements the cryptocurrency operations. We design a software assurance scheme for cryptocurrency and advance the cryptocurrency handshaking protocol. More specifically, we focus on Bitcoin for implementation and integration and advance its Version-message based hand-shaking and thus call our scheme Version++, The Version++ protocol provides software assurance, which is distinguishable from the previous research because it is permissionless, distributed, and lightweight to fit its cryptocurrency application. Utilizing Merkle Tree for the verification efficiency, we implement and test Version++ on Bitcoin software and conduct experiments in an active Bitcoin node prototype connected to the Bitcoin Mainnet. This paper for the conference demonstration supplements our technical paper at CCNC 2023 for synergy but highlights the prototyping and demonstration components of our research.more » « less
-
Cryptocurrency software implements the cryptocurrency operations, including the distributed consensus protocol and the peer-to-peer networking. We design a software assurance scheme for cryptocurrency and advance the cryptocurrency handshaking protocol. Since we focus on Bitcoin (the most popular cryptocurrency) for implementation and integration, we call our scheme Version++, built on and advancing the current Bitcoin handshaking protocol based on the Version message. Our Version++ protocol providing software assurance is distinguishable from the previous research because it is permissionless, distributed, and lightweight to fit its cryptocurrency application. Our scheme is permissionless since it does not require a centralized trusted authority (unlike the remote software attestation techniques from trusted computing); it is distributed since the peer checks the software assurances of its own peer connections; and it is designed for efficiency/lightweight due to the dynamic nature of the peer connections and the large-scale broadcasting in cryptocurrency networking. Utilizing Merkle Tree for the efficiency of the proof verification, we implement and test Version++ on Bitcoin software and conduct experiments in an active Bitcoin node prototype connected to the Bitcoin Mainnet. Our prototype-based performance analyses demonstrate the lightweight design of Version++. The peer-specific verification grows logarithmically with the number of software files in processing time and in storage. In addition, the Version++ verification overhead is small compared to the overall handshaking process; our measured overhead of 2.22% with minimal networking latency between the virtual machines provides an upper bound in the real-world networking with greater handshaking duration, i.e., the relative Version++ overhead in the real world with physically separate machines will be smaller.more » « less
-
Bitcoin, Ethereum and other blockchain-based cryptocurrencies, as deployed today, cannot support more than several transactions per second. Off-chain payment channels, a “layer 2” solution, are a leading approach for cryptocurrency scaling. They enable two mutually distrustful parties to rapidly send payments between each other and can be linked together to form a payment network, such that payments between any two parties can be routed through the network along a path that connects them. We propose a novel payment channel protocol, called Sprites. The main advantage of Sprites compared with earlier protocols is a reduced “collateral cost,” meaning the amount of money × time that must be locked up before disputes are settled. In the Lightning Network and Raiden, a payment across a path of ` channels requires locking up collateral for Θ(`∆) time, where ∆ is the time to commit an on-chain transaction; every additional node on the path forces an increase in lock time. The Sprites construction provides a constant lock time, reducing the overall collateral cost to Θ(` + ∆). Our presentation of the Sprites protocol is also modular, making use of a generic state channel abstraction. Finally, Sprites improves on prior payment channel constructions by supporting partial withdrawals and deposits without any on-chain transactions.more » « less
-
null (Ed.)The value of cryptocurrencies is highly volatile and investors require fast and reliable exchange systems. In cross-chain transactions, multiple parties exchange assets across multiple blockchains which can be represented as a directed graph with vertexes V as parties and edges E as asset transfers. In a simple form, cross-chain transactions are cross-chain swaps where each edge e transfers an asset that the head of e already owns. However, in general, a cross-chain transaction includes a sequence of exchanges at each blockchain. Further, transactions may have off-chain steps and hence may not be strongly connected. Given a transaction, protocols are desired that guarantee the following property called uniformity. If all parties conform to the protocol, all the assets should be transferred. Further, if any party deviates from the protocol, the conforming parties should not experience any loss. Previous work introduced a uniform protocol for strongly connected cross-chain swaps and showed that no uniform protocol exists for transactions that are not strongly connected. We present a uniform protocol for general cross-chain transactions with sequenced and off-chain steps when a few certain parties are conforming. Further, we prove a new property called end-to-end that guarantees that if the source parties pay, the sink parties are paid. We present a synthesis tool called XCHAIN that given a high-level description of a cross-transaction can automatically generate smart contracts in Solidity for all the parties.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3653445
