Blockchain
May 29, 2018
In the previous exercise we studied a simple cryptographic hash. Today we will use that hash to write an equally-simple blockchain, which is the algorithm underneath Bitcoin and other cryptocurrencies.
A blockchain is a publicly-readable database in which data items are stored in blocks in an immutable, verifiable chain. The database admits two operations: adjoin, to add a new data item to the database, and validate, to verify that the database is complete and incorrupt. There is no delete operation; once a datum is added to the database, it can never be removed. There is no update operation; once a datum is added to the database, it can never be modified. And there is no sort operation; once a datum is added to the database, it can never be moved within the chain.
In our implementation, each block in the chain contains four fields: an index number, which starts from zero and is incremented each time a new datum is added; a datum, which can be anything (for simplicity, we restrict the data to strings); the previous hash number, and the current hash number, which we will discuss below.
The adjoin operation takes a blockchain and a datum and returns a new blockchain, which is a linked list of blocks; the first block in a blockchain has index 0, datum “Genesis Block”, and previous hash number 0. The current hash number is a Pearson hash of the concatenated block number, the datum, and the previous hash number. To adjoin a new block, compute the current hash number, allocate a block, attach it to the head of the blockchain, and return the new blockchain.
The validate operation recalculates the current hash number at each block in the chain. If any is incorrect, it halts and reports the blockchain is corrupt. Otherwise, if it reaches the genesis block without finding an error, it reports the blockchain is valid.
Your task is to write a program that implements the simple blockchain described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] Blockchain […]
Here’s a solution in C using an XOR-based Pearson hashing (with the same table from the corresponding paper).
#include <stdarg.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> typedef struct node { size_t idx; char* datum; uint8_t phash; // previous hash uint8_t chash; // current hash struct node* next; } node_t; int asprintf(char** strp, const char* format, ...) { va_list args; va_start(args, format); size_t chars = vsnprintf(NULL, 0, format, args); va_end(args); // Add 1 to include the terminating null byte. ++chars; *strp = malloc(sizeof(char) * chars); va_start(args, format); int output = vsnprintf(*strp, chars, format, args); va_end(args); return output; } uint8_t hash(size_t idx, char* datum, uint8_t phash) { static uint8_t T[] = { 1,87,49,12,176,178,102,166,121,193,6,84,249,230,44,163, 14,197,213,181,161,85,218,80,64,239,24,226,236,142,38,200, 110,177,104,103,141,253,255,50,77,101,81,18,45,96,31,222, 25,107,190,70,86,237,240,34,72,242,20,214,244,227,149,235, 97,234,57,22,60,250,82,175,208,5,127,199,111,62,135,248, 174,169,211,58,66,154,106,195,245,171,17,187,182,179,0,243, 132,56,148,75,128,133,158,100,130,126,91,13,153,246,216,219, 119,68,223,78,83,88,201,99,122,11,92,32,136,114,52,10, 138,30,48,183,156,35,61,26,143,74,251,94,129,162,63,152, 170,7,115,167,241,206,3,150,55,59,151,220,90,53,23,131, 125,173,15,238,79,95,89,16,105,137,225,224,217,160,37,123, 118,73,2,157,46,116,9,145,134,228,207,212,202,215,69,229, 27,188,67,124,168,252,42,4,29,108,21,247,19,205,39,203, 233,40,186,147,198,192,155,33,164,191,98,204,165,180,117,76, 140,36,210,172,41,54,159,8,185,232,113,196,231,47,146,120, 51,65,28,144,254,221,93,189,194,139,112,43,71,109,184,209 }; uint8_t h = 0; char* idx_str; asprintf(&idx_str, "%zu", idx); while (*idx_str) { h = T[h ^ (uint8_t)*idx_str]; ++idx_str; } free(idx_str); while (*datum) { h = T[h ^ (uint8_t)*datum]; ++datum; } char* phash_str; asprintf(&phash_str, "%zu", phash); while (*phash_str) { h = T[h ^ (uint8_t)*phash_str]; ++phash_str; } return h; } node_t* adjoin(node_t* blockchain, char* datum) { node_t* node = (node_t*)malloc(sizeof(node_t)); node->datum = datum; if (blockchain == NULL) { node->idx = 0; node->next = NULL; node->phash = 0; } else { node->idx = blockchain->idx + 1; node->next = blockchain; node->phash = blockchain->chash; } node->chash = hash(node->idx, datum, node->phash); return node; } bool validate(node_t* blockchain) { while (blockchain != NULL) { uint8_t chash = hash(blockchain->idx, blockchain->datum, blockchain->phash); if (chash != blockchain->chash) return false; blockchain = blockchain->next; } return true; } void print(node_t* blockchain) { while (blockchain != NULL) { printf("%zu \"%s\" %u %u\n", blockchain->idx, blockchain->datum, blockchain->phash, blockchain->chash); blockchain = blockchain->next; } } int main(void) { node_t* blockchain = NULL; blockchain = adjoin(blockchain, "Genesis Block"); blockchain = adjoin(blockchain, "Pearson Hashing"); blockchain = adjoin(blockchain, "Floyd's Triangle"); blockchain = adjoin(blockchain, "Billing Period"); blockchain = adjoin(blockchain, "Sum Embedded Numbers"); blockchain = adjoin(blockchain, "Help Wanted: Report Generator"); printf("Valid: %d\n", validate(blockchain)); print(blockchain); while (blockchain != NULL) { node_t* next = blockchain->next; free(blockchain); blockchain = next; } return EXIT_SUCCESS; }Output:
Here’s an updated hash function that fixes a memory leak (phash_str is now free’d).
uint8_t hash(size_t idx, char* datum, uint8_t phash) { static uint8_t T[] = { 1,87,49,12,176,178,102,166,121,193,6,84,249,230,44,163, 14,197,213,181,161,85,218,80,64,239,24,226,236,142,38,200, 110,177,104,103,141,253,255,50,77,101,81,18,45,96,31,222, 25,107,190,70,86,237,240,34,72,242,20,214,244,227,149,235, 97,234,57,22,60,250,82,175,208,5,127,199,111,62,135,248, 174,169,211,58,66,154,106,195,245,171,17,187,182,179,0,243, 132,56,148,75,128,133,158,100,130,126,91,13,153,246,216,219, 119,68,223,78,83,88,201,99,122,11,92,32,136,114,52,10, 138,30,48,183,156,35,61,26,143,74,251,94,129,162,63,152, 170,7,115,167,241,206,3,150,55,59,151,220,90,53,23,131, 125,173,15,238,79,95,89,16,105,137,225,224,217,160,37,123, 118,73,2,157,46,116,9,145,134,228,207,212,202,215,69,229, 27,188,67,124,168,252,42,4,29,108,21,247,19,205,39,203, 233,40,186,147,198,192,155,33,164,191,98,204,165,180,117,76, 140,36,210,172,41,54,159,8,185,232,113,196,231,47,146,120, 51,65,28,144,254,221,93,189,194,139,112,43,71,109,184,209 }; uint8_t h = 0; char* idx_str; asprintf(&idx_str, "%zu", idx); while (*idx_str) { h = T[h ^ (uint8_t)*idx_str]; ++idx_str; } free(idx_str); while (*datum) { h = T[h ^ (uint8_t)*datum]; ++datum; } char* phash_str; asprintf(&phash_str, "%zu", phash); while (*phash_str) { h = T[h ^ (uint8_t)*phash_str]; ++phash_str; } free(phash_str); return h; }