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.




package require sha256
 
# Generate a large and boring piece of code to do the decoding of
# 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
	set count [expr {ceil(log(58**[string length $str])/log(256))}]
	foreach c [split $str {}] {
	    set num [expr {$num*58+[switch $c @BODY@]}]
	}
	for {set i 0} {$i < $count} {incr i} {
	    append result [binary format c [expr {$num & 255}]]
	    set num [expr {$num >> 8}]
	}
	return [string reverse $result]
    }]
}}
 
# 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 "$address is ok"
}