Croire le lot sauf objection
Un rollup optimiste publie un lot et une racine, et la chaîne principale le croit, tout simplement. Personne ne vérifie rien, sauf si quelqu’un conteste.
Cela semble risqué. Vous allez voir pourquoi un seul vérificateur honnête suffit, et comment la chaîne principale tranche un désaccord en rejouant une seule étape.
À la fin de cette leçon
Remarque
Je peux trouver la première étape fausse d’un lot par dichotomie.
Mots-clés
| Mot | Ce que ça veut dire |
|---|---|
| Rollup optimiste | un rollup dont les lots sont tenus pour justes sauf contestation |
| Trace | la racine avant un lot puis après chaque étape |
| Preuve de fraude | la preuve qu’une étape d’un lot est fausse |
| Dichotomie | trouver un point en coupant l’intervalle en deux à chaque fois |
| Fenêtre de contestation | le temps pendant lequel un lot peut être contesté |
| Définitif | qui ne peut plus être contesté |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Une trace montre où deux camps divergent
Chaque lot a une trace : la racine avant le lot puis après chaque transfert. Un vérificateur rejoue les données publiées et construit sa propre trace.
Si les dernières racines diffèrent, les deux camps sont d’accord au début et en désaccord à la fin. Entre les deux se trouve la première étape où ils divergent. La chaîne principale n’a qu’à rejouer cette étape pour savoir qui a raison.
La dichotomie trouve vite cette étape
Les deux camps comparent leurs racines à l’étape du milieu. S’ils sont d’accord, la faute est dans la seconde moitié. Sinon, elle est dans la première.
Chaque question coupe en deux ce qui reste. Seize étapes demandent quatre questions, mille en demandent dix et un million vingt. Les vrais jeux de contestation font cela sur la chaîne principale, un coup après l’autre.
Prendre un séquenceur en flagrant délit
docker exec jupyter python3 steps/dispute.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Exemple travaillé : ce que le labo a affiché
| Question | Étape demandée | Réponse | L’étape fausse est dans |
|---|---|---|---|
| 1 | 8 | d’accord | les étapes 9 à 16 |
| 2 | 12 | pas d’accord | les étapes 9 à 12 |
| 3 | 10 | d’accord | les étapes 11 à 12 |
| 4 | 11 | pas d’accord | l’étape 11 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
À vous : une dichotomie sur 32 étapes
premiere_fausse = 21
def d_accord(i):
return i < premiere_fausse
bon = 0
mauvais = 32
questions = 0
while mauvais - bon > 1:
milieu = (bon + mauvais) // 2
questions = questions + 1
print("question sur l’étape", milieu, "d’accord :", d_accord(milieu))
if d_accord(milieu):
bon = milieu
else:
mauvais = milieu
print("première étape fausse :", mauvais, "après", questions, "questions")
# Mettez premiere_fausse à 1, puis à 32. Combien de questions maintenant ?
Une contestation doit arriver à temps
Un lot ne peut pas rester ouvert indéfiniment, sinon personne ne pourrait s’y fier. Chaque lot a donc une fenêtre de contestation, souvent de sept jours. Ensuite, le lot est définitif.
Dans le labo, la fenêtre fait 50400 slots de 12 secondes, soit 7.0 jours. Un lot publié au slot 1000 pouvait être contesté au slot 51399, mais plus au slot 51400.
Regarder une fenêtre de contestation se fermer
docker exec jupyter python3 steps/window.pyAffichée ici, non exécutée. Appuyez sur Démarrer le labo pour la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
On croit souvent qu’un rollup optimiste a besoin d’une majorité de vérificateurs honnêtes. Un seul vérificateur honnête qui surveille à temps suffit, car la chaîne principale rejoue elle-même l’étape contestée. Il faut en revanche que les données aient été publiées et que la fenêtre soit assez longue.