Bitcoin/address validation

You are encouraged to solve this task according to the task description, using any language you may know.


Task

Write a program that takes a bitcoin address as argument,
and checks whether or not this address is valid.

A bitcoin address uses a base58 encoding, which uses an alphabet of the characters 0 .. 9, A ..Z, a .. z, but without the four characters:

   0   zero
   O   uppercase oh
   I   uppercase eye
   l   lowercase ell


With this encoding, a bitcoin address encodes 25 bytes:

 the first byte is the version number, which will be zero for this task ;
 the next twenty bytes are a RIPEMD-160 digest, but you don't have to know that for this task: you can consider them a pure arbitrary data ;
 the last four bytes are a checksum check. They are the first four bytes of a double SHA-256 digest of the previous 21 bytes.


To check the bitcoin address, you must read the first twenty-one bytes, compute the checksum, and check that it corresponds to the last four bytes.

The program can either return a boolean value or throw an exception when not valid.

You can use a digest library for SHA-256.



Example of a bitcoin address



1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i



It doesn't belong to anyone and is part of the test suite of the bitcoin software.

You can change a few characters in this string and check that it'll fail the test.




#include <stdio.h>
#include <string.h>
#include <openssl/sha.h>
 
const char *coin_err;
#define bail(s) { coin_err = s; return 0; }
 
int unbase58(const char *s, unsigned char *out) {
	static const char *tmpl = "123456789"
		"ABCDEFGHJKLMNPQRSTUVWXYZ"
		"abcdefghijkmnopqrstuvwxyz";
	int i, j, c;
	const char *p;
 
	memset(out, 0, 25);
	for (i = 0; s[i]; i++) {
		if (!(p = strchr(tmpl, s[i])))
			bail("bad char");
 
		c = p - tmpl;
		for (j = 25; j--; ) {
			c += 58 * out[j];
			out[j] = c % 256;
			c /= 256;
		}
 
		if (c) bail("address too long");
	}
 
	return 1;
}
 
int valid(const char *s) {
	unsigned char dec[32], d1[SHA256_DIGEST_LENGTH], d2[SHA256_DIGEST_LENGTH];
 
	coin_err = "";
	if (!unbase58(s, dec)) return 0;
 
	SHA256(SHA256(dec, 21, d1), SHA256_DIGEST_LENGTH, d2);
 
	if (memcmp(dec + 21, d2, 4))
		bail("bad digest");
 
	return 1;
}
 
int main (void) {
	const char *s[] = {
		"1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9",
		"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i",
		"1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nJ9",
		"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62I",
		0 };
	int i;
	for (i = 0; s[i]; i++) {
		int status = valid(s[i]);
		printf("%s: %s\n", s[i], status ? "Ok" : coin_err);
	}
 
	return 0;
}