저자: Guo Yu

이 문서는 Github에 업데이트되었습니다.https://github.com/

소개:

블록체인은 거의 "기술"이 아니라고 생각합니다. 그것은 모든 것을 포괄하는 분야와 같습니다. 또는 형이상학적으로 말하자면, 블록체인은 다양한 이론적 기술을 통합하는 유기체에 가깝습니다.

영지식 증명은 신뢰를 구축하기 위한 중요한 기술이자 블록체인 유기체의 필수불가결한 부분입니다.

영지식 증명은 온체인 데이터와 오프체인 컴퓨팅을 연결하는 핵심 기술이며 온체인 데이터 프라이버시 보호를 실현하는 중요한 방법이기도 합니다.

입증하다

"입증하다"과거와 현재

증거란 무엇입니까? 많은 분들이 저와 같을 수 있습니다 이 두 단어를 보면 중학교 시험지에서 삼각형과 유사한 다양한 기하학적 도형이 떠오를 수밖에 없습니다 선생님이 마술처럼 보조선을 그리면 증명 과정이 갑자기 뻔해집니다 , 그리고 왜 기대하지 않았는지 후회합니다.

고대 그리스어: "증명" == "통찰력"

수학적 증명은 고대 그리스에서 시작되었습니다. 그들은 공리와 논리를 발명(발견)했고, 권위가 아닌 증거로 서로를 설득했다. 이것은 철저한 "분권화"입니다. 고대 그리스 이래로 이 방법론은 인류 문명의 전체 과정에 영향을 미쳤습니다.

위의 그림은 "피타고라스 정리"의 영리한 증거입니다. 역사상 많은 기발한 증거, 마법 같은 아이디어, 천재적인 영감이 있었습니다. 일단 명제가 증명되면 신이 할 수 있는 일은 아무것도 없습니다. 그건 그렇고, "신은 전능하지 않다"는 증거도 있습니다. 신은 들어 올릴 수 없는 돌을 만들 수 없습니다.

수학적 증명은 종종 극도로 심오한 "통찰력"을 숨깁니다. 저는 많은 사람들이 "페르마의 마지막 정리"[1] 이야기를 읽었다고 생각합니다. 저는 그것을 적을 수 없습니다." 맨 위. 최근 "푸앵카레 추측", 약간의 나이감이 있는 "골드바흐의 추측", 제가 매우 존경하는 중국 과학자 장이탕 등이 "골드스톤-핀츠"를 면밀히 연구한 후 10년 동안 -Yıldırım"과 "Bombieri-Friedlander-Iwaniec."의 "통찰력"을 증명한 후 "소수 사이의 제한된 간격"을 증명했습니다[2].

17세기 라이프니츠 이후 사람들은 천재의 섬광에 의존하지 않고 자동으로 증명을 완성할 수 있는 기계적 수단을 찾는 꿈을 꾸었습니다.

20세기 초: "증명" == "상징적 추론"

19세기 말 Cantor, Boole, Frege, Hilbert, Russell, Browe, Gödel 등은 형식 논리의 기호 체계를 정의했습니다. 그리고 "증명"은 형식 논리의 기호 언어로 작성된 추론 과정입니다. 논리 자체가 타당한가? 논리 자체가 "자체 일관성"이 있습니까? 논리적 추론 자체가 맞습니까?증명할 수 있습니까? 이로 인해 수학자/논리학자/컴퓨터 과학자는 기호 시스템, 구문 대 의미론, 신뢰할 수 있는 대 완전한, 재귀 대 무한대를 발명(발견)하게 되었습니다. (멋진 이야기의 이 부분은 "Logic Engine"[3]이라는 책을 참조하십시오).

1910년 러셀은 홍(전)황(두) 걸작 "수학의 원리"를 출판했습니다. 이 책에서 러셀과 화이트헤드는 수학을 완전히 "정식화"하려고 했습니다. 그러한 목표가 달성될 수 있다면 모든 수학적 결과는 입증된 방식으로 견고한 토대 위에 구축될 것입니다. 아래 그림은 "수학의 원리(2권)"의 한 페이지입니다.

그중 110.643은 "1+1=2"라는 명제이며, 이 정리의 증명은 다음과 같습니다. 1+1에도 여전히 증거가 필요한가요? 네, 책 『수학의 원리』에는 숫자 0, 1, 2, ...가 엄격하게 정의되어 있고, "덧셈", "곱셈", "같음"이 엄격하게 정의되어야 하며, 그러면 모든 추론 단계가 필요합니다. 지적할 것. 증명은 무슨 뜻인가요? 증명은 매우 번거로울 수 있지만 추론의 모든 단계는 엄격하고 정확합니다. 이 책의 많은 증명은 기계적입니다.공리와 추론 규칙에 따라 일종의 증명 구성이 수행됩니다.증명을 찾는 것은 사람에게 전달되는 것 같습니다. 생각하지 않고 추론 규칙.

사람들은 "정리의 자동 증명"에서 멀지 않은 것 같습니다.

불행하게도 괴델은 1931년에 "괴델 불완전성 정리"[4]를 증명했고, 튜링은 1936년에 튜링 기계 정지 문제의 결정 불가능성을 증명했습니다[5]. 이 결과는 이 수백 년 된 환상에 종지부를 찍었습니다. 공리계가 아무리 독창적으로 설계되더라도 모든 진실을 포착할 수는 없습니다.

증명은 단순히 엄밀한 추론이 아니라 기계화하기 어려울 것 같은 창의적 사고를 응축한 것이다. 증명에는 많은 "지식"이 포함되어 있으며 모든 돌파구는 우리의 인식을 새로운 수준으로 끌어 올립니다. 추론 과정에서 구성된 "통찰력"이든 "알고리즘"이든 정리의 증명이 내포하는 의미는 종종 정리 자체의 결론을 훨씬 뛰어넘습니다.

1960년대: "증거" == "절차"

반세기 후인 1960년대에 논리학자 하스켈 커리와 윌리엄 하워드는 "논리 시스템"과 "컴퓨팅 시스템 - 람다 미적분학"에서 많은 "매직 대응"을 연속적으로 발견했으며, 이를 나중에 "커리-하워드 대응"이라고 명명했습니다. 이 발견은 모든 사람들이 "프로그램 작성"과 "증명 작성"이 실제로 개념적으로 완전히 통합되어 있음을 깨닫게 했습니다. 이후 50년 동안 관련 이론과 기술의 발전으로 증명은 더 이상 초안에 머물지 않고 프로그램으로 표현될 수 있게 되었습니다. 이 동형 매핑은 매우 흥미롭습니다: 프로그램의 유형은 증명의 정리에 해당하고, 주기는 귀납법에 해당합니다. . 직관주의 프레임워크에서 증명은 알고리즘을 구성하는 것을 의미하고 알고리즘을 구성하는 것은 실제로 코드를 작성하는 것입니다. (그 반대도 마찬가지입니다. 음, 코더가 코딩하는 것은 코드가 아니라 수학적 증명입니다. :P)

현재 컴퓨터 과학 분야에서 많은 이론의 증명이 종이에 스케치에서 코드의 형태로 바뀌었고 더 인기 있는 "프로그래밍 언어 증명"은 Coq, Isabelle, Agda 등입니다. 프로그래밍을 사용하여 증명을 구성하면 증명의 정확성 검사가 프로그램에 의해 기계적으로 완료될 수 있으며 많은 반복 작업이 프로그램에 의해 지원될 수 있습니다. 컴퓨터 소프트웨어와 마찬가지로 수학 이론의 증명 체계도 단계적으로 구축되고 있습니다. 1996년 12월 W. McCune은 자동 정리 증명 도구 EQP를 사용하여 63년 된 수학적 추측인 "Ronbins 추측"을 증명했습니다. 그 후 New York Times는 "Computer Math Proof Shows Reasoning Power"라는 제목의 기사를 발표했습니다[7]. 기계가 인간의 창의적 사고를 대체할 수 있을지에 대한 가능성을 다시 한 번 논의합니다.

