Subscribed unsubscribe Subscribe Subscribe

Bitcoin blog

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

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.

Remove all ads

Bitcoin address

Overview
Bitcoin address represent receiver of funds,it look like bank account.
The address produced from public key.
Show below example of a bitcoin address:

f:id:adrenaline2017:20170329212453p:plain

Bitcoin address example
15oYSxBcM5deLicKoqwNL2iuAJXpdoc3GL
※27-32 digit alphanumeric characters starting from 1 or 3

Flow
①Public key→SHA256→RIPEMD160→add prefix「0x00」→Let be called A

②A→SHA256→SHA256→prefix 4bytes(checksum)→Let be called B

③Add B behind A→Base58 encode→Bitcoin address

Hash function
The output of fixed bit width is calculated from input.
Always certain output calculated from certain input.
It is also called one-way function,The input can't restoration from output.
f:id:adrenaline2017:20170323093412j:plain

Theoretically, there is the possibility that the same output can be acquired from different inputs.
Bitcoin used SHA256 and RIPEMD160 hash functions that are designed so that 「collision」 unlikely.

Hash160
It's also call「Double hash」,Calculate hash value bySHA256andRIPEMD160.

def bin_hash160(string):
    intermed = hashlib.sha256(string).digest()
    digest = hashlib.new('ripemd160', intermed).digest()
    return digest

intermed = hashlib.sha256(string).digest():
→Hash by SHA256
digest = hashlib.new('ripemd160', intermed).digest():
→Hash by RIPEMD160

Checksum
Checksum is used error check of data transmission, record, replication.
Most simple error detection function.

The decoding software calculates checksum of encoded data,And compare with the included checksum.
If the two do not match, this indicates that an error has been mixed or that ths invalid.

def checksum(inp):
        inp = bytes([0]) + inp
        checksum_prefix = hashlib.sha256(hashlib.sha256(inp).digest()).digest()
        checksum = checksum_prefix[:4]
return checksum

def checksum(inp):
→Arguments use the hashed public key with HASH 160
inp = bytes([0]) + inp
→Add「0x00」to prefix
checksum_prefix = hashlib.sha256(hashlib.sha256(inp).digest()).digest()
→Twice hash to A
checksum = checksum_prefix[:4]
→The prefix 4 bytes is checksum

Decode
Encoded data restore to original form.

def decode(string, base):   
        base = int(base)
        result = 0
        while len(string) > 0:
            result *= base
            result += string[0]
            string = string[1:]
        return result

For example,when binary data is converted(decode) from hexadecimal to decimal.
you look at a character string unit by one character, it can be regarded as Base256 notation.
So each data multiply by 256, add to next data ,Repeat this.

Encode
The orignal fomat convert to different fomat.

def encode(val, base):
        base = int(base)
        code_string = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
        result_bytes = bytes()        
        while val > 0:
            curcode = code_string[val % base]
            result_bytes = bytes([ord(curcode)]) + result_bytes
            val //= base
        result_string = ''.join([chr(y) for y in result_bytes])
        return result_string

curcode = code_string[val % base]
→From remainder of argument "val" specify element of argument "code_string".
result_bytes = bytes([ord(curcode)]) + result_bytes
→It stores bytecode of Base 58 to "result_bytes" in order until "val > 0".
result_string = ''.join([chr(y) for y in result_bytes])
→Convert numbers to strings and coupling them.

Base58check encoding
Base58check encoding specially made for Bitcoin.
It use when necessary to convert binary string into format that can be read and written by a person.
Bitcoin's Base58 alphabet as shown below.

'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

Only added one line to the "checksum" code of above.

def bin_to_b58check(inp):
        inp = bytes([0]) + inp
        checksum_prefix = hashlib.sha256(hashlib.sha256(inp).digest()).digest()
        leadingzbytes = 0
        for x in inp:
            if x != 0:
                break
            leadingzbytes += 1
        checksum = checksum_prefix[:4]
        return '1' * leadingzbytes + encode(decode(inp+checksum, 256), 58)

encode(decode(inp+checksum, 256),58)
→ The binary data(Add B behind A) replace from hexadecimal to 58-ary.
leadingzbytes += 1
→It is necessary to record empty byte of leading.
→So put "1" as many as number of empty bytes in head.

Remove all ads

Public key

Overview
Public key indicate to destination of funds.
The public key is private key encrypted with elliptic curve cryptography.

Public key example
0458e0d3f7cd6d54347a25523dee480199e59541d849abcd4223538397ded94
e30f4f10af03bb48a1af2051c529f4ff1a84042f59a266ba028916c54570766162b

※x04 (prefix)+ 64 digits(x-coordinate) + 64 digits(y-coordinate)

