# Le prouveur en flux

> Le prouveur exécute le programme invité deux fois et ne détient jamais la trace d’exécution. La mémoire suit les shards en cours de traitement, et non la longueur de l’exécution, et la preuve ne dépend pas de l’ordonnancement.

Un bloc Ethereum complet représente environ 200 millions de cycles. Sa trace, c’est-à-dire chaque ligne de chaque famille et chaque événement mémoire, occuperait environ 300 octets par cycle : des dizaines de gigaoctets avant même qu’une seule colonne soit engagée. Le prouveur d’Apogee ne la construit jamais. Il exécute le programme invité deux fois et ne détient que les shards sur lesquels il travaille.

## Deux passes

> Figure: Engager, puis prouver. Les défis mémoire doivent suivre les engagements mémoire de chaque shard : les engagements viennent donc en premier, d’une première exécution, et les preuves d’une seconde.

**La passe 1** exécute le programme invité et, à mesure que chaque shard se remplit, engage ses colonnes mémoire, conserve les engagements et abandonne les lignes. À la sortie, elle dérive de l’état final de la mémoire tout le reste dont l’énoncé a besoin : la frontière des registres et du pc, la liste des fenêtres mémoire que l’exécution a touchées, et les shards des familles de fenêtres. Elle exécute ensuite la transcription globale, qui absorbe l’énoncé, chaque engagement mémoire compris, et tire les défis mémoire ainsi que le condensé à partir duquel chaque shard est amorcé.

**La passe 2** exécute de nouveau. L’émulateur est une fonction pure de son entrée : il découpe donc les mêmes shards, et la passe 2 vérifie par assertion que son profil de cycles, sa liste de fenêtres et sa frontière sont ceux de la passe 1. Chaque shard reçoit chacune de ses colonnes engagées et est prouvé : sa transcription, sa passe GKR, son ouverture. Les colonnes mémoire ne sont pas engagées de nouveau : l’ouverture prend leurs engagements dans l’énoncé et leurs valeurs dans la passe 2, si bien que des colonnes qui différeraient d’une passe à l’autre donneraient une ouverture que le vérificateur refuse.

L’ordre est imposé par la solidité (*soundness*). Les défis mémoire doivent suivre chaque valeur que peut lire un tuple mémoire : les colonnes mémoire de chaque shard sont donc engagées avant qu’un shard quelconque puisse être prouvé.

## Le pipeline

Un nombre fixe de fils de travail, `max_in_flight`, partagent un seul verrou autour de l’exécuteur. Sous le verrou, un fil de travail rend son shard terminé et réclame le suivant : un shard rempli s’il y en a un en attente, sinon il fait lui-même avancer l’exécuteur jusqu’à ce qu’un tampon se remplisse. Hors du verrou, il construit les colonnes du shard, le prouve et l’abandonne.

- **L’exécuteur ne devance jamais la demande.** Au plus un shard rempli et non réclamé par famille attend, sous forme de lignes.
- **Au sein d’un shard, le travail est parallèle sur les données**, sur tous les cœurs. Un fil de travail bloqué dans ce travail ne prend pas de second shard.
- **Le bloc ne dépend pas de l’ordonnancement.** La preuve d’un shard est une fonction de l’état global et de ses propres colonnes; les preuves sont placées selon leur position dans l’énoncé. Les octets sont identiques avec 1 et avec 8 shards en cours de traitement.
- **Les échecs sont déterministes.** L’échec renvoyé est le premier dans l’ordre de remplissage, quel que soit le nombre de fils de travail.

## Ce que cela coûte

La mémoire se compose d’un tampon partiel par famille, des tables des derniers accès, des shards en cours de traitement et de la sortie. L’ensemble de travail d’un shard est dominé par sa passe avant, chaque couche GKR interne sous forme d’éléments du corps : 8,4 GiB pour un shard `SHIFT_BITWISE` de `2^20`, 42 GiB pour un shard `KECCAK_F` de `2^18`. Ainsi, **`max_in_flight` borne le nombre de ces ensembles qui coexistent, et les hauteurs fixent la taille de chacun.**

Mesures sur le bloc 257 510 (60 transactions, 101,5 Mgas, 198 millions de cycles, 207 shards) avec 32 vCPU et 247,7 GiB, et douze shards en cours de traitement :

| | |
| --- | --- |
| Passe 1 | 191 s; les remplissages sur un seul fil occupent 81 % de ses shard-secondes; mémoire échantillonnée d’au plus 15,9 GiB |
| Passe 2 | 2 290 s, avec environ 12 shards détenus sur 12 et 30,4 vCPU occupés jusqu’à la sortie du programme invité, puis une phase finale de 460 s |
| Pic de mémoire | 173,92 GiB : les deux shards `KECCAK_F` de `2^18`, ensemble dans la phase finale, sans rien d’autre en cours de traitement |

Le pic est venu de la hauteur d’une seule famille de délégation, et non des douze shards en cours de traitement. C’est là le levier : un bloc avec moins d’appels Keccak, ou avec Keccak à une hauteur inférieure, culmine plus bas.

La spécification : [Le prouveur en flux](https://apogee.gweb3networks.com/docs/auditors/spec/streaming).