Conceptos básicos de fragmentación

Comencemos con el enfoque más simple para fragmentar. En este enfoque en lugar de Al ejecutar un blockchain, ejecutaremos varios y llamaremos a cada uno de ellos blockchain como “fragmento”. Cada fragmento tendrá su propio conjunto de validators. Aquí y abajo utilizamos un término genérico “validator” para referirse a los participantes que verifican transacciones y producir bloques, ya sea mediante minería, como en Prueba de trabajo, o mediante una votación 1Esta sección se publicó anteriormente en https://near.ai/shard1. Si la leyó antes, salte a la siguiente sección.

mecanismo. Por ahora supongamos que los fragmentos nunca se comunican entre sí. otro. Este diseño, aunque simple, es suficiente para esbozar algunos de los principales desafíos iniciales en la fragmentación. 1.1 Partición de validadores y cadenas de balizas Digamos que el sistema consta de 10 fragmentos. El primer desafío es que con cada fragmento que tiene sus propios validators, cada fragmento ahora es 10 veces menos seguro que el cadena entera. Entonces, si una cadena no fragmentada con X validators decide realizar un hard-fork en una cadena fragmentada y divide X validators en 10 fragmentos, cada fragmento ahora solo tiene X/10 validators, y corromper un fragmento solo requiere corromper 5,1% (51% / 10) del número total de validators (ver figura 1), Figura 1: Dividiendo los validators en fragmentos lo que nos lleva al segundo punto: ¿quién elige validators para cada fragmento? Controlar el 5,1% de validators solo es perjudicial si todos esos 5,1% de validators están en el mismo fragmento. Si validators no pueden elegir qué fragmento validar En, es muy poco probable que un participante que controle el 5,1% de los validator obtenga todos sus validators en el mismo fragmento, lo que reduce en gran medida su capacidad de comprometerse el sistema. Casi todos los diseños de fragmentación actuales dependen de alguna fuente de aleatoriedad para asigne validators a fragmentos. La aleatoriedad en blockchain en sí misma es un tema muy desafiante y está fuera del alcance de este documento. Por ahora supongamos que hay alguna fuente de aleatoriedad que podamos utilizar. Cubriremos la tarea de validator en más detalle en la sección 2.1. Tanto la aleatoriedad como la asignación validator requieren un cálculo que no es específico de cualquier fragmento en particular. Para ese cómputo, prácticamente todos los existentes Los diseños tienen un blockchain separado que se encarga de realizar las operaciones. necesarios para el mantenimiento de toda la red. Además de generar aleatorionúmeros y asignando validators a los fragmentos, estas operaciones a menudo también incluir recibir actualizaciones de fragmentos y tomar instantáneas de ellos, procesar apuestas y recortes en los sistemas de prueba de participación, y reequilibrio de fragmentos cuando eso La función es compatible. Dicha cadena se denomina cadena de baliza en Ethereum, retransmisión cadena en PolkaDot y el Cosmos Hub en Cosmos. A lo largo de este documento nos referiremos a dicha cadena como cadena Beacon. La existencia de la cadena Beacon nos lleva al siguiente tema interesante, el fragmentación cuadrática. 1.2 fragmentación cuadrática La fragmentación a menudo se anuncia como una solución que escala infinitamente con el número de nodos que participan en la operación de la red. Si bien en teoría es posible diseñar una solución de fragmentación de este tipo, cualquier solución que tenga el concepto de Beacon La cadena no tiene una escalabilidad infinita. Para entender por qué, tenga en cuenta que Beacon cadena tiene que hacer algunos cálculos contables, como asignar validators a fragmentos, o instantáneas de bloques de cadena de fragmentos, que es proporcional al número de fragmentos en el sistema. Dado que la cadena Beacon es en sí misma un único blockchain, con computación limitada por las capacidades computacionales de los nodos que la operan, la cantidad de fragmentos es naturalmente limitada. Sin embargo, la estructura de una red fragmentada otorga un efecto multiplicativo. efecto sobre cualquier mejora en sus nodos. Consideremos el caso en el que una decisión arbitraria Se realiza una mejora en la eficiencia de los nodos de la red que permitirá ellos tiempos de procesamiento de transacciones más rápidos. Si los nodos que operan la red, incluidos los nodos de la cadena Beacon, se vuelve cuatro veces más rápido, entonces cada fragmento podrá procesar cuatro veces más transacciones, y la cadena Beacon podrá mantener 4 veces más fragmentos. El rendimiento en todo el sistema aumentará en un factor de 4 × 4 = 16 - de ahí el nombre de fragmentación cuadrática. Es difícil proporcionar una medición precisa de cuántos fragmentos hay viable hoy, pero es poco probable que en un futuro previsible el rendimiento Las necesidades de los usuarios blockchain superarán las limitaciones de la fragmentación cuadrática. La gran cantidad de nodos necesarios para operar tal volumen de fragmentos de forma segura es probablemente órdenes de magnitud mayor que el número de nodos que operan todos los blockchains combinados hoy. 1.3 fragmentación de estado Hasta ahora no hemos definido muy bien qué es exactamente lo que está y qué no está separado cuando una red se divide en fragmentos. Específicamente, los nodos en el blockchain realizan tres tareas importantes: no sólo 1) procesan transacciones, también también 2) transmitir transacciones validadas y bloques completados a otros nodos y 3) almacenar el estado y el historial de todo el libro mayor de la red. Cada uno de estos tres tareas impone una exigencia creciente a los nodos que operan la red:1. La necesidad de procesar transacciones requiere más potencia informática con el mayor número de transacciones procesadas; 2. La necesidad de retransmitir transacciones y bloques requiere más ancho de banda de red debido al mayor número de transacciones que se retransmiten; 3. La necesidad de almacenar datos requiere más almacenamiento a medida que crece el estado. Es importante destacar que, a diferencia de la potencia de procesamiento y la red, el requisito de almacenamiento crece incluso si la tasa de transacción (número de transacciones procesadas por segundo) permanece constante. De la lista anterior podría parecer que el requisito de almacenamiento sería el más apremiante, ya que es el único que se va incrementando con el tiempo incluso si el número de transacciones por segundo no cambia, pero en la práctica El requisito más urgente hoy en día es la potencia informática. todo el estado de Ethereum al momento de escribir este artículo es de 100 GB, fácilmente manejable por la mayoría de los nodos. Pero el número de transacciones que Ethereum puede procesar es de alrededor de 20, órdenes de magnitud menor de lo que se necesita para muchos casos de uso práctico. Zilliqa es el proyecto más conocido que fragmenta el procesamiento pero no el almacenamiento. La fragmentación del procesamiento es un problema más fácil porque cada nodo tiene la totalidad estado, lo que significa que los contratos pueden invocar libremente otros contratos y leer cualquier dato del blockchain. Se necesita una ingeniería cuidadosa para garantizar las actualizaciones. de múltiples fragmentos que actualizan las mismas partes del estado no entran en conflicto. en En ese sentido, Zilliqa está adoptando un enfoque relativamente simplista2. Si bien se propuso fragmentar el almacenamiento sin fragmentar el procesamiento, es extremadamente poco común. Así, en la práctica, la fragmentación del almacenamiento, o fragmentación del estado, casi siempre implica fragmentación del procesamiento y fragmentación de la red. En la práctica, bajo State Sharding, los nodos de cada fragmento están construyendo su propio blockchain que contiene transacciones que afectan sólo la parte local del estado global que está asignado a ese fragmento. Por lo tanto, los validators en el El fragmento solo necesita almacenar su parte local del estado global y solo ejecutarse, y como tal sólo transmiten transacciones que afectan su parte del estado. esto La partición reduce linealmente los requisitos de toda la potencia informática, el almacenamiento y la ancho de banda de la red, pero introduce nuevos problemas, como la disponibilidad de datos y transacciones entre fragmentos, las cuales cubriremos a continuación. 1.4 Transacciones entre fragmentos El modelo de fragmentación que describimos hasta ahora no es muy útil, porque si los individuos Los fragmentos no pueden comunicarse entre sí, no son mejores que múltiples blockchains independientes. Incluso hoy en día, cuando la fragmentación no está disponible, existe una enorme demanda de interoperabilidad entre varios blockchains. Por ahora, consideremos solo transacciones de pago simples, donde cada participante tiene una cuenta en exactamente un fragmento. Si uno desea transferir dinero desde 2Nuestro análisis de su enfoque se puede encontrar aquí: https://medium.com/nearprotocol/ 8f9efae0ce3buna cuenta a otra dentro del mismo fragmento, la transacción se puede procesar enteramente por los validators en ese fragmento. Sin embargo, si Alice reside en el fragmento

1 quiere enviar dinero a Bob que reside en el fragmento #2, ni a validators

en el fragmento #1 (no podrán acreditar la cuenta de Bob) ni los validators en El fragmento #2 (no podrán debitar la cuenta de Alice) puede procesar todo el proceso. transacción. Hay dos familias de enfoques para las transacciones entre fragmentos: • Síncrono: siempre que sea necesario ejecutar una transacción entre fragmentos, los bloques en múltiples fragmentos que contienen transición de estado relacionada con el Todas las transacciones se producen al mismo tiempo, y los validators de múltiples fragmentos colaboran en la ejecución de dichas transacciones.3 • Asíncrono: una transacción entre fragmentos que afecta a varios fragmentos. se ejecuta en esos fragmentos de forma asincrónica, el fragmento "Crédito" que se ejecuta su mitad una vez que tenga evidencia suficiente de que el fragmento "Debito" ha ejecutado su parte. Este enfoque tiende a ser más frecuente debido a su Simplicidad y facilidad de coordinación. Este sistema se propone hoy en Cosmos, Ethereum Serenity, Near, Kadena y otros. Un problema con esto El enfoque radica en que si los bloques se producen de forma independiente, existe una probabilidad distinta de cero de que uno de los múltiples bloques quede huérfano, lo que hace que la transacción sólo se aplicó parcialmente. Considere la figura 2 que muestra dos fragmentos que encontraron una bifurcación y una transacción entre fragmentos que quedó registrado en los bloques A y X’ respectivamente. Si las cadenas A-B y V’-X’-Y’-Z’ terminan siendo canónicos en los fragmentos correspondientes, el la transacción está completamente finalizada. Si A'-B'-C'-D' y V-X se vuelven canónicos, entonces la transacción se abandona por completo, lo cual es aceptable. Pero si, por Por ejemplo, A-B y V-X se vuelven canónicos, luego una parte de la transacción finaliza y otra se abandona, creando una falla de atomicidad. nosotros Cubriremos cómo se aborda este problema en los protocolos propuestos en la segunda parte, al cubrir los cambios en las reglas de elección de la bifurcación y el consenso. algoritmos propuestos para protocolos fragmentados. Tenga en cuenta que la comunicación entre cadenas es útil fuera de los blockchains fragmentados. también. La interoperabilidad entre cadenas es un problema complejo que muchos proyectos están tratando de resolver. En blockchains fragmentados el problema es algo más fácil ya que la estructura de bloques y el consenso son los mismos en todos los fragmentos, y hay una cadena de balizas que se puede utilizar para la coordinación. Sin embargo, en un blockchain fragmentado, todas las cadenas de fragmentos son iguales, mientras que en el ecosistema global de blockchains hay Hay muchos blockchain diferentes, con diferentes casos de uso objetivo, descentralización y garantías de privacidad. Construir un sistema en el que un conjunto de cadenas tengan diferentes propiedades pero usar consenso y estructura de bloques suficientemente similares y tener una cadena de baliza común podría permitir un ecosistema de blockchains heterogéneos que tengan una 3El la mayoría detallado propuesta conocido a el autores de esto documento es fusionar bloques, descrito aquí: https://ethresear.ch/t/ fusionar-bloques-y-ejecución-sincrónica-de-estado-entre-fragmentos/1240Figura 2: Transacciones asincrónicas entre fragmentos subsistema de interoperabilidad en funcionamiento. Es poco probable que dicho sistema presente rotación validator, por lo que se deben tomar algunas medidas adicionales para garantizar la seguridad. ambos Cosmos y PolkaDot son efectivamente tales sistemas4 1.5 Comportamiento malicioso En esta sección revisaremos qué comportamiento adversario pueden tener los validators maliciosos. ejercicio si logran corromper un fragmento. Revisaremos los enfoques clásicos. para evitar la corrupción de fragmentos en la sección 2.1. 1.5.1 tenedores maliciosos Un conjunto de validators maliciosos podría intentar crear una bifurcación. Tenga en cuenta que no importa si el consenso subyacente es BFT o no, corrompiendo un número suficiente de validators siempre permitirá crear una bifurcación. Es significativamente más probable que se corrompa más del 50% de un único fragmento que que se corrompa más del 50% de toda la red (veremos). profundizaremos en estas probabilidades en la sección 2.1). Como se analiza en la sección 1.4, Las transacciones entre fragmentos implican ciertos cambios de estado en múltiples fragmentos, y los bloques correspondientes en dichos fragmentos que aplican dichos cambios de estado deben estar completamente finalizado (es decir, aparecer en las cadenas seleccionadas en sus correspondientes fragmentos), o todos quedarán huérfanos (es decir, no aparecerán en las cadenas seleccionadas en sus fragmentos correspondientes). Dado que generalmente la probabilidad de que los fragmentos se corrompan 4Consulte este artículo de Zaki Manian de Cosmos: https://forum.cosmos.network/ t/polkadot-vs-cosmos/1397/2 y esta tormenta de tweets del primer autor de este documento: https://twitter.com/AlexSkidanov/status/1129511266660126720 para una comparación detallada de los dos

no es despreciable, no podemos asumir que las bifurcaciones no ocurrirán incluso si se alcanzó un consenso bizantino entre los fragmentos validators, o si se crearon muchos bloques. producido en la parte superior del bloque con el cambio de estado. Este problema tiene múltiples soluciones, siendo la más común la ocasional. reticulación del último bloque de la cadena de fragmentos con la cadena de baliza. el tenedor La regla de elección en las cadenas de fragmentos se cambia para preferir siempre la cadena que es entrecruzado y solo aplica la regla de elección de bifurcación específica de fragmentos para bloques que fueron publicado desde el último enlace cruzado. 1.5.2 Aprobar bloques no válidos Un conjunto de validator podría intentar crear un bloque que aplique la función de transición de estado incorrectamente. Por ejemplo, comenzando con un estado en el que Alice tiene 10 tokens y Bob tiene 0 tokens, el bloque podría contener una transacción que envía 10 tokens de Alice a Bob, pero termina con un estado en el que Alice tiene 0 tokens y Bob tiene 1000 tokens, como se muestra en la figura 3. Figura 3: Un ejemplo de un bloque no válido En un blockchain clásico no fragmentado, tal ataque no es posible, ya que todos el participante en la red valida todos los bloques, y el bloque con tales una transición de estado no válida será rechazada por los otros dos productores de bloques, y los participantes de la red que no crean bloques. Incluso si los maliciosos validators continúan creando bloques encima de un bloque no válido más rápido que Los validators honestos construyen la cadena correcta, teniendo así la cadena con el valor no válido. Si el bloque es más largo, no importa, ya que cada participante que esté usando el blockchain para cualquier propósito valida todos los bloques y descarta todos los bloques construido sobre el bloque no válido. En la figura 4 hay cinco validator, tres de los cuales son maliciosos. ellos creó un bloque A' no válido y luego continuó construyendo nuevos bloques encima de ello. Dos validators honestos descartaron A’ como inválida y estaban construyendo desde arribaFigura 4: Intento de crear un bloque no válido en un blockchain no fragmentado del último bloque válido conocido por ellos, creando una bifurcación. ya que hay menos validators en el tenedor honesto, su cadena es más corta. Sin embargo, en el blockchain clásico no fragmentado, cada participante que usa blockchain para cualquier propósito es responsable de validar todos los bloques que reciben y recalcular el estado. Por lo tanto, cualquier persona que tenga algún interés en el blockchain observará que A’ es inválido, y por lo tanto también descartar inmediatamente B’, C’ y D’, como tales tomando cadena A-B como la cadena válida más larga actual. Sin embargo, en un blockchain fragmentado, ningún participante puede validar todas las transacciones en todos los fragmentos, por lo que necesitan tener alguna forma de confirmar que en ningún caso. En cualquier momento del historial de cualquier fragmento de blockchain no se incluyó ningún bloque no válido. Tenga en cuenta que, a diferencia de las bifurcaciones, el enlace cruzado a la cadena Beacon no es una solución suficiente, ya que la cadena Beacon no tiene la capacidad de validar la cadena. bloques. Solo puede validar que haya una cantidad suficiente de validator en ese fragmento. firmó el bloque (y como tal dio fe de su exactitud). Discutiremos soluciones a este problema en la sección 2.2 a continuación.

Validez del estado y disponibilidad de datos

La idea central en blockchains fragmentados es que la mayoría de los participantes que operan o el uso de la red no puede validar bloques en todos los fragmentos. Como tal, siempre que cualquier participante necesita interactuar con un fragmento en particular que generalmente no puede descargue y valide el historial completo del fragmento. El aspecto de partición de la fragmentación, sin embargo, plantea un potencial significativo problema: sin descargar y validar el historial completo de un determinado fragmento, el participante no puede necesariamente estar seguro de que el estado con el que 5Esta sección, excepto la subsección 2.5.3, se publicó anteriormente en https://near.ai/ fragmento2. Si lo leíste antes, salta a la siguiente sección.

interactúan es el resultado de alguna secuencia válida de bloques y que dicha secuencia de bloques es de hecho la cadena canónica en el fragmento. Un problema que no existe en un blockchain no fragmentado. Primero presentaremos una solución simple a este problema que ha sido propuesta. por muchos protocolos y luego analizar cómo esta solución puede romperse y qué se han hecho intentos para abordarlo. 2.1 Rotación de validadores La solución ingenua a la validez del estado se muestra en la figura 5: digamos que asumimos que todo el sistema tiene del orden de miles de validators, de los cuales no más del 20% son maliciosos o fallarán de otra manera (por ejemplo, al no ser en línea para producir un bloque). Entonces, si tomamos una muestra de 200 validators, la probabilidad de más de 1 3 reprobados a efectos prácticos se puede suponer que es cero. Figura 5: Muestreo validators 1 3 es un umbral importante. Existe una familia de protocolos de consenso, llamados BFT protocolos de consenso, que garantizan que mientras menos de 1 3 de los participantes fallan, ya sea al estrellarse o al actuar de alguna manera que viole las protocolo, se alcanzará el consenso. Con esta suposición de porcentaje honesto validator, si el conjunto actual de validators en un fragmento nos proporciona algún bloque, la solución ingenua supone que el bloque es válido y que está construido sobre lo que los validators creían que era la cadena canónica para ese fragmento cuando comenzaron a validar. Los validators aprendió la cadena canónica del conjunto anterior de validators, quienes por el mismo suposición construida sobre el bloque que era la cabeza de la cadena canónica antes de eso. Por inducción toda la cadena es válida y dado que no hay un conjunto de validators en cualquier momento se producen bifurcaciones, la solución ingenua también es segura de que la corriente chain es la única cadena en el fragmento. Consulte la figura 6 para obtener una visualización.

Figura 6: Un blockchain con cada bloque finalizado mediante el consenso BFT Esta solución simple no funciona si asumimos que los validators pueden ser corrompidos adaptativamente, lo cual no es una suposición descabellada6. Adaptablemente corromper un solo fragmento en un sistema con 1000 fragmentos es significativamente más barato que corromper todo el sistema. Por tanto, la seguridad del protocolo disminuye linealmente con el número de fragmentos. Para tener certeza en la validez de un bloque, debemos saber que en cualquier momento de la historia ningún fragmento del sistema ha una mayoría de validators en connivencia; con adversarios adaptativos, ya no tenemos tal certeza. Como comentamos en la sección 1.5, los validator en colusión pueden ejercer dos comportamientos maliciosos básicos: crear bifurcaciones y producir bloques no válidos. Las bifurcaciones maliciosas pueden abordarse mediante bloques que se entrecruzan con la cadena Beacon, que generalmente está diseñada para tener una seguridad significativamente mayor que la cadena Beacon. las cadenas de fragmentos. Sin embargo, producir bloques no válidos es una tarea mucho más problema desafiante de abordar. 2.2 Validez del estado Considere la figura 7 en la que el fragmento #1 está dañado y un actor malicioso produce bloque B no válido. Supongamos que en este bloque B se acuñaron 1000 tokens de la nada aire en la cuenta de Alice. El actor malintencionado produce entonces un bloque C válido (en un sentido de que las transacciones en C se aplican correctamente) encima de B, ofuscando el bloque B no válido e inicia una transacción entre fragmentos al fragmento #2 que transfiere esos 1000 tokens a la cuenta de Bob. A partir de este momento el mal Los token creados residen en un blockchain completamente válido en el fragmento #2. Algunos enfoques simples para abordar este problema son: 6Leer esto artículo para detalles en como adaptativo corrupción puede ser llevado fuera: https://medium.com/nearprotocol/d859adb464c8. Para más detalles en adaptativo corrupción, leer https://github.com/ethereum/wiki/wiki/Sharding-FAQ# ¿Cuáles-son-los-modelos-de-seguridad-bajo-los-que-estamos-operando?Figura 7: Una transacción entre fragmentos de una cadena que tiene un bloque no válido 1. Para validators del fragmento #2 para validar el bloque desde el cual se realizó la transacción se inicia. Esto no funcionará ni siquiera en el ejemplo anterior, ya que el bloque C parece ser completamente válido. 2. Para validators en el fragmento #2 para validar una gran cantidad de bloques que preceden al bloque desde el cual se inicia la transacción. Naturalmente, para cualquier número de bloques N validados por el fragmento receptor el malicioso validators pueden crear N+1 bloques válidos además del bloque no válido que producido. Una idea prometedora para resolver este problema sería organizar los fragmentos en un gráfico no dirigido en el que cada fragmento está conectado a varios otros fragmentos, y solo permitir transacciones entre fragmentos entre fragmentos vecinos (por ejemplo, así es como La fragmentación de Vlad Zamfir esencialmente funciona7, y una idea similar se utiliza en la de Kadena. Chainweb [1]). Si se necesita una transacción entre fragmentos entre fragmentos que están no vecinos, dicha transacción se enruta a través de múltiples fragmentos. en este diseño Se espera que un validator en cada fragmento valide todos los bloques en su fragmento así como todos los bloques en todos los fragmentos vecinos. Considere una figura a continuación con 10 fragmentos, cada uno con cuatro vecinos y no hay dos fragmentos que requieran más de dos saltos para una comunicación entre fragmentos como se muestra en la figura 8. El fragmento #2 no solo valida su propio blockchain, sino también los blockchains de todos los vecinos, incluido el fragmento n.° 1. Entonces, si un actor malicioso en el fragmento #1 está intentando crear un bloque B no válido, luego construye el bloque C encima de él e inicia una transacción entre fragmentos, dicha transacción entre fragmentos no se realizará desde el Fragmento #2 habrá validado toda la historia del Fragmento #1 que hará que identifique el bloque B no válido. 7Lea más sobre el diseño aquí: https://medium.com/nearprotocol/37e538177ed9

Figura 8: Una transacción entre fragmentos no válida en un sistema tipo cadena web que ser detectado Si bien corromper un único fragmento ya no es un ataque viable, corromper un pocos fragmentos siguen siendo un problema. En la figura 9, un adversario corrompiendo ambos Shard

1 y el fragmento #2 ejecutan con éxito una transacción entre fragmentos al fragmento #3

con fondos de un bloque B no válido: Figura 9: Una transacción entre fragmentos no válida en un sistema tipo cadena web que no ser detectado El fragmento n.º 3 valida todos los bloques del fragmento n.º 2, pero no del fragmento n.º 1, y no tiene forma de detectar el bloque malicioso. Hay dos direcciones principales para resolver adecuadamente la validez estatal: los pescadores

y pruebas criptográficas de cómputo. 2.3 pescador La idea detrás del primer enfoque es la siguiente: siempre que un encabezado de bloque se comunica entre cadenas para cualquier propósito (como el enlace cruzado con el cadena de baliza, o una transacción entre fragmentos), hay un período de tiempo durante cual cualquier validator honesto puede proporcionar una prueba de que el bloqueo no es válido. allí Hay varias construcciones que permiten pruebas muy sucintas de que los bloques son no válido, por lo que la sobrecarga de comunicación para los nodos receptores es mucho menor que el de recibir un bloqueo completo. Con este enfoque, siempre que haya al menos un validator honesto en el fragmento, el sistema es seguro. Figura 10: pescador Este es el enfoque dominante (además de fingir que el problema no existe) entre los protocolos propuestos hoy. Este enfoque, sin embargo, tiene dos principales desventajas: 1. El período de desafío debe ser lo suficientemente largo para el validator honesto. para reconocer que se produjo un bloque, descargarlo, verificarlo completamente y preparar el desafío si el bloque no es válido. La introducción de ese período ralentizar significativamente las transacciones entre fragmentos. 2. La existencia del protocolo de desafío crea un nuevo vector de ataques cuando los nodos maliciosos envían spam con desafíos no válidos. Una solución obvia a este problema es hacer que los retadores depositen una cierta cantidad de tokens que se devuelven si el desafío es válido. Esta es sólo una solución parcial, ya que Todavía podría ser benéfico para el adversario enviar spam al sistema (y quemar los depósitos) con impugnaciones no válidas, por ejemplo para impedir la validezdesafío de un honesto validator de pasar. Estos ataques son llamados ataques de duelo. Consulte la sección 3.7.2 para conocer una forma de evitar este último punto. 2.4 Argumentos de conocimiento sucintos y no interactivos La segunda solución a la corrupción de múltiples fragmentos es utilizar algún tipo de construcción criptográfica que permita demostrar que un determinado cálculo (como como calcular un bloque a partir de un conjunto de transacciones) se realizó correctamente. Este tipo de construcciones existen, p. zk-SNARK, zk-STARK y algunos otros, y algunos se utilizan activamente en los protocolos blockchain actuales para pagos privados, más notablemente ZCash. El principal problema con tales primitivos es que son notoriamente lentos de calcular. P.ej. Protocolo Coda, que utiliza zk-SNARK específicamente para demostrar que todos los bloques en el blockchain son válidos, dijo en un de las entrevistas que puede tomar 30 segundos por transacción para crear una prueba (Este número probablemente sea menor ahora). Curiosamente, no es necesario que una parte de confianza calcule una prueba, ya que la prueba no sólo da fe de la validez del cálculo para el que está construida, sino también de la la validez de la prueba misma. Por tanto, el cálculo de tales pruebas se puede dividir entre un conjunto de participantes con significativamente menos redundancia de lo que sería necesario realizar algún cálculo sin confianza. También permite a los participantes que calculan zk-SNARK para ejecutarse en hardware especial sin reducir el descentralización del sistema. Los desafíos de los zk-SNARK, además del rendimiento, son: 1. Dependencia de primitivas criptográficas menos investigadas y menos probadas; 2. "Residuos tóxicos": los zk-SNARK dependen de una configuración confiable en la que un grupo de personas realiza algún cálculo y luego descarta el intermedio valores de ese cálculo. Si todos los participantes del procedimiento se confabulan y se mantienen los valores intermedios, se pueden crear pruebas falsas; 3. Se introduce complejidad adicional en el diseño del sistema; 4. Los zk-SNARK solo funcionan para un subconjunto de cálculos posibles, por lo que un protocolo con un lenguaje Turing completo smart contract no podría usar SNARK para demostrar la validez de la cadena. 2.5 Disponibilidad de datos El segundo problema que abordaremos es la disponibilidad de datos. Generalmente nodos que operan un blockchain particular se separan en dos grupos: nodos completos, aquellos que descargan cada bloque completo y validan cada transacción, y Light Nodos, aquellos que solo descargan encabezados de bloques y usan pruebas de Merkle para las partes del estado y las transacciones que les interesan, como se muestra en la figura 11.

Figura 11: árbol de merkle Ahora bien, si la mayoría de los nodos completos se confabulan, pueden producir un bloque, válido o no es válido y envía su hash a los nodos de luz, pero nunca revela el contenido completo del bloque. Hay varias maneras en que pueden beneficiarse de ello. Por ejemplo, considere la figura 12: Figura 12: Problema de disponibilidad de datos Hay tres bloques: el anterior, A, está producido por validators honestos; el actual, B, tiene validators en connivencia; y el siguiente, C, también se producirá por validators honestos (el blockchain se muestra en la esquina inferior derecha). Eres un comerciante. Los validators del bloque actual (B) recibieron el bloque A de los validators anteriores, calculó un bloque en el que recibe dinero,y le envié un encabezado de ese bloque con una prueba Merkle del estado en el que tiene dinero (o una prueba Merkle de una transacción válida que envía el dinero a ti). Con la seguridad de que la transacción está finalizada, usted brinda el servicio. Sin embargo, los validators nunca distribuyen el contenido completo del bloque B a cualquiera. Como tal, los validator__s honestos del bloque C no pueden recuperar el bloque y se ven obligados a detener el sistema o a construir sobre A, privándolo a usted como comerciante de dinero. Cuando aplicamos el mismo escenario a la fragmentación, las definiciones de completo y El nodo ligero generalmente se aplica por fragmento: validators en cada fragmento descarga cada bloquear en ese fragmento y validar cada transacción en ese fragmento, pero otros nodos del sistema, incluidos aquellos que capturan el estado de las cadenas de fragmentos en el cadena de balizas, descargue solo los encabezados. Por lo tanto, los validators en el fragmento son efectivamente nodos completos para ese fragmento, mientras que otros participantes en el sistema, incluida la cadena de balizas, funcionan como nodos luminosos. Para que funcione el enfoque del pescador que analizamos anteriormente, los validators honestos Debe poder descargar bloques que estén vinculados cruzadamente a la cadena de baliza. Si validators maliciosos vinculaban un encabezado de un bloque no válido (o lo usaban para iniciar una transacción entre fragmentos), pero nunca distribuyó el bloque, el honesto Los validators no tienen forma de crear un desafío. Cubriremos tres enfoques para abordar este problema que complementan unos a otros. 2.5.1 Pruebas de custodia El problema más inmediato a resolver es si un bloque está disponible una vez esta publicado. Una idea propuesta es tener los llamados Notarios que rotan entre fragmentos con más frecuencia que validators cuyo único trabajo es descargar un bloquear y dar fe de que pudieron descargarlo. pueden ser rotan con más frecuencia porque no necesitan descargar el estado completo del fragmento, a diferencia de los validators que no se pueden rotar con frecuencia ya que debe descargar el estado del fragmento cada vez que gira, como se muestra en la figura 13. El problema con este enfoque ingenuo es que es imposible demostrar más tarde si el Notario pudo o no descargar el bloque, por lo que un Notario pueden optar por dar fe siempre de que pudieron descargar el bloque sin incluso intentar recuperarlo. Una solución a esto es que los notarios proporcionen alguna evidencia o apostar alguna cantidad de tokens que acrediten que el bloque fue descargado. Una de esas soluciones se analiza aquí: https://ethresear.ch/t/ Bonos de custodia de 1 bit amigables con la agregación/2236. 2.5.2 Códigos de borrado Cuando un nodo de luz en particular recibe un hash de un bloque, para aumentar el valor del nodo Si está seguro de que el bloque está disponible, puede intentar descargar algunos archivos aleatorios. pedazos del bloque. Esta no es una solución completa, ya que a menos que los nodos de luz descargar colectivamente el bloque completo que los productores de bloques maliciosos pueden elegir

Figura 13: Los validadores necesitan descargar el estado y, por lo tanto, no se pueden rotar. frecuentemente retener las partes del bloque que no fueron descargadas por ningún nodo ligero, por lo que el bloque aún no está disponible. Una solución es utilizar una construcción llamada Códigos de borrado para que sea posible para recuperar el bloque completo incluso si solo una parte del bloque está disponible, como se muestra en la figura 14. Figura 14: Merkle tree construido sobre datos codificados de borrado Tanto Polkadot como Ethereum Serenity tienen diseños en torno a esta idea que Proporcionar una manera para que los nodos ligeros estén razonablemente seguros de que los bloques están disponibles. El enfoque Ethereum Serenity tiene una descripción detallada en [2].2.5.3 El enfoque de Polkadot respecto de la disponibilidad de datos En Polkadot, como en la mayoría de las soluciones fragmentadas, cada fragmento (llamado parachain) envía instantáneas de sus bloques a la cadena de baliza (llamada cadena de retransmisión). Digamos que hay 2f + 1 validators en la cadena de relés. Los productores de bloques de los bloques parachain, llamados Alzadores, una vez que se produce el bloque parachain, calcule una versión codificada de borrado del bloque que consta de 2f +1 partes, de modo que cualquier f partes sea suficiente. para reconstruir el bloque. Luego distribuyen una parte a cada validator en el cadena de relevo. Una cadena de retransmisión particular validator solo firmaría en una cadena de retransmisión bloque si tienen su parte para cada bloque de parachain que se captura en dicho bloque de cadena de relés. Por lo tanto, si un bloque de cadena de retransmisión tiene firmas de 2f + 1 validators, y mientras no más de f de ellos violen el protocolo, cada El bloque parachain se puede reconstruir obteniendo las piezas de validators. que siguen el protocolo. Ver figura 15. Figura 15: Disponibilidad de datos de Polkadot 2.5.4 Disponibilidad de datos a largo plazo Tenga en cuenta que todos los enfoques discutidos anteriormente solo dan fe del hecho de que un bloque se publicó y ya está disponible. Los bloques pueden dejar de estar disponibles más adelante por una variedad de razones: nodos que se desconectan, nodos que borran intencionalmente datos históricos datos, y otros. Un documento técnico que vale la pena mencionar y que aborda este problema es Polyshard [3], que utiliza códigos de borrado para hacer que los bloques estén disponibles en todos los fragmentos, incluso si hay varios Los fragmentos pierden completamente sus datos. Desafortunadamente, su enfoque específico requiere todos los fragmentos para descargar bloques de todos los demás fragmentos, lo cual es prohibitivamente caro. La disponibilidad a largo plazo no es un problema tan urgente: dado que ningún participante Se espera que el sistema sea capaz de validar todas las cadenas en todos los

fragmentos, la seguridad del protocolo fragmentado debe diseñarse de tal manera manera que el sistema sea seguro incluso si algunos bloques antiguos en algunos fragmentos se vuelven completamente no disponible.

Nightshade

3.1 De cadenas de fragmentos a fragmentos de fragmentos El modelo de fragmentación con cadenas de fragmentos y una cadena de balizas es muy poderoso pero tiene ciertas complejidades. En particular, es necesario ejecutar la regla de elección de la bifurcación. en cada cadena por separado, la regla de elección de bifurcación en las cadenas de fragmentos y la baliza La cadena debe construirse de manera diferente y probarse por separado. En Nightshade modelamos el sistema como un único blockchain, en el que cada El bloque contiene lógicamente todas las transacciones para todos los fragmentos y cambia el Estado completo de todos los fragmentos. Físicamente, sin embargo, ningún participante descarga el estado completo o el bloque lógico completo. En cambio, cada participante de la red sólo mantiene el estado que corresponde a los fragmentos para los que validan las transacciones, y la lista de todas las transacciones en el bloque se divide en físicas trozos, un trozo por fragmento. En condiciones ideales, cada bloque contiene exactamente un fragmento por fragmento por bloque, que corresponde aproximadamente al modelo con cadenas de fragmentos en el que el Las cadenas de fragmentos producen bloques con la misma velocidad que la cadena de baliza. Sin embargo, Debido a retrasos en la red, es posible que falten algunos fragmentos, por lo que en la práctica cada bloque contiene uno o cero fragmentos por fragmento. Consulte la sección 3.3 para obtener detalles sobre cómo Se producen bloques. Figura 16: Un modelo con cadenas de fragmentos a la izquierda y con una cadena que tiene bloques divididos en trozos a la derecha

3.2 Consenso Los dos enfoques dominantes para el consenso en la década de blockchains hoy son el cadena más larga (o más pesada), en la que la cadena que tiene más trabajo o participación utilizado para construirlo se considera canónico, y BFT, en el que para cada bloque algunos un conjunto de validator alcanzan un consenso BFT. En los protocolos propuestos recientemente, este último es el enfoque más dominante, ya que proporciona una finalidad inmediata, mientras que en la cadena más larga se necesitan más bloques. que se construirá encima del bloque para asegurar la finalidad. A menudo para un significado seguridad: el tiempo que lleva construir un número suficiente de bloques supone el orden de horas. Usar el consenso BFT en cada bloque también tiene desventajas, tales como: 1. El consenso BFT implica una cantidad considerable de comunicación. mientras Los avances recientes permiten alcanzar el consenso en tiempo lineal en número. de los participantes (ver, por ejemplo, [4]), todavía se nota una sobrecarga por bloque; 2. Es inviable que todos los participantes de la red participen en el BFT consenso por bloque, por lo que normalmente sólo un subconjunto de participantes muestreados aleatoriamente alcanza el consenso. Un conjunto muestreado aleatoriamente puede ser, en principio, se corrompe adaptativamente y, en teoría, se puede crear una bifurcación. el sistema cualquiera de los dos necesita ser modelado para estar listo para tal evento y, por lo tanto, aún tener una regla de elección de bifurcación además del consenso BFT, o estar diseñado para cerrar abajo en tal evento. Cabe mencionar que algunos diseños, como Algorand [5], reducen significativamente la probabilidad de corrupción adaptativa. 3. Lo más importante es que el sistema se detiene si 1 3 o más de todos los participantes son fuera de línea. Por lo tanto, cualquier falla temporal de la red o una división de la red puede detener completamente el sistema. Idealmente, el sistema debe poder continuar operar mientras al menos la mitad de los participantes estén en línea (la mayoría Los protocolos basados en cadena continúan funcionando incluso si menos de la mitad de los participantes están en línea, pero la conveniencia de esta propiedad es más discutible. dentro de la comunidad). Un modelo híbrido en el que el consenso utilizado es el más pesado La cadena, pero algunos bloques se finalizan periódicamente utilizando un dispositivo de finalidad BFT mantienen las ventajas de ambos modelos. Estos dispositivos de finalidad BFT son Casper FFG [6] usado en Ethereum 2.0 8, Casper CBC (ver https://vitalik. ca/general/2018/12/05/cbc_casper.html) y ABUELO (ver https:// medium.com/polkadot-network/d08a24a021b5) utilizado en Polkadot. Nightshade utiliza el consenso de cadena más pesado. Específicamente cuando un bloque productor produce un bloque (ver sección 3.3), puede recolectar firmas de otros productores de bloques y validators que acrediten el bloque anterior. Ver sección 3.8 para obtener detalles sobre cómo se agrega una cantidad tan grande de firmas. el peso 8Vea también la sesión de pizarra con Justin Drake para obtener una descripción detallada de Casper. FFG y cómo se integra con el consenso de la cadena más pesada de GHOST aquí: https://www. youtube.com/watch?v=S262StTwkmode un bloque es entonces la participación acumulada de todos los firmantes cuyas firmas son incluido en el bloque. El peso de una cadena es la suma de los pesos de los bloques. Además del consenso de cadena más pesado, utilizamos un dispositivo de finalidad que utiliza las certificaciones para finalizar los bloques. Para reducir la complejidad del sistema, utilizamos un dispositivo de finalidad que no influye de ninguna manera en la regla de elección de la bifurcación, y en su lugar sólo introduce condiciones de corte adicionales, de modo que una vez que un bloque es finalizado por el dispositivo de finalidad, una bifurcación es imposible a menos que un porcentaje muy grande del total de la apuesta se reduce drásticamente. Casper CBC es un dispositivo de finalidad, y Actualmente modela con Casper CBC en mente. También trabajamos en un protocolo BFT separado llamado TxFlow. En el momento de Al escribir este documento no está claro si se utilizará TxFlow en lugar de Casper. CBC. Sin embargo, observamos que la elección del dispositivo final es en gran medida ortogonal al resto del diseño. 3.3 producción de bloques En Nightshade hay dos roles: productores de bloques y validators. en cualquier punto el sistema contiene w productores de bloques, w = 100 en nuestros modelos, y wv validators, en nuestro modelo v = 100, wv = 10, 000. El sistema es Prueba de participación, lo que significa que tanto los productores de bloques como los validators tienen algún número de moneda (denominada "tokens") bloqueada por un período de tiempo que excede con creces el tiempo que dedican a realizar sus tareas de construcción y validación de la cadena. Como ocurre con todos los sistemas de Prueba de participación, no todos los productores de bloques w y no todos los wv validators son entidades diferentes, ya que eso no se puede hacer cumplir. cada uno de los productores de bloques w y los wv validators, sin embargo, tienen una estaca. El sistema contiene n fragmentos, n = 1000 en nuestro modelo. Como se menciona en sección 3.1, en Nightshade no hay cadenas de fragmentos; en cambio, todos los productores de bloques y validator están construyendo un único blockchain, al que nos referimos como cadena principal. El estado de la cadena principal se divide en n fragmentos y cada bloque productor y validator en cualquier momento solo han descargado localmente un subconjunto de el estado que corresponde a algún subconjunto de los fragmentos, y solo el proceso y validar transacciones que afecten a esas partes del estado. Para convertirse en productor de bloques, un participante de la red bloquea algunos grandes cantidad de tokens (una participación). El mantenimiento de la red se realiza en épocas, donde una época es un período de tiempo del orden de días. Los participantes con lo que está en juego más al comienzo de una época particular es el bloque productores de esa época. Cada productor de bloques se asigna a fragmentos sw (digamos sw = 40, lo que haría sww/n = 4 productores de bloques por fragmento). el bloque El productor descarga el estado del fragmento al que están asignados antes de la época. comienza, y a lo largo de la época recopila transacciones que afectan ese fragmento, y los aplica al Estado. Para cada bloque b en la cadena principal, y para cada fragmento s, hay uno de los productores de bloques asignados a s, quien es responsable de producir la parte de b relacionada al fragmento. La parte de b relacionada con el fragmento s se llama fragmento y contiene el lista de las transacciones para que el fragmento se incluya en b, así como el merkleraíz del estado resultante. b en última instancia sólo contendrá un encabezado muy pequeño de el fragmento, es decir, la raíz merkle de todas las transacciones aplicadas (consulte la sección 3.7.1 para detalles exactos), y la raíz merkle del estado final. A lo largo del resto del documento, a menudo nos referimos al productor de bloques. que es responsable de producir un fragmento en un momento particular para un fragmento en particular como productor de trozos. El productor de fragmentos es siempre uno de los productores de bloques. Los productores de bloques y los productores de trozos rotan cada bloque según a un horario fijo. Los productores de bloques tienen un pedido y producen repetidamente. bloques en ese orden. P.ej. Si hay 100 productores de bloques, el primer bloque Los productores son responsables de producir los bloques 1, 101, 201, etc., el segundo es responsable de producir 2, 102, 202, etc.). Dado que la producción de trozos, a diferencia de la producción de bloques, requiere mantener el estado, y para cada fragmento solo los productores de bloques sww/n mantienen el estado por fragmento, en consecuencia, solo los productores de bloques sww/n rotan para crear trozos. P.ej. con las constantes anteriores con cuatro productores de bloques asignados a En cada fragmento, cada productor de bloques creará fragmentos una vez cada cuatro bloques. 3.4 Garantizar la disponibilidad de datos Para garantizar la disponibilidad de datos utilizamos un enfoque similar al de Polkadot descrito en la sección 2.5.3. Una vez que un productor de bloques produce un fragmento, crea una versión codificada de borrado con un código de bloque óptimo (w, ⌊w/6 + 1⌋) del trozo. Luego envían una parte del fragmento codificado de borrado (a esas partes las llamamos partes de fragmentos, o solo partes) a cada productor de bloques. Calculamos un árbol merkle que contiene todas las partes como las hojas, y el El encabezado de cada fragmento contiene la raíz merkle de dicho árbol. Las piezas se envían a los validators mediante mensajes onepart. Cada uno de esos mensajes contiene el encabezado del fragmento, el ordinal de la parte y el contenido de la parte. el El mensaje también contiene la firma del productor del bloque que produjo el chunk y la ruta merkle para demostrar que la parte corresponde al encabezado y es producido por el productor de bloques adecuado. Una vez que un productor de bloques recibe un bloque de la cadena principal, primero verifica si tenga mensajes de una parte para cada fragmento incluido en el bloque. Si no, el bloque no se procesa hasta que se recuperan los mensajes de una parte que faltan. Una vez que se reciben todos los mensajes de una parte, el productor del bloque recupera el partes restantes de los pares y reconstruye los fragmentos que mantienen el estado. El productor de bloques no procesa un bloque de la cadena principal si es por al menos un fragmento incluido en el bloque no tienen el mensaje de una parte correspondiente, o si al menos para un fragmento para el cual mantienen el estado no pueden reconstruir todo el trozo. Para que un fragmento en particular esté disponible es suficiente que ⌊w/6⌋+1 del bloque los productores tienen sus partes y les sirven. Así, mientras el número de Los actores maliciosos no superan ⌊w/3⌋ninguna cadena que tenga más de medio bloque. los productores que lo construyen pueden tener fragmentos no disponibles.Figura 17: Cada bloque contiene uno o cero fragmentos por fragmento, y cada fragmento tiene un código de borrado. Cada parte del fragmento codificado de borrado se envía a un lugar designado productor de bloques a través de un mensaje especial de una parte 3.4.1 Tratar con productores de bloques perezosos Si un productor de bloques tiene un bloque al que le falta un mensaje de una parte, podría optar por firmar aún así, porque si el bloque termina en la cadena, maximizará la recompensa para el productor del bloque. No hay riesgo para el bloque. productor ya que es imposible probar posteriormente que el productor del bloque no tenía el mensaje de una parte. Para solucionarlo, hacemos que cada fragmento sea productor al crear el fragmento para elija un color (rojo o azul) para cada parte del futuro fragmento codificado y guárdelo la máscara de bits del color asignado en el fragmento antes de codificarlo. cada una de las partes El mensaje contiene el color asignado a la pieza y el color se utiliza cuando calcular la raíz merkle de las partes codificadas. Si el productor del trozo se desvía del protocolo, se puede probar fácilmente, ya que la raíz de merkle no corresponden a mensajes de una parte, o los colores en los mensajes de una parte que corresponden a la raíz de merkle no coincidirán con la máscara en el fragmento. Cuando un productor de bloques firma en un bloque, incluye una máscara de bits de todos los piezas rojas que recibieron por los trozos incluidos en el bloque. Publicar un la máscara de bits incorrecta es un comportamiento que se puede recortar. Si un productor de bloques no ha recibido un mensaje de una parte, no tienen forma de saber el color del mensaje, y Por lo tanto, tienen un 50% de posibilidades de ser eliminados si intentan firmar a ciegas el bloque. 3.5 Solicitud de transición de estado Los productores de fragmentos sólo eligen qué transacciones incluir en el fragmento, pero no aplique la transición de estado cuando produzcan un fragmento. En consecuencia,

el encabezado del fragmento contiene la raíz merkle del estado merkelizado como antes se aplican las transacciones en el fragmento. Las transacciones solo se aplican cuando un bloque completo que incluye el fragmento se procesa. Un participante solo procesa un bloque si 1. El bloque anterior fue recibido y procesado; 2. Para cada fragmento, el participante no mantiene el estado que tiene. visto el mensaje de una parte; 3. Para cada fragmento, el participante mantiene el estado porque tiene el trozo completo. Una vez que se procesa el bloque, para cada fragmento para el cual el participante mantiene el estado, aplican las transacciones y calculan el nuevo estado a partir de que se aplican las transacciones, después de lo cual están listas para producir los fragmentos para el siguiente bloque, si están asignados a algún fragmento, ya que tienen la raíz merkle del nuevo estado merkelizado. 3.6 Transacciones y recibos entre fragmentos Si una transacción necesita afectar a más de un fragmento, debe realizarse consecutivamente. ejecutado en cada fragmento por separado. La transacción completa se envía al primer fragmento. afectado, y una vez que la transacción se incluye en el fragmento de dicho fragmento, y se aplica después de que el fragmento se incluye en un bloque, genera el llamado recibo transacción, que se enruta al siguiente fragmento en el que la transacción debe ser ejecutado. Si se requieren más pasos, la ejecución de la transacción de recibo genera una nueva transacción de recibo y así sucesivamente. 3.6.1 Duración de la transacción del recibo Es deseable que la transacción de recibo se aplique en el bloque que sigue inmediatamente al bloque en el que se generó. La transacción del recibo es sólo generado después de que el bloque anterior fue recibido y aplicado por los productores de bloques que mantienen el fragmento de origen, y debe ser conocido en el momento en que El fragmento para el siguiente bloque es producido por los productores de bloques del destino. fragmento. Por lo tanto, el recibo debe comunicarse desde el fragmento de origen al fragmento de destino en el corto período de tiempo entre esos dos eventos. Sea A el último bloque producido que contiene una transacción t que genera un recibo r. Sea B el siguiente bloque producido (es decir, un bloque que tiene A como su bloque anterior) que queremos contener r. Sea t estar en el fragmento a y r en el fragmento b. La vida útil del recibo, también representada en la figura 18, es la siguiente: Elaborar y almacenar los recibos. El cpa del productor de fragmentos para fragmentos a recibe el bloque A, aplica la transacción t y genera el recibo r. cpa luego almacena todos los recibos producidos en su almacenamiento interno persistente indexado por la identificación del fragmento de origen.Distribuyendo los recibos. Una vez que cpa esté listo para producir el fragmento para fragmento a para el bloque B, obtienen todos los recibos generados al aplicar las transacciones del bloque A para el fragmento a y los incluyen en el fragmento para shrad a en el bloque B. Una vez que se genera dicho fragmento, cpa produce su borrado codificado versión y todos los mensajes onepart correspondientes. cpa sabe qué productores de bloques mantienen el estado completo para qué fragmentos. Para un productor de bloques en particular pb cpa incluye los ingresos que resultaron de aplicar las transacciones del bloque A para el fragmento a que tiene como destino cualquiera de los fragmentos que le interesan a bp en el mensaje de una parte cuando distribuyeron el fragmento para el fragmento a en el bloque B (consulte la figura 17, que muestra los recibos incluidos en el mensaje de una parte). Recibir los recibos. Recuerde que los participantes (tanto productores de bloques como validators) no procesan bloques hasta que tengan mensajes de una parte. para cada fragmento incluido en el bloque. Por lo tanto, cuando un participante en particular aplica el bloque B, tiene todos los mensajes de una parte que corresponden a fragmentos en B, y por lo tanto tienen todos los recibos entrantes que tienen los fragmentos el participante mantiene el estado como destino. Al aplicar el transición de estado para un fragmento en particular, el participante aplica ambos recibos que han recopilado para el fragmento en los mensajes de una parte, así como todos las transacciones incluidas en el propio fragmento. Figura 18: La vida útil de una transacción de recibo 3.6.2 Manejar demasiados recibos Es posible que el número de recibos dirigidos a un fragmento concreto en un bloque en particular es demasiado grande para ser procesado. Por ejemplo, considere la figura 19, en en el que cada transacción en cada fragmento genera un recibo dirigido al fragmento 1. En el siguiente bloque, la cantidad de recibos que el fragmento 1 debe procesar es comparable a la carga que todos los fragmentos combinados procesaron mientras se manipulaban el bloque anterior.

Figura 19: Si todos los recibos apuntan al mismo fragmento, es posible que el fragmento no tenga la capacidad de procesarlos Para solucionarlo utilizamos una técnica similar a la utilizada en QuarkChain 9. Específicamente, para cada fragmento, el último bloque B y el último fragmento dentro de ese Se registra el bloque desde el cual se aplicaron los recibos. Cuando el nuevo fragmento esté creado, los recibos se aplican en orden primero a partir de los fragmentos restantes en B, y luego en bloques que siguen a B, hasta que el nuevo fragmento esté lleno. En condiciones normales circunstancias con una carga equilibrada, generalmente resultará en todos los recibos que se está aplicando (y por lo tanto, el último fragmento del último bloque se registrará para cada trozo), pero durante los momentos en que la carga no está equilibrada, y un particular Shard recibe una cantidad desproporcionada de recibos, esta técnica les permite procesarse respetando los límites en el número de transacciones incluidas. Tenga en cuenta que si dicha carga desequilibrada permanece durante mucho tiempo, el retraso desde la creación del recibo hasta que la aplicación pueda seguir creciendo indefinidamente. uno forma de abordarlo es descartar cualquier transacción que genere un recibo dirigido a un fragmento que tiene un retraso de procesamiento que excede alguna constante (por ejemplo, una época). Considere la figura 20. En el bloque B, el fragmento 4 no puede procesar todos los recibos, por lo que solo procesa el origen de los recibos desde hasta el fragmento 3 en el bloque A, y lo registra. En el bloque C se incluyen los recibos hasta el fragmento 5 del bloque B, y luego, en el bloque D, el fragmento se pone al día y procesa todos los recibos restantes en bloque B y todos los recibos del bloque C. 3.7 Validación de fragmentos Un fragmento producido para un fragmento en particular (o un bloque de fragmentos producido para una cadena de fragmentos particular en el modelo con cadenas de fragmentos) solo puede ser validado por el 9Vea el episodio de la pizarra con QuarkChain aquí: https://www.youtube.com/watch? v=opEtG6NM4x4, en el que se analiza el enfoque de las transacciones entre fragmentos, entre otros cosasFigura 20: Procesamiento de recibos retrasados participantes que mantienen el estado. Pueden ser productores de bloques, validators, o simplemente testigos externos que descargaron el estado y validaron el fragmento en donde almacenan activos. En este documento asumimos que la mayoría de los participantes no pueden almacenar al Estado una gran parte de los fragmentos. Vale la pena mencionar, sin embargo, que hay blockchains fragmentados que están diseñados con la suposición de que la mayoría de los participantes tienen capacidad para almacenar el estado y validar la mayoría de los fragmentos, como QuarkChain. Dado que solo una fracción de los participantes tiene el estado para validar el fragmento fragmentos, es posible corromper adaptativamente solo a los participantes que tienen la estado y aplicar una transición de estado no válida. Se propusieron múltiples diseños de fragmentación que muestrean validators cada pocos días, y dentro de un día cualquier bloque en la cadena de fragmentos que tenga más de 2/3 de firmas de los validator asignados a dicho fragmento se considera inmediatamente final. Con tal enfoque un adversario adaptativo sólo necesita corromper 2n/3+1 de los validators en una cadena de fragmentos para aplicar una transición de estado no válida, que, Aunque probablemente sea difícil de lograr, no es un nivel de seguridad suficiente para un público. blockchain. Como se analizó en la sección 2.3, el enfoque común es permitir una cierta ventana de tiempo después de que se crea un bloque para cualquier participante que tenga estado (ya sea es un productor de bloques, un validator o un observador externo) para cuestionar su validez. Estos participantes se llaman pescadores. Para que un pescador pueda impugnar un bloque no válido, se debe garantizar que dicho bloque esté disponible para ellos. La disponibilidad de datos en Nightshade se analiza en la sección 3.4. En Nightshade, una vez que se produce un bloque, los fragmentos no fueron validados por cualquiera excepto el productor de fragmentos real. En particular, el productor de bloques que sugirió que el bloque naturalmente no tenía el estado para la mayoría de los fragmentos, yno pudo validar los fragmentos. Cuando se produce el siguiente bloque, contiene certificaciones (consulte la sección 3.2) de múltiples productores de bloques y validators, pero dado que la mayoría de los productores de bloques y validators no mantienen el estado Además, para la mayoría de los fragmentos, un bloque con solo un fragmento no válido recopilará significativamente más de la mitad de las certificaciones y seguirá estando en la lista más pesada. cadena. Para abordar este problema, permitimos que cualquier participante que mantenga el estado de un fragmento para presentar un desafío en la cadena por cualquier fragmento no válido producido en ese fragmento. 3.7.1 Desafío de validez estatal Una vez que un participante detecta que un fragmento en particular no es válido, debe proporcionar una prueba de que el fragmento no es válido. Dado que la mayoría de los participantes de la red no mantienen el estado del fragmento en el que se encuentra el fragmento no válido producida, la prueba debe tener suficiente información para confirmar que el bloque es inválido sin tener el estado. Establecemos un límite Ls de la cantidad de estado (en bytes) que una sola transacción Puede leer o escribir de forma acumulativa. Cualquier transacción que toque más de Ls. El estado se considera inválido. Recuerde de la sección 3.5 que el trozo en un bloque particular B sólo contiene las transacciones a aplicar, pero no la nueva raíz estatal. La raíz del estado incluida en el fragmento del bloque B es el estado root antes de aplicar dichas transacciones, pero después de aplicar las transacciones de el último fragmento en el mismo fragmento antes del bloque B. Un actor malicioso que desea aplicar una transición de estado no válida incluiría una raíz de estado incorrecta en el bloque B que no corresponde al estado raíz que resulta de aplicar las transacciones en el fragmento anterior. Ampliamos la información que un productor de fragmentos incluye en el fragmento. En lugar de simplemente incluir el estado después de aplicar todas las transacciones, en su lugar incluye una raíz de estado después de aplicar cada conjunto contiguo de transacciones que leer y escribir colectivamente Ls bytes de estado. Con esta información para el pescador para crear un desafío que una transición de estado se aplica incorrectamente es suficiente encontrar la primera raíz de estado no válida e incluir solo Ls bytes de estado que se ven afectados por las transacciones entre la última raíz del estado (que fue válido) y la raíz del estado actual con las pruebas de merkle. Entonces cualquier participante puede validar las transacciones en el segmento y confirmar que el fragmento es inválido. De manera similar, si el productor del fragmento intentara incluir transacciones que leyeran y escribir más de Ls bytes de estado, para el desafío basta con incluir los primeros Ls bytes que toca con las pruebas merkle, que serán suficientes para aplicar las transacciones y confirmar que hay un momento en el que se intenta Se realiza lectura o escritura de contenido más allá de Ls bytes.

3.7.2 Pescadores y transacciones rápidas entre fragmentos. Como se analizó en la sección 2.3, una vez que asumimos que los fragmentos (o fragmentos) bloques en el modelo con cadenas de fragmentos) pueden no ser válidos e introducir un desafío período, afecta negativamente la finalidad y, por lo tanto, la comunicación entre fragmentos. en En particular, el fragmento de destino de cualquier transacción entre fragmentos no puede estar seguro el fragmento o bloque de origen es definitivo hasta que finaliza el período de desafío (ver figura 21). Figura 21: Esperar el período de impugnación antes de aplicar un recibo La forma de abordarlo de manera que se realicen transacciones entre fragmentos. instantáneo es que el fragmento de destino no espere el período de desafío después de que se publique la transacción del fragmento de origen y aplique la transacción del recibo inmediatamente, pero luego revertir el fragmento de destino junto con el origen fragmento si más tarde se descubre que el fragmento o bloque original no es válido (consulte la figura 22). Esto se aplica de forma muy natural al diseño Nightshade en el que el fragmento Las cadenas no son independientes, sino que todos los fragmentos se publican. juntos en el mismo bloque de cadena principal. Si se determina que algún fragmento no es válido, el todo el bloque con ese fragmento se considera inválido y todos los bloques construidos en él encima. Ver figura 23. Ambos enfoques anteriores proporcionan atomicidad suponiendo que el desafío el período es lo suficientemente largo. Usamos el último enfoque, ya que proporcionar transacciones rápidas entre fragmentos en circunstancias normales supera los inconvenientes de el fragmento de destino retrocede debido a una transición de estado no válida en uno de los fragmentos de origen, lo cual es un evento extremadamente raro. 3.7.3 Ocultar validators La existencia de los desafíos ya reduce significativamente la probabilidad de corrupción adaptativa, ya que para finalizar una parte con un estado de transición inválidoFigura 22: Aplicar recibos inmediatamente y revertir el destino cadena si la cadena fuente tenía un bloque no válido Figura 23: Desafío del pescador en Nightshade El período de desafío el adversario adaptativo necesita corromper a todos los participantes. que mantienen el estado del fragmento, incluidos todos los validator. Estimar la probabilidad de que ocurra tal evento es extremadamente complejo, ya que no sharded blockchain ha estado activo el tiempo suficiente para intentar cualquier ataque de este tipo. Sostenemos que la probabilidad, aunque extremadamente baja, sigue siendo suficientemente grande para un sistema que se espera que ejecute transacciones multimillonarias y ejecutar operaciones financieras a nivel mundial. Hay dos razones principales para esta creencia: 1. La mayoría de los validators de las cadenas de Prueba de Participación y mineros del

Las cadenas de prueba de trabajo están incentivadas principalmente por las ventajas financieras. si un adversario adaptativo les ofrece más dinero que el retorno esperado de operar honestamente, es razonable esperar que muchos validators aceptará la oferta. 2. Muchas entidades validan las cadenas de prueba de participación de manera profesional, y Se espera que un gran porcentaje de la participación en cualquier cadena sea de dichas entidades. El número de tales entidades es lo suficientemente pequeño para una adversario adaptativo para conocer a la mayoría de ellos personalmente y tener una buena comprensión de su inclinación a corromperse. Damos un paso más para reducir la probabilidad de corrupción adaptativa al ocultar qué validator están asignados a cada fragmento. La idea es remotamente similar a la forma en que Algorand [5] oculta validators. Es fundamental tener en cuenta que incluso si los validator están ocultos, como en Algorand o como se describe a continuación, la corrupción adaptativa todavía es posible en teoría. mientras El adversario adaptativo no conoce a los participantes que crearán o validarán. un bloque o un trozo, los propios participantes saben que realizarán tal tarea y tener una prueba criptográfica de ello. Así, el adversario puede difundir su intención de corromper y pagar a cualquier participante que proporcione tal prueba criptográfica. Sin embargo, observamos que dado que el adversario no conocen los validator que están asignados al fragmento que quieren corromper, no tienen otra opción que transmitir su intención de corromper un fragmento en particular a toda la comunidad. En ese punto es económicamente benéfico para cualquier persona honesta. participante para activar un nodo completo que valide ese fragmento, ya que hay un alto posibilidad de que aparezca un bloque no válido en ese fragmento, lo cual es una oportunidad para crea un desafío y recolecta la recompensa asociada. Para no revelar los validators que están asignados a un fragmento en particular, hacemos lo siguiente (ver figura 24): Usando VRF para obtener la tarea. Al comienzo de cada época cada validator usa un VRF para obtener una máscara de bits de los fragmentos a los que está asignado validator. La máscara de bits de cada validator tendrá bits Sw (consulte la sección 3.3 para conocer la definición de SW). Luego, el validator recupera el estado de los fragmentos correspondientes y durante la época para cada bloque recibido valida los fragmentos que corresponden a los fragmentos a los que está asignado el validator. Regístrate en bloques en lugar de trozos. Dado que la asignación de fragmentos está oculta, validator no puede firmar fragmentos. En cambio, siempre firma en todo el bloque, por lo que no revela qué fragmentos valida. Específicamente, cuando validator recibe un bloque y valida todos los fragmentos, crea un mensaje que atestigua que todos los fragmentos en todos los fragmentos a los que está asignado el validator son válido (sin indicar de ninguna manera cuáles son esos fragmentos), o un mensaje que contiene una prueba de una transición de estado no válida si algún fragmento no es válido. Ver el sección 3.8 para obtener detalles sobre cómo se agregan dichos mensajes, sección 3.7.4 para los detalles sobre cómo evitar que validators se aprovechen de los mensajes de otros validators, y la sección 3.7.5 para obtener detalles sobre cómo recompensar y castigar validators en caso de que realmente se produzca una impugnación exitosa de una transición de estado no válida.Figura 24: Ocultando los validators en Nightshade 3.7.4 Comprometerse-Revelar Uno de los problemas comunes con validators es que un validator puede omitir la descarga del estado y validar los fragmentos y bloques, y en su lugar observar la red, ver lo que envían los otros validators y repetir sus mensajes. Un validator que sigue dicha estrategia no proporciona ningún beneficio adicional. seguridad para la red, pero recoge recompensas. Una solución común para este problema es que cada validator proporcione una prueba que realmente validaron el bloque, por ejemplo proporcionando un seguimiento único de aplicar la transición estatal, pero tales pruebas aumentan significativamente el costo de validación. Figura 25: comprometerse-revelar

En su lugar, hacemos que los validators se comprometan por primera vez con el resultado de la validación (ya sea el mensaje que da fe de la validez de los fragmentos, o la prueba de una invalidez transición de estado), espere un cierto período y solo entonces revele el resultado de validación real, como se muestra en la figura 25. El período de confirmación no se cruza con el período de revelación y, por lo tanto, un validator perezoso no puede imitar a los validators honestos. Además, si un validator deshonesto se comprometió con un mensaje que da fe de la validez de los fragmentos asignados, y al menos un fragmento no era válido, una vez que se demostrado que el fragmento no es válido, validator no puede evitar la reducción, ya que, Como mostramos en la sección 3.7.5, la única manera de no ser cortado en tal situación es presentar un mensaje que contiene una prueba de la transición de estado no válida que coincide con el compromiso. 3.7.5 Manejando desafíos Como se analizó anteriormente, una vez que un validator recibe un bloque con un fragmento no válido, Primero preparan una prueba de la transición de estado no válida (ver sección 3.7.1), luego comprometerse con dicha prueba (ver 3.7.4) y después de un período revelar el desafío. Una vez incluido el desafío revelado en un bloque, sucede lo siguiente: 1. Todas las transiciones de estado que ocurrieron desde el bloque que contiene el fragmento no válido hasta que se obtenga el bloque en el que se incluye el desafío revelado. anulado. El estado ante el bloque que incluye el desafío revelado se considera el mismo que el estado anterior al bloque que contenía el trozo inválido. 2. Dentro de un cierto período de tiempo cada validator debe revelar su máscara de bits de los fragmentos que validan. Dado que la máscara de bits se crea a través de un VRF, si fueron asignados al fragmento que tenía la transición de estado no válida, No puedo evitar revelarlo. Cualquier validator que no revele la máscara de bits se supone que está asignado al fragmento. 3. Cada validator que después de dicho período se encuentre asignado al fragmento, que se comprometió con algún resultado de validación para el bloque que contiene el fragmento inválido y que no reveló la prueba de transición de estado inválido que corresponde a su compromiso se reduce. 4. Cada validator recibe una nueva asignación de fragmentos y se programa una nueva época. para comenzar después de un tiempo suficiente para que todos los validators descarguen el estado, como se muestra en la figura 26. Tenga en cuenta que desde el momento en que los validator revelan los fragmentos que se les asignan hasta que comienza la nueva época, la seguridad del sistema se reduce desde el Se revela la asignación de fragmentos. Los participantes de la red deben mantenerlo. en mente al utilizar la red durante dicho período. 3.8 Agregación de firmas Para que un sistema con cientos de fragmentos funcione de forma segura, queremos tener en el orden de 10, 000 o más validators. Como se discutió en la sección 3.7, queremos que cadaFigura 26: Manejando el desafío validator para publicar un compromiso con un determinado mensaje y una firma en promedio una vez por bloque. Incluso si los mensajes de confirmación fueran los mismos, agregar tal La firma BLS y su validación habrían sido prohibitivamente costosas. pero naturalmente, los mensajes de confirmación y revelación no son los mismos en validators, y por lo tanto necesitamos alguna forma de agregar dichos mensajes y las firmas en un forma que permita una validación rápida posterior. El enfoque específico que utilizamos es el siguiente: Validadores que se unen a productores de bloques. Los productores de bloques son conocidos. algún tiempo antes de que comience la época, ya que necesitan algo de tiempo para descargar el estado antes de que comience la época y, a diferencia de los validators, los productores de bloques son no oculto. Cada productor de bloques tiene v validator ranuras. Los validadores envían propuestas fuera de la cadena a los productores de bloques para ser incluidos como uno de sus v validators. Si un productor de bloques desea incluir un validator, envía un transacción que contiene la solicitud inicial fuera de la cadena del validator, y el firma del productor del bloque que hace que validator se una al productor del bloque. Tenga en cuenta que los validators asignados a los productores de bloques no necesariamente valide los mismos fragmentos para los que el productor de bloques produce fragmentos. si un validator se aplicó para unir múltiples productores de bloques, solo la transacción de el primer productor de bloques tendrá éxito. Los productores de bloques recopilan compromisos. El productor de bloques recopila constantemente los mensajes de confirmación y revelación de los validator. Una vez que se acumula una cierta cantidad de dichos mensajes, el productor del bloque calcula un merkle árbol de estos mensajes, y envía a cada validator la raíz de merkle y el camino merkle a su mensaje. El validator valida el camino y se registra la raíz de merkle. Luego, el productor del bloque acumula una firma BLS en el raíz de merkle de validators, y publica solo la raíz de merkle y el firma acumulada. El productor del bloque también firma sobre la validez del firma múltiple utilizando una firma ECDSA barata. Si la firma múltiple no coincide con la raíz de merkle enviada o la máscara de bits de los validators participantes, es un comportamiento que se puede recortar. Al sincronizar la cadena, un participante puede optar por validar todas las firmas BLS de validators (lo cual es extremadamente costoso ya que implica agregar las claves públicas de validators), o sololas firmas ECDMA de los productores de bloques y se basan en el hecho de que el El productor de bloques no fue cuestionado ni recortado. Uso de transacciones en cadena y pruebas merkle para desafíos. eso Se puede observar que no tiene ningún valor revelar mensajes de validators si no Se detectó una transición de estado no válida. Sólo los mensajes que contienen la información real Es necesario revelar pruebas de una transición de estado inválida, y sólo para tales mensajes. es necesario demostrar que coinciden con el compromiso anterior. El mensaje necesita ser revelado con dos propósitos: 1. Para iniciar realmente la reversión de la cadena al momento anterior al transición de estado no válida (ver sección 3.7.5). 2. Para demostrar que el validator no intentó dar fe de la validez del trozo no válido. En cualquier caso debemos abordar dos cuestiones: 1. El compromiso real no se incluyó en la cadena, solo la raíz merkle del confirmar agregado con otros mensajes. El validator necesita utilizar el ruta merkle proporcionada por el productor del bloque y su compromiso original con demostrar que se comprometieron con el desafío. 2. Es posible que todos los validator asignados al fragmento con el valor no válido La transición de estado se asigna a productores de bloques corruptos que los están censurando. Para evitarlo, les permitimos enviar sus revelaciones. como una transacción regular en cadena y evitar la agregación. Esto último sólo se permite para las pruebas de transición de estado inválida, que son extremadamente raro y, por lo tanto, no debería generar spam en los bloques. La última cuestión que debe abordarse es que los productores de bloques pueden optar por no participar en la agregación de mensajes o censurar intencionalmente validators concretos. Lo hacemos económicamente desventajoso al hacer que el bloque Recompensa al productor proporcional al número de validators que se les asignen. nosotros También tenga en cuenta que dado que los productores de bloques entre épocas se cruzan en gran medida (ya que siempre son los primeros w participantes con la apuesta más alta), los validators pueden atenerse en gran medida a trabajar con los mismos productores de bloques, y así reducir el riesgo de ser asignados a un productor de bloques que los censuró en el pasado. 3.9 Cadena de instantáneas Dado que los bloques de la cadena principal se producen con mucha frecuencia, descargar el historial completo podría resultar caro muy rápidamente. Es más, dado que cada El bloque contiene una firma BLS de una gran cantidad de participantes, solo la agregación de las claves públicas para verificar la firma podría resultar prohibitiva. caro también. Finalmente, dado que en un futuro previsible Ethereum 1.0 probablemente seguirá siendo uno de los blockchains más utilizados, que tiene una forma significativa de transferir activos desde

Cerca de Ethereum es un requisito y hoy se verifican las firmas BLS para garantizar La validez de bloques cercanos en el lado de Ethereum no es posible. Cada bloque de la cadena principal de Nightshade puede contener opcionalmente un Schnorr firma múltiple en el encabezado del último bloque que incluía dicho Schnorr multifirma. A estos bloques los llamamos bloques instantáneos. El primer bloque de cada época debe ser un bloque de instantáneas. Mientras trabajaba en una firma múltiple de este tipo, los productores de bloques también deben acumular las firmas BLS de los validators en el último bloque de instantáneas y agréguelas de la misma manera que se describe en sección 3.8. Dado que el conjunto de productores de bloques es constante a lo largo de la época, validar sólo los primeros bloques de instantáneas en cada época son suficientes suponiendo que en ningún momento punto, un gran porcentaje de productores de bloques y validators se confabularon y crearon un tenedor. El primer bloque de la época debe contener información suficiente para calcular los productores de bloques y validators para la época. Llamamos a la subcadena de la cadena principal que solo contiene la instantánea. bloquea una cadena de instantáneas. Crear una firma múltiple de Schnorr es un proceso interactivo, pero como Sólo es necesario realizarlo con poca frecuencia, cualquier proceso, por ineficiente que sea, será suficiente. Las firmas múltiples de Schnorr se pueden validar fácilmente en Ethereum, proporcionando así primitivas cruciales para una forma segura de realizar cross-blockchain comunicación. Para sincronizar con la cadena Near solo es necesario descargar toda la instantánea. bloquea y confirma que las firmas Schnorr son correctas (opcionalmente, también verifica las firmas BLS individuales de los validators), y luego solo sincroniza bloques de la cadena principal desde el último bloque de instantánea.

Conclusión

En este documento analizamos enfoques para crear blockchains fragmentados y cubrió dos desafíos principales con los enfoques existentes, a saber, la validez del estado y disponibilidad de datos. Luego presentamos Nightshade, un diseño de fragmentación que poderes NEAR Protocolo. El diseño es un trabajo en progreso, si tiene comentarios, preguntas o comentarios en este documento, vaya a https://near.chat.