Welcome to ZKP
안녕하세요! 최근 암호학 및 블록체인 업계에서 떠오르는 신기술, 영지식 증명(ZKP)에 관심을 가지신 독자분들을 환영합니다.
ZKP는 최근 이더리움의 zk-Rollup이라는 레이어2 솔루션으로 각광받고 있으며, 다양한 분야에서서 개인정보 보호 및 확장성을 담당할 기술로서 자리잡고 있습니다. 이러한 기술의 뒤에는 굉장히 정교한 수학 및 암호학적 배경지식이 숨어있습니다. 앞으로의 블로그 글에서 이들을 단계별로 천천히 파헤쳐보도록 하겠습니다.
'검증 가능한 컴퓨팅'과 '영지식 증명'의 세계
여러분의 스마트폰이 저 멀리 있는 슈퍼컴퓨터에게 복잡한 계산을 시켰다고 상상해 보세요. 슈퍼컴퓨터가 보내온 결과값이 정말 내가 부탁한 것이 맞는지 어떻게 신뢰할 수 있을까요? 심지어 그 슈퍼컴퓨터가 악의적인 의도를 가지고 결과를 조작했다면요?
이처럼 '계산 결과를 믿을 수 있는가'의 문제를 해결하기 위해 탄생한 기술이 바로 검증 가능한 컴퓨팅(Verifiable Computation, VC)입니다. 오늘은 VC의 개념부터 시작해, 그 가장 강력한 형태인 영지식 증명(ZKP)까지 알아보겠습니다.
1. 검증 가능한 컴퓨팅(VC)이란?
검증 가능한 컴퓨팅(VC)은 한마디로, 계산을 수행한 쪽(증명자, Prover)이 그 계산을 요청한 쪽(검증자, Verifier)에게 '내가 이 계산을 정확하게 수행했음'을 암호학적으로 보장하는 기술입니다.
강력한 슈퍼컴퓨터가 '증명자'가 되고, 우리의 스마트폰이 '검증자'가 되는 셈이죠. VC를 이용하면 검증자는 증명자가 보낸 계산 결과가 올바르다는 것을 확신할 수 있습니다. 서버의 계산을 맹목적으로 믿어야 했던 기존의 방식과 달리, 사용자들이 그것을 직접 검증할 수 있게되는 것입니다!
이 기술은 1980년대에 등장한 상호작용 증명(Interactive Proofs, IPs)이라는 개념에서 출발했습니다. 이는 우리가 알던 '증명'의 개념을 크게 확장시켰습니다. 둘을 비교하며 더 자세히 알아보겠습니다.
1-1. 수학적 증명 (전통적)
마치 수학 문제를 푸는 것처럼, 모든 단계가 명확해서 처음부터 끝까지 순서대로 따라가며 맞는지 확인하는 정적인 방식입니다. 이러한 증명 방식이 CS에서 활용되려면, 올바른 증명은 받아들이고 잘못된 증명은 거절하는 증명 시스템(proof system)이라는 체계가 필요합니다. 이때 증명 시스템은 아래 두 가지 조건을 모두 만족해야 합니다.
완전성(completeness): 모든 참인 주장은 올바른 증명을 가져야 합니다.
건전성(soundness): 모든 거짓인 주장은 올바른 증명을 가져서는 안됩니다.
(슬프게도 괴델의 불완전성 정리에 의해 우리 자연수 공리계는 불완전합니다; 즉 참이지만 증명 불가능한 명제가 존재합니다. 저희는 앞으로 살펴볼 증명시스템들에 대하여 완전성과 건전성을 보임으로써 안전성을 분석할 것입니다.)
1-2. 상호작용 증명 (IP)
증명자와 검증자가 서로 질문과 답변을 주고받는 '상호작용'을 통해 증명을 검증하는 방식입니다. 이 과정에서 아주 작은 오류 확률을 허용하는 대신, 훨씬 더 효율적이고 강력한 증명이 가능해졌습니다.
예를 들어, 클라우드 서비스에 데이터 처리를 맡겼을 때 그 계산 결과를 검증하는 상황을 가정해보겠습니다. 대화형 증명(Interactive Proofs, IPs)을 사용하면, 시스템의 사용자인 '검증자(verifier)'는 클라우드와 같은 '증명자(prover)'가 계산을 올바르게 수행했는지 확인하기 위해 일련의 예측 불가능한 질문과 답변을 주고받는 '심문(interrogate)' 과정을 거칩니다.
이 상호작용을 통해 정직한 증명자는 (높은 확률로) 검증을 통과하고(완전성, Completeness), 거짓된 결과를 제시하는 증명자는 높은 확률로 발각되어 검증에 실패하게 됩니다(건전성, Soundness).
또한 상호작용 증명은 한번 작성되면 누구나 복사해서 전달할 수 있는 '정적 증명'과는 다른 핵심적인 특징을 가지는데요, 대화형 증명은 제3자가 대화 기록만으로는 검증의 무결성을 신뢰할 수 없기 때문에 전달 불가능(non-transferrable)하며, 기존 증명이 도용당하거나 재사용되는 것을 방지할 수 있습니다.
1-3. 다중 증명자 상호작용 증명(MIP)과 확률적 검증 가능 증명(PCP)
이어서 이러한 증명 시스템들을 더 효율적으로 발전시킨 다양한 증명 시스템들을 살펴보겠습니다. 대표적인 예가 바로 다중 증명자 상호작용 증명(MIP, Multi-Prover Interactive Proofs)과 확률적 검증 가능 증명(PCP, Probabilistically Checkable Proofs)입니다.
MIP는 IP의 일종이나, 증명자가 다수라는 차이점이 있습니다. 이는 마치 경찰(verifier)이 여러명의 용의자(prover)를 서로 다른 방에 가두고 심문하는 상황에 비유할 수 있습니다. 증명자들이 서로 소통할 수 없는 상황에서 검증자의 질문에 일관된 답변을 내놓는다면, 이들의 주장은 더 높은 신뢰를 얻게 됩니다.
PCP는 정적인 증명 방식이나, 검증자(verifier)가 증명 전체를 모두 확인하는 것이 아니라 일부분만 확률적으로 뽑아 검증한다는 것이 차이점입니다. 바쁜 학술지 심사위원이 논문의 모든 내용을 읽지 않고, 몇 군데만 무작위로 뽑아 읽고도 증명 전체의 타당성을 높은 확률로 확신하는 개념과 같습니다.
하지만 이 두 가지 개념은 그 자체만으로는 현실 세계, 특히 암호학 분야에 적용하기 어렵다는 명확한 한계를 가집니다. MIP는 증명자들이 서로 절대 소통할 수 없다는 비현실적인 가정을 필요로 합니다. 실제로는 증명자가 한 명이거나, 여러 명이라도 이들의 소통을 막을 방법이 없기 때문이죠. PCP 역시 검증자는 증명의 일부만 읽어 편리하지만, 증명자는 여전히 거대한 크기의 증명 전체를 검증자에게 전송해야 합니다. 데이터 전송 비용이 큰 실제 환경에서는 배보다 배꼽이 더 큰 셈입니다.
이러한 한계는 암호학 기술과 결합될 때 비로소 극복할 수 있습니다. MIP와 PCP의 아이디어를 뒤에서 배울 'polynomial commitment scheme'과 같은 암호학적 도구와 결합하면, 증명자가 전체 데이터를 보내지 않고도 자신의 주장을 간결하고 효율적으로 증명할 수 있는 실용적인 '논증 시스템(argument system)'으로 발전시킬 수 있습니다. 이는 결국 저희가 주목할 영지식 증명(ZKP)의 기반이 됩니다.
2. 영지식 증명(ZKP)의 등장
그런데 만약 증명해야 할 계산 내용이나 데이터가 비밀이라면 어떨까요?
예를 들어, "나의 수입은 세금 공제 기준을 만족합니다"라는 계산을 정부 시스템에 증명하고 싶지만, 내 정확한 수입액은 공개하고 싶지 않은 상황처럼 말이죠.
이때 VC 기술에 영지식(Zero-Knowledge)이라는 특별한 속성이 추가됩니다. 이것이 바로 우리가 요즘 자주 듣는 영지식 증명(Zero-Knowledge Proof, ZKP)의 정체입니다.
영지식 증명은 "계산이 올바르게 수행되었다는 사실 외에는, 그 계산에 사용된 데이터나 과정에 대한 어떠한 정보도 노출하지 않고 증명하는 기술"입니다. 결과의 정당성만 보여줄 뿐, 그 내용은 철저히 비밀로 유지되는 것이죠.
핵심 아이디어: 비밀번호 인증 예시
영지식 증명의 강력함을 가장 잘 보여주는 예시 중 하나로 비밀번호 인증이 있습니다.
앨리스(Alice)가 x라는 비밀번호를 정하고, 이 비밀번호를 해시 함수 h를 통해 변환한 값 z = h(x)를 공개했다고 가정해 봅시다. 해시 함수는 x로 z를 계산하긴 쉽지만, z를 보고 원래의 x를 알아내는 것은 거의 불가능합니다.
어느 날 앨리스는 밥(Bob)에게 자신이 진짜 앨리스임을 증명해야 합니다.
나쁜 방법: 앨리스가 밥에게 비밀번호
x를 직접 보내줍니다. 밥은h(x)가z와 일치하는지 확인하면 되지만, 이제 밥도 앨리스의 비밀을 알게 되어 이후로 언제든 그녀를 사칭할 수 있습니다.좋은 방법 (영지식 증명): 앨리스는 영지식 증명을 사용해 "나는
h(x') = z를 만족하는x'를 알고 있다"는 사실을 비밀번호x자체는 보여주지 않고 밥에게 증명합니다. 밥은 앨리스가 비밀번호를 알고 있다는 사실은 확신할 수 있지만, 그 비밀번호가 무엇인지는 전혀 알 수 없습니다.
(이는 ZK 친화적으로 설계된 해시함수 Poseidon Hash를 사용하면 가능합니다.)
한 걸음 더: zk-SNARKs를 만나다
zk-SNARKs (Zero-Knowledge Succinct Non-interactive Argument of Knowledge)
최근 영지식 증명이 각광받는 이유는 zk-SNARKs라는 실용적인 기술 덕분입니다. zk-SNARKs를 사용하면 영지식 증명을 훨씬 더 빠르고, 작고, 편리하게 구현할 수 있습니다. zk-SNARKs의 특징들은 이름 안에 모두 포함되어 있습니다.
Zero-Knowledge (영지식): 비밀 정보가 전혀 노출되지 않습니다.
Succinct (간결성): 증명의 크기가 매우 작고 검증도 빠릅니다.
Non-interactive (비상호작용성): 증명자와 검증자가 여러 번 대화할 필요 없이, 증명자가 던진 증명 하나로 끝납니다.
Argument of Knowledge (지식 증명): 증명자가 '답을 진짜로 알고 있다'는 사실까지 보장합니다.
이와 같은 zk-SNARK 기술이 최근 핫한 zkEVM, Tornado Cash, Mina Protocol 등 신기술의 지평을 열어주었습니다.
마치며
과거에는 이론에 머물렀던 검증 가능한 컴퓨팅과 영지식 증명은 이제 zk-SNARKs와 같은 기술의 등장과 발전으로 우리 삶에 적용될 준비를 마쳤습니다. 프라이버시를 지키면서 데이터의 신뢰도를 높이는 이 혁신적인 기술을, 앞으로 하나하나 알아가봅시다.
Last updated