[hashcash] Sample code for Dworkian memory-bound POW
- From: Anonymous <cripto@xxxxxxx>
- To: hashcash@xxxxxxxxxxxxx, camram-spam@xxxxxxxxxx
- Date: Mon, 24 May 2004 10:56:45 +0200 (CEST)
/* 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;
}
Other related posts:
