Resumo Técnico: Giskard

Declaração do Problema

O aprendizado descentralizado oferece uma alternativa preservadora de privacidade ao treinamento centralizado, permitindo que os participantes interajam ponto a ponto sem um orquestrador central confiável. No entanto, esses sistemas enfrentam dois desafios simultâneos e frequentemente conflitantes:

1. Robustez Bizantina: Nós maliciosos ou defeituosos podem enviar atualizações de modelo arbitrárias e manipuladas (envenenamento de modelo) para corromper o modelo global. Defender-se disso geralmente requer a inspeção e comparação de contribuições individuais para filtrar valores atípicos (por exemplo, usando medianas por coordenada ou médias aparadas).
2. Confidencialidade: Os participantes devem manter seus dados locais e atualizações de modelo privados. Técnicas criptográficas como a Computação Multipartidária Segura (MPC) ocultam essas atualizações, mas funções de agregação robustas padrão (que dependem de ordenação e comparação) são computacionalmente caras para implementar em forma criptografada.

As soluções existentes abordam esses problemas separadamente ou os combinam usando MPC de formas que não escalam. As abordas de MPC descentralizadas anteriores dependem frequentemente de comunicação todos-para-todos ou delegam a computação a um único comitê pequeno, resultando em uma complexidade de comunicação por nó que cresce linearmente ou pior com o tamanho da rede ($O(n)$ ou $O(n \log^2 n)$). Isso cria um gargalo fundamental de escalabilidade para implantações de larga escala (ex: $n \ge 10^4$).

Metodologia: O Protocolo Giskard

Giskard é um protocolo projetado para alcançar tanto robustez bizantina quanto confidencialidade em um ambiente totalmente descentralizado com complexidade de comunicação sublinear. Ele opera sob um modelo de adversário estático e computacionalmente limitado, onde até $f < n/4$ partes podem estar corrompidas.

Insights Técnicos Principais

1. Busca Binária para Mediana: Em vez de implementar circuitos de ordenação genéricos (que são caros em MPC), o Giskard reformula o cálculo da mediana por coordenada como uma busca binária segura sobre o domínio de valores. O protocolo estreita iterativamente o intervalo $[Esquerda, Direita]$ contando quantos inputs são menores que um pivô $p_t$. Isso reduz o problema a uma sequência de operações de contagem seguras.
2. Árvore de Comitês Hierárquica: Para distribuir a carga computacional, o Giskard organiza $n$ partes em uma árvore de comitês $k$-ária, cada um de tamanho $m = O(\log n)$.
   • Folhas (Nível 0): Partes individuais comparam seus vetores locais com o pivô atual e compartilham secretamente os vetores de bits resultantes para seus comitês de base atribuídos.
   • Comitês de Base (Nível 1): Validam o domínio dos bits compartilhados (garantindo que sejam 0 ou 1) usando uma prova de grau 2, agregam as partes e as recompartilham para cima.
   • Comitês Intermediários (Níveis 2 a $L-1$): Recebem partes de comitês filhos, realizam o recompartilhamento verificável e agregam para cima.
   • Comitê Raiz (Nível $L$): Reconstrói a contagem global de forma clara, atualiza o pivô e transmite o novo pivô para baixo na árvore para a próxima iteração.
3. Primitivas Criptográficas: O protocolo utiliza Compartilhamento de Segredos Verificável (VSS) baseado no esquema BGW (Asharov e Lindell) para garantir segurança contra adversários maliciosos. Ele emprega subprotocolos para compartilhamento, multiplicação e recompartilhamento, todos provados como universalmente composíveis (UC) seguros.

Garantias de Segurança e Robustez

• Confidencialidade: Inputs individuais e contagens intermediárias permanecem ocultos; apenas a contagem agregada final (usada para atualizar o pivô) é revelada.
• Robustez Bizantina: O protocolo tolera até $n/4$ partes bizantinas. Ele satisfaz o critério de robustez bizantina $(f, \kappa)$, garantindo que a saída permaneça próxima à média das atualizações honestas, correspondendo ao limiar de robustez da mediana por coordenada.
• Corretude: A busca binária converge para a mediana dentro de uma precisão $q$ após $N_{iter} = \lceil \log_2(2u/q) \rceil$ iterações.

