Day : 35
Blockchain Day : 5
➕ 소소한 지식
- 비트코인 - utxo기반 / 이더리움 - account 기반
- 지갑주소 != 사람 ; EOA(Externally Owned Accounts), CA(Contract Accounts)
3. 머클 트리 & 머클 패트리시아 트라이 (Merkle Tree & Merkle Patricia Trie)
비트코인은 머클트리, 이더리움은 머클 패트리시아 트리 사용
Q. 왜 해시기반의 트리 자료 구조를 사용하는 걸까?
A. 데이터를 손쉽게 가지고 오기 위해서
- 64개의 데이터의 경우, for문을 사용하면 총 64번의 과정을 거쳐야 하지만 머클트리를 사용할 경우 6번만 비교하면 됨.
- 지갑 주소가 100만개 있다고 가정.
→ 100만개를 선형으로 보관할 수 없음.
→ 머클트리 구조로 보관
→ 사용할때 key-value값으로 조회
→ key가 지갑주소, 최종 value값이 지갑잔고
Merkle Tree?
: 이진 트리 형태
: 가장 가까운 거래 내역들의 해시값을 산출하여 상위노드로 보냄
→ 쌍을 지을 수 없을 때까지 이 과정을 반복
: 머클 루트 = 최종 산출된 해시 값 = 블록내의 모든 거래 요약본
: 머클 루트로 자료의 변형 인식이나 검증 과정 수행
: 어떤 거래의 진위를 따질 때 머클 path를 통해 검증 할 수 있음
(SPV 노드가 풀 노드에게 부탁)
: path를 통해 얻은 마지막 값이 value
: 머클 루트 용량 = 32 bytes ; 거래량과 상관 없이 항상 일정
Merkle Patricia Trie?
: 머클트리와 기수트리(Radix trie)의 콜라보
: PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric)
: Blank, Leaf, Branch, Extension 총 4가지 노드 종류 (여기서의 노드는 트리 안에서의 노드)
: extention node - branch Node - Leaf node 순으로 구성
➕
- 이진트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
- 트라이(Trie)는 트리의 한 종류
- 참고자료
Merkle Patricia Tree
: https://ihpark92.tistory.com/48
: https://blog.naver.com/pcmola/222092198653
: https://velog.io/@nara7875/%EB%A8%B8%ED%81%B4-%ED%8C%A8%ED%8A%B8%EB%A6%AC%EC%8B%9C%EC%95%84-%ED%8A%B8%EB%A6%AC
: https://hamait.tistory.com/959
