Mundos grandes 100% On-Chain. ¿Es posible?

Dark Forest ha demostrado que los mapas generados proceduralmente pueden ser atractivos para jugadores y al mismo tiempo representan un costo bajo de almacenamiento on-chain. Sin embargo, en su artículo sobre procgen, Nalin y Gubsheep (desarrolladores de Dark Forest) mencionan que crear mapas hechos a mano on-chain presenta desafíos significativos. Inspirado por esto, decidí buscar una forma escalable de almacenar grandes mapas hechos a mano en ethereum.

En este tutorial, exploraremos tanto la teoría como la práctica de crear mapas a mano completamente on-chain. Crearemos un juego donde el mapa contiene obstáculos (montañas) almacenados en un Árbol de Merkle optimizado para la compresión de datos. Los jugadores deberán enviar pruebas de inclusión de Merkle para avanzar.

Prefer to see the complete code? Head to Github to find all the code mentioned in this guide.

Comencemos con un mapa simple donde 0 representa el pasto y 1 representa las montañas. El jugador solo puede caminar sobre el pasto.

Nuestra primera intuición podría ser declarar un mapping bidimensional y poblarlo de esta manera:

mapping(uint x => mapping(uint y => terrainType)) map;
map[1][0] = 1;
map[2][2] = 1;
map[2][3] = 1;
map[0][3] = 1;

Sin embargo, esto es impráctico para mapas grandes debido a los altos costos de gas y las limitaciones del tamaño de los bloques. Para almacenar mapas más grandes on-chain de manera eficiente, necesitamos algo más escalable: los Árboles de Merkle.

En este tutorial, transformaremos un mapa bidimensional en un árbol de Merkle. Los jugadores probarán su posición enviando una prueba de inclusión de Merkle para el tipo de terreno en el que se encuentran.

Merkleizar un mapa permite pruebas en tiempo logarítmico, en lugar de lineal. Sin embargo, antes de merkleizar, debemos convertir el mapa en un arreglo unidimensional utilizando la siguiente fórmula:

$text{LEAF{textunderscore}INDEX} = y times text{MAP{textunderscore}WIDTH} + x$

Merkleizar un arreglo unidimensional es más sencillo que hacerlo para un mapa bidimensional. El proceso implica hacer un hash de los elementos adyacentes (posiciones 0 y 1, 2 y 3, etc.) y lego las ramas hasta llegar a la raíz de Merkle.

Cuando el juego comienza, los únicos datos guardados on-chain son la raíz de Merkle. A medida que los jugadores se mueven, envían pruebas Merkle para verificar sus movimientos. Esta técnica distribuye el costo de almacenar el mapa entre todos los jugadores, en lugar de colocar toda el costo en el deployer.

Comencemos creando un nuevo proyecto de MUD, la herramienta para crear mundos autónomos en Ethereum.

curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.39.7/install.sh | bash nvm install 20
curl -L https://foundry.paradigm.xyz | bash export PATH=$PATH:~/.foundry/bin
sudo npm install -g pnpm

Una vez listo, crea una plantilla de Phaser.

pnpm create mud@latest tutorial --template phaser
cd tutorial

Para esta demostración probaremos un mapa de 32×32 que definiremos en el siguiente archivo público.

{
    "map": [
        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
        [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
        [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]
}

Nuestra tabla consistirá en la posición de los jugadores, donde cada cuenta de Ethereum puede controlar solo un jugador. También habrá un Singleton que mantendrá la raíz de Merkle del mapa como un commitment, de modo que nadie pueda hacer trampa más adelante en el juego.

Primero, eliminemos los archivos innecesarios.

Ahora vamos guardamos la raíz como commitment en nuestro script de PostDeploy. Ten en cuenta que si cambias los datos del mapa, esto generará una nueva raíz de Merkle. En caso desees probarlo, imprimo la raíz en la terminal para que puedas obtenerla desde allí fácilmente.

También, define la lógica del movimiento on-chain. Fíjate cómo verificamos las pruebas de inclusión Merkle para saber si el personaje está caminando en el pasto o la montaña.

Modifiquemos el MapSystem que viene por defecto para que interprete nuestro map.json.

Por simplicidad, en este demo establecemos la cámara fija en la posición 0,0 arriba a la izquierda.

Instala la dependencia en ethers.

Corre el juego.

En lugar de usar datos simples como 0 y 1, podemos codificar información más compleja en cada posición sin aumentar el costo de gas. Por ejemplo, podríamos codificar la siguiente estructura:

Para ahorrar gas, los jugadores deberían enviar una prueba de Merkle solo una vez. Todos los resultados deberían almacenarse, de modo que los jugadores futuros puedan consultar las zonas del mapa que ya han sido exploradas sin necesidad de volver a enviar una prueba Merkle.

La solución mostrada en este artículo escala bastante bien debido a que los costos de verificación aumentan de manera logarítmica en realación al tamaño del mapa. Por ejemplo, hice la siguiente prueba:

Como puedes ver, el tamaño del mapa no afecta demasiado al costo de gas. El resto de la lógica en la función move es más significativa.

Para esta prueba, utilicé este mapa cuya raíz de Merkle se calcula como 0x86f3820289c9335418aaa077ba6a1dc6ab512203cc1faecb450bfbfe64021e98.

Habiendo dicho esto, para mapas más grandes se necesitará un backend especializado en indexación que pre-calcula todas las pruebas de inclusión de Merkle del mapa para que los jugadores puedan consultarlas. Esto sería un servidor estilo backend Web clásico, con una API que los jugadores puedan consultar o correrla localmente ellos mismos.

Sígueme en dev.to y en Youtube para todo lo relacionado al desarrollo en Blockchain en Español.

Source link
lol