Résumé

  • En 1992, Dwork et Naor exigent d’une fonction de tarification qu’elle soit modérément coûteuse à calculer, peu coûteuse à contrôler et surtout impossible à amortir sur une multitude de destinataires.
  • Les dérogations font partie de l’architecture : une autorité peut distribuer des raccourcis, tandis que chaque destinataire peut exempter ses correspondants habituels. Les travaux ultérieurs sur la mémoire posent ensuite la question de l’inégalité entre machines.

Le courrier indésirable exploite moins la gratuité absolue que la quasi-gratuité de la copie suivante. Rédiger un message reste un effort humain ; le reproduire pour cent mille boîtes transforme cet effort en coût fixe. Le destinataire, lui, paie à chaque fois en attention, en stockage et en capacité de traitement.

Dans Pricing via Processing or Combatting Junk Mail, présenté sous forme préliminaire à CRYPTO ’92, Cynthia Dwork et Moni Naor déplacent le prix vers la requête. L’expéditeur calcule une fonction suffisamment difficile pour ne pas être gratuite, mais pas au point d’interdire un usage ordinaire. Le résultat accompagne le message et le système destinataire peut le contrôler rapidement avant livraison.

La propriété décisive n’est pas la dépense brute. Les auteurs demandent que la fonction résiste à l’amortissement : résoudre un cas ne doit pas réduire sensiblement le prix des milliers de cas suivants. Un calcul unique revendable ou réutilisable ne modifie pas l’économie d’un envoi massif. Il ajoute seulement un droit d’entrée fixe.

Faire appartenir le calcul à la requête

Le schéma associe le calcul au message, au moment et à la destination. Une autre adresse produit donc un autre problème. Un autre contenu aussi. Le temps permet d’écarter une preuve devenue trop ancienne. Cette liaison transforme la répétition, avantage économique du spammeur, en répétition de travail.

La vérification doit rester nettement moins chère que la production. Sinon, une défense contre l’abus offre à l’attaquant un nouveau levier : fabriquer des objets peu coûteux qui obligent le serveur à dépenser beaucoup pour les rejeter. L’asymétrie des efforts protège ainsi le côté receveur. L’émetteur prouve une dépense ; le gestionnaire de la ressource prend une décision rapide.

Les fonctions proposées empruntent à la théorie des nombres et à des constructions cryptographiques volontairement affaiblies : extraction de racines carrées modulo un nombre premier, adaptation de Fiat–Shamir et recyclage d’un schéma Ong–Schnorr–Shamir cassé. Il ne s’agit pas d’ériger l’infranchissable barrière d’un secret cryptographique. Il faut fabriquer un écart réglable entre « facile » et « difficile ».

Ce territoire intermédiaire échappait en grande partie à la théorie classique de la complexité. La sécurité demande souvent si un mur peut être franchi. La tarification demande combien de marches un utilisateur normal peut monter, combien un expéditeur industriel peut monter en parallèle et à quelle vitesse les machines réduiront leur hauteur. L’algorithme porte donc une politique économique.

Les exceptions désignent l’autorité

Les auteurs ne confondent pas volume et nuisance. Une annonce de conférence ou une liste professionnelle peut avoir des milliers de destinataires consentants. Appliquer le plein tarif à chaque copie risquerait de faire disparaître les usages collectifs légitimes avec le spam.

Le papier introduit alors un raccourci. Une autorité de tarification peut remettre à des agents de confiance une information qui rend le calcul peu coûteux. L’accès en masse devient possible selon les conditions fixées par le gestionnaire. De son côté, le destinataire conserve une liste locale de correspondants fréquents admis sans contrôle, ainsi qu’une liste de refus catégoriques.

La preuve de travail n’apparaît plus comme une barrière mathématique neutre. Quelqu’un choisit la fonction, sa difficulté et les détenteurs du raccourci. Le destinataire dessine sa propre frontière de familiarité. Le calcul établit qu’une dépense a eu lieu ; il ne décide pas quelle institution mérite une dispense.

Une fonction de tarification cassée ne produit pas les mêmes dégâts qu’une clé de chiffrement compromise. Si un acteur trouve une évaluation meilleur marché et l’exploite à grande échelle, l’abus redevient visible ; la fonction ou sa clé peut alors être remplacée. Mais cette réparation suppose toujours une autorité capable de détecter l’écart, de modifier le tarif et de coordonner la transition.

Quand la machine modifie le prix

Dix ans plus tard, Dwork, Andrew Goldberg et Naor reprennent ce problème dans On Memory-Bound Functions for Fighting Spam. Une fonction bornée par le processeur ne facture pas le même délai à une station récente et à une vieille machine. Le spammeur équipé de serveurs rapides obtient précisément la remise que la défense voulait lui retirer.

Le nouveau travail explore des accès dispersés à la mémoire, dont les latences variaient moins que les vitesses de processeur dans les machines testées. Il formalise une production exigeant de nombreux accès sans rapport entre eux, alors que la vérification en demande beaucoup moins, voire aucun. Les paramètres incluent le message, l’expéditeur, le destinataire et la date ; les preuves périmées ou déjà vues sont rejetées.

Le résultat expérimental reste circonscrit : une réalisation était environ quatre fois plus lente sur un boîtier à 233 MHz que sur une station à 3,06 GHz. Ce n’est ni l’égalité universelle ni une mesure du matériel actuel. Les auteurs se demandent même si une fonction parfaitement égalitaire serait souhaitable : obliger un abuseur à acheter du matériel cher peut être utile, tandis qu’un appareil lent pourrait déléguer le calcul. La justice du prix devient une décision de conception.

Une filiation n’est pas une identité

La notice de publication de Harvard, la biographie intellectuelle de Dwork et la notice de Microsoft Research replacent cette recherche dans une carrière qui va des systèmes répartis à la confidentialité différentielle et à l’équité algorithmique. Harvard note son influence sur les cryptomonnaies.

Cette filiation ne transforme pas l’article de 1992 en description de Bitcoin. Il ne contient ni consensus par chaîne, ni émission monétaire, ni sélection de branche. Son objet est plus étroit et plus réutilisable : demander la preuve d’un coût intentionnel, rattaché à une requête, avant d’ouvrir l’accès à une ressource.

Cinq questions en restent séparées : quelle ressource protège-t-on ? à quoi le travail est-il lié ? peut-il être amorti ou rejoué ? quel est le coût du contrôle ? qui ajuste le prix et accorde les exceptions ? Prononcer « preuve de travail » ne répond à aucune d’elles.