Angel \”Java\” Lopez on Blog

July 11, 2016

Building A Blockchain (14)

Previous Post

After a while, I’m back, working on my personal blockchain projects:

https://github.com/ajlopez/SimpleBlockchain
https://github.com/ajlopez/BlockchainSharp

Today I want to present my first tests to model a miner. A miner should mine blocks, adding transactions to it, building a child block from a given parent. There are many issues to solve: transactions should be valid, a transactions should be mined only once, etc… But, following TDD (Test-Driven Development) workflow, I can add functionality guided by tests. My first test:

exports['mine empty block'] = function (test) {
    var txs = transactions.txs();
    var miner = miners.miner(txs);
    
    var states = tries.states();
    var genesis = blocks.block();
    
    var result = miner.mine(genesis, states);
    
    test.ok(result);
    test.ok(result.hash);
    test.ok(result.transactions);
    test.ok(Array.isArray(result.transactions));
    test.equal(result.transactions.length, 0);
    test.ok(result.parentHash);
    test.equal(result.parentHash, genesis.hash);
};

After implementing the minimal code to past the test, I wrote and complete a second test:

exports['mine block with transaction'] = function (test) {
    var from = utils.hash();
    var to = utils.hash();
    var value = 1000;

    var states = tries.states().put(from, { balance: 3000 });
    var tx = transactions.transfer(from, to, value);
    
    var txs = transactions.txs();
    txs.add(tx);

    var miner = miners.miner(txs);
    
    var genesis = blocks.block();
    
    var result = miner.mine(genesis, states);
    
    test.ok(result);
    test.ok(result.hash);
    test.ok(result.transactions);
    test.ok(Array.isArray(result.transactions));
    test.equal(result.transactions.length, 1);
    
    test.equal(result.transactions[0].from, from);
    test.equal(result.transactions[0].to, to);
    test.equal(result.transactions[0].value, 1000);
    
    test.ok(result.parentHash);
    test.equal(result.parentHash, genesis.hash);
};

This second test is bit weak yet. Some issues: it doesn’t enforce the validation of the transaction to process, and it is not clear what happen to that transaction after added to the block. But these pending issues should be tackled in future tests, describing the expected behavior.

The interesting face of such workflow, is that implementation is created using the simplest path, after the test descriptions.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

July 4, 2016

New Month’s Resolutions: July 2016

Filed under: Blockchain, C Sharp, JavaScript, NodeJs, Open Source Projects — ajlopez @ 11:24 am

It’s time to write down my new month’s resolutions, and to review the past month’s ones.

– Improve WangTiles [pending]
– Improve WangTilesJS [complete] see repo
– Improve CrysSharp  [complete] see repo
– Improve GoSharp [pending]
– Improve SimpleForth [complete] see repo
– Improve BlockchainSharp [complete] see repo
– Improve SimpleBlockchain [complete] see repo

Additionally, I worked on:

– Improve CrysJS [complete] see repo

My new resolutions:

– Improve WangTiles
– Improve WangTilesJS
– Improve CrysSharp
– Improve CrysJS
– Improve SimpleForth
– Improve BlockchainSharp
– Improve SimpleBlockchain

Stay tuned!

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

June 13, 2016

Building A Blockchain (13)

Filed under: Bitcoin, Ethereum, JavaScript, NodeJs, Open Source Projects — ajlopez @ 9:31 am

Previous Post
Next Post

An important piece of a blockchain a la Ethereum, is the execution of transfer transactions. Each account has a public address and a state containing its balance. The account states are stores in immutable tries. This week I worked on my personal blockchain project written in JavaScript/NodeJS:

https://github.com/ajlopez/SimpleBlockchain

to execute a transference between accounts. As usual, my development workflow follows TDD (Test-Driven Development). My first test:

exports['execute transfer'] = function (test) {
    var from = utils.hash();
    var to = utils.hash();
    var value = 1000;

    var states = tries.states().put(from, { balance: 3000 });

    var tx = transactions.transfer(from, to, value);
    
    test.ok(tx);
    test.equal(tx.from, from);
    test.equal(tx.to, to);
    test.equal(tx.value, value);
    
    var newstates = transactions.execute(tx, states);

    test.ok(newstates);
    
    var oldfromstate = states.get(tx.from);
    
    test.ok(oldfromstate);
    test.equal(oldfromstate.balance, 3000);
    
    var oldtostate = states.get(tx.to);
    
    test.ok(oldtostate);
    test.equal(oldtostate.balance, 0);
    
    var newtostate = newstates.get(tx.to);
    
    test.ok(newtostate);
    test.equal(newtostate.balance, 1000);
    
    var newfromstate = newstates.get(tx.from);
    
    test.ok(newfromstate);
    test.equal(newfromstate.balance, 2000);
}

After the execution of the transaction, a new account states trie is returned. But I should reject transfers that have no enough funds:

exports['execute transfer without funds'] = function (test) {
    var from = utils.hash();
    var to = utils.hash();
    var value = 1000;

    var states = tries.states();

    var tx = transactions.transfer(from, to, value);
    
    test.ok(tx);
    test.equal(tx.from, from);
    test.equal(tx.to, to);
    test.equal(tx.value, value);
    
    var newstates = transactions.execute(tx, states);

    test.equal(newstates, null);
    
    var oldfromstate = states.get(tx.from);
    
    test.ok(oldfromstate);
    test.equal(oldfromstate.balance, 0);
    
    var oldtostate = states.get(tx.to);
    
    test.ok(oldtostate);
    test.equal(oldtostate.balance, 0);
}

My current simple implementation is:

function execute(tx, states) {
    var fromstate = states.get(tx.from);
    var tostate = states.get(tx.to);

    fromstate.balance -= tx.value;
    
    if (fromstate.balance < 0)
        return null;
        
    tostate.balance += tx.value;
    
    return states.put(tx.from, fromstate).put(tx.to, tostate);
}

Next posts: executing a block with its transactions, storing the state tries, etc…

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

June 8, 2016

New Month’s Resolutions: June 2016

Filed under: Blockchain, C Sharp, JavaScript, NodeJs, Open Source Projects — ajlopez @ 9:01 am

Let’s review my previous new month’s resolutions:

– Improve WangTiles [pending]
– Improve WangTilesJS [complete] see repo
– Improve CrysSharp [complete] see repo
– Improve BlockchainSharp [complete] see repo
– Improve SimpleBlockchain [complete] see repo
– Prepare and give a Bitcoin related talk [complete]

I also worked on:

– Improve SimpleForth [complete] see repo

My new month’s resolutions:

– Improve WangTiles
– Improve WangTilesJS
– Improve CrysSharp
– Improve GoSharp 
– Improve SimpleForth
– Improve BlockchainSharp
– Improve SimpleBlockchain

Stay tuned!

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

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

May 30, 2016

Building A Blockchain (11)

Previous Post
Next Post

I refactored the blockchain implementation in my personal JavaScript/NodeJS project:

https://github.com/ajlopez/SimpleBlockchain

In the previous post I showed some tests I wrote using TDD (Test-Driven Development) workflow. Now, I want to show the current implementation, that is an evolution from the past week one.

The implementation is at:

https://github.com/ajlopez/SimpleBlockchain/blob/master/lib/blockchains.js

There is a JavaScript “class”, implemented as a function:

