Utreexo: hash-based accumulator for bitcoin UTXOs
Oradores: Tadge Dryja
Fecha: June 6, 2019
Transcripción De: Bryan Bishop
Traducción Por: Blue Moon
Tags: Utreexo
Utreexo: acumulador basado en hash para UTXOs de bitcoin
http://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2018-10-08-utxo-accumulators-and-utreexo/
http://diyhpl.us/wiki/transcripts/mit-bitcoin-expo-2019/utreexo/
Documento Utreexo https://eprint.iacr.org/2019/611.pdf
https://github.com/mit-dci/utreexo
https://twitter.com/kanzure/status/1136560700187447297
Introducción
Sigues descargando todo; en lugar de escribir en tu base de datos UTXO, modificas tu acumulador. Aceptas una prueba de que está en el acumulador UTXO, tú mismo la pones ahí, simplemente ya no la recuerdas. El resultado final es que almacenas menos de un kilobyte en lugar de 4 GB o así. Pero el inconveniente es que necesitas todas esas pruebas. En el peor de los casos, las pruebas básicamente duplican el tamaño de la descarga. Si haces IBD y no tienes caché, va a estar cerca de 500 GB para IBD. Pero es una curva bastante pronunciada que si tienes unos cientos de megas para RAM y caché, los datos extra bajan significativamente. Una vez que estás sincronizado, el almacenamiento en caché no ayuda tanto. Los datos extra en estado estable acaban siendo el doble. Cuanto más tiempo sigas corriendo, menos sobrecarga tendrás si tienes suficiente memoria porque tus compañeros pueden recordar pruebas superpuestas. Estos son árboles Merkle gigantes, y hay cierta superposición. Pero esto es complejo porque tienes que tener mucho estado para cada peers. Es como bloques compactos, en que tienes que recordar lo que enviaste a cada persona.
Por lo tanto, estoy trabajando en ello, y estoy interesado en cómo hacer esto. Me dijeron que simplemente hiciera un pull request a Bitcoin Core. No se. Tengo algunos números de prueba en golang. No está en C++. Básicamente entra en la carpeta bitcoin/blocks/ y sólo lee todos los bloques y simula un IBD con eso. A largo plazo creo que utreexo es genial y podría ser puesto en Bitcoin Core como una opción. Pero esto es un gran cambio, así que tal vez debería mantenerse por separado. Así que no sé.
Preguntas y Respuestas
P: ¿Cuál es la velocidad de validación de las pruebas? ¿Números de rendimiento?
R: Todavía no lo he acoplado a la verificación de firmas. Pero super vagamente, solo viendo en este ordenador regular Bitcoin Core hace IBD en 6 horas. No me lleva tanto tiempo hacer mi simulación. Además mi simulación sigue siendo single core. En teoría, no debería haber mucha penalización de tiempo, porque estás haciendo algo así como 8 billones de operaciones hash a lo largo del proceso de descarga inicial de bloques (IBD).
La gente ha estado hablando de libconsensus desde siempre, pero es difícil porque leveldb se convierte en parte de él cuando profundizas en él. Pero aquí, esto podría ser algo que podría separarse.
Pero aquí, esto podría ser algo que podría separarse.
P: ¿Quién crea las pruebas?
R: Ahora mismo, se necesitan nodos puente que puedan crear las pruebas. A largo plazo, nunca va a ocurrir, pero parece que es responsabilidad del monedero que si tienes un UTXO guardes tu propia prueba. Pero eso no va a suceder realmente, conseguir que la gente haga eso. Hace un año, sipa estaba preguntando, todas estas ideas para aplastar el conjunto UTXO todos mueren porque se necesita un nodo puente para vincular estas redes p2p. Una de estas redes p2p va a necesitar pruebas pegadas a las transacciones, y las otras no tendrán ni idea. Así que tienes que buscar las entradas, buscar las pruebas, adjuntarlas y reenviarlas. En este diseño, es como un extra de 8 GB para ejecutar un nodo puente, y un poco más de disco de E / S, pero no es tan malo. Parece que si ya estás ejecutando un nodo de archivo y si tienes mucho ancho de banda, entonces por qué no. Necesita el acumulador merkle forest. También necesita un almacén clave-valor de punto de salida para posicionar en ese árbol. Si ve una entrada, ¿cuál es el punto de salida y dónde está?
P: Si estoy utilizando el acumulador, ¿puedo volver mágicamente al conjunto UTXO y obtener esa información?
R: Si nadie quiere hablar contigo, entonces estás un poco atascado. Pero si quieres volver a la forma anterior de hacer las cosas, podrías migrar hacia atrás.
Si tienes los bloques en el disco, tendrías que reindexar, porque el orden de inserción importa. Eso sería un poco lento. Es como volver a escanear. Necesitas altura e índice dentro del bloque… no, no tenemos eso.
P: ¿Cuál es el rendimiento en dispositivos de hardware de mierda? Su propuesta permitiría que esos dispositivos funcionaran con poca memoria, pero ¿se encarecen otras cosas para ellos?
R: Probablemente, la validación de firmas se convierte en un cuello de botella. Tengo un portátil lento y tardo 20 minutos en verificar un bloque. Es como un Core 2 Duo. Es lento, pero no es la CPU, sino el disco. Quiero añadir verificación de firmas a mi simulador.
No sólo sabes cuándo se eliminan esos UTXO, sino también cuándo entran otros nuevos.
P: ¿Cómo funcionan los reorgs?
R: Usted probablemente almacena un montón de viejos estados utreexo, que son sólo unos pocos cientos de bytes, por lo que probablemente almacenar hace 5, hace 10, hace 20, si hay un reorg entonces simplemente retroceder a eso y reiniciar. Debería ser posible mantener algunos miles de estos estados antiguos. Sería genial conseguir que fuera totalmente reversible, no sólo algo que se deshace y se rehace.
P: ¿Qué pasa con la aceptación de transacciones en el mempool?
R: No he implementado la sincronización p2p. La forma más sencilla es dar una prueba completa con cada transacción en el mempool y que todo el mundo la verifique. Sin embargo, eso supone una sobrecarga significativa. Así que necesitas tener una idea de qué partes del acumulador tiene tu compañero, y entonces enviar sólo esas partes de la prueba. Las pruebas cambian cada bloque. Realmente la forma de organizarlo es que tienes un montón de transacciones, tienes un puntero de localización con cada entrada, entonces tienes el estado de tu acumulador en RAM que es este tipo de árbol binario, así que tienes punteros allí, y tienes un lugar donde almacenas todos los datos de la prueba. Cuando actualizas eso cuando entra un bloque, obtienes tus actualizaciones de prueba gratis; si un hash cambia, tienes tu única entrada, y apunta a la posición 500.000 y entonces modificas tu gran árbol y tu hash cambia.
P: ¿Así que puedes averiguar si un bloque entra en conflicto con cosas de tu mempool, puedes averiguarlo porque la prueba ya no es válida?
R: No es que entre en conflicto; cada vez que entra un bloque, modificas tu acumulador.
P: Entonces, ¿podrías perder UTXOs?
R: ¿A qué se refiere?
P: Normalmente, cuando una transacción entra en el mempool, prueba que cabe en la punta. Luego entra otra y también prueba.
R: Eso es lo mismo. Sólo tienes que asegurarte de que todas son únicas. Verificas la prueba con respecto a tu estado. Recibes una nueva prueba, verificas que encaja en tu acumulador, y luego guardas los datos que…
P: Espera, entonces… ¿tu estado de prueba se basa sólo en transacciones confirmadas?
R: Sí.
P: ¿Y qué pasa con una transacción que depende de otras transacciones del mempool?
R: No hay ninguna prueba de ello. Si tienes una transacción que depende de algo que no ha entrado en un bloque, no hay ninguna prueba para ese UTXO. Es lo mismo que hoy. No hay prueba, sólo está en el mempool.
P: Entonces, cuando se mina, ¿tú mismo creas la prueba?
R: Si se crea y se gasta en el mismo bloque, las pruebas se crean y se gastan en el mismo bloque. Para las transacciones que estaban juntas en el mempool, para los árboles encadenados de transacciones, se supone que el minero añadirá la prueba para algunas de las transacciones encadenadas incluso 20-30 bloques más tarde.
P: ¿Cuál es el tamaño del mempool para estas pruebas?
R: En la práctica, no es tan malo porque muchas transacciones gastan salidas recientes. Además, la mayoría tienen árboles que se solapan. Así que se almacena todo el árbol y se solapan. Las pruebas son muy pequeñas. Es explotable, y si quieres ser un idiota, puedes conseguir todos estos UTXOs realmente viejos y hacer que se espacien. Incluso si están a la izquierda y todos agrupados juntos, las pruebas se superponen, pero si tratas de hacer griefing, podrías conseguir - en el peor de los casos, es como 2-3 veces el tamaño de las propias transacciones como si tuvieras toneladas de entradas. Usted probablemente podría hacer peor. Esto fue sólo de tontear con pruebas aleatorias. Usted podría ser capaz de encontrar una manera de obtener 4x uso. Pero en general, en el mundo real, las transacciones se agrupan muy bien.
P: ¿Hay que actualizar las pruebas para los nuevos bloques?
R: Sí, pero en su memoria, usted está manteniendo un puntero a la ubicación en la memoria. Para cada transacción, para cada entrada, es un puntero que dice a qué parte del árbol apunta. Si alguien le pide una prueba de transacción, usted dice bien el puntero está aquí, me acerco a la raíz y lo construyo en la demanda. Es fácil, son sólo todos los punteros dentro de él. Cuando descargas un bloque, modificas todo lo que hay en el árbol.
P: Así que la parte del árbol que estás manteniendo, sirviendo todo lo que hay en el mempool…
R: Modificas todo lo que hay en ese árbol. Cuando sale un bloque, puede estar modificando cosas que no te interesan. Sigues teniendo que modificar, pero puedes optar por olvidarlo inmediatamente después. En algunas secciones, tienes que bajar y recomputar un montón y no te importa en absoluto y lo tiras, pero en otras secciones no cambia nada pero más cerca de la cima quizá se modificó en la raíz. Es un poco complejo, pero en cuanto a CPU básicamente no hay sobrecarga.
P: ¿Mantiene un monedero su propia árbol?
R: Podría. Como vas a usar un nodo puente, no lo he implementado. Parece que sería difícil dejar de usar nodos puente.
Si aceptas el hecho de que los nodos puente serán siempre necesarios, cambia lo que esto mejora. En realidad, lo que se hace es desplazar la búsqueda y gestión de UTXO fuera del nodo completo, pero desplazándola a otro lugar donde es realmente costosa, pero ya no se encuentra en la ruta crítica para la validación de bloques. También se podrían trocear los nodos puente y fragmentarlos. Es bastante fácil fragmentar esto.
Hay otras cosas que puedes hacer con esto, no en el papel. Podrías hacer un tipo de cosa assumeutxo, donde codificas el cliente con un conjunto UTXO inicial y es una línea hexadecimal. Entonces assumeutxo se convierte en «aquí está el hash del árbol merkle» y no necesitas descargar nada, está todo listo. Otra cosa que podría hacer es si usted tiene un nodo de escritorio, usted podría tener un código QR, y luego sincronizar a un dispositivo móvil. También podrías sincronizar copiando toda la carpeta chainstate, es totalmente factible pero nadie lo hace. Pero algunas personas podrían decir, no quiero hacer la descarga inicial de bloques, déjame ir a blockchain.info y tal vez me da un código QR o algo así, por lo que es un arma de doble filo y no queremos ese resultado de confianza realmente.
Si todo el mundo está haciendo, cada UTXO que su cartera tiene, se mantiene un puntero en el árbol disperso y guardarlo en el disco, así que usted sabe que siempre estoy haciendo un seguimiento de estos UTXOs en el árbol y puedo encontrarlo.
P: ¿Y un ataque con huellas dactilares?
R: Sí, podrías intentarlo, pero sería caro porque tendrías que hacer muchas transacciones. Si aceptas una transacción con una prueba parcial, entonces oh, debes tener eso. Así que puedes intentar averiguar qué parte de la transacción conocen. Es caro porque necesitas una transacción válida. Puedes obtener conocimiento averiguando qué partes de las pruebas tienen. Más de una propuesta Chainalysis supongo.
Hay muchos otros trabajos sobre acumuladores, como el de Benedikt Bunz, que en cierto modo es un acumulador mucho mejor. Las pruebas son de tamaño constante y podrías probar un millón de UTXOs con una prueba minúscula. Pero hay problemas de configuración de confianza, o grupos de clase extraños que nadie sabe cómo funcionan. También es difícil o quizás imposible ejecutar un nodo puente. En utreexo, la idea es que si quieres ejecutar un nodo puente, sólo tienes que modificar tu árbol cada vez que entra un bloque, pero en los otros acumuladores, si quieres una prueba para cada UTXO son 60 millones de cosas que tienes que modificar por separado cada vez que entra un bloque. Son como 60 millones de operaciones RSA, o en realidad son 60 millones de operaciones RSA multiplicadas por el número de operaciones que haya en el bloque, así que estamos hablando de millones o billones de operaciones RSA por bloque. Es posible, pero necesitas un centro de datos.
P: Se podría dividir en dos propuestas distintas. Una es el uso de acumuladores para acelerar la descarga inicial de bloques, y la otra es el estado estacionario en el que alguien ejecuta estos acumuladores.
R: Hay transiciones que se pueden hacer, así que si se tiene -la gente hablaba de assumeutxo- aunque no se use utreexo, sigue teniendo sentido tener esta estructura como un compromiso UTXO en el código porque se pueden descargar pequeños trozos y verificarlos. La gente puede entregar el conjunto UTXO, y se puede verificar de forma incremental, y luego se obtiene la cosa completa y ahora eres sólo un nodo normal. Puedes pasar de un nodo utreexo a un nodo completo siguiendo el mismo proceso. Para hacerlo de la otra manera, sí, es una especie de proceso de reexploración por lo que es un poco lento. Podría ser una especie de assumevalid.
A menudo, cuando hablo de esto, la gente lo llama una propuesta de compromiso UTXO. Bueno, no. Realmente no queremos eso. Podrías hacerlo con eso, pero no sé si querrías.
Opciones de implementación
Podría ser un modelo electrum en el que no haya paso de mensajes entre clientes. Quizá sean p2p y cotilleen y se envíen pruebas entre ellos. Pero al principio, ¿por qué no un cliente que simplemente se conecta a un servidor y habla con él? No confía en el servidor, y es mucho más fácil de programar. Sólo estoy tratando de averiguar qué cosas para empezar a codificar.
Usted deshacerse de la base de datos UTXO y el plugin allí. Cory tenía una cosa conjunto utxo hash que hizo. Así que tal vez una interfaz RPC. Eso es genial, pero también tienes cosas p2p y rastreas todas las pruebas que has enviado a cada peer. Todas las pruebas cambian cada bloque. Si le envías a alguien la prueba… la billetera puede ser la misma.
Hay un par de refactorizaciones donde el código de validación está siendo limpiado con interfaces. Mantén un ojo en esos pull requests y pídeles que añadan cosas adicionales para que podamos añadir utreexo más tarde para que tengamos la interfaz correcta.
Conseguir que se fusione
Parece que deberías desarrollar esto en una rama fork de Bitcoin Core, sin saber si alguien lo usará alguna vez. Creo que la pregunta es, ¿cómo de útil sería? Si tienes un ordenador rápido e internet lento, es malo. Si estás intentando hacer la descarga inicial de bloques en un bonito portátil con wifi de avión, esto es mucho peor. Pero otro caso donde parece útil es como nodo Casa donde tenemos raspberrypi que queremos ejecutar un nodo completo.