区块链共识论文列表

整理了一下区块链共识论文，欢迎大家贡献，github地址为：https://github.com/LinkChain/blockchain-papers

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 parliamentLamport 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 toleranceCastro, 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 systemNakamoto, 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 velocityRen 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 blockchainMartino 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.

20. [Stellar] The stellar consensus protocol: A federated model for internet-level consensus

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 SecurelyTuyet 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 throughput and capacity over Bitcoin and Ethereum network.

37.The Bitcoin Backbone Protocol: Analysis and Applications. Garay, Juan, Aggelos Kiayias, and Nikos Leonardos. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2015.

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary relative to network synchronicity; we show our results to be tight under high synchronization.Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that Nakamoto’s suggestion falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3 . The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary’s hashing power is strictly less than 1/2 , while the adversarial bound needed for security decreases as the network desynchronizes.

38.Byteball Byteball: A decentralized system for storage and transfer of value.Huryumov, Anton.

Byteball is a decentralized system that allows tamper proof storage of arbitrary data, including data that represents transferrable value such as currencies, property titles, debt, shares, etc. Storage units are linked to each other such that each storage unit includes one or more hashes of earlier storage units, which serves both to confirm earlier units and establish their partial order. The set of links among units forms a DAG (directed acyclic graph). There is no single central entity that manages or coordinates admission of new units into the database, everyone is allowed to add a new unit provided that he signs it and pays a fee equal to the size of added data in bytes. The fee is collected by other users who later confirm the newly added unit by including its hash within their own units. As new units are added, each earlier unit receives more and more confirmations by later units that include its hash, directly or indirectly.
There is an internal currency called ‘bytes’ that is used to pay for adding data into the decentralized database. Other currencies (assets) can also be freely issued by anyone to represent property rights, debt, shares, etc. Users can send both bytes and other currencies to each other to pay for goods/services or to exchange one currency for another; the transactions that move the value are added to the database as storage units. If two transactions try to spend the same output (double-spend) and there is no partial order between them, both are allowed into the database but only the one that comes earlier in the total order is deemed valid. Total order is established by selecting a single chain on the DAG (the main chain) that is attracted to units signed by known users called witnesses. A unit whose hash is included earlier on the main chain is deemed earlier on the total order. Users choose the witnesses by naming the user-trusted witnesses in every storage unit. Witnesses are reputable users with real-world identities, and users who name them expect them to never try to double-spend. As long as the majority of witnesses behave as expected, all double-spend attempts are detected in time and marked as such. As witnesses-authored units accumulate after a user’s unit, there are deterministic (not probabilistic) criteria when the total order of the user’s unit is considered final.
Users store their funds on addresses that may require more than one signature to spend (multisig). Spending may also require other conditions to be met, including conditions that are evaluated by looking for specific data posted to the database by other users (oracles).Users can issue new assets and define rules that govern their transferability. The rules can include spending restrictions such as a requirement for each transfer to be cosigned by the issuer of the asset, which is one way for financial institutions to comply with existing regulations.
Users can also issue assets whose transfers are not published to the database, and therefore not visible to third parties. Instead, the information about the transfer is exchanged privately between users, and only a hash of the transaction and a spend proof (to prevent double-spends) are published to the database.

39.Blockchain-free cryptocurrencies: A framework for truly decentralised fast transactionsBoyen, Xavier, Christopher Carr, and Thomas Haines. (2016).

The “blockchain” distributed ledger pioneered by Bitcoin is effective atpreventing double-spending, but inherently attracts (1) “user cartels” and (2) incompressible delays, as a result of linear verification and a winner-takes-all incentivelottery.
We propose to forgo the “blocks” and “chain” entirely, and build a truly distributed ledger system based on a lean graph of cross-verifying transactions, whichnow become the main and only objects in the system. A fully distributed consensus mechanism, based on progressive proofs of work with predictable incentives,ensures rapid convergence even across a large network of unequal participants, whoall get rewards working at their own pace. Graph-based affirmation fosters snappyresponse through automatic scaling, while application-agnostic design supports allmodern cryptocurrency features such as multiple denominations, swaps, securitisation, scripting, smart contracts, etc.
We prove theoretically, and experimentally verify, our proposal to show itachieves a crucial “convergence” property — meaning that any valid transactionentering the system will quickly become enshrined into the ancestry upon which allfuture transactions will rest.

40.[Avalanche] Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrenciesRocket, Team.(2018).

