### Present Remotely

Send the link below via email or IM

• Invited audience members will follow you as you navigate and present
• People invited to a presentation do not need a Prezi account
• This link expires 10 minutes after you close the presentation

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

# Session 7

No description
by

## Jimmy Song

on 7 December 2018

Report abuse

#### Transcript of Session 7

Day 1
Day 2
Elliptic Curve Cryptography
Transaction Parsing
Blocks
SPV
Transaction Construction

SCRIPT
Foundational Math
Session 7 Objectives
Learn Merkle Trees
Learn Network Messaging
Learn Node Communication
Learn Merkle Blocks
Merkle Trees
Merkle Blocks
Node Communication
Network Messaging
What is a Merkle Tree?
Structured as a full binary tree.
Computer Science structure useful for proving something belongs in a set without knowing the whole set.
An efficient way to combine a lot of things into a single hash.
Calculating a Merkle Tree
Given a list of items, hash them all using a hash function (bitcoin uses double-SHA256)
Continue until you only have a single hash
You should have half the number of hashes as before.
Pair them and if there’s an odd number, duplicate the last one so it has a pair.
Hash the pair together to get the parent.
Calculating the Merkle Parent
Take each hash and concatenate them.
Hash the result to get the parent.
from helper import double_sha256

tx_hash1 = bytes.fromhex('c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5')

merkle_parent = double_sha256(tx_hash0+tx_hash1)
Exercise 6
1. Calculate the merkle parent of these hashes

f391da6ecfeed1814efae39e7fcb3838ae0b02c02ae7d0a5848a66947c0727b0

3d238a92a94532b946c90e19c49351c763696cff3db400485b813aecb8a13181

2. Write the merkle_parent function

Pair up the hashes
The list of Merkle Parents is the Merkle Parent Level
Calculate the Merkle Parent for each pair
Merkle Parent Level
Duplicate the last element
If there is an odd number of elements on a level:
Append to end of the list
Example
from helper import double_sha256, flip_endian, merkle_parent
hex_hashes = [
...
]
hashes = [bytes.fromhex(x) for x in hex_hashes]
if len(hashes) % 2 == 1:
hashes.append(hashes[-1])
parent_level = []
for i in range(0, len(hex_hashes), 2):
parent = merkle_parent(hashes[i], hashes[i+1])
print(parent.hex())
parent_level.append(parent)
Exercise 7
1. Calculate the parent level given these hashes

68b3e2ab8182dfd646f13fdf01c335cf32476482d963f5cd94e934e6b3401069 43e7274e77fbe8e5a42a8fb58f7decdb04d521f319f332d88e6b06f8e6c09e27

2. Write the merkle_parent_level function

Finding the Merkle Root
We have got the Merkle Root
Repeat until we get the Merkle Root
Otherwise, calculate the Merkle Parent Level from current list of hashes.
If there is exactly one element:
Example Merkle Root Calculation
from helper import double_sha256, merkle_parent_level
hex_hashes = [
...
'b13a750047bc0bdceb2473e5fe488c2596d7a7124b4e716fdd29b046ef99bbf0',
]
current_level = [bytes.fromhex(x) for x in hex_hashes]
while len(current_level) > 1:
current_level = merkle_parent_level(current_level)
print(current_level[0].hex())

Exercise 8
1. Get the merkle root for these hashes:

42f6f52f17620653dcc909e58bb352e0bd4bd1381e2955d19c00959a22122b2e
94c3af34b9667bf787e1c6a0a009201589755d01d02fe2877cc69b929d2418d4
959428d7c48113cb9149d0566bde3d46e98cf028053c522b8fa8f735241aa953
a9f27b99d5d108dede755710d4a1ffa2c74af70b4ca71726fa57d68454e609a2
766900590ece194667e9da2984018057512887110bf54fe0aa800157aec796ba
921b8cfd3e14bf41f028f0a3aa88c813d5039a2b1bceb12208535b0b43a5d09e
15535864799652347cec66cba473f6d8291541238e58b2e03b046bc53cfe1321
1c8af7c502971e67096456eac9cd5407aacf62190fc54188995666a30faf99f0
3311f8acc57e8a3e9b68e2945fb4f53c07b0fa4668a7e5cda6255c21558c774d

2. Write the merkle_root function
Merkle Root for Blocks
The final Merkle Root is interpreted in little-endian order
All transaction hashes are put in little-endian order
Example Block Merkle Root Calculation
from helper import double_sha256, merkle_parent_level, merkle_root
tx_hex_hashes = [
'42f6f52f17620653dcc909e58bb352e0bd4bd1381e2955d19c00959a22122b2e',
...
]
current_level = [bytes.fromhex(x)[::-1] for x in tx_hex_hashes]
print(merkle_root(current_level)[::-1].hex())
Exercise 9
1. Validate the merkle root for this block on Testnet:

0000000000000451fa80fcdb243b84c35eaae215a85a8faa880559e8239e6f20

2. Write the validate_merkle_root method

Why is a Merkle Tree useful?
SPV is very useful where you don’t have room for the entire blockchain (100 GB+ and counting)
You can prove a hash is in the tree without knowing the whole tree!
Very useful for thin-clients using something called Simplified Payment Verification (SPV)
Merkle Parent
Merkle Parent Level
Merkle Root
Merkle Root in Blocks
Merkle Blocks
What is a Merkle Block?
Depth First Ordering of hashes
Example Creating a Merkle Tree
Merkle Block Processing
Example of Populating and Navigating a Merkle Tree
from helper import merkle_parent_level

hex_hashes = [...]
tree = MerkleTree(len(hex_hashes))
tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
tree.nodes[3] = merkle_parent_level(tree.nodes[4])
tree.nodes[2] = merkle_parent_level(tree.nodes[3])
tree.nodes[1] = merkle_parent_level(tree.nodes[2])
tree.nodes[0] = merkle_parent_level(tree.nodes[1])

Node Communication Basics
Being overhauled by Corey Fields
NOT Consensus Critical!
The bitcoin network is a broadcast network
Once connected, nodes can discover other nodes and connect to them.
Nodes initially connect to other known bitcoin nodes (hard coded into core)
Network Message Structure
Command - String that identifies the command (e.g. “version”), 12 bytes
Checksum - First 4 bytes from a double-sha256 of the payload
Magic - This is always 0xf9beb4b9 to identify the network, 4 bytes
Length - Length of the payload, 4 bytes, little endian
Example Network Messages
version
verack
inv
getdata
notfound
ping

tx
block
merkleblock
pong
Version Message Parsing
Exercise 1
1. Parse this message:

f9beb4d976657261636b000000000000000000005df6e0e2

2. Write the parse and serialize methods
Exercise 3
1. Write the serialize method for GetHeadersMessage

2. Write the parse method for HeadersMessage
Network Messaging
Network Handshake
Node A
Node B
Wants to connect to B
Open to new connections
Node A
Node B
Sends version message

Node A
Node B
Sends verack message
Sends version message

Node A
Node B

How do you process the Merkle Block Proof?
If flag is 1 and is a leaf node, this is a hash the block is proving is included (green box)
Flag Bits
[1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0] and 7 hashes
import math

total = 16
max_depth = math.ceil(math.log(total, 2))
merkle_tree = []
for depth in range(max_depth+1):
num_items = math.ceil(total / 2**(max_depth - depth))
level_hashes = [None] * num_items
merkle_tree.append(level_hashes)

for level in merkle_tree:
print(level)

Block data that proves certain transactions are in the block (proof of inclusion)
Defined in BIP0037
The nodes of the merkle tree are processed depth-first
Each node has a flag assigned to it, 0 or 1
If flag is 0, this is a node whose hash is being
given
(blue box)
If flag is 1 and is not a leaf node, this is an internal node whose hash is being
computed
(dotted box)
Flag Bits
[1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0] and 7 hashes
Example of a Different Way of Populating a Merkle Tree
hex_hashes = [...]
tree = MerkleTree(len(hex_hashes))
tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
while tree.root() is None:
if tree.is_leaf():
tree.up()
else:
left_hash = tree.get_left_node()
right_hash = tree.get_right_node()
if left_hash is None:
tree.left()
elif right_hash is None:
tree.right()
else:
tree.set_current_node(merkle_parent(left_hash, right_hash))
tree.up()
print(tree)
Example of Populating a Merkle Tree
tree = MerkleTree(len(hex_hashes))
tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]
while tree.root() is None:
if tree.is_leaf():
tree.up()
else:
left_hash = tree.get_left_node()
if left_hash is None:
tree.left()
elif tree.right_exists():
right_hash = tree.get_right_node()
if right_hash is None:
tree.right()
else:
tree.set_current_node(merkle_parent(left_hash, right_hash))
tree.up()
else:
tree.set_current_node(merkle_parent(left_hash, left_hash))
tree.up()
print(tree)
Exercise 4
1. Write the handshake method.
Handshake Example
from network import SimpleNode, VersionMessage

node = SimpleNode('tbtc.programmingblockchain.com', testnet=True, logging=True)

node.send(b'version', VersionMessage().serialize())
print(node.wait_for_commands([b'verack']))
Exercise 2
1. Write the serialize method for VersionMessage
node = SimpleNode('btc.programmingblockchain.com', testnet=False)
node.handshake()
last_block_hash = GENESIS_BLOCK_HASH
count = 1
for _ in range(20):
if not block.check_pow():
raise RuntimeError('bad proof of work at block {}'.format(count))
if last_block_hash != GENESIS_BLOCK_HASH and block.prev_block != last_block_hash:
raise RuntimeError('discontinuous block at {}'.format(count))
count += 1
last_block_hash = block.hash()
if count % 2016 == 0:
print(block.hash().hex())