Árboles de sintaxis abstracta merkleizados
Fecha: September 7, 2017
Transcripción De: Bryan Bishop
Traducción Por: Blue Moon
Tags: Mast
Categoría: Core dev tech
https://twitter.com/kanzure/status/907075529534328832
Árboles de sintaxis abstracta merkleizados (MAST)
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014932.html
Voy a hablar del esquema que publiqué ayer en la lista de correo, que consiste en implementar MAST (árboles de sintaxis abstracta merkleizados) en bitcoin de la forma menos invasiva posible. Está dividido en dos grandes rasgos de consenso que juntos nos dan MAST. Empezaré con el último BIP.
Esto es la evaluación de la llamada de cola. Podemos generalizar P2SH para darnos capacidades más generales, que un solo script de redimensionamiento. Así que en lugar de comprometerse con un solo script, qué tal si se trata de múltiples scripts. La semántica es súper simple. Todo lo que hace es que cuando se llega al final de la terminación de un script, si la pila no está limpia, lo que significa que hay al menos dos elementos, entonces se recurrirá a la más alta. Esto es lo mismo que hace P2SH… Así que recurrimos a los scripts. There’s two levels of P2SH. Para mantener la seguridad, limitamos la recursión a una evaluación de la llamada de cola.
Para obtener el resto de MAST, tenemos que introducir un nuevo opcode que estoy llamando OP_MERKLEBRANCHVERIFY. Toma 3 argumentos: la raíz, el hash de la hoja y una prueba. Este es el mismo tipo de extensión de opcode que OP_CSV y OP_CLTV. MBV será nop4. Fallará si no hay 3 elementos en la pila. La hoja y la raíz son ambos hashes de 32 bytes. Y el otro tiene que ser una prueba serializada que se especifica en el primer BIP. Comprueba los tipos para ver si pueden ser serializados. Y luego comprobará si estos dos coinciden con la raíz y se asegurará de obtener el valor y fallar o continuar.
Juntas, estas dos capacidades nos dan el MAST generalizado porque podemos construir algo que se parece a esto, donde nuestro testigo se parece a esto. Empujamos la prueba, la prueba merkle. Así que el testigo se ve como arg1..argN y luego [script] y luego [proof].
Testigo: arg1 … argN [script] prueba
Para el reedemScript, queremos copiar el script, capturamos el segundo elemento y lo hashificamos… añadimos el hash de la raíz, y luego MBV. Esto le da capacidades generalizadas de MAST con estas dos características. Después de ejecutar esto, tendremos …. oh, también tenemos que soltar los parámetros de MBV, para hacerlo compatible con el soft-fork.
Canjea el script: OVER HASH256 root MERKLEBRANCHVERIFY 2DROP DROP
Habremos probado que este script fue comprometido en el script original. Dejamos todo lo que hicimos aquí, con la prueba, dejando sólo el script en la pila y los argumentos para pasar a esto, y recurrimos exactamente una vez a este script y hacemos lo que quiera hacer. Podemos generar un contrato complejo y tiene múltiples caminos de ejecución.s Tienes una herramienta que genera cada uno de los posibles caminos de ejecución que te interesan. En el momento de redimir, usted especifica la ruta que desea utilizar, mostrar la ruta, y luego ejecutarlo.
Puedes cegar ciertas vías de código mostrando sólo la que utilizas. O puede hacer algo como árboles clave de sipa en el que se especifica el árbol de merkle de las claves que se desea utilizar, y sólo se sacan las que se quieren utilizar. Merklebranchverify utiliza la mayor parte de la lógica de otro lugar, aunque la haría consensuada. Y la recursividad de la llamada de cola es muy simple porque se limita a ser sólo llamadas de cola. Llegas al final del script, restableces algunas de las variables, ajustas tu script al nuevo script al que estás recursando, y luego realizas un GOTO.
Cuando llega al final de su ejecución, si hay algo todavía en su pila, lo ejecuta. Si hay dos o más. Si vas a través de tu ejecución y encuentras que todavía tienes cosas en tu pila, tomas lo de arriba y lo ejecutas como un script. Esto es seguro porque, en primer lugar no hay scripts por ahí al menos en la mainnet de bitcoin que no tengan cleanstack. No se retransmite por el momento. Eso no es consenso. “Es una regla de consenso para los testigos”. Esto no sería el trabajo en SegWit, correcto. Cuando terminas la ejecución ahora mismo con 2 o más elementos en la pila, lo cual está permitido excepto para SegWit…. cleanstack es una regla de consenso en SegWit, no es sólo una norma. Esto es sólo para v0, por supuesto. Parte del beneficio de esto es que… reduce la necesidad de versionar los scripts. Bueno, eso podría interactuar allí. Al menos sin SegWit, esto es un soft-fork porque cualquier script interesante que se empuje en la pila, excepto un script vacío o una serie de 0 pushes, esto se evaluaría como verdadero.
El guión de redención es parte del testigo. Cómo se evita estar limitado a .. niveles. Uno de ellos es que, la rama merkle, sin CAT o algo que usted no puede conseguir alrededor de él. Pero lo que puedes hacer es que estas estructura de árbol merkle fue diseñada para encadenar llamadas. Puedes sacar un hash del medio y verificar que es parte del siguiente. Y debido a que puedes hacer árboles balanceados de esta manera… y debido a que el caso unario es manejado como un paso a través, puedes tener sólo un paso a través. ¿Qué hay de la recursión de cola log N veces? Bueno, sólo un nivel de profundidad de recursión en la ejecución final. Pero eso probablemente no llegará a bitcoin porque es difícil acotar el cálculo de eso. Pero el tamaño del script será lineal en el… no, OP_DUP y generar datos, puedes hacer un script que se genere a sí mismo y llame a DUP o lo que sea, y siga adelante. Escribe un script que empuje a la pila una copia de sí mismo, y luego ejecutas eso y se ejecuta para siempre. No hay hash en la ejecución en esta propuesta.
La recursividad de cola como modelo de manejo de la recursividad general en los lenguajes basados en la pila, tiene mucho sentido, y requeriría el modelado de costos y probablemente habría scripts de “run-forever” y scripts de “bloat-memory-forever”. Nos salimos con la nuestra en los scripts de bitcoin porque estamos limitados por la no recursividad y la no realización de bucles y podemos casi ignorar el coste del uso de la memoria o de todo, no hay un patrón de opciones que pueda convertirse en un problema. Pero con la recursión sin límites, ese no es el caso. Un nivel de recursión es lo único que necesitas para sacar algo de un árbol hash. Es difícil pensar en un caso de uso en el que quieras la recursión generalizada. ¿Delegabilidad? Si tienes OP_CHECKSIGFROMSTACK, entonces eso resolvería eso. Si tuviéramos un CHECKSIGFROMSTACK esto hace que las cosas de verificación de la rama de merkle sean aún más poderosas donde se puede ejecutar un script y firmado por lo que sea.
¿Cuáles son los problemas con OP_CHECKSIGFROMSTACK? … Podrías hacer convenios, bien con OP_CAT. Aquí hay una moneda que sólo puede ser gastada por una determinada transacción, por lo que podría bloquear una moneda en una cadena.
Si no te importa la explosión exponencial, entonces todo se reduce a “una larga lista de formas de desbloquear esto, elige una”. El aumento exponencial de un árbol de merkle se convierte en un aumento lineal de las formas de desbloquear las cosas, pero sigue siendo un trabajo exponencial para construirlo.
Una de las ventajas de esto sobre bip114 original de jl2012 ((pero ver también) es que, además de estar descompuesto en dos componentes más simples… ir a buscar pubkeys de un árbol, luego tener firmas de árboles clave, también te ayuda a lidiar con el blow-up exponencial cuando empiezas a golpear esos límites, podrías poner más lógica en el script de nivel superior. ¿Qué tan difícil es hacer esto … sacar varias cosas del árbol a la vez, porque hay que compartir. Sí, ese fue uno de los comentarios, es factible, y usted tiene que trabajar en la estructura de la prueba, ya que está destinado a las salidas individuales. En la raíz puedes tener n, que es el número de elementos a sacar. Así que podría ser la prueba de 3 hojas de la raíz. Pero sin saber qué era ese n, básicamente tienes que usarlo como una constante en tu script, la raíz es una constante. Creo que sería interesante tener un n fijo aquí.)
La versión externa es el tipo de hash o explicar lo que los hash son. Así que la historia detrás de esto es que en algún momento estábamos pensando en estos … hashes recuperables que no creo que nadie está considerando seriamente en este momento, pero históricamente la razón para ampliar el tamaño … Creo que mi idea en el momento en que surgió este versionado de testigos, sólo necesitamos 16 versiones allí porque sólo necesitamos el número de versión para qué esquema de hashing utilizar. No quieres poner la versión de hashing dentro del testigo que está limitado por ese hash en sí mismo porque ahora alguien encuentra un error y escribe ripemd160 y ahora hay un ataque de preimagen allí y ahora alguien puede tomar un programa testigo pero reclamar que es un hash ripemd160 y gastarlo de esa manera. Así que, como mínimo, el esquema de hash en sí debería especificarse fuera del testigo. Pero casi todo lo demás puede estar dentro, y no sé qué estructura debería tener, como tal vez un campo de bits de características (no hablo en serio), pero podría haber un campo de bits que tiene los dos últimos se hash, en el programa.
Una de las ventajas del versionado de scripts que hicimos es que en realidad es difícil estar súper seguro de que una implementación de una nueva bandera es realmente un soft-fork. Es más fácil estar seguro de que estas cosas son soft-forks. Mark está diciendo como principio que no fusionamos múltiples cosas no relacionadas, excepto las más razonables. CHECKSEQUENCEVERIFY y CHECKLOCKTIMEVERIFY seguro. Segwit tenía bip147 nulldummy. Pero, por lo general, la combinación de varias cosas no tiene fin y se produce una penalización exponencial en la revisión en la que se dice que hay un montón de características no relacionadas… buena suerte.
No podría hacer un árbol en su esquema no podría hacer una multisig… La serialización de 600 bytes no puede ir en la pila. Cualquier elemento individual en la pila. Hay un push y el push es… … Este árbol más la recursividad de la cola termina con el siguiente script en la pila, por lo que está sujeto al límite de empuje de 510 bytes. Podría estar limitado en v1 o algo así. No puedes empujar algo más grande que eso. Incluso en SegWit, el script de SegWit no se empuja a la pila, sólo está separado. Segwit codifica la pila… no es un script que ejecute nada. El problema no es la prueba, sino el propio script. El script no puede contener todas las pubkeys. Un árbol de 19 de 20 checkmultisig, no se puede poner ese tipo de script para redimir, y esto podría ser arreglado en la v1 o algo así. El límite de 520 bytes para P2SH ha sido un dolor. Sólo puedes llegar hasta 17 de 17 o algo así. Hay razones para no usar… no la responsabilidad, pero también tienes que hacer la configuración por adelantado. Así que si tienes algún script que saca claves de un montón de árboles diferentes, y dice ve a hacer un multisig con eso. Ha sido un límite, pero sería mucho más de un límite, limitado de otras maneras. Ese límite se vuelve más favorable a medida que se introducen otras cosas en el script.
La forma en que las personas que interactúan con esto, como algún escritor de aplicaciones tratando de escribir un script, esto es mucho más complejo que la cosa original de MAST donde sólo tienes una estructura de datos. La gente que trabaja con esto va a tener más dificultades. Alguien debería hacer una propuesta adecuada de cómo es la alternativa.
Merklebranchverify es más útil que generalmente MAST. Esto es una ligera generalización de P2SH y esto es lo que P2SH debería haber sido originalmente. P2SH fue diseñado explícitamente para (¿no?) ser un código nop eval… que trata de qué código será ejecutado. P2SH con hashing especificado por el usuario. Usted hace el hashing, y se encarga de la ejecución, pero sólo un nivel de ejecución al igual que P2SH. El usuario proporciona algún nivel externo de código, y luego proporciona el siguiente nivel. En P2SH estás confinado a sólo ejecutar una plantilla, y esto elimina la plantilla. Con el merklebranchverify se puede hacer uso de esto. Son 3 capas por razones técnicas, por P2SH y por compatibilidad. Si hubiéramos meditado más sobre el P2SH podríamos haber terminado en este diseño de cola recurse también. Es casi indistinguible de P2SH en el sentido de que… si la plantilla de P2SH fuera ligeramente diferente, entonces se podría decir que siempre hizo eso.
El delta de P2SH es que el script sería un DUP, esa es la diferencia. Si P2SH tuviera un DUP delante del hashequalverify y luego ejecutara estas reglas de consenso, entonces simplemente funcionaría, porque P2SH consume el script. O tenía un opcode especial que no elimina realmente la cosa que se hash, entonces sería compatible con esto. Esto sería una reinterpretación de lo que hace P2SH, y haría que P2SH tuviera sentido. … Un script y OP_HASH160 y luego pasar a ella.. Pongo OP_NOP y luego funciona? La gente se queja de la magia de P2SH tipo de sugerir que la gente puede ser confundido así. Hay magia pushonly, derecho.
¿Modo limpio de hacer una salida múltiple para merklebranchverify? Sacar 3 de un árbol de mil. Bastante bien. Usted podría repetir la prueba y hacerlo de nuevo, proporcionar 3 pruebas separadas o algo así. La preocupación con multi-merklebranchverify es la verificación de las secuencias de comandos … pero tal vez no es un problema.
La serialización compacta podría optimizar eso… sólo haciéndolo en el nivel superior. Evita que hagas la operación de recolección y saques 3 elementos, y… No, eso no es cierto. Todavía puedes tener el merklebranchverify como un nopcode para hacer keytreesignatures donde no necesitas hacer recursión. Puedes hacer ambas cosas.
Si utiliza un esquema como bip114, entonces sería menos, porque en la propia salida… y resuelve sobre todo el tema del tamaño del push.
Una vez que usted comprueba la parte superior de la misma, se puede agarrar parte del árbol, y entonces usted puede merklebranchverify y - esto es más como merklebranchget, porque usted ya hizo el verificado. Usted hace una codificación de este donde a partir de un árbol merkle parcial, calcular un hash, y luego hacer GETs en él para ir a obtener elementos del árbol. Usted tiene un opcode que verifica una estructura de datos del árbol merkle podado es lo que usted piensa que es. Sólo hace la verificación en el hash esperado. Y luego obtiene lo que querías del árbol. Así que usted puede hacer la ramificación compartida hacia abajo. Usted toma una prueba, un opcode que toma, entonces usted hace las operaciones para obtener una rama y adjuntar otra rama. Esto es cerca de lo que hace bip114. No estaba claro por qué estaba sacando múltiples cosas, pero esto tiene sentido. Si usted está haciendo múltiples obtiene del árbol de merkle, entonces usted definitivamente quiere compartir los niveles. Si estás sacando dos cosas, entonces la mitad de las veces va a estar en la misma rama izquierda, etc. Y en la práctica estás… y si ordenas intencionadamente tu árbol de forma que lo estén, puedes hacer que tus casos comunes hagan esto de todas formas. Fíjate en que, de nuevo, un sistema que es sólo, reescribamos esa entrada de script como un árbol merkle, podría ser más fácil de implementar, hay casos de borde al final donde puedes comprobar cualquier rama que se proporcionó pero no se podó y nunca se accedió a ella, si es así entonces falla el script y esa es tu regla ((¿qué?)). No estoy entendiendo eso. Con un árbol merkle de serialización en el que tienes ramas podadas y no podadas, la maleabilidad es que alguien tome una rama podada y la haga no podada añadiendo datos extra, lo que podría hacer en algunos casos. Así que quieres deshacerte de la maleabilidad mediante algo como la regla de la pila limpia: si no lo sacaste, … está en la serialización mínima posible para lo que hiciste. La implementación real del árbol puede decir cuántos valores pueden ser… y simplemente llevar la cuenta de eso. El tamaño mínimo de serialización es diferente entre… en este tipo de árboles. O algo es o no es no podado. En la serialización, sólo hay una serialización posible. Es por eso que cleanstack tiene …. y la motivación es prevenir la maleabilidad. Donde un minero no puede añadir basura a su testigo. En un tipo diferente de codificación de serialización para las transacciones, se podría argumentar que la maleabilidad importa porque la cartera puede simplemente tirar eso. Tenemos una maleabilidad residual de los testigos y me gustaría tener un código en la red de retransmisión que autodestruya los testigos. Podría ser un punto de prueba para la maleabilidad por ser un punto de expansión. Por desgracia, es ambas cosas. La maleabilidad es el espacio de expansión del software… El punto intermedio es hacer que las cosas sean prohibidas por la política en lugar de ….
¿Se puede serializar el tamaño del.. en un checksig? Sí. En la v1, probablemente haríamos algo donde el… algo se serializa, como el tamaño de su testigo, algo que no se puede malear más grande.. validar la firma. Y esta idea ha surgido un par de veces en el pasado. Firmar el tamaño de tu firma, esencialmente. La maleabilidad en ambos casos no es un problema, reduce la eficiencia de la retransmisión. La única cosa que podrías hacer es tomar una transacción válida que está siendo retransmitida, y la hago más grande hasta el punto de que es … lo que resulta en la política de rechazos de esa transacción. Segwit mata la recursividad de la llamada de cola debido a cleanstack. En la v1 tal vez podamos cambiar eso. Bueno, ¿y si queremos una recursión general más tarde? Ataque específico aquí… puedes firmar el tamaño, o proporcionar el máximo. El testigo no será más largo que este valor, correcto. Puedes serializar el máximo que usaste. El máximo que usaste cuando firmaste fue de 200 bytes, tu firma podría ser menor, y el verificador necesita saber qué número usar, en el hash. Todo esto de la maleabilidad del testigo es como diferente de…
El proceso de revisión para convertir NOPs en soft-forks es doloroso.
¿Qué es exactamente lo que va en las propuestas de script v1 de bitcoin? ((muchos murmullos/gruñidos))
Podríamos tener un OP_SHA256VERIFY en lugar de OP_SHA256. Para muchas cosas, es conceptualmente… … Si cada operación siempre se verifica, sin no verificaciones, entonces podrías validar los scripts en perfecto paralelo. Tomas cada operación de un script y la validas por sí misma. No necesitas la verificación secuencial. Es malo para la serialización… no puedes hacer eso. Pero si no nos preocupáramos por el ancho de banda y el almacenamiento, entonces sería un mejor diseño.
Si tuvieras un hash256verify aquí en el merklebranchverify… algunos podrían convertirse en OP_DROP. El nopdrop ((risas)). OP_RETURNTRUE, no sólo OP_RETURN. Todos los nopcodes deberían convertirse en OP_RETURNTRUEs. Si se golpea este opcode, entonces se ha terminado para siempre. Esto es una generalización de la versión. La desventaja es que no sabes si has golpeado uno de estos hasta que estás en el script. Esto básicamente te permite tener un árbol merkle donde algunos scripts tienen diferentes versiones en ellos. Esta es una forma de hacer una versión testigo diciendo … mi primer opcode es OP_RETURN15 y 15 no está definido todavía, así que es cierto, y después de definirlo, ahora tiene un significado. Algunos de ellos podrían convertirse en NOPs… No lo llamemos OP_RETURN, debería ser OP_EVIL o OP_VER. Ahora mismo el script que no deserializa nunca es válido, porque no puedes llegar al final. Llega hasta el final, pero tiene un contador de saturación que dice que pase lo que pase, ya he terminado. En DEX, todo es deserialización. Así que tienes tus punteros en un flujo. La ruta de actualización para eso sería la estructura de datos que acabas de deserializar… ¿Qué partes necesitas deserializar si no lo has hecho? OP_RETURN en un scriptsig, devuelve lo que estaría en la parte superior de la pila, lo que sería malo.
No es bueno mezclar código y datos. Se puede hacer un hash de lo que está en la pila y no duplicarlo. La sobrecarga desaparecería. Si no, no necesitarías el gran push en merklebranchverify.
La versión de merklebranchverify en el enlace está encima de Core y eso es un hard-fork por los detalles del testigo. Pero también había uno en elements.git donde hay un RPC de merklebranch y otros. Toma una lista y la convierte en un árbol, pero quiere hacer objetos JSON arbitrarios.
Así que merklebranchverify tal vez debería ser desplegado con la versión no-SegWit.. pero tal vez eso enviaría un mensaje conflictivo a los usuarios de bitcoin. La regla cleanstack de Segwit nos impide hacer esto inmediatamente. Sólo en la v0.
Necesitamos algunos candidatos a soft-forks que sean muy deseados por los usuarios. Tal vez la agregación de firmas, tal vez la sugerencia de luke-jr anti-replay por OP_CHECKBLOCKATHEIGHT propuesta. Sin embargo, tiene que ser muy deseable para el usuario para que se pueda aplicar en este caso concreto. Tiene que ser un pequeño cambio, así que tal vez no la agregación de firmas, pero sí la agregación de firmas, ya que sigue siendo muy deseable.
Pueden romper un CHECKSIGFROMSTACK… en un hard-fork. CHECKBLOCKHASH tiene otras implicaciones, como que las transacciones no son… en el bloque inmediatamente anterior, no se puede reinsertar la transacción, no es reorg-safe. Debería restringirse a unos 100 bloques atrás por lo menos. [a]Apruebo esta violación de la regla de la casa de Chatham
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014932.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014979.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015022.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014963.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/014960.html
https://www.reddit.com/r/Bitcoin/comments/7p61xq/the_first_mast_pull_requests_just_hit_the_bitcoin/
bip98 “Árboles de Merkle rápidos” https://github.com/bitcoin/bips/blob/master/bip-0098.mediawiki
bip116 “MERKLEBRANCHVERIFY” https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki
bip117 “Semántica de la ejecución de la llamada de cola” https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki
implementación de bip98 and bip116 https://github.com/bitcoin/bitcoin/pull/12131
implementación de bip117 https://github.com/bitcoin/bitcoin/pull/12132
https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f