Merkle Trees
マークルツリー
Previous Section Recap
前節のまとめ
In the previous section, we looked at what makes up a basic tree data structure, including tree vocabulary. Can you define them all by memory?:
前節では、ツリーの語彙を含め、基本的な木データ構造を構成するものを見てきました。メモリで全部定義できるのでしょうか？
1.node
2.root node
3.parent node
4.child node
5.key
6.tree height
7.leaves
Merkle Trees in Blockchains
ブロックチェーンのマークルツリー
The design of merkle trees makes them extremely efficient for data verification. In Bitcoin, Merkle trees are used to store every transaction mined on the Bitcoin network in an efficient way:
マークルツリーの設計により、データ検証が非常に効率的になります。ビットコインでは、マークル ツリーを使用して、ビットコイン ネットワークでマイニングされたすべてのトランザクションを効率的な方法で保存します。
The diagram above shows the architecture of a bitcoin block. Did you think a bitcoin block contains all of the transactions per block? In a way it does... but via merkle trees!
上の図は、ビットコインのブロックのアーキテクチャを表しています。ビットコインのブロックには、ブロックごとのすべての取引が含まれていると思いますか？ある意味、そうなのだが...マークルツリーを介しているのだ!
What happens is, all of the transactions per block are arranged into a big Merkle tree. What actually ends up getting committed into the block and immutable blockchain is that Merkle tree's root hash.
ブロックごとの取引はすべて、大きなマークルツリーに配置されます。実際のブロックと不変なブロックチェーンにコミットされるのは、そのマークルツリーのルート・ハッシュである。
By committing the root hash of the tree, the transaction data can be stored off-chain (full nodes, for example, store these transaction records on a LevelDB integrated into all full nodes).
ツリーのルートハッシュをコミットすることで、取引データをオフチェーンに保存することができる（例えばフルノードでは、すべてのフルノードに統合されたLevelDBにこれらの取引記録を保存している）。
Thanks to Merkle trees, storage on the blockchain is efficient - you must only commit one piece of data instead of thousands of transactions per block, which would really bloat the system!
ブロックごとに何千ものトランザクションをコミットする必要がなく、1つのデータのみをコミットすればよいのです。
A main design purpose behind using Merkle trees to commit a lot of data elements (typically transactions) per block is to keep the size of the blockchain as small as possible. Given the nature of their usage, blockchains grow perpetually, so you must account for efficient data storage. Keeping the blockchain size from becoming bloated means more people can support running full nodes which helps network decentralization.
ブロックごとに多くのデータ要素（通常はトランザクション）をコミットするためにマークルツリーを使用する主な設計目的は、ブロックチェーンのサイズをできるだけ小さく保つことです。ブロックチェーンはその用途の性質上、永久に成長し続けるので、効率的なデータ保存を考慮する必要があります。ブロックチェーンのサイズを肥大化させないということは、より多くの人がフルノードの運用をサポートできることを意味し、ネットワークの分散化に貢献します。
Thanks to Merkle trees, there is an efficient way to verify that some data exists in a root hash. Take the image below... can you imagine how bloated each block would be if every single tx needed to be stored? Much better to store just ONE root hash representing all the transactions per block!
マークルツリーのおかげで、あるデータがルートハッシュに存在することを検証する効率的な方法があります。下の画像を見てください。もしすべてのtxを保存する必要があるとしたら、各ブロックがどれだけ肥大化するか想像できますか？ブロックごとにすべてのトランザクションを表す1つのルートハッシュを保存する方がはるかに良い!
Merkle Proofs
マークル証明
The benefit of the Merkle tree design -- a recursive hashing-based algorithm -- is that it allows for efficient proof that some data exists within the root hash construction (actually contained in the block!); in other words, it allows for Merkle proofs. A Merkle proof confirms specific transactions represented by a leaf or branch hash within a Merkle hash root.
再帰的ハッシュアルゴリズムであるマークルツリーの利点は、ルートハッシュの構築にあるデータが存在する（実際にブロックに含まれている！）ことを効率的に証明できることである。マークル証明は、マークルハッシュのルート内のリーフハッシュやブランチハッシュで表される特定のトランザクションを確認するものである。
So if anyone ever needs to prove that a transaction existed at one point in time in the blockchain, they just need to provide a Merkle proof.
つまり、ある取引がブロックチェーンのある時点に存在したことを証明する必要がある場合、Merkle証明書を提出すればよいのです。
In the diagram above, say you want to prove that C (some random tx) exists in this block. Thanks to Merkle proofs, you only need 3 total pieces of data: D, H(A-B), H(E-H) to construct the tree root hash: H(A-H). That might not seem like much with such a small tree, but what about a tree containing over 10,000 transactions? If one is able to successfully construct the root hash, then that is proof enough that their transaction was indeed part of that Merkle tree at that time. Data verification FTW!
上の図で、C（あるランダムなtx）がこのブロックに存在することを証明したいとします。Merkle証明のおかげで、合計3つのデータしか必要ない。D, H(A-B), H(E-H)の3つのデータでツリールートのハッシュを構築することができます。H(A-H)です。しかし、1万件以上のトランザクションを含むツリーではどうだろうか。もしルートハッシュの構築に成功すれば、その時点で自分の取引が確かにそのマークルツリーの一部であったという十分な証明になる。データ検証の醍醐味！
Merkle Trees Use Cases
マークルツリーの使用例
Merkle trees are:
マークルツリーは；
・space and computationally efficient
空間的・計算量的に有利
・good for scalability and decentralization
スケーラビリティと分散化に優れている。
・no need to pack a block full of transactions… just commit a Merkle root hash to it and keep transactions in other places that can handle them
ブロックにトランザクションを詰め込む必要がない...マークルルートハッシュをコミットし、トランザクションはそれを処理できる他の場所に保管すればよい。
In deeper terms, they:
もっと深い意味で言えば、それらは：
1.They significantly reduce the memory needed to verify that data has maintained its integrity and hasn’t been altered.
1.データの整合性が保たれているか、改ざんされていないかを検証するために必要なメモリを大幅に削減することができる。
2.They require less data to be broadcast across the blockchain network to verify data and transactions. This improves the efficiency of a blockchain.
2.データやトランザクションを検証するためにブロックチェーンネットワークに流すデータが少なくて済む。これにより、ブロックチェーンの効率が向上します。
3.They allow for Simple Payment Verification (SPV), which helps you to verify a transaction without downloading an entire block or blockchain. This allows you to send and receive transactions using a light-client node — more commonly known as a crypto wallet.
3.ブロックやブロックチェーン全体をダウンロードすることなく、トランザクションを検証することができるSimple Payment Verification（SPV）を可能にします。これにより、ライトクライアントノード（一般的には暗号ウォレットとして知られています）を使用してトランザクションを送受信することができます。
When verifying data using a Merkle tree, there is a Prover and a Verifier:
マークルツリーを用いてデータを検証する場合、ProverとVerifierが存在する。
・A Prover: Does all the calculation to create the merkle root (just a hash!)
証明者。マークルルートを作成するための全ての計算を行う（単なるハッシュ！）。
・A Verifier: Does not need to know all the values to know for certain one value is in the tree
検証者：すべての値を知らなくても、ある値が木に含まれることを確実に知ることができる。
What is the difference between ‘to prove’ and ‘to verify’ in maths?
Merkle trees are a huge benefit to the Verifier. You either produce a proof successfully, meaning data verification passes, or you don't, meaning your piece of data was not present when the Merkle root hash was calculated (or you performed the calculation wrong!).
マークルツリーは、検証者にとって大きなメリットとなる。証明に成功した場合は、データの検証が成功したことを意味し、失敗した場合は、そのデータがマークルルートのハッシュを計算したときに存在しなかったことを意味する（あるいは計算が間違っていたことを意味する！）。
Logarithmic Scaling
対数スケーリングについて
The amount of proof pieces that you need scales logarithmically to the size of the array of data you need to feed into the Merkle tree hash algorithm.
必要な証明片の量は、マークルツリーハッシュアルゴリズムに入力するデータの配列のサイズに対数的に比例する。
Merkle Tree Vocabulary Summary
マークルツリーに関する用語のまとめ
Final terminology for Merkle trees:
マークルツリーに関する用語のまとめです。
・Merkle tree: a structure used in computer science to validate data
マークルツリー：コンピュータサイエンスにおいて、データの検証を行うために用いられる構造体。
・Merkle root: the hash contained in the block header, which is derived from the
hashes of all other transactions in the block
マークルルート：ブロックヘッダに含まれるハッシュであり、ブロックヘッダ内の他のトランザクションのハッシュから導出される。
・Merkle path: represents the information which the user needs to calculate the expected value for the Merkle root for a block, from their own transaction hash contained in that block. The Merkle path is used as part of of the Merkle proof
マークルパス：ブロックに含まれる自分のトランザクションハッシュから、ブロックのマークルパスの期待値を計算するために必要な情報を表す。マークルパスはマークル証明の一部として使用される。
・Merkle proof: proves the existence of a specific transaction in a specific block (without the user needing to examine all the transactions in the block). It includes the Merkle root and the Merkle path
マークル証明：特定のブロックに特定のトランザクションが存在することを（ユーザがブロック内の全取引を調べることなく）証明するもの。マークルルートとマークルパスを含む。
Conclusion
結論
Merkle trees are a very popular data structure in blockchains. It's important to understand the low-level of blockchain storage and the implications of such decisions. Keeping data storage lean and efficient is the reason behind using structures like Merkle trees - this understanding is essential as you start building out dApps, you always want to be lean and efficient with your data storage. Why? Because on Ethereum, the less efficient your use of data storage, the more expensive your program will be for you and your users.
マークルツリーは、ブロックチェーンで非常によく使われるデータ構造です。ブロックチェーンのストレージの低レベルと、そのような決定の意味を理解することが重要です。データストレージを無駄なく効率的に保つことが、マークルツリーのような構造を使用する背景にあります。この理解は、dAppsを構築し始めるときに不可欠であり、常にデータストレージを無駄なく効率的にしたいと思うものです。なぜでしょうか？Ethereumでは、データストレージの使用効率が悪ければ、ユーザーにとってあなたのプログラムはより高価になるからです(ガス代が高くなる)。
In the next section, we will look at Patricia Merkle Tries, a data structure widely used in Ethereum.
次のセクションでは、Ethereumで広く使用されているデータ構造であるPatricia Merkle Triesについて見ていきます。
<next chapter>
Patricia Merkle Tries
パトリシアマークルトライ
Previous Section Recap
前回のまとめ
In the previous section, we looked at Merkle trees, a tree data structure that provides an efficient way to verify n exists in m.
前節では、m個の中にn個が存在することを効率的に検証できる木構造であるマークルツリーについて説明しました。
Since Merkle trees are hash-based data structures, they inherit the cryptographic properties of the hash functions themselves! Data integrity is strong because proofs are either right or wrong. You can't fool the cryptography!
マークルツリーはハッシュベースのデータ構造なので、ハッシュ関数そのものの暗号学的性質を受け継いでいます！証明は正しいか間違っているかのどちらかなので、データの完全性は強い。暗号を騙すことはできない!
Merkle trees are good for blockchain scalability and decentralization. The less heavy in size a blockchain is, the easier it is for more people to run a node. Even then, a full node is not necessary all the time. Wallets are lightweight clients that use schemes like SPV to communicate with the blockchain via a full node.
マークルツリーはブロックチェーンのスケーラビリティと分散化に適しています。ブロックチェーンのサイズが重くないほど、より多くの人がノードを運営しやすくなります。それでも、フルノードは常に必要なわけではありません。ウォレットは、SPVのようなスキームを使用して、フルノードを介してブロックチェーンと通信する軽量なクライアントです。
Intro
序章
Bitcoin was the first blockchain-based decentralized network ever. It popularized the use of Merkle trees for scalable transaction inclusion. Ethereum also uses Merkle trees but since Ethereum is a completely different design, it also uses one other important tree data structure for some of its data storage needs: Patricia Merkle Tries.
ビットコインは史上初のブロックチェーンベースの分散型ネットワークである。ビットコインは、スケーラブルなトランザクションの包含のためにマークルツリーを使用することを普及させた。Ethereumもマークルツリーを使用していますが、Ethereumは全く異なるデザインであるため、データストレージのニーズの一部に、もう1つの重要な木データ構造も使用しています。Patricia Merkle Triesです。
This is the last data structure heavy day. If you've made it this far, you are doing fantastic! Patricia Merkle Tries are the first introduction into Ethereum-specific fundamentals, let's dive in...
これが最後のデータ構造のヘビーな日です。ここまで来れたなら、あなたは素晴らしいことをしていますよ！Patricia Merkle TriesはEthereum特有の基礎知識への最初の導入であり、飛び込んでみましょう...
REVIEW: Bitcoin: Block Architecture
レビュー：Bitcoin：ブロックアーキテクチャ
In the previous section, we covered how Merkle trees are used to efficiently record a large amount of transactions into blocks, without needing to actually include them all - the merkleRootHash is all that is needed to commit those transactions.
前節では、大量のトランザクションを効率的にブロックに記録するためにMerkleツリーを使用する方法について説明しました。
First Look: Ethereum Block Architecture
チラ見：イーサリアムのブロックアーキテクチャ
Bitcoin's architecture is simple: it's a ledger that keeps track of transactions using a UTXO model. Since Ethereum keeps track of a larger amount of state data, the block architecture is completely different:
ビットコインのアーキテクチャはシンプルで、UTXOモデルを使用してトランザクションを追跡する台帳です。イーサリアムはより大量の状態データを記録しているため、ブロックアーキテクチャは全く異なるものとなっています。
Why are you showing me block architectures, aren't we covering trees?
なぜブロック・アーキテクチャを見せるのですか？ツリーを扱うのではないのですか？
Well, because these blocks contain references to the tree data structures we are focusing on. The main goal here of showing the block architecture first is: by the end of this lesson, you should be familiar with three of the staple Ethereum block properties included in the diagram above: State Root, Transaction Root, Receipt Root - just like in the last section we covered what the merkleRootHash was in the context of a Bitcoin block, we will now look at three new similar tree uses in Ethereum.
それは、これらのブロックには、私たちが注目しているツリーデータ構造への参照が含まれているからです。ブロックアーキテクチャが最初に示すここでの主要なゴールは、このレッスンの終わりまでに、上の図に含まれるEthereumブロックの主な3つのプロパティに精通することです。それはState Root、Transaction Root、Receipt Root - ちょうど前回のセクションでビットコインブロックのコンテキストでmerkleRootHashが何であるかをカバーしたように、今度はEthereumで用いられる3つの似た新しいツリーを見てみましょう。
Woah, that's a lot of properties in an Ethereum block! Don't worry, we will cover these further in the bootcamp. We have to tackle the low-level ones first. ;)
うわー、イーサリアムのブロックにはたくさんのプロパティがあるんですねー。心配しないでください、ブートキャンプでこれらをさらにカバーします。まずは低レベルのものに取り組まないといけませんね ;)
REVIEW: Merkle Trees in Bitcoin
レビュー：Bitcoinのマークルツリー
Merkle trees are fantastic for transactions. They are the perfect data structure. Transactions are static and should never change after being committed. They are "set in stone" via the Merkle hash root construction. Merkle trees are not a data structure fit for editting, so edit time -- how efficient it is to change a record -- does not matter here.
マークルツリーは取引に最適です。完璧なデータ構造である。トランザクションは静的であり、コミットされた後は決して変更されるべきではありません。マークルハッシュルート構造によって「不変」となる。マークルツリーは編集に適したデータ構造ではないので、編集時間、つまり記録を変更する効率がどうであるかは重要ではありません。
The main goal behind their usage is to prove the consistency of data as the blockchain grows. Thanks to Merkle trees, we can rest assured that a transaction existed at one point in time in a block. How? Just by constructing the Merkle proof! Not only this, Merkle proof construction is extremely efficient at scale since they are computationally fast to compute and require only small chunks of data to be communicated over the network.
それら用途の背後にある主な目的は、ブロックチェーンが成長するにつれて、データの一貫性を証明することです。マークルツリーのおかげで、あるブロックのある時点にある取引が存在したことを保証することができる。どのようにして？マークル証明書を作成するだけです！これだけでなく、マークル証明の構築は計算速度が速く、ネットワーク上で通信するデータの塊が小さくて済むため、規模に応じて非常に効率的です。
Trees in Ethereum
イーサリアムにおけるツリー
Ethereum makes use a data structure called a radix trie, also referred to as a Patricia trie or a radix tree and combines this data structure with a Merkle tree to create a Patricia Merkle Trie.
Ethereumでは、Patricia TrieやRadix Treeとも呼ばれるRadix Trieというデータ構造を利用し、このデータ構造とマークルツリーを組み合わせてPatricia Merkle Trieを作成しています。
Patricia Trie + Merkle Tree = Patricia Merkle Trie (pronounced either "tree" or "try")
Patricia Trie + Merkle Tree = Patricia Merkle Trie (発音は「ツリー」または「トライ」)
Radix Trie
ラディックス・トライ
"Trie" comes from the word "retrieval", to give you a hint as to what Patricia Merkle Tries (also referred to as Patricia Merkle Trees 🎄) optimize for.
Trie "は "retrieval "から来ており、Patricia Merkle Tries (Patricia Merkle Trees 🎄とも呼ばれる)が何のために最適化するのかを知るヒントとなる。
A radix trie is a tree-like data structure that is used to retrieve a string value by traversing down a branch of nodes that store associated references (keys) that together lead to the end value that can be returned:
radixのトライはツリー状のデータ構造で、文字列の値を取得するために、関連する参照（キー）を格納するノードの枝を走査して、最終的な値を返すために使用されるものです。
In grouping associated keys together, our search for the end value is optimized and more efficient
関連するキーをグループ化することで、最終値の探索が最適化され、より効率的になります。
Patricia Merkle Trees
パトリシア・マークル・ツリー
A Merkle Patricia trie is a data structure that stores key-value pairs, just like a hash table. In addition to that, it also allows us to verify data integrity and the inclusion of a key-value pair.
マークルパトリシアトライは、ハッシュテーブルのようにKey-Valueペアを格納するデータ構造である。さらに、データの整合性やKey-Valueペアが含まれているかどうかの検証も可能である。
PMTs groups similar-value nodes together in the tree. That way, searching for "HELP" leads you along the same path as searching for "HELLO" - the first three letters are shared entries of different words. Good for space efficiency and read/write efficiency.
PMTは、ツリーの中で似たような値を持つノードをグループ化します。これにより、"HELP "を検索しても "HELLO "を検索するのと同じ経路をたどることになる。最初の3文字は異なる単語の共有エントリである。スペース効率と読み込み/書き込みの効率に優れています。
Patricia Merkle Trees are basically Merkle trees on steroids! Efficient for data verification needs, but also efficient for editting that data.
パトリシア・マークル・ツリーは、基本的にマークル・ツリーである。データ検証のニーズにも効率的だが、そのデータを編集するのにも効率的だ。
Patricia??
P = Practical/実用的
A = Algorithm/アルゴリズム
T = To/To
R = Retrieve/取り出す
I = Information/情報
C = Coded/コード化された
I = In/In
A = Alphanumeric/英数字
The root node of this PMT is empty so we can store other words not starting with ‘n’, like "apple" or "hello".
このPMTのルートノードは空なので、「apple」や「hello」のように「n」で始まらない他の単語を格納することができます。
Why Does Ethereum Use a Merkle Patricia Trie?
なぜEthereumはMerkle Patricia Trieを使用するのか？
There are typically two different types of data:
通常、2種類のデータがあります。
・Permanent
恒久的
・Once a transaction occurs, that record is sealed forever
一度トランザクションが発生すると、その記録は永久に封印される
・This means that once you locate a transaction in a block’s transaction trie, you can return to the same path over and over to retrieve the same result
つまり、あるブロックのトランザクショントライでトランザクションを見つけたら、同じパスを何度も辿って同じ結果を得ることができる
Ephemeral
一時的
・In the case of Ethereum, account states change all the time! (ie. A user receives some ether, interacts with a contract, etc)
・イーサリアムの場合、アカウントの状態は常に変化しています。(例: ユーザーがethを受け取ったり、コントラクトとやり取りをしたり)
・nonce, balance, storageRoot, codeHash
nonce, balance, storageRoot, codeHashなど。
It makes sense that permanent data, like mined transactions, and ephemeral data, like Ethereum accounts (balance, nonce, etc), should be stored separately. Merkle trees, again, are perfect for permanent data. PMTs are perfect for ephemeral data, which Ethereum is in plenty supply of.
マイニングされたトランザクションのような永続的なデータと、イーサリアムのアカウント（残高、nonceなど）のような一時的なデータを別々に保存することは理にかなっています。永続的なデータにはマークルツリーが最適です。PMTは、イーサリアムが大量に保有する一時的なデータに最適です。
Unlike transaction history, Ethereum account state needs to be frequently updated. The balance and nonce of accounts is often changed, and what’s more, new accounts are frequently inserted, and keys in storage are frequently inserted and deleted.
取引履歴とは異なり、イーサリアムのアカウントステートは頻繁に更新される必要がある。アカウントの残高やnonceは頻繁に変更され、さらに、新しいアカウントが頻繁に挿入され、ストレージ内のキーも頻繁に挿入・削除される。
Ethereum Block Header
イーサリアムのブロックヘッダー
The block header contains many pieces of data. Remember back to Week 1 PoW Mining? The block header is the hash result of all of the data elements contained in a block. It's kind of like the gift-wrap of all the block data.
ブロックヘッダには多くのデータが含まれています。第1週目のPoWマイニングを思い出してください。ブロックヘッダは、ブロックに含まれるすべてのデータ要素のハッシュ結果です。ブロックヘッダは、ブロックに含まれるすべてのデータ要素のハッシュ結果であり、すべてのブロックデータのギフト包装のようなものです。
If you look at the Ethereum architecture diagram at the beginning of this lesson, the block header ends up hashing all of the data properties of the block. It also includes:
このレッスンの最初にあるイーサリアムのアーキテクチャ図を見ると、ブロックヘッダはブロックのすべてのデータプロパティをハッシュ化することになるのです。また、以下のようなものも含まれています。
・State Root: the root hash of the state trie
ステートルート: ステートトライのルートハッシュ。
・Transactions Root: the root hash of the block's transactions
Transactions Root: ブロックのトランザクションのルートハッシュ。
・Receipts Root: the root hash of the receipts trie
Receipts Root: Receiptsトライのルートハッシュ。
Ethereum: State Trie
イーサリアムのブロックヘッダーについて
As shown in the above diagram, the state trie acts as a mapping between addresses and account states.
上図のように、ステートトライはアドレスとアカウントの状態をマッピングする役割を果たします。
It can be seen as a global state that is constantly updated by transaction executions.The Ethereum network is a decentralized computer and state trie is considered hard drive. All the information about accounts are stored in the world state trie and you can retrieve information by querying it.
イーサリアムネットワークは分散型コンピュータであり、ステートトライはハードディスクとみなされる。アカウントに関するすべての情報はワールド・ステート・トライに格納され、クエリによって情報を取得することができる。
Account Example
アカウントの例
As mentioned above, the state trie is just a mapping that uses an address as the key and the account state (nonce, balance, etc) as the value returned.
前述の通り、ステートトライはアドレスをキーに、アカウントの状態（nonce、残高など）を戻り値とするマッピングに過ぎない。
This is what you would get back from a JavaScript request to the Ethereum world state. Just an object containing some data! That is all the account state is... but this is too much data to store in each block, so a root hash of it commits the data per block.
これは、JavaScriptでEthereumのworld stateにリクエストしたときに返ってくるものです。データを含むただのオブジェクトです！これがアカウントの状態のすべてです...しかし、これは各ブロックに保存するには多すぎるデータなので、これのルートハッシュがブロックごとにデータをコミットします。
Ethereum: Transaction Trie
イーサリアム ：トランザクショントライ
The transaction trie records transactions in Ethereum. Once the block is mined, the transaction trie is never updated.
トランザクショントライは、イーサリアムのトランザクションを記録する。ブロックが採掘されると、トランザクショントライは更新されることはない。
Each transaction in Ethereum records multiple pieces specific to each transaction such as gasPrice and value.
イーサリアムの各トランザクションには、gasPriceやvalueなど、各トランザクションに固有の複数の要素が記録される。
Transaction Example
トランザクションの例
You've probably seen this via services like Etherscan! All these services do is query the Ethereum blockchain for transaction data and then index it into an organized transaction viewer.
Etherscanのようなサービスを通じてこれを見たことがあるのではないでしょうか! これらのサービスが行うのは、イーサリアムのブロックチェーンに取引データを照会し、整理された取引ビューアにインデックスを付けるだけです。
You can even try querying the transactions trie directly using Alchemy Composer. Just take a random tx hash and use the eth_getTransactionByHash method - you'll get a response looking much like the object in the picture above.
Alchemy Composer を使って、直接トランザクショントライを照会することもできます。ランダムな Tx ハッシュをとって eth_getTransactionByHash メソッドを使えば、上の図のようなレスポンスが返ってくるでしょう。
Ethereum: Transaction Receipt Trie
イーサリアム: トランザクションレシートライ
The transaction receipt trie records receipts (outcomes) of transactions. Data including gasUsed and logs (events emitted are contained here!).
トランザクションレシートトライは、トランザクションのレシート(結果)を記録するものである。gasUsedやログ（発せられたイベントもここに含まれる！)も含んでいる。
Once the block is mined, the transaction receipt trie is never updated.
ブロックが採掘されると、トランザクション結果のトライが更新されることはない。
Transaction Receipt Example
トランザクションレシートの例
Try it out on the Alchemy Composer - just make sure to change the method to eth_getTransactionReceipt.
Alchemy Composer で試してみてください - メソッドを eth_getTransactionReceipt に変更することだけ確認してください。
Conclusion
結論
The above diagram is an excellent visualization into how the tries all end up being committed in every block via their root hash. The raw data is stored elsewhere in Ethereum, particularly archive nodes.
上の図は、トライがすべてルートハッシュを介してブロックごとにコミットされる様子を見事に視覚化したものです。生データはEthereumの他の場所、特にアーカイブノードに保存されます。
Take a look back over the various architectures included in this lesson! Does the Ethereum block architecture diagram look less threatening? If so, good! We are learning as we go and we've just covered some of the lowest-level aspects of Ethereum data storage. Very few people learn these fundamentals. These are super important! Not only does learning them give you a more holistic understanding of Ethereum, this is knowledge applicable in all of computer science and even physics 🤯.
このレッスンに含まれる様々なアーキテクチャを振り返ってみてください。イーサリアムのブロックアーキテクチャ図が、あまり脅威でないように見えますか？もしそうなら、よかったです! 私たちは学びながら進んでおり、Ethereumデータストレージの最も低いレベルの側面をいくつか取り上げただけです。これらの基本的なことを学ぶ人はほとんどいません。これらは超重要です! これらを学ぶことで、Ethereumをより全体的に理解できるだけでなく、これはコンピュータサイエンスのすべて、さらには物理学でも適用できる知識です。
The important takeaway of this lesson is to understand why the low-level data structures used by Ethereum are used: to optimize data space and read/write efficiency.
このレッスンの重要な点は、イーサリアムで使用される低レベルのデータ構造がなぜ使用されているかを理解することです：それはデータスペースと読み取り/書き込みの効率を最適化するためです。
<next chapter>
TRIES
Trie
A trie is pronounced like "try". It comes from the word "retrieval".
トライは「try」のような発音です。これは「検索」という言葉から来ている。
This particular data structure works well with storing strings, especially ones with a many common prefixes.
この特殊なデータ構造は、文字列、特に多くの共通接頭辞を持つ文字列を格納するのに適している。
Let's take a look at a trie:
それでは、トライを見てみましょう。
trie
This trie contains three words. Can you figure out what they are?
このトライは3つの単語を含んでいます。これらが何であるか分かりますか？
They are Hermit, Hello, and Helipad.
「Hermit」「Hello」「Helipad」です。
To figure out why, simply follow the arrows.
矢印をたどっていくと、その理由がわかります。
All three words start with HE so this prefix is shared. After that we branch out to RMIT for HERMIT and L for both HELLO and HELIPAD.
この3つの単語はすべてHEで始まるので、この接頭辞は共有されています。その後、HERMITはRMIT、HELLOとHELIPADはLと枝分かれしています。
Let's build a trie data structure to learn more about it.
もっと詳しく知るためにトライデータ構造を構築してみましょう。
<next chapter>
1: Constructors
コンストラクタ
Trie & Trie Node
トライとトライノード
We're going to create two data structures for the first stage. The Trie and TrieNode.
最初のステージでは、2つのデータ構造を作成する予定です。TrieとTrieNodeです。
The Trie will represent the entire data structure, while the TrieNode will represent each letter in the structure.
トライはデータ構造全体を表し、TrieNodeは構造中の各文字を表します。
Let's see this in a simple example:
これを簡単な例で見てみましょう。
simple example
簡単な例
This single trie data structure has four nodes. It has a root node, which points to a node with the key h, which points to a node with the key e, which points to a node with the key y.
この1つのトライデータ構造には4つのノードがある。ルート・ノードがあり、それがキーhを持つノードを指し、キーeを持つノードを指し、キーyを持つノードを指す。
Your Goal: Constructors
目標：コンストラクタ
Implement the constructor function for both the Trie and TrieNode class.
Trie クラスと TrieNode クラスの両方にコンストラクタ関数を実装します。
For each TrieNode instance, add four properties:
各 TrieNode インスタンスについて、4 つのプロパティを追加します。
1.key - This will be passed to the node, it is the letter stored as a string
key - これはノードに渡されるもので、文字列として格納されている文字です。
2.children - This will be an object, containing the children elements, by default set it to an empty object
children - これは、子要素を含むオブジェクトになります。デフォルトでは、空のオブジェクトに設定します。
3.isWord - This will be a boolean, whether or not the node finishes a word, set it to false by default.
isWord - これはブール値で、ノードが単語を終了するかどうかを表します。
For each Trie instance, add a single property:
各Trieインスタンスについて、プロパティを1つ追加します。
1.root - This will be an instance of TrieNode that contains a null key. The null key will indicate that this is the top parent in the list.
root - これは、nullキーを含むTrieNodeのインスタンスになります。nullキーは、これがリスト内のトップペアレントであることを示します。
Be sure to store these properties on this so they are accessible for every instance of the class.
これらのプロパティは、クラスのすべてのインスタンスでアクセスできるように、必ずこの上に格納してください。
<next chapter>
2: Insert
挿入
Simple Trie Insert
単純なトライの挿入
Let's focus on that example from the previous stage:
前段の例に注目しましょう。
simple example
To create this trie, we would simply do this:
このトライを作成するには、シンプルにこうします。
trie = new Trie();
trie.insert('HEY');
In fact, if you look at the test cases, that's exactly what it does!
実際、テストケースを見てみると、まさにその通りです。
Let's see the data we're expecting in our nodes:
ノードに期待するデータを見てみましょう。
Data Expected
期待されるデータ
Here, the box inside the JSON indicates a reference to the other node.
ここで、JSONの中のボックスは、他のノードへの参照を示しています。
The root node stores a reference to the H node in its H key of its children property.
ルートノードでは、childrenプロパティのHキーに、Hノードへの参照が格納される。
The first node stores a reference to the E node in its E key of its children property.
最初のノードは、そのchildrenプロパティのEキーにEノードへの参照を格納している。
Notice that only the last node Y has set the isWord to true! This property should indicate if the node is the end of a word.
最後のノード Y だけは、isWord を true に設定していることに注意してください。このプロパティは、そのノードが単語の末尾であるかどうかを示すものでなければなりません。
Your Goal: Link the Nodes
目標：ノードをリンクする
Add a new function called insert on the Trie class.
Trie クラスに insert という新しい関数を追加します。
This function will take a string word like "hey". Split this word up by character and create nodes for each character.
この関数は、「hey」のような文字列の単語を受け取ります。この単語を文字ごとに分割し、それぞれの文字に対応するノードを作成します。
Link the nodes children property as indicated in the above image.
上の画像のように、ノードのchildrenプロパティをリンクします。
Be sure to also update the properties isWord property.
プロパティの isWord プロパティも必ず更新してください。
<next chapter>
3: Insert Branching
分岐の挿入
Branching
分岐
An important aspect of the trie is its ability to branch and have many children. Let's take a look at a larger example:
トライの重要な点は、分岐して多くの子を持つことができる点です。より大きな例を見てみましょう。
Larger Example
In this example, both the letter E and the first L will have two children.
この例では、文字Eと最初のLの両方が2つの子供を持つことになります。
The data for the E would be:
Eのデータは次のようになります。
{
key: "E",
isWord: false,
children: {
'L': lNode,
'R': rNode,
}
}
Here the hNode, lNode, and rNode are object references to those particular nodes.
ここで、hNode、lNode、rNodeは、それらの特定のノードへのオブジェクト参照である。
In the above example, there are three nodes that should have isWord set to true. They are D, O and T.
上の例では、isWordがtrueに設定されるべきノードが3つある。それらはD、O、Tである。
Your Goal: Implement Branching
目標：分岐の実装
Add branching to the insert function. When a second child comes up, be sure to add it as well.
挿入関数に分岐を追加します。2 番目の子が現れたら、必ずそれも追加してください。
Depending on how you implemented your logic on the previous stage, you may already be passing the test cases!
前のステージでどのようにロジックを実装したかにもよりますが、すでにテストケースを通過しているかもしれません!
<next chapter>
4: Contains
含有
Does it Contain the Word?
単語を含んでいますか？
With the trie we should be able to quickly figure out if the data structure contains a word we are looking for.
トライを使えば、データ構造に探している単語が含まれているかどうかがすぐにわかるはずだ。
For example, if we were to add a few words:
例えば、いくつかの単語を追加するとしたら。
const trie = new Trie();
trie.insert('happy');
trie.insert('healthy');
We should be able to check for those words:
これらの単語をチェックすることができるはずです。
console.log( trie.contains('happy') ); // true
console.log( trie.contains('healthy') ); // true
Without it picking up on words that aren't contained:
含まれていない単語を拾うことなく。
console.log( trie.contains('whimsical') ); // false
console.log( trie.contains('health') ); // false
Because these words are not in the trie, it should return false
これらの単語はトライに含まれていないので、falseを返すはずです。.
Notice that second example is a bit tricky! The word "healthy" is in the trie, while the word "health" is not.
2番目の例は少し厄介であることに注意してください! healthy "という単語はトライに含まれますが、"health "という単語は含まれません。
Your Goal: Implement Contains
目標：Containsの実装
Add a function contains to the Trie class.
Trie クラスに contains という関数を追加してください。
This function should take a string word and return true/false depending on whether the word is in our trie or not.
この関数は、文字列の単語を受け取り、その単語がトライに含まれるかどうかに応じて true/false を返す必要があります。
<next chapter>
Merkle Trees in Ethereum
イーサリアムにおけるマークルツリーについて
Here is a technical overview of merkling in Ethereum by Vitalik Buterin. Vitalik highlights several reasons for using Patricia Merkle Tries in Ethereum:
Vitalik Buterin氏によるEthereumにおけるマークリングの技術的な概要を紹介します。Vitalik氏は、Ethereumでパトリシア・マークル・トライを使用する理由をいくつか挙げています。
・Efficient data verification (from its merkle properties)
効率的なデータ検証（そのマークルの特性から）
・More complex light-client queries
より複雑なライトクライアントクエリ
・Can quickly change values and only recompute a portion of the tree (prevents some DDOS attack vectors)
素早く値を変更し、ツリーの一部だけを再計算できる（一部のDDOS攻撃ベクトルを防ぐことができる）
・There is a limit to the depth of the tree, which prevents other DDOS attack vectors
ツリーの深さに制限があるため、他のDDOS攻撃ベクトルを防ぐことができる
・The order of the updates do not matter for the root hash
ルートハッシュでは、更新の順番は関係ない
Ethereum nodes maintain four tries:
Ethereumのノードは（以下）4つのトライを保持する。
・A state trie which contains information about Ethereum accounts
イーサリアムアカウントに関する情報を含むステートトライ
・A storage trie which is where we can write persistent data from smart contracts
スマートコントラクトから永続的なデータを書き込むことができるストレージトライ
・A transactions trie which contains the transactions stored in a block
ブロックに格納されたトランザクションを含むトランザクショントライ
・A receipts trie which contains log/event information from contracts
コントラクトからのログ/イベント情報を格納するレシートトライ
Here is a good overview of Patricia Merkle Trees on Medium. This article references some images from a stack overflow answer which are extremely helpful to look at!
Patricia Merkle Treesの概要は、Mediumに掲載されているこちらの記事が参考になります。この記事では、stack overflowの回答からいくつかの画像を参照しており、これを見るのは非常に役に立ちます!
This starts with a good overview and quickly gets highly technical! Read as far as you are interested, we will not need to know the exact details of the Ethereum data storage implementation.
これは良い概要から始まり、すぐに高度に技術的な内容になっていきます Ethereumのデータストレージ実装の正確な詳細を知る必要はありませんので、興味のある範囲でお読みください。
Quick Note on RLP
RLP(Recursive Length Prefix)に関する簡単なメモ
We're going to be seeing RLP come up quite a bit. This is a serialization format used in Ethereum, you can think of it like JSON. It is used to send data from one machine to another in a format where the machine knows how to parse the data.
これからRLPがかなり出てきます。これはEthereumで使用されるシリアライズフォーマットで、JSONのようなものだと考えてください。あるマシンから別のマシンへ、マシンがデータを解析する方法を知っているフォーマットでデータを送信するために使用されます。
You can find more information on RLP here.
RLPの詳細については、こちらをご覧ください。
As the docs here point out "In summary, RLP is like a binary encoding of JSON, if JSON were restricted only to strings and arrays."
このドキュメントで指摘されているように、”要するに、RLPは、文字列と配列だけを制限されたJSONのバイナリエンコーディングのようなもの”です。