Papers tagged as Blockchains
  1. EOSAFE: Security Analysis of EOSIO Smart Contracts 2021 Blockchains Cryptocurrency SmartContracts Usenix
    Ningyu He, Ruiyi Zhang, Haoyu Wang, Lei Wu, Xiapu Luo, Yao Guo, Ting Yu, Xuxian Jiang

    The EOSIO blockchain, one of the representative Delegated Proof-of-Stake (DPoS) blockchain platforms, has grown rapidly recently. Meanwhile, a number of vulnerabilities and high-profile attacks against top EOSIO DApps and their smart contracts have also been discovered and observed in the wild, resulting in serious financial damages. Most of the EOSIO smart contracts are not open-sourced and typically compiled to WebAssembly (Wasm) bytecode, thus making it challenging to analyze and detect the presence of possible vulnerabilities. In this paper, we propose EOSAFE, the first static analysis framework that can be used to automatically detect vulnerabilities in EOSIO smart contracts at the bytecode level. Our framework includes a practical symbolic execution engine for Wasm, a customized library emulator for EOSIO smart contracts, and four heuristic-driven detectors to identify the presence of the four most popular vulnerabilities in EOSIO smart contracts. Experiments have shown that EOSAFE achieves promising results in detecting vulnerabilities, with an F1-measure of 98%. We have applied EOSAFE to all active 53,666 smart contracts in the ecosystem (as of November 15, 2019). Our results show that over 25% of the smart contracts are labeled vulnerable. We further analyze possible exploitation attempts on these vulnerable smart contracts and identify 48 in-the-wild attacks (27 of them have been confirmed by DApp developers), which have resulted in financial loss of at least 1.7 million USD.

  2. Bitcoin-Compatible Virtual Channels 2021 Blockchains Oakland UC
    Lukas Aumayr, Oǧuzhan Ersoy, Andreas Erwig, Sebastian Faust, Kristina Hostáková , Matteo Maffei, Pedro Moreno-Sanchez, Siavash Riahi

    Current permissionless cryptocurrencies such as
    Bitcoin suffer from a limited transaction rate and slow confirmation time, which hinders further adoption. Payment channels are
    one of the most promising solutions to address these problems,
    as they allow the parties of the channel to perform arbitrarily
    many payments in a peer-to-peer fashion while uploading only
    two transactions on the blockchain. This concept has been
    generalized into payment channel networks where a path of
    payment channels is used to settle the payment between two users
    that might not share a direct channel between them. However,
    this approach requires the active involvement of each user in the
    path, making the system less reliable (they might be offline),
    more expensive (they charge fees per payment), and slower
    (intermediaries need to be actively involved in the payment).
    To mitigate this issue, recent work has introduced the concept
    of virtual channels (IEEE S&P’19), which involve intermediaries
    only in the initial creation of a bridge between payer and payee,
    who can later on independently perform arbitrarily many offchain transactions. Unfortunately, existing constructions are only
    available for Ethereum, as they rely on its account model and
    Turing-complete scripting language. The realization of virtual
    channels in other blockchain technologies with limited scripting
    capabilities, like Bitcoin, was so far considered an open challenge.
    In this work, we present the first virtual channel protocols that
    are built on the UTXO-model and require a scripting language
    supporting only a digital signature scheme and a timelock functionality, being thus backward compatible with virtually every
    cryptocurrency, including Bitcoin. We formalize the security
    properties of virtual channels as an ideal functionality in the
    Universal Composability framework and prove that our protocol
    constitutes a secure realization thereof. We have prototyped and
    evaluated our protocol on the Bitcoin blockchain, demonstrating
    its efficiency: for n sequential payments, they require an offchain exchange of 9+2n transactions or a total of 3524+695n
    bytes, with no on-chain footprint in the optimistic case. This is
    a substantial improvement compared to routing payments in a
    payment channel network, which requires 8n transactions with
    a total of 3026n bytes to be exchanged.

  3. Lockable Signatures for Blockchains: Scriptless Scripts for All Signatures 2021 Blockchains Oakland Signatures
    Sri Aravinda Krishnan Thyagarajan, Giulio Malavolta

    Payment Channel Networks (PCNs) have given a huge boost to the scalability of blockchain-based cryptocurrencies: Beyond improving the transaction rate, PCNs enabled cheap cross-currency payments and atomic swaps. However, current PCNs proposals either heavily rely on special scripting features of the underlying blockchain (e.g. Hash Time Lock Contracts) or are tailored to a handful of digital signature schemes, such as Schnorr or ECDSA signatures. This leaves us in an unsatisfactory situation where many currencies that are being actively developed and use different signature schemes cannot enjoy the benefits of a PCN.

    In this work, we investigate whether we can construct PCNs assuming the minimal ability of a blockchain to verify a digital signature, for any signature scheme. In answering this question in the affirmative, we introduce the notion of lockable signatures, which constitutes the cornerstone of our PCN protocols. Our approach is generic and the PCN protocol is compatible with any digital signature scheme, thus inheriting all favorable properties of the underlying scheme that are not offered by Schnorr/ECDSA (e.g.\ aggregatable signatures or post-quantum security).

    While the usage of generic cryptographic machinery makes our generic protocol impractical, we view it as an important feasibility result as it may serve as the basis for constructing optimized protocols for specific signature schemes. To substantiate this claim, we design a highly efficient PCN protocol for the special case of Boneh-Lynn-Shacham (BLS) signatures. BLS signatures enjoy many unique features that make it a viable candidate for a blockchain, e.g. short, unique, and aggregatable signatures. Yet, prior to our work, no PCN was known to be compatible with it (without requiring an advanced scripting language). The cost of our PCN is dominated by a handful of calls to the BLS algorithms. Our concrete evaluation of these basic operations shows that users with commodity hardware can process payments with minimal overhead.

  4. Compact Certificates of Collective Knowledge 2021 Blockchains Certificates Oakland
    Silvio Micali and Leonid Reyzin and Georgios Vlachos and Riad S. Wahby and Nickolai Zeldovich

    We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.

    After defining compact certificates, we demonstrate an efficient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50-280× smaller and 300-4000× cheaper to verify than a natural baseline approach.

  5. Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices 2021 Blockchains Oakland Signatures ThresholdCryptography
    Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, Omer Shlomovits

    Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given
    time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient
    proactivization protocol tailored to this setting. While many proactivization protocols have been devised
    and studied in the literature, none of them have communication patterns ideal for threshold wallets. In
    particular a (t, n) threshold wallet is designed to have t parties jointly sign a transaction (of which only
    one may be honest) whereas even the best current proactivization protocols require at least an additional
    t − 1 honest parties to come online simultaneously to refresh the system.
    In this work we formulate the notion of refresh with offline devices, where any tρ parties may proactivize the system at any time and the remaining n−tρ offline parties can non-interactively “catch up” at
    their leisure. However, many subtle issues arise in realizing this pattern. We identify that this problem
    is divided into two settings: (2, n) and (t, n) where t > 2. We develop novel techniques to address both
    settings as follows:
    • We show that the (2, n) setting permits a tight tρ for refresh. In particular we give a highly
    efficient tρ = 2 protocol to upgrade a number of standard (2, n) threshold signature schemes to
    proactive security with offline refresh. This protocol can augment existing implementations of
    threshold wallets for immediate use– we show that proactivization does not have to interfere with
    their native mode of operation. This technique is compatible with Schnorr, EdDSA, and even
    sophisticated ECDSA protocols. By implementation we show that proactivizing two different recent
    (2, n) ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than
    200 bytes, and no extra round of communication.
    • For the general (t, n) setting we prove that it is impossible to construct an offline refresh protocol
    with tρ < 2(t−1), i.e. tolerating a dishonest majority of online parties. Our techniques are novel in
    reasoning about the message complexity of proactive security, and may be of independent interest.
    Our results are positive for small-scale decentralization (such as 2FA with threshold wallets), and negative
    for large-scale distributed systems with higher thresholds. We thus initiate the study of proactive security
    with offline refresh, with a comprehensive treatment of the dishonest majority case.

  6. Pointproofs: Aggregating Proofs for Multiple Vector Commitments 2020 Blockchains CCS SmartContracts ZK
    Sergey Gorbunov and Leonid Reyzin and Hoeteck Wee and Zhenfei Zhang

    Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific positions at a later time. In this work, we construct Pointproofs–a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values.

    We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state-of-art vector commitments.

    Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.

  7. SmartPulse: Automated Checking of Temporal Properties in Smart Contracts 2021 Blockchains FormalVerification Oakland SmartContracts
    Jon Stephens , Kostas Ferles , Benjamin Mariano , Shuvendu Lahiri , Isil Dillig

    Smart contracts are programs that run on the
    blockchain and digitally enforce the execution of contracts
    between parties. Because bugs in smart contracts can have
    serious monetary consequences, ensuring the correctness of such
    software is of utmost importance. In this paper, we present
    a novel technique, and its implementation in a tool called
    SMARTPULSE, for automatically verifying temporal properties
    in smart contracts. SMARTPULSE is the first smart contract
    verification tool that is capable of checking liveness properties,
    which ensure that “something good” will eventually happen
    (e.g., “I will eventually receive my refund”). We experimentally
    evaluate SMARTPULSE on a broad class of smart contracts and
    properties and show that (a) SMARTPULSE allows automatically
    verifying important liveness properties, (b) it is competitive with
    or better than state-of-the-art tools for safety verification, and (c)
    it can automatically generate attacks for vulnerable contracts.

  8. Red Belly: A Secure, Fair, and Scalable Open Blockchain BFT Blockchains Censorship Oakland
    Tyler Crain, Christopher Natoli, and Vincent Gramoli

    Blockchain has found applications to track ownership of digital assets. Yet, several blockchains were shown
    vulnerable to network attacks. It is thus crucial for companies
    to adopt secure blockchains before moving them to production.
    In this paper, we present Red Belly Blockchain (RBBC), the
    first secure blockchain whose throughput scales to hundreds
    of geodistributed consensus participants. To this end, we drastically revisited Byzantine Fault Tolerant (BFT) blockchains
    through three contributions: (i) defining the Set Byzantine Consensus problem of agreeing on a superblock of all proposed
    blocks instead of a single block; (ii) adopting a fair leaderless
    design to offer censorship-resistance guaranteeing the commit
    of correctly requested transactions; (iii) introducing sharded
    verification to limit the number of signature verifications
    without hampering security. We evaluate RBBC on up to 1000
    VMs of 3 different types, spread across 4 continents, and under
    attacks. Although its performance is affected by attacks, RBBC
    scales in that its throughput increases to hundreds of consensus
    nodes and achieves 30k TPS throughput and 3 second latency
    on 1000 VMs, hence improving by 3× both the latency and
    the throughput of its closest competitor.

  9. On the Optimality of Optimistic Responsiveness 2020 BFT Blockchains CCS Consensus
    Ittai Abraham and Kartik Nayak and Ling Ren and Nibesh Shrestha

    Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some optimistic conditions are met. In this work, we revisit this notion of optimistic responsiveness and present optimal latency results.

    We present a lower bound for Byzantine Broadcast that relates the latencies of optimistic and synchronous commits when the designated sender is honest and while the optimistic commit can tolerate some faults. We then present two matching upper bounds for tolerating f faults out of n = 2f +1 parties. Our first upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest and the optimistic commit can tolerate some faults. Our second upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest but the optimistic commit does not tolerate any faults. The presence of matching lower and upper bound results make both of the results tight for n = 2f + 1. Our upper bound results are presented in a state machine replication setting with a steady state leader who is replaced with a view-change protocol when they do not make progress. For this setting, we also present an optimistically responsive protocol where the view-change protocol is optimistically responsive too.

  10. Dumbo: Faster Asynchronous BFT Protocols 2020 BFT Blockchains CCS Consensus
    Bingyong Guo and Zhenliang Lu and Qiang Tang and Jing Xu and Zhenfeng Zhang

    HoneyBadgerBFT, proposed by Miller et al. [32] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with n reliable broadcast protocol (RBC) to have each node propose its input, followed by n asynchronous binary agreement protocol (ABA) to make a decision for each proposed value (n

    is the total number of nodes).

    In this paper, we propose two new atomic broadcast protocols (called Dumbo1, Dumbo2) both of which have asymptotically and practically better efficiency. In particular, the ACS of Dumbo1 only runs a small k
    (independent of n

    ) instances of ABA, while that of Dumbo2 further reduces it to constant! At the core of our techniques are two major observations: (1) reducing the number of ABA instances significantly improves efficiency; and (2) using multi-valued validated Byzantine agreement (MVBA) which was considered sub-optimal for ACS in [32] in a more careful way could actually lead to a much more efficient ACS.

    We implement both Dumbo1, Dumbo2 and deploy them as well as HB-BFT on 100 Amazon EC2 t2.medium instances uniformly distributed throughout 10 different regions across the globe, and run extensive experiments in the same environments. The experimental results show that our protocols achieve multi-fold improvements over HoneyBadgerBFT on both latency and throughput, especially when the system scale becomes moderately large.

  11. WI is Almost Enough: Contingent Payment All Over Again 2020 Blockchains CCS PaymentChannels
    Ky Nguyen and Miguel Ambrona and Masayuki Abe

    The problem of fair exchange consists of interchanging goods between two parties that do not trust each other. Despite known impossibility results, recent works leverage the block-chain and zero-knowledge proofs to implement zero-knowledge contingent payment (zkCP) systems that make fair exchange of digital goods possible. Implementing these systems in a secure and efficient way is a big challenge, as evidenced by several unsuccessful attempts from the literature. Campanelli et al. (ACM CCS 2017) discovered a vulnerability on an existing zkCP proposal based on SNARKs (succinct non-interactive arguments of knowledge) and suggested several repairs. Fuchsbauer (ACM CCS 2019) found a flaw in the mentioned countermeasures. In particular, he showed that witness-indistinguishability (WI) is not sufficient for the zkCP schemes proposed by Campanelli et al. to be secure. In this work, we observe that a slightly stronger notion of WI, that we coin trapdoor subversion WI (tS-WI), rules out Fuchsbauer’s attack. We formally define security properties for CP systems and show that, under tS-WI, Campanelli et al.’s proposal indeed satisfies these properties. Additionally, we explore alternative approaches to implement ZK (other than SNARKs) and develop a prototype, using it to demonstrate their potential. Our new ideas result in a protocol to sell ECDSA signatures with contingent payment that can be executed in less than $150$ milliseconds over a LAN network.

  12. eThor: Practical and Provably Sound Static Analysis of Ethereum Smart Contracts 2020 Blockchains CCS SmartContracts
    Clara Schneidewind and Ilya Grishchenko and Markus Scherer and Matteo Maffei

    Ethereum has emerged as the most popular smart contract development platform, with hundreds of thousands of contracts stored on the blockchain and covering a variety of application scenarios, such as auctions, trading platforms, and so on. Given their financial nature, security vulnerabilities may lead to catastrophic consequences and, even worse, they can be hardly fixed as data stored on the blockchain, including the smart contract code itself, are immutable. An automated security analysis of these contracts is thus of utmost interest, but at the same time technically challenging for a variety of reasons, such as the specific transaction-oriented programming mechanisms, which feature a subtle semantics, and the fact that the blockchain data which the contract under analysis interacts with, including the code of callers and callees, are not statically known.
    In this work, we present eThor, the first sound and automated static analyzer for EVM bytecode, which is based on an abstraction of the EVM bytecode semantics based on Horn clauses. In particular, our static analysis supports reachability properties, which we show to be sufficient for capturing interesting security properties for smart contracts (e.g., single-entrancy) as well as contract-specific functional properties. Our analysis is proven sound against a complete semantics of EVM bytecode and an experimental large-scale evaluation on real-world contracts demonstrates that eThor is practical and outperforms the state-of-the-art static analyzers: specifically, eThor is the only one to provide soundness guarantees, terminates on 95% of a representative set of real-world contracts, and achieves an F-measure (which combines sensitivity and specificity) of 89%.

  13. BDoS: Blockchain Denial-of-Service 2020 Attacks Blockchains CCS
    Michael Mirkin and Yan Ji and Jonathan Pang and Ariah Klages-Mundt and Ittay Eyal and Ari Juels

    Proof-of-work (PoW) cryptocurrency blockchains like Bitcoin secure vast amounts of money. Their operators, called miners, expend resources to generate blocks and receive monetary rewards for their effort. Blockchains are, in principle, attractive targets for Denial-of-Service (DoS) attacks: There is fierce competition among coins, as well as potential gains from short selling. Classical DoS attacks, however, typically target a few servers and cannot scale to systems with many nodes. There have been no successful DoS attacks to date against prominent cryptocurrencies. We present Blockchain DoS (BDoS), the first incentive-based DoS attack that targets PoW cryptocurrencies. Unlike classical DoS, BDoS targets the system’s mechanism design: It exploits the reward mechanism to discourage miner participation. Previous DoS attacks against PoW blockchains require an adversary’s mining power to match that of all other miners. In contrast, BDoS can cause a blockchain to grind to a halt with significantly fewer resources, e.g., 21% as of March 2020 in Bitcoin, according to our empirical study. We find that Bitcoin’s vulnerability to BDoS increases rapidly as the mining industry matures and profitability drops. BDoS differs from known attacks like Selfish Mining in its aim not to increase an adversary’s revenue, but to disrupt the system. Although it bears some algorithmic similarity to those attacks, it introduces a new adversarial model, goals, algorithm, and game-theoretic analysis. Beyond its direct implications for operational blockchains, BDoS introduces the novel idea that an adversary can manipulate miners’ incentives by proving the existence of blocks without actually publishing them.

  14. ACE: Asynchronous and Concurrent Execution of Complex Smart Contracts 2020 Blockchains CCS SmartContracts
    Karl Wüst and Sinisa Matetic and Silvan Egli and Kari Kostiainen and Srdjan Capkun

    Smart contracts are programmable, decentralized and transparent financial applications. Because smart contract platforms typically support Turing-complete programming languages, such systems are often said to enable arbitrary applications. However, the current permissionless smart contract systems impose heavy restrictions on the types of computations that can be implemented. For example, the globally-replicated and sequential execution model of Ethereum requires low gas limits that make many computations infeasible.

    In this paper, we propose a novel system called ACE whose main goal is to enable more complex smart contracts on permissionless blockchains. ACE is based on an off-chain execution model where the contract issuers appoint a set of service providers to execute the contract code independent from the consensus layer. The primary advantage of ACE over previous solutions is that it allows one contract to safely call another contract that is executed by a different set of service providers. Thus, ACE is the first solution to enable off-chain execution of interactive smart contracts with flexible trust assumptions. Our evaluation shows that ACE enables several orders of magnitude more complex smart contracts than standard Ethereum.

  15. Zexe: Enabling Decentralized Private Computation 2020 Blockchains Oakland Privacy
    Sean Bowe and Alessandro Chiesa and Matthew Green and Ian Miers and Pratyush Mishra and Howard Wu

    Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application’s internal state.

    We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions hide all information about the offline computations. Second, transactions can be validated in constant time by anyone, regardless of the offline computation.

    The core of ZEXE is a construction for a new cryptographic primitive that we introduce, decentralized private computation (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes regardless of the offline computation, and generating them takes less than a minute plus a time that grows with the offline computation.

    We demonstrate how to use ZEXE to realize privacy-preserving analogues of popular applications: private decentralized exchanges for user-defined fungible assets and regulation-friendly private stablecoins.

  16. Towards Scalable Threshold Cryptosystems 2020 Blockchains Oakland
    Alin Tomescu, Robert Chen, Yiming Zheng, Ittai Abraham, Benny Pinkas, Guy Golan Gueta, and Srinivas Devadas

    The resurging interest in Byzantine fault tolerant systems will demand more scalable threshold cryptosystems. Unfortunately, current systems scale poorly, requiring time quadratic in the number of participants. In this paper, we present techniques that help scale threshold signature schemes (TSS), verifiable secret sharing (VSS) and distributed key generation (DKG) protocols to hundreds of thousands of participants and beyond. First, we use efficient algorithms for evaluating polynomials at multiple points to speed up computing Lagrange coefficients when aggregating threshold signatures. As a result, we can aggregate a 130,000 out of 260,000 BLS threshold signature in just 6 seconds (down from 30 minutes). Second, we show how “authenticating” such multipoint evaluations can speed up proving polynomial evaluations, a key step in communication-efficient VSS and DKG protocols. As a result, we reduce the asymptotic (and concrete) computational complexity of VSS and DKG protocols from quadratic time to quasilinear time, at a small increase in communication complexity. For example, using our DKG protocol, we can securely generate a key for the BLS scheme above in 2.3 hours (down from 8 days). Our techniques improve performance for thresholds as small as 255 and generalize to any Lagrange-based threshold scheme, not just threshold signatures. Our work has certain limitations: we require a trusted setup, we focus on synchronous VSS and DKG protocols and we do not address the worst-case complaint overhead in DKGs. Nonetheless, we hope it will spark new interest in designing large-scale distributed systems.

  17. HydRand: Practical Continuous Distributed Randomness 2020 Blockchains Oakland RandomnessGeneration
    Philipp Schindler and Aljosha Judmayer and Nicholas Stifter and Edgar Weippl

    A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention. In particular random beacon protocols, aimed at continuous operation, can be a vital component for current Proof-of-Stake based distributed ledger proposals. We improve upon previous random beacon approaches with HydRand, a novel distributed protocol based on publicly-verifiable secret sharing (PVSS) to ensure unpredictability, bias-resistance, and public-verifiability of a continuous sequence of random beacon values. Furthermore, HydRand provides guaranteed output delivery of randomness at regular and predictable intervals in the presence of adversarial behavior and does not rely on a trusted dealer for the initial setup. Compared to existing PVSS based approaches that strive to achieve similar properties, our solution improves scalability by lowering the communication complexity from O(n3) to O(n2). Furthermore, we are the first to present a detailed comparison of recently described schemes and protocols that can be used for implementing random beacons.

  18. Flyclient: Super-Light Clients for Cryptocurrencies 2020 Blockchains Cryptocurrency Oakland
    Benedikt Bünz and Lucianna Kiffer and Loi Luu and Mahdi Zamani

    To validate transactions, cryptocurrencies such as Bitcoin and Ethereum require nodes to verify that a blockchain is valid. This entails downloading and verifying all blocks, taking hours and requiring gigabytes of bandwidth and storage. Hence, clients with limited resources cannot verify transactions independently without trusting full nodes. Bitcoin and Ethereum offer light clients known as simplified payment verification (SPV) clients, that can verify the chain by downloading only the block headers. Unfortunately, the storage and bandwidth requirements of SPV clients still increase linearly with the chain length. For example, as of July 2019, an SPV client in Ethereum needs to download and store about 4 GB of data. Recently, Kiayias et al. proposed a solution known as non-interactive proofs of proof-of-work (NIPoPoW) that allows a light client to download and store only a polylogarithmic number of block headers in expectation. Unfortunately, NIPoPoWs are succinct only as long as no adversary influences the honest chain, and can only be used in chains with fixed block difficulty, contrary to most cryptocurrencies which adjust block difficulty frequently according to the network hashrate.

    We introduce Flyclient, a novel transaction verification light client for chains of variable difficulty. Flyclient is efficient both asymptotically and practically and requires downloading only a logarithmic number of block headers while storing only a single block header between executions. Using an optimal probabilistic block sampling protocol and Merkle Mountain Range (MMR) commitments, Flyclient overcomes the limitations of NIPoPoWs and generates shorter proofs over all measured parameters. In Ethereum, Flyclient achieves a synchronization proof size of less than 500 KB which is roughly 6,600x smaller than SPV proofs. We finally discuss how Flyclient can be deployed with minimal changes to the existing cryptocurrencies via an uncontentious velvet fork.

  19. Order-Fairness for Byzantine Consensus 2020 Blockchains Consensus Crypto
    Mahimna Kelkar and Fan Zhang and Steven Goldfeder and Ari Juels

    Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in leader-based protocols (almost all protocols used today), malicious leaders can directly choose the final transaction ordering.

    To rectify this problem, we propose a third consensus property: transaction order-fairness. We initiate the first formal investigation of order-fairness and explain its fundamental importance. We provide several natural definitions for order-fairness and analyze the assumptions necessary to realize them.

    We also propose a new class of consensus protocols called Aequitas. Aequitas protocols are the first to achieve order-fairness in addition to consistency and liveness. They can be realized in a black-box way using existing broadcast and agreement primitives (or indeed using any consensus protocol), and work in both synchronous and asynchronous network models.

  20. Pixel: Multi-signatures for Consensus 2020 Blockchains Cryptocurrency ProofOfStake Signatures Usenix
    Manu Drijvers, Sergey Gorbunov, Gregory Neven, and Hoeteck Wee

    In Proof-of-Stake (PoS) and permissioned blockchains, a committee of verifiers agrees and sign every new block of transactions. These blocks are validated, propagated, and stored by all users in the network. However, posterior corruptions pose a common threat to these designs, because the adversary can corrupt committee verifiers after they certified a block and use their signing keys to certify a different block. Designing efficient and secure digital signatures for use in PoS blockchains can substantially reduce bandwidth, storage and computing requirements from nodes, thereby enabling more efficient applications.

    We present Pixel, a pairing-based forward-secure multi-signature scheme optimized for use in blockchains, that achieves substantial savings in bandwidth, storage requirements, and verification effort. Pixel signatures consist of two group elements, regardless of the number of signers, can be verified using three pairings and one exponentiation, and support non-interactive aggregation of individual signatures into a multi-signature. Pixel signatures are also forward-secure and let signers evolve their keys over time, such that new keys cannot be used to sign on old blocks, protecting against posterior corruptions attacks on blockchains. We show how to integrate Pixel into any PoS blockchain. Next, we evaluate Pixel in a real-world PoS blockchain implementation, showing that it yields notable savings in storage, bandwidth, and block verification time. In particular, Pixel signatures reduce the size of blocks with 1500 transactions by 35% and reduce block verification time by 38%.

  21. The Honey Badger of BFT Protocols 2016 BFT Blockchains CCS
    Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, Dawn Song

    The surprising success of cryptocurrencies has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) proto- cols for mission-critical applications, such as finan- cial 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 ex- pected. 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 as- sumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and ex- perimental 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 experi- ments over Tor, without needing to tune any parame- ters. Unlike the alternatives, HoneyBadgerBFT sim- ply does not care about the underlying network.

  22. A Secure Sharding Protocol For Open Blockchains 2016 Blockchains CCS Cryptocurrency
    Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, Prateek Saxena

    Cryptocurrencies, such as Bitcoin and 250 similar alt-coins, embody at their core a blockchain protocol — a mechanism for a distributed network of computational nodes to periodically agree on a set of new transactions. Designing a secure blockchain protocol relies on an open challenge in security, that of designing a highly-scalableagreement protocol open to manipulation by byzantine or arbitrarily malicious nodes. Bitcoin’s blockchain agreement protocol exhibits security, but does not scale: it processes 3–7 transactions per second at present, irrespective of the available computation capacity at hand.

    In this paper, we propose a new distributed agreement protocol for permission-less blockchains called ELASTICO. ELASTICO scales transaction rates almost linearly with available computation for mining: the more the computation power in the network, the higher the number of transaction blocks selected per unit time. ELASTICO is efficient in its network messages and tolerates byzantine adversaries of up to one-fourth of the total computational power. Technically, ELASTICO uniformly partitions or parallelizes the mining network (securely) into smaller committees, each of which processes a disjoint set of transactions (or “shards”). While sharding is common in non-byzantine settings, ELASTICO is the first candidate for a secure sharding protocol with presence of byzantine adversaries. Our scalability experiments on Amazon EC2 with up to $1, 600$ nodes confirm ELASTICO’s theoretical scaling properties.

  23. On the Security and Performance of Proof of Work Blockchains 2016 Blockchains CCS ProofOfWork
    Arthur Gervais, Ghassan O. Karame, Karl Wüst, Vasileios Glykantzis, Hubert Ritzdorf, Srdjan Capkun

    Proof of Work (PoW) powered blockchains currently account for more than 90% of the total market capitalization of existing digital currencies. Although the security provisions of Bitcoin have been thoroughly analysed, the security guarantees of variant (forked) PoW blockchains (which were instantiated with different parameters) have not received much attention in the literature.

    In this paper, we introduce a novel quantitative framework to analyse the security and performance implications of various consensus and network parameters of PoW blockchains. Based on our framework, we devise optimal adversarial strategies for double-spending and selfish mining while taking into account real world constraints such as network propagation, different block sizes, block generation intervals, information propagation mechanism, and the impact of eclipse attacks. Our framework therefore allows us to capture existing PoW-based deployments as well as PoW blockchain variants that are instantiated with different parameters, and to objectively compare the tradeoffs between their performance and security provisions.

  24. Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability 2018 Blockchains CCS
    Christian Badertscher, Peter Gazi, Aggelos Kiayias, Alexander Russell, and Vassilis Zikas

    Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

  25. Improving Authenticated Dynamic Dictionaries, with Applications to Cryptocurrencies 2017 Blockchains FinancialCryptography
    Leonid Reyzin, Dmitry Meshkov, Alexander Chepurnoy, Sasha Ivanov

    We improve the design and implementation of two-party and three-party authenticated dynamic dictionaries and apply these dictionaries to cryptocurrency ledgers.

    A public ledger (blockchain) in a cryptocurrency needs to be easily verifiable. However, maintaining a data structure of all account balances, in order to verify whether a transaction is valid, can be quite burdensome: a verifier who does not have the large amount of RAM required for the data structure will perform slowly because of the need to continually access secondary storage. We demonstrate experimentally that authenticated dynamic dictionaries can considerably reduce verifier load. On the other hand, per-transaction proofs generated by authenticated dictionaries increase the size of the blockchain, which motivates us to find a solution with most compact proofs.

    Our improvements to the design of authenticated dictionaries reduce proof size and speed up verification by 1.4-2.5 times, making them better suited for the cryptocurrency application. We further show that proofs for multiple transactions in a single block can compressed together, reducing their total length by approximately an additional factor of 2.

    We simulate blockchain verification, and show that our verifier can be about 20 times faster than a disk-bound verifier under a realistic transaction load.