기계 지원의 사용은 수학자들의 생각이 더 많은 미지의 영역에 도달하도록 실제로 효과적으로 도울 수 있지만 "증거를 찾는 것"은 여전히 ​​가장 어려운 작업입니다. "검증 증명"은 단순하고 기계적이며 제한적인 작업이어야 합니다. 이것은 자연스러운 "비대칭"입니다.

1980년대: "증명" == "상호작용"

1985년 잡스는 막 애플을 떠났고 S. Goldwasser 박사는 졸업 후 MIT에 와서 S. Micali 및 Rackoff와 함께 컴퓨터 과학의 연대기에 기록될 수 있는 고전을 공동 집필했습니다. 증명 시스템이 복잡하다.성” [8].

그들은 "증명"이라는 단어를 재해석하고 대화형 증명 시스템의 개념을 제안했습니다. 명제가 확률적으로 참인지 여부를 증명하기 위해 "추리"가 아닌 "상호 작용"하는 두 개의 튜링 기계를 구성하는 것입니다. "증명"의 개념이 다시 확장되었습니다.

대화형 증명의 형식은 두 개(또는 그 이상의 튜링 기계) "대화 스크립트" 또는 Transcript입니다. 그리고 이 대화 과정에는 명시적인 "인증자" 역할과 명시적인 "검증자"가 있습니다. 그 중 증명자는 검증자에게 명제가 성립함을 증명함과 동시에 "다른 지식을 공개하지 않는다". 이것을 "영지식 증명"이라고 합니다.

보조 제목

대화형 증명

Alice: 내가 방정식 w^3 - (w+1)^2 + 7 = 0 (방정식의 해: w=3)에 대한 해를 가지고 있음을 증명하고 싶습니다.

밥: 알았어, 듣고 있어

앨리스: 하지만 기꺼이 지불하지 않는 한 x가 얼마인지는 말하지 않겠습니다.

Bob: 예, 하지만 먼저 방정식의 해를 가지고 있음을 증명해야 합니다. 그러면 제가 비용을 지불하겠습니다.

앨리스: @#$%^& (블랙 테크놀로지)

밥: ????????(검은 기술)

앨리스: &*#$@!(검은 기술)

밥: ????????(검은 기술)

...... (검은 기술에 계속)

앨리스: 알았어, 끝났어

밥: 음, 당신은 방정식에 대한 답을 가지고 있지만, 내가 당신에게 돈을 지불하면 답을 말해 줄 수 있습니까?

앨리스: 헛소리 그만하고 돈 내!

위의 예는 "대화식 증명"입니다. Alice가 방정식 f(w) = 0의 해를 알고 있다고 가정하면 Alice는 Bob이 w를 알고 있다고 어떻게 설득할 수 있습니까? Alice는 "검은 기술 단계"에서 Bob에게 많은 정보를 말했습니다. 음, 핵심 질문은 밥이 앨리스가 말한 많은 정보에서 w가 무엇인지 추측할 수 있습니까, 아니면 w에 대한 단서를 분석할 수 있습니까? Bob이 이 능력을 가지고 있다면 Bob은 이미 이 귀중한 정보를 얻었기 때문에 비용을 지불할 필요가 없을 수도 있습니다.

앨리스와 밥 사이의 대화가 "영지식"인 경우 밥은 w가 f(w)=0의 솔루션이라는 점을 제외하고는 w에 대한 다른 정보를 얻을 수 없습니다. 이것은 매우 중요하며 Alice의 관심사입니다.

이제 영어로 "Zero-Knowledge Proof"라고 하는 "Zero-Knowledge Proof"라는 용어를 검토하십시오. 이 단어에는 세 가지 주요 부분이 있습니다.

• 영

• 입증하다

• 입증하다

이미 약간의 느낌이 있을 수 있습니다. 해석해 보겠습니다.

• 제로: 앨리스는 w에 대한 "제로" 지식을 유출했습니다. 즉, 유출된 지식이 없습니다.

• 지식: 여기서는 w를 가리킵니다.

• 증거: Alice와 Bob 간의 대화에서 "검은 기술 부분"입니다.

보조 제목

영지식 증명이 좋은 이유는 무엇입니까?

영지식 증명 기술을 언급할 때 많은 사람들이 ZCash와 같은 Monero와 같은 익명의 코인을 생각합니다. 실제로 이 코인들은 영지식 증명을 아주 잘 대중화시켰습니다.저도 ZCash를 통해 처음으로 영지식 증명이라는 용어를 들었습니다. 하지만 이 기술을 더 깊이 이해하고 나니 이 기술의 힘이 이것보다 훨씬 더 크다는 것을 깊이 느낍니다.

영지식 증명 기술은 데이터와 컴퓨팅의 신뢰 문제를 해결할 수 있습니다!

Zhang San은 100 위안이 있다고 말했고 Li Si는 북경 대학을 졸업했다고 말했고 Wang Wu는 Ba Feite와 점심을 먹겠다고 말했습니다. 증거 없는 공허한 말, 증거를 보여줘

그렇다면 "영지식 증명"은 어떻게 데이터 신뢰를 해결할 수 있습니까? 이전 기사 "zkPoD: Blockchain, Zero-Knowledge Proof and Formal Verification, Realizing Fair Transactions Without Intermediaries and Zero Trust"[9]에서 "시뮬레이션"이라는 개념을 언급했습니다.

영지식 증명 기술은 특정 주장이 신뢰할 수 있는지 확인하기 위해 제3자를 "시뮬레이션"할 수 있습니다.

즉, 암호화된 데이터를 받으면 영지식 증명이 됩니다. 이 영지식 증명은 "데이터에 대한 X 주장이 참"이라고 말합니다. 그러면 이것은 천사가 우리 귀에 "데이터에 대한 X 주장이 참"이라고 속삭이는 것과 같습니다!

이 X 어설션의 경우 매우 유연할 수 있으며 NP 복잡성 알고리즘일 수 있습니다. 언어로 데이터가 X 주장을 만족하는지 판단하기 위한 프로그램(다항식 시간 알고리즘)을 작성할 수 있는 한 이 주장은 영지식 증명으로 표현될 수 있습니다. 평신도의 관점에서 데이터 판단이 객관적인 한 영지식 증명이 적용됩니다.

영지식 증명의 일부 용도:

• 데이터 개인 정보 보호: 데이터 양식에는 노출되고 싶지 않은 정보가 다소 있습니다. 내가 한 일을 남에게 알리고 싶지 않아 61점이든 62점이든 부끄러울 것이다. 나는 심장병이 없지만 보험 회사는 이것을 알 필요가 있지만 보험 회사가 내 개인 정보를 알기를 원하지 않습니다. 그러면 내가 심장 마비가 없다는 것을 보험 회사에 증명할 수 있지만 모든 의료 기록이 노출될 필요는 없습니다. 나는 기업이고 은행에서 대출을 받고 싶습니다. 은행에 내가 건전한 사업과 상환 능력을 가지고 있음을 증명하고 싶지만 은행이 우리의 사업 비밀 중 일부를 알기를 원하지 않습니다.

• 컴퓨팅 압축 및 블록체인 확장: 많은 블록체인 확장 기술 중에서 Vitalik의 zkSNARK 기술 사용은 기존 Ethereum 프레임워크에 수십 배의 성능 향상을 가져올 수 있습니다. 계산 증명으로 인해 동일한 계산을 여러 번 반복할 필요가 없으며, 기존 블록체인 아키텍처에서는 서명 확인, 거래 적법성 확인, 스마트 계약 확인 등 동일한 계산을 여러 번 반복하여 실행합니다. 이러한 계산 프로세스는 영지식 증명 기술로 압축할 수 있습니다.

• 단대단 통신 암호화: 사용자는 서로에게 메시지를 보낼 수 있지만 서버가 모든 메시지 기록을 받는 것에 대해 걱정할 필요가 없으며 동시에 메시지는 또한 해당 영지식 증명을 생성할 수 있습니다. 메시지의 소스 및 토지를 보내는 목적과 같은 서버의 요구 사항.

