2018 Tháng tám 07
Xem tất cả bài viết
Đặc biệt cảm ơn Emin Gun Sirer đã xem xét
Từ lâu, chúng tôi đã nghe nói rằng có thể đạt được sự đồng thuận với khả năng chịu lỗi 50% trong một mạng đồng bộ nơi các thông báo được phát bởi bất kỳ nút trung thực nào được đảm bảo sẽ được nhận bởi tất cả các nút trung thực khác trong một khoảng thời gian xác định (nếu kẻ tấn công có hơn hơn 50%, chúng có thể thực hiện “cuộc tấn công 51%” và có một sự tương tự của điều này đối với bất kỳ thuật toán nào thuộc loại này). Chúng tôi cũng đã nghe từ lâu rằng nếu bạn muốn nới lỏng giả định đồng bộ và có một thuật toán “an toàn trong điều kiện không đồng bộ”, khả năng chịu lỗi tối đa có thể đạt được giảm xuống 33% (PBFT, Casper FFG, v.v. đều rơi vào trường hợp này thể loại). Nhưng bạn có biết rằng nếu bạn thêm thậm chí nhiều hơn giả định (cụ thể, bạn yêu cầu người quan sát, I E. người dùng không tích cực tham gia vào sự đồng thuận nhưng quan tâm đến đầu ra của nó, cũng đang tích cực theo dõi sự đồng thuận và không chỉ tải xuống đầu ra của nó sau khi thực tế), bạn có thể tăng khả năng chịu lỗi lên 99% không?
Trên thực tế, điều này đã được biết đến từ lâu; Bài báo nổi tiếng năm 1982 của Leslie Lamport “The Byzantine Generals Problem” (liên kết tại đây) chứa một mô tả về thuật toán. Sau đây sẽ là nỗ lực của tôi để mô tả và định dạng lại thuật toán ở dạng đơn giản hóa.
Giả sử rằng có \(N\) các nút tham gia đồng thuận và mọi người đều đồng ý rằng các nút này là ai trước thời hạn (tùy thuộc vào ngữ cảnh, chúng có thể đã được chọn bởi một bên đáng tin cậy hoặc, nếu mong muốn phân cấp mạnh mẽ hơn, bằng một số chương trình bằng chứng công việc hoặc bằng chứng cổ phần). Chúng tôi dán nhãn các nút này \(0 …N-1\). Cũng giả sử rằng có một giới hạn đã biết \(D\) về độ trễ của mạng cộng với chênh lệch xung nhịp (ví dụ: \(D\) = 8 giây). Mỗi nút có khả năng xuất bản một giá trị tại thời điểm \(T\) (một nút độc hại tất nhiên có thể đề xuất các giá trị sớm hơn hoặc muộn hơn \(T\)). Tất cả các nút chờ \((N-1) \cdot D\) giây, chạy quy trình sau. Định nghĩa \(x : i\) là “giá trị \(x\) được ký bởi nút \(tôi\)“, \(x : tôi : j\) là “giá trị \(x\) ký kết bởi \(tôi\)và giá trị đó cùng với chữ ký được ký bởi \(j\)“, v.v. Các đề xuất được công bố trong giai đoạn đầu tiên sẽ ở dạng \(v: tôi\) cho một số \(v\) và \(tôi\)chứa chữ ký của nút đã đề xuất nó.
Nếu một trình xác nhận \(tôi\) nhận được một số tin nhắn \(v : tôi[1] : … : tôi[k]\)ở đâu \(tôi[1] … tôi[k]\) là một danh sách các chỉ mục đã (tuần tự) ký vào tin nhắn rồi (chỉ \(v\) tự nó sẽ được tính là \(k=0\)và \(v:i\) như \(k=1\)), thì trình xác thực sẽ kiểm tra xem (i) thời gian có nhỏ hơn \(T + k \cdot D\)và (ii) họ chưa nhìn thấy một tin nhắn hợp lệ có chứa \(v\); nếu cả hai kiểm tra vượt qua, họ xuất bản \(v : tôi[1] : … : tôi[k] : tôi\).
Ở thời điểm \(T + (N-1) \cdot D\), các nút ngừng lắng nghe. Tại thời điểm này, có một sự đảm bảo rằng tất cả các nút trung thực đều “được nhìn thấy một cách hợp lệ” cùng một bộ giá trị.
Nút 1 (màu đỏ) là độc hại và nút 0 và 2 (màu xám) là trung thực. Khi bắt đầu, hai nút trung thực đưa ra đề xuất của họ \(y\) và \(x\)và kẻ tấn công đề xuất cả hai \(w\) và \(z\) muộn. \(w\) đến nút 0 đúng lúc nhưng không đến nút 2 và \(z\) không đến được nút nào đúng giờ. Ở thời điểm \(T + Đ\)các nút 0 và 2 phát lại tất cả các giá trị mà chúng thấy rằng chúng chưa được phát nhưng thêm chữ ký của chúng vào (\(x\) và \(w\) cho nút 0, \(y\) cho nút 2). Cả hai nút trung thực đã thấy \({x, y, w}\).
Nếu vấn đề yêu cầu chọn một giá trị, họ có thể sử dụng một số hàm “lựa chọn” để chọn một giá trị duy nhất trong số các giá trị mà họ đã thấy (ví dụ: họ chọn giá trị có hàm băm thấp nhất). Các nút sau đó có thể đồng ý về giá trị này.
Bây giờ, hãy khám phá lý do tại sao điều này hoạt động. Điều chúng ta cần chứng minh là nếu một nút trung thực đã nhìn thấy một giá trị cụ thể (hợp lệ), thì mọi nút trung thực khác cũng đã thấy giá trị đó (và nếu chúng ta chứng minh điều này, thì chúng ta biết rằng tất cả các nút trung thực đã nhìn thấy cùng một tập hợp và vì vậy nếu tất cả các nút trung thực đang chạy cùng một chức năng lựa chọn, thì chúng sẽ chọn cùng một giá trị). Giả sử rằng bất kỳ nút trung thực nào cũng nhận được thông báo \(v : tôi[1] : … : tôi[k]\) mà họ cho là hợp lệ (tức là nó đến trước thời gian \(T + k \cdot D\)). Giả sử \(x\) là chỉ mục của một nút trung thực khác. Hoặc \(x\) là một phần của \({tôi[1] … tôi[k]}\) hoặc nó không phải là.
- Trong trường hợp đầu tiên (giả sử \(x = tôi[j]\) đối với thông báo này), chúng tôi biết rằng nút trung thực \(x\) đã phát tin nhắn đó và họ đã làm như vậy để trả lời tin nhắn có \(j-1\) chữ ký mà họ nhận được trước thời gian \(T + (j-1) \cdot D\)vì vậy chúng phát tin nhắn của mình vào thời điểm đó và vì vậy tất cả các nút trung thực phải nhận được tin nhắn trước thời điểm \(T + j \cdot D\).
- Trong trường hợp thứ hai, vì nút trung thực nhìn thấy thông báo trước thời gian \(T + k \cdot D\)sau đó họ sẽ phát đi thông điệp có chữ ký của mình và đảm bảo rằng tất cả mọi người, kể cả \(x\)sẽ thấy nó trước khi thời gian \(T + (k+1) \cdot D\).
Lưu ý rằng thuật toán sử dụng hành động thêm chữ ký của chính một người như một loại “vết sưng” khi hết thời gian chờ của tin nhắn và chính khả năng này đảm bảo rằng nếu một nút trung thực nhìn thấy tin nhắn đúng lúc, họ có thể đảm bảo rằng những người khác nhìn thấy thông báo cũng đúng hạn, vì định nghĩa về “đúng giờ” tăng nhiều hơn độ trễ của mạng với mỗi chữ ký được thêm vào.
Trong trường hợp một nút là trung thực, chúng tôi có thể đảm bảo rằng thụ động người quan sát (tức là các nút không tham gia đồng thuận quan tâm đến việc biết kết quả) cũng có thể thấy kết quả, ngay cả khi chúng tôi yêu cầu họ phải theo dõi toàn bộ quá trình? Với sơ đồ như đã viết, có một vấn đề. Giả sử rằng một chỉ huy và một số tập hợp con của \(k\) trình xác thực (độc hại) tạo ra một thông báo \(v : tôi[1] : …. : tôi[k]\)và phát trực tiếp cho một số “nạn nhân” ngay trước thời điểm \(T + k \cdot D\). Các nạn nhân thấy thông báo là “đúng giờ”, nhưng khi họ phát lại nó, nó chỉ đến được tất cả các nút tham gia đồng thuận trung thực sau \(T + k \cdot D\)và vì vậy tất cả các nút tham gia đồng thuận trung thực đều từ chối nó.
Nhưng chúng ta có thể cắm lỗ này. Chúng tôi yêu cầu \(D\) là một ràng buộc trên hai lần độ trễ mạng cộng với chênh lệch đồng hồ. Sau đó, chúng tôi đặt thời gian chờ khác cho người quan sát: người quan sát chấp nhận \(v : tôi[1] : …. : tôi[k]\) Trước thời gian đó \(T + (k – 0,5) \cdot D\). Bây giờ, giả sử một người quan sát thấy một tin nhắn và chấp nhận nó. Họ sẽ có thể phát nó đến một nút trung thực trước thời gian \(T + k \cdot D\)và nút trung thực sẽ đưa ra thông báo có đính kèm chữ ký của họ, chữ ký này sẽ đến được tất cả những người quan sát khác trước thời hạn \(T + (k + 0,5) \cdot D\)thời gian chờ cho tin nhắn với \(k+1\) chữ ký.
Trang bị thêm cho các thuật toán đồng thuận khác
Về mặt lý thuyết, điều trên có thể được sử dụng như một thuật toán đồng thuận độc lập và thậm chí có thể được sử dụng để chạy một chuỗi khối bằng chứng cổ phần. Bộ xác thực của vòng \(N+1\) của sự đồng thuận có thể được quyết định trong vòng \(N\) của sự đồng thuận (ví dụ: mỗi vòng đồng thuận cũng có thể chấp nhận các giao dịch “gửi tiền” và “rút tiền”, nếu được chấp nhận và ký chính xác sẽ thêm hoặc xóa trình xác thực vào vòng tiếp theo). Thành phần bổ sung chính cần được bổ sung là cơ chế quyết định ai được phép đề xuất khối (ví dụ: mỗi vòng có thể có một người đề xuất được chỉ định). Nó cũng có thể được sửa đổi để có thể sử dụng như một chuỗi khối bằng chứng công việc, bằng cách cho phép các nút tham gia đồng thuận “tự tuyên bố” trong thời gian thực bằng cách xuất bản giải pháp bằng chứng công việc trên khóa công khai của chúng cùng lúc với việc ký kết một tin nhắn với nó.
Tuy nhiên, giả định về tính đồng bộ rất mạnh và vì vậy chúng tôi muốn có thể làm việc mà không cần nó trong trường hợp chúng tôi không cần nhiều hơn 33% hoặc 50% khả năng chịu lỗi. Có một cách để thực hiện điều này. Giả sử rằng chúng ta có một số thuật toán đồng thuận khác (ví dụ: PBFT, Casper FFG, PoS dựa trên chuỗi) có đầu ra có thể được nhìn thấy bởi những người quan sát trực tuyến thỉnh thoảng (chúng tôi sẽ gọi đây là phụ thuộc vào ngưỡng thuật toán đồng thuận, trái ngược với thuật toán ở trên, mà chúng ta sẽ gọi là phụ thuộc vào độ trễ thuật toán đồng thuận). Giả sử rằng thuật toán đồng thuận phụ thuộc vào ngưỡng chạy liên tục, ở chế độ mà nó liên tục “hoàn thiện” các khối mới vào một chuỗi (nghĩa là mỗi giá trị cuối cùng trỏ đến một số giá trị đã hoàn thiện trước đó dưới dạng “cha mẹ”; nếu có một chuỗi các con trỏ \(A \rightarrow … \rightarrow B\)chúng tôi sẽ gọi \(MỘT\) một hậu duệ của \(B\)).
Chúng tôi có thể trang bị thêm thuật toán phụ thuộc vào độ trễ vào cấu trúc này, cho phép những người quan sát luôn trực tuyến truy cập vào một loại “mức độ cuối cùng mạnh mẽ” trên các điểm kiểm tra, với khả năng chịu lỗi ~95% (bạn có thể tùy ý đẩy mức này lên gần 100% bằng cách thêm nhiều trình xác thực hơn và yêu cầu quá trình mất nhiều thời gian hơn).
Mỗi khi thời gian đạt đến bội số nào đó của 4096 giây, chúng tôi sẽ chạy thuật toán phụ thuộc vào độ trễ, chọn 512 nút ngẫu nhiên để tham gia vào thuật toán. Đề xuất hợp lệ là bất kỳ chuỗi giá trị hợp lệ nào đã được hoàn thiện bằng thuật toán phụ thuộc vào ngưỡng. Nếu một nút nhìn thấy một số giá trị cuối cùng trước thời gian \(T + k \cdot D\) (\(D\) = 8 giây) với \(k\) chữ ký, nó chấp nhận chuỗi vào tập hợp các chuỗi đã biết của nó và phát lại chuỗi đó với chữ ký riêng được thêm vào; người quan sát sử dụng ngưỡng \(T + (k – 0,5) \cdot D\) như trước.
Chức năng “lựa chọn” được sử dụng ở cuối rất đơn giản:
- Các giá trị cuối cùng không phải là hậu duệ của giá trị đã được đồng ý là giá trị cuối cùng trong vòng trước sẽ bị bỏ qua
- Các giá trị cuối cùng không hợp lệ sẽ bị bỏ qua
- Để chọn giữa hai giá trị cuối cùng hợp lệ, hãy chọn giá trị có hàm băm thấp hơn
Nếu 5% người xác thực là trung thực, thì chỉ có khoảng 1 trên 1 nghìn tỷ khả năng không có nút nào trong số 512 nút được chọn ngẫu nhiên sẽ trung thực và miễn là độ trễ mạng cộng với chênh lệch xung nhịp nhỏ hơn \(\frac{D}{2}\) thuật toán trên sẽ hoạt động, phối hợp chính xác các nút trên một số giá trị cuối cùng duy nhất, ngay cả khi nhiều giá trị cuối cùng xung đột được hiển thị do khả năng chịu lỗi của thuật toán phụ thuộc vào ngưỡng bị hỏng.
Nếu khả năng chịu lỗi của thuật toán đồng thuận phụ thuộc vào ngưỡng được đáp ứng (thường là 50% hoặc 67% trung thực), thì thuật toán đồng thuận phụ thuộc vào ngưỡng sẽ không hoàn thiện bất kỳ điểm kiểm tra mới nào hoặc nó sẽ hoàn thiện các điểm kiểm tra mới tương thích với nhau (ví dụ: một loạt các điểm kiểm tra trong đó mỗi điểm kiểm tra trước đó là cấp độ gốc), do đó, ngay cả khi độ trễ mạng vượt quá \(\frac{D}{2}\) (hoặc thậm chí \(D\)) và kết quả là các nút tham gia thuật toán phụ thuộc vào độ trễ không đồng ý về giá trị mà chúng chấp nhận, các giá trị mà chúng chấp nhận vẫn được đảm bảo là một phần của cùng một chuỗi và do đó không có sự bất đồng thực tế nào. Khi độ trễ phục hồi trở lại bình thường trong một số vòng trong tương lai, sự đồng thuận phụ thuộc vào độ trễ sẽ “đồng bộ” trở lại.
Nếu các giả định của cả hai thuật toán đồng thuận phụ thuộc vào ngưỡng và phụ thuộc vào độ trễ bị phá vỡ đồng thời (hoặc trong các vòng liên tiếp), thì thuật toán có thể bị hỏng. Ví dụ: giả sử trong một vòng, sự đồng thuận phụ thuộc vào ngưỡng kết thúc \(Z \rightarrow Y \rightarrow X\) và sự đồng thuận phụ thuộc vào độ trễ không đồng ý giữa \(Y\) và \(X\)và trong vòng tiếp theo, sự đồng thuận phụ thuộc vào ngưỡng sẽ hoàn thành một hậu duệ \(W\) của \(X\) đó là không phải một hậu duệ của \(Y\); trong sự đồng thuận phụ thuộc vào độ trễ, các nút đã đồng ý \(Y\) sẽ không chấp nhận \(W\)nhưng các nút đã đồng ý \(X\) sẽ. Tuy nhiên, điều này là không thể tránh khỏi; sự bất khả thi của sự đồng thuận an toàn dưới sự không đồng bộ với hơn \(\frac{1}{3}\) khả năng chịu lỗi là một kết quả nổi tiếng trong lý thuyết về khả năng chịu lỗi của Byzantine, cũng như không thể có hơn \(\frac{1}{2}\) khả năng chịu lỗi thậm chí cho phép giả định đồng bộ nhưng giả sử người quan sát ngoại tuyến.
