서로를 신뢰하지 않으면 난수를 생성할 수 있나요? 2 부

헤이 하브르!

В 첫 번째 부분 이 글에서는 서로 신뢰하지 않는 참여자들을 위해 난수를 생성하는 것이 왜 필요한지, 이러한 난수 생성기에 대한 요구 사항은 무엇인지, 그리고 이를 구현하는 두 가지 접근 방식을 고려했습니다.

이 글의 이 부분에서는 임계값 시그니처를 사용하는 또 다른 접근 방식을 자세히 살펴보겠습니다.

약간의 암호화

임계값 서명이 작동하는 방식을 이해하려면 기본적인 암호화에 대한 이해가 필요합니다. 우리는 두 가지 개념을 사용할 것입니다: 스칼라 또는 단순히 숫자, 우리는 소문자로 표시합니다(x, y) 그리고 타원 곡선 위의 점들은 대문자로 표시하겠습니다.

임계값 시그니처의 기본 사항을 이해하려면 타원 곡선의 작동 방식을 이해할 필요는 없지만, 몇 가지 기본적인 사항은 알 수 있습니다.

1. 타원 곡선의 점은 스칼라로 추가되거나 곱해질 수 있습니다(스칼라로 곱하는 것을 다음과 같이 표시함). xG, 표기법은 Gx (문학에서도 종종 사용됨). 스칼라를 더하고 곱한 결과는 타원 곡선 위의 점입니다.

2. 요점만 알고 G 그리고 그 곱은 스칼라와 함께 xG 계산할 수 없다 x.

우리는 또한 다항식의 개념을 사용할 것입니다 피(x) 학위 k-1. 특히, 우리는 다항식의 다음 속성을 사용할 것입니다: 우리가 값을 알고 있다면 피(x) 어떤 것에 대해서든 k 다른 x (그리고 우리는 더 이상에 대한 정보가 없습니다 피(x)), 우리는 계산할 수 있습니다 피(x) 다른 어떤 것에 대해서도 x.

모든 다항식에 대해 흥미로운 점은 피(x) 그리고 곡선의 어떤 지점 G, 의미를 알고 p(x)G 어떤 것에 대해서든 k 다른 의미 x, 계산할 수도 있습니다 p(x)G 어떤 것에 대해서든 x.

이 정보는 임계값 서명이 작동하는 방식과 임계값 서명을 사용하여 난수를 생성하는 방법에 대한 세부 정보를 파헤치는 데 충분합니다.

임계값 서명에 대한 난수 생성기

가정해보자 n 참가자들은 난수를 생성하고 싶어하며 우리는 모든 사람이 참여하기를 원합니다. k 그 중 일부는 숫자를 생성하기에 충분했지만, 공격자는 통제하고 있었습니다. k-1명 이하의 참여자는 생성된 숫자를 예측하거나 영향을 미칠 수 없습니다.

이런 다항식이 있다고 가정해보자. 피(x) 학위 k-1, 첫 번째 참가자가 아는 것 피(1), 두 번째는 알고 있다 p(2), 등등 (n-th는 알고 있다 p(n)). 또한 미리 결정된 지점에 대해 가정해 보겠습니다. G 모두들 알고있다. p(x)G 모든 가치에 대해 x. 우리는 전화할 것이다 피(i) "개인 구성 요소" i-번째 참가자(만 해당) i-번째 참가자는 그녀를 알고 있습니다. 돼지 "공용 구성 요소" i-번째 참가자(모든 참가자가 그녀를 알고 있기 때문). 당신이 기억하는 것처럼, 지식 돼지 복구하기에 충분하지 않다 p(i).

이러한 다항식을 생성하여 다음과 같은 경우에만 i-참가자 중 한 명만 그의 사생활을 알고 다른 사람은 아무도 모른다는 점이 프로토콜에서 가장 복잡하고 흥미로운 부분인데, 아래에서 분석해보겠습니다. 지금은 그러한 다항식이 있고 모든 참가자가 자신의 비공개 구성 요소를 알고 있다고 가정해 보겠습니다.

이런 다항식을 이용해서 어떻게 난수를 생성할 수 있을까? 첫째, 이전에 생성기의 입력으로 사용된 적이 없는 문자열이 필요합니다. 블록체인의 경우 마지막 블록의 해시값은 h — 이런 라인에 적합한 후보입니다. 참가자들이 다음을 사용하여 난수를 생성하도록 합니다. h 씨앗으로. 첫째, 참가자들은 전환합니다 h 미리 정의된 함수를 사용하여 곡선의 한 지점까지:

H = 스칼라ToPoint(h)

그런 다음 각 참가자 i 계산하고 게시합니다 안녕하세요 = p(i)H, 그들이 알고 있기 때문에 할 수 있는 일 p(i)와 H. 공개 H다른 참가자가 개인 구성 요소를 복원하는 것을 허용하지 않습니다. i-번째 참여자이므로 한 세트의 개인 구성 요소를 블록 간에 사용할 수 있습니다. 따라서 아래에 설명된 값비싼 다항식 생성 알고리즘은 한 번만 수행하면 됩니다.

언제 k 참가자들은 노출되었다 안녕하세요 = p(i)H, 누구나 알아낼 수 있다 H엑스 = p(x)H 모두를위한 x 이는 이전 섹션에서 논의했던 다항식의 속성 덕분입니다. 이 시점에서 모든 참가자는 계산합니다. H0 = p(0)H, 그리고 이것이 난수의 결과입니다. 아무도 모른다는 점을 명심하세요. p(0), 따라서 계산할 수 있는 유일한 방법은 p(0)H – 이것은 보간입니다 p(x)H, 이는 오직 다음과 같은 경우에만 가능합니다. k 값 p(i)H 알려져 있습니다. 더 적은 수량의 개봉 p(i)H 에 대한 정보를 제공하지 않습니다 p(0)H.

위의 생성기는 우리가 원하는 모든 속성을 가지고 있습니다: 공격자가 제어하는 ​​것만 k-1명 이하의 참가자는 결과에 대한 정보나 영향력이 없는 반면, k 참가자는 결과 숫자를 계산할 수 있으며, 그 하위 집합은 다음과 같습니다. k 참가자들은 항상 같은 시드에 대해 같은 결과에 도달하게 됩니다.

우리는 위에서 신중하게 피했던 문제 중 하나가 있습니다. 보간이 작동하려면 값이 중요합니다. H각 참가자가 게시한 i i 정말 똑같았어요 p(i)H. 왜냐하면 다른 누구도 i- 참가자가 모른다 p(i), 아무도 없지만 i-참가자는 그것을 확인할 수 없습니다 Hi 실제로는 정확하게 계산되었으며 정확성에 대한 암호화 증명이 없습니다. H공격자는 어떤 값이라도 게시할 수 있습니다. 안녕, 그리고 난수 생성기의 출력에 임의로 영향을 미칩니다.:

첫 번째 참가자가 보낸 H_1의 다른 값은 다른 결과 H_0로 이어집니다.

정확성을 증명하는 방법은 적어도 두 가지가 있습니다. H나. 다항식의 생성을 분석한 후에 이를 고려해 보도록 하자.

다항식 생성

마지막 섹션에서 우리는 다음과 같은 다항식을 가지고 있다고 가정했습니다. 피(x) 학위 k-1 참여자 i 알고있다 피(i), 그리고 이 의미에 대한 정보를 아는 사람은 아무도 없습니다. 다음 섹션에서는 미리 결정된 지점에 대해서도 필요합니다. G 모두가 알고 있었다 p(x)G 모두를위한 x.

이 섹션에서는 각 참가자가 로컬하게 개인 키를 가지고 있다고 가정합니다. 시, 모든 사람이 해당 공개 키를 알 수 있도록 Xi.

가능한 다항식 생성 프로토콜 중 하나는 다음과 같습니다.

1. 각 참가자 i 로컬하게 임의의 다항식을 생성합니다 k-1차의 pi(x). 그런 다음 각 참가자에게 보냅니다. j 가치 pi(j), 공개 키로 암호화됨 엑스제이. 그래서만 i-일 и j-일 참가자는 알고 있다 pi(j). 참가자 i 또한 공개적으로 발표합니다 파이(j)G 모두를위한 j 부터 1 에 k 포함한다.

2. 모든 참가자는 어떤 합의를 통해 선택합니다. k 다항식을 사용할 참가자. 일부 참가자가 오프라인일 수 있으므로 모든 사람이 참여할 때까지 기다릴 수 없습니다. n 참가자들은 다항식을 발표할 것입니다. 이 단계의 결과는 다음과 같습니다. Z 최소한으로 구성된 k (1)단계에서 생성된 다항식.

3. 참가자들은 자신들이 알고 있는 가치가 pi(j)는 공개적으로 발표된 것과 일치합니다. 파이(j)G. 이 단계 이후에 Z 비공개로 전송된 다항식만 pi(j)는 공개적으로 발표된 것과 일치합니다. 파이(j)G.

4. 각 참가자 j 개인 구성 요소를 계산합니다 p(j) 합계로서 p모든 i(j)에 대해 i в Z. 각 참가자는 또한 모든 값을 계산합니다. p(x)G 합계로서 모든 i에 대한 pi(x)G в Z.

참고 p(x) – 이것은 실제로 차수의 다항식입니다 케이-1, 그것은 개인의 합계이기 때문입니다 pi(x)는 각각 차수의 다항식입니다. k-1. 그런 다음 각 참가자가 j 알고있다 p(j), 그들은 그것에 대한 정보가 없습니다 피(x) 에 x ≠ j. 실제로 이 값을 계산하려면 모든 것을 알아야 합니다. 파이(x), 그리고 참가자가 j 선택된 다항식 중 적어도 하나를 모르면 그에 대한 충분한 정보가 없습니다. p(x).

이는 마지막 섹션에서 필요했던 다항식을 생성하는 전체 과정입니다. 위의 1, 2, 4단계는 구현 방법이 매우 명확합니다. 하지만 3단계는 그렇게 간단한 것이 아닙니다.

특히, 우리는 암호화된 것을 증명할 수 있어야 합니다. pi(j)는 게시된 것과 일치합니다. 파이(j)G. 우리가 그것을 증명할 수 없다면 공격자는 i 대신 쓰레기를 보낼 수 있어요 pi(j) 참가자 j, 그리고 참가자 j 실제 의미를 알 수 없을 것이다 파이(j), 그리고 개인 구성 요소를 계산할 수 없습니다..

추가 메시지를 생성할 수 있는 암호화 프로토콜이 있습니다. 증명i(j)는 어떤 가치를 갖는 모든 참가자가 e, 뿐만 아니라, 증명(j) и pi(j)G는 로컬하게 확인할 수 있습니다. e - 정말 그래요 파이(j), 참가자의 키로 암호화됨 j. 불행히도 그러한 증거의 규모는 엄청나게 크고 이를 공개해야 한다는 점을 감안할 때 오(nk) 이러한 증거는 이 목적으로 사용될 수 없습니다.

그것을 증명하는 대신 파이(j) 일치 pi(j)G 우리는 다항식 생성 프로토콜에서 모든 참여자가 수신된 암호화된 내용을 확인하는 매우 긴 시간을 할당할 수 있습니다. 파이(j), 그리고 복호화된 메시지가 공개된 메시지와 일치하지 않으면 pi(j)G에서 그들은 자신들이 받은 암호화된 메시지가 정확하지 않다는 것을 증명하는 암호화된 증거를 공개합니다. 메시지가 증명됨 아니 일치 돼지) 그것이 대응한다는 것을 증명하는 것보다 훨씬 쉽습니다. 여기서 주목할 점은 각 참여자가 해당 증명을 만드는 데 할당된 시간 동안 적어도 한 번은 온라인에 접속해야 하며, 해당 증명을 게시하면 할당된 동일한 시간 내에 다른 모든 참여자에게 전달된다는 가정에 의존한다는 것입니다.

참가자가 이 기간 동안 온라인에 나타나지 않고 실제로 하나 이상의 잘못된 구성 요소를 가지고 있는 경우, 해당 참가자는 추가 숫자 생성에 참여할 수 없습니다. 그러나 최소한 다음이 있는 경우 프로토콜은 계속 작동합니다. k 할당된 시간 내에 올바른 구성 요소를 받았거나, 틀렸다는 증거를 남긴 참가자.

H_i의 정확성 증명

마지막으로 논의해야 할 부분은 게시된 내용의 정확성을 증명하는 방법입니다. H나, 즉 그것 안녕하세요 = p(i)H, 열지 않고 p(i).

우리는 가치를 기억하자 H, G, p(i)G 공개적이고 모든 사람이 알고 있음. 수신 작업 피(i) 앎 돼지 и G 이산대수라고 불리기도 합니다. 디로그, 그리고 우리는 다음 사실을 증명하고 싶습니다.

dlog(p(i)G, G) = dlog(Hi, H)

공개하지 않고 피(i). 이러한 증명에 대한 구성은 다음과 같습니다. 슈노르 프로토콜.

이 디자인을 통해 각 참가자는 함께 Hi 구성에 따라 정확성 증명을 보냅니다.

난수가 생성되면, 난수를 생성한 사람 외의 다른 참여자가 그 난수를 사용해야 하는 경우가 많습니다. 해당 참가자는 번호와 함께 모든 정보를 보내야 합니다. Hi 그리고 이를 뒷받침하는 증거.

호기심 많은 독자는 다음과 같이 질문할 수 있습니다. 최종 난수는 다음과 같습니다. H0, 그리고 p(0)G – 이건 공개된 정보인데 왜 개인마다 증거가 필요한가요? H나, 왜 그 대신에 증거를 보내지 않는가

디로그(p(0)G, G) = dlog(H0, H)

문제는 아무도 값을 모르기 때문에 Schnorr 프로토콜을 사용하여 그러한 증명을 생성할 수 없다는 것입니다. 피(0)이는 증명을 만드는 데 필요하며, 더 나아가 전체 난수 생성기는 아무도 이 값을 모른다는 사실에 기반을 두고 있습니다. 따라서 모든 값을 갖는 것이 필요합니다. Hi 그리고 정확성을 증명하기 위한 개별 증거 H0.

그러나 타원 곡선의 점에 대한 연산이 곱셈과 의미적으로 유사한 경우 정확성 증명은 다음과 같습니다. H0 그것은 사소한 일일 것입니다. 우리는 단순히 그것을 확인할 것입니다.

H0 × G = p(0)G × H

선택된 곡선이 지원하는 경우 타원 곡선 짝짓기, 이런 증명은 유효합니다. 이 경우에는 H0은 참가자라면 누구나 검증할 수 있는 난수 생성기의 출력일 뿐만 아니라 지, 에이치 и p(0)G. 시간0은 또한 시드로 사용된 메시지의 서명으로 다음을 확인합니다. k и n 참가자들은 이 메시지에 서명했습니다. 그래서, 만약 씨앗 - 이것은 블록체인 프로토콜의 블록 해시입니다. H0 – 블록 상의 다중 서명이자 매우 뛰어난 난수입니다.

결론적으로

이 기사는 기술 블로그 시리즈의 일부입니다. NEAR. NEAR는 최종 사용자의 개발 용이성과 사용 편의성에 초점을 맞춘 분산형 애플리케이션을 개발하기 위한 블록체인 프로토콜 및 플랫폼입니다.

프로토콜 코드는 공개되어 있으며 구현은 Rust로 작성되었으며 찾을 수 있습니다. 여기에.

NEAR의 개발 과정을 확인하고 온라인 IDE에서 실험해 볼 수 있습니다. 여기에.

다음 사이트에서 러시아어로 된 모든 뉴스를 확인하실 수 있습니다. 전보 그룹 과 VKontakte의 그룹, 그리고 공식적으로 영어로 트위터.

곧!겠습니다!

출처 : habr.com