- An Overview of Trees in Blockchain Technology: Merkle Trees and Merkle Patricia Tries
Author: Haitz Sáez de Ocáriz Borde
In this work we present an overview of trees in distributed systems and blockchain, and summarize some of the keyconcepts. We focus on Merkle Trees and Merkle Patricia Tries, which are used in Bitcoin and Ethereum, respectively.
- Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM
Authors: Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner
Commit-and-open Σ-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction.
In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkletree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic.
Our analysis makes use of a recent framework by Chung et al. [CFHL21] for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.
Link: https://arxiv.org/pdf/2202.13730.pdf
- Classical Verification of Quantum Computations in Linear Time
Author: Jiayu Zhang
In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit C is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [30, 1, 41]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of total time complexity of both the client and the server, the fastest single-server CVQC protocol so far has complexity O(poly(κ)|C| 3 ) where |C| is the size of the circuit to be verified, given by Mahadev [38].
In this work, by developing new techniques, we give a new CVQC protocol with complexity O(poly(κ)|C|), which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [9] assuming the existence of noisy trapdoor claw-free functions [10], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in {|+θi = √1 2 (|0i + e iθπ/4 |1i) : θ ∈ {0, 1 · · · 7}}, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of L independently random states in this form (up to a constant overall error and a possibly unbounded server-side isometry), and runs in only O(poly(κ)L) time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [31, 18, 4, 34].
Link: https://arxiv.org/pdf/2202.13997.pdf
- Impermanent Loss and Gain of Automated Market Maker Smart Contracts
Authors: Hyoung Joong Kim, Soohyuk Choi, Yong Tae Yoon, and Shiyong Yoo
Smart contract is an important building block of blockchain. Automated market makers are working without an order book, and they determine the price of assets automatically. It is reported that he automated market makers have the impermanent loss, which causes financial damage to liquidity providers. Impermanent loss makes the liquidity providers hesitant to deposit assets in the liquidity pool. Therefore, their participation incentive from liquidity provision should be anticipated by automatic market makers inherently. However, the existence of impermanent gain has never been reported. Impermanent gain is important to attract liquidity providers without giving compensation incentives. This study shows that for some automated market makers, impermanent gain coexists with impermanent loss. Examples showing the coexistence and conditions are provided.
Link: Impermanent Loss and Gain of Automated Market Maker Smart Contracts
- NFTs Emergence in Financial Markets and their Correlation with DeFis and Cryptocurrencies
Authors: Khuloud M. Alawadhi and Nour Alshamali
Non-fungible tokens (NFT) have been defined as digital assets that encode items such as art, collectables, and in-game goods. They are often stored in smart contracts on a blockchain and are exchanged online, frequently using Bitcoin. As NFT became increasingly popular in the last few years, decentralized financial assets (DeFi) tokens also started receiving growing attention as financial instruments that differ from NFTs and cryptocurrencies. Based on data on NFTs, DeFi tokens, and cryptocurrency daily prices between January 15th and December 6th, 2021, we examine the correlation between NFTs, DeFi tokens and major cryptocurrencies such as Bitcoin and Ethereum. Using the volatility spillover matrix approach by Diebold and Yilmaz (2012) as applied by Dowling (2021) and including DeFis into the discussion, we find that there is very limited spillover to and from non-traditional financial markets. Also, DeFi assets appear to be relatively unconnected to cryptocurrency markets. Following the methodology by Karim, Lucey, Naeem and Uddin (2021) of the quantile connectedness approach and the cross-quantilogram model of Han, Linton, Oka and Whang (2016), we determine that positive DeFi and Crypto spillovers exceeded negative NFT spillovers. This paper concludes that both NFTs and DeFi assets show significant potential in terms of portfolio diversification since they display low correlation with cryptocurrencies, especially in the case of DeFis thanks to it being disconnected from other assets in the market, based on this year’s data. This has significant implications for investors who seek to diversify their portfolios by including cryptocurrency, NFTs and DeFis as assets.
Link: https://econpapers.repec.org/article/rfaaefjnl/v_3a9_3ay_3a2022_3ai_3a1_3ap_3a108-120.htm
- EcGFp5: a Specialized Elliptic Curve
Author: Thomas Pornin
We present here the design and implementation of ecGFp5, an elliptic curve meant for a speciec compute model in which operations modulo a given 64-bit prime are especially e cient. This model is primarily intended for running operations in a virtual machine that produces and veriees zero-knowledge STARK proofs. We describe here the choice of a secure curve, amenable to safe cryptographic operations such as digital signatures, that maps to such models, while still providing reasonable performance on general purpose computers.
Link: https://eprint.iacr.org/2022/274.pdf
- Mining Domain Models in Ethereum DApps using Code Cloning
Authors: Noama Fatima Samreen and Manar H. Alalfi
This paper discusses and demonstrates the use of near-miss clone detection to support the characterization of domain models of smart contracts for each of the popular domains in which smart contracts are being rapidly adopted. In this paper, we leverage the code clone detection techniques to detect similarities in functions of the smart contracts deployed onto the Ethereum blockchain network. We analyze the clusters of code clones and the semantics of the code fragments in the clusters in an attempt to categorize them and discover the structural models of the patterns in code clones.
Link: https://arxiv.org/pdf/2203.00771.pdf
- Two Attacks On Proof-of-Stake GHOST/Ethereum
Authors: Joachim Neu, Ertem Nusret Tas, and David Tse
We present two attacks targeting the Proof-of-Stake (PoS) Ethereum consensus protocol. The first attack suggests a fundamental conceptual incompatibility between PoS and the Greedy Heaviest-Observed Sub-Tree (GHOST) fork choice paradigm employed by PoS Ethereum. In a nutshell, PoS allows an adversary with a vanishing amount of stake to produce an unlimited number of equivocating blocks. While most equivocating blocks will be orphaned, such orphaned ‘uncle blocks’ still influence fork choice under the GHOST paradigm, bestowing upon the adversary devastating control over the canonical chain. While the Latest Message Driven (LMD) aspect of current PoS Ethereum prevents a straightforward application of this attack, our second attack shows how LMD specifically can be exploited to obtain a new variant of the balancing attack that overcomes a recent protocol addition that was intended to mitigate balancing-type attacks. Thus, in its current form, PoS Ethereum without and with LMD is vulnerable to our first and second attack, respectively.
Link: https://arxiv.org/pdf/2203.01315.pdf
- VOLCANO: Detecting Vulnerabilities of Ethereum Smart Contracts Using Code Clone Analysis
Authors: Noama Fatima Samreen and Manar H. Alalfi
Ethereum Smart Contracts based on Blockchain Technology (BT) enables monetary transactions among peers on a blockchain network independent of a central authorizing agency. Ethereum Smart Contracts are programs that are deployed as decentralized applications, having the building blocks of the blockchain consensus protocol. This enables consumers to make agreements in a transparent and conflict-free environment. However, there exists some security vulnerabilities within these smart contracts that are a potential threat to the applications and their consumers and have shown in the past to cause huge financial losses. This paper presents a framework and empirical analysis that use code clone detection techniques for identifying vulnerabilities and their variations in smart contracts. Our empirical analysis is conducted using Nicad code clone detection tool on a dataset of approximately 50k Ethereum smart contracts. We evaluated VOLCANO on two datasets, one with confirmed vulnerabilities and another with approximately 50k random smart contracts collected from the Etherscan[1]. Our approach shows an improvement in detection of vulnerabilities in terms of coverage and efficiency when compared to two of the publicly available static analysers to detect vulnerabilities in smart contracts. To the best of our knowledge, this is the first study that uses a clone detection technique to identify vulnerabilities and their evolution in Ethereum smart contracts.
Link: https://arxiv.org/pdf/2203.00769.pdf
- An Empirical Study of Market Inefficiencies in Uniswap and SushiSwap
Authors: Jan Arvid Berg, Robin Fritsch, Lioba Heimbach, and Roger Wattenhofer
Decentralized exchanges are revolutionizing finance. With their ever-growing increase in popularity, a natural question that begs to be asked is: how efficient are these new markets?
We find that nearly 30% of analyzed trades are executed at an unfavorable rate. Additionally, we observe that, especially during the DeFi summer in 2020, price inaccuracies across the market plagued DEXes. Uniswap and SushiSwap, however, quickly adapt to their increased volumes. We see an increase in market efficiency with time during the observation period. Nonetheless, the DEXes still struggle to track the reference market when cryptocurrency prices are highly volatile. During such periods of high volatility, we observe the market becoming less efficient – manifested by an increased prevalence in cyclic arbitrage opportunities.
- Non-interactive Mimblewimble transactions, revisited
Authors: Georg Fuchsbauer and Michele Orru
Mimblewimble is a cryptocurrency protocol promising to overcome notorious blockchain scalability issues. To this day, one of the major factors hindering its wider adoption is the lack of non-interactive transactions, that is, payments where only the sender needs to be online. We analyze and fix a proposal by Yu, which, inspired by stealth addresses, introduces non-interactive transactions to Mimblewimble.
Link: https://eprint.iacr.org/2022/265.pdf
- A Survey on Group Signatures and Ring Signatures: Traceability vs. Anonymity
Authors: Maharage Nisansala Sevwandi Perera, Toru Nakamura, Masayuki Hashimoto, Hiroyuki Yokoyama, Chen-Mou Cheng, and Kouichi Sakurai
This survey reviews the two most prominent group-oriented anonymous signature schemes and analyzes the existing approaches for their problem: balancing anonymity against traceability. Group signatures and ring signatures are the two leading competitive signature schemes with a rich body of research. Both group and ring signatures enable user anonymity with group settings. Any group user can produce a signature while hiding his identity in a group. Although group signatures have predefined group settings, ring signatures allow users to form ad-hoc groups. Preserving user identities provided an advantage for group and ring signatures. Thus, presently many applications utilize them. However, standard group signatures enable an authority to freely revoke signers’ anonymity. Thus, the authority might weaken the anonymity of innocent users. On the other hand, traditional ring signatures maintain permanent user anonymity, allowing space for malicious user activities; thus achieving the requirements of privacy-preserved traceability in group signatures and controlled anonymity in ring signatures has become desirable. This paper reviews group and ring signatures and explores the existing approaches that address the identification of malicious user activities. We selected many papers that discuss balancing user tracing and anonymity in group and ring signatures. Since this paper scrutinizes both signatures from their basic idea to obstacles including tracing users, it provides readers a broad synthesis of information about two signature schemes with the knowledge of current approaches to balance excessive traceability in group signatures and extreme anonymity in ring signatures. This paper will also shape the future research directions of two critical signature schemes that require more awareness.