비탈릭 부테린을 통해 비탈릭 부테린 블로그

이것은 다음 게시물의 거울입니다. https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

이것은 zk-SNARK의 기술이 어떻게 작동하는지 설명하는 일련의 기사 중 세 번째 부분입니다. 에 대한 이전 기사 이차 산술 프로그램 과 타원 곡선 짝짓기 읽어야 하며 이 기사에서는 두 개념을 모두 알고 있다고 가정합니다. zk-SNARK가 무엇인지, 무엇을 하는지에 대한 기본 지식도 가정합니다. 또한보십시오 Christian Reitwiessner의 기사는 여기에 있습니다. 또 다른 기술 소개를 위해.

이전 기사에서 우리는 다양한 형태의 수학적 속임수에 훨씬 더 적합한 다항 방정식으로 계산 문제를 표현하는 방법인 이차 산술 프로그램을 소개했습니다. 또한 우리는 동등성 검사를 수행할 수 있는 매우 제한된 형태의 단방향 동형 암호화를 허용하는 타원 곡선 쌍을 도입했습니다. 이제 우리는 중단한 부분부터 시작하여 몇 가지 다른 수학적 트릭과 함께 타원 곡선 쌍을 사용하여 증명자가 특정 QAP에 대해 다른 것을 공개하지 않고도 특정 QAP에 대한 솔루션을 알고 있음을 증명할 수 있도록 할 것입니다. 실제 솔루션.

이 기사는 피노키오 프로토콜 2013년부터 Parno, Gentry, Howell 및 Raykova(종종 PGHR13이라고 함); 기본 메커니즘에는 몇 가지 변형이 있으므로 실제로 구현된 zk-SNARK 체계는 약간 다르게 작동할 수 있지만 기본 원칙은 일반적으로 동일하게 유지됩니다.

시작하려면 우리가 사용할 메커니즘의 보안을 뒷받침하는 주요 암호화 가정을 살펴보겠습니다. *지수에 대한 지식* 추정.

기본적으로, �⋅�=�인 한 쌍의 점 �과 �를 얻고 � 점을 얻으면 �이 어떤 방식으로든 �에서 "파생"되지 않는 한 �⋅�을 생각해 낼 수 없습니다. 당신이 알고 있는 것. 이는 직관적으로 명백해 보일 수 있지만 실제로 이 가정은 타원 곡선 기반 프로토콜의 보안을 증명할 때 일반적으로 사용하는 다른 가정(예: 이산 로그 경도)에서 파생될 수 없으므로 실제로 zk-SNARK는 다소 의존합니다. 일반적으로 타원 곡선 암호화보다 기반이 더 불안정합니다. 하지만 대부분의 암호화 전문가가 괜찮을 만큼 여전히 견고합니다.

이제 이것이 어떻게 사용될 수 있는지 살펴보겠습니다. 한 쌍의 점 (�,�)이 하늘에서 떨어진다고 가정합니다. 여기서 �⋅�=�이지만 �의 값이 무엇인지 아무도 모릅니다. 이제 �⋅�=�인 한 쌍의 점(�,�)을 생각해냈다고 가정해 보겠습니다. 그런 다음 KoE 가정은 내가 그 점 쌍을 만들 수 있는 유일한 방법은 �과 �를 취하고 두 요소에 r을 곱하는 것임을 의미합니다. 내가 개인적으로 아는 것. 타원 곡선 쌍의 마법 덕분에 �=�⋅�을 확인하는 것도 참고하세요. 실제로 알 필요는 없습니다. – 대신 �(�,�)=�(�,�)인지 아닌지 간단히 확인할 수 있습니다.

좀 더 흥미로운 일을 해보자. 하늘에서 1쌍의 점(�1,�2),(�2,�10)…(�10,�XNUMX)이 떨어진다고 가정합니다. 모든 경우에 ��⋅�=��입니다. 그런 다음 �⋅�=�인 한 쌍의 점(�,�)을 제공한다고 가정합니다. 지금 당신은 무엇을 알고 있나요? �은 선형 조합 �1⋅�1+�2⋅�2+…+�10⋅�10이라는 것을 알고 있습니다. 여기서 저는 계수 �1,�2…�10을 알고 있습니다. 즉, 이러한 점 쌍(�,�)에 도달하는 유일한 방법은 �1,�2…�10의 배수를 취하여 함께 더한 다음 �1,�2… �10.

선형 조합을 확인하려는 특정 �1… � 그러면 선형 조합을 생성할 필요 없이 원하는 �에 대해 �⋅�=�인 쌍(�,�)을 생성할 수 있습니다. 따라서 이것이 작동하려면 해당 포인트를 생성한 사람이 신뢰할 수 있고 실제로 10개의 포인트를 생성한 후에 삭제하는 것이 절대적으로 중요합니다. 여기서 "신뢰할 수 있는 설정"이라는 개념이 유래되었습니다..

QAP에 대한 해는 �(�)⋅�(�)−�(�)=�(�)⋅�(�)과 같은 다항식(�,�,�) 집합이라는 점을 기억하세요.

• �는 다항식 세트 {�1…��}의 선형 조합입니다.
• �은 동일한 계수를 갖는 {�1…��}의 선형 조합입니다.
• �은 동일한 계수를 갖는 {�1…��}의 선형 조합입니다.

집합 {�1…��},{�1…��} 및 {�1…��}과 다항식 �은 문제 설명의 일부입니다.

그러나 대부분의 실제 사례에서 �,� 및 �는 매우 큽니다. 해시 함수와 같이 수천 개의 회로 게이트가 있는 경우 다항식(및 선형 조합의 인수)에는 수천 개의 항이 있을 수 있습니다. 따라서 증명자가 선형 조합을 직접 제공하는 대신 위에서 소개한 트릭을 사용하여 증명자가 다른 것을 공개하지 않고 선형 조합인 것을 제공한다는 것을 증명하도록 할 것입니다.

위의 트릭이 다항식이 아닌 타원 곡선 점에서 작동한다는 것을 눈치챘을 것입니다. 따라서 실제로 일어나는 일은 신뢰할 수 있는 설정에 다음 값을 추가하는 것입니다.

• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• ...

t를 다항식이 계산되는 "비밀 지점"으로 생각할 수 있습니다. �은 "생성기"(프로토콜의 일부로 지정된 일부 임의의 타원 곡선 점)이고 �,��,�� 및 ��는 “독성 폐기물”, 즉 어떤 희생을 치르더라도 반드시 삭제해야 하는 숫자입니다. 그것을 가진 사람은 누구나 가짜 증거를 만들 수 있습니다. 이제 누군가가 �⋅��=�과 같은 �, � 점 쌍을 제공한다면(알림: 페어링 확인을 할 수 있으므로 이를 확인하는 데 ��가 필요하지 않습니다), 그러면 여러분은 그들이 무엇을 하는지 알 수 있습니다. 는 �에서 평가된 �� 다항식의 선형 조합을 제공합니다.

따라서 지금까지 증명자는 다음을 제공해야 합니다.

• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��

증명자는 이러한 값을 계산하기 위해 실제로 �,��,�� 또는 ��를 알 필요가 없습니다(알아서는 안 됩니다!). 오히려 증명자는 신뢰할 수 있는 설정에 추가하는 포인트에서만 이러한 값을 계산할 수 있어야 합니다.

다음 단계는 세 가지 선형 조합이 모두 동일한 계수를 갖는지 확인하는 것입니다. 이는 신뢰할 수 있는 설정에 다른 값 세트를 추가하여 수행할 수 있습니다. �⋅(��(�)+��(�)+��(�))⋅�, 여기서 �는 "유해한 것으로 간주되어야 하는 또 다른 숫자입니다." 낭비”이며 신뢰할 수 있는 설정이 완료되는 즉시 폐기됩니다. 그런 다음 증명자가 동일한 계수를 사용하여 이러한 값과 선형 결합을 생성하도록 하고 위와 동일한 페어링 트릭을 사용하여 이 값이 제공된 '+'+'와 일치하는지 확인할 수 있습니다.

마지막으로 �⋅�−�=�⋅�임을 증명해야 합니다. 페어링 확인을 통해 다시 한 번 이 작업을 수행합니다.

�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))

여기서 �ℎ=�⋅�(�)입니다. 이 방정식과 �⋅�−�=�⋅� 사이의 연결이 이해가 되지 않으면 돌아가서 다음을 읽어 보십시오. 페어링에 관한 기사.

