Research Pulse Issue #34 10/11/21

  1. On the Security and Performance of Blockchain Sharding
    Authors: Runchao Han, Jiangshan Yu, Haoyu Lin, Shiping Chen, and Paulo Esteves-Verıssimo

In this paper, we perform a comprehensive evaluation on blockchain sharding protocols. We deconstruct the blockchain sharding protocol into four foundational layers with orthogonal functionalities, securing some properties. We evaluate each layer of seven state-of-the-art blockchain sharding protocols, and identify a considerable number of new attacks, questionable design trade-offs and some open challenges. The layered evaluation allows us to unveil security and performance problems arising from a fundamental design choice, namely the coherence of system settings across layers. In particular, most sharded blockchains use different trust and synchrony assumptions across layers, without corresponding architectural guarantees. Unless a hybrid architecture were used, assuming differentiated system settings across layers can introduce subtle but severe failure syndromes or reduce the system’s performance.

Link: https://eprint.iacr.org/2021/1276.pdf

  1. A Source­Code­Based Taxonomy for Ethereum Smart Contracts
    Authors: Adrian Hofmann, Julian Kolb, Luc Becker, and Axel Winkelmann

As blockchain gained a lot of attention in IS research since its emergence, development into networks and applications have made it extremely relevant for multiple industry branches. Yet observations show, that there remains a lack of in­depth knowledge and standardization, particularly in the field of blockchain applications, DApps. These DApps often consist of multiple smart contracts, used to automate different processes and the technical elements have so far remained unexplored in depth. In this paper we address this problem by creating a data­driven taxonomy of the technical elements of 150 smart contracts within 101 DApps following the approach of Nickerson et al. (2013). We identified 28 dimension and 64 characteristics in our technical and code­based taxonomy.

Link: https://www.researchgate.net/profile/Adrian-Hofmann-3/publication/354901921_A_Source-Code-Based_Taxonomy_for_Ethereum_Smart_Contracts/links/6153537139b8157d9003f2fc/A-Source-Code-Based-Taxonomy-for-Ethereum-Smart-Contracts.pdf

  1. Selfish & Opaque Transaction Ordering in the Bitcoin Blockchain: The Case for Chain Neutrality
    Authors: Johnnatan Messias, Mohamed Alzayat, Balakrishnan Chandrasekaran, Krishna Gummadi, Patrick Loiseau, and Alan Mislove

Most public blockchain protocols, including the popular Bitcoin and Ethereum blockchains, do not formally specify the order in which miners should select transactions from the pool of pending (or uncommitted) transactions for inclusion in the blockchain. Over the years, informal conventions or “norms” for transaction ordering have, however, emerged via the use of shared software by miners, e.g., the GetBlockTemplate (GBT) mining protocol in Bitcoin Core. Today, a widely held view is that Bitcoin miners prioritize transactions based on their offered “transaction fee-per-byte.” Bitcoin users are, consequently, encouraged to increase the fees to accelerate the commitment of their transactions, particularly during periods of congestion. In this paper, we audit the Bitcoin blockchain and present statistically significant evidence of mining pools deviating from the norms to accelerate the commitment of transactions for which they have (i) a selfish or vested interest, or (ii) received dark-fee payments via opaque (non-public) side-channels. As blockchains are increasingly being used as a record-keeping substrate for a variety of decentralized (financial technology) systems, our findings call for an urgent discussion on defining neutrality norms that miners must adhere to when ordering transactions in the chains. Finally, we make our data sets and scripts publicly available.

Link: https://hal.inria.fr/hal-03361860/document

  1. The Exact Security of BIP32 Wallets
    Authors: Poulami Das, Andreas Erwig, Sebastian Faust, Julian Loss, and Siavash Riahi

In many cryptocurrencies, the problem of key management has become one of the most fundamental security challenges. Typically, keys are kept in designated schemes called wallets, whose main purpose is to store these keys securely. One such system is the BIP32 wallet (Bitcoin Improvement Proposal 32), which since its introduction in 2012 has been adopted by countless Bitcoin users and is one of the most frequently used wallet system today. Surprisingly, very little is known about the concrete security properties offered by this system. In this work, we propose the first formal analysis of the BIP32 system in its entirety and without any modification. Building on the recent work of Das et al. (CCS ‘19), we put forth a formal model for hierarchical deterministic wallet systems (such as BIP32) and give a security reduction in this model from the existential unforgeability of the ECDSA signature algorithm that is used in BIP32. We conclude by giving concrete security parameter estimates achieved by the BIP32 standard, and show that by moving to an alternative key derivation method we can achieve a tighter reduction offering an additional 20 bits of security (111 vs. 91 bits of security) at no additional costs.

