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

Deevashwer Rathee, Guru-Vamsi Policharla, Tiancheng Xie, Ryan Cottone, Dawn Song

TL;DR

ZEBRA is a new anonymous credential (AC) system that uses zkSNARKs to enable private, on-chain access control (like KYC for DeFi) at a fraction of the cost of previous methods. By combining a novel two-layer proof recursion with "token caching," ZEBRA reduces transaction fees for credential verification by over 14x, bringing the cost of private access control down to just a few cents.

What Problem Does This Paper Address?

Decentralized Finance (DeFi) is facing a regulatory crossroads. To comply with anti-money laundering (AML) and "Know Your Customer" (KYC) mandates, many applications must restrict access to verified users.

Current solutions are flawed:

  1. Non-private solutions: A central authority links a user's real identity to their blockchain wallet. This is a privacy nightmare and a honeypot for data breaches.
  2. Oracle-based solutions: These use anonymous credentials but rely on a small committee (an oracle) to verify them. This introduces new trust assumptions and reduces the security of the system to the level of the oracle, which is often much lower than the underlying blockchain.
  3. On-chain verification: The most secure method, but existing cryptographic schemes (like Coconut) are prohibitively expensive to verify on the Ethereum Virtual Machine (EVM). Verifying a single credential can cost upwards of $170 in gas fees.

ZEBRA aims to provide on-chain verification that is both private (unlinkable) and accountable (auditable/revocable) while remaining cheap enough for everyday use.

Methods

The authors move away from traditional "Sigma-protocol" based credentials, which have verification costs that grow linearly with the number of attributes. Instead, they build ZEBRA on zkSNARKs (Zero-Knowledge Succinct Non-interactive Arguments of Knowledge), where verification cost is constant regardless of the complexity of the "rules" being checked.

Key technical innovations include:

  • Two-Layer Proof Recursion: To drive costs down further, ZEBRA uses an untrusted aggregator to batch many users' proofs into one. They use a clever "cycle" of elliptic curves: BN254 (supported by EVM) and Grumpkin.
  • Users create a pairing-based proof (Groth16).
  • The aggregator uses a data-parallel SNARK (Spartan) over the Grumpkin curve to verify a batch of user proofs.
  • The aggregator then wraps that Spartan proof back into a Groth16 proof for the EVM to verify.
  • Token Caching: Instead of re-submitting identity "tokens" every time a user interacts with a new app, ZEBRA allows users to "register" a 32-byte commitment to their tokens once. Subsequent verifications just point to this cache, drastically reducing data costs.
  • Accountability Features: ZEBRA supports Auditability (auditors can identify a malicious user), Revocation (invalidating a credential), and Traceability (finding all wallets associated with a revoked credential) without requiring expensive Multi-Party Computation (MPC).

Datasets

As a cryptography and systems paper, ZEBRA does not use traditional machine learning datasets. Evaluation was performed using:

  • Smart Contract Benchmarks: Implemented in Solidity and tested using Ganache and Truffle.
  • Prover Benchmarks: Measured on a 2019 MacBook Pro (user-side) and an AWS m6i.32xlarge instance (aggregator-side).
  • Comparison Baselines: The authors compared ZEBRA against state-of-the-art schemes including Coconut, BASS, and Concordium.

Key Insights and Ideas

  • SNARKs for Constant Cost: By using SNARKs, adding features like "revocation" or "auditability" doesn't increase the gas cost for the blockchain. In prior schemes, adding revocation tripled the cost.
  • The "Untrusted" Aggregator: The batching process is performed by an aggregator that doesn't need to be trusted. If they try to cheat, the SNARK verification on-chain will simply fail.
  • Efficient Traceability: Most traceable systems require auditors to be online simultaneously to perform MPC. ZEBRA uses threshold encryption and a PRF-based tracing mechanism that allows auditors to work asynchronously and trace millions of wallets in seconds.

Key Results

  • Massive Gas Savings: For a single verification, ZEBRA is 14.3x cheaper than Coconut ($12 vs $176).
  • The Power of Batching: When batching 512 users, the amortized cost drops to $0.44** for Layer-1 (Ethereum) and a mere **$0.02 for Layer-2 (like zkSync).
  • Practical Latency: A user can generate a proof in about 2 seconds on a standard laptop. An aggregator can process a batch of 512 users in roughly 1.5 minutes.
  • Scalable Tracing: Auditors can trace a revoked user across a database of 100 million wallet interactions in approximately 15 seconds on a single CPU thread.

Limitations and Future Work

  • Aggregator Bottleneck: While 1.5 minutes for 512 users is practical, the aggregator is still the computational bottleneck. The authors suggest that moving from R1CS to Plonk arithmetization with custom gates could speed this up significantly.
  • CA Trust: While the Certificate Authority (CA) cannot deanonymize users on its own, it is still trusted for the integrity of the credentials (i.e., not issuing fake ones). The authors mention decentralized issuance models as a future extension.
  • Mobile Proving: While 2 seconds is fast for a laptop, the authors note that further optimizations (like using SNARK-friendly hashes like Poseidon instead of SHA256) would be needed for a smooth experience on low-power mobile devices.

Summary updated

Abstract

Restricting access to certified users is not only desirable for many blockchain applications, it is also legally mandated for decentralized finance (DeFi) applications to counter malicious actors. Existing solutions, however, are either (i) non-private, i.e., they reveal the link between users and their wallets to the authority granting credentials, or (ii) they introduce additional trust assumptions by relying on a decentralized oracle to verify anonymous credentials (ACs). To remove additional trust in the latter approach, we propose verifying credentials on-chain in this work. We find that this approach has impractical costs with prior AC schemes, and propose a new AC scheme ZEBRA that crucially relies on zkSNARKs to provide efficient on-chain verification for the first time. In addition to the standard unlinkability property that provides privacy for users, ZEBRA also supports auditability, revocation, traceability, and theft detection, which adds accountability for malicious users and convenience for honest users to our access control solution. Even with these properties, ZEBRA reduces the gas cost incurred on the Ethereum Virtual Machine (EVM) by 14.3x when compared to Coconut [NDSS 2019], the state-of-the-art AC scheme for blockchains that only provides unlinkability. This improvement translates to a reduction in transaction fees from 176 USD to 12 USD on Ethereum in May 2023. Since 12 USD is still high for most applications, ZEBRA further drives down credential verification costs through batched verification. For a batch of 512 layer-1 and layer-2 wallets, the transaction fee on Ethereum is reduced to just 0.44 USD and 0.02 USD, respectively, which is comparable to the minimum transaction costs on Ethereum.
BibTeX
@article{rathee2022zebra,
  author = {Deevashwer Rathee and Guru-Vamsi Policharla and Tiancheng Xie and Ryan Cottone and Dawn Song},
  title = {{ZEBRA: Anonymous Credentials with Practical On-chain Verification and Applications to KYC in DeFi}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
  url = {https://openreview.net/forum?id=BWW4110BSt},
}

Loading related content...

Figure