위에서 �,� 및 �를 타원 곡선 점으로 변환하는 방법을 살펴보았습니다. �은 단지 생성기입니다(즉, 숫자 1에 해당하는 타원 곡선 점). 신뢰할 수 있는 설정에 �⋅�(�)를 추가할 수 있습니다. � 더 어렵습니다. �은 다항식일 뿐이며 각 개별 QAP 솔루션에 대한 계수가 어떻게 될지 미리 예측하는 것은 거의 없습니다. 따라서 신뢰할 수 있는 설정에 더 많은 데이터를 추가해야 합니다. 구체적으로 순서는 다음과 같습니다.

�,�⋅�,�⋅�2,�⋅�3,�⋅�4…

Zcash의 신뢰할 수 있는 설정에서 여기의 시퀀스는 약 2만개까지 올라갑니다. 이것은 적어도 관심 있는 특정 QAP 인스턴스에 대해 항상 �(�)를 계산할 수 있는지 확인하는 데 필요한 �의 거듭제곱 수입니다. 그리고 이를 통해 증명자는 검증자가 최종 확인을 할 수 있도록 모든 정보를 제공할 수 있습니다.

우리가 논의해야 할 세부 사항이 하나 더 있습니다. 대부분의 경우 우리는 특정 문제에 대한 해결책이 존재한다는 것을 추상적으로 증명하고 싶지 않습니다. 오히려 우리는 특정 솔루션의 정확성(예: "cow"라는 단어를 취하고 SHA3가 이를 백만 번 해시하면 최종 결과가 0x73064fe5로 시작한다는 것을 증명)의 정확성을 증명하거나 제한하는 경우 솔루션이 존재한다는 것을 증명하고 싶습니다. 일부 매개변수. 예를 들어, 거래 금액과 계정 잔액이 암호화된 암호화폐 인스턴스화에서 다음과 같은 일부 암호 해독 키 k를 알고 있음을 증명하려고 합니다.

1. decrypt(old_balance, k) >= decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)

암호화된 old_balance, tx_value 과 new_balance 공개적으로 지정해야 합니다. 왜냐하면 이는 우리가 특정 시점에 확인하려는 특정 값이기 때문입니다. 암호 해독 키만 숨겨야 합니다. 입력에 대한 특정 제한 사항에 해당하는 "사용자 정의 확인 키"를 생성하려면 프로토콜을 약간 수정해야 합니다.

이제 조금 뒤로 물러나 보겠습니다. 우선, ben이 제공한 전체 검증 알고리즘은 다음과 같습니다. 사손, 트로머, 비르자, 키에사:

첫 번째 줄은 매개변수화를 다루고 있습니다. 본질적으로 그 기능은 "맞춤 확인 키"를 생성하는 것이라고 생각할 수 있습니다. 문제의 특정 인스턴스에 대해 여기서 일부 인수가 지정됩니다. 두 번째 줄은 �,� 및 �에 대한 선형 조합 검사입니다. 세 번째 줄은 선형 조합의 계수가 동일한지 확인하는 것이고, 네 번째 줄은 곱 확인 �⋅�−�=�⋅�입니다.

전체적으로 확인 프로세스는 몇 가지 타원 곡선 곱셈(각 "공개" 입력 ​​변수에 대해 하나씩)과 32개의 페어링 확인으로 이루어지며, 그 중 하나에는 추가 페어링 곱셈이 포함됩니다. 증명에는 2개의 타원 곡선 점이 포함되어 있습니다. �(�),�(�) 및 �(�)에 대해 각각 한 쌍의 점, �⋅(�(�)+�(�)+�(�에 대한 점 �� )), �(�)에는 �ℎ 지점이 있습니다. 이 점 중 64개는 �� 곡선(� 좌표를 단일 비트로 압축할 수 있으므로 각각 288바이트)에 있고 Zcash 구현에서는 한 점(��)이 ��XNUMX(XNUMX 바이트)이므로 전체 증명 크기는 ~XNUMX바이트입니다.

증명을 만드는 데 있어 계산적으로 가장 어려운 두 가지 부분은 다음과 같습니다.

• (�⋅�−�)/�를 나누어 �를 얻습니다(알고리즘은 다음을 기반으로 함). 고속 푸리에 변환 이차 시간 미만으로 이 작업을 수행할 수 있지만 여전히 계산 집약적입니다.)
• �(�),�(�),�(�) 및 �(�) 값과 해당 쌍을 생성하기 위해 타원 곡선 곱셈 및 덧셈 수행

