Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs

2024  |  Tianyi Liu · Tiancheng Xie · Jiaheng Zhang · Dawn Song · Yupeng Zhang  |  S&P 2024

In this work, we improve the scalability of these techniques by proposing new schemes of fully distributed ZKPs. Our schemes can improve the efficiency and the scalability of ZKPs using multiple machines, while the communication among the machines is minimal. With our schemes, the ZKP generation can be distributed to multiple participants in a model similar to the mining pools. Our protocols are based on Plonk, an efficient zero-knowledge proof system with a universal trusted setup. The first protocol is for data-parallel circuits. For computation of \(M\) sub-circuits of size \(T\) each, using \(M\) machines, the prover time is \(O(T\log T + M \log M)\), while the prover time of the original Plonk on a single machine is \(O(MT\log (MT))\). Our protocol incurs only \(O(1)\) communication per machine, and the proof size and verifier time are both \(O(1)\), the same as the original Plonk. Moreover, we show that with minor modifications, our second protocol can support general circuits with arbitrary connections while preserving the same proving, verifying, and communication complexity. The technique is general and may be of independent interest for other applications of ZKP.

  Learn More   Read Paper 

ItyFuzz: Snapshot-Based Fuzzer for Smart Contract

2023  |  Chaofan Shou · Shangyin Tan · Koushik Sen |  https://arxiv.org/pdf/2306.17135.pdf

We introduce a novel snapshot-based fuzzer ItyFuzz for testing smart contracts. In ItyFuzz, instead of storing sequences of transactions and mutating from them, we snapshot states and singleton transactions. To explore interesting states, ItyFuzz introduces a dataflow waypoint mechanism to identify states with more potential momentum. ItyFuzz also incorporates comparison waypoints to prune the space of states. Because ItyFuzz has second-level response time to test a smart contract, it can be used for on-chain testing, which has many benefits compared to local development testing. ItyFuzz has been evaluated on real and hacked DeFi projects and shown to surpass existing fuzzers.…

  Read Paper   View Repo

Towards Automated Security Analysis of Smart Contracts based on Execution Property Graph

2023  |  Kaihua Qin* · Zhe Ye* · Zhun Wang · Weilin Li · Liyi Zhou · Chao Zhang · Dawn Song · Arthur Gervais  |  https://arxiv.org/pdf/2305.14046.pdf

Identifying and mitigating vulnerabilities in smart contracts is crucial, especially considering the rapid growth and increasing complexity of DeFi platforms. To address the challenges associated with securing these contracts, we introduce a versatile dynamic analysis framework specifically designed for the EVM. This comprehensive framework focuses on tracking contract executions, capturing valuable runtime information, while introducing and employing the EPG to propose a unique graph traversal technique that swiftly detects potential smart contract attacks. Our approach showcases its efficacy with rapid average graph traversal time per transaction and high true positive rates. The successful identification of a zero-day vulnerability affecting Uniswap highlights the framework's potential to effectively uncover smart contract vulnerabilities in complex DeFi systems…

  Learn More   Read Paper

Blockchain Large Language Models

2023  |  Yu Gai* · Liyi Zhou* · Kaihua Qin · Dawn Song · Arthur Gervais  |  https://arxiv.org/pdf/2304.12749.pdf

This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, BlockGPT is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies.…

  Learn More   Read Paper

Unique Identification of 50,000+ VR Users from Head & Hand Motion

2023  |  Vivek Nair · Wenbo Guo · Justus Mattern · Rui Wang · James F. O’Brien · Louis Rosenberg · Dawn Song

With the recent explosive growth of interest and investment in VR, public attention has rightly shifted toward the unique security and privacy threats that these platforms may pose. While it has long been known that people reveal information about themselves via their motion, the extent to which this makes an individual globally identifiable within virtual reality has not yet been widely understood. In this study, we show that a large number of real VR users can be uniquely identified across multiple sessions using just head and hand motion…

  Learn More   Read Paper   View Repo

SoK: Data Privacy in Virtual Reality

2022  |  Gonzalo Munilla Garrido · Vivek Nair · Dawn Song  |  https://doi.org/10.48550/arXiv.2301.05940

The adoption of VR technologies has rapidly gained momentum in recent years as companies around the world begin to position the so-called "metaverse" as the next major medium for accessing and interacting with the internet. While consumers have become accustomed to a degree of data harvesting on the web, the real-time nature of data sharing in the metaverse indicates that privacy concerns are likely to be even more prevalent in the new "Web 3.0." Research into VR privacy has demonstrated that a plethora of sensitive personal information is observable by various would-be adversaries from just a few minutes of telemetry data. This paper aims to systematize knowledge on the landscape of VR privacy threats and countermeasures…

  Learn More   Read Paper

Specular: Towards Trust-minimized Blockchain Scalability with EVM-native Fraud Proofs

2022  |  Zhe Ye · Ujval Misra · Dawn Song  |  https://arxiv.org/abs/2212.05219  |  Twitter: @SpecularL2

In this work, we aim to build a secure, trust-minimized optimistic rollup that achieves: (1) a minimal trusted computing base, improving security, auditability and upgradeability; (2) support for permissionless, trust-minimized participation of multiple Ethereum clients, enabling client diversity; and (3) efficient dispute resolution. To do so, we design an IFP system native to the EVM, that enforces Ethereum's specified semantics precisely at the level of a single EVM instruction. We present an implementation of this approach in Specular, an ORU which leverages an off-the-shelf Ethereum client—modified minimally to support one-step proof generation.

  Learn More   Read Paper 

zkBridge: Trustless Cross-chain Bridges Made Practical

2022  |  Tiancheng Xie · Jiaheng Zhang · Zerui Cheng · Fan Zhang · Yupeng Zhang · Yongzheng Jia · Dan Boneh · Dawn Song  |  https://arxiv.org/pdf/2210.00264.pdf  |  ACM CCS 2022  |  Twitter: @zkcollective

We present zkBridge, the first trustless, permissionless, extensible, universal, and efficient cross-chain bridge. With succinct proofs, zkBridge not only guarantees strong security without external assumptions, but also significantly reduces on-chain verification cost. We propose novel succinct proof protocols that are orders-of-magnitude faster than existing solutions for workload in zkBridge. With a modular design, zkBridge enables a broad spectrum of applications, including message passing, token transferring, and other computational logic operating on state changes from different chains. We have already implemented zkBridge between certain chains and evaluated its end-to-end performance. We encourage community members to join us to extend zkBridge to other chains; please fill in the form if you are interested in contributing to this project towards building a universal, secure foundation for multi-chain interoperability...

  Learn More   Read Paper 

ZEBRA: Anonymous Credentials with Practical On-chain Verification and Applications to KYC in DeFi

2022  |  Deevashwer Rathee · Guru Vamsi Policharla · Tiancheng Xie · Ryan Cottone · Dawn Song  |  https://eprint.iacr.org/2022/1286.pdf

ZEBRA is an Anonymous Credential (AC) scheme, supporting auditability and revocation, that provides practical on-chain verification for the first time. It realizes efficient access control on permissionless blockchains while achieving both privacy and accountability. In all prior solutions, users either pay exorbitant fees or lose privacy since authorities granting access can map users to their wallets. Hence, ZEBRA is the first to enable DeFi platforms to remain compliant with imminent regulations without compromising user privacy.
When compared to the state-of-the-art AC scheme for blockchains, ZEBRA reduces the gas cost incurred on the Ethereum Virtual Machine (EVM) by 11.8x. This translates to a reduction in transaction fees from 94 USD to 8 USD on Ethereum in August 2022. ZEBRA further drives down credential verification costs through batched verification and achieves a transaction fee of just 0.0126 USD for a batch of 512 wallets.

