작업 증명 시스템

3. 작동 방식

작업 증명(Proof-of-work^eng, PoW) 개념은 스팸 및 서비스 거부 공격 방지에 대한 초기 연구에서 비롯됐다. PoW의 초기 구현 중 하나는 영국의 암호학자 아담 백(Adam Back)이 1997년에 만든 해시캐시(Hashcash)이다.^[8] 해시캐시는 이메일 발신자가 소량의 계산 작업을 수행하도록 요구하는 스팸 방지 메커니즘으로 설계되었다. 이를 통해 발신자는 이메일을 보내기 전에 자원(CPU 시간)을 사용했음을 증명하게 된다. 이 작업은 일반 사용자에게는 사소한 부담이지만, 대량의 메시지를 보내려는 스팸 발송자에게는 상당한 비용을 부과하는 효과를 냈다.

해시캐시 시스템은 특정 기준을 충족하는 해시 값을 찾는 개념에 기반했다. 이 과정에는 계산 노력이 필요하며, 이것이 바로 '작업 증명'의 역할을 했다. 즉, 대량의 이메일을 보내는 데 드는 계산 비용을 높여 스팸을 줄이려는 아이디어였다.

해시캐시에서 사용된 대표적인 방식은 부분 해시 반전(partial hash inversion)을 통해 계산이 완료되었음을 증명하는 방식이다. 예를 들어, 다음 헤더는 2038년 1월 19일에 `calvin@comics.net`으로 메시지를 보내기 위해 약 2⁵²번의 해시 계산을 수행했음을 나타낸다.



X-Hashcash: 1:52:380119:calvin@comics.net:::9B760005E92F0DAE



이 증명은 해당 스탬프의 SHA-1 해시값(헤더 이름 `X-Hashcash:`와 그 뒤에 오는 콜론 및 공백을 제외한 부분)이 52개의 이진수 0(즉, 13개의 16진수 0)으로 시작하는지 확인하는 단일 계산으로 검증된다.



0000000000000756af69e2ffbdb930261873cd71



작업 증명 시스템이 스팸 문제와 같은 특정 서비스 거부 문제를 실제로 효과적으로 해결할 수 있는지에 대해서는 논란이 있었다.^[9][10] 이 시스템은 스팸 발송자에게는 눈에 띄는 비용 부담을 주어야 하지만, 일반 사용자가 메시지를 보내는 데 불편함을 주어서는 안 된다. 다시 말해, 일반 사용자는 이메일을 보낼 때 어려움을 겪지 않아야 하지만, 스팸 발송자는 많은 이메일을 한꺼번에 보내기 위해 상당한 컴퓨팅 성능을 소모해야 한다. 작업 증명 시스템은 해시캐시(Hashcash)와 유사한 시스템을 사용하는 비트코인과 같은 더 복잡한 암호화 시스템에서 활용되었다.^[9]

3. 1. 질문-응답 방식

3. 2. 해결책-검증 방식

• CPU 바운드: 계산 속도가 CPU의 성능에 크게 의존한다. 이는 무어의 법칙에 따라 시간이 지남에 따라 변동하며, 고성능 서버와 저성능 휴대용 기기 간의 성능 차이도 크다.^[11]
• 메모리 바운드: 계산 속도가 주 메모리 접근 속도(대기 시간 또는 대역폭)에 의해 제한된다. 이 방식은 하드웨어 발전에 상대적으로 덜 민감할 것으로 예상된다.^{[19][20][21][22]}
• 네트워크 바운드: 클라이언트가 직접 수행하는 계산량은 적지만, 최종 서비스 제공자에게 요청하기 전에 원격 서버에서 특정 토큰을 수집해야 한다. 이 과정에서 발생하는 네트워크 대기 시간 때문에 지연이 발생한다.^[24]

4. 유형

작업 증명 프로토콜은 크게 두 가지 방식으로 나눌 수 있다.

• 질문-응답 (Challenge-Response^eng) 프로토콜: 이 방식은 요청자(클라이언트)와 제공자(서버) 사이에 직접적인 상호작용이 있다고 가정한다. 서버는 특정 조건을 만족하는 질문을 생성하고, 클라이언트는 해당 질문에 대한 답을 찾아 서버에게 보내 검증받는다. 서버가 실시간으로 질문을 만들기 때문에, 서버의 현재 부하 상태에 맞춰 문제의 난이도를 조절할 수 있다는 장점이 있다. 만약 문제에 대한 해답이 미리 알려져 있거나, 탐색해야 할 범위가 제한적이라면 클라이언트가 수행해야 할 작업량은 줄어들 수 있다.

• 해결책-검증 (Solution-Verification^eng) 프로토콜: 이 방식은 질문-응답 방식과 달리 클라이언트와 서버 간의 직접적인 상호작용을 가정하지 않는다. 따라서 요청자(클라이언트)는 해답을 찾기 전에 스스로 풀어야 할 문제를 설정해야 하며, 제공자(서버)는 클라이언트가 선택한 문제와 찾아낸 해답 모두를 검증해야 한다. 해시캐시(Hashcash)와 같이 정해진 답 없이 확률적으로 반복 계산하여 해답을 찾는 방식이 이 방식에 해당한다.

• CPU 바운드: 계산 속도가 프로세서 성능에 크게 의존하는 방식이다.^[11][39]
• 메모리 바운드: 계산 속도가 주 메모리의 접근 속도(대기 시간 또는 대역폭)에 의해 제한되는 방식이다.^{[19][20][21][22][47][48][49][50]}
• 네트워크 바운드: 클라이언트가 직접 계산하는 대신, 원격 서버에서 필요한 정보를 수집하는 데 시간이 소요되는 방식이다.^[24][52]

4. 1. CPU 바운드

4. 2. 메모리 바운드

4. 3. 네트워크 바운드

5. 바로 가기 계산

일부 작업 증명(PoW) 시스템은 일반적으로 개인 키와 같은 비밀 정보를 알고 있는 참가자가 더 적은 비용으로 작업 증명을 생성할 수 있도록 하는 바로 가기 계산 기능을 제공한다. 이는 예를 들어 메일링 리스트 운영자가 각 수신자에게 스탬프를 생성할 때 발생하는 높은 비용 부담을 줄여줄 수 있다. 이러한 바로 가기 기능이 필요한지는 해당 작업 증명 시스템이 사용되는 구체적인 상황에 따라 달라질 수 있다.

6. 작업 증명 함수 목록

• 큰 소수를 법으로 하는 정수 제곱근^[40]
• 약화된 피아트-샤미르 서명^[40]
• 폴라드에 의해 해독된 Ong–Schnorr–Shamir 서명^[40]
• 부분 해시 역변환^[41][42] (해시캐시와 관련)^[43]
• 해시 수열^[44]
• 퍼즐^[45]
• 디피-헬먼 기반 퍼즐^[46]
• Moderate^[47]
• Mbound^[48]
• Hokkaido^[49]
• Cuckoo Cycle^[50]
• 머클 트리 기반^[51]
• Guided tour puzzle protocol^[52]

7. 유용한 작업 증명 (PoUW)

많은 작업 증명(PoW) 시스템은 클라이언트에게 해시 함수의 역산과 같이 실질적인 의미가 없는 계산 작업을 요구한다. 이는 클라이언트 컴퓨터를 작동시키는 데 필요한 전기와 같은 막대한 자원이 낭비된다는 문제점을 안고 있다. 이러한 자원 손실을 줄이기 위해, 수행된 작업 자체가 실제로 유용한 가치를 지니는 유용한 작업 증명(Proof-of-Useful-Work, PoUW) 시스템이 일부 알트코인에 도입되었다. 예를 들어, 프라임코인(Primecoin)은 소수 정리 등 수학 연구에 기여할 수 있는 특정 종류의 미지의 소수를 찾는 작업을 클라이언트에게 요구한다.

2022년 IACR의 Crypto 2022 학회에서는 PoUW 기반의 합의 메커니즘을 사용하는 블록체인 프로토콜인 'Ofelimos'를 소개하는 논문이 발표되었다. Ofelimos는 거래 검증을 위해 복잡하지만 본질적으로 쓸모없는 퍼즐을 푸는 대신, 분산된 최적화 문제 해결을 통해 합의에 도달하는 방식을 사용한다. 이 프로토콜은 PoUW 구성 요소로 지역 탐색 알고리즘인 이중 병렬 지역 탐색(DPLS)을 기반으로 하며, 논문에서는 부울 문제를 해결하는 지역 탐색 알고리즘인 WalkSAT의 변형을 구현한 예시를 제시했다.^[25]

8. 비트코인과 작업 증명

2009년 등장한 비트코인 네트워크는 해시캐시 작업 증명 방식을 기반으로 하는 디지털 통화이다. 이는 할 피니의 RPoW와 유사점을 가지지만, 비트코인은 RPoW가 사용했던 하드웨어 기반의 신뢰 컴퓨팅 기능 대신, 코인 이체 추적을 위한 분산형 P2P 프로토콜을 통해 이중 지불 문제를 방지한다. 비트코인은 컴퓨팅으로 보호되기 때문에 더 높은 신뢰성을 갖는다.

비트코인은 개별 채굴자들이 해시캐시 작업 증명 함수를 사용하여 "채굴"하며, P2P 비트코인 네트워크의 분산된 노드들이 이 과정을 검증한다. 난이도는 주기적으로 조정되어 블록 생성 시간을 목표 시간으로 유지한다.

8. 1. 에너지 소비 문제

8. 2. 채굴 풀과 ASIC

8. 3. 환경 문제와 규제

9. 재사용 가능한 작업 증명 (RPoW)

컴퓨터 과학자 할 피니는 작업 증명(Proof-of-work, PoW) 개념을 기반으로 재사용 가능한 작업 증명(Reusable Proof-of-work, RPOW) 시스템을 만들었다.^[53] 작업 증명을 실용적인 목적으로 재사용하려는 아이디어는 1999년에 이미 제시된 바 있다. 할 피니는 RPOW를 토큰 화폐(명목 화폐)로 만드는 것을 목표로 삼았다. 금화의 가치가 제조에 필요한 금의 가치에 의해 뒷받침되는 것처럼, RPOW 토큰의 가치는 POW 토큰을 '채굴'하는 데 필요한 현실 세계 자원의 가치에 의해 보장된다는 개념이다. 할 피니의 RPOW 버전에서 POW 토큰은 해시캐시의 일부이다.

웹사이트는 서비스 제공의 대가로 POW 토큰을 요구할 수 있다. 사용자에게 POW 토큰을 요구함으로써 서비스의 무의미하거나 과도한 사용을 억제하고, 인터넷 대역폭, 계산 능력, 디스크 공간, 전력, 관리 비용 등 서비스 운영에 필요한 자원을 절약할 수 있다.

할 피니의 RPOW 시스템은 토큰을 생성하는 데 필요한 작업을 반복하지 않고도 토큰을 교환할 수 있다는 점에서 기존 POW 시스템과 차별화된다. 사용자가 웹사이트에서 POW 토큰을 사용하면, 해당 사이트 관리자는 사용된 POW 토큰을 새로운 미사용 RPOW 토큰으로 교환할 수 있다. 이렇게 얻은 RPOW 토큰은 다시 RPOW를 허용하는 다른 제삼자 웹사이트에서 사용할 수 있다. 이는 POW 토큰 생성에 필요한 자원을 절약하는 효과를 가져온다. RPOW 토큰의 위조는 원격 증명(remote attestation^eng) 기술을 통해 방지된다. 사용된 토큰을 새 토큰으로 교환해주는 RPOW 서버는 원격 증명을 이용하여 사용자가 RPOW 서버에서 실행되는 소프트웨어의 무결성을 검증할 수 있도록 한다. 할 피니는 RPOW 소프트웨어의 소스 코드를 BSD 라이선스와 유사한 조건으로 공개했기 때문에, 충분한 지식을 가진 프로그래머는 코드를 검토하여 RPOW 서버가 정당한 교환 외에는 새로운 토큰을 발행하지 않는다는 것을 확인할 수 있었다.

2009년까지 할 피니의 시스템은 구현된 유일한 RPOW 시스템이었지만, 경제적으로 중요한 용도로 널리 사용되지는 못했다. 2009년에 등장한 비트코인은 작업 증명 기반의 암호화폐로, 할 피니의 RPOW처럼 해시캐시의 POW를 기반으로 한다. 그러나 비트코인은 RPOW에서 사용된 신뢰할 수 있는 플랫폼 모듈(TPM)과 같은 하드웨어 기반 신뢰 컴퓨팅 기능 대신, P2P 네트워크를 통한 분산 원장 기술로 이중 지불 문제를 방지한다. RPOW는 신뢰할 수 있는 플랫폼 모듈(TPM) 하드웨어에 저장된 개인 키와 이를 발급한 제조업체에 의존하므로, 해당 키가 유출되거나 TPM 칩 자체가 해킹될 경우 보안이 취약해질 수 있다는 한계가 있었다. 반면 비트코인은 분산된 네트워크 참여자들의 계산 능력에 의해 보안이 유지되므로 더 높은 신뢰성을 확보할 수 있었다. 비트코인은 개별 채굴자들이 해시캐시의 작업 증명 방식을 통해 "채굴"하며, P2P 비트코인 네트워크 내의 분산된 노드들에 의해 거래 내역이 검증된다.

10. 관련 항목

• 비트코인
• 암호화폐
• 비트메시지
• 지분 증명

참조

_[1] 논문 A Cross-Stack Approach Towards Defending Against Cryptojacking 2020-07-01
_[2] 웹사이트 RPOW - Reusable Proofs of Work https://nakamotoinst[...] 2024-01-17
_[3] 웹사이트 What Is Proof of Work (PoW) in Blockchain? https://www.investop[...] 2024-01-17
_[4] 웹사이트 Cryptocurrencies and blockchain https://www.europarl[...] 2020-10-29
_[5] 웹사이트 Proof of Work Explained in Simple Terms - The Chain Bulletin https://chainbulleti[...] 2023-04-01
_[6] 뉴스 The Only Crypto Story You Need, by Matt Levine https://www.bloomber[...] 2023-04-01
_[7] 뉴스 Analysis {{!}} Bye-Bye, Miners! How Ethereum's Big Change Will Work https://www.washingt[...] 2021-11-30
_[8] 웹사이트 Hashcash - A Denial of Service Counter-Measure http://www.hashcash.[...] 2002-08
_[9] 논문 Proof-of-work proves not to work 2004-05
_[10] 웹사이트 Proof of Work can work - Fifth Workshop on the Economics of Information Security http://www.econinfos[...] 2006-06
_[11] 웹사이트 How powerful was the Apollo 11 computer? http://wayback.vefsa[...]
_[12] 서적 Advances in Cryptology — CRYPTO' 92 Springer
_[13] 웹사이트 HashCash http://hashcash.org/
_[14] 논문 Curbing junk e-mail via secure classification https://www.research[...]
_[15] 논문 Defending against denial-of-service attacks with puzzle auctions http://cs.unc.edu/~r[...] 2003-05
_[16] 서적 Financial Cryptography
_[17] 논문 Client puzzles: A cryptographic defense against connection depletion attacks
_[18] 논문 New client puzzle outsourcing techniques for DoS resistance http://www.cs.utexas[...]
_[19] 논문 Moderately hard, memory-bound functions https://www.research[...]
_[20] 서적 Advances in Cryptology - CRYPTO 2003 Springer
_[21] 논문 Exponential memory-bound functions for proof of work protocols http://eprint.iacr.o[...]
_[22] 서적 Financial Cryptography and Data Security Springer
_[23] 논문 An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees http://eprint.iacr.o[...]
_[24] 서적 2009 Annual Computer Security Applications Conference 2009-12
_[25] 웹사이트 Combinatorial Optimization via Proof-of-Useful-Work https://crypto.iacr.[...]
_[26] 웹사이트 Cambridge Bitcoin Electricity Consumption Index (CBECI) https://www.cbeci.or[...]
_[27] 웹사이트 Cambridge Bitcoin Electricity Consumption Index https://www.cbeci.or[...] Cambridge Center For Alternative Finance
_[28] 뉴스 Short-Term Fixes To Avert "51% Attack" https://blogs.wsj.co[...] Wall Street Journal 2014-06-16
_[29] 웹사이트 Overview of the Bitcoin mining pools https://blockchain.i[...]
_[30] 웹사이트 What is an ASIC miner https://www.digitalt[...]
_[31] 웹사이트 The State of Cryptocurrency Mining https://blog.sia.tec[...] 2018-05-13
_[32] 웹사이트 tevador/RandomX: Proof of work algorithm based on random code execution https://github.com/t[...]
_[33] 논문 Cryptocurrency Value and 51% Attacks: Evidence from Event Studies https://jai.pm-resea[...]
_[34] 논문 The economic dependency of bitcoin security 2021-10-21
_[35] 웹사이트 Ban proof of work crypto mining to save energy, EU regulator says https://www.euronews[...] 2022-01-19
_[36] 웹사이트 New York governor signs first-of-its-kind law cracking down on bitcoin mining — here's everything that's in it https://www.cnbc.com[...] 2022-12-04
_[37] 저널 Proof-of-work proves not to work 2004-05-01
_[38] 웹사이트 Proof of Work can work - Fifth Workshop on the Economics of Information Security http://www.econinfos[...] 2006-06-01
_[39] 웹사이트 How powerful was the Apollo 11 computer? http://downloadsquad[...]
_[40] 저널 Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology http://www.wisdom.we[...] Springer
_[41] 웹사이트 HashCash http://hashcash.org
_[42] 저널 Curbing junk e-mail via secure classification
_[43] 저널 Defending against denial-of-service attacks with puzzle auctions http://cs.unc.edu/~r[...] 2003-05-01
_[44] 저널 Auditable metering with lightweight security
_[45] 저널 Client puzzles: A cryptographic defense against connection depletion attacks
_[46] 저널 New client puzzle outsourcing techniques for DoS resistance
_[47] 저널 Moderately hard, memory-bound functions
_[48] 저널 On memory-bound functions for fighting spam Springer
_[49] 웹사이트 Exponential memory-bound functions for proof of work protocols http://eprint.iacr.o[...]
_[50] 웹사이트 Cuckoo Cycle; a memory bound graph-theoretic proof-of-work https://eprint.iacr.[...] Springer
_[51] 웹사이트 An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees http://eprint.iacr.o[...]
_[52] 저널 A Guided Tour Puzzle for Denial of Service Prevention 2009-12-01
_[53] 웹사이트 Reusable Proofs of Work http://rpow.net/
_[54] 저널 Proofs of Work and Bread Pudding Protocols http://www.emc.com/e[...] Kluwer Academic Publishers
_[55] 저널 Pricing via Processing, Or, Combatting Junk Mail, Advances in Cryptology http://www.wisdom.we[...] Springer
_[56] 웹인용 HashCash http://hashcash.org
_[57] 저널 Curbing junk e-mail via secure classification
_[58] 저널 Defending against denial-of-service attacks with puzzle auctions http://cs.unc.edu/~r[...] 2018-05-11
_[59] 저널 Auditable metering with lightweight security
_[60] 저널 Client puzzles: A cryptographic defense against connection depletion attacks
_[61] 저널 New client puzzle outsourcing techniques for DoS resistance
_[62] 저널 Moderately hard, memory-bound functions
_[63] 저널 On memory-bound functions for fighting spam Springer
_[64] 웹사이트 Exponential memory-bound functions for proof of work protocols http://eprint.iacr.o[...]
_[65] 웹사이트 Cuckoo Cycle; a memory bound graph-theoretic proof-of-work https://eprint.iacr.[...] Springer
_[66] 웹사이트 An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees http://eprint.iacr.o[...]
_[67] 저널 A Guided Tour Puzzle for Denial of Service Prevention 2009-12-01