Zero-Knowledge Proof
Some things i've learned about ZKP
Introduce to ZKP
Zero-Knowledge Proof (ZKP - bằng chứng không tiết lộ) là một kĩ thuật trong mật mã học cho phép một bên (người chứng minh - Prover) chứng minh cho bên còn lại (người xác minh - Verifier) rằng họ biết một thông tin bí mật (secret) mà không cần tiết lộ nội dung của thông tin đó.
Một Zero-Knowledge Proof cần phải thỏa mãn 3 tính chất chính:
- Completeness (Tính đầy đủ): nếu người chứng minh thật sự biết bí mật, thì người xác minh sẽ bị thuyết phục.
- Soundness (Tính đúng đắn): nếu người chứng minh không biết bí mật, thì họ rất khó để lừa được người xác minh (xác suất rất nhỏ).
- Zero-Knowledge (Không tiết lộ thông tin): người xác minh sẽ không học được điều gì, biết được thông tin gì về bí mật, ngoài việc “người chứng minh biết nó”.
Sigma Protocol
Sigma Protocol, kí hiệu là $\Sigma$-Protocol. là một loại zero-knowledge iteractive proof 3 bước, dùng để chứng minh rằng người chứng minh biết một bí mật liên quan đến một hệ toán học công khai, mà không tiết lộ bí mật.
Các bước trong $\Sigma$-Protocol:
- Commitment: Prover chọn số $r$ ngẫu nhiên, tính toán $com = P_1(x, w)$, sau đó gửi cho Verifier.
- Challenge: Verifier chọn một số ngẫu nhiên $chall \in \mathcal{C}$, rồi gửi challenge này cho Prover.
- Response: Prover tính $resp = P_2(chall)$ và gửi lại cho Verifier. Verifier sau đó kiểm tra điều kiện đúng đắn:
tức là biểu thức toán học giữa $x, com, chall, resp$ đã được định nghĩa từ trước.
Để chứng minh một giao thức là một $\Sigma$-Protocol, có 3 điều kiện mà giao thức đó cần phải thỏa mãn:
- Completeness: nếu Prover thật sự biết $w$ tương ứng với $x$, thì Verifier sẽ luôn chấp nhận. Không có trường hợp “đúng nhưng bị từ chối”.
- Special Soundness: Nếu có thể tìm được 2 transcript hợp lệ $(a, e, z)$ và $(a, e’, z’)$ với cùng $a$ nhưng $e \ne e’$, thì có thể tính toán và rút ra được bí mất $w$.
- Special Honest-Verifier Zero-Knowledge (SHVZK): Với Verifer trung thực (chọn challenge ngẫu nhiên), tồn tại một trình mô phòng (simulator) có thể sinh ra transcript $(a, e, z) mà không cần biết bí mật $w$- tức là không thể phân biệt được với transcript thật.
Schnorr’s identification protocol
Schnorr’s identification protocol là một trong những giao thức ZKP nổi tiếng nhất, có tính ứng dụng cao và là nền tảng cho các hệ thống như Schnorr Signature, EdDSA và các hệ thống ZKP hiện đại.
Mục đích của Schnorr’s identification protocol là muốn chứng minh Prover biết:
\[y = g^x \pmod p\]Mà không tiết lộ $x$, trong khi thuyết phục Verifier rằng mình thực sự biết nó. Đây là một $\Sigma$-Protocol 3 bước: $(a, e, z) = (commitment,challenge,response)$
Key components
- Số nguyên tố $p$ lớn.
- Phần tử sinh $g$ có bậc là $q$ ($q$ nguyên tố) nằm trong nhóm $\mathbb{Z}_p^*$
- Prover có $x, 0 \le x \le q$ (private key)
- Public key: $y = g^x \pmod p$.
Iteractive Protocol
Non-Iteractive Protocol
Iteractive Protocol có một vấn đề là cần đến 3 bước để tương tác qua lại giữa Prover và Verifier. Điều này không phù hợp cho môi trường phi tập trung như blockchain hoặc chữ kí số.
Một giải pháp để giải quyết vấn đề này là biến nó thành non-iteractive - tức là Prover có thể tự tạo bằng chứng mà không cần tương tác với Verifier. Giải pháp này có tên gọi là Fiat-Shamir heuristic.
Ý tưởng: thay vì để Verifier chọn challenge $e$, ta sẽ để cho Prover tự sinh ra $e$ bằng cách băm các thông tin công khai.
\[e = H(x, a)\]Trong đó:
- $H$: hàm băm an toàn (SHA256, Poseidon, …)
- $x$: đầu vào công khai (statement)
- $a$: commitment
Như vậy, Prover có thể tự toàn toàn bộ transcript (a, e, z) và Verifier chỉ cần kiểm tra tính đúng đắn như bình thưởng.
Security Notes:
- Random weakness: tính ngẫu nhiên xấu có thể gây rò rỉ bí mật $x$. Nếu $r$ được sử dụng lại 2 lần với 2 challenge tương tác khác nhau hoặc dữ liệu khác nhau, khi đó: $x = \frac{z-z’}{c-c’} = \frac{r - r + x * (c - c’)}{c - c’}$.
- Parameter selection: phải chọn một nhóm cyclic $\mathbb{G} \subset \mathbb{Z}_p^*$ cấp nguyên tố $q$, với $q \mid (p - 1)$. Và $g$ là phần tử sinh bậc $q$. Không được chọn $g$ do Prover cung cấp => dễ bị lừa (Prover tạo $g$ đặc biệt để giả mạo).
Girault’s identification protocol
Gần giống với Schnorr’s identification protocol, nhưng sử dụng modulo là hợp số thay vì số nguyên tố. Mục tiêu: Prover thuyết phục Verifier rằng họ biết $x$ sao cho $h = g^{-x} \pmod N$.
Key components
- Public input: $h, N$ và phần tử sinh $g \in \mathbb{Z}_N^*$.
- Private input: Prover biết bí mật $x \in [S]$
- Security parameters: $k, k’, S$ và $R = 2^{k+k’+|S|}$
Iteractive Protocol
Non-Iteractive Protocol
Security Notes:
- Parameter choice: cần chọn tham số cẩn thận, đặc biệt là khi dùng các giá trị như $2^k, R$, nếu các tham số này có độ dài bit tương tự, vì $z$ được tính dựa trên các số tự nhiên, thì có thể xảy ra: $x \approx \lfloor z/e \rfloor$. (Too Honest)
- Verifier tin tưởng Prover trong non-iteractive protocol:
- Nếu Verifier dùng giá trị $g$ do Prover cung cấp (thay vì dùng generator chuẩn), thì Prover có thể dễ dàng giả mạo bằng: $u = 0, g = 0$ dẫn đến gian lận.
- Verifier không xác thực rằng $u,h \in \mathbb{Z}_N^*$ (từ $1$ đến $N-1$ và $GCD(k, N) = 1$): khi đó, Prover có thể replay chứng minh bằng cách thay đổi nhẹ $u$ và $h$ (thêm bội của $N$) mà vẫn được chấp nhận.
Continue …
References
https://www.zkdocs.com/docs/zkdocs/zero-knowledge-protocols/schnorr/