영지식이란
영지식은 진술을 검증할 때 가능한 가장 작은 양의 정보만 사용하는 것으로, 부가적인 데이터 전송을 피할 수 있는 증거를 마련하는 방식이다. 이 기술의 출발점은 1980년대에 나온 ‘대화형 증명 시스템의 지식 복잡성(Knowledge Complexity of Interactive Proof Systems)’이라는 논문이다. 이름에서 짐작할 수 있듯 이 논문은 대화하는 시스템 간에 진술을 입증하는 데 있어 지식이 어떻게 동작하는지를 이해하는 데 초점을 맞췄다.이 논문에 영감을 준 논문이 있는데 바로 1971년 스티븐 쿡이 발표해 컴퓨터 과학에서 복잡성 이론 분야에 불을 지핀 중대한 논문인 '정리 증명 절차의 완전성(The Completeness of Theorem Proving Procedures)'이다. 쿡의 논문이 알고리즘의 복잡성을 명시적으로 살펴보고 경계를 설정하려 시도했다면, 지식 복잡성 논문은 이와 유사하게 증명에서 지식의 상한과 하한을 정하고 지식에 명확한 초점을 뒀다.
영지식과 인증
일반적으로 증명을 통해 인증을 이해하는 것은 불가능하다. 둘 이상의 소프트웨어 시스템이 통신할 때 한 시스템이 어떤 주장을 한다면 다른 시스템에 그 주장을 어떻게 증명해야 할까? 영지식은 이것이 이뤄지는 방법을 살펴보면서 기본적인 접근 방법의 대안으로 지식 유출의 양을 줄여 전체적인 시스템의 보안을 개선하는 방법을 제공한다.예를 들어 기본 접근 방식에서 시스템은 암호에 대한 지식을 갖고 있다고 주장할 수 있다. 이를 다른 시스템에 증명하기 위해 암호가 전송된다. 여기서 영지식 프로토콜은 암호 자체를 전송하지 않고 최소한의 지식으로 다른 시스템을 납득시키는 방법을 사용한다. 이러한 증명은 확률에 근거하는데 높은 확률로 인증의 유효성을 확보한다.
대화형 증명에는 당사자 간의 지속적인 대화가 필수적이다. 증명자(prover)와 검증자(verifier)가 대화를 주고받으며 검증자가 증명자에게 질문한다. 각 올바른 대답은 증명자의 주장에 대한 검증자의 확신 수준을 높인다. 즉, 증명자가 거짓말을 하고 있을 확률이 낮아진다. zk-SNARK 증명에 주목받는 것은, 이 대화 과정이 증명자에서 검증자로 한 번 전송 가능한 안전한 패키지로 캡슐화된다는 것이다. 이후 검증자는 증명 자체와 상호작용할 수 있고 더는 대화가 필요 없으므로 비대화형 증명이라고 한다.
비대화형 증명은 1988년 ‘비대화형 영지식(Non-interactive Zero-Knowledge)’이라는 논문에서 처음 입증됐다. 영지식 증명을 비대화 형식으로 캡슐화하는 것이 현실적으로 가능해진 기점이었다. 이 논문에 이어 2012년에 나온 ‘추출 가능한 충돌 저항에서 간결한 비대화형 지식 주장으로, 그리고 다시 되돌리기(From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge)’ 논문에서 SNARK가 등장했다. 그 이후 현재까지 기본 개념이 점점 더 발전하고 있다.
zk-SNARK 구현하기
SNARK 아이디어를 개념적 사양으로 본다면 최초(거의)의 실질적 구현은 2013년에 제안된 피노키오(Pinocchio) 프로토콜이다. 이 논문은 신뢰할 수 없는 계산 리소스를 사용해 기능의 실행을 확인할 수 있는 공개 검증 가능한 연산 체계를 제시했다. 더 자세한 내용이 궁금하다면 ‘폰 노이만 아키텍처를 위한 간결한 비대화형 영지식(Non-Interactive Zero Knowledge for a Von Neumann Architecture)’을 참고하면 된다.이러한 활동을 보다 보면 zk-SNARK는 뚫을 수 없는 수학적 덤불처럼 보인다. 실제로 디피-헬만과 같은 직관적인 도약을 포함한 전문 지식이 필요하고 시스템을 뒷받침하는 변환을 위해 엄청난 양의 작업을 해야 한다. 많은 영감과 큰 노력을 모두 요구하는 영역이다.
여전히 변화하고 있다는 사실도 zk-SNARK가 더 어렵게 느껴지는 이유다. 지금까지 살펴본 바와 같이 이론 자체가 최근에야 개발됐고 여전히 다듬어지고 있다. 구현은 특히 변화가 많은 영역이다. 기본적인 부분이 추상화된 다음 특정 애플리케이션과 사용 사례에서 쓸 수 있는 라이브러리로 래핑되기 때문이다. 다양한 기존 시스템에 zk-SNARK를 적용할 수 있는지 테스트하면서 새로운 활용 사례가 만들어지고 있다.
이번 글에서는 사용 사례와 이를 지원하는 소프트웨어에 집중한다. 일단 수학의 세계로 너무 깊이 들어가지 않으면서 zk-SNARK가 어떻게 작동하는지 살펴보자.
zk-SNARK 작동 방식
기본적으로 zk-SNARK는 계산이 수행됐음을 검증한다. 이를 위해 원래의 계산, 즉 함수를 취해 이를 매우 구체적인 형식으로 표현한다. 이는 일련의 수학적 변환을 통해 이뤄진다. 최종 형식은 주어진 입력으로 계산이 수행되었음을 입증하는 데 사용할 수 있는 실제 zk-SNARK 형식이다. 참고로 입력은 zk-SNARK에서 목격자라고 한다. 해당 인수로 계산이 수행되었음을 입증하는 데 사용할 수 있기 때문이다.zk-SNARK에서 주목해야 할 것은 2가지다. 첫째, 암호의 소유 증명과 같은 많은 애플리케이션에서 이 방식은 먼저 원하는 주장을 기능적 등가물로 변경해야 한다. 예를 들어 암호의 경우 일반 텍스트 암호를 해싱 알고리즘을 통해 실행할 수 있다. 그러면 해시가 암호를 대상으로 실행됐음이 입증되며, 이는 암호의 소유를 입증하는 것과 같다.
둘째는 검증 가능한 계산의 속성이 간단한 진술 인증 이상의 의미를 가진 새로운 컴퓨팅 모델을 만든다는 것이다. 이 모델은 신뢰할 수 없는 환경에서도 제3자 리소스로 연산을 아웃소싱할 수 있다. 리소스가 암호화된 방식으로 실행을 입증할 수 있기 때문이다. 이런 특성은 곧 블록체인으로 이어진다. 실제 정보를 브로드캐스팅하는 방법으로 거래를 증명하는 대신 블록체인에서 zk-SNARK를 사용해 증명만 브로드캐스팅할 수 있기 때문이다. 대표적으로 MINA 프로토콜이 이 방식으로 작동한다.
이렇게 연산을 아웃소싱하는 사례는 비단 블록체인만이 아니다. 신뢰할 수 있는 서드파티 없이 일종의 컴퓨팅 마켓플레이스를 만드는 것도 가능하다. 현재 다양한 유형의 클라우드 업체가 이 방식을 활용하고 있다.
SNARK가 사용하는 변환은 진술이 함수로 표현된 이후 원래의 계산 > 대수 회로 > 랭크 1 제약 시스템(R1CS) > 이차 산술 프로그램(QAP) > 선형 PCP > 선형 대화형 증명 > zkSNARK로 이어지는 일반적인 패턴에 따른다(비탈릭 부테린의 이차 산술 논문). 참조된 논문은 첫 4개의 변환을 잘 설명한다. 전체 프로세스를 이해하기 쉽게 설명한 글을 보려면 ‘zk-SNARK를 사용하는 이유와 그 원리(Why and How of zk-SNARK)’를 추천한다. 영지식 블로그도 zk-SNARK와 영지식에 관해 전반적으로 파악하는 데 유용하다.
zk-SNARK가 수행하는 핵심 기능은 계산을 다항식으로 변환하는 것이다. 이 형식에서는 다항식 그래프의 점을 테스트해 계산을 증명할 수 있다. 즉, 이 다항식의 해는 다항식 자체가 아니라 증명자가 실제로 증명을 소유하고 있는지 검증하는 데 사용된다. 여러 점을 테스트해 증명의 확률적 신뢰성이 높아진다.
따라서 변환의 첫 번째 부분은 기능을 수학적 형식으로 바꾼 다음(대수 회로 > R1CS) 이를 다항식(QAP)으로 바꾸고 효율적으로 검증이 가능한 형식으로 바꾸고(선형 PCP > 선형 대화형 증명) 최종적으로 전송 가능한 형식, SNARK 자체로 바꾼다. 영지식 증명을 비대화형 형식으로 캡슐화하는 다른 방법도 있겠지만 현재는 이 방법이 일반적이다.
zk-SNARK의 응용
zk-SNARK는 블록체인을 검증 가능한 연산으로 옮길 수 있는 가능성 외에 로그인을 위한 자격 증명을 제공하고, 더 광범위하게 진술을 설정하는 두 가지 측면에서 영지식 스타일의 인증을 지원한다. 예를 들어 사용자가 특정 금액 이상의 은행 계좌를 소유하고 있다고 주장하는 경우가 있다(이때 서드파티로서 은행과의 대화가 필요함).이때 zk-SNARK를 사용하면 일종의 익명 인증이 가능하다. 즉, 사용자는 신원이 아닌 자신이 소유한 사실을 근거로 하여 리소스에 액세스하도록 허용됐음을 입증할 수 있다. 이러한 메커니즘은 인증 활동 수행 시 교환되는 지식의 양을 줄여 보안 시스템의 안전을 높인다.
마지막으로, zk-SNARK를 사용하면 완전한 익명 지불 시스템을 구현할 수 있다. 거래는 가용한 자금 확인 > 이 자금이 에스크로에 있는지 확인 > 상품 배송 확인 > 계약 완료하는 순서로 진행된다. 이 과정에서 양 당사자의 신원은 일절 누설되지 않는다.
editor@itworld.co.kr