Aleatoriedade pública e sinalizadores de aleatoriedade

Aleatoriedade pública é um componente essencial de muitos protocolos de segurança do mundo real. Em algumas aplicações, como jogos de azar e jogos multijogador, a aleatoriedade acrescenta diversão. Noutras aplicações, a aleatoriedade proporciona uma forma justa de alocar recursos não divisíveis, desde green cards, à designação de juízes de tribunais distritais para casos, até à classificação em torneios desportivos. Também é usado para alocar negativo recursos, como auditorias fiscais ou triagem secundária de segurança no aeroporto.

Tradicionalmente, confiamos em autoridades confiáveis ​​para gerar aleatoriedade para esses protocolos, mas no mundo web3 precisaremos fazer melhor. Nesta postagem, exploraremos abordagens para construir aleatoriedade publicamente verificável por meio de beacons de aleatoriedade distribuída e então discuta algumas aplicações na cadeia. (A Parte II, que será publicada em breve, concentrar-se-á especificamente na eleição de líderes, ao mesmo tempo que fornece uma avaliação das abordagens alternativas de eleição de líderes.) 

Propriedades desejadas

Gerar números aleatórios é uma tarefa notoriamente sutil. Por exemplo, muitas chaves criptográficas vazaram porque confiou em um gerador de números aleatórios com defeito (para o qual a parede de Cloudflare lâmpadas de lava teria servido como uma mitigação criativa). Isso é apenas aleatoriedade privada, no entanto, onde apenas uma parte precisa gerá-lo e utilizá-lo.

A aleatoriedade pública, pelo contrário, é um processo multipartidário, o que aumenta consideravelmente a dificuldade. Um bom protocolo para produzir aleatoriedade pública terá as seguintes propriedades de segurança:

• Imparcial: Nenhum atacante, ou coligação de atacantes, deve ser capaz de distorcer o resultado. 
• Confiável: Nenhum invasor deve ser capaz de impedir que o protocolo produza resultados.
• Verificável: Qualquer pessoa pode verificar facilmente a saída do protocolo e deve ver a mesma saída que todos os outros.
• Imprevisível: Se o protocolo produzir saída no momento T₁, ninguém deveria ser capaz de prever nada sobre o resultado antes de algum tempo T₀<T₁, idealmente com T₀ muito perto de T₁.

A imparcialidade é uma propriedade mais fraca do que a imprevisibilidade porque qualquer protocolo imprevisível deve ser imparcial. Cientistas da computação diriam imparcialidade reduz à imprevisibilidade, porque se você pode influenciar, você pode prever. Mas por vezes quereremos raciocinar sobre eles separadamente porque podem basear-se em pressupostos diferentes – por exemplo, uma maioria desonesta pode prever o resultado, mas não o distorcer.

Além dessas propriedades, o protocolo deve ser eficiente para rodar e produzir um grande número de bits aleatórios. (Na prática, muitas vezes é suficiente que os aplicativos produzam 128 bits aleatórios, usando-os para propagar um gerador de números pseudo-aleatórios [PNRG] para produzir mais bits conforme necessário. No entanto, a imprevisibilidade deve ser mantida para que cada bit individual da saída seja utilizável para tal aplicações como loterias ou alocações de recursos.) Idealmente, o protocolo também deve ser eficiente em termos de custos de comunicação e computação.

Diferentes protocolos podem atingir essas propriedades sob diferentes condições. Por exemplo, alguns protocolos podem ser imparciais por qualquer coligação de f₁ nós maliciosos e imprevisíveis por qualquer coalizão de f₂<f₁ nós maliciosos. Existem também diferentes graus de preconceito. Por exemplo, em alguns protocolos, um participante pode ser capaz de polarizar a saída em “um bit” – o que significa que pode escolher entre uma de duas saídas possíveis. Outros ataques podem permitir que consertem completamente a saída. Normalmente, porém, não queremos tolerar qualquer preconceito (ou previsibilidade).

O ideal criptográfico: Rfaróis de andomness

Os criptógrafos geralmente começam pensando em uma solução ideal para seus problemas. No caso da aleatoriedade pública, um farol de aleatoriedade é um serviço idealizado que produz regularmente resultados aleatórios que satisfazem todos os requisitos de segurança necessários.

