Research Pulse Issue #7 04/02/21

  1. Latus Incentive Scheme: Enabling Decentralization in Blockchains based on Recursive SNARKs
    Authors: Alberto Garoffolo, Dmytro Kaidalov, and Roman Oliynykov

In [11] we introduced a novel SNARK-based construction, called Zendoo, that allows Bitcoin-like blockchains to create and communicate with sidechains of different types without knowing their internal structure. We also introduced a specific construction, called Latus, allowing creation of fully verifiable sidechains. But in [11] we omitted a detailed description of an incentive scheme for Latus that is an essential element of a real decentralized system. This paper fills the gap by introducing details of the incentive scheme for the Latus sidechain. Represented ideas can also be adopted by other SNARK-based blockchains to incentivize decentralized proofs creation.


  1. Research on a Covert Communication Model Realized by Using Smart Contracts in Blockchain Environment
    Authors: Lejun Zhang, Zhijie Zhang, Weizheng Wang, Zilong Jin, Yansen Su, and Huiling Chen

The traditional covert communication channel relying on a third-party node is vulnerable to attack. The data are easily tampered with and the identity information of the communication party is fragile. Blockchain has the characteristics of decentralization and tamper resistance, which can effectively solve the above problems. In addition, some confidential information needs to be transmitted covertly in the transparent blockchain. A smart contract deployed in the blockchain to automatically realize its function can replace a centralized node to provide credible guarantee for communication. The diversity of parameters, data redundancy, and code programmability of smart contract make it an excellent carrier for covert communication under blockchain. In this article, we propose a covert communication model combined with smart contracts to covertly transfer information in the blockchain environment. To implement this model, we use the parameters in the contract to map the secret information sequence, and call the contract to transfer message. Voting contract and secret bidding contract are combined to instantiate the proposed model, and optimized versions of the two contracts are also proposed to reduce costs. Moreover, we use encryption algorithms and two-round protocols to ensure data privacy and design corresponding information embedding and transmission methods for different scenarios. To improve the concealment of communication, redundant options, effective price ranges, and invalid bids are set in two contracts, respectively. The experimental results show that the proposed model has tamper resistance and low complexity, and it is feasible to use this model for covert communication.


  1. On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols
    Authors: Markulf Kohlweiss, Varun Madathil, Kartik Nayak, and Alessandra Scafuro

