타원 곡선: Zcash의 키와 커밋먼트가 태어나는 곳

원문 출처: Annkkitaaa

곡선 위의 점으로 만들어진 한 방향 거리

시리즈: Zcash의 기본 원리부터 시작하기 . 제2편. 타원 곡선 대상 독자: 초보자. 제1편 (유한체)에서 설명한 것처럼, 소수를 모듈로 한 산술만 가정합니다. 다른 배경 지식은 필요하지 않습니다. 학습 결과: 타원 곡선에 대한 직관적이고 정확한 그림을 얻고, 그것이 유용하게 작동하는 "트랩도어(trapdoor)"를 이해하고, Zcash가 이를 어떻게 키와 커밋먼트로 변환하는지 알아보게 됩니다.

제1편은 산술을 위한 완벽한 장난감으로서의 유한체를 제공했습니다. 하지만 단순히 수학적인 체만으로는 충분하지 않습니다. Zcash는 키와 제0편에서 설명한 "봉투"를 만들기 위해 특별하고 한 방향성의 어려움을 가진 객체가 필요합니다: 앞으로 계산하기 쉬우면서, 뒤로 추적하는 것은 사실상 불가능해야 합니다. 그 객체는 타원 곡선입니다. 이 문서에서는 대수보다 직관부터 시작하여 타원 곡선을 처음부터 만들어 보겠습니다.

1. 왜 당신이 관심 가져야 하는가?

모든 프라이버시 시스템은 **한 방향 거리(one-way street)**를 필요로 합니다: 앞으로 걷는 것은 간단하지만, 뒤로 걷는 것은 사실상 불가능해야 합니다.

그 이유는 다음과 같습니다. 당신의 비밀 키는 숨겨야 하는 수입니다. 공개 키(및 주소)는 이 비밀 키로부터 도출되어 세상에 드러납니다. 전체 시스템의 보안은 한 가지 사실에 달려 있습니다: 공개 키가 주어졌을 때, 아무도 당신의 비밀 키로 되돌아갈 수 없다는 것. 만약 그럴 수 있다면, 당신의 자산을 지출할 수 있게 됩니다.

그래서 우리는 다음과 같은 수학적 연산이 필요합니다:

• 앞으로(비밀 -> 공개) 계산하기가 빠르고 쉬우며,
• 뒤로(공개 -> 비밀) 계산하기는 지구상의 모든 컴퓨터들이 우주 생존 기간 동안도 완료할 수 없는 정도로 어렵습니다.

단순한 유한체 곱셈은 충분하지 않습니다; 나눗셈은 즉시 이를 무효화합니다(이것이 제1편에서 설명한 이유였습니다). 우리는 "되돌리기" 버튼이 전혀 없는 것을 필요로 합니다. 타원 곡선은 정확히 이 기능을 제공하며, 추가적으로 그 점들이 커밋먼트를 만들기에 완벽하게 결합됩니다. 어떻게 작동하는지 살펴보겠습니다.

2. 직관: 곡선 위의 점들을 "더할 수 있는" 것

잠시 암호학을 잊고 생각해 보세요. 타원 곡선은 단순히 방정식 y^2 = x^3 + ax + b를 만족하는 (x, y) 좌표들의 집합입니다.

일반적인 숫자로 표현하면 매끄럽고 휘어진 곡선으로 보이며, 종종 둥근 루프와 두 개의 꼬리가 있습니다:

정말 놀라운 점은: 이 곡선 위의 두 점을 더하면, 그 곡선 상에 있는 세 번째 점을 얻을 수 있다는 것입니다. 이는 일반적인 좌표의 덧셈이 아닙니다. 기하학적 규칙이며, 말로 설명하기보다는 시각적으로 이해하기 쉬운 것입니다.

채널 규칙 (다른 두 점 더하기)

P + Q를 계산하려면:

1. P와 Q를 지나는 직선을 그립니다.
2. 이 직선은 곡선과 정확히 하나의 다른 위치에서 만납니다. 이를 R*이라고 합니다.
3. 수평 축에 대해 R*을 반사합니다. 이 반사는 결과, 즉 P + Q입니다.

