Research Pulse Issue #29 09/07/21

  1. Elysium: Automagically Healing Vulnerable Smart Contracts Using Context-Aware Patching
    Authors: Christof Ferreira Torres, Hugo Jonker, and Radu State

Smart contracts are programs that are deployed and executed on the blockchain. Typically, smart contracts govern assets; popular smart contracts can govern assets worth millions. Just like traditional programs, smart contracts are subject to programming mistakes. However, a major difference is that smart contracts cannot be patched once deployed. Several approaches have been studied to improve smart contract security, by detecting bugs prior to deployment, allowing contracts to be updated, or modifying clients to prevent attacking transactions. The most elegant solution would be to automatically eliminate bugs prior to deployment. Merely identifying bugs is not enough. This became evident when the Parity wallet was hacked a second time after being manually patched following a security audit. Automatic pre-deployment patching offers a powerful promise to strengthen smart contract defenses. Current approaches are limited in the types of vulnerabilities that can be patched, in the flexibility of the patching process, and in scalability. In this paper we propose Elysium, a scalable approach towards automatic smart contract repair, that combines template-based patching with semantic patching by inferring context information from the bytecode. Elysium can currently automatically patch 7 known vulnerabilities in smart contracts using external bug-finding tools, and it can easily be extended with new templates and new bug-finding tools. We evaluate effectiveness and correctness of Elysium using 3 different datasets by replaying more than 500K transactions against patched contracts. We find that Elysium outperforms existing tools by patching at least 30% more contracts. Finally, we compare the overhead in terms of deployment and transaction cost increase. In comparison to other tools, Elysium minimizes transaction cost (up to a factor of 1.9), for only a marginally higher deployment cost.

Link: [2108.10071] Elysium: Automagically Healing Vulnerable Smart Contracts Using Context-Aware Patching

  1. Identifying Ransomware Actors in the Bitcoin Network
    Authors: Siddhartha Dalal, Zihe Wang, and Siddhanth Sabharwal

Due to the pseudo-anonymity of the Bitcoin network, users can hide behind their bitcoin addresses that can be generated in unlimited quantity, on the fly, without any formal links between them. Thus, it is being used for payment transfer by the actors involved in ransomware and other illegal activities. The other activity we consider is related to gambling since gambling is often used for transferring illegal funds. The question addressed here is that given temporally limited graphs of Bitcoin transactions, to what extent can one identify common patterns associated with these fraudulent activities and apply them to find other ransomware actors. The problem is rather complex, given that thousands of addresses can belong to the same actor without any obvious links between them and any common pattern of behavior. The main contribution of this paper is to introduce and apply new algorithms for local clustering and supervised graph machine learning for identifying malicious actors. We show that very local subgraphs of the known such actors are sufficient to differentiate between ransomware, random and gambling actors with 85% prediction accuracy on the test data set.

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

  1. Generalizing Weighted Trees: A Bridge from Bitcoin to GHOST
    Authors: Ignacio Amores-Sesar, Christian Cachin, and Anna Parker

Despite the tremendous interest in cryptocurrencies like Bitcoin and Ethereum today, many aspects of the underlying consensus protocols are poorly understood. Therefore, the search for protocols that improve either throughput or security (or both) continues. Bitcoin always selects the longest chain (i.e., the one with most work). Forks may occur when two miners extend the same block simultaneously, and the frequency of forks depends on how fast blocks are propagated in the network. In the GHOST protocol, used by Ethereum, all blocks involved in the fork contribute to the security. However, the greedy chain selection rule of GHOST does not consider the full information available in the block tree, which has led to some concerns about its security.
This paper introduces a new family of protocols, called Medium, which takes the structure of the whole block tree into account, by weighting blocks differently according to their depths. Bitcoin and GHOST result as special cases. This protocol leads to new insights about the security of Bitcoin and GHOST and paves the way for developing network- and application-specific protocols, in which the influence of forks on the chain-selection process can be controlled. It is shown that almost all protocols in this family achieve strictly greater throughput than Bitcoin (at the same security level) and resist attacks that can be mounted against GHOST.

Link: [2108.13502] Generalizing Weighted Trees: A Bridge from Bitcoin to GHOST

  1. “Act natural!”: Having a Private Chat on a Public Blockchain
    Authors: Thore Tiemann, Sebastian Berndt, Thomas Eisenbarth, and Maciej Liskiewicz

