원제 : " 탐색 서클 STARKs "

작성자: Vitalik Buterin, Ethereum 공동 창립자

편집자: Chris, Techub News

이 기사를 이해하기 위한 전제 조건은 SNARK 및 STARK의 기본 원칙을 이미 이해하고 있다는 것입니다. 이에 대해 익숙하지 않다면 이 기사의 처음 몇 부분을 읽고 기본 사항을 이해하는 것이 좋습니다.

최근 몇 년 동안 STARK 프로토콜 설계의 추세는 더 작은 필드를 사용하는 것이었습니다. STARK의 초기 생산 구현에서는 256비트 필드, 큰 숫자(예: 21888...95617)에 대한 모듈로 산술을 사용하여 이러한 프로토콜이 타원 곡선 기반 서명과 호환되도록 했습니다. 그러나 이 설계의 효율성은 일반적인 상황에서 상대적으로 낮습니다. 이러한 큰 숫자를 처리하고 계산하는 것은 실용적이지 않으며 X(특정 숫자를 나타냄)를 처리하고 X를 4번 처리하는 등 많은 컴퓨팅 성능을 낭비하게 됩니다. , 처리 계산 시간 의 1/9 만 필요합니다. 이 문제를 해결하기 위해 STARK는 더 작은 필드(먼저 Goldilocks , 그다음 Mersenne31 및 BabyBear) 를 사용하는 방향으로 이동하기 시작했습니다.

이러한 변화로 인해 Starkware는 M3 노트북에서 초당 620,000개의 Poseidon2 해시를 증명할 수 있는 등 증명 속도가 향상되었습니다. 이는 Poseidon2를 해시 함수로 신뢰하는 한 효율적인 ZK-EVM 개발의 어려운 문제를 해결할 수 있음을 의미합니다. 그렇다면 이러한 기술은 어떻게 작동합니까? 이러한 증명은 더 작은 분야에서 어떻게 구축됩니까? 이러한 프로토콜은 Binius와 같은 솔루션 과 어떻게 비교됩니까? 이 기사에서는 특히 Mersenne31 필드와 호환되는 고유한 속성을 가진 Circle STARKs ( Starkware의 stwo , Polygon의 plonky3 및 내 자체 버전의 Python에서 구현됨)라는 체계에 중점을 두고 이러한 세부 정보를 살펴보겠습니다.

더 작은 수학 필드로 작업할 때 발생하는 일반적인 문제

해시 기반 증명(또는 모든 종류의 증명)을 생성할 때 매우 중요한 트릭은 임의의 지점에서 다항식을 평가하여 다항식의 속성을 간접적으로 확인할 수 있다는 것입니다. 이 접근 방식은 증명 프로세스를 크게 단순화할 수 있습니다. 왜냐하면 무작위 지점에서의 평가는 일반적으로 전체 다항식을 처리하는 것보다 훨씬 쉽기 때문입니다.

더 작은 수학 필드로 작업할 때 발생하는 일반적인 문제

해시 기반 증명(또는 모든 종류의 증명)을 생성할 때 매우 중요한 트릭은 임의의 지점에서 다항식을 평가하여 다항식의 속성을 간접적으로 확인할 수 있다는 것입니다. 이 접근 방식은 증명 프로세스를 크게 단순화할 수 있습니다. 왜냐하면 무작위 지점에서의 평가는 일반적으로 전체 다항식을 처리하는 것보다 훨씬 쉽기 때문입니다.

예를 들어, 증명 시스템에서 A^3 (x) + x - A (\omega*x) = x^N(ZK에서 매우 일반적인 조건)을 충족해야 하는 다항식 A에 대한 약속을 생성해야 한다고 가정합니다. -SNARK 프로토콜 증명 유형). 프로토콜은 임의의 좌표 𝑟를 선택하고 A (r) + r - A (\omega*r) = r^N을 증명하도록 요청할 수 있습니다. 그런 다음 A (r) = c를 뒤집으면 Q = \frac {A - c}{X - r}이 다항식임을 증명합니다.

프로토콜의 세부 내용이나 내부를 미리 알면 이를 우회하거나 해킹할 수 있는 방법을 찾을 수도 있습니다. 이를 달성하기 위한 구체적인 조치나 방법은 다음에 언급될 수 있습니다. 예를 들어, 방정식 A (\omega * r)를 만족시키기 위해 A (r)을 0으로 설정한 다음 A를 이 두 점을 통과하는 직선으로 설정할 수 있습니다.

