IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i23p3016-d687220.html
   My bibliography  Save this article

Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains

Author

Listed:
  • Yuri Bespalov

    (Bogolyubov Institute for Theoretical Physics, 03143 Kiev, Ukraine)

  • Alberto Garoffolo

    (Horizen, 20121 Milan, Italy)

  • Lyudmila Kovalchuk

    (IOHK Research, Hong Kong)

  • Hanna Nelasa

    (Department of Information Security, Zaporizhzhia Polytechnic National University, 69063 Zaporizhzhia, Ukraine)

  • Roman Oliynykov

    (IOHK Research, Hong Kong)

Abstract

The paper is devoted to the investigation of the distributed proof generation process, which makes use of recursive zk-SNARKs. Such distributed proof generation, where recursive zk-SNARK-proofs are organized in perfect Mercle trees, was for the first time proposed in Latus consensus protocol for zk-SNARKs-based sidechains. We consider two models of a such proof generation process: the simplified one, where all proofs are independent (like one level of tree), and its natural generation, where proofs are organized in partially ordered set (poset), according to tree structure. Using discrete Markov chains for modeling of corresponding proof generation process, we obtained the recurrent formulas for the expectation and variance of the number of steps needed to generate a certain number of independent proofs by a given number of provers. We asymptotically represent the expectation as a function of the one variable n/m , where n is the number of provers m is the number of proofs (leaves of tree). Using results obtained, we give numerical recommendation about the number of transactions, which should be included in the current block, idepending on the network parameters, such as time slot duration, number of provers, time needed for proof generation, etc.

Suggested Citation

  • Yuri Bespalov & Alberto Garoffolo & Lyudmila Kovalchuk & Hanna Nelasa & Roman Oliynykov, 2021. "Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains," Mathematics, MDPI, vol. 9(23), pages 1-31, November.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:23:p:3016-:d:687220
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/23/3016/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/23/3016/
    Download Restriction: no
    ---><---

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Xavier Salleras & Sergi Rovira & Vanesa Daza, 2022. "FORT: Right-Proving and Attribute-Blinding Self-Sovereign Authentication," Mathematics, MDPI, vol. 10(4), pages 1-18, February.
    2. Rico-Peña, Juan Jesús & Arguedas-Sanz, Raquel & López-Martin, Carmen, 2023. "Models used to characterise blockchain features. A systematic literature review and bibliometric analysis," Technovation, Elsevier, vol. 123(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:23:p:3016-:d:687220. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.