Research Pulse #88 10/24/2022

  1. aPlonK: Aggregated PlonK from Multi-Polynomial Commitment Schemes
    Authors: Miguel Ambrona, Marc Beunardeau, Anne-Laure Schmitt, and Raphaël R. Toledo

PlonK is a prominent universal and updatable zk-SNARK for general circuit satisfiability. We present aPlonK, a variant of PlonK that reduces the proof size and verification time when multiple statements are proven in a batch. Both the aggregated proof size and the verification complexity of aPlonK are logarithmic in the number of aggregated statements. Our main building block, inspired by the techniques developed in SnarkPack (Gailly, Maller, Nitulescu, FC 2022), is a multi-polynomial commitment scheme, a new primitive that generalizes polynomial commitment schemes. Our techniques also include a mechanism for involving committed data into PlonK statements very efficiently, which can be of independent interest.
We also implement an open-source industrial-grade library for zero-knowledge PlonK proofs with support for aPlonK. Our experimental results show that our techniques are suitable for real-world applications (such as blockchain rollups), achieving significant performance improvements in proof size and verification time.

Link to Paper

  • PlonK has been extensively covered on SCRF as a potentially ground-breaking technology for blockchains given its ability to address, simultaneously, the issues of privacy and scalability that haunt blockchains today.

  • This paper introduces a variant of PlonK called aPlonK, which authors claim offers the very same benefits of the original schema, but with smaller proof sizes and shorter verification times when batching is used.

  • This schema and its accompanying library can be crucial building blocks for zk-rollups, a next-generation scalability technology for Ethereum.

  1. ZKBdf: A ZKBoo-based Quantum-Secure Verifiable Delay Function with Prover-secret
    Authors: Teik Guan Tan, Vishal Sharma, Zeng Peng Li, Pawel Szalachowski, and Jianying Zhou

Since the formalization of Verifiable Delay Functions (VDF) by Boneh et al. in 2018, VDFs have been adopted for use in blockchain consensus protocols and random beacon implementations. However, the impending threat to VDF-based applications comes in the form of Shor’s algorithm running on quantum computers in the future which can break the discrete logarithm and integer factorization problems that existing VDFs are based on. Clearly, there is a need for quantum-secure VDFs. In this paper, we propose ZKBdf, which makes use of ZKBoo, a zero-knowledge proof system for verifiable computation, as the basis for realizing a quantum-secure VDF. We describe the algorithm, provide the security proofs, implement the scheme and measure the execution and size requirements. In addition, as ZKBdf extends the standard VDF with an extra “Prover-secret” feature, new VDF use-cases are also explored.

Link to Paper

  • Verifiable Delay Functions (VDFs) are actively being evaluated in the field of distributed PoS consensus as a better building block for so-called leader selection, the process of determining who will mine a block at a point in time.
  • Leader selection today is predominantly done via random oracles, which is a concerning trend due to the potential attack vectors that emerge when you know who will mine a block ahead of time.
  • This paper introduces an interesting new construct that combines VDFs and Zero-Knowledge proofs to expand the usefulness of these functions, especially in processes that require privacy.
  1. POSE: Practical Off-chain Smart Contract Execution (Full Version)
    Authors: Tommaso Frassetto, Patrick Jauernig, David Koisser, David Kretzler, Benjamin Schlosser, Sebastian Faust, and Ahmad-Reza Sadeghi

Smart contracts enable users to execute payments depending on complex program logic. Ethereum is the most notable example of a blockchain that supports smart contracts leveraged for countless applications including games, auctions and financial products. Unfortunately, the traditional method of running contract code on-chain is very expensive, for instance, on the Ethereum platform, fees have dramatically increased, rendering the system unsuitable for complex applications. A prominent solution to address this problem is to execute code off-chain and only use the blockchain as a trust anchor. While there has been significant progress in developing off-chain systems over the last years, current off-chain solutions suffer from various drawbacks including costly blockchain interactions, lack of data privacy, huge capital costs from locked collateral, or supporting only a restricted set of applications.
In this paper, we present POSE—a practical off-chain protocol for smart contracts that addresses the aforementioned shortcomings of existing solutions. POSE leverages a pool of Trusted Execution Environments (TEEs) to execute the computation efficiently and to swiftly recover from accidental or malicious failures. We show that POSE provides strong security guarantees even if a large subset of parties is corrupted. We evaluate our proof-of-concept implementation with respect to its efficiency and effectiveness.

Link to Paper

  • In the majority of smart contract platforms today, developers publish the code of their applications to the blockchain. The code is transparent and its storage is socialized across all entities running nodes.

  • While this structure has been successful for a plethora of applications, there are drawbacks to be considered. Since the code is public, this structure might not be well-suited for applications that require strong privacy assurances. Furthermore, the socialization of storage costs might generate negative externalities as the size of blockchains grows.

  • This paper discusses an alternative schema for smart contracts where the logic of an application is stored off-chain in a Trusted Execution Environment (TEE). While this does entail centralization considerations, it’s an interesting schema for use-cases that require privacy, such as those that deal with sensitive user information.

  1. Detecting Arbitrage on Ethereum Through Feature Fusion and Positive-unlabeled Learning
    Authors: Hai Jin, Chenchen Li, Jiang Xiao, Teng Zhang, Xiaohai Dai, and Bo Li