• 신원 인증: 사용자는 자신이 개인 키를 가지고 있거나 사용자만 알고 있는 비밀 답을 알고 있음을 웹 사이트에 증명할 수 있지만 웹 사이트는 알 필요가 없지만 웹 사이트는 이를 확인하여 사용자의 신원을 확인할 수 있습니다. 영지식 증명

• 분산형 스토리지: 서버는 데이터가 적절하게 보관되고 데이터의 내용을 공개하지 않는다는 것을 사용자에게 증명할 수 있습니다.

• 신용기록: 신용기록은 영지식 증명의 장점을 십분 발휘할 수 있는 또 다른 분야로, 사용자는 자신의 신용기록을 선택적으로 상대방에게 보여줄 수 있습니다.

• 온라인 디지털 상품에 대한 완전히 공정한 거래 프로토콜을 구축합니다[9].

• 보조 제목

예: 맵 삼중 색칠 문제

고전적인 문제인 지도의 삼색 문제에 대해 이야기해 봅시다. 인접한 두 지역이 서로 다른 색상이 되도록 세 가지 색상으로 지도를 색칠하는 방법. 우리는 이 "지도 삼색 문제"를 "연결된 그래프 정점 삼색 문제"로 변환합니다. 각 영역에 수도(노드)가 있다고 가정하고 인접한 노드를 연결하여 지도 색상 문제를 연결된 그래프 꼭지점 색상 문제로 전환할 수 있습니다.

상호 작용 프로토콜을 설계해 보겠습니다.

• "인증자" 앨리스

• "확인자" 밥

앨리스는 지도의 세 가지 색상에 대한 답을 손에 들고 있습니다. 아래 그림을 참조하세요. 이 그래프에는 총 6개의 정점과 9개의 모서리가 있습니다.

이제 Alice는 자신이 답을 가지고 있음을 Bob에게 증명하고 싶지만 Bob이 답을 알기를 원하지는 않습니다. 앨리스는 무엇을 할까요?

앨리스는 먼저 염색된 그림에 약간의 "변형"을 수행해야 하며, 모든 녹색을 주황색으로, 모든 파란색을 녹색으로, 모든 녹색을 주황색으로 바꾸는 것과 같이 색상에 큰 변화를 주어야 합니다. 그러자 Alice는 새로운 색칠 답을 얻었고, 이때 그녀는 새로운 그래프의 각 꼭지점을 종이로 덮은 다음 Bob에게 보여주었습니다.

아래 그림을 보십시오. 이때 Bob은 이동하려고 합니다(아래 그림 참조). 그는 "측면"을 무작위로 선택하려고 합니다. 이는 무작위이며 Alice는 예측된 난수를 허용하지 않습니다. 전진.

Bob이 아래쪽 가장자리를 선택하고 Alice에게 말한다고 가정합니다.

이때 Alice는 이 모서리의 양쪽 끝에서 종이 조각을 발견하고 Bob에게 확인을 요청합니다. Bob은 두 정점의 색상이 다른 것을 발견하므로 Bob은 이 테스트가 동형이라고 생각합니다. 이때 Bob은 그래프의 일부만 보고 나머지 그래프의 꼭짓점 색상이 괜찮다고 확신할 수 있습니까? 이것만으로는 충분하지 않다고 느끼실 것입니다. 아마도 Alice가 제대로 이해했을까요? 노출되지 않은 다른 꼭지점은 무작위로 색상이 지정될 수 있습니다.

상관없습니다. Bob은 Alice에게 다시 요청하면 됩니다. 아래 그림을 참조하세요.

Alice는 파란색을 보라색으로, 녹색을 갈색으로, 주황색을 회색으로 변경하면서 다시 색상을 변경한 다음 모든 꼭지점을 종이로 덮습니다. 그런 다음 Bob은 예를 들어 위의 그림에서와 같이 다른 가장자리를 선택하고 수직 가장자리를 선택한 다음 Alice에게 종이를 열어 보라고 요청합니다. Bob이 이 가장자리의 양쪽 끝에 있는 정점의 색상이 다른 것을 발견하면 그런 다음 Bob은 Time이 약간 흔들렸을 것입니다. 아마도 Alice는 이 색상에 대한 답을 가지고 있을 것입니다. 그러나 두 번은 여전히 ​​충분하지 않으며 Bob은 몇 번 더 하고 싶어합니다.

그런 다음 이 세 단계를 여러 번 반복하면 Alice가 속이고 성공적으로 Bob을 속일 수 있는 확률이 기하급수적으로 감소합니다. n 라운드 후에 Alice가 부정 행위를 할 확률은 다음과 같다고 가정합니다.

여기서 |E|는 그래프의 모든 모서리의 수입니다. n이 충분히 크면 이 확률 Pr은 매우 작아지고 "무의미"해집니다.

보조 제목

정보 대 지식

• 정보「정보」

• 지식 "지식"

지도 삼색 문제의 대화형 증명에서 여러 번 상호작용을 반복한 후 Bob은 많은 정보를 얻지만 이것은 Alice가 Bob에게 임의의 숫자를 보내는 것과 같으며 Bob은 더 많은 것을 "알지" 못합니다. 예를 들어 Alice가 Bob에게 "1+1=2"라고 말하면 Bob은 이 정보를 얻지만 Bob은 이 사실을 모두가 알고 있기 때문에 더 많은 "지식"을 얻지 못합니다.

Alice가 Bob에게 숫자 2^2^41-1이 소수라고 말하면 분명히 이것은 "지식"입니다. 왜냐하면 숫자가 소수인지 알아내는 데 많은 컴퓨팅 성능이 필요하기 때문입니다.

Alice가 Bob에게 초록색으로 표시된 총 2개의 정점이 있다고 말하면 Bob은 귀중한 "지식"을 얻은 것입니다. Bob은 방금 얻은 정보를 기반으로 Turing 기계를 사용하여 더 짧은 시간에 3개의 정점을 풀 수 있기 때문입니다. 염색 문제. Alice가 Bob에게 가장 왼쪽 꼭짓점의 색상이 주황색임을 밝히면 분명히 이 "정보"는 Bob이 문제를 해결하는 데 실질적으로 도움이 되지 않습니다.

우리는 상호 작용 과정에서 Bob이 얻은 "정보"가 Alice의 비밀을 직접 해독하는 Bob의 능력을 향상시키는 데 도움이 될 수 있다면 Bob이 "지식을 얻었다"고 말할 수 있다고 정의할 수 있습니다. 지식이라는 단어의 정의가 Bob의 컴퓨팅 파워와 관련되어 있음을 알 수 있으며, 정보가 Bob의 컴퓨팅 파워를 증가시키지 않으면 정보를 "지식"이라고 부를 수 없습니다. 예를 들어 Alice와 Bob의 상호 작용 중에 Alice는 매번 동전을 던진 다음 Bob에게 그 결과를 알려줍니다. " Bob이 완전히 동전을 던질 수 있기 때문입니다.

다음은 "Foundations of Cryptography - Basic Tools"라는 책의 요약을 인용한 것입니다[10].

• "지식"은 "계산 난이도"와 관련이 있지만 "정보"는 그렇지 않습니다.

• "지식"은 공개적으로 알려진 것과 관련이 있는 반면, "정보"는 주로 부분적으로 공개된 것과 관련이 있습니다.

보조 제목

검증 가능한 계산 및 회로 만족 문제

위의 지도에서 삼색 문제를 보면 이것이 단지 학문적 문제라는 느낌이 들며 실제 문제와 어떻게 연관시킬 수 있습니까? 맵 3 색 지정 문제는 "계산 이론"의 용어인 NP-완전 문제입니다. "Circuit Satisfiable Problem"이라는 또 다른 문제는 NP-완전 문제입니다. NP-Complete는 문제의 일종으로 그 해결 과정은 다항식 시간에 완료하기 어려운 즉, "해결하기 어려움"이지만 해결을 검증하는 과정은 다항식 시간, 즉 "확인하기 간단함"으로 완료할 수 있습니다. ".

그렇다면 회로란 무엇인가? 다음은 세 가지 "산술 회로"입니다.

회로가 더하기 게이트와 곱셈 게이트를 포함하여 많은 게이트로 구성되어 있음을 알 수 있습니다. 각 게이트에는 여러 개의 입력 핀과 여러 개의 출력 핀이 있습니다. 각 게이트는 더하기 연산 또는 곱하기 연산을 수행합니다. 너무 단순해 보이지 마십시오. 우리가 일반적으로 실행하는 코드(무한 루프 없이)는 산술 회로로 나타낼 수 있습니다.

이것은 무엇을 의미 하는가? "영지식 증명"과 "회로 만족 문제"를 결합하여 데이터 개인 정보 보호 문제를 해결해 봅시다.

다음으로 시나리오에 대해 생각해 보십시오. Bob은 Alice에게 코드 P와 입력 x를 제공하고 Alice에게 한 번 실행하도록 요청한 다음 Bob에게 결과를 알립니다. 이 계산은 리소스를 소비해야 할 수 있으며 Bob은 계산 프로세스를 Alice에게 아웃소싱합니다. 그런 다음 Alice는 다시 실행하여 결과 y를 얻었습니다. 그런 다음 Bob y에게 말하십시오. 여기에 질문이 있습니다.

Bob이 코드를 실행하지 않고 코드 P를 실행한 결과가 y여야 한다고 믿게 만드는 방법은 무엇입니까?

여기 생각할 시간이 있습니다. 누구나 5분 동안 생각할 수 있습니다...

(오분 뒤……)

Alice의 방법 중 하나는 전체 계산 과정을 휴대폰으로 사진을 찍는 것입니다 이 비디오에는 컴퓨터 CPU, 메모리 및 전체 연산 과정 동안 각 트랜지스터의 상태가 포함됩니다. 그렇게 하는 것은 명백히 비현실적입니다. 그렇다면 더 실현 가능한 해결책이 있을까요?

대답은 Bob이 프로그램 P를 완전히 동등한 산술 회로로 변환한 다음 회로를 Alice에게 제공한다는 것입니다. Alice는 회로를 계산하기만 하면 되며, 회로 규모가 그리 크지 않은 경우 휴대폰으로 프로세스를 사진으로 찍거나 종이에 기록할 수 있습니다. Alice는 회로에 매개변수 6을 입력하고 회로가 작동하는 동안 게이트에 연결된 모든 핀의 값을 기록하기만 하면 됩니다. 그리고 최종 회로 출력 핀의 값이 y와 같으면 Bob은 Alice가 계산을 수행했음을 확신할 수 있습니다. 앨리스는 회로의 모든 게이트의 입력과 출력을 종이에 써서 밥에게 건네줘야 하는데 이 종이가 계산 증명이다.

이런 식으로 Bob은 회로를 다시 계산하지 않고도 이 종이에 있는 증명이 올바른지 확인할 수 있습니다. 확인 프로세스는 매우 간단합니다.

Bob은 각 게이트의 입력과 출력이 덧셈 방정식이나 곱셈 방정식을 만족하는지 차례로 확인합니다.

예를 들어, 1번 게이트는 덧셈 게이트이고 두 개의 입력은 3, 4이고 출력은 7이므로 이 게이트의 계산이 정확하다는 것을 쉽게 알 수 있습니다. Bob이 모든 문을 확인했으면 다음을 확인할 수 있습니다.

Alice는 실제로 계산을 했습니다. 그녀는 속이지 않았습니다.

이 논문의 내용은 산술 회로 P를 "만족시키는" 솔루션 "솔루션"입니다.

소위 회로 만족 가능성은 회로를 만족시키는 솔루션이 있음을 의미합니다. 이 솔루션의 출력 값이 특정 값과 같으면 이 솔루션은 회로의 계산 프로세스를 "나타낼" 수 있습니다.

Alice의 경우 Bob이 이런 식으로 확인하면 부정 행위의 여지가 전혀 없습니다. 그러나 이 방법에는 분명히 다음과 같은 단점이 있습니다.

• 단점 1: 회로가 상대적으로 크면 증명이 매우 커지고 Bob이 증명을 확인하는 작업량도 매우 커집니다.

