Zero-Knowledge Proof (ZKP)

**영지식 증명(Zero-knowledge proof, ZKP)**은 한 당사자(증명자)가 다른 당사자(검증자)에게 어떤 진술이 참이라는 사실을, 그 진술의 참 여부 외에는 어떠한 정보도 노출하지 않고 설득할 수 있게 해주는 암호학적 방법입니다.

ZKP를 통해 당사자들은 기본 데이터를 숨긴 채 비밀 정보의 소유나 계산의 정확성을 증명할 수 있으며, 이는 인증, 디지털 신원, 그리고 blockchain 시스템과 같은 분야에서 개인정보 보호 및 보안에 유용하게 사용됩니다.^[1]​

개요

지식 증명(proof of knowledge)은 증명자가 비밀 키와 같은 특정 정보를 알고 있다는 사실을, 그 정보 자체를 노출하지 않고 검증자에게 확신시키는 암호학적 증명입니다. 증명자는 암호학적 증명을 생성하는 엔티티 또는 프로그램이며, 검증자는 해당 증명을 확인하는 엔티티 또는 프로그램입니다.

영지식 증명(Zero-knowledge proofs, ZKPs)은 진술의 참 여부 외에는 검증자가 아무런 정보도 얻을 수 없다는 추가적인 속성을 가진 지식 증명의 특수한 범주입니다. 이상적인 영지식 프로토콜에서 진술이 참이고 증명자가 프로토콜을 올바르게 따른다면, 검증자는 확신을 얻게 되지만 증명을 구성하는 데 사용된 증거(witness)나 비밀에 대한 유용한 정보는 전혀 얻지 못합니다.^[7]​^[11]​

ZKP는 인증 프로토콜, 디지털 신원 체계, 그리고 프라이빗 트랜잭션 및 확장 가능한 롤업과 같은 블록체인 기반 애플리케이션을 포함하여 프라이버시 보호 검증이 필요한 다양한 시스템에서 사용됩니다.^[14]​^[1]​

역사

영지식 증명(zero-knowledge proofs)의 공식적인 개념은 1985년 샤피 골드와서(Shafi Goldwasser), Silvio Micali, 찰스 래코프(Charles Rackoff)가 발표한 논문 “The Knowledge Complexity of Interactive Proof-Systems”에서 처음 소개되었습니다. 이 논문은 대화형 증명(interactive proofs)을 정의하고, 증명자가 검증자에게 기본 증거(witness)를 공개하지 않고도 어떤 진술이 참임을 설득할 수 있는 방법을 보여주었습니다.^[11] 초기 구조들은 실제 배포하기에는 너무 비효율적이었기 때문에 주로 이론적인 관심 대상에 머물렀습니다.

2010년대에 들어 zk-SNARKs(Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge)와 같이 더 효율적인 비대화형 영지식 시스템이 등장하면서 실질적인 응용이 가능해졌습니다. 프라이버시 중심의 cryptocurrency인 Zcash는 2016년 zk-SNARKs를 대규모로 배포한 최초의 사례 중 하나로 출시되었습니다. Zcash는 이를 통해 온체인에서 완전히 암호화되면서도 네트워크의 합의 규칙에 따라 검증 가능한 보호된 거래(shielded transactions)를 가능하게 했습니다.^{[8] [12]}

이후 연구에서는 신뢰할 수 있는 설정(trusted setup)을 피하고 더 나은 확장성을 목표로 하는 zk-STARKs(Zero-Knowledge Scalable Transparent Arguments of Knowledge)가 도입되었으며, 모네로(Monero)와 같은 코인의 기밀 거래에 사용되는 Bulletproofs와 같은 다른 증명 시스템도 등장했습니다.^{[9] [13]} Ethereum을 포함한 주요 smart contract 플랫폼들은 ZKP 친화적인 암호화 프리미티브에 대한 지원을 채택했습니다. 이는 오프체인 연산을 검증하기 위해 ZKP에 의존하는 zk-rollups, zkEVMs 및 기타 확장성 솔루션의 등장을 가속화했습니다.^{[14] [15]}

최근 연구는 증명 생성 속도, 검증자 효율성 및 결합성 향상에 집중하고 있습니다. 여기에는 여러 증명을 하나로 합칠 수 있는 재귀적 증명 시스템(recursive proof systems)과 범용 프로그램의 올바른 실행을 증명할 수 있는 zk-가상 머신(zkVMs) 등이 포함됩니다.^[15]

작동 원리

