Tree

No tag
Publish Date:   2023-05-19

diffrent type of tree structure

simple tree

Picsee-20230517150030.png

binary tree

Picsee-20230517150055.png
a parent must have two children. that’s a rule of binary tree, if the parent have more than two children, it can’t be called binary tree.

tree vs linked tree.

a linked list also is tree - just really long one that only has one child per parent in a long continuous chain. a tree is not necessarily be a linked list.
for example

class linkedList {
  this.data = data;
  this.next = null;
};
class tree {
  this.data = data;
  this.children = [];
}

noticed the treenode holds the typical data and an array to continue refer to any children of the (parent) node. the linkedlist just keep tract to next node.

tree vocabulary summary

Picsee-20230517150651.png

  • key, node id
  • siblings, nodes under the same parent and on the same level
  • root, the top node of the tree.
  • subtree, once u isolate a part of broader tree, u can form a brand new tree with new relationship.

searching binary tree

Picsee-20230517151506.png
searching tree must have those properties:

  • it’s binary tree.
  • the left one must be less than the parent
  • the right one must be greater than the parent

the sbt implement.

Tree

class Tree {
    constructor() {
        this.root = null;
    }
    addNode(node,  current = null) {
      if (!this.root) {
        this.root = node;
        return;
      }
    
      if (!current) {
        // when we assign this.root to current, we just reference the root to current. so when we change current, we also will change root.
        current = this.root;
      }

      if (node.data < current.data) {
        if (!current.left) {
          current.left = node;
        } else {
          // if we use recursive, the current will be assigned be new object, but the root also will be impacted.
          this.addNode(node,  current.left);
        }
      } else {
        if (!current.right) {
          current.right = node;
        } else {
          this.addNode(node,  current.right);
        }
      }
    }
    hasNode(value, current=null){
      if(!this.root) return false;
      if(!current) {
        current = this.root
      }
      if(value === current.data) {
        return true
      } else if ((value < current.data) && current.left) {
        return this.hasNode(value, current.left)
      } else if ((value > current.data) && current.right) {
        return this.hasNode(value, current.right)
      }

      return false
    }
}

module.exports = Tree;

Node

class Node {
    constructor(data) {
        this.data = data 
        this.left = null;
        this.right = null;
    }
}

module.exports = Node;

use case

// 创建一个新的二叉搜索树对象
const tree = new Tree();

// 创建一些节点并添加到树中
tree.addNode({ data: 7 });
tree.addNode({ data: 6 });
tree.addNode({ data: 5 });
tree.addNode({ data: 4 });
tree.addNode({ data: 3 });
tree.addNode({ data: 6 });
tree.addNode({ data: 8 });

// 打印根节点
console.log('根节点:', tree.root);

merkle tree

Merkle tree is a data structure that allows us to make efficient verification that data belong in large set of data.
They are commonly used in p2p where efficient proof of this nature will help increase the scalability of the network.
A Merkle tree is collection reduce to a single hash.

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

Each signle letter reprsent hash. The combined letter represent concatenated hash that have been combined and then hashed to form new hash.

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 incosistencies in all kinds of distributed systems.

For blockchain, storing transactions as Merkle tree allows us to look at a block and verify that a transaction was part of it by only having part of the data set.

example

the benefits of the merkle tree design – a recursion hashin-based algorithm – is that allows for efficient proof that some data exists within the root hash constrution(actually contained in the block). a merkle proof confirmed specific transactions represented by a leaf or branch within merkle hash root.

Picsee-20230519184902.png

if i want prove c exist in the block, we only need use the root, h(a-b) and h(e-h). so that is effience.

Logarithmic scalming.

Picsee-20230519185805.png

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. keeping the data storage lean and efficent is the reason behind using structured like Merkle tree.

Merkle Tree Vocabulary Summary

  • Merkle tree, a special binary tree, that allowed just use targetProveHash and proof to verify is that equal with root.
  • Merkle root, the hash contained in the block header, which is derived from the hash of all the transactions in the block.
  • Merkle path, represents the information that user need to calculate the expected value for Merkle root for a block, from their owner transactions hash contained in that block.
  • Merkle proof, prove the existence of a specific transaction in a specific block(without the user needing to examine all the transaction in block). it includes Merkle root and Merkle proof.

conclusion

Merkle tree is a very popular structure in blockchain. it’s importatnt to understand the low-level of blockchain storage and the implications of such a disicion

partricia Merkle tries

Intro

Bitcoin is the frist blockchain-based contralization newwork ever. it popularizes the use of Merkle tree for scalable transactions inclusion. Ethereum also use Merkle tree but since Ethereum is different design. it also use ont other important tree data structures for some of its data storage needs: Partricia Merkle tries.

Ethereum block structure

Picsee-20230519204553.png

Trees in Ethereum

Ethereum make use a tree called “radix trie, also referenced to as a Partricia Merkle tree” and combine this data structure with Merkle tree to create Partricia Merkle Tries.

A redix trie is a tree like data structure that used to retrieve a string by value triversing down a branch of nodes that store acciocated key that together lead to the end value can be returned.

A Merkle trie is a data structure that store key-value pairing. just like hash-table. in addition to that. it allow us to verify data integrity and the inclusion of key-value pairs.

Picsee-20230519204553.png

PMTs groups similar-value nodes together in the tree. this way searching for ‘help’ leads u along the same path as ‘hello’, the first three letter is same. good for space and efficiency.

why does Etherum use a PMTs?

there are two different type of data:
Permenant:

  • once a transaction occurs, that record is sealed forever.
    • that means once u locate the transaction in a PMTs, u can return to the same path over and over to retrieve the same result.

Ephemeral:

  • the Etherum, account state change all the time(ie. A user recieve some ether, interact with contract…)
  • nounce, balance, storageRoot, codeHash.

It make sense Permenant and Ephemeral need storage separately. Merkle Tree, a perfect data structure for Permenant. PMTs are perfect for Ephemeral data.

Etherum Block header

the block header contains many pieces of data. the block header is the hash result of all of the data element contained in the block. it’s like giftwrap of the all of the block data.

  • state root, the root hash of the state trie
  • transaction root, the root hash of the transaction
  • receipt root, the root hash of the receipt trie

State Trie

Picsee-20230519214704.png

as show in the above diagram, the state trie is mapping between address and account state.

it can be seen a global state that is constanly updated by transaction executions. all the information about account are stored in the world state trie and u can retrieve informantion by query it.

Account Example
as mentioned above, the state trie is just mapping that uses an address as the key and the account state(nount, balance) as the value returned.

Transaction Trie

the transaction trie records transaction in Ethereum. once the block is mined, the transaction trie is never update.

Picsee-20230519221351.png

each transaction in Ethereum record multiple pieces properties for each transaction such as gasPrice and value.

Picsee-20230519222004.png
You can even try querying the transactions trie directly using Alchemy Composer.

Transaction Receipt Trie

outcomes of transactions. data including gasUsed and logs(events emitted are contained here)
Once the block is mined, the transaction receipt trie is never updated.
Picsee-20230519222342.png
Try it out on the <a herf='https://composer.alchemy.com/'>Alchemy Composer</a> - just make sure to change the method to eth_getTransactionReceipt

Conclusion

Picsee-20230519222433.png

the above diagram is an excellent visulaztion into how the trie all end up being committed in every block via their root hash. the raw data is stored elsewhere in Etherum, particularly achive nodes.

good trview for PMTSs

aka

ethereum: 以太坊
Blockchain: 区块链
Crypto： 加密
crytocurrencts: 加密货币
decentralized: 去中心化
bitcoin： 比特币，第一个基于区块链技术实现的加密货币
fiancial incentives： 金融奖励
mining the rewards： 挖矿
deterministic: 确定性
pseudorandom: 伪随机
collsion resistant: 抗碰撞
consensus: 共识，一个网络对数据的状态达成共识。
censorship：审查
bribe： 贿赂
drill home： 钻研
relatively travel：相对较小的
infeasible： 不可能
symmetric: 对称
digital signature: 数字签名
RSA: 非对称加密的经典实现
ECDSA： bitcoin采用的非对称加密算法
ether： 以太币
address： 交易发起方类似于ip, bitcoin 使用checksum and base58, ethereum is last 20 bytes of the hash of the public key.
Enforcement： 执行
consensus rules： 共识规则
consensus mechanisms：协商一致
inter-changeable: 可互换的
cumulative: 积累型
nakamoto consensus： 最长的chain将是其他节点接受的一个真正的链，他是由一条链积累的工作所决定的。
txs: transactions.
pos: proof of stack, pos中，参与者需要持有一定数量的crytocurrency，参与记账过程，相比pow，pos不需要大量的算力
pow: proof of work，miners通过计算来添加txs和block，需要消耗算力。可以增加security of blockchain
merkle root：默克尔根，用来验证和确认交易是否被篡改。
underlying: 底层
hashcash： Hashcash工作量证明功能由Adam Back于 1997 年发明，并建议用于反 DoS 用途
Byzantine General’s Problem： 在p2p场景下，如何证明每个机器都是在工作的。
manipulate： 操作
Genesis Block: 第一个加入到区块链中的块，初始块
cost-effective: 成本效益
UTXO：Unspent Transaction Output, 未使用的交易
Retrospective： 回顾
vulnerable： 脆弱的
light nodes: 轻节点 （存储块头的轻节点）
full nodes：完整节点（常规节点）
achieve nodes: 归档节点， 完整节点（已验证的存档节点）
bandwidth： 带宽
configure: 配置
variables： 变量
discrepancies： 差异
tradeoffs： 权衡利弊
contrast： 对比
unfakeable： 不可伪造
replicate： 复制
Satoshi: “Satoshi” refers to the smallest unit of the cryptocurrency Bitcoin
individual： 个人
multitude： 众多的
aggregate： 总数
expedite： 加快
hefty prize ： 巨额奖金
controlled supply： 受控供应
intentional: 故意的
quirk： 怪癖
denial: 否认
distinguish： 辨别
preceding： 前面
emerge： 出现
hierarchically: 层次分明
intimidating： 令人生畏的
underneath： 底下
infacting：连接
concatenate： 串联
optimization： 优化
inconsistencies: 不一致
deveration: 推导
arbitrary： 随意的
immutable： 不可变
implications: 含义
ledger： 账本
traversal: 遍历
PMTs: Partricia Merkle tries
sealed: 密封.
Permenant: 永恒的
Ephemeral： 短暂的
Constantly: 不断的
prefixes: 前缀
recursion: 递归
portion： 部分
adjacent: 邻近的
neat mechanisms: 整洁的机制
consists: 包含
crowdfunding: 众筹
parse： 解析

No tag
赏
  TOC