Zero Knowledge Proof với KZG commitment scheme

Trong bài viết này mình sẽ giải thích lược đồ commitment bằng đa thức được giới thiệu bởi Kate, Zaverucha và Goldberg. Lược đồ này được áp dụng vào Zero Knowledge Proof trên công nghệ blockchain (Proto-Danksharding EIP-4844) nhằm thu gọn kích thước của proof thành một giá trị cố định mà không quan tâm đến kích cỡ thông điệp như cách dùng merkle tree và merkle path.

Bài toán ZKP qua lược đồ commitment

Một người có thể tuyên bố rằng người ấy biết message \(m\) bằng cách commit một giá trị \(c\) sao cho bất cứ ai cũng có thể dùng \(c \) để verify điều này, tuy nhiên thông tin của \(m\) không hề bị tiết lộ hoặc bị làm giả. Nghĩa là, sẽ không thể hoặc rất khó tìm thấy \(m'\)sao có thể dùng \(c\) để verify cho \(m'\). Điều này phù hợp với các tính chất của Zero Knowledge Proof (xem lại bài ZKP tại đây).

Đối với lược đồ commitment bằng đa thức. Một người có thể chứng minh rằng người ấy biết chính xác một đa thức \(\phi(x)\), nghĩa là người này biết toàn bộ giá trị các hệ số \(a_i\) của \(\phi(x)\) thay vì là biết thông tin về message \(m\).

Thiết lập lược đồ

Bước 1: Thiết lập trust một lần duy nhất. Sau bước này, các bước khác sẽ được lặp lại để chứng minh cho các đa thức khác nhau.

• Cho \(g\) là phần tử sinh (generator) của một group pairing-friendly elliptic curve \(\mathbb G\)

• Gọi \(l\) là bậc cao nhất của các đa thức có thể được tạo.

• Chọn một giá trị \(\tau \in \mathbb F\) ngẫu nhiên bất kỳ, được gọi là trapdoor

• Tính các giá trị \(g,g^{\tau}, g^{\tau^2}, \dots, g^{\tau^l}\). Chú ý rằng \(\tau\) được giữ bí mật, không tiết lộ.

Bước 2: Bước này để một người chứng minh rằng anh ta biết một đa thức \(\phi(x) = \sum_{i=0}^k\phi_ix^i\) với bậc \(k\) nhỏ hơn hoặc bằng \(l\). Tuy nhiên để đơn giản, cứ xem như \(\phi(x)\) có \(l \) hệ số với các hệ số \(\phi_{i>k} = 0\).

• Ta có: \(\phi(x) = \sum_{i=0}^l\phi_ix^i \implies \phi(\tau)=\sum_{i=0}^l\phi_i\tau^i\)

• Tính giá trị \(c=g^{\phi(\tau)}\) thông qua các giá trị đã setup \(g,g^{\tau}, g^{\tau^2}, \dots, g^{\tau^l}\) bằng cách tính \(\prod_{i=0}^l(g^{\tau^i})^{\phi_i} = g^{\sum_{i=0}^l\phi_i\tau^i} = g^{\phi(\tau)}\)

• Commit giá trị \(c\)

Bước 3: Thiết lập bằng chứng \(\pi\)

• Chọn một giá trị \(a\) bất kỳ, tính \(\phi(a)=b\)

• Tính \(\pi=g^{q(\tau)}\), trong đó \(\displaystyle q(x) = \frac {\phi(x) - b} {x-a}\). Để ý rằng \(q(\tau)\) chỉ có có thể tồn tại nếu và chỉ nếu \(\phi(a)=b. \) Ta có thể dễ dàng chứng minh điều này như sau:

  • Ta có
    \(\phi(a) = b \implies \phi(x) - \phi(a) = \sum_{i=0}^l \phi_ix^i - \sum_{i=0}^l \phi_ia^i = \sum_{i=0}^l \phi_i(x^i - a^i)\)sẽ luôn tồn tại \((x-a)\) và vì thế sẽ triệt tiêu mẫu số của \(q(x)\). Nếu không \((x-a)\) ở mẫu số sẽ gây phép chia cho \(0\).

• Output \(a,b,\pi\)

Bước 4: Verify

Cần kiểm tra điều kiện \(\boxed{e(\frac c {g^b}, g) = e(\pi, \frac {g^{\tau}}{g^a})}\), với \(e\) là một cặp ghép song tuyến tính. Điều này xảy ra vì:

$$e(\frac c {g^b}, g) = e(\frac {g^{\phi(\tau)}} {g^b}, g) = e(g^{\phi(\tau)-b},g) = e(g,g)^{\phi(\tau)-b} = e(g,g)^{q(\tau)(\tau-a)} = e(g^{q(\tau)},g^{\tau-a}) = e(\pi,\frac {g^{\tau}}{g^a})$$

Kết thúc

Như vậy, ta thấy chỉ cần hai giá trị \(c\) - commit và \(\pi\) - proof với kích thước xác định, ta có thể chứng minh một người biết đa thức \(\phi(x)\), thay vì phải reveal toàn bộ cá hệ số \(\phi_i\) của đa thức này. Phương pháp này giúp tinh gọn kích thước proof so với mô hình Merkle tree, Merkle path.