跳到主要内容

4 篇博文 含有标签「data-structure」

查看所有标签

Merkle Trees: Real-World Applications and Implementation Examples

· 阅读需 10 分钟

1. Introduction to Merkle Trees​

A Merkle tree (or hash tree) is a cryptographic data structure that efficiently verifies the integrity of large datasets. It's a binary tree where each leaf node contains a cryptographic hash of a data block, and each non-leaf node contains the hash of its child nodes' hashes.

Key Properties​

  • Efficient verification: Verify data integrity without downloading entire dataset
  • Tamper-evident: Any change propagates up to root hash
  • Space-efficient: Proofs are logarithmic in size relative to data

2. How Merkle Trees Work​

Basic Structure​

Root Hash (HR)
/ \
Hash(H1+H2) Hash(H3+H4)
/ \ / \
Hash(A) Hash(B) Hash(C) Hash(D)
| | | |
Block A Block B Block C Block D

Verification Process:

  1. Client has trusted root hash (HR)
  2. Server provides data block + minimal proof hashes
  3. Client recomputes path to root and compares with trusted HR

3. Real-World Applications​

3.1 Blockchain & Cryptocurrencies​

Bitcoin Implementation:

# Simplified Bitcoin Merkle tree example
import hashlib
import struct

def bitcoin_hash(data):
"""Double SHA-256 used in Bitcoin"""
return hashlib.sha256(hashlib.sha256(data).digest()).digest()

def build_merkle_tree(transactions):
"""Build Merkle tree from transaction list"""
if not transactions:
return None

# Hash all transactions
leaf_hashes = [bitcoin_hash(tx.encode()) for tx in transactions]

# Build tree level by level
while len(leaf_hashes) > 1:
# Handle odd number of nodes by duplicating last
if len(leaf_hashes) % 2 == 1:
leaf_hashes.append(leaf_hashes[-1])

parent_level = []
for i in range(0, len(leaf_hashes), 2):
# Concatenate and hash
combined = leaf_hashes[i] + leaf_hashes[i + 1]
parent_hash = bitcoin_hash(combined)
parent_level.append(parent_hash)

leaf_hashes = parent_level

return leaf_hashes[0] # Root hash

# Example usage
transactions = ["Tx1: Alice → Bob 1 BTC", "Tx2: Bob → Charlie 0.5 BTC"]
merkle_root = build_merkle_tree(transactions)
print(f"Merkle Root: {merkle_root.hex()}")

Why Bitcoin Uses Merkle Trees:

  • SPV (Simplified Payment Verification): Light clients verify transactions without full blockchain
  • Block structure: Each block header contains merkle root of all transactions
  • Efficient proofs: Prove transaction inclusion with ~log₂(n) hashes

3.2 Version Control Systems​

Git Implementation:

# Git-style Merkle tree for file versioning
class GitMerkleTree:
def __init__(self):
self.objects = {} # Git object store

def git_hash(self, content):
"""Git-style hash: "blob" + size + content"""
header = f"blob {len(content)}\0"
data = header.encode() + content
return hashlib.sha1(data).hexdigest()

def store_file(self, filename, content):
"""Store file in Git object database"""
obj_hash = self.git_hash(content)
self.objects[obj_hash] = content
return obj_hash

def build_tree_object(self, entries):
"""Build tree object from directory entries"""
# Format: "mode type hash\tname\n"
tree_content = b""
for mode, obj_type, obj_hash, name in entries:
entry = f"{mode} {obj_type} {obj_hash}\t{name}\n"
tree_content += entry.encode()

# Hash tree object
header = f"tree {len(tree_content)}\0"
return hashlib.sha1(header.encode() + tree_content).hexdigest()

def create_commit(self, tree_hash, parent_hash, message, author):
"""Create commit object pointing to tree"""
commit_content = f"tree {tree_hash}\n"
if parent_hash:
commit_content += f"parent {parent_hash}\n"
commit_content += f"author {author}\n"
commit_content += f"committer {author}\n\n"
commit_content += f"{message}\n"

# Hash commit
header = f"commit {len(commit_content)}\0"
commit_hash = hashlib.sha1(header.encode() + commit_content.encode()).hexdigest()
self.objects[commit_hash] = commit_content
return commit_hash

# Example Git-like structure
repo = GitMerkleTree()
file_hash = repo.store_file("README.md", b"# My Project\nVersion 1.0")
tree_hash = repo.build_tree_object([
("100644", "blob", file_hash, "README.md")
])
commit_hash = repo.create_commit(tree_hash, None, "Initial commit", "Alice <alice@example.com>")
print(f"Commit Hash: {commit_hash}")

3.3 Distributed File Systems​

IPFS (InterPlanetary File System) Example:

class IPFSMerkleDAG:
"""IPFS uses Merkle DAGs (Directed Acyclic Graphs)"""

def __init__(self):
self.cid_store = {} # Content ID → data

def chunk_data(self, data, chunk_size=1024):
"""Split data into fixed-size chunks"""
return [data[i:i+chunk_size] for i in range(0, len(data), chunk_size)]

def create_merkledag(self, data):
"""Create Merkle DAG from data chunks"""
chunks = self.chunk_data(data)
chunk_hashes = []

# Hash each chunk
for i, chunk in enumerate(chunks):
chunk_hash = hashlib.sha256(chunk).digest()
chunk_hashes.append(chunk_hash)
self.cid_store[chunk_hash.hex()] = chunk

# Build tree from chunks
nodes = chunk_hashes

while len(nodes) > 1:
new_level = []
for i in range(0, len(nodes), 2):
if i + 1 < len(nodes):
combined = nodes[i] + nodes[i + 1]
else:
combined = nodes[i] + nodes[i] # Duplicate for odd

parent_hash = hashlib.sha256(combined).digest()
new_level.append(parent_hash)
# Store link information
self.cid_store[parent_hash.hex()] = {
'type': 'parent',
'children': [nodes[i].hex(),
nodes[i + 1].hex() if i + 1 < len(nodes) else nodes[i].hex()]
}
nodes = new_level

return nodes[0] # Root CID (Content Identifier)

def get_proof(self, target_chunk_index, root_cid):
"""Generate inclusion proof for a chunk"""
proof = []
current_hash = root_cid

# Traverse tree to build proof
# (Simplified - real implementation would track path)

# For chunk at index 2 (binary 10), need sibling hashes
# Proof would contain: sibling of chunk 2, then parent's sibling
return proof

# Example: Storing a file in IPFS-like system
ipfs = IPFSMerkleDAG()
file_data = b"This is a large file that needs to be distributed across the network..."
root_cid = ipfs.create_merkledag(file_data)
print(f"IPFS Root CID: {root_cid.hex()}")
print(f"Total chunks stored: {len([k for k, v in ipfs.cid_store.items() if isinstance(v, bytes)])}")

3.4 Certificate Transparency (Google)​

Auditing SSL/TLS Certificates:

class CertificateTransparencyLog:
"""CT Log implementation using Merkle trees"""

def __init__(self):
self.entries = [] # List of certificate entries
self.tree_size = 0
self.root_hashes = [] # Store historical roots

def add_certificate(self, certificate):
"""Add certificate to log"""
# Create leaf entry
timestamp = struct.pack('>Q', int(time.time() * 1000))
entry_data = timestamp + certificate.encode()
leaf_hash = hashlib.sha256(b'\x00' + entry_data).digest()

self.entries.append({
'certificate': certificate,
'timestamp': timestamp,
'leaf_hash': leaf_hash
})

# Rebuild tree
self.tree_size += 1
root_hash = self._rebuild_tree()
self.root_hashes.append({
'size': self.tree_size,
'root_hash': root_hash,
'timestamp': time.time()
})

return leaf_hash, root_hash

def _rebuild_tree(self):
"""Rebuild tree from current entries"""
leaf_hashes = [entry['leaf_hash'] for entry in self.entries]

# Build tree
while len(leaf_hashes) > 1:
next_level = []
for i in range(0, len(leaf_hashes), 2):
left = leaf_hashes[i]
right = leaf_hashes[i + 1] if i + 1 < len(leaf_hashes) else left
combined = b'\x01' + left + right
parent_hash = hashlib.sha256(combined).digest()
next_level.append(parent_hash)
leaf_hashes = next_level

return leaf_hashes[0] if leaf_hashes else None

def get_audit_proof(self, leaf_index, tree_size=None):
"""Generate audit proof for a certificate"""
if tree_size is None:
tree_size = self.tree_size

proof = []
node_index = leaf_index
last_index = tree_size - 1

# Calculate required sibling hashes
while tree_size > 1:
if node_index % 2 == 1:
# Node is right child, need left sibling
sibling_index = node_index - 1
else:
# Node is left child, need right sibling (if exists)
sibling_index = node_index + 1 if node_index + 1 < tree_size else node_index

# Get sibling hash (simplified - real would fetch from tree)
if sibling_index < len(self.entries):
proof.append(self.entries[sibling_index]['leaf_hash'])

# Move up tree
node_index //= 2
tree_size = (tree_size + 1) // 2

return proof

def verify_inclusion(self, leaf_hash, proof, root_hash, leaf_index, tree_size):
"""Verify certificate inclusion in log"""
current_hash = leaf_hash

for sibling_hash in proof:
if leaf_index % 2 == 0:
# Current is left child
combined = b'\x01' + current_hash + sibling_hash
else:
# Current is right child
combined = b'\x01' + sibling_hash + current_hash

current_hash = hashlib.sha256(combined).digest()
leaf_index //= 2

return current_hash == root_hash

# Example Certificate Transparency log
ct_log = CertificateTransparencyLog()

# Add certificates
cert1 = "example.com SSL cert issued by Let's Encrypt"
leaf1, root1 = ct_log.add_certificate(cert1)
print(f"Added cert1, Root hash: {root1.hex() if root1 else 'None'}")

cert2 = "google.com SSL cert"
leaf2, root2 = ct_log.add_certificate(cert2)
print(f"Added cert2, New root: {root2.hex() if root2 else 'None'}")

# Get and verify inclusion proof
proof = ct_log.get_audit_proof(leaf_index=0)
verified = ct_log.verify_inclusion(leaf1, proof, root2, 0, 2)
print(f"Inclusion verified: {verified}")

3.5 Database Systems (Apache Cassandra)​

Anti-Entropy Repair with Merkle Trees:

class CassandraMerkleTree:
"""Merkle trees for data synchronization in distributed databases"""

def __init__(self, token_ranges):
self.token_ranges = token_ranges # Data partitions
self.range_trees = {} # Merkle tree per range

def build_range_tree(self, range_data):
"""Build Merkle tree for a token range"""
# Sort keys for consistent ordering
sorted_keys = sorted(range_data.keys())

# Create leaf hashes: hash(key + value + timestamp)
leaves = []
for key in sorted_keys:
value, timestamp = range_data[key]
leaf_data = f"{key}:{value}:{timestamp}".encode()
leaf_hash = hashlib.md5(leaf_data).digest() # Cassandra uses MD5
leaves.append(leaf_hash)

# Build binary tree
while len(leaves) > 1:
parents = []
for i in range(0, len(leaves), 2):
if i + 1 < len(leaves):
combined = leaves[i] + leaves[i + 1]
else:
combined = leaves[i] + leaves[i] # Duplicate last
parent_hash = hashlib.md5(combined).digest()
parents.append(parent_hash)
leaves = parents

return leaves[0] if leaves else None

def sync_nodes(self, node_a_data, node_b_data):
"""Compare data between two nodes using Merkle trees"""
differences = []

for token_range in self.token_ranges:
# Build trees for this range on both nodes
tree_a = self.build_range_tree(node_a_data.get(token_range, {}))
tree_b = self.build_range_tree(node_b_data.get(token_range, {}))

if tree_a != tree_b:
# Trees differ - need detailed comparison
print(f"Range {token_range} differs between nodes")
differences.append(token_range)

# In real Cassandra, would recursively compare subtrees
# to pinpoint exact differing keys

return differences

# Example: Database anti-entropy repair
db_merkle = CassandraMerkleTree(token_ranges=["0-100", "101-200", "201-300"])

# Simulate two nodes with slightly different data
node_a_data = {
"0-100": {"key1": ("value1", 123456), "key2": ("value2", 123457)},
"101-200": {"key3": ("value3", 123458)}
}

node_b_data = {
"0-100": {"key1": ("value1", 123456), "key2": ("value2-different", 123460)}, # Different
"101-200": {"key3": ("value3", 123458)}
}

# Find differences
diffs = db_merkle.sync_nodes(node_a_data, node_b_data)
print(f"Ranges needing repair: {diffs}")

4. Performance Analysis​

Storage and Computational Overhead​

OperationTime ComplexitySpace ComplexityExample (1M items)
Build treeO(n)O(n)~1M hashes
Generate proofO(log n)O(log n)~20 hashes
Verify proofO(log n)O(1)20 hash operations
Update single leafO(log n)O(log n)Update path to root

Hash Function Choices​

ApplicationHash FunctionWhy Chosen
BitcoinSHA-256×2Security, ASIC resistance
GitSHA-1Historical, migrating to SHA-256
IPFSSHA-256Balance of speed/security
EthereumKeccak-256SHA-3 standard
CassandraMD5Speed for large datasets

5. Advanced Variations​

5.1 Merkle Patricia Trie (Ethereum)​

# Simplified Ethereum state trie concept
class MerklePatriciaNode:
def __init__(self):
self.children = {} # Hex character → child node
self.value = None
self.hash = None

def update_hash(self):
"""Recursively update hashes after modification"""
child_hashes = []
for char, child in sorted(self.children.items()):
if child.hash:
child_hashes.append(char.encode() + child.hash)

if self.value:
child_hashes.append(b'value:' + self.value)

if child_hashes:
combined = b''.join(child_hashes)
self.hash = hashlib.sha3_256(combined).digest()
else:
self.hash = None

return self.hash

5.2 Sparse Merkle Trees​

class SparseMerkleTree:
"""For key-value stores with empty defaults"""

def __init__(self, depth=256):
self.depth = depth # Typically 256 for 256-bit keys
self.zero_hashes = self._compute_zero_hashes()
self.root = self.zero_hashes[-1] # Root of empty tree
self.leaves = {} # position → value hash

def _compute_zero_hashes(self):
"""Precompute hashes for empty subtrees"""
zero_hashes = [b'\x00' * 32] # Leaf level (hash of empty)

for i in range(self.depth):
prev = zero_hashes[-1]
zero_hashes.append(hashlib.sha256(prev + prev).digest())

return zero_hashes

def update(self, key, value):
"""Update leaf at key position"""
key_int = int.from_bytes(key, 'big')
value_hash = hashlib.sha256(value).digest()

# Update leaf
self.leaves[key_int] = value_hash

# Recompute path to root
# (Implementation would update only affected path nodes)

def generate_proof(self, key):
"""Generate inclusion/non-inclusion proof"""
key_int = int.from_bytes(key, 'big')
proof = []

# Collect sibling hashes at each level
# If leaf doesn't exist, use zero hash for that level

return proof

6. Security Considerations​

Potential Vulnerabilities​

  1. Second preimage attacks: Ensure different encoding for leaf vs internal nodes
  2. Tree imbalance: Can affect proof size guarantees
  3. Collision resistance: Dependent on underlying hash function
  4. Denial of service: Large trees can be expensive to compute

Best Practices​

  1. Use domain separation: Prefix leaf hashes with 0x00, internal with 0x01
  2. Salt hashes: Add random nonce to prevent precomputation attacks
  3. Regular root publication: Publish roots in trusted locations
  4. Monitor hash function developments: Plan for cryptographic agility

7. Implementation Checklist​

When implementing Merkle trees:

  • Choose appropriate hash function for security/speed needs
  • Implement proper domain separation (leaf vs internal)
  • Handle odd number of nodes (duplicate last vs other methods)
  • Cache intermediate hashes for performance
  • Provide efficient proof generation/verification APIs
  • Include serialization/deserialization methods
  • Add comprehensive test cases (empty tree, single element, large trees)
  • Consider using existing libraries (OpenSSL, cryptography.io)

8. Conclusion​

Merkle trees provide an elegant solution to data integrity verification problems across distributed systems. Their logarithmic proof sizes make them practical for everything from blockchain transactions to version control and database synchronization. The specific implementation details (hash function, tree structure, proof format) vary by application, but the core principle remains the same: building a cryptographic hierarchy that efficiently captures the state of an entire dataset in a single root hash.

Real-world implementations often extend basic Merkle trees with optimizations like caching, incremental updates, and specialized variants (Merkle Patricia Tries, sparse Merkle trees) to address specific use case requirements.

A sample ABI of CCBusERC20 contract

· 阅读需 7 分钟

For the ABI of CCBusERC20, you should include all public and external methods that you want to be accessible from outside the contract. This includes:

  1. All methods from IERC20 interface (required for ERC20 compliance)
  2. Any additional public methods specific to your contract
  3. Events that you want to be queryable
  4. Constructor (only needed for deployment)

Here's what should be included based on your contract:

Required Methods (from IERC20):​

"function decimals() view returns (uint256)",
"function symbol() view returns (string)",
"function name() view returns (string)",
"function totalSupply() view returns (uint256)",
"function balanceOf(address) view returns (uint256)",
"function transfer(address, uint256) returns (bool)",
"function allowance(address, address) view returns (uint256)",
"function approve(address, uint256)",
"function transferFrom(address, address, uint256)"

Additional Public Methods (from CCBusERC20):​

"function deadAddress() view returns (address)",
"function decreaseAllowance(address, uint256) returns (bool)",
"function getCirculatingSupply() view returns (uint256)",
"function increaseAllowance(address, uint256) returns (bool)",
"function owner() view returns (address)"

Events:​

"event Approval(address indexed owner, address indexed spender, uint256 value)",
"event Transfer(address indexed from, address indexed to, uint256 value)"

Constructor:​

"constructor(string[] stringParams, address[] addressParams, uint256[] numberParams, bool[] boolParams)"

Your current ABI is correct and complete:​

const abiCCBusERC20 = [
"constructor(string[] stringParams, address[] addressParams, uint256[] numberParams, bool[] boolParams)",
"event Approval(address indexed owner, address indexed spender, uint256 value)",
"event Transfer(address indexed from, address indexed to, uint256 value)",
"function allowance(address owner, address spender) view returns (uint256)",
"function approve(address spender, uint256 amount)",
"function balanceOf(address account) view returns (uint256)",
"function deadAddress() view returns (address)",
"function decimals() view returns (uint256)",
"function decreaseAllowance(address spender, uint256 subtractedValue) returns (bool)",
"function getCirculatingSupply() view returns (uint256)",
"function increaseAllowance(address spender, uint256 addedValue) returns (bool)",
"function name() view returns (string)",
"function owner() view returns (address)",
"function symbol() view returns (string)",
"function totalSupply() view returns (uint256)",
"function transfer(address recipient, uint256 amount) returns (bool)",
"function transferFrom(address sender, address recipient, uint256 amount)"
] as const;

What to exclude:​

  • Internal/private methods (_approve, _transfer, _basicTransfer, _msgSender, _msgData)
  • Library functions (SafeMath, Address)
  • The receive() function (special fallback function doesn't need ABI entry)

CCBusERC20.sol​

// Created By: CC-Bus
// Website: https://ccbus.cc
// Telegram: https://t.me/CCBus
// The Best Tool for Token Management

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.18;


contract Context {

function _msgSender() internal view returns (address) {
return payable(msg.sender);
}

function _msgData() internal view returns (bytes memory) {
this; // silence state mutability warning without generating bytecode - see https://github.com/ethereum/solidity/issues/2691
return msg.data;
}
}


library SafeMath {
function add(uint256 a, uint256 b) internal pure returns (uint256) {
uint256 c = a + b;
require(c >= a, "SafeMath: addition overflow");

return c;
}

function sub(uint256 a, uint256 b) internal pure returns (uint256) {
return sub(a, b, "SafeMath: subtraction overflow");
}

function sub(
uint256 a,
uint256 b,
string memory errorMessage
) internal pure returns (uint256) {
require(b <= a, errorMessage);
uint256 c = a - b;

return c;
}

function mul(uint256 a, uint256 b) internal pure returns (uint256) {
if (a == 0) {
return 0;
}

uint256 c = a * b;
require(c / a == b, "SafeMath: multiplication overflow");

return c;
}

function div(uint256 a, uint256 b) internal pure returns (uint256) {
return div(a, b, "SafeMath: division by zero");
}

function div(
uint256 a,
uint256 b,
string memory errorMessage
) internal pure returns (uint256) {
require(b > 0, errorMessage);
uint256 c = a / b;
// assert(a == b * c + a % b); // There is no case in which this doesn't hold

return c;
}

function mod(uint256 a, uint256 b) internal pure returns (uint256) {
return mod(a, b, "SafeMath: modulo by zero");
}

function mod(
uint256 a,
uint256 b,
string memory errorMessage
) internal pure returns (uint256) {
require(b != 0, errorMessage);
return a % b;
}
}

library Address {
function isContract(address account) internal view returns (bool) {

bytes32 codehash;
bytes32 accountHash = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470;

assembly {
codehash := extcodehash(account)
}
return (codehash != accountHash && codehash != 0x0);
}

function sendValue(address payable recipient, uint256 amount) internal {
require(
address(this).balance >= amount,
"Address: insufficient balance"
);

// solhint-disable-next-line avoid-low-level-calls, avoid-call-value
(bool success, ) = recipient.call{value: amount}("");
require(
success,
"Address: unable to send value, recipient may have reverted"
);
}

function functionCall(address target, bytes memory data)
internal
returns (bytes memory)
{
return functionCall(target, data, "Address: low-level call failed");
}

function functionCall(
address target,
bytes memory data,
string memory errorMessage
) internal returns (bytes memory) {
return _functionCallWithValue(target, data, 0, errorMessage);
}

function functionCallWithValue(
address target,
bytes memory data,
uint256 value
) internal returns (bytes memory) {
return
functionCallWithValue(
target,
data,
value,
"Address: low-level call with value failed"
);
}

function functionCallWithValue(
address target,
bytes memory data,
uint256 value,
string memory errorMessage
) internal returns (bytes memory) {
require(
address(this).balance >= value,
"Address: insufficient balance for call"
);
return _functionCallWithValue(target, data, value, errorMessage);
}

function _functionCallWithValue(
address target,
bytes memory data,
uint256 weiValue,
string memory errorMessage
) private returns (bytes memory) {
require(isContract(target), "Address: call to non-contract");

(bool success, bytes memory returndata) = target.call{value: weiValue}(
data
);
if (success) {
return returndata;
} else {
if (returndata.length > 0) {
assembly {
let returndata_size := mload(returndata)
revert(add(32, returndata), returndata_size)
}
} else {
revert(errorMessage);
}
}
}
}

interface IERC20 {
function decimals() external view returns (uint256);

function symbol() external view returns (string memory);

function name() external view returns (string memory);

function totalSupply() external view returns (uint256);

function balanceOf(address who) external view returns (uint);

function transfer(
address recipient,
uint256 amount
) external returns (bool);

function allowance(
address owner,
address spender
) external view returns (uint256);

function approve(address _spender, uint _value) external;

function transferFrom(address _from, address _to, uint _value) external ;

event Transfer(address indexed from, address indexed to, uint256 value);
event Approval(
address indexed owner,
address indexed spender,
uint256 value
);
}


contract CCBusToken is Context, IERC20{
using SafeMath for uint256;
using Address for address;

string private _name;
string private _symbol;
uint256 private _decimals;

mapping(address => uint256) _balances;
mapping(address => mapping(address => uint256)) private _allowances;

address public immutable deadAddress =
0x000000000000000000000000000000000000dEaD;
uint256 private _totalSupply;

constructor(
string[] memory stringParams,
address[] memory addressParams,
uint256[] memory numberParams,
bool[] memory boolParams
) {
require(addressParams.length==0);
require(boolParams.length==0);

address receiveAddr = tx.origin;
_name = stringParams[0];
_symbol = stringParams[1];
_decimals = numberParams[0];
_totalSupply = numberParams[1];
_balances[receiveAddr] = _totalSupply;
emit Transfer(address(0), receiveAddr, _totalSupply);
}

function name() public view override returns (string memory) {
return _name;
}


function symbol() public view override returns (string memory) {
return _symbol;
}

function decimals() public view override returns (uint256) {
return _decimals;
}

function totalSupply() public view override returns (uint256) {
return _totalSupply;
}

function owner() public view returns (address) {
return deadAddress;
}

function balanceOf(address account) public view override returns (uint256) {
return _balances[account];
}

function allowance(address owner1, address spender)
public
view
override
returns (uint256)
{
return _allowances[owner1][spender];
}

function increaseAllowance(address spender, uint256 addedValue)
public
virtual
returns (bool)
{
_approve(
_msgSender(),
spender,
_allowances[_msgSender()][spender].add(addedValue)
);
return true;
}

function decreaseAllowance(address spender, uint256 subtractedValue)
public
virtual
returns (bool)
{
_approve(
_msgSender(),
spender,
_allowances[_msgSender()][spender].sub(
subtractedValue,
"ERC20: decreased allowance below zero"
)
);
return true;
}

function approve(address spender, uint256 amount)
public
override

{
_approve(_msgSender(), spender, amount);

}

function _approve(
address owner1,
address spender,
uint256 amount
) private {
require(owner1 != address(0), "ERC20: approve from the zero address");
require(spender != address(0), "ERC20: approve to the zero address");

_allowances[owner1][spender] = amount;
emit Approval(owner1, spender, amount);
}

function getCirculatingSupply() public view returns (uint256) {
return _totalSupply.sub(balanceOf(deadAddress));
}

//to recieve ETH from uniswapV2Router when swaping
receive() external payable {}

function transfer(address recipient, uint256 amount)
public
override
returns (bool)
{
_transfer(_msgSender(), recipient, amount);
return true;
}

function transferFrom(
address sender,
address recipient,
uint256 amount
) public override {
_transfer(sender, recipient, amount);
_approve(
sender,
_msgSender(),
_allowances[sender][_msgSender()].sub(
amount,
"ERC20: transfer amount exceeds allowance"
)
);

}

function _transfer(
address sender,
address recipient,
uint256 amount
) private returns (bool) {
require(sender != address(0), "ERC20: transfer from the zero address");
require(recipient != address(0), "ERC20: transfer to the zero address");
return _basicTransfer(sender, recipient, amount);
}

function _basicTransfer(
address sender,
address recipient,
uint256 amount
) internal returns (bool) {
_balances[sender] = _balances[sender].sub(
amount,
"Insufficient Balance"
);
_balances[recipient] = _balances[recipient].add(amount);
emit Transfer(sender, recipient, amount);
return true;
}
}

Merkle Tree in Chinese

· 阅读需 3 分钟

Merkle Tree(默克尔树)在区块链、密码学和数据完整性验证中是一个非常核心的概念。它是一种树状数据结构,用来高效而安全地验证数据的完整性。


🌳 一、Merkle Tree 是什么?​

Merkle Tree 是一种二叉树结构,每个叶子节点是某一笔数据的哈希值,每个非叶子节点是其子节点哈希值的组合再哈希后的结果,直到根节点 —— Merkle Root。

📌 特点:​

  • 快速验证某条数据是否属于某批数据(O(log n))
  • 数据完整性校验非常高效
  • 广泛用于区块链中(比特币、以太坊)以验证交易

🧩 二、图示说明​

假设我们有 4 个交易 Tx0, Tx1, Tx2, Tx3:

Merkle Root
│
┌───────┴────────┐
│ │
Hash01 Hash23
┌────┴────┐ ┌────┴────┐
Hash0 Hash1 Hash2 Hash3
│ │ │ │
Tx0 Tx1 Tx2 Tx3

哈希过程:​

  • Hash0 = hash(Tx0),Hash1 = hash(Tx1)
  • Hash01 = hash(Hash0 + Hash1)
  • Merkle Root = hash(Hash01 + Hash23)

💡 三、Merkle Tree 的作用​

✅ 在区块链中主要用来:​

用途说明
验证交易是否在区块中比如比特币 SPV(轻节点)用来验证一笔交易是否在区块中,无需下载整个区块
保证数据不可篡改即使更改一笔交易,Merkle Root 也会完全不同
批量处理大量数据的完整性验证用于 IPFS、文件校验、区块快照

🧪 四、一个简单的 Merkle Tree 实现(用 JavaScript)​

import { createHash } from 'crypto';

function sha256(data: string) {
return createHash('sha256').update(data).digest('hex');
}

// 构建 Merkle Tree 并返回根节点
function buildMerkleTree(leaves: string[]): string {
if (leaves.length === 0) return '';

let level = leaves.map(sha256);

while (level.length > 1) {
const nextLevel: string[] = [];

for (let i = 0; i < level.length; i += 2) {
const left = level[i];
const right = level[i + 1] ?? left; // 如果是奇数,复制最后一个
nextLevel.push(sha256(left + right));
}

level = nextLevel;
}

return level[0];
}

// 示例
const txs = ['tx0', 'tx1', 'tx2', 'tx3'];
console.log('Merkle Root:', buildMerkleTree(txs));

🔍 五、如何验证某笔交易在 Merkle Tree 中?​

验证步骤是:

  1. 获取你那笔交易的哈希(比如 tx1 → h1)
  2. 获取你需要验证路径的兄弟节点哈希(称为“Merkle Proof”)
  3. 逐层拼接并计算,直到得出 Merkle Root
  4. 看是否和真正的 Merkle Root 匹配

这样你就可以仅凭部分数据验证整批数据完整性,这在区块链轻节点中尤为重要。


📦 六、真实区块链场景​

以太坊中:​

  • 并不直接使用二叉 Merkle Tree,而是使用改进版:Merkle Patricia Trie 来处理状态(账户、余额等)
  • 区块头中的 transactionsRoot、stateRoot 等字段就是 Merkle 根

比特币中:​

  • 区块中的 merkle_root 字段是所有交易的 Merkle 根
  • 支持轻节点(SPV)通过 Merkle Proof 验证交易

🧾 七、总结重点​

项目内容
是什么二叉哈希树,用于验证大批数据中某一条数据是否存在
为什么重要高效验证、防篡改、轻节点支持
区块链用途交易验证、状态验证、数据完整性证明
优点空间占用小,验证时间快(对数级别),可组合证明

Merkle Tree

· 阅读需 2 分钟

🔍 What is a Merkle Tree?​

A Merkle Tree (also called a binary hash tree) is a tree structure where:

  • Every leaf node contains the cryptographic hash of a data block.
  • Every non-leaf node contains the hash of the concatenation of its child hashes.

It’s used in blockchain systems (e.g., Bitcoin, Ethereum) to efficiently and securely verify the integrity of large sets of data, such as transactions.


🌳 Merkle Tree Structure​

Example with 4 transactions (T1, T2, T3, T4):

Root
/ \
H12 H34
/ \ / \
H1 H2 H3 H4
  • H1 = hash(T1), H2 = hash(T2), etc.
  • H12 = hash(H1 + H2), H34 = hash(H3 + H4)
  • Root = hash(H12 + H34)

This root hash is called the Merkle Root.


🧠 Benefits of Merkle Tree​

  • Efficient and secure verification of data integrity.
  • Only need a small part of the tree (a Merkle proof) to verify a data block.
  • Used in SPV (Simplified Payment Verification) in Bitcoin.

💻 JavaScript Sample Code Using crypto​

const crypto = require('crypto');

// Hashing function
function sha256(data) {
return crypto.createHash('sha256').update(data).digest('hex');
}

// Build Merkle Tree from an array of transactions
function buildMerkleTree(transactions) {
if (transactions.length === 0) return [''];

// Step 1: Hash each transaction
let level = transactions.map(tx => sha256(tx));

// Step 2: Build tree up to the root
while (level.length > 1) {
const nextLevel = [];

for (let i = 0; i < level.length; i += 2) {
const left = level[i];
const right = i + 1 < level.length ? level[i + 1] : left; // duplicate last if odd
const combined = left + right;
nextLevel.push(sha256(combined));
}

level = nextLevel;
}

return level[0]; // Merkle root
}

// Example usage
const txs = ['tx1-data', 'tx2-data', 'tx3-data', 'tx4-data'];
const merkleRoot = buildMerkleTree(txs);

console.log('Merkle Root:', merkleRoot);

📎 Notes:​

  • This sample assumes a binary Merkle tree.
  • If there's an odd number of leaves, the last hash is duplicated to make a pair.
  • You can also implement Merkle Proof logic to verify a leaf's inclusion using hashes up to the root.

Another drawn​

Merkle Root
│
┌───────┴────────┐
│ │
Hash01 Hash23
┌────┴────┐ ┌────┴────┐
Hash0 Hash1 Hash2 Hash3
│ │ │ │
Tx0 Tx1 Tx2 Tx3