Tác giả gốc:cỗ máy linh hồn; Video hỗ trợ cho bài viết này:https://v.qq.com/x/page/f07704nx4iq.html

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

Luồng thuật toán Casper FFG

Mô tả hình ảnh

quá trình PoW

Những người khai thác màu vàng trong hình trên đột nhiên tăng tính toán của họ và bắt đầu làm những điều tồi tệ. Bắt đầu từ một khối cũ, một chuỗi mới được phân nhánh và tiếp tục khai thác trên đó. Nếu chiều dài của nó vượt quá bên trái, thì chuỗi mới sẽ bị hỏng .Nếu chuỗi cũ có thể được thay thế thành công, khối cũ trước đó sẽ bị thu hồi và tất cả các giao dịch bên trong sẽ bị ghi đè và viết lại.

Trên cơ sở PoW hiện tại, Casper FFG bổ sung một lớp quy trình bỏ phiếu PoS, giúp nâng cao hơn nữa Tính hoàn thiện và về mặt lý thuyết, các khối cũ không thể bị thu hồi. Casper FFG là một thuật toán không xâm lấn. Nó không thay đổi thuật toán Ethereum PoW hiện tại, nhưng bổ sung PoS kiểu BFT trên lớp PoW này. Điều đó có nghĩa là, tất cả các khối đều được đào ra bởi những người khai thác PoW. Quá trình cốt lõi này là bảo quản. Trên cơ sở này, mỗi khi 100 khối được khai thác, các nút xác minh PoS sẽ bỏ phiếu cho khối cuối cùng, sau khi vượt qua 2/3, khối cuối cùng được gọi là điểm kiểm tra (điểm kiểm tra).Không thể hoàn tác bất kỳ điểm kiểm tra nào đã hoàn thành.Tóm lại, cơ chế tạo khối PoW được giữ lại, đồng thời, PoS bỏ phiếu cứ sau 100 khối, điều này giúp tăng cường hơn nữa tính bảo mật (An toàn hoặc Tính cuối cùng) của Ethereum.

Các trường của tin nhắn bình chọn như sau:

Như được hiển thị trong bảng trên, mỗi thông báo biểu quyết chứa 5 trường, s biểu thị hàm băm khối của điểm kiểm tra nguồn, t biểu thị hàm băm khối của điểm kiểm tra đích, h(s) biểu thị chiều cao khối của s, h(t) biểu thị chiều cao khối của t và S đại diện cho chữ ký Trong số 5 trường này, chỉ có 3 trường thực sự cốt lõi, đó là h(s), t, h(t).

Thông báo vote của Casper FFG đã khéo léo kết hợp 2 bước thành 1, về bản chất vẫn tương đương với 2 giai đoạn vote trong pBFT và Tendermint, pre-prepare->prepare, pre-vote -> pre-commit.

Hình dưới đây giải thích lý do tại sao bỏ phiếu cần có hai giai đoạn.

Đồng thời, thông báo bỏ phiếu của Casper FFG có tác dụng tương tự như cơ chế khóa trong Tendermint.

Sau đây là định nghĩa của một số thuật ngữ thường thấy trong thuật toán Casper FFG:

• một miếngsupermajority link, được viết dưới dạng a→b, có nghĩa là nếu hơn 2/3 số thông báo biểu quyết bắt đầu từ điểm kiểm tra a và trỏ đến điểm kiểm tra b, thì có một liên kết đa số giữa a và b. Một liên kết siêu đa số có thể vượt qua một số điểm kiểm tra, nghĩa là, h(b)>h(a)+1 là hợp lệ.

• Hai điểm kiểm tra a và b lẫn nhauxung đột, có nghĩa là a và b nằm trên các nhánh khác nhau, nghĩa là a và b không nằm trên cùng một đường đi.

• Một điểm kiểm tra c sẽ trở thành mộtjustifiedMột điểm kiểm tra cần phải đáp ứng một trong các điều kiện sau, (1) nó là một khối gốc; (2) hoặc có một liên kết siêu đa số trỏ đến nó.

• Một điểm kiểm tra c sẽ trở thành mộtfinalizedĐiểm kiểm tra, nó cần phải được chứng minh và có một liên kết siêu đa số bắt nguồn từ nó, c→c' và c' là điểm kiểm tra của nócon trực tiếp, nghĩa là chiều cao của c' là chiều cao của c tăng thêm 1.

