Complétude de Turing : définition, raisons pour lesquelles Ethereum en avait besoin et pourquoi Bitcoin a choisi de l’éviter
Un ami travaillant dans la finance traditionnelle m'a demandé un jour pourquoi Ethereum pouvait faire tourner des applications financières complètes sur sa blockchain, alors que Bitcoin ne permettait que d'envoyer de l'argent d'une adresse à une autre. « Ce sont tous deux des blockchains », m'a-t-il répondu. « Quelle est la différence concrète ? »
J'ai tenté d'expliquer la complétude de Turing, mais son regard s'est voilé. J'ai donc réessayé avec une analogie. Bitcoin est un distributeur automatique. On y insère de l'argent, on appuie sur un bouton, et on obtient un article précis. Il fait ce pour quoi il a été conçu, et rien d'autre. Ethereum est une cuisine avec un chef. Donnez-lui n'importe quelle recette et suffisamment d'ingrédients, et il peut tout préparer. Boucles (« remuer jusqu'à épaississement »), décisions (« si c'est trop salé, ajouter de l'eau »), créativité (« improviser un dessert avec les restes »). Le chef peut suivre n'importe quelle instruction. Le distributeur automatique, lui, ne le peut pas.
Cette analogie n'est pas parfaite. Un informaticien soulignerait plusieurs points où j'ai simplifié à l'excès. Mais elle a permis à mon ami de poser la bonne question : « Alors, pourquoi quelqu'un choisirait-il d'être un distributeur automatique ? »
Cette question résume tout le débat sur la complétude de Turing dans le domaine des cryptomonnaies. Sécurité contre flexibilité. Prévisibilité contre puissance. Bitcoin contre Ethereum. Et la réponse, aussi agaçante soit-elle, est que les deux camps ont raison.
D’où vient cette idée et pourquoi un article de mathématiques de 1936 est encore pertinent ?
En 1936, Alan Turing publia un article intitulé « Sur les nombres calculables ». Il avait alors 23 ans. Il y décrivait une machine d'une simplicité telle qu'elle semblait être un jouet : une bande de ruban divisée en cellules, une tête de lecture/écriture qui lit et écrit des symboles, et des règles qui indiquent à la tête de lecture/écriture ce qu'elle doit faire en fonction des symboles lus. Bande, tête de lecture/écriture, règles : voilà la machine dans son intégralité.
Voici ce qui me donne encore des frissons. Turing a prouvé que cette machine d'une simplicité déconcertante pouvait calculer tout ce qu'un ordinateur pourra jamais calculer. Absolument tout. Votre téléphone effectue des opérations de lecture et d'écriture en ce moment même. Le serveur qui exécute ChatGPT aussi. La puce de votre voiture également. Il a prouvé tout cela en 1936, avant même l'existence du premier ordinateur électronique sur Terre. Cet article a près de 90 ans et tous les départements d'informatique du monde l'enseignent encore au premier semestre.
Quand on dit qu'un système est « Turing-complet », cela signifie qu'il peut simuler la machine à ruban de Turing. Il peut exécuter des boucles, prendre des décisions à partir de données, stocker des informations en mémoire et exécuter n'importe quel algorithme. Votre ordinateur portable est Turing-complet. Une calculatrice de poche ne l'est pas. Et voici une anecdote amusante que j'adore partager : les circuits de redstone de Minecraft sont techniquement Turing-complets. Des joueurs ont construit des ordinateurs fonctionnels dans le jeu. Pas des ordinateurs vraiment utiles, certes, mais fonctionnels.
Comment cela se traduit-il dans le Bitcoin : pourquoi Satoshi a choisi la limitation
Satoshi a créé Bitcoin avec un langage de programmation appelé Bitcoin Script, volontairement rudimentaire. Il vérifie les signatures, gère les portefeuilles multi-signatures, bloque les fonds avec des conditions temporelles, et c'est tout. Pas de boucles. Pas de branchements complexes. Aucun état n'est conservé entre les transactions.
La première fois que j'ai compris l'importance de ce point, je lisais un article sur le piratage de la DAO sur Ethereum (j'y reviendrai). Un appel de fonction récursif a permis de dérober 150 millions de dollars à un contrat intelligent, car le code pouvait s'appeler lui-même dans une boucle infinie que les développeurs n'avaient pas anticipée. Sur Bitcoin, ce type de piratage est impossible. Non pas improbable, mais impossible. Bitcoin Script ne peut pas s'appeler lui-même. Impossible de créer une boucle. Impossible d'utiliser la récursivité. Le langage est trop limité pour exprimer le genre de bug qui a coûté 150 millions de dollars à Ethereum.
Cette limitation est en réalité une caractéristique essentielle. Chaque script Bitcoin s'arrête de manière prévisible. On peut le lire et savoir exactement ce qu'il fera. Aucune surprise. Aucun comportement inattendu. Lorsqu'il s'agit de sécuriser un réseau d'une valeur de plus de mille milliards de dollars, la prévisibilité n'est pas un défaut, mais un choix de conception.
Ce que Vitalik a construit et pourquoi cela a tout changé.
Vitalik Buterin avait 19 ans lorsqu'il a publié le livre blanc d'Ethereum en 2013. Sa question était simple et radicale : et si la blockchain elle-même pouvait exécuter n'importe quel programme ? Pas seulement « envoyer des pièces de A à B », mais tout ce qu'un ordinateur peut faire ?
J'étais à la fac quand le livre blanc d'Ethereum est sorti. Je l'ai lu dans un PDF partagé sur un forum Bitcoin. La moitié des réponses disaient que Vitalik était un génie. L'autre moitié disait qu'il construisait un système qui serait immédiatement piraté. Les deux avaient raison.
Ethereum a été lancé en 2015 avec deux éléments qui le rendent Turing-complet. Solidity est le langage de programmation permettant d'écrire des contrats intelligents. Il offre des boucles, des conditions, un stockage d'état et des appels de fonctions : tout ce dont vous avez besoin. La machine virtuelle Ethereum exécute ces contrats simultanément sur chaque nœud du réseau. Ensemble, ils permettent aux développeurs de déployer n'importe quel code qu'ils écrivent.
Cette décision explique l'existence de la DeFi, des NFT et des DAO. Elle explique aussi pourquoi des milliards de dollars transitent par des programmes qui ne sont contrôlés par aucune entreprise. Toutes les applications intéressantes dans le domaine des cryptomonnaies, d'Uniswap à Aave en passant par OpenSea, sont possibles grâce à la capacité d'Ethereum à exécuter du code arbitraire.
Mais Vitalik a fait un pari. Il a parié que la flexibilité l'emporterait sur les risques liés à la complexité. Le piratage de la DAO en 2016 a mis ce pari à rude épreuve. Les failles de sécurité dans la DeFi, qui coûtent des milliards chaque année, continuent de le tester. Et la communauté Bitcoin ne cesse de pointer du doigt ces pertes et de dire : « Voilà pourquoi nous avons opté pour la simplicité. » Les deux camps ont raison.
Le problème des arrêts et les raisons des frais d'essence
Voici la partie qui m'a empêché de dormir la première fois que je l'ai comprise.
Dans le même article de 1936, Turing a démontré un fait troublant : aucun algorithme ne peut, à partir d’un programme quelconque, déterminer avec certitude s’il s’arrêtera ou s’il bouclera indéfiniment. Il ne s’agit pas d’un problème technique non résolu, mais d’une impossibilité mathématique. C’est un fait établi. Aucun ordinateur, aussi performant soit-il, ne peut résoudre le problème de l’arrêt pour tous les programmes.
Sur mon ordinateur portable, une boucle infinie est agaçante. J'appuie sur Ctrl+C. Et tout continue. Sur une blockchain, une boucle infinie est catastrophique. Chaque nœud exécute chaque contrat intelligent. Si un seul contrat ne s'arrête jamais, tous les nœuds de la planète qui utilisent cette blockchain se bloquent. Le réseau est hors service.
La solution d'Ethereum est simple mais efficace : le gas. Chaque calcul a un coût en gas. Vous associez du gas à votre transaction. Lorsque le gas est épuisé, le code s'arrête, qu'il soit terminé ou en cours de transfert. Dès que le gas atteint zéro, l'exécution s'interrompt. C'est pourquoi les frais de gas d'ETH varient. Un simple transfert : 21 000 unités de gas. Un swap DeFi complexe : 200 000 unités. La création d'un NFT avec une illustration intégrée à la blockchain : un demi-million. Vous payez en fonction de la puissance de calcul nécessaire à chaque nœud.
Bitcoin a examiné ce problème et a dit « non ». Impossible d'écrire une boucle, impossible de s'y bloquer. Chaque script se termine. Aucun mécanisme de gaz n'est nécessaire. Le langage est trop limité pour exprimer l'infini.
Juin 2016 : quand la théorie s'est concrétisée en réalité à hauteur de 150 millions de dollars
Toute conversation sur la complétude de Turing en cryptographie finit par aboutir à ce moment précis.
La DAO était un fonds d'investissement de 150 millions de dollars fonctionnant sur Ethereum. Contrat intelligent. Gouvernance communautaire : les fonds sont investis, et les votes déterminent leur utilisation. Le code était complexe : boucles, conditions, appels inter-contrats, état évoluant en cours d'exécution. Tout ce que permet la complétude de Turing.
Quelqu'un a trouvé une faille. La fonction de retrait envoyait d'abord l'ETH, puis mettait à jour le solde. L'attaquant a lancé le retrait, a été payé, et avant même que le solde ne soit mis à jour, la fonction s'est appelée elle-même. Et encore. Et encore. Réentrance. Une boucle infinie que les développeurs n'avaient jamais prévue, qui draine l'argent à chaque itération.
Est-ce possible sur Bitcoin ? Non. Un script Bitcoin ne peut pas s'appeler lui-même, ni appeler d'autres scripts, ni créer de boucles. Ce qui rend Bitcoin monotone est précisément ce qui rend cette attaque impossible.
La communauté Ethereum a voté pour une bifurcation dure (hard fork) afin d'annuler le vol. Cette scission a donné naissance à Ethereum Classic. Les développeurs ont tiré des leçons de cette expérience. Les mécanismes de protection contre la réentrance sont devenus la norme. Le modèle « vérifications-effets-interactions » est devenu incontournable. Mais la vérité fondamentale demeure : un code Turing-complet peut toujours contenir des bogues imprévus par ses créateurs. Il ne s'agit pas d'un défaut d'Ethereum, mais d'une conséquence inhérente aux mathématiques.
Bitcoin devient moins restrictif : Taproot et BitVM
La frontière entre les systèmes Turing-complets et Turing-incomplets n'est plus aussi nette qu'auparavant pour le Bitcoin.
Taproot, lancé en novembre 2021, a étendu les possibilités de Bitcoin Script. Il offre une gestion plus complexe des dépenses conditionnelles, une meilleure confidentialité grâce aux signatures Schnorr et des arbres de syntaxe abstraite merkelisés qui masquent les conditions d'une transaction jusqu'à son exécution. Bien qu'il ne soit pas encore Turing-complet, Taproot est plus expressif qu'auparavant.
BitVM, proposé en 2023, va plus loin. Il décrit un système permettant d'effectuer des calculs arbitraires hors chaîne, puis de vérifier le résultat sur Bitcoin. En d'autres termes : les calculs sont effectués ailleurs, et Bitcoin n'intervient que si quelqu'un conteste le résultat. En théorie, cela rend Bitcoin pratiquement Turing-complet pour des cas d'utilisation spécifiques, sans modifier le langage de script lui-même.
J'ai discuté de BitVM avec des développeurs Bitcoin, et leurs réactions sont intéressantes. Ils sont enthousiastes quant aux possibilités offertes, mais terrifiés par les risques. L'un d'eux m'a confié : « Nous n'allons pas précipiter les choses. Des milliards de dollars sont investis dans ce système. Si nous le sabotons en essayant de le rendre plus sophistiqué, personne ne nous le pardonnera. » Cette prudence est frustrante pour ceux qui souhaitent voir apparaître la finance décentralisée Bitcoin dès demain. Elle est rassurante, en revanche, pour ceux qui ont un tel investissement.
L'objectif est indéniablement une plus grande expressivité. Taproot a déjà repoussé les limites du possible. BitVM les repoussera encore davantage. Mais n'espérez pas que Bitcoin devienne Ethereum : leurs cultures sont trop différentes.
Pourquoi toutes les nouvelles blockchains ont-elles opté pour la complétude de Turing ?
Voici ce qui a tranché le débat dans les faits : plus personne ne construit de blockchains Turing-incomplètes. Solana, Cardano, Polkadot, Avalanche, BNB Chain : toutes Turing-complètes et capables d’exécuter des programmes arbitraires. Le marché a tranché : la programmabilité l’emporte. Désormais, la seule question est de savoir comment rendre les systèmes Turing-complets plus rapides, moins chers et plus sûrs.
Chaque blockchain a fait des compromis différents. Ethereum a opté pour l'EVM et Solidity (écosystème le plus vaste, frais les plus élevés sur la couche 1). Solana a développé Sealevel pour l'exécution parallèle avec Rust (rapide mais plus complexe à développer). Cardano a choisi Haskell et la vérification formelle (rigueur mathématique, adoption plus lente). Toutes ont cependant choisi la complétude de Turing car elles souhaitaient exécuter des contrats intelligents, la DeFi, les NFT, les DAO et tout autre système nécessitant une logique personnalisée.
Les problèmes de sécurité sont bien réels. Les failles de sécurité dans la DeFi coûtent des milliards chaque année. Le piratage de la DAO n'était que le début. Mais le secteur a conclu que les avantages de la programmabilité l'emportent sur les risques. Même Bitcoin, la blockchain originale volontairement limitée, évolue vers une plus grande expressivité avec Taproot et BitVM.
Je pratique les cryptomonnaies depuis suffisamment longtemps pour avoir largement utilisé les deux types de blockchains. J'ai effectué des transactions Bitcoin qui ont été confirmées sans faute, comme prévu. J'ai également déployé des contrats intelligents Ethereum qui ont eu des comportements imprévus, car Solidity permet d'écrire du code suffisamment complexe pour nous surprendre nous-mêmes. Ces deux expériences ont façonné mon point de vue.
Le débat porte moins sur la pertinence de la complétude de Turing que sur vos besoins. Si vous souhaitez un système de paiement numérique offrant une sécurité et une prévisibilité maximales, la conception du Bitcoin est pertinente. En revanche, si vous souhaitez développer des applications financières, des jeux, des systèmes d'identité ou tout autre système nécessitant une logique personnalisée, la complétude de Turing est indispensable. La plupart des aspects qui rendent les cryptomonnaies si intéressantes aujourd'hui n'ont été possibles que grâce à un jeune de 19 ans qui a jugé que le risque en valait la peine.
J'y pense à chaque fois que j'utilise Uniswap, Aave ou tout autre protocole DeFi. Chaque échange que j'effectue est du code exécuté sur une machine virtuelle Turing-complète. Chaque transaction comporte le risque théorique qu'un bug imprévu puisse anéantir tout le contrat. J'utilise ces protocoles malgré tout, car leur utilité justifie le risque à mes yeux. Mais je n'oublie jamais que ce risque existe. Et je n'oublie jamais que Bitcoin a choisi une autre voie, une voie qui recèle sa propre sagesse. Le distributeur automatique ne vous vole jamais votre argent. Le chef cuisinier, lui, peut mettre le feu à sa cuisine.
