読者です 読者をやめる 読者になる 読者になる

Bitcoin geeky blog

Essence of Bitcoin is innovation that may be related to remittance and asset holding rights and liberation and freedom.

Hierarchical Deterministic Wallets

Oveview
The type is leading-edge deterministic wallets that is described in BIP 0032.Just have to copy root-seed,You can restore overall HD wallet,backup of millions keys or HD wallet , and export.It can generate public key without users have exposure to private key.In other words, it can generate in independent environments,private key will be able to storage in safe place.


f:id:adrenaline2017:20170410133107j:plain


Generate HD wallets from seed

1.Secure pseudo-random number generator generate to Root Seed(128-256 bits)

2.Root Seed(512bit) is generated using PBKDF2(key extended function)from seed(128-256bits)

3.Hash value is calculated from Root Seed by using HMAC-SHA512

4.Left half of hash become 'Master private key',and right half of hash become 'Master chain code'

5.The generate method of master public key is exactly the same method which was introduced in past articles(using ECDSA to private key)

f:id:adrenaline2017:20170412093735j:plain


Extended Key
It add parent key(256-bits) to chain code(256-bits) in order to generate child.

Extended private key(parent privkey + chain code)
It possible to generate child privkey and child pubkey.
Expanded privkey can create complete branch root.

Extended privkey example(Prefix become "xprv")

xprv9tyUQV64JT5qs3RSTJkXCWKMyUgoQp7F3hA1xzG6...

Extended public key(parent pubkey + chain code)
It possible to generate child pubkey.
Expand privkey can create branch of pubkey only.

Extended pubkey example(Prefix become "xpub")

xpub67xpozcx8pe95XVuZLHXZeG6XWXHpGq6Qv5cmNfi...


Master private key & Master chain code

def bip32_master_key(seed):
    I = hmac.new(bytes("Bitcoin seed", 'utf-8'), seed, hashlib.sha512).digest()

    vbytes = b'\x04\x88\xAD\xE4'
    depth = 0
    fingerprint = b'\x00\x00\x00\x00'
    i = b'\x00\x00\x00\x00'
    chaincode = encode(decode(I[32:], 256), 256, 32)
    keydata = b'\x00'+(I[:32]+b'\x01')[:-1]

    bindata = vbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
    string=bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4]
    return encode(decode(string, 256), 58, 0)

bip32_masterprivatekey = bip32_master_key(privatekey)

def bip32_master_key(seed):
→"seed" use Root seed(512bit)

I = hmac.new(bytes("Bitcoin seed", 'utf-8'), seed, hashlib.sha512).digest()
→Calculate of Hmac use Python module

chaincode = encode(decode(I[32:], 256), 256, 32)
→Master chain code

bindata = vbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
→Encode by Base58chack for sum ① to ⑥

①vbytes(Prefix of private key defined by BIP32)
②depth(Derived path depth)
③fingerprin(Connection with parents)
④i(Key index)
⑤chaincode(Master chaincode)
⑥keydata(Master private key)

※The value is 0 for initial state about ② to ④


Master public key

def bip32_serialize(rawtuple):
    dbin = encode(decode(rawtuple, 58), 256, 0)
    vbytes = dbin[0:4]
    depth = dbin[4]
    fingerprint = dbin[5:9]
    i = decode(dbin[9:13], 256)
    chaincode = dbin[13:45]
    key = dbin[46:78]+b'\x01'
    newvbytes = b'\x04\x88\xB2\x1E'
    
    privkey = decode(key[:32], 256)
    pub = fast_multiply(G, privkey)
    keydata = bytes([2+(pub[1] % 2)]) + encode(pub[0], 256, 32)
    i = encode(i, 256, 4)
    chaincode = encode(decode(chaincode, 256), 256, 32)
    bindata = newvbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
    return encode(decode((bindata+hashlib.sha256(hashlib.sha256(bindata).digest()).digest()[:4]), 256), 58, 0)

bip32_masterpublickey = bip32_serialize(bip32_masterprivatekey)  

dbin = encode(decode(rawtuple, 58), 256, 0)
→Convert hex to byte data of 256-hex,It contains the following information.
①dbin[0:4]:vbytes(4byte)
②dbin[4]:depth(1byte)
③dbin[5:9]:fingerprint(4byte)
④dbin[9:13]:i(4byte)
⑤dbin[13:45]:chain code(33byte)
⑥dbin[46:78]:key(33byte)

pub = fast_multiply(G, privkey)
→Use ECDSA to private key

keydata = bytes([2+(pub[1] % 2)]) + encode(pub[0], 256, 32)
→Generate compressed public key

bindata = newvbytes + bytes([depth % 256]) + fingerprint + i + chaincode + keydata
→Add edited data from ① to ⑥

encode(decode*1.digest()[:4]), 256), 58, 0)
→It encode by Base58chack


The code is used in this article,it have posted on GitHub.

*1:bindata+hashlib.sha256(hashlib.sha256(bindata).digest(

Mnemonic code

Overview
Mnemonic code is English words representing random numbers used as Wallet master keys.
Passphrase is easy to remember for human beings(passphrase 12 to 24 words).
Mnemonic is used to regenerate the seed (master key), regenerating wallet and all keys from this seed.


mnemonic code example

ten enable powder skull spot volume tragic search engage faculty tag pencil 
crowd record business same pudding bulb swear pony blush noise divert typical 


Flow
1.Generate entropy of 128 bits to 256 bits
2.Get the first 4 bits of SHA 256 hash of random array(=checksum)
3.Add this checksum to the end of the random array
4.Divide this array into 11 bit portions
5.Use as an index of 2048 predetermined English word dictionaries
6.Generate 12 to 24 English words representing mnemonic code


Code
1.Generate entropy

from random import choice
from binascii import hexlify

for i in range(10):
    data = ''.join(chr(choice(range(0, 256))) for _ in range(8 * (i % 3 + 2)))
    data = data.encode('latin1')
    h = (hexlify(data))
    print(h.decode('utf8'))

data = ''.join(chr(choice(range(0, 256))) for _ in range(8 * (i % 3 + 2)))
→Random Unicode of 16,24,36bytes

data = data.encode('latin1')
→Encode roman font

h = (hexlify(data))
→Convert to hexadecimal

(h.decode('utf8'))
→Decode to utf-8


2.Generate English word dictionaries

#Reading to list of mnemonic code 
with open('english.txt', 'r') as f:
    wordlist = [w.strip() for w in f.readlines()]
    print(wordlist)

with open('english.txt', 'r') as f:
→Read predetermined dictionary of 2048 English words

wordlist = [w.strip() for w in f.readlines()]
→List of 2048 English words

※Please refer to this "english.txt".


3.Generate mnemonic code word

def to_mnemonic(self, data):
        h = hashlib.sha256(data).hexdigest()
        b = bin(int(binascii.hexlify(data), 16))[2:].zfill(len(data) * 8) + \
            bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
        result = []
        
        for i in range(len(b) // 11):
            idx = int(b[i * 11:(i + 1) * 11], 2)
            result.append(self.wordlist[idx])
        result_phrase = ' '.join(result)
        return result_phrase

h = hashlib.sha256(data).hexdigest()
→Get SHA 256 hash of random array

bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
→Get the first 4 bits of SHA 256 hash of random array(checksum)

bin(int(binascii.hexlify(data), 16))[2:].zfill(len(data) * 8) + bin(int(h, 16))[2:].zfill(256)[:len(data) * 8 // 32]
→Add this checksum to the end of the random array

for i in range(len(b) // 11)
→Divide this array into 11 bit portions

idx = int(b[i * 11:(i + 1) * 11], 2)result.append(self.wordlist[idx])
→Generate 12 to 24 English words representing mnemonic code.


Seed
Seed (512 bits) is generated by using key extension function(PBKDF2) from mnemonic code.
The resulting seed is used to generate deterministic wallet and all keys.

def normalize_string(txt):
        if isinstance(txt, bytes):
            utxt = txt.decode('utf8')
        elif isinstance(txt, str):
            utxt = txt
        else:
            raise TypeError("String value expected")
        return unicodedata.normalize('NFKD', utxt)

def to_seed(mnemonic, passphrase=''):
        mnemonic = normalize_string(mnemonic)
        passphrase = normalize_string(passphrase)
        return PBKDF2(mnemonic, u'mnemonic' + passphrase, iterations=2048,
                      macmodule=hmac, digestmodule=hashlib.sha512).read(64)

def normalize_string(txt):
→Decode with utf-8 when text equal byte format
Unicode normalization(Normalization form compatibility decomposition)

PBKDF2(mnemonic, u'mnemonic' + passphrase, iterations=2048,macmodule=hmac, digestmodule=hashlib.sha512).read(64)
→PBKDF2 iterate hash function(hmac) thousands of times.by so doing, trying to spend time on brute force attack.
→pasword, pasward+slat(short string), iteration, macmodule, digestmodle


The code is used in this article,it have posted on GitHub.

Key format

Overview
Bitcoin has notation method of some kinds in private key and public key.

Why Bitcoin has some kinds of notation?
Because if you adopted compressed notation, It's possible to reduce the size of the public key by 50%!
That means we can reduce greatly the size of transaction and blockchain prevents enlargement.

Problems caused by using compressed notation
Wallet has two types that correspond to compressed or uncompressed,
Which causes problems when importing private key into different type of wallet.
The receiving wallet needs to scan the blockchain to find the transaction corresponding to the sent private key.
At that time, it can not be determined whether the address based on compressed public key or uncompressed public key.

problem solution
In order to solve the problem,private key use properly WIF format and WIF compression format.
f:id:adrenaline2017:20170407090740j:plain

Private key notation method
①Hexadecimal notation(64 hex characters)
The number was generated by random number(256-bit).
※About how to generate for raw private key,please check below past blog.

adrenaline2017.hatenablog.com

②WIF(prefix「5」:51 hex characters)
Format for importing private key into wallet(WIF).
It inform to came from new wallet that have compress function.

Flow

0x08 + private key → checksum

0x08 + private key + checksum → Base58checkencode → WIF

Code

def ifchecksum(code):
    return hashlib.sha256(hashlib.sha256(code).digest()).digest()[:4]

def private_key_to_wif(private_key):
    assert(len(private_key) == 32) 
    checksum = wifchecksum(b"\x80" + private_key)
    return b58encode(b"\x80" + private_key + checksum) 
   
print (private_key_to_wif(private_key))

def wifchecksum(code):
→Designated checksum for WIF
assert(len(private_key) == 32)
→If number of private key and 32 byte not equals,return error.
checksum = wifchecksum(b"\x80" + private_key)
→Add "0x08" to prefix of private key,generate checksum.
return b58encode(b"\x80" + private_key + checksum)
→Excutive Base58checkencode.

③WIF-compressed(prefix「K or L」:52-characters)
It indicate to came from new wallet that have compress function,and it means that must make compressed public key.

Flow

0x08 + private key + checksum + 0x01 → Base58checkencode

Code

def private_key_to_wif_compressed(private_key):                                    
    assert(len(private_key) == 32)                                                  
    checksum = wifchecksum(b"\x80" + private_key)                         
    return b58encode(b"\x80" +( private_key +b"\x01")+ checksum)
print(private_key_to_wif_compressed(private_key))  

def private_key_to_wif_compressed(private_key):
→The only one difference to WIF format, it do checksum after add "0x01".


Public key notation method
①Hexadecimal number notation(130 hex characters)
※About how to generate for hexadecimal public key,please check below past blog.

adrenaline2017.hatenablog.com

②Compressed(66 hex characters)
We can calculate the y coordinate by below equation of solving when know the x coordinate .

y2 mod p = (x3 + 7) mod p

But notice that means the solution for y is a square root, which have a positive or negative value.
When calculating elliptic curve on the finite field of prime number order p,
that means y coordinate is either even or odd,corresponds to the positive and negative sign.

Flow

0x02 + X coodinateoo(Y coordinate is even)
0x03 + X coodinateoo(Y coordinate is odd)

Code

(public_key_x, public_key_y) = public_key
if (public_key_y % 2) == 0:
    compressed_prefix = '02'
else:
    compressed_prefix = '03'    
encode_pubkey =  "%x"%public_key[0]
hex_compressed_public_key = compressed_prefix + encode_pubkey
print (hex_compressed_public_key)

(public_key_x, public_key_y) = public_key
→Public key divide to X coordinate and Y coordinate
compressed_prefix = '02', compressed_prefix = '03'
→Public key with the prefix 02 if the y is even, and 03 if it is odd

※1 If the wallet receiving the secret key does not correspond to the compressed format,it export private key in WIF format instead of WIF compressed format.
※2 If the wallet corresponde compressed format,when exporting private keys they are always output in compressed WIF format,and all transactions are done in compressed way.



The code used in this article is published in Github.