Bảng tóm tắt toán học: Những khái niệm cốt lõi cần biết trước khi tìm hiểu về Zero-Knowledge

Chúng ta sẽ không giải thích về Zero-Knowledge (ZK) trong năm phút tại đây. Thậm chí, chúng ta còn chưa đụng đến nó. Tuy nhiên, có một số chủ đề toán học mà bạn bắt buộc phải hiểu trước khi bất kỳ bài viết nào trong chuỗi series này trở nên có ý nghĩa.

Bạn có sợ những ký hiệu toán học khô khan đó không? Việc mở một bài báo trên arxiv có khiến bạn muốn trốn dưới gầm giường không? Tốt đấy. Tôi cũng thế. Vì vậy, hãy cùng làm quen với nó một cách chậm rãi, từng khái niệm một, không có chữ Hy Lạp nào cả và có những thứ bạn có thể click vào để tìm hiểu thêm.

1. Số học mô đun (Modular arithmetic)

Hãy tưởng tượng về một chiếc đồng hồ. Một chiếc đồng hồ bình thường có 12 vị trí (từ 0 đến 11 nếu bạn là một lập trình viên). Nếu bây giờ là 10 giờ và bạn cộng thêm 5 giờ, bạn sẽ không có 15 giờ. Bạn sẽ có 3 giờ. Con số sẽ quay vòng.

Đó chính là số học mô đun. Toán tử mod cho bạn phần dư sau khi chia:

10 + 5 = 15 → 15 mod 12 = 3
7 + 7 = 14 → 14 mod 12 = 2

Trong mật mã học, mô đun không phải là 12. Nó là một số nguyên tố lớn đến mức có 77 chữ số. Nhưng nguyên lý thì hoàn toàn giống nhau: mọi kết quả đều được quay lại một phạm vi cố định, và sự quay vòng này sẽ phá hủy thông tin về các đầu vào ban đầu.

Bạn có thể tự thử nghiệm. Chiếc đồng hồ dưới đây sử dụng một mô đun nhỏ để bạn có thể quan sát các giá trị quay vòng:

Interactive: Modular arithmetic clock visualization — try it on luk3.tech

Giải thích chính thức: Modular arithmetic on Wikipedia

2. Trường hữu hạn (Finite fields)

Một trường hữu hạn (còn gọi là trường Galois) là một tập hợp các số mà bạn có thể cộng, trừ, nhân và chia, và bạn không bao giờ rời khỏi tập hợp đó. Mọi phép toán đều quay trở lại cùng một nhóm giá trị.

Chính xác hơn, một trường hữu hạn GF(p) là tập hợp các số nguyên {0, 1, 2, ..., p-1} trong đó p là một số nguyên tố, và mọi phép tính số học đều được thực hiện theo mô đun p. Có ba thuộc tính quan trọng:

• Đóng (Closed): Không có phép toán nào tạo ra kết quả nằm ngoài tập hợp.
• Mọi phần tử đều có nghịch đảo: Với bất kỳ số a nào trong trường, luôn tồn tại một số b sao cho a * b = 1 (mod p). Phép chia luôn hoạt động.
• Không thoát ra ngoài: Bạn có thể xích chuỗi bao nhiêu phép toán tùy thích. Bạn vẫn nằm trong trường đó.

Tại sao mật mã học lại quan tâm? Bởi vì các trường hữu hạn cho phép bạn thực hiện đại số phức tạp trên các con số khổng lồ trong khi đảm bảo rằng mọi kết quả trung gian đều nằm trong một phạm vi cố định, có thể dự đoán trước. Không bị tràn số (overflow), không có vấn đề về dấu chấm động, không có bất ngờ nào. Và sự quay vòng mô đun làm cho việc đảo ngược kỹ thuật xem đầu vào nào đã tạo ra một đầu ra cụ thể trở nên cực kỳ khó khăn.

Giải thích chính thức: Finite field on Wikipedia

3. Bài toán logarit rời rạc (The discrete logarithm problem)

Đây là sự bất đối xứng cốt lõi làm cho mật mã học khóa công khai trở nên khả thi.

Hướng dễ: Cho một cơ số g, một số mũ k, và một mô đun p, việc tính toán g^k mod p rất nhanh. Máy tính rất giỏi trong việc lấy lũy thừa.

g = 3, k = 5, p = 7
3^5 = 243 → 243 mod 7 = 5

Hướng khó: Cho g, p, và kết quả 5, hãy tìm k. Với các số nhỏ, bạn có thể thử tất cả. Nhưng với những con số có 77 chữ số thì sao? Không có thuật toán nào được biết đến có thể làm điều này một cách hiệu quả. Bạn sẽ phải đoán mãi mãi đến khi vũ trụ chết nhiệt.

Đây chính là bài toán logarit rời rạc (DLP). "Rời rạc" vì bạn đang làm việc trong một trường hữu hạn (các giá trị rời rạc, không liên tục). "Logarit" vì bạn đang cố gắng tìm số mũ.

Khi cùng một bài toán này được đặt trên đường cong elliptic (tìm xem một điểm đã được "nhân" bao nhiêu lần để tạo ra một điểm khác), nó được gọi là Bài toán logarit rời rạc đường cong elliptic (ECDLP). Cùng một ý tưởng, cấu trúc đại số khác, và còn khó phá vỡ hơn nữa.

Sự phân biệt quan trọng: "khó" ở đây có nghĩa là không khả thi về mặt tính toán, không phải là không thể về mặt toán học. Câu trả lời thì có. Không ai cấm bạn tìm nó. Chỉ là các thuật toán nhanh nhất được biết đến sẽ mất nhiều thời gian hơn tuổi của vũ trụ trên phần cứng hiện tại.

Giải thích chính thức: Discrete logarithm on Wikipedia

4. Hàm băm (Hash functions)

Một hàm băm nhận bất kỳ đầu vào nào (một ký tự đơn, một cuốn tiểu thuyết, một tệp video) và tạo ra một đầu ra có kích thước cố định. SHA-256 luôn cho bạn 256 bit (64 ký tự thập lục phân). SHA-3 cũng vậy. Không quan trọng đầu vào của bạn là bốn chữ cái hay bốn gigabyte.

Nhưng làm thế nào? Làm thế nào từ "math" lại biến thành a0885e289f3e77a14e06e6887a1fc93b5ed2e14cfe7f7052805fe92e1a0e0e38?

Điều gì thực sự xảy ra bên trong một hàm băm

Hãy cùng đi qua các bước sơ lược. Các thuật toán khác nhau (SHA-2, SHA-3, BLAKE) khác nhau về chi tiết, nhưng khung sườn thì giống nhau:

Bước 1: Chuyển đổi sang nhị phân. Đầu vào của bạn trở thành các byte thô. Chuỗi math trở thành bốn giá trị ASCII: 109 97 116 104, mà trong nhị phân là 01101101 01100001 01110100 01101000.

Bước 2: Đệm thông điệp (Pad the message). Thuật toán cần đầu vào có độ dài cụ thể (bội số của kích thước khối). Vì vậy, nó nối thêm một bit 1, sau đó là đủ các bit 0, và cuối cùng là độ dài thông điệp gốc. Bây giờ bạn có một khối có kích thước cố định, gọn gàng để làm việc.

Bước 3: Khởi tạo trạng thái. Thuật toán bắt đầu với một tập hợp các hằng số cố định làm trạng thái nội bộ của nó. Những thứ này không bí mật. Chúng được định nghĩa trong spec (đối với SHA-256, chúng đến từ các phần thập phân của căn bậc hai của tám số nguyên tố đầu tiên, tại sao không chứ).

Bước 4: Nén, vòng này qua vòng khác. Đây là nơi phép thuật xảy ra. Thông điệp đã được đệm được chia thành các khối, và mỗi khối được đưa qua một hàm nén trộn nó vào trạng thái nội bộ. SHA-256 chạy 64 vòng. SHA-3 chạy 24 vòng. Mỗi vòng thực hiện sự kết hợp của:

• Phép toán trên bit: XOR, AND, NOT, xoay vòng. Những thứ này làm xáo trộn các bit theo các cách phi tuyến tính.
• Phép cộng mô đun: Cộng các giá trị theo mô đun 2^32, điều này gây ra các phép nhớ lan truyền khó lường.
• Trộn: Các bit từ các vị trí khác nhau ảnh hưởng lẫn nhau, do đó thông tin lan truyền khắp trạng thái.

Hình ảnh trực quan dưới đây đi qua toàn bộ tính toán SHA-256 cho từ "math", từng bước một. Bạn có thể thấy phần đệm, lịch trình thông điệp, và cách mỗi vòng làm xáo trộn các biến làm việc cho đến khi băm cuối cùng xuất hiện.

Interactive: SHA-256 step-by-step computation walkthrough — try it on luk3.tech

Bước 5: Đầu ra. Trạng thái nội bộ cuối cùng (một phần của nó) trở thành băm của bạn.

Kết quả là xác định (cùng đầu vào, cùng đầu ra, mọi lúc) nhưng thực tế là không thể đảo ngược. Bạn không thể tái tạo math từ băm cũng giống như bạn không thể tái tạo một quả trứng từ một món trứng bác. Điều này làm cho các hàm băm trở thành một loại hàm bẫy (trapdoor): dễ tính toán theo hướng thuận, không thể đảo ngược. Bạn sẽ thấy mô hình này ở khắp nơi trong mật mã học. Khóa công khai của bạn được dẫn xuất từ khóa riêng tư của bạn thông qua một hàm bẫy (logarit rời rạc). Chữ ký số sử dụng một cái. Các hàm băm là ví dụ đơn giản nhất: một chiều, không đường quay lại.

Giải thích chính thức: Cryptographic hash function on Wikipedia · Trapdoor function on Wikipedia

5. Ràng buộc (Constraints): cách ZK suy nghĩ về tính toán

Đây là nơi mọi thứ bắt đầu cảm thấy xa lạ.

Thông thường, khi bạn muốn chứng minh rằng bạn đã chạy một tính toán đúng cách, bạn chỉ cần chạy lại nó và kiểm tra câu trả lời. Bằng chứng ZK tiếp cận hoàn toàn khác. Thay vì chạy lại chương trình, bạn biểu diễn toàn bộ tính toán dưới dạng một tập hợp các phương trình (được gọi là các ràng buộc) phải được thỏa mãn đồng thời.

Một ví dụ đơn giản. Giả sử bạn muốn chứng minh rằng bạn biết hai số nhân với nhau bằng 35. Thay vì tiết lộ "5 và 7", bạn viết một ràng buộc:

a * b = 35

Nếu bạn có thể cung cấp các giá trị cho a và b thỏa mãn phương trình này, bạn đã chứng minh rằng bạn biết chúng. Hệ thống ràng buộc không quan tâm bạn làm thế nào tìm thấy các giá trị đó. Nó chỉ quan tâm rằng chúng thỏa mãn các phương trình.

Các hệ thống ZK thực tế biểu diễn toàn bộ chương trình theo cách này. Một chương trình kiểm tra mật khẩu, xác minh bằng chứng Merkle, hoặc xác thực giao dịch được biên dịch thành hàng nghìn (hoặc hàng triệu) ràng buộc. Định dạng phổ biến nhất cho việc này được gọi là R1CS (Rank-1 Constraint System), trong đó mọi ràng buộc có dạng:

(trái) * (phải) = (đầu ra)

Mỗi trong số trái, phải, và đầu ra là một tổ hợp tuyến tính của các biến. Toàn bộ chương trình trở thành một hệ thống các phương trình này.

Sự thật ngộ nhận: "Tôi biết các giá trị thỏa mãn tất cả các ràng buộc này" là một tuyên bố mà bạn có thể chứng minh mà không cần tiết lộ các giá trị đó.

Giải thích chính thức: R1CS on Wikipedia

6. Ý tưởng đằng sau bằng chứng Zero-Knowledge

Bây giờ bạn đã có tất cả các mảnh ghép. Bằng chứng ZK kết hợp các khái niệm trên thành một giao thức duy nhất.

Thiết lập: có một người chứng minh (prover) (người biết bí mật) và một người xác minh (verifier) (người muốn được thuyết phục rằng người chứng minh biết nó, mà không học được bí mật).

Một bằng chứng zero-knowledge có ba thuộc tính:

• Tính đầy đủ (Completeness): Nếu người chứng minh thực sự biết bí mật, họ luôn có thể thuyết phục người xác minh. Người chứng minh trung thực luôn thành công.
• Tính đúng đắn (Soundness): Nếu người chứng minh không biết bí mật, họ không thể lừa người xác minh (trừ với xác suất không đáng kể). Kẻ nói dối sẽ bị bắt.
• Zero-knowledge (Không có kiến thức): Người xác minh không học được gì ngoài việc tuyên bố là đúng. Không có thông tin về bí mật bị rò rỉ.

Kết hợp những điều đó với các hệ thống ràng buộc và bạn sẽ có bức tranh toàn cảnh: người chứng minh lấy một chương trình, biên dịch nó thành các ràng buộc, cắm các giá trị bí mật của họ vào, và tạo ra một bằng chứng rằng tất cả các ràng buộc đều được thỏa mãn. Người xác minh kiểm tra bằng chứng mà không bao giờ thấy các giá trị bí mật.

Toán học làm cho điều này thực sự hoạt động (cam kết đa thức, ghép cặp đường cong elliptic, biến đổi Fiat-Shamir) rất sâu sắc. Các bài viết sau sẽ đi sâu vào đó. Còn bây giờ, mô hình tư duy là đủ: các ràng buộc định nghĩa việc "đúng" có nghĩa là gì, và bằng chứng ZK cho phép bạn chứng minh tính đúng đắn mà không cần tiết lộ đầu vào của bạn.

Giải thích chính thức: Zero-knowledge proof on Wikipedia