Cet article analyse en détail l'algorithme MSM, l'algorithme d'ajout de points de courbe elliptique, l'algorithme de multiplication de Montgomery, etc., et compare la différence de performances entre GPU et FPGA dans l'ajout de points de courbe BLS12_381.
Écrit par : Star Li
La technologie de preuve de connaissance zéro est de plus en plus largement utilisée, comme la preuve de confidentialité, la preuve de calcul, la preuve de consensus, etc. Tout en recherchant des scénarios d'application plus nombreux et meilleurs, de nombreuses personnes ont progressivement découvert que la preuve de connaissance nulle prouve que les performances sont un goulot d'étranglement. L'équipe Trapdoor Tech a effectué des recherches approfondies sur la technologie à l'épreuve de la connaissance zéro depuis 2019 et a exploré des solutions d'accélération efficaces à l'épreuve de la connaissance zéro. Les GPU ou FPGA sont des plates-formes d'accélération relativement courantes actuellement sur le marché. Cet article commence par le calcul de MSM et analyse les avantages et les inconvénients du calcul de preuve à connaissance zéro accéléré par FPGA et GPU.
TL; DR
ZKP est une technologie avec de larges perspectives d'avenir. De plus en plus d'applications adoptent une technologie sans connaissance. Cependant, il existe de nombreux algorithmes ZKP et divers projets utilisent différents algorithmes ZKP. Dans le même temps, les performances de calcul de la preuve ZKP sont relativement médiocres. Cet article analyse en détail l'algorithme MSM, l'algorithme d'ajout de points de courbe elliptique, l'algorithme de multiplication de Montgomery, etc., et compare la différence de performances entre le GPU et le FPGA dans l'ajout de points de courbe BLS12_381. En général, en termes de calcul de preuve ZKP, le GPU à court terme présente des avantages évidents, un débit élevé, des performances à coût élevé, une programmabilité, etc. Relativement parlant, le FPGA présente certains avantages en termes de consommation d'énergie. À long terme, il peut y avoir des puces FPGA adaptées aux calculs ZKP, ou des puces ASIC personnalisées pour ZKP.
Complexe d'algorithmes ZKP
ZKP est un terme général pour la technologie Zero Knowledge Proof (Zero Knowledge Proof). Il existe principalement deux classifications : zk-SNARK et zk-STARK. Les algorithmes communs actuels de zk-SNARK sont Groth16, PLONK, PLOOKUP, Marlin et Halo/Halo2. L'itération de l'algorithme zk-SNARK s'effectue principalement dans deux directions : 1/si une configuration de confiance est nécessaire 2/la performance de la structure du circuit. L'avantage de l'algorithme zk-STARK est qu'aucune configuration de confiance n'est requise, mais la quantité de calcul de vérification est log-linéaire.
En ce qui concerne l'application de l'algorithme zk-SNARK/zk-STARK, les algorithmes de preuve à connaissance nulle utilisés par différents projets sont relativement dispersés. Dans l'application de l'algorithme zk-SNARK, parce que l'algorithme PLONK/Halo2 est universel (pas besoin de configuration de confiance), il peut y avoir de plus en plus d'applications.
PLONK prouve la quantité de calcul
En prenant l'algorithme PLONK comme exemple, analysez le montant de calcul de la preuve PLONK.
Le montant de calcul de la partie preuve PLONK se compose de quatre parties :
1/ MSM - Multiplication Scalaire Multiple. MSM est souvent utilisé pour calculer des engagements polynomiaux.
2/ Calcul NTT - Conversion polynomiale entre la valeur du point et la représentation du coefficient.
3/ Calcul polynomial - addition, soustraction, multiplication et division polynomiales. Évaluation polynomiale (uation) et ainsi de suite.
4/ Circuit Synthesize - synthèse de circuit. Le calcul de cette partie est lié à l'échelle/complexité du circuit.
D'une manière générale, la quantité de calcul dans la partie Circuit Synthesize est plus logique de jugement et de boucle, et le degré de parallélisme est relativement faible, ce qui convient mieux au calcul du processeur. D'une manière générale, l'accélération sans preuve de connaissance fait généralement référence à l'accélération de calcul des trois premières parties. Parmi eux, le montant de calcul de MSM est relativement le plus important, suivi de NTT.
Qu'est-ce que les MSM ?
MSM (Multiple Scalar Multiplication) fait référence à une série donnée de points et de scalaires sur la courbe elliptique, et calcule les points correspondant aux résultats de l'addition de ces points.
Par exemple, étant donné une série de points sur une courbe elliptique :
Étant donné un ensemble fixe de points de courbe elliptique à partir d'une courbe spécifiée :
[G_1, G_2, G_3, ..., G_n]
et coefficients aléatoires :
et un élément de champ fini échantillonné au hasard à partir d'un champ scalaire spécifié :
[s_1, s_2, s_3, ..., s_n]
MSM est le calcul pour obtenir le point Q de la courbe elliptique :
Q = \somme_{i=1}^{n}s_i*G_i
L'industrie adopte généralement l'algorithme Pippenger pour optimiser le calcul MSM. Examinez de plus près le diagramme schématique du processus de l'algorithme de Pippenger :
Le processus de calcul de l'algorithme Pippenger est divisé en deux étapes :
1/ Scalaire découpé en Windows. Si Scalar est de 256 bits et qu'une fenêtre est de 8 bits, alors tous les scalaires sont divisés en 256/8 = 32 fenêtres. Chaque couche de Window utilise un "Buckets" pour stocker temporairement les résultats intermédiaires. GW_x est le résultat du point d'accumulation sur une couche. Le calcul de GW_x est également relativement simple. Il parcourt tour à tour chaque scalaire d'une couche, utilise la valeur de la couche scalaire comme indice et ajoute le G_x correspondant aux compartiments correspondants. En fait, le principe est relativement simple : si les coefficients de l'addition de deux points sont les mêmes, on additionne d'abord les deux points puis on ajoute à nouveau le Scalaire, au lieu d'additionner les deux points deux fois avant d'ajouter le Scalaire.
2/ Les points calculés par chaque fenêtre sont cumulés par double-addition pour obtenir le résultat final.
L'algorithme de Pippenger possède également de nombreux algorithmes d'optimisation de la déformation. Dans tous les cas, le calcul sous-jacent de l'algorithme MSM est l'addition de points sur la courbe elliptique. Différents algorithmes d'optimisation correspondent à différents nombres de points ajoutés.
Ajout de points de courbe elliptique (Point Add)
Vous pouvez consulter divers algorithmes d'ajout de points sur des courbes elliptiques avec la forme "Short Weierstrass" à partir de ce site.
En supposant que les coordonnées projectives des deux points sont (x1, y1, z1) et (x2, y2, z2) respectivement, le résultat de l'addition de points (x3, y3, z3) peut être calculé par la formule de calcul suivante.
La raison de donner le processus de calcul en détail est de montrer que l'ensemble du processus de calcul est principalement composé d'opérations sur des nombres entiers. La largeur en bits de l'entier dépend des paramètres de la courbe elliptique. Donnez les largeurs de bits de certaines courbes elliptiques courantes :
BN256 - 256 bits
BLS12_381 - 381bits
BLS12_377 - 377 bits
Une attention particulière est que ces opérations sur les entiers sont des opérations sur le champ modulo. L'addition modulaire/soustraction de module est relativement simple, concentrez-vous sur le principe et la mise en œuvre de la multiplication modulaire.
模乘（Muliplication modulaire）
Soit deux valeurs sur un champ modulo : x et y. Le calcul de la multiplication modulaire fait référence à x*y mod p. Notez que la largeur en bits de ces entiers est la largeur en bits de la courbe elliptique. L'algorithme classique de la multiplication modulaire est la multiplication de Montgomery (MontgomeryMulplication). Avant d'effectuer la multiplication de Montgomery, le multiplicande doit être converti en représentation de Montgomery :
La formule de calcul de la multiplication de Montgomery est la suivante :
Il existe de nombreux algorithmes d'implémentation de multiplication de Montgomery : CIOS (Coarsely Integrated Operand Scanning), FIOS (Finely Integrated Operand Scanning) et FIPS (Finely Integrated Product Scanning), etc. Cet article ne présente pas en profondeur les détails des différentes implémentations d'algorithmes, et les lecteurs intéressés peuvent faire leurs propres recherches.
Afin de comparer la différence de performances entre FPGA et GPU, choisissez la méthode d'implémentation d'algorithme la plus basique :
En termes simples, l'algorithme de multiplication modulaire peut être divisé en deux calculs : la multiplication de grands nombres et l'addition de grands nombres. Après avoir compris la logique de calcul de MSM, vous pouvez choisir les performances de la multiplication modulaire (Throughput) pour comparer les performances du FPGA et du GPU.
Observer et réfléchir
Sous une telle conception de FPGA, on peut estimer que l'ensemble du VU9P peut fournir le débit aux points de la courbe elliptique BLS12_381. Une addition ponctuelle (méthode add_mix) nécessite environ 12 multiplications modulaires. L'horloge système du FPGA est de 450M.
Sous le même algorithme de multiplication modulaire / addition de module, en utilisant le même algorithme d'addition de points, le point plus Troughput de Nvidia 3090 (en tenant compte des facteurs de transmission de données) dépasse 500 M/s. Bien sûr, l'ensemble du calcul implique une variété d'algorithmes, certains algorithmes peuvent convenir au FPGA et certains algorithmes conviennent au GPU. La raison d'utiliser la même comparaison d'algorithmes est de comparer les capacités de calcul de base du FPGA et du GPU.
Sur la base des résultats ci-dessus, résumez la comparaison entre GPU et FPGA en termes de performances de preuve ZKP :
Résumer
De plus en plus d'applications adoptent une technologie sans connaissance. Cependant, il existe de nombreux algorithmes ZKP et divers projets utilisent différents algorithmes ZKP. D'après notre expérience pratique en ingénierie, le FPGA est une option, mais le GPU est actuellement une option rentable. Le FPGA préfère l'informatique déterministe, qui présente les avantages de la latence et de la consommation d'énergie. Le GPU a une grande programmabilité, dispose d'un cadre de calcul haute performance relativement mature, et a un cycle d'itération de développement court, et préfère les scénarios de débit.
Voir l'original
Le contenu est fourni à titre de référence uniquement, il ne s'agit pas d'une sollicitation ou d'une offre. Aucun conseil en investissement, fiscalité ou juridique n'est fourni. Consultez l'Avertissement pour plus de détails sur les risques.
Un article pour comprendre les avantages et les inconvénients de l'informatique sans connaissance accélérée par FPGA et GPU
Écrit par : Star Li
La technologie de preuve de connaissance zéro est de plus en plus largement utilisée, comme la preuve de confidentialité, la preuve de calcul, la preuve de consensus, etc. Tout en recherchant des scénarios d'application plus nombreux et meilleurs, de nombreuses personnes ont progressivement découvert que la preuve de connaissance nulle prouve que les performances sont un goulot d'étranglement. L'équipe Trapdoor Tech a effectué des recherches approfondies sur la technologie à l'épreuve de la connaissance zéro depuis 2019 et a exploré des solutions d'accélération efficaces à l'épreuve de la connaissance zéro. Les GPU ou FPGA sont des plates-formes d'accélération relativement courantes actuellement sur le marché. Cet article commence par le calcul de MSM et analyse les avantages et les inconvénients du calcul de preuve à connaissance zéro accéléré par FPGA et GPU.
TL; DR
ZKP est une technologie avec de larges perspectives d'avenir. De plus en plus d'applications adoptent une technologie sans connaissance. Cependant, il existe de nombreux algorithmes ZKP et divers projets utilisent différents algorithmes ZKP. Dans le même temps, les performances de calcul de la preuve ZKP sont relativement médiocres. Cet article analyse en détail l'algorithme MSM, l'algorithme d'ajout de points de courbe elliptique, l'algorithme de multiplication de Montgomery, etc., et compare la différence de performances entre le GPU et le FPGA dans l'ajout de points de courbe BLS12_381. En général, en termes de calcul de preuve ZKP, le GPU à court terme présente des avantages évidents, un débit élevé, des performances à coût élevé, une programmabilité, etc. Relativement parlant, le FPGA présente certains avantages en termes de consommation d'énergie. À long terme, il peut y avoir des puces FPGA adaptées aux calculs ZKP, ou des puces ASIC personnalisées pour ZKP.
Complexe d'algorithmes ZKP
ZKP est un terme général pour la technologie Zero Knowledge Proof (Zero Knowledge Proof). Il existe principalement deux classifications : zk-SNARK et zk-STARK. Les algorithmes communs actuels de zk-SNARK sont Groth16, PLONK, PLOOKUP, Marlin et Halo/Halo2. L'itération de l'algorithme zk-SNARK s'effectue principalement dans deux directions : 1/si une configuration de confiance est nécessaire 2/la performance de la structure du circuit. L'avantage de l'algorithme zk-STARK est qu'aucune configuration de confiance n'est requise, mais la quantité de calcul de vérification est log-linéaire.
En ce qui concerne l'application de l'algorithme zk-SNARK/zk-STARK, les algorithmes de preuve à connaissance nulle utilisés par différents projets sont relativement dispersés. Dans l'application de l'algorithme zk-SNARK, parce que l'algorithme PLONK/Halo2 est universel (pas besoin de configuration de confiance), il peut y avoir de plus en plus d'applications.
PLONK prouve la quantité de calcul
En prenant l'algorithme PLONK comme exemple, analysez le montant de calcul de la preuve PLONK.
Le montant de calcul de la partie preuve PLONK se compose de quatre parties :
1/ MSM - Multiplication Scalaire Multiple. MSM est souvent utilisé pour calculer des engagements polynomiaux.
2/ Calcul NTT - Conversion polynomiale entre la valeur du point et la représentation du coefficient.
3/ Calcul polynomial - addition, soustraction, multiplication et division polynomiales. Évaluation polynomiale (uation) et ainsi de suite.
4/ Circuit Synthesize - synthèse de circuit. Le calcul de cette partie est lié à l'échelle/complexité du circuit.
D'une manière générale, la quantité de calcul dans la partie Circuit Synthesize est plus logique de jugement et de boucle, et le degré de parallélisme est relativement faible, ce qui convient mieux au calcul du processeur. D'une manière générale, l'accélération sans preuve de connaissance fait généralement référence à l'accélération de calcul des trois premières parties. Parmi eux, le montant de calcul de MSM est relativement le plus important, suivi de NTT.
Qu'est-ce que les MSM ?
MSM (Multiple Scalar Multiplication) fait référence à une série donnée de points et de scalaires sur la courbe elliptique, et calcule les points correspondant aux résultats de l'addition de ces points.
Par exemple, étant donné une série de points sur une courbe elliptique :
Étant donné un ensemble fixe de points de courbe elliptique à partir d'une courbe spécifiée :
[G_1, G_2, G_3, ..., G_n]
et coefficients aléatoires :
et un élément de champ fini échantillonné au hasard à partir d'un champ scalaire spécifié :
[s_1, s_2, s_3, ..., s_n]
MSM est le calcul pour obtenir le point Q de la courbe elliptique :
Q = \somme_{i=1}^{n}s_i*G_i
L'industrie adopte généralement l'algorithme Pippenger pour optimiser le calcul MSM. Examinez de plus près le diagramme schématique du processus de l'algorithme de Pippenger :
Le processus de calcul de l'algorithme Pippenger est divisé en deux étapes :
1/ Scalaire découpé en Windows. Si Scalar est de 256 bits et qu'une fenêtre est de 8 bits, alors tous les scalaires sont divisés en 256/8 = 32 fenêtres. Chaque couche de Window utilise un "Buckets" pour stocker temporairement les résultats intermédiaires. GW_x est le résultat du point d'accumulation sur une couche. Le calcul de GW_x est également relativement simple. Il parcourt tour à tour chaque scalaire d'une couche, utilise la valeur de la couche scalaire comme indice et ajoute le G_x correspondant aux compartiments correspondants. En fait, le principe est relativement simple : si les coefficients de l'addition de deux points sont les mêmes, on additionne d'abord les deux points puis on ajoute à nouveau le Scalaire, au lieu d'additionner les deux points deux fois avant d'ajouter le Scalaire.
2/ Les points calculés par chaque fenêtre sont cumulés par double-addition pour obtenir le résultat final.
L'algorithme de Pippenger possède également de nombreux algorithmes d'optimisation de la déformation. Dans tous les cas, le calcul sous-jacent de l'algorithme MSM est l'addition de points sur la courbe elliptique. Différents algorithmes d'optimisation correspondent à différents nombres de points ajoutés.
Ajout de points de courbe elliptique (Point Add)
Vous pouvez consulter divers algorithmes d'ajout de points sur des courbes elliptiques avec la forme "Short Weierstrass" à partir de ce site.
En supposant que les coordonnées projectives des deux points sont (x1, y1, z1) et (x2, y2, z2) respectivement, le résultat de l'addition de points (x3, y3, z3) peut être calculé par la formule de calcul suivante.
La raison de donner le processus de calcul en détail est de montrer que l'ensemble du processus de calcul est principalement composé d'opérations sur des nombres entiers. La largeur en bits de l'entier dépend des paramètres de la courbe elliptique. Donnez les largeurs de bits de certaines courbes elliptiques courantes :
模乘（Muliplication modulaire）
Soit deux valeurs sur un champ modulo : x et y. Le calcul de la multiplication modulaire fait référence à x*y mod p. Notez que la largeur en bits de ces entiers est la largeur en bits de la courbe elliptique. L'algorithme classique de la multiplication modulaire est la multiplication de Montgomery (MontgomeryMulplication). Avant d'effectuer la multiplication de Montgomery, le multiplicande doit être converti en représentation de Montgomery :
La formule de calcul de la multiplication de Montgomery est la suivante :
Il existe de nombreux algorithmes d'implémentation de multiplication de Montgomery : CIOS (Coarsely Integrated Operand Scanning), FIOS (Finely Integrated Operand Scanning) et FIPS (Finely Integrated Product Scanning), etc. Cet article ne présente pas en profondeur les détails des différentes implémentations d'algorithmes, et les lecteurs intéressés peuvent faire leurs propres recherches.
Afin de comparer la différence de performances entre FPGA et GPU, choisissez la méthode d'implémentation d'algorithme la plus basique :
En termes simples, l'algorithme de multiplication modulaire peut être divisé en deux calculs : la multiplication de grands nombres et l'addition de grands nombres. Après avoir compris la logique de calcul de MSM, vous pouvez choisir les performances de la multiplication modulaire (Throughput) pour comparer les performances du FPGA et du GPU.
Observer et réfléchir
Sous une telle conception de FPGA, on peut estimer que l'ensemble du VU9P peut fournir le débit aux points de la courbe elliptique BLS12_381. Une addition ponctuelle (méthode add_mix) nécessite environ 12 multiplications modulaires. L'horloge système du FPGA est de 450M.
Sous le même algorithme de multiplication modulaire / addition de module, en utilisant le même algorithme d'addition de points, le point plus Troughput de Nvidia 3090 (en tenant compte des facteurs de transmission de données) dépasse 500 M/s. Bien sûr, l'ensemble du calcul implique une variété d'algorithmes, certains algorithmes peuvent convenir au FPGA et certains algorithmes conviennent au GPU. La raison d'utiliser la même comparaison d'algorithmes est de comparer les capacités de calcul de base du FPGA et du GPU.
Sur la base des résultats ci-dessus, résumez la comparaison entre GPU et FPGA en termes de performances de preuve ZKP :
Résumer
De plus en plus d'applications adoptent une technologie sans connaissance. Cependant, il existe de nombreux algorithmes ZKP et divers projets utilisent différents algorithmes ZKP. D'après notre expérience pratique en ingénierie, le FPGA est une option, mais le GPU est actuellement une option rentable. Le FPGA préfère l'informatique déterministe, qui présente les avantages de la latence et de la consommation d'énergie. Le GPU a une grande programmabilité, dispose d'un cadre de calcul haute performance relativement mature, et a un cycle d'itération de développement court, et préfère les scénarios de débit.