- Zero-knowledge proof cho phép chứng minh một tuyên bố là đúng mà không tiết lộ thông tin gì về bằng chứng
- 3 tính chất: Completeness (prover honest luôn prove được), Soundness (prover dishonest không thể fake proof), Zero-knowledge (verifier không học được gì ngoài "tuyên bố đúng")
- zk-SNARKSuccinct Non-interactive ARgument of Knowledge: ZK proof nhỏ gọn, verify <1ms. Cần trusted setupNghi thức khởi tạo một lần cho zk-SNARK: nhiều bên generate tham số và xóa secret. An toàn nếu ít nhất 1 bên honest. Không cần cho zk-STARK. ban đầu (Groth16, PLONK).: proof nhỏ, verify nhanh, cần trusted setup, không quantum-resistant
- zk-STARKScalable Transparent ARgument of Knowledge: ZK proof không cần trusted setup, kháng lượng tử. Proof lớn hơn SNARK nhưng trustless.: proof lớn hơn, không cần trusted setup, quantum-resistant nhờ dùng hash function
- ZK-KYC: dùng ZK để prove "tôi pass KYC" mà không tiết lộ identity thật với verifier
- Circuit bugs là attack surface thực tế nguy hiểm nhất — không phải toán học ZK bị phá
1. Ba Tính Chất Cốt Lõi Của Zero-Knowledge Proof
Zero-knowledge proof được định nghĩa bởi Goldwasser, Micali và Rackoff năm 1985 — một trong những công trình nền tảng của cryptography hiện đại. Một ZK proof hợp lệ phải thỏa mãn đúng 3 tính chất sau:
Completeness (Đầy đủ)
Nếu tuyên bố là đúng và prover biết witness (bằng chứng), prover luôn luôn có thể thuyết phục verifier chấp nhận. Không có false negative — prover honest không bị reject.
Ví dụ thực tế: Nếu bạn thực sự có credential hợp lệ từ issuer tin cậy, bạn luôn có thể tạo proof hợp lệ. System không bao giờ reject người đúng vì lý do kỹ thuật.
Soundness (Tính vững chắc)
Nếu tuyên bố là sai, prover không thể thuyết phục verifier chấp nhận — trừ khi với xác suất rất nhỏ (negligible probability). Đây là tính chất bảo vệ verifier khỏi bị lừa.
Có hai mức soundness: computational soundness (an toàn với adversary có tính toán hữu hạn — đủ cho thực tế) và statistical soundness (an toàn tuyệt đối dù adversary có vô hạn tính toán — mạnh hơn nhưng khó đạt được).
Zero-Knowledge (Không rò rỉ thông tin)
Verifier không học được bất kỳ thông tin gì về witness ngoài việc "tuyên bố là đúng". Formally, mọi thứ verifier có thể tính toán từ proof đều có thể simulate được mà không cần witness thật.
Đây là tính chất khó nhất để chứng minh và implement đúng. Trong thực tế, "zero-knowledge" thường là computational zero-knowledge — nghĩa là safe với adversary có tính toán hữu hạn.
// Ví dụ trực quan: Hang Ali Baba
// Prover muốn prove họ biết mật khẩu của cánh cửa bí mật
// mà không tiết lộ mật khẩu đó
Round 1:
- Prover vào hang, chọn một trong hai đường (A hoặc B) ngẫu nhiên
- Verifier đến cửa hang, yêu cầu prover ra đường X (X random)
If prover biết mật khẩu:
- Luôn có thể ra đúng đường X được yêu cầu
- Xác suất đoán may mắn: 1/2 mỗi round
After k rounds:
- Xác suất fake thành công = (1/2)^k
- k = 30 → xác suất fake ≈ 1 tỷ phần 1
Ba tính chất (Completeness, Soundness, Zero-knowledge) phải đủ cả ba — thiếu một là không phải ZK proof hợp lệ. Soundness bảo vệ verifier khỏi bị lừa. Zero-knowledge bảo vệ prover. Completeness bảo vệ honest user khỏi false rejection.
2. Interactive vs Non-Interactive ZK Proof
ZK proof ban đầu là interactive — prover và verifier phải giao tiếp qua lại nhiều round (như ví dụ hang Ali Baba). Điều này không thực tế cho blockchain và internet vì:
- Cần kết nối real-time giữa hai bên
- Không thể verify proof sau khi conversation kết thúc
- Không thể share proof với nhiều verifier
Fiat-Shamir Heuristic — Chuyển sang Non-Interactive
Năm 1986, Fiat và Shamir đề xuất một transformation quan trọng: thay vì verifier gửi random challenge, prover tự tính challenge bằng cách hash các message trước đó. Điều này biến interactive proof thành non-interactive proof (NIZK).
Fiat-Shamir: challenge = Hash(statement || message₁ || message₂ || ...)
Proof có thể verify bởi bất kỳ ai, bất kỳ lúc nào, mà không cần prover online. Đây là nền tảng của mọi ZK proof dùng trên blockchain.
zk-SNARK và zk-STARK đều là NIZK
Cả hai đều là non-interactive zero-knowledge proof. Sự khác biệt nằm ở cách construct proof, security assumption và trade-off hiệu năng — không phải ở việc interactive hay không.
Interactive proof cần verifier online liên tục — không thực tế. Non-interactive (Fiat-Shamir) là standard thực tế. SNARK/STARK đều là non-interactive ZK proof, khác nhau ở trade-off kích thước vs trusted setup.
3. zk-SNARK — Succinct Non-Interactive ARgument of Knowledge
zk-SNARK là loại ZK proof phổ biến nhất hiện nay, dùng trong Zcash, Ethereum zkEVM, Tornado Cash, và nhiều ZK identity system. "Succinct" có nghĩa là proof rất nhỏ và verify rất nhanh — dù computation cần prove có thể rất lớn.
Cấu trúc cơ bản của zk-SNARK
Một SNARK system gồm 3 bước:
- Setup: Tạo proving key (pk) và verification key (vk) từ circuit và trusted randomness
- Prove: Prover dùng pk + witness → tạo proof π
- Verify: Verifier kiểm tra Verify(vk, statement, π) → true/false
Trusted Setup — Điểm yếu của SNARK
Trusted setup tạo ra một cặp số bí mật (toxic waste) — nếu bị lộ, kẻ tấn công có thể tạo fake proof cho bất kỳ tuyên bố nào. Giải pháp là Multi-Party Computation (MPC) ceremony: nhiều người tham gia, mỗi người thêm randomness của mình vào, sau đó xóa đi. Chỉ cần 1 người honest là đủ safe.
Các proving system SNARK phổ biến
| System | Proof Size | Prover Time | Verify Time | Trusted Setup |
|---|---|---|---|---|
| Groth16 | ~200 bytes | Trung bình | Rất nhanh | Per-circuit |
| PLONK | ~400 bytes | Trung bình | Nhanh | Universal |
| Marlin | ~600 bytes | Trung bình | Nhanh | Universal |
| Nova | Nhỏ | Rất nhanh | Trung bình | Cần |
Quantum Risk: zk-SNARK dựa trên elliptic curve pairing — một quantum computer đủ mạnh (chạy Shor's algorithm) có thể phá vỡ security assumption này. Đây là lý do STARK ra đời.
zk-SNARK: nhỏ (<300 bytes), verify <1ms, nhưng cần trusted setup → Groth16 là tiêu chuẩn. zk-STARK: không cần trusted setup, kháng lượng tử, nhưng proof lớn hơn. Chọn dựa trên: trustless là ưu tiên tuyệt đối hay performance là ưu tiên?
4. zk-STARK — Scalable Transparent ARgument of Knowledge
zk-STARK được phát triển bởi StarkWare (Eli Ben-Sasson và team), giải quyết hai vấn đề lớn của SNARK: trusted setup và quantum resistance.
Cơ chế hoạt động của STARK
STARK không dùng elliptic curve pairing — thay vào đó dùng hash function và polynomial commitment thông qua giao thức FRI (Fast Reed-Solomon Interactive Oracle Proof).
// STARK high-level flow
1. Execution Trace:
Computation → biểu diễn thành bảng (trace) các bước tính toán
2. Arithmetization:
Trace → polynomial constraints
(mỗi bước computation = một polynomial equation)
3. FRI Protocol:
Prove rằng polynomial đúng mà không tiết lộ
Dùng: hash function + Merkle tree + random sampling
4. Output: STARK proof
Verifier check Merkle proofs + polynomial evaluations
Tại sao STARK quantum-resistant?
Security của STARK dựa trên collision resistance của hash function (SHA-256, Poseidon, Rescue). Không có quantum algorithm nào hiện tại phá được collision resistance hiệu quả — Grover's algorithm chỉ giảm security từ 256-bit xuống 128-bit, vẫn đủ an toàn với các hash function hiện tại.
Ngược lại, SNARK dựa trên discrete logarithm problem trên elliptic curve — Shor's algorithm có thể giải quyết điều này với quantum computer đủ mạnh.
Trade-off của STARK
- Proof size: ~40–200KB — lớn hơn SNARK 100–500 lần
- Không trusted setup: Transparent, mọi người có thể audit
- Prover time: Nhanh hơn SNARK khi computation lớn (zkVM)
- Verify time: Nhanh — polylogarithmic trong size computation
Circuit là attack surface nguy hiểm nhất — không phải toán học ZK. Bug trong constraint logic cho phép adversary tạo proof cho statement sai. Audit circuit nghiêm như audit smart contract — một constraint sai = toàn bộ system sai.
5. SNARK vs STARK — So Sánh Thực Chiến
Không có câu trả lời tuyệt đối. Lựa chọn phụ thuộc vào context:
| Tiêu chí | zk-SNARK | zk-STARK |
|---|---|---|
| Proof size | Nhỏ (~200B–1KB) | Lớn (~40–200KB) |
| On-chain verify cost | Rẻ | Đắt hơn |
| Trusted setup | Cần (Groth16: per-circuit; PLONK: universal) | Không cần — transparent |
| Quantum resistance | Không (elliptic curve) | Có (hash function) |
| Prover speed (large) | Chậm hơn với circuit lớn | Tốt hơn với computation lớn |
| Ecosystem/tooling | Trưởng thành (Circom, Noir) | Phát triển nhanh (Cairo) |
| Use case phù hợp | ZK Identity on-chain, mobile proof | zkRollup, zkVM, long-term quantum-safe |
Rule of thumb: Dùng SNARK khi cần proof nhỏ nhất và verify on-chain rẻ nhất (ZK Identity, ZK-KYC). Dùng STARK khi cần không trusted setup, quantum-resistance, hoặc prove computation rất lớn (zkRollup, zkVM).
ZK Identity flow: Issuer ký claim → User generate ZK proof → Verifier verify proof mà không biết identity thật. NullifierGiá trị hash dùng một lần để ngăn double-vote/double-spend. Như serial number trên tiền — không link về identity gốc. prevent double-use mà không expose identity. Architecture đơn giản, nhưng implementation phải chính xác tuyệt đối.
6. ZK Circuit Design — Từ Statement Đến Proof
Để tạo ZK proof, bạn cần "viết circuit" — một biểu diễn toán học của computation cần prove. Circuit không phải code thông thường — nó là arithmetic constraint system.
Arithmetic Circuit
Mọi computation đều có thể biểu diễn thành circuit với hai loại gate: addition gate và multiplication gate. Kết quả là một hệ phương trình polynomial ràng buộc các wires (input, intermediate values, output).
// Ví dụ circuit đơn giản: prove x biết a,b sao cho a*b = x
// và a,b đều > 0 (không tiết lộ a,b cụ thể)
Circuit constraints:
w1 * w2 = w3 // multiplication gate
w3 = x // output constraint
w1 > 0 // range check
w2 > 0 // range check
Public input: x
Witness (private): a, b
Prove: tôi biết a,b sao cho a*b = x, a > 0, b > 0
// Trong Circom (SNARK circuit language):
template Multiply() {
signal input a;
signal input b;
signal output c;
c <== a * b;
}
R1CS — Rank-1 Constraint System
Groth16 và PLONK sử dụng R1CS — chuẩn hóa circuit thành dạng: A·w ∘ B·w = C·w, trong đó w là vector witness. Mọi constraint đều được flatten về dạng này trước khi generate proof.
Circuit Bugs — Rủi ro thực tế số 1
Lỗi phổ biến nhất trong ZK circuit không phải là toán học bị phá — mà là under-constrained circuit: circuit không ràng buộc đủ để ngăn fake witness. Kẻ tấn công có thể tạo witness hợp lệ về mặt circuit nhưng không tương ứng với computation thực tế.
Ví dụ bug thực tế: Tornadocash-style exploit — circuit check A + B = C nhưng không check A và B phải dương. Kẻ tấn công dùng A âm để "mint" tiền từ không khí. Circuit audit là chuyên môn riêng, khác với smart contract audit.
ZK-KYC là thực tế kỹ thuật: bank verify user một lần, user tự generate proof cho bất kỳ service nào, service không biết user là ai. Privacy-preserving compliance không còn là lý tưởng — là kiến trúc có thể deploy ngay hôm nay.
7. ZK-KYC & ZK Identity — Ứng Dụng Thực Chiến
Đây là ứng dụng quan trọng nhất của ZK proof với identity. Thay vì verifier biết full identity của người dùng, ZK-KYC chỉ tiết lộ đúng và chỉ đúng những gì cần thiết.
Flow ZK-KYC End-to-End
// Bước 1: KYC với trusted issuer (1 lần)
User → Bank/Government → Full KYC verification
Bank issues: Verifiable Credential (VC) với chữ ký digital
VC chứa: name, DOB, nationality, ID number, ...
VC được lưu trong user's wallet (không lên blockchain)
// Bước 2: Tạo ZK proof (mỗi khi cần verify)
User muốn truy cập DeFi protocol cần: "resident VN, đủ 18 tuổi"
ZK circuit inputs:
- Public: issuer_public_key, requirement (age≥18, country=VN)
- Private: VC, VC_signature, user_secret
ZK circuit proves:
1. VC được ký bởi issuer hợp lệ (verify signature)
2. DOB trong VC → age ≥ 18 (tính toán không tiết lộ DOB)
3. Country trong VC = VN (match mà không tiết lộ full address)
4. nullifier = Hash(user_secret || protocol_id) ← chống double-use
Output: proof π (không chứa tên, DOB, ID number thật)
// Bước 3: DeFi protocol verify
Protocol nhận: proof π + nullifier + public statement
Verify(vk, statement, π) → true
Check: nullifier chưa từng dùng trong protocol này
→ Grant access — không biết user là ai
Nullifier — Chìa khóa chống abuse
Nullifier là Hash(user_secret || context_id). Mỗi lần dùng trong một context, nullifierGiá trị hash dùng một lần để ngăn double-vote/double-spend. Không link về identity gốc. được record. Nếu dùng lại trong cùng context → reject (chống double-use). Nhưng trong context khác → nullifier khác hoàn toàn → không thể link hai lần verify.
Ứng dụng thực tế ZK-KYC
- DeFiDecentralized Finance: tài chính phi tập trung dựa trên smart contract, không qua ngân hàng hay sàn tập trung. KYC-gate: Prove "tôi không phải US person" mà không tiết lộ quốc tịch thật
- Age verification: Prove đủ tuổi với gaming/adult content platform
- Credit scoring: Prove credit score > threshold mà không tiết lộ điểm thật
- Voting: Prove quyền bầu cử mà không link vote với identity
- Airdrop: Prove eligibility mà không deanonymize wallet
Để hiểu sâu hơn về Verifiable Credential — nền tảng của ZK-KYC flow — xem bài phân tích Verifiable Credentials. Về cơ chế Sybil resistanceKhả năng của hệ thống chống lại Sybil attack — đảm bảo một thực thể không thể kiểm soát hệ thống bằng cách tạo nhiều identity giả. và tại sao ZK proof thôi là chưa đủ, xem bài Sybil Attack.
Performance 2025: SNARK verify <1ms trên browser, generation 0.5–2s trên mobile — acceptable nếu UX design đúng. Bottleneck hiện tại là proof generation time, không phải verification. Cải thiện đang diễn ra nhanh.
8. Giới Hạn Thực Tế Của ZK Proof
ZK proof là công cụ mạnh nhưng không phải silver bullet. Hiểu giới hạn quan trọng không kém hiểu tính năng.
Prover computation cost
Tạo ZK proof tốn tài nguyên tính toán đáng kể — đặc biệt với circuit lớn. Trên thiết bị mobile, proof generation có thể mất 5–30 giây. Đây là bottleneck UX quan trọng cho ZK Identity ứng dụng đại chúng. GPU acceleration và dedicated ZK coprocessor đang được phát triển để giải quyết.
Circuit expressive power
Không phải mọi computation đều dễ viết circuit. Các operation phức tạp (floating point, string comparison, machine learning inference) tốn nhiều constraint → proof lớn và chậm. Circuit optimization là một kỹ năng riêng biệt.
ZK không thể prove về thế giới thật
ZK proof chỉ prove về data đã có trong hệ thống. Nó không thể tự prove rằng "người này thực sự là ai họ claim" — đó là bài toán của identity issuer (ngân hàng, chính phủ). ZK chỉ prove rằng "credential này hợp lệ và được ký đúng". Nếu credential gốc bị giả mạo, ZK không giúp được gì.
Trusted setup vẫn là rủi ro với SNARK
Dù MPC ceremony giảm risk rất nhiều, trusted setup vẫn là điểm yếu lý thuyết của SNARK. Và ceremony phải được tổ chức lại cho mỗi circuit mới (với Groth16) hoặc khi upgrade circuit quan trọng (với PLONK).
Về các bước cần làm để identity system sẵn sàng cho tương lai quantum, xem bài Post-Quantum Identity — phân tích chi tiết tại sao zk-STARK là lựa chọn an toàn hơn về dài hạn.
Để hiểu kiến trúc tổng thể danh tính phi tập trung — từ ZK proof đến DID đến Verifiable Credential — xem bài nghiên cứu chính về danh tính phi tập trung tại WLD.VN.
ZK không phải silver bullet: trusted setup failure, circuit bugs, side-channel attacks, và hard fork khi upgrade proof system đều là risk thực tế. Plan cho crypto-agility từ đầu, không assume ZK scheme bất biến.
Câu hỏi thường gặp về ZK Proof
Tài liệu tham khảo
- Goldwasser, S., Micali, S., Rackoff, C. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing. 1989. — Paper gốc định nghĩa ZK proof.
- Groth, J. On the Size of Pairing-Based Non-interactive Arguments. EUROCRYPT 2016. — Groth16 proving system.
- Gabizon, A., Williamson, Z.J., Ciobotaru, O. PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR 2019.
- Ben-Sasson, E. et al. Scalable, transparent, and post-quantum secure computational integrity. IACR ePrint 2018/046. — STARK foundation paper.
- Fiat, A., Shamir, A. How To Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986. — Fiat-Shamir heuristic.
- Semaphore Protocol. Zero-Knowledge Group Membership and Signaling. semaphore.pse.dev. 2023.
- ZRO Research. AI & Identity Research Hub. zro.vn/wld-vn/.
- Circom. Circuit Programming Language for ZK Proofs. docs.circom.io.