Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

Contents

HashCash

HashCash는 이메일 스팸과 DOS(Denial of services) 공격을 제한하기 위해서 사용하는 작업증명(proof-of-work) 시스템의 구현 알고리즘이다. 최근 비트코인의 마이닝 알고리즘에 사용되면서 주목받고 있다. POW의 핵심은 문제풀이의 비 대칭성에 있다. 만드는데는 짧은 시간이 걸리지만 문제를 푸는데는 긴 시간이 걸린다. 적절한 시간내에 문제를 풀었다면, 이 사용자는 유효한 사용자라는 것을 증명 할 수 있다. Hash가 대표적인 경우로 한 방향 계산은 쉽지만 역방향 계산은 매우 어렵다. Hashcash는 160비트 SHA-1, 비트코인은 256비트 SHA-2를 사용한다.

 Hash

$ echo -n foobar | sha1sum 
8843d7f92416211de9ebb963ff4ce28125932878 
"foobar"문자열을 SHA-1 hashes를 이용해서 해시했다. 8843d.... 라는 해시값이 나왔는데, "8843d..."의 원래 값이 foobar라는 것을 찾는 것은 매우매우 어렵다. Y값만 가지고 정확한 X(foobar)를 찾으려면 Y가 160비트일 때 최대 2^160번의 연산을 해야 한다.

여기에서 비트코인의 작동방식을 예상해 볼 수 있겠다. 풀기 어려운 문제를 던진 다음에, 가장 먼저 문제를 푼 사람에게 화폐를 준다. 많은 컴퓨터를 동원하는 사람이 문제를 빨리 풀 수 있겠고, GPU 클러스터를 이용해서 채굴을 하는 사람이 생겨나는 이유다.

HashCash는 스팸 필터로도 사용하는데, 메일을 보내기 위해서는 어느 정도의 노력을 해야 하는 반면, 메일을 받는 사람은 약간의 노력으로 클라이언트가 필요한 정도의 노력을 했는지를 계산 할 수 있기 때문에 효율적으로 스팸을 걸러낼 수 있다.

메일 시스템에서 HashCash는 아래와 같이 사용한다.
X-Hashcash: 1:20:1303030600:adam@cypherspace.org::McMybZIhxKXu57jd:ckvi
  • ver: Hashcash 포맷 버전, 1
  • bit : 해시코드에서 연속된 0이 나올 비트의 크기
  • date : 메시지를 보낸시간
  • resource : IP주소나 Email주소와 같은 목적지 주소
  • ext: 옵션. 버전 1에서는 무시한다.
  • rand: 랜덤 스트링, base-64 인코딩 포맷이다.
  • counter: 바이너리 카운터 base-64 포멧이다.
스팸필터에서의 Hashcash 예를 살펴보자. 스팸 필터링에 걸리지 않기 위해서 Email은 헤더에 아래와 같은 Hashcash 헤더를 추가한다.

 Email에서의 Hashcash
  • 보내는 측은 랜덤 값을 포함한 헤더를 준비한다. 수신측은 랜덤값을 저장하는데, 해시를 반복해서 사용하는 것을 막기 위해서 사용한다.
  • 송신측은 카운터를 포함해서 해시 값을 만들어 낸다. 카운터가 변할 때 마다 이 해시 값은 계속 변할 거다.
  • 이렇게 카운터를 바꿔가면서 연산을 하다보면 해시값의 처음 20비트가 0이라는 조건을 만족 할 것이다. 그럼 이 카운터 값을 설정해서 메일을 전송한다.
  • Hash 함수의 특성상, 수신측은 간단하게 처음 20비트가 0이라는 것을 확인 할 수 있다. 이게 확인되면, 수신측은 스팸이 아니라고 판단 하게 된다.
20비트가 0인 해시를 만들기 위해서 송신층은 평균 100(2^20 == 1048576)만번의 연산을 해야 하는데, 대량으로 메일을 보내야 하는 스패머로써는 상당한 부담이 될 것이다. 스팸메일은 돈 벌려고 하는데, 더 많은 돈을 써야 할 수 있기 때문이다.

취업시장에서 학력을 보는 이유와 비슷하다고 보면 된다. 점수를 올리려고 노력했던 사람은 능력 좋은(최소한 맡겨진 일은 열심히 하는) 사람일 확률이 높을 것이다.

HashCash의 특징은 아래의 3가지로 요약 할 수 있다.
  • 노력이 신뢰다.
  • 노력에 비해서 검증은 간편하다.
  • 제 3자의 개입없이 검증 할 수 있다.

장점과 단점

제 3자의 개입이 없다. 어떤 시스템이든지 제 3자가 개입하면 신뢰를 보증하기 위한 돈이 들어가게 된다. HashCash는 중앙에 있는 3자가 아닌 클라이언트로 분산이 되므로 별도의 비용을 지불할 필요가 없다.

Hashcash를 만들기 위해서, 클라이언트는 자원을 소비해야 한다. 일반적인 PC에서는 무시할 수 있겠으나, 임베디드 장비에서는 문제가 될 수 있다. 따라서 HashCash 응용 개발자는 장비의 성능을 고려해서 문제의 난이도를 조정해야 한다. Hashcash의 bit를 작게 하는 것으로 난이도를 조절할 수 있는데 난이도가 너무 높을 경우에는 장비에 부담이 될 수 있고, 반면 난이도가 너무 낮을 경우에는 공격에 취약해 질 수 있다.

컴퓨터는 점점 빨라질 것이다. 따라서 Hashcash의 bit는 점점 더 커져야 할 것이다. 따라서 돈이 충분하지 않다면, Hashcash 기반 시스템에 참여가 어려워진다. 개발도상국은 아예 시스템에서 배제될 수도 있다.

예제 코드

Hashcash의 기본원리를 구현한 간단한 프로그램이다.
package main

import (
    "crypto/sha256"
    "encoding/binary"
    "fmt"
    "time"
)

func main() {
    var (
        count int
        str   string
    )
    h := sha256.New()
    t := time.Now().Unix()
    str = fmt.Sprintf("%d:Hello World: %%d", t)
    for {
        count++
        str := fmt.Sprintf(str, count)
        h.Write([]byte(str))
        hbyte := h.Sum(nil)
        val := binary.BigEndian.Uint32(hbyte) >> 12
        if val == 0 {
            break
        }
    }
    fmt.Println("계산에 걸린 시간", count)
}
		
"Hello World:"뒤에 카운트를 붙여가면서, 처음 20bit가 0인 값이 나올 때까지 연산을 수행한다. "Hello World:"앞에는 현재 유닉스 시간을 추가해서, 실행 할 때마다 다른 문제를 풀도록 했다.

응용

노력(일을 제대로 했는지) 필터링을 위한 영역에서 활용 할 수 있다.
  • 비트코인 마이닝 : 마이닝은 결국 노력을 기준으로 필터링을 하겠다는 거다.
  • 스팸 필터
  • 블로그 : 댓글 폭탄을 막기 위해서 사용 할 수 있다. 스팸 필터와 비슷하다.
  • Email 클라이언트
  • Email Postmark

비트코인

Hashcash는 악성유저를 필터링하기 위한 목적으로 만들었지만, 비트코인에서는 비트코인 마이닝을 위해서 사용한다. 비트코인 마이닝은 현실세계에서의 "금"채굴과 원리적으로 동일하다. 채굴기계와 지질학 대신에, CPU(GPU)를 사용한다는 차이가 있을 뿐이다. 난이도 조절은 연속된 0의 비트 크기로 설정하며, 지금은 256비트 중 처음 72 비트가 0이어야 하도록 요구사항을 강화했다. 대략 "4722366482869645213696" 정도가 되는 엄청난 크기다. GPU 클러스터를 동원해야 하는 이유다.

참고