Category Archives: Test-Driven Development

Building A Blockchain (16)

Previous Post

In recent months I have been busy working on the RSK project. It’s time to write about my personal blockchain projects:

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

Currently, the most active one is the C# project. I added one project:

https://github.com/ajlopez/BlockchainJ

in Java. The experience I gained written all this code (using test-driven design, as usual) gaves me a clear idea of what is involved when building a blockchain. Writing my own implementations gave me better understanding of the parts related to the creation of a blockchain. And now the RSK project (Java core implementation) is public, I’m free to relate this work with an existing full implementation.

The key points to be written are:

  • Entities
  • States
  • Virtual machine to run smart contracts
  • Encoders
  • Consensus
  • Validation logic
  • Inter-node communication
  • Expose node state to external applications

The base entities are:

  • Block
  • Transaction
  • Account

The states to be kept are:

  • Blockchain
  • Account state
  • Contract state

My projects are oriented to have smart contracts, a la Ethereum. One reason to have a virtual machine is be agnostic of host programming language. I think that having a way of run smart contract that is independent of the programming language used in each project, is an interesting feature. So, I should define:

  • Virtual machine opcodes
  • Transient (memory) storage
  • Persistent storage

I need encoders for blocks, transactions and account states. The encoded entities are used in the network communication, local storage, and in the hash calculation. For example, when I have to transmit a block I encoded it. And if I want to send the block to another node, I should encoded the block before transmission. And the encoded data is the basis for hash calculation.

The inter-node communication includes:

  • Message definitions
  • Message and handshake protocol
  • Peer-discovery protocol

Validation logic refers to:

  • Validation of blocks
  • Sign of transaction and its validation

Consensus logic has:

  • Selection of the next block
  • Run of the transactions, updating the accounts/contracts states

The exposure of a node state is implemented in Bitcoin and Ethereum using JSON RPC (Remote procudure call), usually exposed via http. In this way, the node can be accessed by external technologies implemented in different technologies (JavaScript blockchain ecosystems are the more popular).

Followin Ethereum ideas, one entity I implemented many times is a trie. I think my implementations are very simple and effective. I hope to be able to write in the next posts about those implementations.

Stay tuned!

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

 

 

 

New Month’s Resolutions: April 2017

A new month begins, it’s time to write down my monthly resolutions. First, a review of the last month ones:

– Continue RskSharp [complete] see repo
– Continue SimpleBlockchain [pending]
– Continue Solidity Compiler [complete] see repo
– Continue ChineseP [pending]
– Continue TensorSharp [complete] see repo

Additionally, I was working on:

– Improve SimpleProlog [complete] see repo
– Continue RSharp [complete] see repo
– Improve AjDrawJS [complete] see repo
– Improve SimpleForth [complete] see repo

My new month’s resolutions:

– Continue RskSharp
– Continue SimpleBlockchain
– Continue Solidity Compiler
– Continue ChineseP
– Continue TensorSharp
– Continue RSharp
– Continue SimpleForth

Stay tuned!

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

Building A Blockchain (14)

Previous Post
Next 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

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

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

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

Building A Blockchain (8)

Previous Post
Next Post

In previous post, I wrote about the virtual machine I’m implementing in my personal blockchain project, in C#, using TDD (Test-Driven Development) workflow:

https://github.com/ajlopez/SimpleBlockchain

I added a simple bytecode compiler, in order to simplify some tests. The class is not needed for production code, but it is included in the core project:

public class BytecodeCompiler
{
    private IList<byte> bytes = new List<byte>();

    public void Stop()
    {
        this.Compile(Bytecodes.Stop);
    }

    public void Add()
    {
        this.Compile(Bytecodes.Add);
    }

    public void Subtract()
    {
        this.Compile(Bytecodes.Subtract);
    }
    
    // more methods
    
    public byte[] ToBytes()
    {
        return this.bytes.ToArray();
    }
}

It collects a series of bytecodes, with optional arguments. There is a method to return a byte array with the compiled program. A sample test:

[TestMethod]
public void LessThan()
{
    BytecodeCompiler compiler = new BytecodeCompiler();

    compiler.Push(2);
    compiler.Push(2);
    compiler.LessThan();
    compiler.Push(0);
    compiler.Push(1);
    compiler.LessThan();
    compiler.Push(1);
    compiler.Push(0);
    compiler.LessThan();

    Machine machine = new Machine();

    machine.Execute(compiler.ToBytes());

    var stack = machine.Stack;

    Assert.IsNotNull(stack);
    Assert.AreEqual(3, stack.Size);
    Assert.AreEqual(DataWord.Zero, stack.ElementAt(2));
    Assert.AreEqual(DataWord.Zero, stack.ElementAt(1));
    Assert.AreEqual(DataWord.One, stack.ElementAt(0));
}

I also wrote a simple line compiler, named SimpleCompiler. Now, I can use it in my machine tests:

[TestMethod]
public void IsZeroUsingSimpleCompiler()
{
    string program = "push 2\n" +
        "iszero\n" +
        "push 0\n" +
        "iszero";

    SimpleCompiler compiler = new SimpleCompiler(program);

    Machine machine = new Machine();

    machine.Execute(compiler.Compile());

    var stack = machine.Stack;

    Assert.IsNotNull(stack);
    Assert.AreEqual(2, stack.Size);
    Assert.AreEqual(DataWord.Zero, stack.ElementAt(1));
    Assert.AreEqual(DataWord.One, stack.ElementAt(0));
}

These are auxiliary classes, but they simplify the writing of new tests. It is part of my simplification strategy: after some initial and long tests, try to simplify the writing of the newer ones.

In the next post, a surprise: a new blockchain project, but using NodeJS, JavaScript.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez