STARK-Friendly Hash
0x568B
June 7th, 2022

Initialement publié en anglais part StarkWare le 15 août, 2019

Il est temps de tester la marchandise

Déroulement du Grant de la Ethereum Fondation

L'été dernier, la Ethereum Fondation (EF) a accordé à StarkWare un grant (une subvention) de recherche pour proposer un Hash compatible avec le système STARK (STARK-Friendly Hash)(SFH), puis publier un logiciel efficace et de qualité pour un système STARK pour le SFH (sous une licence approuvée par l'EF) à l'usage de l'écosystème des développeurs Ethereum. L'EF a fixé une barre élevée pour l'efficacité, bien au-delà de ce qui est réalisable par libSTARK (et libSNARK et BulletProofs) : un prouver doit générer des preuves STARKs pour de nombreuses invocations répétées d'une fonction de hachage et le taux de création de preuves (ne pas confondre avec le hash-rate - taux de hashage) doit être d'au moins 100 hashes/seconde, mesuré sur une machine à quatre cœurs avec 16 Go de RAM.
En outre, la preuve STARK pour 100 000 hashes doit être vérifiable en 10 ms sur un seul cœur et sa taille doit être inférieure à 200 Ko.

Les fonctions de hachage standard comme SHA2, SHA3 et Blake et les ciphers symétriques standard comme AES constituent la référence en matière de sécurité. Cependant, ces fonctions ont été sélectionnées pour optimiser un ensemble de contraintes liées au matériel et à la consommation électrique. Les implémentations de systèmes ZKP n'existaient pas à l'époque et la "convivialité STARK" n'était donc pas une priorité.

Cela doit changer. La scalabilité (et la confidentialité) des blockchains nécessite des systèmes de preuve succincts capables de prouver des affirmations sur des données hachées (et cryptées). Souvent, les parties les plus lourdes de la construction de la preuve sont dues à des primitives cryptographiques. C'est par exemple le cas du Zcash Sapling ZK-SNARK qui protège les paiements : la plupart du temps de preuve (et de la complexité) provient de la preuve des déclarations sur les invocations des fonctions de hachage Pedersen et Blake2b. (Les objectifs fixés par l'EF pour StarkWare sont ceux de la scalabilité, et non de la confidentialité, mais avoir des fonctions de hachage prouvables efficacement est important dans les deux cas).

Notre projet a débuté avec un objectif plutôt simple : StarkWare devait collecter et étudier les fonctions de hachage existantes avec des paramètres de sécurité bien établis, et sélectionner les plus conviviales d'entre elles. Cependant, nous avons rapidement réalisé qu'il existait une meilleure façon, plus ambitieuse, de servir la communauté Ethereum, qui pourrait également profiter à d'autres projets dans cet espace : solliciter de nouvelles fonctions de hachage optimisées pour la convivialité de STARK. (Bien que les fonctions de hachage adaptées à SNARK et BulletProof ne fassent pas partie des objectifs de ce projet, certaines des propositions favorables aux STARKs peuvent également être favorables à ces systèmes ZKP).

Nous avons contacté deux équipes universitaires externes de cryptographes et financé leurs recherches qui ont abouti à deux paires de constructions : la Vision/Rescuepair et la Starkad/Poseidon pair. Ces constructions sont présentées par paires : un type fonctionne sur des champs binaires et l'autre sur des champs premiers. En même temps, nous avons appris l'existence d'un troisième travail de recherche, appelé GMiMC, qui n'a pas été sollicité, ni financé, par StarkWare. Chacun de ces trois groupes est basé sur des principes de conception différents. À ces constructions, il convient d'ajouter la plus ancienne des constructions "finite-field friendly" - MiMC. C'est notre liste actuelle de prétendants au titre de fonction de hachage compatible avec STARK (SFH) (nous sommes toujours à la recherche de nouvelles fonctions). Nous avons déjà sollicité une évaluation par des experts de la sécurité algébrique de ces candidats, mais c'est loin d'être suffisant. Nous invitons donc maintenant le public à tester ces candidats par le biais d'un ensemble public d'énigmes, récompensées par de l'Ether et distribuées par des smart contracts. Les détails dans la suite.

Collision challenges - Gagnez de l'Éther !

Le Dr Tomer Ashur a accepté d'organiser le challenge SFH pour le compte de StarkWare. Il a consulté les différentes équipes qui ont construit les candidats et a conçu un ensemble d'énigmes, chacune demandant de trouver une collision dans une version de l'un des candidats SFH (une collision est une paire d'entrées distinctes qui ont exactement le même hachage). Il existe quatre gammes de paramètres : sécurité faible (devrait être cassé avec environ 2⁴⁵ tentatives), sécurité moyenne (cassable en environ 2⁸⁰ tentatives), sécurité cible (cassable en environ 2¹²⁸ étapes) et sécurité élevée (environ 2²⁵⁶ étapes à casser).

La cagnotte s'élève à plus de 200 ETH (>40 000 $ à l'heure où nous écrivons ces lignes) - c'est une somme importante, mais le coût de rupture du SFH une fois qu'il sera déployé et utilisé massivement pourrait être plusieurs fois supérieur. Le premier à résoudre chaque puzzle sera récompensé en fonction du niveau de sécurité du puzzle : 1, 2, 4 ou 8 ETH pour chaque puzzle résolu. Nous prévoyons actuellement de mener ce défi jusqu'à la fin du mois de mars 2020, mais nous pourrions le prolonger et/ou modifier certaines des énigmes par la suite.

Remarque : En dehors de ce défi, StarkWare ne donne PAS d'ETH et n'organise pas d'ICO. Méfiez-vous des scammers !

Pour les énigmes qui sont définies sur des champs primaires, nous déployons des smart contracts sur Ethereum qui attribueront automatiquement le prix au premier solveur. Vous pouvez également nous envoyer la solution directement off-chain, nous collecterons le prix en ETH et vous l'enverrons - mais veuillez noter que nous n'accepterons les solutions qu'à partir de la date de mise en service des smart contracts. Pour les champs binaires, off-chain est le seul moyen de collecter le prix (la VM d'Ethereum ne supporte pas naturellement la multiplication des champs binaires). Des prix supplémentaires peuvent être distribués à notre discrétion pour de belles attaques et des informations sur celles-ci.

Prochaine étape - Le comité de sélection des SFH

En novembre 2019, nous réunirons un petit comité d'experts universitaires de premier plan dans le domaine de la construction et de l'analyse des primitives cryptographiques symétriques. Cet estimable comité passera plusieurs jours à examiner toutes les données disponibles à ce moment-là concernant les candidats SFH - y compris ce qui ressortira du challenge SFH - et recommandera ceux qui sont les plus sûrs à utiliser. Le rapport de ce comité devrait être publié au début de l'année 2020.

Avec cette recommandation en main, StarkWare va commencer à écrire le code du vérifieur et du prouveur (prover and verifier), puis se soumettre à un certain nombre d'audits de code par des parties externes avant de livrer le code à la Fondation Ethereum qui le partagera avec sa communauté de développeurs.

Nous avons un calendrier très serré, le défi qui nous attend est considérable et nous sommes conscients de l'enjeu. Nous ferons de notre mieux pour répondre aux attentes de la communauté des développeurs Ethereum. Nous demandons votre aide : s'il vous plaît, faites un tour et gagnez de l’ETH. Détails et spécifications ici.

Eli Ben-Sasson

StarkWare

Traduction faite par HoVa.

Arweave TX
XC062YoyQF-8SU4dghlLFeD6k6lnf4cjq-nYqASFJl8
Ethereum Address
0x568B12eBBE85521D2cd8a2C9B7a8EF3f48aa2d66
Content Digest
TaAUNyTug-Oink57FVXq9YkxeCBwV9ynM600M9wMk00