Skip to main content
SpringerLink
Log in

Publicly Verifiable Zero Knowledge from (Collapsing) Blockchains

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2021 (PKC 2021)

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

Included in the following conference series:

Abstract

Publicly Verifiable Zero-Knowledge proofs are known to exist only from setup assumptions such as a trusted common reference string or a random oracle. Unfortunately, the former requires a trusted party while the latter does not exist.

Blockchains are distributed systems that already exist and provide certain security properties (under some honest majority assumption), hence, a natural recent research direction has been to use a blockchain as an alternative setup assumption.

In TCC 2017 Goyal and Goyal proposed a construction of a publicly verifiable zero-knowledge (pvZK) proof system for some proof-of-stake blockchains. The zero-knowledge property of their construction however relies on some additional and not fully specified assumptions about the current and future behavior of honest blockchain players.

In this paper we provide several contributions. First, we show that when using a blockchain to design a provably secure protocol, it is dangerous to rely on demanding additional requirements on behaviors of the blockchain players. We do so by showing an “attack of the clones” whereby a malicious verifier can use a smart contract to slyly (not through bribing) clone capabilities of honest stakeholders and use those to invalidate the zero-knowledge property of the proof system by Goyal and Goyal.

Second, we propose a new publicly verifiable zero-knowledge proof system that relies on non-interactive commitments and on an assumption on the min-entropy of some blocks appearing on the blockchain.

Third, motivated by the fact that blockchains are a recent innovation and their resilience in the long run is still controversial, we introduce the concept of collapsing blockchain, and we prove that the zero-knowledge property of our scheme holds even if the blockchain eventually becomes insecure and all blockchain players eventually become dishonest.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    We note that this threat model was never considered before. [34] only made observations about additional limitations that GG-NIZK imposes on their underlying blockchain. Instead, in this work we are showing an attack that works for any PoS blockchain (even the ones that comply with GG-NIZK pre-requirement) allowing the execution of such smart contracts.

  2. 2.

    Here we refer to wallets identifying the block leader cashing the reward and not to wallets involved in transactions.

  3. 3.

    See the paragraph below about the power of the adversary.

  4. 4.

    Our results were publicly announced in [1] way before we have noticed CVZK, therefore the two works are independent.

  5. 5.

    The role of \(s_1,s_2\) and \(\beta \) is not relevant for our discussion and therefore they can be ignored.

  6. 6.

    In order to simplify the notation we make an abuse of notation and we explicitly add the blockchain as input of \(\mathsf{GenBlock}\) even though the blockchain can be computed running \(\mathsf {GetRecords}\) on input \(\mathsf {st}\).

  7. 7.

    In the existing blockchains the value v could be an identifier of a wallet and \(f_\mathsf{ID}\) is the randomized function that generates it.

  8. 8.

    In the sense of the underlying consensus mechanism.

  9. 9.

    For instance, they require that any broadcasted message is delivered in a maximum number of time steps.

  10. 10.

    Note that the execution of \(\varGamma ^\mathsf {V}_\mathsf {view}(\mathcal {A}, \mathcal {H}, \mathcal {Z}, 1^\lambda )\) could continue even after \(\pi \) is provided by \(\mathcal {P}\).

