Giao thức đồng thuận Stellar lần đầu tiên được mô tả trong David Mazier vào năm 2015 Đây là một “hệ thống thỏa thuận Byzantine liên bang” cho phép các mạng máy tính phi tập trung, không có người lãnh đạo đạt được sự đồng thuận một cách hiệu quả về một quyết định. Mạng thanh toán Stellar sử dụng Giao thức đồng thuận Stellar (SCP) để duy trì lịch sử giao dịch nhất quán mà tất cả người tham gia đều có thể nhìn thấy.
Các giao thức đồng thuận được coi là khó hiểu. SCP đơn giản hơn hầu hết chúng, nhưng vẫn chia sẻ danh tiếng này - một phần do quan niệm sai lầm rằng "bỏ phiếu liên bang", chủ đề của nửa đầu bài báo khoa học, là SCP. Nhưng điều đó không đúng! Đây chỉ là một khối xây dựng quan trọng mà nửa sau của bài viết sử dụng để tạo thật sự Giao thức đồng thuận của Stellar.
Trong bài viết này, chúng tôi sẽ giải thích ngắn gọn “hệ thống thỏa thuận” là gì, điều gì có thể khiến nó trở thành “Byzantine” và tại sao lại biến hệ thống Byzantine thành “liên bang”. Sau đó, chúng tôi sẽ giải thích quy trình bỏ phiếu liên kết được mô tả trong bài viết SCP và cuối cùng chúng tôi sẽ giải thích về giao thức SCP.
Hệ thống thỏa thuận
Một hệ thống thỏa thuận cho phép một nhóm người tham gia đạt được sự đồng thuận về một chủ đề, chẳng hạn như gọi món gì cho bữa trưa.
Tại Interstellar, chúng tôi đã triển khai hệ thống thỏa thuận ăn uống của riêng mình: chúng tôi gọi món theo yêu cầu của giám đốc điều hành John. Đây là một hệ thống thỏa thuận đơn giản và hiệu quả. Tất cả chúng tôi đều tin tưởng John và tin rằng anh ấy sẽ tìm thấy điều gì đó thú vị và bổ dưỡng mỗi ngày.
Nhưng nếu John lạm dụng lòng tin của chúng ta thì sao? Anh ấy có thể tự mình quyết định rằng tất cả chúng ta nên trở thành người ăn chay. Trong một hoặc hai tuần nữa, chúng ta có thể sẽ lật đổ ông ta và trao lại quyền lực cho Elizabeth. Nhưng bỗng nhiên cô lại thích ăn bơ với cá cơm và nghĩ ai cũng phải như vậy. Quyền lực tham nhũng. Vì vậy, tốt hơn là tìm một số phương pháp dân chủ hơn: một số cách để đảm bảo rằng các sở thích khác nhau được tính đến, đồng thời đảm bảo kết quả kịp thời và rõ ràng, để không ai kết thúc việc đặt bữa trưa, hoặc năm người gọi món khác nhau, hoặc thảo luận kéo dài đến buổi tối.
Có vẻ như giải pháp rất đơn giản: tổ chức một cuộc bỏ phiếu! Nhưng đây là một ấn tượng sai lầm. Ai sẽ thu phiếu bầu và báo cáo kết quả? Và tại sao người khác phải tin những gì anh ta nói? Có lẽ chúng ta có thể lúc đầu bỏ phiếu cho người lãnh đạo mà chúng ta tin tưởng sẽ dẫn đầu cuộc bỏ phiếu - nhưng ai sẽ là người lãnh đạo cuộc bỏ phiếu đó đầu tiên bằng cách bỏ phiếu? Điều gì sẽ xảy ra nếu chúng ta không thể thống nhất về một người lãnh đạo? Hoặc điều gì sẽ xảy ra nếu chúng ta đạt được thỏa thuận nhưng người lãnh đạo này lại bận họp hoặc phải nghỉ ốm?
Các vấn đề tương tự xảy ra trong các mạng máy tính phân tán. Tất cả người tham gia hoặc nút phải đồng ý về một số quyết định, chẳng hạn như đến lượt ai cập nhật tệp được chia sẻ hoặc xóa tác vụ khỏi hàng đợi xử lý. Trong mạng tiền điện tử, các nút liên tục phải chọn toàn bộ câu chuyện sẽ trông như thế nào từ một số phiên bản có thể, điều này đôi khi xung đột. Thỏa thuận mạng này cung cấp sự đảm bảo cho người nhận rằng đồng xu đó (a) hợp lệ (không phải giả) và (b) chưa được sử dụng ở nơi khác. Điều này cũng đảm bảo rằng anh ta sẽ có thể tiêu tiền trong tương lai vì người nhận mới sẽ có những đảm bảo tương tự vì những lý do tương tự.
Bất kỳ hệ thống đồng thuận nào trong mạng điện toán phân tán đều phải có khả năng chịu lỗi: nó phải tạo ra kết quả nhất quán bất chấp các lỗi như liên kết chậm, nút không phản hồi và thứ tự tin nhắn không chính xác. Byzantine Hệ thống thỏa thuận còn có khả năng chống lại các lỗi "Byzantine": các nút cung cấp thông tin sai lệch, cho dù là do lỗi hay do cố tình phá hoại hệ thống hoặc đạt được lợi thế nào đó. Khả năng chịu lỗi "Byzantine" - khả năng tin tưởng vào quyết định của nhóm ngay cả khi một số thành viên trong nhóm có thể nói dối hoặc không tuân theo các quy tắc ra quyết định - được gọi là người đã cố gắng phối hợp tấn công. tại Anthony Stevens.
Hãy xem xét trường hợp của chủ sở hữu đồng tiền điện tử Alice, người phải lựa chọn giữa việc mua món kem ngon từ Bob và trả hết nợ cho Carol. Có lẽ Alice muốn trả cả hai cùng một lúc bằng cách tiêu dùng gian lận cùng một đồng xu. Để làm được điều này, cô ấy phải thuyết phục máy tính của Bob rằng đồng xu đó chưa bao giờ được trả cho Carol và thuyết phục máy tính của Carol rằng đồng xu đó chưa bao giờ được trả cho Bob. Hệ thống thỏa thuận Byzantine khiến điều này gần như không thể thực hiện được bằng cách sử dụng một hình thức nguyên tắc đa số gọi là số đại biểu. Một nút trong mạng như vậy từ chối chuyển sang một phiên bản lịch sử cụ thể cho đến khi nó thấy rằng có đủ số lượng ngang hàng - số đại biểu - đồng ý với quá trình chuyển đổi như vậy. Một khi điều này xảy ra, họ sẽ thành lập một khối bỏ phiếu đủ lớn để buộc các nút mạng còn lại đồng ý với quyết định của họ. Alice có thể buộc một số nút nói dối thay mặt cô ấy, nhưng nếu mạng đủ lớn, nỗ lực của cô ấy sẽ bị áp đảo bởi số phiếu bầu của các nút trung thực.
Cần bao nhiêu nút cho số đại biểu? Tối thiểu là đa số, hay đúng hơn là đa số đủ điều kiện để chống lại sai sót và gian lận. Nhưng để đếm đa số, bạn cần biết tổng số người tham gia. Tại văn phòng Interstellar hoặc tại các cuộc bầu cử cấp quận, những con số này rất dễ tìm ra. Nhưng nếu nhóm của bạn là một mạng được xác định lỏng lẻo trong đó các nút có thể vào và ra theo ý muốn mà không cần sự chấp thuận của trung tâm, thì bạn cần liên bang một hệ thống thỏa thuận Byzantine có khả năng xác định số đại biểu không phải từ danh sách các nút được xác định trước mà một cách linh hoạt, từ ảnh chụp nhanh các nút luôn thay đổi và chắc chắn không đầy đủ tại một thời điểm nhất định.
Có vẻ như không thể tạo ra số đại biểu từ góc độ của một nút duy nhất trong một mạng lưới rộng lớn, nhưng điều đó là có thể. Số đại biểu như vậy thậm chí có thể đảm bảo kết quả của việc bỏ phiếu phi tập trung. Sách trắng của SCP chỉ ra cách thực hiện việc này bằng cách sử dụng quy trình được gọi là bởi cuộc bỏ phiếu liên bang.
Vì thiếu kiên nhẫn
Phần còn lại của bài viết mô tả chi tiết hơn về biểu quyết liên kết và giao thức đồng thuận của Stellar. Nếu bạn không quan tâm đến chi tiết, đây là tổng quan chung về quy trình.
- Các nút tiến hành các vòng bỏ phiếu liên bang về “những người được đề cử”. Vòng bỏ phiếu liên bang có nghĩa là:
- Nút bỏ phiếu cho một số tuyên bố, ví dụ: “Tôi đề xuất giá trị của V”;
- Nút lắng nghe giọng nói của các nút ngang hàng cho đến khi tìm thấy giọng nói có thể "nhận";
- Nút này tìm kiếm "số đại biểu" cho xác nhận này. Số đại biểu "xác nhận" người được đề cử.
- Khi một nút có thể xác nhận một hoặc nhiều người được đề cử, nó sẽ cố gắng "chuẩn bị" "lá phiếu" thông qua nhiều vòng bỏ phiếu liên kết.
- Khi một nút có thể xác minh lá phiếu đã sẵn sàng, nó sẽ cố gắng thực hiện lá phiếu đó thông qua nhiều vòng bỏ phiếu liên kết hơn nữa.
- Khi một nút có thể xác nhận cam kết của một lá phiếu, nó có thể "ngoại hóa" giá trị của lá phiếu đó bằng cách sử dụng nó làm kết quả đồng thuận.
Các bước này bao gồm nhiều vòng bỏ phiếu liên kết, tạo thành một vòng SCP. Chúng ta hãy xem xét kỹ hơn những gì xảy ra ở mỗi bước.
Bỏ phiếu liên bang
Bỏ phiếu liên kết là một thủ tục để xác định xem mạng có thể đồng ý với một đề xuất hay không. Trong vòng biểu quyết, mỗi nút phải chọn một trong nhiều giá trị có thể có. Nó không thể làm điều này trừ khi tin chắc rằng các nút khác trong mạng sẽ không chọn kết quả khác. Để đảm bảo điều này, các nút trao đổi một loạt tin nhắn qua lại để mọi người đã xác nhậnĐó túc số điểm giao mất giống nhau quyết định. Phần còn lại của phần này giải thích các thuật ngữ trong câu này và toàn bộ quy trình diễn ra như thế nào.
Số đại biểu và lát đại biểu
Hãy bắt đầu bằng việc xác định số đại biểu. Như chúng ta đã thảo luận ở trên, trong một mạng lưới phi tập trung với tư cách thành viên năng động, không thể biết trước số lượng nút và do đó cần bao nhiêu nút cho đa số. Bỏ phiếu liên bang giải quyết vấn đề này bằng cách đưa ra một ý tưởng mới cắt giảm đại biểu (lát đại biểu): Một nhóm nhỏ các đồng nghiệp mà một nút tin cậy để truyền đạt thông tin trạng thái biểu quyết đến phần còn lại của mạng. Mỗi nút xác định phần đại biểu riêng của mình (trong đó nó trở thành thành viên trên thực tế).
Việc hình thành số đại biểu bắt đầu bằng việc cắt giảm số đại biểu. Đối với mỗi nút, các nút cắt của nó được thêm vào. Sau đó, các thuật ngữ lát cắt được thêm vào những nút này và như thế. Khi bạn tiếp tục, ngày càng có nhiều nút mà bạn không thể thêm vì chúng đã được đưa vào lát cắt. Khi không còn nút mới nào để thêm, quá trình sẽ dừng: chúng tôi đã hình thành số đại biểu bằng cách “đóng bắc cầu” của lát đại biểu của nút ban đầu.
Để tìm số đại biểu từ một nút nhất định...
... thêm các thành viên vào slice của nó...
...sau đó chúng tôi thêm các thành viên lát cắt của các nút này.
Chúng tôi tiếp tục cho đến khi không còn nút nào để thêm.
Không còn nút nào để thêm. Đây là một số đại biểu.
Trong thực tế, mỗi nút có thể xuất hiện ở nhiều lát cắt. Để tạo thành một đại biểu, chỉ chọn một trong các lát và thêm thành viên; sau đó chọn bất kỳ lát cắt nào cho từng thành viên và thêm thành viên nó cắt và vân vân. Điều này có nghĩa là mỗi nút là thành viên của nhiều số đại biểu có thể có.
Chỉ chọn một lát đại biểu ở mỗi bước.
Một số đại biểu có thể có. Hoặc một giải pháp thay thế...
...chọn các lát khác...
…(khi có thể)…
... tạo ra một đại biểu khác.
Làm thế nào một nút biết được các nút khác đang ở trong lát cắt nào? Tương tự như các thông tin khác về các nút khác: từ các đường truyền mà mỗi nút phát tới mạng khi trạng thái biểu quyết của nó thay đổi. Mỗi chương trình phát sóng bao gồm thông tin về các lát cắt của nút gửi. Sách trắng của SCP không chỉ định cơ chế giao tiếp. Việc triển khai thường sử dụng để đảm bảo phát sóng các tin nhắn trên toàn mạng.
Hãy nhớ lại rằng trong hệ thống thỏa thuận Byzantine phi liên bang, số đại biểu được xác định là đa số của tất cả các nút. Hệ thống thỏa thuận Byzantine được thiết kế dựa trên quan điểm của câu hỏi: hệ thống có thể dung thứ cho bao nhiêu nút không trung thực? Trong một hệ thống gồm N nút được thiết kế để tồn tại trong f thất bại, một nút sẽ có thể đạt được tiến bộ bằng cách nhận được phản hồi từ N-f nút ngang hàng vì f trong số chúng có thể bị hỏng. Nhưng sau khi nhận được phản hồi từ N−f ngang hàng, chúng ta có thể giả sử rằng tất cả f ngang hàng (từ đó nút không nhận được phản hồi) thực sự là trung thực. Do đó, f trong số N−f ngang hàng (từ đó nhận được phản hồi) là độc hại. Để các nút đạt được sự đồng thuận giống nhau, phần lớn các nút còn lại phải trung thực, nghĩa là chúng ta cần N−f lớn hơn 2f hoặc N > 3f. Vì vậy, thông thường một hệ thống được thiết kế để tồn tại trong f thất bại sẽ có tổng cộng N=3f+1 nút và kích thước đại biểu là 2f+1. Khi một đề xuất vượt qua ngưỡng đại biểu, phần còn lại của mạng tin chắc rằng mọi đề xuất cạnh tranh sẽ thất bại. Đây là cách mạng hội tụ đến kết quả.
Nhưng trong hệ thống thỏa thuận Byzantine liên bang, không những không thể có đa số (vì không ai biết tổng quy mô của mạng lưới), mà khái niệm đa số cũng hoàn toàn vô dụng! Nếu tư cách thành viên trong hệ thống được mở thì ai đó có thể giành được đa số chỉ bằng cách thực hiện cái gọi là tấn công Sybil: liên tục tham gia mạng qua nhiều nút. Vậy tại sao việc đóng lát chuyển tiếp có thể được gọi là số đại biểuvà làm thế nào nó có thể loại bỏ các đề xuất cạnh tranh?
Về mặt kỹ thuật, không thể nào! Hãy tưởng tượng một mạng gồm sáu nút, trong đó hai bộ ba được phân lập trong các lát đại biểu của nhau. Nhóm con đầu tiên có thể đưa ra quyết định mà nhóm thứ hai sẽ không bao giờ nghe được và ngược lại. Không có cách nào để mạng này đạt được sự đồng thuận (ngoại trừ tình cờ).
Do đó, SCP yêu cầu rằng để bỏ phiếu liên bang (và để áp dụng các định lý quan trọng của bài báo), mạng phải có một thuộc tính được gọi là giao điểm của số đại biểu. Trong mạng có thuộc tính này, bất kỳ hai đại biểu nào có thể được xây dựng luôn chồng lên nhau ở ít nhất một nút. Để xác định tâm lý phổ biến của mạng, điều này cũng tốt như có được đa số. Theo trực giác, điều này có nghĩa là nếu bất kỳ số đại biểu nào đồng ý với tuyên bố X thì không có số đại biểu nào khác có thể đồng ý với bất kỳ điều gì khác, bởi vì nó nhất thiết sẽ bao gồm một số nút từ số đại biểu đầu tiên đã bỏ phiếu cho X.
Nếu có sự giao nhau của số đại biểu trong mạng...
...sau đó bạn có thể xây dựng hai số đại biểu bất kỳ...
...sẽ luôn cắt nhau.
(Tất nhiên, các nút chồng chéo có thể trở thành nói dối Byzantine hoặc nói cách khác là xấu. Trong trường hợp này, giao điểm đại biểu không giúp mạng đồng ý chút nào. Vì lý do này, nhiều kết quả trong sách trắng của SCP dựa trên các giả định rõ ràng, chẳng hạn như những gì còn lại trong việc vượt qua đại biểu mạng ngay cả sau khi loại bỏ các nút xấu. Để đơn giản, hãy để lại những giả định này ngầm trong phần còn lại của bài viết).
Có vẻ như không hợp lý khi mong đợi rằng có thể vượt qua số đại biểu đáng tin cậy trong một mạng lưới các nút độc lập. Nhưng có hai lý do giải thích tại sao lại như vậy.
Lý do đầu tiên là sự tồn tại của Internet. Internet là một ví dụ hoàn hảo về một mạng lưới các nút độc lập với số đại biểu giao nhau. Hầu hết các nút trên Internet chỉ kết nối với một số nút cục bộ khác, nhưng những nhóm nhỏ này chồng lên nhau đủ để có thể truy cập mọi nút từ mọi nút khác dọc theo một số tuyến đường.
Lý do thứ hai dành riêng cho mạng thanh toán Stellar (cách sử dụng SCP phổ biến nhất). Mọi tài sản trên mạng Stellar đều có một nhà phát hành và nguyên tắc của Stellar yêu cầu mỗi nhà phát hành chỉ định một hoặc nhiều nút trên mạng để xử lý các yêu cầu đổi quà. Lợi ích tốt nhất của bạn là trực tiếp hoặc gián tiếp đưa các nút này vào các phần đại biểu cho từng nội dung mà bạn quan tâm. Số đại biểu cho tất cả các nút quan tâm đến một nội dung nhất định sau đó sẽ trùng lặp ít nhất tại các nút quy đổi đó. Các nút quan tâm đến nhiều tài sản sẽ bao gồm tất cả các nút mua lại của các tổ chức phát hành tương ứng trong các phần đại biểu của họ và họ sẽ tìm cách gộp tất cả các tài sản lại với nhau. Ngoài ra, bất kỳ tài sản nào không được liên kết theo cách này với những tài sản khác trên mạng và không nên kết nối - điều này được thiết kế sao cho không có sự chồng chéo đại biểu cho mạng này (ví dụ: các ngân hàng từ khu vực đồng đô la đôi khi muốn giao dịch với các ngân hàng từ khu vực đồng euro và các ngân hàng từ khu vực peso, vì vậy họ ở trên cùng một mạng, nhưng không có trong số họ quan tâm đến mạng lưới trẻ em bán thẻ bóng chày riêng biệt).
Tất nhiên, ожидание vượt qua số đại biểu không bảo đảm. Các hệ thống thỏa thuận Byzantine khác có phần lớn tính phức tạp của chúng là do việc đảm bảo số đại biểu. Một cải tiến quan trọng của SCP là nó loại bỏ trách nhiệm tạo ra số đại biểu khỏi chính thuật toán đồng thuận và đưa nó lên cấp độ ứng dụng. Do đó, mặc dù việc bỏ phiếu liên bang là đủ chung để bỏ phiếu về bất kỳ vấn đề nào, nhưng độ tin cậy của nó thực sự phụ thuộc rất nhiều vào ý nghĩa rộng hơn của những ý nghĩa này. Một số cách sử dụng giả định có thể không có lợi cho việc tạo ra các mạng được kết nối tốt như những cách sử dụng khác.
Biểu quyết, chấp nhận và xác nhận
Trong vòng biểu quyết liên kết, một nút tùy ý bắt đầu biểu quyết cho một giá trị V nào đó. Điều này có nghĩa là phát một thông báo tới mạng: “Tôi là nút N, phần đại biểu của tôi là Q và tôi đang bỏ phiếu cho V”. Khi một nút bỏ phiếu theo cách này, nó hứa rằng nó chưa bao giờ bỏ phiếu chống lại V và sẽ không bao giờ như vậy.
Trong các chương trình phát sóng ngang hàng, mỗi nút sẽ xem các nút khác bỏ phiếu như thế nào. Khi một nút đã thu thập đủ các thông báo này, nó có thể theo dõi các lát đại biểu và cố gắng tìm ra các đại biểu. Nếu anh ta thấy một số đại biểu ngang hàng cũng bỏ phiếu cho V, anh ta có thể tiến hành nhận con nuôi V và phát thông báo mới này lên mạng: “Tôi là nút N, số đại biểu của tôi là Q và tôi chấp nhận V.” Sự chấp nhận mang lại sự đảm bảo mạnh mẽ hơn so với việc bỏ phiếu đơn giản. Khi một nút bỏ phiếu cho V, nó không bao giờ có thể bỏ phiếu cho các lựa chọn khác. Nhưng nếu một nút chấp nhận V thì sẽ không có nút nào trên Mạng chấp nhận tùy chọn kia (Định lý 8 trong sách trắng SCP chứng minh điều này).
Tất nhiên, có khả năng cao là sẽ không ngay lập tức có đủ số nút đồng ý với V. Các nút khác có thể bỏ phiếu cho các giá trị khác. Nhưng có một cách khác để nút chuyển từ bỏ phiếu đơn giản sang chấp nhận. N có thể chấp nhận một giá trị khác cho W, ngay cả khi anh ta không bỏ phiếu cho nó và ngay cả khi anh ta không thấy số đại biểu cho nó. Để quyết định thay đổi phiếu bầu của bạn, chỉ cần xem bộ chặn các nút đã chấp nhận W. Một tập hợp chặn là một nút từ mỗi lát cắt đại biểu N. Như tên cho thấy, nó có thể khối bất kỳ ý nghĩa nào khác. Nếu tất cả các nút trong một tập hợp như vậy chấp nhận W, thì (theo Định lý 8) sẽ không bao giờ có thể hình thành một đại biểu nhận một giá trị khác, và do đó N cũng an toàn khi chấp nhận W.
Nút N với ba lát đại biểu.
BDF là tập chặn cho N: nó bao gồm một nút từ mỗi lát của N.
BE cũng là tập chặn cho N vì E xuất hiện trong hai lát của N.
Nhưng bộ chặn không phải là số đại biểu. Sẽ là quá dễ dàng để lừa nút N chấp nhận giá trị mong muốn nếu việc hack chỉ một nút trong mỗi lát của N là đủ. Do đó, việc chấp nhận giá trị không phải là kết thúc của việc bỏ phiếu. Thay vào đó, N phải xác nhận giá trị, nghĩa là xem số lượng nút chấp nhận nó. Nếu nó đi xa đến mức đó, như sách trắng của SCP đã chứng minh (trong Định lý 11), phần còn lại của mạng cuối cùng cũng sẽ xác nhận giá trị tương tự, do đó N sẽ kết thúc cuộc bỏ phiếu liên kết với một giá trị nhất định.
Bỏ phiếu liên bang.
Quá trình bỏ phiếu, chấp nhận và xác nhận tạo thành một vòng bỏ phiếu liên kết đầy đủ. Giao thức đồng thuận Stellar kết hợp nhiều vòng này để tạo ra một hệ thống đồng thuận hoàn chỉnh.
Giao thức đồng thuận Stellar
Hai thuộc tính quan trọng nhất của hệ thống đồng thuận là - an toàn и khả năng sống sót. Thuật toán đồng thuận là "an toàn" nếu nó không bao giờ có thể đưa ra các kết quả khác nhau cho những người tham gia khác nhau (bản sao lịch sử của Bob sẽ không bao giờ mâu thuẫn với Carol). “Khả năng sống được” có nghĩa là thuật toán sẽ luôn cho ra một kết quả, tức là sẽ không bị mắc kẹt.
Thủ tục bỏ phiếu liên bang được mô tả an toàn theo nghĩa là nếu một nút xác nhận giá trị của V thì sẽ không có nút nào khác xác nhận giá trị kia. Nhưng “sẽ không xác nhận ý nghĩa khác” không có nghĩa là nó nhất thiết sẽ xác nhận điều gì đó. Người tham gia có thể bỏ phiếu cho rất nhiều giá trị khác nhau mà không có giá trị nào đạt đến ngưỡng chấp nhận. Điều này có nghĩa là trong cuộc bỏ phiếu liên bang không có khả năng sống sót.
Giao thức đồng thuận của Stellar sử dụng bỏ phiếu liên kết theo cách đảm bảo cả tính bảo mật và khả năng tồn tại. (Sự đảm bảo về tính bảo mật và khả năng sống sót của SCP có một giới hạn về mặt lý thuyết. Thiết kế chọn một sự đảm bảo an ninh rất mạnh, hy sinh một khoản giảm thiểu nhỏ về khả năng sống sót, nhưng nếu có đủ thời gian, rất có thể sẽ đạt được sự đồng thuận.) Tóm lại, ý tưởng là có nhiều phiếu bầu liên kết trên nhiều giá trị cho đến khi một trong số chúng vượt qua tất cả các giai đoạn bỏ phiếu SCP được mô tả bên dưới.
Các giá trị mà SCP tìm kiếm sự đồng thuận có thể là lịch sử giao dịch hoặc đơn đặt hàng bữa trưa hoặc thứ gì khác, nhưng điều quan trọng cần lưu ý là đây không phải là những giá trị được chấp nhận hoặc xác nhận. Thay vào đó, việc bỏ phiếu liên bang diễn ra theo tuyên bố về những giá trị này.
Vòng bỏ phiếu liên bang đầu tiên diễn ra vào ngày giai đoạn đề cử (giai đoạn đề cử), trên một tập hợp các tuyên bố như “Tôi đề cử V,” có lẽ cho nhiều giá trị khác nhau của V. Mục đích của việc đề cử là tìm một hoặc nhiều tuyên bố trải qua quá trình chấp nhận và xác nhận.
Sau khi tìm thấy các ứng cử viên có thể xác minh được, SCP chuyển sang giai đoạn bỏ phiếu, trong đó mục tiêu là tìm ra một ứng cử viên nhất định. bản tin (nghĩa là vùng chứa giá trị được đề xuất) và đại biểu có thể khai báo làm cho nó (cam kết). Nếu số đại biểu cam kết bỏ phiếu, giá trị của nó được chấp nhận là sự đồng thuận. Nhưng trước khi một nút có thể bỏ phiếu cho một cam kết bỏ phiếu, trước tiên nó phải xác nhận sự hủy bỏ tất cả các lá phiếu có giá trị đếm thấp hơn. Các bước này—hủy bỏ các lá phiếu để tìm một lá phiếu có thể được cam kết—bao gồm nhiều vòng bỏ phiếu liên bang đối với nhiều yêu cầu bỏ phiếu.
Các phần sau mô tả chi tiết hơn về đề cử và bỏ phiếu.
Sự đề cử
Khi bắt đầu giai đoạn đề cử, mỗi nút có thể tự động chọn một giá trị cho V và bỏ phiếu cho câu lệnh “Tôi đề cử V”. Mục tiêu ở giai đoạn này là xác nhận việc đề cử có giá trị nào đó thông qua cuộc bỏ phiếu liên đoàn.
Có lẽ đã có đủ nút bỏ phiếu cho các đề xuất đủ khác nhau để không đề cử nào có thể đạt đến ngưỡng chấp nhận. Do đó, ngoài việc phát sóng phiếu đề cử của riêng mình, các nút còn “phản ánh” đề cử của các đồng nghiệp của họ. Tiếng vọng có nghĩa là nếu một nút bỏ phiếu cho đề cử V, nhưng nhìn thấy tin nhắn từ một nút lân cận bỏ phiếu cho đề cử W, thì nút đó sẽ bỏ phiếu cho cả V và W. (Không phải tất cả các phiếu bầu ngang hàng đều được lặp lại trong quá trình đề cử vì điều này có thể dẫn đến sự bùng nổ của đề cử khác nhau. SCP bao gồm một cơ chế để điều chỉnh các phiếu bầu này. Tóm lại, có một công thức để xác định "mức độ ưu tiên" của một nút ngang hàng theo quan điểm của nút và chỉ phiếu bầu của các nút có mức độ ưu tiên cao mới được phản ánh. Đề cử càng dài lấy, ngưỡng càng thấp, do đó nút sẽ mở rộng tập hợp các ngang hàng có phiếu bầu mà nó sẽ phản ánh. Công thức ưu tiên bao gồm số vị trí là một trong các đầu vào của nó, do đó, một ngang hàng có mức độ ưu tiên cao cho một vị trí có thể là một ngang hàng có mức độ ưu tiên thấp cho một vị trí. khác và ngược lại).
Về mặt khái niệm, việc đề cử là song song, cả V và W đều là các phiếu bầu liên bang riêng biệt, mỗi phiếu đều có khả năng đạt được sự chấp nhận hoặc xác nhận. Trong thực tế, các thông điệp giao thức SCP gói các phiếu bầu riêng lẻ này lại với nhau.
Mặc dù việc bỏ phiếu cho sự đề cử của V là một lời hứa sẽ không bao giờ bỏ phiếu chống lại sự đề cử của V, nhưng ở cấp độ ứng dụng - trong trường hợp này là SCP - nó được xác định "chống lại" nghĩa là gì. SCP không nhìn thấy tuyên bố mâu thuẫn với phiếu bầu "Tôi đề cử X", tức là không có thông báo "Tôi chống lại việc đề cử X", do đó nút có thể bỏ phiếu để đề cử bất kỳ giá trị nào. Nhiều đề cử trong số này sẽ chẳng đi đến đâu, nhưng cuối cùng nút sẽ có thể chấp nhận hoặc xác nhận một hoặc nhiều giá trị. Sau khi một người được đề cử được xác nhận, anh ta sẽ trở thành ứng viên.
Đề cử SCP bằng cách sử dụng biểu quyết liên đoàn. Có thể có nhiều giá trị “B” do các nút ngang hàng đưa ra và được nút “phản ánh”.
Đề cử có thể dẫn đến nhiều ứng cử viên được xác nhận. Do đó, SCP yêu cầu lớp ứng dụng cung cấp một số phương pháp kết hợp các ứng cử viên thành một hỗn hợp (tổng hợp). Phương pháp tham gia có thể là bất cứ điều gì. Điều chính là nếu phương pháp này mang tính xác định thì mỗi nút sẽ kết hợp các ứng cử viên giống nhau. Trong hệ thống bỏ phiếu ăn trưa, "thống nhất" có thể chỉ đơn giản là từ chối một trong hai ứng cử viên. (Nhưng theo cách xác định: mỗi nút phải chọn cùng một giá trị để đặt lại. Ví dụ: lựa chọn trước đó theo thứ tự bảng chữ cái). Trong mạng thanh toán Stellar, nơi lịch sử giao dịch được bình chọn, việc hợp nhất hai đề cử được đề xuất liên quan đến việc hợp nhất các giao dịch mà chúng chứa và dấu thời gian mới nhất trong số hai dấu thời gian của chúng.
Sách trắng SCP chứng minh (Định lý 12) rằng vào cuối giai đoạn mở rộng, mạng cuối cùng sẽ hội tụ thành một tổ hợp duy nhất. Nhưng có một vấn đề: bỏ phiếu liên kết là một giao thức không đồng bộ (như SCP). Nói cách khác, các nút không được phối hợp theo thời gian mà chỉ theo các tin nhắn chúng gửi. Từ quan điểm của nút, không rõ khi nào đã kết thúc giai đoạn mở rộng. Và mặc dù tất cả các nút cuối cùng sẽ đến cùng một tổ hợp, nhưng chúng có thể đi theo các tuyến đường khác nhau trên đường đi, tạo ra các ứng cử viên tổng hợp khác nhau trên đường đi và không bao giờ có thể biết nút nào là nút cuối cùng.
Nhưng nó bình thường. Đề cử chỉ là sự chuẩn bị. Điều chính là hạn chế số lượng ứng viên để đạt được sự đồng thuận, điều này xảy ra trong quá trình bỏ phiếu (bỏ phiếu).
Đang chạy
Bản tin là một cặp đôi , trong đó bộ đếm là số nguyên bắt đầu từ 1 và giá trị là ứng cử viên từ giai đoạn đề cử. Đây có thể là ứng cử viên của chính nút hoặc ứng cử viên của nút lân cận được nút đó chấp nhận. Nói một cách đại khái, một cuộc bỏ phiếu bao gồm các nỗ lực lặp đi lặp lại để buộc mạng đạt được sự đồng thuận về một số ứng cử viên trên một số lá phiếu bằng cách nắm giữ nhiều phiếu bầu liên bang tiềm năng trên các báo cáo lá phiếu. Máy đếm phiếu sẽ theo dõi những lần thử được thực hiện và những lá phiếu có số phiếu cao hơn sẽ được ưu tiên hơn những lá phiếu có số phiếu thấp hơn. Nếu bản tin bị kẹt, một cuộc bỏ phiếu mới bắt đầu, bây giờ là trên lá phiếu .
Quan trọng để phân biệt giá trị (ví dụ: bữa trưa nên gọi món gì: pizza hoặc salad), bản tin (cặp phản giá trị) và báo cáo về lá phiếu. Vòng SCP bao gồm một số vòng bỏ phiếu liên bang, đặc biệt là các tuyên bố sau:
- "Tôi sẵn sàng bỏ phiếu B" và
- “Tôi công bố cam kết của lá phiếu B”
Từ quan điểm của một nút nhất định, sự đồng thuận đạt được khi nó tìm thấy lá phiếu B mà nó có thể xác nhận (nghĩa là tìm số đại biểu chấp nhận) tuyên bố "Tôi cam kết lá phiếu B." Từ thời điểm này trở đi, việc hành động theo giá trị được chỉ định trong B là an toàn - ví dụ: đặt đơn hàng này cho bữa trưa. Nó được gọi là ngoại hiện ý nghĩa. Sau khi việc chấp nhận lá phiếu được xác nhận, một nút có thể chắc chắn rằng bất kỳ nút nào khác đã đưa ra bên ngoài cùng một giá trị hoặc sẽ làm như vậy trong tương lai.
Mặc dù về mặt khái niệm, nhiều cuộc bỏ phiếu liên bang được tiến hành dựa trên các yêu cầu cho nhiều lá phiếu khác nhau, nhưng chúng không trao đổi nhiều tin nhắn vì mỗi tin nhắn bao gồm một số lá phiếu. Do đó, một thông điệp sẽ thúc đẩy tình trạng có nhiều phiếu bầu liên bang cùng một lúc, chẳng hạn: “Tôi chấp nhận các lá phiếu cam kết từ trước "
Các thuật ngữ “chuẩn bị” và “cam kết” có nghĩa là gì?
Một nút bỏ phiếu để cam kết một lá phiếu khi tin chắc rằng các nút khác sẽ không cam kết các lá phiếu có giá trị khác. Thuyết phục đây là mục đích của việc chuẩn bị hồ sơ. Một cuộc bỏ phiếu có nội dung "Tôi sẵn sàng bỏ phiếu B" là lời hứa không bao giờ bỏ phiếu nhỏ hơn B, tức là với số lượng nhỏ hơn (SCP yêu cầu các giá trị trong lá phiếu phải theo một thứ tự nhất định. ít hơn , nếu N1
Tại sao “Tôi sẵn sàng bỏ phiếu B” có nghĩa là “Tôi hứa sẽ không bao giờ bỏ phiếu nhỏ hơn B”? Bởi vì SCP định nghĩa hủy bỏ là trái ngược với cam kết. Một cuộc bỏ phiếu để chuẩn bị lá phiếu cũng bao gồm một cuộc bỏ phiếu để loại bỏ một số lá phiếu khác, và như chúng ta đã thảo luận trước đó, bỏ phiếu cho một điều là lời hứa không bao giờ bỏ phiếu chống lại nó.
Trước khi phát đi một cam kết, nút đầu tiên phải tìm một bản tin mà nó có thể xác nhận là đã chuẩn bị. Nói cách khác, nó thực hiện một cuộc bỏ phiếu liên bang về chủ đề “Tôi sẵn sàng bỏ phiếu B,” có thể trên nhiều lá phiếu khác nhau, cho đến khi nó tìm thấy một lá phiếu chấp nhận số đại biểu.
Phiếu lấy từ đâu để chuẩn bị bầu cử? Đầu tiên, nút phát đi thông báo chuẩn bị bỏ phiếu cho <1,C>, trong đó C là ứng cử viên tổng hợp được tạo ra ở giai đoạn đề cử. Tuy nhiên, ngay cả sau khi việc chuẩn bị bỏ phiếu bắt đầu, việc đề cử có thể dẫn đến việc có thêm các ứng cử viên dường như trở thành lá phiếu mới. Trong khi đó, các đồng nghiệp có thể có các ứng cử viên khác nhau và họ có thể tạo thành một bộ chặn chấp nhận "Tôi đã sẵn sàng thực hiện lá phiếu B2", điều này cũng sẽ thuyết phục nút chấp nhận nó. Cuối cùng, có một cơ chế hết thời gian chờ để tạo ra các vòng bỏ phiếu liên bang mới cho các lá phiếu mới có số phiếu cao hơn nếu các lá phiếu hiện tại bị kẹt.
Ngay sau khi nút tìm thấy lá phiếu B mà nó có thể xác nhận là đã chuẩn bị, nó sẽ phát đi một thông báo mới “Cam kết lá phiếu B”. Cuộc bỏ phiếu này cho các đồng nghiệp biết rằng nút sẽ không bao giờ từ bỏ B. Trên thực tế, nếu B là một lá phiếu , sau đó “Cam kết bỏ phiếu " nghĩa là sự đồng ý bỏ phiếu vô điều kiện về tính sẵn sàng của mỗi lá phiếu từ đến <∞, s>. Giá trị bổ sung này giúp các đồng nghiệp khác bắt kịp với đồng nghiệp cam kết nếu họ vẫn đang ở giai đoạn đầu của giao thức.
Ở giai đoạn này, cần nhấn mạnh một lần nữa rằng đây là các giao thức không đồng bộ. Chỉ vì một nút gửi phiếu tán thành cho một cam kết không có nghĩa là các nút ngang hàng của nó cũng làm như vậy. Một số người trong số họ có thể vẫn đang bỏ phiếu cho các tuyên bố để chuẩn bị bỏ phiếu, những người khác có thể đã thể hiện ý nghĩa đó ra bên ngoài. SCP giải thích cách một nút nên xử lý từng loại tin nhắn ngang hàng bất kể giai đoạn của nó.
Nếu thông báo "Tôi đã thông báo cam kết » không thể nhận được hoặc xác nhận, nghĩa là xác suất tin nhắn được chấp nhận hoặc xác nhận hoặc - hoặc, trong mọi trường hợp, bất kỳ lá phiếu nào có giá trị C chứ không phải bất kỳ giá trị nào khác, vì nút đã hứa không bao giờ hủy . Vào thời điểm một nút phát đi phiếu bầu cho một cam kết, nó sẽ là C hoặc không có gì, tùy thuộc vào mức độ đồng thuận. Tuy nhiên, điều này vẫn chưa đủ để nút xuất hiện bên ngoài C. Một số nút ngang hàng Byzantine (được cấu thành ít hơn số đại biểu, dựa trên các giả định bảo mật của chúng tôi) có thể nói dối nút. Chấp nhận và sau đó xác nhận một số phiếu bầu (hoặc phạm vi phiếu bầu) là điều mang lại cho nút sự tự tin để cuối cùng xuất hiện C.
SCP bỏ phiếu thông qua bỏ phiếu liên bang. Không hiển thị: Đồng hồ bấm giờ có thể tắt bất kỳ lúc nào, làm tăng số lượng phiếu bầu (và có thể tạo ra một danh sách tổng hợp mới gồm các ứng cử viên được đề cử bổ sung).
Và đó là tất cả! Khi mạng đã đạt được sự đồng thuận, nó sẵn sàng thực hiện lại điều đó. Trên mạng thanh toán Stellar, điều này xảy ra khoảng 5 giây một lần: một kỳ tích đòi hỏi cả tính bảo mật và khả năng sống sót được đảm bảo bởi SCP.
SCP có thể đạt được điều này bằng cách dựa vào nhiều vòng bỏ phiếu liên đoàn. Việc bỏ phiếu liên kết được thực hiện nhờ khái niệm về các lát cắt đại biểu: tập hợp các đồng nghiệp mà mỗi nút đã quyết định tin tưởng như một phần của đại biểu (chủ quan) của nó. Cấu hình này có nghĩa là có thể đạt được sự đồng thuận ngay cả trong một mạng có tư cách thành viên mở và sự lừa dối kiểu Byzantine.
đọc thêm
- Sách trắng SCP gốc có thể được tìm thấy Và dự thảo các thông số kỹ thuật để thực hiện nó.
- Tác giả ban đầu của giao thức SCP, David Mazier, giải thích nó theo cách đơn giản hóa (nhưng vẫn mang tính kỹ thuật). .
- Bạn có thể ngạc nhiên khi không tìm thấy thuật ngữ “khai thác” hoặc “bằng chứng công việc” trong bài viết này. SCP không sử dụng các phương pháp này, nhưng một số thuật toán đồng thuận khác thì có. Zane Witherspoon đã viết có thể truy cập được .
- một mạng đơn giản đạt được sự đồng thuận trong một vòng SCP đầy đủ.
- Đối với độc giả quan tâm đến việc triển khai SCP: xem , được sử dụng bởi mạng thanh toán Stellar, hoặc , mà tôi đã viết để hiểu rõ hơn về SCP.
Nguồn: www.habr.com