Assignment 12: Simple Blockchain

A blockchain is a popular data structure that is used in many applications, most notably in the world of cryptocurrencies. A blockchain is simply a sequence of blocks, like an array or a linked list, where each block contains some data. The catch here is that each block stores not only some data but also a hash of the previous block. (You could imagine having a struct for a block where one field is data and one more field is hash which is the hash of the previous block.) This hash is generated by running a cryptographic hash function with the input of the entire previous block, e.g., all the fields of struct for the previous block.

This kind of hashing is a simple way to check that a block's content (e.g., all the fields of the block's struct) has not changed after it's added to the blockchain. If you change any content in one block, it makes the hash of that block change, and it will no longer match the hash stored in the next block. This way, you can detect if a block's content has changed by calculating the hash of the block and comparing it to the hash stored in the next block. If they differ, you know that the block's content has changed.

What this means is that, you could potentially avoid the tampering detection by not only modifying the content in one block (say, Block A), but also modifying the hash stored in the next block (say, Block B). However, this needs more work than it appears. Modifying the hash stored in Block B means that you're changing the content of Block B. In turn, it means that it will change the hash of Block B, and it won't match the hash stored in the next block of Block B (say, Block C). Thus, in order to avoid tampering detection, you further needs to modify the hash stored in Block C as well. But then this changes the content of Block C, which changes the hash of Block C. This goes on until the end of the block. Thus, if you want to successfully tamper with one block, you need to tamper with all the blocks that come after it, which can be a computationally challenging task.

To make it even more challenging, a typical blockchain requires that newly-added blocks meet certain conditions. For example, Bitcoin, a popular cryptocurrency, has a target hash and a new block must have a hash value that is less than or equal to the target. Remember that a hash of a block is still a number generated by running a cryptographic hash function with the input of the entire block (all the fields). If the values of the these fields are all fixed, every time you run the cryptographic hash function, you will get the same hash. In case of Bitcoin, if this hash is not less than or equal to the target hash, you will not satisfy the requirement for a new block, and you won't be able to add it to the blockchain. So what do we do?

To allow this, each block also stores a nonce, which is a number that one can vary to create a hash that satisfies the condition. So now you would have at least three fields for a block's struct, data, previous block's hash, and nonce. For a new block, you can calculate the hash with one nonce value and check if the hash is less than or equal to the target. If not, you change the nonce value and try again. You can keep doing this until you generate a hash that is less than or equal to the target hash.

As you can imagine, it is computationally challenging to find such a nonce, i.e., it requires a lot of trials. Thus, the process of finding a correct nonce has a fitting name, mining, analogous to mining for precious metals such as gold. One needs to try a very large number of different nonces to find the one that creates a hash that satisfies the condition. In Bitcoin, miners are rewarded with new Bitcoins for successfully mining a new block.

In this assignment, you will implement a simple blockchain.

Block

Each block is a data structure defined in include/blockchain.h. It contains the following fields.

• core: the core of the block that contains the following fields.
  • index: the index of the block in the blockchain.
  • timestamp: the time when the block was created.
  • data: the data that the block contains.
  • p_hash: the hash of the previous block.
  • nonce: a number that is used to create a hash that satisfies a certain condition.
• hash: the hash of the current block.

Each block should satisfy the following conditions.

• The hash of a block is created by hashing the block core (i.e., the entire struct block_core) using SHA256.
• index should start from 0 (for the first block) and increase monotonically by one for each new block.
• timestamp should contain the creation time of each block. You should use clock_gettime() with CLOCK_REALTIME to get the current time. (man clock_gettime for more information.)
• data should store the bytes passed as an argument for the bc_add_block() function described below.
• The hash of a block should be less than or equal to the target hash (difficulty) specified in the bc_init() function described below. Your program needs to find a correct nonce by trying different nonces until it finds the one that creates a hash that satisfies the difficulty. In a typical blockchain, the target hash decreases over time to make it more and more difficult to find a correct nonce. However, in this assignment, the target hash is fixed per blockchain and you don't need to worry about changing it. The target hash can differ between blockchains, but it is fixed for each blockchain.
• The hash of the current block should match the p_hash field of the next block.
• The p_hash field of the first block is 0. You still need to find the correct nonce for the first block that satisfies the hash condition.

