Hashcash

Dwork와 Naor는 1992년 스팸에 계산 가격을 부과하는 방법을 설명했습니다. Back은 1997년 3월 부분 hash preimage 구현을 공개했고 2002년 무료 네트워크 자원 남용 대책으로 Hashcash를 정식화했습니다.

v1 스탬프는 version, bits, date, resource, extension, random, counter를 담습니다: `1:bits:date:resource:ext:rand:counter`. 발신자는 임계값까지 counter를 바꾸고 수신자는 구문과 정책도 확인합니다.

필요한 수의 0 bit로 시작하는 SHA-1 digest의 입력을 찾습니다. 이는 한 hash의 성질을 노리는 부분 preimage이며, 같은 hash를 가진 서로 다른 두 메시지를 찾는 충돌 문제가 아닙니다.

이상적 hash에서 한 번의 성공 확률은 2^-b, 기대 시도 수는 2^b입니다. 완료 시간의 편차는 크지만 검증은 hash 한 번과 임계값 비교뿐입니다. 이 비용 비대칭이 핵심입니다.

resource는 작업을 수신자나 서비스에, date는 유효 기간에 묶습니다. 결합이 없으면 전용되고 사용 기록이나 메시지 결합이 없으면 replay됩니다. Hashcash에는 전역 이중사용 장부가 없습니다.

bit 수는 보편적 보안 상수가 아닙니다. 서비스는 장치 속도, 공격 비용, 양, 허용 지연과 유효 기간을 고려합니다. hardware 성장과 전문화는 과거 임계값을 약화합니다.

계산 비용은 정당 사용자와 botnet, 도난 전력, 강력한 발신자를 구별하지 못합니다. 느린 장치를 불리하게 하고 전달이나 privacy를 보장하지 않으며 rate limit, 평판, filter, 감시도 대체하지 않습니다.

원래 스탬프는 특정 용도로 소비되며 양도 가능한 동전이 아닙니다. Finney의 RPOW는 Hashcash를 새 token으로 교환해 순차 재사용했지만 이중사용 통제는 증명 가능한 hardware의 server에 의존했습니다.

Bitcoin whitepaper는 Back 논문을 명시적으로 인용하고 target 아래 hash 탐색과 비싼 작업의 저렴한 검증을 계승합니다. 그렇다고 Hashcash에 bitcoin 화폐, blockchain, 분산 consensus가 있었던 것은 아닙니다.

Bitcoin은 block header를 double SHA-256하고 공통 후보 chain을 경쟁시키며 target을 조정하고 누적 작업으로 역사를 정렬합니다. 보상, 수수료, transaction 검증과 node 규칙이 이를 공개 consensus 구성요소로 만듭니다. Cynthia Dwork and Moni Naor — Pricing via Processing or Combatting Junk Mail · Adam Back — Hashcash original implementation and announcement · Adam Back — Hashcash: A Denial of Service Counter-Measure · Hashcash — Version 1 stamp format and command documentation · Hashcash — FAQ and operational limits · Markus Jakobsson and Ari Juels — Proofs of Work and Bread Pudding Protocols · Hal Finney — RPOW: Reusable Proofs of Work · Satoshi Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System · Bitcoin Core — Proof-of-work target and difficulty validation