높은 수준에서 영지식 증명은 두 가지 역할을 포함합니다. 비밀 정보를 보유하고 있거나 계산을 수행한 증명자(prover)와, 그 비밀이나 계산에 대한 진술이 참이라는 확신을 얻고자 하는 검증자(verifier)입니다. 증명자는 무작위성과 암호학적 커밋먼트(commitments)를 사용하여 자신의 지식을 증명으로 인코딩하고, 이 증명(및 일부 공개 입력값)을 검증자에게 보냅니다. 그러면 검증자는 검증 알고리즘을 실행하여 증명을 수락할지 여부를 확인합니다.^[2]​

대부분의 ZKP 구조는 계산에 대한 진술을 증명하는 관점에서 설명될 수 있습니다. 증명자는 (잠재적으로 숨겨진) 일부 입력값에 대해 프로그램을 올바르게 실행하여 특정 출력값을 얻었음을 보여줍니다. 현대적인 시스템은 계산을 산술 회로(arithmetic circuit)나 제약 시스템(constraint system)으로 인코딩한 다음, 기본 입력값을 공개하지 않고 이러한 제약 조건이 충족되었다는 간결한 증명을 생성합니다. 검증자는 공개 매개변수와 주장된 출력값을 사용하여 증명을 확인하며, 증명이 검증되면 검증자는 해당 진술을 참으로 수락합니다.

영지식 증명은 일반적으로 세 가지 핵심 속성을 충족하도록 설계됩니다. **완전성(Completeness)**은 진술이 참이고 증명자가 프로토콜을 올바르게 따른다면, 정직한 검증자는 이를 확신하게 된다는 것을 의미합니다. **건전성(Soundness)**은 진술이 거짓일 경우, 속임수를 쓰는 증명자가 검증자를 설득할 수 있는 확률이 무시할 수 있을 정도로 작다는 것을 의미합니다. **영지식성(Zero-knowledge)**은 검증자가 진술이 참이라는 사실 외에는 아무것도 알 수 없음을 의미하며, 이는 종종 증명에 사용된 증거(witness)에 접근하지 않고도 검증자의 상호작용 뷰를 시뮬레이션할 수 있어야 한다는 요구 사항으로 공식화됩니다.^[14]​

현대적인 증명 시스템은 효율성과 구성 가능성(composability)에도 중점을 둡니다. zk-SNARK 및 zk-STARK와 같은 Succinct 시스템은 매우 짧은 증명과 빠른 검증을 목표로 하며, 온체인 계산 비용이 비싼 blockchains에서의 사용을 가능하게 합니다. 재귀적 증명(Recursive proof) 기술은 하나의 증명이 다른 증명들의 유효성을 증명할 수 있게 하며, 이는 롤업의 확장성을 높이고 많은 트랜잭션이나 계산을 하나의 간결한 증명으로 통합하는 데 중요합니다.^[7]​^[15]​

유형

영지식 증명에는 상호작용 방식, 효율성 달성 방법, 의존하는 가정에 따라 다음과 같은 몇 가지 주요 유형이 있습니다.

• 대화형 ZKP (Interactive ZKPs): 증명자와 검증자 사이에 일련의 도전(challenge)과 응답(response)이 수반됩니다. 검증자가 무작위성이나 도전을 보내면 증명자가 여러 라운드에 걸쳐 응답하고, 그 후 검증자가 수용 또는 거부 여부를 결정합니다.^[3]​^[4]​
• 비대화형 ZKP (Non-interactive ZKPs): 증명자가 검증자에게 단 한 번의 메시지만 보내면 됩니다. 비대화형 증명은 종종 공통 참조 문자열(common reference strings)이나 공개적 무작위성을 사용하여 구성되며, 상호작용 비용이 많이 드는 blockchain 및 분산 시스템에 편리합니다.^[4]​^[5]​
• Sigma 프로토콜 (Sigma protocols): 이들은 이산 로그 스타일의 문장에 대해 영지식을 제공하는 3단계 대화형 증명(커밋, 도전, 응답)이며, 더 복잡한 프로토콜을 위한 빌딩 blocks 역할을 합니다.^[6]​
• zk-SNARKs: Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge는 매우 짧고 검증 속도가 빠른 비대화형 증명으로, 복잡한 계산에 대한 문장을 증명하는 데 적합합니다. 많은 blockchain 프라이버시 프로토콜과 zk-rollup은 트랜잭션 유효성이나 오프체인 실행을 증명하기 위해 zk-SNARKs를 사용합니다.^[8]​^[7]​
• zk-STARKs: Zero-Knowledge Scalable Transparent Arguments of Knowledge는 확장성과 투명성을 강조하는 비대화형 증명입니다. 이들은 공개적으로 검증 가능한 무작위성에 의존함으로써 신뢰할 수 있는 설정(trusted setup)을 피하며, 비교적 효율적인 검증을 통해 매우 큰 규모의 계산을 지원하도록 설계되었습니다.^[9]​^[7]​

