Bitcoin/address validation

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, O, I and l.

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.

Here is an example of a bitcoin address:

1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i

It does not belong to anyone. It is part of the test suite of the bitcoin software. You can change a few characters in this string and check that it will fail the test.

extra credit: allow your code to deal with compressed keys

Perl

<lang perl>my @b58 = qw{

     1 2 3 4 5 6 7 8 9
   A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
   a b c d e f g h i j k   m n o p q r s t u v w x y z

}; my %b58 = map { $b58[$_] => $_ } 0 .. 57; my $b58 = qr/[@{[join , @b58]}]/x;

sub decode {

   use bigint;
   shift =~ m/$b58\Z/p ? $b58{${^MATCH}} + 58*decode(${^PREMATCH}) : 0

}

sub check_bitcoin_address {

   use Digest::SHA qw(sha256);
   my $value = decode shift;
   my @byte; for (1 .. 25) { push @byte, $value % 256; $value /= 256 }
   @byte = reverse @byte;
   die unless join(, map { chr } @byte[21..24]) eq
   substr sha256(sha256 pack 'C*', @byte[0..20]), 0, 4;

}</lang>

Unix shell

<lang bash>base58=({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z}) bitcoinregex="^[$(printf "%s" "${base58[@]}")]{34}$"

decodeBase58() {

   local s=$1
   for i in {0..57}
   do s="${s//${base58[i]}/ $i}"
   done
   dc <<< "16o0d${s// /+58*}+f"

}

checksum() {

   xxd -p -r <<<"$1" |
   openssl dgst -sha256 -binary |
   openssl dgst -sha256 -binary |
   xxd -p -c 80 |
   head -c 8

}

checkBitcoinAddress() {

   if "$1" =~ $bitcoinregex 
   then
       h=$(decodeBase58 "$1")
       checksum "00${h::${#h}-8}" |
       grep -qi "^${h: -8}$"
   else return 2
   fi

}</lang>