- 주의: 저는 정보이론 (Information theory) 응용 연구와 SNARK 설계 연구를 수행한 경험이 있습니다. 이 글의 결론은 지난 경험을 조합하여 도출한 개인적 견해이며 학술적 근거는 없습니다.
- 배경 지식: SNARK와 검증회로에 관한 이해를 필요로 합니다. 관련된 간략한 설명은 저의 이전 게시물을 참고해 주세요.
- An English version can be found here.
SNARK는 정말 블록체인 데이터를 압축할 수 있을까?
이는 지난 2022년 콜롬비아 Bogota에서 개최된 Devcon6에서 Ian Miers의 발표 ‘Scalability is Boring, Privacy is Dead: ZK-Proofs, What are They Good for?’ 를 현장에서 보고 떠오른 질문입니다.
결론부터 말씀드리면, 이 질문에 대한 저의 대답은 다음과 같습니다:
SNARK는 블록체인 데이터를 압축할 수 있지만, 블록체인 보안 (Security) 혹은 분산성 (Decentralization)의 희생이 반드시 따른다.
이 글에서는 위의 대답에 대한 이유를 정보 이론 (Information theory) 관점에서 설명합니다.
정보 이론이란?
정보 이론은 1920년대부터 연구되어 온 응용 수학으로써, 확률론적 변수 (Random variable)가 내포하는 정보의 양에 관한 연구입니다. 정보이론은 변수 X의 정보량 (Entropy)를 측정 (Measure)하는 것에서 시작합니다. 그리고 정보 이론의 아버지라 불리는 Claude E. Shannon은 정보량을 다음과 같이 정의하였습니다:
여기서 더하기의 범위는 X가 출력 가능한 모든 사건입니다. 정보량의 단위는 “bits”인데, 이는 우리가 컴퓨터 공학에서 word size를 측정할 때 사용하는 단위인 bits와 같습니다 (로그 함수의 밑을 다른 값으로 바꿈으로써 다른 단위를 사용할 수도 있습니다). 정보량은 변수가 더욱 불확실할수록, 즉 변수가 출력 가능한 사건들의 확률 분포가 균등할수록 더 커지게 정의되었습니다. 반대로, 변수가 결정적이면 (deterministic) 정보량은 0 bits 입니다.
정보 이론은 비결정적 데이터의 압축에 대한 이론적 한계를 설명합니다: 비결정적 데이터가 내포하는 모든 불확실성을 잃어버리지 않고 표현하기 위해서는, 표현 수단의 차원이 적어도 데이터의 정보량보다 같거나 커야 한다는 이론적인 결과가 있습니다.
정보 이론의 활용 예
예를 들어, 면이 8개인 주사위를 던져 나온 가장 윗면의 값을 X라고 한다면, X의 정보량은 정의에 의해 3bits입니다. 정보 이론은 X의 측정 결과를 기록하기 위해서는 적어도 3-bit 길이의 이진 문자열이 필요하다고 말합니다.
또 다른 예를 들겠습니다. 어떤 변수 Y의 출력을 3-bit 길이의 이진 문자열에 기록하고 있는데, 이 출력물에서 다음과 같은 규칙들이 발견되었다고 가정하겠습니다: 1) 세 비트 중 적어도 한 비트는 1이다; 2) 세 비트 중 첫 번째 혹은 두 번째 비트가 1이라면, 그 다음 비트는 반드시 0이다. 이러한 규칙 하에서 발생 가능한 문자열은 001, 010, 100, 그리고 101뿐입니다. 이 출력물들이 균등 확률 (Equally-likely), 즉 각각 1/4의 확률로 발생한다고 가정하면, Y의 정보량은 2 bits입니다. 만약 Y라는 변수를 기록 및 저장하고 있는 기존의 3-bit 길이의 문자열에 어떤 처리를 가하여 용량을 줄이고자 한다면, 그 결과물의 용량은 2-bit 보다는 같거나 커야 합니다.
이러한 결과는 1차원 랜덤 변수가 아닌 다차원의 랜덤 벡터 (랜덤 변수의 벡터)에도 마찬가지로 적용됩니다. 어떤 벡터 (프로그래머의 표현으로는 배열)를 무손실 (Lossless) 압축 (Compression)할 수 있는 한계는 그 벡터의 정보량에 의해 결정됩니다. 다시 말해, 어떤 벡터를 정보량보다 더 작은 차원의 벡터로 압축하면 손실(Lossy) 압축이 될 수밖에 없고, 이는 원본 벡터로 다시 되돌릴 수 없음을 의미합니다. 우리가 잘 알고 있는 무손실 압축 알고리즘의 예는 zip, rar, 혹은 7z등이며, 손실 압축의 예는 고화질의 Tiff 포맷 이미지를 저화질의 JPEG 포맷으로 변환하는 것입니다.
SNARK는 압축기?
질문 “SNARK는 정말 블록체인 데이터를 압축할 수 있을까?”으로 다시 돌아오겠습니다. 이 질문에 대한 답을 도출하기 위해 먼저 SNARK의 증명기(Prover)가 하나의 압축 알고리즘이라고 가정하겠습니다. 그렇다면 SNARK 증명기는 손실과 무손실 압축 중 어느 범주에 속할까요? 이를 확인하기 위해 먼저 SNARK 증명기가 압축하려는 데이터인 “Witness”의 불확실성을 확인하겠습니다.
Witness는 SNARK의 증명기가 증거 생성 과정에서 생성하고 폐기하는 비밀스러운 데이터 벡터입니다. SNARK증명기가 하나의 압축기라는 가정 하에, Witness는 압축되기 전의 원본 데이터라 할 수 있습니다. 따라서 SNARK의 검증기(Verifier)의 관점에서는 Witness는 비결정적이며, 힌트가 없이는 전혀 예측할 수 없기 때문에 최대의 정보량을 가진다고 할 수 있습니다. 즉, 무손실 압축을 할 여지가 없습니다. 우리가 위에서 논의한 정보 이론에 의하면, SNARK 검증기가 증거로부터 Witness를 손실 없이 복원하는 것은 불가능해야 합니다.
SNARK의 목표
여기까지는 정보 이론의 입장이었고, SNARK의 목표는 다를 수 있으니 꼼꼼히 확인해 보겠습니다. SNARK 증명기가 목표하는 압축은 무손실과 손실 압축 중 어느 것일까요? 이는 SNARK의 3 가지 보안 정의인 Completeness, Knowledge soundness, 그리고 Zero-knowledge 중 두 번째인 Knowledge soundness의 정의를 보면 알 수 있습니다. Knowledge soundness의 쟁점은 “1에 가까운 확률로 아주 작은 차원의 압축된 증거에서 아주 큰 차원의 Witness를 복원할 수 있는 가상의 추출 알고리즘(Extractor)이 존재하느냐?” 입니다. 다시 말해 SNARK 증명기가 목표하는 압축은 무손실 압축입니다.
대부분의 SNARK 프로토콜들이 논문을 통해 knowledge soundness를 증명하였기 때문에, 언뜻 보기에는 이들이 정보 이론적으로는 무손실 압축이 불가능한 데이터를 다룸에도 불구하고 무손실 압축을 수행할 수 있는 증명기를 설계한 것 처럼 보이긴 합니다. 그리고 zk-rollup이라는 기술을 접해보신 분들 중 대부분이 그렇게 알고 계실 것입니다. 그런데 여기에는 치명적인 가정이 하나 숨어 있습니다.
블록체인 압축기로써는 치명적인 가정
SNARK의 가정은, 검증기가 Oracle polynomial들에 접근 가능하다는 것입니다. 이 Oracle polynomial들의 집합은 검증회로 (Circuit)라고 불리며 Witness에 규칙을 부여합니다. 검증회로 또한 정보량을 가진 변수입니다. 검증기가 검증회로에 접근 가능하다는 것은 검증기가 아주 큰 정보량을 이미 가지고 있다는 것을 의미합니다. 이러한 가정 하에 SNARK증명기로 압축된 증거에서 Witness를 복원하는 가상의 추출기가 존재 할 수 있는 것입니다 (존재한다는 것일 뿐, 검증기가 실제로 추출을 수행하지는 않습니다).
이는 정보 이론적으로도 설명이 되는데, 아무런 힌트가 주어지지 않은 Witness는 최대의 정보량을 가지는 반면, 검증회로라는 정보가 주어졌다는 조건 하에서는 Witness의 조건적 정보량이 0 bits가 됩니다. 이는 검증 회로가 Witness가 가질 수 있는 값들의 모든 규칙을 결정하기 때문입니다. 즉, SNARK증명기는 Witness와 검증회로의 상호정보량 (mutual information)을 활용하는 무손실 압축기입니다.
SNARK 증명기가 블록체인 Scalability를 위해 데이터를 압축하려는 상황에서 이러한 사전정보의 가정은 아주 비현실적입니다. 블록체인 Scalability에서는 검증 노드가 아주 작은 차원의 압축된 데이터만을 가지고도 큰 차원의 원본 데이터의 올바름을 검증할 수 있도록 하는 것이 목표 중 하나인데, 만약 검증노드가 SNARK 검증기라고 한다면, 검증노드는 이미 검증회로라는 큰 차원의 데이터를 지니고 있다는 모순이 발생합니다.
SNARK를 블록체인 Scalability에 적용하는 실용적인 방법들
이러한 문제을 극복하기 위한 실용적인 방안은 새로운 가정을 추가하는 것입니다: 신뢰할 수 있는 제3자가 존재하여 이들이 올바른 검증회로를 게시한다는 가정입니다. 이 가정은 검증노드 각각이 검증회로를 지니고 있을 필요 없이, 제3자의 게시물을 참조하는 것으로도 제 역할을 수행할 수 있게 해줍니다. 그러나 이러한 가정이 실현된다면 블록체인 분산성 (Decentralization)의 저하는 불가피합니다.
또 다른 방안도 있습니다. Powers-of-tau (Snarky ceremonies)와 같은 Threshold cryptography 기반의 분산 키 생성 기술을 활용하는 것입니다. 쉽게 말해, 다수의 행사(Ceremony) 참여자가 일정 기간동안 올바른 검증회로 생성에 기여합니다. 이 방식은 이전 방식에서 필요했던 신뢰할 수 있는 제3 자를 제거합니다. 그러나 이 방식 또한 새로운 가정을 필요로 합니다: 참여자들 중 적어도 한 명 (혹은 프로토콜에 따라 절반 이상)이 올바르다는 가정입니다. 이는 곧 블록체인의 보안 (Security)의 저하를 야기합니다.
여기서 블록체인 보안과 분산성이란 과거 Vitalik Buterin이 정의했던 Scalability trilemma의 요소들입니다.
결론
지금까지의 이야기를 요약하면, 블록체인 Scalability를 위해 SNARK 증명기가 무손실 압축기 역할을 할 수는 있지만, 이를 위해서는 보안 혹은 분산성 중 하나를 희생해야만 합니다.
그렇다면 보안을 잃지 않으면서 블록체인 데이터를 압축하는 방법은 없을까요? 옵티미스틱 롤업의 접근이 이러한 시도 중 하나입니다. 옵티미스틱 롤업은 레이어 2의 데이터를 전통적인 무손실 압축 알고리즘 (혹은 그것들의 변형)을 이용해서 압축 후 레이어1에 기록합니다. 압축된 데이터를 삭제하지 않는다는 가정 하에 (예를 들어 Blob이 없다는 가정) 보안을 저하하지 않는 최선의 압축 방법을 선택한 것입니다. 그러나 안타깝게도 옵티미스틱 롤업에는 레이어1의 검증 노드가 복원 없이 원본 데이터의 올바름을 검증하도록 해주는 비용-효율적인 기능이 없습니다.
저의 결론은 결코 SNARK기반 Scalability 솔루션 (예를 들어, Zk-rollup)들의 가치를 평가절하하는 것이 아닙니다. 저는 Vitalik Buterin의 최근 블로그 게시물에 깊게 공감하는데, 그 내용은 레이어2의 다양성에 관한 것입니다. 레이어2 솔루션 또한 Scalability trilemma의 굴레를 벗어나지 못하므로, 보안은 레이어1이 보장하고, 레이어2에서는 사용자에게 보안 혹은 분산성을 일부 희생하는 대신 성능적 이점을 제공하는 선택지, 즉 사용자에게 더 다양한 Dapp을 활용할 기회를 제공해주는 것에 큰 가치가 있다고 생각합니다.
우리가 개발중인 Tokamak zk-EVM 및 Zk-rollup는 SNARK와 합의 프로토콜을 적절히 조합한 새로운 접근 방식입니다. 완전히 SNARK에만 의존하는 Scroll 및 Linea 등의 기존 Zk-rollup과는 전혀 다른 방식이며, Challenging이라는 합의 프로토콜에만 의존하는 Optimistic rollup과도 또 전혀 다른 방식입니다. 우리의 도전이 Scalability trilemma 하에서 발현 가능한 다양성 공간에 하나의 새로운 기저 벡터를 제공해 주기를 기대합니다.