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.




 
#lang racket/base
 
;; Same sha-256 interface as the same-named task
(require ffi/unsafe ffi/unsafe/define openssl/libcrypto)
(define-ffi-definer defcrypto libcrypto)
(defcrypto SHA256_Init   (_fun _pointer -> _int))
(defcrypto SHA256_Update (_fun _pointer _pointer _long -> _int))
(defcrypto SHA256_Final  (_fun _pointer _pointer -> _int))
(define (sha256 bytes)
  (define ctx (malloc 128))
  (define result (make-bytes 32))
  (SHA256_Init ctx)
  (SHA256_Update ctx bytes (bytes-length bytes))
  (SHA256_Final result ctx)
  result)
 
;; base58 decoding
(define base58-digits
  (let ([v (make-vector 128 #f)])
    (for ([i (in-naturals)]
          [c "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"])
      (vector-set! v (char->integer c) i))
    v))
(define (base58->integer str)
  (for/fold ([n 0]) ([c str])
    (+ (* n 58) (vector-ref base58-digits (char->integer c)))))
 
(define (int->bytes n digits)
  (list->bytes (let loop ([n n] [digits digits] [acc '()])
                 (if (zero? digits) acc
                     (let-values ([(q r) (quotient/remainder n 256)])
                       (loop q (sub1 digits) (cons r acc)))))))
 
(define (validate-bitcoin-address str)
  (define bs (int->bytes (base58->integer str) 25))
  (equal? (subbytes (sha256 (sha256 (subbytes bs 0 21))) 0 4)
          (subbytes bs 21)))
 
;; additional tests taken from the other solutions
(validate-bitcoin-address "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i") ; => #t
(validate-bitcoin-address "1111111111111111111114oLvT2")        ; => #t
(validate-bitcoin-address "17NdbrSGoUotzeGCcMMCqnFkEvLymoou9j") ; => #t
(validate-bitcoin-address "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9") ; => #t
(validate-bitcoin-address "1badbadbadbadbadbadbadbadbadbadbad") ; => #f
 