Ví dụ, như thể hiện trong hình dưới đây:

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

Điều kiện hình phạt (SlashCondition)

Nếu Người xác thực vi phạm bất kỳ điều kiện nào trong hai điều kiện sau, họ sẽ bị trừng phạt và tất cả các khoản tiền gửi sẽ bị tịch thu.

1. No double vote: t1==t2. Không thể bỏ phiếu cho hai khối khác nhau ở cùng một độ cao. Điều này tương đối dễ hiểu, ở cùng một độ cao, bỏ phiếu cho hai khối khác nhau là một hành vi đầu cơ điển hình của Nothingat stake, hành vi này sẽ bị trừng phạt.

2. No surround vote.t2 < t1 < s1 < s2 . Ví dụ: trình xác nhận đầu tiên bỏ phiếu, s1 -> t1, sau một vài khối, tiếp tục bỏ phiếu, s2 -> t2, vì chiều cao khối tăng dần theo thời gian, rõ ràng là s2> e1 và lần thứ hai nếu t2< t1,Nó thấp hơn khối mục tiêu của lần bỏ phiếu trước, đây là vấn đề, bởi vì bạn đã bỏ phiếu s1 -> t1 trước đó, có nghĩa là bạn đã nhận ra rằng tất cả các khối giữa s1 và t1 đều đúng, nhưng lần bỏ phiếu thứ hai s2 ->t2, khoảng cách nhỏ hơn s1->t1, được bao phủ hoàn toàn bởi s1->t1, phiếu bầu này liên tục đồng ý khối giữa s2 và t2, như thể bạn đã quên phiếu bầu trước đó. Hành vi quên như vậy cũng sẽ bị phạt.

Hình dưới đây cho thấy một ví dụ về vi phạm bỏ phiếu Nodouble,

Trong quá trình khai thác PoW, việc phân nhánh xảy ra ở cùng độ cao là điều bình thường. Tại thời điểm này, trong số 4 nút xác thực, có 2 nút độc hại đã bỏ phiếu cho cả hai nhánh cùng một lúc, điều này sẽ khiến hai khối mới trở thành hợp lệ. Trong trường hợp này, hai nút độc hại sẽ bị trừng phạt, khoản tiền gửi sẽ bị tiêu diệt và người báo cáo sẽ nhận được phần thưởng (phí tìm kiếm).

Hình dưới đây cho thấy một ví dụ về vi phạm Không bỏ phiếu xung quanh,

Tại một thời điểm nào đó, có hai liên kết siêu đa số, A->B và A->C, vì vậy A trở thành kết thúc và cả B và C đều là các khối hợp lý. Trong trường hợp này, điều đó có nghĩa là hơn 1/3 số nút xác minh đã bỏ phiếu cho B và C cùng một lúc, điều này hợp pháp và không vi phạm quy tắc bỏ phiếu không kép hoặc quy tắc bỏ phiếu vòng quanh.

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

Bằng chứng về sự an toàn và sự sống hợp lý

Trong phần này, chúng tôi sẽ chứng minh tính An toàn (Finality) và Tính sống động (Liveness) của Casper FFG.

Trước hết, Casper FFG tuyên bố là an toàn có trách nhiệm và tính sống động hợp lý. Có trách nhiệm có nghĩa là các nút của trình xác thực cần phải trả một khoản tiền gửi đáng kể. Với khoản tiền gửi này, có sự tin tưởng ban đầu và có thể được tính vào (có trách nhiệm giải trình).
Sự sống động hợp lý thực ra không có gì mới, nó giống hệt như sự sống động của Bitcoin, nghĩa là khi mạng phân tách (phân vùng), toàn bộ hệ thống vẫn có thể viết các giao dịch mới và tạo khối.

Bằng chứng chi tiết bắt đầu dưới đây.

An toàn có trách nhiệm: Hai điểm kiểm tra (checkpoint) xung đột, am và bn không thể hoàn thành (hoàn thành)

chứng minh:Sử dụng phương pháp phản chứng, giả sử rằng am và bn xung đột với nhau (nghĩa là trên hai nhánh chứ không phải trên cùng một nhánh) và phép toán được hoàn thiện và chúng đều có một khối con chính đáng am+1 và tỷ+1.

