Preuves Zero-Knowledge : que sont les zk-STARK et comment fonctionnent-ils ?

1. Qu’est-ce que c’est?

Le système zk-STARK Proof of Reserves (PoR) s’appuie sur la théorie STARK, une solution mathématique complexe. zk-STARK signifie : Zero-Knowledge Scalable Transparent Argument of Knowledge, une technologie de preuve cryptographique basée sur une idée de Vitalik pour faire respecter l’intégrité et la confidentialité des calculs sur les blockchains. Dans cet article, nous allons présenter son fonctionnement et expliquer le concept mathématique général, mais si vous souhaitez vous y intéresser plus en détail, commencez par cet article ou celui-ci.

Comment ça marche?

Figure 1. Tableau de trace d’exécution et arbre de Merkle construits pour zk-STARK PoR

Étape 1 : contraintes de construction

Afin de prouver la responsabilité de notre plateforme d’échange, nous énonçons trois affirmations :

Affirmation 1 : Nous avons rassemblé correctement les valeurs de chaque utilisateur, y compris la valeur de chaque crypto et la valeur nette de chaque utilisateur

Affirmation 2 : La plateforme d’échange n’a pas créé d’utilisateur virtuel dont la valeur nette est négative pour réduire la responsabilité totale de la plateforme d’échange (un utilisateur individuel ayant des soldes négatifs n’est acceptable que si sa valeur nette est supérieure à 0)

Affirmation 3 : La valeur totale indiquée par la plateforme d’échange comptabilise chaque utilisateur, de sorte que chaque utilisateur doit être en mesure de vérifier l’inclusion de sa valeur nette dans la valeur totale

Pour tester et vérifier les affirmations ci-dessus, nous devons créer des contraintes telles que :

Affirmation 1 : Contrainte de solde total (Contrainte de solde total correct)

uts : taille de la trace utilisateur, qui correspond au nombre de lignes de traces incluses dans les données de chaque utilisateur.

sum : solde total de l’utilisateur

N : nombre d’utilisateurs

Affirmation 2 : Contrainte non négative (Contrainte de fonds propres positifs)

Affirmation 3 : Contrainte d’inclusion (Contrainte d’inclusion de tous les soldes des comptes clients)

Selon les contraintes ci-dessus, nous créons un tableau de traçabilité, pour valider et vérifier les soldes totaux et non négatifs par des contrôles par échantillonnage. Voici comment la table de suivi est construite (exemple simple : 3 utilisateurs dont la valeur maximale en USD est inférieure à 4^6 = 4096) :

1）Nous initialisons une table avec 32 lignes et 5 colonnes, et nous remplissons les valeurs et les identifiants de l’utilisateur dans ligne, où k % 8 = 6, et . Chaque 8 lignes représente un bloc, et les informations sur les actifs de l’utilisateur sont maintenant dans  depuis l’arrière de chaque bloc. Le premier utilisateur reçoit des soldes virtuels à 0. Nous pouvons donc le publier pour prouver que l’ajout de valeurs ne commence pas par une valeur négative.

2）Nous ajoutons les valeurs des actifs utilisateur une par une et indiquons le résultat dans lignes où k % 8 = 7, et , qui sont les dernières lignes de chaque bloc

3. Nous continuons à diviser la valeur totale de chaque utilisateur par 4 ligne par ligne à partir de depuis l’arrière de chaque bloc. Il s’agit de faire en sorte que la valeur nette de l’utilisateur ne soit pas négative, en vérifiant si les premières lignes sont nulles pour chaque bloc. Si quelqu’un a une valeur nette négative, la première ligne de son bloc ne sera pas nulle car une valeur négative (-x) se révélera être (p - x) dans un champ fini , donc une très grande valeur positive.

4）Nous indiquons des nombres aléatoires pour chaque utilisateur et remplissons les espaces vides du tableau avec 0

Étape 2 : extension polynomiale de bas degré En utilisant les contraintes polynomiales ci-dessus, nous pouvons obtenir un polynôme de trace de calcul de longueur uts * N. Pour des raisons de sécurité, nous effectuons l’engagement du polynôme sur un domaine d’évaluation plus large, avec le facteur d’amplification du domaine comme extension_factor.

Dans le cas ci-dessus, nous pourrions calculer un polynôme p(x) à partir de I(x). Lorsque nous utilisons une extension_factor de 8, nous calculerons encore 32(8-1)* points sur p(x).

Étant donné que deux polynômes différents de degré D partageront au plus D points, un exemple de paire de polynômes avec un polynôme valide (qui satisfait aux contraintes ci-dessus) et un faux polynôme de degré D (qui ne satisfait pas les contraintes ci-dessus) partageront au plus D points. Cela signifie qu’un faux polynôme a une chance de  de réussir une inspection par échantillonnage aléatoire. Si nous effectuons l’inspection par échantillonnage n fois, la probabilité diminuera à .

Nous implémentons l’extension_factor par défaut à 16 et le temps d’inspection par défaut à 16, de sorte que le niveau de sécurité sera de 80 bits.

Étape 3 : engagement polynomial Nous calculons la valeur de hachage de la trace de calcul et le solde utilisateur correspondant, l’ID d’utilisateur et la valeur du polynôme de contrainte correspondant pour chaque ligne, et générons un arbre de Merkle. La racine de Merkle est la valeur d’engagement du polynôme.

Étape 4 : génération d’une preuve d’échantillonnage En utilisant la racine de Merkle comme source aléatoire, nous échantillonnons les données. Pour éviter les fuites de données de trace de calcul, nous évitons les données avec un index de *k ** extension_factor lors de l’échantillonnage et générons le chemin de preuve de Merkle correspondant à l’indice d’échantillonnage.

Nous effectuons les inspections par échantillonnage pour vérifier si le polynôme engagé est un polynôme valide satisfaisant aux contraintes énumérées à l’étape 1. Comme spécifié à l’étape 2, les heures des inspections d’échantillonnage auront une incidence sur les chances de réussite de la falsification ou de la manipulation.

Étape 5 : génération d’une preuve de faible degré

Nous pouvons contrôler la probabilité de réussite de l’altération ou de la manipulation grâce à une inspection par échantillonnage. Cependant, comme mentionné à l’étape 2, dans une certaine condition nous devons nous assurer que le degré du polynôme vérifié n’est pas supérieur au degré d’un polynôme valide. Pour améliorer l’efficacité de la preuve, nous combinons linéairement tous les polynômes de contrainte en un seul polynôme et générons une preuve de faible degré pour celui-ci. Les coefficients de combinaison sont également générés en utilisant la racine de Merkle comme source aléatoire.

Par exemple, si nous voulons prouver que p0(x), p1(x) et p2(x) ne sont pas supérieurs à D degrés, nous pouvons générer 2 coefficients aléatoires à partir de la racine de Merkle générée à l’étape 3 et calculer le polynôme linéaire l(x) comme suit :

k0 = hash(root + "0")
k1 = hash(root + "1")
l(x) = k0 * p0(x) + k1 * p1(x) + p2(x)

S’il est possible de prouver que l(x) n’est pas supérieur à D degré, alors la probabilité que le degré de p0(x), p1(x) et p2(x) au choix soit supérieur à D sera proche de 0.

Étape 6 : vérification du solde total Tout d’abord, nous vérifions la preuve de faible degré générée à l’étape 5.

Ensuite, une autre vérification ouverte est effectuée sur les données échantillonnées générées à l’étape 4. Il s’agit premièrement de vérifier que les données sont cohérentes avec l’engagement polynomial, et deuxièmement, que les données satisfont les contraintes construites à l’étape 1. Enfin, les coefficients de combinaison du polynôme de test de faible degré sont vérifiés.

Étape 7 : générer une preuve d’inclusion d’utilisateur Pour prouver qu’un utilisateur spécifique est inclus dans le montant total indiqué par la plateforme d’échange, nous fournissons la trace calculée de l’utilisateur, le solde de l’utilisateur, l’identifiant de l’utilisateur et un nombre aléatoire correspondant à l’index de l’utilisateur. Nous fournissons également le chemin de Merkle correspondant à ces données.

Étape 8 : vérification par l’utilisateur de la preuve d’inclusion L’utilisateur vérifie son solde, son ID, calcule la valeur de hachage des données correspondant à son index et vérifie la valeur de hachage sur le nœud feuille de l’arbre de Merkle à l’aide du chemin de Merkle fourni.

2. Comment effectuer une auto-vérification de la Preuve de réserves (PoR) ?

2.1 Vérifier la contrainte d’inclusion zk-STARK

Théorie de vérification

En suivant la procédure STARK, nous calculerons la table de trace d’exécution de tous les actifs utilisateur comme ci-dessous. Nous hacherons les informations de chaque utilisateur sous forme de table de trace, laquelle deviendra une feuille d’arbre de Merkle, puis engagerons les feuilles dans une racine de Merkle qui sera publiée lors de chaque cycle d’audit PoR.

Pour vérifier si vos actifs sont inclus dans la racine, nous vous fournirons le chemin de Merkle pour vérification. Vous pouvez d’abord calculer votre feuille en hachant vos informations d’actif, puis vérifier si votre feuille est une feuille valide dans l’arbre de Merkle et la racine que nous publions.

Par exemple, dans la figure 1, l’utilisateur avec un identifiant id_k calculera hashk = hash("20" "15" "5" "id_k" "99821"), et les autres données figurant dans le cadre rouge correspondront à la vérification du chemin Merkle. Un outil open source est fourni aux utilisateurs pour effectuer cette vérification.

Étant donné que les feuilles de l’arbre Merkle sont des hachages, vos informations personnelles ne seront pas divulguées à des tiers.

Pour procéder à la vérification :

1）Pour vérifier si le solde d’actifs de votre compte a été inclus sous forme de feuille de zk-STARK Merkle, connectez-vous à votre compte OKX, cliquez sur « Actifs » et rendez-vous dans « Audits » consulter les derniers audits. Cliquez sur « Détails » pour afficher vos données d’audit.

2）Pour obtenir les données nécessaires à une vérification manuelle, cliquez sur « Copier les données ».

3）Après avoir cliqué sur ce bouton, ouvrez un éditeur de texte (le bloc-notes, par exemple), puis collez-y et enregistrez la chaîne JSON sous forme de fichier. Le fichier doit se terminer par le nom « _inclusion_preuve.json ». La chaîne JSON contient le solde de votre compte et un instantané du chemin de Merkle, puis enregistre le fichier dans un nouveau dossier.

Le texte JSON se présente ainsi :

{
"batch_inclusion_proof": {
"batch_mtree_root": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"user_id": "47db1d296a7c146eab653591583a9a4873c626d8de47ae11393edd153e40f1ed",
"total_value": 138312291,
"BTC": 2152907,
"ETH": 909757,
"USDT": 2319557,
"random_number": "e7b7a5a6fdba87a58559aed4fca66fb63d3d9395ce0d51bda40fcd35893391ac",
"merkle_path": [
"5e3dd0ad776b15743076405d53e12af8fdac85c446bcc6c2eb8cab0e0e0c24f9",
"9dd5fcb0f3835b10772a7baabe7a074ed0b6947f7284e2d7ce5a84c3b5b394da",
"973186c5ea69bdc06c0c786cfae76173a89e0989bd759e1b2c37fdd317c70fe2",
"0c7ea3dd9bc0a15019b9ace6cf003befa31133ee84728d21bf67aa984ef1b60a",
"2adf4a58ccec7a44ed3a3f8bd365c61eac7d25c55524e69a31c6665769b7962a",
"4cddf667adbfa51e1b999e39a2009dcc9786385d9f3e240919f763e4db6f3609",
"4e841f9b5c2641759572fdfaf66c518b191e89b7a4745f179c046fef1eb9c374",
"cc12d77e7d13ee3c57064697dfef230064efaaf5b6ccf22a5ef5b7a2602632ab",
"ead6745e91b88021aeecddd8d014ea26ba26f42c4d5286ef8e196085d3757f62",
"1a583279e243ddc0a36bf870b5af70f2e52f059faeb5f3757d0d1903770371e8",
"5c1729384a2f2c8c434f3b34e99d6152aab42093c4f68aab638eaa212e799933",
"e154c1011883b2cea377c6bc820a21ac01d9d792ce3e1f376f35c1b29df04167"
]
},
"trunk_inclusion_proof": {
"trunk_mtree_root": "9b61d44f4f3de6b284d95a844dee9327d5e2091ac7e6b6f67ca10bd866617290",
"batch_id": "34d4e17e0071f180736bae075f632845ded76262d19970c47cabb8d88046e9c5",
"total_value": 2007657936,
"BTC": 18915744,
"ETH": 21522734,
"USDT": 21268768,
"random_number": "c93d3517d691564f3cc8e1eee6634ba7e0f59125aa89cd6984677459ac5f8164",
"merkle_path": [
"1082ec62ad0bd2b2b2c38a08f4b0de2f9aa77b387c611b927d203deb9bc97376",
"a57a391c137877993cd61ca4ad57bb1754bf8776fd207e630c362b8560fbb34b",
"413cba43d7f7236b5ce21fe951583660277507250ecbabca6a1ac6e9ac66bb5b",
"d87e2c64c34700195e322967ebbbb282810671320d083029fb9e46f92474d47b",
"85438a308f8d668779dbdb462437434f8f9d551229e8ebb2235605fe18cf97f6",
"d1cbf91c33b4cb0366877c4c805548401887f2a428c7297d0c4d97fa0f936cec",
"147fccf20ff7010d2ba162333f62200dce116d337230ee73f7c8bc2abcba148e",
"0901034401e6b6fa7de911d658ebc9b10c6a64c16a5450a22e390859ae87e1c4",
"b2e3525d853749ca2edfa718cd4f12ba26a0f645dfb0d5512d42c67fc74d0a1a",
"annonce34d5acf98f7e6234d132d578f823e7bd8410d1850db76a55dd794ce388b2c2",
"7e81326a45550eea02398a8459dbd5d73d6d90b58268ce4453231cf3077f4fdf",
"239263d4cf31258c7910fe7abe8cc23d1b71cf73e796a958e60d3fafe095e49d",
"bb44ebaed47333c967f79c48cb3e0106fe64f55411f94181daa4c55f2a563e43"
]
}
}

4）Téléchargez l’outil de vérification open source d’OKX zk-STARKValidator

5）Placez l’outil de vérification open source d’OKX zk-STARKValidatoret le fichier de chaîne JSON ensemble dans le nouveau dossier de l’étape 3. Dans notre cas : nous mettons l’outil ainsi que le fichier de données dans le dossier « Téléchargements », nommé « proof-of-reserves » ci-dessous :

6. Ouvrez le zk-STARKValidator, il exécutera automatiquement le fichier de chaîne JSON que vous avez enregistré dans le dossier.

7）Vérifiez le résultat

• Si la vérification réussit, le résultat « Inclusion constraint validation passed » s’affichera :

  

• En cas d’échec de la vérification, vous verrez s’afficher le message « Inclusion constraint validation failed » :

  

2.2 Vérifier le solde total zk-STARK et la contrainte non négative

Pour procéder à la vérification :

Pour vérifier et prouver que les actifs que nous prétendons détenir sont réels et qu’aucun utilisateur ne détient de fonds propres négatifs, consultez notre page des « Fichiers d’audit », et téléchargez les fichiers « zk-STARK » sous Rapport de responsabilité, puis enregistrez-les dans un nouveau dossier.

Décompressez le fichier téléchargé. Vous y trouverez un dossier « sum proof data », qui contient des milliers de sous-dossiers et un dossier principal. Chaque dossier contient deux fichiers JSON nommés « sum_proof.json » et « sum_value.json ».

Téléchargez l’outil de vérification open source d’OKX zk-STARKValidator

Placez l’outil de vérification open source d’OKX zk-STARKValidator et le dossier « sum proof data » ensemble dans le dossier nouvellement créé à l’étape 1. Dans notre cas : nous mettons l’outil ainsi que le fichier de données dans le dossier « Téléchargements », nommé « proof-of-reserves » ci-dessous :

Ouvrez le zk-STARKValidator, il exécutera automatiquement « sum proof data » que vous avez enregistré dans le dossier.

Vérifier le résultat

Si la vérification réussit, le résultat « Total sum and non-negative constraint validation passed » s’affichera :

En cas d’échec de la vérification, vous verrez s’afficher le message « Total sum and non-negative constraint validation failed » :