무작위 비콘 및 기타 전략에서 리더 선출

블록체인 환경에서 리더 선출은 블록체인에 추가될 다음 블록을 결정할 참가자를 선택하는 것을 목표로 합니다. 일반적으로 유효성 검사기 세트에서 슬롯당 하나의 유효성 검사기가 선택되고 해당 슬롯의 새 블록으로 체인을 확장할 수 있는 권한을 얻습니다. (우리는 유효성 검사기가 정확한 시간을 유지하고 현재 슬롯 번호에 동의한다고 가정합니다.) 이 기사에서는 다음을 위한 전략을 살펴봅니다. 무작위 리더 선출 합의 프로토콜에서. (일반적인 무작위성에 대한 자세한 내용은 이전 기사를 참조하십시오. 공개 무작위성 및 무작위성 비콘어디로 우리는 공개적으로 검증 가능하고 예측할 수 없는 임의성을 생성하기 위한 독립 실행형 프로토콜을 조사했습니다.) 

리더 선출이 중요한 이유

정직하고 적극적인 리더를 선출하는 것은 체인의 건강한 성장을 위해 매우 중요합니다. 악의적인 유효성 검사기는 자신을 더 자주 리더로 만들기 위해 리더 선출 프로세스를 편향시킬 수 없어야 합니다. 그렇지 않으면 블록 생성이 트랜잭션을 검열하거나 블록체인을 완전히 중단할 수 있는 당사자의 손에 넘어갈 수 있습니다. 가장 긴 체인 스타일 합의 프로토콜에서 유효하지 않은 블록을 생성하는 리더(또는 블록이 전혀 없음)로 인해 체인이 일시적으로 분기될 수 있습니다. BFT 스타일 합의 프로토콜에서 나쁜 리더는 통신 오버헤드를 발생시키는 보기 변경 하위 프로토콜을 트리거합니다. 

위원회 선거 대안

위원회 선출은 관련된 문제이며 목표는 고정된 크기의 유효성 검사기의 균일하고 무작위적인 하위 집합을 선택하는 것입니다. k. 이 기능은 블록체인 설정에서 블록체인 설정에서 종종 합의 실행 속도를 높이기 위해 검증자 세트 크기를 줄이기 위해 필요하기 때문에 그 자체로 유용합니다. 알고랜드의 분류 과 이더리움 위원회 선정). 그러나 위원회 선거는 리더 선출에도 유용하며, 선출된 리더가 나타나지 않을 경우 유효성 검사기가 리더 선거 프로토콜을 다시 실행하지 않도록 합니다. 리더 대신 정해진 순서로 위원회를 선출할 경우 첫 번째 위원이 없을 경우 두 번째 위원이 리더가 될 수 있습니다. 

좋은 선거 프로토콜의 속성

리더 선출 프로토콜에서 리더는 예측할 수 없어야 합니다. 공격자가 다음 리더가 누구인지 알게 되면 블록을 게시하지 못하도록 서비스 거부(DoS) 공격을 시작할 수 있습니다. 그런 다음 공격자는 다음 리더를 쓰러뜨리는 식으로 블록체인을 중단시킬 수 있습니다. 예측 불가능성은 검증자 자체가 리드할 때 학습하지 않도록 강화될 수 있으며, 이는 뇌물 방지에 중요할 수 있습니다.

리더 선출 프로세스에는 다음 세 가지 속성이 있어야 합니다.

• 공평: 각 정직한 검증자는 1/의 확률을 가집니다.N 집합에서 선출 N 유효성 검사기(편안한 개념 게임 이론적 공정성은 라운드 수의 하한선이 일정하지 않더라도 악의적인 다수가 존재하는 경우에도 리더 선출을 구축합니다.
• 예측할 수 없음: 적이 어느 정도 시간이 될 때까지 다음 리더를 배우지 않습니다. T 리더가 다음 블록을 발표하기 전에
• 고유성: 각 슬롯에서 정확히 하나의 리더가 선택됩니다.

비밀 지도자 선거

비밀 지도자 선거는 예측할 수없는 선거입니다. T = 0. 이 과정에서 리더는 블록을 게시할 때까지 누구에게도 알려지지 않습니다. 이렇게 하면 DoS 공격의 기회가 완전히 제거됩니다. 리더가 자신을 드러내기 전에 공격자는 누구를 공격해야 할지 모르기 때문에 최선의 전략을 무작위로 추측하게 됩니다. 그리고 리더가 블록을 게시한 후에는 리더가 이미 프로토콜에 대한 책임을 다했기 때문에 공격하기에는 너무 늦습니다. 

그러나 "리더가 블록을 게시한 후"라는 개념은 현실 세계에서 즉각적인 브로드캐스트가 없기 때문에 실제로는 단순화된 것입니다. 강력한 네트워크 위치에 있는 공격자는 먼저 블록을 브로드캐스트하는 리더를 알아차리고 리더를 빠르게 손상시키고 다른 블록을 생성하고 원래 브로드캐스트를 전면 실행할 수 있습니다. 

이것은 매우 강력한 공격자 모델이지만 이에 대한 방어가 제안되었습니다. 알고랜드는 삭제 모델, 리더는 슬롯에서 블록 서명에 필요한 키를 실제로 지울 수 있습니다. 전에 그래서 지도자가 공개적인 조치를 취할 때까지 공격하기에는 정말 너무 늦었습니다. MIT Media Lab의 세 명의 연구원인 Thaddeus Dryja, Quanquan C. Liu 및 Neha Narula는 제안 된 리더는 브로드캐스트하기 전에 블록에서 VDF를 계산하여 적응형 공격자가 원하는 슬롯에 대해 허용할 대체 유효한 블록을 시간 내에 구성할 수 없도록 합니다.

기타 선거 방법 

가장 간단한 리더 선출 프로세스는 라운드 로빈, 여기서 리더는 결정론적 순서로 선출됩니다. 이 접근 방식은 예측 가능하고 따라서 DoS 공격에 취약하지만 유효성 검사기가 DoS 보호 기능이 우수한 허가된 시스템에 적합합니다.

외부 출력을 사용하여 리더를 선출할 수도 있습니다. 임의성 비콘, 사용 가능하고 안전하다고 신뢰할 수 있는 경우. 불행하게도 컨센서스 참여자들이 DRB(distributed randomness beacon) 프로토콜을 자체적으로 실행하는 것은 까다롭습니다. 이들은 일반적으로 신뢰할 수 있는 브로드캐스트 또는 컨센서스의 개념을 가정하기 때문에 다시 리더 선택을 요구하고 순환 종속성을 도입하기 때문입니다.

Current Ethereum의 리더 선거 좋은 사례 연구입니다. 각각의 새로운 리더는 VRF(Verifiable Randomness Function) 출력(epoch 번호의 BLS 서명)을 계산하고 값을 혼합으로 XOR합니다. 에포크 종료 시점의 믹스 값 i epoch 기간 동안 리더와 소위원회를 정의합니다. i+2. 리더와 일정은 한 에포크(현재 ~6.4분) 전에 예측 가능합니다. 이 프로토콜은 공정성 공격에 취약합니다. 마지막 리더가 믹스에 대한 기여를 게시하거나 보류하여 다음 선거 결과에 XNUMX비트 영향을 미칠 수 있기 때문입니다. 마지막 경우  k 지도자들은 결탁하여 소개할 수 있습니다. k  약간의 편견과 악의적인 사용자의 선택 가능성을 높입니다. 이더리움 재단은 아래에서 논의할 리더 선택을 위한 고급 기술을 적극적으로 연구하고 있습니다.

VRF 기반 리더 선출

에 의해 개척된 또 다른 접근법 알고리즘이다 VRF 기반 리더 선출, 각 유효성 검사기가 개인적으로 VRF 출력을 계산하고 출력이 임계값 아래로 떨어지는지 여부를 확인하는 것과 관련됩니다. 임계값이 그 아래로 떨어질 가능성이 없도록 선택되었기 때문에 이 절차는 이미 대부분의 유효성 검사기를 필터링합니다. 남아 있는 소수의 검증자는 VRF 출력을 공개하고 VRF 값이 가장 낮은 검증자가 선출됩니다. 이 접근 방식은 완벽한 예측 불가능성(또는 비밀성)을 달성하지만 고유성을 보장하지는 않습니다. 일부 유효성 검사기는 모든 잠재적 리더로부터 메시지를 받지 못할 수 있으며 잘못된 리더가 선거에서 승리했다고 가정하여 이러한 유효성 검사기가 메인 체인에서 분기되도록 할 수 있습니다. 

VRF 평가는 임의성 비콘의 출력으로 주기적으로 시드되어 유효성 검사기 자체가 어떤 슬롯을 리드할지 예측하기 어렵게 만듭니다. 이 속성은 유효성 검사기가 리더가 될 때 유효성 검사기를 자동으로 손상시키는 공격자가 슬롯을 학습하고 유효성 검사기가 블록을 발표하려고 할 때 공격을 시작하는 것을 방지합니다. 이 접근 방식은 또한 검증자가 특정 슬롯에서 리더가 될 것임을 외부 당사자에게 증명하고 리더로서 일부 작업을 완료하는 대가로 뇌물을 받는 뇌물 공격을 방지하는 데 도움이 됩니다(예: 거래 차단).

선출된 지도자의 수가 무작위 변수인 이러한 접근 방식을 호출합니다. 확률론적 리더 선출 (PLE). PLE는 주어진 슬롯에 대해 리더가 선출되지 않도록 할 수 있습니다. 이것은 슬롯이 궁극적으로 건너뛰게 되어 합의 프로토콜의 효율성을 감소시킨다는 점에서 악의적이거나 오프라인인 리더를 선출하는 것과 같습니다.

그러나 PLE의 가장 큰 주의 사항은 여러 리더가 선출될 수 있으므로 일종의 타이 브레이킹 절차가 필요하다는 것입니다. 동점은 합의에 위험을 초래합니다. 승자 입력이 있는 유효성 검사기가 네트워크의 절반에만 보고할 수 있기 때문에 잠재적으로 선택한 리더에 의견 불일치가 발생할 수 있습니다. 또한 관계를 해결하는 프로세스에 추가 시간과 커뮤니케이션이 소요되어 효율성이 저하될 수 있습니다. Dfinity, 에서 더 자세히 논의 첫 번째 게시물 이 시리즈의 VRF 기반 임의성 비콘을 사용하여 단일 리더를 선출합니다. 그러나 이를 위해 예측 불가능성을 희생합니다. 이상적으로는 리더를 선택하는 모든 프로세스는 동점을 완전히 피하고 여전히 예측할 수 없어야 하며, 이는 이 연구 분야의 성배인 단일 비밀 리더 선거로 이어집니다.

단일 비밀 지도자 선거 

의 목표 단일 비밀 지도자 선거 (SSLE)는 공정성과 예측 불가능성을 유지하면서 일련의 검증자 중에서 고유한 리더를 선택하는 것입니다. Protocol Labs는 이 개념을 연구 문제, 그리고 스탠포드 컴퓨터 과학자이자 a16z 암호화 연구 고문인 Dan Boneh는 Saba Eskandarian, Lucjan Hanzlik, Nicola Greco와 함께 나중에 제안했습니다. SSLE의 공식적인 정의. 이 고유성 속성은 타이 브레이킹 절차에서 발생하는 합의 위험 및 효율성 비용을 방지합니다. 구체적으로 Protocol Labs의 Sarah Azouvi와 Politecnico di Torino의 Danielle Cappelletti는 표시 가장 긴 체인 프로토콜에서 PLE와 비교할 때 SSLE를 사용하면 블록이 훨씬 더 빠르게 완료될 수 있습니다(적이 스테이크의 25/XNUMX을 제어하는 ​​경우 XNUMX% 더 빠름). 따라서 실용적인 SSLE 프로토콜을 개발하는 것이 중요한 문제입니다.

가장 일반적인 접근 방식은 셔플 기반 (원본 SSLE 논문과 이더리움 SSLE 제안), 각 유효성 검사기는 로마 교황 사절 그것은 무작위로 보이지만 그들이 그들에게 속한다는 것을 증명할 수 있습니다. 그런 다음 nonce는 목록으로 컴파일됩니다. nonce를 제출한 유효성 검사기에서 연결이 해제되도록 목록을 섞습니다. 즉, 섞인 목록이 주어지면 어떤 검증인이 어떤 nonce를 제출했는지 알 수 없습니다. 그런 다음 공개에 따라 목록 인덱스가 선택됩니다. 임의성 비콘, 그리고 리더는 섞인 목록의 해당 인덱스에 있는 논스(nonce)가 자신에게 속한다는 것을 증명함으로써 자신을 드러냅니다. 

하나의 인덱스만 선택되기 때문에 셔플 기반 프로토콜은 항상 유일한 지도자. 임의의 비콘은 임의의 값을 균일하게 출력하도록 구성되어 있기 때문에 프로토콜도 공정한: 각 검증인은 선출될 동등한 기회를 갖습니다. 또한, 셔플링이 적절하게 수행되고(즉, 균등하게 무작위로) 논스(nonce)가 검증인의 신원에 연결되지 않게 되면 이 프로토콜은 또한 다음을 달성합니다. 예측 불가능 성.

랜덤 비콘을 기반으로 셔플되지 않은 목록에서 단순히 인덱스를 선택하면 이미 고유성과 공정성이 부여되지만 예측 불가능성은 달성하기 더 어렵기 때문에 셔플링이 필요합니다. 공격자가 어떤 검증인이 어떤 논스를 제출했는지 알면 누가 선택한 논스를 제출했는지 알 수 있습니다. 색인을 생성하고 리더를 식별할 수 있습니다. 

다음 두 가지 접근 방식은 서로 다른 방식으로 목록을 섞습니다. 더 간단한 것은 이더리움 SSLE 제안어느 n 검증자는 Tor를 통해 논스를 제출하여 논스에서 검증인의 ID를 연결 해제합니다. 모든 유효성 검사기가 등록되면 공개 무작위 비콘을 사용하여 목록이 섞이고 유효성 검사기는 섞인 목록 순서대로 리더가 됩니다. 이 계획은 실용적이지만 선거는 XNUMX년에 한 번만 실행되어야 합니다. n 슬롯 – Tor에 대한 이러한 의존은 바람직하지 않을 수 있습니다(외부 프로토콜의 보안에 의존하는 경우와 마찬가지로). 게다가 완전히 예측할 수 없는 것은 아닙니다. n-1명의 리더가 자신을 드러내고, 최종 nth 리더는 알려져 있다.

Tor를 사용하는 대신, 원래 SSLE 문서에는 nonce를 목록에 추가하고, 목록을 섞고, 재무작위화 논스. 이 재랜덤화는 각 논스를 연결 불가능한 새 문자열로 매핑하여 그것이 속한 검증자가 여전히 재랜덤화된 논스의 소유권을 증명할 수 있음을 의미합니다. 재무작위화는 적어도 하나의 셔플러가 정직하다고 가정할 때 적이 셔플 후에 어떤 특정 논스가 어떤 위치에 있는지 알 수 없도록 합니다.

원래 SSLE 논문의 이 순차적 셔플 접근 방식은 Tor에 대한 의존을 피하고 SSLE의 형식적 속성을 달성하지만 비용이 많이 듭니다. 그들이 정직하게 행동했다는 증거를 제공하여 검증자당 선형적인 커뮤니케이션 양을 가져옵니다. 변경되지 않는 유효성 검사기 세트를 사용하면 리더가 nonce에 대한 증거를 공개한 후 다시 등록하므로 선거당 한 번 수행(분할 상환)해야 합니다. 이 논문은 조정 가능한 효율성-예측 가능성 트레이드 오프를 제공합니다. 대신 소량의 예측 가능성을 허용하려는 경우 목록의 더 작은 하위 집합만 섞을 수 있으므로 비용이 절감됩니다. 효율성과 보안 간의 균형을 잘 맞추는 것은 어려운 일이므로 SSLE 프로토콜은 아직 실제로 널리 사용되지 않습니다. 

편리하게도 이 순차 셔플링 접근 방식은 무작위 비콘을 사용하여 목록에서 k개의 개별 인덱스를 위원회 구성원으로 선택함으로써 위원회 선출 문제를 해결하는 데에도 사용할 수 있습니다. 확률론적 VRF 기반 프로토콜을 실행하기 때문에 VRF 기반 접근 방식으로 문제가 사소하게 해결되지 않기 때문에 이것은 좋은 성과입니다. k 시간은 임의성에 따라 다양한 위원회 크기를 선택할 수 있습니다. 

SSLE에 대한 다른 접근 방식

또 다른 셔플 기반 접근법은 DDH의 적응형 보안 SSLE. 이 구성은 약간 더 복잡하지만 더 강력한 보안 개념을 달성하여 적응 적 알고랜드의 삭제 모델에서. 이 적은 프로토콜이 시작되기 전이 아니라 프로토콜 중에 손상시킬 유효성 검사기를 선택할 수 있다는 점에서 적응력이 있습니다. 

SSLE의 또 다른 과제는 균등하게 무작위로가 아니라 지분에 비례하는 확률로 각 유효성 검사기를 선택하는 것입니다. 셔플링 기반 프로토콜은 각 검증인이 보유하고 있는 지분 단위마다 하나의 임시값을 등록하도록 허용함으로써 순진하게 이를 달성할 수 있습니다. 그러나 셔플링 비용은 지분 단위 수에 따라 선형적으로 증가합니다. S, 현실적인 지분 분배의 경우에도 매우 비싸집니다. 우아한 MPC 기반 SSLE 접근 방식은 로그로만 복잡성이 증가합니다. S, 또한 신뢰할 수 있는 설정 또는 임의성 비콘이 필요하지 않습니다. 그러나 셔플 기반 접근 방식에 비해 선출된 리더당 더 많은 의사 소통(참가자 수의 대수)이 필요합니다.

***

이 편리한 표에 분석을 요약했습니다.

* 라운드 로빈 비콘은 완전히 예측 가능하지만 나머지 비콘에서는 ✗ 개념이 특정 제한된 수준까지 달성됨을 의미합니다. 이상적인 임의성 비콘은 예측할 수 없지만 적은 선출된 리더와 동시에 출력을 학습하므로 선출된 리더는 블록을 발표하기 전에 공격을 받을 수 있습니다. Etherum의 비콘은 최대 6분까지 예측할 수 없으며 약간 편향되어 공정성을 해칠 수 있습니다. 알고랜드는 작은 확률로 여러 리더를 선출합니다.

SSLE는 공정성, 예측 불가능성 및 고유성을 달성하는 유망한 방향입니다. 채택에 직면한 두 가지 중요한 문제는 효율성과 불균일한 지분 분배를 수용할 수 있는 능력입니다. 또한 우리가 강조하는 셔플 기반 SSLE 접근 방식은 편향되지 않은 임의 비콘이 존재한다고 가정하며 이는 실제로 달성하기 쉽지 않습니다. SSLE는 최근에야 공식적으로 정의되었으므로 가까운 장래에 문제를 해결하는 개선된 프로토콜을 보게 될 것입니다. 

***

미란다 그리스도 컬럼비아 대학교에서 컴퓨터 공학 박사 과정을 밟고 있으며, 이론 그룹의 회원이자 회장 연구원입니다. 그녀는 또한 a16z crypto의 연구 인턴이기도 합니다.

조셉 보노 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를 참조하십시오.