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

헤이 하브르!

이 기사에서는 서로를 신뢰하지 않는 참가자의 의사 난수 생성에 대해 이야기하겠습니다. 아래에서 볼 수 있듯이 "거의" 좋은 생성기를 구현하는 것은 매우 간단하지만 매우 좋은 생성기는 어렵습니다.

서로를 신뢰하지 않는 참가자들 사이에서 난수를 생성해야 하는 이유는 무엇입니까? 한 가지 응용 분야는 분산형 응용 프로그램입니다. 예를 들어 참가자의 베팅을 수락하고 49% 확률로 금액을 두 배로 늘리거나 51% 확률로 빼는 애플리케이션은 편견 없이 난수를 받을 수 있는 경우에만 작동합니다. 공격자가 난수 생성기의 결과에 영향을 미칠 수 있고 응용 프로그램에서 지불금을 받을 가능성이 조금이라도 높아진다면 공격자는 이를 쉽게 파괴할 것입니다.

분산 난수 생성 프로토콜을 설계할 때 다음 세 가지 속성을 갖기를 원합니다.

1. 그는 편견이 없어야 합니다. 즉, 어떤 참가자도 난수 생성기의 결과에 어떤 식으로든 영향을 주어서는 안 됩니다.

2. 그는 예측할 수 없는 사람임에 틀림없다. 즉, 어떤 참가자도 숫자가 생성되기 전에 어떤 숫자가 생성될지 예측(또는 해당 속성을 추론)할 수 없어야 합니다.

3. 프로토콜은 실행 가능해야 합니다. 즉, 특정 비율의 참가자가 네트워크 연결을 끊거나 의도적으로 프로토콜을 중지하려고 한다는 사실에 저항할 수 있어야 합니다.

이 기사에서는 RANDAO + VDF와 삭제 코드 접근 방식의 두 가지 접근 방식을 살펴보겠습니다. 다음 부분에서는 임계값 서명을 기반으로 한 접근 방식을 자세히 살펴보겠습니다.

하지만 먼저 실행 가능하고 예측 불가능하지만 편향된 간단하고 일반적으로 사용되는 알고리즘을 살펴보겠습니다.

란다오

RANDAO는 매우 간단하므로 무작위성을 생성하는 데 매우 일반적으로 사용되는 접근 방식입니다. 모든 네트워크 참가자는 먼저 로컬에서 의사 난수를 선택한 다음 각 참가자가 선택한 번호의 해시를 보냅니다. 다음으로, 참가자들은 자신이 선택한 번호를 차례로 공개하고, 공개된 번호에 대해 XOR 연산을 수행하며, 이 연산의 결과가 프로토콜의 결과가 됩니다.

공격자가 다른 참가자의 번호를 본 후 자신의 번호를 선택할 수 없도록 번호를 공개하기 전에 해시를 게시하는 단계가 필요합니다. 이를 통해 그는 사실상 난수 생성기의 출력을 혼자서 결정할 수 있게 되었습니다.

프로토콜이 진행되는 동안 참가자는 공통 결정(소위 합의)을 두 번 내려야 합니다. 즉, 선택한 숫자 공개를 시작하여 해시 수락을 중지할 시점과 선택한 숫자 수락 및 결과 무작위 계산을 중지할 시점을 결정해야 합니다. 숫자. 서로를 신뢰하지 않는 참가자들 사이에서 그러한 결정을 내리는 것은 그 자체로 쉬운 작업이 아니며 향후 기사에서 이에 대해 다시 설명할 것입니다. 이 기사에서는 그러한 합의 알고리즘을 사용할 수 있다고 가정합니다.

위에서 설명한 속성 중 RANDAO에는 어떤 속성이 있습니까? 이는 예측할 수 없고 기본 합의 프로토콜과 동일한 활력을 갖고 있지만 편향되어 있습니다. 특히, 공격자는 네트워크를 관찰할 수 있으며, 다른 참가자가 자신의 숫자를 공개한 후 XOR을 계산하고 결과에 영향을 미치기 위해 자신의 숫자를 공개할지 여부를 결정할 수 있습니다. 이는 공격자가 난수 생성기의 출력을 단독으로 결정하는 것을 방지하지만 여전히 1비트의 영향력을 제공합니다. 그리고 공격자가 여러 참가자를 제어하는 ​​경우 공격자가 제어하는 ​​비트 수는 자신이 제어하는 ​​참가자 수와 동일합니다.

참가자에게 숫자를 순서대로 공개하도록 요구함으로써 공격자의 영향력을 크게 줄일 수 있습니다. 그러면 공격자는 마지막에 열린 경우에만 결과에 영향을 미칠 수 있습니다. 영향력은 상당히 적지만 알고리즘은 여전히 ​​편향되어 있습니다.

란다오+VDF

RANDAO를 편향되지 않게 만드는 한 가지 방법은 다음과 같습니다. 모든 숫자가 공개되고 XOR이 계산된 후 그 결과가 함수의 입력으로 제공됩니다. 이는 계산하는 데 매우 오랜 시간이 걸리지만 결과의 정확성을 확인할 수 있습니다. 매우 빠르게 계산됩니다.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

이 함수를 검증 가능한 지연 함수(VDF)라고 합니다. 최종 결과를 계산하는 데 숫자 공개 단계보다 시간이 오래 걸리면 공격자는 자신의 숫자를 표시하거나 숨기는 효과를 예측할 수 없으므로 결과에 영향을 줄 수 있는 기회를 잃게 됩니다.

좋은 VDF를 개발하는 것은 매우 어렵습니다. 최근 몇 가지 획기적인 발전이 있었습니다. 이 и 이 하나 이는 실제로 VDF를 더욱 실용적으로 만들었으며 Ethereum 2.0은 장기적으로 VDF와 함께 RANDAO를 난수 소스로 사용할 계획입니다. 이 접근 방식은 예측 불가능하고 편견이 없다는 사실 외에도 네트워크에 최소 두 명의 참가자가 있는 경우 실행 가능하다는 추가 이점이 있습니다(사용되는 합의 프로토콜이 그렇게 적은 수의 참가자를 처리할 때 실행 가능하다고 가정).

이 접근 방식의 가장 큰 과제는 매우 값비싼 전문 하드웨어를 가진 참가자라도 검색 단계가 끝나기 전에 VDF를 계산할 수 없도록 VDF를 설정하는 것입니다. 이상적으로 알고리즘은 상당한 안전 마진(예: 10배)을 가져야 합니다. 아래 그림은 RANDAO 확인을 공개하기 위해 할당된 시간보다 더 빠르게 VDF를 실행할 수 있는 특수 ASIC을 보유한 행위자의 공격을 보여줍니다. 이러한 참가자는 자신의 번호를 사용하거나 사용하지 않고 최종 결과를 계산할 수 있으며 계산에 따라 표시 여부를 선택할 수 있습니다.

위에서 언급한 VDF 제품군의 경우 전용 ASIC의 성능은 기존 하드웨어보다 100배 이상 높을 수 있습니다. 따라서 배포 단계가 10초 동안 지속된다면 해당 ASIC에서 계산된 VDF는 100배의 안전 마진을 확보하기 위해 10초 이상이 소요되어야 하며, 따라서 상용 하드웨어에서 계산된 동일한 VDF는 100x 100초 = ~3시간이 소요되어야 합니다.

Ethereum Foundation은 공개적으로 사용 가능한 무료 ASIC을 만들어 이 문제를 해결할 계획입니다. 이런 일이 발생하면 다른 모든 프로토콜도 이 기술을 활용할 수 있지만 그때까지는 RANDAO+VDF 접근 방식이 자체 ASIC 개발에 투자할 수 없는 프로토콜에 적합하지 않습니다.

VDF에 관한 많은 기사, 비디오 및 기타 정보가 수집되었습니다. 이 사이트.

삭제 코드를 사용합니다

이 섹션에서는 다음을 사용하는 난수 생성 프로토콜을 살펴보겠습니다. 코드 지우기. 실행 가능한 상태로 유지되는 동안 최대 ⅓의 공격자를 허용할 수 있으며, 결과를 예측하거나 영향을 미치기 전에 최대 ⅔의 공격자가 존재할 수 있도록 허용합니다.

프로토콜의 주요 아이디어는 다음과 같습니다. 단순화를 위해 정확히 100명의 참가자가 있다고 가정해 보겠습니다. 또한 모든 참가자가 로컬에서 일부 개인 키를 갖고 있고 모든 참가자의 공개 키가 모든 참가자에게 알려져 있다고 가정해 보겠습니다.

1. 각 참가자는 로컬에서 긴 문자열을 만들어 67개 부분으로 나누고, 100개면 문자열을 복구하기에 충분하도록 67개의 공유를 얻기 위한 삭제 코드를 생성하고, 100개의 공유 각각을 참가자 중 한 명에게 할당하고 다음과 같이 암호화합니다. 동일한 참가자의 공개 키. 그러면 인코딩된 모든 공유가 게시됩니다.

2. 참가자는 특정 67명의 참가자의 코드화된 세트에 대한 합의에 도달하기 위해 일종의 합의를 사용합니다.

3. 합의에 도달하면 각 참가자는 자신의 공개 키로 암호화된 67개 세트 각각에서 암호화된 공유를 가져와 이러한 모든 공유를 해독하고 해독된 모든 공유를 게시합니다.

4. 67명의 참가자가 (3)단계를 완료하면 삭제 코드의 속성으로 인해 합의된 모든 세트가 완전히 디코딩 및 재구성될 수 있으며, 최종 번호는 (1)에서 참가자가 시작한 초기 행의 XOR로 얻을 수 있습니다. .

이 프로토콜은 편견이 없고 예측할 수 없는 것으로 나타날 수 있습니다. 결과 난수는 합의에 도달한 후 결정되지만 참가자 중 XNUMX/XNUMX가 공개 키로 암호화된 부분을 해독할 때까지는 누구에게도 알려지지 않습니다. 따라서 난수는 이를 재구성하기에 충분한 정보가 게시되기 전에 결정됩니다.

(1) 단계에서 참가자 중 한 명이 일부 문자열에 대한 올바른 삭제 코드가 아닌 인코딩된 공유를 다른 참가자에게 보낸 경우 어떻게 됩니까? 추가 변경 없이는 다른 참가자가 문자열을 전혀 복구할 수 없거나 다른 문자열을 복구하게 되어 다른 참가자가 다른 난수를 받게 됩니다. 이를 방지하려면 다음을 수행할 수 있습니다. 각 참가자는 인코딩된 공유 외에도 다음을 계산합니다. 메르클라 트리 그러한 모든 공유를 전송하고 각 참가자에게 인코딩된 공유 자체와 머클 트리의 루트, 그리고 해당 공유가 머클 트리에 포함되었다는 증거를 보냅니다. (2) 단계의 합의에서 참가자들은 세트 세트에 동의할 뿐만 아니라 해당 트리의 특정 루트 세트에 동의합니다(일부 참가자가 프로토콜에서 벗어나 다른 참가자에게 다른 머클 트리 루트를 보낸 경우, 그리고 합의 중에 그러한 두 개의 루트가 표시되며 그의 행은 결과 세트에 포함되지 않습니다. 합의의 결과로 우리는 67개의 인코딩된 라인과 머클 트리의 해당 루트를 가지게 되어 최소 67명의 참가자(해당 라인을 제안한 참가자와 반드시 동일할 필요는 없음)가 있게 되며, 67개의 라인 각각에 대해 삭제 코드 공유가 포함된 메시지와 해당 트리에서 해당 공유가 사라졌다는 증거.

단계 (4)에서 참가자가 특정 문자열에 대한 67비트를 해독하고 그로부터 원래 문자열을 재구성하려고 시도하면 다음 옵션 중 하나가 가능합니다.

1. 문자열이 복원되고 다시 삭제 인코딩되어 로컬로 계산된 공유에 대해 Merkle 트리가 계산되면 루트는 합의에 도달한 것과 일치합니다.

2. 행이 복원되었지만 로컬로 계산된 루트가 합의에 도달한 루트와 일치하지 않습니다.

3. 행이 복원되지 않습니다.

위의 적어도 한 명의 참가자에게 옵션 (1)이 발생하면 옵션 (1)이 모든 참가자에게 발생하고 그 반대의 경우 옵션 (2) 또는 (3)이 적어도 한 명의 참가자에게 발생하면 다음을 보여주기 쉽습니다. 모든 참가자에게 옵션 (2) 또는 (3)이 발생합니다. 따라서 세트의 각 행에 대해 모든 참가자가 성공적으로 복구하거나 모든 참가자가 복구에 실패합니다. 결과 난수는 참가자가 복구할 수 있었던 행만 XOR한 것입니다.

임계값 서명

무작위성에 대한 또 다른 접근 방식은 BLS 임계값 서명을 사용하는 것입니다. 임계값 서명을 기반으로 하는 난수 생성기는 위에서 설명한 삭제 코드 기반 알고리즘과 정확히 동일한 보장을 제공하지만 생성된 각 숫자에 대해 네트워크를 통해 전송되는 메시지의 점근적 수는 상당히 적습니다.

BLS 서명은 여러 참가자가 메시지에 대해 하나의 공통 서명을 만들 수 있도록 하는 디자인입니다. 이러한 서명은 여러 서명을 전송할 필요가 없으므로 공간과 대역폭을 절약하는 데 자주 사용됩니다. 

난수 생성 외에도 블록체인 프로토콜의 BLS 서명에 대한 일반적인 응용 프로그램은 BFT 프로토콜의 블록 서명입니다. 100명의 참가자가 블록을 생성하고 그 중 67명이 서명하면 블록이 최종적으로 간주된다고 가정해 보겠습니다. 그들은 모두 BLS 서명의 일부를 제출하고 일부 합의 알고리즘을 사용하여 그 중 67개에 동의한 다음 이를 하나의 BLS 서명으로 병합할 수 있습니다. 67개(또는 그 이상)의 부분을 사용하여 최종 서명을 만들 수 있으며, 이는 어떤 67개의 서명이 결합되었는지에 따라 달라질 수 있으므로 달라질 수 있습니다. 67명의 참가자가 서로 다른 선택을 하면 다른 서명이 생성되지만 이러한 서명은 유효합니다. 블록에 대한 서명. 그러면 나머지 참가자는 네트워크를 통해 67개가 아닌 블록당 하나의 서명만 수신하고 확인하면 되므로 네트워크 부하가 크게 줄어듭니다.

참가자가 사용하는 개인 키가 특정 방식으로 생성되면 어떤 67개의 서명(또는 그 이상, 이하)이 집계되더라도 결과 서명은 동일하다는 것이 밝혀졌습니다. 이는 임의성의 소스로 사용될 수 있습니다. 참가자는 먼저 서명할 일부 메시지에 동의합니다(이는 RANDAO의 출력일 수도 있고 마지막 블록의 해시일 수도 있지만 매번 변경되는 한 실제로는 중요하지 않습니다). 일관성이 있음) 이에 대한 BLS 서명을 생성합니다. 생성 결과는 67명의 참가자가 자신의 부품을 제공할 때까지 예측할 수 없으며, 그 이후의 출력은 이미 미리 결정되어 있어 참가자의 행동에 따라 달라질 수 없습니다.

무작위성에 대한 이러한 접근 방식은 온라인 참가자 중 최소 ⅔가 둘 다 프로토콜을 따르는 한 실행 가능하며, 참가자 중 최소 ⅓이 프로토콜을 따르는 한 편견이 없고 예측할 수 없습니다. 참가자의 ⅓ 이상 XNUMX/XNUMX 미만을 제어하는 ​​공격자는 프로토콜을 중지할 수 있지만 프로토콜의 출력을 예측하거나 영향을 미칠 수는 없다는 점에 유의하는 것이 중요합니다.

임계값 서명 자체는 매우 흥미로운 주제입니다. 기사의 두 번째 부분에서는 작동 방식과 임계값 서명을 난수 생성기로 사용할 수 있도록 참가자 키를 생성하는 것이 정확히 얼마나 필요한지 자세히 분석합니다.

결론적으로

이 기사는 기술 블로그 기사 시리즈 중 첫 번째 기사입니다. NEAR. NEAR는 최종 사용자의 개발 용이성과 사용 용이성에 중점을 두고 분산형 애플리케이션을 개발하기 위한 블록체인 프로토콜 및 플랫폼입니다.

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

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

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

곧!겠습니다!

출처 : habr.com