SNARKs 대 STARKS 대 재귀적 SNARKs

영지식 증명은 한 당사자가 정보 자체를 노출하지 않고 다른 당사자에게 해당 정보에 대한 지식을 증명할 수 있게 하는 메커니즘이다. 유효성 증명(validity proof)이라고도 불리는 ZK 증명은 원래 프라이버시 중심 블록체인에서 트랜잭션 세부 정보를 숨기는 데 사용되었다.

하지만 ZK 증명에는 또 다른 흥미로운 활용 사례가 있다. 바로 범용 블록체인의 확장이다. 유효성 증명을 사용하면 블록체인 노드는 세부 정보를 저장하거나 연산을 재실행하지 않고도 트랜잭션을 검증할 수 있다. 이는 확인 시간을 단축하고 네트워크 처리량을 높인다.

확장성 이점 덕분에 ZK 증명은 블록체인 확장 프로젝트, 특히 zero-knowledge rollups의 핵심 인프라가 되었다. 이 가이드에서는 블록체인에서 사용되는 ZK 증명의 주요 분류인 ZK-SNARK, ZK-STARK, 재귀적 ZK-SNARK를 다룬다.

ZK-SNARK란 무엇인가?

ZK-SNARK는 기반 데이터를 노출하지 않고 정보의 진위를 검증하기 위한 영지식 증명을 생성하는 프로토콜이다. 이 약어는 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge를 의미한다.

ZK-SNARK 프로토콜에는 두 당사자가 관여한다. 증명자(prover, Alice)와 검증자(verifier, Bob)다. 증명자(Alice)는 주장을 하는 당사자이고, 검증자(Bob)는 그 주장을 검증하는 책임을 지는 당사자다.

주장에서 언급되는 정보를 증인(witness) 또는 _비밀(secret)_이라고 부른다. 증명자(Alice)는 ZK-SNARK 메커니즘을 사용해 증명을 생성함으로써 검증자(Bob)에게 해당 주장이 참임을 보이는데... 이때 참조된 정보 자체는 드러내지 않는다.

ZK-SNARK가 관련될 수 있는 가상의 예로 사용자 신원 인증이 있다. 개인은 여권이나 사회보장번호 같은 개인정보를 노출하지 않고도 "나는 미국 시민이다"라는 진술을 증명할 수 있다.

ZK-SNARK라는 이름은 다음과 같은 특성을 지니기 때문에 붙었다.

1. Zero-knowledge(영지식): 검증자는 진술의 참/거짓 여부 외에는 그 진술에 대해 아무것도 알지 못한다는 뜻이다.

2. Succinct(간결함): 증명은 검증자가 짧은 시간 내에 검증할 수 있을 만큼 작다.

3. Non-interactive(비대화형): SNARK가 비대화형인 이유는 증명자와 검증자가 최초 제출된 증명 이외에 정보를 교환할 필요가 없기 때문이다. 초기 영지식 증명 시스템은 진술을 검증하기 위해 증명자와 검증자가 여러 메시지를 주고받아야 했다.

4. Argument(논증): SNARK는 엄격한 요건을 충족하는 "계산적으로 견고한(computationally sound)" 진술로, 이로 인해 부정행위(즉, 거짓 증명 생성)가 어렵다.

5. Knowledge(지식): SNARK 기반 증명은 기반 정보, 즉 _증인_에 대한 접근 없이는 생성될 수 없다.

블록체인에서의 ZK-SNARK

퍼블릭 블록체인 같은 분산 컴퓨팅 시스템은 이른바 "연산 무결성 문제(computational integrity problem)"를 해결해야 한다. 연산 무결성(CI)은 특정 연산에서 얻은 출력의 정확성을 의미한다.

퍼블릭 블록체인에서 연산 무결성은 네트워크에서 실행된 트랜잭션의 정확성을 의미한다. 대부분의 블록체인은 다른 컴퓨터(노드)가 각 트랜잭션을 재실행하도록 함으로써 이를 달성한다.

하지만 이 접근 방식에는 문제가 있다. 모든 노드가 각 트랜잭션을 재실행하도록 강제하면 네트워크 속도가 느려지고 확장성이 제한된다. 노드는 연산을 재실행하기 위해 트랜잭션 데이터를 저장해야 하는데, 이는 블록체인 크기의 기하급수적 증가를 초래한다.

하지만 노드가 연산을 재실행하지 않고도 그 유효성을 확인할 수 있다면 어떨까? 이는 네트워크 처리량을 향상시키고 노드가 불필요한 트랜잭션 데이터를 저장할 필요를 없앨 것이다.

ZK-SNARK가 등장하는 지점이다.

ZK-SNARK를 사용해 생성된 유효성 증명은 입력값을 노출하지 않고도 트랜잭션의 유효성을 증명할 수 있다. 이것이 Zcash나 Monero 같은 프라이버시 중심 암호화폐가 트랜잭션 정보를 감추기 위해 SNARK를 사용하는 이유다.

SNARK는 또한 노드가 연산의 모든 단계를 재실행하지 않고도 오프체인에서 수행된 연산의 정확성을 증명할 수 있다. 바로 이 지점에서 ZK-SNARK가 블록체인 확장에 유용해진다.

SNARK를 사용해 오프체인 연산을 검증하는 것은 연산을 수학적 표현으로 인코딩하는 것에서 시작하는 복잡한 과정이다. 이 수학적 진술이 유효성 증명의 기반을 형성한다.

이후 검증자는 증명에 대해 연산을 수행하여 정확성을 확인한다. 증명이 모든 검사를 통과하면 기반이 되는 연산은 유효한 것으로 간주된다. 이것이 SNARK가 간결한(succinct) 이유다. 유효성 증명의 크기는 그것이 검증하는 연산보다 훨씬 작다.

ZK-SNARK와 ZK rollups

rollup은 Ethereum의 Layer 2 확장 솔루션으로, 오프체인 실행을 통해 Layer 1(L1) 블록체인의 처리량을 향상시킨다. rollup은 L2 체인에서 트랜잭션을 처리하고, 여러 오프체인 트랜잭션을 블록으로 집계한 뒤 L1 체인에 제출한다.

연산을 기반 레이어에서 옮김으로써 rollup은 네트워크 혼잡을 줄이고 트랜잭션을 확장한다.

하지만 L1 체인은 오프체인에서 실행된 트랜잭션이 유효한지 알아야 한다(즉, 연산 무결성 문제). 그렇지 않으면 악의적인 행위자가 rollup을 탈취해 잘못된 트랜잭션을 메인 체인에 제출할 수 있다.

한 유형의 rollup(zero-knowledge rollup)은 ZK-SNARK를 사용해 오프체인 트랜잭션의 진위를 L1 체인에 증명한다. SNARK 증명은 누구나 검증할 수 있어, L1 체인에 트랜잭션 유효성을 보장한다.

ZK-SNARK를 사용하는 대부분의 ZK rollup은 다음과 같은 동일한 구조를 따른다.

1. L2 체인의 사용자가 트랜잭션에 서명하고 validator에게 제출한다.

2. Validator는 트랜잭션을 블록으로 압축하고 이에 대응하는 유효성 증명(SNARK)을 생성한다. 이는 새로운 상태가 유효한 트랜잭션 추가로부터 발생했다는 암호학적 보장을 제공한다.

3. L1 체인의 스마트 컨트랙트가 유효성 증명에 대해 연산을 수행한다. 이 연산 결과에 따라 배치된 트랜잭션이 검증되어 메인 체인에 게시될지 여부가 결정된다.

ZK-SNARK의 이점은 무엇인가?

ZK-SNARK를 사용하는 데는 세 가지 주요 이점이 있다: 높은 처리량, 작은 유효성 증명 크기, 그리고 보안성이다.

1. 높은 처리량

ZK-SNARK는 Ethereum 기반 레이어의 연산을 축소함으로써 처리량을 확장한다. ZK-SNARK를 사용하면 rollup은 TPS 비율을 수천 단위까지 늘릴 수 있다.

ZK-SNARK는 보통 그것이 검증하는 트랜잭션 데이터보다 훨씬 작다. 이는 기반 블록체인의 혼잡을 줄이고 더 저렴한 gas fee와 더 빠른 트랜잭션을 가능하게 한다.

2. 작은 증명 크기

SNARK 증명의 작은 크기 덕분에 메인 체인에서 검증하기 쉽다. Ethereum에서는 이것이 오프체인 트랜잭션 검증에 드는 gas fee를 낮춰 최종 사용자의 rollup 비용을 절감함을 의미한다.

3. 보안성

ZK rollup은 다른 확장 프로젝트보다 더 안전하다고 여겨지는데, 이는 주로 ZK-SNARK에 사용되는 최첨단 암호학적 보안 메커니즘 때문이다.

ZK-SNARK 증명은 계산적으로 견고하여 검증자를 속이고 악의적으로 행동하기 어렵게 만든다. ZK-SNARK의 비대화성은 또한 누구나 신뢰 없이(trustlessly) 증명을 검증할 수 있음을 의미한다.

ZK-SNARK의 단점은 무엇인가?

ZK-SNARK를 사용하는 데는 세 가지 주요 단점이 있다: trusted setup이 필요하다는 점, 양자 컴퓨팅 공격에 취약하다는 점, 그리고 특수 하드웨어에 의존한다는 점이다.

1. Trusted setup

ZK-SNARK 프로토콜을 설정하려면 Universal Common Reference String(CRS)을 생성해야 한다. _공개 매개변수(public parameters)_라고도 불리는 CRS는 증명자와 검증자 간의 안전한 통신을 가능하게 한다.

악의적인 행위자가 공개 매개변수를 알게 되면 거짓 유효성 증명을 생성할 수 있다. 일부 프로젝트는 서로 다른 개인들이 참여하는 multi-party computation(MPC)을 사용해 공개 매개변수를 생성함으로써 이 문제를 해결하려 한다.

그럼에도 이 접근 방식은 사용자가 관여자들의 무결성을 신뢰해야 한다는 점을 요구한다. 블록체인의 목적이 권위자에 대한 신뢰 필요성을 줄이는 것이라는 점에서 이는 상당히 문제가 된다.

2. 양자 컴퓨팅 공격에 대한 취약성

ZK-SNARK는 유효성 증명을 생성하는 데 사용되는 정보를 암호화하기 위해 Elliptic Curve Cryptography(ECC)를 사용한다. ECC는 현재로서는 비교적 안전하지만, 양자 컴퓨팅의 발전이 그 보안 모델을 무너뜨릴 수 있다.

3. 특수 하드웨어에 대한 의존

ZK-SNARK로 유효성 증명을 생성하는 것은 연산 집약적인 과정이며, 이는 증명자가 특수 하드웨어에 투자해야 함을 의미한다. 이런 기기를 구매할 수 있는 사람이 매우 적기 때문에, 많은 이들은 ZK-SNARK 증명 생성 과정이 상당히 중앙화되어 있다고 본다.

ZK-SNARK를 사용하는 프로젝트는 무엇인가?

ZK-SNARK를 사용하는 다섯 가지 주목할 만한 프로젝트로는 ZKSync, Loopring, Aztec, Polygon Hermez, ZKSpace가 있다.

zkSync

Matter Labs가 만든, Ethereum Mainnet에 존재하는 EVM 호환 ZK rollup이다. ZKSync는 스마트 컨트랙트, 토큰 스왑, 결제, NFT 민팅을 지원한다.

Loopring

SNARK 기반 ZK rollup 기술로 구동되는 Ethereum Layer 2(L2) 프로젝트다. Loopring은 또한 ETH와 다른 ERC-20 토큰을 Ethereum Mainnet의 DEX들이 부과하는 비용의 일부만으로 거래할 수 있는 탈중앙화 거래소 역할도 한다.

Aztec

Ethereum 네트워크 위에 구축된 오픈소스 L2 네트워크다. Aztec은 ZK-SNARK를 활용해 트랜잭션을 확장하고 사용자의 금융 프라이버시를 높인다.

Polygon hermez

Ethereum 블록체인 위에서 작동하는 ZK rollup이다. Polygon Hermez는 ZK-SNARK를 사용해 안전하고 저비용의 토큰 전송과 결제를 구동한다.

Zkspace

ZK-SNARK 기반 ZK rollup 프로젝트다. ZKSpace는 Ethereum 사용자에게 더 낮은 gas fee와 더 빠른 트랜잭션을 제공하며, AMM 방식 DEX(ZKSwap v3), 결제 네트워크(ZKSquare), NFT 마켓플레이스(ZKSea)로 구성된다.

ZK-STARK란 무엇인가?

ZK-STARK는 Zero-Knowledge Scalable Transparent Argument of Knowledge의 약자다. ZK-SNARK와 마찬가지로 ZK-STARK는 진술 자체에 대해 아무것도 노출하지 않고 그 진술이 유효함을 보여준다.

몇 가지 차이를 제외하면 STARK는 SNARK와 동일한 특성을 가진다. STARK 기반 유효성 증명은 검증자에게 숨겨진 정보 조각을 사용해 생성된다. STARK 역시 입력값을 노출하지 않고 트랜잭션의 정확성을 검증할 수 있다.

ZK-STARK vs. ZK-SNARK

ZK-STARK의 주요 차이점은 확장 가능성(scalable)과 투명성(transparent) 속성에서 비롯된다.

ZK-STARK는 Common Reference String(CRS)의 trusted setup 없이 작동할 수 있기 때문에 투명하다고 여겨진다. 대신 STARK 프로토콜은 증명자와 검증자 사이의 상호작용을 설정하기 위해 공개적으로 검증 가능한 무작위성을 사용한다.

ZK-STARK가 _확장 가능(scalable)_한 이유는 증명 및 검증의 복잡도가 연산 복잡도에 대해 준선형적으로(quasilinearly) 확장되기 때문이다. ZK-SNARK의 경우 증명 및 검증 복잡도는 기반 연산에 대해 선형적으로(linearly) 확장된다.

이는 단순히 검증해야 할 연산이 커질수록 ZK-SNARK 프로토콜이 ZK-STARK보다 증명을 생성하고 검증하는 데 더 많은 시간이 필요함을 의미한다. 이것이 STARK가 대량의 트랜잭션을 처리하는 애플리케이션에 더 적합한 이유다.

ZK-STARK의 이점은 무엇인가?

ZK-STARK를 사용하는 데는 네 가지 주요 이점이 있다: trusted setup이 필요 없다는 점, 확장 가능하다는 점, 사용자에게 최대 처리량을 제공한다는 점, 그리고 높은 보안 보장을 제공한다는 점이다.

1. trusted setup이 필요 없음

ZK-STARK는 작동하는 데 trusted setup이 필요하지 않고 대신 공개 무작위성에 의존한다. 이는 사용자 측의 신뢰 가정을 줄이고 STARK 기반 프로토콜의 보안을 향상시킨다.

2. 확장 가능한 속성

STARK는 SNARK에 비해 규모가 커질 때 더 빠르게 연산 및 검증될 수 있다. 더 중요한 점은, ZK-STARK는 기반 연산의 복잡도가 기하급수적으로 증가하더라도 증명 및 검증 시간을 낮게 유지한다는 것이다.

3. 최대 처리량

SNARK와 마찬가지로 STARK는 안전하고 검증 가능한 오프체인 연산을 가능하게 함으로써 블록체인을 확장할 수 있다.

L1 체인에 제출된 단일 STARK 증명은 메인 체인 외부에서 수행된 수천 건의 트랜잭션을 검증할 수 있다. 따라서 여러 주요 ZK rollup 프로젝트가 오프체인 연산의 무결성을 증명하기 위해 ZK-SNARK를 사용한다.

4. 더 높은 보안 보장

ZK-STARK는 ZK-SNARK에서 사용되는 타원곡선 방식 대신 충돌 저항성 해시(collision-resistant hashes)를 암호화에 사용한다. 이는 양자 컴퓨팅 공격에 저항력이 있는 것으로 간주되어, SNARK에서 사용되는 타원곡선보다 더 안전하다.

ZK-STARK의 단점은 무엇인가?

ZK-STARK를 사용하는 데는 두 가지 주요 단점이 있다: 더 큰 증명 크기를 사용한다는 점과 블록체인 분야에서 이 기술의 채택이 상대적으로 적다는 점이다.

1. 더 큰 증명 크기

STARK는 더 빠른 증명을 제공하지만, 단점은 이러한 증명이 SNARK 기반 증명에 비해 더 크다는 것이다. 이는 더 큰 증명을 연산하는 데 더 높은 gas fee가 발생하기 때문에 Ethereum에서 STARK 증명 검증 비용을 더 높게 만든다.

2. 낮은 채택률

SNARK는 블록체인에서 영지식 기술의 첫 실용적 응용이었으며, 이것이 SNARK가 STARK보다 더 많은 시장 점유율을 가진 이유다. 대부분의 ZK rollup은 ZK-SNARK를 사용하며, SNARK 기반 ZK 증명을 위한 개발자 생태계와 도구가 더 크다.

ZK-STARK 역시 Ethereum Foundation을 포함한 유력한 지지자들이 있지만, 채택률은 더 낮다. 따라서 개발자는 STARK로 ZK 프로젝트를 구축할 때 지원과 도구가 더 적다는 것을 알게 될 수 있다.

ZK-STARK를 사용하는 프로젝트는 무엇인가?

StarkNet

Ethereum의 L2 네트워크로 작동하는 범용 ZK rollup이다. StarkNet은 탈중앙화 애플리케이션이 Ethereum의 탈중앙화와 보안을 훼손하지 않고도 무제한의 확장성을 달성할 수 있게 한다.

dYdX

빠르고 저비용의 거래, 대출, 차입을 암호화폐 사용자와 트레이더에게 제공하는 Ethereum 기반 ZK rollup 프로젝트(동시에 탈중앙화 거래소이기도 하다)다. dYdX는 보안 메커니즘의 일환으로 STARK 증명을 사용하여 사용자 자금의 안전을 보장한다.

Polygon miden

EVM 호환성을 갖춘 STARK 기반 ZK rollup이다. 아직 개발 중이지만, Polygon Miden은 출시 시점에 최초의 EVM 호환 ZK-STARK 프로토콜이 될 것이며, 개발자들이 Ethereum 네이티브 앱을 마이그레이션하여 L2 네트워크에서 확장성을 누릴 수 있게 할 것이다.

재귀적 ZK-SNARK란 무엇인가?

재귀적 SNARK 시스템은 서로 다른 트랜잭션 블록에 대한 증명을 병렬로 생성하고 이를 하나의 단일 블록 증명으로 집계해 메인 블록체인에 제출하는데, 이는 하나의 SNARK가 다른 SNARK들을 검증할 수 있음을 의미한다.

L2 rollup은 여전히 Ethereum에 하나의 유효성 증명을 제출한다. 하지만 이 "재귀적 증명(recursive proof)"은 여러 L2 블록의 트랜잭션을 검증하며, on-chain 컨트랙트가 제출된 증명을 수락하는 순간 이 트랜잭션들 모두가 유효해진다.

재귀적 ZK-SNARK는 어떤 문제를 해결하는가?

재귀적 ZK-SNARK는 L1 체인에 제출되는 단일 증명에 여러 L2 증명을 포함시킴으로써 ZK 증명으로 확정될 수 있는 트랜잭션 수를 극적으로 늘린다. 이는 현재 Ethereum의 12~14초 블록 타임에 의해 제한되어 있다.

블록 타임이란 Ethereum에서 새로운 트랜잭션 블록을 채굴하는 데 걸리는 시간을 말한다. ZK rollup은 블록당 하나의 on-chain 트랜잭션(및 이에 대응하는 유효성 증명)만 제출할 수 있어, 처리할 수 있는 트랜잭션 수가 제한된다.

재귀적 ZK-SNARK는 일반 ZK-SNARK와 어떻게 다른가?

재귀적 ZK-SNARK는 서로 다른 L2 블록을 위해 생성된 SNARK들을 하나로 결합하여 L1 체인에 제출되는 단일 유효성 증명으로 만듦으로써 하나 이상의 트랜잭션 블록을 검증할 수 있다는 점에서 일반 ZK-SNARK와 다르다.

ZK rollup은 메인 블록체인에 게시하기 전에 각 트랜잭션 배치마다 SNARK 증명을 생성하며, 단일 SNARK 증명은 L2 rollup에서 수행된 트랜잭션 한 블록만 검증할 수 있다.

ZK-SNARK는 원래의 입력값을 사용하지 않고도 일반 ZK-SNARK에 의해 검증된 트랜잭션을 검증할 수 있다. 따라서 on-chain 스마트 컨트랙트는 여러 SNARK를 입력값으로 실행하지 않고도 더 많은 오프체인 연산 집합을 검증할 수 있다.

plonky2란 무엇인가?

Plonky2는 재귀적 ZK-SNARK를 사용해 트랜잭션을 늘리기 위해 제안된 Polygon ZK rollup인 Polygon Zero에서 사용되는 새로운 증명 메커니즘이다.

재귀적 SNARK는 여러 증명을 하나의 재귀적 증명으로 집계함으로써 증명 생성 과정을 확장하며, Plonky2는 새로운 블록 증명을 생성하는 데 걸리는 시간을 줄이기 위해 같은 기법을 사용한다.

Plonky2 증명 메커니즘은 수천 건의 트랜잭션에 대한 증명을 병렬로 생성한 뒤 이를 재귀적으로 하나의 블록 증명으로 집계한다. 이는 전체 블록 증명을 한 번에 생성하려는 전통적인 증명 메커니즘보다 더 효율적이다.

이 접근 방식의 이점은 명백하다.

Plonky2는 0.17초 만에 재귀적 증명을 생성할 수 있으며, 이는 현존하는 가장 빠른 증명 메커니즘이다. 게다가 Plonky2는 일반 소비자용 기기에서 증명을 생성할 수 있어, 일반적인 SNARK 기반 prover 시스템이 안고 있던 하드웨어 중앙화 문제를 해결한다.

결론

영지식 증명은 프라이버시 보호 기술에서 확장 기술의 다음 프론티어로 발전해왔다. ZK rollup의 폭발적 증가와 함께, ZK-SNARK, ZK-STARK, 재귀적 SNARK가 Ethereum 확장을 향한 노력에서 크게 두드러질 것이라고 말할 수 있다.

Web3 개발자는 Alchemy가 지원하는 STARK 기반 Ethereum ZK rollup인 StarkNet 위에서 구축함으로써 영지식 기술을 활용할 수 있다. 오늘 바로 트레이드오프 없이 확장 가능한 앱을 만들기 시작하라!