이러한 공격을 방지하려면 공격자가 A를 제공한 후 r을 선택해야 합니다. Fiat-Shamir 는 특정 매개변수를 일부 해시 값으로 설정하여 공격을 피하기 위해 프로토콜의 보안을 강화하는 데 사용되는 기술입니다. 매개변수는 다음에서 와야 합니다. 공격자가 이러한 매개변수를 예측하거나 추측할 수 없도록 충분히 큰 세트이므로 시스템 보안이 향상됩니다.

2019년 타원 곡선 기반 프로토콜과 STARK에서 문제는 간단합니다. 모든 수학 연산은 256비트 숫자에서 수행되므로 r을 임의의 256비트 숫자로 선택할 수 있으므로 . 그러나 더 작은 필드의 STARK에서는 문제에 직면합니다. 선택할 수 있는 r 값은 약 20억 개뿐이므로 증명을 위조하려는 공격자는 20억 번만 시도하면 됩니다. 많은 작업이 필요하지만 단호한 공격자에게는 여전히 가능합니다!

이 문제에 대한 두 가지 해결책이 있습니다.

다중 무작위 검사를 수행하는 가장 간단하고 효율적인 방법은 하나의 좌표에서 검사하는 대신 4개의 무작위 좌표에서 검사를 반복하는 것입니다. 이는 이론적으로는 가능하지만 효율성 문제가 있습니다. 특정 값보다 작은 차수의 다항식을 다루고 특정 크기의 도메인에서 작업하는 경우 공격자는 실제로 해당 위치에서 정상적으로 보이는 악의적인 다항식을 구성할 수 있습니다. 따라서 프로토콜을 성공적으로 위반할 수 있는지 여부는 확률적인 문제이므로 전반적인 보안을 강화하고 공격자가 공격으로부터 효과적으로 방어할 수 있도록 확인 라운드 수를 늘려야 합니다.

이것은 또 다른 해결책으로 이어집니다: 확장 필드는 복소수와 비슷하지만 유한 필드를 기반으로 합니다. 우리는 α\alphaα로 표시된 새로운 값을 도입하고 α2=some value\alpha^2 = \text {some value}α2=some value와 같은 특정 관계를 만족한다고 선언합니다. 이러한 방식으로 우리는 유한 필드에서 더 복잡한 작업을 수행할 수 있는 새로운 수학적 구조를 만듭니다. 이 확장된 영역에서 곱셈의 계산은 새로운 값 α\alphaα를 사용한 곱셈이 됩니다. 이제 단일 숫자뿐만 아니라 확장된 도메인의 값 쌍에 대해 작업을 수행할 수 있습니다. 예를 들어 Mersenne 또는 BabyBear와 같은 분야에서 작업하는 경우 이러한 확장을 통해 더 많은 가치를 선택할 수 있어 보안이 향상됩니다. 필드 크기를 더 늘리려면 동일한 기술을 반복적으로 적용할 수 있습니다. 이미 α\alphaα를 사용했기 때문에 새로운 값을 정의해야 합니다. Mersenne31에서는 α2=어떤 값\alpha^2 = \text {어떤 값}α2=어떤 값이 되도록 α\alphaα를 선택하여 표현됩니다.

코드 ( Karatsuba 로 개선 가능)

코드 ( Karatsuba 로 개선 가능)

도메인을 확장함으로써 이제 보안 요구 사항을 충족하는 충분한 값을 선택할 수 있게 되었습니다. ddd보다 낮은 차수의 다항식을 처리하는 경우 각 라운드는 104비트 보안을 제공할 수 있습니다. 이는 우리가 적절한 보안을 갖추고 있음을 의미합니다. 128비트와 같은 더 높은 보안 수준이 필요한 경우 프로토콜에 추가 계산 작업을 추가하여 보안을 강화할 수 있습니다.

확장된 도메인은 실제로 FRI(Fast Reed-Solomon Interactive) 프로토콜과 임의의 선형 조합이 필요한 기타 시나리오에서만 사용됩니다. 대부분의 수학적 연산은 여전히 ​​기본 필드(보통 모듈로 ppp 또는 qqq 필드)에서 수행됩니다. 또한 거의 모든 해시된 데이터가 기본 필드에서 수행되므로 값당 4바이트만 해시됩니다. 이렇게 하면 보안 강화가 필요할 때 더 큰 필드를 사용하는 동시에 작은 필드의 효율성을 활용할 수 있습니다.