Due to the lack of supervision in the decentralized exchanges (DEXs), arbitrageurs can utilize information and take advantage of price gap to make profits over such platforms such as Ethereum blockchain. DEX arbitrage poses possibilities and opportunities for defrauding and can seriously impair the operation of the Ethereum ecosystem. It motivates this work to explore and characterize the unique features of arbitrage which differ from other frauds such as money laundering and Ponzi games for better detection. This work makes the first attempt for detecting arbitrage on Ethereum through feature fusion and positive-unlabeled learning (PU learning). We first conduct an in-depth analysis and exploit two-fold arbitrage features by fusion including: 1) statistical features that explicitly represent the node activity levels according to expert knowledge; and 2) structural features that implicitly encode the transactions information by graph machine learning. We then apply PU learning to generate negative instances for compensating the imbalanced arbitrage datasets. We evaluate our proposed method through extensive experiments over a real-world dataset and demonstrate that it can achieve 90% accuracy in detecting arbitrage activities on Ethereum.

Link to Paper

  • Modern Decentralized Exchanges (DEXs) frequently rival their centralized counterparts on volume and breadth of market coverage.

  • Nevertheless, there are fundamental differences between these two constructs, especially as it relates to how power users, such as high-frequency traders, drive market efficiency via arbitrage.

  • This paper introduces a machine-learning model to identify the frequency of arbitrage trades in DEXs. The authors claim a 90% accuracy rate in identifying arbitrage trades on-chain.

  1. Anti-Collusion Multiparty Smart Contracts for Distributed Watchtowers in Payment Channel Networks
    Authors: Miao Du, Peng Yang, Wen Tian, and Zhu Han

Leveraging watchtowers to monitor payment channel networks (PCNs) is regarded to be a promising option to ensure off-chain transaction security and boost cryptocurrency scalability. However, existing solutions have two major limitations: First, since the watchtower’s inaction or collusion with counterparties, the deposits in off-chain transactions will be threatened; Second, due to occasional false positives, the efficiency of the single watchtower in monitoring the payment channels for fraud is questionable. To solve this, we present anti-collusion multiparty smart contracts for distributed watchtowers in PCNs. Specifically, we first design the distributed watchtower mechanism to solve the false positive problem in regulating PCNs. In addition, we utilize smart contracts to constrain and force counterparties to relinquish collusion in the distributed watchtower mechanism, thus making collusion impossible for rational parties. We further offer a mathematical proof and contract implementation in Solidity. Finally, extensive experiments and contracts executed on Ethereum under various benchmarks with baseline comparison demonstrate the validity of our proposals. Specifically, our scheme can both improve the throughput and accuracy by up to 20-25% and 10-15%, respectively, and reduce the false positive rate by up to 10% compared with existing single watchtower mechanism.

Link to Paper

  • Payment Channel Networks (PCNs), Bitcoin’s Lightning and Ethereum’s Raiden networks, have shown promising properties for cryptoasset payments. However, there are still issues that prevent their mass adoption.
  • Chief amongst these issues is the requirement for nodes to be online at all times to monitor for channel closures and malicious activity.
  • This paper discusses one of the potential solutions to this issue, monitoring systems popularly called WatchTowers.
  1. Modeling Effective Lifespan of Payment Channels
    Authors: Soheil Zibakhsh Shabgahi, Seyed Mahdi Hosseini, Seyed Pooya Shariatpanahi, and Behnam Bahrak

While being decentralized, secure, and reliable, Bitcoin and many other blockchain-based cryptocurrencies suffer from scalability issues. One of the promising proposals to address this problem is off-chain payment channels. Since, not all nodes are connected directly to each other, they can use a payment network to route their payments. Each node allocates a balance that is frozen during the channel’s lifespan. Spending and receiving transactions will shift the balance to one side of the channel. A channel becomes unbalanced when there is not sufficient balance in one direction. In this case, we say the effective lifespan of the channel has ended. In this paper, we develop a mathematical model to predict the expected effective lifespan of a channel based on the network’s topology. We investigate the impact of channel unbalancing on the payment network and individual channels. We also discuss the effect of certain characteristics of payment channels on their lifespan. Our case study on a snapshot of the Lightning Network shows how the effective lifespan is distributed, and how it is correlated with other network characteristics. Our results show that central unbalanced channels have a drastic effect on the network performance.

Link to Paper

  • Also on the topic of Payment Channel Networks (PCNs), another issue faced relates to the management of the individual payment channels that make up a user’s total liquidity within the PCN.
  • This paper provides interesting insights into how channels on the Lightning network are managed today and sheds light on their lifespan as users’ connections and routing structures change over time.