VanhGer

Đây là kiến thức mình tìm hiểu được từ khóa học CS251 của đại học Stanford. Mọi người có thể truy cập vào khóa học này để đọc thêm các tài liệu và bài giảng bằng tiếng Anh.

Trong hệ thống tài chính, việc riêng tư là điều cần thiết. Một vài ví dụ như: Một nhà sản xuất không muốn tiết lộ số tiền họ trả cho nhà cung cấp của mình cho các bộ phận, Người dùng cuối cần quyền riêng tư để thuê, quyên góp, mua hàng,… Do đó, blockchain không thể phát huy hết tiềm năng nếu không có một số Tx riêng tư.

Sự riêng tư trong các blockchain

• Với Ethereum, mọi số dư đều công khai. Trong các DApps, code và state cũng công khai cho người dùng. Ngoài ra, các Tx cũng nối đến các account.
• Với Bitcoin, dữ liệu Tx có thể được sử dụng để kết nối 1 địa chỉ tới 1 định danh vật lý.

Tx riêng tư trên blockchain công khai

Chúng ta có thể sử dụng commitments và zero knowledge proof để làm điều này.

Committed data : cam kết ngắn (ẩn) ở trên chuỗi.
Proof 𝝅 : succinct Zero knowledge (Zk) proof:

• Committed Tx data nhất quán với trạng thái commited hiện tại.
• Committed update state thì đúng. Từ đó, ai cũng có thể xác thực 𝝅.

Review: Commitment

Được sử dụng với nhiều mục đích, ví dụ Đấu giá kín. Người tham gia cam kết giá, sau khi hết thời gian thì mọi người sẽ mở cam kết của họ.

Cú pháp 2 thuật toán:

• commit(msg, r) -> com. Trong đó, r là randombit, com là string ngắn
• verify(msg, com, r) -> reject / accept.

Tính bảo mật

Binding : Không thể tạo 2 valid openings cho com.

Tức là: tạo ra com, (m1, r1), (m2, r2) mà:

• verify(m1, com, r1) = accept. Và
• verify(m2, com, r2) = accept với m1 ≠ m2.

Hiding : Com không tiết lộ gì về data đã committed. Tức là com sẽ độc lập với m.

zk-SNARK là gì?

Các khái niệm

Để verify 1 Tx, Validator cần phải xem thông tin trong Tx đó và kiểm tra xem có thoả mãn không. Nhưng nếu các Tx là private thì Validator sẽ kiểm tra như thế nào? Lúc này, zk-SNARK được ra đời.

SNARK : là 1 proof ngắn gọn để chứng minh 1 statement là đúng. Ngoài ra, nó cần nhanh để xác thực bởi người xác thực.

Ví dụ: statement: “Tôi biết một m mà SHA256(m) = 0”.
zk-SNARK : là SNARK không tiết lộ gì về nội dung. Ví dụ trong statement kia thì zk-SNARK sẽ không tiết lộ gì về giá trị của m.

Ứng dụng:

• Private Tx
• zkBrigde: nối các chuỗi khối
• tính riêng tư trong zk-Rollups

Kĩ thuật zk-SNARK

Arithmetic Circuits (AC)

Cho 1 trường hữu hạn: $𝔽={0, …, 𝑝−1}$ với p là số nguyên tố > 2.

Arithmetic Circuit: C: $𝔽^𝑛 ⇾ 𝔽$.

C lấy input là list gồm n phần tử thuộc F, output là 1 phần tử thuộc F.

|C| = số gates trong mạch C.

Ví dụ:

• C_hash(h, m) = 0 nếu SHA256(m) = h, $!= 0$ nếu ngược lại.
• C_sig(pk, msg, σ) = 0 nếu chữ kí σ là hợp lệ trên msg với pk.

Argument System

Cho một AC: C(x, w) -> F với:

• x: là statement công khai
• w: secret witness.

Prover P cần thuyết phục các Verifier V rằng tồn tại w mà C(x, w) = 0 nhưng không muốn gửi w vì lý do bảo mật.

Có 2 loại argument systems: Interactive vs Non-interactives.

• Interactive: P <-> V tương tác với nhau nhiều lần để V đồng ý. Cách này chỉ áp dụng với hệ thống có ít V.
• Non-interactive: P chỉ gửi duy nhất 1 msg là proof cho V. Cách này có ích khi có nhiều Verifier (Ví dụ nhiều Validator muốn xác thực 1 Tx).

NARK: Non-interactive Argument of Knowledge

Với mạch C(x, w) ⇾ 𝔽.

Preprocessing : S(C) ⇾ public parameters(Sp, Sv).

Minh hoạ:

Một preprocessing NARK là bộ 3 (S, P, V):

• S(C) ⇾ public parameters(Sp, Sv).
• P(Sp, x, w) ⇾ proof 𝜋
• V(𝑣𝑝, 𝒙, 𝝅) ⇾ accept / reject

Yêu cầu

• Complete: ∀𝑥, 𝑤: $𝐶(𝒙, 𝒘) = 0 ⇒ Pr[ V(𝑣𝑝, 𝑥, P(𝑝𝑝, 𝒙, 𝒘)) = accept] = 1$.
• Argument of knowledge: V accepts ⇒ P biết 𝑤
• Zero knowledge: (𝐶, 𝑝𝑝,𝑣𝑝 ,𝒙, 𝜋) không tiết lộ gì về 𝒘

Succinct
Một NARK gọi là SNARK khi việc tạo ra và xác minh proof với thời gian nhanh:

• S(𝐶) ⇾ public parameters (S𝑝, S𝑣)
• P(𝑝𝑝, 𝒙, 𝒘) $\rightarrow$ short proof 𝜋; $\lVert 𝜋 \rVert =𝑂_𝜆(𝐥𝐨𝐠⁡(\lVert𝑪\rVert))$
• V(𝑣𝑝, 𝒙, 𝝅) nhanh để thẩm định: $time(V) = 𝑂_𝜆 (\lVert 𝑥 \rVert, 𝐥𝐨𝐠⁡(\lVert 𝑪 \rVert))$.

Do đó, với SNARK thì việc đọc toàn bộ mạch C là không kịp thời gian. VÌ vậy cần bước preprocessing.

Tóm lại:

• SNARK: bộ (S, P, V) thoả mãn: Complete, Argument of knowledge, Succinct.
• zk-SNARK: SNARK có zero knowledge.

Các loại Preprocessing

• trusted setup per circuit: S(C) sử dụng data bí mật (Ví dụ: randombit r).
• trusted but universal: Randombit r độc lập khỏi C:
  
  S = (S_init, S_index) với:
  • 𝑆_𝑖𝑛𝑖𝑡 (𝜆;𝑟) ⇾ U: 1 lần duy nhất.
  • 𝑆_𝑖𝑛𝑑𝑒𝑥 (U,𝐶) ⇾ (S𝑝, S𝑣): Không chứa secret data.

Argurment of knowledge

P biết w nếu w có thể được extracted từ P.

Bộ 3 (S, P, V) là Argurment of knowledge với mạch C nếu:

• A = (A0, A1) là adversary mà có thể bị extracted thông tin:
  • S(C) ⇾ (Sp, Sv), A0(Sp) ⇾ (x, st)
  • 𝜋 ⇽ A1(𝑝𝑝, 𝑥, st): Pr[V(vp, 𝑥, 𝜋) = accept] > 1/10^6 (không đáng kể )
• Có extractor E (sử dụng A1 là blackbox) và tạo ra được w bằng tương tác với A1(Sp, x, st).

Zero knowledge

Proof 𝜋 không tiết lộ về 𝒘 nếu Verifier tự tạo 𝜋, hay Verifier không học được gì từ proof 𝜋.

Tức là:

• Tồn tại 1 hàm Sim() sao cho: (S𝑝, S𝑣, 𝜋) ⇽ Sim(𝐶,𝑥). Hay Sim() có thể tạo ra proof 𝜋 mà không cần w.

Lời kết

Ở trên là sơ lược về tính riêng tư trong Blockchain và cái nhìn tổng quan về zk-SNARK.