El estado: clave-valor, trie radix-16 y raíz de estado

Un equipo de tesorería muestra en su panel el saldo de una cuenta en una cadena Substrate (Polkadot SDK). El dato llega de un nodo RPC que opera un proveedor externo. Un auditor pregunta: "¿cómo sabes que ese número es el que está en la cadena y no el que el proveedor quiso darte?". Descargar todo el estado para comprobarlo no es una respuesta. La respuesta correcta es pedir, junto con el valor, una prueba que se pueda verificar contra un número de 32 bytes que está en la cabecera del bloque.

Este capítulo explica de dónde sale ese número, cómo se organiza el estado para que la prueba sea pequeña y qué decisiones de diseño la hacen crecer o encoger.

Bytes que el nodo guarda y no entiende

La documentación del SDK describe el estado como una base de datos clave-valor: todo lo que la función de transición necesita conservar se escribe ahí. [1] Las claves y los valores son secuencias de bytes, y el nodo no sabe interpretar la mayoría de ellas.

Esa ignorancia es deliberada. El documento del protocolo Wasm lo resume en dos frases: el estado se guarda en el lado del nodo, pero el runtime es el único componente que puede actualizarlo y el único que puede interpretarlo por completo. [2] Para el nodo, un saldo y un voto de gobernanza son lo mismo: bytes bajo una clave.

Si recuerdas el runtime en Wasm, ya conoces la consecuencia: como el nodo no depende del formato de los datos, el runtime puede cambiar ese formato sin que el nodo se entere. Esa opacidad es la razón de fondo por la que una cadena Substrate puede actualizarse sin fork, y el capítulo de actualizaciones vuelve sobre ella.

Las pocas claves que el nodo sí conoce

Hay excepciones. Un puñado de claves well-known tienen un significado fijo que el nodo conoce. La más importante es :code, donde vive el propio runtime en Wasm. Las demás están en el crate sp-storage: [3]

• :code: el blob Wasm del runtime.
• :pending_code: un runtime nuevo que se aplicará en un bloque posterior.
• :heappages: cuántas páginas de memoria le da el nodo al runtime.
• :extrinsic_index: el índice del extrinsic que se está aplicando.
• :child_storage:: el prefijo bajo el que se cuelgan los child tries.

Todas empiezan con dos puntos. Ninguna clave de FRAME empieza así, porque las de FRAME son hashes, y eso evita choques.

Cómo arma FRAME una clave de storage

Un pallet no escribe claves a mano. Declara un StorageValue o un StorageMap y FRAME construye la clave. La regla, según frame-support, es que toda clave empieza por twox128(pallet_prefix) ++ twox128(STORAGE_PREFIX): el hash del nombre de la instancia del pallet en el runtime y el hash del nombre del item. [4] En un mapa, a ese prefijo se le suma el hash de la clave del mapa.

clave = twox128("Balances") ++ twox128("Account") ++ blake2_128_concat(account_id)
        \_______ 16 B _______/  \______ 16 B ______/  \__ 16 B + la clave en claro __/

El ejemplo es ilustrativo: los nombres reales del pallet y del item dependen del runtime. El diseño tiene dos efectos útiles. Todos los items de un pallet comparten prefijo, así que viven en la misma rama del trie y se pueden recorrer o borrar juntos. Y el hash de la clave del mapa reparte las entradas de manera uniforme.

La elección del hasher es una decisión de seguridad, no de estilo. La regla práctica de la documentación: si la clave la controla el usuario final, usa un hasher criptográfico como Blake2; si no la controla o ya es criptográfica (por ejemplo, un AccountId), un hasher rápido como Twox basta. [4] Si un atacante elige claves que comparten prefijo, desequilibra el trie y alarga las rutas: las lecturas y las pruebas se encarecen para todos. Las variantes _concat guardan la clave en claro después del hash, lo que permite recuperarla al iterar.

El trie radix-16 y la raíz de estado

Una lista de pares clave-valor no se puede resumir en un número de forma eficiente si hay que volver a hashear todo en cada bloque. Por eso la especificación ordena el estado en un trie radix-16: un árbol donde cada nodo tiene hasta 16 hijos. [5]

La clave se parte en nibbles de 4 bits; cada nibble elige uno de los 16 hijos al bajar por el árbol. Hay dos clases de nodo. Un branch tiene uno o más hijos y puede guardar además un valor; un leaf no tiene hijos. Cuando un tramo del camino no se bifurca, la especificación lo comprime en una clave parcial guardada en el nodo, para no gastar un nodo por nibble cuando el espacio de claves es disperso.

