영지식 증명: 마술과 같지만 설명하겠습니다.

Peggy가 비밀을 공개하지 않고 자신이 비밀을 소유하고 있음을 Victor에게 증명해야 한다고 가정해 보겠습니다. 그녀는 빅터에게 자신이 정말로 비밀을 알고 있다고 확신시키는 방식으로 그렇게 할 수 있을까요? 이는 신원 시스템에서 사용할 수 있는 가장 강력한 암호화 프로세스 중 하나인 영지식 증명 (ZKP) 의 핵심 질문입니다.

예를 들어 Peggy가 디지털 운전 면허증을 가지고 있고 바텐더인 Victor에게 운전 면허증을 넘겨주거나 생년월일을 보여주지 않고도 자신이 21세 이상임을 증명하고 싶다고 가정해 보겠습니다. ZKP는 Peggy가 다른 것을 공개하지 않고도 Victor를 설득할 수 있는 방식으로 Peggy가 자신의 운전 면허증을 증명할 수 있도록 허용합니다(즉, 과잉 지식이 전혀 없음).

이 문제는 1980년대 MIT 연구원 Shafi Goldwasser, Silvio Micali 및 Charles Rackoff가 정보 유출에 대처하는 방법으로 처음 조사했습니다. 목표는 검증자인 Victor가 증명자인 Peggy에 대해 배울 수 있는 추가 정보의 양을 줄이는 것입니다.

ZKP의 작동 방식을 이해하는 한 가지 방법은 암호 해독가 Quisquater, Guillou 및 Berson1이 처음 출판한 Alibaba 동굴 이야기입니다. 다음 다이어그램은 예시를 제공합니다.

알리바바 동굴에는 입구에 연결된 단일 통로로 분리되는 A와 B라는 두 개의 통로가 있습니다. Peggy는 A와 B를 연결하는 문을 열 수 있는 비밀 코드를 가지고 있습니다. Victor는 코드를 구매하고 싶어하지만 Peggy가 이를 확실히 알 때까지는 비용을 지불하지 않습니다. Peggy는 Victor가 비용을 지불할 때까지 해당 정보를 Victor와 공유하지 않습니다.

Peggy가 코드를 알고 있음을 증명하는 알고리즘은 다음과 같이 진행됩니다.

• Victor는 동굴 밖에 서 있고 Peggy는 들어가서 통로 중 하나를 선택합니다. Victor는 Peggy가 어떤 경로를 택하는지 확인할 수 없습니다.
• 빅터는 동굴에 들어가 "A" 또는 "B"를 무작위로 부릅니다.
• Peggy는 들어갈 때 어떤 선택을 했는지에 관계없이 쉽게 문을 열 수 있기 때문에 올바른 통로에서 나옵니다.
• 물론 Peggy가 운이 좋아서 추측이 맞았을 수도 있으므로 Peggy와 Victor는 실험을 여러 번 반복합니다.

Peggy가 Victor가 선택한 통로로 항상 돌아올 수 있다면 Peggy가 실제로 코드를 알고 있을 확률이 높아집니다. 20번의 시도 후에 Peggy가 Victor가 어떤 편지를 부를지 추측할 확률은 백만 분의 1 미만입니다. 이는 Peggy가 비밀을 알고 있다는 확률론적 증거 입니다.

이 알고리즘을 사용하면 Peggy는 Victor에게 자신이 코드를 알고 있다고 확신할 수 있을 뿐만 아니라 Victor가 Peggy가 코드를 알고 있는 다른 사람을 설득할 수 없도록 보장합니다. Victor가 전체 거래를 기록한다고 가정해 보겠습니다. 관찰자가 보는 유일한 것은 Victor가 편지를 부르고 Peggy가 오른쪽 터널에서 나오는 것뿐입니다. 관찰자는 빅터와 페기가 관찰자를 속이기 위해 미리 일련의 편지에 동의하지 않았는지 확신할 수 없습니다.

따라서 Peggy는 Victor에게 자신이 비밀을 알고 있다는 사실을 부인할 수 없지만 다른 제3자에게는 자신이 비밀을 알고 있다는 사실을 부인할 수 있습니다. 이를 통해 그녀가 Victor에게 증명한 모든 것이 그들 사이에 유지되고 Victor가 이를 유출할 수 없도록 보장합니다. 적어도 그것이 Peggy로부터 왔다는 것을 증명하는 암호화 방식으로 말이죠. Peggy는 자신의 비밀과 자신이 그것을 알고 있다는 사실 모두에 대한 통제권을 유지합니다.

우리가 "지식 없음"이라고 말하고 Victor가 문제의 명제 외에는 아무것도 배우지 못한다고 말할 때 그것은 완전히 사실이 아닙니다. 알리바바의 동굴에서 페기는 자신이 비밀을 알고 있다는 것을 무지식으로 증명합니다. 그러나 Victor가 Peggy에 대해 알게 된 것 외에도 ZKP가 할 수 없는 일이 많이 있습니다. 예를 들어, Victor는 Peggy가 자신의 말을 듣고, 자신의 언어를 말하고, 걷고, 협조적이라는 것을 알고 있습니다. 또한 문을 여는 데 걸리는 대략적인 시간과 같은 동굴에 관한 정보를 배울 수도 있습니다. Peggy는 Victor에 대해 비슷한 것을 배웁니다. 따라서 현실은 증명이 완벽하게 제로 지식이 아니라 거의 제로 지식이라는 것입니다.

ZKP 시스템

알리바바 동굴의 예는 영지식 지식 증명이라고 불리는 ZKP의 매우 구체적인 사용입니다. Peggy는 자신이 알고 있는 것(또는 뭔가를 소유하고 있는 것)을 증명하고 있습니다. 보다 일반적으로 Peggy는 Victor에게 많은 사실을 증명하고 싶어할 수도 있습니다. 여기에는 명제 문구나 값도 포함될 수 있습니다. ZKP도 그렇게 할 수 있습니다.

지식이 없는 상태에서 명제를 증명할 수 있는 방법을 이해하려면 사회주의 백만장자 문제 라고도 불리는 다른 예를 고려해 보세요. Peggy와 Victor가 자신들이 공정한 임금을 받고 있는지 알고 싶어한다고 가정해 보겠습니다. 특히 그들은 동일한 금액을 받는지 알고 싶어하지만 구체적인 시간당 요금을 서로 또는 신뢰할 수 있는 제3자에게 공개하고 싶지 않습니다. 이 경우 Peggy는 자신이 비밀을 알고 있음을 증명하는 것이 아니라 평등(또는 불평등) 명제를 증명하고 있습니다.

단순화를 위해 Peggy와 Victor가 시간당 $10, $20, $30, $40 중 하나를 받는 것으로 가정합니다.

알고리즘은 다음과 같이 작동합니다.

• Peggy는 자물쇠 상자 4개를 구입하여 $10, $20, $30, $40라는 라벨을 붙였습니다.
• 그녀는 급여가 표시된 상자를 제외한 모든 상자의 열쇠를 버립니다.
• Peggy는 잠긴 상자를 모두 Victor에게 주었고 Victor는 급여가 적힌 상자 상단의 슬롯에 "+"가 표시된 종이 쪽지를 개인적으로 넣었습니다. 그는 다른 모든 상자에 "-"가 붙은 전표를 넣었습니다.
• Victor는 Peggy에게 상자를 돌려주고 Peggy는 비밀리에 자신의 열쇠를 사용하여 급여가 적힌 상자를 엽니다.
• 그녀가 "+"를 찾으면 그들은 같은 금액을 벌게 됩니다. 그렇지 않으면 다른 금액을 벌게 됩니다. 그녀는 이를 사용하여 Victor에게 사실을 증명할 수 있습니다.

이를 망각 이전 이라고 하며 VictorSalary = PeggySalary 명제가 지식이 없는 상태에서(즉, 다른 정보를 공개하지 않고) 참 또는 거짓임을 증명합니다.

이것이 작동하려면 Peggy와 Victor는 상대방이 곧 나올 것이라고 믿고 실제 급여를 명시해야 합니다. Victor는 Peggy가 세 개의 다른 열쇠를 버릴 것이라고 믿어야 합니다. Peggy는 Victor가 상자에 "+" 표시가 있는 전표 하나만 넣을 것이라고 믿어야 합니다.

자체 발급 인증서만으로 가능한 것 이상의 신뢰도를 구축하기 위해 디지털 인증서에 PKI가 필요한 것처럼, ZKP는 Peggy와 Victor가 자신이 말하는 것뿐만 아니라 다른 사람이 말하는 것으로부터 사실을 증명할 수 있는 시스템에서 더욱 강력합니다. 그들 자신. 예를 들어, Peggy와 Victor가 자신의 급여를 직접 주장하는 대신 HR 부서에서 서명한 문서에 의존하여 서로가 실제 급여를 명시하고 있음을 두 사람 모두 알 수 있다고 가정해 보겠습니다. 검증가능한 크리덴셜은 방법에 대한 확신과 데이터에 대한 신뢰를 제공하는 방식으로 ZKP를 사용하여 다양한 사실을 단독으로 또는 함께 증명할 수 있는 시스템을 제공합니다.

비대화형 ZKP

