Se cree el lote salvo que alguien proteste
Un rollup optimista publica un lote y una raíz, y la cadena principal simplemente se lo cree. Nadie comprueba nada salvo que alguien proteste.
Parece arriesgado. Hoy verás por qué basta con un solo verificador honrado, y cómo la cadena principal resuelve la discusión volviendo a ejecutar un único paso.
Al terminar esta lección
Nota
Puedo encontrar por bisección el primer paso erróneo de un lote.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Rollup optimista | un rollup cuyos lotes cuentan como correctos salvo que se impugnen |
| Traza | la raíz antes del lote y después de cada paso |
| Prueba de fraude | la evidencia de que un paso del lote está mal |
| Bisección | encontrar un punto partiendo el rango por la mitad cada vez |
| Ventana de impugnación | el plazo en el que se puede disputar un lote |
| Definitivo | que ya no se puede impugnar |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Una traza muestra dónde se separan
Cada lote tiene una traza: la raíz antes del lote y después de cada transferencia. Un verificador reejecuta los datos publicados y construye su propia traza.
Si las últimas raíces no coinciden, las dos partes están de acuerdo al principio y en desacuerdo al final. En algún punto intermedio está el primer paso donde se separan. La cadena principal solo necesita volver a ejecutar ese paso para ver quién tiene razón.
La bisección encuentra ese paso rápido
Las dos partes comparan sus raíces en el paso del medio. Si coinciden, el fallo está en la segunda mitad. Si no, está en la primera.
Cada pregunta parte por la mitad lo que queda. Dieciséis pasos necesitan cuatro preguntas, mil necesitan diez y un millón, veinte. Los juegos de disputa reales hacen esto en la cadena principal, un movimiento cada vez.
Pilla a un secuenciador que miente
docker exec jupyter python3 steps/dispute.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Ejemplo: lo que imprimió el laboratorio
| Pregunta | Paso preguntado | Respuesta | El paso erróneo está en |
|---|---|---|---|
| 1 | 8 | coinciden | pasos 9 a 16 |
| 2 | 12 | no coinciden | pasos 9 a 12 |
| 3 | 10 | coinciden | pasos 11 a 12 |
| 4 | 11 | no coinciden | paso 11 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Pruébalo: bisección sobre 32 pasos
first_wrong = 21
def agree(i):
return i < first_wrong
good = 0
bad = 32
questions = 0
while bad - good > 1:
middle = (good + bad) // 2
questions = questions + 1
print("pregunta por el paso", middle, "coinciden:", agree(middle))
if agree(middle):
good = middle
else:
bad = middle
print("primer paso erróneo:", bad, "tras", questions, "preguntas")
# Cambia first_wrong a 1 y luego a 32. ¿Cuántas preguntas hacen falta ahora?
Una impugnación tiene que llegar a tiempo
Un lote no puede quedar abierto para siempre, o nadie podría contar con él. Por eso cada lote tiene una ventana de impugnación, a menudo de siete días. Después, el lote es definitivo.
En el laboratorio la ventana es de 50400 slots de 12 segundos, que son 7.0 días. Un lote publicado en el slot 1000 se podía impugnar en el slot 51399, pero no en el 51400.
Mira cómo se cierra una ventana
docker exec jupyter python3 steps/window.pySe muestra aquí y no se ejecuta. Pulsa Iniciar laboratorio para escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que un rollup optimista necesita que la mayoría de los verificadores sean honrados. Basta con uno honrado que vigile a tiempo, porque la cadena principal vuelve a ejecutar ella misma el paso disputado. Lo que sí necesita es que los datos estén publicados y que la ventana sea bastante larga.