리뷰와 피드백을 주신 Jochem Brouwer, Sina Mahmoodi, Thomas Thiery, Rahul Guha, Carlos Perez, Guillaume Ballet에게 감사드립니다.

요약:

• 이 게시물에서는 L1 스나키피케이션과 관련된 잘 알려진 최악의 시나리오인 바이트코드 청킹에 대한 솔루션에 대한 광범위한 관점을 제공합니다.
• 다가오는 L1 확장 및 기타 프로토콜 변경은 이러한 최악의 시나리오를 더욱 악화시킵니다. 이러한 변화는 지속 되어야 하지만, 향후 SNARKification 과제를 해결하는 방법을 고민하는 것이 중요합니다.
• 시간이 흐르고 이더리움이 발전함에 따라, 핵심 개발자와 연구자들 사이에서 중대한 프로토콜 변경과 관련된 위험에 대한 의견이 점점 더 다양해지고 있으므로 모든 잠재적 솔루션의 미묘한 차이를 심층적으로 탐구하는 것이 중요합니다.
• 이 문서의 목적은 다음과 같습니다.
  • 이 문제에 대한 잠재적 해결책을 조사합니다. 가장 간단한 것부터 가장 복잡한 것까지 다양하며, 각 해결책의 뚜렷한 상충관계를 강조합니다.
  • 인식을 높여 더 많은 사람들이 이를 고려하고 더 나은 해결책을 제안하도록 장려합니다.
• 이는 즉각적인 조치를 필요로 하지 않습니다(예: "글램스터담"). 겉보기에 간단한 해결책이라도 최선의 전진 방향을 결정하기 위해서는 철저한 분석이 필요합니다.

이 문서에서는 블록 증명의 최악의 시나리오, 즉 실행 추적에 계약 바이트코드가 필요한 상황에 대한 해결책을 살펴봅니다. 이 문제는 오랫동안 지속되어 왔으며, 다양한 해결책이 제시되어 왔습니다. 시간이 지남에 따라 프로토콜 변경은 UX 영향 및 위험 측면에서 평가 방식이 달라지므로, 상충 관계에 대한 보다 자세한 이해가 필요합니다.

배경 및 동기

이 부분은 이 주제에 익숙하지 않은 독자를 위한 소개 부분입니다. 이미 잘 알고 계시다면 건너뛰셔도 됩니다.

블록 실행 증명이 필요한 이유는 무엇인가요?

이더리움에 더 많은 실행 처리량이 필요한 이유에 대한 근거는 Vitalik의 최근 게시물 에서 찾을 수 있습니다. 가스 한도를 높이면 블록 검증 부하가 선형적으로 증가하여 증명자의 연산 및 저장 리소스가 더 많이 필요하게 되는데, 이는 탈중앙화 및 무신뢰성과 같은 이더리움의 핵심 가치와 상충됩니다.

실행 증명은 이 관계를 선형에서 준선형으로 바꾸어, 블록 제안자에게 작업 부하를 전가함으로써 증명자에게 영향을 미치지 않고 가스 한도를 더 안전하게 증가시킬 수 있도록 합니다. 이는 더 안전한 실행 처리량 증가를 향한 중요한 진전이지만, 상태 증가와 같은 모든 확장 문제를 해결하지는 못합니다.

블록 증명 하드웨어 및 효율성 증명

블록 증명은 블록 생성자에게 작업을 분산시키지만, 증명자의 최소 하드웨어 요구 사항에는 한계가 있습니다. 블록 증명에는 N개 중 1개라는 가정이 있습니다(정직한 증명자 한 명이 Liveness 와 검열 저항성을 보장합니다). 모든 N개 중 1개라는 가정과 마찬가지로, 이더리움 커뮤니티는 언젠가 이 가정을 수용하기 위해 얼마나 많은 정직하고 독립적인 증명자가 필요한지 결정해야 합니다.

이 하드웨어 예산은 네트워크가 설정할 수 있는 최대 가스 한도를 제한하므로, 가스 한도의 최악의 사용을 최소화하는 것이 중요합니다. 평균 시나리오와 최악의 시나리오 간의 차이를 줄이면 네트워크 효율성이 향상되어 주어진 가스 한도에 대해 더 낮은 검증 예산을 사용할 수 있습니다.

증명기의 두 가지 주요 병목 현상은 계약 코드(바이트코드) 증명과 잘못된 가격의 연산 코드/사전 컴파일입니다. 본 문서에서는 전자에 중점을 둡니다.

계약 코드가 병목 현상인 이유는 무엇입니까?

현재 각 계정 바이트코드는 계정 Merkle Patricia Trie(MPT)의 코드 해시( keccak(bytecode) ) 필드에 커밋되므로 바이트코드의 슬라이스를 검증하려면 모든 것을 제공해야 합니다. 즉, 해시 완전한 바이트코드에서만 계산할 수 있습니다.

이는 블록 증명에 비효율적입니다. 트랜잭션은 일반적으로 계약 코드의 일부만 사용하기 때문입니다. 예를 들어, 이더리움 요청 사항(ERC)-20 토큰 전송에는 채굴 코드가 필요하지 않습니다. 마찬가지로, 계약 크기를 반환하는 EXTCODESIZE 와 같은 명령어는 계약 크기가 트리에 직접 저장되지 않으므로 길이를 계산하기 위해 전체 바이트코드가 필요합니다.

예를 들어, 현재 36M 가스 한도를 고려할 때, 최악의 시나리오는 최대 크기(현재 24KiB)의 EXTCODESIZE 컨트랙트를 대상으로 하는 하나의 트랜잭션이 포함된 블록 에서 36M 가스를 사용하여 반복적으로 실행하는 것입니다. 현재 36M 가스 한도의 경우, 검증자는 약 338MiB의 데이터( 이더리움 개선 제안(EIP) -2930을 사용하여 약 36M/2500*24KiB )를 해시 해야 합니다.

이것은 그다지 복잡한 이론적 공격이 아닙니다. 몇 달 전, Ethproofs 증명자들에게 미치는 영향을 확인하기 위해 메인넷에서 9배 다운그레이드된 공격을 실행했습니다. 25달러를 지출했는데( tx 공격 , 블록 공격 ), 증명자들은 평균보다 3배에서 5배 더 오랜 시간 동안 증명을 수행하거나 그 과정에서 충돌이 발생했습니다.

EXTCODESIZE 공격 벡터만 있는 것은 아닙니다. 계약의 단일 바이트코드에 영향을 미치는 CALL 유사 공격은 증명자가 증인(witness)에 전체 바이트코드를 포함하도록 강제합니다. EXTCODESIZE 사용하는 것은 공격을 유발하는 가장 간단한 방법일 뿐입니다.

다양한 가스 한도에 대한 최악의 경우는 다음과 같습니다.

• 36M 가스 = ~338MiB의 데이터가 keccak에 전송됩니다.
• 60M 가스 = ~563MiB의 데이터가 keccak에 전송됩니다.
• 100M 가스 = ~939MiB의 데이터가 keccak에 전송됩니다.
• 300M 가스 = ~2.8GiB의 데이터.

프로토콜이 최대 계약 크기인 24KiB를 256KiB로 늘리면 각 사례를 약 10배로 곱해야 합니다.

@kevaundray 와 협력하여 모든 zkVM이 이 시나리오(및 기타)의 최악의 시나리오를 다양한 가스 한도와 최대 계약 규모에 걸쳐 블록 테스트로 재현할 수 있도록 하고 있습니다. 이를 통해 zkVM 팀은 이러한 극단적인 상황이 아키텍처에 어떤 영향을 미치는지 정확하게 파악할 수 있으며, 엔지니어링 및 프로토콜 설계 모두 구체적이고 재현 가능한 지표를 기반으로 진행될 수 있습니다.

솔루션

블록 증명의 맥락에서 바이트코드 문제를 해결하는 데에는 프로토콜 외부 접근 방식과 프로토콜 내부 접근 방식의 두 가지 접근 방식이 있습니다.

완벽한 해결책은 없다는 점에 유의하십시오. 각 해결책은 이점을 얻는 대신 복잡성을 증가시킵니다. 이 문서에서는 다양한 가능성을 탐색하며, 최종 결정은 향후 ACD(Advanced Computing Development)에 맡깁니다. 해결책은 복잡성이 높은 순서대로 정렬되어 있습니다.

프로토콜 외부 해결 방법

가장 덜 침습적인 접근 방식은 프로토콜을 변경하지 않는 것이지만, 단순한 해결책을 넘어 임시방편입니다. Reth의 Ress 클라이언트 는 부분적으로 상태 비저장(stateless) 방식으로, 바이트코드만 저장하고 나머지 상태(논스, 잔액, 저장 슬롯)는 저장하지 않습니다. 블록 증명자는 검증자가 계약 바이트코드를 가지고 있다고 가정할 때, 바이트코드 데이터 자체가 아닌 코드 해시 정확성만 증명하면 됩니다.

이 솔루션의 장점:

• 핵심 프로토콜은 변경되지 않습니다(이것이 큰 이점입니다). 네트워크에서 증명 배포만 지원합니다.

단점:

• 클라이언트는 상태 비저장(stateless)이 아니라 부분 상태 저장(partially stateless)으로, 약 10GiB의 데이터가 필요합니다. 이 요구 사항은 체인이 발전함에 따라 계속 증가할 것이며, 가스 한도 증가 또는 최대 계약 크기 증가에 따라 성장 속도도 빨라질 것입니다. 이 용량은 대부분의 검증자에게는 여전히 비교적 작지만, 스마트폰과 같은 매우 저전력 기기는 제외될 수 있습니다.
• 블록 검증자는 블록체인에 참여하기 전에 모든 계약 바이트코드를 다운로드할 수 있지만, 추가적인 신뢰 가정 없이는 데이터가 완전한지 확인할 수 없습니다. 따라서 다른 네트워크 노드에서 누락된 계약 바이트코드를 가져와야 할 수도 있습니다. 이러한 가져오기 프로세스는 시간 제한이 없으므로 블록 검증 파이프라인에 네트워크 종속성이 발생합니다.
• 따라서 이 솔루션은 블록 증명에 엄격한 기한을 가진 네트워크 증명자에게는 적합하지 않습니다. 증명자가 아닌 노드, 예를 들어 체인 검증만 수행하는 노드에는 문제가 되지 않습니다.
• 증명과 바이트코드 제공은 모두 네트워크 노드의 정직성에 달려 있습니다. 전체 프로토콜 솔루션과 비교할 때 블록 제안자는 블록 내에 증명을 포함해야 합니다.

위 목록에는 많은 단점이 있지만, 프로토콜을 변경할 필요가 없다는 점을 고려하면 이 솔루션에 더 많은 것을 기대할 수는 없습니다.

노드는 신뢰할 수 있는 출처에서 모든 계약 바이트코드를 다운로드하여 향후 네트워크 호출을 필요로 하는 누락된 바이트코드가 없도록 함으로써 이러한 단점을 완화할 수 있습니다. 프로토콜 수준에서 코드 해시의 추가 전용 머클 트리를 포함함으로써 이러한 신뢰 가정을 없앨 수 있습니다. 루트는 클라이언트가 데이터를 검증하고 오프라인 노드가 누락된 데이터를 동기화하도록 지원합니다.

프로토콜 내 옵션

이 문제에 대한 해결책은 계약의 바이트코드를 청크로 분할하고 이를 메르켈화하는 것입니다. 이를 통해 실행 추적에서 언급된 코드 청크만 검증할 수 있으며, 이는 전체 계약 코드보다 적은 데이터입니다.

코드 청킹과 관련된 모든 솔루션에는 두 개의 직교 차원이 있습니다.

• 바이트코드는 어떻게 청크로 나뉘나요?
• 덩어리는 어떻게 메르켈화되나요?

바이트코드는 어떻게 청크로 나뉘나요?

두 가지 주요 코드 청커 전략은 다음과 같습니다.

• 31바이트 코드 청커: JUMPDEST 분석에 도움이 되도록 1바이트 접두사를 사용하여 바이트코드를 31바이트 청크로 분할합니다. 자세한 설명은 여기에서 확인할 수 있습니다.
• 32바이트 코드 청커: 바이트코드를 32바이트 청크로 분할하지만, 유효하지 않은 점프 대상 0x5B 를 포함하는 코드 청크를 효율적으로 인코딩하는 테이블을 바이트코드 앞에 추가합니다. 예를 들어, PUSHN 즉시 명령에 0x5B 포함되어 있지 않으면 모든 점프가 유효하므로 테이블은 비어 있게 됩니다. 더 자세한 설명은 여기 에서 확인할 수 있습니다.
• 동적 청킹: 이전 연구에서는 코드 점프가 청크의 시작 부분만 대상으로 하는 동적 크기 청킹을 ​​연구했습니다. JUMPDEST 명령어는 유효한 점프 대상을 표시하므로 청크의 시작 위치를 효과적으로 결정합니다. 이를 통해 유효하지 않은 점프를 감지하기 위한 추가 메커니즘이 필요하지 않습니다. 그러나 JUMPDEST 명령어가 없는 대용량 바이트코드와 같은 다른 메커니즘을 통해 해결해야 할 잠재적인 문제가 있습니다.

이러한 코드 청커는 기존 계약에서 발생할 수 있는 문제를 해결합니다. 향후 EOF 계약에서는 유효한 점프가 있는 코드만 배포될 수 있으므로 이러한 문제가 발생하지 않습니다. 얼마 전 두 전략을 비교하는 분석을 진행한 적이 있습니다.

위에 제시된 것은 두 가지 청커 제안이지만, 더 많은 변형이 있을 수 있습니다.

• 사용 효율성 : 청크가 클수록 증인에게 제공해야 할 청크가 적어지지만 청크의 모든 바이트가 실행 추적에 사용되지 않으므로 낭비되는 바이트가 늘어날 수 있습니다.
  • 두 청커 모두 32바이트 코드 청크를 제안하는데, 이는 저장 슬롯과 같은 크기를 갖도록 의도되었기 때문일 수 있습니다.
• 저장 효율성 : 청킹으로 인해 얼마나 많은 저장 오버헤드가 생성됩니까?
  • 31바이트 코드 청커: 1/31~=3.2% 오버헤드
  • 32바이트 코드 청커: 동적, 얼마 전 메인넷 분석을 통해 ~0.1%가 보고되었고, 최악의 경우 3.1%(즉, 모든 청크에 잘못된 점프가 포함됨)가 보고되었습니다.
• 복잡성 : 사양 및 구현 복잡성
  • 31바이트 코드 청커: 매우 간단함
  • 32바이트 코드 청커: 테이블 형식, 위치 이더리움 클래식(ETC) 을 정의하는 데 더 많은 복잡성이 있습니다.

덩어리는 어떻게 메르켈화되나요?

청크화된 바이트코드가 주어지면 실행 추적에서 액세스한 부분 바이트코드에 대한 증명을 생성할 수 있도록 청크가 어떻게 메르켈화되는지 확인해야 합니다.

EXTCODE* 연산 코드를 효율적으로 지원하기 위해 기존 codeHash 와 새로운 codeSize 필드도 포함해야 합니다. 이 작업은 매우 간단하므로, 여기서는 가장 중요한 어려움인 코드 청크의 머켈라이징에만 집중하겠습니다.

코드 덩어리를 어디에 메르켈화해야 하나요?

다음은 메르켈화할 수 있는 몇 가지 전략입니다.

• 현재 MPT 내부 .
  • 이는 이더리움 개선 제안(EIP)-2926 , 특히 코드 머켈라이제이션(Code Merkelization) 섹션에서 제안됩니다. 코드 해시 필드는 청크 코드를 저장하는 MPT의 루트로 대체됩니다.
  • 코드 청크는 동일한 루트를 공유하므로 자연스럽게 중복이 제거됩니다.
  • 장점:
    • 기존의 나무를 활용한 자연스러운 디자인.
    • 복잡성이 낮음.
  • 단점:
    • RLP와 keccak과 같은 기존 오버헤드를 유지하는 것이 사양 복잡성을 더 증가시키는 것보다 나을 수 있습니다.
• 새로운 통합 국가 트리 내부
  • 계정 및 저장 데이터에 대한 새로운 통합 트리(예: 이진 트리 )를 제안하는 EIP에서 계약 코드 청크도 여기에 저장됩니다.
  • 찬성:
    • 새로운 나무를 고려한 자연스러운 디자인이 도입되었습니다.
    • 기존 코드의 코드 청킹은 트리 변환 프로세스의 일부입니다.
  • 단점:
    • 현재 제안에서는 동일한 청크의 중복을 제거하지 않지만, 이는 변경될 수 있습니다.
    • 다른 많은 변경 사항과 함께 적용되면 합의 버그의 위험이 커질 수 있습니다.
• 코드 청크에만 전념하는 새로운 트리 내부
  • 코드 청크 전용의 새로운 트리가 도입되었습니다. 기존 MPT는 그대로 유지됩니다.
  • 찬성:
    • 선택적으로 새로운 트리를 설계할 때 유연성을 허용합니다(예: 다른 아리티 또는 해시 함수).
    • 중복 제거는 키 정의에 따라 선택 사항입니다.
  • 단점:
    • 블록 헤더에 추가 트리 루트가 있습니다.
    • MPT와 다른 트리 디자인은 사양 복잡성과 구현 버그의 위험이 더 크다는 것을 의미합니다.

새로운 바이트코드와 기존 바이트코드의 메르켈화는 어떻게 처리되나요?

새로운 계약을 생성할 때 코드를 메르켈화하는 과정은 간단합니다. 이더리움 개선 제안(EIP)-4762 에서 이미 저장된 코드 청크당 가스 요금을 청구하는 구조, 즉 트리에 삽입된 코드 청크당 사용자에게 요금을 청구하는 구조를 설명하고 있기 때문입니다.

가장 큰 과제는 기존 코드, 즉 최소 15GiB의 중복 제거된 데이터를 메르켈화하는 것입니다. 이는 포크(Fork) 활성화 단계에서만 작업을 수행하는 것으로는 달성할 수 없습니다. 새로운 통합 상태 트리 케이스는 트리 변환 프로세스 중에 이 작업을 수행할 수 있지만, 다른 두 가지 전략은 어떻게 수행할지 결정해야 합니다. 몇 가지 아이디어는 다음과 같습니다.

• 주문형 변환 (이 변형을 언급해 준 Dankrad에게 감사드립니다. 장단점은 제 개인적인 생각입니다)
  • 트랜잭션이 분할되지 않은 계약과 상호 작용할 때만 이 코드가 분할됩니다. 트랜잭션 발신자는 코드 분할에 대한 비용을 지불합니다.
  • 장점:
    • 기존 메인넷 바이트코드를 사용하기 전까지 변환할 필요가 없으므로 프로토콜에 매우 편리합니다.
    • 코드가 메르켈화된 대상 트리는 다시는 사용되지 않을 계약으로 오염되지 않으므로 간접적으로 일부 가지치기가 수행됩니다.
  • 단점:
    • 계약의 코드 청킹은 해당 계약과 상호작용하는 첫 번째 트랜잭션을 통해 지불됩니다. 이는 누가 비용을 지불할지 예측할 수 없기 때문에 UX 문제가 될 수 있으며, 사용자 관점에서는 다른 사람이 먼저 지불할 때까지 기다리는 것이 트랜잭션을 전송하는 것보다 나을 수 있습니다.
    • 포크(Fork) 활성화 시점과 이후 일부 블록에서는 코드 청킹과 관련된 가스 사용량이 크게 증가할 수 있습니다. 이는 시스템이 안정화될 때까지 기본 수수료에도 영향을 미칠 수 있습니다.
    • 이 접근 방식은 변환되지 않은 바이트코드를 영원히 남길 수 있습니다. 따라서 EL 클라이언트는 변환 코드가 나중에 다시 필요할 수 있으므로 해당 코드를 보관해야 합니다. 또한 블록 증명자가 코드 청킹을 증명해야 하므로 변환에 필요한 가스 비용이 높아질 수 있습니다.
• 다중 블록 변환
  • 새로운 트리 변환( 이더리움 개선 제안(EIP)-7748 )과 유사하게, 모든 코드가 청크로 정리될 때까지 각 블록 에서 보류 중인 코드를 마이그레이션하는 프로세스를 정의합니다.
  • 장점:
    • 사용자가 코드 청킹에 비용을 지불하지 않으므로 UX 문제가 없습니다.
    • 가스 요금 급증이나 기본 요금 변동이 없습니다.
    • 블록 단위 변환을 통해 단일 블록 활성화와 비교해 합의 수준에서 버그가 발생하는 즉시 이를 감지할 수 있습니다.
  • 단점:
    • 한 번만 수행되는 작업에 대한 사양이 복잡해지고, 구현상의 버그가 많아 위험할 수 있습니다.
• 오프라인 변환
  • 이것이 언급된 이더리움 개선 제안(EIP)-2926 에서 제안된 변환 메커니즘입니다. 이 섹션 에는 해당 아이디어가 설명되어 있습니다.
  • 찬성:
    • 사용자가 코드 청킹에 비용을 지불하지 않으므로 UX 문제가 없습니다.
    • 가스 요금 급증이나 기본 요금 변동이 없습니다.
    • 포크(Fork) 활성화 시점에 시스템은 즉시 원하는 상태로 전환됩니다. "다중 블록 변환"처럼 임시 변환 단계는 존재하지 않습니다.
  • 단점:
    • 변환이 오프라인에서 이루어지므로 적절한 포크(Fork) 활성화 타임스탬프를 추정해야 합니다. 하지만 안전한 값은 쉽게 계산할 수 있습니다. 또는 EL 클라이언트가 적절한 대역 외 검사를 수행한 후 수동 두 번째 빠른 포크(Fork) 사용하여 활성화할 수도 있습니다.
    • 각 EL 클라이언트의 백그라운드 변환 결과는 활성화 시간까지 불투명한 상태로 유지되므로 "멀티 블록 변환"에 비해 위험하다고 간주될 수 있습니다.
    • 최악의 시나리오를 대비해 포크(Fork) 활성화에 가까운 심각한 재구성을 고려해야 합니다.
• 온디맨드 + (제한된) 오프라인 믹스
  • 업무 부담을 최소화하기 위해 지난 1년 이내에 접속한 계약에 대해서만 오프라인 변환을 요청하세요. 나머지 미처리 계약의 경우, 첫 번째 거래에서 변환 비용이 충당됩니다.
  • 장점:
    • 지난 해의 계약에 접근하는 사용자에게는 비용이 발생하지 않으므로 UX 문제가 최소화됩니다. 이전 거래에 접근하는 사용자만 비용을 지불하면 됩니다.
    • 가스 가격 급등이나 기본 요금 변동이 최소화됩니다.
    • 오프라인 변환 시 EL 클라이언트의 작업 부하가 감소합니다.
  • 단점:
    • 변환이 필요한 바이트코드가 줄었음에도 불구하고 백그라운드 변환은 불투명한 상태로 남아 있어 합의 실패의 위험은 여전히 ​​존재합니다.
    • 포크(Fork) 활성화 타임스탬프 추정은 여전히 ​​중요하며, 그렇지 않으면 활성화를 위해 수동으로 두 번째 포크(Fork) 실행해야 할 수도 있습니다.
    • 항상 변환되지 않은 코드가 있고 코드 청크를 증명해야 하는 상황이 있습니다.

그 다음에는 무슨 일이 일어날까요?

정리되지 않은 바이트코드 문제를 해결한 후에도 남은 병목 현상은 잘못된 가격이 책정된 명령어/사전 컴파일(예: MODEXP 및 페어링 - Fusaka( 이더리움 개선 제안(EIP)-7883 )에서 이에 대한 작업이 계획됨)과 상태 액세스 효율성입니다. 연구원과 zkVM 엔지니어는 이전 문제를 분석하고 있습니다.

후자는 사용 가능한 모든 가스를 사용하여 상태에 접근하는 것을 의미합니다. 부하량은 기본 트리의 arity와 해시 함수에 따라 달라지며, 이는 증인(witness)에 필요한 해싱 양에 영향을 미칩니다. 현재 MPT를 유지한다는 가정 하에, 가능한 한 많은 계정 접근을 수행하면 다음과 같습니다.

• 36M 가스 = ~407k 케착 순열.
• 60M 가스 = ~678k 케착 순열.
• 1억 가스 = ~113만 케착 순열.
• 300M 가스 = ~339m 케착 순열.

( keccak perms = gas/2500*tree_depth*15*32/keccak_rate = gas/2500*8*15*32/136 )

위의 계산은 MPT와 같은 16-arity 트리(즉, ~8)에서 메인넷의 예상 깊이를 사용합니다. 그러나 실제 트리 구조 내의 특정 분기는 더 큰 깊이에 도달하여 활용 가능성을 제공합니다.

위의 예측이 고려된 최소한의 증명자 하드웨어 예산에 문제가 되는 경우, 상태 트리 변경이나 상태 접근을 위한 가스 모델을 고려해야 할 수도 있습니다.