Acumuladores UTXO, compromisos UTXO y Utreexo
Oradores: Tadge Dryja
Fecha: October 8, 2018
Transcripción De: Bryan Bishop
Traducción Por: Blue Moon
Tags: Proof systems, Utreexo
Categoría: Core dev tech
https://twitter.com/kanzure/status/1049112390413897728
Si la gente vio la charla de Benedikt, hace dos días, está relacionado. Es una construcción diferente, pero el mismo objetivo. La idea básica es, y creo que Cory comenzó a hablar de esto hace unos meses en la lista de correo … en lugar de almacenar todos los UTXOs en leveldb, almacenar el hash de cada UTXO, y entonces es la mitad del tamaño, y entonces casi se podría crear a partir del hash de la entrada, es como 10 bytes más. En vez de almacenar los hashes de cada UTXO, que tal almacenar alguna representación compacta de eso y proveer pruebas.
En la charla de Benedikt, había acumuladores basados en RSA o posiblemente esta cosa del «grupo de clase» que está totalmente sin probar. No lo se. En lo que estoy trabajando es en el acumulador basado en hash. Las propiedades básicas de un acumulador son que puedes… hay diferentes construcciones con diferentes características u operaciones que puedes hacer. Por lo general, usted tendrá algún generador, hacer que el acumulador, algún tipo de operación de adición (añadir un elemento), y luego una función de prueba. El creador del generador devuelve el acumulador, la operación de suma toma un acumulador y un elemento y luego escupe un acumulador modificado, y luego la función de prueba es… hay una prueba y luego una verificación. La función prove es, quiero probar que este elemento existe en el acumulador, y esto resulta en algún tipo de prueba. La función de verificación toma una prueba contra el acumulador y se obtiene un booleano. Cada construcción de acumulador tendrá al menos estas funciones, necesitas ser capaz de sumar, probar y verificar. Prove genera la prueba, verify comprueba la validez de la prueba contra el acumulador. Alice hace una prueba, y Bob verifica o algo así. Esta es la construcción más básica. También puedes tener una función de no inclusión (probar que no existe) y obtener una prueba diferente de que la cosa no está en el acumulador. A veces se puede tener una operación de borrado y eliminar un elemento del acumulador y obtener un acumulador modificado.
Los primeros trabajos sobre estos tenían acumuladores unidireccionales en los que podías seguir añadiendo cosas al acumulador, nunca eliminar pero todo está ahí. Otros tienen la capacidad de eliminar y probar la no inclusión. El que estoy hablando no tienen no-inclusión … podría haber maneras de hacerlo, pero probablemente será feo. Para un conjunto UTXO, es posible que no lo necesite.
Hay un número de diversas razones por las que usted puede ser que desee esto. El objetivo es reemplazar leveldb. En lugar de almacenar todo el conjunto UTXO, estás almacenando este acumulador. Cada vez que entra una transacción, añades y borras de tu acumulador. Para cada entrada en cada transacción, hay una prueba y verificas esa prueba. Ese es el modelo en el que estoy pensando. Hay otros posibles casos de uso para esto en bitcoin, pero creo que este sería genial y sería más rápido.
A largo plazo, es bueno porque entonces el crecimiento ilimitado del conjunto utxo se vuelve mucho menos aterrador. Generalmente estos acumuladores o pruebas son de tamaño constante o logarítmico. Los de RSA son de tamaño constante, estos son de tamaño logarítmico. 10 mil millones de UTXOs, no hay problema. Desplaza la carga al lugar correcto. Si eres un intercambio con 20 millones de UTXOs, todo el mundo tiene que almacenarlos en su carpeta chainstate, pero en cambio esto empujaría el esfuerzo al intercambio para mantener sus propias pruebas y proporcionarlas a la gente.
Incluso si eso no es lo que ocurre, incluso si lo que ocurre es que la carga de crear estas pruebas se traslada a nodos que lo hacen para todo el mundo -como nodos que sirven a todo el blockchain para todo el mundo- sigue siendo una ventaja porque has eliminado la carga de la gestión de UTXO de los validadores. Los mineros ya no lo necesitan, los nodos completos ya no lo necesitan, y estos servicios (ya seas tú mismo u otras personas) pueden producir las pruebas y no es crítico para la latencia, puede ser lento. Cada bloque tendría una prueba, recogiéndola de las transacciones individuales.
Esto se puede hacer sin cambios en el consenso, podría ser p2p.
Para RSA, si pudiéramos hacerlo sin configuración de confianza, aunque sea lento, ¿sigue siendo práctico para bitcoin? No estamos seguros. Probablemente no. ¿Los grupos de clase? Probablemente no. No tenemos números, pero no parece probable.
Si tienes un acumulador… digamos que empiezas de cero y no hay 500k bloques de historia. Empieza un nuevo blockchain y esto ignora el problema del nodo puente.. el problema del nodo puente es que si eres la primera persona en usar este nuevo software, y no tienes el conjunto UTXO, y necesitas pruebas de cada entrada- 0.17 no será capaz de proporcionarte una prueba, así que estás atascado. Necesitas alguna manera de arrancar. Los nodos puente son una gran cosa aquí.
Si usted tiene estas operaciones, y todo el mundo comienza con ella, y cada cartera ahora mantiene pruebas para cada UTXO que poseen y hay laso una operación de prueba de actualización … y son una especie de combinación con la operación de añadir y eliminar, donde se modifica el acumulador, pero cuando se modifica el acumulador es posible que desee modificar las pruebas. Las pruebas son con respecto a los acumuladores. Las pruebas cambian cada vez que cambias el acumulador y eso puede ser costoso. Si tienes un UTXO, vas a hacer 5000 operaciones por bloque para mantenerlo actualizado. Si tienes un millón de UTXOs, entonces estás haciendo como un billón de operaciones… necesitas actualizar cada prueba por cada cambio en el acumulador.
Podrías usar esto hoy- no tienes que tocar disco, todo está en RAM. Esto no es para trillones de UTXOs. Tardar un día en sincronizar el blockchain es un poco soso. Ahora mismo bitcoin funciona bien con la configuración actual y no necesitas un ordenador rápido. Pero esta técnica del acumulador te permitiría hacerlo en teléfonos de forma bastante viable.
¿Podrían los nodos completos tirar las pruebas después de la verificación? Sí. Igual que la poda. Podrías crear las pruebas mientras sincronizas desde el principio. Todos los datos de las pruebas se pueden calcular a partir de la cadena de bloques. Es sólo una optimización.
Así que llegando a los nodos del puente.Hay un problema.La idea de un nodo puente es que es un wlalet con cada UTXO.Es su cartera para mantener sus pruebas al día.Los nodos puente tienen una prueba para todo. Une como nodos v0.17 y entonces tienes un puente y entonces tienes estos clientes utreexo… necesitan pruebas, estos chicos no tienen ni idea de lo que son estas pruebas, todos los mensajes UTX que van aquí, los nodos puente pegan pruebas en las entradas, él lo difunde y lo propaga. Esto es factible, pero depende.Este nodo puente tiene que mantener 60 millones de pruebas, dependiendo de lo grandes que sean las pruebas, esto podría ser molesto… Bueno, quizás puedan recalcular una prueba sobre la marcha cuando llega una entrada, ¿cuánto almacenan?Con el RSA, parece que el nodo puente tarda como 100 milisegundos en calcular cada uno.El nodo puente le permite entrar en el mempool.Tiene que ser todo; puedes intentar predecirlo. Así que tiene que almacenar todas estas pruebas y recalcularlas constantemente. Para RSA, esto es un problema, son años por bloque de pruebas. Podrías dividirlo en una granja de servidores. Es perfectamente fragmentable… pero podría ser un gran centro de datos. Las pruebas RSA aquí son muy rápidas de verificar.
Hay un nuevo desarrollo anunciado en Scaling Bitcoin. Hay algunos que son rápidos, pequeños, unos pocos kilobytes para todo el bloque o toda la blockchain.Es realmente genial en tamaño, pero en velocidad no está claro todavía.Así que el de RSA es como, diminuto, y es lento de probar… Mi método es utreexo… Para RSA y grupo de clase, la prueba de actualización es lenta.Para utreexo (basado en hash), es rápido. utreexo es agregable porque todos se superponen en el árbol.Verificar para RSA/CG es rápido, son nanosegundos tal vez 1 microsegundo digamos. En utreexo, es rápido pero no super rápido para hacer la verificación. El tamaño de la prueba para RSA/CG es O(1) en la práctica es 1,5 kilobytes, y el tamaño del acumulador es 1,5 kilobytes y O(1) y también es agregable…. La operación de actualización es add + delete. Acumuladores RSA, puede probar un millón de cosas en tamaño constante. En utreexo, es O(log(n)) y es algo así como z log(n). Puedes conseguir un par de cientos de kilobytes por bloque para utreexo, pero hay un montón de optimizaciones que puedes hacer. Quiero bajar el tamaño de la prueba para el acumulador basado en hash, hay un montón de trucos. Para RSA, el tamaño del acumulador es de tamaño constante, pero utreexo es O(log(n)) pero en la práctica es como 800 bytes. El otro compromiso es la confianza, o las suposiciones. Es un gran problema. La gran suposición para RSA es la suposición RSA pero también algún tipo de N = PQ que nadie conoce, y el grupo de clase ni siquiera lo conozco así que no puedo decir nada al respecto. Y la de utreexo son hashes resistentes a colisiones que es una suposición que bitcoin ya hace, como SHA. Quantumy, quién sabe.Para RSA, necesitas un módulo del que nadie conoce la factorización, lo que no es divertido para bitcoin en general. Pero se puede hacer esto sin un tenedor. Estoy ejecutando un nodo de prueba y el puente de prueba y nadie sabe y está bien … usted puede tener una cosa electrum-estilo donde usted tiene un índice de direcciones y sólo se puede construir eso, para un cliente que necesita esas pruebas, y usted tiene un servidor en algún lugar que proporciona esas pruebas. Pero es un modelo más agradable donde se construye en los clientes y pueden p2p propagar las pruebas, pero se puede empezar sin eso y probar que es una especie de fresco.
Las principales formas de mejorar el tamaño de la prueba para el acumulador basado en hash… la idea del acumulador basado en hash es que tienes árboles merkle, pones UTXOs en los árboles merkle, y puedes borrar elementos arbitrarios y luego barajar para mantener árboles perfectos. Voy a entrar en eso más tarde. En general, cada cosa va a necesitar una prueba de la altura del árbol.Si estás probando dos primos, una vez que se cruzan, no necesitas datos de prueba superpuestos.Además, con el tiempo, el árbol de merkle no cambia completamente cada pocos bloques, sólo pequeños segmentos del árbol.
Cuando estás haciendo la descarga inicial de bloques, el nodo completo con el que estás hablando conoce el futuro en el sentido de que sabe lo que viene a continuación. Si te ayudan, pueden acelerarte mucho. El nodo completo puede decir que este UTXO que acabas de añadir se borrará en el próximo bloque, así que guárdalo en la RAM, para que puedas recordarlo y no tengas que almacenarlo en caché o lo que sea.Y otras partes del árbol, se queda allí durante 5 años, por lo que expulsarlo de la RAM y lo pruebo más tarde cuando haya terminado con la descarga inicial de bloques. También puede ayudar con la expulsión de caché para cosas leveldb. Esto puede reducir el tamaño de la prueba.
¿De dónde viene el tamaño del acumulador de 800 bytes? Se almacena la raíz de los subárboles. Permítanme hablar de la construcción de este acumulador basado en hash. Tienes un bosque merkle- es un árbol perfecto, siempre una potencia de 2. Hay algunas cosas divertidas bitshifty donde se escribe el número total de UTXOs en binarios, por lo que para 15 elementos es 0b1111. Si yo fuera a eliminar dos cosas, terminaría convirtiendo htis en un 0 y este subárbol desaparecería, por lo que es una especie de fresco. Añadir es fácil en el que acaba de poner las cosas en el lado y volver a calcular sus árboles. Si yo fuera a añadir algo al final, no sé estos números uncircled porque sólo estoy almacenando las raíces. Pero puedo calcular el padre de la última, y el nuevo, y puedo seguir bajando y obtener un hash para todo el estado.
Si borras algo, su vecino se convierte en «hijo único». Se expulsa al final del árbol. Hay un montón de cosas que se desplazan al final del árbol, y lo divides en cuatro subárboles como hiciste antes. Si eliminas un elemento, la prueba estará relacionada con su vecino y los subárboles que lo rodean. Esos hashes en la prueba se convierten en las siguientes raíces para los cuatro subárboles una vez que eliminaste eso. Puedes agregar esto, así que si estás borrando muchas cosas a la vez… esto está en progreso pero funciona… lo primero que haces es encontrar lugares donde ambos hermanos fueron borrados, tienes una lista de borrados, encuentras dos hermanos siendo borrados, entonces borras el padre.Si tienes borrados simples, dejando sólo hijos, puedes intercambiar los hermanos a otros subárboles. Mantén las cosas viejas a la izquierda, mantén las cosas nuevas a la derecha porque es más probable que las cosas nuevas se gasten, así que las pruebas deberían ser más pequeñas por eso.
Para los nodos no puente, es super rápido y fácil.Usted tiene estas ramas parciales y que acaba de hash mucho. El principal problema que tienes, la principal compensación, es como RAM vs descarga. Si tienes un número de bloques que mirar - asumiendo que el nodo IBD al que te estás conectando te dirá cuando se gasta el UTXO; podrías almacenar todo para 4000 bloques en marcha, así que mantienes todo en RAM para los UTXOs que se gastan pronto… si recuerdas todo, entonces nunca necesitas descargar ninguna prueba, así que el tamaño total de todas las pruebas es cero. Si no tienes nada de memoria y siempre necesitas descargar nuevas pruebas para cada bloque, el total acaba siendo de 160 gigabytes, que se suman a los 200 gigabytes de datos del blockchain. Creo que la curva de la compensación es realmente empinada. Aún no lo he calculado, pero intuitivamente, si almacenas todo entonces nunca necesitas descargar.Creo que la curva es empinada y como hay un montón de UTXOs que se gastan rápidamente… si tienes unos cientos de megas de RAM, entonces almacenas un montón de pruebas temporalmente durante el IBD. Espacialmente, lo de RSA lo borra por completo y son 1,5 kilobytes para todo.
¿Qué tal convertir esto en un soft-fork, ya que nos gustan los soft-forks y son tan fáciles de hacer? Pongamos las raíces de este acumulador o este acumulador RSA en un OP_RETURN en la transacción coinbase, y entonces nadie tiene que validar todo más porque entonces pueden confiar en los mineros para verificar todo. Tal vez tomamos todas las pruebas para el bloque y poner eso en un OP_RETURN, y se puede explicar por qué eso es importante….Es la resistencia a la denegación de servicio. Ahora mismo, cada vez que hago una validación de bloque, primero hago una comprobación de prueba de trabajo, que es muy barata, y si la prueba de trabajo no funciona, entonces no me voy a molestar en hacer la validación completa. Debido al hecho de que todos los datos que entran en mi ecuación de validación están comprometidos por el PoW, si alguien sobre la marcha en el protocolo p2p invalida un bloque modificando una firma o lo que sea, entonces el PoW queda invalidado y no me voy a molestar. La otra cara de la moneda es que, siempre que pase la comprobación PoW y un bloque siga siendo inválido, puedo marcarlo como inválido de forma permanente, ya que era el bloque el que era inválido, no algunos datos auxiliares a su alrededor. Nunca voy a comprobar el mismo bloque dos veces. Si estás en un mundo en el que los bloques tienen datos auxiliares que deben ser válidos, no puedes distinguir entre que el bloque no sea válido o que los datos auxiliares no lo sean. Esto da un vector de DoS. Obtienes un bloque, con datos de prueba modificados/atacados, y entonces oops no puedes distinguir en absoluto- puedes banear el nodo pero no sabes si el bloque es realmente inválido (o puedes pensar que lo es, pero ahora has sido atacado). Si no eres capaz de hacer un soft-fork en un compromiso, entonces en la práctica, la mayoría de las cosas en el bloque van a ser cosas ……..
¿Comprometiendo el estado real del acumulador? No, porque eso anima a la gente a no validar nada. El tema del compromiso de UTXO, del que la gente lleva hablando mil años, si se compromete el conjunto de UTXO en el bloque, ayuda a la gente a saber que tienen el conjunto de UTXO correcto o que pueden descargarlo. Si añades esto, entonces eso ocurrirá. Puedes tener una versión súper potente de assumevalid y puedes simplemente codificar a la altura 500000 aquí están los hashes del conjunto UTXO, saltar allí y validar completamente después de eso. Eso es un arma de doble filo: es genial, y hay casos de uso para eso como sincronizar en mi escritorio, validar todo, tomar una instantánea en mi teléfono del código QR que el cliente me proporciona, y luego mi teléfono tiene el estado. Pero alguien podría ir a blockchain.info y descargar el estado del acumulador.
Digamos que descubrimos una manera de hacer que las cosas del grupo de clase sean súper eficientes. Desafortunadamente es una suposición criptográfica completamente nueva. La gente ha asumido que este es un problema difícil durante mucho tiempo, como 200 años, y nunca se ha utilizado en ningún protocolo real. Así que sí, no vamos a hacer de eso una regla de consenso.Pero si quieres confiar en eso y configurar una red p2p en la que funcione, entonces por qué no.O incluso si es como, aquí hay un modelo basado en hash que es bastante eficiente y luego un año o dos más tarde alguien hace uno mejor y es 10 veces más eficiente, entonces un soft-fork significaría que estamos atascados con uno viejo.Supongo que podríamos hacer un soft-fork con fecha de desactivación, pero aún es pronto para analizar esos aspectos. No sé, es una buena manera de acelerar las cosas. Los clientes pueden elegir sus compensaciones, como en el modelo no comprometido para esto. Pero quieres eliminar la necesidad de que los mineros mantengan conjuntos UTXO. La validación completa sería más barata.
Si se utiliza un modelo en el que las pruebas quedan obsoletas, lo que no es cierto para todos ellos pero sí para la mayoría, significa que es necesario ver los bloques completos para poder actualizar las pruebas, lo que descarta por completo a los clientes lite.Los clientes lite necesitan depender de un servicio para actualizar las pruebas.Creo que no es razonable decir que podemos tener un ecosistema en el que no haya servicios que proporcionen esas pruebas.Así que creo que se necesitarán nodos puente.
Electrum tiene un índice de direcciones, y proporciona pruebas SPV, y en este modelo también sería un nodo puente.En el modelo basado en hsah, ser un nodo puente es más pequeño y más fácil que tener un índice de direcciones.En el modelo RSA, es pequeño pero computacionalmente inviable.
Si no hubiera nodos puente, entonces en SPV todavía puedes molestarte en no validar, pero sigues haciendo mucho trabajo para mantener tus pruebas válidas, y casi no hay sobrecarga adicional para validar realmente.También aumenta los costos para las personas que tienen bazillions de UTXOs.Pero lo estás haciendo lento y molesto para la gente a la que querríamos disuadir de todas formas, como las cosas SPV y tener billones de UTXOs.
En el modelo basado en hash, los nodos puente no hacen ningún trabajo extra de CPU porque estás realizando todos esos hashes… en el nodo puente basado en hash, simplemente almacenas todo el árbol en lugar de sólo las raíces. Haces las mismas operaciones hash, pero guardas todo en el disco.Es más i/o, mientras que el nodo no puente está almacenando menos datos en general. El nodo puente en el modelo basado en hsah no está haciendo ningún trabajo extra de CPU aparte de i/o de disco.
Para el nodo puente en el modelo basado en hash, debería tardar del orden de un segundo.Todo mi software es de un solo núcleo y sin optimizar y sigue siendo bastante rápido.Está escrito en golang. Lo tengo donde, no tengo como las cosas de la capa p2p. Es sobre todo para obtener números.Hace todo el hash y todas las cosas, pero no tiene el nodo p2p mensajes.Se siente como ninguna utilización del disco, es agradable. Es 100% cpu mientras puedas mantener el ancho de banda. Ahora mismo es 10% cpu. No sé qué tan nicho es eso. ¿Qué hace la gente con nodos completos? No lo se.
Probar la existencia de UTXO en pequeños entornos de hardware como módulos de seguridad de hardware o HSMs, eso sería realmente útil. Aquí puedes hacerlo de forma completamente privada. Tu anfitrión es el nodo puente, y sólo le entrega las pruebas.
La otra posible característica de libconsensus es la idea de una función que tome todo el estado de la cadena de bloques y diga si es válido o no. Se vuelve más factible.Todo el asunto es como un megabyte, los argumentos son como aquí hay un bloque, aquí está el estado, y devuelve un booleano y un nuevo estado.Esto es algo que la gente ha estado trabajando y parece que te ayuda a llegar allí. Podría ayudar.
Estoy escribiendo un artículo, tratando de hacer esto más legítimo. He escrito código en golang.Parece divertido. Parece que a largo plazo es un buen modelo.
Podría ser más elegante no tener estados gigantes que se llevan alrededor para la validación.¿Qué pasa si quieres bloques más grandes? utreexo probablemente ayuda a eso.Sé que la gente de bcash no me gusta porque relámpago, pero tal vez les gustará utreexo ((risas)).
No se puede tener una cosa ordenada-inserción para monero porque se necesita probar la no-inclusión del gasto en el conjunto de gastos. Puedes tener un conjunto de salida de transacciones gastadas… ah pero no sabes los gastos que hay. Esto no funcionaria para monero.
Trabajos futuros
http://diyhpl.us/wiki/transcripts/mit-bitcoin-expo-2019/utreexo/
https://github.com/mit-dci/utreexo