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.




--
-- demo\rosetta\bitcoin_address_validation.exw
-- ===========================================
--
with javascript_semantics
include builtins\sha256.e

constant b58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
string charmap = ""

function valid(string s, bool expected)
    bool res := (expected==false)
    if charmap="" then
        charmap = repeat('\0',256)
        for i=1 to length(b58) do
            charmap[b58[i]] = i
        end for
    end if
-- not at all sure about this:
--  if length(s)!=34 then
--      return {expected==false,"bad length"}
--  end if
    if not find(s[1],"13") then
        return {res,"first character is not 1 or 3"}
    end if
    string out = repeat('\0',25)
    for i=1 to length(s) do
        integer c = charmap[s[i]]
        if c=0 then 
            return {res,"bad char"}
        end if
        c -= 1
        for j=25 to 1 by -1 do
            c += 58 * out[j];
            out[j] = and_bits(c,#FF)
            c = floor(c/#100)
        end for
        if c!=0 then
            return {res,"address too long"}
        end if
    end for
    if out[1]!='\0' then
        return {res,"not version 0"}
    end if
    if out[22..$]!=sha256(sha256(out[1..21]))[1..4] then
        return {res,"bad digest"}
    end if
    res := (expected==true)
    return {res,"OK"}
end function
 
constant tests = {{"1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9",true},  -- OK
                  {"1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nJ9",false}, -- bad digest
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i",true},  -- OK
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62j",false}, -- bad disgest
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62X",false}, -- bad digest (checksum changed, original data.)
                  {"1ANNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i",false}, -- bad digest (data changed, original checksum.)
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62iz",false}, -- not version 0
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62izz",false}, -- address too long
                  {"1BGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i",false}, -- bad digest
                  {"1A Na15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i",false}, -- bad char
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62I",false}, -- bad char
                  {"1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62!",false}, -- bad char
                  {"1AGNa15ZQXAZUgFiqJ3i7Z2DPU2J6hW62i",false}, -- bad digest
                  {"1111111111111111111114oLvT2",       true},  -- OK
                  {"17NdbrSGoUotzeGCcMMCqnFkEvLymoou9j",true},  -- OK
                  {"1badbadbadbadbadbadbadbadbadbadbad",false}, -- not version 0
                  {"BZbvjr",false}, -- first character is not 1 or 3 (checksum is fine, address too short)
                  {"i55j",false}, -- first character is not 1 or 3 (checksum is fine, address too short)
                  {"16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM", true},  -- OK (from public_point_to_address)
                 $}

for i=1 to length(tests) do
    {string ti, bool expected} = tests[i]
    {bool res, string coin_err} = valid(ti,expected)
    if not res then
        printf(1,"%s: %s\n", {ti, coin_err})
        {} = wait_key()
    end if          
end for

?"done"
{} = wait_key()
