이더해시

이더해시(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 계산을 반복한다.
• 목적 자체가 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)을 사용한다.

비트코인과의 비교

비트코인은 SHA256 연산만을 필요로 하지만 이더해시는 DAG를 사용해 예상 불가능한 순차적 메모리 연산을 필요로 해 ASIC의 제작이 어렵다. 비트코인과 같은 Pow 구조를 갖고 있으나 다른 매커니즘을 갖는다.

채굴 과정

1. 32개 길이의 배열의 Epoch수만큼 해싱한다. 그 값을 Seed값으로 삼는데, 이 Seed값을 30000블록마다 변경된다.
2. Seed 값으로 pseudo-random한 cache data를 생성한다. 생성 시 메모리를 사용하게 되는데 메모리를 타 용도로 사용한다면 cache data의 생성 속도가 매우 느려지므로 주의한다.
3. 1GB 이상의 dataset을 생성한다. 이때 full client와 miner는 dataset(DAG를 저장하며 dataset은 linear하게 커진다. DAG 파일은 cache data를 이용해 생성하는데 한 번에 64bytes의 데이터를 생성하고 이를 data size만큼 생성하도록 반복한다.
4. mining 과정에서 dataset의 일부를 같이 해싱한다.
5. Keccak156해시를 해 결과값이 조건에 맞으면 채굴에 성공한다.
6. Digest와 Nonce는 블록 헤더에 포함되는데 Digest 필드, Nonce 필드가 포함되지 않아 해시값에 변경이 없다.

사용 함수

Folwer-Noll-Vo

hash = FNV_offset_basis
  for each byte_of_data to be hashed
    hash = hash × FNV_prime
  	hash = hash XOR byte_of_data
  return hash

• 출력 비트에 따라 FNV_offset_basis 값을 정한다.
• 입력 바이트에 FNV 함수의 출력 비트에 따라 정해지는 FNV 소수를 곱한다.
• 입력 바이트와 XOR 연산을 수행한다.

mining 과정

 def mine(full_size, dataset, header, difficulty): 
 # zero-pad target to compare with hash on the same digit 
 target = zpad(encode_int(2**256 // difficulty), 64)[::-1] 
 from random import randint 
 nonce = randint(0, 2**64) 
 while hashimoto_full(full_size, dataset, header, nonce) > target: 
   nonce = (nonce + 1) % 2**64 
   return nonce  

참고자료

• 야옹메롱,〈크립토알고리즘 개념 및 종류〉, 《네이버 블로그》, 2018-10-03

• 니르바나,〈이더리움의 합의 알고리즘 - 작업증명〉, 《티스토리》, 2018

• dongsamb,〈Ethereun PoW 알고리즘 비교 및 원리〉,《steemit》, 2018

• bero in TOMAK, 〈이더리움 Ethash 연구〉, 《Medium》, 2018-7-26

이 이더해시 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반