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:
- 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.
- 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.
- 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.32xlargeinstance (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