# Récursion et règlement

> Comment une preuve de base de centaines de shards devient une seule preuve Groth16 que vérifie un contrat. Apogee qui prouve son propre vérificateur, les bandes qui rendent cela peu coûteux, la transcription chaînée à travers un arbre, et des couplages repliés jusqu’à ce qu’il n’en reste qu’un.

La preuve de base d’un bloc Ethereum se compose de 207 preuves de shards : 14,5 MB, chaque shard étant une preuve GKR accompagnée de ses engagements et d’une ouverture Mercury qui se termine par une vérification de couplage. Un contrat ne peut rien vérifier de tout cela directement. La récursion la compresse, et la façon dont elle le fait est le choix de conception le plus lourd de conséquences après le moteur GKR lui-même.

## La preuve de base reste intacte

La première décision porte sur ce que la récursion ne fait *pas*. Aucune clé, aucun énoncé ni aucune preuve de base ne change pour rendre la récursion possible : une feuille vérifie les shards de base exactement comme le ferait un vérificateur natif. Tout ce dont la récursion a besoin est ajouté au-dessus de la preuve de base, jamais à l’intérieur. Un bloc peut être vérifié en natif, passé par la récursion, ou les deux, à partir des mêmes octets.

## Apogee prouve son propre vérificateur

Un **nœud** de l’arbre, c’est Apogee qui prouve un programme vérificateur. Une **feuille** vérifie une suite de shards de base consécutifs, de `from` à `to`; un **nœud** interne vérifie de deux à quatre enfants, chacun étant une preuve complète d’un programme feuille ou nœud; la **racine** couvre tous les shards de base. Chaque nœud est prouvé par le même prouveur en flux qu’un bloc de base.

Exécuter le vérificateur Rust sous forme d’instructions RISC-V fonctionnerait, et la mesure a donné 3,0 milliards de cycles pour les 207 shards d’un bloc : quinze fois le bloc lui-même. Les nœuds s’exécutent donc plutôt dans un **format de récursion**.

## Le format de récursion

Un énoncé est au format de récursion exactement quand son programme déclare des familles de corps. Le format ajoute un espace d’adressage et quatre familles de coprocesseurs qui opèrent sur cet espace, toutes invoquées par l’ABI de délégation ordinaire, et ne change rien d’autre :

| Famille | Une ligne est |
| --- | --- |
| `FIELD_WINDOWS` | une **cellule de corps** : une cellule mémoire qui contient un élément `Fr` entier, dans le même multiensemble mémoire que la RAM |
| `FR_OP` | une opération de corps sur des cellules : multiplication, addition, soustraction, multiplication-accumulation, inversion, assertion d’égalité, et étapes de construction de constantes |
| `P2_FIELD` | une étape duplex Poseidon2 sur des cellules, si bien qu’une transcription s’exécute à raison d’une ligne par permutation |
| `FIELD_IO` | huit mots de RAM vers une cellule, ou une cellule vers huit mots |
| `FQ_OP` | une opération dans le corps de base de BN254, chaque élément tenant en quatre cellules de limbs de 64 bits, si bien que l’arithmétique de courbe s’exécute à raison d’une ligne par opération de corps |

Deux autres changements rendent un shard de récursion moins coûteux à vérifier pour son parent. Ses colonnes mémoire et témoins sont engagées sous forme d’**empilements** d’au plus `2^24` évaluations : un parent replie donc une poignée de points au lieu de centaines. Et une demande de récursion écrit la base de son cadre avancée au-delà du cadre, si bien que des cadres placés bout à bout se rejouent sous forme d’`ecall` consécutifs, à raison d’une ligne par appel.

## Bandes

Les vérifications d’un shard ont une forme fixe pour sa famille et sa hauteur. L’hôte les compile donc, une fois pour toutes, en une **bande** : une liste séquentielle d’appels de coprocesseur sur des cellules absolues, dans laquelle rien ne bifurque selon une valeur. La bande d’un shard reprend, appel pour appel, les étapes du vérificateur natif pour ce shard : la transcription du shard, la passe arrière GKR, les vérifications de lookup et de racines, et les douze scalaires de l’ouverture Mercury. Chaque vérification est une assertion d’égalité.

Les bandes, les gabarits de repliement et les constantes de chaque programme de récursion sont construits à la compilation par la crate du vérificateur elle-même, et placés dans les données en lecture seule du programme. L’identité du programme lie donc chaque bande que le programme rejoue : prouver qu’un nœud a exécuté son programme, c’est prouver qu’il a exécuté exactement ces vérifications.

## Une transcription chaînée à travers l’arbre

La transcription globale de l’énoncé de base est une seule éponge sur l’énoncé entier. L’arbre la découpe sans la modifier. Le nœud qui détient le shard 0 exécute le préfixe, jusqu’au condensé de l’entrée publique inclus; chaque nœud absorbe les engagements mémoire de ses propres shards, en repartant de l’état qu’a laissé son prédécesseur; le nœud qui détient le dernier shard exécute le suffixe et tire les défis mémoire que chaque nœud avait pris comme affirmations. Le journal d’un nœud enregistre l’état de la chaîne aux deux extrémités de sa plage, et un parent exige que les états de ses enfants se rejoignent.

Un nœud astreint aussi ses enfants les uns par rapport aux autres : statut de sortie 0, un seul énoncé de base (sa forme, son condensé, ses défis, le condensé de l’entrée et du journal, le statut de sortie et le nombre de shards), des plages de shards adjacentes, des états de chaîne qui se rejoignent, des fenêtres temporelles dans l’ordre de part et d’autre de la jointure, et les identités des programmes de récursion. Un nœud qui détient un énoncé entier établit l’argument de mémoire.

## Replier les couplages

Aucun nœud ne calcule de couplage. La vérification Mercury de chaque shard est différée sous forme de douze entrées `(side, scalar, point)`; après la bande du shard, la transcription propre au nœud absorbe l’état final de la transcription du shard et tire des poids, et chaque entrée est ajoutée, pondérée, à une seule paire de points cumulative `(A, B)` qui représente l’affirmation `e(A, [1]_2) = e(B, [x]_2)`. La vérification de lot qui rattache l’engagement combiné d’un shard à ses colonnes est repliée à côté. Les points que partagent tous les shards d’une famille, comme `[1]_1` et les engagements de mise en place, accumulent chacun un seul scalaire et n’entrent qu’une fois. Le `(A, B)` d’un enfant entre sous un poids tiré après son journal entier.

Chaque côté est une seule multiplication multi-scalaire sur `FQ_OP`, exécutée selon un gabarit statique : Pippenger avec des chiffres de 8 bits sur des moitiés GLV, chaque point étant astreint à la courbe, chaque étape fixée à l’avance. Un point coûte environ 400 appels `FQ_OP`.

À la racine, le contenu entier de l’arbre s’est contracté : chaque shard de base vérifié, la transcription exécutée de bout en bout, l’argument de mémoire établi, et chaque ouverture repliée en une seule affirmation de couplage. Il reste cette affirmation et deux identités de programme.

## Le décideur

La racine reste une preuve GKR accompagnée de quelques centaines de points, ce qu’un contrat ne peut pas vérifier. Le **décideur** est un circuit Groth16 qui exécute la procédure de nœud sur un seul enfant, la racine, au moyen d’un pilote écrivant des contraintes de rang 1 au lieu d’appels de coprocesseur, et qui astreint le journal de la racine à toute la plage des shards de base. Il ne replie rien : chaque point que la racine doit au couplage final, avec son scalaire, devient un **fil lié**, une valeur que détient le vérificateur, engagée dans la preuve sous une cinquième trappe plutôt que passée comme entrée publique. Il en va de même des deux identités, du statut de sortie de base, ainsi que de l’entrée publique et du journal de base, octet par octet.

Le Groth16 d’Apogee diffère de celui des manuels sur trois points : l’engagement des fils liés, l’absence d’aveuglement, et une clé de preuve sur la base de Lagrange que publie déjà la cérémonie des puissances de tau. Sa clé provient d’une cérémonie en deux phases : la phase 1 est le même fichier de cérémonie que celui sur lequel reposent les engagements; la phase 2 est propre au circuit, les contributions à `α` et à `β` étant achevées avant toute contribution à `γ`, `δ` et `η`, un ordre qui fait lui-même partie de la solidité (*soundness*).

`ApogeeVerifier.sol` reconstruit les valeurs liées à partir du calldata, vérifie l’équation de Groth16, replie les points des deux côtés avec `ecMul` et `ecAdd`, ce qui astreint aussi chaque point à la courbe, et vérifie l’unique couplage restant. Son constructeur fixe la clé, les deux points G2 de la cérémonie et les identités des deux programmes de récursion. Un déploiement sert un seul programme de base, une seule forme de racine et des longueurs de valeurs publiques fixes.

## Mesures

Bloc 257 510, avec l’arbre sur une machine à 32 CPU, et la cérémonie et le décideur sur un portable à 18 cœurs :

| | |
| --- | --- |
| Preuve de base | 207 shards, 14,5 MB, 2 481 s |
| Arbre | 4 feuilles d’au plus 64 shards de base et une racine : 116 shards en tout |
| Feuilles, quatre à la fois | 21, 24, 23 et 27 shards; 2 157 s; pic de 92 GiB |
| Racine | 21 shards, 460 s, 1,03 MB |
| Décideur | 7 896 686 contraintes; preuve en 18,5 s et 6,1 GB |
| Contrat | 358 points; 3 620 026 gas; 34 980 octets de calldata |

La spécification : [Récursion et décideur](https://apogee.gweb3networks.com/docs/auditors/spec/recursion). Pour l’exécuter vous-même : [Régler sur la chaîne](https://apogee.gweb3networks.com/docs/launch/on-chain).