Một lần, hàng xóm của tôi gọi tôi sang nếm một nồi phở. Chỉ một muỗng là đủ để biết nước dùng có ngon hay không – dù nồi đó chứa một lít hay một trăm lít. Nhưng để nấu ra nước dùng đó phải mất nhiều giờ. Đó chính là câu chuyện của zero-knowledge proof tóm lại trong một câu: proving time zk thì dài, còn xác minh thì gần như tức thì. Trong bài viết này, chúng ta sẽ đào sâu vì sao tạo ra một zk proof thì chậm mà kiểm tra nó lại nhanh đến kinh ngạc – và vì sao sự bất đối xứng này là trái tim của việc mở rộng blockchain như zk-rollups.
Hình 1: Đầu bếp (prover) vs người nếm (verifier) — sự bất đối xứng
Hai vai diễn trong một vở kịch
Mỗi zero-knowledge proof có hai phía:
- Prover – đầu bếp. Bên này thực hiện một phép tính rất nặng để tạo ra một bằng chứng cho thấy một tuyên bố là đúng, mà không tiết lộ bí mật bên trong.
- Verifier – người nếm thử. Bên này nhận bằng chứng và chỉ cần vài bước toán nhẹ để xác nhận "đúng" hoặc "sai".
Trong ví dụ về phở: prover là đầu bếp, verifier là người nếm. Nấu ăn mất thời gian; nếm chỉ mất một giây. Nồi càng to, nấu càng lâu – nhưng một muỗng luôn mất đúng một giây.
Khoảng cách này không phải tình cờ. Đó là một thiết kế có chủ đích. Chi phí nặng được trả một lần (khi tạo bằng chứng) để hàng triệu người khác chỉ phải trả gần như không gì (khi họ xác minh). Đây chính là lý do nền kinh tế zk-rollups vận hành: một máy trả chi phí cao để chứng minh cả một lô giao dịch, còn mỗi node trên blockchain chỉ cần xác minh một bằng chứng nhỏ.
Tại sao proving time của ZK lại lâu đến vậy
Bước 1: Chuyển phép tính thành một circuit
Đầu tiên, phép tính cần chứng minh được dịch thành một circuit – một mạng các phép tính cơ bản (cộng, nhân) gọi là constraints. Một phép tính tài chính phức tạp có thể cần tới một triệu constraints. Đây là nơi công thức được viết ra: càng nhiều nguyên liệu, công thức càng dài.
Bước 2: Tạo witness
Prover chạy circuit với dữ liệu bí mật để tạo ra một witness – tất cả các giá trị trung gian của phép tính. Về bản chất, bước này thực thi lại chính phép tính đó. Nó rẻ hơn một chút so với proving đầy đủ, nhưng vẫn là công việc thực sự.
Bước 3: Biến đổi Fourier (FFT / NTT)
Tại đây phép thuật toán học bắt đầu. Circuit được biểu diễn dưới dạng các polynomial, và để làm việc với polynomial hiệu quả, prover phải chạy Number Theoretic Transform (NTT) – một người anh em rời rạc của biến đổi Fourier. Với circuit một triệu constraints, mỗi NTT xử lý hàng triệu điểm dữ liệu. FFT/NTT chiếm một phần lớn tổng proving time – và khi bước MSM dưới đây đã tối ưu, NTT thường trở thành chi phí lớn nhất còn lại.
Bước 4: MSM – kẻ ngốn thời gian số một
Multi-Scalar Multiplication (MSM) nhân hàng triệu scalar 256-bit với các điểm trên đường cong elip, rồi cộng tất cả lại. Đây là bước chậm nhất trong toàn bộ pipeline. Theo báo cáo nghiên cứu DistMSM (ACM 2024), MSM chiếm khoảng 78,2% khối lượng công việc tạo bằng chứng. Trong các hệ thống sản xuất (Bellperson của Zcash), MSM cộng NTT chiếm khoảng 90% thời gian.
Vì sao MSM chậm đến vậy? Vì mỗi phép cộng điểm trên đường cong elip 256-bit (hoặc 377-bit) là một chuỗi dài các phép số học trên trường hữu hạn. Hàng triệu phép cộng như vậy không thể song song hóa hoàn toàn – ngay cả khi thuật toán Pippenger giảm số phép nhân, tổng thời gian vẫn lớn.
Kết quả: với một circuit trung bình, proving mất từ vài giây đến vài phút trên CPU. GPU chuyên dụng có thể rút xuống còn vài giây, nhưng không bao giờ là "tức thì".
Còn polynomial commitments thì sao?
Trước khi tiếp tục, có một khái niệm gắn kết tất cả các bước: polynomial commitment. Sau khi phép tính trở thành polynomial, prover phải commit (cam kết) với chúng để verifier có thể kiểm tra các tuyên bố cụ thể mà không cần đọc lại toàn bộ phép tính. Hai họ chiếm ưu thế:
- KZG commitments (được dùng bởi Groth16, PLONK và hầu hết SNARK) ràng một polynomial vào một giá trị ngắn duy nhất bằng pairings. Chúng tạo bằng chứng rất nhỏ, nhưng cần một trusted setup cung cấp điểm đánh giá bí mật.
- FRI-based commitments (được dùng bởi STARK) cam kết với các giá trị của polynomial bằng một Merkle tree. Không cần trusted setup, nhưng bằng chứng lớn hơn nhiều.
Chi phí commitment là một lý do nữa khiến prover chậm – đặc biệt với KZG, nơi prover chạy thuật toán mở (opening) nặng MSM. Ngược lại, verifier chỉ chạm vào commitment ở cuối cùng, bên trong vài phép kiểm tra pairing.
Hình 2: Bên trong prover — proving time đi về đâu
Vì sao xác minh nhanh đến mức gây sốc
Giờ đến vai trò của người nếm. Verifier không chạy lại phép tính. Nó chỉ kiểm tra vài đồng nhất thức đại số – pairings – được dựng từ bằng chứng và một verification key công khai.
Với Groth16 (SNARK phổ biến nhất):
- Bằng chứng chỉ gọn trong 192 byte (3 điểm trên đường cong elip).
- Xác minh chỉ cần 3 phép pairing.
- Thời gian xác minh về cơ bản là hằng số (constant), bất kể circuit lớn đến đâu. Đây là khác biệt lớn nhất so với STARK, nơi xác minh tăng theo hàm đa-logarit (polylogarithmic) với kích thước phép tính – vẫn rất nhanh, nhưng không phải hằng số.
Trên phần cứng thông thường, xác minh Groth16 mất khoảng 3-5 milliseconds. Trên Ethereum, một lần xác minh Groth16 tốn khoảng 200.000-250.000 gas – rất nhỏ so với việc chạy lại phép tính gốc on-chain. Điều này nhờ EIP-1108, giúp giảm chi phí precompile alt_bn128 (mỗi phép pairing giờ tốn 34.000 gas), có hiệu lực từ 2019.
Nói cách khác, verifier không "chấm lại bài thi" bằng cách giải lại. Nó cầm answer key (verification key) và kiểm tra vài bước ngắn để chắc chắn bài thi không bị làm giả.
Hình 3: Bên trong verifier — vì sao zk verification nhanh đến vậy
Độ phức tạp – hai đường rẽ hai ngả
Hãy phóng to bằng lý thuyết độ phức tạp:
- Prover: thời gian tăng tuyến tính theo kích thước circuit – O(n). Nếu circuit tăng 10 lần, proving time tăng khoảng 10 lần, cộng thêm các hằng số lớn từ MSM và NTT.
- Verifier (SNARK): thời gian là hằng số – O(1). Một circuit 100.000 constraints và một circuit 10.000.000 constraints đều xác minh trong vài milliseconds.
- Verifier (STARK): thời gian tăng theo O(log n) – chậm hơn nhiều so với bất kỳ tăng trưởng tuyến tính nào, nhưng không phải hằng số.
Một ví dụ cụ thể – một circuit 1.000.000 constraints:
| Kích thước circuit | Thời gian chứng minh (CPU) | Thời gian xác minh |
|---|---|---|
| 100.000 constraints | ~1-3 giây | ~3-5 ms |
| 1.000.000 constraints | ~30 giây - 2 phút | ~3-5 ms |
| 10.000.000 constraints | ~10-30 phút (cần GPU) | ~3-5 ms |
Đường proving time leo dốc đứng; đường xác minh vẫn phẳng lì. Đó là lý do zk-rollups có thể tuyên bố "scale": chúng đẩy chi phí dốc ra ngoài chuỗi (về phía prover) và chỉ giữ phần phẳng (xác minh) on-chain.
Hình 4: Mở rộng — proving tăng, verification giữ phẳng
Vì sao sự bất đối xứng này quan trọng
1. Zk-rollups: nấu một nồi lớn, thử một thìa
Trong zk-rollup, đầu bếp (một prover tập trung hoặc một mạng prover) thu thập hàng nghìn giao dịch, gộp chúng thành lô và tạo một bằng chứng cho cả lô. Việc đó có thể mất vài phút. Nhưng trên Ethereum, một lần xác minh – vài giây và ~200k gas – xác nhận toàn bộ lô. Khối lượng tính toán được "nén" vào một bằng chứng nhỏ.
2. Điện thoại: có thể nếm, không thể nấu
Điện thoại thông minh có thể xác minh một zk proof trong vài milliseconds mà pin gần như không sụt. Nhưng tạo ra một bằng chứng cho circuit lớn trên điện thoại là không thực tế – mất vài phút đến vài giờ và ngốn pin rất nhanh. Vì vậy các hệ thống di động hiện đại dùng proving networks: máy chủ tạo bằng chứng thay mặt người dùng, điện thoại chỉ đóng vai verifier. Client-side proving chỉ khả thi với các circuit rất nhỏ.
3. Lịch sử: cuộc chiến với hai kẻ ngốn thời gian
Từ 2016 đến 2024, proving time giảm từ phút xuống milliseconds trong nhiều hệ thống. Chuyện gì đã xảy ra? Cộng đồng tấn công đúng hai nút thắt: MSM (cải tiến Pippenger, song song hóa 4 hướng) và FFT/NTT (batching, pipelining). Đây là bằng chứng rõ ràng rằng proving chậm không phải định luật bất biến – nó đang bị đẩy lùi mỗi năm.
4. Prover networks: thuê nhà bếp
Vì công việc của đầu bếp quá nặng, cả một ngành ra đời để cho thuê nhà bếp. Prover networks (chợ chứng minh phân tán) chia một circuit khổng lồ thành nhiều phần trên nhiều máy, mỗi máy tính một phần, rồi ráp lại bằng chứng cuối cùng. Chúng tồn tại chính xác vì tính bất đối xứng: xác minh rẻ nên ai cũng có thể xác nhận một bằng chứng do một mạng không hoàn toàn tin cậy tạo ra – miễn là bằng chứng đó đúng đắn. Nếu proving rẻ như xác minh, thị trường này sẽ không bao giờ hình thành.
Hỏi đáp
Q: Tại sao proving time zk không thể đạt tốc độ xác minh? A: Vì prover phải thực thi toàn bộ phép tính (witness generation), chạy biến đổi Fourier (FFT/NTT) và thực hiện hàng triệu phép nhân điểm trên đường cong elip (MSM) – khối lượng công việc tỷ lệ với kích thước circuit. Verifier chỉ kiểm tra vài đồng nhất thức dựng sẵn (pairings), nên thời gian gần như là hằng số.
Q: "Zk proof performance" thực sự nghĩa là gì? A: "Zk proof performance" đề cập đến sự đánh đổi giữa chi phí tạo bằng chứng và chi phí xác minh. Một hệ thống hiệu năng cao chọn đúng điểm cân bằng: bằng chứng đủ nhỏ, proving đủ nhanh cho môi trường chạy prover, và xác minh đủ rẻ cho môi trường chạy verifier – đặc biệt là on-chain.
Q: Xác minh on-chain tốn bao nhiêu gas? A: Với Groth16 trên Ethereum, khoảng 200.000-250.000 gas (nhờ EIP-1108). Bằng chứng STARK lớn hơn và tốn tới khoảng 5 triệu gas để xác minh on-chain – đó là lý do nhiều hệ thống "bọc" STARK trong SNARK (STARK-to-SNARK) để trả hóa đơn nhỏ hơn.
Q: Điện thoại có thể tạo ra zk proof không? A: Về nguyên tắc là có, nhưng chỉ với circuit rất nhỏ. Với circuit lớn, thời gian và pin khiến điều này không thực tế. Trong thực tế người ta dùng proving networks – máy chủ tạo bằng chứng, thiết bị chỉ xác minh.
Q: Nếu xác minh nhanh vậy, sao không dùng ZK cho mọi thứ? A: Vì chi phí nằm ở phía prover. Mỗi khi có dữ liệu mới cần chứng minh, bạn phải trả chi phí proving từ đầu. Với hệ thống hàng nghìn giao dịch mỗi giây, chi phí proving là vấn đề hạ tầng nghiêm trọng – chính là lý do proving networks và GPU farms tồn tại.
Tóm tắt
Một zero-knowledge proof là một vở kịch hai vai: đầu bếp (prover) dốc sức nấu một nồi bằng chứng, và người nếm (verifier) chỉ cần một thìa để đánh giá. Proving time zk tăng theo kích thước phép tính – chủ yếu do MSM (~78%) và FFT/NTT – trong khi xác minh gần như không đổi. Sự bất đối xứng này là nền tảng của zk-rollups, của blockchain scaling, và của mô hình "nấu một lần, mọi người cùng thưởng thức". Hiểu nó, bạn sẽ hiểu vì sao ZK không chỉ là toán học – nó là một kiến trúc kinh tế.