# 9.8. Extended Example: Blockchain Proof-of-Work¶

A blockchain is a sequence of messages that create a verifiable ordering of events. Blockchains can be used in a variety of applications, such as cryptocurrency (Bitcoin) or other distributed database ledgers. One key idea behind a blockchain is that new entries are difficult to generate. A common technique is to require a proof-of-work calculation, such as finding a string that produces a cryptographic hash value with several leading 0s.

Consider the example output below. Each line contains a message index (0, 1, 2, …) followed by the previous line’s hash value (0000..., f74d..., and so on), a timestamp (omitted for brevity), then a log message (“Genesis Block”). The line then ends with an integer value (called a nonce), such as 0000, 22d75, and 6ea as shown. The entire line ending at the nonce is then used as input to a cryptographic hash function. If the output of the hash does not begin with 0s, the nonce is increased and the line is re-hashed. For instance, the second line required 142,709 (0x22d75) attempts before the hash output began with 0s. Once this entry is found, it can be added to the blockchain.

 1 2 3 4 5 6 7 8 \$ ./blockchain Here is the blockchain: ...0 00000000... [...] Genesis Block ...000000 f74d3a10... ...1 f74d3a10... [...] Data message 1 ...022d75 0000b38b... ...2 0000b38b... [...] Data message 2 ...0006ea 0000e2c4... ...3 0000e2c4... [...] Data message 3 ...00be80 00002c45... ...4 00002c45... [...] Data message 4 ...019e63 0000a65e... ...5 0000a65e... [...] Data message 5 ...0188a8 0000cb6f... 

The second field in each line is the previous line’s hash output, which serves the purpose of declaring that the new line is the only legitimate successor of the previous line. That is, each line explicitly ties itself to the previous line by including the previous line’s hash in the input. Note that the first line, often called a Genesis block, is special, as it does not follow any entry. As such, a nonce of 0 is often used for this value and the hash value does not need to begin with 0s. In this extended example, we use SHA-1 as a cryptographic hash function simply to make the search more efficient. In practice, SHA-1 is considered insecure and should not be use for applications like this.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 #include #include #include #include #include #include #include #include #include #include #define ASCTIME_LENGTH 24 #define BLOCKCHAIN_ZEROES 3 char * construct_block (uint64_t, char *, struct tm *, char *, size_t, uint64_t, size_t *); char * create_genesis_block (void); char * hash_to_string (uint8_t *hash); char * append_block (char *, char *, size_t); int main (void) { size_t number_of_threads = 4; size_t number_of_blocks = 10; /* Generate the blockchain pointers and create genesis block */ char *blockchain[number_of_blocks]; memset (blockchain, 0, sizeof (blockchain)); blockchain[0] = create_genesis_block (); /* Use a generic message to append each time */ char *message = calloc (50, sizeof (char)); size_t i; for (i = 1; i < number_of_blocks; i++) { strncpy (message, "Data message ", 50); snprintf (message + strlen (message), 50 - strlen (message), "%zd", i); blockchain[i] = append_block (message, blockchain[i-1], number_of_threads); } free (message); /* Print the results of the computations */ printf ("Here is the blockchain:\n"); for (i = 0; i < number_of_blocks; i++) { printf (" %s\n", blockchain[i]); free (blockchain[i]); } return EXIT_SUCCESS; } /* Parameters for each copy of the mining thread */ struct mining_params { char *block; size_t blocklen; uint64_t nonce; size_t attempts; bool success; }; /* Blockchain mining thread. Each instance of this thread starts with a block string to work with. The string contains a nonce that is iteratively incremented until the string hashes to the correct structure (leading zeroes) or the thread runs out of attempts. */ void * mining_thread (void * _params) { struct mining_params *params = (struct mining_params *) _params; char *block = params->block; char *nonce_loc = block + strlen (block) - 16; size_t count = 0; uint8_t hash[SHA_DIGEST_LENGTH]; while (count < params->attempts) { /* Update nonce in the string and re-calculate the hash */ snprintf (nonce_loc, 17, "%016" PRIx64, params->nonce++); memset (hash, 0, SHA_DIGEST_LENGTH); unsigned char *md = SHA1 ((unsigned char *)block, (unsigned long) params->blocklen, hash); /* Check to see if the hash begins with the desired number of leading zeroes */ bool zeroes = true; int i = 0; for (i = 0; i < BLOCKCHAIN_ZEROES; i++) if (md[i] != 0) zeroes = false; /* If the leading zeroes match, update the block and exit */ if (zeroes) { char *hash_str = hash_to_string (md); block[strlen (block)] = ' '; strncat (block, hash_str, SHA_DIGEST_LENGTH * 2); free (hash_str); params->success = true; pthread_exit (NULL); } count++; } pthread_exit (NULL); } /* Create a block to append to the end of the chain. Can be parallelized for improved performance, but blockchain calculations are designed to be slow. */ char * append_block (char *data, char *previous, size_t num_threads) { uint64_t index = (uint64_t) strtoul ((char *)previous, NULL, 16); char *prev_hash = calloc (SHA_DIGEST_LENGTH * 2 + 1, sizeof (char)); strncpy (prev_hash, (char *)&previous[strlen ((char *)previous) - SHA_DIGEST_LENGTH * 2], SHA_DIGEST_LENGTH * 2); /* Last block was validated, now construct a new block */ time_t now = time (NULL); size_t blocklen = 0; char *block = construct_block (index + 1, prev_hash, localtime (&now), data, strlen (data), 0, &blocklen); free (prev_hash); /* Repeatedly implement a fork/join pattern until the search is successful. Each time through the while-loop, create a fixed number of threads that will perform a maximum number of calculations with different nonces. For instance, using 1,000,000 attempts per thread, the first thread will use nonces 0 through 999,999, the second 1,000,000 through 1,999,999, and so forth. Once all threads have run, check to see if any were successful. If not, create a new set of threads that continue with the next group of possible nonces. */ size_t attempts_per_thread = 1000000; uint64_t nonce = 0; bool success = false; while (! success) { struct mining_params params[num_threads]; pthread_t thread[num_threads]; int i; for (i = 0; i < num_threads; i++) { /* Each thread needs its own copy of the block, so that it can change the nonce portion of the string. Note that we cannot just use strdup() here, because that would not allocate the additional bytes needed to append the hash for the successul search. */ params[i].block = calloc (blocklen + 2 + 2 * SHA_DIGEST_LENGTH, sizeof (char)); strncpy (params[i].block, block, blocklen); params[i].blocklen = blocklen; params[i].nonce = nonce; params[i].attempts = attempts_per_thread; params[i].success = false; pthread_create (&thread[i], NULL, mining_thread, ¶ms[i]); /* The starting nonce for each thread is repeatedly incremented to ensure no two threads search the same set of values */ nonce += attempts_per_thread; } /* For this group of threads, check to see if any were successful. If so, replace the generated block string with that thread's copy. */ for (i = 0; i < num_threads; i++) { pthread_join (thread[i], NULL); if (params[i].success && !success) { free (block); block = params[i].block; success = true; } else free (params[i].block); } } return block; } /* Create a genesis block to serve as the foundation */ char * create_genesis_block (void) { /* Start off with a bogus 0 hash */ uint8_t hash[SHA_DIGEST_LENGTH]; memset (hash, 0, SHA_DIGEST_LENGTH); char *hash_str = hash_to_string (hash); /* Create a genesis block with the current time */ time_t now = time (NULL); size_t blocklen = 0; char *genesis = construct_block (0, (char*) hash_str, localtime (&now), "Genesis Block", 13, 0, &blocklen); free (hash_str); /* Compute the hash of the genesis block and append it */ unsigned char *md = SHA1 ((unsigned char *)genesis, (unsigned long) blocklen, hash); hash_str = hash_to_string (md); genesis[strlen ((char *)genesis)] = ' '; strncat ((char *)genesis, hash_str, SHA_DIGEST_LENGTH * 2); free (hash_str); return genesis; } /* Constrct a block of the following form: index.previous hash.[timestamp].data.nonce (Dots denote spaces for readability of the line.) Note that the dynamic allocation also includes space for this block's hash at the end, but those bytes are initialized to all 0. */ char * construct_block (uint64_t index, char *previous, struct tm *timestamp, char *data, size_t length, uint64_t nonce, size_t *block_length) { *block_length = 16 + 16 + length + 4 + // index, nonce, length, spaces SHA_DIGEST_LENGTH * 2 + // previous hash ASCTIME_LENGTH + 2; // [ASCII timestamp] /* Allocate extra space for the block's hash, as well */ char *block = calloc (*block_length + 2 + SHA_DIGEST_LENGTH * 2, sizeof (char)); /* Both the index and the nonce are padded with leading 0s to be fixed width */ snprintf (block, 17, "%016" PRIx64, index); block[16] = ' '; strncat (block, previous, SHA_DIGEST_LENGTH * 2); /* For the [timestamp] the asctime returns a trailing '\n' that must be overwritten with the ']' */ block[SHA_DIGEST_LENGTH * 2 + 17] = ' '; block[SHA_DIGEST_LENGTH * 2 + 18] = '['; strncat (block, asctime (timestamp), *block_length - strlen (block)); block[strlen (block) - 1] = ']'; /* For readability of data, add a space before and after */ block[strlen (block)] = ' '; strncat (block, data, length); block[*block_length - 17] = ' '; snprintf (block + *block_length - 16, 17, "%016" PRIx64, nonce); return block; } /* Convert a SHA hash to a readable hex string */ char * hash_to_string (uint8_t *hash) { size_t j; char *str = calloc (SHA_DIGEST_LENGTH * 2 + 1, sizeof (char)); /* Each byte gets split into two hex digits */ for (j = 0; j < SHA_DIGEST_LENGTH; j++) sprintf (&str[j*2], "%02x", hash[j]); return str; }