El "indefenso" Satoshi Nakamoto y la "redundancia" del árbol Merkle

Guía

La moneda digital es esencialmente una cadena de cadenas especiales que se pueden copiar infinitamente. Si un minero controla temporalmente más del 50% de la potencia informática, inicia una transferencia al intercambio y se transfiere la misma moneda digital a sí mismo al mismo tiempo. Debido a que hay suficiente poder de cómputo disponible, ambas transacciones se escriben en el bloque y se convierten en transacciones legales. Este es un "ataque de doble gasto".

La red Bitcoin ha estado funcionando de manera constante desde su inicio y se ha demostrado que: en una red peer-to-peer sin un centro de liquidación, las transacciones peer-to-peer también pueden rechazar ataques de doble gasto. Todos los registros de transacciones de Bitcoin se almacenan en la cadena de bloques. En 2008, Satoshi Nakamoto mencionó en su artículo que describe el prototipo de Bitcoin que usó un Merkle Tree (MT para abreviar) La estructura de datos hace un breve registro de todas las transacciones en cada bloque, y el El árbol Merkle puede expresar una gran cantidad de información con menos bytes.

La estructura del árbol Merkle es un árbol binario completo, por lo que el número de transacciones debe ser 2n. Satoshi Nakamoto resolvió este problema introduciendo información redundante "no válida pero necesaria", a costa de que esta información redundante pueda ser utilizada por atacantes para llevar a cabo ataques de doble gasto.

Este artículo primero presenta la estructura básica del árbol de Merkle y las reglas para generar nodos, luego usa un ejemplo para ilustrar cómo construir un árbol de Merkle para las transacciones de Bitcoin y finalmente explica cómo Bitcoin usa el número único de UTXO para evitar la amenaza de Merkle. de dobles flores que el árbol pueda causar.

Punto de conocimiento 1:

Una función hash es una regla de operación matemática cuidadosamente diseñada por un matemático o un criptógrafo. Puede ingresar datos de cualquier longitud, mientras que la longitud del resultado de salida (es decir, el valor hash) permanece sin cambios y satisface:

1) Operación unidireccional: solo puede calcular la entrada para obtener la salida y no puede invertir el cálculo para obtener la entrada;

2) Prevención de colisiones: es imposible encontrar dos entradas diferentes que tengan el mismo hash.

Se puede decir que la función hash es una de las tecnologías centrales de blockchain, y la otra es el cifrado asimétrico. Son estas dos propiedades las que aseguran que Bitcoin sea tan difícil de obtener como el oro, y solo se puede obtener un valor hash correcto después de una gran cantidad de cálculos, lo que hace que el valor hash sea más valioso que otras cadenas, obteniendo así atributos de valor. Esta es la aplicación de las funciones hash en la minería de Bitcoin, pero no es el tema central de este artículo.

Punto de conocimiento 2:

Un árbol Merkle también se denomina árbol hash, porque en esta estructura de datos similar a un árbol, la etiqueta (o valor) de cada nodo es una cadena de valores hash. En orden de izquierda a derecha, los valores hash de todos los nodos secundarios se concatenan en una nueva cadena larga, y el resultado se usa como entrada de la función hash, y la etiqueta del nodo principal se obtiene después del cálculo.

El concepto de árbol de hachís lleva el nombre de Ralph Merkle, quien solicitó una patente el 5 de septiembre de 1979. Por supuesto, cuando Satoshi Nakamoto utilizó el árbol de Merkle como la estructura de datos subyacente de Bitcoin, el período de protección de la patente había terminado. De lo contrario, Satoshi Nakamoto tendría que pagarle al Sr. Merkel una tarifa de licencia de patente. Al hacerlo, su identidad podría quedar expuesta y toda la industria de la cadena de bloques tendría que pagar una tarifa enorme.

Además, Bitcoin no creó ninguna tecnología nueva de la nada, sino que usó inteligentemente varias herramientas criptográficas existentes y, después de la combinación, se convirtió en un sistema nunca antes visto como blockchain. Este tipo de innovación requiere un pensamiento sistemático extremadamente sólido y, a menudo, es difícil que una sola persona tenga un pensamiento tan profundo y amplio. Algunas personas especulan que Satoshi Nakamoto no es en realidad una persona detrás de él, sino que puede ser un grupo de criptografía. expertos

Estructura básica del árbol de Merkle

Más cerca de casa, el árbol de Merkle es un árbol binario completo y su estructura se muestra en la figura.

La etiqueta de cada nodo hoja es el valor hash de su contenido registrado, y las etiquetas de los dos nodos hermanos se concatenan como la entrada de la función hash, y el hash del nodo principal se obtiene después del cálculo, y así sucesivamente hasta que solo El siguiente nodo, el nodo raíz, también se denomina raíz de Merkle.

Satoshi Nakamoto diseñó una estructura de bloques en la que un campo en el encabezado del bloque es la raíz del árbol de Merkle. La raíz del árbol Merkle proviene de cada transacción registrada en el bloque, y la transacción puede entenderse como una transferencia, por ejemplo, un formato similar a "A transfiere una cierta cantidad de Bitcoin a B". Después de serializar un registro de transferencia con un formato fijo, se puede utilizar como tx de entrada y enviarse a la operación de función hash, y el resultado obtenido es la etiqueta L del nodo hoja.

L = hash (tx)

Los hash de cada dos nodos hoja se pueden concatenar como entrada para obtener el hash P del nodo principal.

P = Hash(L0+L1) // '+' significa concatenación

La longitud del contenido de la transacción que se puede registrar en un bloque es limitada. En el diseño de Satoshi Nakamoto, la longitud total de todas las transacciones en un bloque está estrictamente limitada a no más de 1 MB. La duración de la transacción varía con la complejidad de la transacción.Puede entenderse simplemente que cuanto más compleja es la transacción, más extenso es su contenido. Para usar los bloques de manera efectiva y ganar más tarifas, los mineros siempre esperan registrar tantas transacciones como sea posible en el bloque.

Observando la estructura del árbol de Merkle, se puede encontrar que siempre es un árbol binario completo, lo que significa que el número de nodos hoja es siempre 2n. Cuando el número de transacciones a registrar es inferior a 2n, o igual a 2n, la longitud total de todas las transacciones supera el límite de 1 MB. En este momento, el número de transacciones que se pueden registrar en un bloque no puede ser exactamente igual al número de hojas de un árbol binario completo. Cuando esto sucede, ¿cómo calcular la raíz del árbol de Merkle?

¿Cómo Satoshi Nakamoto construyó Merkle Trees para las transacciones de Bitcoin?

Ilustremos este problema con un ejemplo sencillo.

Suponiendo que se registra un total de 5 transacciones en un bloque, solo hay 5 nodos de hoja iniciales. Cada 2 nodos de hoja generan un nodo principal, pero en el proceso de generar el nodo principal, el último nodo de hoja no tiene nodos hermanos, por lo que es necesario construir otro nodo para que coincida. El método de Satoshi Nakamoto es: repetir directamente el nodo como su nodo hermano y luego obtener el nodo principal de acuerdo con el método mencionado anteriormente. Este nodo duplicado es la información redundante que no está en el registro de transacción original pero existe en el árbol de Merkle.

En este momento, aparecen tres nodos principales en la estructura de árbol de Merkle y luego continúan construyendo nodos principales basados ​​en estos tres nodos. El mismo problema ocurre nuevamente, solo hay 3 nodos en esta capa, y el último nodo debe repetirse para cumplir con el requisito de que los nodos hermanos aparezcan en pares, por lo que aparece nueva información redundante. Finalmente, dos nodos principales aparecen en el siguiente nivel superior y continúan fusionándose para obtener el último nodo único, es decir, el nodo raíz.

En el caso de que el número de transacciones sea 5, la estructura del árbol de Merkle construida a partir de esto se muestra en la siguiente figura.

Cómo puede evitar Bitcoin

¿Posible amenaza de doble flor debido a los árboles Merkle?

Este enfoque de Satoshi Nakamoto puede confundir a los lectores: dado que el último nodo de hoja se repetirá, desde la perspectiva de su nodo principal, tiene dos nodos de hoja con el mismo hash. De acuerdo con la propiedad de prevención de colisiones de la función hash, se puede juzgar que los contenidos representados por los dos nodos hoja son exactamente iguales. Es decir, asumiendo que se puede agregar un registro de transacción idéntico al bloque, el valor calculado de la raíz del árbol de Merkle permanece sin cambios. ¿No conduciría este enfoque al problema de los ataques de doble gasto?

¿Cómo evita la red Bitcoin que los nodos deshonestos registren intencionalmente dos transacciones idénticas en el mismo bloque? Esta confusión debe explicarse con la ayuda de UTXO, la unidad básica de las transacciones de Bitcoin.

En la red Bitcoin, no existe tal cosa como "cuenta", y no existe un concepto derivado como "saldo". Por lo tanto, es imposible juzgar si el usuario tiene activos que pueden continuar gastándose al verificar el saldo de la cuenta. como el sistema bancario tradicional. Todos los bitcoins existen en forma de UTXO (Salida de transacción no gastada).La transacción consume el UTXO existente (llamado entrada, Entrada) y genera un nuevo UTXO (llamado salida, Salida), y el UTXO consumido ya no es eficiente.

Cada UTXO tiene un script de bloqueo (ScriptPubKey) para proteger el UTXO de ser utilizado por otros, excepto por su propietario Actualmente, nadie puede desbloquear UTXO que no les pertenezca. El requisito previo para que UTXO sea gastable es que su secuencia de comandos de bloqueo esté correctamente desbloqueada. Por lo general, la secuencia de comandos de bloqueo de una UTXO especificará la información de la clave pública del propietario. Cuando se gasta la UTXO, solo la firma digital generada por la clave privada que coincide con la clave pública, es decir, la secuencia de comandos de desbloqueo (ScriptSig), se puede desbloquear con éxito. .UTXO.

En el diseño de Bitcoin, la identificación de la transacción y el número de serie de salida de UTXO en la transacción se utilizan como identificador único de UTXO, y todos los UTXO disponibles se almacenan en una recopilación de datos denominada conjunto UTXO.

Esto significa que es posible almacenar cada UTXO que no se haya gastado en la base de datos y hacerlo público en toda la red, y destruir y eliminar el UTXO consumido de la base de datos. Luego, cuando el atacante construye deliberadamente una segunda transacción e intenta gastar el mismo UTXO nuevamente, encontrará que el UTXO con la misma ID no se puede encontrar en la base de datos. Esto es equivalente a que después de que alguien gasta la moneda física real en su mano, no puede volver a usarla.

Debido a que cada UTXO tiene un identificador único, es fácil para los nodos determinar si el UTXO consumido por cada transacción es el mismo en un bloque: si hay dos transacciones cuya entrada es UTXO con la misma ID, se puede juzgar que la segunda La transacción no es válida y este bloque no puede ser verificado por nodos honestos.

Por lo tanto, aunque el árbol de Merkle tiene el problema de valores hash repetidos en teoría cuando el número de transacciones no es igual a 2n, en la práctica ya no es posible falsificar transacciones con el mismo contenido en el bloque real, y el Se evita el problema del doble gasto. .

Nota: Las imágenes de arriba son de Onchain

Referencias:

Papel original de Bitcoin Bitcoin: un sistema de efectivo electrónico entre pares

Archivo de patente original del árbol de Merkle

Este artículo fue producido por el equipo de Poly Enterprise

Tags：

FTX