Armando una Blockchain (5)

Published on Author lopezLeave a comment

Anterior Post
Siguiente Post

En esta semana pasada estuve trabajando bastante en mi proyecto personal:

https://github.com/ajlopez/BlockchainSharp

implementando una blockchain en C#, usando como es habitual el flujo de trabajo de TDD (Test-Driven Development). Un elemento que necesito implementar es el almacenamiento (store) de los estados de cuentas (en principio, voy a guardar sus balances). El balance de una cuenta debe poder ser recuperado por el id de la cuenta (un hash). Pero en muchos casos de uso, necesito conocer los balances de algunas cuentas a UN INSTANTE dado de tiempo. No es suficiente tener los balances de las cuentas al tiempo actual, solamente. Para cumplir con esos casos de uso, implementé un trie pero inmutable.

Un trie es un árbol donde los nodos no terminales almacenan parte de la clave:

En el ejemplo de la figura de arriba, el valor V1 está asociado con la clave AAA, y el valor V5 está asociado con la clave ACA. CUando cambio el valor asociado con la clave ABC desde V4 a V7, entonces, un nuevo trie es creado, manteniéndose el anterior sin modificarlo:

Puedo acceder el par original clave/valor usando a partir de la “vieja raíz” del trie, y cuando necesito valores más actuales, cambio a usar la “nueva raíz” del nuevo trie. Si algún nodo o porción del árbol queda inalcanzable, el recolector de basura liberará la memoria asociada.

La implementación del trie que tengo ahora es simple, y está basada en haber escrito los test e implementado el código que hace que los test pases. Un ejemplo de test:

[TestMethod]
public void PutAndGetKeyValue()
{
    Trie<string> trie = new Trie<string>();

    var trie2 = trie.Put("012", "foo");

    Assert.IsNotNull(trie2);
    Assert.AreNotSame(trie2, trie);
    Assert.IsNull(trie.Get("012"));
    Assert.AreEqual("foo", trie2.Get("012"));
}

Otro ejemplo que muestra que los tries mantienen sus valores, aún cuando se crean nuevos tries en cada actualización:

[TestMethod]
public void ReplaceValue()
{
    Trie<string> trie = new Trie<string>();

    var trie2 = trie.Put("012", "foo");
    var trie3 = trie2.Put("012", "bar");

    Assert.IsNotNull(trie2);
    Assert.AreNotSame(trie2, trie);
    Assert.IsNull(trie.Get("012"));
    Assert.AreEqual("foo", trie2.Get("012"));

    Assert.IsNotNull(trie3);
    Assert.AreNotSame(trie3, trie2);
    Assert.AreEqual("bar", trie3.Get("012"));
}

Mi idea es usar Trie<AccountState> como un almacén de los estados de cuenta. Al final del proceso de cada bloque y de cada transacción, habrá un trie de estado de cuentas. Y al final del siguiente bloque, habrá otro trie, con los balances actualizados. En cualquier momento, puedo recuperar los estados de las cuentas al final de bloque 1, o al final del bloque 2, partiendo de los respectivos tries.

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 *