Provas de conhecimento zero: O que são zk-STARKs e como eles 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 (argumento de conhecimento escalável e transparente com conhecimento-zero), uma tecnologia de prova de cripto baseada em ideia de Vitalik para determinar a integridade e a privacidade dos cálculos em blockchains. Neste artigo, explicamos como funciona e apresentamos o conceito matemático geral, mas se você estiver interessado em se aprofundar, comece por aqui ou aqui.

Como funciona?

Figura 1. Tabela de monitoramento de execução e árvore Merkle desenvolvida para zk-STARK PoR

Etapa 1: restrições de desenvolvimento

Para comprovar a responsabilidade de nossa exchange, manifestamos três afirmações:

Afirmação 1: Acumulamos os valores de todos os usuários corretamente, incluindo o valor de cada cripto e o valor líquido de cada usuário

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

Afirmação 3: O valor total que a exchange declara representa cada usuário, portanto, cada usuário deve ser capaz de verificar a inclusão de seu valor líquido no valor total

Para testar e verificar as afirmações acima, precisamos formular restrições como:

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

uts: tamanho do trace do usuário, que é o número de linhas de traces incluídas nos dados de cada usuário.

soma: saldo total do usuário

N: número de usuários

Afirmação 2: Restrição não negativa (Restrição de patrimônio 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 monitoramento, para confirmar e verificar os saldos totais e a não negatividade por meio de inspeções de amostragem. Veja aqui como a tabela de monitoramento é desenvolvida (para um exemplo simples, 3 usuários cujo valor máximo de usd é menor que 4^6 = 4096):

1. Inicializamos uma tabela com 32 linhas e 5 colunas, e preenchemos os valores e IDs do usuário na linha , onde k % 8 = 6, e . Cada 8 linhas formam um bloco e as informações de ativos do usuário agora estão em atrás de cada bloco. O primeiro usuário recebe saldos virtuais 0, para que possamos publicá-lo para provar que o acúmulo de valores não começa com um valor negativo.

2）Acumulamos os valores de ativos do usuário um por um e preenchemos o resultado em linhas onde k % 8 = 7, e , que são as últimas linhas de cada bloco

3）Nós continuamos dividindo o valor total de cada usuário por 4 linha por linha de atrás de cada bloco. Fazemos isso para manter o valor líquido do usuário 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) em um campo finito , que é um valor positivo muito alto.

4）Inserimos números aleatórios para cada usuário 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 monitoramento de computação de comprimento uts * N. Por motivos de segurança, realizamos o compromisso com o polinômio em um 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 compartilharã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) compartilharão no máximo pontos D. Isso significa que um polinômio falso tem uma probabilidade de de passar por uma inspeção de amostragem aleatória. Se fizermos a inspeção por amostragem n vezes, a chance diminuirá para .

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

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

Etapa 4: gerar prova de amostragem Usando a raiz de Merkle como uma fonte aleatória, amostramos os dados. Para evitar o vazamento de dados de monitoramento de computação, evitamos os dados com um índice de *k ** extensão_fator durante a amostragem e geramos o caminho de prova de 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 satisfaça as restrições relacionaadas na Etapa 1. Conforme especificado na Etapa 2, os tempos das inspeções de amostragem afetarão a probabilidade 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 na Etapa 2 de que precisamos garantir que o grau do polinômio que está sendo verificado não seja maior 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 em um polinômio e geramos uma prova de baixo grau para ele. Os coeficientes de combinação também são gerados usando a raiz de Merkle como fonte aleatória.

Por exemplo, se quisermos provar que p0(x), p1(x) e p2(x) não tem mais do que D graus, podemos gerar 2 coeficientes aleatórios da raiz de Merkle gerada na 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 que D grau, então a probabilidade de que o grau de qualquer valor entre p0(x), p1(x) e p2(x) seja maior que D será próxima de 0

Etapa 6: verificação saldo total Primeiramente, verificamos a prova de baixo grau gerada na Etapa 5.

Em seguida, uma verificação aberta adicional é realizada nos dados amostrados gerados na Etapa 4. Primeiro para verificar se os dados são consistentes com o compromisso polinomial e em seguida para verificar se os dados satisfazem as restrições desenvolvidas na 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 usuário Para provar que um usuário específico está incluído no valor total alegado pela exchange, realizamos o monitoramento computado do usuário, do saldo do usuário, da ID do usuário e um número aleatório correspondente ao índice do usuário. Também fornecemos o caminho de Merkle correspondente a esses dados.

Etapa 8: verificação do usuário da prova de inclusão O usuário verifica seu saldo, sua ID, calcula o valor hash dos dados correspondentes ao seu índice e verifica o valor hash no nó da folha da árvore Merkle usando o caminho de 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 monitoramento de execução de todos os ativos do usuário, conforme abaixo, e o hash das informações de cada usuário como uma tabela de monitoramento que se tornará uma folha da árvore de Merkle e, em seguida, enviaremos as folhas para uma raiz de Merkle que será publicada durante cada rodada de auditoria PoR.

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

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

Como as folhas da árvore de Merkle são hashes, nenhuma das suas informações privadas vazará para outras pessoas.

Como verificar:

1）Para verificar se o saldo de ativos da sua conta foi incluído como uma folha zk-STARK de Merkle, acesse sua conta na OKX, e em seguida "Auditorias" para visualizar auditorias recentes e clique em "Detalhes" para visualizar seus dados de auditoria.

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

3）Depois de clicar em "Copiar dados", abra um editor de texto (por exemplo, o bloco de notas), cole e salve a string JSON como um arquivo. O arquivo deve terminar com o nome "_inclusion_proof.json." A string JSON contém o saldo da sua conta e um snapshot do caminho Merkle e, em seguida, salve o arquivo em uma nova pasta.

O texto JSON pode ser visto 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”
]
}
}

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

5）Salve a ferramenta de verificação de código aberto OKX zk-STARKValidatore o arquivo de string JSON juntos na nova pasta da Etapa 3. No nosso caso: colocamos a ferramenta assim como o arquivo de dados na pasta "Downloads", com nome "comprovante de reservas" conforme segue:

6）Abra o zk-STARKValidator, que executará automaticamente o arquivo de string JSON que você salvou na pasta.

7. Confira 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 usuário tem patrimônio negativo, visite nossa página "Arquivos de auditoria" e baixe os arquivos "zk-STARK" em Relatório de responsabilidade, em seguida salve-os em uma nova pasta.

Descompacte o arquivo baixado e haverá uma pasta "sum proof data", que inclui milhares de pastas de filiais e uma pasta principal. Cada pasta contém dois arquivos JSON chamados "sum_proof.json" e 'sum_value.json'.

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

Salve a ferramenta de verificação de código aberto OKX zk-STARKValidator e a pasta "sum proof data" juntas na pasta recém-criada da Etapa 1. No nosso caso: colocamos a ferramenta e o arquivo de dados na pasta "Downloads", como nome "comprovante de reservas", conforme abaixo:

Abra o zk-STARKValidator, ele executará automaticamente o arquivo "sum proof data" que você salvou na pasta.

Confira 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: