# Hello --- # I'm Jakub Trąd --- # How are # Merkle Trees? --- ## What's in this presentation? ---- ## 1. A small & visual theoretical introduction ---- ## 2. Semi-live coding implementation session ---- ## What's in it for you? --- # What is a # Merkle Tree ----  ----  ----  ----  ----  --- ### Applications of Merkle Trees 1. Blockchain 2. Smart contracts 3. Consistency verification (DynamoDB) 4. Efficient delta calculation (git) --- I just think they're cool! --- ### How is that different from just concatenating and hashing everything together? --- # Inclusion Proofs ----  ----  ----  ----  ----  ---- # Merkle Proof  --- # Efficient updates! ----  ----  ----  ----  --- # Ok, but how efficient? ## Let's talk numbers! ---- # Depth & logarithms ---- ## Let's measure the tree  ---- ## $\text{depth} = 0$  ## $n_{\text{leaves}} = 1$ ## $n_{\text{nodes}} = 1$ ---- ## $\text{depth} = 1$  ## $n_{leaves} = 2$ ## $n_{nodes} = 3$ ---- ## $\text{depth} = 2$  ## $n_{leaves} = 4 \text{ } n_{nodes} = 7$ ---- ## $n_{\text{leaves}} = 2^{\text{depth}}$ ## $n_{\text{nodes}} = 2^{(\text{depth} + 1)} - 1$ --- ## How efficient is an update?  ---- ## We only need to update ## $n = depth + 1$ nodes ---- ## Let's take a tree of depth 20 ---- ## $n_{\text{leaves}} = 2^{\text{depth}} = 524288$ ## $n_{\text{nodes}} = 2^{\text{depth} + 1} - 1 = 2097151$ ---- # $21$ ---- ## $O(\log_2(n))$ --- ### How efficient is an inclusion proof? ---- # Merkle Proof  ---- ## $O(\log_2(n))$ --- # Implementation ---- ## Memory layout ----  ----  ----  ----  ----  --- ## Index Calculus ---- ## Index of parent? ----  ---- ## $i_{p} = \frac{i}{2}$ ---- ## Index of sibling? ----  ---- ### $i_s = \begin{cases} i + 1,& \text{if } x \mod 2 = 0 \\ i - 1, & \text{otherwise} \end{cases}$ ---- ## Depth at index? ----  ----  ---- ## Depth at index? ### $d = \log_2(i)$ ---- ## Won't somebody please ## think of the children?!? ----  ---- ## Index of left child ## $i_{l} = 2n$ ## Index of right child ## $i_{l} = 2n +1$ --- # Coding time! ---  ---  ---  --- For a tree of depth 20, we have $n_{\text{nodes}} = 2^{21} = 2097152$ $n_{\text{leaves}} = 2^{20} = 1048576$ And $1048576$ hashes! --- Or do we? --- We're hiring*** --- `~fin~`