Bitcoin/address validation

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, O, I and l.

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.

Here is an example of a bitcoin address:

1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i

It does not belong to anyone. It is part of the test suite of the bitcoin software. You can change a few characters in this string and check that it will fail the test.

extra credit: allow your code to deal with compressed keys

C

<lang c>#include <stdio.h>

include <string.h>
include <openssl/sha.h>

const char *coin_err;

define bail(s) { coin_err = s; return 0; }

int unbase58(const char *s, unsigned char *out) { static const char *tmpl = "123456789" "ABCDEFGHJKLMNPQRSTUVWXYZ" "abcdefghijkmnopqrstuvwxyz"; int i, j, c; const char *p;

memset(out, 0, 25); for (i = 0; s[i]; i++) { if (!(p = strchr(tmpl, s[i]))) bail("bad char");

c = p - tmpl; for (j = 25; j--; ) { c += 58 * out[j]; out[j] = c % 256; c /= 256; }

if (c) bail("address too long"); }

return 1; }

int valid(const char *s) { unsigned char dec[32], d1[SHA256_DIGEST_LENGTH], d2[SHA256_DIGEST_LENGTH];

coin_err = ""; if (!unbase58(s, dec)) return 0;

SHA256(SHA256(dec, 21, d1), SHA256_DIGEST_LENGTH, d2);

if (memcmp(dec + 21, d2, 4)) bail("bad digest");

return 1; }

int main (void) { const char *s[] = { "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9", "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i", "1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nJ9", "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62I", 0 }; int i; for (i = 0; s[i]; i++) { int status = valid(s[i]); printf("%s: %s\n", s[i], status ? "Ok" : coin_err); }

return 0; }</lang>

Erlang

Using base58 module from http://github.com/titan098/erl-base58.git.

<lang Erlang> -module( bitcoin_address ).

-export( [task/0, validate/1] ).

task() -> io:fwrite( "Validate ~p~n", ["1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"] ), io:fwrite( "~p~n", [validate("1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i")] ), io:fwrite( "Validate ~p~n", ["1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW622"] ), io:fwrite( "~p~n", [validate("1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW622")] ).

validate( String ) -> {length_25, <<Address:21/binary, Checksum:4/binary>>} = {length_25, base58:base58_to_binary( String )}, <<Version:1/binary, _/binary>> = Address, {version_0, <<0>>} = {version_0, Version}, <<Four_bytes:4/binary, _T/binary>> = crypto:hash( sha256, crypto:hash(sha256, Address) ), {checksum, Checksum} = {checksum, Four_bytes}, ok. </lang>

Output:

17>  bitcoin_address:task().
Validate "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i"
ok
Validate "1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW622"
** exception error: no match of right hand side value {checksum,<<"ÀF²ÿ">>}
     in function  bitcoin_address:validate/1 (src/bitcoin_address.erl, line 16)
     in call from bitcoin_address:task/0 (src/bitcoin_address.erl, line 9)

Go

Translation of: C

<lang go>package main

import (

   "bytes"
   "crypto/sha256"
   "errors"
   "os"

)

// With at least one other bitcoin RC task, this source is styled more like // a package to show how functions of the two tasks might be combined into // a single package. It turns out there's not really that much shared code, // just the A25 type and doubleSHA256 method, but it's enough to suggest how // the code might be organized. Types, methods, and functions are capitalized // where they might be exported from a package.

// A25 is a type for a 25 byte (not base58 encoded) bitcoin address. type A25 [25]byte

func (a *A25) Version() byte {

   return a[0]

}

func (a *A25) EmbeddedChecksum() (c [4]byte) {

   copy(c[:], a[21:])
   return

}

// DoubleSHA256 computes a double sha256 hash of the first 21 bytes of the // address. This is the one function shared with the other bitcoin RC task. // Returned is the full 32 byte sha256 hash. (The bitcoin checksum will be // the first four bytes of the slice.) func (a *A25) doubleSHA256() []byte {

   h := sha256.New()
   h.Write(a[:21])
   d := h.Sum([]byte{})
   h = sha256.New()
   h.Write(d)
   return h.Sum(d[:0])

}

// ComputeChecksum returns a four byte checksum computed from the first 21 // bytes of the address. The embedded checksum is not updated. func (a *A25) ComputeChecksum() (c [4]byte) {

   copy(c[:], a.doubleSHA256())
   return

}/* Go */

// Tmpl and Set58 are adapted from the C solution. // Go has big integers but this techinique seems better. var tmpl = []byte("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz")

// Set58 takes a base58 encoded address and decodes it into the receiver. // Errors are returned if the argument is not valid base58 or if the decoded // value does not fit in the 25 byte address. The address is not otherwise // checked for validity. func (a *A25) Set58(s []byte) error {

   for _, s1 := range s {
       c := bytes.IndexByte(tmpl, s1)
       if c < 0 {
           return errors.New("bad char")
       }
       for j := 24; j >= 0; j-- {
           c += 58 * int(a[j])
           a[j] = byte(c % 256)
           c /= 256
       }
       if c > 0 {
           return errors.New("too long")
       }
   }
   return nil

}

// ValidA58 validates a base58 encoded bitcoin address. An address is valid // if it can be decoded into a 25 byte address, the version number is 0, // and the checksum validates. Return value ok will be true for valid // addresses. If ok is false, the address is invalid and the error value // may indicate why. func ValidA58(a58 []byte) (ok bool, err error) {

   var a A25
   if err := a.Set58(a58); err != nil {
       return false, err
   }
   if a.Version() != 0 {
       return false, errors.New("not version 0")
   }
   return a.EmbeddedChecksum() == a.ComputeChecksum(), nil

}

// Program returns exit code 0 with valid address and produces no output. // Otherwise exit code is 1 and a message is written to stderr. func main() {

   if len(os.Args) != 2 {
       errorExit("Usage: valid <base58 address>")
   }
   switch ok, err := ValidA58([]byte(os.Args[1])); {
   case ok:
   case err == nil:
       errorExit("Invalid")
   default:
       errorExit(err.Error())
   }

}

func errorExit(m string) {

   os.Stderr.WriteString(m + "\n")
   os.Exit(1)

}</lang>

Output:

Command line usage examples showing program exit status.

> valid ; echo $status
Usage: valid <base58 address>
1
> valid 1 1 ; echo $status
Usage: valid <base58 address>
1
> valid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i ; echo $status
0
> valid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62j ; echo $status
Invalid
1
> valid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62! ; echo $status
bad char
1
> valid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62iz ; echo $status
not version 0
1
> valid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62izz ; echo $status
too long
1

Perl

Translation of: C

<lang perl>my @b58 = qw{

     1 2 3 4 5 6 7 8 9
   A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
   a b c d e f g h i j k   m n o p q r s t u v w x y z

}; my %b58 = map { $b58[$_] => $_ } 0 .. 57;