이러한 범주 외에도 현대 시스템은 주류 언어로 작성된 임의의 프로그램의 올바른 실행을 증명할 수 있는 zk-virtual machines (zkVMs)와 같은 범용 증명 프레임워크와, 여러 개의 작은 증명을 하나의 간결한 증명으로 통합할 수 있는 재귀적 증명 시스템을 도입하고 있습니다. 이러한 접근 방식은 확장 가능한 롤업 및 검증 가능한 계산 서비스에서 광범위하게 사용됩니다.^[14]​^[15]​

예시

• Schnorr signature: 사용자가 개인 키 자체를 공개하지 않고도 개인 키를 소유하고 있음을 증명할 수 있는 암호화 서명 방식입니다. 단순함으로 잘 알려진 elliptic curve cryptography를 활용하는 알고리즘인 Schnorr 서명은 역사적으로 Bitcoin’의 기술 로드맵에서 Elliptic Curve Digital Signature Algorithm (ECDSA)의 업그레이드 안으로 제안되었으며, 이후 2021년 11월 Taproot 소프트 fork의 일부로 Bitcoin에 활성화되었습니다. Schnorr는 증명 가능한 보안 특성과 선형성을 갖춘 단순한 방식으로 자주 묘사되며, ECDSA보다 적은 계산량을 요구하므로 cryptocurrency 트랜잭션에 적합합니다.^[10]

• ZK-SNARKs: 복잡한 문장을 효율적으로 증명하기 위해 고급 암호학을 사용하는 비대화형 ZKP의 한 유형입니다. ZK-SNARK라는 약어는 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge의 약자로, 비밀 키와 같은 특정 정보의 소유를 해당 정보를 공개하지 않고 증명자와 검증자 간의 상호작용 없이 증명할 수 있는 증명 구조를 의미합니다. Zcash는 zk-SNARKs를 널리 적용한 최초의 사례 중 하나로, 이를 통해 보호된 트랜잭션이 blockchain 상에서 완전히 암호화되면서도 네트워크의 합의 규칙에 따라 유효한 것으로 검증될 수 있도록 합니다.^[8]​^[12]​
• ZK-STARKs: 다항식 커밋먼트(polynomial commitments)를 기반으로 하며, 많은 zk-SNARK 구조보다 더 나은 확장성과 투명성을 위해 설계된 또 다른 유형의 비대화형 ZKP입니다. Ethereum 및 관련 프로젝트들은 프라이빗 트랜잭션, 검증 가능한 오프체인 연산, 그리고 네트워크상의 확장성 솔루션을 가능하게 하기 위해 zk-SNARKs 및 zk-STARKs와 같은 ZKP 프로토콜을 지원합니다.^[9]​^[14]​

• Bulletproofs: Monero는 자사의 Bulletproofs ZKP 시스템 코드를 Bulletproof+ 솔루션으로 업그레이드했습니다. Bulletproofs는 비대화형 ZKP로, 다른 용도 외에도 실제 금액을 공개하지 않고 결제 금액이 유효한 범위 내에 있음을 증명할 수 있습니다. 이는 당사자 및 당사자가 승인한 사람을 제외하고는 누구도 각 트랜잭션의 송신자, 수신자 또는 금액을 추적할 수 없도록 보장하는 데 도움이 됩니다.^[13]

Use Cases and Applications

영지식 증명(ZKP)은 기본 데이터를 공개하지 않고 사실이나 계산 결과를 증명하는 것이 유용한 모든 분야에서 광범위하게 응용됩니다. 개인정보 보호 인증에서 사용자는 비밀번호를 보내지 않고도 비밀번호를 알고 있음을 증명하거나, 서비스에 자격 증명을 전송하지 않고도 자격 증명 소유를 증명할 수 있어 자격 증명 도난 위험을 줄일 수 있습니다. 익명 자격 증명 시스템에서 사용자는 발급자로부터 검증 가능한 자격 증명을 얻은 후, 나중에 자신의 전체 신원을 밝히지 않고도 해당 자격 증명의 속성(예: 연령 또는 회원 여부)을 증명할 수 있습니다.^[1]​

보안 투표 체계에서 ZKP는 투표자가 자신이 어떻게 투표했는지 밝히지 않고도 자신의 투표가 올바르게 형성되고 집계되었음을 입증하는 데 도움을 줄 수 있습니다. 유사한 기술이 개인정보 보호 설문조사 및 경매에도 적용되어, 참가자가 개별 입찰가나 답변을 노출하지 않고도 올바른 집계나 낙찰가 결정에 대한 확신을 가질 수 있게 합니다.^[1]​

