O que você precisará:
- uma formação em ciência da computação
- o básico do Ethereum
- os fundamentos do cálculo (otimização de restrições)
O que você vai ter:
- os fundamentos dos SNARKs de conhecimento zero
- o básico das árvores Merkle
- como o Ethereum poderia escalar para milhares de transações por segundo graças aos SNARKs
SNARKs permitem que um provador prove a um verificador que ele/ela tem uma solução W para o problema F com entradas compartilhadas/conhecidas X, sem revelar W.
Encontrar a solução para o problema pode exigir uma enorme quantidade de poder computacional e memória.
Portanto, o verificador pode basicamente ter 100% de certeza de que o provador funcionou corretamente (e encontrou uma solução), sem refazer o trabalho sozinho para verificar a solução, nem saber a solução. É Magica!
O processo tem 3 etapas:
- CONFIGURAÇÃO — O problema F (que precisa ser expresso como programa aritmético quadrático, veja abaixo) é preparado para SNARKs. Este processo exige muita memória e computação dependendo da complexidade do problema (→ O número de entradas e restrições → A dimensão da matriz do problema de satisfação das restrições). O jogador que faz o Setup (pode ser o próprio Verificador) deve ser de confiança de todas as partes, já que a saída do Setup é utilizada nas próximas fases. A configuração geralmente é feita usando biblioteca, uma biblioteca C++ que é a implementação mais popular para zkSNARKs.
- PROVANDO — O Provador, que tem uma solução W para o problema F com entradas compartilhadas X (talvez ele/ela tenha gasto enormes quantidades de CPU e memória para encontrá-la!), usa biblioteca e a saída do instalação fase para criar uma prova 𝚷. Este processo definitivamente exige muita memória e computação (dependendo da complexidade do problema, como acima). O tamanho da saída (ou seja, prova 𝚷) é, em vez disso, sucinto e constante, independentemente da complexidade do problema. O Provador precisa confiar em quem fez a fase de Configuração, pois ele/ela utiliza sua saída…
- VERIFICANDO — Um Verificador — dando como entrada a saída da fase de Configuração, entradas compartilhadas X e prova 𝚷 – verifica a prova. Se a verificação for bem-sucedida, o Provador conseguiu provar ao Verificador que encontrou a solução W para o problema F… sem revelar W! A parte boa é que não só a Prova é sucinta e tem sempre o mesmo comprimento..., o processo de verificação é rápido e não consome muita memória/computação. Ao contrário das duas fases anteriores… a verificação pode ser feita facilmente com um smartphone em milissegundos!
Uma boa recapitulação (fonte):
Como isso pode acontecer? Bem, é a magia de Merlin! Se você quiser entender a matemática por trás disso, comece daqui.
Como posso transformar meu software em um programa de aritmética quadrática?
Conforme mencionado acima, o problema F da fase de configuração precisa ser um programa aritmético quadrático. As regras do jogo são difíceis:
- As entradas do seu software devem ser números. Converta suas coisas (matrizes, strings, etc.) em números. Isso é trivial.
- Um “sistema de equações quadraticamente restrito” significa:
onde x é o vetor n-dimensional de suas entradas, m é o número de restrições (ou seja, o número de equações do seu sistema), C é a matriz de coeficientes n por n e q é um vetor de coeficientes n-dimensionais. Se você não gosta de matrizes e vetores, aqui está o caso n = 3 e m = 2 (3 entradas, 2 restrições):
- A implementação é um circuito aritmético, o que significa que o resultado é Problema resolvido (o sistema está resolvido, ou seja, todos os polinômios são iguais a 0) ou Problema não resolvido (todos os outros casos). Ou seja: “estes inputs são/não são uma das soluções para este Problema”.
- Os coeficientes C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 são as restrições do sistema. Isso é basicamente o que define o seu software. Mude-os… e você obterá outro software! Voltando a como funcionam os SNARKs: C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 são as entradas da fase de configuração. A saída da fase de configuração (que você precisa para provar e verificar) está, portanto, estritamente relacionada a C₁, C₂,…, C𝚖, q₁, q₂,…, q𝚖 e funciona apenas para esse problema. Se você alterá-los, você estará definindo outro software/problema e precisará executar novamente a fase de configuração! x₁, x₂,…, x𝗇 são as variáveis (ou seja, o que você precisa adivinhar para obter a solução de um sistema). Então, quando dizemos “Caro provador, você poderia encontrar uma solução secreta W para o problema F com entradas compartilhadas/públicas X” queremos dizer, por exemplo, “Caro provador, você pode encontrar os valores x₁, x₂,…, x𝗇 que resolvem o sistema com, por exemplo, x₇ = 2393, x₅₂₆ = 5647?” Você pode fazer o que quiser com todos os x𝗇, exceto x₇ e x₅₂₆, que são restritos às entradas compartilhadas/públicas.
É uma vida difícil, mas você pode sobreviver… Se precisar de loops, você pode desdobrá-los repetindo a mesma operação várias vezes. Ou se você precisar, por exemplo, de x₁⁴ x₂⁵, defina uma nova entrada x₃ = x₁⁴ x₂⁵ e use x₃ em suas restrições. É tudo uma questão de adicionar variáveis e restrições… Mesmo para softwares bastante simples, é fácil alcançar centenas de milhões ou bilhões de entradas e restrições!
Quer saber mais? Ler SUA PARTICIPAÇÃO FAZ A DIFERENÇA. E também confira este básico code_to_r1cs.py de ethereum/pesquisa.
O que é uma árvore Merkle?
Uma função hash é uma regra que mapeia uma entrada de tamanho arbitrário para uma saída de tamanho fixo. Poderíamos inventar uma função hash bastante inútil “Concatenar as duas primeiras com as duas últimas letras” que transforma “Woody Allen” em “Woen” e “Paul McCartney” em “Paey”.
Uma árvore Merkle é uma estrutura de dados onde cada pai é o hash de seus dois filhos. No topo você encontra o Root, que é o hash dos dois filhos do nível 1. Na parte inferior, cada folha é o hash de uma entrada externa.
Usando nossa função hash fictícia “Woody Allen”→”Woen”:
Quando uma folha muda, a modificação é propagada até a raiz. Se ANTHONY muda, também mudam ANNY (folha), CENY e CECO (raiz). Qualquer que seja a folha que mude, a raiz também muda.
Você não precisa da árvore inteira para recalcular a raiz. Em nosso exemplo, se ANTHONY mudar e você conhecer JACO e CECÍLIA, poderá recalcular facilmente a raiz, mesmo ignorando completamente JAMES, MARCO, JAES e MACO. Para árvores enormes, isso economiza muito tempo!
Então o quê?
As árvores Merkle são ótimas para verificações de integridade de dados. Normalmente: você sabe qual é a raiz válida e verifica se os dados recebidos correspondem a essa raiz. Por exemplo: uma parte confiável que não pode fornecer todo o conjunto de dados dos primeiros nomes das pessoas na Terra (sem tempo, sem largura de banda ou talvez ela/ele não tenha nenhum dado) fornece apenas a raiz (por exemplo, “CECO”). Posfácio: você recebe milhões de nomes próprios, com referência ao número da folha, de milhares de pessoas não confiáveis. Bem, como você tem o Root correto, você pode verificar em quem pode confiar, quem está lhe fornecendo dados falsos…
As árvores Merkle também fazem parte da sua vida! Quando você baixa um arquivo Torrent de 3 GB, seu arquivo é dividido em milhões de pequenos pedaços. O hash de cada pedaço é armazenado em uma folha. Como você sabe qual é a raiz válida da árvore, toda vez que receber um pedaço do arquivo de alguém, você poderá verificar se está correto. Se não for, você pode pedir o mesmo pedaço para outra pessoa.
Você pode fazer isso mesmo que ainda não tenha baixado a árvore inteira/todas as folhas: se você sabe que a raiz é CECO e confia no JACO… ao receber o pedaço ANTHONY você pode verificá-lo mesmo que não tenha baixado ainda os pedaços MARCO e JAMES.
A razão pela qual as árvores Merkle são úteis na tecnologia de contabilidade distribuída é simples: você usa protocolos de consenso (lentos, caros) apenas para chegar a um consenso na raiz. Assim, os nós não confiáveis da rede podem compartilhar dados de maneira eficiente e direta... e podem dormir sãos e salvos graças às verificações de integridade com o Root.
Quando Deus pediu ao Ethereum para escolher 2 superpoderes entre Segurança, Escalabilidade e Descentralização… Ethereum sacrificou a Escalabilidade. Na verdade não existe um limite forte para “transações por segundo”: o limite diz respeito à quantidade de gás de cada bloco — que é, simplificando, a quantidade de operações que posso fazer em cada bloco. Esse limite é de 8 milhões de gás. Isso pode significar muitas transações “pequenas” (nenhum dado anexado às transações, nenhuma operação a ser executada nesses dados) ou poucas transações grandes. Cabe aos nós do Ethereum, que enviam as transações, e aos mineradores do Ethereum, que incluem no bloco as transações que pagam mais.
Um bloco é minado cada ~15 segundos. Isso significa cerca de 32 milhões de gás por minuto, o que definitivamente não é suficiente se quisermos que os dapps do Ethereum se tornem populares.
A propósito: pare com aquelas comparações tediosas entre Ethereum e Visa. Um sistema centralizado irá sempre seja mais rápido que o Ethereum… por design! Eles fazem coisas diferentes e você precisa deles em situações diferentes. Se você não precisa de descentralização e de um ambiente sem confiança… é claro que você deve escolher a Visa. Resumidamente: o fato de seu liquidificador girar mais rápido que sua máquina de lavar não significa que você lavará suas calças no liquidificador!
Vamos montar o quebra-cabeça! Imagine que você pudesse “comprimir” muitas pequenas transações em uma grande transação graças aos SNARKs. Se o gás gasto nesta grande transação for menor que a soma do gás gasto nas pequenas transações, isso significa que você está economizando gás.
E economizar gás significa:
- Os usuários gastam menos em transações em geral → Isso seria um impulso para todo o ecossistema
- Ser capaz de colocar mais coisas em um bloco → Ethereum girando mais rápido que o seu liquidificador!
Como funciona o Tech & Data Studio:
Existem usuários, um retransmissor (ou mais retransmissores) que agrega transações e um contrato inteligente.
- Os usuários dispostos a jogar este jogo enviam seu Ether (ou tokens) para um contrato inteligente auditado publicamente. Para cada novo jogador é criada uma nova folha na árvore Merkle. A folha inclui informações sobre o dono do Ether (seu endereço, que também é a chave pública), quantidade de Ether e nonce (o contador de transações dessa conta, que é 0 quando a folha é adicionada)
- Quando A deseja enviar Ether para B (ambos precisam ter uma folha/conta no contrato inteligente), A embala uma transação, que inclui o endereço do daconta, o para conta, o nonce da conta de origem, o quantidade de Ether a ser transferido e o assinatura da transação (assinada com a chave privada da conta “de”, obviamente). Ele/ela então envia a transação compactada para o retransmissor.
- O retransmissor agrega todas as transações recebidas em uma determinada janela de tempo (por exemplo, uma hora), atualiza a árvore Merkle com os valores dos novos saldos e cria uma prova SNARK que prova que todas as assinaturas e a nova raiz da árvore Merkle são válidas. O retransmissor finalmente envia o novo estado e a prova para o contrato inteligente.
- O contrato inteligente valida a Prova on-chain. Se for válido salva a raiz da árvore Merkle do estado Novo na memória interna do contrato.
Basicamente, a raiz da árvore Merkle representa todo o estado de todas as contas. E você não pode alterá-lo (= roubar dinheiro) a menos que possa provar a validade das assinaturas cujas transações levam ao estado Novo resumido pela nova raiz que você está enviando.
Resumindo: os usuários têm transações super rápidas e quase gratuitas, como no Coinbase, sem precisar confiar no retransmissor, que não pode fazer nada, ao contrário do Coinbase, sem a sua assinatura.
É uma cadeia lateral sem custódia cujo estado é resumido por uma raiz de árvore Merkle.
Vamos conectar o que aprendemos acima sobre SNARKs com o que acabamos de discutir sobre escalonamento. Existem diferentes maneiras de fazer isso. Vou comparar 2 receitas: Vitalik’s versão e BarryWhiteHat's versão.
A CONFIGURAÇÃO é feita por…
O cara que inicia o projeto, que também cria o contrato inteligente. Quanto mais auditável for, melhor. Você deve confiar nele... é um configuração confiável!
O contrato inteligente economiza…
2 raízes Merkle (valores bytes32): a primeira árvore contém endereços de contas (assinaturas públicas), a segunda árvore contém saldos e nonces
A PROVAÇÃO é feita por…
O retransmissor
O retransmissor envia para o contrato inteligente…
- as 2 raízes Merkle do Novo estado (árvore de endereços e árvore de saldos+nonces)
- a lista de transações, sem assinaturas. “Cada transação custa 68 gases por byte. Portanto, para uma transferência regular, podemos esperar que o custo marginal seja 68 * 3 (de) + 68 * 3 (para) + 68 * 1 (taxa) + 68 * 4 + 4 * 2 (valor) + 68 * 2 (nonce) ou gás 892”
As entradas conhecidas do processo PROVING são…
- as 2 raízes Merkle do antigo estado
- as 2 novas raízes Merkle do estado
- lista de transações
O processo PROVING prova que…
Dado
- as 2 raízes Merkle do antigo estado (já armazenadas no contrato)
- as 2 raízes Merkle do novo estado (enviadas na transação agregada)
- a lista de transações (enviada na transação agregada)
… o retransmissor tem assinaturas válidas para passar do estado com 2 raízes antigas para o estado com 2 raízes novas com essas transações.
A VERIFICAÇÃO é feita por…
O contrato inteligente (codificado em solidez, vyper, como você quiser!)
As entradas conhecidas do processo de VERIFICAÇÃO são…
As mesmas entradas conhecidas do processo PROVING, claramente…!
Limites à escalabilidade
Cada transação agregada usa 650k de gás para verificação SNARK (custo fixo) mais ~900 gás de custo marginal por transação (custa enviar dados!). Portanto, usando o bloco inteiro, o relé pode agregar no máximo:
que significa ~544 tx por segundo
BarryWhiteHat's versão
A CONFIGURAÇÃO é feita por…
O cara que inicia o projeto.
O contrato inteligente economiza…
1 Raiz Merkle com o estado atual. Cada folha é o estado hash de uma conta.
Quer crio uma conta?
estado = AccountState(pubkey, saldo, nonce)
estado.index = self._tree.append(estado.hash())
A PROVAÇÃO é feita por…
O retransmissor
O retransmissor envia para o contrato inteligente…
- prova 𝚷
- a raiz Merkle do novo estado
- prova 𝚷
As entradas conhecidas do processo PROVING são…
- a raiz Merkle do antigo estado
- a raiz Merkle do novo estado
O processo PROVING prova que…
Dado
- a raiz Old Merkle (já armazenada no contrato)
- a raiz New Merkle (senti na transação agregada)
… o retransmissor tem uma lista de transações com assinaturas válidas para passar do estado com raiz antiga para o estado com raiz nova
A VERIFICAÇÃO é feita por…
O contrato inteligente (codificado em solidez, vyper, como você quiser!)
As entradas conhecidas do processo de VERIFICAÇÃO são…
As mesmas entradas conhecidas do processo PROVING, claramente…!
Limites à escalabilidade
O retransmissor não está enviando dados de transações para o contrato inteligente (o que é caro), então o limite é na verdade a quantidade de gás para verificar a prova SNARK.
Mencionando Howard Wu trabalho sobre a execução da fase PROVING do SNARK em sistemas distribuídos, barryWhiteHat otimisticamente afirma que é possível confirmar 16666 transações em um enorme SNARK (1 bilhão de restrições!).
BarryWhiteHat também pensa é possível verificar a prova 𝚷 on-chain com gás 500k, o que significa que você pode colocar 16 SNARKs (8 milhões/500k) por bloco, o que é ~1.07 SNARKs por segundo… o que significa ~17,832 tx por segundo (16,666 * 1.07).
Ao infinito e além
- Nem tudo que reluz é ouro / 1. A quantidade de poder de computação e memória necessária na fase de prova pode ser literalmente chocante. Especialmente na versão de BarryWhiteHat, onde parte da complexidade é transferida para fora da cadeia. Barry escreve “Em um laptop com 7 GB de RAM e 20 GB de espaço de troca, ele tem dificuldade para agregar 20 transações por segundo”. Bem, se a meta é 17,832 tx por segundo… hahaha. Isso introduz desafios de computação paralela não triviais. Mas se o custo médio em dólares por transação for muito mais barato do que a opção comum sem SNARKs… o jogo vale a pena.
- Nem tudo que reluz é ouro / 2. Há um problema relevante de disponibilidade de dados! Como apenas a raiz da árvore é salva no contrato, você deve ter certeza de que uma versão completa da árvore (ou, é a mesma coisa, todo o histórico de transações) está sempre disponível. Se os dados não estiverem disponíveis, o retransmissor, mesmo com transações assinadas válidas, não pode fazer nada porque não pode provar Estado Antigo → Transações → Estado Novo.
- Para que o retransmissor não seja confiável e os Ethers no contrato tenham o mesmo valor dos Ethers externos (problema de liquidez)… os usuários devem poder sacar dinheiro do contrato inteligente quando quiserem, sem depender de um retransmissor (específico). Como? Isso não está no escopo desta postagem 101, mas você pode ler sobre isso nos links incluídos.
- Quer entender mais sobre como o estado atual (endereços, saldos e nonces) pode ser tratado com uma árvore Merkle? Adicionando uma folha, atualizando uma folha, etc? Confira esta biblioteca (arquivo de teste SUA PARTICIPAÇÃO FAZ A DIFERENÇA) que usa esse subjacente módulo. Obrigado HarryR!
- Quer configurar seu ambiente pessoal Ethereum-SNARKs? Vamos começar fora da cadeia com C++ (configuração, prova, verificação) SUA PARTICIPAÇÃO FAZ A DIFERENÇA. Então você pode mudar para Ethereum (não se esqueça, apenas a verificação é feita on-chain!) com Zokrates (repo, documentação para começar).
- Que tal usar acumuladores RSA em vez de árvores Merkle? Google “acumuladores rsa ethereum” para iniciar…
Divirta-se!
Twitter @marco_derossi
- 7
- Conta
- Todos os Produtos
- entre
- disponibilidade
- fundamentos básicos
- bilhão
- casos
- alterar
- Cheques
- coinbase
- computação
- Consenso
- contract
- custos
- Atual
- Estado atual
- DApps
- dados,
- conjunto de dados
- Descentralização
- Dimensão
- Ledger distribuído
- tecnologia de contabilidade distribuída
- Meio Ambiente
- Ether
- ethereum
- EU
- EV
- falsificação
- Finalmente
- Primeiro nome
- Gratuito
- função
- jogo
- GAS
- GitHub
- Dando
- Dourado
- Bom estado, com sinais de uso
- ótimo
- guia
- hash
- SUA PARTICIPAÇÃO FAZ A DIFERENÇA
- Alta
- história
- Como funciona o dobrador de carta de canal
- hr
- HTTPS
- enorme
- Centenas
- ia
- índice
- INFORMAÇÕES
- IP
- IT
- Trabalho
- Chave
- laptop
- grande
- conduzir
- Ledger
- Nível
- LG
- Biblioteca
- Liquidez
- Lista
- Corrente principal
- mapas
- média
- milhão
- Mineradores
- dinheiro
- mês
- Mais populares
- mover
- nomes
- rede
- nós
- números
- Operações
- ordem
- Outros
- proprietário
- Pagar
- Pessoas
- jogador
- Popular
- poder
- privado
- chave privada
- Agenda
- projeto
- prova
- Prova
- público
- chave pública
- recapitulação
- rsa
- regras
- corrida
- seguro
- poupança
- AMPLIAR
- Escala
- dimensionamento
- Ciência
- segurança
- conjunto
- Partilhar
- compartilhado
- Baixo
- simples
- Tamanho
- dormir
- smart
- smart contract
- smartphones
- So
- Software
- solidez
- Soluções
- RESOLVER
- Espaço
- Passar
- começo
- começado
- Estado
- Unidos
- bem sucedido
- .
- sistemas
- Equipar
- teste
- tempo
- Tokens
- topo
- torrente
- transação
- Transações
- Confiança
- Atualizações
- usuários
- valor
- Verificação
- visto
- W
- QUEM
- palavras
- Atividades:
- trabalho
- Equivalente há
- X