접선 규칙 (같은 점 더하기)

P + P(또는 2P)를 계산하려면 두 번째 점이 없기 때문에, 대신 P에서의 접선을 사용합니다. 그 후 동일한 "세 번째 교차점 찾고 반사" 규칙을 따릅니다.

이게 전부입니다. 두 개의 기하학적 규칙. 이를 통해 타원 곡선의 점들은 수학자들이 말하는 **그룹(group)**을 형성합니다: 잘 정리된 "덧셈" 연산을 가진 집합이며, 심지어 "0"도 있습니다.

무한점 (곡선의 0)

모든 숫자 체계는 0이 필요합니다. 이는 더할 때 아무것도 바꾸지 않는 것입니다. 타원 곡선에서는 특별한 추가 점인 무한점(기호로 O)이 이 역할을 합니다. 이를 "무한히 멀리 위"라고 상상할 수 있으며, 수직선들이 만나는 지점입니다. O를 어떤 점에 더해도 그 점은 변하지 않으며, 이는 0과 동일합니다.

3. 그림에서 유한체로

위의 매끄러운 곡선은 직관이었습니다. 하지만 Zcash는 실수(소수를 모듈로 한 것에 따라 둥글어지고 크기 누출, 제1편 참조)를 사용하지 않습니다. 대신 유한체 위의 타원 곡선(동일한 방정식 y^2 = x^3 + ax + b지만, 소수 모듈로 산술을 사용)을 사용합니다.

이렇게 하면 예쁜 곡선은 분리된 점들의 집합으로 깨지고, 각 (x, y) 쌍이 방정식 mod p를 만족하는 한 개의 점이 됩니다. 더 이상 곡선처럼 보이지 않지만, 중요한 사실은 다음과 같습니다:

채널-접선 규칙의 대수는 여전히 완벽하게 작동합니다. 기하학적으로 P + Q를 찾았던 동일한 공식이 이제 유한체 산술로 계산됩니다. 점들은 여전히 그룹을 형성하며, 동일한 0(무한점)도 있습니다.

실제 예시로 이를 구체화해 보겠습니다.

완전한 곡선, 정확하게 계산된 예시

y^2 = x^3 + 2x + 2를 유한체 F_17 위에서 고려합니다. 모든 유효한 점을 계산하면 18개의 점과 무한점(O)을 포함해 총 19개의 점이 됩니다. 그 중 일부는 다음과 같습니다:

(0,6) (0,11) (3,1) (3,16) (5,1) (5,16) (6,3) (6,14) (7,6) (7,11) ...

이제 G = (5, 1)을 선택하고, 계속해서 자신과 더해보세요. 무슨 일이 일어나는지 확인해 보세요(아래 모든 줄은 계산한 것이며 추측한 것이 아닙니다):

두 가지 주의할 점:

• 모든 18개의 유한점을 방문하고, 19단계에서 O(무한점)에 도달한 후 계속 반복됩니다. 시작점 G는 전체 그룹을 생성하므로 **생성자(generator)**라고 부릅니다.
• 이는 검증된 그룹입니다: 예를 들어 1G + 2G = (5,1) + (6,3) = (10,6)이 정확히 3G와 같습니다. 덧셈은 그룹의 요구사항에 따라 내부적으로 일관됩니다.

4. 트랩도어: 스칼라 곱

1G, 2G, 3G, ...이라는 표는 모든 것의 핵심입니다. 점을 반복해서 더하는 것은 스칼라 곱이라고 불리며, kG는 "G를 k번 더한 값"을 의미합니다.

이제 마법이 시작됩니다. 두 방향을 고려해 보세요:

이 비대칭성은 제1절에서 필요했던 **한 방향 거리(one-way street)**입니다. 뒤로 가는 문제("어떤 k가 이 점을 만들었나?")는 **타원 곡선 이산 로그 문제(ECDLP)**라고 불리며, Zcash가 사용하는 곡선에서는 우주 열사(heat death) 전에는 해결할 수 없다고 알려져 있습니다.

우리의 장난감 F_17 곡선에서는 표에서 바로 k를 읽을 수 있다는 점에 주의하세요. 왜냐하면 이 곡선은 단지 19개의 점만 있기 때문입니다. 실제 곡선은 약 2^(255)개의 점을 가집니다. 표에는 우주에 있는 원자 수보다 더 많은 행이 있을 것이며, "읽기"는 불가능합니다. 이 작은 크기가 장난감 곡선이 가르칠 수 있고, 동시에 보안성이 부족한 이유입니다.

5. 키의 탄생 (결과)

이제 실제 암호학적 키를 설명하기 위해 필요한 모든 것이 있습니다. 놀랍게도 매우 간단합니다:

비밀 숫자 k를 선택하고, 점 kG를 공개하면 됩니다. 그것만으로 충분합니다. k는 당신의 프라이버트 키이며, kG는 당신의 공개 키입니다. 한 방향 거리(ECDLP)가 보장하듯, 아무도 kG를 통해 k로 되돌아갈 수 없습니다.

이 단일한 아이디어, 공개 키는 비밀 스칼라와 고정된 생성자(generator)의 곱이라는 것은 Zcash의 지출 키, 뷰잉 키 및 주소의 기초가 됩니다. 전체 키 트리에는 더 많은 구조가 추가되지만, 모든 가지는 이 뿌리에서 성장합니다.

보너스: 왜 곡선 점이 커밋먼트에 완벽한가?

제0편에서 설명한 "봉투"(커밋먼트)를 다시 생각해보세요. 이 봉투는 내용을 숨기면서도 조작 불가능해야 합니다. 타원 곡선은 이를 깔끔하게 구현할 수 있습니다. 두 개의 고정된 공개 생성자 점 G와 H, 비밀 값 v, 무작위 블라인딩 숫자 r을 선택하고 다음과 같이 형성합니다:

Commitment  =  v.G  +  r.H

이것은 Pedersen 커밋먼트이며, 우리가 원했던 두 가지 특성을 모두 갖습니다:

• 숨김: 무작위 r은 결과를 전체 곡선에 걸쳐 퍼뜨려 v에 대한 정보는 전혀 드러내지 않습니다.
• 결합: ECDLP는 다른 (v, r) 쌍이 동일한 점을 생성하도록 하기 어렵게 만듭니다. 따라서 커밋먼트를 변경할 수 없습니다.

추가적인 특성은 나중에 귀중하게 작용합니다: 이러한 커밋먼트는 더해질 수 있습니다. v_1의 커밋먼트와 v_2의 커밋먼트를 더하면, v_1 + v_2에 대한 유효한 커밋먼트가 됩니다. 이 "호모모픽(homomorphic)" 특성은 Zcash가 나중에 거래 내부로 들어오는 금액이 외부로 나가는 금액과 같음을 증명하는 데 사용됩니다. 이는 약간 후의 제6편에서 활용될 것입니다.

6. Zcash에서 어디에 위치하는가

지문은 구체적이고 확인 가능합니다.

하나의 곡선이 다른 곡선의 필드 내에 "내장"되는 이유와 두 곡선 사이의 "사이클(cycle)"이 왜 유용한지, 이는 증명 시스템 관련 문서에서 다룹니다. 지금은 확실한 결론만 기억하세요: 모든 Zcash 키는 스칼라와 생성자의 곱이며, 모든 Zcash 커밋먼트는 곡선 위의 점들의 합입니다. 이 곡선 중 하나에 존재합니다.

7. 정직한 고백

몇 가지 단순화가 이 문서를 읽기 쉬워지게 했습니다. 우리는 짧은 Weierstrass 형태(y^2 = x^3 + ax + b)를 사용했습니다; Zcash의 곡선은 종종 다른 동등한 형태(예: Jubjub는 twisted Edwards 곡선)로 표현되며, 이는 효율성과 안전성을 위해 선택된 것이지만, 그룹 개념은 동일합니다. 우리는 구체적인 점 추가 공식을 정의하지 않았고("세 번째 교차점, 반사"), "순서(order), cofactors, 'pairings'" 같은 세부 사항도 생략했습니다; 이는 증명 시스템 문서에서 중요하게 다루어질 것입니다. 하지만 이는 직관을 바꾸지 않고 오히려 더 명확하게 합니다.

