Introdución
"A xeración de números aleatorios é demasiado importante para deixala ao azar".
Robert Cavue, 1970
Este artigo está dedicado á aplicación práctica de solucións que utilizan a xeración de números aleatorios colectivos nun ambiente non fiable. En resumo, como e por que se usa o aleatorio nas cadeas de bloques e un pouco sobre como distinguir "bo" aleatorio de "malo". Xerar un número verdadeiramente aleatorio é un problema extremadamente difícil, mesmo nun só ordenador, e foi estudado por criptógrafos durante moito tempo. Ben, nas redes descentralizadas, a xeración de números aleatorios é aínda máis complexa e importante.
É nas redes onde os participantes non confían uns nos outros onde a capacidade de xerar un número aleatorio indiscutible permítenos resolver eficazmente moitos problemas críticos e mellorar significativamente os esquemas existentes. Ademais, os xogos de azar e as loterías non son o obxectivo número un aquí, como pode parecer nun principio ao lector inexperto.
Xeración de números aleatorios
Os ordenadores non poden xerar números aleatorios por si mesmos; precisan axuda externa para facelo. O ordenador pode obter algún valor aleatorio utilizando, por exemplo, os movementos do rato, a cantidade de memoria utilizada, as correntes erradas nos pinos do procesador e moitas outras fontes chamadas fontes de entropía. Estes valores non son completamente aleatorios, xa que están nun intervalo determinado ou teñen un patrón de cambios previsible. Para converter tales números nun número verdadeiramente aleatorio dentro dun intervalo determinado, aplícanselles criptotransformacións para producir valores pseudoaleatorios distribuídos uniformemente a partir dos valores distribuídos de forma desigual da fonte de entropía. Os valores resultantes chámanse pseudoaleatorios porque non son verdadeiramente aleatorios, senón que se derivan de forma determinista da entropía. Calquera bo algoritmo criptográfico, ao cifrar datos, produce textos cifrados que deberían ser estatisticamente indistinguibles dunha secuencia aleatoria, polo que para producir aleatoriedade pódese tomar unha fonte de entropía, que só proporciona unha boa non-repetibilidade e imprevisibilidade dos valores mesmo en intervalos pequenos. , o resto do traballo é dispersar e mesturar bits en O valor resultante será asumido polo algoritmo de cifrado.
Para completar un breve programa educativo, engadirei que xerar números aleatorios mesmo nun dispositivo é un dos piares para garantir a seguridade dos nosos datos. Os números pseudoaleatorios xerados utilízanse cando se establecen conexións seguras en varias redes, para xerar claves criptográficas, para equilibrar a carga, monitorizar a integridade e para moitas máis aplicacións. A seguridade de moitos protocolos depende da capacidade de xerar un aleatorio fiable e imprevisible externamente, almacenalo e non revelalo ata o seguinte paso do protocolo, se non, a seguridade ficará comprometida. Un ataque a un xerador de valores pseudoaleatorios é extremadamente perigoso e ameaza inmediatamente todo o software que utiliza a xeración aleatoria.
Deberías saber todo isto se fixeches un curso básico de criptografía, así que sigamos coas redes descentralizadas.
Aleatorio en blockchains
En primeiro lugar, falarei das cadeas de bloques con soporte para contratos intelixentes; son as que poden aproveitar plenamente as oportunidades que ofrece unha aleatoriedade innegable e de alta calidade. Ademais, para brevidade, chamarei a esta tecnoloxía "Balizas aleatorias verificables publicamente” ou PVRB. Dado que as cadeas de bloques son redes nas que calquera participante pode verificar a información, a parte clave do nome é "Verificable públicamente", é dicir. Calquera persoa pode usar cálculos para obter a proba de que o número resultante publicado na cadea de bloques ten as seguintes propiedades:
- O resultado debe ter unha distribución probabelmente uniforme, é dicir, basearse nunha criptografía probabelmente forte.
- Non é posible controlar ningún dos bits do resultado. Como consecuencia, o resultado non se pode prever con antelación.
- Non pode sabotear o protocolo de xeración non participando no protocolo ou sobrecargando a rede con mensaxes de ataque
- Todo o anterior debe ser resistente á connivencia dun número permitido de participantes de protocolo deshonestos (por exemplo, 1/3 dos participantes).
Calquera posibilidade de que un grupo menor de participantes en connivencia produza incluso un aleatorio par/impar controlado é un buraco de seguridade. Calquera capacidade do grupo para deter a emisión de aleatorias é un buraco de seguridade. En xeral, hai moitos problemas, e esta tarefa non é fácil...
Parece que a aplicación máis importante para PVRB son varios xogos, loterías e, en xeral, calquera tipo de xogo na cadea de bloques. De feito, esta é unha dirección importante, pero a aleatoriedade nas cadeas de bloques ten aplicacións aínda máis importantes. Mirámolos.
Algoritmos de consenso
PVRB xoga un papel importante na organización do consenso da rede. As transaccións en cadeas de bloques están protexidas por unha sinatura electrónica, polo que un "ataque a unha transacción" é sempre a inclusión/exclusión dunha transacción nun bloque (ou varios bloques). E a principal tarefa do algoritmo de consenso é acordar a orde destas transaccións e a orde dos bloques que inclúen estas transaccións. Ademais, unha propiedade necesaria para as cadeas de bloques reais é a finalidade: a capacidade da rede para aceptar que a cadea ata o bloque finalizado é definitiva e nunca se excluirá debido á aparición dunha nova bifurcación. Normalmente, para acordar que un bloque é válido e, o máis importante, definitivo, é necesario recoller sinaturas da maioría dos produtores de bloques (en diante denominados BP - block-producers), o que require polo menos entregar a cadea de bloques. a todos os BP e distribuíndo sinaturas entre todos os BP. A medida que crece o número de BPs, o número de mensaxes necesarias na rede medra exponencialmente, polo tanto, os algoritmos de consenso que requiren finalidade, empregados por exemplo no consenso pBFT de Hyperledger, non funcionan á velocidade requirida, a partir de varias ducias de BPs, requirindo un gran número de conexións.
Se hai un PVRB innegable e honesto na rede, entón, mesmo na aproximación máis simple, pódese escoller un dos produtores de bloques en función del e nomealo como "líder" durante unha rolda do protocolo. Se temos N produtores de bloques, dos cales M: M > 1/2 N son honestos, non censuran transaccións e non bifurcan a cadea para levar a cabo un ataque de "dobre gasto", entón usar un PVRB non cuestionado distribuído uniformemente permitirá escoller un líder honesto con probabilidade M / N (M / N > 1/2). Se a cada líder se lle asigna o seu propio intervalo de tempo durante o cal pode producir un bloque e validar a cadea, e estes intervalos son iguais no tempo, entón a cadea de bloques de BP honestos será máis longa que a cadea formada por BPs maliciosos e o consenso. O algoritmo depende da lonxitude da cadea, simplemente descartará o "malo". Este principio de asignar porcións de tempo iguais a cada BP aplicouse por primeira vez en Graphene (o predecesor de EOS), e permite que a maioría dos bloques se pechen cunha única sinatura, o que reduce moito a carga da rede e permite que este consenso funcione de forma extremadamente rápida e rápida. constantemente. Non obstante, a rede EOS agora ten que usar bloques especiais (Último bloque irreversible), que están confirmados polas sinaturas de 2/3 BP. Estes bloques serven para garantir a finalidade (a imposibilidade de que unha bifurcación de cadea comece antes do último Último Bloque Irreversible).
Ademais, nas implementacións reais, o esquema do protocolo é máis complicado: a votación dos bloques propostos realízase en varias etapas para manter a rede en caso de faltar bloques e problemas coa rede, pero aínda tendo isto en conta, os algoritmos de consenso que usan PVRB requiren significativamente menos mensaxes entre BPs, o que permite facelos máis rápidos que os PVFT tradicionales ou as súas diversas modificacións.
O representante máis destacado deste tipo de algoritmos: do equipo Cardano, que se di que é matematicamente demostrable contra a connivencia de BP.
En Ouroboros, PVRB utilízase para definir o chamado "programa BP" - un horario segundo o cal a cada BP se lle asigna a súa propia franxa horaria para publicar un bloque. A gran vantaxe de usar PVRB é a completa "igualdade" dos BPs (segundo o tamaño dos seus balances). A integridade do PVRB garante que os BP maliciosos non poidan controlar a programación das franxas horarias e, polo tanto, non poidan manipular a cadea preparando e analizando as bifurcacións da cadea con antelación, e para seleccionar unha bifurcación é suficiente con simplemente confiar na lonxitude da cadea. cadea, sen usar formas complicadas de calcular a "utilidade" de BP e o "peso" dos seus bloques.
En xeral, en todos os casos nos que hai que escoller un participante aleatorio nunha rede descentralizada, PVRB é case sempre a mellor opción, en lugar dunha opción determinista baseada, por exemplo, nun bloque hash. Sen PVRB, a capacidade de influír na elección dun participante leva a ataques nos que o atacante pode escoller entre varios futuros para escoller o seguinte participante corrupto ou varios á vez para garantir unha maior participación na decisión. O uso de PVRB desacredita este tipo de ataques.
Escalado e equilibrio de carga
PVRB tamén pode ser de gran vantaxe en tarefas como a redución de carga e a escala de pagos. Para comezar, ten sentido familiarizarse Rivesta “Lotería electrónica como micropagos”. A idea xeral é que en lugar de facer 100 pagos 1c do pagador ao destinatario, pode xogar unha lotería honesta cun premio de 1$ = 100c, onde o pagador dá ao banco un dos 1 dos seus "billets de lotería" por cada un. 100c pago. Un destes billetes gaña un bote de $ 1, e é este billete o que o destinatario pode gravar na cadea de bloques. O máis importante é que os 99 billetes restantes transfiran entre o destinatario e o pagador sen ningunha participación externa, a través dunha canle privada e á velocidade desexada. Pódese ler unha boa descrición do protocolo baseado neste esquema na rede Emercoin .
Este esquema ten algúns problemas, como que o destinatario pode deixar de servir ao pagador inmediatamente despois de recibir un boleto gañador, pero para moitas aplicacións especiais, como a facturación por minuto ou as subscricións electrónicas a servizos, pódense descoidar. O principal requisito, por suposto, é a integridade da lotería, e para a súa implementación é absolutamente necesario un PVRB.
A elección dun participante aleatorio tamén é moi importante para os protocolos de fragmentación, cuxo propósito é escalar horizontalmente a cadea de bloques, permitindo que diferentes BP procesen só o seu alcance de transaccións. Esta é unha tarefa extremadamente difícil, especialmente en termos de seguridade ao combinar fragmentos. A selección xusta dun BP aleatorio co propósito de asignar os responsables dun fragmento específico, como nos algoritmos de consenso, tamén é tarefa do PVRB. Nos sistemas centralizados, os fragmentos son asignados por un equilibrador; simplemente calcula o hash da solicitude e envíao ao executor necesario. Nas cadeas de bloques, a capacidade de influír nesta asignación pode levar a un ataque ao consenso. Por exemplo, o contido das transaccións pode ser controlado por un atacante, pode controlar que transaccións van ao fragmento que controla e manipular a cadea de bloques nel. Podes ler unha discusión sobre o problema do uso de números aleatorios para tarefas de fragmentación en Ethereum
Sharding é un dos problemas máis ambiciosos e graves no campo da cadea de bloques; a súa solución permitirá construír redes descentralizadas de rendemento e volume fantásticos. PVRB é só un dos bloques importantes para resolvelo.
Xogos, protocolos económicos, arbitraxe
O papel dos números aleatorios na industria dos xogos é difícil de sobreestimar. O uso explícito nos casinos en liña e o uso implícito ao calcular os efectos da acción dun xogador son problemas extremadamente difíciles para as redes descentralizadas, onde non hai forma de confiar nunha fonte central de aleatoriedade. Pero a selección aleatoria tamén pode resolver moitos problemas económicos e axudar a construír protocolos máis sinxelos e eficientes. Supoñamos que no noso protocolo hai disputas sobre o pago dalgúns servizos económicos, e estas disputas ocorren moi raramente. Neste caso, se hai un PVRB indiscutible, os clientes e vendedores poden acordar resolver as disputas de forma aleatoria, pero cunha probabilidade determinada. Por exemplo, cun 60% de probabilidade gañe o cliente e cun 40% de probabilidade de que gañe o vendedor. Este enfoque, absurdo desde o primeiro punto de vista, permite resolver automaticamente as disputas cunha cota de gañas/perdas precisamente previsible, que convén a ambas as partes sen ningunha participación de terceiros e unha perda de tempo innecesaria. Ademais, a razón de probabilidade pode ser dinámica e depender dalgunhas variables globais. Por exemplo, se unha empresa vai ben, ten un número baixo de disputas e unha alta rendibilidade, a empresa pode cambiar automaticamente a probabilidade de resolver unha disputa cara a centrarse no cliente, por exemplo 70/30 ou 80/20, e viceversa, se as disputas levan moito diñeiro e son fraudulentas ou inadecuadas, pode cambiar a probabilidade na outra dirección.
Un gran número de protocolos descentralizados interesantes, como rexistros curados por tokens, mercados de predicións, curvas de enlace e moitos outros, son xogos económicos nos que se premia o bo comportamento e se penaliza o mal comportamento. Moitas veces conteñen problemas de seguridade polos que as proteccións entran en conflito entre si. O que está protexido dun ataque de "baleas" con miles de millóns de fichas ("gran aposta") é vulnerable aos ataques de miles de contas con pequenos saldos ("partica de sibilo") e ás medidas tomadas contra un só ataque, como non As tarifas lineais creadas para facer que o traballo cunha gran participación sexa pouco rendible adoitan ser desacreditadas por outro ataque. Xa que estamos a falar dun xogo económico, pódense calcular previamente os correspondentes pesos estatísticos, e simplemente substituír as comisións por outras aleatorias coa distribución axeitada. Tales comisións probabilísticas impléntanse de forma extremadamente sinxela se a cadea de bloques ten unha fonte fiable de aleatoriedade e non requiren cálculos complexos, o que dificulta a vida tanto das baleas como das sibilas.
Ao mesmo tempo, é necesario seguir lembrando que o control dun só bit nesta aleatoriedade permite facer trampas, reducindo e aumentando as probabilidades á metade, polo que un PVRB honesto é o compoñente máis importante deste tipo de protocolos.
Onde atopar o azar correcto?
En teoría, a selección aleatoria xusta en redes descentralizadas fai que case calquera protocolo sexa probabelmente seguro contra a connivencia. A razón é bastante sinxela: se a rede está de acordo nun único bit 0 ou 1 e menos da metade dos participantes son deshonestos, entón, dadas suficientes iteracións, a rede está garantida para chegar a un consenso sobre ese bit cunha probabilidade fixa. Simplemente porque un aleatorio honesto escollerá 51 de 100 participantes o 51% do tempo. Pero isto é en teoría, porque... nas redes reais, para garantir tal nivel de seguridade como nos artigos, requírense moitas mensaxes entre hosts, criptografía complexa multipaso e calquera complicación do protocolo engade de inmediato novos vectores de ataque.
É por iso que aínda non vemos un PVRB resistente probado nas cadeas de bloques, que se tería empregado durante o tempo suficiente para ser probado por aplicacións reais, auditorías múltiples, cargas e, por suposto, ataques reais, sen os que é difícil chamar a un produto verdadeiramente seguro.
Non obstante, hai varios enfoques prometedores, difieren en moitos detalles e un deles definitivamente resolverá o problema. Con recursos informáticos modernos, a teoría criptográfica pode traducirse de xeito bastante intelixente en aplicacións prácticas. No futuro, estaremos encantados de falar das implementacións de PVRB: agora hai varias, cada unha ten o seu propio conxunto de propiedades importantes e características de implementación, e detrás de cada unha hai unha boa idea. Non hai moitos equipos implicados na aleatorización e a experiencia de cada un deles é moi importante para todos os demais. Agardamos que a nosa información permita a outros equipos avanzar máis rápido, tendo en conta a experiencia dos seus antecesores.
Fonte: www.habr.com