Giới thiệu

Cây Merkle là một trong những khái niệm quan trọng hỗ trợ nhiều công nghệ mà chúng ta sử dụng ngày nay như Git, blockchain và các hệ thống peer-to-peer như IPFS. Chúng cung cấp một cách hiệu quả để chứng minh rằng một mảnh dữ liệu thuộc về một tập hợp dữ liệu lớn hơn mà không cần phải tiết lộ hoặc truyền tải toàn bộ dữ liệu.

Tuy nhiên, cây Merkle thường chỉ được giới thiệu trong bối cảnh các hệ thống phân tán lớn. Vậy nếu bạn chỉ muốn thử nghiệm với chúng trên máy tính cá nhân mà không cần hạ tầng phức tạp thì sao? Đó chính là lúc SQLite trở nên hữu ích.

Trong hướng dẫn này, chúng ta sẽ xây dựng một cây Merkle bằng Python và lưu trữ nó trong SQLite. Cuối cùng, bạn sẽ có một dự án hoạt động có thể:

Tạo cây Merkle từ các chuỗi tùy ý.
Lưu trữ tất cả các nút—các nhánh và băm nội bộ—trong một cơ sở dữ liệu quan hệ.
Truy vấn các chứng cứ bao gồm cho bất kỳ lá nào.
Xác minh các chứng cứ dựa trên gốc đã lưu.
Kiểm tra và trực quan hóa cây bằng SQL hoặc các script trợ giúp.

Sự kết hợp này mang lại cho bạn một cấu trúc dữ liệu có thể kiểm chứng, không thể giả mạo và có thể truy vấn trong một tệp .db duy nhất.

Tất cả mã nguồn đều có sẵn trên GitHub.

Tại Sao Chọn SQLite?

Trước khi đi vào mã, hãy trả lời câu hỏi hiển nhiên: tại sao lại lưu trữ cây Merkle trong SQLite?

SQLite là một cơ sở dữ liệu nhẹ, có thể nhúng. Bạn không cần một máy chủ, một cụm, hoặc thậm chí là kết nối internet—chỉ cần một tệp. Điều này làm cho nó trở thành một lựa chọn lý tưởng cho:

Nhật ký không thể giả mạo
Lưu trữ nhật ký hoặc sự kiện như các lá, và sử dụng gốc Merkle để chứng minh rằng không có hàng nào bị thay đổi. Nếu ai đó thay đổi ngay cả một ký tự trong cơ sở dữ liệu, băm gốc sẽ không khớp.
Hệ thống blockchain nhẹ
Bạn có thể thử nghiệm với các khái niệm blockchain mà không cần xây dựng hạ tầng nặng nề. Trao đổi gốc Merkle và chứng cứ giữa các peer thay vì toàn bộ bảng.
Đồng bộ hóa hiệu quả
Hai thiết bị có cùng một tập dữ liệu có thể chỉ trao đổi gốc của chúng. Nếu chúng khác nhau, bạn có thể hòa giải từng nhánh thay vì sao chép mọi thứ.
Truy vấn có thể kiểm chứng
SQL mang lại cho bạn tốc độ và cấu trúc; cây Merkle cung cấp các chứng cứ. Kết hợp, bạn có thể thực hiện một truy vấn và cung cấp một đảm bảo mật mã rằng kết quả thuộc về một trạng thái cơ sở dữ liệu cụ thể.
Giáo dục và demo
SQLite giúp khái niệm trở nên cụ thể. Bạn có thể xem từng nút trong một bảng, kiểm tra nó bằng SQL và trực quan hóa cây.

Vì vậy, trong khi có vẻ bất thường, việc lưu trữ cây Merkle trong SQLite là một cách tuyệt vời để kết nối các cấu trúc mật mã với các cơ sở dữ liệu mà chúng ta đã sử dụng.

Cây Merkle Hoạt Động Như Thế Nào

Một cây Merkle là một cây nhị phân mà:

Lá chứa băm của dữ liệu thô.
Nút nội bộ chứa băm của sự kết hợp của các nhánh con của nó.
Băm gốc cam kết với toàn bộ tập dữ liệu.

Nếu bạn muốn chứng minh rằng “gamma” là một phần của tập dữ liệu, bạn không cần phải hiển thị mọi giá trị khác. Thay vào đó, bạn cung cấp các băm của các nhánh anh chị của nó dọc theo đường đến gốc. Người xác minh sẽ tính toán lại và kiểm tra xem nó có khớp với băm gốc đã lưu không.

Cấu Trúc Dự Án

Dự án Python của chúng ta rất đơn giản và không có phụ thuộc. Các tệp chính bao gồm:

Copy

├── main.py            # Ví dụ sử dụng
├── merkle_tree.py     # Lớp MerkleTree chính
├── print_proof.py     # CLI để in và xác minh chứng cứ
├── visualize_tree.py   # CLI để vẽ cây dưới dạng ASCII hoặc Graphviz
├── pyproject.toml     # Metadata và script
└── README.md

Mọi thứ chỉ sử dụng thư viện chuẩn của Python (hashlib, sqlite3, pathlib).

Lược Đồ SQLite

Trái tim của việc lưu trữ là một bảng duy nhất:

Copy

CREATE TABLE IF NOT EXISTS merkle_nodes (
  id INTEGER PRIMARY KEY,
  parent_id INTEGER,
  left_child_id INTEGER,
  right_child_id INTEGER,
  hash TEXT NOT NULL,
  level INTEGER NOT NULL,
  is_leaf BOOLEAN NOT NULL,
  data TEXT,
  FOREIGN KEY(parent_id) REFERENCES merkle_nodes(id),
  FOREIGN KEY(left_child_id) REFERENCES merkle_nodes(id),
  FOREIGN KEY(right_child_id) REFERENCES merkle_nodes(id)
);

Mỗi hàng là một nút. Các lá mang dữ liệu gốc; các nút nội bộ chỉ có băm. Các liên kết giữa cha và con cho phép bạn duyệt cây theo cả hai hướng.

Lớp `MerkleTree`

Logic chính nằm trong merkle_tree.py. Nó được bọc trong một lớp quản lý cả việc băm và lưu trữ cơ sở dữ liệu.

Khởi Tạo và Quản Lý Ngữ Cảnh

Copy

with MerkleTree("merkle_tree.db") as tree:
    root_id = tree.build_tree(["alpha", "beta", "gamma"])

Lớp này mở và đóng kết nối SQLite của nó tự động. Sử dụng khối with đảm bảo các tài nguyên được dọn dẹp.

Xây Dựng Cây

build_tree(data_blocks) thực hiện ba bước:

Băm các lá bằng SHA-256.
Từng bước ghép cặp chúng, băm các băm con cho đến khi một gốc được hình thành. Nếu có số lẻ, băm cuối cùng sẽ được nhân đôi (theo phong cách Bitcoin).
Chèn mỗi nút vào cơ sở dữ liệu và liên kết các mối quan hệ cha-con.

Phương thức này trả về ID của nút gốc cho sự tiện lợi.

Tạo Chứng Cứ

get_proof(leaf_id) đi từ một lá lên gốc, thu thập băm anh chị dọc đường. Mỗi bước cũng ghi lại xem nút hiện tại là một nhánh trái hay phải. Hướng đó quan trọng vì thứ tự kết hợp của các băm thay đổi kết quả.

Nếu nút hiện tại là nhánh trái, băm anh chị nằm bên phải → (sibling_hash, True).
Nếu nút hiện tại là nhánh phải, băm anh chị nằm bên trái → (sibling_hash, False).

Bằng cách này, người xác minh biết liệu có tính toán sha256(current + sibling) hay sha256(sibling + current).

Ví dụ đường chứng cứ:

Copy

[
    ("hash_of_right_sibling", True),   # nút hiện tại là trái
    ("hash_of_left_sibling", False),   # nút hiện tại là phải
    ("hash_of_right_sibling", True)    # nút hiện tại là trái
]

Trong quá trình xác minh, bạn bắt đầu từ băm của lá, sau đó ghép từng băm anh chị theo thứ tự chính xác cho đến khi bạn tính toán lại gốc.

Xác Minh

Cuối cùng, verify_proof(data_item, proof_path, expected_root) tính toán lại đường đi từ một lá đến gốc.

Nó hoạt động như sau:

Bắt đầu với băm SHA-256 của dữ liệu gốc.
Đối với mỗi (sibling_hash, is_left_child) trong đường chứng cứ:

Nếu is_left_child == True, nút hiện tại là nhánh trái, vì vậy tính toán:
Copy
```
 current = sha256((current + sibling_hash).encode())
```
Nếu is_left_child == False, nút hiện tại là nhánh phải, vì vậy tính toán:
Copy
```
 current = sha256((sibling_hash + current).encode())
```

Khi bạn lên đến đỉnh, so sánh kết quả với gốc đã lưu.

Ví dụ:

Copy

current = hashlib.sha256(data_item.encode()).hexdigest()
for sibling_hash, is_left_child in proof_path:
    if is_left_child:
        current = hashlib.sha256((current + sibling_hash).encode()).hexdigest()
    else:
        current = hashlib.sha256((sibling_hash + current).encode()).hexdigest()
print(current == expected_root)  # True nếu bao gồm hợp lệ

Điều này đảm bảo rằng chỉ có lá đúng, kết hợp với đúng thứ tự các băm anh chị, mới có thể tái tạo lại gốc.

Chạy Demo

main.py kết nối mọi thứ lại với nhau:

Copy

uv run main.py

Kết quả sẽ như sau:

Copy

ID nút gốc: 31
Lá: 3 5f9a...
Chứng cứ cho 'gamma': [('4f4a...', True), ('0cb0...', False), ('673e...', True)]
Xác minh: True
Cây Merkle đã lưu tại /absolute/path/merkle_tree.db

Điều này cho thấy:

Nút gốc đã được xây dựng.
Một chứng cứ cho "gamma" đã được tạo ra.
Việc xác minh thành công.
Toàn bộ cây được lưu trữ trong merkle_tree.db.

Kiểm Tra Với SQL

Vì mọi thứ đều ở trong SQLite, bạn có thể tự mình khám phá:

Copy

sqlite3 merkle_tree.db

Xem lược đồ và các nút mẫu:

Copy

.schema merkle_nodes
SELECT id, level, is_leaf, substr(hash,1,16) AS h, data
FROM merkle_nodes ORDER BY level, id LIMIT 10;

Tìm gốc:

Copy

SELECT id, hash FROM merkle_nodes WHERE parent_id IS NULL;

Bạn thậm chí có thể trích xuất các chứng cứ bao gồm với một CTE đệ quy.

In và Xác Minh Các Chứng Cứ

Script trợ giúp print_proof.py cho phép bạn lấy chứng cứ từ cơ sở dữ liệu hiện có:

Copy

uv run python print_proof.py gamma

Kết quả:

Copy

Dữ liệu: gamma
Cơ sở dữ liệu: merkle_tree.db
Lá: id=3 hash=be9d...
Gốc: afc48e...
Chứng cứ (sibling_hash, is_left_child):
   ('4f4a94...', True)
   ('0cb030...', False)
   ('673e72...', True)
Xác minh: True

Trực Quan Hóa Cây

Script tùy chọn visualize_tree.py cho thấy cây dưới dạng ASCII hoặc Graphviz DOT:

Copy

uv run python visualize_tree.py --format ascii

Kết quả ví dụ:

Copy

Gốc: id=31 hash=abc123
Cấp 0: [N id=31 h=abc123]
Cấp 1: [N id=25 h=1122aa]  [N id=30 h=99ee77]
Cấp 2: [L id=3 h=5f9a... data='gamma']  [L id=4 h=...]

So Sánh Với Git Và Bitcoin

Điều đáng lưu ý là cây Merkle đơn giản của chúng ta liên quan như thế nào đến các hệ thống thực tế:

Git sử dụng cây Merkle để theo dõi các phiên bản tệp. Mỗi commit trỏ đến một đối tượng cây (thư mục), mà trỏ đến các blob (tệp). Các băm được lưu trữ trong một cơ sở dữ liệu có địa chỉ nội dung (.git/objects). Triển khai của chúng ta đơn giản hơn nhưng theo cùng một nguyên tắc: nội dung → băm → băm cha → gốc.
Bitcoin sử dụng cây Merkle để cam kết tất cả các giao dịch trong một khối. Mỗi lá là một băm giao dịch; gốc Merkle được bao gồm trong tiêu đề khối. Ví dụ của chúng ta sử dụng các chuỗi như "alpha" thay vì các giao dịch, nhưng quy trình—ghép cặp, băm và nhân đôi các lá lẻ—là giống nhau.

Sự khác biệt nằm ở quy mô và mục đích. Git và Bitcoin tối ưu hóa cho hàng tỷ đối tượng hoặc đồng thuận an ninh cao. Ví dụ SQLite của chúng ta mang tính giáo dục: nhỏ, minh bạch và dễ truy vấn.

Bài Học Rút Ra

Dự án nhỏ này làm nổi bật một số ý tưởng mạnh mẽ:

Mật mã gặp cơ sở dữ liệu: Bằng cách lưu trữ cây Merkle trong SQLite, bạn kết hợp khả năng kiểm chứng với khả năng truy vấn.
Chứng cứ là gọn nhẹ: Việc xác minh bao gồm không cần tải xuống mọi thứ—chỉ cần log(N) băm anh chị.
SQLite rất linh hoạt: Nó không chỉ là một cơ sở dữ liệu toy; bạn có thể mô hình hóa cả các cấu trúc mật mã.
Sự rõ ràng trong giáo dục: Kiểm tra cây trong SQL làm cho khái niệm trở nên ít trừu tượng hơn.

Hướng Đi Tiếp Theo

Đây là một triển khai giáo dục tối thiểu. Các mở rộng trong thế giới thực có thể bao gồm:

Nhật ký chỉ thêm cho kiểm toán không thể giả mạo.
Nhiều cây Merkle độc lập trong một cơ sở dữ liệu.
Tinh chỉnh hiệu suất cho tập dữ liệu lớn.
Các chiến lược băm nâng cao hơn (phân tách miền, kết hợp theo cấp byte).
Tích hợp với các API yêu cầu phản hồi có thể kiểm chứng.

Kết Luận

Cây Merkle thường được giảng dạy như những cấu trúc mật mã trừu tượng đứng sau các hệ thống lớn như Bitcoin. Nhưng như hướng dẫn này cho thấy, bạn có thể triển khai chúng một cách cục bộ chỉ với Python và SQLite.

Kết quả là một cơ sở dữ liệu có thể kiểm chứng, không thể giả mạo trong một tệp .db duy nhất—không cần máy chủ, không cần phụ thuộc. Dù bạn đang tạo mẫu, giảng dạy hay chỉ đang khám phá, đây là một cách mạnh mẽ để làm cho cây Merkle trở nên cụ thể.

Hướng Dẫn Thực Tế Về Cây Merkle Trong SQLite Với Python

Giới thiệu

Tại Sao Chọn SQLite?

Cây Merkle Hoạt Động Như Thế Nào

Cấu Trúc Dự Án

Lược Đồ SQLite

Lớp `MerkleTree`

Khởi Tạo và Quản Lý Ngữ Cảnh

Xây Dựng Cây

Tạo Chứng Cứ

Xác Minh

Chạy Demo

Kiểm Tra Với SQL

In và Xác Minh Các Chứng Cứ

Trực Quan Hóa Cây

So Sánh Với Git Và Bitcoin

Bài Học Rút Ra

Hướng Đi Tiếp Theo

Kết Luận

Bình luận