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>
Tcl
<lang tcl>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"
}</lang> Testing if it works <lang tcl>puts [bitcoin_addressValid 1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9] puts [bitcoin_addressValid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i]</lang>
- Output:
1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9 is ok 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i is 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>