Cómo diseñar el circuito ZKVM

Puerta personalizada

Al diseñar el circuito zkvm, debido a la determinación de muchas puertas personalizadas, se introducen muchos selectores binarios.

Tomando la puerta de división (de campo) como ejemplo, planeamos diseñar una puerta para verificar que la relación q = x/y funciona entre tres elementos q, x, y.

Por conveniencia, no realizaremos la operación de división de campo a nivel de circuito, sino que la realizaremos verificando la siguiente relación lógica:

x * inv_y = q

inv_y∗y=1 //asegurar y≠0

Entre los dos elementos, existe una relación de igualdad. Por lo tanto, tenemos la siguiente tabla de Trace:

Defina el polinomio w_0(x), w_1(x), w_2(x), w_3(x) para las columnas w_0,w_1,w_2,w_3, luego las filas correspondientes a la operación de división deberán satisfacer:

w_0(x) . w_3(x) - w_2(x) = 0 w_1(x) . w_3(x) - 1 = 0

Para garantizar que la relación anterior pueda cumplirse en la fila correspondiente, se necesita un selector para realizar la división correspondiente para restringir la verificación.

Por lo tanto, hemos introducido una nueva columna s_{div} = {0,0,...1,...0}$. Cuando se transforma al polinomio s_{div}(x), la ecuación anterior 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

Selector Combinado

En el ejemplo anterior, podemos ver que cuando definimos una nueva puerta personalizada, se debe introducir una columna selectora s* para que corresponda a la puerta.

Si representamos el polinomio de restricción correspondiente de la puerta con t∗(x), podemos obtener finalmente las siguientes restricciones:

s_{añadir}(x) ⋅ t_{añadir}(x) = 0

s_{div}(x) ⋅ t_{sumar}(x) = 0

s_{cubo}(x) ⋅ t_{cubo}(x) = 0

s_{raíz cuadrada}(x) ⋅ t_{raíz cuadrada}(x) = 0

...

Dado que el probador necesita realizar compromisos con todos los polinomios durante la generación de la prueba, la introducción de demasiados polinomios selectores aumentará la carga de trabajo del probador y el verificador.

Por lo tanto, es necesario optimizar el número del selector mientras se deben cumplir las dos condiciones siguientes:

1. No hay pérdida para el significado del polinomio selector, es decir, solo se pueden usar puertas específicas;

   
   

2. Menos polinomio selector

En "Plonky2: argumentos recursivos rápidos con PLONK y FRI" ( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ), hay un método de optimización "Selector basado en árbol binario" , que reduce el número del polinomio seleccionado a log(k), y k es el número de la puerta personalizada.

En el artículo de Halo2, el equipo de zcash ha presentado un nuevo método de optimización, que puede generar un número menor del polinomio (en correlación con el polinomio de restricción t∗(x) y los parámetros establecidos para el polinomio de restricción max_degree).

Para entenderlo más fácilmente, tomemos un ejemplo simple (para un algoritmo específico, consulte Combinación de selectores: el libro de halo2 )

Podemos ver que hemos configurado 4 columnas selectoras para 4 tipos de puertas personalizadas, que no son las que queremos como las mencionadas anteriormente.

Por lo tanto, esto aumentará la carga de trabajo del probador y el verificador. Aquí definimos una nueva columna q, que satisface:

Si definimos un conjunto {s_{add}, s_{div}, s_{cube}, s_{sqrt}} (llamado disjunto, es decir, para que no haya un punto común entre posibles filas) para los selectores s_{add} , s_{div}, s_{cube}, s_{sqrt} luego, según la definición de la columna q, tenemos:

Aquí, defina una nueva forma de polinomio selector basada en la columna q, y para el polinomio selector de número k, tenemos:

Por ejemplo, para la restricción: s_add ⋅ t_add(x) = 0, puede reescribirse como:

La fórmula anterior se puede expandir a:

Establecer

Entonces, se obtiene la cifra del valor real:

Se puede ver que hace lo mismo que el selector original. Por lo tanto, para restricciones:

s_{añadir}(x) ⋅ t_{añadir}(x) = 0

s_{div}(x) ⋅ t_{sumar}(x) = 0

s_{cubo}(x) ⋅ t_{cubo}(x) = 0

s_{raíz cuadrada}(x) ⋅ t_{raíz cuadrada}(x) = 0

...

Podemos reescribir las restricciones en:

Para las restricciones anteriores, solo necesitamos realizar un compromiso con el polinomio q(x). Pero vale la pena señalar que este método también ha aumentado el grado de restricción.

Hasta ahora, hemos logrado los dos puntos mencionados anteriormente:

1. No hay pérdida para el significado del polinomio selector, es decir, solo se pueden usar puertas específicas;

   
   

2. Menos polinomio selector

Por supuesto, existen limitaciones para el Grado restringido en el protocolo, por lo que el número de selector que participa en la combinación está acotado, es decir, el número del selector combinado único depende del valor límite del Grado y max_degree del polinomio de restricción t ∗(x).

Por lo tanto, se necesitan más columnas combinadas y, de todos modos, el número sigue siendo mucho menor que el original.

Para obtener más información sobre casos de manejo y algoritmos, consulte Combinación de selectores: el libro de halo2 .

Referencias

1. “El libro de halo2”,

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

   
   

2. Equipo Polygon Zero, "Plonky2: Argumentos recursivos rápidos con PLONK y FRI", https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf , consultado: 2022-02-06