Merkle

Week 0x4.4

Announcements

• Welcome to Computing Security
  • Trees, ish
    • Heaps
    • Merkle Trees
• Action Items:
  • BTCinC

Today

• Trees, ish
  • Heaps
  • Merkle Trees
• Aside: Tx’s

Trees

\(n\)-ary Trees

• A tree is a type of graph.
• A graph is a pair of
  • A set of “nodes” or “vertices” (or “vertexes”)
  • A set of “edges” which are pairs of nodes
    • They may be ordered pairs or not.

Blockchain

• Blockchain is a 1-ary tree
  • Usually called a link(ed) list in computing
  • Sometimes called a sequence, depending on which mathematical object.

list_t

• A list_t is a 1-ary tree

mocha 2-tree

Common Case

• Usually in computing, I use trees to store “stuff”
  • In a SQL database, I used a b-tree to store… data, I guess
  • In a binary search tree, I sort elements of sets with total orders, like integers or words
  • In OS page table, I store memory locations.

Our Case

• We will store digests in nodes and transactions in leavefes.
  • So, 256 bits
• Leaves a transaction “record”

Transaction review

• Recall:
  • A bitcoin transaction and a bitcoin coin are identical
  • A coin is a chain of ownership
  • Own a coin by being the most recent owner.

Transaction review

• Recall:
  • A transaction contains:
    • A sender
    • A receiver
    • An amount.
  • A sender/receiver is not a person par se but a public key

Transaction

• Something like this:

tx.h

#define KEY_SIZE 4096 / 8 * sizeof(an_int)

typedef uint64_t an_int;

struct tx_struct {
    an_int send_n[KEY_SIZE]; /* 4096 bit sender modulus */
    an_int recv_n[KEY_SIZE]; /* 4096 bit recver modulus */
    uint64_t amount;         /* $\exists$ ~2.1 quadrillion atomics, ~2^50 */
}

In Practice

• 64 + 64 + 1 == 129
• Can’t RSA things bigger than \(n\), so must RSA in chunks
• 129 / 3 == 129 // 3 == 43
• Each 43 word block would be encrypted into a 64 word block.

tx.h

struct signed_tx_struct {
    an_int send_n[KEY_SIZE];    /* needed to decrypt */
    an_int chunks[3][KEY_SIZE]; /* 3 chunks of up to size 64 */
    uint32_t digest[8];           /* sha256 */
}

So basically

• Make a tx_struct
• Cast it to a uint64_t array
  • RSA encrypt with private key each third into chunks
  • SHA hash into digest
• Load thirds into signed_tx_struct
• Prefix with public key.

How do ensure?

• We want to have confidence in these transactions.
• Easy - hash them, and save the hashes.
• But wait - that’s a lot of hashes to hold onto…
• And it is unreasonable to store potentially thousands of hashes in each block!

Hash tree

In practice

1. Place on transaction in linear data structure, like a stack or array list
2. Hash each transaction, store the results (!!! non-trivial)
3. For each pair of hashes, compute the hash of the concatenation of the two hashes and store the results
4. Repeat until there is a single hash, the “Merkle root”

Tree Terms

• Complete

• Definition: A tree in which every level, except possibly the deepest, is entirely filled. At depth n, the height of the tree, all nodes are as far left as possible.

Tree Terms

• Perfect

• Definition: A k-ary tree with all leaf nodes at same depth. All internal nodes have degree k.

• Note: Authors differ in their definitions. This is called “complete” by [CLR90, page 95].

• I take CLR as ground truth (more often 2nd+ edition as “CLRS”)

Complete

Complete

Complete

Incomplete

Takeaway

• In a complete tree, we can always place all leafves in a linear data structure, like an array.
• In a complete binary (2-ary) tree, there will be (roughly) the same number of non-leaf and leaf nodes

Naive

• We may be tempted to do this

struct hash_tree_struct {
    uint32_t digest[8];
    struct hash_tree_struct *left;
    struct hash_tree_struct *rite;
}

• This could in fact work, mostly, but leads to some problems.
  • How do you tell if a pointer points to a leaf or not?

Today

• ✓ Trees, ish
  • Heaps
  • Merkle Trees
• ✓ Aside: Tx’s

Heap

Heaps

• To motivate our technique for Merkle trees, we are going to make a digression to the heap abstract data type, also called a priority queue.
• Vs. other graph representations, heaps can be implemented by store nodes only and deriving edges from a e.g. node’s index in an array.

Why “Priority”

• A heap is a nonlinear (but linearizable) data structure which sorts* data… kinda.
• A heap always has some minimal or maximal value, within the the collection, in its initial position, or root.

Make one

Empty Heap

• Heaps are usually based on binary trees so we’ll make an example.
• Start with an empty heap it looks like this:

• There’s nothing here

Initial Value

• Insert 128 as an initial value
• 128 is the maximium, and also the root/initial value

Insert 64

• To Insert a value, we Insert an unpopulated node that would make a complete tree of appropriate size.
• In this case, in a binary tree, the first “child” of 128

Insert 64

• Place 64 here
• 64 is \(\leq\) 128 so this is “A-OK”
  • “A-OK” is short for “Ada, Oklahoma” in honor of Ada Lovelace, the first computer scientist
  • (This isn’t true)

Insert 192

• To Insert a value, we Insert an unpopulated node that would make a complete tree of appropriate size.
• In this case, in a binary tree, the second “child” of 128

Insert 192

• Place 192 here.
• Big “uh oh”

Heapify

• We do an operation often called “heapify”
• In a loop
  • Swap new value with its parent
  • Terminate when (1) parent is greater or (2) no parent.
• So swap 192 and 128

Insert 96

• To Insert a value, we Insert an unpopulated node that would make a complete tree of appropriate size.
• In this case, in a binary tree, the first “child” of 064

Insert 96

• Place 96 here.

Heapify

• 96 \(\gt\) 64 so swap
• 96 \(\leq\) 192 so terminate

Aside: Structs

• It is possible to implement a heap like so:

struct heap_struct {
    uint8_t data;
    struct heap_struct *left;
    struct heap_struct *rite;
}

• In this case, storing these 8 bit values would require structs of size 8 + 64 + 64 = 136 bits.
• An overhead of of (136-8)/8 = 16x (or worse as 8 bits will take a 64 bit “slot”)

Aside: Arrays

• Instead, realize we always Insert new elements to the… next available position.
• This is a stack push, usually implement on top of a list or array.

typedef uint8_t *heap;

• Overhead of zero.

Use arrays

• In theory

• In practice

Insert 160

• In theory

• In practice

Insert 160

• In theory

• In practice

Heapify

• In theory

• In practice

On Indices

• Consider what happens here with respect to indices
• 160 is Inserted as the element at zero-index location 4

On Indices

• After swap, 160 is at swaps at zero-index location 1
  • No particularly clear pattern here, to me

1-Index

• 3 also would’ve swapped to 1
  • Floor/int div by 2
  • Wait, 4 -> 1 is an off-by-one int div
• Index by one (1), not zero (0).

Insert 224

1. Next index is 6.

Insert 224

1. Next index is 6
2. Insert 224 there

Heapify

1. Next index is 6
2. Insert 224 there
3. Check 3 = 6/2

Heapify

1. Next index is 6
2. Insert 224 there
3. Check 3 = 6/2
4. Swap

Heapify

1. Next index is 6
2. Insert 224 there
3. Check 3 = 6/2
4. Swap
5. Check 1 = 3/2

Heapify

1. Next index is 6
2. Insert 224 there
3. Check 3 = 6/2
4. Swap
5. Check 1 = 3/2

Heapified

1. Next index is 6
2. Insert 224 there
3. Check 3 = 6/2
4. Swap
5. Check 1 = 3/2
6. Swap

Heapified

Today

• ✓ Trees, ish
  • ✓ Heaps
  • Merkle Trees
• ✓ Aside: Tx’s

Merkle

• To create a Merkle tree, all non-leaf nodes are hashes and all leaf nodes are what the data type is.
• Store the data type in array of length \(n\)
• The tree requires \(n-1\) non-leaf nodes

Example

• Suppose these are your transactions
  • Stored in an array (or a list_t!)

Example

• In a complete binary tree, the last row is a power of 2 in size.
  • We have 6 entries, so we will need part of a row of size 8 and part of a row of size 4

Example

• Fill out the tree to get up to the 4-row.

Example

• Add additional leaves until there’s enough…

Example

• More…

Example

1. Relate transactions to leaves.

Hash Tx’s

Hash Hashes

Today

• ✓ Trees, ish
  • ✓ Heaps
  • ✓ Merkle Trees
• ✓ Aside: Tx’s

tx.h

#define KEY_SIZE 4096 / 8 * sizeof(an_int)

typedef uint64_t an_int;
typedef struct hash_struct{uint32_t digest[8];} hash_t;

struct tx_struct {
    an_int send_n[KEY_SIZE]; /* 4096 bit sender modulus */
    an_int recv_n[KEY_SIZE]; /* 4096 bit recver modulus */
    uint64_t amount;     /* $\exists$ ~2.1 quadrillion atomics, ~2^50 */
}

typedef struct signed_tx_struct {
    an_int send_n[KEY_SIZE];    /* needed to decrypt */
    an_int chunks[3][KEY_SIZE]; /* 3 chunks of up to size 64 */
    hash_t digest;              /* sha256 */
} signed_tx_truct signtx;

struct hash_tree_struct {
    size_t  num_tx;
    hash_t *merkle; /* malloc to 2 * numx_tx * sizeof(hash_t) */
    signtx *txtree; /* malloc to     numx_tx * sizeof(signtx) */
}