이전 예에서 Peggy는 일련의 상호 작용을 통해 Victor에게 사물을 증명할 수 있었습니다. ZKP가 실용적이려면 증명자와 검증자 간의 상호 작용이 최소화되어야 합니다. 다행히 SNARK라는 기술을 사용하면 비대화형 영지식 증명이 가능합니다.

SNARK에는 다음과 같은 속성이 있습니다(이름이 파생된 출처).

• 간결함: 메시지의 크기가 실제 증명의 길이에 비해 작습니다.
• Non-interactive : 일부 설정 외에 증명자는 검증자에게 하나의 메시지만 보냅니다.
• 논증(ARguments): 이것은 우리가 수학적으로 이해하는 증명이 아니라 실제로 무언가가 옳다는 논증입니다. 특히 증명자는 이론적으로 충분한 계산 능력이 주어지면 거짓 진술을 증명할 수 있습니다. 따라서 SNARK는 "완벽하게 건전한" 것이 아니라 "계산적으로 건전한" 것입니다.
• 지식의 증명: 증명자는 문제의 사실을 알고 있습니다.

일반적으로 이 프로세스 중에 검증자가 증명되는 사실 외에는 아무것도 배우지 않음을 나타내기 위해 앞면에 "zk"(영 지식의 경우)가 붙은 것을 볼 수 있습니다.

zkSNARK의 기본 수학에는 고차 다항식에 대한 동형 계산이 포함됩니다. 그러나 zkSNARK가 건전함을 보장하는 기본 수학을 모르더라도 zkSNARK가 어떻게 작동하는지 이해할 수 있습니다. 수학에 대해 더 자세히 알고 싶다면 Christian Reitwiessner의 "zkSNARKs in a Nutshell"을 추천합니다.

간단한 예로 Victor에게 어떤 값의 sha256 해시 H 가 주어졌다고 가정해 보겠습니다. Peggy는 Victor에게 s 공개하지 않고 sha265(s) == H 와 같은 값 s 알고 있음을 증명하려고 합니다. 관계를 포착하는 함수 C 정의할 수 있습니다.

 C(x, w) = ( sha256(w) == x )

따라서 C(H, s) == true 이고 w 에 대한 다른 값은 false 반환합니다.

zkSNARK를 계산하려면 세 가지 함수 G , P 및 V 가 필요합니다. G 는 lambda 라는 비밀 매개변수와 함수 C 사용하여 두 개의 공개 키, 증명 키 pk 와 검증 키 vk 생성하는 키 생성기입니다. 주어진 함수 C 에 대해 한 번만 생성하면 됩니다. 매개변수 lambda 다시 필요하지 않으며 이를 가진 사람은 누구나 가짜 증명을 생성할 수 있으므로 이 단계 후에는 파기되어야 합니다.

증명 함수 P 증명 키 pk , 공개 입력 x , 비공개(비밀) 증인 w 입력으로 사용합니다. P(pk,x,w) 실행 결과는 증명자가 C 만족하는 w 값을 알고 있다는 증거 prf 입니다.

검증 함수 V 는 증명 prf 정확하면 참이고 그렇지 않으면 거짓인 V(vk, x, prf) 계산합니다.

Peggy와 Victor로 돌아가서 Victor는 Peggy가 증명하기를 원하는 것을 나타내는 함수 C 선택하고 난수 lambda 생성한 다음 G 실행하여 증명 및 검증 키를 생성합니다.

 (pk, vk) = G(C, lambda)

Peggy는 lambda 의 가치를 학습해서는 안 됩니다. Victor는 Peggy와 C , pk 및 vk 공유합니다.

Peggy는 x = H 에 대해 C 만족시키는 값 s 알고 있음을 증명하고 싶어합니다. 그녀는 다음 값을 입력으로 사용하여 증명 함수 P 실행합니다.

 prf = P(pk, H, s)

Peggy는 검증 기능을 실행하는 Victor에게 증거 prf 제시합니다.

 V(vk, H, prf)

결과가 참이면 승자는 Peggy가 s 값을 알고 있다고 확신할 수 있습니다.

이 예에서처럼 함수 C 를 해시로 제한할 필요는 없습니다. 기본 수학의 한계 내에서 C 매우 복잡할 수 있으며 Victor가 Peggy가 증명하기를 원하는 모든 값을 동시에 포함할 수 있습니다.

이 기사는 O'Reilly Media에서 출판한 나의 저서 Learning Digital Identity 에서 발췌한 것입니다.

노트

1. Quisquater, 장 자크; 기유, 루이스 C.; 버슨, 토마스 A. (1990). 자녀에게 영지식 프로토콜을 설명하는 방법(PDF). 암호학의 발전 – CRYPTO '89: Proceedings. 컴퓨터 과학 강의 노트. 435. pp. 628–631. doi:10.1007/0-387-34805-0_60. ISBN 978-0-387-97317-3.