原文：An toàn và lành mạnh - Đi sâu vào bảo mật STARK
Dịch và hiệu đính: "Cộng đồng người Trung Quốc Starknet"
Thông tin nhanh nổi bật
STARK không tương tác có nguồn gốc từ Bằng chứng Oracle Tương tác (IOP), được biên soạn thành một bằng chứng không tương tác trong mô hình oracle ngẫu nhiên.
Bài viết này giải thích các bản cập nhật mới nhất của tài liệu ethSTARK và cung cấp phân tích toàn diện và chi tiết về tính bảo mật của giao thức ethSTARK trong mô hình oracle ngẫu nhiên.
Giải thích chi tiết về bảo mật STARK
Hệ thống chứng minh STARK, hay đối số kiến thức minh bạch có thể mở rộng, là một công cụ mạnh mẽ để đảm bảo tính toàn vẹn trong tính toán: nó cho phép xác minh một cách không đáng tin cậy về tính chính xác của các tính toán được thực hiện trên dữ liệu công cộng. Trong bài viết này, chúng ta sẽ đi sâu vào tính bảo mật được cung cấp bởi các bằng chứng STARK, xác định chúng và khám phá các kỹ thuật để chứng minh tính bảo mật của các sơ đồ.
(Đọc phần 6 của tài liệu ethSTARK (phiên bản 1.2) để biết chi tiết, cũng như công trình độc lập quan trọng và toàn diện về chủ đề này của Block et al.).
Chúng ta đang cố gắng đạt được điều gì với phân tích bảo mật? Chúng tôi muốn ngăn chặn "các cuộc tấn công thành công" vào hệ thống STARK do một tuyên bố sai và bằng chứng STARK được người xác thực STARK chấp nhận để phản hồi lại tuyên bố (sai) đó. Bởi vì việc trình bày sai là nguy hiểm và chúng có thể xảy ra ở mọi quy mô và hình thức nên chúng tôi muốn được an toàn trước tất cả những điều đó. Bất kỳ tuyên bố sai nào, thậm chí tầm thường như 1+1=3, khi được kết hợp với bằng chứng STARK được trình xác nhận STARK chấp nhận, sẽ được coi là một cuộc tấn công thành công vào hệ thống. (Những người có nền tảng về mật mã có thể muốn biết rằng STARK cũng có thể đáp ứng các khái niệm bảo mật mạnh hơn như độ tin cậy của kiến thức, nhưng để đơn giản, bài viết này sẽ tập trung vào các trường hợp đơn giản về độ tin cậy).
Làm cách nào để chúng tôi xác định chính thức tính bảo mật của hệ thống STARK? Chúng tôi xác định điều này bằng cách phân tích "lỗi về độ tin cậy". "Lỗi về độ tin cậy" đo lường đại khái "chi phí" dự kiến mà kẻ tấn công sẽ phải trả để thực hiện một cuộc tấn công thành công (tức là tìm bằng chứng STARK cho một tuyên bố sai được người xác nhận STARK chấp nhận). Về mặt toán học, lỗi độ tin cậy là một hàm (t) có đầu vào là tham số thời gian t, biểu thị thời gian tính toán mà kẻ tấn công sẵn sàng bỏ ra để khởi động một cuộc tấn công và đầu ra là xác suất cuộc tấn công của kẻ tấn công sẽ thành công (được tìm thấy cho lời khai sai có bằng chứng thuyết phục). “Chi phí” mà kẻ tấn công sẵn sàng chi ra càng lớn thì khả năng thành công của hắn càng cao.
Cho đến nay, chúng tôi đã định nghĩa tính bảo mật của STARK là một hàm (t), khác với cách mọi người thảo luận về bảo mật trên Twitter tiền điện tử hàng ngày. Trên Twitter, bạn có thể nghe thấy những điều như thế này: “Giải pháp này có 96 bit bảo mật.” Điều này chuyển thành định nghĩa của chúng ta về bảo mật như thế nào? Không có câu trả lời duy nhất cho vấn đề này, vì mọi người hiểu “x bit bảo mật” hơi khác một chút:
Giải thích một cách chặt chẽ, điều này có nghĩa là với bất kỳ t nào từ 1 đến 2⁹⁶, sai số độ tin cậy là (t) 2⁹⁶. Kẻ tấn công có thời gian chạy từ 2⁹⁶ trở xuống có xác suất thành công rất nhỏ, dưới 2⁹⁶, tức là nhỏ hơn 1 trên một tỷ nhân với 1 trên một tỷ.
Một cách giải thích lỏng lẻo hơn và có lẽ phổ biến hơn là bảo mật 96-bit có nghĩa là với bất kỳ t nào, sẽ có tình huống t/(t) 2⁹⁶. Điều này có nghĩa là xác suất thành công là tuyến tính (nghịch đảo) với thời gian chạy. Nếu kẻ tấn công có thời gian chạy là 2⁸⁶ thì xác suất thành công của hắn nhiều nhất là 2¹⁰.
Trong bài viết này, chúng ta sẽ thảo luận về lựa chọn thứ hai.
Từ IOP đến STARK với bảo mật 96-bit
Vì vậy, làm cách nào để chứng minh rằng một giải pháp có độ bảo mật 96 bit? Để trả lời câu hỏi này, chúng ta cần hiểu cấu trúc cấp cao mà STARK được xây dựng trên đó. STARK bao gồm ba phần chính: IOP (Bằng chứng Oracle tương tác), cây Merkle và hàm băm Fiat-Shamir; trọng tâm chính của chúng tôi là IOP. Khi các bộ phận thành phần này được chỉ định, chúng tôi có thể biên dịch chúng để tạo STARK. Chúng ta sẽ xem xét chi tiết các thành phần này, bao gồm chúng là gì và chúng kết hợp với nhau như thế nào.
Thành phần đầu tiên chúng ta sẽ xem xét là IOP: IOP tương tự như một bằng chứng tương tác tiêu chuẩn, trong đó người chứng minh và người xác thực tương tác trong nhiều vòng (chúng ta bị giới hạn ở các giao thức tiền xu công khai, trong đó người xác thực chỉ gửi các thử thách ngẫu nhiên đến người chứng minh). ). Trong IOP, trình xác minh không đọc đầy đủ thông báo của người chứng minh mà thay vào đó lấy mẫu một phần nhỏ bit từ thông báo của mỗi người chứng minh. Đây là lý do tại sao STARK được biên dịch sau này đạt được sự đơn giản.
Với IOP, làm cách nào để tạo STARK từ nó? Thông điệp của người tục ngữ có thể rất dài (trên thực tế, chúng còn dài hơn cả bản tính toán). Để nén thông tin này, chúng tôi sử dụng cây Merkle. Cây Merkle là cây băm nhị phân trong đó mỗi nút lá biểu thị một truy vấn hoặc một câu trả lời trong IOP. Rễ là lời hứa của toàn bộ thông điệp. Khi người xác nhận muốn đọc một vị trí cụ thể trong tin nhắn, người chứng minh sẽ cung cấp giá trị của vị trí đó và đường dẫn xác minh. Sau đó, người xác nhận có thể sử dụng đường dẫn này để xác minh rằng giá trị là chính xác. Trình xác thực IOP chỉ đọc một lượng nhỏ thông tin vị trí từ thông tin của người chứng minh. Do đó, các giao thức ngắn gọn (các giao thức có khối lượng giao tiếp thấp) có thể được triển khai bằng cây Merkle.
Vòng nén
Chúng ta có thể chọn STARK tương tác, nhưng để đơn giản hóa quá trình tạo STARK, chúng ta thường chọn STARK không tương tác, để người xác thực không cần chờ thông tin bên ngoài khi xây dựng STARK. Trên thực tế, đây là cách tất cả các hệ thống STARK hiện tại được triển khai và cách xây dựng giao thức ethSTARK. STARK không tương tác cũng là trường hợp đặc biệt của SNARK minh bạch (minh bạch có nghĩa là không cần thiết lập đáng tin cậy để khởi tạo chúng; "Giao thức Arthur Merlin" hoặc "IOP tiền xu công cộng"). Để thực hiện điều này, bước cuối cùng là áp dụng thuật toán Fiat-Shamir để nén nhiều vòng tương tác thành một tin nhắn duy nhất mà chúng tôi gọi là bằng chứng STARK. Chuyển đổi Fiat-Shamir là phương pháp chuyển đổi giao thức tương tác thành giao thức không tương tác. Trình chứng minh mô phỏng một giao thức tương tác trong khi nói chuyện với hàm băm. Để rút ra thử thách ngẫu nhiên cho vòng i, người chứng minh băm vào bản ghi một phần cho vòng i và diễn giải kết quả đầu ra là thử thách tiếp theo.
Điều này đảm bảo rằng người chứng minh không thể thay đổi câu trả lời của mình sau khi thử thách được đưa ra. Tuy nhiên, kẻ gian lận có một số con đường chiến lược mới không có trong IOP tương tác. Người chứng minh có thể tạo lại thử thách của người xác thực bằng cách sửa đổi thông tin của người chứng minh cuối cùng để nó sẽ nhận được bản ghi mới và do đó là một thử thách mới. Hóa ra khái niệm độ tin cậy tiêu chuẩn của IOP là không đủ để chứng minh sự an toàn của việc chuyển đổi Fiat-Shamir.
Ví dụ: có IOP gồm 96 vòng và thêm bản hack sau vào trình xác thực: nếu bit đầu tiên về tính ngẫu nhiên của trình xác thực là 0 trong mỗi vòng trong số 96 vòng thì trình xác thực sẽ chấp nhận nó (mà không thấy bất kỳ bằng chứng nào). Chúng ta có thể thấy rằng việc thêm bản hack này vào trình xác thực chỉ thêm một thuật ngữ 2⁹⁶ vào lỗi độ tin cậy của IOP. Tuy nhiên, sau khi chuyển đổi Fiat-Shamir, kẻ tấn công có thể dễ dàng sửa đổi thông tin của bộ chứng minh để đảm bảo rằng mỗi giá trị băm bắt đầu bằng 0, từ đó xâm nhập vào hệ thống trong thời gian rất ngắn. Hãy yên tâm, kịch bản thảm khốc này chỉ là ví dụ lý thuyết và không áp dụng cho STARK đã triển khai. Vì vậy, hãy cùng xem tại sao STARK của chúng ta lại an toàn. Nói tóm lại, chúng tôi sẽ chỉ ra rằng kẻ tấn công chạy tối đa t bước và xác suất tấn công thành công nhiều nhất là (t) t 2⁹⁶.
IOP và độ tin cậy từng vòng
Bảo mật của STARK phụ thuộc vào IOP cơ bản của nó. Nhưng việc IOP có 96 bit bảo mật có ý nghĩa gì? Theo định nghĩa tiêu chuẩn, lỗi độ tin cậy của IOP là 2⁹⁶: điều này có nghĩa là xác suất mà bất kỳ kẻ tấn công nào (bất kể thời gian chạy) có thể đánh lừa người xác nhận nhiều nhất là 2-96. Tuy nhiên, như chúng ta đã thảo luận, độ tin cậy của IOP chỉ là một trong ba thành phần, không đủ để có được 96 bit bảo mật từ STARK được tổng hợp từ cả ba bước. Ngược lại, tính an toàn của STARK đã biên dịch được chứng minh với giả định rằng STARK có lỗi độ tin cậy theo từng vòng là 96 bit (đôi khi sử dụng một định nghĩa tương tự gọi là độ tin cậy phục hồi trạng thái).
Theo trực giác, "sự ổn định từng vòng" có nghĩa là mỗi vòng có 96 bit bảo mật, không chỉ toàn bộ giao thức. Cụ thể hơn, độ tin cậy theo từng vòng đề cập đến sự tồn tại của một biến vị ngữ có thể lấy được một phần bản ghi của giao thức và cho chúng tôi biết liệu bản ghi này có phải là "lừa đảo" hay không: "bản ghi trống" không phải là "lừa đảo" và khi Và bản ghi hoàn chỉnh chỉ là "lừa đảo" nếu được người xác thực chấp nhận. Cuối cùng, đối với bất kỳ bản ghi một phần nào không "giả mạo" trình xác nhận, xác suất bản ghi đó trở thành "giả mạo" trong vòng tiếp theo nhiều nhất là 2⁹⁶. Nếu có một vị từ có các thuộc tính này, chúng ta nói rằng giao thức có độ tin cậy 96 bit (vị ngữ này không yêu cầu tính toán hiệu quả).
Trong nhiều trường hợp, mọi người chỉ phân tích độ tin cậy của IOP chứ không phải độ tin cậy toàn diện của nó. Phải thừa nhận rằng, thật khó để nghĩ ra một ví dụ (ngoại trừ các ví dụ được sản xuất) về IOP có độ tin cậy tiêu chuẩn nhưng không có độ tin cậy toàn diện. Tuy nhiên, khi rút ra các giới hạn an toàn cụ thể, sự khác biệt giữa hai giới hạn này có thể phát sinh và mỗi bit đều có giá trị. Do đó, để đưa ra các giới hạn chặt chẽ và cụ thể, việc phân tích nghiêm ngặt về độ tin cậy theo từng vòng của IOP là cần thiết. Đây chính xác là những gì chúng tôi đang làm với giao thức FRI và ethSTARK IOP mà STARK IOP dựa trên đó. Bản thân việc phân tích này không hề tầm thường và nằm ngoài phạm vi của bài viết này. Sử dụng phân tích mới, chúng tôi có thể đặt các tham số chính xác cho bằng chứng của mình.
Độ tin cậy từng bước thực sự mang lại cho chúng tôi sự đảm bảo mà chúng tôi cần. Người chứng minh có thể tạo lại thử thách nhiều lần, nhưng chúng tôi biết rằng trong bất kỳ vòng nào, xác suất tạo ra bản ghi gian lận là 2⁹⁶. Do đó, nếu người chứng minh có t lần (được đo bằng số lần gọi hàm băm), thì Nó có thể thử ở hầu hết t lần để có được một bản ghi lừa đảo, điều này giới hạn khả năng thành công của nó ở mức (t) t 2⁹⁶.
Thêm tất cả các mục lỗi
Cuối cùng, để tất cả những điều này là đúng, chúng ta cần đảm bảo rằng người chứng minh không thể giả mạo cây Merkle. Chúng ta có thể chỉ ra rằng miễn là người chứng minh không tìm thấy xung đột nào trong hàm băm thì anh ta không thể gian lận trong cây Merkle. Xác suất kẻ tấn công tìm thấy xung đột bằng cách sử dụng lệnh gọi t (hàm băm ngẫu nhiên) tối đa là t2/2, là độ dài đầu ra của hàm băm (gây ra bởi "Nghịch lý sinh nhật"). Đây là lý do tại sao chúng ta cần đặt hàm băm Độ dài gấp đôi độ bảo mật cần thiết. Vì vậy, nếu chúng ta có hàm băm có độ dài đầu ra là 192 và IOP có độ tin cậy từng vòng là 96 bit, chúng ta sẽ nhận được STARK được biên dịch đáng tin cậy Lỗi tình dục (t )=t2-⁹⁶ + t2 2¹⁹⁶. Vì t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, lược đồ này có 95 bit giới tính an toàn.
Tóm tắt
Kết hợp lại với nhau, STARK cung cấp một phương pháp mạnh mẽ để xác minh một cách đáng tin cậy tính chính xác của các phép tính được thực hiện trên dữ liệu công khai. Tính bảo mật của STARK thường được đo bằng "lỗi độ tin cậy", biểu thị xác suất kẻ tấn công đưa ra tuyên bố sai thành công và thuyết phục người xác nhận bằng bằng chứng. Để đạt được mức bảo mật cần thiết, chẳng hạn như 96 bit, IOP cơ bản phải đáp ứng độ tin cậy từng vòng để đảm bảo duy trì mức bảo mật cao ở mỗi vòng. Chúng tôi đã phân tích độ tin cậy từng vòng của IOP mà STARK của chúng tôi dựa vào đó để rút ra các giới hạn an toàn cụ thể.
Xem bản gốc
Trang này có thể chứa nội dung của bên thứ ba, được cung cấp chỉ nhằm mục đích thông tin (không phải là tuyên bố/bảo đảm) và không được coi là sự chứng thực cho quan điểm của Gate hoặc là lời khuyên về tài chính hoặc chuyên môn. Xem Tuyên bố từ chối trách nhiệm để biết chi tiết.
Phân tích chuyên sâu về tính bảo mật hoàn toàn của STARK
原文：An toàn và lành mạnh - Đi sâu vào bảo mật STARK
Dịch và hiệu đính: "Cộng đồng người Trung Quốc Starknet"
Thông tin nhanh nổi bật
Giải thích chi tiết về bảo mật STARK
Hệ thống chứng minh STARK, hay đối số kiến thức minh bạch có thể mở rộng, là một công cụ mạnh mẽ để đảm bảo tính toàn vẹn trong tính toán: nó cho phép xác minh một cách không đáng tin cậy về tính chính xác của các tính toán được thực hiện trên dữ liệu công cộng. Trong bài viết này, chúng ta sẽ đi sâu vào tính bảo mật được cung cấp bởi các bằng chứng STARK, xác định chúng và khám phá các kỹ thuật để chứng minh tính bảo mật của các sơ đồ.
(Đọc phần 6 của tài liệu ethSTARK (phiên bản 1.2) để biết chi tiết, cũng như công trình độc lập quan trọng và toàn diện về chủ đề này của Block et al.).
Chúng ta đang cố gắng đạt được điều gì với phân tích bảo mật? Chúng tôi muốn ngăn chặn "các cuộc tấn công thành công" vào hệ thống STARK do một tuyên bố sai và bằng chứng STARK được người xác thực STARK chấp nhận để phản hồi lại tuyên bố (sai) đó. Bởi vì việc trình bày sai là nguy hiểm và chúng có thể xảy ra ở mọi quy mô và hình thức nên chúng tôi muốn được an toàn trước tất cả những điều đó. Bất kỳ tuyên bố sai nào, thậm chí tầm thường như 1+1=3, khi được kết hợp với bằng chứng STARK được trình xác nhận STARK chấp nhận, sẽ được coi là một cuộc tấn công thành công vào hệ thống. (Những người có nền tảng về mật mã có thể muốn biết rằng STARK cũng có thể đáp ứng các khái niệm bảo mật mạnh hơn như độ tin cậy của kiến thức, nhưng để đơn giản, bài viết này sẽ tập trung vào các trường hợp đơn giản về độ tin cậy).
Làm cách nào để chúng tôi xác định chính thức tính bảo mật của hệ thống STARK? Chúng tôi xác định điều này bằng cách phân tích "lỗi về độ tin cậy". "Lỗi về độ tin cậy" đo lường đại khái "chi phí" dự kiến mà kẻ tấn công sẽ phải trả để thực hiện một cuộc tấn công thành công (tức là tìm bằng chứng STARK cho một tuyên bố sai được người xác nhận STARK chấp nhận). Về mặt toán học, lỗi độ tin cậy là một hàm (t) có đầu vào là tham số thời gian t, biểu thị thời gian tính toán mà kẻ tấn công sẵn sàng bỏ ra để khởi động một cuộc tấn công và đầu ra là xác suất cuộc tấn công của kẻ tấn công sẽ thành công (được tìm thấy cho lời khai sai có bằng chứng thuyết phục). “Chi phí” mà kẻ tấn công sẵn sàng chi ra càng lớn thì khả năng thành công của hắn càng cao.
Cho đến nay, chúng tôi đã định nghĩa tính bảo mật của STARK là một hàm (t), khác với cách mọi người thảo luận về bảo mật trên Twitter tiền điện tử hàng ngày. Trên Twitter, bạn có thể nghe thấy những điều như thế này: “Giải pháp này có 96 bit bảo mật.” Điều này chuyển thành định nghĩa của chúng ta về bảo mật như thế nào? Không có câu trả lời duy nhất cho vấn đề này, vì mọi người hiểu “x bit bảo mật” hơi khác một chút:
Trong bài viết này, chúng ta sẽ thảo luận về lựa chọn thứ hai.
Từ IOP đến STARK với bảo mật 96-bit
Vì vậy, làm cách nào để chứng minh rằng một giải pháp có độ bảo mật 96 bit? Để trả lời câu hỏi này, chúng ta cần hiểu cấu trúc cấp cao mà STARK được xây dựng trên đó. STARK bao gồm ba phần chính: IOP (Bằng chứng Oracle tương tác), cây Merkle và hàm băm Fiat-Shamir; trọng tâm chính của chúng tôi là IOP. Khi các bộ phận thành phần này được chỉ định, chúng tôi có thể biên dịch chúng để tạo STARK. Chúng ta sẽ xem xét chi tiết các thành phần này, bao gồm chúng là gì và chúng kết hợp với nhau như thế nào.
Thành phần đầu tiên chúng ta sẽ xem xét là IOP: IOP tương tự như một bằng chứng tương tác tiêu chuẩn, trong đó người chứng minh và người xác thực tương tác trong nhiều vòng (chúng ta bị giới hạn ở các giao thức tiền xu công khai, trong đó người xác thực chỉ gửi các thử thách ngẫu nhiên đến người chứng minh). ). Trong IOP, trình xác minh không đọc đầy đủ thông báo của người chứng minh mà thay vào đó lấy mẫu một phần nhỏ bit từ thông báo của mỗi người chứng minh. Đây là lý do tại sao STARK được biên dịch sau này đạt được sự đơn giản.
Với IOP, làm cách nào để tạo STARK từ nó? Thông điệp của người tục ngữ có thể rất dài (trên thực tế, chúng còn dài hơn cả bản tính toán). Để nén thông tin này, chúng tôi sử dụng cây Merkle. Cây Merkle là cây băm nhị phân trong đó mỗi nút lá biểu thị một truy vấn hoặc một câu trả lời trong IOP. Rễ là lời hứa của toàn bộ thông điệp. Khi người xác nhận muốn đọc một vị trí cụ thể trong tin nhắn, người chứng minh sẽ cung cấp giá trị của vị trí đó và đường dẫn xác minh. Sau đó, người xác nhận có thể sử dụng đường dẫn này để xác minh rằng giá trị là chính xác. Trình xác thực IOP chỉ đọc một lượng nhỏ thông tin vị trí từ thông tin của người chứng minh. Do đó, các giao thức ngắn gọn (các giao thức có khối lượng giao tiếp thấp) có thể được triển khai bằng cây Merkle.
Vòng nén
Chúng ta có thể chọn STARK tương tác, nhưng để đơn giản hóa quá trình tạo STARK, chúng ta thường chọn STARK không tương tác, để người xác thực không cần chờ thông tin bên ngoài khi xây dựng STARK. Trên thực tế, đây là cách tất cả các hệ thống STARK hiện tại được triển khai và cách xây dựng giao thức ethSTARK. STARK không tương tác cũng là trường hợp đặc biệt của SNARK minh bạch (minh bạch có nghĩa là không cần thiết lập đáng tin cậy để khởi tạo chúng; "Giao thức Arthur Merlin" hoặc "IOP tiền xu công cộng"). Để thực hiện điều này, bước cuối cùng là áp dụng thuật toán Fiat-Shamir để nén nhiều vòng tương tác thành một tin nhắn duy nhất mà chúng tôi gọi là bằng chứng STARK. Chuyển đổi Fiat-Shamir là phương pháp chuyển đổi giao thức tương tác thành giao thức không tương tác. Trình chứng minh mô phỏng một giao thức tương tác trong khi nói chuyện với hàm băm. Để rút ra thử thách ngẫu nhiên cho vòng i, người chứng minh băm vào bản ghi một phần cho vòng i và diễn giải kết quả đầu ra là thử thách tiếp theo.
Điều này đảm bảo rằng người chứng minh không thể thay đổi câu trả lời của mình sau khi thử thách được đưa ra. Tuy nhiên, kẻ gian lận có một số con đường chiến lược mới không có trong IOP tương tác. Người chứng minh có thể tạo lại thử thách của người xác thực bằng cách sửa đổi thông tin của người chứng minh cuối cùng để nó sẽ nhận được bản ghi mới và do đó là một thử thách mới. Hóa ra khái niệm độ tin cậy tiêu chuẩn của IOP là không đủ để chứng minh sự an toàn của việc chuyển đổi Fiat-Shamir.
Ví dụ: có IOP gồm 96 vòng và thêm bản hack sau vào trình xác thực: nếu bit đầu tiên về tính ngẫu nhiên của trình xác thực là 0 trong mỗi vòng trong số 96 vòng thì trình xác thực sẽ chấp nhận nó (mà không thấy bất kỳ bằng chứng nào). Chúng ta có thể thấy rằng việc thêm bản hack này vào trình xác thực chỉ thêm một thuật ngữ 2⁹⁶ vào lỗi độ tin cậy của IOP. Tuy nhiên, sau khi chuyển đổi Fiat-Shamir, kẻ tấn công có thể dễ dàng sửa đổi thông tin của bộ chứng minh để đảm bảo rằng mỗi giá trị băm bắt đầu bằng 0, từ đó xâm nhập vào hệ thống trong thời gian rất ngắn. Hãy yên tâm, kịch bản thảm khốc này chỉ là ví dụ lý thuyết và không áp dụng cho STARK đã triển khai. Vì vậy, hãy cùng xem tại sao STARK của chúng ta lại an toàn. Nói tóm lại, chúng tôi sẽ chỉ ra rằng kẻ tấn công chạy tối đa t bước và xác suất tấn công thành công nhiều nhất là (t) t 2⁹⁶.
IOP và độ tin cậy từng vòng
Bảo mật của STARK phụ thuộc vào IOP cơ bản của nó. Nhưng việc IOP có 96 bit bảo mật có ý nghĩa gì? Theo định nghĩa tiêu chuẩn, lỗi độ tin cậy của IOP là 2⁹⁶: điều này có nghĩa là xác suất mà bất kỳ kẻ tấn công nào (bất kể thời gian chạy) có thể đánh lừa người xác nhận nhiều nhất là 2-96. Tuy nhiên, như chúng ta đã thảo luận, độ tin cậy của IOP chỉ là một trong ba thành phần, không đủ để có được 96 bit bảo mật từ STARK được tổng hợp từ cả ba bước. Ngược lại, tính an toàn của STARK đã biên dịch được chứng minh với giả định rằng STARK có lỗi độ tin cậy theo từng vòng là 96 bit (đôi khi sử dụng một định nghĩa tương tự gọi là độ tin cậy phục hồi trạng thái).
Theo trực giác, "sự ổn định từng vòng" có nghĩa là mỗi vòng có 96 bit bảo mật, không chỉ toàn bộ giao thức. Cụ thể hơn, độ tin cậy theo từng vòng đề cập đến sự tồn tại của một biến vị ngữ có thể lấy được một phần bản ghi của giao thức và cho chúng tôi biết liệu bản ghi này có phải là "lừa đảo" hay không: "bản ghi trống" không phải là "lừa đảo" và khi Và bản ghi hoàn chỉnh chỉ là "lừa đảo" nếu được người xác thực chấp nhận. Cuối cùng, đối với bất kỳ bản ghi một phần nào không "giả mạo" trình xác nhận, xác suất bản ghi đó trở thành "giả mạo" trong vòng tiếp theo nhiều nhất là 2⁹⁶. Nếu có một vị từ có các thuộc tính này, chúng ta nói rằng giao thức có độ tin cậy 96 bit (vị ngữ này không yêu cầu tính toán hiệu quả).
Trong nhiều trường hợp, mọi người chỉ phân tích độ tin cậy của IOP chứ không phải độ tin cậy toàn diện của nó. Phải thừa nhận rằng, thật khó để nghĩ ra một ví dụ (ngoại trừ các ví dụ được sản xuất) về IOP có độ tin cậy tiêu chuẩn nhưng không có độ tin cậy toàn diện. Tuy nhiên, khi rút ra các giới hạn an toàn cụ thể, sự khác biệt giữa hai giới hạn này có thể phát sinh và mỗi bit đều có giá trị. Do đó, để đưa ra các giới hạn chặt chẽ và cụ thể, việc phân tích nghiêm ngặt về độ tin cậy theo từng vòng của IOP là cần thiết. Đây chính xác là những gì chúng tôi đang làm với giao thức FRI và ethSTARK IOP mà STARK IOP dựa trên đó. Bản thân việc phân tích này không hề tầm thường và nằm ngoài phạm vi của bài viết này. Sử dụng phân tích mới, chúng tôi có thể đặt các tham số chính xác cho bằng chứng của mình.
Độ tin cậy từng bước thực sự mang lại cho chúng tôi sự đảm bảo mà chúng tôi cần. Người chứng minh có thể tạo lại thử thách nhiều lần, nhưng chúng tôi biết rằng trong bất kỳ vòng nào, xác suất tạo ra bản ghi gian lận là 2⁹⁶. Do đó, nếu người chứng minh có t lần (được đo bằng số lần gọi hàm băm), thì Nó có thể thử ở hầu hết t lần để có được một bản ghi lừa đảo, điều này giới hạn khả năng thành công của nó ở mức (t) t 2⁹⁶.
Thêm tất cả các mục lỗi
Cuối cùng, để tất cả những điều này là đúng, chúng ta cần đảm bảo rằng người chứng minh không thể giả mạo cây Merkle. Chúng ta có thể chỉ ra rằng miễn là người chứng minh không tìm thấy xung đột nào trong hàm băm thì anh ta không thể gian lận trong cây Merkle. Xác suất kẻ tấn công tìm thấy xung đột bằng cách sử dụng lệnh gọi t (hàm băm ngẫu nhiên) tối đa là t2/2, là độ dài đầu ra của hàm băm (gây ra bởi "Nghịch lý sinh nhật"). Đây là lý do tại sao chúng ta cần đặt hàm băm Độ dài gấp đôi độ bảo mật cần thiết. Vì vậy, nếu chúng ta có hàm băm có độ dài đầu ra là 192 và IOP có độ tin cậy từng vòng là 96 bit, chúng ta sẽ nhận được STARK được biên dịch đáng tin cậy Lỗi tình dục (t )=t2-⁹⁶ + t2 2¹⁹⁶. Vì t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, lược đồ này có 95 bit giới tính an toàn.
Tóm tắt
Kết hợp lại với nhau, STARK cung cấp một phương pháp mạnh mẽ để xác minh một cách đáng tin cậy tính chính xác của các phép tính được thực hiện trên dữ liệu công khai. Tính bảo mật của STARK thường được đo bằng "lỗi độ tin cậy", biểu thị xác suất kẻ tấn công đưa ra tuyên bố sai thành công và thuyết phục người xác nhận bằng bằng chứng. Để đạt được mức bảo mật cần thiết, chẳng hạn như 96 bit, IOP cơ bản phải đáp ứng độ tin cậy từng vòng để đảm bảo duy trì mức bảo mật cao ở mỗi vòng. Chúng tôi đã phân tích độ tin cậy từng vòng của IOP mà STARK của chúng tôi dựa vào đó để rút ra các giới hạn an toàn cụ thể.