Ir para o conteúdo
Financial Context Wiki

Acumuladores criptográficos

Um guia de acumuladores criptográficos voltado à verificação, que aborda projetos baseados em RSA e hash, testemunhas de pertinência e não pertinência, atualizações dinâmicas, usos em blockchains e riscos operacionais.

Atualizado

Somente para fins educacionais; isto não constitui aconselhamento de investimento nem de implementação criptográfica. Uma prova de acumulador autentica uma afirmação em relação a um compromisso, não os dados subjacentes, o estado de consenso nem a disponibilidade dos dados.

Resposta direta

Um acumulador criptográfico vincula um compromisso a um conjunto por meio de um valor curto e permite que um verificador confira, com uma testemunha concisa, se um elemento pertence ao conjunto comprometido. Alguns esquemas também provam a não pertinência. O verificador precisa do valor do acumulador, do elemento, da testemunha e dos parâmetros públicos do esquema, mas não de todos os outros elementos do conjunto.

Um acumulador é estático quando precisa ser reconstruído após uma alteração no conjunto, dinâmico quando adições ou exclusões permitem atualizar o acumulador e as testemunhas com eficiência e universal quando admite provas tanto de pertinência quanto de não pertinência. Esses rótulos descrevem capacidades distintas; um esquema dinâmico não é necessariamente universal.

Blockchains podem vincular compromissos a transações, saídas não gastas, contas, validadores ou registros de revogação. Um compromisso menor pode reduzir o estado mantido por alguns participantes, mas o sistema ainda precisa distribuir os dados subjacentes e as testemunhas atuais, autenticar as atualizações, lidar com reorganizações da cadeia e definir quem pode alterar o conjunto.

Como funciona

  1. Especifique o conjunto com precisão. Defina a codificação canônica dos elementos, o tratamento de duplicatas, as regras de ordenação quando pertinentes, a separação de domínios e a versão exata do compromisso. Uma prova referente a uma codificação ou raiz de estado não afirma nada sobre outra.

  2. Execute a configuração do esquema. Um acumulador baseado em hash pode usar apenas parâmetros públicos de hash. Um acumulador RSA usa um grupo de ordem desconhecida, normalmente derivado de um módulo RSA N; a segurança exige que partes não autorizadas não consigam explorar sua fatoração. Outros esquemas podem usar emparelhamentos, grupos de classes, reticulados ou parâmetros públicos adicionais com diferentes pressupostos de confiança.

  3. Mapeie os elementos para a álgebra. Em uma construção RSA simplificada, cada elemento x_i é mapeado de maneira determinística para um representante primo distinto p_i. Com a base g, o acumulador é:

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. Crie uma testemunha de pertinência. Para o elemento representado por p_i, omita seu fator do expoente:

    w_i = g^(product of p_j for all j != i) mod N

  5. Verifique em relação ao acumulador exato. O verificador confere as entradas canônicas e calcula:

    w_i^(p_i) mod N = A

    Segundo o pressuposto de segurança do esquema, deve ser inviável produzir essa igualdade para um elemento fora do conjunto acumulado. A igualdade não demonstra que o próprio elemento seja verdadeiro ou autorizado.

  6. Processe separadamente as atualizações e a não pertinência. Esquemas dinâmicos definem como adições e exclusões alteram A e como as testemunhas afetadas são atualizadas. Esquemas universais acrescentam uma testemunha de não pertinência e um algoritmo de verificação distintos. As implementações devem rejeitar testemunhas desatualizadas e atualizações vinculadas a outro estado.

  7. Compare as estruturas baseadas em hash por seus custos reais. Uma árvore de Merkle é um acumulador baseado em hash em sentido amplo: sua raiz é curta, enquanto uma prova de pertinência contém os hashes irmãos ao longo de um caminho e, portanto, cresce de forma logarítmica com o número de folhas. Esquemas do tipo RSA podem oferecer testemunhas individuais de tamanho constante, mas a geração de provas, a manutenção de testemunhas, a configuração e o processamento têm custos diferentes.