Link: https://eprint.iacr.org/2021/1287.pdf

  1. Strangely mined bitcoins: Empirical analysis of anomalies in the bitcoin blockchain transaction network
    Authors: María Óskarsdóttir and Jacky Mallett

The blockchain technology introduced by bitcoin, with its decentralised peer-to-peer network and cryptographic protocols, provides a public and accessible database of bitcoin transactions that have attracted interest from both economics and network science as an example of a complex evolving monetary network. Despite the known cryptographic guarantees present in the blockchain, there exists significant evidence of inconsistencies and suspicious behavior in the chain. In this paper, we examine the prevalence and evolution of two types of anomalies occurring in coinbase transactions in blockchain mining, which we reported on in earlier research. We further develop our techniques for investigating the impact of these anomalies on the blockchain transaction network, by building networks induced by anomalous coinbase transactions at regular intervals and calculating a range of network measures, including degree correlation and assortativity, as well as inequality in terms of wealth and anomaly ratio using the Gini coefficient. We obtain time series of network measures calculated over the full transaction network and three sub-networks. Inspecting trends in these time series allows us to identify a period in time with particularly strange transaction behavior. We then perform a frequency analysis of this time period to reveal several blocks of highly anomalous transactions. Our technique represents a novel way of using network science to detect and investigate cryptographic anomalies.

Link: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0258001

  1. WebFlow: Scalable and Decentralized Routing for Payment Channel Networks with High Resource Utilization
    Authors: Xiaoxue Zhang, Shouqian Shi and Chen Qian

Payment channel networks (PCNs) have been designed and utilized to address the scalability challenge and throughput limitation of blockchains. Routing is a core problem of PCNs. An ideal PCN routing method needs to achieve 1) high scalability that can maintain low per-node memory and communication cost for large PCNs, 2) high resource utilization of payment channels, and 3) the privacy of users. However, none of the existing PCN systems consider all these requirements. In this work, we propose WebFlow, a distributed routing solution for PCNs, which only requires each user to maintain localized information and can be used for massive-scale networks with high resource utilization. We make use of two distributed data structures: multi-hop Delaunay triangulation (MDT) originally proposed for wireless networks and our innovation called distributed Voronoi diagram. We propose new protocols to generate a virtual Euclidean space in order to apply MDT to PCNs and use the distributed Voronoi diagram to enhance routing privacy. We conduct extensive simulations and prototype implementation to further evaluate WebFlow. The results using real and synthetic PCN topologies and transaction traces show that WebFlow can achieve extremely low per-node overhead and a high success rate compared to existing methods.

Link: https://arxiv.org/pdf/2109.11665.pdf

  1. Invited Paper: Failure is (literally) an Option: Atomic Commitment vs Optionality in Decentralized Finance
    Authors: Daniel Engel, Maurice Herlihy, and Yingjie Xue

Many aspects of blockchain-based decentralized finance can be understood as an extension of classical distributed computing. In this paper, we trace the evolution of two interrelated notions: failure and fault-tolerance. In classical distributed computing, a failure to complete a multi-party protocol is typically attributed to hardware malfunctions. A fault-tolerant protocol is one that responds to such failures by rolling the system back to an earlier consistent state. In the presence of Byzantine failures, a failure may be the result of an attack, and a fault-tolerant protocol is one that ensures that attackers will be punished and victims compensated. In modern decentralized finance however, failure to complete a protocol can be considered a legitimate option, not a transgression. A fault-tolerant protocol is one that ensures that the party offering the option cannot renege, and the party purchasing the option provides fair compensation (in the form of a fee) to the offering party. We sketch the evolution of such protocols, starting with two-phase commit, and finishing with timed hashlocked smart contracts.

Link: https://arxiv.org/pdf/2109.12167.pdf

  1. SoK: How private is Bitcoin? Classification and Evaluation of Bitcoin Mixing Techniques
    Authors: Simin Ghesmati, Walid Fdhila, and Edgar Weippl

Blockchain is a disruptive technology that promises a multitude of benefits, such as transparency, traceability, and immutability. However, this unique bundle of key characteristics has proved to be a double-edged sword that can put users’ privacy at risk. Unlike traditional systems, Bitcoin transactions are publicly and permanently recorded, and anyone can access the full history of the records. Despite using pseudonymous identities, an adversary can undermine users’ financial privacy and reveal their actual identities using advanced heuristics and techniques to identify possible links between transactions, senders, receivers, and consumed services (e.g., online purchases). In this regard, a multitude of approaches has been proposed to reduce financial transparency and enhance users’ anonymity. These techniques range from using mixing services to off-chain transactions that address different privacy issues. In this paper, we particularly focus on comparing and evaluating mixing techniques in the Bitcoin blockchain, present their limitations, and highlight the new challenges.

