ArkStream Capital: Các mốc phát triển công nghệ chứng minh không kiến thức trong bốn mươi năm
Tuyển chọn TechFlowTuyển chọn TechFlow
ArkStream Capital: Các mốc phát triển công nghệ chứng minh không kiến thức trong bốn mươi năm
Bài viết này cung cấp một bản tổng quan hệ thống về các tài liệu lịch sử và nghiên cứu mới nhất trong gần bốn mươi năm qua về công nghệ chứng minh không kiến thức.
Chuyên sâu báo cáo Web3Tác giả: @renkingeth
Tóm tắt
Chứng minh kiến thức không (ZKP) trong lĩnh vực blockchain được coi rộng rãi là một trong những đột phá công nghệ quan trọng nhất kể từ công nghệ sổ cái phân tán, đồng thời cũng là lĩnh vực thu hút nhiều đầu tư mạo hiểm. Bài viết này tổng hợp hệ thống các tài liệu nghiên cứu về chứng minh kiến thức không trong gần bốn thập kỷ qua và những nghiên cứu mới nhất.
Trước hết, bài viết giới thiệu khái niệm cơ bản và bối cảnh lịch sử của ZKP. Sau đó, tập trung phân tích các kỹ thuật chứng minh kiến thức không dựa trên mạch điện, bao gồm các mô hình như zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs và Ligero, cùng với thiết kế, ứng dụng và phương pháp tối ưu hóa. Trong lĩnh vực môi trường tính toán, bài viết trình bày về ZKVM và ZKEVM, thảo luận cách chúng nâng cao khả năng xử lý giao dịch, bảo vệ quyền riêng tư và cải thiện hiệu quả xác minh. Bài viết cũng giới thiệu về Zero-Knowledge Rollup (ZK Rollup) – giải pháp mở rộng lớp 2 – cùng cơ chế hoạt động và các phương pháp tối ưu hóa, cũng như những tiến triển mới nhất về tăng tốc phần cứng, các giải pháp hỗn hợp và ZK EVM chuyên dụng.
Cuối cùng, bài viết nhìn về tương lai với các khái niệm mới nổi như ZKCoprocessor, ZKML, ZKThreads, ZK Sharding và ZK StateChannels, đồng thời thảo luận tiềm năng của chúng trong việc mở rộng quy mô, tương tác liên chuỗi và bảo mật riêng tư của blockchain.
Thông qua việc phân tích những công nghệ và xu hướng phát triển mới nhất này, bài viết cung cấp một góc nhìn toàn diện để hiểu và ứng dụng công nghệ chứng minh kiến thức không, thể hiện rõ tiềm năng to lớn của nó trong việc nâng cao hiệu quả và độ an toàn của hệ thống blockchain, đồng thời đưa ra cơ sở tham khảo quan trọng cho các quyết định đầu tư trong tương lai.
Mở đầu
Ngày nay, khi Internet đang chuyển mình sang thời kỳ Web3, các ứng dụng blockchain (DApps) phát triển nhanh chóng, với hàng loạt ứng dụng mới xuất hiện mỗi ngày. Trong vài năm gần đây, các nền tảng blockchain đã xử lý hàng triệu hoạt động người dùng và hàng tỷ giao dịch mỗi ngày. Dữ liệu khổng lồ sinh ra từ những giao dịch này thường bao gồm thông tin cá nhân nhạy cảm như danh tính người dùng, số tiền giao dịch, địa chỉ ví và số dư tài khoản. Do đặc điểm minh bạch và công khai của blockchain, dữ liệu này có thể truy cập bởi bất kỳ ai, do đó đặt ra nhiều vấn đề về an toàn và quyền riêng tư.
Hiện tại, có một số kỹ thuật mã hóa có thể giải quyết những thách thức này, bao gồm mã hóa đồng dạng, chữ ký vòng, tính toán đa bên an toàn và chứng minh kiến thức không (ZKP). Mã hóa đồng dạng cho phép thực hiện phép toán mà không cần giải mã dữ liệu, giúp bảo vệ an toàn số dư tài khoản và số tiền giao dịch, nhưng không thể bảo vệ địa chỉ ví. Chữ ký vòng cung cấp một dạng chữ ký số đặc biệt, có thể ẩn danh người ký, từ đó bảo vệ địa chỉ ví, nhưng lại vô hiệu trong việc bảo vệ số dư và số tiền giao dịch. Tính toán đa bên an toàn cho phép phân chia nhiệm vụ tính toán giữa nhiều bên tham gia mà không bên nào biết dữ liệu của bên khác, hiệu quả bảo vệ số dư và số tiền giao dịch, tuy nhiên cũng không thể bảo vệ địa chỉ ví. Ngoài ra, cả mã hóa đồng dạng, chữ ký vòng và tính toán đa bên an toàn đều không thể dùng để xác minh rằng bên chứng minh có đủ số tiền giao dịch mà không tiết lộ số tiền, địa chỉ ví hay số dư trong môi trường blockchain (Sun et al., 2021).
Chứng minh kiến thức không là một giải pháp toàn diện hơn, một giao thức xác minh cho phép kiểm tra tính đúng đắn của một mệnh đề mà không tiết lộ bất kỳ dữ liệu trung gian nào (Goldwasser, Micali & Rackoff, 1985). Giao thức này không yêu cầu cơ sở hạ tầng khóa công phức tạp, và việc lặp lại thực thi cũng sẽ không tạo cơ hội cho người dùng độc hại thu thập thêm thông tin hữu ích (Goldreich, 2004). Nhờ ZKP, bên xác minh có thể kiểm tra xem bên chứng minh có đủ số tiền giao dịch hay không mà không cần tiết lộ bất kỳ dữ liệu giao dịch riêng tư nào. Quá trình xác minh bao gồm việc tạo ra một "bằng chứng" chứa số tiền giao dịch mà bên chứng minh tuyên bố, sau đó gửi bằng chứng này đến bên xác minh. Bên xác minh thực hiện các phép toán được định nghĩa trước trên bằng chứng và đưa ra kết quả cuối cùng để kết luận có chấp nhận tuyên bố của bên chứng minh hay không. Nếu tuyên bố được chấp nhận, có nghĩa là bên chứng minh thực sự có đủ số tiền giao dịch. Toàn bộ quá trình xác minh này có thể được ghi lại trên blockchain mà không thể bị làm giả (Feige, Fiat & Shamir, 1986).
Đặc tính này khiến ZKP đóng vai trò trung tâm trong các giao dịch blockchain và ứng dụng tiền mã hóa, đặc biệt trong lĩnh vực bảo mật riêng tư và mở rộng mạng lưới, khiến nó không chỉ trở thành trọng tâm nghiên cứu học thuật, mà còn được coi là một trong những đột phá công nghệ quan trọng nhất kể từ khi công nghệ sổ cái phân tán – đặc biệt là Bitcoin – được triển khai thành công. Đồng thời, đây cũng là lĩnh vực trọng điểm trong ứng dụng công nghiệp và đầu tư mạo hiểm (Konstantopoulos, 2022).
Do đó, hàng loạt dự án dựa trên ZKP lần lượt xuất hiện, chẳng hạn như ZkSync, StarkNet, Mina, Filecoin và Aleo. Cùng với sự phát triển của các dự án này, các sáng tạo về thuật toán ZKP không ngừng xuất hiện, theo báo cáo, gần như mỗi tuần đều có thuật toán mới ra đời (Lavery, 2024; AdaPulse, 2024). Hơn nữa, việc phát triển phần cứng liên quan đến công nghệ ZKP cũng đang tiến triển nhanh chóng, bao gồm các chip được tối ưu hóa riêng cho ZKP. Ví dụ, các dự án như Ingonyama, Irreducible và Cysic đã huy động được lượng vốn lớn, những phát triển này không chỉ thể hiện bước tiến nhanh chóng của công nghệ ZKP mà còn phản ánh xu hướng chuyển đổi từ phần cứng phổ thông sang phần cứng chuyên dụng như GPU, FPGA và ASIC (Ingonyama, 2023; Burger, 2022).
Những tiến triển này cho thấy công nghệ chứng minh kiến thức không không chỉ là một bước đột phá quan trọng trong lĩnh vực mật mã, mà còn là động lực then chốt thúc đẩy ứng dụng rộng rãi hơn của công nghệ blockchain – đặc biệt là trong việc nâng cao bảo mật riêng tư và khả năng xử lý (Zhou et al, 2022).
Vì vậy, chúng tôi quyết định tổ chức hệ thống tri thức liên quan đến chứng minh kiến thức không (ZKP) nhằm hỗ trợ tốt hơn cho các quyết định đầu tư trong tương lai. Vì mục đích này, chúng tôi đã tổng hợp và xem xét các bài báo khoa học cốt lõi về ZKP (sắp xếp theo mức độ liên quan và số lần trích dẫn); đồng thời, chúng tôi cũng phân tích chi tiết tài liệu và whitepaper của các dự án hàng đầu trong lĩnh vực này (sắp xếp theo quy mô gọi vốn). Việc thu thập và phân tích dữ liệu tổng hợp này đã tạo nên nền tảng vững chắc cho việc soạn thảo bài viết này.
I. Kiến thức cơ bản về Chứng minh kiến thức không
1. Tổng quan
Năm 1985, các học giả Goldwasser, Micali và Rackoff lần đầu tiên đề xuất khái niệm Chứng minh kiến thức không (Zero-Knowledge Proof, ZKP) và Chứng minh kiến thức tương tác (Interactive Zero-Knowledge, IZK) trong bài báo "The Knowledge Complexity of Interactive Proof-Systems". Bài báo này là nền tảng cho ZKP, định nghĩa nhiều khái niệm ảnh hưởng sâu sắc đến nghiên cứu học thuật sau này. Ví dụ, khái niệm "kiến thức" được định nghĩa là "đầu ra của một phép tính không khả thi (unfeasible computation)", tức là kiến thức phải là một đầu ra, và là kết quả của một phép tính không khả thi, có nghĩa nó không thể là hàm đơn giản mà phải là hàm phức tạp. Phép tính không khả thi thường được hiểu là một bài toán NP, tức là một bài toán mà có thể kiểm tra tính đúng đắn của lời giải trong thời gian đa thức, thời gian đa thức ở đây có nghĩa là thời gian chạy của thuật toán có thể biểu diễn bằng một hàm đa thức của kích thước đầu vào. Đây là tiêu chuẩn quan trọng trong khoa học máy tính để đo lường hiệu quả và khả thi của thuật toán. Do quá trình giải bài toán NP rất phức tạp, nên được coi là không khả thi; tuy nhiên, quá trình kiểm tra lại tương đối đơn giản, do đó rất phù hợp để dùng cho việc xác minh trong chứng minh kiến thức không (Goldwasser, Micali & Rackoff, 1985).
Một ví dụ kinh điển về bài toán NP là bài toán người bán hàng du lịch, trong đó cần tìm đường đi ngắn nhất để thăm một loạt thành phố và quay về điểm xuất phát. Mặc dù việc tìm đường đi ngắn nhất có thể rất khó khăn, nhưng việc xác minh một đường đi cụ thể có phải là ngắn nhất hay không thì lại dễ dàng hơn nhiều. Bởi vì việc xác minh tổng khoảng cách của một đường đi cụ thể có thể hoàn thành trong thời gian đa thức.
Trong bài báo của mình, Goldwasser và cộng sự đã giới thiệu khái niệm "độ phức tạp kiến thức" (knowledge complexity), dùng để định lượng lượng kiến thức mà bên chứng minh tiết lộ cho bên xác minh trong hệ thống chứng minh tương tác. Họ cũng đề xuất Hệ thống chứng minh tương tác (Interactive Proof Systems, IPS), trong đó bên chứng minh (Prover) và bên xác minh (Verifier) thông qua nhiều vòng tương tác để chứng minh tính chân thực của một mệnh đề (Goldwasser, Micali & Rackoff, 1985).
Tóm lại, định nghĩa về chứng minh kiến thức không do Goldwasser và cộng sự đưa ra là một dạng đặc biệt của hệ thống chứng minh tương tác, trong đó bên xác minh trong suốt quá trình xác minh sẽ không thu được bất kỳ thông tin bổ sung nào ngoài giá trị chân lý của mệnh đề; đồng thời họ đề xuất ba đặc tính cơ bản:
-
Tính đầy đủ (completeness): Nếu lập luận là thật, một bên chứng minh trung thực có thể thuyết phục được một bên xác minh trung thực;
-
Tính đáng tin cậy (soundness): Nếu bên chứng minh không biết nội dung tuyên bố, anh ta chỉ có thể đánh lừa bên xác minh với xác suất cực nhỏ;
-
Tính kiến thức không (zero-knowledge): Sau khi quá trình chứng minh hoàn tất, bên xác minh chỉ biết được thông tin "bên chứng minh sở hữu kiến thức này", mà không thể biết thêm bất kỳ nội dung nào khác (Goldwasser, Micali & Rackoff, 1985).
2. Ví dụ về Chứng minh kiến thức không
Để hiểu rõ hơn về chứng minh kiến thức không và các thuộc tính của nó, dưới đây là một ví dụ về việc xác minh xem bên chứng minh có sở hữu một thông tin bí mật nào đó hay không, ví dụ này được chia thành ba giai đoạn: thiết lập, thách thức và phản hồi.
Bước thứ nhất: Thiết lập (Setup)
Ở bước này, mục tiêu của bên chứng minh là tạo ra một bằng chứng, chứng tỏ anh ta biết một con số bí mật s, nhưng lại không hiển thị trực tiếp s. Đặt con số bí mật;
Chọn hai số nguyên tố lớn p và q, tính tích của chúng. Đặt các số nguyên tố và , tính được;
Tính , ở đây v được gửi đến bên xác minh như một phần của bằng chứng, nhưng không đủ để bên xác minh hoặc bất kỳ người quan sát nào suy ra được s;
Chọn ngẫu nhiên một số nguyên r, tính và gửi đến bên xác minh. Giá trị x này dùng cho quá trình xác minh sau này, nhưng cũng không tiết lộ s. Đặt số nguyên ngẫu nhiên, tính được .
Bước thứ hai: Thách thức (Challenge)
Bên xác minh chọn ngẫu nhiên một bit a (có thể là 0 hoặc 1), sau đó gửi đến bên chứng minh. "Thử thách" này quyết định bước tiếp theo mà bên chứng minh cần thực hiện.
Bước thứ ba: Phản hồi (Response)
Tùy theo giá trị a mà bên xác minh gửi tới, bên chứng minh sẽ phản hồi:
Nếu , bên chứng minh gửi (ở đây r là số mà anh ta chọn ngẫu nhiên trước đó).
Nếu , bên chứng minh tính và gửi. Giả sử bên xác minh gửi bit ngẫu nhiên, tùy theo giá trị của a, bên chứng minh tính ;
Cuối cùng, bên xác minh dựa vào g nhận được để kiểm tra xem có bằng hay không. Nếu đẳng thức đúng, bên xác minh chấp nhận bằng chứng này. Khi , bên xác minh tính , kiểm tra vế phải; khi , bên xác minh tính , kiểm tra vế phải.
Ở đây, ta thấy bên xác minh tính được cho thấy bên chứng minh đã vượt qua quá trình xác minh thành công, đồng thời không tiết lộ con số bí mật s của mình. Trong trường hợp này, do a chỉ có thể lấy giá trị 0 hoặc 1, chỉ có hai khả năng, xác suất bên chứng minh vượt qua xác minh nhờ may mắn (khi a=0) là . Nhưng nếu bên xác minh tiếp tục thử thách bên chứng minh nhiều lần, bên chứng minh liên tục thay đổi các số liên quan, nộp cho bên xác minh, và luôn vượt qua xác minh thành công, thì xác suất bên chứng minh vượt qua nhờ may mắn sẽ là (tiệm cận 0), từ đó khẳng định chắc chắn rằng bên chứng minh thực sự biết một con số bí mật s. Ví dụ này minh họa tính đầy đủ, đáng tin cậy và kiến thức không của hệ thống chứng minh kiến thức không (Fiat & Shamir, 1986).
II. Chứng minh kiến thức không phi tương tác
1. Bối cảnh
Chứng minh kiến thức không (ZKP) theo khái niệm truyền thống thường là giao thức tương tác và trực tuyến; ví dụ, giao thức Sigma thường cần từ ba đến năm vòng tương tác để hoàn thành xác thực (Fiat & Shamir, 1986). Tuy nhiên, trong các tình huống như giao dịch tức thời hoặc bỏ phiếu, thường không có cơ hội để thực hiện nhiều vòng tương tác, đặc biệt trong ứng dụng công nghệ blockchain, chức năng xác minh ngoại tuyến trở nên cực kỳ quan trọng (Sun et al., 2021).
2. Đề xuất NIZK
Năm 1988, Blum, Feldman và Micali lần đầu tiên đề xuất khái niệm Chứng minh kiến thức không phi tương tác (NIZK), chứng minh rằng khả năng hoàn thành quá trình xác thực giữa bên chứng minh (Prover) và bên xác minh (Verifier) vẫn tồn tại mà không cần nhiều vòng tương tác. Đột phá này khiến việc thực hiện giao dịch tức thời, bỏ phiếu và các ứng dụng blockchain trở nên khả thi (Blum, Feldman & Micali, 1988).
Họ đề xuất NIZK có thể được chia thành ba giai đoạn:
-
Thiết lập
-
Tính toán
-
Xác minh
Giai đoạn thiết lập sử dụng hàm tính toán để chuyển đổi tham số bảo mật thành kiến thức công cộng (bên chứng minh và bên xác minh đều có thể truy cập), thường được mã hóa trong một chuỗi tham chiếu chung (CRS). Đây là cách để tạo bằng chứng và sử dụng các tham số và thuật toán chính xác để xác minh.
Giai đoạn tính toán sử dụng hàm tính toán, đầu vào và khóa chứng minh để xuất ra kết quả tính toán và bằng chứng.
Trong giai đoạn xác minh, tính hợp lệ của bằng chứng được kiểm tra thông qua khóa xác minh.
Mô hình Chuỗi tham chiếu chung (CRS) mà họ đề xuất, tức là dựa trên việc tất cả các bên tham gia chia sẻ một chuỗi để thực hiện chứng minh kiến thức không phi tương tác cho bài toán NP. Hoạt động của mô hình này phụ thuộc vào việc CRS được tạo một cách đáng tin cậy, tất cả các bên tham gia phải có thể truy cập cùng một chuỗi. Chỉ khi CRS được tạo một cách chính xác và an toàn, các giải pháp được triển khai theo mô hình này mới đảm bảo được tính an toàn. Đối với một lượng lớn người tham gia, quá trình tạo CRS có thể vừa phức tạp vừa tốn thời gian, do đó mặc dù các giải pháp loại này thường dễ vận hành và kích thước bằng chứng nhỏ, nhưng quá trình thiết lập lại khá thách thức (Blum, Feldman & Micali, 1988).
Sau đó, công nghệ NIZK đã phát triển mạnh mẽ, xuất hiện nhiều phương pháp chuyển đổi chứng minh kiến thức không tương tác thành phi tương tác. Những phương pháp này khác nhau về giả định xây dựng hệ thống hoặc mô hình mật mã cơ bản.
3. Biến đổi Fiat-Shamir
Biến đổi Fiat-Shamir, còn gọi là Heuristic Fiat-Shamir (phương pháp ước lượng), hoặc Paradigm Fiat-Shamir (mô hình); được đề xuất bởi Fiat và Shamir vào năm 1986, là một phương pháp có thể chuyển đổi chứng minh kiến thức không tương tác thành phi tương tác. Phương pháp này giảm số lần tương tác bằng cách đưa vào hàm băm, đồng thời dựa vào các giả định an toàn để đảm bảo tính chân thực của bằng chứng và đặc tính khó làm giả. Biến đổi Fiat-Shamir sử dụng hàm băm mật mã công cộng để thay thế một phần tính ngẫu nhiên và tương tác, đầu ra của nó có thể coi là một dạng CRS. Mặc dù giao thức này được coi là an toàn trong mô hình oracle ngẫu nhiên, nhưng nó dựa trên giả định rằng đầu ra của hàm băm có tính ngẫu nhiên đều đặn và độc lập với các đầu vào khác (Fiat & Shamir, 1986). Nghiên cứu của Canetti, Goldreich và Halevi năm 2003 cho thấy, mặc dù giả định này đúng trong mô hình lý thuyết, nhưng trong ứng dụng thực tế có thể gặp thách thức, do đó khi sử dụng có nguy cơ thất bại (Canetti, Goldreich & Halevi, 2003). Sau này, Micali cải tiến phương pháp này, nén nhiều vòng tương tác thành một vòng duy nhất, từ đó đơn giản hóa hơn nữa quy trình tương tác (Micali, 1994).
4. Jens Groth và các nghiên cứu của ông
Các nghiên cứu sau này của Jens Groth đã thúc đẩy mạnh mẽ ứng dụng của chứng minh kiến thức không trong mật mã học và công nghệ blockchain. Năm 2005, ông cùng Ostrovsky và Sahai đã đề xuất hệ thống chứng minh kiến thức không phi tương tác hoàn hảo đầu tiên áp dụng cho mọi ngôn ngữ NP, đảm bảo an toàn tổ hợp phổ quát (UC) ngay cả trước các đối thủ động / thích nghi. Ngoài ra, họ đã sử dụng các giả định phức tạp về lý thuyết số để thiết kế một hệ thống chứng minh kiến thức không phi tương tác ngắn gọn và hiệu quả, giảm đáng kể kích thước CRS và bằng chứng (Groth & Sahai, 2005).
Năm 2007, Groth, Cramer và Damgård bắt đầu thương mại hóa các công nghệ này, thông qua kiểm nghiệm thực nghiệm, các sơ đồ mã hóa khóa công khai và chữ ký của họ đều đạt được sự cải thiện đáng kể về hiệu quả và an toàn, mặc dù các sơ đồ này dựa trên giả định nhóm song tuyến (Groth & Sahai, 2007). Năm 2011, Groth tiếp tục khám phá cách kết hợp mã hóa toàn đồng dạng với chứng minh kiến thức không phi tương tác, đề xuất một giải pháp giảm chi phí truyền thông, khiến kích thước NIZK phù hợp với kích thước bằng chứng (Groth, 2011). Trong những năm tiếp theo, ông cùng các nhà nghiên cứu khác đã nghiên cứu sâu về các kỹ thuật dựa trên ghép nối, cung cấp các bằng chứng phi tương tác ngắn gọn và hiệu quả cho các tuyên bố quy mô lớn, mặc dù những bằng chứng này vẫn chưa thoát khỏi khuôn khổ nhóm song tuyến (Bayer & Groth, 2012; Groth, Kohlweiss & Pintore, 2016; Bootle, Cerulli, Chaidos, Groth & Petit, 2015; Groth, Ostrovsky & Sahai, 2012; Groth & Maller, 2017).
5. Các nghiên cứu khác
Trong các ứng dụng cụ thể, chứng minh kiến thức không phi tương tác dành cho bên xác minh cụ thể đã thể hiện giá trị thực tiễn độc đáo. Ví dụ, Cramer và Shoup đã phát triển một sơ đồ mã hóa khóa công khai dựa trên phương pháp hàm băm phổ quát, hiệu quả chống lại các cuộc tấn công lựa chọn mật mã vào năm 1998 và 2002. Ngoài ra, trong mô hình đăng ký khóa, một phương pháp chứng minh kiến thức không phi tương tác mới đã được phát triển thành công, có thể giải quyết mọi bài toán lớp NP, chìa khóa nằm ở chỗ người tham gia cần đăng ký khóa riêng của họ để thực hiện xác minh sau này (Cramer & Shoup, 1998, 2002).
Ngoài ra, Damgård, Fazio và Nicolosi năm 2006 đã đề xuất một phương pháp mới cải tiến biến đổi Fiat-Shamir hiện có, cho phép thực hiện chứng minh kiến thức không phi tương tác mà không cần tương tác trực tiếp. Trong phương pháp của họ, bên xác minh trước tiên cần đăng ký một khóa công khai, chuẩn bị cho các thao tác mã hóa sau này. Bên chứng minh sử dụng kỹ thuật mã hóa cộng đồng để thực hiện phép toán trên dữ liệu mà không cần biết trước, tạo ra thông tin mã hóa chứa câu trả lời, như một phản hồi với thách thức. Độ an toàn của phương pháp này dựa trên "giả định đòn bẩy độ phức tạp", cho rằng đối với kẻ thù có nguồn lực tính toán siêu việt, một số bài toán được coi là khó giải có thể được giải quyết (Damgård, Fazio & Nicolosi, 2006).
Khái niệm "tính đáng tin cậy có thể truy trách nhiệm yếu" do Ventre và Visconti đề xuất năm 2009 là một sự thay thế cho giả định này, yêu cầu kẻ thù khi đưa ra bằng chứng giả, không chỉ phải nhận thức được sự giả dối mà còn phải rõ ràng về cách thức tạo ra bằng chứng giả đó. Yêu cầu này làm tăng đáng kể độ khó lừa dối, vì kẻ thù phải xác định rõ thủ đoạn lừa đảo của mình. Trong thực tế, kẻ thù sử dụng khái niệm này cần cung cấp bằng chứng cụ thể, chứa thông tin mã hóa dành riêng cho bên xác minh nhất định, không có khóa riêng của bên xác minh thì khó hoàn thành bằng chứng, do đó khi cố gắng làm giả bằng chứng, hành vi của chúng có thể bị phát hiện thông qua kiểm tra (Ventre and Visconti, 2009).
Biến đổi Unruh là một phương án thay thế cho biến đổi Fiat-Shamir được đề xuất năm 2015. Phương pháp Fiat-Shamir thường không an toàn trước máy tính lượng tử, và có thể tạo ra các giải pháp không an toàn đối với một số giao thức nhất định (Unruh, 2015). Ngược lại, biến đổi Unruh trong mô hình oracle ngẫu nhiên (ROM), cung cấp chứng minh kiến thức không phi tương tác (NIZK) có thể chứng minh an toàn trước kẻ thù lượng tử cho mọi giao thức tương tác. Tương tự như phương pháp Fiat-Shamir, biến đổi Unruh không cần thêm bước thiết lập nào (Ambainis, Rosmanis & Unruh, 2014).
Ngoài ra, Kalai và cộng sự đề xuất một hệ thống lập luận cho các bài toán quyết định tùy ý dựa trên kỹ thuật truy vấn thông tin riêng tư. Phương pháp này sử dụng mô hình hệ thống chứng minh đa bên (MIP), và thông qua phương pháp của Aiello, chuyển đổi MIP thành một hệ thống lập luận. Cấu trúc này hoạt động trong mô hình chuẩn, không cần dựa vào giả định oracle ngẫu nhiên. Phương pháp này được áp dụng trong một số lập luận kiến thức không dựa trên "Proofs-for-Muggles" (Kalai, Raz & Rothblum, 2014).
Trên cơ sở các công nghệ này, chứng minh kiến thức không phi tương tác (NIZK) đã được ứng dụng rộng rãi trong nhiều lĩnh vực đòi hỏi độ an toàn và bảo mật riêng tư cao, như giao dịch tài chính, bỏ phiếu điện tử và công nghệ blockchain. Bằng cách giảm số lần tương tác và tối ưu hóa quá trình tạo và xác minh bằng chứng, NIZK không chỉ nâng cao hiệu quả hệ thống mà còn tăng cường khả năng an toàn và bảo mật. Trong tương lai, cùng với sự phát triển và hoàn thiện hơn nữa các công nghệ này, chúng ta có thể kỳ vọng NIZK sẽ đóng vai trò quan trọng trong nhiều lĩnh vực khác, cung cấp nền tảng kỹ thuật vững chắc để thực hiện xử lý và truyền tải thông tin an toàn và hiệu quả hơn (Partala, Nguyen & Pirttikangas, 2020).
III. Chứng minh kiến thức không dựa trên mạch điện
1. Bối cảnh
Trong lĩnh vực mật mã học, đặc biệt khi xử lý các tác vụ tính toán cần độ song song hóa cao và loại hình tính toán cụ thể (như phép toán ma trận quy mô lớn), mô hình máy Turing truyền thống bộc lộ một số hạn chế nhất định. Mô hình máy Turing cần cơ chế quản lý bộ nhớ phức tạp để mô phỏng băng vô hạn, và không phù hợp để biểu diễn trực tiếp các tính toán song song và xử lý dây chuyền. Ngược lại, mô hình mạch điện với cấu trúc tính toán độc đáo của nó, phù hợp hơn với một số nhiệm vụ xử lý mật mã cụ thể (Chaidos, 2017). Bài viết này sẽ thảo luận chi tiết về các hệ thống chứng minh kiến thức không dựa trên mô hình mạch điện (Zero-Knowledge Proof Systems Based on Circuit Models), những hệ thống này đặc biệt nhấn mạnh việc sử dụng mạch điện (thường là mạch số học hoặc mạch logic) để biểu diễn và xác minh quá trình tính toán.
2. Khái niệm và đặc điểm cơ bản của mô hình mạch điện
Trong mô hình tính toán dựa trên mạch điện, mạch điện được định nghĩa là một mô hình tính toán đặc biệt, có thể chuyển đổi mọi quá trình tính toán thành một chuỗi các cổng và dây nối, các cổng này thực hiện các thao tác logic hoặc số học cụ thể. Cụ thể, mô hình mạch điện chủ yếu được chia thành hai loại lớn:
-
Mạch số học: Chủ yếu bao gồm các cổng cộng và nhân, dùng để xử lý các phần tử trên trường hữu hạn. Mạch số học phù hợp để thực hiện các phép toán số học phức tạp, được ứng dụng rộng rãi trong các thuật toán mã hóa và phân tích số học.
-
Mạch logic: Được cấu thành từ các cổng cơ bản như AND, OR, NOT, dùng để xử lý các phép toán Boole. Mạch logic phù hợp để thực hiện các logic phán đoán đơn giản và tính toán nhị phân, thường được dùng để hiện thực các hệ thống điều khiển và các nhiệm vụ xử lý dữ liệu đơn giản (Chaidos, 2017).
3. Thiết kế và ứng dụng mạch điện trong chứng minh kiến thức không
Trong hệ thống chứng minh kiến thức không, quá trình thiết kế mạch điện liên quan đến việc biểu diễn vấn đề cần chứng minh dưới dạng một mạch điện, quá trình này đòi hỏi việc thiết kế mạch zk cần rất nhiều "tư duy ngược": "Nếu đầu ra được tuyên bố của một phép tính là thật, thì đầu ra đó phải thỏa mãn một số yêu cầu nhất định. Nếu những yêu cầu này khó mô hình hóa chỉ bằng phép cộng hoặc nhân, chúng ta yêu cầu bên chứng minh thực hiện thêm công việc, để chúng ta có thể dễ dàng mô hình hóa những yêu cầu đó." Quá trình thiết kế thường tuân theo các bước sau (Chaidos, 2017):
-
Biểu diễn vấn đề: Trước tiên chuyển đổi vấn đề cần chứng minh, ví dụ như quá trình tính toán hàm băm mật mã, thành dạng mạch điện. Điều này bao gồm việc phân tách các bước tính toán thành các đơn vị cơ bản trong mạch điện, như cổng và dây nối.
-
Tối ưu hóa mạch: Thông qua các kỹ thuật như gộp cổng và rút gọn hằng số, tối ưu hóa thiết kế mạch, giảm số lượng cổng và bước tính toán cần thiết, từ đó nâng cao hiệu quả vận hành và tốc độ phản hồi của hệ thống.
-
Chuyển đổi sang biểu diễn đa thức: Để phù hợp với công nghệ chứng minh kiến thức không, chuyển đổi mạch điện đã được tối ưu hóa sang dạng đa thức. Mỗi thành phần mạch và kết nối đều tương ứng với một ràng buộc đa thức cụ thể.
-
Tạo Chuỗi tham chiếu chung (CRS): Trong giai đoạn khởi tạo hệ thống, tạo CRS bao gồm khóa chứng minh và khóa xác minh, để phục vụ cho quá trình tạo và xác minh bằng chứng sau này.
-
Tạo bằng chứng và xác minh: Bên chứng minh dựa trên đầu vào riêng tư và CRS, thực hiện tính toán trên mạch điện, tạo ra bằng chứng kiến thức không. Bên xác minh có thể dựa trên mô tả mạch công khai và CRS để xác minh tính đúng đắn của bằng chứng, mà không cần biết thông tin riêng tư của bên chứng minh (Chaidos, 2017).
Thiết kế mạch điện trong chứng minh kiến thức không liên quan đến việc chuyển đổi quá trình tính toán cụ thể thành biểu diễn mạch điện, và thông qua việc xây dựng các ràng buộc đa thức để đảm bảo tính chính xác của kết quả tính toán, đồng thời tránh tiết lộ bất kỳ thông tin cá nhân nào thêm. Trong thiết kế mạch điện, nhiệm vụ then chốt là tối ưu hóa cấu trúc mạch và tạo ra biểu diễn đa thức hiệu quả, nhằm nâng cao hiệu quả tạo và xác minh bằng chứng. Thông qua các bước này, công nghệ chứng minh kiến thức không có thể xác minh tính đúng đắn của phép tính mà không tiết lộ thông tin bổ sung, đáp ứng đồng thời nhu cầu bảo mật riêng tư và an toàn dữ liệu (Chaidos, 2017).
4. Các nhược điểm và thách thức tiềm tàng
Các nhược điểm bao gồm:
-
Độ phức tạp và quy mô mạch điện: Các phép tính phức tạp cần mạch điện lớn, dẫn đến chi phí tính toán để tạo và xác minh bằng chứng tăng đáng kể, đặc biệt khi xử lý dữ liệu quy mô lớn;
-
Khó khăn trong tối ưu hóa: Mặc dù các kỹ thuật (như gộp cổng, rút gọn hằng số, v.v.) có thể tối ưu hóa mạch điện, nhưng việc thiết kế và tối ưu hóa mạch điện hiệu quả vẫn đòi hỏi kiến thức chuyên môn sâu sắc;
-
Tính thích nghi với các nhiệm vụ tính toán cụ thể: Các nhiệm vụ tính toán khác nhau cần thiết kế mạch điện khác nhau, việc thiết kế mạch điện hiệu quả cho từng nhiệm vụ cụ thể có thể tốn thời gian và khó mở rộng;
-
Khó khăn trong triển khai thuật toán mã hóa: Triển khai các thuật toán mật mã phức tạp (như hàm băm hoặc mã hóa khóa công khai) có thể cần rất nhiều cổng logic, khiến việc thiết kế và thực hiện mạch điện trở nên khó khăn;
-
Tiêu thụ tài nguyên: Mạch điện quy mô lớn cần nhiều tài nguyên phần cứng, có thể gặp giới hạn thực tế trong việc triển khai phần cứng về mặt tiêu thụ điện năng, nhiệt lượng và không gian vật lý (Goldreich, 2004; Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
Các giải pháp và hướng cải tiến:
-
Công nghệ nén mạch: Thông qua nghiên cứu và áp dụng các công nghệ nén mạch điện hiệu quả, giảm số lượng cổng logic và tài nguyên tính toán cần thiết;
-
Thiết kế mô-đun: Thông qua thiết kế mô-đun mạch điện, nâng cao khả năng tái sử dụng và mở rộng, giảm khối lượng công việc thiết kế lại mạch cho các nhiệm vụ khác nhau;
-
Tăng tốc phần cứng: Sử dụng phần cứng chuyên dụng (như FPGA hoặc ASIC) để tăng tốc tính toán mạch điện, nâng cao hiệu suất tổng thể của chứng minh kiến thức không (Goldreich, 2004; Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
IV. Các mô hình chứng minh kiến thức không
1. Bối cảnh
Tính phổ quát kém của chứng minh kiến thức không dựa trên mạch điện, cần phát triển các mô hình và thuật toán mới cho từng vấn đề cụ thể, hiện có nhiều trình biên dịch ngôn ngữ cấp cao và công cụ kết hợp mạch điện cấp thấp để tạo và thiết kế thuật toán mạch điện, việc chuyển đổi các phép tính liên quan có thể được thực hiện bằng công cụ xây dựng mạch thủ công hoặc trình biên dịch tự động. Chuyển đổi thủ công thường tạo ra mạch điện tối ưu hơn, trong khi chuyển đổi tự động thuận tiện hơn cho nhà phát triển. Các ứng dụng then chốt về hiệu suất thường cần công cụ chuyển đổi thủ công (Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun et al., 2021).
Bài viết này sẽ thảo luận về một số mô hình nổi tiếng nhất. Nhìn chung, các mô hình này đều là mở rộng hoặc biến thể của công nghệ zkSNARKs, mỗi mô hình đều cố gắng tối ưu hóa cho các nhu cầu ứng dụng cụ thể (như kích thước bằng chứng, độ phức tạp tính toán, yêu cầu thiết lập, v.v.).
Mỗi giao thức đều có các ứng dụng, lợi thế và hạn chế cụ thể, đặc biệt về yêu cầu thiết lập, kích thước bằng chứng, tốc độ xác minh và chi phí tính toán. Chúng được ứng dụng trong nhiều lĩnh vực, từ quyền riêng tư tiền mã hóa và hệ thống bỏ phiếu an toàn đến việc xác minh tính toán tổng quát theo cách kiến thức không (Čapko, Vukmirović & Nedić, 2019).
2. Các mô hình thuật toán phổ biến
1. Mô hình zkSNARK: Năm 2011, được đề xuất bởi các học giả mật mã Bitansky và cộng sự, là viết tắt của "Zero-Knowledge Succinct Non-Interactive Argument of Knowledge" (Lập luận kiến thức không ngắn gọn phi tương tác), là một cơ chế chứng minh kiến thức không được cải tiến. Nếu tồn tại hàm băm kháng va chạm có thể trích xuất (ECRH), thì việc thực hiện SNARK cho bài toán NP là khả thi, và cho thấy tính ứng dụng của SNARK trong ủy thác tính toán, chứng minh kiến thức không ngắn gọn phi tương tác và tính toán an toàn hai bên ngắn gọn trong nhiều tình huống. Nghiên cứu này cũng chỉ ra rằng sự tồn tại của SNARK ngụ ý sự cần thiết của ECRH, thiết lập mối liên hệ nền tảng giữa các nguyên thủy mật mã này (Bitansky et al., 2011).
Hệ thống zkSNARK bao gồm ba phần: thiết lập, bên chứng minh và bên xác minh. Quá trình thiết lập tạo ra khóa chứng minh (PK) và khóa xác minh (VK), sử dụng tham số bảo mật đã định trước l và mạch số học F- C. Tất cả đầu vào và đầu ra của mạch này đều là các phần tử trong miền F. PK được dùng để tạo bằng chứng có thể xác minh, trong khi VK dùng để xác minh bằng chứng đã tạo. Dựa trên PK đã tạo, bên chứng minh sử dụng đầu vào x ∈ Fn và bằng chứng W ∈ Fh để tạo bằng chứng p, trong đó C(x, W) = 0l. Ở đây, C(x, W) = 0l biểu thị đầu ra của mạch C là 0l, x và W là các tham số đầu vào của mạch C. n, h và l lần lượt biểu thị chiều kích của x, W và đầu ra của C. Cuối cùng, bên xác minh sử dụng VK, x và p để xác minh p, và quyết định chấp nhận hoặc từ chối bằng chứng dựa trên kết quả xác minh (Bitansky et al., 2011).
Ngoài ra, zkSNARK còn có một số đặc tính bổ sung. Thứ nhất, quá trình xác minh có thể hoàn thành trong thời gian ngắn, và kích thước bằng chứng thường chỉ vài byte. Thứ hai, không cần giao tiếp đồng bộ giữa bên chứng minh và bên xác minh, bất kỳ bên xác minh nào cũng có thể xác minh bằng chứng ngoại tuyến. Cuối cùng, thuật toán bên chứng minh chỉ có thể thực hiện trong thời gian đa thức. Từ đó, đã xuất hiện nhiều mô hình zkSNARK được cải tiến, tiếp tục tối ưu hóa hiệu suất và phạm vi ứng dụng (Bitansky et al., 2011).
2. Mô hình Ben-Sasson: Ben-Sasson và cộng sự (2013, 2014) đề xuất một mô hình zkSNARK mới dành cho việc thực thi chương trình kiến trúc RISC von Neumann. Sau đó, dựa trên bộ tạo mạch điện tổng quát được đề xuất, Ben-Sasson và cộng sự xây dựng một hệ thống và thể hiện ứng dụng của nó trong việc xác minh thực thi chương trình. Hệ thống này bao gồm hai thành phần: hệ thống chứng minh mật mã dùng để xác minh tính khả thi của mạch số học, và bộ tạo mạch điện chuyển đổi việc thực thi chương trình thành mạch số học. Thiết kế này vượt trội hơn các công trình trước về cả chức năng và hiệu quả, đặc biệt là tính tổng quát của bộ tạo mạch và sự phụ thuộc cộng tính vào kích thước mạch đầu ra. Đánh giá thử nghiệm cho thấy hệ thống có thể xử lý chương trình lên đến 10.000 lệnh và tạo bằng chứng ngắn gọn ở cấp độ bảo mật cao, thời gian xác minh chỉ 5 miligiây. Giá trị của nó nằm ở việc cung cấp giải pháp zk-SNARKs hiệu quả, tổng quát và an toàn cho các ứng dụng thực tế như blockchain và hợp đồng thông minh bảo vệ quyền riêng tư (Ben-Sasson et al., 2013, 2014).
3. Mô hình Pinocchio: Parno và cộng sự (2013) đề xuất, là bộ công cụ tạo lập luận kiến thức không phi tương tác hoàn chỉnh (Parno et al., 2013). Nó bao gồm một trình biên dịch cấp cao, cung cấp cho nhà phát triển một phương pháp thuận tiện để chuyển đổi phép tính thành mạch điện. Các trình biên dịch này chấp nhận mã được viết bằng ngôn ngữ cấp cao, do đó cả thuật toán cũ và mới đều có thể dễ dàng chuyển đổi. Tuy nhiên, để tạo mạch điện kích thước phù hợp, cấu trúc mã có thể bị giới hạn một số điều kiện.
Một đặc điểm khác của Pinocchio là sử dụng một cấu trúc toán học gọi là Chương trình số học bậc hai (Quadratic Arithmetic Programs, QAPs), có thể chuyển đổi hiệu quả nhiệm vụ tính toán thành nhiệm vụ xác minh. QAPs có thể mã hóa bất kỳ mạch số học nào thành một tập hợp đa thức, và chỉ cần độ phức tạp thời gian và không gian tuyến tính để tạo các đa thức này. Bằng chứng do Pinocchio tạo ra
Chào mừng tham gia cộng đồng chính thức TechFlow
Nhóm Telegram:https://t.me/TechFlowDaily
Tài khoản Twitter chính thức:https://x.com/TechFlowPost
Tài khoản Twitter tiếng Anh:https://x.com/BlockFlow_News
Arkstream Capital
