Alexandru Cojocaru, Juan A. Garay, Aggelos Kiayias, Fang Song · 5 authors
Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems and foundations of the consensus problem. At the same time, the rapid development in quantum computing makes the threats to cryptography more and more concerning. In this work, we revisit the formal security of the core of the Bitcoin consensus protocol, called the Bitcoin backbone (Eurocrypt 2015), in the presence of quantum adversaries -- i.e. adversaries equipped with quantum computers.
We show that the security of the Bitcoin backbone holds under a quantum analogue of the ``honest majority'' assumption that we develop. The critical ingredient of proving security of the blockchain is to analyzing the quantum query complexity of a Chain-of-Proofs-of-Work search problem. This problem in turn reduces to a problem we call multi-solution Bernoulli search, for which we establish its quantum query complexity. This can be viewed as an extension of a threshold direct product theorem to an average-case unstructured search problem. Our proof, adding to active recent efforts, simplifies and generalizes the powerful recording technique due to Zhandry (Crypto 2019).
Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded so that each quantum query is worth $O(p^{-1/2})$ classical ones, where $p$ is the probability of success of a single classical query to the protocol's underlying hash function. Perhaps surprisingly, the wait time for safe settlement of transactions in the case of quantum adversaries matches (up to a constant) the safe settlement time in the classical case and thus does not result in any further overhead.
Achieving the equilibrium between scalability, sustainability and security has prevailed as the ideal solution for decentralized blockchain applications over the last years. Several approaches have been proposed being Ethereum a solid proposal among them. Ethereum is on the path of a major protocol improvement called Ethereum 2.0 (Eth2), implementing Sharding and introducing the Proof-of-Stake (PoS). As the change of consensus mechanism is a delicate matter, this improvement will be achieved through different phases, the first of which is the implementation of the Beacon Chain. The implementation of the latest has been stated with the recent launch of the Eth2 main net. In this work, we introduce an Eth2 network monitor tool, called Armiarma, used to generate a complete analysis of the p2p network of the Eth2 main net. In this paper, we present some of the results of what this Eth2 network monitor can achieve.
Leonid Al'bertovich Merkin-Janson, Ruslan Rezin, Nikolay Konstantinovich Vasilyev
In this paper we consider the software architecture of InnoChain, a distributed ledger system (DLS) with 5 levels of formal verification, including a formally-verified underlying operating system (OS). The objective of this architecture is to achieve a higher level of DLS dependability compared to more traditional software architectures and quality assurance (QA) methods. The architecture of InnoChain includes (1) a programming language for smart contracts which is a domain-specific language with formal semantics embedded into CakeML, which is a functional language ofthe ML family; this allows us to carry out formal verification of smart contracts' correctness properties using higher-order logic systems, such as HOL4; (2) trusted compilation of smart contracts into the machine code using the verified compiler available for CakeML, rather than relying on a virtual machine for execution of smart contracts; (3) using CakeML for implementation of InnoChain node functionality which allows for formal verification of code correctness and trusted compilation into the machine code; (4) formal verification of the consensus protocol used InnoChain, namely HotStuff BFT; (5) using seL4, a formally-verified microkernel, as the underlying OS for InnoChain instead of more traditional general-purpose OSes such as Linux. The proposed verified architecture will allow InnoChain to be used in mission-critical applications, such as the decentralized Aircraft Fuelling Control System which is currently under development for JSC Aeroflot, the Russian national air carrier.
Vladimir Kukharenko, Kirill Ziborov, Rafael Faritovich Sadykov, Alexandr Naumchev · 6 authors
The extent of formal verification methods applied to industrial projects has always been limited. The proliferation of distributed ledger systems (DLS), also known as blockchain, is rapidly changing the situation. Since the main area of DLSs' application is the automation of financial transactions, the properties of predictability and reliability are critical for implementing such systems. The actual behavior of the DLS is determined by the chosen consensus protocol, which properties require strict specification and formal verification. Formal specification and verification of the consensus protocol is necessary but not sufficient. It is required to ensure that the software implementation of the DLS nodes complies with this protocol. The verified software implementation of the protocol must run on a fairly reliable operating system. The so-called “smart contracts”, which are an important part of the applied implementations of specific business processes based on DLSs, must be verifiable as well. In this paper, we describe an ongoing industrial project that will result in a DLS verified at least at the four technological levels described above. We then share our experience with the formal specification and verification of HotStuff, a leader-based fault-tolerant protocol that ensures reaching distributed consensus in the presence of Byzantine processes.
Kendric Hood, Joseph Oglio, Mikhail Nesterenko, Gokarna Sharma
We consider operation of blockchain-based cryptocurrency in case of partitioning. We define the Partitionable Blockchain Consensus Problem. The problem may have an interesting solution if the partitions proceed independently by splitting accounts. We prove that this problem is not solvable in the asynchronous system. The peers in the two partitions may not agree on the last jointly mined block or, alternatively, on the starting point of independent concurrent computation. We introduce a family of detectors that enable a solution. We establish the relationship between detectors. We present the algorithm that solves the Partitionable Blockchain Consensus Problem using our detectors. We extend our solution to multiple splits, message loss and to partition merging. We simulate and evaluate the performance of detectors, discuss the implementation of the detectors and future work.
Mwrwan Abubakar, Zakwan Jaroucheh, Ahmed Al‐Dubai, Bill Buchanan
The original consensus algorithm - Proof of Work (PoW) has been widely utilized in the blockchain systems and is been adopted by many cryptocurrencies, such as Bitcoin and Ethereum, among many others. Nevertheless, the concept has received criticisms over its high energy consumption. This is induced by the necessity for all nodes in the network to communicate synchronously for consensus over the ledger state to be reached. Additionally, the concept has also shown clear limitations regarding performance and throughput. In trying to rectify this issue, the paper proposes the introduction of a new hybrid consensus protocol known as the Proof of Notarized Work (PoNW). The PoNW concept reduces the number of nodes that need to achieve consensus, thereby reducing the overall energy consumption in the current PoW. In addition, we propose using a decentralized random beacon to select nodes to participate in the mining process randomly. Therefore, our algorithm promises to achieve higher scalability and consistency levels without conceding its decentralization. When this is paired with a Byzantine Fault Tolerance (PBFT) verification, the system gains the ability to replace the probabilistic finality in current PoW with absolute finality in a matter of seconds, solving the issue of scalability. Finally, the study will look into the proposed algorithm's security and provides threats model to insure an acceptable failure probability. Results from the security analysis have shown that our consensus algorithm ensures forks cannot occur, and it remains secure and consistent even amid numerous attacks.
Practical Byzantine Fault Tolerance (PBFT) consensus mechanism shows a great potential to break the performance bottleneck of the Proof-of-Work (PoW)-based blockchain systems, which typically support only dozens of transactions per second and require minutes to hours for transaction confirmation. However, due to frequent inter-node communications, PBFT mechanism has a poor node scalability and thus it is typically adopted in small networks. To enable PBFT in large systems such as massive Internet of Things (IoT) ecosystems and blockchain, in this article, a scalable multi-layer PBFT-based consensus mechanism is proposed by hierarchically grouping nodes into different layers and limiting the communication within the group. We first propose an optimal double-layer PBFT and show that the communication complexity is significantly reduced. Specifically, we prove that when the nodes are evenly distributed within the sub-groups in the second layer, the communication complexity is minimized. The security threshold is analyzed based on faulty probability determined (FPD) and faulty number determined (FND) models, respectively. We also provide a practical protocol for the proposed double-layer PBFT system. Finally, the results are extended to arbitrary-layer PBFT systems with communication complexity and security analysis. Simulation results verify the effectiveness of the analytical results.
Christian Cachin, Angelo De, Pedro Moreno-Sánchez, Björn Tackmann · 5 authors
The advent of Bitcoin paved the way for a plethora of blockchain systems supporting diverse applications beyond cryptocurrencies. Although in-depth studies of the consensus protocols as well as the privacy of blockchain transactions are available, there is no formal model of the transaction semantics that a blockchain is supposed to guarantee.
Xuan Luo, Zehua Wang, Wei Cai, Xiuhua Li · 5 authors
Traditional centralized token exchange (CEX) has been suffering from hacking due to the centralized management of users’ tokens. In contrast, decentralized token exchange (DEX) maintains users’ assets by smart contracts in a decentralized manner, but introduces additional overhead in terms of gas fee and transaction confirmation latency. Hybrid decentralized token exchange (HEX) has been proposed to combine the benefits of CEX and DEX. However, existing HEX is criticized for two issues. First, trading transactions are time-consuming and expensive for frequent token traders. Second, excessive simultaneous transactions might cause the pending transaction congestion in the Ethereum network. In this paper, we propose a payment channel based HEX, which extends existing solutions by adding a new payment channel layer to benefit frequent traders and alleviate the pending transaction congestion. Besides, we propose the very first gas-price vs. transaction-confirmation-latency function to guide Ethereum transaction issuers to choose an optimal gas price that minimizes the overall cost. Extensive simulations are conducted to compare the cost in the proposed HEX with that in the conventional HEX. The results demonstrate the effectiveness of our proposed mechanism in terms of reducing gas fees and transaction confirmation latency for frequent traders as well as the pending transaction congestion in Ethereum.
Proof-of-work (PoW) based blockchain protocols, are protocols that organize data into blocks, connected through the use of a hash function to form chains, and which make use of PoW to reach agreement, i.e., proofs that require spending some amount of computational power to be generated. This type of protocols rose into prominence with the advent of Bitcoin, the first protocol that provably implements a distributed transaction ledger against an adversary that controls less than half of the total computational power in the network, in a setting where protocol participants join and leave dynamically without the need for a registration service. Protocols in this class were also the first to be shown sufficient to solve consensus under similar conditions, a problem of fundamental importance in distributed computing. In this thesis, we explore foundational issues of PoW-based blockchain protocols that mainly have to do with the assumptions required to ensure their safe operation. We start by examining whether a common random string that is shared at the start of the protocol execution among the protocol participants is required to efficiently run such protocols. Bitcoin's security is based on the existence of such a string, called the genesis block. On the other hand, protocols found in previous works that do not assume such a setup are inefficient, in the sense that their round complexity strongly depends on the number of protocol participants. Our first contribution is the construction of efficient PoW-based blockchain protocols that provably implement a distributed ledger and consensus without such setup. Next, we turn our attention to the PoW primitive. All previous analyses model PoW using a random oracle. While satisfactory as a sanity check, the random oracle methodology has received significant criticism and shown not to be sound. We make progress by introducing a non-idealized security model and appropriate computational assumptions that are sufficient to implement a distributed ledger or consensus when combined with the right PoW-based protocol. Finally, we analyze GHOST, a recently proposed blockchain protocol, and prove its security against a byzantine adversary under similar assumptions as Bitcoin. Previous works only considered specific attacks.
Decentralized blockchain platforms have enabled the secure exchange of crypto-assets without the intermediation of trusted authorities. To this purpose, these platforms rely on a peer-to-peer network of byzantine nodes, which collaboratively maintain an append-only ledger of transactions, called blockchain. Transactions represent the actions required by users, e.g. the transfer of some units of crypto-currency to another user, or the execution of a smart contract which distributes crypto-assets according to its internal logic. Part of the nodes of the peer-to-peer network compete to append transactions to the blockchain. To do so, they group the transactions sent by users into blocks, and update their view of the blockchain state by executing these transactions in the chosen order. Once a block of transactions is appended to the blockchain, the other nodes validate it, re-executing the transactions in the same order. The serial execution of transactions does not take advantage of the multi-core architecture of modern processors, so contributing to limit the throughput. In this paper we develop a theory of transaction parallelism for blockchains, which is based on static analysis of transactions and smart contracts. We illustrate how blockchain nodes can use our theory to parallelize the execution of transactions. Initial experiments on Ethereum show that our technique can improve the performance of nodes.
The General Purpose Atomic Crosschain Transaction protocol allows composable programming across multiple Ethereum blockchains. It allows for inter-contract and inter-blockchain function calls that are both synchronous and atomic: if one part fails, the whole call execution tree of function calls is rolled back. The protocol operates on existing Ethereum blockchains without modification. It works for both public permissioned and consortium blockchains. Additionally, the protocol is expected to work across heterogeneous blockchains other than Ethereum. This paper describes the protocol, analyses it in terms of Gas usage and Finalised Block Periods for three scenarios: reading a value from one blockchain to another, writing a value from one blockchain to another, and a trade finance system involving five contracts on five blockchains with a complex call execution tree, and provides an initial security analysis that shows that the protocol has Safety and Liveness properties.
Blockchains have captured the attention of many, resulting in an abundance of new systems available for use. However, selecting an appropriate blockchain for an application is challenging due to the lack of comparative information discussing core metrics such as throughput, latency and scalability. Although a number of efforts have been devoted to performance evaluation, there is limited work dedicated to blockchains that are both efficient, due to avoiding complex Proof-of-Work cryptopuzzles, and secure, because they solve consensus deterministically despite Byzantine failures. In this paper, we evaluate the performance of three blockchains that cope with such malicious behaviors, namely Burrow, Quorum and Red Belly Blockchain. To this end, we modified the Hyperledger Caliper benchmark to solve three main limitations: unnecessary overheads, online cryptographic signatures and centralized clients. Our results identify the maximum send rate that Burrow and Quorum can process, and that Red Belly Blockchain can offer an 8-times higher throughput than the other blockchains.
For a blockchain, consensus is the foundation protocol that enables cryptocurrencies such as Bitcoin to maintain state. Additionally, to ensure safety and liveness for a publicly accessible and verifiable ledger, fault tolerance must be robust. However, there appears to be a degree of misunderstanding about how consensus is applied across blockchains. To assist researchers considering variations between them, this study presents a rational classification of consensus methods applied to current blockchains. The study provides a survey of 19 methods classified by the scarce resource they employ: clock-cycles, bits, tokens, votes, time, and biometrics. Blockchain implementations are split between consensus algorithms requiring proof of resource and those that use majority voting to update the ledger.
Callbacks are an effective programming discipline for implementing event-driven programming, especially in environments like Ethereum which forbid shared global state and concurrency. Callbacks allow a callee to delegate the execution back to the caller. Though effective, they can lead to subtle mistakes principally in open environments where callbacks can be added in a new code. Indeed, several high profile bugs in smart contracts exploit callbacks. We present the first static technique ensuring modularity in the presence of callbacks and apply it to verify prominent smart contracts. Modularity ensures that external calls to other contracts cannot affect the behavior of the contract. Importantly, modularity is guaranteed without restricting programming. In general, checking modularity is undecidable—even for programs without loops. This paper describes an effective technique for soundly ensuring modularity harnessing SMT solvers. The main idea is to define a constructive version of modularity using commutativity and projection operations on program segments. We believe that this approach is also accessible to programmers, since counterexamples to modularity can be generated automatically by the SMT solvers, allowing programmers to understand and fix the error. We implemented our approach in order to demonstrate the precision of the modularity analysis and applied it to real smart contracts, including a subset of the 150 most active contracts in Ethereum. Our implementation decompiles bytecode programs into an intermediate representation and then implements the modularity checking using SMT queries. Overall, we argue that our experimental results indicate that the method can be applied to many realistic contracts, and that it is able to prove modularity where other methods fail.
Ryan Henry, Alyssa Tory, Sophie Henry, Isabella Henry · 5 authors
In this short paper, we revisit the celebrated Naor?Naor?Reingold (NNR) protocol for ?[convincing] people you know where Waldo is without revealing information about his location?. We observe that, despite oft-repeated claims to the contrary, the NNR protocol is neither zero-knowledge nor a proof of knowledge. We propose a slightly more elaborate version that is both of these things?but still eminently suitable for children?s playdates (and the classroom).
Sina Rafati Niya, Raphael Beckmann, Burkhard Stiller
The integration of the Internet-of-Things (IoT) and Blockchain (BC) for strong trust and decentralization shows potentials in use cases, such as supply chain tracing, smart cities, and health care. As a great number of IoT devices interacting in such cases, it is crucial to provide scalable and secure mechanisms for IoT data persistence within BCs. In this regard, sharding mechanisms have been employed to enhance the scalability of BCs. However, disconnections and delays of a BC's distributed network can cause concerns for inter-shard and inter-miner synchronizations, eventually preventing the BC from reaching a high throughput. Thus, this work develops an IoT-oriented permissioned BC, which covers via a scalable Distributed Ledger (DL) a novel sharding mechanism for unstable distributed networks. Therefore, DLIT (Distributed Ledger for IoT Data) offers a novel two-layered transaction distribution, validation, and inter-shard synchronization, combined with authentication and verification mechanisms in support of a viable security level.
Although blockchain, the supporting technology of Bitcoin and various cryptocurrencies, has offered a potentially effective framework for numerous applications, it still suffers from the adverse affects of the impossibility triangle. Performance, security, and decentralization of blockchains normally do not scale simultaneously with the number of participants in the network. The recent introduction of error correcting codes in sharded blockchain by Li et al. partially settles this trilemma, boosting throughput without compromising security and decentralization. In this paper, we improve the coded sharding scheme in three ways. First, we propose a novel 2-Dimensional Sharding strategy, which inherently supports cross-shard transactions, alleviating the need for complicated inter-shard communication protocols. Second, we employ distributed storage techniques in the propagation of blocks, improving latency under restricted bandwidth. Finally, we incorporate polynomial cryptographic primitives of low degree, which brings coded blockchain techniques into the realm of feasible real-world parameters.
A popular method in practice offloads computation and storage in blockchains by relying on committing only hashes of off-chain data into the blockchain. This mechanism is acknowledged to be vulnerable to a stalling attack: the blocks corresponding to the committed hashes may be unavailable at any honest node. The straightforward solution of broadcasting all blocks to the entire network sidesteps this data availability attack, but it is not scalable. In this paper, we propose ACeD, a scalable solution to this data availability problem with $O(1)$ communication efficiency, the first to the best of our knowledge. The key innovation is a new protocol that requires each of the $N$ nodes to receive only $O(1/N)$ of the block, such that the data is guaranteed to be available in a distributed manner in the network. Our solution creatively integrates coding-theoretic designs inside of Merkle tree commitments to guarantee efficient and tamper-proof reconstruction; this solution is distinct from Asynchronous Verifiable Information Dispersal (in guaranteeing efficient proofs of malformed coding) and Coded Merkle Tree (which only provides guarantees for random corruption as opposed to our guarantees for worst-case corruption). We implement ACeD with full functionality in 6000 lines of Rust code, integrate the functionality as a smart contract into Ethereum via a high-performance implementation demonstrating up to 10,000 transactions per second in throughput and 6000x reduction in gas cost on the Ethereum testnet Kovan.
Vitor N. Coelho, Rodolfo Pereira Araújo, Haroldo Gambini Santos, Wang Yong Qiang · 5 authors
Mixed-integer mathematical programming has been widely used to model and solve challenging optimization problems. One interesting feature of this technique is the ability to prove the optimality of the achieved solution, for many practical scenarios where a linear programming model can be devised. This paper explores its use to model very strong Byzantine adversaries, in the context of distributed consensus systems. In particular, we apply the proposed technique to find challenging adversarial conditions on a state-of-the-art blockchain consensus: the Neo dBFT. Neo Blockchain has been using the dBFT algorithm since its foundation, but, due to the complexity of the algorithm, it is challenging to devise definitive algebraic proofs that guarantee safety/liveness of the system (and adjust for every change proposed by the community). Core developers have to manually devise and explore possible adversarial attacks scenarios as an exhaustive task. The proposed multi-objective model is intended to assist the search of possible faulty scenario, which includes three objective functions that can be combined as a maximization problem for testing one-block finality or a minimization problem for ensuring liveness. Automated graphics help developers to visually observe attack conditions and to quickly find a solution. This paper proposes an exact adversarial model that explores current limits for practical blockchain consensus applications such as dBFT, with ideas that can also be extended to other decentralized ledger technologies.
The availability-finality dilemma says that blockchain protocols cannot be both available under dynamic participation and safe under network partition. Snap-and-chat protocols have recently been proposed as a resolution to this dilemma. A snap-and-chat protocol produces an always available ledger containing a finalized prefix ledger which is always safe and catches up with the available ledger whenever network conditions permit. In contrast to existing handcrafted finality gadget based designs like Ethereum 2.0's consensus protocol Gasper, snap-and-chat protocols are constructed as a black-box composition of off-the-shelf BFT and longest chain protocols. In this paper, we consider system aspects of snap-and-chat protocols and show how they can provide two important features: 1) accountability, 2) support of light clients. Through this investigation, a deeper understanding of the strengths and challenges of snap-and-chat protocols is gained.
Blockchain technology started as the backbone for cryptocurriencies and it has emerged as one of the most interesting technologies of the last decade. It is a new paradigm able to modify the way how industries transact. Today, the industries’ concern is about their ability to handle a high volume of data transactions per second while preserving both decentralization and security. Both decentralization and security are guaranteed by the mathematical strength of cryptographic primitives. There are two main approaches to achieve consensus: the Proof-of-Work based blockchains—PoW—and the Proof-of-Stake—PoS. Both of them come with some pros and drawbacks, but both rely on cryptography. In this survey, we present a review of the main consensus procedures, including the new consensus proposed by Algorand: Pure Proof-of-Stake—Pure PoS. In this article, we provide a framework to compare the performances of PoW, PoS and the Pure PoS, based on throughput and scalability.
In this paper, we propose a scheme called securePrune for reducing the storage space of a full node and synchronization time of bootstrapping nodes joining the Peer-to-Peer (P2P) network in an Unspent Transaction Outputs (UTXO) based blockchain like bitcoin using RSA accumulators. The size of the bitcoin blockchain is growing linearly with transactions. We propose a new block structure to represent the state of a blockchain also called UTXO set by including an accumulator of a state in the block header and proofs of knowledge for inclusion and deletion of the transactions of the current block in the block. In our scheme, the miners periodically release a snapshot of the blockchain state. The other full nodes in the network, securely prune the historical blocks after attaining the required number of confirmations for the snapshot block, which in turn confirms the snapshot of the state through an accumulator specified in the block header and proofs inside the block. The secure and periodic pruning of the old blocks, reduce the synchronization time for a new node joining into the network. The simulation results demonstrate a significant reduction in the storage space of a full node and bootstrapping cost of the new nodes.