Plus facile à lire avec un fond crème, une teinte, plus de contraste ou un texte plus grand ? Choisissez vos couleurs et votre texte, une fois pour toutes les pages.

Leçon gratuite

Rollups optimistes et preuves de fraude

Après cette leçon: Je peux trouver la première étape fausse d’un lot par dichotomie.

Leçon de 70 min2 commandesLab de rollups : lots, preuves de fraude, disponibilité des données et sorties en Python

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

MotCe que ça veut dire
Rollup optimisteun rollup dont les lots sont tenus pour justes sauf contestation
Tracela racine avant un lot puis après chaque étape
Preuve de fraudela preuve qu’une étape d’un lot est fausse
Dichotomietrouver un point en coupant l’intervalle en deux à chaque fois
Fenêtre de contestationle temps pendant lequel un lot peut être contesté
Définitifqui 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

Commande
docker exec jupyter python3 steps/dispute.py

Affiché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éeRéponseL’étape fausse est dans
18d’accordles étapes 9 à 16
212pas d’accordles étapes 9 à 12
310d’accordles étapes 11 à 12
411pas d’accordl’étape 11

Les cellules que les étudiants remplissent restent vides dans cet aperçu.

À vous : une dichotomie sur 32 étapes

Code: python
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

Commande
docker exec jupyter python3 steps/window.py

Affiché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.

À propos de ce labo et de sa source: Lab de rollups : lots, preuves de fraude, disponibilité des données et sorties en Python

Vous enseignez à une classe ? Proposez ce module à vos étudiants avec un guide de l'enseignant, des devoirs corrigés et un laboratoire pour chaque étudiant.