In the past few years, blockchain thechnologies have sparked a lot of interest in the scientific and businness communities. The working Bitcoin blockchain has spawned a number of scientific research on the technology, security and reliability of the model. It managed to generate a new kind of economy with a market cap of around $ 300 billion at its peak. This article aims to elaborate on the development of blockchain technologies, to discuss the main problems, as well as to show various solutions.
This paper introduces a new consensus protocol, so-called \emph{\stair}, for fast consensus in DAG-based trustless system. In \stair, we propose a new approach to creating local block DAG, namely \emph{x-DAG} (cross-DAG), on each node. \emph{\stair} protocol is based on our Proof-of-Stake StakeDag framework \cite{stakedag} that distinguishes participants into users and validators by their stake. Both users and validators can create and validate event blocks. Unlike StakeDag's DAG, x-DAG ensures that each new block has to have parent blocks from both Users and Validators to achieve more safety and liveness. Our protocol leverages a pool of validators to expose more validating power to new blocks for faster consensus in a leaderless asynchronous system. Further, our framework allows participants to join as observers / monitors, who can retrieve DAG for post-validation, but do not participate in onchain validation.
This paper examines, with the help of a theoretical setting, the properties of two blockchain consensus protocols, namely the Proof of Work (PoW) and the Proof of Stake (PoS) protocol in the management of a digital local complementary currency or a network of digital local currencies. The model includes a control (by the issuer of the currency) of advantages derived from the use of a local currency by heterogeneous consumers and a determination of rewards for heterogeneous validators and miners. It also considers the resilience of these protocols to attacks conducted by an individual or a pool of validators or miners. Our results share similarities with an ordinary crypto-currency system and show that there is support for the PoS protocol for small communities of local complementary currencies, whereas the PoW appears to be more advantageous when the size of the communities is significantly large. JEL Classification: E42, D91, L86, O31
Although Bitcoin is mostly used as a decentralized application to transfer cryptocurrency, over the last ten years there have been several studies on how to exploit Bitcoin to execute smart contracts. These are computer protocols which allow users to exchange bitcoins according to complex pre-agreed rules. Some of these studies introduce formal models of Bitcoin contracts, which specify their behaviour in non-ambiguous terms, in some cases providing tools to automatically verify relevant contract properties. In this paper we survey the formal models proposed in the scientific literature, comparing their expressiveness and applicability in the wild.
This paper presents a new consensus protocol based on verifiable delay function. First, we introduce the concept of verifiable delay puzzle (VDP), which resembles the hashing puzzle used in the PoW mechanism but can only be solved sequentially. We then present a VDP implementation based on the continuous verifiable delay function. Further, we show that VDP can be combined with the Nakamoto consensus in a proof-of-stake/proof-of-delay hybrid protocol. We analyze the persistence and liveness of the protocol, and show that compared to PoW, our proposal consumes much less energy; compared to BFT leader-election based consensus algorithms, our proposal achieves better resistance to long-range attacks and DoS attacks targeting the block proposers.
A. Pinar Ozisik, Gavin Andresen, Brian Neil Levine, Darren Tapp · 6 authors
We introduce Graphene, a method and protocol for interactive set reconciliation among peers in blockchains and related distributed systems. Through the novel combination of a Bloom filter and an Invertible Bloom Lookup Table (IBLT), Graphene uses a fraction of the network bandwidth used by deployed work for one- and two-way synchronization. We show that, for this specific problem, Graphene is more efficient at reconciling n items than using a Bloom filter at the information theoretic bound. We contribute a fast and implementation-independent algorithm for parameterizing an IBLT so that it is optimally small in size and meets a desired decode rate with arbitrarily high probability. We characterize our performance improvements through analysis, detailed simulation, and deployment results for Bitcoin Cash, a prominent cryptocurrency. Our implementations of Graphene, IBLTs, and our IBLT optimization algorithm are all open-source code.
Bitcoin and Ethereum, whose miners arguably collectively comprise the most powerful computational resource in the history of mankind, offer no more power for processing and verifying transactions than a typical smart phone. The system described herein bypasses this bottleneck and brings scalable computation to Ethereum. Our new system consists of a financial incentive layer atop a dispute resolution layer where the latter takes form of a versatile "verification game." In addition to secure outsourced computation, immediate applications include decentralized mining pools whose operator is an Ethereum smart contract, a cryptocurrency with scalable transaction throughput, and a trustless means for transferring currency between disjoint cryptocurrency systems.
Blockchain is the core technology of many cryptocurrencies. Blockchain as a distributed ledger technology has received extensive research attention. In addition to cryptography and P2P (peer-to-peer) technology, consensus protocols are also a fundamental part of the blockchain technology. A good consensus protocol can guarantee the fault tolerance and security of the blockchain systems. The consensus protocols currently used in most blockchain systems can be broadly divided into two categories: the probabilistic-finality consensus protocols and the absolute-finality consensus protocols. This paper introduces some of the main consensus protocols of these two categories, and analyzes their strengths and weaknesses as well as the applicable blockchain types.
Recent advances in the cryptographic field of "Zero-Knowledge Proofs" have sparked a new wave of research, giving birth to many exciting theoretical approaches in the last few years. Such research has often overlapped with the need for private and scalable solutions of Blockchain-based communities, resulting in the first practical implementations of such systems. Many of these innovative constructions have developed in parallel, using different terminologies and evolving into a fragmented ecosystem, calling for their consolidation into the more stable domain of "Verifiable Computation". In this master thesis I propose a unifying Verifiable Computation model for the simplification and efficient comparison of all cryptographic proof systems. I take advantage of this model to analyse innovative technologies (Homomorphic Authenticators, Verifiable Delay Functions) which developed into their own specialised domains, and I attempt to make them more accessible for newcomers to the field. Furthermore, I expand on the future of Verifiable Computation, Universal proof compilers and "Proofs of All", by approaching the state-of-the-art zk-STARK construction from a more accessible and informal design perspective.
Blockchain (BC), the backbone technology of cryptocurrency systems and smart contracts, is considered to be an alluring concept in recent years due to its ability to ensure enhanced security and privacy for multifarious applications in many domains. The blockchain is exclusively used for facilitating secure online transactions by maintaining a distributed and decentralized ledger of records across multiple computers. In this paper, we have analyzed and modified the PBFT (Practical Byzantine Fault Tolerant) consensus-based Tendermint blockchain algorithm. The major contributions of this paper are as follows; first we have analyzed and enhanced the correctness of Tendermint blockchain algorithm by proposing a lock free algorithm, employing wait-freedom property by using a timeout on the voting phase. Our second contribution relates to the fairness of the Tendermint algorithm. We have considered the block sensitivity and node's trustworthiness for determining the size of voter's (validator's) subset and employed the random walk algorithm for the fair selection of sub set of the voter nodes. Our third contribution is to investigate the reason for having voting conflicts and the weakness of consensuses as a correctness property. Finally, we have shown how to detect byzantine and failure nodes in the blockchain.
Vojislav B. Mišić, Jelena Mišić, Xiaolin Chang
Healthcare information systems are the next big application area for Blockchain technology. However, straightforward extensions of existing digital cryptocurrency systems such as Bitcoin and Ethereum results in systems that are unsuitable for the challenges posed by healthcare systems. In this paper, we propose an architecture for a blockchain-based healthcare information system in which block validation is performed through collective signatures initiated by a designated leader and executed by a pool of witnesses. Furthermore, we describe a smart-contract based approach that allows data owners to explicitly grant or revoke authorizations for other actors to access healthcare data. All accesses, successful or not, are recorded on the blockchain as separate transactions, thus ensuring transparency and privacy protection.
Distributed ledgers are among the most replicated data repositories in the world. They offer data consistency, immutability, and auditability, based on the assumption that each participating node locally verifies their entire content. Although their content, currently extending up to a few hundred gigabytes, can be accommodated by dedicated commodity hard disks, downloading it, processing it, and storing it in general-purpose desktop and laptop computers can prove largely impractical. Even worse, this becomes a prohibitive restriction for smartphones, mobile devices, and resource-constrained IoT devices. In this demo, we present an implementation of Dietcoin, a Bitcoin protocol extension that allows nodes to perform secure local verification of Bitcoin transactions with small bandwidth and storage requirements. This demo presents and benchmarks the main features of Dietcoin that are important for today's cryptocurrencies and smart contract systems, but are missing in the current state-of-the-art: (i) allowing resource-constrained devices to verify the correctness of selected blocks locally without having to download the complete ledger; (ii) enabling devices to join a blockchain quickly yet securely, dropping bootstrap time from days down to a matter of seconds; (iii) providing a generic solution that can be applied to other distributed ledgers secured with Proof-of-Work.
Abstract In the blockchain system, the consensus mechanism not only helps the nodes maintain data consistency, but also has certain functions for token issuance and attack prevention. Aiming at the problems of low enthusiasm and weak centralization in Delegated Proof of Stake (DPoS), this paper proposes a weak centralization consensus mechanism with more incentive effect. We replace the voting link with opportunity verification mechanism, and make the voting link that affects the enthusiasm of nodes become the embodiment of their own rights and interests, so as to strive for the maximization of their own interests. And we also introduce the method of random guess to make the selection of representative nodes more random, so as to achieve the situation of weaker center. At last, combined with the existing problems, the paper analyses the feasible solution with this mechanism.
Ghareeb Falazi, Vikas Khinchi, Uwe Breitenbücher, Frank Leymann
Traditional distributed transaction processing (TP) systems, such as replicated databases, faced difficulties in getting wide adoption for scenarios of enterprise integration due to the level of mutual trust required. Ironically, public blockchains, which promised to solve the problem of mutual trust in collaborative processes, suffer from issues like scalability, probabilistic transaction finality, and lack of data confidentiality. To tackle these issues, permissioned blockchains were introduced as an alternative approach combining the positives of the two worlds and avoiding their drawbacks. However, no sufficient analysis has been done to emphasize their actual capabilities regarding TP. In this paper, we identify a suitable collection of TP criteria to analyze permissioned blockchains and apply them to a prominent set of these systems. Finally, we compare the derived properties and provide general conclusions.
Abhinav Aggarwal, Mahnush Movahedi, Jared Saia, Mahdi Zamani
We propose a protocol that allows the participants of a permissionless decentralized system to agree on a set of identities in the presence of a computationally-bounded Byzantine adversary. Our protocol guarantees that the fraction of identities belonging to the adversary in the set of identities is at most equal to the total computational hash power of the adversary.
Ruffin White, Gianluca Caiazza, Agostino Cortesi, Young Im Cho · 5 authors
Event data recording is crucial in robotics research, providing prolonged insights into a robot's situational understanding, progression of behavioral state, and resulting outcomes. Such recordings are invaluable when debugging complex robotic applications or profiling experiments ex post facto. As robotic developments mature into production, both the roles and requirements of event logging will broaden, to include serving as evidence for auditors and regulators investigating accidents or fraud. Given the growing number of high profile public incidents involving self-driving automotives resulting in fatality and regulatory policy making, it is paramount that the integrity, authenticity and non-repudiation of such event logs are maintained to ensure accountability. Being mobile cyber-physical systems, robots present new threats, and vulnerabilities beyond traditional IT: unsupervised physical system access or postmortem collusion between robot and OEM could result in the truncation or alteration of prior records. In this letter, we address immutablization of log records via integrity proofs and distributed ledgers with special considerations for mobile and public service robot deployments.
Musab A. Alturki, Jing Chen, Victor Luchangco, Brandon Moore · 7 authors
The Algorand blockchain is a secure and decentralized public ledger based on pure proof of stake rather than proof of work. At its core it is a novel consensus protocol with exactly one block certified in each round: that is, the protocol guarantees that the blockchain does not fork. In this paper, we report on our effort to model and formally verify the Algorand consensus protocol in the Coq proof assistant. Similar to previous consensus protocol verification efforts, we model the protocol as a state transition system and reason over reachable global states. However, in contrast to previous work, our model explicitly incorporates timing issues (e.g., timeouts and network delays) and adversarial actions, reflecting a more realistic environment faced by a public blockchain. Thus far, we have proved asynchronous safety of the protocol: two different blocks cannot be certified in the same round, even when the adversary has complete control of message delivery in the network. We believe that our model is sufficiently general and other relevant properties of the protocol such as liveness can be proved for the same model.
Bitcoin is a peer-to-peer payment system proposed by Nakamoto in 2008. Properties of the bitcoin backbone protocol have been investigated in some depth: the blockchain growth property quantifies the number of blocks added to the blockchain during any time intervals; the blockchain quality property ensures the honest miners always contribute at least a certain fraction of the blockchain; the common prefix property ensures if a block is deep enough, it will eventually be adopted by all honest miners with high probability. Following the spirit of decoupling various functionalities of the blockchain, the Prism protocol is proposed to dramatically improve the throughput while maintaining the same level of security. Prior analyses of the bitcoin and Prism backbone protocols assume the lifespan of blockchain is finite. This paper presents a streamlined and strengthened analysis without the finite horizon assumption. Specifically, the results include a blockchain growth property, a blockchain quality property, and a common prefix property of the bitcoin backbone protocol, as well as the liveness and persistence of the Prism backbone protocol regardless of whether the blockchains have a infinite lifespan. We also express the properties of bitcoin and Prism backbone protocols in explicit expressions rather than order optimal results, which lead to tighter bounds and practical references for public transaction ledger protocol design.
Antoine Durand, Emmanuelle Anceaume, Romaric Ludinard
Our work focuses on the design of a scalable permissionless blockchain in the\nproof-of-stake setting. In particular, we use a distributed hash table as a\nbuilding block to set up randomized shards, and then leverage the sharded\narchitecture to validate blocks in an efficient manner. We combine verifiable\nByzantine agreements run by shards of stakeholders and a block validation\nprotocol to guarantee that forks occur with negligible probability. We impose\ninduced churn to make shards robust to eclipse attacks, and we rely on the UTXO\ncoin model to guarantee that any stakeholder action is securely verifiable by\nanyone. Our protocol works against adaptive adversary, and makes no synchrony\nassumption beyond what is required for the byzantine agreement.\n
The Byzantine general problem is the core problem that consensus algorithms are trying to solve, which is at the heart of the design of blockchains. As a result, we have seen numerous proposals of consensus algorithms in recent years, trying to improve the level of decentralization, performance, and security of blockchains. In our opinion, there are two most challenging issues when we consider the design of such algorithms in the context of powering blockchains in practice. First, the outcome of a consensus algorithm usually depends on the underlying incentive model, so each participant should have an equal probability of receiving rewards for its work. Secondly, the protocol should be able to resist network failures, such as cloud services shutdown, while maintaining high performance otherwise. We address these two critical issues in this paper. First, we propose a new metric, called fair validity, for measuring the performance of Byzantine agreements. Intuitively, fair validity provides a lower bound for the probability of acceptances of honest nodes' proposals. This is a strong notion of fairness, and we argue that it is crucial for the success of a blockchain in practice. We then show that any Byzantine agreement could not achieve fair validity in an asynchronous network, so we will focus on synchronous protocols. This leads to our second contribution: we propose a fair, responsive, and partition-resilient Byzantine agreement protocol able to tolerate up to 1/3 corruptions. As we will show in the paper, our protocol achieves fair validity and is responsive in the sense that the termination time only depends on actual network delay, as opposed to arbitrary, pre-determined time-bound. Furthermore, our proposal is partition-resilient. Last but not least, experimental results show that our Byzantine agreement protocol outperforms a wide variety of state-of-art synchronous protocols, combining the best from both theoretic and practical worlds.