Exemplos práticos

  • Tamanho da prova de Merkle. Uma árvore de Merkle binária balanceada com 1,048,576 = 2^20 folhas precisa de 20 hashes irmãos para um caminho de inclusão. Com hashes de 32 bytes, isso corresponde a 20 * 32 = 640 bytes antes dos dados da folha, dos bits de posição e da sobrecarga de serialização. A raiz permanece com 32 bytes.
  • Tamanho constante não significa trabalho constante. Na construção RSA simplificada, A e cada w_i continuam sendo um único elemento do grupo à medida que o conjunto cresce. O expoente formado pelo produto, a geração de representantes primos, as atualizações em lote e a distribuição de testemunhas atualizadas ainda podem exigir processamento ou dados auxiliares substanciais.
  • Um acumulador de UTXO muda quem armazena o quê. Um nó de estado compacto pode manter um acumulador de saídas não gastas e validar um gasto somente quando recebe a saída junto com uma prova de pertinência atual. Outros participantes ainda precisam manter estado suficiente para produzir essas provas, e as atualizações devem remover as saídas gastas e adicionar as recém-criadas.
  • A revogação segue o mesmo limite. O titular de uma credencial pode provar que um identificador permanece em um acumulador de membros ativos ou usar um projeto universal para provar que ele está ausente de um conjunto de revogação. A prova autentica o conjunto com o qual o emissor se comprometeu; ela não prova que o emissor aplicou uma política de revogação justa ou correta.

Riscos

  • Usar codificações de elementos ambíguas ou não canônicas, permitindo que o mesmo item lógico seja representado de maneiras diferentes.
  • Mapear elementos incorretamente para representantes primos ou sem os controles de colisão exigidos pelo esquema.
  • Confiar em um módulo RSA cuja fatoração possa ser conhecida pela parte responsável pela configuração ou por um invasor.
  • Considerar segura uma cerimônia de configuração multipartidária sem verificar sua transcrição, os pressupostos sobre os participantes e a vinculação dos parâmetros.
  • Permitir que um administrador substitua parâmetros públicos ou versões do acumulador sem regras de migração autenticadas.
  • Verificar uma testemunha em relação a um valor de acumulador desatualizado, não finalizado ou escolhido por um invasor.
  • Aplicar uma adição, exclusão ou atualização de testemunha proveniente do bloco, bifurcação, época ou versão do conjunto errados.
  • Presumir que uma testemunha de pertinência também prova a validade, a propriedade, a autorização ou o valor econômico do elemento.
  • Presumir que um compromisso curto torna o conjunto subjacente disponível ou recuperável.
  • Perder os dados ou o serviço necessários para construir testemunhas atuais, tornando inutilizável um estado válido.
  • Omitir o suporte à não pertinência enquanto uma aplicação depende implicitamente de provas de ausência.
  • Confundir um caminho de Merkle, uma testemunha RSA, uma abertura polinomial e uma prova de validade como se fossem objetos intercambiáveis.
  • Ignorar os custos de exclusão, o tráfego de atualização de testemunhas, a latência de geração de provas ou entradas de negação de serviço.
  • Deixar de vincular as provas a um protocolo, uma cadeia, um contrato, uma raiz de estado, um domínio e uma versão de serialização.
  • Depender de uma única implementação não auditada ou de aritmética personalizada sem vetores de teste independentes.
  • Presumir que a segurança clássica de RSA, emparelhamento ou logaritmo discreto continuará segura contra um computador quântico criptograficamente relevante.

Equívocos comuns

  • O acumulador contém uma cópia compactada do conjunto. Ele é um compromisso vinculante, não um arquivo reversível.
  • Todo acumulador prova a ausência. A não pertinência exige um esquema projetado e verificado para essa capacidade.
  • Uma testemunha de tamanho constante proporciona custo total constante. A configuração, a geração de provas, as atualizações, o armazenamento e a distribuição de testemunhas continuam sendo custos distintos.
  • Sem estado significa que ninguém armazena estado. Alguns participantes precisam manter ou reconstruir dados suficientes para criar elementos, atualizações e testemunhas.
  • Uma prova válida torna verdadeiro o item comprometido. Ela apenas vincula o item a um compromisso autenticado sob pressupostos específicos.
  • Árvores de Merkle e acumuladores RSA têm o mesmo perfil de confiança e desempenho. Eles compartilham a finalidade de vincular um compromisso a um conjunto, mas usam pressupostos, tamanhos de prova, procedimentos de atualização e modos de falha diferentes.

Tópicos relacionados

Fontes

Navegação

Pesquisar na wiki...