💻 computer science

PoSME: Proof of Sequential Memory Execution via Latency-Bound Pointer Chasing with Causal Hash Binding

Le papier présente PoSME, une primitive cryptographique qui impose une exécution séquentielle stricte via un parcours de pointeurs lié à la latence mémoire, rendant les attaques ASIC inefficaces et offrant une résistance supérieure aux compromis temps-mémoire pour des applications comme la preuve de délai vérifiable et la résistance aux Sybils.

Auteurs originaux : David L. Condrey

Publié 2026-04-20

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : David L. Condrey

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🌟 Le Concept : La "Course de Relais dans un Labyrinthe Vivant"

Imaginez que vous voulez prouver à quelqu'un que vous avez passé un certain temps à faire un travail difficile, sans qu'ils aient besoin de vous surveiller en permanence.

Jusqu'à présent, les systèmes informatiques utilisaient deux méthodes principales :

La méthode "Calcul pur" (comme un VDF) : C'est comme faire des additions très vite. Si vous avez un super-calculateur (un ASIC), vous pouvez aller 100 fois plus vite que moi.
La méthode "Mémoire statique" (comme PoSW) : C'est comme chercher des objets dans une bibliothèque où les livres ne bougent jamais. Si vous avez un robot rapide, il trouve les livres plus vite que moi.

PoSME (Proof of Sequential Memory Execution) change les règles du jeu. Il ne s'agit plus de calculer vite, ni de chercher dans un livre fixe. C'est une course de relais dans un labyrinthe qui change à chaque seconde.

