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

Yuri Bespalov, Alberto Garoffolo, Lyudmila Kovalchuk, Hanna Nelasa and Roman Oliynykov
Additional contact information
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

Mathematics, 2021, vol. 9, issue 23, 1-31

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.

Keywords: blockchain; perfect binary tree; lumping/factorization of Markov chains; product of Markov chains; Stirling numbers of the second kind; asymptotic of Stirling numbers; coupon collector’s problem; classical occupancy distribution; probability on posets; Birkhoff duality (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/23/3016/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/23/3016/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:23:p:3016-:d:687220

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().