Bitcoin/address validation

Write a program that takes a bitcoin address as argument, and checks whether or not this address is valid. The program can either return a boolean value or throw an exception when not 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 encoded, a bitcoin address encodes a string 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 bytes, compute the checksum, and check that it corresponds to the last four bytes.

You can use a digest library for SHA-256.

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>