이더해시 편집하기
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
− | '''이더해시'''(Ethash)는 [[ | + | '''이더해시'''(Ethash)는 러시아, 캐나다의 프로그래머이며 이더리움의 개발자인 [[비탈릭 부테린]](Vitalik Buterin)이 개발한 블록 체인 통화의 [[작업 증명]](POW; Proof Of Work) 기능이다. |
==개요== | ==개요== | ||
− | + | 이더해시는 비트코인의 [[합의 알고리즘]]에 특화된 [[주문형 반도체]](ASIC; Application Specific Integrated Circuit) 장비로 인해 채굴자가 대형화된 연산력을 바탕으로 이뤄진 중앙화를 해결하기 위해 개발된 알고리즘이다. | |
− | + | [[대거]](Dagger) 알고리즘과 [[하시모토]](Hashimoto) 알고리즘을 결합해 만든 [[대거-하시모토]](Dagger-Hashimoto) 알고리즘을 사용한다. 이 알고리즘은 메모리를 활용하는 알고리즘이며, 연산장치의 물리적 한계를 사용함으로써 [[ASIC]]의 효율성을 낮춘다. | |
− | |||
==특징== | ==특징== | ||
− | + | * [[2차원 배열 데이터]](DAG; Directed Acyclic Graph) 파일을 이용해 [[GPU]] 연산의 효율성은 높힌다. ASIC 무력화를 위해 메모리를 사용하며, 컴퓨터 메모리 일정량의 데이터를 읽은 후 [[nonce]]와 [[hash]] 계산을 반복한다. <ref>니르바나,〈[https://ihpark92.tistory.com/51 이더리움의 합의 알고리즘 - 작업증명]〉, 《티스토리》, 2018</ref> | |
− | + | * 목적 자체가 ASIC의 효율성을 낮춰 제작에 어려움을 주는 것이기 때문에 그를 위해 3만 블록마다 수 GB의 [[DAG]]을 새로 생성해 해싱에 사용한다. 블록의 헤더들을 스캔해 [[seed]]값을 추출할 수 있으며 당 seed를 통해 16mb의 [[pseudo random cache]]를 계산할 수 있고 당 cashe를 통해 1gb 이상의 Full Dataset을 생성할 수 있다. 30000 블록 단위 별로 Full Dataset이 완전히 변형되며 선형으로 증가한다. 또 해당 Full Dataset의 랜덤값을 마이닝 해싱 작업에 포함 시키도록 하여 메모리의 읽기 연산과 Dataset 저장 공간에 제약을 줘 ASIC 제작에 어려움을 주며 [[마이닝]] 과정에서 페이지를 불러올 때 mix 과정을 통해 다음에 불러올 페이지를 예측할 수 없게 설계되어 있다. 캐시 용량 자체가 8kb~32kb의 작은 크기로 DAG를 저장하기가 현실적으로 불가하며 [[캐시 미스]]의 확률이 높기 때문에 일부를 캐시에 저장하는 것 또한 불가능하다. | |
− | + | cache data를 이용해 64bytes의 데이터를 생성하고 이를 계산 결과에 맞는 Data size크기만큼 생성하도록 반복해 DAG 파일을 생성한다. | |
− | + | * Memory Hard Computation이다. | |
− | + | * Memory Easy Validation이다. | |
+ | * [[KECCAK]]([[SHA-3]])을 사용한다.<ref>dongsamb,〈[https://steemit.com/kr/@dongsamb/ethereum-pow-ethash Ethereun PoW 알고리즘 비교 및 원리]〉, 《steemit》, 2018</ref> | ||
− | + | '''비트코인과의 비교''' | |
− | + | [[비트코인]]은 [[SHA256]] 연산만을 필요로 하지만 이더해시는 [[DAG]]를 사용해 예상 불가능한 순차적 메모리 연산을 필요로 해 [[ASIC]]의 제작이 어렵다. 비트코인과 같은 [[Pow]] 구조를 갖고 있으나 다른 매커니즘을 갖는다. | |
− | |||
− | # 32개 길이의 배열의 [[ | + | ==채굴 과정== |
− | # | + | # 32개 길이의 배열의 [[Epoch]]수만큼 해싱한다. 그 값을 [[Seed]]값으로 삼는데, 이 Seed값을 30000블록마다 변경된다. |
− | # 1GB 이상의 | + | # Seed 값으로 [[pseudo-random]]한 [[cache data]]를 생성한다. 생성 시 메모리를 사용하게 되는데 메모리를 타 용도로 사용한다면 cache data의 생성 속도가 매우 느려지므로 주의한다. |
− | # | + | # 1GB 이상의 dataset을 생성한다. 이때 [[full client]]와 [[miner]]는 dataset([[DAG]]를 저장하며 dataset은 [[linear]]하게 커진다. DAG 파일은 cache data를 이용해 생성하는데 한 번에 64bytes의 데이터를 생성하고 이를 data size만큼 생성하도록 반복한다. |
+ | # [[mining]] 과정에서 dataset의 일부를 같이 해싱한다. | ||
# [[Keccak156]]해시를 해 결과값이 조건에 맞으면 채굴에 성공한다. | # [[Keccak156]]해시를 해 결과값이 조건에 맞으면 채굴에 성공한다. | ||
− | # | + | # Digest와 Nonce는 블록 헤더에 포함되는데 Digest 필드, Nonce 필드가 포함되지 않아 해시값에 변경이 없다. |
− | |||
===사용 함수=== | ===사용 함수=== | ||
− | + | '''[[Folwer-Noll-Vo]]''' | |
− | |||
hash = FNV_offset_basis | hash = FNV_offset_basis | ||
for each byte_of_data to be hashed | for each byte_of_data to be hashed | ||
33번째 줄: | 31번째 줄: | ||
hash = hash XOR byte_of_data | hash = hash XOR byte_of_data | ||
return hash | return hash | ||
− | |||
* 출력 비트에 따라 FNV_offset_basis 값을 정한다. | * 출력 비트에 따라 FNV_offset_basis 값을 정한다. | ||
* 입력 바이트에 FNV 함수의 출력 비트에 따라 정해지는 FNV 소수를 곱한다. | * 입력 바이트에 FNV 함수의 출력 비트에 따라 정해지는 FNV 소수를 곱한다. | ||
* 입력 바이트와 XOR 연산을 수행한다. | * 입력 바이트와 XOR 연산을 수행한다. | ||
− | === | + | ===mining 과정=== |
def mine(full_size, dataset, header, difficulty): | def mine(full_size, dataset, header, difficulty): | ||
# zero-pad target to compare with hash on the same digit | # zero-pad target to compare with hash on the same digit | ||
46번째 줄: | 43번째 줄: | ||
while hashimoto_full(full_size, dataset, header, nonce) > target: | while hashimoto_full(full_size, dataset, header, nonce) > target: | ||
nonce = (nonce + 1) % 2**64 | nonce = (nonce + 1) % 2**64 | ||
− | return nonce <ref>야옹메롱, 〈[https://blog.naver.com/mage7th/221493945127 크립토알고리즘 개념 및 종류]〉, 《네이버 블로그》, 2018-10-03</ref><ref>bero in TOMAK, 〈[https://medium.com/tomak/%EC%9D%B4%EB%8D%94%EB%A6%AC%EC%9B%80-ethash-%EC%97%B0%EA%B5%AC-16677ed7da50 이더리움 Ethash 연구]〉, | + | return nonce <ref>야옹메롱,〈[https://blog.naver.com/mage7th/221493945127 크립토알고리즘 개념 및 종류]〉, 《네이버 블로그》, 2018-10-03</ref><ref>bero in TOMAK, 〈[https://medium.com/tomak/%EC%9D%B4%EB%8D%94%EB%A6%AC%EC%9B%80-ethash-%EC%97%B0%EA%B5%AC-16677ed7da50 이더리움 Ethash 연구]〉, 《Medium》, 2018-7-26</ref> |
{{각주}} | {{각주}} | ||
== 참고자료 == | == 참고자료 == | ||
− | + | 야옹메롱,〈[https://blog.naver.com/mage7th/221493945127 크립토알고리즘 개념 및 종류]〉, 《네이버 블로그》, 2018-10-03 | |
− | + | ||
− | + | 니르바나,〈[https://ihpark92.tistory.com/51 이더리움의 합의 알고리즘 - 작업증명]〉, 《티스토리》, 2018 | |
− | + | ||
− | + | dongsamb,〈[https://steemit.com/kr/@dongsamb/ethereum-pow-ethash Ethereun PoW 알고리즘 비교 및 원리]〉,《steemit》, 2018 | |
− | + | bero in TOMAK, 〈[https://medium.com/tomak/%EC%9D%B4%EB%8D%94%EB%A6%AC%EC%9B%80-ethash-%EC%97%B0%EA%B5%AC-16677ed7da50 이더리움 Ethash 연구]〉, 《Medium》, 2018-7-26 | |
− | |||
− | |||
− | |||
{{알고리즘|검토 필요}} | {{알고리즘|검토 필요}} |