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
Ethereumで使用されている。伝統的な銀行もこのモデルを使用しているため、私たちもよく知っている。
Keeps track of an overall user state which includes balance (ie. Alice has $17.76)
残高を含むユーザー全体の状態を把握する（例えば、アリスは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
すべてのUTXOはグローバルUTXOセットに格納される。
Intro
はじめに
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.
木データ構造の種類を区別するために、「木」の前に何らかの強制力を持たせるのが一般的である。各親が最大2つの子を持つとき、木は二項とみなされる。この木のキーワードはバイナリで、「木」の前にある他の用語と同様に、木に何らかの規則を設定する。この場合、それぞれの親ノードは最大で2つの子を持つことができる、ということだ。
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.
上の図の木には、新たに4つの灰色のノードが追加されていることに注目してください。これらは、木の最後のレベルであり、それ以上の子を持たないので、葉と呼ばれるようになりました。
Tree
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
「木」という言葉の前に、その木がどのような種類の規則を強制するかを示す用語がある、というパターンが見えてくるでしょう。二分木は、「親は最大2人の子を持つことができる」という規則を強制する。木は、ただの木だ。木は、必ずしも来る必要はない
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:
リンクリストもツリーです。ただ、非常に長いツリーで、親1人に対して子1人の連続したチェーンになっています。木は必ずしもリンクリストとは限りません。以下は、LinkedListNodeとTreeNodeを区別するための2つのコード実装です。
class LinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
class TreeNode {
constructor(data) {
this.data = data;
this.children = [];
}
}
Notice the TreeNode holds the typical data and an array to contain references to any children of that (parent) node.
TreeNodeは典型的なデータと、その（親）ノードの子ノードへの参照を格納する配列を保持していることに注意してください。
The LinkedListNode just keeps track of a next node.
LinkedListNodeは、次のノードを追跡するだけである。
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
2分木である。
・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).
入力（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（入力要素の数）に対して、アルゴリズムがどの程度うまく機能するかを大まかに示すものです。アルゴリズムは効率的であることが望まれます。
Conclusion
まとめ
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.
基本的な木構造、木に対する様々な強制力、そして一般的な木構造の語彙を説明しました。これは、より具体的な木と、その木に対するより具体的な強制力についてさらに深く掘り下げていく上で、すべて重要な情報です。次の章では、Merkle木について見ていきます。
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:
木はルートノードから始まり、その下にあるノード（子ノード）へと分岐します。バイナリーという言葉は、各ノードが最大2つの子を持つことを表しています。ノードの順番がデータの値でソートされるため、探索木と呼ばれています。例を見てみましょう。
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.
このようにデータが順番に並んでいることがわかると、特定のノードを探すのに時間がかからなくなります。4を探せばいいのです。ルートから始めて、5より小さいことが分かっているので、左に進みます。次に3があり、4は3より大きいことが分かっているので、右へ進みます。そして、4が見つかります。平均して、この方法はランダムに検索するよりも速いでしょう。木が大きくなればなるほど、時間短縮の効果は大きくなります。
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:
まず、Nodeというクラスを作り、そこからツリー内の各要素を作ることにしましょう。
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).
このノードにはデータ（この例では5）を格納し、左の子（3）と右の子（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.
左右のプロパティにnullを格納する。
Usage Example:
使用例
const node = new Node(5);
console.log(node.data); // 5
console.log(node.left); // null
console.log(node.right); // null
<next chapter>
2: Tree
Storing the Root
Rootの格納
Now it's time to create our Tree!
さて、いよいよTreeを作成します。
A tree will keep track of one property: a reference to the root node.
ツリーは、ルート・ノードへの参照という1つのプロパティを記録します。
Root
Your Goal: Store the Root
目標：ルートを保存する。
Finish the constructor function on the Tree class in the new file Tree.js.
Treeクラスのコンストラクタ関数を、新規ファイルTree.jsで完成させる。
All you need to do for now is store null on a root property.
今必要なことは、ルートプロパティにnullを格納することです。
const tree = new Tree();
console.log(tree.root); // null
<next chapter>
3: Add Root
Rootの追加
Adding a Root
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 を使ってノードをツリーに追加する。
tree.addNode(node);
// the new node becomes the tree's root
// 新しいノードがツリーのルートになる
console.log(tree.root.data); // 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
目標：addNodeメソッドを修正する
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);
tree.addNode(node1);
tree.addNode(node2);
tree.addNode(node3);
console.log(tree.root.left.data); // 3
console.log(tree.root.right.data); // 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
多層階層
Generalizing
一般化
Now it's time to make our addNode function work for many layers of the tree:
さて、次はaddNode関数が木の多くの層に対して機能するようにする番です。
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.
再帰的な解決策を始める良い方法は、親と子の2つの引数を取る新しい関数をTreeに書くことです。この関数は親ノードの下に子を追加する。
●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.
これで、既存のルートがある場合は、addNodeからこのメソッドを呼び出すことができるようになりました。最初はルートが親になり、ノードが追加されるにつれて拡張されていく。
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.
反復解は再帰解と似たようなものである。しかし、私たちの意見では、この方法はより難しい。ノードを追加できるポイントを見つけるまで、while(true)を使って繰り返し、ノードを追加した後にbreakまたはreturnするのがよいでしょう。
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.
新しいノードを追加する場所を見つけるまで、参照を移動し続けます。その場所を見つけたら、ノードを追加し、while(true)ループから抜け出すためにブレークします。
<next chapter>
6: Search
6：探索
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:
ソート順を利用して、木の中のノードを探してみましょう。例えば、ノード4.を探すとしたら、次のようになります。
Search 4
1.We start at the root 5, recognize that 4 is less than 5 so we move left.
ルート5から始めて、4が5より小さいことを認識し、左に移動する。
2.We find 3, recognize that 4 is greater than 3 so we move right.
3を見つけ、4が3より大きいことを認識し、右へ移動する。
3.We find 4, recognize this is what we are looking for and return true.
4が見つかり、これが探しているものであることを認識し、trueを返す。
If we search for a missing node, we return false.
もし存在しないノードを探すと、false を返す。
For instance if we were looking for 7 on this tree:
例えば、このツリーで7を探していた場合。
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);
tree.addNode(node1);
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:
ここで、一歩下がって、２分木のマークルツリーを大まかに見てみよう。マークルツリーとは、ハッシュの集まりを1つのハッシュにまとめたものである。
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.
一連のaステップで、8つのリーフハッシュA、B、C、D、E、F、G、Hが結合され、単一のユニークなハッシュとなり、個々のデータポイントを見ることなく矛盾を素早くチェックすることができます。
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?
なぜツリー構造なのか？8つのハッシュを一度に連結して、そのハッシュを保存することはできなかったのでしょうか？
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:
いい質問だ。もちろん可能です。この二分木構造は、さらにもう一つの最適化を可能にする。それは、すべてのデータがなくても、あるデータが木に属するかどうかを検証できることだ。上のマークルツリーに欠損データがある場合を考えてみよう。
ABCDEFGH
/ \
ABCD EFGH
/ \ / \
- - EF GH
/ \ / \ / \ / \
- - - - E F - -
What do we need in order to prove that E belongs in this tree?
Eがこの木に属することを証明するために必要なものは何だろう？
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:
もし、途中で何か問題があれば、ルートで気づくことができます。例えば、EをMに置き換えた場合。
ABCDMFGH
/ \
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.
ABCDMFGHを期待したルートABCDEFGHと照らし合わせてみると、期待したハッシュが得られないことがすぐにわかります。何かが間違っているのです。
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.
この節約は大きな木で重要になります。木の検証の平均的なケースはlog2(n)で、nは木のノードの数です。つまり、サイズ128の木では、ルートを決定するのに必要なハッシュは7個だけである。
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 TREE
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:
例を見てみましょう。
ABCDEFGHIJ Merkle Tree
ABCDEFGHIJマークルツリー
In this tree each letter represents a hash, and combined letters represent concatenating hashes and hashing those together.
この木では、各文字がハッシュを表し、組み合わせた文字がハッシュを連結してハッシュ化したものを表しています。
Root
/ \
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:
ハッシュAがマークルルートの一部であることを証明するためには、ハッシュCやDを知る必要はなく、ハッシュCDを知るだけで良いのです。Aについて必要な証明は：
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.
ここで、Aがマークルルートにあることを証明するためには、ハッシュB、CD、EFGHIJを知るだけでよいのである。
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
2枚の葉を組み合わせる
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.
マークルツリーは、葉のノードの配列を、一度に2つずつ、層ごとに組み合わせて、1つの根のノードになるようにするものです。これはハッシュの木のような構造である。
Your Goal: Root of Two Leaves
目標：2つの葉のルート
First, let's write a constructor for the MerkleTree class. This constructor will take two arguments passed in this order:
まず、MerkleTreeクラスのコンストラクタを書こう。このコンストラクタは2つの引数をこの順序で受け取る。
1.An array of leaf nodes
リーフノードの配列
2.A combination function used to concatenate and hash two leaves together
2つの葉を連結してハッシュ化するための結合関数
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.
次に、MerkleTreeクラスにgetRoot関数を追加する。この関数はマークルルートを見つける。
For this stage you will only need to take two leaves and hash them together:
この段階では、2つの葉をとってハッシュ化するだけでよい。
Root
/ \
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.
このMerkleTreeの実装を単純化し、デバッグを容易にするために、テストからMerkleTreeのコンストラクタに連結関数を渡すことにする。
This function will take two arguments: a left leaf node and a right leaf node and will return the resulting combination.
この関数は左葉のノードと右葉のノードの2つの引数を取り、結果の組合せを返す。
For instance in a four-leaf tree:
例えば4葉の木では
Root
/ \
AB CD
/ \ / \
A B C D
The function is used three times, for each combination. We'll denote it here with Hash:
この関数は、各組み合わせに対して3回ずつ使用されます。ここでは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.
まずAとBを組み合わせ、次にCとDを組み合わせ、最後にABとCDの2つの組み合わせの結果を組み合わせてRootハッシュを生成しています。
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.
この木は複数のレイヤーを持つことになる。例えば、4つのリーフノードを持つ場合、最初の2つのノードを結合し、最後の2つのノードを結合する。そして、その2つの結果を組み合わせて、ルートノードを得る。
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.
2つ以上のリーフノードを持つマークルツリーを処理するために、getRoot関数を更新する。
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:
マークルツリーのロジックを分解すると、まずAとBをハッシュし、次にCとDをハッシュする。そしてAとBの組み合わせ（AB）と、CとDの組み合わせ（CD）をハッシュする。こんな感じ。
ABCD
/ \
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)
最後の層は、最後の組み合わせであるマークルルート（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.
各層で、2つずつ要素を組み合わせていき、1つの要素だけの層に到達する必要がある。この時点で、ルートが見つかったと判断し、中止することができます。
For this stage you'll need to handle a single leaf node, two leaf nodes, four leaf nodes and eight leaf nodes.
この段階では、1つのリーフノード、2つのリーフノード、4つのリーフノード、8つのリーフノードを処理する必要があります。
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:
4つの葉の例で考えてみよう。
ABCD
/ \
AB CD
/ \ / \
A B C D
What do we need to prove that C is in ABCD?
Cが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:
必要なのはABと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.
このABCDの導出では、AとBのことは忘れてもよい。Cがルートにあることを証明するために、それらが何であるかを知る必要はない。Dと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.
この最適化こそが、MerkleTreeの力なのです。大きな木になると、葉のノードが木の一部であることを証明するために必要なデータが少なくなり、さらに顕著になる。128ノードのMerkle木では、リーフノードが集合に属していることを証明するために必要な他のハッシュは7つだけである。
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:
任意の数の葉節を持つマークルツリーがある。例えば、4つの葉の木があるとする。
Root
/ \
AB CD
/ \ / \
A B C D
Maybe it's the eight leaf tree:
八枚の葉の場合はこうなる
Root
/ \
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.
8枚の葉の木を考えてみましょう。各レイヤーで、2ノードずつ取り出して組み合わせたいと思います。
So, if we're on the bottom layer:
つまり、一番下の層であれば
・Combine A and B to make AB
AとBを組み合わせてABとする
・Combine C and D to make CD
CとDを組み合わせてCD
・Combine E and F to make EF
EとFを組み合わせてEF
・Combine G and H to make GH
GとHを組み合わせてGH
After that, we'll move up a layer! Next layer:
この後、1つ上のレイヤーに移動します 次のレイヤーです。
・Combine AB and CD to make ABCD
ABとCDを組み合わせてABCD
・Combine EF and GH to make EFGH
EFとGHを組み合わせてEFGHを作る
Finally:
最後に
・Combine ABCD and EFGH to make ABCDEFGH
ABCDとEFGHを組み合わせて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!
各レイヤーで、1つの要素が残っているかどうかをチェックします。もし、1つしか残っていなければ、それはルートです。そのルートを返す時が来ました!
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.😂
その木がたまたまちょっと...変だったとしても
（※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:
ある要素に対して右のペアが存在しない場合、その葉を1つ上の層に運ぶだけである。
Root
/ \
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.
この場合、CノードはABと結合してマークルルートを作成するまで使用しません。これはgetRoot関数で処理しましょう。
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.
5枚の葉の場合、最初の4枚を左側として、5枚目を最後の組み合わせまで持っていきます。
Root
/ \
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.
七枚葉では、最後の3つのハッシュが三葉の木と同様に働いてEFGの組み合わせを構築し、最初の4つのハッシュと組み合わされます。
Root
/ \
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
ABCDEマークルツリー証明の例
Root
/ \
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:
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.
ここで使われているハッシュはAB,C,D,Eの4つである。必要なのはAB、D、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.
また、それらをどのような順序で組み合わせるかも知っておく必要があります。Hash(A+B)とHash(B+A)は同じにはならないでしょう。証明にはデータ(ハッシュ)と、ノードが左の位置にあるかどうかが必要である。
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.
この証明を見ることで、簡単にルートへの連結ができます。Cから始めて、右にDを連結し（CD）、左にABを連結し（ABCD）、右にEを連結すると、ルートABCDEが得られます。
Look at that! We didn't even need to know A or B, just the combined hash of the two.
見てくださいよ。AやBを知る必要はなく、ただ2つのハッシュを結合すればいいのです。
Check out Details for another example.
他の例として、Detailsをチェックしてみてください。
Add the getProof Method
getProofメソッドを追加する
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に属することを証明しよう。
Root
/ \
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
Aがこの木にあることを証明するためには、次のような証明経路が必要です。
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!
こんなに大きな木なのに、Aを証明するのに必要なハッシュは4つだけです。IやJの場合、この木ではさらに節約が可能で、証明に必要なハッシュは2つだけです。とてもクールです。
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.
getRootアルゴリズムと同じようなアプローチをとりたいところです。このアルゴリズムをレイヤーで考えると、各レイヤーで何をすべきかがわかる。
Let's use the ABCDE Merkle Tree for an example:
ABCDE マークルツリーを例にとって考えてみよう。
Root
/ \
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?
そこで、最下層のCから始めることにする。まず必要なことは何だろう？
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).
Cがペアリングの左ノードなのか右ノードなのかを知る必要があります。これはCのインデックス(2)をチェックすることで判断できます。2は偶数なので、左のノードです。それがわかったので、右のノードを得るために、インデックスに1を加える必要があります。Dを証明に加え、左ノード：false（右なので）とします。
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.
Cから始めて、Dを証明に加えたので、CDと結合するデータが必要です。1つ上の階層に移動して、CDのインデックスに移動する必要があります。私たちはインデックス2にいるので、インデックス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:
このマークルツリーは2分木なので、各層でペアを組み合わせると、ノードの数は半分になる。つまり、インデックスを半分にし、切り捨てればよいのです。このことは、個々のノードを見て、次にどの層に行きたいかを考えることで確かめることができます。
For A at index 0, we want to move to AB at index 0
インデックス0のAは、インデックス0のABに移動したい。
For B at index 1, we want to move to AB at index 0
インデックス1のBは、インデックス0のABに移動したい。
For C at index 2, we want to move to CD at index 1
インデックス2のCは、インデックス1のCDに移動したい。
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
インデックス5のFは、インデックス2のEFに移動したい。
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:
ここで、2層目のCDのインデックス1に移動します。ここでもう一度、CDが左ノードか右ノードかを確認する必要があります。奇数なので、右のノードです。1を引いて、左ノードABとし、証明に加えます。
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:
このパターンを繰り返すと、インデックス(1)を2で割って、フロア(0)を取り、ABCDになります。右のノードEを掴んで、それを証明に加えよう。
[
{ 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.
この時点で、ノードが1つある最上層に到達し、証明を返すことができる。
<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.
ノードを取り出し、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マークルツリーを使い、Cが木に含まれることの証明を作成した。
ABCDE Merkle Tree
Root
/ \
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:
この証明を検証するためには、3つのステップを踏む必要がある。
1.Hash C and D
CとDをハッシュ化する
2.Hash the result together with AB (AB should be on the left)
ABと一緒にハッシュする(ABは左側)
3.Hash the result together with E (E should be on the right)
Eとハッシュ化する（Eが右になるはず）
After this is complete, our resulting hash is our merkle root: ABCDE.
これが終わると、ハッシュの結果がマークルツリーのルートとなる。ABCDEである。