Provas de conhecimento zero: uma introdução aos fundamentos

Introdução

As provas de conhecimento zero estão entre as ferramentas mais poderosas criadas por criptógrafos. Infelizmente, a maioria das pessoas não as compreende. Este artigo busca mudar isso apresentando uma visão abrangente das provas de conhecimento zero com base em seus princípios fundamentais. Abordaremos a teoria, a matemática e a criptografia por trás dessas provas para que qualquer pessoa possa entender os avanços mais recentes na Solana, especificamente ZK Compression e o futuro da interoperabilidade.

Este artigo pressupõe conhecimento do modelo de programação da Solana e das primitivas criptográficas inerentes a sistemas blockchain (ou seja, funções hash, ponteiros hash, árvores de Merkle e árvores de Merkle concorrentes). Se esses conceitos forem novos para você, recomendo ler primeiro estas publicações anteriores do blog:

• Fundamentos das ferramentas criptográficas — explicação sobre funções hash e árvores de Merkle
• O modelo de programação da Solana: uma introdução ao desenvolvimento na Solana

Este artigo foi elaborado com modularidade em mente. Recomenda-se que leitores sem familiaridade com esses temas leiam cada seção e subseção em sequência. Porém, se você já conhecer determinados assuntos ou quiser aprender sobre um tema específico, poderá acessar diretamente a seção correspondente sem problemas.

Este também é o primeiro artigo de uma série de duas partes sobre provas de conhecimento zero. É altamente recomendável ler este artigo antes de seguir para Provas de conhecimento zero: suas aplicações na Solana.

A teoria por trás das provas de conhecimento zero

Em 1989, os pesquisadores do MIT Shafi Goldwasser, Silvio Micali (fundador da Algorand) e Charles Rackoff publicaram A complexidade do conhecimento em sistemas de prova interativos. Eles trabalhavam em sistemas nos quais uma parte (o provador) troca mensagens com outra parte (o verificador) para convencê-la de que uma afirmação matemática é verdadeira. Foram os primeiros a perguntar: “E se nem o provador nem o verificador confiarem um no outro?” A preocupação é quanta informação, além do fato de a afirmação ser verdadeira, o verificador obterá durante essa troca de mensagens. Por exemplo, o provador pode querer convencer o verificador de que conhece a solução de um quebra-cabeça complexo sem revelar a solução em si.

Afinal, que tipo de problema estamos tentando resolver?

Tricoloração de grafos

A tricoloração de grafos é um problema clássico da ciência da computação e da teoria dos grafos. Ela consiste em colorir os vértices de um grafo com três cores, de modo que nenhum vértice adjacente tenha a mesma cor. Em um grafo com três vértices, isso é simples. No entanto, à medida que aumentamos o número de vértices, a tarefa fica cada vez mais difícil.

Uma aplicação prática seria a elaboração de horários universitários. Em uma universidade grande, os horários precisam ser organizados para que nenhum aluno tenha aulas simultâneas. Cada disciplina pode ser representada como um vértice em um grafo, enquanto as arestas representam alunos em comum entre as disciplinas. Isso garante que duas disciplinas com um aluno em comum não sejam agendadas para o mesmo horário. Há ainda restrições relacionadas à capacidade das salas, aos horários preferidos dos professores e à distribuição uniforme das aulas ao longo da semana. Portanto, horários e salas devem ser atribuídos às disciplinas de modo que duas disciplinas adjacentes não ocupem o mesmo horário. Isso pode ser feito com a tricoloração de grafos.

Agora, imagine que o cronograma final precise ser verificado por uma empresa de auditoria externa. Devido a regulamentações específicas de privacidade, a universidade não pode compartilhar com os auditores informações detalhadas sobre a matrícula dos alunos. Em vez disso, ela precisa provar que o cronograma final atende às restrições exigidas sem revelar quais alunos estão matriculados em cada disciplina. 

Para isso, a universidade precisa criar um grafo no qual cada vértice represente uma disciplina. Uma aresta seria traçada entre dois vértices se as disciplinas correspondentes tivessem pelo menos um aluno em comum. A universidade atribuiria horários a cada disciplina para garantir que duas disciplinas adjacentes não fossem agendadas simultaneamente. Em seguida, ela assumiria um compromisso com o cronograma final usando um esquema de compromisso criptográfico. Isso envolve criar um hash criptográfico do horário atribuído a cada disciplina e compartilhar os hashes com o verificador sem revelar os horários. A empresa de auditoria externa selecionaria aleatoriamente pares de disciplinas adjacentes para questionar os horários atribuídos. A universidade revelaria os horários comprometidos do par selecionado e forneceria os compromissos originais (ou seja, os hashes), permitindo que a empresa verificasse os valores revelados. As últimas etapas de questionamento, revelação e verificação seriam repetidas até que a empresa de auditoria externa estivesse convencida de que não há sobreposição de aulas. Recomendo muito a demonstração interativa de tricoloração com conhecimento zero do MIT para ver essas etapas acontecendo em tempo real.

A universidade quer provar à empresa de auditoria externa que conhece um cronograma correto. Ou seja, ela quer provar a outra parte que possui determinado conhecimento. O interessante desse problema é que ele é NP-completo.

NP-completo

Na teoria da complexidade computacional, um problema é NP-completo quando:

• Para qualquer entrada do problema, a saída é “sim” ou “não”
• Quando a resposta é “sim”, ela pode ser demonstrada com uma solução curta
• Deve ser possível verificar rapidamente se cada solução está correta, e um algoritmo de força bruta pode encontrar uma solução testando todas as possibilidades

Problemas NP-completos são importantes porque representam os problemas mais difíceis da classe NP (ou seja, um grupo de quebra-cabeças muito difíceis nos quais é fácil verificar uma solução proposta em tempo polinomial, mas difícil encontrá-la). Esses problemas se destacam por sua capacidade universal de simulação. Isto é, se conseguirmos resolver rapidamente um problema NP-completo, poderemos reduzir ou transformar qualquer problema NP em um problema NP-completo e encontrar sua solução em tempo polinomial. Verificar soluções de problemas NP-completos também é fácil. 

Assim, temos uma classe inteira de problemas que podemos provar de forma eficiente com provas de conhecimento zero. Por exemplo:

• Problema do caixeiro-viajante — Dada uma lista de cidades e as distâncias entre cada par, encontrar a rota mais curta possível que visite cada cidade uma vez e retorne à cidade de origem. Esse problema tem inúmeras aplicações em logística, planejamento de rotas, manufatura e gestão da cadeia de suprimentos
• Problema da mochila — Dado um conjunto de itens, determinar quantas unidades de cada item incluir em uma coleção para que o peso total seja menor ou igual a um limite definido e o valor total seja o maior possível. Esse é um problema comum nas áreas de finanças e alocação de recursos
• Agendamento de tarefas — Dado um conjunto de tarefas com durações e prazos específicos, agendá-las em uma única máquina para minimizar a penalidade total por atrasos. Isso tem diversas aplicações em computação, manufatura e gerenciamento de projetos

Além disso, o teorema de Cook-Levin afirma que o problema de satisfatibilidade booleana é NP-completo. Ou seja, qualquer problema cujas variáveis possam ser substituídas por valores verdadeiros ou falsos de modo que o resultado final seja verdadeiro pode ser transformado em um problema NP-completo. Isso implica que qualquer problema que possamos reduzir a uma série de perguntas de verdadeiro ou falso pode ser provado de forma eficiente com provas de conhecimento zero.

Propriedades de uma prova de conhecimento zero

Diante da complexidade e da importância dos problemas NP-completos, torna-se essencial provar soluções para essa classe de problemas de forma eficiente e segura. As provas de conhecimento zero oferecem um método para isso sem comprometer a privacidade das informações envolvidas. Goldwasser, Micali e Rackoff propuseram que todas as provas de conhecimento zero devem atender às seguintes propriedades:

• Completude — o Provador acabará convencendo o Verificador se for honesto
• Solidez — um Provador desonesto nunca convencerá um Verificador de uma afirmação falsa
• Conhecimento zero — a interação entre Provador e Verificador revela apenas se uma afirmação é verdadeira, e nada mais

Ao aproveitar as propriedades robustas das provas de conhecimento zero, podemos provar fatos ou o conhecimento de determinadas informações em vários contextos, preservando a privacidade e mantendo a precisão. Nas próximas seções, veremos por que isso é tão valioso para aplicações que exigem altos níveis de segurança e eficiência, como blockchains.

Interativas versus não interativas

As provas de conhecimento zero costumam seguir a mesma estrutura de três etapas:

• O provador gera uma solução para a computação (ou seja, a testemunha) e envia um compromisso com a resposta da testemunha
• O verificador responde com um valor de desafio gerado aleatoriamente
• O provador calcula a prova final com base no compromisso e no desafio

Essa estrutura é inerentemente interativa: o provador afirma que sabe algo, e o verificador o desafia continuamente até que a probabilidade de ser enganado seja insignificante. Isso não é ideal para a maioria das aplicações, pois o provador precisa de uma ou mais respostas antes de gerar a prova completa. Essa configuração apresenta os seguintes desafios:

• O verificador pode conspirar com o provador, permitindo a falsificação de provas
• O verificador pode criar provas falsas
• O verificador precisa armazenar seus valores secretos em algum lugar, o que pode deixá-los vulneráveis a vazamentos ou ataques

A heurística de Fiat-Shamir é uma técnica para transformar uma prova interativa de conhecimento em uma assinatura digital baseada nela. Assim, um fato pode ser provado publicamente sem revelar as informações subjacentes. A ideia é que, em vez de o verificador enviar um valor de desafio aleatório ao provador, o próprio provador pode calcular essa assinatura digital usando uma função aleatória, como uma boa função hash criptográfica. Portanto, em vez de o verificador inspecionar a computação em 500 pontos diferentes para confirmar que todos estão corretos, o provador calcula uma raiz de Merkle da computação, usa essa raiz para selecionar 500 índices de forma pseudoaleatória e fornece os 500 ramos de Merkle correspondentes. A ideia central é que o provador não sabe quais ramos precisará revelar até que os dados tenham sido comprometidos.

O leitor atento pode perceber uma falha fatal no uso de amostragem aleatória para verificar computações por partes: a computação é inerentemente frágil. Um provador mal-intencionado poderia inverter um único bit no meio da computação sem que o verificador jamais descobrisse. Como o verificador pode conferir cada parte da computação sem examinar cada uma individualmente? Polinômios.

No entanto, precisamos entender uma boa quantidade de matemática antes de falar sobre polinômios.

A matemática por trás das provas de conhecimento zero

Esta não pretende ser uma introdução abrangente aos campos matemáticos a seguir — cada uma destas seções poderia ser um artigo inteiro. O objetivo é oferecer uma breve introdução para que você comece a entender os fundamentos matemáticos das provas de conhecimento zero e, em linhas gerais, como elas realmente funcionam.

Este artigo também apresentará a notação matemática adequada. Por exemplo, na subseção seguinte sobre teoria dos conjuntos, apresentaremos os símbolos ∈, ∉ e ⊆. No fim das contas, todos esses símbolos são representações de outra coisa. Provas de conhecimento zero não são um tema para iniciantes; por isso, a grande maioria dos artigos sobre o assunto não é acessível para iniciantes. Eles não explicarão o significado desses símbolos, e partirão do princípio de que o leitor compreende essa notação. Apresentar essa notação agora é essencial para torná-la menos assustadora para quem quiser se aprofundar em provas de conhecimento zero. Tente não se perder na notação. Persista, pois chegará o momento em que você olhará para esses símbolos e verá os conceitos subjacentes, em vez de apenas uma letra grega.

Teoria dos conjuntos

A teoria dos conjuntos é um ramo da matemática que estuda coleções de objetos. Um conjunto é uma coleção de objetos distintos. Esses objetos são chamados de elementos, ou membros, do conjunto. Por exemplo, considere uma coleção de frutas:

Chaves são usadas na notação de conjuntos para delimitar uma coleção de elementos e representar um conjunto. Assim, sabemos que maçã, laranja, pera e banana fazem parte do conjunto, mas algo como “batata” não faz. O símbolo ∈ indica pertinência a um conjunto e é lido como “é um elemento de”. Da mesma forma, ∉ indica que um elemento não pertence a determinado conjunto. Portanto, podemos dizer:

Leríamos isso como “maçã é um elemento do conjunto Fruit, e batata não é um elemento do conjunto Fruit”.

Subconjuntos

Também podemos ter conjuntos formados por outros conjuntos. Um subconjunto é um conjunto que contém apenas elementos encontrados em outro conjunto. Por exemplo, se tivéssemos:

Podemos dizer que o conjunto Citrus é um subconjunto do conjunto maior AllFruits. Também poderíamos usar nosso conjunto Fruit anterior para dizer que Fruit é um subconjunto do conjunto maior AllFruit. Na notação de conjuntos, escreveríamos:

Por que isso é importante?

A teoria dos conjuntos é essencial para entender os conceitos de intervalos e restrições. Nas próximas seções, sobre teoria dos números e aritmética modular, exploraremos a ideia de números contidos em determinado intervalo. Por exemplo, podemos ter um conjunto de valores possíveis para uma chave criptográfica:

Aqui, K define o intervalo de todas as chaves possíveis. Podemos construir nossas provas de conhecimento zero aplicando determinadas restrições a esse conjunto, para que apenas certos valores sejam válidos. Por exemplo, poderíamos dizer que a chave deve ser um número entre 1 e 5. 

Assim, a teoria dos conjuntos fornece a linguagem, as ferramentas e a notação fundamentais para definir e analisar conjuntos de possíveis entradas, saídas e estados em protocolos criptográficos. Em provas de conhecimento zero, muitas vezes precisamos provar que um elemento pertence a um conjunto ou intervalo específico sem revelar o próprio elemento.

Recomendo acessar a Khan Academy para conferir excelentes exercícios sobre notação básica de conjuntos.

Teoria dos números

A teoria dos números é um ramo da matemática que estuda números inteiros e funções aritméticas. Podemos definir os inteiros como um conjunto de números sem parte fracionária, incluindo números positivos, negativos e zero. Mais formalmente, podemos definir o conjunto dos inteiros como:

Aqui, ℤ representa o conjunto dos inteiros, e as reticências mostram que os inteiros vão do infinito negativo ao infinito positivo. Por exemplo, 12 é um número inteiro, e -1978649832794275 também é.

Números racionais

Números racionais são números que podemos expressar como uma fração cujo denominador (ou seja, o número abaixo da linha em uma fração comum, um divisor) não seja zero. Por exemplo, $(\frac{1}{2}), 74, (\frac{2}{3})$ são todos números racionais. Podemos definir os números racionais mais formalmente como um conjunto de números que podem ser expressos pela fração pq, em que p é o numerador, q é o denominador e q não é 0. O símbolo ℚ representa os números racionais. Na notação de conjuntos, escreveríamos:‍

‍Embora isso possa parecer assustador à primeira vista, é exatamente o que a frase anterior descreve. Leríamos esse estranho jargão matemático como “Q é o conjunto de todas as frações p sobre q, em que p e q são inteiros e q não é igual a zero”. 

Números reais

