Research Pulse Issue #24 08/02/21

  1. Constant Function Market Makers: Multi-Asset Trades via Convex Optimization
    Authors: Guillermo Angeris, Akshay Agrawal, Alex Evans, Tarun Chitra, and Stephen Boyd

The rise of Ethereum and other blockchains that support smart contracts has led to the creation of decentralized exchanges (DEXs), such as Uniswap, Balancer, Curve, mStable, and SushiSwap, which enable agents to trade cryptocurrencies without trusting a centralized authority. While traditional exchanges use order books to match and execute trades, DEXs are typically organized as constant function market makers (CFMMs). CFMMs accept and reject proposed trades based on the evaluation of a function that depends on the proposed trade and the current reserves of the DEX. For trades that involve only two assets, CFMMs are easy to understand, via two functions that give the quantity of one asset that must be tendered to receive a given quantity of the other, and vice versa. When more than two assets are being exchanged, it is harder to understand the landscape of possible trades. We observe that various problems of choosing a multi-asset trade can be formulated as convex optimization problems, and can therefore be reliably and efficiently solved.


  1. Rectifying Administrated ERC20 Tokens
    Author: Nikolay Ivanov, Hanqing Guo, and Qiben Yan

ERC20 token is the most popular type of Ethereum smart contract. The daily transaction volume of these tokens exceeds 100 billion dollars, which agitates the popular notions of “decentralized banking” and “tokenized economy”. Yet, it is a common misconception to assume that the decentralization of blockchain entails the decentralization of smart contracts deployed on this blockchain. In practice, the developers of smart contracts implement administrating patterns, such as censoring certain users, creating or destroying balances on demand, destroying smart contracts, or injecting arbitrary code. These routines, which are designed to tightly control the operation of these smart contracts, turn an ERC20 token into an administrated token — the type of Ethereum smart contract that we scrutinize in this research.
We discover that many smart contracts are administrated, which means that their owners solely possess an omnipotent power over these contracts. Moreover, the owners of these tokens carry lesser social and legal responsibilities compared to the traditional centralized actors that those tokens intend to disrupt. This entails two major problems: a) the owners of the tokens have the ability to quickly steal all the funds and disappear from the market; and b) if the private key of the owner’s account is stolen, all the assets might immediately turn into the property of the attacker. Therefore, the administrated ERC20 tokens are not only dissimilar to the traditional centralized asset management tools, such as banks, but they are also more vulnerable to adversarial actions by their owners or attackers. We develop a pattern recognition framework based on 9 syntactic features characterizing administrated ERC20 tokens, which we use to analyze existing smart contracts deployed on Ethereum Mainnet. Our analysis of 84,062 unique Ethereum smart contracts reveals that nearly 58% of them are administrated ERC20 tokens, which accounts for almost 90% of all ERC20 tokens deployed on Ethereum.
To protect users from the frivolousness of unregulated token owners without depriving the ability of these owners to properly manage their tokens, we introduce SafelyAdministrated — a library that enforces a responsible ownership and management of ERC20 tokens. The library introduces three mechanisms: deferred maintenance, board of trustees and safe pause. We implement and test SafelyAdministrated in the form of Solidity abstract contract, which is ready to be used by the next generation of safely administrated ERC20 tokens.


  1. How to Construct Physical Zero-Knowledge Proofs for Puzzles with a “Single Loop” Condition
    Authors: Pascal Lafourcade, Daiki Miyahara, Takaaki Mizuki, LĂ©o Robert, Tatsuya Sasaki, and Hideaki Sone

We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.

Link: How to Construct Physical Zero-Knowledge Proofs for Puzzles with a “Single Loop” Condition - ScienceDirect

  1. A survey on NIST PQ signatures
    Authors: Nicola Di Chiano, Riccardo Longo, Alessio Meneghetti, and Giordano Santilli

Shor’s shockingly fast quantum algorithm for solving the period-finding problem is a threat for the most common public-key primitives, as it can be efficiently applied to solve both the Integer Factorisation Problem and the Discrete Logarithm Problem. In other words, as soon as a large-enough quantum computer is born, many once-secure protocols have to be replaced by still-secure alternatives. Instead of relying, for example, on the RSA protocol, the Diffie-Hellman key-exchange or the (Elliptic Curve) Digital Signature Algorithm, many researchers moved their attention to the design and analysis of primitives which are yet to be broken by quantum algorithms.
The urgency of the threat imposed by quantum computers led the U.S. National Institute of Standards and Technology (NIST) to open calls for both Post-Quantum Public-Keys Exchange Algorithms and Post-Quantum Digital Signature Algorithms [32]. This new NIST standardisation process started in 2016, has involved hundreds of researchers, has seen 37 early submissions for a total of 82 proposals, and has recently reached its third round of analyses.


  1. AToM: Active Topology Monitoring for the Bitcoin Peer-to-Peer Network
    Authors: Federico Franzoni, Xavier Salleras, and Vanesa Daza

