Research Pulse

This thread is intended to capture exciting ongoing research. Please feel free to share new papers as you find them.

Halo Infinite: Recursive zk-SNARKs from any Additive Polynomial Commitment Scheme
by Dan Boneh, Justin Drake, Ben Fisch, Ariel Gabizon.

Abstract: A polynomial commitment scheme (PCS) provides the ability to commit to a polynomial
over a finite field and prove its evaluation at points. A succinct PCS has commitment and
evaluation proof size sublinear in the degree of the polynomial. An efficient PCS has sublinear
proof verification. Recently, it has been shown that any efficient and succinct PCS can be used
to construct a SNARK with similar security and efficiency characteristics. We define an additive
PCS to capture a “homomorphic” property of commitments over a computational group G of
bounded size. All existing examples of additive schemes (e.g., Bulletproofs, KZG, DARK, Dory)
are also what we call m-spanning, meaning that commitments to the monomials of degree less
than m generate G. Our first technical result is a black-box transformation of any m-spanning
additive PCS into a hiding PCS with a zero-knowledge evaluation proof. Our second technical
result is that every additive succinct PCS supports efficient proof aggregation.
PCS proof aggregation reduces the task of proving evaluations of multiple commitments
at multiple independent points to the task of proving the evaluation of a single “aggregate”
commitment at a single point. We present two flavors of aggregation: private and public.
In private aggregation the prover has a private witness consisting of openings of the input
commitments. In public aggregation, the prover/verifier share the same inputs, which includes
non-interactive evaluation proofs for each input commitment. Our public aggregation protocol
applies to any additive succinct PCS. Our private aggregation protocol applies more broadly to
any succinct PCS that supports an efficient linear combination scheme: a protocol for verifiably
aggregating commitments into a new commitment to their linear combination. This includes
non-additive schemes such as the post-quantum FRI-based PCS.
We apply these results to the Halo proof carrying data (PCD) system. Halo was originally
built using the Bulletproofs inner-product argument as the underlying PCS, and was recently
generalized to work with the KZG PCS. We show that Halo can be instantiated with any PCS
that supports efficient PCS aggregation, private or public. Thus, our results show that efficient
(zero-knowledge) SNARKs and PCD can be constructed from any succinct PCS that has an
efficient linear combination scheme, even if the PCS itself is inefficient. These results yield
new Halo-like PCD systems from PCS constructions beyond Bulletproofs and KZG, including
DARK, FRI, and Dory. The post-quantum Halo instantiation from FRI is particularly surprising
as FRI is not additive.

Link: https://eprint.iacr.org/2020/1536.pdf

2 Likes

VM Matters: A Comparison of WASM VMs and EVMs in the Performance of Blockchain Smart Contracts
by Shuyu Zheng, Haoyu Wang, Lei Wu, Gang Huang, Xuanzhe Liu.

WebAssemly is an emerging runtime for Web applications and has been supported in almost all browsers. Recently, WebAssembly is further regarded to be a the next-generation environment for
blockchain applications, and has been adopted by Ethereum, namely eWASM, to replace the state-of-the-art EVM. However, whether and how well current eWASM outperforms EVM on blockchain clients is still unknown. This paper conducts the first measurement study, to measure the performance on WASM VM and EVM for executing smart contracts on blockchain. To our surprise, the current WASM VM does not perform in expected performance. The overhead introduced by WASM is really non-trivial. Our results highlight the challenges when deploying WASM in practice, and provide insightful implications for improvement space.

Link: https://arxiv.org/pdf/2012.01032.pdf

3 Likes

A First Look into DeFi Oracles
Authors: Bowen Liu, Pawel Szalachowski, and Jianying Zhou.

Recently emerging Decentralized Finance (DeFi) takes the promise of cryptocurrencies a step further, leveraging their decentralized networks to transform traditional financial products into trustless and transparent protocols that run without intermediaries. However, these protocols often re- quire critical external information, like currency or commod- ity exchange rates, and in this respect they rely on special oracle nodes. In this paper, we present a comprehensive mea- surement study of DeFi price oracles deployed in practice. First, we investigate designs of mainstream DeFi platforms that rely on data from oracles. We find that these designs, surprisingly, position oracles as trusted parties with no or low accountability. Then, we present results of large-scale measurements of deployed oracles. We find and report that prices reported by oracles regularly deviate from current exchange rates, oracles are not free from operational issues, and their reports include anomalies. Finally, we compare the oracle designs and propose potential improvements.

Link: https://arxiv.org/pdf/2005.04377.pdf

3 Likes

Pricing Security in Proof-of-Work Systems
Authors: Rainer Bohme, David Thibodeau, Brian N. Levine

A key component of security in decentralized blockchains is proof of opportunity cost among block producers. In the case of proof-of-work (PoW), currently used by the most prominent systems, the cost is due to spent computation. In this paper, we characterize the security investment of miners in terms of its cost in fiat money. This enables comparison of security allocations across PoW blockchains that generally use different PoW algorithms and reward miners in different cryptocurrency units. We prove that there exists a unique allocation equilibrium, depending on market prices only, that is achieved by both strategic miners (who contemplate the actions of others) and by miners seeking only short-term profit. In fact, the latter will unknowingly compensate for any attempt to deliberately shift security allocation away from equilibrium. Our conclusions are supported analytically through the development of a Markov decision process, game theoretical analysis, and derivation of no arbitrage conditions. We corroborate those results with empirical evidence from more than two years of blockchain and price data. Overall agreement is strong. We show that between January 1, 2018 and August 1, 2020, market prices predicted security allocation between Bitcoin and Bitcoin Cash with error less than 0.6%. And from the beginning of October 2019, until August 1, 2020, market prices predicted security allocation between Bitcoin and Litecoin with error of 0.45%. These results are further corroborated by our establishment of Granger-causality between change in market prices and change in security allocation. To demonstrate the practicality of our results, we describe a trustless oracle that leverages the equilibrium to estimate the price ratios of PoW cryptocurrencies from on-chain information only.

Link: https://arxiv.org/pdf/2012.03706.pdf

3 Likes

Design-Pattern-as-a-Service for Blockchain-based Self-Sovereign Identity
Authors: Yue Liu, Qinghua Lu†‡, Hye-Young Paik‡, Xiwei Xu†‡, Shiping Chen†, Liming Zhu

Abstract—Self-sovereign identity (SSI) is considered to be a “killer application” of blockchain. However, there is a lack of systematic architecture designs for blockchain-based SSI systems to support methodical development. An aspect of such gap is demonstrated in current solutions, which are considered coarse grained and may increase data security risks. In this paper, we first identify the lifecycles of three major SSI objects (i.e., key, identifier, and credential) and present fine-grained design patterns critical for application development. These patterns are associated with particular state transitions, providing a systematic view of system interactions and serving as a guidance for effective use of these patterns. Further, we present an SSI platform architecture, which advocates the notion of Design-Pattern-as-a-Service. Each design pattern serves as an API by wrapping the respective pattern code to ease application development and improve scalability and security. We implement a prototype and evaluate it on feasibility and scalability.
Link: Design-Pattern-as-a-Service-for-Blockchain-based-Self-Sovereign-Identity.pdf (researchgate.net)

1 Like

Lockable Signatures for Blockchains: Scriptless Scripts for All Signatures
Authors: Sri Aravinda Krishnan Thyagaraja, Giulio Malavolta

Abstract: 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.

Link: https://eprint.iacr.org/2020/1613.pdf

2 Likes

BDoS: Blockchain Denial-of-Service
Authors: Michael Mirkin, Yan Ji, Jonathan Pang, Ariah Klages-Mundt, Ittay Eyal, 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 gametheoretic 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.

Link: https://arxiv.org/ftp/arxiv/papers/1912/1912.07497.pdf

1 Like

Proof-Carrying Data without Succinct Arguments
Authors: Benedikt Bunz, Alessandro Chiesa, William Lin, Pratyush Mishra, Nicholas Spooner

Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme for their proofs. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size proofs) that has a split accumulation scheme, which is a weak form of accumulation that we introduce. We additionally construct a transparent non-interactive argument of knowledge for R1CS whose accumulation is verifiable via a constant number of group and field operations. This leads, via the random oracle heuristic and our result above, to efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.