Esse farol de aleatoriedade idealizado, semelhante a outras abstrações criptográficas – como oráculos aleatórios ou o modelo de grupo genérico – não existe no mundo real. Mas é um objetivo útil a ser alcançado e um modelo útil para raciocinar sobre protocolos que dependem da aleatoriedade pública. 

Podemos considerar algumas aproximações de um farol de aleatoriedade ideal.

• Beacons centralizados: A abordagem mais fácil para gerar uma boa aleatoriedade é através de um terceiro centralizado com serviços como Farol de aleatoriedade do NIST or random.org, que gera aleatoriedade a partir do ruído atmosférico e é credenciado para uso em jogos de azar. Esta dependência de terceiros mina completamente a filosofia da descentralização. Na verdade, no exemplo acima temos que confiar que as organizações relevantes estão a gerar aleatoriedade corretamente, sem qualquer prova criptográfica.
• Exibições de aleatoriedade física: Muitas loterias tradicionais dependem de uma exibição pública, que pode incluir, por exemplo, alguém pegando um recipiente com bolas de pingue-pongue com números diferentes. Infelizmente, estes são muitas vezes facilmente manipuláveis. Por exemplo, certas bolas podem ser colocadas em um freezer e o seletor pode ser instruído a escolher os frios.
• Faróis naturais: Uma ideia comum é usar fenômenos naturais aleatórios, como clima ou radiação cósmica de fundo, como farol. Infelizmente, todas as fontes propostas não fornecem um consenso forte. Diferentes observadores verão valores ligeiramente diferentes, o que requer a reintrodução de uma parte confiável para realizar uma medição oficial, com todas as desvantagens de um farol centralizado.
• Beacons semicentralizados: Uma abordagem melhor seria obter a aleatoriedade de Cabeçalhos de bloco Bitcoin diretamente ou de preços de fechamento das ações, que é mais fácil de verificar publicamente e mais difícil para qualquer uma das partes controlar completamente. No entanto, ainda existem ataques sutis contra ambos aleatoriedade do blockchain de prova de trabalho e aleatoriedade do preço das ações. Com cabeçalhos de blockchain, por exemplo, os mineradores podem optar por reter blocos cujos cabeçalhos produzem um valor de beacon que eles não gostam. Ou eles podem optar por desempate quando dois blocos em colisão são encontrados com base em sua saída de beacon preferida.

Beacons de aleatoriedade descentralizados (DRBs)

Uma abordagem natural para os problemas dos beacons centralizados é projetar um protocolo criptográfico descentralizado para produzir aleatoriedade pública. Este problema é semelhante ao projeto de protocolos de consenso descentralizados, só que mais difícil. Não apenas todos os participantes precisam concordar sobre um resultado (a aleatoriedade), mas também deveria ser impossível para um participante mal-intencionado no protocolo distorcer ou prever o resultado.

Os protocolos projetados para simular um beacon de aleatoriedade são chamados de beacons de aleatoriedade distribuídos (DRBs). (Outros nomes incluem “lançamento distribuído de moedas”.) O problema tem sido estudado há décadas, com famosos resultados de impossibilidade comprovados na década de 1980, mas o interesse reacendeu na era do blockchain. Os DRBs poderiam ser usados ​​para fornecer aleatoriedade na cadeia, o que seria um ingrediente chave para aplicações na cadeia justas, seguras e transparentes.

A abordagem clássica: protocolos de confirmação e revelação

Um protocolo muito simples de duas rodadas é suficiente para um DRB no caso otimista. Na rodada 1, cada participante i gera um valor aleatório r_i e publica um compromisso criptográfico c_i=Comprometer-se(r_i). Nesta aplicação, o compromisso pode ser simplesmente uma função hash como SHA-256. Depois que o compromisso de cada participante é publicado, eles ficam limitados à sua escolha de r_i, mas os compromissos não revelam qualquer informação sobre as contribuições de outros participantes. Na segunda rodada, cada participante “abre seu compromisso” publicando r_i. Todos os valores aleatórios são então combinados, por exemplo, por meio de XOR ou (de preferência) hash de sua concatenação.

