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

#include <assert.h>
#include <inttypes.h>
#include <openssl/sha.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#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, &params[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;
}