해시 트리: 머클 트리(Merkle tree)

머클 트리(Merkle tree), 머클 루트(Merkle root)

 

머클 트리와 머클 루트는 데이터가 위변조 되었는지 효율적으로 확인하기 위한 용도로 사용하고 있다.

 

 

- Merkle tree

 

머클 트리(Merkle tree)

 

발명자인 랄프 머클(Ralph Merkle)의 이름에서 따온 단어로, 해시 트리(Hash tree)라 부르기도 한다. 머클 트리는 여러 블록으로 나뉘어 있는 데이터를 전송할 때 데이터가 변조되지 않았음을 보증하는 용도로 쓰인다. 특히 P2P 네트워크에서 전송받은 데이터에 오류가 있거나 외부로부터 조작이 있었는지 검증하는 용도로 사용한다.

 

머클 트리는 랄프 머클이 여러 램포트 서명(디지털 서명 알고리즘)을 효율적으로 다루기 위해 개발했다. 램포트 서명은 보안에 대해서는 어느 정도 검증을 받았지만 각 데이터마다 새로운 키를 생성해야 하는 단점이 있었다. 이에 여러 램포트 키를 머클 트리로 묶어 효율성을 높였다. 블록체인에서는 블록에 포함된 거래 데이터를 요약해 트리 형태로 만들게 되는데 해시 함수를 활용해 두 개의 거래 데이터를 하나의 데이터로 묶음으로써 용량을 절약할 수 있다.

머클 루트(Merkle root)

 

블록에 들어 있는 모든 거래 내역을 요약한 데이터로, 최소한의 정보로 인증할 수 있도록 도와준다. 전체 데이터는 용량이 매우 크므로, 모든 노드가 갖고 있기에는 부담스럽다. 모든 노드가 갖고 있어야 한다면 블록체인 네트워크에 참여할 수 있는 노드의 수도 줄어들 수밖에 없을 것이다. 이에 개별 거래에 대한 트랜잭션을 검증하는 기능을 수행하는 노드(라이트 노드)에 대해서는 중요한 데이터만 갖고 있도록 하였다.

 

외부에서 다른 블록의 거래 내역을 조작하면 머클 루트를 대조하여 비교하게 된다. 가장 밑단에 있는 거래를 제외한 나머지 내역을 두 개씩 짝지어서 해시 값을 얻고 또 그 해시끼리 짝지어 암호화하는 식이다. 이렇게 모든 거래 내역에 해시 값을 얻는 과정을 거듭하여 나무 모형으로 만들면 머클 트리가 된다.

머클 트리는 그 자체가 해시로 이루어져 있다. 그렇기에 하나의 트랜잭션 혹은 블록 내 필드 값이 변조될 경우, 머클 루트 해시 값도 변조된다. 하나의 트랜잭션이 변조되면 머클 루트까지 모든 값이 바뀌게 되는 쇄도 효과(avalanche effect)가 일어난다. 따라서 검증 과정에서 잘못된 해시값을 발견하면 해당 블록을 거부함으로써 블록체인 네트워크를 안정적으로 유지할 수 있다.

 

 

- bitcoin.stackexchange.com

 

쇄도 효과(avalanche effect) : 입력값에 미세한 변화가 생기게 되면 출력 값에도 큰 변화가 일어나는 성질이다. 일반적으로, 암호 알고리즘은 쇄도 효과가 강할수록 분석이 어렵다고 평가받는다.