Angel \”Java\” Lopez on Blog

June 6, 2016

Building A Blockchain (12)

Previous Post
Next Post

In a previous post I described the C# implementation of an immutable trie. I need the trie structure to keep the state of accounts in the blockchain: their balance could be retrieved by account public address. The structure should be immutable, so I can retrieve the account states at different times. Each trie has the states of all accounts at a given time. Having an immutable trie, each time I added a value to a key, a new trie is created, and the old one can be still available.

These days, I added a trie implementation to my personal blockchain project written in JavaScript/NodeJS:

https://github.com/ajlopez/SimpleBlockchain

The implementation was written using TDD (Test-Development Driven) workflow. I have simple tests like:

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

Using a dynamic language like JavaScript, without type declaration for variables and arguments, I was able to write a simple implementation, as a function:

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

Each value has a key. I created a tree of tries. To add a value using a key, I added the value to the tree, using each letter in the key to traverse the trie internal tree. In a typed language, I should declare the type of keys and values, but using JavaScript, only the algorithm is important: the declaration of types is not needed to write the code.

The offset argument is used to select the character in the key. So, if the key has four characters, the value is saved in a composite trie with four levels.

This is a simple implementation, and I could improve it, having new use cases, writing new tests describing the expected behavior. Some things to add: persistent to disk/file/database, and hash by trie. Each processed block and transaction would have the hash of their resulting states, so I could retrieve it at any moment, and check if the block, after its processing, reach the same state.

When a new block is built, the initial state from parent block is known, and each transaction in the block had the hash of its final state. In this way, the block execution consistency can be checked against the output states.

Next posts: block and transaction processing, storage and validation.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

2 Comments »

  1. […] Previous Post Next Post […]

    Pingback by Building A Blockchain (11) | Angel "Java" Lopez on Blog — June 6, 2016 @ 9:02 am

  2. […] Previous Post […]

    Pingback by Building A Blockchain (13) | Angel "Java" Lopez on Blog — June 13, 2016 @ 9:31 am


RSS feed for comments on this post. TrackBack URI

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: