Rollup의 두 가지 검증 상태: 사기 증명과 비상호작용 사기 증명에 대한 자세한 설명

원문 제목：《진정으로 이해하는 Layer2》

원문 저자：web3 탐험가

Layer2의 핵심 목표는 블록체인의 처리 속도를 향상시키는 것입니다. 그 이유는 1층에서 보안성, 처리 속도, 탈중앙화(불가능한 삼각형)를 동시에 만족시킬 수 없기 때문입니다.

L2에는 세 가지 모드가 있습니다: 상태 채널(state channel), 플라즈마(plasma), 롤업(rollup). 세 가지 모두 각자의 결함으로 인해 주인공이 되지 못했으므로, 본문에서는 롤업 메커니즘만 소개하고, 다른 모드는 관심이 있는 분들이 직접 찾아보시기 바랍니다.

1. 롤업

롤업의 핵심 아이디어는 L1에서 거래 과정을 검증할 수 있는 증거를 저장하고, 거래 과정(계산 과정)과 상태 저장을 L2에서 실행하는 것입니다.

거래 과정의 증거란 무엇인가? 우리는 거래 실행 과정이 하나의 상태에서 다른 상태로 전이되는 과정이라는 것을 알고 있습니다. 만약 L1이 거래 전의 상태와 거래 후의 상태, 그리고 이 거래 집합을 알고 있다면, 자연스럽게 이 거래 집합에 해당하는 상태 전이가 올바른지 검증할 수 있습니다.

위 그림과 같이, 발행자는 거래 전 상태 트리의 루트 해시와 거래 후 상태 트리의 루트 해시, 그리고 거래를 L1에 게시합니다. L1 스마트 계약은 거래 전 상태 트리의 루트 해시가 저장된 루트 해시와 일치하는지 확인합니다. 거래 전의 루트 해시가 일치하면 초기 상태가 올바르다는 것을 의미합니다. 그렇다면 이번 거래 과정이 올바른지 어떻게 검증할까요? 가장 안전한 방법은 매번 L1에서 L2의 거래 트리를 다시 실행하여 상태 전이를 수행하는 것이지만, 이렇게 되면 L2의 의미가 사라지고 여전히 불가능한 삼각형의 처리 속도 문제에 직면하게 됩니다.

상태 전이가 올바른지 검증하는 방법은 두 가지 다른 Layer2 롤업 메커니즘을 도출합니다.

첫 번째는 사기 증명(fraud proof)입니다. 즉, 저장된 상태가 올바르다고 기본적으로 믿고, 다른 참여자가 사기 증명 도전을 제기할 때까지 기다립니다. L2가 L1에 게시할 때마다 노드는 일정 금액의 보증금을 지불해야 하며, 사기가 입증되면 이전 상태로 롤백되고 발행자의 보증금은 전액 차감되며 일부는 도전자에게, 일부는 직접 소각됩니다. 사기를 입증하는 방법은 L1과의 상호작용 정도에 따라 상호작용 사기 증명과 비상호작용 사기 증명으로 나뉘며, 아래에서 자세히 설명하겠습니다.

두 번째는 제로 지식 증명(zero-knowledge proof)입니다. 매번 상태를 저장할 때 증명을 제공해야 하며, 이 증명은 L1에서 검증됩니다. 만약 검증된 루트 해시 값이 올바르다면, 발행자의 게시가 정확하다는 것을 나타냅니다. 여기서 증명은 제로 지식 증명 관련 연구를 사용합니다.

• 사기 증명

방금 위에서 언급한 사기 증명은 기본적으로 믿는 원칙에 따라 진행됩니다. 도전이 없을 때는 과정이 비교적 간단합니다. 즉, 상태 트리의 루트 해시 거래 정보를 L1에 저장하는 것입니다. 핵심은 도전자가 도전을 시작할 때, 거래 전 상태 트리의 루트 해시가 이 거래 집합을 통해 새로운 상태 루트 해시로 변할 수 있음을 증명하는 것입니다. 여기에는 두 가지 접근 방식이 있습니다.

1. 비상호작용 사기 증명: 즉, L1에서 이 거래 집합을 다시 실행하여 실행 후의 상태 트리 루트 해시 값과 전달된 루트가 일치하는지 확인합니다.

2. 상호작용 사기 증명: 도전자와 발행자가 L2에서 여러 차례 도전을 진행하며, 최종적으로 도전자가 어떤 명령이 사기성인지 특정합니다. L1이 이를 판별합니다. L1은 논란이 있는 최소 명령만 실행하면 됩니다.

• 비상호작용 사기 증명

우리는 Optimism을 예로 들어 상호작용 사기를 설명하겠습니다.

사기 증명 과정 분석:

비상호작용 사기 증명은 구현이 비교적 간단합니다. L2에서 실행된 거래를 L1에서 다시 완전히 실행하여 상태 루트의 해시가 일치하는지 판단하여 사기 행위를 확인합니다.

위 그림과 같이, 발행자는 정보를 L1에 게시하며 거래 정보와 새로운 전체 루트 해시를 포함합니다. L1의 스마트 계약은 이를 수신한 후 상태를 새로운 루트 해시로 변경합니다. 이때 도전자가 도전을 제기하며, 도전자는 이전 루트 해시와 일치하는 머클 상태 트리를 제공해야 합니다. L1 스마트 계약은 이전 상태 트리를 통해 전체 거래 프로세스를 실행하여 루트 해시와 발행자가 제공한 새로운 루트 해시를 비교합니다. 일치하지 않으면 사기 행위가 있음을 나타냅니다.

다시 실행하면 하나의 문제에 직면하게 되는데, 블록 관련 속성이 실행 환경에 따라 달라질 수 있습니다.

위 그림과 같이 block.timestamp는 현재 블록의 타임스탬프를 가져오지만, 계약 실행 환경이 다르기 때문에 얻는 타임스탬프는 대개 다를 것입니다. Optimism이 이 문제를 해결하기 위해 OVM을 어떻게 설계했는지 살펴보겠습니다.

OVM

L2와 L1에서 스마트 계약을 실행할 때 환경이 일치하지 않는 문제를 해결하기 위해, Optimism은 가상화 기술(실제로는 캡슐화 방법을 사용하여)을 사용하여 스마트 계약이 직접 일부 상태를 OVM 캡슐화 후 호출하도록 합니다.

위의 예에서 block.timestamp를 직접 호출할 수 없으며, 대신 OVM 캡슐화된 하나의 메서드인 ovm_getTimestamp(실제 이름은 임의로 지정됨)를 호출합니다.

상호작용 사기 증명

우리는 Arbitrum을 예로 들어 상호작용 사기를 설명하겠습니다.

Arbitrum 사기 증명 과정 분석:

사실 이전에 스마트 계약 문서의 시작 부분에서 스마트 계약 실행 과정이 상태 변화를 추진하는 과정이라고 언급한 바 있습니다. 우리는 상태 기계의 개념을 다시 살펴보겠습니다.

위 그림과 같이, L1의 상태 트리든 L2의 상태 트리든 모두 일련의 거래(스마트 계약의 실행도 하나의 거래 호출입니다)로 상태 전환을 추진합니다. 스마트 계약 덕분에 거래는 더 작은 단계 명령으로 나눌 수 있습니다. 그래서 아래와 같은 형태가 됩니다.

우리의 문제는 상태 트리가 상태 A에서 N개의 명령을 거쳐 상태 B로 변했음을 증명하는 것입니다. 그렇다면 이 증명 과정은 분해 가능할까요? 우리는 분할 정복 방식을 사용하여 이분법을 생각할 수 있습니다. 하나의 큰 문제를 두 개의 작은 문제로 나누면, 문제는 상태 A가 앞의 N/2 개 명령을 거쳐 상태 X로 변하고, 상태 X가 뒤의 N/2 개 명령을 거쳐 상태 B로 변하는 것을 증명하는 것이 됩니다. 점진적으로 이분화하여 최종적으로 문제가 있는 명령을 찾아 L1에서 실행하여 검증하면 됩니다.

전체 실행 과정을 완전하게 설명해 보겠습니다. 가정해 보겠습니다. X는 발행자가 상태 A에서 N개의 명령을 거쳐 상태 B로 전이하는 것이고, Y는 도전자입니다.

Y는 X에게 도전을 제기하며 N/2 개 명령을 거친 상태를 제시하라고 요구합니다. X가 상태를 제공하면 Y는 스스로 검증합니다. 검증이 올바르면 앞의 N/2 개 명령 실행에는 문제가 없고, 문제는 뒤의 N/2 개에 있습니다. 검증이 잘못되면 앞의 N/2 개 명령 실행에 문제가 있다는 것을 의미합니다. Y는 계속해서 X에게 문제가 있는 명령 구간 N/2의 상태를 질문하며, 반복하여 문제가 있는 명령을 찾습니다(여기서 명령이 문제가 있는 것이 아니라, 실행 명령 전의 상태가 실행 명령 후의 상태로 전환될 수 없음을 의미합니다).

실제 응용에서 Arbitrum은 이분법을 사용하지 않고 K분할 방식을 사용합니다. 즉, 매번 N개의 명령을 N/K 그룹으로 나누어 사기 명령을 찾습니다. 효율성이 더 높습니다.

AVM

Arbitrum이 AVM을 설계한 핵심 포인트는 EVM과 완전히 호환되는 실행 논리를 지원할 뿐만 아니라 상호작용 사기 증명의 증명 논리도 지원해야 한다는 것입니다.

증명 과정에서 현재 프로그램 카운터의 명령의 정확성을 보장해야 합니다. 이때 블록체인과 유사한 방식을 채택하여, PC(현재 프로그램 카운터 위치)는 작업 코드뿐만 아니라 PC+1 위치의 해시 값도 저장합니다. 이렇게 하면 명령 실행 과정에서 각 명령이 올바른지 검증할 수 있습니다.

위의 비교에서 볼 수 있듯이, 상호작용 사기 증명은 구현 난이도가 높을 뿐만 아니라 주요 특성이 비상호작용 사기 증명보다 우수합니다. 대표적인 비상호작용 사기 증명 사용자인 Optimism도 상호작용 사기 증명으로 전환할 준비를 하고 있습니다. 미래에는 상호작용 사기 증명이 사기 증명의 주류가 될 것으로 예상됩니다.

사기 증명은 대개 긴 인출 주기라는 문제를 가지고 있습니다. 이는 도전자가 도전을 제기할 충분한 시간이 필요하기 때문입니다. 암호학의 최신 연구 결과 덕분에 zk-rollup이 이 문제를 해결할 것입니다.

2. ZK-Rollup

• 제로 지식 증명의 의미

제로 지식은 참여자가 문제의 결과를 해결하였지만 검증자에게 결과를 알리지 않은 상태에서 검증자가 참여자가 문제를 해결한 결과가 올바르다고 믿게 만드는 것입니다. 우리는 두 가지 유명한 예를 들어보겠습니다.

• 유명한 알리바바

아주 오래 전, 보물이 숨겨진 동굴이 있었습니다. 알리바바는 동굴의 돌문을 여는 주문을 알고 있었기 때문에 강도에게 붙잡혔습니다. 만약 주문을 말하면 이용 가치를 잃고 죽게 됩니다. 만약 말하지 않으면 강도가 그를 죽일 것입니다.
두 가지 선택지에 처한 알리바바는 좋은 방법을 생각해냈습니다. 그는 강도에게 무작위로 지시했습니다. "너희는 나와 한 화살 거리만큼 떨어져서 활로 나를 겨누고, 오른손을 들면 나는 주문을 외워서 돌문을 열고, 왼손을 들면 나는 주문을 외워서 돌문을 닫겠다. 만약 내가 이를 수행하지 못하거나 도망칠 기회를 노린다면, 너희는 나를 활로 쏘아 죽여라."
여러 번 반복한 후, 강도는 주문을 알 수 없지만 알리바바가 주문을 가지고 있다는 사실을 믿을 수 있게 되었습니다. 알리바바는 목숨을 구했습니다.

• 스도쿠 문제

9x9 스도쿠가 있습니다. A는 이미 답을 찾았고, A는 답을 공개하지 않고 B가 A가 성공적으로 해결했음을 믿게 만들고 싶습니다.

해결 방법은 B가 무작위로 1행 또는 1열을 선택하게 하고, A는 이 행 또는 열을 추출하여 섞어서 B에게 보여주는 것입니다. 1에서 9까지 포함되어 있으며, 여러 번 반복하면 B는 A가 올바른 답을 얻었다고 믿게 됩니다.

• ZK-SNARK가 문제를 해결하는 방법

현재 ZK 메커니즘 중 가장 성숙한 것은 zk-SNARK이므로, 이후 zk 알고리즘은 모두 zk-SNARK를 예로 들 것입니다.

ZK-SNARK 작업 흐름은 두 단계로 나뉩니다:

1. 문제를 회로로 변환한 다음 다항식으로 변환하여 실제 제로 지식 증명 문제를 수학적 제로 지식 증명 문제로 변환합니다.

2. 이 다항식 제로 지식 증명을 검증하여 무작위로 몇 개의 검사점을 제공하면 조건에 맞는 해를 얻을 수 있습니다. 그러면 검증이 성공합니다.

zk 증명에 대해서는 나중에 별도의 글을 통해 소개할 예정입니다. zk 증명은 이더리움 확장뿐만 아니라 개인 정보 보호 분야에서도 많이 활용될 것입니다. 예를 들어, 최근 인기 있는 DID와 같은 분야입니다.

우리는 starkware를 예로 들어 zk-rollup의 메커니즘을 소개하겠습니다. starkware의 흐름도는 아래와 같습니다.

발행자가 거래를 L1에 게시할 때, 거래와 L2의 상태를 패키징하여 증명 생성 서비스에 전달해야 합니다. 증명 생성 서비스는 대량의 계산을 통해 이번 게시의 증명을 생성합니다. 증명 서비스는 증명을 L1의 검증 서비스에 전송합니다. 동시에 발행자는 상태 루트 해시 값을 L1에 제출합니다. L1은 루트 해시 값을 수신하면 L1의 검증 서비스에 문의하여, 검증 서비스는 증명에 따라 루트 해시 값이 올바른지 검증합니다. 만약 올바르다면 L1은 상태 루트를 새로운 해시 값으로 전환합니다.

이 과정에서 상태 트리의 루트 해시를 검증하기 위해서는 이전의 전체 상태 트리를 실행하여 이번 게시의 모든 거래를 수행하여 새로운 거래 트리를 얻고, 최종적으로 발행자가 제공한 루트 해시 값과 새로운 해시 값을 비교하여 게시가 합법적인지를 판단해야 합니다. zk 증명을 도입함으로써 우리는 구체적인 상태와 거래를 알 필요 없이 해시 값이 올바른지를 판단할 수 있습니다. 이것이 zk 증명이 이더리움 확장에서의 응용입니다.

• ZK 증명의 발전

SNARK(제로 지식 간결 비상호작용 지식 증명)과 STARK(제로 지식 확장 투명 증명)의 비교:

SNARK에 비해 STARK는 아직 초기 단계에 있지만, 보안성과 양자 저항성에서 좋은 성능을 보여 향후 더 큰 발전을 이룰 것으로 기대됩니다.

3. 결론

본 문서에서는 주로 롤업이라는 주류 Layer2 기술을 소개했습니다. 롤업에서는 L2가 제출한 상태가 올바른지를 검증하는 시점에 따라 사기 증명과 zk 롤업으로 나뉘며, 사기 증명은 도전자가 발행자와 상호작용할 필요가 있는지에 따라 비상호작용 사기 증명과 상호작용 사기 증명으로 나뉩니다. 비교 결과, 운영 비용이나 EVM 호환성 면에서 상호작용 사기 증명이 우위를 점하고 있습니다. 그리고 zk라는 암호학의 최신 연구 결과는 우리에게 새로운 방향을 제시하며, zk 롤업이 발행자의 게시를 더 빠르게 검증할 수 있게 합니다. 또한 zk는 개인 정보 보호 등 다른 방향에도 새로운 가능성을 제공합니다.