[블록체인]머클 트리 & 머클 패트리샤 트리

dhkim·2022년 7월 4일

머클 패트리샤 트리 블록체인

블록체인 뽀개기

목록 보기

8/22

비트코인과 다르게 이더리움에서는 단순 이진 머클트리가 아닌, 머클트리의 개선된 버전인 머클 패트리샤 트리를 채택하여 사용하고 있다.

머클 트리와 머클 패트리샤 트리에는 어떤 차이가 있을까?

머클 트리 (Merkle tree)

머클 트리는 일련의 '데이터 무결성'을 효과적으로 검증(증명)하는 데 사용되는 구조이다
머클 트리 구조의 핵심에는 '해시 함수'가 있다
머클 트리는 데이터를 여러 조각으로 나누며 생성되며,
'머클 루트'를 형성하기 위해 반복적으로 해시화된다
이후 데이터 조각이 잘못된 경우, 이를 효율적으로 검증(수정)할 수 있다
큰 장점은 하위 트리를 분석하여 데이터가 트리 내에 있는지 쉽게 확인할 수 있다

머클 루트(Merkle Root)

이렇게 파일을 다운로드 하면,
이 자료는 '머클 루트(Merkle Root)' 라는 해시를 제공한다

다운로드 하고자 하는 파일의 해시가 개발자에 의해 공개된 것과 일치하는지 확인해야 한다
두 해시가 일치한다면, 컴퓨터에 존재하는 파일이 개발자들의 것과 정확히 일치한다고 말할 수 있다
머클루트가 중요한 이유는 데이터 유효성의 검증 때문이다
(유효성 검증 속도는 OLog₂N)

👉 '머클 루트'를 사용하면, 훨씬 간단하게 데이터를 검증할 수 있다

쇄도 효과(avalanche effect)

하나의 트랜잭션이 변조되면 머클 루트까지 모든 값이 바뀌게 된다

이러한 현상을 '쇄도 효과(avalanche effect)'라고 한다

머클 패트리샤 트리(Merkle Patricia Tree)

'이더리움' 에서는 모든 트랜잭션의 완전한 모델을 만들기 위해
머클 패트리샤 트리 Merkle-Patricia-Tree (trie) 방법을 사용한다

머클-패트리샤는 연관 배열을 저장하기 위해 '키'🔑 (일반적으로 문자열로 정의됨) 를 사용하여 이를 향상시킨다
노드는 키🔑와 연결된다
이것은 '디지털 트리'인 '트라이(trie)'로 정의된다
이것은 각 노드의 실제 '키🔑'가 저장되지 않지만
트리에서의 위치가 '키🔑'를 정의하는 데 사용된다는 점에서 <ㅡ> 머클 트리와 다르다

머클 패트리샤 트리 특징

이더리움의 전역상태는 계정 주소와 계정 상태를 매핑한 것으로 구성되어 있다

부모 노드는 '두 자식 노드를 모아' 해싱한 값을 가진다

자식 노드의 값이 '조금이라도 바뀌면' 부모 노드의 값도 바뀐다

이더리움 블록 헤더는 상태트리 / 트랜잭션 트리 / 영수증 트리

세 트리의 루트 노드 해시값이 저장되어 있다

블록 헤더에 루트 노드들의 값을 가지고 있지만,
이더리움의 '상태 일부분을 검증' 할 수 있다

트리 '맨 아래'에 있는 노드들은 데이터를 가지고 있다

이더리움에서는 머클 패트리샤 트리를 왜 사용하나요?

정보를 효율적으로 저장, 수정, 삭제, 검색 등을 할 수 있다. 머클 패트리샤 트리는 공통의 키 값을 따라 저장하고 그 안에서 수정, 삭제, 검색을 한다. 정보를 저장할 때는 키값에 따라 저장하고 중복저장을 하지 않아 공간이 절약된다. 세부적으로는 일정 바이트를 초과하면 해싱도 한다. 또한 전체 정보를 뒤질 필요 없이 연결된 키 값들(path)을 따라 수정,삭제,검색을 하니 처리속도도 빨라진다.
거래 정보를 검증할 수 있다. 해쉬함수로 인해 노드의 값이 달라지면 상위노드의 해쉬값이 달라지고 root 값도 완전히 달라진다. 이로 인해 full node는 새로운 거래 정보를 효율적으로 검증할 수 있고, 블록헤더만 가지고 있는 light node도 root 값을 통해 거래 정보를 검증할 수 있다. 머클 트리가 없다면 light node는 거래 정보를 검증할 방법이 없다.
그래서 머클 패트리샤 트리는 이더리움의 코어 프로토콜 이외에도 이더리움 스케일링 솔루션인 샤딩, 플라즈마 등 블록체인 기술 전반에 널리 쓰이고 있다.