Over the past decade, the Bitcoin P2P network protocol has become a reference model for all modern cryptocurrencies. While nodes in this network are known, the connections among them are kept hidden, as it is commonly believed that this helps protect from deanonymization and low-level attacks. However, adversaries can bypass this limitation by inferring connections through side channels. At the same time, the lack of topology information hinders the analysis of the network, which is essential to improve efficiency and security. In this paper, we thoroughly review network-level attacks and empirically show that topology obfuscation is not an effective countermeasure. We then argue that the benefits of an open topology potentially outweigh its risks, and propose a protocol to reliably infer and monitor connections among reachable nodes of the Bitcoin network. We formally analyze our protocol and experimentally evaluate its accuracy in both trusted and untrusted settings. Results show our system has a low impact on the network, and has precision and recall are over 90% with up to 20% of malicious nodes in the network.


  1. A Lattice-based Provably Secure Multisignature Scheme in Quantum Random Oracle Model⋆
    Authors: Masayuki Fukumitsu and Shingo Hasegawa

The multisignature schemes are attracted to utilize in some cryptographic applications such as the blockchain. Though the lattice-based constructions of multisignature schemes exist as quantum-secure multisignature, a multisignature scheme whose security is proven in the quantum random oracle model (QROM), rather than the classical random oracle model (CROM), is not known.
In this paper, we propose a first lattice-based multisignature scheme whose security is proven in QROM. Although our proposed scheme is based on the Dilithium-QROM signature, whose security is proven in QROM, their proof technique cannot be directly applied to the multisignature setting. The difficulty of proving the security in QROM is how to program the random oracle in the security proof. To solve the problems in the security proof, we develop several proof techniques in QROM. First, we employ the searching query technique by Targi and Unruh to convert the Dilithium-QROM into the multisignature setting. For the second, we develop a new programming technique in QROM since the conventional programming techniques seem not to work in the multisignature setting of QROM. We combine the programming technique by Unruh with the one by Liu and Zhandry. The new technique enables us to program the random oracle in QROM and construct the signing oracle in the security proof.


  1. Proving ownership of Bitcoin-like UTXO’s using a zk-SNARK scheme
    Author: Aaron Menegalli-Boggelli

We study the core principles behind zk-SNARK schemes using the Pinocchio protocol [1] as reference. Furthermore, the potential of such schemes is highlighted by addressing the problem of proving ownership of some Bitcoin in a simplified setting using the ZoKrates [2] toolbox.


  1. How Lightning’s Routing Diminishes its Anonymity
    Authors: Satwik Prabhu Kumble, Dick Epema, and Stefanie Roos

Lightning, the prevailing solution to Bitcoin’s scalability issue, uses onion routing to hide senders and recipients of payments. Yet, the path between the sender and the recipient along which payments are routed is selected such that it is short, cost efficient, and fast. The low degree of randomness in the path selection entails that anonymity sets are small. However, quantifying the anonymity provided by Lightning is challenging due to the existence of multiple implementations that differ with regard to the path selection algorithm and exist in parallel within the network.
In this paper, we propose a general method allowing a local internal attacker to determine sender and recipient anonymity sets. Based on an in-depth code review of three Lightning implementations, we analyze how an adversary can predict the sender and the recipient of a multi-hop transaction. Our simulations indicate that only one adversarial node on a payment path uniquely identifies at least one of sender and recipient for around 70% of the transactions observed by the adversary. Moreover, multiple colluding attackers can almost always identify sender and receiver uniquely.


  1. Blockchain Intra- and Interoperability
    Authors: A. Lipton and T. Hardjono

We introduce blockchains and distributed ledgers and study their intra- and interoperability. Blockchain intraoperability allows one to swap di§erent assets deÖned on the same blockchain supporting smart contracts. Blockchain interoperability enables one to exchange or move assets residing on di§erent blockchains. Finding practical mechanisms for intraand interoperability is of paramount importance for the ultimate success of blockchain technology. We recommend using automated market makers for intraoperability and gateways and atomic swaps for interoperability.



Research Pulse Issue #24 is out!

The design of Decentralized Exchanges (DEXs) continues to be one of the industry’s most vibrant research areas. The majority of DEXs today are structured as Constant Function Market Makers (CFMMs), whereby traders can swap assets. Critically, these assets are priced on the basis of a constant function that is applied to an asset pool that represents a pair. While CFMMs have provided a feasible structure for trades involving two assets, their properties for multi-asset trades are not well-understood. In Constant Function Market Makers: Multi-Asset Trades via Convex Optimization, the authors formulate this issue as a convex optimization problem and provide interesting solutions that can be applied to multi-asset trades.

In the topic of security, there have also been interesting developments related to how smart contracts are governed by their creators. In Rectifying Administrated ERC20 Tokens, the authors provide a fascinating overview of the admin key issue surrounding ERC20 tokens and present risk scenarios where admin functions can be exploited. Such exploits could enable attackers to steal funds, inflate the monetary base and censor users. The authors then provide a library that can improve the security of these contracts by implementing better controls around admin functionality.

Finally, in Proving ownership of Bitcoin-like UTXO’s using a zk-SNARK scheme, the author provides a novel proving and verification mechanism of shielded (private) UTXOs using zkSNARKs. This is an interesting work as it provides a simplified way to the creation of modular privacy-preserving mechanisms that could be implemented atop existing protocols. As such, a level of privacy can be optionally added atop UTXO chains without the need for a hard-fork that adds more complex primitives to the base layer.