머클트리란?
머클트리는 여러 데이터에 대해 단계적으로 해시함수를 적용하여 하나의 해시값으로 나타내는 데이터 구조
머클트리는 블록체인에 있는 데이터의 위변조를 방지하고, 데이터가 변하지 않았음을 보장하는데 사용
그렇다면, 머클트리는 어떻게 블록체인의 무결성을 보장할 수 있을까?
이를 알기 위해서는 먼저 머클트리의 동작 방식을 알아야 한다.
머클트리의 동작방식
머클트리는 위의 그림처럼 여러 개의 데이터(A,B,C,D)를 여러 단계를 거쳐 하나의 해시값으로 만드는 트리, 이렇게 여러 데이터를 모아 만들어진 하나의 해시값을 머클 루트(Merkle Root)라고 한다.
어떻게 머클 루트가 만들어지는지 확인해보자!
- 다음과 같이, 머클 루트를 만들기 위한 데이터 A,B,C,D가 있다.
- 각 데이터를 해시함수에 넣어, 해시값을 만든다.
- 각 해시 값을 두개씩 짝지어서 연결
- 연결된 두 해시값을 해싱한다. hA와 hB를 하나로 연결하고, 이를 해시 함수에 넣어 해싱
- 이런식으로 최종적으로 하나의 해시값만 남을 때까지 반복
- 마지막으로 남은 해시값을 다시 한번 해싱
이렇게 최종적으로 나온 해시값이 바로 머클 루트
머클 루트는 트리의 루트이자, 모든 데이터를 모아 해싱한 값
머클트리가 무결성을 보장하는 방법
머클 트리는 어떻게 무결성을 보장할까?
만약 머클 트리의 데이터 C가 변경된다고 가정해보자.
데이터 C의 내용이 1바이트라도 변경된다면, 데이터 C의 해시값 hC도 변경될 것이다.
해시함수는 서로 다른 입력에 대해 동일한 출력값을 가지지 않기 때문(이를 충돌저항성이라고 한다)
hC의 값도 바뀌었으니, hC와 hD를 연결한 값도 바뀔 것이고, 이를 해싱한 값도 바뀔 것이다.
결론적으로, 머클 루트 값까지 전부 바뀌게 될 것이다.
이렇게 머클트리는 해시 함수의 충돌저항성을 활용하여 여러 데이터의 집합 중 단 하나라도 변경되었는지 찾을 수 있다.
Blockchain developer