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

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.

Chứng minh Không để lộ Tri Thức (ZKP) là một giao thức về xác suất cho phép người chứng minh (prover) thuyết phục người kiểm chứng (verifier) rằng một mệnh đề là ĐÚNG kể cả khi không hề tiết lộ bất cứ thông tin gì về mệnh đề ấy.

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, hay còn được biết là Sigma Protocol, tuy “đơ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. Gồm 3 bước:

• Prover và Verifier đều biết $p$ là số nguyên tố và $g$ là generator của $\mathbb Z_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 thực chất $w$ bằng bao nhiêu.

• Bước 1: Commitment

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

  • 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$, rồi gửi $t$ cho Verifier

• Bước 2: Challenge

  • Verifier chọn giá trị ngẫu nhiên $c$ 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$

• Bước 3: Response

  • 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ệ (bằng chứng đã hợp lệ).

Mô hình Sigma protocol

Tại sao $v=t$?

Tại sao giao thức này là Zero - Knowledge?

Vì Verifier chỉ học được rằng: "Prover biết $w$ sao cho $y=g^w$" và không thể suy ra giá trị của $w$. Tính chất này được đảm bảo bởi 3 yếu tố:

• Completeness — Prover trung thực luôn được chấp nhận

• Soundness — người không biết $w$ rất khó giả mạo proof

• Zero-knowledge — proof không tiết lộ thông tin về $w$

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 bên thanh công cụ.

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$.

Nếu chữ ký hợp lệ, Verifier có thể tin rằng Prover biết khóa bí mật tương ứng với $pk$. Theo nghĩa này, chữ ký số đóng vai trò như một bằng chứng không tương tác cho việc biết khóa bí mật. Tuy nhiên, chữ ký số chỉ là một ví dụ đặc biệt của proof of knowledge. Trong khi đó, các hệ Non-Interactive Zero-Knowledge Proof (NIZK) có thể được xây dựng để chứng minh những mệnh đề tổng quát hơn nhiều, chẳng hạn như chứng minh rằng một giá trị bí mật thỏa mãn một điều kiện toán học nhất định mà không cần tiết lộ giá trị đó.