In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S&P 2019 the “Ouroboros Crypsinous” system of Kerber et al. (and concurrently Ganesh et al. in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the networklayer can be removed as well by employing anonymous broadcast channels. In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block. We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay – within the synchrony bound – loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than (1 − 2f) anonymity at the same time (where f is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We show that our attacks are practical, by describing how they can be carried out over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.


  1. Analysis and Probing of Parallel Channels in the Lightning Network
    Authors: Alex Biryukov, Gleb Naumenko, and Sergei Tikhomirov

The Lightning Network (LN) is a prominent scalability solution for Bitcoin that allows for low-latency off-chain payments through a network of payment channels. LN users lock bitcoins into collaboratively owned addresses and redistribute the ownership of these funds without confirming each transfer on-chain. The LN introduces new privacy challenges. In this paper, we focus on channel balance probing. We propose a new model of the LN that accounts for parallel and unidirectional channels, which has not been done in prior work. We describe a probing algorithm that accurately updates the attacker’s balance estimates without the need to directly connect to victims. We introduce an uncertainty-based metric to measure the attacker’s information gain. We implement the first probing-focused LN simulator and suggest several countermeasures against general probing (implemented considering parallel channels). We evaluate these techniques using the simulator, as well as experiments on the real network. According to our simulations, an attacker can infer up to 80% information regarding channel balances spending ≈ 20 seconds per channel. The suggested countermeasures limit the attacker’s gain at 30%, while also increasing the attack time by 2-4x. In addition, we describe sophisticated attack techniques that combine fee-probing and channel jamming to get precise access to individual channel balances inside a hop, and test them against the real network. Finally, we discuss payment flows and their concealment.


  1. Do the Rich Get Richer? Fairness Analysis for Blockchain Incentives
    Authors: Yuming Huang, Jing Tang, Qianhao Cong, Andrew Lim, and Jianliang Xu

Proof-of-Work (PoW) is the most widely adopted incentive model in current blockchain systems, which unfortunately is energy inefficient. Proof-of-Stake (PoS) is then proposed to tackle the energy issue. The rich-get-richer concern of PoS has been heavily debated in the blockchain community. The debate is centered around the argument that whether rich miners possessing more stakes will obtain higher staking rewards and further increase their potential income in the future. In this paper, we define two types of fairness, i.e., expectational fairness and robust fairness, that are useful for answering this question. In particular, expectational fairness illustrates that the expected income of a miner is proportional to her initial investment, indicating that the expected return on investment is a constant. To better capture the uncertainty of mining outcomes, robust fairness is proposed to characterize whether the return on investment concentrates to a constant with high probability as time evolves. Our analysis shows that the classical PoW mechanism can always preserve both types of fairness as long as the mining game runs for a sufficiently long time. Furthermore, we observe that current PoS blockchains implement various incentive models and discuss three representatives, namely ML-PoS, SL-PoS and C-PoS. We find that (i) ML-PoS (e.g., Qtum and Blackcoin) preserves expectational fairness but may not achieve robust fairness, (ii) SL-PoS (e.g., NXT) does not protect any type of fairness, and (iii) C-PoS (e.g., Ethereum 2.0) outperforms ML-PoS in terms of robust fairness while still maintaining expectational fairness. Finally, massive experiments on real blockchain systems and extensive numerical simulations are performed to validate our analysis.


  1. Nova: Recursive Zero-Knowledge Arguments from Folding Schemes
    Authors: Abhiram Kothapalli, Srinath Setty, and Ioanna Tzialla

We introduce folding schemes for NP, an interactive protocol between a prover and a verifier to combine two N-sized NP instances over a finite field F into a single N-sized instance such that the folded instance is satisfiable only if the original instances are satisfiable. In particular, we devise a folding scheme for relaxed R1CS, a characterization of NP that is especially amenable to folding. The verifier’s cost and the communication in the folding scheme are both Oλ(1), where λ is the security parameter, assuming any additively-homomorphic commitment scheme that provides Oλ(1)-sized commitments to N-sized vectors over F . Additionally, the protocol is honest-verifier zero-knowledge and public coin, so it can be made non-interactive in the ROM using the Fiat-Shamir transform. We then construct incrementally verifiable computation (IVC) from folding schemes by using a “verifier circuit” that at each recursive step folds an entire R1CS instance representing computation (including a copy of the verifier circuit) at its prior step into a running relaxed R1CS instance. A distinctive aspect of our approach to IVC is that it achieves the smallest verifier circuit (a key metric to minimize in IVC) in the literature: the circuit is constant-sized and its size is dominated by two group scalar multiplications. We then show that the running relaxed R1CS instance can be proven in zero-knowledge with a succinct proof using a variant of an existing zkSNARK. Putting these together, we obtain Nova, a new zero-knowledge proof system for incremental computations, where for an N-sized computation with C-sized steps, the prover runs in Oλ(N) time to produce Oλ(log C)- sized proofs that can be verified in Oλ(C) time. Nova does not require a trusted setup nor performs FFTs, so it can be efficiently instantiated with any cycles of elliptic curves where DLOG is hard. Furthermore, at each step, the prover time is dominated by two ≈C-sized multiexponentiations. Finally, Nova can achieve Oλ(log C) verification time at the cost of employing a pairing-friendly elliptic curve where SXDH is hard.


  1. Helmholtz: A Verifier for Tezos Smart Contracts Based on Refinement Types
    Authors: Yuki Nishida, Hiromasa Saito, Ran Chen, Akira Kawata, Jun Furuse, Kohei Suenaga, and Atsushi Igarashi

A smart contract is a program executed on a blockchain, based on which many cryptocurrencies are implemented, and is being used for automating transactions. Due to the large amount of money that smart contracts deal with, there is a surging demand for a method that can statically and formally verify them. This tool paper describes our type-based static verification tool Helmholtz for Michelson, which is a statically typed stack-based language for writing smart contracts that are executed on the blockchain platform Tezos. Helmholtz is designed on top of our extension of Michelson’s type system with refinement types. Helmholtz takes a Michelson program annotated with a user-defined specification written in the form of a refinement type as input; it then typechecks the program against the specification based on the refinement type system, discharging the generated verification conditions with the SMT solver Z3. We briefly introduce our refinement type system for the core calculus Mini-Michelson of Michelson, which incorporates the characteristic features such as compound datatypes (e.g., lists and pairs), higher-order functions, and invocation of another contract. Helmholtz successfully verifies several practical Michelson programs, including one that transfers money to an account and that checks a digital signature.


  1. Analyzing Transaction Confirmation in Ethereum Using Machine Learning Techniques
    Authors: Vinicius C. Oliveira, Julia Almeida Valadares, Jose Eduardo A. Sousa, Alex Borges Vieira, Heder Soares Bernardino, Saulo Moraes Villela, and Glauber Dias Goncalves

Ethereum has emerged as one of the most important cryptocurrencies in terms of the number of transactions. Given the recent growth of Ethereum, the cryptocurrency community and researchers are interested in understanding the Ethereum transactions behavior. In this work, we investigate a key aspect of Ethereum: the prediction of a transaction confirmation or failure based on its features. This is a challenging issue due to the small, but still relevant, fraction of failures in millions of recorded transactions and the complexity of the distributed mechanism to execute transactions in Ethereum. To conduct this investigation, we train machine learning models for this prediction, taking into consideration carefully balanced sets of confirmed and failed transactions. The results show high-performance models for classification of transactions with the best values of F1-score and area under the ROC curve approximately equal to 0.67 and 0.87, respectively. Also, we identified the gas used as the most relevant feature for the prediction.


  1. Fertile LAND: Pricing non-fungible tokens
    Authors: Michael M. Dowling

The current popularity of non-fungible token (NFT) markets is one of the most notable public successes of blockchain technology. NFTs are blockchain-traded rights to any digital asset; including images, videos, music, even the parts of virtual worlds. As a first study of NFT pricing, we explore the pricing of parcels of virtual real estate in the largest blockchain virtual world, Decentraland; an NFT simply termed LAND. We show a LAND price series characterised by both inefficiency and a steady rise in value.

Link: Fertile LAND: Pricing non-fungible tokens by Michael M. Dowling :: SSRN

  1. Fighting Under-price DoS Attack in Ethereum with Machine Learning Techniques
    Authors: Jose Eduardo A. Sousa, Vinicius C. Oliveira, Julia Almeida Valadares, Alex Borges Vieira, Heder S. Bernardino, Saulo Moraes Villela, and Glauber Dias Goncalves

Ethereum is one of the most popular cryptocurrency currently and it has been facing security threats and attacks. As a consequence, Ethereum users may experience long periods to validate transactions. Despite the maintenance on the Ethereum mechanisms, there are still indications that it remains susceptible to a sort of attacks. In this work, we analyze the Ethereum network behavior during an under-priced DoS attack, where malicious users try to perform denial-of-service attacks that exploit flaws in the fee mechanism of this cryptocurrency. We propose the application of machine learning techniques and ensemble methods to detect this attack, using the available transaction attributes. The proposals present notable performance as the Decision Tree models, with AUC-ROC, Fβ-score and recall larger than 0.94, 0.82, and 0.98, respectively.



Seems like there is a lot of buzz around “On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols”. I finished reading it this morning and it’s a great read. They describe an attack on Cardano’s consensus protocol that carries big implications.

My take on it is that blockchains that I) do not have base layer privacy-preserving technologies or II) have base layer privacy, but small anonymity sets, will face considerable challenges preserving the privacy of its PoS validators. Too much information is leaked at both network and tx graph levels.

Another interesting read is “Do the Rich Get Richer? Fairness Analysis for Blockchain Incentives” since it is one of the first attempts at formalizing and standardizing the different PoS economic models.

1 Like