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.




using SHA
 
bytes(n::Integer, l::Int) = collect(UInt8, (n >> 8i) & 0xFF for i in l-1:-1:0)
 
function decodebase58(bc::String, l::Int)
    digits = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    num = big(0)
    for c in bc
        num = num * 58 + search(digits, c) - 1
    end
    return bytes(num, l)
end
 
function checkbcaddress(addr::String)
    if !(25 ≤ length(addr) ≤ 35) return false end
    bcbytes = decodebase58(addr, 25)
    sha = sha256(sha256(bcbytes[1:end-4]))
    return bcbytes[end-3:end] == sha[1:4]
end
 
const addresses = Dict(
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i" => true,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62j" => false,
    "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9" => true,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62X" => true,
    "1ANNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i" => false,
    "1A Na15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i" => false,
    "BZbvjr" => false,
    "i55j" => false,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62!" => false,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62iz" => false,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62izz" => false,
    "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nJ9" => false,
    "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62I" => false)
 
for (addr, corr) in addresses
    println("Address: $addr\nExpected: $corr\tChecked: ", checkbcaddress(addr))
end