Iddo Bentov, Charles Lee, Alex Mizrahi, Meni Rosenfeld
We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity (PoA) protocol offers good security against possibly practical future attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. We explore various attack scenarios and suggest remedies to potential vulnerabilities of the PoA protocol, as well as evaluate the performance of its core subroutine. 1
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
Bitcoin is a peer-to-peer cryptographic currency system. Since its introduction in 2008, Bitcoin has gained noticeable popularity, mostly due to its following properties: (1) the transaction fees are very low, and (2) it is not controlled by any central authority, which in particular means that nobody can "print" the money to generate inflation. Moreover, the transaction syntax allows to create the so-called contracts, where a number of mutually-distrusting parties engage in a protocol to jointly perform some financial task, and the fairness of this process is guaranteed by the properties of Bitcoin. Although the Bitcoin contracts have several potential applications in the digital economy, so far they have not been widely used in real life. This is partly due to the fact that they are cumbersome to create and analyze, and hence risky to use. In this paper we propose to remedy this problem by using the methods originally developed for the computer-aided analysis for hardware and software systems, in particular those based on the timed automata. More concretely, we propose a framework for modeling the Bitcoin contracts using the timed automata in the UPPAAL model checker. Our method is general and can be used to model several contracts. As a proof-of-concept we use this framework to model some of the Bitcoin contracts from our recent previous work. We then automatically verify their security in UPPAAL, finding (and correcting) some subtle errors that were difficult to spot by the manual analysis. We hope that our work can draw the attention of the researchers working on formal modeling to the problem of the Bitcoin contract verification, and spark off more research on this topic.
In Bitcoin, transaction malleability describes the fact that the signatures that prove the ownership of bitcoins being transferred in a transaction do not provide any integrity guarantee for the signatures themselves. This allows an attacker to mount a malleability attack in which it intercepts, modifies, and rebroadcasts a transaction, causing the transaction issuer to believe that the original transaction was not confirmed. In February 2014 MtGox, once the largest Bitcoin exchange, closed and filed for bankruptcy claiming that attackers used malleability attacks to drain its accounts. In this work we use traces of the Bitcoin network for over a year preceding the filing to show that, while the problem is real, there was no widespread use of malleability attacks before the closure of MtGox.
We study a model of fairness in secure computation in which an adversarial party that aborts on receiving output is forced to pay a mutually predefined monetary penalty. We then show how the Bitcoin network can be used to achieve the above notion of fairness in the two-party as well as the multiparty setting (with a dishonest majority). In particular, we propose new ideal functionalities and protocols for fair secure computation and fair lottery in this model. One of our main contributions is the definition of an ideal primitive, which we call F?CR (CR stands for “claim-or-refund”), that formalizes and abstracts the exact properties we require from the Bitcoin network to achieve our goals. Naturally, this abstraction allows us to design fair protocols in a hybrid model in which parties have access to the F?CR functionality, and is otherwise independent of the Bitcoin ecosystem. We also show an efficient realization of F?CR that requires only two Bitcoin transactions to be made on the network. Our constructions also enjoy high efficiency. In a multiparty setting, our protocols only require a constant number of calls to F?CR per party on top of a standard multiparty secure computation protocol. Our fair multiparty lottery protocol improves over previous solutions which required a quadratic number of Bitcoin transactions.
Joseph Bonneau, Arvind Narayanan, Andrew Miller, Jeremy Clark · 6 authors
Abstract. We propose Mixcoin, a protocol to facilitate anonymous payments in Bitcoin and similar cryptocurrencies. We build on the emergent phenomenon of currency mixes, adding an accountability mechanism to expose theft. We demonstrate that incentives of mixes and clients can be aligned to ensure that rational mixes will not steal. Our scheme is efficient and fully compatible with Bitcoin. Against a passive attacker, our scheme provides an anonymity set of all other users mixing coins contemporaneously. This is an interesting new property with no clear analog in better-studied communication mixes. Against active attackers our scheme offers similar anonymity to traditional communication mixes. 1
Eli Ben‐Sasson, Alessandro Chiesa, Christina Garman, Matthew Green · 7 authors
Bit coin is the first digital currency to see widespread adoption. While payments are conducted between pseudonyms, Bit coin cannot offer strong privacy guarantees: payment transactions are recorded in a public decentralized ledger, from which much information can be deduced. Zero coin (Miers et al., IEEE S&P 2013) tackles some of these privacy issues by unlinking transactions from the payment's origin. Yet, it still reveals payments' destinations and amounts, and is limited in functionality. In this paper, we construct a full-fledged ledger-based digital currency with strong privacy guarantees. Our results leverage recent advances in zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs). First, we formulate and construct decentralized anonymous payment schemes (DAP schemes). A DAP scheme enables users to directly pay each other privately: the corresponding transaction hides the payment's origin, destination, and transferred amount. We provide formal definitions and proofs of the construction's security. Second, we build Zero cash, a practical instantiation of our DAP scheme construction. In Zero cash, transactions are less than 1 kB and take under 6 ms to verify - orders of magnitude more efficient than the less-anonymous Zero coin and competitive with plain Bit coin.
A widespread security claim of the Bitcoin system, presented in the original Bitcoin white-paper, states that the security of the system is guaranteed as long as there is no attacker in possession of half or more of the total computational power used to maintain the system. This claim, however, is proved based on theoretically flawed assumptions. In the paper we analyze two kinds of attacks based on two theoretical flaws: the Block Discarding Attack and the Difficulty Raising Attack. We argue that the current theoretical limit of attacker's fraction of total computational power essential for the security of the system is in a sense not $\frac{1}{2}$ but a bit less than $\frac{1}{4}$, and outline proposals for protocol change that can raise this limit to be as close to $\frac{1}{2}$ as we want. The basic idea of the Block Discarding Attack has been noted as early as 2010, and lately was independently though-of and analyzed by both author of this paper and authors of a most recently pre-print published paper. We thus focus on the major differences of our analysis, and try to explain the unfortunate surprising coincidence. To the best of our knowledge, the second attack is presented here for the first time.
Open access
2 source records
cs.CR
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
Marcelo Arenas, Juan L. Reutter, Etienne Toussaint, Martín Ugarte · 6 authors
In the consensus protocols used in most cryptocurrencies, participants called miners must find valid blocks of transactions and append them to a shared tree-like data structure. Ideally, the rules of the protocol should ensure that miners maximize their gains if they follow a default strategy, which consists on appending blocks only to the longest branch of the tree, called the blockchain. Our goal is to understand under which circumstances are miners encouraged to follow the default strategy. Unfortunately, most of the existing models work with simplified payoff functions, without considering the possibility that rewards decrease over time because of the game rules (like in Bitcoin), nor integrating the fact that a miner naturally prefers to be paid earlier than later (the economic concept of discount). In order to integrate these factors, we consider a more general model where issues such as economic discount and decreasing rewards can be set as parameters of an infinite stochastic game. In this model, we study the limit situation in which a miner does not receive a full reward for a block if it stops being in the blockchain. We show that if rewards are not decreasing, then miners do not have incentives to create new branches, no matter how high their computational power is. On the other hand, when working with decreasing rewards similar to those in Bitcoin, we show that miners have an incentive to create such branches. Nevertheless, this incentive only occurs when a miner controls a proportion of the computational power which is close to half of the computational power of the entire network.
One of important issues of information security in the interaction of users is the use of methods and tools, allowing one party to make sure of the authenticity of another party. The proof of knowledge protocols which have the additional property of zero-knowledge are applied to solve this problem. The protocols based on asymmetric encryption have received wide acceptance, such as the Fiat-Shamir, Schnorr, Okamoto, Guillou-Quisquater, Brickell-McCurley, Feige-Fiat-Shamir protocols. Cryptographic strength of these protocols is defined by discrete logarithms in a finite prime field, as well as an increase in the number of accreditation cycles. As a result of the development of methods and tools of cryptanalysis and rapid development of technologies and power of computing systems, there is a need to increase the sizes of system-wide parameters of the protocol, leading to increased resource intensity and performance complexity of basic operations in the fields.Cryptographic zero-knowledge protocols on elliptic curves are proposed in the paper. The strength of cryptosystems on elliptic curves is based on the difficulty of solving the discrete logarithm problem in the group of elliptic curve points, and is more difficult than the discrete logarithm problem in the finite field. The completeness and soundness of protocols were determined, computation examples were given. The tools of the Strength Protocol Animator package were applied to verify the protocols for resistance to enemy attacks. Consequently, the use of cryptographic protocols on elliptic curves will significantly reduce the sizes of protocol parameters and increase the cryptographic strength
Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Łukasz Mazurek
BitCoin transactions are malleable in a sense that given a transaction an adversary can easily construct an equivalent transaction which has a different hash. This can pose a serious problem in some BitCoin distributed contracts in which changing a transaction's hash may result in the protocol disruption and a financial loss. The problem mostly concerns protocols, which use a "refund" transaction to withdraw a deposit in a case of the protocol interruption. In this short note, we show a general technique for creating malleability-resilient "refund" transactions, which does not require any modification of the BitCoin protocol. Applying our technique to our previous paper "Fair Two-Party Computations via the BitCoin Deposits" (Cryptology ePrint Archive, 2013) allows to achieve fairness in any Two-Party Computation using the BitCoin protocol in its current version.
With the rise and extensive usage of Bit coin, a peer-to-peer electronic cash system beginning at 2008, the number of transactions is growing. In order to analyze the activity in this currency system, we present a parallel analysis approach for meeting the need of building the transaction graph of this financial system. In order to test the performance and the realistic possibility of our approach, we implemented our approach and conducted some comparing to test the performance of our system. Through the experiment, we confirmed that this method is highly efficient and reliable compared with the traditional method.
Prabhjot Singh, B. R. Chandavarkar, Srishti Arora, Neha Agrawal
In this paper, we study Bit coin network for electronic cash transactions, and compare the extension to the BTCs network which inculcates provision of executing fast transactions with greater security and assurance with the former method of Proof-Of-Work for executing transactions. Above milestones are achieved by introducing the concepts of mutual trust and verifiable code execution between the payer and the payee in the network. Our work proposes a significant modification of the Pioneer model to provide a two-party trust framework for Bit coin transactions, considerably faster compared to the generic trust platform of Bit coin networks based on slow proof-of-work. The scheme proposed can promote the use of Bit coin transactions in real life scenarios, where fast transactions are desirable due time constraints between the payment and the service.
Masayuki Abe, Jan Camenisch, Maria Dubovitskaya, Ryo Nishimaki
In this paper, we provide the first scheme that realises an attribute-based access control system for static resources that offers maximal privacy and is secure in the universal composability framework (UC). More precisely, we offer a protocol for adaptive oblivious transfer, where the sender can enforce an attribute-based access control policy for each record and nevertheless learns neither which record a user retrieves nor which attributes a user has. As additional results we provide a new structure-preserving signature scheme from the SXDH assumption and a new universally composable adaptive oblivious transfer protocol that is secure under two DDH-like assumptions and is the most efficient one secure under ``non $q$-type'' assumptions. We believe the new signature scheme to be of independent interest as a building block that is compatible with Groth-Sahai non-interactive zero-knowledge proofs.
George Danezis, Cédric Fournet, Markulf Kohlweiss, Bryan Parno
Bitcoin is the first widely adopted distributed e-cash system and Zerocoin is a recent proposal to extend Bitcoin with anonymous transactions. The original Zerocoin protocol relies heavily on the Strong RSA assumption and double-discrete logarithm proofs, long-standing techniques with known performance restrictions. We show a variant of the Zerocoin protocol using instead elliptic curves and bilinear pairings. The proof system makes use of modern techniques based on quadratic arithmetic programs resulting in smaller proofs and quicker verification. We remark on several extensions to Zerocoin that are enabled by the general-purpose nature of these techniques.
We present BLACRONYM, a suite of new communication- and computation-efficient protocols for anonymous blacklisting without trusted third parties. Our protocols improve on Tsang et al.'s Blacklistable Anonymous Credentials (BLAC) system and its variants by incorporating novel batch zero-knowledge proof and verification techniques. BLACRONYM provides comparable functionality and security guarantees to those of BLAC and its derivatives, but it is substantially faster and consumes much less bandwidth. At the heart of BLACRONYM is the first batch zero-knowledge protocol in the literature for proofs of partial knowledge over non-monotone access structures; we suspect that our new techniques will find applications in speeding up other cryptographic constructions that require proofs of similar statements.
Antonis Papadimitriou, Mingchen Zhao, Andreas Haeberlen
In this paper, we discuss the problem of detecting general faults in distributed systems that handle confidential information. Detecting non-crash faults is difficult in this setting because, to check the behavior of a given node, we need to know its expected behavior -- but that can depend on the confidential information. Classical zero-knowledge proofs are difficult to apply because they are designed to verify functions with a fixed number of inputs, but in many distributed systems, both the size and the number of a node's "inputs" (the messages it has received from other nodes) are not known.
The Bitcoin cryptocurrency records its transactions in a public log called the blockchain. Its security rests critically on the distributed protocol that maintains the blockchain, run by participants called miners. Conventional wisdom asserts that the protocol is incentive-compatible and secure against colluding minority groups, i.e., it incentivizes miners to follow the protocol as prescribed. We show that the Bitcoin protocol is not incentive-compatible. We present an attack with which colluding miners obtain a revenue larger than their fair share. This attack can have significant consequences for Bitcoin: Rational miners will prefer to join the selfish miners, and the colluding group will increase in size until it becomes a majority. At this point, the Bitcoin system ceases to be a decentralized currency. Selfish mining is feasible for any group size of colluding miners. We propose a practical modification to the Bitcoin protocol that protects against selfish mining pools that command less than 1/4 of the resources. This threshold is lower than the wrongly assumed 1/2 bound, but better than the current reality where a group of any size can compromise the system.