Research Pulse Issue #27 08/23/21

  1. Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments
    Authors: Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon

Polynomial commitment schemes (PCS) have recently been in the spotlight for their key role in building SNARKs. A 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. Any efficient and succinct PCS can be used to construct a SNARK with similar security and efficiency characteristics (in the random oracle model).
Proof-carrying data (PCD) enables a set of parties to carry out an indefinitely long distributed computation where every step along the way is accompanied by a proof of correctness. It generalizes incrementally verifiable computation and can even be used to construct SNARKs. Until recently, however, the only known method for constructing PCD required expensive SNARK recursion. A system called Halo first demonstrated a new methodology for building PCD without SNARKs, exploiting an aggregation property of the Bulletproofs inner-product argument. The construction was heuristic because it makes non-black-box use of a concrete instantiation of the Fiat-Shamir transform. We expand upon this methodology to show that PCD can be (heuristically) built from any homomorphic polynomial commitment scheme (PCS), even if the PCS evaluation proofs are neither succinct nor efficient. In fact, the Halo methodology extends to any PCS that has an even more general property, namely the ability to aggregate linear combinations of commitments into a new succinct commitment that can later be opened to this linear combination. Our results thus imply new constructions of SNARKs and PCD that were not previously described in the literature and serve as a blueprint for future constructions as well.


  1. On Liquidity Mining for Uniswap v3
    Authors: Jimmy Yin and Mac Ren

The recently proposed Uniswap v3 replaces the fungible liquidity provider token (LP token) into non-fungible ones, making the design for liquidity mining more difficult. In this paper, we propose a flexible liquidity mining scheme that realizes the overall liquidity distribution through the fine control of local rewards. From the liquidity provider’s point of view, the liquidity provision strategy forms a multiplayer zero-sum game. We analyze the Nash Equilibrium and the corresponding strategy, approximately, deploying the liquidity proportional to the reward distribution, in some special cases and use it to guide the general situations. Based on the strategic response above, such a scheme allows the mining rewards provider to optimize the distribution of liquidity for the purpose such as low slippage and price stabilization.


  1. Dynamic threshold ECDSA signature and application to asset custody in blockchain
    Authors: Huili Wang, Wenping Ma, Fuyang Deng, Haibin Zheng, and Qianhong Wu

The centralized exchange is one of the hottest DeFi applications based on blockchain transaction systems. However, depositing user assets to the exchanges brings the security risks of assets misappropriation. Threshold cryptosystem can effectively solve the drawbacks of centralized hosting by assigning the assets authorization to multiple trustees, but the collusion attack generated by malicious trustees is still unavoidable. In this paper, we propose a new dynamic threshold ECDSA signature scheme which is compatible with current blockchain transaction system. It realizes distributed custody of assets in exchanges, and further achieves a dynamic mechanism allowing user join and drop out to resist collusion attacks. Specifically, we formalize the definition of this system architecture and give its construction based on basic cryptography modules such as ECDSA signature, distributed key generation, and distributed computation. Analysis and experiment results show that our scheme holds protocol security and is more efficient than other threshold ECDSA signature schemes when threshold is less than 200, which makes it applicable to the assets custody scenarios of exchanges.

Link: Dynamic threshold ECDSA signature and application to asset custody in blockchain - ScienceDirect

  1. Ethereum Data Structures
    Author: Kamil Jezek

Ethereum platform operates with rich spectrum of data structures and hashing and coding functions. The main source describing them is the Yellow paper, complemented by a lot of informal blogs. These sources are somehow limited. In particular, the Yellow paper does not ideally balance brevity and detail, in some parts it is very detail, while too shallow elsewhere. The blogs on the other hand are often too vague and in certain cases contain incorrect information. As a solution, we provide this document, which summarises data structures used in Ethereum. The goal is to provide sufficient detail while keeping brevity. Sufficiently detailed formal view is enriched with examples to extend on clarity.


  1. DualRing: Generic Construction of Ring Signatures with Efficient Instantiations
    Authors: Tsz Hon Yuen, Muhammed F. Esgin, Joseph K. Liu, Man Ho Au, and Zhimin Ding

