ZKEVM에서 메모리 제한 제거에 대한 몇 가지 생각

特邀专栏作者

2022-09-21 09:23

이 기사는 약 2361자로, 전체를 읽는 데 약 4분이 소요됩니다

ZKVM의 제약 시스템에서 zk 제약의 규모를 줄이기 위해 VM 수준에서 메모리 액세스 메커니즘을 설계하는 것이 가능할 수 있습니다.

ZKEVM은 ZK 기술을 기반으로 프로그래밍 가능한 가상 머신으로, 가상 머신이 수행하는 모든 작업에 대해 영지식 증명(zk proof)을 생성하여 가상 머신 작동의 정확성을 증명할 수 있습니다. ZKEVM의 여러 구현 체계 소개와 장단점 비교는 V God의 기사를 참조할 수 있습니다.The different types of ZK-EVMs; 더 자세한 디자인 정보를 알고 싶다면 PSE의 ZKEVM 체계(네이티브 레벨)를 읽을 수도 있습니다.privacy-scaling-explorations/zkevm-specsPolygon의 ZKEVM 설계(바이트코드 수준):Polygon zkEVM Documentation; Sin7y의 ZKEVM 설계(언어 수준):OlaVM: An Ethereum compatible ZKVM. 솔루션에 관계없이 다음을 포함하여 VM의 모든 동작을 제한하려면 zk를 사용해야 합니다.

• 계약 계산 로직 실행

• 메모리 액세스 수행

• 해시 계산 수행

• 세계 상태 업데이트 수행

• ...

우리 모두 알고 있듯이 zk는 컴퓨팅 압축 분야에서 뛰어난 응용 가능성을 가지고 있습니다. 원래 계산이 아무리 복잡하더라도 검증 프로세스는 매우 효율적이며 이는 모든 zk 알고리즘의 기본 기술입니다. 따라서 zk는 계산 부분(예: 계약 논리, 해시 계산 등)에서 좋은 역할을 할 수 있습니다. 일부 데이터는 사전에 메모리에 배치한 다음 계산을 수행할 때 가져와야 합니다.

대부분의 VM은 메모리를 읽고 쓰기 때문에 이러한 메모리 액세스 작업의 정확성을 제한해야 합니다(예: 특정 주소에서 읽은 데이터가 마지막으로 쓴 데이터와 동일한지 확인하는 일관성 검사). 그 자체는 복잡하지 않지만(경우가 적음) 메모리 액세스 수가 많기 때문에 다항식의 차수가 매우 높아 메모리 관련 제약 조건이 시간이 많이 소요됩니다.

첫 번째 레벨 제목

텍스트

~에 의해EVM이미지 설명

텍스트

• MSTORE(x,텍스트

• MSTORE8(x,y): 주소 x부터 시작하여 y의 8바이트 쓰기(하위 비트 시작) 관심 있는 독자는 찾을 수 있습니다.EVM Playground텍스트

존재하다

존재하다OlaVM섹션 5.3.5에서 메모리 제약의 설계 원칙을 볼 수 있습니다(OlaVM 메모리 관련 명령어는 EVM과 유사함).

OlaVM에서 모든 RAM 작업은 독립적인 테이블을 형성하고 테이블의 콘텐츠는 메모리와 스토리지의 두 가지 유형으로 구성됩니다. 여기서는 메모리 제약 조건에만 초점을 맞춥니다. 메모리 작업 유형은 대략 세 가지 범주로 나눌 수 있습니다.

• 초기화 작업

• 쓰기 작업

• 읽기 작업

Init을 트리거하는 시나리오는 ctx 변환, 유형 변경, addr 변경의 세 가지 시나리오가 있으며, 시나리오 중 하나가 트리거되면 제약 조건이 필요합니다.작업 유형은 w(쓰기), v(값)는 0입니다.。

위의 세 가지 시나리오가 트리거되지 않으면 현재 작업 유형에 따라 제한해야 합니다.

• w(쓰기) 작업인 경우 clk가 증가하고(rangecheck 모듈 호출) 쓰여진 값 v가 정확하도록 제약해야 합니다(복사 제약 호출, OlaVM에서 메모리 명령의 모든 값). 레지스터에서 가져옵니다).

• r(읽기) 작업인 경우 clk가 증가하도록 제한해야 합니다(rangecheck 모듈 호출).읽은 값은 마지막으로 쓴 값과 동일합니다.。

일부 가능성 개선(zk 친화적)

• 초기화 작업을 위해 메모리 주소의 초기화 값을 0으로 제한해야 합니까?

초기화 작업을 제한할 필요는 없다고 생각합니다. 사실 모든 주소에 대해 첫 번째 액세스가 읽기 작업이 아니라 쓰기 작업이어야 한다는 제한을 둘 수 있습니다. 제한은 당연할 것이므로 가상머신의 메모리 모델을 1회 쓰기 모델로 변경하면 메모리에 대한 접근 제약이 줄어들 것이다.

• 읽기 작업의 경우 해당 제약 조건을 피할 수 있습니까? 즉, 읽기 값이 마지막으로 쓴 값과 일치하는지 확인하는 것을 방지할 수 있습니까?

VM 자체에서 정의한 메모리 유형의 읽기-쓰기 메모리는 보장할 수 없으므로 VM이 이 메모리 주소의 값을 읽기 전에는 이 메모리 주소의 값이 수정되지 않았으므로 다음과 같이 동등성 검사가 추가되어야 합니다. 다음 그림에 나와 있습니다.

이것에서 이러한 제약의 핵심적인 이유는 메모리 모델이 메모리를 읽고 쓰는 것이고, 주소의 값이 다시 쓰여질 수 있기 때문임을 알 수 있습니다. ), 메모리에 쓸 필요가 없습니다.위의 일관성 제약 조건을 달성하기 위한 제약 조건.

참고: 이것은 일반적이지 않은 메모리 모델이기 때문에 가상 머신 구현의 어려움을 증가시킬 수 있으며, 이 언어는 Dapp 개발자에게 다소 생소할 것이기 때문에 이 가상 머신에서 고급 DSL을 먼저 정의해서는 안 됩니다. 컴파일러 수준에서 개발자에게 친숙하지 않고 보이지 않게 만듭니다. 따라서 위의 메모리 모델을 채택하면 메모리 모듈의 제약은 쓰기 작업에 대한 제약, 즉 복사 제약을 사용하여 기록된 값이 올바른지 확인합니다.제약 없음：

• 메모리는 한 번만 쓸 수 있기 때문에 읽은 값은 쓴 값과 같습니다.

• 먼저 쓴 다음 읽을 수만 있기 때문에 읽기 clk는 쓰기 clk보다 큽니다.

• 메모리가 0으로 초기화됩니다(둘 다 필요하지 않음).