Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • 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
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

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

DeleteCancel

Session 7

No description
by

Jimmy Song

on 7 December 2018

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Session 7

Day 1
Day 2
Elliptic Curve Cryptography
Transaction Parsing
Advanced Topics
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_hash0 = bytes.fromhex('c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5')
tx_hash1 = bytes.fromhex('c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5')

merkle_parent = double_sha256(tx_hash0+tx_hash1)
merkle_parent.hex() # 8b30c5ba100f6f2e5ad1e2a742e5020491240f8eb514fe97c713c31718ad7ecd
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 = [
'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',
...
'2e6d722e5e4dbdf2447ddecc9f7dabb8e299bae921c99ad5b0184cd9eb8e5908',
]
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

8b30c5ba100f6f2e5ad1e2a742e5020491240f8eb514fe97c713c31718ad7ecd 7f4e6f9e224e20fda0ae4c44114237f97cd35aca38d83081c9bfd41feb907800 ade48f2bbb57318cc79f3a8678febaa827599c509dce5940602e54c7733332e7
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 = [
'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',
...
'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
62af110031e29de1efcad103b3ad4bec7bdcf6cb9c9f4afdd586981795516577
766900590ece194667e9da2984018057512887110bf54fe0aa800157aec796ba
e8270fb475763bc8d855cfe45ed98060988c1bdcad2ffc8364f783c98999a208
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',
...
'e8270fb475763bc8d855cfe45ed98060988c1bdcad2ffc8364f783c98999a208',
]
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
Payload - Actual message
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
addr
inv
getdata
notfound
ping

getheaders
tx
block
headers
merkleblock
getaddr
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
Receives version message
Sends verack message
Sends version message

Node A
Node B
Receives verack message
Receives version message

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']))
GetHeaders Message Parsing
Exercise 2
1. Write the serialize method for VersionMessage
Block Header Download Example
node = SimpleNode('btc.programmingblockchain.com', testnet=False)
node.handshake()
last_block_hash = GENESIS_BLOCK_HASH
count = 1
for _ in range(20):
getheaders = GetHeadersMessage(start_block=last_block_hash)
node.send(getheaders.command, getheaders.serialize())
headers_envelope = node.wait_for_commands([b'headers'])
headers_message = HeadersMessage.parse(headers_envelope.stream())
for block in headers_message.blocks:
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())
headers
...
Exercise 5
1. Download the first 40000 blocks for testnet and validate them.
Exercise 10
1. Validate the merkle root for this block on Testnet via network protocol:

0000000000044b01a9440b34f582fe171c7b8642fedd0ebfccf8fdf6a1810900

Full transcript