미덴의 극명한 증명 시스템

Sin7y

特邀专栏作者

2022-10-11 08:38

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

이 백서에서는 miden proof 시스템 아키텍처를 자세히 설명합니다.

첫 번째 레벨 제목

미덴 증명 시스템 아키텍처

miden은 strark 기술을 기반으로 하는 zkvm 구현입니다. 맨 아래 레이어는 Winterfell의 zkp 라이브러리를 기반으로 하여 확실한 증명을 생성하고 증명을 확인합니다. 아래 그림 1의 점선은 미덴에서 구현한 주요 기능입니다. 크게 세 가지 구성 요소가 있음을 알 수 있습니다.

1. 아래 그림 1의 어휘 문법 컴파일러, 어휘 분석기 및 구문 파서 세트. 그들은 miden에 의해 정의된 어셈블리 명령을 codeblock 및 블록에 포함된 opcode 및 op 값으로 프로그래밍할 수 있습니다.

3. 극명한 증명 요구 사항을 충족하는 AIR(대수적 중간 표현) 집합, 아래 그림 1의 AIR. 미덴의 가상 머신의 실행 프로세스를 제한하기 위해 사용됩니다.

첫 번째 레벨 제목

AIR 구조 설계

AIR의 제약 조건은 스택과 디코더의 두 부분으로 나뉩니다.

그림 3은 디코더의 제약 조건을 보여줍니다. 그 중 op_counter, op_sponge, cf_op_bits, ld_op_bits, hd_op_bits는 고정 열 길이입니다. 그중 op_sponge는 명령 실행의 순서와 정확성을 제한하는 데 사용됩니다. cf_op_bits는 3비트 flow_ops를 제한합니다. ld_op_bits, hd_op_bits는 각각 user_ops의 하위 5비트 및 상위 2비트를 제한합니다. ld_op_bits와 hd_op_bits의 조합은 실행된 user_op를 구성하며 스택의 각 단계 상태 제약 조건에 대한 선택기로도 사용됩니다.

첫 번째 레벨 제목

Miden VM 실행 프로세스 인스턴스

이 섹션에서는 vm의 실행 프로세스와 stark의 실행 추적 생성을 설명하기 위해 간단한 miden 논리를 보여줍니다.

아래의 코드 세그먼트 1은 실행할 코드 세그먼트입니다.

이것이 실행하는 논리는 3과 5를 스택에 푸시하는 것입니다. 그런 다음 테이프에서 깃발을 읽으십시오. 플래그가 1인지 0인지 확인합니다. 1이면 if.true 분기를 실행하여 스택에 푸시된 두 숫자 3과 5를 꺼내고 함께 더하여 8을 얻고 다시 스택에 푸시합니다. 0이면 else 분기를 실행하여 스택에 푸시된 두 숫자 3과 5를 꺼내고 곱하여 15를 얻은 다음 15를 다시 스택으로 푸시합니다.

코드 세그먼트가 miden의 어휘 및 문법 분석기에 의해 구문 분석된 후의 최종 명령 코드는 다음과 같습니다. 코드 세그먼트 2:

아래 그림 4는 vm이 code segment 2를 실행하는 과정을 보여주고 있다. 코드 실행에 의해 생성된 스택 트레이스.

그중 실행자는 코드 블록에 따라 하나씩 실행됩니다. 이 예에서는 span 블록이 먼저 실행됩니다. 그런 다음 32단계에서 if-else-end 구조를 실행하여 swtich 블록에 진입하고 이전 span 블록의 마지막 단계에서 생성된 스폰지 해시를 ctx_stack에 푸시하고 swtich 블록이 실행된 후 49단계에서 Pop into the 스펀지.