Blockchain Papers List, Updated Monthly.
1. [Byzantine] The byzantine generals problem. Lamport L, Shostak R, Pease M. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 382-401.
Abstract: Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.
2. [FLP] Impossibility of Distributed Consensus with One Faulty Process Fischer M J, Lynch N A, Paterson M S. Journal of the ACM, 1985, 32(2): 374:382
Abstract: The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the Byzantine Generals problem.
3. [VR] Viewstamped replication: a new primary copy method to support highly-available distributed systems Oki B M, Liskov B H. In: Proceedings ofProceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing.Toronto, Ontario, Canada: ACM, 1988. 8:17
Abstract: One of the potential benefits of distributed systems is their use in providing highly-available services that are likely to be usable when needed. Availabilay is achieved through replication. By having inore than one copy of information, a service continues to be usable even when some copies are inaccessible, for example, because of a crash of the computer where a copy was stored. This paper presents a new replication algorithm that has desirable performance properties. Our approach is based on the primary copy technique. Computations run at a primary. which notifies its backups of what it has done. If the primary crashes, the backups are reorganized, and one of the backups becomes the new primary. Our method works in a general network with both node crashes and partitions. Replication causes little delay in user computations and little information is lost in a reorganization; we use a special kind of timestamp called a viewstamp to detect lost information.
4. [Paxos] The part-time parliament. Lamport L. ACM Transactions on Computer Systems, 1998, 16(2): 133:169.
Abstract: Recent archaeological discoveries on the island of Paxos reveal that the parliament functioned despite the peripatetic propensity of its part-time legislators. The legislators maintained consistent copies of the parliamentary record, despite their frequent forays from the chamber and the forgetfulness of their messengers. The Paxon parliament's protocol provides a new way of implementing the state-machine approach to the design of distributed systems--an approach that has received limited attention because it leads to designs of insufflicient complexity.
5. [PBFT] Practical Byzantine fault tolerance. Castro, Miguel, and Barbara Liskov.1999.
Abstract: This paper describes a new replication algorithm that is able to tolerate Byzantine faults. We believe that Byzantine-fault-tolerant algorithms will be increasingly important in the future because malicious attacks and software errors are increasingly common and can cause faulty nodes to exhibit arbitrary behavior. Whereas previous algorithms assumed a synchronous system or were too slow to be used in practice, the algorithm described in this paper is practical: it works in asynchronous environments like the Internet and incorporates several important optimizations that improve the response time of previous algorithms by more than an order of magnitude. We implemented a Byzantine-fault-tolerant NFS service using our algorithm and measured its performance. The results show that our service is only 3% slower than a standard unreplicated NFS.
6. [CAP] Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. Gilbert S, Lynch N. Acm Sigact News, 2002, 33(2): 51:59.
Abstract: When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, we prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.
7. [BASE] BASE: An Acid Alternative. Dan Pritchett.EBay.2008.
Abstract: In partitioned databases, trading some consistency for availability can lead to dramatic improvements in scalability.
8. [PoW] Bitcoin: A peer-to-peer electronic cash system. Nakamoto, Satoshi.2008.
Abstract: A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. 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 a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hashbased proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. 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 broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proofof-work chain as proof of what happened while they were gone.
9. [PoS] Proof of Stake. QuantumMechanic.2011.
Abstract: Proof of Stake is a proposed alternative to Proof of Work. Like proof of work, proof of stake attempts to provide consensus and doublespend prevention (see "main" bitcointalk thread, and a Bounty Thread). Because creating forks is costless when you aren't burning an external resource Proof of Stake alone is considered to an unworkable consensus mechanism.
10. [Ripple] The Ripple Protocol Consensus Algorithm
Abstract: While several consensus algorithms exist for the Byzantine Generals Problem, specifically as it pertains to distributed payment systems, many suffer from high latency induced by the requirement that all nodes within the network communicate synchronously. In this work, we present a novel consensus algorithm that circumvents this requirement by utilizing collectively-trusted subnetworks within the larger network. We show that the “trust” required of these subnetworks is in fact minimal and can be further reduced with principled choice of the member nodes. In addition, we show that minimal connectivity is required to maintain agreement throughout the whole network. The result is a low-latency consensus algorithm which still maintains robustness in the face of Byzantine failures. We present this algorithm in its embodiment in the Ripple Protocol.
11. [DPoS] Delegated Proof of Stake.Larimer, Daniel. 2014.
12. [Raft] In search of an understandable consensus algorithm. Diego Ongaro and John Ousterhout,2014.
Abstract: Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems. In order to enhance understandability, Raft separates the key elements of consensus, such as leader election, log replication, and safety, and it enforces a stronger degree of coherency to reduce the number of states that must be considered. Results from a user study demonstrate that Raft is easier for students to learn than Paxos. Raft also includes a new mechanism for changing the cluster membership, which uses overlapping majorities to guarantee safety.
13. [PoSV] Proof of stake velocity. Ren L.April 10, 2018.
Abstract: Proof of Stake Velocity (PoSV) is proposed as an alternative to Proof of Work (PoW) and Proof of Stake (PoS) to secure the peer-to-peer network and confirm transactions of Reddcoin, a cryptocurrency created specifically to facilitate social interactions in the digital age. PoSV is designed to encourage both ownership (Stake) and activity (Velocity) which directly correspond to the two main functions of Reddcoin as a real currency: store of value and medium of exchange. Reddcoin can also function as the unit of account in heterogeneous social context. The technological aspects of PoSV are presented after a detailed review of existing designs. The economic aspects of Reddcoin are then analysed. Finally the unique position of Reddcoin as a digital social currency in the competitive landscape of cryptocurrencies is discussed.
14. [Tendermint] The latest gossip on BFT consensus
Abstract: The paper presents Tendermint, a new protocol for ordering events in a distributed network under adversarial conditions. More commonly known as Byzantine Fault Tolerant (BFT) consensus or atomic broadcast, the problem has attracted significant attention in recent years due to the widespread success of blockchain-based digital currencies, such as Bitcoin and Ethereum, which successfully solved the problem in a public setting without a central authority. Tendermint modernizes classic academic work on the subject and simplifies the design of the BFT algorithm by relying on a peer-to-peer gossip protocol among nodes.
15. [Ouroboros] Ouroboros: A provably secure proof-of-stake blockchain protocol. Kiayias, Aggelos. Springer, Cham, 2017.
Abstract:We present “Ouroboros”, the first blockchain protocol based on proof of stake with rigorous security guarantees. We establish security properties for the protocol comparable to those achieved by the bitcoin blockchain protocol. As the protocol provides a “proof of stake” blockchain discipline, it offers qualitative efficiency advantages over blockchains based on proof of physical resources (e.g., proof of work). We also present a novel reward mechanism for incentivizing Proof of Stake protocols and we prove that, given this mechanism, honest behavior is an approximate Nash equilibrium, thus neutralizing attacks such as selfish mining.
16. [HoneyBadgerBFT] The Honey Badger of BFT Protocols.Miller A, Xia Y, Croman K, Shi E,Song D. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. Xi’an, China: ACM, 2016.
Abstract: The surprising success of cryptocurrencies has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) protocols for mission-critical applications, such as financial transactions. Although the conventional wisdom is to build atop a (weakly) synchronous protocol such as PBFT (or a variation thereof), such protocols rely critically on network timing assumptions, and only guarantee liveness when the network behaves as expected. We argue these protocols are ill-suited for this deployment scenario. We present an alternative, HoneyBadgerBFT, the first practical asynchronous BFT protocol, which guarantees liveness without making any timing assumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and experimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experiments over Tor, without needing to tune any parameters. Unlike the alternatives, HoneyBadgerBFT simply does not care about the underlying network.
17. [Bitcoin-NG] Bitcoin-NG: A Scalable Blockchain Protocol. Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert van Renesse, Cornell University. 2016.
Abstract: Cryptocurrencies, based on and led by Bitcoin, have shown promise as infrastructure for pseudonymous online payments, cheap remittance, trustless digital asset exchange, and smart contracts. However, Bitcoin-derived blockchain protocols have inherent scalability limits that trade off between throughput and latency, which withhold the realization of this potential. This paper presents Bitcoin-NG (Next Generation), a new blockchain protocol designed to scale. Bitcoin-NG is a Byzantine fault tolerant blockchain protocol that is robust to extreme churn and shares the same trust model as Bitcoin. In addition to Bitcoin-NG, we introduce several novel metrics of interest in quantifying the security and efficiency of Bitcoin-like blockchain protocols. We implement Bitcoin-NG and perform large-scale experiments at 15% the size of the operational Bitcoin system, using unchanged clients of both protocols. These experiments demonstrate that Bitcoin-NG scales optimally, with bandwidth limited only by the capacity of the individual nodes and latency limited only by the propagation time of the network.
18. [Tangaroa] Tangaroa: a byzantine fault tolerant raft. Christopher Copeland and Hongxia Zhong.2016.
Abstract: We propose a Byzantine Fault Tolerant variant of the Raft consensus algorithm, BFTRaft, inspired by the original Raft[1] algorithm and the Practical Byzantine Fault Tolerance algorithm[2]. BFT Raft maintains the safety, fault tolerance, and liveness properties of Raft in the presence of Byzantine faults, while also aiming towards to Raft’s goal of simplicity and understandability. We have implemented a proof-of-concept of this algorithm in the Haskell programming language.
19. [Kadena] Kadena: The flrst scalable, high performance private blockchain. Martino W. Kadena.April 10, 2018.
Abstract: This paper introduces Kadena, the first private/permissioned blockchain technology to achieve high performance at scale. Kadena is an implementation of the novel ScalableBFT consensus protocol, which draws inspiration from the Tangaroa protocol as well as practical engineering realities. Until now, private blockchain technologies have been able to provide either high performance or scalability but not both. Rarely deployed into production, BFT-Consensus algorithms achieve high performance initially, but exhibit drastic performance degradation as cluster size increases. Mining (or “proof of work”) is the only workable alternative: it has practically no scaling limit. However, being a probabilistic mechanism, mining is necessarily slow and thus unable to attain the performance demanded by enterprise use-cases. The ability to perform at scale, without sacrificing the guarantees that blockchains provide, has been a major unresolved problem in the implementation of private blockchains. Scaling is critical for industrial adoption. Blockchain applications must be able to maintain acceptable performance for a successful deployment to sustain wide and growing participation.
Abstract: This paper introduces a new model for consensus called federated Byzantine agreement (FBA). FBA achieves robustness through quorum slices—individual trust decisions made by each node that together determine system-level quorums. Slices bind the system together much the way individual networks’ peering and transit decisions now unify the Internet. We also present the Stellar Consensus Protocol (SCP), a construction for FBA. Like all Byzantine agreement protocols, SCP makes no assumptions about the rational behavior of attackers. Unlike prior Byzantine agreement models, which presuppose a unanimously accepted membership list, SCP enjoys open membership that promotes organic network growth. Compared to decentralized proof of-work and proof-of-stake schemes, SCP has modest computing and financial requirements, lowering the barrier to entry and potentially opening up financial systems to new participants.
21. [Algorand] Algorand: Scaling Byzantine Agreements for Cryptocurrencies. Gilad Y, Hemo R, Micali S, Vlachos G, Zeldovich N.2018.
Abstract: Algorand is a new cryptocurrency system that can confirm transactions with latency on the order of a minute while scaling to many users. Algorand ensures that users never have divergent views of confirmed transactions, even if some of the users are malicious and the network is partitioned. In contrast, existing cryptocurrencies allow for temporary forks and therefore require a long time, on the order of an hour, to confirm transactions with high confidence. Algorand uses a new Byzantine Agreement (BA) protocol to reach consensus among users on the next set of transactions. To scale the consensus to many users, Algorand uses a novel mechanism based on Verifiable Random Functions that allows users to privately check whether they are selected to participate in the BA to agree on the next set of transactions, and to include a proof of their selection in their network messages. In Algorand's BA protocol, users do not keep any private state except for their private keys, which allows Algorand to replace participants immediately after they send a message. This mitigates targeted attacks on chosen participants after their identity is revealed. We implement Algorand and evaluate its performance on 1,000 EC2 virtual machines, simulating up to 500,000 users. Experimental results show that Algorand confirms transactions in under a minute, achieves 30× Bitcoin's throughput, and incurs almost no penalty for scaling to more users.
22. [SleepyModel] The Sleepy Model of Consensus. Rafael Pass,Elaine Shi.2017
Abstract: The literature on distributed computing (as well as the cryptography literature) typically considers two types of players—honest players and corrupted players. Resilience properties are then analyzed assuming a lower bound on the fraction of honest players. Honest players, however, are not only assumed to follow the prescribed the protocol, but also assumed to be online throughout the whole execution of the protocol. The advent of “large-scale” consensus protocols (e.g., the blockchain protocol) where we may have millions of players, makes this assumption unrealistic. In this work, we initiate a study of distributed protocols in a “sleepy” model of computation where players can be either online (awake) or offline (asleep), and their online status may change at any point during the protocol. The main question we address is: Can we design consensus protocols that remain resilient under “sporadic participation”, where at any given point, only a subset of the players are actually online? As far as we know, all standard consensus protocols break down under such sporadic participation, even if we assume that 99% of the online players are honest. Our main result answers the above question in the affirmative. We present a construction of a consensus protocol in the sleepy model, which is resilient assuming only that a majority of the online players are honest. Our protocol relies on a Public-Key Infrastructure (PKI), a Common Random String (CRS) and is proven secure in the timing model of Dwork-Naor-Sahai (STOC’98) where all players are assumed to have weakly-synchronized clocks (all clocks are within Δ of the “real time”) and all messages sent on the network are delivered within Δ time, and assuming the existence of sub-exponentially secure collision-resistant hash functions and enhanced trapdoor permutations. Perhaps surprisingly, our protocol significantly departs from the standard approaches to distributed consensus, and we instead rely on key ideas behind Nakamoto’s blockchain protocol (while dispensing the need for “proofs-of-work”). We finally observe that sleepy consensus is impossible in the presence of a dishonest majority of online players.
23. [SAREK] SAREK: Optimistic Parallel Ordering in Byzantine Fault Tolerance. Bijun Li ; Wenbo Xu ; Muhammad Zeeshan Abid ; Tobias Distler ; Rüdiger Kapitza.2016.
Abstract: Recently proposed Byzantine fault-tolerant (BFT) systems achieve high throughput by processing requests in parallel. However, as their agreement protocols rely on a single leader and make big efforts to establish a global total order on all requests before execution, the performance and scalability of such approaches is limited. To address this problem we present SAREK, a parallel ordering framework that partitions the service state to exploit parallelism during both agreement as well as execution. SAREK utilizes request dependency which is abstracted from application-specific knowledge for the service state partitioning. Instead of having one leader at a time for the entire system, it uses one leader per partition and only establishes an order on requests accessing the same partition. SAREK supports operations that span multiple partitions and provides a deterministic mechanism to atomically process them. To address use cases in which there is not enough application-specific knowledge to always determine a priori which partition(s) a request will operate on, SAREK provides mechanisms to even handle mis-predictions without requiring rollbacks. Our evaluation of a key-value store shows an increase in throughput performance by a factor of 2 at half the latency compared to a single-leader implementation.
24. [2-hop] 2-hop Blockchain:Combining Proof-of-Work and Proof-of-Stake Securely. Tuyet Duong,Lei Fan,Hong-Sheng Zhou.2017.
Abstract: Cryptocurrencies like Bitcoin have proven to be a phenomenal success. Bitcoin-like systems use proof-of-work mechanism, and their security holds if the majority of the computing power is under the control of honest players. However, this assumption has been seriously challenged recently and Bitcoinlike systems will fail when this assumption is broken. We propose the first provably secure 2-hop blockchain by combining proof-of-work and proof-ofstake mechanisms. On top of Bitcoin’s brilliant ideas of utilizing the power of the honest miners, via their computing resources, to secure the blockchain, we further leverage the power of the honest users/stakeholders, via their coins/stake, to achieve this goal. The security of our blockchain holds if the honest players control majority of the collective resources (which consists of both computing power and stake). That said, even if the adversary controls more than 50% computing power, the honest players still have the chance to defend the blockchain via honest stake.
25. [RBFT] RBFT: Redundant Byzantine Fault Tolerance. Pierre-Louis Aublin ; Sonia Ben Mokhtar ; Vivien Quéma. 2013.
Abstract: Byzantine Fault Tolerant state machine replication (BFT) protocols are replication protocols that tolerate arbitrary faults of a fraction of the replicas. Although significant efforts have been recently made, existing BFT protocols do not provide acceptable performance when faults occur. As we show in this paper, this comes from the fact that all existing BFT protocols targeting high throughput use a special replica, called the primary, which indicates to other replicas the order in which requests should be processed. This primary can be smartly malicious and degrade the performance of the system without being detected by correct replicas. In this paper, we propose a new approach, called RBFT for Redundant-BFT: we execute multiple instances of the same BFT protocol, each with a primary replica executing on a different machine. All the instances order the requests, but only the requests ordered by one of the instances, called the master instance, are actually executed. The performance of the different instances is closely monitored, in order to check that the master instance provides adequate performance. If that is not the case, the primary replica of the master instance is considered malicious and replaced. We implemented RBFT and compared its performance to that of other existing robust protocols. Our evaluation shows that RBFT achieves similar performance as the most robust protocols when there is no failure and that, under faults, its maximum performance degradation is about 3%, whereas it is at least equal to 78% for existing protocols.
26. [Zyzzyva] Zyzzyva: Speculative Byzantine fault tolerance. Ramakrishna Kotla. 2009.
Abstract: A longstanding vision in distributed systems is to build reliable systems from unreliable components. An enticing formulation of this vision is Byzantine Fault-Tolerant (BFT) state machine replication, in which a group of servers collectively act as a correct server even if some of the servers misbehave or malfunction in arbitrary (“Byzantine”) ways. Despite this promise, practitioners hesitate to deploy BFT systems, at least partly because of the perception that BFT must impose high overheads. In this article, we present Zyzzyva, a protocol that uses speculation to reduce the cost of BFT replication. In Zyzzyva, replicas reply to a client's request without first running an expensive three-phase commit protocol to agree on the order to process requests. Instead, they optimistically adopt the order proposed by a primary server, process the request, and reply immediately to the client. If the primary is faulty, replicas can become temporarily inconsistent with one another, but clients detect inconsistencies, help correct replicas converge on a single total ordering of requests, and only rely on responses that are consistent with this total order. This approach allows Zyzzyva to reduce replication overheads to near their theoretical minima and to achieve throughputs of tens of thousands of requests per second, making BFT replication practical for a broad range of demanding services.
27. [SBFT] SBFT: a Scalable and Decentralized Trust Infrastructure. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu.2019.
Abstract: SBFT is a state of the art Byzantine fault tolerant permissioned blockchain system that addresses the challenges of scalability, decentralization and world-scale geo-replication. SBFTis optimized for decentralization and can easily handle more than 200 active replicas in a real world-scale deployment. We evaluate sysname in a world-scale geo-replicated deployment with 209 replicas withstanding f=64 Byzantine failures. We provide experiments that show how the different algorithmic ingredients of sysname increase its performance and scalability. The results show that SBFT simultaneously provides almost 2x better throughput and about 1.5x better latency relative to a highly optimized system that implements the PBFT protocol. To achieve this performance improvement, SBFT uses a combination of four ingredients: using collectors and threshold signatures to reduce communication to linear, using an optimistic fast path, reducing client communication and utilizing redundant servers for the fast path.
28. [PoT] A Proof-of-Trust Consensus Protocol for Enhancing Accountability in Crowdsourcing Services. Jun Zou,Bin Ye,Lie Qu,Yan Wang,Mehmet A Orgun, Lei Li. IEEE Transactions on Services Computing.2018.
Abstract: Incorporating accountability mechanisms in online services requires effective trust management and immutable, traceable source of truth for transaction evidence. The emergence of the blockchain technology brings in high hopes for fulfilling most of those requirements. However, a major challenge is to find a proper consensus protocol that is applicable to the crowdsourcing services in particular and online services in general. Building upon the idea of using blockchain as the underlying technology to enable tracing transactions for service contracts and dispute arbitration, this paper proposes a novel consensus protocol that is suitable for the crowdsourcing as well as the general online service industry. The new consensus protocol is called “Proof-of-Trust” (PoT) consensus; it selects transaction validators based on the service participants' trust values while leveraging RAFT leader election and Shamir's secret sharing algorithms. The PoT protocol avoids the low throughput and resource intensive pitfalls associated with Bitcoin's “Proof-of-Work” (PoW) mining, while addressing the scalability issue associated with the traditional Paxos-based and Byzantine Fault Tolerance (BFT)-based algorithms. In addition, it addresses the unfaithful behaviors that cannot be dealt with in the traditional BFT algorithms. The paper demonstrates that our approach can provide a viable accountability solution for the online service industry.
29. [Conflux] Scaling Nakamoto Consensus to Thousands of Transactions per Second. Chenxing Li, Peilun Li, Dong Zhou, Wei Xu, Fan Long, Andrew Yao.2018.
Abstract: This paper presents Conflux, a fast, scalable and decentralized blockchain system that optimistically process concurrent blocks without discarding any as forks. The Conflux consensus protocol represents relationships between blocks as a direct acyclic graph and achieves consensus on a total order of the blocks. Conflux then, from the block order, deterministically derives a transaction total order as the blockchain ledger. We evaluated Conflux on Amazon EC2 clusters with up to 20k full nodes. Conflux achieves a transaction throughput of 5.76GB/h while confirming transactions in 4.5-7.4 minutes. The throughput is equivalent to 6400 transactions per second for typical Bitcoin transactions. Our results also indicate that when running Conflux, the consensus protocol is no longer the throughput bottleneck. The bottleneck is instead at the processing capability of individual nodes.
30. [Gosig] Gosig: Scalable Byzantine Consensus on Adversarial Wide Area Network for Blockchains. Peilun Li, Guosai Wang, Xiaoqi Chen, Wei Xu. 2018.
Abstract: Existing Byzantine fault tolerance (BFT) protocols face significant challenges in the consortium blockchain scenario. On the one hand, we can make little assumptions about the reliability and security of the underlying Internet. On the other hand, the applications on consortium blockchains demand a system as scalable as the Bit-coin but providing much higher performance, as well as provable safety. We present a new BFT protocol, Gosig, that combines crypto-based secret leader selection and multi-round voting in the protocol layer with implementation layer optimizations such as gossip-based message propagation. In particular, Gosig guarantees safety even in a network fully controlled by adversaries, while providing provable liveness with easy-to-achieve network connectivity assumption. On a wide area testbed consisting of 140 Amazon EC2 servers spanning 14 cities on five continents, we show that Gosig can achieve over 4,000 transactions per second with less than 1 minute transaction confirmation time.
31. [Velisarios] Velisarios: Byzantine Fault-Tolerant Protocols Powered by Coq. Vincent Rahli,Ivana Vukotic,Marcus Völp,Paulo Esteves-Verissimo.2018
Abstract: Our increasing dependence on complex and critical information infrastructures and the emerging threat of sophisticated attacks, ask for extended efforts to ensure the correctness and security of these systems. Byzantine fault-tolerant state-machine replication (BFT-SMR) provides a way to harden such systems. It ensures that they maintain correctness and availability in an application-agnostic way, provided that the replication protocol is correct and at least n−f out of n replicas survive arbitrary faults. This paper presents Velisarios, a logic-of-events based framework implemented in Coq, which we developed to implement and reason about BFT-SMR protocols. As a case study, we present the first machine-checked proof of a crucial safety property of an implementation of the area’s reference protocol: PBFT.
32. Efficient Synchronous Byzantine Consensus. Ittai Abraham,Srinivas Devadas,Danny Dolev,Kartik Nayak,Ling Ren.2017
Abstract: We present new protocols for Byzantine state machine replication and Byzantine agreement in the synchronous and authenticated setting. The celebrated PBFT state machine replication protocol tolerates f Byzantine faults in an asynchronous setting using 3f + 1 replicas, and has since been studied or deployed by numerous works. In this work, we improve the Byzantine fault tolerance threshold to n = 2f + 1 by utilizing a relaxed synchrony assumption. We present a synchronous state machine replication protocol that commits a decision every 3 rounds in the common case. The key challenge is to ensure quorum intersection at one honest replica. Our solution is to rely on the synchrony assumption to form a post-commit quorum of size 2f + 1, which intersects at f + 1 replicas with any pre-commit quorums of size f + 1. Our protocol also solves synchronous authenticated Byzantine agreement in expected 8 rounds. The best previous solution (Katz and Koo, 2006) requires expected 24 rounds. Our protocols may be applied to build Byzantine fault tolerant systems or improve cryptographic protocols such as cryptocurrencies when synchrony can be assumed.
33. Solida Solida: A Blockchain Protocol Based on Reconfigurable Byzantine Consensus.Ittai Abraham,Dahlia Malkhi,Kartik Nayak, Ling Ren, and Alexander Spiegelman.2016.
Abstract: The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin in confirmation time, and provides safety and liveness assuming the adversary control less than (roughly) one-third of the total mining power.
34. Proof of Space From Stacked Expanders.Ling Ren,Srinivas Devadas.2016.
Abstract: Recently, proof of space (PoS) has been suggested as a more egalitarian alternative to the traditional hash-based proof of work. In PoS, a prover proves to a verifier that it has dedicated some specified amount of space. A closely related notion is memory-hard functions (MHF), functions that require a lot of memory/space to compute. While making promising progress, existing PoS and MHF have several problems. First, there are large gaps between the desired space-hardness and what can be proven. Second, it has been pointed out that PoS and MHF should require a lot of space not just at some point, but throughout the entire computation/protocol; few proposals considered this issue. Third, the two existing PoS constructions are both based on a class of graphs called superconcentrators, which are either hard to construct or add a logarithmic factor overhead to efficiency. In this paper, we construct PoS from stacked expander graphs. Our constructions are simpler, more efficient and have tighter provable space-hardness than prior works. Our results also apply to a recent MHF called Balloon hash. We show Balloon hash has tighter space-hardness than previously believed and consistent space-hardness throughout its computation.
35. Bandwidth Hard Functions for ASIC Resistance.Ling Ren,Srinivas Devadas.2017.
Abstract: Cryptographic hash functions have wide applications including password hashing, pricing functions for spam and denial-of-service countermeasures and proof of work in cryptocurrencies. Recent progress on ASIC (Application Specific Integrated Circuit) hash engines raise concerns about the security of the above applications. This leads to a growing interest in ASIC resistant hash function and ASIC resistant proof of work schemes, i.e., those that do not give ASICs a huge advantage. The standard approach towards ASIC resistance today is through memory hard functions or memory hard proof of work schemes. However, we observe that the memory hardness approach is an incomplete solution. It only attempts to provide resistance to an ASIC’s area advantage but overlooks the more important energy advantage. In this paper, we propose the notion of bandwidth hard functions to reduce an ASIC’s energy advantage. CPUs cannot compete with ASICs for energy efficiency in computation, but we can rely on memory accesses to reduce an ASIC’s energy advantage because energy costs of memory accesses are comparable for ASICs and CPUs. We propose a model for hardware energy cost that has sound foundations in practice. We then analyze the bandwidth hardness property of ASIC resistant candidates. We find scrypt, Catena-BRG and Balloon are bandwidth hard with suitable parameters. Lastly, we observe that a capacity hard function is not necessarily bandwidth hard, with a stacked double butterfly graph being a counterexample.
36. Monoxide Monoxide: Scale out Blockchains with Asynchronous Consensus Zones.Jiaping Wang, ICT/CAS, Sinovation Ventures; Hao Wang, Ohio State University.
Abstract: Cryptocurrencies have provided a promising infrastructure for pseudonymous online payments. However, low throughput has significantly hindered the scalability and usability of cryptocurrency systems for increasing numbers of users and transactions. Another obstacle to achieving scalability is that every node is required to duplicate the communication, storage, and state representation of the entire network.
In this paper, we introduce the Asynchronous Consensus Zones, which scales blockchain system linearly without compromising decentralization or security. We achieve this by running multiple independent and parallel instances of single-chain consensus (zones). The consensus happens independently within each zone with minimized communication, which partitions the workload of the entire network and ensures moderate burden for each individual node as network grows. We propose eventual atomicity to ensure transaction atomicity across zones, which guarantees the efficient completion of transaction without the overhead of two-phase commit protocol. We also propose Chu-ko-nu mining to ensure the effective mining power in each zone is at the same level of the entire network, and makes an attack on any individual zone as hard as that on the entire network. Our experimental results show the effectiveness of our work. On a test-bed including 1,200 virtual machines worldwide to support 48,000 nodes, our system deliver
- On Bitcoin as a public randomness source. Bonneau J, Clark J, Goldfeder S. '15.
- Distributed Cryptography Based on the Proofs of Work. Andrychowicz M, and Dziembowski S. '14.
- Scalable, transparent, and post-quantum secure computational integrity. Ben-Sasson E, Bentov I, Horesh Y, Riabzev M. '18.
- Zerocoin: Anonymous distributed e-cash from bitcoin. Miers I, Garman C, Green M, Rubin AD. S&P '13.
- Zerocash: Decentralized anonymous payments from bitcoin. Sasson EB, Chiesa A, Garman C, Green M, Miers I, Tromer E, Virza M. S&P '14.
- "Monero": CryptoNote v2.0. Saberhagen N. '13?
- Rational Zero: Economic Security for Zerocoin with Everlasting Anonymity. Garman C, Green M, Miers I, Rubin A. FC '14.
- Mixcoin: Anonymity for bitcoin with accountable mixes. Bonneau J, Narayanan A, Miller A, Clark J, Kroll JA, Felten EW. '14.
- TumbleBit: An untrusted Bitcoin-compatible anonymous payment hub. Heilman E, Alshenibr L, Baldimtsi F, Scafuro A, Goldberg S. '16.
- Blindly Signed Contracts: Anonymous On-Blockchain and Off-Blockchain Bitcoin Transactions. Heilman E, Baldimtsi F, Goldberg S. FC '16.
- Coinshuffle: Practical decentralized coin mixing for bitcoin. Ruffing T, Moreno-Sanchez P, Kate A. ESORICS '14.
- Quantitative analysis of the full bitcoin transaction graph. Ron D, Shamir A. FC '13.
- How Did Dread Pirate Roberts Acquire and Protect His Bitcoin Wealth?. Ron D, Shamir A. FC '14.
- "MoneroLink": An Empirical Analysis of Linkability in the Monero Blockchain. Miller A, Möser M, Lee K, Narayanan A. '17.
- Provisions: Privacy-preserving proofs of solvency for Bitcoin exchanges. Dagher GG, Bünz B, Bonneau J, Clark J, Boneh D. CCS '15.
- Increasing Anonymity in Bitcoin. Saxena A, Misra J, Dhar A. FC '14.
- Blindcoin Blinded, Accountable Mixes for Bitcoin. Valenta L, Rowan B. FC '15.
- Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts. Kosba A, Miller A, Shi E, Wen Z, Papamanthou C. SP '16
- Could Network Information Facilitate Address Clustering in Bitcoin?. Neudecker T, Hartenstein H. FC '17.
- Blind signatures for untraceable payments. Chaum D. CRYPTO '83.
- Exchange Pattern Mining in the Bitcoin Transaction Directed Hypergraph. Ranshous S, Joslyn A, Kreyling S, Nowak K, Samatova N, West C, Winters C. FC '17.
- Confidential Assets. Poelstra A, Back A, Friedenbach M, Maxwell G, Wuille P. FC '17.
- Mixing Confidential Transactions: Comprehensive Transaction Privacy for Bitcoin. Ruffing T, Moreno-Sanchez P. FC '17.
- Switch Commitments: A Safety Switch for Confidential Transactions. Ruffing T, Malavolta G. FC '17.
- CoinParty: Secure Multi-Party Mixing of Bitcoins. Ziegeldorf, J.H., Grossmann, F., Henze, M., Inden, N. and Wehrle, K. CODASPY '15.
- "Ethereum": A next-generation smart contract and decentralized application platform. Vitalik Buterin. '14.
- Ethereum: A secure decentralised generalised transaction ledger. Wood G. '14.
- Fair Two-Party Computations via Bitcoin Deposits. Andrychowicz M, Dziembowski S, Malinowski D, Mazurek Ł. FC '14.
- Step by Step Towards Creating a Safe Smart Contract: Lessons and Insights from a Cryptocurrency Lab. Delmolino K, Arnett M, Kosba A, Miller A, Shi E. FC '16.
- EthIKS: Using Ethereum to audit a CONIKS key transparency log. Bonneau J. FC '16.
- "Oyente": Making Smart Contracts Smarter. Luu L, Chu DH, Olickel H, Saxena P, Hobor A. CCS '16.
- The Ring of Gyges: Investigating the Future of Criminal Smart Contracts. Juels A, Kosba A, Shi E. CCS '16.
- Town crier: An authenticated data feed for smart contracts. Zhang F, Cecchetti E, Croman K, Juels A, Shi E. CCS '16.
- A Smart Contract for Boardroom Voting with Maximum Voter Privacy. McCorry P, Shahandashti SF, Hao F. FC '17.
- Constant-deposit multiparty lotteries on Bitcoin. Bartoletti M, Zunino R. FC '17.
- Blockstack Technical Whitepaper. Muneeb A., Ryan S., Jude N, Michael F. '17
- Storj A Peer-to-Peer Cloud Storage Network. Shawn W., Tome B., Josh B.,James P., Gordon H., Patrick G., Philip H., Chris P. '16
- IPFS - Content Addressed, Versioned, P2P File System. Benet J. '15
- BigchainDB: A Scalable Blockchain Database. McConaghy T, Marques R, Müller A, De Jonghe D, McConaghy T, McMullen G, Henderson R, Bellemare S, Granzotto A. '17
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent