Alexander Chepurnoy, Mario Larangeira, Alexander Ojiganov
Bitcoin is the first successful decentralized global digital cash system. Its mining process requires intense computational resources, therefore its usefulness remains a disputable topic. We aim to solve three problems with Bitcoin and other blockchain systems of today by repurposing their work. First, space to store a blockchain is growing linearly with number of transactions. Second, a honest node is forced to be irrational regarding storing full blocks by a way implementations are done. Third, a trustless bootstrapping process for a new node involves downloading and processing all the transactions ever written into a blockchain. In this paper we present a new consensus protocol for Bitcoin-like peer-to-peer systems where a right to generate a block is given to a party providing non-interactive proofs of storing a subset of the past state snapshots. Unlike the blockchain systems in use today, a network using our protocol is safe if the nodes prune full blocks not needed for mining. We extend the GKL model to describe our Proof-of-Work scheme and a transactional model modifications needed for it. We provide a detailed analysis of our protocol and proofs of its security.
Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi · 6 authors
While showing great promise, Bitcoin requires users to wait tens of minutes\nfor transactions to commit, and even then, offering only probabilistic\nguarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol\nthat leverages scalable collective signing to commit Bitcoin transactions\nirreversibly within seconds. ByzCoin achieves Byzantine consensus while\npreserving Bitcoin's open membership by dynamically forming hash\npower-proportionate consensus groups that represent recently-successful block\nminers. ByzCoin employs communication trees to optimize transaction commitment\nand verification under normal operation while guaranteeing safety and liveness\nunder Byzantine faults, up to a near-optimal tolerance of f faulty group\nmembers among 3f + 2 total. ByzCoin mitigates double spending and selfish\nmining attacks by producing collectively signed transaction blocks within one\nminute of transaction submission. Tree-structured communication further reduces\nthis latency to less than 30 seconds. Due to these optimizations, ByzCoin\nachieves a throughput higher than PayPal currently handles, with a confirmation\nlatency of 15-20 seconds.\n
Bitcoin is the first decentralized peer-to-peer (P2P) electronic currency. It was created in November 2008 by Satoshi Nakamoto. Nakamoto released the first implementation of the protocol in an open source client software and the genesis of bitcoins began on January 9th 2009. The Bitcoin protocol is based on clever ideas which solve a form of the Byzantine Generals Problem and sets the foundation for Decentralized Trust Protocols. Still in its infancy, the currency and the protocol have the potential to disrupt the international financial system and other sectors where business is based on trusted third parties. The security of the bitcoin protocol relies on strong cryptography and one way hashing algorithms.
I present the design and implementation of a novel anti-malware environment called BitAV. BitAV allows for the decentralization of the update and maintenance mechanisms of the software, traditionally performed by a central host, and uses a staggered scanning mechanism in order to improve performance. The peer-to-peer network maintenance mechanism lowered the average update propagation speed by 500% and is far less susceptible to targeted denial-of-service attacks. The feedforward scanning mechanism significantly improved end-to-end performance of the malware matching system, to a degree of an average 14x increase, by decomposing the file matching process into efficient queries that operate in verifiably constant time.
Distributed consensus (aka Byzantine agreement [Pease, Shostak & Lamport, 1980]) is one of the fundamental problems in fault-tolerant distributed computing and cryptographic protocols. It requires correct participants (parties) to reach agreement on initially held values despite the arbitrary behavior of some of them, with the additional requirement (known as Validity) that if all the correct participants start off with the same value, then that must be the decision value. The problem has been studied extensively in both the unconditional setting (where no assumptions are made about the computational power of the adversary) and the cryptographic setting, and efficient (i.e., polynomial-time) solutions exist tolerating the optimal number of misbehaving parties and running in the optimal number of rounds, on networks with pairwise authenticated channels. In many interesting scenarios, however, such as "peer-to-peer" networks, where parties come and go as they please and there are no prior relations among them, such infrastructure (pairwise authenticated channels, public-key infrastructure) is unavailable, thus raising the question whether anything "interesting" can be achieved. In this talk we answer this question in the affirmative, presenting two new probabilistic consensus protocols based on "proofs of work" (POWs, aka "moderately hard functions," "cryptographic puzzles" [Dwork & Naor, 1992]), the technology underlying Bitcoin, the first and most popular decentralized cryptocurrency to date. (In Bitcoin, POWs are implemented using the SHA-256 cryptographic hash function, by finding preimages that produce values in a given smaller domain.) In more detail, we first extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two fundamental properties of its "blockchain" approach which we call "common prefix" and "chain quality." The consensus protocols can then be built as applications on top of the backbone protocol, with the Agreement and Validity properties following from common prefix and chain quality, respectively. The first protocol works assuming the adversary's hashing power is bounded by 1/3 of the network's total hashing power. The second consensus protocol is more elaborate, relies on the notion of robust transaction ledgers, which capture the essence of Bitcoin's operation as a cryptocurrency, and works assuming the adversary's hashing power is strictly less than 1/2.
Blockchains and Byzantine Fault Tolerance form the basis of decentralized currencies and ledgers such as Bitcoin, Ripple, ZeroCash, and Ethereum. A large slate of literature has focused on the currency aspects (e.g. anonymity, independence from central banks, etc.). We argue that, as-far-as Distributed Payment Transactions Networks (PTNs) are concerned, there are other, possibly more interesting, properties. This paper provides a systematic review of both traditional PTNs and their analogues in decentralized ledgers and associates different technological features to the corresponding business and financial requirements. We provide a conceptual classification of the key properties (value creation, payment promise, transaction fulfillment, and value preservation). We map existing (distributed) PTNs into the classification showing different alternatives are possible. Furthermore, the ideas behind distributed ledgers can be extended beyond payments and contracts. We illustrate the idea of derivatives-contracts-as-programs that are marked to market (or an account that is margined) automatically by computations run on, and whose ownership transitions are recorded, in a distributed payment network.
The past several years have seen the surprising and rapid rise of Bitcoin and other “cryptocurrencies.” These are decentralized peer-to-peer networks that allow users to transmit money, tocompose financial instruments, and to enforce contracts between mutually distrusting peers, andthat show great promise as a foundation for financial infrastructure that is more robust, efficientand equitable than ours today. However, it is difficult to reason about the security of cryptocurrencies. Bitcoin is a complex system, comprising many intricate and subtly-interacting protocol layers. At each layer it features design innovations that (prior to our work) have not undergone any rigorous analysis. Compounding the challenge, Bitcoin is but one of hundreds of competing cryptocurrencies in an ecosystem that is constantly evolving. The goal of this thesis is to formally reason about the security of cryptocurrencies, reining in their complexity, and providing well-defined and justified statements of their guarantees. We provide a formal specification and construction for each layer of an abstract cryptocurrency protocol, and prove that our constructions satisfy their specifications. The contributions of this thesis are centered around two new abstractions: “scratch-off puzzles,” and the “blockchain functionality” model. Scratch-off puzzles are a generalization of the Bitcoin “mining” algorithm, its most iconic and novel design feature. We show how to provide secure upgrades to a cryptocurrency by instantiating the protocol with alternative puzzle schemes. We construct secure puzzles that address important and well-known challenges facing Bitcoin today, including wasted energy and dangerous coalitions. The blockchain functionality is a general-purpose model of a cryptocurrency rooted in the “Universal Composability” cryptography theory. We use this model to express a wide range of applications, including transparent “smart contracts” (like those featured in Bitcoin and Ethereum), and also privacy-preserving applications like sealed-bid auctions. We also construct a new protocol compiler, called Hawk, which translates user-provided specifications into privacy-preserving protocols based on zero-knowledge proofs.
Bitcoin scripts currently do not enable loops. Therefore, they are commonly considered to be not Turing Complete. This limits the types of algorithms the Bitcoin scripts can execute to linear or tree-like instructions. This white paper describes the invention of an Oracle module that: • Continuously monitors the state of Blockchain. • Makes decisions based on the current state. • Generates the next set of transactions to be written onto the Blockchain. The above processes is executed continuously by the Oracle in parallel to the Blockchain network. It therefore implements looping constructs that makes the combined Oracle and Blockchain system Turing Complete. As old blocks cannot be erased from the Blockchain, but new blocks can be added, the Oracle and the Blockchain will work as a non-erasable Turing Machine as described in Minsky et al. (1967). We will discuss the use of the Oracle in applications including: • Distributed data storage • Distributed computing • The control of drones. We will also describe how metadata storage and digital signature authorization on the Blockchain can be useful features for implementing these applications.
A fundamental open problem in the area of blockchain protocols is whether the Bitcoin protocol is the only solution for building a secure transaction ledger. A recently proposed and widely considered alternative is the \GHOST protocol which, notably, was proposed to be at the core of Ethereum as well as other recent proposals for improved Bitcoin-like systems. % The \GHOST variant is touted as offering superior performance compared to Bitcoin (potentially offering block production speed up by a factor of more than 40) without a security loss. Motivated by this, in this work, we study from a provable security point of view the \GHOST protocol.<br/><br/>We introduce a new formal framework for the analysis of blockchain protocols that relies on trees (rather than chains) and we showcase the power of the framework by providing a unified description of the \GHOST and Bitcoin protocols, the former of which we extract and formally describe. We then prove that \GHOST implements a ``robust transaction ledger'' (i.e., possesses liveness and persistence) and hence it is a provably secure alternative to Bitcoin; moreover, our bound for the liveness parameter is superior to that proven for the bitcoin backbone in line with the original expectation for \GHOST. Our proof follows a novel methodology for establishing that \GHOST is a robust transaction ledger compared to previous works, which may be of independent interest and can be applicable to other blockchain variants.
Fault-tolerant consensus has been studied extensively in the literature, because it is one of the most important distributed primitives and has wide applications in practice. This paper surveys important results on fault-tolerant consensus in message-passing networks, and the focus is on results from the past decade. Particularly, we categorize the results into two groups: new problem formulations and practical applications. In the first part, we discuss new ways to define the consensus problem, which includes larger input domains, link fault models, different network models . . . etc, and briefly discuss the important techniques. In the second part, we focus on Crash Fault-Tolerant (CFT) systems that use Paxos or Raft, and Byzantine Fault-Tolerant (BFT) systems. We also discuss Bitcoin, which can be related to solving Byzantine consensus in anonymous systems, and compare Bitcoin with BFT systems and Byzantine consensus.
Peer-to-peer networks are often large, collaborative networks where peers can join openly. The essence of a collaborative, distributed system is that every node performs tasks for other nodes. The peers often help in singular interactions and without direct reciprocity. Malicious peers can abuse and freeride the public goods. The network without countermeasures can fall into a tragedy of the commons where no one helps another and everyone takes advantage of the generosity of peers. Only when the reputation of a peer is publicly available at scale and peers trust this reputation can the network escape the problems of freeriding and attain high utility for all participants. This thesis focuses on designing and implementing the first step of a tamper proof reputation system within Tribler. Tribler is a peer-to-peer BitTorrent system developed at the Delft University of Technology. This first step, made by this thesis, is to create MultiChain, a proof-of-concept bookkeeping system. MultiChain tracks the upload and download amounts of peers to eliminate freeriding. Multi-Chain is cryptographically protected and validated. The bookkeeping system has to be scalable to be publicly available and be able to process enough transactions. The system has to work in an asynchronous network. A new design of a distributed data structure that can be used as a ledger is introduced by this thesis. This first step with MultiChain is already more resilient to tampering than previous work, like BarterCast. BarterCast has no security measures against tampering records. The design of MultiChain is to have a chain of blocks for every peer as a ledger. Peers are participants of a peer-to-peer network. A block contains a transaction between two peers. This block is shared and added to both chains. This makes both chains of the peers intertwined and entangled at a shared block. The proposed design abandons the typical global, full ledger. The protocol of creating these blocks between peers is described. The problems faced by MultiChain in an asynchronous network are explained. The thesis proposes how the design can overcome these problems by only allowing atomic operations to be performed on the chain and to introduce unfinished blocks in the chain. The implementation of the design is tested and experimented with within this thesis to validate it to work correctly. Furthermore, a number of weak points are discussed. These weak points have to be addressed in the future to create a tamper proof reputation system.
Kriptovalute su digitalni novac utemeljen na kriptografiji i decentraliziranom sustavu. Postoje samo u elektroničkom obliku kao jedinstveni digitalni novčići ("tokeni"). Iza njih ne stoji autoritet države niti ih je moguće svojevoljno proizvesti. Rad se fokusira na značajkama, postavkama, razvoju i svim međuodnosima važnih ekonomskih faktora koji utječu na kriptovalute. U prvom poglavlju navedena su obilježja kriptovaluta. Drugo poglavlje daje primjere i govori o primjeni kriptovaluta u svakodnevnom životu. U trećem poglavlju je raspravljano o trenutnim i budućim regulacijama najmoćnijih zemalja svijeta (G20) , kao i njihovoj zajedničkoj suradnji u želji za jedinstvenim i standardiziranim pravilima, a sve u svrhu što kvalitetnijeg nadzora nad kriptovalutama kako bi se spriječile malverzacije i zaštitili potrošači. Četvrto poglavlje govori o inicijalnoj ponudi kovanica, a peto poglavlje je namijenjeno sigurnosti kriptovaluta. Cilj istraživanja je utvrditi koliko je studentska populacija upoznata i usmjerena prema novim oblicima digitalnog novca, koje značajke kriptovaluta smatraju pozitivnima, a koje negativnima i u kojoj su mjeri investirali ili su spremni investirati dio svojih ulaganja u kriptovalute i sl. Metode istraživanja korištene u radu su kompilacija na temelju proučavanja postojeće literature o temi rada, prikupljanje i analiza podataka vezanih uz kriptovalute, ponajprije podataka vezanih uz cijene i tržišnu kapitalizaciju, anketiranje studenata Ekonomskog fakulteta u Rijeci i metoda dedukcije putem koje su pokazane sve važne karakteristike i obilježja kriptovaluta. Na temelju provedene ankete u kojoj je sudjelovalo 90 studenata Ekonomskog fakulteta u Rijeci zaključak toga dijela istraživanja je da je mlada populacija dobro upoznata s kriptovalutama i njenim glavnim značajkama, ali i određenim nedostatkom informiranosti o tehnologiji (trećina studenata nije čula za pojam "blockchain") i nedovoljnoj odlučnosti oko investiranja i trgovanja u kriptovalute. Povrh toga, dokazan je i negativan utjecaj hakerskih napada i određenih kriminalnih radnji, kao i nestabilnost tržišne cijene na povjerenje studenata, ali i ukupne populacije vezane uz globalni financijski sustav u kriptovalute. Ishod istraživanja omogućio je da zaključimo kako su kriptovalute trenutno u ranoj fazi razvoja i nisu se dovoljno implementirale za široku primjenu u trgovini roba i usluga ili općenito kao sredstvo razmjene. Faktor koji je uključen u istraživanje kako bi opisao veličinu, odnosno obujam neke kriptovalute je tržišna kapitalizacija u dolarima. Temeljna ideja ovog rada je informirati čitatelja o pozitivnim i negativnim značajkama koje se se vežu uz kriptovalute. Na taj način čitatelji će biti bolje informirani i educirani o potencijalnom riziku ulaganja u kriptovalute, kao i većoj razini zaštite prilikom posjedovanja neke digitalne valute.
Kaylash Chaudhary, Ansgar Fehnker, Jaco van de Pol, Mariëlle Stoelinga
Bitcoin is a popular digital currency for online payments, realized as a decentralized peer-to-peer electronic cash system. Bitcoin keeps a ledger of all transactions; the majority of the participants decides on the correct ledger. Since there is no trusted third party to guard against double spending, and inspired by its popularity, we would like to investigate the correctness of the Bitcoin protocol. Double spending is an important threat to electronic payment systems. Double spending would happen if one user could force a majority to believe that a ledger without his previous payment is the correct one. We are interested in the probability of success of such a double spending attack, which is linked to the computational power of the attacker. This paper examines the Bitcoin protocol and provides its formalization as an UPPAAL model. The model will be used to show how double spending can be done if the parties in the Bitcoin protocol behave maliciously, and with what probability double spending occurs.
Ayush Dubey, Greg D. Hill, Robert Escriva, Emin Gün Sirer
Graph databases have become an increasingly common infrastructure component. Yet existing systems either operate on offline snapshots, provide weak consistency guarantees, or use expensive concurrency control techniques that limit performance. In this paper, we introduce a new distributed graph database, called Weaver, which enables efficient, transactional graph analyses as well as strictly serializable ACID transactions on dynamic graphs. The key insight that allows Weaver to combine strict serializability with horizontal scalability and high performance is a novel request ordering mechanism called refinable timestamps. This technique couples coarse-grained vector timestamps with a fine-grained timeline oracle to pay the overhead of strong consistency only when needed. Experiments show that Weaver enables a Bitcoin blockchain explorer that is 8x faster than Blockchain.info, and achieves 12x higher throughput than the Titan graph database on social network workloads and 4x lower latency than GraphLab on offline graph traversal workloads.
A purely anti-node non-peer-to-peer version of electronic money would allow online payments to be sent directly from one person to another without going through a financial institution and node promoters such as digital and gold-miners. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using an anti-node non-peer-to-peer network which is not only distributed but encrypted to the core of the gene. The network timestamps transactions by hashing them into an ongoing chain of hash-based genesis-concept combined with military grade chain-reinforced-encryption using AES, SHA, RSA and custom algos, forming a record that cannot be changed without redoing the genesis-concept. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcasted on a best effort basis, and nodes can leave and re-join the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone. However, in the proposed model, the central authority server itself acts as the node and represents the network transport layer by itself which enables it to not to be dependent on individual nodes, and the crypto-formulation continuous at server level. By this process, the dependency on nodes are ruled out and the server (the executioner, in this case) gets all the bits combined in one platform from the beginning to the end using enhanced salting layer, providing the facility of de-centralized defacto standard e-payments within nano seconds or less i.e., account to account transfer using one central block processing schema.
Kourosh Davarpanah, Dan Kaufman, Ophelie Pubellier
NeuCoin is a decentralized peer-to-peer cryptocurrency derived from Sunny\nKing's Peercoin, which itself was derived from Satoshi Nakamoto's Bitcoin. As\nwith Peercoin, proof-of-stake replaces proof-of-work as NeuCoin's security\nmodel, effectively replacing the operating costs of Bitcoin miners\n(electricity, computers) with the capital costs of holding the currency.\nProof-of-stake also avoids proof-of-work's inherent tendency towards\ncentralization resulting from competition for coinbase rewards among miners\nbased on lowest cost electricity and hash power.\n NeuCoin increases security relative to Peercoin and other existing\nproof-of-stake currencies in numerous ways, including: (1) incentivizing nodes\nto continuously stake coins over time through substantially higher mining\nrewards and lower minimum stake age; (2) abandoning the use of coin age in the\nmining formula; (3) causing the stake modifier parameter to change over time\nfor each stake; and (4) utilizing a client that punishes nodes that attempt to\nmine on multiple branches with duplicate stakes.\n This paper demonstrates how NeuCoin's proof-of-stake implementation addresses\nall commonly raised "nothing at stake" objections to generic proof-of-stake\nsystems. It also reviews many of the flaws of proof-of-work designs to\nhighlight the potential for an alternate cryptocurrency that solves these\nflaws.\n
Bitcoin is an emerging crypto-currency, which is wrapped in mystery and controversy. The goal is to transform how we transfer payments. The current approach for sending money from one remote party to another is via bank deposit and transfer by check or bank transfer. PayPal and other services were developed to provide faster payments to verified individuals, but each layer in the transaction adds time, cost, and/or risk to the transaction. Users of this new digital currency proclaim the benefits of security, anonymity, and efficiency for making transactions. The functionality and structure of the Bitcoin Network is complex and often attacked for not being a suitable replacement for currency. An independent understanding can be developed of the composite Bitcoin Financial Systems of Systems architecture by considering the challenges any System of System would face. A functional analysis, employing the Systems Modeling Language (SysML), is performed on the Bitcoin System of Systems architecture to help gain an understanding of the structure and functionality, and how that relates to the key actors and use cases, for determining if the users’ expectations are aligned with the architecture.
The advent of Bitcoin in 2009 has not only introduced Cryptocurrencies and lead to a new digitization movement in the financial, especially payments industry but also made way for a new breed of innovative technologies based on decentralized digital currencies. Generally, decentralized consensus systems could change the very nature of how companies, organizations and individuals are built and interact with each other. Decentralized consensus systems, decentralized applications and smart contracts provide the conceptual framework as well as the technological basis to establish predefined, incorruptible protocols and contracts to organize human behavior and interconnectedness. However, the technical protocols and implementations are quite complex and practitioners as well as interdisciplinary researchers not familiar with cryptography, network protocols or decentralized networks are struggling to find access to these concepts and grasp their potential. To fill this gap, we develop a comprehensive taxonomy of decentralized consensus systems in order to provide a tool for researchers and practitioners alike to facilitate classification and analysis of emerging technologies in the field of "Crypto 2.0", the next level of innovation beyond cryptocurrencies.