logo
banner
avatar
Nhabachoc Dũng
Thứ năm 2023
Úm ba la cây thần hiện ra: Cấu trúc dữ liệu và mã hoá 🪵🌱🌿
# javascript
# html
# blockchain

Chao xìn mọi người lại là mình đây Nhabachoc KAD.

Vì mình không có nhiều thời gian để có thể làm được một Blog hoàn chỉnh nên các bạn thông cảm nha. Hãy vào link sau để đọc được chi tiết bài viết vì ở dưới bị lỗi hình ảnh:

https://kadpkt.notion.site/C-u-tr-c-d-li-u-v-m-ho-ba7adb3fecc142b88e423cc7226bb1c2

Bài viết này có dành cho bạn?

  • Bạn đọc các bài viết trên mạng nhưng không ai giải thích một cách rõ ràng về những cấu trúc và mã hoá dùng trong Ethereum

Hành trang cần chuẩn bị:

  • Đi qua chuỗi bài “Mã hoá cơ bản”

Cùng tắt đèn bật ý tưởng, gét go 🪄

RLP encoding

Trình tự hoá dữ liệu giúp biến dạng dữ liệu phức tap thành dạng byte để lưu trữ hoặc truyền đi. RLP là thuật toán mã hoá / giải mã giúp Ethereum serialize dữ liệu và đảo ngược lại chúng.

Định nghĩa:

  1. Nếu đầu vào là một byte đơn trong phạm vi [0x00, 0x7f] , thì chính nó là RLP.

  2. Nếu đầu vào không phải là giá trị (uint(0), []byte{}, chuỗi(“”), con trỏ trống …), RLP là 0x80.

  3. Nếu đầu vào là một byte đặc biệt trong phạm vi [0x80, 0xff], RLP sẽ nối 0x81 với byte [0x81, byte].

  4. Nếu đầu vào là một chuỗi có độ dài từ 2–55 byte, RLP bao gồm một byte đơn có giá trị 0x80 cộng với độ dài của chuỗi tính bằng byte và mảng giá trị hex của chuỗi. Dễ dàng thấy rằng byte đầu tiên nằm trong phạm vi [0x82, 0xb7]

    VD: **“hello world” = [**0x8b**, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x20, 0x77, 0x6f, 0x72, 0x6c, 0x64]

    • “hello world” có độ dài 11 tính ra byte 0x0b

    • Byte đầu tiên = 0x80 + 0x0b = **0x8b**

  5. Nếu đầu vào là một chuỗi dài hơn 55 byte, RLP bao gồm 3 phần từ trái sang phải:

    • Phần đầu tiên là một byte đơn có giá trị 0xb7cộng với độ dài tính bằng byte của phần thứ hai. Dễ dàng nhận ra phạm vi của byte đầu [0xb8, 0xbf]

    • Phần thứ hai là giá trị hex của độ dài của chuỗi.

    • Phần cuối cùng là chuỗi tính bằng byte.

    VD: **Một chuỗi có 1024 ký tự “a” ⇒ “aaa…” = [**0xb9**, **0x04**, **0x00**, 0x61, 0x61, …]

    • Phần đầu**0xb9 =** 0xb7 + 0x02 vì phần 2 có độ dài là 2

    • Phần hai 0x04, 0x00 = ****0x0400 ****là độ dài của “1024” - độ dài chuỗi ****

    • Phần cuối 0x61 là “a”

  6. Nếu đầu vào là một mảng trống, mã hóa RLP là một byte đơn 0xc0.

  7. Nếu đầu vào là một mảng có độ dài phần tử từ 0–55 byte, RLP bao gồm một byte đơn có giá trị 0xc0 cộng với độ dài toàn bộ phần tử sau khi chuyển sang dạng hex và nối tất cả phần tử sau khi mã hoá RLP. Phạm vi của byte đầu tiên là [0xc1, 0xf7]

    VD: **[“hello”, “world”] = [0xcc, 0x85, 0x68, 0x65, 0x6c, 0x6c, 0x6f, 0x85, 0x77, 0x6f, 0x72, 0x6c, 0x64].

    • [0x85, 0x68, 0x65, 0x6c, 0x6c, 0x6f]là mã hóa RLP của “hello”

    • [0x85, 0x77, 0x6f, 0x72, 0x6c, 0x64]là mã hóa RLP của “world”

    • 0xcc = 0xc0 + 0x0c và 0x0c = 0x06 + 0x06độ dài các phần tử sau chuyển sang dạng hex.

  8. Nếu đầu vào là một mảng có độ dài phần tử lớn hơn 55 byte, RLP bao gồm 3 phần:

    • Phần đầu là một byte đơn có giá trị 0xf7 cộng với độ dài tính bằng byte của phần thứ hai. Phạm vi của byte đầu tiên là [0xf8, 0xff]

    • Phần thứ hai là chiều dài của phần tử sau khi chuyển sang dạng hex.

    • Phần cuối cùng là nối mã hóa RLP của các mục trong danh sách.

  9. Một điều nữa, nó không được đề cập trong wiki Ethereum nhưng trong mã nguồn Golang. Với kiểu boolean true = 0x01 và false = 0x80.

Compact encoding - Hex Prefix encoding

Bạn nên đọc về Patricia trie xong và quay lại đây đọc hoặc mình sẽ link đến đây lúc cần kiến thức này.

"nibble" (tiếng Việt là "nửa byte") được sử dụng để mô tả mỗi ký tự của một địa chỉ Ethereum. Một địa chỉ Ethereum được biểu diễn bằng 40 ký tự hex, tương đương với 20 byte. Mỗi byte bao gồm 2 nibble.

⇒ 1 ký tự = 1 nibble

câu chuyện về mã HP này khá dài nên các bạn hứng thú thì có thể đọc, không muốn hiểu sâu chỉ cần biết định nghĩa sau là được. Ta nói rằng để phân biệt node leaf và node extension ta cần thêm vào trong 1 tiền tố như bảng sau:

loại node   độ dài path    |    prefix    hexchar
--------------------------------------------------
extension    chẵn           |    0000      0x0
extension    lẻ             |    0001      0x1
leaf         chẵn           |    0010      0x2
leaf         lẻ             |    0011      0x3

và thêm 1 nibble 0 vào các đường dẫn chẵn.

loại node    độ dài path    |    prefix    nibble    hexchar
------------------------------------------------------------
extension    chẵn           |    0000      0000      0x00
extension    lẻ             |    0001                0x1
leaf         chẵn           |    0010      0000      0x20
leaf         lẻ             |    0011                0x3

Ok vậy là xong định nghĩa làm theo là được nhưng nếu bạn hỏi:

  • Vì sao lại phải phân chia chẵn lẻ trong các node ?

  • Vì sao phải thêm 1 nibble 0 vào node có đường dẫn chẵn ?

Các bạn hỏi rất đúng và mình cũng trằn trọc không ngủ mấy đêm để tìm được ra câu trả lời mình thấy hợp lý:

  • Giai đoạn 1: Ban đầu bạn sẽ chỉ đơn giản là muốn phân biệt 2 loại node và khi làm việc với máy tính ta tương với bit ta có 2 bit 0 và 1 . Khi làm việc với trie với ethereum thì ta có đơn vị nibble = 1hex = 4bit ⇒ khi đó ta có bảng sau:

    loại node     |    prefix    hexchar
--------------------------------------------------
extension     |    0000      0x0
leaf          |    0001      0x1

    Xét cụ thể leaf có 2 trường hợp:

    • Đường dẫn chẵn: 36 fa thì theo bảng trên ta thêm tiền tố 1 36 fa (mình viết cách ra vì cứ 2hex = 1byte và máy tính đọc theo byte nên cách ra cho dễ nhìn)

    • Đường dẫn chẵn: 3 6f thì theo bảng trên ta thêm tiền tố 13 6f

    Byte là đơn vị dữ liệu tiêu chuẩn được sử dụng để truyền dữ liệu giữa các thiết bị và mạng máy tính vì vậy khi bạn có 1 nibble 1 và 2 nibble 01 nhưng khi được lưu trữ sẽ cùng lưu thành byte 01

    Chính xác là thế khi chúng ta lưu 2 đường dẫn bên trên vào DB ta có 01 36 fa và 13 6f. Đây là giai đoạn mã hoá oki ổn nha nhưng giải mã 😀 ủa tui chịu lun á không giải mã được. Theo quy luật ta có: mã hoá thêm 1 nibble ⇒ giải mã bỏ 1 nibble nhưng vì lưu vào DB nó lưu thành byte nên nibble đầu tiên bây giờ lại là 0 ⇒ đường dẫn là 1 36 fa 💥 toang luôn vì đường dẫn đùng là 36 fa.

    Nếu bạn bảo thêm

    if(ký tự đầu = 01) {
	bỏ luôn 2nibble 01
}
else {
	tiếp tục như bình thường
}

    vào đi để check trường hợp này vậy thì nếu mình có 1 node extension có đường dẫn 1 36 fa ⇒ mã hoá HP xong sẽ được 01 36 fa. Nếu if else xử lý được phần ở trên thì đến đây lại toang 💥 vì ở đây thực sự chỉ cần bỏ đi nibble đầu tiên 0 thì sẽ thu được đường dẫn ban đầu.

  • Giai đoạn 2: Hừm thực sự ta cần thêm 1 cái gì đó rồi. Ta cần thêm cờ để đánh dấu chẵn lẻ cho đường dẫn, trong nibble bít cuối thể hiện cho tính chẵn lẻ, bit tiếp theo thể hiện cho loại node:

    loại node   độ dài path    |    prefix    hexchar
--------------------------------------------------
extension    chẵn           |    0000      0x0
extension    lẻ             |    0001      0x1
leaf         chẵn           |    0010      0x2
leaf         lẻ             |    0011      0x3

    và các bạn thử áp dụng lại vào bài toán ở trên thì oki, ngon lành cành đào, không trùng nhau phân biệt rõ ràng NHƯNG đấy là trong trường hợp mã hoá, đừng quên bài toán đẩy vào DB sẽ làm tròn lên byte ảnh hưởng đến phần giải mã. VD: 02 36 fa sẽ được giải mã ra sao: nibble 0 đầu tiên có thể là prefix của node extension hoặc cùng có thể là do máy làm tròn lên byte của node leaf . Nhờ vào tính độ dài sau khi thu được ta vẫn có thể biết chính xác nó là node leaf chẵn nhưng không phù hợp để làm thuật toán giải mã khi quá cồng kềnh cần nhiều phép tính.

  • Giai đoạn 3: Ta cần thêm 1 chút thôi, chút gì đó … 💭. Thay vì để mặc số phận đời trôi nổi ta sẽ tự kiểm soát nó, thay vì để nó auto làm tròn byte ta sẽ thêm 1 nibble 0 vào sau nibble prefix vào trường hợp chẵn khi giải mã ta thu được mảng byte tròn trịa do ta kiểm soát và nhìn vào hex bạn có thể thấy ngay không còn sự cồng kềnh do cần bị trùng lặp nữa:

    loại node    độ dài path    |    prefix    nibble    hexchar
------------------------------------------------------------
extension    chẵn           |    0000      0000      0x00
extension    lẻ             |    0001                0x1
leaf         chẵn           |    0010      0000      0x20
leaf         lẻ             |    0011                0x3

Radix Tree - Trie

Là một cấu trúc dữ liệu còn được gọi là Patricia Tree - Radix Tree - Trie. Trie sử dụng một khóa làm đường dẫn để các nút có chung tiền tố cũng sẽ nằm chung trên một đường dẫn. Cấu trúc này nhanh nhất trong việc tìm, dễ thực hiện và yêu cầu bộ nhớ nhỏ. Do đó, nó thường được sử dụng để triển khai các bảng định tuyến, các hệ thống được sử dụng trong các máy có thông số kỹ thuật thấp như bộ định tuyến.

Không gì tốt hơn nếu có gì đấy để nhìn bằng mắt, chúng ta có ví dụ về các cặp key-value:

  • TOKEN: 1

  • TOW: 12

  • TRAN: 90

  • TRIE: 6

Ta sẽ vẽ lại theo cấu trúc Trie:

  • Đầu tiên ta thấy tất cả các cặp key đều có chung tiền tố T nên ta để T là nút cha

  • Sau đó ta thấy có 2 trường hợp O, R nên ta đặt làm 2 nút con của 2 nhánh OKEN, OW và RAN, RIE

  • Ta thấy O lại là tiền tố chung của OKEN trong TOKEN và OW trong TOW nên ta để O là nút cha

  • Tiếp tục thế cho đến hết

Hay theo dạng Radix Tree:

Chúng ta có một cấu trúc nhìn gọn gàng hơn, giảm được các node trung gian không chứa giá trị gì.

Nhưng trong lập trình sẽ phải lập trình theo mảng: [vt0, vt1, vt3, …, {giá trị}]. vt0 là vị trí 0 mà vì sao lại là vị trí thì các bạn theo dõi sau đây:

Các bạn chuyển key từ tring sang hex (giảm chiều dài mảng chứa key):

  • TOKEN ⇒ 746F6B656E

  • TOW ⇒ 746F77

  • TRAN ⇒ 7472616E

  • TRIE ⇒ 74726965

Các bước thực hiện:

  • Ta áp dụng Trie đầu tiên thấy 7 chung ta đặt làm node cha nhưng hay suy nghĩ lại tý. Trong lập trình nếu ta đơn giản là ghi 7 → 4 ai biết được trỏ là gì vậy nên 7 hay 4 hay các ký tự từ 0→9 và a→f phải là vị trí, vị trí đấy chứa con trỏ hay chứa địa chỉ của ô nhớ kế tiếp. 😐 hơi rắc rối nhỉ, cố ngẫm nhá hoặc do mình nói ngu 😅. Chốt lại node cha đầu tiên ở vị trí thứ 7 sẽ chứa con trỏ đến node tiếp theo.

  • Tiếp tục 4 chung ở mọi chuỗi nên trong node này chọn vị trí thứ 4 chứa con trỏ node tiếp theo

  • Cứ tiếp tục như vậy ta được như hình vẽ

Lưu ý:

  • Dãy mình ghi số 0-9, a-f để cho các bạn dễ nhìn đc vị trí nhưng thực tế thì:

    [null, null, null, null, null, null, null, <Con trỏ đến node tiếp>, null, null, null, null, null, null, null, null, {giá trị}] nếu không có giá trị thì = null

Ưu điểm:

Sau đây là những lợi thế chính của trie so với cây nhị phân tìm kiếm:

  • Thời gian tìm kiếm nhỏ hơn. Thao tác tìm kiếm một khóa độ dài m đòi hỏi O(m) phép so sánh ký tự. Một cây nhị phân tìm kiếm sử dụng O(log_n) phép so sánh xâu (n là số lượng khóa). Trong trường hợp xấu nhất, cây nhị phân tìm kiếm cần dùng O(m*log_n) phép so sánh ký tự.

  • Trie sử dụng ít bộ nhớ hơn bởi các tiền tố chung chỉ cần được lưu trữ một lần

  • Số lượng nút từ gốc tới lá đúng bằng độ dài của khóa.

Tóm lại là tím kiếm nhanh hơn và sử dụng ít bộ nhớ hơn với xâu ký tự

Merkle Tree

Cây Merkle là một cây băm. Các nút lá lưu trữ dữ liệu. Các nút cha chứa giá trị băm của con chúng và quá trình này được lặp lại đến khi chỉ còn lại một giá trị băm duy nhất, ta gọi đó là RootHash. RootHash tóm tắt tất cả dữ liệu trong các giao dịch liên quan, nó duy trì tính toàn vẹn của dữ liệu. Nếu một chi tiết duy nhất trong bất kỳ giao dịch hoặc thứ tự giao dịch nào thay đổi, thì MerkleRoot hay RootHash cũng sẽ thay đổi. Sử dụng cây Merkle cho phép kiểm tra nhanh chóng và đơn giản xem liệu một giao dịch cụ thể có được bao gồm trong tập hợp hay không:

Transaction A <TxA> có Hash A

…

Transaction D <TxD> có Hash D

⇒ Bắt đầu gộp các 2 node lại thành 1 node mới ta được:

Hash AB = hash(Hash A + Hash B)

Hash CD = hash(Hash C + Hash D)

Và khi còn lại 2 node cuối cùng ta được:

HashRoot = hash(Hash AB + hash CD)

Ưu điểm:

  • Cây Merkle cung cấp một phương tiện để chứng minh tính toàn vẹn và hợp lệ của dữ liệu

  • Cây Merkle đòi hỏi ít bộ nhớ hoặc dung lượng ổ đĩa vì các bằng chứng được tính toán dễ dàng và nhanh chóng

  • Bằng chứng và quản lý của nó chỉ yêu cầu một lượng nhỏ thông tin được truyền qua mạng

Merkle Patricia Trie

Patricia trie là trie chính được sử dụng trong Ethereum để lưu trữ dữ liệu. Nó là sự kết hợp của Radix trie và Merkle tree.

// đây sẽ dữ liệu muốn lưu theo dạng key-value
{
	{ '546F' : '1'  },
	{ '556'  : '12' },
	{ '9AA'  : '90' },
	{ '8FA2' : '6'  }
}

Đây là cấu trúc của node - đây sẽ là thứ được lưu vào DB cũng theo dạng key-value:

Một node trong Ethereum được lưu trữ dưới dạng key-value với key là hàm băm của nút. Value là một mảng có 17 phần tử: 16 phần tử đầu tiên là số hex từ 0đến fvà phần tử cuối cùng là dữ liệu chứa trong node đó.

Key của node để “tra cứu trong cơ sở dữ liệu” và Path <key của dữ liệu muốn lưu. Vd: address> được sử dụng để “tra cứu trong trie”.

Patricia Trie cơ bản

Đây là sẽ là thứ được lưu trên DB và nếu bạn muốn tìm kiếm dữ liệu 546F thì mình sẽ nói từng bước:

  • Nhìn vào dữ liệu cần tìm 546F ta tính được Path là 5, 4, 6, F

  • Tìm kiếm trong node đầu tiên <root Hash> vị trí đầu tiên trong Path là 5 mang giá trị HashA

  • Tìm đến Node có key = HashA rồi tìm tiếp vị trí tiếp theo trong Path là 4 mang giá trị HashB

  • Tìm đến Node có key = HashB rồi tìm tiếp vị trí tiếp theo trong Path là 6 mang giá trị HashC

  • Tìm đến Node có key = HashC rồi tìm tiếp vị trí tiếp theo trong Path là F mang giá trị HashD

  • Tìm đến Node có key = HashD và ta cũng đã tìm hết các vị trí trong Path, nhìn vào data ta thấy kết quả = 1. Vậy đây chính là giá trị tương ứng cần tìm

Vậy các bạn đã hiểu câu trên

Key của node để “tra cứu trong cơ sở dữ liệu” và Path được sử dụng để “tra cứu trong trie”.

Bạn có thể thấy rằng, mình đã sử dụng Path để tìm giá trị (một thuộc tính của Radix trie) và nếu một giá trị trong trie bị thay đổi, nó sẽ khiến rootHash thay đổi (một thuộc tính của Merkle tree). Hơn nữa, trie có rất nhiều node có giá trị null trong phần tử dữ liệu và mình phải cải thiện nó để hiệu quả hơn.

Cấu trúc đầu tiên mình sẽ để các đường dẫn cho dễ hình dung nhưng ở dưới các bạn tự hiểu ra các đường dẫn nhé vì nhìn khá là rối.

Patricia Trie cải tiến

Cây trên có 2 vấn đề chúng ta cần xem xét:

  • 8FA2 để tìm được giá trị 6 không bị phân tách mà thẳng một đường

  • Hay ở 1 trường hợp khác {caption, capte} ta thấy có đoạn cap chung và đoạn cap cũng không bị phân tách ở giữa

⇒ lãng phí bộ nhớ cho các node và các giá trị null

👉 Để giải quyết vấn đề đầu tiên Ethereum đã giới thiệu leaf - nút lá và vấn đề thứ hai dùng extension - node mở rộng. leaf và extension đều là các node dạng mảng có 2 phần tử:

  • Phần tử đầu là partialPath giúp giảm giá trị rỗng

  • Phần tử thứ 2:

    • Nếu là leaf : chứa giá trị data

    • Nếu là extension : chứa giá trị merkleHash

Sau khi áp dụng đã gọn hơn rất nhiều rồi phải không. À thì thực ra ví dụ này của mình hơi tệ nhỉ vì nó không có đủ trường hợp, để mình lấy 1 ví dụ khác:

// đây sẽ dữ liệu muốn lưu theo dạng key-value
{
	{ 'cab8' : '1'  },
	{ 'cab'  : '12' },
	{ '39'   : '90' },
	{ '395'  : '6'  },
	{ '56f0' : '15' }
}

Ta được cấu trúc chưa tối ưu:

Sau khi tối ưu:

Đây cũng chưa phải bước hoàn thiện. Mình và các bạn sẽ đi đến bước cuối cùng để hoàn thiện và nhận về Patricia trie mà Ethereum sử dụng:

Một số quy tắc bổ sung:

  1. Các node leaf hoặc extension thì partialPath được mã hóa HP

  2. Mọi phần tử trong một node sẽ được mã hóa RLP

  3. Value sẽ được mã hóa RLP.

Giờ thì quay lại phần Hex Prefix encoding để hiểu được hết ý nghĩa. Thành quả là:

Đọc tiếp
Cách tạo ra một database lưu trữ dữ liệu từ đầu
Khổng Anh Dũng - Thứ5 15
Cách tạo ra một database lưu trữ dữ liệu từ đầu
Khổng Anh Dũng - Thứ5 15
Cách tạo ra một database lưu trữ dữ liệu từ đầu
Khổng Anh Dũng - Thứ5 15