Cảnh báo rủi ro: Đề phòng huy động vốn bất hợp pháp dưới danh nghĩa 'tiền điện tử' và 'blockchain'. — Năm cơ quan bao gồm Ủy ban Giám sát Ngân hàng và Bảo hiểm
Tìm kiếm
Đăng nhập
简中
繁中
English
日本語
한국어
ภาษาไทย
Tiếng Việt
BTC
ETH
HTX
SOL
BNB
Xem thị trường
Hiểu biết đầu tiên về "không kiến ​​thức" và "bằng chứng"
安比(SECBIT)实验室
特邀专栏作者
2019-09-04 03:42
Bài viết này có khoảng 10223 từ, đọc toàn bộ bài viết mất khoảng 15 phút
Khám phá chuỗi bằng chứng không có kiến ​​thức (1)

Tác giả: Quách Vũ

Bài viết này đã được cập nhật lên Github:https://github.com/

giới thiệu:

Tôi nghĩ blockchain hầu như không phải là một "công nghệ". Nó giống như một lĩnh vực, bao gồm tất cả. Hay nói một cách siêu hình, blockchain giống như một sinh vật hơn, tích hợp nhiều công nghệ lý thuyết khác nhau.

Bằng chứng không kiến ​​thức là một công nghệ quan trọng để xây dựng niềm tin và là một phần không thể thiếu của sinh vật chuỗi khối.

Bằng chứng không kiến ​​thức là một công nghệ quan trọng để kết nối dữ liệu trên chuỗi và điện toán ngoài chuỗi, đồng thời đây cũng là một cách quan trọng để thực hiện bảo vệ quyền riêng tư dữ liệu trên chuỗi

chứng minh

"chứng minh"quá khứ và hiện tại

Bằng chứng là gì? Nhiều người có thể giống tôi, khi nhìn thấy hai từ này, họ không thể không nghĩ đến các hình hình học khác nhau tương tự như hình tam giác trong đề thi cấp 2. Khi giáo viên vẽ một đường phụ một cách kỳ diệu, quá trình chứng minh đột nhiên rõ ràng , rồi hối hận sao không ngờ.

Tiếng Hy Lạp cổ đại: "bằng chứng" == "cái nhìn sâu sắc"

Chứng minh toán học bắt nguồn từ Hy Lạp cổ đại. Họ đã phát minh ra (khám phá) các tiên đề và logic, và họ thuyết phục nhau bằng bằng chứng chứ không phải bằng uy quyền. Đây là "phân cấp" xuyên suốt. Kể từ thời Hy Lạp cổ đại, phương pháp luận này đã ảnh hưởng đến toàn bộ quá trình phát triển của nền văn minh nhân loại.

Hình trên là một bằng chứng thông minh của "Định lý Pitago". Đã có nhiều bằng chứng khéo léo, ý tưởng kỳ diệu và nguồn cảm hứng thiên tài trong lịch sử. Một khi mệnh đề đã được chứng minh, Đức Chúa Trời không thể làm gì được. Nhân tiện, cũng có bằng chứng "Chúa không toàn năng": Chúa không thể tạo ra một hòn đá mà anh ta không thể nâng được.

Một chứng minh toán học thường ẩn chứa những "cái nhìn sâu sắc" vô cùng sâu sắc. Tôi tin rằng nhiều người đã đọc câu chuyện về "Định lý cuối cùng của Fermat" [1]. Tôi không thể viết ra được", và phải mất nhiều thế hệ khéo léo để đưa Wiles đến đứng đầu. Gần đây, chẳng hạn như "Giả thuyết Poincaré", "Phỏng đoán của Goldbach" với một chút cảm giác về tuổi tác, và nhà khoa học Trung Quốc Zhang Yitang, người mà tôi rất ngưỡng mộ, đã làm việc chăm chỉ trong mười năm, sau khi nghiên cứu kỹ lưỡng "Goldston-Pintz -Yıldırım" và Sau chứng minh "sáng suốt" của "Bombieri-Friedlander-Iwaniec.", đã chứng minh được "khoảng có giới hạn giữa các số nguyên tố" [2].

Kể từ thời Leibniz vào thế kỷ 17, người ta đã mơ ước tìm ra một phương tiện máy móc có thể tự động hoàn thành các phép chứng minh mà không cần dựa vào một tia sáng của thiên tài.

Đầu thế kỷ 20: "Bằng chứng" == "Lý luận tượng trưng"

Vào cuối thế kỷ 19, Cantor, Boole, Frege, Hilbert, Russell, Browe, Gödel và những người khác đã định nghĩa hệ thống ký hiệu của logic hình thức. Còn “chứng minh” là quy trình lập luận được viết bằng ngôn ngữ ký hiệu của logic hình thức. Bản thân logic có hợp lý không? Bản thân logic có phải là "tự nhất quán" không? Bản thân suy luận logic có đúng không, có chứng minh được không? Điều này khiến các nhà toán học/nhà logic học/nhà khoa học máy tính phát minh ra (khám phá) các hệ thống ký hiệu, cú pháp so với ngữ nghĩa, đáng tin cậy so với hoàn chỉnh, đệ quy so với vô hạn. (Về phần câu chuyện kỳ ​​diệu này, xin tham khảo cuốn “Logic Engine” [3]).

Năm 1910, Russell xuất bản kiệt tác "Các nguyên tắc toán học" của Hong (zhuan) Huang (tou). Trong cuốn sách, Russell và Whitehead đã cố gắng "chính thức hóa" toán học một cách hoàn chỉnh. Nếu mục tiêu như vậy có thể đạt được, tất cả các kết quả toán học sẽ được xây dựng trên một nền tảng vững chắc theo cách đã được chứng minh. Hình bên dưới là một trang trong cuốn "Những nguyên lý toán học (Tập 2)":


Trong số đó, 110.643 là một mệnh đề: "1+1=2", và sau đó là chứng minh của định lý này. Bạn có thể tự hỏi, liệu 1+1 vẫn cần bằng chứng? Vâng, trong cuốn sách Nguyên tắc toán học, các số 0, 1, 2, ... được xác định chặt chẽ, và "cộng", "nhân", "bằng" phải được xác định chặt chẽ, và sau đó từng bước suy luận cần được chỉ ra. bằng chứng nghĩa là gì? Việc chứng minh có thể cực kỳ rườm rà, nhưng mọi bước lập luận đều chặt chẽ và đúng đắn. Một số lượng lớn các bằng chứng trong cuốn sách là máy móc, theo các tiên đề và quy tắc suy luận, một kiểu xây dựng bằng chứng được thực hiện, việc tìm kiếm các bằng chứng dường như được giao cho một người, và sau đó anh ta tìm kiếm một cách máy móc trong tập hợp các tiên đề và quy tắc suy luận mà không cần suy nghĩ.

Có vẻ như mọi người không còn xa lạ với "chứng minh định lý tự động".

Thật không may, Gödel đã chứng minh "Định lý bất toàn Gödel" [4] vào năm 1931, và Turing đã chứng minh tính không quyết định của bài toán dừng máy Turing vào năm 1936 [5]. Những kết quả này đã đặt dấu chấm hết cho sự tưởng tượng hàng thế kỷ này. Cho dù một hệ tiên đề được thiết kế tài tình đến đâu, nó cũng không thể nắm bắt được tất cả sự thật.

Bằng chứng không chỉ là một suy luận chặt chẽ, mà cô đọng tư duy sáng tạo mà dường như khó máy móc hóa. Chứng minh chứa rất nhiều "kiến thức", và mỗi bước đột phá đều nâng tầm nhận thức của chúng ta lên một tầm cao mới. Cho dù đó là một "cái nhìn sâu sắc" hay một "thuật toán" được xây dựng trong quá trình lập luận, nội hàm của chứng minh của một định lý thường vượt xa kết luận của chính định lý đó.

Những năm 1960: "Bằng chứng" == "Thủ tục"

Nửa thế kỷ sau, vào những năm 1960, các nhà logic học Haskell Curry và William Howard đã lần lượt khám phá ra nhiều “sự tương ứng kỳ diệu” trong “hệ thống logic” và “hệ thống tính toán - phép tính Lambda”, mà sau này được đặt tên là “Sự tương ứng Curry-Howard”. Phát hiện này khiến mọi người chợt nhận ra rằng "viết chương trình" và "viết chứng minh" thực ra hoàn toàn thống nhất về mặt khái niệm. Trong 50 năm tiếp theo, sự phát triển của các lý thuyết và công nghệ liên quan đã làm cho bằng chứng không còn nằm trên giấy nháp mà có thể được thể hiện bằng các chương trình. Ánh xạ đẳng cấu này rất thú vị: loại chương trình tương ứng với định lý chứng minh; chu trình tương ứng với quy nạp;... (một cuốn sách được đề xuất tại đây: "Software Foundation" (Bản dịch tiếng Trung của Software Foundations) [6]) . Trong khuôn khổ của người theo chủ nghĩa trực giác, chứng minh có nghĩa là xây dựng một thuật toán và xây dựng một thuật toán thực sự là viết mã. (Điều ngược lại cũng đúng, ừm, cái được coder viết ra không phải là code, mà là chứng minh toán học, :P)

Hiện nay, trong lĩnh vực khoa học máy tính, bằng chứng của nhiều lý thuyết đã thay đổi từ bản phác thảo trên giấy sang dạng mã, "ngôn ngữ lập trình bằng chứng" phổ biến hơn bao gồm Coq, Isabelle, Agda, v.v. Sử dụng lập trình để xây dựng bằng chứng, việc kiểm tra tính chính xác của bằng chứng có thể được chương trình hoàn thành một cách máy móc và chương trình có thể hỗ trợ nhiều công việc lặp đi lặp lại. Giống như phần mềm máy tính, tòa nhà chứng minh các lý thuyết toán học đang từng bước được xây dựng. Vào tháng 12 năm 1996, W. McCune đã sử dụng công cụ chứng minh định lý tự động EQP để chứng minh một phỏng đoán toán học 63 tuổi "Phỏng đoán Ronbins". Tờ New York Times sau đó đã đăng một bài báo có tựa đề "Bằng chứng toán học máy tính cho thấy sức mạnh suy luận" [7], một lần nữa bàn về khả năng máy móc có thể thay thế tư duy sáng tạo của con người hay không.

Việc sử dụng sự hỗ trợ của máy móc quả thực có thể giúp tư duy của các nhà toán học vươn tới những khoảng không gian chưa biết một cách hiệu quả, nhưng “đi tìm bằng chứng” vẫn là công việc khó khăn nhất. “Chứng minh xác minh” phải là một công việc đơn giản, máy móc và hạn chế. Đây là một "sự bất đối xứng" tự nhiên.

Những năm 1980: "bằng chứng" == "tương tác"

Năm 1985, Jobs vừa rời Apple và Tiến sĩ S. Goldwasser đến MIT sau khi tốt nghiệp, đồng thời viết một tác phẩm kinh điển với S. Micali và Rackoff có thể được ghi vào biên niên sử của khoa học máy tính: "Kiến thức trong tương tác hệ thống chứng minh rất phức tạp” [8].

Họ diễn giải lại từ "chứng minh" và đề xuất khái niệm hệ thống chứng minh tương tác: bằng cách xây dựng hai máy Turing để "tương tác" thay vì "lý do", để chứng minh liệu một mệnh đề có đúng trong xác suất hay không. Khái niệm "bằng chứng" đã được mở rộng một lần nữa.

Hình thức chứng minh tương tác là hai (hoặc nhiều máy Turing) "kịch bản đối thoại" hoặc Bản ghi. Và trong quá trình đối thoại này, rõ ràng có vai trò “người xác nhận” và “người xác minh” rõ ràng. Trong số đó, người chứng minh chứng minh cho người xác minh rằng một mệnh đề được thiết lập, đồng thời "không tiết lộ bất kỳ kiến ​​​​thức nào khác". Điều này được gọi là "bằng chứng không kiến ​​thức".

tiêu đề phụ

bằng chứng tương tác

Alice: Tôi muốn chứng minh với bạn rằng tôi có nghiệm của phương trình, w^3 - (w+1)^2 + 7 = 0 (nghiệm của phương trình: w=3)

Bob: được rồi, tôi đang nghe đây

Alice: Nhưng tôi sẽ không nói cho bạn biết x là bao nhiêu trừ khi bạn sẵn sàng trả tiền cho nó.

Bob: Vâng, nhưng bạn phải chứng minh rằng bạn có nghiệm của phương trình trước, sau đó tôi sẽ trả tiền cho bạn.

Alice: @#$%^& (công nghệ đen)

Bob: ?????? (nghệ đen)

Alice: '$@! (công nghệ đen)

Bob: ?????? (nghệ đen)

...... (Còn tiếp nghệ đen)

Alice: Được rồi, kết thúc rồi

Bob: Chà, bạn có nghiệm của phương trình, nhưng bạn sẽ cho tôi biết câu trả lời nếu tôi trả tiền cho bạn chứ?

Alice: Đừng nói nhảm nữa và trả tiền đi!

Ví dụ trên là một "bằng chứng tương tác". Giả sử Alice biết nghiệm của phương trình, f(w) = 0, làm thế nào Alice có thể thuyết phục Bob rằng cô ấy biết w? Alice đã kể cho Bob rất nhiều thông tin trong "giai đoạn công nghệ đen". Chà, câu hỏi quan trọng là, Bob có thể đoán w là gì từ rất nhiều thông tin mà Alice đã nói hay anh ấy có thể phân tích các manh mối về w không? Nếu Bob có khả năng này, Bob có thể không cần trả tiền, vì anh ta đã có được thông tin quý giá này rồi.

Xin lưu ý rằng nếu cuộc đối thoại giữa Alice và Bob là "không có kiến ​​thức", thì Bob không thể lấy được bất kỳ thông tin nào khác về w ngoại trừ w là nghiệm của f(w)=0. Điều này rất quan trọng, vì lợi ích của Alice.

Bây giờ xem lại thuật ngữ Zero-Knowledge Proof mà tiếng Anh gọi là “Bằng chứng tri thức bằng không”. Từ này có ba phần chính:

  • số không

  • chứng minh

  • chứng minh

Bạn có thể đã có một chút cảm giác, hãy thử diễn giải nó:

  • Zero: Alice đã tiết lộ kiến ​​thức "zero" về w, tức là không có kiến ​​thức nào bị rò rỉ.

  • Kiến thức: Ở đây nó đề cập đến w.

  • Bằng chứng: Đó là “phần công nghệ đen” trong đoạn hội thoại giữa Alice và Bob.

tiêu đề phụ

Bằng chứng không có kiến ​​​​thức tốt cho việc gì?

Khi nhắc đến công nghệ zero-knowledge proof, nhiều người nghĩ ngay đến những đồng tiền ẩn danh, chẳng hạn như Monero, chẳng hạn như ZCash. Thật vậy, những đồng tiền này đã phổ biến bằng chứng không kiến ​​thức rất tốt Bản thân tôi đã nghe thấy thuật ngữ bằng chứng không kiến ​​thức lần đầu tiên thông qua ZCash. Nhưng sau khi hiểu sâu hơn về công nghệ này, tôi cảm nhận sâu sắc rằng sức mạnh của công nghệ này còn hơn thế rất nhiều.

Công nghệ bằng chứng không kiến ​​thức có thể giải quyết vấn đề tin cậy của dữ liệu và điện toán!

Zhang San nói rằng anh ấy có 100 nhân dân tệ, Li Si nói rằng anh ấy đã tốt nghiệp Đại học Bắc Kinh và Wang Wu nói rằng anh ấy sẽ ăn trưa với Ba Feite. Nói suông không bằng chứng, Cho tôi xem bằng chứng.

Vậy làm thế nào "bằng chứng không kiến ​​thức" có thể giải quyết vấn đề tin cậy dữ liệu? Trong bài viết trước "zkPoD: Blockchain, Bằng chứng Zero-Knowledge và Xác minh chính thức, Thực hiện các giao dịch công bằng mà không cần trung gian và Zero Trust" [9], tôi đã đề cập đến một khái niệm "mô phỏng":

Công nghệ bằng chứng không kiến ​​thức có thể "mô phỏng" bên thứ ba để đảm bảo rằng một khẳng định nhất định là đáng tin cậy

Nói cách khác, khi chúng tôi nhận được dữ liệu được mã hóa, thì sẽ có bằng chứng không có kiến ​​thức. Bằng chứng không có kiến ​​thức này nói rằng "xác nhận X về dữ liệu là đúng", thì điều này tương đương với việc một thiên thần thì thầm vào tai chúng ta, "xác nhận X về dữ liệu là đúng"!

Đối với khẳng định X này, nó có thể rất linh hoạt, nó có thể là một thuật toán phức tạp NP. Nói một cách thông dụng, miễn là chúng ta có thể viết một chương trình (thuật toán thời gian đa thức) để đánh giá liệu một dữ liệu có thỏa mãn khẳng định X hay không, thì khẳng định này có thể được biểu thị bằng chứng minh không có kiến ​​thức. Theo thuật ngữ của giáo dân, miễn là phán đoán dữ liệu là khách quan, thì bằng chứng không kiến ​​thức sẽ được áp dụng.

Một số cách sử dụng bằng chứng không kiến ​​thức:

  • Bảo vệ quyền riêng tư dữ liệu: Trong một biểu mẫu dữ liệu ít nhiều sẽ có một số thông tin mà mình không muốn bị lộ ra ngoài, ví dụ như bảng điểm của mình năm đó, mình chỉ muốn chứng minh cho người khác thấy điểm mình đậu, nhưng mình không Tôi không muốn người khác biết mình đã làm gì, được 61 điểm hay 62 điểm thì xấu hổ lắm. Tôi không bị bệnh tim, nhưng công ty bảo hiểm cần biết điều này, nhưng tôi không muốn công ty bảo hiểm biết thông tin cá nhân của tôi. Sau đó, tôi có thể chứng minh với công ty bảo hiểm rằng tôi không bị đau tim, nhưng tất cả các hồ sơ bệnh án không cần phải phơi bày ra ngoài. Tôi là doanh nghiệp, tôi muốn vay vốn ngân hàng, tôi chỉ muốn chứng minh với ngân hàng là tôi làm ăn lành mạnh và có khả năng trả nợ, chứ tôi không muốn ngân hàng biết một số bí mật kinh doanh của mình.

  • Nén điện toán và mở rộng chuỗi khối: Trong số nhiều công nghệ mở rộng chuỗi khối, việc Vitalik sử dụng công nghệ zkSNARK có thể mang lại hiệu suất cải thiện hàng chục lần cho khung Ethereum hiện có. Do bằng chứng tính toán nên không cần lặp lại cùng một phép tính nhiều lần, trong kiến ​​trúc chuỗi khối truyền thống, phép tính tương tự được lặp lại nhiều lần, chẳng hạn như xác minh chữ ký, xác minh tính hợp pháp giao dịch, xác minh hợp đồng thông minh thực thi, v.v. Các quy trình tính toán này có thể được nén bằng công nghệ bằng chứng không kiến ​​thức.

  • Mã hóa liên lạc đầu cuối: người dùng có thể gửi tin nhắn cho nhau mà không cần lo lắng về việc máy chủ lấy tất cả các bản ghi tin nhắn. Đồng thời, các tin nhắn cũng có thể tạo ra bằng chứng không kiến ​​thức tương ứng theo các yêu cầu của máy chủ, chẳng hạn như nguồn của tin nhắn và mục đích gửi nó đến đất liền.

  • Xác thực danh tính: Người dùng có thể chứng minh với trang web rằng anh ta có khóa riêng hoặc biết câu trả lời bí mật mà chỉ người dùng biết, nhưng trang web không cần biết, nhưng trang web có thể xác nhận danh tính của người dùng bằng cách xác minh điều này bằng chứng không kiến ​​thức

  • Lưu trữ phi tập trung: Máy chủ có thể chứng minh với người dùng rằng dữ liệu của họ được lưu giữ đúng cách và không tiết lộ bất kỳ nội dung nào của dữ liệu.

  • Hồ sơ tín dụng: Hồ sơ tín dụng là một lĩnh vực khác có thể phát huy hết lợi thế của bằng chứng không có kiến ​​thức. Người dùng có thể hiển thị có chọn lọc hồ sơ tín dụng của mình cho bên kia.

  • Xây dựng một giao thức giao dịch hoàn toàn công bằng cho hàng hóa kỹ thuật số trực tuyến [9].

  • tiêu đề phụ