정기금

SNARK 또는 STARK를 구축할 때 첫 번째 단계는 일반적으로 산술화입니다. 이는 모든 계산 문제를 일부 변수와 계수가 다항식인 방정식으로 변환하는 것입니다. 구체적으로 이 방정식은 일반적으로 P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0처럼 보입니다. 여기서 P는 다항식이고 Z는 주어진 매개변수입니다. 솔버는 X 및 Y 값을 제공해야 합니다. 그러한 방정식이 있으면 해당 방정식에 대한 해는 기본 계산 문제에 대한 해와 일치합니다.

해법이 있다는 것을 증명하려면, 생각해낸 값이 실제로 합법적인 다항식(분수와 반대이거나 어떤 곳에서는 하나의 다항식처럼 보이고 다른 곳에서는 다른 다항식처럼 보이는 등)임을 보여야 합니다. 그리고 이 다항식은 특정 최대 차수를 갖습니다. 이를 위해 단계적으로 적용되는 확률적 선형 결합 기술을 사용합니다.

본질적으로 무슨 일이 일어나고 있는지는 B가 짝수 계수 A를 분리하고 𝐶가 홀수 계수를 분리한다는 것입니다. B와 C가 주어지면 원래 다항식 A를 복구할 수 있습니다. A(x) = B(x^2) + xC(x^2). A의 차수가 실제로 2^{20}보다 작은 경우 B와 C의 차수는 각각 A의 차수와 A의 차수에서 1을 뺀 값이 됩니다. 짝수항과 홀수항을 조합해도 차수가 증가하지 않기 때문입니다. D는 B와 C의 임의의 선형결합이므로 D의 차수도 A의 차수여야 하며, 이는 D의 차수를 통해 A의 차수가 요구사항을 충족하는지 여부를 확인할 수 있게 해줍니다.

첫째, FRI는 다항식이 d차임을 증명하는 문제를 다항식이 d/2차임을 증명하는 문제로 줄여 검증 과정을 단순화한다. 이 프로세스는 여러 번 반복될 수 있으므로 매번 문제가 절반으로 단순화됩니다.

FRI는 이러한 단순화 과정을 반복하여 작동합니다. 예를 들어 다항식의 차수가 d라는 것을 증명하는 것으로 시작했다면 일련의 단계를 거쳐 결국 다항식의 차수가 d/2라는 것을 증명하게 됩니다. 단순화할 때마다 결과 다항식의 차수는 점차 감소합니다. 단계의 출력이 예상된 다항식 수준이 아닌 경우 이번 검사는 실패합니다. 누군가가 이 기법을 통해 d차가 아닌 다항식을 밀어내려고 하면 두 번째 출력에서 ​​그 차수는 일정 확률로 기대에 미치지 못하고 세 번째 라운드에서는 불일치할 가능성이 더 커집니다. 그리고 마지막으로 검사가 실패합니다. 이 설계는 요구 사항을 충족하지 않는 입력을 효과적으로 감지하고 거부할 수 있습니다. 데이터 세트가 대부분의 위치에서 d차 다항식과 같으면 데이터 세트는 FRI 검증을 통과할 가능성이 높습니다. 그러나 이러한 데이터 세트를 구성하려면 공격자가 실제 다항식을 알아야 하므로 약간의 결함이 있는 증명이라도 증명자가 "실제" 증명을 생성할 수 있음을 보여줍니다.

여기서 무슨 일이 일어나고 있는지, 그리고 이 모든 것이 작동하는 데 필요한 속성을 자세히 살펴보겠습니다. 각 단계에서 다항식의 차수를 절반으로 줄이고, 점 집합(관심 있는 점 집합)도 절반으로 줄입니다. 전자는 FRI(Fast Reed-Solomon Interactive) 프로토콜이 제대로 작동하도록 만드는 핵심입니다. 후자는 알고리즘을 매우 빠르게 실행합니다. 각 라운드의 크기가 이전 라운드에 비해 절반으로 줄어들기 때문에 총 계산 비용은 O(N*log(N)) 대신 O(N)입니다.

도메인의 점진적인 축소를 달성하기 위해 2대1 매핑이 사용됩니다. 즉, 각 지점이 두 지점 중 하나에 매핑됩니다. 이 매핑을 통해 데이터세트 크기를 절반으로 줄일 수 있습니다. 이 2대1 매핑의 중요한 장점은 반복 가능하다는 것입니다. 즉, 이 매핑을 적용하면 결과 결과 집합은 여전히 ​​동일한 속성을 유지합니다. 곱셈 하위 그룹으로 시작한다고 가정합니다. 이 부분군은 모든 원소 x가 집합 내에서도 배수의 2x를 갖는 집합 S입니다. 집합 S를 제곱하면(즉, 집합의 각 요소 x를 x^2에 매핑) 새 집합 S^2도 동일한 속성을 유지합니다. 이 작업을 통해 결국 하나의 값만 남을 때까지 데이터세트의 크기를 계속해서 줄일 수 있습니다. 이론적으로는 데이터 세트를 하나의 값으로 축소할 수 있지만 실제로는 더 작은 세트에 도달하기 전에 중지하는 것이 일반적입니다.

이 작업은 원 둘레에 선(예: 선분 또는 호)을 늘려 원 주위를 두 번 회전시키는 프로세스로 생각할 수 있습니다. 예를 들어, 점이 원주의 x도에 위치한 경우 이 작업 후에는 2x도만큼 이동합니다. 0도에서 179도까지 원의 모든 점은 180도에서 359도까지 대응하는 점을 가지며, 이 두 점은 일치합니다. 즉, x도에서 2x도로 점을 매핑하면 x+180도 위치와 일치하게 됩니다. 이 과정은 반복될 수 있습니다. 즉, 원의 점을 새 위치로 이동할 때마다 이 매핑 작업을 여러 번 적용할 수 있습니다.

매핑 기법이 효과적이려면 원래 곱셈 하위 그룹의 크기가 요인으로 2의 큰 거듭제곱을 가져야 합니다. BabyBear는 최대 곱셈 하위 그룹이 0이 아닌 모든 값을 포함하도록 특정 값의 특정 모듈러스를 갖는 시스템입니다. 따라서 하위 그룹의 크기는 2k−1입니다(여기서 k는 모듈러스의 자릿수입니다). 이 크기의 하위 그룹은 매핑 작업을 반복적으로 적용하여 다항식의 차수를 효율적으로 줄일 수 있으므로 위 기술에 매우 적합합니다. BabyBear에서는 크기가 2^k인 하위 그룹을 선택한 다음(또는 전체 집합을 사용) FRI 방법을 적용하여 다항식의 차수를 점차적으로 15로 줄이고 마지막에 다항식의 차수를 확인할 수 있습니다. 이 방법은 계수의 속성과 곱셈 하위 그룹의 크기를 활용하여 계산 프로세스를 매우 효율적으로 만듭니다. Mersenne31은 곱셈 하위 그룹의 크기가 2^31 - 1이 되는 모듈러스를 갖는 또 다른 시스템입니다. 이 경우 곱셈 하위 그룹의 크기는 인수로 2의 거듭제곱만 가지므로 한 번만 2로 나눌 수 있습니다. 위의 기술은 더 이상 후속 처리에 적용할 수 없습니다. 즉, FFT는 BabyBear와 같은 효과적인 다항식 차수 감소에 사용할 수 없습니다.

Mersenne31 필드는 기존 32비트 CPU/GPU 연산에 대한 산술 연산에 매우 적합합니다. 모듈러스 속성(예: 2^{31} - 1)으로 인해 효율적인 비트 연산을 사용하여 많은 작업을 완료할 수 있습니다. 두 숫자를 더한 결과가 모듈러스를 초과하는 경우 모듈러스 연산을 통해 결과를 이동하여 이를 줄일 수 있습니다. 적절한 범위로. 변위 작업은 매우 효율적인 작업입니다. 곱셈 연산에서는 특수 CPU 명령어(종종 고차 시프트 명령어라고 함)를 사용하여 결과를 처리할 수 있습니다. 이러한 명령어는 곱셈의 고차 부분을 효율적으로 계산할 수 있으므로 연산 효율성이 향상됩니다. Mersenne31 도메인에서는 위의 특성으로 인해 BabyBear 도메인에 비해 산술 연산 속도가 약 1.3배 빠릅니다. Mersenne31은 더 큰 계산 효율성을 제공합니다. Mersenne31 도메인에서 FRI를 구현할 수 있다면 계산 효율성이 크게 향상되고 FRI 적용이 더욱 효율적이게 됩니다.

서클금

서클금

이것이 Circle STARK 의 멋진 점입니다. 소수 p가 주어지면 유사한 2대1 속성을 갖는 크기 p의 그룹을 찾을 수 있습니다. 이 모집단은 특정 조건을 충족하는 모든 점으로 구성됩니다(예: x^2 mod p가 특정 값과 같은 점 집합).

이러한 점은 덧셈 패턴을 따르는데, 최근에 삼각법 이나 복소수 곱셈 과 관련된 작업을 수행해 본 적이 있다면 친숙해 보일 수 있습니다.

(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)

이중 형태는 다음과 같습니다.

2 * (x, y) = (2x^2 - 1, 2xy)

이제 이 원의 홀수 점에 초점을 맞춰 보겠습니다.

먼저 모든 점을 직선으로 수렴합니다. 일반 FRI에서 사용하는 B(x²) 및 C(x²) 공식의 동등한 형식은 다음과 같습니다.

f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}

그런 다음 무작위 선형 조합을 수행하여 x선의 하위 집합에 대해 정의된 1차원 P(x) 다항식을 얻을 수 있습니다.

두 번째 라운드부터 매핑이 다음과 같이 변경됩니다.

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

두 번째 라운드부터 매핑이 다음과 같이 변경됩니다.

f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}

이 매핑은 실제로 매번 위 세트의 크기를 절반으로 줄입니다. 여기서 일어나는 일은 각 x가 어떤 의미에서는 (x, y)와 (x, -y)의 두 지점을 나타낸다는 것입니다. 그리고 (x → 2x^2 - 1)은 위의 포인트 배가 규칙입니다. 따라서 원 위의 반대되는 두 점의 x 좌표를 곱한 점의 x 좌표로 변환합니다.

예를 들어 오른쪽에서 원의 두 번째 값인 2를 가져와 매핑 2 → 2 (2^2) - 1 = 7을 적용하면 결과는 7입니다. 원래 원으로 돌아가면 (2, 11)은 오른쪽에서 세 번째 점이므로 두 배로 늘리면 오른쪽에서 여섯 번째 점인 (7, 13)을 얻게 됩니다.

이는 2차원에서 수행될 수도 있지만 1차원에서 작동하면 프로세스가 더 효율적입니다.

원형 FFT

FRI와 밀접하게 관련된 알고리즘은 FFT 입니다. 이는 n보다 작은 차수 다항식의 n 평가를 다항식의 n 계수로 변환합니다. FFT의 과정은 각 단계에서 무작위 선형 조합 f_0과 f_1을 생성하는 대신 FFT가 반복적으로 절반 크기 FFT를 수행하고 FFT(f_0)의 출력을 짝수 계수로 처리한다는 점을 제외하면 FRI와 유사합니다. FFT(f_1)를 홀수 계수로 사용합니다.

Circle 그룹은 FRI와 유사한 방식으로 구성된 FFT도 지원합니다. 그러나 주요 차이점은 Circle FFT(및 Circle FRI)가 처리하는 객체가 엄밀히 말하면 다항식이 아니라는 것입니다. 대신, 수학적으로 Riemann-Roch 공간 이라고 불리는 공간입니다. 이 경우 다항식은 모듈로 원형( x^2 + y^2 - 1 = 0 )입니다. 즉, x^2 + y^2 - 1의 배수는 0으로 처리됩니다. 또 다른 생각은 다음과 같습니다. y의 거듭제곱만 허용합니다. y^2 항이 나타나면 이를 1 - x^2 로 바꿉니다.

이는 또한 Circle FFT의 계수 출력이 일반 FRI와 같은 단항식이 아니라는 것을 의미합니다(예를 들어 일반 FRI가 [6, 2, 8, 3]을 출력하는 경우 P(x) = 3x^3 + 8x를 의미함을 알 수 있습니다. ^2 + 2x + 6). 이와 대조적으로 Circle FFT의 계수는 Circle FFT 기준에 따라 다릅니다. {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}

좋은 소식은 개발자로서 이 문제를 거의 완전히 무시할 수 있다는 것입니다. STARK는 계수를 알 것을 요구하지 않습니다. 대신, 특정 도메인에 대한 평가 값 세트로 다항식을 저장하기만 하면 됩니다. FFT의 유일한 용도는 낮은 수준의 확장(Riemann-Roch 공간과 유사)을 수행하는 것입니다. N 값이 주어지면 k*N 값이 모두 동일한 다항식에서 생성됩니다. 이 경우 FFT를 사용하여 계수를 생성하고 이러한 계수에 (k-1) n개의 0을 추가한 다음 역 FFT를 사용하여 더 큰 평가 값 세트를 얻을 수 있습니다.

Circle FFT는 FFT의 유일한 특수 유형이 아닙니다. 타원 곡선 FFT는 모든 유한 필드(소수 필드, 이진 필드 등)에서 작동할 수 있기 때문에 더욱 강력합니다. 그러나 ECFFT는 더 복잡하고 효율성이 떨어지므로 p = 2^{31}-1에서 Circle FFT를 사용할 수 있으므로 이를 사용하기로 선택합니다.

이제부터 Circle STARK의 구현을 일반 STARK와 다르게 만드는 좀 더 모호한 세부 사항에 대해 살펴보겠습니다.

지수화

이제부터 Circle STARK의 구현을 일반 STARK와 다르게 만드는 좀 더 모호한 세부 사항에 대해 살펴보겠습니다.

지수화

STARK 프로토콜에서 일반적인 작업은 특정 포인트에 대해 몫 작업을 수행하는 것입니다. 이러한 포인트는 의도적으로 또는 무작위로 선택할 수 있습니다. 예를 들어, P(x) = y임을 증명하려면 다음 단계를 수행하면 됩니다.

몫 계산: 다항식 P(x)와 상수 y가 주어지면 몫 Q ={P - y}/{X - x}를 계산합니다. 여기서 X는 선택한 점입니다.

다항식 증명: Q가 분수 값이 아닌 다항식임을 증명하십시오. 이로써 P(x)=y가 성립함을 증명하였다.

또한 DEEP-FRI 프로토콜 에서는 평가 포인트를 무작위로 선택하여 Merkle 분기 수를 줄여 FRI 프로토콜의 보안성과 효율성을 향상시킵니다.

원 그룹의 STARK 프로토콜을 다룰 때 단일 지점을 통과할 수 있는 선형 함수가 없기 때문에 기존의 몫 연산 방법을 대체하기 위해 다른 기술을 사용해야 합니다. 이를 위해서는 일반적으로 원 그룹의 고유한 기하학적 특성을 사용하여 새로운 알고리즘을 설계해야 합니다.

원 그룹에서 특정 점(P_x, P_y)에 접하는 접선 함수를 구성할 수 있지만 이 함수는 점을 통해 다중도 2를 갖습니다. 즉, 다항식은 다음과 같은 선형 함수의 A 배수가 됩니다. 그 시점에서 단순히 0이 되는 것보다 더 엄격한 조건을 충족합니다. 따라서 평가 결과를 한 시점에 증명할 수는 없습니다. 그러면 우리는 이것을 어떻게 처리해야 할까요?

우리는 이 도전을 받아들이고 두 가지 지점을 평가하여 이를 증명해야 했으며, 이를 통해 우리가 집중할 필요가 없는 더미 지점을 추가해야 했습니다.

선 함수: ax + by + c. 이를 방정식으로 바꾸고 강제로 0이 되도록 하면 고등학교 수학에서 표준 형식이라고 하는 선으로 인식할 수 있습니다.

x_1에서 y_1, x_2에서 y_2와 동일한 다항식 P가 있는 경우 x_1에서 y_1, x_2에서 y_2와 동일한 보간 함수 L을 선택할 수 있습니다. 이는 간단히 L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1로 표현할 수 있습니다.

그런 다음 L을 빼고(두 지점에서 P - L을 0으로 만듦) L(즉, x_2 - x_1 사이의 선형 함수)로 P가 x_1에서 y_1, x_2에서 y_2와 같음을 증명합니다. L로 나누어 몫 Q가 다음임을 증명합니다. 다항식.

사라지는 다항식

사라지는 다항식

STARK에서 증명하려는 다항 방정식은 일반적으로 C (P (x), P ({next}(x))) = Z (x) ⋅ H (x) 와 같습니다. 여기서 Z (x)는 A입니다. 원래 평가 영역 전체에 걸쳐 0과 같은 다항식. 일반 STARK에서 이 함수는 x^n - 1입니다. 원형 STARK에서 해당 기능은 다음과 같습니다.

Z_1 (x,y) = y

Z_2 (x,y) = x

Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1

접기 함수에서 소실 다항식을 도출할 수 있습니다. 일반 STARK에서는 x → x^2 를 재사용하고 원형 STARK에서는 x → 2x^2 - 1 을 재사용합니다. 하지만 첫 번째 라운드의 경우 첫 번째 라운드가 특별하기 때문에 다르게 수행합니다.

역방향 비트 순서

STARK에서 다항식은 일반적으로 "자연적인" 순서(예: P(1), P(Ω), P(Ω2),…, P(Ωn−1))가 아니라 내가 역순이라고 부르는 순서로 평가됩니다. 역방향 비트 순서:

P (\omega^{\frac {3n}{8}})

n=16으로 설정하고 평가할 Ω의 거듭제곱에만 초점을 맞추면 목록은 다음과 같습니다.

{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

이 정렬의 주요 속성은 FRI 평가 프로세스 초기에 함께 그룹화된 값이 정렬에서 인접해 있다는 것입니다. 예를 들어 FRI 그룹 x 및 -x의 첫 번째 단계입니다. n = 16인 경우 Ω^8 = -1이며, 이는 P(Ω^i) ) 및 ( P(-Ω^i) = P(Ω^{i+8})\)를 의미합니다. 보시다시피, 이들은 정확히 서로 옆에 있는 쌍입니다. FRI 그룹의 두 번째 단계는 P(Ω^i), P(Ω^{i+4}), P(Ω^{i+8}) 및 P(Ω^{i+12})입니다. 이것들은 우리가 4명으로 구성된 그룹에서 보는 것과 정확히 같습니다. 이렇게 하면 함께 접힌 값(또는 한 번에 k 라운드를 접는 경우 모든 2^k 값에 대해)에 대한 Merkle 증명을 제공할 수 있으므로 FRI의 공간 효율성이 더 높아집니다.

원 STARK에서는 접기 구조가 약간 다릅니다. 첫 번째 단계에서는 (x, y)를 (x, -y)와 쌍으로 묶고, 다음 단계에서는 x를 -x와 쌍으로 만듭니다. q와 함께, Q^i(p) = -Q^i(q)가 되도록 p와 q를 선택합니다. 여기서 Q^i는 x → 2x^2-1 i번 반복되는 매핑입니다. 원에서의 위치 측면에서 점을 생각하면 각 단계에서 첫 번째 점이 마지막 점과 짝을 이루고, 두 번째 점이 두 번째에서 마지막 점과 짝을 이루는 것처럼 보입니다.

이 접기 구조를 반영하도록 역방향 비트 순서를 조정하려면 마지막 비트를 제외한 모든 비트를 역방향으로 수행해야 합니다. 마지막 비트를 유지하고 이를 사용하여 다른 비트를 뒤집을지 여부를 결정합니다.

크기 16의 접힌 역방향 비트 순서는 다음과 같습니다.

{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}

앞선 원을 보면 오른쪽부터 0, 15, 8, 7번 지점(오른쪽부터 반시계방향)이 (x, y), (x, -y), (-x, - y)와 (-x, y)가 바로 우리에게 필요한 것입니다.

앞선 원을 보면 오른쪽부터 0, 15, 8, 7번 지점(오른쪽부터 반시계방향)이 (x, y), (x, -y), (-x, - y)와 (-x, y)가 바로 우리에게 필요한 것입니다.

능률

Circle STARK(및 일반적으로 31비트 프라임 STARK)에서 이러한 프로토콜은 매우 효율적입니다. Circle STARK에서 입증된 계산에는 일반적으로 여러 유형의 계산이 포함됩니다.

1. 기본 산술: 계산과 같은 비즈니스 논리에 사용됩니다.

2. 기본 산술: 포세이돈 과 같은 해시 함수와 같은 암호화에 사용됩니다.

3. 조회 매개변수 : 테이블에서 값을 읽어 다양한 계산을 구현하는 일반적이고 효율적인 계산 방법입니다.

효율성의 주요 척도는 컴퓨팅 추적에서 유용한 작업을 수행하기 위해 전체 공간을 완전히 활용하고 있는지, 아니면 여유 공간을 많이 남겨두고 있는지 여부입니다. 큰 필드에 대한 SNARK에는 여유 공간이 많은 경우가 많습니다. 비즈니스 논리 및 조회 테이블에는 종종 작은 숫자에 대한 계산이 포함됩니다(이러한 숫자는 N보다 작은 경향이 있습니다. 여기서 N은 계산의 총 단계 수이므로 2^{25 }) 미만으로 연습하지만 여전히 2^{256} 비트 크기의 필드를 사용하는 데 드는 비용을 지불해야 합니다. 여기서 필드의 크기는 2^{31}이므로 낭비되는 공간은 크지 않습니다. SNARK(예: Poseidon)용으로 설계된 낮은 산술 복잡성 해시는 모든 필드에서 추적에 있는 모든 숫자의 모든 비트를 최대한 활용합니다.

Binius는 서로 다른 크기의 필드를 혼합하여 비트 패킹을 더 효율적으로 수행할 수 있으므로 Circle STARK보다 더 나은 솔루션입니다. Binius는 또한 조회 테이블의 오버헤드 없이 32비트 추가를 수행할 수 있는 옵션을 제공합니다. 그러나 이러한 장점은 개념을 더 복잡하게 만드는 대가로 발생하는 반면 Circle STARK(및 일반 BabyBear 기반 STARK)는 개념적으로 훨씬 간단합니다.

결론: Circle STARK에 대한 나의 생각

Circle STARK는 STARK보다 개발자에게 더 이상 복잡하지 않습니다. 구현 과정에서 위에서 언급한 세 가지 문제는 기본적으로 기존 FRI와의 차이점입니다. Circle FRI가 작동하는 다항식 뒤에 숨은 수학은 매우 복잡하고 수학을 이해하고 감상하는 데 시간이 걸리지만 실제로 이러한 복잡성은 개발자가 직접 느끼지 못할 정도로 숨겨져 있습니다.

Circle FRI 및 Circle FFT를 이해하는 것은 다른 특수 FFT를 이해하는 관문이 될 수도 있습니다. 특히 Binius 및 이전 LibSTARK 에서 사용하는 것과 같은 이진 도메인 FFT는 물론 타원 곡선 FFT 사용 과 같은 좀 더 복잡한 구성도 가능합니다. -다양한 매핑은 타원 곡선 점 작업과 잘 결합될 수 있습니다.

Mersenne31, BabyBear 및 Binius와 같은 바이너리 도메인 기술을 결합하면 STARK 기본 계층의 효율성 한계에 접근하고 있는 것처럼 느껴집니다. 현시점에서 STARK의 최적화 방향은 다음과 같은 점에 초점이 맞춰질 것으로 예측합니다.

효율성 극대화를 위한 해시 함수 및 서명의 산술화: 해시 함수 및 디지털 서명과 같은 기본적인 암호화 기본 요소를 가장 효율적인 형태로 최적화하여 STARK 증명에 사용될 때 최고의 성능을 달성할 수 있습니다. 이는 계산 노력을 줄이고 효율성을 높이기 위해 이러한 기본 요소에 대한 특별한 최적화를 의미합니다.

더 많은 병렬화를 가능하게 하는 재귀 구성: 재귀 구성은 STARK 증명 프로세스를 다양한 수준에 재귀적으로 적용하여 병렬 처리 기능을 향상시키는 것을 의미합니다. 이러한 방식으로 컴퓨팅 리소스를 보다 효율적으로 사용할 수 있으며 증명 프로세스를 가속화할 수 있습니다.

더 많은 병렬화를 가능하게 하는 재귀 구성: 재귀 구성은 STARK 증명 프로세스를 다양한 수준에 재귀적으로 적용하여 병렬 처리 기능을 향상시키는 것을 의미합니다. 이러한 방식으로 컴퓨팅 리소스를 보다 효율적으로 사용할 수 있으며 증명 프로세스를 가속화할 수 있습니다.

가상 머신을 연산하여 개발자 환경 개선: 가상 머신을 연산하면 개발자가 컴퓨팅 작업을 보다 효율적이고 간단하게 생성하고 실행할 수 있습니다. 여기에는 STARK 증명에 사용할 가상 머신을 최적화하고 스마트 계약 또는 기타 컴퓨팅 작업을 구축하고 테스트할 때 개발자 경험을 개선하는 것이 포함됩니다.