portão personalizado  Ao projetar o circuito zkvm, devido a muitos portões personalizados determinados, muitos seletores binários são introduzidos.  Tomando a porta de divisão (do campo) como exemplo, planejamos projetar uma porta para verificar se a relação q = x/y funciona entre três elementos q, x, y.  Por conveniência, não realizaremos a operação de divisão de campo no nível do circuito, em vez disso, faremos isso verificando a seguinte relação lógica:   x * inv_y = q   inv_y∗y=1 //garantir y≠0  Entre os dois elementos, existe uma relação igual. Portanto, temos a seguinte tabela Trace:  Defina o polinômio   para as colunas   então as linhas correspondentes à operação de divisão devem satisfazer: w_0(x), w_1(x), w_2(x), w_3(x) w_0,w_1,w_2,w_3   w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0  Para garantir que o relacionamento acima possa ser satisfeito na linha correspondente, é necessário um seletor para fazer a divisão correspondente para restringir a verificação.  Portanto, introduzimos uma nova coluna s_{div} = {0,0,...1,...0}$. Quando for transformada para o polinômio s_{div}(x), a equação acima será:   s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0   s_{div}(x) ⋅ (w_1(x) ⋅ w_3(x) - 1) = 0   Seletor Combinado  No exemplo acima, podemos ver que quando definimos uma nova porta personalizada, uma coluna seletora s* precisa ser introduzida para corresponder à porta.  Se representarmos o polinômio de restrição correspondente da porta com t∗(x), podemos obter as seguintes restrições finalmente:   s_{adicionar}(x) ⋅ t_{adicionar}(x) = 0   s_{div}(x) ⋅ t_{adicionar}(x) = 0   s_{cubo}(x) ⋅ t_{cubo}(x) = 0   s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0   ...  Como o provador precisa realizar compromissos com todos os polinômios durante a geração da prova, muitos polinômios seletores introduzidos aumentarão a carga de trabalho do provador e do verificador.  Portanto, é necessário otimizar o número do seletor enquanto as duas condições a seguir devem ser satisfeitas:  Não há prejuízo para o significado do polinômio seletor, ou seja, somente portas específicas podem ser utilizadas;  Menos polinômio seletor  Em “Plonky2: Fast Recursive Arguments with PLONK and FRI”(   ), existe um método de otimização “Binary-Tree Based Selector” , que reduz o número do polinômio selecionado para log(k) e k é o número do portão personalizado. https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf  No documento Halo2, a equipe zcash apresentou um novo método de otimização, que pode realizar um número menor do polinômio (em correlação com o polinômio de restrição t∗(x) e os parâmetros definidos para o polinômio de restrição max_degree).  Para entender mais facilmente, vamos dar um exemplo simples (para um algoritmo específico, consulte Combinação de   ) seletores - O livro halo2  Podemos ver que definimos 4 colunas seletoras para 4 tipos de portões personalizados, que não são o que queremos, como o mencionado acima.  Portanto, isso aumentará a carga de trabalho do provador e do verificador. Aqui definimos uma nova coluna q, satisfazendo:  Se definirmos um conjunto {s_{add}, s_{div}, s_{cube}, s_{sqrt}} (chamado de disjunto, ou seja para fazer com que não haja ponto comum entre as linhas possíveis) para seletores s_{add} , s_{div}, s_{cubo}, s_{sqrt} então com base na definição da coluna q, temos:  Aqui, defina uma nova forma de polinômio seletor com base na coluna q, e para o polinômio seletor de número k, temos:  Por exemplo, para a restrição: s_add ⋅ t_add(x) = 0, pode ser reescrito como:  A fórmula acima pode ser expandida em:  Definir  Então, a figura do valor real é obtida:  Pode-se ver que ele faz a mesma coisa que o seletor original. Portanto, para restrições:   s_{adicionar}(x) ⋅ t_{adicionar}(x) = 0   s_{div}(x) ⋅ t_{adicionar}(x) = 0   s_{cubo}(x) ⋅ t_{cubo}(x) = 0   s_{sqrt}(x) ⋅ t_{sqrt}(x) = 0   ...  Podemos reescrever as restrições em:  Para as restrições acima, só precisamos realizar o compromisso com o polinômio q(x). Mas vale a pena notar que este método também aumentou o grau de restrição.  Até agora, alcançamos os dois pontos mencionados acima:  Não há prejuízo para o significado do polinômio seletor, ou seja, somente portas específicas podem ser utilizadas;  Menos polinômio seletor  Obviamente, existem limitações para o Grau restrito no protocolo, portanto, o número do seletor que participa da combinação é limitado, ou seja, o número do seletor combinado único depende do valor limite do Grau e max_degree da restrição polinomial t ∗(x).  Portanto, são necessárias mais colunas combinadas e, de qualquer forma, o número ainda é muito menor que o original.  Para mais casos de manuseio e detalhes de algoritmo, consulte   . Seletor combinando - O livro halo2  Referências  “O livro halo2”,   https://zcash.github.io/halo2/design/implementation/selector-combining.html  Polygon Zero Team, “Plonky2: Fast Recursive Arguments with PLONK and FRI”,   , acessado: 2022-02-06 https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf

Trace

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

Este áudio é produzido no idioma original da história!

Muito longo; Para ler

Como projetar o circuito ZKVM

Como projetar o circuito ZKVM

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Digital Nomads Ouçam: O que você precisa saber sobre o novo visto DTV da Tailândia

Uma breve introdução à teoria do cérebro de Boltzmann

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Navegando pelas águas: desenvolvendo aplicações RAG de nível de produção com data lakes

Digital Nomads Ouçam: O que você precisa saber sobre o novo visto DTV da Tailândia

Uma breve introdução à teoria do cérebro de Boltzmann

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps