Blockchain
May 29, 2018
We represent a block as a four-slot vector:
(define (index block) (vector-ref block 0)) (define (datum block) (vector-ref block 1)) (define (phash block) (vector-ref block 2)) (define (chash block) (vector-ref block 3))
The Pearson hash is computed by concatenating the index, datum and phash elements of a block, converting to strings as necessary:
(define (hash index datum phash) (pearson8 (string-append (number->string index) datum (number->string phash))))
We use the 8-bit version of the Pearson hash, but you could use the 16-bit version if you prefer. The genesis block has index 0, datum “Genesis Block”, and previous hash 0:
(define genesis (vector 0 "Genesis Block" 0 (hash 0 "Genesis Block" 0)))
Now it is easy to add a new block to a blockchain:
(define (adjoin chain datum)
(let ((index (+ (index (car chain)) 1)) (phash (chash (car chain))))
(cons (vector index datum phash (hash index datum phash)) chain)))
Validating a blockchain is a little bit more work, because we have to visit every block in the chain:
(define (validate? chain)
(define (valid? curr prev)
(and (= (index curr) (+ (index prev) 1))
(= (phash curr) (chash prev))
(= (hash (index curr) (datum curr) (phash curr)) (chash curr))))
(if (null? (cdr chain)) (equal? (car chain) genesis)
(and (valid? (car chain) (cadr chain)) (validate? (cdr chain)))))
And that’s it: blockchain in seventeen lines of code, not counting four lines from the previous exercise. Here is an example blockchain based on the titles of the five most recent exercises in this blog:
> (define b (list genesis)) > (set! b (adjoin b "Pearson Hashing")) > (set! b (adjoin b "Floyd's Triangle")) > (set! b (adjoin b "Billing Period")) > (set! b (adjoin b "Sum Embedded Numbers")) > (set! b (adjoin b "Help Wanted: Report Generator")) > (validate? b) #t > b (#(5 "Help Wanted: Report Generator" 192 216) #(4 "Sum Embedded Numbers" 70 192) #(3 "Billing Period" 59 70) #(2 "Floyd's Triangle" 106 59) #(1 "Pearson Hashing" 108 106) #(0 "Genesis Block" 0 108)) > (set! b (cons (car b) (cddr b))) > (validate? b) #f > b (#(5 "Help Wanted: Report Generator" 192 216) #(3 "Billing Period" 59 70) #(2 "Floyd's Triangle" 106 59) #(1 "Pearson Hashing" 108 106) #(0 "Genesis Block" 0 108))
The blockchain used by Bitcoin and other cryptocurrencies is only a little bit more complicated than this. It uses a proper hashing function, of course, it adds a timestamp to the block, and it includes a provision for merging chains when more than one person adds a block at the same time. The data is a series of accounting transactions — John Smith pays 3.7 bitcoin to Programming Praxis in exchange for programming services — and hundreds or thousands of accounting transactions are aggregated in each datum; the idea is that anyone can run back through the chain and determine who has how many bitcoin. There is also a proof of work that makes it costly (in terms of computer time) to add a transaction; thus, “miners” do the work of aggregating transactions and adding them to the blockchain, in exchange for micropayments of bitcoin deducted from each transaction they aggregate. But at its heart, Bitcoin is little more that what we have done here.
You can run the program at https://ideone.com/GozM0B.
[…] 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; }