Abstract. Bitcoin is quickly emerging as a popular digital payment system. However, in spite of its reliance on pseudonyms, Bitcoin raises a number of privacy concerns due to the fact that all of the transactions that take place are publicly announced in the system. In this paper, we investigate the privacy guarantees of Bitcoin in the setting where Bitcoin is used as a primary currency for the daily transactions of individuals. More specifically, we evaluate the privacy that is provided by Bitcoin (i) by analyzing the genuine Bitcoin system and (ii) through a simulator that faithfully mimics the operation of Bitcoin in the context where Bitcoin is used for all transactions within a university. In this setting, our results show that the profiles of almost 40 % of the users can be, to a large extent, recovered even when users adopt privacy measures recommended by Bitcoin. To the best of our knowledge, this is the first work that comprehensively analyzes, and evaluates the privacy implications of Bitcoin. As a by-product, we have designed and implemented the first simulator of Bitcoin; our simulator can be used to model the interaction between Bitcoin users in generic settings. 1
Abstract. The Bitcoin scheme is a rare example of a large scale global payment system in which all the transactions are publicly accessible (but in an anonymous way). We downloaded the full history of this scheme, and analyzed many statistical properties of its associated transaction graph. In this paper we answer for the first time a variety of interesting questions about the typical behavior of users, how they acquire and how they spend their bitcoins, the balance of bitcoins they keep in their accounts, and how they move bitcoins between their various accounts in order to better protect their privacy. In addition, we isolated all the large transactions in the system, and discovered that almost all of them are closely related to a single large transaction that took place in November 2010, even though the associated users apparently tried to hide this fact with many strange looking long chains and fork-merge structures in the transaction graph.
Moshe Babaioff, Shahar Dobzinski, Sigal Oren, Aviv Zohar
Many large decentralized systems rely on information propagation to ensure their proper function. We examine a common scenario in which only participants that are aware of the information can compete for some reward, and thus informed participants have an incentive not to propagate information to others. One recent example in which such tension arises is the 2009 DARPA Network Challenge (finding red balloons). We focus on another prominent example: Bitcoin, a decentralized electronic currency system. Bitcoin represents a radical new approach to monetary systems. It has been getting a large amount of public attention over the last year, both in policy discussions and in the popular press. Its cryptographic fundamentals have largely held up even as its usage has become increasingly widespread. We find, however, that it exhibits a fundamental problem of a different nature, based on how its incentives are structured. We propose a modification to the protocol that can eliminate this problem. Bitcoin relies on a peer-to-peer network to track transactions that are performed with the currency. For this purpose, every transaction a node learns about should be transmitted to its neighbors in the network. The current implemented protocol provides an incentive to nodes to not broadcast transactions they are aware of. Our solution is to augment the protocol with a scheme that rewards information propagation. Since clones are easy to create in the Bitcoin system, an important feature of our scheme is Sybil-proofness. We show that our proposed scheme succeeds in setting the correct incentives, that it is Sybil-proof, and that it requires only a small payment overhead, all this is achieved with iterated elimination of dominated strategies. We complement this result by showing that there are no reward schemes in which information propagation and no self-cloning is a dominant strategy.
• Electronic financial transactions and payment systems have traditionally relied on third party institutions, such as banks or credit card companies, to ensure secure transfers between parties. Users of such systems must trust that third party institutions will be honest and follow through with their claims. Trust-based systems are difficult to establish in the digital realm without a governing body regulating and securing transfers. Systems using this model have many downfalls that make them risky and undesirable for Internet use. With the requirement of all transactions being completely digital, how can we transfer funds securely without a trusted third party?
• All types of currencies share many common problems such as stability, control, and inflation. As time passes, the relative value of a currency usually decreases (meaning that prices increase). If this happens too quickly, it can cause major problems if prices increase beyond the means of the populace who uses the currency. Another problem is stability because the currency should not be subject to dramatic exchange rate fluctuations under the influence of a single individual or party. Control over a currency, or lack thereof, is also important. Typical fiat currencies depend on a mint and the promise that the mint will continue its operations. If the mint were to close indefinitely, the currency would likely die out in a relatively short period of time. Therefore, the mint has some level of control over the currency.
• Bitcoin is a digital currency introduced in 2009, based on a self-published paper by Satoshi Nakamoto[1]. Bitcoin enables payments that are based on proof, rather than trust, in a manner that is similar to cash. A seller given a cash payment can inspect the currency and, with a good degree of confidence, assert whether the payment is valid or invalid. Bitcoins works using a similar concept that make coins and coin ownership easy to verify. An important difference between this virtual currency and typical fiat currency is that Bitcoin's validity can be verified.
• During this workshop we showed attendees the verification process as well as the algorithms and technologies that make verification possible. The audience learned about online money transaction, then analyzed standard techniques and form comparisons between them. The workshop then proceeded to discuss the history and purpose of Bitcoins along with an overview of its concepts and terminologies.
• The workshop continues to compare Bitcoins with other transaction techniques discussed and talk about the pros and the cons. We also go though the problems that Bitcoin will be able to solve and what new problems it will introduce.
• Attendees will learn the details of Bitcoins and its implementations. From Asymmetric cryptography algorithms to hashing and digital signatures to proof of work, the audience will be walked though all the technologies that make Bitcoin possible.
• The workshop will take attendees through actual Bitcoin transactions and the details of the transaction process as it will allow them to see how the Bitcoin system overcome problems such as double spending. The audience was also taught about Bitcoin generation and how Bitcoins are generated out of thin air. For context, we covered how much coins are worth and how people are already profiting from services other than mining. The details of Bitcoin blocks and chains were demystified in a manner that was detailed but simple to understand.
• The Bitcoin network was one of the main focuses - how a distributed and completely public network can maintain the anonymity of its users. It was discussed in detail about how transactions are validated through the network and about the transaction databases that is on the distributed network. The audience learned how the distributed database handles failures, delay, and is able to work effectively with only a subset of the entire database. The audience learned concepts such as merkle trees and how they help the Bitcoin network to maintain the database. We answer questions such as how Bitcoins control the expansion of its own currency when the Bitcoin network may double in size in a short period of time. The many interesting characteristics of the network were unveiled during this engaging demonstration.
• Attacks and malicious hosts are constantly a threat to modern day electronic transactional systems and this also applies to Bitcoin. We mapped out the architectural features that make Bitcoin naturally resilient to many common attacks, as well as the features that make it vulnerable. We discussed possible attacks on the Bitcoin network as well as attack mitigation and ways in which end users can protect themselves.
• Another interesting issue is anonymity. Bitcoin is regarded as being anonymous by many people, yet Bitcoins can be traced from the original miner all the way to the current owner. A Bitcoin address itself is just a number and cannot identify anyone. However if a person manages to collect enough information about the owner of that address (perhaps through forums) then the owner can be exposed.
• To conclude, in this workshop we explored everything from cryptographic algorithms to the massive peer-to-peer network. We took a security perspective for an in-depth exploration of Bitcoin attacks and attack mitigation. We ended our workshop with a look at how Bitcoin might change the e-commerce landscape, followed by an open discussion.
Anonymity in Bitcoin, a peer-to-peer electronic currency system, is a complicated issue. Within the system, users are identified by public-keys only. An attacker wishing to de-anonymize its users will attempt to construct the one-to-many mapping between users and public-keys and associate information external to the system with the users. Bitcoin tries to prevent this attack by storing the mapping of a user to his or her public-keys on that user's node only and by allowing each user to generate as many public-keys as required. In this chapter we consider the topological structure of two networks derived from Bitcoin's public transaction history. We show that the two networks have a non-trivial topological structure, provide complementary views of the Bitcoin system and have implications for anonymity. We combine these structures with external information and techniques such as context discovery and flow analysis to investigate an alleged theft of Bitcoins, which, at the time of the theft, had a market value of approximately half a million U.S. dollars.
Paulo Nováis, Francisco Andrade, José Machado, José Neves
Inter-systemic contracting may be based upon autonomous intelligent behaviour. Autonomy is an important advantage of software agents. Yet, it brings along several issues concerning the legal consideration (e.g. legal personality/attribution) and the legal consequences of software agent’s behaviour. The intervention of software agents in corporate bodies and the consideration of its roles must also be referred. All this intends interactions based on contracts and relations of trust, at an individual, at a community and at a systemic level. In this regard, it does make sense to speak of the relation between good faith and trust in inter-systemic contracting. And at the systemic level there is a need to focus on special protocols intended to enhance trust in electronic commerce. Chapter 12 proposes smart contracts as a way of enhancing trust and of achieving enforcement in electronic contracting.
Sonu Mariam Paulose, R. Venkatesan, K. Ramalakshmi
Conjunction of massive amount of idle computers or resources that may be loosely coupled, heterogeneous and geographically dispersed to reach a common goal leads to a virtual computing platform for sharing resources across the world. Resource management, application development and usage models in these environments has some dilemma in undertaking resources due to resource providers with multiple administrative domains having their own policies and terms. A ditch in the Grid computing environment is how to coordinate the distributed resources amongst a dynamic set of individuals and organizations where the requesters and providers are allowed to join and leave Grid environment at any time. Bidding model prevents single point of failure and server overload problems of match making model while minimizing turnaround time by using some set of deterministic and probabilistic selection heuristics where resource requesters and resource providers were given the privilege to take autonomous decisions regarding resource selection. Autonomous decision making is enabled via peer-to-peer decentralized scheduling frame work. In decentralized environment, lack of global information is a key challenge to facilitate optimum decision making which can lead to greedy selection of the best provider. Therefore some probabilistic selection is used to reduce the fairness deviation among processors while minimizing the turnaround time. Currently just various level of information about providers has been concentrated to minimize the turnaround time. Simply concentrating on various level of information may also leads to failure due to rejection factor resulted by number of failures occurred at provider. However by merging trust oriented mechanisms along with various level of information, rejection factor can also be minimized along with minimization of the turnaround time.
Harry Kalodner, Miles Carlsten, Paul Ellenbogen, Joseph Bonneau · 5 authors
Secure decentralized namespaces have recently become possible due to cryptocurrency technology. They enable a censorship-resistant domainname system outside the control of any single entity, among other applications. Namecoin, a fork of Bitcoin, is the most prominent example. We initiate the study of decentralized namespaces and the market for names in such systems. Our extensive empirical analysis of Namecoin reveals a system in disrepair. Indeed, our methodology for detecting “squatted” and otherwise inactive domains reveals that among Namecoin’s roughly 120,000 registered domain names, a mere 28 are not squatted and have nontrivial content. Further, we develop techniques for detecting transfers of domains in the Namecoin block chain and provide evidence that the market for domains is thin-tononexistent. We argue that the state of the art in mechanism design for decentralized namespace markets is lacking. We propose a model of utility of different names to different participants, and articulate desiderata of a decentralized namespace in terms of this utility function. We use this model to explore the design space of mechanisms and analyze the trade-offs.
Abstract. In resetting attacks against a proof system, a prover or a verifier is reset and enforced to use the same random tape on various inputs as many times as an adversary may want. Recent deployment of cloud computing gives these attacks a new importance. This paper shows that argument systems for any NP language that are both resettably-sound and resettable zero-knowledge are possible by a constant-round protocol in the BPK model. For that sake, we define and construct a resettablyextractable conditional commitment scheme.
We present a method to compile Yao’s two-player garbled circuit protocol into one that is secure against malicious adversaries that relies on witness indistinguishability. Our approach can enjoy lower communication and computation overhead than methods based on cut-andchoose [13] and lower overhead than methods based on zero-knowledge proofs [8] (or Σ-protocols [14]). To do so, we develop and analyze new solutions to issues arising with this transformation: — How to guarantee the generator’s input consistency — How to support different outputs for each player without adding extra gates to the circuit of the function f being computed — How the evaluator can retrieve input keys but avoid selective failure attacks — Challenging 3/5 of the circuits is near optimal for cut-and-choose (and better than challenging 1/2) Our protocols require the existence of secure-OT and claw-free functions that have a weak malleability property. We discuss an experimental implementation of our protocol to validate our efficiency claims.
Abstract. In the standard definition of a commitment scheme, the sender commits to a message and immediately sends the commitment to the recipient interested in it. However the sender may not always know at the time of commitment who will become interested in verifying it. Further, when the interested party does emerge, it could be critical to establish when the commitment was made. Employing a proof of work protocol at commitment time will later allow anyone to “carbon date ” when the commitment was made, approximately, without trusting any external parties. We present CommitCoin, an instantiation of this approach that harnesses the existing processing power of the Bitcoin peer-to-peer network; a network used to mint and trade digital cash. 1 Introductory Remarks Consider the scenario where Alice makes an important discovery. It is important to her that she receives recognition for her breakthrough, however she would also like to keep it a secret until she can establish a suitable infrastructure for monetizing it. By forgoing publication of her discovery, she risks Bob independently making the same discovery and publicizing it as his own. Folklore suggests that Alice might mail herself a copy of her discovery and leave the letter sealed, with the postal service’s timestamp intact, for a later resolution time. If Bob later claims the same discovery, the
Traditional electricity meters are replaced by Smart Meters in customers' households. Smart Meters collects fine-grained utility consumption profiles from customers, which in turn enables the introduction of dynamic, time-of-use tariffs. However, the fine-grained usage data that is compiled in this process also allows to infer the inhabitant's personal schedules and habits. We propose a privacy-preserving protocol that enables billing with time-of-use tariffs without disclosing the actual consumption profile to the supplier. Our approach relies on a zero-knowledge proof based on Pedersen Commitments performed by a plug-in privacy component that is put into the communication link between Smart Meter and supplier's back-end system. We require no changes to the Smart Meter hardware and only small changes to the software of Smart Meter and back-end system. In this paper we describe the functional and privacy requirements, the specification and security proof of our solution and give a performance evaluation of a prototypical implementation.
Cloud computing provides a novel computing paradigm for enterprises to store programs and data in the Cloud in a transparent manner, which poses the challenge of security and privacy. In this paper, based on homomorphic cryptography and Zero-Knowledge Proof, we present a novel privacy-preserving scheme for Cloud publish/subscribe service, which achieve efficient privacy-preserving authentication, data integrity, and publish-subscribe confidentiality. The performance evaluation and security analysis demonstrate the practice and validity of the proposed scheme.
Based on the interactive proof of Hamiltonian Cycle (HC) of large directed graph, which is a $\Sigma$-protocol, we construct a perfectly hiding and computationally binding trapdoor commitment in 2-round from any one-way permutation. Then, based on this trapdoor commitment, we construct perfect zero-knowledge argument of knowledge with negligible error probability in 2-round for $\mathcal{NP}$, assuming only the existence of a one-way permutation.
Multiparty computation protocols have been known for more than twenty years now, but due to their lack of efficiency their use is still limited in real-world applications: the goal of this paper is the design of efficient two and multi party computation protocols aimed to fill the gap between theory and practice. We propose a new protocol to securely evaluate reactive arithmetic circuits, that offers security against an active adversary in the universally composable security framework. Instead of the “do-and-compile” approach (where the parties use zero-knowledge proofs to show that they are following the protocol) our key ingredient is an efficient version of the “cut-and-choose” technique, that allow us to achieve active security for just a (small) constant amount of work more than for passive security.
As its own security risks of existing patent trading platform, on-line patent transaction can not be realized. The security problems are mainly embodied in the confidentiality of transaction information, and security of patent delivery areas. One of the important characteristics of zero-knowledge proof is zero-knowledge, which can enable the verifier to believe that the conclusion is correct without knowing the contents of it. This characteristic can solve the problems of current patent transaction security mentioned above. Based on zero-knowledge proof, through the framework and flow design, this paper builds a secure patent trading platform, which shows a new way of patent trading. What is more, the security and convenience of this trading platform are better than ever before.