Several new services incentivize clients to compete in solving large computation tasks in exchange for financial rewards. This model of competitive distributed computation enables every user connected to the Internet to participate in a game in which he splits his computational power among a set of competing pools â the game is called a computational power splitting game. We formally model this game and show its utility in analyzing the security of pool protocols that dictate how financial rewards are shared among the members of a pool. As a case study, we analyze the Bitcoin cryptocurrency which attracts computing power roughly equivalent to billions of desktop machines, over 70% of which is organized into public pools. We show that existing pool reward sharing protocols are insecure in our game-theoretic analysis under an attack strategy called the âblock withholding attackâ. This attack is a topic of debate, initially thought to be ill-incentivized in todayâs pool protocols: i.e., causing a net loss to the attacker, and later argued to be always profitable. Our analysis shows that the attack is always well-incentivized in the long-run, but may not be so for a short duration. This implies that existing pool protocols are insecure, and if the attack is conducted systematically, Bitcoin pools could lose millions of dollars worth in months. The equilibrium state is a mixed strategyâthat isâin equilibrium all clients are incentivized to probabilistically attack to maximize their payoffs rather than participate honestly. As a result, a part of the Bitcoin network is incentivized to waste resource competing for higher selfish reward.
Feroz Ahmad Ahmad, Prashant Kumar, Gulshan Shrivastava, Med Salim Bouhlel
ON 12 JANUARY 2009 a pseudonymous entity signed a transaction that instructed a distributed network to transfer a small amount of digital currency to Hal Finney, one ofthe key figures of the cypherpunk movement. After a few minutes, the transaction was recorded on a distributed public ledger, permanently updating the balance ofbothparties. This transactionâ the first Bitcoin transactionâmarked the beginning of a new era of decentralized payment systems, ushering in a variety of financial Services that do not depend on any centralized clearinghouse or other financial middleman. Bitcoin is regarded by many as a powerful technological innovation that could disrupt many sectors, in the realm of finance and beyond. But the underlying technology on which the network operates, the Bitcoin blockchain can do much more than that. Just as the internet did in the early-1990s, blockchain technology carries with it a whole new range of promises concerning how decentralization can support and promote individual freedoms and autonomy. Blockchain proponents believe that Bitcoin and other cryptocurrency platforms will revolutionize mechanisms of value exchange in the same way that the internet transformed information sharing, by providing a platform for people to exchange digital resources, in a secure and decentralized manner without the need to rely on any intermediary or trusted authority. But this revolutionary potential also carries with it serious implications for censorship, intellectual property, and the regulated flow of information. A blockchain is a decentralized database of transactions maintained by a distributed network of computers, which all contribute to the verification and the validation of transactions. Once accepted, these transactions are recorded inside a âblockâ of transactions, which incorporates a reference to previous blocks. This creates a long chain of blocksâa âblockchainââthat stores the history of all transactions in a chronological order. Every block contains information about a particular set of transactions, a reference to the preceding block in the blockchain, and the answer to a complex mathematical puzzle that is used to validate the data associated with that block. A copy of the blockchain is stored on every computer in the network, making it virtually impossible for anyone unilaterally to modify the data stored on this decentralized database: if anyone tries to modify any transaction the fraud will be immediately detected by all other network participants.
Open access
43 source records
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
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 Bitcoin backbone , and prove three of its fundamental properties which we call Common Prefix , Chain Quality, and Chain Growth in 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 call 2-for-1 proof-of-work (PoW) that has proven to be useful in the design of other PoW-based protocols.
Christian Decker, Jochen Seidel, Roger Wattenhofer
The Bitcoin system only provides eventual consistency. For everyday life, the time to confirm a Bitcoin transaction is prohibitively slow. In this paper we propose a new system, built on the Bitcoin blockchain, which enables strong consistency. Our system, PeerCensus, acts as a certification authority, manages peer identities in a peer-to-peer network, and ultimately enhances Bitcoin and similar systems with strong consistency. Our extensive analysis shows that PeerCensus is in a secure state with high probability. We also show how Discoin, a Bitcoin variant that decouples block creation and transaction confirmation, can be built on top of PeerCensus, enabling real-time payments. Unlike Bitcoin, once transactions in Discoin are committed, they stay committed.
The growing parallelism and heterogeneity of modern computing infrastructures such as High Performance Computing (HPC) platforms raises new challenges to their programmers and users. Additional requirements have emerged nowadays, such as minimizing the consumed energy, reducing the utilized system resources, or providing built-in reliability mechanisms. Therefore High Performance Computing (HPC) applications require adaptation mechanisms and then must avoid traditional monolithic centralized approaches in favor of novel autonomous, flexible and decentralized decision systems. In this context, we describe here a dynamic and flexible adaptation scheme based on a Multi-Agent System (MAS) to handle parallel or distributed executions in an HPC environment. More precisely, we model and extend the existing HPC middleware Kaapi to offer the power of the ParaMoise multi-agent organizational framework. Our proposed solution, named ParaMASK, relies on the similarities between ParaMoise workflow-based functional specifications and the Direct Acyclic Graph (DAG) representation of the distributed execution within Kaapi. As a result, ParaMASK permits to analyze and reorganize the scheduling of tasks that compose a program in an autonomous and decentralized way, while additionally handling dynamic adaptations (using task migration to fulfill energy consumption goals for example). The proposed solution was implemented on top of the existing Kaapi middleware and includes an optimized algorithm for the agent coordination. ParaMASK has been validated with a series of experiments on a real computational grid. Experimental results show a good scalability and an exceptional low overhead induced by the approach: less than 1.5% execution time increase with periodic coordinations every 15 seconds on 2662 cores.
Enas Al Kawasmi, Edin ArnautoviÄ, Davor SvetinoviÄ
ABSTRACT This paper presents a systemâofâsystems architecture model for a Decentralized Carbon Emissions Trading Infrastructure (DâCETI) with focus on privacy and system security goals. The structure and behavior are implemented as a solution to the problem of trading carbon emissions anonymously among the trading agents. Privacy and security of the trading agents and their carbon credits are the main requirements behind the architecture of DâCETI. The decentralized structure of multiple systems and distributed behavior are the two main features of DâCETI that distinguish it from the traditional carbon trading schemes and protocols. DâCETI is based on Bitcoin, a peerâtoâpeer digital currency with no central authority, and Open Transactions, a system that simplifies the use of cryptography in financial transactions. The architecture of DâCETI is evaluated and compared with the architecture of five other carbon emissions trading platforms.
Jelle van den Hooff, M. Frans Kaashoek, Nickolai Zeldovich
VerSum allows lightweight clients to outsource expensive computations over large and frequently changing data structures, such as the Bitcoin or Namecoin blockchains, or a Certificate Transparency log. VerSum clients ensure that the output is correct by comparing the outputs from multiple servers. VerSum assumes that at least one server is honest, and crucially, when servers disagree, VerSum uses an efficient conflict resolution protocol to determine which server(s) made a mistake and thus obtain the correct output.
With the vast increase in smartphones, there have been an increasing number of opportunities growing in the app industry. One in particular is the way we deal with money. There are huge overheads in the current payment systems around the world particularly in the United States, many of which include large transaction fees. Many new businesses have grown to solve these inefficiencies and create a new platform that provides a new user experience, security, and convenience among many other things. However, many of these platforms are still centralized, making them more susceptible to attacks. This thesis goes over the various methods of payments, starting from their origins and discusses their flaws and ways they are being improved. This study explains where payment platforms are going and how they line up against other platforms in terms of security and usability. We look at the origins of credit cards and why the US is lagging behind other countries in credit card security. Digital wallets like PayPal, Venmo, Square, etc. have done a remarkable job, but still have room for improvement in terms of security and usage. I try to solve these problems with the mobile application AnyCoin by bringing one platform that houses different types of digital wallets. The goal of this application was to grow a large user base and collect data off the transaction for future analysis and advertising. This study goes through an in depth analysis on the application from the iv perspective of merchants and consumers to understand what users are looking for in digital wallets. Decentralized platforms and crypto-currencies like Bitcoin have also created different ways to send money by creating a trustless system that does not depend on any central authority. I discuss what Bitcoin is and exactly how it works and the flaws in the current system. Mining is the process that puts Bitcoin into circulation and secures the network. However, as more customized hardware is released, Bitcoin will fall subject to becoming more centralized, and unfortunately become heavy regulated if it is to be used as a currency. Ethereum is a new technology that takes the concepts of Bitcoin and creates a platform for a developer to create a decentralized application. I create a few contracts that show how we can create a decentralized version of PayPal that works using other crypto- currencies. Ethereum is still in its alpha stage and has yet to
We give an explicit definition of decentralization and show you that\ndecentralization is almost impossible for the current stage and Bitcoin is the\nfirst truly noncentralized currency in the currency history. We propose a new\nframework of noncentralized cryptocurrency system with an assumption of the\nexistence of a weak adversary for a bank alliance. It abandons the mining\nprocess and blockchain, and removes history transactions from data\nsynchronization. We propose a consensus algorithm named Converged Consensus for\na noncentralized cryptocurrency system.\n
Describing, understanding, and modeling the emergent behavior of self-organizing software systems remains an open challenge. Such systems can solve problems in computing domains where traditional, centralized models are impractical or problematic, including ubiquitous and pervasive computing, peer-to-peer networks, large-scale grids, and Ultra-Large-Scale Systems. Self-organizing approaches have demonstrated great promise in building adaptive behavior into decentralized systems, enabling cooperative, autonomous self-management and the exploitation of the heterogeneity of system components. My investigation of self-organizing software systems has revolved around Myconet, an unstructured overlay protocol for peer-to-peer networks. Myconet takes inspiration from fungal growth patterns in order to build an efficient self-optimizing superpeer topology that can also rapidly self-heal in response to damage orattacks. Myconet has proven to be flexible, and has been used as a platform for the development of other self-organizing applications in large-scale distributed systems, including load-balancing in distributed service networks (Mycoload), and detection and mitigation of attacks against the overlay (Hormone-Inspired Topology Adaptation Protection [HITAP] and Self-Organized Degree Adaptation Protection [SODAP]). Each extension has given additional insights into the self-organizing dynamics of such systems, but has also shown the limitations of ad hoc approaches to the design and analysis of new applications. These experiences have led me to investigate formal tools and models that may provide the designer of a self-organizing system with early and accurate insight through augmented analytical power. This research selects a small set of synergistic modeling techniques, and builds an integrated approach to modeling for the design and validation of self-organizing software systems. These tools are used to model the core Myconet platform and its currently developed extensions, particularly focusing on the SODAP layer which provides self-protection features to a superpeer-based P2P overlay network. Once established, this modeling approach can be applied to the principled design of further Myconet extensions, as well as other self-organizing systems, thus advancing the understanding of how to model and engineer self-organization in software systems.
In this paper we put forward the Bounded Player Model for secure computation. In this new model, the number of players that will ever be involved in secure computations is bounded, but the number of computations has no a priori bound. Indeed, while the number of devices and people on this planet can be realistically estimated and bounded, the number of computations these devices will run can not be realistically bounded. We stress that in the Bounded Player model, in addition to no a priori bound on the number of sessions, there is no synchronization barrier, no trusted party, and simulation must be performed in polynomial time. In this setting, we achieve concurrent Zero Knowledge (cZK) with sub-logarithmic round complexity. Our security proof is (necessarily) non-black-box, our simulator is âstraight-lineâ and works as long as the number of rounds is Ï(1). We further show that unlike previously studied relaxations of the standard model (e.g., bounded number of sessions, timing assumptions, super-polynomial simulation), concurrent-secure computation is still impossible to achieve in the Bounded Player model. This gives evidence that our model is âcloserâ to the standard model than previously studied models, and study of this model might shed light on constructing round efficient concurrent zero-knowledge in the standard model as well.
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.
Abstract Distributed applications are difficult to program reliably and securely. Dependently typed functional languages promise to prevent broad classes of errors and vulnerabilities, and to enable program verification to proceed side-by-side with development. However, as recursion, effects, and rich libraries are added, using types to reason about programs, specifications, and proofs becomes challenging. We present F*, a full-fledged design and implementation of a new dependently typed language for secure distributed programming. Our language provides arbitrary recursion while maintaining a logically consistent core; it enables modular reasoning about state and other effects using affine types; and it supports proofs of refinement properties using a mixture of cryptographic evidence and logical proof terms. The key mechanism is a new kind system that tracks several sub-languages within F* and controls their interaction. F* subsumes two previous languages, F7 and Fine. We prove type soundness (with proofs mechanized in Coq) and logical consistency for F*. We have implemented a compiler that translates F* to .NET bytecode, based on a prototype for Fine. F* provides access to libraries for concurrency, networking, cryptography, and interoperability with C#, F#, and the other .NET languages. The compiler produces verifiable binaries with 60% code size overhead for proofs and types, as much as a 45x improvement over the Fine compiler, while still enabling efficient bytecode verification. We have programmed and verified nearly 50,000 lines of F* including new schemes for multi-party sessions; a zero-knowledge privacy-preserving payment protocol; a provenance-aware curated database; a suite of web-browser extensions verified for authorization properties; a cloud-hosted multi-tier web application with a verified reference monitor; the core F* typechecker itself; and programs translated to F* from other languages such as F7 and JavaScript.
Shlomi Dolev, Panagiota N. Panagopoulou, Mikaël Rabie, Elad M. Schiller · 5 authors
Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.
Zero-knowledge proofs protocols are effective interactive methods to prove a node's identity without disclosing any additional information other than the veracity of the proof. They are implementable in several ways. In this thesis, I investigate the graph isomorphism based zero-knowledge proofs protocol. My experiments and analyses suggest that graph isomorphism can easily be solved for many types of graphs and hence is not an ideal solution for implementing ZKP.
Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström
We show that only languages in BPP have public-coin black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This result holds both in the plain model (without any setup) and in the bare public key model (where the prover and the verifier have registered public keys). We complement this result by constructing a public-coin black-box zero-knowledge proof based on one-way functions that remains secure under any a priori bounded number of concurrent executions. A key step (of independent interest) in the analysis of our lower bound shows that any public-coin protocol, when repeated sufficiently in parallel, satisfies a notion of âresettable soundnessâ if the verifier picks its random coins using a pseudorandom function.
We present an efficient simultaneous broadcast protocol Μ-SimCast that allows n players to announce independently chosen values, even if up to t < n players are corrupt. Independence is guaranteed in the partially syn-2 chronous communication model, where communication is structured into rounds, while each round is asynchronous. The Μ-SimCast protocol is more efficient than previous constructions. For repeated executions, we reduce the communication and computation complexity by a factor O(n). Combined with a deterministic extractor, Μ-SimCast provides a particularly efficient solution for distributed coin-flipping. The protocol does not require any zero-knowledge proofs and is shown to be secure in the standard model under the Decisional Diffie Hellman assumption.
Esoteric protocols, such as electronic cash, electronic voting and selective disclosure protocols, use special message constructors that are not widely used in other types of protocols (for example, in authentication protocols). These message constructors include blind signatures, commitments and zero-knowledge proofs. Furthermore, a standard formalization of the Dolev-Yao intruder [6] does not take into account these message constructors, nor does it consider some types of attacks (such as privacy attacks, brute-force dictionary attacks and known-plaintext attacks) that esoteric as well as other types of protocols are designed to protect against. This paper aims to present an extension of typed MSR [3, 4] in order to formally specify the needed message constructors, as well as the capabilities of a Dolev-Yao intruder designed to attack esoteric protocols.
Blockchain technology has been gaining great interest from a variety of sectors including healthcare, supply chain, and cryptocurrencies. However, Blockchain suffers from a limited ability to scale (i.e., low throughput and high latency). Several solutions have been proposed to tackle this. In particular, sharding has proved to be one of the most promising solutions to Blockchain's scalability issue. Sharding can be divided into two major categories: (1) Sharding-based Proof-of-Work (PoW) Blockchain protocols, and (2) Sharding-based Proof-of-Stake (PoS) Blockchain protocols. The two categories achieve good performances (i.e., good throughput with a reasonable latency), but raise security issues. This article focuses on the second category. In this paper, we start by introducing the key components of sharding-based PoS Blockchain protocols. We then briefly introduce two consensus mechanisms, namely PoS and practical Byzantine Fault Tolerance (pBFT), and discuss their use and limitations in the context of sharding-based Blockchain protocols. Next, we provide a probabilistic model to analyze the security of these protocols. More specifically, we compute the probability of committing a faulty block and measure the security by computing the number of years to fail. We achieve a number of years to fail of approximately 4000 in a network of 4000 nodes, 10 shards, and a shard resiliency of 33%.
Asynchronous collaborative applications and systems have to deal with complexities associated with interaction nature, idiosyncrasy of groups and technical and administrative issues. Inclusion of requirements derived from them is costly (in time, resources and economically). Existing solutions addresses asynchronous collaboration via simplification of requirements and by using centralized models. In this paper we present LaCOLLA, a fully decentralized infrastructure for building collaborative applications that provides general purpose collaborative functionalities. The provision of those functionalities will avoid applications deal with most of complexities derived from groups and its members, what will help inclusion of collaborative aspects. The implementation of LaCOLLA follows the peer-to-peer paradigm and pays special attention to autonomy of its members and to self-organization of the components of the infrastructure. Another key aspect is that resources (e.g. storage) and services (e.g. authorization) are provided by its members (avoiding dependency from agents not belonging to group).