Research Pulse Issue #41 11/29/21

  1. Understanding Security Issues in the NFT Ecosystem
    Authors: Dipanjan Das, Priyanka Bose, Nicola Ruaro, Christopher Kruegel, and Giovanni Vigna

Non-Fungible Tokens (NFTs) have emerged as a way to collect digital art as well as an investment vehicle. Despite having been popularized only recently, over the last year, NFT markets have witnessed several high-profile (and high-value) asset sales and a tremendous growth in trading volumes. However, these marketplaces have not yet received much scrutiny. Most academic researchers have analyzed decentralized finance (DeFi) protocols, studied attacks on those protocols, and developed automated techniques to detect smart contract vulnerabilities. To the best of our knowledge, we are the first to study the market dynamics and security issues of the multi-billion dollar NFT ecosystem. In this paper, we first present a systematic overview of how the NFT ecosystem works, and we identify three major actors: marketplaces, external entities, and users. We study the design of the underlying protocols of the top 8 marketplaces (ranked by transaction volume) and discover security, privacy, and usability issues. Many of these issues can lead to substantial financial losses. During our analysis, we reported 5 security bugs in 3 top marketplaces; all of them have been confirmed by the affected parties. Moreover, we provide insights on how the entities external to the blockchain are able to interfere with NFT markets, leading to serious consequences. We also collect a large amount of asset and event data pertaining to the NFTs being traded in the examined marketplaces, and we quantify malicious trading behaviors carried out by users under the cloak of anonymity. Finally, we studied the 15 most expensive NFT sales to date, and discovered discrepancies in at least half of these transactions.


  1. Estimating the Effectiveness of Lattice Attacks
    Authors: Kotaro Abe and Makoto Ikeda

Lattice attacks are threats to (EC)DSA and have been used in cryptanalysis. In lattice attacks, a few bits of nonce leaks in multiple signatures are sufficient to recover the secret key. Currently, the BKZ algorithm is frequently used as a lattice reduction algorithm for lattice attacks, and there are many reports on the conditions for successful attacks. However, experimental attacks using the BKZ algorithm have only shown results for specific key lengths, and it is not clear how the conditions change as the key length changes. In this study, we conducted some experiments to simulate lattice attacks on P256, P384, and P521 and confirmed that attacks on P256 with 3 bits nonce leak, P384 with 4 bits nonce leak, and P521 with 5 bits nonce leak are feasible. The result for P521 is a new record. We also investigated in detail the reasons for the failure of the attacks and proposed a model to estimate the feasibility of lattice attacks using the BKZ algorithm. We believe that this model can be used to estimate the effectiveness of lattice attacks when the key length is changed.


  1. A theory of transaction parallelism in blockchains
    Authors: Massimo Bartoletti, Letterio Galletta, And Maurizio Murgia

Decentralized blockchain platforms have enabled the secure exchange of cryptoassets without the intermediation of trusted authorities. To this purpose, these platforms rely on a peer-to-peer network of byzantine nodes, which collaboratively maintain an append-only ledger of transactions, called blockchain. Transactions represent the actions required by users, e.g. the transfer of some units of crypto-currency to another user, or the execution of a smart contract which distributes crypto-assets according to its internal logic. Part of the nodes of the peer-to-peer network compete to append transactions to the blockchain. To do so, they group the transactions sent by users into blocks, and update their view of the blockchain state by executing these transactions in the chosen order. Once a block of transactions is appended to the blockchain, the other nodes validate it, re-executing the transactions in the same order. The serial execution of transactions does not take advantage of the multi-core architecture of modern processors, so contributing to limit the throughput. In this paper we develop a theory of transaction parallelism for blockchains, which is based on static analysis of transactions and smart contracts. We illustrate how blockchain nodes can use our theory to parallelize the execution of transactions. Initial experiments on Ethereum show that our technique can improve the performance of nodes.


  1. Clarion: Anonymous Communication from Multiparty Shuffling Protocols
    Authors: Saba Eskandarian and Dan Boneh

This paper studies the role of multiparty shuffling protocols in enabling more efficient metadatahiding communication. We show that the process of shuffling messages can be expedited by having servers collaboratively shuffle and verify secret-shares of messages instead of using a conventional mixnet approach where servers take turns performing independent verifiable shuffles of user messages. We apply this technique to achieve both practical and asymptotic improvements in anonymous broadcast and messaging systems. We first show how to build a three server anonymous broadcast scheme, secure against one malicious server, that relies only on symmetric cryptography. Next, we adapt our three server broadcast scheme to a k-server scheme secure against k − 1 malicious servers, at the cost of a more expensive per-shuffle preprocessing phase. Finally, we show how our scheme can be used to significantly improve the performance of the MCMix anonymous messaging system. We implement our shuffling protocol in a system called Clarion and find that it outperforms a mixnet made up of a sequence of verifiable (single-server) shuffles by 9.2× for broadcasting small messages and outperforms the MCMix conversation protocol by 11.8×.


  1. Route Discovery in Private Payment Channel Networks
    Authors: Zeta Avarikioti, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof Pietrzak, Jakub Svoboda, and Michelle Yeo.

