머클트리(Merkle tree)와 머클 패트리샤 트리(Merkle Patricia Tree)
머클트리(Merkle tree)
-
머클트리는 여러 데이터에 대해 단계적으로 해시함수를 적용하여 하나의 해시값으로 나타내는 데이터
-
머클 트리 구조의 핵심은 해시함수
-
머클트리는 최초 데이터를 SHA256형태의 해시값으로 변환한다.
-
SHA-256 암호화 : SHA-256은 단방향 암호화 기술로, 머클 트리가 데이터를 간편하게 인증하기 위해 사용하는 암호화 기술
-
각 데이터에 해시함수를 넣어 해시값을 만들고 해시값을 2개씩 짝지어서 연결된 2개의 값을 해싱하고 해시함수에 넣는다
-
이러한 구조로 인해 데이터의 무결성이 보장된다
-
예를 들어, 하나의 데이터 C의 내용이 1바이트라도 변경된다면 c의 데이터 해시값도 바뀐다(해시함수는 서로 다른입력에 대해 동일한 출력값을 가지지않는다. 충돌저항성)
이렇게 c가 바뀌엇으니 c와 연결된 d와 연결된 값도 바뀔것이고 이를 해싱한 값도 바뀔것이다. 즉 머클루트까지 값이 바뀐다 -
이러한 머클트리의 구조를 블록체인에서는 쇄도효과(avalanche effect)로 쓴다. 쇄도효과란, 하나의 트랜잭션이 변조되면 머클 루트까지 모든 값이 바뀌는 현상이다. 이로 인해 데이터의 무결성이 보장된다.
-
블록체인에서 머클트리가 가지는 또 하나의 장점은 특정 거래내역을 증명하기 위해 모든 거래내역을 검색할 필요가 없다는 것이다. 블록체인은 블록에 저장된 데이터가 시간이 지남에 따라 용량이 커지면, 거래 처리 속도도 느려질 수밖에 없다.
머클 패트리샤 트리(Merkle Patricia Tree)
비트코인에서는 머클트리를 사용하는 거와 달리 이더리움에서는 머클 패트리샤트리를 사용한다.
-
머클-패트리샤는 연관된 배열을 저장하기 위해 키를 사용하여 향상시킨다
-
노드는 키와 연결되고 각 노드의 실제 키가 저장되지 않지만 트리에서의 위치가 키를 정의하는 데 사용된다는 점이 머클 트리와 다르다
-
블록 헤더에 루트 노드들의 값을 가지고 있지만, 이더리움의 상태 일부분을 검증 할 수 있다.
머클 패트리샤 트리의 종류
-
이더리움 트리 종류는 트랜잭션 트리, 상태 트리, 저장트리, 영수증 트리가 있다
-
상태 트리는 State의 정보가 담겨 있다. 여기서 key값(path)은 항상 sha3(이더리움계정주소) 이고 value 값은 항상 rlp(이더리움 계정) 이 된다. value 값에 쓰인 이더리움 계정은 (nonce, balance, storageRoot, codeHash) 인 배열이다.
-
저장 트리는 컨트랙트 계정의 storage 정보가 담겨 있다. 이더리움 계정 배열 안에 storageroot에 root값이 들어간다. key값(path)은 약간의 계산 과정을 거친다.
계산 과정 참고자료 -
트랜잭션 트리는 거래 정보가 담겨 있다. key값은 rlp(트랜잭션 Index값)가 되는데 여기서 트랜잭션 Index값은 블록 안의 거래 Index이다.
-
영수증 트리는 부가적인 거래 정보(누적 가스량, 로그 등)이 담겨 있다. key값은 rlp(트랜잭션 Index값이다.
머클 패트리샤 트리를 쓰는 이유
-
머클 패트리샤 트리는 머클트리와 마찬가지로 무결성을 보장할 수 있다. 해쉬함수로 인해 노드의 값이 달라지면 상위노드의 해쉬값이 달라지고 root 값도 완전히 달라진다. 이로 인해 full node는 새로운 거래 정보를 효율적으로 검증할 수 있고, 블록헤더만 가지고 있는 light node도 root 값을 통해 거래 정보를 검증할 수 있습니다. 머클 트리가 없다면 light node는 거래 정보를 검증할 방법이 없다.
-
정보를 저장, 수정, 삭제, 검색 등을 효율적으로 할 수 있다. 머클 패트리샤 트리는 공통의 key값을 따라 저장하고 그 안에서 수정, 삭제, 검색을 한다. 정보를 저장할 때는 key값에 따라 저장하고 중복으로 저장을 하지 않아 공간이 절약된다. 세부적으로는 일정 byte를 초과하면 해싱도 한다. 또한 전체 정보를 뒤질 필요 없이 연결된 key값들(path)을 따라 수정,삭제,검색을 하니 처리 속도도 빨라진다.
