Comment concevoir le circuit ZKVM

Porte personnalisée

Lors de la conception du circuit zkvm, en raison des nombreuses portes personnalisées déterminées, de nombreux sélecteurs binaires sont introduits.

En prenant la porte de division (de champ) comme exemple, nous prévoyons de concevoir une porte pour vérifier que la relation q = x/y fonctionne entre trois éléments q, x, y.

Par commodité, nous n'effectuerons pas l'opération de division de champ au niveau du circuit, mais nous le ferons en vérifiant la relation logique suivante :

x * inv_y = q

inv_y∗y=1 //assure y≠0

Entre les deux éléments, il y a une relation égale. Par conséquent, nous avons la table Trace suivante :

Définissez le polynôme w_0(x), w_1(x), w_2(x), w_3(x) pour les colonnes w_0,w_1,w_2,w_3 puis les lignes correspondant à l'opération de division doivent satisfaire :

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

Pour s'assurer que la relation ci-dessus peut être satisfaite dans la ligne correspondante, un sélecteur est nécessaire pour effectuer la division correspondante afin de contraindre la vérification.

Par conséquent, nous avons introduit une nouvelle colonne s_{div} = {0,0,...1,...0}$. Lorsqu'elle est transformée en polynôme s_{div}(x), l'équation ci-dessus sera :

s_{div}(x) ⋅ (w_0(x) ⋅ w_3(x) - w_2(x)) = 0

s_{div}(x) ⋅ (w_1(x) ⋅ w_3(x) - 1) = 0

Sélecteur combiné

À partir de l'exemple ci-dessus, nous pouvons voir que lorsque nous définissons une nouvelle porte personnalisée, une colonne de sélection s* doit être introduite pour correspondre à la porte.

Si nous représentons le polynôme de contrainte correspondant de la porte avec t∗(x), nous pouvons finalement obtenir les contraintes suivantes :

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

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

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

s_{carré}(x) ⋅ t_{carré}(x) = 0

...

Comme le prouveur doit effectuer des engagements sur tous les polynômes lors de la génération de la preuve, trop de polynômes sélecteurs introduits augmenteront la charge de travail du prouveur et du vérificateur.

Il faut donc optimiser le nombre de sélecteurs alors que les deux conditions suivantes doivent être satisfaites :

1. Il n'y a pas de perte pour la signification du polynôme sélecteur, c'est-à-dire que seules des portes spécifiques peuvent être utilisées ;

   
   

2. Moins polynôme sélecteur

Dans "Plonky2 : Arguments récursifs rapides avec PLONK et FRI" ( https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf ), il existe une méthode d'optimisation "Binary-Tree Based Selector" , ce qui réduit le numéro du polynôme de sélection à log(k), et k est le numéro de la porte personnalisée.

Dans l'article Halo2, l'équipe zcash a proposé une nouvelle méthode d'optimisation, qui peut réaliser un plus petit nombre de polynômes (en corrélation avec le polynôme de contrainte t∗(x) et les paramètres définis pour le polynôme de contrainte max_degree).

Pour le comprendre plus facilement, prenons un exemple simple (pour un algorithme spécifique, veuillez vous référer à Selector combination - The halo2 Book )

Nous pouvons voir que nous avons défini 4 colonnes de sélection pour 4 types de portes personnalisées, qui ne sont pas ce que nous voulons, tout comme ce qui précède.

Par conséquent, cela augmentera la charge de travail du démonstrateur et du vérificateur. On définit ici une nouvelle colonne q, satisfaisant :

Si nous définissons un ensemble {s_{add}, s_{div}, s_{cube}, s_{sqrt}} (appelé disjoint, c'est-à-dire qu'il n'y a pas de point commun entre les lignes possibles) pour les sélecteurs s_{add} , s_{div}, s_{cube}, s_{sqrt} alors en se basant sur la définition de la colonne q, on a :

Ici, définissez une nouvelle forme de polynôme sélecteur basée sur la colonne q, et pour le polynôme sélecteur numéro k, nous avons :

Par exemple, pour la contrainte : s_add ⋅ t_add(x) = 0, peut être réécrit en :

La formule ci-dessus peut être étendue à :

Régler

Ensuite, le chiffre de la valeur vraie est obtenu :

On peut voir qu'il fait la même chose que le sélecteur d'origine. Donc, pour les contraintes :

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

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

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

s_{carré}(x) ⋅ t_{carré}(x) = 0

...

On peut réécrire les contraintes en :

Pour les contraintes ci-dessus, nous n'avons qu'à effectuer l'engagement sur le polynôme q(x). Mais il convient de noter que cette méthode a également augmenté le degré de contrainte.

Jusqu'à présent, nous avons atteint les deux points mentionnés ci-dessus :

1. Il n'y a pas de perte pour la signification du polynôme sélecteur, c'est-à-dire que seules des portes spécifiques peuvent être utilisées ;

   
   

2. Moins polynôme sélecteur

Bien sûr, il y a des limites au degré contraint dans le protocole, de sorte que le nombre de sélecteurs participant à la combinaison est limité, c'est-à-dire que le numéro du sélecteur combiné unique dépend de la valeur limite du degré et du degré max du polynôme de contrainte t ∗(x).

Par conséquent, plus de colonnes combinées sont nécessaires, et de toute façon, le nombre est encore beaucoup plus petit que celui d'origine.

Pour plus de cas de manipulation et de détails sur l'algorithme, veuillez vous référer à Selector combination - The halo2 Book .

Références

1. « Le livre halo2 »,

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

   
   

2. Polygon Zero Team, « Plonky2 : Arguments récursifs rapides avec PLONK et FRI », https://github.com/mir-protocol/plonky2/blob/main/plonky2/plonky2.pdf , consulté le : 2022-02-06