블록체인의 가장 큰 장점이자 특징은 블록체인의 모든 데이터를 참여자들이 모두 공유한다는 것이다. 그러나 블록체인의 크기가 계속해서 증가한다면 공유를 위해 많은 데이터를 동기화 해야하는 것이 문제이다.
이 문제를 해결하기 위해 머클 트리를 사용했고 이더리움에서는 이를 개선하여 머클 패트리시아 트리라는 암호 해시 기반의 트리 자료구조를 사용한다.
- 트리 내의 모든 정보는 레벨DB에 저장한다.
해시 함수란?
해시 함수는 임의의 크기 값을 입력했을 때 고정 크기 값을 생성해 내는 함수다.
예를들어 “허유명”이라는 글과 “유명한 허유명”이라는 글을 sha256으로 암호화 했을때 들어간 byte값을 다르지만 64바이트 크기의 고정된 문자열 값을 생성해 낸다.
- 이더리움에서는 keccak256 암호 해시를 사용한다.
머클 트리란?
머클 트리는 암호화 함수로 데이터를 해싱한 후 이 결괏값을 다시 암호화 해시하여 상위노드로 만들어진 트리 구조의 데이터이다.
- 공간을 절약하기 위해서 만들어진 데이터 구조(?)이다.
머클 트리는 어떻게 만들어지는가?
첫번째로 구체적인 특정 값들을 해싱한다.
그 해싱한 값들을 합쳐서 다시 해싱한다.
최상위 노드 하나가 남을때까지 위 작업을 반복하면 머클 트리가 생성된다.
- 바이너리 머클 트리
- 해싱한 값들을 2개씩 쌍으로 축약시켜서 하나로 만든다.
![](https://blog.kakaocdn.net/dn/bddOVw/btrvVAcfsM6/tlDjRamuk9q2TpEmWZnGvk/img.png)
- 거래 데이터를 해싱해서 해시0,1,2,3을 만들고 그걸 또 해쉬하여 루트해쉬까지 만든다.
- 루트 해시만을 가지고 있는 라이트 노드가 특정 거래가 블록에 있는지 확인하려면 순서대로 재계산을 하면 확인할 수 있게 된다.
- 새로운 트랜잭션이 일어나고 상태가 변경될때 바이너리 머클 체인은 상태를 업데이트 시키지 않고 원래 있던 상태를 삭제하고 새로 바뀐 상태를 인서트 한다.
2. 상태전이 머클 트리
![](https://blog.kakaocdn.net/dn/nJexa/btrvQhLMBIq/11ICxBqOeIpl9iXUYM4hfK/img.png)
- 위 그림을 보면 2개의 블록이 있고 두 블록이 동일한 머클 트리를 공유하고 있다.
- 대신 블록당 트리가 한개씩 있는 것이 아니라 공통된 것은 공유하고 변경 된 것만 추가하여 사용하는 것.
패트리시아 트리란?
![](https://blog.kakaocdn.net/dn/bX07bt/btrvUB3wLph/nHHCku55tM2Mcg47HaKXSk/img.png)
위 그림처럼 각 단어 전체를 저장하는 게 아니라 공통되는 부분을 공유하며 저장하는 방식이다. 이렇게 되면 데이터를 굉장히 많이 절약할 수 있게됨
머클 페트리시아 트리란?
![](https://blog.kakaocdn.net/dn/Q93j8/btrvVBCcDci/4PgybCr1FRcqNorXU6Gik1/img.png)
위 그림과 같이 구성된 구조 형태이다.
![](https://blog.kakaocdn.net/dn/kwDLx/btrvPeVZwl3/8cqJxX0FogNsbFhSLaI3kK/img.png)
이더리움 내에서 노드는 위 그림과 같이 key, value 형태로 저장이 된다.
- key = value의 hash값, 레벨DB에서 특정 노드를 검색할때 사용됨
- value = 17개 요소로 구성됨.첫 16개의 요소는 hex(16진수)값을 나타내고 마지막 17번째 요소에 노드가 가지고 있는 데이터가 저장되어있음. 트리에서 데이터를 찾는데 사용된다.
아래와 같은 key, value 데이터를 가지고있다고 하자.
{
'cab8': 'dog',
'cabe': 'cat',
'39': 'chicken',
'395': 'duck',
'56f0': 'horse'
}
비효율적인 트리
![](https://blog.kakaocdn.net/dn/xZlrP/btrvSeVkofD/2SWddX8JZ1SGgwRNd6yyjk/img.png)
위 트리에서 395에 해당하는 key값을 찾는 과정을 알아보자.
- 키값 395는 3,9,5 로 분리되어 순서대로 사용된다.
- rootHash에서 첫번째 패스인 3에 해당하는 hashA를 검색한다.
- DB에서 hashA를 검색한후 두번째 패스인 9 인자를 검색해서 hashC를 검색한다.
- DB에서 hashC를 검색한 후 마지막 패스인 5를 검색해서 hashD를 찾는다.
- hashD의 value가 duck인 것을 확인한다.
이런 과정으로 395의 value 값을 찾는다.
위 과정으로 value를 검색할때 노드들이 많은 null 값을 가져서 메모리가 낭비되고 있다.
이걸 한 단계 업글시켜서 데이터의 끝까지 분기되는 경로가 없을 경우 노드 하나에 나머지 경로를 할당해서 null값을 줄이는 방법이 있다.
56f0경로를 예로 보자.
첫번째 패스인 5에 ****할당하는 hashE부터 6f0패스 끝 노드까지 빈값을 거쳐간다.
이를 6f0패스 단하나로 통일하여 기존 16개 값을 저장하는 노드에 나머지 경로 6f0만 할당하는 것이다.
아래 이미지를 참조하자.
![](https://blog.kakaocdn.net/dn/Eu0vF/btrvUAXQiWT/rnckf4tsM4pdMgwwbGe9ek/img.png)
세번째 패스까지는 겹치는 cab8, cabe는 겹치는 경로를 하나로 정의해서 데이터를 절약할 수 있다.
아래 이미지를 보면
- 첫번째 패스인 c를 찾아 hashB를 찾는다.
- hashB의 패스 전체를 ab로 정의하고 value값으로 hashJ를 갖는다.
- hashJ를 검색하여 그곳에서 각자의 라스트 패스를 따라간다.
순서로 진행되는걸 알 수 있다.
![](https://blog.kakaocdn.net/dn/9KKsz/btrvWGJ1Jhx/okXqrElGfdtbKEX4RrBjv0/img.png)
나머지 노드들도 위에 나온 방법들로 정리하면 최적화된 메모리 저장 구조를 만들 수 있다.
마지막으로 HP인코딩을 통하여 리프노드와 확장노드에 prefix를 붙이게 된다.
![](https://blog.kakaocdn.net/dn/bCfDkC/btrvWGpKPuI/bU2iqjlI9NLv9eFCpf6yO1/img.png)
HP인코딩까지 마친 최종 머클 패트리시아 트리는 아래와 같다.
![](https://blog.kakaocdn.net/dn/c8ryUQ/btrvW5bL0b8/jKLCbRQ5ugKkMTknfvFD4k/img.png)
'BlockChain' 카테고리의 다른 글
부트스트랩 노드 (1) | 2022.03.28 |
---|---|
[EVM] 이더리움 가상머신 (0) | 2022.03.21 |
openethereum 메인넷 구축 (1) | 2021.11.30 |
스마트 컨트랙트 연산 gas(가스) 소모 (0) | 2021.10.26 |
스마트 컨트렉트, WEB3, 솔리디티 (0) | 2021.10.12 |