Thay đổi định dạng của cây trạng thái Ethereum bằng lớp phủ

Lưu ý của biên tập viên: Bài viết này đến từNhững người đam mê Ethereum (ID: ethfans)Lưu ý của biên tập viên: Bài viết này đến từ

Những người đam mê Ethereum (ID: ethfans)

Cách tài khoản và hợp đồng lưu trữ dữ liệu là một trong nhiều vấn đề ảnh hưởng đến Ethereum. Giao thức Ethereum sử dụng Cây Merkle Patricia (MPT, Cây Merkle Patricia) để tổ chức dữ liệu tài khoản và hợp đồng. Mặc dù cấu trúc dữ liệu này hoạt động tốt trên lý thuyết, nhưng trên thực tế, nó tạo ra nhiều vấn đề hơn là giải quyết được. Các nhà phát triển cốt lõi đã thảo luận trong nhiều năm rằng họ muốn thay thế cấu trúc dữ liệu này bằng cây nhị phân.Trong bài viết này, tôi sẽ giải thích quan điểm của mình về vấn đề này và cách đạt được chuyển đổi này.

lý lịch

Phương pháp đề xuất của tôi bao gồm một giai đoạn chuyển tiếp trong đó mạng duy trì cả hai cấu trúc cây. Ưu điểm của việc này là quá trình chuyển đổi cấu trúc cây sẽ không ảnh hưởng đến hoạt động của chuỗi và nó có thể đảm bảo rằng tất cả các tài khoản được chuyển đổi sang định dạng nhị phân.

lý lịch

Hiện tại, cây trạng thái của Ethereum là hệ thập lục phân. Hex có nghĩa là mỗi nút có 16 nút con. Về lý thuyết, điều này là tốt, bởi vì có nhiều con hơn có nghĩa là cần ít "cấp độ" hơn (tức là chiều cao của cây) để lưu trữ tất cả dữ liệu.

Mô tả hình ảnh

- Hình 1. Ví dụ về cây hex cho biết cách lưu trữ giá trị v tại khóa tương ứng 0xaa. Độ dài khóa của cây này chỉ là 2 byte và chỉ có cây con dọc theo 0xaa được biểu diễn. Để cho ngắn gọn, các cây con không liên quan được thay thế bằng "..." −

Có thể thấy cây ở hình trên rất ngắn và tán rộng. Với cùng một cặp khóa-giá trị, hình dưới đây cho thấy tình hình lưu trữ cây nhị phân. 170 được biểu diễn dưới dạng 10101010 trong cây nhị phân.

Mô tả hình ảnh

Như có thể thấy từ hình, cây nhị phân sâu hơn và hẹp hơn nhiều.

Trong Ethereum, mỗi khối chứa một trường stateRoot, là giá trị băm gốc của MPT đại diện cho trạng thái toàn cầu của Ethereum sau khi khối được xử lý. Nói chung, giá trị băm này có được bằng cách băm danh sách các giá trị băm của 16 nút con của nút gốc. Giá trị băm của các nút con này có được bằng cách băm danh sách 16 giá trị băm của nút con của nút con, v.v.

Mỗi khi một giao dịch được đóng gói tạo ra một khối mới, công cụ khai thác sẽ cập nhật cây tài khoản và tính toán lại hàm băm gốc. Băm gốc được lưu trữ trong trường stateRoot của khối mới và sau đó khối mới được đồng thuận.

Mô tả hình ảnh

Đây là vấn đề: tính toán lại hàm băm gốc sẽ mất quá nhiều thời gian nếu tất cả các nút đều được băm, vì vậy để tính toán hàm băm của nút gốc, công cụ khai thác sẽ truy xuất các hàm băm anh chị em từ cơ sở dữ liệu (băm anh chị em). Mặc dù cách thứ hai (thợ đào lấy các giá trị băm anh chị em từ cơ sở dữ liệu) không mất nhiều thời gian như cách trước (thợ mỏ lấy tất cả các nút lá từ cơ sở dữ liệu và băm chúng), thao tác này vẫn tốn nhiều thời gian. Bởi vì mỗi hàm băm phải được lấy từ cơ sở dữ liệu.

Trong một cây hex, bạn thường cần lấy ra 15 giá trị băm anh chị em ở mỗi cấp độ. Trong ví dụ tôi đã xây dựng ở trên (Hình 1), (tính toán lại hàm băm gốc) sẽ yêu cầu 30 hàm băm.

Mặc dù cây nhị phân sâu hơn một chút, nhưng chỉ cần một hàm băm anh chị em ở mỗi cấp độ. Trong ví dụ trên (Hình 2), chỉ cần 8 giá trị băm! Đó là lý do tại sao cây nhị phân tốt hơn trong thực tế.

tiêu đề cấp đầu tiên

Thật không may, việc chuyển đổi sang cây nhị phân không đơn giản. Có quá nhiều dữ liệu cần chuyển đổi nên sẽ mất hơn 15 giây thời gian tạo khối để thực hiện chuyển đổi.

Bên cạnh đó, hãy tưởng tượng bạn đang dịch một cuốn sách dày 5000 trang và các tác giả liên tục nói với bạn rằng họ đã thực hiện một số thay đổi đối với câu chuyện và những thay đổi này ảnh hưởng đến các trang bạn đã dịch... thì quá trình này sẽ kéo dài vô tận. Chuyển đổi định dạng của cây trạng thái cũng là một vấn đề: có thể bạn vừa hoàn thành chuyển đổi định dạng của một địa chỉ và người dùng sử dụng địa chỉ đó (do đó cập nhật trạng thái của địa chỉ), sau đó bạn phải chuyển đổi lại từ đầu (vì trạng thái của một địa chỉ Cập nhật cũng ảnh hưởng đến toàn bộ cây trạng thái).

tiêu đề phụ

Bước 1 - Chuyển đổi

Theo phương pháp này, khi chiều cao khối là H1, phải có hai gốc trạng thái: một là gốc trạng thái hệ thập lục phân "lớp cơ bản" và gốc trạng thái cây nhị phân "lớp phủ" là gốc trạng thái.

Mô tả hình ảnh

Cây hex được tạo ở chế độ chỉ đọc, vì vậy mọi cập nhật về trạng thái sẽ được thực hiện trên cây lớp phủ.

Khi một giao dịch đọc hoặc cập nhật một tài khoản, đầu tiên hệ thống sẽ tìm kiếm cây lớp phủ. Nếu tài khoản không được tìm thấy trong cây lớp phủ, thì cây hex cũ sẽ được tìm kiếm giá trị.

tiêu đề phụ

Bước 2 - Chuyển đổi cây cơ sở

Mô tả hình ảnh

- Hình 5. Trong giai đoạn chuyển đổi thứ hai, những người khai thác thay thế gốc thập lục phân bằng gốc của cây nhị phân đã chuyển đổi trong tiêu đề khối, báo hiệu cho mạng rằng họ đã sẵn sàng -

Khi đủ chuỗi khối cung cấp cùng một giá trị cho gốc của cây cơ sở nhị phân được chuyển đổi, điều đó có nghĩa là hầu hết các công cụ khai thác đã hoàn thành việc chuyển đổi và phê duyệt cây được chuyển đổi. Quá trình hợp nhất sau đó bắt đầu. (Ghi chú của người dịch: Việc hợp nhất tại thời điểm này là dành cho cây cơ sở nhị phân chỉ đọc và cây bìa nhị phân đọc-ghi)

Quá trình hợp nhất diễn ra liên tục: mỗi khi một khối mới được tạo, n khóa sẽ bị xóa khỏi cây lớp phủ và được chèn lại vào cây cơ sở nhị phân. Quá trình này tiếp tục cho đến khi tất cả các khóa đã bị xóa khỏi cây lớp phủ. Khi đạt đến bước này, tiêu đề khối không còn giữ gốc của cây trạng thái lớp phủ.

Bước tiếp theo

tiêu đề phụ

Bước tiếp theo