8. 요약

• 프라이버시 시스템은 한 방향 거리가 필요합니다: 앞으로 갈 때는 쉬우나, 뒤로 가는 것은 불가능해야 합니다. 타원 곡선이 이를 제공합니다.
• 타원 곡선은 y^2 = x^3 + ax + b를 만족하는 점의 집합이며, 그 점들은 기하학적 줄과 접선 규칙을 통해 더할 수 있습니다, 특별한 **무한점(O)**이 0 역할을 합니다.
• 유한체(finite field) 상에서는 곡선이 점들의 산산조각으로 변하지만, 동일한 덧셈은 여전히 작동하며, 이는 그룹을 형성합니다. (검증된 예시: y^2 = x^3 + 2x + 2 over F_17에는 19개의 점이 있으며, G = (5,1)은 모두를 생성합니다.)
• 스칼라 곱 kG는 계산하기 쉬우나 역으로 추적하는 것은 불가능합니다: 이는 ECDLP(타원 곡선 이산 로그 문제)입니다. 이것이 트랩도어입니다.
• 키: 프라이버트 키 k, 공개 키 kG. 커밋먼트: Pedersen 형태 v.G + r.H로, 숨김, 결합, 그리고 더할 수 있는 특성을 가집니다.
• Zcash에서 Sapling은 BLS12-381 + Jubjub, Orchard는 Pallas/Vesta (Pasta) 곡선을 사용하며, 모든 키와 커밋먼트는 이 곡선 위에 존재합니다.

용어집

FAQ

왜 곡선을 사용해야 하며, 단순히 큰 수를 소수로 나눈 것보다는? 둘 다 한 방향 거리를 제공하지만, 타원 곡선은 훨씬 작은 키와 더 빠른 연산으로 동일한 보안성을 달성하며, 점의 산술은 커밋먼트에 이상적입니다.

ECDLP는 증명된 어려움인가? 아니요, 증명되지 않았지만 수십 년간 집중적인 노력으로 잘 선택된 곡선에 대한 효율적인 공격이 발견되지 않았습니다. 보안은 이 잘 검증된 가정에 기반합니다.

양자 컴퓨터는 이를 깨뜨릴 수 있는가? 충분히 큰 양자 컴퓨터는 ECDLP를 깨뜨릴 수 있습니다. 이는 산업 전반에서 알려진 장기적 우려이며, 연구 분야입니다; 오늘날의 곡선은 고전 컴퓨터에 대해 안전합니다.

Zcash가 여러 곡선을 사용하는 이유는? 다른 목적을 위해. 하나의 곡선은 zero-knowledge proof 시스템을 담당하고, 다른 하나(첫 번째 곡선의 필드 내에 포함됨)는 증명 내에서 키와 커밋먼트 연산이 효율적으로 수행되도록 합니다. 다음 문서에서는 이 쌍이 왜 중요한지 설명합니다.

직관을 테스트해 보세요

제3절의 검증된 표를 사용하여, 우리의 장난감 곡선에서 9G + 10G는 무엇인가요? 그리고 답은 G에 대해 어떤 정보를 알려주는가요? (아래에 답이 있습니다.)

다음은 무엇인가

제3편 . 해싱 및 커밋먼트: 우리는 "마법 봉투"를 제대로 열어보겠습니다. 지금까지 곡선 점에서 커밋먼트를 만드는 한 가지 방법을 보았습니다; 다음에는 숨김과 결합이 실제로 무엇인지, 해시 함수를 만나고, 모든 Zcash 지불에 기반하는 노트 커밋먼트와 연결해보겠습니다.

ZecHub의 Zcash from First Principles 시리즈의 일부. CC BY-SA 4.0 라이선스.