Tính hữu hạn thực sự của khối DAG

lời tựa

lời tựa

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

Tầm quan trọng của tính cuối cùng

Tính hữu hạn của hầu hết các cấu trúc liên kết chuỗi khối ngày nay dựa trên xác suất, điều đó có nghĩa là bạn không bao giờ có thể chắc chắn 100% rằng một giao dịch đã thực sự hoàn tất. Ví dụ: trong mạng Bitcoin, theo thời gian (hoặc theo ngôn ngữ của thế giới Bitcoin, khi số lượng khối tăng lên), xác suất kẻ tấn công bắt kịp phần còn lại của mạng và sắp xếp lại các khối thay đổi theo cấp số nhân. Việc giảm rủi ro theo cấp số nhân này đã dẫn đến chủ nghĩa kinh nghiệm "6 khối". Nói cách khác, nếu 5 khối nữa được thêm vào khối chứa giao dịch của bạn, thì giao dịch của bạn có "sâu 6 khối", và theo thống kê, giao dịch đó không rất có thể bị tấn công sắp xếp lại.

Trong nhiều trường hợp, quyết toán xác suất là tốt. Tuy nhiên, nếu bạn đang thực hiện một số lượng lớn giao dịch, mỗi giao dịch phụ thuộc vào đầu ra của giao dịch trước đó hoặc nếu bạn đang thực hiện một giao dịch lớn và bạn cần chắc chắn rằng giao dịch này sẽ không bao giờ bị đảo ngược, thì cuối cùng là khá quan trọng lên.

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

Ý nghĩa cuối cùng của DAG là gì?

Nhớ lại rằng rủi ro sắp xếp lại cơ chế đặt hàng sớm của chúng tôi chủ yếu xảy ra khi chuỗi neo thay đổi.

Do đó, miễn là chúng ta có thể đảm bảo rằng chuỗi neo được cố định thường xuyên, thứ tự các khối trên chuỗi neo có thể được xác định hoàn toàn bất kể điều gì xảy ra.

Chúng ta làm điều đó như thế nào? Mạng sẽ tổ chức các phiếu bầu thông thường, được đồng bộ hóa với việc xây dựng khối DAG, để áp dụng trọng số vô hạn cho các khối cụ thể gần ranh giới DAG.

Khi một khối được cho trọng lượng vô hạn, điều đó có nghĩa là tất cả các khối được nó trực tiếp hoặc gián tiếp trỏ tới thông qua con trỏ ma (ghost pointer) đều có trọng số vô hạn, nghĩa là giờ đây không thể lật đổ trật tự này bằng cách tấn công.

Trong hình trên, chúng ta đã chọn khối màu cam để có trọng lượng vô hạn và chúng ta có thể thấy rằng khối vô cực này đã tạo ra trọng lượng vô hạn cho tất cả các khối trên chuỗi neo bằng cách chỉ trở lại khối DAG (được đánh dấu bằng màu xám đậm trong hình) . Hiện tại, chúng tôi đã xác định một cách hiệu quả thứ tự của chuỗi neo này và tất cả các khối tại kỷ nguyên của chính nó.

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

Lựa chọn khối định kỳ bằng thuật toán giống như PBFT

Để chọn một khối trong DAG để hoàn thiện, chúng tôi sử dụng một quy trình tương tự như thuật toán PBFT (Dung sai lỗi Byzantine thực tế). Xét rằng PBFT là một thuật toán được phát triển tốt và được triển khai rộng rãi, các chi tiết và lỗi tiềm ẩn (lỗi) liên quan đến bài viết này sẽ không được lặp lại ở đây.

Quá trình hoàn thiện khối thời gian của PBFT được chia thành bốn bước, như thể hiện trong sơ đồ đơn giản hóa cao bên dưới.

tiêu đề phụ

1. Đề xuất một khối mới

• Tính toán tính đủ điều kiện của nó thông qua VRF (SK, previous_PBFT_block_hash, current_vote_type, current_round_number, current_step_number) = (e, π), trong đó e là giá trị đủ điều kiện và π là bằng chứng tính toán đúng VRF

• Quyết định "nếu e < ngưỡng thì đủ điều kiện đề xuất khối PBFT trong vòng này"

• Chọn một ứng cử viên khối DAG gần ranh giới nhưng không nằm trên ranh giới để xác nhận lần cuối, nghĩa là ứng cử viên khối Pt của giai đoạn hiện tại (Giai đoạn)

• Tạo một chu trình giữa Pt và P(t-1) (chi tiết bên dưới), tìm tất cả các khối có trong chu trình này

• Tạo một bộ lập lịch đồng thời CS

• Tạo ứng cử viên khối PBFT (Pc) chứa (Pt, CS) và các thông tin khác như dấu thời gian, chữ ký, người thụ hưởng

• Tính hàm băm của Pc (hash)

• tiêu đề phụ

2. Bầu nhóm trưởng

• Tính toán lại trình độ của nó thông qua VRF (đưa vào số_vòng_tròn hiện tại cộng với một và loại biểu quyết hiện tại) để tạo một (e, π) khác

• Quyết định "nếu e < ngưỡng thì được vào vòng này"

• Đợi 2 λ, trong đó λ là đường kính mạng - nghĩa là khoảng cách ngắn nhất (theo thời gian) giữa hai nút xa nhất trong mạng

• Tính giá trị nhỏ nhất của e được quan sát khi π cũng đúng và người tạo là giá trị nhỏ nhất. Khi e là "lãnh đạo", nó là người tạo - nút này là nút đề xuất ứng cử viên khối PBFT tiếp theo

• tiêu đề phụ

3. Bỏ phiếu cho các khối

• Tính toán lại trình độ của nó thông qua VRF (đưa vào số_vòng_tròn hiện tại cộng với một và loại biểu quyết hiện tại) để tạo một (e, π) khác

• Quyết định "nếu e < ngưỡng thì được vào vòng này"

• Đợi 2 lambda

• Tính xem nó có nhận được 2T+1 phiếu bầu trong khoảng thời gian e_min nhất định hay không (ở đây T là 1/3 số nút bỏ phiếu đủ điều kiện trong vòng trước)

• Nếu nó chưa có khối PBFT, nó sẽ thực hiện bỏ phiếu ngang hàng cho Pc tương ứng với e_min và hàm băm liên quan (Pc)

• Xác minh rằng Pc đã được tạo chính xác

• tiêu đề phụ

4. Bỏ phiếu để chuyển sang bước tiếp theo

• Tính toán lại trình độ của nó thông qua VRF (đưa vào số_vòng_tròn hiện tại cộng với một và loại biểu quyết hiện tại) để tạo một (e, π) khác

• Quyết định "nếu e < ngưỡng thì được vào vòng này"

• Đợi 2 lambda

• Tính toán xem có bất kỳ Pc cụ thể nào đã nhận được 2T+1 phiếu bầu không

• Xác minh rằng Pc chiến thắng đã được tạo chính xác

• Tính toán Pc được xác minh mới nhất và đưa kết quả vào bộ nhớ vĩnh viễn

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

Giới thiệu thêm về PBFT của chúng tôi

Những gì được viết ở trên là một mô tả cực kỳ đơn giản

chữ

Quy trình PBFT này có tính bảo mật cao và có thể mở rộng

Lưu ý rằng mỗi khi một nút muốn phát biểu, nó sẽ tính toán giá trị đủ điều kiện VRF để đảm bảo rằng nút đó đủ điều kiện phát biểu trong vòng đó. Ngưỡng đủ điều kiện được thiết lập và điều chỉnh động để đảm bảo hai điều:

Các nút tham gia trong mỗi vòng là ngẫu nhiên và có khả năng khác nhau, nghĩa là một khi kẻ tấn công quan sát thấy một nút là người tham gia và nhắm mục tiêu vào nút đó, nút đó có thể bị loại trong vòng tiếp theo. Điều này khác với nhiều thuật toán khác giữ chân người tham gia (hoặc thành viên ủy ban) trong một khoảng thời gian dài, khiến họ trở thành mục tiêu chính cho các cuộc tấn công.

Trong bất kỳ vòng nhất định nào, chỉ một phần nhỏ các nút đủ điều kiện tham gia, làm cho quy trình PBFT này có khả năng mở rộng cao. Điều này có nghĩa là ngay cả khi dung lượng mạng mở rộng và số lượng người tham gia đủ điều kiện tăng lên, thì những người tham gia thực tế (quy mô ủy ban) của các vòng PBFT này so với dung lượng mạng có thể dễ dàng được thiết lập để đạt được mức mở rộng tuyến tính phụ. Số lượng người tham gia càng ít thì quá trình bỏ phiếu càng nhanh.

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

Chuỗi PBFT song song

Quy trình PBFT của Taraxa tạo ra một chuỗi khối PBFT tuyến tính cùng với DAG của các khối hiện có.

Mỗi khối PBFT có hai mục tiêu chính,

• Hoàn thành việc hoàn thiện khối DAG trong khối tuần hoàn

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

Hoàn thành hoàn thiện các khối DAG

Quá trình PBFT này sẽ xác nhận một khối duy nhất trong khối DAG. Do đó, không giống như hầu hết các mạng khác sử dụng quy trình PBFT, nó không đóng vai trò là thuật toán đồng thuận chính để kiểm tra toàn bộ quy trình chuỗi khối. Đây là lý do tại sao quy trình PBFT của Taraxa song song và phần lớn không đồng bộ với quy trình tạo DAG khối.

Bất cứ khi nào một khối DAG mới được hoàn thiện, chúng tôi sẽ tạo một chuỗi neo đã hoàn thiện và một tập hợp các khối có liên quan trên chuỗi neo (được triển khai dọc theo kỷ nguyên của mỗi khối neo). Tập hợp toàn bộ các khối được gọi là một khoảng thời gian, cũng có thể được coi là ảnh chụp nhanh của một cụm khối được sắp xếp cuối cùng.

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

lập lịch trình đồng thời

Lập lịch trình đồng thời xác định thứ tự theo các cách sau:

• Thứ tự của các khối, điều này được xác định bởi cơ chế sắp xếp, bởi vì có nhiều khối trong một chu kỳ.

• Lọc ra các giao dịch dư thừa giữa các khối. Bởi vì chúng tôi sử dụng cấu trúc dữ liệu DAG, nên rất có khả năng nhiều người đề xuất khối sẽ đóng gói cùng một nhóm giao dịch thành các khối DAG khác nhau, dẫn đến một mức độ chồng chéo giao dịch nhất định. Taraxa đã thiết kế một cơ chế phân xử giao dịch (sẽ được giới thiệu chi tiết trong một bài viết sau) để giúp điều chỉnh sự chồng chéo này - chúng tôi hy vọng sẽ giảm thiểu tình trạng này nhưng không phải bằng không, nếu không sẽ có sự cô lập quá mức giữa các giao dịch.

• Chia các giao dịch thành các tập hợp đồng thời và các tập hợp tuần tự.

• Đây là một phần quan trọng trong thiết kế EVM đồng thời của chúng tôi (sẽ được giới thiệu trong bài viết sau), trong đó một tập hợp các thuật toán thực thi suy đoán được sử dụng để phân chia các giao dịch thành những giao dịch có thể được thực hiện song song một cách an toàn và những giao dịch phải được thực hiện tuần tự .

  Bạn cũng có thể nghĩ lập lịch trình đồng thời là kết quả của việc kết hợp tất cả các khối DAG riêng lẻ thành một khối duy nhất và nhúng từng khối PBFT.

Ngoài sự đồng thuận, chúng tôi sẽ tiếp tục chia sẻ nhiều công nghệ thú vị hơn và phát hành chúng trong quá trình nghiên cứu và triển khai.

Giữ nguyên!