Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains
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-...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-11-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/23/3016 |
| _version_ | 1797507449668763648 |
|---|---|
| author | Yuri Bespalov Alberto Garoffolo Lyudmila Kovalchuk Hanna Nelasa Roman Oliynykov |
| author_facet | Yuri Bespalov Alberto Garoffolo Lyudmila Kovalchuk Hanna Nelasa Roman Oliynykov |
| author_sort | Yuri Bespalov |
| collection | DOAJ |
| description | 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 <i>n/m</i>, where <i>n</i> is the number of provers <i>m</i> 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. |
| first_indexed | 2024-03-10T04:48:41Z |
| format | Article |
| id | doaj.art-b3f64e3c831f44e6b8b929f71430ab68 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T04:48:41Z |
| publishDate | 2021-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-b3f64e3c831f44e6b8b929f71430ab682023-11-23T02:44:46ZengMDPI AGMathematics2227-73902021-11-01923301610.3390/math9233016Probability Models of Distributed Proof Generation for zk-SNARK-Based BlockchainsYuri Bespalov0Alberto Garoffolo1Lyudmila Kovalchuk2Hanna Nelasa3Roman Oliynykov4Bogolyubov Institute for Theoretical Physics, 03143 Kiev, UkraineHorizen, 20121 Milan, ItalyIOHK Research, Hong KongDepartment of Information Security, Zaporizhzhia Polytechnic National University, 69063 Zaporizhzhia, UkraineIOHK Research, Hong KongThe 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 <i>n/m</i>, where <i>n</i> is the number of provers <i>m</i> 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.https://www.mdpi.com/2227-7390/9/23/3016blockchainperfect binary treelumping/factorization of Markov chainsproduct of Markov chainsStirling numbers of the second kindasymptotic of Stirling numbers |
| spellingShingle | Yuri Bespalov Alberto Garoffolo Lyudmila Kovalchuk Hanna Nelasa Roman Oliynykov Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains Mathematics blockchain perfect binary tree lumping/factorization of Markov chains product of Markov chains Stirling numbers of the second kind asymptotic of Stirling numbers |
| title | Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains |
| title_full | Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains |
| title_fullStr | Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains |
| title_full_unstemmed | Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains |
| title_short | Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains |
| title_sort | probability models of distributed proof generation for zk snark based blockchains |
| topic | blockchain perfect binary tree lumping/factorization of Markov chains product of Markov chains Stirling numbers of the second kind asymptotic of Stirling numbers |
| url | https://www.mdpi.com/2227-7390/9/23/3016 |
| work_keys_str_mv | AT yuribespalov probabilitymodelsofdistributedproofgenerationforzksnarkbasedblockchains AT albertogaroffolo probabilitymodelsofdistributedproofgenerationforzksnarkbasedblockchains AT lyudmilakovalchuk probabilitymodelsofdistributedproofgenerationforzksnarkbasedblockchains AT hannanelasa probabilitymodelsofdistributedproofgenerationforzksnarkbasedblockchains AT romanoliynykov probabilitymodelsofdistributedproofgenerationforzksnarkbasedblockchains |