Qtum 연구소：Cuckoo Cycle 알고리즘 소개

 

 

 

　　

　　MimbleWimble는 인 블록 사슬 프리미티브 우수한 확장 성과 프라이버시를 제공 둘도 강력한 암호화에 의존 프로토콜. 누락 및 기타 지역은 트랜잭션의 수 (<코어 100 바이트)를 최소화 Utxo을 채택하고,

 

- MimbleWimble 프로젝트 계약의 주요 목표와 기능 거래의 거래 금액에서 공개 정보를 만들어 개인 정보 보호, 송신자와 수신자를 추적 할 수 없습니다 체인 블록에 비해 상당한 공간 절약, 강력한 암호화 및 검증은 MimbleWimble 만 타원 곡선 암호에 따라, 그것은 시도 시험 수십 통해왔다. 

 

최근 커뮤니티 중심의 프로젝트 Grin은 새로운 PoW의 Cuckoo Cycle 알고리즘을 사용하여 광산업 을 장려 합니다.

 

　　리뷰 : QTUM Quantum Chain Institute : 새로운 개인 정보 보호 프로토콜 MimbleWimble

　　PoW 합의는 Bitcoin에 의해 처음으로 채택 되었으며 블록 체인에 의해 사용 된 최초의 합의 방법이었다. 

지금까지 PoW는 내결함성을위한 가장 좋은 공용 체인 컨센서스 메커니즘입니다. 공개 체인의 보안 토대는 합의 메커니즘입니다 .PoW는 물리적 컴퓨팅 성능을 기반으로합니다.

 

전체 네트워크 (51 % 공격)의 컴퓨팅 성능의 절반 이상을 차지해야하므로 Bitcoin과 같이 체인의 컴퓨팅 성능이 특정 규모에 도달하면 공격이됩니다 매우 비쌉니다. 전원이 분산되어있을 때 전원 공격을하는 것은 어렵습니다.

　　

그러므로, 알고리즘 선택은 계산 능력을 분산시키는 경향이있다 (반 평행 마이닝 알고리즘). 이는 DRAM 대기 시간이 상대적으로 일정하게 유지되는 반면 CPU 속도와 메모리 대역폭은 하드웨어 아키텍처와 처리 기술간에 크게 다르므로 주 메모리 지연을 병목 현상으로 만들면 성취됩니다.

　　

 

       일반적인 POW 알고리즘 유형

　　순수 해시 유형 알고리즘 : 임의 충돌, 계산 난이도

　　 Equihash 클래스 알고리즘 : 일반화 된 생일 역설 문제, 메모리 하드

　　ETH 해시 : 제약 조건을 해결하기위한 DAG 기반, 메모리 - 하드

　　Cuckoo Cycle : 그래프 이론 작업 모드 증명, 메모리 하드

　　Cuckoo Cycle

　　그리고 포로 연장이 알고리즘 뻐꾸기주기의 상단에, 알고리즘은, 더 공평한 방식으로 컨센서스 인 하드웨어 아키텍처, 하드웨어 및 비용 효율적인 광산의 성능 차이를 최소화 할 수 있습니다.

　　

Cuckoo Cycle은 확장 가능한 메모리 요구 사항과 즉각적인 검증 가능성을 결합한 새로운 그래프 이론 알고리즘 설계입니다. 또한 메모리 대기 시간을 제어하는 ​​최초의 설계 런타임입니다. 예측할 수없는 메모리 시간 트레이드 오프가 없다면, 상품 하드웨어의 비용 효율성이 광업 산업의 분산화에 크게 기여할 수 있다는 사실을 거의 완벽하게 증명하는 메모리 제한 증명이 생길 것입니다.

　　
Cuckoo Cycle의 흥미로운 특징은 ASIC을 제조하는 것이 비용면에서 효율적이지 않다는 것입니다. 여전히 ASIC은 거의 불가피하므로 Cuckoo 루프를위한 ASIC을 사용할 수있게 될 것입니다. 그러나이 경우에도 하드웨어 제조업체는 일반 사용자에게 ASIC을 만들 수 없습니다.

　　

     이 기사는 Grin - Cuckoo Cycle에서 사용 된 PoW 합의 알고리즘에 초점을 맞 춥니 다.

　　Grin의 PoW 알고리즘 : Cuckoo Cycle

　　

Grin의 기본적인 Proof-of-Work 알고리즘은 Cuckoo Cycle이라고하며 2014 년 John Tromp에 의해 개발되었습니다.

 

이는 주로 메모리 제약 알고리즘이므로 솔루션 시간은 원래 프로세서 또는 GPU 속도가 아닌 메모리 대역폭으로 제한됩니다. 

따라서 Cuckoo Cycle의 솔루션은 대부분의 상용 하드웨어에서 작동해야합니다. Grin은 2 개의 POW 알고리즘을 도입했습니다. 

 

주 알고리즘은 ASIC 친화적 인 반면 보조 알고리즘은 ASIC 내성을 갖도록 설계되었습니다. 초기 출시 당시 Grin Mining은 점차적으로 anti-ASIC에서 ASIC-friendly로 전환했습니다.

　　

블록의 90 %는 네트워크가 시작될 때 2 차 알고리즘에 의해 파헤쳐지고, 주 알고리즘은 블록의 약 10 %만을 파고들 것입니다. 

 

주요 알고리즘은 Cuckatoo31이며 2 차 알고리즘 인 Cuckaroo29, Cuckaroo29 anti-ASIC은 매 6 개월마다 알고리즘을 변경하여 구현됩니다.

　　

 Cuckoo Cycle 문제

　　Cuckoo Cycle 문제는 Cuckoo 다이어그램에서 L- 길이 링을 찾는 것입니다. Cuckoo 그래프는 두 노드 (노드를 연결하는 선)가 두 개의 개별 노드 그룹 사이에서만 연결되는 두 부분 그래프입니다. N 개의 노드와 M 개의 에지로 구성되며 노드는 Cuckoo 해시 테이블로 표시됩니다.

　　

그래프의 한면은 홀수 색인 (그래프의 최대 크기)으로 번호가 매겨진 배열이고, 다른면은 짝수 색인으로 번호가 매겨집니다. 아래의 간단한 차트는 짝수쪽에 4 개의 노드 (위쪽)와 홀수쪽에 4 개의 노드와 4 개의 측면 (아래쪽)이있는 그래프입니다.

 

 

　

　Cuckoo Cycle의 존재 확률

　　포로의 작업량 증명의 보안과 공정성을 보장하기 위해서는 모든 참가자가 어떤 방법 으로든 문제를 해결할 확률을 향상시킬 수 없다는 것을 의미합니다. Cuckoo Cycle이 존재할 확률은 그래프의 노드 수와 모서리 수와 관련이 있으며, M과 N이 증가할수록 그래프에서 L의 루프를 찾을 확률은 안정적인 경향이 있습니다.

　　아래 그림은 링이 L = 42 인 경우 M / N 비율로 볼 수있는 확률을 보여줍니다. M = 29, 31, N = 2M, M / N = 50 %이고 L = 42의 반지를 발견 할 확률은 1/42임을 알 수 있습니다.

 

　　Cuckoo 그래프의 가장자리 트리밍 및 루프 감지

　　노드의 자유도를 계산하고 2보다 작은 에지를 반복적으로 트리밍하면 (루프의 일부가되지 않음) 루프 찾기 알고리즘에 필요한 에지 수를 크게 줄일 수 있습니다. 절단 가장자리의 예는 다음 도면, 먼저 캔 (2,15) (11,12)의 경우,이 시간 (10,11) (4,15) 조건이 정리 될 수있다 마지막이 완료 오른쪽 트리밍 남아 등장 그림, 측면 수를 40 % 줄입니다.

 

 

　　

제 가장자리부터 검출 루프, 다른 쪽은 트리 구조를 형성 할 링이없는 상태에서 첨가 하였다 새로운 에지 트리 백 루프를 형성할지 여부를 결정함으로써 루트 노드의 깊이에 따라 선택했다. 모든 점에 대해 한 번 실행하고 모서리와 관련된 모든 루프를 찾아 대상 매개 변수와 비교합니다. 동일한 길이의 루프가 있으면 문제가 성공적으로 해결됩니다.

　　 

 

       Grin의 PoW 실행 프로세스

　　블록이 처리되면, 이는 도면 고리를 찾아, 쿠쿠 해시 알고리즘을 결합의 헤더 영역, 헤더 영역을 얻을 수 있고, 결과가 해시와 비교하여 더 어려운 목표 대상 미만의 부하 POW 찾을 완료되었습니다. 프로세스는 다음과 같습니다.

　　새 블록 헤더를 해시하여 해시 값 K 생성

　　해시 값 K는 SIPHASH 함수의 KEY로 사용되며 그래프의 각 요소에 대한 위치 쌍을 생성합니다.

　　트리밍을 수행하면 Cuckoo 루프 감지 알고리즘이 실행되어 생성 된 그래프 (즉, 길이가 42 인 루프)에서 솔루션을 찾으려고 시도합니다.

　　

발견 된 링의 Blake2b 해시를 현재 대상 난이도와 비교합니다.

　　해시 난이도가 목표 난이도보다 크거나 같으면 블록을 네트워크로 브로드 캐스트하고 다음 블록에서 작업을 시작합니다

　　

솔루션을 찾지 못하면 블록 헤더의 Nounce를 1 늘리고 다음 해시 반복을위한 타임 스탬프를 업데이트하십시오

　

 

　참고 자료

　　 Https : // forum. AE ternity.com/t/pow-vs-pos/767

　　추천 독서

　　Qtum Quantum Chain Weekly (3 월 4 일 - 3 월 10 일)

　　Qtum Quantum Chain, 일본 Blockchain Summit TEAMZ에 초청 됨

　　Qtum 퀀텀 체인 첫 번째 공간 노드 트랜잭션 완료

　　Qtum Quantum Chain Technology 서비스를 Amazon에서 무료로 사용하는 방법

 

 

http://www.btb8.com/qtum/1904/41573.html