Armando una Blockchain (12)

Published on Author lopezLeave a comment

Anterior Post
Siguiente Post

En un anterior post describí la implementación en C# de un árbol inmutable. Necesito un estructura llamada trie para mantener el estado de las cuentas en la blockchain: sus balances pueden ser recuperados usando la dirección pública de la cuenta. La estructura debería ser inmutable para poder recuperar fácilmente los estados de las cuentas en distintos instantes del tiempo. Cada trie tiene los estados de todas las cuentas en un determinado instante. Al ser inmutable, cuando se agrega un valor, un nuevo trie es creado y el original todavía sigue estando disponible.

En estos dias he agregado una implementación de trie a mi proyecto personal de blockchain escrito en JavaScript/NodeJS:

https://github.com/ajlopez/SimpleBlockchain

La implementación fue escrita usando el flujo de trabajo de TDD (Test-Development Driven). Tengo tests simples como:

exports['put data and get data'] = function (test) {
    var trie = tries.trie();
    
    var result = trie.put('0123', 42).get('0123');
    
    test.ok(result);
    test.equal(result, 42);
};

exports['put two new data and retrieve them'] = function (test) {
    var trie = tries.trie();
    
    var result = trie.put('0123', 42)
        .put('3210', 1);
    
    test.ok(result);
    test.equal(result.get('0123'), 42);
    test.equal(result.get('3210'), 1);
    test.equal(trie.get('0123'), null);
    test.equal(trie.get('3210'), null);
};

Usando un lenguaje dinámico como JavaScript, sin declaración de tipos para las variables y argumentos, pude escribir una implementación muy simple, como una función:

function Trie(values) {
    if (values == null)
        values = [];
        
    this.get = function (key, offset) {
        if (offset == null)
            offset = 0;
            
        var ky = key[offset];
        
        if (offset === key.length - 1)
            return values[ky];
        else if (values[ky])
            return values[ky].get(key, offset + 1);
        else
            return null;
    };
    
    this.put = function (key, data, offset) {
        if (offset == null)
            offset = 0;
        
        var newvalues = values.slice();
        var ky = key[offset];
        
        if (offset === key.length - 1)
            newvalues[ky] = data;
        else {
            if (!newvalues[ky])
                newvalues[ky] = new Trie();
                
            newvalues[ky] = newvalues[ky].put(key, data, offset + 1);
        }
            
        return new Trie(newvalues); 
    };
}

Cada valor tiene una clave (key). Creo un árbol de tries. Para agregar un valor usando una clave, agrego el valor al árbol, usando cada letra en la clave para recorrer el árbol interno del trie. En un lenguaje tipado, debería declarar el tipo de las claves y valores. Pero usando JavaScript, solamente el algoritmo es importante: la declaración de los tipos no es importante para escribir el código.

El argumento offset es usado para seleccionar el caracter de la clave. Así, si la clave tiene cuatro caracteres, el valor es guardado en un trie compuesto de cuatro niveles.

Esta es una implementación simple, que puedo mejorar, escribiendo nuevos tests con la conducta esperada. Algo para agregar: persistencia a disco/archivo/base de datos, y calcular hash por trie. Cada bloque procesado y cada transición tendría un hash con los estados resultados, así puedo recuperar el árbol usando el hash. Y cada bloque tendría el hash del estado esperado al terminar su proceso. Si ese hash del bloque no coincide con el hash del árbol calculado por aplicar las transacciones del bloque, entones no es válido lo que estamos calculando. Todos los nodos de la red está revisando cada bloque que agregan a la blockchain, controlando que los estados resultantes sean los esperados por el que calculó por primera vez un bloque.

Cuando un nuevo bloque es construido, se usa como estado inicial el estado final del bloque padre, se aplica cada transacción a ese estado, y el hash del estado final se guarda con el bloque. De esta forma, todos pueden controlar que cada bloque queda en el mismo estado para todos los nodos de la red, manteniendo la coherencia de los estados de las cuentas, o sea, sus balances.

Próximos posts: proceso de transacciones y bloques, almacenamiento y validación.

Nos leemos!

Angel “Java” Lopez
http://www.ajlopez.com
http://twitter.com/ajlopez

Leave a Reply

Your email address will not be published. Required fields are marked *