Arthur Gervais, SrÄjan Äapkun, Ghassan Karame, Damian Gruber
Lightweight Bitcoin clients are gaining increasing adoption among Bitcoin users, owing to their reduced resource and bandwidth consumption. These clients support a simplified payment verification (SPV) mode as they are only required to download and verify a part of the block chain---thus supporting the usage of Bitcoin on constrained devices, such as smartphones. SPV clients rely on Bloom filters to receive transactions that are relevant to their local wallet. These filters embed all the Bitcoin addresses used by the SPV clients, and are outsourced to more powerful Bitcoin nodes which then only forward to those clients transactions relevant to their outsourced Bloom filters. \n \nIn this paper, we explore the privacy of existing SPV clients. We show analytically and empirically that the reliance on Bloom filters within existing SPV clients leaks considerable information about the addresses of Bitcoin users. Our results show that an SPV client who uses a modest number of Bitcoin addresses (e.g., < 20) risks revealing almost all of his addresses. We also show that this information leakage is further exacerbated when users restart their SPV clients and/or when the adversary has access to more than one Bloom filter pertaining to the same SPV client. Motivated by these findings, we propose an efficient countermeasure to enhance the privacy of users which rely on SPV clients; our proposal can be directly integrated within existing SPV client implementations.
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.
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
Jan 1, 2014·25th IET Irish Signals & Systems Conference 2014 and 2014 China-Ireland International Conference on Information and Communities Technologies (ISSC 2014/CIICT 2014)
Bitcoin is a digital cryptocurrency that has generated considerable public interest, including both booms in value and busts of exchanges dealing in Bitcoins. One of the fundamental concepts of Bitcoin is that work, called mining, must be done in checking all monetary transactions, which in turn creates Bitcoins as a reward. In this paper we look at the energy consumption of Bitcoin mining. We consider if and when Bitcoin mining has been profitable compared to the energy cost of performing the mining, and conclude that specialist hardware is usually required to make Bitcoin mining profitable. We also show that the power currently used for Bitcoin mining is comparable to Ireland's electricity consumption.
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.
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.
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.
We provide a first systematic account of opportunities and limitations of anti-money laundering (AML) in Bitcoin, a decentralized cryptographic currency proliferating on the Internet. Our starting point is the observation that Bitcoin attracts criminal activity as many say it is an anonymous transaction system. While this claim does not stand up to scrutiny, several services offering increased transaction anonymization have emerged in the Bitcoin ecosystem - such as Bitcoin Fog, BitLaundry, and the Send Shared functionality of Blockchain.info. Some of these services routinely handle the equivalent of 6-digit dollar amounts. In a series of experiments, we use reverse-engineering methods to understand the mode of operation and try to trace anonymized transactions back to our probe accounts. While Bitcoin Fog and Blockchain.info successfully anonymize our test transactions, we can link the input and output transactions of BitLaundry. Against the backdrop of these findings, it appears unlikely that a Know-Your-Customer principle can be enforced in the Bitcoin system. Hence, we sketch alternative AML strategies accounting for imperfect knowledge of true identities but exploiting public information in the transaction graph, and discuss the implications for Bitcoin as a decentralized currency.
A collection of questions about Bitcoin and its hypothetical relatives Bitguilder and Bitpenny is formulated. These questions concern technical issues about protocols, security issues, issues about the formalizations of informational monies in various contexts, and issues about forms of use and misuse. Some questions are formulated in the more general setting of informational monies and near-monies. We also formulate questions about legal, psychological, and ethical aspects of informational money. Finally we formulate a number of questions concerning the economical merits of and outlooks for Bitcoin.
With the advent of the information age, the network security is particularly important. The secure multiparty computation is a very important branch of cryptography. It is a hotspot in the field of information security. It expanded the scope of the traditional distributed computing and information security, provided a new computing model for the network collaborative computing. First we introduced several key technologies of secure multiparty computation: secret sharing and verifiable secret sharing, homomorphic public key cryptosystem, mix network, zero knowledge proof, oblivious transfer, millionaire protocol. Second we discussed the applications of secure multiparty computation in electronic voting, electronic auctions, threshold signature, database queries, data mining, mechanical engineering and other fields.
We perform a comprehensive measurement analysis of Silk Road, an anonymous, international online marketplace that operates as a Tor hidden service and uses Bitcoin as its exchange currency. We gather and analyze data over eight months between the end of 2011 and 2012, including daily crawls of the marketplace for nearly six months in 2012. We obtain a detailed picture of the type of goods sold on Silk Road, and of the revenues made both by sellers and Silk Road operators. Through examining over 24,400 separate items sold on the site, we show that Silk Road is overwhelmingly used as a market for controlled substances and narcotics, and that most items sold are available for less than three weeks. The majority of sellers disappears within roughly three months of their arrival, but a core of 112 sellers has been present throughout our measurement interval. We evaluate the total revenue made by all sellers, from public listings, to slightly over USD 1.2 million per month; this corresponds to about USD 92,000 per month in commissions for the Silk Road operators. We further show that the marketplace has been operating steadily, with daily sales and number of sellers overall increasing over our measurement interval. We discuss economic and policy implications of our analysis and results, including ethical considerations for future research in this area.
The Bitcoin network of decentralized payment transactions has attracted a lot of attention from both Internet users and researchers in recent years. Bitcoin utilizes a peer-to-peer network to issue anonymous payment transactions between different users. In the currently used Bitcoin clients, the full transaction history is available at each node of the network to prevent double spending without the need for a central authority, forming a valuable source for empirical research on network structure, network dynamics, and the implied anonymity challenges, as well as guidance on the future evolution of complex payment systems. We found dynamical effects of which some increase anonymity while others decrease it. Most importantly, several parameters of the Bitcoin transaction graph seem to have become stationary over the last 12â18 months. We discuss the implications.
Blind signature-based electronic voting is the simplest paradigm for implementing remote voting platforms due to the fact that it does not employ complicated zero-knowledge proofs. Unfortunately, the existence of a trusted entity (the "Authentication Server") that, in case of corruption, would be able to cast indistinguishable fake votes reduces the acceptance of the paradigm in non fully trusted environments. Trust on the system can be increased by splitting this entity into of a set of parties that are unlikely to collaborate in a dishonest manner. Nevertheless, this technique increases the risk of failure of some of them causing a service interruption during the voting period. Better fault tolerance is provided by proposals which permit to anticipate the interaction with the distributed authentication server before the voting period begins, so that, in case of failure, there is a broad time margin for system restoration. Previous proposals following this approach have been proven to be cryptographically weak or just provide individual verifiability. In this paper, a system that employs blind certificates is presented. Unlike previous proposals, it provides universal verifiability and permits to detect double voting without putting voters' privacy at risk.
Electronic voting is a popular application of cryptographic and network techniques to e-government. Most of the existing e-voting schemes can be classified into two categories: homomorphic voting and shuffling-based voting. In a homomorphic voting, an encryption algorithm with special homomorphic property (e.g. ElGamal encryption or Paillier encryption) is employed to encrypt the votes such that the sum of the votes can be recovered without decrypting any single vote. An advantage of homomorphic voting is efficient tallying. Tallying in homomorphic voting only costs one single decryption operation for each candidate. In this chapter, the existing e-voting solutions in both categories are surveyed and analysed. The key security properties in both categories are presented and then the existing e-voting schemes in each category are checked against the corresponding security properties. Security and efficiency of the schemes are analysed and the strongest security and highest efficiency achievable in each category is estimated. Problems and concerns about the existing solutions including vulnerability to malicious voters and (or) talliers, possible failure of complete correctness, imperfect privacy, dependence on computational assumptions, and exaggerated efficiency are addressed. New approaches will be proposed in both kinds of solutions to overcome the existing drawbacks in them. In homomorphic e-voting, the authors deal with possibly malicious voters and aim at efficient vote validity check to achieve strong and formally provable soundness and privacy. It can be implemented through new zero knowledge proof techniques, which are both efficient and provably secure. In mix-network-based e-voting, the authors deal with possibly deviating operations of both voters and talliers and aim at efficient proof of validity of shuffling, which guarantees the desired security properties and prevent attacks from malicious participants. It can be based on inspiring linear algebra knowledge and the new zero knowledge proof of existence of secret permutation.
In this article, we discuss a possible exploit in Bitcoin that arises from the simultaneous adoption of client versions 0.8.1 and 0.8.2 (or 0.8.3) in the network. In version 0.8.2, Bitcoin clients no longer accept transactions with non-strict signature encoding. As we show, this incompatibility with prior client versions can potentially lead to a double-spending attack in a fast payment setting in Bitcoin. The attack can only work when merchants operate on any client version prior to 0.8.2. Our aim is therefore to raise the awareness of merchants to adopt version 0.8.2 (or 0.8.3) if they are willing to accept fast payments [1].
Online advertising is at the core of todayâs Web: it is the main business model, generating large annual revenues expressed in tens of billions of dollars that sponsor most of the online content and services. Online advertising consists of delivering marketing messages, embedded into Web content, to a targeted audience. In this model, entities attract Web traffic by offering the content and services for free and charge advertisers for including advertisements in this traffic (i.e., advertisers pay for usersâ attention and interests). Online advertising is a very successful form of advertising as it allows for advertisements (ads) to be targeted to individual usersâ interests; especially when advertisements are served on usersâ mobile devices, as ads can be targeted to usersâ locations and the corresponding context. However, online advertising also introduces a number of problems. Given the high ad revenue at stake, fraudsters have economic incentives to exploit the ad system and generate profit from it. Unfortunately, to achieve this goal, they often compromise usersâ online security (e.g., via malware, phishing, etc.). For the purpose of maximizing the revenue by matching ads to usersâ interests, a number of techniques are deployed, aimed at tracking and profiling usersâ digital footprints, i.e., their behavior in the digital world. These techniques introduce new threats to usersâ privacy. Consequently, some users adopt ad-avoidance tools that prevent the download of advertisements and partially thwart user profiling. Such user behavior, as well as exploits of ad systems, have economic implications as they undermine the online advertising business model. Meddling with advertising revenue disrupts the current economic model of the Web, the consequences of which are unclear. Given that todayâs Web model relies on online advertising revenue in order for users to have access and consume content and services for âfreeâ, coupled with the fact that there are many threats that could jeopardize this model, in this thesis we address the security, privacy and economic issues stemming from this fundamental element of the Web. In the first part of the thesis, we investigate the vulnerabilities of online advertising systems. We identify how an adversary can exploit the ad system to generate profit for itself, notably by performing inflight modification of ad traffic. We provide a proof-of-concept implementation of the identified threat on Wi-Fi routers. We propose a collaborative approach for securing online advertising and Web browsing against such threats. By investigating how a certificate-based authentication is deployed in practice, we assess the potential of relying on certificate-based authentication as a building block of a solution to protect the ad revenue. We propose a multidisciplinary approach for improving the current state of certificate-based authentication on the Web. In the second part of the thesis, we study the economics of ad systemsâ exploits and certain potential countermeasures. We evaluate the potential of different solutions aimed at protecting ad revenue being implemented by the stakeholders (e.g., Internet Service Providers or ad networks) and the conditions under which this is likely to happen. We also study the economic ramifications of ad-avoidance technologies on the monetization of online content. We use game-theory to model the strategic behavior of involved entities and their interactions. In the third part of the thesis, we focus on privacy implications of online advertising. We identify a novel threat to usersâ location privacy that enables service providers to geolocate users with high accuracy, which is needed to serve location-targeted ads for local businesses. We draw attention to the large scale of the threat and the potential impact on usersâ location privacy.