• 단점 2: 검증 과정에서 Bob은 입력을 포함하여 회로 작동의 모든 세부 사항을 알고 있습니다.

• 검은 기술

지금 Alice와 Bob 장면을 약간 변경해 보겠습니다. Alice 자신이 온라인 뱅킹 암호와 같은 비밀을 가지고 있다고 가정합니다. 그리고 Bob은 Alice의 온라인 뱅킹 암호 길이가 20자인지 알고 싶어합니다. 그러나 Alice는 잠시 생각하고 암호의 길이는 큰 문제가 되지 않아야 한다고 말했습니다. 이때 Bob은 문자열의 길이를 계산하는 코드를 회로 Q로 변환하여 Alice에게 보냅니다. Alice는 회로 Q로 자신의 암호를 계산한 다음 Bob에게 회로의 모든 게이트 핀을 보냈고 계산 결과 20을 가져왔습니다.

잠깐만요, 밥이 회로 작동에 대한 모든 내부 세부 정보를 얻은 후에 문제가 됩니다. 밥이 암호를 모르나요? 예, Alice는 분명히 그렇게 할 수 없습니다. 그럼 앨리스는 어떻게 해야 할까요?

블록체인 기술을 좋아하는 독자라면 zkSNARK[11], zkSTARK[12], BulletProof[13] 및 상대적으로 작은 일부 기술에 가장 익숙할 것입니다.

영지식 방식으로 Alice는 Bob에게 자신이 회로를 계산하고 비밀 입력을 사용했음을 증명합니다.

즉, 이러한 "영지식 회로 만족 증명 프로토콜"은 Alice에게 그녀의 온라인 뱅킹 암호 길이가 20이고 그 외에도 Bob이 더 이상 다른 유용한 정보를 얻을 수 없음을 증명할 강력한 무기를 제공합니다. 온라인 뱅킹 암호 외에도 Alice는 이론적으로 Bob에게 개인 데이터의 일부 특성을 증명할 수 있지만 다른 정보는 공개하지 않습니다.

"영지식 회로 만족 증명 프로토콜"은 프라이버시/민감 데이터 보호를 위한 가장 직접적인 기술을 제공합니다.

마지막에 쓰기

마지막에 쓰기

미묘한 정수론 정리든, 삼색 지도 문제든, 회로 만족 문제든. 존재 증명의 요점은 무엇입니까? 모든 증명은 "증명"과 "검증" 사이의 "비대칭성"을 구현합니다. 증명은 수백 년이 걸린 "Fermat의 마지막 정리"이든 비트코인의 POW 증명이든, 계산적으로나 정신적으로 매우 소모적인 활동일 수 있습니다. 이러한 증명은 증명을 찾는 과정에서 소요되는 시간을 압축합니다. 에너지, 증명 프로세스는 비현실적으로 복잡할 수 있으며 때로는 천재가 필요합니다. 그리고 검증 프로세스는 (다항식) 유효 시간에 매우 단순하고 기계적이며 종료 가능한 활동이어야 합니다(또는 그래야 합니다). 어떤 의미에서 이 비대칭성은 실제로 증명의 중요성을 구현하고 영지식 증명의 가치를 보여줍니다.

대략적으로 말하면 "증명"은 "논리"의 산물이지만 "논리"와 "계산"은 불가분의 관계입니다. "증명"과 "계산" 사이에 어떤 연결이 있는지 막연하게 느낄 수 있습니다. 표현, 대화식 계산. 이것은 흥미롭지만 더 큰 철학적 질문입니다.

참조

참조

• [1] 사이먼, 싱어, 쉬에미 페르마의 마지막 정리: 358년 동안 세계 현자를 곤혹스럽게 만든 미스터리 [M] 상하이 번역 출판사, 1998.

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

• [3] Martin, Davis, Zhang Butian. 논리 엔진 [M]. Hunan Science and Technology Press, 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."중국어 번역:<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: 블록체인, 영지식 증명 및 공식 검증, 중개자 및 제로 트러스트 없는 공정한 거래 실현 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.