이퀴해시

이퀴해시(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의 전용개발이 종합적으로 투입원가-개선효과를 평가할 때 경제적이지 못하게 한다. 따라서 이는 객관적으로 ASIC에 대한 저애특징을 갖게 된다. 여기서 가정하는 하나의 전제조건은 시중판매되는 하드웨어들이 비교적 넓은 메모리 대역폭을 보유하고 있어야 한다.

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

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

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

발명배경

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

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

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

만약 비트메인의 보유해시속도가 51%에 도달하거나 초과하면 소위 말하는 51%공격이 이루어질 수 있는 가능성이 형성되며 트랜잭션이 반대로 이루어지거나 이중지불이 이루어지는 것을 포함한 네트워크의 붕괴를 일으킬 수 있다.

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

이퀴해시 - 상용컴퓨터와 주문제작 컴퓨터간의 채굴경쟁력 차이를 해소하고 간단한 작업증명 검증을 목표로 Memory-Hard방식의 해결방안을 모색한다. 주지하다싶이 알고리즘은 이의 시간복잡도와 공간복잡도로 측정을 할 수 있다.

기본원리

특징

Progress-free process

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

높은 AT원가(Large AT cost)

• 요청하는 작업증명의 컴퓨팅이 메모리집약으로 최적화된 ASIC 칩이 메모리영역에서 원가경쟁력을 해소시켰다. 여기서 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)

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

생일문제

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

생일 문제(The generalized 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)

기본원리

이퀴해시 발명자 비류코프와 호프라비토비치는 캘리포니아대학의 데이비드 바그너가 발명한 일반화한 생일문제 알고리즘을 이용하여 이퀴해시 알고리즘을 제출하였다.

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

이퀴해시한계

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

이퀴해시 알고리즘을 적용 한 암호화폐들은

• 비트코인골드
• Bitcoin Private
• Komodo
• ZenCash
• ZClassic

등이 있다.

참고자료

• "Zcash (ZEC)-Whitepaper", Whitepaper Database
• "Equihash", Wikipedia
• "Birthday problem", Wikipedia
• "Equihash - Mining Algorithms, Coins, Tokens", BitcoinWiki
• "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
• 최혜빈 기자, 〈中 비트메인, 이퀴해시(Equihash) 전용 채굴기 출시〉, 《코인리더스》, 2018-05-04
• 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) 매칭 알고리즘 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반