{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:37:58Z","timestamp":1768109878095,"version":"3.49.0"},"reference-count":36,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,3,7]],"date-time":"2023-03-07T00:00:00Z","timestamp":1678147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Research Foundation of Ukraine","award":["2020.01\/0351"],"award-info":[{"award-number":["2020.01\/0351"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Sidechains are among the most promising scalability and extended functionality solutions for blockchains. Application of zero knowledge techniques (Latus, Mina) allows for reaching high level security and general throughput, though it brings new challenges on keeping decentralization where significant effort is required for robust computation of zk-proofs. We consider a simultaneous decentralized creation of various zk-proof trees that form proof-trees sequences in sidechains in the model that combines behavior of provers, both deterministic (mutually consistent) or stochastic (independent) and types of proof trees. We define the concept of efficiency of such process, introduce its quantity measure and recommend parameters for tree creation. In deterministic cases, the sequences of published trees are ultimately periodic and ensure the highest possible efficiency (no collisions in proof creation). In stochastic cases, we obtain a universal measure of prover efficiencies given by the explicit formula in one case or calculated by a simulation model in another case. The optimal number of allowed provers\u2019 positions for a step can be set for various sidechain parameters, such as number of provers, number of time steps within one block, etc. Benefits and restrictions for utilization of non-perfect binary proof trees are also explicitly presented.<\/jats:p>","DOI":"10.3390\/cryptography7010014","type":"journal-article","created":{"date-parts":[[2023,3,8]],"date-time":"2023-03-08T01:58:22Z","timestamp":1678240702000},"page":"14","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Models for Generation of Proof Forest in zk-SNARK Based Sidechains"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0503-953X","authenticated-orcid":false,"given":"Yuri","family":"Bespalov","sequence":"first","affiliation":[{"name":"Department of Mathematical Methods in Theoretical Physics, Bogolyubov Institute for Theoretical Physics, National Academy of Sciences of Ukraine, 03143 Kiev, Ukraine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2874-7950","authenticated-orcid":false,"given":"Lyudmila","family":"Kovalchuk","sequence":"additional","affiliation":[{"name":"Input Output, 61022 Kharkiv, Ukraine"},{"name":"G. E. Pukhov Institute for Modelling in Energy Engineering, National Academy of Sciences of Ukraine, 03164 Kyiv, Ukraine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3708-0089","authenticated-orcid":false,"given":"Hanna","family":"Nelasa","sequence":"additional","affiliation":[{"name":"Department of Information Security, National University \u201cZaporizhzhia Polytechnic\u201d, 69063 Zaporizhzhia, Ukraine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3494-0493","authenticated-orcid":false,"given":"Roman","family":"Oliynykov","sequence":"additional","affiliation":[{"name":"Input Output, 61022 Kharkiv, Ukraine"},{"name":"Department of Information Systems and Technologies Security, V. N. Karazin Kharkiv National University, 61022 Kharkiv, Ukraine"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Viglione","sequence":"additional","affiliation":[{"name":"Horizen Labs, Austin, TX 78701, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,3,7]]},"reference":[{"key":"ref_1","unstructured":"Back, A., Corallo, M., Dashjr, L., Friedenbach, M., Maxwell, G., Miller, A., Poelstra, A., Tim\u00f3n, J., and Wuille, P. (2023, February 27). Enabling Blockchain Innovations with Pegged Sidechains. Available online: https:\/\/blockstream.com\/sidechains.pdf."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ga\u017ei, P., Kiayias, A., and Zindros, D. (2019, January 19\u201323). Proof-of-work sidechains. Proceedings of the 2019 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA.","DOI":"10.1109\/SP.2019.00040"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Garoffolo, A., Kaidalov, D., and Oliynykov, R. (December, January 29). Zendoo: A zk-SNARK Verifiable Cross-Chain Transfer Protocol Enabling Decoupled and Decentralized Sidechains. Proceedings of the 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), Singapore.","DOI":"10.1109\/ICDCS47774.2020.00161"},{"key":"ref_4","unstructured":"Garoffolo, A., and Viglione, R. (2018). Sidechains: Decoupled Consensus Between Chains. arXiv."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-662-46803-6_10","article-title":"The bitcoin backbone protocol: Analysis and applications","volume":"Volume 9057","author":"Garay","year":"2015","journal-title":"Advances in Cryptology\u2014EUROCRYPT 2015, Part II"},{"key":"ref_6","unstructured":"Ben-Sasson, E., Chiesa, A., Tromer, E., and Virza, M. (2014, January 20\u201322). Succinct Non-Interactive Zero Knowledge for a von Neumann architecture. Proceedings of the 2014 23rd USENIX Conference on Security Symposium\u2014SEC\u201914, San Diego, CA, USA. Available online: https:\/\/dl.acm.org\/doi\/abs\/10.5555\/2671225.2671275."},{"key":"ref_7","unstructured":"Bowe, S., and Gabizon, A. (2023, February 27). Making Groth\u2019s zk-SNARK Simulation Extractable in the Random Oracle Model. Available online: https:\/\/ia.cr\/2018\/187."},{"key":"ref_8","unstructured":"Bonneau, J., Meckler, I., Rao, V., and Shapiro, E. (2023, February 27). Coda: Decentralized Cryptocurrency at Scale. Cryptology ePrint Archive, Report 2020\/352. Available online: https:\/\/ia.cr\/2020\/352."},{"key":"ref_9","unstructured":"Matter Labs (2023, February 27). zkSync Era Basics. Available online: https:\/\/era.zksync.io\/docs\/dev\/fundamentals\/zkSync.html."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Och\u00f4a, I.S., Silva, L.A., de Mello, G., Garcia, N.M., de Paz Santana, J.F., and Leithardt, V.R.Q. (2020). A Cost Analysis of Implementing a Blockchain Architecture in a Smart Grid Scenario Using Sidechains. Sensors, 20.","DOI":"10.3390\/s20030843"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Zhou, J., Wang, N., Liu, A., Wang, W., and Du, X. (2023). CBCS: A Scalable Consortium Blockchain Architecture Based on World State Collaborative Storage. Electronics, 12.","DOI":"10.3390\/electronics12030735"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lee, N.Y. (2021). Hierarchical Multi-Blockchain System for Parallel Computation in Cryptocurrency Transfers and Smart Contracts. Appl. Sci., 11.","DOI":"10.3390\/app112110173"},{"key":"ref_13","unstructured":"Garoffolo, A., Kaidalov, D., and Oliynykov, R. (2023, February 27). Trustless Cross-chain Communication for Zendoo Sidechains. Cryptology ePrint Archive, Report 2022\/1179. Available online: https:\/\/ia.cr\/2022\/1179."},{"key":"ref_14","unstructured":"Kiayias, A., and Zindros, D. (2023, February 27). Proof-of-Work Sidechains. Cryptology ePrint Archive, Report 2018\/1048. Available online: https:\/\/ia.cr\/2018\/1048."},{"key":"ref_15","unstructured":"Ga\u017ei, P., Kiayias, A., and Zindros, D. (2023, February 27). Proof-of-Stake Sidechains. Cryptology ePrint Archive, Report 2018\/1239. Available online: https:\/\/ia.cr\/2018\/1239."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/978-3-319-63688-7_12","article-title":"Ouroboros: A provably secure proof-of-stake blockchain protocol","volume":"Volume 10401","author":"Kiayias","year":"2017","journal-title":"CRYPTO 2017, Part I"},{"key":"ref_17","unstructured":"Eagen, L. (2023, February 27). \u03bcCash: Transparent Anonymous Transactions. Cryptology ePrint Archive, Report 2022\/1104. Available online: https:\/\/ia.cr\/2022\/1104."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bespalov, Y., Garoffolo, A., Kovalchuk, L., Nelasa, H., and Oliynykov, R. (2021). Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains. Mathematics, 9.","DOI":"10.3390\/math9233016"},{"key":"ref_19","first-page":"47","article-title":"Game-Theoretic View on Decentralized Proof Generation in zk-SNARK Based Sidechains","volume":"Volume 2923","author":"Bespalov","year":"2021","journal-title":"CEUR Workshop Proceedings, Cybersecurity Providing in Information and Telecommunication Systems (CPITS 2021), Kyiv, Ukraine, 28 January 2021"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Bespalov, Y., Kovalchuk, L., Nelasa, H., Oliynykov, R., and Garoffolo, A. (2022, January 7\u20139). Game theory analysis of incentive distribution for prompt generation of the proof tree in zk-SNARK based sidechains. Proceedings of the 2022 IEEE International Carnahan Conference on Security Technology (ICCST), Valec u Hrotovic, Czech Republic.","DOI":"10.1109\/ICCST52959.2022.9896484"},{"key":"ref_21","unstructured":"Bonneau, J., Meckler, I., Rao, V., and Shapiro, E. (2023, February 27). Mina: Decentralized Cryptocurrency at Scale. Available online: https:\/\/minaprotocol.com\/wp-content\/uploads\/technicalWhitepaper.pdf."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cioab\u0103, S.M., and Murty, M.R. (2022). A First Course in Graph Theory and Combinatorics, Cambridge University Press. Texts and Readings in Mathematics 55.","DOI":"10.1007\/978-981-19-0957-3_5"},{"key":"ref_23","unstructured":"Bourbaki, N. (1998). Algebra I. Chapters 1\u20133, Springer."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Reutenauer, C. (1993). Free Lie Algebras, Oxford University Press.","DOI":"10.1093\/oso\/9780198536796.001.0001"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Stanley, R.P. (2015). Catalan Numbers, Cambridge University Press.","DOI":"10.1017\/CBO9781139871495"},{"key":"ref_26","unstructured":"Johnson, N.L., and Kotz, S. (1977). Urn Models and Their Applications, John Wiley and Sons."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1080\/00031305.2019.1699445","article-title":"The Classical Occupancy Distribution: Computation and Approximation","volume":"75","year":"2021","journal-title":"Am. Stat."},{"key":"ref_28","unstructured":"Kanani, J., Nailwal, S., and Arjun, A. (2023, February 27). Matic Whitepaper. Available online: https:\/\/github.com\/maticnetwork\/whitepaper."},{"key":"ref_29","unstructured":"Kuszmaul, J. (2018, January 19\u201320). Verkle Trees. Proceedings of the Eighth Annual PRIMES Conference, Available online: https:\/\/math.mit.edu\/research\/highschool\/primes\/materials\/2018\/Kuszmaul.pdf."},{"key":"ref_30","unstructured":"Campanelli, M., Hall-Andersen, M., and Kamp, S.H. (2023, February 27). Curve Trees: Practical and Transparent Zero-Knowledge Accumulators. Cryptology ePrint Archive, Report 2022\/756. Available online: https:\/\/ia.cr\/2022\/756."},{"key":"ref_31","unstructured":"Mac Lane, S. (1998). Categories for the Working Mathematician, Springer. [2nd ed.]. Graduate Texts in Mathematics 5."},{"key":"ref_32","unstructured":"Awodey, S. (2010). Category Theory, Oxford University Press. [2nd ed.]. Oxforg Logic Guides 52."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Leinster, T. (2014). Basic Category Theory, Cambridge University Press. Cambridge Studies in Advanced Mathematics 143.","DOI":"10.1017\/CBO9781107360068"},{"key":"ref_34","unstructured":"Markl, M., Shnider, S., and Stasheff, J.D. (2002). Operads in Algebra, Topology and Physics, AMS. Mathematical Surveys and Monographs 96."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"M\u00e9ndez, M.A. (2015). Set Operads in Combinatorics and Computer Science, Springer. SpringerBriefs in Mathematics.","DOI":"10.1007\/978-3-319-11713-3"},{"key":"ref_36","unstructured":"Spivak, D.I. (2014). Category Theory for the Sciences, MIT Press."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/1\/14\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:50:21Z","timestamp":1760122221000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/7\/1\/14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,7]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,3]]}},"alternative-id":["cryptography7010014"],"URL":"https:\/\/doi.org\/10.3390\/cryptography7010014","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,7]]}}}