Research Pulse Issue #22 07/19/21

  1. The Dissensus Protocol: Governing Differences in Online Peer Communities
    Authors: Jaya Klara Brekke, Kate Beecroft, and Francesca Pick

Peer-to-peer networks and protocols have inspired new ideas and ideologies about governance, with the aim of using technology to enable horizontal and decentralized decision-making at scale. This article introduces the concept of “dissensus” from political theory to debates about peer governance in online communities. Dissensus describes the emergence of incompatible differences. Among peer-to-peer technologies, blockchain stands out as a set of ideas that explicitly seek to resolve dissensus through consensus protocols. In this article, we propose dissensus as a “protocol” for foregrounding the often sidelined yet productive aspects of incompatible differences. The concept highlights that there might not always be consensus about a consensus algorithm, and that indeed, dissensus is the precondition for new possibilities and perspectives to emerge. We discuss the concept in relation to the histories of governance ideas in blockchain, namely, a “materialist,” “design,” and “emergent” approach. We then describe moments of dissensus in practice through two cases of online communities, Genesis DAO and Ouishare, discussing their different ways of recognizing and navigating dissensus. Finally, we give a critical overview of consensus algorithms, voting, staking, and forking as the mechanisms that make out blockchain governance ideologies. In conclusion, we argue that dissensus can serve as a useful concept for pointing attention to governance as it is conducted in practice, as historically and culturally specific practices, rather than as a problem to be solved through supposedly universal mechanisms.

Link: Redirect Notice

  1. HERMES: Scalable, Secure, and Privacy-Enhancing Vehicular Sharing-Access System
    Authors: Iraklis Symeonidis, Dragos Rotaru, Mustafa A. Mustafa, Bart Mennink, Bart Preneel, and Panos Papadimitratos

We propose , a scalable, secure, and privacy-enhancing system for users to share and access vehicles. securely outsources operations of vehicle access token generation to a set of untrusted servers. It builds on an earlier proposal, namely DBLP:conf/esorics/SymeonidisAMMDP17, and extends the system design for improved efficiency and scalability. To cater to system and user needs for secure and private computations, utilizes and combines several cryptographic primitives with secure multiparty computation efficiently. It conceals secret keys of vehicles and transaction details from the servers, including vehicle booking details, access token information, and user and vehicle identities. It also provides user accountability in case of disputes. Besides, we provide semantic security analysis and prove that meets its security and privacy requirements. Last but not least, we demonstrate that is efficient and, in contrast to , scales to a large number of users and vehicles, making it practical for real-world deployments. We build our evaluations with two different multiparty computation protocols: HtMAC-MiMC and CBC-MAC-AES. Our results demonstrate that is in the range of milliseconds for generating an access token, whether it operates for a single-vehicle owner or a large rental-company branch with over 1000 vehicles; handling 546 and 84 access token generations per second, respectively. As a result, is an order of magnitude faster compared to . Specifically, it delivers 696 (with HtMAC-MiMC) and 42 (with CBC-MAC-AES) more access tokens compared to in for a single-vehicle owner access token generation. Furthermore, we show that is practical on the vehicle side, too, as access token operations performed on a prototype vehicle on-board unit take only ≈62 ms.

Link: HERMES: Scalable, Secure, and Privacy-Enhancing Vehicular Sharing-Access System | IEEE Journals & Magazine | IEEE Xplore

  1. echidna-parade: a tool for diverse multicore smart contract fuzzing
    Authors: Alex Groce and Gustavo Grieco

Echidna is a widely used fuzzer for Ethereum Virtual Machine (EVM) compatible blockchain smart contracts that generates transaction sequences of calls to smart contracts. While Echidna is an essentially single-threaded tool, it is possible for multiple Echidna processes to communicate by use of a shared transaction sequence corpus. Echidna provides a very large variety of configuration options, since each smart contract may be best-tested by a non-default configuration, and different faults or coverage targets within a single contract may also have differing ideal configurations. This paper presents echidna-parade, a tool that provides pushbutton multicore fuzzing using Echidna as an underlying fuzzing engine, and automatically provides sophisticated diversification of configurations. Even without using multiple cores, echidna-parade can improve the effectiveness of fuzzing with Echidna, due to the advantages provided by multiple types of test configuration diversity. Using echidna-parade with multiple cores can produce significantly better results than Echidna, in less time.


  1. SECDSA: Mobile signing and authentication under classical “sole control”?
    Author: Eric R. Verheul

