¿Qué es un árbol de merkle?

Un árbol Merkle es una estructura de datos dividida en varios niveles que están relacionados como nodos de una raíz única. Los árboles de Merkle permiten relacionar una gran cantidad de datos en un único punto (Merkle Root) y permite con ello que no sea necesario el almacenaje de todos ellos para una posterior verificación.

Para lograr esto cada nodo debe estar identificado con un hash. Estos nodos iniciales, llamados nodos hijos u hojas, se asocian luego con un nodo superior llamado nodo padre o rama, que no es más que otro hash generado con los hashes hijos. El proceso se parece a la encadenación entre bloques que se realiza en una blockchain. Esta estructura se repite hasta llegar a un nodo final llamado raíz o raíz de Merkle (Merkle Root), que con nuestro ejemplo sobre la blockchain representaría al último bloque, cuya impronta de todos los datos anteriores estará representada con el hash heredado.

De esta forma, la verificación y validación de unos datos puede ser muy eficiente y barata. Solo es necesario registrar en el contrato la raíz de los datos.

Este diseño fue creado por Ralph Merkle, en el año de 1979, con el fin de agilizar el proceso de verificación de grandes cantidades de datos.

Usaremos la red Binance Smart Chain

Lo primero, deme su permiso para conectarme a su Metamask. La conexión automática de su metamask por parte de una dAPP es una mala práctica. Téngalo en cuenta a la hora de crear la suya.

Si no tiene BNBs de prueba para hacer el tutorial apriete el botón azul para poder reclamar tokens y así poder pagar las transacciones.

Ejemplo de árbol de merkle

Para que compruebe su funcionamiento vamos a comprobar si existe un dato de los siguientes con el panel que encontrará a su izquierda del texto:

0x1C541e05a5A640755B3F1B2434dB4e8096b8322f, 0x1071258E2C706fFc9A32a5369d4094d11D4392Ec, 0x25f7fF7917555132eDD3294626D105eA1C797250, 0xF6574D878f99D94896Da75B6762fc935F34C1300, 0xfDbAb374ee0FC0EA0D7e7A60917ac01365010bFe, 0xfB73f8B1DcD5d61D4dDC3872dA53200B8562F243, 0x95F6E4C94857f605b9A73c9163D5c94AAf849c40, 0xEd2C82417256DF74a995213713A586E07d3e5255, 0xCb14d0D43BB32705fAbbD863f860A1410fa14613, 0x7a865e44988a2ebcad845E977db07C71f8c62d31, 0x340F5bEcB63a33B53959026d0CEb1f83C53A102F, 0x969560dBBf4872049D0d245791eD74dEd0D66578, 0x81B8888dfbdcc3Ad1dfe30A6f58a6d47eaf99aE8, 0x29aB6E246c4aC305974A730B10459417FF65D469, 0x2B790Dd5d9440f098E057E4958e3Ac0214712352, 0xA53E16be846D815dfF774A384858021952b5B22E, 0x04473648f6BeA9b074DFd7693b20AFCF9971a125, 0xc26716b827c0d207AA3D25667028C2da1De787bf, 0x21BAa9441e2DF389Ca27c9dB1cD9B59f2504dfEa, 0x93D5193694a49eB85366ea1BDa69B577f1b878ae, 0x3654322cFecCD60965A8b7866f50e55FE14EEBCC, 0x174BAFfcB004ACfc53cDD3A48957b9D353BB171f, 0x1d9A510DfCa2b1f3C52BD81122816FD86C7C7Ba0, 0x55ae457519BbAf25d825772da81F57bD18E4B6Db, 0x0997680928431EA22C1930c12Dc91f06d10be0c6, 0xF9E8383bd1250aCf18Da971467B70045d4D06fB1, 0x847aB63F94e931F9264407C54C97DbCfFEC9f8FE, 0x5dcE9Fc14eED67D046A130d1d991163114b2820c, 0x53b5585AA42b79B0b8e620896ceB0D0435441071, 0x5E661e550Fcac43DEC925449A7F0bCA0C32D6A44, 0xA46f327d91282aFD4E99d79a8fD7Eac7A123dAF5, 0xD03241a89a18c779B71f1bD348d2BbF1e20b8ea8, 0xed0850a960ABE5715ECEa4b479272092733922f0, 0x4D15f921A25e8677Da2d878B01c80Df861E67F03, 0x98d450BfbBFD64D780B632f6acd0FC59d11E575e, 0xaef0FfA370108915d4198Fe6eF40eBa446f00d79, 0x5Bc46cf525E6E26f8799685E5247a93355354cBf, 0x5B9837c339F7b55564Aeb185e8DEdeEDD10AfcB7, 0xbda8049200F7a42312AFeBDb5b99D514EE0df302, 0x5B38Da6a701c568545dCfcB03FcB875f56beddC4, 0x322d9e3F049a845e9C8ED089B2Bdf8F33c65a08F

