Building A Blockchain (5)

Previous Post
Next Post

I was working a lot on my personal project:

https://github.com/ajlopez/BlockchainSharp

implementing a blockchain in C#, using TDD (Test-Driven Development) workflow. One element I need to implement, is the store of account states (initially their balances). The balance of an account should be retrieved by account id (a hash). But in many use cases, I need to know the balances of accounts at a given time. It is not enough to have the LATESTS balances. So, I implemented a data structure, a trie, but with immutable properties.

A trie is a tree where the non-leaf nodes stores part of the key:

In the above example, the value V1 is associated with key AAA, and the value V5 is associated with key ACA. When I change the value associated with key ABC from V4 to V7, part of a new trie is created, so the original one persists without modification:

I can access the original key/values using the “old root”, and then, I can switch to use the “new root”, at any moment. If any node/root is not reachable from a variable, garbage collector will release the memory associated with that node.

I wrote a typed trie implementation, using TDD. An example 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"));
}

An example that shows the persistent of tries after updates:

[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"));
}

My idea is to use Trie<AccountState> as a store for account balances. At the end of a block (with transactions) processing, there is an account state trie. Ant the end of the next block processing, another trie will be generated. At any moment, I could retrieve the account balances at time “block 1”, and at time “block 2”, using the generated tries.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

5 thoughts on “Building A Blockchain (5)

  1. Pingback: Building A Blockchain (4) | Angel "Java" Lopez on Blog

  2. Pingback: Building A Blockchain (6) | Angel "Java" Lopez on Blog

  3. Pingback: Building A Blockchain (12) | Angel "Java" Lopez on Blog

  4. Pingback: Scaling Ethereum/RSK (1) | Angel "Java" Lopez on Blog

  5. Pingback: Multi-Blockchains in Ethereum/RSK | Angel "Java" Lopez on Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s