Đường đến Neo3: Triển khai Merkle Patricia trie

TIN TỨC NEO
2020-03-13



Trong bài viết Đường đến Neo3 trước, chúng ta đã đề cập đến Patricia tries, cây Merkle và cách sử dụng bằng chứng Merkle để cung cấp xác minh giao dịch nhẹ. Đối với tập cuối cùng trong loạt bài về trạng thái gốc (state root) này, chúng ta hãy kết hợp hai phần đầu để hiểu Merkle Patricia tries (MPT).


Xem các bài trong chuỗi bài Đường đến Neo3 tại đây.


Node lưu trữ

Mỗi node trên blockchain Neo xử lý dữ liệu từ các khối, đọc và thực hiện từng giao dịch theo thứ tự. Một số giao dịch ở chế độ chỉ đọc, chẳng hạn như truy vấn về tổng nguồn cung của một tài sản cụ thể, nhưng một số giao dịch khác sẽ yêu cầu thay đổi đối với bộ lưu trữ của node. Ví dụ: việc chuyển token từ địa chỉ này sang địa chỉ khác sẽ sửa đổi các giá trị số dư được lưu trữ cho cả hai địa chỉ.


Các node lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị. Khóa có thể được coi là tên hoặc mã định danh duy nhất tương ứng với một phần dữ liệu cụ thể, chẳng hạn như tên của hợp đồng thông minh hoặc thông tin số dư token cho một địa chỉ cụ thể.


Để xác định vị trí giá trị cụ thể được thay đổi, khóa được sử dụng. Vì mỗi node xử lý mọi giao dịch theo cùng một thứ tự chính xác, hy vọng mỗi node sẽ xác định các khóa và giá trị giống nhau và do đó chia sẻ cùng một trạng thái.


Để xác minh rằng các node thực sự có chung trạng thái, chúng ta có thể sử dụng Merkle Patricia trie. Như chúng ta đã phác thảo trong tập trước, thành phần Patricia trie là một cấu trúc dữ liệu tổ chức các khóa theo bất kỳ tiền tố được chia sẻ nào và thành phần cây Merkle cung cấp dấu vân tay của toàn bộ cấu trúc có thể được sử dụng để xác thực trạng thái của nó.


Merkle Patricia trie

Trong hình ảnh bên dưới, chúng ta có một bộ ba Merkle Patricia đơn giản lưu trữ ba cặp khóa-giá trị. Bạn có thể nghĩ về cây này như một ảnh chụp nhanh của bộ lưu trữ của node. Trong trường hợp của chúng tôi, bộ ba cho thấy ba phần dữ liệu cân bằng được lưu trữ như thế nào.


Ở đầu trie, chúng ta có node đầu tiên chứa khóa b3, tiền tố được chia sẻ của ba khóa b31d4, b38a2b3d6f. Nếu chúng ta có nhiều khóa bắt đầu bằng b3, tất cả chúng sẽ được tìm thấy trên một node con phân nhánh từ cùng một điểm.


Ví dụ đơn giản về Merkle Patricia trie
Ví dụ đơn giản về Merkle Patricia trie

Để khám phá các giá trị của mỗi khóa, chúng ta theo dõi bộ ba giống như cách chúng ta đã làm với Patricia trie. Trong node tiếp theo, n2, chúng ta có 16 nhánh để chọn, mỗi nhánh tương ứng với một trong 16 chữ số thập lục phân có thể có (0-9, a-f). Ví dụ: nếu chúng ta muốn tìm giá trị tương ứng với khóa b38a2, chúng ta sẽ theo nhánh từ 8, dẫn chúng ta đến node n4. Trong trie đơn giản của Neo, node này giữ phần cuối cùng của khóa, a2 và trỏ chúng ta đến giá trị được lưu trữ, 13.12 GAS.


Ngược lại, chúng ta cũng có thể theo trie lên trên để khám phá gốc Merkle, bắt đầu với các giá trị được lưu trữ giống như chúng ta đã làm với cây Merkle trong bài trước. Để tìm hàm băm của n3, n4n5, trước tiên chúng ta cần băm của từng giá trị. Chúng ta có thể băm từng node đó cùng với các giá trị băm của chúng để xác định hàm băm của n2. Với hàm băm của n2, chúng ta có thể xác định hàm băm của n1, tương ứng với gốc Merkle của chúng ta.


Nếu tất cả các node trên mạng có cùng thông tin chính xác trong bộ lưu trữ, tất cả chúng sẽ chia sẻ cùng một gốc Merkle. Ngược lại, nếu một node có dữ liệu khác nhau được lưu trữ, chẳng hạn như giá trị không chính xác cho một khóa cụ thể, quá trình băm sẽ dẫn đến một gốc Merkle hoàn toàn khác được tạo ra. Điều này giúp dễ dàng kiểm tra xem một node có nằm ngoài vị trí với chế độ xem được giữ bởi các node đồng thuận hay không.


Triển khai MPT

Việc triển khai MPT cho Neo đang diễn ra, với những nỗ lực phát triển hiện đang được dẫn dắt bởi Zhang Tao, một kỹ sư phần mềm cho Neo Global Development. Như với ví dụ ở trên, ba loại node chính được sử dụng trong cấu trúc:


  1. Node đầy đủ (node nhánh) - có một nhánh cho mỗi chữ số hex cộng với một giá trị (n2)

  2. Node ngắn - chỉ có một khóa cùng với một con trỏ. Hai loại tồn tại:

  • node mở rộng - một khóa và một con trỏ tới node tiếp theo (n1)

  • node lá - một khóa trỏ đến node giá trị (n3, n4, n5)

  1. node giá trị - lưu trữ giá trị cuối cùng cho khóa


Ngoài ra, cũng có các node băm, tương ứng với hàm băm của một node cụ thể trong trie. Chúng được sử dụng để đạt hiệu quả vì nhiều giá trị được lưu trữ không được yêu cầu ngay lập tức, không cần lưu trữ toàn bộ dữ liệu cho một node cụ thể.


Nếu thông tin này được yêu cầu sau này, chúng ta có thể xác định giá trị chính xác bằng cách sử dụng chứng minh gốc và trạng thái Merkle, như Tao giải thích:


“Ví dụ: Khi lưu trữ một node, n1, [chúng tôi] sử dụng HashNode để đại diện n2 trong phần tiếp theo. Vì vậy, trong cơ sở dữ liệu, khóa là của n1 và giá trị là phần khóa của n1 và phần băm của n2. Vì vậy, chúng ta có thể sử dụng cơ sở dữ liệu và chỉ băm gốc trạng thái để xây dựng toàn bộ phần cây theo từng phần [mà] chúng ta cần.”


Sau khi triển khai MPT và các thành phần cần thiết khác, cả node đầy đủ và node nhẹ trên mạng Neo sẽ có thể cung cấp tính nhất quán lưu trữ mạnh mẽ. Ngoài ra, nó mở đường cho các trường hợp sử dụng mới, chẳng hạn như tạo điều kiện tính toán cục bộ trên các node nhẹ thông qua điểm kiểm tra, và đảm bảo rằng lưu trữ node có thể kiểm tra được và đáng tin cậy, một yêu cầu cho cả người dùng cuối bình thường và ứng dụng doanh nghiệp.


TINTUCNEO – Tham gia các cộng đồng Tin tức NEO tại:

Website tin tức

Medium tin tức

Telegram tin tức

Telegram Thảo luận

Fanpage tin tức

Kênh Youtube



0 bình luận. Để lại câu hỏi & nhận trả lời nhanh qua email.




Bài cùng chủ đề
Giới thiệu về đội ngũ phía sau O3 Labs mới
Vào tháng 5 năm 2020, O3 Labs tuyên bố họ thuộc quyền quản lý mới và sẽ tiến tới bảo trì các sản phẩm do công ty phát triển trước đó. Nhóm O3 Labs mới sẽ được cấu trúc như một cộng đồng nguồn mở với các thành viên cốt lõi và đóng góp từ các nhà phát triển bên ngoài.

2020-05-30

John deVadoss nói về trải nghiệm của nhà phát triển Neo, “tôi rất vui khi được canh tranh với bất cứ ai”
Nhà lãnh đạo của Neo Global Development (NGD) Seattle, John deVadoss, gần đây đã chia sẻ suy nghĩ của mình về tiến trình Neo hướng tới việc trở thành nền tảng blockchain thân thiện với nhà phát triển nhất. Các bình luận được đưa ra bởi cựu chiến binh Microsoft trong lần xuất hiện trên tập 31 của podcast Neo News Today (NNT).

2020-05-30

Senno thông báo ngừng hoạt động vì COVID-19
Senno - một dự án có trụ sở tại Hồng Kông, hướng đến mục đích xây dựng một hệ sinh thái phân tích cảm xúc phân tán, đã tuyên bố thông qua kênh Telegram của mình rằng họ sẽ ngừng hoạt động. Senno đã tìm cách tạo ra một hệ sinh thái trí tuệ đám đông trong thời gian thực thông qua việc sử dụng các thuật toán AI được thiết kế để đọc và giải thích nội dung do người dùng tạo trên internet.

2020-05-29

FLETA nhấn mạnh việc tích hợp NeoVM và nền tảng đăng ký dữ liệu lâm sàng trong thông báo hợp tác với Neo
FLETA đã thông báo rằng họ đã ký kết hợp tác chiến lược với Neo, cam kết sử dụng NeoVM trên MainNet để thực hiện các hợp đồng thông minh. Điều này đã được thực hiện bằng cách tách NeoVM khỏi giao thức lõi Neo vào năm 2019, nhằm mở rộng các kịch bản ứng dụng có thể có của nó.

2020-05-29

Tham gia Cộng đồng NEO Việt Nam - TINTUCNEO
NEO-based projects? Contact us at [email protected] for collaborations in the Vietnam market