function Blockchain(block) {
    var self = this;
    var blocks = [block];
    var blockstore = stores.blockstore();
    blockstore.save(block);
    
    this.bestBlock = function () { return blocks[blocks.length - 1]; }

In my new implementation, I’m using a block store. This object was able to save a block, and retrieve a block by hash, or retrieve the blocks with same number. But now, I added the retrieve by parent hash: that is, given a block hash, blockstore can retrieve all its know children. Given such functionality, the blockchain implementation evolved to use that feature. In this way, I don’t need to have a tree of blocks: given a block, I can retrieve all the tree of its descendants, from the blockstore.

Notice that the state of the blockchain has a naive implementation: only a JavaScript array, where the index coincides with the block number, starting with genesis block having 0 as number. My plan is to refactor this implementation, to support thousands or millions of blocks, using a block store based on disk. But now, using this naive implementation, I could explore the behavior of the node application.

The exposed method to add a block is:

this.add = function (block) {
    if (blockstore.hasBlockHash(block.hash))
        return;
        
    blockstore.save(block);
    
    if (getUnknownAncestor(block) != null)
        return;
    
    tryAdd(block);
}

If the block is know, then it implies it was already processed, then return.

If not, the block is saved in the in-memory store, and the first unknown ancestor hash is calculated. Maybe, the store has not ALL the ancestor chain up to genesis block. In this case, I cannot process the block.

If the block has a chain of ancestor that connects it to the genesis block, then I try to add the block to the blockchain:

function tryAdd(block) {
    if (isBestBlockChild(block))
        blocks.push(block);
    else if (isBetterBestBlock(block))
        tryFork(block);
        
    tryChildren(block);
}

It it is a direct child of the best block, it is added to the block (remember, a naive implementation, a simple array). If not, but it is a better block (it has a higher number), a fork to the block is performed. In any case, the children of the block are processed: maybe, the new block is the missing link to new candidate chains based on previously known blocks that were disconnected from genesis until the arrival of the new block.

These are the predicates I wrote:

function isBestBlockChild(block) {
    var bblock = self.bestBlock();
    
    return bblock.hash === block.parentHash && bblock.number === block.number - 1;
}

function isBetterBestBlock(block) {
    var bblock = self.bestBlock();
    
    return bblock.number < block.number;
}

This is the process of the children:

function tryChildren(block) {
    var children = blockstore.getChildren(block.hash);

    for (var n in children)
        tryAdd(children[n]);
}

Note: again, it is a naive implementation, that implies a recursion using tryAdd, that calls tryChildren. I could refactor to avoid recursion, a pending task.

Given a block, this function calculates the upward chain to its first ancestor included in the current blockchain, and then change the blockchain to have that chain:

function tryFork(block) {
    var newbranch = [block];
    var parentHash = block.parentHash;
    
    while (parentHash && blockstore.hasBlockHash(parentHash)) {
        var parent = blockstore.getByHash(parentHash);
        
        if (parent.hash === blocks[parent.number].hash)
            return switchToFork(newbranch);
            
        newbranch.push(parent);
        
        parentHash = parent.parentHash;
    }
}

The find of the first unknow ancestor of a block:

function getUnknownAncestor(block) {
    var parentHash = block.parentHash;

    while (parentHash && blockstore.hasBlockHash(parentHash)) {
        var parent = blockstore.getByHash(parentHash);
        
        if (parent.hash === blocks[parent.number].hash)
            return null;
        
        parentHash = parent.parentHash;
    }
    
    return parentHash;
}

The change of the blockchain to a new fork:

function switchToFork(newbranch) {
    for (var n = newbranch.length; n-- > 0😉 {
        var block = newbranch[n];
        blocks[block.number] = block;
    }
}

All the test passed. As I mentioned, my plan is to improve the implementation. But, as usual in my TDD workflow, I prefer to give baby steps, make it works, and only then, make it right and make it fast. I had good experiences using this way of writing code, obtaining simple and solid implementations, having all the test to help me to change any internal implementation, without pain.

Encouraged by this result, I also started to refactor my blockchain implementation in my personal C# project, too:

https://github.com/ajlopez/BlockchainSharp

I started to use a block store with GetByParentHash into my BlockChain code:

https://github.com/ajlopez/BlockchainSharp/blob/master/Src/BlockchainSharp/Core/BlockChain.cs

I wrote about my previous implementation in this post.

Stay tuned!

Angel “Java” Lopez

@ajlopez

May 23, 2016

Building A Blockchain (10)

Previous Post
Next Post

This week, I added more logic to my personal blockchain project in JavaScript:

https://github.com/ajlopez/SimpleBlockchain

I started to implement the blockchain logic using TDD (Test-Driven Development) workflow. A first test creating the blockchain object using a genesis block:

var blockchains = require('../lib/blockchains');
var blocks = require('../lib/blocks');

exports['create blockchain'] = function (test) {
    var genesis = blocks.block();
    var bc = blockchains.blockchain(genesis);
    
    test.ok(bc);
    test.equal(typeof bc, 'object');
    test.equal(bc.bestBlock(), genesis);
};

Then, I wrote a test exercising to add a new block:

exports['add block'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block(genesis);
    var bc = blockchains.blockchain(genesis);
    
    bc.add(block);
    
    test.equal(bc.bestBlock(), block);
};

The rejection of a block of the same height than the best block in blockchain:

exports['add block same height'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block(genesis);
    var block2 = blocks.block(genesis);
    
    var bc = blockchains.blockchain(genesis);
    
    bc.add(block);
    bc.add(block2);
    
    test.equal(bc.bestBlock(), block);
};

The adding of a block that is a child of the best block, and the rejection of a block that is not the descendant of the best block:

exports['add block with next height'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block(genesis);
    var block2 = blocks.block(block);
    
    var bc = blockchains.blockchain(genesis);
    
    bc.add(block);
    bc.add(block2);
    
    test.equal(bc.bestBlock(), block2);
};

exports['add block next height but another parent block'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block(genesis);
    var block2 = blocks.block(genesis);
    var block3 = blocks.block(block2);
    
    var bc = blockchains.blockchain(genesis);
    
    bc.add(block);
    bc.add(block3);
    
    test.equal(bc.bestBlock(), block);
};

These tests were written one by one, and each test was followed by the simplest implementation that pass the test. This is the spirit of TDD: baby steps, simple implementation, explicit description of expected behavior.

Next post: implementing account states, immutable states, and node communication.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

May 16, 2016

Building A Blockchain (9)

Filed under: Bitcoin, Blockchain, Ethereum, JavaScript, NodeJs, Open Source Projects — ajlopez @ 10:32 am

Previous Post
Next Post

You already know my personal blockchain project in C#:

https://github.com/ajlopez/BlockchainSharp

This week I started another implementation, using JavaScript/NodeJS:

https://github.com/ajlopez/SimpleBlockchain

It is interesting to compare a typed language implementation with another without types.

The base concepts are: blocks, transactions, a blockchain, etc. I’m writing the code using TDD (Test-Driven Development) workflow, as usual. The idea is to implement those base entities, and then, write a node program that can communicate with other nodes in the network, exchanging transactions and new mined blocks. My intention is to use JSON messages, instead of byte streams. But the format could be an decision to change. By now, I have some simple behavior implemented, covered by the corresponding tests.

These are my initial block tests:

exports['create genesis block'] = function (test) {
    var block = blocks.block();
    
    test.ok(block);
    test.equal(typeof block, 'object');
    test.equal(block.number, 0);
    test.ok(isHash(block.hash));
    test.ok(isHash(block.parentHash));
    test.equal(block.parentHash, '0x000....000000');
}

exports['create child block'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block(genesis);
    
    test.ok(block);
    test.equal(typeof block, 'object');
    test.equal(block.number, 1);
    test.ok(isHash(block.hash));
    test.ok(isHash(block.parentHash));
    test.equal(block.parentHash, genesis.hash);
}

exports['create child block with initial data'] = function (test) {
    var genesis = blocks.block();
    var block = blocks.block({ extra: 'hello' }, genesis);
    
    test.ok(block);
    test.equal(typeof block, 'object');
    test.equal(block.number, 1);
    test.ok(isHash(block.hash));
    test.ok(isHash(block.parentHash));
    test.equal(block.parentHash, genesis.hash);
    test.equal(block.extra, 'hello');
}

I wrote these tests one by one, and after each test, I implemented the code that makes the test pass. In this way, I wrote the simplest solution that satisfies the expected behavior. And I can refactor the implementations to a more powerful one without unnoticed breaking changes: every behavior is backed up by a test.

After the base entities, I need some auxiliary entities that allow the efficient process of blocks and transactions. One of this helper entities is a block store: where to save and retrieve blocks using hash, parent hash or number. By now, I have an in memory implementation. Some tests:

exports['create store'] = function (test) {
    var store = stores.blockstore();
    
    test.ok(store);
    test.equal(typeof store, 'object');
};

exports['retrieve unknown block by hash'] = function (test) {
    var store = stores.blockstore();
    
    var block = store.getByHash(utils.hash());
    
    test.equal(block, null);
};

exports['save block and retrieve it by hash'] = function (test) {
    var store = stores.blockstore();
    var hash = utils.hash();
    var block = { hash: hash };
    
    store.save(block);
    
    var result = store.getByHash(hash);
    
    test.ok(result);
    test.equal(result.hash, hash);
};

I will work on both projects: C# project needs some network code, and JavaScript project needs a blockchain implementation. I want to explore an alternative implementation for the blockchain growth. One nice thing about JavaScript implementation is that I don’t need to worry about multithreading issues. I can wrote code that changes the blockchain structure without having to check concurrent access.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

May 8, 2016

New Month’s Resolutions: May 2016

Filed under: C Sharp, JavaScript, NodeJs, Open Source Projects, Wang Tiles — ajlopez @ 5:27 pm

Time to write my new month’s resolutions, and review the previous month’s ones:

– Improve WangTiles [complete] see repo
– Improve BlockchainSharp [complete] see repo
– Start Blockchain in JavaScript [complete] see repo
– Work on EthSharp [pending]
– Improve SimpleGA [pending]
– Improve AjGenesisNode-Express [pending]
– Work on CrysJS [pending]
– Work on CrysSharp [pending]

Additionally, I worked on:

– Improve SimpleForth [complete] see repo
– Start WangTilesJS [complete] see repo

My new month’s resolutions are:

– Improve WangTiles
– Improve WangTilesJS
– Improve CrysSharp
– Improve BlockchainSharp
– Improve SimpleBlockchain
– Prepare and give a Bitcoin related talk

Stay tuned!

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

April 9, 2016

New Month’s Resolutions: Aprill 2016

Filed under: Blockchain, C Sharp, Ethereum, JavaScript, NodeJs, Open Source Projects, SimpleForth — ajlopez @ 4:34 pm

A new month started, and it’s time to write the new resolutions. And to review the past month ones:

– Improve AjGenesisNode-Express [pending]
– Work on CrysJS [complete] see repo
– Work on CrysSharp [pending]
– Improve my SimpleGA samples [pending
– Work on SharpGo [pending]
– Work on EthSharp [complete] see repo

Also I worked on:

– Improve SimpleForth in JavaScript [complete] see repo
– Start WangTiles in C# [complete] see repo
– Publish new version of SimpleArgs [complete] see repo
– Start BlockchainSharp in C# [complete] see repo
– Improve SimpleDT samples [complete] see repo
– Move AjGo to GitHub [complete] see repo
– Improve RuScript [complete] see repo
– Add Code Coverate to ethereumjs rlp [complete] see repo
– New Machine Learning in JavaScript presentation [complete] see repo see talk

My new resolutions:

– Improve WangTiles
– Improve BlockchainSharp
– Start Blockchain in JavaScript
– Work on EthSharp
– Improve SimpleGA
– Improve AjGenesisNode-Express
– Work on CrysJS
– Work on CrysSharp

Stay tuned!

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

Older Posts »

The Shocking Blue Green Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 74 other followers