Hello world!

By last blog, I have presented how to locally simulate a simple Proof-of-Work(PoW) Blockchain in Java with multithreading. In this blog, I will make proper modifications to implement a more complex Blockchain inspired by the idea of sharding.

Basic Idea of Sharding in Blockchain

Sharding is originally a concept popular in database area. It is the idea of dividing a huge chunk of data into several disjoint subsets, and each of the subset is called a shard. The reason recent researchers have been interested in applying sharding into Blockchain is that this concept seems to be helpful to solve the scalability problem of Blockchain technology. The mining congestion happens when the transactions producing rate is higher than the transactions processing rate of the Blockchain system, which causes longer and longer waiting time for the transactions confirmation as the market keeps growing. With the ideas of sharding and parallel mining, we can divide the overloaded transactions into smaller disjoint shards and allow multiple concurrently maintained sub-chains to record them. Ideally, in this way, we should be able to improve the transactions processing rate dramatically.

Sharding Data Structure in my Simulation

As there is a variety of different ways of implementing sharding in Blockchain, I will apply a relatively simple approach here. Let’s treat the Block data structure from previous code as Sub-Block, and redefine the Block as a collection of Sub-Blocks. The entire Blockchain data structure should look like the figure below:

Now every mining iteration, based on the transactions load, the Blockchain system would decide to divide next Block into a proper number of shards(sub-blocks), and evenly distribute compute powers to each of the shards. Miners of different shards will concurrently compute the satisfying nounce for the shard they belong to. For N shards, there will be N winners. Each of them will be able to generate a new sub-block and all the sub-blocks will be gathered together as a whole new Block to be attached to the Blockchain.

Implementation Modifications

First, the blockchain variable in Beecoin class should now be implemented as a ArrayList of Block Array:

private static ArrayList<Block[]> blockchain = new ArrayList<>();

Every mining iteration, we will first decide the number of shards we want, which is the length of the Block array, according to two things:
1. the transactions load
2. the number of miners

The reason we want to also consider the miners quantity is that we don’t want to have too many shards that there is not enough miners in charge of each shard. When there is only little miners for each shard, the safety of the shard is harmed. In my simulation, I simply assume that each shard will have at least two miners in charge of it.
We can compute the number of shards needed for each Block in this way:

desiredShards = (# of unconfirmed transactiosn) / (Capacity of each sub-block)
maxShards = (# of miners) / (minimum Miners per Shard)
IF desiredShards >= maxShards:
desiredShards = maxShards

Now, when we create a Miner thread for mining, we also want to tell it which shard it belongs to. Additionally, we need to modify the Miner class to let it support concurrent multi-blocks mining. The only things I need to change, is the class variables of Miner, which are used to support communication between Miner threads. They were designed to make sure all threads terminating when a solution is found by any thread. Now, they should make sure a thread only terminate when a solution is found by itself or a thread of the same shard. Thus, for N shards, there will be N final_nounce to be found. In other words, each of those class variables now should become an collection of what it was. Now the Miner class data members should look like this:

public class Miner extends Thread {
    public static boolean solutionClaimed[]; // modified
    public static int claimerID[]; // modified
    public static int candidate[]; // modified
    public static ArrayList consensusList = new ArrayList(); // modified
    public static int minerNum = 0;
    public static String final_nounce[]; // modified
    public static int shardsNum; // newly added
    public static int minersPerShard; // newly added

    private int difficulty;
    private long prevInfo;
    private int shardID; // newly added

    public int index;
    public String solution;
}

Results and Discussion

After all code modifications needed for the upgrade from a single-chain to a sharded-chain being done, we can finally test and compare the performance.

First, I set up the PoW difficulty level and the number of miners to be 4 for both single chain and sharded chain, which made the only difference to be the Blockchain data structure. I let both the single chain and the sharded chain systems to run for 15, 20, and 25 mining iterations, and I observed the transactions confirming rate of them. I got Figure-1 as followed:

In Figure-1, we can compare the transactions confirming rate between the classic single chain and the chain with sharded blocks. It not only shows the general better performance of the sharded chain but also shows that as more and more mining iterations pass, the single chain easily stucks at a confriming rate bottleneck, while the sharded chain clearly has a bigger growing space of transaction processing rate.

If we focus on the number of backlog transactions after 15, 20, and 25 mining iterations for both single chain and sharded chain system, we can see a pattern as followed:

In Figure-2, the advantage of sharded chain is more obvious. When the single chain has more and more serious mining congestion problem, the sharded chain shows a perfect transactions processing capability that eliminates the mining congestion problem when mining iterations being less than 25.
These two figures indicate a huge improvement of transactions processing throughput when update the single chain to a sharded chain.

What’s more, the sharded chain can have even better performance as it showed in Figures above. When the number of miners in the network grows, the transaction processing capability of the system grows with it.

I let the sharded chain system run for 15, 20, 25, 35, and 50 iterations with 4 miners and 6 miners. The difficulty level remained 4. It was possible to have at most 2 shards for the 4-miners system and 3 shards for the 6-miners system. Notice that as more and more iterations passed, the transactions load in my simulation tended to grow exponentially.

In Figure-3 and Figure-4, we can see clearly that the transactions confirming rate grows quicker with 6 miners. Also the number of backlog transactions grows much slower with 6 miners. This shows how dramatically the increase of miner numbers can improve the transactions processing capability of the system.

Conclusion

In this simulation, some assumptions have been made in order to focus on my main concern and avoid unnecessary complexity of the model. As the simulation successfully shows how sharding and parallel mining can dramatically improve the transactions processing capability, it gives us hope that we can apply sharding to the real world Blockchain to promote the transactions processing throughput to make it more realistic to apply Blockchain technology to more areas.

In the real world Blockchain systems with distributed network envolved, to be able to upgrade a single chain to a sharded chain, extra works are required on managing the communications among different shards. In the future, I will explore how to maintain a safe and efficient cross-shards communications so that not only the transactions processing throughput are enhanced but also the double-spending problem can be eliminated and the safety of the network is kept.

In the last two blogs, I have introduced how I gradually implemented most of the properties of a typical ProofofWork(PoW) Blockchain including the simulation for transactions generating, transactions processing, and the PoW algorithm. However, I made an assumption that no mining competition really happened, in other words, I just randomly picked one miner to be the winner. In this blog, in order to make the consensus mechanism more realistic, I will introduce how to simulate the mining competition between multiple miners.

Multiple Miners Simulation via Multithreading

The basic idea is to implement competing miners as concurrent mining threads. Therefore, I created a Miner class and let it extend the Thread class which provides multithreading properties. Additionally, I used a couple of class variables(static variables) to support communication between threads.

class Miner extends Thread {
    public static boolean solutionClaimed = false;
    public static int claimerID = -1;
    public static int candidate = Integer.MIN_VALUE;
    public static ArrayList<Boolean> consensusList = new ArrayList<Boolean>();
    public static int minerNum = 0;
    public static String final_nounce;

    private int difficulty;
    private long prevInfo;

    public int index;
    public String solution;

    public Miner(String minerID, long prevInfo, int difficulty) {
        super(minerID);
        index = minerNum;
        minerNum++;
        consensusList.add(false);
        solution = "";
        this.prevInfo = prevInfo;
        this.difficulty = difficulty;

        //System.out.println("Creating miner thread: " + minerID);
    }

    public void run() {
    // TODO: Proof-of-Work
    }
    ...
}

Variables

The static integer variable minerNum is for tracking the total number of constructed miner threads, and it is used to initiate the non-static variable index which identifies each thread among all. The static boolean arraylist consensusList has the length of minerNum, and each element of it indicates an individual miner’s attitude to the PoW solution provided by certain miner who claims to solved the PoW. The static integer variable claimerID indicates which miner claims that he/she solves the PoW and the static integer variable candidate is the integer provided by the claiming miner that sha256(candidate+previousBlock.timestamp) contains the required number of leading zeros. The static String variable final_nounce is generated by concatenating verified candidate value and the timestamp of previous block.
The non-static variable difficulty and prevInfo are passed to the miner thread while constructing and are used to compute the satisfying nounce.

Methods

To achieve concurrent mining among multiple miners(threads), I overrided the void run() method with the PoW algorithm:

    @Override
    public void run() {
//      System.out.println("Running miner thread: " + this.getName());
        int nounce = Integer.MIN_VALUE;
        while (!consensusAchieved()) {
            while (!solutionClaimed && !numLeading0is(difficulty, Encryption.sha256("" + nounce + prevInfo))) {
                nounce++;
                if (nounce == Integer.MAX_VALUE
                        && !numLeading0is(difficulty, Encryption.sha256("" + nounce + prevInfo))) {
                    prevInfo++;
                    nounce = Integer.MIN_VALUE;
                }
            }
            if (solutionClaimed) {
                // if someone else claims that a solution is found, verify that
                if (numLeading0is(difficulty, Encryption.sha256("" + candidate + prevInfo))) {
                    consensusList.set(index, true);
                } else {
                    // if this candidate fails the verification
                    resetConsensus();
                }
            } else if (numLeading0is(difficulty, Encryption.sha256("" + nounce + prevInfo))) {
                // if this miner finds a solution, report to the public, and wait for
                // verification
                solutionClaimed = true;
                consensusList.set(index, true);
                candidate = nounce;
                claimerID = index;
            }
        }
        final_nounce = "" + candidate + prevInfo;
        System.out.println("Miner" + (this.index + 1) + "(" + this.getName() + ")" + " has approved that Miner"
                + (claimerID + 1) + " came up with the correct solution: " + "\"" + final_nounce + "\"");
    }

So a Miner thread will continuously look for the satisfying nounce until it find it or any other miner thread claims to find it. When a Miner thread claims to find a satisfying nounce, it will set the static boolean variable solutionClaimed to be true in order to inform other concurrent threads to stop trying temporarily and verify the value it just put into the static int variable candidate. If a Miner thread of index i approves of the candidate value, it will set consensusList[i] to be true. If all Miner threads agreed that the candidate is satisfying, then they will all terminate and then the consensus is achieved. So the following method determines whether the consensus is achieved:

    private boolean consensusAchieved() {
        boolean agree = true;
        for (int i = 0; i < consensusList.size(); i++) {
            if (consensusList.get(i) == false) {
                agree = false;
                break;
            }
        }
        return agree;
    }

Notice that whenever a Miner finds that the the candidate doesn’t satisfiy the requirement for the nounce, all verifying work will stop and the current claim of solution will be ignored and all threads will continue looking for the correct nounce. Thus, we need a method to reset all static variables to the default value. Also, every time a new Block is about to be mined, a new competition of finding the nounce happens. So before each iteration of Block mining, we need to reset the static variables too.

    ...
    // called from inside the class Miner
    private void resetConsensus() {
        // 1, reset the consensusList to all false
        for (int i = 0; i < consensusList.size(); i++) {
            consensusList.set(i, false);
        }
        // 2, reset candidate
        candidate = Integer.MIN_VALUE;
        // 3, reset solutionClaimed to false
        solutionClaimed = false;
        // 4, reset claimerID to -1
        claimerID = -1;
    }
    ...
    // called from outside the class Miner
    public static void reset() {
        solutionClaimed = false;
        claimerID = -1;
        candidate = Integer.MIN_VALUE;
        for (int i = 0; i < consensusList.size(); i++) {
            consensusList.removeAll(consensusList);
        }
        minerNum = 0;
        final_nounce = "";
    }
    ...

Besides creating this Miner class, I also modified the Beecoin class, specifically, the mine() method. This is neccessary since now the winner miner is not randomly picked from all miners but is approved by all other miners.
The modified version of mine() method:

    public static Block mine() {
        Block lastBlock = blockchain.get(blockchain.size() - 1);
        //String miner_address = getMinerAddr();
        Miner.reset();
        for (int i = 0; i < miners_address.size(); i++) {
            Miner mt = new Miner(miners_address.get(i), lastBlock.getTimestamp(), DIFFICULTY);
            miner_threads.add(mt);
            mt.start();
        }
        for (int i = 0; i < miner_threads.size(); i++) {
            try {
                miner_threads.get(i).join();
            } catch (InterruptedException e) {
                System.out.println("Thread interrupted.");
            }
        }
        System.out.println();
        miner_threads.removeAll(miner_threads);
        //String nounce;
        //nounce = proofOFwork(lastBlock.getTimestamp());
        Block next = createNextBlock(lastBlock, Miner.final_nounce);
        Transaction nextToBeConfirmed[] = new Transaction[Block.BLOCK_SIZE];
        String miner_address = miners_address.get(Miner.claimerID);
        // rewards to the miner will be the first txion
        nextToBeConfirmed[0] = new Transaction("System", miner_address, MINING_REWARDS, true);
        retreiveVerifiedTxions(nextToBeConfirmed);
        next.setTransactions(nextToBeConfirmed);
        next.setNote("This is Block #" + next.getIndex());
        next.setHash();

        return next;
    }

The main difference, is that I used two for loops to start all miner threads and join all of them. Now when we create a new Block, we don’t pass in return value of proofOFwork() method in Beecoin class, and instead, we pass in the static variable final_nounce of Miner class. And the winner miner’s address will be retrieved according to the static variable claimerID of Miner class.

Test

I let the miner thread print some message when it verifies a solution, and I run the whole Beecoin project I get following result:

Miner1(617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e) has approved that Miner2 came up with the correct solution: "-21473401071543985328663"
Miner3(a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996) has approved that Miner2 came up with the correct solution: "-21473401071543985328663"
Miner2(ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd) has approved that Miner2 came up with the correct solution: "-21473401071543985328663"
Miner4(75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac) has approved that Miner2 came up with the correct solution: "-21473401071543985328663"

Miner4(75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac) has approved that Miner1 came up with the correct solution: "-21474082291543985329102"
Miner2(ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd) has approved that Miner1 came up with the correct solution: "-21474082291543985329102"
Miner1(617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e) has approved that Miner1 came up with the correct solution: "-21474082291543985329102"
Miner3(a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996) has approved that Miner1 came up with the correct solution: "-21474082291543985329102"
...

The output above shows the mining competition before first two blocks are mined. Miner2 won the first competition and Miner1 won the second. All miners approved their solution too.

Discussion

In this blog I present how I simulate mining competition with multiple threads and now the simulation has become more complete. Next time I will try to implement the idea of sharding by maintaining multiple chains with multithreading.

In part 1, a rough structure design of Block and Blockchain has been completed. However, as a simulated ledger system, it is very incomplete since there is no transaction to record at all and there is a missing part of digital coin minting. Also there should be a Proof-Of-Work algorithm to make sure the validity of a miner to append a new Block to the Blockchain.

Simulating transactions

Before we can simulate a transaciton, first thing to do is defining a Transaction object:

import lombok.AllArgsConstructor;
import lombok.Getter;
import lombok.Setter;
import lombok.ToString;

@Getter
@Setter
@AllArgsConstructor
@ToString
public class Transaction {
    private String senderID;
    private String recepientID;
    private double amount;
    private boolean verified;

    public Transaction(String iID, String rID, double amt) {
        this.senderID = iID;
        this.recepientID = rID;
        this.amount = amt;
        this.verified = false;
    }
}

In part1 where there wasn’t a Transaction class defined, we kept a String ArrayList for tracking the transactions waiting to be verified. Now we should modify it to be a Transaction ArrayList:

private static ArrayList<Transaction> transactions = new ArrayList<>();

Since my entire simulation will be local(no network envolved), there won’t be any real transaction broadcasting. In such situation, we can randomly simulate some Transactions and add them to the Transaction ArrayList above in every mining iteration. Additionaly, since each transaction sender must have some coins, keepying another ArrayList: coinHolders is helpful for us to randomly pick a sender.

private static final int MAX_TXIONS_EACH_PERSON_EACH_EPOCH = 5;
...
    public static void simulateTransactions() {
        // only work when at least one person holds some coins
        if (!coinHolders_address.isEmpty()) {
            int numTxions = 0;
            for (int i = 0; i < coinHolders_address.size(); i++) {
                numTxions += (int) (MAX_TXIONS_EACH_PERSON_EACH_EPOCH * Math.random());
            }
            for (int i = 0; i < numTxions; i++) {
                simulateAtransaction();
            }
        }
    }

    public static void simulateAtransaction() {
        // randomly pick an sender
        String sender = getSender();
        double issBallence = getBalance(sender);
        double amount = ((int) (issBallence * Math.random() * 100)) / 100.0;
        String recepient = getRecepient(sender);
        transactions.add(new Transaction(sender, recepient, amount));
    }

    public static String getSender() {
        return coinHolders_address.get((int) ((Math.random() * coinHolders_address.size())));
    }

    public static String getRecepient(String sender) {
        String recepient = null;
        double isNewUser = Math.random();
        if (coinHolders_address.size() == 1 || isNewUser < 0.5) {
            recepient = Encryption.sha256("coinHolder" + coinHolders_address.size());
        } else {
            do {
                recepient = coinHolders_address.get((int) ((Math.random() * coinHolders_address.size())));
            } while (recepient == null || recepient.equals(sender));
        }

        return recepient;
    }

    public static double getBalance(String addr) {
        double balance = 0;
        for (int i = 1; i < blockchain.size(); i++) {
            Block currB = blockchain.get(i);
            for (int j = 0; j < Block.BLOCK_SIZE; j++) {
                Transaction currT = currB.getTransactions()[j];
                if (currT == null) {
                    break;
                }
                if (currT.getRecepientID().equals(addr)) {
                    balance += currT.getAmount();
                } else if (currT.getSenderID().equals(addr)) {
                    balance -= currT.getAmount();
                }
            }
        }

        return balance;
    }

In the code above, some assumptions are made. For example, we assume for each mining iteration, one user can send 0-5 transactions. As a result, the number of newly-generated transactions in each mining iteration can be calculated by:

    for (int i = 0; i < coinHolders_address.size(); i++) {
        numTxions += (int) (5 * Math.random());
    }

Also, in method getRecepient(), we assume that for each transaction, the recepient is either a new user or an existing user tracked in ArrayList: coinHolders, and the chance for each possibility is 50%.
What’s more, for each transaction, we assume the amount of coins is randomly between 0 and the sender’s wallet balance. The method getBalance() is used to determine the balance of a given user.
Now, where does the coin come from?

Mining and Minting

First, let’s define the process of mining as two sections:

1. Performing Proof-Of-Work;
2. Verifying and retrieving valid transactions;

In a real-world PoW Blockchain network, the PoW algorithm is used to help achieving consensus of who is the rightful one to append the new Block to the chain and get awarded among all competing miners. As mentioned before, my current simulation will not envolve any network and will stay local for now, the mining competition will be simulated using some other simple assumptions. Afterall, how different Blockchain structure will affect the processing rate is the core problem we want to figure out here.
For now, we simply assume that there are 4 miners totally, and keep track of them with a global ArrayList: miners_address:

    private static ArrayList<String> miners_address = new ArrayList<>();

At the beginning of each mining iteration, we simulate the mining competition by randomly picking one of the miners from the list:

    public static String getMinerAddr() {
        return miners_address.get((int) ((Math.random() * MINERS_NUM)));
    }

For the Proof-Of-Work algorithm, it will require the miner to find an Integer value, namely nounce, that the hash value of the concatenation String of nounce and previous Block’s timestamp contains given number of leading 0’s. The number of leading 0’s is the difficulty of the PoW algorithm and maintained as a global constant.

    private final static int DIFFICULTY = 4;

At this time, we should also add nounce and difficulty as two extra data members to the Block class, the complete version of Block class definition should be:

import java.util.Date;

import lombok.Getter;

@Getter
public class Block {
    private int index;
    private long timestamp;
    private String note;
    private Transaction transactions[];
    private String prev_hash;
    private String hash;
    private int difficulty;
    private String nounce;

    public static final int BLOCK_SIZE = 20;

    public Block(int index, String prev_hash, String nounce, int difficulty) {
        this.index = index;
        this.timestamp = new Date().getTime();
        this.prev_hash = prev_hash;
        this.hash = calcHash();
        this.nounce = nounce;
        this.difficulty = difficulty;
        transactions = new Transaction[BLOCK_SIZE];
    }

    public void setNote(String note) {
        this.note = note;
    }

    public void setTransactions(Transaction[] transactions) {
        // make a deep copy
        for (int i = 0; i < this.transactions.length; i++) {
            this.transactions[i] = transactions[i];
        }
    }

    public String toString() {
        return ("Block #" + this.index + "\n\tmined at: " + this.timestamp + "\n\tNote: " + this.note
                + "\n\tTransactions: " + this.transactions + "\n\tHash: {" + this.hash + "}\n");
    }

    private String calcHash() {
        return Encryption.sha256(this.index + this.timestamp + this.note + this.transactions + this.prev_hash);
    }
}

The PoW algorithm is as below:

    // this PoW algorithm tries to find an integer 'nounce',
    // so that sha256(nounce+previous_block.timestamp) contains the required number
    // of leading 0's.
    public static String proofOFwork(long prevTimestamp) {
        int nounce = Integer.MIN_VALUE;
        while (!numLeading0is(DIFFICULTY, Encryption.sha256("" + nounce + prevTimestamp))) {
            nounce++;
            if (nounce == Integer.MAX_VALUE
                    && !numLeading0is(DIFFICULTY, Encryption.sha256("" + nounce + prevTimestamp))) {
                prevTimestamp++;
                nounce = Integer.MIN_VALUE;
            }
        }

        return ("" + nounce + prevTimestamp);
    }

If all Integer values has been tried and no satisfying nounce value has been found, it will increment the previous Block’s timestamp by 1 milliseconds and try again from there. We can use a method numLeading0is() to deteremine whether the satisfying nounce is found.

    public static boolean numLeading0is(int amount, String hash) {
        boolean result = true;
        int count = 0;
        for (int i = 0; i < hash.length(); i++) {
            if (hash.charAt(i) == '0') {
                count++;
            } else {
                break;
            }
        }
        if (count != amount) {
            result = false;
        }

        return result;
    }

When a miner solves the PoW problem, the next thing to do is to verify and retreive transactions from the transactions waiting list. The size of a Block is fixed, so that the number of transactions to put on a Block is also fixed, in this case, I define it to be 20.
To verify a transaction, we must check if the sender’s account balance is no less than the amount of coins he/she wants to send. A tricky part is that we should not simply calculate the account balance according to transactions in all existing Blocks, but we also need to dynamically check the account balance according to each new transaction we are going to add to the new Block. For example, if Bob has 10 coins by the latest Block, but 3 of the 20 new transactions indicate that Bob totally going to send 5 coins to three other people. Alghough Bob’s account balance seems to be valid for each 5-coin transaction, but after the first two 5-coins transactions, he’s balance dropped to zero and he will not be able to send 5 more coins to the third people. If we verify all three transactions to be valid, a double-spent problem arises.

    public static void retreiveVerifiedTxions(Transaction[] nextToBeConfirmed) {
        HashMap<String, Double> tempBalanceMap = new HashMap<String, Double>();
        int i = 1;
        while (nextToBeConfirmed[nextToBeConfirmed.length - 1] == null && !transactions.isEmpty()) {
            Transaction curr = transactions.get(0);
            String sender = curr.getSenderID();
            double balance;
            if (tempBalanceMap.containsKey(sender)) {
                balance = tempBalanceMap.get(sender);
            } else {
                balance = getBalance(sender);
                tempBalanceMap.put(sender, balance);
            }
            if (balance < curr.getAmount() || curr.getAmount() == 0.0) {
                curr.setVerified(false);
            } else {
                curr.setVerified(true);
                nextToBeConfirmed[i] = new Transaction(curr.getSenderID(), curr.getRecepientID(), curr.getAmount(),
                        true);
                i++;
                balance -= curr.getAmount();
                tempBalanceMap.put(sender, balance);
            }
            transactions.remove(curr);
        }
    }

In the method above, we use a local variable to hold user’s account balance by the last Block, and dynamically adjust the balance according to the new transactions we are verifying. Also, when a transaction from the waiting list is checked, no matter it is valid or not, we remove it from the waiting list.
Although we allow each Block capable of recording 20 transactions, each time we can only retrieve 19 transactions at most from the waiting list. This is because we must always leave the first spot for the system’s rewarding to the miner.
The implementation of mine() method is as followed:

    public static Block mine() {
        Block lastBlock = blockchain.get(blockchain.size() - 1);
        String miner_address = getMinerAddr();
        String nounce;
        nounce = proofOFwork(lastBlock.getTimestamp());
        Block next = createNextBlock(lastBlock, nounce);
        Transaction nextToBeConfirmed[] = new Transaction[Block.BLOCK_SIZE];

        // rewards to the miner will be the first txion
        nextToBeConfirmed[0] = new Transaction("System", miner_address, MINING_REWARDS, true);
        retreiveVerifiedTxions(nextToBeConfirmed);

        next.setTransactions(nextToBeConfirmed);
        next.setNote("This is Block #" + next.getIndex());

        return next;
    }

Method mine() returns the newly generated Block, we shall append the new Block to the Blockchain:

    newBlock = mine();
    blockchain.add(newBlock);

As a Block appended to the Blockchain, finally the transactions recorded in that Block can be considered confirmed. For our simulation, the global ArrayList: coinHolders shall be updated after each mining iteration by adding any new user to the list:

    public static void main(String[] args) {
        ...
        updateCoinHolders(newBlock);
        ...
    }
    ...
    public static void updateCoinHolders(Block block) {
        for (int i = 0; i < Block.BLOCK_SIZE; i++) {
            Transaction curr = block.getTransactions()[i];
            if (curr == null) {
                break;
            } else {
                addCoinHolder(curr.getRecepientID());
            }
        }
    }

Test

By now, most important functionality of a Blockchain has been implemented or simulated. Let’s test the code by making 6 Blocks to be mined. And for the sake of future expansion to a network-envolved version, let’s convert the blockchain to a JSON object and print the whole chain:

    ...
    private final static int MAX_BLOCKS = 6;
    ...
    public static void main(String args[]) {
        Block newBlock = createGenesisBlock();
        blockchain.add(newBlock);
        miners_address = loadMiners();

        for (int i = 0; i < MAX_BLOCKS; i++) {
            simulateTransactions();
            newBlock = mine();
            blockchain.add(newBlock);
            updateCoinHolders(newBlock);
//          updateTransactions(newBlock);
        }

        String blockchainJson = new GsonBuilder().setPrettyPrinting().create().toJson(blockchain);
        System.out.println(blockchainJson);
    }

The result should be something like:

[
  {
    "index": 0,
    "timestamp": 1542333495628,
    "note": "Everything starts from here!",
    "transactions": [
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "0",
    "hash": "9dc089f9d9b28e8b81ed273ca8e49fe8d477e2b3755c0f4f1f4ac23caebf0506",
    "difficulty": 4,
    "nounce": "no nounce for the first time"
  },
  {
    "index": 1,
    "timestamp": 1542333495841,
    "note": "This is Block #1",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "amount": 6.0,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "9dc089f9d9b28e8b81ed273ca8e49fe8d477e2b3755c0f4f1f4ac23caebf0506",
    "hash": "d9616fccd217f982acb260c9103a03124e10d63ace6fa69f29ab692d2799f620",
    "difficulty": 4,
    "nounce": "-21474117981542333495628"
  },
  {
    "index": 2,
    "timestamp": 1542333496105,
    "note": "This is Block #2",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "amount": 6.0,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "d9616fccd217f982acb260c9103a03124e10d63ace6fa69f29ab692d2799f620",
    "hash": "75697a650b3ca50a656816c10b9a3bad60080c187fdaebdb8569ee8a12cc2837",
    "difficulty": 4,
    "nounce": "-21473512071542333495841"
  },
  {
    "index": 3,
    "timestamp": 1542333496351,
    "note": "This is Block #3",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "amount": 6.0,
        "verified": true
      },
      {
        "senderID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "recepientID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "amount": 4.61,
        "verified": true
      },
      {
        "senderID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "recepientID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "amount": 3.21,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "75697a650b3ca50a656816c10b9a3bad60080c187fdaebdb8569ee8a12cc2837",
    "hash": "5ebe4d139e424e8ca29c2d70ac21149f49835e1d0951aab803da85252f9a807d",
    "difficulty": 4,
    "nounce": "-21473604601542333496105"
  },
  {
    "index": 4,
    "timestamp": 1542333496378,
    "note": "This is Block #4",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd",
        "amount": 6.0,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "5ebe4d139e424e8ca29c2d70ac21149f49835e1d0951aab803da85252f9a807d",
    "hash": "ad22feea01346082fb78ab6af40a759abd3e6453718914379695b8fe60152f80",
    "difficulty": 4,
    "nounce": "-21474666701542333496351"
  },
  {
    "index": 5,
    "timestamp": 1542333496692,
    "note": "This is Block #5",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e",
        "amount": 6.0,
        "verified": true
      },
      {
        "senderID": "ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd",
        "recepientID": "22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983",
        "amount": 1.29,
        "verified": true
      },
      {
        "senderID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "recepientID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "amount": 2.74,
        "verified": true
      },
      {
        "senderID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "recepientID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "amount": 2.38,
        "verified": true
      },
      {
        "senderID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "recepientID": "ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd",
        "amount": 6.75,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "ad22feea01346082fb78ab6af40a759abd3e6453718914379695b8fe60152f80",
    "hash": "a190f7ac0ea77dd1086c7be51c98f99610107ee776473928c43207f246a5fe0a",
    "difficulty": 4,
    "nounce": "-21473289591542333496378"
  },
  {
    "index": 6,
    "timestamp": 1542333496810,
    "note": "This is Block #6",
    "transactions": [
      {
        "senderID": "System",
        "recepientID": "617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e",
        "amount": 6.0,
        "verified": true
      },
      {
        "senderID": "ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd",
        "recepientID": "22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983",
        "amount": 6.87,
        "verified": true
      },
      {
        "senderID": "22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 0.1,
        "verified": true
      },
      {
        "senderID": "22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 0.07,
        "verified": true
      },
      {
        "senderID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 1.8,
        "verified": true
      },
      {
        "senderID": "617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 4.53,
        "verified": true
      },
      {
        "senderID": "a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996",
        "recepientID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "amount": 3.6,
        "verified": true
      },
      {
        "senderID": "75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 1.94,
        "verified": true
      },
      {
        "senderID": "22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983",
        "recepientID": "0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5",
        "amount": 0.34,
        "verified": true
      },
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null,
      null
    ],
    "prev_hash": "a190f7ac0ea77dd1086c7be51c98f99610107ee776473928c43207f246a5fe0a",
    "hash": "01a8365ea5e74f93e8bd48c0a990b999555efbf4b37736236acbc62acb745a56",
    "difficulty": 4,
    "nounce": "-21474252741542333496692"
  }
]

This time, the output Blockchain looks very close to the real-world one.
We should also validate this Blockchain works well as a ledger, and we can do this by comparing the amount of coins minted and the amount of coins belonging to all coin holders, let’s print them all out:

    public static void main(String args[]) {
        // mined 6 blocks
        ...
        System.out.println("\nAll minted coins: " + MAX_BLOCKS * MINING_REWARDS);
        double coinsOfHolders = 0;
        for (int i = 0; i < coinHolders_address.size(); i++) {
            coinsOfHolders += getBalance(coinHolders_address.get(i));
        }
        System.out.println("All coins in coinHolders: " + coinsOfHolders + "\n");
        printCoinHolders();
        ...
    }
    ...
    public static void printCoinHolders() {
        for (int i = 0; i < coinHolders_address.size(); i++) {
            String addr = coinHolders_address.get(i);
            System.out.println(addr + " owns: " + getBalance(addr));
        }
    }

And we shall be able to see the result matching our expectation:

All minted coins: 36.0
All coins in coinHolders: 36.0

75ec216e32856f59cf033dd89fbb1bcd570506c3ccce1a2c2d9e2ebcdcdbd6ac owns: 5.87
a3cc07dee0ea2341a89e117eb12cbbed3739912c8dde4704649c5b73c570d996 owns: 1.64
ada68893c9c6fa324307c3964f1eb6d871253665b0d0173168032da8a7b8a2fd owns: 4.59
617b672120aa914054db960299fc1fa8c229e8b31ed596c651cfad09d04d336e owns: 7.47
22f1f8d4b2551a72eb3a49b5365716999b19da1e6ff9e129b13ddd88fbce8983 owns: 7.65
0ce3dfe2ad6326428519678a2211549ac96e2da77466e4657fae03fadbbae5a5 owns: 8.78

Discussion

As the Blockchain transactions processing rate is my main concern, I observed the transaction processing performance by tuning the number of Blocks to be mined. As I saw, even for such a simple Blockchain following Bitcoin’s general design protocol, the scalibility problem is obvious that when 20 Blocks has been mined, which means 20 mining iterations has passed, there were 37 unconfirmed transactions staying in the waiting list. This means that the transactions processing rate is slower than the transactions producing rate. I will observer the performance and make a comparison when a sharding version is implemented.
So far this is very complete for a local Blockchain, a “non-distributed” ledger. The only thing missing is a more realistic simulation of mining competition between miners.
I will furthur expand my code into a multi-threaded version, so that each thread can play the role of a competing miner, and several threads will be searching for the satisfying nounce concurrently. When one of the thread finds the nounce, a global variable will hold that nounce, and other threads will verify that nounce. If all miners find it valid, then a concensus is achieved.

For my project, I’m seeking for solutions to increase the transaction processing throughput of the distributed ledger technology. In order to observe how different factors would affect the Blockchain performance, I would will simulate a Blockchain system with the Proof-of-Work(POW) consensus protocol in Java and all my exploration will be based on that.

First, I will start with the implementation of the fundamental Block data structure and a local Blockchain

A Block is nothing but just a data structure that each instance of it stores some valuable data and some unique identifying information which protects the data from any malicious modification. In the area of cryptocurrency, Block is used to record transactions. Apart from the transactions data, a Block also stores a timestamp which indicates when this block is generated, a hash value of the previously generated Block, and a hash value of its own.

It is containing the hash value of previous Block that links all the Blocks togetherand eventually make them a robust chain. Since each Block’s hash is related to the one before it, modifying any Block will cause a conflict of its hash value recorded by its own and the Block next to it. A real world Block in a PoW-based Blockchain actually still needs to store at least two additional variables: nounce and difficulty to support the PoW mechanism, but I will not include them here and leave them in Part2.

In Java, we will make the Block an object, so let’s write a Block class first:

import java.util.Date;

public class Block {
    public int index;
    public long timestamp;
    public String data;
    public String prev_hash;
    public String hash;

    public Block(int index, String data, String prev_hash) {
        this.index = index;
        this.timestamp = new Date().getTime();
        this.data = data;
        this.prev_hash = prev_hash;
        this.hash = getHash();
    }
}

Now only the hashing algorithm is missing. For the sake of easy future extension on the hashing algorithm, I will also put the hashing method in a separate class: Encrption. Also, for simplicity, in this project, I will follow Bitcoin‘s approach using sha256 for hashing.

Since the sha256 hashing method from Java’s built-in MessageDigest class will outpout the hash in byte type and my Block object holds hash as String, I will also convert the hash from byte to a String of hexadecimal after hashing.
This part is inspired by this page: https://www.baeldung.com/sha-256-hashing-java

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class Encryption {
    public static String sha256(String origin) {
        MessageDigest digest = null;
        try {
            digest = MessageDigest.getInstance("SHA-256");
        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
        byte[] byteHash = digest.digest(origin.getBytes(StandardCharsets.UTF_8));

        StringBuffer hexHash = new StringBuffer();
        for (int i = 0; i < byteHash.length; i++) {
            String hexDigit = Integer.toHexString(0xff & byteHash[i]);
            if (hexDigit.length() == 1) {
                hexHash.append('0');
            }
            hexHash.append(hexDigit);
        }
        return hexHash.toString();
    }
}

Now, back to the Block class, I will add an getHash() method which will use the Encryption class to hash the Block information:

private String getHash() {
        return Encryption.sha256(this.index + this.timestamp + this.data + this.prev_hash);
    }

By now, the basic Block data structure has been completed. I will build a Blockchain class to bring the blockchain to life. Here I will implement the Blockchain as an ArrayList of Blocks. Besides the blockchain list, I add another list of String, which is used to collect all transactions that are waiting to be validated. I will leave it empty for now.

import java.util.ArrayList;
public class Blockchain {
    public static ArrayList<Block> blockchain = new ArrayList<>(); // The blockchain is implemented as an arraylist of Blocks
    public static ArrayList<String> transactions = new ArrayList<>();
}

Next, to bring the genesis of the blockchain, let’s have a createGenesisBlock() method that generates the first block in the chain for us:

public static Block createGenesisBlock() {
        return new Block(0, "\"Everything starts from here!\"", "0");
    }

As it doesn’t have any previous block, I simply hardcode the previous hash to zero.
Now I need another method that can be used to repeatedly generate new Block based on the lastest Block, this time we need to record the collected transactions information too:

public static Block createNextBlock(Block prevBlock) {
        return new Block(prevBlock.index + 1, transactions.toString(), prevBlock.hash);
    }

Now, every basic functionality of the Block and Blockchain is implemented. To be able to test these visibly, I override the toString() method of the Block class and add a printChain() method to the Blockchain class.

public class Block{
    ... 
    public String toString() {
        return ("Block #" + this.index + "\n\tmined at: " + this.timestamp + "\n\tData: " + this.data + "\n\tHash: {"
                + this.hash + "}\n");
    }
    ...
}

public class Blockchain{
    ... 
    public static void printChain() {
        for (int i = 0; i < blockchain.size(); i++) {
            System.out.println(blockchain.get(i));
        }
    }
    ...
}

Finally, we can test all the works by now. Let’s call createGenesisBlock() in main() and try to add 20 more Blocks to the chain and print out the chain:

public class Blockchain{
    ...
    public final static int NUM_BLOCKS = 20;

    public static void main(String args[]) {
        blockchain.add(createGenesisBlock()); // create genesis block and add it to the chain
        // add 20 more blocks to the chain
        for (int i = 0; i < NUM_BLOCKS; i++) {
            Block next = createNextBlock(blockchain.get(i));
            blockchain.add(next);
        }
        printChain();
    }
}

The output is below:

Block #0
    mined at: 1541753737049
    Data: "Everything starts from here!"
    Hash: {9ccb44f52cbc9fe74a673146bb751b0e280d2644e7cca40fa6ab2de1ef12491f}

Block #1
    mined at: 1541753737059
    Data: []
    Hash: {ca3b31056c8570d154d4342b30568de4bb08053cd6e2c0d942c48fcb08b8ead0}

Block #2
    mined at: 1541753737059
    Data: []
    Hash: {3b8d0515f0b851def18d77d88f1036cae16a69c81209633eada213b2cf0cb561}

Block #3
    mined at: 1541753737059
    Data: []
    Hash: {440d5309fb4273df5657c1d8739d524730b842021ea4fe20a35a40dd67537939}

Block #4
    mined at: 1541753737059
    Data: []
    Hash: {885c9e72a12933d52e3101ffa5fc20baea9a36fa1704016e7c794a57387f3dc4}

Block #5
    mined at: 1541753737060
    Data: []
    Hash: {cb16b9283b669ec6d48a8a424e621b5ab96304f515bb18ae3b8affb3ad42ad50}

Block #6
    mined at: 1541753737060
    Data: []
    Hash: {428b1fec3da2058875da8230d75eae3afacf3ea7110b1b369410cb58736f9d5a}

Block #7
    mined at: 1541753737060
    Data: []
    Hash: {d327e49f238928e77974a7c471a58477b35306563db36aabef65148ee809f3b5}

Block #8
    mined at: 1541753737060
    Data: []
    Hash: {7e82eb0afb71a38c6196a2fe5415691531715378ab85db3f9a5ffd39082a1ab0}

Block #9
    mined at: 1541753737060
    Data: []
    Hash: {a6308867ca8db751a6435a107897c2f9fc0ade5cbe8bf1e0749dedf2eeb08c98}

Block #10
    mined at: 1541753737060
    Data: []
    Hash: {ff955eec0f5cc9903385a7a3b71757f636da24d4f4c382c380761696507899fa}

Block #11
    mined at: 1541753737060
    Data: []
    Hash: {c7d7cfc7baf7822214927776b453a95487754ad842a8fdcb7d3a9376b421d132}

Block #12
    mined at: 1541753737060
    Data: []
    Hash: {5444098344c1d088ac7e6197a34d8320a3d0669cc6af1a1c912e17ca4811679d}

Block #13
    mined at: 1541753737060
    Data: []
    Hash: {dedaf1fbf35ea73c01105cd46260dfbcc503d4994af22bc0a733cf7faf01ae5f}

Block #14
    mined at: 1541753737060
    Data: []
    Hash: {b7f1b23b0dc2b16ac868703b031e270741b0faa911e610ebbc1a6b2747e59213}

Block #15
    mined at: 1541753737060
    Data: []
    Hash: {5dec33bd153bd87ca9e09770a452ed8413b55c560342ff768a3bd54bc89f7940}

Block #16
    mined at: 1541753737062
    Data: []
    Hash: {4e8c715548ede2c257d315c3ad9a67b92f2071d3fb88fbb25d7182f838b27b4e}

Block #17
    mined at: 1541753737062
    Data: []
    Hash: {c56245af9bd5a79e33378c85a8a57c1a15787e88289e02d65869444df0406c35}

Block #18
    mined at: 1541753737062
    Data: []
    Hash: {775434803233007b550958fe519152647b81ae7edf3a3f9ac7f227891c143610}

Block #19
    mined at: 1541753737062
    Data: []
    Hash: {36eaf36426c9bd6e5122fb0f65324c707ded2c7341ef1bfed4c775c259837f88}

Block #20
    mined at: 1541753737062
    Data: []
    Hash: {6546920a8779d82c918e1528ae9c5ee2ec7ab47fc7aca231f7f9a2b7c77d1544}

This result meets my expectation for the simple basic data structure, but some problems is obvious:
1. All data is blank, this is because we doesn’t have any transactions yet;
2. Blocks are generated too quickly, as we can see the timestamp are almost the same for 20 contineous blocks;
3. Coins are still missing.

In part 2, I will complete the implementation to make sure:
1. Transactions broadcasting will be simulated, so that Blocks can record transactions;
2. A Proof-of-Work algorithm will be implemented, so that we can control the Block mining rate;
3. A reward mechanism will be introduced to the Block mining process, miners will be rewarded by coins.