Link: https://eprint.iacr.org/2020/1618.pdf

1 Like

Practical Mutation Testing for Smart Contracts
Authors: Joran J. Honig, Maarten H. Everts, and Marieke Huisman

Solidity smart contracts operate in a hostile environment, which introduces the need for the adequate application of testing techniques to ensure mitigation of the risk of a security incident. Mutation testing is one such technique. It allows for the evaluation of the efficiency of a test suite in detecting faults in a program, allowing developers to both assess and improve the quality of their test suites. In this paper, we propose a mutation testing framework and implement a prototype implementation called Vertigo that targets Solidity contracts for the Ethereum blockchain. We also show that mutation testing can be used to assess the test suites of real-world projects.

Link: Practical Mutation Testing for Smart Contracts | SpringerLink

1 Like

Highway: Efficient Consensus with Flexible Finality
Authors: Daniel Kane, Andreas Fackler, Adam Gągol, Damian Straszak, Vlad Zamfir

There has been recently a lot of progress in designing efficient partially synchronous BFT consensus protocols that are meant to serve as core consensus engines for Proof of Stake blockchain systems. While the state-of-the-art solutions attain virtually optimal performance under this theoretical model, there is still room for improvement, as several practical aspects of such systems are not captured by this model. Most notably, during regular execution, due to financial incentives in such systems, one expects an overwhelming fraction of nodes to honestly follow the protocol rules and only few of them to be faulty, most likely due to temporary network issues. Intuitively, the fact that almost all nodes behave honestly should result in stronger confidence in blocks finalized in such periods, however it is not the case under the classical model, where finality is binary.
We propose Highway, a new consensus protocol that is safe and live in the classical partially synchronous BFT model, while at the same time offering practical improvements over existing solutions. Specifically, block finality in Highway is not binary but is expressed by fraction of nodes that would need to break the protocol rules in order for a block to be reverted. During periods of honest participation finality of blocks might reach well beyond 1∕3 (as what would be the maximum for classical protocols), up to even 1 (complete certainty). Having finality defined this way, Highway offers flexibility with respect to the configuration of security thresholds among nodes running the protocol, allowing nodes with lower thresholds to reach finality faster than the ones requiring higher levels of confidence

Link: https://arxiv.org/pdf/2101.02159.pdf

1 Like

Battlement: A Quorum Based Design for Lightning Network Key Management
Authors: Omer Shlomovits

The lightning network is a payment channel network on top of bitcoin. It defines a set of protocols and specifications for securely establishing channels between lightning nodes and transmit payments between them without touching the Bitcoin blockchain. From a cryptographic stand point, a channel can be seen as a collection of two-party protocols, drawing their security from the orchestration of private keys. In this work we therefore treat channels as a key management problem. We model the adversary as an outsider attacker that gains either full or partial access to the different types of keys during the different stages of a channel life cycle. In the context of the lightning network, a watchtower is a semi trusted, always online third party. The watchtower gets a limited permission from a party to act on its behalf in the scenario where the counter party is trying to cheat while the party is offline. We build our key management solution based on the watchtower concept: we require a quorum of watchtowers, called a Battlement, to which a user delegates key management responsibilities. Under a threshold assumption, we show how our design eliminates the existing attack surface for attackers. We additionally show how a Battlement can mitigate a bribing attack existing in current lightning network design.

Link: https://static1.squarespace.com/static/5f3a45dc0638305e031b7419/t/5fd877e477d7f03dcdb5b3f9/1608022219533/Battlement.pdf

1 Like

Quantifying Blockchain Extractable Value: How dark is the forest?
Authors: Kaihua Qin, Liyi Zhou, Arthur Gervais

