Provas de conhecimento zero: O que são os zk-STARKs e como funcionam?

1. O que é?

O sistema de Prova de Reservas (PoR) zk-STARK utiliza a teoria STARK, uma solução matemática complexa. zk-STARK significa: Zero-Knowledge Scalable Transparent Argument of Knowledge (ou argumento de conhecimento sucinto transparente de conhecimento-zero), uma tecnologia de prova de cripto baseada na ideia de Vitalik para impor a integridade e a privacidade dos cálculos em blockchains. Neste artigo, apresentaremos como funciona e explicaremos o conceito matemático geral, mas se tiver interesse em saber mais, comece por aqui ou aqui.

Como funciona?

Figura 1. Tabela de rastreamento de execução e árvore Merkle construída para zk-STARK PoR

Etapa 1: restrições de construção

Para provar a responsabilidade da nossa exchange, fazemos três afirmações:

Afirmação 1: Acumulamos os valores de todos os utilizadores corretamente, incluindo o valor de cada cripto e o valor líquido de cada utilizador

Afirmação 2: A exchange não falsificou um utilizador virtual cujo valor líquido seja negativo para reduzir o passivo total da exchange (um utilizador individual com saldos negativos só é aceitável se o seu valor líquido for superior a 0)

Afirmação 3: O valor total que a exchange declara representa cada utilizador, por isso, cada utilizador deve ser capaz de verificar a inclusão do seu valor líquido no valor total

Para testar e verificar as afirmações acima, é necessário construir restrições como:

Afirmação 1: Restrição de saldo total (Restrição de um saldo total correto)

uts: tamanho do rasto do utilizador, que é o número de linhas de ratos incluídas nos dados de cada utilizador.

soma: saldo total do utilizador

N: número de utilizadores

Afirmação 2: Restrição não negativa (Restrição de património líquido positivo)

Afirmação 3: Restrição de inclusão (Restrição de inclusão de todo o saldo da conta do cliente)

De acordo com as restrições acima, criamos uma tabela de rastreamento, para confirmar e verificar os saldos totais e a não negatividade através de inspeções de amostragem. Aqui está como a tabela de rastreamento é construída (para um exemplo simples, 3 utilizadores cujo valor máximo de USD é menor do que 4^6 = 4096):

1. Inicializamos uma tabela com 32 linhas e 5 colunas, e preenchemos os valores e IDs do utilizador na linha

, onde k % 8 = 6, e

. Cada 8 linhas é um bloco, e as informações de ativos do utilizador agora estão em

atrás de cada bloco. O primeiro utilizador recebe saldos virtuais 0, para que possamos publicá-lo para provar que o acumulação de valores não começa com um valor negativo.

2. Acumulamos os valores de ativos do utilizador um a um e preenchemos o resultado em

linhas onde k % 8 = 7, e

, que são as últimas linhas de cada bloco

3. Continuamos a dividir o valor total de cada utilizador por 4 linha por linha de

atrás de cada bloco. Fazemos isto para manter o valor líquido do utilizador não negativo, verificando se as primeiras linhas são zero para cada bloco. Se alguém tiver um valor líquido negativo, a primeira linha do bloco não será zero porque um valor negativo (-x) será (p - x) num campo finito

, que é um valor positivo muito grande.

4. Inserimos números aleatórios para cada utilizador e preenchemos os espaços em branco na tabela com 0

Etapa 2: Extensão polinomial de baixo grau Usando as restrições polinomiais acima, podemos obter um polinómio de rastreamento de computação de comprimento uts * N. Por motivos de segurança, realizamos o compromisso com o polinómio num domínio de avaliação maior, com o fator de amplificação do domínio como extensão_fator.

No caso acima, poderíamos calcular um polinómio p(x) a partir de I(x). Quando usamos uma extensão_fator de 8, calcularemos outros 32(8-1)* pontos em p(x).

Uma vez que dois polinómios diferentes com grau D partilharão no máximo pontos D, um exemplo de par polinomial com um polinómio válido (que satisfaça as restrições acima) e um polinómio falso com grau D (que não satisfaça as restrições acima) partilharão no máximo pontos D. Isto significa que um polinómio falso tem uma possibilidade de

de passar por uma inspeção de amostragem aleatória. Se fizermos a inspeção por amostragem n vezes, a possibilidade diminuirá para

.

Implementamos a extensão_fator padrão como 16 e o tempo padrão de inspeção de amostragem como 16, por isso, o nível de segurança será de 80 bits.

Etapa 3: compromisso polinomial Calculamos o valor de hash do rastreamento de computação e o saldo do utilizador correspondente, ID do utilizadore o valor do polinómio de restrição correspondente para cada linha e geramos uma árvore Merkle. A raiz Merkle é o valor de compromisso do polinómio.

Etapa 4: gerar prova de amostragem Usando a raiz Merkle como uma fonte aleatória, amostramos os dados. Para evitar o vazamento de dados de rastreamento de computação, evitamos os dados com um índice de *k ** extensão_factor durante a amostragem e gerar o caminho de prova Merkle correspondente ao índice de amostragem.

Fazemos as inspeções de amostragem para verificar se o polinómio confirmado é um polinómio válido que satisfaz as restrições listadas no Etapa 1. Conforme especificado no Etapa 2, os tempos das inspeções de amostragem afetarão a chance de adulteração ou manipulação bem-sucedida.

Etapa 5: geração de provas de baixo grau

Podemos controlar a probabilidade de adulteração ou sucesso da manipulação por meio de inspeção por amostragem. No entanto, há uma condição mencionada no Etapa 2 de que precisamos garantir que o grau do polinómio que está a ser verificado não seja maior do que o grau de um polinómio válido. Para melhorar a eficiência da prova, combinamos linearmente todos os polinómios de restrição num polinómio e geramos uma prova de baixo grau para ele. Os coeficientes de combinação também são gerados usando a raiz Merkle como fonte aleatória.

Por exemplo, se quisermos provar que p0(x), p1(x) e p2(x) não são mais do que D graus, podemos gerar 2 coeficientes aleatórios da raiz Merkle gerada no Etapa 3 e calcular o polinómio linear l(x) como:

k0 = hash(raiz + "0") k1 = hash(raiz + "1") l(x) = k0 * p0(x) k1 * p1(x) p2(x)

Se for possível provar que l(x) não é maior do que D grau, então a possibilidade de que o grau de qualquer um de p0(x), p1(x) e p2(x) seja maior do que D será próxima de 0

Etapa 6: verificação total do saldo Primeiro, verificamos a prova de baixo grau gerada no Etapa 5.

Em seguida, uma verificação aberta adicional é realizada nos dados amostrados gerados no Etapa 4. Primeiro para verificar se os dados são consistentes com o compromisso polinomial e segundo para verificar se os dados satisfazem as restrições construídas no Etapa 1. Por fim, verificam-se os coeficientes de combinação do polinómio de teste de baixo grau.

Etapa 7: gerar prova de inclusão do utilizador Para provar que um utilizador específico está incluído no valor total reivindicado pela exchange, fornecemos o rastreamento computado do utilizador, saldo do utilizador, ID do utilizador e um número aleatório correspondente ao índice do utilizador. Também fornecemos o caminho Merkle correspondente a esses dados.

Etapa 8: verificação do utilizador da prova de inclusão O utilizador verifica o seu saldo, ID, calcula o valor hash dos dados correspondentes ao seu índice e verifica o valor hash no nó folha da árvore Merkle usando o caminho Merkle fornecido.

2. Como realizar a autoverificação de prova de reservas (PoR)?

2.1 Verifique a restrição de inclusão do zk-STARK

Teoria da verificação

Seguindo o procedimento STARK, calcularemos a tabela de rastreamento de execução de todos os ativos do utilizador, conforme abaixo, e fazendo hash das informações de cada utilizador como uma tabela de rastreamento que se tornará uma folha da árvore Merkle e, em seguida, enviaremos as folhas para uma raiz Merkle que será publicada durante cada rodada de auditoria PoR.

