Resumen

Un libro de contabilidad público es una secuencia de datos a prueba de manipulaciones que todos pueden leer y ampliar. Los libros públicos tienen innumerables y convincentes usos. Pueden asegurar, a simple vista, todo tipo de transacciones —como títulos, ventas y pagos— en el orden exacto en que ocurren. Los libros públicos no sólo frenan la corrupción, sino que también permiten aplicaciones muy sofisticadas, como criptomonedas y smart contracts. Se proponen revolucionar la forma en que una sociedad democrática opera. Sin embargo, tal como se implementan actualmente, su escalabilidad es deficiente y no pueden alcanzar su potencial. Algorand es una forma verdaderamente democrática y eficiente de implementar un libro de contabilidad público. A diferencia del anterior implementaciones basadas en prueba de trabajo, requiere una cantidad insignificante de cálculo, y genera un historial de transacciones que no se “bifurcará” con una probabilidad abrumadoramente alta. Algorand se basa en un acuerdo bizantino de transmisión de mensajes (novedoso y súper rápido). Para ser más concretos, describiremos Algorand únicamente como una plataforma monetaria.

Introducción

El dinero es cada vez más virtual. Se ha estimado que alrededor del 80% de los Estados Unidos Los dólares hoy solo existen como asientos contables [5]. Otros instrumentos financieros están siguiendo el ejemplo. En un mundo ideal, en el que pudiéramos contar con una entidad central de confianza universal, inmune Ante todos los posibles ciberataques, el dinero y otras transacciones financieras podrían ser únicamente electrónicas. Desafortunadamente, no vivimos en un mundo así. En consecuencia, las criptomonedas descentralizadas, como como Bitcoin [29], y sistemas “smart contract”, como Ethereum, se han propuesto [4]. en El corazón de estos sistemas es un libro de contabilidad compartido que registra de manera confiable una secuencia de transacciones, ∗Esta es la versión más formal (y asincrónica) del artículo ArXiv del segundo autor [24], un artículo basado en el de Gorbunov y Micali [18]. Las tecnologías de Algorand son objeto de las siguientes solicitudes de patente: US62/117,138 US62/120,916 US62/142,318 US62/218,817 US62/314,601 PCT/US2016/018300 US62/326,865 62/331,654 US62/333,340 US62/343,369 US62/344,667 US62/346,775 US62/351,011 US62/653,482 US62/352,195 US62/363,970 US62/369,447 US62/378,753 US62/383,299 US62/394,091 US62/400,361 US62/403,403 US62/410,721 US62/416,959 US62/422,883 US62/455,444 US62/458,746 US62/459,652 US62/460,928 US62/465,931tan variados como pagos y contratos, de forma a prueba de manipulaciones. La tecnología elegida para garantizar dicha inviolabilidad es el blockchain. Las cadenas de bloques están detrás de aplicaciones como criptomonedas [29], aplicaciones financieras [4] e Internet de las cosas [3]. Varias técnicas para gestionar libros de contabilidad basados en blockchain se han propuesto: prueba de trabajo [29], prueba de participación [2], práctica tolerancia a fallos bizantinos [8], o alguna combinación. Sin embargo, en la actualidad, la gestión de los libros de contabilidad puede resultar ineficiente. Por ejemplo, Bitcoin proof-of-work El enfoque (basado en el concepto original de [14]) requiere una gran cantidad de cálculos y es un desperdicio. y escala mal [1]. Además, de facto concentra el poder en muy pocas manos. Por lo tanto, deseamos proponer un nuevo método para implementar un libro de contabilidad público que ofrezca la conveniencia y eficiencia de un sistema centralizado administrado por una autoridad confiable e inviolable, sin las ineficiencias y debilidades de las implementaciones descentralizadas actuales. Llamamos a nuestro enfoque Algorand, porque utilizamos aleatoriedad algorítmica para seleccionar, según el libro mayor construido hasta ahora, un conjunto de verificadores que están a cargo de construir el siguiente bloque de transacciones válidas. Naturalmente, Nos aseguramos de que dichas selecciones sean demostrablemente inmunes a manipulaciones e impredecibles hasta el momento. en el último momento, sino también que, en última instancia, sean universalmente claras. El enfoque de Algorand es bastante democrático, en el sentido de que ni en principio ni de facto crea diferentes clases de usuarios (como “mineros” y “usuarios comunes” en Bitcoin). En Algorand “todos el poder reside en el conjunto de todos los usuarios”. Una propiedad notable de Algorand es que su historial de transacciones puede bifurcarse sólo con cantidades muy pequeñas. probabilidad (por ejemplo, una entre un billón, es decir, o incluso 10-18). Algorand también puede abordar algunos temas legales. y preocupaciones políticas. El enfoque Algorand se aplica a blockchains y, más generalmente, a cualquier método de generación una secuencia de bloques a prueba de manipulaciones. De hecho, propusimos un nuevo método, alternativo y más eficiente que blockchains, eso puede ser de interés independiente. 1.1 Supuestos y problemas técnicos de Bitcoin Bitcoin es un sistema muy ingenioso y ha inspirado una gran cantidad de investigaciones posteriores. Sin embargo, También es problemático. Resumamos sus supuestos subyacentes y sus problemas técnicos, que En realidad, son compartidos por prácticamente todas las criptomonedas que, como Bitcoin, se basan en proof-of-work. Para este resumen, basta recordar que, en Bitcoin, un usuario puede poseer varias claves públicas de un esquema de firma digital, que el dinero está asociado con claves públicas y que un pago es un Firma digital que transfiere una cierta cantidad de dinero de una clave pública a otra. Esencialmente, Bitcoin organiza todos los pagos procesados en una cadena de bloques, B1, B2, . . ., cada uno compuesto por múltiples pagos, de modo que todos los pagos de B1, tomados en cualquier orden, seguidos de los de B2, en cualquier orden, etc., constituyen una secuencia de pagos válidos. Cada bloque se genera, en promedio, cada 10 minutos. Esta secuencia de bloques es una cadena, porque está estructurada de manera que garantice que cualquier cambio, incluso en un solo bloque, se filtra en todos los bloques posteriores, lo que facilita la detección de cualquier alteración de el historial de pagos. (Como veremos, esto se consigue incluyendo en cada bloque un código criptográfico hash del anterior). Dicha estructura de bloques se denomina blockchain. Supuesto: mayoría honesta de potencia computacional Bitcoin asume que no hay ningún malicioso entidad (ni una coalición de entidades maliciosas coordinadas) controla la mayoría de los procesos computacionales. energía dedicada a la generación de bloques. De hecho, dicha entidad podría modificar el blockchain,y así reescribir el historial de pagos, como le plazca. En particular, podría realizar un pago \(\wp\), obtener los beneficios pagados y luego “borrar” cualquier rastro de \(\wp\). Problema técnico 1: Desperdicio computacional Enfoque proof-of-work de Bitcoin para bloquear La generación requiere una cantidad extraordinaria de cálculos. Actualmente, con sólo unos pocos cientos miles de claves públicas en el sistema, las 500 supercomputadoras más poderosas solo pueden reunir apenas el 12,8% por ciento de la potencia computacional total requerida de los jugadores Bitcoin. esto La cantidad de cálculo aumentaría considerablemente si un número significativamente mayor de usuarios se unieran al sistema. Problema técnico 2: concentración de poder Hoy, debido a la exorbitante cantidad de cálculo requerido, un usuario, que intenta generar un nuevo bloque usando un escritorio normal (y mucho menos un teléfono celular), espera perder dinero. De hecho, para calcular un nuevo bloque con una computadora común, el costo esperado de la electricidad necesaria para impulsar el cálculo excede la recompensa esperada. Utilizando únicamente grupos de computadoras especialmente construidas (que no hacen nada más que "extraer nuevos bloques"), uno podría esperar obtener ganancias generando nuevos bloques. En consecuencia, hoy existen, de facto, dos clases disjuntas de usuarios: usuarios comunes, que solo realizan pagos, y grupos de minería especializados, que solo buscan nuevos bloques. Por lo tanto, no debería sorprender que, hasta hace poco, la potencia informática total de los bloques La generación se encuentra dentro de sólo cinco grupos. En tales condiciones, el supuesto de que la mayoría de los el poder computacional es honesto se vuelve menos creíble. Problema técnico 3: ambigüedad En Bitcoin, blockchain no es necesariamente único. De hecho su última porción a menudo se bifurca: el blockchain puede ser, digamos, B1,. . . , Bk, B′ k+1, B′ k+2, según un usuario, y B1, . . . , Bk, B′′ k+1, B′′ k+2, B′′ k+3 según otro usuario. Sólo después de varios bloques agregado a la cadena, ¿se puede estar razonablemente seguro de que los primeros k + 3 bloques serán los mismos? para todos los usuarios. Por tanto, no se puede confiar inmediatamente en los pagos contenidos en el último bloque de la cadena. Es más prudente esperar y ver si el bloque se vuelve lo suficientemente profundo en el blockchain y, por tanto, suficientemente estable. Por otra parte, también se han planteado preocupaciones sobre la aplicación de la ley y la política monetaria sobre Bitcoin.1 1.2 Algorand, en pocas palabras Configuración Algorand trabaja en un entorno muy difícil. Brevemente, (a) Entornos sin permiso y con permiso. Algorand funciona de manera eficiente y segura incluso en un entorno totalmente sin permisos, donde arbitrariamente muchos usuarios pueden unirse al sistema en cualquier momento, sin ningún tipo de investigación o permiso de ningún tipo. Por supuesto, Algorand funciona Aún mejor en un entorno autorizado. 1El (pseudo) anonimato que ofrecen los pagos Bitcoin puede utilizarse indebidamente para el lavado de dinero y/o la financiación. de personas criminales u organizaciones terroristas. Los billetes tradicionales o lingotes de oro, que en principio ofrecen una perfecta anonimato, debería plantear el mismo desafío, pero la fisicalidad de estas monedas ralentiza sustancialmente el movimiento del dinero. transferencias, a fin de permitir cierto grado de supervisión por parte de los organismos encargados de hacer cumplir la ley. La capacidad de “imprimir dinero” es uno de los poderes básicos de un Estado nación. Por lo tanto, en principio, la masiva La adopción de una moneda con flotación independiente puede limitar este poder. Sin embargo, actualmente Bitcoin está lejos de ser una amenaza para las políticas monetarias gubernamentales y, debido a sus problemas de escalabilidad, puede que nunca lo sea.(b) Entornos muy conflictivos. Algorand resiste a un Adversario muy poderoso, que puede (1) corromper instantáneamente a cualquier usuario que desee, en cualquier momento que desee, siempre que, en un entorno sin permisos, 2/3 del dinero en el sistema pertenece al usuario honesto. (En un entorno autorizado, independientemente del dinero, basta con que 2/3 de los usuarios sean honestos.) (2) controlar totalmente y coordinar perfectamente a todos los usuarios corruptos; y (3) programar la entrega de todos los mensajes, siempre que cada mensaje sea enviado por un usuario honesto llega al 95% de los usuarios honestos en un tiempo \(\lambda\)m, que depende únicamente del tamaño de m. Propiedades principales A pesar de la presencia de nuestro poderoso adversario, en Algorand • La cantidad de cálculo requerida es mínima. Básicamente, no importa cuántos usuarios haya presentes en el sistema, cada uno de los mil quinientos usuarios debe realizar como máximo unos segundos de cálculo. • Se genera un nuevo bloque en menos de 10 minutos y, de facto, nunca saldrá del blockchain. Por ejemplo, en la expectativa, el tiempo para generar un bloque en la primera realización es menor que Λ + 12,4\(\lambda\), donde Λ es el tiempo necesario para propagar un bloque, en un chisme entre pares manera, no importa qué tamaño de bloque se elija, y \(\lambda\) es el tiempo para propagar 1.500 mensajes 200Blong. (Dado que en un sistema verdaderamente descentralizado, Λ es esencialmente una latencia intrínseca, en Algorand el factor limitante en la generación de bloques es la velocidad de la red). La segunda realización tiene en realidad ha sido probado experimentalmente (¿por ?), lo que indica que un bloque se genera en menos de 40 segundos. Además, el blockchain de Algorand puede bifurcarse sólo con una probabilidad insignificante (es decir, menos de un en un billón), y así los usuarios pueden transmitir los pagos contenidos en un nuevo bloque tan pronto como el Aparece el bloque. • Todo el poder reside en los propios usuarios. Algorand es un verdadero sistema distribuido. En particular, no hay entidades exógenas (como los “mineros” en Bitcoin), que puedan controlar qué transacciones son reconocidos. Técnicas de Algorand. 1. Un nuevo y rápido protocolo de acuerdo bizantino. Algorand genera un nuevo bloque vía un nuevo protocolo de acuerdo bizantino (BA) binario criptográfico, de paso de mensajes, BA⋆. Protocolo BA⋆ no sólo satisface algunas propiedades adicionales (que discutiremos pronto), sino que también es muy rápido. En términos generales, su versión de entrada binaria consiste en un bucle de 3 pasos, en el que un jugador i envía un único envía un mensaje mi a todos los demás jugadores. Ejecutado en red completa y síncrona, con más siendo honestos más de 2/3 de los jugadores, con probabilidad > 1/3, después de cada bucle el protocolo termina en acuerdo. (Hacemos hincapié en que el protocolo BA⋆satisface la definición original de acuerdo bizantino de Pease, Shostak y Lamport [31], sin debilitamientos). Algorand aprovecha este protocolo BA binario para llegar a un acuerdo, en nuestras diferentes comunicaciones modelo, en cada nuevo bloque. Luego se certifica el bloque acordado, mediante un número prescrito de firma digital de los verificadores correspondientes, y se propaga a través de la red. 2. Ordenación criptográfica. Aunque es muy rápido, el protocolo BA⋆se beneficiaría de una mayor velocidad cuando lo juegan millones de usuarios. En consecuencia, Algorand elige a los jugadores de BA⋆para serun subconjunto mucho más pequeño del conjunto de todos los usuarios. Para evitar un tipo diferente de concentración de poder problema, cada nuevo bloque Br será construido y acordado, mediante una nueva ejecución de BA⋆, por un conjunto separado de verificadores seleccionados, SV r. En principio, seleccionar un conjunto de este tipo podría ser tan difícil como seleccionando Br directamente. Atravesamos este problema potencial mediante un enfoque que denominamos abarcar la perspicaz sugerencia de Maurice Herlihy, la clasificación criptográfica. La clasificación es la práctica de seleccionar funcionarios al azar de un gran conjunto de personas elegibles [6]. (Se practicó la clasificación a lo largo de los siglos: por ejemplo, por las repúblicas de Atenas, Florencia y Venecia. En la justicia moderna En estos sistemas, la selección aleatoria se utiliza a menudo para elegir a los jurados. El muestreo aleatorio también se ha utilizado recientemente. defendido para las elecciones por David Chaum [9].) En un sistema descentralizado, por supuesto, elegir el Las monedas aleatorias necesarias para seleccionar aleatoriamente los miembros de cada conjunto de verificador SV r son problemáticas. Por tanto, recurrimos a la criptografía para seleccionar cada conjunto de verificadores, de la población de todos los usuarios, de una manera que se garantiza que será automática (es decir, que no requiere intercambio de mensajes) y aleatoria. En esencia, utilizamos una función criptográfica para determinar automáticamente, a partir del bloque anterior Br−1, un usuario, el líder, encargado de proponer el nuevo bloque Br, y el verificador establece SV r, en encargado de llegar a un acuerdo sobre el bloque propuesto por el dirigente. Dado que los usuarios malintencionados pueden afectar la composición de Br−1 (por ejemplo, eligiendo algunos de sus pagos), construimos y utilizamos especialmente entradas adicionales para demostrar que el líder para el bloque r y el conjunto de verificador SV r son de hecho elegidos al azar. 3. La Cantidad (Semilla) Qr. Usamos el último bloque Br−1 en blockchain para determinar automáticamente el siguiente conjunto de verificadores y el líder a cargo de construir el nuevo bloque Hno. El desafío de este enfoque es que, con sólo elegir un pago ligeramente diferente en el En la ronda anterior, nuestro poderoso adversario obtiene un tremendo control sobre el siguiente líder. Incluso si el sólo controlaba 1/1000 de los jugadores/dinero en el sistema, podía garantizar que todos los líderes estuvieran malicioso. (Consulte la Sección 4.1 de Intuición). Este desafío es fundamental para todos los enfoques proof-of-stake, y, hasta donde sabemos, hasta el momento no se ha resuelto satisfactoriamente. Para enfrentar este desafío, construimos intencionalmente y actualizamos continuamente un sistema separado y cuidadosamente cantidad definida, Qr, que probablemente no sólo es impredecible, sino que tampoco puede ser influenciada por nuestro poderoso adversario. Podemos referirnos a Qr como la r-ésima semilla, ya que es de Qr que Algorand selecciona, mediante clasificación criptográfica secreta, todos los usuarios que desempeñarán un papel especial en la generación del bloque r. 4. Clasificación critográfica secreta y credenciales secretas. Utilizar aleatoriamente y sin ambigüedades el último bloque actual, Br-1, para elegir el conjunto de verificadores y el líder a cargo. de construir el nuevo bloque, Br, no es suficiente. Dado que Br−1 debe conocerse antes de generar Br, También se debe conocer la última cantidad no influenciable Qr−1 contenida en Br−1. En consecuencia, entonces son los verificadores y el líder encargado de calcular el bloque Br. Así, nuestro poderoso adversario podría corromperlos a todos inmediatamente, antes de que entablen cualquier discusión sobre Br, para obtener control total sobre el bloque que certifican. Para evitar este problema, los líderes (y en realidad también los verificadores) aprenden en secreto su papel, pero pueden calcular una credencial adecuada, capaz de demostrar a todos que efectivamente tienen ese rol. cuando Si un usuario se da cuenta en privado de que es el líder del siguiente bloque, primero reúne en secreto su propio nuevo bloque propuesto, y luego lo difunde (para que pueda ser certificado) junto con su propio credencial. De esta manera, aunque el Adversario se dará cuenta inmediatamente de quién es el líder del próximo bloque es, y aunque puede corromperlo de inmediato, será demasiado tarde para que el Adversario Influir en la elección de un nuevo bloque. De hecho, ya no puede “revocar” el mensaje del líder.de lo que un gobierno poderoso puede volver a encerrar en la botella un mensaje difundido viralmente por WikiLeaks. Como veremos, no podemos garantizar la unicidad del líder, ni que todos estén seguros de quién es el líder. es, ¡incluido el propio líder! Pero en Algorand se garantizará un progreso inequívoco. 5. Reemplazabilidad de jugadores. Después de proponer un nuevo bloque, el líder también podría “morir” (o ser corrompido por el Adversario), porque su trabajo está hecho. Pero, para los verificadores en SV r, las cosas son menos sencillo. En efecto, siendo el encargado de certificar el nuevo bloque Br con suficientes firmas, primero deben ejecutar un acuerdo bizantino sobre el bloque propuesto por el líder. El problema es que, No importa cuán eficiente sea, BA⋆requiere múltiples pasos y la honestidad de > 2/3 de sus jugadores. Esto es un problema porque, por razones de eficiencia, el conjunto de jugadores de BA⋆ consiste en el pequeño conjunto SV r seleccionados aleatoriamente entre el conjunto de todos los usuarios. Así, nuestro poderoso Adversario, aunque incapaz de corrompe 1/3 de todos los usuarios, ¡ciertamente puede corromper a todos los miembros de SV r! Afortunadamente, demostraremos que el protocolo BA⋆, ejecutado mediante la propagación de mensajes entre pares, es reemplazable por el jugador. Este novedoso requisito significa que el protocolo debe aplicarse correctamente y logra un consenso de manera eficiente incluso si cada uno de sus pasos es ejecutado por un proceso totalmente nuevo y aleatorio. conjunto de jugadores seleccionados independientemente. Así, con millones de usuarios, cada pequeño grupo de jugadores asociado a un paso de BA⋆muy probablemente tenga una intersección vacía con el siguiente conjunto. Además, los conjuntos de jugadores de diferentes pasos de BA⋆probablemente tendrán resultados totalmente diferentes. cardinalidades. Además, los miembros de cada grupo no saben quién será el próximo grupo de jugadores. ser, y no pasar en secreto ningún estado interno. La propiedad del jugador reemplazable es realmente crucial para derrotar al dinámico y muy poderoso Adversario que imaginamos. Creemos que los protocolos de jugadores reemplazables resultarán cruciales en muchos Contextos y aplicaciones. En particular, serán cruciales para ejecutar de forma segura pequeños subprotocolos. incrustado en un universo más grande de jugadores con un adversario dinámico, quien, siendo capaz de corromper incluso una pequeña fracción del total de jugadores, no tiene dificultad en corromper a todos los jugadores en el grupo más pequeño. subprotocolo. Una propiedad/técnica adicional: la honestidad perezosa Un usuario honesto sigue lo prescrito. instrucciones, que incluyen estar en línea y ejecutar el protocolo. Desde entonces, Algorand solo tiene una modesta requisito de computación y comunicación, estar en línea y ejecutar el protocolo “en el antecedentes” no es un sacrificio importante. Por supuesto, algunas “ausencias” entre jugadores honestos, como aquellas debido a una pérdida repentina de conectividad o la necesidad de reiniciar, se toleran automáticamente (porque siempre podemos considerar que esos pocos jugadores sean temporalmente maliciosos). Señalemos, sin embargo, que Algorand se puede adaptar simplemente para que funcione en un nuevo modelo, en el que los usuarios honestos puedan ser fuera de línea la mayor parte del tiempo. Nuestro nuevo modelo se puede presentar informalmente de la siguiente manera. Honestidad perezosa. En términos generales, un usuario i es vago pero honesto si (1) sigue todas las instrucciones prescritas. instrucciones, cuando se le pide que participe en el protocolo, y (2) se le pide que participe al protocolo sólo en raras ocasiones y con la debida antelación. Con una noción tan relajada de honestidad, podemos estar aún más seguros de que las personas honestas serán a mano cuando los necesitemos, y Algorand garantizan que, cuando este sea el caso, El sistema funciona de forma segura incluso si, en un momento dado, la mayoría de los jugadores participantes son maliciosos.1.3 Trabajo estrechamente relacionado Los enfoques de prueba de trabajo (como los citados [29] y [4]) son bastante ortogonales a los nuestros. Así son los enfoques basados en el acuerdo bizantino de transmisión de mensajes o en la práctica tolerancia a fallos bizantinos (como el citado [8]). De hecho, estos protocolos no pueden ejecutarse entre el conjunto de todos los usuarios y no pueden, en nuestro modelo, estar restringido a un conjunto adecuadamente pequeño de usuarios. De hecho, nuestro poderoso adversario mi corrompe inmediatamente a todos los usuarios involucrados en un pequeño conjunto encargado de ejecutar un protocolo BA. Nuestro enfoque podría considerarse relacionado con la prueba de participación [2], en el sentido de que el "poder" de los usuarios en la construcción de bloques es proporcional al dinero que poseen en el sistema (a diferencia de, digamos, el dinero que han puesto en “escrow”). El artículo más cercano al nuestro es el Sleepy Consensus Model of Pass and Shi [30]. Para evitar el cálculo pesado requerido en el enfoque proof-of-work, su artículo se basa (y amablemente) créditos) Clasificación criptográfica secreta de Algorand. Con este aspecto crucial en común, varios Existen diferencias significativas entre nuestros artículos. En particular, (1) Su configuración sólo está permitida. Por el contrario, Algorand también es un sistema sin permisos. (2) Usan un protocolo estilo Nakamoto y, por lo tanto, su blockchain se bifurca con frecuencia. aunque prescindiendo de proof-of-work, en su protocolo se le pide a un líder seleccionado en secreto que alargue el válido más largo (en un sentido más rico) blockchain. Por lo tanto, las bifurcaciones son inevitables y hay que esperar a que el bloque está lo suficientemente “profundo” en la cadena. De hecho, para lograr sus objetivos con un adversario capaces de corrupciones adaptativas, requieren que un bloque tenga una profundidad poli(N), donde N representa el Número total de usuarios del sistema. Observe que, incluso suponiendo que se pudiera producir un bloque en un minuto, si hubiera N = 1 millón de usuarios, entonces habría que esperar unos 2 millones de años para un bloque se convierta en N 2 de profundidad, y durante aproximadamente 2 años para que un bloque alcance N 2 de profundidad. Por el contrario, El blockchain de Algorand se bifurca solo con una probabilidad insignificante, a pesar de que el Adversario es corrupto. usuarios de forma inmediata y adaptable, y se puede confiar inmediatamente en sus nuevos bloques. (3) No manejan acuerdos bizantinos individuales. En cierto sentido, sólo garantizan “eventual consenso sobre una secuencia creciente de valores”. El suyo es un protocolo de replicación estatal, más bien que uno de BA, y no se puede utilizar para llegar a un acuerdo bizantino sobre un valor de interés individual. Por el contrario, Algorand también se puede utilizar sólo una vez, si así se desea, para permitir a millones de usuarios acceder rápidamente llegar a un acuerdo bizantino sobre un valor de interés específico. (4) Requieren relojes débilmente sincronizados. Es decir, los relojes de todos los usuarios están compensados por un pequeño tiempo. δ. Por el contrario, en Algorand, los relojes sólo necesitan tener (esencialmente) la misma "velocidad". (5) Su protocolo funciona con usuarios perezosos pero honestos o con la mayoría honesta de usuarios en línea. Amablemente le dan crédito a Algorand por plantear el problema de los usuarios honestos que se desconectan en masa y por presentando como respuesta el modelo de honestidad perezosa. Su protocolo no sólo funciona en los perezosos modelo de honestidad, sino también en su modelo adversario somnoliento, donde un adversario elige qué usuarios están en línea y cuáles fuera de línea, siempre que, en todo momento, la mayoría de los usuarios en línea sean honestos.2 2La versión original de su artículo en realidad consideraba sólo la seguridad en su modelo adversario y somnoliento. el versión original de Algorand, que precede a la suya, también preveía explícitamente asumir que una mayoría dada de los Los jugadores en línea siempre son honestos, pero lo excluyen explícitamente de su consideración, a favor del modelo de honestidad perezosa. (Por ejemplo, si en algún momento la mitad de los usuarios honestos deciden desconectarse, entonces la mayoría de los usuarios en línea puede muy bien ser malicioso. Por lo tanto, para evitar que esto suceda, el Adversario debería forzar la mayor parte de sus jugadores corruptos también se desconecten, lo que claramente va en contra de sus propios intereses.) Observe que un protocolo con una mayoría de jugadores perezosos pero honestos funciona bien si la mayoría de los usuarios en línea son siempre maliciosos. Esto es así, porque un número suficiente de jugadores honestos, sabiendo que van a ser cruciales en algún momento excepcional, elegirán no desconectarse en esos momentos, ni pueden ser forzados a desconectarse por el Adversario, ya que no sabe quién es el Los jugadores honestos cruciales podrían serlo.(6) Requieren una mayoría simple y honesta. Por el contrario, la versión actual de Algorand requiere una mayoría honesta de 2/3. Otro artículo cercano a nosotros es Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol, por Kiayias, Russell, David y Oliynykov [20]. Además, su sistema apareció después del nuestro. También utiliza clasificación criptográfica para prescindir de la prueba de trabajo de manera demostrable. Sin embargo, sus El sistema es, nuevamente, un protocolo al estilo Nakamoto, en el que las bifurcaciones son inevitables y frecuentes. (Sin embargo, en su modelo, los bloqueos no tienen por qué ser tan profundos como en el modelo de consenso somnoliento). Además, su sistema se basa en los siguientes supuestos: en palabras de los propios autores, “(1) el La red es altamente sincrónica, (2) la mayoría de las partes interesadas seleccionadas están disponibles según sea necesario. para participar en cada época, (3) las partes interesadas no permanecen desconectadas durante largos períodos de tiempo, (4) la adaptabilidad de las corrupciones está sujeta a un pequeño retraso que se mide en rondas lineales en el parámetro de seguridad”. Por el contrario, Algorand, con una probabilidad abrumadora, no tiene bifurcación y no se basa en ninguno de estos 4 supuestos. En particular, en Algorand, el Adversario puede corrompe instantáneamente a los usuarios que quiere controlar.

Preliminares

