[블록체인] 해시함수 이해 2 - 특성 1 - 충돌이 거의 발생하지 않는다.

in kr •  last year

암호화폐 기술에 대한 내용에 항상 등장하는 것 중 하나가 해시함수(Hash Function)죠.
해시함수는 무엇일까요?

그 두번째 글로 "특성 1 : 충돌이 잘 발생하지 않는다"입니다.

충돌 저항성이라고 하는데 영어로는 Collision-registance라고 하죠. 충돌에 저항력이 있다.

이전 글은 아래 링트에서 보실 수 있습니다.
[블록체인] 해시함수 이해 1 - 해시함수란?

여기서 충돌(collision)은 해시함수의 결과 값이 동일하다는 말입니다.
hash function image (3).png

이전 해시함수란? 에서 해시 함수는

어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수

라고 간단히 이야기했습니다.

SHA256 해시는 결과가 256 bits입니다.
입력으로 사용할 수 있는 값은 무제한이고 결과는 256bits로 한정되어 있다는 말이죠.

그렇다면 2^256 + 1개의 다른 입력을 해시함수에 입력을 하면 100% 같은 결과를 갖게 됩니다.

2^130 + 1 개의 다른 입력을 시도하면 결과 중에 같은 값을 갖게될 확율이 99.8%라고 합니다.

특성 1 : 충돌이 거의 발생하지 않는다

정해진 길이의 결과를 출력하는 해시함수의 특성상 무한대의 입력을 사용할 수 있다면 충돌되는 값을 찾는 것은 100% 가능합니다.
그래서 충돌이 없다(Collision free)라고 말하지 않는 것입니다.
대신 충돌되는 경우를 찾기가 힘들다라고 말하는 이유죠.

실제로 충돌이 되는 값을 찾기위해서는 정말, 정말, 정말..... 오랜 시간이 걸립니다.
인류가 지금까지 만들었던 모든 컴퓨터를 다 동원해서 우주의 시작부터 지금까지 시도를 해도 못 찾을 거라고 합니다.
그건 2^256이라는 숫자가 얼마나 큰 숫자인지 보면 좀 더 이해가 됩니다.

2^256이라는 숫자가 얼마나 큰 숫자인가

아래 숫자를 한번 보세요.
hash function image (2).png
2^256이라는 값은 약 40억이라는 숫자를 8번 곱한 것과 같습니다.
그럼 이 숫자가 실제로 어떤 느낌인지 한번 볼까요?
2018-03-28_23-19-57.jpg
(출처 : How secure is 256 bit security?)

위 그림에 있는 숫자들이 의미하는 것을 하나씩 보겠습니다.

1. 초당 40억개의 해시를 계산하는 GPU

이런 GPU가 있다고 가정을 하는 것입니다. 이런 GPU를 장착한 컴퓨터가 있다는 가정입니다.

2. 이런 컴퓨터를 40억개 보유한 회사

실제 구글도 수백만개의 컴퓨터 정도가 있을테고 실제로 GPU 성능은 우리의 가정보다는 낮습니다.
이런 회사를 수퍼 킬로 구글이라고 부릅니다.

3. 이런 회사가 지구에 40억개

지구 전체 인구가 약 73억 정도입니다. 그중 절반이 수퍼 킬로 구글을 하나씩 소유하고 있습니다.

4. 이런 지구가 은하계에 40억개

은하계에 별의 갯수가 대략 1000억개에서 4000억개 있다고 하는데요. 그중에서 100개 중 하나가 지구와 같다는 가정입니다.

5. 이런 은하계가 40억개

이런 은하계가 온 우주에 40억개 있다는 가정입니다.
여기까지만 해도 충분히 얼마나 큰지 이해가 가네요.
그래도 끝까지 한번 가 보죠.

6. 40억 초는....

40억초는 대략 126.8년이라고 하네요.

7. 126년 X 40억은?

대략 5천70억년이라고 하는데요. 현 우주의 나이의 37배라고 합니다.

8. 여기까지 계산을 했더라도 아직 40억분의 1

맞습니다. 이제 40억분의 1을 계산한거에요...

자 이정도면 충돌이 없다라고 말해도 되는 거 아닌가요?
이제 똑같은 계산 결과를 만들어내는 입력 값을 찾는 것은 불가능하다는 것이 이해가 되시나요?=
바꿔 말하면

해시가 같다는 것은 입력값도 같다는 것이다.

라고 할 수 있죠.

그럼 이 해시로 뭘 할 수 있을까요?

데이터 요약본(Message Digest)

Alice가 중요한 데이터가 담긴 10 기가짜리 파일을 구글드라이브에 올렸습니다. 그리고 Bob에게 그 파일을 다운받으라고 알려줍니다.
그런데, Bob이 다운받은 파일은 정말 Alice가 올린 파일과 1 bit도 다르지 않은 동일한 파일일까요?
이를 확인하는 방법은 Bob이 자기가 받은 파일을 구글 드라이브 어딘가 다시 올리고 Alice가 받아서 원본과 비교해 보는 것입니다.
그런데, 만일 Bob이 아직도 전화선으로 인터넷이 연결되어 있는 곳에 살고 있다면요.
아마 다운로드 받는데는 10시간 정도 걸렸겠지만 다시 올리는데는 10 일이 걸릴지도 모르겠습니다.
이때 해시를 이용하합니다.
Alice가 자기가 업로드한 파일의 SHA256 해시를 계산해서 Bob에게 줍니다.
Bob은 다운로드 받은 파일의 SHA256 해시를 구해서 Alice가 준 것과 비교합니다.
10기가의 파일을 다시 올리는 대신에 요약된 256 bits로 비교가 가능해 집니다.
해시가 같다는 것은 입력된 값도 같다는 것이니까요.

데이터 무결성 증명

Alice가 업로드한 파일은 실제로 아주 중요한 데이터를 가지고 있습니다. 단 한글자라도 변경이 되면 안되는 중요한 데이터죠.
Bob이 나쁜 마음을 품고 데이터를 살짝 변경해서 회사의 경영자인 James에게 전달할 수도 있죠.
Bob을 못 믿는 James는 자기가 받은 파일이 Alice가 준 것과 동일한 지 확인해야합니다.
방법은 Alice한테 연락을 해서 파일을 다시 올리면 직접 다운받아서 Bob이 준 것과 비교하는 것이죠.
그런데 그럴 거면 뭐하러 Bob한테 받겠어요.
이때도 해시를 이용하면 됩니다.
Alice한테 SHA256해시만 미리 받아두고 있다가 Bob이 준 파일의 해시를 계산해서 비교해 보는 거죠.
역시 해시가 같다는 것은 입력된 값도 같다는 것이니까요.

여기까지 해시의 특성 첫번째까지 알아봤습니다.
내용을 보시면서 블록체인에서 어떻게 이용될지 좀 감이 오시나요?
나머지 두가지 특성에 대해서도 이어지는 포스트에서 설명하겠습니다.

관련 포스트 목록입니다.
[블록체인] - [블록체인] 해시함수 이해 1 - 해시함수란?
[블록체인] 해시함수 이해 2 - 특성 1 - 충돌이 거의 발생하지 않는다.(현재글)
[블록체인] 해시함수 이해 3 - 특성 2 - 원본 내용을 알 수 없다
[블록체인] 해시함수 이해 4 - 특성 3 - 퍼즐 게임을 만들 수 있다

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!