💻 computer science

Protocols for Univariate Sumcheck

Cet article présente trois approches candidates pour le protocole de vérification de somme univariée sur des racines de l'unité, dont deux réduisant le problème à une évaluation multivariée compatible avec Gemini, tout en permettant des réductions de tours tout en conservant un temps de calcul linéaire pour le prouveur.

Auteurs originaux : Malcom Mohamed

Publié 2026-03-24

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Malcom Mohamed

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 Contexte : Le Grand Défi de la "Preuve"

Imaginez que vous êtes un organisateur de fête (le Prover) qui veut prouver à un inspecteur très méfiant (le Vérificateur) que tout s'est bien passé. Vous avez une liste de 1 million de convives et vous devez prouver que la somme de leurs notes de satisfaction est exactement de 500 000.

Le problème ? L'inspecteur ne veut pas vérifier un par un les 1 million de notes (ce serait trop long). Il veut une preuve rapide, courte et incontestable.

Dans le monde des cryptographies modernes (les SNARKs), on utilise des mathématiques complexes (des polynômes) pour faire ces preuves. Il existe deux façons principales de gérer ces données :

Le monde "Multidimensionnel" (Multilinear) : Comme un cube de Rubik géant. C'est très efficace pour le calcul (le Prover est rapide), mais la preuve finale est un peu longue à vérifier.
Le monde "Unidimensionnel" (Univariate) : Comme une longue file d'attente. C'est très rapide à vérifier (l'inspecteur a juste à regarder un seul point), mais le calcul pour le Prover est souvent lent et lourd.

Le but de ce papier : Malcom Mohamed veut créer un pont magique. Il veut permettre aux organisateurs de fêtes qui utilisent la "file d'attente" (Univariate) de bénéficier de la rapidité de calcul du "cube de Rubik" (Multilinear), sans perdre la rapidité de vérification.

Les Trois Solutions Proposées

L'auteur propose trois nouvelles méthodes (protocoles) pour résoudre ce problème. Voici comment on peut les imaginer :

1. La Méthode du "Pliage de Carte" (Protocol 2)

L'analogie : Imaginez que vous avez une immense carte au trésor (vos données) étalée sur le sol. L'inspecteur veut vérifier un point précis, mais il ne veut pas marcher sur toute la carte.
Le truc : Au lieu de marcher, vous pliez la carte en deux, puis encore en deux, jusqu'à ce qu'elle tienne dans votre poche. À chaque pli, vous gardez une trace mathématique qui prouve que le point que l'inspecteur veut vérifier est toujours là, même si la carte a rétréci.
Le résultat : Vous transformez le problème complexe du "cube" en une série de plis simples. Cela permet d'utiliser les techniques rapides du monde multidimensionnel directement sur la file d'attente, en gardant le temps de calcul très bas (linéaire).

2. La Méthode du "Détective Corrigé" (Basée sur DGM)

L'analogie : Un détective (un chercheur nommé Drake) avait proposé une méthode pour vérifier la file d'attente en la découpant en deux : les nombres pairs et les nombres impairs.
Le problème : L'auteur du papier dit : "Attendez, le détective a fait une erreur de calcul ! Sa méthode ne marche pas telle quelle."
La correction : Il prend l'idée du détective, corrige l'erreur mathématique (en ajustant les pièces du puzzle pour qu'elles s'emboîtent parfaitement) et montre que, une fois corrigée, cette méthode fonctionne et est très rapide. C'est comme réparer un moteur de voiture pour qu'il roule à la vitesse de la lumière.

3. La Méthode du "Téléporteur Direct" (Protocol 4)

L'analogie : C'est la solution la plus élégante. Au lieu de plier la carte ou de corriger un détective, vous utilisez un téléporteur.
Le fonctionnement : Vous prenez directement la file d'attente (Univariate) et vous la transformez instantanément en un cube (Multilinear) pour faire le calcul, puis vous la retransformez.
Pourquoi c'est génial : C'est la méthode la plus simple et la plus efficace. Elle évite les étapes intermédiaires lourdes. C'est comme si vous pouviez traverser un mur sans même vous en rendre compte.

L'Idée de "Réduire les Tours" (Round Reduction)

Dans ces protocoles, il y a souvent une série d'échanges entre le Prover et le Vérificateur (des "tours"). Plus il y a de tours, plus c'est long.

L'analogie : Imaginez que vous devez descendre un immeuble de 100 étages.
- La méthode classique : Vous descendez un étage par un étage (100 tours).
- La méthode de ce papier : Vous pouvez sauter 50 étages d'un coup, puis 25, puis 12... jusqu'à arriver au bas très vite.
Le gain : L'auteur montre qu'on peut réduire le nombre d'échanges de 1 million à seulement quelques dizaines (ou même la racine carrée de 1 million, soit 1000), tout en gardant le calcul rapide. C'est comme passer de l'escalier à l'ascenseur express.

En Résumé : Pourquoi c'est important ?

Ce papier est une avancée majeure car il brise une barrière technique.

Avant : Si vous vouliez une preuve rapide à vérifier (pour les utilisateurs), vous deviez accepter un calcul lent pour le serveur. Si vous vouliez un calcul rapide, la vérification était lourde.
Aujourd'hui (grâce à ce papier) : On peut avoir le meilleur des deux mondes. Le serveur calcule vite (comme un super-ordinateur), et l'inspecteur vérifie vite (comme un coup d'œil).

C'est comme si on avait trouvé un moyen de faire cuire un gâteau en 5 minutes (au lieu d'une heure) tout en s'assurant qu'il est parfaitement cuit, sans que le chef ait besoin de rester dans la cuisine pendant tout le processus. Cela rendra les systèmes de confidentialité et de sécurité sur internet beaucoup plus rapides et accessibles pour tout le monde.

1. Problématique

Les systèmes de preuves à connaissance nulle (SNARKs) reposent souvent sur des techniques algébriques pour prouver des faits concernant des données encodées sous forme de polynômes. Une brique fondamentale de ces systèmes est le protocole Sumcheck, qui permet de réduire une affirmation globale (la somme de valeurs d'un polynôme sur un domaine) à une affirmation locale (l'évaluation du polynôme en un point aléatoire).

Il existe actuellement une séparation nette dans le paysage des SNARKs :

Systèmes Multilinéaires : Utilisent l'extension multilinéaire (mlex) des données. Ils bénéficient de protocoles Sumcheck multivariés standards (comme LFKN) très efficaces pour le prouveur (temps linéaire), mais qui nécessitent un nombre de tours de communication proportionnel au nombre de variables ( $m$ ), ce qui est coûteux en bande passante.
Systèmes Univariés : Utilisent l'extension univariée (unex) sur des racines de l'unité. Leurs protocoles Sumcheck standards (comme Aurora) ne nécessitent qu'un seul tour, ce qui est très efficace pour le vérificateur et la bande passante, mais les protocoles connus pour le prouveur sont souvent moins efficaces (temps quasi-linéaire ou pire) ou nécessitent des adaptateurs complexes.

Le problème central est de concevoir un protocole de Sumcheck pour des polynômes univariés qui soit efficace en temps pour le prouveur (linéaire) tout en conservant les avantages des systèmes univariés (peu de tours, compatibilité avec les oracles existants). L'article examine si l'on peut combiner la puissance des techniques multivariées avec les avantages des systèmes univariés, notamment via l'adaptateur Gemini.

2. Méthodologie

L'auteur propose trois approches distinctes pour réaliser un Sumcheck univarié linéaire, en exploitant des relations entre les extensions multilinéaires et univariées.

A. Réduction de `mlex` vers `unex` (Section 3)

L'auteur propose un protocole d'identification (adaptor) qui permet de prouver l'évaluation d'une extension multilinéaire (mlex) en utilisant un oracle d'extension univariée (unex).

Mécanisme : Le protocole utilise une folding récursive par carrés. Il décompose le polynôme univarié $f$ en deux parties : une partie "carrée" ( $f_{sq}$ ) et une partie "non-carrée" ( $f_{no}$ ), correspondant respectivement aux coefficients pairs et impairs.
Fonctionnement : À chaque tour, le prouveur envoie des oracles pour ces composantes. Le vérificateur confirme la cohérence via une formule d'interpolation de Lagrange généralisée. Après $m$ tours, la réduction aboutit à une évaluation multilinéaire.
Avantage : Cela permet d'utiliser le protocole Sumcheck multivarié standard (LFKN) directement sur des oracles univariés.

B. Réduction directe du Sumcheck univarié vers Gemini (Section 4)

L'article analyse et corrige un protocole existant (DGM - Drake, Gabizon, Meckler) qui tentait de réduire le Sumcheck univarié à l'adaptateur Gemini.

Correction : L'auteur identifie une faille dans le protocole DGM original (incohérence de degrés dans les identités polynomiales) et propose une version corrigée (Protocole 3) qui ajoute des vérifications de degré et de cohérence via des quotients.
Alternative Directe (Protocole 4) : L'auteur propose une méthode plus simple et plus efficace. Elle repose sur l'observation que l'évaluation d'un polynôme univarié sur les racines de l'unité peut être réécrite comme l'évaluation d'un polynôme multilinéaire sur un sous-ensemble spécifique de ces racines.
- Le protocole réduit directement la somme $\sum g(f(w_i))$ à une évaluation multilinéaire en utilisant une structure de somme similaire au Sumcheck multivarié, mais adaptée au domaine univarié.
- Cette approche évite les étapes intermédiaires complexes du protocole DGM corrigé.

C. Réduction du nombre de tours (Round Reduction)

Pour tous les protocoles proposés, l'auteur montre comment réduire le nombre de tours de $m$ à $\log(m)$ ou même $O(\sqrt{m})$ :

Stratégie : Arrêter le protocole récursif après $k$ tours. La revendication restante (sur un domaine plus petit) est ensuite traitée par un protocole Sumcheck univarié à un seul tour (comme Aurora).
Innovation : Contrairement à des travaux précédents (comme HybridPlonk), cette méthode ne nécessite pas de phase de traduction de base (basis translation) coûteuse entre les représentations coefficients/valeurs, car la correspondance est naturelle.

3. Contributions Clés

Protocole d'Adaptateur Linéaire (mlex vers unex) : Présentation d'un protocole (Protocole 2) permettant d'utiliser le Sumcheck multivarié sur des données univariées avec un temps de prouveur linéaire $O(2^m)$ , surpassant les méthodes précédentes (quasi-linéaires).
Correction et Identification du Protocole DGM : Démonstration que le protocole DGM original est défectueux, mais qu'une version corrigée est en fait un cas particulier d'un Sumcheck linéaire basé sur Gemini.
Protocole de Sumcheck Direct (Protocole 4) : Introduction d'une méthode plus simple et plus efficace que DGM pour réduire le Sumcheck univarié à Gemini. Ce protocole atteint des performances équivalentes au Sumcheck multivarié standard tout en restant nativement univarié.
Optimisation des Tours : Démonstration que ces protocoles permettent des réductions de tours naturelles jusqu'à $\log(m)$ ou $O(\sqrt{m})$ sans surcoût de calcul pour le prouveur, en combinant la réduction récursive avec des protocoles à un tour pour les petits domaines restants.

4. Résultats et Performance

Le tableau 2 de l'article compare les nouvelles approches avec la méthode standard (Aurora) et les combinaisons existantes :

Complexité du Prouveur : Tous les nouveaux protocoles maintiennent un temps de calcul linéaire par rapport à la taille du domaine ( $O(2^m)$ ), ce qui est un avantage majeur par rapport aux solutions précédentes pour les systèmes univariés.
Complexité du Vérificateur et Tours :
- L'approche standard (multivariée + adaptateur) nécessite $m$ tours.
- Avec la réduction de tours, le nombre de tours peut être réduit à $\log(m)$ (en utilisant Aurora pour la fin) ou $O(\sqrt{m})$ (via une généralisation des paramètres de folding).
- Le Protocole 4 (Direct) combiné à Gemini est le plus efficace en termes de communication (moins d'oracles envoyés) et de calcul du vérificateur par rapport à l'approche via l'adaptateur de la Section 3.
Comparaison avec Aurora : Les nouvelles méthodes permettent d'obtenir l'efficacité du prouveur du monde multivarié (linéaire) tout en gardant la compatibilité avec les oracles univariés existants, comblant ainsi le fossé de performance entre les deux mondes.

5. Signification et Impact

Cet article est significatif car il démocratise l'efficacité du prouveur linéaire pour les systèmes univariés.

Unification : Il brise la dichotomie traditionnelle où l'on devait choisir entre l'efficacité du prouveur (multivarié) et l'efficacité du vérificateur/bande passante (univarié).
Pragmatisme : En corrigeant le protocole DGM et en proposant une alternative plus simple (Protocole 4), l'auteur fournit des solutions pratiques et implémentables pour les systèmes de SNARKs modernes (comme ceux utilisant des oracles de polynômes).
Flexibilité : La capacité de réduire le nombre de tours à $\log(m)$ ou $O(\sqrt{m})$ sans pénalité de performance offre une flexibilité cruciale pour l'optimisation des systèmes de preuve selon les contraintes spécifiques (latence réseau vs puissance de calcul).
Fondation pour l'avenir : Ces protocoles permettent d'intégrer des techniques de "monde opposé" (opposite world) dans les systèmes existants sans surcoût de traduction de base, ouvrant la voie à de nouvelles architectures de SNARKs plus performantes.

En résumé, Malcom Mohamed démontre qu'un Sumcheck univarié linéaire est non seulement possible mais peut être réalisé de manière générique et efficace, rendant les systèmes univariés aussi performants que leurs homologues multivariés du point de vue du prouveur.