Os números reais abrangem tanto os números racionais quanto os irracionais. Números irracionais são aqueles que não podem ser expressos como uma fração simples e têm casas decimais infinitas e não periódicas. Por exemplo, pi (ou seja, π) e $\sqrt{2}$ (ou seja, 1.4.1421…) são números irracionais. Por enquanto, não abordaremos a notação de conjuntos, mas observe que os números reais são representados pelo símbolo ℝ.

Por que isso é importante?

A teoria dos números está profundamente ligada à teoria dos conjuntos, pois envolve o estudo de conjuntos específicos de números, como os números racionais. Esses conjuntos costumam ser a base para definir intervalos e restrições em problemas matemáticos e criptográficos. 

Também podemos ver como a teoria dos números e a teoria dos conjuntos estão conectadas. Por exemplo, podemos dizer que o conjunto de todos os inteiros ℤ é um subconjunto dos números racionais ℚ. Isso fica evidente em nossa definição de números reais na notação de conjuntos acima, quando afirmamos que numerador e denominador são inteiros.

Aritmética modular

A aritmética modular, também conhecida como aritmética do relógio, é um sistema de operações numéricas com inteiros no qual os números “dão a volta” depois de alcançar um valor específico, conhecido como módulo. A ideia é trabalhar com os primeiros n números positivos, em vez de um conjunto infinito de números.

Relógios

Considere um relógio analógico (detesto ter de especificar, nos dias de hoje, que ele tem ponteiros e não é digital) com os números de 1 a 12. Se fossem 11 horas e quiséssemos saber o horário dali a duas horas, não chegaríamos às 13 horas. Em vez disso, daríamos a volta até 1 hora. Isso pode ser expresso como $11 + 2 \equiv 1 \pmod{12}$ . A expressão matemática correta seria $13 \bmod 12 = 1$. Programadores reconhecerão o uso da operação módulo no formato $13 \% 12 = 1$.

Operação módulo

Quando escrevemos n mod k, queremos o resto da divisão de n por k. Isso é conhecido como operação módulo. Por exemplo:

• 25 mod 3 significa dividir 25 por 3, o que resulta em resto 1, pois $25 = 8 \times 3 + 1$
• 15 mod 4 significa dividir 15 por 4, o que resulta em resto 3, pois $15 = 3 \times 4 + 3$

Na aritmética modular, o resto é sempre não negativo.

Por que isso é importante?

Entender a aritmética modular é essencial porque ela ajuda a compreender o comportamento dos números sob restrições, algo valioso para a criptografia. A aritmética modular fundamenta muitos algoritmos criptográficos e é usada em toda a ciência da computação, na engenharia e em qualquer área que exija manipulação e criptografia seguras de dados.

Considere a computação x + y = z. Se estivermos trabalhando com um corpo finito definido por um número primo p = 17 (abordaremos isso em breve; por enquanto, pense nele como o conjunto de todos os inteiros de 0 a 16 que dá a volta ao chegar a 17), a computação seria (x + y) mod p = z nesse corpo. Se x = 12 e y = 15, a computação seria:‍

O uso da aritmética modular nos permite realizar computações dentro de um intervalo de valores gerenciável, definido pelo número primo p. Isso é particularmente importante porque computadores e processadores têm espaço limitado. Por isso, normalmente trabalhamos com inteiros de tamanho fixo, como u32 ou u64. A aritmética modular garante que nossos valores permaneçam dentro desses limites. Além disso, o uso de números primos acrescenta uma camada de complexidade. Isso é essencial do ponto de vista criptográfico, pois aumenta a segurança e torna determinadas propriedades matemáticas mais previsíveis e confiáveis.

Por exemplo, a aritmética modular é usada em zk-SNARKs para garantir que os valores calculados permaneçam dentro de limites específicos e gerenciáveis. Ela também é usada para criar circuitos aritméticos sobre um determinado conjunto de números. Isso permite expressar computações e garantir que possam ser verificadas com eficiência. Nesse caso, o provador precisaria provar que realizou a computação sem revelar os valores de x, y e z.

Recomendo muito consultar a lista de problemas da Art of Problem Solving e os exercícios de aritmética modular de Joseph Zoller para adquirir mais experiência prática na resolução de problemas de aritmética modular. 

Teoria dos grupos

A teoria dos grupos é um ramo da matemática que estuda estruturas algébricas conhecidas como grupos. Um grupo é um conjunto de elementos com uma operação que satisfaz as condições a seguir, conhecidas como axiomas de grupo:

• Fechamento — O resultado de qualquer cálculo aritmético será outro elemento do conjunto
• Associatividade — Ao realizar a mesma operação em três ou mais elementos, a forma de agrupá-los não importa; o resultado será o mesmo
• Elemento neutro — Existe um elemento sobre o qual você pode realizar uma operação com qualquer outro elemento sem alterar seu valor
• Elemento inverso — Existe um elemento sobre o qual você pode realizar uma operação com outro elemento, resultando no elemento neutro

Formalmente, eles são definidos assim:

• Fechamento — Se a e b pertencem ao grupo, o resultado da operação (geralmente representada como $a \times b$, $ab$, $a \circ b$, ou $ab$) também pertence ao grupo. Formalmente, podemos escrever $\forall a, b \in G \mid a \circ b \in G$. Podemos ler isso como: “para todos os valores dos elementos a e b no conjunto G, o resultado da operação entre a e b está em G”
• Associatividade — Se a, b e c pertencem ao grupo, então (ab)c = a(cb). Formalmente, podemos escrever $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Podemos ler isso como: “para todos os valores dos elementos a, b e c no conjunto G, a operação de a e b seguida de c é igual à operação de a seguida da operação de b e c
• Elemento neutro — Existe um elemento e no grupo tal que, para todo elemento a do grupo, vale a operação $e \circ a = a \circ e = a$. Formalmente, escreveríamos $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Podemos ler isso como “existe um elemento e no conjunto G em que, para cada elemento a do conjunto G, a operação de e seguida de a é igual à operação de a seguida de e, que é igual a a
• Elemento inverso — Para cada elemento a do grupo, existe um elemento b no grupo tal que $a \circ b = b \circ a = e$, em que e é o elemento neutro. Formalmente, escreveríamos $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Podemos ler isso como “para todos os valores dos elementos a no conjunto G, existe um elemento b no conjunto G em que a operação de a seguida de b é igual à operação de b seguida de a, que é igual ao elemento neutro

Podemos tornar todo esse jargão matemático mais compreensível com um exemplo. Considere o conjunto dos inteiros sob a operação de adição. Podemos dizer que esse conjunto forma um grupo porque satisfaz os quatro axiomas de grupo:

• Fechamento — Se você somar dois inteiros, obterá outro inteiro
• Associatividade — $(5 + 4) + 3 = 5 + (4 + 3)$
• Elemento neutro — O número zero é considerado o elemento neutro porque somar zero a qualquer inteiro não altera seu valor. Por exemplo, $7 + 0 = 0 + 7 = 7$
• Elemento inverso — O inverso de qualquer inteiro é seu oposto, pois a soma dos dois resulta no elemento neutro. Por exemplo, $5 + (-5) = 0$. Podemos generalizar isso como $n + (-n) = 0$

Também podemos ampliar isso para um exemplo mais difícil, como o conjunto dos números racionais diferentes de zero $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ sob a operação de multiplicação. Isso também forma um conjunto:

• Fechamento — Multiplicar dois números racionais diferentes de zero resulta em outro número racional diferente de zero
• Associatividade — $ab \times cd \times ef = ab \times (cd \times ef)$
• Elemento neutro — O número 1 é considerado o elemento neutro porque multiplicar qualquer número racional diferente de zero por um não altera seu valor. Por exemplo, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemento inverso — O inverso de qualquer número racional diferente de zero é seu recíproco (ou seja, basta trocar o numerador e o denominador), pois o resultado será 1, o elemento neutro. Por exemplo, $\frac{3}{5} \times \frac{5}{3} = 1$

