Deep dive into zkEVM

Published in

Decipher Media ｜디사이퍼 미디어

16 min readMar 29, 2024

Disclaimer : 서울대학교 블록체인 학회 디사이퍼(Decipher)에서 zkEVM을 주제로 Weekly Session에서 발표한 내용을 바탕으로 합니다. 본 아티클은 zkEVM의 개념, zkEVM 구현 방법론 등에 대한 내용을 다루고 있습니다. 이 보고서에 포함된 어떠한 내용도 투자 조언이 아니며, 투자 조언으로 해석되어서도 안 됩니다.

Author

Merlyn of Decipher Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media) Reviewed By 신성헌, 박순종, 최재우

Abstract

최근 여러 Layer 2 프로젝트에서 빠른 속도로 발전하고 있는 zkEVM이 무엇인지 영지식증명의 이론적인 기반과 함께 알아보고 현재 zkEVM을 사용하고 있는 ZK 롤업들의 특징들을 비교합니다. 이 아티클은 이더리움과 Layer 2, 영지식증명에 대한 기초적인 지식을 가진 독자들을 대상으로 작성되었습니다.

Scaling Ethereum
ZK-SNARK
What is zkEVM?
The architecture of zkEVM
Types of zkEVM
Optimization
Conclusion

1. Scaling Ethereum

블록체인 트릴레마(Blockchain Trilemma)란 탈중앙화(Decentralization)와 보안(Security), 확장성(Scalability)을 한 번에 만족시키기 어려움을 뜻합니다. 2014년경에 블록체인 트릴레마라는 개념이 제시되었지만, 여전히 Layer 1의 풀리지 않는 숙제입니다. Layer 1의 확장성을 위한 솔루션으로 여러 가지 방안들이 제시되었는데, 이더리움의 경우 탈중앙성(Decentralization)과 보안(Security)은 블록체인 중에서도 최고 수준이라고 할 수 있지만 수수료가 비싸고 트랜잭션 처리 속도가 느리다는 점에서 확장성(Scalability)이 부족하다는 단점이 있습니다.

이더리움의 확장성을 위한 가장 중요한 솔루션 중 하나가 트랜젝션들을 오프체인에서 처리해 속도를 향상시키고 비용을 절감하는 Layer 2입니다. Layer 2는 유효성 검증 방식과 데이터 가용성에 따라 Rollup, Plasma, Validium 등 여러 가지 유형으로 분류할 수 있는데 그 중 Rollup은 트랜잭션 데이터를 온체인에 올리는 방식입니다.

Rollup은 크게 ZK-Rollup과 Optimistic Rollup으로 나눌 수 있는데, 이들의 가장 큰 차이는 Validity proof 제출의 유무입니다. Optimistic Rollup의 경우 “Presumption of innocent”를 전제로 Layer 2에서 어떤 증명 값을 제출하지 않고, 수동적으로 Challenge를 받는 방식인 반면 ZK 롤업의 경우 Layer 2 데이터를 Layer 1 블록에 올릴 때마다 해당 데이터에 대한 Validity proof를 능동적으로 제출합니다. 해당 글에서는 zkEVM 또는 zkVM을 사용해 Proof를 생성하는 Universal ZK-Rollup을 중점적으로 살펴보겠습니다.

2. ZK-SNARK

본격적으로 zkEVM에 대해 알아보기 전에 ZK-SNARK에 대해 알아보겠습니다. zkEVM에서는 Validity Proof를 생성하기 위해 주로 ZK-SNARK라는 증명 방식을 사용합니다. ZK-SNARK는 Zero Knowledge Succinct Non-interactive Argument of Knowledge의 약자로 ZK의 속성인 Hiding과, SNARK의 속성인 Non-interactive를 모두 만족하면서 간결한 검증을 할 수 있는 증명 방식입니다.

용어 및 개념설명

Setup
합의된 형태를 통해 Prover와 Verifier가 증명과 검증을 위해 각각 가지고 있는 파라미터입니다.

Prover
증명하고자 하는 Function을 Arithmetic circuit의 형태로 바꿉니다. Arithmetic circuit을 Oracle(주로 다항식)의 형태로 바꿉니다. Oracle을 암호학적인 컴파일을 통해 특정 형태의 Commitment 값으로 Verifier에게 제출합니다.

Verifier
Prover로부터 받은 증명 값을 검증 로직으로 연산 후 Accept 또는 Reject 합니다.

ZK-SNARK는 어떤 로직(Program)의 유효성을 증명할 수 있는 제약조건 집합(Constraints)들인 Circuit으로 나타내는 부분과 Circuit을 다시 암호학적인 방법으로 Proof 값으로 생성하는 부분으로 나눌 수 있습니다.

ZK-SNARK의 특성

ZK-SNARK에는 여러 가지 scheme들이 존재하는데 각각의 장단점이 있기 때문에, zkEVM의 형태와 Trade-off를 잘 고려하여 적절한 Proving scheme을 선택해야합니다. 고려해야 할 특성은 크게 3가지가 있습니다.

Setup:
- Trusted setup per circuit — Circuit 별로 매번 다른 Trusted setup이 필요 (e.g. Groth16)
- Universal Trusted Setup — 한 번의 Trusted setup으로 모든 Circuit에 사용 가능 (e.g. KZG)
- Transparent Setup: Trusted party가 필요하지 않은 Transparent setup (e.g. FRI)
Proving cost: Prover가 Proof를 생성하기 위한 Complexity
Verifying cost: ZK 롤업의 Verify는 보통 온체인에서 이루어지기 때문에 가스비와 직결되는 특성
- Proof size — Circuit의 크기 대비 증명 값의 크기 (e.g. KZG — O(1), IPA — O(log N))
- Verifier time — Verifier proof 검증 로직의 Time complexity (e.g. KZG — O(1), IPA — O(N))

암호시스템에 따른 Proving scheme 종류

Proving scheme들은 사용하는 암호 시스템에 따라 나눌 수 있습니다. 각각의 암호학적 기반에 따라 코스트(Proof size 및 Verifier time)가 달라질 수 있습니다.

Pairing based: 타원곡선의 Bilinear pairing을 이용한 스킴 (e.g. KZG)
Discrete log based: 타원곡선의 이산로그문제(ECDLP)를 이용한 스킴 (e.g. Bulletproofs)
Hash based: 해시를 사용하는 Scheme (e.g. FRI)

또한 이런 암호 시스템에는 프로토콜에 사용되는 파라미터를 생성하기 위한 Setup이 필요합니다. Setup은 크게 세 가지 종류로 나눌 수 있습니다.

Non-universal setup: Trusted party가 필요하고 Circuit마다 고유한 Setup이 매번 필요함.
Universal setup: Trusted party가 필요하지만, 단 한 번의 Setup으로 생성된 파라미터를 모든 Circuit에 대해 매번 사용할 수 있음.
Transparent setup: Trusted party가 필요하지 않은 Setup.

Trusted setup은 파라미터의 보안이 해당 Trusted party에 의존하기 때문에 Transparent setup 보다 보안에 취약하다고 할 수 있고, Non-universal Setup은 Circuit 별로 다른 파라미터를 생성하기 위한 Setup이 매번 필요하기 때문에 Transparent, Universal, Non-universal 순으로 선호되는 경향이 있습니다. 다음은 스킴 별 Complexity와 Setup 방식을 나타낸 표입니다.

Taxonomy of the proving schemes | source: zk-learning.org

이렇게 각 스킴 별로 Complexity와 Setup 방식에 서로 장단점이 다르기 때문에 사용되는 프로토콜의 특성에 맞는 Scheme을 고르는 것이 중요합니다.

3. What is zkEVM?

영지식증명의 Proof를 생성하는 데에는 매우 많은 연산량이 필요한데, Lookup, Recursion 등 ZKP 기술이 진보함에 따라 보다 큰 Circuit에 대한 Proof를 효율적으로 생성할 수 있게 되었습니다. Polygon Hermez v1.0과 같은 1세대 ZK-Rollup의 경우 송금과 같이 특정 기능만 가능한 App-specific Rollup이었는데, 이러한 ZK 기술의 발전은 Universal ZK-Rollup을 구축하기 위한 발판이 되었습니다. Universal ZK-Rollup은 EVM의 연산 유효성을 증명할 수 있는 zkEVM을 사용합니다.

4. The architecture of zkEVM

위에서 언급한 바와 같이 ZK-SNARK는 Constraint들의 집합인 Circuit으로부터 암호 프로토콜을 이용해 Proof를 생성하는 증명 방식입니다. zkEVM에서 Program은 EVM 그 자체라고 할 수 있고 EVM의 로직 유효성에 대한 Constraint들이 zkEVM Circuit이라고 할 수 있습니다.

zkEVM proving data

zkEVM은 모든 트랜젝션들을 올바르게 실행시켰는지, 즉 EVM의 Execution Trace가 모두 올바른지를 증명하는 Circuit입니다. 여기서 증명해야 하는 것들은 EVM의 word가 256비트인지, Opcode의 실행 결과가 모두 올바른지, 스택과 메모리에서 값이 올바르게 읽고 쓰였는지 등 EVM 실행에 대한 모든 validity입니다.

zkEVM Prover가 가지는 input 데이터는 다음과 같습니다:
- Input: 이더리움의 기존 World state t, 새로운 World state t+1, L2 트랜젝션
- Witness: Execution trace

이 데이터들을 이용해 모든 Execution trace의 Codehash, Gas usage, Program Counter와 Stack Pointer에서 Read & Write 데이터, Opcode 등 모든 실행 유효성을 증명합니다.

Example — ADD

위 그림은 ADD에 대한 유효성을 보여주는 예시입니다. zkEVM Circuit에서는 Execution trace의 각 스텝마다 크게 세 가지 측면의 제약 사항들이 있습니다.

Step context
Program Counter 및 Stack Pointer, 가스 사용량 등의 Context에 대한 제약사항입니다. 위 예시에서는 Program Counter와 Stack Pointer가 각각 1씩 증가했는지와 Gas를 3만큼 사용했는지 확인합니다.
Case switch
해당 스텝에서 사용된 Opcode에 대해 확인합니다. 모든 Opcode는 Selector로 존재하고 매 스텝마다 단 한 개의 Opcode만 사용되었는지 확인합니다.
Opcode specific witness
Opcode 마다 별도로 확인해야 하는 사항들에 대한 추가적인 제약 사항들입니다. 위 예시에서는 덧셈 연산에서 발생하는 Carry의 크기가 2¹²⁸인지 확인합니다.

또한 각 스텝의 값들이 STACK과 MEMORY, STORAGE에서 올바르게 읽고 쓰였는지를 판단하기 위해 Lookup argument를 이용합니다. Lookup argument는 Lookup table에서 해당 값이 존재하는지를 증명하는 방식입니다.

zkEVM structure

zkEVM의 구조는 프로젝트마다 모두 상이하지만, 이런 거대한 크기의 Circuit의 증명을 가능하게 한 요인 중 하나는 앞서 언급한 Lookup argument 입니다. Lookup은 Circuit 내부에서 직접 연산을 처리하지 않고 미리 Precompile 되어있는 테이블에서 값이 “존재”하는지만을 증명하는 획기적인 방법입니다. 대부분의 zkEVM들은 기본적으로 EVM trace가 올바른지 증명하기 위한 EVM circuit이 있고 증명하고자 하는 값들이 Precompile 된 여러 Lookup 테이블들이 존재합니다. 가령 이더리움에서 사용하는 해시함수인 Keccak의 경우 Circuit 내부에서 연산하려면 코스트가 커지는데 해시값을 미리 연산한 Keccak table에서 Lookup 하는 방식으로 Constraints를 줄일 수 있습니다. 따라서 zkEVM은 보통 Execution trace를 검증하기 위한 메인 EVM circuit과 Lookup을 위한 Auxiliary circuit들로 구성되어 있습니다.

zkEVM에서 중요한 또 다른 미션은 여러 개의 Proof들을 어떻게 줄이느냐인데, 이는 사용하는 Proving scheme에 따라 다양한 방식이 있습니다. ZCash에서 사용하는 Halo2(IPA)의 경우 Pasta curve를 사용한 Recursion으로 Proof를 accumulation하고, Scroll의 경우 Halo2(KZG)를 사용하는데 Cycling이 불가능한 BN254를 사용하기 때문에 Proof들을 합치기 위한 또 다른 Aggregation circuit이 존재합니다.

5. Optimization

이처럼 zkEVM은 Proof size와 Verification cost가 매우 작다는 ZK-SNARK의 특성을 이용하여 Validity proof를 Layer 1에 제출하고 효과적으로 확장성 문제를 해결할 수 있습니다. 하지만 현재 zkEVM을 사용하는 ZK-Rollup의 가장 큰 문제점은 Proving cost가 매우 크다는 것입니다. 이를 해결하기 위해 현재 여러 방면으로 zkEVM을 최적화하려는 시도가 많아지고 있습니다. 최적화 방식은 크게 세 가지로 나눌 수 있습니다.

이론적 최적화: 기존 Scheme을 이론적으로 최적화 하거나 더 효율적인 Proving scheme을 디자인 하려는 연구. 최근에는 Hyper Nova와 Protostar와 같이 Folding 관련 연구와 MVLookup, Baloo와 같은 새로운 Lookup scheme에 관한 연구가 활발하게 진행되고 있음.
엔지니어링 최적화: 구현 레벨에서 메모리 최적화, 병렬처리 등과 같은 소프트웨어적인 최적화와 더불어 GPU와 FPGA, ASIC과 같은 하드웨어 영역까지 최적화를 시도함.

6. Types of zkEVM

The different types of ZK-EVMs | source: Vitalik’s blog

비탈릭 부테린의 zkEVM의 분류체계는 총 네 가지로 나눌 수 있습니다.

Type 1: 이더리움 컨센서스 레이어까지 모두 호환되는 이더리움 호환 zkEVM. 이더리움의 보안과 모든 인프라를 그대로 상속받을 수 있는 장점이 있는 반면, 그만큼 Proving 코스트가 매우 큼. 현재 대표적으로 Taiko가 Type1 zkEVM을 개발 중임.
Type 2: EVM과 호환되는 EVM 호환 zkEVM. 이더리움의 MPT를 ZK-friendly structure인 ZK-Trie로 변경하는 경우와 같이 ZK를 위한 변경이 있지만 여전히 EVM레벨에서는 동등한 호환성을 가지고 있음. 대표적인 프로젝트로 스크롤이 있음.
Type 3: ZK-unfriendly Opcode나 구조들을 없앤 형태로 이더리움 디앱들이 그대로 온보딩하지 못하고 약간의 수정이 필요한 허들이 존재함.
Type 4: 자체적인 ZK-friendly 언어와 Virtual Machine을 사용하는 경우로 이더리움과 호환이 되지 않지만, 다른 타입에 비해 Proof 생성이 훨씬 빠르다는 장점이 있음. 대표적으로 StarkNet과 zkSync가 있음.

Type 1에서 Type 4로 갈수록 이더리움과의 호환성은 떨어지지만, Proof 생성에 대한 코스트가 줄어든다는 장점이 있습니다. 이더리움과 완전히 호환되는 Type 1 zkEVM 은 아직 상용화되지는 않았지만, Lookup과 Recursion 등으로 연산의 최적화가 충분히 이루어진다면 머지않은 미래에 Type 1 zkEVM을 사용하는 날이 올 것입니다.

7. Conclusion

ZK-Rollup은 아직 미완의 기술이고 가야 할 길이 멀다고 할 수 있습니다. 연산 최적화를 위해 많은 수많은 시도를 하고 있지만 여전히 Proof 생성에 높은 코스트가 요구되고 하드웨어 요구사항도 매우 높다는 문제가 있습니다. 또한 기술의 특성상 진입장벽이 높아 아직 이 분야를 이끌어갈 수 있는 전문가의 절대적인 수도 부족하고 지원도 부족하다는 문제가 있습니다. 그럼에도 불구하고 현재 매우 빠른 속도로 발전 중이고 이더리움의 확장성에 기여할 수 있는 좋은 솔루션 중에 하나임은 분명하다고 할 수 있습니다.