한 문장으로 이해하는 StarkNet 제로 지식 재귀 증명—STARK

StarkNet 중국 커뮤니티

2022-08-16 19:07:26

수집

재귀는 비용과 성능을 더욱 확장하고자 하는 플랫폼과 애플리케이션에 더 많은 기회를 열어줍니다.

위챗으로 스캔하기

원제목: 《Recursive STARKs》

저자: StarkWare 핵심 엔지니어 Gidi Kaempfer

번역: StarkNet 중국 커뮤니티

개요

재귀 증명이 메인넷에 배포되어 하나의 증명으로 StarkEx 애플리케이션과 StarkNet을 확장합니다.
재귀 증명은 확장성을 높이고 비용과 지연을 줄입니다(드물게 확장성과 지연이 동기화되어 발전하며, 타협이 없습니다).
재귀 증명은 L3 및 기타 유용한 응용 프로그램을 위한 조건을 만듭니다.
재귀 증명의 블로그를 확인해 보세요, 정말 멋집니다 ?

배수 확장!

Cairo의 범용 계산을 지원하는 재귀 증명이 이제 생산에 투입되었습니다. 이는 STARK의 L2 확장 능력에 대한 중대한 향상을 나타냅니다. 단일 증명으로 이더리움의 거래 수를 빠르게 배가할 수 있습니다.

지금까지 STARK 증명은 수만 또는 수십만 개의 거래를 단일 증명으로 이더리움에 "집계"하여 확장을 이루었습니다. 재귀를 통해 이러한 많은 증명을 "집계"하여 하나의 단일 증명으로 만들 수 있습니다.

이 방법은 Cairo 기반의 여러 애플리케이션에 적용되었습니다: StarkWare의 SaaS 확장 엔진 StarkEx와 허가 없는 롤업 StarkNet에서 실행되는 애플리케이션입니다.

지금까지의 발전 과정

2020년 3월 메인넷에서 첫 번째 증명이 생성된 이후, STARK 증명은 지금까지 다양한 발전 단계를 거쳤습니다.

STARK 확장

2020년 6월, 첫 번째 STARK 확장 솔루션 StarkEx가 이더리움 메인넷에 배포되었습니다. StarkEx는 체인 외부에서 대규모 계산을 수행하고 거래의 정확성을 나타내는 STARK 증명을 생성하는 증명기를 가지고 있으며, 체인에서 증명의 정확성을 검증하는 검증기도 있습니다. 첫 번째 배포는 StarkWare 엔지니어가 처음부터 끝까지 직접 수행했기 때문에 StarkEx의 기능은 크게 제한되었습니다. 결국 우리는 증명이 범용 계산을 지원하는 프로그래밍 언어가 필요하다는 결정을 내렸습니다. 그렇게 Cairo가 탄생했습니다.

Cairo 프로그래밍 언어

2020년 여름, Cairo가 처음으로 이더리움 메인넷에 등장했습니다. Cairo는 CPU 대수 중간 코드(CPU Algebraic Intermediate Representation [AIR])로, 해당 "CPU" 명령어 집합을 검증하기 위한 단일 AIR를 포함하고 있습니다. Cairo는 더 복잡한 비즈니스 논리와 임의의 계산 명제를 위한 증명 코딩의 문을 열었으며, 더 빠르고 안전합니다. 하나의 Cairo 프로그램은 해당 애플리케이션의 실행 논리를 증명할 수 있습니다. 그러나 하나의 Cairo 프로그램은 여러 개의 이러한 애플리케이션을 집계할 수도 있으며, 이것이 SHARP입니다.

SHARP

SHARP는 공유 증명기(SHARed ProSver)로, 여러 독립 애플리케이션의 거래를 집계하고 단일 STARK 증명에서 증명할 수 있습니다. 애플리케이션은 다양한 배치 거래를 조합하여 STARK 증명의 용량을 더 빨리 채울 수 있습니다. 거래 처리 속도와 지연이 모두 향상되었습니다. 재귀 증명은 차세대 최첨단 기술로, 일부 하드 코딩된 논리뿐만 아니라 범용 계산에도 적합합니다.

재귀 증명의 모든 이점을 이해하기 위해서는 SHARP가 지금까지 어떻게 (비재귀) 증명을 수행해왔는지 더 알아볼 필요가 있습니다. 그림 1은 전형적인 비재귀 프로세스를 묘사합니다:

이 프로세스에서 명제가 점진적으로 도달합니다. 용량(또는 시간)이 특정 임계값에 도달하면 대형 조합 명제(Train)가 생성됩니다. 모든 개별 명제를 수신한 후에만 이 조합 명제를 증명할 수 있습니다. 이 증명은 상당한 시간이 소요됩니다(각 명제를 개별적으로 증명하는 데 필요한 시간의 총합과 비슷합니다).

극도로 거대한 명제를 증명하는 것은 결국 메모리와 같은 가용 계산 자원의 제한을 받습니다. 재귀 이전에는 이것이 실제로 STARK 증명의 확장성을 제한하는 큰 장애물이었습니다.

재귀 증명이란 무엇인가?

STARK 증명을 통해 명제를 증명하는 데 소요되는 시간은 명제를 실행하는 데 소요되는 시간과 대략 선형 관계를 가집니다. 또한, 만약 명제를 증명하는 데 T의 시간이 필요하다면, 증명을 검증하는 데 필요한 시간은 대략 log(T)입니다. 이는 일반적으로 "로그 압축"이라고 불립니다. 다시 말해, STARK를 사용하면 사용자가 명제를 검증하는 데 소요되는 시간이 명제를 계산하는 데 소요되는 시간보다 훨씬 적습니다.

Cairo는 범용 계산 명제를 표현할 수 있으며, 이러한 명제는 STARK 증명으로 증명되고 해당 STARK 검증기로 검증됩니다.

이것이 재귀를 실행할 기회입니다: 수천 개의 거래의 정확성을 증명하기 위해 Cairo 프로그램을 작성할 수 있을 뿐만 아니라 여러 STARK 증명을 검증하기 위해 Cairo 프로그램을 작성할 수 있습니다. 여러 "상류" 증명의 유효성을 검증하기 위해 하나의 증명을 생성할 수 있습니다. 이것이 우리가 말하는 재귀 증명입니다.

로그 압축과 증명 시간의 대략적인 선형 관계 덕분에 STARK 증명을 증명하는 데 필요한 시간은 상대적으로 짧습니다(가까운 미래에는 몇 분이면 충분할 것으로 예상됩니다).

재귀를 구현할 때 SHARP는 명제를 수신하는 즉시 이를 검증할 수 있습니다. 증명은 다양한 방식으로 반복적으로 결합되어 재귀 증명이 될 때까지 진행됩니다. 특정 시점에서 생성된 증명은 체인상의 검증자 계약에 제출됩니다. 그림 2는 전형적인 재귀 증명 패턴입니다:

이 예에서 SHARP에 네 개의 명제가 전송됩니다(아마도 네 개의 서로 다른 애플리케이션에서 발생한 것일 수 있습니다). 이러한 명제는 각각 병렬로 증명됩니다. 그런 다음 각 증명 쌍은 재귀 검증기 명제(증명 STARK 증명의 Cairo 프로그램)에 의해 검증되어 하나의 증명을 생성합니다. 이 명제는 두 개의 증명이 검증되었음을 증명합니다. 다음으로, 재귀 검증기 명제를 통해 이 두 증명을 다시 결합합니다. 이렇게 해서 네 개의 원래 명제를 모두 증명하는 증명이 생성됩니다. 이 증명은 최종적으로 체인에 제출되어 Solidity 검증기 스마트 계약에 의해 검증됩니다.

재귀 증명의 직접적인 이점

체인상의 비용 절감

