Resumo Técnico: Orq – Análise Complexa de Dados Privados com Fortes Garantias de Segurança

1. Definição do Problema

O artigo aborda o desafio de realizar análises relacionais complexas (especificamente junções de múltiplas vias e agregações) em grandes conjuntos de dados privados dentro de um ambiente de Computação Multipartidária Segura (MPC) terceirizada. Nesse cenário, os proprietários dos dados distribuem partes secretas (secret shares) de seus dados para um conjunto de partes computacionais não confiáveis e não colusivas (servidores).

O principal gargalo em sistemas MPC anteriores é o efeito cascata das junções (joins) oblíquas. Para manter a oblicuidade (ocultando padrões de acesso e distribuição de dados), as junções oblíquas padrão em tabelas com $n$ registros devem produzir um tamanho de saída de pior caso de $n^2$ (o produto cartesiano). Para consultas envolvendo múltiplas junções ($k$ junções), isso leva a uma complexidade de tempo e espaço de $O(n^{k+1})$, tornando consultas complexas intratáveis para grandes conjuntos de dados.

Soluções existentes enfrentam um trilema:

1. Custo Quadrático: Computar o produto cartesiano completo (caro).
2. Descarte Silencioso: Impor um limite subquadrático descartando registros silenciosamente (incorreto).
3. Vazamento (Leakage): Vazamento do tamanho do resultado da junção para os servidores (inseguro).

Trabalhos anteriores em ambientes terceirizados (ex: Secrecy, Scape) sofrem tanto de custos quadráticos quanto de vazamento do tamanho do resultado. Além disso, muitos sistemas existentes dependem de bases de computação confiáveis (TCBs) ou modelos específicos de propriedade de dados (ex: peer-to-peer onde os proprietários também são partes computacionais) que não se generalizam para o modelo terceirizado onde os servidores nunca veem o texto simples (plaintext).

2. Metodologia

O Orq introduz um tempo de execução de sistema holístico projetado para avaliar consultas complexas com complexidade $O(n \log n)$, evitando o aumento quadrático sem vazar informações.

2.1 Percepção Central: Limites Independentes de Dados

Os autores observam que, em muitos cenários práticos de análise colaborativa, o tamanho do resultado da consulta é limitado pelo pior caso pelo tamanho da entrada ($O(n)$), independentemente da distribuição dos dados. Isso se mantém mesmo para junções de muitos-para-muitos, desde que a estrutura da consulta permita uma agregação decomponível. O Orq aproveita essa observação para limitar os tamanhos dos resultados intermediários.

2.2 O Operador Composto de Junção-Agregação

A inovação central é um operador de Junção-Agregação fundido que evita a materialização do produto cartesiano.

• Mecanismo: Em vez de primeiro realizar a junção e depois a agregação, o Orq realiza uma avaliação no estilo "MapReduce". Ele aplica uma pré-agregação (avaliação parcial) nas tabelas de entrada para lidar com duplicatas, realiza a junção e, em seguida, aplica uma pós-agregação.
• Implementação: O operador concatena as tabelas de entrada, ordena-as obliquamente pelas chaves de junção e utiliza uma Rede de Agregação (AggNet) do tipo butterfly para propagar valores e computar agregados em um único fluxo de controle.
• Suporte: Suporta inner, outer, semi- e anti-joins, bem como agregações arbitrárias definidas pelo usuário (soma, contagem, mín, máx, média).
• Lidando com Duplicatas: Para junções de muitos-para-muitos, o Orq pré-agrega uma entrada para criar chaves únicas (multiplicidade), realiza a junção e, em seguida, pós-agrega para combinar as multiplicidades. Isso garante que o tamanho da tabela intermediária nunca exceda a cardinalidade da maior entrada.

2.3 Primitivas Oblíquas e Ordenação

Para suportar o operador de junção-agregação, o Orq implementa primitivas oblíquas de última geração:

• Ordenação (Sorting): O Orq fornece implementações vetorizadas e paralelas de dados de Quicksort e Radixsort.
  • Quicksort: Utiliza um paradigma iterativo de embaralhamento seguido de ordenação para reduzir as rodadas de comunicação para $O(\log n)$.
  • Radixsort: Utiliza uma abordagem híbrida combinando permutação de bits imediata com embaralhamento oblíquo.
  • TableSort: Um invólucro (wrapper) que extrai a permutação de ordenação de uma ordenação com preenchimento (padded sort) e a aplica a todas as colunas de uma tabela, evitando a ordenação redundante de múltiplas colunas.
• Embaralhamento (Shuffling): Primitivas de embaralhamento oblíquo generalizadas compatíveis com vários protocolos de MPC.
• Vetorização: Todos os operadores são implementados usando um formato de dados colunar, permitindo que mensagens independentes dentro de um estágio sejam agrupadas (batched) e enviadas em uma única rodada de comunicação.

2.4 Arquitetura do Sistema

