Loading...
시리즈: Zcash from First Principles . 아티클 5 . 영지식 증명 대상 독자: 입문자. 이전의 모든 아티클(유한체, 곡선, 커밋먼트, 머클 트리)을 바탕으로 하지만, 각 개념은 필요할 때마다 다시 떠올릴 수 있도록 설명합니다. 이 글을 읽고 얻게 될 것: 영지식 증명이 무엇인지, 그것이 제공하는 세 가지 보장, 임의의 명제가 어떻게 증명되는지, 그리고 Zcash의 Sapling과 Orchard를 구동하는 것이 무엇인지에 대한 직관적이면서도 정확한 이해.
이 글은 이 시리즈 전체가 향해 오던 목적지입니다. 아티클 0부터 우리는 결제가 "장막 뒤에서" 검증된다고, 아무것도 드러내지 않은 채 올바름이 증명된다고 계속 말해 왔습니다. 영지식 증명은 바로 그 장막입니다. 그리고 이것이야말로 우리가 처음 던졌던 역설을 마침내 해결해 주는 핵심입니다. 어떻게 대중은 볼 수 없는 거래를 검증할 수 있을까요?
Zcash의 핵심에 있는 모순을 다시 떠올려 봅시다.
이 둘은 서로 양립할 수 없어 보입니다. 검증은 보는 것을 필요로 하는 듯합니다. 프라이버시는 보는 것을 금지합니다. 이 둘을 화해시키지 못한다면, 누구나 신뢰할 수 있는 프라이빗 머니는 존재할 수 없습니다.
영지식 증명(ZKP) 은 그 화해입니다. 그것은 증명자(prover) 가 검증자(verifier) 에게 어떤 명제가 참이라는 사실을 그것이 참이라는 사실 외에는 아무것도 드러내지 않고 납득시키게 해줍니다. 금액도 없습니다. 신원도 없습니다. 노트도 없습니다. 오직 이것만 있습니다: "여기 있는 모든 것은 규칙을 따릅니다." 먼저 어떤 복잡한 기계장치도 없이 직관부터 쌓아 봅시다.
비밀번호를 말하지 않고도 알고 있음을 증명하기. 어떤 웹사이트는 비밀번호 자체를 보지 않고도, 오직 그 비밀번호로만 열 수 있는 무언가를 당신이 여는 모습을 확인함으로써 당신이 비밀번호를 안다는 사실을 검증할 수 있습니다. 당신은 공개 없이 지식을 증명합니다.
색맹 친구와 두 개의 공. 당신은 빨간 공 하나와 초록 공 하나를 들고 있는데, 색맹인 친구에게는 둘이 똑같아 보입니다. 당신은 그 공들이 서로 다른 색이라는 것을, 어느 것이 어느 색인지는 말하지 않고 친구에게 납득시키고 싶습니다. 친구는 두 공을 등 뒤로 숨기고, 선택적으로 서로 바꾼 뒤 하나를 보여줍니다. 당신은 그가 공을 바꿨는지 말합니다. 공들이 정말 다르다면 당신은 항상 맞습니다. 공들이 사실 동일했다면 당신은 추측하는 것뿐이고, 절반의 확률로만 맞습니다. 20번 반복한 뒤에도 당신이 한 번도 틀리지 않았다면, 친구는 두 공의 색이 다르다고 납득합니다. 하지만 어느 공이 빨간색인지는 끝내 알지 못합니다. 그는 어떤 사실에는 확신을 갖게 되지만, 그 외에는 아무것도 배우지 못합니다. 이것이 영지식의 축소판입니다.
동굴. 고리 모양의 동굴 맨 뒤에는 비밀 주문을 알아야만 열 수 있는 마법의 문이 있습니다. 당신은 그 주문을 안다고 주장합니다. 그것을 드러내지 않고 증명하려면 이렇게 하면 됩니다: 검증자는 밖에서 기다리고, 당신은 안으로 들어가 왼쪽 또는 오른쪽 통로를 무작위로 선택합니다. 그러면 검증자가 당신에게 어느 쪽에서 나오길 원하는지 외칩니다. 당신이 정말 주문을 안다면 언제나 그렇게 할 수 있습니다(필요하다면 문을 열어 반대편으로 넘어갈 수 있으니까요). 거짓말을 하고 있다면 매 라운드마다 운 좋게 맞는 경우에만 올바른 쪽으로 나올 수 있고, 확률은 50 대 50입니다. 이것을 20번 반복하면 허풍쟁이가 끝까지 살아남을 확률은 백만 분의 일보다도 작습니다.
이 동굴 이야기는 조용히 영지식 증명이 반드시 제공해야 하는 세 가지 보장을 보여 줍니다.
| 보장 | 동굴 이야기에서는 | Zcash에서는 |
|---|---|---|
| 완전성(Completeness) | 주문을 알고 있다면 언제나 올바른 쪽으로 나온다 | 유효한 거래는 언제나 받아들여지는 증명을 만든다 |
| 건전성(Soundness) | 허풍쟁이는 압도적으로 높은 확률로 들통난다 | 사기 거래(위조된 돈, 이중 지불)는 받아들여지는 증명을 만들 수 없다 |
| 영지식성(Zero-knowledge) | 검증자는 비밀 주문을 절대 듣지 못한다 | 네트워크는 금액, 주소, 어떤 노트인지도 결코 알지 못한다 |
이 중 하나라도 실패하면 시스템은 무너집니다. 완전성이 없으면 정직한 사용자가 거부되고, 건전성이 없으면 위조자가 돈을 찍어내며, 영지식성이 없으면 프라이버시는 사라집니다.
동굴은 하나의 재미있는 사실을 증명합니다. 하지만 Zcash는 훨씬 풍부한 명제를 증명해야 합니다: "나는 트리 안에 아직 사용되지 않은 노트를 알고 있고, 그것을 사용할 권한이 있으며, 그 nullifier는 올바르게 계산되었고, 내 입력의 합은 출력의 합과 같다." 공과 동굴에서 어떻게 이런 데까지 갈 수 있을까요?
그 다리는 이 시리즈 전체를 관통하는 하나의 아이디어입니다.
계산으로 검사할 수 있는 어떤 명제든, 유한체 위의 덧셈과 곱셈의 네트워크인 산술 회로로 다시 쓸 수 있습니다(아티클 1).
회로를, 그 명제가 참일 때에만 모두 만족되는 산술 제약들의 목록이라고 생각해 보세요. 모든 것이 검사를 통과하게 만드는 비공개 입력들, 즉 당신의 노트, 당신의 키, 머클 경로가 바로 증인(witness) 입니다.
이것이 우리가 아티클 1에서 유한체를, 아티클 3에서 ZK 친화적 해시를 다뤘던 이유입니다. 회로는 유한체 산술을 말하는 언어이기 때문에, 명제 안의 모든 연산(해시와 아티클 4의 머클 경로 올라가기까지 포함해)은 그 방식으로 표현되어야 합니다. 각 연산을 더 저렴하게 표현할 수 있을수록, 증명은 더 작아지고 더 빨라집니다.
동굴 예시는 많은 왕복 상호작용이 필요했습니다. 하지만 블록체인에서는 이것이 비실용적입니다. 증명은 한 번 게시되어야 하고, 누구나 그것을 영원히 검사할 수 있어야 하기 때문입니다. 이 문제는 두 가지 개선으로 해결됩니다.
비대화형(Fiat-Shamir 아이디어). 검증자가 실시간으로 무작위 도전을 외치는 대신, 증명자는 자기 자신이 지금까지 만든 증명을 해시해서 "무작위 도전"을 스스로 생성합니다. 좋은 해시는 예측 불가능하기 때문에(아티클 3), 증명자는 자신에게 유리하게 도전을 조작할 수 없습니다. 수다스러운 대화는 나중에 누구나 검사할 수 있는 단일한 자기완결적 증명으로 압축됩니다. 상호작용은 필요 없습니다.
간결성(succinct). 최고의 시스템은 명제가 얼마나 크든 상관없이, 증명을 아주 작고 매우 빠르게 검증 가능하게 만듭니다. 이 부분이야말로 정말 놀라운 점입니다.
Sapling이 사용하는 시스템인 Groth16 증명은 대략 192바이트 정도이며, 그것이 증명하는 명제가 작든 거대하든 밀리초 단위로 검증됩니다. 수백 바이트만으로도 수천 개의 제약이 들어간 계산을 증명할 수 있습니다.
이 둘을 합치면 어디서나 보게 될 약어가 나옵니다.
zk-SNARK = zero-knowledge Succinct Non-interactive ARgument of Knowledge. 영지식(아무것도 드러내지 않음), 간결함(작고 빠름), 비대화형(한 번에 끝남), 지식의 논증(argument of knowledge, 증명자가 실제로 유효한 증인을 알고 있음).
공짜 점심은 없습니다. 많은 SNARK는 회로를 위한 공개 파라미터를 생성하는 일회성 설정(setup) 을 필요로 합니다. 이 설정은 부산물로 비밀 난수를 만들어내고, 그 비밀은 반드시 파기되어야 합니다. 누군가 그것을 보관했다면, 그 사람은 증명을 위조할 수 있고, 즉 돈을 위조할 수 있습니다(하지만 중요한 점은, 그럼에도 프라이버리 자체를 깨뜨릴 수는 없다는 것입니다).
이 남아 있는 비밀은 toxic waste 라는 별명으로 불립니다. 이것을 안전하게 폐기하기 위해 Zcash는 많은 독립적인 참여자들이 각자 난수를 보태는 정교한 다자간 세리머니를 진행했습니다. 그들 중 단 한 명이라도 자기 몫을 정직하게 파기했다면, toxic waste는 복구할 수 없습니다.
더 새로운 시스템들은 이 요구사항 자체를 없앴고, 그것이 바로 Zcash가 시간이 지나며 증명 시스템을 발전시킨 가장 큰 이유 중 하나입니다.
| 설계 | 증명 시스템 | 신뢰된 설정? | 기반 |
|---|---|---|---|
| Sprout (가장 초기) | 초기 zk-SNARK | 예 | 원래 세리머니 |
| Sapling | Groth16 | 예 (다자간 "Powers of Tau" + Sapling 세리머니) | BLS12-381 (아티클 2) |
| Orchard (현재) | Halo 2 | 신뢰된 설정 없음 | Pallas / Vesta (아티클 2) |
Sprout에서 Sapling, 그리고 Orchard로 이어지는 진화는 대체로 증명이 더 작고, 더 빠르고, 신뢰된 설정에서 벗어나게 되는 이야기입니다. Halo 2 는 Orchard에서 사용되며 세리머니가 전혀 필요 없고, 재귀(recursion) (다른 증명을 검증하는 증명)을 지원하도록 설계되었습니다. 그래서 Orchard는 아티클 2에서 본 Pallas/Vesta 곡선의 사이클을 사용합니다. 각 곡선이 서로 위에 쓰인 증명을 검증하도록 조정되어 있기 때문입니다.
이로써 아티클 0에서 시작된 가장 큰 고리가 닫힙니다. "장막 뒤에서" 일어나는 마법은 바로 zk-SNARK 입니다. 이것은 당신의 거래가 모든 규칙을 부호화한 산술 회로를 만족한다는 것을 증명하면서도, "유효함"이라는 단 하나의 비트 외에는 아무것도 드러내지 않습니다.
영지식 증명은 매우 깊은 분야이고, 우리는 의도적으로 직관 수준에 머물렀습니다. 우리는 건전성의 정확한 확률 경계, 산술 회로의 정확한 형태(R1CS, PLONKish 등), 다항식과 커밋먼트가 어떻게 회로를 짧은 증명으로 바꾸는지, 혹은 Groth16과 Halo 2의 실제 내부 구조를 정의하지 않았습니다. 동굴은 대화형 증명이고, 실제 운영 시스템은 비대화형이며 훨씬 더 정교합니다. 하지만 그 어떤 것도 핵심을 바꾸지는 않습니다. 비밀 증인으로 회로가 만족된다는 것을, 완전하게, 건전하게, 그리고 아무것도 드러내지 않은 채 증명하는 것. 그 기계장치는 그 자체로 또 하나의 시리즈가 될 만한 주제입니다.
| 용어 | 쉬운 뜻 |
|---|---|
| Zero-knowledge proof | 그 외의 아무것도 드러내지 않고 어떤 명제가 참이라고 납득시키는 것 |
| Prover / Verifier | 증명을 만드는 사람 / 그것을 검사하는 사람 |
| Completeness | 참인 명제는 언제나 받아들여진다(정직한 증명자로부터) |
| Soundness | 거짓인 명제는 거부된다(사기꾼은 운이 아니고서는 이길 수 없다) |
| Witness | 그 명제를 참으로 만드는 비밀 입력 |
| Arithmetic circuit | 유한체 위의 덧셈과 곱셈으로 다시 쓴 명제 |
| Non-interactive (Fiat-Shamir) | 실시간 왕복이 필요 없는 일회성 증명 |
| Succinct | 명제 크기와 무관하게 증명이 작고 빠르게 검증된다 |
| zk-SNARK | Zero-knowledge Succinct Non-interactive ARgument of Knowledge |
| Trusted setup / toxic waste | 남은 비밀을 반드시 파기해야 하는 일회성 파라미터 생성 |
증명이 아무것도 드러내지 않는다면, 그것을 검사하는 것이 무슨 의미가 있나요? 수학적 구조가 오직 실제로 유효한 증인만이 통과 가능한 증명을 만들 수 있도록 되어 있기 때문입니다. 검사를 통과했다는 사실 자체가 바로 증거이며, 공개는 필요 없습니다.
누군가 증명을 위조할 수 있나요? 건전성 때문에 이는 사실상 불가능합니다. 유일한 예외는 신뢰된 설정의 toxic waste가 보관된 SNARK인데, 바로 그 때문에 그것을 파기하는 세리머니가 중요합니다.
신뢰된 설정이 깨지면 내 개인 데이터가 유출되나요? 아니요. 그것은 공격자가 새로운 돈을 위조하게 만들 수는 있지만, 금액, 주소, 노트를 드러내지는 않습니다. 프라이버시와 건전성은 서로 별개의 보장입니다.
왜 Zcash는 시간이 지나면서 증명 시스템을 바꾸었나요? 더 작고 더 빠른 증명을 얻기 위해서이고, Halo 2를 통해서는 신뢰된 설정을 완전히 제거하고 재귀도 가능하게 하기 위해서입니다.
동굴에서, 검증자가 증명자가 이미 안으로 들어간 뒤에 출구 쪽을 선택하는 것이 왜 필수적일까요? 미리 알려주면 안 되는 이유는 무엇일까요? (답은 아래에 있습니다.)
검증자가 먼저 어느 쪽으로 나오라고 말해 버리면, 주문을 모르는 허풍쟁이도 처음부터 그쪽 통로로 들어갔다가 그냥 다시 걸어 나오면 됩니다. 문이 전혀 필요하지 않죠. 증명자가 먼저 통로 하나를 선택하도록 한 뒤에 나중에 도전을 주어야만, 허풍쟁이는 운(매 라운드 50 대 50)에 의존하게 됩니다. 바로 그 점이 반복 라운드를 설득력 있게 만듭니다. 이런 "먼저 커밋하고, 그다음 도전을 받는다"는 순서가 정확히 Fiat-Shamir가 보존하는 것입니다. 도전은 증명자가 이미 커밋한 증명의 해시에서 유도되기 때문입니다.
아티클 6 . 실드 프로토콜 전체 흐름: 대미를 장식하는 마지막 글입니다. 노트, 커밋먼트, 노트 커밋먼트 트리, nullifier, 가치 균형, 그리고 영지식 증명까지 모든 조각을 가져와 완전한 Zcash 실드 거래를 조립하며, 아티클 0에서 열어 둔 모든 고리를 하나하나 닫습니다.
이 글은 ZecHub를 위한 Zcash from First Principles 시리즈의 일부입니다. CC BY-SA 4.0 라이선스 적용.