Modelos de probabilidad de generación distribuida de pruebas para blockchains basados en zk-SNARK
Autores: Bespalov, Yuri; Garoffolo, Alberto; Kovalchuk, Lyudmila; Nelasa, Hanna; Oliynykov, Roman
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Modelos de probabilidad de generación distribuida de pruebas para blockchains basados en zk-SNARK
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Investigación
Generación distribuida de pruebas
Zk-SNARKs recursivos
árboles de Merkle
Protocolo de consenso Latus
Sidechains
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
El documento está dedicado a la investigación del proceso de generación de pruebas distribuidas, que hace uso de zk-SNARKs recursivos. Tal generación de pruebas distribuidas, donde las pruebas zk-SNARK recursivas se organizan en árboles de Mercle perfectos, fue propuesta por primera vez en el protocolo de consenso Latus para cadenas laterales basadas en zk-SNARKs. Consideramos dos modelos de un proceso de generación de pruebas de este tipo: el simplificado, donde todas las pruebas son independientes (como un nivel de árbol), y su generación natural, donde las pruebas se organizan en un conjunto parcialmente ordenado (poset), de acuerdo con la estructura del árbol. Utilizando cadenas de Markov discretas para modelar el proceso de generación de pruebas correspondiente, obtuvimos las fórmulas recurrentes para la esperanza y la varianza del número de pasos necesarios para generar un cierto número de pruebas independientes por un número dado de probadores. Representamos asintóticamente la esperanza como una función de una variable, donde es el número de probadores y es el número de pruebas (hojas del árbol). Utilizando los resultados obtenidos, damos recomendaciones numéricas sobre el número de transacciones que deberían incluirse en el bloque actual, dependiendo de los parámetros de la red, como la duración del intervalo de tiempo, el número de probadores, el tiempo necesario para la generación de pruebas, etc.
Descripción
El documento está dedicado a la investigación del proceso de generación de pruebas distribuidas, que hace uso de zk-SNARKs recursivos. Tal generación de pruebas distribuidas, donde las pruebas zk-SNARK recursivas se organizan en árboles de Mercle perfectos, fue propuesta por primera vez en el protocolo de consenso Latus para cadenas laterales basadas en zk-SNARKs. Consideramos dos modelos de un proceso de generación de pruebas de este tipo: el simplificado, donde todas las pruebas son independientes (como un nivel de árbol), y su generación natural, donde las pruebas se organizan en un conjunto parcialmente ordenado (poset), de acuerdo con la estructura del árbol. Utilizando cadenas de Markov discretas para modelar el proceso de generación de pruebas correspondiente, obtuvimos las fórmulas recurrentes para la esperanza y la varianza del número de pasos necesarios para generar un cierto número de pruebas independientes por un número dado de probadores. Representamos asintóticamente la esperanza como una función de una variable, donde es el número de probadores y es el número de pruebas (hojas del árbol). Utilizando los resultados obtenidos, damos recomendaciones numéricas sobre el número de transacciones que deberían incluirse en el bloque actual, dependiendo de los parámetros de la red, como la duración del intervalo de tiempo, el número de probadores, el tiempo necesario para la generación de pruebas, etc.