NEAR: 블록체인 프로토콜의 무작위성
Last updated
Last updated
우리는 오늘 NEAR 프로토콜에서 사용되는 무작위 비콘을 설명하는 짧은 논문을 발표했습니다. 함께 제공되는 이 블로그 게시물에서 무작위성이 왜 중요한지, 왜 어려운지, 다른 프로토콜에서 어떻게 처리되는지 논의합니다.
NEAR를 포함한 많은 최신 블록체인 프로토콜은 프로토콜에서 특정 작업을 수행하는 참가자를 선택하기 위해 무작위 소스에 의존합니다. 악의적인 행위자가 이 무작위성 소스에 영향을 줄 수 있는 경우 선택될 가능성이 높아지고 프로토콜의 보안이 잠재적으로 손상될 수 있습니다.
분산 무작위성은 블록체인에 구축된 많은 분산 애플리케이션의 핵심 구성 요소이기도 합니다. 예를 들어 참가자가 배팅을 수락하고 이중 금액의 49%를 지불하고 51%가 아닌 스마트 계약은 편견 없는 난수를 얻을 수 있다고 가정합니다. 악의적인 행위자가 nonce에 영향을 미치거나 예측할 수 있는 경우 스마트 계약에서 지불을 받을 가능성을 높이고 고갈시킬 수 있습니다.
분산 랜덤 알고리즘을 설계할 때 세 가지 속성을 갖기를 원합니다.
편견이 없어야 합니다. 즉, 참가자는 어떤 식으로든 랜더마이저의 결과에 영향을 줄 수 없습니다.
예측할 수 없어야 합니다. 다시 말해, 어떤 액터도 생성되기 전에 생성될 숫자(또는 속성에 대한 이유)를 예측할 수 없습니다.
프로토콜은 일정 비율의 참가자가 오프라인 상태가 되거나 프로토콜을 의도적으로 중지하려는 시도를 허용해야 합니다.
이 기사에서는 분산 랜덤 비콘의 기본 사항을 다루고 간단한 방법이 작동하지 않는 이유에 대해 설명합니다. 마지막으로 DFinity, Ethereum Serenity, NEAR에서 사용하는 방법을 소개하고 각각의 장단점에 대해 논의합니다.
RANDAO는 매우 간단하고 따라서 매우 일반적인 임의성 방법입니다. 일반적인 아이디어는 네트워크의 참가자 모두가 먼저 의사 난수를 개인적으로 선택하고 이 개인적으로 선택한 숫자에 대한 약정을 제출하고 일부 합의 알고리즘을 사용하여 약속 집합에 동의한 다음 모두 선택한 숫자 A를 공개한다는 것입니다. 표시된 숫자에 대한 합의에 도달하고 표시된 숫자의 XOR이 합의의 출력으로 사용됩니다.
예측할 수 없으며 기본 합의 프로토콜과 동일한 활성을 갖지만 편향이 있습니다. 특히, 다른 사람들이 자신의 숫자를 공개하기 시작하면 악의적인 행위자가 네트워크를 관찰하고 지금까지 관찰된 숫자의 XOR을 기반으로 숫자를 공개할지 여부를 선택할 수 있습니다. 이를 통해 한 명의 악의적인 행위자가 출력에 약간의 영향을 미치는 반면, 여러 명의 행위자를 제어하는 악의적인 행위자는 그들이 제어하는 행위자의 수만큼 영향력을 행사할 수 있습니다.
RANDAO를 편향되지 않게 만드는 한 가지 방법은 출력을 XOR뿐만 아니라 숫자를 표시하기 위해 할당된 것보다 더 많은 실행 시간으로 만드는 것입니다. 최종 출력의 계산 시간이 공개 단계보다 길면 악의적인 행위자가 자신의 공개 또는 공개하지 않는 효과를 예측할 수 없으므로 결과에 영향을 미칠 수 없습니다.
우리는 난수를 생성하는 액터에 대해 난수를 계산하는 함수가 오랜 시간이 걸리기를 원하지만 난수 사용자가 동일한 값비싼 기능을 다시 수행하지 않아도 되기를 바랍니다. 따라서 그들은 값비싼 계산을 다시 수행하지 않고 난수가 올바르게 생성되었는지 어떻게든 신속하게 검증해야 합니다.
이러한 긴 계산 시간, 빠른 계산 검증 속도, 각 입력에 대한 고유한 출력을 VDF(Verifiable Delay Function)라고 하며 설계가 매우 복잡합니다. 최근 여러 가지 돌파구가 있었는데, 이 하나와 하나, 이더리움은 현재 확률적 신호로 VDF와 함께 RANDAO를 사용할 계획입니다. 이 접근 방식에서 예측할 수 없고 편견이 없다는 것 외에도 두 명의 참가자만 온라인 상태인 경우에도 활성화된다는 추가 이점이 있습니다(기본 합의 프로토콜이 소수의 참가자와 함께 활성화되어 있다고 가정).
이 접근 방식의 가장 큰 문제는 매우 고가의 전용 하드웨어를 사용하는 행위자라도 공개 단계가 끝나기 전에 VDF를 계산할 수 없고 이상적으로는 10배와 같이 의미 있는 안전 여유가 있는 방식으로 VDF를 구성해야 한다는 것입니다. 아래 그래프는 RANDAO 약속을 밝히기 위해 할당된 시간보다 빠르게 VDF를 실행할 수 있도록 하는 특수 ASIC을 사용하는 행위자의 공격을 보여줍니다. 이러한 참가자는 여전히 자신의 몫이 있거나 없는 최종 출력을 계산하고 해당 출력을 기반으로 표시할지 여부를 선택할 수 있습니다.
전용 ASIC 위에 연결된 VDF 제품군의 경우 기존 하드웨어보다 100배 이상 빠를 수 있습니다. 따라서 공개 단계가 10초 지속되는 경우 이러한 ASIC에서 계산된 VDF는 10x 안전 마진을 얻기 위해 100초 이상 소요되어야 하므로 레거시 하드웨어에서 계산된 동일한 VDF는 100 x 100초 = ~3시간이 걸립니다.
이더리움 재단이 이 문제를 해결하려는 방식은 자체 ASIC을 설계하여 무료로 공개하는 것입니다. 이러한 일이 발생하면 다른 모든 프로토콜이 이 기술을 활용할 수 있지만 그때까지는 자체 ASIC 설계에 투자할 수 없는 프로토콜에 대해 RANDAO+VDF 접근 방식이 실현 가능하지 않습니다.
Dfinity가 개척한 무작위성에 대한 또 다른 접근 방식은 소위 임계값 BLS 서명을 사용하는 것입니다. (흥미롭게도 Dfinity는 BLS의 L 캐릭터인 Ben Lynn을 고용했습니다.)
BLS 서명은 여러 당사자가 메시지에 단일 서명을 만들 수 있도록 하는 구조로, 여러 서명을 보낼 필요가 없어 공간과 대역폭을 절약하는 데 자주 사용됩니다. 블록체인에서 BLS 서명의 일반적인 용도는 BFT 프로토콜에서 블록에 서명하는 것입니다. 100명의 참가자가 블록을 만들고 그 중 67명이 서명하면 블록이 최종 블록으로 간주된다고 가정합니다. 그들은 모두 자신의 부분 BLS 서명을 제출한 다음 일부 합의 알고리즘을 사용하여 67개에 동의한 다음 단일 BLS 서명으로 집계할 수 있습니다. 67개 부분 중 어느 것이든 누적 서명을 만드는 데 사용할 수 있지만 결과 서명은 집계된 67개 서명에 따라 다릅니다.
참가자가 사용하는 개인 키가 특정 방식으로 생성되면 결과 다중 서명은 67개(또는 그 이상, 그 이하)의 서명이 집계되더라도 동일합니다. 이것은 무작위성의 원천으로 사용될 수 있습니다. 참가자는 먼저 서명할 일부 메시지에 동의합니다(매번 다르고 동의하는 한 RANDAO의 출력 또는 마지막 블록의 해시일 수 있음). 다중 서명이 생성됩니다. 67명의 참가자가 부품을 제공할 때까지 출력은 예측할 수 없었지만 첫 번째 부품이 제공되기 전에도 출력은 미리 결정되었으며 참가자의 영향을 받지 않았습니다.
이 무작위성 방법은 완전히 편향되지 않고 예측할 수 없으며 참가자의 2/3가 온라인 상태인 한 지속됩니다(임계값에 대해 구성 가능). ⅓ 오프라인 또는 잘못된 행동을 하는 참가자가 알고리즘을 중지할 수 있지만, 출력에 영향을 미치려면 참가자의 ⅔ 이상이 협력해야 합니다.
그러나 주의 사항이 있습니다. 위에서 이 방식에 대한 개인 키가 특정 방식으로 생성되어야 한다고 언급했습니다. 분산 키 생성(Distributed Key Generation) 또는 줄여서 DKG라고 하는 키 생성 프로세스는 복잡하고 활발한 연구 영역입니다. 최근 강연에서 Dfinity는 단계 중 하나로 매우 복잡하고 오랜 시간 동안 검증되지 않은 암호화 구조인 zk-SNARK를 포함하는 매우 정교한 접근 방식을 제시했습니다. 일반적으로 문턱 시그니처에 대한 연구, 특히 DKG에 대한 연구는 아직 실무에 쉽게 적용할 수 있는 상태가 아닙니다.
NEAR 방법은 RandShare라는 다른 알고리즘의 영향을 받습니다. RandShare는 참여자의 최대 1/3이 악의적임을 허용할 수 있는 편향되지 않고 예측할 수 없는 프로토콜입니다. 상대적으로 느리고 링크된 논문에서도 RandHound 및 RandHerd라는 두 가지 가속 방법을 설명하지만 RandShare 자체와 달리 RandHound와 RandHerd는 상대적으로 복잡하며 프로토콜이 매우 단순하기를 원합니다.
많은 수의 메시지 교환(참가자가 O(n^3)개의 메시지를 함께 교환함)을 제외하고 RandShare의 일반적인 문제는 ⅓가 실제로 의미 있는 활성 임계값이지만 영향을 미칠 수 있는 능력이 낮다는 사실입니다. 산출. 몇 가지 이유가 있습니다.
출력에 영향을 주는 이점이 무작위성을 중지하는 이점보다 훨씬 클 수 있습니다.
참가자가 RandShare 참가자의 1/3 이상을 제어하고 이를 사용하여 출력에 영향을 미치는 경우 흔적이 남지 않습니다. 따라서 악의적인 행위자는 탐지되지 않고 이를 수행할 수 있습니다. 합의 지연은 자연스럽게 보입니다.
누군가가 해시 파워/지분의 1/3을 제어하는 것은 불가능하지 않으며, 위의 (1)과 (2)를 고려할 때 그러한 제어를 가진 누군가가 무작위성을 방지하려고 시도할 가능성은 없지만 영향을 미칠 수 있고 시도할 수 있습니다. 그것.
NEAR 방법은 우리가 최근에 발표한 논문에 설명되어 있습니다. 편견이 없고 예측할 수 없으며 악의적인 행위자의 활동을 최대 1/3까지 허용할 수 있습니다. 즉, 누군가가 참가자의 1/3 이상을 제어하는 경우 프로토콜을 중지할 수 있습니다.
그러나 RandShare와 달리 출력에 영향을 미치기 전에 최대 ⅔의 악의적인 행위자를 허용할 수 있습니다. 이것은 실제 적용을 위한 훨씬 더 나은 임계값입니다.
프로토콜의 핵심 아이디어는 다음과 같습니다(단순화를 위해 정확히 100명의 참가자를 가정).
각 참가자는 출력에서 자신의 부분을 가져와 67개 부분으로 나누고 100개 공유를 얻기 위해 지우기 코드를 작성하여 67개가 출력을 재구성하기에 충분하도록 100개 공유 각각을 참가자에게 할당하고 해당 참가자의 공개를 사용합니다. 열쇠. 그런 다음 인코딩된 모든 공유를 공유합니다.
참가자는 67명의 참가자로부터 이러한 인코딩 세트에 동의하기 위해 일부 합의(예: Tendermint)를 사용합니다.
일단 합의에 도달하면, 각 참가자는 이러한 방식으로 발행된 67개 세트의 인코딩된 공유를 얻고, 공개 키로 인코딩하고, 모든 공유를 디코딩하고 모든 공유를 한 번에 공개합니다. 디코딩된 공유.
적어도 67명의 참가자가 (3) 단계를 완료하면 합의된 모든 세트를 완전히 디코딩하고 재구성할 수 있으며 최종 숫자는 (1)에서 참가자가 제안한 초기 부분의 XOR로 얻을 수 있습니다.
프로토콜이 편향되지 않고 예측할 수 없는 이유에 대한 아이디어는 RandShare 및 임계값 서명의 아이디어와 유사합니다. 최종 출력은 합의 후에 결정되지만 참여자의 ⅔가 암호를 해독할 때까지 아무도 공유를 해독할 수 없습니다. 그들의 공개 키로 암호화된 공유.
모든 코너 케이스와 가능한 악의적인 행동을 처리하면 조금 더 복잡해집니다(예: 참가자는 누군가가 (1)단계에서 잘못된 삭제 코드를 생성한 경우를 처리해야 함). 그러나 일반적으로 전체 프로토콜은 예를 들어 다음과 같이 매우 간단합니다. 모든 증명, 해당 암호화 기본 형식 및 이를 설명하는 참조 전체 논문은 7페이지에 불과합니다. 알고리즘에 대한 보다 공식적인 설명이나 해당 알고리즘의 활동 및 영향에 대한 저항에 대한 분석을 읽고 싶다면 반드시 확인하십시오.
특정 시대의 블록 생산자가 특정 샤드에 대한 모든 트랜잭션을 포함하는 이른바 블록을 생성하고 해당 블록의 삭제 코딩된 버전을 다른 사람에게 배포하는 NEAR의 기존 인프라에서 삭제 코딩을 활용하는 유사한 아이디어가 이미 사용되었습니다. 블록 생산자는 데이터 가용성을 보장하기 위해 머클 증명을 제공합니다.