2.1 Primitivas criptográficas Hashing ideal. Nos basaremos en una función criptográfica hash eficientemente computable, H, que asigna cadenas arbitrariamente largas a cadenas binarias de longitud fija. Siguiendo una larga tradición, modelamos H como un oracle aleatorio, esencialmente una función que asigna cada cadena posible s a una secuencia aleatoria y cadena binaria seleccionada independientemente (y luego fijada), H(s), de la longitud elegida. En este artículo, H tiene salidas de 256 bits de longitud. De hecho, dicha longitud es lo suficientemente corta como para hacer que el sistema eficiente y lo suficientemente largo para que el sistema sea seguro. Por ejemplo, queremos que H sea resistente a las colisiones. Es decir, debería ser difícil encontrar dos cadenas diferentes xey tales que H(x) = H(y). Cuando H es un oracle aleatorio con salidas de 256 bits de longitud, encontrar dicho par de cadenas es realmente difícil. (Probar al azar y confiar en la paradoja del cumpleaños requeriría 2256/2 = 2128 ensayos.) Firma Digital. Las firmas digitales permiten a los usuarios autenticar información entre sí sin compartir ninguna clave secreta. Un esquema de firma digital consta de tres rápidos algoritmos: un generador de claves probabilísticas G, un algoritmo de firma S y un algoritmo de verificación V. Dado un parámetro de seguridad k, un número entero suficientemente alto, un usuario i usa G para producir un par de Claves de k bits (es decir, cadenas): una clave pki "pública" y una clave de firma "secreta" coincidente. Fundamentalmente, un La clave pública no “traiciona” su correspondiente clave secreta. Es decir, incluso dado el conocimiento de pki, no otro que yo es capaz de calcular el esquí en menos de un tiempo astronómico. El usuario i utiliza ski para firmar mensajes digitalmente. Para cada mensaje posible (cadena binaria) m, primero hashes m y luego ejecuta el algoritmo S en las entradas H(m) y ski para producir la cadena de k bits sigpki(m) \(\triangleq\)S(H(m), esquí) .3 3Dado que H es resistente a colisiones, es prácticamente imposible que, al firmar uno “accidentalmente” un signo diferente. mensaje m′.La cadena binaria sigpki(m) se conoce como la firma digital de m (relativa a pki) y puede ser denotado más simplemente por sigi(m), cuando la clave pública pki se desprende del contexto. Cualquiera que conozca pki puede utilizarlo para verificar las firmas digitales producidas por i. Específicamente, en ingresa (a) la clave pública pki de un jugador i, (b) un mensaje m, y (c) una cadena s, es decir, la supuesta i firma digital del mensaje m, el algoritmo de verificación V genera SÍ o NO. Las propiedades que requerimos de un esquema de firma digital son: 1. Siempre se verifican las firmas legítimas: Si s = sigi(m), entonces V (pki, m, s) = Y ES; y 2. Las firmas digitales son difíciles de falsificar: sin conocimientos de esquí, el tiempo para encontrar una cadena como que V (pki, m, s) = Y ES, para un mensaje m nunca firmado por i, es astronómicamente largo. (Siguiendo los estrictos requisitos de seguridad de Goldwasser, Micali y Rivest [17], esto es cierto incluso si se puede obtener la firma de cualquier otro mensaje.) En consecuencia, para evitar que alguien más firme mensajes en su nombre, un jugador debe conservar su clave de firma secreta (de ahí el término "clave secreta") y para permitir que cualquiera verifique los mensajes Si firma, tengo interés en hacer pública su clave pki (de ahí el término “clave pública”). En general, un mensaje m no se puede recuperar a partir de su firma sigi(m). Para tratar virtualmente con firmas digitales que satisfacen la propiedad de “recuperabilidad” conceptualmente conveniente (es decir, Para garantizar que el firmante y el mensaje sean fácilmente computables a partir de una firma, definimos SIGpki(m) = (i, m, sigpki(m)) y SIGi(m) = (i, m, sigi(m)), si pki está claro. Firma digital única. También consideramos esquemas de firma digital (G, S, V) que satisfacen los siguiente propiedad adicional. 3. Unicidad. Es difícil encontrar cadenas pk′, m, s y s′ tales que ̸= s′ y V (pk′, m, s) = V (pk′, m, s′) = 1. (Tenga en cuenta que la propiedad de unicidad también se aplica a las cadenas pk′ que no se generan legítimamente claves públicas. Sin embargo, en particular, la propiedad de unicidad implica que, si se utilizara la generador de claves especificado G para calcular una clave pública pk junto con una clave secreta coincidente sk, y por lo tanto sabía sk, también le sería esencialmente imposible encontrar dos números digitales diferentes. firmas de un mismo mensaje en relación con pk.) Observaciones • Desde firmas únicas hasta funciones aleatorias verificables. En relación con lo digital esquema de firma con la propiedad de unicidad, el mapeo m \(\to\) H(sigi(m)) se asocia a cada cadena posible m, una cadena única, seleccionada aleatoriamente, de 256 bits, y la exactitud de esta El mapeo se puede probar con la firma sigi(m). Es decir, el esquema ideal de hashing y firma digital que satisface esencialmente la propiedad de unicidad. proporcionar una implementación elemental de una función aleatoria verificable, tal como se introdujo y por Micali, Rabin y Vadhan [27]. (Su implementación original fue necesariamente más compleja, ya que no se basaron en el hashing ideal).• Tres necesidades diferentes de firmas digitales. En Algorand, un usuario i depende de lo digital firmas para (1) Autenticar mis propios pagos. En esta aplicación, las claves pueden ser "a largo plazo" (es decir, utilizadas para firmar muchos mensajes durante un largo período de tiempo) y provienen de un esquema de firma ordinario. (2) Generar credenciales que demuestren que i tiene derecho a actuar en algunos pasos s de una ronda r. Aquí, Las claves pueden ser de largo plazo, pero deben provenir de un esquema que satisfaga la propiedad de unicidad. (3) Autenticar el mensaje que envío en cada paso en el que actúa. Aquí las claves deben ser efímero (es decir, destruido después de su primer uso), pero puede provenir de un esquema de firma ordinario. • Una simplificación de pequeño coste. Para simplificar, imaginamos que cada usuario i tenga una única clave a largo plazo. En consecuencia, dicha clave debe provenir de un esquema de firma con la unicidad propiedad. Esta simplicidad tiene un pequeño coste computacional. De hecho, normalmente son digitales únicos. Las firmas son ligeramente más caras de producir y verificar que las firmas ordinarias. 2.2 El libro público idealizado Algorand intenta imitar el siguiente sistema de pago, basado en un libro de contabilidad público idealizado. 1. El Estado Inicial. El dinero está asociado con claves públicas individuales (generadas de forma privada y propiedad de los usuarios). Dejando pk1, . . . , pkj sean las claves públicas iniciales y a1, . . . , aj sus respectivos cantidades iniciales de unidades monetarias, entonces el estado inicial es S0 = (pk1, a1), . . . , (pkj, aj), que se supone que es de conocimiento común en el sistema. 2. Pagos. Sea pk una clave pública que actualmente tiene \(\geq\)0 unidades monetarias, pk′ otra pública clave, y a′ un número no negativo no mayor que a. Entonces, un pago (válido) \(\wp\)es un pago digital firma, relativa a pk, que especifica la transferencia de a′ unidades monetarias de pk a pk′, juntas con alguna información adicional. En símbolos, \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), donde represento cualquier información adicional que se considere útil pero no confidencial (por ejemplo, tiempo información y un identificador de pago), y cualquier información adicional que se considere confidencial (p. ej., el motivo del pago, posiblemente las identidades de los propietarios de pk y pk′, etc.). Nos referimos a pk (o su propietario) como pagador, a cada pk′ (o su propietario) como beneficiario y a a′ como el monto del pago \(\wp\). Unirse gratis mediante pagos. Tenga en cuenta que los usuarios pueden unirse al sistema cuando lo deseen generando sus propios pares de claves pública/secreta. En consecuencia, la clave pública pk′ que aparece en el pago \(\wp\)anterior puede ser una clave pública recién generada que nunca había “poseído” dinero antes. 3. El libro mayor mágico. En el Sistema Idealizado, todos los pagos son válidos y aparecen en un formato a prueba de manipulaciones. lista L de conjuntos de pagos “publicados en el cielo” para que todos los vean: L = PAGO 1, PAGO 2, . . . ,Cada bloque PAY r+1 consta del conjunto de todos los pagos realizados desde la aparición del bloque PAGAR r. En el sistema ideal, aparece un nuevo bloque después de un período de tiempo fijo (o finito). Discusión. • Más pagos generales y resultados de transacciones no gastadas. De manera más general, si una clave pública pk posee una cantidad a, entonces un pago válido \(\wp\)de pk puede transferir las cantidades a′ 1, un' 2, . . ., respectivamente a las teclas pk′ 1, paquete′ 2, . . ., siempre que P ja' j \(\leq\)a. En Bitcoin y sistemas similares, el dinero propiedad de un paquete de clave pública se segrega en montos, y un pago \(\wp\)realizado por pk debe transferir dicho monto segregado a en su totalidad. Si pk desea transferir sólo una fracción a′ < a de a a otra clave, entonces también debe transferir la saldo, el resultado de la transacción no gastada, a otra clave, posiblemente pk mismo. Algorand también funciona con claves que tienen cantidades segregadas. Sin embargo, para centrarse en el aspectos novedosos de Algorand, es conceptualmente más sencillo ceñirse a nuestras formas de pago más simples y claves que tienen asociada una única cantidad. • Estado actual. El Esquema Idealizado no proporciona directamente información sobre la situación actual. estado del sistema (es decir, aproximadamente cuántas unidades monetarias tiene cada clave pública). Esta información es deducible del Magic Ledger. En el sistema ideal, un usuario activo almacena y actualiza continuamente la información de estado más reciente, o tendría que reconstruirlo, ya sea desde cero o desde la última vez que lo hizo. lo calculó. (En la próxima versión de este documento, aumentaremos Algorand para permitir su usuarios reconstruir el estado actual de manera eficiente.) • Seguridad y “Privacidad”. Las firmas digitales garantizan que nadie pueda falsificar un pago mediante otro usuario. En un pago \(\wp\), las claves públicas y el importe no están ocultas, pero sí la sensible información que soy. De hecho, solo H(I) aparece en \(\wp\), y dado que H es una función ideal hash, H(I) es un valor aleatorio de 256 bits y, por lo tanto, no hay forma de determinar qué era mejor que mediante simplemente adivinándolo. Sin embargo, para probar lo que yo era (por ejemplo, para probar el motivo del pago), el el pagador puede simplemente revelar I. La exactitud de la I revelada puede verificarse calculando H(I) y comparando el valor resultante con el último elemento de \(\wp\). De hecho, dado que H es resistente a colisiones, es difícil encontrar un segundo valor I′ tal que H(I) = H(I′). 2.3 Nociones y notaciones básicas Claves, usuarios y propietarios A menos que se especifique lo contrario, cada clave pública (“clave” para abreviar) es de largo plazo y relativa a un esquema de firma digital con la propiedad de unicidad. Una clave pública a la que me uno el sistema cuando otra clave pública j que ya está en el sistema realiza un pago a i. Para el color, personificamos las claves. Nos referimos a una clave i como “él”, decimos que es honesto, que envía y recibe mensajes, etc. Usuario es sinónimo de clave. Cuando queremos distinguir una clave de la persona a la que pertenece, utilizamos respectivamente los términos “clave digital” y “propietario”. Sistemas sin permiso y con permiso. Un sistema no tiene permiso si una clave digital está libre unirse en cualquier momento y un propietario puede poseer varias claves digitales; y está permitido, de lo contrario.Representación única Cada objeto en Algorand tiene una representación única. En particular, cada conjunto {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} está ordenado de una manera preespecificada: por ejemplo, primero lexicográficamente en x, luego en y, etc. Relojes de la misma velocidad No existe un reloj global: cada usuario tiene su propio reloj. Relojes de usuario No es necesario sincronizarlo de ninguna manera. Sin embargo, suponemos que todos tienen la misma velocidad. Por ejemplo, cuando son las 12:00 p.m. según el reloj de un usuario i, pueden ser las 2:30 p.m. según el reloj de un usuario i. el reloj de otro usuario j, pero cuando serán las 12:01 según el reloj de i, serán las 2:31 según al reloj de j. Es decir, “un minuto es igual (suficientemente, esencialmente igual) para cada usuario”. Rondas Algorand está organizado en unidades lógicas, r = 0, 1, . . ., llamadas rondas. Usamos consistentemente superíndices para indicar rondas. Para indicar que una cantidad no numérica Q (por ejemplo, una cadena, una clave pública, un conjunto, una firma digital, etc.) se refiere a una r redonda, simplemente escribimos Qr. Sólo cuando Q sea un número genuino (a diferencia de una cadena binaria interpretable como un número), no escribimos Q(r), de modo que el símbolo r no pueda interpretarse como el exponente de Q. En (el comienzo de una) ronda r > 0, el conjunto de todas las claves públicas es PKr y el estado del sistema es Sr = norte yo, un(r) yo, . . .  : i \(\in\)PKro , donde un(r) yo es la cantidad de dinero disponible para la clave pública i. Tenga en cuenta que PKr es deducible de Sr, y que Sr también puede especificar otros componentes para cada clave pública i. Para la ronda 0, PK0 es el conjunto de claves públicas iniciales y S0 es el estado inicial. Tanto PK0 como Se supone que S0 es de conocimiento común en el sistema. Para simplificar, al comienzo de la ronda r, entonces son PK1, . . . , PKr y S1, . . . , Sr. En una ronda r, el estado del sistema pasa de Sr a Sr+1: simbólicamente, Ronda r: Sr −→Sr+1. Pagos En Algorand, los usuarios realizan pagos continuamente (y los difunden de la forma descrito en la subsección 2.7). Un pago \(\wp\) de un usuario i \(\in\)PKr tiene el mismo formato y semántica como en el Sistema Ideal. Es decir, \(\wp\)= SIGi(i, i′, a, I, H(I)) . El pago \(\wp\) es válido individualmente en una ronda r (es un pago redondo r, para abreviar) si (1) su monto a es menor o igual que a(r) i, y (2) no aparece en ningún conjunto de pagos oficial PAY r′ para r′ < r. (Como se explica a continuación, la segunda condición significa que \(\wp\) aún no ha entrado en vigor. Un conjunto de pagos redondos de i es colectivamente válido si la suma de sus montos es como máximo a(r) yo. Conjuntos de pago Un conjunto de pagos redondo r P es un conjunto de pagos redondos r tales que, para cada usuario i, los pagos de i en P (posiblemente ninguno) son colectivamente válidos. El conjunto de todos los pagos de la ronda r es PAY(r). Una r redonda el conjunto de pagos P es máximo si ningún superconjunto de P es un conjunto de pagos redondo-r. De hecho, sugerimos que un pago \(\wp\) también especifique una ronda \(\rho\), \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , y no puede ser válido en ninguna ronda fuera de [\(\rho\), \(\rho\) + k], para algún entero fijo no negativo k.4 4Esto simplifica verificar si \(\wp\) se ha vuelto “efectivo” (es decir, simplifica determinar si algún pago PAGAR r contiene \(\wp\). Cuando k = 0, si \(\wp\)= SIGi(r, i, i′, a, I, H(I)) y \(\wp\)/\(\in\)PAY r, entonces debo volver a enviar \(\wp\).Pagos oficiales Para cada ronda r, Algorand selecciona públicamente (de la manera que se describe más adelante) un solo pago (posiblemente vacío), PAY r, el pago oficial de la ronda. (Esencialmente, PAY r representa los pagos redondos-r que “realmente” han ocurrido). Como en el Sistema Ideal (y Bitcoin), (1) la única forma para que un nuevo usuario j ingrese al sistema es ser el destinatario de un pago perteneciente al conjunto de pagos oficial PAY r de una ronda r determinada; y (2) EL PAGO r determina el estado de la siguiente ronda, Sr+1, a partir del de la ronda actual, Sr. Simbólicamente, PAGO r : Sr −→Sr+1. Específicamente, 1. el conjunto de claves públicas de la ronda r + 1, PKr+1, consta de la unión de PKr y el conjunto de todas claves de beneficiario que aparecen, por primera vez, en los pagos de PAY r; y 2. la cantidad de dinero a(r+1) yo que posee un usuario i en la ronda r + 1 es la suma de ai(r), es decir, el cantidad de dinero que poseí en la ronda anterior (0 si i ̸\(\in\)PKr)— y la suma de las cantidades pagado a i de acuerdo con los pagos de PAY r. En resumen, al igual que en el Sistema Ideal, cada estatus Sr+1 es deducible del historial de pagos anterior: PAGA 0, . . . , PAGAR r. 2.4 Bloques y bloques probados En Algorand0, el bloque Br correspondiente a una ronda r especifica: r mismo; el conjunto de pagos de ronda r, PAGAR r; una cantidad Qr, por explicar, y el hash del bloque anterior, H(Br−1). Así, partiendo de algún bloque fijo B0, tenemos un blockchain tradicional: B1 = (1, PAGO 1, Q0, H(B0)), B2 = (2, PAGO 2, Q1, H(B1)), B3 = (3, PAGAR 3, Q2, H(B2)), . . . En Algorand, la autenticidad de un bloque en realidad está garantizada por una información separada, un “certificado de bloque” CERT r, que convierte a Br en un bloque probado, Br. El Libro Mayor Mágico, por lo tanto, se implementa mediante la secuencia de los bloques probados, B1, B2, . . . Discusión Como veremos, CERT r consta de un conjunto de firmas digitales para H(Br), las de un mayoría de los miembros de SV r, junto con una prueba de que cada uno de esos miembros pertenece efectivamente a SV r. Por supuesto, podríamos incluir los certificados CERT r en los propios bloques, pero resultaría conceptualmente más limpio para mantenerlo separado). En Bitcoin cada bloque debe satisfacer una propiedad especial, es decir, debe “contener una solución de un cripto rompecabezas”, lo que hace que la generación de bloques sea computacionalmente intensiva y ambas bifurcaciones sean inevitables. y no raro. Por el contrario, el blockchain de Algorand tiene dos ventajas principales: se genera con cálculo mínimo y no se bifurcará con una probabilidad abrumadoramente alta. Cada bloque Bi es finalice de forma segura tan pronto como entre en blockchain.2.5 Probabilidad de falla aceptable Para analizar la seguridad de Algorand especificamos la probabilidad, F, con la que estamos dispuestos a aceptar que algo sale mal (por ejemplo, que un conjunto de verificadores SV r no tiene una mayoría honesta). Como en el caso de la longitud de salida de la función criptográfica hash H, también F es un parámetro. Pero, como en ese caso, nos resulta útil establecer F en un valor concreto, para obtener una interpretación más intuitiva. comprender el hecho de que es realmente posible, en Algorand, disfrutar simultáneamente de suficiente seguridad y suficiente eficiencia. Para enfatizar que F es un parámetro que se puede configurar como se desee, en la primera y segundas realizaciones que establecemos respectivamente F = 10-12 y F = 10-18. Discusión Tenga en cuenta que 10-12 es en realidad menos de uno en un billón, y creemos que tal La elección de F es adecuada en nuestra aplicación. Enfaticemos que 10−12 no es la probabilidad con el que el Adversario puede falsificar los pagos de un usuario honesto. Todos los pagos son digitales. firmado y, por lo tanto, si se utilizan las firmas digitales adecuadas, la probabilidad de falsificar un pago es mucho menor que 10−12 y, de hecho, es esencialmente 0. El mal evento que estamos dispuestos a tolerar con probabilidad F es que Algorand se bifurca blockchain. Observe que, con nuestra configuración de F y rondas de un minuto de duración, se espera que ocurra una bifurcación en el blockchain de Algorand con la menor frecuencia posible. (aproximadamente) una vez cada 1,9 millones de años. Por el contrario, en Bitcoin, las bifurcaciones ocurren con bastante frecuencia. Una persona más exigente puede establecer F en un valor más bajo. Con este fin, en nuestra segunda realización consideramos establecer F en 10−18. Tenga en cuenta que, suponiendo que se genera un bloque cada segundo, 1018 es el número estimado de segundos que ha tardado el Universo hasta el momento: desde el Big Bang hasta el presente tiempo. Por lo tanto, con F = 10−18, si se genera un bloque en un segundo, se debería esperar que para la edad de el Universo para ver una bifurcación. 2.6 El modelo adversario Algorand está diseñado para ser seguro en un modelo muy conflictivo. Expliquemos. Usuarios honestos y maliciosos Un usuario es honesto si sigue todas las instrucciones de su protocolo, y es perfectamente capaz de enviar y recibir mensajes. Un usuario es malicioso (es decir, bizantino, en el sentido lenguaje de computación distribuida) si puede desviarse arbitrariamente de sus instrucciones prescritas. El adversario El Adversario es un algoritmo eficiente (técnicamente de tiempo polinómico), personificado por el color, que puede convertir inmediatamente en malicioso a cualquier usuario que quiera, en cualquier momento que quiera (sujeto). sólo hasta un límite superior al número de usuarios que puede corromper). El Adversario controla totalmente y coordina perfectamente a todos los usuarios maliciosos. Él toma todas las acciones en su nombre, incluyendo recibir y enviar todos sus mensajes, y puede permitirles desviarse de sus instrucciones prescritas de manera arbitraria. O simplemente puede aislar a un usuario corrupto que envía y recibir mensajes. Aclaremos que nadie más se entera automáticamente de que un usuario i es malicioso, aunque su malicia puede traslucirse por las acciones que el Adversario le hace realizar. Este poderoso adversario, sin embargo, • No tiene un poder computacional ilimitado y no puede forjar con éxito la tecnología digital. firma de un usuario honesto, salvo con probabilidad insignificante; y• No puede interferir de ninguna manera con el intercambio de mensajes entre usuarios honestos. Además, su capacidad para atacar a usuarios honestos está limitada por uno de los siguientes supuestos. Honestidad Mayoría del dinero Consideramos un continuo de Mayoría Honesta del Dinero (HMM) supuestos: es decir, para cada entero no negativo k y real h > 1/2, HHMk > h: los usuarios honestos en cada ronda r poseían una fracción mayor que h de todo el dinero en el sistema en la ronda r −k. Discusión. Suponiendo que todos los usuarios malintencionados coordinan perfectamente sus acciones (como si estuvieran controlados por una sola entidad, el Adversario) es una hipótesis bastante pesimista. Coordinación perfecta entre también. para muchos individuos es difícil de lograr. Quizás la coordinación sólo se produzca dentro de grupos separados. de jugadores maliciosos. Pero como no se puede estar seguro del nivel de coordinación, los usuarios malintencionados podemos disfrutar, más vale prevenir que lamentar. Asumir que el Adversario puede corromper a los usuarios de forma secreta, dinámica e inmediata también es pesimista. Después de todo, de manera realista, tomar el control total de las operaciones de un usuario debería llevar algún tiempo. El supuesto HMMk > h implica, por ejemplo, que si se implementa una ronda (en promedio) Entonces, en un minuto, la mayor parte del dinero en una ronda determinada permanecerá en manos honestas durante al menos dos horas, si k = 120, y al menos una semana, si k = 10.000. Tenga en cuenta que los supuestos de HMM y la mayoría honesta de potencia informática anterior Los supuestos están relacionados en el sentido de que, dado que la potencia informática se puede comprar con dinero, Si los usuarios malintencionados poseen la mayor parte del dinero, entonces pueden obtener la mayor parte de la potencia informática. 2.7 El modelo de comunicación Prevemos que la propagación de mensajes —es decir, “chismes entre pares”5— sea el único medio de comunicación. Supuesto Temporal: Entrega Oportuna de Mensajes en Toda la Red. Para En la mayor parte de este artículo asumimos que cada mensaje propagado llega a casi todos los usuarios honestos. de manera oportuna. Eliminaremos esta suposición en la Sección 10, donde tratamos la red. particiones, ya sean naturales o inducidas adversamente. (Como veremos, sólo asumimos entrega oportuna de mensajes dentro de cada componente conectado de la red). Una forma concreta de capturar la entrega oportuna de mensajes propagados (en toda la red) es lo siguiente: Para toda accesibilidad \(\rho\) > 95% y tamaño de mensaje \(\mu\) \(\in\)Z+, existe \(\lambda\) \(\rho\),\(\mu\) tal que, si un usuario honesto propaga el mensaje m de \(\mu\)-byte en el momento t, entonces m alcanza, en el tiempo t + \(\lambda\) \(\rho\),μ, al menos una fracción \(\rho\) de los usuarios honestos. 5Esencialmente, como en Bitcoin, cuando un usuario propaga un mensaje m, cada usuario activo i recibe m por primera vez, selecciona aleatoriamente e independientemente un número adecuadamente pequeño de usuarios activos, sus "vecinos", a quienes reenvía m, posiblemente hasta que reciba un reconocimiento de ellos. La propagación de m termina cuando ningún usuario recibe m por primera vez.La propiedad anterior, sin embargo, no puede soportar nuestro protocolo Algorand, sin prever explícitamente y por separado un mecanismo para obtener el último blockchain, por parte de otro usuario/depósito/etc. De hecho, para construir un nuevo bloque Br no sólo se debe contar con un conjunto adecuado de verificadores que reciban oportunamente la ronda r. mensajes, sino también los mensajes de rondas anteriores, para conocer Br-1 y todos los demás mensajes anteriores. bloques, lo cual es necesario para determinar si los pagos en Br son válidos. lo siguiente en cambio, basta con asumirlo. Supuesto de propagación de mensajes (MP): Para todo \(\rho\) > 95% y \(\mu\) \(\in\)Z+, existe \(\lambda\) \(\rho\),\(\mu\) tal que, para todos los tiempos t y todos los mensajes de \(\mu\)-byte m propagados por un usuario honesto antes de t −\(\lambda\) \(\rho\),\(\mu\), m es recibido, en el tiempo t, por al menos una fracción \(\rho\) de los usuarios honestos. El protocolo Algorand ′ en realidad instruye a cada uno de un pequeño número de usuarios (es decir, los verificadores de un paso dado de una ronda en Algorand ′, para propagar un mensaje separado de un tamaño (pequeño) prescrito, y necesitamos limitar el tiempo necesario para cumplir estas instrucciones. Lo hacemos enriqueciendo al MP suposición de la siguiente manera. Para todo n, \(\rho\) > 95% y \(\mu\) \(\in\)Z+, existe \(\lambda\)n,\(\rho\),\(\mu\) tal que, para todos los tiempos t y todos los \(\mu\)-byte mensajes m1, . . . , mn, cada uno propagado por un usuario honesto antes de t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . . . , se reciben mn, en el tiempo t, por al menos una fracción \(\rho\) de los usuarios honestos. Nota • El supuesto anterior es deliberadamente simple, pero también más sólido de lo necesario en nuestro artículo.6 • Por simplicidad, asumimos \(\rho\) = 1 y, por lo tanto, dejamos de mencionar \(\rho\). • Asumimos pesimistamente que, siempre que no viole el supuesto MP, el Adversario controla totalmente la entrega de todos los mensajes. En particular, sin que los honestos se den cuenta usuarios, el Adversario puede decidir arbitrariamente qué jugador honesto recibe qué mensaje cuando, y acelerar arbitrariamente la entrega de cualquier mensaje que desee.7

El Protocolo BA BA⋆ en un entorno tradicional

Como ya se destacó, el acuerdo bizantino es un ingrediente clave de Algorand. En efecto, es a través el uso de un protocolo BA tal que Algorand no se vea afectado por las bifurcaciones. Sin embargo, para estar seguros contra nuestra poderoso adversario, Algorand debe confiar en un protocolo BA que satisfaga la nueva capacidad de reemplazo del jugador. restricción. Además, para que Algorand sea eficiente, dicho protocolo BA debe ser muy eficiente. Los protocolos BA se definieron por primera vez para un modelo de comunicación idealizado, sincrónico completo. redes (redes SC). Este modelo permite un diseño y análisis más simples de los protocolos BA. 6Dado el porcentaje honesto h y la probabilidad de falla aceptable F, Algorand calcula un límite superior, N, al número máximo de miembros de verificadores en un paso. Por lo tanto, el supuesto de MP sólo necesita ser válido para n \(\leq\)N. Además, como se indicó, la suposición de MP se mantiene sin importar cuántos otros mensajes puedan propagarse junto con él. los mj. Sin embargo, como veremos, en Algorand los mensajes en se propagan en un tiempo esencialmente no superpuesto. intervalos, durante los cuales se propaga un solo bloque o, como máximo, N verificadores propagan un bloque pequeño (por ejemplo, 200B). mensaje. Por lo tanto, podríamos reformular el supuesto de MP de una manera más débil, pero también más compleja. 7Por ejemplo, puede aprender inmediatamente los mensajes enviados por jugadores honestos. Así, un usuario malintencionado i′, que es Cuando se le pide que propague un mensaje simultáneamente con un usuario honesto i, siempre puede elegir su propio mensaje m′ basándose en el mensaje m realmente propagado por i. Esta capacidad está relacionada con la prisa, en el lenguaje de la computación distribuida. literatura.En consecuencia, en esta sección, presentamos un nuevo protocolo BA, BA⋆, para redes SC e ignoramos la cuestión de la reemplazabilidad de los jugadores por completo. El protocolo BA⋆ es una aportación de valor independiente. De hecho, es el protocolo BA criptográfico más eficiente para redes SC conocido hasta el momento. Para usarlo dentro de nuestro protocolo Algorand, modificamos BA⋆ un poco, para tener en cuenta nuestros diferentes modelo de comunicación y contexto, pero asegúrese, en la sección X, de resaltar cómo se utiliza BA⋆ dentro de nuestro protocolo actual Algorand ′. Comenzamos recordando el modelo en el que opera BA⋆ y la noción de acuerdo bizantino. 3.1 Redes completas sincrónicas y adversarios coincidentes En una red SC, hay un reloj común, que hace tictac en cada integral en tiempos r = 1, 2,. . . En cada momento par, haga clic en r, cada jugador i envía instantánea y simultáneamente un único mensaje señor i,j (posiblemente el mensaje vacío) a cada jugador j, incluido él mismo. cada señor i,j se recibe en ese momento haga clic en r + 1 por parte del jugador j, junto con la identidad del remitente i. Nuevamente, en un protocolo de comunicación, un jugador es honesto si sigue todas sus instrucciones prescritas. instrucciones y maliciosas en caso contrario. Todos los jugadores maliciosos están totalmente controlados y perfectamente coordinado por el Adversario, quien, en particular, recibe inmediatamente todos los mensajes dirigidos a jugadores maliciosos y elige los mensajes que envían. El adversario puede convertir inmediatamente en malicioso a cualquier usuario honesto que desee en cualquier momento. quiere, sujeto únicamente a un posible límite superior t para el número de jugadores maliciosos. Es decir, el Adversario “no puede interferir con los mensajes ya enviados por un usuario honesto i”, que será Entregado como de costumbre. El Adversario también tiene la capacidad adicional de ver instantáneamente, en cada ronda par, el mensajes que envían los jugadores actualmente honestos, y utilizar instantáneamente esta información para elegir los mensajes que los jugadores maliciosos envían al mismo tiempo marcan. Observaciones • Poder Adversario. La configuración anterior es muy conflictiva. De hecho, en el acuerdo bizantino En la literatura, muchos entornos son menos conflictivos. Sin embargo, algunos escenarios más conflictivos han También se ha considerado, donde el Adversario, después de ver los mensajes enviados por un jugador honesto, en un momento dado haga clic en r, tiene la capacidad de borrar todos estos mensajes de la red, inmediatamente corrupto i, elija el mensaje que envía el ahora malicioso i en el momento de hacer clic en r y haga que Entregado como de costumbre. El poder previsto del Adversario coincide con el que tiene en nuestro entorno. • Abstracción Física. El modelo de comunicación previsto abstrae un modelo más físico, en el que cada par de jugadores (i, j) está unido por una línea de comunicación separada y privada li,j. Es decir, nadie más puede inyectar, interferir u obtener información sobre los mensajes enviados. li,j. La única manera que tiene el Adversario de tener acceso a li,j es corromper a i o j. • Privacidad y Autenticación. En las redes SC se garantiza la privacidad y autenticación de los mensajes. por suposición. Por el contrario, en nuestra red de comunicación, donde los mensajes se propagan De igual a igual, la autenticación está garantizada mediante firmas digitales y la privacidad es inexistente. Así, para adoptar el protocolo BA⋆ en nuestro entorno, cada mensaje intercambiado debe estar firmado digitalmente. (identificando además el estado en el que fue enviado). Afortunadamente, los protocolos de BA que utilizamos considere usar en Algorand no requiere privacidad de mensajes.3.2 La noción de un acuerdo bizantino La noción de acuerdo bizantino fue introducida por Pease Shostak y Lamport [31] para el Caso binario, es decir, cuando cada valor inicial consta de un bit. Sin embargo, se amplió rápidamente. a valores iniciales arbitrarios. (Ver las encuestas de Fischer [16] y Chor y Dwork [10].) Por un BA protocolo, nos referimos a uno de valor arbitrario. Definición 3.1. En una red síncrona, sea P un protocolo de n jugadores, cuyo conjunto de jugadores es común conocimiento entre los jugadores, t un entero positivo tal que n \(\geq\)2t + 1. Decimos que P es un valor arbitrario (respectivamente, binario) (n, t) -Protocolo de acuerdo bizantino con solidez \(\sigma\) \(\in\)(0, 1) si, para cada conjunto de valores V que no contiene el símbolo especial \(\bot\) (respectivamente, para V = {0, 1}), en un ejecución en la que como máximo t de los jugadores son maliciosos y en la que cada jugador i comienza con un valor inicial vi \(\in\)V , cada jugador honesto j se detiene con probabilidad 1, generando un valor outi \(\in\)V \(\cup\){\(\bot\)} de modo que se satisfagan, con probabilidad al menos \(\sigma\), las dos condiciones siguientes: 1. Acuerdo: Existe out \(\in\)V \(\cup\){\(\bot\)} tal que outi = out para todos los jugadores honestos i. 2. Consistencia: si, para algún valor v \(\in\)V, vi = v para todos los jugadores honestos, entonces out = v. Nos referimos a out como la salida de P y a cada outi como la salida del jugador i. 3.3 La notación BA # En nuestros protocolos de BA, un jugador debe contar cuántos jugadores le enviaron un mensaje determinado en un paso dado. En consecuencia, para cada valor posible v que podría enviarse,

s

yo(v) (o simplemente #i(v) cuando s está claro) es el número de jugadores j de los cuales he recibido v en el paso s. Recordando que un jugador i recibe exactamente un mensaje de cada jugador j, si el número de jugadores es n, entonces, para todos i y s, P v#s yo(v) = norte. 3.4 El protocolo binario BA BBA⋆ En esta sección presentamos un nuevo protocolo BA binario, BBA⋆, que se basa en la honestidad de más de dos tercios de los jugadores y es muy rápido: no importa lo que puedan hacer los jugadores maliciosos, cada ejecución de su bucle principal hace que los jugadores se pongan de acuerdo con una probabilidad de 1/3. Cada jugador tiene su propia clave pública de un esquema de firma digital que satisface la firma única. propiedad. Dado que este protocolo está diseñado para ejecutarse en una red completa síncrona, no hay Necesito que un jugador firme cada uno de sus mensajes. Las firmas digitales se utilizan para generar un bit aleatorio suficientemente común en el Paso 3. (En Algorand, Las firmas digitales también se utilizan para autenticar todos los demás mensajes). El protocolo requiere una configuración mínima: una cadena aleatoria común r, independiente de los jugadores llaves. (En Algorand, r en realidad se reemplaza por la cantidad Qr.) El protocolo BBA⋆ es un bucle de 3 pasos, donde los jugadores intercambian repetidamente valores booleanos y Diferentes jugadores pueden salir de este bucle en diferentes momentos. Un jugador i sale de este bucle propagándose, en algún paso, ya sea un valor especial 0∗ o un valor especial 1∗, instruyendo así a todos los jugadores a "fingir" que reciben respectivamente 0 y 1 de i en todos los pasos futuros. (Dicho alternativamente: asumirque el último mensaje recibido por un jugador j de otro jugador i fue un poco b. Luego, en cualquier paso en el que no recibe ningún mensaje de i, j actúa como si le hubiera enviado el bit b.) El protocolo utiliza un contador \(\gamma\), que representa cuántas veces se ha ejecutado su bucle de 3 pasos. Al comienzo de BBA⋆, \(\gamma\) = 0. (Se puede pensar en \(\gamma\) como un contador global, pero en realidad aumenta por cada jugador individual cada vez que se ejecuta el bucle.) Hay n \(\geq\)3t + 1, donde t es el número máximo posible de jugadores maliciosos. un binario la cadena x se identifica con el número entero cuya representación binaria (con posibles ceros iniciales) es x; y lsb(x) denota el bit menos significativo de x. Protocolo BBA⋆ (Comunicación) Paso 1. [Paso Coin-Fixed-To-0] Cada jugador i envía bi. 1.1 Si #1 i (0) \(\geq\)2t + 1, luego i establece bi = 0, envía 0∗, genera outi = 0, y SE DETIENE. 1.2 Si #1 i (1) \(\geq\)2t + 1, entonces, entonces i establece bi = 1. 1.3 De lo contrario, establezco bi = 0. (Comunicación) Paso 2. [Paso de moneda fijada a 1] Cada jugador i envía bi. 2.1 Si #2 i (1) \(\geq\)2t + 1, entonces i establece bi = 1, envía 1∗, salidas outi = 1, y SE DETIENE. 2.2 Si #2 i (0) \(\geq\)2t + 1, luego establezco bi = 0. 2.3 De lo contrario, establezco bi = 1. (Comunicación) Paso 3. [Paso lanzado genuinamente con moneda] Cada jugador i envía bi y SIGi(r, \(\gamma\)). 3.1 Si #3 i (0) \(\geq\)2t + 1, entonces i establece bi = 0. 3.2 Si #3 i (1) \(\geq\)2t + 1, entonces i establece bi = 1. 3.3 De lo contrario, dejando Si = {j \(\in\)N que le han enviado a i un mensaje adecuado en este paso 3 }, i establece bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\)))); aumenta \(\gamma\)i en 1; y regresa al Paso 1. Teorema 3.1. Siempre que n \(\geq\)3t + 1, BBA⋆ es un protocolo binario (n, t)-BA con solidez 1. En [26] se proporciona una demostración del teorema 3.1. Su adaptación a nuestro entorno y su reemplazabilidad del jugador. La propiedad es novedosa. Observación histórica Los protocolos BA binarios probabilísticos fueron propuestos por primera vez por Ben-Or en configuraciones asincrónicas [7]. El protocolo BBA⋆ es una adaptación novedosa, a nuestro entorno de clave pública, del Protocolo binario BA de Feldman y Micali [15]. Su protocolo fue el primero en funcionar de la manera esperada. número constante de pasos. Funcionó haciendo que los propios jugadores implementaran una moneda común, una noción propuesta por Rabin, quien la implementó a través de una parte externa de confianza [32].3.5 Consenso Graduado y el Protocolo CG Recordemos, para los valores arbitrarios, una noción de consenso mucho más débil que el acuerdo bizantino. Definición 3.2. Sea P un protocolo en el que el conjunto de todos los jugadores es de conocimiento común y cada uno El jugador i conoce en privado un valor inicial arbitrario v′. yo. Decimos que P es un protocolo de consenso graduado (n, t) si, en cada ejecución con n jugadores, en la mayoría de los cuales son maliciosos, cada jugador honesto deja de generar un par valor-grado (vi, gi), donde gi \(\in\){0, 1, 2}, para satisfacer las tres condiciones siguientes: 1. Para todos los jugadores honestos i y j, |gi −gj| \(\leq\)1. 2. Para todos los jugadores honestos i y j, gi, gj > 0 ⇒vi = vj. 3. Si v′ 1 = \(\cdots\) = v′ n = v para algún valor v, luego vi = v y gi = 2 para todos los jugadores honestos i. Nota histórica La noción de consenso gradual se deriva simplemente de la de consenso gradual. transmitido, presentado por Feldman y Micali en [15], al fortalecer la noción de un cruzado acuerdo, presentado por Dolev [12] y perfeccionado por Turpin y Coan [33].8 En [15], los autores también proporcionaron un protocolo de transmisión graduado de 3 pasos (n, t), Gradecast, para n\(\geq\)3t+1. Posteriormente se encontró un protocolo de transmisión graduado (n, t) más complejo para n > 2t+1. por Katz y Koo [19]. El siguiente protocolo de dos pasos GC consta de los dos últimos pasos de Gradecast, expresados en nuestro notación. Para enfatizar este hecho, y para coincidir con los pasos del protocolo Algorand ′ de la sección 4.1, respectivamente nombre 2 y 3 los pasos de GC. Protocolo GC Paso 2. Cada jugador que envío v′ Yo a todos los jugadores. Paso 3. Cada jugador i envía a todos los jugadores la cadena x si y solo si #2 yo (x) \(\geq\)2t + 1. Determinación de la producción. Cada jugador i genera el par (vi, gi) calculado de la siguiente manera: • Si, para alguna x, #3 i (x) \(\geq\)2t + 1, entonces vi = x y gi = 2. • Si, para alguna x, #3 i (x) \(\geq\)t + 1, entonces vi = x y gi = 1. • En caso contrario, vi = \(\bot\) y gi = 0. Teorema 3.2. Si n \(\geq\)3t + 1, entonces GC es un protocolo de transmisión graduado (n, t). La prueba se deriva inmediatamente de la del protocolo de calificaciones en [15] y, por lo tanto, se omite.9 8En esencia, en un protocolo de transmisión gradual, (a) el aporte de cada jugador es la identidad de un distinguido jugador, el remitente, que tiene un valor arbitrario v como entrada privada adicional, y (b) las salidas deben satisfacer el mismas propiedades 1 y 2 del consenso graduado, más la siguiente propiedad 3′: si el remitente es honesto, entonces vi = v y gi = 2 para todo jugador honesto i. 9De hecho, en su protocolo, en el paso 1, el remitente envía su propio valor privado v a todos los jugadores, y cada jugador i permite v′ Estoy compuesto por el valor que realmente recibió del remitente en el paso 1.3.6 El Protocolo BA⋆ Ahora describimos el protocolo BA de valor arbitrario BA⋆ a través del protocolo BA binario BBA⋆ y el protocolo de consenso graduado GC. A continuación, el valor inicial de cada jugador i es v′ yo. Protocolo BA⋆ Pasos 1 y 2. Cada jugador i ejecuta GC, en la entrada v′ i, para calcular un par (vi, gi). Paso 3,. . . Cada jugador i ejecuta BBA⋆—con entrada inicial 0, si gi = 2, y 1 en caso contrario—por lo que para calcular el bit outi. Determinación de la producción. Cada jugador i genera vi, si outi = 0, y \(\bot\) en caso contrario. Teorema 3.3. Siempre que n \(\geq\)3t + 1, BA⋆es un protocolo (n, t)-BA con solidez 1. Prueba. Primero demostramos la coherencia y luego el acuerdo. Prueba de coherencia. Supongamos que, para algún valor v \(\in\)V , v′ i = v. Entonces, por la propiedad 3 de Consenso calificado, después de la ejecución de GC, todos los jugadores honestos salen (v, 2). En consecuencia, 0 es la parte inicial de todos los jugadores honestos al final de la ejecución de BBA⋆. Así, por el Acuerdo propiedad del acuerdo bizantino binario, al final de la ejecución de BA⋆, outi = 0 para todos los honestos jugadores. Esto implica que la producción de cada jugador honesto i en BA⋆es vi = v. ✷ Prueba de Acuerdo. Dado que BBA⋆ es un protocolo BA binario, ya sea (A) outi = 1 para todo jugador honesto i, o (B) outi = 0 para todo jugador honesto i. En el caso A, todos los jugadores honestos generan \(\bot\) en BA⋆ y, por lo tanto, se cumple el acuerdo. Consideremos ahora el caso B. En En este caso, en la ejecución de BBA⋆, el bit inicial de al menos un jugador honesto i es 0. (De hecho, si El bit inicial de todos los jugadores honestos fuera 1, entonces, según la propiedad de consistencia de BBA⋆, tendríamos outj = 1 para todos los j honestos). En consecuencia, después de la ejecución de GC, i genera el par (v, 2) para algunos valor v. Por tanto, según la propiedad 1 del consenso graduado, gj > 0 para todos los jugadores honestos j. En consecuencia, por propiedad 2 del consenso graduado, vj = v para todos los jugadores honestos j. Esto implica que, al final de BA⋆, todo jugador honesto j produce v. Por lo tanto, el acuerdo también se cumple en el caso B. ✷ Dado que se mantienen tanto la coherencia como el acuerdo, BA⋆ es un protocolo BA de valor arbitrario. Nota histórica Turpin y Coan fueron los primeros en demostrar que, para n \(\geq\)3t+1, cualquier binario (n, t)-BA El protocolo se puede convertir en un protocolo de valor arbitrario (n, t) -BA. La reducción del valor arbitrario. Del acuerdo bizantino al acuerdo bizantino binario a través del consenso graduado es más modular y más limpio y simplifica el análisis de nuestro protocolo Algorand Algorand ′. Generalizando BA⋆para uso en Algorand Algorand funciona incluso cuando toda la comunicación se realiza a través de chismeando. Sin embargo, aunque se presenta en una red de comunicación tradicional y familiar, para Para permitir una mejor comparación con el estado de la técnica y una comprensión más fácil, el protocolo BA⋆funciona también en redes de chismes. De hecho, en nuestras realizaciones detalladas de Algorand, lo presentaremos directamente para las redes de chismes. También señalaremos que satisface la reemplazabilidad del jugador. propiedad que es crucial para que Algorand esté seguro en el modelo muy adversario previsto.

Cualquier protocolo reemplazable por un reproductor BA que funcione en una red de comunicación chismosa puede ser empleado de forma segura dentro del sistema inventivo Algorand. En particular, Micali y Vaikunthanatan Hemos ampliado BA⋆ para que funcione de manera muy eficiente también con una mayoría simple de jugadores honestos. eso El protocolo también podría usarse en Algorand.

Dos realizaciones de Algorand

Como se analizó, en un nivel muy alto, una ronda de Algorand idealmente se desarrolla de la siguiente manera. Primero, al azar El usuario seleccionado, el líder, propone y hace circular un nuevo bloque. (Este proceso incluye inicialmente seleccionar algunos líderes potenciales y luego garantizar que, al menos una buena fracción del tiempo, emerge un solo líder común.) En segundo lugar, se selecciona un comité de usuarios seleccionado al azar, y llega a un acuerdo bizantino sobre el bloque propuesto por el líder. (Este proceso incluye que cada paso del protocolo BA es dirigido por un comité seleccionado por separado). El bloque acordado luego es firmado digitalmente por un umbral determinado (TH) de miembros del comité. Estas firmas digitales Se circulan para que todos tengan la seguridad de cuál es el nuevo bloque. (Esto incluye hacer circular el credencial de los firmantes y autenticar solo el hash del nuevo bloque, asegurando que todos Se garantiza que aprenderá el bloque, una vez que se aclare su hash). En las dos secciones siguientes, presentamos dos realizaciones de Algorand, Algorand ′ 1 y Algorand ′ 2, que funcionan bajo el supuesto de que la mayoría de los usuarios son honestos. En la Sección 8 mostramos cómo adoptar estos encarnaciones para trabajar bajo una suposición honesta de mayoría del dinero. Algorand ′ 1 sólo prevé que > 2/3 de los miembros del comité sean honestos. Además, en Algorand ′ 1, el número de pasos para llegar a un acuerdo bizantino tiene un límite suficientemente alto número, de modo que se garantiza que se llegará a un acuerdo con una probabilidad abrumadora en un plazo número fijo de pasos (pero potencialmente requiere más tiempo que los pasos de Algorand ′ 2). en el caso remoto en el que aún no se llega a un acuerdo en el último paso, el comité acuerda la bloque vacío, que siempre es válido. Algorand ′ 2 prevé que el número de miembros honestos de un comité sea siempre mayor que el o igual a un umbral fijo tH (que garantiza que, con una probabilidad abrumadora, al menos 2/3 de los miembros del comité son honestos). Además, Algorand ′ 2 permite que el acuerdo bizantino alcanzarse en un número arbitrario de pasos (pero potencialmente en un tiempo más corto que Algorand ′ 1). Es fácil derivar muchas variantes de estas realizaciones básicas. En particular, es fácil, dado Algorand ′ 2, para modificar Algorand ′ 1 para permitir llegar a un acuerdo bizantino de forma arbitraria número de pasos. Ambas realizaciones comparten los siguientes núcleos, notaciones, nociones y parámetros comunes. 4.1 Un núcleo común Objetivos Idealmente, para cada ronda r, Algorand satisfaría las siguientes propiedades: 1. Perfecta corrección. Todos los usuarios honestos coinciden en el mismo bloque Br. 2. Integridad 1. Con probabilidad 1, el conjunto de pagos de Br, PAY r, es máximo.10 10Debido a que se define que los pagos contienen pagos válidos y que los usuarios honestos solo realizan pagos válidos, un máximo PAY r contiene los pagos "actualmente pendientes" de todos los usuarios honestos.Por supuesto, garantizar por sí solo la corrección perfecta es trivial: cada uno elige siempre el payset PAY r para estar vacío. Pero en este caso, el sistema tendría una completitud 0. Desafortunadamente, Garantizar tanto la exactitud como la integridad 1 no es fácil en presencia de información maliciosa. usuarios. Algorand adopta así un objetivo más realista. Informalmente, sea h el porcentaje de usuarios que son honestos, h > 2/3, el objetivo de Algorand es Garantizando, con abrumadora probabilidad, perfecta corrección e integridad cerca de h. Privilegiar la corrección sobre la integridad parece una opción razonable: los pagos no procesados en Una ronda se puede procesar en la siguiente, pero se deben evitar los tenedores, si es posible. Acuerdo bizantino liderado La corrección perfecta se puede garantizar de la siguiente manera. al principio de la ronda r, cada usuario i construye su propio bloque candidato Br i, y luego todos los usuarios llegan a Byzantine acuerdo sobre un bloque de candidatos. Según nuestra introducción, el protocolo BA empleado requiere una mayoría honesta de 2/3 y es jugador reemplazable. Cada uno de sus pasos puede ser ejecutado por un pequeño y conjunto de verificadores seleccionados al azar, que no comparten ninguna variable interna. Desafortunadamente, este enfoque no ofrece garantías de integridad. Esto es así porque el candidato Lo más probable es que los bloques de usuarios honestos sean totalmente diferentes entre sí. Así, en definitiva El bloque acordado siempre puede ser uno con un pago no máximo. De hecho, siempre puede ser el bloque vacío, B\(\varepsilon\), es decir, el bloque cuyo payset está vacío. Será el predeterminado, vacío. Algorand ′ evita este problema de integridad de la siguiente manera. Primero, se selecciona un líder para la ronda r, \(\ell\)r. Luego, \(\ell\)r propaga su propio bloque candidato, Br \(\ell\)r. Finalmente, los usuarios llegan a un acuerdo sobre el bloque en realidad reciben de \(\ell\)r. Porque, siempre que \(\ell\)r sea honesto, Perfecta Corrección e Integridad 1 ambos se mantienen, Algorand ′ asegura que \(\ell\)r es honesto con una probabilidad cercana a h. (Cuando el líder es malicioso, no nos importa si el bloque acordado tiene un conjunto de pagos vacío. Después de todo, un El líder malicioso \(\ell\)r siempre puede elegir maliciosamente a Br. \(\ell\)r para ser el bloque vacío, y luego honestamente propagarlo, obligando así a los usuarios honestos a aceptar el bloque vacío). Selección de líder En Algorand, el bloque r tiene la forma Br = (r, PAY r, Qr, H(Br−1). Como ya se mencionó en la introducción, la cantidad Qr−1 se construye cuidadosamente para que sea esencialmente no manipulable por nuestro muy poderoso Adversario. (Más adelante en esta sección, veremos proporcionar alguna intuición sobre por qué este es el caso.) Al comienzo de una ronda r, todos los usuarios saben blockchain hasta ahora, B0, . . . , Br−1, de donde deducen el conjunto de usuarios de cada ronda anterior: que es, PK1, . . . , PKr-1. Un líder potencial de la ronda r es un usuario i tal que .H SIGi r, 1, Qr−1 \(\leq\)p. Expliquemos. Tenga en cuenta que, dado que la cantidad Qr−1 es parte del bloque Br−1, y el subyacente El esquema de firma satisface la propiedad de unicidad, SIGi. r, 1, Qr−1 es una cadena binaria únicamente asociado a i y r. Por lo tanto, dado que H es un oracle aleatorio, H SIGi r, 1, Qr−1 es un aleatorio de 256 bits cadena larga asociada únicamente a i y r. El símbolo "." frente a h SIGi r, 1, Qr−1 es el punto decimal (en nuestro caso, binario), de modo que ri \(\triangleq\).H SIGi r, 1, Qr−1 es la expansión binaria de a Número aleatorio de 256 bits entre 0 y 1 asociado únicamente a i y r. Así, la probabilidad de que ri es menor o igual que p es esencialmente p. (Nuestro mecanismo de selección de líderes potenciales ha sido inspirado en el esquema de micropagos de Micali y Rivest [28].) La probabilidad p se elige de modo que, con una probabilidad abrumadora (es decir, 1 −F), al menos una El verificador potencial es honesto. (De hecho, se elige p como la probabilidad más pequeña).Tenga en cuenta que, dado que i es el único capaz de calcular sus propias firmas, sólo él puede determinar si es un verificador potencial de la ronda 1. Sin embargo, al revelar su propia credencial, \(\sigma\)r yo \(\triangleq\)SIGi r, 1, Qr−1 , puedo demostrarle a cualquiera que soy un verificador potencial de la ronda r. El líder \(\ell\)r se define como el líder potencial cuya credencial hashed es más pequeña que la hashed credencial de todos los demás líderes potenciales j: es decir, H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s j). Tenga en cuenta que, dado que un \(\ell\)r malicioso no puede revelar su credencial, el líder correcto de la ronda r puede nunca se sabrá, y que, salvo vínculos improbables, \(\ell\)r es de hecho el único líder de la ronda r. Por último, mencionemos un último pero importante detalle: un usuario i puede ser un líder potencial (y por tanto el líder) de una ronda r sólo si perteneció al sistema durante al menos k rondas. Esto garantiza la no manipulabilidad de Qr y de todas las cantidades Q futuras. De hecho, uno de los líderes potenciales en realidad determinará Qr. Selección del verificador Cada paso s > 1 de la ronda r es ejecutado por un pequeño conjunto de verificadores, SV r,s. Nuevamente, cada verificador i \(\in\)SV r,s se selecciona aleatoriamente entre los usuarios que ya están en el sistema k rondas antes de r, y nuevamente a través de la cantidad especial Qr−1. Específicamente, i \(\in\)PKr−k es un verificador en SV r,s, si .H SIGi r, s, Qr−1 \(\leq\)p′. Una vez más, sólo yo sé si pertenece al SV r,s, pero, si es así, podría demostrarlo mediante exhibiendo su credencial \(\sigma\)r,s yo \(\triangleq\)H(SIGi r, s, Qr−1 ). Un verificador i \(\in\)SV r,s envía un mensaje, mr,s yo, en paso s de la ronda r, y este mensaje incluye su credencial \(\sigma\)r,s i , para permitir a los verificadores del Nido paso para reconocer que el señor yo es un mensaje de paso legítimo. La probabilidad p′ se elige de manera que se asegure que, en SV r,s, siendo #good el número de usuarios honestos y #bad el número de usuarios maliciosos, con una probabilidad abrumadora los siguientes Se cumplen dos condiciones. Para la realización Algorand ′ 1: (1) #bueno > 2 \(\cdot\) #malo y (2) #bueno + 4 \(\cdot\) #malo < 2n, donde n es la cardinalidad esperada de SV r,s. Para la realización Algorand ′ 2: (1) #bueno > tH y (2) #bueno + 2#malo < 2tH, donde tH es un umbral especificado. Estas condiciones implican que, con una probabilidad suficientemente alta, (a) en el último paso del BA protocolo, habrá al menos un número determinado de jugadores honestos para firmar digitalmente el nuevo bloque Br, (b) sólo un bloque por ronda puede tener el número necesario de firmas, y (c) el BA utilizado El protocolo tiene (en cada paso) la mayoría honesta requerida de 2/3. Aclarando la generación de bloques Si el líder redondo-r \(\ell\)r es honesto, entonces el bloque correspondiente es de la forma hermano = r, PAGAR r, SIG\(\ell\)r Qr−1 , h Br-1 , donde el salario PAY r es máximo. (Recuerde que todos los pagos son, por definición, colectivamente válidos). De lo contrario (es decir, si \(\ell\)r es malicioso), Br tiene una de las dos formas posibles siguientes: hermano = r, PAGAR r, SIGi qr-1 , h Br-1 y Br = Br \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Br-1 .En la primera forma, el PAGO r es un conjunto de pagos (no necesariamente máximo) y puede ser el PAGO r = \(\emptyset\); y yo soy un líder potencial de la ronda r. (Sin embargo, es posible que no sea el líder \(\ell\)r. Esto de hecho puede suceder si \(\ell\)r mantiene en secreto su credencial y no se revela.) La segunda forma surge cuando, en la ejecución de la ronda r del protocolo BA, todos los jugadores honestos genera el valor predeterminado, que es el bloque vacío Br \(\varepsilon\) en nuestra aplicación. (Por definición, la posible Las salidas de un protocolo BA incluyen un valor predeterminado, indicado genéricamente por \(\bot\). Ver sección 3.2.) Tenga en cuenta que, aunque los paysets están vacíos en ambos casos, Br = r, \(\emptyset\), SIGi qr-1 , h Br-1 y hermano \(\varepsilon\) son bloques sintácticamente diferentes y surgen en dos situaciones diferentes: respectivamente, “todos transcurrió sin problemas en la ejecución del protocolo BA”, y “algo salió mal en el Protocolo BA y se emitió el valor predeterminado”. Describamos ahora intuitivamente cómo se produce la generación del bloque Br en la ronda r de Algorand ′. En el primer paso, cada jugador elegible, es decir, cada jugador i \(\in\)PKr−k, verifica si es un potencial líder. Si este es el caso, entonces se me pregunta, utilizando todos los pagos que ha visto hasta ahora, y el actual blockchain, B0, . . . , Br−1, para preparar en secreto un conjunto de pagos máximo, PAY r yo y en secreto reúne su bloque candidato, Br = r, PAGAR r yo, SIGi qr-1 , h Br-1 . Es decir, no sólo él incluir en br i , como segundo componente, el conjunto de pagos recién preparado, pero también, como tercer componente, su propia firma de Qr−1, el tercer componente del último bloque, Br−1. Finalmente, propaga su mensaje redondo-r-paso-1, señor,1 i , que incluye (a) su bloque candidato Br i , (b) su firma apropiada de su bloque de candidatos (es decir, su firma del hash del Hno. i , y (c) su propia credencial \(\sigma\)r,1 yo, probando que de hecho es un verificador potencial de la ronda r. (Tenga en cuenta que, hasta que un i honesto produzca su mensaje mr,1 Yo, el Adversario no tiene idea de que soy un verificador potencial. Si quisiera corromper a líderes potenciales honestos, el Adversario también podría jugadores honestos al azar corruptos. Sin embargo, una vez que ve al señor,1 i, ya que contiene la credencial de i, el El adversario sabe y podría corromperme, pero no puede impedir que mr,1 i , que se propaga viralmente, de llegar a todos los usuarios del sistema). En el segundo paso, cada verificador seleccionado j \(\in\)SV r,2 intenta identificar al líder de la ronda. Específicamente, j toma las credenciales del paso 1, \(\sigma\)r,1 i1 , . . . , \(\sigma\)r,1 en , contenido en el mensaje adecuado del paso 1 mr,1 yo ha recibido; hashestablece todos, es decir, calcula H  \(\sigma\)r,1 i1  , . . . , h  \(\sigma\)r,1 en  ; encuentra la credencial, \(\sigma\)r,1 \(\ell\)j , cuyo hash es lexicográficamente mínimo; y considera \(\ell\)r j para ser el líder de la ronda r. Recordemos que cada credencial considerada es una firma digital de Qr−1, que SIGi r, 1, Qr−1 es determinado únicamente por i y Qr−1, que H es aleatorio oracle y, por tanto, que cada H(SIGi r, 1, Qr−1 es una cadena aleatoria de 256 bits de longitud única para cada líder potencial i de la ronda r. De esto podemos concluir que, si la cadena de 256 bits Qr−1 fuera aleatoria e independientemente seleccionado, entonces serían las credenciales hashed de todos los líderes potenciales de la ronda r. De hecho, todos Los líderes potenciales están bien definidos, al igual que sus credenciales (ya sean realmente calculadas o calculadas). no). Además, el conjunto de líderes potenciales de la ronda r es un subconjunto aleatorio de los usuarios de la ronda r −k, y un líder potencial honesto siempre construye y propaga adecuadamente su mensaje, señor yo, que contiene la credencial de i. Por lo tanto, dado que el porcentaje de usuarios honestos es h, no importa cuál sea el líderes potenciales maliciosos podrían hacer (por ejemplo, revelar u ocultar sus propias credenciales), el mínimo La credencial de líder potencial hashed pertenece a un usuario honesto, quien necesariamente es identificado por todos. ser el líder \(\ell\)r de la ronda r. En consecuencia, si la cadena de 256 bits Qr-1 fuera aleatoria y seleccionado independientemente, con probabilidad exactamente h (a) el líder \(\ell\)r es honesto y (b) \(\ell\)j = \(\ell\)r para todos verificadores honestos del paso 2 j. En realidad, las credenciales hashed se seleccionan, sí, al azar, pero dependen de Qr-1, que esno seleccionados de forma aleatoria e independiente. Sin embargo, demostraremos en nuestro análisis que Qr−1 es suficientemente no manipulable para garantizar que el líder de una ronda sea honesto con la probabilidad h′ suficientemente cerca de h: es decir, h′ > h2(1 + h −h2). Por ejemplo, si h = 80%, entonces h′ > 0,7424. Habiendo identificado al líder de la ronda (lo que hacen correctamente cuando el líder \(\ell\)r es honesto), La tarea de los verificadores del paso 2 es comenzar a ejecutar el BA utilizando como valores iniciales lo que ellos creen. ser el bloque del líder. En realidad, para minimizar la cantidad de comunicación requerida, un verificador j \(\in\)SV r,2 no utiliza como valor de entrada v′ j al protocolo bizantino, el bloque Bj que en realidad ha recibido de \(\ell\)j (el usuario j cree que es el líder), pero el líder, pero el hash de ese bloque, es decir, v′ j = H(Bi). Por lo tanto, al finalizar el protocolo BA, los verificadores del último paso no calcula el bloque redondo-r deseado Br, sino que calcula (autentica y propagar) H(Br). En consecuencia, dado que H(Br) está firmado digitalmente por un número suficiente de verificadores del último paso del protocolo BA, los usuarios del sistema se darán cuenta de que H(Br) es el hash del nuevo bloque. Sin embargo, también deben recuperar (o esperar, ya que la ejecución es bastante asincrónica) el bloquear Br en sí, que el protocolo garantiza que esté realmente disponible, sin importar cuál sea el adversario podría servir. Asincronía y sincronización Algorand ′ 1 y Algorand ′ 2 tienen un grado significativo de asincronía. Esto es así porque el Adversario tiene una gran libertad para programar la entrega de los mensajes que se envían. propagado. Además, ya sea que el número total de pasos en una ronda esté limitado o no, existe la varianza contribuye por el número de pasos realmente tomados. Tan pronto como conozca los certificados de B0,. . . , Br−1, un usuario i calcula Qr−1 y comienza a trabajar en la ronda r, comprobando si es un líder potencial o un verificador en algunos pasos de la ronda r. Suponiendo que debo actuar en el paso s, a la luz de la asincronía discutida, me baso en varios estrategias para asegurar que tenga suficiente información antes de actuar. Por ejemplo, podría esperar a recibir al menos un número determinado de mensajes de los verificadores de el paso anterior, o esperar un tiempo suficiente para asegurarse de que recibe los mensajes de suficiente muchos verificadores del paso anterior. La semilla Qr y el parámetro retrospectivo k Recuerde que, idealmente, las cantidades Qr deberían aleatorios e independientes, aunque bastará con que sean lo suficientemente no manipulables por el Adversario. A primera vista, podríamos elegir Qr−1 para que coincida con H PAGAR r-1 , y así evitar especifique Qr−1 explícitamente en Br−1. Un análisis elemental revela, sin embargo, que los usuarios malintencionados pueden aprovechar este mecanismo de selección.11 Algunos esfuerzos adicionales muestran que miles de otros 11Estamos al comienzo de la ronda r −1. Por lo tanto, Qr−2 = PAY r−2 se conoce públicamente y el Adversario se conoce en privado. sabe quiénes son los líderes potenciales que controla. Supongamos que el Adversario controla el 10% de los usuarios, y que, con una probabilidad muy alta, un usuario malintencionado w es el líder potencial de la ronda r −1. Es decir, suponer que h SIGw r-2, 1, Qr-2 es tan pequeño que es muy improbable que un líder potencial honesto sea realmente el líder de la ronda r −1. (Recuerde que, dado que elegimos líderes potenciales mediante un mecanismo secreto de clasificación criptográfica, El Adversario no sabe quiénes son los líderes potenciales honestos.) El Adversario, por lo tanto, está en la envidiable posición de elegir el pago PAY ′ que desea y hacer que se convierta en el pago oficial de la ronda r −1. Sin embargo, él puede hacer más. También puede asegurar que, con alta probabilidad, () uno de sus usuarios maliciosos será el líder también de la ronda r, para que pueda seleccionar libremente cuál será el PAGO r. (Y así sucesivamente. Al menos durante mucho tiempo, es decir, siempre y cuando estos eventos de alta probabilidad realmente ocurran.) Para garantizar (), el Adversario actúa de la siguiente manera. Deja PAGAR ′ sea el pago que prefiera el adversario para la ronda r −1. Luego, calcula H(PAY ′) y comprueba si, para algunos ya el jugador malicioso z, SIGz(r, 1, H(PAY ′)) es particularmente pequeño, es decir, lo suficientemente pequeño como para que con niveles muy altos probabilidad z será el líder de la ronda r. Si este es el caso, entonces le indica a w que elija su bloque candidato para seralternativas, basadas en cantidades de bloques tradicionales, son fácilmente explotables por el adversario para garantizar que los líderes maliciosos son muy frecuentes. En cambio, definimos específica e inductivamente nuestra marca. nueva cantidad Qr para poder demostrar que no es manipulable por el Adversario. Es decir, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), si Br no es el bloque vacío, y Qr \(\triangleq\)H(Qr−1, r) en caso contrario. La intuición de por qué funciona esta construcción de Qr es la siguiente. Supongamos por un momento que Qr−1 se selecciona verdaderamente de forma aleatoria e independiente. Entonces, ¿lo será también Qr? Cuando \(\ell\)r es honesto el La respuesta es (en términos generales) sí. Esto es así porque H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256 es una función aleatoria. Sin embargo, cuando \(\ell\)r es malicioso, Qr ya no se define unívocamente a partir de Qr−1 y \(\ell\)r. Hay al menos dos valores separados para Qr. Uno sigue siendo Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), y el otro es H(Qr−1, r). Primero argumentemos que, si bien la segunda opción es algo arbitraria, una segunda elección es absolutamente obligatoria. La razón de esto es que un \(\ell\)r malicioso siempre puede causar bloques candidatos totalmente diferentes para ser recibidos por los verificadores honestos del segundo paso.12 Una vez Si este es el caso, es fácil garantizar que el bloque finalmente acordado a través del protocolo BA de La ronda r será la predeterminada y, por lo tanto, no contendrá la firma digital Qr-1 de nadie. pero el sistema debe continuar y para ello necesita un líder para la ronda r. Si este líder es automáticamente y seleccionado abiertamente, entonces el Adversario lo corromperá trivialmente. Si es seleccionado por el anterior Qr−1 mediante el mismo proceso, \(\ell\)r volverá a ser el líder en la ronda r+1. Proponemos específicamente utilizar el mismo mecanismo secreto de clasificación criptográfica, pero aplicado a una nueva cantidad Q: a saber, H(Qr−1,r). Al tener esta cantidad como salida de H se garantiza que la salida sea aleatoria, e incluyendo r como segunda entrada de H, mientras que todos los demás usos de H tienen una o más de 3 entradas, “garantiza” que dicho Qr se selecciona de forma independiente. Nuevamente, nuestra elección específica de la alternativa Qr No importa, lo que importa es que \(\ell\)r tiene dos opciones para Qr y, por lo tanto, puede duplicar sus posibilidades. tener otro usuario malicioso como próximo líder. Las opciones para Qr pueden ser incluso más numerosas para el Adversario que controla un \(\ell\)r malicioso. Por ejemplo, sean x, y y z tres líderes potenciales maliciosos de la ronda r tales que h \(\sigma\)r,1 x
<H \(\sigma\)r,1 y
1. Observe que n1 << n, ya que necesitamos al menos un miembro honesto y honesto en SV r,1, pero al menos una mayoría de miembros honestos en cada SV r,s para s > 1. • h \(\in\)(0, 1): una constante mayor que 2/3. h es el índice de honestidad en el sistema. Es decir, el La fracción de usuarios honestos o dinero honesto, dependiendo del supuesto utilizado, en cada PKr es al menos h. • H: una función criptográfica hash, modelada como una oracle aleatoria. • \(\bot\): Una cadena especial de la misma longitud que la salida de H. • F \(\in\)(0, 1): el parámetro que especifica la probabilidad de error permitida. Una probabilidad \(\leq\)F es se considera “insignificante”, y una probabilidad \(\geq\)1 −F se considera “abrumadora”. • ph \(\in\)(0, 1): la probabilidad de que el líder de una ronda r, \(\ell\)r, sea honesto. Idealmente ph = h. con En caso de existencia del Adversario, el valor de ph será determinado en el análisis. • k \(\in\)Z+: el parámetro retrospectivo. Es decir, la ronda r −k es donde están los verificadores para la ronda r. elegido entre —es decir, SV r \(\subseteq\)PKr−k.15 • p1 \(\in\)(0, 1): para el primer paso de la ronda r, se elige un usuario en la ronda r −k para estar en SV r,1 con probabilidad p1 \(\triangleq\) n1 |P Kr−k|. • p \(\in\)(0, 1): para cada paso s > 1 de la ronda r, se elige un usuario en la ronda r −k para estar en SV r,s con probabilidad p \(\triangleq\) norte |P Kr−k|. • CERT r: el certificado del Br. Es un conjunto de firmas tH de H(Br) de verificadores adecuados en redondo r. • Br \(\triangleq\)(Br, CERT r) es un bloque probado. Un usuario i conoce Br si posee (y verifica con éxito) ambas partes del bloque probado. Tenga en cuenta que el CERT visto por diferentes usuarios puede ser diferente. • τ r i: la hora (local) en la que un usuario conoce a Br. En el protocolo Algorand cada usuario tiene su propio reloj. No es necesario sincronizar los relojes de diferentes usuarios, pero deben tener la misma velocidad. Sólo a efectos del análisis, consideramos un reloj de referencia y medimos el tiempo de los jugadores. tiempos relacionados con respecto al mismo. • ar,s yo y \(\beta\)r,s i: respectivamente, la hora (local) en la que un usuario i inicia y finaliza su ejecución de los Pasos de redondo r. • Λ y \(\lambda\): esencialmente, los límites superiores de, respectivamente, el tiempo necesario para ejecutar el Paso 1 y el tiempo necesario para cualquier otro paso del protocolo Algorand. El parámetro Λ limita el tiempo para propagar un único bloque de 1 MB. (En nuestra notación, Λ = \(\lambda\) \(\rho\),1MB. Recordando nuestra notación, que establecemos \(\rho\) = 1 por simplicidad, y que los bloques son elegido para que tenga como máximo 1 MB de longitud, tenemos Λ = \(\lambda\)1,1,1 MB.) 15Estrictamente hablando, “r −k” debería ser “max{0, r −k}”.El parámetro \(\lambda\) limita el tiempo para propagar un mensaje pequeño por verificador en un Paso s > 1. (Usando, como en Bitcoin, firmas de curvas elípticas con claves de 32B, un mensaje de verificación tiene una longitud de 200B. Así, en nuestra notación, \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Suponemos que Λ = O(\(\lambda\)). Nociones • Selección de verificador. Para cada ronda r y paso s > 1, SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. cada uno El usuario i \(\in\)PKr−k calcula de forma privada su firma utilizando su clave a largo plazo y decide si i \(\in\)SV r,s o no. Si i \(\in\)SV r,s, entonces SIGi(r, s, Qr−1) es la credencial (r, s) de i, denotada de forma compacta por \(\sigma\)r,s yo. Para el primer paso de la ronda r, SV r,1 y \(\sigma\)r,1 yo se definen de manera similar, con p reemplazado por p1. el Los verificadores en SV r,1 son líderes potenciales. • Selección de líderes. El usuario i \(\in\)SV r,1 es el líder de la ronda r, denotada por \(\ell\)r, si H(\(\sigma\)r,1 i ) \(\leq\)H(\(\sigma\)r,1 j ) para todo potencial líderes j \(\in\)SV r,1. Siempre que se comparan los hashes de las credenciales de dos jugadores, en el improbable En caso de empates, el protocolo siempre rompe los lazos lexicográficamente de acuerdo con el (público a largo plazo). claves de los) líderes potenciales. Por definición, el valor hash de la credencial del jugador \(\ell\)r también es el más pequeño entre todos los usuarios en PKr−k. Tenga en cuenta que un líder potencial no puede decidir en privado si es el líder o no, sin ver las credenciales de los otros líderes potenciales. Dado que los valores hash son uniformes al azar, cuando SV r,1 no está vacío, \(\ell\)r siempre existe y es honesto con probabilidad al menos h. El parámetro n1 es lo suficientemente grande como para garantizar que cada SV r,1 no está vacío con una probabilidad abrumadora. • Estructura de bloques. Un bloque no vacío tiene la forma Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)) y un bloque vacío es de la forma Br ǫ = (r, \(\emptyset\), Qr−1, H(Br−1)). Tenga en cuenta que un bloque no vacío aún puede contener un conjunto de pagos vacío PAY r, si no se produce ningún pago en esta ronda o si el líder es malicioso. Sin embargo, un bloque no vacío implica que la identidad de \(\ell\)r, su credencial \(\sigma\)r,1 \(\ell\)r y SIG\(\ell\)r(Qr−1) han sido revelados oportunamente. El protocolo garantiza que, si el líder es honesto, entonces el bloque no estará vacío con una probabilidad abrumadora. • Semilla Qr. Si Br no está vacío, entonces Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), en caso contrario Qr \(\triangleq\)H(Qr−1, r). Parámetros • Relaciones entre varios parámetros. — Los verificadores y líderes potenciales de la ronda r se seleccionan entre los usuarios de PKr−k, donde k se elige de modo que el adversario no pueda predecir Qr−1 en la ronda r −k −1 con probabilidad mejor que F: de lo contrario, podrá introducir usuarios maliciosos para la ronda r −k, todos los cuales serán líderes/verificadores potenciales en la ronda r, logrando

tener un líder malicioso o una mayoría maliciosa en SV r,s para algunos pasos deseados por él. — Para el Paso 1 de cada ronda r, se elige n1 de manera que con una probabilidad abrumadora, SV r,1 ̸= \(\emptyset\). • Ejemplos de opciones de parámetros importantes. — Las salidas de H tienen una longitud de 256 bits. — h = 80%, n1 = 35. — Λ = 1 minuto y \(\lambda\) = 10 segundos. • Inicialización del protocolo. El protocolo comienza en el momento 0 con r = 0. Como no existe "B-1" o "CERT -1", sintácticamente B-1 es un parámetro público con su tercer componente especificando Q-1, y todos los usuarios conozca B−1 en el tiempo 0.

Algorand ′

1 En esta sección, construimos una versión de Algorand ′ que funciona bajo el siguiente supuesto. Supuesto honesto de la mayoría de los usuarios: Más de 2/3 de los usuarios en cada PKr son honestos. En la Sección 8, mostramos cómo reemplazar el supuesto anterior con la deseada Mayoría Honesta de Suposición de dinero. 5.1 Notaciones y parámetros adicionales Notaciones • m \(\in\)Z+: el número máximo de pasos en el protocolo BA binario, múltiplo de 3. • Lr \(\leq\)m/3: una variable aleatoria que representa el número de ensayos de Bernoulli necesarios para ver un 1, cuando cada ensayo es 1 con probabilidad ph 2 y hay como máximo m/3 ensayos. Si todas las pruebas fallan entonces Lr\(\triangleq\)m/3. Lr se utilizará para limitar el tiempo necesario para generar el bloque Br. • tH = 2n 3 + 1: el número de firmas necesarias en las condiciones finales del protocolo. • CERT r: el certificado del Br. Es un conjunto de firmas tH de H(Br) de verificadores adecuados en redondo r. Parámetros • Relaciones entre varios parámetros. — Para cada paso s > 1 de la ronda r, se elige n de modo que, con una probabilidad abrumadora, |VHS r,s| > 2|MSV r,s| y |VHS r,s| + 4|MSV r,s| < 2n. Cuanto más cercano a 1 esté el valor de h, menor debe ser n. En particular, utilizamos (variantes de) Chernofflimits para garantizar que las condiciones deseadas se mantengan con una probabilidad abrumadora. — m se elige de modo que Lr < m/3 con una probabilidad abrumadora. • Ejemplos de opciones de parámetros importantes. —F = 10−12. — n \(\approx\)1500, k = 40 y m = 180.5.2 Implementación de claves efímeras en Algorand ′ 1 Como ya se mencionó, deseamos que un verificador i \(\in\)SV r,s firme digitalmente su mensaje mr,s yo de paso s en la ronda r, relativa a una clave pública efímera pkr,s i, usando una clave secreta efímera skr,s yo eso él rápidamente destruye después de usarlo. Por lo tanto, necesitamos un método eficiente para garantizar que cada usuario pueda verificar que pkr,s yo es de hecho la clave a utilizar para verificar la firma del señor i yo. Lo hacemos mediante un (al mejor según nuestro conocimiento) nuevo uso de esquemas de firma basados en la identidad. En un nivel alto, en tal esquema, una autoridad central A genera una clave maestra pública, PMK, y una clave maestra secreta correspondiente, SMK. Dada la identidad, U, de un jugador U, A calcula, a través de SMK, una clave de firma secreta skU relativa a la clave pública U, y de forma privada proporciona skU a U. (De hecho, en un esquema de firma digital basado en identidad, ¡la clave pública de un usuario U es la propia U!) De esta manera, si A destruye SMK después de calcular las claves secretas de los usuarios que desea habilitar para produce firmas digitales y no guarda ninguna clave secreta calculada, entonces U es el único que puede firmar digitalmente mensajes relativos a la clave pública U. Por lo tanto, cualquiera que conozca el "nombre de U", conoce automáticamente la clave pública de U y, por lo tanto, puede verificar las firmas de U (posiblemente usando también el clave maestra pública PMK). En nuestra aplicación, la autoridad A es el usuario i, y el conjunto de todos los posibles usuarios U coincide con el par de paso redondo (r, s) en —digamos— S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, donde r′ es un dato ronda, y m + 3 el límite superior del número de pasos que pueden ocurrir dentro de una ronda. esto camino, pkr, s yo \(\triangleq\)(i, r, s), para que todos vean la firma de i SIGr,s pkr yo (señor, s yo) puedo, con abrumador probabilidad, verifíquela inmediatamente para el primer millón de rondas r después de r′. En otras palabras, primero genero PMK y SMK. Luego, publicita que PMK es el amo de i. clave pública para cualquier ronda r \(\in\)[r′, r′ + 106], y utiliza SMK para producir y almacenar el secreto de forma privada clave skr,s yo para cada tripleta (i, r, s) \(\in\)S. Hecho esto, destruye SMK. Si determina que no es parte de SV r,s, entonces puedo dejar skr,s yo solo (ya que el protocolo no requiere que se autentique cualquier mensaje en el Paso s de la ronda r). De lo contrario, primero uso skr,s yo para firmar digitalmente su mensaje mr,s yo, y luego destruye skr,s yo. Tenga en cuenta que puedo publicar su primera clave maestra pública cuando ingresa por primera vez al sistema. Es decir, el mismo pago \(\wp\) que trae i al sistema (en una ronda r′ o en una ronda cercana a r′), también puede especifique, a petición de i, que la clave maestra pública de i para cualquier ronda r \(\in\)[r′, r′ + 106] es PMK —por ejemplo, mediante incluyendo un par de la forma (PMK, [r′, r′ + 106]). También tenga en cuenta que, dado que m + 3 es el número máximo de pasos en una ronda, suponiendo que una ronda toma un minuto, el alijo de claves efímeras así producidas durará casi dos años. al mismo Con el tiempo, estas claves secretas efímeras no tardarán mucho en producirse. Usando una curva elíptica basada En un sistema con 32B de claves, cada clave secreta se calcula en unos pocos microsegundos. Por tanto, si m + 3 = 180, entonces, las 180 millones de claves secretas se pueden calcular en menos de una hora. Cuando la ronda actual se acerca a r′ + 106, para manejar los próximos millones de rondas, i genera un nuevo par (PMK′, SMK′) e informa cuál será su próximo alijo de claves efímeras mediante —por ejemplo— teniendo SIGi(PMK′, [r′ + 106 + 1, r′ + 2 \(\cdot\) 106 + 1]) entrar en un nuevo bloque, ya sea como “transacción” separada o como información adicional que es parte de un pago. Al hacerlo, Les informo a todos que deben usar PMK′ para verificar mis firmas efímeras en el próximo millones de rondas. Etcétera. (Tenga en cuenta que, siguiendo este enfoque básico, otras formas de implementar claves efímeras sin El uso de firmas basadas en identidad es ciertamente posible. Por ejemplo, a través de Merkle trees.16) 16En este método, genero un par de claves secretas públicas (pkr,s yo, skr, s yo ) para cada par de pasos redondos (r, s) en —digamos—Ciertamente son posibles otras formas de implementar claves efímeras, por ejemplo, a través de Merkle trees. 5.3 Coincidiendo con los pasos de Algorand ′ 1 con los de BA⋆ Como decíamos, una ronda en Algorand′ 1 tiene como máximo m + 3 pasos. Paso 1. En este paso, cada líder potencial i calcula y propaga su bloque candidato Br yo, junto con su propia credencial, \(\sigma\)r,1 yo. Recuerde que esta credencial identifica explícitamente a i. Esto es así porque \(\sigma\)r,1 yo \(\triangleq\)SIGi(r, 1, Qr−1). El verificador potencial también propaga, como parte de su mensaje, su firma digital adecuada de H(Br). yo). Al no tratarse de un pago o de una credencial, esta firma de i es relativa a su público efímero. llave pkr,1 i: es decir, propaga sigpkr,1 yo (H(Br yo )). Dadas nuestras convenciones, en lugar de propagar Br yo y sigpkr,1 yo (H(Br i )), podría haber propagado SIGpkr,1 yo (H(Br yo )). Sin embargo, en nuestro análisis necesitamos tener acceso explícito a sigpkr,1 yo (H(Br yo )). Pasos 2. En este paso, cada verificador i establece \(\ell\)r Ser el líder potencial cuya credencial hashed es el más pequeño, y Br i será el bloque propuesto por \(\ell\)r yo. Dado que, en aras de la eficiencia, desea ponerse de acuerdo sobre H(Br), en lugar de hacerlo directamente sobre Br, propaga el mensaje que habría propagado en el primer paso de BA⋆con valor inicial v′ yo = H(Br yo). Es decir, propaga v′ yo, tras firmarlo efímeramente, claro. (Es decir, después de firmarlo en relación con el efímero derecho clave pública, que en este caso es pkr,2 i .) Por supuesto también, también transmito su propia credencial. Dado que el primer paso de BA⋆consiste en el primer paso del protocolo de consenso graduado GC, Paso 2 de Algorand ′ corresponde al primer paso de GC. Pasos 3. En este paso, cada verificador i \(\in\)SV r,2 ejecuta el segundo paso de BA⋆. Es decir, envía el El mismo mensaje que habría enviado en el segundo paso de GC. Una vez más, mi mensaje es efímero. firmado y acompañado de mi credencial. (De ahora en adelante, omitiremos decir que un verificador firma efímeramente su mensaje y también propaga su credencial.) Paso 4. En este paso, cada verificador i \(\in\)SV r,4 calcula la salida de GC, (vi, gi), y efímeramente firma y envía el mismo mensaje que habría enviado en el tercer paso de BA⋆, es decir, en el primer paso de BBA⋆, con el bit inicial 0 si gi = 2 y 1 en caso contrario. Paso s = 5, . . . , m + 2. Tal paso, si alguna vez se alcanza, corresponde al paso s −1 de BA⋆ y, por tanto, a paso s −3 de BBA⋆. Dado que nuestro modelo de propagación es suficientemente asíncrono, debemos tener en cuenta la posibilidad que, en medio de tal paso s, un verificador i \(\in\)SV r,s es alcanzado por información que lo prueba ese bloque Br ya ha sido elegido. En este caso, i detiene su propia ejecución de la ronda r de Algorand ′, y comienza a ejecutar sus instrucciones de ronda-(r + 1). {r', . . . , r′ + 106} \(\times\) {1, . . . , metro + 3}. Luego ordena estas claves públicas de forma canónica, almacena la j-ésima pública ingresa la j-ésima hoja de un Merkle tree y calcula el valor raíz Ri, que publica. Cuando quiere firmar un mensaje relativo a la clave pkr,s yo , no solo proporciono la firma real, sino también la ruta de autenticación para pkr,s yo en relación con Ri. Observe que esta ruta de autenticación también prueba que pkr,s yo se almacena en la j-ésima hoja. El resto del Los detalles se pueden completar fácilmente.En consecuencia, las instrucciones de un verificador i \(\in\)SV r,s, además de las instrucciones correspondientes al Paso s −3 de BBA⋆, incluya verificar si la ejecución de BBA⋆ se ha detenido en una etapa anterior Paso s′. Dado que BBA⋆sólo puede detenerse en un paso Coin-Fixed-to-0 o en un paso Coin-Fixed-to-1, el las instrucciones distinguen si A (Condición final 0): s′ −2 ≡0 mod 3, o B (Condición final 1): s′ −2 ≡1 mod 3. De hecho, en el caso A, el bloque Br no está vacío y, por lo tanto, se necesitan instrucciones adicionales para asegúrese de que i reconstruya adecuadamente Br, junto con su certificado adecuado CERT r. En el caso B, el bloque Br está vacío y, por lo tanto, se me indica que establezca Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), y para calcular CERT r. Si, durante la ejecución del paso s, no veo ninguna evidencia de que el bloque Br ya haya sido generado, luego envía el mismo mensaje que habría enviado en el paso s −3 de BBA⋆. Paso m + 3. Si durante el paso m + 3, i \(\in\)SV r,m+3 ve que el bloque Br ya fue generado en un paso previo s′, luego procede tal como se explicó anteriormente. De lo contrario, en lugar de enviar el mismo mensaje que habría enviado en el paso m de BBA⋆, i es recibió instrucciones, basándose en la información que poseía, de calcular Br y su correspondiente certificado CERT r. Recuerde, de hecho, que elevamos en m + 3 el número total de pasos de una ronda. 5.4 El protocolo real Recuerde que, en cada paso s de una ronda r, un verificador i \(\in\)SV r,s utiliza su par de claves secretas públicas de largo plazo para presentar su credencial, \(\sigma\)r,s yo \(\triangleq\)SIGi(r, s, Qr−1), así como SIGi qr-1 en caso s = 1. Verificador i utiliza su efímera clave secreta skr,s yo para firmar su mensaje (r, s) mr,s yo. Por simplicidad, cuando r y s son claro, escribimos esigi(x) en lugar de sigpkr,s i (x) para denotar la firma efímera propia de un valor x en el paso s de la ronda r, y escriba ESIGi(x) en lugar de SIGpkr,s i (x) para denotar (i, x, esigi(x)). Paso 1: bloquear la propuesta Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 1 de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,1 o no. • Si i /\(\in\)SV r,1, entonces i detiene su propia ejecución del Paso 1 de inmediato. • Si i \(\in\)SV r,1, es decir, si i es un líder potencial, entonces cobra los pagos redondos r que han se le ha propagado hasta el momento y calcula un pago máximo PAY r yo de ellos. A continuación, él calcula su “bloque de candidatos” fr. i = (r, PAGAR r i , SIGi(Qr−1), H(Br−1)). Finalmente, calcula el mensaje señor,1 yo = (Hermano yo , esigi(H(Br i )), \(\sigma\)r,1 i ), destruye su efímera clave secreta skr,1 yo, y luego propaga mr,1 yo.Observación. En la práctica, para acortar la ejecución global del Paso 1, es importante que el (r, 1)- Los mensajes se propagan selectivamente. Es decir, para cada usuario i en el sistema, para el primer (r, 1)- mensaje que alguna vez recibe y verifica con éxito,17 el jugador i lo propaga como de costumbre. Para todos los otros (r, 1): mensajes que el jugador i recibe y verifica con éxito, los propaga solo si el hash El valor de la credencial que contiene es el más pequeño entre los valores hash de las credenciales contenidas. en todos los mensajes (r, 1) que ha recibido y verificado con éxito hasta el momento. Además, como sugiere Según Georgios Vlachos, es útil que cada líder potencial i también propague su credencial \(\sigma\)r,1 yo por separado: esos pequeños mensajes viajan más rápido que los bloques, aseguran la propagación oportuna del mr,1 j's donde las credenciales contenidas tienen valores hash pequeños, mientras que aquellas con valores hash grandes desaparecer rápidamente. Paso 2: El primer paso del Protocolo de Consenso Graduado GC Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 2 de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,2 o no. • Si i /\(\in\)SV r,2 entonces i detiene su propia ejecución del Paso 2 de inmediato. • Si i \(\in\)SV r,2, entonces después de esperar un tiempo t2 \(\triangleq\) \(\lambda\) + Λ, i actúa de la siguiente manera. 1. Encuentra al usuario \(\ell\)tal que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) para todas las credenciales \(\sigma\)r,1 j que son parte de los mensajes (r, 1) verificados con éxito que ha recibido hasta ahora.a 2. Si ha recibido de \(\ell\) un mensaje válido mr,1 \(\ell\) = (Hermano \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b entonces me pongo v′ yo \(\triangleq\)H(Br \(\ell\)); de lo contrario establezco v′ yo \(\triangleq\) \(\bot\). 3. Calculo el mensaje mr,2 yo \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),c destruye su efímera clave secreta skr,2 i y luego propaga mr,2 yo. aEsencialmente, el usuario i decide en privado que el líder de la ronda r es el usuario \(\ell\). bNuevamente, las firmas del jugador \(\ell\) y los hashes se verifican con éxito y PAGA r \(\ell\)en Br \(\ell\)es un pago válido para round r —aunque no compruebo si PAY r \(\ell\)es máximo para \(\ell\)o no. cEl mensaje señor,2 yo señala a ese jugador que considero v′ i debe ser el hash del siguiente bloque, o considera el siguiente bloque para estar vacío. 17Es decir, todas las firmas son correctas y tanto el bloque como su hash son válidos —aunque no compruebo si el pago incluido es máximo para su proponente o no.

Paso 3: el segundo paso de GC Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 3 de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,3 o no. • Si i /\(\in\)SV r,3, entonces i detiene su propia ejecución del Paso 3 de inmediato. • Si i \(\in\)SV r,3, entonces después de esperar un tiempo t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ, i actúa de la siguiente manera. 1. Si existe un valor v′ ̸= \(\bot\) tal que, entre todos los mensajes válidos mr,2 j él ha recibido, más de 2/3 de ellos son de la forma (ESIGj(v′), \(\sigma\)r,2 j ), sin contradicción alguna,a luego calcula el mensaje mr,3 yo \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 yo). De lo contrario, calcula mr,3 yo \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 yo). 2. Destruyo su efímera clave secreta skr,3 i y luego propaga mr,3 yo. aEs decir, no ha recibido dos mensajes válidos que contengan ESIGj(v′) y un ESIGj(v′′) diferente respectivamente, de un jugador j. Aquí y de aquí en adelante, excepto en las Condiciones Finales que se definen más adelante, siempre que un jugador honesto quiere mensajes de una forma determinada, los mensajes que se contradicen entre sí nunca se cuentan ni se consideran válidos.Paso 4: Salida de GC y el primer paso de BBA⋆ Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 4 de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,4 o no. • Si i /\(\in\)SV r,4, entonces i detiene su propia ejecución del Paso 4 de inmediato. • Si i \(\in\)SV r,4, entonces después de esperar un tiempo t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ, i actúa de la siguiente manera. 1. Calcula vi y gi, la salida de GC, de la siguiente manera. (a) Si existe un valor v′ ̸= \(\bot\) tal que, entre todos los mensajes válidos mr,3 j el tiene recibidos, más de 2/3 de ellos son de la forma (ESIGj(v′), \(\sigma\)r,3 j ), luego establece vi \(\triangleq\)v′ y gi \(\triangleq\)2. (b) En caso contrario, si existe un valor v′ ̸= \(\bot\) tal que, entre todos los mensajes válidos señor,3 j ha recibido, más de 1/3 de ellos son de la forma (ESIGj(v′), \(\sigma\)r,3 j), entonces establece vi \(\triangleq\)v′ y gi \(\triangleq\)1.a (c) En caso contrario, establece vi \(\triangleq\)H(Br ǫ ) y gi \(\triangleq\)0. 2. Calcula bi, la entrada de BBA⋆, de la siguiente manera: bi \(\triangleq\)0 si gi = 2, y bi \(\triangleq\)1 en caso contrario. 3. Calcula el mensaje mr,4 yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), destruye su efímero clave secreta skr,4 i y luego propaga mr,4 yo. aSe puede demostrar que v′ en el caso (b), si existe, debe ser única.

Paso s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: un paso de BBA⋆ con moneda fijada a 0 Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,s. • Si i /\(\in\)SV r,s, entonces i detiene su propia ejecución del Paso s inmediatamente. • Si i \(\in\)SV r,s entonces actúa de la siguiente manera. – Espera hasta que haya transcurrido un tiempo ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. – Condición final 0: Si, durante dicha espera y en cualquier momento, existe una cadena v ̸= \(\bot\)y un paso s′ tal que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3, es decir, el paso s′ es un paso fijo con moneda a 0, (b) he recibido al menos tH = 2n 3 + 1 mensajes válidos mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a y (c) He recibido un mensaje válido mr,1 j = (Hermano j , esigj(H(Br j )), \(\sigma\)r,1 j ) con v = H(Br j), entonces, detengo su propia ejecución de los Pasos s (y de hecho de la ronda r) inmediatamente sin propagar cualquier cosa; establece Br = Br j; y establece su propio CERT r para que sea el conjunto de mensajes señor,s′−1 j del subpaso (b).b – Condición final 1: Si, durante dicha espera y en cualquier momento, existe una paso s′ tal que (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3, es decir, el paso s′ es un paso fijo con moneda a 1, y (b’) he recibido al menos tH mensajes válidos mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c entonces, detengo su propia ejecución de los Pasos s (y de hecho de la ronda r) inmediatamente sin propagar cualquier cosa; establece Br = Br ǫ ; y establece su propio CERT r para que sea el conjunto de mensajes señor,s′−1 j del subpaso (b’). – De lo contrario, al final de la espera, el usuario i hace lo siguiente. Establece vi como el voto mayoritario de los vj en los segundos componentes de todos los votos válidos. señor, s-1 j que ha recibido. Calcula bi de la siguiente manera. Si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)0. De lo contrario, si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)1. De lo contrario, establece bi \(\triangleq\)0. Calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destruye su efímero clave secreta skr,s i y luego propaga mr,s yo. aUn mensaje de este tipo del jugador j se cuenta incluso si el jugador i también ha recibido un mensaje de j firmando por 1. Cosas similares para la condición final 1. Como se muestra en el análisis, esto se hace para garantizar que todos los usuarios honestos sepan Br dentro del tiempo \(\lambda\) entre sí. El usuario i ahora conoce a Br y sus propios acabados redondos. Todavía ayuda a propagar mensajes como usuario genérico, pero no inicia ninguna propagación como verificador (r, s). En particular, ha ayudado a difundir todos los mensajes en su CERT r, que es suficiente para nuestro protocolo. Tenga en cuenta que también debería establecer bi \(\triangleq\)0 para el protocolo BA binario, pero bi De todos modos, no es necesario en este caso. Cosas similares para todas las instrucciones futuras. cEn este caso, no importa cuáles sean los vj.Paso s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: un paso de BBA⋆ con moneda fijada a 1 Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,s o no. • Si i /\(\in\)SV r,s, entonces i detiene su propia ejecución del Paso s inmediatamente. • Si i \(\in\)SV r,s entonces hace lo siguiente. – Espera hasta que haya transcurrido un tiempo ts \(\triangleq\)(2s −3)\(\lambda\) + Λ. – Condición final 0: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – Condición final 1: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – De lo contrario, al final de la espera, el usuario i hace lo siguiente. Establece vi como el voto mayoritario de los vj en los segundos componentes de todos los votos válidos. señor, s-1 j que ha recibido. Calcula bi de la siguiente manera. Si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)0. De lo contrario, si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)1. En caso contrario, establece bi \(\triangleq\)1. Calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destruye su efímero clave secreta skr,s i y luego propaga mr,s yo.

Paso s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: un paso de BBA⋆ genuinamente lanzado al aire Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,s o no. • Si i /\(\in\)SV r,s, entonces i detiene su propia ejecución del Paso s inmediatamente. • Si i \(\in\)SV r,s entonces hace lo siguiente. – Espera hasta que haya transcurrido un tiempo ts \(\triangleq\)(2s −3)\(\lambda\) + Λ. – Condición final 0: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – Condición final 1: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – De lo contrario, al final de la espera, el usuario i hace lo siguiente. Establece vi como el voto mayoritario de los vj en los segundos componentes de todos los votos válidos. señor, s-1 j que ha recibido. Calcula bi de la siguiente manera. Si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)0. De lo contrario, si más de 2/3 de todos los mr,s−1 válidos j que ha recibido son de la forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), luego establece bi \(\triangleq\)1. De lo contrario, sea SV r,s−1 yo ser el conjunto de (r, s −1)-verificadores de quienes ha recibido una mensaje señor, s-1 j . Él establece bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 yo H(\(\sigma\)r,s−1 j )). Calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destruye su efímero clave secreta skr,s i y luego propaga mr,s yo.

Paso m + 3: El último paso de BBA⋆a Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso m + 3 de la ronda r tan pronto como conoce Br−1. • El usuario i calcula Qr−1 a partir del tercer componente de Br−1 y comprueba si i \(\in\)SV r,m+3 o no. • Si i /\(\in\)SV r,m+3, entonces i detiene su propia ejecución del Paso m + 3 de inmediato. • Si i \(\in\)SV r,m+3 entonces hace lo siguiente. – Espera hasta que haya transcurrido un tiempo tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ. – Condición final 0: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – Condición final 1: Las mismas instrucciones que los pasos Coin-Fixed-To-0. – De lo contrario, al final de la espera, el usuario i hace lo siguiente. Él establece i \(\triangleq\)1 y Br \(\triangleq\)Br ǫ. Calcula el mensaje mr,m+3 yo = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 yo ), destruye su clave secreta efímera skr,m+3 yo y luego propaga mr,m+3 yo para certificar Br.b aCon una probabilidad abrumadora, BBA⋆ha terminado antes de este paso, y especificamos este paso para que esté completo. Un certificado b del Paso m + 3 no tiene que incluir ESIGi(outi). Lo incluimos sólo por uniformidad: el Los certificados ahora tienen un formato uniforme sin importar en qué paso se generen.Reconstrucción del bloque Round-r por parte de no verificadores Instrucciones para cada usuario i en el sistema: El usuario i comienza su propia ronda tan pronto como lo sepa. Br-1, y espera información del bloque de la siguiente manera. – Si, durante dicha espera y en cualquier momento, existe una cadena v y un paso s′ tal eso (a) 5 \(\leq\)s′ \(\leq\)m + 3 con s′ −2 ≡0 mod 3, (b) he recibido al menos tH mensajes válidos mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ), y (c) He recibido un mensaje válido mr,1 j = (Hermano j , esigj(H(Br j )), \(\sigma\)r,1 j ) con v = H(Br j), entonces, detengo su propia ejecución de la ronda r inmediatamente; establece Br = Br j; y establece su propio CERT r ser el conjunto de mensajes mr,s′−1 j del subpaso (b). – Si, durante dicha espera y en cualquier momento, existe un paso s′ tal que (a’) 6 \(\leq\)s′ \(\leq\)m + 3 con s′ −2 ≡1 mod 3, y (b’) he recibido al menos tH mensajes válidos mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), entonces, detengo su propia ejecución de la ronda r inmediatamente; establece Br = Br ǫ; y establece su propio CERT r ser el conjunto de mensajes mr,s′−1 j del subpaso (b’). – Si, durante dicha espera y en cualquier momento, he recibido al menos tH mensajes válidos señor,m+3 j = (ESIGj(1), ESIGj(H(Br ǫ )), \(\sigma\)r,m+3 j ), entonces detengo su propia ejecución de la ronda r inmediatamente, establece Br = Br ǫ y establece su propio CERT r como el conjunto de mensajes mr,m+3 j por 1 y H(Br ǫ). 5.5 Análisis de Algorand ′ 1 Introducimos las siguientes notaciones para cada ronda r \(\geq\)0, utilizadas en el análisis. • Sea T r el momento en que el primer usuario honesto conoce Br−1. • Sea Ir+1 el intervalo [T r+1, T r+1 + \(\lambda\)]. Tenga en cuenta que T 0 = 0 por la inicialización del protocolo. Para cada s \(\geq\)1 y i \(\in\)SV r,s, recuerde que \(\alpha\)r, s yo y \(\beta\)r,s yo son respectivamente la hora de inicio y la hora de finalización de los pasos s del jugador i. Además, recuerde que ts = (2s −3)\(\lambda\) + Λ para cada 2 \(\leq\)s \(\leq\)m + 3. Además, sean I0 \(\triangleq\){0} y t1 \(\triangleq\)0. Finalmente, recuerde que Lr \(\leq\)m/3 es una variable aleatoria que representa el número de ensayos de Bernoulli. necesario para ver un 1, cuando cada prueba es 1 con probabilidad ph 2 y hay como máximo m/3 ensayos. si todo las pruebas fallan entonces Lr \(\triangleq\)m/3. En el análisis ignoramos el tiempo de cálculo, ya que de hecho es insignificante en relación con el tiempo necesario. para propagar mensajes. En cualquier caso, al usar \(\lambda\) y Λ ligeramente mayores, el tiempo de cálculo puede incorporarse directamente al análisis. La mayoría de las afirmaciones siguientes son válidas “con abrumadora probabilidad”, y es posible que no enfaticemos repetidamente este hecho en el análisis.5.6 Teorema principal Teorema 5.1. Las siguientes propiedades se mantienen con una probabilidad abrumadora para cada ronda r \(\geq\)0: 1. Todos los usuarios honestos coinciden en el mismo bloque Br. 2. Cuando el líder \(\ell\)r es honesto, el bloque Br es generado por \(\ell\)r, Br contiene un pago máximo recibido por \(\ell\)r por tiempo \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ y todos los usuarios honestos conocen Br en el tiempo intervalo Ir+1. 3. Cuando el líder \(\ell\)r es malicioso, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ y todos los usuarios honestos saben Br en el intervalo de tiempo Ir+1. 4. ph = h2(1 + h −h2) para Lr, y el líder \(\ell\)r es honesto con probabilidad al menos ph. Antes de demostrar nuestro teorema principal, hagamos dos observaciones. Observaciones. • Generación de bloques y latencia verdadera. El tiempo para generar el bloque Br se define como T r+1 −T r. Es decir, se define como la diferencia entre la primera vez que un usuario honesto aprende Br y la primera vez que un usuario honesto aprende Br−1. Cuando el líder de la ronda r es honesto, la Propiedad 2 es nuestra El teorema principal garantiza que el tiempo exacto para generar Br es 8\(\lambda\) + Λ tiempo, sin importar qué el valor preciso de h > 2/3 puede ser. Cuando el líder es malicioso, la Propiedad 3 implica que el El tiempo esperado para generar Br está limitado por ( 12 ph + 10)\(\lambda\) + Λ, de nuevo no importa la precisión valor de h.18 Sin embargo, el tiempo esperado para generar Br depende del valor preciso de h. De hecho, según la Propiedad 4, ph = h2(1 + h −h2) y el líder es honesto con probabilidad al menos ph, por lo tanto E[T r+1 −T r] \(\leq\)h2(1 + h −h2) \(\cdot\) (8\(\lambda\) + Λ) + (1 −h2(1 + h −h2))(( 12 h2(1 + h −h2) + 10)\(\lambda\) + Λ). Por ejemplo, si h = 80%, entonces E[T r+1 −T r] \(\leq\)12,7\(\lambda\) + Λ. • \(\lambda\) frente a Λ. Tenga en cuenta que el tamaño de los mensajes enviados por los verificadores en un paso Algorand ′ está dominado por la longitud de las claves de firma digital, que pueden permanecer fijas, incluso cuando el número de usuarios es enorme. También tenga en cuenta que, en cualquier paso s > 1, el mismo número esperado n de verificadores se puede utilizar ya sea que el número de usuarios sea 100K, 100M o 100M. Esto es así porque n únicamente depende de hy F. En resumen, por lo tanto, salvo una necesidad repentina de aumentar la longitud de la clave secreta, el valor de \(\lambda\) debe permanecer igual sin importar cuán grande sea el número de usuarios en el futuro previsible. Por el contrario, para cualquier tasa de transacción, el número de transacciones crece con el número de usuarios. Por lo tanto, para procesar todas las transacciones nuevas de manera oportuna, el tamaño de un bloque debe también crece con el número de usuarios, lo que hace que Λ también crezca. Por lo tanto, a largo plazo, deberíamos haber \(\lambda\) << Λ. En consecuencia, es apropiado tener un coeficiente mayor para \(\lambda\), y en realidad un coeficiente de 1 para Λ. Demostración del teorema 5.1. Probamos las propiedades 1 a 3 por inducción: suponiendo que se cumplan para la ronda r −1 (sin pérdida de generalidad, se cumplen automáticamente para la “ronda -1” cuando r = 0), los probamos para redondo r. 18Efectivamente, E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Dado que Br−1 está definido únicamente por la hipótesis inductiva, el conjunto SV r,s está definido únicamente para cada paso s de la ronda r. Por la elección de n1, SV r,1 ̸= \(\emptyset\) con abrumadora probabilidad. nosotros ahora Enuncie los siguientes dos lemas, demostrados en las Secciones 5.7 y 5.8. Durante toda la inducción y en En las pruebas de los dos lemas, el análisis de la ronda 0 es casi el mismo que el del paso inductivo, y resaltaremos las diferencias cuando ocurran. Lema 5.2. [Lema de integridad] Suponiendo que las propiedades 1 a 3 se mantienen para la ronda r-1, cuando el líder \(\ell\)r es honesto, con una probabilidad abrumadora, • Todos los usuarios honestos están de acuerdo en el mismo bloque Br, que es generado por \(\ell\)r y contiene un máximo pago recibido por \(\ell\)r en el momento \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; y • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ y todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1. Lema 5.3. [Lema de solidez] Suponiendo que las propiedades 1 a 3 se mantienen para la ronda r −1, cuando el líder \(\ell\)r es malicioso, con una probabilidad abrumadora, todos los usuarios honestos coinciden en el mismo bloque Br, T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ y todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1. Las propiedades 1 a 3 se mantienen aplicando los lemas 5.2 y 5.3 a r = 0 y al paso inductivo. Finalmente, Reformulamos la Propiedad 4 como el siguiente lema, demostrado en la Sección 5.9. Lema 5.4. Dadas las propiedades 1 a 3 para cada ronda antes de r, ph = h2(1 + h −h2) para Lr, y la El líder \(\ell\)r es honesto con probabilidad al menos ph. Combinando los tres lemas anteriores, se cumple el teorema 5.1. ■ El siguiente lema establece varias propiedades importantes sobre la ronda r dada la inductiva. hipótesis, y se utilizará en las pruebas de los tres lemas anteriores. Lema 5.5. Supongamos que las propiedades 1 a 3 se mantienen para la ronda r −1. Para cada paso s \(\geq\)1 de la ronda r y cada verificador honesto i \(\in\)HSV r,s, tenemos que (a) \(\alpha\)r,s yo \(\in\)Ir; (b) si el jugador i ha esperado una cantidad de tiempo ts, entonces \(\beta\)r,s yo \(\in\)[T r + ts, T r + \(\lambda\) + ts] para r > 0 y \(\beta\)r,s yo = ts para r = 0; y (c) si el jugador i ha esperado una cantidad de tiempo ts, entonces en el tiempo \(\beta\)r,s Yo, ha recibido todos los mensajes. enviado por todos los verificadores honestos j \(\in\)HSV r,s′ para todos los pasos s′ < s. Además, para cada paso s \(\geq\)3, tenemos que (d) no existen dos jugadores diferentes i, i′ \(\in\)SV r,s y dos valores diferentes v, v′ del mismo longitud, tal que ambos jugadores han esperado una cantidad de tiempo ts, más de 2/3 de todo el mensajes válidos mr,s−1 j El jugador que recibo ha firmado por v, y más de 2/3 de todos los válidos. mensajes señor, s-1 j El jugador que recibe i′ ha firmado por v′. Prueba. La propiedad (a) se deriva directamente de la hipótesis inductiva, ya que el jugador i conoce Br−1 en el intervalo de tiempo Ir y comienza sus propios pasos de inmediato. La propiedad (b) se sigue directamente de (a): ya que El jugador i ha esperado una cantidad de tiempo ts antes de actuar, \(\beta\)r,s. yo = \(\alpha\)r,s yo + ts. Tenga en cuenta que \(\alpha\)r,s yo = 0 para r = 0. Ahora demostramos la propiedad (c). Si s = 2, entonces por la Propiedad (b), para todos los verificadores j \(\in\)HSV r,1 tenemos \(\beta\)r,s yo = \(\alpha\)r,s yo + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j + Λ.Dado que cada verificador j \(\in\)HSV r,1 envía su mensaje en el tiempo \(\beta\)r,1 j y el mensaje llega a todos los honestos usuarios en como máximo Λ tiempo, por tiempo \(\beta\)r,s yo jugador he recibido los mensajes enviados por todos los verificadores en HSV r,1 como se desee. Si s > 2, entonces ts = ts−1 + 2\(\lambda\). Por la propiedad (b), para todos los pasos s′ < s y todos los verificadores j \(\in\)HSV r,s′, \(\beta\)r,s yo = \(\alpha\)r,s yo + ts \(\geq\)T r + ts = T r + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = T r + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ j + \(\lambda\). Dado que cada verificador j \(\in\)HSV r,s′ envía su mensaje en el instante \(\beta\)r,s′ j y el mensaje llega a todos los honestos usuarios en como máximo \(\lambda\) tiempo, por tiempo \(\beta\)r,s yo jugador he recibido todos los mensajes enviados por todos los verificadores honestos en HSV r,s′ para todos s′ < s. Por tanto, se cumple la propiedad (c). Finalmente, demostramos la propiedad (d). Tenga en cuenta que los verificadores j \(\in\)SV r,s−1 firman como máximo dos cosas en Paso s −1 usando sus claves secretas efímeras: un valor vj de la misma longitud que la salida del hash función, y también un poco bj \(\in\){0, 1} si s −1 \(\geq\)4. Por eso en el enunciado del lema requerimos que v y v′ tengan la misma longitud: muchos verificadores pueden haber firmado ambos un valor hash v y un bit b, por lo que ambos pasan el umbral de 2/3. Supongamos, en aras de la contradicción, que existen los verificadores deseados i, i′ y los valores v, v′. Tenga en cuenta que algunos verificadores maliciosos en MSV r,s−1 pueden haber firmado tanto v como v′, pero cada uno honesto El verificador en HSV r,s−1 ha firmado como máximo uno de ellos. Por la propiedad (c), tanto i como i′ han recibido todos los mensajes enviados por todos los verificadores honestos en HSV r,s−1. Sea HSV r,s−1(v) el conjunto de verificadores (r, s −1) honestos que han firmado v, MSV r,s−1 yo el conjunto de verificadores (r, s −1) maliciosos de los cuales he recibido un mensaje válido, y MSV r,s−1 yo (v) el subconjunto de MSV r,s−1 yo de quien he recibido una firma de mensaje válida v. Por los requisitos para i y v, tenemos relación \(\triangleq\)|HSV r,s−1(v)| + |VMS r,s−1 yo (v)| |VHS r,s−1| + |VMS r,s−1 yo |

2 3. (1) Primero mostramos |VMS r,s−1 yo (v)| \(\leq\)|VHS r,s−1(v)|. (2) Suponiendo lo contrario, por las relaciones entre los parámetros, con una probabilidad abrumadora |VHS r,s−1| > 2|MSV r,s−1| \(\geq\)2|VSM r,s−1 yo |, por lo tanto relación < |HSV r,s−1(v)| + |VMS r,s−1 yo (v)| 3|VSM r,s−1 yo | < 2|MSV r,s−1 yo (v)| 3|VSM r,s−1 yo | \(\leq\)2 3, Contradicción con la desigualdad 1. A continuación, por la desigualdad 1 tenemos 2|VHS r,s−1| + 2|MSV r,s−1 yo | < 3|VHS r,s−1(v)| + 3|MSV r,s−1 yo (v)| \(\leq\) 3|VHS r,s−1(v)| + 2|MSV r,s−1 yo | + |VMS r,s−1 yo (v)|. Combinando con la desigualdad 2, 2|VHS r,s−1| < 3|VHS r,s−1(v)| + |VMS r,s−1 yo (v)| \(\leq\)4|VHS r,s−1(v)|, lo que implica |VHS r,s−1(v)| > 1 2|VHS r,s−1|.De manera similar, por los requisitos para i′ y v′, tenemos |VHS r,s−1(v′)| > 1 2|VHS r,s−1|. Dado que un verificador honesto j \(\in\)HSV r,s−1 destruye su efímera clave secreta skr,s−1 j antes de propagar En su mensaje, el Adversario no puede falsificar la firma de j por un valor que j no firmó, después aprender que j es un verificador. Por lo tanto, las dos desigualdades anteriores implican |HSV r,s−1| \(\geq\)|VHS r,s−1(v)| + |VHS r,s−1(v′)| > |HSV r,s−1|, una contradicción. En consecuencia, los i, i′, v, v′ deseados no existen, y La propiedad (d) se mantiene. ■ 5.7 El lema de la completitud Lema 5.2. [Lema de integridad, reformulado] Suponiendo que las propiedades 1–3 se mantienen para la ronda r−1, cuando el líder \(\ell\)r es honesto, con una probabilidad abrumadora, • Todos los usuarios honestos están de acuerdo en el mismo bloque Br, que es generado por \(\ell\)r y contiene un máximo pago recibido por \(\ell\)r en el momento \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; y • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ y todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1. Prueba. Según la hipótesis inductiva y el Lema 5.5, para cada paso s y verificador i \(\in\)HSV r,s, \(\alpha\)r, s yo \(\in\)Ir. A continuación analizamos el protocolo paso a paso. Paso 1. Por definición, todo verificador honesto i \(\in\)HSV r,1 propaga el mensaje deseado mr,1 yo en tiempo \(\beta\)r,1 yo = \(\alpha\)r,1 yo, donde señor,1 yo = (Hermano yo , esigi(H(Br i )), \(\sigma\)r,1 yo), hermano i = (r, PAGAR r i , SIGi(Qr−1), H(Br−1)), y PAGAR r i es un conjunto de pagos máximo entre todos los pagos que i ha visto en el tiempo \(\alpha\)r,1 yo. Paso 2. Fijar arbitrariamente un verificador honesto i \(\in\)HSV r,2. Según el Lema 5.5, cuando el jugador i termina esperando en el momento \(\beta\)r,2 yo = \(\alpha\)r,2 yo + t2, ha recibido todos los mensajes enviados por los verificadores en HSV r,1, incluidos señor, 1 \(\ell\)r. Según la definición de \(\ell\)r, no existe otro jugador en PKr−k cuya credencial sea hash el valor es menor que H(\(\sigma\)r,1 \(\ell\)r). Por supuesto, el Adversario puede corromper a \(\ell\)r después de ver que H(\(\sigma\)r,1 \(\ell\)r) es muy pequeño, pero para entonces el jugador \(\ell\)r ha destruido su clave efímera y el mensaje mr,1 \(\ell\)r ha sido propagado. Por lo tanto, el verificador i establece que su propio líder sea el jugador \(\ell\)r. En consecuencia, en el momento \(\beta\)r,2 yo, verificador i propaga mr,2 yo = (ESIGi(v′ i), \(\sigma\)r,2 i ), donde v′ yo = H(Br \(\ell\)r). Cuando r = 0, la única diferencia es que \(\beta\)r,2 yo = t2 en lugar de estar en un rango. Se pueden decir cosas similares para pasos futuros y No los enfatizaré nuevamente. Paso 3. Fijar arbitrariamente un verificador honesto i \(\in\)HSV r,3. Según el Lema 5.5, cuando el jugador i termina esperando en el momento \(\beta\)r,3 yo = \(\alpha\)r,3 yo + t3, ha recibido todos los mensajes enviados por los verificadores en HSV r,2. Por las relaciones entre los parámetros, con abrumadora probabilidad |HSV r,2| > 2|MSV r,2|. Además, ningún verificador honesto firmaría mensajes contradictorios, y el Adversario no puede falsificar la firma de un verificador honesto después de que éste haya destruido su correspondiente clave secreta efímera. Por lo tanto, más de 2/3 de todos los mensajes (r, 2) válidos que he recibido son de verificadores honestos y de la forma mr,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), sin contradicción. En consecuencia, en el momento \(\beta\)r,3 yo jugador que propaga mr,3 yo = (ESIGi(v′), \(\sigma\)r,3 i ), donde v′ = H(Br \(\ell\)r).Paso 4. Fijar arbitrariamente un verificador honesto i \(\in\)HSV r,4. Según el Lema 5.5, el jugador i ha recibido todos mensajes enviados por los verificadores en HSV r,3 cuando termina de esperar en el momento \(\beta\)r,4 yo = \(\alpha\)r,4 yo +t4. Similar a Paso 3, más de 2/3 de todos los mensajes (r, 3) válidos que he recibido son de verificadores honestos y de la forma señor,3 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j). En consecuencia, el jugador i establece vi = H(Br \(\ell\)r), gi = 2 y bi = 0. En el momento \(\beta\)r,4 yo = \(\alpha\)r,4 yo +t4 se propaga señor,4 yo = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 yo). Paso 5. Fijar arbitrariamente un verificador honesto i \(\in\)HSV r,5. Según el Lema 5.5, el jugador que tendría recibido todos los mensajes enviados por los verificadores en HSV r,4 si ha esperado hasta el momento \(\alpha\)r,5 yo +t5. Tenga en cuenta que |VHS r,4| \(\geq\)tH.19 También tenga en cuenta que todos los verificadores en HSV r,4 han firmado para H(Br \(\ell\)r). Como |MSV r,4| < tH, no existe v′ ̸= H(Br \(\ell\)r) que podría haber sido firmado por tH verificadores en SV r,4 (que necesariamente serían maliciosos), por lo que el jugador i no se detiene antes de haber recibido mensajes válidos mr,4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j). Sea T el momento en que ocurre este último evento. Algunos de esos mensajes pueden ser de jugadores malintencionados, pero debido a |MSV r,4| < tH, al menos uno de ellos es de un verificador honesto en HSV r,4 y se envía después de un tiempo T r +t4. En consecuencia, T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, y para cuando T el jugador i también haya recibido el mensaje señor,1 \(\ell\)r. Según la construcción del protocolo, el jugador i se detiene en el momento \(\beta\)r,5 yo = T sin propagar cualquier cosa; establece Br = Br \(\ell\)r; y establece su propio CERT r como el conjunto de (r, 4) mensajes para 0 y H(Br \(\ell\)r) que ha recibido. Paso s > 5. De manera similar, para cualquier paso s > 5 y cualquier verificador i \(\in\)HSV r,s, el jugador i tendría recibido todos los mensajes enviados por los verificadores en HSV r,4 si ha esperado hasta el momento \(\alpha\)r,s yo + ts. por el Mismo análisis, el jugador i se detiene sin propagar nada, estableciendo Br = Br \(\ell\)r (y estableciendo el suyo propio CERT r correctamente). Por supuesto, es posible que los verificadores maliciosos no se detengan y propaguen datos arbitrarios. mensajes, sino porque |MSV r,s| < tH, por inducción ningún otro v′ podría ser firmado por los verificadores tH en cualquier paso 4 \(\leq\)s′ < s, por lo tanto los verificadores honestos sólo se detienen porque han recibido tH válido (r, 4) -mensajes para 0 y H(Br) \(\ell\)r). Reconstrucción del Bloque Ronda-r. El análisis del Paso 5 se aplica a un honesto genérico. usuario i casi sin ningún cambio. De hecho, el jugador i comienza su propia ronda r en el intervalo Ir y sólo se detendrá en un momento T cuando haya recibido tH mensajes (r, 4) válidos para H(Br) \(\ell\)r). otra vez porque al menos uno de esos mensajes es de verificadores honestos y se envía después del tiempo T r + t4, el jugador i tiene también recibió mr,1 \(\ell\)r por el tiempo T. Así establece Br = Br \(\ell\)r con el CERT r adecuado. Sólo queda demostrar que todos los usuarios honestos terminan su ronda r dentro del intervalo de tiempo Ir+1. Según el análisis del Paso 5, todo verificador honesto i \(\in\)HSV r,5 conoce Br en o antes de \(\alpha\)r,5 yo + t5 \(\leq\) Tr + \(\lambda\) + t5 = Tr + 8\(\lambda\) + Λ. Dado que T r+1 es el momento en que el primer usuario honesto conoce Br, tenemos Tr+1 \(\leq\)Tr + 8\(\lambda\) + Λ como se desee. Además, cuando el jugador conoce a Br, ya ha ayudado a propagar los mensajes en su CERT r. Tenga en cuenta que todos esos mensajes serán recibidos por todos los usuarios honestos dentro del tiempo \(\lambda\), incluso si 19Estrictamente hablando, esto sucede con una probabilidad muy alta pero no necesariamente abrumadora. Sin embargo, esto La probabilidad afecta ligeramente el tiempo de ejecución del protocolo, pero no afecta su corrección. Cuando h = 80%, entonces |VHS r,4| \(\geq\)tH con probabilidad 1 −10−8. Si este evento no ocurre, entonces el protocolo continuará por otro 3 pasos. Como la probabilidad de que esto no ocurra en dos pasos es insignificante, el protocolo terminará en el Paso 8. En Como se esperaba, entonces, el número de pasos necesarios es casi 5.El jugador fue el primero en propagarlos. Además, siguiendo el análisis anterior tenemos Tr+1 \(\geq\)Tr + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, por lo tanto todos los usuarios honestos han recibido mr,1 \(\ell\)r por tiempo T r+1 + \(\lambda\). En consecuencia, todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Finalmente, para r = 0 en realidad tenemos T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ. Combinando todo junto, El lema 5.2 se cumple. ■ 5.8 El lema de la solidez Lema 5.3. [Lema de solidez, reformulado] Suponiendo que las propiedades 1 a 3 se mantienen para la ronda r −1, cuando el líder \(\ell\)r es malicioso, con una probabilidad abrumadora, todos los usuarios honestos coinciden en el mismo bloque Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ y todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1. Prueba. Consideramos las dos partes del protocolo, GC y BBA⋆, por separado. GC. Por la hipótesis inductiva y por el Lema 5.5, para cualquier paso s \(\in\){2, 3, 4} y cualquier paso honesto verificador i \(\in\)HSV r,s, cuando el jugador i actúa en el momento \(\beta\)r,s yo = \(\alpha\)r,s yo + ts, ha recibido todos los mensajes enviados por todos los verificadores honestos en los pasos s′ < s. Distinguimos dos posibles casos para el paso 4. Caso 1. Ningún verificador i \(\in\)HSV r,4 establece gi = 2. En este caso, por definición bi = 1 para todos los verificadores i \(\in\)HSV r,4. Es decir, comienzan con un acuerdo sobre 1 en el protocolo binario BA. Es posible que no tengan un acuerdo sobre sus vi, pero esto no importa como veremos en el binario BA. Caso 2. Existe un verificador ˆi \(\in\)HSV r,4 tal que gˆi = 2. En este caso demostramos que (1) gi \(\geq\)1 para todo i \(\in\)HSV r,4, (2) existe un valor v′ tal que vi = v′ para todo i \(\in\)HSV r,4, y (3) existe un mensaje válido mr,1 \(\ell\) de algún verificador \(\ell\) \(\in\)SV r,1 tal que v′ = H(Br \(\ell\)). De hecho, dado que el jugador ˆi es honesto y establece gˆi = 2, más de 2/3 de todos los mensajes válidos mr,3 j ha recibido son por el mismo valor v′ ̸= \(\bot\), y ha puesto vˆi = v′. Por la Propiedad (d) en el Lema 5.5, para cualquier otro verificador (r, 4) i honesto, no puede ser más de 2/3 de todos los mensajes válidos mr,3 j que i′ ha recibido son del mismo valor v′′ ̸= v′. En consecuencia, si i establece gi = 2, debe ser que i también ha visto > 2/3 de la mayoría para v′ y establece vi = v′, como se desee. Consideremos ahora un verificador arbitrario i \(\in\)HSV r,4 con gi < 2. Similar al análisis de Propiedad (d) en el Lema 5.5, debido a que el jugador ˆi ha visto > 2/3 de mayoría para v′, más de 1 2|VHS r,3| honesto (r, 3)-los verificadores han firmado v′. Porque he recibido todos los mensajes de verificadores honestos (r, 3) de tiempo \(\beta\)r,4 yo = \(\alpha\)r,4 yo + t4, en particular ha recibido más de 1 2|VHS r,3| mensajes de ellos para v′. Porque |HSV r,3| > 2|MSV r,3|, i ha visto > 1/3 de mayoría para v′. En consecuencia, jugador i establece gi = 1 y se cumple la propiedad (1). ¿El jugador i necesariamente establece vi = v′? Supongamos que existe un valor diferente v′′ ̸= \(\bot\)tal que El jugador i también ha visto > 1/3 de mayoría para v′′. Algunos de esos mensajes pueden ser de origen malicioso. verificadores, pero al menos uno de ellos es de algún verificador honesto j \(\in\)HSV r,3: de hecho, porque |VHS r,3| > 2|MSV r,3| y he recibido todos los mensajes de HSV r,3, el conjunto de malware Los verificadores de quienes he recibido un mensaje (r, 3) válido cuentan para < 1/3 de todos los válidos. mensajes que ha recibido.Por definición, el jugador j debe haber visto > 2/3 de la mayoría para v′′ entre todos los mensajes (r, 2) válidos. él ha recibido. Sin embargo, ya sabemos que algunos otros verificadores honestos (r, 3) han visto 2/3 de mayoría para v′ (porque firmaron v′). Según la propiedad (d) del Lema 5.5, esto no puede sucede y tal valor v′′ no existe. Por lo tanto, el jugador i debe haber configurado vi = v′ como deseaba, y la propiedad (2) se mantiene. Finalmente, dado que algunos verificadores honestos (r, 3) han visto > 2/3 de mayoría para v′, algunos (en realidad, más de la mitad de los verificadores (r, 2) honestos firmaron por v′ y propagaron sus mensajes. Según la construcción del protocolo, aquellos verificadores (r, 2) honestos deben haber recibido una evaluación válida. mensaje señor,1 \(\ell\) de algún jugador \(\ell\) \(\in\)SV r,1 con v′ = H(Br \(\ell\)), por lo que se cumple la propiedad (3). BBA⋆. Nuevamente distinguimos dos casos. Caso 1. Todos los verificadores i \(\in\)HSV r,4 tienen bi = 1. Esto sucede siguiendo el Caso 1 del CG. Como |MSV r,4| < tH, en este caso no hay verificador en SV r,5 podría recopilar o generar tH mensajes (r, 4) válidos para el bit 0. Por lo tanto, no hay ningún verificador honesto en HSV r,5 Se detendría porque conoce un bloque que no está vacío. Además, aunque hay al menos tH mensajes (r, 4) válidos para el bit 1, s′ = 5 no satisface s′ −2 ≡1 mod 3, por lo tanto ningún verificador honesto en HSV r,5 se detendría porque sabe Br = Br ǫ. En cambio, cada verificador i \(\in\)HSV r,5 actúa en el momento \(\beta\)r,5 yo = \(\alpha\)r,5 yo + t5, cuando haya recibido todo mensajes enviados por HSV r,4 siguiendo el Lema 5.5. Así, el jugador i ha visto > 2/3 de mayoría para 1 y establece bi = 1. En el paso 6, que es un paso de moneda fijada en 1, aunque s′ = 5 satisface s′ −2 ≡0 mod 3, hay no existen mensajes (r, 4) válidos para el bit 0, por lo que ningún verificador en HSV r,6 se detendría porque él conoce un bloque no vacío Br. Sin embargo, con s′ = 6, s′ −2 ≡1 mod 3 y existen |VHS r,5| \(\geq\)tH mensajes válidos (r, 5) para el bit 1 de HSV r,5. Para cada verificador i \(\in\)HSV r,6, siguiendo el Lema 5.5, en o antes del tiempo \(\alpha\)r,6 yo + t6 jugador i ha recibido todos los mensajes de HSV r,5, por lo tanto me detengo sin propagar nada y configuro Br = Br ǫ. Su CERT r es el conjunto de tH mensajes (r, 5) válidos mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) recibido por él cuando se detiene. A continuación, deje que el jugador i sea un verificador honesto en un paso s > 6 o un usuario honesto genérico (es decir, no verificador). De manera similar a la prueba del Lema 5.2, el jugador i establece Br = Br ǫ y establece el suyo CERT r será el conjunto de tH mensajes (r, 5) válidos mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) él tiene recibido. Finalmente, similar al Lema 5.2, Tr+1 \(\leq\) mín. i\(\in\)HSV r,6 \(\alpha\)r,6 yo + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, y todos los usuarios honestos conocen Br en el intervalo de tiempo Ir+1, porque el primer usuario honesto que Sabe que Br ha ayudado a propagar los mensajes (r, 5) en su CERT r. Caso 2. Existe un verificador ˆi \(\in\)HSV r,4 con bˆi = 0. Esto sucede después del Caso 2 de GC y es el caso más complejo. Según el análisis de GC, en este caso existe un mensaje válido mr,1 \(\ell\) tal que vi = H(Br \(\ell\)) para todo i \(\in\)HSV r,4. Nota que los verificadores en HSV r,4 pueden no tener un acuerdo sobre sus bi. Para cualquier paso s \(\in\){5, . . . , m + 3} y verificador i \(\in\)HSV r,s, por el Lema 5.5 jugador i habría recibió todos los mensajes enviados por todos los verificadores honestos en HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 si ha esperado por tiempo ts.Consideremos ahora el siguiente evento E: existe un paso s∗\(\geq\)5 tal que, por primera vez tiempo en el binario BA, algún jugador i∗\(\in\)SV r,s∗ (ya sea malicioso u honesto) debería detenerse sin propagar nada. Usamos “should stop” para enfatizar el hecho de que, si el jugador i∗ es malicioso, entonces puede fingir que no debe detenerse según el protocolo y propagar mensajes elegidos por el adversario. Además, según la construcción del protocolo, ya sea (E.a) i∗es capaz de recopilar o generar al menos tH mensajes válidos mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) para los mismos v y s′, con 5 \(\leq\)s′ \(\leq\)s∗ y s′ −2 ≡0 mod 3; o (E.b) i∗es capaz de recopilar o generar al menos tH mensajes válidos mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) para el mismo s′, con 6 \(\leq\)s′ \(\leq\)s∗ y s′ −2 ≡1 mod 3. Porque los mensajes honestos (r, s′ −1) son recibidos por todos los verificadores (r, s′) honestos antes de han terminado de esperar en los Pasos s′, y debido a que el Adversario recibe todo a más tardar el Usuarios honestos, sin pérdida de generalidad tenemos s′ = s∗ y el jugador i∗ es malicioso. Tenga en cuenta que No requerimos que el valor v en E.a sea el hash de un bloque válido: como quedará claro en el análisis, v = H(Br \(\ell\)) en este subevento. A continuación analizamos primero el caso 2 después del evento E, y luego mostramos que el valor de s∗es esencialmente distribuido en consecuencia a Lr (por lo tanto, el evento E ocurre antes del Paso m + 3 con abrumador probabilidad dadas las relaciones de los parámetros). Para empezar, para cualquier paso 5 \(\leq\)s < s∗, cada verificador honesto i \(\in\)HSV r,s ha esperado el tiempo ts y ha establecido vi como el voto mayoritario de la mensajes (r, s−1) válidos que ha recibido. Desde que el jugador i recibió todos los mensajes honestos (r, s−1) siguiendo el Lema 5.5, ya que todos los verificadores honestos en HSV r,4 han firmado H(Br \(\ell\)) siguiente caso 2 de GC, y desde |HSV r,s−1| > 2|MSV r,s−1| para cada s, por inducción tenemos ese jugador i ha establecido vi = H(Br \(\ell\)). Lo mismo vale para todo verificador honesto i \(\in\)HSV r,s∗ que no se detiene sin propagar cualquier cosa. Ahora consideramos el Paso s∗ y distinguimos cuatro subcasos. Caso 2.1.a. El evento E.a ocurre y existe un verificador honesto i′ \(\in\)HSV r,s∗ que debería También parar sin propagar nada. En este caso, tenemos s∗−2 ≡0 mod 3 y el Paso s∗ es un paso Coin-Fixed-To-0. Por definición, el jugador i′ ha recibido al menos tH mensajes (r, s∗−1) válidos de la forma (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 j ). Dado que todos los verificadores en HSV r,s∗−1 han firmado H(Br \(\ell\)) y |MSV r,s∗−1| < tH, tenemos v = H(Br \(\ell\)). Dado que al menos tH −|MSV r,s∗−1| \(\geq\)1 de los (r, s∗−1)-mensajes recibidos por i′ para 0 y v son enviados por verificadores en HSV r,s∗−1 después del tiempo T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\) +Λ, jugador i′ ha recibido mr,1 \(\ell\) en el momento en que recibe esos (r, s∗−1)-mensajes. Así jugador i′ se detiene sin propagar nada; establece Br = Br \(\ell\); y establece su propio CERT r como el conjunto de mensajes válidos (r, s∗−1) para 0 y v que ha recibido. A continuación, demostramos que cualquier otro verificador i \(\in\)HSV r,s∗ se ha detenido en Br = Br \(\ell\), o ha establecido bi = 0 y propagado (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s yo). De hecho, porque el Paso s∗ es la primera vez que algún verificador debe detenerse sin propagar nada, no existe un paso s′ < s∗ con s′ −2 ≡1 mod 3 tal que tH (r, s′ −1)-verificadores tengan signo 1. En consecuencia, ningún verificador en HSV r,s∗ se detiene con Br = Br ǫ.Además, como todos los verificadores honestos en los pasos {4, 5, . . . , s∗−1} han firmado H(Br \(\ell\)), no hay no existe un paso s′ \(\leq\)s∗ con s′ −2 ≡0 mod 3 tal que tH (r, s′ −1)-verificadores hayan firmado algunos v′′ ̸= H(Br \(\ell\)) —de hecho, |MSV r,s′−1| < tH. En consecuencia, ningún verificador en HSV r,s∗se detiene con Br ̸= Br ǫ y Br ̸= Br \(\ell\). Es decir, si un jugador i \(\in\)HSV r,s∗ se ha detenido sin propagando cualquier cosa, debe haber establecido Br = Br \(\ell\). Si un jugador i \(\in\)HSV r,s∗ ha esperado el tiempo ts∗ y ha propagado un mensaje en el tiempo \(\beta\)r,s∗ yo = \(\alpha\)r,s∗ yo + ts∗, ha recibido todos los mensajes de HSV r,s∗−1, incluyendo al menos tH −|MSV r,s∗−1| de ellos para 0 y v. Si he visto > 2/3 de mayoría por 1, entonces él ha visto más de 2(tH −|MSV r,s∗−1|) (r, s∗−1)-mensajes válidos para 1, con más que 2tH −3|MSV r,s∗−1| de ellos de verificadores (r, s∗−1) honestos. Sin embargo, esto implica |VHS r,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, contradiciendo el hecho de que |VHS r,s∗−1| + 4|MSV r,s∗−1| < 2n, que proviene de las relaciones de los parámetros. En consecuencia, no veo > 2/3 mayoría para 1, y establece bi = 0 porque el paso s∗ es un paso fijado con moneda a 0. como tenemos visto, vi = H(Br \(\ell\)). Así i propaga (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i ) como queríamos espectáculo. Para el Paso s∗+ 1, dado que el jugador i′ ha ayudado a propagar los mensajes en su CERT r en o antes del tiempo \(\alpha\)r,s∗ yo' + ts∗, todos los verificadores honestos en HSV r,s∗+1 han recibido al menos tH mensajes válidos (r, s∗−1) para el bit 0 y el valor H(Br \(\ell\)) en o antes de que hayan terminado esperando. Además, los verificadores en HSV r,s∗+1 no se detendrán antes de recibir aquellos (r, s∗−1)- mensajes, porque no existe ningún otro tH válido (r, s′ −1)-mensajes para el bit 1 con s′ −2 ≡1 mod 3 y 6 \(\leq\)s′ \(\leq\)s∗+ 1, según la definición del Paso s∗. En particular, paso s∗+ 1 en sí mismo es un paso Coin-Fixed-To-1, pero no se ha propagado ningún verificador honesto en HSV r,s∗ un mensaje para 1, y |MSV r,s∗| < tH. Así, todos los verificadores honestos en HSV r,s∗+1 se detienen sin propagar nada y establecen Br = hermano \(\ell\): como antes, han recibido mr,1 \(\ell\) antes de recibir los mensajes (r, s∗−1) deseados.20 Lo mismo puede decirse de todos los verificadores honestos en pasos futuros y de todos los usuarios honestos en general. En particular, todos saben Br = Br \(\ell\) dentro del intervalo de tiempo Ir+1 y Tr+1 \(\leq\) \(\alpha\)r,s∗ yo' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Caso 2.1.b. El evento E.b ocurre y existe un verificador honesto i′ \(\in\)HSV r,s∗ que debería También parar sin propagar nada. En este caso tenemos s∗−2 ≡1 mod 3 y el paso s∗ es un paso fijo con moneda a 1. El análisis es similar al Caso 2.1.a y se han omitido muchos detalles. 20 Si \(\ell\) es malicioso, podría enviar al señor 1 \(\ell\) tarde, esperando que algunos usuarios/verificadores honestos no hayan recibido mr,1 \(\ell\) todavía cuando reciban el certificado deseado para ello. Sin embargo, dado que el verificador ˆi \(\in\)HSV r,4 ha establecido bˆi = 0 y vˆi = H(Br \(\ell\)), como antes tenemos que más de la mitad de los verificadores honestos i \(\in\)HSV r,3 han fijado vi = H(Br \(\ell\)). Esto implica además más de la mitad de los verificadores honestos i \(\in\)HSV r,2 han fijado vi = H(Br \(\ell\)), y todos esos verificadores (r, 2) han recibido mr,1 \(\ell\). como el El adversario no puede distinguir a un verificador de un no verificador, no puede apuntar a la propagación de mr,1 \(\ell\) a (r, 2)-verificadores sin que los no verificadores lo vean. De hecho, con alta probabilidad, más de la mitad (o una buena fracción constante) de todos los usuarios honestos han visto mr,1 \(\ell\) después de esperar t2 desde el comienzo de su propia ronda r. De aquí en adelante, el tiempo \(\lambda\)′ necesario para mr,1 \(\ell\) para llegar a los usuarios honestos restantes es mucho menor que Λ, y por simplicidad no escríbalo en el análisis. Si 4\(\lambda\) \(\geq\) \(\lambda\)′ entonces el análisis se realiza sin ningún cambio: al final del Paso 4, todos los usuarios honestos habrían recibido mr,1 \(\ell\). Si el tamaño del bloque se vuelve enorme y 4\(\lambda\) < \(\lambda\)′, entonces en los Pasos 3 y 4, el protocolo podría pedir a cada verificador que esperara \(\lambda\)′/2 en lugar de 2\(\lambda\), y el análisis continúa manteniéndose.Como antes, el jugador i′ debe haber recibido al menos tH mensajes (r, s∗−1) válidos de la forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 j ). Nuevamente por la definición de s∗, no existe un paso 5 \(\leq\)s′ < s∗con s′ −2 ≡0 mod 3, donde al menos tH (r, s′ −1)-verificadores tienen signo 0 y lo mismo v. Así el jugador i′ se detiene sin propagar nada; establece Br = Br ǫ; y conjuntos su propio CERT r es el conjunto de mensajes (r, s∗−1) válidos para el bit 1 que ha recibido. Además, cualquier otro verificador i \(\in\)HSV r,s∗ se ha detenido en Br = Br ǫ , o ha puesto bi = 1 y propagado (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ yo ). Dado que el jugador i′ ha ayudado a propagar los mensajes (r, s∗−1) en su CERT r en el tiempo \(\alpha\)r,s∗ yo' + ts∗, nuevamente todos los verificadores honestos en HSV r,s∗+1 se detiene sin propagar nada y establece Br = Br ǫ . Del mismo modo, todo honesto. los usuarios saben Br = Br ǫ dentro del intervalo de tiempo Ir+1 y Tr+1 \(\leq\) \(\alpha\)r,s∗ yo' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Caso 2.2.a. El evento E.a ocurre y no existe un verificador honesto i′ \(\in\)HSV r,s∗que También debería parar sin propagar nada. En este caso, tenga en cuenta que el jugador i∗ podría tener un CERT r válido i∗compuesto por el tH deseado (r, s∗−1) -mensajes que el Adversario puede recopilar o generar. Sin embargo, los maliciosos Es posible que los verificadores no ayuden a propagar esos mensajes, por lo que no podemos concluir que la información honesta los usuarios los recibirán en el tiempo \(\lambda\). De hecho, |MSV r,s∗−1| de esos mensajes pueden ser de verificadores maliciosos (r, s∗−1), que no propagaron sus mensajes en absoluto y solo enviaron a los verificadores maliciosos en el paso s∗. Similar al Caso 2.1.a, aquí tenemos s∗−2 ≡0 mod 3, el Paso s∗ es un paso Coin-Fixed-To-0, y los mensajes (r, s∗−1) en CERT r i∗son para el bit 0 y v = H(Br \(\ell\)). De hecho, todo honesto Los verificadores (r, s∗−1) firman v, por lo que el adversario no puede generar tH mensajes (r, s∗−1) válidos. para una v′ diferente. Además, todos los verificadores (r, s∗) honestos han esperado el tiempo ts∗ y no ven > 2/3 de la mayoría para el bit 1, nuevamente porque |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n. Así, todo verificador honesto i \(\in\)HSV r,s∗conjuntos bi = 0, vi = H(Br \(\ell\)) por mayoría de votos, y propaga mr,s∗ yo = (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s∗ yo ) en el momento \(\alpha\)r,s∗ yo + ts∗. Consideremos ahora los verificadores honestos en el paso s∗+ 1 (que es un paso de moneda fijada en 1). si el El adversario realmente envía los mensajes en CERT r i∗a algunos de ellos y les hace detenerse, entonces similar al Caso 2.1.a, todos los usuarios honestos saben Br = Br \(\ell\)dentro del intervalo de tiempo Ir+1 y Tr+1 \(\leq\)Tr + \(\lambda\) + ts∗+1. De lo contrario, todos los verificadores honestos en el Paso s∗+1 han recibido todos los mensajes (r, s∗) para 0 y H(Br \(\ell\)) de HSV r,s∗después del tiempo de espera ts∗+1, lo que conduce a una mayoría > 2/3, porque |VHS r,s∗| > 2|MSV r,s∗|. Así, todos los verificadores en HSV r,s∗+1 propagan sus mensajes para 0 y H(Br \(\ell\)) en consecuencia. Tenga en cuenta que los verificadores en HSV r,s∗+1 no se detienen en Br = Br \(\ell\), porque el paso s∗+ 1 no es un paso de moneda fijada a 0. Consideremos ahora los verificadores honestos en el paso s∗+2 (que es un paso de moneda genuinamente lanzada al aire). Si el Adversario envía los mensajes en CERT r i∗a algunos de ellos y hace que se detengan, por otra parte, todos los usuarios honestos saben Br = Br \(\ell\) dentro del intervalo de tiempo Ir+1 y T r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.De lo contrario, todos los verificadores honestos en el Paso s∗+ 2 han recibido todos los mensajes (r, s∗+ 1) para 0 y H(Br \(\ell\)) de HSV r,s∗+1 después del tiempo de espera ts∗+2, lo que conduce a una mayoría > 2/3. Así todos ellos propagan sus mensajes para 0 y H(Br \(\ell\)) en consecuencia: eso es lo que hacen En este caso, no “lanzar una moneda”. Nuevamente, tenga en cuenta que no paran sin propagarse, porque el Paso s∗+ 2 no es un paso Coin-Fixed-To-0. Finalmente, para los verificadores honestos en el Paso s∗+3 (que es otro paso de Coin-Fixed-To-0), todos de ellos habrían recibido al menos tH mensajes válidos para 0 y H(Br \(\ell\)) de HSV s∗+2, si realmente esperan el tiempo ts∗+3. Por lo tanto, si el adversario envía o no los mensajes en CERT r i∗a cualquiera de ellos, todos los verificadores en HSV r,s∗+3 terminan en Br = Br \(\ell\), sin propagar cualquier cosa. Dependiendo de cómo actúe el Adversario, algunos de ellos pueden tener su propio CERT r que consta de esos (r, s∗−1) mensajes en CERT r i∗, y los demás tienen su propio CERT r que consta de esos mensajes (r, s∗+ 2). En cualquier caso, todos los usuarios honestos. saber Br = Br \(\ell\) dentro del intervalo de tiempo Ir+1 y T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Caso 2.2.b. El evento E.b ocurre y no existe un verificador honesto i′ \(\in\)HSV r,s∗que También debería parar sin propagar nada. El análisis en este caso es similar a los del Caso 2.1.b y Caso 2.2.a, por lo que muchos detalles han sido omitidos. En particular, CERT r i∗consiste en los tH mensajes (r, s∗−1) deseados para el bit 1 que el Adversario puede recolectar o generar, s∗−2 ≡1 mod 3, el Paso s∗es un Paso Coin-Fixed-To-1, y ningún verificador honesto (r, s∗) podría haber visto > 2/3 de mayoría para 0. Por lo tanto, cada verificador i \(\in\)HSV r,s∗ establece bi = 1 y propaga mr,s∗ yo = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ yo ) en el momento \(\alpha\)r,s∗ yo + ts∗. Similar al Caso 2.2.a, en como máximo 3 pasos más (es decir, el protocolo alcanza el Paso s∗+3, que es otro paso Coin-Fixed-To-1), todos los usuarios honestos saben Br = Br ǫ dentro del intervalo de tiempo Ir+1. Además, T r+1 puede ser \(\leq\)T r+\(\lambda\)+ts∗+1, o \(\leq\)T r+\(\lambda\)+ts∗+2, o \(\leq\)T r + \(\lambda\) + ts∗+3, dependiendo de cuándo es la primera vez que un verificador honesto puede detener sin propagarse. Combinando los cuatro subcasos, tenemos que todos los usuarios honestos conocen Br dentro del intervalo de tiempo Ir+1, con T r+1 \(\leq\)T r + \(\lambda\) + ts∗ en los Casos 2.1.a y 2.1.b, y T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 en los Casos 2.2.a y 2.2.b. Queda por el límite superior s∗ y por lo tanto T r+1 para el Caso 2, y lo hacemos considerando cómo muchas veces los pasos de la moneda genuinamente lanzada se ejecutan en el protocolo: es decir, De hecho, algunos verificadores honestos han lanzado una moneda al aire. En particular, arregle arbitrariamente un paso s′ de moneda genuinamente lanzada (es decir, 7 \(\leq\)s′ \(\leq\)m + 2 y s′ −2 ≡2 mod 3), y sea \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ). Por ahora supongamos s′ < s∗, porque de lo contrario ningún verificador honesto lanza una moneda en el Paso s′, de acuerdo con lo anterior discusiones. Según la definición de SV r,s′−1, el valor hash de la credencial de \(\ell\)′ es también el más pequeño entre todos los usuarios en PKr-k. Dado que la función hash es una oracle aleatoria, idealmente el jugador \(\ell\)′ es honesto con probabilidad al menos h. Como mostraremos más adelante, incluso si el Adversario hace lo mejor que puede para predecir el salida del oracle aleatorio e inclina la probabilidad, el jugador \(\ell\)′ sigue siendo honesto con la probabilidadal menos ph = h2(1 + h −h2). A continuación consideramos el caso en el que eso realmente sucede: es decir, \(\ell\)′ \(\in\)HSV r,s′−1. Tenga en cuenta que cada verificador honesto i \(\in\)HSV r,s′ ha recibido todos los mensajes de HSV r,s′−1 por tiempo \(\alpha\)r,s′ yo + ts′. Si el jugador i necesita lanzar una moneda (es decir, no ha visto > 2/3 de la mayoría durante el mismo bit b \(\in\){0, 1}), luego establece bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )). Si existe otro honesto verificador i′ \(\in\)HSV r,s′ que ha visto > 2/3 de mayoría para un bit b \(\in\){0, 1}, entonces por Propiedad (d) del Lema 5.5, ningún verificador honesto en HSV r,s′ habría visto > 2/3 de mayoría por un tiempo b′ ̸= b. Desde lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b con probabilidad 1/2, todos los verificadores honestos en HSV r,s′ alcanzan un acuerdo sobre b con probabilidad 1/2. Por supuesto, si dicho verificador i′ no existe, entonces todos verificadores honestos en HSV r,s′ están de acuerdo en el bit lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) con probabilidad 1. Combinando la probabilidad para \(\ell\)′ \(\in\)HSV r,s′−1, tenemos que los verificadores honestos en HSV r,s′ llegar a un acuerdo sobre un bit b \(\in\){0, 1} con probabilidad al menos ph 2 = h2(1+h−h2) 2 . Además, por inducción en el voto mayoritario como antes, todos los verificadores honestos en HSV r,s′ tienen sus vi establecidos ser H(Br \(\ell\)). Por lo tanto, una vez que se llega a un acuerdo sobre b en el Paso s′, T r+1 es ya sea \(\leq\)T r + \(\lambda\) + ts′+1 o \(\leq\)T r + \(\lambda\) + ts′+2, dependiendo de si b = 0 o b = 1, siguiendo el análisis de los Casos 2.1.a y 2.1.b. en En particular, no se ejecutará ningún otro paso de moneda genuinamente lanzada: es decir, los verificadores en Dichos pasos aún verifican que son los verificadores y, por lo tanto, esperan, pero todos se detendrán sin propagar cualquier cosa. En consecuencia, antes del Paso s∗, el número de veces que se ejecutan los pasos Coin-GenuinelyFlipped se distribuye según la variable aleatoria Lr. Dejándose pasar ser el último paso de moneda genuinamente lanzada según Lr, mediante la construcción del protocolo tenemos s′ = 4 + 3Lr. ¿Cuándo debe el Adversario realizar el Paso s∗ si quiere retrasar T r+1 tanto como posible? Incluso podemos suponer que el Adversario conoce de antemano la realización de Lr. si s∗> s′ entonces es inútil, porque los verificadores honestos ya han llegado a un acuerdo en Paso s′. Sin duda, en este caso s∗ sería s′ +1 o s′ +2, nuevamente dependiendo de si b = 0 o b = 1. Sin embargo, estos son en realidad los Casos 2.1.a y 2.1.b, y el T r+1 resultante es exactamente el igual que en ese caso. Más precisamente, T r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Si s∗< s′ −3 —es decir, s∗ está antes del penúltimo paso de la moneda genuinamente lanzada— entonces por el análisis de los Casos 2.2.a y 2.2.b, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < T r + \(\lambda\) + ts′. Es decir, el Adversario en realidad está haciendo que el acuerdo sobre Br se realice más rápido. Si s∗= s′ −2 o s′ −1, es decir, el paso Coin-Fixed-To-0 o el paso Coin-Fixed-To-1 inmediatamente antes del Paso s′; luego, mediante el análisis de los cuatro subcasos, los verificadores honestos en Los pasos s′ ya no pueden lanzar monedas porque se han detenido sin propagarse, o haber visto > 2/3 de mayoría para el mismo bit b. Por lo tanto tenemos T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.En resumen, no importa cuál sea, tenemos T r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = Tr + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = Tr + (6Lr + 10)\(\lambda\) + Λ, como queríamos mostrar. El peor caso es cuando s∗= s′ −1 y ocurre el Caso 2.2.b. Combinando los casos 1 y 2 del protocolo binario BA, se cumple el lema 5.3. ■ 5.9 Seguridad de la semilla Qr y probabilidad de un líder honesto Queda por demostrar el Lema 5.4. Recuerde que los verificadores de la ronda r se toman de PKr−k y se eligen según la cantidad Qr−1. El motivo de la introducción del parámetro retrospectivo k es asegurarse de que, en la ronda r −k, cuando el Adversario pueda agregar nuevos usuarios maliciosos para PKr−k, no puede predecir la cantidad Qr−1 excepto con una probabilidad insignificante. Tenga en cuenta que el La función hash es una oracle aleatoria y Qr−1 es una de sus entradas al seleccionar verificadores para la ronda r. Por lo tanto, no importa cuántos usuarios maliciosos se agreguen a PKr-k, desde el punto de vista del Adversario cada uno de ellos todavía está seleccionado para ser verificador en un paso de la ronda r con la probabilidad requerida p (o p1 para el Paso 1). Más precisamente, tenemos el siguiente lema. Lema 5.6. Con k = O(log1/2 F), para cada ronda r, con una probabilidad abrumadora el Adversario no consultó Qr−1 al oracle aleatorio en la ronda r −k. Prueba. Procedemos por inducción. Supongamos que para cada ronda \(\gamma\) < r, el Adversario no consultó Q\(\gamma\)−1 al oracle aleatorio en la ronda \(\gamma\) −k.21 Considere el siguiente juego mental jugado por el Adversario en la ronda r −k, tratando de predecir Qr−1. En el Paso 1 de cada ronda \(\gamma\) = r −k, . . . , r −1, dado un Q\(\gamma\)−1 específico no consultado al azar oracle, ordenando los jugadores i \(\in\)PK\(\gamma\)−k según los valores de hash H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) Cada vez más, obtenemos una permutación aleatoria sobre PK\(\gamma\)−k. Por definición, el líder \(\ell\) \(\gamma\) es el primer usuario en la permutación y es honesto con probabilidad h. Además, cuando PK\(\gamma\)−k es grande suficiente, para cualquier número entero x \(\geq\)1, la probabilidad de que los primeros x usuarios en la permutación sean todos malicioso pero el (x + 1)st es honesto es (1 −h)xh. Si \(\ell\) \(\gamma\) es honesto, entonces Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Como el adversario no puede falsificar la firma de \(\ell\) \(\gamma\), Q\(\gamma\) se distribuye uniformemente al azar desde el punto de vista del Adversario y, excepto con probabilidad exponencialmente pequeña,22 no fue consultado a H en la ronda r −k. Dado que cada Q\(\gamma\)+1, Q\(\gamma\)+2, . . . , Qr−1 respectivamente es la salida de H con Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 como una de las entradas, todos parecen aleatorios para el Adversario y el Adversario no podría haber consultado Qr−1 a H en redondear r −k. En consecuencia, el único caso en el que el adversario puede predecir Qr−1 con buena probabilidad en la ronda r−k es cuando todos los líderes \(\ell\)r−k, . . . , \(\ell\)r−1 son maliciosos. Consideremos nuevamente una ronda \(\gamma\) \(\in\){r−k . . . , r-1} y la permutación aleatoria sobre PK\(\gamma\)−k inducida por los valores hash correspondientes. si por algunos x \(\geq\)2, los primeros x −1 usuarios en la permutación son todos maliciosos y el x-ésimo es honesto, entonces el El adversario tiene x opciones posibles para Q\(\gamma\): cualquiera de la forma H(SIGi(Q\(\gamma\)−1, \(\gamma\))), donde i es una de 21 Como k es un número entero pequeño, sin pérdida de generalidad se puede suponer que las primeras k rondas del protocolo se ejecutan en un entorno seguro y la hipótesis inductiva es válida para esas rondas. 22Es decir, exponencial en la longitud de la salida de H. Tenga en cuenta que esta probabilidad es mucho menor que F.los primeros usuarios maliciosos x−1, al convertir al jugador i en el líder real de la ronda \(\gamma\); o H(Q\(\gamma\)−1, \(\gamma\)), por forzando B\(\gamma\) = B\(\gamma\) ǫ . De lo contrario, el líder de la ronda \(\gamma\) será el primer usuario honesto en la permutación. y Qr−1 se vuelve impredecible para el Adversario. ¿Cuál de las x opciones anteriores de Q\(\gamma\) debería perseguir el adversario? Para ayudar al adversario Responda esta pregunta, en el juego mental en realidad lo hacemos más poderoso de lo que realmente es, como sigue. En primer lugar, en realidad, el Adversario no puede calcular el hash de la cuenta de un usuario honesto. firma, por lo que no puede decidir, para cada Q\(\gamma\), el número x(Q\(\gamma\)) de usuarios maliciosos al principio de la permutación aleatoria en la ronda \(\gamma\) + 1 inducida por Q\(\gamma\). En el juego mental, le damos la números x(Q\(\gamma\)) gratis. En segundo lugar, en realidad, tener los primeros x usuarios en la permutación todos Ser malicioso no significa necesariamente que todos puedan convertirse en líderes, porque el hash Los valores de sus firmas también deben ser menores que p1. Hemos ignorado esta limitación en el ámbito mental. juego, dándole al Adversario aún más ventajas. Es fácil ver que en el juego mental, la opción óptima para el Adversario, denotada por ˆQ\(\gamma\), es el que produce la secuencia más larga de usuarios maliciosos al comienzo del proceso aleatorio permutación en ronda \(\gamma\) + 1. De hecho, dado un Q\(\gamma\) específico, el protocolo no depende de Q\(\gamma\)−1 ya y el Adversario sólo puede centrarse en la nueva permutación en la ronda \(\gamma\) + 1, que tiene la misma distribución para el número de usuarios maliciosos al principio. En consecuencia, en cada ronda \(\gamma\), el ˆQ\(\gamma\) mencionado anteriormente le da el mayor número de opciones para Q\(\gamma\)+1 y por lo tanto maximiza la probabilidad de que los líderes consecutivos sean todos maliciosos. Por lo tanto, en el juego mental el Adversario sigue una Cadena de Markov desde la ronda r −k para redondear r −1, siendo el espacio de estados {0} \(\cup\){x : x \(\geq\)2}. El estado 0 representa el hecho de que el El primer usuario en la permutación aleatoria en la ronda actual \(\gamma\) es honesto, por lo tanto el Adversario falla el juego de predicción de Qr−1; y cada estado x \(\geq\)2 representa el hecho de que los primeros x −1 usuarios en el Las permutaciones son maliciosas y el x-ésimo es honesto, por lo que el Adversario tiene x opciones para Q\(\gamma\). el Las probabilidades de transición P(x, y) son las siguientes. • P(0, 0) = 1 y P(0, y) = 0 para cualquier y \(\geq\)2. Es decir, el adversario falla el juego una vez que la primera El usuario en la permutación se vuelve honesto. • P(x, 0) = hx para cualquier x \(\geq\)2. Es decir, con probabilidad hx, todas las x permutaciones aleatorias tienen sus primeros usuarios son honestos, por lo que el Adversario falla el juego en la siguiente ronda. • Para cualquier x \(\geq\)2 e y \(\geq\)2, P(x, y) es la probabilidad de que, entre las x permutaciones aleatorias inducido por las opciones x de Q\(\gamma\), la secuencia más larga de usuarios maliciosos al comienzo de algunas de ellas son y −1, por lo que el Adversario tiene y opciones para Q\(\gamma\)+1 en la siguiente ronda. Es decir, P(x, y) = y-1 x yo=0 (1 −h)ih !x − y-2 x yo=0 (1 −h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Tenga en cuenta que el estado 0 es el único estado absorbente en la matriz de transición P, y todos los demás estados x tiene una probabilidad positiva de llegar a 0. Estamos interesados en acotar superiormente el número k de rondas necesarias para que la Cadena de Markov converja a 0 con una probabilidad abrumadora: es decir, no No importa en qué estado comience la cadena, con una probabilidad abrumadora el adversario pierde el juego. y no logra predecir Qr−1 en la ronda r −k. Considere la matriz de transición P (2) \(\triangleq\)P \(\cdot\) P después de dos rondas. Es fácil ver que P (2)(0, 0) = 1 y P (2)(0, x) = 0 para cualquier x \(\geq\)2. Para cualquier x \(\geq\)2 e y \(\geq\)2, como P(0, y) = 0, tenemos P(2)(x, y) = P(x, 0)P(0, y) + x z\(\geq\)2 P(x, z)P(z, y) = x z\(\geq\)2 P(x, z)P(z, y).Haciendo ¯h \(\triangleq\)1 −h, tenemos P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x y P(2)(x, y) = x z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. A continuación calculamos el límite de P (2)(x,y) P(x,y) cuando h llega a 1, es decir, ¯h llega a 0. Tenga en cuenta que el valor más alto El orden de ¯h en P(x, y) es ¯hy−1, con coeficiente x. En consecuencia, Lim h \(\to\) 1 P(2)(x, y) P(x, y) = límite ¯h \(\to\) 0 P(2)(x, y) P(x,y) = límite ¯h \(\to\) 0 P(2)(x, y) x¯hy−1 + O(¯hy) = Lim ¯h \(\to\) 0 pag z\(\geq\)2[x¯hz−1 + O(¯hz)][z¯hy−1 + O(¯hy)] x¯hy−1 + O(¯hy) = límite ¯h \(\to\) 0 2x¯hy + O(¯hy+1) x¯hy−1 + O(¯hy) = Lim ¯h \(\to\) 0 2x¯hy x¯hy−1 = lím ¯h \(\to\) 0 2¯h = 0. Cuando h es suficientemente cercano a 1,23 tenemos P(2)(x, y) P(x,y) \(\leq\)1 2 para cualquier x \(\geq\)2 y y \(\geq\)2. Por inducción, para cualquier k > 2, P (k) \(\triangleq\)P k es tal que • P (k)(0, 0) = 1, P (k)(0, x) = 0 para cualquier x \(\geq\)2, y • para cualquier x \(\geq\)2 e y \(\geq\)2, P (k)(x, y) = P (k−1)(x, 0)P(0, y) + x z\(\geq\)2 P (k−1)(x, z)P(z, y) = x z\(\geq\)2 P (k−1)(x, z)P(z, y) \(\leq\) x z\(\geq\)2 P(x,z) 2k-2 \(\cdot\) P(z, y) = P (2)(x, y) 2k-2 \(\leq\)P(x,y) 2k-1. Como P(x, y) \(\leq\)1, después de 1−log2 F rondas, la probabilidad de transición a cualquier estado y \(\geq\)2 es insignificante, comenzando con cualquier estado x \(\geq\)2. Aunque hay muchos estados de este tipo y, es fácil ver que Lim y→+∞ P(x, y) P(x, y + 1) = Lim y→+∞ (1 −¯hy)x −(1 −¯hy−1)x (1 −¯hy+1)x −(1 −¯hy)x = Lim y→+∞ ¯hy−1 −¯hy ¯hy −¯hy+1 = 1 ¯h = 1 1-h. Por lo tanto, cada fila x de la matriz de transición P disminuye como una secuencia geométrica con tasa 1 1-h > 2 cuando y es lo suficientemente grande, y lo mismo se aplica a P (k). En consecuencia, cuando k es lo suficientemente grande pero aún del orden de log1/2 F, P y\(\geq\)2 P (k)(x, y) < F para cualquier x \(\geq\)2. Es decir, con una probabilidad abrumadora el Adversario pierde el juego y no logra predecir Qr−1 en la ronda r −k. Para h \(\in\)(2/3, 1], un más Un análisis complejo muestra que existe una constante C ligeramente mayor que 1/2, tal que es suficiente para tomar k = O(logC F). Por tanto, se cumple el Lema 5.6. ■ Lema 5.4. (reformulado) Dadas las propiedades 1 a 3 para cada ronda antes de r, ph = h2(1 + h −h2) para Lr, y el líder \(\ell\)r es honesto con probabilidad al menos ph. 23Por ejemplo, h = 80% como lo sugieren las elecciones específicas de parámetros.

Prueba. Siguiendo el Lema 5.6, el Adversario no puede predecir Qr−1 en la ronda r −k excepto con probabilidad insignificante. Tenga en cuenta que esto no significa que la probabilidad de que un líder honesto sea h para cada ronda. De hecho, dado Qr-1, dependiendo de cuántos usuarios maliciosos haya al comienzo de la permutación aleatoria de PKr−k, el Adversario puede tener más de una opción para Qr y por lo tanto puede aumentar la probabilidad de que haya un líder malicioso en la ronda r + 1; nuevamente le estamos dando algunas ventajas poco realistas como en el Lema 5.6, para simplificar el análisis. Sin embargo, para cada Qr−1 que el Adversario no consultó a H en la ronda r −k, para cualquier x \(\geq\)1, con probabilidad (1 −h)x−1h, el primer usuario honesto ocurre en la posición x en el resultado permutación aleatoria de PKr−k. Cuando x = 1, la probabilidad de que haya un líder honesto en la ronda r + 1 es de hecho h; mientras que cuando x = 2, el Adversario tiene dos opciones para Qr y la probabilidad resultante es h2. Sólo considerando estos dos casos tenemos que la probabilidad de que un líder honesto en ronda r + 1 es al menos h \(\cdot\) h + (1 −h)h \(\cdot\) h2 = h2(1 + h −h2) como se desee. Tenga en cuenta que la probabilidad anterior sólo considera la aleatoriedad en el protocolo de la ronda r −k para redondear r. Cuando se tiene en cuenta toda la aleatoriedad desde la ronda 0 hasta la ronda r, Qr−1 es aún menos predecible para el Adversario y la probabilidad de un líder honesto en la ronda r + 1 es de menos h2(1 + h −h2). Reemplazando r + 1 con r y desplaza todo hacia atrás una ronda, el líder \(\ell\)r es honesto con una probabilidad de al menos h2(1 + h −h2), como se desee. De manera similar, en cada paso de una moneda lanzada genuinamente al aire, el “líder” de ese paso, es decir, el verificador. en SV r,s cuya credencial tiene el valor hash más pequeño, es honesta con probabilidad al menos h2(1 + h-h2). Así, ph = h2(1 + h −h2) para Lr y el Lema 5.4 se cumple. ■

Algorand ′

2 En esta sección, construimos una versión de Algorand ′ que funciona bajo el siguiente supuesto. Supuesto honesto de la mayoría de los usuarios: Más de 2/3 de los usuarios en cada PKr son honestos. En la Sección 8, mostramos cómo reemplazar el supuesto anterior con la deseada Mayoría Honesta de Suposición de dinero. 6.1 Notaciones y parámetros adicionales para Algorand ′ 2 Notaciones • \(\mu\) \(\in\)Z+: un límite superior pragmático para el número de pasos que, con una probabilidad abrumadora, En realidad, se tomará en una ronda. (Como veremos, el parámetro \(\mu\) controla cuántos efímeros claves que un usuario prepara con antelación para cada ronda.) • Lr: una variable aleatoria que representa el número de ensayos de Bernoulli necesarios para ver un 1, cuando cada la prueba es 1 con probabilidad ph 2 . Lr se utilizará para limitar el tiempo necesario para generar bloque br. • tH: un límite inferior para el número de verificadores honestos en un paso s > 1 de la ronda r, tal que con probabilidad abrumadora (dados n y p), hay > tH verificadores honestos en SV r,s. Parámetros • Relaciones entre varios parámetros. — Para cada paso s > 1 de la ronda r, se elige n de modo que, con una probabilidad abrumadora,

|VHS r,s| > tH y |VHS r,s| + 2|MSV r,s| < 2tH. Tenga en cuenta que las dos desigualdades anteriores juntas implican |HSV r,s| > 2|MSV r,s|: es decir, hay Hay una mayoría honesta de 2/3 entre los verificadores seleccionados. Cuanto más cercano a 1 esté el valor de h, menor debe ser n. En particular, utilizamos (variantes de) Chernofflimits para garantizar que las condiciones deseadas se mantengan con una probabilidad abrumadora. • Ejemplos de opciones de parámetros importantes. - F = 10-18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Implementación de claves efímeras en Algorand ′ 2 Recuerde que un verificador i \(\in\)SV r,s firma digitalmente su mensaje mr,s yo del paso s en la ronda r, en relación con una clave pública efímera pkr,s i, usando una clave secreta efímera skr,s yo que rápidamente destruye después de usarlo. Cuando el número de pasos posibles que puede tomar una ronda está limitado a un determinado entero \(\mu\), ya hemos visto cómo manejar prácticamente claves efímeras. Por ejemplo, como nosotros lo he explicado en Algorand ′ 1 (donde \(\mu\) = m + 3), para manejar todas sus posibles claves efímeras, desde una ronda r′ a una ronda r′ + 106, i genera un par (PMK, SMK), donde PMK public master clave de un esquema de firma basado en identidad, y SMK su correspondiente clave maestra secreta. Usuario yo publicita PMK y utiliza SMK para generar la clave secreta de cada posible clave pública efímera (y destruye SMK después de haberlo hecho). El conjunto de claves públicas efímeras de i para lo relevante rondas es S = {i} \(\times\) {r′, . . . , r′ + 106} \(\times\) {1, . . . , \(\mu\)}. (Como se analizó, a medida que se acerca la ronda r′ + 106, "Actualizo" su par (PMK, SMK).) En la práctica, si \(\mu\) es lo suficientemente grande, una ronda de Algorand ′ 2 no tomará más de \(\mu\) pasos. en principio, sin embargo, existe la remota posibilidad de que, durante alguna ronda r el número de pasos realmente tomado excederá \(\mu\). Cuando esto suceda, no podría firmar su mensaje, Sr. yo para cualquier paso s > \(\mu\), porque ha preparado de antemano sólo \(\mu\) claves secretas para la ronda r. Además, él no pudo preparar y publicar un nuevo alijo de claves efímeras, como se discutió antes. De hecho, hacer por lo tanto, necesitaría insertar una nueva clave maestra pública PMK′ en un nuevo bloque. Pero, ¿debería redondearse r? Si toma más y más pasos, no se generarán nuevos bloques. Sin embargo, existen soluciones. Por ejemplo, puedo usar la última clave efímera de la ronda r, pkr,μ yo , como sigue. Genera otro alijo de pares de claves para la ronda r, por ejemplo, (1) generando otro par de claves maestras (PMK, SMK); (2) usar este par para generar otras, digamos, 106 claves efímeras, sk r,μ+1 yo , . . . , sk r,μ+106 yo , correspondiente a los pasos \(\mu\)+1, ..., \(\mu\)+106 de la ronda r; (3) usando skr,μ yo a digitalmente signo PMK (y cualquier mensaje (r, \(\mu\)) si i \(\in\)SV r,\(\mu\)), relativo a pkr,\(\mu\) yo ; y (4) borrar SMK y skr, \(\mu\) yo . ¿Debería convertirme en verificador en un paso \(\mu\) + s con s \(\in\){1, . . . , 106}, luego firmo digitalmente su (r, \(\mu\) + s)- mensaje señor, \(\mu\)+s yo en relación con su nuevo paquete de claves r,μ+s yo = (i, r, \(\mu\) + s). Por supuesto, para verificar esta firma. de i, otros deben estar seguros de que esta clave pública corresponde a la nueva clave maestra pública PMK de i. Así, además de esta firma, i transmite su firma digital de PMK en relación con pkr,μ yo . Por supuesto, este enfoque se puede repetir tantas veces como sea necesario, si se redondea r continuar ¡Para más y más pasos! La última clave secreta efímera se utiliza para autenticar un nuevo público maestro. clave y, por lo tanto, otro alijo de claves efímeras para la ronda r. Etcétera.6.3 El protocolo real Algorand ′ 2 Recuerde nuevamente que, en cada paso s de una ronda r, un verificador i \(\in\)SV r,s usa su secreto público de largo plazo. par de claves para producir su credencial, \(\sigma\)r,s yo \(\triangleq\)SIGi(r, s, Qr−1), así como SIGi qr-1 en el caso s = 1. El verificador i utiliza su par de claves efímeras (pkr,s yo, skr, s i ), para firmar cualquier otro mensaje m que pueda ser requerido. Para simplificar, escribimos esigi(m), en lugar de sigpkr,s. i (m), para denotar lo efímero propio de i firma de m en este paso y escriba ESIGi(m) en lugar de SIGpkr,s i (m) \(\triangleq\)(i, m, esigi(m)). Paso 1: bloquear la propuesta Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 1 de la ronda r tan pronto como haya CERT r−1, que permite i calcular sin ambigüedades H(Br−1) y Qr−1. • El usuario i utiliza Qr−1 para comprobar si i \(\in\)SV r,1 o no. Si i /\(\in\)SV r,1, no hace nada para el Paso 1. • Si i \(\in\)SV r,1, es decir, si i es un líder potencial, entonces hace lo siguiente. (a) Si he visto B0, . . . , Br−1 mismo (cualquier Bj = Bj ǫ se puede derivar fácilmente de su valor hash en CERT j y por lo tanto se supone "visto"), luego cobra los pagos redondos r que han se le ha propagado hasta el momento y calcula un pago máximo PAY r yo de ellos. (b) Si no he visto todo B0, . . . , Br−1 todavía, luego establece PAY r yo = \(\emptyset\). (c) A continuación, i calcula su “bloque de candidatos” Br. i = (r, PAGAR r i , SIGi(Qr−1), H(Br−1)). (c) Finalmente, i calcula el mensaje mr,1 yo = (Hermano yo , esigi(H(Br i )), \(\sigma\)r,1 i ), destruye su efímero clave secreta skr,1 i y luego propaga dos mensajes, mr,1 yo y (SIGi(Qr−1), \(\sigma\)r,1 yo), por separado pero simultáneamente.a aCuando i es el líder, SIGi(Qr−1) permite que otros calculen Qr = H(SIGi(Qr−1), r).

Propagación selectiva Para acortar la ejecución global del Paso 1 y toda la ronda, es importante que (r, 1)- Los mensajes se propagan selectivamente. Es decir, para cada usuario j en el sistema, • Para el primer mensaje (r, 1) que recibe y verifica con éxitoa, si contiene un bloque o es solo una credencial y una firma de Qr−1, el jugador j lo propaga como de costumbre. • Para todos los demás mensajes (r, 1) que el jugador j recibe y verifica con éxito, propaga solo si el valor hash de la credencial que contiene es el más pequeño entre los valores hash de las credenciales contenidas en todos los mensajes (r, 1) que ha recibido y verificado con éxito para lejos. • Sin embargo, si j recibe dos mensajes diferentes de la forma mr,1 yo del mismo jugador i,b él descarta el segundo sin importar cuál sea el valor hash de la credencial de i. Tenga en cuenta que, bajo propagación selectiva, es útil que cada líder potencial i propague su credencial \(\sigma\)r,1 yo por separado del señor 1 i :c esos pequeños mensajes viajan más rápido que los bloques, asegúrese propagación oportuna del mr,1 i es donde las credenciales contenidas tienen valores pequeños hash, mientras que hacer que aquellos con valores hash grandes desaparezcan rápidamente. aEs decir, todas las firmas son correctas y, si es de la forma mr,1 i, tanto el bloque como su hash son válidos —Aunque j no comprueba si el conjunto de pagos incluido es máximo para i o no. bLo que significa que soy malicioso. cAgradecemos a Georgios Vlachos por sugerir esto.Paso 2: El primer paso del Protocolo de Consenso Graduado GC Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 2 de la ronda r tan pronto como haya CERT r-1. • El usuario i espera un tiempo máximo t2 \(\triangleq\) \(\lambda\) + Λ. Mientras espero, actúo de la siguiente manera. 1. Después de esperar el tiempo 2\(\lambda\), encuentra al usuario \(\ell\)tal que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j) para todos credenciales \(\sigma\)r,1 j que son parte de los mensajes (r, 1) verificados con éxito que ha recibido hasta ahora.a 2. Si el tiene recibido un bloquear Br-1, cual partidos el hash valor H(Br−1) contenido en CERT r−1,b y si ha recibido de \(\ell\)un mensaje válido mr,1 \(\ell\) = (hermano \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c entonces dejo de esperar y establezco v′ yo \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. De lo contrario, cuando se acaba el tiempo t2, i establece v′ yo \(\triangleq\) \(\bot\). 4. Cuando el valor de v′ Se ha configurado i, calcula Qr−1 a partir de CERT r−1 y verifica si i \(\in\)SV r,2 o no. 5. Si i \(\in\)SV r,2, i calcula el mensaje mr,2 yo \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),d destruye su efímero clave secreta skr,2 i y luego propaga mr,2 yo. De lo contrario, me detengo sin propagarme. cualquier cosa. aEsencialmente, el usuario i decide en privado que el líder de la ronda r es el usuario \(\ell\). bPor supuesto, si CERT r−1 indica que Br−1 = Br−1 ǫ , entonces ya he “recibido” Br−1 en el momento en que él ha CERT r-1. cNuevamente, las firmas del jugador \(\ell\) y los hashes se verifican con éxito y PAGAN r \(\ell\)en Br \(\ell\)es un pago válido para round r —aunque no compruebo si PAY r \(\ell\)es máximo para \(\ell\)o no. si hermano \(\ell\)contiene un conjunto de pagos vacío, entonces en realidad no hay necesidad de que i vea Br−1 antes de verificar si Br \(\ell\)es válido o no. dEl mensaje mr,2 yo indica que el jugador i considera el primer componente de v′ i será el hash del siguiente bloque, o considera que el siguiente bloque está vacío.

Paso 3: el segundo paso de GC Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 3 de la ronda r tan pronto como haya CERT r-1. • El usuario i espera un tiempo máximo t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. Mientras espero, actúo como sigue. 1. Si existe un valor v tal que haya recibido al menos tH mensajes válidos mr,2 j de la forma (ESIGj(v), \(\sigma\)r,2 j ), sin contradicción alguna,a luego deja de esperar y pone v′ = v. 2. De lo contrario, cuando se acaba el tiempo t3, establece v′ = \(\bot\). 3. Cuando se ha establecido el valor de v′, i calcula Qr−1 a partir de CERT r−1 y verifica si i \(\in\)SV r,3 o no. 4. Si i \(\in\)SV r,3, entonces i calcula el mensaje mr,3 yo \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 i ), destruye su clave secreta efímera skr,3 i y luego propaga mr,3 yo. De lo contrario, me detengo sin propagar cualquier cosa. aEs decir, no ha recibido dos mensajes válidos que contengan ESIGj(v) y un ESIGj(ˆv) diferente respectivamente, de un jugador j. Aquí y de aquí en adelante, excepto en las Condiciones Finales que se definen más adelante, siempre que un jugador honesto quiere mensajes de una forma determinada, los mensajes que se contradicen entre sí nunca se cuentan ni se consideran válidos.

Paso 4: Salida de GC y el primer paso de BBA⋆ Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza su propio Paso 4 de la ronda r tan pronto como termina su propio Paso 3. • El usuario i espera una cantidad máxima de tiempo 2\(\lambda\).a Mientras espera, i actúa de la siguiente manera. 1. Calcula vi y gi, la salida de GC, de la siguiente manera. (a) Si existe un valor v′ ̸= \(\bot\) tal que haya recibido al menos tH mensajes válidos señor,3 j = (ESIGj(v′), \(\sigma\)r,3 j ), luego deja de esperar y establece vi \(\triangleq\)v′ y gi \(\triangleq\)2. b) Si ha recibido al menos los mensajes válidos mr,3 j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), luego se detiene esperando y establece vi \(\triangleq\) \(\bot\) y gi \(\triangleq\)0.b (c) En caso contrario, cuando se acabe el tiempo 2\(\lambda\), si existe un valor v′ ̸= \(\bot\) tal que tenga recibido al menos ⌈tH 2 ⌉mensajes válidos mr,j j = (ESIGj(v′), \(\sigma\)r,3 j ), luego establece vi \(\triangleq\)v′ y gi \(\triangleq\)1.c (d) De lo contrario, cuando se acaba el tiempo 2\(\lambda\), establece vi \(\triangleq\) \(\bot\) y gi \(\triangleq\)0. 2. Cuando se han establecido los valores vi y gi, i calcula bi, la entrada de BBA⋆, de la siguiente manera: bi \(\triangleq\)0 si gi = 2, y bi \(\triangleq\)1 en caso contrario. 3. i calcula Qr−1 a partir de CERT r−1 y comprueba si i \(\in\)SV r,4 o no. 4. Si i \(\in\)SV r,4, calcula el mensaje mr,4 yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), destruye su clave secreta efímera skr,4 i , y propaga mr,4 yo. De lo contrario, me detengo sin propagarme. cualquier cosa. aPor lo tanto, la cantidad total máxima de tiempo desde que i comienza su Paso 1 de la ronda r podría ser t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ. bEl hecho de que el paso (b) esté o no en el protocolo no afecta su exactitud. Sin embargo, la presencia del Paso (b) permite que el Paso 4 finalice en menos de 2\(\lambda\) si un número suficiente de verificadores del Paso 3 han “firmado \(\bot\)”. cSe puede demostrar que v′ en este caso, si existe, debe ser única.Paso s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: un paso de BBA⋆ con moneda fijada a 0 Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como termina su propio Paso s −1. • El usuario i espera una cantidad máxima de tiempo 2\(\lambda\).a Mientras espera, i actúa de la siguiente manera. – Condición final 0: Si en algún punto existe una cadena v ̸= \(\bot\) y un paso s′ tal que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3, es decir, el paso s′ es un paso fijo con moneda a 0, (b) he recibido al menos tH mensajes válidos mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b y (c) he recibido un mensaje válido (SIGj(Qr−1), \(\sigma\)r,1 j ) siendo j el segundo componente de v, entonces, i deja de esperar y finaliza su propia ejecución de los Pasos s (y de hecho de la ronda r) inmediatamente sin propagar nada como verificador (r, s); establece que H(Br) sea el primero componente de v; y establece su propio CERT r como el conjunto de mensajes mr,s′−1 j del paso (b) junto con (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Condición final 1: Si en algún punto existe un paso s′ tal que (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3, es decir, el paso s′ es un paso fijo con moneda a 1, y (b’) he recibido al menos tH mensajes válidos mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d entonces, i deja de esperar y finaliza su propia ejecución del Paso s (y de hecho de la ronda r) correctamente. lejos sin propagar nada como verificador (r, s); establece Br = Br ǫ ; y establece el suyo CERT r será el conjunto de mensajes mr,s′−1 j del subpaso (b’). – Si en cualquiera punto el tiene recibido en menos tH válido señor, s-1 j es de el forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), luego deja de esperar y establece bi \(\triangleq\)1. – Si en cualquiera punto el tiene recibido en menos tH válido señor, s-1 j es de el forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), pero no están de acuerdo en la misma v, entonces se detiene esperando y establece bi \(\triangleq\)0. – En caso contrario, cuando se acaba el tiempo 2\(\lambda\), i establece bi \(\triangleq\)0. – Cuando se ha establecido el valor bi, i calcula Qr−1 a partir de CERT r−1 y comprueba si i \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) siendo vi el valor que ha calculado en el Paso 4, destruye su efímera clave secreta skr,s yo, y luego propaga señor, s yo. De lo contrario, me detengo sin propagar nada. aPor lo tanto, la cantidad total máxima de tiempo desde que i comienza su Paso 1 de la ronda r podría ser ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. bDicho mensaje del jugador j se cuenta incluso si el jugador i también ha recibido un mensaje de j firmando por 1. Cosas similares para la condición final 1. Como se muestra en el análisis, esto es para garantizar que todos los usuarios honestos sepan CERT r dentro del tiempo \(\lambda\) entre sí. El usuario i ahora conoce H(Br) y sus propios acabados redondos r. Sólo necesita esperar hasta que Br esté realmente bloqueado. propagado a él, lo que puede llevar algún tiempo adicional. Todavía ayuda a propagar mensajes como usuario genérico. pero no inicia ninguna propagación como verificador (r, s). En particular, ha ayudado a difundir todos los mensajes en su CERT r, que es suficiente para nuestro protocolo. Tenga en cuenta que también debería establecer bi \(\triangleq\)0 para el protocolo BA binario, pero bi no es necesario en este caso de todos modos. Cosas similares para todas las instrucciones futuras. dEn este caso, no importa cuáles sean los vj. 65Paso s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: un paso de BBA⋆ con moneda fijada a 1 Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como termina su propio Paso s −1. • El usuario i espera un tiempo máximo de 2\(\lambda\). Mientras espero, actúo de la siguiente manera. – Condición final 0: Las mismas instrucciones que en un paso Coin-Fixed-To-0. – Condición final 1: Las mismas instrucciones que en un paso Coin-Fixed-To-0. – Si en cualquiera punto el tiene recibido en menos tH válido señor, s-1 j es de el forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), luego deja de esperar y establece bi \(\triangleq\)0.a – En caso contrario, cuando se acaba el tiempo 2\(\lambda\), i establece bi \(\triangleq\)1. – Cuando se ha establecido el valor bi, i calcula Qr−1 a partir de CERT r−1 y comprueba si i \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) siendo vi el valor que ha calculado en el Paso 4, destruye su efímera clave secreta skr,s yo, y luego propaga señor, s yo. De lo contrario, me detengo sin propagar nada. aTenga en cuenta que recibir tH mensajes válidos (r, s −1) firmados para 1 significaría la Condición Final 1. Paso s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: un paso de BBA⋆ genuinamente lanzado al aire Instrucciones para cada usuario i \(\in\)PKr−k: El usuario i comienza sus propios Pasos de la ronda r tan pronto como termina su propio paso s −1. • El usuario i espera un tiempo máximo de 2\(\lambda\). Mientras espero, actúo de la siguiente manera. – Condición final 0: Las mismas instrucciones que en un paso Coin-Fixed-To-0. – Condición final 1: Las mismas instrucciones que en un paso Coin-Fixed-To-0. – Si en cualquiera punto el tiene recibido en menos tH válido señor, s-1 j es de el forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), luego deja de esperar y establece bi \(\triangleq\)0. – Si en cualquiera punto el tiene recibido en menos tH válido señor, s-1 j es de el forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), luego deja de esperar y establece bi \(\triangleq\)1. – De lo contrario, cuando se acabe el tiempo 2\(\lambda\), dejar que SV r,s−1 yo ser el conjunto de (r, s −1)-verificadores de a quien ha recibido un mensaje válido mr,s−1 j , i establece bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 yo H(\(\sigma\)r,s−1 j )). – Cuando se ha establecido el valor bi, i calcula Qr−1 a partir de CERT r−1 y comprueba si i \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcula el mensaje mr,s yo \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) siendo vi el valor que ha calculado en el Paso 4, destruye su efímera clave secreta skr,s yo, y luego propaga señor, s yo. De lo contrario, me detengo sin propagar nada. Observación. En principio, como se considera en la subsección 6.2, el protocolo puede tomar arbitrariamente muchos pasos en alguna ronda. Si esto sucede, como se discutió, un usuario i \(\in\)SV r,s con s > \(\mu\) ha agotado

su alijo de claves efímeras pregeneradas y tiene que autenticar su mensaje (r, s) mr,s yo por un “cascada” de claves efímeras. Por lo tanto, el mensaje se vuelve un poco más largo y la transmisión de estos es más larga. Los mensajes tardarán un poco más. En consecuencia, después de tantos pasos de una ronda determinada, el valor de el parámetro \(\lambda\) aumentará ligeramente automáticamente. (Pero vuelve al \(\lambda\) original una vez que se introduce un nuevo Se produce un bloque y comienza una nueva ronda.) Reconstrucción del bloque Round-r por parte de no verificadores Instrucciones para cada usuario i en el sistema: El usuario i comienza su propia ronda r tan pronto como haya CERT r-1. • Sigo las instrucciones de cada paso del protocolo, participo en la propagación de todos. mensajes, pero no inicia ninguna propagación en un paso si no es un verificador en el mismo. • i termina su propia ronda r ingresando ya sea la Condición Final 0 o la Condición Final 1 en alguna paso, con el correspondiente CERT r. • A partir de ahí, comienza su ronda r + 1 mientras espera recibir el bloque Br real (a menos que ya lo recibió), cuyo hash H(Br) ha sido fijado por CERT r. De nuevo, si CERT r indica que Br = Br ǫ, i conoce a Br en el momento en que tiene CERT r. 6.4 Análisis de Algorand ′ 2 El análisis de Algorand ′ 2 se deriva fácilmente del de Algorand ′ 1. Esencialmente, en Algorand ′ 2, con probabilidad abrumadora, (a) todos los usuarios honestos están de acuerdo en el mismo bloque Br; el líder de un nuevo El bloque es honesto con probabilidad al menos ph = h2(1 + h −h2).

Manejo de usuarios honestos sin conexión

Como decíamos, un usuario honesto sigue todas las instrucciones prescritas, entre las que se incluye la de estar en línea. y ejecutar el protocolo. Esto no es una carga importante en Algorand, ya que el cálculo y El ancho de banda requerido por un usuario honesto es bastante modesto. Sin embargo, señalemos que Algorand puede modificarse fácilmente para que funcione en dos modelos, en los que los usuarios honestos pueden estar desconectados en grandes números. Antes de discutir estos dos modelos, señalemos que, si el porcentaje de jugadores honestos fueran 95%, Algorand aún podría ejecutarse configurando todos los parámetros asumiendo que h = 80%. En consecuencia, Algorand continuaría funcionando correctamente incluso si como máximo la mitad de los jugadores honestos decidió desconectarse (de hecho, un caso importante de “absentismo”). De hecho, en cualquier momento, al menos El 80% de los jugadores online serían honestos. De la participación continua a la honestidad perezosa Como vimos, Algorand ′ 1 y Algorand ′ 2 elegir el parámetro retrospectivo k. Demostremos ahora que elegir k adecuadamente grande permite eliminar el requisito de Participación Continua. Este requisito garantiza una propiedad crucial: a saber, que el protocolo BA subyacente BBA⋆tiene una mayoría honesta adecuada. Expliquemos ahora lo perezoso La honestidad proporciona una forma alternativa y atractiva de satisfacer esta propiedad.

Recuerde que un usuario i es vago pero honesto si (1) sigue todas las instrucciones prescritas, cuando se le pide que participe en el protocolo, y (2) se le pide que participe únicamente en el protocolo muy raramente —por ejemplo, una vez a la semana— con un aviso previo adecuado y potencialmente recibiendo recompensas cuando participa. Para permitir que Algorand trabaje con dichos reproductores, basta con “elegir los verificadores del ronda actual entre los usuarios que ya están en el sistema en una ronda mucho anterior”. En efecto, recuerda que los verificadores para una ronda r se eligen entre los usuarios de la ronda r −k, y las selecciones se realizan en función sobre la cantidad Qr−1. Tenga en cuenta que una semana consta de aproximadamente 10.000 minutos y suponga que un Una ronda dura aproximadamente (por ejemplo, en promedio) 5 minutos, por lo que una semana tiene aproximadamente 2000 rondas. asumir que, en algún momento, un usuario desea planificar su tiempo y saber si va a estar un verificador en la próxima semana. El protocolo ahora elige los verificadores para una ronda r entre los usuarios en redondee r −k −2, 000, y las selecciones se basan en Qr−2,001. En la ronda r, el jugador que ya conozco los valores Qr−2.000, . . . , Qr−1, ya que en realidad son parte de blockchain. Entonces, para cada M entre 1 y 2000, i es un verificador en un paso s de la ronda r + M si y sólo si .H SIGi r + M, s, Qr+M−2,001 \(\leq\)p. Así, para comprobar si va a ser llamado a actuar como verificador en las próximas 2.000 rondas, debo calcular \(\sigma\)M,s yo = SIGi r + M, s, Qr+M−2,001 para M = 1 a 2, 000 y para cada paso s, y verifique si .H(\(\sigma\)M,s yo ) \(\leq\)p para algunos de ellos. Si calcular una firma digital toma un milisegundo, entonces Toda esta operación le llevará aproximadamente 1 minuto de cálculo. Si no es seleccionado como verificador En cualquiera de estas rondas, entonces puede desconectarse con una “conciencia honesta”. ¿Había estado continuamente hubiera participado, ¡básicamente habría dado 0 pasos en las siguientes 2000 rondas de todos modos! Si, en cambio, es seleccionado para ser verificador en una de estas rondas, luego se prepara (por ejemplo, obteniendo todos la información necesaria) para actuar como un verificador honesto en la ronda adecuada. Al actuar así, un verificador potencial perezoso pero honesto sólo deja de participar en la propagación. de mensajes. Pero la propagación de mensajes suele ser sólida. Además, los pagadores y los beneficiarios de Se espera que los pagos propagados recientemente estén en línea para observar qué sucede con sus pagos. y así participarán en la propagación del mensaje, si son honestos.

Protocolo Algorand ′ con Mayoría Honesta de Dinero

Ahora, finalmente, mostramos cómo reemplazar el supuesto de la Mayoría Honesta de Usuarios con el supuesto mucho más Suposición significativa de Mayoría Honesta del Dinero. La idea básica es (en formato proof-of-stake) “seleccionar un usuario i \(\in\)PKr−k para que pertenezca a SV r,s con un peso (es decir, poder de decisión) proporcional a la cantidad de dinero que posee yo.”24 Según nuestra suposición HMM, podemos elegir si esa cantidad debe poseerse en la ronda r −k o al (inicio de) la ronda r. Suponiendo que no nos importe la participación continua, optamos por la última elección. (Para eliminar la participación continua, habríamos optado por la primera opción. Mejor dicho, por la cantidad de dinero que se posee en la ronda r −k −2, 000.) Hay muchas maneras de implementar esta idea. La forma más sencilla sería mantener cada tecla como máximo 1 unidad de dinero y luego seleccionar al azar n usuarios i de PKr−k tal que a(r) yo = 1. 24Deberíamos decir PKr−k−2.000 para reemplazar la participación continua. Por simplicidad, ya que uno puede desear requerir participación continua de todos modos, usamos PKr−k como antes, para llevar un parámetro menos.

La siguiente implementación más simple La siguiente implementación más simple puede ser exigir que cada clave pública posea una cantidad máxima de dinero M, para algún M fijo. El valor M es lo suficientemente pequeño en comparación con la cantidad total de dinero en el sistema, de modo que la probabilidad de que una clave pertenezca al conjunto de verificador de más de un el paso en —digamos— k rondas es insignificante. Entonces, una clave i \(\in\)PKr−k, poseer una cantidad de dinero a(r) yo en la ronda r, se elige que pertenezca a SV r,s si .H SIGi r, s, Qr−1 \(\leq\)p \(\cdot\) a(r) yo m . Y todo continúa como antes. Una implementación más compleja La última implementación "obligó a un participante rico en el sistema a poseer muchas claves". Una implementación alternativa, que se describe a continuación, generaliza la noción de estatus y considera cada usuario i constará de K + 1 copias (i, v), cada una de las cuales se selecciona independientemente para ser un verificador, y será dueño de su propia llave efímera (pkr,s i,v, skr,s i,v) en un paso s de una ronda r. El valor K depende sobre la cantidad de dinero a(r) yo propiedad de i en la ronda r. Veamos ahora con mayor detalle cómo funciona dicho sistema. Número de copias Sea n la cardinalidad esperada objetivo de cada conjunto de verificadores, y sea a(r) yo Sea la cantidad de dinero que posee un usuario i en la ronda r. Sea Ar la cantidad total de dinero que se posee por los usuarios en PKr−k en la ronda r, es decir, ar = x i\(\in\)PKr−k un(r) yo. Si i es un usuario en PKr−k, entonces las copias de i son (i, 1), . . . , (yo, K + 1), donde k = $ n \(\cdot\) a(r) yo ar % . Ejemplo. Sea n = 1.000, Ar = 109 y a(r) yo = 3,7 millones. Entonces, k = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3.7⌋= 3 . Verificadores y Credenciales Sea yo un usuario en PKr−k con K + 1 copias. Para cada v = 1, . . . , K, copia (i, v) pertenece automáticamente a SV r,s. Es decir, mi credencial es \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), pero la condición correspondiente pasa a ser .H(\(\sigma\)r,s i,v) \(\leq\)1, que es siempre cierto. Para la copia (i, K + 1), para cada paso s de la ronda r, i verifica si .H SIGi (yo, K + 1), r, s, Qr−1 \(\leq\)a(r) yo norte Ar-K.

Si es así, la copia (i, K + 1) pertenece a SV r,s. Para probarlo, propago la credencial. \(\sigma\)r,1 i,K+1 = SIGi (yo, K + 1), r, s, Qr−1 . Ejemplo. Como en el ejemplo anterior, sea n = 1K, a(r) yo = 3,7M, Ar = 1B, y i tiene 4 copias: (i, 1), . . . , (yo, 4). Entonces, las primeras 3 copias pertenecen a SV r,s automáticamente. Para el cuarto, conceptualmente, Algorand ′ lanza de forma independiente una moneda sesgada, cuya probabilidad de obtener Cara es 0,7. Copiar (i, 4) se selecciona si y sólo si el lanzamiento de la moneda es Cara. (Por supuesto, este lanzamiento de moneda sesgado se implementa hashing, firmando y comparando, como Lo he hecho todo el tiempo en este artículo, para permitirme probar su resultado.) Negocios como siempre Habiendo explicado cómo se seleccionan los verificadores y cómo se obtienen sus credenciales. Calculado en cada paso de una ronda r, la ejecución de una ronda es similar a la ya explicada.

Manejo de bifurcaciones

Habiendo reducido la probabilidad de bifurcaciones a 10−12 o 10−18, es prácticamente innecesario manejar ellos en la remota posibilidad de que ocurran. Algorand, sin embargo, también puede emplear varias bifurcaciones. Procedimientos de resolución, con o sin constancia de trabajo. Una forma posible de indicar a los usuarios que resuelvan las bifurcaciones es la siguiente: • Siga la cadena más larga si un usuario ve varias cadenas. • Si hay más de una cadena más larga, siga aquella que tenga un bloque no vacío al final. si Todos tienen bloques vacíos al final, considere sus penúltimos bloques. • Si hay más de una cadena más larga con bloques no vacíos al final, digamos que las cadenas son de longitud r, siga aquel cuyo líder del bloque r tenga la credencial más pequeña. Si hay vínculos, siga aquel cuyo bloque r tenga el valor hash más pequeño. Si todavía hay empates, siga las aquel cuyo bloque r está ordenado lexicográficamente como el primero.

Manejo de particiones de red

Como se dijo, asumimos que los tiempos de propagación de los mensajes entre todos los usuarios de la red están limitados por \(\lambda\) y Λ. Esta no es una suposición sólida, ya que la Internet actual es rápida y sólida, y los valores reales de estos parámetros son bastante razonables. Aquí, señalemos que Algorand ′ 2 continúa funcionando incluso si Internet ocasionalmente se divide en dos partes. El caso cuando Internet está dividida en más de dos partes. 10.1 Particiones Físicas En primer lugar, la partición puede deberse a motivos físicos. Por ejemplo, un gran terremoto puede terminarán por romper por completo la conexión entre Europa y América. En este caso, el Los usuarios malintencionados también están particionados y no hay comunicación entre las dos partes. Así

Habrá dos Adversarios, uno para la parte 1 y el otro para la parte 2. Cada Adversario todavía intenta romper el protocolo por su parte. Supongamos que la partición ocurre en medio de la ronda r. Entonces cada usuario sigue siendo seleccionado como verificador basado en PKr−k, con la misma probabilidad que antes. Sea HSV r,s yo y MSV r,s yo respectivamente sea el conjunto de verificadores honestos y maliciosos en un paso s en la parte i \(\in\){1, 2}. tenemos |VHS r,s 1 | + |MSV r,s 1 | + |VHS r,s 2 | + |MSV r,s 2 | = |VHS r,s| + |MSV r,s|. Tenga en cuenta que |HSV r,s| + |MSV r,s| < |VHS r,s| + 2|MSV r,s| < 2tH con una probabilidad abrumadora. Si alguna parte i tiene |HSV r,s yo | + |MSV r,s yo | \(\geq\)tH con probabilidad no despreciable, por ejemplo, 1%, entonces el probabilidad de que |HSV r,s 3-i| + |MSV r,s 3-i| \(\geq\)tH es muy bajo, por ejemplo, 10−16 cuando F = 10−18. En este caso, también podemos tratar la parte más pequeña como si estuviera fuera de línea, porque no habrá suficientes verificadores en esta parte para generar firmas tH para certificar un bloque. Consideremos la parte más amplia, digamos la parte 1, sin pérdida de generalidad. Aunque |HSV r,s| < tH con probabilidad insignificante en cada paso s, cuando la red está particionada, |HSV r,s 1 | puede ser menor que tH con alguna probabilidad no despreciable. En este caso el adversario podrá, con alguna otra probabilidad no despreciable, fuerce el protocolo binario BA en una bifurcación en la ronda r, con un bloque no vacío Br y el bloque vacío Br ǫ ambos con tH firmas válidas.25 Por ejemplo, en un Pasos Coin-Fixed-To-0, todos los verificadores en HSV r,s 1 firmó para el bit 0 y H(Br), y propagó sus mensajes. Todos los verificadores en MSV r,s 1 También firmaron 0 y H(Br), pero retuvieron sus mensajes. porque |VHS r,s 1 | + |MSV r,s 1 | \(\geq\)tH, el sistema tiene suficientes firmas para certificar al Hno. Sin embargo, desde el Los verificadores maliciosos retienen sus firmas, los usuarios ingresan al paso s + 1, que es un paso Coin-Fixed-To1. Porque |HSV r,s 1 | < tH debido a la partición, los verificadores en HSV r,s+1 1 no lo vi firmas para el bit 0 y todos firmaron para el bit 1. Todos los verificadores en MSV r,s+1 1 hizo lo mismo. porque |VHS r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH, el sistema tiene suficientes firmas para certificar a Br ǫ. El adversario luego crea una bifurcación liberando las firmas de MSV r,s 1 para 0 y H(Br). En consecuencia, habrá dos Qr, definidas por los bloques correspondientes de la ronda r. Sin embargo, la bifurcación no continuará y sólo una de las dos ramas podrá crecer en la ronda r + 1. Instrucciones adicionales para Algorand ′ 2. Al ver un bloque Br no vacío y el bloque vacío bloque Br ǫ , sigue al no vacío (y el Qr definido por él). De hecho, al indicar a los usuarios que utilicen el bloque no vacío en el protocolo, si una gran cantidad cantidad de usuarios honestos en PKr+1−k se dan cuenta de que hay una bifurcación al comienzo de la ronda r +1, entonces la El bloque vacío no tendrá suficientes seguidores y no crecerá. Supongamos que el adversario logra dividir a los usuarios honestos para que algunos usuarios honestos vean Br (y quizás Br ǫ), y algunos sólo ven hermano ǫ. Debido a que el Adversario no puede decir cuál de ellos será un verificador siguiendo a Br y cuál será un verificador siguiendo al Hno. ǫ , los usuarios honestos se dividen aleatoriamente y cada uno de ellos sigue se convierte en un verificador (ya sea con respecto a Br o con respecto a Br ǫ) en un paso s > 1 con probabilidad pág. Para los usuarios maliciosos, cada uno de ellos puede tener dos oportunidades de convertirse en verificador, una con Br y el otro con Br ǫ, cada uno con probabilidad p de forma independiente. Sea HSV r+1,s 1;Br sea el conjunto de verificadores honestos en el paso s de la ronda r+1 después de Br. Otras notaciones como HSV r+1,s 1;Brǫ , MSV r+1,s 1;Br y MSV r+1,s 1;Brǫ se definen de manera similar. Por Chernoffbound, es fácil 25No es posible tener una bifurcación con dos bloques no vacíos con o sin particiones, excepto con cantidades insignificantes. probabilidad.para ver que con abrumadora probabilidad, |VHS r+1,s 1;Br | + |VHS r+1,s 1;Brǫ | + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Brǫ | < 2tH. En consecuencia, las dos sucursales no pueden tener las firmas adecuadas que certifiquen un bloque para la ronda. r + 1 en el mismo paso s. Además, dado que las probabilidades de selección para dos pasos s y s′ son las iguales y las selecciones son independientes, también con una probabilidad abrumadora |VHS r+1,s 1;Br | + |MSV r+1,s 1;Br | + |VHS r+1,s′ 1;Brǫ | + |MSV r+1,s′ 1;Brǫ | < 2tH, para dos pasos cualesquiera s y s′. Cuando F = 10−18, por unión ligada, siempre y cuando el Adversario no pueda particionar a los usuarios honestos durante mucho tiempo (digamos 104 pasos, que son más de 55 horas con \(\lambda\) = 10 segundos26), con alta probabilidad (digamos 1−10−10) como máximo una rama tendrá las firmas adecuadas para certificar un bloque en la ronda r + 1. Finalmente, si la partición física ha creado dos partes con aproximadamente el mismo tamaño, entonces la probabilidad de que |HSV r,s yo | + |MSV r,s yo | \(\geq\)tH es pequeño para cada parte i. Tras un análisis similar, incluso si el Adversario logra crear una bifurcación con alguna probabilidad no despreciable en cada parte para la ronda r, como máximo una de las cuatro ramas puede crecer en la ronda r + 1. 10.2 Partición adversaria En segundo lugar, la partición puede ser causada por el Adversario, de modo que los mensajes propagados por los usuarios honestos en una parte no llegará directamente a los usuarios honestos de la otra parte, pero el Adversario puede reenviar mensajes entre las dos partes. Aún así, una vez que un mensaje de uno parte llega a un usuario honesto en la otra parte, se propagará en esta última como de costumbre. si el El adversario está dispuesto a gastar mucho dinero, es posible que pueda hackear el Internet y particionarlo así por un tiempo. El análisis es similar al de la parte más grande de la partición física anterior (la más pequeña parte se puede considerar que tiene población 0): el Adversario puede ser capaz de crear una bifurcación y cada usuario honesto sólo ve una de las ramas, pero como máximo una rama puede crecer. 10.3 Particiones de red en suma Aunque pueden ocurrir particiones de red y puede ocurrir una bifurcación en una ronda debajo de las particiones, No hay ninguna ambigüedad persistente: una bifurcación dura muy poco y, de hecho, dura como máximo una ronda. en todas las partes de la partición excepto como máximo una, los usuarios no pueden generar un nuevo bloque y, por lo tanto, (a) darse cuenta de que hay una partición en la red y (b) nunca confiar en bloques que "desaparecerán". Agradecimientos En primer lugar, nos gustaría agradecer a Sergey Gorbunov, coautor del citado sistema Democoin. Nuestro más sincero agradecimiento a Maurice Herlihy por muchas discusiones esclarecedoras, por señalar señaló que la canalización mejorará el rendimiento de Algorand y mejorará en gran medida el 26 Tenga en cuenta que un usuario finaliza un paso s sin esperar 2\(\lambda\) tiempo sólo si ha visto al menos tH firmas para el mismo mensaje. Cuando no hay suficientes firmas, cada paso durará 2\(\lambda\).

exposición de una versión anterior de este artículo. Muchas gracias a Sergio Rajsbaum, por sus comentarios sobre una versión anterior de este documento. Muchas gracias a Vinod Vaikuntanathan por varias discusiones profundas. y percepciones. Muchas gracias a Yossi Gilad, Rotem Hamo, Georgios Vlachos y Nickolai Zeldovich. por comenzar a probar estas ideas y por muchos comentarios y discusiones útiles. Silvio Micali quisiera agradecer personalmente a Ron Rivest por innumerables debates y orientación. en investigación criptográfica durante más de 3 décadas, por ser coautor del citado sistema de micropagos que ha inspirado uno de los mecanismos de selección de verificadores de Algorand. Esperamos llevar esta tecnología al siguiente nivel. Mientras tanto el viaje y el compañerismo Son muy divertidos, por lo que estamos muy agradecidos.