Link: https://eprint.iacr.org/2021/629.pdf

  1. zkKYC A solution concept for KYC without knowing your customer, leveraging self-sovereign identity and zero-knowledge proofs
    Author: Pieter Pauwels

Businesses that are subject to AML/CTF regulation must meet their KYC obligations. In this context, to establish and verify a customer’s identity, the customer is required to share personal information with these businesses. This creates a Pareto dominated situation where a customer’s privacy is typically traded off for the mandated transparency requirements. In addition, this privacy erosion also reduces the security and safety of the customer as shared personal information can be passed on or stolen and used against the best interest of the customer (e.g. identity theft). Recent innovations in self-sovereign identity and zero-knowledge cryptography, along with proper ecosystem design, allow for a novel approach to KYC that protects the customer’s privacy without reducing transparency. The proposed solution concept, zkKYC, removes the need for the customer to share any personal information with a regulated business for the purpose of KYC, and yet provides the transparency to allow for a customer to be identified if and when that is ruled necessary by a designated governing entity (e.g. regulator, law enforcement). This approach breaks the traditional privacy vs. transparency trade-off and provides structured transparency, resulting in a net positive outcome for all parties involved.

Link: https://eprint.iacr.org/2021/907.pdf

  1. Concentrated Liquidity in Automated Market Makers
    Author: Robin Fritsch

We examine how the introduction of concentrated liquidity has changed the liquidity provision market in automated market makers such as Uniswap. To this end, we compare average liquidity provider returns from trading fees before and after its introduction. Furthermore, we quantify the performance of a number of fundamental concentrated liquidity strategies using historical trade data. We estimate their possible returns and evaluate which perform best for certain trading pairs and market conditions.

Link: https://arxiv.org/pdf/2110.01368.pdf

  1. SolType: Refinement Types for Solidity
    Authors: Bryan Tan, Benjamin Mariano, Shuvendu Lahiri, Isil Dillig, and Yu Feng

As smart contracts gain adoption in financial transactions, it becomes increasingly important to ensure that they are free of bugs and security vulnerabilities. Of particular relevance in this context are arithmetic overflow bugs, as integers are often used to represent financial assets like account balances. Motivated by this observation, this paper presents SolType, a refinement type system for Solidity that can be used to prevent arithmetic over- and under-flows in smart contracts. SolType allows developers to add refinement type annotations and uses them to prove that arithmetic operations do not lead to over- and under-flows. SolType incorporates a rich vocabulary of refinement terms that allow expressing relationships between integer values and aggregate properties of complex data structures. Furthermore, our implementation, called Solid, incorporates a type inference engine and can automatically infer useful type annotations, including non-trivial contract invariants.
To evaluate the usefulness of our type system, we use Solid to prove arithmetic safety of a total of 120 smart contracts. When used in its fully automated mode (i.e., using Solid’s type inference capabilities), Solid is able to eliminate 86.3% of redundant runtime checks used to guard against overflows. We also compare Solid against a state-of-the-art arithmetic safety verifier called VeriSmart and show that Solid has a significantly lower false positive rate, while being significantly faster in terms of verification time.

Link: https://arxiv.org/pdf/2110.00677.pdf

1 Like

Research Pulse #34 is out!

Blockchain sharding is one of the most highly anticipated scalability solutions under development. While the team behind Ethereum 2.0 often leads the charge when it comes to this technology, there are several teams actively pursuing a shared architecture. On the Security and Performance of Blockchain Sharding provides a comprehensive overview of the current status quo and sheds light on the pros and cons of existing approaches to a sharded architecture.

In The Exact Security of BIP32 Wallets, the authors provide an evaluation of crypto’s most widely-used custody protocol: BIP32. This standard enables the creation of so-called Hierarchical Deterministic (HD) wallets which enable users of various cryptoassets to back up their wallets using a single key. Beyond providing the first thorough evaluation of the security of BIP32, this work proposes a modification to the standard that adds additional 20 bits of security at no additional cost.

Finally, in SoK: How private is Bitcoin? Classification and Evaluation of Bitcoin Mixing Techniques, the authors evaluate the strength of Bitcoin’s pseudonymity when users employ mixing techniques. Such techniques are intended to increase the privacy of users by combining their funds into a single transaction. In doing so, third parties observing the blockchain would need to perform substantially more work in order to track individual senders and receivers.

1 Like