blockchain 시스템에서 ZKP는 프라이버시 코인과 확장성 솔루션 모두를 뒷받침합니다. Zcash 및 Monero와 같은 프라이버시 중심 cryptocurrencies는 ZKP를 사용하여 거래 세부 정보(금액 및 주소)를 숨기면서도 코인이 생성되거나 파괴되지 않았음을 공개적으로 검증할 수 있게 합니다. Ethereum과 같은 smart contract 플랫폼에서 zk-rollups 및 zkEVMs는 많은 거래를 오프체인에서 일괄 처리하고, 모든 상태 전환이 올바르게 계산되었다는 간결한 증명을 생성하여 이를 메인 체인에 게시함으로써 보안을 유지하면서 확장성을 개선합니다. validium 및 volition과 같은 관련 설계는 데이터 가용성, 비용 및 프라이버시 사이의 균형을 맞추면서 ZKP를 사용하여 상태 업데이트의 유효성을 증명하고 데이터를 오프체인 또는 선택적으로 온체인에 저장합니다.^[14]​^[15]​

ZKP는 디지털 신원 및 규제 준수 시나리오에서도 사용됩니다. 사용자는 데이터 노출을 최소화하려는 고객 알기 제도(KYC) 및 자금 세탁 방지(AML) 체제와 관련하여, 전체 신원 서류를 공개하지 않고 국적, 연령 또는 인증 상태와 같은 속성을 증명할 수 있습니다. Central bank digital currency (CBDC) 설계 및 개인정보 보호 결제 시스템은 규제 기관에 필요한 가시성을 제공하는 동시에 일상적인 거래 세부 정보가 광범위하게 공개되지 않도록 보호하기 위해 ZKP를 탐색하고 있습니다.^[1]​

금융을 넘어 ZKP는 검증 가능한 연산 및 데이터 무결성 사용 사례를 지원합니다. 클라우드 컴퓨팅에서 서버는 클라이언트가 계산을 다시 실행할 필요 없이 클라이언트의 계산(예: 머신러닝 모델 평가)을 올바르게 수행했음을 증명할 수 있습니다. 데이터 공유 및 AI 파이프라인에서 ZKP는 민감하거나 독점적인 정보에 중요한 원시 데이터를 공개하지 않고도 데이터 세트 또는 모델 학습의 속성(예: 특정 제약 조건 또는 출처 요구 사항 준수)을 인증할 수 있습니다. 이러한 패턴은 공급망 추적, 의료 연구 및 기업이 기밀 데이터에 대한 주장을 검증해야 하는 다른 도메인으로 확장됩니다.^[14]​

Challenges

ZKPs는 상당한 이점을 제공하지만, 채택 및 설계 선택에 영향을 미치는 몇 가지 과제에도 직면해 있습니다. 많은 구조가 특히 증명자 측에서 **계산 집약적(computationally intensive)**이며, 이는 복잡한 문장이나 대규모 애플리케이션에 대해 증명을 생성하는 비용을 비싸게 하거나 속도를 느리게 만들 수 있습니다. 현대적인 시스템과 하드웨어 가속이 성능을 향상시켰음에도 불구하고, 증명 시간을 단축하는 것은 특히 blockchain 롤업 및 검증 가능한 계산 서비스 분야에서 여전히 활발한 연구 영역으로 남아 있습니다.^[15]​

또 다른 과제는 **표준화 및 상호 운용성(standardization and interoperability)**입니다. ZKPs를 위한 단일 표준은 없으며, 서로 다른 프로토콜(예: zk-SNARKs, zk-STARKs, Bulletproofs 및 zkVM 기반 시스템)은 신뢰 가정, 성능 및 증명 크기 측면에서 서로 다른 절충안을 가집니다. 이러한 다양성은 플랫폼 간의 결합성을 저해하고 공통 도구 및 라이브러리의 개발을 늦출 수 있습니다.^[6]​

보안 및 신뢰 가정(Security and trust assumptions) 또한 중요한 고려 사항입니다. 일부 구조는 공개 매개변수를 생성하기 위해 신뢰할 수 있는 설정(trusted setup) 세레모니에 의존합니다. 만약 이 과정이 손상되면 시스템의 건전성(soundness)이 위험에 처할 수 있습니다. 또한 ZKPs는 복잡하고 오류를 감지하기 어렵기 때문에, 구현 시 미묘한 암호학적 및 프로토콜 수준의 취약점을 처리해야 합니다. 마지막으로, ZKP 시스템은 개발자와 사용자가 이해하고 통합하기 어려울 수 있으며, 이는 도구 및 문서화 노력을 통해 줄이고자 하는 사용성 및 교육(usability and education) 장벽을 만듭니다.^[14]​