Phân tích bảo mật thỏa thuận Byzantine của Tendermint BFT | Cột Sperax

Tác giả: Giáo sư Wang Yongge, một nhà mật mã học nổi tiếng người Trung Quốc, giáo sư chính thức của Khoa Khoa học Máy tính tại Đại học Bắc Carolina ở Charlotte (UNC, Charlotte), và bằng tiến sĩ của Đại học Heidelberg ở Đức.

Trong bài viết trước, chúng tôi đã phân tích các vấn đề bảo mật của Thỏa thuận Byzantine PBFT. Hôm nay chúng ta thảo luận về các vấn đề bảo mật của Thỏa thuận Byzantine Tendermint BFT, một hệ thống blockchain khác được sử dụng rộng rãi. Thỏa thuận BFT Byzantine của Tendermint có thể được coi là phiên bản cải tiến của Thỏa thuận Byzantine PBFT. Theo thống kê mới nhất, Thỏa thuận Byzantine Tendermint BFT được sử dụng bởi hơn 40% chuỗi khối PoS (Xem bài phát biểu gần đây của Jae Kwon: Tendermint hỗ trợ hơn 40% tất cả các chuỗi khối bằng chứng cổ phần ). Ví dụ: chuỗi công khai Cosmos (thường được gọi là "Internet của Blockchain" ) Cả Thỏa thuận Byzantine Tendermint BFT và chuỗi liên minh Hyperledger Burrow đều sử dụng Thỏa thuận Byzantine Tendermint BFT. Phân tích của chúng tôi dựa trên giao thức Tendermint BFT từ bài viết sau:

-E. Buchman, J. Kwon và Z. Milosevic . Tin đồn mới nhất về sự đồng thuận của BFT. Bản in trước arXiv:1807.04938, 2018. /1807.04938.pdf

Tác giả của Tendermint BFT tuyên bố rằng giao thức này được bảo mật trong các mạng không đồng bộ. Trong bài viết trước, chúng tôi đã đề cập rằng các mạng không đồng bộ thường được sử dụng được đặc trưng bởi mô hình sau:

-Có Thời gian ổn định toàn cầu (GST) mà trước đó mọi tin nhắn có thể bị mất (chẳng hạn như một cuộc tấn công DoS) hoặc được sắp xếp lại. Sau GST, mạng trở thành mạng đồng bộ. Khi nào GST sẽ bắt đầu, không ai biết.

Nhưng điều chúng ta cần lưu ý là mặc dù Tendermint BFT sử dụng mô hình mạng không đồng bộ ở trên nhưng nó cũng có Giả định mạnh mẽ :

-Có một kênh liên lạc điểm-điểm đáng tin cậy và an toàn giữa tất cả các nút. Nghĩa là, nếu nút A gửi tin nhắn đến nút B. Sau đó nút B chắc chắn sẽ nhận được thông tin này một thời gian sau GST.

Đây là một giả định chắc chắn. Ví dụ, trong mô hình này, các cuộc tấn công DoS thường không được phép. Hôm nay chúng ta sẽ phân tích giao thức Tendermint BFT. Kết quả phân tích của chúng tôi là Tendermint BFT không an toàn ngay cả với các giả định mạng mạnh ở trên. Trước khi phân tích tính bảo mật của nó, trước tiên chúng tôi đưa ra mô tả chính thức về giao thức của nó.

Trong giao thức Tendermint BFT, chúng tôi giả định rằng có n=3t+1 nút P1, …, Pn. Hầu hết các nút t được kiểm soát bởi kẻ tấn công. Trong suốt quá trình chạy giao thức, mỗi nút có năm biến: step, lockV, lockR, validV và ValidR. Đối với mỗi chiều cao blockchain h, giao thức bắt đầu từ vòng 0 cho đến khi đạt được sự đồng thuận (nghĩa là: cho đến khi khối có chiều cao h được tạo ra). Giao thức sau đó chuyển sang cấp độ tiếp theo của blockchain. Mỗi vòng của giao thức bao gồm ba bước: đề xuất, bỏ phiếu trước và cam kết trước. Đối với mỗi chiều cao blockchain h, trước tiên mỗi nút khởi tạo năm biến của mình: bước = đề xuất, khóaV = nil, lockR = −1, validV = nil và ValidR = −1. Sau đó, tất cả các nút thực hiện giao thức bắt đầu từ vòng 0 cho đến khi khối có chiều cao h được tạo. Mỗi vòng r có một nhà tài trợ được công nhận. Danh tính của người đề xuất được xác định bởi người đề xuất chức năng công khai(h, r). Quá trình làm tròn r có độ cao h như sau:

1.propose: Người quảng bá Pi = người đề xuất(h, r) Phân biệt hai tình huống:

    ◎r=0 hoặc validV=nil: Pi chọn đề xuất v của riêng mình và đặt vr=−1.

    ◎r>0 và validV¹nil: Pi đặt v=validV và đặt vr=ValidR 

Sau đó, Pi phát thông báo sau tới tất cả các nút

2. prevote: Tất cả các nút Pj trong bước = đề xuất phân biệt ba tình huống sau: 

    ◎Pj nhận được ⟨ĐỀ XUẤT, h, r, v, vr　 từ Pi trong đó vr = −1: Nếu lockR = −1 hoặc validV =v, thì Pj sẽ phát thông báo sau tới tất cả các nút ⟨PREVOTE, h, r,H(v)　. Nếu không, Pj sẽ phát thông báo sau ⟨PREVOTE,h,r,nil　 tới tất cả các nút. Pj đặt bước = bỏ phiếu trước.

    ◎o Pj Trong số ⟨ĐỀ XUẤT, h, r, v, vr　 nhận được từ Pi, vr >−1 và Pj đã nhận được ít nhất 2t + 1 ⟨TRƯỚC, h, vr, H(v)　: Pj phân biệt hai loại sau Tình huống

        ●lockedR ≤ vr hoặc lockV = v: Pj phát thông báo sau tới tất cả các nút ⟨PREVOTE, h, r, H(v)　

        ●Nếu không thì Pj sẽ phát thông báo sau tới tất cả các nút ⟨PREVOTE,h,r,nil　

Pj đặt bước = bỏ phiếu trước.

    ◎Pj nhận được từ Pi ⟨ĐỀ XUẤT, h, r, v, vr in vr >−1 Nhưng Pj vẫn chưa đã nhận được 2t+1

    ⟨PREVOTE,h,vr,H(v)　: Pj không làm gì cả.

3. cam kết trước:

    ◎Bất cứ khi nào nút Pj ở trạng thái bỏ phiếu trước nhận được tin nhắn 2t + 1 A ⟨ PREVOTE, h, r, ∗　, Pj khởi tạo hàm đếm thời gian chờ OnTimeoutPrevote(h, r).

    ◎Mọi lúc Nút Pj ở trạng thái bỏ phiếu trước nhận được tin nhắn 2t + 1 ⟨PREVOTE, h, r, nil　 và Pj phát tin nhắn ⟨PRECOMMIT, h, r, nil　 tới tất cả các nút có bước = precommit.

    ◎Nếu Pj ở trạng thái bỏ phiếu trước hoặc cam kết trước trạng thái và đã nhận được ⟨ĐỀ XUẤT, h, r, v, vr　 từ Pi và nhận được ít nhất 2t + 1 tin nhắn ⟨BỎ TRƯỚC, h, r từ tất cả các nút , H( v)　, thì Pj thực hiện các bước sau 

        ●Nếu bước = bỏ phiếu trước, thì Pj đặt lockV = v, lockR = r và phát thông báo tới tất cả các nút ⟨PRECOMMIT, h , r, H(v)　 và đặt bước = cam kết trước.

        ●Pj đặt validV = v và validR = r.

4. quyết định: Bất cứ khi nào nút Pj nhận được tin nhắn 2t + 1 ⟨PRECOMMIT, h, r, ∗ , Pj khởi tạo hàm đếm thời gian chờ OnTimeoutPrecommit(h, r). Nếu Pj chưa đưa ra quyết định ban đầu về khối có chiều cao h và nhận được ⟨ĐỀ XUẤT, h, r, v, vr　 từ Pi thì nó đã nhận được ít nhất 2t + 1 tin nhắn ⟨PRECOMMIT, h, r, H từ các nút khác .(v)　, thì Pj xác định rằng v là một khối có chiều cao h và khởi tạo năm biến toàn cục của mình. Sau đó vào vòng 0 với chiều cao h+1.

5. Cập nhật vòng tự động: Nếu nút Pj nhận được tin nhắn t + 1 vòng r′ > r bất kỳ lúc nào thì Pj sẽ tự động chuyển sang vòng r '.

6. Chức năng đếm thời gian chờ:
    (a) OnTimeoutPropose(h, r): Phát sóng ⟨PREVOTE, h, r,nil　 và đặt bước = bỏ phiếu trước.
    (b) OnTimeoutPrevote(h, r): Phát sóng ⟨PRECOMMIT, h, r,nil　 và đặt bước = precommit
    (c) OnTimeoutPrecommit(h, r): Nhập vòng r + 1 với chiều cao h.

Gần đây, chúng tôi đã phân tích tính bảo mật của Tendermint BFT trong bài viết sau:

-Yongge Wang. Khả năng chịu lỗi của Byzantine trong Mạng không đồng bộ được kết nối một phần

