ZKP - Giới thiệu đơn giản về Chứng minh Không Để Lộ Tri Thức

Cho những ai muốn xem tiếng Anh thì xem ở đây.

Làm cách nào chứng minh cho một người bị mù màu hai quả bóng bida khác màu nhau?

Giả sử bạn có 2 quả bóng bida giống hệt nhau về hình dạng, chỉ khác màu: một xanh và một đỏ và cần chứng minh cho một người mù màu rằng chúng khác màu nhau. Sau đây là các bước chứng minh:

• Đầu tiên, đặt 2 quả bóng trước mặt người đó và nói với anh ta rằng hai quả bóng này có màu khác nhau. Tất nhiên, đối với người mù màu, hai quả bóng này trông giống hệt nhau.

• Bạn để người này giấu hai quả bóng ra sau lưng để bạn không thể nhìn thấy chúng nữa. Người này có quyền hoán đổi hai quả bóng hoặc giữ nguyên vị trí của chúng trong tay.

• Sau đó, người này thách thức bạn bằng cách đưa ra một quả bóng trong tay trái hoặc tay phải và hỏi bạn liệu anh ta có hoán đổi hai quả bóng hay không.

• Tất nhiên, nếu hai quả bóng có cùng màu, bạn sẽ không thể trả lời chính xác. Nếu bạn luôn có thể trả lời đúng, điều đó có nghĩa là hai quả bóng có màu khác nhau.

Ở trên là ví dụ về Chứng minh Không để lộ Tri Thức (zero-knowledge proof) vì người thực hiện kiểm tra (người mù màu) không bao giờ biết được quả bóng nào là màu xanh và quả bóng nào là màu đỏ; thực tế, anh ta không có được bất kỳ kiến thức nào về cách phân biệt hai quả bóng nhưng thông qua những lần hỏi và trả lời, anh ta vẫn tin rằng hai quả bóng ấy khác màu.

Tính chất của ZKP

• Completeness: Nếu mệnh đề cần chứng minh là đúng, người kiếm chứng sẽ bị thuyết phục. Ở đây, người kiểm chứng có thể yêu cầu người chứng minh thực hiện việc chứng minh nhiều lần cho đến khi anh ta cảm thấy thuyết phục.

• Soundness: Nếu mệnh đề cần chứng minh là sai, người chứng minh không thể lừa được người kiểm chứng hoặc với xác suất cực kỳ nhỏ, gần như bằng 0%.

• Zero-Knowledge: Người kiểm chứng không biết thêm được thông tin gì ngoại trừ mệnh đề cần kiểm chứng.

ZKP Tương tác (Interactive ZKP) và ZKP Không Tương tác (Non-Interactive ZKP)

ZKP có ai loại: Tương tác (IZKP) vào Không tương tác(NIZKP).

• IZKP: Yêu cầu người chứng minh và người kiểm chứng tương tác với nhau, giống như ví dụ chứng minh hai quả bóng và người mù màu ở bên trên trên.

• NIZKP: Bằng chứng được tạo trước khi chứng minh, sau đó người kiểm chứng có thể lấy dùng và kiểm chứng sau mà không cần phải giao tiếp trực tiếp với người chứng minh.

Mô hình đơn giản cho I-ZKP

Mô hình dưới đây tuy gọi là “đơn giản“ nhưng các bạn hoàn toàn có thể đưa vào áp dụng cho một vài mô hình authentication.

• Prover và Verifier đều biết \(g, p\)

• Prover muốn chứng minh rằng anh ấy biết giá trị \(w\), nhưng không muốn cho Verifier biết \(w\) thực chất bằng bao nhiêu.

• Prover tính \(y=g^w \mod p\), gửi cho Verifer và báo cho anh ta biết rằng \(y=g^w \mod p \) . Ở đây Prover muốn thông qua \(y\) để chứng minh rằng anh ta biết \(w\).

• Verifier dùng \(y\) để kiểm chứng

• Prover tiếp tục chọn một giá trị ngẫu nhiên \(x\), rồi tính \(t = g^x \mod p\), gửi \(t\) cho Verifier

• Verifier chọn giá trị \(c\) ngẫu nhiên gửi cho Prover và yêu cầu Prover tính \(r = x -cw\). Lưu ý rằng Verifier không hề biết giá trị của \(x\) và \(w\)

• Prover gửi \(r\) qua cho Verifier kiểm chứng

• Verifier nhận được \(r\) sẽ kiểm chứng bằng cách tính \(v=g^r.y^c \mod p\). Nếu \(v = t\) thì mệnh đề được xem là hợp lệ.

Tại sao \(v=t\) ?

$$\begin{align*} v &= g^r.y^c \mod p \\ v &= g^{x-cw}y^c \mod p = g^{x-cw}(g^w)^c \mod p= g^{x-cw}g^{cw} \mod p\\ \implies v&= g^{x-cw}g^{cw}\mod p = g^{x-cw+cw} \mod p=g^x \mod p = t \end{align*}$$

Demo

Bạn cứ theo sát lược đồ bên trên để chạy demo nhé! Nếu cần verify tính toán thì có thể dùng mini calculator của mình trên header.

Mô hình đơn giản cho NI-ZKP

Ý tưởng cốt lõi là mô hình chữ ký số (digital signature). Chữ ký số có thể đóng vai trò như một bằng chứng độc lập và loại bỏ nhu cầu tương tác qua lại giữa người chứng minh (Prover) và người xác minh (Verifier).

Prover muốn chứng minh anh ta biết khóa bí mật \(sk\) kết hợp với khóa công khai \(pk\).

• Prover chọn thông điệp ngẫu nhiên \(m\)

• Prover tạo ra chữ ký \(\delta\) từ thông điệp \(m\), dùng khóa \(sk\)

• Prover gửi cặp \((m,\delta)\) cho Verifier

• Verifier dùng khóa công khai \(pk\) để verify \(\delta\) và \(m\).