- 머클 트리
머클 트리는 데이터의 무결성을 효과적으로 검증하는데 사용되는 구조이다.머클 루트를 형성하기 위해, 반복적으로 데이터를 해시화한다.- 이후 데이터 조각이 잘못된 경우, 이를 효율적으로 검증할 수 있다.
- 검증에 필요한 용량이 대폭 줄어들고, 저사양 디바이스의 참여가 가능해짐(
라이트 노드)
- 머클 루트
머클 루트의 해시가 개발자에 의해 공개된 것과 일치하는지 확인해야 한다.- 두 해시가 일치하면, 모든 파일이 정확히 일치한다고 할 수 있다. → O(logN)
- 머클루트는 다음 과정으로 만들어진다
- 최초 데이터를 SHA256 형태의 해시값으로 반환
- 가장 가까운 2개의 노드를 한 쌍으로 묶어 합친 후, 해시값으로 반환
- 위 과정을 계속하여, 마지막 하나가 남을 때까지 반복
- 머클루트의 값이 됨
- 이 과정을 통해, 각 리프노드의 거래 정보들의 유효성 검사를 할 수 있음
- 머클 페트리샤 트리
- 이더리움은
머클 패트리샤 트리를 사용한다. - 머클 트리 + 페트리샤 트리이다. 여기서 페트리샤 트리는
트라이이다. 트라이는 문자열을 빠르게 탐색할 수 있는 자료구조이다.- 머클 페트리샤 트리도 해시 기반 트리 구조이다. 데이터가 변경되면 상위 노드들의 해시가 바뀐다.
- 각 레벨에서 중복되는 해시를 최소화해 효율적인 압축 구조를 갖는다.
- 트리에서의 위치가 키를 정의하는 데 사용된다는 점에서 머클 트리와 다르다
- 공통 접두사를 하나의 키에 저장하기 때문에 공통 접두사를 찾는 속도가 빨라지고, 그 결과로
- 메모리 사용량 감소, 검색 속도 향상, 노드 탐색 최소화가 가능하다.
- 머클 페트리샤 트리에는 다음 데이터들이 저장된다.
상태 루트(State Root)- 모든 Account와 Account의 상태 데이터가 저장된다.
트랜잭션 루트(Transaction Root)- 블록에 포함된 모든 트랜잭션 데이터를 나타낸다.
- 각 거래의 송신자, 수신자, 금액, 데이터 등 정보가 포함됨
reciept 루트- 거래 결과 (영수증)
ref
Share article