sub unbase58 {

   use integer;
   my @out;
   for my $c ( map { $b58{$_} } shift =~ /./g ) {
       for (my $j = 25; $j--; ) {
           $c += 58 * ($out[$j] // 0);
           $out[$j] = $c % 256;
           $c /= 256;
       }
   }
   return @out;

}

sub check_bitcoin_address {

   # does nothing if the address is valid
   # dies otherwise
   use Digest::SHA qw(sha256);
   my @byte = unbase58 shift;
   die "wrong checksum" unless
   join(, map { chr } @byte[21..24]) eq
   substr sha256(sha256 pack 'C*', @byte[0..20]), 0, 4;

}</lang>

Perl 6

Translation of: C

<lang perl6>enum B58 <

     1 2 3 4 5 6 7 8 9
   A B C D E F G H   J K L M N   P Q R S T U V W X Y Z
   a b c d e f g h i j k   m n o p q r s t u v w x y z

>;

sub unbase58(Str $str) {

   my @out = 0 xx 25;
   for B58.enums.hash{$str.comb} {
       my $c = $_;
       for reverse ^25 {
           $c += 58 * @out[$_];
           @out[$_] = $c % 256;
           $c div= 256;
       }
   }
   return @out;

}

sub check-bitcoin-address($addr) {

   use Digest;
   my @byte = unbase58 $addr;
   !!! 'wrong checksum' unless @byte[21..24] ~~
   sha256(sha256 Buf.new: @byte[0..20]).subbuf(0, 4).list;

}</lang>

Python

<lang python>from hashlib import sha256

digits58 = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def decode_base58(bc, length):

   n = 0
   for char in bc:
       n = n * 58 + digits58.index(char)
   return n.to_bytes(length, 'big')

def check_bc(bc):

   bcbytes = decode_base58(bc, 25)
   return bcbytes[-4:] == sha256(sha256(bcbytes[:-4]).digest()).digest()[:4]

if __name__ == '__main__':

   bc = '1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i'
   assert check_bc(bc)
   assert not check_bc( bc.replace('N', 'P', 1) )
   assert check_bc('1111111111111111111114oLvT2')
   assert check_bc("17NdbrSGoUotzeGCcMMCqnFkEvLymoou9j")</lang>

Output:

No output signifying success.

Help: For those looking at examples here to try and work out what is required, the n.to_bytes() call is equivalent to this code which converts a (long) integer into individual bytes of a byte array in a particular order:; <lang python>>>> n = 2491969579123783355964723219455906992268673266682165637887

>>> length = 25 >>> list( reversed(range(length)) ) [24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0] >>> assert n.to_bytes(length, 'big') == bytes( (n >> i*8) & 0xff for i in reversed(range(length))) >>> </lang>

Racket

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 </lang>

Tcl

Library: Tcllib (Package: sha256)

<lang tcl>package require sha256

Generate a large and boring piece of code to do the decoding of
base58-encoded data.

apply {{} {

   set chars "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
   set i -1
   foreach c [split $chars ""] {

lappend map $c "return -level 0 [incr i]"

   }
   lappend map default {return -code error "bad character \"$c\""}
   proc base58decode str [string map [list @BODY@ [list $map]] {

set num 0 set count [expr {ceil(log(58**[string length $str])/log(256))}] foreach c [split $str {}] { set num [expr {$num*58+[switch $c @BODY@]}] } for {set i 0} {$i < $count} {incr i} { append result [binary format c [expr {$num & 255}]] set num [expr {$num >> 8}] } return [string reverse $result]

}]

}}

How to check bitcoin address validity

proc bitcoin_addressValid {address} {

   set a [base58decode $address]
   set ck [sha2::sha256 -bin [sha2::sha256 -bin [string range $a 0 end-4]]]
   if {[string range $a end-3 end] ne [string range $ck 0 3]} {

return -code error "signature does not match"

   }
   return "$address is ok"

}</lang> Testing if it works <lang tcl>puts [bitcoin_addressValid 1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9] puts [bitcoin_addressValid 1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i]</lang>

Output:

1Q1pE5vPGEEMqRcVRMbtBK842Y6Pzo6nK9 is ok
1AGNa15ZQXAZUgFiqJ2i7Z2DPU2J6hW62i is ok

UNIX Shell

Works with: bash

<lang bash>base58=({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z}) bitcoinregex="^[$(printf "%s" "${base58[@]}")]{34}$"

decodeBase58() {

   local s=$1
   for i in {0..57}
   do s="${s//${base58[i]}/ $i}"
   done
   dc <<< "16o0d${s// /+58*}+f"

}

checksum() {

   xxd -p -r <<<"$1" |
   openssl dgst -sha256 -binary |
   openssl dgst -sha256 -binary |
   xxd -p -c 80 |
   head -c 8

}

checkBitcoinAddress() {

   if "$1" =~ $bitcoinregex 
   then
       h=$(decodeBase58 "$1")
       checksum "00${h::${#h}-8}" |
       grep -qi "^${h: -8}$"
   else return 2
   fi

}</lang>