TinyRAM에 대한 심층적인 이해

特邀专栏作者

2022-08-17 12:53

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

이 기사에서는 TinyRAM의 아키텍처, 설계, 조립 지침, 장점 등에 대해 설명합니다.

TinyRAM은 유명한 BCTGTV 5인조 그룹(Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza)과 SCIPR 연구소가 제안한 임의 접근자 아키텍처로, 비결정적 컴퓨팅 편리한 도구의 증거가 되는 것을 목표로 합니다. 특히 TinyRAM은 바이트 수준의 주소 지정이 가능한 임의 액세스 메모리가 있는 RISC(Reduced Instruction Set Computer)입니다. 그것은 "충분히 표현적이다"와 "충분히 단순하다"의 반대말 사이의 균형을 이룬다:

• 높은 수준의 프로그래밍 언어에서 컴파일할 때 짧고 효율적인 어셈블리 코드를 지원하기에 충분한 표현력

•작은 명령어 세트, 명령어는 연산 회로에 의해 쉽게 검증되고 효율적인 검증은 SCIPR의 알고리즘 및 암호 메커니즘을 사용하여 실현됩니다.

건축학

TinyRAM은 2개의 정수로 매개변수화됩니다. 워드 길이 W는 2의 거듭제곱이어야 하고 8로 나눌 수 있어야 합니다(이는 32, 64와 같은 최신 컴퓨터와 동일함). 일반적으로 TinyRAM(W,K)으로 표현되는 기계의 상태는 다음을 포함합니다.

1. 프로그램 카운터 pc(프로그램 카운터)는 W 비트로 구성됩니다.

2. r0, r1, ..., r(K-1)로 표시되는 K 범용 레지스터, 각 레지스터는 W 비트입니다.

3. 조건 플래그 플래그는 1비트로 구성됩니다.

4. 리틀 엔디안 규칙을 사용하여 바이트를 배열하는 메모리, 2^W 바이트의 선형 배열.

5. 각각 W 비트 워드 문자열을 포함하는 2개의 테이프. 각 테이프는 한 방향으로 읽기 전용입니다. 그 중 하나의 테이프는 공개 입력 x용이고 다른 테이프는 개인 입력 w용입니다. 사실 TinyRAM의 입력 캐리어입니다.

TinyRAM 머신의 입력은 2개의 테이프와 메모리이고, 출력은 반환 값을 나타내는 매개변수 A가 있는 응답 명령이고 A = 0은 수락을 의미합니다. 이 명령을 사용하여 프로그램 실행을 종료할 수도 있습니다.

TinyRAM에는 명령이 실행되는 위치에 따라 두 가지 변형이 있습니다. 하나는 Harvard 아키텍처를 따르고 다른 하나는 von Neumann 아키텍처를 따릅니다. 전자 구조의 데이터와 프로그램은 서로 다른 주소 공간에 저장되며 프로그램은 읽기 전용이며 후자 구조의 데이터와 프로그램은 읽기 및 쓰기 가능한 동일한 주소 공간에 저장됩니다. 특히 둘 사이의 차이점은 다이어그램으로 표시됩니다.

다음 두 아키텍처의 그림:

더 자세한 TinyRAM 설계 세부 사항을 시작하기 전에 공식 백서의 예를 사용하여 TinyRAM이 얼마나 간결하고 포괄적이며 비결정적 컴퓨팅 문제를 만족시킬 수 있는지 설명합니다.

중요성

Alice는 x를 소유하고 Bob은 w를 소유합니다. Alice는 알고리즘 A(x, w)의 계산 결과의 정확성을 알고 싶지만 직접 계산하고 싶지는 않습니다. 이러한 시나리오는 영지식 증명 시스템에서 매우 일반적입니다.증명자와 검증자가 있습니다.검증자는 증명자가 제공한 증거의 정확성을 알고 싶어하지만 직접 다시 계산할 필요는 없습니다. TinyRAM 아키텍처는 두 개의 테이프가 증명 계산 및 검증 절차가 실행되는 개인 입력 w 및 공용 입력 x를 통과할 수 있는 시나리오를 충족합니다. TinyRAM은 SCIPR 연구소에서 구현한 libsnark 라이브러리에 구현되었습니다. 자세한 내용은 다음을 참조하세요.https://github.com/scipr-lab/libsnark.

Circuit Generator를 예로 들면, C 프로그램이 컴파일러를 거친 후 TinyRAM 프로그램으로 컴파일되고 Circuit Generator를 거친 후 회로가 생성되고 최종적으로 zkSNARK 회로가 얻어진다.

지침

TinyRAM은 29개의 명령을 지원하며 각 명령은 1개의 opcode와 최대 3개의 피연산자로 지정됩니다. 피연산자는 레지스터 이름(즉, 0에서 K-1까지의 정수) 또는 즉치 값(즉, W-비트 문자열)일 수 있습니다. 별도로 지정하지 않는 한 각 명령어는 플래그를 수정하지 않고 i만큼 pc를 증가시킵니다(modulo 2^W). Harvard 아키텍처의 경우 i=1이고 von Neumann 아키텍처의 경우 i=2W /8입니다. 일반적으로 첫 번째 피연산자는 명령어가 수행하는 계산의 대상 레지스터이고 다른 연산(있는 경우)은 명령어의 인수를 지정합니다. 결국 모든 명령어는 실행하는 데 기계의 한 주기가 걸립니다.

명령어에는 여러 유형이 있으며 명령어 이름은 이름에서 알 수 있듯이 intel x86 어셈블리 명령어와 유사합니다.

● 비트 조작 지침：

•and

•or

•xor

•not

● 정수 조작 지침:

•add

•sub

•mull

•umulh

•smulh

•udiv

•umod

● 시프트 작업 명령:

•shl

•shr

● 비교 연산 명령

•cmpe

•cmpa

•cmpae

•cmpg

•cmpge

●이동 작업 지시

•mov

•cmov

● 점프 조작 지시

•jmp

•cjmp

•cnjmp

● 메모리 조작 지침

•store.b

•load.b

•store.w

•load.w

● 작업 명령을 입력합니다.

•read

● 출력 작동 지침:

•answer

어셈블리어

TinyRAM용 프로그램은 Intel x86 어셈블리 언어 구문에서 영감을 받은 TinyRAM 어셈블리 언어로 작성됩니다. 프로그램은 TinyRAM 어셈블리 코드 라인을 포함하는 텍스트 파일입니다. 프로그램이 Harvard 아키텍처를 기반으로 하는지 von Neumann 아키텍처를 기반으로 하는지에 따라 첫 번째 줄에 포함된 문자열도 다릅니다.

• 하버드 아키텍처

“; TinyRAM V=2.000 M=hv W=W K=K”

• 폰 노이만 아키텍처

“; TinyRAM V=2.000 M=vn W=W K=K”

그 중 W는 10진법으로 표현된 워드 길이이고 K는 10진법으로 표현된 레지스터의 수이다. 프로그램 파일에서 각 행에 포함된 내용은 다음을 충족해야 합니다.

1. 선택적 공간.

2. 뒤에 오는 첫 번째 명령을 참조하도록 정의된 선택적 레이블입니다.

3. 피연산자가 따라오는 명령어 니모닉에 의한 선택적 명령어.

4. 선택적 공간.

5. 선택적으로 세미콜론으로 시작하는 주석은 줄의 끝에서 끝납니다.

프로그램에서 최대 2^W 명령이 있을 수 있습니다. 레이블은 고급 언어의 변수와 같이 한 번만 정의할 수 있습니다.

샘플 코드(https://github.com/scipr-lab/libsnark/blob/master/tinyram_examples/answer0/answer0.s)

계산 요구를 충족하고 회로 만족 효율을 향상시키기 위해 TinyRAM은 프리앰블을 추가합니다. TinyRAM 프로그램이 프리앰블로 시작하면 그 프로그램이 제대로 된 프로그램이라는 뜻입니다.

위 서문:

• Harvard 아키텍처의 경우 I(i)= 1 * i 및 inc = 1

• von Neumann 아키텍처의 경우 I(i) = 2W/8 * i 및 inc = W/8

이전 샘플 코드도 이 서문을 따릅니다.

두 아키텍처의 성능 비교

TinyRAM의 두 아키텍처의 설계 차이점은 이전 "아키텍처" 섹션에서 소개했으며 여기에서는 두 아키텍처의 성능을 비교합니다.

첫 번째 그래프는 두 아키텍처에서 생성된 게이트 수를 보여줍니다.

l은 명령의 수, n은 입력 크기, T는 실행 단계의 수입니다.

전자의 경우 게이트 수와 명령어 수가 선형적으로 증가함을 알 수 있다. 후자는 크게 개선되었으며 지침이 많을수록 개선이 커졌습니다.

두 번째 차트는 서로 다른 단어 길이의 곡선 아래에서 키 생성기/증명기/검증기를 생성하는 두 아키텍처의 시간 및 증명 크기를 보여줍니다.

80비트에서는 von Neumann 아키텍처가 Harvard 아키텍처에 비해 더 크게 개선되었으며 128비트에서도 약간의 개선이 있음을 알 수 있습니다.

요약하다

TinyRAM의 아키텍처, 디자인, 조립 지침 등에 대해 이야기하고 비결정론적 계산을 편리하게 수행하는 데 사용할 수 있는 이점을 소개했습니다. 특히 영지식증명 시스템은 발전의 여지가 더 많다. 마지막으로 두 TinyRAM 아키텍처의 성능 비교를 소개하는데 von Neumann 아키텍처가 생성된 게이트의 수와 시간, 증명의 크기 측면에서 우수합니다.