Orion: Zero Knowledge Proof with Linear Prover Time

2022  |  Tiancheng Xie · Yupeng Zhang · Dawn Song  |  Link to Paper  |  published in CRYPTO 2022

Zero-knowledge proof is a powerful cryptographic primitive that has found various applications in the real world. However, existing schemes with succinct proof size suffer from a high overhead on the proof generation time that is super-linear in the size of the statement represented as an arithmetic circuit, limiting their efficiency and scalability in practice. In this paper, we present Orion, a new zero-knowledge argument system that achieves \(O(N)\) prover time of field operations and hash functions and \(O(\log^2 N)\) proof size.

  Read Paper   View Repo

MetaData: Exploring the Unprecedented Privacy Risks of the Metaverse

2022  |  Vivek Nair · Gonzalo Munilla Garrido · Dawn Song  |  https://doi.org/10.48550/arXiv.2207.13176

Thirty study participants playtested an innocent-looking "escape room" game in virtual reality (VR). Behind the scenes, an adversarial program had accurately inferred over 25 personal data attributes, from anthropometrics like height and wingspan to demographics like age and gender, within just a few minutes of gameplay. In this work, we illustrate how VR attackers can covertly ascertain dozens of personal data attributes from seemingly-anonymous users of popular metaverse applications…

  Metaverse Research   Learn More   Read Paper   View Repo

MetaGuard: Going Incognito in the Metaverse

2022  |  Vivek Nair · Gonzalo Munilla Garrido · Dawn Song  |  https://doi.org/10.48550/arXiv.2208.05604

We present the first known method of implementing an "incognito mode" for VR. Our technique leverages local ε-differential privacy to quantifiably obscure sensitive user data attributes, with a focus on intelligently adding noise when and where it is needed most to maximize privacy while minimizing usability impact…

  Metaverse Research   Learn More   Read Paper   View Repo

Multi-Factor Key Derivation Function (MFKDF)

2022  |  Vivek Nair · Dawn Song  |  https://doi.org/10.48550/arXiv.2208.05586

Our Multi-Factor Key Derivation Function (MFKDF) expands upon password-based key derivation functions (PBKDFs) with support for using other popular authentication factors like TOTP, HOTP, and hardware tokens in the key derivation process. In doing so, it provides an exponential security improvement over PBKDFs with less than 12 ms of additional computational overhead. The result is a paradigm shift toward direct cryptographic protection of user data using all available authentication factors, without changeing the user experience…

  Learn More   Read Paper   View Repo

A More Complete Analysis of the Signal Double Ratchet Algorithm

2022  |  Alexander Bienstock · Jaiden Fairoze · Sanjam Garg · Pratyay Mukherjee · Srinivasan Raghuraman

We develop new formal definitions in the Universal Composability framework for the Signal Double Ratchet (DR) protocol. Our definitions (a) capture the security and correctness guarantees of prior work, and (b) capture more guarantees that are absent from one or all prior works. We also present an enhancement of the DR, denoted the Triple Ratchet (TR), that meets a stronger security definition and also applies to other protocols…

  Watch Presentation   Read Paper

Systematization of Knowledge (SoK): DeFi Incidents

2022  |  Liyi Zhou · Xihan Xiong · Jens Ernstberger · Stefanos Chaliasos · Zhipeng Wang · Ye Wang · Kaihua Qin · Roger Wattenhofer · Dawn Song · Arthur Gervais

In this paper, we introduce a common reference frame to systematically evaluate and compare DeFi incidents. We investigate 77 academic papers, 30 audit reports, and 181 real-world incidents. Our open data reveals several gaps between academia and the practitioners' community. For example, few academic papers address "price oracle attacks" and "permissonless interactions", while our data suggests that they are the two most frequent incident types (15% and 10.5% correspondingly). We also investigate potential defenses…

  Read Paper

Copyright ©2022 UC Regents  |  Email us at rdi@berkeley.edu.