The 2014 European eIDAS regulation regulates strong electronic authentication and legally binding electronic signatures. Both require user “sole control”. Historically smartcards are used based on direct interaction between user and relying party. Here sole control is provided by giving users both physical possession and control of the cryptographic key used for signing/authentication through a PIN. Such classical sole control is required in the 1999 electronic signature directive by some interpretations. The eIDAS regulation repeals the directive and explicitly relaxes its sole control requirements in a trade-off between security and usability. This allows user interaction to be outsourced to intermediary parties (authentication providers, signing services). This also allows mobile applications as user friendly alternatives for smartcards. However, current mobile platforms are only equipped with limited cryptographic hardware not supporting secure knowledge factors (PINs) controlling keys. The eIDAS relaxation raises concerns on sole control; intermediary parties should not be able to act as man-in-the-middle and impersonate users. In this paper we present a simple cryptographic design for signing and authentication on standard mobile platforms providing classical sole control. We argue that our design can meet the highest eIDAS requirements, effectively introducing a new signature category in a 2016 decision of the European Commission. We also sketch a SECDSA based implementation of the European Digital Identity Wallet recently proposed by the European Commission as part of the eIDAS regulation update.


  1. Empirical Evaluation of MakerDAO’s Resilience
    Author: Martin Kjäer, Monika di Angelo, and Gernot Salzer

Stablecoins are cryptocurrencies with the aim to reduce the price volatility by design. This increases their acceptance as an instrument of payment. Centralized approaches facilitate stable organizational structures, at the cost of introducing dependencies. Decentralized projects, on the other hand, face several challenges, one of them at the core of stablecoins: stability.
In this paper, we assess the stability of the MakerDAO protocol, one of the major decentralized stablecoins. We conduct a measurement study regarding MakerDAO’s resilience during the first year of its full protocol, from November 2019 to 2020, including the cryptocurrency crisis in March 2020. Our analysis is based on the publicly available transaction data of Ethereum that documents the activities of MakerDAO’s contracts executing the protocol. We state requirements for resilience and introduce empirical metrics, based on which we test the resilience hypotheses against the transaction data. While the events of March 2020 were unfortunate for several users, the resilience at protocol level proved to be good even under stress.


  1. Revisiting Nakamoto Consensus in Asynchronous Networks: A Comprehensive Analysis of Bitcoin Safety and Chain Quality
    Authors: Muhammad Saad, Afsah Anwar, Srivatsan Ravi, and David Mohaisen

The Bitcoin blockchain safety relies on strong network synchrony. Therefore, violating the blockchain safety requires strong adversaries that control a mining pool with ≈51% hash rate. In this paper, we show that the network synchrony does not hold in the real world Bitcoin network which can be exploited to lower the cost of various attacks that violate the blockchain safety and chain quality. Towards that, first we construct the Bitcoin ideal functionality to formally specify its ideal execution model in a synchronous network. We then develop a large-scale data collection system through which we connect with more than 36K IP addresses of the Bitcoin nodes and identify 359 mining nodes. We contrast the ideal functionality against the real world measurements to expose the network anomalies that can be exploited to optimize the existing attacks. Particularly, we observe a weak network synchronization in Bitcoin: on average, in 9.97 minutes, only 39% nodes have the upto-date blockchain. Through a fine-grained analysis, we discover non-uniform block propagation delay among the mining nodes showing that the Bitcoin network is asynchronous.
To realize the threat of an asynchronous network, we present the HashSplit attack that allows an adversary to orchestrate concurrent mining on multiple branches of the blockchain to violate common prefix and chain quality properties. We also propose the attack countermeasures by releasing a Bitcoin Core version that models the Bitcoin ideal functionality. Our measurements, theoretical modeling, proposed attack, and countermeasures open new directions in the security evaluation of Bitcoin and similar blockchain systems.


  1. Blockchain Based Unified Authentication with Zero-knowledge Proof in Heterogeneous MEC*
    Authors: Wanxue Lin, Xuefei Zhang, Qimei Cui, and Zhiwei Zhang

