머클 트리는 해쉬의 해쉬의 해쉬…를 트리로 만든 거다. 일부 변경된 부분을 빠르게 찾을때 쓴다. Git과 비트코인이 그 예다.
해쉬란?
해쉬는 원래 내용을 정해진 공간의 값으로 바꾼 것이다. 그 공간은 1에서 100 사이일수도 있고, integer 범위일수도 있고, 20바이트일수도 있고, 32바이트일수도 있다. 그래서 해쉬값은 같은지 다른지 한 번에 비교할 수 있다.
Git의 두 파일이 n바이트라면, 비교하는데 시간복잡도 O(n)이 걸린다. 그런데 파일의 해쉬끼리 비교하면 O(1)로 줄어든다.
해쉬 충돌이란?
그런데 사실은 한번보다 더 걸릴수도 있다. 예를 들어 100바이트 파일들을 20바이트 해쉬로 변환하다보면, 그 중에 뭔가 같은 해쉬값이 생길 수 있다. 100바이트로 만들 수 있는 파일 조합은 256^100개인데, 20바이트로 만들 수 있는 해쉬값은 256^20개이기 때문이다. 이걸 해쉬 충돌(hash collision)이라고 한다.
이건 생일 문제(birthday problem)라고도 하는데, 사람의 해쉬값을 생일로 쓰면 누군가는 같은 생일인 사람들이 있을 수 있다는 문제다. 1년은 최대 366일이니까, 367명 이상이면 누군가 생일이 같을 것이다. 한국이야 주민등록번호를 쓰면 되겠지만, 그것도 한국의 인구가 아주 많아져서 주민등록번호의 범위를 넘으면 문제가 될 것이다.
해쉬 충돌을 어떻게 다룰까?
생일이 같아도 같은 사람이 아닐 수 있듯이, 해쉬값이 같아도 파일이 다를 수 있다. 그러면 어떡할까? 각 해쉬값마다 파일들을 다 연결해놓고, 파일 하나씩 다 비교한다.
그러면 시간복잡도가 O(n)으로 증가하지 않나? 예를 들어 367명의 사람을 생일로 찾으면, 생일이 같은 사람이 최대 367명일 것이다. 그렇긴 한데, 꼭 그렇진 않다.
두 사람의 생일이 같을 확률은 1/366 이다. (편의상 윤년 확률은 무시하겠다) . 반면 두 사람의 생일이 같을 확률은 365/366 이다. 이것이 세 명, 네 명, 다섯 명… 367명인 경우에 생일이 같을 확률과 다를 확률을 계산해보자. 시간복잡도가 O(1)인 경우와 O(n)인 경우가 나뉜다. 각각의 복잡도에 확률을 곱해서 평균을 내면, O(n)보다 O(1)에 가깝다. 이걸 분할 상환 분석(amortized analysis)라고 한다.
그리고 해쉬 펑션(hash function)을 잘 만들면 충돌을 줄일 수 있다. 생일이 같더라도 이름으로 더 찾을 수 있고, 이름이 같아도 성별로 더 찾을 수 있다. 이렇게 생일, 이름, 성별, 나이, 태어난 주소… 등을 추가하면 충돌이 줄어들 것이다.
같은 경우 말고, 다른 경우는 어떨까?
반대로 생각해보자. 생일이 같은데 다른 사람일 수 있다. 그럼 생일이 다른데 같은 사람일 수 있을까? 없다. 그럼 해쉬값이 같아도 다른 파일일 수 있지만, 해쉬값이 다른데 같은 파일일 수 있을까? 없다.
다른 걸 찾는게 더 쉽다. 굳이 amortized analysis를 안해도 그냥 O(1)이다.
파일 n개를 비교하면?
파일 하나에 O(1)이라도, 파일 n개면 O(n)이다. 더 빠르게 안될까? 머클 트리(Merkle tree)가 있다.
각 파일별로 해쉬를 구한 다음에, 각 폴더별로 해쉬들의 해쉬를 구한다. 파일 n개의 해쉬를 합쳐서 폴더 1개의 해쉬를 만든다. 그 상위 폴더도 마찬지로 하위의 모든 파일들과 폴더들의 해쉬를 구한다. 그렇게 루트 폴더까지 간다.
그러면 루트 폴더의 해쉬 1개만 비교하면 된다. 그게 다르면 하위의 어딘가가 다를 것이다. 그럼 그 하위로 가서 다른 해쉬값을 찾아나가면 된다. 그럼 최악의 경우, 맨 밑에까지 내려갈 수 있다. 폴더들의 높이 만큼이다.
그럼 이 중에 파일 1개를 수정했을때, 몇 개 폴더의 해쉬를 수정해야 할까? 그것도 상위 폴더들 갯수 만큼이다. 폴더들의 높이 만큼이다.
그럼 그 높이는 얼마일까? 파일 n개일때 그 높이가 최대 n이겠지만, 한 폴더당 파일을 최대 100개까지만 넣어놨다면 log n일 것이다. 이렇게 100개 같이 상수값으로 잘 정리해놨다고 가정하자.
잠깐, 머클 트리는 해쉬 충돌이 없나?
있을 수 있다. 하지만 Git이나 비트코인 같은 경우에는 없다고 쳐도 된다. 100%는 아니지만, 거의 100%에 가깝다. 왜냐하면 Git이나 비트코인은 한 번에 조금씩 바꾸고, 조금 바꿀 땐 해쉬 충돌이 거의 일어나지 않기 때문이다.
내 경험도 그렇다. 지금까지 Git을 쓰면서, 파일을 고쳤는데 안 고쳤다고 나온 경우가 없었다. Git이야 그렇지만 비트코인은 돈인데 괜찮을까? 비트코인도 지금까지 해쉬 충돌 공격으로 뚫린 적이 없다.