Nếu chiều cao m và n của chúng bằng nhau thì phải có 1/3 số nút xác minh bỏ phiếu cho cả hai điểm kiểm tra cùng một lúc. Các nút này vi phạm quy tắc Không bỏ phiếu kép và tất cả tiền đặt cọc sẽ bị hủy, mất 1/3 các nút xác minh, am và bn không thể được hoàn thành.

Nếu độ cao m và n không bằng nhau, đặt n > m(n< m chứng minh quá trình tương tự), đường dẫn từ khối genesis đến bn là genesis→b1→b2→...→bi→bj→...→bn, bi là khối đầu tiên có chiều cao nhỏ hơn hoặc bằng am, tức là i≤m, bj là khối đầu tiên có chiều cao lớn hơn hoặc bằng am+1, tức là j≥m+1. Điều sau đây chứng minh rằng:

• Nếu i==m, 1/3 số nút xác minh vi phạm quy tắc không bỏ phiếu kép và sẽ bị phạt, khiến am và bn không thể hoàn thành;

• Nếu j==m+1, tương tự như trên;

• nếu tôim+1, có nghĩa là có một liên kết siêu đa số bi→bj bao quanh hoàn toàn am->am+1, điều này vi phạm quy tắc bỏ phiếu không bao quanh và 1/3 số nút sẽ bị trừng phạt, khiến cho am và bn không thể thực hiện được Sẽ được hoàn thiện. Một số người có thể hỏi rằng bi và bj có thể không được hoàn thành.Mặc dù vậy, ít nhất genesis→bn bao quanh am->am+1, điều này vẫn vi phạm quy tắc không bao quanh.

Tóm lại, am và bn là không thể cuối cùng trong bất kỳ trường hợp nào, và chứng minh đã hoàn tất.

Sự sống động hợp lý: Miễn là hơn 2/3 số nút của trình xác thực bỏ phiếu sử dụng khối được chứng minh làm điểm bắt đầu, thì một khối hoàn thiện mới luôn có thể được tạo.

Nói một cách đơn giản, nó lấy một khối hợp lý làm điểm bắt đầu và bạn có thể bỏ phiếu cho bất kỳ nút nào cao hơn nó. Ví dụ: có hai khối mới, một khối ở độ cao m và một khối ở độ cao n (bao gồm cả điểm bắt đầu , ba khối phải nằm trên một dòng), thì bạn có thể bỏ phiếu cho một trong hai hoặc thậm chí cả hai mà không vi phạm các quy tắc bỏ phiếu không kép và bỏ phiếu xung quanh. Điều đó có nghĩa là, bạn có thể bỏ qua nhiều khối và ném trực tiếp các khối cao hơn. Khối hợp lý tiếp theo có thể là am hoặc bn, hoặc cả hai (cả hai đều nhận được hơn 2/3 phiếu bầu, tại thời điểm này phải có hơn 1/3 số nút bình chọn cho cả hai) đó là lý do được gọi là hợp lý.

Ngay cả khi mạng bị chia tách, PoW có thể tiếp tục tạo khối ở cả hai bên, nhưng tại thời điểm này, các nút Trình xác thực không còn có thể đạt được 2/3 phiếu bầu trên bất kỳ điểm kiểm tra nào vì một nửa của một bên không thể giao tiếp. được hoàn thiện tiếp tục phát triển. Khi mạng được chia thành hai nửa, nó vẫn có thể hoạt động (Tendermint chỉ có thể đợi vô thời hạn khi mạng được chia) Loại hoạt động mạnh mẽ này có thể là một ý nghĩa khác của hợp lý.

Casper FFG có thể suy ra từ Plausible livenessQuy tắc ForkChoice: Luôn chọn chuỗi dài nhất trên điểm kiểm tra hợp lý với mức cao nhất.Đó là tìm khối hợp lý cao nhất trước, sau đó bắt đầu từ khối này để chọn chuỗi dài nhất. So với việc lựa chọn đơn giản chuỗi dài nhất trong thuật toán PoW, có một điều kiện tiên quyết nữa.

Ví dụ, như hình dưới đây:

Trong hình trên, từ đường cao nhất được hoàn thiện, có hai siêu liên kết trỏ đến hai điểm kiểm tra hợp lý, lúc này mạng bị chia cắt tại một thời điểm nhất định, ví dụ như cáp quang biển bị đứt chia mạng toàn cầu thành hai. Tại thời điểm này, PoW của cả hai bên sẽ tiếp tục tạo khối bình thường, nhưng khi mỗi điểm kiểm tra bỏ phiếu, nó chỉ có thể nhận được tối đa một nửa số phiếu bầu, vì nút xác thực chỉ có một nửa, ngay cả khi 100% đồng ý với điểm kiểm tra mới , nó không thể vượt quá 2/3. Do đó, sau khi chia tách mạng, PoW sẽ tiếp tục phát triển chuỗi, nhưng tất cả các khối mới không thể được hoàn thiện và chứng minh.

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

Bộ trình xác thực động

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

Không có gì trong cuộc tấn công ngăn xếp

Các khối và biểu quyết PoS thuần túy không yêu cầu sức mạnh tính toán và không có chi phí (trong PoW, nếu bạn khai thác trên một chuỗi ngắn, bạn sẽ không được thưởng nếu bạn đào nó và sức mạnh tính toán bị lãng phí và có chi phí ), do đó, khi rẽ nhánh chuỗi khối, các nút xác thực không biết nhánh nào là chính xác. Để nhận được phần thưởng, chiến lược tốt nhất là bỏ phiếu cho từng nhánh. Để trừng phạt loại hành vi này, PoS thường yêu cầu các nút xác minh phải trả tiền đặt cọc trước khi bỏ phiếu.

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

Tấn công tầm xa

Các cuộc tấn công tầm xa đề cập đến ba tình huống sau:

• Trong trường hợp của PoS thuần túy, vì không có chi phí để tạo khối trong PoS thuần túy, nên dễ dàng tạo ra một chuỗi rẽ nhánh dài hơn chuỗi thực.

• Trong trường hợp của PoW, giả sử rằng các nút độc hại có hơn 51% sức mạnh tính toán, chúng cũng có thể tạo ra một chuỗi rẽ nhánh dài hơn chuỗi thực. Loại tình huống này tương đối hiếm, bởi vì có chi phí cho việc sản xuất khối PoW, với sức mạnh tính toán lớn như vậy, tốt hơn hết là khai thác một cách trung thực và nhận được nhiều phần thưởng hơn. Tuy nhiên, nếu một nút độc hại đã có một giao dịch với số lượng lớn từ lâu, được thúc đẩy bởi lợi nhuận, thì nút độc hại đó cũng có động lực để phân nhánh lại và chi tiêu gấp đôi số tiền.Trong trường hợp này, nút độc hại cũng sẽ khởi chạy một tấn công tầm xa.

• Trường hợp thứ ba có thể áp dụng cho PoS và PoW. Nếu một nút đầy đủ mới vừa trực tuyến, nó sẽ tình cờ được kết nối với một số nút độc hại để bắt đầu đồng bộ hóa các khối. Chuỗi vẫn còn dài. Tại thời điểm này, ngay cả khi một nút đầy đủ trung thực là được kết nối muộn hơn, chuỗi được gửi bởi nút đầy đủ sẽ ngắn hơn và sẽ bị nút mới từ chối. Điều đó thật đáng xấu hổ.

Đối với trường hợp thứ nhất và thứ ba, vấn đề về cơ bản là giống nhau, khi nhận được một chuỗi dài hơn, làm thế nào để đánh giá đó là đúng hay sai? Vitalik trong bài viết nàyProof of Stake: How I Learned toLove Weak Subjectivity Giải thích giải pháp, chúng ta vẫn cần giới thiệu một chút kiến ​​​​thức và niềm tin từ thế giới bên ngoài, cái gọi là chủ quan yếu V Chúa tin rằng loại niềm tin yếu này rất dễ đạt được, vì vậy nó không làm suy yếu Sự an toàn của chuỗi khối. Khi một nút mới xuất hiện trực tuyến, nó cần thu thập và tin tưởng những kiến ​​thức sau từ thế giới bên ngoài:

1. Định nghĩa giao thức Cái này dễ xử lý, giao thức của chuỗi khối tồn tại trong mã. Phiên bản mã nào mà nút mới chạy có nghĩa là nút đó tin cậy mã theo mặc định.

2. Khối hợp lệ mới nhất. Khối này không thể quá cũ, nó phải nằm trong số N cuối cùng. N có thể được xác định trước, miễn là nó đủ mới. Ví dụ: đối với Bitcoin, bất kỳ khối nào trong vòng 6 khối cuối cùng được coi là đủ mới Đối với Ethereum, 12 khối cuối cùng là tương đối mới.

