Skip to main content
Springer Nature Link
Log in

Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2019 (CRYPTO 2019)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11694))

Included in the following conference series:

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 s 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 119.00
Price excludes VAT (USA)
Softcover Book
USD 159.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In ZKP literature, “succinct” is poly-logarithmic in the size of the statement C.

  2. 2.

    To be compatible with other protocols later, we use three values \(t=0,1,2\) in our evaluations instead of just two.

  3. 3.

    We use the circuit representation of matrix multiplication with \(O(n^3)\) gates for fair comparisons, not the special protocol proposed in [43].

References

  1. Ate-pairing. https://github.com/herumi/ate-pairing

  2. The GNU multiple precision arithmetic library. https://gmplib.org/

  3. Hyrax reference implementation. https://github.com/hyraxZK/hyraxZK

  4. jsnark. https://github.com/akosba/jsnark

  5. libsnark. https://github.com/scipr-lab/libsnark

  6. Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (2017)

    Google Scholar 

  7. Bayer, S., Groth, J.: Efficient zero-knowledge argument for correctness of a shuffle. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 263–280. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_17

    Chapter  Google Scholar 

  8. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint (2018)

    Google Scholar 

  9. Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: Proceedings of the Symposium on Security and Privacy SP (2014)

    Google Scholar 

  10. Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90–108. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_6

    Chapter  MATH  Google Scholar 

  11. Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. Cryptology ePrint (2018)

    Google Scholar 

  12. Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31–60. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_2

    Chapter  Google Scholar 

  13. Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the USENIX Security Symposium (2014)

    Google Scholar 

  14. Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable zero knowledge via cycles of elliptic curves. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 276–294. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_16

    Chapter  Google Scholar 

  15. Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2–3), 225–244 (1994)

    Article  MathSciNet  Google Scholar 

  16. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: Proceedings of the Symposium on Security and Privacy (SP), pp. 319–338 (2018)

    Google Scholar 

  17. Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327–357. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_12

    Chapter  MATH  Google Scholar 

  18. Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., Jakobsen, S.K.: Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 336–365. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_12

    Chapter  Google Scholar 

  19. Braun, B., Feldman, A.J., Ren, Z., Setty, S.T.V., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: ACM SIGOPS 24th Symposium on Operating Systems Principles, SOSP (2013)

    Google Scholar 

  20. Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-Shamir from simpler assumptions. IACR Cryptology ePrint Archive 2018:1004 (2018)

    Google Scholar 

  21. Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1825–1842. ACM (2017)

    Google Scholar 

  22. Chiesa, A., Forbes, M.A., Spooner, N.: A zero knowledge sumcheck and its applications. CoRR abs/1704.02086 (2017). http://arxiv.org/abs/1704.02086

  23. Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012 (2012)

    Google Scholar 

  24. Costello, C., et al.: Geppetto: Versatile verifiable computation. In: S&P (2015)

    Google Scholar 

  25. Cramer, R., Damgård, I.: Zero-knowledge proofs for finite field arithmetic, or: can zero-knowledge be for free? In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 424–441. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055745

    Chapter  Google Scholar 

  26. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12

    Chapter  Google Scholar 

  27. Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., Parno, B.: Hash first, argue later: adaptive verifiable computations on outsourced data. In: ACM SIGSAC Conference on Computer and Communications Security (2016)

    Google Scholar 

  28. Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_37

    Chapter  Google Scholar 

  29. Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster zero-knowledge for boolean circuits. In: USENIX Security Symposium, pp. 1069–1083 (2016)

    Google Scholar 

  30. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for Muggles. J. ACM 62(4), 27:1–27:64 (2015)

    Article  MathSciNet  Google Scholar 

  31. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)

    Article  MathSciNet  Google Scholar 

  32. Groth, J.: Linear algebra with sub-linear zero-knowledge arguments. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 192–208. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_12

    Chapter  Google Scholar 

  33. Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_19

    Chapter  Google Scholar 

  34. Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: 22nd Annual IEEE Conference on Computational Complexity (CCC 2007) (2007)

    Google Scholar 

  35. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 21–30. ACM (2007)

    Google Scholar 

  36. Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Proceedings of the ACM Symposium on Theory of Computing (1992)

    Google Scholar 

  37. Kosba, A., Miller, A., Shi, E., Wen, Z., Papamanthou, C.: Hawk: the blockchain model of cryptography and privacy-preserving smart contracts. In: Proceedings of Symposium on Security and Privacy (SP) (2016)

    Google Scholar 

  38. Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169–189. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28914-9_10

    Chapter  Google Scholar 

  39. Lund, C., Fortnow, L., Karloff, H., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859–868 (1992)

    Article  MathSciNet  Google Scholar 

  40. Merkle, R.C.: A digital signature based on a conventional encryption function. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 369–378. Springer, Heidelberg (1988). https://doi.org/10.1007/3-540-48184-2_32

    Chapter  Google Scholar 

  41. Micali, S.: Computationally sound proofs. SIAM J. Comput. (2000)

    Google Scholar 

  42. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: S&P 2013, pp. 238–252 (2013)

    Google Scholar 

  43. Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 71–89. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_5

    Chapter  Google Scholar 

  44. Turkowski, K.: Filters for common resampling tasks. In: Graphics Gems, pp. 147–165. Academic Press Professional, Inc. (1990)

    Google Scholar 

  45. Vu, V., Setty, S., Blumberg, A.J., Walfish, M.: A hybrid architecture for interactive verifiable computation. In: Proceedings of the 2013 IEEE Symposium on Security and Privacy, SP 2013 (2013)

    Google Scholar 

  46. Wahby, R.S., et al.: Full accounting for verifiable outsourcing. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. ACM (2017)

    Google Scholar 

  47. Wahby, R.S., Setty, S.T., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: NDSS (2015)

    Google Scholar 

  48. Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 926–943. IEEE (2018)

    Google Scholar 

  49. Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint (2017)

    Google Scholar 

  50. Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vSQL: verifying arbitrary SQL queries over dynamic outsourced databases. In: 2017 IEEE Symposium on Security and Privacy (SP), pp. 863–880. IEEE (2017)

    Google Scholar 

  51. Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vRAM: faster verifiable RAM with program-independent preprocessing. In: Proceeding of IEEE Symposium on Security and Privacy (S&P) (2018)

    Google Scholar 

Download references

Acknowledgments

This material is in part based upon work supported by DARPA under Grant No. N66001-15-C-4066 and Center for Long-Term Cybersecurity (CLTC). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA or CLTC. Charalampos Papamanthou’s work was supported by NSF grants #1652259 and #1514261 and by a NIST grant.

Author information

Authors and Affiliations

  1. University of California, Berkeley, USA

    Tiacheng Xie, Jiaheng Zhang, Yupeng Zhang & Dawn Song

  2. Texas A&M University, College Station, USA

    Yupeng Zhang

  3. University of Maryland, College Park, USA

    Charalampos Papamanthou

Authors
  1. Tiacheng Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jiaheng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yupeng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Charalampos Papamanthou
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Dawn Song
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Tiacheng Xie or Jiaheng Zhang .

Editor information

Editors and Affiliations

  1. Georgia Institute of Technology, Atlanta, GA, USA

    Alexandra Boldyreva

  2. University of California at San Diego, La Jolla, CA, USA

    Daniele Micciancio

Rights and permissions

Reprints and permissions

Copyright information

© 2019 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Xie, T., Zhang, J., Zhang, Y., Papamanthou, C., Song, D. (2019). Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation. In: Boldyreva, A., Micciancio, D. (eds) Advances in Cryptology – CRYPTO 2019. CRYPTO 2019. Lecture Notes in Computer Science(), vol 11694. Springer, Cham. https://doi.org/10.1007/978-3-030-26954-8_24

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-26954-8_24

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-26953-1

  • Online ISBN: 978-3-030-26954-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation