El rompecabezas del doble hash (30 de abril de 2019)

Hay un viejo rompecabezas en Bitcoin que aún no se ha resuelto correctamente: ¿por qué utilicé un doble hash?

En primer lugar, la explicación del problema del doble hash tal y como se da en la wiki de CoreCoin es totalmente falsa.

image

Si aplicas doble hash a un valor, persisten los ataques de cumpleaños. Si tienes dos valores que al hacer el hash dan el mismo resultado, formando un ataque de cumpleaños o una colisión, éstos seguirán colisionando. Es simple de demostrar. Se supone que tenemos dos valores X e Y. Para una función de hash dada, tenemos una colisión tal que:

A == Hash(X) == Hash(Y).

Ahora, dado el resultado de que tanto X como Y llegan como resultado del hash al mismo valor, A, podemos ver fácilmente que ningún proceso de doble hash o de hash al cuadrado ayudará, ya que:

Hash(A) == Hash[Hash(X)] == Hash[Hash(Y)].

De hecho, perdemos un bit de información por la operación de hash adicional. Podemos decir que si iteramos un hash n veces, esto hace que sea n veces más probable que ocurra una colisión. Me tomo un poco de libertad aquí, y las matemáticas involucradas en lo que he explicado no son completamente exactas, pero es cierto que, cada vez que iteramos una función usando la misma función de hash, perdemos seguridad de colisión en la función. De hecho, si miramos cómo se crean las direcciones en Bitcoin, vemos que la función de doble hash aumenta el efecto aún más. En otras palabras, es más probable que el hash del hash en este escenario provoque una colisión que el hecho de que ocurra en un hash simple o incluso en el hash de la misma función de hash (un doble hash).

A == Hash (X1) == Hash (Y1)

B1 == Hash-a(X2)

B2 == Hash-a(Y2)

Si B1 = B2, entonces tenemos el escenario de A.

Sin embargo, también existirán valores como:

C == Hash-b(B1) == Hash-b(B2).

Por lo tanto, la probabilidad de encontrar una colisión en dos valores, es decir, separar las claves públicas, aumenta (más que con sólo un doble hash) cuando utilizamos funciones de hash separadas (por ejemplo, SHA256 y RIPEMD160).

Así pues, tengo que señalar que en esta área (como en tantas otras), la wiki de Bitcoin, perdón, CoreCoin, es errónea. No se utiliza el doble hash dentro de Bitcoin para aumentar la seguridad. Al abordarlo, añade un beneficio en el sentido de que si se encuentra que una función de hash es vulnerable, entonces la otra función de hash permanecerá siendo segura durante más tiempo, pero como en el escenario anterior, se podrían encontrar colisiones más fácilmente. En consecuencia, desafortunadamente, la razón no tiene que ver con ese beneficio aparente.

Ferguson y Schneier (Criptografía práctica) propusieron utilizar una función de doble hash como medio para defenderse de los ataques de «extensión de la longitud» con SHA-256, y la denominaron SHA-256d. Las funciones de hash de Merkle-Damgård, como MD5 o SHA-256, son vulnerables a este tipo de ataques. Si eso supusiera un problema, podríamos haber usado HMAC, pero la realidad es que Bitcoin constituye un sistema económico. La seguridad de Bitcoin siempre tiene que ver con el coste de atacar frente al coste de defender.

Aunque puede suceder que el cómputo de un SHA-256(k||d) en concreto sufra un ataque de extensión de longitud que se pueda encontrar, también será fácilmente detectado, monitorizado y bloqueado. Encontrar el script que sigue ese escenario no supone realmente lo que yo consideraría un problema. De hecho, no se trata realmente de un problema, pero no entraré en más detalles aquí. Hay muchas formas mejores de detener los ataques de extensión de longitud en Bitcoin ahora mismo. Y esto forma parte del poder del script.

Entonces, si reduce la seguridad, ¿por qué lo hacemos?

Estamos registrando numerosas patentes donde se cubre todo esto. Desafortunadamente, todas las falsas bifurcaciones de Bitcoin han hecho necesario patentar muchas de esas tecnologías que la gente no comprendía. Un uso de la función de doble hash en Bitcoin es la especialización de las funciones de verificación individual según Bitcoin va escalando.

Si empiezas a pensar en ello, verás que donde:

A == Hash(X),

ahora:

B == Hash(A)

Esto nos permite hacer que el valor (A) sea enviado a un minero de una manera que no le permita emitir un bloque sin transacciones individuales. En una estructura de árbol de Merkle, podríamos tener todo el bloque enviado y resuelto a partir de una sola transacción. Hacerlo nos permitiría construir una instalación minera ASIC que no albergue los datos en bloques. El minero es ahora una función distribuida.

Como tal, la prueba de trabajo y la verificación pueden delegarse a entidades especializadas. La instalación de la ASIC puede pagar a la instalación de verificación cuando se descubran bloques válidos, y sin embargo el sistema les permite interactuar sin poder engañar a ninguna de las partes. De hecho, pueden incluso llegar a acuerdos con diferentes mineros y consorcios y permitir que suceda sin preocupaciones: si una parte hace trampas, ambas salen perdiendo.

A partir de la cuestión de dónde ubicar las instalaciones, el asunto se vuelve interesante. China y muchos lugares de Asia Central tienen electricidad, pero no tienen acceso a la red. Poder distribuir esas funciones constituye una característica valiosa.

Con un árbol de Merkle, podemos permitir que un nodo de verificación que actúa como un sistema distribuido fuera de China envíe funciones de hash simples pero fáciles de validar que puedan ser comprobadas estadísticamente por el minero sin tener que validar todas las partes de la transacción. En otras palabras, si la propagación de bloques supone un problema en ciertas áreas, no lo es para los mineros de Bitcoin a gran escala en BSV.

De hecho, sólo representa la punta del iceberg de lo que se puede hacer. A lo largo de este año, cuando las patentes empiecen a publicarse, podrás ver algunas posibilidades más.

Material ilícito

El uso de una función de doble hash también permite crear un sistema que puede ser distribuido y validado mientras se actúa dentro de la ley. Las funciones de distribución pueden enviarse a sistemas especializados que actúen en las jurisdicciones locales. En consecuencia, nos permite tener un almacenamiento de datos inmutables que se pueden filtrar con el hash que se esté validando y una posterior poda del material ilícito que se permita en ciertas jurisdicciones. Es decir, el doble hash dentro de Bitcoin crea un método para poder entregar contenido de forma selectiva.

La blockchain es inmutable, pero con un doble hash, se puede restringir o aprobar la solicitud de un registro.

Así pues, te planteo una pregunta hipotética:

¿Qué pasaría si BTC, ETH, etc., empezaran a alojar pornografía infantil y otros materiales ilícitos y sólo BSV los pudiera filtrar?


Enlace al artículo original: https://craigwright.net/blog/bitcoin-blockchain-tech/the-puzzle-of-the-double-hash/

3 Likes

Justo el mismo día que se publicó este artículo, se cambió la página wiki de Core.

En el historial de la página que se enlaza en el artículo se deja ver el cambio el 30 de abril del 2019, en el que se quita el párrafo que estaba mal. El cual estaba desde la redacción de Adam Back.

He subido la página del cambio a Bitcoin para evitar cambios posteriores. https://etched.page/1baec53d76438796b1f805ee5cf7ecca9102c57be1615039cd4002de6c12f5e9/https://en.bitcoin.it/w/index.php?diff=prev&oldid=66429&title=Hashcash

4 Likes