비탈릭 부테린을 통해 비탈릭 부테린 블로그
이것은 다음 게시물의 거울입니다. https://medium.com/@VitalikButerin/이차-산술-프로그램-6에서 영웅으로-f558d649ceaXNUMX
최근 zk-SNARK의 기술에 많은 관심이 있었고 사람들은 점점 더 신비화하려고 노력 중 이는 해독할 수 없는 복잡성으로 인해 많은 사람들이 "달 수학"이라고 부르게 된 것입니다. zk-SNARK는 특히 전체 작업을 위해 함께 모여야 하는 움직이는 부품의 수가 엄청나게 많기 때문에 실제로 파악하기가 매우 어렵습니다. 그러나 기술을 하나씩 분해하면 이해가 더 간단해집니다.
이 게시물의 목적은 zk-SNARK에 대한 전체 소개를 제공하는 것이 아닙니다. (i) zk-SNARK가 무엇인지, 무엇을 하는지 알고 있고, (ii) 다항식과 같은 것에 대해 추론할 수 있을 만큼 충분한 수학을 알고 있다고 가정합니다(문이 �(�)+�(�) =(�+�)(�) , 여기서 � 및 �는 다항식이며 자연스럽고 분명해 보입니다. 그렇다면 올바른 수준에 있는 것입니다. 오히려 이 게시물은 기술 뒤에 있는 기계를 더 깊이 파고들어 zk-SNARK 연구원 Eran Tromer가 여기에 그린 것처럼 파이프라인의 전반부를 최대한 설명하려고 합니다.
여기의 단계는 두 부분으로 나눌 수 있습니다. 첫째, zk-SNARK는 계산 문제에 직접 적용될 수 없습니다. 오히려 문제를 작동할 수 있는 올바른 "형식"으로 문제를 변환해야 합니다. 이 형식을 "QAP(이차 산술 프로그램)"이라고 하며 함수 코드를 이들 중 하나로 변환하는 것 자체가 매우 중요합니다. 함수의 코드를 QAP로 변환하는 프로세스와 함께 실행할 수 있는 또 다른 프로세스가 있으므로 코드에 대한 입력이 있는 경우 해당 솔루션(QAP에 대한 "증인"이라고도 함)을 만들 수 있습니다. 그 후, 이 증인에 대한 실제 "영지식 증명"을 생성하기 위한 상당히 복잡한 또 다른 프로세스와 다른 사람이 귀하에게 전달한 증거를 확인하기 위한 별도의 프로세스가 있지만 이러한 세부 사항은 이 게시물의 범위를 벗어납니다. .
우리가 선택할 예는 간단한 것입니다. 삼차 방정식: �3+�+5=35(힌트: 답은 3)에 대한 해를 알고 있음을 입증하는 것입니다. 이 문제는 결과적인 QAP가 위협적일 만큼 크지 않을 정도로 간단하지만 모든 기계가 작동하는 것을 볼 수 있을 만큼 사소하지 않습니다.
다음과 같이 함수를 작성해 보겠습니다.
def qeval(x):
y = x**3
return x + y + 5여기서 사용하고 있는 간단한 특수 목적 프로그래밍 언어는 기본 산술(+, −, ⋅, /), 상수 지수 지수(�7, ��는 아님) 및 변수 할당을 지원합니다. 이는 이론적으로 수행할 수 있을 만큼 강력합니다. 그 내부의 모든 계산(계산 단계 수가 제한되어 있는 한, 루프는 허용되지 않음) 모듈로(%) 및 비교 연산자(<, >, ≤, ≥)는 지원되지 않습니다. 유한 순환 그룹 산술에서 직접 모듈로 또는 비교를 수행하는 효율적인 방법이 없기 때문입니다(이 점에 대해 감사드립니다. 방법이 있었다면) 둘 중 하나를 수행하면 "이진 검색" 및 "중국 나머지 정리"라고 말할 수 있는 것보다 타원 곡선 암호화가 더 빨리 손상됩니다.
비트 분해(예: 13=23+22+1)를 보조 입력으로 제공하고 해당 분해의 정확성을 입증하고 이진 회로에서 수학을 수행하여 언어를 모듈로 및 비교로 확장할 수 있습니다. 유한 필드 산술에서는 상등(==) 검사를 수행하는 것도 가능하고 실제로는 조금 더 쉽습니다. 그러나 이 두 가지 세부 사항은 지금 당장 다루지 않겠습니다. 조건문(예: if �<5:�=7; else: �=9)을 산술 형식으로 변환하여 지원하도록 언어를 확장할 수 있습니다: �=7⋅(�<5)+9⋅(�≥5 ) 그러나 조건문의 두 "경로"를 모두 실행해야 하며, 중첩된 조건문이 많으면 이로 인해 상당한 양의 오버헤드가 발생할 수 있습니다.
이제 이 과정을 단계별로 살펴보겠습니다. 어떤 코드에든 이 작업을 직접 수행하려면 여기에 컴파일러를 구현했습니다. (교육 목적으로만 사용되며 아직 실제 zk-SNARK에 대한 QAP를 만들 준비가 되지 않았습니다!)
평탄화
첫 번째 단계는 임의로 복잡한 명령문과 표현식을 포함할 수 있는 원본 코드를 다음 두 가지 형식의 명령문 시퀀스로 변환하는 "평탄화" 절차입니다. ) 및 �=� (��) � (여기서 ��는 +, −, ⋅, /일 수 있으며 � 및 �는 변수, 숫자 또는 하위 표현식일 수 있습니다). 이러한 각 명령문은 회로의 논리 게이트와 비슷하다고 생각할 수 있습니다. 위 코드의 평면화 프로세스 결과는 다음과 같습니다.
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5원본 코드와 여기에 있는 코드를 읽어보면 두 코드가 동일하다는 것을 쉽게 알 수 있습니다.
R1CS로 가는 문
이제 이것을 순위 1 제약 시스템(R1CS)이라는 것으로 변환합니다. R1CS는 세 개의 벡터(�, �, �) 그룹의 시퀀스이고 R1CS에 대한 해는 벡터 �입니다. 여기서 �는 방정식 �.�⋅�.�−�.�=0을 충족해야 합니다. 여기서 . 내적을 나타냅니다. 더 간단한 용어로 � 및 �를 "함께 압축"하고 동일한 위치의 두 값을 곱한 다음 이 곱의 합을 취하면 � 및 �, � 및 �에도 동일한 작업을 수행합니다. 이면 세 번째 결과는 처음 두 결과의 곱과 같습니다. 예를 들어, 다음은 만족스러운 R1CS입니다.
먼저 사용할 변수 매핑을 제공합니다.
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'솔루션 벡터는 이러한 모든 변수에 대한 할당을 순서대로 구성합니다.
이제 첫 번째 게이트에 (�,�,�) 트리플을 제공하겠습니다.
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]솔루션 벡터의 두 번째 위치에 3이 포함되고 네 번째 위치에 9가 포함되어 있으면 솔루션 벡터의 나머지 내용에 관계없이 내적 검사가 3⋅3=9로 요약된다는 것을 알 수 있습니다. 그래서 통과할 것이다. 솔루션 벡터의 두 번째 위치에 -3이 있고 네 번째 위치에 9가 있으면 검사도 통과됩니다. 실제로 솔루션 벡터의 두 번째 위치에 7이 있고 네 번째 위치에 49가 있으면 해당 검사는 여전히 통과됩니다. 이 첫 번째 검사의 목적은 첫 번째 게이트의 입력과 출력의 일관성만 확인하는 것입니다.
이제 두 번째 게이트로 가보겠습니다.
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]첫 번째 내적 확인과 비슷한 스타일로 여기서는 ���1⋅�=�을 확인합니다.
이제 세 번째 게이트는 다음과 같습니다.
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]여기서는 패턴이 다소 다릅니다. 즉, 솔루션 벡터의 첫 번째 요소에 두 번째 요소를 곱한 다음 다섯 번째 요소를 곱하고 두 결과를 더한 다음 합이 여섯 번째 요소와 같은지 확인합니다. 솔루션 벡터의 첫 번째 요소는 항상 1이기 때문에 이는 출력이 두 입력의 합과 같은지 확인하는 덧셈 검사일 뿐입니다.
마지막으로 네 번째 문은 다음과 같습니다.
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]여기서는 마지막 검사인 ~out =����2+5를 평가하고 있습니다. 내적 검사는 해 벡터의 여섯 번째 요소를 가져와서 첫 번째 요소에 1배를 더한 다음(주의: 첫 번째 요소는 5이므로 사실상 XNUMX를 더하는 것을 의미함) 이를 세 번째 요소와 비교하여 확인하는 방식으로 작동합니다. 출력 변수를 저장합니다.
그리고 거기에는 네 가지 제약 조건이 있는 R1CS가 있습니다. Witness는 단순히 입력, 출력 및 내부 변수를 포함한 모든 변수에 대한 할당입니다.
[1, 3, 35, 9, 27, 30]위의 평면화된 코드를 간단히 "실행"하고 입력 변수 할당 �=3으로 시작하여 모든 중간 변수의 값과 계산할 때 출력을 입력하면 이를 직접 계산할 수 있습니다.
전체 R1CS를 합하면 다음과 같습니다.
A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]R1CS에서 QAP로
다음 단계는 이 R1CS를 QAP 형식으로 변환하는 것입니다. 이는 내적 대신 다항식을 사용하는 것을 제외하고는 완전히 동일한 논리를 구현합니다. 우리는 다음과 같이 이를 수행합니다. 우리는 길이가 3인 3개 벡터로 구성된 XNUMX개 그룹에서 XNUMX차 XNUMX 다항식으로 구성된 XNUMX개 그룹으로 이동합니다. 여기서 각각의 다항식을 평가합니다. x 좌표 제약 조건 중 하나를 나타냅니다. 즉, �=1에서 다항식을 평가하면 첫 번째 벡터 세트를 얻고, �=2에서 다항식을 평가하면 두 번째 벡터 세트를 얻는 식입니다.
우리는 라그랑주 보간. 라그랑주 보간이 해결하는 문제는 다음과 같습니다. 점 세트(예: (�,�) 좌표 쌍)가 있는 경우 해당 점에 대해 라그랑주 보간을 수행하면 모든 점을 통과하는 다항식을 얻을 수 있습니다. 우리는 문제를 분해하여 이를 수행합니다: 각 � 좌표에 대해 해당 � 좌표에서 원하는 � 좌표를 갖고 관심 있는 다른 � 좌표에서 � 좌표가 0인 다항식을 만든 다음 최종 결과를 얻습니다. 결과적으로 모든 다항식을 더합니다.
예를 들어 보겠습니다. (1,3),(2,2) 및 (3,4)를 통과하는 다항식을 원한다고 가정합니다. (1,3),(2,0), (3,0)을 통과하는 다항식을 만드는 것부터 시작합니다. 결과적으로 �=1에서 "돌출"하고 다른 관심 지점에서는 XNUMX인 다항식을 만드는 것은 쉽습니다. 우리는 단순히 다음을 수행합니다.
(x - 2) * (x - 3)다음과 같이 보입니다.
(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))이것은 우리에게 :
1.5 * x**2 - 7.5 * x + 9
1.5 * x**2 - 5.5 * x + 7
이제 라그랑주 보간법을 사용하여 R1CS를 변환해 보겠습니다. 우리가 할 일은 모든 � 벡터에서 첫 번째 값을 가져오고, 라그랑주 보간을 사용하여 그것에서 다항식을 만드는 것입니다(여기서 �에서 다항식을 평가하면 �번째 � 벡터의 첫 번째 값을 얻습니다). 프로세스를 반복합니다. 모든 � 및 � 벡터의 첫 번째 값에 대해 그런 다음 두 번째 값, 세 번째 값 등에 대해 해당 프로세스를 반복합니다. 편의를 위해 지금 답변을 제공하겠습니다.
A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]
B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]계수는 오름차순이므로 위의 첫 번째 다항식은 실제로 0.833⋅�3—5⋅�2+9.166⋅�−5입니다. 이 다항식 세트(나중에 설명할 Z 다항식 포함)는 이 특정 QAP 인스턴스에 대한 매개변수를 구성합니다. 이 시점까지의 모든 작업은 zk-SNARK를 사용하여 확인하려는 모든 기능에 대해 한 번만 수행하면 됩니다. QAP 매개변수가 생성되면 재사용할 수 있습니다.
�=1에서 이러한 다항식을 모두 평가해 보겠습니다. �=1에서 다항식을 평가한다는 것은 단순히 모든 계수를 더하는 것을 의미하므로(모든 �에 대해 1�=1이므로) 어렵지 않습니다. 우리는 다음을 얻습니다:
A results at x=1
0
1
0
0
0
0
B results at x=1
0
1
0
0
0
0
C results at x=1
0
0
0
1
0
0그리고 보라, 여기에 있는 것은 위에서 만든 첫 번째 논리 게이트에 대한 세 개의 벡터 세트와 정확히 동일합니다.
QAP 확인 중
이제 이 미친 변화의 요점은 무엇입니까? 대답은 R1CS의 제약 조건을 개별적으로 확인하는 대신 이제 확인할 수 있다는 것입니다. 모든 제약을 동시에 내적 확인을 통해 다항식에.
결과 다항식은 그 자체로 0일 필요는 없으며 실제로 대부분의 경우에는 그렇지 않습니다. 논리 게이트에 해당하지 않는 모든 지점에서 결과가 0인 한 어떤 동작도 가질 수 있습니다. do 어떤 게이트에 해당합니다. 정확성을 확인하기 위해 실제로 게이트에 해당하는 모든 지점에서 다항식 �=�.�⋅�.�−�.�을 평가하지 않습니다. 대신에 �를 다른 다항식 �으로 나누고 �가 균등하게 나누어지는지 확인합니다. 즉, �/� 나누기는 나머지가 남지 않습니다.
�는 (�−1)⋅(�−2)⋅(�−3)…으로 정의됩니다. – 논리 게이트에 해당하는 모든 지점에서 XNUMX과 같은 가장 간단한 다항식입니다. 대수학의 기본 사실은 다음과 같습니다. 어떤 이 모든 점에서 0과 같은 다항식은 이 최소 다항식의 배수여야 하며, 다항식이 �의 배수인 경우 해당 점 중 하나에서의 평가는 0이 됩니다. 이러한 동등성은 우리 작업을 훨씬 쉽게 만듭니다.
이제 실제로 위의 다항식을 사용하여 내적 검사를 수행해 보겠습니다. 첫째, 중간 다항식은 다음과 같습니다.
A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]이제 �.�⋅�.�—�.�:
t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]이제 최소 다항식 �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):
Z = [24, -50, 35, -10, 1]그리고 위의 결과를 �로 나누면 다음과 같은 결과를 얻습니다.
h = t / Z = [-3.666, 17.055, -3.444]남은 것이 없습니다.
그래서 우리는 QAP에 대한 솔루션을 갖게 되었습니다. 이 QAP 솔루션에서 파생되는 R1CS 솔루션의 변수 중 하나를 위조하려고 시도하는 경우(예: 마지막 변수를 31 대신 30로 설정하면 검사 중 하나에 실패하는 � 다항식을 얻습니다. 이 경우, �=3의 결과는 1이 아닌 -0이 되며, 더욱이 �은 �의 배수가 되지 않습니다. 오히려 �/�를 나누면 나머지는 [−5.0,8.833,−4.5,0.666]이 됩니다.
위의 내용은 단순화된 것입니다. "실제 세계에서" 덧셈, 곱셈, 뺄셈 및 나눗셈은 정규 숫자가 아닌 유한 필드 요소(자기 일관성이 있는 으스스한 종류의 산술)를 사용하여 발생하므로 우리가 알고 사랑하는 모든 대수 법칙은 여전히 사실이지만 모든 대답은 유한 크기 집합의 요소이며 일반적으로 일부 의 경우 0에서 �−1 범위 내의 정수입니다. 예를 들어 �=13이면 1/2=7(및 7⋅2=1), 3⋅5=2 등입니다. 유한 필드 산술을 사용하면 반올림 오류에 대해 걱정할 필요가 없으며 시스템이 타원 곡선과 잘 작동할 수 있으며, 이는 결국 zk-SNARK 프로토콜을 실제로 안전하게 만드는 나머지 zk-SNARK 기계에 필요하게 됩니다.
zk-SNARK의 내부 작동에 대해 많은 세부 사항을 설명하는 데 도움을 준 Eran Tromer에게 특별히 감사드립니다.
- SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
- PlatoData.Network 수직 생성 Ai. 자신에게 권한을 부여하십시오. 여기에서 액세스하십시오.
- PlatoAiStream. 웹3 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
- 플라톤ESG. 탄소, 클린테크, 에너지, 환경, 태양광, 폐기물 관리. 여기에서 액세스하십시오.
- PlatoHealth. 생명 공학 및 임상 시험 인텔리전스. 여기에서 액세스하십시오.
- BlockOffsets. 환경 오프셋 소유권 현대화. 여기에서 액세스하십시오.
- 출처: 플라톤 데이터 인텔리전스.