Chats have become an essential means of interpersonal interaction. Yet untraceable private communication remains an elusive goal, as most messengers hide content, but not communication patterns. The knowledge of communication patterns can by itself reveal too much, as happened e. g., in the context of the Arab Spring. The subliminal channel in cryptographic systems – as introduced by Simmons in his pioneering works – enables untraceable private communication in plain sight. In this context, blockchains are a natural object for subliminal communication: accessing them is innocuous, as they rely on distributed access for verification and extension. At the same time, blockchain transactions generate hundreds of thousands transactions per day that are individually signed and placed on the blockchain. This significantly increases the availability of publicly accessible cryptographic transactions where subliminal channels can be placed. In this paper we propose a public-key subliminal channel using ECDSA signatures on blockchains and prove that our construction is undetectable in the random oracle model under a common cryptographic assumption. While our approach is applicable to any blockchain platform relying on (variants of) ECDSA signatures, we present a proof of concept of our method for the popular Bitcoin protocol and show the simplicity and practicality of our approach.

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

  1. Chartalist: Labeled Graph Datasets for UTXO and Account based blockchains
    Author: Cuneyt G. Akcora, Friedhelm Victor, Murat Kantarcioglu, and Yulia R. Gel

Machine learning on blockchain graphs is an emerging field with many applications such as ransomware payment detection, price manipulation analysis, and money laundering detection. However, on many blockchains, analyzing the data requires domain expertise and computational resources which pose a significant barrier and hinder advancement in this field. To address this challenge, we introduce Chartalist, the first comprehensive platform to methodically access and use machine learning across a large selection of blockchains. Chartalist contains ML-ready datasets from unspent transaction output and account-based blockchains. Chartalist also provides data science tools for making the execution of machine learning tasks on blockchains easier. We envision that Chartalist can facilitate data modeling, analysis, and representation of blockchain data and attract a wider community of scientists to analyze blockchains. Chartalist is an open-science initiative that can be accessed at https://github.com/Chartalist.

Link: https://openreview.net/pdf?id=c0psj-rpDZm

  1. Mt. Random : Multi-Tiered Randomness Beacons
    Authors: Ignacio Cascudo, Bernardo David, Omer Shlomovits, and Denis Varlakov

Many decentralized applications require a common source of randomness that cannot be biased by any single party. Randomness beacons provide such a functionality, allowing any (third) party to periodically obtain random values and verify their validity (i.e. check that they are indeed produced by the beacon and consequently random). Protocols implementing randomness beacons have been constructed via a number of different techniques. In particular, several beacons based on time-based cryptography, Publicly Verifiable Secret Sharing (PVSS), Verifiable Random Functions (VRF) and their threshold variant (TVRF) have been proposed. These protocols provide a range of efficiency/randomness quality trade-offs but guarantee security under different setups, assumptions and adversarial models.
In this work, we propose Mt. Random, a multi-tiered randomness beacon that combines PVSS and (T)VRF techniques in order to provide an optimal efficiency/quality trade-off without sacrificing security guarantees. Each tier is based on a different technique and provides a constant stream of random outputs offering progressing efficiency vs. quality trade-offs: true uniform randomness is refreshed less frequently than pseudorandomness, which in turn is refreshed less frequently than (bounded) biased randomness. This wide span of efficiency/quality allows for applications to consume random outputs from an optimal point in this trade-off spectrum. In order to achieve these results, we construct two new building blocks of independent interest: GULL, a PVSS-based beacon that preprocesses a large batch of random outputs but allows for gradual release of smaller “subbatches”, which is a first in the literature of randomness beacons; and a publicly verifiable and unbiasable protocol for Distributed Key Generation protocol (DKG), which is significantly more efficient than most of previous DKGs secure under standard assumptions and closely matches the efficiency of the currently most efficient biasable DKG protocol.
Mt. Random (and all of its building blocks) can be proven secure under the standard DDH assumption (in the random oracle model) using only a bulletin board as setup, which is a requirement for the vast majority of beacons. We showcase the efficiency of our novel building blocks and of the Mt. Random beacon via benchmarks made with a prototype implementation. Our experimental results confirm the benefits of our multi-tiered approach, showing that even though higher tiers provide fresh random outputs more often, lower tiers can be executed fast enough to keep higher tiers freshly seeded.

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

  1. MProve+: Privacy Enhancing Proof of Reserves Protocol for Monero
    Authors: Arijit Dutta, Suyash Bagad, and Saravanan Vijayakumaran