References

  1. Pencil - workshop on privacy enhancing cryptography in ledgers (2019). https://priviledge-project.eu/pencil

  2. Aggarwal, D., Obremski, M., Ribeiro, J., Siniscalchi, L., Visconti, I.: How to extract useful randomness from unreliable sources. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 343–372. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_13

    Chapter  Google Scholar 

  3. Badertscher, C., Garay, J., Maurer, U., Tschudi, D., Zikas, V.: But why does it work? A rational protocol design treatment of bitcoin. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 34–65. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_2

    Chapter  Google Scholar 

  4. Badertscher, C., Gazi, P., Kiayias, A., Russell, A., Zikas, V.: Ouroboros genesis: composable proof-of-stake blockchains with dynamic availability. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, 15–19 October 2018, pp. 913–930 (2018)

    Google Scholar 

  5. Badertscher, C., Maurer, U., Tschudi, D., Zikas, V.: Bitcoin as a transaction ledger: a composable treatment. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 324–356. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_11

    Chapter  Google Scholar 

  6. Baldimtsi, F., Kiayias, A., Zacharias, T., Zhang, B.: Crowd verifiable zero-knowledge and end-to-end verifiable multiparty computation. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12493, pp. 717–748. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_24

    Chapter  Google Scholar 

  7. Barak, B.: How to go beyond the black-box simulation barrier. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, , Las Vegas, Nevada, USA, 14–17 October 2001, pp. 106–115. IEEE Computer Society (2001)

    Google Scholar 

  8. Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995). https://doi.org/10.1007/BFb0053428

    Chapter  Google Scholar 

  9. Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasi-linear size zero knowledge from linear-algebraic PCPs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 33–64. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49099-0_2

    Chapter  Google Scholar 

  10. Benhamouda, F., et al.: Can a public blockchain keep a secret? In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 260–290. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64375-1_10

    Chapter  Google Scholar 

  11. Bentov, I., Gabizon, A., Zuckerman, D.: Bitcoin beacon. CoRR abs/1605.04559 (2016)

    Google Scholar 

  12. Bentov, I., Kumaresan, R.: How to use bitcoin to design fair protocols. IACR Crypto. ePrint Arch. 2014, 129 (2014)

    MATH  Google Scholar 

  13. Bonneau, J., Clark, J., Goldfeder, S.: On bitcoin as a public randomness source. Cryptology ePrint Archive, Report 2015/1015 (2015). https://eprint.iacr.org/2015/1015

  14. Bowe, S., Gabizon, A., Green, M.D.: A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. In: Zohar, A., et al. (eds.) FC 2018. LNCS, vol. 10958, pp. 64–77. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-58820-8_5

    Chapter  Google Scholar 

  15. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, 14–17 October 2001, pp. 136–145. IEEE Computer Society (2001)

    Google Scholar 

  16. Choudhuri, A.R., Goyal, V., Jain, A.: Founding secure computation on blockchains. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 351–380. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_13

    Chapter  Google Scholar 

  17. Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, 22–24 October 1990, vol. 1, pp. 308–317. IEEE Computer Society (1990)

    Google Scholar 

  18. Ganesh, C., Orlandi, C., Tschudi, D.: Proof-of-stake protocols for privacy-aware blockchains. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 690–719. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_23

    Chapter  Google Scholar 

  19. Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10

    Chapter  Google Scholar 

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

  21. Gentry, C., Halevi, S., Magri, B., Nielsen, J.B., Yakoubov, S.: Random-index PIR with applications to large-scale secure MPC. Cryptology ePrint Archive, Report 2020/1248 (2020). https://eprint.iacr.org/2020/1248

  22. Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling Byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, 28–31 October 2017, pp. 51–68 (2017)

    Google Scholar 

  23. Goyal, R., Goyal, V.: Overcoming cryptographic impossibility results using blockchains. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 529–561. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_18

    Chapter  Google Scholar 

  24. Goyal, R., Goyal, V.: Overcoming cryptographic impossibility results using blockchains. Cryptology ePrint Archive, Report 2017/935 (2017). https://eprint.iacr.org/2017/935

  25. Goyal, V., Kothapalli, A., Masserova, E., Parno, B., Song, Y.: Storing and retrieving secrets on a blockchain. IACR Cryptol. ePrint Arch. 2020, 504 (2020)

    Google Scholar 

  26. Groth, J., Kohlweiss, M., Maller, M., Meiklejohn, S., Miers, I.: Updatable and universal common reference strings with applications to zk-SNARKs. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 698–728. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_24

    Chapter  Google Scholar 

  27. Juels, A., Kosba, A.E., Shi, E.: The ring of gyges: investigating the future of criminal smart contracts. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 283–295 (2016)

    Google Scholar 

  28. Kerber, T., Kiayias, A., Kohlweiss, M., Zikas, V.: Ouroboros crypsinous: privacy-preserving proof-of-stake. In: 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, 19–23 May 2019, pp. 157–174. IEEE (2019)

    Google Scholar 

  29. Kiayias, A., Panagiotakos, G.: Speed-security tradeoffs in blockchain protocols. IACR Cryptology ePrint Archive: Report 2015/1019 (2015). http://eprint.iacr.org/2015/1019

  30. Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge SNARKs from linear-size universal and updatable structured reference strings. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, 11–15 November 2019, pp. 2111–2128. ACM (2019)

    Google Scholar 

  31. Nakamoto, S.: Bitcoin: a peer-to-peer electionic cash system (2008, unpublished)

    Google Scholar 

  32. Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643–673. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_22

    Chapter  MATH  Google Scholar 

  33. Pass, R., Shi, E.: The sleepy model of consensus. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 380–409. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_14

    Chapter  Google Scholar 

  34. Scafuro, A., Siniscalchi, L., Visconti, I.: Publicly verifiable proofs from blockchains. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11442, pp. 374–401. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17253-4_13

    Chapter  Google Scholar 

  35. Scafuro, A., Siniscalchi, L., Visconti, I.: Publicly verifiable zero knowledge from (collapsing) blockchains. Cryptology ePrint Archive, Report 2020/1435. https://eprint.iacr.org/2020/1435

Download references

Acknowledgments

Research supported in part by NSF grants #1012798,#1764025, and in part by the European Union’s Horizon 2020 research and innovation programme under grant agreement No 780477 (project PRIViLEDGE).

Author information

Authors and Affiliations

  1. North Carolina State University, Raleigh, USA

    Alessandra Scafuro

  2. Concordium Blockchain Research Center, Aarhus University, Aarhus, Denmark

    Luisa Siniscalchi

  3. DIEM, University of Salerno, Fisciano, Italy

    Ivan Visconti

Authors
  1. Alessandra Scafuro
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Luisa Siniscalchi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ivan Visconti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alessandra Scafuro .

Editor information

Editors and Affiliations

  1. Texas A&M University, College Station, TX, USA

    Juan A. Garay

Rights and permissions

Reprints and permissions

Copyright information

© 2021 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Scafuro, A., Siniscalchi, L., Visconti, I. (2021). Publicly Verifiable Zero Knowledge from (Collapsing) Blockchains. In: Garay, J.A. (eds) Public-Key Cryptography – PKC 2021. PKC 2021. Lecture Notes in Computer Science(), vol 12711. Springer, Cham. https://doi.org/10.1007/978-3-030-75248-4_17

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75248-4_17

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75247-7

  • Online ISBN: 978-3-030-75248-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation