2026-03-04

Zero-knowledge proofs - Part 1

Độ phức tạp

Độ phức tạp ở đây bao gồm hai khía cạnh: độ phức tạp về thời gian và độ phức tạp về không gian.

Như ta đã biết, máy Turing được lựa chọn cho khái niệm thuật toán và do đó việc xây dựng thuật toán giải bài toán cho trước được đưa về việc xây dựng máy Turing khẳng định ngôn ngữ tương ứng với bài toán ấy. Trên thực tế, việc khảo sát không chỉ dừng lại ở chỗ kết luận bài toán là giải được một cách chung chung mà phải là giải được một cách thực tế, tức là giải được trong khuôn khổ thời gian và không gian bộ nhớ hạn chế.

Trước tiên đối với độ phức tạp về thời gian ta có định nghĩa như sau:

Định nghĩa: Cho $M$ là một máy Turing tất định dừng (một băng hoặc nhiều băng). Độ phức tạp thời gian (time complexity) hay thời gian hoạt động (running time) của $M$ là hàm $t: \mathbb{N} \to \mathbb{N}$, mà giá trị $t(n)$ là số lần tối đa các phép biến đổi cơ bản được sử dụng trong quá trình tính toán của $M$ trên bất cứ từ vào nào độ dài $n$.

Ví dụ:

for i in range(n):
    print(arr[i])

Việc duyệt qua từng phần tử của mảng như vậy có độ phức tạp thời gian là $O(n)$ vì số lần thực hiện phép biến đổi cơ bản là $n$ lần, ứng với một lần duyệt.

for i in range(n):
    for j in range(m): 
        print(arr[i][j])

Còn ở ví dụ này thì độ phức tạp thời gian sẽ là $O(n \times m)$ vì ta có hai vòng lặp lồng nhau, vòng ngoài chạy $n$ lần và vòng trong chạy $m$ lần, tổng cộng là $n \times m$ lần thực hiện phép biến đổi cơ bản.

Khái niệm trên có thể được mở rộng cho các máy Turing không tất định, trong đó ta sẽ xem xét số lần thực hiện phép biến đổi cơ bản trên đường dẫn tính toán dài nhất. Lúc này $t(n)$ sẽ là số lần tối đa các phép biến đổi cơ bản được sử dụng trong quá trình tính toán của máy Turing trên mỗi từ vào độ dài $n$ và theo từng nhánh trong cây tính toán của máy.

Sự khác biệt cơ bản giữa tất định và không tất định đó chính là ở máy tất định tại mỗi bước tính toán chỉ có một phép biến đổi cơ bản duy nhất được thực hiện, trong khi đó ở máy không tất định tại mỗi bước có thể có nhiều phép biến đổi cơ bản khác nhau được thực hiện, tạo thành nhiều nhánh trong cây tính toán.

Độ phức tạp thời gian được chia ra nhiều lớp khác nhau, trong đó có lớp P, NP, NP-đầy đủ (NP-complete) và NP-khó (NP-hard).

Vì phần này nếu viết thực sự đầy đủ ra thì sẽ rất dài nên mình khuyên mọi người nên đọc bài viết sau của Geeksforgeeks để nắm được các khác niệm trên ở mức high-level: Link

Đầu tiên, lớp P bao gồm các bài toán có thể giải quyết dễ dàng và cũng có thể kiểm tra dễ dàng. Hai thao tác trên đều có thể được thực hiện trong thời gian đa thức đối với độ dài từ vào.

Ví dụ: Sắp xếp một danh sách

Để sắp xếp một danh sách ta có thể sử dụng Merge Sort với độ phức tạp thời gian là $O(n \log n)$. Ta biết rằng $\log n < n$ cho nên $n \log n < n^2$. Do đó độ phức tạp thời gian của thuật toán bị chặn trên bởi một đa thức vì vậy bài toán thuộc vào lớp P.
Để kiểm tra xem danh sách đã được sắp xếp hay chưa ta có thể duyệt qua từng phần tử của danh sách và so sánh nó với phần tử tiếp theo, nếu như có một phần tử nào đó lớn hơn phần tử tiếp theo thì ta kết luận rằng danh sách chưa được sắp xếp. Việc duyệt qua từng phần tử như vậy có độ phức tạp thời gian là $O(n)$.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        lefthalf = arr[:mid]
        righthalf = arr[mid:]

        merge_sort(lefthalf)
        merge_sort(righthalf)

        i = 0
        j = 0
        k = 0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                arr[k] = lefthalf[i]
                i = i+1
            else:
                arr[k] = righthalf[j]
                j = j+1
            k = k+1

        while i < len(lefthalf):
            arr[k] = lefthalf[i]
            i = i+1
            k = k+1

        while j < len(righthalf):
            arr[k] = righthalf[j]
            j = j+1
            k = k+1
    return arr
def verify(arr):
    for i in range(len(arr) - 1): 
        if arr[i] > arr[i+1]:
            return False 
    return True 

Tiếp theo ta có khái niệm về Witness. Witness ở đây có thể hiểu là một bằng chứng tuyên bố rằng một từ nào đó thuộc về một ngôn ngữ, hay nói cách khác nó là một bằng chứng cho thấy một bài toán có lời giải. Như ví dụ ở trên thì bằng chứng sẽ là dãy đã được sắp xếp.

