Bằng chứng không tiết lộ: Giới thiệu các nguyên lý nền tảng

Giới thiệu

Bằng chứng không tiết lộ là một trong những công cụ mạnh mẽ nhất do các nhà mật mã học tạo ra. Đáng tiếc là phần lớn mọi người chưa hiểu về chúng. Bài viết này hướng đến việc khắc phục điều đó bằng cách cung cấp một cái nhìn tổng quan toàn diện về bằng chứng không tiết lộ từ các nguyên lý đầu tiên. Chúng ta sẽ tìm hiểu lý thuyết, toán học và mật mã học đằng sau bằng chứng không tiết lộ để bất kỳ ai cũng có thể hiểu những bước phát triển mới nhất trên Solana, cụ thể là ZK Compression và tương lai của khả năng tương tác.

Bài viết này giả định rằng bạn đã hiểu mô hình lập trình của Solana và các nguyên hàm mật mã vốn có trong hệ thống blockchain (tức là hàm băm, con trỏ băm, cây Merkle, cây Merkle đồng thời). Nếu những khái niệm này còn mới, bạn nên đọc trước các bài blog sau:

• Công cụ mật mã 101 — Giải thích hàm băm và cây Merkle
• Mô hình lập trình Solana: Giới thiệu về phát triển trên Solana

Lưu ý rằng bài viết này được thiết kế theo hướng mô-đun. Những độc giả chưa quen với các chủ đề này nên đọc tuần tự từng phần và tiểu mục. Tuy nhiên, nếu đã quen thuộc với một số chủ đề cụ thể hoặc muốn tìm hiểu một chủ đề nhất định, bạn hoàn toàn có thể chuyển thẳng đến phần tương ứng.

Đây cũng là bài viết đầu tiên trong loạt bài gồm hai phần về bằng chứng không tiết lộ. Bạn nên đọc bài viết này trước khi chuyển sang Bằng chứng không tiết lộ: Các ứng dụng trên Solana.

Lý thuyết đằng sau bằng chứng không tiết lộ

Năm 1989, các nhà nghiên cứu MIT Shafi Goldwasser, Silvio Micali (nhà sáng lập Algorand) và Charles Rackoff đã công bố Độ phức tạp tri thức của các hệ thống chứng minh tương tác. Họ nghiên cứu các hệ thống trong đó một bên (tức người chứng minh) trao đổi thông điệp với bên thứ hai (tức người xác minh) để thuyết phục bên đó rằng một mệnh đề toán học nào đó là đúng. Họ là những người đầu tiên đặt câu hỏi: “Điều gì xảy ra nếu cả người chứng minh và người xác minh đều không tin tưởng nhau?” Mối lo ngại ở đây là ngoài việc biết mệnh đề đúng, người xác minh sẽ thu được bao nhiêu thông tin trong quá trình trao đổi thông điệp. Ví dụ, người chứng minh có thể muốn thuyết phục người xác minh rằng họ biết lời giải của một câu đố phức tạp mà không tiết lộ chính lời giải đó.

Trước hết, chúng ta đang cố giải quyết loại bài toán nào?

Tô ba màu đồ thị

Tô ba màu đồ thị là một bài toán kinh điển trong khoa học máy tính và lý thuyết đồ thị. Bài toán yêu cầu tô các đỉnh của một đồ thị bằng ba màu sao cho không có hai đỉnh kề nhau nào cùng màu. Với đồ thị có ba đỉnh, việc này khá đơn giản. Tuy nhiên, khi số lượng đỉnh tăng lên, bài toán ngày càng khó giải hơn.

Một ứng dụng thực tế của bài toán này là xếp thời khóa biểu đại học. Tại một trường đại học lớn, thời khóa biểu phải được lập sao cho không sinh viên nào có các lớp trùng giờ. Mỗi lớp học có thể được biểu diễn bằng một đỉnh trong đồ thị, còn các cạnh biểu diễn những sinh viên chung giữa các lớp. Điều này đảm bảo không có hai lớp có chung sinh viên được xếp cùng thời điểm. Ngoài ra còn có các ràng buộc về sức chứa phòng, thời gian ưu tiên của giảng viên và việc phân bổ đều các lớp trong tuần. Vì vậy, cần gán khung giờ và phòng học cho các lớp sao cho không có hai lớp kề nhau nào dùng cùng một khung giờ. Có thể thực hiện điều này bằng cách tô ba màu đồ thị.

Bây giờ, hãy hình dung lịch học cuối cùng phải được một công ty kiểm toán bên ngoài xác minh. Do các quy định cụ thể về quyền riêng tư, trường đại học không thể chia sẻ thông tin đăng ký học chi tiết của sinh viên với kiểm toán viên. Thay vào đó, trường phải chứng minh rằng lịch học cuối cùng đáp ứng các ràng buộc bắt buộc mà không tiết lộ cụ thể sinh viên nào đăng ký lớp nào. 

Để làm vậy, trường đại học phải tạo một đồ thị trong đó mỗi đỉnh biểu diễn một lớp học. Một cạnh sẽ được vẽ giữa hai đỉnh nếu các lớp tương ứng có ít nhất một sinh viên chung. Trường sẽ gán khung giờ cho từng lớp để đảm bảo không có hai lớp kề nhau diễn ra đồng thời. Trường đại học sẽ cam kết lịch học hoàn chỉnh bằng một cơ chế cam kết mật mã. Quá trình này gồm việc tạo giá trị băm mật mã cho khung giờ được gán cho từng lớp và chia sẻ các giá trị băm với người xác minh mà không tiết lộ khung giờ. Sau đó, công ty kiểm toán bên ngoài sẽ chọn ngẫu nhiên các cặp lớp kề nhau để kiểm tra khung giờ được gán. Trường đại học sẽ tiết lộ các khung giờ đã cam kết cho cặp lớp kề nhau được chọn và cung cấp các cam kết ban đầu (tức các giá trị băm) để công ty kiểm toán bên ngoài xác minh những giá trị được tiết lộ. Các bước kiểm tra, tiết lộ và xác minh cuối cùng này được lặp lại cho đến khi công ty kiểm toán bên ngoài tin rằng không có lớp nào trùng giờ. Tôi đặc biệt khuyên bạn xem bản minh họa tương tác về khả năng tô 3 màu không tiết lộ của MIT để theo dõi các bước này diễn ra theo thời gian thực.

Trường đại học muốn chứng minh với công ty kiểm toán bên ngoài rằng họ biết một lịch học chính xác. Nói cách khác, họ muốn chứng minh với một bên khác rằng mình biết điều gì đó. Điểm hay của bài toán này là nó thuộc loại NP-đầy đủ.

NP-đầy đủ

Trong lý thuyết độ phức tạp tính toán, một bài toán là NP-đầy đủ khi:

• Với mọi đầu vào của bài toán, đầu ra là “có” hoặc “không”
• Khi câu trả lời là “có”, có thể chứng minh bằng một lời giải ngắn
• Tính đúng đắn của mỗi lời giải phải có thể được xác minh nhanh chóng và một thuật toán vét cạn có thể tìm ra lời giải bằng cách thử mọi lời giải khả dĩ

Các bài toán NP-đầy đủ rất quan trọng vì chúng đại diện cho những bài toán khó nhất trong lớp NP (tức một nhóm các câu đố rất khó, trong đó việc xác minh một lời giải phỏng đoán là dễ trong thời gian đa thức, nhưng việc tìm lời giải lại khó). Những bài toán này đáng chú ý nhờ khả năng mô phỏng phổ quát. Nghĩa là nếu có thể giải nhanh một bài toán NP-đầy đủ, chúng ta có thể quy giản hoặc biến đổi bất kỳ bài toán NP nào thành một bài toán NP-đầy đủ và tìm lời giải trong thời gian đa thức. Việc xác minh lời giải cho các bài toán NP-đầy đủ cũng dễ dàng. 

Do đó, chúng ta có cả một lớp bài toán có thể được chứng minh hiệu quả bằng bằng chứng không tiết lộ. Ví dụ:

• Bài toán người bán hàng — Cho danh sách các thành phố và khoảng cách giữa từng cặp, hãy tìm tuyến đường ngắn nhất có thể đi qua mỗi thành phố đúng một lần rồi quay về thành phố xuất phát. Bài toán này có nhiều ứng dụng trong logistics, lập kế hoạch tuyến đường, sản xuất và quản lý chuỗi cung ứng
• Bài toán ba lô — Cho một tập hợp vật phẩm, hãy xác định số lượng từng vật phẩm cần đưa vào một bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng một giới hạn cho trước và tổng giá trị lớn nhất có thể. Đây là bài toán phổ biến trong lĩnh vực tài chính và phân bổ tài nguyên
• Lập lịch công việc — Cho một tập hợp công việc với thời lượng và thời hạn cụ thể, hãy xếp lịch chúng trên một máy duy nhất để giảm thiểu tổng mức phạt do công việc trễ hạn. Bài toán này có nhiều ứng dụng trong điện toán, sản xuất và quản lý dự án

Ngoài ra, định lý Cook-Levin phát biểu rằng bài toán thỏa mãn Boolean là NP-đầy đủ. Nghĩa là bất kỳ bài toán nào có các biến có thể được thay thế bằng giá trị đúng hoặc sai sao cho cuối cùng biểu thức cho kết quả đúng đều có thể được biến đổi thành một bài toán NP-đầy đủ. Điều này hàm ý rằng bất kỳ bài toán nào có thể quy giản thành một chuỗi câu hỏi đúng và sai đều có thể được chứng minh hiệu quả bằng bằng chứng không tiết lộ.

Các thuộc tính của bằng chứng không tiết lộ

Do độ phức tạp và tầm quan trọng của các bài toán NP-đầy đủ, việc chứng minh lời giải cho lớp bài toán này một cách hiệu quả và an toàn trở nên thiết yếu. Bằng chứng không tiết lộ cung cấp một phương pháp thực hiện điều đó mà không làm tổn hại đến quyền riêng tư của thông tin liên quan. Goldwasser, Micali và Rackoff đề xuất rằng mọi bằng chứng không tiết lộ phải đáp ứng các thuộc tính sau:

• Tính đầy đủ — người Chứng minh cuối cùng sẽ thuyết phục được người Xác minh nếu họ trung thực
• Tính đúng đắn — người Chứng minh gian lận sẽ không bao giờ thuyết phục được người Xác minh về một mệnh đề sai
• Tính không tiết lộ — tương tác giữa người Chứng minh và người Xác minh chỉ cho biết một mệnh đề có đúng hay không và không tiết lộ gì khác

Bằng cách tận dụng các thuộc tính mạnh mẽ của bằng chứng không tiết lộ, chúng ta có thể chứng minh các sự kiện hoặc việc biết một số thông tin trong nhiều bối cảnh khác nhau, vừa bảo vệ quyền riêng tư vừa đảm bảo độ chính xác. Trong các phần sau, chúng ta sẽ khám phá lý do điều này đặc biệt giá trị với những ứng dụng đòi hỏi mức độ bảo mật và hiệu quả cao, chẳng hạn như blockchain.

Tương tác và không tương tác

Bằng chứng không tiết lộ thường có cùng cấu trúc ba bước:

• Người chứng minh tạo lời giải cho phép tính (tức nhân chứng), sau đó gửi một cam kết về câu trả lời của nhân chứng
• Người xác minh phản hồi bằng một giá trị thử thách được tạo ngẫu nhiên
• Người chứng minh tính toán bằng chứng cuối cùng dựa trên cam kết và thử thách

Cấu trúc này vốn mang tính tương tác — người chứng minh tuyên bố rằng họ biết điều gì đó, còn người xác minh liên tục đưa ra thử thách cho đến khi xác suất người chứng minh đánh lừa họ trở nên không đáng kể. Cách này không lý tưởng cho hầu hết ứng dụng vì người chứng minh cần nhận một hoặc nhiều phản hồi trước khi tạo được bằng chứng hoàn chỉnh. Thiết lập này vốn có các thách thức sau:

• Người xác minh có thể thông đồng với người chứng minh, cho phép họ làm giả bằng chứng
• Người xác minh có thể tạo bằng chứng giả
• Người xác minh phải lưu trữ các giá trị bí mật ở đâu đó, có thể dễ bị rò rỉ hoặc tấn công

Phương pháp heuristic Fiat-Shamir là một kỹ thuật chuyển bằng chứng tri thức tương tác thành chữ ký số dựa trên bằng chứng đó. Nhờ vậy, một sự kiện có thể được chứng minh công khai mà không tiết lộ thông tin nền tảng. Ý tưởng là thay vì để người xác minh gửi một giá trị thử thách ngẫu nhiên cho người chứng minh, người chứng minh có thể tự tính chữ ký số này bằng một hàm ngẫu nhiên, chẳng hạn như một hàm băm mật mã tốt. Vì vậy, thay vì để người xác minh kiểm tra phép tính tại 500 vị trí khác nhau để đảm bảo tất cả đều chính xác, người chứng minh tính gốc Merkle của phép tính, dùng gốc Merkle để chọn giả ngẫu nhiên 500 chỉ mục và cung cấp 500 nhánh Merkle dữ liệu tương ứng. Ý tưởng cốt lõi là người chứng minh không biết phải tiết lộ những nhánh nào cho đến sau khi dữ liệu đã được cam kết.

Độc giả tinh ý có thể nhận ra một lỗ hổng nghiêm trọng khi áp dụng lấy mẫu ngẫu nhiên để kiểm tra nhanh các phép tính — phép tính vốn rất mong manh. Người chứng minh độc hại có thể đảo một bit duy nhất ở giữa phép tính mà người xác minh không bao giờ phát hiện ra. Làm thế nào người xác minh có thể kiểm tra mọi phần của phép tính mà không xem xét riêng từng phần? Đa thức.

Tuy nhiên, chúng ta cần hiểu khá nhiều kiến thức toán học trước khi có thể bàn về đa thức.

Toán học đằng sau bằng chứng không tiết lộ

Đây không phải phần giới thiệu chuyên sâu về các lĩnh vực toán học sau đây — bản thân mỗi phần đều có thể trở thành một bài viết riêng. Mục đích ở đây là cung cấp phần giới thiệu ngắn gọn để bạn bắt đầu hiểu các nền tảng toán học đằng sau bằng chứng không tiết lộ và cách chúng thực sự hoạt động ở cấp độ tổng quan.

Bài viết này cũng sẽ giới thiệu ký hiệu toán học chuẩn. Ví dụ, trong tiểu mục sau về Lý thuyết tập hợp, chúng ta sẽ giới thiệu các ký hiệu ∈, ∉ và ⊆. Xét cho cùng, tất cả các ký hiệu này đều là phần giữ chỗ cho một thứ khác. Bằng chứng không tiết lộ không phải chủ đề dành cho người mới bắt đầu; vì vậy, phần lớn bài viết về chủ đề này không thân thiện với người mới. Chúng sẽ không đi sâu giải thích ý nghĩa của các ký hiệu này, và mặc định rằng người đọc hiểu ký hiệu đó. Việc giới thiệu các ký hiệu ngay lúc này rất quan trọng để chúng bớt đáng sợ hơn với những ai muốn tìm hiểu sâu về bằng chứng không tiết lộ. Đừng quá sa đà vào ký hiệu. Hãy kiên trì, vì sẽ đến lúc bạn nhìn vào các ký hiệu này và thấy những khái niệm nền tảng thay vì chỉ thấy một chữ cái Hy Lạp nào đó.

Lý thuyết tập hợp

Lý thuyết tập hợp là một nhánh toán học nghiên cứu các tập hợp đối tượng. Một tập hợp là tập hợp gồm các đối tượng phân biệt. Những đối tượng phân biệt này được gọi là phần tử hay thành viên của tập hợp. Ví dụ, hãy xem xét một tập hợp trái cây:

Dấu ngoặc nhọn được dùng trong ký hiệu tập hợp để bao quanh một tập hợp các phần tử và biểu diễn một tập hợp. Nhờ vậy, chúng ta biết apple, orange, pear và banana thuộc tập hợp, còn một thứ như “potato” thì không. Ký hiệu ∈ được dùng để chỉ quan hệ thuộc tập hợp và được đọc là “là một phần tử của”. Tương tự, ∉ biểu thị rằng một phần tử không thuộc một tập hợp cho trước. Vì vậy, ta có thể viết:

Ta sẽ đọc biểu thức này là “apple là một phần tử của tập hợp Fruit và potato không phải là một phần tử của tập hợp Fruit”.

Tập con

Chúng ta cũng có thể có các tập hợp được cấu thành từ những tập hợp khác. Tập con là một tập hợp chỉ chứa các phần tử có trong một tập hợp khác. Chẳng hạn, nếu có:

Ta có thể nói tập hợp Citrus là tập con của tập hợp lớn hơn AllFruits. Ta cũng có thể dùng tập hợp Fruit trước đó để nói Fruit là tập con của tập hợp lớn hơn AllFruit. Theo ký hiệu tập hợp, ta viết như sau:

Tại sao điều này quan trọng?

Lý thuyết tập hợp rất cần thiết để hiểu khái niệm phạm vi và ràng buộc. Trong các phần tiếp theo về lý thuyết số và số học mô-đun, chúng ta sẽ khám phá ý tưởng các số nằm trong một phạm vi nhất định. Ví dụ, ta có thể có một tập hợp các giá trị khả dĩ cho khóa mật mã:

Ở đây, K xác định phạm vi của tất cả khóa khả dĩ. Chúng ta có thể xây dựng bằng chứng không tiết lộ sao cho một số ràng buộc nhất định được áp dụng cho tập hợp này, khiến chỉ một số giá trị nhất định là hợp lệ. Ví dụ, ta có thể quy định khóa phải là một số từ 1 đến 5. 

Do đó, lý thuyết tập hợp cung cấp ngôn ngữ, công cụ và ký hiệu nền tảng để xác định và phân tích các tập hợp đầu vào, đầu ra và trạng thái khả dĩ trong giao thức mật mã. Trong bằng chứng không tiết lộ, ta thường cần chứng minh rằng một phần tử thuộc một tập hợp hoặc phạm vi cụ thể mà không tiết lộ chính phần tử đó.

Tôi khuyên bạn xem Khan Academy để làm một số bài tập rất hữu ích về ký hiệu tập hợp cơ bản.

Lý thuyết số

Lý thuyết số là một nhánh toán học nghiên cứu số nguyên và các hàm số học. Ta có thể định nghĩa số nguyên là tập hợp các số không có phần thập phân (tức các số không phải phân số), bao gồm số dương, số âm và số không. Có thể định nghĩa tập hợp số nguyên chính thức hơn như sau:

Ở đây, ℤ được dùng để biểu thị tập hợp số nguyên, còn dấu ba chấm cho thấy các số nguyên trải dài từ âm vô cực đến dương vô cực. Ví dụ, số 12 là một số nguyên và -1978649832794275 cũng là một số nguyên.

Số hữu tỉ

Số hữu tỉ là những số có thể biểu diễn dưới dạng phân số với mẫu số (tức số nằm dưới gạch phân số thông thường, một số chia) khác không. Ví dụ, $(\frac{1}{2}), 74, (\frac{2}{3})$ đều là số hữu tỉ. Chính thức hơn, ta có thể định nghĩa số hữu tỉ là tập hợp các số có thể biểu diễn dưới dạng phân số pq, trong đó p là tử số, q là mẫu số và q khác 0. Ký hiệu ℚ được dùng để biểu thị số hữu tỉ. Theo ký hiệu tập hợp, ta viết:‍

‍Thoạt nhìn biểu thức này có vẻ đáng sợ, nhưng nó mô tả chính xác câu trước đó. Ta sẽ đọc thuật ngữ toán học trông kỳ lạ này là “Q là tập hợp tất cả phân số p trên q, trong đó p và q là số nguyên, còn q không bằng không”. 

Số thực

Số thực bao gồm cả số hữu tỉ và số vô tỉ. Số vô tỉ là những số không thể biểu diễn dưới dạng phân số đơn giản và có phần thập phân vô hạn không tuần hoàn. Ví dụ, pi (tức π) và $\sqrt{2}$ (tức 1.4.1421…) là các số vô tỉ. Tạm thời chúng ta sẽ bỏ qua ký hiệu tập hợp, nhưng cần lưu ý rằng số thực được biểu thị bằng ký hiệu ℝ.

Tại sao điều này quan trọng?

Lý thuyết số có mối liên hệ sâu sắc với lý thuyết tập hợp vì nó nghiên cứu các tập hợp số cụ thể (ví dụ: số hữu tỉ). Các tập hợp này thường là cơ sở để xác định phạm vi và ràng buộc trong các bài toán toán học và mật mã. 

Ta cũng có thể thấy lý thuyết số và lý thuyết tập hợp liên kết với nhau như thế nào. Ví dụ, có thể nói tập hợp mọi số nguyên ℤ là tập con của các số hữu tỉ ℚ. Điều này thể hiện rõ trong định nghĩa về số thực bằng ký hiệu tập hợp ở trên, khi ta nêu rằng tử số và mẫu số là số nguyên.

Số học mô-đun

Số học mô-đun, còn gọi là số học đồng hồ, là một hệ thống phép toán số học trên số nguyên, trong đó các số “quay vòng” sau khi đạt đến một giá trị cụ thể gọi là mô-đun. Ý tưởng ở đây là thay vì làm việc với một tập hợp số vô hạn, chúng ta làm việc với n số dương đầu tiên.

Đồng hồ

Hãy xem xét một chiếc đồng hồ kim (tôi không thích việc ở thời đại này vẫn phải nói rõ rằng nó có kim và không phải đồng hồ điện tử) với các số từ 1 đến 12. Nếu bây giờ là 11 giờ và muốn biết thời gian sau hai tiếng, ta sẽ không nhận được 13 giờ. Thay vào đó, đồng hồ sẽ quay vòng về 1 giờ. Có thể biểu diễn điều này là $11 + 2 \equiv 1 \pmod{12}$ . Biểu thức toán học chuẩn ở đây là $13 \bmod 12 = 1$. Các lập trình viên sẽ quen với việc dùng phép toán modulo theo dạng $13 \% 12 = 1$.

Phép toán modulo

Khi viết n mod k, điều đó có nghĩa là ta muốn tìm số dư khi chia n cho k. Đây được gọi là phép toán modulo. Ví dụ:

• 25 mod 3 nghĩa là chia 25 cho 3, cho số dư là 1 vì $25 = 8 \times 3 + 1$
• 15 mod 4 nghĩa là chia 15 cho 4, cho số dư là 3 vì $15 = 3 \times 4 + 3$

Trong số học mô-đun, số dư luôn không âm.

Tại sao điều này quan trọng?

Hiểu số học mô-đun là điều thiết yếu vì nó cung cấp góc nhìn về cách các số vận hành dưới những ràng buộc, một yếu tố quan trọng đối với mật mã học. Số học mô-đun là nền tảng của nhiều thuật toán mật mã và được sử dụng rộng rãi trong khoa học máy tính, kỹ thuật cũng như bất kỳ lĩnh vực nào đòi hỏi xử lý và mã hóa dữ liệu an toàn.

Hãy xem xét phép tính x + y = z. Nếu làm việc với một trường hữu hạn được xác định bởi số nguyên tố p = 17 (chúng ta sẽ sớm tìm hiểu phần này. Hiện tại, hãy coi đó là tập hợp mọi số nguyên từ 0 đến 16 và quay vòng tại 17). Phép tính trong trường này sẽ là (x + y) mod p = z. Nếu x = 12 và y = 15, phép tính sẽ là:‍

Việc sử dụng số học mô-đun ở đây cho phép chúng ta thực hiện phép tính trong một phạm vi giá trị có thể quản lý, được xác định bởi số nguyên tố p. Điều này đặc biệt quan trọng vì máy tính và bộ xử lý có không gian hữu hạn, nên chúng ta thường làm việc với các số nguyên có kích thước cố định như u32 hoặc u64. Số học mô-đun đảm bảo các giá trị luôn nằm trong những giới hạn này. Ngoài ra, việc sử dụng số nguyên tố bổ sung thêm một lớp phức tạp. Điều này rất quan trọng từ góc độ mật mã vì nó tăng cường bảo mật và giúp một số thuộc tính toán học trở nên dễ dự đoán và đáng tin cậy hơn.

Ví dụ, số học mô-đun được dùng trong zk-SNARKs để đảm bảo các giá trị tính toán luôn nằm trong những giới hạn cụ thể, dễ quản lý. Nó cũng được dùng để tạo các mạch số học trên một tập hợp số cho trước. Điều này cho phép chúng ta biểu diễn phép tính đồng thời đảm bảo chúng có thể được xác minh hiệu quả. Ở đây, người chứng minh phải chứng minh rằng họ đã thực hiện phép tính này mà không tiết lộ các giá trị x, y và z.

Tôi đặc biệt khuyên bạn xem bộ bài tập của Art of Problem Solving và bài luyện tập số học mô-đun của Joseph Zoller để có thêm kinh nghiệm thực hành giải các bài toán số học mô-đun. 

Lý thuyết nhóm

Lý thuyết nhóm là một nhánh toán học nghiên cứu các cấu trúc đại số được gọi là nhóm. Nhóm là một tập hợp các phần tử cùng với một phép toán thỏa mãn các điều kiện sau, được gọi là các tiên đề nhóm:

• Tính đóng — Kết quả của mọi phép tính số học sẽ là một phần tử khác trong tập hợp
• Tính kết hợp — Khi thực hiện cùng một phép toán trên ba phần tử trở lên, cách nhóm các phần tử không ảnh hưởng đến kết quả; kết quả vẫn giống nhau
• Phần tử đơn vị — Có một phần tử mà khi thực hiện phép toán với bất kỳ phần tử nào khác, giá trị của phần tử kia không thay đổi
• Phần tử nghịch đảo — Với mỗi phần tử, có một phần tử khác mà khi thực hiện phép toán giữa chúng sẽ cho ra phần tử đơn vị

Về mặt chính thức, chúng được định nghĩa như sau:

• Tính đóng — Nếu a và b là thành viên của nhóm, thì kết quả của phép toán (thường được ký hiệu là $a \times b$, $ab$, $a \circ b$, hoặc $ab$) cũng là thành viên của nhóm. Về mặt chính thức, ta có thể viết $\forall a, b \in G \mid a \circ b \in G$. Có thể đọc là: “với mọi giá trị của các phần tử a và b trong tập hợp G, kết quả của phép toán giữa a và b thuộc G”
• Tính kết hợp — Nếu a, b và c là thành viên của nhóm, thì (ab)c = a(cb). Về mặt chính thức, ta có thể viết $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Có thể đọc là: “với mọi giá trị của các phần tử a, b và c trong tập hợp G, phép toán giữa a và b, sau đó với c, bằng phép toán giữa a với kết quả của phép toán giữa b và c
• Phần tử đơn vị — Tồn tại một phần tử e trong nhóm sao cho với mọi phần tử a trong nhóm, phép toán $e \circ a = a \circ e = a$. Về mặt chính thức, ta viết $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Có thể đọc là “tồn tại một phần tử e trong tập hợp G, trong đó với mọi phần tử a trong tập hợp G, phép toán giữa e rồi đến a bằng phép toán giữa a rồi đến e, và đều bằng a
• Phần tử nghịch đảo — Với mỗi phần tử a trong nhóm, tồn tại một phần tử b trong nhóm sao cho $a \circ b = b \circ a = e$, trong đó e là phần tử đơn vị. Về mặt chính thức, ta viết $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Có thể đọc là “với mọi giá trị của phần tử a trong tập hợp G, tồn tại một phần tử b trong tập hợp G, trong đó phép toán giữa a rồi đến b bằng phép toán giữa b rồi đến a, và đều bằng phần tử đơn vị”

Chúng ta có thể phân tích tất cả thuật ngữ toán học này thành nội dung dễ hiểu hơn bằng một ví dụ. Hãy xét tập hợp số nguyên với phép cộng. Có thể nói tập hợp này tạo thành một nhóm vì nó thỏa mãn cả bốn tiên đề nhóm:

• Tính đóng — Nếu cộng hai số nguyên với nhau, kết quả là một số nguyên khác
• Tính kết hợp — $(5 + 4) + 3 = 5 + (4 + 3)$
• Phần tử đơn vị — Số không được xem là phần tử đơn vị vì cộng bất kỳ số nguyên nào với không cũng không làm thay đổi giá trị của số đó. Ví dụ, $7 + 0 = 0 + 7 = 7$
• Phần tử nghịch đảo — Nghịch đảo của bất kỳ số nguyên nào là số đối của nó vì cộng hai số lại sẽ cho ra phần tử đơn vị. Ví dụ, $5 + (-5) = 0$. Ta có thể tổng quát hóa thành $n + (-n) = 0$

Ta cũng có thể mở rộng sang một ví dụ khó hơn, chẳng hạn tập hợp các số hữu tỉ khác không $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ với phép nhân. Tập hợp này cũng tạo thành một nhóm:

• Tính đóng — Nhân hai số hữu tỉ khác không sẽ cho ra một số hữu tỉ khác không
• Tính kết hợp — $ab \times cd \times ef = ab \times (cd \times ef)$
• Phần tử đơn vị — Số 1 được xem là phần tử đơn vị vì nhân bất kỳ số hữu tỉ khác không nào với một cũng không làm thay đổi giá trị của nó. Ví dụ, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Phần tử nghịch đảo — Nghịch đảo của bất kỳ số hữu tỉ khác không nào là số nghịch đảo của nó (tức đổi chỗ tử số và mẫu số), vì phép nhân này sẽ bằng 1, là phần tử đơn vị. Ví dụ, $\frac{3}{5} \times \frac{5}{3} = 1$

Nhóm con

Nhóm con là một nhóm nằm trong một nhóm khác. Nếu nói nhóm con H của nhóm G là một tập con của G, ta cần thỏa mãn các tiên đề nhóm sau:

• Tính đóng — Nếu a và b thuộc H, thì kết quả của phép toán giữa chúng cũng phải thuộc H
• Tính kết hợp — Tiên đề này được kế thừa từ nhóm lớn hơn G 
• Phần tử đơn vị — Phần tử đơn vị của G cũng phải thuộc H 
• Phần tử nghịch đảo — Với mọi phần tử a trong H, phải có một phần tử b cũng thuộc H sao cho ab và ba đều bằng phần tử đơn vị

Ví dụ kinh điển ở đây là tập hợp số nguyên chẵn với phép cộng là một nhóm con của tập hợp số nguyên với phép cộng:

• Tính đóng — Cộng hai số nguyên chẵn sẽ cho ra một số nguyên chẵn khác
• Tính kết hợp — Tiên đề này được kế thừa từ số nguyên. Ví dụ, $2 + (4 + 6) = (2 + 4) + 6$
• Phần tử đơn vị — Số không được xem là phần tử đơn vị vì cộng bất kỳ số nguyên chẵn nào với không cũng không làm thay đổi giá trị của nó. Số không cũng thuộc tập hợp số nguyên
• Phần tử nghịch đảo — Nghịch đảo của mọi số chẵn cũng là một số chẵn. Ví dụ, nghịch đảo của 4 là -4 vì $4 + (-4) = 0$, chính là phần tử đơn vị

Ta có thể áp dụng điều này cho một ví dụ khó hơn. Hãy xét tập hợp tất cả số hữu tỉ khác không (tức ℚ*) với phép nhân. Ta có thể chứng minh ℚ* là nhóm con của tập hợp số thực khác không (tức ℝ*) với phép nhân:

• Tính đóng — Nếu a và b là các số hữu tỉ khác không, tích ab của chúng cũng là một số khác không. Ví dụ, $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$ là một số hữu tỉ khác không
• Tính kết hợp — Phép nhân các số hữu tỉ có tính kết hợp. Ví dụ, $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Phần tử đơn vị — Số 1 được xem là phần tử đơn vị vì nhân bất kỳ số hữu tỉ khác không nào với 1 cũng giữ nguyên giá trị. Ví dụ, $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Phần tử nghịch đảo — Mọi số hữu tỉ khác không $a = \frac{p}{q}$ đều có nghịch đảo nhân $a^{-1} = \frac{q}{p}$, cũng là một số hữu tỉ khác không và tích của chúng bằng phần tử đơn vị. Ví dụ, cho a = $\frac{2}{3}$. Nghịch đảo là $\frac{3}{2}$ vì $\frac{2}{3} \times \frac{3}{2} = 1$

Vì ℚ* thỏa mãn mọi tiên đề nhóm nên nó tạo thành một nhóm. Ngoài ra, do ℚ* là tập con của ℝ* và kế thừa các thuộc tính của nó, ta có thể khẳng định ℚ* là nhóm con của ℝ*.

Tại sao điều này quan trọng?

Nhóm tạo thành nền tảng cho nhiều khái niệm và cấu trúc toán học cũng như mật mã. Ví dụ, các hệ mật mã như RSA và mật mã đường cong elliptic phụ thuộc rất nhiều vào thuộc tính của nhóm và các phép toán trên nhóm. Hiểu nhóm con giúp chúng ta hiểu cấu trúc của các nhóm lớn hơn bằng cách xem xét những tập con nhỏ hơn, dễ quản lý hơn. Nhóm cung cấp khuôn khổ cơ bản để hiểu tính đối xứng, phép toán và phép biến đổi. Những kiến thức này sẽ rất cần thiết khi chúng ta chuyển sang phần tiếp theo về trường.

Trường

Một trường là tập hợp các phần tử thỏa mãn các tiên đề trường đối với phép cộng và phép nhân, đồng thời là một đại số chia giao hoán (tức luôn có thể thực hiện phép chia, ngoại trừ chia cho không). Các tiên đề trường thường được viết thành các cặp cộng và nhân:

• Phép cộng
  • Tính kết hợp: $(a + b) + c = a + (b + c)$
  • Tính giao hoán: $a + b = b + a$
  • Tính phân phối: $a(b + c) = ab + ac$
  • Phần tử đơn vị: $a + 0 = 0 + a = a$
  • Phần tử nghịch đảo: $a + (-a) = 0$
• Phép nhân
  • Tính kết hợp: $(ab)c = a(bc)$
  • Tính giao hoán: $ab = ba$
  • Tính phân phối: $(a + b)c = ac + bc$
  • Phần tử đơn vị: $(a + b)c = ac + bc$
  • Phần tử nghịch đảo: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Trường hữu hạn và phần tử sinh

Trường hữu hạn là một trường có số lượng phần tử giới hạn. Trường hữu hạn còn được gọi là trường Galois. Số lượng phần tử được gọi là cấp hoặc lực lượng của trường. Số lượng phần tử luôn là một lũy thừa của số nguyên tố. Điểm hay của trường hữu hạn là mọi phép toán số học được thực hiện trên các phần tử trong trường đều cho kết quả vẫn thuộc trường. Đó là vì mọi phép toán đều được thực hiện theo modulo cấp của trường, khiến các giá trị quay vòng.

Mỗi trường hữu hạn đều có một phần tử sinh. Phần tử sinh có thể tạo ra mọi phần tử trong trường thông qua phép lũy thừa. Điều này nghĩa là ta có thể lấy phần tử sinh và tăng số mũ của nó từng đơn vị cho đến khi có được tất cả phần tử trong trường. Vì vậy, phần tử sinh là một phần tử trong trường mà các lũy thừa của nó có thể tạo ra mọi phần tử khác không của trường.

Ví dụ, hãy hình dung ta lấy tập hợp số nguyên theo modulo p = 7 và có trường $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Nếu muốn tìm phần tử sinh g của $\mathbb{Z}_7^*$ (tức nhóm nhân của các phần tử khác không thuộc $\mathbb{Z}_7$, ta cần đảm bảo rằng g1, g2,g3, v.v. có thể tạo ra mọi phần tử khác không của trường.

Hãy kiểm tra xem 3 có phải là phần tử sinh không:

Các lũy thừa của 3 tạo ra mọi phần tử khác không của $\mathbb{Z}_7$. Vì vậy, 3 là một phần tử sinh của nhóm nhân $\mathbb{Z}_7^*$.

Tại sao điều này quan trọng?

Mật mã học là một ngành khoa học làm việc với các tập hợp hữu hạn. Kiến thức này tạo nên nền tảng thiết yếu để giải quyết các chủ đề như Bài toán logarit rời rạc, mã hóa, trao đổi Diffie-Hellman và đường cong elliptic. Các phần tử sinh cho phép thực hiện phép toán trên đa thức đã mã hóa mà không cần giải mã chúng (tức mã hóa đồng cấu). Nói cách khác, chúng ta có thể tính toán trên dữ liệu đã mã hóa trong khi vẫn bảo vệ quyền riêng tư của các giá trị nền tảng. Hiểu phần này là điều thiết yếu để nắm được khía cạnh không tiết lộ của bằng chứng không tiết lộ.

Tôi khuyên bạn truy cập Bill’s Security Site, nơi cung cấp một ví dụ tương tác về cách tạo trường hữu hạn bằng các tham số cụ thể và lý thuyết nền tảng trong Python. 

Hàm

Hàm là một biểu thức, quy tắc hoặc định luật xác định mối quan hệ giữa hai biến — biến độc lập và biến phụ thuộc. Hai biến này thường lần lượt được mô tả là nguyên nhân và kết quả. Mối quan hệ này thường được ký hiệu là y = f(x), đọc là “f của x”. Với mỗi giá trị x, có một giá trị y duy nhất, nghĩa là f(x) không thể có nhiều hơn một giá trị cho cùng một x.

Hàm có thể là một-một hoặc nhiều-một, thường được gọi là lực lượng. Điều này nghĩa là một giá trị x có thể ánh xạ đến một giá trị y duy nhất, hoặc nhiều giá trị x có thể ánh xạ đến cùng một giá trị y

Hãy hình dung một đường thẳng được xác định bởi $y = 3x + 4$. Đây là một hàm tuyến tính, trong đó thay một giá trị x vào sẽ trả về giá trị y tương ứng. Hai giá trị này kết hợp lại tạo thành một điểm trên đường thẳng. Ví dụ, ta có thể viết lại phương trình thành $f(x) = 3x + 4$ và tính khi x = 1, cho kết quả $f(1) = 7$. Hàm cũng có thể có nhiều biến. Ví dụ, hãy xét công thức tính diện tích tam giác: $A = \frac{bh}{2}$. Ở đây, A (tức diện tích) được xác định là hàm của cả b (tức đáy) và h (tức chiều cao).

Miền xác định và miền giá trị

Miền xác định của một hàm là tập hợp mọi giá trị đầu vào khả dĩ (tức các biến độc lập) mà hàm có thể nhận. Miền giá trị của hàm là tập hợp mọi giá trị đầu ra khả dĩ (tức các biến phụ thuộc) mà hàm có thể tạo ra.

Với hàm $y = 2x + 2$:

• Miền xác định là tất cả số thực vì mọi số từ âm vô cực đến dương vô cực đều dùng được. Ví dụ:
  • Nếu x = 2.5, thì $y = 2(2.5) + 2 = 7$ 
  • Nếu x = -9234525, thì $y = 2(-9234525) + 2 = -18469048$
• Miền giá trị cũng là tất cả số thực vì có thể tạo ra mọi số từ âm vô cực đến dương vô cực. Ví dụ:
  • Để tìm y = -50, ta giải -50 = 2x + 2, cho x = -26. 
  • Để tìm y = 0, ta giải 0 = 2x + 2, cho x = 0

Tại sao điều này quan trọng?

Hàm rất quan trọng để hiểu đa thức. Đa thức là các hàm đặc biệt có các biến được nâng lên những lũy thừa khác nhau cùng các hệ số tương ứng. Đa thức là cấu trúc đại số nền tảng, tạo cơ sở để xây dựng các giao thức mật mã. Trong phần tiếp theo, chúng ta sẽ tìm hiểu chi tiết về đa thức, xem xét các thuộc tính và ý nghĩa của chúng trong bằng chứng không tiết lộ.

Tôi khuyên bạn xem Paul’s Online Notes và làm các bài tập thực hành để hiểu rõ hơn về hàm.

Đa thức

Đa thức là một hàm gồm nhiều biến và hệ số, chỉ sử dụng các phép cộng, trừ, nhân và lũy thừa biến với số mũ nguyên không âm. Đa thức thường được viết dưới dạng:‍

Trong đó $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ là các hệ số và x là biến. Lũy thừa cao nhất của biến x có hệ số khác không được gọi là bậc của đa thức.

Đa thức có thể được phân loại thành đơn biến, chỉ gồm một biến (như dạng viết ở trên), hoặc đa biến, gồm nhiều biến (ví dụ: $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check là một ví dụ về giao thức sử dụng đa thức đa biến. Tuy nhiên, phần lớn bằng chứng không tiết lộ chỉ cần một biến.

Các tên gọi phổ biến dành cho đa thức dựa trên bậc của chúng là:

• Bậc 0 — Hằng số khác không (ví dụ: $P(x) = 6$)
• Bậc 1 — Tuyến tính (ví dụ: $P(x) = 2x - 7$)
• Bậc 2 — Bậc hai (ví dụ: $P(x) = 8x^2 - 3x + 1$)
• Bậc 3 — Bậc ba (ví dụ: $P(x) = 3x^3 - 4x$)

Nếu có hai đa thức không bằng nhau với bậc tối đa là $d$, chúng có thể giao nhau tại không quá $d$ điểm (ví dụ: nếu cho một hàm tuyến tính bằng một hàm bậc ba, chúng có thể giao nhau tối đa ba lần). Tính chất này xuất phát từ cách ta tìm các điểm chung. Muốn tìm giao điểm của hai đa thức, ta đặt chúng bằng nhau. Trong phần phụ sau, chúng ta sẽ thực hành tìm nghiệm của đa thức, tức là tìm nơi một đa thức cho trước giao với trục x. Định lý cơ bản của đại số phát biểu rằng một đa thức bậc $d$ có thể có tối đa $d$ nghiệm và do đó có tối đa $d$ điểm chung.

Nghiệm của đa thức 

Nghiệm, hay nghiệm không, của một đa thức là các giá trị của x khiến đa thức bằng không. Nói cách khác, nếu $P(x)$ là một đa thức thì nghiệm $r$ là một nghiệm của phương trình $P(r) = 0$. Để tìm nghiệm, chúng ta phải nắm rõ cách phân tích đa thức thành nhân tử. Phân tích thành nhân tử là tìm những đại lượng cần nhân với nhau để thu được một đại lượng cho trước. Ví dụ, có nhiều cách phân tích 12 thành nhân tử:

Một phương pháp phân tích thành nhân tử phổ biến là phân tích hoàn toàn số đó thành các thừa số nguyên tố dương. Khi phân tích, tốt nhất nên bắt đầu bằng ước chung lớn nhất (ƯCLN) của tất cả các số hạng. Ví dụ:

Trong ví dụ trên, cả hai số hạng (tức 6x và 3) đều chia hết cho 3 nên có ƯCLN là 3. Vì vậy, các nhân tử là 3 và $2x + 1$. Ta thực hiện ngược lại tính chất phân phối: $3 \times 2x$ và $3 \times 1$. Tìm nghiệm nghĩa là giải x khi $P(x) = 0$.

Việc phân tích thành nhân tử khá đơn giản với đa thức có hai số hạng. Khi có đồ thị, việc này còn trực quan hơn vì nghiệm chính là nơi đa thức giao với trục x. Tuy nhiên, từ bậc ba trở lên, bài toán có thể phức tạp hơn. Tôi khuyên bạn đọc bài Giải thích cách phân tích đa thức thành nhân tử để tìm hiểu sâu hơn. 

Bạn không cần nắm chính xác mọi sắc thái của việc phân tích các đa thức khác nhau thành nhân tử để đọc phần còn lại của bài viết này. Trong phạm vi bài viết, chúng ta quan tâm đến trường hợp một đa thức được đặt bằng một giá trị khác. Ở đây, ta quan tâm đến thời điểm một đa thức bằng không. Sau đó, ta sẽ xem xét khi một đa thức bằng một đa thức khác hoặc hiệu của hai đa thức đồng nhất bằng không (tức tất cả hệ số đều bằng không), qua đó cần kiểm tra xem một đa thức cho trước có các nghiệm nhất định hay không.

Bổ đề Schwartz-Zippel 

Bổ đề Schwartz-Zippel là một công cụ xác suất để kiểm tra xem một phương trình đa thức có luôn đúng hay không. Công cụ này tính giá trị của đa thức tại các điểm ngẫu nhiên rồi kiểm tra kết quả có bằng không hay không.

Hãy hình dung một phương trình phức tạp chứa các biến $x_1, x_2, \ldots, x_n$. Nếu phương trình này là một đa thức chứ không chỉ là tập hợp ngẫu nhiên của các số hạng, Bổ đề Schwartz_Zippel giúp ta xác minh liệu nó có đúng với mọi giá trị khả dĩ của các biến này hay không.

Cách hoạt động như sau:

• Gọi $P(x_1, x_2, \ldots, x_n)$ là một đa thức có tổng bậc d (tức tổng số mũ cao nhất trong bất kỳ số hạng nào)
• Chọn một tập hữu hạn S từ trường (tương tự như chọn một tập hợp số)
• Chọn ngẫu nhiên giá trị cho từng biến $x_1, x_2, \ldots, x_n$ từ tập S

Bổ đề phát biểu rằng xác suất để P bằng không tại các điểm được chọn ngẫu nhiên này không vượt quá $\frac{d}{S}$. Điều này có nghĩa là nếu đa thức không bằng không thì rất khó để nó tình cờ trông như bằng không. Tính chất này đặc biệt hữu ích cho các bằng chứng không tiết lộ, khi ta cần xác minh hiệu quả các đồng nhất thức đa thức.

Nội suy Lagrange

Nội suy Lagrange là phương pháp xây dựng một đa thức đi qua một tập hợp điểm cho trước. Đa thức Lagrange là đa thức có bậc nhỏ nhất đi qua từng điểm cho trước. Với n điểm, ta có thể tạo một đa thức bậc n-1 đi qua tất cả các điểm. Ví dụ, nếu có hai điểm trên một mặt phẳng, ta có thể xác định một đường thẳng đi qua cả hai điểm. Nếu có ba điểm trên một mặt phẳng, ta có thể xác định một đa thức bậc hai (tức $y = ax^2 + bx + c$) đi qua tất cả các điểm. Các trường hợp tiếp theo cũng tương tự.

Tại sao điều này đáng quan tâm?

Đa thức là một đối tượng toán học duy nhất có thể chứa lượng thông tin không giới hạn — hãy coi đa thức là một danh sách số nguyên và điều này sẽ trở nên hiển nhiên. Vì vậy, một phương trình duy nhất giữa các đa thức có thể biểu diễn số lượng không giới hạn các phương trình giữa những con số. Nếu ai đó có thể xác minh một phương trình cho trước giữa các đa thức, họ mặc nhiên xác minh đồng thời mọi phương trình khả dĩ. Đây là cách chúng ta bảo vệ các bằng chứng không tương tác trước hiểm họa từ người chứng minh độc hại và tránh phải dựa vào việc kiểm tra ngẫu nhiên từng phần của một phép tính cho trước. 

Đa thức còn có một số tính chất khiến chúng hữu ích cho việc tạo bằng chứng:

• Khi có đủ số điểm của một đa thức cho trước, toàn bộ đa thức có thể được tái dựng
• Một thay đổi nhỏ ở đầu vào của đa thức có thể dẫn đến thay đổi đáng kể ở đầu ra, giúp dễ phát hiện lỗi hơn
• Đa thức có thể phát hiện và sửa lỗi trong phép tính, tương tự như cách mã xóa giúp dữ liệu có khả năng chịu lỗi (đây là yếu tố thiết yếu trong cách Turbine hoạt động)

Bằng chứng không tiết lộ được dùng để chứng minh các phép tính nhất định. Đa thức vô cùng hữu ích cho mục đích này vì ta có thể tạo chúng với những đặc tính cụ thể. Giả sử bạn có một phép tính hoặc tập hợp điểm dữ liệu cần chứng minh. Cách dễ nhất là mã hóa chúng thành một đa thức rồi sử dụng các tính chất của đa thức để tạo bằng chứng:

• Mã hóa dữ liệu thành một đa thức $P(x)$ sao cho việc tính $P(x)$ tại những điểm nhất định cho ra dữ liệu gốc hoặc kết quả của một phép tính cho trước
• Để bảo đảm đa thức đáp ứng các tiêu chí cho trước (ví dụ: mọi giá trị đều nằm trong một khoảng), hãy tạo đa thức ràng buộc $C(x)$. Ví dụ, $C(x) = (P(x) - 0)(P(x) - 1)$ bảo đảm $P(x)$ bằng 0 hoặc 1
• Chuyển đổi bài toán thành việc chứng minh $P(x)$ đáp ứng những điều kiện nhất định đối với tập dữ liệu hoặc phép tính của bạn
• Tạo một đa thức đã biết $H(x)$ là bội của $P(x)$ và mã hóa các điều kiện này
• Người chứng minh cam kết các giá trị của $P(x)$ và mọi đa thức liên quan bằng cách tạo cây Merkle từ các kết quả tính, rồi gửi hàm băm gốc cho người xác minh
• Người xác minh chọn ngẫu nhiên một vài điểm và yêu cầu người chứng minh cung cấp giá trị của $P(x)$ và $C(x)$ tại các điểm đó
• Người xác minh đối chiếu các giá trị được cung cấp với hàm băm gốc đã cam kết và các quan hệ đa thức dự kiến

Kích thước của đa thức không quan trọng; vì sử dụng cam kết đa thức, ta có thể xác minh các phương trình giữa những đa thức trong thời gian ngắn. Đây là cách tạo bằng chứng cực kỳ ngắn gọn và hiệu quả. Mọi lỗi đều được khuếch đại và khi sử dụng các kỹ thuật như heuristic Fiat-Shamir, những bằng chứng này có thể trở thành không tương tác để bất kỳ ai cũng xác minh được mà không cần tương tác thêm. 

Để hiểu sâu hơn, tôi khuyên bạn thử các bài tập sau:

• Bài tập thực hành về đa thức
• Bài tập tìm nghiệm không của đa thức
• Phân tích đa thức thành nhân tử: Các bài toán rất khó kèm lời giải

Khan Academy cũng có một chương chuyên sâu về biểu thức, phương trình và hàm đa thức.

Để hiểu rõ hơn về cam kết đa thức, ta cần khám phá nền tảng mật mã học của các bằng chứng không tiết lộ.

Nền tảng mật mã học của bằng chứng không tiết lộ

Hãy cùng tìm hiểu mã hóa đối xứng và bất đối xứng.

Mã hóa đối xứng

Mã hóa đối xứng là kỹ thuật mã hóa sử dụng cùng một khóa để mã hóa bản rõ và giải mã bản mã. Khóa này thường được gọi là khóa bí mật hoặc khóa riêng vì việc sử dụng một khóa duy nhất đòi hỏi khóa đó phải được giữ bí mật. Tuy nhiên, điều này cũng có nghĩa là khóa bí mật phải được chia sẻ cho hai bên trước khi họ có thể giao tiếp an toàn. Do đó, việc quản lý và phân phối khóa bí mật một cách an toàn có thể gặp nhiều khó khăn và dễ bị rò rỉ nếu xử lý không đúng cách. Bất chấp nhược điểm này, mã hóa đối xứng vẫn nhanh, hiệu quả và cần ít sức mạnh tính toán cũng như bộ nhớ hơn các cơ chế mã hóa khác.

Các thuật toán mã hóa đối xứng phổ biến gồm:

Tiêu chuẩn mã hóa nâng cao (AES)

Tiêu chuẩn mã hóa nâng cao (AES) là một biến thể của mã khối Rijndael, được sử dụng rộng rãi trên toàn thế giới để bảo vệ dữ liệu. Thuật toán này hỗ trợ khóa có kích thước 128, 192 và 256 bit.

ChaCha20

ChaCha20 là một mã dòng hiện đại, hiệu quả do Daniel J. Bernstein phát triển. Đây là một biến thể của mã dòng Salsa20, tận dụng các phép toán cộng-xoay-XOR (ARX). Thuật toán ánh xạ một khóa 256 bit, một nonce 64 bit và một bộ đếm 64 bit thành một khối 512 bit của dòng khóa, nghĩa là người dùng có thể tìm đến bất kỳ vị trí nào trên dòng khóa một cách hiệu quả trong thời gian hằng số.

Dù mã hóa đối xứng mạnh mẽ và hiệu quả, nó đòi hỏi một phương thức trao đổi khóa an toàn. Một phương thức như vậy là trao đổi khóa Diffie-Hellman, cho phép hai bên chia sẻ khóa bí mật một cách an toàn qua kênh không an toàn. Tuy nhiên, phương thức này dựa trên các nguyên tắc mã hóa bất đối xứng mà chúng ta sẽ đề cập trong phần tiếp theo.

Mã hóa bất đối xứng

Mã hóa bất đối xứng, còn gọi là mã hóa khóa công khai, là phương pháp sử dụng một cặp khóa có liên quan (tức khóa công khai và khóa riêng) để mã hóa và giải mã thông tin. Khóa công khai được chia sẻ rộng rãi, còn khóa riêng được giữ bí mật. Khi muốn mã hóa một thông điệp, người gửi sử dụng khóa công khai của người nhận. Sau khi nhận, người nhận dùng khóa riêng tương ứng để giải mã thông điệp. Dữ liệu được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa riêng. Vì vậy, mã hóa bất đối xứng cho phép giao tiếp an toàn qua các kênh không an toàn vì khóa giải mã không bao giờ được chia sẻ.

Mã hóa bất đối xứng có ưu điểm là cung cấp mức bảo mật cao do khóa riêng không bao giờ được chia sẻ. Nó cũng đơn giản hóa việc phân phối khóa vì khóa công khai có thể được chia sẻ rộng rãi, đồng thời hỗ trợ chữ ký số. Tuy nhiên, mã hóa bất đối xứng tốn nhiều tài nguyên tính toán và chậm hơn mã hóa đối xứng. Việc quản lý các cặp khóa cũng có thể trở nên phức tạp, đặc biệt trong các hệ thống có nhiều người dùng và khi các cặp khóa không trực quan. 

Các thuật toán mã hóa bất đối xứng phổ biến gồm:

• Rivest-Shamir-Adleman (RSA) — một trong những hệ mật mã khóa công khai lâu đời và phổ biến nhất để truyền dữ liệu an toàn. Hệ này được phát triển vào thập niên 1970 và dựa trên độ khó thực tế của việc phân tích tích của hai số nguyên tố lớn thành nhân tử
• Mật mã đường cong elliptic (ECC) — một cách tiếp cận mật mã khóa công khai dựa trên cấu trúc đại số của đường cong elliptic trên trường hữu hạn. ECC cung cấp mức bảo mật tương đương RSA nhưng với kích thước khóa nhỏ hơn, giúp tính toán nhanh hơn và giảm yêu cầu lưu trữ. Solana sử dụng đường cong elliptic Ed25519 để tạo cặp khóa

Chữ ký số

Chữ ký số là một khía cạnh quan trọng của mật mã khóa công khai, cung cấp cách xác minh tính xác thực và toàn vẹn của thông điệp, phần mềm hoặc tài liệu số. Chữ ký số được tạo bằng khóa riêng của người gửi và bất kỳ ai có quyền truy cập khóa công khai tương ứng đều có thể xác minh. Điều này bảo đảm thông điệp được gửi bởi người gửi hợp lệ và chưa bị sửa đổi.

Các thuật toán phổ biến dùng cho chữ ký số gồm:

• Thuật toán chữ ký số (DSA) — phương pháp dựa trên lũy thừa mô-đun (tức phép lũy thừa được thực hiện theo một mô-đun) và bài toán logarit rời rạc
• Thuật toán chữ ký số đường cong elliptic (ECDSA) — một biến thể của DSA sử dụng mật mã đường cong elliptic để cung cấp mức bảo mật cao hơn với kích thước khóa nhỏ hơn

Bài toán logarit rời rạc

Bài toán logarit rời rạc là bài toán tìm số mũ k trong phương trình $g^k \equiv h \pmod{p}$, trong đó:

• g là cơ số đã biết (tức một phần tử sinh)
• h là kết quả đã biết (tức một phần tử của nhóm)
• p là số nguyên tố (tức cấp của nhóm)
• k là số mũ chưa biết (tức logarit rời rạc của h theo cơ số g)

Nói cụ thể hơn, nếu biết các giá trị g, h và p, bài toán logarit rời rạc là tìm k. Ví dụ, với phương trình $2^k \equiv 9 \pmod{23}$, mục tiêu là tìm k.

Bài toán logarit rời rạc được xem là khó giải hiệu quả, đặc biệt với các số lớn. Vì độ khó này, nó tạo thành nền tảng bảo mật cho nhiều hệ thống mật mã, bao gồm Solana, Mã hóa ElGamal, các Thuật toán chữ ký số (tức DSA và ECDSA) và Trao đổi khóa Diffie-Hellman

Trao đổi khóa Diffie-Hellman

Trao đổi khóa Diffie-Hellman là phương pháp trao đổi khóa mật mã an toàn qua một kênh công khai.  Cách triển khai đơn giản và nguyên bản nhất (tức Diffie-Hellman trên trường hữu hạn) như sau:

• Alice và Bob công khai thống nhất hai số — một số nguyên tố lớn p (tức mô-đun) và một cơ số g (tức phần tử sinh), là căn nguyên thủy theo mô-đun p 
• Alice chọn một số nguyên bí mật a rồi gửi cho Bob $A \equiv g^a \pmod{p}$
• Bob chọn một số nguyên bí mật b rồi gửi cho Alice $B \equiv g^b \pmod{p}$
• Alice tính $s \equiv B^a \pmod{p}$ 
• Bob tính $s = A^b \pmod{p}$ 

Giờ đây Alice và Bob có cùng một giá trị bí mật. Lý do là cả hai phép tính đều cho ra cùng bí mật s vì:

Bí mật chung s này sau đó có thể được dùng làm khóa cho mã hóa đối xứng, cho phép Alice và Bob giao tiếp an toàn. Tính bảo mật của trao đổi khóa Diffie-Hellman dựa trên độ khó của bài toán logarit rời rạc. Nếu không biết các giá trị bí mật a và b, kẻ nghe lén không thể suy ra bí mật chung trong phạm vi tính toán khả thi. Đây được gọi là hàm một chiều — tương đối dễ tính nhưng cực kỳ khó đảo ngược.

Mặc dù trao đổi khóa Diffie-Helman trên trường hữu hạn an toàn và được sử dụng rộng rãi, nó cần kích thước khóa lớn để bảo đảm an toàn. Ví dụ, nếu Alice và Bob công khai chọn mô-đun 23, việc bẻ khóa sẽ dễ hơn nhiều vì chỉ có 23 kết quả khả dĩ của n mod 23. Do đó, phương pháp này có thể tốn nhiều tài nguyên tính toán và kém hiệu quả. Để giải quyết những thách thức này, mật mã đường cong elliptic (ECC) cung cấp một giải pháp thay thế hiệu quả hơn vì có cùng mức bảo mật với kích thước khóa nhỏ hơn đáng kể và tốc độ tính toán nhanh hơn.

Đường cong elliptic

Một đường cong elliptic được xác định bởi phương trình $y^2 = x^3 + ax + b$, trong đó a và b là các hằng số. Mật mã đường cong elliptic đơn giản là làm việc với các điểm trên một đường cong elliptic cho trước. Những đường cong này có nhiều tính chất độc đáo khiến chúng hữu ích trong mật mã học. Ví dụ:

• Cộng điểm — Với hai điểm P và Q trên một đường cong elliptic cho trước, tổng R = P + Q của chúng cũng là một điểm trên đường cong. Bài viết Hướng dẫn dễ hiểu về mật mã học cho bằng chứng không tiết lộ của Preethi Kasireddy giải thích rõ cách cộng các điểm trên một đường cong elliptic
• Phép nhân vô hướng — Với một điểm P trên một đường cong elliptic cho trước và một số nguyên k, phép nhân vô hướng là quá trình cộng điểm P với chính nó k lần. Kết quả sẽ là một điểm khác (tức kP) trên đường cong. Phép toán này được dùng để tạo khóa công khai từ khóa riêng
• Bài toán logarit rời rạc — Bài toán logarit rời rạc trên đường cong elliptic khó giải hơn nhiều so với phiên bản trên số nguyên. Với các điểm P và q = kP, việc xác định k là bất khả thi về mặt tính toán nếu các tham số đường cong được chọn đúng. Điều này có nghĩa là đường cong elliptic cung cấp mức bảo mật tương đương các hệ thống truyền thống nhưng dùng kích thước khóa nhỏ hơn nhiều, nhờ đó hiệu quả hơn

Với kiến thức mới về lý thuyết nhóm, ta có thể nói rằng một số phương trình đường cong elliptic sẽ thỏa mãn nhóm tiên đề sau:

• Bất kỳ hai điểm nào cũng có thể được cộng để tạo ra điểm thứ ba
• Thứ tự cộng hai điểm không ảnh hưởng đến kết quả
• Nếu có nhiều hơn hai điểm cần cộng, thứ tự cộng không ảnh hưởng đến kết quả
• Có một phần tử đơn vị (tức cộng không vào bất kỳ điểm nào trên đường cong vẫn cho ra chính điểm đó)

Tôi đặc biệt khuyên bạn đọc Mật mã đường cong elliptic của Georgie Bumpus để tìm hiểu kỹ hơn về cấu trúc nhóm này. 

Đường cong elliptic cung cấp mức bảo mật tương đương các hệ mật mã truyền thống khác như RSA nhưng với kích thước khóa nhỏ hơn nhiều. Ví dụ, khóa 256 bit trong ECC cung cấp mức bảo mật tương đương khóa 3072 bit trong RSA. Điều này có lợi vì:

• Kích thước khóa nhỏ hơn giúp mã hóa và giải mã nhanh hơn
• Khóa và chứng chỉ cần ít không gian hơn
• Khóa nhỏ hơn làm giảm lượng dữ liệu được truyền, hữu ích trong các môi trường có băng thông hạn chế như blockchain

Đường cong Montgomery

Đường cong Montgomery là một dạng đường cong elliptic được xác định bởi phương trình $By^2 = x^3 + Ax^2 + x$ trên một trường hữu hạn, trong đó A và B là các hằng số, B khác không và A không phải -2 hoặc 2. Những đường cong này đặc biệt vì phép nhân đường cong elliptic có thể được triển khai hiệu quả hơn bằng thang Montgomery. 

Về cơ bản, thang Montgomery nhận một điểm P trên đường cong Montgomery và một số vô hướng k, khởi tạo hai điểm từ điểm vô cực đến P, rồi cập nhật từng bit của số vô hướng k từ bit quan trọng nhất đến điểm ít quan trọng nhất. Ý tưởng cốt lõi là duy trì hai điểm và cập nhật chúng bằng một chuỗi phép toán cố định, bất kể các bit của số vô hướng k.

Điều này quan trọng vì một số lý do:

• Nó chống được các cuộc tấn công kênh kề, tức mọi cuộc tấn công dựa trên thông tin bổ sung có thể thu thập được từ cách triển khai hoặc thiết kế một giao thức hay thuật toán. Đây là một chủ đề chuyên sâu thực sự đáng để tìm hiểu. Những kiểu tấn công này trải dài từ mức tiêu thụ điện năng thay đổi của phần cứng trong quá trình tính toán đến bức xạ điện từ bị rò rỉ
• Không cần tọa độ y vì phép nhân vô hướng có thể được thực hiện chỉ bằng tọa độ x
• Nó hoạt động trong thời gian hằng số, nghĩa là thời gian thực hiện một phép tính không phụ thuộc vào giá trị đầu vào

Đường cong Montgomery được sử dụng rộng rãi trong các giao thức mật mã, chẳng hạn như thuật toán X25519 để trao đổi khóa, sử dụng dạng Montgomery của đường cong Curve25519. Thuật toán này là nền tảng của truyền thông an toàn hiện đại, bao gồm các cách triển khai trong những giao thức phổ biến như TLS. 

Đường cong Edwards

Đường cong Edwards là một loại đường cong elliptic được xác định bởi phương trình $x^2 + y^2 = 1 + d x^2 y^2$, trong đó d là hằng số khác không và khác 1.  

Những đường cong này quan trọng vì:

• Hiệu quả trong các phép toán điểm — Phép cộng hai điểm trên đường cong Edwards hiệu quả hơn so với các dạng đường cong elliptic khác. Công thức cộng và nhân đôi điểm đơn giản hơn, đồng thời cần ít phép toán trên trường hơn, nên tính toán nhanh hơn
• Công thức cộng thống nhất — Đường cong Edwards sử dụng công thức cộng thống nhất, nghĩa là cùng một công thức có thể dùng cho cả phép cộng điểm và nhân đôi điểm. Điều này làm giảm nguy cơ lỗi triển khai và tăng cường bảo mật
• Tính đầy đủ — Với một số giá trị nhất định của d, đường cong Edwards có tính đầy đủ. Điều này nghĩa là quy tắc cộng bao quát mọi đầu vào khả dĩ mà không có ngoại lệ.
• Khả năng chống tấn công kênh kề — Giống đường cong Montgomery, đường cong Edwards chống được các cuộc tấn công kênh kề nhờ mẫu hoạt động đồng nhất và có thể dự đoán.

Một đường cong Edwards được sử dụng rộng rãi là Edwards25519, được xác định bởi phương trình $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$. Đường cong này nổi tiếng nhờ số học hiệu quả và kích thước khóa 256 bit. Cơ chế chữ ký của nó được triển khai trong nhiều giao thức và hệ thống bảo mật, bao gồm Solana, OpenSSH và Tor. Monero sử dụng Edwards25519 làm nền tảng để tạo cặp khóa.

Tại sao điều này đáng quan tâm?

Đường cong elliptic giữ vai trò thiết yếu trong các bằng chứng không tiết lộ nhờ hiệu quả và các đặc tính tăng cường bảo mật. Lưu ý: việc sử dụng đường cong elliptic cho phép tạo bằng chứng nhỏ hơn và nhanh hơn, yếu tố thiết yếu cho mọi cách triển khai thực tế. Chúng ta sẽ phân tích sâu hơn khi nói về các bước phát triển liên quan đến bằng chứng không tiết lộ, nhưng nhu cầu về bằng chứng nhỏ và nhanh là cực kỳ quan trọng trong môi trường tính toán cao với nhiều hạn chế về tài khoản và giao dịch. Đây là điều khiến bằng chứng không tiết lộ trở nên hấp dẫn khi xây dựng rollup, vì ta có thể tạo một bằng chứng ngắn gọn rằng mọi thao tác trên L2 đều hợp lệ rồi xác thực bằng chứng đó trên L1.

Cuối cùng, hãy coi đường cong elliptic là giải pháp thay thế cho số học mô-đun. Với đường cong elliptic, việc tìm một điểm cụ thể khó hơn đáng kể. Nếu ta sử dụng số học mô-đun truyền thống với $g^a \bmod n$, trong đó g là phần tử sinh, n là một số nguyên tố lớn và a là khóa bí mật. Như đã trình bày ở phần bài toán logarit rời rạc, bạn sẽ cần một số nguyên tố rất lớn để bảo vệ khóa bí mật. Đường cong elliptic cung cấp giải pháp thay thế hiệu quả hơn với kích thước khóa nhỏ hơn, mang lại cùng mức bảo mật nhưng cải thiện đáng kể hiệu suất.

Tính ngẫu nhiên

Mọi nội dung khác trong bài viết này sẽ trở nên vô nghĩa nếu không có tính ngẫu nhiên, một khía cạnh nền tảng của mật mã học. Làm sao có thể kỳ vọng một hệ thống an toàn nếu các giá trị của nó có thể dự đoán và bị thiên lệch? Tính ngẫu nhiên thực sự có thể khó đạt được, nhưng nó thiết yếu vì một số lý do:

• Tạo khóa — Khóa mật mã phải được tạo ngẫu nhiên để bảo đảm không thể dự đoán và an toàn
• Nonce và salt — Nonce (tức các số chỉ dùng một lần) và salt (tức các giá trị ngẫu nhiên được thêm vào dữ liệu trước khi băm) lần lượt ngăn chặn tấn công phát lại và bảo vệ trước tấn công tính toán trước
• Giao thức an toàn — Tính ngẫu nhiên được dùng để bảo đảm tính công bằng và bảo mật, ngăn khả năng dự đoán và các mẫu mà kẻ tấn công có thể khai thác

Hầu hết các trình tạo số ngẫu nhiên không thể tạo ra số ngẫu nhiên có thể được xác minh bằng mật mã. Điều này khiến chúng dễ bị thao túng và hạn chế các trường hợp sử dụng. Tuy nhiên, hàm ngẫu nhiên có thể xác minh giải quyết được vấn đề này.

Hàm ngẫu nhiên có thể xác minh

Hàm ngẫu nhiên có thể xác minh (VRF) là một nguyên thủy mật mã tạo ra đầu ra ngẫu nhiên và bằng chứng cho thấy đầu ra được tạo đúng cách từ một đầu vào cho trước. VRF phải không thể dự đoán, nghĩa là với bất kỳ ai không biết đầu vào bí mật, đầu ra của nó không thể phân biệt với một giá trị ngẫu nhiên. Tính bảo mật của nó dựa trên giả định RSA rằng rất khó tính $y = h^d \bmod n$ nếu không biết số mũ bí mật d, cùng với tính bảo mật của hàm băm H. 

Các bước chính của một VRF như sau:

• Tạo khóa — Người dùng tạo một cặp khóa RSA gồm (e, n) làm khóa công khai và (d, n) làm khóa riêng. Trong khóa công khai, e là số mũ và n là mô-đun. Trong khóa riêng, d là số mũ bí mật
• Tính toán — Với đầu vào x, người dùng tính đầu ra VRF y và bằng chứng π. Trước tiên, tính giá trị băm h = H(x), trong đó H là một hàm băm mật mã. Sau đó tính $y = h^d \bmod n$, đây là chữ ký RSA của giá trị băm. Cuối cùng, tính bằng chứng π = (h, y)
• Xác minh — Với khóa công khai (e, n), đầu vào x, đầu ra y và bằng chứng π = (h, y), bất kỳ ai cũng có thể xác minh tính chính xác của đầu ra VRF bằng cách kiểm tra giá trị băm h có bằng $H(x)$ hay không và kiểm tra $y^e \equiv h \pmod{n}$ để xác minh phương trình RSA‍

VRF thường được dùng trong các giao thức đồng thuận, nơi tính ngẫu nhiên cần vừa không thể dự đoán vừa có thể xác minh. Các L1, bao gồm Algorand, Cardano, Internet Computer và Polkadot, sử dụng VRF trong cơ chế đồng thuận để chọn ngẫu nhiên nhà sản xuất khối. Chainlink cung cấp Chainlink VRF làm lớp trừu tượng giữa người dùng và blockchain để tạo các giá trị công bằng theo xác suất và có thể xác minh. Pyth Entropy cũng cung cấp một nguồn ngẫu nhiên đáng tin cậy và an toàn.

Nghi lễ và thiết lập tin cậy

Nghi lễ mật mã là các giao thức hoặc sự kiện trong đó những phép tính mật mã quan trọng được thực hiện trong một môi trường an toàn, có kiểm soát. Có một số loại nghi lễ mật mã, gồm:

• Nghi lễ tạo khóa — Các nghi lễ này liên quan đến việc tạo khóa mật mã nhằm bảo đảm không có thực thể đơn lẻ nào kiểm soát quy trình tạo khóa
• Nghi lễ tạo tham số — Các nghi lễ này liên quan đến việc tạo các tham số mật mã để nhiều bên sử dụng
• Nghi lễ tính toán đa bên (MPC) — Các nghi lễ này có nhiều bên cùng thực hiện một phép tính mật mã nhằm bảo đảm không bên đơn lẻ nào có thể xâm phạm quy trình

Nghi lễ thiết lập tin cậy là một sự kiện hoặc quy trình đặc biệt được thiết kế để tạo ra tập hợp tham số mật mã cần thiết nhằm vận hành một giao thức mật mã. Trong phần về bằng chứng không tiết lộ tương tác và không tương tác, chúng ta đã xác định rằng bước đầu tiên của một bằng chứng là để người chứng minh và người xác minh thống nhất một giá trị sẽ được sử dụng. Trong nghi lễ thiết lập tin cậy, nhiều người tham gia đóng góp tính ngẫu nhiên cho quá trình thiết lập nhằm bảo đảm không người tham gia đơn lẻ nào kiểm soát quy trình. Mỗi người tham gia tạo một giá trị ngẫu nhiên rồi kết hợp nó với các giá trị do những người khác cung cấp. Đầu ra tổng hợp trở thành một tập hợp tham số mà mọi người có thể tin cậy. 

Quy trình này rất quan trọng vì nếu tất cả người tham gia thông đồng, họ có thể phá vỡ hệ thống bằng cách tạo bằng chứng cho một khẳng định không hợp lệ. Tuy nhiên, chỉ cần một người tham gia trung thực là đủ để bảo đảm tính an toàn của các tham số. 

Zcash từng nổi tiếng với việc sử dụng một nghi lễ tin cậy để khởi tạo các tính năng quyền riêng tư của chuỗi. Ethereum cũng tổ chức Nghi lễ KZG, một nghi thức công khai có phối hợp nhằm cung cấp nền tảng mật mã cho các nỗ lực mở rộng quy mô của họ (ví dụ: EIP-4844 / proto-danksharding). 

Lưu ý rằng một số hệ thống bằng chứng không tiết lộ, chẳng hạn như zk-STARK, không yêu cầu thiết lập tin cậy. Chúng ta sẽ tìm hiểu sâu hơn về nội dung này trong bài viết thứ hai.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu lý thuyết, toán học và mật mã học nền tảng cho các bằng chứng không tiết lộ. Đây là tất cả những gì bạn cần biết để bắt đầu trả lời câu hỏi bằng chứng không tiết lộ là gì. Giờ đây, chúng ta có thể bắt đầu áp dụng những kiến thức này vào các mạng như Solana để đóng góp cho cuộc thảo luận và quá trình phát triển chung của bằng chứng không tiết lộ.

Chúng tôi tiếp tục phân tích chủ đề này trong bài viết thứ hai, cũng là bài cuối cùng trong loạt bài hai phần về bằng chứng không tiết lộ, với tên gọi phù hợp là Bằng chứng không tiết lộ: Ứng dụng trên Solana. 

Nếu đã đọc đến đây, cảm ơn bạn, anon! Hãy nhập địa chỉ email bên dưới để không bỏ lỡ bất kỳ thông tin cập nhật nào về những điểm mới trên Solana. Sẵn sàng tìm hiểu sâu hơn? Khám phá các bài viết mới nhất trên blog Helius và tiếp tục hành trình Solana của bạn ngay hôm nay.

Tài nguyên bổ sung

• Tính ngẫu nhiên thực sự có tồn tại không?
• Đường cong elliptic — Computerphile
• Giới thiệu về lớp độ phức tạp NP-đầy đủ
• Các vấn đề về trao đổi khóa — Computerphile
• Chuyên đề về mật mã học của Khan Academy
• Mật mã khóa công khai — Computerphile
• Độ phức tạp tri thức của các hệ thống chứng minh tương tác