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:
- Performing Proof-Of-Work;
- 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.
What about loadMiner method?
In this simulation, loadMiner() method really is just used to generate a collection of miners addresses(hashed values), so that later we can use them to identify each miner during mining process.
You can choose your own way to do this, as long as the method returns an ArrayList of unique miners addresses. 🙂
What does the coinHolder array list contain? Can you provide the syntax for it?
how is the addCoinHolder method defined