Research Pulse Issue #90 11/7/2022

  1. Leveraging the Verifier’s Dilemma to Double Spend in Bitcoin
    Authors: Tong Cao, Jérémie Decouchant, and Jiangshan Yu

We describe and analyze perishing mining, a novel block-withholding mining strategy that lures profit-driven miners away from doing useful work on the public chain by releasing block headers from a privately maintained chain. We then introduce the dual private chain (DPC) attack, where an adversary that aims at double spending increases its success rate by intermittently dedicating part of its hash power to perishing mining. We detail the DPC attack’s Markov decision process, evaluate its double spending success rate using Monte Carlo simulations. We show that the DPC attack lowers Bitcoin’s security bound in the presence of profit-driven miners that do not wait to validate the transactions of a block before mining on it.

Link to Paper

  • A primary design goal for any blockchain system is to make it prohibitively expensive to reorganize the blocks that users consider to be “final”, or irreversible. Otherwise, blockchains would be considerably more susceptible to fraud via attacks such as double spends.

  • In PoW systems, the susceptibility for a network to be captured has been measured in the context of “51% attacks” which are made possible by the centralization of mining resources.

  • This paper discusses a variant of Bitcoin double spend attack called perishing mining. Like traditional double-spend attacks, this strategy involves mining a private chain to confuse network nodes unaware of the attack.

  1. Simplified State Storage Rent for EVM Blockchains
    Authors: Sergio Demian Lerner, Federico Jinich, Diego Masini, and Shreemoy Mishra

Uncontrolled growth of blockchain state can adversely affect client performance, decentralization and security. Previous attempts to introduce duration-based state storage pricing or storage rent in Ethereum have stalled, partly because of complexity. We present a new approach with finer granularity to “spread” rent payments across peers. Our proposal shifts the burden of state rent from ‘owners’ or contracts to transaction senders in a ‘quasi-random’ manner. This proposal offers a simple path for initial adoption on Ethereum Virtual Machine (EVM) compatible chains, and serve as a foundation to address remaining challenges.

Link to Paper

  • Blockchain nodes are becoming increasingly expensive to run. The historical transactions, or state, of some blockchains exceed 20TB which prevents nodes to be run on commodity hardware, a problem often called state bloat.

  • This issue has decreased the number of nodes validating blockchain transactions, which is problematic for many reasons, especially network security.

  • This paper discusses a schema where the entities encoding information on the blockchain have to pay for state rent, which effectively socializes the impact that leveraging blockchains for storage has on network nodes.

  1. Accountable Safety for Rollups
    Authors: Ertem Nusret Tas, John Adler, Mustafa Al-Bassam, Ismail Khoffi, David Tse, and Nima Vaziri

Accountability, the ability to provably identify protocol violators, gained prominence as the main economic argument for the security of proof-of-stake (PoS) protocols. Rollups, the most popular scaling solution for blockchains, typically use PoS protocols as their parent chain. We define accountability for rollups, and present an attack that shows the absence of accountability on existing designs. We provide an accountable rollup design and prove its security, both for the traditional ‘enshrined’ rollups and for sovereign rollups, an emergent alternative built on lazy blockchains, tasked only with ordering and availability of the rollup data.

Link to Paper

  • Optimistic Rollup designs have become the most popular scalability strategies not only for Ethereum but also for the smart contract ecosystem as a whole.

  • At their core, optimistic designs trust a set of bonded operators that facilitate user transactions. If these intermediaries misbehave, users can provide fraud proofs and receive a reward. The system is optimistic in nature because it assumes intermediaries won’t misbehave since doing so will make them lose their stake.

  • This paper discusses an important tool that can make these designs even safer: an accountability gadget for rollups. In this paradigm, network participants have stronger assurances around a node’s accountability which is intrinsically linked to the rollup’s security.

  1. An efficient verifiable state for zk-EVM and beyond from the Anemoi hash function
    Authors: Jianwei Liu, Harshad Patil, Akhil Sai Peddireddy, Kevin Singh, Haifeng Sun, Huachuang Sun, and Weikeng Chen

In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions; i.e., EVM is a state machine.
In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses.
In this note, we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive mode of operation [Bou+22], by Clemence Bouvier, Pierre Briaud, Pyrros ´ Chaidos, Leo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems.
We demonstrate that with 14 gates (≈ 1 gate per round in a 12-round Amenoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations would often require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK. Our implementation can be found in noah, a library for modern privacy tokens.

Link to Paper

  • Zero Knowledge Proofs (ZKPs) have been used in privacy and scalability prototypes that have the potential to drastically improve the performance and usefulness of blockchains.

  • Given the industry’s convergence on the Ethereum Virtual Machine (EVM), the intersection of the EVM and ZKPs has been a vibrant area of research.

  • This paper discusses the verifiability of zero knowledge circuits within the EVM and proposes a new schema for a ZKP-compatible execution environment.