이퀴해시

이퀴해시(Equihash)는 작업증명에 사용되는 채굴 알고리즘(Proof-of-Work mining algorithm)이다.

개요

2016년 미국 샌디에이고에서 개최된 네트워크 & 분산시스템의 보 안관련 학술토론회의에서 룩셈부르크 대학교 정보통신기술 학제연구센터(the University of Luxembourg's Interdisciplinary Center for Security, Reliability and Trust)는 Memory-Hard Proof-of-Work라는 알고리즘을 소개하였다.

이 알고리즘은 해시충돌 값을 찾아내기 위한 생일문제(birthday problem)의 연구결과에서 출발하여 시간-공간의 균형을 엄격히 규제하고 병행 방식의 최적화가 메모리 대역폭에서 병목에 걸리듯이 제한을 받는 것으로 설계하여 성능개선을 추구하는 에이식(ASIC) 채굴기의 개발이 투입원가-개선효과의 종합적인 평가에서 경제적이지 못하게 한다. 따라서 알고리즘은 객관적으로 에이식에 대한 저항 특징을 갖게 된다. 여기서 가정이 필요한 전제조건은 시중에 판매되는 하드웨어들이 비교적 넓은 메모리 대역폭을 보유하고 있어야 한다.

알고리즘의 발명자는 룩셈부르그 대학교 연구클럽 크립토LUX의 암호학자 알렉스 비류코프(Alex Biryukov)와 암호연구원 드미트리 호브라토비치(Dmitry Khovratovich)이다. 발명은 2006년에 정식 소개되었다. 이 알고리즘을 이퀴해시라 부른다.

블록체인 기반의 암호화폐 지캐시(ZCash), 아이온(Aion) 등이 보안, 프라이버시, 에이식 방식 채굴 제어 등의 측면에서 종합적으로 검토하고 이퀴해시를 자체 암호화폐 시스템에 적용시켰다.

알렉스 비류코프(좌)와 드미트리 호브라토비치(우)

발명 배경

암호화폐 채굴상황 - 현재 비트코인 혹은 유사한 암호화폐들의 채굴 작업증명 상황을 살펴보면 에이식(ASIC) 채굴기와 같은 채굴 전용 하드웨어 출시로 인해 블록체인 시스템이 중앙화 상태로 가는 추세가 뚜렷해진다.

채굴 전용 하드웨어는 특정의 용도로 주문설계 제작된 하드웨어로서 작업증명을 진행하는 컴퓨팅 과정에 월등한 성능을 나타내며 시중에 출시된 상용 컴퓨터 대비 막강한 경쟁력을 가지고 있다. 따라서 암호화페 채굴은 나날이 에이식 하드웨어를 많이 보유한 세력들 또는 대규모의 암호화폐 마이닝풀로 중앙화되어가고 있다.

사례를 들면 ASIC 하드웨어 제작사인 중국의 비트메인은 비트코인 네트워크 해시파워의 51%의 연산력에 접근하는 해시파워 점유율을 보유하고 있다.

만약 비트메인이 보유한 해시파워가 전체 네트워크의 51%에 도달하거나 초과하면 소위 말하는 51% 공격이 이루어질 수 있는 가능성이 형성되며 트랜잭션이 반대로 이루어지거나 이중지불이 이루어지는 것을 포함한 네트워크의 붕괴를 야기시킬 수 있다. 이는 탈중앙화 분산화를 추구하는 블록체인의 개발 취지와 어긋난다.

연구과제 - 상기 암호화폐 채굴상황에서 어떻게 하면 알고리즘 방식으로 특정 용도의 목적으로 개발한 하드웨어의 우세를 해소시켜 중앙화 추이를 방지하느냐는 컴퓨터과학에서 해결해야 할 하나의 과제이다. 이 과제를 해결하는 방식에는 시간원가 제약, 공간원가 제약, 시간-공간 균형 제약 등의 방식들을 활용하여 주문제작 개발의 경제성을 떨어뜨리는 방식이 포함된다.

발명취지 - 메모리 취급 알고리즘으로 전용하드웨어와 시중판매 하드웨어간에 존재하는 전용하드웨어의 우세를 해소 시킴. 구체방식은

• 채굴자별로 보유하고 있는 적기 메모리용량 소요조건 설정방식(Memory-Hard PoWs)과 일정한 시간내에 메모리를 홀딩하는 방식(sequential memory-hard PoWs)

• 경량급의 검증방식, 특히 이더리움의 컨트렉트에 적용가능해야 함.

기본원리

특징

Progress-free process

• 중앙화된 채굴 방식을 피하고 스토캐스틱 프로세스(stochastic process) 상태에서 기존 사건과 관계없이 임의의 주어진 시간에 채굴방식의 작업증명을 추진할 수 있다.

높은 AT원가

• 요청하는 작업증명의 컴퓨팅이 메모리 집약으로 최적화된 에이식 칩이 메모리 영역에서 원가경쟁력을 해소시켰다. 여기서 AT는 영역과 시간의 곱한 값을 표시한다.

작은 검증 프로그램 크기와 인스턴트 검증(Small proof size and instant verification)

• 검증 프로그램 크기가 작고 최소의 메모리 사용량 상태에서 신속하고 충분하게 검증을 수행할 수 있다.

스팁 시간-공간의 균형(Steep time-space tradeoffs)

• 사용자가 비례에 맞지 않은 최적화 시도시 이퀴해시 알고리즘의 규제가 적용 된 메모리 규제가 일어나면서 벌칙이 적용된다.(Memory requirements imposed by the Equihash algorithm are worthwhile as long as attempts to optimize for memory disproportionately penalizes the user.)

유연성(flexibility)

• 알고리즘의 개선과 아키텍처의 변동을 감안하여 시간, 메모리, 작업증명(PoW)의 steepness가 독립적으로 조율이 가능하게 하였으며 따라서 일정한 채굴율을 유지하게 하였다.

제약받는 병렬성(Parallelism-constrained)

• 시스템적으로 병목(bottleneck)을 설치하여 병렬작업증명이 제약을 받게 한다.

필요없는 최적화(Optimization-free)

• 총명한 증명자가 다른 사람을 초과하여 우세를 가지지 않도록 오늘날까지의 최적 알고리즘을 적용하였으며 가능한 최적화를 전수 검증하였다.

생일문제

인원수에 따른 같은 생일의 확률 변화 그래프

생일 문제(birthday problem)는 사람이 임의로 모였을 때 그 중에 생일이 같은 두 명이 존재할 확률을 구하는 문제이다. 생일의 가능한 가짓수는 365개(2월 29일을 고려할 경우 366개)이므로 366명 이상의 사람이 모인다면 비둘기집 원리에 따라 생일이 같은 두 명이 반드시 존재하며, 23명 이상이 모인다면 그 중 두 명이 생일이 같은 확률은 1/2를 넘는다.

생일 문제는 일반적인 인간의 직관과 다른 결과를 가지는 것으로 알려져 있다. 얼핏 생각하기에는 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를 넘어간다.

생일이 같은 두 사람을 찾는 것과 비슷하게, 암호학적 해시 결과가 같은(해시 충돌) 두 입력값을 찾는 것 역시 모든 입력값을 계산하지 않아도 충분히 높은 확률로 해시 충돌을 찾을 수 있다. 이러한 암호 공격을 생일공격(birthday attack)이라고 부른다.

미국 캘리포니아 대학교 버클리 캠퍼스(University of California, Berkeley) 데이비드 바그너(David A. Wagner)는 생일문제를 더 일반화하여 다중 차원형의 k차원을 제시하였다. "n-bit 값의 k 리스트가 주어진 경우, 각 리스트에서 하나의 요소(element)를 찾아 k값의 배타적 논리합이 0이 되게 한다." 바그너는 이의 복잡도를 증명하고 이를 적용한 알고리즘을 만들어냈다. 여기서 시간과 공간의 규제는 엄격하였다.

일반화한 생일문제는 암호와 해시충돌의 연구에 상당히 중요하며 이의 특징은 작업증명 이론에 적합하다.

k차원

이퀴해시 알고리즘

메커니즘의 전제조건

• 비대칭성(asymmetry)
• 가능한 최적화 불가(no possible optimizations)
• 가능한 상각불가(no possible amortizations)
• 독립적으로 조율가능한 매개변수(independently tunable parameters)
• 제약받는 병렬성(constrained parallelism)

기본원리

이퀴해시 발명자 알렉스 비류코프(Alex Biryukov)와 드미트리 호브라토비치(Dmitry Khovratovich)는 미국 캘리포니아 대학교의 데이비드 바그너(David A. Wagner)가 발명한 일반화한 생일문제 알고리즘을 이용하여 이퀴해시 알고리즘을 제출하였다.

알고리즘에는 알고리즘의 run time과 메모리 소요량을 결정하는 세개의 매개변수 - n, k, d가 있다. 공간복잡도가 비례적으로 $2^{k+{\frac {n}{k+1}}}$ 에 접근 할 때 시간의 복잡도 역시 비례적으로 $2^{{\frac {n}{k+1}}+d}$에 접근 된다. 알고리즘은 경상적으로 d = 0 인 조건으로 작동한다.

바그너의 생일 문제: 주어진 n-bit 스트링스의 리스트 L{X_i}에서 확정된 값 {X_ij}를 찾아 아래의 등식이 성립되게 한다.

Xi₁ ⊕ Xi₂ ⊕ · · · ⊕ Xi₂k = 0

이퀴해시 문제:

$i_{1},i_{2},...i_{j}$를 찾아

H(i₁) ⊕ H(i₂) ⊕ · · · ⊕ H(i₂k ) = 0 이 만족되게 하는것이다. 이럴 경우에 H( i₁|| i₂|| · · · i₂k )는 값 d를 얻어

알고리즘에 설정된 규제조건으로 임의의 메모리를 줄이는 스트레인(strain)은 시간의 복잡도를 늘이게 되고 채굴의 효율은 램(RAM) 용량에 의존한다. 암호화폐는 이와 유사한 원리를 기반으로 설계가 되며 통상적으로 memory-orientated 또는 memory-hard로 부른다. 따라서 다수의 경우에 채굴의 효율은 마이너한테 얼마만큼의 램이 보유되어 있느냐에 따라 정해진다.

이퀴해시의 한계

지캐시(Zcash)는 프라이버시에 초점을 두어 널리 알려진 암호화폐이며 언더라잉 알고리즘은 이퀴해시를 적용하였다. 이퀴해시 적용 시 에이식(ASIC) 제어 능력도 중요한 이유의 하나였다. 그러나 지캐시가 2016년에 출시된 뒤 2018년에 비트메인이 이퀴해시 전용 채굴기 앤트마이너 Z9 미니(Antminer Z9 mini) 채굴기 개발에 성공하였다고 선언하였다. 이 사례는 알고리즘의 개발로 에이식을 막는다는것은 어려운 길이라는 것을 다시 한 번 증명하였다.

이퀴해시 알고리즘을 적용한 암호화폐들은 다음과 같다.

• 비트코인골드(Bitcoin Gold)
• 비트코인 프라이빗(Bitcoin Private)
• 코모도(Komodo)
• 젠캐시(ZenCash)
• 지클래식(ZClassic)

참고자료

• "Zcash (ZEC)-Whitepaper", Whitepaper Database
• "Equihash", Wikipedia
• "Birthday problem", Wikipedia
• "Equihash - Mining Algorithms, Coins, Tokens", BitcoinWiki
• 최혜빈 기자, 〈中 비트메인, 이퀴해시(Equihash) 전용 채굴기 출시〉, 《코인리더스》, 2018-05-04
• 명정선 기자, 〈비트메인, 이퀴해시 전용 채굴기 출시…채굴시장 새 시대 열었다〉, 《블록미디어》, 2018-05-04
• 이동언 기자, 〈비트메인, ‘앤트마이너 Z11’ 출시...해시파워 기존모델 3배〉, 《블록타임즈뉴스》, 2019-03-19
• "What is Equihash? | Guide to Equihash Coins", UNHASHED
• 〈生日悖论〉, 《百度百科》
• "How the Equihash Algorithm Could Democratize Zcash Mining", Nasdaq.com
• Beam Privacy, "Speaking of Equihash", Medium, 2018-11-15
• "www.hashcash.org/papers/dagger.html", Hashcash
• EtherDream, 〈怎样的 Hash 算法能对抗硬件破解〉, 《博客园》,2017-02-22
• Alexander Peslyak, "An analysis of Zcash's use of the Equihash proof-of-work scheme", Openwall, 2016-11-18
• David Wagner, "A Generalized Birthday Problem", Semantic Scholar
• Alex Biryukov/Dmitry Khovratovich, "Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem", orbilu.uni.lu
• 〈계산복잡도이론〉, 《네이버 지식백과》
• 雷盈 , 〈Zcash挖矿算法深度解析〉, 《巴比特》, 2016-11-25
• "David A. Wagner", Wikipedia
• "Memory bound function", Wikipedia

같이보기

• 지캐시

이 이퀴해시 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 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 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반