Blockchain

A blockchain is a data structure that contains an array of blocks. It is defined in include/blockchain.h. Along with it, you need to implement the following functions.

• bc_init(): initializes the blockchain. It should initialize the buffer passed as the argument and use the hash target also passed as an argument (difficulty). If difficulty is NULL, it means that there is no target hash. bc_init() should also perform any initialization necessary for your code. The function should return 0 for success and -1 for failure.
• bc_add_block(): adds a new block to the blockchain. It should create a new block, set the fields of the block, and find the correct nonce that satisfies the hash condition. It should then add the block to the blockchain. It should return 0 for success and -1 for failure.
• bc_verify(): verifies the blockchain. It should check if the hash of each block is correct and matches the p_hash field of the next block. It should also check if the hash of each block satisfies the difficulty condition. It should return 0 for success and -1 for failure.

Implementation

• Nonce: you need to implement your own way of finding a correct nonce. You can use any method you like, but you need to find a nonce that satisfies the hash condition.
• SHA256: you need to use the OpenSSL libcrypto library to generate a SHA256 hash. OpenSSL's man page for ossl-guide-libcrypto-introduction provides a good introduction to how to use the library. You can refer to the section Using Algorithms in Action, or their wiki page on message digests to see examples of calling SHA256 hash functions.
• You need to link your code against libcrypto as well.
• You need to link against a shared library under lib/ that the test cases use, which is platform-dependent. You need to use the appropriate one for your platform.
  • For Intel machines, use libcheck-amd64.so.
  • For ARM machines, use libcheck-arm64.so.

Requirements

• You need to use the same code structure as previous assignments with src/ and include/.

• You should not change the provided code and files as we will replace it for our grading. This is unless the description above says otherwise. This can easily result in a 0 for the assignment. Be very careful about this. You can add your own code/files as needed.

• You also need to write CMakeLists.txt that produces one executable, blockchain. The executable should run the main function in src/main.c. Be very careful about file names and capitalization. If they are not exactly what we expect, it will result in a 0.

• When you open a source file, you might see an error saying that a header file is not found. If that's the case, generate a compile_commands.json file by adding the following line to your CMakeLists.txt and running cmake.

  set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

• You should not hard-code or customize your implementation tailored to our test cases. Generally, you should consider the provided test cases as examples or specific instances of general cases.

Grading

• Our base grading does not use the debug option or sanitizers. Therefore, your code should function correctly without them.
• [40 pts] Blockchain with no difficulty
  • [20 pts] bc_add_block() successfully adds one block (the first block).
  • [20 pts] bc_add_block() successfully adds multiple blocks.
• [60 pts] Blockchain with a difficulty
  • [20 pts] bc_add_block() successfully adds one block (the first block).
  • [20 pts] bc_add_block() successfully adds multiple blocks.
  • [20 pts] bc_verify() successfully verifies the blockchain.
• Occasionally, and especially before you submit, make sure that you run the minimum checker, which is already installed in your Docker container (minimum_checker). Please don't forget to run it from the top directory. As with previous assignments, it performs basic checks (e.g., .record, .nvim, copy-and-paste, etc.). If this does not pass, you will receive a 0.
• Code that does not compile with CMake gets a 0.
• Code that does not generate all the required executables gets a 0.
• Memory issues have a penalty of -10 pts. Use appropriate sanitizers and enable the debug option. Make sure your code works without the debug option as well. Before you submit, make sure that you remove the debug option.
• A wrong code directory structure has a penalty of -10 pts.
• Thread/synchronization issues have a penalty of -10 pts.