Para verificar se os seus ativos estão incluídos na raiz, forneceremos o caminho Merkle para verificação. Pode primeiro calcular a sua folha fazendo o hash das suas informações de ativos e, em seguida, verificar se a sua folha é uma folha válida na árvore Merkle e na raiz que publicamos.

Por exemplo, na Figura 1, o utilizador com id id_k calculará hashk = hash("20" "15" "5" "id_k" "99821"), e os outros dados no quadro quadrado vermelho serão a verificação do caminho Merkle. Uma ferramenta de código aberto é fornecida para os utilizadores fazerem essa verificação.

Como as folhas da árvore Merkle são hashes, nenhuma das suas informações privadas será divulgada a outras pessoas.

Como verificar:

1. Para verificar se o saldo de ativos da sua conta foi incluído como uma folha zk-STARK Merkle, inicie sessão na sua conta da OKX, aceda a "Auditorias" para visualizar auditorias recentes e clique em "Detalhes" para ver os seus dados de auditoria.

2. Obtenha os dados necessários para verificação manual ao clicar em "Copiar dados".

3. Depois de clicar em "Copiar dados", abra um editor de texto (por exemplo, o bloco de notas), 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 um instantâneo do caminho Merkle e, em seguida, guarde o ficheiro numa nova pasta.

O texto JSON é mostrado abaixo:

{ "batch_inclusion_proof": { "batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed", "total_value": 138312291, "BTC": 2152907, "ETH": 909757, "USDT": 2319557, "random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac", "merkle_path": [ "5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9", "9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da", "973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2", "0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a", "2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a", "4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609", "4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374", "cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab", "ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62", "1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8", "5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933", "e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167" ] }, "trunk_inclusion_proof": { "trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290", "batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5", "total_value": 2007657936, "BTC": 18915744, "ETH": 21522734, "USDT": 21268768, "random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164", "merkle_path": [ "1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376", "a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b", "413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b", "d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b", "85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6", "d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec", "147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e", "0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4", "b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a", "ad34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2", "7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf", "239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d", “bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43” ] } }

1. Transfira a ferramenta de verificação de código aberto da OKX zk-STARKValidator

2. Guarde a ferramenta de verificação de código aberto OKX zk-STARKValidatore o ficheiro de string JSON juntos na nova pasta do Etapa 3. No nosso caso: colocamos a ferramenta assim como o ficheiro de dados na pasta "Transferências", com o nome "prova de reservas", conforme ilustrado abaixo:

1. Abra o zk-STARKValidator, que executará automaticamente o arficheiro quivo de string JSON que guardou na pasta.

2. Veja o resultado

• Se a verificação for aprovada, a frase "Inclusion constraint validation passed" será mostrada:

  

• Se a verificação falhar, a frase "Inclusion constraint validation failed" será mostrada:

  

2.2 Verifique o saldo total zk-STARK e a restrição não negativa

Como verificar:

Para verificar e provar que os ativos que afirmamos possuir são verdadeiros e que nenhum utilizador possui património líquido negativo, visite a nossa página "Ficheiros de auditoria" e transfira os ficheiros "zk-STARK" em Relatório de responsabilidade e, em seguida, guarde-os numa nova pasta.

Descomprima o ficheiro transferido e haverá uma pasta "sum proof data", que inclui milhares de pastas de filiais e uma pasta principal. Cada pasta contém dois ficheiros JSON chamados "sum_proof.json” e "sum_value.json".

Transfira a ferramenta de verificação de código aberto da OKX zk-STARKValidator

Guarde a ferramenta de verificação de código aberto OKX zk-STARKValidator e a pasta "sum proof data" juntas na pasta recém-criada do Etapa 1. No nosso caso: colocamos a ferramenta e o ficheiro de dados na pasta "Transferências", com o nome "prova de reservas", conforme ilustrado abaixo:

Abra o zk-STARKValidator, que executará automaticamente o ficheiro "sum proof data" que guardou na pasta.

Veja o resultado

Se a verificação for aprovada, a frase "Total sum and non-negative constraint validation passed" será mostrada:

Se a verificação falhar, a frase "Total sum and non-negative constraint validation failed" será mostrada: