- Maximizing Extractable Value from Automated Market Makers
Authors: Massimo Bartoletti, James Hsin-yu Chiang, and Alberto Lluch-Lafuente
Automated Market Makers (AMMs) are decentralized applications that allow users to exchange crypto-tokens without the need to find a matching exchange order. AMMs are one of the most successful DeFi use case so far, as the main AMM platforms UniSwap and Balancer process a daily volume of transactions worth billions of dollars. Despite this success story, AMMs are well-known to suffer from transaction-ordering issues: indeed, adversaries can frontrun user transactions to increase their gain to the detriment of honest users. Being specifically designated to arrange user transactions into blocks, miners can easily play the role of adversary, by suitably selecting and ordering transactions — and possibly inserting their own — to increase their gain. In this paper we formally characterize rational miners as players which follow an optimal strategy in the mining game. We identify relevant variants of the game, corresponding to specific real-world constraints that a miner might have. We devise effective procedures to construct solutions to mining game, both in its most general form and in some relevant variants. Most notably, miners can exploit these solutions to maximize the value extracted from user transactions.
Link: https://arxiv.org/pdf/2106.01870.pdf
- GoAT: File Geolocation via Anchor Timestamping
Authors: Deepak Maram, Iddo Bentov, Mahimna Kelkar, and Ari Juels
Blockchain systems are rapidly gaining traction. Decentralized storage systems like Filecoin are a crucial component of this ecosystem that aim to provide robust file storage through a Proof of Replication (PoRep) or its variants. However, a PoRep actually offers limited robustness. Indeed if all the file replicas are stored on a single hard disk, a single catastrophic event is enough to lose the file.
We introduce a new primitive, Proof of Geo-Retrievability or in short PoGeoRet, that enables proving that a file is located within a strict geographic boundary. Using PoGeoRet, one can trivially construct a PoRep by proving that a file is in several distinct geographic regions. We define what it means for a PoGeoRet scheme to be complete and sound, in the process making important extensions to prior formalism.
We propose GoAT, a practical PoGeoRet scheme to prove file geolocation. Unlike previous geolocation systems that rely on trusted verifiers, GoAT bootstraps using public time stamping servers on the internet that serve as geolocation anchors, tolerating a local threshold of dishonest anchors. GoAT internally uses a communication efficient Proof-of-Retrievability (PoRet) scheme in a novel way to achieve constant-size PoRet-component in its proofs. We validate GoAT’s practicality by conducting an initial measurement study to find usable anchors and also perform a real-world experiment. The results show that a significant fraction of the internet can be used as anchors and that GoAT achieves geolocation radii as little as 1000km.
Link: https://eprint.iacr.org/2021/697.pdf
- Designing Stable Coins
Authors: Yizhou Cao, Min Dai, Steven Kou, Lewei Li, and Chen Yang
Existing cryptocurrencies are too volatile to be used as currencies for daily payments. Stable coins, which are cryptocurrencies pegged to other stable financial assets such as the U.S. dollar, are desirable for payments within blockchain networks, whereby being often called the “Holy Grail of cryptocurrency.” By using the option pricing theory and the Ethereum platform that allows running smart contracts, we design several dual-class structures that are written on the ETH cryptocurrency and offer a fixed income crypto asset (class A coin), a stable coin (class A0 coin) pegged to a traditional currency, and leveraged investment instruments (class B and B0 coins). Our investigation of the values of stable coins in presence of jump risk and black-swan type events shows the robustness of the design. The design has been implemented on the Ethereum platform.
- Phoenix: A Formally Verified Regenerating Vault
Authors: Uri Kirstein, Shelly Grossman, Michael Mirkin, James Wilcox, Ittay Eyal, and Mooly Sagiv
An attacker that gains access to a cryptocurrency user’s private keys can perform any operation in her stead. Due to the decentralized nature of most cryptocurrencies, no entity can revert those operations. This is a central challenge for decentralized systems, illustrated by numerous high-profile heists. Vault contracts reduce this risk by introducing artificial delay on operations, allowing abortion by the contract owner during the delay. However, the theft of a key still renders the vault unusable and puts funds at risk.
We introduce Phoenix, a novel contract architecture that allows the user to restore its security properties after key loss. Phoenix takes advantage of users’ ability to store keys in easily-available but less secure storage (tier-two) as well as more secure storage that is harder to access (tier-one). Unlike previous solutions, the user can restore Phoenix security after the theft of tier-two keys and does not lose funds despite losing keys in either tier. Phoenix also introduces a mechanism to reduce the damage an attacker can cause in case of a tier-one compromise.
We formally specify Phoenix’s required behavior and provide a prototype implementation of Phoenix as an Ethereum contract. Since such an implementation is highly sensitive and vulnerable to subtle bugs, we apply a formal verification tool to prove specific code properties and identify faults. We highlight a bug identified by the tool that could be exploited by an attacker to compromise Phoenix. After fixing the bug, the tool proved the low-level executable code’s correctness.
Link: https://arxiv.org/pdf/2106.01240.pdf
- Analysis of CryptoNote Transaction Graphs using the Dulmage-Mendelsohn Decomposition
Author: Saravanan Vijayakumaran
Transactions in CryptoNote blockchains induce a bipartite graph, with the set of transaction outputs forming one vertex class and the set of key images forming the other vertex class. In this graph, an edge exists between an output and a key image if the output appeared in the ring of the linkable ring signature which created the key image. Any maximum matching on this graph is a plausible candidate for the ground truth, i.e. the association of each key image with the actual output being spent in the transaction.
The Dulmage-Mendelsohn (DM) decomposition of a bipartite graph reveals constraints which are satisfied by every maximum matching on the graph. It identifies vertices which are matched in every maximum matching. It classifies edges as admissible or inadmissible. An edge is called admissible if it appears in at least one maximum matching and is called inadmissible if it does not appear in any maximum matching.
The DM decomposition of a CryptoNote transaction graph reveals a set of outputs which can be marked as spent (precisely those outputs which are matched by every maximum matching). In some transaction rings, the decomposition identifies the true output being spent (making the ring traceable) by classifying the edges from all the other outputs to the key image as inadmissible.
For pre-RingCT outputs in Monero, the DM decomposition performs better than existing techniques for Monero traceability, but the improvement is marginal. For RingCT outputs in Monero up to April 1, 2021, the DM decomposition is only able to identify the same five outputs that were identified as spent by existing techniques (which do not use information from hard forks).
Link: https://eprint.iacr.org/2021/760.pdf
- SoK: Privacy-Preserving Computing in the Blockchain Era
Authors: Ghada Almashaqbeh and Ravital Solomon
Cryptocurrency and blockchain continue to build on an innovative computation model that has paved the way for a large variety of applications. However, privacy is a huge concern as most (permissionless) blockchains log everything in the clear. This has resulted in several academic and industrial initiatives to address privacy. Starting with the UTXO model introduced by Bitcoin, initial works brought confidentiality and anonymity to payments. Recent works have expanded to support more generalized forms of private computation. Such solutions tend to be highly involved as they rely on advanced cryptographic primitives and creative techniques to handle issues related to dealing with private blockchain records (e.g. concurrency, private coin tracking to prevent double spending, efficiency). This situation makes it hard to comprehend the current state-of-the-art, much less build on top of it. To address these challenges, we provide a systematization of knowledge for privacy-preserving solutions in blockchain. To the best of our knowledge, our work is the first of its kind. After motivating design challenges, we provide an overview of the zero-knowledge proof systems used in supporting blockchain privacy, focusing on their key features and limitations. Then, we develop a systematization of knowledge framework using which we group the state-of-the-art privacy preserving solutions under three categories: private payments, computation with input/output privacy, and function privacy. We briefly touch upon challenges and implications including misuse, regulations and compliance, usability, and limited functionality. Our work seeks to highlight open problems and research questions to guide future work directions.
Link: https://eprint.iacr.org/2021/727.pdf
- An analysis and evaluation of lightweight hash functions for blockchain-based IoT devices (Paywalled: SCRF members can request access.)
Authors: Sa’ed Abed, Reem Jaffal, Bassam J. Mohd, and Mohammad Al-Shayeji
Blockchain is among the most promising new technologies due to its unique features, encompassing security, privacy, data integrity, and immutability. Blockchain applications include cryptocurrencies such as Bitcoin. Recently, many other applications have begun to deploy blockchain in their systems. These applications include internet of things (IoT) environments. Although deploying blockchain in IoT architecture has yielded numerous advantages, issues and challenges have arisen that require further research. Most IoT devices and platforms have limited storage capacity, low battery power, and limited hardware resources for computation and network communication. Thus, energy efficiency is a critical factor in these devices. On the other hand, blockchain requires extensive resources and high computational capabilities for mining and communication processes. Balancing computation complexity and IoT resources is a fundamental design challenge in implementing blockchain functions, including the hash function, which is crucial to blockchain design for the mining process. In this study, we present a literature review on the common hash functions used in blockchain-based applications, in addition to the lightweight hash functions available in literature. We evaluate and test the common lightweight hash functions (SPONGENT, PHOTON, and QUARK) on FPGA platforms to determine which is most suitable for blockchain-IoT devices. Moreover, we assess lightweight hash functions in terms of area, power, energy, security, and throughput. The results show tradeoffs between these hash functions. SPONGENT performs best on security and throughput. QUARK consumes the least power and energy but has the lowest security parameters. PHOTON utilizes less area and offers a balance between multiple performance metrics (area, energy, and security), rendering it the most suitable lightweight hash function.
Link: https://link.springer.com/article/10.1007/s10586-021-03324-1
- Secure Multi-Party Computation in Practice
Author: Marcella Christine Hastings
Secure multi-party computation (MPC) is a cryptographic primitive for computing on private data. MPC provides strong privacy guarantees, but practical adoption requires high-quality application design, software development, and resource management. This dissertation aims to identify and reduce barriers to practical deployment of MPC applications.
First, the dissertation evaluates the design, capabilities, and usability of eleven state-of-the-art MPC software frameworks. These frameworks are essential for prototyping MPC applications, but their qualities vary widely; the survey provides insight into their current abilities and limitations. A comprehensive online repository augments the survey, including complete build environments, sample programs, and additional documentation for each framework.
Second, the dissertation applies these lessons in two practical applications of MPC. The first addresses algorithms for assessing stability in financial networks, traditionally designed in a full information model with a central regulator or data aggregator. This case study describes principles to transform two such algorithms into data-oblivious versions and benchmark their execution under MPC using three frameworks. The second aims to enable unlinkability of payments made with blockchain-based cryptocurrencies. This study uses MPC in conjunction with other privacy techniques to achieve unlinkability in payment channels. Together, these studies illuminate the limitations of existing software, develop guidelines for transforming non-private algorithms into versions suitable for execution under MPC, and illustrate the current practical feasibility of MPC as a solution to a wide variety of applications.
Link: Secure Multi-Party Computation in Practice - ProQuest
- BALAdIN: truthfulness in collaborative access networks with distributed ledgers (Paywalled: SCRF members can request access)
Authors: Vincent Messié, Gaël Fromentoux, Nathalie Labidurie, Benoit Radier, Sandrine Vaton, and Isabel Amigo
Distributed ledger technology (DLT), also known as “Blockchain” is one of the trendiest digital innovations in our era. While firstly applied to crypto-currencies, the trustworthiness inherent to DLT paved the way to many new usages notably in sectors such as land registration or banking where confidence in transactions is crucial. In the telecommunications sector, DLTs have enabled the development of future network architectures, such as new decentralised and multi-actor access networks. Having identified this as a great opportunity, we designed BALAdIN, a novel Blockchain-powered decentralised application that improves network coverage thanks to partnerships. Indeed, it allows a crowd of local actors such as shop tenants to deploy mobile cells with the help of a consortium of telcos. The traffic conveyed by each actor is traced thanks to a decentralised and trustworthy network monitoring mechanism we have designed. This mechanism both solves the centralisation dilemma caused by Blockchain Oracles and allows each actor to be rewarded depending on usage. In this paper, we focus on the description of this network usage monitoring mechanism. We then study the feasibility of its implementation onto regular Blockchain by studying its performance regarding the throughput and the propagation of the resulting Blockchain transactions. Finally, we derive a scalable deployment scheme for our novel Blockchain-powered decentralised network metering application BALAdIN.
- The Matrix Reloaded: Multiplication Strategies in FrodoKEM
Authors: Joppe W. Bos, Maximilian Ofner, Joost Renes, Tobias Schneider, and Christine van Vredendaal
Lattice-based schemes are promising candidates to replace the current public-key cryptographic infrastructure in wake of the looming threat of quantum computers. One of the Round 3 candidates of the ongoing NIST post-quantum standardization effort is FrodoKEM. It was designed to provide conservative security, which comes with the caveat that implementations are often bigger and slower compared to alternative schemes. In particular, the most time-consuming arithmetic operation of FrodoKEM is the multiplication of matrices with entries in Zq.
In this work, we investigate the performance of different matrix multiplication approaches in the specific setting of FrodoKEM. We consider both optimized “na¨ıve” matrix multiplication with cubic complexity, as well as the Strassen multiplication algorithm which has a lower asymptotic run-time complexity. Our results show that for the proposed parameter sets of FrodoKEM we can improve over the state-of-the-art implementation with a row-wise blocking and packing approach, denoted as RWCF in the following. For the matrix multiplication in FrodoKEM, this results in a factor two speed-up. The impact of these improvements on the full decapsulation operation is up to 22 percent. We additionally show that for batching use-cases, where many inputs are processed at once, the Strassen approach can be the best choice from batch size 8 upwards. For a practically-relevant batch size of 128 inputs the observed speed-up is in the range of 5 to 11 percent over using the efficient RWCF approach and this speed-up grows with the batch size.