Cada nodo tiene un valor de Merkle. Si la codificación del nodo ocupa menos de 32 bytes, se usa tal cual; si ocupa 32 o más, o si el nodo es la raíz, se usa su hash Blake2b. Un branch incluye en su codificación los valores de Merkle de sus hijos, de modo que cualquier cambio en una hoja cambia todos los nodos hasta la raíz.

El valor de Merkle de la raíz es el state_root, uno de los cinco campos de la cabecera de un bloque, junto a parent_hash, number, extrinsics_root y digest. [5] Cuando el nodo importa un bloque, ejecuta el runtime, recalcula la raíz y la compara con la que trae la cabecera. Si no coinciden, el bloque es inválido.

Figura 1

Una prueba de almacenamiento en el trie radix-16

Fuentes:

[5]

Cómo leer esta figura

A la izquierda, una clave de storage se divide en nibbles de 4 bits; los primeros nibbles corresponden al prefijo del pallet. En el centro, un trie de tres niveles: la raíz, dos branches y varias hojas. El camino de la raíz a la hoja buscada está resaltado en ciruela y numerado 1, 2 y 3; los nodos fuera del camino aparecen en gris y se marcan como representados solo por su hash dentro del branch. Arriba a la derecha, la cabecera del bloque muestra parent_hash, number, state_root, extrinsics_root y digest, con state_root unido a la raíz del trie. Abajo a la derecha, el verificador recibe los tres nodos del camino, recalcula los hashes de abajo hacia arriba y compara el resultado con state_root.

Descargar SVGDescargar .tex

Código TikZ

Abrir `.tex` en otra pestaña

Probar un valor sin descargar el estado

Volvamos al auditor. Para probar el saldo, el proveedor entrega los nodos del camino desde la raíz hasta la hoja de esa cuenta. El verificador decodifica la hoja, sube al branch, comprueba que el valor de Merkle de la hoja aparece en la posición correcta, y así hasta la raíz. Si el resultado coincide con el state_root de una cabecera en la que confía, el valor está probado.

La prueba no necesita los hermanos completos. Cada branch ya contiene los valores de Merkle de sus hijos, así que el resto del árbol entra en la prueba solo como hashes. El tamaño crece con la profundidad del camino y con el tamaño de cada branch, no con el tamaño total del estado.

Dos decisiones de la especificación ayudan a mantenerla pequeña. Los nodos de menos de 32 bytes se incrustan sin hashear. Y, con la versión de cálculo de raíz que hashea valores, todo valor de más de 32 bytes se reemplaza en el nodo por su hash. [5] Así, probar una clave vecina de un valor grande no obliga a cargar ese valor. Cómo se llama esa versión en el código del SDK (la llamada state version) y qué versión usa cada red es un dato a validar en el runtime concreto.

Esta misma mecánica reaparece más adelante. Los light clients verifican saldos así en sincronización y light clients, y una parachain envía a la relay chain la prueba de cada clave que su bloque tocó, cuyo tamaño se mide como la dimensión proof_size del peso.

Child tries: estado aislado con su propia raíz

A veces un runtime maneja muchas instancias del mismo tipo de objeto, cada una con sus propias claves, y quiere aislarlas. Para eso existen los child tries: tries independientes cuya raíz se guarda como un valor dentro del trie principal, bajo una clave con el prefijo :child_storage:. [5]

Cada vez que cambia un child trie hay que recalcular primero su raíz y después la del estado principal. La ventaja es que se puede probar o borrar una instancia entera sin tocar el resto. La especificación cita parachains y contratos como usos típicos.

Qué cambia respecto de Ethereum

El estado de Ethereum y su Merkle Patricia Trie es el pariente más cercano, y conviene marcar las diferencias para no trasladar intuiciones equivocadas.

La diferencia de fondo es quién define la forma del estado. En Ethereum la forma la fija el protocolo: cuentas con cuatro campos. En Substrate la fija el runtime: el nodo ve un único espacio de claves, y cada pallet decide qué guarda y cómo.

Decisiones de diseño del storage

Con el estado en la cabeza ya se puede hablar de su costo. Cada lectura y escritura del storage es trabajo que el bloque tiene que pagar, y en una parachain también es tamaño de prueba. El siguiente capítulo, pesos y comisiones, mide ese trabajo antes de ejecutar. El anterior, extrinsics, muestra qué entra al bloque y termina escribiendo en este trie.