ArkStream Capital: 제로지식 증명 40년 기술 발전의 이정표
글쓴이: @renkingeth
요약
제로나우리지 프루프(ZKP)는 분산원장 기술 이후 가장 중요한 과학기술 혁신 중 하나로 블록체인 분야에서 널리 여겨지며, 벤처 캐피탈의 주요 투자 대상이 되고 있다. 본고에서는 제로나우리지 프루프 기술에 대한 약 40년간의 문헌과 최신 연구를 체계적으로 종합 검토한다.
먼저 제로나우리지 프루프의 기본 개념과 역사적 배경을 소개한다. 그 다음 회로 기반 제로나우리지 프루프 기술에 초점을 맞추어 zkSNARK, Ben-Sasson, Pinocchio, Bulletproofs, Ligero 등의 모델 설계와 응용 및 최적화 방법을 분석한다. 컴퓨팅 환경 분야에서는 ZKVM과 ZKEVM을 소개하고, 이들이 트랜잭션 처리 능력 향상, 개인정보 보호 및 검증 효율성 증대에 어떻게 기여하는지를 탐구한다. 또한 본고는 Layer 2 확장 솔루션으로서 제로나우리지 롤업(ZK Rollup)의 작동 메커니즘과 최적화 방안, 그리고 하드웨어 가속, 하이브리드 솔루션, 전용 ZK EVM의 최신 진전도 다룬다.
마지막으로 본고는 ZKCoprocessor, ZKML, ZKThreads, ZK Sharding, ZK StateChannels 등 새로운 개념들을 전망하며, 이들이 블록체인의 확장성, 상호운용성, 개인정보 보호 측면에서 지닌 가능성을 논의한다.
이러한 최신 기술과 발전 동향을 분석함으로써, 본고는 제로나우리지 프루프 기술의 이해와 적용에 있어 포괄적인 관점을 제공하며, 블록체인 시스템의 효율성과 보안성을 크게 향상시킬 수 있는 잠재력을 보여주고, 미래의 투자 결정에 중요한 참고 자료를 제공한다.
서론
현재 인터넷은 Web3 시대로 접어들고 있으며, 블록체인 애플리케이션(DApps)의 개발이 급속히 진행되고 있고 거의 매일 새로운 앱이 등장하고 있다. 최근 몇 년간 블록체인 플랫폼은 매일 수백만 명의 사용자 활동을 수십억 건의 거래로 처리해왔다. 이러한 거래가 생성하는 엄청난 양의 데이터에는 일반적으로 사용자 신원, 거래 금액, 계정 주소, 계정 잔액 등 민감한 개인정보가 포함된다. 블록체인의 개방성과 투명성 특성상 저장된 데이터는 누구에게나 공개되므로 여러 가지 보안 및 개인정보 문제를 야기한다.
현재 이러한 문제를 해결하기 위한 몇 가지 암호 기술이 존재하는데, 여기에는 동형암호, 링 서명, 안전한 다자간 계산(Secure Multi-Party Computation), 제로나우리지 프루프가 포함된다. 동형암호는 암호문을 복호화하지 않고 연산을 수행할 수 있어 계정 잔액과 거래 금액의 보안을 보호하는 데 도움이 되지만, 계정 주소 보안은 보호할 수 없다. 링 서명은 서명자의 신원을 숨길 수 있는 특수한 디지털 서명 형태로 계정 주소 보안을 보호할 수 있지만, 계정 잔액과 거래 금액 보호에는 무능하다. 안전한 다자간 계산은 여러 참여자 사이에서 계산 작업을 나누면서도 어느 참여자도 다른 참여자의 데이터를 알 수 없도록 해 계정 잔액과 거래 금액의 보안을 효과적으로 보호하지만, 역시 계정 주소 보안은 보호하지 못한다. 게다가 동형암호, 링 서명, 안전한 다자간 계산은 거래 금액, 계정 주소, 계정 잔액을 노출하지 않으면서도 블록체인 환경에서 증명자가 충분한 거래 금액을 가지고 있음을 검증하는 데는 적합하지 않다(Sun et al., 2021).
제로나우리지 프루프는 이러한 문제를 더욱 포괄적으로 해결하는 방법이다. 이 검증 프로토콜은 어떤 명제의 정확성을 중간 데이터를 전혀 공개하지 않고도 검증할 수 있게 한다(Goldwasser, Micali & Rackoff, 1985). 이 프로토콜은 복잡한 공개키 구조를 필요로 하지 않으며, 반복적으로 실행하더라도 악의적인 사용자가 추가 유용 정보를 획득할 기회를 제공하지 않는다(Goldreich, 2004). ZKP를 통해 검증자는 어떤 개인 거래 데이터도 노출되지 않은 상태에서 증명자가 충분한 거래 금액을 가지고 있는지를 검증할 수 있다. 검증 과정은 증명자가 주장하는 거래 금액을 포함한 증명을 생성하여 이를 검증자에게 전달하고, 검증자가 사전 정의된 계산을 수행하여 최종 결과를 산출함으로써 증명자의 주장을 수용할지 여부를 판단하는 것이다. 증명자의 주장이 수용되면, 이는 그가 충분한 거래 금액을 보유하고 있음을 의미한다. 위의 검증 절차는 위조 없이 블록체인에 기록될 수 있다(Feige, Fiat & Shamir, 1986).
ZKP의 이러한 특성은 블록체인 거래 및 암호화폐 응용에서 핵심적인 역할을 하며, 특히 개인정보 보호와 네트워크 확장성 측면에서 학계 연구의 중심이 되었으며, 비트코인의 성공적인 실현 이후 가장 중요한 기술 혁신 중 하나로 널리 여겨진다(Konstantopoulos, 2022). 동시에 산업 응용과 벤처 캐피탈의 주요 투자 분야이기도 하다.
이러한 이유로 ZkSync, StarkNet, Mina, Filecoin, Aleo 등 다양한 ZKP 기반 네트워크 프로젝트가 차례로 등장했다. 이러한 프로젝트들의 발전과 함께 ZKP 알고리즘 혁신도 계속해서 나타나고 있으며, 거의 매주 새로운 알고리즘이 발표되고 있다고 보고된다(Lavery, 2024; AdaPulse, 2024). 또한 ZKP 기술 관련 하드웨어 개발도 급속히 진행되고 있는데, ZKP 최적화 칩을 포함한다. 예를 들어 Ingonyama, Irreducible, Cysic 등의 프로젝트는 이미 대규모 자금 조달을 완료했으며, 이러한 발전은 ZKP 기술의 빠른 진보를 보여줄 뿐 아니라 GPU, FPGA, ASIC 등 범용 하드웨어에서 전용 하드웨어로의 전환을 반영한다(Ingonyama, 2023; Burger, 2022).
이러한 발전은 제로나우리지 프루프 기술이 단순히 암호학 분야의 중요한 돌파구일 뿐 아니라, 개인정보 보호 및 처리 능력을 향상시키는 더 광범위한 블록체인 기술 응용을 실현하는 핵심 추진력임을 보여준다(Zhou et al., 2022).
따라서 우리는 미래의 투자 결정을 보다 잘 지원하기 위해 제로나우리지 프루프(ZKP)에 관한 지식을 체계적으로 정리하기로 결정했다. 이를 위해 ZKP 관련 핵심 학술 논문들을 종합적으로 검토했다(관련성과 인용 횟수에 따라 정렬); 또한 해당 분야 선도 프로젝트의 자료와 백서를 상세히 분석했다(자금 조달 규모에 따라 정렬). 이러한 포괄적인 자료 수집과 분석이 본고 작성의 견고한 기반이 되었다.
일, 제로나우리지 프루프 기초 지식
1. 개요
1985년 Goldwasser, Micali, Rackoff 세 학자는 논문 'The Knowledge Complexity of Interactive Proof-Systems'에서 처음으로 제로나우리지 프루프(Zero-Knowledge Proof, ZKP)와 대화형 제로나우리지(Interactive Zero-Knowledge, IZK)를 제안했다. 이 논문은 제로나우리지 프루프의 기초가 되는 작품으로, 후속 학계 연구에 영향을 미친 많은 개념을 정의했다. 예를 들어 '지식'의 정의는 「불가능한 계산(unfeasible computation)의 출력」이며, 즉 지식은 출력이어야 하며 불가능한 계산이어야 하고, 간단한 함수가 아닌 복잡한 함수여야 함을 의미한다. 불가능한 계산은 일반적으로 NP 문제로 이해할 수 있는데, 이는 다항 시간 내에 해의 정확성을 검증할 수 있는 문제를 말한다. 다항 시간이란 알고리즘의 실행 시간이 입력 크기의 다항식 함수로 표현될 수 있음을 의미한다. 이것은 컴퓨터 과학에서 알고리즘 효율성과 실현 가능성 평가의 중요한 기준이다. NP 문제는 해를 구하는 과정이 복잡하기 때문에 불가능한 계산으로 간주되지만, 검증 과정은 비교적 간단하므로 제로나우리지 프루프 검증에 매우 적합하다(Goldwasser, Micali & Rackoff, 1985).
NP 문제의 고전적인 예로 여행자 문제(TSP)가 있다. 여기서 일련의 도시를 방문하고 출발지로 돌아오는 최단 경로를 찾아야 한다. 최단 경로를 찾는 것은 어려울 수 있지만, 주어진 경로가 최단인지 검증하는 것은 비교적 쉽다. 왜냐하면 특정 경로의 총 거리를 다항 시간 내에 검증할 수 있기 때문이다.
Goldwasser 등은 논문에서 '지식 복잡도(knowledge complexity)'라는 개념을 도입하여 대화형 증명 시스템에서 증명자가 검증자에게 누설하는 지식량을 정량화했다. 또한 대화형 증명 시스템(Interactive Proof Systems, IPS)을 제안했는데, 여기서 증명자(Prover)와 검증자(Verifier)는 다중 라운드의 상호작용을 통해 어떤 진술의 진실성을 증명한다(Goldwasser, Micali & Rackoff, 1985).
이상에서 Goldwasser 등이 요약한 제로나우리지 프루프의 정의는 검증자가 검증 과정에서 진술의 참값 외에 어떠한 추가 정보도 얻지 못하는 특수한 대화형 증명이며, 다음과 같은 세 가지 기본 특성을 제시한다:
-
완전성(completeness): 주장이 사실이라면 정직한 증명자는 정직한 검증자를 납득시킬 수 있다;
-
건전성(soundness): 증명자가 주장 내용을 모를 경우, 검증자를 속일 확률은 극미하다;
-
제로나우리지성(zero-knowledge): 증명 과정이 끝난 후 검증자는 '증명자가 이 지식을 가지고 있다'는 정보만 얻을 수 있으며, 어떠한 추가 내용도 얻을 수 없다(Goldwasser, Micali & Rackoff, 1985).
2. 제로나우리지 프루프 예시
제로나우리지 프루프及其 속성을 더 잘 이해하기 위해, 아래는 증명자가 특정 비밀 정보를 가지고 있는지 여부를 검증하는 예시를 들며, 이 예시는 설정, 도전, 응답의 세 단계로 나뉜다.
첫 번째 단계: 설정(Setup)
이 단계에서 증명자의 목표는 비밀 숫자 s를 알고 있다는 것을 증명하는 증거를 만들되, s를 직접 보여주지는 않는 것이다. 비밀 숫자를 설정한다;
두 개의 큰 소수 p와 q를 선택하고, 그 곱을 계산한다. 소수 p와 q를 설정하고, 계산하여 얻은 값을 n = p*q로 한다;
계산하여 v = s^2 mod n을 구한다. 여기서 v는 증명의 일부로서 검증자에게 전송되지만, s를 추론하거나 모든 관찰자가 s를 추론하는 것을 충분히 어렵게 만든다;
임의의 정수 r을 선택하고, x = r^2 mod n을 계산하여 검증자에게 전송한다. 이 값 x는 후속 검증 과정에 사용되지만, 마찬가지로 s를 노출하지 않는다. 임의의 정수 r을 설정하고, 계산하여 얻은 x를 구한다.
두 번째 단계: 도전(Challenge)
검증자는 임의로 비트 a(0 또는 1)를 선택하여 증명자에게 전송한다. 이 '도전'은 증명자가 다음에 취해야 할 단계를 결정한다.
세 번째 단계: 응답(Response)
검증자가 보내온 a 값에 따라 증명자가 응답한다:
만약 a=0이면, 증명자는 g=r을 보낸다(r은 이전에 임의로 선택한 수).
만약 a=1이면, 증명자는 g=(r*s) mod n을 계산하여 보낸다. 검증자가 보내는 임의 비트 a에 따라, 증명자는 g을 계산한다;
마지막으로 검증자는 받은 g를 이용하여 g^2 mod n이 x*v^a mod n과 같은지 검증한다. 만약 등식이 성립하면 검증자는 이 증명을 수용한다. a=0일 때, 검증자는 g^2 mod n을 계산하고 우변을 x로 검증한다; a=1일 때, 검증자는 g^2 mod n을 계산하고 우변을 x*v mod n으로 검증한다.
여기서 우리는 검증자가 계산하여 얻은 결과가 증명자가 검증 과정을 성공적으로 통과했지만 비밀 숫자 s를 노출하지 않았음을 보여준다. 여기서 a는 0 또는 1만 가능하므로 두 가지 가능성밖에 없으며, 증명자가 운에 의존하여 검증을 통과할 확률은 (a=0일 때) 1/2이다. 그러나 검증자가 이후 다시 증명자에게 도전하고, 증명자가 관련 숫자를 계속 바꿔 검증자에게 제출하면서 항상 성공적으로 검증을 통과한다면, 증명자가 운에 의존하여 검증을 통과할 확률은 (무한히 0에 가까워짐) 0에 수렴하게 되며, 증명자가 실제로 비밀 숫자 s를 알고 있다는 결론이 입증된다. 이 예시는 제로나우리지 프루프 시스템의 완전성, 건전성, 제로나우리지성을 증명한다(Fiat & Shamir, 1986).
이, 비대화형 제로나우리지 프루프
1. 배경
제로나우리지 프루프(ZKP)는 전통적인 개념에서 대화형이고 온라인 프로토콜 형식을 따른다. 예를 들어 Sigma 프로토콜은 일반적으로 인증을 완료하기 위해 3~5라운드의 상호작용을 필요로 한다(Fiat & Shamir, 1986). 그러나 즉시 거래나 투표와 같은 시나리오에서는 종종 다중 라운드 상호작용의 기회가 없으며, 특히 블록체인 기술 응용에서는 오프라인 검증 기능이 중요하다(Sun 등, 2021).
2. NIZK의 제안
1988년 Blum, Feldman, Micali는 비대화형 제로나우리지(NIZK) 프루프 개념을 처음 제안하며, 증명자(Prover)와 검증자(Verifier)가 다중 라운드의 상호작용 없이도 인증 과정을 완료할 수 있음을 증명했다. 이 돌파구는 즉시 거래, 투표 및 블록체인 응용의 실현을 가능하게 했다(Blum, Feldman & Micali, 1988).
그들은 비대화형 제로나우리지 프루프(NIZK)를 세 단계로 나눌 수 있다고 제안했다:
-
설정
-
계산
-
검증
설정 단계에서는 계산 함수를 사용하여 보안 파라미터를 공통 지식(CRS)에 인코딩된 형태로 변환한다. 이는 증명을 생성하고 올바른 파라미터와 알고리즘을 사용하여 검증하는 방식이다.
계산 단계에서는 계산 함수, 입력 및 증명 키를 사용하여 계산 결과와 증명을 출력한다.
검증 단계에서는 검증 키를 통해 증명의 유효성을 검증한다.
그들이 제안한 공통 참조 문자열(CRS) 모델은 모든 참여자가 공유하는 문자열을 기반으로 NP 문제에 대한 비대화형 제로나우리지 프루프를 실현한다. 이 모델의 작동은 CRS의 신뢰 가능한 생성에 의존하며, 모든 참여자는 동일한 문자열에 접근할 수 있어야 한다. 오직 CRS가 올바르고 안전하게 생성될 때에만 이 모델에 따라 구현된 솔루션이 보안성을 보장할 수 있다. 다수의 참여자에게 있어 CRS 생성 과정은 복잡하고 시간이 오래 걸릴 수 있으므로, 이러한 솔루션은 일반적으로 조작이 간편하고 증명 크기가 작지만 설정 과정이颇具 도전적이다(Blum, Feldman & Micali, 1988).
이후 NIZK 기술은 급속히 발전하였으며, 대화형 제로나우리지 프루프를 비대화형으로 전환하는 다양한 방법이 등장했다. 이러한 방법들은 시스템 구성이나 기본 암호 모델의 가정에서 서로 다르다.
3. Fiat-Shamir 변환
Fiat-Shamir 변환은 또 다른 이름으로 Fiat-Shamir Heuristic(휴리스틱) 또는 Fiat-Shamir Paradigm(패러다임)이라고도 하며, 1986년 Fiat와 Shamir가 제안한 대화형 제로나우리지 프루프를 비대화형으로 전환하는 방법이다. 이 방법은 해시 함수를 도입하여 상호작용 횟수를 줄이고, 보안 가정에 의존하여 증명의 진실성과 위조의 어려움을 보장한다. Fiat-Shamir 변환은 공개 암호 해시 함수를 사용하여 부분적인 무작위성과 상호작용성을 대체하며, 그 출력은 어느 정도 CRS로 간주될 수 있다. 이 프로토콜은 무작위 예언자 모델에서 안전하다고 여겨지지만, 해시 함수 출력이 서로 다른 입력에 대해 균일하고 무작위적이며 독립적이어야 한다는 가정에 의존한다(Fiat & Shamir, 1986). Canetti, Goldreich, Halevi는 2003년 연구에서 이 가정이 이론 모델에서는 성립하지만 실제 응용에서는 도전에 직면할 수 있으며, 따라서 사용 시 실패할 위험이 있음을 보여주었다(Canetti, Goldreich & Halevi, 2003). Micali는 이후 이 방법을 개선하여 다중 라운드를 단일 라운드로 압축하여 상호작용 절차를 더욱 간소화했다(Micali, 1994).
4. Jens Groth及其 연구
Jens Groth의 후속 연구는 제로나우리지 프루프가 암호학과 블록체인 기술에서의 응용을 크게 촉진시켰다. 2005년 그는 Ostrovsky와 Sahai와 함께 첫 번째로 모든 NP 언어에 적용 가능한 완벽한 비대화형 제로나우리지 프루프 시스템을 제안했으며, 동적/적응형 적수에 대해서도 일반적인 조합 보안(UC)을 보장했다. 또한 그들은 수론적 복잡성 가정을 활용하여 간결하고 효율적인 비대화형 제로나우리지 프루프 시스템을 설계하여 CRS와 증명의 크기를 크게 줄였다(Groth & Sahai, 2005).
2007년 Groth, Cramer 및 Damgård는 이러한 기술을 상용화하기 시작하여 실험을 통해 공개키 암호화 및 서명 방식이 효율성과 보안성 측면에서 현저한 향상을 이루었으며, 비록 이러한 방식은 쌍선형 군 가정에 기반하지만(Groth & Sahai, 2007). 2011년 Groth는 전형적 동형 암호와 비대화형 제로나우리지 프루프를 결합하는 방법을 더 깊이 탐색하며 통신 오버헤드를 줄이는 방식을 제안하여 NIZK의 크기가 증명의 witness 크기와 일치하도록 만들었다(Groth, 2011). 이후 몇 년간 그는 다른 연구자들과 함께 쌍선형 기술에 대해 심층적인 연구를 수행하여 대규모 진술에 대해 간결하고 효율적인 비대화형 증명을 제공했으나, 이러한 증명은 여전히 쌍선형 군 프레임워크를 벗어나지 못했다(Bayer & Groth, 2012; Groth, Kohlweiss & Pintore, 2016; Bootle, Cerulli, Chaidos, Groth & Petit, 2015; Groth, Ostrovsky & Sahai, 2012; Groth & Maller, 2017).
5. 기타 연구
특정 응용 시나리오에서 특정 검증자에 대한 비대화형 제로나우리지 프루프는 독특한 실용적 가치를 보여주었다. 예를 들어 Cramer과 Shoup은 1998년과 2002년에 일반적인 해시 함수를 기반으로 하는 방법을 활용하여 공개키 암호화 방식을 개발했으며, 이는 선택적 암호문 공격(ciphertext attack)에 효과적으로 저항했다. 또한 키 등록 모델에서는 모든 NP 문제를 해결할 수 있는 새로운 비대화형 제로나우리지 프루프 방법을 성공적으로 개발했으며, 핵심은 참여자가 후속 검증을 위해 자신의 키를 등록해야 한다는 점이다(Cramer & Shoup, 1998, 2002).
또한 Damgård, Fazio 및 Nicolosi는 2006년 기존 Fiat-Shamir 변환을 개선하는 새로운 방법을 제안하여 직접적인 상호작용 없이도 비대화형 제로나우리지 프루프를 수행할 수 있도록 했다. 이들의 방법에서 검증자는 먼저 공개키를 등록하여 후속 암호화 작업을 준비해야 한다. 증명자는 덧셈 동형 암호화 기술을 사용하여 데이터를 무지 상태에서 연산하여 답변을 포함한 암호화된 정보를 생성하며, 이를 도전에 대한 응답으로 한다. 이 방법의 보안성은 '복잡성 레버리지 가정'에 기반하며, 초월적인 계산 리소스를 갖춘 적수라도 해결하기 어려운 것으로 여겨지는 일부 계산 문제가 해결될 수 있다고 생각한다(Damgård, Fazio & Nicolosi, 2006).
Ventre와 Visconti는 2009년 '약한 책임 부과 가능 건전성(weakly accountable soundness)'이라는 개념을 제안하여 이 가정을 대체했다. 이는 적수가 허위 증명을 제시할 때 단지 그것이 허위임을 인식하는 것뿐만 아니라 자신이 어떻게 성공적으로 허위 증명을 만들었는지도 분명히 알아야 한다는 요구를 의미한다. 이 요구는 기만의 난이도를 현저히 높인다. 왜냐하면 적수는 자신의 기만 수단을 명확히 해야 하기 때문이다. 실제 운영에서 이 개념을 사용하는 적수는 지정된 검증자에 대한 암호문 정보를 포함하는 특정 증명을 제공해야 하며, 해당 검증자의 비밀키 없이는 증명을 완성할 수 없으므로, 적수가 허위 증명을 시도할 때 이를 감지하여 그 행위를 노출시킬 수 있다(Ventre and Visconti, 2009).
Unruh 변환은 2015년 제안된 Fiat-Shamir 변환의 대안이다. Fiat-Shamir 방법은 일반적으로 양자 컴퓨팅에 대해 안전하지 않으며, 일부 프로토콜의 경우 안전하지 않은 방식을 생성할 수 있다(Unruh, 2015). 반면 Unruh 변환은 무작위 예언자 모델(ROM)에서 어떤 대화형 프로토콜에도 양자 적수에 대응하는 증명 가능한 안전한 비대화형 제로나우리지 프루프(NIZK)를 제공한다. Fiat-Shamir 방법과 유사하게, Unruh 변환은 추가 설정 단계를 필요로 하지 않는다(Ambainis, Rosmanis & Unruh, 2014).
또한 Kalai 등은 사생활 보호 정보 검색 기술을 기반으로 한 임의의 의사결정 문제에 대한 증명 시스템을 제안했다. 이 방법은 다중 증명자 대화형 증명 시스템(MIP) 모델을 사용하며 Aiello 등의 방법을 통해 MIP를 증명 시스템으로 변환한다. 이 구조는 무작위 예언자 가정에 의존하지 않는 표준 모델에서 작동한다. 이 방법은 '평범한 사람을 위한 증명(Proofs-for-Muggles)' 기반 제로나우리지 증명에 적용되었다(Kalai, Raz & Rothblum, 2014).
이러한 기술을 기반으로 비대화형 제로나우리지 프루프(NIZK)는 금융 거래, 전자 투표, 블록체인 기술 등 고도의 보안과 개인정보 보호가 필요한 다양한 분야에서 광범위하게 응용되었다. 상호작용 횟수를 줄이고 증명 생성 및 검증 과정을 최적화함으로써 NIZK는 시스템의 효율성을 높일 뿐 아니라 보안성과 개인정보 보호 능력을 강화했다. 앞으로 이러한 기술의 추가적인 발전과 완성을 통해 NIZK가 더 많은 분야에서 중요한 역할을 하며, 보다 안전하고 효율적인 정보 처리 및 전송을 위한 견고한 기술적 기반을 제공할 것으로 기대된다(Partala, Nguyen & Pirttikangas, 2020).
삼, 회로 기반 제로나우리지 프루프
1. 배경
암호학 분야, 특히 고도의 병렬화와 특정 유형의 계산 작업(예: 대규모 행렬 연산)을 처리할 때 전통적인 튜링 머신 모델은 일정한 한계를 드러낸다. 튜링 머신 모델은 무한한 롤을 시뮬레이션하기 위해 복잡한 메모리 관리 메커니즘을 필요로 하며, 병렬 계산과 파이프라이닝 작업을 직접 표현하는 데 적합하지 않다. 반면 회로 모델은 독특한 계산 구조적 장점으로 인해 특정 암호학 처리 작업에 더 적합하다(Chaidos, 2017). 본고는 회로 기반 제로나우리지 프루프 시스템(Zero-Knowledge Proof Systems Based on Circuit Models)을 자세히 다룰 것이며, 이러한 시스템은 특히 회로(일반적으로 산술 회로 또는 부울 회로)를 사용하여 계산 과정을 표현하고 검증하는 데 중점을 둔다.
2. 회로 모델의 기본 개념과 특징
회로 기반 계산 모델에서 회로는 어떤 계산 과정을 일련의 게이트와 연결선으로 변환할 수 있는 특수한 계산 모델로 정의된다. 이러한 게이트는 특정 논리 또는 산술 연산을 수행한다. 구체적으로 회로 모델은 주로 두 가지로 나뉜다:
-
산술 회로: 주로 덧셈 및 곱셈 게이트로 구성되어 유한 체 상의 원소를 처리한다. 산술 회로는 복잡한 수치 연산을 수행하는 데 적합하며, 암호 알고리즘 및 수치 분석에 널리 응용된다.
-
논리 회로: AND 게이트, OR 게이트, NOT 게이트 등 기본 논리 게이트로 구성되어 부울 연산을 처리한다. 논리 회로는 간단한 판단 로직 및 이진 계산을 수행하는 데 적합하며, 각종 제어 시스템 및 간단한 데이터 처리 작업에 일반적으로 사용된다(Chaidos, 2017).
3. 제로나우리지 프루프에서의 회로 설계와 응용
제로나우리지 프루프 시스템에서 회로 설계 과정은 증명할 문제를 회로 형태로 표현하는 것을 포함한다. 이 과정은 많은 '역사적 사고(reverse thinking)'를 필요로 한다. "만약 계산의 주장된 출력이 사실이라면, 출력은 일정한 요구사항을 충족해야 한다. 이러한 요구사항이 단순한 덧셈이나 곱셈으로 모델링하기 어려울 경우, 증명자가 추가 작업을 수행하도록 요구하여 이러한 요구사항을 더 쉽게 모델링할 수 있도록 해야 한다." 설계 과정은 일반적으로 다음 단계를 따른다(Chaidos, 2017):
-
문제 표현: 먼저 암호학적 해시 함수 계산과 같은 증명할 문제를 회로 형태로 변환한다. 여기에는 계산 단계를 게이트 및 연결선과 같은 회로의 기본 단위로 분해하는 것이 포함된다.
-
회로 최적화: 게이트 병합 및 상수 접기(constant folding) 등의 기술을 통해 회로 설계를 최적화하여 필요한 게이트 수와 계산 단계를 줄이고, 시스템의 실행 효율성과 응답 속도를 향상시킨다.
-
다항식 표현으로의 변환: 제로나우리지 프루프 기술에 적합하도록 최적화된 회로를 추가로 다항식 형태로 변환한다. 각 회로 구성 요소와 연결은 특정 다항식 제약에 해당한다.
-
공통 참조 문자열(CRS) 생성: 시스템 초기화 단계에서 증명 키와 검증 키를 포함한 공통 참조 문자열을 생성하여 후속 증명 생성 및 검증 과정에 사용한다.
-
증명 생성 및 검증: 증명자는 자신의 개인 입력과 CRS를 기반으로 회로에서 계산을 수행하여 제로나우리지 증명을 생성한다. 검증자는 공개된 회로 설명과 CRS를 기반으로 증명의 정확성을 검증할 수 있으며, 증명자의 개인 정보를 알 필요가 없다(Chaidos, 2017).
제로나우리지 프루프 회로 설계는 특정 계산 과정을 회로 표현으로 변환하고 다항식 제약을 구축하여 계산 결과의 정확성을 보장하면서도 추가 개인정보를 누설하지 않도록 하는 것을 포함한다. 회로 설계에서 핵심 과제는 회로 구조를 최적화하고 효과적인 다항식 표현을 생성하여 증명 생성 및 검증의 효율성을 향상시키는 것이다. 이러한 단계를 통해 제로나우리지 프루프 기술은 추가 정보를 누설하지 않으면서도 계산의 정확성을 검증할 수 있으며, 개인정보 보호와 데이터 보안의 이중 요구를 만족시킨다(Chaidos, 2017).
4. 잠재적 결함과 도전
단점은 다음과 같다:
-
회로의 복잡성과 규모: 복잡한 계산은 방대한 회로를 필요로 하여 증명 생성 및 검증의 계산 비용이 현저히 증가하며, 특히 대규모 데이터 처리 시 더욱 그러하다;
-
최적화의 어려움: 게이트 병합, 상수 접기 등의 기술을 사용할 수는 있지만, 효율적인 회로의 설계와 최적화는 여전히 깊은 전문 지식을 필요로 한다;
-
특정 계산 작업의 적응성: 서로 다른 계산 작업은 서로 다른 회로 설계를 필요로 하며, 각 구체적인 작업에 대해 효율적인 회로를 설계하는 것은 시간이 많이 들고 일반화하기 어렵다;
-
암호 알고리즘 구현의 어려움: 해시 함수나 공개키 암호화와 같은 복잡한 암호학 알고리즘을 구현하려면 많은 논리 게이트가 필요하여 회로 설계 및 구현이 어렵다;
-
자원 소비: 대규모 회로는 많은 하드웨어 자원을 필요로 하며, 전력 소모, 열 발생, 물리적 공간 등의 면에서 실제 하드웨어 구현의 병목 현상에 직면할 수 있다(Goldreich, 2004; Chaidos, 2017; Partala, Nguyen & Pirttikangas, 2020; Sun 등, 2021).
해결책과 개선 방향:
-
회로 압축 기술: 효율적인 회로 압축 기술의 연구 및 응용을 통해 필요한 논리 게이트 수와 계산 자원을 줄인다;
-
모듈화 설계: 회로를 모듈화 설계하여 회로 설계의 재사용성과 확장성을 높이고, 서로 다른 작업을 위해 회로를 다시 설계하는 작업량을 줄인다;
-
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
즐겨찾기 추가소셜 미디어 공유
Arkstream Capital
