Bitcoin/address validation

Bitcoin/address validation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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>

Tcl

Library: Tcllib (Package: sha256)

<lang tcl>package require sha256

1. Generate a large and boring piece of code to do the decoding of
2. base58-encoded data.

apply {{} {

   set chars "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
   set i -1
   foreach c [split $chars ""] {

lappend map $c "return -level 0 [incr i]"

   }
   lappend map default {return -code error "bad character \"$c\""}
   proc base58decode str [string map [list @BODY@ [list $map]] {

set num 0 foreach c [split $str {}] { set num [expr {$num*58+[switch $c @BODY@]}] } for {set i 0} {$i < 25} {incr i} { append result [binary format c [expr {$num & 255}]] set num [expr {$num >> 8}] } return [string reverse $result]

   }]

}}

1. How to check bitcoin address validity

proc bitcoin_addressValid {address} {

   set a [base58decode $address]
   set ck [sha2::sha256 -bin [sha2::sha256 -bin [string range $a 0 end-4]]]
   if {[string range $a end-3 end] ne [string range $ck 0 3]} {

return -code error "signature does not match"

   }
   return "ok"

}</lang> Testing if it works <lang tcl>puts [bitcoin_addressValid 1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9]</lang>

Output:

ok

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>