Merkel Patricia Tree

As stated on June 10, 2020 at 5:34 pm, a Merkle Tree is a way of structuring data that allows a large body of information to be verified for accuracy both extremely efficiently and quickly. The Merkle Tree is named after Ralph Merkle who wrote a paper titled, “A Certified Digital Signature” in August 1989. Satoshi Nakamoto’s essay that introduced Bitcoin titled “Bitcoin: A Peer-to-Peer Electronic Cash System”, in Section 7 references Merkle’s paper: “Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block’s hash, transactions are hashed in a Merkle Tree, with only the root included in the block’s hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored” (R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.) The Merkle trees have become a crucial component of blockchain technology and cryptocurrency. Every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. The records are hashed in the ledger, which effectively separates the proof of data from the data itself. Proving a transaction is valid only involves sending small amounts of information across the network

Patricia stands for Practical Algorithm To Retrieve Information Coded in Alphanumeric. Patricia is an algorithm which provides a flexible means of storing, indexing, and retrieving information in a large file, which is economical of index space and of reindexing time. It does not require rearrangement of text or index as new material is added. Therefore, in the Merkle Patricia Trees (MPT), as well as in the Merkle tree, every node has a hash value. Each node’s hash is decided by the sha3 hash value of its contents. This hash is also used as the key (normally defined as a string) that refers to the node. Ethereum uses MPTs with three different Merkle Roots for each block.