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.
Cryptographic accumulators allow to succinctly represent a set by an accumulation value with respect to which short non-membership proofs about the set can be efficiently constructed and verified. Traditionally, their security captures soundness but offers no privacy: Convincing proofs reliably encode set membership, but they may well leak information about the accumulated set.
In this paper we put forward a strong privacy-preserving enhancement by introducing and devising zero-knowledge accumulators that additionally provide hiding guarantees: Accumulation values and proofs leak nothing about a dynamic set that evolves via element insertions/deletions. We formalize the new property using the standard real-ideal paradigm, namely demanding that an adaptive adversary with access to query/update oracles, cannot tell whether he interacts with honest protocol executions or a simulator fully ignorant of the set even of the type of updates on it. We rigorously compare the new primitive to existing ones for privacy-preserving verification of set membership or other relations and derive interesting implications among related security definitions, showing that zero-knowledge accumulators offer stronger privacy than recent related works by Naor et al. [TCCi¾?2015] and Derler et al. [CT-RSAi¾?2015]. We construct the first dynamic universal zero-knowledge accumulator that we show to be perfect zero-knowledge and secure under the q-Strong Bilinear Diffie-Hellman assumption.
Finally, we extend our new privacy notion and our new construction to provide privacy-preserving proofs also for an authenticated dynamic set collection--a primitive for efficiently verifying more elaborate set operations, beyond set-membership. We introduce a primitive that supports a zero-knowledge verifiable set algebra: Succinct proofs for union, intersection and set difference queries over a dynamically evolving collection of sets can be efficiently constructed and optimally verified, while--for the first time--they leak nothing about the collection beyond the query result.
Carlos Pérez-Leguízamo, Pedro Josue Hernandez-Torres, Juan Sebastian Guadalupe Godinez-Borja, Victor TAPIA-TEC
Recently, the Services Oriented Architectures (SOA) have been recognized as the key to the integration and interoperability of different applications and systems that coexist in an organization. However, even though the use of SOA has increased, some applications are unable to use it. That is the case of mission critical information applications, whose requirements such as high reliability, non-stop operation, high flexibility and high performance are not satisfied by conventional SOA infrastructures. In this article we present a novel approach of combining SOA with Autonomous Decentralized Systems (ADS) in order to provide an infrastructure that can satisfy those requirements. We have named this infrastructure Autonomous Decentralized Service Oriented Architecture (ADSOA). We present the concept and architecture of ADSOA, as well as the Loosely Couple Delivery Transaction and Synchronization Technology for assuring the data consistency and high reliability of the application. Moreover, a real implementation and evaluation of the proposal in a mission critical information system, the Uniqueness Verifying Public Key Infrastructure (UV-PKI), is shown in order to prove its effectiveness.
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.
An active research trend is to exploit the consensus mechanism of cryptocurrencies to secure the execution of distributed applications. In particular, some recent works have proposed fair lotteries which work on Bitcoin. These protocols, however, require a deposit from each player which grows quadratically with the number of players. We propose a fair lottery on Bitcoin which only requires a constant deposit.
Nakamoto’s famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents “sybil attacks” (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. “moderately hard functions”) introduced by Dwork and Naor (Crypto’92).
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.
Recent blockchain-technology related innovations enable the governance of collaborating decentralized autonomous organizations (DAO) to engage in agile business-network collaborations that are based on the novel concept of smart contracting. DAOs utilize service-oriented cloud computing in a loosely coupled collaboration lifecycle with the main steps of setup, enactment, possible rollbacks and finally, an orderly termination. This lifecycle supports the selection of services provided and used by DAOs, smart contract negotiations, and behavior monitoring during enactment with the potential for breach management. Based on a sound understanding of the collaboration lifecycle in a Governance- as-a-Service (GaaS)-platform, a new type of conflict management must safeguard business-semantics induced consistency rules. This conflict management involves breach detection with recovery aspects. To fill the detected gap, we employ a formal design-notation that comprises the definition of structural and behavioral properties for exploring conflict-related exception- and compensation management during a decentralized collaboration. With the formal approach, we generate a highly dependable DAO-GaaS conflict model that does not collapse under left-behind clutter such as orphaned processes and exponentially growing database entries that require an unacceptable periodic GaaS reset.
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.
Mobile agent brings new concept on programming, especially on distributed computing paradigm. It attracts great interest because of its mobility, autonomy and persistence. But it also brings security issues i.e. insecure networks, malicious agents, malicious hosts and malicious users. One most difficult issues is protecting mobile agent from malicious host because mobile agent execute its code on host so that host can do many things to manipulate data, code and control flow of mobile agent. This paper proposes mobile-agent's self-reliant host security examination so that mobile agent is able to identify malicious host. In this proposed scheme, every hosts must have signature in blinded form in order to ensure unauthorized host cannot use this signature. This signature serves to distinguish malicious hosts with trusted host. When mobile agent arrives at new host, it will check validation of host's signature. Mobile agent also gives challenge to host, and host has to give a valid response. If host cannot give valid signature and response, mobile agent will identify this host as malicious host and return to its previous host. Zero knowledge proof of knowledge is used on challenge-response phase so that private keys cannot be revealed.
We show that equivocation, i.e., making conflicting statements to others in a distributed protocol, can be monetarily disincentivized by the use of crypto-currencies such as Bitcoin. To this end, we design completely decentralized non-equivocation contracts, which make it possible to penalize an equivocating party by the loss of its money. At the core of these contracts, there is a novel cryptographic primitive called accountable assertions, which reveals the party's Bitcoin credentials if it equivocates. Non-equivocation contracts are particularly useful for distributed systems that employ public append-only logs to protect data integrity, e.g., in cloud storage and social networks. Moreover, as double-spending in Bitcoin is a special case of equivocation, the contracts enable us to design a payment protocol that allows a payee to receive funds at several unsynchronized points of sale, while being able to penalize a double-spending payer after the fact.
Loi Luu, Jason Teutsch, Raghav Kulkarni, Prateek Saxena
Cryptocurrencies like Bitcoin and the more recent Ethereum system allow users to specify scripts in transactions and contracts to support applications beyond simple cash transactions. In this work, we analyze the extent to which these systems can enforce the correct semantics of scripts. We show that when a script execution requires nontrivial computation effort, practical attacks exist which either waste miners' computational resources or lead miners to accept incorrect script results. These attacks drive miners to an ill-fated choice, which we call the verifier's dilemma, whereby rational miners are well-incentivized to accept unvalidated blockchains. We call the framework of computation through a scriptable cryptocurrency a consensus computer and develop a model that captures incentives for verifying computation in it. We propose a resolution to the verifier's dilemma which incentivizes correct execution of certain applications, including outsourced computation, where scripts require minimal time to verify. Finally we discuss two distinct, practical implementations of our consensus computer in real cryptocurrency networks like Ethereum.
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.