The next generation wireless network will be a heterogeneous network with multiple access networks, and Mobile Edge Computation (MEC) is oriented to heterogeneous users with various security authentication mechanisms. However, compared to the central servers, the lightweight and the limited computing power make MEC servers hard to support multiple security authentication mechanisms at the same time. To resolve this issue, this paper introduces a blockchain based unified authentication with Zero-knowledge Proof (ZPB authentication) system. Blockchain is adopted to recorder the authentication results, so there is no need to perform secondary authentication in HetNet handoff. A non-interactive Schnorr Zero-knowledge Proof scheme is used to avoid privacy issues caused by blockchain, and it can calculate parameters in advance to reduce real-time overhead of MEC. At the same time, the mechanism of anonymous code updating periodically also makes the system more secure. Through performance analysis and simulation, it can be seen that the authentication system proposed in this paper can achieve both security and effectiveness, and is suitable for HetNet access authentication in MEC scenario.

Link: Blockchain Based Unified Authentication with Zero-knowledge Proof in Heterogeneous MEC* | IEEE Conference Publication | IEEE Xplore

  1. T-Auth: A Novel Authentication Mechanism for the IoT Based on Smart Contracts and PUFs [Paywalled]
    Authors: Wun-Cing Liou and Tsungnan Lin

In recent years, the number of Internet-of-Things (IoT) devices has grown at an explosive rate. With the dramatic surge of the IoT, security issues have also come to the fore. Consequently, ensuring the security of the IoT communication community environment and trust between entities have become important research topics. In this paper, we design a passwordless IoT authentication mechanism, namely, T-Auth, to address these issues. The identity of a device in T-Auth is based on physical unclonable functions (PUFs), a hardware-based device fingerprint technology, which can greatly improve the security level compared to hardcoded passwords. A smart contract is a program that runs on the blockchain, which provides design flexibility and operational reliability. Our mechanism establishes a new trust architecture that enables devices to exchange information securely and reliably. The main contribution of this paper is to propose a new authentication mechanism that utilizes PUFs and combines them with blockchain to greatly improve the security and reliability of a system. Additionally, by leveraging Ethereum smart contracts, our mechanism supports cross-service group authentication.

Link: T-Auth: A Novel Authentication Mechanism for the IoT Based on Smart Contracts and PUFs | IEEE Conference Publication | IEEE Xplore

  1. Evolution of Ethereum Transaction Relationships: Toward Understanding Global Driving Factors From Microscopic Patterns
    Authors: Dan Lin, Jialan Chen, Jiajing Wu, and Zibin Zheng

Much of the current research in Ethereum transaction records focuses on the statistical analysis and measurements of existing data; however, the evolution mechanism of Ethereum transactions is an important, yet seldom discussed issue. In this work, we first collect the transaction data of Ethereum and build network models from a microlevel view and then use a link-prediction-based framework to quantify the impact of network characteristics on Ethereum evolution. Next, we explore the graph structure properties and the driving factors of newly generated transaction relationships. Experimental results show that the local and microscopic structure of Ethereum networks is star-shaped, and the transaction frequency of addresses has a great impact on the evolution of Ethereum transaction relationships. First-layer nodes of microstructures dominate the network evolution. Moreover, the degree of addresses is an effective basis for predicting the direction of new transactions. Potential further studies on Ethereum transaction link prediction are discussed, for example, the label effect of center addresses.

Link: Evolution of Ethereum Transaction Relationships: Toward Understanding Global Driving Factors From Microscopic Patterns | IEEE Journals & Magazine | IEEE Xplore

  1. Resurrecting Address Clustering in Bitcoin
    Authors: Malte Möser and Arvind Narayanan

Blockchain analysis is essential for understanding how cryptocurrencies like Bitcoin are used in practice, and address clustering is a cornerstone of blockchain analysis. However, current techniques rely on heuristics that have not been rigorously evaluated or optimized. In this paper, we tackle several challenges of change address identification and clustering. First, we build a ground truth set of transactions with known change from the Bitcoin blockchain that can be used to validate the efficacy of individual change address detection heuristics. Equipped with this data set, we develop new techniques to predict change outputs with low false positive rates. After applying our prediction model to the Bitcoin blockchain, we analyze the resulting clustering and develop ways to detect and prevent cluster collapse. Finally, we assess the impact our enhanced clustering has on two exemplary applications.


  1. Mithril: Stake-based Threshold Multisignatures
    Authors: Pyrros Chaidos and Aggelos Kiayias