Proof of reserves protocols enable cryptocurrency exchanges to prove solvency, i.e. prove that they have enough reserves to meet their liabilities towards their customers. MProve (EuroS&PW, 2019) was the first proof of reserves protocol for Monero which provided some privacy to the exchanges’ addresses. As the key images and the addresses are inherently linked in the MProve proof, an observer could easily recognize the exchange-owned address when a transaction spending from it appears on the blockchain. This is detrimental for an exchange’s privacy and becomes a natural reason for exchanges to not adopt MProve. To this end, we propose MProve+, a Bulletproofsbased (S&P, 2018) NIZK protocol, which unlinks the key images and the addresses, thus alleviating the drawback of MProve. Furthermore, MProve+ presents a promising alternative to MProve due to an order of magnitude smaller proof sizes along with practical proof generation and verification times.

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

  1. SolDetector: Detect Defects Based on Knowledge Graph of Solidity Smart Contract
    Authors: Tianyuan Hu, Zhenyu Pan, and Bixin Li

Smart contract security is one of core security issues in the application of blockchain. In recent years, attacks on smart contracts occur frequently, there are a lot of researches concerning on smart contract security issues. However, almost all solutions proposed in these researches are low precision and high False Negative Rate(FNR). In this paper, we propose a defect detection method for checking security of Solidity smart contract based on knowledge graph. Therefore, we first construct knowledge graph of smart contracts by fully integrating syntax and semantic information of Solidity source code; then, we define defect patterns by analyzing defect characteristics; furthermore, we define inference rules for defects based on knowledge graph and defect patterns; finally, we detect defects by SPARQL query. We also implement a tool named SolDetector and perform experiment on three different datasets, which shows that SolDetector is effective and efficient.

Link: https://ksiresearch.org/seke/seke21paper/paper133.pdf

  1. Differential Privacy in Constant Function Market Makers
    Authors: Tarun Chitra, Guillermo Angeris, and Alex Evans

Constant function market makers (CFMMs) are the most popular mechanism for facilitating decentralized trading. While these mechanisms have facilitated hundreds of billions of dollars of trades, they provide users with little to no privacy. Recent work illustrates that privacy cannot be achieved in CFMMs without forcing worse pricing and/or latency on end users. This paper more precisely quantifies the trade-off between pricing and privacy in CFMMs. We analyze a simple privacy-enhancing mechanism called Uniform Random Execution and prove that it provides (, δ)-differential privacy. The privacy parameter depends on the curvature of the CFMM trading function and the number of trades executed. This mechanism can be implemented in any blockchain system that allows smart contracts to access a verifiable random function. We also investigate the worst case complexity over all private CFMM mechanisms using recent results from private PAC learning. These results suggest that one cannot do much better than Uniform Random Execution in CFMMs with non-zero curvature. Our results provide an optimistic outlook on providing partial privacy in CFMMs.

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

  1. Systematic Review of Ethereum Smart Contract Security Vulnerabilities, Analysis Methods and Tools
    Author: Heidelinde Rameder

Smart contracts deployed to the Ethereum blockchain hold billions of dollars worth of assets. Ethereum currently represents the most widely used smart contract platform. It is the second largest blockchain system, based on market capitalization, after Bitcoin with a continuously growing market share.
Since smart contracts cannot be changed after deployment, it is critical the code is checked for potential vulnerabilities, that can cause substantial financial losses and damage trust. Numerous tools have been developed for this purpose and extensive literature on vulnerabilities and detection methods on the topic keeps emerging. Regular reviews are essential in order to keep pace with the rapidly advancing field.
This work presents a systematic literature and tool review providing a structured, comprehensive overview of state of the art tools, classifications of smart contract vulnerabilities, and detection methods. A precise review strategy and protocol is strictly followed and documented. Search and relevance checks assure comprehensive and reproducible results of the systematic literature review (SLR). Initial search results are collected, references cleaned up, duplicates removed and inclusion and exclusion criteria applied, resulting in an first identification of 303 publications. After conducting a quality appraisal based on intrinsic and contextual data quality metrics, a final set of 149 primary studies, 38 surveys and 8 SLRs is selected for data extraction.
The synthesis includes a comprehensive classification of smart contract vulnerabilities, a novel taxonomy of analysis tool properties and methods employed, as well as an overview of tools, including a structured comparison based on the taxonomy.
Finally, a consolidated collection of published and available benchmark data sets is provided.

Link: https://repositum.tuwien.at/bitstream/20.500.12708/18323/1/Rameder%20Heidelinde%20-%202021%20-%20Systematic%20Review%20of%20Ethereum%20Smart%20Contract...pdf

  1. Clover: an Anonymous Transaction Relay Protocol for the Bitcoin P2P Network∗
    Authors: Federico Franzoni and Vanesa Daza

The Bitcoin P2P network currently represents a reference benchmark for modern cryptocurrencies. Its underlying protocol defines how transactions and blocks are distributed through all participating nodes. To protect user privacy, the identity of the node originating a message is kept hidden. However, an adversary observing the whole network can analyze the spread pattern of a transaction to trace it back to its source. This is possible thanks to the so-called rumor centrality, which is caused by the symmetry in the spreading of gossip-like protocols.
Recent works try to address this issue by breaking the symmetry of the Diffusion protocol, currently used in Bitcoin, and leveraging proxied broadcast. Nonetheless, the complexity of their design can be a barrier to their adoption in real life. In this work, we propose Clover, a novel transaction relay protocol that protects the source of transaction messages with a simple, yet effective, design. Compared to previous solutions, our protocol does not require building propagation graphs, and reduces the ability of the adversary to gain precision by opening multiple connections towards the same node. Experimental results show that the deanonymization accuracy of an eavesdropper adversary against Clover is up to 10 times smaller compared to Diffusion.

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

  1. Quantitative Analysis of MakerDAO’s Liquidation System
    Author: Martin Kjäer

With the growth and development of smart contract-based blockchains a completely new technology entered the stage and initiated a revolution comparable to the one that begun in the 1990s after the invention of the Internet. During the last years a variety of new product categories have unfolded on top of these blockchains, with stablecoins being one of them. Stablecoins are tokens that aim to be stable in price and are thus comparable to fiat currencies. The most well-known decentralized stablecoin project is MakerDAO, which lives on Ethereum and offers a stablecoin named DAI. Especially due to the project’s novel approach of having its core business logic implemented in smart contracts, it is worth to investigate it from an academic perspective. Within the scope of this thesis, we focus on MakerDAO’s liquidation mechanisms that aim to secure the value of its stablecoin. After analyzing MakerDAO’s core contracts we develop requirements that need to be fulfilled in order to guarantee a secure operation of the protocol. We derive metrics from these requirements that help us assess if the requirements are met in practice. MakerDAO’s liquidation mechanism turns out to work well during most times, however, it also faces difficulties when under stress. Especially during the so-called Black Thursday event in March 2020, the protocol was not able to continue normal operation and found itself with several millions of uncovered debt. It seems that the community has fixed most of the issues that led to this incident, yet further research is needed to evaluate how a recently deployed remake of the collateral auctioning mechanism proves itself in practice.

Link: https://repositum.tuwien.at/bitstream/20.500.12708/18324/1/Kjaeer%20Martin%20-%202021%20-%20Quantitative%20Analysis%20of%20MakerDAOs%20Liquidation%20System.pdf

Research Pulse #29 is out and it is packed with interesting publications!

In “Act natural!”: Having a Private Chat on a Public Blockchain, the authors provide an elegant scheme for a private messaging application built on public blockchains. Private avenues of communication are an essential tool to empower human sovereignty, but most existing approaches are centralized and carry critical drawbacks. The construct shown in the paper is interesting as it simply relies on ECDSA (and variants) to encode messages on the chain.

The field of Machine Learning continues to be an interesting area of research in the context of cryptonetworks. This is particularly true when it comes to address clustering and the understanding of when the pseudonymity of an entity on-chain is broken. However, the tooling for ML researchers interested in crypto is still at very early stages. In Chartalist: Labeled Graph Datasets for UTXO and Account based blockchains, the authors attempt to improve this field by providing pre-built & open-source tools to make such analyses easier on UTXO and account-based blockchains.

Finally, in Mt. Random : Multi-Tiered Randomness Beacons, the authors provide a rigorous review of the various sources of randomness used in crypto protocols, which are arguably one of the most critical primitives when it comes to security. Consensus systems, for example, depend upon sufficiently random leader selection to remain secure. Similarly, the security of any process that requires the generation of seeds and key pairs is only as good as the randomness source utilized. Beyond an interesting evaluation of the randomness sources employed today, this paper also provides an interesting construct for a multi-tiered source of randomness that can be used by crypto networks to improve their security.

2 Likes