Principais Contribuições

1. Protocolo Inovador: Proposta do Giskard, um protocolo de aprendizado descentralizado robusto e confidencial capaz de escalar para milhões de partes.
2. Segurança Teórica: Uma prova formal de que o Giskard é UC-seguro no modelo híbrido, baseando-se em suposições criptográficas padrão e na segurança de seus subprotocolos (BA, VSS, etc.).
3. Análise de Complexidade de Comunicação: Demonstração de que a complexidade de comunicação por parte no pior caso é polilogarítmica em $n$ ($O(d \cdot N_{iter} \cdot \log^3 n)$), uma melhoria significativa em relação aos concorrentes como Todos-para-Todos ($O(d \cdot n^2)$) ou Todos-para-Comitê ($O(d \cdot n \log^2 n)$).
4. Validação Experimental: Avaliação extensiva nos conjuntos de dados MNIST e CIFAR-10 com tamanhos de rede de até $n=10^6$.

Resultados Experimentais

Os autores avaliaram o Giskard contra duas topologias de referência: Todos-para-Todos (A2A) e Todos-para-Comitê (A2C).

• Escalabilidade (Custo de Comunicação):

  • Em $n=10^6$ com uma fração bizantina de 10%, o Giskard reduz a comunicação por parte em aproximadamente 1.775 vezes em comparação ao A2C e ordens de magnitude em comparação ao A2A.
  • Enquanto o A2C concentra a carga em um único comitê (tornando-o impraticável devido aos limites de largura de banda em escala), o Giskard distribui a carga através da árvore, mantendo os custos por parte gerenciáveis mesmo para $n=10^6$.
  • O tempo de execução estimado para A2C e A2A em grandes escalas excede os limites práticos (dias a anos), enquanto o Giskard permanece dentro de minutos ou horas.

• Utilidade do Modelo (Robustez):

  • Sob quatro ataques de envenenamento de modelo (Label Flipping, Sign Flipping, IPM, ALIE) em dados não-i.i.d., a mediana de busca binária do Giskard alcançou precisão de teste comparável aos agregadores robustos de texto claro de última geração (Trimmed Mean, Median).
  • No MNIST, a lacuna de precisão foi inferior a 0,4%. No CIFAR-10, a lacuna foi geralmente inferior a 1,5%, com lacunas ligeiramente maiores (até 2,7%) para ataques altamente otimizados que exigem maior precisão.
  • Os experimentos identificaram um limiar nítido para o número de iterações da busca binária ($N_{iter}$); aumentar as iterações além de $\approx 10$ não gerou ganhos significativos de robustez, mas aumentou linearmente os custos de comunicação.

Significância e Alegações

O artigo afirma que o Giskard preenche a lacuna entre escalabilidade e segurança no aprendizado descentralizado. Ao combinar uma estrutura de comitê hierárquica com uma formulação especializada de busca binária da mediana, o Giskard alcança:

• Comunicação sublinear: É o primeiro protocolo a alcançar comunicação por parte polilogarítmica para agregação confidencial e bizantino-robusta em um ambiente totalmente descentralizado.
• Garantias Formais: Ao contrário de abordagens heurísticas, o Giskard fornece provas de segurança UC e limites formais de robustez.
• Praticidade: Os resultados experimentais demonstram que o protocolo é viável para implantações de larga escala (até um milhão de participantes), onde soluções de MPC anteriores seriam computacional e comunicativamente inviáveis.

Os autores concluem que, embora o protocolo introduza um compromisso entre o número de iterações e a precisão, o sistema proposto equilibra efetivamente confidencialidade, robustez e escalabilidade, tornando o aprendizado descentralizado seguro em larga escala algo prático. Sugere-se que trabalhos futuros explorem variantes computacionais baseadas em suposições criptográficas para reduzir ainda mais os custos.