Como zk-SNARKs melhoram o sistema de Proof of Reserves da Binance
Principais tópicos do post:
Em novembro de 2022, a Binance lançou seu sistema de Proof of Reserves utilizando a criptografia de Merkle tree para permitir que os usuários verifiquem seus holdings.
A Binance agora aprimorou sua solução implementando zk-SNARKs, uma forma de zero-knowledge proof.
Os usuários agora podem verificar se o saldo líquido total de cada conta não é negativo e se todos os ativos do usuário fazem parte do saldo líquido total de ativos do usuário informado pela Binance – de maneira privada e segura.
Dê uma olhada nos bastidores da nova solução proof-of-reserves da Binance. Combinando zk-SNARKs e informações da Merkle tree, ela oferece aos usuários uma maneira nova e aprimorada de verificar o estado das reservas da Binance.
Nos últimos meses, a equipe de desenvolvimento da Binance tem trabalhado arduamente para criar soluções avançadas de proof-of-solvency. Essas ferramentas tornaram-se importantes para as corretoras de criptomoedas centralizadas em meio à crise de confiança que tomou o setor após o colapso do FTX. Os fundos dos usuários armazenados na Binance são garantidos em uma proporção de 1:1, mais reservas, e encontrar uma maneira de provar isso ao público se tornou uma parte importante do plano da Binance para restaurar a confiança do setor.
Em novembro de 2022, lançamos nosso sistema de proof-of-reserves utilizando uma técnica criptográfica de Merkle tree para permitir que os usuários verifiquem seus ativos na Binance. Embora seja um avanço no esforço de transparência de fundos de usuários da Binance, o design inicial dessa solução tinha duas deficiências:
Para proteger a privacidade do usuário, os nodes da leaf na Merkle proof representavam o hash dos holdings dos usuários – portanto, a Merkle root não podia refletir a soma das informações de saldo de seus nodes da leaf.
A entidade cujas reservas estavam sendo verificadas poderia adicionar um saldo negativo em uma conta falsa em algum lugar da árvore para fazer com que o total de reservas exigidas parecesse menor. O diagrama a seguir do blog do Vitalik Buterin mostra um exemplo de uma Merkle tree maliciosa (embora, neste caso, a root (raiz) reflita a soma dos saldos de todos os nodes (nós) da leaf (folha), o que pode ser um problema para privacidade).
Agora temos uma solução que pode remediar essas deficiências e, assim, fortalecer o sistema de proof-of-reserves da Binance. Com base em protocolos zero-knowledge proof, zk-SNARKs, podemos provar que:
Todos os nodes leaf da Merkle tree contribuíram para o saldo total de cada ativo reivindicado pela Binance.
Não há usuários com saldo líquido total negativo (um valor geral em USD de todos os ativos que o usuário possui) incluídos na Merkle tree.
Sobre saldos negativos e desempenho
Como a Binance oferece margem, empréstimos de criptomoedas e produtos de negociação de futuros, o saldo de cada criptoativo de cada usuário pode ser composto de ativos e passivos. O saldo de um determinado criptoativo de um usuário pode ser negativo, mas seu saldo líquido total em todos os criptoativos não deve ser negativo (já que todos os empréstimos são totalmente garantidos).
Nesse cenário hipotético, digamos que Alice tenha depositado 10.000 BUSD na Binance e depois usado 4.000 BUSD como garantia para obter empréstimo de 2 BNB (a uma taxa de 1 BNB = 1.000 BUSD, supondo que a Binance esteja sempre optando por garantias em excesso). A tabela abaixo mostra o saldo da Alice.
Se Alice então negociar 1 BNB por 1.000 BUSD com Bob (que também depositou 10.000 BUSD), seu saldo ficaria assim após a negociação ser correspondida:
Nesse caso, o saldo de BNB da Alice será -1, que não é um node válido em uma Merkle tree e que cobre apenas um ativo: BNB. No entanto, se estivermos olhando para os saldos líquidos totais, Alice ainda está em 10.000.
Outro desafio vem da escala da base de usuários da Binance. Uma solução viável deve gerar prova de usuário e prova zk-SNARK para dezenas de milhões de usuários, alguns dos quais podem ter mais de 300 criptoativos em nossa plataforma.
Em suma, queremos fornecer prova dos seguintes fatos dentro de uma janela de tempo razoável:
Os ativos de cada usuário da Binance fazem parte do saldo total reivindicado do usuário mostrado no snapshot. Os usuários podem verificar nosso saldo total reivindicado em relação aos ativos mantidos em endereços controlados pela Binance utilizando um explorador de blockchain (como o Etherscan para carteiras Ethereum ou BscScan para carteiras BNB Chain).
O saldo líquido total de cada usuário não é negativo, o que significa que a Binance não criou contas fictícias com saldo negativo para reduzir artificialmente o tamanho de nossas reservas verificadas.
O que são zk-SNARKs?
Antes de mergulharmos nos detalhes de nossa solução, uma breve visão geral do mecanismo de zero-knowledge proof é necessária. Protocolos de zero-knowledge como o zk-SNARK permitem que uma parte, o provador, demonstre à outra parte, o verificador, que o provador executou certos cálculos com precisão com certas entradas sob certas restrições, tudo sem divulgar as entradas. A computação pode ser demorada, mas o mecanismo matemático subjacente pode ajudar o verificador a avaliar a prova de forma rápida e segura.
O provador (Binance) começa definindo um conjunto de restrições da computação que deseja provar. As restrições são definidas em circuitos que podem ser expressos em uma linguagem de programação de alto nível (no nosso caso, uma versão que passou por fork do gnark.)
O provador então executa o cálculo pesado, fazendo hash de todos os IDs e saldos dos usuários, e gera provas de que o cálculo atende às restrições estabelecidas anteriormente. Para fazer isso, ele usa o rastreamento de computação (testemunha) e entradas públicas ou privadas.
O verificador (usuário) obtém a prova e a verifica com a entrada pública do circuito para se certificar de que a computação foi executada com precisão atendendo a todas as restrições. O cálculo de verificação leva um tempo extremamente curto em comparação com o tempo de prova. Se o provador não gerar a prova nos circuitos predefinidos, não poderá produzir prova válida para passar na verificação.
Para dar uma olhada mais profunda sob o capô dos zk-SNARKs, você pode consultar esta série de artigos.
Nossa solução
O bloco de construção fundamental da solução atualizada de proof-of-reserves ainda é uma Merkle tree. Para o exemplo acima, ficaria assim:
Além da Merkle tree, também mantemos um estado global que representa uma lista dos saldos líquidos totais de cada ativo que cada cliente da Binance possui.
Para provar nossas reservas, vamos gerar provas zk-SNARK para a construção da Merkle tree. Para o conjunto de saldos de cada usuário – um node leaf da Merkle tree – nosso circuito garantiria que:
O saldo de todos os ativos desse usuário está incluído na lista de estados globais mencionada acima.
O saldo líquido total do usuário não é negativo.
A alteração da Merkle tree root é válida após atualizar as informações desse usuário para o hash do node leaf.
Consulte esta especificação técnica e nosso código-fonte para o circuito (restrições) para saber os detalhes da implementação.
Em cada instância de comprovação de nossas reservas, publicaremos:
1. A prova Merkle: os hashes para cada usuário (para Alice, representado por nodes azuis na figura acima).
2. zk-SNARK proofs e entradas públicas (uma hash da lista de saldos líquidos totais de cada ativo e a Merkle root) do circuito para todos os usuários.
Ao verificar a prova Merkle, os usuários podem garantir que seu balanço esteja incluído na root (raiz) da Merkle tree. Ao verificar a prova zk-SNARK, os usuários podem garantir que a construção da Merkle tree atenda às restrições definidas no circuito.
A segurança desta solução depende muito da configuração da chave de prova e da chave de verificação. Estamos trabalhando em uma configuração descentralizada das chaves. Quando se trata de cerimônias de configuração confiáveis descentralizadas existentes, a cerimônia Ethereum oferece um bom exemplo. Estamos muito perto de ter uma solução de MPC para tornar a configuração confiável.
Desempenho
Dado o número de usuários da Binance cujos saldos devem ser incluídos, não há como obter uma única prova da construção da Merkle tree que abranja todos os usuários de uma só vez. Uma solução para isso é dividir os usuários em lotes de 864 cada, de modo a ter um circuito de menor escala e procedimentos de prova paralelos.
Para um lote que contém 864 usuários em que cada usuário possui 350 ativos diferentes, suponha que o saldo de cada ativo esteja no intervalo [0, 2^64-1]. Com um servidor de 128 GB e 32 núcleos, o tempo de geração da prova zk é de cerca de 110 segundos e o tempo de verificação da prova é inferior a 1 milissegundo.
A Binance iniciará 1.000 provadores ao mesmo tempo para gerar provas para todas as contas em 2 horas. O custo desse servidor de prova por hora é de cerca de 0,56 USD, portanto, o custo total de geração de todas as provas zk que abrangem todos os usuários seria de cerca de 1.000 USD.
Conclusão
Forneceremos a primeira iteração da prova para usuários, gerada por esta nova solução, em um anúncio subsequente de proof-of-reserves. Além disso, abrimos o código do nosso processador de dados do usuário, provador, circuito e verificador, para que cada corretora centralizada que depende do mesmo modelo possa gerar, facilmente, provas para seus usuários e ativos.
Esperamos que isso seja fundamental para levar a transparência da indústria de ativos digitais a um novo nível. Também estamos trabalhando na implementação da solução mencionada no blog do Vitalik para obter um melhor desempenho, o que nos permitirá fornecer a prova com mais frequência a um custo menor.
Como esta é a primeira versão do nosso zk-SNARK, estamos ansiosos para receber feedback da comunidade para que possamos continuar a melhorar o sistema.