Jacobi coordinates
To present elliptic curves,use to projective coordinates system instead of the affine coordinate system.
By using projective coordinate system, division operation becomes unnecessary.
Also, use the jacobian coordinate system instead of the projective coordinate system (suitab for multiplication operating)

secp256k1 parameter
"secp256k1" is parameters of the ECDSA curve used in Bitcoin.

P = 2**256 - 2**32 - 977
A = 0
B = 7
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
G = (Gx, Gy)


Modular multiplicative inverse
Division of modular arithmetic calculate to use modular reciprocal.

def inv(a, n):
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        r = high//low
        nm, new = hm-lm*r, high-low*r
        lm, low, hm, high = nm, new, lm, low
    return lm % n 


Jacobian coordinate
Define x, y, z as follows in elliptic curve of jacobian coordinate.

def to_jacobian(p):
    o = (p[0], p[1], 1)
    return o


Multiplication formula
In jacobian coordinate system,scalar multiplication formula in multiplication point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

s = 4*X1*Y1^2
m = 3*X1^a*Z1^4
T = -2*s + m^2

X3 = T
Y3 = -8*Y1^4 + m(s - T)
Z3 = 2*Y1*Z1

def jacobian_double(p):
    if not p[1]:
        return (0, 0, 0)
    ysq = (p[1] ** 2) % P
    S = (4 * p[0] * ysq) % P
    M = (3 * p[0] ** 2 + A * p[2] ** 4) % P
    nx = (M**2 - 2 * S) % P
    ny = (M * (S - nx) - 8 * ysq ** 2) % P
    nz = (2 * p[1] * p[2]) % P
    return (nx, ny, nz)


Addition formula
In jacobian coordinate system,addition formula in addition point R(X3, Y3, Z3) of point P(X1, Y1, Z1) and point Q(X2, Y2, Z2) is as follows.

U1 = X1*Z2^2
U2 = X2*Z1^2
S1 = Y1*Z2^3
S2 = Y2*Z1^3
H = U2 - U1
r = S2 - S1

X3 = -H^3 - 2*U1*H^2 + r^2
Y3 = -S1*H^3 + r*(U1*H^2 - X3)
Z3 = Z1*Z2*H

def jacobian_add(p, q):
    if not p[1]:
        return q
    if not q[1]:
        return p
    U1 = (p[0] * q[2] ** 2) % P
    U2 = (q[0] * p[2] ** 2) % P
    S1 = (p[1] * q[2] ** 3) % P
    S2 = (q[1] * p[2] ** 3) % P
    if U1 == U2:
        if S1 != S2:
            return (0, 0, 1)
        return jacobian_double(p)
    H = U2 - U1
    R = S2 - S1
    H2 = (H * H) % P
    H3 = (H * H2) % P
    U1H2 = (U1 * H2) % P
    nx = (R ** 2 - H3 - 2 * U1H2) % P
    ny = (R * (U1H2 - nx) - S1 * H3) % P
    nz = (H * p[2] * q[2]) % P
    return (nx, ny, nz)

Double-and-add
About multiplication of elliptic curve,the most simple way to calculation method is repeated addition.
But this calculation method not realistic,because calculation amount increase exponential.
So use to "Double-and-add" method.

def jacobian_multiply(a, n):
    if a[1] == 0 or n == 0:
        return (0, 0, 1)
    if n == 1:
        return a
    if n < 0 or n >= N:
        return jacobian_multiply(a, n % N)
    if (n % 2) == 0:
        return jacobian_double(jacobian_multiply(a, n//2))
    if (n % 2) == 1:
        return jacobian_add(jacobian_double(jacobian_multiply(a, n//2)), a)   

It's branch by remainder value obtained by dividing n to B,
「0」is executed "double(multiple)",「1」is execute "double" and "add".
Repeat until "n" became 0 or 1.



Elliptic curve coordinate of jacobian coordinate system
Coordinate(x,y) defined as following in jacobian coordinate.
x = X / Z^2
y = Y / Z^3

def from jacobian(p):
    z = inv(p[0], P)
    return ((p[0] * z**2) % P, (p[0] * Z**3) % P)


Get public key coordinate
Find coordinate(x, y) of public key, with argument "base point G" and "private key (decoded_private_key)".

def fast_multiply(a, n):
    return from_jacobian(jacobian_multiply(to_jacobian(a), n))
public_key = fast_multiply(G, decoded_private_key)
print(public_key)


Make public key
Add prefix"04" to coordinate(x, y) of public key,it's genuine " Public key".

def encode_pubkey(pub):
    return "04" + "%x"%public_key[0] + "%x"%public_key[1] 
hex_encoded_public_key = encode_pubkey(public_key)
print (hex_encoded_public_key)
Remove all ads