Research Pulse Issue #12 05/07/21

  1. SnarkPack: Practical SNARK Aggregation
    Authors: Nicolas Gailly, Mary Maller, and Anca Nitulescu

We present and implement SnarkPack, an argument for aggregating n Groth16 zkSNARKs with a O(log n) proof size and verifier time. Our techniques are inspired from the inner pairing product argument introduced by Bunz et al. with the difference that our final scheme does not require a different trusted setup, but it reuses the one from the pairing-based SNARK that it aggregates.
The key tool for our SnarkPack construction is a new commitment scheme that allows us to instantiate the inner product pairing argument of Bunz et al. by using existing powers of tau ceremony transcripts. We also describe a scheme that merge together a multi-exponentiation argument and an inner pairing product argument for some common randomness vector with minimal overhead. We further apply some optimisations to our protocol and illustrate it’s efficiency by implementing it.
SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 33ms, including un-serialization time, yielding a verification mechanism that is exponentially faster than batching and previous solutions in the field.


  1. Demo Paper: Atomic Bonded Cross-chain Debt
    Authors: Amirhossein Khajehpour, Fatemeh Bagheri, and Melika Abdi

Atomic Bonded Cross-chain Debt (ABCD) is the first non-custodial smart-contract-independent cross-chain atomic bond. Theoretical aspects of ABCD have been presented in the International Conference on Blockchain Technology and Applications (ICBTA) and won the best presentation award. It is the first time a demo of Atomic Bonded Cross-chain Debt is presented.


  1. Characterizing key agents in the cryptocurrency economy through blockchain transaction analysis
    Authors: Xiao Fan Liu, Huan-Huan Ren, Si-Hao Liu, and Xian-Jian Jiang

The cryptocurrency economy provides a comprehensive digital trace of human economic behavior: almost all cryptocurrency users’ activities are faithfully recorded in transactions on public blockchains. However, the user identifiers in the transaction records, i.e., blockchain addresses, are anonymous. That is, they cannot be associated with any real “off-chain” identify of actual users. Nonetheless, identifying the economic roles of the addresses from their past behaviors is still feasible. This paper analyzes Ethereum token transactions, characterizes key economic agents’ behavior from their transaction patterns, and explores their identifiability through interpretable machine learning models. Specifically, six types of most active economic agents are considered, including centralized cryptocurrency exchanges, decentralized exchanges, cryptocurrency wallets, token issuers, airdrop services, and gaming services. Transaction patterns such as trading volume, transaction tempo, and structural properties of transaction networks are defined for individual blockchain addresses. The results showed that cryptocurrency exchanges and online wallets have signature behavior patterns and hence can be accurately distinguished from other agents. Token issuers, airdrop services, and gaming services can sometimes be confused. Moreover, transaction networks’ features provide the richest information in the economic agent’s identification.


  1. Complex Network Analysis of the Bitcoin Blockchain Network
    Authors: Bishenghui Tao, Ivan Wang-Hei Ho, and Hong-Ning Dai

In this paper, we conduct a complex-network analysis of the Bitcoin 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, the assortativity, and the rich-club coefficient. There are several important observations from the Bitcoin network, such as smallworld phenomenon and non-rich-club effect. 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.

Link: IEEE Xplore Full-Text PDF:

  1. SIGTRAN: Signature Vectors for Detecting Illicit Activities in Blockchain Transaction Networks
    Author: Farimah Poursafaei, Reihaneh Rabbany, and Zeljko Zilic

Cryptocurrency networks have evolved into multi-billion-dollar havens for a variety of disputable financial activities, including phishing, ponzi schemes, money-laundering, and ransomware. In this paper, we propose an efficient graphbased method, SIGTRAN, for detecting illicit nodes on blockchain networks. SIGTRAN first generates a graph based on the transaction records from blockchain. It then represents the nodes based on their structural and transactional characteristics. These node representations accurately differentiate nodes involved in illicit activities. SIGTRAN is generic and can be applied to records extracted from different networks. SIGTRAN achieves an F1 score of 0.92 on Bitcoin and 0.94 on Ethereum, which outperforms the state-of-the-art performance on these benchmarks obtained by much more complex, platform-dependent models.


  1. Cryptographically Strong Elliptic Curves of Prime Order
    Authors: Marcin Baranski, Rafał Gliwa, and Janusz Szmidt

The purpose of this paper is to generate cryptographically strong elliptic curves over prime fields Fp, where p is a Mersenne prime, one of the special primes or a random prime. We search for elliptic curves which orders are also prime numbers. The cryptographically strong elliptic curves are those for which the discrete logarithm problem is computationally hard. The required mathematical conditions are formulated in terms of parameters characterizing the elliptic curves. We present an algorithm to generate such curves. Examples of elliptic curves of prime order are generated with Magma.


  1. Vulnerabilities and Open Issues of Smart Contracts: A Systematic Mapping
    Author: Gabriel de Sousa Matsumura, Luciana Brasil Rebelo dos Santos, Arlindo Flavio da Conceicao, and Nandamudi Lankalapalli Vijaykumar

Smart Contracts (SCs) are programs stored in a Blockchain to ensure agreements between two or more parties. Due to the unchangeable essence of Blockchain, failures or errors in SCs become perpetual once published. The reliability of SCs is essential to avoid financial losses. So, SCs must be checked to ensure the absence of errors. Hence, many studies addressed new methods and tools for zero-bug software in SCs. This paper conducted a systematic literature mapping identifying initiatives and tools to analyze SCs and how to deal with the identified vulnerabilities. Besides, this work identifies gaps that may lead to research topics for future work.


  1. R-SWAP: Relay based atomic cross-chain swap protocol
    Authors: LĂ©onard Lys, Arthur Micoulet, and Maria Potop-Butucaru

In this paper, we consider the problem of cross-chain transactions where parties that do not trust each other safely exchange digital assets across blockchains. Open blockchains models are decentralized ledgers that keep records of transactions. They are comparable with distributed account books. While they have proven their potential as a store of value, exchanging assets across several blockchains remains a challenge. Our paper proposes a new protocol, R-SWAP, for cross-chain swaps that outperforms existing solutions. Our protocol is built on top of two abstractions: relays and adapters that we formalize for the first time in this paper. Furthermore, we prove the correctness of R-SWAP and analytically evaluate its performances, in terms of cost and latency. Moreover, we evaluate the performances of R-SWAP in two case studies showing the generality of our approach: atomic swaps between Ethereum and Bitcoin (two popular permissionless blockchains) and atomic swaps between Ethereum and Tendermint (one permissionless and one permissioned blockchain).


  1. PrivChain: Provenance and Privacy Preservation in Blockchain enabled Supply Chains
    Authors: Sidra Malika, Volkan Dedeoglub, Salil S. Kanherea, and Raja Jurdakc

Blockchain offers traceability and transparency to supply chain event data and hence can help overcome many challenges in supply chain management such as: data integrity, provenance and traceability. However, data privacy concerns such as the protection of trade secrets have hindered adoption of blockchain technology. Although consortium blockchains only allow authorised supply chain entities to read/write to the ledger, privacy preservation of trade secrets cannot be ascertained. In this work, we propose a privacy-preservation framework, PrivChain, to protect sensitive data on blockchain using zero knowledge proofs. PrivChain provides provenance and traceability without revealing any sensitive information to end-consumers or supply chain entities. Its novelty stems from: a) its ability to allow data owners to protect trade related information and instead provide proofs on the data, and b) an integrated incentive mechanism for entities providing valid proofs over provenance data. In particular, PrivChain uses Zero Knowledge Range Proofs (ZKRPs), an efficient variant of ZKPs, to provide origin information without disclosing the exact location of a supply chain product. Furthermore, the framework allows to compute proofs and commitments off-line, decoupling the computational overhead from blockchain. The proof verification process and incentive payment initiation are automated using blockchain transactions, smart contracts, and events. A proof of concept implementation on Hyperledger Fabric reveals a minimal overhead of using PrivChain for blockchain enabled supply chains.


  1. Traffic Redundancy in Blockchain Systems: The Impact of Logical and Physical Network Structures
    Authors: Ying-Hao Zhan, Xiao Fan Liu

The current designs of Internet-based blockchain systems generate huge traffic redundancy, thereby reducing the efficacy of the system. This paper simulates the Bitcoin blockchain network traffic in a realistic setting and studies the impacts of both logical and physical network structure on the traffic redundancy. Firstly, we construct an Internet AS layer topology graph and map the Bitcoin nodes to the ASes. Then, Bitcoin ’s neighbor discovery algorithm is used to connect Bitcoin nodes together logically. Finally, we simulate the Internet traffic generated by Bitcoin ’s flood-based broadcast algorithm in the AS layer topology graph. Specifically, the traffic that a message generates is calculated by the number of ASes a message passes through times the message size. The difference between the total and effective traffic (i.e., the theoretical minimum) is considered traffic redundancy. Simulations show that traffic redundancy is positively correlated with the Bitcoin network scale and the number of peer neighbors for each node. Meanwhile, the underlying physical network topology, especially the average routing path length between the Bitcoin nodes, determines the traffic redundancy as well. Our findings imply that one can optimize the blockchain network’s throughput by altering the underlying physical network, e.g., migrating from the Internet to a satellite environment.

Link: Traffic Redundancy in Blockchain Systems: The Impact of Logical and Physical Network Structures | IEEE Conference Publication | IEEE Xplore

  1. Bitcoin Address Clustering Method Based on Multiple Heuristic Conditions
    Authors: He Xi, He Ketai, Lin Shenwen, Yang Jinglin, and Mao Hongliang

We analyzed the associations between Bitcoin transactions and addresses to cluster address and further find groups of addresses controlled by the same entity. It revealed the vulnerabilities of Bitcoin anonymity mechanism, which could be used by the law enforcement agencies to track and crack down illegal transactions. However, single heuristic method and incomplete heuristic conditions were difficult to cluster a large number of addresses comprehensively and accurately. Therefore, this paper reviewed a variety of heuristics, and used multiple heuristics comprehensively to cluster addresses to improve the degree of address aggregation and address recall rate, which laid a foundation for further inferring of entity identity.



Another interesting week for Research Pulse!

There were three papers this week that were particularly interesting.

First up is SnarkPack: Practical SNARK Aggregation, which explores the bulk aggregation of zkSNARKs. Benchmarks on this scheme show that SnarkPack can aggregate 8192 proofs in 8.7s and verify them in 33ms. This has the potential to unlock several use-cases for batch validation of private proofs, such as user identity & permission management.

Traffic Redundancy in Blockchain Systems: The Impact of Logical and Physical Network Structures is an interesting analysis of Bitcoin’s networking layer. The authors found that network traffic redundancy is positively correlated with the number of neighbors of nodes. This insight could be used to improve how Bitcoin nodes manage their network peers.

Interestingly, Complex Network Analysis of the Bitcoin Blockchain Network also provided good insights on Bitcoin’s networking layer. The authors use a novel sampling methodology in their data collection frameworks and provide the following takeaways: “Firstly, the degree distribution of the Bitcoin blockchain network conforms to a power-law distribution, approximated to a scale-free network. Secondly, the Bitcoin blockchain network is a small-world network after analyzing the average clustering coefficient and the shortestpath length. Thirdly, regarding to the disassortativity of the Bitcoin network, low-degree nodes prefer connecting to nodes with a higher degree.”

1 Like