原文: An toàn và lành mạnh — Đi sâu vào bảo mật STARK
Dịch thuật và hiệu đính: "Cộng đồng người Hoa 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 dịch thành các 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 cập nhật mới nhất cho 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, định nghĩa 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, đều đượ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 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 cần để 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 bảo mật được thảo luận hàng ngày trên Twitter về tiền điện tử. Trên Twitter, bạn có thể nghe thấ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 bảo mật của chúng tôi 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ố về độ tin cậy là (t) 2⁹⁶ . Kẻ tấn công chạy từ 2⁹⁶ trở xuống có xác suất thành công rất nhỏ, nhỏ hơn 2⁹⁶ hoặc 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ó trường hợp 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 tương tác của Oracle), 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 ra 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á đại diện cho một truy vấn hoặc 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 đang đượ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à một 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, những kẻ chứng minh gian lận có một số con đường chính sách 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 các khái niệm về độ 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 trong tính ngẫu nhiên của trình xác thực là 0 trong mỗi 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 đều bắt đầu bằng 0, từ đó gây nguy hiểm cho 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 tôi lại an toàn. Nói tóm lại, chúng tôi sẽ chỉ ra rằng, đối với kẻ tấn công chạy tối đa t bước, 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
Tính 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, IOP có lỗi độ tin cậy 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 đủ để đạt được mức bảo mật 96 bit từ STARK được tổng hợp từ cả ba bước. Ngược lại, tính an toàn của STARK được biên dịch đã được chứng minh khi giả định rằng STARK có lỗi độ tin cậy theo từng vòng 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" chỉ ra rằng 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 nhận 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ó 96 bit độ tin cậy theo từng vòng (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 đó, để rút 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 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 dựa trên STARK IOP. 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ì Người đó có thể thử tại. 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 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"). 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 tuyến tính ( t)=t2-⁹⁶ + t2 2¹⁹⁶. Vì t/(t) = t/(t 2⁹⁶+t2 2¹⁹⁶) 1/(2⁹⁶+1/2⁹⁶) = 2²⁹⁵, sơ đồ này có 95 bit bảo mật.
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 thực 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 trong 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ể.