Ces cinq octets, 0x6001600201, font une seule chose dans l'EVM : additionner 1 et 2 et laisser 3 au sommet de la pile. Ils ne référencent aucun registre et n'indiquent pas où ranger le résultat : les deux opérandes se placent implicitement sur la pile, et le résultat y retourne. Toute l'arithmétique et tout le contrôle de flux de l'EVM reposent sur ce modèle.
Les articles précédents ont traité de la machine à états et des comptes ; celui-ci regarde d'un cran vers l'intérieur : de quoi cette machine est faite, comment tourne un cycle d'exécution, d'où viennent les mots de 256 bits et la profondeur de pile de 1 024 éléments, et ce que cette conception de machine à pile achète et ce qu'elle coûte.
Des mots de 256 bits : au service de la cryptographie, pas de l'arithmétique
Le Yellow Paper ne consacre qu'une phrase à la taille de mot : la largeur de mot de la machine (autrement dit la largeur d'un élément de pile) est de 256 bits, ce choix visant à faciliter le hachage Keccak-256 et les opérations sur courbes elliptiques. Développé, cela donne trois raisons concrètes.
La sortie de Keccak-256 fait 256 bits : les hachages comme les clés de stockage n'ont besoin ni d'être tronqués ni d'être étendus. Ethereum signe avec ECDSA sur secp256k1, les clés privées et les composantes de signature tenant dans un espace de 256 bits ; la capacité correspondante côté EVM est fournie par ecrecover, un contrat précompilé à l'adresse 0x01, tarifé à 3 000 gaz. Les adresses font 160 bits, une largeur qui s'aligne naturellement dans un mot de 256 bits.
Il y a ici un problème de précision souvent négligé : le Keccak-256 utilisé par Ethereum n'est pas le SHA3-256 issu de la normalisation NIST. Les deux ont la même largeur de sortie et la même fonction de permutation, mais diffèrent par l'octet de séparation de domaine du remplissage : le Keccak d'origine utilise 0x01, SHA3-256 utilise 0x06. Pour une vérification de hachage, il faut choisir une bibliothèque explicitement étiquetée Keccak-256 ; avec SHA3-256, le résultat est totalement différent.
Le coût de la largeur de mot est tout aussi net. Toute l'arithmétique s'effectue modulo 2^256 : un débordement boucle silencieusement, sans lever d'exception ; une valeur booléenne occupe elle aussi 32 octets pleins ; calldata et slots de stockage sont alignés sur 32 octets, et les types courts doivent être compactés au niveau de l'encodage — c'est exactement ce que fait le storage packing de Solidity (voir l'article 0.19 de la même série, « Storage Layout : comment les variables d'état de Solidity atterrissent dans les slots »). La sémantique de bouclage est en outre à l'origine de nombreuses failles historiques de dépassement d'entier. Depuis Solidity 0.8, des vérifications sont insérées par défaut et un revert via Panic(0x11) a lieu : c'est un correctif au niveau du langage, l'EVM lui-même n'ayant pas changé.
L'état de la machine : ce que gèrent respectivement la pile, la mémoire et le compteur de programme
Le Yellow Paper décrit l'état de la machine par un sextuplet μ = (g, pc, m, i, s, o) : gaz disponible, compteur de programme, contenu de la mémoire, nombre de mots de mémoire actifs, contenu de la pile, et tampon de données de retour. Les rôles des quatre composants se lisent côte à côte :
| Composant | Adressage et unité | Portée de vie | Coût en gaz associé |
|---|---|---|---|
| Pile (stack) | Seul le sommet est visible, 256 bits par élément, 1 024 éléments au maximum | Un seul cadre d'appel | 2 à 3 gaz pour l'opcode lui-même |
| Mémoire (memory) | Adressée par octet, extension par mots de 32 octets | Un seul cadre d'appel, un nouveau cadre part de zéro | 3a + ⌊a²/512⌋, où a est le nombre de mots actifs |
| Compteur de programme (PC) | Décalage en octets dans le code | Un seul cadre d'appel | JUMP 8 gaz, JUMPI 10 gaz, JUMPDEST 1 gaz |
| Compteur de gaz | Gaz disponible, un entier non négatif | Toute la transaction ; le gaz restant est transféré entre cadres d'appel selon les paramètres d'appel | Chaque instruction est débitée selon la table de frais |
La pile (stack) est la seule zone d'opérandes implicite. Elle n'expose que son sommet : la grande majorité des instructions y dépilent leurs arguments et y empilent leur résultat, les éléments intermédiaires restant invisibles pour les instructions. Sa limite est de 1 024 éléments de 256 bits chacun.
La mémoire (memory) est adressée par octet, toutes ses positions valent zéro au départ, et elle est accessible via MLOAD/MSTORE (lecture-écriture par mots de 32 octets) et MSTORE8 (écriture d'un seul octet). Son coût est dynamique : l'extension est facturée au nombre de mots actifs, la formule donnée par le Yellow Paper fixant le coût mémoire total à 3a + ⌊a²/512⌋ gaz pour a mots occupés ; le terme quadratique fait qu'accéder à un décalage énorme épuise directement le gaz. Il n'existe donc pas de grand tableau gratuit dans la mémoire de l'EVM, ni de problème de « lecture de données non initialisées » : les positions jamais écrites valent toujours 0.
Le compteur de programme (program counter, PC) est le décalage en octets de la prochaine instruction dans le code. Le contrôle de flux ne peut être modifié que par JUMP/JUMPI, et le Yellow Paper définit l'ensemble des cibles de saut valides comme les positions où apparaît l'instruction JUMPDEST dans le code. Cet ensemble est donc énumérable statiquement, et l'exécution ne peut pas calculer une adresse arbitraire pour y sauter. Cette contrainte est le fondement de l'analyse de flux de contrôle hors ligne.
Le code lui-même n'est pas placé dans la pile, la mémoire ou le stockage. Le Yellow Paper précise explicitement que la machine ne suit pas l'architecture de von Neumann et que le code réside à part, dans une mémoire morte virtuelle accessible uniquement par des instructions dédiées. Le code d'un contrat déployé ne peut donc pas se réécrire lui-même, et il est impossible de remplacer le flux d'instructions en cours d'exécution. Le stockage et la mémoire sont mutables ; le code ne l'est pas.
Extraction, décodage, exécution : un tour de boucle
Le Yellow Paper définit « l'instruction à exécuter » par une fonction par morceaux : si le compteur de programme est inférieur à la longueur du code, l'instruction est l'octet à cette position ; sinon, l'instruction équivaut à STOP. Autrement dit, lire au-delà de la fin du code ne constitue pas une erreur : la spécification définit ainsi une fin naturelle.
Pour exécuter une instruction, il faut d'abord connaître trois choses : combien d'éléments elle dépile (δ), combien elle empile (α), et combien de gaz elle consomme (fonction de coût C). Ces trois quantités sont déterminées par l'instruction elle-même et figurent dans la ligne correspondante de la table des opcodes. La boucle peut alors s'écrire comme suit, en omettant le substate, l'access list et les remboursements de gaz :
# Boucle d'exécution simplifiée, qui conserve l'ordre des vérifications de la spécification
pc, gas, stack, memory = 0, gas_limit, [], bytearray()
while True:
# Extraction : dépasser la fin du code équivaut à STOP
op = code[pc] if pc < len(code) else STOP
# Décodage : la table donne le nombre de dépilements, d'empilements et le coût
delta, alpha, cost = OPCODE_TABLE[op]
# La validation précède l'exécution : gaz insuffisant, pile trop courte et débordement de pile arrêtent tous l'exécution de façon exceptionnelle
if gas < cost or len(stack) < delta or len(stack) - delta + alpha > 1024:
raise ExceptionalHalt()
gas -= cost
# Exécution : prendre les opérandes au sommet de la pile et y repousser le résultat
args = [stack.pop() for _ in range(delta)]
stack.extend(dispatch(op, args, memory, pc))
# Le PC avance ; les instructions de la famille PUSH sautent en plus l'immédiat qui les suit
pc += 1 + immediates(op)
Les commentaires correspondent à trois endroits faciles à se tromper : la sémantique d'extraction au-delà de la fin, la validation qui doit précéder l'exécution, et l'immédiat d'un PUSH qui occupe de l'espace dans le code.
Le dernier point mérite d'être développé. PUSH1 à PUSH32 encodent la constante directement après l'opcode, si bien que PUSH1 0x2a occupe deux octets. D'où une conséquence contre-intuitive : dans un bytecode, chaque octet n'est pas une instruction, et un balayage des cibles de saut doit reconnaître et sauter les données immédiates, sous peine de prendre un octet d'une constante pour un JUMPDEST.
Détailler les cinq octets 60 2a 60 5b 56 rend la chose plus claire. 60 2a est une instruction portant un immédiat ; le deuxième octet de 60 5b est la constante 0x5b, dont la valeur est exactement celle de l'opcode JUMPDEST, mais ce n'est pas une instruction ; 56 est le JUMP. Pour balayer les cibles de saut valides, il faut d'abord reconnaître 0x60 puis sauter l'octet qui suit. La règle n'est pas compliquée en soi ; elle exige simplement que toute implémentation faisant de l'analyse de flux de contrôle calcule correctement la longueur des PUSH, faute de quoi l'ensemble des cibles est pollué par des octets de constantes.
Cela explique aussi pourquoi un 0x5b dédié est nécessaire comme marqueur de saut, plutôt que d'autoriser un saut vers n'importe quel décalage.
Sous-débordement et débordement de pile : deux exceptions, un même dénouement
La fonction d'arrêt exceptionnel Z du Yellow Paper énumère toutes les conditions qui interrompent immédiatement l'exécution ; deux d'entre elles concernent la pile : moins d'éléments sur la pile que l'instruction ne veut en dépiler, soit le sous-débordement (stack underflow) ; et une hauteur de pile supérieure à 1 024 après exécution, soit le débordement (stack overflow).
Les deux suivent la même voie : arrêt exceptionnel, consommation de tout le gaz restant, et abandon de tous les changements d'état dans le cadre d'appel courant. Les vecteurs de test normatifs de l'EIP-3855 en donnent un contraste net : 1 024 PUSH0 consécutifs s'exécutent avec succès, 1 025 s'arrêtent sur un débordement de pile.
Il faut distinguer ce cas d'une autre forme d'« échec ». L'instruction REVERT (0xfd, depuis Byzantium, EIP-140) annule elle aussi les changements d'état, mais ne consomme pas le gaz restant et peut renvoyer à l'appelant une portion d'octets de la mémoire comme données d'erreur. L'échec d'un require de Solidity se compile généralement en REVERT : le message d'erreur remonte à l'appelant et le gaz restant n'est pas consommé. Un sous-débordement de pile est en revanche une exception dure, qui se manifeste au débogage par un gaz épuisé et l'absence de données de retour. Dans la pratique du débogage, une transaction qui brûle tout son gaz sans renvoyer de données vient souvent d'un bytecode tombé sur une exception dure, la quantité de calcul n'étant pas nécessairement élevée.
La limite doit elle aussi être claire : si REVERT manque lui-même de gaz, ou s'il rencontre un sous-débordement de pile en s'exécutant, il dégénère en exception ordinaire et consomme pareillement tout le gaz.
Ce que la machine à pile apporte : réduire la complexité d'implémentation au minimum
L'explication d'ethereum.org est que la structure de pile est l'architecture privilégiée des machines virtuelles parce qu'elle est facile à implémenter, ce qui réduit la probabilité de bugs et de failles de sécurité. Cet apport peut se décomposer en plusieurs points.
Un décodeur minimal. L'opcode tient sur un octet et la position des opérandes est implicitement déterminée par l'ordre de la pile : le bytecode n'a pas à encoder de numéro de registre pour chaque instruction. Hormis les instructions de la famille PUSH, qui portent un immédiat, la longueur des instructions est fixe ; décoder revient à une consultation de table.
Il n'y a pas de couche d'allocation de registres dans la spécification. La stratégie d'allocation est par nature une liberté du compilateur ; dès qu'elle entre dans la spécification d'une machine virtuelle, elle devient un comportement que toutes les implémentations doivent reproduire bit à bit. La machine à pile retire de la spécification la question du « où placer les valeurs », et la description d'état à figer par le consensus s'en trouve réduite.
Les sémantiques des opérations sur la pile se définissent presque indépendamment les unes des autres, les coûts en gaz peuvent être attachés directement aux opcodes, et l'espace de recherche de l'analyse statique, du fuzzing et de la vérification formelle est plus petit. C'est l'une des raisons pour lesquelles l'EVM peut compter plusieurs implémentations indépendantes (geth, revm, evmone, etc.) restant cohérentes au niveau de l'octet.
Le coût de la machine à pile : DUP, SWAP et l'absence d'accès aléatoire
Le prix à payer pour une pile qui n'expose que son sommet se lit dans le nombre d'instructions du bytecode.
Pour utiliser un élément proche du sommet, on peut le copier au sommet avec DUP1 à DUP16, ou l'y amener avec SWAP1 à SWAP16. Seize est une limite dure : si l'élément à copier se trouve à la 17e position, il faut d'abord le ramener à portée de copie avec un SWAP16 ou équivalent avant de poursuivre, et plus la pile est profonde, plus la chaîne de manipulations s'allonge. Un même calcul qui tiendrait souvent en une instruction sur une machine à registres se déploie ici en une séquence d'empilements, de copies, d'échanges et de dépilements.
Un scénario concret : un contrat doit calculer f(a, b, c, d), et d se trouve à la 4e position de la pile. Une machine à registres peut référencer directement le registre contenant d ; sur une machine à pile, le compilateur doit soit copier d à l'avance plus près du sommet, soit le faire remonter avec la famille SWAP avant l'appel puis le redescendre ensuite. C'est pourquoi le compilateur Solidity génère beaucoup de ces instructions de réarrangement lorsque les fonctions ont de nombreux paramètres.
Le compilateur doit en outre maintenir l'équilibre de la pile. La hauteur de pile à la fin de chaque bloc de base doit être prévisible, sans quoi le code situé après un saut ne peut plus localiser ses opérandes. Solidity effectue donc une planification de pile dédiée à la compilation, insérant des DUP, des SWAP et des POP pour déplacer les opérandes lorsque paramètres et variables locales sont nombreux. Ces instructions ne sont pas chères en elles-mêmes — la plupart relèvent du palier à 3 gaz — mais elles allongent le chemin d'exécution de l'interpréteur.
Ce qu'une machine à pile coûte de plus qu'une machine à registres trouve un point de comparaison indirect dans la JVM. Davis et al. ont traduit du bytecode JVM vers une machine à registres virtuelle et rapportent un arbitrage entre baisse du nombre d'instructions exécutées et hausse du nombre d'extractions de bytecode (Davis et al., 2003). Ce rapprochement vient de la JVM et n'est pas transposable directement à l'EVM : il mesure le coût de dispatch de l'interprétation, alors que la tarification en gaz de l'EVM a déjà externalisé l'essentiel de ce coût. Une seule conclusion directionnelle en ressort : pour un même calcul, une machine à pile demande généralement plus d'instructions exécutées, une machine à registres échange davantage d'extractions contre moins d'instructions exécutées.
Les concepteurs de l'EVM ont accepté ce coût en échange d'une implémentation simple et d'une spécification déterministe. Ces dernières années ont aussi apporté de petites améliorations incrémentales, par exemple PUSH0 (EIP-3855, Shanghai), qui remplace le PUSH1 0x00 de 2 octets et 3 gaz par une instruction de 1 octet et 2 gaz.
Dans quelles conditions cette conception devient un fardeau
Lorsque les expressions sont profondément imbriquées et les fonctions riches en paramètres, la part des instructions de réarrangement de pile augmente, et la consommation de gaz à l'exécution du contrat grimpe avec elle. Côté largeurs, l'EVM ne propose pas de types natifs de 8, 32 ou 64 bits : tout doit être tronqué ou masqué explicitement, ce qui demande une attention particulière lors d'un portage entre langages.
La profondeur de pile est de 1 024, mais ce 1 024 n'est pas le 1 024, souvent confondu, de la définition de CALL/CREATE, où le Yellow Paper limite de la même façon la profondeur d'appel à 1 024. Le premier borne le nombre d'opérandes dans un cadre, le second la longueur de la chaîne d'appels ; heurter le premier est un bug de programme, heurter le second signale généralement une récursion mal écrite.
Une dernière frontière à tracer : la machine à pile n'est pas un obstacle à l'exécution parallèle. Le parallélisme doit traiter les conflits de lecture-écriture sur un état global mutable, alors que la position d'un opérande dans la pile est implicitement déterminée par l'ordre de la pile — une question sans rapport avec la détection de conflits ou le déterminisme de l'exécution. La véritable contrainte se situe au niveau de l'état, et relève des articles suivants.
Sources
- Ethereum Yellow Paper (le sextuplet d'état de la machine, la limite de pile de 1 024, la formule de coût mémoire, l'ensemble des cibles JUMPDEST, la fonction d'arrêt exceptionnel Z, la table des frais de gaz et la table des opcodes, la tarification du précompilé ECREC) : https://ethereum.github.io/yellowpaper/paper.pdf
- ethereum.org, Ethereum Virtual Machine (EVM) (profondeur de pile de 1 024, relation entre mots de 256 bits et Keccak-256 / secp256k1) : https://ethereum.org/developers/docs/evm/
- ethereum.org, Understanding the Yellow Paper's EVM Specifications (machine à pile facile à implémenter donc moins sujette aux défauts, raisons du choix des mots de 256 bits) : https://ethereum.org/developers/tutorials/yellow-paper-evm/
- Keccak Team, Keccak specifications summary (les bits de suffixe 0x06 de SHA3-256 et le processus de remplissage) : https://keccak.team/keccak_specs_summary.html
- Keccak Team, The Keccak reference, version 3.0 (le remplissage multi-débit pad10*1 du Keccak d'origine) : https://keccak.team/files/Keccak-reference-3.0.pdf
- NIST, FIPS 202 (remplissage SHA-3 0x06) : https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
- EIP-3855, PUSH0 instruction (0x5f, 2 gaz, vecteurs de test à 1 024 et 1 025 PUSH0) : https://eips.ethereum.org/EIPS/eip-3855
- EIP-140, REVERT instruction (annule les changements d'état sans consommer tout le gaz restant, et la limite où il dégénère en exception) : https://eips.ethereum.org/EIPS/eip-140
- Davis, Beatty, Casey, Gregg, Waldron, The Case for Virtual Register Machines, 2003 (traduction du bytecode JVM vers une machine à registres virtuelle, avec baisse du nombre d'instructions exécutées et hausse du nombre d'extractions de bytecode) : https://mural.maynoothuniversity.ie/id/eprint/10191/1/KC-Case-2003.pdf
- Solidity 0.8.0 Release Announcement (vérification par défaut des opérations arithmétiques, revert via Panic(0x11)) : https://www.soliditylang.org/blog/2020/12/16/solidity-v0.8.0-release-announcement/
- ethereum/execution-spec-tests (tests normatifs de PUSH0 et du débordement de pile) : https://github.com/ethereum/execution-spec-tests