Este protocolo é simples e produz uma saída de beacon aleatória, desde que um dos participantes escolha seu r_i aleatoriamente. Infelizmente, ele sofre de uma falha clássica: quando todos os participantes, exceto um, revelam seu valor aleatório, o último participante é capaz de calcular a suposta saída do beacon. Caso não gostem, podem se recusar a publicar seu valor, abortando o protocolo. Ignorar a contribuição de um participante defeituoso não resolve o problema, porque ainda dá ao invasor a escolha entre duas saídas de beacon (uma calculada com sua contribuição e outra sem).

As blockchains oferecem uma solução natural para este problema: cada participante pode ser obrigado a colocar alguns fundos em depósito que serão apreendidos se não revelarem a sua contribuição aleatória. Esta foi exatamente a abordagem adotada pelo clássico RANDO farol no Ethereum. A desvantagem dessa abordagem é que o resultado ainda pode ser tendencioso, o que pode valer a pena financeiramente para o invasor se o dinheiro em depósito for menor do que a quantidade de dinheiro que depende do resultado do beacon. Uma melhor segurança contra ataques tendenciosos exige a colocação de mais moedas em depósito.

Protocolos de confirmação-revelação-recuperação

Em vez de tentar forçar todas as partes a revelarem a sua contribuição aleatória, alguns protocolos incluem um mecanismo de recuperação para que, mesmo que uma minoria de participantes desista, o restante possa completar o protocolo. É importante que o protocolo produza o mesmo resultado em ambos os casos, para que as partes não possam influenciar o resultado ao escolherem desistir ou não.

Uma abordagem para conseguir isso é fazer com que cada participante forneça aos outros partes do seu segredo, de modo que a maioria deles possa reconstruí-lo, usando, por exemplo, O compartilhamento de segredos de Shamir. Uma propriedade importante, entretanto, é que os outros podem verificar se o segredo comprometido foi adequadamente compartilhado, exigindo o uso de uma primitiva mais forte chamada compartilhamento de segredo publicamente verificável (PVSS).

Vários outros mecanismos de recuperação são possíveis, mas todos têm a mesma limitação. Se houver N participantes, e queremos resiliência se algum grupo de até f nós desaparecem, então deve ser o caso de qualquer grupo de Número os participantes podem calcular o resultado final. Mas isso também significa uma coligação maliciosa de Número os participantes podem prever o resultado antecipadamente, simulando de forma privada o mecanismo de recuperação. Isto também pode acontecer durante a primeira ronda do protocolo, período durante o qual tal coligação poderia modificar as suas próprias escolhas de aleatoriedade e distorcer o resultado. 

Dito de outra forma, isto significa que qualquer coligação de Número os nós devem incluir pelo menos um nó honesto. Por álgebra simples, Nf >f, assim f < N/2, e esses protocolos exigem inerentemente uma maioria honesta. Esta é uma diferença significativa em relação ao modelo de segurança original de confirmação-revelação, que requer apenas f<N (pelo menos um participante honesto).

Esses protocolos muitas vezes também exigem custos de comunicação significativos para compartilhar informações extras de PVSS entre todos os nós em cada execução do protocolo. A comunidade científica tem feito um trabalho considerável sobre este problema nos últimos anos, com propostas de investigação incluindo RandShare, Raspar, SecRand, HERBou Albatroz, mas nenhum parece ter sido implantado no mundo real.

Protocolos verificáveis ​​baseados em funções aleatórias

Percebendo que um grupo de Número participantes podem calcular o valor do beacon aleatório no protocolo acima leva a uma abordagem um pouco mais simples: compartilhar uma chave secreta de longo prazo entre N partes e peça-lhes que o utilizem para avaliar um função aleatória verificável (VRF). A chave secreta é compartilhada através de um t-de-N esquema de limites, de modo que qualquer t os participantes podem calcular o VRF (mas uma coalizão menor não pode). Para t=Número, isso fornece a mesma resiliência para f nós maliciosos como os protocolos commit-reveal-recover discutidos acima.

DFINITY foi pioneiro nesta abordagem como parte de seu protocolo de consenso usando assinaturas BLS de limite (que funcionam como VRF). O independente dinheiro O farol de aleatoriedade usa essencialmente a mesma abordagem, com um conjunto de participantes assinando um contador em cada rodada. O Liga da Entropia é uma instância de código aberto de drand que produz aleatoriedade a cada 30 segundos usando 16 nós participantes (em setembro de 2022), administrada por uma combinação de empresas e grupos de pesquisa universitários. 

Uma desvantagem dessas abordagens é que a inicialização da chave de limite é relativamente complexa, assim como a reconfiguração da chave quando os nós entram ou saem. No caso comum, porém, os protocolos são muito eficientes. 

Conforme descrito acima, a simples assinatura de um valor de contador não adiciona nenhuma nova aleatoriedade por rodada; portanto, se um número suficiente de chaves dos participantes for comprometido, o protocolo será previsível em todas as rodadas futuras.

VRF Chainlink combina esta abordagem (usando o NSEC5 VRF) com uma fonte externa de aleatoriedade especificada pelas partes que solicitam aleatoriedade, normalmente um cabeçalho de blockchain recente na prática. Esses dados são então alimentados por meio de um VRF que é executado por uma parte ou limitado a um grupo.

Ethereum's Beacon Chain atualmente usa VRFs baseados em BLS: o proponente de cada rodada adiciona seu valor de VRF ao mix. Isso economiza uma rodada de comunicação em comparação com o paradigma commit-reveal (assumindo que uma chave pública BLS de longo prazo seja registrada uma vez), embora este design herde algumas advertências da abordagem commit-reveal, incluindo a possibilidade de distorcer a saída do beacon retendo a saída .

Protocolos baseados em função de atraso verificável

Finalmente, uma nova direção promissora é usar criptografia baseada em tempo, especificamente funções de atraso verificáveis ​​(VDFs). Esta abordagem promete proporcionar boa eficiência e robustez de comunicação com resiliência a N-1 nós maliciosos. 

Voltando ao protocolo original de commit-reveal, os compromissos tradicionais podem ser substituídos por compromissos cronometrados para eliminar o problema dos participantes se recusarem a revelar a sua contribuição aleatória. Os compromissos cronometrados podem ser abertos de forma eficiente pelo committer original ou por qualquer pessoa que esteja disposta a calcular uma função lenta (essencialmente um VDF). Assim, se algum participante sair de um protocolo de commit-reveal, seu comprometimento ainda poderá ser aberto por outros. É essencial que o tempo mínimo para abrir o compromisso seja longo o suficiente para que isso não possa ser feito durante a primeira rodada (a fase de commit) do protocolo, caso contrário, participantes mal-intencionados poderiam abrir compromissos de outros com rapidez suficiente para modificar sua própria contribuição e distorcer o resultado. .

Um protocolo de rodada única ainda mais elegante é possível com VDFs modernos: abandone totalmente o compromisso. Cada participante pode simplesmente publicar sua contribuição aleatória r_i, e o resultado final é uma combinação da contribuição de cada participante, executada através de um VDF. O atraso no cálculo do VDF garante que ninguém possa escolher o seu compromisso de uma forma que vise o resultado final. Esta abordagem foi proposta como UNICORN por Arjen Lenstra e Benjamin Wesolowski em 2015 e, de fato, foi uma aplicação motivadora fundamental no desenvolvimento de VDFs.

Esta abordagem teve alguma implantação prática. Chia implementa uma versão disso como parte de seu protocolo de consenso, usando VDFs de quadratura repetida em grupos de classes. Farmacêutico implementou um farol de prova de conceito baseado em VDF usando VDFs baseados em SNARK. Ethereum também planeja usar esta abordagem, construindo um ASIC dedicado para computar VDFs para gerar aleatoriedade na camada de consenso.

***

A aleatoriedade pública é um componente essencial de muitos protocolos, mas ainda falta qualquer DRB padrão que forneça alta segurança. O espaço de design é grande e muitos híbridos e combinações das abordagens acima são possíveis. Por exemplo, é possível combinar um protocolo baseado em VRF com um protocolo baseado em VDF, o que adiciona nova entropia, por exemplo, conforme proposto por RandRunner. O Beacon Chain da Ethereum atualmente usa VRFs, embora possa adicionar VDFs no futuro para eliminar a possibilidade de viés de ataques de retenção de bloqueio.