증명을 만드는 것이 어려운 기본적인 이유는 원래 계산에서 단일 이진 논리 게이트였던 것이 영지식 증명을 만들려면 타원 곡선 연산을 통해 암호화 처리되어야 하는 연산으로 바뀌기 때문입니다. . 이 사실은 빠른 푸리에 변환의 초선형성과 함께 Zcash 거래에 대해 증명 생성에 ~20-40초가 소요된다는 것을 의미합니다.

또 다른 매우 중요한 질문은 다음과 같습니다. 신뢰할 수 있는 설정을 좀 더… 신뢰를 덜 요구하도록 만들 수 있습니까? 불행하게도 완전히 신뢰할 수 없게 만들 수는 없습니다. KoE 가정 자체는 �이 무엇인지 알지 못한 채 독립적인 쌍(��,��⋅�)을 만드는 것을 불가능하게 합니다. 그러나 우리는 �다자간 계산을 사용하여 보안을 크게 강화할 수 있습니다. 즉, 참가자 중 적어도 한 명이 독성 폐기물을 삭제했다면 괜찮을 수 있는 방식으로 � 당사자 간에 신뢰할 수 있는 설정을 구성합니다. .

이를 수행하는 방법에 대한 약간의 느낌을 얻기 위해 기존 세트(�,�⋅�,�⋅�2,�⋅�3…)를 사용하고 자신의 비밀을 "추가"하는 간단한 알고리즘이 있습니다. 따라서 속임수를 쓰려면 비밀과 이전 비밀(또는 이전 비밀 세트)이 모두 필요합니다.

출력 세트는 간단합니다.

�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3…

원래 세트와 s만 알고 이 세트를 생산할 수 있으며, 새 세트는 이제 � 대신 "독성 폐기물"로 �⋅�를 사용하는 것을 제외하고는 이전 세트와 동일한 방식으로 기능합니다. 귀하와 이전 세트를 만든 사람(또는 사람들)이 모두 유독성 폐기물을 삭제하지 않고 나중에 공모하지 않는 한 세트는 "안전"합니다.

완전한 신뢰할 수 있는 설정을 위해 이 작업을 수행하는 것은 여러 값이 관련되어 있고 알고리즘이 여러 라운드에 걸쳐 당사자 간에 수행되어야 하기 때문에 상당히 어렵습니다. 다자간 계산 알고리즘을 더욱 단순화하여 더 적은 라운드를 요구하도록 만들거나 더 많은 병렬화를 가능하게 만들 수 있는지 확인하기 위한 활발한 연구 영역입니다. 더 많은 작업을 수행할수록 더 많은 당사자를 신뢰할 수 있는 설정 절차에 포함시킬 수 있게 됩니다. . 서로 알고 협력하는 6명의 참가자 사이의 신뢰할 수 있는 설정이 일부 사람들을 불편하게 만들 수 있는 이유를 이해하는 것은 합리적입니다. 그러나 수천 명의 참가자로 구성된 신뢰할 수 있는 설정은 전혀 신뢰하지 않는 것과 거의 구별할 수 없습니다. 그리고 정말로 편집증적인 경우 , 귀하는 직접 설정 절차에 들어가서 참여할 수 있으며 귀하의 값을 개인적으로 삭제했는지 확인하십시오.

활발한 연구의 또 다른 영역은 동일한 목표를 달성하기 위해 페어링 및 동일한 신뢰할 수 있는 설정 패러다임을 사용하지 않는 다른 접근 방식을 사용하는 것입니다. 보다 Eli ben Sasson의 최근 프레젠테이션 한 가지 대안에 대해 (경고하지만 적어도 SNARK만큼 수학적으로 복잡합니다!)

검토해 주신 Ariel Gabizon과 Christian Reitwiessner에게 특별히 감사드립니다.

• SEO 기반 콘텐츠 및 PR 배포. 오늘 증폭하십시오.
• PlatoData.Network 수직 생성 Ai. 자신에게 권한을 부여하십시오. 여기에서 액세스하십시오.
• PlatoAiStream. 웹3 인텔리전스. 지식 증폭. 여기에서 액세스하십시오.
• 플라톤ESG. 탄소, 클린테크, 에너지, 환경, 태양광, 폐기물 관리. 여기에서 액세스하십시오.
• PlatoHealth. 생명 공학 및 임상 시험 인텔리전스. 여기에서 액세스하십시오.
• BlockOffsets. 환경 오프셋 소유권 현대화. 여기에서 액세스하십시오.
• 출처: 플라톤 데이터 인텔리전스.