Bitcoin/address validation: Difference between revisions
m →{{header|Perl}}: adding error message |
|||
Line 180: | Line 180: | ||
>>> assert n.to_bytes(length, 'big') == bytes( (n >> i*8) & 0xff for i in reversed(range(length))) |
>>> assert n.to_bytes(length, 'big') == bytes( (n >> i*8) & 0xff for i in reversed(range(length))) |
||
>>> </lang> |
>>> </lang> |
||
=={{header|Racket}}== |
|||
<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> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 05:23, 26 May 2013
You are encouraged to solve this task according to the task description, using any language you may know.
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>
Perl
<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
<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>
- 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
<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
<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>