Como funcionam as configurações de confiança?

Necessário conhecimento em: curvas elípticas e emparelhamento de curvas elípticas. Veja também: artigo de Dankrad Feist sobre compromissos polinomiais KZG.

Agradecimentos especiais a Justin Drake, Dankrad Feist e Chih-Cheng Liang pelo feedback e revisão.

Muitos protocolos criptográficos, especialmente nas áreas de amostragem de disponibilidade de dados e ZK-SNARKs dependem de configurações de confiança. Uma operação de configuração de confiança é um procedimento que é feito uma vez para gerar um dado que deve ser usado toda vez que algum protocolo criptográfico é executado. A geração destes dados requer algumas informações sigilosas; a "confiança" vem do fato de que alguma pessoa ou algum grupo de pessoas tem que gerar esses códigos, usá-los para gerar os dados, e depois publicar os dados e esquecer os códigos.Mas uma vez que os dados são gerados e os códigos são esquecidos, nenhuma outra participação dos criadores da operação é necessária.

Há muitos tipos de configurações de confiança. O primeiro exemplo de uma configuração de confiança sendo usada em um grande protocolo é a cerimônia do Zcash original em 2016. Esta cerimônia foi muito complexa e exigiu muitas rodadas de comunicação, por isso só pôde ter seis participantes. Todos que usavam Zcash naquele momento estavam efetivamente confiando que pelo menos um dos seis participantes era honesto. Protocolos mais modernos geralmente usam a configuração powers-of-tau, que tem um modelo de confiança de 1-of-N (um para N) com N normalmente nas centenas. Ou seja, centenas de pessoas participam da geração dos dados juntos, e apenas uma delas precisa ser honesta e não publicar seu código secreto para que o produto final seja seguro. Configurações bem executadas como esta são frequentemente consideradas "próximas o suficiente da desconfiança" na prática.

Este artigo explicará como e por que a configuração do KZG funciona e o futuro dos protocolos de configuração de confiança. Qualquer pessoa proficiente em código também deve se sentir livre para acompanhar a implementação deste código: https://github.com/ethereum/research/blob/master/trusted_setup/trusted_setup.py

Como é a configuração powers-of-tau?

Uma configuração de powers-of-tau é composta por duas séries de pontos da curva elíptica que parecem com o seguinte:

[G₁,G₁∗s,G₁∗s²...G₁∗sⁿ¹⁻¹]

[G₂,G₂∗s,G₂∗s²...G₂∗sⁿ²⁻¹]

G₁ e G₂ são os pontos de geração padronizados dos dois grupos de curvas elípticas; em BLS12-381, os pontos G₁ têm (na forma comprimida) 48 bytes de comprimento e os de G₂ têm 96 bytes de comprimento. n₁ e n₂ são os comprimentos dos lados de G₁ e G₂ da configuração. Alguns protocolos requerem n₂=2, outros requerem que n₁ e n₂ sejam ambos grandes, e alguns estão no meio (por exemplo, a amostragem de disponibilidade de dados da Ethereum em sua forma atual requer n₁=4096 e n₂=16). s é o código que é usado para gerar os pontos e precisa ser esquecido.

Para fazer um compromisso KZG para um polinômio P(x)=∑_ic_ixⁱ, nós simplesmente tomamos uma combinação linear ∑_ic_iS_i, onde S_i=G₁∗sⁱ (os pontos da curva elíptica na configuração de confiança). Os pontos G₂ na configuração são usados para verificar as avaliações dos polinômios para os quais foi feito um compromisso; não entrarei na verificação aqui com mais detalhes, no entanto Dankrad fez isso em seu post.

Intuitivamente, qual é o valor que a configuração de confiança está fornecendo?

Vale a pena entender o que está filosoficamente acontecendo aqui, e por que a configuração de confiança está fornecendo valor. Um compromisso polinomial é um comprometimento com uma parte dos dados de tamanho-N, com um objeto de tamanho O(1) (um único ponto da curva elíptica). Poderíamos fazer isso com um simples Pedersen commitment: basta definir os valores S_i para serem pontos da curva elíptica aleatória N que não têm relação conhecida entre si, e se comprometer com os polinômios com ∑_ic_iS_i como antes. E na verdade, é exatamente isso que as provas de avaliação do IPA fazem.

Entretanto, quaisquer provas com base no IPA leva O(N) tempo para verificar e existe uma inevitável razão para isso: um compromisso com um polinômio P(x) usando os pontos de base [S₀,S₁...S_i...S_n−1] comprometiria um polinômio diferente se usássemos os pontos de base [S₀,S₁...(S_i∗2)...S_n−1]

.

Um compromisso válido para o polinômio 3x³+8x²+2x+6 sob um conjunto de pontos básicos é um compromisso válido para 3x³+4x²+2x+6 sob um conjunto diferente de pontos básicos.

Se quisermos fazer uma prova baseada no IPA para alguma afirmação (digamos, que este polinômio avaliado em x=10 é igual a 3826), a prova deve passar com o primeiro conjunto de pontos de base e falhar com o segundo. Portanto, qualquer que seja o procedimento de verificação de provas, não pode evitar de alguma forma levar em conta cada um dos valores Si, e por isso inevitavelmente leva tempo O(N).

Mas com uma configuração de confiança, há uma relação matemática oculta entre os pontos. É garantido que S_i+1=s∗S_i, com o mesmo fator s entre qualquer dos dois pontos adjacentes. Se [S₀,S₁...S_i...S_n−1] é uma configuração válida, a "configuração editada" [S₀,S₁...(S_i∗2)...S_n−1] não pode ser também uma configuração válida. Portanto, não precisamos de computação O(n); em vez disso, aproveitamos esta relação matemática para verificar qualquer coisa que precisemos verificar em tempo constante.

Entretanto, a relação matemática tem que permanecer em segredo: se s é conhecido, então qualquer um poderia assumir um compromisso que representa muitos polinômios diferentes: se C se compromete com P(x), também fica comprometido com P(x) ∗ x/s, ou P(x)− x + s, ou muitas outras coisas. Isto quebraria completamente todas as aplicações de comprometimentos polinomiais. **Portanto, enquanto alguns s secretos devem ter existido em algum momento para tornar possível a ligação matemática entre os valores S_i que permite uma verificação eficiente, os s também devem ter sido esquecidos.

Como funcionam as configurações multiparticipantes?

É fácil ver como um participante pode gerar uma configuração: basta escolher aleatoriamente um s e gerar os pontos da curva elíptica usando esse s. Mas uma configuração de confiança de um único participante é insegura: você tem que confiar em uma pessoa específica!

A solução para isto é configurações de confiança com multi-participantes, onde "multi" quer dizer muitos participantes: mais de 100 é normal, e para configurações menores é possível conseguir mais de 1000. Eis como funciona uma configuração multi-participante da powers-of-tau.

Pegue uma configuração existente (note que você não conhece s, você só conhece os pontos):

[G₁,G₁∗s,G₁∗s₂...G₁∗sⁿ¹⁻¹]

[G₂,G₂∗s,G₂∗s₂...G₂∗sⁿ²⁻¹]

Agora, escolha seu próprio segredo t aleatório.Compute:

[G₁,(G₁∗s)∗t,(G₁∗s₂)∗t²...(G₁∗sⁿ¹⁻¹)∗tⁿ²⁻¹]

[G₂,(G₂∗s)∗t,(G₂∗s₂)∗t²...(G₂∗sⁿ²⁻¹)∗tⁿ²⁻¹]

Observe que isso é equivalente a:

[G₁,G₁∗(st),G₁∗(st)²...G₁∗(st)ⁿ¹⁻¹]

[G₂,G₂∗(st),G₂∗(st)²...G₂∗(st)ⁿ²⁻¹]

Ou seja, você criou uma configuração válida com o segredo s∗t! Você nunca dá seu t aos participantes anteriores, e os participantes anteriores nunca lhe dão seus segredos que entraram em s. E enquanto qualquer um dos participantes for honesto e não revelar sua parte do segredo, o segredo combinado não será revelado. Em particular, os campos finitos têm a propriedade que se você sabe s mas não t, e t é gerado com segurança aleatoriamente, então você não sabe nada sobre s∗t!

Verificando a configuração

Para verificar se cada participante realmente participou, cada participante pode fornecer uma prova que consiste em (i) o ponto G₁∗s que recebeu e (ii) G₂∗t, onde t é o código secreto que eles introduzem. A lista dessas provas pode ser usada para verificar se a configuração final combina todos os segredos (em vez de, digamos, o último participante apenas esquecer os valores anteriores e emitir uma configuração apenas com seu próprio código secreto, que é guardado para poder trapacear em qualquer protocolo que use a configuração).

s₁ é o código secreto do primeiro participante, s₂ é o código secreto do segundo participante etc. A verificação de pareamento em cada etapa prova que a configuração em cada etapa veio realmente de uma combinação da configuração na etapa anterior e de um novo segredo conhecido pelo participante naquela etapa.

Cada participante deve revelar sua prova em algum meio publicamente verificável (por exemplo, site pessoal, transação de seu endereço .eth, Twitter). Note que este mecanismo não impede que alguém alegue ter participado de algum índice onde outra pessoa tenha participado (assumindo que outra pessoa tenha revelado sua prova), mas geralmente considera-se que isto não importa: se alguém está disposto a mentir sobre ter participado, também estaria disposto a mentir sobre ter apagado seu código secreto. Desde que pelo menos uma das pessoas que afirmam publicamente ter participado seja honesta, a configuração é segura.

Além da verificação acima, também queremos verificar se todas as atribuições na configuração estão construídas corretamente (ou seja, são atribuições do mesmo código secreto). Para isso, poderíamos fazer uma série de verificações de pareamento, verificando que e(S_i+1,G₂)=e(S_i,T₁) (onde T₁ é o valor G₂∗s na configuração) para todo i. Isso verifica que o fator entre cada S_i e S_i+1 é o mesmo que o fator entre T₁ e G₂. Podemos então fazer o mesmo no lado G₂.

Mas, isso é muito pareamento e é caro. Em vez disso, tomamos uma combinação linear aleatória L₁=∑_i=0^n₁−2r_iS_i, e a mesma combinação linear substituída por uma: L₂=∑_i=0^n₁₋₂r_iS_i+1. Usamos uma única verificação de pareamento para verificar se eles coincidem: e(L₂,G₂)=e(L₁,T₁).

Podemos até combinar o processo para o lado G₁ e o lado G₂ juntos: além de calcular L₁ e L₂ como acima, também calculamos L₃= ∑_i=0^n₂-2q_iT_i (q_i é outro conjunto de coeficientes aleatórios) e L₄=∑_i=0^n₂-2q_iT_i+1, e verificamos se e(L₂,L₃)=e(L₁,L₄).

.

Configurações no método de Lagrange

Em muitos casos de uso, não se quer trabalhar com polinômios em forma de coeficiente (ex. P(x)=3x³+8x²+2x+6), se quer trabalhar com polinômios em forma de avaliação (ex. P(x) é o polinômio que avalia a [19,146,9,187] no domínio [1,189,336,148] módulo 337). A forma de avaliação tem muitas vantagens (por exemplo, você pode multiplicar e às vezes dividir os polinômios no tempo O(N)) e você pode até usá-lo para avaliar no tempo O(N). Em particular, a amostragem da disponibilidade de dados espera que os blobs (coleção de dados binários armazenados como uma única entidade em um sistema de gerenciamento de banco de dados) estejam no formulário de avaliação.

Para trabalhar com estes casos, muitas vezes é conveniente converter a configuração de confiança em formulário de avaliação. Isto lhe permitiria tomar as avaliações ([19.146.9.187] no exemplo acima) e usá-las para computar o comprometimento diretamente.

Isso é feito de forma mais fácil com o Fast Fourier transform (FFT), mas passando os pontos da curva como input, em vez de números. Evitarei repetir aqui uma explicação completa e detalhada das FFTs, mas aqui está uma implementação; na verdade, não é tão difícil assim.

O futuro das configurações de confiança

A powers-of-tau não é o único tipo de configuração de confiança que existe. Algumas outras configurações de confiança importantes (reais ou potenciais) incluem:

• As mais complicadas configurações nos antigos protocolos ZK-SNARK (ex. veja aqui), que ainda são utilizadas algumas vezes (particularmente Groth16) porque a verificação é mais barata que o PLONK.
• Alguns protocolos criptográficos (ex. DARK) dependem de grupos hidden-order, onde não se sabe o número pelo qual um elemento pode ser multiplicado para obter o elemento zero. Existem versões totalmente não confiáveis (veja: class groups), mas de longe a versão mais eficiente utiliza grupos RSA, potências de x mod n=pq onde p e q não são conhecidos). Cerimônias de configurações de confiança para isto com 1-of-n premissas de confiança são possíveis, mas são muito complicadas para implementar.
• Se/quando a ofuscação de indistinguibilidade se torna viável, muitos protocolos que dependem dela envolverão alguém criando e publicando um programa ofuscado que faz algo com um segredo interno oculto. Esta é uma configuração de confiança: o(s) criador(es) precisaria(m) possuir o código secreto para criar o programa, e precisaria(m) apagá-lo posteriormente.

A criptografia continua a ser um campo em rápida evolução, e como as configurações de confiança são importantes, poderia facilmente mudar. É possível que as técnicas para trabalhar com IPAs e idéias do tipo Halo se aperfeiçoem ao ponto de tornar KZG ultrapassado e desnecessário, ou que os computadores quânticos tornem qualquer coisa baseada em curvas elípticas inviáveis daqui a dez anos e que fiquemos presos a trabalhar com protocolos baseados em hash sem configuração de confiança. Também é possível que o que pudermos fazer com KZG se aprimore ainda mais rápido, ou que surja uma nova área de criptografia que dependa de um tipo diferente de configuração de confiança.

Na medida em que cerimônias de configuração de confiança são necessárias, é importante lembrar que nem todas as configurações de confiança são criadas de uma mesma forma. 176 participantes é melhor do que 6, e 2000 deve ser ainda melhor. Uma cerimônia pequena o suficiente que pode ser executada dentro de um browser ou um aplicativo no telefone (ex. a configuração ZKopru tem por base a web) poderia atrair muito mais participantes do que uma cerimônia que requeira executar um pacote de software complicado. Cada cerimônia deve, de preferência, ter participantes executando múltiplas implementações de software construídas independentemente e executando diferentes ambientes e sistemas operacionais, para reduzir riscos de erros de modo comum. Cerimônias que requerem apenas uma rodada de interação por participante (como a powers-of-tau) são muito melhores do que cerimônias com múltiplas rodadas, tanto devido à capacidade de apoiar muito mais participantes quanto devido à maior facilidade de escrever múltiplas implementações. As cerimônias deveriam ser de preferência universais (o resultado de uma única cerimônia podendo apoiar uma ampla variedade de protocolos). Estas são todas as coisas pelas quais podemos e devemos continuar trabalhando, para garantir que as configurações confiáveis possam ser tão seguras e confiáveis quanto possível.

Março de 2022. Veja todos os posts aqui

Este artigo foi escrito por vitalik.ca e traduzido por Fátima Lima. O artigo original pode ser lido aqui.