🏃‍♂️ Comment ça marche ? (L'Analogie du Labyrinthe)

Imaginez un immense terrain de jeu (le "Labyrinthe") rempli de millions de boîtes. Voici les règles du jeu PoSME :

Le Labyrinthe est Vivant (Mémoire Mutable) :
Contrairement à une bibliothèque où les livres restent à leur place, ici, chaque fois que vous ouvrez une boîte pour lire son contenu, vous devez écrire un nouveau message dedans qui change tout ce qui s'y trouvait avant. Le terrain se réécrit lui-même en temps réel.
La Boussole Magique (Pointeur Dépendant des Données) :
Pour savoir quelle est la prochaine boîte à ouvrir, vous ne pouvez pas regarder une carte fixe. Vous devez regarder le contenu de la boîte actuelle.
- Exemple : Si la boîte actuelle contient "Gauche", la prochaine est à gauche. Si elle contient "Droite", la prochaine est à droite.
- Le piège : Comme le contenu de la boîte change à chaque fois que vous y touchez, vous ne pouvez pas prédire la prochaine étape. Vous êtes obligé de faire les étapes une par une, dans l'ordre. Impossible de sauter des étapes ou de faire plusieurs choses en même temps.
Le Lien Indissociable (L'Encre Symbiotique) :
Chaque fois que vous écrivez un nouveau message dans une boîte, vous y collez une "empreinte digitale" (un hachage) qui prouve que ce message a été écrit après les messages précédents.
- Si quelqu'un essaie de tricher en fabriquant une boîte fausse, il doit aussi recréer toute l'histoire de toutes les boîtes qui ont mené à celle-ci. C'est comme essayer de falsifier un journal intime : si vous changez une page, vous devez réécrire tout le livre depuis le début.

🚫 Pourquoi les Super-ordinateurs (ASIC/GPU) échouent ?

C'est la partie la plus brillante du système.

Le problème des Super-calculateurs : Les GPU et les ASIC sont comme des armées de robots ultra-rapides capables de faire des millions de calculs à la seconde. Mais ils sont très maladroits pour aller chercher des objets un par un dans des endroits éloignés.
Le goulot d'étranglement : Dans PoSME, le temps perdu n'est pas à faire le calcul (qui est rapide), mais à courir chercher la prochaine boîte dans la mémoire (la RAM).
- Imaginez un coureur de 100 mètres (le calcul) qui est très rapide, mais qui doit s'arrêter à chaque fois pour aller chercher une balle dans un champ à 50 mètres de distance (la latence de la mémoire).
- Même si vous avez 100 robots (GPU), ils doivent tous attendre leur tour pour aller chercher la balle. Ils ne peuvent pas courir plus vite que la vitesse de la lumière dans les câbles de la mémoire.

Résultat : Un simple ordinateur portable de bureau (un CPU) est souvent plus rapide que des super-ordinateurs coûteux pour ce jeu précis, car il est mieux adapté pour cette course de relais lente et séquentielle.

💡 Les Trois Grands Avantages

Impossibilité de tricher avec la mémoire : Si vous voulez tricher en ne stockant pas toutes les boîtes (pour économiser de l'espace), vous devrez recalculer tout le chemin à chaque fois. Cela prendrait 10 fois plus de temps que de jouer honnêtement.
Pas de triche avec la puissance brute : Avoir un super-calculateur ne vous aide pas, car le jeu est limité par la vitesse de la mémoire, pas par la vitesse du processeur.
Preuve de temps réel : Puisqu'on ne peut pas accélérer le processus, si vous avez fini le jeu, cela prouve que vous avez passé le temps nécessaire à le faire. C'est une preuve incontestable que "le temps s'est écoulé".

🎯 À quoi ça sert dans la vraie vie ?

Cryptomonnaies équitables : Cela permet de miner des cryptos sans que les riches puissent acheter des machines spéciales pour écraser tout le monde. Tout le monde a une chance égale.
Preuve d'authenticité : Cela permet de prouver qu'un texte ou une œuvre a été écrit par une personne qui a passé du temps dessus, et non généré instantanément par une IA.
Sécurité contre les faux comptes : Cela empêche les pirates de créer des milliers de faux comptes (Sybil) en un clin d'œil, car chaque compte demande du temps réel pour être créé.

En résumé

PoSME est comme un jeu de mémoire géant et dynamique où la seule façon de gagner est de jouer honnêtement, étape par étape, sans pouvoir tricher avec la vitesse ou la mémoire. C'est une innovation qui rend le monde numérique plus équitable en reliant la sécurité informatique à la physique réelle de la mémoire des ordinateurs.

1. Problématique et Contexte

Le papier identifie un vide dans les primitives cryptographiques existantes pour prouver qu'une partie a effectué un calcul séquentiel soutenu sous des contraintes de ressources réelles. Les solutions actuelles présentent des lacunes majeures :

VDF (Verifiable Delay Functions) : Garantissent le temps séquentiel mais sont insensibles à la mémoire. Les ASICs peuvent les accélérer arbitrairement via des unités de calcul (ALU) plus rapides.
PoSW (Proofs of Sequential Work) : Prouvent la traversée de graphes mais sur une mémoire statique et immuable, permettant une recomputation facile sans stockage.
MHF (Memory-Hard Functions) comme Argon2id : Augmentent le coût par évaluation via la pression mémoire, mais sont des primitives "single-shot" sans système de preuve de chaîne.

L'objectif est de concevoir une primitive qui combine l'exécution séquentielle, la difficulté mémoire (Memory-Hardness) et un état mutable, tout en étant résistante aux ASICs et vérifiable efficacement.

2. Méthodologie et Construction (PoSME)

L'auteur propose PoSME (Proof of Sequential Memory Execution), une primitive basée sur trois principes de conception clés :

A. Chasse de pointeurs dépendante des données (Data-Dependent Pointer Chasing)

Le calcul s'effectue sur une arène mutable (un tableau de $N$ blocs). À chaque étape, l'adresse de la prochaine lecture est déterminée par la valeur lue précédemment (via une fonction de hachage). Cela crée une chaîne stricte et séquentielle qui ne peut pas être parallélisée.

B. État d'arène mutable

Contrairement aux graphes statiques, l'arène évolue à chaque étape. Un bloc lu est modifié in-place. Pour recalculer un bloc évacué de la mémoire cache, un adversaire doit rejouer toute la chaîne d'écriture (O(ρ) hachages par défaut), rendant la réduction de stockage extrêmement coûteuse.

C. Liaison causale symbiotique (Symbiotic Causal Binding)

C'est l'innovation centrale. Chaque bloc écrit contient deux champs interdépendants :

Données (Data) : La valeur du bloc.
Hachage causal (Causal Hash) : Un hachage qui lie la valeur actuelle à l'historique des écritures (le curseur).
Ces deux champs sont "symbiotiques" : on ne peut pas fabriquer l'un sans l'autre. Cela double le coût de recalcul en cas de défaut de cache (2ρ au lieu de ρ) et amplifie la sécurité de la preuve.

D. Architecture Technique

Arène Hypercube : L'arène est mappée sur un hypercube booléen de dimension $d_{hc}$ .
Fonction d'étape : Chaque étape effectue $d$ lectures séquentielles, met à jour un curseur, et écrit un nouveau bloc avec la liaison symbiotique.
Vérification :
- Mode Classique : Utilise des preuves Merkle et Fiat-Shamir (taille de preuve logarithmique).
- Mode IVC (Incrementally Verifiable Computation) : Utilise la pliage sur les corps binaires (via Binius) pour atteindre une taille de preuve constante $O(1)$ , indépendamment du nombre d'étapes $K$ .

3. Contributions Clés

Nouvelle Primitive : Première combinaison d'un état d'arène mutable, d'un adressage par chasse de pointeurs dépendant des données et d'une liaison causale symbiotique.
Sécurité Espace-Temps Formelle :
- Preuve d'une borne inférieure formelle $S \cdot T = \Omega(K^2)$ pour les graphes causaux dynamiques.
- Introduction du concept de "staleness temporelle" (Theorem 4) : même si un adversaire stocke une grande partie de l'arène, les valeurs deviennent obsolètes à mesure que l'on remonte dans le temps de calcul, augmentant exponentiellement le coût de recalcul.
- Preuve que les stratégies adaptatives (changement dynamique de la mémoire stockée) n'apportent aucun avantage par rapport aux stratégies statiques.
Validation ROM (Random Oracle Model) : Validation mathématique et empirique (via BLAKE3) que les adresses générées sont uniformément distribuées, confirmant que l'arène se comporte comme une oracle aléatoire à l'échelle de production ( $N=2^{24}$ ).
Résistance Matérielle : Démonstration que la goulée d'étranglement est la latence d'accès aléatoire DRAM (40-50 ns) et non la bande passante ou la puissance de calcul.

4. Résultats Empiriques

Les auteurs ont benchmarké PoSME sur 17 plateformes CPU et 4 architectures GPU (y compris NVIDIA H100).

Coût de calcul : Le calcul du hachage représente moins de 3,5 % du coût total par étape. Le reste est du temps d'attente DRAM.
Performance GPU vs CPU : Contrairement à la croyance populaire, les GPU sont 14 à 19 fois plus lents que les CPU grand public pour PoSME.
- Raison : Les GPU sont optimisés pour le débit parallèle, pas pour les accès séquentiels dépendants. De plus, leur avantage en bande passante est annulé par la limite de capacité de la VRAM (les instances multiples sont limitées par la mémoire disponible, pas par la bande passante).
Résistance aux ASIC : L'avantage potentiel des ASICs est borné à environ 2x (lié à la latence DRAM physique), ce qui est bien inférieur aux 8-16x observés pour Argon2id. Un ASIC dédié serait économiquement irrationnel pour un gain de 30%.
Taille de preuve :
- Mode classique : ~8 Mo pour une profondeur de récursion $R=2$ .
- Mode IVC : Quelques kilo-octets ( $O(1)$ ).

5. Signification et Implications

PoSME comble le fossé entre les preuves de travail, les fonctions résistantes à la mémoire et les VDFs. Ses implications majeures incluent :

Attestation d'auteur (Authorship Attestation) : Prouver qu'un contenu a été généré par un processus séquentiel coûteux en temps réel, empêchant la génération massive par des fermes de calcul.
Résistance Sybil : En rendant le coût de création d'identités proportionnel à la latence DRAM (ressource physique limitée) plutôt qu'à la puissance de calcul, PoSME offre une barrière économique robuste contre les attaques Sybil.
Fonction de Délai Vérifiable (VDF) : Bien que PoSME ne prouve pas directement le temps écoulé (wall-clock time) sans wrapper externe, il fournit une base solide pour des VDFs hybrides qui combinent résistance matérielle et garanties temporelles.
Durabilité : La sécurité repose sur la physique de la latence DRAM, qui s'est améliorée très lentement (1,3x en 20 ans) comparée à la bande passante (20x), rendant la primitive structurellement plus durable que les solutions basées sur la bande passante.

En résumé, PoSME est une primitive cryptographique innovante qui force l'utilisation de la mémoire séquentielle de manière vérifiable, rendant les attaques par matériel spécialisé (ASIC/GPU) économiquement et techniquement inefficaces par rapport aux CPU grand public.