Coloque una dirección de la lista vigilando no dejar ningún espacio. Seguidamente apriete el botón "Comprobar dato". Haga lo propio ahora con una dirección ajeno a la lista compartida.

Las búsquedas se generarán y si encuentra la dirección aparecerá un check, en caso contrario le avisará de su inexistencia. Si quiere ver el árbol junto a su prueba abra la consola javascript . Esta prueba es "la ruta de hashes" correcta empezando por la hoja más baja: su dato compartido. Si al realizar la comprobación su dato no genera un hash existente todos los demás fallarán en cascada devolviendo un array vacio.

Ejemplo con Solidity: Whitelist de compra de NFTs

Generalmente, la generación de una whitelist para compra o acceso a un proyecto suele ser recabada por medios tradicionales offChain. Esto suele ser un quebradero de cabeza para los desarrolladores Web3. Ya que nosotros consideramos más seguro y eficiente un registro directo sobre el contrato. Es decir, que cada usuario que desee estar en la whitelist pase por la dApp y se registre el mismo en el contrato. Con ello evitamos errores o reclamaciones. Pero una cosa es como se debería hacer y otra cosa es como se "suele hacer". Aplicando el principio de que "aquí, se ha hecho siempre así" los desarrolladores blockchain no tenemos otra que saber conectar con "las viejas prácticas".

Una de las soluciones para no tener que registrar en bruto una base de datos de cuentas priviliegiadas es con el uso de éste árbol de merkle. Recabada las direcciones de la forma tradicional, se registrarán en un array para generar la correspondiente root. A partir de ahí, el contrato verificará la dirección que le llame con la prueba de merkle correspondiente.

Vamos a verlo detenidamente.

Primeramente generaremos un array de direcciones en las que ha de introducir alguna que usted posea. Introduzca una a una estos datos en el campo "Introduzca dirección" del panel "Registro Array" y apriete "Registrar dato" tantas veces como direcciones desee registrar. Así se creará el array con el que generará su base de datos a verificar. Recuerde que si actualiza la página los datos registrados se perderán.

Cuando considere que ha introducido todos los datos que desee verificar apriete el botón de "Conseguir raíz". Aparecerá entonces tando debajo como en el campo "Root" del siguiente panel de interración con el contrato de NFTs.

A continuación tendrá que registrar su raíz en el contrato de NFTs. Como éste es un contrato con fines educativos en el se permite tantos registros como usuarios interactuen con el. Evidentemente esto no es funcional para un contrato que pretende verificar una lista segura. Por lógica tendría que estar solo accesible para el owner o cuenta con role admin. También he dejado en el contrato un acceso público a la función de validación del árbol de merkle: "isValid", para que usted pueda hacer pruebas con el contrato desde Remix.

Registrada la raíz en el contrato intente ahora adquirir un NFT con una cuenta que haya registado en su base de datos. Si la dirección estaba en los datos introducidos por usted le permitirá la compra gratuita en nuestro ejemplo. En caso contrario le rechazará la transacción.