Subgrupos

Um subgrupo é um grupo dentro de outro grupo. Para dizer que o subgrupo H do grupo G é um subconjunto de G, precisaríamos satisfazer os seguintes axiomas de grupo:

• Fechamento — Se a e b estão em H, o resultado da operação entre eles também deve estar em H
• Associatividade — Esse axioma é herdado do grupo maior G 
• Elemento neutro — O elemento neutro de G também deve estar em H 
• Elemento inverso — Para cada elemento a em H, deve haver algum elemento b também em H tal que ab e ba sejam iguais ao elemento neutro

O exemplo clássico é o conjunto dos inteiros pares sob adição como um subgrupo do conjunto dos inteiros sob adição:

• Fechamento — Somar dois inteiros pares resulta em outro inteiro par
• Associatividade — Esse axioma é herdado dos inteiros. Por exemplo, $2 + (4 + 6) = (2 + 4) + 6$
• Elemento neutro — O número zero é considerado o elemento neutro porque somar zero a qualquer inteiro par não altera seu valor. Zero também pertence ao conjunto dos inteiros
• Elemento inverso — O inverso de qualquer número par também é um número par. Por exemplo, o inverso de 4 é -4, pois $4 + (-4) = 0$, que é o elemento neutro

Podemos aplicar isso a um exemplo mais difícil. Considere o conjunto de todos os números racionais diferentes de zero (ou seja, ℚ*) sob multiplicação. Podemos provar que ℚ* é um subgrupo do conjunto dos números reais diferentes de zero (ou seja, ℝ*) sob multiplicação:

• Fechamento — Se a e b são números racionais diferentes de zero, seu produto ab também é um número diferente de zero. Por exemplo, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$, que é um número racional diferente de zero
• Associatividade — A multiplicação de números racionais é associativa. Por exemplo, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Elemento neutro — O número 1 é considerado o elemento neutro porque multiplicar qualquer número racional diferente de zero por 1 não altera seu valor. Por exemplo, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Elemento inverso — Todo número racional diferente de zero $a = \frac{p}{q}$ tem um inverso multiplicativo $a^{-1} = \frac{q}{p}$, que também é um número racional diferente de zero e resulta no elemento neutro. Por exemplo, considere a = $\frac{2}{3}$. O inverso é $\frac{3}{2}$, pois $\frac{2}{3} \times \frac{3}{2} = 1$

Como ℚ* satisfaz todos os axiomas de grupo, ele forma um grupo. Além disso, como ℚ* é um subconjunto de ℝ* e herda suas propriedades, podemos afirmar que ℚ* é um subgrupo de ℝ*.

Por que isso é importante?

Os grupos são a base de vários conceitos e estruturas matemáticas e criptográficas. Por exemplo, sistemas criptográficos como RSA e criptografia de curvas elípticas dependem fortemente das propriedades dos grupos e de suas operações. Entender subgrupos ajuda a compreender a estrutura de grupos maiores por meio da análise de seus subconjuntos menores e mais gerenciáveis. Os grupos fornecem uma estrutura básica para entender simetria, operações e transformações, algo essencial ao avançarmos para a próxima seção, sobre corpos.

Corpos

Um corpo é um conjunto de elementos que satisfaz os axiomas de corpo para adição e multiplicação e constitui uma álgebra de divisão comutativa (ou seja, a divisão, exceto por zero, é sempre possível). Em geral, os axiomas de corpo são escritos em pares aditivos e multiplicativos:

• Adição
  • Associatividade: $(a + b) + c = a + (b + c)$
  • Comutatividade: $a + b = b + a$
  • Distributividade: $a(b + c) = ab + ac$
  • Elemento neutro: $a + 0 = 0 + a = a$
  • Elemento inverso: $a + (-a) = 0$
• Multiplicação
  • Associatividade: $(ab)c = a(bc)$
  • Comutatividade: $ab = ba$
  • Distributividade: $(a + b)c = ac + bc$
  • Elemento neutro: $(a + b)c = ac + bc$
  • Elemento inverso: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Corpos finitos e geradores

Um corpo finito é um corpo com um conjunto limitado de elementos. Corpos finitos também são chamados de corpos de Galois. O número de elementos é chamado de ordem, ou cardinalidade, do corpo. Esse número será sempre uma potência de um primo. A vantagem dos corpos finitos é que qualquer operação aritmética realizada em seus elementos permanece no corpo. Isso acontece porque todas as operações são realizadas módulo a ordem do corpo, fazendo os valores darem a volta.

Todo corpo finito tem um gerador. Um gerador pode gerar todos os elementos do corpo por exponenciação. Isso significa que podemos pegar o gerador e aumentar seu expoente em um até obter todos os elementos do corpo. Portanto, um gerador é um elemento do corpo que, por meio de suas potências, pode produzir todos os elementos diferentes de zero desse corpo.

