Provas de Conhecimento Zero: o que são zk-STARKs e como funcionam? (zk-Stark V2)

O que é a Prova de Reserva e a Prova de Conhecimento Zero?

Prova de Reserva (PoR)

Este é um processo para as trocas de criptomoedas mostrarem que têm ativos suficientes para cobrir todos os saldos dos clientes. Isto constrói confiança ao provar que a troca não está a esconder quaisquer responsabilidades. A forma mais simples de mostrar isso é publicando tanto os montantes de ativos da troca quanto uma lista de saldos de utilizadores para que todos possam confirmar:

• O total de ativos que a OKX afirma possuir é a soma do saldo total de ativos de cada utilizador.

• O saldo total de cada utilizador é superior a zero, e os seus ativos estão contabilizados, cobrindo as suas responsabilidades e garantindo que cada utilizador tem um património líquido positivo.

• O valor total que a troca reivindica representa cada um dos utilizadores, pelo que cada utilizador deve poder verificar a inclusão do seu valor líquido no valor total

No entanto, revelar esses saldos pode comprometer a privacidade do utilizador. Para resolver esta questão, usamos um método chamado Prova de Conhecimento Zero (ZKP) para proteger a privacidade do utilizador.

Prova de Conhecimento Zero (ZKP)

É uma técnica de segurança que permite que a troca de criptomoedas prove que uma afirmação é verdadeira sem revelar qualquer informação adicional.

No nosso caso, queremos provar que temos fundos suficientes sem partilhar detalhes específicos do utilizador. A maior parte das ZKP enquadra-se em duas categorias:

• zk-SNARK

• zk-STARK

Usamos zk-STARK porque é mais seguro e tem uma suposição mínima de segurança. Neste artigo, vamos explicar como usamos zk-STARK para proteger a privacidade do utilizador enquanto provamos a nossa solvência.Antes de continuarmos, é útil entender alguns termos básicos de ZKP, como Circuito, Árvore de Merkle e Compromissos.

Para os principiantes, existem muitos recursos disponíveis para o ajudar a começar. Para utilizadores avançados, podem consultar o Curso MOOC e a monografia académica.

Como funciona o zk-STARK?

Criamos uma Árvore de Merkle usando o hash da conta de cada utilizador como as folhas. Cada conta mostra saldos em USD para vários tokens (porexemplo, BTC, ETH). Para lidar com esses saldos, separamos os seus saldos em capitais não negativos e dívidas para cada token. Desta forma, só trabalhamos com números positivos, o que facilita a realização de cálculos e evita erros.

Por exemplo:

• Se o saldo de tokens BTC de um utilizador for A, o seu capital BTC é A e a dívida BTC é 0.

• Se o saldo do token ETH de um utilizador for -B, o seu capital correspondente é 0 e a dívida é B

Em seguida, construímos uma Árvore de Merkle com estes valores de conta como folhas. A raiz da árvore atua como um único valor representando todos os saldos dos utilizadores. Cada utilizador pode provar que a sua conta faz parte desta árvore utilizando um Caminho de Merkle que mostra como a sua conta se conecta à raiz.

Também publicamos o total de capital próprio e dívida somados em todos os tokens e utilizadores. Em seguida, criamos uma Prova de Conhecimento Zero (ZKP) para mostrar duas coisas:

• Prova de Soma: os valores de capital próprio e dívida na Árvore de Merkle somam corretamente

• Prova Não Negativa: o capital total de cada utilizador é superior à sua dívida total

Quando tentamos verificar a Árvore de Merkle para um grande número de contas, torna-se demasiado para lidar de uma só vez. Para superar este desafio, dividimos as contas em grupos menores chamados lotes. Cada lote é processado separadamente usando circuitos de lote, que verificam a parte inferior da Árvore de Merkle.

O loteamento não só torna possível a sua gestão, como também nos permite executar estas verificações ao mesmo tempo (processamento paralelo). Assim que tivermos os resultados de cada lote, utilizamos outra camada de circuitos, chamados circuitos recursivos, para combinar e verificar todos os lotes em conjunto, até termos provado toda a Árvore de Merkle.

O que é Circuito de Lote?

O circuito de lote aceita 1024 contas (acc₀, acc₁,..., acc₁₀₂₃) como entradas e gera 3 saídas principais: um hash (h_lote), um valor total de capital próprio (e_lote), e um valor total da dívida (d_lote). Verifica que:

• O total dos fundos próprios denominados em USD de cada conta é superior ao total da sua dívida

• e_lote é a soma de todos os valores de capital denominados em USD nestas contas

• d_lote é a soma de todos os valores da dívida denominados em USD nestas contas

• h_lote é a raiz da Árvore de Merkle criada usando os hashes das contas

• Não há transbordo durante a soma para e_lote e d_lote

O que é o Circuito Recursivo?