We introduce a novel generic ring signature construction, called DualRing, which can be built from several canonical identification schemes (such as Schnorr identification). DualRing differs from the classical ring signatures by its formation of two rings: a ring of commitments and a ring of challenges. It has a structural difference from the common ring signature approaches based on accumulators or zero-knowledge proofs of the signer index. Comparatively, DualRing has a number of unique advantages.
Considering the DL-based setting by using Schnorr identification scheme, our DualRing structure allows the signature size to be compressed into logarithmic size via an argument of knowledge system such as Bulletproofs. We further improve on the Bulletproofs argument system to eliminate about half of the computation while maintaining the same proof size. We call this Sum Argument and it can be of independent interest. This DL-based construction, named DualRing-EC, using Schnorr identification with Sum Argument has the shortest ring signature size in the literature without using trusted setup.
Considering the lattice-based setting, we instantiate DualRing by a canonical identification based on M-LWE and M-SIS. In practice, we achieve the shortest lattice-based ring signature, named DualRing-LB, when the ring size is between 4 and 2000. DualRing-LB is also 5 × faster in signing and verification than the fastest lattice-based scheme by Esgin et al. (CRYPTO’19).

Link: DualRing: Generic Construction of Ring Signatures with Efficient Instantiations | SpringerLink

  1. CRSA: A Cryptocurrency Recovery Scheme Based on Hidden Assistance Relationships
    Authors: Weiqi Dai, Yan Lv, Kim-Kwang Raymond Choo, Zhongze Liu, Deqin Zou, and Hai Jin

As cryptocurrency and blockchain-related assets become more common in our digital society, there is a corresponding need to secure our digital assets, including the private keys used to secure access to such assets (e.g., due to loss or corruption of the data storage medium). However, there are limitations in existing blockchain-related asset management and recovery methods. Therefore, we use zero-knowledge proof to design a cryptocurrency recovery scheme based on hidden assisting relationships (hereafter referred to as the CRSA scheme) to facilitate the recovery of blockchain assets. Specifically, when the user’s private key is lost, and access to the assets cannot be obtained, the user leverages information such as the pre-defined list of assistants to authenticate himself/herself on the blockchain. Once the assistants have confirmed the legitimacy of the user’s authentication request, the asset will be transferred from the old address to the new address. During the (identity) proof process, the zero-knowledge proof is used to ensure that the identification of assistants is not leaked to other nodes, assistants, and the adversary. We provide the formal definition of the above scheme and the security proof of the construction. We also implement a prototype of the system and evaluate its performance. Evaluations indicate that the time required for the zero-knowledge proof is less than 10s, and the block verification time is less than 100ms.

Link: CRSA: A Cryptocurrency Recovery Scheme Based on Hidden Assistance Relationships | IEEE Journals & Magazine | IEEE Xplore

  1. I Told You Tomorrow: Practical Time-Locked Secrets using Smart Contracts
    Authors: Enrico Bacis, Dario Facchinetti, Marco Guarnieri, Marco Rosa, Matthew Rossi, and Stefano Paraboschi

A Time-Lock enables the release of a secret at a future point in time. Many approaches implement Time-Locks as cryptographic puzzles, binding the recovery of the secret to the solution of the puzzle. Since the time required to find the puzzle’s solution may vary due to a multitude of factors, including the computational effort spent, these solutions may not suit all scenarios.
To overcome this limitation, we propose I Told You Tomorrow (ITYT), a novel way of implementing time-locked secrets based on smart contracts. ITYT relies on the blockchain to measure the elapse of time, and it combines threshold cryptography with economic incentives and penalties to replace cryptographic puzzles.
We implement a prototype of ITYT on top of the Ethereum blockchain. The prototype leverages secure Multi-Party Computation to avoid any single point of trust. We also analyze resiliency to attacks with the help of economic game theory, in the context of rational adversaries. The experiments demonstrate the low cost and limited resource consumption associated with our approach.



Research Pulse #28 is out!

Zero-Knowledge systems are one of the modern frontiers of cryptography. It has been fascinating to see this area being predominantly pushed further by researchers working on cryptoasset systems. A good example of this is Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments. In this fascinating paper, a novel SNARK scheme called SHPLONK is hypothesized. SHPLONK borrows elements from Halo and PLONK and could considerably improve the performance, applicability, and functionality of SNARKs.

Cryptoasset custody is going through massive changes given the proliferation of Multi-Party Computation (MPC) schemes, which implement multisigs outside of the consensus layer. In Dynamic threshold ECDSA signature and application to asset custody in blockchain, the authors provide a new scheme for MPC-powered threshold signatures, whereby a threshold of individual signers must produce a valid signature before a transaction is completed. This scheme may provide improvements over other approaches when a signature threshold is lower than 200 participants.

Finally, in Ethereum Data Structures, the author provides one of the most concise explanations of the data structures employed by Ethereum today. Unlike the Yellow Paper, this work goes deep into design structures and motivations behind the various Merkle Trees used in Ethereum to track state. The author also provides a set of interesting examples on these structures, which help readers better contextualize how a tree is being used.

1 Like