Também é uma questão em aberto quando os protocolos de maioria honesta são aceitáveis. Para um grupo relativamente pequeno e avaliado de participantes – como a Liga da Entropia – uma suposição de maioria honesta é razoável. Por outro lado, os protocolos que requerem apenas um único participante honesto têm uma vantagem inerente – mais participantes só podem melhorar a segurança. Isso significa que esses protocolos podem ser potencialmente implantados com participação aberta e sem permissão.

Na Parte II, discutiremos a aplicação específica da eleição aleatória de líderes em protocolos de consenso, que tem objetivos de design ligeiramente diferentes e, como resultado, viu ainda mais protocolos e abordagens propostas.

***

José Bonneau é um parceiro de pesquisa na criptomoeda a16z. Sua pesquisa se concentra em criptografia aplicada e segurança blockchain. Ele ministrou cursos de criptomoeda na Universidade de Melbourne, NYU, Stanford e Princeton, e recebeu um doutorado em ciência da computação pela Universidade de Cambridge e bacharelado em Stanford.

Valéria Nikolaenko é um parceiro de pesquisa na criptomoeda a16z. Sua pesquisa se concentra em criptografia e segurança blockchain. Ela também trabalhou em tópicos como ataques de longo alcance em protocolos de consenso PoS, esquemas de assinatura, segurança pós-quântica e computação multipartidária. Ela é PhD em Criptografia pela Universidade de Stanford sob a orientação do professor Dan Boneh e trabalhou na blockchain Diem como parte da equipe de pesquisa principal.

***

Editor: Tim Sullivan

***

As opiniões expressas aqui são as do pessoal individual da AH Capital Management, LLC (“a16z”) citadas e não são as opiniões da a16z ou de suas afiliadas. Certas informações aqui contidas foram obtidas de fontes de terceiros, inclusive de empresas do portfólio de fundos administrados pela a16z. Embora retiradas de fontes consideradas confiáveis, a16z não verificou essas informações de forma independente e não faz representações sobre a precisão duradoura das informações ou sua adequação a uma determinada situação. Além disso, esse conteúdo pode incluir anúncios de terceiros; a16z não revisou tais anúncios e não endossa nenhum conteúdo de publicidade neles contido.

Este conteúdo é fornecido apenas para fins informativos e não deve ser considerado como aconselhamento jurídico, comercial, de investimento ou fiscal. Você deve consultar seus próprios conselheiros sobre esses assuntos. As referências a quaisquer valores mobiliários ou ativos digitais são apenas para fins ilustrativos e não constituem uma recomendação de investimento ou oferta para fornecer serviços de consultoria de investimento. Além disso, este conteúdo não é direcionado nem destinado ao uso por quaisquer investidores ou potenciais investidores, e não pode, em nenhuma circunstância, ser invocado ao tomar uma decisão de investir em qualquer fundo administrado pela a16z. (Uma oferta para investir em um fundo a16z será feita apenas pelo memorando de colocação privada, contrato de subscrição e outra documentação relevante de tal fundo e deve ser lida na íntegra.) Quaisquer investimentos ou empresas de portfólio mencionados, referidos ou descritos não são representativos de todos os investimentos em veículos administrados pela a16z, e não pode haver garantia de que os investimentos serão rentáveis ​​ou que outros investimentos realizados no futuro terão características ou resultados semelhantes. Uma lista de investimentos feitos por fundos administrados por Andreessen Horowitz (excluindo investimentos para os quais o emissor não deu permissão para a a16z divulgar publicamente, bem como investimentos não anunciados em ativos digitais negociados publicamente) está disponível em https://a16z.com/investments /.

Os gráficos e gráficos fornecidos são apenas para fins informativos e não devem ser considerados ao tomar qualquer decisão de investimento. O desempenho passado não é indicativo de resultados futuros. O conteúdo fala apenas a partir da data indicada. Quaisquer projeções, estimativas, previsões, metas, perspectivas e/ou opiniões expressas nestes materiais estão sujeitas a alterações sem aviso prévio e podem diferir ou ser contrárias às opiniões expressas por outros. Consulte https://a16z.com/disclosures para obter informações adicionais importantes.