Angel \”Java\” Lopez on Blog

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

April 11, 2016

Building A Blockchain (4)

Filed under: Bitcoin, Blockchain, C Sharp, Ethereum, Open Source Projects — ajlopez @ 10:20 am

Previous Post
Next Post

In this post, I want to describe the key parts of a blockchain example I’m writing at:

https://github.com/ajlopez/BlockchainSharp

using C# and TDD (Test-Driven Development). The essential things to be implemented are:

– Blocks
– Transactions

the concepts of:

– Account
– Account State
– Smart Contracts (executed in a virtual machine)

and utilities for:

– Encode/Decode entities to be transmited/received via the network of nodes
– Hash calculations
– Immutable tries
– Sign transactions
– Verify transaction sign
– Verify block integrity
– Verify transactions are valid
– Proof of Work calculation (as usual in Bitcoin and Ethereum implementations)
– Store some entities: complete blocks, partial blocks (block headers in Ethereum), account state, … in general, tries with storage

Some days ago, I started to write a Transaction class, having pairs of accounts and values. I adopted Ethereum approach: instead of having inputs/outputs as in Bitcoin, I have accounts with balances/states. Each account is identified by an address (actually a random hexadecimal string):

Each transaction can have one or more inputs and outputs. Each input/output has an account address and a value. The values are instances of BigInteger, so I can manage large integer numbers. It’s the way the criptocurrencies implementations allow the use of value fractions: the unity is a power of 10, and the amounts are expressed in integer quantity of minimal fractions.

Next steps: add transactions to blocks, apply transaction to account states, validate that input values are available, store states in an immutable trie,…

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

April 4, 2016

Building A Blockchain (3)

Previous Post
Next Post

I added a lot of code to my simple blockchain implementation written in C#:

https://github.com/ajlopez/BlockchainSharp

As usual, I followed TDD (Test-Driven Development) workflow, pursuing simplicity, doing baby steps. In the last post I mentioned the use of a DSL (Domain Specific Language) to specify some block processing tests that have complex setup.

Initially, I wrote tests like:

[TestMethod]
public void ProcessTwoBlocksAndTwoUncles()
{
    Block genesis = new Block(0, null);
    Block block = new Block(1, genesis.Hash);
    Block uncle1 = new Block(1, genesis.Hash);
    Block uncle2 = new Block(2, uncle1.Hash);

    BlockProcessor processor = new BlockProcessor();

    processor.Process(genesis);
    processor.Process(block);
    processor.Process(uncle1);
    processor.Process(uncle2);

    Assert.IsNotNull(processor.BlockChain);
    Assert.AreEqual(2, processor.BlockChain.BestBlockNumber);
    Assert.AreEqual(genesis, processor.BlockChain.GetBlock(0));
    Assert.AreEqual(uncle1, processor.BlockChain.GetBlock(1));
    Assert.AreEqual(uncle2, processor.BlockChain.GetBlock(2));
}

The idea is:

– Create some blocks

– Send the blocks to the block processor

– Check the blocks in the block chain

The created blocks are related by parent relationships. Sometimes, a competing block is created, so the block processor must deal with block branches.

But the setup code could be long and complex. So, I wrote a DSL, and now I have tests like:

[TestMethod]
public void SendTwoBlocksAndTwoUncles()
{
    var processor = new BlockProcessor();
    var dsl = new BlockProcessorDsl(processor);

    dsl.Run(new string[] 
    {
        "chain g0 b1 b2",
        "chain b1 c2 c3",
        "send b1 b2",
        "send c2 c3",
        "top c3"
    });
}

Each command is an string, with verb and arguments. The block g0 is the genesis block. The verb “chain” enumerates a list of blocks to be created, each block is child of its previous block. The verb “send” sends the created blocks to the block processor. The verb “top” checks if the specified block is the top block in the current blockchain.

The result should not depend on order of arriving blocks, ie:

[TestMethod]
public void SendTwoBlocksInReversedOrder()
{
    var processor = new BlockProcessor();
    var dsl = new BlockProcessorDsl(processor);

    dsl.Run(new string[] 
    {
        "chain g0 b1 b2",
        "send b2 b1",
        "top b2"
    });
}

I could add text files, each one specifying command lines to be executed as sentences of the DSL.

In the next posts: core implementations needed by a blockchain, byte serialization, and implementing immutable tries for storing states.

Stay tuned!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

March 28, 2016

Building A Blockchain (2)

Previous Post
Next Post

In the past days, I wrote a first implementation of a blockchain, using TDD (Test-Driven Development). Simplicity guides my decision: the blockchain is in-memory, and blocks are identified by number and a hash. Two blocks with number 42 are differente blocks if they have different hashes. A block has the parent block hash (the parent block number is deduced, it’s the block number minus one). A genesis block has number 0, and null parent hash. In this way, I have all the ingredients to build a blockchain, from genesis block to best block, chaining the blocks using their numbers and hashes.

I have a class BlockChain (yes, I prefer the mixed case name). There is a method to add a new block to the blockchain. It controls the new block has as parent the current best block in the blockchain.

But there are other nodes, that send other blocks, that can or cannot be added to the blockchain. How to process those blocks? I collect the blocks that cannot be added to the current blockchain in other objects, I call them blockbranch:

In the second blockbranch, parent block for block 41 is unknown, so, the blockbranch is waiting for the arrival of that block. The first blockbranch is connected to blockchain, as an alternative branch. But is has a height less than blockchain height.

A block branch has one or more consecutive blocks. The blocks are not part of the current blockchain. But they are proto-blockchain.

In the second blockbranch of the above figure, parent block for block 41 is unknown, so, the blockbranch is waiting for the arrival of that block. The first blockbranch is connected to blockchain, as an alternative branch. But is has a height less than blockchain height.

When I have sufficient blocks in a block branch (maybe, connect the bottom of the blockbranch to an existing block in another blockbranch or in the current blockchain), and I can build a list of blocks from genesis to the block in block branch, the branch is a candidate to be the new blockchain. Suppose a new block arrives:

The new block can be added to the second block branch, and it has an existing parent in the current blockchain. So, the block branch now has a complete path of block from genesis.

If the block branch is valid (applying their blocks to a known valid state at end of main block 39), and its height is greater than the current blockchain, the block branch is promoted to be the new blockchain:

The process works even if the new blocks arrives in random order. To manage the creation, growth, and promotion of blockchain and related blockbranches, I have a separate object, of class BlockProcessor, in charge of all this orchestration. The processor receives the new blocks, and send them to the corresponding blockchain or branch. Then, it can detect any new connection between branches, and the formation of branches that can be promoted to blockchains.

In the next post: details of a DSL (Domain Specific Language) I’m using to test different scenarios for the block processor.

Stay tuned!

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

March 21, 2016

Building a Blockchain (1)

Filed under: Bitcoin, Blockchain, C Sharp, Ethereum, Open Source Projects — ajlopez @ 8:50 am

Next Post

In the past month, I started to work at Rootstock dev team, a very interesting project involving smart contracts over distributed ledgers. In recent weeks, I studied about Bitcoin, Ethereum, and cryptocurrencies. I read many papers, books, and reviewed some code implementation. My links:

http://delicious.com/ajlopez/bitcoin
http://delicious.com/ajlopez/ethereum
http://delicious.com/ajlopez/blockchain

I want to describe the essential elements of a distributed blockchain, and its importance. I hope to write source code implementing those ideas, in a simple way, grasping what is the core of all implementations.

A blockchain is a list of blocks, starting from the first one, called the genesis block:

A block has information. In crypto-currencies, that information is usually called transactions:

A transaction describe, in such domains, a transference of crypto-currency, named bitcoins or ether or whatever. But the essence is: a transaction is a piece of information that describe the change of world state.

There is an initial world state after the appearance of the genesis block, and each block, having 0 or more transactions (and, usually, a block finalization implicit transaction), ALTERS the world state:

The transactions should be valid: no transaction is allowed to transform the world state into an invalid one. A typical example of an invalid transaction: one than transfer crypto-currencies from an inexistent account, or from an account with insufficient funds.

The system is not running in one dedicated server. Instead, a network of independent machines is running the software, called the nodes, running the client software (“client” name is a bit confused, because implies the existent of a “server”, but no: each node is the client of other nodes).

Nodes are connected to some other nodes, and the network could have hundreds or thousands of nodes.

There are new transactions that are injected in the system, using specialized software. A node can received a new transaction, and send it to its neighbors:

Some specialized nodes, having all the resources to validate and execute transactions, generates new blocks, containing zero or more transactions. In bitcoin and similar systems, there are economics incentives for such block producers, called miners. The miners gain crypto-currencies, for each created block, and collecting fees from mined transactions.

When a miner (say, N2) produces a new block, it sends it to their neighbor nodes, eventually reaching the whole network:

Many nodes keep the full blockchain, and at receiving a new block, they adds it to its own version of the blockchain, if the block is valid. But sometimes, there are many competing blocks to be added:

And one part of the network could have a blockchain different from the blockchain of other nodes:

In these cases, there is an algorithm to reach consensus. Once the consensus is reached, the blockchain is a distributed one (many nodes have its content and world state), and the mined transactions are accepted in the distributed version.

There are many details to be discussed:

– When a block is valid?
– When a transaction is valid?
– How to generate a transaction? (a transaction moving value from one account to another cannot be generated by anyone, only for the giving account owners)
– How to reach consensus?
– How to store the blockchain?
– How to store the state after each block transactions execution?
– How to transmit the transactions and mined blocks from node to node?

And I want to write some example code, giving a minimal and essential. I created a C# class library. It is being writing using TDD (Test-Driven Development):

https://github.com/ajlopez/BlockchainSharp

Stay tuned!

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

March 6, 2016

New Month’s Resolutions: March 2016

Filed under: C Sharp, Crystal, JavaScript, NodeJs, Open Source Projects — ajlopez @ 4:01 pm

A new month starts, time to write the new resolutions, but first, review the previous ones.

– Improve AjGenesisNode-Express [pending]
– Work on CrysJS [complete] see repo
– Work on CrysSharp [pending]
– Work on Memolap [pending]
– Work on SimpleMemolap [pending]
– Improve my SimpleGA samples [pending]
– Improve SharpGo [complete] see repo
– Improve Husky [pending]
– Work on GoLin [pending]
– Improve ImmuO [complete] see repo
– More ReactJS samples [pending]
– Improve Aktores [pending]
– Improve ErlSharp [pending]

It was a month to start a new job, an very interesting project related to Ethereum. Additionally, I worked on:

– Improve RuScript [complete] see repo
– Start EthSharp, Ethereum-like node in C# [complete] see repo
– Start EthSharpVm, Ethereum-like virtual machine, in C# [complete] see repo
– Improve ElixirJS [complete] see repo
– Improve SimpleForth [complete] see repo
– Start CrLisp [complete] see repo

My new resolutions:

– Improve AjGenesisNode-Express
– Work on CrysJS
– Work on CrysSharp
– Improve my SimpleGA samples
– Work on SharpGo
– Work on EthSharp

Stay tuned!

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

February 7, 2016

New Month’s Resolutions: February 2016

Filed under: C Sharp, JavaScript, NodeJs, Open Source Projects — ajlopez @ 6:20 pm

Before declaring my new resolutions, first let review the previous month’s ones:

– Work on SimpleGA trader samples [pending]
– Work on SimpleDatabase [pending]
– Work on SimpleMemolap [complete] see repo
– Work on Memolap [complete] see repo
– Improve AjGenesisNode [pending]
– Improve SharpGo [complete] see repo
– Improve Husky [complete] see repo
– Work on GoLin [complete] see repo

Also, I was working on:

– Created SRedux, a Redux-like library [complete] see repo
– Created ImmuO, immutable objects in JavaScript [complete] see repo
– Started CrysSharp, Crystal language in C# [complete] see repo
– Started CrysJS, Crystal language in JavaScript [complete] see repo
– Add ReactJS samples to JavaScript samples [complete] see repo
– Improve ElixirJS [complete] see repo
– Created ReduMan, reducer manager in JavaScript [complete] see repo
– Created RkStreams, reactive streams in JavaScript [complete] see repo

My new resolutions:

– Improve AjGenesisNode-Express
– Work on CrysJS
– Work on CrysSharp
– Work on Memolap
– Work on SimpleMemolap
– Improve my SimpleGA samples
– Improve SharpGo
– Improve Husky
– Work on GoLin
– Improve ImmuO
– More ReactJS samples
– Improve Aktores
– Improve ErlSharp

Keep tuned!

Angel “Java” Lopez
@ajlopez

« Newer PostsOlder Posts »

Blog at WordPress.com.