Bài phân tích này kết luận rằng giao thức đồng thuận Tendermint BFT không an toàn trong mạng không đồng bộ. Trong bài viết này, chúng tôi giới thiệu ngắn gọn về phương pháp tấn công mà chúng tôi đã thiết kế nhằm chống lại giao thức Tendermint BFT trong các mạng không đồng bộ. Để đơn giản hóa mô tả của chúng tôi, chúng tôi giả sử rằng hệ thống có n=3+1=4 nút P1, P2, P3, P4. Trong số đó, nút P1 bị kẻ tấn công kiểm soát. Ngoài ra, chúng ta giả sử rằng điểm khởi đầu của vòng 0 là P1. Cuộc tấn công của chúng ta được phát động ở vòng 0:

1. Ở vòng 0 có độ cao h, P1 chọn khối hợp lệ nhỏ nhất có thể v làm đề xuất. P1 phát thông báo ⟨ĐỀ XUẤT, h, 0, v, −1　 tới các nút P1, P2 và P3.

2. Sau khi nhận được tin nhắn ⟨PROPOSAL, h, 0, v, −1　, P1 phát tin nhắn ⟨PREVOTE, h tới các nút P2 và P3 , 0, H(v)　, các nút P2 và P3 phát thông báo ⟨PREVOTE, h, 0, H(v)　 tới tất cả các nút. Các nút P1, P2, P3 đặt bước = bỏ phiếu trước.

3. Nút P2 và P3 nhận được 2 + 1=3 tin nhắn ⟨PREVOTE, h, 0, H (v ) . Vì vậy, các nút P2 và P3 được đặt lockV = v, lockR = 0, step = precommit, validV = v, validR = 0. Sau đó, các nút P2 và P3 phát thông báo ⟨PRECOMMIT, h, 0, H(v)　 tới tất cả các nút.

4. Vì mỗi nút nhận được tối đa 1+1=2 thông báo xác nhận trước nên không nút nào có thể Xác định được khối có chiều cao h tại vòng 0.

5. Sau khi bộ đếm thời gian chờ của vòng 0 hết hạn (chúng tôi cho rằng GST chưa đến), tất cả các nút nhập chiều cao là vòng 1 của h.

6. Kể từ đó trở đi, nút P1 chuyển sang trạng thái ngủ và không còn tham gia thực hiện bất kỳ giao thức nào.

7. Nếu người khởi xướng vòng 1 là P2 (hoặc P3), P2 sẽ phát thông báo tới tất cả các nút⟨ ĐỀ XUẤT, h, 1, v, 0　. Bởi vì nút P4 nhận được tối đa t + 1 tin nhắn đề xuất cho v ở vòng 0, P4 không làm gì cho đến khi bộ đếm hết thời gian chờ hết hạn. Do đó, không có nút trung thực nào có thể nhận đủ thông báo bỏ phiếu trước để giao thức tiến hành bước tiếp theo. Sau khi bộ đếm thời gian chờ của vòng 1 hết hạn (chúng tôi giả định rằng GST chưa đến), tất cả các nút sẽ vào vòng 2 với chiều cao h.

8. Nếu người khởi xướng vòng 1 là P4, P4 sẽ phát thông báo ⟨PROPOSAL, h, 1, v′, −1　 tới tất cả các nút. . Bởi vì nút P0 đã chọn khối hợp pháp nhỏ nhất v ở vòng 0, nên các giao dịch mới đã được gửi trong khoảng thời gian vừa qua, do đó với xác suất cao, v′ và v khác nhau. Do đó, các nút P2 và P3 sẽ không chấp nhận v′ mà phát thông báo ⟨PROVOTE, h, 1, nil　 tới tất cả các nút. Sau khi bộ đếm thời gian chờ của vòng 1 hết hạn (chúng tôi giả định rằng GST chưa đến), tất cả các nút sẽ vào vòng 2 với chiều cao h.

9. Quá trình này sẽ tiếp tục. Tất cả các khối có chiều cao h không bao giờ có thể được tạo ra. Hệ thống đi vào một vòng lặp vô hạn.

Cuộc tấn công trên của chúng tôi có thể được triển khai trước thuế GST trên các mạng không đồng bộ. Do đó, khi mạng bắt đầu đồng bộ hóa, hệ thống đã không thể tiếp tục hoạt động do các giá trị bị khóa bởi mỗi nút là khác nhau.

Xem các bài viết khác do Giáo sư Wang Yongge xuất bản trên BlockBeats:

Nhà khoa học trưởng Wang Yongge của Sperax: PoS bị nghi ngờ là tập trung hóa và PoTR là giải pháp tốt nhất hiện nay

Phân tích bảo mật thỏa thuận Byzantine PBFT: Không phù hợp với chuỗi liên minh hoặc chuỗi công khai - BlockBeats

Sự đồng thuận của Byzantine không còn có thể đáp ứng nhu cầu bảo mật của chuỗi công cộng và tập đoàn ngày nay - BlockBeats

Sperax: Đặt cược vào ổ flash USB? Thiết kế PoS dựa trên nguồn ngẫu nhiên phần cứng | Giới thiệu dự án mới-BlockBeats

Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia