공개 임의성 많은 실제 보안 프로토콜의 필수 구성 요소입니다. 도박 및 멀티플레이어 게임과 같은 일부 응용 프로그램에서는 무작위성이 재미를 더합니다. 다른 응용 프로그램에서 무작위성은 영주권에서 사건에 대한 순회 법원 판사 배정, 스포츠 토너먼트 시드 배정에 이르기까지 나눌 수 없는 자원을 할당하는 공정한 방법을 제공합니다. 할당하는 데에도 사용됩니다. 부정 세금 감사 또는 공항의 XNUMX차 보안 검색과 같은 자원.

전통적으로 우리는 이러한 프로토콜에 대한 무작위성을 생성하기 위해 신뢰할 수 있는 기관에 의존했지만 web3 세계에서는 더 잘해야 합니다. 이 게시물에서는 다음을 통해 공개적으로 검증 가능한 임의성을 구축하는 분산된 임의성 비콘 그런 다음 일부 온체인 응용 프로그램에 대해 논의합니다. (곧 나올 XNUMX부에서는 특히 리더 선출에 초점을 맞추면서 대안적 리더 선출 접근 방식에 대한 평가를 제공할 것입니다.) 

원하는 속성

난수를 생성하는 것은 악명 높은 미묘한 작업입니다. 예를 들어 많은 암호화 키가 유출되었습니다. 결함이 있는 난수 생성기에 의존 (Cloudflare의 벽은 용암 램프 창의적인 완화 수단으로 작용했을 것입니다). 그건 그냥 사적인 무작위성그러나 한 당사자만 이를 생성하고 사용해야 하는 경우.

대조적으로 공개 무작위성은 다자간 프로세스이므로 어려움이 상당히 가중됩니다. 공개 임의성을 생성하는 좋은 프로토콜은 다음과 같은 보안 속성을 갖습니다.

• 편견 없는: 어떤 공격자 또는 공격자 연합도 출력을 편향시킬 수 없어야 합니다. 
• 신뢰할 수있는: 어떤 공격자도 프로토콜이 출력을 생성하는 것을 막을 수 없어야 합니다.
• 증명할 수 있는: 누구나 쉽게 프로토콜 출력을 확인할 수 있으며 다른 모든 사람과 동일한 출력을 볼 수 있습니다.
• 예측할 수없는: 프로토콜이 시간에 출력을 생성하는 경우 T₁, 어느 누구도 얼마 전에 출력에 대해 아무 것도 예측할 수 없어야 합니다. T₀<T₁, 이상적으로 T₀ 매우 가까이 T₁.

예측할 수 없는 프로토콜은 편향되지 않아야 하기 때문에 편향성(Unbiasability)은 예측 불가능성보다 약한 속성입니다. 컴퓨터 과학자들은 편향성이 없다고 말할 것입니다. 감소 편향될 수 있다면 예측할 수 있기 때문입니다. 그러나 때로는 서로 다른 가정에 의존할 수 있기 때문에 개별적으로 추론하고 싶을 것입니다. 예를 들어, 부정직한 대다수가 결과를 예측할 수 있지만 편향되지는 않을 수 있습니다.

이러한 속성 외에도 프로토콜은 실행하고 많은 수의 임의 비트를 생성하는 데 효율적이어야 합니다. (실제로 응용 프로그램이 128개의 임의 비트를 생성하는 것으로 충분하며, 이를 사용하여 의사 난수 생성기[PNRG]를 시드하여 필요에 따라 더 많은 비트를 출력합니다. 추첨 또는 자원 할당과 같은 응용 프로그램.) 프로토콜은 또한 통신 및 계산 비용 측면에서 이상적으로 효율적이어야 합니다.

