💻 computer science

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

Cet article introduit « Split Tallies », un schéma d'audit à mémoire constante qui vérifie des ensembles ordonnés dynamiques maintenus par une partie non fiable en suivant les écarts maximaux via un calcul de certificat discret, atteignant une sécurité à haute probabilité contre des adversaires aux capacités de calcul illimitées tout en prouvant qu'une telle efficacité est impossible sans l'usage de l'aléatoire caché ou d'horodatages.

Auteurs originaux : Faruk Alpay, Levent Sarioglu

Publié 2026-06-12

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Faruk Alpay, Levent Sarioglu

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

Imaginez que vous avez un bibliothécaire très intelligent, mais potentiellement malhonnête (le Mainteneur), qui gère une bibliothèque de livres disposés dans un ordre parfait. Vous (l'Utilisateur) posez des questions du type « Le livre X est-il ici ? » ou « Quel est le livre juste avant Y ? ». Le bibliothécaire répond instantanément. Cependant, vous ne faites pas confiance à la mémoire interne du bibliothécaire, et vous ne pouvez pas vérifier ses étagères à chaque fois que vous posez une question, car cela serait trop lent.

Vous avez besoin d'un moyen de vérifier plus tard que chaque réponse donnée par le bibliothécaire était réellement correcte, sans avoir besoin de vous souvenir de toute la bibliothèque vous-même.

Ce document présente un système appelé Split Tallies pour résoudre ce problème. Il utilise un mélange ingénieux de l'histoire comptable ancienne et des mathématiques modernes pour créer un « certificat » qui prouve que le bibliothécaire dit la vérité, en utilisant presque aucune mémoire de votre côté.

Voici comment cela fonctionne, décomposé en concepts simples :

1. La métaphore ancienne : Le bâton fendu

L'idée est inspirée des « bâtons de comptage » (tally sticks) anglais d'il y a 600 ans.

L'histoire : Si un marchand prêtait de l'argent à un fermier, ils taillaient des encoches dans un bâton de bois pour représenter le montant. Ensuite, ils fendaient le bâton en longueur. Le marchand gardait une moitié (le Stock) et le fermier gardait l'autre (le Foil).
La magie : Le moment venu de rembourser, ils joignaient les deux moitiés. Seul le vrai bâton s'emboîtait parfaitement car le grain du bois et les encoches s'alignaient. Un faux bâton ne correspondrait jamais.
Dans ce document :
- Le Bibliothécaire détient le « Foil » (sa mémoire interne de la bibliothèque).
- L'Auditeur (vous) détient le « Stock » (une liste secrète de 5 nombres).
- Le Tally Public est une liste de « encoches » que le bibliothécaire doit noter après chaque action.
- L'Audit est le moment où vous vérifiez si l'histoire du bibliothécaire correspond à votre liste secrète.

2. Le tour central : Suivre les « écarts » plutôt que les livres

La plupart des gens pensent à une bibliothèque comme à une liste de livres. Ce document dit : « Non, pensez aux espaces vides entre les livres. »

Imaginez que l'étagère de la bibliothèque a un début (0) et une fin (U).
Si l'étagère est vide, il y a un seul immense écart du début à la fin.
Si vous ajoutez un livre, vous divisez cet écart géant en deux écarts plus petits.
Si vous supprimez un livre, vous fusionnez deux écarts pour n'en faire qu'un seul.

Le document prouve que si vous savez exactement comment les écarts sont connectés, vous savez exactement où se trouve chaque livre. Le bibliothécaire ne se contente pas de dire « Le livre X est ici » ; il doit citer l'ID de l'écart spécifique qui le prouve.

3. Les règles du jeu (L'« Indenture »)

Pour empêcher le bibliothécaire de mentir, le système le force à suivre des règles strictes, comme un jeu de chaises musicales avec un timing rigoureux :

L'Horloge Publique : Chaque fois qu'un nouvel écart est créé (un livre est ajouté), il reçoit un numéro d'identification (ID) unique et séquentiel (comme un horodatage).
La Règle de Citation : Chaque fois que le bibliothécaire répond à une question, il doit citer l'ID de l'écart qu'il utilise.
- Règle cruciale : Vous ne pouvez citer qu'un ID d'écart qui a été créé avant ce moment. Vous ne pouvez pas citer un ID du « futur ».
Les Mathématiques Secrètes : L'Auditeur (vous) détient un nombre secret. Chaque fois qu'un écart naît ou est utilisé, l'Auditeur multiplie ses nombres secrets par une formule mathématique impliquant l'ID de cet écart.
- Si le bibliothécaire est honnête, les mathématiques fonctionnent parfaitement à la fin.
- Si le bibliothécaire ment (par exemple, en disant qu'un livre est là alors qu'il ne l'est pas), il doit falsifier un ID d'écart. Comme il ne connaît pas votre nombre secret, les mathématiques échoueront presque certainement à la fin.

4. Pourquoi est-ce si efficace ?

Le document affirme que ce système est incroyablement léger :

Pour vous (l'Auditeur) : Vous avez seulement besoin de mémoriser 5 nombres et un « flag » (un interrupteur oui/non). Vous n'avez pas besoin de stocker la bibliothèque, les livres ou l'historique. Vous vous contentez de regarder le flux de notches.
Pour le Bibliothécaire : Il a besoin d'un tout petit peu d'espace supplémentaire (un nombre supplémentaire par livre) pour stocker les IDs des écarts.
Le Coût : Si le bibliothécaire tente de tricher, la probabilité qu'il y parvienne est astronomiquement faible (moins de 1 sur un billion pour un million d'opérations).

5. Les parties « impossibles »

Les auteurs ont également prouvé que vous ne pouvez pas rendre ce système plus simple sans le briser :

Pas de hasard ? Si vous n'utilisez pas de nombre aléatoire secret, un menteur habile peut toujours vous tromper.
Pas de secret ? Si le bibliothécaire connaît votre nombre secret, il peut falsifier les mathématiques.
Pas de limites de temps ? Si le bibliothécaire est autorisé à citer des IDs « futurs » (voyage dans le temps), il peut créer une bibliothèque de toutes pièces qui semble réelle. La règle de l'« horloge » est essentielle pour empêcher cela.

6. Le bonus du « Rééquilibrage »

Les bibliothèques doivent parfois réorganiser les étagères (diviser une étagère pleine en deux, ou fusionner deux étagères vides). Le document montre que même ces étapes de réorganisation désordonnées peuvent être auditées. Ils ont prouvé que peu importe le nombre de fois que le bibliothécaire réorganise, le nombre total de « mouvements » est prévisible. L'auditeur peut simplement compter les « reçus » du bibliothécaire pour ces mouvements afin de s'assurer qu'il ne fait pas de travail supplémentaire pour cacher un mensonge.

Résumé

Ce document construit un détecteur de mensonges mathématique pour les listes dynamiques.

Le Bibliothécaire fait le travail.
L'Auditeur ne fait presque rien (juste 5 nombres).
Le Tally est un registre public de « notches ».
Le Résultat : Vous pouvez vérifier avec une certitude proche de 100 % que chaque réponse donnée était correcte, même si le bibliothécaire est un super-ordinateur essayant de vous tromper, et même si vous avez presque aucune mémoire pour stocker les données.

C'est comme vérifier le solde d'un compte bancaire en regardant un simple reçu qui prouve que les calculs sont justes, plutôt que de compter chaque pièce dans le coffre-fort.

Résumé technique : Split Tallies : Un calcul de certificats discrets pour l'audit d'ensembles ordonnés dynamiques en mémoire constante

Énoncé du problème

Le document traite de la vérification d'ensembles ordonnés dynamiques maintenus par une partie adverse (le « mainteneur ») et interrogés par un consommateur. Dans de nombreux scénaux informatiques modernes, les structures de données résident dans des environnements non approuvés (par exemple, services distants, accélérateurs matériels opaques ou bibliothèques tierces). Le consommateur émet des opérations (insertions, suppressions, tests d'appartenance, requêtes de prédécesseur/successeur et requêtes d'extrémum) et reçoit des réponses immédiatement, agissant sur celles-ci sans délai.

Le défi central est de fournir un certificat de correction pour l'intégralité de l'historique des opérations sans exiger que le consommateur (l'auditeur) stocke la structure de données elle-même ou réexécute les opérations. L'auditeur doit être passif, ne stockant qu'une quantité constante d'état (spécifiquement, cinq mots de machine et un drapeau), tandis que le mainteneur ajoute une courte « entaille » (enregistrement) à une séquence publique et incrémentale appelée tally (comptage) pour chaque opération. L'objectif est de détecter, avec une probabilité élevée, si le mainteneur a fourni une réponse incorrecte, même si celui-ci possède une puissance de calcul illimitée et adapte sa stratégie en fonction de l'historique visible.

Méthodologie

La solution proposée, nommée Split Tallies, s'inspire des historiques bâtons de compte (tally sticks) en bois, où une dette était enregistrée par une entaille sur un bâton, lequel était ensuite fendu longitudinalement. Le créancier gardait le « stock » et le débiteur le « foil ». Lors du règlement, les deux moitiés étaient assemblées pour vérifier l'authenticité. Dans ce contexte numérique :

Le Tally (Comptage) : Un flux public d'entailles ajoutées par le mainteneur.
Le Stock : L'état privé de l'auditeur (cinq mots et un drapeau).
Le Foil (Feuille) : La comptabilité interne de la structure du mainteneur.
L'Audit : Le processus d'« assemblage » du stock contre le foil (divulgué à la fin d'une session).

Le calcul des écarts (Gap Calculus)

Le cœur technique du document est un calcul discret des écarts. Au lieu d'auditer l'ensemble $S$ directement, le système audite la famille des intervalles vacants maximaux (écarts) qui partitionnent l'univers ordonné.

Représentation : Un ensemble $S$ sur un univers $\{1, \dots, U\}$ est représenté de manière unique par une chaîne imbriquée d'écarts $\langle a, b \rangle$ reliant les sentinelles $0$ et $U+1$ .
Forme normale : Le document prouve que cette famille d'écarts correspond à l'unique chemin unitaire de $0 $à$ U+1$ dans un graphe acyclique d'intervalles.
Réécritures : Les opérations sont modélisées comme des réécritures locales de ce chemin :
- Insertion : Divise un écart $\langle a, b \rangle$ en deux $\langle a, x \rangle, \langle x, b \rangle$ .
- Suppression : Fusionne deux écarts adjacents $\langle a, x \rangle, \langle x, b \rangle$ en un seul $\langle a, b \rangle$ .
- Requêtes : Sont répondues en exhibant un écart spécifique (par exemple, l'écart contenant $x$ pour l'appartenance, ou l'écart commençant à $x$ pour le prédécesseur).

La discipline de l'indenture

Pour auditer ces réécritures sans stocker l'état, l'auditeur utilise un mécanisme de fingerprinting basé sur le test d'identité polynomiale sur un corps fini $\mathbb{F}_p$ :

Codes et horodatages : Chaque naissance d'écart se voit attribuer un code unique (horodatage) via un compteur public $\kappa$ .
Citations : Chaque opération doit citer les codes des écarts qu'elle consomme (réécritures).
Accumulateurs : L'auditeur maintient deux accumulateurs, $A$ $A$ (pour les naissances) et $R$ $R$ (pour les consommations). Pour un écart avec un code $c$ $c$ et des extrémités $a, b$ $a, b$ , la valeur $\nu(a, b, c)$ $ν (a, b, c)$ est projetée dans le corps.
- À la naissance : $A \leftarrow A \cdot (z - \nu(a, b, c))$
- À la consommation : $R \leftarrow R \cdot (z - \nu(a, b, c))$
- Ici, $z$ est un élément de corps secret choisi par l'auditeur avant la session.
Vérification : Lors de l'audit, le mainteneur divulgue l'ensemble actuel des écarts avec leurs codes. L'auditeur vérifie si les écarts divulgués s'assemblent (forment une chaîne valide) et vérifie si $A = R$ .

Mécanismes clés

Règle temporelle : Un code cité doit être strictement inférieur à la valeur du compteur au début de l'événement. Cela empêche le mainteneur de « emprunter » des codes futurs pour forger un registre équilibré.
Forçage : En raison de l'unicité du chemin des écarts, la réponse correcte à toute requête est une fonction forcée de l'écart cité. Si le mainteneur cite un écart qui n'existe pas ou qui n'est plus actif, la réponse sera incohérente avec les propriétés de l'écart, ou le registre deviendra déséquilibré.

Contributions et résultats clés

1. Le théorème d'audit (Correction et Complétude)

Le document établit que le schéma est parfaitement complet (les mainteneurs honnêtes sont toujours acceptés) et $\epsilon$ -sûr.

Erreur de fiabilité (Soundness Error) : Si un mainteneur fournit une seule réponse incorrecte parmi $T$ opérations, la probabilité d'acceptation est au plus $(4T + 1)/p$ .
Paramètres : Avec un nombre premier de 61 bits (par exemple, $2^{61}-1$ ), la probabilité d'erreur est inférieure à $2^{-38}$ pour des sessions allant jusqu'à un million d'opérations.
Hypothèses : Aucune hypothèse de dureté computationnelle n'est requise ; la sécurité est informationnelle contre un adversaire aux capacités de calcul illimitées.

2. Résultats d'impossibilité et de nécessité

Le document prouve que les choix de conception spécifiques sont indispensables :

Plancher déterministe : Tout auditeur déterministe avec une correction de fin de session doit stocker au moins $2n - \log_2(2n+1)$ bits d'état pour un ensemble de taille $n$ . Cela prouve que le hasard est une exigence, et non une commodité.
Aléas secrets : Si les pièces de monnaie aléatoires de l'auditeur sont visibles par le mainteneur, l'erreur de fiabilité devient 1 (le mainteneur peut toujours forger un historique). La secretitude du point d'évaluation $z$ est nécessaire.
Nécessité de la règle temporelle : Sans la règle empêchant la citation de codes futurs, une fraude explicite en trois opérations existe, laquelle atteint un équilibre exact et est acceptée avec une probabilité de 1.

3. Implémentation du mainteneur

Le document fournit une implémentation concrète utilisant un arbre (2, 4) orienté vers les feuilles :

Complexité : Les opérations s'exécutent en $O(\log n)$ temps dans le pire des cas.
Surcoût : La structure ne nécessite qu'un mot supplémentaire par élément (pour stocker le code de l'écart).
Rééquilibrage audité : Le document introduit une enveloppe d'attestation prouvant que le nombre d'événements structurels (divisions, fusions, partages) sur $m$ mises à jour est au plus $2m$ . Cette limite est certifiée par l'auditeur comptant les attestations d'un mot ajoutées par le mainteneur, transformant l'analyse amortie en une affirmation publiquement vérifiable.

4. Points de contrôle et époques

Le protocole prend en charge des points de contrôle arbitraires. Les audits peuvent être effectués à tout moment, et les époques acceptées peuvent être enchaînées avec des limites d'erreur additives. Cela permet de moduler la latence de détection (par exemple, auditer après chaque opération pour une sécurité élevée, ou moins fréquemment pour l'efficacité).

Signification et portée

Le document prétend fournir un compte clos d'audit en mémoire constante pour les ensembles ordonnés dynamiques. Sa signification réside dans :

Changement de paradigme : Passer du « test en isolation » à la « certification voyageant avec l'exécution ».
Garanties informationnelles : Atteindre la vérification sans hypothèses cryptographiques (comme les arbres de Merkle ou les signatures numériques), en s'appuyant sur les propriétés algébriques des polynômes et la structure combinatoire des ensembles ordonnés.
Bornes inférieures serrées : Démontrer que la solution proposée en mémoire constante est proche de l'optimalité en prouissant que toute solution déterministe nécessite un espace linéaire et que le hasard doit être caché.
Constantes explicites : Tous les paramètres (tailles des nombres premiers, nombre de mots, bornes d'erreur) sont explicites et calibrés pour un usage pratique (par exemple, tenir dans des mots de 64 bits).

La portée est strictement limitée à l'interface des sept opérations (insertion, suppression, appartenance, prédécesseur, successeur, min, max). Le document note explicitement que le calcul des écarts certifie l'arrangement (adjacence, encadrement, extrémalité) mais ne s'étend pas aux propriétés agrégées comme le rang, qui ne sont pas locales à un seul écart. La détection est rétrospective ; le document reconnaît que la détection en ligne (rejet immédiat d'une réponse) dans ce cadre informationnel est une frontière reconnue liée à l'existence de fonctions à sens unique, et que la solution proposée est donc optimale dans son modèle rétrospectif défini.