Finalidade Instantânea na Transmissão Atômica Bizantina Sob Participação Desconhecida/Dinâmica

13 de Setembro, 2020 — Dahlia Malkhi

Authors: Dahlia Malkhi (Chainlink Labs), Atsuki Momose (UIUC), Ling Ren (UIUC)

Tradução do artigo Instant Finality in Byzantine Atomic Broadcast Under Unknown/Dynamic Participation.

Sinopse:

Em um post anterior, apresentamos uma solução simples para um acordo Bizantino binário único com participantes Desconhecidos/Dinâmicos que pode ser substituídos a qualquer momento, condicionado à honestidade de dois terços dos participantes ativos, que garante finalidade determinística e incondicional e tem uma (pequena) latência esperada constante.

Neste post, estendemos a abordagem ao consenso multivalorado em uma sequência de valores, ou seja, resolvemos o problema da transmissão atômica bizantina (BAB — Byzantine Atomic Broadcast). Nosso protocolo herda do post anterior as seguintes vantagens sobre as soluções existentes: 1) pequena latência de 3 rodadas, 2) segurança determinística e incondicional, 3) não requer participação estável eventual, 4) permite participação flutuante de nós (nodes) defeituosos.

Recapitulação do modelo. O conjunto de participantes ativos — também chamados de nós — é desconhecido, sua contagem é desconhecida e, a cada rodada, eles podem ser substituídos integralmente, observados os seguintes pressupostos:

• PKI. Os nós participantes são retirados de um universo finito, cada um pode ser identificado por uma chave pública da qual possui a chave privada.
  — Observe que a PKI é necessária apenas para VRF e liveness; as mensagens não precisam ser assinadas por seus remetentes
• Nós ativos. Cada rodada r tem um conjunto desconhecido de nós ativos, cuja (desconhecida) contagem nr satisfaz nr ≥ 3fr + 1 , onde fr são bizantinos.
• Comunicação síncrona. Na rodada r, os nós honestos e ativos recebem todas as mensagens transmitidas pelos nós honestos na rodada r-1.

Também observamos que qualquer mensagem de nós defeituosos não pode ser atrasada para rodadas futuras.

Transmissão atômica. O protocolo permite que os nós concordem com uma sequência crescente de valores (entrada pelos nós) de tal forma que:

• Segurança. Dois nós honestos não decidem um valor na mesma posição da sequência.
• Vivacidade (liveness). O valor de entrada do nó honesto é finalmente decidido.

Nosso protocolo

Encadeamento. Usamos a técnica comum de encadeamento de blocos. Cada bloco contém algum valor (por exemplo, novas transações), bem como o hash de um bloco predecessor. O primeiro bloco inclui o hash de um bloco especial predefinido chamado de bloco “genesis”. Dizemos que um bloco B’ estende um bloco B se a sequência que termina em B é um prefixo da sequência que termina em B. Se dois blocos não se estendem um ao outro, dizemos que são conflitantes.

Acordo Avaliado/Classificado (GA–Graded Agreement). Nosso protocolo BA (Byzantine Atomic) no post anterior possui duas etapas de comunicação muito semelhantes. Cada etapa implementa uma abstração chamada de acordo graduado (GA). Primeiro apresentamos esse bloco de construção do GA e, em seguida, o usamos para construir nosso protocolo de transmissão atômica.

No contexto de participação desconhecida e dinâmica, o conjunto de nós ativos no início desta rodada (GA–Acordo Avaliado/Classificado) pode ser diferente do conjunto de nós ativos no final do GA (nós ativos na próxima rodada). Cada nó ativo no início do GA tem um bloco de entrada B. Cada (recentemente) nó ativo no final do GA determina um conjunto { (B, g) } de pares do bloco B e bit de grau g como uma saída de GA. Enfatizamos novamente que usamos o encadeamento de blocos, de modo que um bloco B identifica exclusivamente toda uma sequência de blocos começando na gênese e terminando em B.

Nosso protocolo GA (Acordo Avaliado/Classificado | GA–Graded Agreement)

No início do GA, todo nó ativo p envia (voto, B) para seu input B.

(O conjunto de nós ativos desde o início do GA pode agora ser substituído, ou seja, um conjunto diferente de nós pode agora receber e contabilizar os votos.)

Ao final do GA, cada nó ativo contabiliza votos. Se B’ estender B, então um voto em B’ também conta como um voto em B. Votos para blocos conflitantes do mesmo eleitor são ignorados.

• Saídas/Outputs (B, 1) se mais de ⅔ dos votos recebidos votar em B.
• Saídas/Outputs (B, 0) se mais de ⅓ dos votos recebidos votar em B.

Propriedades do GA. Pelas propriedades UDQ no post anterior, temos as seguintes garantias.

• Consistência avaliada/classificada. Se um nó honesto produzir (B, 1), todos os nós honestos produzirão (B, *).
• Integridade. Se um nó honesto gera (B, *), então pelo menos um nó honesto insere B’ que estende B.
• Validade. Seja B o ancestral comum mais alto das entradas dos nós honestos. Então, todos os nós honestos saem (B, 1)
• Singularidade. Se um nó honesto produzir (B, 1) e outro nó honesto produzir (B’, 1), então B e B’ não entrarão em conflito um com o outro.
• Divergência limitada. Cada nó emite (com nota 0) no máximo dois blocos conflitantes.

Nosso protocolo de transmissão atômica (Atomic Broadcast Protocol). Agora damos nosso protocolo de transmissão atômica. As variáveis ​​C, L são inicializadas na gênese. (C: candidato, L: bloqueio)

Cada visualização tem duas rodadas. Há uma rodada inicial extra antes do início da primeira visualização v = 1.

Rodada inicial 0: Enviar (propor, B, VRF) onde B é um bloco que estende a gênese.

1ª rodada de visualização v:

Se v > 1:

Decida qualquer bloco B de modo que GA2 da visualização v-1 saia (B, 1)

Defina L para o bloco mais alto, de modo que GA2 das saídas de visualização v-1 (L, *)

Input no GA1 um bloco com o maior VRF entre as mensagens “propostas” da rodada anterior que estendem L.

Se não houver tal bloco, insira L em GA1.

2ª rodada de visualização v:

Defina B para o bloco mais alto de forma que GA1 saia (B, 1).

Defina C para um bloco mais alto, de modo que GA1 saia (C, *). (Se houver dois desses C, escolha um aleatoriamente.)

Input B para GA2.

Enviar (propor, B’, VRF) onde B’ estende C.

Esboço da prova

Segurança. Suponha que um nó ativo honesto decida em um bloco B na rodada 1 da visualização v, ou seja, ele emite (B, 1) do GA2 que foi iniciado na visualização v-1. Devido à consistência graduada, qualquer nó honesto p ativo na rodada 1 da visualização v deve produzir (B, *). Observe também que o GA2 da view v-1 não pode ter como saída nenhum bloco conflitante. Isso ocorre porque nenhum nó honesto poderia ter inserido qualquer bloco conflitante no GA2 da visualização v-1 (devido à singularidade do GA1) e o GA2 não poderia ter gerado nenhum bloco conflitante sem a entrada de algum nó honesto (devido à integridade). Então p deve ter definido L como um bloco estendendo B na rodada 1 da visualização v. Ambos os GAs na visualização v, e indutivamente em todas as visões após v, produzem apenas blocos estendendo B (devido à validade). Portanto, nenhum nó honesto decide qualquer bloco conflitante.

Vivacidade. Vamos chamar o nó que enviou o VRF mais alto na visualização v-1 de líder da visualização v. É claro que se todos os nós honestos ativos inserirem a proposta de um líder honesto no GA1 da visualização v, o bloco proposto deve ser decidido. A única razão pela qual um nó honesto p não insere a proposta do líder para GA1 é que ele entra em conflito com seu bloqueio L. O nó p deve ter saída (L, *) do GA2 que começou na visualização anterior v-1. Então, algum nó honesto q deve ter entrada L (ou um bloco estendendo L) para GA2 após a saída (L, 1) em GA1 de visualização v-1. Assim, o líder da visualização v produz (L, 0) no GA1 da visualização v-1 (devido à consistência graduada). Devido à divergência limitada, o líder gera no máximo um outro bloco conflitante do GA1 da visualização v-1. Portanto, com probabilidade de pelo menos ½, o líder propõe um bloco estendendo L e todos os nós honestos aceitam a proposta do líder.

Discussão

Das quatro vantagens fundamentais listadas no início deste post, destacamos duas vantagens práticas importantes sobre as soluções existentes.

Latência de 3 rodadas. Uma vantagem prática importante do nosso protocolo é a latência prática: apenas 3 rodadas. Em contraste, o estado da arte anterior [Momose-Ren 2022] que custa 16 rodadas. Essa melhoria é atribuída a dois fatores: em primeiro lugar, melhoramos a latência do GA de 3 rodadas para 1 rodada, sacrificando a tolerância a falhas de ½ para ⅓. Em segundo lugar, e mais importante, melhoramos o protocolo de transmissão atômica reduzindo o número de invocações de GA de 5 para 2.

Flutuação de nodes defeituosos. Como mencionado no post anterior, nosso protocolo permite que não apenas nós honestos, mas também nós defeituosos entrem/saiam durante as execuções. Esta é uma vantagem prática importante, pois todas as soluções existentes sem prova de trabalho (ou função de atraso verificável) assumem que os nós defeituosos estão online o tempo todo (como mostrado em [Deb-Kannan-Tse, 2021]). Essa restrição ao adversário é difícil de justificar. Suponha que apenas 10 nós estejam ativos no início, mas 10 anos depois, um milhão de nós estejam ativos. Então, as soluções existentes terão que assumir que o adversário controla no máximo 10 dos 1 milhão de nós ativos. Nosso protocolo ainda tolera ⅓ milhões de nós ativos defeituosos.

Leia mais sobre esse trabalho em nosso whitepaper publicado recentemente.

Para as pesquisas mais recentes sobre blockchains, contratos inteligentes e oráculos, assine a newsletter da Chainlink e siga o Twitter oficial da Chainlink.