작성자: RareSkills
"Pedersen Promise"를 사용하면 타원 곡선 점을 사용하여 임의로 큰 벡터를 표현할 수 있으며 선택적으로 이 벡터에 대한 정보를 숨길 수 있습니다. 이는 벡터 자체를 노출하지 않고 이 점으로 인코딩된 벡터를 증명할 수 있는 중요한 구성 요소를 제공합니다.
동기 부여
Bulletproot 영지식 증명 기술을 논의할 때 사람들은 종종 다음과 같이 말합니다. "우리는 두 개의 벡터를 가지고 있고 그 내부 곱은 c입니다." 이것은 사소해 보일 수 있지만 실제로는 이 메커니즘을 사용하여 매우 복잡한 주장을 증명할 수 있습니다. 이에 대해서는 나중에 자세히 설명하겠습니다.
그러나 이러한 증명 시스템이 작동하려면 이러한 벡터를 증명자만 알 수는 없습니다. 그렇지 않으면 증명자가 마음대로 벡터를 변경할 수 있습니다. 그들은 현실 세계의 수학적 실체여야 합니다. 일반적으로 증명자는 이 두 벡터를 검증자에게 직접 전달하는 것을 원하지 않지만 여전히 검증자에게 "뭔가를 전달"해야 합니다. 이는 벡터 쌍을 선택했으며 더 이상 변경할 수 없음을 나타냅니다.
이것이 바로 Pedersen의 헌신이 필요한 부분입니다.
전제 지식
우리는 독자가 이미 타원 곡선 점 덧셈과 점 곱셈, 그리고 "곡선 위의 점"이 무엇을 의미하는지 잘 알고 있다고 가정합니다. 아직 이해하지 못하셨다면 " 영지식 증명 책 "의 처음 4장을 참조하세요.
표기법에 관해서는 [A] 사용하여 타원 곡선(EC) 점을 나타내고, a 사용하여 유한 필드 의 요소를 나타내며, a[A] 사용하여 이 유한 필드 요소 a 와 타원 곡선 점의 점 곱셈을 나타냅니다. [A] . 그리고 [A] + [B] 표현은 이 두 점의 점 합산을 나타냅니다.
전통적인 약속 제도
스마트 계약에서 약속 공개 기능을 설계할 때 일반적으로 다음 형식을 사용합니다.
commit = hash(value, salt)"salt"는 공격자가 무차별 검색 추측을 방지하는 데 사용되는 임의의 값입니다. 예를 들어, 투표에 전념하는 경우 투표 옵션이 제한되어 있으므로 모든 옵션을 시도하고 해시 값 일치를 확인하여 투표 대상이 누구인지 알 수 있습니다. (소금을 추가하면 이러한 무차별 검색이 작동하지 않습니다.)
이 시나리오에서 소금을 사용하는 것은 " 눈가림 요인"이라는 학문적 용어가 있습니다. 무작위이기 때문에 공격자는 눈이 멀어 약속된 값(위 공식의 "값")이 무엇인지 추측할 수 없습니다.
공격자는 "약속"을 통해 그 뒤에 숨은 가치를 추측할 수 없기 때문에 이 약속 체계 는 은폐 효과가 있다고 말합니다.
가치 공개 단계에서 약속자는 가치와 소금(문헌에서는 " 오프닝 "이라고 함)을 공개하고, 상대방(또는 스마트 계약)은 원래 약속과 일치하는지 확인할 수 있습니다. 동일한 약속 체계에서 다른 쌍 (value, salt) 으로 동일한 약속을 얻는 것이 불가능한 경우, 이 체계 는 구속력이 있다고 말합니다. 약속자가 약속을 공개하면 약속된 값을 변경할 수 없습니다. 즉, 둘은 묶여 있다.)
용어 요약
- 숨겨진 효과가 있는 커밋 방식은 커미터가 선택한 값을 공격자가 알 수 없도록 합니다. 이는 일반적으로 공격자가 추측할 수 없는 임의의 숫자를 추가하여 수행됩니다.
- 블라인드 팩터는 무차별 대입 검색을 통해 약속된 가치를 얻을 수 없게 만드는 난수입니다. 무지식(그러나 단순성만 고려)에 관심이 없는 일부 시나리오에서는 맹목 요소가 사용되지 않을 수 있습니다.
- 기회는 약속의 가치(약속된 가치와 소금)를 계산해 보는 것이다.
- 구속력 있는 약속 체계는 약속자가 다른 기회를 사용하여 동일한 약속을 계산하는 것을 허용하지 않습니다. 즉, 동일한 약속(이 경우 해시)을 계산하는 두 쌍
(value, salt)을 찾을 수 없어야 합니다.
페데르센의 약속
Pedersen의 커밋 방식 패턴은 암호화 해시 함수가 아닌 타원 곡선 그룹을 사용한다는 점을 제외하면 다르지 않습니다.
"타원 곡선의 이산 로그는 다루기 어렵다"는 가정하에 타원 곡선 점 [U] 및 [G] 가 주어지면 [U] = u[G] 만들 수 있는 u 계산할 수 없습니다.
Python 언어 코드 측면에서 보면 다음과 같습니다.
from py_ecc.bn128 import G1, multiplyu = 569723450 # chosen randomlyU = multiply(G1, u)print(U, "cannot compute the discrete log of U") u [U] 의 이산 로그라고 합니다. u 계산할 수 없더라도 그것이 존재한다는 것을 알고 있기 때문에 이를 [U] 의 이산 로그라고 부릅니다. 모든 (암호화) 타원 곡선 점은 계산할 수 없더라도 이산 로그를 갖습니다.
이런 의미에서 타원 곡선 점 곱셈은 해시 함수와 같습니다. 곡선 순서 내에서만 기회를 허용하는 한 바인딩 효과가 있습니다.
그러나 바인딩 효과가 있지만 점 반전을 통해 이산 로그를 반전할 수는 없습니다. u 의 값 범위가 매우 작은 경우 위의 투표 사례와 마찬가지로 정확히 동일한 문제에 직면하게 됩니다. 공격자는 가능한 모든 x 반복하고 x[G] 를 계산하여 x 추측할 수 있습니다.
다음과 같은 방법으로 "Pedersen 스타일 은폐"를 달성할 수 있습니다.
commitment = v[G] + s[Q] 여기서 v 는 우리가 커밋하려는 값이고 s 는 솔트(블라인딩 팩터)입니다. Q 는 약속자에게 이산 로그가 알려지지 않은 또 다른 타원 곡선 점입니다.
이산 로그는 알 수 없지만 [G] 와 [Q] 모두 공개되어 검증자와 커미터 모두에게 알려져 있다는 점을 강조하고 싶습니다.
약속자는 왜 [Q]
약속자가 [Q] [Q] = d[G] 뒤에 있는 이산 로그를 알고 있다고 가정합니다. 이를 통해 약속자는 동일한 약속으로 두 가지 기회를 식별할 수 있습니다. 원리는 다음과 같습니다.
[C] = v[G] + s[Q] = 10[G] + 15[Q] = 10[G] + 15[dG] [C′] = 11[G] + (15d−1)[G] [C] = [C′] 독자는 수동으로 d 숫자로 대체하여 작동 방식을 확인할 수 있습니다.
약속자는 자신이 사용하는 타원 곡선 점의 이산 로그 관계를 알 수 없습니다.
이를 보장하는 한 가지 방법은 검증자가 이 타원 곡선 지점을 커미터에게 제공하도록 하는 것입니다. 그러나 더 간단한 접근 방식은 무작위적이고 투명한 방식으로 타원 곡선 점을 선택하는 것입니다(예: 의사 무작위로 타원 곡선 점 선택). 임의의 타원 곡선 점이 주어지면 이산 로그를 알 수 없습니다.
예를 들어 생성기( [G] )로 시작하여 x 좌표와 y 좌표를 해시한 다음 의사 무작위이지만 결정적인 함수를 제공하여 다음 지점을 찾을 수 있습니다.
Pedersen 서약의 용도는 무엇입니까?
Pedersen 커밋은 다른 해시 함수를 사용하는 일반적인 커밋 방식인 것 같습니다. 어디에 유용합니까?
이 프로그램에는 많은 이점이 있습니다.
동형이 추가될 수 있음
생성기 [G] 가 주어지면 a[G] + b[G] = (a + b)[G] 두 가지 약속을 함께 추가할 수 있습니다. 무작위로 블라인드 개인 정보 보호를 추가하더라도 여전히 효과적인 기회를 만들 수 있습니다.
$$
C_1 = a[G] + s_1[Q] \
C_2 = b[G] + s_2[Q] \
C_3 = C_1 + C_2 \
약속 공개\
(a, b, s_1 + s_2) \
유효성 검사기 확인\
C_3 ?= a[G] + b[G] + (s_1 + s_2)[Q]
$$
기존 암호화 해시 함수(예: SHA256)는 이를 수행할 수 없습니다.
(Pedersen Promise에서) b[G] 와 s[Q] 추가될 때 서로 "충돌"하지 않습니다.
다음 방정식이 성립한다는 것을 아시나요?
(a[G]+b[H]) + (c[G]+d[H]) = (a+c)[G] + (c+d)[H] (여기서 [G] 와 [H] 알 수 없는 이산 로그의 두 타원 곡선 점입니다.)
타원 곡선 점을 직교 차원의 선형 결합의 기초로 생각할 수 있습니다.
유한 필드 요소 $a_1, a_2, b_1, b_2$ 및 타원 곡선 점 [G] 및 [H] 있고 [G] 가 [H] 와 같지 않은 경우 $a_1 \ne a_2$, $b_1 \ ne b_2$ , $a_1[G] + b_1[H] = a_2[G] + b_2[H]$인 경우에도 이산 로그를 우회하여 $(a_1, a_2, b_1, b_2)$를 해결하는 것은 여전히 불가능합니다. 문제.
더욱이 타원 곡선 그룹의 순서가 충분히 크면 운이 좋게 일치하는 항목을 찾을 가능성이 훨씬 더 낮습니다.
즉, 두 사람이 각자의 약속 [C] = a[G] + b[H] 및 [C'] = a'[G] + b'[H] 및 $a $ 및 $b \ne b'$. [G] 와 [H] 의 이산 로그를 알 수 없는 한 [C] 가 [C'] 와 같을 가능성은 없습니다.
Pedersen은 친절하게 대할 것을 약속합니다.
유일한 요구 사항은 일반 산술 연산이므로 타원 곡선에서 덧셈과 곱셈을 위한 회로를 만드는 것은 상대적으로 쉽습니다. 그러나 일반 해시 함수는 영지식 증명으로 코딩된 회로가 필요한 비트 이동 및 배타적 OR 연산(XOR)을 사용합니다.
여러 개의 포인트를 하나의 포인트로 인코딩할 수 있습니다.
[G] 와 [Q] 사용한 예는 눈을 멀게 하는 요소가 없는 2차원 벡터 커밋으로 생각할 수도 있습니다. 그러나 원하는 수의 스칼라를 적용하여 타원 곡선 점 $[G_1, G_2,…, G_n]$을 원하는 수만큼 추가할 수도 있습니다.
페데르센 벡터 약속
우리는 위의 계획을 한 단계 더 발전시켜 가치와 맹목적인 달러가 아닌 일련의 가치를 약속합니다.
벡터 약속 방식
임의의 타원 곡선 점 집합($[G_1, G_2,…, G_n]$)(그들의 이산 로그는 우리에게 알려지지 않음)이 있다고 가정하면 다음과 같이 할 수 있습니다.
$$\underbrace{[C] = v_1[G_1] + v_2[G_2] + … + v_n[G_n]} {커밋된 값} + \underbrace{r[Q]} {블라인딩 팩터}$$
이를 통해 Promise [C] 로 많은 값을 약속하고 r 로 숨길 수 있습니다.
커미터는 생성기 뒤에 있는 이산 로그를 모르기 때문에 [C] 의 이산 로그를 알 수 없습니다. 따라서 이 방식은 바인딩 효과가 있습니다. 다른 벡터 세트가 아닌 $[v_1, v_2,…, v_n]$를 사용하여 Promise [C] 만 생성할 수 있습니다.
벡터 약속은 집계될 수 있습니다.
두 개의 Pedersen 벡터 Promise를 추가하여 두 벡터에 대한 Promise를 얻을 수 있습니다. 약속자는 여전히 원래 벡터를 사용하여 공개할 수 있습니다. 여기서 중요한 구현 세부 사항은 두 개의 서로 다른 타원 곡선 점 세트를 사용하여 원래의 두 벡터 약속을 생성해야 한다는 것입니다.
$$
[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q] \
[C_2] = w_1[H_1] + w_2[H_2] + … + w_n[H_n] + s[Q] \
[C_3] = [C_1] + [C_2]
$$
여기서 r[Q] 와 s[Q] 눈가림 요소입니다. 인스턴트 약속자에는 약속 벡터가 없으며 전체 약속은 여전히 임의의 지점처럼 보입니다.
커미터는 나중에 원래 벡터 $[v_1, v_2,…, v_n]$ 및 $[w_1, w_2,…, w_n]$뿐만 아니라 블라인드 팩터 r + s 공개할 수 있습니다. 이는 또한 구속력 있는 효과를 가지며 다른 벡터 세트 및 블라인드 요소와 동일한 약속을 생성할 수 없습니다.
한 벡터 세트에는 $[G_1, G_2,…, G_n]$를 사용하고 다른 세트에는 $[H_1, H_2,…, H_n]$를 사용합니다. 이는 이러한 [G_i] 생성기와 [H_i] 생성기가 다음과 같다는 의미는 아닙니다. 내부 특별한 관계는 무엇입니까? 이 모든 점은 의사 무작위로 선택되어야 합니다. 이는 단지 표기상의 우연일 뿐이므로 "이 타원 곡선 점 벡터는 이 유한 필드 요소 벡터 세트와 일치하고 해당 타원 곡선 점 벡터는 해당 유한 필드 요소 벡터와 일치합니다"라고 직접적으로 말할 수 있습니다.
우리가 커밋할 수 있는 벡터 수에는 본질적인 상한이 없습니다.
독자를 테스트하십시오 . 두 개의 약속에 대해 동일한 생성자 $[G_1, G_2,..., G_n]$를 사용한 다음 이를 함께 추가하는 경우 약속자는 $[C_3]$에 대한 두 개의 서로 다른 벡터 세트를 어떻게 공개합니까? 예를 들어, 다른 타원 곡선 점 세트 $[H_1, H_2,…, H_n]$를 사용하여 이를 피할 수 있습니까?
독자 퀴즈 : 약속한 가치가 공개되었을 때 약속자가 그 입장을 바꾸면 어떻게 될까요?
예를 들어, 그는 이렇게 약속했습니다.
$$[C_1] = v_1[G_1] + v_2[G_2] + … + v_n[G_n] + r[Q]$$
그러나 공개 기회는 다음과 같습니다.
$$[v_2, v_1, v_3, v4,…,v_n]$$
즉, 약속자는 처음 두 요소의 위치를 바꾸지만 다른 모든 요소는 변경되지 않은 상태로 둡니다. $[G_1, G_2,…, G_n]$ 벡터는 교환 가능하지 않다고 가정합니다.
무작위 포인트를 투명하게 생성
이러한 임의의 타원 곡선 점을 어떻게 생성할 수 있습니까? 확실한 해결책은 신뢰할 수 있는 시작 설정을 사용하는 것이지만 이것이 반드시 필요한 것은 아닙니다. 커미터는 우리가 모르는 이산 로그의 일부 포인트를 투명하게 무작위로 선택할 수 있습니다.
먼저 생성기 [G] 선택하고 이를 공개적으로 선택된 난수와 혼합한 다음 결과를 해시하여(모듈로 field_modulus 필요) 다른 값을 얻을 수 있습니다. x 값으로서의 결과가 타원 곡선에 해당하는 경우 이를 다음 생성기로 사용하고 해당 (x, y) 좌표 값을 다시 해시합니다. 반대로 타원 곡선에 x 값으로 해당 점이 없으면 해당 타원 곡선 점이 생길 때까지 x 값을 증가시킵니다. 커미터는 포인트를 생성하지 않았기 때문에 포인트의 이산 로그를 알 수 없습니다. 이 알고리즘의 구현 세부 사항은 독자의 연습 문제로 남겨 둡니다.
어떤 경우에도 곱셈을 통해 점을 생성해서는 안 됩니다. 이렇게 하면 이산 로그를 알 수 있기 때문입니다. 해시 함수를 통해 x 값을 의사 무작위로 도출하고 그것이 타원 곡선에 속하는지 확인해야 합니다.
생성기 [G] (이산 로그가 1로 알려져 있음)에서 시작한 다음 다른 점을 생성하는 것도 가능합니다.
독자를 위한 연습 문제 : 점 [G1] 및 [G2] 가 있는 2차원 벡터를 커밋했다고 가정합니다. [G1] 의 이산 로그는 알려져 있지만, [G2] 의 이산 로그는 알려져 있지 않습니다. (지금은 눈을 멀게 하는 요인을 무시합니다). 약속자는 약속을 밝히기 위해 또 다른 2차원 벡터를 사용할 수 있습니까? 왜?
(위에)
