Hashing e compromissos: o envelope selado mágico

Pesquisa original de Annkkitaaa

Como guardar um segredo em público e nunca poder mentir sobre ele

Série: Zcash from First Principles . Artigo 3 . Hashing e compromissos Público: iniciantes. Partimos do Artigo 1 (campos finitos) e do Artigo 2 (curvas elípticas), mas a intuição se sustenta por si só. O que você vai levar daqui: uma compreensão clara de funções hash, do que "hiding" e "binding" realmente significam e de como o Zcash constrói os compromissos de notes que ancoram cada pagamento privado.

No Artigo 0, descrevemos um "envelope selado mágico": algo que você pode prender em um quadro público para provar que um envelope existe enquanto esconde o que há dentro e que você nunca poderá trocar depois. Prometemos explicar como algo assim é possível. Este é esse artigo. Precisamos de dois ingredientes: funções hash e compromissos.

1. Por que isso deveria importar para você?

Imagine que você prevê o resultado de uma eleição e quer provar, depois, que acertou com antecedência. Você não pode simplesmente anunciar sua previsão (isso influencia as pessoas ou convida a acusações de que você a mudou). E também não pode mantê-la totalmente secreta (aí não poderá provar nada mais tarde).

O que você quer é uma forma de fixar um valor agora, em público, de tal maneira que:

• ninguém consiga dizer o que você fixou (isso permanece secreto por enquanto), e
• mais tarde, quando você o revelar, você não possa mentir sobre o que era.

Esse mecanismo de "fixar agora, revelar depois, sem mentir" é chamado de compromisso, e ele está por toda parte no Zcash. O valor e o proprietário de uma note ficam fixados em um compromisso no momento em que a note é criada. Para construir compromissos, primeiro precisamos do seu cavalo de batalha: a função hash.

2. A intuição: uma impressão digital para dados

Uma função hash pega quaisquer dados, desde uma única letra até uma biblioteca inteira, e os comprime em uma string curta de tamanho fixo chamada digest ou hash. Pense nela como uma impressão digital para dados.

Uma boa impressão digital criptográfica tem quatro propriedades. Guarde-as como intuições, não como equações:

E mais um comportamento que faz essas impressões digitais parecerem quase mágicas:

O efeito avalanche (verificado)

Mude a entrada na menor quantidade possível e a impressão digital muda completamente, sem qualquer semelhança com a anterior. Aqui estão duas impressões digitais SHA-256 reais de mensagens que diferem por um único caractere:

H("Pay Bob 5 ZEC") = 6e2dc1a954c70cc865f18ea8cb70b7b56eeaf6ca42b380824a55d65dc342f34b
H("Pay Bob 6 ZEC") = 76abc346d8d3053f76a9ae18b617af71f02729a73ec6a51732d2d94934e4217f

De 64 dígitos hexadecimais, 59 são diferentes. Um caractere entra, uma impressão digital totalmente diferente sai. É por isso que você não pode ajustar uma entrada gradualmente em direção a uma impressão digital-alvo: não existe nenhum sinal de "mais quente / mais frio" para seguir.

3. Da impressão digital ao compromisso

Aqui vai uma ideia tentadora, mas falha: para se comprometer com um valor secreto v, basta publicar sua impressão digital H(v).

Isso faz um bom binding (você não pode depois alegar um v diferente, porque isso exigiria uma colisão). Mas falha em esconder. Se o conjunto de valores possíveis for pequeno, um atacante simplesmente calcula a impressão digital de cada candidato e compara. Comprometendo-se com "sim" ou "não"? Ele aplica hash aos dois e descobre instantaneamente qual você escolheu. O determinismo, nosso amigo há um momento, agora está vazando o segredo.

A correção é uma palavra: aleatoriedade.

Um compromisso é a impressão digital do seu valor misturada com um número aleatório novo: commitment = H(v, r) onde r é um valor aleatório secreto de "blinding".

Agora o mesmo v produz um compromisso com aparência diferente toda vez, porque r é diferente. As duas propriedades que queríamos finalmente passam a valer ao mesmo tempo:

Para abrir (revelar) o compromisso mais tarde, você publica v e r; qualquer pessoa recalcula H(v, r) e verifica se coincide. Você ficou preso àquele valor. Esse é o envelope selado mágico do Artigo 0, tornado real.

Duas conclusões para levar para sempre: binding vem do fato de o hash ser resistente a colisões; hiding vem do fator de blinding aleatório r.

4. Duas formas de construir o envelope

Existem duas receitas comuns, e o Zcash usa ambas.

Essa última linha é o motivo de os compromissos de Pedersen importarem tanto no Zcash. Como commit(v_1) + commit(v_2) é um commit(v_1 + v_2) válido, o protocolo pode depois provar que o dinheiro que entra é igual ao dinheiro que sai somando compromissos, tudo isso sem revelar um único valor. Vamos guardar esse fato para o Artigo 6.

5. Uma sutileza que molda todo o Zcash: hashing amigável para ZK

