Qu’est-ce qu’un zk-STARK et comment fonctionne-t-il ?

Qu’est-ce qu’un zk-STARK ?

Un zk-STARK est une manière cryptographique de prouver qu’un calcul est correct, sans que la personne qui vérifie la preuve doive recommencer l’intégralité du calcul. Grâce à la propriété zero-knowledge, certaines données utilisées dans le calcul peuvent en outre rester cachées.

L’acronyme signifie Zero-Knowledge Scalable Transparent ARgument of Knowledge. Cela paraît technique, mais ses éléments sont faciles à expliquer :

• Zero-Knowledge : vous pouvez prouver qu’une chose est correcte sans révéler les informations secrètes sous-jacentes.
• Scalable : même pour de grands calculs, la preuve peut être vérifiée de manière relativement efficace.
• Transparent : aucune trusted setup n’est nécessaire. Il n’est donc pas nécessaire d’organiser au préalable une configuration spéciale au cours de laquelle des informations secrètes seraient créées puis devraient être détruites de manière sécurisée.
• Argument of Knowledge : une preuve valide montre que son créateur dispose des informations nécessaires pour exécuter correctement le calcul. Il est donc extrêmement difficile de falsifier simplement une preuve valide.

Dans la crypto, cela est particulièrement utile lorsque de grands calculs sont effectués hors de la blockchain. Un système peut par exemple traiter de nombreuses transactions off-chain, puis envoyer une seule preuve à la blockchain. La blockchain n’a alors pas besoin de refaire chaque calcul, mais vérifie seulement si la preuve fournie est valide.

Exemple : supposons que des milliers de transactions soient traitées en dehors d’Ethereum. Au lieu de refaire toutes ces transactions sur Ethereum, un système peut générer un seul zk-STARK qui prouve que l’ensemble du lot a été traité conformément aux règles. Ethereum n’a ensuite plus qu’à vérifier cette preuve.

Les bases des STARKs ont été décrites en 2018 par Eli Ben-Sasson, Iddo Bentov, Yinon Horesh et Michael Riabzev. Le système a été conçu pour rendre de grands calculs vérifiables efficacement, sans trusted setup.

À retenir

• Un zk-STARK prouve qu’un calcul a été exécuté correctement sans devoir le refaire entièrement.
• Le zero knowledge peut garder l’entrée privée cachée, mais il n’est pas automatiquement présent dans chaque application STARK.
• Les STARKs n’ont pas besoin d’une trusted setup avec des paramètres secrets.
• Dans les rollups, de nombreuses transactions off-chain peuvent être vérifiées sur une blockchain avec une seule validity proof.
• Cette technique peut être utilisée à la fois pour la scalabilité de la blockchain et pour des calculs vérifiables en dehors de la crypto.

Comment fonctionne un zk-STARK ?

Un zk-STARK transforme un grand calcul en une forme beaucoup plus simple à vérifier. La partie qui exécute le calcul, le prover, produit ensuite une preuve cryptographique. Le verifier contrôle cette preuve sans devoir refaire l’intégralité du calcul d’origine.

En termes simples, le prover effectue le travail de calcul lourd et le verifier contrôle, à l’aide de plusieurs vérifications cryptographiques et mathématiques, si le résultat est correct.

En grandes lignes, cela fonctionne ainsi :

1. Le calcul est transformé en règles mathématiques: D’abord, on définit les règles auxquelles chaque étape du calcul doit se conformer. Avec les STARKs, cela se fait souvent au moyen d’une Algebraic Intermediate Representation (AIR). On peut voir cela comme une description mathématique de ce qui est autorisé ou non pendant le calcul.

2. Le prover consigne toutes les étapes de calcul: Le prover exécute le calcul et crée ce que l’on appelle une execution trace. On peut la voir comme un grand tableau qui enregistre les différentes étapes du calcul.

3. Les données sont enregistrées cryptographiquement: Le prover traite ces données mathématiquement et les fige à l’aide de cryptographic commitments, par exemple avec un Merkle tree. Le prover ne peut donc pas simplement modifier les données par la suite.

4. Le verifier contrôle un échantillon des données: Ensuite, des contrôles sont effectués à des endroits imprévisibles. Le verifier vérifie notamment si les données correspondent aux commitments enregistrés précédemment et si les règles mathématiques du calcul ont bien été respectées. Les STARKs utilisent notamment une technique appelée FRI. Elle permet de vérifier efficacement si les fonctions mathématiques utilisées ont la bonne forme, sans contrôler chaque donnée individuellement.

5. La preuve est vérifiée: Si tous les contrôles réussissent, le verifier obtient une forte certitude cryptographique que le calcul a été exécuté correctement. Il n’est pas nécessaire de refaire l’intégralité du calcul pour cela. Lorsqu’ils sont utilisés sur une blockchain, le prover peut envoyer la preuve finale à un smart contract. Ce contrat vérifie la preuve et n’accepte le nouveau résultat que si celle-ci est valide. StarkWare utilise par exemple des verifiers on-chain sur Ethereum pour contrôler les STARK-proofs.

Exemple : supposons qu’un rollup traite 1 000 transactions en dehors d’Ethereum. Le rollup exécute tous les calculs, puis produit une preuve unique qui montre que les transactions ont été traitées conformément aux règles. Ethereum n’a alors pas besoin de refaire les 1 000 transactions une par une. À la place, un smart contract vérifie la preuve. Si elle est valide, le nouvel état du rollup peut être accepté.

Cela rend les zk-STARKs particulièrement intéressants pour la scalabilité : une grande partie du travail de calcul peut avoir lieu hors de la blockchain, tandis que la blockchain peut tout de même vérifier cryptographiquement que le résultat est correct.

Que sont les zero-knowledge proofs ?

Une zero-knowledge proof permet de prouver qu’une affirmation est vraie sans révéler les informations secrètes qui se trouvent derrière cette affirmation.

En termes simples, le prover montre au verifier que quelque chose est correct, sans devoir partager toutes les données sous-jacentes.

Une zero-knowledge proof possède trois propriétés importantes :

• Completeness : si l’affirmation est vraie et que le prover exécute tout correctement, le verifier peut accepter la preuve.
• Soundness : quelqu’un qui tente de prouver une affirmation fausse n’a qu’une chance négligeable d’y parvenir.
• Zero knowledge : le verifier n’apprend aucune information secrète supplémentaire, si ce n’est que l’affirmation est vraie.

Exemple : un système peut prouver qu’un lot de transactions a été traité conformément à toutes les règles, sans rendre publiques certaines données privées issues de ces transactions.

Dans un rollup, l’affirmation publique peut par exemple être qu’un nouveau state root provient d’une suite valide de transactions. Les données qui restent cachées dépendent de la manière dont le système de preuve et l’application ont été conçus.

Point important à retenir : une validity proof n’offre pas automatiquement la confidentialité. Un système peut prouver cryptographiquement que des transactions ont été traitées correctement tout en laissant les données de transaction publiques. Pour obtenir de la confidentialité, la propriété zero-knowledge doit être intégrée volontairement dans le système.

Quel est le rôle des STARKs ?

Les STARKs sont le système de preuve qui permet de prouver et de vérifier efficacement de grands calculs sans trusted setup.

La propriété zero-knowledge détermine quelles informations peuvent rester cachées. La technique STARK permet au verifier de contrôler efficacement si le calcul a été exécuté conformément aux règles.

Une caractéristique importante des STARKs est qu’ils sont transparents. Aucune trusted setup n’est nécessaire, au cours de laquelle des paramètres cryptographiques secrets seraient créés puis devraient être détruits de manière sécurisée. À la place, le système repose notamment sur du hasard public et sur des fonctions de hachage cryptographiques.

Les STARKs utilisent également des techniques comme FRI, qui permettent de vérifier efficacement si la structure mathématique derrière la preuve est correcte.

Le terme Argument of Knowledge signifie qu’un prover ne peut pas simplement produire une preuve valide. Sous les hypothèses de sécurité du système, le prover doit disposer des informations nécessaires pour exécuter correctement le calcul.

À quoi servent les zk-STARKs ?

Les zk-STARKs sont surtout utilisés pour exécuter de grands calculs en dehors d’une blockchain, puis prouver avec une seule preuve cryptographique que le résultat est correct. Les validity rollups constituent une application importante de cette approche.

Dans un tel rollup, de nombreuses transactions sont traitées au-dessus de la couche de base. Ensuite, une preuve est envoyée à la blockchain pour montrer que le nouvel état a bien été obtenu à partir de l’ancien conformément aux règles.

C’est utile, car la couche de base n’a pas besoin de refaire tous les calculs. Le coût d’une seule preuve peut ainsi être réparti sur un grand nombre de transactions.

Un exemple connu est StarkEx. Ce système utilise des STARK-proofs pour traiter de grands volumes de transactions pour des applications telles que le trading, les paiements, le gaming et les NFT's. Les transactions sont regroupées, puis une preuve est générée et vérifiée par un smart contract sur Ethereum.

La technologie STARK peut aussi être utilisée en dehors de la crypto. En principe, cette technique convient aux situations dans lesquelles vous souhaitez prouver qu’un grand calcul a été exécuté correctement sans que le contrôleur doive refaire tous les calculs. Avec le zero knowledge, certaines données sous-jacentes peuvent également rester cachées.

Une preuve ne résout pas tout à elle seule. Dans les rollups, il reste par exemple important de savoir où les données de transaction sont disponibles. Une preuve valide prouve que le calcul respecte les règles définies, mais n’assure pas automatiquement la disponibilité de toutes les données.

Quelles blockchains utilisent les STARKs ?

L’exemple le plus connu de réseau blockchain qui utilise des STARK-proofs est Starknet. Starknet est une Layer 2 au-dessus d’Ethereum qui traite de nombreuses transactions en dehors d’Ethereum, puis envoie une STARK-proof à Ethereum.

Ethereum vérifie cette preuve pour confirmer que le nouvel état de Starknet a été calculé correctement. Ethereum n’a donc pas besoin de refaire individuellement toutes les transactions qui ont lieu sur Starknet.

StarkEx utilise également des STARK-proofs, mais StarkEx n’est pas une blockchain autonome. Il s’agit d’une solution de scaling qui permet à différentes applications crypto de traiter de grands volumes de transactions en dehors d’Ethereum, puis de prouver cryptographiquement que les calculs ont été exécutés correctement.

Ethereum n’utilise donc pas les STARKs comme mécanisme propre de consensus ou de transaction. Le réseau peut en revanche vérifier les STARK-proofs fournies par des applications et des réseaux Layer 2 comme Starknet.

Point important à retenir : l’utilisation de STARK-proofs ne signifie pas automatiquement que les transactions sont privées. Starknet utilise des STARK validity proofs pour prouver que les calculs ont été exécutés correctement, tandis que la confidentialité zero-knowledge est une propriété distincte.

Quels sont les avantages des zk-STARKs ?

Les zk-STARKs permettent de vérifier de grands calculs beaucoup plus efficacement que si chaque participant devait refaire tous les calculs.

Les principaux avantages sont :

• Aucune trusted setup : les STARKs n’ont pas besoin d’une cérémonie préalable au cours de laquelle des informations cryptographiques secrètes sont créées puis doivent être détruites de manière sécurisée.
• Vérification efficace : le verifier peut contrôler un grand calcul sans refaire chaque étape individuellement.
• Adaptés à la scalabilité : une seule preuve peut démontrer l’exécution correcte d’un grand lot de transactions, ce qui permet aux blockchains de traiter davantage de transactions hors de la couche de base.
• Possibilité de confidentialité : lorsque le zero knowledge est intégré au système, certaines données privées peuvent rester cachées tout en gardant le calcul vérifiable.
• Sécurité fondée sur le hachage : pour leur proving layer, les STARKs s’appuient sur des fonctions de hachage cryptographiques plutôt que sur des pairings sur courbes elliptiques, utilisés dans de nombreux systèmes SNARK classiques.