Por exemplo, imagine que usamos o conjunto dos inteiros módulo p = 7 e temos o corpo $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Se quisermos encontrar o gerador g de $\mathbb{Z}_7^*$ (ou seja, o grupo multiplicativo dos elementos diferentes de zero de $\mathbb{Z}_7$, precisamos garantir que g1, g2,g3 etc. possam gerar todos os elementos diferentes de zero do corpo.

Vamos verificar se 3 é um gerador:

As potências de 3 geram todos os elementos diferentes de zero de $\mathbb{Z}_7$. Portanto, 3 é um gerador do grupo multiplicativo $\mathbb{Z}_7^*$.

Por que isso é importante?

A criptografia é uma ciência que trabalha com conjuntos finitos. Ela fornece uma compreensão fundamental para abordar temas como o problema do logaritmo discreto, criptografia, troca Diffie-Hellman e curvas elípticas. Os geradores permitem realizar operações aritméticas em polinômios criptografados sem descriptografá-los (ou seja, criptografia homomórfica). Em outras palavras, podemos computar dados criptografados preservando a privacidade dos valores subjacentes. Entender esta seção é essencial para compreender o aspecto de conhecimento zero das provas de conhecimento zero.

Recomendo acessar o Bill’s Security Site, que oferece um exemplo interativo de geração de corpos finitos com parâmetros específicos e explica a teoria subjacente em Python. 

Funções

Uma função é uma expressão, regra ou lei que define uma relação entre duas variáveis: a variável independente e a variável dependente. Essas duas variáveis costumam ser descritas, respectivamente, como causa e efeito. Essa relação costuma ser representada como y = f(x), que é lida como “f de x”. Para cada valor de x, há um único valor de y, o que significa que f(x) não pode ter mais de um valor para o mesmo x.

As funções podem ser de 1 para 1 ou de muitos para 1, algo frequentemente chamado de cardinalidade. Isso significa que um valor de x pode ser mapeado para um valor único de y, ou que vários valores de x podem ser mapeados para o mesmo valor de y

Imagine uma reta definida por $y = 3x + 4$. Essa é uma função linear na qual inserir um valor de x retorna o valor correspondente de y. Juntos, esses dois valores formam um ponto na reta. Por exemplo, podemos reescrever a equação como $f(x) = 3x + 4$ e avaliá-la quando x = 1, resultando em $f(1) = 7$. As funções também podem ter várias variáveis. Por exemplo, considere a fórmula da área de um triângulo: $A = \frac{bh}{2}$. Aqui, A (ou seja, a área) é definida como uma função tanto de b (ou seja, a base) quanto de h (ou seja, a altura).

Domínio e imagem

O domínio de uma função é o conjunto de todos os valores possíveis de entrada (ou seja, variáveis independentes) que a função pode aceitar. A imagem da função é o conjunto de todos os valores possíveis de saída (ou seja, variáveis dependentes) que a função pode produzir.

Para a função $y = 2x + 2$:

• O domínio é formado por todos os números reais, pois qualquer número do infinito negativo ao infinito positivo funcionará. Por exemplo:
  • Se x = 2.5, então $y = 2(2.5) + 2 = 7$ 
  • Se x = -9234525, então $y = 2(-9234525) + 2 = -18469048$
• A imagem também é formada por todos os números reais, pois qualquer número do infinito negativo ao infinito positivo pode ser produzido. Por exemplo:
  • Para encontrar y = -50, resolvemos -50 = 2x + 2, o que resulta em x = -26. 
  • Para encontrar y = 0, resolvemos 0 = 2x + 2, o que resulta em x = 0

Por que isso é importante?

As funções são essenciais para entender polinômios. Eles são funções especiais que envolvem variáveis elevadas a várias potências e seus coeficientes. Polinômios são estruturas algébricas fundamentais que servem de base para a construção de protocolos criptográficos. Na próxima seção, exploraremos os polinômios em detalhes, examinando suas propriedades e sua importância nas provas de conhecimento zero.

Recomendo consultar as notas on-line de Paul e resolver seus exercícios para compreender melhor as funções.

Polinômios

Um polinômio é uma função composta por várias variáveis e coeficientes que envolve apenas operações de adição, subtração, multiplicação e exponenciação de variáveis por inteiros não negativos. Em geral, os polinômios são escritos na forma:‍

Em que $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ são coeficientes, e x é a variável. A maior potência da variável x com um coeficiente diferente de zero é chamada de grau do polinômio.

Os polinômios podem ser classificados como univariados, envolvendo uma única variável (como na forma escrita acima), ou multivariados, envolvendo várias variáveis (por exemplo, $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check é um exemplo de protocolo que usa polinômios multivariados. No entanto, na maioria das vezes, as provas de conhecimento zero exigem apenas uma variável.

Os nomes comuns atribuídos aos polinômios de acordo com seu grau são:

• Grau 0 — Constante diferente de zero (por exemplo, $P(x) = 6$)
• Grau 1 — Linear (por exemplo, $P(x) = 2x - 7$)
• Grau 2 — Quadrático (por exemplo, $P(x) = 8x^2 - 3x + 1$)
• Grau 3 — Cúbico (por exemplo, $P(x) = 3x^3 - 4x$)

Se tivermos dois polinômios diferentes de grau no máximo $d$, eles poderão se cruzar em, no máximo, $d$ pontos (por exemplo, se igualarmos uma função linear a uma função cúbica, elas poderão se cruzar até três vezes). Essa propriedade decorre da forma como encontramos pontos em comum. Para descobrir onde dois polinômios se cruzam, nós os igualamos. Na subseção a seguir, praticaremos como encontrar as raízes de um polinômio, ou seja, onde um determinado polinômio cruza o eixo x. O Teorema Fundamental da Álgebra afirma que um polinômio de grau $d$ pode ter, no máximo, $d$ soluções e, portanto, no máximo $d$ pontos em comum.

Raízes de polinômios 

As raízes, ou zeros, de um polinômio são os valores de x para os quais o polinômio é igual a zero. Em outras palavras, se $P(x)$ for um polinômio, uma raiz $r$ será uma solução da equação $P(r) = 0$. Para encontrar as raízes, precisamos saber fatorar polinômios. Fatorar significa descobrir o que devemos multiplicar para obter uma determinada quantidade. Por exemplo, há várias maneiras de fatorar 12:

Um método comum de fatoração consiste em decompor completamente o número em fatores primos positivos. Ao fatorar, é sempre melhor começar pelo máximo divisor comum (MDC) de todos os termos. Por exemplo:

No exemplo acima, ambos os termos (ou seja, 6x e 3) são divisíveis por 3, portanto, têm um MDC de 3. Assim, os fatores são 3 e $2x + 1$. Invertemos a propriedade distributiva: $3 \times 2x$ e $3 \times 1$. Encontrar as raízes significa resolver x quando $P(x) = 0$.

A fatoração é simples para polinômios com dois termos. E fica ainda mais simples quando temos um gráfico, pois as raízes são os pontos onde o polinômio cruza o eixo x. No entanto, adicionar três ou mais graus pode tornar o processo mais complexo. Recomendo a leitura do artigo Como fatorar polinômios para uma explicação mais aprofundada. 

Conhecer todas as nuances da fatoração de diferentes polinômios não é essencial para ler o restante deste artigo. Para os nossos objetivos, interessa-nos saber quando um polinômio é igualado a outro valor. Neste caso, queremos saber quando um polinômio é igual a zero. Mais adiante, veremos quando um polinômio é igual a outro ou quando a diferença entre dois polinômios é identicamente zero (ou seja, todos os coeficientes são zero), o que envolve verificar se um determinado polinômio tem certas raízes.

O lema de Schwartz-Zippel 

O lema de Schwartz-Zippel é uma ferramenta probabilística para verificar se uma equação polinomial é sempre verdadeira. Ele avalia o polinômio em pontos aleatórios e verifica se o resultado é zero.

Imagine uma equação complexa que envolva as variáveis $x_1, x_2, \ldots, x_n$. Se essa equação for um polinômio, e não apenas uma coleção aleatória de termos, o lema de Schwartz_Zippel nos ajudará a verificar se ela é válida para todos os valores possíveis dessas variáveis.

Veja como funciona:

• Considere $P(x_1, x_2, \ldots, x_n)$ um polinômio de grau total d (ou seja, a maior soma dos expoentes em qualquer termo)
• Escolha um conjunto finito S do corpo (como selecionar um conjunto de números)
• Selecione aleatoriamente valores para cada variável $x_1, x_2, \ldots, x_n$ no conjunto S

O lema afirma que a probabilidade de P ser zero nesses pontos escolhidos aleatoriamente é, no máximo, $\frac{d}{S}$. Isso significa que, se o polinômio não for zero, é muito improvável que ele pareça ser zero por mero acaso. Isso é particularmente útil em provas de conhecimento zero, nas quais precisamos verificar identidades polinomiais com eficiência.

Interpolação de Lagrange

A interpolação de Lagrange é um método para construir um polinômio que passa por um determinado conjunto de pontos. O polinômio de Lagrange é o polinômio de menor grau que passa por cada ponto fornecido. Para n pontos, é possível criar um polinômio de grau n-1 que passe por todos eles. Por exemplo, se você tiver dois pontos em um plano, poderá definir uma linha reta que passe por ambos. Se tivermos três pontos em um plano, poderemos definir um polinômio quadrático (ou seja, $y = ax^2 + bx + c$) que passe por todos eles. E assim por diante.

Por que isso é importante?

Os polinômios são um único objeto matemático capaz de conter uma quantidade ilimitada de informações — pense em um polinômio como uma lista de números inteiros, e isso ficará evidente. Assim, uma única equação entre polinômios pode representar um número ilimitado de equações entre números. Se alguém puder verificar uma determinada equação entre polinômios, estará verificando implicitamente todas as equações possíveis ao mesmo tempo. É assim que protegemos provas não interativas contra os riscos de um provador mal-intencionado e evitamos depender de verificações pontuais aleatórias de um determinado cálculo. 

Os polinômios também têm várias propriedades que os tornam úteis para a criação de provas:

• Com pontos suficientes de um determinado polinômio, é possível reconstruir o polinômio inteiro
• Uma pequena alteração na entrada de um polinômio pode causar uma mudança significativa em sua saída, facilitando a detecção de erros
• Os polinômios podem detectar e corrigir erros em cálculos, de forma semelhante a como os códigos de apagamento tornam os dados tolerantes a falhas (o que é essencial para o funcionamento do Turbine)

As provas de conhecimento zero servem para comprovar determinados cálculos. Os polinômios são inestimáveis para essa tarefa, pois podemos criá-los com características específicas em mente. Digamos que você tenha um cálculo ou um conjunto de pontos de dados que deseja comprovar. A maneira mais fácil de fazer isso é codificá-lo em um polinômio e usar suas propriedades para criar uma prova:

• Codifique os dados em um polinômio $P(x)$ de modo que avaliar $P(x)$ em determinados pontos produza os dados originais ou o resultado de um determinado cálculo
• Para garantir que o polinômio atenda aos critérios definidos (por exemplo, que todos os valores estejam dentro de um intervalo), crie um polinômio de restrição $C(x)$. Por exemplo, $C(x) = (P(x) - 0)(P(x) - 1)$ garante que $P(x)$ seja 0 ou 1
• Transforme o problema em provar que $P(x)$ atende a determinadas condições para o seu conjunto de dados ou cálculo
• Crie um polinômio conhecido $H(x)$ que seja múltiplo de $P(x)$ e codifique essas condições
• O provador compromete os valores de $P(x)$ e de quaisquer polinômios relacionados criando uma árvore de Merkle com as avaliações e envia o hash raiz ao verificador
• O verificador seleciona aleatoriamente alguns pontos e pede ao provador que forneça os valores de $P(x)$ e $C(x)$ nesses pontos
• O verificador compara os valores fornecidos com o hash raiz comprometido e com as relações polinomiais esperadas

Não importa o tamanho do polinômio: como usamos o compromisso polinomial, podemos verificar equações entre polinômios em pouco tempo. Essa é uma forma extremamente sucinta e eficiente de criar provas. Todos os erros são amplificados e, com técnicas como a heurística de Fiat-Shamir, essas provas podem se tornar não interativas, permitindo que qualquer pessoa as verifique sem interação adicional. 

Para aprofundar seu conhecimento, recomendo conferir os seguintes exercícios:

• Exercícios sobre polinômios
• Exercícios para encontrar zeros de polinômios
• Fatoração de polinômios: problemas muito difíceis com soluções

A Khan Academy também tem uma unidade completa sobre expressões, equações e funções polinomiais.

Agora, para entender melhor os compromissos polinomiais, precisamos explorar a criptografia por trás das provas de conhecimento zero.

A criptografia por trás das provas de conhecimento zero

Vamos explorar a criptografia simétrica e assimétrica.

Criptografia simétrica

A criptografia simétrica é uma técnica de criptografia na qual a mesma chave é usada para criptografar um texto simples e descriptografar um texto cifrado. Essa chave costuma ser chamada de chave secreta ou chave privada, pois o uso de uma única chave exige que ela permaneça em segredo. No entanto, isso também significa que a chave secreta precisa ser compartilhada entre as duas partes antes que elas possam se comunicar com segurança. Portanto, gerenciar e distribuir a chave secreta de forma segura pode ser desafiador e suscetível a vazamentos quando não é feito corretamente. Apesar dessa desvantagem, a criptografia simétrica é rápida, eficiente e exige menos capacidade computacional e memória do que outros esquemas de criptografia.

Algoritmos comuns de criptografia simétrica incluem:

Advanced Encryption Standard (AES)

O Advanced Encryption Standard (AES) é uma variante da cifra de bloco Rijndael amplamente usada em todo o mundo para proteger dados. Ele aceita chaves de 128, 192 e 256 bits.

ChaCha20

O ChaCha20 é uma cifra de fluxo moderna e eficiente desenvolvida por Daniel J. Bernstein. É uma variante da cifra de fluxo Salsa20 que aproveita as operações de adição-rotação-XOR (ARX). Ela mapeia uma chave de 256 bits, um nonce de 64 bits e um contador de 64 bits para um bloco de 512 bits do fluxo de chaves, o que permite ao usuário acessar com eficiência qualquer posição do fluxo de chaves em tempo constante.

Embora a criptografia simétrica seja robusta e eficiente, ela exige um método seguro para a troca de chaves. Um desses métodos é a troca de chaves Diffie-Hellman, que permite que duas partes compartilhem com segurança uma chave secreta por um canal inseguro. No entanto, esse método se baseia nos princípios da criptografia assimétrica, que abordaremos na próxima seção.

Criptografia assimétrica

A criptografia assimétrica, também conhecida como criptografia de chave pública, é um método que usa um par de chaves relacionadas (ou seja, uma chave pública e uma chave privada) para criptografar e descriptografar informações. A chave pública é compartilhada abertamente, enquanto a chave privada é mantida em segredo. Quando um remetente deseja criptografar uma mensagem, ele usa a chave pública do destinatário. Ao recebê-la, o destinatário descriptografa a mensagem usando sua chave privada correspondente. Os dados criptografados com a chave pública só podem ser descriptografados com a chave privada. Assim, a criptografia assimétrica permite uma comunicação segura por canais inseguros, já que a chave de descriptografia nunca é compartilhada.

A criptografia assimétrica é vantajosa porque oferece um alto nível de segurança, já que a chave privada nunca é compartilhada. Ela também simplifica a distribuição de chaves, pois a chave pública pode ser compartilhada abertamente, além de viabilizar assinaturas digitais. No entanto, a criptografia assimétrica exige mais recursos computacionais e é mais lenta do que a simétrica. Gerenciar pares de chaves também pode se tornar complexo, especialmente em sistemas com muitos usuários e nos quais os pares de chaves não são intuitivos. 

Algoritmos comuns de criptografia assimétrica incluem:

• Rivest-Shamir-Adleman (RSA) — um dos sistemas criptográficos de chave pública mais antigos e utilizados para a transmissão segura de dados. Foi desenvolvido na década de 1970 e se baseia na dificuldade prática de fatorar o produto de dois números primos grandes
• Criptografia de Curva Elíptica (ECC) — uma abordagem de criptografia de chave pública baseada na estrutura algébrica de curvas elípticas sobre corpos finitos. Ela oferece segurança semelhante à do RSA, mas usa chaves menores, resultando em cálculos mais rápidos e menor necessidade de armazenamento. A Solana usa a curva elíptica Ed25519 para gerar seus pares de chaves

Assinaturas digitais

As assinaturas digitais são um aspecto essencial da criptografia de chave pública e fornecem uma forma de verificar a autenticidade e a integridade de uma mensagem, um software ou um documento digital. Uma assinatura digital é criada usando a chave privada do remetente e pode ser verificada por qualquer pessoa com acesso à chave pública correspondente. Isso garante que a mensagem tenha sido enviada por um remetente legítimo e não tenha sido alterada.

Algoritmos comuns usados em assinaturas digitais incluem:

• Digital Signature Algorithm (DSA) — uma abordagem baseada em exponenciação modular (ou seja, exponenciação realizada sobre um módulo) e no problema do logaritmo discreto
• Elliptic Curve Digital Signature Algorithm (ECDSA) — uma variante do DSA que usa criptografia de curva elíptica para oferecer um nível mais alto de segurança com chaves menores

Problema do logaritmo discreto

O problema do logaritmo discreto consiste em encontrar o expoente k na equação $g^k \equiv h \pmod{p}$, em que:

• g é uma base conhecida (ou seja, um gerador)
• h é um resultado conhecido (ou seja, um elemento do grupo)
• p é um número primo (ou seja, a ordem do grupo)
• k é o expoente desconhecido (ou seja, o logaritmo discreto de h na base g)

Em outras palavras, se você conhece os valores de g, h e p, o problema do logaritmo discreto consiste em encontrar k. Por exemplo, dada a equação $2^k \equiv 9 \pmod{23}$, o objetivo é encontrar k.

O problema do logaritmo discreto é considerado difícil de resolver com eficiência, especialmente para números grandes. Devido a essa dificuldade, ele é a base da segurança de vários sistemas criptográficos, incluindo a Solana, a criptografia ElGamal, os algoritmos de assinatura digital (ou seja, DSA e ECDSA) e a troca de chaves Diffie-Hellman

Troca de chaves Diffie-Hellman

A troca de chaves Diffie-Hellman é um método para trocar chaves criptográficas com segurança por um canal público.  A implementação original e mais simples (ou seja, Diffie-Hellman sobre corpo finito) funciona da seguinte forma:

• Alice e Bob concordam publicamente com dois números: um número primo grande p (ou seja, o módulo) e uma base g (ou seja, o gerador), que é uma raiz primitiva módulo p 
• Alice seleciona um número inteiro secreto a e envia a Bob $A \equiv g^a \pmod{p}$
• Bob seleciona um número inteiro secreto b e envia a Alice $B \equiv g^b \pmod{p}$
• Alice calcula $s \equiv B^a \pmod{p}$ 
• Bob calcula $s = A^b \pmod{p}$ 

Alice e Bob agora têm o mesmo valor secreto. Isso acontece porque ambos os cálculos resultam no mesmo segredo s, pois:

Esse segredo compartilhado s pode então ser usado como uma chave de criptografia simétrica, permitindo que Alice e Bob se comuniquem com segurança. A segurança da troca de chaves Diffie-Hellman depende da dificuldade do problema do logaritmo discreto. Sem conhecer os valores secretos a e b, é computacionalmente inviável para alguém que esteja interceptando a comunicação derivar o segredo compartilhado. Isso é conhecido como função unidirecional: é relativamente fácil de calcular, mas extremamente difícil de inverter.

Embora a troca de chaves Diffie-Helman sobre corpo finito seja segura e amplamente usada, ela exige chaves grandes para garantir a segurança. Por exemplo, se Alice e Bob escolhessem publicamente um módulo de 23, seria muito mais fácil quebrá-lo, pois existem apenas 23 resultados possíveis para n mod 23. Assim, esse método pode exigir muitos recursos computacionais e ser menos eficiente. Para solucionar esses desafios, a criptografia de curva elíptica (ECC) oferece uma alternativa mais eficiente, pois proporciona o mesmo nível de segurança com chaves significativamente menores e cálculos mais rápidos.

Curvas elípticas

Uma curva elíptica é definida pela equação $y^2 = x^3 + ax + b$, em que a e b são constantes. A criptografia de curva elíptica consiste simplesmente em trabalhar com pontos de uma determinada curva elíptica. Essas curvas têm várias propriedades únicas que as tornam úteis para a criptografia. Por exemplo:

• Adição de pontos — Dados dois pontos, P e Q, em uma determinada curva elíptica, sua soma R = P + Q também será um ponto da curva. O artigo de Preethi Kasireddy, Um guia descomplicado de criptografia para provas de conhecimento zero, apresenta uma boa explicação de como somar pontos em uma curva elíptica
• Multiplicação escalar — Dado um ponto P em uma determinada curva elíptica e um número inteiro k, a multiplicação escalar é o processo de somar o ponto P a ele mesmo k vezes. Isso produzirá outro ponto (ou seja, kP) na curva. Esse processo é usado para gerar chaves públicas a partir de chaves privadas
• Problema do logaritmo discreto — O problema do logaritmo discreto em curvas elípticas é muito mais difícil de resolver do que seu equivalente com números inteiros. Dados os pontos P e q = kP, é computacionalmente inviável determinar k se os parâmetros da curva forem escolhidos corretamente. Isso significa que as curvas elípticas oferecem a mesma segurança dos sistemas tradicionais com chaves muito menores, tornando-as mais eficientes

Com nosso conhecimento recém-adquirido sobre teoria dos grupos, podemos afirmar que certas equações de curvas elípticas satisfazem o conjunto de axiomas:

• Quaisquer dois pontos podem ser somados para gerar um terceiro ponto
• A ordem em que os dois pontos são somados não importa
• Se houver mais de dois pontos para somar, a ordem em que são somados não importa
• Existe um elemento identidade (ou seja, somar zero a qualquer ponto da curva resulta no mesmo ponto)

Recomendo muito a leitura de Criptografia de curva elíptica, de Georgie Bumpus para explorar essa estrutura de grupo com mais profundidade. 

As curvas elípticas oferecem o mesmo nível de segurança de outros sistemas criptográficos tradicionais, como o RSA, mas com chaves muito menores. Por exemplo, uma chave de 256 bits em ECC oferece segurança comparável à de uma chave de 3.072 bits em RSA. Isso é vantajoso porque:

• Chaves menores permitem criptografia e descriptografia mais rápidas
• Chaves e certificados exigem menos espaço
• Chaves menores reduzem a quantidade de dados transmitidos, o que é vantajoso em ambientes com largura de banda limitada, como uma blockchain

Curvas de Montgomery

As curvas de Montgomery são curvas elípticas definidas pela equação $By^2 = x^3 + Ax^2 + x$ sobre um corpo finito, em que A e B são constantes, B é diferente de zero e A não é -2 nem 2. Essas curvas são especiais porque a multiplicação em curvas elípticas pode ser implementada com mais eficiência usando uma escada de Montgomery. 

Uma escada de Montgomery basicamente recebe um ponto P em uma curva de Montgomery e um escalar k, inicializa dois pontos do infinito até P e atualiza cada bit do escalar k, do bit mais significativo ao menos significativo. A ideia principal é manter dois pontos e atualizá-los com uma sequência constante de operações, independentemente dos bits do escalar k.

Isso é importante por alguns motivos:

• É resistente a ataques de canal lateral, que são ataques baseados nas informações adicionais que podem ser coletadas devido à implementação ou ao projeto de um determinado protocolo ou algoritmo. Esse é um assunto muito, muito técnico que recomendo explorar. Esses tipos de ataque vão desde variações no consumo de energia do hardware durante o cálculo até vazamentos de radiação eletromagnética
• Não é necessário usar a coordenada y, pois a multiplicação escalar pode ser realizada usando apenas as coordenadas x
• Opera em tempo constante, o que significa que o tempo necessário para um determinado cálculo não depende do valor de entrada

As curvas de Montgomery são amplamente usadas em protocolos criptográficos, como o algoritmo X25519 para troca de chaves, que usa a forma de Montgomery da curva Curve25519. Esse algoritmo é a base das comunicações seguras modernas, incluindo implementações em protocolos populares como o TLS. 

Curvas de Edwards

As curvas de Edwards são um tipo de curva elíptica definida pela equação $x^2 + y^2 = 1 + d x^2 y^2$, em que d é uma constante diferente de zero e de 1.  

Essas curvas são importantes porque:

• Eficiência nas operações com pontos — A adição de dois pontos em uma curva de Edwards é mais eficiente do que em outras formas de curvas elípticas. As fórmulas de adição e duplicação de pontos são mais simples e envolvem menos operações no corpo, o que acelera os cálculos
• Fórmula de adição unificada — As curvas de Edwards usam uma fórmula de adição unificada, o que significa que a mesma fórmula pode ser usada para adicionar e duplicar pontos. Isso reduz a possibilidade de erros de implementação e aumenta a segurança
• Completude — Para determinados valores de d, as curvas de Edwards são completas. Isso significa que a lei de adição abrange todas as entradas possíveis, sem exceções.
• Resistência a ataques de canal lateral — Assim como as curvas de Montgomery, as curvas de Edwards são resistentes a ataques de canal lateral devido aos seus padrões de operação uniformes e previsíveis.

Uma curva de Edwards amplamente usada é a Edwards25519, definida pela equação $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Essa curva é conhecida por sua aritmética eficiente e por usar chaves de 256 bits. Seu esquema de assinatura é implementado em vários protocolos e sistemas de segurança, incluindo a Solana, o OpenSSH e o Tor. A Monero usa a Edwards25519 como base para gerar seus pares de chaves.

Por que isso é importante?

As curvas elípticas são essenciais para provas de conhecimento zero devido à sua eficiência e às propriedades que reforçam a segurança. Observação: o uso de curvas elípticas permite criar provas menores e mais rápidas, algo essencial para qualquer tipo de implementação prática. Analisaremos isso melhor ao abordar os avanços relacionados ao conhecimento zero, mas a necessidade de provas pequenas e rápidas é essencial em um ambiente de alta demanda computacional com várias restrições de contas e transações. É isso que torna as provas de conhecimento zero atraentes para a criação de rollups, pois seria possível gerar uma prova sucinta de que todas as operações em uma L2 são válidas e validá-la na L1.

Em resumo, pense nas curvas elípticas como substitutas da aritmética modular. Com curvas elípticas, é muito mais difícil obter um ponto específico. Se usássemos a aritmética modular tradicional com $g^a \bmod n$, em que g é um gerador, n é um número primo grande e a é a chave secreta. Como vimos anteriormente com o problema do logaritmo discreto, seria necessário usar um número primo muito grande para proteger a chave secreta. As curvas elípticas oferecem uma alternativa mais eficiente, com chaves menores e o mesmo nível de segurança, mas com desempenho significativamente melhor.

Aleatoriedade

Nada mais neste artigo teria importância sem a aleatoriedade, um aspecto fundamental da criptografia. Como esperar que um sistema seja seguro se seus valores forem previsíveis e tendenciosos? Alcançar uma aleatoriedade verdadeira pode ser difícil, mas ela é essencial por vários motivos:

• Geração de chaves — As chaves criptográficas devem ser geradas aleatoriamente para garantir que sejam imprevisíveis e seguras
• Nonces e sais — Os nonces (ou seja, números usados uma única vez) e os sais (ou seja, valores aleatórios adicionados aos dados antes da aplicação de hash) impedem, respectivamente, ataques de repetição e protegem contra ataques pré-computados
• Protocolos seguros — A aleatoriedade é usada para garantir imparcialidade e segurança, evitando previsibilidade e padrões que invasores poderiam explorar

A maioria dos geradores de números aleatórios não consegue produzir um número aleatório que possa ser verificado criptograficamente. Isso os deixa vulneráveis à manipulação e limita seus casos de uso. No entanto, as funções aleatórias verificáveis resolvem esse problema.

Funções aleatórias verificáveis

Uma função aleatória verificável (VRF) é uma primitiva criptográfica que produz uma saída aleatória e uma prova de que essa saída foi gerada corretamente a partir de uma determinada entrada. Uma VRF deve ser imprevisível, ou seja, sua saída deve ser indistinguível de um valor aleatório para qualquer pessoa que não conheça a entrada secreta. Sua segurança depende da suposição do RSA de que é difícil calcular $y = h^d \bmod n$ sem conhecer o expoente secreto d e da segurança da função hash H. 

As principais etapas de uma determinada VRF são:

• Geração de chaves — O usuário gera um par de chaves RSA: (e, n) como chave pública e (d, n) como chave privada. A chave pública e é o expoente, e n é o módulo. A chave privada d é o expoente secreto
• Cálculo — Dada uma entrada x, o usuário calcula a saída y da VRF e a prova π. Primeiro, calcula-se o hash h = H(x), em que H é uma função hash criptográfica. Em seguida, calcula-se $y = h^d \bmod n$, que é a assinatura RSA do hash. Por fim, calcula-se a prova π = (h, y)
• Verificação — Com a chave pública (e, n), a entrada x, a saída y e a prova π = (h, y), qualquer pessoa pode verificar se a saída da VRF está correta conferindo se o hash h é igual a $H(x)$ e se $y^e \equiv h \pmod{n}$ é válido para verificar a equação RSA‍

As VRFs são frequentemente usadas em protocolos de consenso nos quais a aleatoriedade precisa ser imprevisível, mas verificável. L1s como Algorand, Cardano, Internet Computer e Polkadot usam VRFs em seus mecanismos de consenso para selecionar produtores de blocos aleatoriamente. A Chainlink oferece o Chainlink VRF como uma camada de abstração entre o usuário e a blockchain para gerar valores comprovadamente justos e verificáveis. A Pyth Entropy também oferece uma fonte de aleatoriedade confiável e segura.

Cerimônias e configurações confiáveis

Cerimônias criptográficas são protocolos ou eventos nos quais cálculos criptográficos essenciais são realizados em um ambiente seguro e controlado. Há vários tipos de cerimônias criptográficas, como:

• Cerimônias de geração de chaves — Envolvem a geração de chaves criptográficas para garantir que nenhuma entidade tenha controle sobre o processo de geração
• Cerimônias de geração de parâmetros — Envolvem a criação de parâmetros criptográficos que serão usados por várias partes
• Cerimônias de computação multipartidária (MPC) — Envolvem várias partes realizando conjuntamente um cálculo criptográfico para garantir que nenhuma parte possa comprometer o processo

Uma cerimônia de configuração confiável é um evento ou processo especial criado para gerar um conjunto de parâmetros criptográficos necessários para executar um protocolo criptográfico. Em nossa seção sobre provas de conhecimento zero interativas e não interativas, vimos que a primeira etapa de uma prova consiste em fazer com que o provador e o verificador concordem sobre algum valor a ser usado. Em uma cerimônia de configuração confiável, vários participantes contribuem com aleatoriedade para a configuração, garantindo que nenhum participante controle o processo. Cada participante gera um valor aleatório que é combinado aos valores fornecidos pelos demais participantes. A saída combinada se torna um conjunto de parâmetros no qual todos podem confiar. 

Esse processo é essencial porque, se todos os participantes entrarem em conluio, eles poderão comprometer o sistema gerando uma prova para uma afirmação inválida. No entanto, basta um único participante honesto para garantir a segurança dos parâmetros. 

A Zcash ficou conhecida por usar uma cerimônia confiável para inicializar os recursos de privacidade da rede. A Ethereum também realizou a Cerimônia KZG, um ritual público coordenado para fornecer uma base criptográfica aos seus esforços de escalabilidade (por exemplo, EIP-4844 / proto-danksharding). 

Vale observar que alguns sistemas de provas de conhecimento zero, como zk-STARKs, não exigem uma configuração confiável. Exploraremos isso melhor no segundo artigo.

Conclusão

Neste artigo, exploramos a teoria, a matemática e a criptografia por trás das provas de conhecimento zero. Isso é tudo o que você precisa saber para começar a entender o que são provas de conhecimento zero. Agora, podemos começar a aplicar esse conhecimento a redes como a Solana para contribuir com a discussão e o desenvolvimento geral das provas de conhecimento zero.

Continuamos esta análise no segundo e último artigo da nossa série de duas partes sobre provas de conhecimento zero, apropriadamente intitulado Provas de conhecimento zero: suas aplicações na Solana. 

Se você leu até aqui, valeu, anon! Insira seu endereço de e-mail abaixo para nunca perder uma atualização sobre as novidades da Solana. Quer se aprofundar? Explore os artigos mais recentes no blog da Helius e continue hoje mesmo sua jornada na Solana.

Recursos adicionais

• A verdadeira aleatoriedade existe?
• Curvas elípticas — Computerphile
• Introdução à classe de complexidade NP-completo
• Problemas de troca de chaves — Computerphile
• Unidade da Khan Academy sobre criptografia
• Criptografia de chave pública — Computerphile
• A complexidade de conhecimento dos sistemas de prova interativos