Como projetar o circuito ZKVM

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 w_0(x), w_1(x), w_2(x), w_3(x) para as colunas w_0,w_1,w_2,w_3 então as linhas correspondentes à operação de divisão devem satisfazer:

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:

1. Não há prejuízo para o significado do polinômio seletor, ou seja, somente portas específicas podem ser utilizadas;

   
   

2. Menos polinômio seletor

Em “Plonky2: Fast Recursive Arguments with PLONK and FRI”( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ), 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.

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:

1. Não há prejuízo para o significado do polinômio seletor, ou seja, somente portas específicas podem ser utilizadas;

   
   

2. 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

1. “O livro halo2”,

   https://zcash.github.io/halo2/design/implementation/selector-combining.html

   
   

2. Polygon Zero Team, “Plonky2: Fast Recursive Arguments with PLONK and FRI”, https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf , acessado: 2022-02-06