Research Pulse #40 11/22/21

  1. SPEEDEX: A Scalable, Parallelizable, and Economically Efficient Distributed EXchange
    Authors: Geoffrey Ramseyer, Ashish Goel, and David Mazieres

SPEEDEX is a decentralized exchange (DEX) letting participants securely trade assets without giving any single party undue control over the market. SPEEDEX offers several advantages over prior DEXes. It achieves high throughput— over 100,000 transactions per second on 32-core servers, even with 70M open offers. It eliminates internal arbitrage opportunities, so that a direct trade from asset 𝐴 to 𝐵 always receives as good a price as trading through some third asset such as USD. Finally, it prevents frontrunning attacks that would otherwise increase the effective bid-ask spread for small traders. SPEEDEX’s key design insight is to use an Arrow-Debreu exchange market structure that fixes the valuation of assets for all trades in a given block of transactions. Not only does this market structure provide fairness across trades, it makes trade operations commutative and hence efficiently parallelizable.


  1. Looking for Lacunae in Bitcoin Core’s Fuzzing Efforts
    Authors: Alex Groce, Kush Jain, Rijnard van Tonder, Goutamkumar Tulajappa Kalburgi, and Claire Le Goues

Bitcoin is one of the most prominent distributed software systems in the world, and a key part of a potentially revolutionary new form of financial tool, cryptocurrency. At heart, Bitcoin exists as a set of nodes running an implementation of the Bitcoin protocol. This paper describes an effort to investigate and enhance the effectiveness of the Bitcoin Core implementation fuzzing effort. The effort initially began as a query about how to escape saturation in the fuzzing effort, but developed into a more general exploration once it was determined that saturation was largely illusory, a byproduct of the (then) fuzzing configuration. This paper reports the process and outcomes of the two-week focused effort that emerged from that initial contact between Chaincode Labs and academic researchers. That effort found no smoking guns indicating major test/fuzz weaknesses. However, it produced a large number of additional fuzz corpus entries to add to the Bitcoin QA assets, clarified some long-standing problems in OSS-Fuzz triage, increased the set of documented fuzzers used in Bitcoin Core testing, and ran the first (to our knowledge) mutation analysis of Bitcoin Core’s fuzz targets, revealing opportunities for further improvement. We contrast the Bitcoin Core transaction verification testing with that for other popular cryptocurrencies. This paper provides an overview of the challenges involved in improving testing infrastructure, processes, and documentation for a highly visible open source target system, from both the state-of-the-art research perspective and the practical engineering perspective. One major conclusion is that for well-designed fuzzing efforts, improvements to the oracle side of testing, increasing invariant checks and assertions, may be the best route to getting more out of fuzzing.


  1. Is a “Decentralized Autonomous Organization” a Panopticon?: Algorithmic governance as creating and mitigating vulnerabilities in DAOs
    Author: Kelsie Nabben

This piece explores algorithmic governance as a strength and a vulnerability in the experience of building participatory communities known as “Decentralized Autonomous Organizations”. The Cypherpunks were terrified of surveillance. They envisaged the combination of cryptography and computer technology fundamentally altering the nature of trust and reputation and built cryptographically secure blockchain-based infrastructure to counter this threat. Now, not just on chain transactions are being tracked but every move of participants in blockchain communities. Reputation in blockchain systems could become the new algorithmic authoritarianism if mis-used for social control. This piece analyzes the ways in which decentralization efforts can be a threat to themselves by exploring the question, ‘Are “Decentralized Autonomous Organizations” (DAOs) the next panopticon of algorithmic governance or a different panacea, and what does this mean for human autonomy in “autonomous” systems?’. By employing ethnographic methods and case study analysis, this piece provides an important qualitative contribution to the early dynamics of the aspirations and problems of decentralized, autonomous organizations.


  1. Size, Speed, and Security: An Ed25519 Case Study
    Authors: Cesar Pereida García and Sampo Sovio

Ed25519 has significant performance benefits compared to ECDSA using Weierstrass curves such as NIST P-256, therefore it is considered a state-of-the-art digital signature algorithm, specially for low performance IoT devices. However, such devices often have very limited resources and thus, implementations for these devices need to be as small and as performant as possible while being secure. In this paper we describe a scenario in which an obvious strategy to aggressively optimize an Ed25519 implementation for code size leads to a small memory footprint that is functionally correct but vulnerable to side-channel attacks. This strategy serves as an example of aggressive optimizations that might be considered by cryptography engineers, developers, and practitioners unfamiliar with the power of Side-Channel Analysis (SCA). As a solution to the flawed implementation example, we use a computer-aided cryptography tool generating formally verified finite field arithmetic to generate two secure Ed25519 implementations fulfilling different size requirements. After benchmarking and comparing these implementations to other widely used implementations our results show that computer-aided cryptography is capable of generating competitive code in terms of security, speed, and size.