Đối với 2, vấn đề là rất lớn.Khi một nút đầy đủ mới trực tuyến, tôi có thể lấy khối hợp lệ mới nhất ở đâu? Kiến thức tin tưởng bổ sung cần được giới thiệu ở đây. Ví dụ: đối với CasperFFG, khi một nút mới trực tuyến, nó chỉ nên tin tưởng nút đầy đủ đã thanh toán tiền đặt cọc và tốt nhất là kết nối nhiều nút để có được khối hoàn thiện mới nhất. Khi bạn nhận được khối cuối cùng mới nhất, bạn có thể yên tâm bắt đầu đồng bộ hóa. Ngay cả khi bạn nhận được một chuỗi dài hơn từ nút độc hại, do giá trị băm của khối của nút độc hại phải khác nhau ở cùng một độ cao, nó có thể được đánh giá rằng đó phải là một chuỗi giả, hãy vứt chuỗi này đi.

Tóm lại, để đối phó với các cuộc tấn công tầm xa, cần phải dựa vào một chút kiến ​​thức từ thế giới bên ngoài để ngăn chặn các cuộc tấn công như vậy.

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

Các Trường Hợp Tai Nạn Lớn (Castastrophic Crashes)

Nếu hơn 1/3 số nút xác minh gặp sự cố cùng lúc hoặc mạng gặp sự cố khiến chúng ngoại tuyến hoặc mạng bị chia tách thì không thể thu thập hơn 2/3 số phiếu bầu khi bỏ phiếu tại thời điểm này thời gian, tức là từ giờ trở đi, không thể tạo một siêu liên kết mới, tức là không thể hoàn thành bất kỳ khối mới nào.

Bài báo giới thiệu một phương pháp gọi là Inactivity leak Bí quyết là làm cho hai mạng con hoạt động độc lập, tiếp tục bỏ phiếu độc lập và hoàn thiện các khối mới.

tóm tắt

tóm tắt

Thuật toán Casper FFG bao gồm 3 phần: 2 điều kiện phạt (slash condition), quy tắc lựa chọn rẽ nhánh (fork choice rule) và tập hợp động các nút xác minh. Casper FFG có thể áp dụng cho bất kỳ thuật toán PoW nào, cải thiện tính bảo mật của thuật toán PoW.

Cơ chế tạo khối của Casper FFG là PoW (cơ chế đề xuất khối dựa trên PoW), trong tương lai cơ chế tạo khối sẽ được thay thế bằng PoS, tức là PoS thuần túy.

Về độ phức tạp của giao tiếp mạng, trong giai đoạn PoW, nó là O(n) và trong giai đoạn bỏ phiếu BFT, nó là O(n2). Nói chung, do ngưỡng vốn, số lượng nút xác minh nhỏ so với toàn bộ nút mạng, do đó, ngay cả khi nó là O(n2), vì n nhỏ nên khối lượng giao tiếp vẫn tương đối nhỏ.

Về khả năng chịu lỗi tối đa, trong giai đoạn PoW, sức mạnh tính toán của các nút độc hại có thể được chấp nhận dưới 50% và trong giai đoạn bỏ phiếu BFT, số tiền mà các nút độc hại yêu cầu ít hơn 1/3. một bản tóm tắt đơn giản và sơ bộ, khả năng chịu lỗi tối đa có thể được coi là 1/3.

Về giả định mạng, nó là đồng bộ trong giai đoạn PoW và không đồng bộ trong giai đoạn bỏ phiếu BFT.Nói chung, giả định mạng là đồng bộ.

Về Tính cuối cùng, nó mang tính Xác suất trong giai đoạn PoW và nó trở thành Tính xác định sau khi bỏ phiếu BFT và nói chung là tính Xác định.

Người giới thiệu

Người giới thiệu

• Casper the Friendly Finality Gadget
  

• EthereumPoS: Casper FFG In Depth - YouTube

• Ethereum PoS Overview: Casper FFG

• Casper FFG with one message type,and simpler fork choice rule

• Ethereum Casper 101

• A Simplified Look at Ethereum’sCasper

• Consensus Compare: Casper vs.Tendermint - Medium

• Proof of Stake: How I Learned toLove Weak Subjectivity