La blockchain de Ethereum alcanzó recientemente un tamaño de aproximadamente 130 GBytes... Si queremos buscar una transacción específica, en casi 517 millones de transacciones y 130 GBytes, ¿cómo podemos encontrarla eficientemente?
Precisamente una de las tecnologías menos entendidas y más importantes para conseguir escalabilidad en las criptomonedas son los árboles de Merkle (US Patent 4309569). Esta breve nota busca explicar esta tecnología, su uso y sus características de complejidad que permiten escalar a una estructura de datos capaz de almacenar trillones de transacciones.
Funciones de hashing
Las funciones de hashing han tenido un notorio incremento en su uso en muchas aplicaciones corporativas. Desde simples verificaciones de integridad de documentos comerciales, hasta passwords de un solo uso en servicios de doble factor de autenticación, nos es posible afirmar que el uso de esta tecnología recientemente se ha multiplicado.
En su concepción más básica, una función de hashing es una función matemática que permite detectar la más mínima alteración en un documento electrónico, con la ingeniería para ser operada con un costo computacional muy bajo. Por ejemplo, este documento fue escrito en LATEX, una formidable herramienta open-source de composición de textos que se pue de descargar de https://tug.org/mactex/. Cuando descargué esta aplicación supe con certeza que esta pieza de software era original y no ha sido alterado porque al re-calcular la función de hash SHA-256 obtuve el resultado 7d0cf1 . . . 138 que el grupo autor de LATEX publicó en su sitio web. Si algún atacante malicioso hubiera alterado esta distribución para inocular algún tipo de malware, hubiera alterado el resultado del hash y podría detectarse la alteración.
Arboles de Merkle
Sobre este bloque constructor de funciones de hashing, Ralph Merkle propuso una estructura de datos supremamente creativa. Esta estructura de datos permite revisar alteraciones en una secuencia ordenada de mensajes de una manera muy eficiente. En los trazos originales de la patente, Merkle construye un árbol de 8 elementos, a cada uno de los cuales se le calcula individualmente el hash como se muestra abajo en la figura.
Luego se concatenan por parejas los resultados del hash, para crear un hash de la pareja y así sucesivamente hasta construir un árbol binario de log2(8) = 3 niveles.
Arboles de Merkle y redes P2P
La potencia de esta estructura de datos la hace muy conveniente en las descargas de documentos en redes peer-to-peer como torrent. Un documento a distribuir como torrent, se divide en múltiples pedazos que se esparcen por toda la red. El documento completo se identifica unívocamente con el hash de la raíz, mientras que su vez, cada pedazo individual se identifica con su propio hash.
Cuando el usuario decide descargar el torrent, su cliente P2P descarga individualmente y en paralelo cada pedazo y va construyendo los hashes de las ramas del árbol. Si alguna de las ramas intermedias el hash no coincide, los pedazos bajo el nodo se descartan, y se buscan y descargan de algún otro sitio, de manera que no es necesario descargar todos los pedazos antes de verificar si hay alguno dañado o alterado. Este recurso permite una gran eficiencia y velocidad en la descarga de documentos muy grandes, una ventaja que sin duda los usuarios torrent aprecian.
Arboles de Merkle y la blockchain
Un bloque de transacciones en la blockchain de Ethereum o de Bitcoin está formado por alrededor de un par de miles de transacciones, que colectivamente los usuarios de la criptomoneda han generado y esperan que sean minados. Al momento de escribir este documento, la blockchain de bitcoin tiene 624,887 bloques, mientras la blockchain de Ethereum tiene 9’827,523 bloques.
Para poder recorrer y buscar eficientemente una transacción específica en un bloque, se recurre al artificio de los árboles de Merkle que se ha descrito en previas secciones. Así,
con todas y cada una de las transacciones se construye un árbol binario y el hash raíz se almacena como parte del bloque minado.
Suponga en la figura que se desea verificar si la transacción HK está en el bloque. Una alternativa es recorrer secuencialmente las transacciones del bloque, hasta encontrar (o no) la transacción en el bloque. Un algoritmo bastante ineficiente toda vez que tiene carga lineal respecto al número de transacciones del bloque.
Es posible usar los árboles de Merkle como un mecanismo más eficiente para verificar la pertenencia de esta transacción al bloque. Primero se necesita el hash de la transacción HL, ya que con este resultado de hash se puede calcular el nodo común a estas dos transacciones (llamado HKL en la figura). Con este valor de hash HKL ya calculado, se necesita ahora el valor de hash HIJ para con el calcular el hash HIJKL.
Una vez se tenga calculado hash HIJKL, se necesita el valor de hash HMNOP , con el cual se calcula el hash HIJKLMNOP . Con este valor se necesita el hash HABCDEF GH para calcular finalmente el el hash de la raíz. Es decir, para verificar la pertenencia de la transacción HK se necesitan los valores de hash de HL, HIJ , HMNOP y HABCDEF GH. Solo cuatro valores o en términos más precisos de complejidad, es posible afirmar que con un algoritmo basado en los árboles de Merkle se tiene complejidad O(log2 L) con el número de transaccionesLdel bloque versus la complejidad del recorrido O(L − 1) del algoritmo inicial.
Consúltenos en B info@cyte.co acerca de las preguntas que pueda tener acerca del uso de esta tecnología para mejora de sus procesos de negocios.
Las imagenes usadas en esta nota fueron tomadas -en orden de aparición- de:
https://commons.wikimedia.org/wiki/File:Blockchain_Illustration.jpg,
https://patents.google.com/patent/US4309569A/en,
Imagen del autor.