15 Jun

Detecting a loop in a linked list

I was recently asked about Floyd’s cycle-finding algorithm, see here for details. In particular the person wanted to know what speeds the two pointers could move at for the algorithm to work. In Floyd’s algorithm the pointers move 1 step and 2 steps at a time respectively.

It’s an interesting question which touches on an element of number theory called modulo arithmetic and the study of congruence relations.

linked list

In Floyd’s algorithm the “hare” and “tortoise” both start at the beginning of the linked list at time, t = 0. At each step the “tortoise” moves 1 place and the hare moves 2 places. Given an arbitrary linked list with a cycle then it is clear the “tortoise” and “hare” won’t meet until they are both in the cycle. For this reason we don’t need to know how many steps it took for both of them to be in the cycle, and we only care from the point that both are in the cycle and we will actually call this t = 0. We will call linked list and linked list the positions that the “tortoise” and “hare” are in on the earliest step that both are in the cycle.

We don’t know how long the cycle is in length, but we will call it, n. We label the first element in the cycle 0, the second 1, the third 2, …., the n-th will be labelled n-1.

If we are at the position labelled n-1 and we move one place then we are at the position labelled 0.

linked list

The above diagram demonstrates what the values of t, n, linked list, linked list will be for the above linked list.

To give a few concrete examples we will pretend to be working with a cycle of length 12 as this gives us the familiar intuition that we have from using our watches.

linked list

however we will relabel the 12 position to be 0.

linked list

Now consider the “tortoise” and “hare” starting at positions 0 and 1 respectively. If the “tortoise” and “hare” move 1 place and 2 places respectively at a time, will they ever meet?

linked list

A quick bit of working with some pen and paper will yield the result that after 11 steps the “tortoise” will be at position 11 and the “hare” would have gone round the watch once and reached position 11 again.

It is true that with the “tortoise” moving 1 place and the “hare” moving 2 places at a time that they will always meet eventually regardless of their start positions (linked list, linked list). The reasons for this will be described later.

What we would like to know is whether other values that the “tortoise” and “hare” can move at each step yields the same result of them meeting eventually.

Consider the start positions as we have above but this time the “tortoise” moves 3 places and the “hare” moves 5 places at a time. Will they meet then?

The positions at each step for the first 15 steps is shown below.

Step Tortoise Hare
0 0 1
1 3 6
2 6 11
3 9 4
4 0 9
5 3 2
6 6 7
7 9 0
8 0 5
9 3 10
10 6 3
11 9 8
12 0 1
13 3 6
14 6 11
15 9 4

You may have noticed that at step 12 we have started to repeat the pattern of step 0. The “tortoise” and “hare” didn’t meet in the first 12 steps and so will never meet. Clearly steps of 3 and 5 don’t work for Floyd’s algorithm and these start positions. However if the “tortoise” started at position 0 and the “hare” at position 2 then it is easy to check that they will meet, so the start positions do matter as well!

Before we write out the problem more formally, let’s first formalise this “clock” arithmetic we have been using implicitly.

We say that linked list if (b – a) is a multiple of n.

The concrete examples we will give will use our familiar clock.

linked list — that is to say that 1pm and 1am look the same on a 12 hour clock. They both use the 1 position.
linked list — that is to say if we start at 1pm and add 24 hours then it is still 1pm but just a day later

In both examples 13 – 1 = 12 and 25 – 1 = 24 are both multiples of 12.

Given the start positions linked list and linked list and the places moved at each step linked list and linked list and a cycle of length n then we are looking for a solution to the following equation:

linked list

This can be rewritten to:

linked list

This is a standard equation in number theory and it has a solution if and only if linked list

The gcd is the greatest common divisor. More information can be found at gcd.

Given that the length of the cycle n and the start positions are arbitrary the only way to guarantee that the above equation has a solution is to ensure that linked list and the only way to guarantee this for all n is to make linked list. In other words the places that the “tortoise” and “hare” move at a time must differ by 1.

This explains why the choice of 1 and 2 work for all linked lists with a cycle, however values such as 4 and 5 will also work. 99 and 100 or even the values 121 and 120!

02 Jun

Creating a private Ethereum block chain and crypto currency

I’ve recently been playing with a few block chain implementations and looking at the technologies use to the financial services sector.

One of the block chain implementations I’ve been looking at is Ethereum.

This blog post is an all in one guide to getting up and running with Ethereum on a private network. This blog post will cover the following

  1. Starting a blockchain with Ethereum
  2. Mining with an Ethereum node
  3. Connecting the 2 nodes and sending a test transaction
  4. Creating a cryptocurrency called Innovions
  5. Performing a transaction with Innovions

Starting a blockchain with Ethereum

Make sure you have installed geth locally. There is a docker container for geth in the docker hub which can be used for testing purposes.

The first thing we need to do is create the initialisation settings for the private block chain. Create a file called genesis.block.json and populate it’s contents as follows:

{
	"nonce": "0xfaceb00cfaceb00c",
	"timestamp": "0x0",
	"parentHash": "0x0000000000000000000000000000000000000000000000000000000000000000",
	"extraData": "0x0",
	"gasLimit": "0x8000000",
	"difficulty": "0x400",
	"mixhash": "0x0000000000000000000000000000000000000000000000000000000000000000",
	"coinbase": "0x3333333333333333333333333333333333333333",
	"alloc": {
	}
}

launch geth with the following command to initialise the block chain on this node:

geth --datadir /path/to/store/nodedata init /path/to/genesis.block.json

If successful the output will be similar to:

I0531 11:13:39.555651 ethdb/database.go:82] Alloted 16MB cache and 16 file handles to node1/chaindata
I0531 11:13:39.560438 cmd/geth/main.go:353] successfully wrote genesis block and/or chain rule set: ba4fe4055a968c1b05a1254289164e7665cfef89782dcc7dcaec2e5e4edc83a6

To start Ethereum in console mode run the following:

geth --datadir nodedata --nodiscover --networkid 222 console

Note: Just make sure the networkid is unique to any other ethereum networks that you may be able to contact. The main network uses either 0 or 1 as it’s network id.

Mining with an Ethereum node

Before we can begin mining we need to create an account. At the geth console type the following:
> personal.newAccount("insecure_password")
"0x160b182bc3fed971000a05a5dc9eff821ad63f21"

The string “0x160b182bc3fed971000a05a5dc9eff821ad63f21” is our address of our account on the network and “insecure_password” is a password which protects the private key of this address on this node.

Ethereum works on a base currency called ether. You need ether to send transactions. First we will check our ether balance.
Type the following into the console:

function checkAllBalances() { 
    var i =0; 
    eth.accounts.forEach( function(e){
        console.log("  eth.accounts["+i+"]: " +  e + " \tbalance: " + web3.fromWei(eth.getBalance(e), "ether") + " ether"); 
        i++; 
    })
};

and then type the following at the console:
> checkAllBalances()
eth.accounts[0]: 0x160b182bc3fed971000a05a5dc9eff821ad63f21 balance: 0 ether

You will see that we have no ether. Let’s mine to gather some.

miner.start();

Mining should begin after the DAG is generated. We should gather ether quickly enough that after 5 minutes we can check our balance again and we will see that we have acquired ether.

> checkAllBalances()
eth.accounts[0]: 0x160b182bc3fed971000a05a5dc9eff821ad63f21 balance: 5 ether

This confirms that we have successfully mined. Next we will connect a second node.

Connecting the 2 nodes and sending a test transaction

Reperform the initialisation step as we did on the first node using the same genesis.block.json file but on a secondary node. Ideally use a second computer however if you want to run both nodes on the same computer use a different port when running geth by specifying –port “65432” on the command line.

geth --datadir nodedata init genesis.block.json

Start Ethereum in console mode by running the following:

geth --datadir nodedata --nodiscover --networkid 222 console

now type the following to get the address of the second node:
> admin.nodeInfo.enode
"enode://33b87bfabdeace1b40faf7219870f716ded69e04be409278e9673d80e475bac3e[email protected][::]:30303?discport=0"

Replace the [::] in the enode address with the IP address of the second node. For example, if the second node has IP address 172.17.100.3 then replace [::] with [172.17.100.3].

On the first node type the following:

admin.addPeer("enode://33b87bfabdeace1b40faf7219870f716ded69e04be409278e9673d80e475bac3e[email protected][172.17.0.3]:30303?discport=0");

If successful running admin.peers.length on both nodes should return 1.

Create a new account on the secondary node and start mining:

> personal.newAccount("insecure_password")
"0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2"
> miner.start();

Run the following code to have access to a function to check ether balances:

function checkAllBalances() { 
    var i =0; 
    eth.accounts.forEach( function(e){
        console.log("  eth.accounts["+i+"]: " +  e + " \tbalance: " + web3.fromWei(eth.getBalance(e), "ether") + " ether"); 
        i++; 
    })
};

After the DAG has been generated and after about 5 minutes of mining you should have a non-zero ether balance:

> checkAllBalances()
eth.accounts[0]: 0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2 balance: 5 ether

Let’s send some ether.

On the first node type the following:

> personal.unlockAccount(eth.accounts[0], "insecure_password")
true
> eth.sendTransaction({ from: eth.accounts[0], to: "0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2", value: web3.toWei(1, "ether")});
I0531 12:06:30.232783 eth/api.go:1193] Tx(0x67cd98d4599602d2b99a7a63193aa23c6170f9177203f5a841d736ce62ffa0d8) to: 0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2
"0x67cd98d4599602d2b99a7a63193aa23c6170f9177203f5a841d736ce62ffa0d8"

Please note that you will need to regularly use personal.unlockAccount as your account locks itself quite frequently. You can pass a third parameter to unlockAccount which is the duration to have the account unlocked however this has not been tested.
Wait for a block to be mined to confirm the transaction and check the balances on each node:

Node 1:

> checkAllBalances()
eth.accounts[0]: 0x160b182bc3fed971000a05a5dc9eff821ad63f21 balance: 17.999116405924692 ether

Node 2:

> checkAllBalances()
eth.accounts[0]: 0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2 balance: 7.000883594075308 ether

We can now move on to creating our own crypto currency.

Creating a cryptocurrency called Innovions

I’ve used an online contract compiler, https://ethereum.github.io/browser-solidity/, to compile the Ethereum contracts.

My Innovions contract (currency) is as follows:

contract Innovions {

    address public controller;

    /* This creates an array with all balances */
    mapping (address => uint256) public balanceOf;

    function Innovions() {
        controller = msg.sender;
    }

    function transferController(address _to) {
        
        if (msg.sender != controller) {
            throw;
        }
        
        controller = _to;
    }
    
    function transfer(address _to, uint256 _value) {
        
        /* Check if sender has balance and for overflows */
        if (balanceOf[msg.sender] < _value || balanceOf[_to] + _value < balanceOf[_to])
        {
            throw;
        }

        /* Add and subtract new balances */
        balanceOf[msg.sender] -= _value;
        balanceOf[_to] += _value;
        
    }
    
    function issue(uint256 _value)
    {
        if (msg.sender != controller) {
            throw;
        }
        
        balanceOf[msg.sender] += _value;
    }
}

Copy the contract to the online compiler and under the Web3 Deploy section will be code similiar to the following that is used to create the contract:

var innovionsContract = web3.eth.contract([
    {"constant":true,"inputs":[{"name":"","type":"address"}],"name":"balanceOf","outputs":[{"name":"","type":"uint256"}],"type":"function"},
    {"constant":false,"inputs":[{"name":"_to","type":"address"},{"name":"_value","type":"uint256"}],"name":"transfer","outputs":[],"type":"function"},
    {"constant":false,"inputs":[{"name":"_value","type":"uint256"}],"name":"issue","outputs":[],"type":"function"},
    {"constant":false,"inputs":[{"name":"_to","type":"address"}],"name":"transferController","outputs":[],"type":"function"},
    {"constant":true,"inputs":[],"name":"controller","outputs":[{"name":"","type":"address"}],"type":"function"},
    {"inputs":[],"type":"constructor"}]);

var innovions = innovionsContract.new(
    {
        from: web3.eth.accounts[0],
        data: '60606040525b33600060006101000a81548173ffffffffffffffffffffffffffffffffffffffff021916908302179055505b6103a68061003f6000396000f360606040526000357c01000000000000000000000000000000000000000000000000000000009004806370a0823114610065578063a9059cbb14610091578063cc872b66146100b2578063e8ea054b146100ca578063f77c4791146100e257610063565b005b61007b600480803590602001909190505061011b565b6040518082815260200191505060405180910390f35b6100b06004808035906020019091908035906020019091905050610136565b005b6100c86004808035906020019091905050610259565b005b6100e060048080359060200190919050506102f5565b005b6100ef6004805050610380565b604051808273ffffffffffffffffffffffffffffffffffffffff16815260200191505060405180910390f35b60016000506020528060005260406000206000915090505481565b80600160005060003373ffffffffffffffffffffffffffffffffffffffff1681526020019081526020016000206000505410806101d25750600160005060008373ffffffffffffffffffffffffffffffffffffffff1681526020019081526020016000206000505481600160005060008573ffffffffffffffffffffffffffffffffffffffff1681526020019081526020016000206000505401105b156101dc57610002565b80600160005060003373ffffffffffffffffffffffffffffffffffffffff16815260200190815260200160002060008282825054039250508190555080600160005060008473ffffffffffffffffffffffffffffffffffffffff1681526020019081526020016000206000828282505401925050819055505b5050565b600060009054906101000a900473ffffffffffffffffffffffffffffffffffffffff1673ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff161415156102b557610002565b80600160005060003373ffffffffffffffffffffffffffffffffffffffff1681526020019081526020016000206000828282505401925050819055505b50565b600060009054906101000a900473ffffffffffffffffffffffffffffffffffffffff1673ffffffffffffffffffffffffffffffffffffffff163373ffffffffffffffffffffffffffffffffffffffff1614151561035157610002565b80600060006101000a81548173ffffffffffffffffffffffffffffffffffffffff021916908302179055505b50565b600060009054906101000a900473ffffffffffffffffffffffffffffffffffffffff168156',
        gas: 3000000
    }, function(e, contract) {
        console.log(e, contract);

        if (typeof contract.address != 'undefined') {
            console.log('Contract mined! address: ' + contract.address + ' transactionHash: ' + contract.transactionHash);
        }
    });

Run the following code on the first node. This will make the first node the “royal mint” for the new currency.

Once the create contract transaction has been mined. We will receive the contracts address on the console:

Contract mined! address: 0x0636d186816c37bb1292725fba6f110c85c7c8d6 transactionHash: 0x33c73a0a314bc0ddf3a129452bc3457ade067ec7427ce9fc95bddd3446530b3f

So that we can interact with the contract on the second node type the following on the second node:

var innovions = web3.eth.contract([
    {"constant":true,"inputs":[{"name":"","type":"address"}],"name":"balanceOf","outputs":[{"name":"","type":"uint256"}],"type":"function"},
    {"constant":false,"inputs":[{"name":"_to","type":"address"},{"name":"_value","type":"uint256"}],"name":"transfer","outputs":[],"type":"function"},
    {"constant":false,"inputs":[{"name":"_value","type":"uint256"}],"name":"issue","outputs":[],"type":"function"},
    {"constant":false,"inputs":[{"name":"_to","type":"address"}],"name":"transferController","outputs":[],"type":"function"},
    {"constant":true,"inputs":[],"name":"controller","outputs":[{"name":"","type":"address"}],"type":"function"},
    {"inputs":[],"type":"constructor"}]).at("0x0636d186816c37bb1292725fba6f110c85c7c8d6");

Make sure to replace “0x0636d186816c37bb1292725fba6f110c85c7c8d6” with the contract address

Performing a transaction with Innovions

For the first transaction we will issue 100 Innovions to the royal mint. On the first node execute the following:

>innovions.issue(100, { from: eth.accounts[0] });

Once the issue transaction has been mined we can check the balance of all parties from either node:

> innovions.balanceOf("0x160b182bc3fed971000a05a5dc9eff821ad63f21")
100
> innovions.balanceOf("0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2")
0

Next from the first node, let’s transfer 25 Innovions to the second node:

>innovions.transfer("0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2", 25, { from: eth.accounts[0] });

Once the transaction has been mined we can check the balances on either node:

> innovions.balanceOf("0x160b182bc3fed971000a05a5dc9eff821ad63f21")
75
> innovions.balanceOf("0x8b6e1d3dac361256c371b308c8e3be42fe4b9dc2")
25

Summary

From start to finish we have created a private Ethereum block chain and created a smart contract (The crypto currency in this instance) on that block chain. We have demonstrated mining and transactions. Hopefully this will serve as a rapid introduction to a standard use case of Ethereum and give you the confidence to take your next steps.