Phân tích thuật toán STARK

• Phần 0: Giới thiệu

• Phần 1: Nhìn vào STARK

• Phần 2: Những “Công cụ” hữu ích

• Phần 3: THỨ SÁU

• Phần 4: IOP đa thức STARK

• Phần 5: Cuộc giải cứu-Prime STARK

• Phần 6: Tăng tốc toàn bộ quá trình

1. STARK là gì?

Gần đây, một trong những bước phát triển thú vị nhất trong lĩnh vực hệ thống chứng minh mật mã là sự phát triển của STARK. Nó xuất hiện sau khi ngành công nghiệp blockchain đang bùng nổ. Nhìn chung, các hệ thống bằng chứng dường như được thiết kế riêng cho chúng: các mạng chuỗi khối thường bao gồm các bên không tin tưởng lẫn nhau, những người muốn sử dụng thông tin bí mật để giao dịch hoặc cập nhật trạng thái tập thể theo các quy tắc tiến hóa của trạng thái. Vì những người tham gia không tin tưởng lẫn nhau, nên họ cần một cách để xác minh tính hợp lệ của các giao dịch (hoặc cập nhật trạng thái) do các đồng nghiệp của họ đề xuất.

Do các thuộc tính sau của zk-SNARK, chúng có khả năng đảm bảo tính toàn vẹn tính toán một cách tự nhiên trong môi trường này:

• zk-SNARK nói chung là tổng quát, có nghĩa là chúng có thể chứng minh tính toàn vẹn của bất kỳ tính toán nào;

• zk-SNARK không tương tác, nghĩa là toàn bộ bằng chứng về tính toàn vẹn bao gồm một thông báo duy nhất;

• Việc xác minh zk-SNARK là hiệu quả, nghĩa là, khối lượng công việc của trình xác minh ít hơn một bậc so với việc chỉ chạy lại phép tính (Ghi chú của người dịch: Cũng có thể có một số bậc độ lớn);

• zk-SNARK không có kiến ​​thức, nghĩa là chúng không tiết lộ bất kỳ thông tin nào về đầu vào bí mật của máy tính.

"Tôi hy vọng zk-SNARK sẽ thâm nhập vào thế giới chính thống trong 10-20 năm tới và dẫn đầu một cuộc cách mạng lớn."—— "Thần V" 2021.9.2

zk-SNARK đã xuất hiện được một thời gian, nhưng hệ thống bằng chứng STARK là một thứ tương đối mới. Nó nổi bật vì nhiều lý do:

• Trong khi zk-SNARK truyền thống dựa trên các giả định và câu đố mật mã phức tạp, thành phần mật mã duy nhất trong hệ thống bằng chứng STARK là hàm băm chống va chạm. Do đó, theo mô hình hàm băm lý tưởng hóa, có thể chứng minh tính bảo mật chống lượng tử của hệ thống bằng chứng (trong tài liệu, sự lý tưởng hóa này được gọi là "mô hình tiên tri ngẫu nhiên lượng tử" mô hình tiên tri ngẫu nhiên lượng tử). Điều này hoàn toàn trái ngược với SNARK thế hệ đầu tiên, sử dụng bản đồ song tuyến tính và chỉ được chứng minh là an toàn theo các giả định không thể chứng minh được.

• Số học của STARK không phụ thuộc vào các vấn đề khó về mật mã, vì vậy miền này có thể được chọn cụ thể để tối ưu hóa hiệu suất. Do đó, các STARK có thể đưa ra bằng chứng (Prover) thực sự nhanh chóng.

• Các zk-SNARK truyền thống dựa vào một buổi lễ thiết lập đáng tin cậy để tạo ra các tham số công khai. Sau buổi lễ, các thông số ngẫu nhiên được sử dụng phải được quên đi một cách an toàn. Bản thân buổi lễ không phải là không đáng tin cậy, vì nếu những người tham gia từ chối hoặc quên xóa "rác độc hại" mật mã này, thì họ vẫn có khả năng giả mạo bằng chứng. Ngược lại, STARK không có thiết lập đáng tin cậy và do đó không có mật mã"chất thải nguy hại".



"Tôi thường đồng ý, với sự dè dặt ở hai điểm:

1) STARK sẽ thống trị, không phải SNARK

2) 3-5 năm nữa sẽ thâm nhập vào thế giới chính thống

Đặt một lời nhắc trên lịch của tôi để kiểm tra những từ đó 4 năm kể từ bây giờ. ——Eli Ben-Sasson 2021.9.2

Trong hướng dẫn này, tôi sẽ giải thích có bao nhiêu phần trong số này hoạt động cùng nhau. Giải thích theo nghĩa đen này được hỗ trợ bởi một triển khai Python chứng minh và xác minh các phép tính đơn giản dựa trên hàm băm Rescue-Prime. Sau khi đọc hoặc làm theo hướng dẫn này, bạn sẽ có thể viết các trình chứng minh và trình xác minh STARK không cần kiến ​​thức của riêng mình để tính toán theo lựa chọn của bạn

2. Tại sao viết bài này?

Cần sớm chỉ ra rằng có nhiều nguồn học tập STARK. Đây là một danh sách không đầy đủ.

• Các bài báo về FRI, STARK, DEEP-FRI và phân tích độ tin cậy mới nhất của FRI

• Hướng dẫn nhiều phần (Phần 1/2/3) của Vitalik Buterin.

• Một loạt các bài đăng trên blog từ StarkWare (phần 1, 2, 3, 4, 5).

• Webcast STARK@Home của StarkWare

• Khóa học trực tuyến STARK 101 của StarkWare

• Tài liệu EthStark của StarkWare

• Nói chung, bất cứ thứ gì StarkWare đưa ra

Với rất nhiều tài nguyên học tập, tại sao tôi lại viết một hướng dẫn khác?

Hướng dẫn hiện có là tương đối nông. Những hướng dẫn này thực hiện tốt công việc giải thích ở cấp độ cao cách thức hoạt động của các kỹ thuật này và truyền đạt trực giác về lý do tại sao STARK hoạt động. Tuy nhiên, chúng không mô tả một hệ thống hoàn chỉnh, có thể triển khai được. Ví dụ: không có hướng dẫn nào mô tả cách triển khai kiến ​​thức không, cách xử lý hàng loạt các bằng chứng cấp thấp khác nhau hoặc cách xác định mức độ bảo mật kết quả. Tài liệu EthSTARK cung cấp một tài liệu tham khảo đầy đủ để trả lời hầu hết các câu hỏi này, nhưng nó dành riêng cho một tính toán cụ thể, không bao gồm kiến ​​thức bằng không và không đưa ra lời giải thích trực quan và dễ tiếp cận.

Những giấy tờ này là khó hiểu. Đáng buồn thay, các ưu đãi trong xuất bản khoa học được thiết lập để gây khó khăn cho các bài báo khoa học đối với độc giả bình thường. Do đó, các hướng dẫn như bài viết này là cần thiết để làm cho các giấy tờ này dễ hiểu với nhiều người hơn.

Thông tin đã lỗi thời. Kể từ đó, nhiều kỹ thuật được mô tả trong các hướng dẫn khác nhau đã được cải tiến. Ví dụ: tài liệu EthSTARK (tài liệu mới nhất được trích dẫn ở trên) mô tả kỹ thuật nội suy SÂU để giảm yêu cầu đánh giá chính xác đối với các đa thức có mức độ giới hạn. Kỹ thuật này không được đề cập trong các nguồn này vì các nguồn này có trước kỹ thuật này.