In this work, we are the first to explore route discovery in private channel networks. We first determine what “ideal” privacy for a routing protocol means in this setting. We observe that protocols achieving this strong privacy definition exist by leveraging (topology hiding) Multi-Party Computation but they are (inherently) inefficient as route discovery must involve the entire network. We then present protocols with weaker privacy guarantees but much better efficiency. In particular, route discovery typically only involves small fraction of the nodes but some information on the topology and balances – beyond what is necessary for performing the transaction – is leaked. The core idea is that both sender and receiver gossip a message which then slowly propagates through the network, and the moment any node in the network receives both messages, a path is found. In our first protocol the message is always sent to all neighbouring nodes with a delay proportional to the fees of that edge. In our second protocol the message is only sent to one neighbour chosen randomly with a probability proportional to its degree. While the first instantiation always finds the cheapest path, the second might not, but it involves a smaller fraction of the network. We also discuss some extensions to further improve privacy by employing bilinear maps. Simulations of our protocols on the Lightning network topology (for random transactions and uniform fees) show that our first protocol (which finds the cheapest path) typically involves around 12% of the 6376 nodes, while the second only touches around 18 nodes (< 0.3%), and the cost of the path that is found is around twice the cost of the optimal one.


  1. Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets
    Authors: Alex Ozdemir and Dan Boneh

A zk-SNARK is a powerful cryptographic primitive that provides a succinct and efficiently checkable argument that the prover has a witness to a public NP statement, without revealing the witness. However, in their native form, zk-SNARKs only apply to a secret witness held by a single party. In practice, a collection of parties often need to a prove a statement where the secret witness is distributed or shared among them. We implement and experiment with collaborative zkSNARKs: proofs over the secrets of multiple, mutually distrusting parties. We construct these by lifting conventional zk-SNARKs into secure protocols among N provers to jointly produce a single proof over the distributed witness. We optimize the proof generation algorithm in pairing-based zkSNARKs so that algebraic techniques for multiparty computation (MPC) yield efficient proof generation protocols. For some zk-SNARKs, optimization is more challenging. This suggests MPC “friendliness” as an additional criterion for evaluating zk-SNARKs. We implement 3 collaborative proofs and evaluate the concrete cost of proof generation. We find that over a good network, security against a malicious minority of provers can be achieved with approximately the same runtime as a single prover. Security against N −1 malicious provers requires only a 2× slowdown. This efficiency is unusual: most computations slow down by several orders of magnitude when securely distributed. It is also significant: most server-side applications that can tolerate the cost of a single-prover proof should also be able to tolerate the cost of a collaborative proof.


  1. REBAL: Channel Balancing for Payment Channel Networks
    Authors: Nitin Awathare; Suraj; Akash; Vinay Joseph Ribeiro; Umesh Bellur

Cryptocurrency networks are a promising infrastructure for pseudonymous online payments. However, low throughput has prevented their widespread acceptance. A promising solution to scale throughput is the Payment channel network (PCN), exemplified by the Lightning Network (LN), that uses a network of off-chain bidirectional payment channels between parties that wish to transact often. Since payments use the shortest paths with sufficient funds over this network, channel balances get exhausted in the direction transactions flow and eventually become unidirectional. This results in transactions failing and consequently a lower transaction success ratio. Our observations on the production LN show that over 63% of the channels lose over 80% of the channel balance in one direction over time, which makes the success ratio of a real-world workload drop from 71% to 29%. A unidirectional channel along a path results in a failure message back to the source that recomputes the path, excluding the failed channel and reattempts the transaction, thus adding to the completion latency even for those transactions that do complete.We propose REBAL, a distributed re-balancing mechanism, and a new routing scheme to address the above issues. REBAL maximizes the extent to which channels can be re-balanced across the entire network. REBAL addresses the completion latency issue by re-routing transactions from intermediate nodes around a unidirectional channel rather than propagating the failure back to the source.Our comprehensive evaluation of REBAL shows that the success ratio improves from 30.18% to 79.54% and success volume from 3.98% to 29.99% for a real-world workload derived from the Ripple network, without adversely impacting the transaction latency. Even at very high transaction rates, REBAL outperforms Lightning Network Daemon (LND- a Golang implementation of LN) (12%) with a success ratio of 43.76%.

Link: REBAL: Channel Balancing for Payment Channel Networks | IEEE Conference Publication | IEEE Xplore

  1. A Voting-Based Blockchain Interoperability Oracle
    Authors: Michael Sober, Giulia Scaffino, Christof Spanring, Stefan Schulte

Today’s blockchain landscape is severely fragmented as more and more heterogeneous blockchain platforms have been developed in recent years. These blockchain platforms are not able to interact with each other or with the outside world since only little emphasis is placed on the interoperability between them. Already proposed solutions for blockchain interoperability such as naive relay or oracle solutions are usually not broadly applicable since they are either too expensive to operate or very resource-intensive. For that reason, we propose a blockchain interoperability oracle that follows a voting-based approach based on threshold signatures. The oracle nodes generate a distributed private key to execute an off-chain aggregation mechanism to collectively respond to requests. Compared to state-of-the-art relay schemes, our approach does not incur any ongoing costs and since the on-chain component only needs to verify a single signature, we can achieve remarkable cost savings compared to conventional oracle solutions.



Research Pulse Issue 41 is out!

In Understanding Security Issues in the NFT Ecosystem, the authors provide an interesting evaluation of the security issues surrounding the nascent, multi-billion-dollar NFT market. Specifically, they provide critical insights on how the entities external to the blockchain are able to interfere with NFT markets, leading to serious consequences. They also evaluate the top NFT sales to date and highlight some unusual behaviors in those events.

In A theory of transaction parallelism in blockchains, the authors evaluate blockchain transactional performance and propose a model to reason about potential increases in throughput. They highlight the fact that the serial execution of transactions does not take advantage of the multi-core architecture of modern processors, and pose this as a limiting factor to blockchain scalability.

Finally, in Route Discovery in Private Payment Channel Networks, the authors propose a mechanism to increase the efficiency of private channels in the Lightning Network. The mechanism’s core idea is a delay system where both sender and receiver gossip a message which then slowly propagates through the network, and the moment any node in the network receives both messages, a path is found.