• API de Fluxo de Dados (Dataflow API): Os usuários definem consultas usando uma API de estilo fluxo de dados (semelhante ao Apache Spark) em vez de SQL, permit que a expressão de pipelines complexos seja concisa.
• Agnosticismo de Protocolo: Os operadores são construídos como abstrações de caixa-preta sobre primitivas de MPC ($+, \times, \oplus, \land$). O Orq suporta três protocolos:
  1. Semi-honesto, maioria desonesta (ABY, 2-partes).
  2. Semi-honesto, maioria honesta (Araki et al., 3-partes).
  3. Segurança maliciosa, maioria honesta (Fantastic Four, 4-partes).
• Camada de Comunicação: Uma camada customizada baseada em TCP com buffers de anel (ring buffers) sem bloqueio para amortizar os custos de rede, particularmente em configurações WAN.

3. Principais Contribuições

1. Sistema Orq: Um sistema completo para análises relacionais complexas no ambiente de MPC terceirizado, suportando junções de múltiplas vias e agregações com fortes garantias de segurança (sem vazamento de tamanhos de resultados).
2. Novo Operador de Junção-Agregação: Uma técnica que decompõe e aplica agregações de forma imediata para limitar os tamanhos dos resultados intermediários, alcançando complexidade $O(n \log n)$ para junções que anteriormente exigiam $O(n^2)$.
3. Primitivas Agnósticas a Protocolos: Uma implementação unificada de operadores oblíquos (junções, ordenações, agregações) que podem ser instanciados com protocolos MPC semi-honestos ou maliciosos.
4. Ordenação Escalável: Implementações de ordenação paralela de dados e vetorizadas que lidam com até 537 milhões de linhas, superando significativamente o estado da arte.
5. Avaliação Abrangente: A primeira execução de ponta a ponta de MPC do benchmark completo TPC-H (Fator de Escala 10) sem vazamento ou computação confiável.

4. Resultados Experimentais

Os autores avaliaram o Orq em implantações LAN e WAN em diversas cargas de trabalho, incluindo o benchmark completo TPC-H e consultas de trabalhos anteriores.

• Desempenho vs. Estado da Arte:
  • Vs. Secrecy: O Orq alcança uma latência até 827$\times$ menor. O Secrecy usa junções $O(n^2)$ e execução de thread única; o Orq usa $O(n \log n)$ e vetorização.
  • Vs. SecretFlow: O Orq é de 1,1$\times$ a 1,5$\times$ mais rápido em consultas de junção e de 58$\times$ a 85$\times$ mais rápido em consultas que não envolvem junção, apesar de o SecretFlow vazar tamanhos de resultados de junção. O Orq alcança isso sem qualquer vazamento.
  • Vs. MP-SPDC: A ordenação do Orq é até 189$\times$ mais rápida devido ao paralelismo de dados.
• Escalabilidade:
  • O Orq processa consultas TPC-H de Fator de Escala 10 (média de 58 milhões de linhas) inteiramente sob MPC.
  • A consulta mais cara (Q21) é concluída em 42 minutos (LAN, segurança maliciosa) e 18 horas (WAN, segurança maliciosa).
  • Protocolos de ordenação escalam para 537 milhões de linhas (Quicksort, SH-HM) e 134 milhões de linhas (Radixsort, Mal-HM).
• Largura de Banda: O Orq exibe até duas ordens de magnitude a menos de consumo de largura de banda comparado ao Secrecy devido a melhorias assintóticas.
• Pré-processamento: O artigo avalia a geração de triplas de Beaver, mostrando que protocolos subquadráticos (Doerner et al.) oferecem economias significativas de largura de banda em relação aos métodos tradicionais, apesar do maior custo computacional.

5. Significância e Alegações

O artigo afirma que o Orq representa um passo significativo para tornar a análise segura prática para análise de dados colaborativa de grande escala no mundo real.

• Quebrando a Barreira Quadrática: O Orq demonstra que a avaliação oblíqua completa e eficiente de junções complexas de múltiplas vias é possível sem vazar tamanhos de resultados ou depender de hardware confiável.
• Praticidade em Escala: Ao executar com sucesso o benchmark completo TPC-H com Fator de Escala 10 (anteriormente alcançável apenas com vazamento ou computação confiável), o Orq prova que o MPC pode lidar com cargas de trabalho de nível empresarial.
• Generalidade: O sistema não é restrito a modelos específicos de propriedade de dados ou modelos de ameaça, suportando tanto adversários semi-honestos quanto maliciosos em ambientes terceirizados.
• Código Aberto: Os autores disponibilizaram o Orq como código aberto para facilitar novas pesquisas e adoção.

Os autores observam que, embora atualmente exijam uma API de fluxo de dados (em vez de um planejador SQL automático), o desempenho e as propriedades de segurança do sistema estabelecem um novo patamar para a análise relacional segura. O trabalho futuro inclui a integração de planejamento de consulta automática e a otimização adicional de verificações maliciosas para ambientes WAN.