Stake-based multiparty cryptographic primitives operate in a setting where participants are associated with their stake, security is argued against an adversary that is bounded by the total stake it possesses —as opposed to number of parties— and we are interested in scalability, i.e., the complexity of critical operations depends only logarithmically in the number of participants (that are assumed to be numerous). In this work we put forth a new stake-based primitive, stake-based threshold multisignatures (STM, or “Mithril” signatures), which allows the aggregation of individual signatures into a compact multisignature provided the stake that supports a given message exceeds a stake threshold. This is achieved by having for each message a pseudorandomly sampled subset of participants eligible to issue an individual signature; this ensures the scalability of signing, aggregation and verification. We formalize the primitive in the universal composition setting and propose efficient constructions for STMs. We also showcase that STMs are eminently useful in the cryptocurrency setting by providing two applications: (i) stakeholder decision-making for Proof of Work (PoW) blockchains, specifically, Bitcoin, and (ii) fast bootstrapping for Proof of Stake (PoS) blockchains.


  1. Optimally Reliable & Cheap Payment Flows on the Lightning Network
    Authors: Rene Pickhardt & Stefan Richter

Today, payment paths in Bitcoin’s Lightning Network are found by searching for shortest paths on the fee graph. We enhance this approach in two dimensions. Firstly, we take into account the probability of a payment actually being possible due to the unknown balance distributions in the channels. Secondly, we use minimum cost flows as a proper generalization of shortest paths to multi-part payments (MPP).
In particular we show that under plausible assumptions about the balance distributions we can find the most likely MPP for any given set of senders, recipients and amounts by solving for a (generalized) integer minimum cost flow with a separable and convex cost function. Polynomial time exact algorithms as well as approximations are known for this optimization problem.
We present a round-based algorithm of min-cost flow computations for delivering large payment amounts over the Lightning Network. This algorithm works by updating the probability distributions with the information gained from both successful and unsuccessful paths on prior rounds. In all our experiments a single digit number of rounds sufficed to deliver payments of sizes that were close to the total local balance of the sender. Early experiments indicate that our approach increases the size of payments that can be reliably delivered by several orders of magnitude compared to the current state of the art.
We observe that finding the cheapest multi-part payments is an NP-hard problem considering the current fee structure and propose dropping the base fee to make it a linear min-cost flow problem. Finally, we discuss possibilities for maximizing the probability while at the same time minimizing the fees of a flow. While this turns out to be a hard problem in general as well — even in the single path case — it appears to be surprisingly tractable in practice.



Research Pulse Issue #22 is out!

In Resurrecting Address Clustering in Bitcoin, privacy researchers Malte Möser and Arvind Narayanan provide one of the most thorough analysis of address clustering to date. For context, address clustering is a technique whereby a group of addresses can be probabilistically assigned to a wallet. It is frequently used to de-anonymize users on the blockchain and understand their behavior – especially across exchanges. The authors revisit popular heuristics for address clustering and evaluate its effectiveness.

Network nodes are the backbone of public blockchains. However, analysis of the relationship of nodes in the Peer-to-Peer network is still in very early stages. In Revisiting Nakamoto Consensus in Asynchronous Networks: A Comprehensive Analysis of Bitcoin Safety and Chain Quality, the authors provide an interesting framework to evaluate consensus performance and its impact on node synchronization (and, by extension, network security).

Finally, in The Dissensus Protocol: Governing Differences in Online Peer Communities, the authors provide a literature review of on-chain governance and DAOs. They specifically focus on events where reaching majority consensus was a contentious process and the governance structures currently being pursued. While the analysis does not focus too much on mechanism design, it is, nevertheless an interesting framework to dissect on-chain governance from a political science perspective.


The Limits of Code Deference

A paper that explores whether DAOs can bind their users through code.

Link: The Limits of Code Deference by Andrew Hinkes :: SSRN