Ví dụ: Bài toán tô màu ba bản đồ

Hãy nói về một bài toán kinh điển, bài toán ba màu của bản đồ. Làm thế nào để tô màu một bản đồ có ba màu sao cho hai vùng liền kề bất kỳ có màu khác nhau. Chúng tôi chuyển đổi "bài toán tô ba màu bản đồ" này thành "bài toán tô ba đỉnh của đồ thị liên thông". Giả sử mỗi vùng có một thủ đô (nút), sau đó kết nối các nút liền kề, để bài toán tô màu bản đồ có thể chuyển thành bài toán tô màu đỉnh đồ thị liên thông.

Hãy thiết kế một giao thức tương tác:

  • "Người chứng nhận" Alice

  • "Người xác minh" Bob

Alice có trong tay câu trả lời cho ba màu của bản đồ, xem hình bên dưới. Đồ thị này có tổng cộng 6 đỉnh và 9 cạnh.

Bây giờ Alice muốn chứng minh với Bob rằng cô ấy có câu trả lời, nhưng cô ấy không muốn Bob biết câu trả lời. Alice sẽ làm gì?

Trước tiên, Alice cần thực hiện một số "biến đổi" trên bức tranh đã nhuộm và tạo ra sự thay đổi lớn về màu sắc, chẳng hạn như biến toàn bộ màu lục thành màu cam, biến toàn bộ màu lam thành màu lục và biến toàn bộ màu lục thành màu cam. Sau đó, Alice nhận được một câu trả lời tô màu mới, lúc này cô ấy che mỗi đỉnh của đồ thị mới bằng một mảnh giấy rồi đưa cho Bob xem.

Nhìn hình bên dưới, lúc này Bob chuẩn bị đi nước cờ (xem hình bên dưới), anh ấy muốn chọn ngẫu nhiên một "bên", lưu ý là ngẫu nhiên, Alice sẽ không để số ngẫu nhiên dự đoán vào nâng cao.

Giả sử Bob chọn cạnh dưới và nói với Alice.

Lúc này Alice bóc các mảnh giấy ở hai đầu của cạnh này và nhờ Bob kiểm tra, Bob thấy màu của hai đỉnh khác nhau nên Bob cho rằng phép thử này là đẳng cấu. Lúc này, Bob chỉ nhìn thấy một phần của đồ thị, liệu anh ta có thể tin chắc rằng việc tô màu các đỉnh của phần còn lại của đồ thị là ổn không? Chắc hẳn bạn cảm thấy như thế này là chưa đủ, chẳng lẽ Alice mới hiểu đúng không? Các đỉnh khác không lộ ra ngoài có thể được tô màu ngẫu nhiên.

Không thành vấn đề, Bob có thể yêu cầu Alice làm lại, xem hình bên dưới

Alice thay đổi màu một lần nữa, thay đổi màu lam thành màu tím, màu lục thành màu nâu, màu cam thành màu xám, sau đó phủ tất cả các đỉnh bằng giấy. Sau đó, Bob chọn một cạnh khác, chẳng hạn như trong hình trên, anh ta chọn một cạnh thẳng đứng, rồi bảo Alice mở tờ giấy ra để xem, nếu Bob thấy các đỉnh ở hai đầu của cạnh này có màu khác nhau, sau đó Bob sẽ Thời gian đã chậm lại một chút, có lẽ Alice thực sự có câu trả lời cho màu này. Tuy nhiên, hai lần vẫn chưa đủ và Bob muốn làm điều đó thêm vài lần nữa.

Sau đó, sau khi lặp lại ba bước này nhiều lần, xác suất để Alice có thể lừa và đánh lừa thành công Bob sẽ giảm theo cấp số nhân. Giả sử sau n vòng, xác suất để Alice ăn gian là

Ở đây |E| là số tất cả các cạnh trong đồ thị. Nếu n đủ lớn, xác suất này Pr sẽ trở nên rất, rất nhỏ và trở thành "không đáng kể".

tiêu đề phụ

Thông tin so với Kiến thức

  • Thông tin「Thông tin」

  • Kiến thức "Kiến thức"

Trong chứng minh tương tác của bài toán tô ba màu bản đồ, sau nhiều lần tương tác lặp đi lặp lại, Bob thu được rất nhiều thông tin, nhưng điều này giống như việc Alice gửi cho Bob một dãy số ngẫu nhiên, Bob không “biết” thêm được điều gì. Ví dụ: nếu Alice nói với Bob "1+1=2", Bob sẽ nhận được thông tin này, nhưng Bob không nhận được thêm "kiến thức" vì mọi người đều biết sự thật này.

Nếu Alice nói với Bob rằng số 2^2^41-1 là số nguyên tố, thì rõ ràng đây là "kiến thức", vì cần rất nhiều sức mạnh tính toán để tìm ra số đó có phải là số nguyên tố hay không.

Nếu Alice nói với Bob rằng có tổng cộng 2 đỉnh có màu xanh lục, thì Bob đã có được “kiến thức” quý ​​giá, vì dựa trên thông tin vừa có được, Bob có thể sử dụng máy Turing để giải 3 đỉnh trong thời gian ngắn hơn. Vấn đề nhuộm màu. Nếu Alice tiết lộ với Bob rằng màu của đỉnh ngoài cùng bên trái là màu da cam, thì rõ ràng, "thông tin" này về cơ bản không giúp Bob giải quyết vấn đề.

Chúng ta có thể thử định nghĩa rằng nếu "thông tin" mà Bob thu được trong quá trình tương tác có thể giúp cải thiện khả năng của Bob trong việc bẻ khóa trực tiếp bí mật của Alice, thì chúng ta nói rằng Bob "đã thu được kiến ​​thức". Có thể thấy rằng định nghĩa của từ kiến ​​​​thức có liên quan đến khả năng tính toán của Bob, nếu thông tin không làm tăng khả năng tính toán của Bob thì thông tin đó không thể được gọi là "kiến thức". Ví dụ: trong quá trình tương tác giữa Alice và Bob, Alice tung một đồng xu mỗi lần rồi nói cho Bob kết quả. Từ góc độ thông tin, thông tin mà Bob nhận được chỉ là một "sự kiện", nhưng Bob không nhận được bất kỳ "kiến thức nào". " bởi vì Bob hoàn toàn có thể tự tung đồng xu.

Sau đây trích dẫn phần tóm tắt trong cuốn sách "Những nền tảng của Mật mã học - Những công cụ cơ bản" [10]

  • "Kiến thức" liên quan đến "độ khó tính toán", nhưng "thông tin" thì không

  • "Kiến thức" liên quan đến những gì được biết đến công khai, trong khi "Thông tin" chủ yếu liên quan đến những gì được công khai một phần

tiêu đề phụ

Tính toán có thể kiểm chứng và các vấn đề về tính thỏa mãn của mạch

Nhìn vào bài toán ba màu trên bản đồ trên, bạn có cảm thấy đây chỉ là một bài toán học thuật, làm sao liên hệ nó với các bài toán thực tế? Bài toán tô màu ba bản đồ là một bài toán NP-Complete, là một thuật ngữ trong "lý thuyết tính toán". Một vấn đề khác gọi là "Vấn đề thỏa mãn mạch" cũng là một vấn đề NP-Complete. NP-Complete là một loại bài toán, quá trình giải của nó khó hoàn thành trong thời gian đa thức, tức là "khó giải", nhưng quá trình xác minh lời giải có thể hoàn thành trong thời gian đa thức, nghĩa là "dễ xác minh “.

Vậy mạch là gì? Đây là ba "mạch số học" khác nhau:

Có thể thấy một mạch bao gồm nhiều cổng, trong đó có cổng cộng và cổng nhân. Mỗi cổng có một số chân đầu vào và một số chân đầu ra. Mỗi cổng thực hiện một phép toán cộng hoặc phép toán nhân. Đừng nhìn đơn giản như vậy, mã chúng ta thường chạy (không có vòng lặp vô hạn) có thể được biểu diễn bằng các mạch số học.

Điều đó có nghĩa là gì? Hãy thử giải quyết vấn đề bảo vệ quyền riêng tư của dữ liệu bằng cách kết hợp "bằng chứng không kiến ​​thức" và "vấn đề về sự hài lòng của mạch".

