Chapter 02

Tree Data Structures


Basic Tree Data Structures

Tree Data Structures

Previous Section Recap

In the previous section, we looked at how Bitcoin and Ethereum keep track of user balances:

・Account-based Model:
Used by Ethereum; we are familiar with this model since traditional banks also use it
Keeps track of an overall user state which includes balance (ie. Alice has $17.76)

・UTXO (Unspent Transaction Outputs):
Cash-like system of balance tracking used by Bitcoin
All the UTXOs are stored in a global UTXO set


Blockchain networks use transactions to change state and keep track of user balances, as we saw in the previous section. Let's dig even further into the complexity of these systems and start looking at what data structures they use to store all this changing state data.

An Orientation to Trees

First things first, computer scientists are weird. They like to draw trees upside down.

Just like in real life there are many kinds of trees, there are many tree-like data structures in computer science. Let's familiarize ourselves with a few of these trees.

Make sure to take a close look at the bolded terms, as they are very important vocabulary to learn for blockchains in general!

The first term you will see widely used in data structures: nodes. A node is a basic unit of a data structure.

In computer systems, "node" can also refer to network nodes communicating data on a peer-to-peer network (which Bitcoin and Ethereum are!). Context is important!

Simple Tree

The top, orange node is referred to as the parent while the bottom green nodes would be referred to as the children (relative to the parent node)

Binary Tree

It is typical to see some enforcement property before "tree" to distinguish different types of tree data structures. A tree is considered binary when each parent has at most two children. The key word in this tree is binary - it, like other preceding terms to "tree", sets some type of rule for the tree - in this case, that each parent node can have at most two children.

Notice the tree in the diagram above now has four new gray nodes. These would now be referred to as the leaves since they are the last level of the tree and have no further children.


The tree above shows that a tree can be any parent with any number of children. There doesn't have to be any enforcement on the tree, it just is a tree of data.

You will see a pattern emerge where the word "tree" is usually preceded by some term that tells you what types of rules that tree will enforce. A binary tree enforces the rule that parents can have at most two children. A tree... is just a tree! Trees don't necessarily have to come

Enforcement allows people to more efficiently work with data since they know a tree will have certain rules enforced - but, the point is, a tree can just be... a tree!

Tree vs. Linked List

A linked list is also a tree - just a really long one that only has one child per parent in a long continuous chain. A tree is not necessarily a linked list. Here are the two code implementations for a LinkedListNode and aTreeNode to help distinguish:

class LinkedListNode {
	constructor(data) { = data; = null;

class TreeNode {
	constructor(data) { = data;
	    this.children = [];

Notice the TreeNode holds the typical data and an array to contain references to any children of that (parent) node.

The LinkedListNode just keeps track of a next node.

Tree Vocabulary Summary

Take note of all of the relativity that happens as a tree grows in size. A node that was a leaf node becomes a parent node once a new child is added under it.

Final vocabulary for trees:

key: actual data held inside node
key: ノードに格納されている実際のデータ

root: the parentest node in a tree
root: ツリー内の親ノード

siblings: nodes under the same parent and on the same level

subtree: once you isolate a part of a broader tree, you can form a brand new tree with new relationships
サブツリー: 広いツリーの一部を切り離すと、新しい関係を持つ全く新しいツリーを形成することができる

When To Use a Tree 🌲
ツリーを使用する場合 🌲

Sometimes trees occur quite naturally! Take a file system for example:

☝️ A file system can be a tree with an arbitrary amount of children in each directory
☝️ ファイルシステムは、各ディレクトリに任意の数の子供を持つツリーにすることができる

Tree usage:

・If your data can be stored hierarchically, using a tree can be a good data structure to go with.

・A tree is also a very efficient data structure for the searching and sorting of data

●Recursive algorithms are often used in conjunction with trees

Trees can be very efficient data structures for searching/sorting data precisely because of the rules it sets, like being a binary tree or an even stricter rule set, a binary search tree.

Binary Search Tree

A binary search tree, like the one above has the following properties:

・it is a binary tree

・the left subtree of a node contains only nodes with keys lesser than the node's key

・the right subtree of a node contains only nodes with keys greater than the node's key

・each node’s left and right subtrees must also be a binary search tree

These types of enforcements make a binary search tree a highly in-demand data structure, since algorithms can now account for these rules and storing/searching is made much more efficient!

Binary Search Tree Trivia

Knowing that each left child is less than the parent and each right child is greater than the parent, how many attempts does it take you to find a number (key) at most?
Adding a whole new layer of elements adds only 1 more search attempt at worst. Because of the BST (short for Binary Search Tree) enforcement properties, the search time always remains O(log n) where n is the number of nodes in the tree.
新しい階層を追加しても、最悪1回しか試行回数が増えないのです。BST(Binary Search Treeの略)の実施特性により、探索時間は常にO(log n)(nはツリーのノード数)のままである。

The tree in the diagram above is a BST of a height, how many levels a tree has, of three, with nodes held at each level that increase in number by a power of two each level down. The last level contains 4 nodes which means the next level under that will contain 8 nodes (at most). Here is the real magic of enforced-property trees like BSTs: even though we add a whole new level of new data, the search time only increases by one. In other words, as the size of the tree grows at an exponential, the search time always remains O(log n).
上の図は、高さ(木のレベルの数)が3のBSTで、各レベルに保持されるノードは、レベルが下がるごとに2の累乗で増えていきます。最後のレベルには4つのノードがあり、その下のレベルには(最大でも)8つのノードがあることになる。BSTのような強制特性木の本当の魅力は、新しいレベルの新しいデータを追加しても、探索時間が1だけ増加することである。つまり、木のサイズが指数関数的に大きくなっても、探索時間は常にO(log n)のままなのです。

Here is a chart to visualize how much algorithm search time is affected by growth of input (n).


Since blockchains are basically databases, Big O analysis is very important to help choose the most efficient data structure (low storage costs, easy search and retrieval). When designing a system with data needs, you want your data structure to be as close to Constant Time (the blue line on the chart) as possible.
ブロックチェーンは基本的にデータベースなので、最も効率的なデータ構造(保存コストが低く、検索や取り出しが容易)を選択するために、ビッグ・オー解析は非常に重要です。データニーズがあるシステムを設計する場合、データ構造はできるだけConstant Time(グラフの青い線)に近づけたいものです。

Big O Notation gives us a rough indicator of how well an algorithm will perform in terms of N (# of input elements). We want our algorithms to be efficient.
Big O記法は、N(入力要素の数)に対して、アルゴリズムがどの程度うまく機能するかを大まかに示すものです。アルゴリズムは効率的であることが望まれます。


We covered basic tree data structures, different types of enforcements on trees and general tree data structure vocabulary. This is all important information as we dive even deeper into more specific trees with more specific enforcements on them. In the next section, we'll look at Merkle Trees.

As a heads up for the next two sections, blockchains use tree data structures quite heavily... buckle up... it's TREE TIME.
次の2つのセクションの予告として、ブロックチェーンはツリーデータ構造を非常に多用します。ベルトを締めて...TREE TIMEだ。

<next chapter>

Build a Binary Search Tree

Binary Search Tree

In programming, trees are a data structure that come up surprisingly often! They have a number of different use cases ranging from efficient data storage to representing a file heirarchy.

In this particular lesson we're going to go over the Binary Search Tree. Its name might sound intimidating, but it's actually quite simple!

Trees start with a root node which branches to nodes underneath it (its children). The word binary indicates that each nodes has at most 2 children. It's called a search tree because the order of the nodes is sorted by the value of the data. Let's take a look at an example:


Any child that is to the left of it's parent is smaller. Any child that is to the right of it's parent is greater. For example, the root 5 has two children 3 and 7. Since 3 is less than 5, it is to the left of 5.
親より左側にある子は小さくなります。親より右側にある子は、より大きい。例えば、ルート 5 は 2 つの子 3 と 7 を持っています。3 は 5 より小さいので、5 の左側にあります。

Knowing that the data is in this order, it will take us less time to find a particular node. We can look for 4. Starting at the root, we know it's less than 5 so we go left. We encounter 3 next and know that 4 is greater than 3, so we go right. There, we find 4. On average this will be faster than searching randomly. The time savings become greater the bigger the tree is.

Now let's build our own Binary Search Tree!

<next chapter>

1: Node

Creating a Node

Let's first create the class Node, from which we will create each element inside of our tree:

The node should contain data, which in this case is 5. It should also contain references to the left child (3) and the right child (7).

Your Goal: Complete Constructor

Complete the constructor function on the node. Store the data inside a data property on the instance.

Store null in properties left and right.

Usage Example:

const node = new Node(5);

console.log(; // 5
console.log(node.left); // null
console.log(node.right); // null
<next chapter>

2: Tree

Storing the Root

Now it's time to create our Tree!

A tree will keep track of one property: a reference to the root node.


Your Goal: Store the Root

Finish the constructor function on the Tree class in the new file Tree.js.

All you need to do for now is store null on a root property.

const tree = new Tree();

console.log(tree.root); // null
<next chapter>

3: Add Root

Adding a Root

In this stage we'll create a new method for adding nodes to our tree. This is a difficult task to generalize so we'll attack it piece by piece!

First let's start by adding a root to an empty tree.

Your Goal: Add Node Method

Create a new method addNode on Tree which will take a new node and add it to the tree.
新しいノードを受け取ってツリーに追加するメソッド addNode をツリー上に作成します。

Assume that the tree is empty for this stage. Simply set the root to be the node passed into the method.

// create a new tree and new node
// 新しいツリーと新しいノードを作成する
const tree = new Tree();
const node = new Node(5);

// add the node to the tree using addNode
// addNode を使ってノードをツリーに追加する。

// the new node becomes the tree's root
// 新しいノードがツリーのルートになる
console.log(; // 5

In the next few stages we'll start to generalize this function, so it won't hurt to start thinking in that direction!

<next chapter>

4: First Layer

Now it's time to focus on adding the first layer of nodes underneath our root!

The bottom-most layer of a tree is call it's leaves

Keep the code you used to pass the last stage and then add another case for when a root already exists:

When the root already exists, we'll need to decide which side to add the new leaf node to.

If the new node data is less than the root data, we'll want to add it to the left.

Conversely, if the data is greater we'll add it to the right.

Your Goal: Modify Add Node

Modify the addNode function to also handle adding the first children of the root.
ルートの最初の子の追加も処理するように addNode 関数を修正します。

const tree = new Tree();
const node1 = new Node(5);
const node2 = new Node(3);
const node3 = new Node(7);


console.log(; // 3
console.log(; // 7

Don't worry about generalizing this any further than the first left and right children just yet! We'll focus on that in the next stage.

<next chapter>

5: Many Layers


Now it's time to make our addNode function work for many layers of the tree:

You can do this iteratively or recursively! For help on designing your solution, check out details.

Your Goal: Generalize

Complete the function addNode so that it can handle adding nodes no matter how large the tree gets.
関数 addNode を完成させ、木がどれだけ大きくなってもノードを追加できるようにしなさい。

Don't worry if you start to get frustrated! This is a tough stage. It may take you several tries to get it right.

Recursive Solution

Ready to write a recursive solution? Let's do it!

You already wrote the code to add a node underneath another node. All we need to do is apply this recursively.

So far your code does this:

Add to Root

Now we just need to do add a node underneath a different node:

Add 4

A good way to start the recursive solution is to write a new function on Tree that will take two arguments: a parent and a child. This function should add the child under the parent node.

●If the child data is less than the parent data, then it should go left

○If the parent already has a left node, call this new function recursively with   that left node as the parent.
 ○If the parent does not have a left node, set the new node as the new left node.

●If the child data is greater than the parent data, then is should go right

If the parent already has a right node, call this new function recursively with that right node as the parent.

○If the parent does not have a right node, set the new node as the new right node.

Now you can call this method from addNode if there is an existing root. Initially the root will be the parent, and this will expand as more nodes get added.

Iterative Solution

The iterative solution can be similar to the recursive solution. In our opinion it is more difficult. You'll likely want to iterate until you find the point where you can add the node by using a while(true) and then break or return after you've added the node.

Similar to the recursive solution you change the node your focused on by storing a reference and changing that reference as you move down the tree.

So at first your reference might be the root:

Then you can shift the reference to be the next node as you move downwards:

You'll continue to shift the reference until you find a spot to add your new node. Once you've found that spot, you can add the node and break to escape the while(true) loop.

<next chapter>

6: Search

Search Tree

It's time to reap the rewards of creating our binary search tree. That's right, it's time to search!

Let's use the sort order to find nodes in the tree. For instance, if we were searching for the node 4:

Search 4

1.We start at the root 5, recognize that 4 is less than 5 so we move left.

2.We find 3, recognize that 4 is greater than 3 so we move right.

3.We find 4, recognize this is what we are looking for and return true.

If we search for a missing node, we return false.
もし存在しないノードを探すと、false を返す。

For instance if we were looking for 7 on this tree:

Missing Node

After recognizing that 7 is greater than 5, we attempt to move right, but there is no right node! We return false.
7が5より大きいことを認識した後、右に移動しようとしたが、右のノードがない! falseを返す。

Your Goal: hasNode Method
あなたの目標:hasNode メソッドを追加する。

Add a method hasNode that will take a number and search our tree to find a node that has that number inside it's data property.
数値を受け取り、ツリーを検索してその数値をデータプロパティ内に持つノードを見つけるメソッド hasNode を追加します。

If a node exists with the number, return true. If not return false.
もし、その番号を持つノードが存在すれば、true を返します。存在しない場合は false を返します。

For example:

const tree = new Tree();
const node1 = new Node(4);


console.log(tree.hasNode(4)); // true
console.log(tree.hasNode(7)); // false
<next chapter>

Markle Tree Intro

Merkle Trees

Now it's time to talk about an important data structure: Merkle Trees. As we take a look at Ethereum Data Storage and as we build smart contracts, we'll often find ourselves interfacing with this data structure and we'll be expected to understand its usefulness.
さて、そろそろ重要なデータ構造についてお話ししましょう。Merkle Treesです。Ethereum Data Storageを見ていく中で、またスマートコントラクトを作っていく中で、このデータ構造に接することが多くなり、その有用性を理解することが求められるようになります。

Ok, tell it to me straight! What is a Merkle Tree and what does it do?
よし、はっきり言ってくれ! マークルツリーとは何ですか、そして何をするのですか?

Quite simply, a Merkle Tree is a data structure that allows us to make efficient verifications that data belongs in a larger set of data.

They are commonly used in Peer to Peer networks where efficient proofs of this nature will help increase the scalability of the network.
一般的ににPeer to Peerネットワークで使用され、この性質の効率的な証明がネットワークのスケーラビリティを向上させるのに役立っています。

Let's take a step back and take a look at a binary Merkle Tree from a high-level. A Merkle Tree is a collection of hashes reduced to a single hash:

      ABCDEFGH <-- Merkle Root
       /    \
    ABCD     EFGH
    / \      / \
   AB  CD   EF  GH
  / \  / \  / \ / \
  A B  C D  E F G H

We use letters for convenience in this illustration. Each single letter represents a hash. The combined letters represent concatenated hashes that have been combined and hashed to form a new hash.

Over a series of a steps the eight leaf hashes A, B, C, D, E, F, G, and H are combined to create a single, unique hash that allows us to quickly check for inconsistencies without having to look at each individual data point.

As peers in a system, I can simply ask if your root matches mine. If so, we agree. This is a nice optimization for distributed systems of any kind!

Now, if we're just comparing roots, you might be asking:

Why the tree structure? Could we not concatenate all eight hashes at once and store that hash?

Great question! We certainly could. This binary tree structure affords us one further optimization: it allows us to verify a single piece of data belongs in the tree without having all of the data. Consider the merkle tree from above with some missing data:

       /    \
    ABCD     EFGH
    / \      / \
   -  -     EF  GH
  / \  / \  / \ / \
  - -  - -  E F -  -

What do we need in order to prove that E belongs in this tree?

Just F, GH, ABCD. We use these to calculate EF, EFGH, and ABCDEFGH. Then we can compare the result to our expected root ABCDEFGH .
F, GH, ABCDだけです.これらを使って、EF, EFGH, ABCDEFGHを計算します。そして、その結果を予想されるルートABCDEFGHと比較することができます。

If something went wrong along the way, we would notice it at the root. For example if we replaced E with M:

       /    \
    ABCD     MFGH
    / \      / \
   -  -     MF  GH
  / \  / \  / \ / \
  - -  - -  M F -  -

We can quickly check ABCDMFGH against the our expected root ABCDEFGH and see we did not get our expected hash. Something's wrong.

The savings become important with larger trees where the average case for verification of tree is log2(n) where n is the number of nodes in the tree. So for a tree of size 128, it would take only 7 hashes to determine the root.

Build a Merkle Tree in JavaScript
JavaScriptでMerkle Treeを構築する

As programmers, it is often easiest to learn things by building them from scratch. We believe this holds true for most engineers; we like to get our hands on things. That's why, in this next module, you will build your own Merkle Tree! You can do it💪
プログラマーにとって、ゼロから作り上げることは最も簡単な学習方法であることが多い。これは多くのエンジニアにも言えることで、私たちは実際に手を動かしてみることが好きなのです。そこで、次のモジュールでは、あなた自身のMerkle Treeを構築してみましょう! パワー!!!!!!💪💪💪💪💪

<next chapter>


Merkle Trees

Merkle Trees are awesome! They allow us to verify if a piece of data is part of a larger data structure, without having all of the data within that structure. This means they can be used to check for inconsistencies in all kinds of distributed systems!

For Blockchain, storing transactions as Merkle Trees allows us to look at a block and verify that a transaction was part of it by only having part of the data set!
ブロックチェーンでは、トランザクションをMerkle Treeとして保存することで、データセットの一部しか持っていなくても、あるブロックを見て、あるトランザクションがその一部であることを検証することができるのだ!

Remember that the data within a blockchain block is just a set of transactions.

Let's take a look at an example:


In this tree each letter represents a hash, and combined letters represent concatenating hashes and hashing those together.

        /      \
    ABCD        EFGHIJ
     |          /    \
    ABCD     EFGH     IJ
    / \      /   \     |
   AB  CD   EF   GH   IJ
  / \  / \  / \  / \  / \      
  A B  C D  E F  G H  I J

To prove that the hash A is a part of the Merkle Root we don't need to know hash C or D, we just need to know hash CD. The necessary proof for A is:

Hash(Hash(Hash(A + B) + CD) + EFGHIJ)

Where we only need to know the hashes B, CD, and EFGHIJ to prove that A is in the merkle root.

If this all sounds like nonsense, don't worry.

That's what this lesson is for!

You will understand soon and we'll come back to this over the coming stages.

<next chapter>

1: Combine Two Leaves

Alright, let's build us a Merkle Tree!

A merkle tree will take an array of leaf nodes, combining them together two at a time, layer-by-layer, until they are reduced to a single root node. This forms a tree-like structure of hashing.

Your Goal: Root of Two Leaves

First, let's write a constructor for the MerkleTree class. This constructor will take two arguments passed in this order:

1.An array of leaf nodes

2.A combination function used to concatenate and hash two leaves together

Let's take a closer look at the combination function.

Next, let's add a function getRoot on the MerkleTree class. This function will find the merkle root.

For this stage you will only need to take two leaves and hash them together:

    /  \ 
   A    B

Here, A and B are the leaf nodes and the root is the result of the concatenation. Simply take the first and second leaf nodes and use the concatenate function to get the result.
ここで、AとBはリーフノードで、ルートは連結の結果です。1 番目と 2 番目のリーフノードを取り、concatenate 関数を使用して結果を得るだけです。

Don't worry about generalizing just yet! On the next stage we'll move onto some more in-depth scenarios.

Combination Function

To simplify this merkle tree implementation and to make debugging easier, we'll pass a concatenation function from the tests into the MerkleTree constructor.

This function will take two arguments: a left leaf node and a right leaf node and will return the resulting combination.

For instance in a four-leaf tree:

    / \    
   AB  CD  
  / \  / \ 
  A B  C D

The function is used three times, for each combination. We'll denote it here with Hash:

Hash(Hash(A + B) + Hash(C + D))

First we're combining A and B. Next we're combining C and D. Finally we're combining the result of those two combinations AB and CD to get the Root hash.

If you take a look at testTwo.js you'll see the function is simply forming the string in the format shown above. This will help us debug problems in the first few stages! You'll be able to compare the string you created versus the expected result.
testTwo.jsを見てみると、この関数は単に上記のような形式で文字列を形成していることが分かる。これは最初の数ステージで問題をデバッグするのに役立ちます! 作成した文字列と期待される結果を比較することができるようになります。

<next chapter>

2: Multiple Layers

Now it's time to handle a larger Merkle Tree!

This tree will have multiple layers. For example, with four leaf nodes you'll combine the first two nodes and then you'll combine the last two nodes. Then you'll take the two results and combine those to get the root node.

Before generalizing your algorithm it might be helpful to re-visit the purpose of the Merkle Tree.

Your Goal: Handle Bigger Trees

Update the getRoot function to handle merkle trees with more than two leaf nodes.

When breaking down the logic of merkle trees, first we hash together A and B, then we hash together C and D. Then we hash together the combination of A and B (AB) with the combination of C and D (CD). Something like this:

    /  \ 
   AB  CD
  / \  / \
  A B  C D

Writing the code you will likely find it useful to think of the tree as having multiple layers:

・The first layer is the leaves (A, B, C, D)
最初の層は葉です (A, B, C, D)

・The second is the combination of both of those combinations (AB, CD)
2 番目の層は、それらの両方の組み合わせ (AB, CD) です。

・The last layer is the final combination: the merkle root (ABCD)

In each layer, we'll need to combine elements two-at-a-time until we reach a layer with just a single element. At that point we can stop, knowing we've found the root.

For this stage you'll need to handle a single leaf node, two leaf nodes, four leaf nodes and eight leaf nodes.

This is a tough algorithm to work through. If you need help getting started check out our Recommended Approach.

Purpose of the Merkle Tree
Merkle Treeの目的

Consider the four leaf example:

    /  \ 
   AB  CD
  / \  / \
  A B  C D

What do we need to prove that C is in ABCD?

You might say, we need A, B, and D. But this is actually more information than we need!

We actually only need AB and D:

Hash(AB, Hash(C, D))
ハッシュ(AB, ハッシュ(C, D))

In this derivation of ABCD, we can forget about A and B. We don't need to know what they are to prove that C is in the Root. We just need the D and AB.

This optimization is the power of Merkle Trees. It becomes even more apparent with larger trees where less data is necessary to prove that a leaf node is part of the tree. A Merkle Tree of 128 nodes only requires 7 other hashes to prove a leaf node belongs in the set.

Recommended Approach

There's several ways to approach writing this algorithm. First off, you'll need to choose between recursion and iteration. Personally, I find the recursive approach more elegant and easy to work with. Feel free to pick the approach you're most comfortable with!

Either way, let's break down the thought process on how to approach this.

We have a merkle tree with some arbitrary number of leaf nodes. Maybe it's the four leaf tree:

    /  \ 
   AB  CD
  / \  / \
  A B  C D

Maybe it's the eight leaf tree:

       /    \
    ABCD     EFGH
    / \      / \
   AB  CD   EF  GH
  / \  / \  / \ / \
  A B  C D  E F G H

Our recommended approach to this problem, is to break it down into layers.

Let's consider the eight leaf tree. For each layer, we want to take every 2 nodes and combine them.

So, if we're on the bottom layer:

・Combine A and B to make AB

・Combine C and D to make CD

・Combine E and F to make EF

・Combine G and H to make GH

After that, we'll move up a layer! Next layer:
この後、1つ上のレイヤーに移動します 次のレイヤーです。

・Combine AB and CD to make ABCD

・Combine EF and GH to make EFGH


・Combine ABCD and EFGH to make ABCDEFGH

Each layer we check to see if there is a single element left. If there is only one element left, it's root. Time to return that root!

Alternatively, you can calculate ahead of time how many layers will be in the tree. Then you'll know when to return the root based on how many layers you've worked on

<next chapter>

3: Odd Leaves

Trees are great! We❤trees🌲

Even when those trees happen to be a bit... odd.😂

Your Goal: Handle Odd Number of Leaves

Let's consider what happens in the case of an odd number of leaves in a tree.

Any time that there is no right pair to an element, we're just going to want to carry that leaf one layer up:

    / \ 
   AB  C
  / \  |
  A B  C

In this case we don't use the C node until we combine it with AB to create the Merkle Root. Let's handle this in our getRoot function.

Check out configurations for Other Odd Trees
Other Odd Treesの構成をチェックしてください。

Other Odd Trees

The rule for odd trees is always to use up everything towards the left side before filling out the right side of the tree.

Five Leaf Tree

With five leaves, we use the first four as the left side and bring the fifth all the way up until the last combination.

     /    \
    ABCD   E
    / \    |
   AB  CD  E
  / \  / \ |
  A B  C D E

Seven Leaf Tree

With seven leaves, the last three hashes work similar to a three leaf tree to build up the EFG combination and then combines with the first four hashes.

       /    \
    ABCD     EFG
    / \      / \
   AB  CD   EF  G
  / \  / \  / \ |
  A B  C D  E F G
<next chapter>

4: Build the Proof

Alright, now it's time to build the proof that a particular leaf node exists within a merkle tree!

With this proof, we'll only want to include the necessary hashes we need to create the root hash from our target leaf node.

ABCDE Merkle Proof Example

     /    \
    ABCD   E
    / \    |
   AB  CD  E
  / \  / \ |
  A B  C D E

Proof of C
Proof of C

Let's prove C is in the Merkle Root!
CがMerkle Rootにあることを証明しよう!

We build the path to create the root from C:

Hash(Hash(AB + Hash(C + D)) + E)

So the four hashes in use here are AB, C, D, and E. Since we're starting with C, we won't need it in the proof. We'll need to know AB, D and E.

Also we need to know the order in which they should be combined. Hash(A + B) will not be the same as Hash(B + A). Our proof should contain the data (the hash) and whether or not the node is in the left position.

Our resulting proof would look like this:

 { data: 'D', left: false },
 { data: 'AB', left: true },
 { data: 'E', left: false }

By looking at this proof, we can easily concatenate to the root. We start with C, concatenate D on the right (CD), concatenate AB to the left (ABCD) and then concatenate E on the right to get the root ABCDE.

Look at that! We didn't even need to know A or B, just the combined hash of the two.

Check out Details for another example.

Add the getProof Method

Let's add a getProof method to our MerkleTree class. This function will take in an index of a leaf node and return a Merkle Proof.
MerkleTreeクラスにgetProofメソッドを追加してみましょう。この関数は、リーフノードのインデックスを受け取り、Merkle Proofを返します。

The Merkle Proof will be an array of objects with the properties data (the hash) and left (a boolean indicating if the hash is on the left).
Merkle Proofは、data(ハッシュ)とleft(ハッシュが左にあるかどうかを示すブール値)のプロパティを持つオブジェクトの配列になる。

If you get stuck be sure to check out our Recommended Approach.

Another Example

Let's prove A belongs in the ABCDEFGHIJ Merkle Tree
AがABCDEFGHIJのMerkle Treeに属することを証明しよう。

              /      \
      ABCDEFGH        IJ
      /      \         |
    ABCD     EFGH     IJ
    / \      /   \     |
   AB  CD   EF   GH   IJ
  / \  / \  / \  / \  / \      
  A B  C D  E F  G H  I J

In order to prove A is in this tree we'll need the following proof path

Hash(Hash(Hash(Hash(A + B) + CD) + EFGH) + IJ)

So we'll need four hashes: B, CD, EFGH, and IJ.
つまり、4つのハッシュが必要です。B, CD, EFGH, IJの4つのハッシュが必要です。

 { data: 'B', left: false },
 { data: 'CD', left: false },
 { data: 'EFGH', left: false }
 { data: 'IJ', left: false }

Such a big tree and we only need four hashes to prove A! For I or J the savings would be even better in this tree, only two hashes necessary for their proofs. Very cool!

Recommended Approach

This is a difficult algorithm to come up with, so we've included a recommended approach.

You'll want to approach this similar to how you did the getRoot algorithm. If you think of the algorithm in terms of layers, we can figure out what need to do on each layer.

Let's use the ABCDE Merkle Tree for an example:
ABCDE マークルツリーを例にとって考えてみよう。

     /   \
   ABCD   E
   / \    |
  AB  CD  E
 / \  / \ |
 A B  C D E

Let's say we want to prove C exists in the tree. We're given the index 2, which corresponds to the C's position in the array passed into our Merkle Tree constructor.
例えば、Cが木の中に存在することを証明したいとする。これは、Merkle Treeのコンストラクタに渡された配列の中でCの位置に相当する。

So we start at C on the bottom layer. What do we need to first?

We need to know if C is the left or right node in its pairing. We can determine this by checking C's index (2). Two is even so it is a left node. Now that we know that, we need to add one to our index to get the right node: D. We add D to our proof and say it is left: false (because it's on the right).

Our proof so far:

  { data: 'D', left: false }

Since we started at C and we have D in our proof, we'll want the piece of data that combines with CD. We'll need to move up one layer and move to the index of CD. We're at index 2 and need to move to index 1.

Since our merkle tree is a binary tree, each layer combines its pairs resulting in half the number of nodes. This means we should cut our index in half and round down. You can verify this for yourself by taking a look at each individual node and thinking where you want to be next up one layer:

For A at index 0, we want to move to AB at index 0

For B at index 1, we want to move to AB at index 0

For C at index 2, we want to move to CD at index 1

For D at index 3, we want to move to CD at index 1
インデックス 3 の D は、インデックス 1 の CD に移動したい。

For E at index 4, we want to move to EF at index 2
インデックス 4 の E は、インデックス 2 の EF に移動します。

For F at index 5, we want to move to EF at index 2

Notice each time we need to divide the index in half and round down.

So now we move to index 1 on the second layer, which is CD. We need to again check if CD is a left or right node. Since it's an odd number, it's a right node. We'll subtract one to get it's left node AB and add it to our proof:

Our proof so far:

  { data: 'D', left: false }, 
  { data: 'AB', left: true }

If we repeat this pattern, we'll divide our index (1) by 2, take the floor (0) and be at ABCD. We'll grab the right node E and add that to our proof:

  { data: 'D', left: false },
  { data: 'AB', left: true },
  { data: 'E', left: false }

At this point we will reach the top layer, with one node and can return our proof.

<next chapter>

5: Verify your Proof
5: 証明を検証する

Almost done! Remember that proof that we just made in the last stage?

It's time to verify it.

The test cases will include some valid proofs and some invalid proofs, your function will need to know the difference.

Your Goal: Complete Verify Proof

The function verifyProof takes four parameters: proof, node, root and concat.
関数 verifyProof は4つのパラメータを取る:proof, node, root, concat.

Here are their definitions:

1.proof - An array of objects whose properties are data and left. (The proof you created in the previous stage)
proof - プロパティが data と left であるオブジェクトの配列。(前のステージで作成したプルーフ)

2.node - A leaf node we're trying to prove is within the merkle tree.
node - マークルツリーの中にあることを証明しようとするリーフノード

3.root - The valid Merkle Root.
root - 有効なMerkle Root

4.concat - The method used to combine the leaf nodes.
concat - リーフノードを結合するために使用するメソッド。

Take the node and combine it with all the data provided in the proof.

At this point you'll have your own root derived from the node and the proof. Compare this to the true root with === to see if they match.

Check out the Details tab for an example proof.

Example Proof

In the previous stage we used the ABCDE merkle tree and created a proof of C being in the tree.

ABCDE Merkle Tree

     /    \
    ABCD   E
    / \    |
   AB  CD  E
  / \  / \ |
  A B  C D E

Proof of C

As we said in the previous stage, the hash path is as follows:

Hash(Hash(AB + Hash(C + D)) + E)

In order to verify this proof we need to take three steps:

1.Hash C and D

2.Hash the result together with AB (AB should be on the left)

3.Hash the result together with E (E should be on the right)

After this is complete, our resulting hash is our merkle root: ABCDE.