우리는 여러 증명을 "압축"하여 하나로 만드는 것을 구현했습니다. 이는 각 거래의 체인상 검증 비용이 크게 낮아짐을 의미합니다(각 명제가 여러 거래를 포함할 수 있습니다).

재귀 증명을 사용하면 지금까지 증명 크기를 제한했던 계산 자원 장애(예: 메모리)를 제거할 수 있습니다. 각 명제의 용량이 제한되어 있으므로 개별적으로 증명할 수 있습니다. 따라서 재귀를 사용할 때 재귀의 유효한 조합 명제(Train)의 용량은 거의 무한하며, 각 거래의 비용을 여러 차원에서 줄일 수 있습니다.

실제 운영에서 비용 절감은 수용 가능한 지연(및 거래 도착 속도)에 따라 달라집니다. 또한, 각 증명은 일반적으로 해당 체인상의 데이터 출력을 동반하므로 단일 증명과 함께 체인에 기록되는 데이터 양도 제한적입니다. 그럼에도 불구하고 비용을 한 차원 낮추고 성능을 계속 향상시키는 것은 쉽게 달성할 수 있습니다.

지연 감소

재귀 증명 패턴은 대형 조합 명제의 지연을 줄일 수 있습니다. 두 가지 요소가 작용합니다:

수신된 명제를 병렬로 증명할 수 있습니다(거대한 조합 명제를 증명하는 것이 아닙니다).
Train의 마지막 명제가 도착할 때까지 기다릴 필요 없이 증명할 수 있습니다. 반대로, 새로운 명제가 추가되면 언제든지 증명과 결합할 수 있습니다. 즉, Train에 추가된 마지막 명제의 지연은 대략 마지막 명제를 증명하는 데 필요한 시간과 이미 "추가된" 특정 Train의 명제를 증명하는 데 필요한 시간의 합입니다.

우리는 증명 재귀 검증기 명제의 지연 문제를 적극적으로 개발하고 최적화하고 있습니다. 몇 달 내에 증명 재귀 검증기 명제가 몇 분의 범위에 도달할 것으로 예상됩니다. 따라서 효율적인 SHARP 지연은 몇 분에서 몇 시간으로 조절할 수 있으며, 지연의 길이는 각 거래의 체인상 비용에 대한 타협에 따라 달라집니다. 이는 SHARP 지연의 중대한 개선입니다.

L3 애플리케이션 촉진

Cairo로 개발된 재귀 검증기 명제는 StarkNet에 증명을 제출할 가능성을 열어줍니다. 이 명제는 StarkNet 스마트 계약에 기록될 수 있습니다. 이는 StarkNet L2 공공 네트워크에서 L3를 배포할 수 있게 해줍니다.

재귀 패턴은 L3에서 오는 집계 증명에도 적용될 수 있으며, L2의 단일 증명으로 검증됩니다. 따라서 L3도 초대규모 확장을 이룰 수 있습니다.

더 많은 유용성

재귀 적용

재귀는 비용과 성능을 더욱 확장하고자 하는 플랫폼과 애플리케이션에 더 많은 기회를 열어줍니다.

각 STARK 증명은 특정 "공개 입력"(또는 Cairo 용어의 "프로그램 출력")에 대한 명제의 유효성을 증명합니다. 개념적으로 STARK 재귀는 두 개의 입력을 가진 두 개의 증명을 하나의 두 개의 입력을 가진 증명으로 압축합니다. 다시 말해, 증명의 수는 줄어들지만 입력의 수는 변하지 않습니다. 그런 다음 입력은 일반적으로 애플리케이션이 L1의 특정 상태(예: 상태 루트 업데이트 또는 체인상의 출금 실행)를 업데이트하는 데 사용됩니다.

재귀 명제가 애플리케이션 계층에서 인식될 수 있다면, 즉 애플리케이션 자체의 의미를 인식할 수 있다면, 재귀 명제는 두 개의 증명을 하나로 압축할 수 있을 뿐만 아니라 두 개의 입력을 하나로 조합할 수 있습니다. 최종 명제는 애플리케이션 의미에 기반한 입력 조합의 유효성을 증명합니다. 이것이 바로 응용 재귀(Applicative Recursion)입니다(그림 3 예시 참조).

명제 1은 A에서 B로의 상태 업데이트를 증명하고, 명제 2는 B에서 C로의 추가 업데이트를 검증합니다. 명제 1과 명제 2의 증명은 세 번째 명제로 통합되어 A에서 C로의 업데이트를 직접 증명합니다. 유사한 재귀 논리를 적용함으로써 상태 업데이트의 비용을 매우 크게 줄이고 최종 지연 요구 사항을 충족할 수 있습니다.

응용 재귀의 또 다른 중요한 예시는 여러 증명에서 집계된 데이터를 압축하는 것입니다. 예를 들어, StarkNet과 같은 유효성 증명 롤업의 경우, L2는 매번 저장 업데이트를 L1 업데이트의 전송 데이터로 사용하여 데이터 가용성을 보장합니다. 그러나 동일한 저장 단위에 대해 여러 번 업데이트를 보낼 필요는 없습니다. 왜냐하면 증명으로 검증된 거래만이 데이터 가용성을 충족할 수 있기 때문입니다. 이 최적화는 단일 StarkNet 블록에서 수행되었습니다. 그러나 각 블록에 대해 증명을 생성함으로써 응용 재귀는 여러 L2 블록의 집계 데이터를 압축할 수 있습니다. 이는 비용을 크게 줄이고 L2의 블록 생성 시간을 단축할 수 있으며, L1 업데이트의 확장성을 희생하지 않습니다.

주목할 점은: 응용 재귀는 앞서 설명한 응용 범용 재귀와 결합하여 사용할 수 있습니다. 그러나 이 두 가지 최적화는 서로 관련이 없습니다.

체인상의 검증기 복잡성 감소

STARK 검증기의 복잡성은 검증에 사용되는 명제 유형에 따라 달라집니다. 특히 Cairo 명제의 경우, 검증기의 복잡성은 Cairo 언어에서 허용되는 특정 요소에 따라 달라지며, 더 구체적으로는 지원되는 내장 항목에 따라 달라집니다(만약 Cairo를 CPU에 비유한다면, 내장 항목은 CPU의 마이크로회로와 같습니다: 계산 실행이 너무 빈번하므로 자체 계산을 최적화해야 합니다).

Cairo 언어는 지속적으로 발전하며 점점 더 많은 유용한 내장 항목을 제공합니다. 반면에 재귀 검증기는 소수의 내장 항목만 사용하면 됩니다. 따라서 재귀 SHARP는 재귀 검증기에서 전체 언어를 지원함으로써 Cairo의 모든 명제를 성공적으로 지원할 수 있습니다. 구체적으로, L1의 Solidity 검증기는 재귀 증명만 검증하면 되므로 검증기는 Cairo 언어의 더 안정적인 하위 집합만 검증하면 됩니다: L1 검증기는 최신의 가장 안정적인 내장 항목으로 업데이트할 필요가 없습니다. 다시 말해, 명제는 지속적으로 진화하고 복잡한 검증은 L2에서 처리되며, L1 검증기는 단순하고 안정적인 명제만 검증하면 됩니다.

계산 발자국 감소

재귀 이전에는 여러 명제를 하나의 증명으로 집계하는 것이 가용 계산 인스턴스에서 증명할 수 있는 명제 크기(및 이러한 증명을 생성하는 데 필요한 시간)의 제한을 받았습니다.

재귀가 있으면 그렇게 거대한 명제를 증명할 필요가 없습니다. 더 작고 저렴한 계산 인스턴스가 더 많이 사용 가능해졌기 때문입니다(비록 계산 인스턴스가 대형 단일 증명기를 사용할 때보다 더 많이 필요할 수 있습니다). 이는 더 많은 물리적 및 가상 환경에서 증명기 인스턴스를 배포할 수 있게 해줍니다.