STARK: Chứng minh đa thức
Tuyển chọn TechFlowTuyển chọn TechFlow
STARK: Chứng minh đa thức
Làm thế nào loại bằng chứng không kiến thức mới này thực sự hoạt động?
Chuyên sâu báo cáo Web3Chắc hẳn nhiều người đã từng nghe đến ZK-SNARKS, một công nghệ chứng minh kiến thức không tiết lộ (zero-knowledge proof) phổ quát và súc tích, có thể được áp dụng trong nhiều lĩnh vực từ tính toán có xác minh được cho tới các loại tiền mã hóa yêu cầu bảo mật. Tuy nhiên, bạn có thể chưa biết rằng hiện nay ZK-SNARKs đã có thêm một người anh em mới: ZK-STARKs. Chữ "T" ở đây đại diện cho từ "transparent" (minh bạch), ZK-STARKs giải quyết một điểm yếu lớn của ZK-SNARKs, đó là việc ZK-SNARKs phụ thuộc vào “thiết lập đáng tin cậy” (trusted setup). ZK-STARKs cũng mang lại những giả định mật mã đơn giản hơn, loại bỏ việc sử dụng đường cong elliptic, các phép ghép cặp (pairings) và giả thiết về kiến thức số mũ (the knowledge-of-exponent assumption), đồng thời hoàn toàn dựa trên hàm băm và lý thuyết thông tin. Điều này cũng có nghĩa là, ngay cả trước các đối thủ sử dụng máy tính lượng tử, nó vẫn đảm bảo an toàn.
Tất nhiên, điều này đi kèm với một cái giá: kích thước bằng chứng sẽ tăng từ 288 byte (b) lên vài trăm kilobyte (kb). Mặc dù trong một số trường hợp, chi phí này có thể không thực sự xứng đáng, nhưng trong các tình huống khác, đặc biệt là đối với các ứng dụng blockchain đòi hỏi mức độ tối thiểu hóa niềm tin cao, thì nó hoàn toàn có thể xứng đáng. Và nếu một ngày nào đó đường cong elliptic bị phá vỡ, hay máy tính lượng tử thực sự xuất hiện, thì lúc ấy chắc chắn nó sẽ rất đáng giá.
Vậy thì, loại bằng chứng kiến thức không tiết lộ mới này hoạt động như thế nào? Trước tiên, hãy cùng ôn lại xem một bằng chứng kiến thức không tiết lộ ngắn gọn và phổ quát thực sự làm gì. Giả sử bạn hiện có một hàm (công khai, public) f, một đầu vào (riêng tư, private) x, và một đầu vào (công khai, public) y. Bạn muốn chứng minh rằng bạn biết một giá trị x sao cho f(x) = y mà không tiết lộ x là gì (người dịch: ví dụ như có một chiếc két sắt, bạn muốn chứng minh rằng mình biết mật khẩu của chiếc két mà không cần nói rõ mật khẩu cụ thể là gì). Ngoài ra, để bằng chứng này có tính súc tích, bạn mong muốn quá trình kiểm tra nó có thể diễn ra nhanh hơn so với việc tự thực hiện phép tính f.
Hãy cùng thảo luận một vài ví dụ:
-
f là một phép tính mất hai tuần để chạy trên một máy tính thông thường, nhưng chỉ mất hai giờ tại một trung tâm dữ liệu. Bạn có thể gửi tác vụ tính toán (tức là đoạn mã thực thi f) đến trung tâm dữ liệu, nơi này sẽ thực hiện phép tính và trả về kết quả, tức là bằng chứng y. Trong vài miligiây bạn có thể xác minh và tin chắc rằng y chính là câu trả lời đúng.
-
Bạn có một giao dịch được mã hóa dưới dạng "X1 là số dư cũ của tôi. X2 là số dư cũ của bạn. X3 là số dư mới của tôi. X4 là số dư mới của bạn". Bạn muốn xây dựng một bằng chứng rằng giao dịch này là hợp lệ (cụ thể là, số dư cũ và mới đều không âm, và số dư của tôi giảm đúng bằng số dư của bạn tăng lên). Giá trị x có thể là một cặp khóa mã hóa, f là một hàm chứa sẵn đầu vào công khai là giao dịch, dùng khóa để giải mã giao dịch, kiểm tra tính hợp lệ, nếu vượt qua thì trả về 1, ngược lại trả về 0. Khi đó y tất nhiên phải là 1.
-
Bạn đang có một chuỗi khối tương tự Ethereum và vừa tải về khối mới nhất. Bạn muốn tạo ra một bằng chứng rằng khối này hợp lệ, là khối mới nhất trong chuỗi, và mọi khối trong chuỗi đều hợp lệ. Bạn yêu cầu một nút toàn phần (full node) đáng tin cung cấp bằng chứng như vậy. Giá trị x là toàn bộ (hoặc một phần) chuỗi khối, f là một hàm xử lý từng khối, xác minh tính hợp lệ và xuất ra hash của khối trước, còn y chính là hash của khối bạn vừa tải về.
Vậy thì, khó khăn ở đâu đối với tất cả các ví dụ này? Hóa ra,
đảm bảo tính chấtkiến thức không tiết lộ(tức là riêng tư) là (tương đối!) dễ thực hiện. Có nhiều cách để chuyển đổi bất kỳ phép tính nào thành một vấn đề tương tự như bài toán tô màu đồ thị ba màu, trong đó cách tô màu đồ thị liên quan đến lời giải của bài toán gốc, sau đó sử dụng một giao thức chứng minh kiến thức không tiết lộ truyền thống để chứng minh rằng bạn có một cách tô màu hợp lệ mà không tiết lộ cách tô đó. Một bài viết tuyệt vời năm 2014 của Matthew Green giải thích chi tiết về điều này.
Thứ khó khăn hơn nhiều làtính súc tích. Trực giác mà nói, việc chứng minh ngắn gọn các phép tính rất khó vì bản thân các phép tính cực kỳ mong manh. Nếu bạn có một phép tính dài và phức tạp, và giả sử bạn có khả năng thay đổi bất kỳ bit nào từ 0 thành 1 ở giữa quá trình tính toán, thì trong nhiều trường hợp, chỉ cần thay đổi một bit duy nhất cũng đủ để khiến kết quả tính toán hoàn toàn khác biệt. Do đó, thật khó hình dung làm cách nào để xác minh tính đúng đắn bằng cách lấy mẫu ngẫu nhiên dọc theo hành trình tính toán, bởi vì bạn rất dễ bỏ lỡ “bit ác độc” (“one evil bit”) đó. Tuy nhiên, thông qua một số phương pháp toán học tinh vi, có thể chứng minh rằng bạn thực sự có thể làm được điều này.
Trực giác cấp cao chung là giao thức có thể đạt được điều này nhờ sử dụng toán học tương tự như trong kỹ thuật mã hóa sửa lỗi (erasure coding), vốn thường được dùng để làm cho dữ liệu chống chịu lỗi. Nếu bạn có một tập dữ liệu và mã hóa nó thành một đường thẳng, rồi chọn ra bốn điểm trên đường thẳng đó. Bất kỳ hai điểm nào trong bốn điểm này cũng có thể tái tạo lại đường thẳng, do đó cũng suy ra hai điểm còn lại. Hơn nữa, nếu bạn thay đổi rất nhỏ dữ liệu ban đầu, ít nhất ba trong số bốn điểm sẽ thay đổi. Bạn có thể mở rộng ý tưởng này: mã hóa dữ liệu thành một đa thức bậc 1.000.000, sau đó chọn 2.000.000 điểm trên đa thức đó; bất kỳ 1.000.001 điểm nào cũng có thể phục hồi dữ liệu gốc và từ đó suy ra các điểm còn lại, và bất kỳ thay đổi nhỏ nào ở dữ liệu gốc cũng sẽ làm thay đổi ít nhất 1.000.000 điểm. Thuật toán được trình bày ở đây tận dụng mạnh mẽ phương pháp này thông qua các đa thức nhằm khuếch đại sai số.
Một ví dụ đơn giản
Giả sử bạn muốn chứng minh rằng bạn có một đa thức P sao cho với mọi x từ 1 đến 1 triệu, P(x) là một số nguyên và 0 <= P(x) <= 9. Đây là một ví dụ đơn giản về “kiểm tra phạm vi” (range check) rất phổ biến. Bạn có thể hình dung loại kiểm tra này giống như việc xác minh rằng sau khi thực hiện một giao dịch, số dư tài khoản vẫn dương. Nếu 1 <= P(x) <= 9, nó có thể là một phần của việc kiểm tra nghiệm Sudoku hợp lệ.
Phương pháp “truyền thống” để chứng minh bài toán này là duyệt qua cả 1.000.000 điểm và kiểm tra từng giá trị. Nhưng chúng ta muốn biết liệu có thể xây dựng một bằng chứng có thể được xác minh trong ít hơn 1.000.000 bước hay không. Việc đơn giản lấy mẫu ngẫu nhiên vài giá trị P sẽ không hiệu quả; luôn tồn tại khả năng một kẻ cung cấp bằng chứng gian lận sẽ nghĩ ra một P thỏa mãn ràng buộc tại 999.999 vị trí nhưng vi phạm tại vị trí cuối cùng, và việc lấy mẫu ngẫu nhiên vài giá trị sẽ luôn bỏ lỡ điểm sai đó. Vậy ta nên làm gì?
Hãy chuyển đổi bài toán sang dạng toán học. Gọi C(x) là một đa thức kiểm tra ràng buộc (constraint checking polynomial), sao cho C(x) = 0 nếu 0 <= x <= 9, và khác 0 trong các trường hợp còn lại. Một cách đơn giản để xây dựng C(x) là: x * (x-1) * (x-2) * ... * (x-9).
Bây giờ, bài toán trở thành: chứng minh rằng bạn biết P sao cho C(P(x)) = 0 với mọi x từ 1 đến 1.000.000. Đặt Z(x) = (x-1) * (x-2) * ... * (x-1000000). Đây là một sự thật toán học đã biết: mọi đa thức bằng 0 tại tất cả các điểm từ 1 đến 1.000.000 đều là bội số của Z(x). Vì vậy, bài toán có thể được chuyển đổi lần nữa: chứng minh rằng bạn biết P và D sao cho C(P(x)) = Z(x) * D(x) với mọi x (lưu ý rằng nếu bạn biết C(P(x)) hợp lệ, thì việc chia cho Z(x) để tính D(x) không quá khó; bạn dùng phép chia đa thức hoặc thuật toán nhanh hơn dựa trên biến đổi Fourier nhanh). Bây giờ, ta đã chuyển đổi mệnh đề ban đầu thành một bài toán rõ ràng hơn về mặt toán học và dễ chứng minh hơn.
Vậy thì, làm thế nào để chứng minh? Ta có thể hình dung quá trình chứng minh như một cuộc trao đổi ba bước giữa người chứng minh và người xác minh:
- Người chứng minh gửi một số thông tin
- Sau đó người xác minh gửi một số yêu cầu
- Sau đó người chứng minh gửi thêm một số thông tin
Đầu tiên, người chứng minh nộp (tức là, tạo một cây Merkle và gửi root hash tới người xác minh) các giá trị P(x) và D(x) với mọi x từ 1 đến 1 tỷ (vâng, 1 tỷ). Trong đó có 1 triệu điểm thỏa mãn 0 <= P(x) <= 9 và 999 triệu điểm còn lại có thể nằm ngoài điều kiện.
Ta giả sử người xác minh đã biết trước các giá trị Z(x) tại tất cả các điểm này; trong sơ đồ này, Z(x) giống như một khóa xác minh công khai, mọi người đều phải biết trước (khách hàng không lưu trữ toàn bộ Z(x) do chiếm nhiều dung lượng, mà chỉ lưu root Merkle của Z(x), và yêu cầu người chứng minh cung cấp đồng thời các nhánh Merkle cho mỗi giá trị Z(x) cần truy vấn; hoặc, với mỗi x, có thể có một cách tính toán rất đơn giản trên Z(x)). Sau khi nhận được cam kết (tức là root Merkle), người xác minh chọn ngẫu nhiên 16 giá trị x trong khoảng từ 1 đến 1 tỷ, và yêu cầu người chứng minh cung cấp các nhánh Merkle tương ứng với P(x) và D(x) tại các điểm đó. Người chứng minh cung cấp các giá trị này, và người xác minh kiểm tra:
-
Các nhánh khớp với root Merkle đã cung cấp trước đó
-
C(P(x)) bằng Z(x) * D(x) trong cả 16 trường hợp
Ta biết rằng bằng chứng này đảm bảotính đầy đủ— nếu bạn thực sự biết một P(x) phù hợp, và bạn tính D(x) và xây dựng bằng chứng đúng cách, thì cả 16 kiểm tra sẽ đều thành công. Nhưng còntính đáng tin cậythì sao?
Tức là, nếu một kẻ cung cấp bằng chứng gian lận đưa ra một P(x) xấu, xác suất thấp nhất mà họ bị phát hiện là bao nhiêu? Ta có thể phân tích như sau: vì C(P(x)) là một đa thức bậc 1.000.000, bậc của nó tối đa là 10.000.000.
Thông thường, ta biết rằng hai đa thức bậc N khác nhau sẽ cắt nhau tại tối đa N điểm. Do đó, một đa thức bậc 1.000.000 và bất kỳ đa thức nào luôn bằng Z(x) * D(x), nếu khác nhau, sẽ khác biệt tại ít nhất 990.000.000 điểm. Vì vậy, ngay cả khi chỉ kiểm tra một lần, xác suất phát hiện một P(x) xấu đã là 99%, và với 16 lần kiểm tra, xác suất phát hiện tăng lên 1 - 10^-32. Nói cách khác, việc lừa dối sơ đồ này khó ngang với việc tạo va chạm hàm băm.
Vậy thì, ta vừa phân tích điều gì? Chúng ta đã sử dụng các đa thức để “khuếch đại” lỗi trong mọi lời giải sai, biến một bài toán kiểm tra trực tiếp một triệu lần thành một giao thức xác minh, nơi chỉ cần một lần kiểm tra cũng có thể phát hiện lỗi với xác suất 99%.
Chúng ta có thể chuyển cơ chế ba bước này thành một bằng chứng phi tương tác (non-interactive proof), tức là người chứng minh có thể phát sóng nó và tất cả mọi người đều có thể xác minh. Người chứng minh trước tiên xây dựng cây Merkle cho các giá trị P(x) và D(x), sau đó tính root hash của cây. Chính root này sau đó được dùng làm nguồn entropy để quyết định nhánh nào của cây mà người chứng minh cần cung cấp. Người chứng minh sau đó phát sóng root cây Merkle cùng các nhánh như một bằng chứng. Toàn bộ quá trình tính toán đều do bên người chứng minh thực hiện. Việc tính root cây Merkle từ dữ liệu, rồi dùng root đó để chọn các nhánh cần kiểm toán, một cách hiệu quả đã thay thế nhu cầu về một người xác minh tương tác.
Đối với một kẻ cung cấp bằng chứng gian lận không có P(x) hợp lệ, điều duy nhất họ có thể làm là cố gắng liên tục xây dựng một bằng chứng hợp lệ cho đến khi may mắn tìm được một root cây Merkle mà các nhánh được chọn có thể vượt qua kiểm tra. Tuy nhiên, do tính đáng tin cậy là 1 – 10^-32 (tức là, với một bằng chứng giả cho trước, xác suất không vượt qua kiểm tra ít nhất là 1-10^-32), điều này có thể khiến kẻ gian lận phải mất hàng tỷ năm để tìm được một bằng chứng vượt qua kiểm tra.
Khám phá sâu hơn
Để minh họa sức mạnh của kỹ thuật này, hãy dùng nó để làm một điều bất thường: chứng minh rằng bạn biết số Fibonacci thứ một triệu. Để làm điều này, ta sẽ chứng minh rằng bạn biết một đa thức biểu diễn dải tính toán, trong đó P(x) biểu diễn số Fibonacci thứ x. Đa thức kiểm tra ràng buộc bây giờ sẽ trải rộng trên 3 tọa độ x: C(x1, x2, x3) = x3 - x2 - x1 (lưu ý rằng, với mọi x, nếu C(P(x), P(x+1), P(x+2)) = 0 thì P(x) biểu diễn một dãy Fibonacci).
-Fibonacci-
Bài toán sau khi chuyển đổi trở thành: xác minh rằng bạn biết P và D sao cho C(P(x), P(x+1), P(x+2)) = Z(x) * D(x). Với mỗi trong 16 trường hợp kiểm toán bằng chứng, người chứng minh cần cung cấp các nhánh Merkle cho P(x), P(x+1), P(x+2) và D(x). Người chứng minh cũng cần cung cấp thêm các nhánh Merkle để chứng minh rằng P(0) = P(1) = 1. Ngoài ra, toàn bộ quy trình vẫn giữ nguyên.
Bây giờ, để triển khai thực tế, ta cần giải quyết hai vấn đề. Thứ nhất, nếu muốn áp dụng thực tế với các con số thông thường, thì phương án này chưa hiệu quả do các con số đó có thể trở nên cực lớn. Ví dụ, số Fibonacci thứ một triệu có tới 208.988 chữ số. Nếu thực sự muốn đạt được tính súc tích trong thực tiễn, ta cần làm việc không phải trên các số bình thường mà là trên các trường hữu hạn (finite field)— tức là một hệ thống số vẫn tuân theo các quy tắc toán học như a * (b+c) = (a*b) + (a*c) và (a^2 - b^2) = (a-b) * (a+b), nhưng mỗi số trong hệ thống này được đảm bảo chỉ chiếm một không gian hằng số. Việc chứng minh số Fibonacci thứ một triệu sẽ cần một thiết kế phức tạp hơn, nơi thực hiện các phép tính số lớn trên nền tảng toán học trường hữu hạn.
Trường hữu hạn đơn giản và phổ biến nhất là toán học modulo. Tức là, với một số nguyên tố N, thay mỗi a + b bằng a + b mod N. Áp dụng tương tự cho phép trừ và nhân, còn phép chia thì dùng nghịch đảo modulo (ví dụ, nếu n = 7, thì 3 + 4 = 0, 2 + 6 = 1, 3 * 4 = 5, 4 / 2 = 2, 5 / 2 = 6). Bạn có thể tìm hiểu thêm về các hệ thống số này tại đây(tìm trong trang từ khóa “prime field”), nơi tôi đã giới thiệu đôi chút về trường số nguyên tố. Hoặc tìm hiểu từ mục Wikipedia về toán học modulo(trong bài tìm trực tiếp “finite fields” và “prime fields”, có vẻ rất phức tạp và liên quan đến đại số trừu tượng, nhưng đừng lo lắng về điều đó).
Thứ hai, bạn có thể đã nhận thấy rằng trong phần phác thảo chứng minh tính đáng tin cậy phía trên, tôi đã bỏ qua một kiểu tấn công: kẻ tấn công thay vì cung cấp các giá trị P(x) khoảng 1.000.000 lần và D(x) khoảng 9.000.000 lần, lại gửi các giá trị khác không đến từ bất kỳ đa thức bậc thấp nào? Khi đó, một tham số C(P(x)) không hợp lệ phải khác biệt với mọi C(P(x)) hợp lệ tại ít nhất 990 triệu điểm không hợp lệ, do đó có thể có nhiều kiểu tấn công hiệu quả hơn. Ví dụ, một kẻ tấn công có thể sinh một giá trị ngẫu nhiên p cho mỗi x, tính d = C(p) / Z(x), rồi gửi các giá trị này thay thế P(x) và D(x). Các giá trị này sẽ không dựa trên bất kỳ đa thức bậc thấp nào, nhưngchúngsẽ vượt qua kiểm tra.
Hóa ra, mặc dù các công cụ sử dụng có thể khá phức tạp, nhưng khả năng này vẫn có thể được ngăn chặn hiệu quả, và hiện nay bạn có thể khẳng định một cách có trách nhiệm rằng chúng thực sự lấp đầy khoảng trống đổi mới toán học trong STARKs. Tuy nhiên, giải pháp này cũng có một hạn chế: mặc dù bạn có thể loại bỏ các cam kết dữ liệu khác xa một đa thức bậc 1.000.000 (ví dụ, bạn cần thay đổi 20% toàn bộ giá trị để biến nó thành một đa thức bậc 1.000.000), nhưng bạn không thể loại trừ các đa thức chỉ khác nhau một hoặc hai tọa độ. Do đó, các công cụ này sẽ cung cấpbằng chứng gần đúng (proof of proximity)— chứng minh rằng phần lớn các điểm trên P và D đều liên quan đến một đa thức như vậy.
Do đó, mặc dù có hai “vấn đề phát sinh (catches)”, nhưng việc xây dựng một bằng chứng vẫn là đủ. Thứ nhất, người xác minh cần kiểm tra thêm một vài trường hợp để bù đắp cho sai số do giới hạn này gây ra. Thứ hai, nếu chúng ta đang thực hiện “kiểm tra ràng buộc biên giới (boundary constraint checking)” (ví dụ, chứng minh trong ví dụ Fibonacci ở trên rằng P(0) = P(1) = 1), thì chúng ta cần mở rộng bằng chứng gần đúng để không chỉ chứng minh rằng phần lớn các điểm nằm trên cùng một đa thức, mà còn chứng minh rằng hai điểm cụ thể này (hoặc bất kỳ số điểm nào bạn muốn kiểm tra) thực sự nằm trên đa thức đó.
Trong phần tiếp theo của loạt bài này, tôi sẽ tiếp tục phân tích giải pháp cho vấn đề kiểm tra gần đúng.
Chào mừng tham gia cộng đồng chính thức TechFlow
Nhóm Telegram:https://t.me/TechFlowDaily
Tài khoản Twitter chính thức:https://x.com/TechFlowPost
Tài khoản Twitter tiếng Anh:https://x.com/BlockFlow_News
@VitalikButerin