Grâce à cette approche fondée sur le hachage, les STARKs sont aussi souvent considérés comme mieux préparés à un avenir avec des ordinateurs quantiques puissants. En effet, les algorithmes quantiques connus posent un problème plus important pour de nombreuses constructions sur courbes elliptiques que pour des fonctions de hachage cryptographiques bien choisies.

Cela ne signifie pas que toute application utilisant des STARKs est automatiquement totalement résistante au quantique. Les fonctions de hachage utilisées, les paramètres, l’implémentation et les autres éléments cryptographiques du système restent également importants.

Quelles sont les limites des zk-STARKs ?

Les zk-STARKs ont aussi des inconvénients. En particulier, la génération d’une preuve peut demander beaucoup de puissance de calcul et de mémoire. Le travail lourd ne disparaît donc pas, mais il est surtout déplacé vers le prover.

En outre, les STARK-proofs sont généralement plus volumineuses que les proofs de nombreux systèmes zk-SNARK classiques. Cela peut signifier qu’il faut traiter davantage de données lorsqu’une preuve est vérifiée sur une blockchain.

Parmi les autres limites :

• Complexité technique : les développeurs doivent convertir correctement les calculs dans une forme qui peut être vérifiée par le système de preuve.
• Coût de génération des proofs : la création de proofs peut demander beaucoup de puissance de calcul et donc entraîner des coûts.
• La preuve ne vérifie que les règles enregistrées : si la logique de l’application contient elle-même une erreur, une preuve valide ne prouve que ces règles erronées ont été suivies correctement.
• La confidentialité n’est pas automatique : un système basé sur les STARKs peut utiliser des validity proofs sans garder les données de transaction secrètes.

En bref, une STARK-proof peut démontrer de manière très solide qu’un calcul donné a été exécuté conformément aux règles enregistrées, mais elle ne peut pas déterminer si ces règles elles-mêmes ont été bien conçues.

Quelle est la différence entre zk-STARKs et zk-SNARKs ?

Les zk-STARKs et les zk-SNARKs ont le même objectif général : prouver efficacement qu’un calcul a été exécuté correctement sans que le verifier doive refaire l’intégralité du calcul.

La principale différence réside dans la technique cryptographique utilisée pour y parvenir.

Un avantage important des zk-SNARKs est que, dans de nombreux systèmes, les preuves peuvent être très petites. Elles sont donc attrayantes lorsque la quantité de données à vérifier on-chain doit rester aussi faible que possible.

Les zk-STARKs ont généralement des preuves plus volumineuses, mais ils n’ont pas besoin de trusted setup et reposent sur d’autres hypothèses cryptographiques. Ils sont donc particulièrement intéressants pour les grands calculs et les applications où la transparence de la configuration est importante.

Il est toutefois important de ne pas mettre tous les zk-SNARKs dans le même panier. zk-SNARK est un terme générique qui désigne plusieurs systèmes de preuve. Tous les SNARKs n’utilisent pas la même cryptographie et toutes les variantes n’exigent pas le même type de trusted setup.

Pour les deux techniques, une validity proof ne signifie pas automatiquement confidentialité. Le zero knowledge doit faire partie du système de preuve spécifique et de l’application.

En résumé

Un zk-STARK est une technique cryptographique qui permet de prouver qu’un grand calcul a été exécuté correctement sans que le verifier doive refaire l’intégralité de ce calcul.

Cela rend les zk-STARKs particulièrement intéressants pour la scalabilité de la blockchain. Les rollups peuvent traiter de grands volumes de transactions hors de la couche de base, puis prouver avec une seule preuve que le résultat est correct.

Les principaux avantages sont la configuration transparente sans trusted setup et la vérification efficace de grands calculs. En contrepartie, les preuves sont plus volumineuses, la génération des preuves demande beaucoup de calcul et la technique est complexe.

Les zk-STARKs sont donc avant tout un moyen de rendre de grands calculs efficaces et vérifiables cryptographiquement. La confidentialité peut en faire partie, mais elle n’est pas automatiquement présente.