전문
zk-SNARK 의 더 복잡한 측면을 탐색할 준비가 되셨습니까? 이전 섹션 에서는 산술 회로 및 이차 산술 프로그램 과 같은 몇 가지 고급 개념에 대해 배웠습니다. 이 섹션에서는 타원 곡선 쌍 (Elliptic Curve pairings) 이라는 또 다른 강력한 개념을 탐구하여 지식을 확장하겠습니다.
참고 : 타원 곡선 쌍 과 같은 주제를 깊이 있게 이해하는 것은 때때로 많은 사람들에게 어려울 수 있습니다. 그러나 이것이 바로 여러분이 이에 대한 최소한의 기본적인 관점을 얻는 데 도움이 되도록 이 기사를 쓴 이유입니다.
내 목표는 타원 곡선 쌍을 철저하게 설명하는 것뿐만 아니라 주제를 더 흥미롭고 이해하기 쉽게 만드는 것입니다. 이 기사를 통해 일반적으로 수학과 암호화뿐만 아니라 특히 zk-SNARK 의 특정 응용 분야에서 타원 곡선 쌍의 힘을 볼 수 있기를 바랍니다.
타원 곡선
타원 곡선은 타원 곡선 암호화 분야의 일부입니다. 이것은 모든 사람이 이해하기 쉽지 않은 복잡한 주제입니다. 이를 더 잘 이해하려면 이전 섹션의 ECC에 대한 내 기사를 살펴보십시오.
타원 곡선 암호화에는 2차원 공간의 "점"이 포함되며, 각 "점"은 (x, y) 좌표 쌍을 특징으로 합니다.
점 사이의 덧셈과 뺄셈과 같은 수학적 연산을 수행하기 위한 특정 규칙이 있어 다른 점을 알고 있을 때 새 점의 좌표를 계산할 수 있습니다.
예 : 좌표 계산 R = P + Q
또한 해당 정수만큼 점 자체에 점을 반복적으로 추가하여 점에 정수를 곱할 수도 있습니다.
예 : P * n = P + P + … + P
이는 타원 곡선 암호화 에서 수학적 연산을 수행하는 효율적인 방법을 제공합니다.
타원 곡선에는 "무한대 점" ( O )이라는 특별한 점이 있는데, 이는 점 계산에서 숫자 0에 해당하며 P + O = P 가 항상 참입니다.
곡선에도 "순서" 가 있습니다. 모든 P 에 대해 P * n = O 인 숫자 n이 존재합니다( P * (n+1) = P, P * (7*n + 5) = P * 5 등).
또한 어떤 방식으로든 숫자 1을 나타내는 것으로 이해되는 "생성기 지점"(G )도 있습니다. 이론적으로 곡선의 모든 점( O 제외)은 G 가 될 수 있습니다.
페어링
페어링을 사용하면 타원 곡선의 점에서 더 복잡한 방정식을 테스트할 수 있습니다.
예를 들어:
P, Q 및 R 에서 p * q 가 r 과 같은지 확인할 수 있습니다.
p 에 대한 정보가 P 에서 누출될 수 있지만 이러한 누출은 신중하게 제어됩니다.
페어링을 통해 2차 제약 조건을 확인할 수 있습니다.
예를 들어 e(P, Q) * e(G, G * 5) = 1 테스트는 실제로 p * q + 5 = 0 테스트입니다.
페어링 이라는 작업입니다. 수학자들은 이를 이중선형 매핑(bilinear mapping) 이라고 부르기도 합니다. 여기서 "Bilinear"는 다음 규칙을 준수합니다.
다음 규칙을 준수하는 한 + 및 * 연산자를 어떤 방식으로든 사용할 수 있습니다.
그리고
P, Q, R 및 S 가 간단한 숫자인 경우 다음 표현식을 사용하면 간단한 페어링 작업을 쉽게 만들 수 있습니다.
다음 결과:
그것은 평행선 입니다!
그러나 이러한 단순 페어링 작업은 단순 정수에 대해 작동하고 분석하기가 너무 쉽기 때문에 암호화에 적합하지 않습니다.
페어링 작업을 수행할 때 숫자와 그 결과를 알면 남은 숫자를 쉽게 계산하고 찾을 수 있습니다.
우리는 추가 분석이나 이해 없이 기본적인 수학 연산만 수행할 수 있는 "블랙 박스" 와 같은 수학 연산을 사용합니다. 이것이 타원 곡선과 타원 곡선에 대한 페어링 작업이 암호화에서 중요해지는 이유입니다.
프라임 필드 및 확장 필드
타원 곡선 점에 이중선형 지도를 만드는 것이 가능합니다. 즉, 함수를 만드는 것이 가능합니다.
여기서 P 와 Q는 타원 곡선 점이고 결과는 F_p1² 라는 요소 유형입니다.
먼저 프라임 필드(Prime Field) 와 확장 필드(Extension Field)에 대해 알아보겠습니다.
위 이미지의 타원 곡선은 곡선의 방정식이 일반적인 실수를 사용하여 정의되기 때문에 매우 아름답습니다.
그러나 암호화에서 기존 실수를 사용하면 "뒤로 돌아가기" 위해 로그를 사용하게 될 수 있으며, 숫자를 저장하고 표현하는 데 필요한 공간이 임의로 증가할 수 있으므로 문제가 발생할 수 있습니다. 따라서 우리는 소수 필드 에 숫자를 사용합니다.
소수 필드 에는 숫자 0, 1, 2… p-1 세트가 포함됩니다. 여기서 p는 소수이고 다양한 연산은 다음과 같이 정의됩니다.
모든 작업은 모듈로 p로 수행됩니다.
나눗셈은 특별한 경우입니다. 일반적으로 3/2는 정수가 아니며 이제는 정수만 다루고 싶기 때문에 대신 다음과 같은 숫자 x를 찾으려고 합니다.
x * 2 = 3 .
이는 확장 유클리드 알고리즘을 사용하여 수행할 수 있습니다. 예를 들어 p = 7 이면 다음과 같습니다.
다음으로 확장 필드 에 대해 설명하겠습니다.
수학 책에서 자주 볼 수 있는 일반적인 예는 복소수 필드 입니다. 여기서 실수 필드는 추가 요소 sqrt(-1) = i를 사용하여 " 확장 "됩니다.
확장 필드는 기존 필드를 가져온 다음 새 요소를 " 추가 "하고 새 요소와 원래 필드에 이미 있는 요소 사이의 관계를 정의하는 방식으로 작동합니다(예: i² + 1 = 0 ).
중요한 것은 이 방정식이 원래 필드의 모든 숫자에 대해 참이 아니라는 점입니다. 그런 다음 원래 필드에 있는 요소와 방금 생성된 새 요소의 모든 선형 조합을 고려하십시오.
주요 필드를 확장할 수도 있습니다.
예를 들어 위에서 설명한 프라임 필드 mod 7을 i로 확장하면 다음을 수행할 수 있습니다.
코드에서 수행된 모든 수학을 보려면 여기에서 프라임 필드 및 필드 확장이 수행됩니다.
타원 곡선 쌍
타원 곡선 쌍은 두 개의 타원 곡선에서 두 개의 점을 가져와 해당 점을 단일 숫자로 매핑하는 메커니즘입니다.
이 매핑은 타원 곡선의 점을 곱하는 것과 동일하다고 생각할 수 있습니다.
수학적으로 타원 곡선 쌍은 타원 곡선의 두 점을 유한 필드 와 같은 다른 그룹의 요소에 매핑하는 것으로 정의됩니다 .
여기서 e 는 쌍을 이루고 있으며 E 1과 E 2는 타원 곡선 이고 𝐹는 유한 필드 입니다.
타원 곡선 E 1과 E 2는 다를 필요가 없습니다.
연결이 발생하면 결과적으로 다른 그룹의 요소를 다음 연결에 재사용할 수 없습니다.
타원 곡선 쌍에는 쌍선형 매핑 이라는 특정 속성이 있습니다.
여기서 P , Q , R은 타원 곡선 의 점이고 𝑎∈𝑍, 𝑏∈𝑍
이러한 "쌍선형 매핑"을 사용하면 매핑을 그대로 유지하면서 두 곡선의 계수 𝑎 및 𝑏을 "이동 "할 수 있습니다.
우리는 타원 곡선 쌍을 G2 x G1 -> Gt 의 매핑으로 상상할 수 있습니다.
G1은 점들이 형태 방정식을 만족하는 타원 곡선입니다.
두 좌표 모두 F_p 의 요소입니다(단순 숫자이지만 연산은 특정 소수에 대해 모듈로 수행됩니다).
G2 도 타원 곡선입니다. 여기서 점은 G1 과 동일한 방정식을 만족하지만 해당 좌표는 F_p1² 필드에 속합니다(우리는 다음과 같이 12차 다항식으로 정의되는 새로운 " 매직 넘버 " w를 정의합니다.
Gt는 타원 곡선의 결과가 들어가는 객체 유형입니다. 우리가 고려한 곡선에서 Gt 는 F_p1² ( G2 에서 사용된 것과 동일한 강력한 복소수)입니다.
여기서는 이중선형성을 충족해야 합니다.
다른 두 가지 중요한 기준과 함께:
- 효율적인 계산 가능성: 효율적인 계산 능력이란 너무 복잡하지 않고 신속하게 복합 연산을 계산할 수 있다는 것을 의미합니다. 예를 들면 다음과 같습니다. 점의 이산 로그를 취하여 이를 곱하여 화합물을 생성하면 원래 타원 곡선 코드가 깨지는 것처럼 계산이 너무 어려워집니다. 따라서 복합 연산은 너무 많은 계산 부담을 주지 않고 효율적으로 계산할 수 있는 경우 계산적으로 효율적인 것으로 간주됩니다.
- 비퇴화(Non-degeneracy): 비퇴화는 연결이 쓸모없는 연결이 아니라는 것을 보장합니다. 즉, 입력 포인트와 독립적인 고정 값을 반환하지 않습니다. 예 : 모든 P 및 Q 에 대해 결합을 e(P, Q) = 1 로 정의하면 타원 곡선의 점 간의 관계에 대한 유용한 정보를 제공하지 않습니다. 따라서 연결은 입력 지점 간의 관계에 대한 유용한 정보를 제공하는 경우 비퇴행성으로 간주됩니다.
그럼 어떻게 해야 할까요?
먼저, 타원 곡선의 점에 대한 함수를 표현하는 또 다른 방법 인 제수(divisor)의 개념을 이해해야 합니다.
함수의 제수는 본질적으로 함수의 0과 무한대 수를 계산합니다. 이것이 무엇을 의미하는지 이해하기 위해 몇 가지 예를 살펴보겠습니다. 일부 점 P = (P_x, P_y) 를 수정하고 다음 함수를 고려해 보겠습니다.
제수 는 [P] + [-P] – 2 * [O] 입니다.
[P] + [Q] 는 [P + Q]와 다릅니다. 이유는 다음과 같습니다.
- x 가 P_x 일 때 x – P_x = 0 이기 때문에 P 에서 함수는 0 입니다.
- -P 와 P가 동일한 x 좌표를 가지므로 -P 에서는 함수가 0 입니다.
- x가 무한대로 가면서 함수는 무한대로 가므로 우리는 함수가 O 에서 무한하다고 말합니다.
그 이유는 타원 곡선의 방정식에 있습니다.
y는 x^3을 따라잡기 위해 x 보다 약 "1.5배" 빠르게 무한대로 증가합니다. 따라서 선형함수에 x 만 있으면 다중도가 2인 무한대로 표현되고, y 가 있으면 3의 배수로 무한대로 표현됩니다.
이제 "라인 함수"를 고려해보세요.
여기서 직선이 타원 곡선의 점 P 와 Q를 통과하도록 a, b 및 c를 신중하게 선택했습니다.
타원 곡선의 덧셈이 작동하는 방식 때문에 이는 점 -PQ 를 통과한다는 의미이기도 합니다. 이 함수는 또한 x 와 y 에 따라 무한대로 이동하여 다음이 될 가능성을 나눕니다.
각 "유리 함수" (점 좌표에서 유한한 수의 연산 +, -, *, / 만 사용하여 정의된 함수)는 상수를 곱하는 조건으로 divsor 에 고유하게 해당합니다(즉, 두 함수 F 와 G 가 동일한 제수 , F = G * k, 여기서 k 는 상수임).
두 함수의 곱의 나눗셈은 각 함수의 나눗셈의 합과 같습니다.
그 다음에
기사 출처: Team Tech/Research Alphatrue
참고 출처:
