Homework 5 - CACoin Mining with POSIX Threads

Blockchain and Cryptocurrencies

In the recent years, the cryptocurrency such as Bitcoin is becoming one of the hottest financial products in the world. And due to the release of COVID-19 financial stimulus plans by multiple major countries, Bitcoin is rapidly recovering from the financial depression caused by the global pandemic COVID-19 and making its history in the last a few months. On March 14, 2021, just several weeks ago, Bitcoin reached the all-time high at $61800 US dollars, with market value of over 1 trillion US dollars. This market value indicates that Bitcoin is now worth over 40% of the US dollars in circulation, or 1% of currency in the world. This also makes Bitcoin the 4th biggest currency in the world.

The Bitcoin, just like many other popular cryptocurrencies, is based on the technique of Blockchain. A blockchain is a growing list of records, called blocks, that are linked using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data. By design, a blockchain is resistant to modification of its data. This is because once recorded, the data in any given block cannot be altered retroactively without alteration of all subsequent blocks.

For Bitcoin, each bitcoin is produced by the process called "mining", which is a record-keeping (by creating new blocks) service done through the use of computer processing power. In order to "mine" Bitcoin, computers are connected to the cryptocurrency network and each "miner" (or each group of "miner") uses their computational power to compete against each other. Miners keep the blockchain consistent, complete, and unalterable by repeatedly grouping newly broadcast transactions into a block, which is then broadcast to the network and verified by recipient nodes. Each block contains a SHA-256 cryptographic hash of the previous block, thus linking it to the previous block. And once the new block is successfully created and accepted by the rest of the network, the miner who mined this block will be awarded with a certain amount of bitcoin (now it's 6.25 Bitcoin).

To be accepted by the rest of the network, a new block must contain a proof of work (PoW). Recall what you learned in the previous courses that a good hash function $h(x) = y$ should have following major properties:

• Easy to evaluate: Given a hash function $h: \mathbb{X} \rightarrow \mathbb{Y}$ and a preimage $x \in \mathbb{X}$, it is easy to compute $y=h(x)$, (takes $O(1)$).
• Preimage resistant: Given a hash function $h: \mathbb{X} \rightarrow \mathbb{Y}$ and an image $y\in \mathbb{Y}$, it is difficult to find a preimage $x\in \mathbb{X}$ such that $y=h(x)$.
• Second preimage resistant: Given a hash function $h: \mathbb{X} \rightarrow \mathbb{Y}$ and a preimage $x \in \mathbb{X}$, it is difficult to find another preimage $x'\in \mathbb{X}$ such that $x' \neq x$ and $h(x')=h(x)$.
• Uniformity: A hash function $h: \mathbb{X} \rightarrow \mathbb{Y}$ maps the preimage $x \in \mathbb{X}$ evenly to its images $y\in \mathbb{Y}$. And each $y\in \mathbb{Y}$ should be generated with roughly the same probability.

The proof of work, or PoW, requires miners to find a number called a nonce, such that when the block content is hashed along with the nonce, the result is numerically smaller than the network's difficulty target. That is, the hashed values should have multiple zeros in its higher bits. (For Bitcoin, the number of zeros is 84 now!) As you can see in the properties of hash functions, this proof is easy for any node in the network to verify, but extremely time-consuming to generate, as for a secure cryptographic hash, miners must try many different nonce values before meeting the difficulty target. And this process is also extremely power-consuming. According to the research conducted by the Cambridge University, Bitcoin now uses more electricity annually than the whole country of Argentina.

Envying of the great fortune created by Bitcoin and many other cryptocurrencies, our CS 110 staff decided to issue our own cryptocurrency: CACoin. As the enrolled CA students at ShanghaiTech, you are privileged to try out the CACoin mining. In this homework you will get to know how to mine the great CACoin on a local blockchain and compete against your peers by optimizing your mining program using POSIX Threads. In this homework, we are focusing on the creation and verification of the PoW, leaving along the distribution and acception of it in a network which requires sophisticated specialty on distributed system.

CACoin Blockchain Setup

You can get the framework file here.

In the CACoin's Blockchain, or CAChain, a basic block looks like this:

struct block {
  uint32_t index;
  uint32_t timestamp;
  unsigned char prev_hash[HASH_BLOCK_SIZE];
  unsigned char data[256];
  uint64_t nonce;
}

index : The index of the current block.

timestamp : The timestamp when the block is created, here we would provide the timestamp for you.

prev_hash: The hash value of the previous block.

data: Data stored in this block. It could be transaction information or other useful information. It is also provided to you.

nonce: The variable to be generated in order to pass the difficulty check of hash value.

You would find blkh_t in blockchain.h regarding to this block structure.

In order to make these blocks a blockchain, each block is stored in a dedicated block_node struct (which is blk_t).

struct block_node {
  blkh_t block;
  unsigned char hash[HASH_BLOCK_SIZE];
}

block: (or header) is a block described in the previous part.

hash: The hash value of the block.

When mining CACoin, you have to use the hash function provided by us (now we are using SHA-256) to calculate each block's hash value and make sure that the hash value complies with the difficulty levels. The difficulty level, or diff, means that the valid hash value of the current block must start with diff zeros in its' highest bits. Equivalently, the hash value should be less than $2^{256-diff}-1$. You will be awarded with a CACoin once a block is successfully generated. Each block may contain different information and with a difficulty of different levels.

Your Mission

As we are issuing the CACoin, we have already implemented a simple sequential CACoin mining program for you. However, as the mining program is too time-consuming, we want you, the future computer scientists, to optimize the code for us! Your final task is to mine several amounts of CACoins on our machine with shortest time you could achieve.

Based on this simple framework, you should conduct optimizations and parallelizations with pthread to accelerate the algorithm. Here are some rules:

1. As we really want to use our implementation of the hash functions, you CANNOT modify the code related to hash_functions, including hash_function.c, hash_function.h, sha256.c and sha256.h. Also, please don't change the headers such as blockchain.h or bool.h. We will replace them with a clean version or change it to another hash function we want at your submission.
2. You must introduce pthread for parallelization and feel free to modify any other files to serve your optimization.
3. Before you start, please take a good look at the Makefile. Please do NOT change the targets and file names defined in the Makefile but you are allowed to change other parts of it. The commands used to build, test, submit or clean are described in the comments of the Makefile.
4. We have provided you the test functions in test.c, which you may find useful to test the performance of your implementation. Feel free to tune the mining parameters to test your performance on a more difficult mining job.

Other Requirements

You are required to implement your CAcoin mining with following rules:

• Compilation of the source code requires no errors or warnings.
• No memory leaks are allowed. Memory leaks will be automatically detected and manually screened and will result in a deduction in your score after the deadline.

Submission and Grading

Submit your work to Autolab with an archive hw5.tar, which can be generated by $ make submission as described in Makefile.

The hw5.tar should contain exactly the following files:

hw5.tar
├── blockchain.c
└── Makefile 

We will then put in our version of hash functions and other files (*.h, hash_function.c and so on) to conduct the test. Your program is first compiled with our Makefile to make sure it compiles with no errors or warnings and conformity to the C89 standard. Then we will use your Makefile to generate binary for you and test the binary generated. You can assume the same directory structure in the auto-grader as in the starter code (e.g., the main() function will also be in test.c and so on). As we don't want the heat of CACoin mining to burn down the Autolab server and the whole SIST building, we will only let you mine 15 CACoins and give you a score according to correctness. The execution time on Autolab will also be given, but that is only a reference.

Step 1: If you submitted the correct algorithm onto Autolab, which means it makes meaningful uses of multithreading and outperforms our baseline program, you get 60% of the total score. (Memory leak check with valgrind is also included)

Step 2: After the autograding deadline, we will run your CACoin mining program on a much stronger and stabler server with sound fire equipment so that it would not burn down the building. We will mine a loooooot of CACoins there, and take the weighted average of mining time regarding the difficulty parameters. If you have earned the 60% in step 1, the rest 40% will be given based on the performance of your algorithm on the strong server. NOTE: If your program crashes when mining CACoins, then you get zero in this phase.

Server Configurations

Autolab Server (Just for your reference):

• CPUs: 2 * Intel Xeon E5-2690 v4 2.6 GHz, 14 cores (so 28 physical cores and 56 threads (logical cores) in total) Details here
• Memory: 256GB DDR4 2400MHz
• 4 threads are allowed for each grading job

Star Lab Server (Used for final speed test):

• CPU: Intel Xeon E5-2650 v3 2.3 GHz, 10 cores (20 threads) Details here

  • L1 cache 640KB per core
  • L2 cache 2560KB per core
  • L3 cache 25600KB

• Memory: 32GB