ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash

Sarah Meiklejohn, C. Christopher Erway, Alptekin Küpçü, Theodora Hinkle, Anna LysyanskayaUSENIX Security 2010

Sarah Meiklejohn, C. Chris Erway, Alptekin Küpçü, Theodora Hinkle, and Anna Lysyanskaya

Introduction

Modern cryptography has produced powerful tools like zero-knowledge proofs (ZKPs), which allow a prover to convince a verifier of a statement's truth without revealing underlying private data. Despite their theoretical potential, a significant "implementation gap" exists. These protocols are mathematically complex and computationally intensive, making manual implementation in languages like C++ error-prone and inefficient. ZKPDL (Zero-Knowledge Proof Description Language) addresses this by providing a high-level language and optimizing interpreter to bridge the gap between cryptographic theory and practical deployment.

System Architecture

The ZKPDL system consists of two primary components: a domain-specific language and an optimizing interpreter. The language is a non-Turing-complete DSL used to describe variables, equations, and relationships within a protocol. A single ZKPDL program specifies the logic for both the prover and the verifier, ensuring consistency across the protocol.

The ZKPDL system architecture, showing the compilation and interpretation process for provers and verifiers.

The C++ interpreter (~6000 lines) parses the ZKPDL code and applies several key optimizations to overcome the performance penalties typically associated with high-level abstractions:

  • Translation: Converting proofs into a "fundamental discrete logarithm form" to eliminate redundant computations.
  • Multi-exponentiation: Utilizing precomputed lookup tables for fixed-base exponentiations to accelerate modular arithmetic.
  • Caching: Storing compiled environments so that repeated protocols (like a bank processing thousands of e-coins) avoid re-parsing overhead.

Practical Application: Electronic Cash

To demonstrate the utility of ZKPDL, the authors developed Cashlib, a library providing interfaces for electronic cash, blind signatures, and fair exchange protocols. This library supports complex interactions between users, banks, and arbiters, facilitating privacy-preserving financial transactions.

The interaction model for electronic cash and barter protocols supported by Cashlib.

Cashlib enables various operations such as "Withdraw," "Deposit," and "Buy." It also supports a "Barter" protocol for data-for-data exchange, which was shown to be significantly more efficient than the "Buy" protocol by avoiding the heavy computational costs of verifiable escrow for every data block.

Performance and Results

The ZKPDL approach offers significant advantages in both development effort and execution speed. The authors were able to replace approximately 9,000 lines of hand-coded C++ with just 400 lines of ZKPDL, drastically reducing the "bug surface" and making the code easier to audit for security.

Performance benchmarks on a standard laptop revealed that the interpreter's optimizations led to an average 48% speed improvement for the prover and a 31% improvement for the verifier compared to unoptimized versions. Specific timings include:

  • Discrete Logarithm Proof: 3.07 ms.
  • Complex "Coin" Proof: 134.37 ms.
  • Bank Verification: ~83 ms per coin.

Caching the compiled environment alone saved roughly 10% of total computation time for high-volume entities like banks.

Conclusion and Future Work

While ZKPDL significantly advances the practicality of ZKPs, challenges remain. Range proofs continue to be a computational bottleneck and a primary source of large proof sizes. Future work will focus on integrating more efficient range proof techniques, exploring coarse-grained parallelism for multicore architectures, and enhancing the composability of ZKPDL programs through subroutines.

Summary updated

BibTeX
@inproceedings{meiklejohn2010zkpdl,
  author = {Sarah Meiklejohn and C. Christopher Erway and Alptekin Küpçü and Theodora Hinkle and Anna Lysyanskaya},
  title = {{ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash}},
  booktitle = {USENIX Security},
  year = {2010},
}
Figure