Practical Byzantine Fault Tolenrance 201

Bài này tập trung vào thuật toán Byzantine Paxos với biến thể nổi tiếng nhất là Practical Byzantine Fault Tolenrance (PBFT).

Sơ lược về bài toán các vị tướng Byzantine

Bài toán các vị tướng Byzantine (Byzantine Generals) là một bài toán trong khoa học máy tính về đường truyền tin cậy, bộ xử lý lỗi trong một hệ phân tán.

Nội dung của bài toán này như sau:

Có N tướng cầm các cánh quân khác nhau Có M tướng phản bội, cố gắng ngăn cản các tướng khác làm theo thỏa thuận:

4 tướng muốn tấn công
4 tướng muốn rút quân
1 tướng phản bội nói với nhóm thứ nhất là muốn tấn công, nói với nhóm thứ 2 là muốn rút quân

Các tướng trung thành làm thế nào để đạt được thỏa thuận?

Một trong những cách giải quyết Byzantine Generals:

Nếu có M tướng phản bội, phải có ít nhất 2M+1 tướng trung thành. Như vậy tổng cộng sẽ có M+1 vòng trao đổi thông điệp. Tổng cộng cần có O(MN2) thông điệp trao đổi, việc này rất tốn kém.

Thuật toán Byzantine Paxos

Thuật toán Paxos được mở rộng cho môi trường thực tế trong đó các node bị lỗi (ngẫu nhiên hoặc bị tấn công) tại các thời điểm ngẫu nhiên, hoặc là bị lợi dụng để phá hoại. Thuật toán mở rộng đó là Byzantine Paxos.

Byzantine Paxos được giới thiệu vào năm 1999 bởi Castro và Liskov (Lab of computer science, MIT), đã thêm 1 bản tin verify để kiểm tra tính đúng đắn và khả năng đồng thuận của các node trong mạng.

Thuật toán Byzantine Paxos được ứng dụng rộng rãi thông qua phiên bản thực hành và có nhiều sửa đổi phù hợp với các hành vi xảy ra trong thực tế có tên là Practical Byzantine Fault Tolerance (PBFT). Ngày nay PBFT dần được ứng dụng rộng rãi bởi vì hiện trạng ngày càng gia tăng của các vụ tấn công mạng dẫn tới tỉ lệ lỗi ở các node mạng rất cao. Các node mạng bị hiện tượng đó gọi chung là faulty node.

Thuật toán PBFT

PBFT sử dụng trong state machine replication được mô hình hoá như sau: mỗi node mạng được xem như một state machine có chức năng xử lý truy vấn của client và replicate trạng thái của nó tới các node mạng khác. Các node gọi là các replica. PFBT có thể hoạt động với R replicas được đánh số từ 0,1,…,R-1. Với R = 3f+1, f là số replica tối đa có khả năng bị lỗi trong mạng.

Vai trò của các node replica:

PBFT quy định số tự nhiên view v đại diện cho khung thời gian mà các node mạng hoạt động ổn định.
Trong mỗi view v, có 1 replica được bầu là primary, các replica khác là backup
Primary của view v được xác định bằng công thức: p = v mod R
Cứ mỗi khi primary có sự cố, v sẽ được tăng lên v+1.

Thuật toán PBFT về cơ bản hoạt động như sau:

Client gửi request tới primary để thực hiện 1 hành động (operation)
Primary sẽ truyền multicast tới các backup
Các node đồng loạt thực hiện request và gửi response về cho client
Client sẽ đợi cho tới khi nhận đủ f+1 response giống nhau thì response được chấp nhận là hợp lệ.

Lưu ý: Cũng như các kĩ thuật state machine replication khác, 2 yêu cầu sau cần phải thoả mãn trong PBFT:

Việc execute các request của client là deterministic - nghĩa là cùng trạng thái, cùng request đầu vào thì kết quả ra phải giống nhau.
Toàn bộ replicas cùng start ở 1 state giống nhau.

Client

Client c gửi truy vấn tới primary thông qua bản tin REQUEST có dạng: (REQUEST,o,t,c) trong đó t là timestamp tại lúc gửi và o là operation mà c muốn truy vấn. Sau khi thực hiện PBFT, các replica sẽ gửi lại client bản tin REPLY có dạng: (REPLY,v,t,c,i,r) trong đó:

v là view hiện tại
t là timestamp của bản tin REQUEST
i là số hiệu của replica
r là kết quả thực hiện operation o

Client sẽ đợi đủ f+1 bản tin REPLY có t và r giống nhau thì mới chấp nhận kết quả r. Điều đó có nghĩa là hệ thống có ít nhất f replica không bị lỗi.

Nếu client không nhận đủ REPLY trong khoảng thời gian timeout, nó sẽ broadcast bản tin REQUEST tới toàn bộ replicas (đề phòng trường hợp primary đã lỗi). Khi đó nếu replica nào đã ghi nhận bản tin REQUEST này đã xử lý thì nó lập tức gửi lại bản tin RESPONSE, ngược lại nó sẽ forward REQUEST tới primary nó đang biết.

Nếu primary không hoạt động trong khoảng thời gian timeout, hệ thống sẽ tiến hành đổi view bằng giao thức view_change sẽ đề cập sau.

Cách PBFT hoạt động trong điều kiện bình thường

Trong điều kiện không có lỗi, các node replicas hoạt động đều đặn và toàn bộ các bản tin trao đổi được ghi lại trong hệ thống message log.

Trạng thái của mỗi replica bao gồm: trạng thái của service, message log chứa các msg mà replica đó đã chấp nhân và xử lý, số tư nhiên v là view hiện tại của replica đó.

Khi primary p nhân được request tư client (m), nó sẽ bắt đầu giao thức 3 bước để multicast request đó tơi các backup/replicas. Primary xứ lý ngay mà k cần đợi, nếu sô request vượt quá maximum thì request sẽ được buffer xử lý dần. Giao thức 3 bước bao gồm: pre-prepare, prepare và commit. Hai bước đầu được sử dụng để sắp xếp các request gửi đi theo cùng view. Hai bước sau được sử dụng để chắc chắn các requests được sắp xếp chuẩn.

Bước 1: pre-prepare

Primary thiết lập số tuần tự n cho request, multicast bản tin pre-prepare với bản tin request của client (m), tới tất cả các backups và lưu bản tin lại vào log của nó. Bản tin pre-prepare có định dạng: (<PRE-PREPARE,v,n,d>,m) trong đó: v - view hiện tại, m - request của client, d - là digest của bản tin m. Lưu ý bản tin request m không được gắn vào bản tin pre-prepare để tối ưu kích thước dữ liệu. Bản tin pre-prepare mục đích chính là truyền số thứ tự n và số view v.

Các backup chỉ chấp nhận bản tin pre-prepare khi thoả mãn:

d đúng là digest của m, thông qua việc tính lại d từ request m nó có.
view v giống nhau.
số thứ tự n nằm trong khoảng h <= n <= H (h: low watermark, H: high watermark). Điều kiện này đảm bảo không có node xấu gửi số cực lớn làm hỏng danh sách tuần tự hiện tại.

Bước 2: prepare

Khi một replica i đồng ý bản tin pre-prepare, nó sẽ tạo bản tin prepare và multicast tới các replicas khác, đồng thời ghi vào log hoạt động. Bản tin prepare bao gồm (PREPARE,v,n,d,i). Nếu nó không đồng ý, nó sẽ không làm gì cả. Bản tin prepare chỉ được chấp nhận khi: đúng chữ ký, số view v trùng nhau, số tuần tự n nằm trong khoảng (h,H)

Cặp bản tin pre-prepare và prepare được ghi nhận là hợp lệ trên replica i nếu nó đã lưu những thông tin kia vào log: request m, số view v, số tuần tự n, có 2f bản tin prepare nhận về từ các replicas khác là khớp với bản tin pre-prepare nó đang có. Việc kiểm tra được thực hiện bằng cách so sánh số n, v và digest d.

Bước 3: Commit

Replica i sẽ multicast bản tin commit khi nhận đủ bản tin prepare. Nội dung bản tin (COMMIT,v,n,D(m),i) tới các replicas khác. Các replica khi nhận bản tin commit sẽ đồng ý thêm vào log của mình nếu đủ điều kiện: số view v và số tuần tự n giống nhau.

Có hai trạng thái commit: committed và committed-local như sau:

committed: nếu có f+1 replicas cùng đồng bộ với nhau về m,v,n
committed-local nếu replica i đó nhận được 2f+1 bản tin commit đúng.

Replica sẽ thực hiện request m của client sau khi đạt điều kiện committed-local và số n đảm bảo tính tuần tự 1) là lớn nhất trong những số đã được xử lý trước đó 2) tăng dần đều. Ngoài ra timestamp cũng cần thoả mãn tính tuần tự.

Hình dưới mô tả hoạt động của thuật toán với C là client, node 0 là primary, node 1,2,3 là replicas với node 3 là faulty.

Garbage Collection (Dọn dẹp dữ liệu cũ)

Trên mỗi replica, hệ thống message log sẽ bị đầy dần theo thời gian. Việc phát hiện các bản tin nào không còn dùng nữa là rất cần thiết: khi request m đã được thực hiện bởi ít nhất f+1 non-faulty replicas. Ngoài ra, khi replicas bị thiếu những message đã bị các replicas khác từ chối, nó sẽ cần phải đồng bộ lại trạng thái với các replicas khác. Việc đồng bộ này diễn ra định kỳ (hằng số xác định trước) chứ không phải tại mọi request. Thời điểm diễn ra đồng bộ trạng thái gọi là thời điểm checkpoint.

Mỗi replica sẽ tự lưu lại một số bản copy của state: state tại lần checkpoint cuối cùng, một số checkpoint chưa stable, và state hiện tại. Có thể sử dụng kĩ thuật copy-on-write để giảm dung lượng state cần lưu trữ (bàn sau).

Việc chứng minh tính đúng đắn của bản checkpoint được thực hiện như sau:

Replica i muốn thực hiện checkpoint, nó sẽ gửi multicast bản tin (CHECKPOINT,n,d,i) tới các replicas khác. Trong đó: n là số tuần tự của request cuối cùng, d là digest của state.
Mỗi replica ghi nhận các bản tin checkpoint vào message log cho tới khi nó nhận đủ 2f+1 bản tin cùng số n và d. Khi đó, checkpoint được xem là đúng đắn và đạt trạng thái stable. => Nghĩa là 2f+1 node đồng ý!

Khi checkpoint s được coi là đúng đắn, toàn bộ các bản tin pre-prepare, prepare, commit có số tuần tự <= n trong message log sẽ bị xóa để giảm dung lượng lưu trữ. Đồng thời các checkpoint sau đó có số tuần tự <=n cũng sẽ bị từ chối.

Việc kiểm tra tính toàn vẹn dữ liệu phụ thuộc vào thuật toán mã hoá được sử dụng cho digest d. Số checkpoint cũng được sử dụng để tính toán lại cận trên H cận dưới h như sau:

h = số tuần tự của checkpoint cuối cùng
H = h + k (k là hằng số xác định trước, đủ lớn để replicas ko phải đợi cho tới khi checkpoint đạt stable)

View Changes

Giao thức view-change giúp hệ thống tiếp tục vận hành khi node primary bị lỗi. Nó được trigger khi hết timeout để giúp các node replicas khác không phải đợi multicast mãi.

Các backup replicas (non-primary) sẽ tiến hành đợi request khi nó đã nhận 1 request hợp lệ nhưng chưa xử lý. Node backup sẽ khởi động tiến trình timer mỗi khi nó nhận 1 request và timer dừng khi hết timeout mà node đó chưa xử lý thêm request nào khác.

Nếu timer bị dừng trong view v, node backup đó sẽ đổi view sang v+1. Đồng nghĩa với việc nó từ chối nhận tất cả các bản tin tới có số view là v, đồng thời nó truyền multicast bản tin view-change (VIEW-CHANGE,v+1,n,C,P,i) tới tất cả các replicas khác. Trong đó: n là số tuần tự của checkpoint (s) stable gần nhất mà nó (replica i) biết, C là tập 2f+1 bản tin checkpoint mà nó giữ chứng minh tính đúng đắn của s, P là tập tất cả các bản tin pre-prepare, prepare của các request m có 1) số tuần tự lớn hơn n, 2) cùng view v mà được nó (replica i) tạo bản tin prepare, cùng với digest của m.

Khi node primary p của view v+1 nhận đủ 2f bản tin view-change cho view v+1 từ các replicas, nó truyền multicast bản tin new-view (NEW-VIEW,v+1,V,O) tới tất cả replicas trong đó: V là tập các bản tin view-change nó nhận được, O là tập các bản tin pre-prepare. Cách xác định O sẽ viết sau.

Một số implementation sử dụng PBFT

Bitcoin
Boeing 777, 787 Aircraft Information Management System, Flight Control System
Spacecraft flight system: SpaceX Dragon
Tendermint Core

Một số biến thể khác của PBFT

Sau khi Castro và Liskov công bố PBFT năm 1999, có một số biến thể của nó nhằm cải thiện tốc độ như Q/U, HQ, Zyzzyva, ABsTRACTs, A2M-PBFT-EA, MinBFT.

Referrence

http://pmg.csail.mit.edu/papers/osdi99.pdf