Preuves d’intervalle et Bulletproofs+

Prouver qu’un nombre caché est compris entre 0 et 2⁶⁴ sans le révéler

L’idée : décomposer le nombre en bits

Un nombre dans [0, 2⁶⁴), c’est 64 bits : v = b₀·1 + b₁·2 + b₂·4 + … + b₆₃·2⁶³, avec chaque bᵢ ∈ {0, 1}. Si l’on prouve (1) que chaque bᵢ vaut réellement 0 ou 1 et (2) que la somme pondérée des bits est égale à v, alors v est forcément dans l’intervalle.

La condition « est un bit » est algébrique : bᵢ·(bᵢ − 1) = 0. Le problème devient : prouver qu’un ensemble de nombres cachés satisfait un ensemble d’équations sans révéler ces nombres.

Évolution dans Monero

Le passage à Bulletproofs en 2018 a rendu les transactions environ 10× plus petites et a réduit les frais d’autant. L’une des mises à niveau les plus marquantes de l’histoire de Monero.

Comment fonctionne Bulletproofs (intuition)

1. Le prouveur s’engage sur le vecteur de bits a_L et le vecteur a_R = a_L − 1 avec un seul engagement de Pedersen vectoriel.
2. Le vérificateur (via un hachage, Fiat–Shamir) envoie des défis aléatoires y, z. Les 64 conditions « est un bit » et la condition « somme » sont réunies en une seule équation de produit scalaire ⟨l, r⟩ = t. Les défis aléatoires garantissent qu’on ne peut pas falsifier l’équation combinée sans satisfaire toutes les équations d’origine.
3. Un produit scalaire de vecteurs de longueur n se prouve récursivement : à chaque étape, les vecteurs sont « pliés en deux » avec un nouveau défi, et après log₂ n étapes il ne reste qu’un nombre de chaque côté. Chaque étape envoie 2 points — d’où la taille logarithmique.

Agrégation : pour m sorties, les vecteurs ont une longueur 64·m, et la taille n’augmente que de 2·log₂ m points. C’est pourquoi Monero limite le nombre de sorties par transaction à 16 et complète jusqu’à une puissance de deux.

Avantages et inconvénients