Research Pulse #65 05/16/22

  1. ROAST: Robust Asynchronous Schnorr Threshold Signatures
    Authors: Tim Ruffing, Viktoria Ronge, Elliott Jin, Jonas Schneider-Bensch, and Dominique Schröder

Bitcoin and other cryptocurrencies have recently introduced support for Schnorr signatures whose cleaner algebraic structure, as compared to ECDSA, allows for simpler and more practical constructions of highly demanded “𝑡-of-𝑛” threshold signatures. However, existing Schnorr threshold signature schemes (like their ECDSA counterparts) still fall short of the needs of real-world applications due to their assumption that the network is synchronous and due to their lack of robustness, i.e., the guarantee that 𝑡 honest signers are able to obtain a valid signature even in the presence of other malicious signers who try to disrupt the protocol. This hinders the adoption of threshold signatures in the cryptocurrency ecosystem, e.g., in second-layer protocols built on top of cryptocurrencies.
In this work, we propose ROAST, a simple wrapper that turns a given threshold signature scheme into a scheme with a robust and asynchronous signing protocol, as long as the underlying signing protocol is semi-interactive (i.e., has one preprocessing round and one actual signing round), provides identifiable aborts, and is unforgeable under concurrent signing sessions. When applied to the state-of-the-art Schnorr threshold signature scheme FROST, which fulfills these requirements, we obtain a simple, efficient, and highly practical Schnorr threshold signature scheme.

Link: https://eprint.iacr.org/2022/550.pdf

  1. Automated Test-Case Generation for Solidity Smart Contracts: the AGSolT Framework and its Evaluation
    Authors: Stefan W. Driessen, Dario Di Nucci, Geert Monsieur, Damian A. Tamburri, and Willem-Jan van den Heuvel

Blockchain and smart contract technology are novel approaches to data and code management that facilitate trusted computing by allowing for development in a distributed and decentralized manner. Testing smart contracts comes with its own set of challenges which have not yet been fully identified and explored. Although existing tools can identify and discover known vulnerabilities and their interactions on the Ethereum blockchain through random search or symbolic execution, these tools generally do not produce test suites suitable for human oracles. In this paper, we present AGSOLT (Automated Generator of Solidity Test Suites). We demonstrate its efficiency by implementing two search algorithms to automatically generate test suites for stand-alone Solidity smart contracts, taking into account some of the blockchain-specific challenges. To test AGSOLT, we compared a random search algorithm and a genetic algorithm on a set of 36 real-world smart contracts. We found that AGSOLT is capable of achieving high branch coverage with both approaches and even discovered some errors in some of the most popular Solidity smart contracts on Github.

Link: https://pure.tue.nl/ws/files/203455762/2102.08864v4.pdf

  1. Ethereum transaction tracking: Inferring evolution of transaction networks via link prediction
    Authors: Dan Lin, Jiajing Wu, Qi Xuan, and Chi K.Tse

Blockchain is an emerging technology which has attracted wide attention in recent years. As one of the blockchain applications, cryptocurrency has developed rapidly in recent years, attracting criminals to commit fraud and money laundering. Therefore, to better protect the legitimate interests of users and help formulate an effective supervision, it is necessary to track and follow transaction records on blockchain-based systems. This paper studies the problem of transaction tracking in Ethereum from a network perspective, aiming to study explainable strategies for money flow generation. We first collect the space-intensive transaction data from Ethereum blockchain and model them as temporal weighted multi-digraphs. A variety of tracking strategies considering different transaction factors (i.e., frequency and amount) are proposed, and the corresponding random-walk based link predictions method are designed for evaluation. Our method gets explainable results from the experiments, demonstrating that both transaction frequency and amount influence the generation of new transactions in Ethereum. This means when tracking the money flow among Ethereum accounts, we should pay more attention to those transaction paths having a shorter time interval and a larger amount. From these transaction features, the proposed random-walk based link prediction framework is found to be an effective method for transaction tracking. Furthermore, we show an application of transaction tracking via link prediction effectively enhance the ability to detect the suspicious accounts in Ethereum.

Link: https://www.sciencedirect.com/science/article/abs/pii/S0378437122003600

  1. He-HTLC: Revisiting Incentives in HTLC
    Authors: Sarisht Wadhwa, Jannis Stoter, Fan Zhang, and Kartik Nayak

Hashed Time-Locked Contracts (HTLCs) are a widely used primitive in blockchain systems. Unfortunately, HTLC is incentive-incompatible and is vulnerable to bribery attacks. MAD-HTLC (Oakland’21) is an elegant solution aiming to address the incentive incompatibility of HTLC.
In this paper, we show that MAD-HTLC is also incentiveincompatible. The crux of the issue is that MAD-HTLC only considers passively rational miners. We argue that such a model fails to capture active rational behaviors. We demonstrate the importance of taking actively rational behaviors into consideration by showing three novel reverse-bribery attacks against MAD-HTLC that can be implemented using Trusted Execution Environments (TEEs) or zero-knowledge proofs (ZKPs). We further show that reverse bribery can be combined with original delaying attacks to render MAD-HTLC insecure regardless of the relationship between v col and v dep. Based on the learnings from our attacks, we devise a new smart contract specification, He-HTLC, 1 that meets the HTLC specification even in the presence of actively rational miners.

Link: https://eprint.iacr.org/2022/546.pdf

  1. RANC: Reward-All Nakamoto Consensus
    Authors: Rami A. Khalil and Naranker Dulay

In this work we present Reward-All Nakamoto-Consensus (RANC), a Proof-of-Work cryptocurrency that resiliently rewards each miner with a number of coins that is directly proportional to its individual mining power, rather than to its relative share of the entire network’s mining power as done in Bitcoin. Under this approach, the security of mining in RANC achieves near-perfect incentive compatibility, and near-zero censorship susceptibility, for adversarial mining shares up to 45%, but at the cost of regression in subversiongain resilience. Moreover, mining rewards in RANC exhibit significantly lower variance for non-majority miners compared to NC, enabling dependable reward stability. Consequently, depending on the network transaction-fees, RANC improves miner’s waiting time for rewards, and incentivizes forming mining pools smaller than required in Bitcoin for equal reward stability. A detailed specification of RANC is presented, along with an evaluation of the practicality and efficiency achieved by our prototype RANC implementation.

Link: https://dl.acm.org/doi/pdf/10.1145/3477314.3507056

  1. Model checking of vulnerabilities in smart contracts: a solidity-to-CPN approach
    Authors: Ikram Garfatta, Kaïs Klai, Mohamed Graïet, and Walid Gaaloul

Despite the benefits that the Blockchain technology brings to many application fields, its adoption does not come without challenges. Smart contracts, which are at the core of 2nd generation blockchains, can often be riddled with vulnerabilities that can be exploited to attack the platform and threaten its security. It is therefore crucial for the protection of the designed systems to prove the correctness of the smart contracts to be deployed. Approaches have been proposed to detect generic vulnerabilities like reentrancy, but the results would often include false positives where the detected bug is either non existent or not exploitable. Besides, such approaches do not offer to check contract-specific properties. The work presented in this paper is situated as part of a formal approach that we have proposed in an attempt to bridge this gap. This previously outlined approach is based on the transformation of Solidity smart contracts into Coloured Petri nets, which provides the possibility to verify smart contracts with reference to properties expressed as Linear Temporal Logic (LTL) formulae. Herein we extend our previous work on mainly two levels: first, by taking into account the concept of function calls in the transformation and second, by focusing on the LTL properties that can define the correctness of a smart contract. Such properties can be specific to the control- or data-flow of the contracts being checked. They can also be used to express vulnerabilities as we showcase by proposing LTL formalizations for six vulnerabilities from the literature. We then leverage the capability of the Helena model checker to detect these vulnerabilities while discerning their exploitability, as well as check temporal-based contract-specific properties.

Link: https://dl.acm.org/doi/abs/10.1145/3477314.3507309

  1. AntMan: Interactive Zero-Knowledge Proofs with Sublinear Communication*
    Authors: Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, and Xiao Wang

Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this paper, we proposed two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency.

  1. We designed a ZK protocol that can prove B executions of any circuit C in communication O(B + |C|) field elements (with free addition gates), while the best prior work requires a communication of O(B|C|) field elements. Our protocol is enabled by a new tool called as information-theoretic polynomial authentication code, which may be of independent interest.
  2. We developed an optimized implementation of this protocol which shows high practicality. For example, with B = 2048, |C| = 220, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove 0.78 million MULT gates per second (mgps) and send one field element per gate; our protocol can prove 14 mgps (18× improvement) and send 0.0064 field elements per gate (156× improvement) under the same hardware configuration.
  3. Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit C in communication O(|C|3/4 ). This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.

Link: https://eprint.iacr.org/2022/566.pdf

3 Likes