메 르 켈 나무

분산 시스템, P2P 응용 프로그램 이나 블록 체인 에서 데이터 구조 인 Merkle tree (메 르 켈 트 리) 를 자주 사용 합 니 다. 여기 서 우 리 는 이 자주 사용 하 는 데이터 구 조 를 상세 하 게 토론 할 것 입 니 다.
Merkle tree
Merkle 나 무 는 이 진 트 리 처럼 보 입 니 다. 그 잎 노드 의 값 은 보통 데이터 블록 의 해시 값 이지 잎 노드 의 값 이 아 닙 니 다. 그래서 가끔 Merkle tree 도 Hash tree 라 고 표시 합 니 다. 다음 그림 과 같 습 니 다.
Merkle 트 리 를 구성 할 때 먼저 데이터 블록 에 대해 해시 값 을 계산 하고 보통 SHA - 256 등 해시 알고리즘 을 사용 합 니 다.그러나 데이터 가 의도 적 으로 손상 되 거나 변경 되 지 않도록 한다 면 CRC 와 같은 안전성 은 낮 지만 효율 적 인 검사 와 알고리즘 을 바 꿀 수 있다.그 다음 에 데이터 블록 이 계산 한 해시 값 을 두 쌍 으로 짝 짓 기 (홀수 개수 라면 마지막 자신 과 자신 이 짝 짓 기) 하고 이전 층 의 하 시 를 계산 한 다음 에 이 절 차 를 반복 하여 근 하 시 값 을 계산 할 때 까지 합 니 다.
Merkle 트 리 는 대부분 분포 식 환경 에서 여러 호스트 에서 데 이 터 를 얻 고 얻 은 데이터 가 정확 한 지 검증 하 는 데 사 용 됩 니 다. Merkle 트 리 뿌리 해시 가 일치 하 는 지 검증 하면 됩 니 다.예 를 들 어 다음 그림 에서 L3 데이터 블록 에 오류 가 발생 하면 (예 를 들 어 데이터 가 수정 되 었 다) 오 류 는 계산 hash(L3) 으로 전 달 됩 니 다. 이 어 계산 hash(Hash1-0+Hash1-1) 으로 전 달 됩 니 다. 마지막 으로 건 하 쉬 로 전 달 됩 니 다. 건 하 쉬 의 일치 하지 않 습 니 다. 그 어떠한 바 텀 데이터 블록 의 변화 도 결국은 건 하 쉬 로 전 달 됩 니 다.또 건 해시 가 일치 하지 않 으 면 Merkle 트 리 를 통 해 일치 하지 않 는 데 이 터 를 빠르게 찾 을 수 있다.
Merkle 트 리 는 데 이 터 를 빠르게 비교 하여 일치 하지 않 는 데 이 터 를 빠르게 찾 을 수 있 습 니 다.예 를 들 어 분포 식 저장 소 에서 한 개의 데 이 터 는 여러 개의 사본 이 있 고 서로 다른 기계 에 분포 된다.데이터 의 일치 성 을 유지 하기 위해 서 는 사본 동기 화가 필요 하 다. 가장 중요 한 것 은 현재 사본 이 일치 하 는 지, 일치 하지 않 으 면 동기 화 할 필요 가 없다. 일치 하지 않 으 면 일치 하지 않 는 부분 을 찾 아 동기 화 해 야 한다.분명 한 것 은 직접 전송 데 이 터 를 비교 하면 매우 비효 율 적 이 고 보통 데 이 터 를 해시 하고 해시 값 을 전송 하 는 방법 을 사용한다.이 를 위해 모든 기기 에 비교 해 야 할 데이터 구조 인 Merkle 트 리 를 만 들 수 있 으 며, 건 해시 가 일치 하면 데이터 가 같 고 건 해시 가 일치 하지 않 으 면 Merkle 트 리 를 통 해 일치 하지 않 는 데 이 터 를 빠르게 검색 할 수 있다.위 그림 의 파란색 레이 블 과 같이 빠 른 검색 과정 을 예 로 들 어 설명 한다.만약 에 두 기계 에서 L3 데이터 블록 이 일치 하지 않 는 다 고 가정 하면 우 리 는 건 하 시 를 비교 해 보면 건 하 시가 일치 하지 않 는 다 는 것 을 발견 했다. 즉, 데이터 가 일치 하지 않 는 다 는 것 이다. 이때 그 블록 이 일치 하지 않 는 것 을 찾 아야 한다. 각각 Hash0 과 Hash1 를 비교 해 보면 Hash1 이 일치 하지 않 는 것 을 발견 했다. 그 다음 에 아래로 보 내 는 것 은 Hash1-0 일치 하지 않 는 것 이다. 그러면 L3 데이터 블록 이 일치 하지 않 는 것 으로 포 지 셔 닝 된다.포 지 셔 닝 과정의 알고리즘 복잡 도 는 O(log(n)) 이다.
또 하나의 데이터 구 조 는 어느 정도 에 Merkle 트 리 의 하위 트 리 라 고 볼 수 있 지만 완전히 같 지 않다. 이 데이터 구 조 는 Hash list (중국어 해시 목록 과 해시 표 의 오 해 를 피하 기 위해 영어 이름 을 사용 합 니 다) 입 니 다. 이 Hash list 를 살 펴 보 겠 습 니 다.
Hash list
점대 점 네트워크 에서 데이터 전송 을 할 때 효율 을 높이 기 위해 여러 기계 에서 데이터 의 다른 부분 을 동시에 다운로드 하 는 경우 가 많다. 즉, 한 기계 에서 전체 데 이 터 를 다운로드 하 는 것 이 아니 라 전체 데 이 터 를 서로 다른 부분 으로 나 누 어 서로 다른 기계 에서 전체 데이터 의 서로 다른 구성 부분 을 얻 는 것 이다.이렇게 블록 전송 은 여러 대의 기계 에서 데 이 터 를 동시에 다운로드 할 수 있 을 뿐만 아니 라, 또 다른 장점 은 이 작은 데이터 전송 과정 에서 손상 되면 이 작은 데이터 블록 을 다시 다운로드 하면 되 며, 전체 데 이 터 를 다시 다운로드 하지 않 아 도 된다 는 것 이다.
그러나 이런 분포 식 환경 에서 많은 기계 들 이 불안정 하거나 믿 을 수 없다 고 생각해 야 한다. 어떻게 전체 데이터 의 완전 성과 모든 작은 데이터 블록의 완전 성 을 검사 합 니까?
모든 데이터 블록 을 검사 하기 위해 서 는 모든 데이터 블록 을 해시 로 만들어 해시 목록 을 만들어 야 합 니 다. 이렇게 다운로드 하기 전에 우 리 는 먼저 해시 목록 을 가 져 와 야 합 니 다. 다운로드 한 후에 우 리 는 해시 목록 을 통 해 모든 데이터 블록 을 검증 할 수 있 습 니 다.이 해시 목록 이 정확 하 다 는 것 을 어떻게 보장 합 니까? 아니면 전체 데 이 터 를 어떻게 검사 합 니까?모든 데이터 블록 해시 가 정확 하 다 면 최종 적 으로 얻 은 전체 데 이 터 는 정확 할 것 입 니 다. 따라서 우 리 는 해시 목록 에 대해 하 시 를 진행 하여 건 하 시 를 얻 고 이 건 하 시 를 신뢰 할 수 있 는 소스 에 넣 어야 합 니 다. 데 이 터 를 다운로드 하기 전에 신뢰 할 수 있 는 데이터 소스 에서 데 이 터 를 얻 은 다음 에 임의의 기계 에서 하 시 목록 을 얻 은 다음 에 데이터 블록 을 다운로드 해 야 합 니 다.이렇게 하면 데이터 의 완전 성 은 건 하 시 를 통 해 보장 할 수 있다.
Merkle tree 비교 해시 목록
두 가지 데이터 구 조 는 모두 데이터 의 완전 성 을 검증 하 는 기능 을 가지 고 있 으 며 모두 겐 하 시 를 통 해 전체 데이터 의 완전 성 을 확보 할 수 있다.다른 것 은 데이터 가 방대 하고 데이터 블록 이 매우 많은 상황 에서 건 하 시가 데이터 가 일치 하지 않 음 을 감지 할 때 Merkle tree 는 일치 하지 않 는 데이터 블록 을 신속하게 찾 을 수 있 고 복잡 도 는 O(log(n)) 이 며 Hash list 는 방대 한 해시 목록 을 옮 겨 다 니 며 일치 하지 않 는 데이터 블록 을 찾 을 수 있 을 뿐 복잡 도 는 O(n) 임 이 분명 하 다.이때 Merkle tree 의 효율 은 매우 높다.
참고 문서: Hash list
위 챗 공식 번 호 를 주목 하고 저 와 함께 분포 식, 데이터 구조, 블록 체인 을 배 웁 니 다!