Gavin Andresen (OP)
Legendary
Offline
Activity: 1652
Merit: 2300
Chief Scientist
|
|
September 13, 2010, 12:38:24 PM Last edit: October 20, 2010, 03:18:57 PM by gavinandresen |
|
This bitcoind address validator is a subclass of the Django forms.CharField class, but could easily be adapted to other frameworks or to be standalone code. It does a "deep" validation, checking that the checksum built into every bitcoin address matches the address. It needs the PyCrypto library for the SHA256 function. I hereby release this code into the public domain, do with it what you will. And please let me know if you find any bugs in it. BCAddressField.py: # # DJango field type for a Bitcoin Address # import re from django import forms from django.forms.util import ValidationError from Crypto.Hash import SHA256
class BCAddressField(forms.CharField): default_error_messages = { 'invalid': 'Invalid Bitcoin address.', }
def __init__(self, *args, **kwargs): super(BCAddressField, self).__init__(*args, **kwargs)
def clean(self, value): value = value.strip() if re.match(r"[a-zA-Z1-9]{27,35}$", value) is None: raise ValidationError(self.error_messages['invalid']) version = get_bcaddress_version(value) if version is None: raise ValidationError(self.error_messages['invalid']) return value
import math
__b58chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' __b58base = len(__b58chars)
def b58encode(v): """ encode v, which is a string of bytes, to base58. """
long_value = 0L for (i, c) in enumerate(v[::-1]): long_value += (256**i) * ord(c)
result = '' while long_value >= __b58base: div, mod = divmod(long_value, __b58base) result = __b58chars[mod] + result long_value = div result = __b58chars[long_value] + result
# Bitcoin does a little leading-zero-compression: # leading 0-bytes in the input become leading-1s nPad = 0 for c in v: if c == '\0': nPad += 1 else: break
return (__b58chars[0]*nPad) + result
def b58decode(v, length): """ decode v into a string of len bytes """ long_value = 0L for (i, c) in enumerate(v[::-1]): long_value += __b58chars.find(c) * (__b58base**i)
result = '' while long_value >= 256: div, mod = divmod(long_value, 256) result = chr(mod) + result long_value = div result = chr(long_value) + result
nPad = 0 for c in v: if c == __b58chars[0]: nPad += 1 else: break
result = chr(0)*nPad + result if length is not None and len(result) != length: return None
return result
def get_bcaddress_version(strAddress): """ Returns None if strAddress is invalid. Otherwise returns integer version of address. """ addr = b58decode(strAddress,25) if addr is None: return None version = addr[0] checksum = addr[-4:] vh160 = addr[:-4] # Version plus hash160 is what is checksummed h3=SHA256.new(SHA256.new(vh160).digest()).digest() if h3[0:4] == checksum: return ord(version) return None
October 20: Fixed bug with bitcoin addresses with leading-1's.
|
How often do you get the chance to work on a potentially world-changing project?
|
|
|
davout
Legendary
Offline
Activity: 1372
Merit: 1007
1davout
|
|
October 19, 2010, 10:55:32 PM |
|
Thanks for your code ! Contributing with a Ruby translation (more specifically a Rails drop-in validator) require 'digest'
class BitcoinAddressValidator < ActiveModel::EachValidator def validate(record, field, value) unless valid_bitcoin_address?(value) record.errors[field] << "Bitcoin address is invalid" end end
private
B58Chars = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz' B58Base = B58Chars.length
def self.valid_bitcoin_address?(address) (address =~ /^[a-zA-Z1-9]{33,35}$/) and version(address) end
def self.version(address) decoded = b58_decode(address, 25) version = decoded[0, 1] checksum = decoded[-4, decoded.length] vh160 = decoded[0, decoded.length - 4]
hashed = (Digest::SHA2.new << (Digest::SHA2.new << vh160).digest).digest
hashed[0, 4] == checksum ? version[0] : nil end
def self.b58_decode(value, length) long_value = 0 index = 0 result = ""
value.reverse.each_char do |c| long_value += B58Chars.index(c) * (B58Base ** index) index += 1 end
while long_value >= 256 do div, mod = long_value.divmod 256 result = mod.chr + result long_value = div end
result = long_value.chr + result
if result.length < length result = 0.chr * (length - result.length) + result end
result end end Passes unit tests (see http://github.com/davout/bitcoin-bank) Just a question, what's the use of your b58_encode method ?
|
|
|
|
ByteCoin
|
|
October 19, 2010, 11:40:42 PM |
|
(address =~ /^[a-zA-Z1-9]{33,35}$/) You should bear in mind the fact that 1111111111111111111114oLvT2 is a valid Bitcoin address. It has 27 characters. 28,29,30... etc character addresses also exist. I have mentioned this before in ByteCoin
|
|
|
|
Gavin Andresen (OP)
Legendary
Offline
Activity: 1652
Merit: 2300
Chief Scientist
|
|
October 20, 2010, 12:43:36 AM |
|
RE: what's the use of b58_encode? It is dead code for this use-- bitcointools (where I first implemented this stuff) uses it to translate from binary hash160 to human-readable bitcoin addresses.
RE: 27 character bitcoin addresses: I'm puzzled. There's a mismatch between the way bitcoin treats leading zeros (leading 1's when base58 encoded) and the way my python code treats them.
ByteCoin: have you dissected the bitcoin code enough to explain how it decides how many leading zeros to add? According to my code, '14oLvT2' and '11111111111111111111111111114oLvT2' are the same bitcoin address (corresponding to the public key with a hash of all zero bytes).
But bitcoin only likes the 27-character '1111111111111111111114oLvT2' version.
I'll have to stare at the code some more tomorrow when I'm more awake.
|
How often do you get the chance to work on a potentially world-changing project?
|
|
|
theymos
Administrator
Legendary
Offline
Activity: 5306
Merit: 13296
|
|
October 20, 2010, 01:50:10 AM Last edit: October 20, 2010, 02:04:37 AM by theymos |
|
For every leading 0x00 byte, add a leading 1 (encode). For every leading 1, add a 0x00 byte (decode). For encode, don't accept input that doesn't have an even number of bits (divisible by eight), as this doesn't make sense. For decode, pad leading zeros until you have an even number of bits. I just check that the output immediately post-DecodeBase58 (including leading zeroes, checksum, versionNumber) is 25 bytes long. I think that Bitcoin does something similar to this. I made some web tools for dealing with addresses: http://theymos.ath.cx:64150/q/checkaddresshttp://theymos.ath.cx:64150/q/addresstohashhttp://theymos.ath.cx:64150/q/hashtoaddresshttp://theymos.ath.cx:64150/q/hashpubkey(Source not public yet.)
|
1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
|
|
|
Gavin Andresen (OP)
Legendary
Offline
Activity: 1652
Merit: 2300
Chief Scientist
|
|
October 20, 2010, 03:18:17 PM |
|
Thanks theymos! I completely missed the leading-zero-bytes become leading-'1'-chars one-for-one.
I fixed the python code in the first message of this thread.
|
How often do you get the chance to work on a potentially world-changing project?
|
|
|
ploum
|
|
October 25, 2010, 07:46:52 AM |
|
Are you working on a Django bitcoin project ? I'm highly interested, thinking about it myself too.
|
|
|
|
MagicalTux
VIP
Hero Member
Offline
Activity: 608
Merit: 501
-
|
|
November 15, 2010, 07:01:46 PM |
|
For those interested, I rewrote base58_encode/base58_decode in PHP, and added a "decode_btc" function (that will return an array containing "version" and "hash" for a given bitcoin address). This code requires the following php extensions: - gmp (for bignum values, we could use bc, or even the php-native implementation in pear, I'm just too lazy and I got gmp installed on all my servers anyway)
- hash (or mhash, someone could insert a php-native sha256 implementation to fallback to)
Here's the code, largely inspired from the code of the previous authors of this thread: <?php $btc = decode_btc('1Eym7pyJcaambv8FG4ZoU8A4xsiL9us2zz'); var_dump($btc); var_dump(encode_btc($btc)); $btc = decode_btc('1111111111111111111114oLvT2'); var_dump($btc); var_dump(encode_btc($btc));
function hash_sha256($string) { if (function_exists('hash')) return hash('sha256', $string, true); if (function_exists('mhash')) return mhash(MHASH_SHA256, $string); // insert native php implementation of sha256 here throw new Exception('Too lazy to fallback when the guy who configured php was lazy too'); }
function encode_btc($btc) { $btc = chr($btc['version']).pack('H*', $btc['hash']); if (strlen($btc) != 21) return false; $cksum = substr(hash_sha256(hash_sha256($btc)), 0, 4); return base58_encode($btc.$cksum); }
function decode_btc($btc) { $btc = base58_decode($btc); if (strlen($btc) != 25) return false; // invalid $version = ord($btc[0]); $cksum = substr($btc, -4); // checksum is double sha256 (take 4 first bytes of result) $good_cksum = substr(hash_sha256(hash_sha256(substr($btc, 0, -4))), 0, 4); if ($cksum != $good_cksum) return false; return array('version' => $version, 'hash' => bin2hex(substr($btc, 1, 20))); }
function base58_encode($string) { $table = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';
$long_value = gmp_init(bin2hex($string), 16);
$result = ''; while(gmp_cmp($long_value, 58) > 0) { list($long_value, $mod) = gmp_div_qr($long_value, 58); $result .= $table[gmp_intval($mod)]; } $result .= $table[gmp_intval($long_value)];
for($nPad = 0; $string[$nPad] == "\0"; ++$nPad);
return str_repeat($table[0], $nPad).strrev($result); }
function base58_decode($string) { $table = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'; static $table_rev = null; if (is_null($table_rev)) { $table_rev = array(); for($i=0;$i<58;++$i) $table_rev[$table[$i]]=$i; }
$l = strlen($string); $long_value = gmp_init('0'); for($i=0;$i<$l;++$i) { $c=$string[$l-$i-1]; $long_value = gmp_add($long_value, gmp_mul($table_rev[$c], gmp_pow(58, $i))); }
// php is lacking binary output for gmp $res = pack('H*', gmp_strval($long_value, 16));
for($nPad = 0; $string[$nPad] == $table[0]; ++$nPad); return str_repeat("\0", $nPad).$res; }
This outputs: array(2) { ["version"]=> int(0) ["hash"]=> string(40) "9955c1b44fa66688d27aaa06ba4ad02c6dd91088" } string(34) "1Eym7pyJcaambv8FG4ZoU8A4xsiL9us2zz" array(2) { ["version"]=> int(0) ["hash"]=> string(40) "0000000000000000000000000000000000000000" } string(27) "1111111111111111111114oLvT2"
|
|
|
|
jerfelix
|
|
May 28, 2011, 10:44:52 PM |
|
default_error_messages = { 'invalid': 'Invalid Bitcoin address.', }
def __init__(self, *args, **kwargs): super(BCAddressField, self).__init__(*args, **kwargs)
def clean(self, value): value = value.strip() if re.match(r"[a-zA-Z1-9]{27,35}$", value) is None: raise ValidationError(self.error_messages['invalid'])
Gavin, I'm trying to understand your usage of default.error_messages (first line in the snippet), vs. self.error_messages (last line in the snippet, above), in your code. Does Django somehow link those two together? Or is that a bug in the code? (I'm sure this code has been tested a lot since October!) Seems to me that you should be using the same dictionary in both places.
|
|
|
|
grondilu
Legendary
Offline
Activity: 1288
Merit: 1080
|
|
May 28, 2011, 11:05:22 PM |
|
It's kind of frustrating that nobody seems to want to use my bash functions to check bitcoin addresses. It only requires basic unix tools such as xxd, dc and openssl. 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 }
|
|
|
|
beppu
Newbie
Offline
Activity: 5
Merit: 0
|
|
May 29, 2011, 10:10:19 PM |
|
It's kind of frustrating that nobody seems to want to use my bash functions to check bitcoin addresses.
It only requires basic unix tools such as xxd, dc and openssl.
This is beautiful and concise shell scripting. Nice job.
|
|
|
|
grondilu
Legendary
Offline
Activity: 1288
Merit: 1080
|
|
May 29, 2011, 11:09:01 PM |
|
It's kind of frustrating that nobody seems to want to use my bash functions to check bitcoin addresses.
It only requires basic unix tools such as xxd, dc and openssl.
This is beautiful and concise shell scripting. Nice job. Ah, finally! Thanks!
|
|
|
|
Yogafan00000
|
|
November 15, 2012, 02:38:58 PM |
|
.NET 4.0 version of bitcoin address validation, Translated by YogaFan: Imports System.Security.Cryptography Imports System.Numerics
Module ValidateBitCoinAddress
Function isValidBitcoinAddress(s As String) As Boolean Dim regExPattern As String = "[a-zA-Z1-9]{27,35}$" If MatchString(s, regExPattern) Then If get_bcaddress_version(s) <> "" Then isValidBitcoinAddress = True Else isValidBitcoinAddress = False End If Else isValidBitcoinAddress = False End If End Function
Function MatchString(ByVal str As String, ByVal regexstr As String) As Boolean str = str.Trim() Dim pattern As New System.Text.RegularExpressions.Regex(regexstr) Return pattern.IsMatch(str) End Function
Function get_bcaddress_version(strAddress) As String
Dim addr As Byte() Dim version As Byte Dim checksum(3) As Byte Dim h3(3) As Byte Dim x As Integer
addr = b58decode(strAddress, 25)
If IsNothing(addr) Then 'fail get_bcaddress_version = "" Exit Function End If
Dim lenAddr As Integer = addr.GetLength(0) Dim vh160(lenAddr - 5) As Byte Dim sha As New SHA256Managed()
version = addr(0) checksum = {addr(lenAddr - 4), addr(lenAddr - 3), addr(lenAddr - 2), addr(lenAddr - 1)}
For x = 0 To vh160.GetLength(0) - 1 vh160(x) = addr(x) Next
Dim Hash() As Byte = sha.ComputeHash(vh160) Dim SecondHash() As Byte = sha.ComputeHash(Hash)
h3 = {SecondHash(0), SecondHash(1), SecondHash(2), SecondHash(3)}
If h3(0) = checksum(0) And h3(1) = checksum(1) And h3(2) = checksum(2) And h3(3) = checksum(3) Then get_bcaddress_version = version.ToString Else 'fail get_bcaddress_version = "" End If
End Function
Function b58encode(b() As Byte) As String
Dim b58chars As String = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" Dim b58base As BigInteger = 58 Dim x As BigInteger Dim long_value As BigInteger = 0 Dim result As String = "" Dim iMod As BigInteger = 0 Dim iDiv As BigInteger = 0 Dim b256base As BigInteger = 256
Dim c As Integer Dim lv As Integer
lv = b.GetLength(0) - 1 c = 0 For x = lv To 0 Step -1 long_value = long_value + BigInteger.Pow(b256base, x) * b(c) c = c + 1 Next
Do While long_value >= b58base iMod = long_value Mod b58base iDiv = long_value / b58base
result = b58chars(iMod) & result long_value = iDiv Loop result = b58chars(long_value) & result
For x = 0 To lv If b(x) = CByte(0) Then result = b58chars(0) & result Else Exit For End If Next
Return result End Function
Function insertat(b As Byte, bArr As Byte(), pos As Integer) As Byte()
If IsNothing(bArr) Then 'empty array; return single celled array Dim tmpsomeOtherBarr(0) As Byte tmpsomeOtherBarr(0) = b insertat = tmpsomeOtherBarr Exit Function End If
Dim x As Integer Dim tmpbArr(bArr.GetLength(0)) As Byte
If pos = -1 Then 'insert at end of array For x = 0 To bArr.GetLength(0) - 1 tmpbArr(x) = bArr(x) Next tmpbArr(bArr.GetLength(0)) = b
Return tmpbArr ElseIf pos = 0 Then 'insert at beginning tmpbArr(0) = b For x = 1 To bArr.GetLength(0) tmpbArr(x) = bArr(x - 1) Next Return tmpbArr Else 'insert in the middle For x = 0 To pos - 1 tmpbArr(x) = bArr(x) Next tmpbArr(pos) = b For x = pos + 1 To bArr.GetLength(0) tmpbArr(x) = bArr(x) Next Return tmpbArr
End If End Function
Function b58decode(v As String, l As Integer) As Byte()
Dim b58chars As String = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" Dim b58base As BigInteger = 58 Dim long_value As BigInteger = 0 Dim lv As Integer Dim c As Integer Dim x As BigInteger Dim biPos As BigInteger = 0 Dim iMod As BigInteger = 0 Dim iDiv As BigInteger = 0 Dim result() As Byte
lv = Len(v) - 1
For x = lv To 0 Step -1 c = c + 1 biPos = b58chars.IndexOf(Mid(v, c, 1)) long_value = long_value + BigInteger.Pow(b58base, x) * biPos Next
Do While long_value >= 256 iMod = long_value Mod 256 iDiv = long_value / 256 result = insertat(CByte(iMod), result, 0) long_value = iDiv Loop result = insertat(CByte(long_value), result, 0)
For x = 1 To Len(v) If Mid(v, x, 1) = b58chars(0) Then result = insertat(CByte(0), result, 0) Else Exit For End If Next
If l > 0 And result.GetLength(0) <> l Then Return Nothing Else Return result End If
End Function
End Module
|
1YogAFA... (oh, nevermind)
|
|
|
Xenland
Legendary
Offline
Activity: 980
Merit: 1003
I'm not just any shaman, I'm a Sha256man
|
|
November 17, 2012, 10:03:13 AM |
|
|
|
|
|
matmar10
Newbie
Offline
Activity: 47
Merit: 0
|
|
November 27, 2012, 05:18:21 PM |
|
For those interested, I rewrote base58_encode/base58_decode in PHP, and added a "decode_btc" function (that will return an array containing "version" and "hash" for a given bitcoin address). This code requires the following php extensions: - gmp (for bignum values, we could use bc, or even the php-native implementation in pear, I'm just too lazy and I got gmp installed on all my servers anyway)
- hash (or mhash, someone could insert a php-native sha256 implementation to fallback to)
Here's the code, largely inspired from the code of the previous authors of this thread: <?php $btc = decode_btc('1Eym7pyJcaambv8FG4ZoU8A4xsiL9us2zz'); var_dump($btc); var_dump(encode_btc($btc)); $btc = decode_btc('1111111111111111111114oLvT2'); var_dump($btc); var_dump(encode_btc($btc));
function hash_sha256($string) { if (function_exists('hash')) return hash('sha256', $string, true); if (function_exists('mhash')) return mhash(MHASH_SHA256, $string); // insert native php implementation of sha256 here throw new Exception('Too lazy to fallback when the guy who configured php was lazy too'); }
function encode_btc($btc) { $btc = chr($btc['version']).pack('H*', $btc['hash']); if (strlen($btc) != 21) return false; $cksum = substr(hash_sha256(hash_sha256($btc)), 0, 4); return base58_encode($btc.$cksum); }
function decode_btc($btc) { $btc = base58_decode($btc); if (strlen($btc) != 25) return false; // invalid $version = ord($btc[0]); $cksum = substr($btc, -4); // checksum is double sha256 (take 4 first bytes of result) $good_cksum = substr(hash_sha256(hash_sha256(substr($btc, 0, -4))), 0, 4); if ($cksum != $good_cksum) return false; return array('version' => $version, 'hash' => bin2hex(substr($btc, 1, 20))); }
function base58_encode($string) { $table = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz';
$long_value = gmp_init(bin2hex($string), 16);
$result = ''; while(gmp_cmp($long_value, 58) > 0) { list($long_value, $mod) = gmp_div_qr($long_value, 58); $result .= $table[gmp_intval($mod)]; } $result .= $table[gmp_intval($long_value)];
for($nPad = 0; $string[$nPad] == "\0"; ++$nPad);
return str_repeat($table[0], $nPad).strrev($result); }
function base58_decode($string) { $table = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'; static $table_rev = null; if (is_null($table_rev)) { $table_rev = array(); for($i=0;$i<58;++$i) $table_rev[$table[$i]]=$i; }
$l = strlen($string); $long_value = gmp_init('0'); for($i=0;$i<$l;++$i) { $c=$string[$l-$i-1]; $long_value = gmp_add($long_value, gmp_mul($table_rev[$c], gmp_pow(58, $i))); }
// php is lacking binary output for gmp $res = pack('H*', gmp_strval($long_value, 16));
for($nPad = 0; $string[$nPad] == $table[0]; ++$nPad); return str_repeat("\0", $nPad).$res; }
This outputs: array(2) { ["version"]=> int(0) ["hash"]=> string(40) "9955c1b44fa66688d27aaa06ba4ad02c6dd91088" } string(34) "1Eym7pyJcaambv8FG4ZoU8A4xsiL9us2zz" array(2) { ["version"]=> int(0) ["hash"]=> string(40) "0000000000000000000000000000000000000000" } string(27) "1111111111111111111114oLvT2" Thanks for sharing this source! I've used your implementation, but I noticed some addresses don't validate. For example: 12HzMcHURwmAxAkfWgtktYsF3vRTkBz4F3 Any thoughts on why?
|
|
|
|
grondilu
Legendary
Offline
Activity: 1288
Merit: 1080
|
|
November 27, 2012, 07:23:50 PM |
|
Has anyone written a test-suite for key generation-validation?
I mean, a text/json/whatever file where you'd have a couple of address/private key pairs?
And in all possible formats (test network, compressed/uncompressed and so on...).
That would be useful.
|
|
|
|
jgarzik
Legendary
Offline
Activity: 1596
Merit: 1099
|
|
November 27, 2012, 08:00:11 PM |
|
Has anyone written a test-suite for key generation-validation?
I mean, a text/json/whatever file where you'd have a couple of address/private key pairs?
And in all possible formats (test network, compressed/uncompressed and so on...).
That would be useful.
There is some JSON test data at https://github.com/bitcoin/bitcoin/tree/master/src/test/dataI'm using this for a C-based "libccoin" bitcoin library testing https://github.com/jgarzik/picocoin/
|
Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own. Visit bloq.com / metronome.io Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
|
|
|
|
grondilu
Legendary
Offline
Activity: 1288
Merit: 1080
|
|
November 28, 2012, 01:05:54 AM |
|
|
|
|
|
matmar10
Newbie
Offline
Activity: 47
Merit: 0
|
|
November 28, 2012, 09:02:58 AM |
|
Thanks for this contribution! I ran the test fixtures for valid and invalid public keys listed below, with a few of my own known keys added; I got the following result: There was 1 failure: 1) Lmh\BitcoinTransferBundle\Tests\BitcoinAddressValidatorTest::testInvalid Test invalid public key '37qgekLpCCHrQuSjvX3fs496FWTGsHFHizjJAs6NPcR47aefnnCWECAhHV6E3g4YN7u7Yuwod5Y' returns 1 error. Failed asserting that 0 matches expected 1. /Users/matmar10/Projects/bitcoinbymobile/src/Lmh/BitcoinTransferBundle/Tests/BitcoinAddressValidatorTest.php:69 FAILURES! Tests: 2, Assertions: 22, Failures: 1. By the way, your PHP code had an undefined variable throwing an error and also an unused variable; I'll send you a git push request.
|
|
|
|
|