Bitcoin blog

The essence of Bitcoin is innovation that be related to remittance, asset holding rights, liberation, and freedom.

Mining

Overview
The Mining has two meanings.

・Currency supply mecanism
・Decentralized emergent consensus


①Currency supply mechanism
At a point of jan 2009, Remuneration of mining for 1 block was 50BTC. In other word, mining means that supply new bitcoin to network.Mining reward is designed to reduce by half in 210,000 blocks (about 4 years).In 2140, it will reaches upper limit of 20,999,999,98bitcoin (13.44M block). If the reward is less than 1 satoshi, the reward for mining is lost.

f:id:adrenaline2017:20170614134249j:plain


The total number of Mining reward
Code to calculate how much the upper limit issue quantity.

#primary miners reward
start_block_reward = 50
#reward is halved every 210,000 blocks
reward_interval = 210000

#upper limite number
def max_money():
    current_reward = start_block_reward * 10 ** 8
    total = 0
    
    while current_reward > 0:
        total += reward_interval * current_reward
        current_reward /= 2
    return total

print("Total BTC to ever be created:", max_money(), "Satoshis")


②Decentralized emergent consensus
Participating node in the Bitcoin network reach a global consensus based on public ledger (blocking chain) without Centralized trust model. This is Bitcoin revolutionary invention that is dispersive mechanism to decentralized emergent consensus.The consent obtained by asynchronous interaction is established by node who following below rules.

・Verification of independent transaction
・Accumulation of independent transaction
・Verification of independent new block and blockchain transmission
・Select of independent blockchain


1.Verification of independent transaction
It is verified whether valid transaction.

・Is the transaction grammar and structure correct?
・Input and output is not empty?
・transaction data size does not over define upper limit of block size?
・Output value and Total value in the range of 0-21,000,000BTC?
・Input is not coinbase tranzaction(hash=0, N=-1)?
・”nLockTime” is lower than 31bit?
・transaction data size ≧100?
・Do not over upper limit of signature operation times?
・scriptSig can push the number to stack?
・scriptpub in isStandard format?
・Same transaction exist in the transaction pool or main branch blockchain block?
・Input is not referring to the output referred to from other transactions in the transaction pool?
・In the case of input refer to output that is coinbase transaction, number of conformation is not over than 100?
・Output referred to by input does not already used?
・Sum of each input is in the range of 0-21,000,000bitcoin?
・Sum of inputs smaller than the sum of output?
・ScripSig can unlock to corresponded scriptPub?


2.Accumulation of independent transaction
Mining nodes do not only add to memory pool and transaction pool after transaction verification, this transaction is collected to candidate block.

Priority of transaction processing
Elements related to priority of transaction
・Transaction age
・Transaction fee
・Input value of transaction size
※transaction age;The number of blocks that have elapsed since the UTXO was recorded on the blockchain

Calculation of priority is as follow

Priority = Sum (Value of input * input age ) / Transaction size

High Priority is necessary larger than 57,600,000 of priority

High Priority > 100,000,000 satoshis * 144 block / 250 byts = 57,600,000

Priority

Priority(Even if no fee) > Transaction fee/Transaction data size  > No fee

Validity period of transactions
Valid transactions have no deadline. But, If the transaction sent to the network is not transmitted to the whole, it needs to be sent again. Because, Memory pool of mining node is temporary storage.

Generation transaction
It is said that “coinbase transaction”. It is the reward you get when the mining is successful.For get remuneration,the miner generate "generation transaction" as payment of own wallet. This transaction is special and does not have UTXO in the input.Instead, the transaction has an input called coinbase.The output is a script that sends remuneration (mining remuneration and fee) to miner's address.

Constraction
Transaction hash does not have refering previous hash, Instead it fill with 0 of 32 bytes.All Output index is set to 0xFF (255), and scriptSig is a free field (coindase data) which minor can use arbitrarily.
f:id:adrenaline2017:20170614144925j:plain

Coinbase data
As defined in BIP0034 when version is "2", block hight must include in Coinbsae data.

For example,when scriptSig is...

03443b0403858402062f503253482f

03:
push 3byte to stack
443b04:
It means block hight 277,316 (little endian )
0385840206:
extra nonce
2f503253482f:
defined in BIP0016 support P2SH


Proof of work algorithm
Change the value of nonce, hash the block header with SHA256 and continue to calculate until it falls below the target value.

Characteristic of hash value with SHA256
・If input changes even for one character, the value output is completely different.
・If input is same, the same output will be returned no matter how many times calculated (anyone can check it).
・Input value can not calculate from output value.

The way to find a value smaller than the target only is only by brute force.So this work is called trust work.Verification of work is very easy. Just compare the hash value of the block header containing the answer of nonce.

Simple code to explain proof-of-work algorithm

import binascii
import hashlib
import time

max_nonce = 2 ** 32 

def proof_of_work(header, difficulty_bits):
    #When "difficulty_bits" value increase,"target" value decrease and up to difficulty
    target = 2 ** (256-difficulty_bits) 
    
    #nonce is 0 to 4294967296
    for nonce in range(max_nonce):
        #header + nonce = 'test block with transactions0, 1, 2...'
        hash_result = hashlib.sha256(header.encode('utf-8') + str(nonce).encode('utf-8')).hexdigest()
        
        # check if this is a valid result, below the target
        if int(hash_result, 16) < target:
            print ("Success with nonce %d" % nonce)
            print ("Hash is %s" % hash_result)
            return (hash_result,nonce)
            
    print ("Failed after %d (max_nonce) tries" % nonce)
    return nonce

    
if __name__ == '__main__':
    
    nonce = 0
    hash_result = ''
     
    # difficulty from 0 to 31 bits
    # Increase "difficult_bits" one by one   
    # change "nonce"value until you enter traget range.
    for difficulty_bits in range(32):
        difficulty = 2 ** difficulty_bits
        print ("Difficulty: %ld (%d bits)" % (difficulty, difficulty_bits))
    
        print ("Starting search...")
        
        # checkpoint the current time
        start_time = time.time()
        
        # make a new block which includes the hash from the previous block
        # we fake a block of transactions - just a string
        new_block = 'test block with transactions' + hash_result 
        
        # find a valid nonce for the new block
        (hash_result, nonce) = proof_of_work(new_block, difficulty_bits) 
        
        # checkpoint how long it took to find a result
        end_time = time.time()
        
        #Time to proof of work
        elapsed_time = end_time - start_time
        print ("Elapsed Time: %.4f seconds" % elapsed_time)
        
        
        if elapsed_time > 0:
            # estimate the hashes per second
            hash_power = float(int(nonce)/elapsed_time)
            print ("Hashing Power: %ld hashes per second" % hash_power)

Calcurate of target
whether nonce is right answer, blockhash will attain an objective depend on whether.Specifically, when block hash containing the value of certain nonce falls below the target value.The equation is as follows.

target value =(low of bit 3byte)* 2 ^ (8*( upper of bit 1byte - 3))

Let's calculate the target with block number 285566 as an example!

①Bits of block number “285566” is 419537774
②hexadecimal of 419537774 is ”1901a36e”
③lower 3 byte of bit is 0x01a36e
④Upper 1 byte of bit is 0x19(in the case of decimal 25)
⑤Substitute ① to ④ for above formula
⑥Check to calculated value is lower than the hash of block285566
※The hash of block number 285566 is "000000000000000149c7840096f76475d018ed0c05f1a688e608b8254a39d796"

#target calculate function
def target(bits):
    hexadecimal_bits = '%x' % int(bits)
    upperbits = hexadecimal_bits[:2]
    lowerbits = hexadecimal_bits[2:]
    upperbits = int(upperbits, 16)
    lowerbits = int(lowerbits, 16)
    target_value = lowerbits * 2 ** (8 * (upperbits - 3))
    number =64 - len('%x' % int(target_value))
    target = (number * "0") + '%x' % int(target_value)
    return(target)

#Bits of block number “285566” is...
bits = "419537774"
target_value = target(bits)

#Hash of block number "285566" is...
hash = "000000000000000149c7840096f76475d018ed0c05f1a688e608b8254a39d796"

#It can see that the hash is smaller than target_value
target_value > hash

Calculate of difficulty
Difficulty is indicator of the difficulty of finding the target block hash.

difficulty=upper limit value of target / current target

Let's calculate about difficulty of block number43420(Ask for difficulty 3.78)!
①Calculate current target
※bits of block number43420 is 474199013(hexadecimal 1c43b3e5)
②Next, calculate upper limit value of target
※The upper limit value of the target is defined as constant 0x1d00ffff
③Finally,by difficulty=upper limit value of target / current target

#target calculate function
def target(bits):
    hexadecimal_bits = '%x' % int(bits)
    upperbits = hexadecimal_bits[:2]
    lowerbits = hexadecimal_bits[2:]
    upperbits = int(upperbits, 16)
    lowerbits = int(lowerbits, 16)
    target = lowerbits * 2 ** (8 * (upperbits - 3))
    return(target)

#calculate about target of block number43420
bits = "474199013"
current_target = target(bits)

#The upper limit value of the bits is defined as constant 0x1d00ffff
upper_bits = int("1d00ffff", 16)
upper_target = target(upper_bits)

#Formula to calculate difficulty
difficulty= upper_target / current_target

print(difficulty)


3.Verification of independent new block and blockchain transmission
The node Independently verification whether effective block ,before new generated block sent to other node.
Whether valid chack it with below lists.

・Is the block's data structure and syntax valid?
・Block header hash value is smaller than target?
・Time Stamp of block is earlier than 2 hours later of the node's time?
・Block size is with in range?
・First transaction is "coinbase generation transaction"?
・The transaction included in the block satisfy the transaction rule?
※Invalid blocks are repelled by other nodes based on this rule.


4.Select of independent blockchain
The node rebuilds the new block by connecting it to the existing block chain.The node has three kinds of block set.

main blockchain
This is the chain with the most ”difficulty” accumulation. In other words, it can be said to be a chain with the most blocks.
Sometimes it has a branch of sibling block. when the branch exceeds "difficulty" of main blockchain in the future,This keeps it to be replaced by the main.

secondary blockchain
It is said that Fork.The fork occur when different nodes mined same block.Some times,there are times when new block extended except with main chain.

orphan
If a parent is not found in an existing chain even if it receives a valid block from another node, it becomes an orphan block and is retained in the orphan block pool.
The oprhan block occurs when the order of blocks mined almost simultaneously is received in reverse.

extra noce
Extra nonce is included in the coinbase transaction which is a transaction paying a minor reward.
In the early days difficulty target was low, so it was possible to find a hash value lower than target with 400 million nonces.Updated the Time Stamp and discovered a hash value lower than the target by obtaining a hash value.But, as difficulty got better, 400 million nonces were used up within 1 second, and more space was needed to find effective blocks.so,using 2 - 100 byte data space of coinbase transaction it became possible to calculate in a larger range.

Remove all ads

Blockchain

Overiew
Blockchain is transaction database shared by all nodes participating in system based on Bitcoin protocol. The full copy of blockchain contains every transaction ever executed in the currency.With this information, one can find out how much value belonged to each address at any point in history.
f:id:adrenaline2017:20170602105140j:plain


Block structure
A block is like a data container of transaction, and it consists of a block header and a list of transactions. The block header is used to calculate the block hash. Specifically, it can be calculated by double-hashing(SHA256) the block header. The capacity of the block header is about 80 byte, whereas one transaction is approximately 250 byte. And since there are 500 or more transactions included in one block, it reaches about 125,000 byte. That is, the transaction has a capacity of 1000 times or more of the block header!

f:id:adrenaline2017:20170602165638j:plain


Block header
The block header is composed of the following contents.
①Version(4byte):Verification rule of block
②Previous block(32byte):A thing to connect with Previous block and next block
③Time stamp(4byte), difficulty(4byte), nonce(4byte):involved to mining
④Merkle tree(32byte):A data structure used for collecting transactions in block efficiently


Block hash
The block hash is not included in block's data, when block is released to network or stored in the storage as part of block chain.It is calculated at each node when it arrives at the node from the network.It is stored in the database of each node as a part of the block's metadata, and it is used for retrieving and indexing blocks.


Derivation of block hash
Calculate block hash by referring to this site.

f:id:adrenaline2017:20170602145814j:plain

1. BlockVersion and PreviousBlocHash and BlockMerkleRoot convert to Little-Endian
2. BlockTime convert to Unix Time → Convert to hexadecimal → Conver to Little-Endian
3. BlockBits and BlockNonce convert to hexadecimal → Conver to Little-Endian
4. Connect 1, 2, 3 in order
5. Calcurate double hash value with SHA256 to ④
6. Convert this value to Big-Endian

import hashlib
import binascii
import re

#little edian function
def endian(src):
    scr = ''.join(re.split('(..)',src)[1::2][::-1])
    return scr

#block data(from blockchain info)
block_version = "00000004"
previous_block_hash = "0000000000000000005629ef6b683f8f6301c7e6f8e796e7c58702a079db14e8"
block_merkle_root = "efb8011cb97b5f1599b2e18f200188f1b8207da2884392672f92ac7985534eeb"
block_time = "2016-01-30 13:23:09"
block_bits = "403253488"
block_nonce = "1448681410"

#convert little endian
block_version       = endian(block_version)
previous_block_hash = endian(previous_block_hash)
block_merkle_root   = endian(block_merkle_root)

#convert GMT to unix
from datetime import datetime
block_time = int((datetime.strptime(block_time, "%Y-%m-%d %H:%M:%S")-datetime(1970,1,1)).total_seconds())
block_time = endian(format(block_time,"x"))

#convert decimal to hexadecimal
block_bits = endian('%x' % int(block_bits))
block_nonce = endian('%x' % int(block_nonce))

#block header
block_data = block_version + previous_block_hash + block_merkle_root + block_time + block_bits + block_nonce

#calcurate 
hash = hashlib.sha256(hashlib.sha256(binascii.a2b_hex(block_data)).digest()).digest()
hash = endian(binascii.b2a_hex(hash).decode('utf-8'))
print(hash) 


Block height
"Block Height" means the hight of stacked of block.For example,when block hight is "29500", it expressing that the block processed at 29500th from beginning.The block height does not include in part of the data of block.So,the node don't judge place of block in the blockchain from "block height"."Block height" is saved as metadata in data base.


Genesis block
First block of the blockchain is called "Genesis block" and it was made in 2009.As the word "Genesis" implies, it eventually return to genesis block even if any block.Every block contains a hash of the previous block. By This structure,it has the effect of creating a chain of blocks from the genesis block to the current block. This ensures the safety of the block chain.

f:id:adrenaline2017:20170604185210j:plain


Concatenation of blocks
Full node client maintains local copy of block chain that continues from genesis block.The client is periodically updated every time new block is found.When the nodes receive block from Bitcoin network, node verifies block and connects to the blockchain already held.


Fork
The fork is phenomenon where different blocks are found by different minors almost at the same time and the chain branches.However, since longer chain is adopted and shorter one is discarded, it is solved when one child block becomes part of the blockchain at certain timing.Generally, the more times network approve it, the more reliable it is. When more than six times are approved,it would be almost certainly.


Merkle tree
Part of the block contains Merkle tree information.Merkle tree contains an overview of all transactions in the block.The tree is also called "binary hash tree", it can efficiently compile large data and verify the whole data."Tree" represents data structure with leaf, with upper direction being root and lower direction being leaf.

Function of Merkle tree
① Merkle tree is used to compile all the transactions included in the block
② Create digital fingerprint of the entire transaction (hashed digital information)
③ It helps to confirm efficiently whether a transaction is included in the block

f:id:adrenaline2017:20170604214105j:plain


Calcurate of Merkle tree
1. If there is a hash of two transactions in the block
2. Convert each hash value to Little Endian
3. Connect the hash value of 2 directly
4. Convert 3 to a binary string and double hash the SHA 256
5. Convert 4 to Big Endian
※If there are no hash pairs, duplicate myself.

import hashlib
import re
import binascii

#edian function
def endian(src):
    scr = ''.join(re.split('(..)',src)[1::2][::-1])
    return scr

transaction_hash1 = "e909043fa259d7a36c4e868cb0e4fc2ed589384c1766705d0c4e132117fc207d"
transaction_hash2 = "e6d51744d77bd69a00acc42c322b2aeeec80ee6fcce7bb371fb0239ad2865fd2"

#convert to little endian
transaction_hash1 = endian(transaction_hash1)
transaction_hash2 = endian(transaction_hash2)

#connect to hash1 and hash2
transaction_hash = transaction_hash1 + transaction_hash2

#double hash with SHA256
hash = hashlib.sha256(hashlib.sha256(binascii.a2b_hex(transaction_hash)).digest()).digest()
hash = endian(binascii.b2a_hex(hash).decode('utf-8'))
print(hash)


Merkle root
Merkle tree computes one hash value from a pair of leaf nodes,and continue calculation with pairs until one hash value. Last remaining value is called "Merkle route".One block has several hundreds to several thousands of transactions, but eventually it becomes 32byte hash on Merkle route.Regardless of how many transactions,it does not change.
In order to prove whether a particular transaction is included in a block, it is enough to create hashes of log 2 (N) . As shown in the figure below.


f:id:adrenaline2017:20170605110043j:plain


Effect of Meekle root
The block capacity is only 4 KB in 16 transactions, but in 65,535 transactions the block capacity is 16 MB (16,000,000 bytes) .In the case of Merkle path,the block capacity is 128 bytes in 16 transactions,in 65,535 transactions the block capacity is 512 bytes .It can save 1 / 31,250 times the capacity by using Merkle path.

f:id:adrenaline2017:20170605121139j:plain


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

Remove all ads

Network

Overview
Bitcoin is builded as peer-to-peer(P2P) network on internet. P2P network is essentially decentralize and open. This network is formed by connecting mutually equal nodes. we calling computer terminal participating in the network as “node”, and Bitcoin network means that entire note running the P2P protocol. This node can be divided into several roles according below.


Node type
The Bitcoin node is collection of functions such as routing, block chain database, mining, and wallet.

Wallet
User wallet has two types of full node and SPV node.
Miner
Mining nodes are competing to create new blocks.
Full blockchain
It refers to full node with a complete blockchain.
Routing node
All nodes must have routing function in order to join the network.


Extended network type
It shows the main type on the extended Bitcoin network.
f:id:adrenaline2017:20170620165104j:plain


Join the network
When new node launch, the node must find another node to join Bitcoin network. And this node has to find and connect at least one node. Geographical location of other nodes is irrelevant. Becouse topology of Bitcoin network isn't desided in reration to geography. The node can be randomly chosen.

①The node establish TCP conection(use port 8333)
TCP (Transmission Control Protocol):It is a standard protocol used to realize reliable communication in the Internet.

②Stand up to New node(It find and connect at least one node)

③Contact DNS server (DNS seed provide IP address of Bitcoin node)
DNS(Domain Name System):It tells IP address based on hostname.

④ As soon as establishing a connection, the node sending“version message”
version message:It include basic Identification information

⑤The peer node returns " verack " to acknowledge the connection and establish it
verack:It inform that trying to connect

⑥When the node establish one or more connections, New node sends "addr message" to the adjacent node
addr message: It include IP address

⑦Adjacent nodes communicate "addr message" to another adjacent nodes one after another

⑧Also, when send "getaddr" to adjacent node
getaddr:It get to return IP address of other peer

⑨The node connects to plurality of different peers

⑩node must always keep finding new node


Full node working
Full node is node managing a complete blockchain including all transactions.

①Full node sends to “version message”
version message:It is included to“Bestheight”that shows current blockchain hight of node

②By looking at "version messages", the nodes know how many peers the peer holds and can compare with our own blockchains

③Then the peer node exchanges "getblocks message" containing the top block hash (fingerprint) of each other local blockchain

④The node can compare with the hash of other node and identify which block the other node wants

⑤Identify the first 500 blocks to share with other nodes
"inv message" include in this infomation

⑥Send “inv message” to other node

⑦Pick a hash of missing blocks and request "getdata messages" to be sent full block data

※The node keeps track of how many blocks per peer are still in the "transmitting" state that has not yet been sent.
※It continues checking so that it does not exceed the maximum number of blocks during transmission for one peer.


Simplified payment verification
As Bitcoin grows in usage the datasize amount needed to download blocks and transaction broadcasts increases. All notes can't hold a full blockchain. The data size problem occer when running Bitcoin wallet on low spec machin like smartphone. Convenience will be lost unless irrelevant transactions are discarded and block chains are not synchronized quickly. The SPV is used so that network processes can be executed without holding a full blockchain.

Solution method
The SPV node downloads only the block header and does not download transaction. It only validates all blockchains and transactions associated with this SPV node. So the SPV node can't verify that UTXO is not in use.
Instead, the SPV node uses merkle path to tie the transaction to block containing this transaction. The SPV node can check existence of the transaction in the block by requesting the stead node for merkle path certification and by verifying the proof of work in blockchain.

※The SPV node can prove that the transaction exists reliably, but it can not verify whether there is a transaction like dual use of the same UTXO.So the SPV node needs to be connected randomly to several nodes.


What is Bloom filter?
With the protocol extension proposed in BIP0037,SPV client can efficiently download only transactions related to myself address by using "Bloom filter".Bloom filter operates at a very high speed and is a data structure that can probabilistically determine whether an element is included in a set.
"Stochastic" means that sometimes to say "Although do not included,it contains",but it does not say "despite being included in it, not included" .
※there is a false positive but false There is no negative


How does Bloom filter work?
①Initialize bloom filter with empty state
f:id:adrenaline2017:20170614104547j:plain

②Create list of all the addresses the wallet has

③Create a search pattern for each Bitcoin address

④These search patterns are passed through a hash function to obtain a number between 1 and N

⑤Find bits in the bit string corresponding to this number and set "1"
f:id:adrenaline2017:20170614105534j:plain

⑥It will do this further by the number of the pattern(already remains 1 stands place where 1)
f:id:adrenaline2017:20170614105741j:plain
※Accuracy decreases as the number of patterns increases.Conversely, the larger the size (N) of the bit string and the number (M) of hash functions, the more accurate it becomes.Using larger bit strings and more hash functions makes more accurate.

⑦bloom fliter send to peer

⑧The peer uses sent bloom filter to find out which transaction matches the search pattern

⑨Use bloom filter to check pattern "X" exists.
If the place where the bit pattern is "1" is the same "1" in the bit string of the bloom filter,the bit pattern may be included in the bloom filter.
f:id:adrenaline2017:20170614110042j:plain

⑩Conversely, to check that a pattern is not included in the bloom filter, make sure that any one of the bit strings of the corresponding bloom filter is 0.
f:id:adrenaline2017:20170614110312j:plain


Bloom Filter and Inventory
1.SPV node send "filterload(include bloom filter)" to peer

2.Peer chack this bloom filter

3.Peer send "transaction(only matching bloom filter)" to SPV node

4.SPV node send "getdata message" to peer

5.Peer send "merkleblock message" to SPV node
※Block header and transaction correspond to merkle path

6.Peer send "tx message" to SPV node
※Contains transactions matching "bloom filter"

Remove all ads