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.




import           Control.Monad      (when)
import           Data.List          (elemIndex)
import           Data.Monoid        ((<>))
import qualified Data.ByteString    as BS
import           Data.ByteString    (ByteString)
 
import           Crypto.Hash.SHA256 (hash)  -- from package cryptohash
 
-- Convert from base58 encoded value to Integer
decode58 :: String -> Maybe Integer
decode58 = fmap combine . traverse parseDigit
  where
    combine = foldl (\acc digit -> 58 * acc + digit) 0  -- should be foldl', but this trips up the highlighting
    parseDigit char = toInteger <$> elemIndex char c58
    c58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
 
-- Convert from base58 encoded value to bytes
toBytes :: Integer -> ByteString
toBytes = BS.reverse . BS.pack . map (fromIntegral . (`mod` 256)) . takeWhile (> 0) . iterate (`div` 256)
 
-- Check if the hash of the first 21 (padded) bytes matches the last 4 bytes
checksumValid :: ByteString -> Bool
checksumValid address =
  let (value, checksum) = BS.splitAt 21 $ leftPad address
  in and $ BS.zipWith (==) checksum $ hash $ hash $ value
  where
    leftPad bs = BS.replicate (25 - BS.length bs) 0 <> bs
 
-- utility
withError :: e -> Maybe a -> Either e a
withError e = maybe (Left e) Right
 
-- Check validity of base58 encoded bitcoin address.
-- Result is either an error string (Left) or unit (Right ()).
validityCheck :: String -> Either String ()
validityCheck encoded = do
  num <- withError "Invalid base 58 encoding" $ decode58 encoded
  let address = toBytes num
  when (BS.length address > 25) $ Left "Address length exceeds 25 bytes"
  when (BS.length address <  4) $ Left "Address length less than 4 bytes"
  when (not $ checksumValid address) $ Left "Invalid checksum"
 
-- Run one validity check and display results.
validate :: String -> IO ()
validate encodedAddress = do
  let result = either show (const "Valid") $ validityCheck encodedAddress
  putStrLn $ show encodedAddress ++ " -> " ++ result
 
-- Run some validity check tests.
main :: IO ()
main  = do
  validate "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"     -- VALID
  validate "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9"     -- VALID
  validate "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62X"     -- checksum changed, original data.
  validate "1ANNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"     -- data changed, original checksum.
  validate "1A Na15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"     -- invalid chars
  validate "1ANa55215ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"   -- too long
  validate "i55j"                                   -- too short 
 