난수 및 분산 네트워크: 실제 응용

소개

"난수 생성은 우연에 맡기기에는 너무 중요합니다."
로버트 카부에, 1970

이 기사는 신뢰할 수 없는 환경에서 집단 난수 생성을 사용하는 솔루션의 실제 적용에 대해 다룹니다. 간단히 말해서, 블록체인에서 무작위가 어떻게, 왜 사용되는지, 그리고 "좋은" 무작위와 "나쁜" 무작위를 구별하는 방법에 대해 조금 설명합니다. 진정한 난수를 생성하는 것은 단일 컴퓨터에서도 매우 어려운 문제이며 오랫동안 암호학자에 의해 연구되어 왔습니다. 분산형 네트워크에서 난수 생성은 훨씬 더 복잡하고 중요합니다.

참가자들이 서로를 신뢰하지 않는 네트워크에서는 확실한 난수를 생성하는 기능을 통해 많은 중요한 문제를 효과적으로 해결하고 기존 체계를 크게 개선할 수 있습니다. 더욱이, 경험이 부족한 독자에게는 처음에는 그렇게 보일 수 있기 때문에 도박과 복권이 여기서 최고의 목표가 아닙니다.

난수 생성

컴퓨터는 스스로 난수를 생성할 수 없으며 이를 위해서는 외부의 도움이 필요합니다. 컴퓨터는 마우스 움직임, 사용된 메모리 양, 프로세서 핀의 표류 전류 및 엔트로피 소스라고 하는 기타 여러 소스로부터 임의의 값을 얻을 수 있습니다. 이러한 값 자체는 특정 범위에 있거나 예측 가능한 변화 패턴을 갖기 때문에 완전히 무작위가 아닙니다. 이러한 숫자를 주어진 범위 내에서 진정한 난수로 바꾸기 위해 암호화 변환이 적용되어 엔트로피 소스의 고르지 않게 분포된 값에서 균일하게 분포된 의사 난수 값을 생성합니다. 결과 값은 실제 무작위가 아니라 결정론적으로 엔트로피에서 파생되므로 의사 난수라고 합니다. 좋은 암호화 알고리즘은 데이터를 암호화할 때 통계적으로 무작위 시퀀스와 구별할 수 없는 암호문을 생성하므로 무작위성을 생성하려면 작은 범위에서도 값의 우수한 반복성과 예측 불가능성을 제공하는 엔트로피 소스를 사용할 수 있습니다. 나머지 작업은 비트를 분산하고 혼합하는 것입니다. 결과 값은 암호화 알고리즘에 의해 인수됩니다.

간단한 교육 프로그램을 완성하기 위해 하나의 장치에서도 난수를 생성하는 것이 데이터 보안을 보장하는 핵심 중 하나라고 덧붙일 것입니다. 생성된 의사 난수는 다양한 네트워크에서 보안 연결을 설정할 때 사용되어 데이터를 생성합니다. 로드 밸런싱, 무결성 모니터링 및 더 많은 애플리케이션을 위한 암호화 키입니다. 많은 프로토콜의 보안은 신뢰할 수 있고 외부적으로 예측할 수 없는 무작위를 생성하고 저장하며 프로토콜의 다음 단계까지 이를 공개하지 않는 능력에 달려 있습니다. 그렇지 않으면 보안이 손상됩니다. 의사 난수 값 생성기에 대한 공격은 매우 위험하며 무작위 생성을 사용하는 모든 소프트웨어를 즉시 위협합니다.

암호화에 대한 기본 과정을 수강했다면 이 모든 것을 알아야 하므로 분산 네트워크에 대해 계속 살펴보겠습니다.

블록체인에서의 무작위

우선, 고품질의 부인할 수 없는 무작위성이 제공하는 기회를 최대한 활용할 수 있는 스마트 계약을 지원하는 블록체인에 대해 이야기하겠습니다. 또한, 간략하게 이 기술을 ''이라고 부르겠습니다.공개적으로 검증 가능한 무작위 비콘" 또는 PVRB. 블록체인은 모든 참가자가 정보를 확인할 수 있는 네트워크이므로 이름의 핵심 부분은 "공개적으로 검증 가능"입니다. 누구나 계산을 사용하여 블록체인에 게시된 결과 숫자가 다음과 같은 속성을 가지고 있다는 증거를 얻을 수 있습니다.

• 결과는 입증 가능한 균일한 분포를 가져야 합니다. 즉, 입증 가능한 강력한 암호화를 기반으로 해야 합니다.
• 결과의 어떤 비트도 제어할 수 없습니다. 따라서 결과를 미리 예측할 수 없습니다.
• 프로토콜에 참여하지 않거나 공격 메시지로 네트워크에 과부하를 주어 생성 프로토콜을 방해할 수 없습니다.
• 위의 모든 사항은 허용되는 부정직한 프로토콜 참가자 수(예: 참가자의 1/3)의 공모에 저항해야 합니다.

소수 참가자 그룹이 공모하여 통제된 짝수/홀수 무작위를 생성할 가능성은 보안 허점입니다. 무작위 발행을 막는 그룹의 모든 능력은 보안 허점입니다. 전반적으로 문제가 많은데 이 작업도 쉽지 않습니다...

PVRB의 가장 중요한 응용 프로그램은 다양한 게임, 복권 및 일반적으로 블록체인의 모든 유형의 도박인 것 같습니다. 실제로 이것은 중요한 방향이지만 블록체인의 무작위성은 훨씬 더 중요한 용도로 사용됩니다. 그들을 살펴보자.

합의 알고리즘

PVRB는 네트워크 합의를 구성하는 데 큰 역할을 합니다. 블록체인의 거래는 전자 서명으로 보호되므로 "거래에 대한 공격"은 항상 블록(또는 여러 블록)의 거래를 포함/제외하는 것입니다. 그리고 합의 알고리즘의 주요 임무는 이러한 거래의 순서와 이러한 거래를 포함하는 블록의 순서에 동의하는 것입니다. 또한, 실제 블록체인에 필요한 속성은 최종성입니다. 즉, 최종 블록까지의 체인이 최종적이며 새로운 포크의 출현으로 인해 결코 제외되지 않는다는 점에 네트워크가 동의하는 능력입니다. 일반적으로 블록이 유효하고 가장 중요하게 최종적이라는 데 동의하려면 대다수의 블록 생산자(이하 BP - 블록 생산자라고 함)로부터 서명을 수집해야 하며, 이를 위해서는 최소한 블록체인을 전달해야 합니다. 모든 BP에게 서명을 배포하고 모든 BP 간에 서명을 배포합니다. BP의 수가 증가함에 따라 네트워크에 필요한 메시지의 수도 기하급수적으로 증가하므로 Hyperledger pBFT 합의에서 사용되는 최종성을 요구하는 합의 알고리즘은 수십 개의 BP에서 시작하여 필요한 속도로 작동하지 않습니다. 엄청난 수의 연결.

네트워크에 부정할 수 없고 정직한 PVRB가 있는 경우, 가장 단순한 근사치에서도 이를 기반으로 블록 생산자 중 한 명을 선택하고 프로토콜의 한 라운드 동안 그를 "리더"로 임명할 수 있습니다. 우리가 가지고 있다면 N 블록 생산자 중 M: M > 1/2 N 정직하고, 거래를 검열하지 않으며, "이중 지출" 공격을 수행하기 위해 체인을 분기하지 않습니다. 그런 다음 균일하게 분산된 도전받지 않은 PVRB를 사용하면 확률이 있는 정직한 리더를 선택할 수 있습니다. M / N (M / N > 1/2). 각 리더에게 블록을 생성하고 체인을 검증할 수 있는 시간 간격이 할당되고 이 간격이 시간상 동일하다면 정직한 BP의 블록체인은 악의적인 BP에 의해 형성된 체인보다 길어질 것이며 합의는 알고리즘은 체인의 길이에 의존하므로 단순히 "나쁜" 체인을 버립니다. 각 BP에 동일한 시간을 할당하는 이 원칙은 Graphene(EOS의 전신)에서 처음 적용되었으며, 대부분의 블록이 단일 서명으로 닫힐 수 있도록 하여 네트워크 부하를 크게 줄이고 이러한 합의가 매우 빠르고 효율적으로 작동할 수 있도록 합니다. 꾸준히. 그러나 이제 EOS 네트워크는 2/3 BP의 서명으로 확인되는 특수 블록(Last Irreversible Block)을 사용해야 합니다. 이러한 블록은 최종성을 보장하는 역할을 합니다(마지막 되돌릴 수 없는 마지막 블록 이전에 체인 포크가 시작하는 것이 불가능함).

또한 실제 구현에서는 프로토콜 방식이 더 복잡합니다. 제안된 블록에 대한 투표는 블록 누락 및 네트워크 문제가 발생할 경우 네트워크를 유지하기 위해 여러 단계로 수행되지만 이를 고려하더라도 PVRB를 사용하는 합의 알고리즘에는 다음이 필요합니다. BP 간의 메시지 수가 훨씬 적어서 기존 PVFT나 다양한 수정보다 속도가 빨라집니다.

이러한 알고리즘의 가장 유명한 대표자는 다음과 같습니다. 우로 보로스 이는 BP 공모에 대해 수학적으로 증명 가능하다고 알려진 Cardano 팀의 주장입니다.

Ouroboros에서 PVRB는 소위 "BP 일정"을 정의하는 데 사용됩니다. 이 일정은 각 BP에 블록 게시를 위한 자체 시간 슬롯이 할당되는 일정입니다. PVRB 사용의 가장 큰 장점은 BP의 완전한 "균등"입니다(대차대조표 규모에 따라). PVRB의 무결성은 악의적인 BP가 타임 슬롯의 일정을 제어할 수 없도록 보장하므로 체인의 포크를 미리 준비하고 분석하여 체인을 조작할 수 없으며 포크를 선택하려면 단순히 길이에 의존하면 충분합니다. BP의 "효용성"과 블록의 "무게"를 계산하는 까다로운 방법을 사용하지 않고 체인을 관리합니다.

일반적으로 분산형 네트워크에서 임의의 참가자를 선택해야 하는 모든 경우 PVRB는 예를 들어 블록 해시를 기반으로 하는 결정론적 옵션보다는 거의 항상 최선의 선택입니다. PVRB가 없으면 참가자의 선택에 영향을 미칠 수 있는 능력은 공격자가 여러 미래 중에서 선택하여 다음 부패한 참가자를 선택하거나 한 번에 여러 참가자를 선택하여 결정에서 더 큰 공유를 보장할 수 있는 공격으로 이어집니다. PVRB를 사용하면 이러한 유형의 공격을 신뢰할 수 없습니다.

확장 및 로드 밸런싱

PVRB는 부하 감소 및 지불 확장과 같은 작업에서도 큰 이점을 얻을 수 있습니다. 우선, 다음 사항에 익숙해지는 것이 좋습니다. 조 Rivesta “소액 결제로서의 전자 복권”. 일반적인 생각은 지불인이 받는 사람에게 100 1c 지불을 하는 대신 1$ = 100c의 상금으로 정직한 복권을 할 수 있다는 것입니다. 여기서 지불인은 각각에 대해 자신의 "복권" 1장 중 하나를 은행에 제공합니다. 100c 지불. 이 티켓 중 하나는 1달러의 상금을 받게 되며, 수령인은 이 티켓을 블록체인에 기록할 수 있습니다. 가장 중요한 것은 나머지 99개의 티켓이 외부 참여 없이 개인 채널을 통해 원하는 속도로 수신자와 지불자 간에 전송된다는 것입니다. Emercoin 네트워크에서 이 체계를 기반으로 하는 프로토콜에 대한 자세한 설명을 읽을 수 있습니다. 여기에.

이 체계에는 당첨 티켓을 받은 후 수령인이 지불인에게 즉시 서비스를 중단할 수 있다는 등 몇 가지 문제가 있지만 분당 청구 또는 서비스 전자 구독과 같은 많은 특수 애플리케이션의 경우 이러한 문제가 무시될 수 있습니다. 물론 주요 요구 사항은 복권의 무결성이며 이를 구현하려면 PVRB가 절대적으로 필요합니다.

무작위 참가자의 선택은 샤딩 프로토콜에 있어서도 매우 중요합니다. 샤딩 프로토콜의 목적은 블록체인을 수평적으로 확장하여 서로 다른 BP가 자신의 거래 범위만 처리할 수 있도록 하는 것입니다. 이는 특히 샤드 병합 시 보안 측면에서 매우 어려운 작업입니다. 합의 알고리즘에서와 같이 특정 샤드에 대한 책임을 할당하기 위해 무작위 BP를 공정하게 선택하는 것도 PVRB의 임무입니다. 중앙 집중식 시스템에서 샤드는 밸런서에 의해 할당되며 단순히 요청에서 해시를 계산하여 필요한 실행자에게 보냅니다. 블록체인에서 이 할당에 영향을 미치는 능력은 합의에 대한 공격으로 이어질 수 있습니다. 예를 들어, 거래 내용은 공격자가 제어할 수 있으며, 어떤 거래가 자신이 제어하는 ​​샤드로 이동하는지 제어하고 그 안의 블록 체인을 조작할 수 있습니다. Ethereum의 샤딩 작업에 난수를 사용하는 문제에 대한 토론을 읽을 수 있습니다. 여기에
샤딩은 블록체인 분야에서 가장 야심차고 심각한 문제 중 하나이며, 샤딩 솔루션을 사용하면 환상적인 성능과 규모의 분산 네트워크를 구축할 수 있습니다. PVRB는 이를 해결하기 위한 중요한 블록 중 하나일 뿐입니다.

게임, 경제 프로토콜, 중재

게임 산업에서 난수의 역할은 과대평가하기 어렵습니다. 온라인 카지노에서의 명시적인 사용과 플레이어 행동의 효과를 계산할 때의 암시적인 사용은 중앙 무작위 소스에 의존할 방법이 없는 분산형 네트워크에서는 모두 매우 어려운 문제입니다. 그러나 무작위 선택은 많은 경제적 문제를 해결하고 더 간단하고 효율적인 프로토콜을 구축하는 데 도움이 될 수도 있습니다. 우리 프로토콜에서 일부 저렴한 서비스에 대한 지불에 대한 분쟁이 있고 이러한 분쟁은 거의 발생하지 않는다고 가정합니다. 이 경우 논쟁의 여지가 없는 PVRB가 있는 경우 고객과 판매자는 무작위로 분쟁을 해결하는 데 동의할 수 있지만 주어진 확률이 있습니다. 예를 들어, 60% 확률로 고객이 승리하고 40% 확률로 판매자가 승리합니다. 첫 번째 관점에서 볼 때 터무니없는 이 접근 방식을 사용하면 제70자의 참여나 불필요한 시간 낭비 없이 양측 모두에게 적합한 정확하게 예측 가능한 승/패 비율로 분쟁을 자동으로 해결할 수 있습니다. 또한 확률 비율은 동적일 수 있으며 일부 전역 변수에 따라 달라질 수 있습니다. 예를 들어, 회사가 잘 운영되고 분쟁 건수가 적고 수익성이 높은 경우 회사는 분쟁 해결 확률을 고객 중심으로 자동으로 전환할 수 있습니다(예: 30/80 또는 20/XNUMX 또는 그 반대로). 분쟁에 많은 비용이 들고 사기성이 있거나 부적절하다면 확률을 다른 방향으로 바꿀 수 있습니다.

토큰 선별 레지스트리, 예측 시장, 결합 곡선 등과 같은 수많은 흥미로운 분산형 프로토콜은 좋은 행동에 보상을 주고 나쁜 행동에 처벌을 가하는 경제 게임입니다. 여기에는 보호 기능이 서로 충돌하는 보안 문제가 포함되는 경우가 많습니다. 수십억 개의 토큰을 보유한 “고래”(“빅 스테이크”)의 공격으로부터 보호되는 것은 소액 잔고를 가진 수천 개의 계정(“시빌 스테이크”)의 공격에 취약하며, 단일 공격에 대해 취해진 조치는 대규모 지분 작업을 수익성 없게 만들기 위해 생성된 선형 수수료는 일반적으로 또 다른 공격으로 인해 신뢰를 잃게 됩니다. 우리는 경제 게임에 대해 이야기하고 있으므로 해당 통계적 가중치를 미리 계산할 수 있으며 수수료를 적절한 분포를 갖춘 무작위 수수료로 간단히 대체할 수 있습니다. 이러한 확률적 커미션은 블록체인이 신뢰할 수 있는 임의성 소스를 갖고 있고 복잡한 계산이 필요하지 않은 경우 매우 간단하게 구현되어 고래와 시빌 모두의 삶을 어렵게 만듭니다.
동시에, 이 무작위성에서 단일 비트를 제어하면 속임수를 쓰고 확률을 절반으로 줄이거나 늘릴 수 있으므로 정직한 PVRB가 이러한 프로토콜의 가장 중요한 구성 요소라는 점을 계속 기억해야 합니다.

올바른 무작위를 어디에서 찾을 수 있습니까?

이론적으로 분산형 네트워크의 공정한 무작위 선택은 거의 모든 프로토콜을 공모로부터 안전하게 보호합니다. 근거는 매우 간단합니다. 네트워크가 단일 0 또는 1 비트에 동의하고 참가자의 절반 미만이 부정직한 경우 충분한 반복이 주어지면 네트워크는 고정 확률로 해당 비트에 대한 합의에 도달하도록 보장됩니다. 단순히 정직한 무작위가 51%의 확률로 100명의 참가자 중 51명을 선택하기 때문입니다. 하지만 이는 이론상이기 때문에... 실제 네트워크에서는 기사에서와 같은 수준의 보안을 보장하려면 호스트 간의 많은 메시지, 복잡한 다중 패스 암호화가 필요하며 프로토콜이 복잡해지면 즉시 새로운 공격 벡터가 추가됩니다.
이것이 바로 블록체인에서 검증된 저항성 PVRB를 아직 볼 수 없는 이유입니다. 이는 실제 애플리케이션, 다중 감사, 로드 및 물론 실제 공격을 통해 테스트하기에 충분한 시간 동안 사용되었을 것입니다. 정말 안전한 제품입니다.

그러나 몇 가지 유망한 접근 방식이 있으며 세부 사항이 많이 다르며 그 중 하나가 문제를 확실히 해결할 것입니다. 현대 컴퓨팅 자원을 사용하면 암호 이론을 실제 응용 프로그램으로 영리하게 번역할 수 있습니다. 앞으로 우리는 PVRB 구현에 관해 기꺼이 이야기할 것입니다. 이제 그 중 몇 가지가 있으며 각각에는 고유한 중요한 속성 및 구현 기능 세트가 있으며 각 뒤에는 좋은 아이디어가 있습니다. 무작위 배정에 참여하는 팀은 많지 않으며 각 팀의 경험은 다른 모든 사람에게 매우 중요합니다. 우리의 정보를 통해 다른 팀이 전임자의 경험을 고려하여 더 빠르게 움직일 수 있기를 바랍니다.

출처 : habr.com