Merkle Tree (MT) de Bitcoin, prototipo de Satoshi Nakamoto y el problema del doble gasto

La moneda digital es esencialmente una serie de cadenas especiales, que pueden ser ilimitadas. Si un minero controla temporalmente más del 50% de la potencia de cálculo, inicie una transferencia al intercambio y transfiera la misma moneda digital a sí mismo. Debido a que hay suficiente potencia informática disponible, ambas transacciones se escriben en el bloque y se convierten en transacciones legales. Este es el “ataque de doble gasto”.

Desde el inicio y el funcionamiento estable de la red Bitcoin, 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 los ataques de doble gasto. Todos los registros de transacciones de Bitcoin se almacenan en la cadena de bloques. En 2008, Satoshi Nakamoto describió el prototipo de Bitcoin y mencionó que usó un Merkle Tree (MT). La estructura de datos hace un registro breve de todas las transacciones en cada bloque, y el árbol de 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 resuelve este problema introduciendo información redundante “inválida pero necesaria”. El precio que se paga es que los atacantes pueden utilizar esta información redundante para llevar a cabo ataques de doble gasto.

Comprendamos la estructura básica del árbol Merkle, las reglas para generar nodos, y luego use un ejemplo para ilustrar cómo construir un árbol Merkle para transacciones de Bitcoin, y finalmente explique cómo Bitcoin puede evitar immekle a través del número único de UTXO. La amenaza de la doble flor causada por los árboles.

Punto clave 1:

La función hash es una regla de operación matemática cuidadosamente diseñada por un matemático o criptógrafo. Puede ingresar datos de cualquier longitud, y 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 calcular la salida para obtener la entrada en la dirección inversa;

2) Evitación de conflictos: no se pueden encontrar dos entradas diferentes, pero sus valores hash son los mismos.

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

Punto 2 de Ket:

El árbol de Merkel también se llama árbol hash , porque en esta estructura de datos en forma de árbol, la etiqueta (o valor) de cada nodo es una cadena de valores hash. En el orden de izquierda a derecha, los hash de todos los nodos secundarios se concatenan en una nueva cadena larga, el resultado se utiliza como entrada de la función hash y se calcula la etiqueta del nodo principal.

El concepto del árbol de hachís recibió su nombre de Ralph Merkle, quien solicitó la patente el 5 de septiembre de 1979. Por supuesto, cuando Satoshi Nakamoto usa el árbol de Merkel como la estructura de datos subyacente de Bitcoin, el período de protección de la patente ha terminó. De lo contrario, Satoshi Nakamoto tiene que pagar una tarifa de licencia de patente al Sr. Merkel. De esta manera, su identidad puede quedar expuesta y toda la industria blockchain tendrá que pagar mucho dinero.

Además, Bitcoin no crea ninguna tecnología nueva de la nada, sino que utiliza inteligentemente varias herramientas criptográficas existentes, y después de la combinación, es un sistema que nunca antes se había visto. Este tipo de innovación requiere un pensamiento sistemático extremadamente fuerte y, a menudo, es difícil tener un pensamiento tan profundo y amplio por sí solo. También se especula que Satoshi Nakamoto en realidad no es una sola persona detrás de él, sino que puede ser un grupo de criptografía.

Estructura básica del árbol Merkle

El árbol de Merkel 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 conectan en serie como la entrada de la función hash, y el hash del nodo padre se obtiene después del cálculo. Repita esto hasta que solo quede el final. El siguiente nodo, el nodo raíz, también se llama raíz del árbol Merkle.

Satoshi Nakamoto diseñó una estructura de bloques en la que un determinado campo en el encabezado del bloque es la raíz del árbol de Merkel. La raíz del árbol Merkle se deriva 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 valor a B una pequeña cantidad de Bitcoin”. Después de serializar un registro de transferencia con un formato fijo, se puede usar como entrada tx, que se calcula mediante la función hash, y el resultado es la etiqueta L del nodo hoja.

L = Hash (H)

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

P = Hash (Ha + Hb) // ’+’ significa concatenatio

La duración 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 cambia con la complejidad de la transacción. Puede entenderse simplemente como cuanto más compleja es la transacción, más largo es el contenido. Para usar el bloque 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, podemos 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 menor que 2n, o igual a 2n, la longitud total de todas las transacciones excede el límite de 1 MB. En este momento, el número de transacciones que puede registrar el bloque no puede ser exactamente igual al número de hojas de un árbol binario completo. ¿Cómo calcular las raíces de Merkel cuando esto sucede?

¿Cómo construye Satoshi Nakamoto un árbol Merkle para transacciones de Bitcoin?

Para ilustrar este problema con un ejemplo sencillo. Suponiendo que se registren un total de 5 transacciones en un bloque, solo hay 5 nodos hoja iniciales. Se genera un nodo padre por cada dos nodos hoja. En el proceso de generar nodos padres, el último nodo hoja no tiene nodos hermanos. En este momento, es necesario construir otro nodo para que coincida. El enfoque de Satoshi Nakamoto es repetir directamente el nodo en sí mismo como su nodo hermano y luego obtener el nodo principal de acuerdo con el método mencionado anteriormente. Este nodo duplicado es información redundante que no se encuentra en el registro de transacción original pero que existe en el árbol Merkle.

En este momento, aparecen tres nodos principales en la estructura de árbol de Merkel y luego continúan construyendo nodos principales basados ​​en estos tres nodos. Vuelve a aparecer el mismo problema. 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, de modo que aparezca nueva información redundante. Finalmente, dos nodos principales aparecen un nivel más alto y continúan fusionándose para obtener el último y único nodo, el nodo raíz.

Cuando el número de transacciones es 5, la estructura del árbol Merkle construido a partir de esto se muestra en la siguiente figura.

Cómo evitar Bitcoin

¿La amenaza de la doble flor provocada por el árbol de Merkel?

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

¿Cómo evita la red Bitcoin que los nodos deshonestos registren deliberadamente las mismas dos transacciones en el mismo bloque? Esta duda debe explicarse con la ayuda de UTXO, la unidad básica de las transacciones de Bitcoin.

En la red Bitcoin, no existe una “cuenta”, y no existe el llamado “saldo” y otros conceptos derivados. Por lo tanto, es imposible juzgar si un usuario tiene activos que se pueden seguir gastando al verificar el saldo de la cuenta como un sistema bancario tradicional. Todos los bitcoins existen en forma de UTXO (Salida de transacción sin gastar). La transacción consume el UTXO existente (llamado Entrada), genera un nuevo UTXO (llamado Salida, Salida) y el UTXO consumido ya no es efectivo.

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

En el diseño de Bitcoin, el ID de transacción y el número de serie de salida de UTXO en la transacción se utilizan como identificación única de UTXO. Todos los UTXO disponibles se almacenan en un conjunto de datos denominado conjunto UTXO.

Esto significa que se puede lograr: cada UTXO que no se ha gastado se almacena en la base de datos y se divulga a toda la red, y el UTXO que se ha consumido se destruye y elimina de la base de datos. Luego, cuando el atacante construye deliberadamente la segunda transacción e intenta gastar el mismo UTXO nuevamente, encontrará que el UTXO con el mismo ID no se puede encontrar en la base de datos. Esto equivale a alguien que ha gastado la moneda física real en su mano y no puede volver a usarla.

Debido a que cada UTXO tiene una etiqueta única, es fácil para un nodo determinar si el UTXO consumido por cada transacción es el mismo dentro de un bloque: si hay dos transacciones cuya entrada es UTXO con el mismo ID, puede determinar el segundo La transacción no es válida y el bloque no puede ser verificado por nodos honestos.

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