Aqui está uma percepção que a maioria das introduções deixa passar, e é exatamente o ponto "matemática encontra engenharia" que vale destacar.

SHA-256 é uma impressão digital excelente para a computação do dia a dia. Mas o Zcash não apenas calcula hashes; ele precisa provar, dentro de uma prova de conhecimento zero, que um hash foi calculado corretamente (o Artigo 5 explica por quê). E aqui está a pegadinha: uma prova de conhecimento zero funciona na linguagem da aritmética de campos finitos (Artigo 1), enquanto SHA-256 é construído com operações de manipulação de bits (deslocamentos, ANDs, XORs). Expressar toda essa manipulação de bits em aritmética de campo é enormemente caro, tornando as provas grandes e lentas.

Por isso, os criptógrafos do Zcash projetaram funções hash cujos mecanismos internos já são aritmética de campo, tornando-as baratas de provar:

Essa única pressão de engenharia, "tem que ser barato de provar," é o motivo pelo qual o Zcash inventou e adotou funções hash especiais em vez de recorrer ao SHA-256 em toda parte.

6. Onde isso está no Zcash

O Zcash usou hashes diferentes ao longo de seus designs, cada um escolhido para a tarefa:

Os nomes a reconhecer são Pedersen e Sinsemilla (hashes no estilo de compromissos construídos a partir de pontos de curva, então herdam o superpoder de "se somar" e são baratos de provar) e Poseidon (um hash de aritmética de campo criado especificamente para circuitos de conhecimento zero). Quando o Artigo 0 disse que o conteúdo de uma note é selado em um compromisso, é esta a maquinaria que faz a selagem.

Assim, o ciclo aberto no Artigo 0, "como um envelope selado pode esconder seu conteúdo e ainda assim ser impossível de falsificar?", agora está fechado: hiding vem de um fator de blinding aleatório, binding vem da resistência a colisões ou do problema difícil da curva.

7. Um aviso honesto

Simplificamos para manter a clareza. Esquemas reais de compromisso especificam exatamente como v e r são codificados e quais geradores são usados; "hiding" e "binding" vêm em variantes (perfeito vs. computacional) com definições de segurança precisas; e não mostramos os mecanismos internos de Pedersen, Sinsemilla ou Poseidon. Nada disso muda a intuição: um compromisso é uma impressão digital mais aleatoriedade que esconde agora e vincula para sempre. Os detalhes voltarão, sinalizados, quando o artigo sobre o protocolo precisar deles.

8. Resumo

• Uma função hash é uma impressão digital para dados: determinística, rápida no sentido direto, unidirecional, resistente a colisões, com efeito avalanche (um bit entra, uma impressão digital totalmente diferente sai).
• Um compromisso permite que você fixe um valor em público agora e o revele depois sem poder mentir.
• Publicar uma impressão digital pura H(v) faz binding, mas não esconde. Adicionar um fator de blinding aleatório, H(v, r), resolve isso: hiding vem de r, binding vem da resistência a colisões.
• O Zcash usa tanto compromissos baseados em hash quanto Pedersen; os compromissos de Pedersen, além disso, se somam, algo que o Artigo 6 vai explorar para provar o balanceamento de valor em privado.
• Como hashes precisam ser provados dentro de provas de conhecimento zero, o Zcash usa hashes amigáveis para ZK construídos a partir de aritmética de campo (Pedersen, Sinsemilla, Poseidon) em vez de SHA-256 em toda parte.

Glossário

FAQ

Por que não simplesmente criptografar o valor em vez de se comprometer com ele? Criptografia trata de sigilo que você pode descriptografar depois. Um compromisso trata de binding: a garantia de que você não pode mudar sua resposta depois. São trabalhos diferentes.

Se compromissos escondem o valor, como alguém verifica as regras? Esse é o papel das provas de conhecimento zero (Artigo 5): elas provam que o valor oculto obedece às regras sem revelá-lo.

O SHA-256 está quebrado, já que o Zcash o evita em alguns lugares? Não. SHA-256 está ótimo e o Zcash ainda o usa. Só que é caro de provar dentro de um circuito, e é por isso que existem hashes amigáveis para ZK para esse trabalho específico.

De onde vem o r aleatório e quem o guarda? Ele é gerado do zero quando a note é criada e é conhecido pelo proprietário da note. É parte do que torna cada note única e privada.

Teste sua intuição

Você se compromete com sua previsão eleitoral como H(v, r) e a publica. Um amigo insiste que você deveria publicar só H(v) para simplificar. Em uma frase, por que isso é uma má ideia se houver apenas dois resultados possíveis? (Resposta abaixo.)

O que vem a seguir

Artigo 4 . Árvores de Merkle: agora temos milhões de compromissos se acumulando. O Artigo 4 mostra como o Zcash os organiza em uma única árvore cuja pequena impressão digital raiz representa todo o histórico e como você pode provar que sua note está nessa árvore sem revelar qual é. Essa é a forma real do "quadro público" do Artigo 0.

Parte da série Zcash from First Principles para ZecHub. Licenciado sob CC BY-SA 4.0.