Đối với các bài toán thuộc nhóm NP, việc kiểm tra một lời giải có thể được thực hiện trong thời gian đa thức bởi máy Turing tất định, Tuy nhiên, hiện tại ta vẫn chưa biết liệu có tồn tại thuật toán đa thức để tìm lời giải cho mọi bài toán trong lớp NP hay không.

Một bài viết nói rõ hơn về vấn đề trên: P vs NP

ZKP

Vậy thì những khái niệm trên có liên quan gì đến ZKP?

ZKP là một giao thức mật mã cho phép một bên (gọi là Prover - người chứng minh) chứng minh với một bên khác (gọi là Verifier - người xác minh) rằng một tuyên bố nào đó là đúng mà không cần tiết lộ thêm bất kì thông tin nào ngoài tính đúng của tuyên bố đó

Một hệ thống chứng minh ZKP cần thỏa mãn 3 đặc điểm cơ bản như sau:

Tính đúng đắn (completeness): Nếu người chứng minh có thông tin hợp lệ, thì có thể thuyết phục được người xác minh
Tính bảo mật (soundness): Nếu người chứng minh gian lận, xác suất thuyết phục được người xác minh rất thấp
Tính không tiết lộ (zero-knowledge): Người xác minh không học được thêm bất cứ thông tin gì ngoài việc “tuyên bố là đúng”

Trong các giao thức ZKP ta lại chia ra làm hai loại: interactive ZKP và non-interactive ZKP (NIZK).

Đối với interactive ZKP, quá trình chứng minh yêu cầu trao đổi nhiều bước giữa Prover và Verifier. Còn đối với NIZK thì quá trình chứng minh chỉ yêu cầu một bước duy nhất, trong đó Prover gửi một bằng chứng duy nhất cho Verifier mà không cần bất kỳ sự tương tác nào sau đó.

Một hệ thống chứng minh như vậy thường được xây dựng dựa trên các lớp ngôn ngữ cụ thể trong lý thuyết độ phức tạp tính toán. Trong thực tế, các giao thức ZKP thường được xây dựng cho các ngôn ngữ thuộc lớp NP.

Lý do là vì đối với các bài toán trong NP, nếu tồn tại một lời giải (gọi là witness), thì tính đúng đắn của lời giải đó có thể được kiểm tra bởi một thuật toán chạy trong thời gian đa thức. Điều này phù hợp với mô hình của ZKP, trong đó Verifier là một thực thể có khả năng tính toán giới hạn (không thể có vô hạn năng lực tính toán hay vô hạn bộ nhớ).

$\displaystyle P( x)\xrightarrow{\pi } V( x)$

Với ngôn ngữ $L \in NP$, tồn tại một thuật toán hiệu quả $\displaystyle M( \cdot ,\cdot )$ sao cho:

$\displaystyle x\in L\leftrightarrow \exists w\in \lbrace 0,1\rbrace^{poly( |x|)} :M( x,w) =1$

Như vậy giao thức chứng minh cho ngôn ngữ $L$ có thể được hiểu như sau

$P(x)$: Tính toán một witness $w$ sao cho $M(x,w) = 1$ và gửi cho $V$
$V(x)$: Kiểm tra $M(x,w)=1$ và trả về kết quả đúng nếu $M(x,w)=1$ và sai nếu $M(x,w)=0$

Đối với Interactive ZKP, quá trình trên sẽ diễn ra lặp lại nhiều lần. Hơn nữa $(P,V)$ sẽ được gọi là một hệ thống chứng minh interactive cho ngôn ngữ $L$ nếu nó thỏa mãn hai tính chất sau:

Completeness: $\forall x \in L$,

$\displaystyle \Pr[ \langle P,V\rangle ( x) =1] \geqslant \frac{2}{3}$

Soundness: $\displaystyle \forall x\notin L,\forall P^{*}$,

$\displaystyle \Pr\left[ \langle P^{*}( x) ,V( x) \rangle =1\right] \leqslant \frac{1}{3}$

Điều này có nghĩa là nếu $x \notin L$ thì không có bất cứ thuật toán nào có thể thuyết phục được $V$ rằng $x$ thuộc về $L$ với xác suất lớn hơn $\displaystyle \frac{1}{3}$, bất kể thuật toán đó có thể làm gì đi nữa.

Về ý nghĩa của interactive ZKP: Interactive ZKP cho phép Prover và Verifier trao đổi thông tin qua nhiều vòng tương tác. Mỗi vòng tương tác thường bao gồm một bước thử thách (challenge) từ Verifier và một phản hồi (response) từ Prover. Việc lặp lại quá trình này giúp giảm xác suất gian lận của Prover, vì nếu Prover không thực sự biết witness thì xác suất trả lời đúng mọi thử thách sẽ giảm nhanh theo số vòng tương tác.

Tiếp theo ta sẽ đào sâu hơn về ZKP thông qua một số ví dụ

Resources:

https://github.com/ken3k06/Zero-knowledge-proof/tree/main