Research Pulse Issue #32 09/27/21

  1. Not So Slowth: Invertible VDF for Ethereum and others
    Authors: Dmitry Khovratovich, Mary Maller, and Pratyush Ranjan Tiwari

Many distributed protocols benefit not only from fast but also from (guaranteed) slow computations. When we say guaranteed slow computations we mean that there is a lower bound on the time the computation takes even if one has access to an unlimited number of cores i.e. the computation cannot be parallelized. Slow computations are often required when a party is supposed to produce an output that will eventually benefit some other participants, so that the slowness of computation would guarantee unpredictability and thus fairness.
An example of this requirement in Ethereum 2.0 is the following. A group of 32 validators progressively builds a chain of collective randomness, also called a beacon chain, with one value O generated per epoch E. The value O must be computed by the leading validator of E and must depend on certain inputs produced by other validators during E. When generated, O serves as the source of entropy in other chains and thus affect a number of computations potentially beneficial to the validator. It is thus of utmost importance to ensure that O can be outputted only after a certain delay. In other words, O is derived from a verifiable delay function (VDF).
A number of VDF constructions has been proposed in the recent past [LW17, Wes19, BBBF18, Pie19] with their own advantages and limitations. The VDF Alliance seeks for a concretely-efficient post-quantum VDF which may be used by L1 projects such as Cosmos, Ethereum, Filecoin, Tezos as well as L2 applications. The post-quantumness requirement rules out the promising RSA VDF [Wes19, Pie19], but leaves open the possibility for VDFs based on verifiable computation, which are the subject of this report.


  1. Summarizing and Analyzing the Privacy-Preserving Techniques in Bitcoin and other Cryptocurrencies
    Authors: Chaitanya Rahalkar and Anushka Virgaonkar

Bitcoin and many other similar Cryptocurrencies have been in existence for over a decade, prominently focusing on decentralized, pseudo-anonymous ledger-based transactions. Many protocol improvements and changes have resulted in new variants of Cryptocurrencies that are known for their peculiar characteristics. For instance, Storjcoin is a Proof-ofStorage-based Cryptocurrency that incentivizes its peers based on the amount of storage owned by them [1]. Cryptocurrencies like Monero strive for user privacy by using privacy-centric cryptographic algorithms [2]. While Cryptocurrencies strive to maintain peer transparency by making the transactions and the entire ledger public, user privacy is compromised at times. Monero and many other privacy-centric Cryptocurrencies have significantly improved from the original Bitcoin protocol after several problems were found in the protocol. Most of these deficiencies were related to the privacy of users. Even though Bitcoin claims to have pseudo-anonymous user identities, many attacks have managed to successfully de-anonymize users. In this paper, we present some well-known attacks and analysis techniques that have compromised the privacy of Bitcoin and many other similar Cryptocurrencies. We also analyze and study different privacy-preserving algorithms and the problems these algorithms manage to solve. Lastly, we touch upon the ethics, impact, legality, and acceptance of imposing these privacy algorithms.


  1. ASIC Design for Bitcoin Mining
    Authors: Yiqiu Sun, Haichao Yang, Wentao Zhang, and Yufeng Gu

This paper first gives a brief introduction to the bitcoin and how the SHA-256 hash function is related with the bitcoin mining. We examine how the hash function is implemented on the CPU and GPU. Three ASIC designs (NaĂŻve, Novel Counter-Based, Pipeline) are then given, beating the CPU and GPU in terms of power efficiency and latency. Finally, the costs of all hardware designs are compared. The code can be found at the github repository.


  1. SMARTIAN: Enhancing Smart Contract Fuzzing with Static and Dynamic Analyses
    Authors: Jaeseung Choi, Doyeon Kim, Soomin Kim, Gustavo Grieco, Alex Groce, and Sang Kil Cha

Unlike traditional software, smart contracts have the unique organization in which a sequence of transactions shares persistent states. Unfortunately, such a characteristic makes it difficult for existing fuzzers to find out critical transaction sequences. To tackle this challenge, we employ both static and dynamic analyses for fuzzing smart contracts. First, we statically analyze smart contract bytecodes to predict which transaction sequences will lead to effective testing, and figure out if there is a certain constraint that each transaction should satisfy. Such information is then passed to the fuzzing phase and used to construct an initial seed corpus. During a fuzzing campaign, we perform a lightweight dynamic data-flow analysis to collect data-flow-based feedback to effectively guide fuzzing. We implement our ideas on a practical open-source fuzzer, named SMARTIAN. SMARTIAN can discover bugs in real-world smart contracts without the need for the source code. Our experimental results show that SMARTIAN is more effective than existing state-of-the-art tools in finding known CVEs from real-world contracts. SMARTIAN also outperforms other tools in terms of code coverage.


  1. ZKAttest: Ring and Group Signatures for existing ECDSA keys
    Authors: Armando Faz-Hernandez, Watson Ladd, and Deepak Maram

Cryptographic keys are increasingly stored in dedicated hardware or behind software interfaces. Doing so limits access, such as permitting only signing via ECDSA. This makes using them in existing ring and group signature schemes impossible as these schemes assume the ability to access the private key for other operations. We present a Σ-protocol that uses a committed public key to verify an ECDSA or Schnorr signature on a message, without revealing the public key. We then discuss how this protocol may be used to derive ring signatures in combination with Groth–Kohlweiss membership proofs and other applications. This scheme has been implemented and source code is freely available.


  1. Privacy Focused Proof of Reserves Protocols for Cryptocurrency Exchanges
    Author: Arijit Dutta

Cryptocurrency exchanges help to distribute the ownership of cryptocurrencies from the miners to other cryptocurrency users. They buy cryptocurrencies from different miners and provide their customers with various services, namely, possession of cryptocurrencies, safe-keeping the private keys in custodial wallets, and trading of cryptocurrencies. However, there is growing customer concern and distrust towards this popular business model. This is mainly because of the loss of assets by the exchanges due to fraudulent activities and the inability of the exchanges to meet the liabilities towards their customers at some particular instant of time. To regain the trust of the customers, it is proposed that the exchanges should publish periodic proofs that they own more amount of cryptocurrencies than they have sold to their customers i.e. they are solvent. It is desirable that such proof of solvency techniques (a) do not violate the privacy of the exchange, (b) are based on standard cryptographic assumptions, (c) should be publicly verifiable, and (d) need no trusted setup or involvement of a third party.
Provisions [1] is the first proof of solvency scheme proposed for Bitcoin which meets all the above criteria. To prove solvency, the scheme generates an encryption of the reserves amount and obfuscates the exchange-owned addresses in a larger anonymity set. Then the scheme gives a proof of reserves (PoR) without violating the privacy of the exchange. A PoR protocol is an integral part of a proof of solvency protocol. Unlike the remaining steps, the PoR protocol in Provisions is specific to Bitcoin and does not work for other cryptocurrencies. We have proposed the first privacy focused PoR protocols for three different cryptocurrency systems, namely, Monero, MimbleWimble, and Quisquis. Our PoR protocols enable proof of solvency schemes satisfying the above mentioned criteria. For Monero, we have proposed another PoR scheme which provides better privacy than our previous proposal. The simulation results show that all the proposed schemes are practical enough to be adopted by the exchanges in practice.


  1. SESCon: Secure Ethereum Smart Contracts by Vulnerable Patterns’ Detection
    Authors: Amir Ali, Zain Ul Abideen, and Kalim Ullah

Ethereum smart contracts have been gaining popularity toward the automation of so many domains, i.e., FinTech, IoT, and supply chain, which are based on blockchain technology. %e most critical domain, e.g., FinTech, has been targeted by so many successful attacks due to its financial worth of billions of dollars. In all attacks, the vulnerability in the source code of smart contracts is being exploited and causes the steal of millions of dollars. To find the vulnerability in the source code of smart contracts written in Solidity language, a state-of-the-art work provides a lot of solutions based on dynamic or static analysis. However, these tools have shown a lot of false positives/negatives against the smart contracts having complex logic. Furthermore, the output of these tools is not reported in a standard way with their actual vulnerability names as per standards defined by the Ethereum community. To solve these problems, we have introduced a static analysis tool, SESCon (secure Ethereum smart contract), applying the taint analysis techniques with XPath queries. Our tool outperforms other analyzers and detected up to 90% of the known vulnerability patterns. SESCon also reports the detected vulnerabilities with their titles, descriptions, and remediations as per defined standards by the Ethereum community. SESCon will serve as a foundation for the standardization of vulnerability detection.


  1. ZXAD: High-volume Attack Mitigation for Tor
    Authors: Akshaya Mani and Ian Goldberg

The Tor anonymity network is often abused by attackers to (anonymously) convey attack traffic. These attacks abuse Tor exit relays (i.e., the relays through which traffic exits Tor) by making it appear the attack originates there; as a result, many website operators indiscriminately block all Tor traffic (by blacklisting all exit IPs), reducing the usefulness of Tor.
Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service attacks). This suggests that a simple solution such as throttling traffic flow at the Tor exits may permit early detection of these attacks, improve overall reputation of exits, and eventually prevent blanket blocking of Tor exits. However, naïvely monitoring and throttling traffic at the Tor exits can endanger the privacy of the network’s users.
This paper introduces ZXAD (pronounced “zed-zad”), a zeroknowledge based private Tor exit abuse detection system that permits identification of otherwise unlinkable connections that are part of a high-volume attack. ZXAD does not reveal any information, apart from the fact that some user is conveying a high volume of traffic through Tor. We formally prove the correctness and security of ZXAD. We also measure two proof-of-concept implementations of our zero-knowledge proofs and show that ZXAD operates with low bandwidth and processing overheads.


  1. Bandersnatch: a fast elliptic curve built over the BLS12-381 scalar field
    Authors: Simon Masson, Antonio Sanso, and Zhenfei Zhang

In this short note, we introduce Bandersnatch, a new elliptic curve built over the BLS12-381 scalar field. The curve is equipped with an efficient endomorphism, allowing a fast scalar multiplication algorithm. Our benchmark shows that the multiplication is 42% faster, compared to another curve, called Jubjub, having similar properties. Nonetheless, Bandersnatch does not provide any performance improvement for either rank 1 constraint systems (R1CS) or multi scalar multiplications, compared to the Jubjub curve.


  1. Towards a Game-Theoretic Security Analysis of Off-Chain Protocols
    Authors: Sophie Rain, Zeta Avarikioti, Laura Kov´acs, and Matteo Maffei

Off-chain protocols constitute one of the most promising approaches to solve the inherent scalability issue of blockchain technologies. The core idea is to let parties transact on-chain only once to establish a channel between them, leveraging later on the resulting channel paths to perform arbitrarily many peer-to-peer transactions off-chain. While significant progress has been made in terms of proof techniques for offchain protocols, existing approaches do not capture the game-theoretic incentives at the core of their design, which led to overlooking significant attack vectors like the Wormhole attack in the past.
This work introduces the first game-theoretic model that is expressive enough to reason about the security of off-chain protocols. We advocate the use of Extensive Form Games – EFGs and introduce two instances of EFGs to capture security properties of the closing and the routing of the Lightning Network. Specifically, we model the closing protocol, which relies on punishment mechanisms to disincentivize the uploading on-chain of old channel states, as well as the routing protocol, thereby formally characterizing the Wormhole attack, a vulnerability that undermines the fee-based incentive mechanism underlying the Lightning Network.


  1. SMT-Based Bounded Model Checking for Solidity Smart Contracts
    Author: Kunjian Song

Apart from Bitcoin, Ethereum is another distributed ledger that uses blockchain technology. Smart contracts are autonomous programs that automatically control Ether’s transactions in the distributive environment of the Ethereum blockchain. A vulnerable smart contract allows the hackers to perform unauthorized withdraw. Since a smart contract is immutable after its deployment on the Ethereum blockchain, which does not allow the owner to fix bugs, it becomes critical to make sure the smart contract is safe prior to deployment. Solidity is the most widely used programming language to create such contracts. There is a great deal of interest from academia and industry in formal verification for Solidity smart contracts.
The SMT-Based BMC has been successfully used to verify software programs written in general programming languages. ESBMC is a state-of-the-art SMT-based bounded model checker to verify C and C++ software. This project uses ESBMC as the vehicle to explore the opportunity to apply SMT-Based BMC for Solidity verification. However, Solidity is a domain-specific language for writing smart contracts. To extend ESBMC to verify Solidity smart contract, a detailed study of syntax, semantics and grammar rules of Solidity language was conducted. Two type checking methods were proposed to convert Solidity AST into ESBMC intermediate representation: Tracker-Based Hybrid Conversion and Grammar-Based Hybrid Conversion.
The Grammar-Based Hybrid Conversion method was found to have better extendibility and maintainability. As a result, a new Solidity frontend was developed to extend ESBMC to verify Solidity smart contacts. Additionally, a test suite that contains vulnerably smart contracts was developed due to the lack of a standard benchmark for Solidity. The test results confirmed the correctness of the new Solidity frontend that enables ESBMC to verify Solidity smart contracts. ESBMC was compared with other state-of-the-art Solidity verification tools by running the same test suite against other tools. The results show that ESBMC is the only tool that successfully detected all vulnerabilities in each test case and provided the corresponding counterexamples for each type of vulnerability. The other tools are only able to reveal the vulnerabilities in the test suite partially.


  1. Adaptive Security of Multi-Party Protocols, Revisited
    Authors: Martin Hirt, Chen-Da Liu-Zhang, and Ueli Maurer

The goal of secure multi-party computation (MPC) is to allow a set of parties to perform an arbitrary computation task, where the security guarantees depend on the set of parties that are corrupted. The more parties are corrupted, the less is guaranteed, and typically the guarantees are completely lost when the number of corrupted parties exceeds a certain corruption bound. Early and also many recent protocols are only statically secure in the sense that they provide no security guarantees if the adversary is allowed to choose adaptively which parties to corrupt. Security against an adversary with such a strong capability is often called adaptive security and a significant body of literature is devoted to achieving adaptive security, which is known as a difficult problem. In particular, a main technical obstacle in this context is the so-called “commitment problem”, where the simulator is unable to consistently explain the internal state of a party with respect to its pre-corruption outputs. As a result, protocols typically resort to the use of cryptographic primitives like non-committing encryption, incurring a substantial efficiency loss. This paper provides a new, clean-slate treatment of adaptive security in MPC, exploiting the specification concept of constructive cryptography (CC). A new natural security notion, called CC-adaptive security, is proposed, which is technically weaker than standard adaptive security but nevertheless captures security against a fully adaptive adversary. Known protocol examples separating between adaptive and static security are also insecure in our notion. Moreover, our notion avoids the commitment problem and thereby the need to use non-committing or equivocal tools. We exemplify this by showing that the protocols by Cramer, Damgard and Nielsen (EUROCRYPT’01) for the honest majority setting, and (the variant without non-committing encryption) by Canetti, Lindell, Ostrovsky and Sahai (STOC’02) for the dishonest majority setting, achieve CC-adaptive security. The latter example is of special interest since all UC-adaptive protocols in the dishonest majority setting require some form of non-committing or equivocal encryption.


  1. Decentralized lending and its users: Insights from Compound
    Author: Kanis Saengchote

Decentralized finance (DeFi) has recently gained much attention and scrutiny because of its rapid growth. DeFi services replicate traditional financial services such as lending, exchange, and asset management, but they are currently unregulated, unlike their traditional counterparts. We investigate Compound – one of the earliest and largest DeFi lending protocol – to show how it works, who the users are and the potential motivations behind their uses. We find that the loan durations are short (31 days on average), borrowing rates volatile and borrowers are concerned about liquidation risk. Further analyses reveal that some loan demand may arise from leveraged investment strategies. Taken together with the tacit leverage in DeFi yield farming, further availability of on-chain lending could potentially transpire into DeFi systemic risk.


1 Like

Research Pulse Issue #33 is out!

It has been interesting to see an increase in publications focusing on technologies for Ethereum 2.0, which is scheduled to be merged with ETH1 early next year.

In Not So Slowth: Invertible VDF for Ethereum and others, authors propose a Verifiable Delay Function (VDF) that could be used by ETH2 to select block producers. Currently, ETH2’s Beacon Chain selects block producers from a set of stakers using RANDAO, a random number generator. However, ETH2 researchers aim to change this process and switch to a VDF. While there is no consensus on which VDF will be used, it is interesting to see more research on purpose-built VDFs for leader selection.

Another key change in ETH2 is the switch from the Elliptic Curve Digital Signature Algorithm to the nascent BLS (Boneh-Lynn-Shacham) signature algorithm. While the change will enable performance increases, especially when it comes to signature aggregation, it does entail a considerable development effort on tooling and standards. In Bandersnatch: a fast elliptic curve built over the BLS12-381 scalar field, authors provide some fascinating benchmarks and present a new curve for this signature algorithm.

Finally, in Summarizing and Analyzing the Privacy-Preserving Techniques in Bitcoin and other Cryptocurrencies authors provide a good overview of privacy technologies in the context of blockchains. They provide a good review of the various attacks where privacy can be broken and shed light on the open research questions in this field. Good read for those interested in this topic.