다른 프로토콜은 다른 조건에서 이러한 속성을 달성할 수 있습니다. 예를 들어, 일부 프로토콜은 연합에 의해 편향되지 않을 수 있습니다. f₁ 악의적인 노드 및 연합에 의해 예측할 수 없는 f₂<f₁ 악성 노드. 편견의 정도도 다릅니다. 예를 들어, 일부 프로토콜에서 참가자는 출력을 "XNUMX비트"로 바이어스할 수 있습니다. 즉, 두 가지 가능한 출력 중 하나를 선택할 수 있습니다. 다른 공격을 통해 출력을 완전히 수정할 수 있습니다. 그러나 일반적으로 우리는 편견(또는 예측 가능성)을 전혀 용인하고 싶지 않습니다.

암호학적 이상: Randomness 비콘

암호 작성자는 종종 문제에 대한 이상적인 솔루션을 생각하는 것으로 시작합니다. 공개 무작위의 경우, 임의성 비콘 필요한 모든 보안 요구 사항을 충족하는 임의의 출력을 정기적으로 생성하는 이상적인 서비스입니다.

임의의 오라클이나 일반 그룹 모델과 같은 다른 암호화 추상화와 유사한 이상적인 임의성 비콘은 현실 세계에 존재하지 않습니다. 그러나 이는 공공의 무작위성에 의존하는 프로토콜을 추론하는 데 유용한 모델이자 노력해야 할 유용한 목표입니다. 

이상적인 임의성 비콘의 몇 가지 근사치를 고려할 수 있습니다.

• 중앙 집중식 비콘: 좋은 무작위성을 생성하는 가장 쉬운 방법은 다음과 같은 서비스를 제공하는 중앙 집중식 제XNUMX자를 통하는 것입니다. NIST 임의성 비콘 or random.org, 대기 소음에서 임의성을 생성하고 도박에 사용하도록 인증되었습니다. 제XNUMX자에 대한 이러한 의존은 탈중앙화 철학을 완전히 훼손합니다. 실제로 위의 예에서 우리는 관련 조직이 암호화 증거 없이 무작위성을 올바르게 생성하고 있음을 신뢰해야 합니다.
• 물리적 무작위성 표시: 많은 전통적인 복권은 예를 들어 누군가가 다른 숫자가 적힌 탁구공 용기에 손을 뻗는 것을 포함할 수 있는 공개 전시에 의존합니다. 불행히도 이것들은 종종 쉽게 조작할 수 있습니다. 예를 들어, 특정 공은 냉동실에 넣을 수 있습니다. 과 선택자는 차가운 것을 선택하도록 말할 수 있습니다..
• 내츄럴 비콘: 일반적인 아이디어는 날씨 또는 우주 배경 복사와 같은 임의의 자연 현상을 표지로 사용하는 것입니다. 불행히도 제안된 모든 출처는 강력한 합의를 제공하지 않습니다. 다른 관찰자는 약간 다른 값을 보게 될 것이며, 이는 중앙 집중식 비콘의 모든 단점과 함께 공식 측정을 수행하기 위해 신뢰할 수 있는 당사자를 다시 도입해야 합니다.
• 반 중앙 집중식 비콘: 더 나은 접근 방식은 다음에서 임의성을 얻는 것입니다. 비트코인 블록 헤더 직접 또는 주식의 종가, 공개적으로 확인하는 것이 더 쉽고 한 당사자가 완전히 제어하기가 더 어렵습니다. 그러나 미묘한 공격은 여전히 ​​​​둘 모두에 존재합니다. 작업 증명 블록체인 무작위성 과 주가의 무작위성. 예를 들어 블록체인 헤더를 사용하여 채굴자는 헤더가 원하지 않는 신호 값을 생성하는 블록을 보류하도록 선택할 수 있습니다. 또는 선호하는 신호 출력을 기반으로 두 개의 충돌 블록이 발견되면 관계를 끊도록 선택할 수 있습니다.

분산된 임의성 비콘(DRB)

중앙 집중식 비콘의 문제에 대한 자연스러운 접근 방식은 공개 무작위성을 생성하기 위한 분산형 암호화 프로토콜을 설계하는 것입니다. 이 문제는 분산된 합의 프로토콜을 설계하는 것과 다소 비슷하지만 더 어렵습니다. 모든 참가자가 출력(임의성)에 동의해야 할 뿐만 아니라 프로토콜의 악의적인 참가자가 출력을 편향하거나 예측하는 것이 불가능해야 합니다.

임의성 비콘을 시뮬레이션하도록 설계된 프로토콜을 분산 임의성 비콘(DRB)이라고 합니다. (다른 이름에는 "분산 동전 던지기"가 포함됩니다.) 이 문제는 수십 년 동안 연구되어 왔습니다. 1980년대에 입증된 유명한 불가능 결과, 하지만 블록체인 시대에 다시 관심이 쏠리고 있습니다. DRB는 온체인 무작위성을 제공하는 데 사용될 수 있으며, 이는 공정하고 안전하며 투명한 온체인 애플리케이션의 핵심 요소입니다.

고전적인 접근 방식: 커밋-공개 프로토콜

낙관적 인 경우 DRB에는 매우 간단한 1 라운드 프로토콜로 충분합니다. XNUMX라운드에서는 각 참가자가 i 임의의 값을 생성 r_i 암호화 약정을 게시합니다. c_i=저지르다(r_i). 이 애플리케이션에서 확약은 단순히 SHA-256과 같은 해시 함수일 수 있습니다. 각 참가자의 약정이 게시된 후에는 r_i, 그러나 약속은 다른 참가자의 기여에 대한 정보를 공개하지 않습니다. 2라운드에서 모든 참가자는 r_i. 그런 다음 모든 임의 값은 예를 들어 XOR 또는 (바람직하게는) 연결을 해싱하여 결합됩니다.

이 프로토콜은 간단하며 참가자 중 한 명이라도 자신을 선택하는 한 임의의 비컨 출력을 생성합니다. r_i 무작위로. 불행히도 이것은 고전적인 결함을 가지고 있습니다. 참가자 중 한 명을 제외하고 모두가 무작위 값을 공개했을 때 마지막 참가자는 추정 비콘 출력을 계산할 수 있습니다. 그들이 마음에 들지 않으면 가치 공개를 거부하고 프로토콜을 중단할 수 있습니다. 결함이 있는 참가자의 기여를 무시해도 문제가 해결되지 않습니다. 그 이유는 공격자가 두 개의 비콘 출력(하나는 기여로 계산되고 다른 하나는 포함하지 않음) 중에서 선택할 수 있기 때문입니다.

블록체인은 이 문제에 대한 자연스러운 해결책을 제공합니다. 각 참가자는 임의의 기여금을 공개하지 않을 경우 압수되는 일부 자금을 에스크로에 넣어야 할 수 있습니다. 이것이 바로 클래식이 취한 접근 방식이었습니다. 란다오 이더리움의 비콘. 이 접근 방식의 단점은 출력이 여전히 편향될 수 있다는 것입니다. 이는 에스크로에 있는 돈이 비콘의 결과에 따라 달라지는 금액보다 적은 경우 공격자에게 재정적으로 가치가 있을 수 있습니다. 편향 공격에 대한 더 나은 보안을 위해서는 더 많은 코인을 에스크로에 넣어야 합니다.

커밋-공개-복구 프로토콜

모든 당사자가 무작위 기여를 공개하도록 강요하는 대신 일부 프로토콜에는 복구 메커니즘이 포함되어 소수의 참가자가 탈락하더라도 나머지는 프로토콜을 완료할 수 있습니다. 프로토콜이 두 경우 모두 동일한 결과를 생성하는 것이 중요하므로 당사자가 탈락 여부를 선택하여 결과를 편향시킬 수 없습니다.

이를 달성하기 위한 한 가지 접근 방식은 각 참가자가 다른 사람들에게 비밀을 공유하도록 하여 대부분이 예를 들어 다음을 사용하여 암호를 재구성할 수 있도록 하는 것입니다. 샤미르의 비밀 공유. 그러나 중요한 속성은 다른 사람들이 커밋된 비밀이 적절하게 공유되었는지 확인할 수 있다는 것입니다. 따라서 공개적으로 검증 가능한 비밀 공유(PVSS)라고 하는 더 강력한 기본 요소를 사용해야 합니다.

몇 가지 다른 복구 메커니즘이 가능하지만 모두 동일한 제한이 있습니다. 만일 거기에 N 우리는 복원력을 원합니다. f 노드가 탈락하면 다음의 모든 그룹이 엔에프 참가자는 최종 결과를 계산할 수 있습니다. 그러나 그것은 또한 악의적 인 연합을 의미합니다. 엔에프 참가자는 복구 메커니즘을 개인적으로 시뮬레이션하여 결과를 미리 예측할 수 있습니다. 이는 프로토콜의 첫 번째 라운드 중에도 발생할 수 있으며, 이 기간 동안 이러한 연합은 자체 무작위 선택을 수정하고 결과를 편향시킬 수 있습니다. 

다시 말해서, 이것은 모든 연합을 의미합니다. 엔에프 노드에는 정직한 노드가 하나 이상 포함되어야 합니다. 간단한 대수학으로, 엔 > 에프그래서 f < N/2, 그리고 이러한 프로토콜은 본질적으로 정직한 다수를 요구합니다. 이것은 commit-reveal의 원래 보안 모델과 상당한 차이가 있습니다. f<N (최소 한 명의 정직한 참가자).

이러한 프로토콜은 각 프로토콜 실행에서 모든 노드 간에 추가 PVSS 정보를 공유하기 위해 상당한 통신 비용이 필요합니다. 연구 커뮤니티는 지난 몇 년 동안 다음을 포함한 연구 제안과 함께 이 문제에 대해 상당한 작업을 수행했습니다. 랜드쉐어, 긁다, 초랜드, 목초및 신천옹, 그러나 아무도 실제 배포를 본 적이 없는 것 같습니다.

검증 가능한 임의 기능 기반 프로토콜

그룹임을 깨닫고 엔에프 참가자는 위의 프로토콜에서 임의의 비컨 값을 계산할 수 있어 다소 간단한 접근 방식으로 이어집니다. N 당사자가 이를 사용하여 평가하도록 하십시오. 검증 가능한 랜덤 함수 (VRF). 비밀 키는 다음을 통해 공유됩니다. t-밖에서-N 임계값 체계, 그래서 어떤 t 참가자는 VRF를 계산할 수 있지만 소규모 연합은 할 수 없습니다. 을 위한 t=엔에프, 이것은 동일한 복원력을 제공합니다. f 위에서 논의한 커밋-공개-복구 프로토콜과 같은 악성 노드.

DFINITY 이 접근 방식을 개척했습니다 임계값 BLS 서명(VRF로 기능)을 사용하는 합의 프로토콜의 일부로. 독립 실행형 드 랜드 임의성 비콘은 본질적으로 동일한 접근 방식을 사용하며, 각 라운드에서 일련의 참가자 임계값(BLS 서명)이 카운터에 서명합니다. 그만큼 엔트로피 리그 30개의 참여 노드(16년 2022월 기준)를 사용하여 XNUMX초마다 무작위성을 생성하는 드랜드의 오픈 소스 인스턴스로, 기업과 대학 연구 그룹이 혼합되어 운영됩니다. 

이러한 접근 방식의 단점은 노드가 결합하거나 떠날 때 키를 재구성하는 것과 같이 임계값 키를 초기화하는 것이 상대적으로 복잡하다는 것입니다. 그러나 일반적인 경우에는 프로토콜이 매우 효율적입니다. 

위에서 설명한 것처럼 단순히 카운터 값에 서명하는 것은 라운드당 새로운 임의성을 추가하지 않으므로 충분한 수의 참가자 키가 손상되면 향후 모든 라운드에서 프로토콜을 예측할 수 있습니다.

체인 링크 VRF 결합 이 접근 방식(사용 NSEC5 VRF) 임의성을 요청하는 당사자가 지정한 임의성의 외부 소스(일반적으로 실제로는 최근의 블록체인 헤더)를 사용합니다. 그런 다음 이 데이터는 한 당사자에 의해 실행되거나 그룹에 임계값으로 지정된 VRF를 통해 제공됩니다.

에테 리엄 비컨 사슬 현재 BLS 기반 VRF를 사용합니다. 각 라운드의 제안자는 VRF 값을 믹스에 추가합니다. 이것은 커밋-공개 패러다임(장기 BLS 공개 키가 한 번 등록되었다고 가정)과 비교하여 통신 라운드를 절약하지만, 이 디자인은 출력을 보류하여 비컨의 출력을 편향시킬 가능성을 포함하여 커밋-공개 접근 방식의 몇 가지 주의 사항을 상속합니다. .

검증 가능한 지연 기능 기반 프로토콜

마지막으로 유망한 새로운 방향은 시간 기반 암호화, 특히 검증 가능한 지연 기능을 사용하는 것입니다(VDF). 이 접근 방식은 복원력과 함께 우수한 통신 효율성과 견고성을 제공할 것을 약속합니다. N-1 악성 노드. 

원래 커밋-공개 프로토콜로 돌아가서 기존 커밋을 다음으로 대체할 수 있습니다. 시간 약속 참가자가 무작위 기여를 공개하기를 거부하는 문제를 제거합니다. 시간 제한 커밋은 원래 커미터 또는 느린 함수(기본적으로 VDF)를 계산하려는 사람이 효율적으로 열 수 있습니다. 따라서 참가자가 커밋 공개 프로토콜에서 탈퇴하더라도 다른 참가자가 해당 커밋을 열 수 있습니다. 커밋을 여는 최소 시간은 프로토콜의 첫 번째 라운드(커밋 단계)에서 수행할 수 없을 만큼 충분히 길어야 합니다. .

최신 VDF를 사용하면 훨씬 더 우아한 원라운드 프로토콜이 가능합니다. 즉, 약속을 완전히 삭제하십시오. 각 참가자는 단순히 자신의 무작위 기여를 게시할 수 있습니다. r_i, 그리고 최종 결과는 VDF를 통해 실행되는 각 참가자의 기여의 조합입니다. VDF 계산의 시간 지연으로 인해 아무도 최종 출력을 편향시키는 방식으로 약속을 선택할 수 없습니다. 이 접근법은 다음과 같이 제안되었습니다. 유니콘 Arjen Lenstra와 Benjamin Wesolowski가 2015년에 작성했으며 실제로 VDF 개발.

이 접근 방식은 몇 가지 실용적인 배포를 보았습니다. 치아 클래스 그룹에서 반복 제곱 VDF를 사용하여 합의 프로토콜의 일부로 이것의 버전을 구현합니다. 스타 케웨어 구현 개념 증명 VDF 기반 비콘 SNARK 기반 VDF 사용. 이더리움 또한 계획 사용 이 접근법, VDF를 계산하기 위한 전용 ASIC을 구축하여 합의 계층에서 무작위성을 생성합니다.

***

공개 무작위성은 많은 프로토콜의 필수 구성 요소이지만 여전히 높은 보안을 제공하는 표준 DRB가 부족합니다. 설계 공간이 넓고 위의 접근 방식의 많은 하이브리드 및 조합이 가능합니다. 예를 들어, VRF 기반 프로토콜을 VDF 기반 프로토콜과 결합하는 것이 가능합니다. 랜드러너. Ethereum의 Beacon Chain은 현재 VRF를 사용하지만 블록 보류 공격으로 인한 편향 가능성을 제거하기 위해 향후 VDF를 추가할 수 있습니다.

정직한 다수의 프로토콜이 허용되는 경우에도 미해결 질문입니다. 엔트로피 연맹과 같이 비교적 소규모의 검증된 참가자 그룹의 경우 정직한 다수결 가정이 합리적입니다. 반면에 정직한 참가자 한 명만 필요로 하는 프로토콜은 고유한 이점이 있습니다. 참가자가 많을수록 보안만 향상될 수 있습니다. 이는 이러한 프로토콜이 개방적이고 허가 없는 참여로 잠재적으로 배포될 수 있음을 의미합니다.

XNUMX부에서는 디자인 목표가 약간 다르고 결과적으로 더 많은 프로토콜과 접근 방식이 제안된 합의 프로토콜에서 무작위 리더 선출의 특정 적용에 대해 논의할 것입니다.

***

조셉 보노 16z 암호화의 연구 파트너입니다. 그의 연구는 응용 암호화 및 블록체인 보안에 중점을 둡니다. 그는 멜버른 대학, NYU, 스탠포드 및 프린스턴 대학에서 암호화폐 과정을 가르쳤고, 케임브리지 대학에서 컴퓨터 공학 박사 학위를, 스탠포드에서 학사/석사 학위를 받았습니다.

발레리아 니콜라엔코 16z 암호화의 연구 파트너입니다. 그녀의 연구는 암호화 및 블록체인 보안에 중점을 둡니다. 그녀는 또한 PoS 합의 프로토콜의 장거리 공격, 서명 체계, 양자 후 보안 및 다자간 계산과 같은 주제에 대해 작업했습니다. 그녀는 Dan Boneh 교수의 지도하에 스탠포드 대학에서 암호학 박사 학위를 취득했으며 핵심 연구 팀의 일원으로 Diem 블록체인에서 일했습니다.

***

에디터 : 팀 설리반

***

여기에 표현된 견해는 인용된 개별 AH Capital Management, LLC("a16z") 직원의 견해이며 16z 또는 그 계열사의 견해가 아닙니다. 여기에 포함된 특정 정보는 16z가 관리하는 펀드의 포트폴리오 회사를 포함하여 제16자 출처에서 얻은 것입니다. 신뢰할 수 있다고 여겨지는 출처에서 가져왔지만 16z는 그러한 정보를 독립적으로 검증하지 않았으며 정보의 지속적인 정확성이나 주어진 상황에 대한 적절성에 대해 어떠한 진술도 하지 않습니다. 또한 이 콘텐츠에는 타사 광고가 포함될 수 있습니다. XNUMXz는 그러한 광고를 검토하지 않았으며 여기에 포함된 광고 콘텐츠를 보증하지 않습니다.

이 콘텐츠는 정보 제공의 목적으로만 제공되며 법률, 비즈니스, 투자 또는 세금 관련 조언에 의존해서는 안 됩니다. 그러한 문제에 관해서는 자신의 고문과 상의해야 합니다. 증권 또는 디지털 자산에 대한 언급은 설명을 위한 것일 뿐이며 투자 추천이나 투자 자문 서비스 제공을 의미하지 않습니다. 또한, 이 콘텐츠는 투자자 또는 예비 투자자를 대상으로 하거나 사용하도록 의도되지 않았으며, 어떤 상황에서도 a16z가 관리하는 펀드에 투자하기로 결정할 때 의존할 수 없습니다. (16z 펀드에 대한 투자 제안은 사모 투자 각서, 청약 계약서 및 해당 펀드의 기타 관련 문서에 의해서만 이루어지며 전체 내용을 읽어야 합니다.) 언급되거나 언급된 모든 투자 또는 포트폴리오 회사 설명된 내용은 16z가 관리하는 차량에 대한 모든 투자를 대표하는 것은 아니며 투자가 수익성이 있거나 미래에 수행되는 다른 투자가 유사한 특성 또는 결과를 가질 것이라는 보장이 없습니다. Andreessen Horowitz가 관리하는 펀드의 투자 목록(발행자가 16z가 공개적으로 공개하도록 허가하지 않은 투자 및 공개적으로 거래되는 디지털 자산에 대한 미고지 투자 제외)은 https://a16z.com/investments에서 볼 수 있습니다. /.

내부에 제공된 차트와 그래프는 정보 제공의 목적으로만 사용되며 투자 결정을 내릴 때 의존해서는 안 됩니다. 과거의 성과는 미래의 결과를 나타내지 않습니다. 내용은 표시된 날짜 현재만 말합니다. 이 자료에 표현된 모든 예측, 추정, 예측, 목표, 전망 및/또는 의견은 예고 없이 변경될 수 있으며 다른 사람이 표현한 의견과 다르거나 반대될 수 있습니다. 추가 중요 정보는 https://a16z.com/disclosures를 참조하십시오.