Resumo Técnico: Códigos de Apagamento Monótonos

1. Declaração do Problema

Os códigos de apagamento tradicionais, como os códigos Reed-Solomon (MDS), operam sob uma hipótese de falha de limite. Nestes sistemas, os dados são divididos em $k$ partes e codificados em $n$ fragmentos, de modo que qualquer conjunto de $k$ fragmentos seja suficiente para a reconstrução. Este modelo assume que qualquer subconjunto de $k$ nós tem igual probabilidade de estar disponível ou falhar, independentemente da identidade específica dos nós.

No entanto, os sistemas distribuídos modernos, particularmente em blockchain e criptomoedas (por exemplo, Stellar, XRP Ledger), utilizam hipóteses de falha generalizadas ou sistemas de quórum bizantinos. Nestes contextos, a confiança não é uniforme; alguns nós são mais confiáveis do que outros, e os padrões de falha não são puramente aleatórios, mas dependem de subconjuntos específicos de nós. Os códigos existentes baseados em limites não conseguem acomodar eficientemente essas hipóteses de confiança arbitrárias sem sobrecarga significativa ou incompatibilidade estrutural. O artigo aborda a necessidade de códigos de apagamento que respeitem estruturas de acesso monótonas arbitrárias, onde subconjuntos específicos de nós (conjuntos de acesso) têm garantida a reconstrução dos dados, enquanto outros podem não tê-la.

2. Metodologia

O artigo introduz os Códigos de Apagamento Monótonos, uma generalização dos códigos de apagamento clássicos projetada para funcionar com estruturas de acesso arbitrárias $\mathcal{A} \subseteq 2^{\mathcal{P}}$, onde $\mathcal{P}$ é o conjunto de nós.

2.1 Definições e Formalismo

• Código de Apagamento Monótono: Um esquema consistindo em algoritmos Encode (Codificar) e Decode (Decodificar). Encode mapeia um arquivo $f$ para um vetor de fragmentos $(g_1, \dots, g_n)$, onde os fragmentos podem ter tamanhos diferentes. Decode reconstrói $f$ a partir de qualquer subconjunto de fragmentos correspondente a um conjunto de acesso $A \in \mathcal{A}$.
• Eficiência: Medida pela sobrecarga $\beta = (\mu - \kappa) / \kappa$, onde $\kappa$ é o tamanho do arquivo de entrada e $\mu$ é o tamanho total de todos os fragmentos. O objetivo é minimizar $\beta$.
• Códigos de Apagamento Monótonos Lineares: Uma classe específica onde a codificação e a decodificação são operações lineares sobre um corpo finito $\mathbb{F}_q$. A codificação é definida por uma matriz geradora $G$ e uma função de rotulagem $\phi$ que mapeia as colunas de $G$ para os nós. Um conjunto de nós é suficiente se a submatriz de $G$ correspondente a esses nós tiver posto completo ($k$).

2.2 Abordagens de Construção

O artigo apresenta três métodos distintos para construir esses códigos:

1. Construção Básica (Não Ótima):

   • Baseada em uma Fórmula Booleana Monótona (MBF) que representa a estrutura de acesso.
   • O algoritmo percorre recursivamente a árvore de acesso. Para um nó E (AND), o arquivo é dividido em blocos; para um nó OU (OR), o arquivo é replicado.
   • Resultado: Garante completude, mas frequentemente resulta em alta sobrecarga devido à replicação redundante na estrutura da árvore.

2. Construção Linear Eficiente (Sub-Ótima):

   • Utiliza um algoritmo recursivo que constrói uma matriz MDS por blocos.
   • Constrói a matriz de codificação combinando matrizes de Vandermonde (para operadores de limite) usando produtos de Kronecker e matrizes identidade para alinhar as dimensões.
   • Resultado: Computacionalmente eficiente (polinomial no tamanho da árvore de acesso), mas não garante sobrecarga mínima.

3. Construção Linear Ótima (via Programação Linear):

   • Caso Geral: Formula o problema de encontrar a distribuição ótima de fragmentos como um Problema de Programação Linear (PPL). O objetivo é minimizar a soma dos pesos dos fragmentos atribuídos aos nós, sujeito a restrições de que todo conjunto de acesso detenha pelo menos $k$ fragmentos "base" (derivados de um código MDS subjacente).
   • Estruturas de Acesso Partitionadas: Para uma classe específica de estruturas (hierárquicas, onde cada nó aparece exatamente uma vez na MBF, por exemplo, o modelo de confiança do Stellar), o artigo fornece um algoritmo recursivo especializado (Algoritmo 2). Este algoritmo resolve o PPL eficientemente ($O(n^2)$) identificando quais subárvores incluir ou excluir para minimizar a sobrecarga, determinando efetivamente uma atribuição ótima de fragmentos base.

2.3 Aplicação no Protocolo: GAVID

O artigo integra esses códigos em um protocolo distribuído chamado Dispersão de Informação Verificável Assíncrona Geral (GAVID).

• Generalização: Estende o protocolo AVID clássico (Cachin e Tessaro) de sistemas de limite para sistemas gerais de quórum bizantino.
• Mecanismo: Utiliza o sistema de núcleo do sistema de quórum como a estrutura de acesso para o código de apagamento monótono.
• Conceitos Chave: Introduz Conjuntos Confiáveis (conjuntos que contêm um núcleo disjunto de qualquer conjunto defeituoso) para garantir disponibilidade e consistência no cenário assíncrono.
• Otimização: Propõe o GAVID-H, que substitui o vetor de verificação completo pela raiz de uma árvore de Merkle, reduzindo a complexidade de comunicação.

3. Contribuições Principais

1. Definição de Códigos de Apagamento Monótonos: O artigo define formalmente um novo primitivo de codificação que generaliza os códigos de apagamento clássicos para estruturas de acesso monótonas arbitrárias, permitindo hipóteses de confiança não uniformes.
2. Algoritmos de Construção:
   • Fornece um método computacionalmente eficiente para construir códigos de apagamento monótonos lineares para qualquer estrutura de acesso (embora nem sempre ótimo em termos de sobrecarga).
   • Fornece um método para construir códigos de apagamento monótonos lineares ótimos resolvendo um problema de programação linear derivado da estrutura de acesso.
3. Estruturas de Acesso Partitionadas: Analisa o caso específico de estruturas de acesso partitionadas (comuns na prática) e apresenta um algoritmo eficiente para construir códigos ótimos para elas, caracterizando sua sobrecarga.
4. Protocolo GAVID: Formula um protocolo geral de dispersão de informação verificável assíncrona (GAVID) que utiliza códigos de apagamento monótonos para alcançar transmissão confiável bizantina eficiente em comunicação para sistemas de quórum arbitrários.

4. Resultados e Análise

• Limites de Sobrecarga: Para uma estrutura de acesso geral com tamanho mínimo de conjunto de acesso $\tau$, a sobrecarga $\beta$ de um código de apagamento monótono linear ótimo é limitada por $\beta \le (n - \tau)/\tau$ para grandes $k$. Isso implica que, se o menor conjunto de acesso estiver próximo do número total de nós, a sobrecarga aproxima-se de zero.
• Eficiência da Construção Partitionada: O algoritmo especializado para estruturas de acesso partitionadas executa em tempo $O(n^2)$, o que é significativamente mais rápido do que resolver o PPL geral diretamente quando o número de conjuntos de acesso é exponencial.
• Complexidade do Protocolo:
  • GAVID Dispersar: Complexidade de mensagens $O(n^2)$; Complexidade de comunicação $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Otimizado com Merkle): Reduz a complexidade de comunicação para $O(n(1+\beta)|f| + n^2(\log n)|H|)$ e a complexidade de armazenamento para $O((1+\beta)|f| + n(\log n)|H|)$.
• Correção: O artigo prova que o GAVID satisfaz as propriedades de Término, Acordo, Disponibilidade e Correção para qualquer sistema de quórum bizantino, desde que exista um código de apagamento monótono para a estrutura de núcleo do sistema.

5. Significado e Alegações

O artigo alega que os códigos de apagamento monótonos são um facilitador crítico para sistemas distribuídos conscientes de confiança. Ao ir além do modelo rígido de limite "qualquer $k$ de $n$", esses códigos permitem que os sistemas:

• Reduzam a Redundância: Otimizem a sobrecarga de armazenamento e comunicação atribuindo mais dados a nós confiáveis e menos a nós arriscados, em vez de tratar todos os nós igualmente.
• Suportem Modelos de Confiança Complexos: Implementem diretamente as hipóteses de confiança encontradas em redes de blockchain do mundo real (como o Stellar), onde a confiança é hierárquica e não uniforme.
• Generalizem Protocolos: Fornecer um primitivo fundamental (GAVID) que permite que protocolos existentes de transmissão e consenso eficientes funcionem sob sistemas gerais de quórum bizantino, e não apenas sob modelos de limite simples.

Os autores observam que, embora forneçam uma construção eficiente para estruturas partitionadas, o problema de construir um código de apagamento monótono ótimo para uma estrutura de acesso arbitrária (dada como uma MBF com conjuntos exponencialmente numerosos) permanece uma questão em aberto. Eles também sugerem trabalhos futuros em códigos dinâmicos e a aplicação de outras técnicas da teoria de codificação (por exemplo, códigos sem taxa) a este cenário.