간단하고 실용적인 관점에서 제로 지식 증명을 한 문장으로 이해하기

저자: benlaw.eth

이전에 몇 개의 제로 지식 증명에 관한 기사를 읽었지만 여전히 혼란스러웠던 적이 있나요? 이러한 기사들은 다음과 같은 문제를 가질 수 있습니다:

• ZKP의 본질을 깊이 있게 설명하지 않고 이야기나 동화를 예로 듭니다.
• 초보자에게는 너무 복잡한 암호학 용어, 수학 공식, 학술 논문 등이 포함되어 있습니다.

이 글에서는 ZKP에 대한 간결한 개요를 제공하고, 수학, 암호학 및 프로그래밍 관점에서 ZKP의 핵심 요소를 추가로 설명합니다.

색맹에게 색상 증명 제공하기

색맹 환자에게 두 공의 색상이 실제로 다르다는 것을 어떻게 증명할 수 있을까요? 사실 그렇게 복잡하지 않습니다:

그에게 두 개의 공을 손에 쥐게 하고, 등을 돌린 후 무작위로 두 공의 위치를 바꾸거나 바꾸지 않도록 선택하게 한 다음, 당신에게 보여줍니다. 당신은 그에게 두 공의 위치가 변했는지 여부를 알려줍니다.

그의 입장에서는, 당신이 무작위로 추측하여 증명을 완료할 수 있습니다. 그러나 이 과정을 수천 번 반복한다면: 당신이 항상 정답을 말할 수 있다면, 순전히 추측에 의존하여 계속해서 정답을 유지할 확률은 무시할 수 있을 정도로 작습니다. 따라서 이러한 방식으로 색맹 환자에게 두 공의 색상이 실제로 다르며, 우리가 인식하고 구별할 수 있는 능력이 있음을 증명할 수 있습니다.

색상 증명

위의 증명 과정은 전형적인 제로 지식 증명입니다:

• 검증자는 증명 과정에서 색상에 대한 어떤 지식도 얻을 수 없습니다. 왜냐하면 검증 과정 후에도 그는 색상을 구별할 수 있는 능력이 없기 때문입니다.
• 이 검증 과정은 결정적이지 않고 확률적입니다.
• 이 과정은 상호작용적이며 여러 번의 상호작용이 필요합니다. 그러나 제로 지식 증명에는 고급 기술을 통해 증명 과정을 비상호작용적으로 전환하는 많은 프로토콜도 있습니다.

지식의 증명

우리는 현실 세계에서의 제로 지식 증명의 예를 공유했습니다. 이제 이진 세계에서 제로 지식 증명을 어떻게 구현할 수 있는지 살펴보겠습니다.

Arthur는 Elon의 친구이며, 서로의 전화번호를 알고 있습니다. Betty는 Elon의 번호를 모릅니다. Arthur가 Betty에게 자신이 번호를 알고 있음을 증명하고 싶지만 번호를 유출하고 싶지 않다면 어떻게 해야 할까요?

지식 증명

하나의 미성숙한 방법은 Elon이 자신의 전화번호의 해시를 발표하고, Arthur가 프로그램을 통해 해시의 원상을 입력하여 프로그램이 계산하고 결과를 확인하는 것입니다. 이 방법에는 몇 가지 치명적인 결함이 있습니다:

• 해시에 따라, Betty는 무차별 대입 공격을 통해 원상을 얻을 수 있으며, 이를 해독할 확률은 무시할 수 없고, 얻은 결과는 거의 결정적입니다.
• Arthur는 해당 프로그램에 원상을 입력해야 합니다. 만약 프로그램이 Arthur의 컴퓨터에서 실행된다면, Betty는 의문을 가질 것입니다: "당신이 속이지 않았다는 것을 어떻게 알 수 있죠? 당신의 컴퓨터는 항상 당신의 증명이 맞다고 주장할 수 있습니다."
• 만약 프로그램이 Betty의 컴퓨터에서 실행된다면, Arthur는 자신의 입력 정보가 도용될까 걱정할 것입니다. 비록 프로그램의 눈에 보이는 코드에 도용 정보를 수집하는 명령이 없더라도 말입니다.
• 프로그램을 서로 다른 환경에서 실행할 수 없기 때문에, 이 신뢰 문제는 해결하기 어렵습니다.

일반적인 방법이 여기서 벽에 부딪혔습니다. 이제 제로 지식 증명이 등장할 때입니다!

암호학 기반 제로 지식 증명의 구현 방안

여기서는 제로 지식 증명에서 Sigma 프로토콜을 사용하여 문제를 해결하겠습니다. 이 방법이 비교적 간단하기 때문입니다. 또한 간결하고 이해하기 쉽게 하기 위해, 여기서는 엄격한 암호학 및 수학의 정의, 용어 및 유도 과정 등을 사용하지 않겠습니다.

핵심 프로세스

특정 지식을 가진 사람을 증명하기 위해 제로 지식 증명을 사용하는 방법은 다음과 같습니다:

Sigma 프로토콜

1. P차의 유한군과 그 생성원 g를 정의합니다. 이러한 이상한 용어가 무엇을 의미하는지 잠시 무시해도 됩니다.
2. 위의 정의에 따라, 지식을 가진 제3자가 지식(w)을 h = g^w (mod P) 방식으로 암호화하여 h를 발표합니다.
3. 증명자는 제로 지식 증명 프로세스를 시작합니다. 무작위 수 r을 생성하고 a = g^r을 계산한 후 a를 검증자에게 보냅니다.
4. 검증자는 무작위 수 e를 생성하고 증명자에게 보냅니다.
5. 증명자는 z = r + ew를 계산하여 검증자에게 보냅니다.
6. 검증자는 g^z == a·h^e (mod P)를 확인합니다. 만약 참이라면, 검증자는 실제로 그가 주장하는 지식을 가지고 있습니다.

좋습니다! 이 증명 프로토콜은 여기서 끝났습니다! 매우 간단하지만, 여전히 위의 일부 수학적 계산에 혼란스러울 수 있습니다. 그러나 괜찮습니다. 우리는 먼저 대략적인 인상을 가지고 깊이 이해하도록 하겠습니다.

수학 원리

이 프로세스 뒤에 있는 핵심 수학 원리는 이산 로그 문제입니다: P가 매우 큰 소수일 때, 주어진 h에 대해 h = g^w (mod P)를 만족하는 w를 찾는 것은 어렵습니다. 이 원리는 위의 모든 유사한 식에 적용됩니다.

이제 단계별로 분석해 보겠습니다:

암호화된 지식 h = g^w (mod P)는 무차별 대입 공격으로 해독하기 어렵습니다. 나머지 연산의 특성 때문에, 설령 해독되더라도 단일 결정적 해를 갖지 않습니다. 이는 증명자가 무차별 대입 공격을 통해 속여서 검증자를 속이는 것이 불가능하다는 것을 의미합니다.

그런 다음 3, 4, 5단계를 하나의 전체로 보아 이들이 왜 이러한 무작위 수를 교환해야 하는지 살펴보겠습니다:

I. 증명자는 자신의 비밀을 드러내고 싶지 않으므로 무작위 수로 이를 감추어야 합니다. 검증자도 무작위 수를 추가하여 그 지식을 자신이 검증할 수 있도록 하면서 증명자가 속이지 못하도록 해야 하며, 동시에 증명자의 비밀을 엿볼 수 없어야 합니다.

II. 만약 검증자가 먼저 무작위 수 e를 보냈다면 (즉, 3단계와 4단계를 바꾼다면), 명백히 증명자는 a = g^z·h^-e를 조작하여 최종 검증에서 검증자를 속일 수 있습니다. 지식이 없어도 그렇게 할 수 있습니다. 따라서 증명자는 먼저 약속(a=g^r)을 보내야 하며, r 본체는 아니어야 하여 속일 수 있는 장면을 피하고, 검증자가 w = (z - r)/e를 통해 비밀을 추출하지 못하도록 해야 합니다.

III. 약속을 받은 후, 검증자는 증명자에게 무작위 수 e를 보냅니다. 이 수는 그 자체로 또는 그 파생물으로 어떤 한쪽의 정보를 누설할 수 없으므로 암호화할 필요가 없습니다. 이후 증명자는 z = r + ew를 계산하여 z를 검증자에게 보냅니다. 검증자는 최종적으로 g^z = g^(r+ew) = g^r·(g^w)^e = a·h^e를 확인하여 증명자가 지식을 가지고 있는지 판단합니다.

이러한 왕복 구조를 통해 우리는 세 가지 속성을 얻었습니다:

완전성: 증명자가 올바른 지식을 입력할 때만 검증이 통과합니다.

신뢰성: 증명자가 잘못된 지식을 입력할 때만 검증이 실패합니다.

제로 지식성: 검증자는 검증 과정에서 어떤 지식도 얻을 수 없습니다.

위의 세 가지는 제로 지식 증명의 핵심 특성입니다. 수학과 암호학을 통해 우리는 기묘한 증명 체계를 구축했습니다. 당신은 지금까지 잘 해왔습니다. 이제 화려하고 신비로운 ZKP의 성전으로 정식으로 발을 내딛을 수 있을 것입니다.

즐거운 시간 되세요!

더 알아보기

시뮬레이터와 제로 지식성

이제 몇 가지 마법 같은 장면을 고려해 보겠습니다. 만약 증명자가 검증자가 생성한 무작위 수를 예측하거나 변조할 수 있는 초능력을 가지고 있다면, 우리는 이를 시뮬레이터라고 부릅니다.

시뮬레이터 vs 검증자

상상해보세요, 시뮬레이터가 검증자의 무작위 수 e가 생성되기 전에 이를 변조하여 자신이 설정한 값으로 생성되도록 했다고 가정해 보겠습니다. 위의 II에서 언급한 바와 같이, 이러한 능력은 시뮬레이터가 약속 a를 조작하여 검증자를 속일 수 있게 합니다. 시뮬레이터의 입력이 무엇이든 간에, 검증자는 항상 시뮬레이터가 지식을 가지고 있다고 결론을 내릴 것입니다. 그러나 실제로 그는 지식이 없습니다.

명백히, 이러한 사고 실험을 통해 우리는 검증자가 해당 제로 지식 증명 프로토콜에서 어떤 지식도 얻을 수 없음을 결론지을 수 있습니다. 즉, 그의 제로 지식성이 성립합니다:

제로 지식성 \<== ∀ 시뮬레이터 S, S(x)와 실제 프로토콜 실행이 구별할 수 없도록 하며, 여기서 S(x): 무작위로 z와 e를 선택하고 a = g^z·h^-e로 설정하며, (a,e,z)의 분포가 실제 무작위 수 환경과 일치하고 g^z=a·h^e를 만족합니다.

추출기와 신뢰성

또 다른 초능력자, 즉 추출기를 상상해 보겠습니다. 그는 시간 여행의 능력을 가지고 있습니다. 그러나 이번에는 추출기가 검증자의 역할을 하고, 정상적인 증명자를 상대합니다.

프로토콜이 끝나면, 추출기는 시간을 되돌려 프로토콜의 시작점으로 돌아가고, 이전 라운드에서 얻은 (z, e, a)를 보유합니다. 이제 프로토콜을 다시 실행합니다. 증명자는 초능력이 없기 때문에 시간 여행을 할 수 없고 고정된 시간선에서 결정적인 작업만 수행할 수 있으며, 그는 동일한 무작위 수 r과 약속 a = g^r을 생성합니다. 그러면 추출기는 증명자에게 새로운 무작위 수 e'를 생성할 수 있습니다.

증명자 vs 추출기

이제 추출기는 g^z = a·h^e, g^z' = a·h^e => g^(z-z') = h(e-e') => 암호화된 지식 h = g^((z-z')/(e-e')) => 지식 w = (z-z')/(e-e')를 얻었습니다.

명백히, 증명자가 실제로 지식을 가지고 있다면, 추출기는 항상 이를 추출할 수 있습니다. 즉, 완전성이 성립합니다: 완전성 \<== ∀ 추출기 E, 주어진 h에 대해, (a,e,z),(a,e',z')를 알고 e≠e'인 경우, w를 출력할 수 있습니다 s.t. (h,w) ∈ R.

완전성

완전성은 특별한 역할이 필요하지 않습니다. 왜냐하면: g^z = g^(r+ew) = g^r·(g^w)^e = a·h^e이기 때문입니다.