This paper introduces a new family of leaderless Byzantinefault tolerance protocols, built around a metastable mechanism. These protocols provide a strong probabilistic safetyguarantee in the presence of Byzantine adversaries, whiletheir concurrent nature enables them to achieve high throughput and scalability. Unlike blockchains that rely on proofof-work, they are quiescent and green. Unlike traditionalconsensus protocols having leader nodes that process O(n)information (in terms of number of bits exchanged), no nodeprocesses more than O(k) for some security parameter k.
The paper describes the protocol family, instantiates it inthree separate protocols, analyzes their guarantees, and describes how they can be used to construct the core of aninternet-scale electronic payment system. The system isevaluated in a large scale deployment. Experiments demonstrate that the system can achieve high throughput (3400 tps),provide low confirmation latency (1.35 sec), and scale wellcompared to existing systems that deliver similar functionality. For our implementation and setup, the bottleneck of thesystem is in transaction verification.

41.[SPECTRE] SPECTRE: A Fast and Scalable Cryptocurrency ProtocolSompolinsky, Yonatan, Yoad Lewenberg, and Aviv Zohar.IACR Cryptology ePrint Archive 2016 (2016): 1159.

A growing body of research on Bitcoin and other permissionlesscryptocurrencies that utilize Nakamoto’s blockchain has shown that they donot easily scale to process a high throughput of transactions, or to quicklyapprove individual transactions; blocks must be kept small, and their creationrates must be kept low in order to allow nodes to reach consensus securely. Asof today, Bitcoin processes a mere 3-7 transactions per second, and transactionconfirmation takes at least several minutes.
We present SPECTRE, a new protocol for the consensus core ofcrypto-currencies that remains secure even under high throughput and fastconfirmation times. At any throughput, SPECTRE is resilient to attackerswith up to 50% of the computational power (up until the limit defined bynetwork congestion and bandwidth constraints). SPECTRE can operate athigh block creation rates, which implies that its transactions confirm in mereseconds (limited mostly by the round-trip-time in the network).
Key to SPECTRE’s achievements is the fact that it satisfies weakerproperties than classic consensus requires. In the conventional paradigm, theorder between any two transactions must be decided and agreed upon by allnon-corrupt nodes. In contrast, SPECTRE only satisfies this with respect totransactions performed by honest users. We observe that in the context ofmoney, two conflicting payments that are published concurrently could onlyhave been created by a dishonest user, hence we can afford to delay theacceptance of such transactions without harming the usability of the system.Our framework formalizes this weaker set of requirements for a crypto-currency’sdistributed ledger. We then provide a formal proof that SPECTRE satisfiesthese requirements.

42.[DAGcoin] DAGcoin Whitepaper Ribero Y, Raissar D. 2015.

There are more than 700 different cryptocurrencies available around theworld. Majority of them are based on blockchain technology, which wasinvented in 2009. When bitcoin first came live. Blockchain technology hasbeen going through many improvements such as proof of stake insteadof proof of work, many different mining algorithms are in use and latestimprovement, segwit, went live with litecoin and other coins. Still thereare some major issues regarding the blockchain technology.
First issue regarding blockchain is scalability. On a bigger scale - listeningtransactions, putting them into the blocks and trying to get confirmationand consensus over the blocks - it just takes time. It doesn’t matter much,either it’s POW or POS, even compared to some centralised transactionplatforms, such blockchain designs are too slow.
Another issue is the cost of proof of work. Today, bitcoin transaction, whichinitially was made to bring down the cost of the money transactions, isone of the most expensive transactions in the world. POW isn’t energyeffective way to secure ledgers.
Third issue is the fact what the cryptocurrency community has beenacknowledged that some way, majority of the miners, are holding the keyof final word for the new improvements and enhancements inside thenetwork. Miners are like a separate interest group, with their owneconomic incentives, besides being the inducers who are transactinginside the network. That has been the blocker to introduce new features inbitcoin blockchain. For example the activation of segwit and etherumblockchain moving from POW to POS.

43.[HotStuff] HotStuff: BFT Consensus in the Lens of Blockchain Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, Ittai Abraham. 2018

We present HotStuff, a leader-based Byzantine fault-tolerant replication protocol for the partially synchronous model. Once network communication becomes synchronous, HotStuff enables a correct leader to drive the protocol to consensus at the pace of actual (vs. maximum) network delay--a property called responsiveness--and with communication complexity that is linear in the number of replicas. To our knowledge, HotStuff is the first partially synchronous BFT replication protocol exhibiting these combined properties. HotStuff is built around a novel framework that forms a bridge between classical BFT foundations and blockchains. It allows the expression of other known protocols (DLS, PBFT, Tendermint, Casper), and ours, in a common framework.
Our deployment of HotStuff over a network with over 100 replicas achieves throughput and latency comparable to that of BFT-SMaRt, while enjoying linear communication footprint during leader failover (vs. quadratic with BFT-SMaRt).