Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation

Tiancheng Xie; Jiaheng Zhang; Yupeng Zhang; Charalampos Papamanthou; Dawn Song

Paper 2019/317

Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation

Tiancheng Xie, Jiaheng Zhang, Yupeng Zhang, Charalampos Papamanthou, and Dawn Song

Abstract

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both O(d log C) for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 seconds to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.

Note: keep aligned as virgo

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2019
Keywords: Zero knowledge proof interactive proof polynomial delegation
Contact author(s): zhangyp @ tamu edu
jiaheng_zhang @ berkeley edu
niconiconi @ berkeley edu
History: 2021-11-20: last of 8 revisions; 2019-03-29: received; See all versions
Short URL: https://ia.cr/2019/317
License: CC BY

BibTeX

@misc{cryptoeprint:2019/317,
      author = {Tiancheng Xie and Jiaheng Zhang and Yupeng Zhang and Charalampos Papamanthou and Dawn Song},
      title = {Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/317},
      year = {2019},
      url = {https://eprint.iacr.org/2019/317}
}