Sample code for Dworkian memory-bound POW

/* mempow.c
 *
 * Memory based proof of work
 * Based on Dwork, Goldberg and Naor, Crypto 03
 *
 * Note that mempow.dat used with this comes from the 1st two
 * 10 MB files from http://www.random.org/.
 * http://www.random.org/files/10megs.001
 * http://www.random.org/files/10megs.002
 * Concatenate them and then truncate to 16778240 (2^24 + 2^10) bytes.
 * md5sum: 283e22de6826cfbdaddfc1d2c21afada  mempow.dat
 */

#include <stdio.h>
#include "openssl/sha.h"

#define DATFILE		"mempow.dat"

/* T holds 2^22 entries */
#define TLEN 		(2048*2048)
#define ALEN 		256
#define HASHLEN		16
#define PREFIX		"MEMPOW"
#define PREFIXLEN	6
#define elemsof(x)	(sizeof(x)/sizeof((x)[0]))

/* This value of L, the chain length, is tuned for >= 14 zero bits */
#define L			2048

typedef unsigned char uchar;
typedef unsigned long ulong;

ulong T[TLEN];			/* Fixed */
ulong A0[ALEN];			/* Seed for A */
ulong A[ALEN];			/* Variable */
ulong A1[ALEN];			/* Network byte order version of A */

int verboseflag = 0;

/* Compute a hash chain value */
void
chain (uchar out[HASHLEN], uchar salt[HASHLEN], int k)
{
	uchar buf[PREFIXLEN + HASHLEN + 4];
	uchar md[SHA_DIGEST_LENGTH];
	ulong mdl[HASHLEN/4];
	int i, j, l, c;
	ulong tmp;

	/* Step 1: compute A */

	strcpy (buf, PREFIX);
	memcpy (buf+PREFIXLEN, salt, HASHLEN);
	buf[PREFIXLEN+HASHLEN]   = (uchar)(k >> 24);
	buf[PREFIXLEN+HASHLEN+1] = (uchar)(k >> 16);
	buf[PREFIXLEN+HASHLEN+2] = (uchar)(k >> 8);
	buf[PREFIXLEN+HASHLEN+3] = (uchar)(k);

	SHA1 (buf, sizeof(buf), md);

	for (i=0; i<HASHLEN/4; i++)
		mdl[i] = ntohl(((ulong *)md)[i]);
	for (i=0; i<sizeof(A); i+=HASHLEN)
		memcpy (A + i/sizeof(A[0]), mdl, HASHLEN);
	for (i=0; i<elemsof(A); i++)
		A[i] ^= A0[i];

	/* Step 2: iterate l steps */

	c = A[ALEN-1];
	i = 0;
	j = 0;

	for (l=0; l<L; l++)
	{
		c &= 0x3fffff;
		i = (i+1) % ALEN;
		j = (j + A[i]) % ALEN;
		A[i] = A[i] + T[c];
		A[i] = (A[i] << 21) | (A[i] >> 11);
		tmp = A[i]; A[i] = A[j]; A[j] = tmp;
		c = T[c] ^ A[(A[i] + A[j])%ALEN];
	}

	/* Step 3: return HASHLEN bytes of hash of A */

	/* A1 is a copy of A with its bytes in network order. */
	for (i=0; i<elemsof(A); i++)
		A1[i] = htonl(A[i]);
	SHA1 ((uchar *)A1, sizeof(A1), md);
	memcpy (out, md, HASHLEN);
}

/* Count the zero low order bits in a hash output buffer */
int
countbits (uchar *buf, int buflen)
{
	int ibuflen = buflen;
	int b;
	int nbits;

	/* Count low order 0 bits of buf */
	while (buflen--)
		if (buf[buflen] != 0)
			break;
	nbits = 8*(ibuflen-buflen-1);
	b = buf[buflen];
	while ((b&1) == 0)
	{
		b >>= 1;
		++nbits;
	}
	return nbits;
}


/* Search for a value of specified number of bits */
void
gen (uchar *salt, int nbits)
{
	int k = 0;
	uchar md[HASHLEN];
	int curbits;
	int maxbits = -1;

	RAND_bytes (salt, HASHLEN);
	for ( ; ; )
	{
		chain (md, salt, k);
		curbits = countbits(md, sizeof(md));
		if (verboseflag && (curbits > maxbits))
		{
			printf ("Max bits: %2d\n", curbits);
			maxbits = curbits;
		}
		if (curbits >= nbits)
			break;
		k += 1;
	}
	salt[HASHLEN]   = (uchar) (k>>24);
	salt[HASHLEN+1] = (uchar) (k>>16);
	salt[HASHLEN+2] = (uchar) (k>>8);
	salt[HASHLEN+3] = (uchar) (k);
}

/* Return the number of bits in a claimed collision value */
int
test (uchar salt[HASHLEN+4])
{
	uchar md[HASHLEN];
	int k;
	k = (salt[HASHLEN] << 24) | (salt[HASHLEN+1] << 16)
			| (salt[HASHLEN+2] << 8) | salt[HASHLEN+3];
	chain (md, salt, k);
	return countbits(md, sizeof(md));
}


int
main (int ac, char **av)
{
	int nbits;
	FILE *frand;
	int k;
	int dogen=0, dotest=0;
	uchar salt[HASHLEN + 4];
	int i;

	if (ac != 3 && ac != 4)
	{
		fprintf (stderr, "Usage: %s [-v] -g nbits\n"
				"\t-t kval\n", av[0]);
		exit (1);
	}

	if (strcmp (av[1], "-v") == 0)
	{
		verboseflag = 1;
		av[1] = av[2]; av[2] = av[3];
	}

	if (strcmp (av[1], "-g") == 0)
		dogen = 1;
	else if (strcmp (av[1], "-t") == 0)
		dotest = 1;
	else {
		fprintf (stderr, "Illegal option\n");
		exit (1);
	}

	if (dogen)
		nbits = atoi(av[2]);

	if ((frand = fopen (DATFILE, "rb")) == NULL)
	{
		fprintf (stderr, "Unable to open random data file %s\n", DATFILE);
		fprintf (stderr, "See the source code for how to construct this file\n");
		exit (1);
	}

	if (fread (T, 1, sizeof(T), frand) != sizeof(T)
		|| fread (A0, 1, sizeof(A0), frand) != sizeof(A0))

	{
		fprintf (stderr, "Unable to read sufficient data from DATFILE\n");
		fprintf (stderr, "See the source code for how to construct this file\n");
		exit (1);
	}
	fclose (frand);

	/* Correct for byte order on little endian machines */
	for (i=0; i<elemsof(T); i++)
		T[i] = ntohl(T[i]);
	for (i=0; i<elemsof(A0); i++)
		A0[i] = ntohl(A0[i]);

	if (dogen)
	{
		gen(salt, nbits);
		for (i=0; i<sizeof(salt); i++)
			printf ("%02x", salt[i]);
		printf ("\n");
	}

	if (dotest)
	{
		for (i=0; i<sizeof(salt); i++)
		{
			char c = av[2][2*i];
			unsigned u1 = (c >= 'a') ? (c - 'a' + 10) :
				(c >= 'A') ? (c - 'A' + 10) : (c - '0');
			unsigned u2;
			c = av[2][2*i+1];
			u2 = (c >= 'a') ? (c - 'a' + 10) :
				(c >= 'A') ? (c - 'A' + 10) : (c - '0');
			salt[i] = (u1<<4) | u2;
		}
		nbits = test(salt);
		printf ("nbits = %d\n", nbits);
	}
	return 0;
}