규범적 명세(Normative spec): Cannon 결함 증명 가상 머신은(는) 멀티스레드 Cannon 결함 증명 VM 명세에 규범적으로 정의되어 있습니다. 이 페이지는 offchain 구현을 설명하며, 명세 내용을 다시 서술하지 않습니다.
- Onchain
MIPS64.sol: 단일 MIPS 명령어의 실행을 검증하는 EVM 구현입니다. - Offchain
mipsevm: onchain에서 검증할 수 있도록 모든 MIPS 명령어에 대한 증명을 생성하는 Go 구현입니다.
이전 세대의 Cannon은 Go로 작성된 결함 증명 프로그램
op-program을 실행했습니다. 처음에는 32비트 MIPS32 명령어로 컴파일되어 onchain에서
MIPS.sol로 검증되었고, 이후에는 MIPS64로 컴파일되어 이 페이지에서 설명하는 64비트 Cannon에서 실행되었습니다. 이러한 op-program 구성은 레거시
CANNON(game type 0) 및 PERMISSIONED_CANNON(game type 1) 분쟁 게임의 기반이 되며, op-program은 이후
지원 종료되었습니다(op-geth 및 op-program 지원 종료 참고). 현재 분쟁 게임은
cannon-kona(game type 8) 구성, 즉 64비트 Cannon에서 실행되는 kona-client를 사용합니다.
MIPS.sol 레퍼런스는 폐기된 32비트 onchain 컨트랙트를 설명합니다.MIPS64.sol의 차이점도 살펴봅니다.
편의상 이 문서에서 Cannon이라고 할 때는 offchain 구현을 의미합니다.
제어 흐름
op-program이라고 표시된 부분은 현재 그 역할을 하는 kona-client로 읽으십시오. 다이어그램에서
Cannon이 op-challenger 및 결함 증명 프로그램과 상호작용하는 것을 볼 수 있습니다. 그러나 이 다이어그램은
op-challenger <> Cannon, 그리고 kona-client <> Cannon 간의 관계를 단순화한 것입니다. 일반적으로 Cannon은 진행 중인 결함 분쟁이 bisection 게임의
실행 트레이스(execution trace) 부분에 도달할 때까지 실행되지 않습니다. 이는 진행 중인 결함 분쟁 게임의 참여자들이 의견이 일치하지 않는
단일 L2 블록 상태 전이에 도달할 때까지 발생하지 않습니다.
op-challenger <> Cannon
진행 중인 결함 분쟁 게임이 L2 블록 상태 전이를 공격/방어하는 깊이보다 더 아래로 내려가면, op-challenger가 Cannon을 실행하여 FPVM 내에서 MIPS 명령어 처리를 시작합니다. MIPS 명령어를 처리하는 과정에서 Cannon은 상태 witness 해시를 생성하며, 이는 FPVM 내에서 수행된 MIPS 명령어 연산 결과에 대한 커밋먼트입니다. 이제 bisection 게임에서 op-challenger는 단일 MIPS 명령어가 진행 중인 분쟁 참여자 간 불일치의 근원으로 식별될 때까지 생성된 해시를 제공합니다. 그러면 Cannon은 해당 MIPS 명령어를 onchain에서 실행하는 데 필요한 모든 정보를 담은 witness 증명을 생성합니다. 이 단일 MIPS 명령어를 onchain의MIPS64.sol에서 실행하여 올바른 사후 상태(post state)를 확정적으로 증명하며, 이 결과는 결함
분쟁 게임을 해결하는 데 사용됩니다.
kona-client <> Cannon
실행 트레이스 bisection이 시작되고 Cannon이 실행되면, Executable and Linkable Format(ELF) 바이너리가 Cannon 내에 로드되어 실행됩니다. Cannon 내부에는mips64 컴파일러 타깃이 요구하는 빅 엔디언 64비트 MIPS 명령어 세트(MIPS64 Release 1)를 처리하도록 만들어진
mipsevm이 있습니다. ELF 파일에는 MIPS 명령어가 담겨 있으며, MIPS 명령어로 컴파일된 코드가 바로 kona-client입니다.
kona-client는 mips64-unknown-none 타깃으로 컴파일되어 Cannon FPVM 내에서 실행되는 Rust 코드입니다. kona-client는 네이티브로 실행되든
Cannon에서 실행되든, 동반 프로그램인 kona-host가 가져온 데이터로부터 L2의 상태를 도출합니다. kona-client는
동일한 입력이 동일한 출력뿐만 아니라 동일한 실행 트레이스를 생성하도록 만들어졌습니다. 따라서 결함 분쟁 게임의 모든 참여자는
kona-client를 실행하여, 동일한 L2 output root 상태 전이가 주어지면 동일한 실행 트레이스를 생성할 수 있습니다. 이는 결과적으로 onchain에서
실행될 정확히 동일한 MIPS 명령어에 대해 동일한 witness 증명을 생성합니다.
op-program이 지원 종료되기 전에는 레거시 game type에서 동일한 역할을 수행했습니다. 즉, 동일한 결정론적 특성을 가진 채 MIPS 명령어로
컴파일된 Go 코드였습니다(초기 세대에서는 32비트, 이후에는 64비트). 현재는 kona 변형만 유지 관리됩니다.
Offchain Cannon 컴포넌트 개요
이제 Cannon을 구성하는 각 주요 컴포넌트를 살펴보겠습니다. 컴포넌트는 Cannon을 위해 수행하는 기능별로 그룹화되어 있으며, 하나 이상의 Go 파일과 대응될 수 있습니다. 간결성을 위해 각 Go 파일은 상위 수준에서 설명하며, 가장 중요한 기능/고려 사항을 강조합니다.
mipsevm 상태와 메모리
앞서 언급했듯이 mipsevm은 64비트이므로 주소 지정 가능한 전체 주소 범위는 [0, 2^64-1]입니다. 메모리 레이아웃은
일반적인 모놀리식 메모리 구조를 사용하며, VM은 마치 물리 메모리와 직접 상호작용하는 것처럼 동작합니다.
mipsevm의 경우 Go 런타임 내에 메모리를 보관할 수 있으므로 메모리가 어떻게 저장되는지는 중요하지 않습니다.
이런 방식으로 메모리 표현 방식은 VM 자체로부터 추상화됩니다. 그러나 onchain에서 MIPS 명령어를 실행할 때 메모리의 작은 부분만 필요하도록
메모리를 표현하는 것이 중요합니다. 비용 때문에 전체 64비트 메모리 공간을 onchain에서 표현하는 것은 불가능하기 때문입니다.
따라서 메모리는 바이너리 Merkle 트리 자료 구조에 저장되며, 구현은
memory.go와
page.go에 나뉘어 있습니다.
트리는 59단계의 고정 깊이를 가지며, 각 리프 값은 32바이트입니다. 이는 전체 64비트 주소 공간을 포괄합니다: 2**59 * 32 = 2**64.
각 리프에는 트리의 해당 부분에 대한 메모리가 담겨 있습니다.
memory.go는 메모리 노드와 페이지를 추적하는 자료 구조인 Memory를 정의합니다. 메모리 노드는 메모리 바이너리 Merkle 트리 내
서브트리의 계산된 Merkle root를 보유하며, 노드의 ‘위치’는 generalized index로 결정됩니다.
Merkle root에 대해 계산되는 인덱스는
generalized Merkle tree index 명세를 따릅니다.
page.go는 이름에서 알 수 있듯이 메모리 페이지를 정의합니다. 각 Page는 4096바이트이며, 이는 VM 내부에서 실행되는 프로그램의
최소 페이지 할당 크기로도 지정됩니다. Page는 메모리 바이너리 Merkle 트리의 가장 낮은 깊이를 나타내며, page.go는
memory.go와 비슷한 역할을 수행하여 트리의 각 레벨에 대한 Merkle root를 계산합니다.
이 메모리 트리의 노드는 out = keccak256(left ++ right)로 결합됩니다. 여기서 ++는 연결(concatenation)이며,
left와 right는 각 서브트리의 32바이트 출력 또는 리프 값 자체입니다.
개별 리프 노드는 해시되지 않습니다.
memory.go와 page.go 모두에는 계산 비용이 큰 Merkle root 계산을 줄이기 위한 몇 가지 최적화가 있습니다.
그중 하나는 0으로 채워진 메모리 영역의 Merkle root를 각 깊이별로 계산해 두는 것입니다. 이렇게 하면 전체가 0으로 채워진
서브트리의 root를 실제로 전체 서브트리를 만들지 않고도 계산할 수 있으므로 트리가 효율적으로 할당됩니다:
zero_hash[d] = hash(zero_hash[d-1], zero_hash[d-1]), 기본 사례인 zero_hash[0] == bytes32(0)에 도달할 때까지 반복합니다.
따라서 처음에 0으로 채워진 Merkle root를 미리 계산해 두면 사용되지 않는 메모리 영역을 캐시할 수 있습니다. 또한 0이 아닌 Merkle root도
memory.go와 page.go 모두에서 캐시되며, 해당 Merkle root가 포괄하는 메모리 영역에 쓰기가 발생하지 않는 한 사용됩니다.
쓰기가 발생하면 캐시가 무효화되어 전체 서브트리에 대해 Merkle root를 다시 계산해야 합니다. memory.go에만 있는
또 다른 최적화는 마지막으로 사용된 두 페이지를 캐시하는 것입니다. mipsevm은 일반적으로 한 페이지에서 명령어를 읽으면서
다른 페이지에 대해 load와 store를 수행하므로 두 페이지를 캐시합니다.
또 다른 중요한 구현 세부 사항은 mipsevm의 엔디언(워드 내 바이트 순서)이 빅 엔디언(Big-Endian)이라는 점입니다.
워드 크기의 읽기와 쓰기는 빅 엔디언 바이트 순서 헬퍼를 거치므로(
arch64.go 참고), 내부 mipsevm은
Cannon을 실행하는 머신의 엔디언과 관계없이 항상 빅 엔디언 워드를 처리합니다.
엔디언은 EVM 자체가 빅 엔디언인 onchain MIPS64.sol에서도 중요한 요소입니다. 따라서 MIPS64.sol은
엔디언 변환을 수행할 필요가 없으며 모든 데이터가 빅 엔디언 순서를 사용한다고 가정할 수 있습니다. 이는 스마트 컨트랙트 자체의 복잡성을 줄여 줍니다.
마지막 주요 컴포넌트는 state.go에 있습니다.
state.go의 State struct는 mipsevm에 필요한 모든 실행 상태를 보유합니다.
저장되는 정보는 MIPS64.sol이 다루는 packed VM 실행 상태와 거의 동일합니다
(Cannon FPVM 명세 참고). 주요 차이점은 다음과 같습니다.
- 메모리 Merkle root만 저장하는 대신, 전체 64비트 메모리 공간의 바이너리 Merkle 트리 표현을 위한
Memorystruct 포인터가 있습니다. - 선택적인
LastHintbytes 변수가 있으며, 이를 사용해 Pre-image 힌트를 전달하여 여러 이전 Pre-image를 로드하지 않아도 되도록 할 수 있습니다.
State struct는 스레드 상태 스택과 현재 활성 스레드도 추적하며, packed
onchain 상태도 이러한 스레드 스택에 커밋합니다.
Cannon은 레거시 32비트 VM과 64비트 멀티스레드 VM을 모두 포괄하는 여러 버전별 상태 형식을
지원합니다. kona-client prestate는 최신 64비트 멀티스레드 버전으로 빌드됩니다.
witness 증명 생성
Cannon은 분쟁 게임에서 두 가지 주요 작업을 처리합니다. 실행 트레이스 bisection 게임 중에 op-challenger가 게시할 상태 witness 해시를 생성하는 것과, 결함 분쟁 게임에서 단일 MIPS 명령어가 불일치의 근원으로 도달했을 때 witness 증명을 생성하는 것입니다. 앞서 언급했듯이 witness 증명에는MIPS64.sol이 onchain에서 동일한 명령어를 실행하고
결함 분쟁 게임을 해결하는 데 사용될 사후 상태를 도출하는 데 필요한 모든 정보가 담겨 있습니다. MIPS64.sol이 실행한 명령어의 사후 상태는
mipsevm이 생성한 사후 상태와 정확히 동일해야 합니다.
cannon/cmd에 있는 최상위 witness.go가
witness 증명 생성을 시작합니다. cannon/mipsevm에 있는 내부
witness.go는 특정 MIPS 명령어에 대한
모든 관련 정보를 보유하는 struct를 정의하며, 이 정보는 MIPS64.sol calldata로 인코딩됩니다.
또한 MIPS 명령어에 Pre-image가 필요한 경우,
witness.go는 관련 Pre-image 키와 오프셋을 op-challenger에 전달하여 이를 onchain의
PreimageOracle.sol에 게시할 수 있도록 합니다.
witness 증명 생성에 관한 중요한 참고 사항: onchain에서 실행될 명령어에 관한 모든 관련 정보는 MIPS 명령어 처리로 인해
mipsevm 실행 상태가 변경되기 전에 생성되어야 합니다. 그렇지 않고 offchain에서 명령어를 실행한 후에
witness 증명을 생성하면, 인코딩되는 상태는 사후 상태가 됩니다.
ELF 파일 로드
bisection 게임의 실행 트레이스 부분이 시작되면, MIPS 명령어로 컴파일된 kona-client가 담긴 ELF 파일이 Cannon 내에서 실행됩니다. 그러나 kona-client를 실행할 수 있도록 Cannon에 넣으려면 바이너리 로더가 필요합니다. 바이너리 로더는load_elf.go와
load.go로 구성됩니다. load_elf.go는
최상위 인수를 파싱하고, Cannon이 실행할 수 있도록 ELF 바이너리를 읽어 로드합니다.
load.go는 실제로 ELF 파일의 헤더를 파싱하는 역할을 하며, 헤더에는 여러 정보와 함께 파일 내에 어떤 프로그램 세그먼트가
존재하고 메모리의 어디에 위치하는지가 지정되어 있습니다. 로더는 이 정보를 사용하여 mipsevm의 실행 상태를 인스턴스화하고
각 세그먼트를 메모리의 예상 위치에 로드합니다. 실행 상태를 인스턴스화하는 과정에서
load.go는 PC와 초기 힙 위치의 값을 설정하고,
patch.go는 프로그램 메모리 상단 근처에 초기 스택
프레임을 설정하며, 여기에는 스택 포인터 위치 위쪽에 프로그램 런타임이 요구하는 인수가 포함됩니다.
ELF 파일을 Cannon에 로드하는 동안 metadata.go가
ELF 파일에 저장된 모든 심볼을 파싱하는 데 사용됩니다. 어떤 ELF 심볼이 존재하며 메모리의 어느 영역에 위치하는지 파악하는 것은
현재 PC가 특정 함수 내에서 실행 중인지 파악하는 것과 같은 다른 기능에 중요합니다.
onchain 및 offchain mipsevm 구현 모두에서 핵심적인 설계 결정은 어느 구현도
커널에 접근할 수 없다는 것입니다. 이는 주로 EVM 자체의 제약 때문이며, offchain Cannon
구현은 onchain 대응 구현과 기능이 정확히 일치해야 하므로 Cannon 내에서도 커널 접근이 불가능합니다. 이는 VM이
커널이 수행하는 동작을 1:1로 재현할 수 없다는 의미이며, 주로 시스템 콜(syscall)에 영향을 미칩니다.
대신 syscall 명령어는 Linux 커널의 최소한의 하위 집합만 시뮬레이션합니다. 즉, 메모리를 할당하고, 특정 파일 디스크립터에서 읽고 쓰고,
종료하기에 충분한 정도입니다. 그 외에 메모리 관리 및 시그널 처리 콜과 같이 정의된 일련의 syscall은
no-op으로 구현되며, 지원되는 집합 밖의 syscall은 지원되지 않고 VM을 중단시킵니다. Cannon 내에서 실행되는 프로그램은
이러한 최소 환경을 견딜 수 있도록 빌드되어야 합니다.
명령어 스테핑
MIPS 바이너리가 Cannon에 로드되면 MIPS 명령어를 한 번에 하나씩 실행할 수 있습니다.run.go에는 MIPS 명령어를 단계별로 실행하는
최상위 코드가 담겨 있습니다. 또한 run.go는 각 MIPS 명령어 전에 별도의 작업을 수행해야 하는지 판단합니다.
수행할 작업은 사용자가 구성하며, 정보 로깅, 특정 명령어에서 중지,
특정 명령어에서 스냅샷 생성, 또는 VM에 witness 증명 생성을 신호하는 것 등이 포함될 수 있습니다.
수행할 작업은 matcher.go에서 인스턴스화되고 확인되며,
matcher.go는 구성된 스텝 패턴(특정 스텝 또는 스텝 간격)이 일치할 때 트리거되는 match 함수를 생성합니다.
run.go 내에서 StepFn은 실행할 MIPS 명령어를 시작하는 래퍼입니다.
instrumented.go는 각 MIPS 명령어마다 시작되는
인터페이스로 Step을 구현합니다. 또한 instrumented.go는 witness 증명에 대한 정보와
Pre-image 정보(MIPS 명령어에 필요한 경우)의 인코딩을 처리합니다.
mips.go
mips.go는
mipsevm/exec의 공유 명령어 처리 코드와 함께 필요한 모든 MIPS
명령어를 구현하며, 현재 실행 중인 명령어에 대한 추가 메모리 접근도 추적합니다.
이는 load, store, 특정 syscall과 같이 두 번째 메모리 증명을 사용하는 명령어에서 해당 증명이 올바르게 인코딩되도록 하는 데 중요합니다.
지원되는 명령어의 전체 목록은
mipsevm README에서 확인할 수 있습니다.
mips.go vs. MIPS64.sol
offchain mips.go와 onchain Cannon MIPS64.sol은 MIPS64 Release 1 명령어를 실행할 때 비슷하게 동작합니다.
실제로 둘은 동일한 명령어, 메모리, 레지스터 상태가 주어지면 정확히 동일한 결과를 생성해야 합니다.
따라서 onchain과 offchain에서 동일한 명령어를 재현하려면 witness 데이터가 필수적입니다.
그러나 둘 사이에는 차이점이 있습니다.
- onchain의
MIPS64.sol에서는 단일 명령어가 실행되는 반면, offchainmips.go는 분쟁 대상 L2 상태의 모든 상태 전이에 대해 모든 MIPS 명령어를 실행합니다. mipsevm은 전체 64비트 모놀리식 메모리 공간을 포함하고, MIPS 명령어의 결과에 따라 메모리 상태를 유지 관리하며, 메모리 바이너리 Merkle 트리, Merkle root, 메모리 Merkle 증명을 생성합니다.MIPS64.sol은 대부분 stateless이며 전체 메모리 공간을 유지 관리하지 않습니다. 대신 메모리 Merkle root와 최대 두 개의 메모리 Merkle 증명만 필요합니다. 하나는 명령어용이고, 다른 하나는 load, store 또는 특정 syscall 명령어가 있을 경우를 위한 것입니다.MIPS64.sol과 달리mips.go는 Pre-image 서버에서 Pre-image를 읽고, 선택적으로 힌트를 Pre-image 서버에 쓰는 역할을 합니다.
PreimageOracle 상호작용
앞서 언급했듯이 Cannon은MIPS64.sol에서 명령어를 실행하는 데 필요할 수 있는 모든 상태를 설정하는 역할을 합니다.
또한 Cannon은 Pre-image 서버와 상호작용하고, MIPS64.sol에서 실행될 명령어에 필요한 경우 op-challenger가
onchain PreimageOracle.sol에 Pre-image를 제공하도록 지시하는 역할도 합니다.
Pre-image 서버는 kona-host입니다. run.go는 이를 하위 프로세스로 실행하며(host 명령은 -- 구분자 뒤에
cannon run으로 전달됨), kona-host는 실행 중에 kona-client가 요청하는 체인 데이터를 제공합니다.
mips.go는 MIPS syscall 명령어의 일부로 Pre-image를 읽을 때 Pre-image 서버와 통신하며,
Pre-image 서버에 힌트를 전달할 때도 통신합니다.
OP Stack 결함 증명 Pre-image Oracle 명세는
pre-image 통신을 위한 ABI를 정의합니다.
이 ABI는 VM이 특정 파일 디스크립터에 대한 read/write syscall을 가로채는 방식으로 구현됩니다. 자세한 내용은 Cannon VM 명세를 참고하십시오.
oracle은 pre-image를 최대 32바이트까지 제공하지만,
Cannon은 메모리 작업을 64비트 load/store와 통일하기 위해 한 번에 최대 8바이트만 읽을 수 있다는 점에 유의하십시오.