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.




with Ada.Exceptions, Interfaces;
with Ada.Streams;
use Ada.Exceptions, Interfaces;
use Ada.Streams;
 
package Bitcoin is
    subtype BT_Raw_Addr is Stream_Element_Array(1..25);
    subtype BT_Checksum is Stream_Element_Array(1..4);
    subtype BT_Addr is String(1..34);
    subtype Sha256String is String(1..64);
    Invalid_Address_Error : Exception;
 
    function Double_Sha256(S : Stream_Element_Array) return BT_Checksum;
    function Is_Valid(A : BT_Raw_Addr) return Boolean;
    procedure Base58_Decode(S : BT_Addr; A : out BT_Raw_Addr) ;
private
    Base58 : constant String := "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
    function Hex_Val (C, C2 : Character) return Stream_Element;
end Bitcoin;
 
 
with GNAT.SHA256, Ada.Strings.Fixed;
use  GNAT.SHA256, Ada.Strings.Fixed;
 
package body Bitcoin is
 
function Hex_Val (C, C2 : Character) return Stream_Element is
    subtype Nibble is Integer range 0..15;
    HEX : array (0..255) of Nibble := (
          48=>0, 49=>1, 50=>2, 51=>3, 52=>4, 53=>5, 54=>6, 55=>7, 56=>8, 57=>9
        , 65=>10, 66=>11, 67=>12, 68 =>13, 69 =>14, 70 =>15
        , 97=>10, 98=>11, 99=>12, 100=>13, 101=>14, 102=>15
        , Others=>0
    );
begin
    return Stream_Element(HEX(Character'Pos(C)) * 16 + HEX(Character'Pos(C2)));
end Hex_Val;
 
function Double_Sha256(S : Stream_Element_Array) return BT_Checksum is
    Ctx  : Context := Initial_Context;
    D : Message_Digest;
    S2 : Stream_Element_Array(1..32);
    Ctx2 : Context := Initial_Context;
    C : BT_Checksum;
begin
    Update(Ctx, S);
    D := Digest(Ctx);
    for I in S2'Range loop
        S2(I) := Hex_Val(D(Integer(I)*2-1), D(Integer(I)*2));
    end loop;
    Update(Ctx2, S2);
    D := Digest(Ctx2);
    for I in C'Range loop
        C(I) := Hex_Val(D(Integer(I)*2-1), D(Integer(I)*2));
    end loop;
    return C;
 
end Double_Sha256;
 
 
--------------------------------------------------------------------------------
-- Summary of Base58:                                                         --
-- We decode S into a 200 bit unsigned integer.                               --
-- We could use a BigNum library, but choose to go without.                   --
--------------------------------------------------------------------------------
procedure Base58_Decode(S : BT_Addr; A : out BT_Raw_Addr) is
begin
    A := (Others => 0);
    for I in S'Range loop
        declare
            P : Natural := Index(Base58, String(S(I..I)));
            C : Natural;
        begin
            if P = 0 then
                raise Invalid_Address_Error;
            end if;
            C := P - 1;
            for J in reverse A'Range loop
                C    := C + Natural(A(J)) * 58;
                A(J) := Stream_Element(Unsigned_32(C) and 255);         -- 0x00FF
                C    := Natural(Shift_Right(Unsigned_32(C),8) and 255); -- 0xFF00
            end loop;
            if C /= 0 then
                raise Invalid_Address_Error;
            end if;
        end;
    end loop;
end Base58_Decode;
 
 
function Is_Valid(A : BT_Raw_Addr) return Boolean is
begin
    return A(1) = 0 and A(22..25) = Double_Sha256(A(1..21));
end Is_Valid;
 
 
end Bitcoin;
 
with Ada.Text_IO, Bitcoin;
use Ada.Text_IO, Bitcoin;
 
procedure Bitcoin_Addr_Validate is
begin
    declare
        BTs : array (positive range <>) of BT_Addr := (
              "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"  -- VALID
            , "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9"  -- VALID
            , "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62X"  -- checksum changed, original data.
            , "1ANNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"  -- data changed, original checksum.
            , "1A Na15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"  -- invalid chars
        );
    begin
        for I in Bts'Range loop
            declare
                A : BT_Raw_Addr;
                Valid : Boolean;
            begin
                Put(BTs(I) & " validity: ");
                Base58_Decode(BTs(I), A);
                Valid := Is_Valid(A);
                Put_Line(Boolean'Image(Valid));
            exception
                when E : Invalid_Address_Error  =>
                    Put_Line ("*** Error: Invalid BT address.");
            end;
        end loop;
    end;
end Bitcoin_Addr_Validate;
 