Permissionless blockchains such as Bitcoin have excelled at financial services. Yet, adversaries extract monetary value from the mesh of decentralized finance (DeFi) smart contracts. Some have characterized the Ethereum peer-to-peer network as a dark forest, wherein broadcast transactions represent prey, which are devoured by generalized trading bots. While transaction (re)ordering and front-running are known to cause losses to users, we quantify how much value was sourced from blockchain extractable value (BEV). We systematize a transaction ordering taxonomy to quantify the USD extracted from sandwich attacks, liquidations, and decentralized exchange arbitrage. We estimate that over 2 years, those trading activities yielded 28.80M USD in profit, divided among 5, 084 unique addresses. While arbitrage and liquidations might appear benign, traders can front-run others, causing financial losses to competitors. To provide an example of a generalized trading bot, we show a simple yet effective automated transaction replay algorithm capable of replacing unconfirmed transactions without understanding the victim transactions’ underlying logic. We estimate that our transaction replay algorithm could have yielded a profit of 51, 688.33 ETH (17.60M USD) over 2 years on past blockchain data. We also find that miners do not broadcast 1.64% of their mined transactions and instead choose to mine them privately. Privately mined transactions cannot be front-run by other traders or miners. We show that the largest Ethereum mining pool performs arbitrage and seemingly tries to cloak its private transaction mining activities. We therefore provide evidence that miners already extract Miner Extractable Value (MEV), which could destabilize the blockchain consensus security, as related work has shown.

Link: https://arxiv.org/pdf/2101.05511.pdf

1 Like

Not quite a paper:

General-purpose AMMs and Options: Why general-purpose AMMs aren’t suited for options trading

Author: Aerhy Myoung of Pods.finance

TL;DR

  • Options pricing depends on various factors (time to maturity and implied volatility, to name a few) and, in most cases, they tend to zero .
  • The price discovery mechanism of general-purpose AMMs (like Uniswap) normally relies on the volume of trades, assuming that in a liquid market the assets should be priced correctly by market forces. However, DeFi options markets are still nascent by the time of this post and options may not be updated as often, leaving the price outdated. Potentially generating a substantial impermanent loss for the liquidity providers of the option pool.
  • This post explores the math behind Uniswap v1 and concludes that using it as a venue of exchange for options tokens may not be the most adequate.

Link: General-purpose AMMs and Options. Why general-purpose AMMs aren’t the… | by Aerhy | Pods | Jan, 2021 | Medium

3 Likes

The Eye of Horus: Spotting and Analyzing Attacks on Ethereum Smart Contracts
Authors: Christof Ferreira Torres, Antonio Iannillo, Arthur Gervais, and Radu State

In recent years, Ethereum gained tremendously in popularity, growing from a daily transaction average of 10K in January 2016 to an average of 500K in January 2020. Similarly, smart contracts began to carry more value, making them appealing targets for attackers. As a result, they started to become victims of attacks, costing millions of dollars. In response to these attacks, both academia and industry proposed a plethora of tools to scan smart contracts for vulnerabilities before deploying them on the blockchain. However, most of these tools solely focus on detecting vulnerabilities and not attacks, let alone quantifying or tracing the number of stolen assets. In this paper, we present Horus, a framework that empowers the automated detection and investigation of smart contract attacks based on logic-driven and graph-driven analysis of transactions. Horus provides quick means to quantify and trace the flow of stolen assets across the Ethereum blockchain. We perform a large-scale analysis of all the smart contracts deployed on Ethereum until May 2020. We identified 1,888 attacked smart contracts and 8,095 adversarial transactions in the wild. Our investigation shows that the number of attacks did not necessarily decrease over the past few years, but for some vulnerabilities remained constant. Finally, we also demonstrate the practicality of our framework via an in-depth analysis on the recent Uniswap and Lendfme attacks.

Link: https://arxiv.org/pdf/2101.06204.pdf

3 Likes

Post-Quantum Security of the Bitcoin Backbone and Quantum Multi-Solution Bernoulli Search
Authors: Alexandru Cojocaru, Juan Garay, Aggelos Kiayias, Fang Song, Petros Wallden

Bitcoin and its underlying blockchain protocol have recently received significant attention in the context of building distributed systems as well as from the perspective of the foundations of the consensus problem. At the same time, the rapid development of quantum technologies brings the possibility of quantum computing devices from a theoretical conception to an emerging technology. Motivated by this, in this work, we revisit the formal security of the core of the Bitcoin protocol, called Bitcoin backbone, in the presence of quantum adversaries – i.e. adversaries equipped with quantum computers. We show that the security of the bitcoin holds as long as the quantum computational hashing power of the adversary in the Quantum Random Oracle model is appropriately bounded. We analyze the quantum query complexity of a Chain-of-Proofs-of-Work search problem, problem that is at the core of the blockchain protocol, which in turn is related to the complexity of a multi-solution Bernoulli search problem. The query complexity of the latter is performed using a modification of the Zhandry’s recording technique (Crypto ’19) and can be of independent interest. Our analysis indicates that the security of the Bitcoin backbone protocol is guaranteed provided that the number of adversarial quantum queries is bounded, such 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 in the case of quantum adversaries matches (up to a constant) the safe settlement time in the setting of classical adversaries and thus does not result in any further overhead.

Link:https://arxiv.org/pdf/2012.15254.pdf

1 Like

Markets for Crypto Tokens, and Security under Proof of Stake
Authors: Christian Catalini, Ravi Jagadeesan

Cryptocurrency systems based on proof of stake (PoS) grant governance rights to the holders of currency tokens and therefore are vulnerable to attack by adversaries who buy tokens in order to gain control. To evaluate the robustness of PoS cryptocurrencies to such attacks, we model the market for tokens and determine how the cost of attacking the system depends on the level and shape of token supply and demand. We show that, contrary to popular belief, the appreciation of tokens in response to demand by attackers plays a small role in securing the system. In particular, stablecoins can be less vulnerable to attack than cryptocurrencies that are freely oating. Moreover, PoS cryptocurrencies that primarily function as mediums of exchange are vulnerable to attack if the velocity of money is high.

Link: https://poseidon01.ssrn.com/delivery.php?ID=585094117064086105066066030024119006057009006016027026022113114010089065024101126087011017111035041046097082007030090126008002024090078032077008101083019125096087030081040022070065120107005113115013087064110081116086065011014126006028118081031113124&EXT=pdf&INDEX=TRUE

1 Like

Probabilistic Framework For Loss Distribution Of Smart Contract Risk
Authors: Petar Jevtic and Nicolas Lanchier

Smart contract risk can be defined as a financial risk of loss due to cyber attacks on or contagious failures of smart contracts. Its quantification is of paramount importance to technology platform providers as well as companies and individuals when considering the deployment of this new technology. That is why, as our primary contribution, we propose a structural framework of aggregate loss distribution for smart contract risk under the assumption of a tree-stars graph topology representing the network of interactions among smart contracts and their users. Up to our knowledge, there exist no theoretical frameworks or models of an aggregate loss distribution for smart contracts in this setting. To achieve our goal, we contextualize the problem in the probabilistic graph-theoretical framework using bond percolation models. We assume that the smart contract network topology is represented by a random tree graph of finite size, and that each smart contract is the center of a random star graph whose leaves represent the users of the smart contract. We allow for heterogeneous loss topology superimposed on this smart contract and user topology and provide analytical results and instructive numerical examples.

Link: https://arxiv.org/pdf/2101.08964.pdf

2 Likes

Interested in summarizing this one!

4 Likes

Low-cost attacks on Ethereum 2.0 by sub-1/3 stakeholders
Authors: Michael Neuder, Daniel J. Moroz, Rithvik Rao, and David C. Parkes

We outline two dishonest strategies that can be cheaply executed on the Ethereum 2.0 beacon
chain, even by validators holding less than one-third of the total stake: malicious chain reorganizations (“reorgs”) and finality delays. In a malicious reorg, an attacker withholds their blocks and
attestations before releasing them at an opportune time in order to force a chain reorganization,
which they can take advantage of by double-spending or front-running transactions. To execute
a finality delay an attacker uses delayed block releases and withholding of attestations to increase
the mean and variance of the time it takes blocks to become finalized. This impacts the efficiency
and predictability of the system. We provide a probabilistic and cost analysis for each of these
attacks, considering a validator with 30% of the total stake.

Link: https://arxiv.org/pdf/2102.02247.pdf

3 Likes