비탈릭의 새로운 작품, 서클스타크를 탐구하다

원제: "서클 스타크 탐색하기" 이더리움 공동창립자 비탈릭 부테린 글, 크리스 편집, 테크큐브뉴스

이 글을 이해하기 위한 가정은 여러분이 이미 스나크와 스탁의 기본을 이해하고 있다는 것입니다. 익숙하지 않다면 이 글의 처음 몇 섹션을 읽고 기본 사항을 이해하는 것이 좋습니다.

최근 몇 년 동안 STARK 프로토콜 설계의 추세는 더 작은 필드로 이동하는 것이었습니다. STARKs의 초기 프로덕션 구현은 256비트 필드, 즉 큰 숫자(예: 21888.... .95617), 즉 타원 곡선 기반 서명과 호환되는 256비트 필드를 사용했습니다. 그러나 이 설계는 상대적으로 비효율적이며 일반적으로 이러한 큰 숫자의 계산을 처리하는 데 실용적이지 않고, 예를 들어 특정 숫자를 나타내는 X를 처리하는 것과 계산 시간이 9분의 1밖에 걸리지 않는 X를 4배로 하는 데 많은 산술이 낭비됩니다. 이 문제를 해결하기 위해 스타크는 처음에는 <골디락스>, 그다음에는 <메르센31>, <베이비베어> 등 작은 필드를 사용하는 방식으로 전환하기 시작했습니다.

이 같은 전환을 통해 다음과 같이 증명 속도가 빨라졌습니다. Starkware는 M3 노트북에서 초당 620,000개의 포세이돈2 해시를 증명할 수 있었습니다. 즉, 포세이돈2를 해시 함수로 신뢰할 수 있다면 효율적인 ZK-EVM 개발의 과제를 해결할 수 있습니다. 그렇다면 이러한 기술은 어떻게 작동할까요? 이러한 증명은 어떻게 더 작은 필드에 구축될까요? 이러한 프로토콜은 비니우스 같은 솔루션과 어떻게 비교될까요? 이 백서에서는 이러한 세부 사항을 살펴보고, 특히 Mersenne31 필드와 호환되는 고유한 속성을 가진 Circle STARKs(Starkware의 stwo, Polygon의 plonky3, 파이썬으로 구현된 제 버전)라는 체계에 초점을 맞춰 살펴봅니다. 고유 프로퍼티가 있는 Mersenne31 필드와 호환됩니다.

작은 수학 필드를 사용할 때 흔히 발생하는 문제

해시 기반 증명(또는 모든 종류의 증명)을 만들 때 매우 중요한 요령은 임의의 지점에서 다항식의 결과를 평가하여 다항식을 증명하는 것입니다. 이를 통해 다항식의 속성을 간접적으로 검증할 수 있습니다. 이 방법은 일반적으로 전체 다항식을 다루는 것보다 임의의 지점에서 평가하는 것이 훨씬 쉽기 때문에 증명 과정을 크게 간소화할 수 있습니다.

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

프로토콜의 세부 사항이나 내부 메커니즘을 미리 알고 있다면 이를 우회하거나 깨뜨리는 방법을 찾을 수 있습니다. 이를 달성하기 위한 구체적인 작업이나 방법은 다음에 언급할 수 있습니다. 예를 들어, A(\오메가 * r) 방정식을 만족시키기 위해 A(r)를 0으로 설정한 다음 A가 두 점을 통과하는 직선이 되도록 할 수 있습니다.

이러한 공격을 방지하려면 공격자가 A를 제공한 후 r을 선택해야 합니다. (피아트-샤미르는 특정 매개변수를 특정 해시값으로 설정하여 공격을 피하기 위해 프로토콜의 보안을 강화하는 데 사용되는 기법입니다. 선택한 매개변수는 공격자가 예측하거나 추측할 수 없을 정도로 충분히 큰 집합이어야 시스템의 보안을 강화할 수 있습니다.

타원 곡선 기반 프로토콜과 2019년형 STARK에서는 모든 수학적 연산이 256비트 숫자로 수행되기 때문에 r을 임의의 256비트 숫자로 선택해도 문제가 없을 수 있습니다. 그러나 더 작은 필드의 STARK에서는 선택할 수 있는 r의 값이 약 20억 개에 불과하므로 증명을 위조하려는 공격자는 20억 번만 시도하면 되는데, 이는 많은 작업이지만 결단력 있는 공격자에게는 여전히 완벽하게 해낼 수 있는 문제입니다!

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

• 복수의 무작위 검사 수행

• < p style="text-align: 왼쪽;">필드 확장

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

이것은 복소수와 유사하지만 유한 도메인을 기반으로 하는 확장 도메인이라는 또 다른 해결책으로 이어집니다. α\알파α로 표시되는 새로운 값을 도입하고 α2=어떤 값\알파^2 = \text {어떤 값}α2=어떤 값과 같은 어떤 관계를 만족한다고 선언합니다. 이런 식으로 유한 필드에서 더 복잡한 연산을 수행할 수 있는 새로운 수학적 구조를 만들 수 있습니다. 이 확장된 영역에서 곱셈 계산은 새로운 값 α\알파α를 사용한 곱셈이 됩니다. 이제 개별 숫자가 아닌 확장된 영역에서 값의 쌍을 조작할 수 있습니다. 예를 들어, 메르센이나 베이비베어와 같은 필드에서 작업하는 경우 이러한 확장을 통해 더 다양한 값을 선택할 수 있으므로 보안이 강화됩니다. 필드의 크기를 더 늘리려면 동일한 기법을 반복해서 적용할 수 있습니다. 이미 α\알파α를 사용했으므로 α2=어떤 값\알파^2 = \text {어떤 값}α2=어떤 값이 되도록 α\알파α를 선택해 메르센31에서 표현되는 새로운 값을 정의해야 합니다.

코드(Karatsuba로 개선 가능)

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

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

정규 FRI

일반적으로 SNARK 또는 STARK를 구축할 때 첫 번째 단계는 산술화입니다. 이는 임의의 계산 문제를 특정 변수와 계수가 다항식인 방정식으로 변환하는 것입니다. 구체적으로 이 방정식은 일반적으로 P (X,Y,Z) = 0P (X,Y,Z) = 0P (X,Y,Z) = 0으로, 여기서 P는 다항식이고 X, Y, Z는 주어진 파라미터이며 솔버가 X와 Y의 값을 제공하면 다음과 같은 방정식이 됩니다. 이러한 방정식을 구할 수 있으면 해당 방정식의 해는 기본 계산 문제의 해에 해당합니다.

해법이 있다는 것을 증명하려면 제안하는 값이 실제로 합리적인 다항식(분수 또는 어떤 곳에서는 하나의 다항식처럼 보이지만 다른 곳에서는 다른 다항식으로 보이는 다항식과 반대)이며 이러한 다항식이 일정한 최대 차수를 가지고 있음을 보여 주어야 합니다. 이를 위해 단계별로 적용되는 확률적 선형 조합 트릭을 사용합니다.

• 평가된 다항식 A가 있고 그 차수가 <2^{20}보다 작다는 것을 증명하고 싶다고 가정해 보겠습니다.

• 다항식 B (x^2) = A (x) + A (-x) 및 C (x^2) = \frac {A (x) - A (-x)}{x}

• D는 B의 임의 선형 조합입니다. C의 임의의 선형 조합, 즉 D = B + rCD = B + rCD = B + rC, 여기서 r은 임의의 계수입니다.

본질적으로, 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를 증명하는 문제로 축소하여 검증 과정을 간소화합니다. 이 과정은 여러 번 반복할 수 있으며, 매번 문제를 절반으로 단순화할 수 있습니다.

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

이제 여기서 어떤 일이 일어나고 있는지, 그리고 이 모든 것을 작동시키는 데 필요한 속성을 더 자세히 살펴봅시다. 각 단계에서 다항식의 수를 절반으로 줄이고 포인트 세트(우리가 보고 있는 점의 집합)도 절반으로 줄입니다. 전자는 FRI(Fast Reed-Solomon Interactive) 프로토콜을 작동시키기 위한 핵심 요소입니다. 후자는 알고리즘을 매우 빠르게 실행합니다. 각 라운드의 크기가 이전 라운드에 비해 절반으로 줄어들었기 때문에 총 계산 비용이 O(N)가 아닌 O(N*로그(N))가 됩니다.

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

이 작업은 원 둘레를 중심으로 선(예: 선분 또는 호)을 늘려 원을 두 바퀴 회전하는 과정으로 생각할 수 있습니다. 예를 들어 원주에서 x도 위치에 있는 점이 이 작업 후 2배도 위치로 이동합니다. 원주의 0도에서 179도까지의 모든 점에는 180도에서 359도에 해당하는 점이 있으며, 이 두 점은 일치합니다. 즉, 한 점을 x도부터 2배도까지 매핑하면 x+180도의 위치와 일치하게 됩니다. 이 과정은 반복할 수 있습니다. 즉, 이 매핑 작업을 여러 번 적용할 수 있으며 매번 둘레의 점을 새 위치로 이동할 수 있습니다.

매핑 기법이 효과적이려면 원래 곱셈 하위 그룹의 크기에 2의 큰 거듭제곱을 곱해야 합니다. BabyBear는 특정 계수를 가진 시스템으로, 가장 큰 곱셈 하위 그룹이 0이 아닌 값을 모두 포함하는 값이므로 하위 그룹의 크기는 2k -1(여기서 k는 모듈러스의 비트 수)입니다. 이 크기의 하위 그룹은 매핑 연산을 반복적으로 적용하여 다항식의 차수를 효과적으로 줄일 수 있기 때문에 위의 기법에 적합합니다. BabyBear에서는 2^k 크기의 하위 그룹(또는 전체 집합을 사용)을 선택한 다음 FRI 방법을 적용하여 다항식의 차수를 15까지 점진적으로 줄이고 마지막에 다항식의 차수를 확인할 수 있습니다. 이 방법은 계수와 곱셈 부분집합의 크기를 사용하여 계산을 매우 효율적으로 만듭니다. 메르센31은 곱셈 부분집합의 크기가 2^31 - 1이 되도록 어떤 값의 계수를 가진 또 다른 시스템입니다. 이 경우 곱셈 부분집합의 크기는 2의 거듭제곱으로만 인수분해되므로 2로 한 번만 나눌 수 있습니다. 이후 처리에는 더 이상 위의 기법이 적용되지 않으므로 BabyBear처럼 효과적인 다항식 차수 감소를 위해 FFT를 사용할 수 없습니다.

메르센31 영역은 기존 32비트 CPU/GPU 연산에서 산술 연산에 매우 적합합니다. 계수 속성(예: 2^{31} - 1)은 효율적인 비트 단위 연산을 사용하여 많은 연산을 수행할 수 있게 해줍니다. 두 수를 더한 결과가 계수를 초과하는 경우 결과를 계수로 이동시켜 결과를 적절한 범위로 줄일 수 있습니다. 비트 연산은 매우 효율적인 연산입니다. 곱셈 연산에서는 특정 CPU 명령어(흔히 높은 비트 시프트 명령어라고 함)를 사용하여 결과를 처리할 수 있습니다. 이러한 명령어는 곱셈의 높은 비트 부분을 효율적으로 계산하여 연산 효율을 높입니다. 메르센31 영역에서는 위의 기능으로 인해 산술 연산이 베이비베어 영역보다 약 1.3배 빠르며, 메르센31은 계산 효율성이 더 높습니다. Mersenne31 도메인에서 FRI를 구현할 수 있다면 계산 효율성이 크게 향상되어 FRI를 더욱 효율적으로 사용할 수 있습니다.

원 FRI

이것은 소수 p가 주어졌을 때, 비슷한 2대 1의 속성을 갖는 크기 p의 그룹을 찾을 수 있는 비슷한 2대 1 속성을 가진 그룹을 찾을 수 있습니다. 이 모집단은 특정 조건을 만족하는 모든 점으로 구성됩니다(예: 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}

이 매핑은 실제로 위 집합의 크기를 매번 절반으로 줄이며, 여기서 일어나는 일은 각 x가 어떤 의미에서 (x, y) 및 (x, -y)라는 두 점을 나타낸다는 것입니다. 그리고 (x → 2x^2 - 1)은 위의 점 곱셈 법칙입니다. 따라서 원에 있는 두 개의 반대쪽 점의 x 좌표를 곱한 점의 x 좌표로 변환합니다.

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

원 FFT

FRI와 밀접한 관련이 있는 알고리즘 중 하나는 n보다 작은 차수의 다항식의 평가값을 그 값으로 변환하는

FFT