Bitcoin is a decentralized payment system that relies on Proof-of-Work (PoW) to verify payments. Nowadays, Bitcoin is increasingly used in a number of fast payment scenarios, where the time between the exchange of currency and goods is short (in the order of few seconds). While the Bitcoin payment verification scheme is designed to prevent double-spending, our results show that the system requires tens of minutes to verify a transaction and is therefore inappropriate for fast payments. An example of this use of Bitcoin was recently reported in the media: Bitcoins were used as a form of \emph{fast} payment in a local fast-food restaurant. Until now, the security of fast Bitcoin payments has not been studied. In this paper, we analyze the security of using Bitcoin for fast payments. We show that, unless appropriate detection techniques are integrated in the current Bitcoin implementation, double-spending attacks on fast payments succeed with overwhelming probability and can be mounted at low cost. We further show that the measures recommended by Bitcoin developers for the use of Bitcoin in fast payments are not always effective in detecting double-spending; we show that if those recommendations are integrated in future Bitcoin implementations, double-spending attacks on Bitcoin will still be possible. Finally, we propose and implement a modification to the existing Bitcoin implementation that ensures the detection of double-spending attacks against fast payments.
Vipul Goyal, Chen-Kuei Lee, Rafail Ostrovsky, Ivan Visconti
We propose the first black-box construction of non-malleable commitments according to the standard notion of non-malleability with respect to commitment. Our construction additionally only requires a constant number of rounds and is based only on (black-box use of) one-way functions. Prior to our work, no black-box construction of non-malleable commitments was known (except for relaxed notions of security) in any (polynomial) number of rounds based on any cryptographic assumption. This closes the wide gap existent between black-box and non-black-box constructions for the problem of non-malleable commitments. Our construction relies on (and can be seen as a generalization of) the recent non-malleable commitment scheme of Goyal (STOC 2011). We also show how to get black-box constructions for a host of other cryptographic primitives. We extend our construction to get constant-round concurrent non-malleable commitments, constant-round multi-party coin tossing, and non-malleable statistically hiding commitments (satisfying the notion of non-malleability with respect to opening). All of the mentioned results make only a black-box use of one-way functions. Our primary technical contribution is a novel way of implementing the proof of consistency typically required in the constructions of non-malleable commitments (and other related primitives). We do this by relying on ideas from the ``zero-knowledge from secure multi-party computation" paradigm of Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2007). We extend in a novel way this ``computation in the head" paradigm (which can be though of as bringing powerful error-correcting codes into purely computational setting). To construct a non-malleable commitment scheme, we apply our computation in the head techniques to the recent (constant-round) construction of Goyal. Along the way, we also present a simplification of the construction of Goyal where a part of the protocol is implemented in an information theoretic manner. Such a simplification is crucial for getting a black-box construction. This is done by making use of pair wise-independent hash functions and strong randomness extractors. We show that our techniques have multiple applications, as elaborated in the paper. Hence, we believe our techniques might be useful in other settings in future.
A hybrid cloud is a cloud computing environment in which an organization provides and manages some internal resources and has others provided externally. However, this new environment could bring irretrievable losses to the clients due to a lack of integrity verification mechanism for distributed data outsourcing. To support scalable service and data migration, in this paper we address the construction of a collaborative integrity verification mechanism in hybrid clouds where we consider the existence of multiple cloud service providers to collaboratively store and maintain the clients' data. We propose a collaborative provable data possession scheme adopting the techniques of homomorphic verifiable responses and hash index hierarchy. In addition, we articulate the performance optimization mechanisms for our scheme and prove the security of our scheme based on multi-prover zero-knowledge proof system, which can satisfy the properties of completeness, knowledge soundness, and zero-knowledge. Our experiments also show that our proposed solution only incurs a small constant amount of communications overhead.
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 being 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.
« Bitcoin » est une monnaie virtuelle, électronique, cryptographique disponible en « peer to peer », créée en 2009. Au vu de sa popularité grandissante, le taux de convertibilité de cette monnaie augmente et baisse de façon incontrôlée depuis quelques mois. « Bitcoin », échappant par sa nature à tout contrôle des autorités financières, pourrait devenir un objet de spéculation, un outil utile aux « systèmes d’économie dangereuse » mais aussi constituer le ferment de changements sociétaux d’ampleur. Controversée, elle a fait l’objet de plusieurs tentatives de déstabilisation.
There's nothing like a dollar bill for paying a stripper. Anonymous, yet highly personal-wherever you use it, that dollar will fit the occasion. Purveyors of Internet smut, after years of hiding charges on credit cards, or just giving it away for free, recently found their own version of the dollar-a new digital currency called Bitcoin.
Privacy-preserving set operations are useful for many data mining algorithms as building tools. Protocols for privacy-preserving set operations have considered semi-honest and malicious adversarial models in cryptographic settings, whereby an adversary is assumed to follow or arbitrarily deviate from the protocol. Semi-honest model provides weak security requiring small amount of computation, on the other hand, malicious model provides strong security requiring expensive computations like homomorphic encryption. However, efficient computation of such set operations are desirable for practical implementations. In this paper, we build efficient and private set operations avoiding the use of expensive tools like homomorphic encryption, zero knowledge proof, and oblivious transfer. Our protocol is constructed in game-theoretic model. In other words, instead of being semi-honest or malicious, the parties are viewed as rational and are assumed (only) to act in their self-interest. We show that our protocol satisfies computational Nash equilibrium.
Provable data possession (PDP) is a technique for ensuring the integrity of data in storage outsourcing. In this paper, we address the construction of an efficient PDP scheme for distributed cloud storage to support the scalability of service and data migration, in which we consider the existence of multiple cloud service providers to cooperatively store and maintain the clients' data. We present a cooperative PDP (CPDP) scheme based on homomorphic verifiable response and hash index hierarchy. We prove the security of our scheme based on multiprover zero-knowledge proof system, which can satisfy completeness, knowledge soundness, and zero-knowledge properties. In addition, we articulate performance optimization mechanisms for our scheme, and in particular present an efficient method for selecting optimal parameter values to minimize the computation costs of clients and storage service providers. Our experiments show that our solution introduces lower computation and communication overheads in comparison with noncooperative approaches.
Marco Aurelio Felizardo de Andrade, Wladston Viana Ferreira Filho, Francisco Chaves de Carvalho Marinho, Bruna Andreata Avelar · 6 authors
Resumo. A ampla utilizacao e disponibilizacao de tecnologias criptograficas, juntamente com a internet, possibilitou a troca segura, anonima e distribuida de mensagens. Utilizando essas tecnologias como base, foi desenvolvido um protocolo para um sistema financeiro anonimo, seguro, distribuido, e sem controle central chamado Bitcoin. Hoje ja sao transacionados milhoes de dolares cada dia em Bitcoins, e nos Estados Unidos e Europa muitos comercios e prestadores de servicos estao aceitando pagamentos nessa moeda. Essa plataforma tem um potencial imenso para aumentar as liberdades individuais dos cidadaos, caso seja amplamente utilizada, pois torna os bancos obsoletos ao disponibilizar um sistema seguro, privado e anonimo. O custo das transacoes e quase zero, e nao ha restricoes para transacoes financeiras para outros paises. Neste artigo sera explicado como funciona, as vantagens e desvantagens, e serao mostrados exemplos de utilizacao.
What is the legal status of a “bitcoin,” a decentralized peer-to-peer digital currency? Is the use of bitcoins even legal? Should it be? The bitcoin cybercurrency thus poses a puzzle. Unlike centralized and publicly-created metallic or paper currencies, bitcoin is a privately-created, decentralized medium of exchange and thus is not backed by any national or transnational government or by any public or private bank. As such, the legal status of the bitcoin cybercurrency is murky and unclear at best. Despite this legal uncertainty, the demand for bitcoins on the Internet continues to grow. The authors will present a legal, normative, and game-theoretic analysis of the bitcoin cybercurrency. To provide a theoretical background to our legal and normative analysis, the first part of the paper will present an analytical model of the behavior of bitcoin users. In summary, the use of bitcoins can be modeled as a Prisoner’s Dilemma. That is, because of the limited supply of bitcoins and the rising demand of this cybercurrency, the temptation to defect by hoarding this currency -- rather than using bitcoins for the exchange of goods and services -- threatens the stability of the bitcoin cybercurrency as a whole. In the second part of the paper, the authors consider the legal status of bitcoins, discuss the policy and normative arguments for and against the legalization of bitcoins, and propose several possible legal frameworks for protecting the bitcoin cybercurrency and solving the bitcoin puzzle.
利用Cha-Cheon 的基于身份的签名方案提出了一个可证安全的基于身份的可验证加密签名(verifiablyencrypted signature,简称VES)方案,并利用该方案和基于身份的代理可验证加密签名(proxy verifiably encryptedsignature,简称PVES)方案提出了一个新颖的多元合同签署协议.信息交换过程中,原始签名者或代理签名者分别利用VES 或PVES 实现承诺消息的交换与认证,并未使用复杂的零知识证明系统,从而有效避免了大量运算.当争议发生时,可信第三方从VES 或PVES 中恢复出有效的合同签名,以保证签署者的公平性.安全性分析结果表明,协议满足不可否认性、时效性以及公平性.;Utilizing the Cha-Cheon’s identity-based signature scheme, a provably secure identity-based verifiably encrypted signature (VES) scheme is proposed. Utilizing the proposed scheme and identity-based proxy verifiably encrypted signature (PVES) scheme, a novel multiplex contract signing protocol is also proposed. The original signer or proxy signer uses VES or PVES to realize the interaction and certification of the commitment message in the information exchange process. The proposed scheme does not need the zero-knowledge proof and excessive computation. An optimized trusted third party who participates in the protocol extracts the formal signature from the VES or PVES only when problem occurs. The performance analysis results show that the scheme satisfies non-repudiation, timeliness and fairness.
This paper analyses 26 time series that measure daily data for different attributes of the Bitcoin network and studies how the virtual currency behaves compared to a basket of currencies containing the Brazil Real (BRL), the Chinese Yuan (CNY), the Euro (EUR), and the Japan Yen (JPY) against the US Dollar (USD). \nBasic statistics about the time series have been taken and stationarity has been studied in order to build sterilized fact data and meaningful cointegrations have been found among them. By applying a Vector Autoregressive (VAR) model, a regression has been built among the currencies and the Granger causality test has been applied in order to determine whether one time series (of a given currency) is useful in forecasting another and to observe causal relationships among the currencies studied.
Blockchain, a continuously growing tamper resistant data structure, was developed as the technology underlying the Bitcoin crypto-currency and it is now being applied to a wide range of problems as a form of ‘Distributed Ledger’. The promise of this technology has been recognised by governments and the financial industry. It also has application to enhance privacy of personal information, to secure the Internet of things and to change electronic identity. This study explains what a Blockchain is and how it works. It describes some actual and the potential applications of this technology together with some of the risks associated with its use.
The Fiat-Shamir paradigm was proposed as a way to remove interaction from 3-round proof of knowledge protocols and derive secure signature schemes. This generic transformation leads to very efficient schemes and has thus grown quite popular. However, this transformation is proven secure only in the random oracle model. In FOCS 2003, Goldwasser and Kalai showed that this transformation is provably insecure in the standard model by presenting a counterexample of a 3-round protocol, the Fiat-Shamir transformation of which is (although provably secure in the random oracle model) insecure in the standard model, thus showing that the random oracle is uninstantiable. In particular, for every hash function that is used to replace the random oracle, the resulting signature scheme is existentially forgeable. This result was shown by relying on the non-black-box techniques of Barak (FOCS 2001). An alternative to the Fiat-Shamir paradigm was proposed by Fischlin in Crypto 2005. Fischlin’s transformation can be applied to any so called 3-round “Fiat-Shamir proof of knowledge’ ’ and can be used to derive non-interactive zero-knowledge proofs of knowledge as well as signature schemes. An attractive property of this transformation is that it provides online extractability (i.e., the extractor works without having to rewind the prover). Fischlin remarks that in comparison to the Fiat-Shamir transformation, his construction tries to
In cloud storage service, clients upload their data together with authentication information to cloud storage server. To ensure the availability and integrity of clients' stored data, cloud server(CS) must prove to a verifier that he is actually storing all of the client's data unchanged. And, enabling public auditability for cloud storage is of critical importance to users with constrained computing resources, who can resort to a third party auditor (TPA) to check the integrity of outsourced data. However, most of the existing proofs of retrievability schemes or proof of data possession schemes do not consider data privacy problem. Zero knowledge privacy requires TPA or the adversary can not deduce any information of the file data from auditing system. In this paper, after giving a new construction of a recently proposed cryptographic primitive named aggregatable signature based broadcast (ASBB) encryption scheme, we present an efficient public auditing scheme with zero knowledge privacy. The new scheme is as efficient as the scheme presented by Shacham and Waters without considering privacy and is secure in the random oracle model.