Tiếp theo, hãy nghĩ về một tình huống: Bob đưa cho Alice một đoạn mã P và một đầu vào x, yêu cầu Alice chạy đoạn mã đó một lần rồi nói cho Bob biết kết quả. Có thể phép tính này cần tiêu tốn tài nguyên và Bob thuê ngoài quá trình tính toán cho Alice. Sau đó Alice chạy lại và nhận được kết quả là y. Sau đó nói với Bob y. Đây là câu hỏi:

Làm thế nào để Bob tin rằng kết quả của việc chạy mã P phải là y mà không cần chạy mã?

Đây là thời gian suy nghĩ, mọi người có thể suy nghĩ trong năm phút...

(năm phút sau……)

Một trong những phương pháp của Alice là chụp ảnh toàn bộ quá trình tính toán bằng điện thoại di động. Video này bao gồm CPU máy tính, bộ nhớ và trạng thái của từng bóng bán dẫn trong toàn bộ quá trình hoạt động. Rõ ràng là không thực tế để làm như vậy. Vậy có giải pháp nào khả thi hơn không?

Câu trả lời là Bob chuyển đổi chương trình P thành một mạch số học hoàn toàn tương đương, sau đó đưa mạch đó cho Alice. Alice chỉ cần tính toán mạch, sau đó quá trình này có thể được chụp ảnh bằng điện thoại di động hoặc viết ra giấy nếu quy mô mạch không quá lớn. Alice chỉ cần nhập tham số 6 vào mạch, sau đó ghi lại giá trị của tất cả các chân được kết nối với cổng trong quá trình hoạt động của mạch. Và giá trị của chân đầu ra mạch cuối cùng bằng y, thì Bob có thể chắc chắn rằng Alice đã thực hiện phép tính. Alice cần viết đầu vào và đầu ra của tất cả các cổng của mạch trên một tờ giấy và đưa cho Bob, tờ giấy này là bằng chứng của phép tính.

Bằng cách này, Bob có thể xác minh xem bằng chứng trên mảnh giấy này có chính xác hay không mà không cần tính toán lại mạch điện. Quá trình xác minh rất đơn giản:

Bob lần lượt kiểm tra xem đầu vào và đầu ra của mỗi cổng có thể thỏa mãn phương trình cộng hoặc phương trình nhân hay không.

Ví dụ, cổng số 1 là một cổng bổ sung, hai đầu vào của nó là 3, 4 và đầu ra của nó là 7, vì vậy dễ dàng biết rằng việc tính toán cổng này là chính xác. Khi Bob đã kiểm tra tất cả các cửa, anh ấy có thể chắc chắn rằng:

Alice thực sự đã tính toán, cô ấy không gian lận.

Nội dung trong bài báo này là một “Giải pháp” làm “thỏa mãn” mạch số học P.

Cái gọi là khả năng thỏa mãn của mạch có nghĩa là có một giải pháp thỏa mãn mạch. Nếu giá trị đầu ra của giải pháp này bằng một giá trị nhất định, thì giải pháp này có thể "đại diện" cho quá trình tính toán của mạch.

Đối với Alice, nếu Bob xác minh theo cách này, cô ấy hoàn toàn không có chỗ để gian lận. Nhưng phương pháp này rõ ràng có một nhược điểm:

  • Nhược điểm 1: Nếu mạch tương đối lớn, bằng chứng sẽ rất lớn và khối lượng công việc để Bob kiểm tra bằng chứng cũng rất lớn.

  • Bất lợi 2: Trong quá trình xác minh, Bob biết tất cả các chi tiết về hoạt động của mạch, bao gồm cả đầu vào.

  • công nghệ đen

Bây giờ hãy thực hiện một số thay đổi đối với cảnh Alice và Bob. Giả sử bản thân Alice có một bí mật, chẳng hạn như mật khẩu ngân hàng trực tuyến của cô ấy. Và Bob muốn biết liệu mật khẩu ngân hàng trực tuyến của Alice có dài 20 ký tự hay không. Bất quá Alice suy nghĩ một chút, nói cho hắn biết, mật khẩu độ dài hẳn là không thành vấn đề lớn. Tại thời điểm này, Bob chuyển đổi mã tính toán độ dài của chuỗi thành mạch Q và gửi mã đó cho Alice. Alice đã tính toán mật khẩu của chính mình với mạch Q, sau đó gửi cho Bob các chân của tất cả các cổng của mạch và mang lại kết quả tính toán là 20.

Đợi đã...t, đây là một vấn đề, sau khi Bob có được tất cả các chi tiết bên trong của hoạt động của mạch, anh ta không biết mật khẩu sao? Vâng, Alice rõ ràng là không thể làm điều đó. Vậy Alice nên làm gì?

Câu trả lời là có rất nhiều cách, bạn đọc yêu thích công nghệ blockchain chắc hẳn quen thuộc nhất với zkSNARK[11], zkSTARK[12], BulletProof[13] và một số công nghệ tương đối nhỏ, tất cả đều có thể giúp Alice làm được điều đó:

Theo kiểu không có kiến ​​thức, Alice chứng minh cho Bob thấy rằng cô ấy đã tính toán mạch điện và sử dụng thông tin đầu vào bí mật của mình.

Nói cách khác, "các giao thức chứng minh tính thỏa mãn của mạch không kiến ​​thức" này cung cấp cho Alice một vũ khí mạnh mẽ để chứng minh với Bob rằng mật khẩu ngân hàng trực tuyến của cô ấy có độ dài 20 và ngoài ra, Bob không còn có thể lấy được bất kỳ Thông tin hữu ích nào khác. Ngoài mật khẩu ngân hàng trực tuyến, về mặt lý thuyết, Alice có thể chứng minh cho Bob một số đặc điểm của bất kỳ dữ liệu riêng tư nào của cô ấy, nhưng không tiết lộ bất kỳ thông tin nào khác.

"Giao thức chứng minh sự hài lòng của mạch không có kiến ​​thức" cung cấp công nghệ trực tiếp nhất để bảo vệ quyền riêng tư/dữ liệu nhạy cảm

viết ở cuối

viết ở cuối

Cho dù đó là một định lý lý thuyết số tinh tế, một bài toán bản đồ ba màu hay một bài toán về sự thỏa mãn của mạch điện. Điểm chứng minh sự tồn tại là gì? Tất cả các bằng chứng đều thể hiện sự "bất đối xứng" giữa "bằng chứng" và "xác minh". Bằng chứng có thể là một hoạt động đòi hỏi nhiều tính toán hoặc trí óc, cho dù đó là "Định lý cuối cùng của Fermat" mất hàng trăm năm hay bằng chứng POW trong Bitcoin, những bằng chứng này cô đọng thời gian dành cho quá trình tìm kiếm bằng chứng. quá trình này có thể phức tạp một cách phi thực tế, đôi khi đòi hỏi phải có một thiên tài. Và quá trình xác minh phải (hoặc nên) là một hoạt động rất đơn giản, máy móc và có thể chấm dứt trong thời gian hợp lệ (đa thức). Theo một nghĩa nào đó, sự bất đối xứng này thực sự thể hiện tầm quan trọng của bằng chứng và thể hiện giá trị của bằng chứng không kiến ​​thức.

Nói một cách đại khái, "chứng minh" là sản phẩm của "logic", nhưng "logic" và "tính toán" có mối liên hệ chặt chẽ với nhau. Bạn có thể mơ hồ cảm thấy có mối liên hệ nào đó giữa "chứng minh" và "tính toán". Chúng xuyên suốt: ví dụ: suy luận máy móc, chứng minh biểu diễn, tính toán tương tác. Đây là một câu hỏi triết học thú vị nhưng lớn hơn.

người giới thiệu

người giới thiệu

  • [1] Simon, Singer, Xue Mi.

  • [2]  Alec Wilkinson. The Pursuit of Beauty: Yitang Zhang solves a pure-math mystery. The New Yorker. Feb. 2015.

  • [3] Martin, Davis, Zhang Butian.The Engine of Logic [M].Nhà xuất bản Khoa học và Công nghệ Hồ Nam, 2012.

  • [4] Raymond Smullyan. Gödel's Incompleteness Theorems, Oxford Univ.Press. 1991.

  • [5] Turing, Alan. "On computable numbers, with an application to the Entscheidungsproblem." Proceedings of the London mathematical society 2.1 (1937): 230-265.

  • [6] Pierce, Benjamin C., et al. "Software foundations."Bản dịch tiếng Trung:<https://github.com/Coq-zh/SF-zh

  • [7] Kolata, Gina. "Computer math proof shows reasoning power." Math Horizons 4.3 (1997): 22-25.

  • [8] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.

  • [9] zkPoD: Chuỗi khối, bằng chứng không kiến ​​thức và xác minh chính thức, thực hiện các giao dịch công bằng mà không cần trung gian và không tin tưởng. Ambi Lab. 2019.

  • [10] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

  • [11] Gennaro, Rosario, et al. "Quadratic span programs and succinct NIZKs without PCPs." AnnualInternational Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin, Heidelberg, 2013.

  • [12] Ben-Sasson, Eli, et al. "Scalable, transparent, and post-quantum secure computational integrity." IACR Cryptology ePrint Archive 2018 (2018): 46.

  • [13] Bünz, Benedikt, et al. "Bulletproofs: Short proofs for confidential transactions and more." 2018IEEE Symposium on Security and Privacy (SP). IEEE, 2018.

安全
Chào mừng tham gia cộng đồng chính thức của Odaily
Nhóm đăng ký
https://t.me/Odaily_News
Tài khoản chính thức
https://twitter.com/OdailyChina