한 문서에서 조회 인수에 대해 알아보기

特邀专栏作者

2022-12-22 09:44

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

이 기사에서는 OlaVM이 고성능을 달성할 수 있게 해주는 도구 중 하나인 조회 인수에 중점을 둘 것입니다.

TL;DR

이전 기사 Hello, OlaVM!에서 언급했듯이 OlaVM의 비전은 고성능 ZKVM을 구축하는 것입니다. 조회 인수는 ZK의 효율성을 향상시키기 위해 회로의 크기를 줄이는 데 중요한 역할을 하며 ZKVM의 회로 설계에 널리 사용됩니다. 이 기사를 통해 다음을 배울 수 있습니다.

1. 조회 인수는 ZKVM에서 어떤 역할을 합니까?

2. Plookup 프로토콜 원리.

3. Halo 2의 조회 인수 프로토콜 원리.

첫 번째 레벨 제목

The roles in ZKVM

소위 ZKVM은 실제로 ZK를 사용하여 VM의 모든 실행 프로세스를 제한합니다. VM의 실행 프로세스는 일반적으로 명령 실행, 메모리 액세스, 내장 함수 실행 등으로 나눌 수 있습니다. 트레이스에서 이러한 오퍼레이션에 대한 제약 조건을 구현하는 것은 다소 비실용적입니다.첫째, 다른 오퍼레이션 유형의 제약 조건은 다른 트레이스 폭에 해당합니다.제약 사항 중 하나에 해당하는 트레이스 폭이 특히 크면 나머지 제약 조건이 발생합니다. 트레이스 폭에 해당하는 낭비; 그런 다음 트레이스에 너무 많은 다른 작업 유형이 있는 경우 더 많은 선택기가 도입되어 다항식의 수를 증가시킬 뿐만 아니라 제약 조건의 순서도 증가합니다. 그룹의 순서 제한, 추적 라인 수는 이 그룹의 순서를 초과할 수 없으므로 특정 유형의 작업이 차지하는 추적 라인의 수를 최소화해야 합니다.

따라서 단순화를 위해 다음이 필요합니다.

a. 서로 다른 작업 유형을 여러 하위 추적으로 나눈 다음 데이터 일관성을 보장하기 위해 기본 추적과 하위 추적 간에 조회 인수가 필요함을 개별적으로 증명합니다.

b. 일부 ZK 비우호적 계산의 경우 조회 인수 기술을 사용하여 비트 연산과 같은 추적 크기를 줄일 수 있습니다.

보조 제목

Lookup between trace tables

이미지 설명

그림 1. 추적 간 조회

보조 제목

Lookup for ZK-unfriendly operations

앞서 언급했듯이 각 하위 트레이스의 증명은 독립적이므로 가능한 한 작은 트레이스를 얻으면 증명자의 효율성이 향상됩니다. 비트 단위를 예로 들면, 비트 단위 연산에는 AND, XOR, NOT 세 가지 연산이 포함됩니다. 회로를 통해 비트 연산에 대한 제약 조건을 간단히 구현하려는 경우 각 연산을 여러 이진 팔다리로 분할해야 할 수 있습니다. 이러한 연산이 3 2비트 폭인 경우 32개의 팔다리로 분할됩니다. 그런 다음 다음을 제한해야 합니다.