Tôi thích phong cách của riêng tôi hơn. Tôi không đồng ý với rất nhiều biểu tượng và tên và tôi hy vọng mọi người sử dụng đúng. Đặc biệt, tôi muốn tập trung vào các đa thức, như những đối tượng cơ bản nhất của các hệ thống chứng minh. Ngược lại, tất cả các nguồn khác mô tả cơ chế của các hệ thống bằng chứng về mặt hoạt động trên các từ mã Reed-Solomon.

Hướng dẫn này đã giúp tôi hiểu rõ hơn về STARK. Việc viết bài hướng dẫn này đã giúp tôi hệ thống hóa kiến ​​thức của mình và tìm ra những chỗ còn nông cạn hoặc thiếu sót.

3. Yêu cầu kiến ​​thức nền tảng

Hướng dẫn này đề cập đến một số kiến ​​thức cơ bản khi cần thiết. Tuy nhiên, tất cả độc giả nên hiểu và nghiên cứu các chủ đề sau, vì phần giới thiệu ở đây có thể quá dày đặc nếu họ không quen thuộc với chúng.

• Trường hữu hạn và trường mở rộng của chúng

• Đa thức trên trường hữu hạn, bao gồm cả đa thức đơn biến và đa biến

• hàm băm

• hàm băm

4. Thuật sĩ sê-ri

• Phần 1: Nhìn vào STARK mô tả khái niệm và quy trình làm việc ở cấp độ cao

• Phần 2: Các "công cụ" hữu ích giới thiệu các công cụ toán học và mật mã cơ bản để từ đó xây dựng hệ thống chứng minh

• Phần 3: FRI bao gồm thử nghiệm cấp thấp, là cốt lõi mật mã của hệ thống bằng chứng

• Part 4: STARK Polynomial IOP（IOP,bằng chứng tiên tri tương tác) giải thích lý thuyết thông tin để tạo ra các hệ thống bằng chứng trừu tượng từ các yêu cầu tính toán tùy ý

• Phần 5: A Rescue-Prime STARK kết hợp các công cụ này lại với nhau để xây dựng một hệ thống chứng minh minh bạch không kiến ​​thức cho một phép tính đơn giản

• Phần 6: Tăng tốc toàn bộ quy trình Giới thiệu các thuật toán và công nghệ giúp toàn bộ quy trình nhanh hơn và hiệu quả hơn"S "(ngắn gọn, súc tích) đưa vào STARK

  5. Lời cảm ơn

Các tác giả xin cảm ơn Bobbin Threadbare, Thorkil Værge và Eli Ben-Sasson vì những phản hồi và nhận xét hữu ích của họ cũng như Quỹ Nervos đã hỗ trợ tài chính cho họ. Gửi email cho anh ấy: alan@nervos.org hoặc theo dõi aszepieniec trên twitter hoặc Github.

Lưu ý của người dịch: Có một số lượng lớn các liên kết tài liệu trong văn bản gốc, không thể đính kèm do giới hạn của tài khoản chính thức, xin độc giả tham khảo các liên kết tài liệu trong văn bản gốc.

About zCloak Network

zCloak Network là một nền tảng dịch vụ điện toán riêng dựa trên hệ sinh thái Polkadot, sử dụng máy ảo zk-STARK để tạo và xác minh bằng chứng không kiến ​​thức cho điện toán nói chung. Dựa trên dữ liệu tự trị ban đầu và công nghệ điện toán tự chứng nhận, người dùng có thể phân tích và tính toán dữ liệu mà không cần gửi dữ liệu ra bên ngoài. Thông qua cơ chế nhắn tin chuỗi chéo Polkadot, hỗ trợ bảo vệ quyền riêng tư dữ liệu có thể được cung cấp cho các chuỗi song song khác và các chuỗi công khai khác trong hệ sinh thái Polkadot. Dự án sẽ áp dụng mô hình kinh doanh "zero-knowledge proof-as-a-service" để tạo ra cơ sở hạ tầng điện toán bảo mật đa chuỗi một cửa.