Angel \”Java\” Lopez on Blog

September 24, 2017

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

 

 

 

April 6, 2017

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

July 11, 2016

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

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 9, 2016

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

May 2, 2016

Building A Blockchain (7)

Previous Post
Next Post

In my personal blockchain project:

https://github.com/ajlopez/BlockchainSharp

I want to execute simple code chain, using a virtual machine. The programs are usually called smart contracts. I adopted the Ethereum virtual machine design (read Ethereum Yellow Paper). Some classes:

A DataWord represents a number using 32 bytes. I implemented simple arithmetic operations using System.Numerics.BigInteger internally. I can create DataWord from integers or from byte arrays.

The Stack is an stack of DataWords, manipulated by the Machine. There is an enumeration, named Bytecodes, with the values of byte codes to be executed in the machine implementation. A program consists of a series of bytecodes, contained in a byte array. The Machine.Execute method is the place where the bytecodes are executed, manipulating the stack. Excerpt:

public void Execute(byte[] bytecodes)
{
    int pc = 0;
    int pl = bytecodes.Length;

    while (pc < pl)
    {
        byte bytecode = bytecodes[pc++];

        switch (bytecode)
        {
            case (byte)Bytecodes.Stop:
                return;
            case (byte)Bytecodes.Add:
                this.stack.Push(this.stack.Pop().Add(this.stack.Pop()));
                break;
            case (byte)Bytecodes.Multiply:
                this.stack.Push(this.stack.Pop().Multiply(this.stack.Pop()));
                break;
            case (byte)Bytecodes.Subtract:
                this.stack.Push(this.stack.Pop().Subtract(this.stack.Pop()));
                break;
                
            // more operations
        }
    }
}

I will add Storage and Memory to the execution of a program. The Storage will be associated and persisted with the contract account. Each contract is an account, with address, balance, but with code and storage state. The Memory will be created and used during the execution of the program, but it won’t be persisted: it is a temporary memory, used only at execution time.

I have a simple bytecode compiler, and a line compiler, to facilitate the creation of programs.

Next posts: description of compilers, block execution with transactions, storage and memory, persistent stores.

Keep tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

April 25, 2016

Building A Blockchain (6)

Previous Post
Next Post

These days, I added transaction processing to my personal project:

https://github.com/ajlopez/BlockchainSharp

In the previous post, I described the immutable Trie structure. Now, I have an AccountState that is saved by hash in a such Trie:

public class AccountState
{
    private BigInteger balance;

    public AccountState(BigInteger balance)
    {
        if (BigInteger.Compare(BigInteger.Zero, balance) > 0)
            throw new InvalidOperationException("Invalid balance");

        this.balance = balance;
    }

    public BigInteger Balance { get { return this.balance; } }

    public AccountState AddToBalance(BigInteger amount)
    {
        return new AccountState(BigInteger.Add(this.balance, amount));
    }

    public AccountState SubtractFromBalance(BigInteger amount)
    {
        return new AccountState(BigInteger.Subtract(this.balance, amount));
    }
}

I decided to implement the Ethereum way: having an account state, instead of inputs and outputs. The only property is Balance, but I will add more data. Notice that negative balances are rejeceted. Then, I added a TransactionProcessor:

public class TransactionProcessor
{
    private Trie<AccountState> states;

    public TransactionProcessor(Trie<AccountState> states)
    {
        this.states = states;
    }

    public Trie<AccountState> States { get { return this.states; } }

    public bool ExecuteTransaction(Transaction transaction)
    {
        var states = this.states;

        try
        {
            foreach (var av in transaction.Inputs)
            {
                var addr = av.Address.ToString();
                var state = states.Get(addr);
                var newstate = state.SubtractFromBalance(av.Value);
                states = states.Put(addr, newstate);
            }

            foreach (var av in transaction.Outputs)
            {
                var addr = av.Address.ToString();
                var state = states.Get(addr);
                var newstate = state.AddToBalance(av.Value);
                states = states.Put(addr, newstate);
            }

            this.states = states;

            return true;
        }
        catch (Exception ex)
        {
            return false;
        }
    }
}

If the transaction is processed, a new account state trie is generated, and ExecuteTransaction returns true. If the transaction is rejected, the initial accout state trie still has the original values. A typical test:

[TestMethod]
public void ExecuteTransaction()
{
    var transaction = CreateTransaction(100);

    var addr1 = transaction.Inputs.First().Address;
    var addr2 = transaction.Outputs.First().Address;

    var states = new Trie<AccountState>(new AccountState(BigInteger.Zero));

    states = states.Put(addr1.ToString(), new AccountState(new BigInteger(200)));

    var processor = new TransactionProcessor(states);

    Assert.IsTrue(processor.ExecuteTransaction(transaction));

    var newstates = processor.States;

    Assert.IsNotNull(newstates);
    Assert.AreNotSame(states, newstates);

    Assert.AreEqual(new BigInteger(200), states.Get(addr1.ToString()).Balance);
    Assert.AreEqual(BigInteger.Zero, states.Get(addr2.ToString()).Balance);

    Assert.AreEqual(new BigInteger(100), newstates.Get(addr1.ToString()).Balance);
    Assert.AreEqual(new BigInteger(100), newstates.Get(addr2.ToString()).Balance);
}

The auxiliary CreateTransaction method creates a transaction with an amount, and two random addresses.

I’m thinking to have only one sender account and receiving account per transaction, as in Ethereum. The change is easy, I have all the TDD tests to help me to do redesigns without a lot of work.

Next topics: executing blocks with transactions, saving state in persistent store, virtual machine and its bytecodes, a simple compiler, etc…

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

April 17, 2016

Building A Blockchain (5)

Filed under: Bitcoin, Blockchain, C Sharp, Ethereum, Test-Driven Development — ajlopez @ 10:02 am

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

Older Posts »

Create a free website or blog at WordPress.com.