작업증명

거의 모든 고장 허용 시스템은 시스템 내 노드의 절대 다수(예: 절반 이상 또는 3분의 2 이상)가 정직하고 신뢰할 수 있다고 가정합니다. 그러나 개방형 피어 투 피어 네트워크에서는 노드 등록이 필요하지 않으며, 노드가 자유롭게 참여하거나 떠날 수 있습니다. 이로 인해 공격자가 충분한 시빌(Sybil) 노드 또는 소위 허위 노드를 생성하여 시스템의 합의 보장을 무력화할 수 있습니다. 이러한 시빌 공격(Sybil attack)은 2002년 존 두서(John Douceur)에 의해 공식화되었으며, 그는 이를 완화하기 위해 작업 증명(proof of work)이라는 암호학적 구조를 제안했습니다.

작업 증명의 기원

작업 증명을 이해하려면 그 기원을 살펴볼 필요가 있습니다. 오늘날 작업 증명으로 불리는 개념의 최초 제안은 1992년 신시아 드워크(Cynthia Dwork)와 모니 나오르(Moni Naor)에 의해 제시되었습니다. 이들의 목표는 스팸 메일을 방지하는 것이었습니다. 주목할 점은 스팸, 시빌 공격(Sybil attacks), 서비스 거부 공격(DoS)이 본질적으로 네트워크에서 공격자가 일반 사용자에 비해 자신의 영향을 증폭시키는 유사한 문제라는 것입니다. 작업 증명은 이들 세 가지 문제 모두에 대한 방어책으로 활용될 수 있습니다.

드워크와 나오르의 설계에서 이메일 수신자는 발신자가 적당한 양의 계산 작업을 수행했음을 증명하는 작업 증명과 함께 전송된 이메일만 처리하도록 했습니다. 이를 "작업 증명"이라고 부르는 이유입니다. 이 작업 증명을 계산하는 데는 일반적인 컴퓨터에서 몇 초 정도의 시간이 소요됩니다. 이는 일반 사용자에게는 별다른 부담이 되지 않지만, 스팸 발송자가 백만 통의 이메일을 보내려면 동일한 하드웨어를 사용해도 수 주간의 시간이 필요합니다.

작업 증명의 핵심 속성 중 하나는 작업 증명 인스턴스(또는 퍼즐)가 특정 이메일과 수신자에 대해 고유해야 한다는 점입니다. 그렇지 않으면 스팸 발송자는 하나의 작업 증명으로 동일한 수신자에게 여러 메시지를 보내거나, 동일한 메시지를 여러 수신자에게 보낼 수 있게 됩니다. 두 번째 중요한 속성은 수신자에게 최소한의 계산 부담을 주어야 한다는 점입니다. 퍼즐의 해결은 계산이 어렵더라도, 검증은 간단하고 빠르게 이루어져야 합니다.

또한, 드워크와 나오르는 트랩도어(trapdoor) 기능을 가진 함수를 고려했는데, 이는 중앙 권한이 알고 있는 비밀 정보로, 권한이 퍼즐을 작업 없이 해결할 수 있게 하는 구조입니다. 이 트랩도어의 한 가지 응용은 중앙 권한이 메일링 리스트에 게시를 승인할 때 비용을 부담하지 않도록 하는 것입니다. 드워크와 나오르의 제안은 이러한 속성을 충족하는 세 가지 후보 퍼즐로 구성되었으며, 이 연구는 새로운 연구 분야를 여는 계기가 되었습니다. 앞으로 이 주제로 다시 돌아가겠습니다.

해시캐시(Hashcash)

1997년, 당시 사이퍼펑크(cypherpunk) 커뮤니티의 일원이었던 애덤 백(Adam Back)은 매우 유사한 아이디어인 해시캐시(Hashcash)를 독립적으로 발명했습니다. 애덤 백은 박사 후 연구원(postdoctoral researcher)으로 활동하며 암호학을 통해 사회적, 정치적 변화를 추구하던 사이퍼펑크 운동에 동참했습니다. 그는 실용적인 접근 방식을 취해 먼저 해시캐시를 소프트웨어로 공개했고, 5년 후인 2002년에는 인터넷 초안(표준화 문서)과 논문 형태로 발표했습니다.

해시캐시는 드워크와 나오르의 아이디어보다 훨씬 간단합니다. 트랩도어도 없고, 중앙 권한도 필요하지 않으며, 디지털 서명 대신 해시 함수만을 사용합니다. 그 원리는 단순한 개념에 기반합니다. 해시 함수는 실질적으로 무작위 함수처럼 작동하기 때문에, 특정 출력값에 해당하는 입력값을 찾는 유일한 방법은 다양한 입력값을 시도하여 원하는 출력을 생성할 때까지 계속 시도하는 것입니다. 예를 들어, 바이너리 해시 값이 10개의 0으로 시작하는 입력값을 찾으라는 도전 과제를 받았다면, 여러 입력값을 해싱해야 하며, 각 출력이 10개의 0으로 시작할 확률은 (1/2^10), 즉 약 1/1000입니다. 이는 약 1000번의 해시 계산이 필요하다는 의미입니다.

해시캐시라는 이름이 시사하듯, 백은 작업 증명을 일종의 디지털 현금으로 보았습니다. 그의 웹사이트에서 그는 이를 데이비드 차움(David Chaum)의 디지캐시(DigiCash)에 대한 대안으로 제시했습니다. 디지캐시는 은행에서 사용자에게 발급되는 추적 불가능한 디지털 현금 시스템이었습니다. 백은 해시캐시를 디지털 현금처럼 보이게 하기 위해 기술적 설계에서 일부 타협을 하기도 했습니다. 나중에 백은 비트코인이 해시캐시의 직접적인 확장이라는 견해를 표명했습니다. 그러나 해시캐시는 진정한 의미의 현금은 아니었습니다. 이중 지불(double spending)을 방지하는 메커니즘이 없었으며, 해시캐시 토큰은 사용자 간에 교환할 수 없었기 때문입니다.

한편, 학계에서는 작업 증명이 스팸 방지 외에도 다양한 응용 가능성을 지니고 있음을 발견했습니다. 예를 들어, 서비스 거부(DoS) 공격 방지, 웹 분석 데이터의 무결성 보장, 온라인 비밀번호 추측 시도의 속도 제한 등이 이에 포함됩니다. 흥미롭게도 "작업 증명"이라는 용어는 1999년에 마르쿠스 야콥슨(Markus Jakobsson)과 아리 줄스(Ari Juels)의 논문에서 처음 등장했으며, 이 논문은 당시까지의 연구를 잘 정리한 개요를 제공합니다. 주목할 점은 이 연구자들이 해시캐시를 인지하지 못한 상태에서 독립적으로 해시 기반 작업 증명 방식에 접근했다는 것입니다. 이는 에란 개버(Eran Gabber) 외와 줄스 및 브레이너드(Juels and Brainard)의 논문에서 소개되었습니다. 이 문단에서 사용된 용어들 중 다수는 논문이 발표된 후 오랜 시간이 지난 후에야 표준 용어로 자리 잡았습니다.

작업 증명과 디지털 화폐: 딜레마

작업 증명이 스팸 방지라는 원래의 응용에서 성공하지 못했다는 사실은 널리 알려져 있습니다. 그 이유 중 하나는 서로 다른 장치의 퍼즐 해결 속도에 큰 차이가 있다는 점입니다. 이는 스패머가 맞춤형 하드웨어에 소액을 투자하여 스팸 발송 속도를 대폭 증가시킬 수 있음을 의미합니다. 경제학적으로 생산 비용의 비대칭이 존재할 때 자연스러운 대응은 무역, 즉 작업 증명 솔루션의 시장 형성입니다. 그러나 이것은 딜레마를 초래합니다. 이러한 시장이 작동하려면 디지털 화폐가 필요하지만, 작업 증명의 주요 동기는 바로 디지털 화폐의 부재를 해결하기 위한 것이기 때문입니다. 이 문제에 대한 단순한 해결책 중 하나는 해시캐시처럼 퍼즐 솔루션을 화폐로 선언하는 것입니다.

보다 일관된 접근법은 비트코인 이전의 두 가지 에세이에서 찾을 수 있습니다. 이들은 각각 b-머니(b-money)와 비트 골드(bit gold)라는 아이디어를 설명하고 있습니다. 이 제안들은 작업 증명을 통해 화폐를 생성하고, 생성된 화폐에 타임스탬프 서비스를 부여하며, 이후 화폐의 이동을 승인하는 구조를 제시합니다. 그러나 서버나 노드 간에 원장에 대한 의견 차이가 발생하면 이를 명확히 해결하는 방법은 없습니다. 다수결에 따라 결정을 내리는 것이 두 저자의 글에서 암묵적으로 언급된 것으로 보이지만, 시빌 문제(Sybil problem) 때문에 이러한 메커니즘은 게이트키퍼가 네트워크에 대한 접근을 통제하거나, 작업 증명 자체로 시빌 저항(Sybil resistance)을 달성하지 않는 한 매우 안전하지 않습니다.

비트코인은 이 딜레마를 해결하기 위해 독창적인 방식을 도입했습니다. 작업 증명에 기반한 합의 메커니즘은 시빌 문제를 방지하고, 분산된 환경에서도 신뢰 가능한 디지털 화폐를 가능하게 만들었습니다. 이는 퍼즐 솔루션을 단순히 화폐로 선언하는 것 이상의 새로운 패러다임을 제시했습니다.