O circuito recursivo leva 64 provas diferentes (π₀, ..., π₆₃), hashes (h₀, ..., h₆₃), ações (e₀, ..., e₆₃₎, e dívidas (d₀, ..., d₆₃) dos circuitos de camada inferior como entradas. Combina estas entradas e produz 3 saídas: um novo hash (h_recursivo), capital total (e_recursivo), e dívida total (d_recursivo). Verifica que:

• Cada uma das 64 provas é válida

• Cada prova π₀, ..., π₆₃ do circuito de camada inferior é válida

• e_recursivo é a soma de e₀, ..., e₆₃

• d_recursivo é a soma de d₀, ..., d₆₃

• h_recursivo é o hash da concatenação de h₀, ..., h₆₃, i.e.

  • h_recursivo = Hash (h₀ || h₁ || ... || h₆₃₎

• Não há transbordo durante a soma para e_recursivo e d_recursivo

Qual é a relação entre circuitos de lote e circuitos recursivos?

O diagrama abaixo ilustra como o circuito de lote e os circuitos recursivos se conectam e trocam dados entre si. Tenha em atenção que, no diagrama, duplicámos os circuitos para fins ilustrativos, mas na nossa implementação, utilizamos apenas um circuito para cada camada.

A nossa Árvore de Merkle está estruturada de forma um pouco diferente. Nos 10 níveis inferiores, cada nó pai tem 2 filhos, enquanto nos níveis superiores, cada pai tem 64 filhos. Isto é porque os circuitos de lote tratam a parte inferior, e os circuitos recursivos gerem a parte superior. O diagrama abaixo usa um exemplo com "Alice" para mostrar a Árvore de Merkle e a sua Prova de Merkle (colorida a verde).

Para mais pormenores técnicos, como a forma como ajustamos os números de conta para se adequarem ao tamanho do lote ou como escolhemos o algoritmo de hash correto, consulte esta página.

Avanços na Versão 2 do zk-PoR

A nossa Versão 2 do zk-PoR fez vários avanços em relação à versão anterior:

• Maior eficiência: Atualmente, é 50 vezes mais rápido do que a versão anterior. Leva 3 horas numa única máquina de 10 núcleos, em comparação com as 36 horas da versão anterior usando nove máquinas de 64 núcleos. Este aumento de velocidade deve-se à utilização do framework Plonky2, que compila circuitos codificados em Rust em linguagem de máquina eficiente, em vez de usar scripts Python mais lentos. Também melhorámos o Plonky2 para realizar alguns cálculos em GPUs, reduzindo o tempo em mais 30%.

• Melhor auditabilidade: Com a Versão 2, utilizamos uma estrutura de alto nível que lida com detalhes criptográficos complexos para nós. Isto torna o nosso código mais claro, mais legível e menos propenso a erros.

• Prova concisa: O tamanho da prova V2 (~500KB) é apenas 0.05% de V1 (~1.2GB). Graças ao método recursivo, as provas podem ser repetidamente agregadas e condensadas numa única prova.

Como faço a autoverificação da Prova de Reservas (PoR)?

Eis como pode verificar se o saldo do seu ativo está incluído como uma Folha de Merkle zk-STARK:

1. Inicie sessão na sua conta OKX, vá a Ativos e selecione relatórios PoR

2. Selecione Detalhes para ver os seus dados de auditoria

   

3. Obtenha os dados necessários para a verificação manual selecionando Copiar dados

   

4. Após selecionar Copiar dados, abra o editor de texto (porexemplo usando o caderno) e, em seguida, cole e guarde a string JSON como um ficheiro. O ficheiro deve terminar com o nome "_inclusion_proof."json." A string JSON contém o saldo da sua conta e uma imagem do Caminho de Merkle e, em seguida, guarda o ficheiro numa nova pasta

5. Abra um editor de texto (porexemplo, Caderno) e, em seguida, cole e guarde a string JSON como um ficheiro. O nome do ficheiro deve terminar com "_inclusion_proof.json." Guarde o ficheiro numa nova pasta

   • A string JSON contém o saldo da sua conta e uma imagem do Caminho de Merkle.

   • O texto JSON é mostrado abaixo:

     {"sum_tree_siblings":["9ffb169fecf075e203edca2af65e4c69fa4331d13ac75ccae4cd5b990c91b675","7149661a789763cb61293ebf5d8bdd5570e79ee203738f87a444c79642b89a79","788aac9e392fa62bc3f79c98c7afd7bb41ee7d5bd496876cd0580080f19e002f","e828a44d345e6799e232aabc57cb2b92986ee1c52b65344d83e79d84b4b571b7","6c0675de9cd6b2be1abd6a98260e7ea776492c4aa9aadf31086f23452cb7c48d","2dfe3aadb5ac00ee0b1110ee8c313afdee85d9f9c62904d6ee79c8f02354d80a","5068ae26192587432892a6de8b54ea25a8aafd1c010ab5e67b55b2c30c6257fa","a1bb026ec9f3d8a1fa1b6f498c40ed8b117a57e1af9816d08d9135ab4fe43a60","119dfcd214191405b7f7f7c7091b89196c0cae818bfcd8252a48f20d9cf3c378","4d9403482ca177c669df34a60bb2afab7a18097012d0b70703c8e59258cdfee6"],"recursive_tree_siblings":[{"right_hashes":["e041eaa366259f873e9e1477aac77362f4b1b460c2d5e1c14907fa9288d66cff","b45a8c503e649ff39543a918996b06fc65f4df9b61d071b22f7342f94862c9be","e00ec1225dfe6b7e950f6b9b8e9d1121bf17eb60c444fd7191b861a2ddddad23","c02c12beb73c03f996508cdce7bef927f0aa8b77ebd899f6a75df83de9d4022e","d36b95f14c5fd5bfaf1347e3177340e2fc9475a77b852321b80527132e7d539c","c0b9770178e70a7bba4ac8aeaadab2bcb2ae7f90d0f678bd463f2c42ff4f4a7b","fab5e7c6f7f8bc6d51f515c5db235cc1ebe987adee8c19c9bc7313e9e266d72c","b3884fb88fc95949c78ca8867cfa9e8a3c4c59fa1a48d8371f7fbfbebda0acfd","0c6da9bdbd40065f92ddaa45297670f2f0bffedb74020c5d5752e70d8b507b77","left_hashes":["1101beee3c6a36a168ceee9d43fcf6cb6de7e5c87ed4d22cd0308c9870d17839","d40a8e9eb4c873996ec515600def480eaa9378ca8481a7bcdf5f77725dbec4ae","63b12566ba8473f502386e92d500664cb63683dca6c26593378dcc9715257b77","166440a8ccbfbc1ce6ec5efaf8bc0b25e1bf692fa972e2729e45ce709d1d35a3","724451ad1d937fc47de5ede930d159dce78093d5e6a1f2e698452f8a29b4de3a","081a88f12d4e23173a1bf5038d4a9413cc92dd421c92261065de06492b5010ec","a76dbb1d4c393539b9546f4460d50ebc7582748d7de63c62c463b793c55bac7c","91e6c21de3f4060e1bd864131a570af42de31bbcd84a5afcbbc8fedcbf806002","fad08eca5bfdc5f37d39eabb44c2216afc6498afcb6b913d72586eaaf132a572","d39b06fe28387ba8045e2b2f95e90613916beef4f79df7961514e6e4cbfd07fa","81d07e300a116a0e4fcb56c39715c5fd5921abe8d10329b07c3f33d417b70ca8","7b72a7e62a45c9958a8a55eec2ba47352f2af701bacba098668589f6a3ce0423","8766bc64c38c2bb4188d89de0e732bca103daaed0c779cba9a8b191e24b51c9c","fa57ae4409e46c605f3cbfd01dfd9ccebc86cbd765cdc067206cb9367832442f"]}, ...... "index":9583119,"account":{"id":"50f5f08cc5036e15a541c64ac4ac6d2d9aa8ddab1ec32ed58b10e6ed3edfad59","debt":["0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"],"equity":["8412384","9386185","45265193","0","0","8751","3824171","2716990","0","313671","28319","0","0","0","41261","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","142353","0","0","0","0","0","4435","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","662","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","993","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","25132","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","305","0","0","0","0","0","0","0","0","6141","0","0","0","0","0","0","0","0","0","0","0","5511","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"]}}

6. Descarregar a ferramenta de verificação de código aberto OKX: zk-STARKValidator

7. Guarde a ferramenta de verificação de código aberto OKX, zk-STARKValidator, e o ficheiro de string JSON juntos na nova pasta criada no Passo 5. No nosso caso, colocámos a ferramenta e o ficheiro de dados na pasta Transferências, chamada "prova de reservas", conforme mostrado abaixo:

   

8. Abra o zk-STARKValidator; este executará automaticamente o ficheiro JSON que guardou na pasta

9. Verificar o resultado:

   • Se a verificação for aprovada, será apresentado o resultado Validação da restrição de inclusão aprovada:

     

   • Se a verificação falhar, será apresentado o resultado Validação da restrição de inclusão falhou:

     

Como posso verificar o saldo total do zk-STARK e a restrição não negativa?

Eis como pode verificar se os ativos que afirmamos possuir são verdadeiros e se nenhum utilizador possui património líquido negativo:

1. Vá à nossa páginaProva de Reserva e selecione Relatório de Responsabilidade

2. Descarregue o ficheiro zk-STARK e guarde-o numa nova pasta

   

3. Descompacte o ficheiro para extrair um ficheiro "sum_proof_data.json

   

4. Descarregar a ferramenta de verificação de código aberto OKX: zk-STARKValidator

5. Guarde a ferramenta de verificação de código aberto OKX, zk-STARKValidator, e o ficheiro "sum_proof_data.json" juntos na nova pasta criada no Passo 2. No nosso caso, colocámos a ferramenta e o ficheiro de dados na pasta Transferências, chamada "prova de reservas", conforme mostrado abaixo:

   

6. Abra o zk-STARKValidator; este executará automaticamente o ficheiro de dados de prova de soma que guardou na pasta

7. Verificar o resultado

   • Se a verificação for aprovada, será apresentado o resultado Soma total e validação de restrição não negativa aprovada:

     

   • Se a verificação falhar, será apresentado o resultado Soma total e a validação da restrição não-negativa falhou:

     

Para explorar mais detalhes técnicos, o nosso sistema de Prova de Reservas é de código aberto e está disponível para revisão e uso em github.