Link: Size, Speed, and Security: An Ed25519 Case Study | SpringerLink

  1. DEVA: Decentralized, Verifiable Secure Aggregation for Privacy-Preserving Learning
    Authors: Georgia Tsaloli, Bei Liang, Carlo Brunetta, Gustavo Banegas, and Aikaterini Mitrokotsa

Aggregating data from multiple sources is often required in multiple applications. In this paper, we introduce DEVA, a protocol that allows a distributed set of servers to perform secure and verifiable aggregation of multiple users’ secret data, while no communication between the users occurs. DEVA computes the sum of the users’ input and provides public verifiability, i.e., anyone can be convinced about the correctness of the aggregated sum computed from a threshold amount of servers. A direct application of the DEVA protocol is its employment in the machine learning setting, where the aggregation of multiple users’ parameters (used in the learning model), can be orchestrated by multiple servers, contrary to centralized solutions that rely on a single server. We prove the security and verifiability of the proposed protocol and evaluate its performance for the execution time and bandwidth, the verification execution, the communication cost, and the total bandwidth usage of the protocol. We compare our findings to the prior work, concluding that DEVA requires less communication cost for a big amount of users.


  1. Application of Cluster Analysis in Bitcoin Deanonymization
    Author: Meng Li

Bitcoin is the world’s first decentralized cryptocurrency whose transactions are recorded on a distributed, openly accessible ledger. On the Bitcoin Blockchain, an entity’s real-world identity is hidden behind a pseudonym, a so-called address.Therefore, Bitcoin is widely assumed to provide a high degree of anonymity, which is a driver for its frequent use for illicit activities.
Some criminal activities that use Bitcoin as an intermediary are becoming more rampant, and it is difficult for law enforcement agencies to identify and track them. In order to identify the identity behind the Bitcoin address and realize the supervision of the blockchain, this paper propose to give a review of the most used Bitcoin clustering algorithms. The research is divided into two categories: One is the Transaction-based heuristic method for static address information; The other is classic clustering algorithms for dynamic behavior patterns, so as to achieve the purpose of de-anonymization of Bitcoin.

Link: Application of Cluster Analysis in Bitcoin Deanonymization | SpringerLink

  1. Revisiting Nakamoto Consensus in Asynchronous Networks: A Comprehensive Analysis of Bitcoin Safety and ChainQuality
    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,! rst 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 non-uniform block propagation pattern among the mining nodes showing that the Bitcoin network is asynchronous in practice.
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 pre!x and chain quality properties. We also propose the attack countermeasures by tweaking Bitcoin Core to model 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. SyncAttack: Double-spending in Bitcoin Without Mining Power
    Authors: Muhammad Saad, Songqing Chen, and David Mohaisen

The existing Bitcoin security research has mainly followed the security models in [22, 35], which stipulate that an adversary controls some mining power in order to violate the blockchain consistency property (i.e., through a double-spend attack). These models, however, largely overlooked the impact of the realistic network synchronization, which can be manipulated given the permissionless nature of the network. In this paper, we revisit the security of Bitcoin blockchain by incorporating the network synchronization into the security model and evaluating that in practice. Towards this goal, we propose the ideal functionality for the Bitcoin network synchronization and specify bounds on the network outdegree and the block propagation delay in order to preserve the consistency property. By contrasting the ideal functionality against measurements, we find deteriorating network synchronization reported by Bitnodes and a notable churn rate with 10% of the nodes arriving and departing from the network daily.
Motivated by these findings, we propose SyncAttack, an attack that allows an adversary to violate the Bitcoin blockchain consistency property and double-spend without using any mining power. Moreover, during our measurements, we discover weaknesses in Bitcoin that can be exploited to reduce the cost of SyncAttack, deanonymize Bitcoin transactions, and reduce the effective network hash rate. We also observe events that suggest malicious nodes are exploiting those weaknesses in the network. Finally, we patch those weaknesses to mitigate SyncAttack and associated risks.


  1. Complex Network Analysis of the Bitcoin Transaction Network
    Authors: Bishenghui Tao, Hong-Ning Dai, Jiajing Wu, Ivan Wang-Hei Ho, Zibin Zheng, and Chak Fong Cheang

In this brief, we conduct a complex-network analysis of the Bitcoin transaction network. In particular, we design a new sampling method, namely random walk with flying-back (RWFB), to conduct effective data sampling. We then conduct a comprehensive analysis of the Bitcoin network in terms of the degree distribution, clustering coefficient, the shortest-path length, connected component, centrality, assortativity, and the rich-club coefficient. We obtain several important observations including the small-world phenomenon, multi-center status, preferential attachment, and non-rich-club effect of the current network. This work brings up an in-depth understanding of the current Bitcoin blockchain network and offers implications for future directions in malicious activity and fraud detection in cryptocurrency blockchain networks.


  1. On the Implementation of Access Control in Ethereum Blockchain
    Authors: Insaf Achour, Samiha Ayed, and Hanen Idoudi

Access control is a main component in Blockchain systems. It is usually implemented in smart contracts and defines the security policy, in other words, it determines who can access a protected resource in the network. In this paper, we present a review of the major implementations of access control in Ethereum platform. The latter is based on RBAC model (Role-Based Access Control). Implementations require to take into account the whole RBAC process, that is, user role assignment and permission assignment. Three implementations currently exist and are described and compared in this work according to several features: RBAC-SC, Smart policies and OpenZepplin contracts.

Link: On the Implementation of Access Control in Ethereum Blockchain | IEEE Conference Publication | IEEE Xplore

  1. DETER: Denial of Ethereum Txpool sERvices
    Authors: Kai Li, Yibo Wang, and Yuzhe Tang

On an Ethereum node, txpool (a.k.a. mempool) is a buffer storing unconfirmed transactions and controls what downstream services can see, such as mining and transaction propagation. This work presents the first security study on Ethereum txpool designs. We discover flawed transaction handling in all known Ethereum clients (e.g., Geth), and by exploiting it, design a series of low-cost denial-of-service attacks named DETER. A DETER attacker can disable a remote Ethereum node’s txpool and deny the critical downstream services in mining, transaction propagation, Gas station, etc. By design, DETER attacks incur zero or low Ether cost. The attack can be amplified to cause global disruption to an Ethereum network by targeting centralized network services there (e.g., mining pools and transaction relay services). By evaluating local nodes, we verify the effectiveness and low cost of DETER attacks on all known Ethereum clients and in major testnets. We design non-trivial measurement methods against blackbox mainnet nodes and conduct light probes to confirm that popular mainnet services are exploitable under DETER attacks.
We propose mitigation schemes that reduce a DETER attack’s success rate down to zero while preserving the miners’ revenue.


  1. A Family of Multi-Asset Automated Market Makers
    Authors: Eric Forgy and Leo Liu

We present a family of multi-asset automated market makers whose liquidity curves are derived from the financial principles of self financing transactions and rebalancing. The constant product market maker emerges as a special case.


  1. Disentangling Decentralized Finance (DeFi) Compositions
    Authors: Stefan Kitzler, Friedhelm Victor, Pietro Saggese, and Bernhard Haslhofer

We present the first study on compositions of Decentralized Finance (DeFi) protocols, which aim to disrupt traditional finance and offer financial services on top of the distributed ledgers, such as the Ethereum. Starting from a ground-truth of 23 DeFi protocols and 10,663,881 associated accounts, we study the interactions of DeFi protocols and associated smart contracts from a macroscopic perspective. We find that DEX and lending protocols have a high degree centrality, that interactions among protocols primarily occur in a strongly connected component, and that known community detection cannot disentangle DeFi protocols. Therefore, we propose an algorithm for extracting the building blocks and uncovering the compositions of DeFi protocols. We apply the algorithm and conduct an empirical analysis finding that swaps are the most frequent building blocks and that DeFi aggregation protocols utilize functions of many other DeFi protocols. Overall, our results and methods contribute to a better understanding of a new family of financial products and could play an essential role in assessing systemic risks if DeFi continues to proliferate.



Research Pulse #40 is out!

In SPEEDEX: A Scalable, Parallelizable, and Economically Efficient Distributed EXchange, authors propose a new architecture for a decentralized exchange. SPEEDEX claims to iterate upon existing DEXes through the use of the Arrow-Debreu exchange market structure. It also aims to improve upon scalability issues by targeting a throughput of over 100,000 transactions per second on 32-core servers.

In Is a “Decentralized Autonomous Organization” a Panopticon?: Algorithmic governance as creating and mitigating vulnerabilities in DAOs, the author provides an honest perspective of the merits and challenges of using Decentralized Autonomous Organizations in a pseudonymous environment.

Finally, in Disentangling Decentralized Finance (DeFi) Compositions, authors evaluate composability in DeFi applications. This is done through the analysis of the actors simultaneously interacting with multiple DeFi protocols. Interestingly, the authors find that “DEX and lending protocols have a high degree centrality, that interactions among protocols primarily occur in a strongly connected component, and that known community detection cannot disentangle DeFi protocols.”