머클 트리 개념

머클 트리에 대한 개념은 네이버 블로그에 간단하게 작성해두었습니다.
이 단어를 처음 듣는 분은 링크를 클릭하여 가볍게 읽고 오시는 것을 추천드립니다.

머클 트리 코드로 구현하기

1. 개발 환경

• Ubuntu-20.04
  
  

2. 사용한 언어

• Javascript
  
  

3. 사용 모듈

• merkletreejs : 머클 트리 생성 및 검증 메서드 제공
• crypto-js : SHA256, AES 등의 여러 암호화 메서드 제공
  
  

4. 전체 소스 코드

• githup 에 올려두었습니다.
  github 링크
  
  

5. 구현 목표

머클 트리가 어떻게 생성되는지, 그리고 어떤 방식으로 검증이 되는지 알아보기.

6. 구현 과정

1) 필요한 모듈 설치하기

$ npm i merkletreejs crypto-js

2) SHA256 암호화 사용해보기

// Import modules
const SHA256 = require("crypto-js/sha256");

// Check output of SHA256()
console.log("SHA256('a') : ", SHA256("a"));
console.log("SHA256('a').toString() : ", SHA256("a").toString());

crypto-js의 SHA256함수의 출력값을 보면 우리가 원하는 64자리의 16진수가 안나온다.
toString() 함수를 사용하면 원하는 형태의 해시값이 출력된다.

이를 활용해서 테스트 할 배열을 만들고 내부 요소들을 모두 해시화 한다.

// Create an array and convert it into hash using SHA256
const testSet = ['a', 'b', 'c', 'd', 'e']
const testArray = testSet.map((v) => SHA256(v).toString());
console.log(testArray)

3) 머클 트리 만들기

위에서 만든 테스트 배열을 이용해서 머클 트리를 만들어보자.

// Import modules
const SHA256 = require("crypto-js/sha256");
const { MerkleTree } = require("merkletreejs");

...

// Create a merkleTree of testArray
const testMerkleTree = new MerkleTree(testArray, SHA256);
console.log("testMerkleTree : ", testMerkleTree);

// Get merkleRoot
const merkleRoot = testMerkleTree.getRoot();
console.log("merkleRoot : ", merkleRoot);

출력된 값을 보면 아래의 정보들이 존재한다.

• leaves : 자식 노드가 없는 최하단 노드들
• layers : 각 레이어에 존재하는 노드들을 나타냄, 제일 마지막 레이어(원래는 최상단 노드)에 Merkle Root가 있음을 알 수 있다.
  
  

4) 검증해보기

마지막으로 위에서 만든 머클 트리에 속한 값인지 아닌지 검증해보자.

4-1) 머클 트리에 존재하는 값 검증

...

// Verify valid hash, 'a'
const testValue_valid = "a";
const leaf_valid = SHA256(testValue_valid).toString();
const proof_valid = testMerkleTree.getProof(leaf_valid)
const result_valid = testMerkleTree.verify(proof_valid, leaf_valid, merkleRoot)
console.log('leaf_valid : ', leaf_valid);
console.log('proof_valid : ', proof_valid);
console.log('result_valid : ', result_valid);

proof_valid 값을 보면 어떤 순서로 어느 값과 비교를 진행했는지 알 수 있다.
leaves가 홀수인 경우엔 아래 그림처럼 진행된다.

자세한 내용은 Verifiable data structures를 참고하자.

4-2) 머클 트리에 존재하지 않는 값 검증

...

// Verify invalid hash, 'u'
const testValue_invalid = "u";
const leaf_invalid = SHA256(testValue_invalid).toString();
const proof_invalid = testMerkleTree.getProof(leaf_invalid);
const result_invalid = testMerkleTree.verify(proof_invalid, leaf_invalid, merkleRoot);
console.log('leaf_invalid : ', leaf_invalid);
console.log('proof_invalid : ', proof_invalid);
console.log('result_invalid : ', result_invalid);

존재하지 않는 값이므로 proof는 비어있는 배열을,result는 false를 반환한다.

7. 마무리

직접 알고리즘을 짜본 건 아니지만, 모듈을 활용해서 머클 트리가 어떻게 검증되는지 이해할 수 있었다.
이를 통해서 블록체인에서는 각각의 Peer가 모든 트랜잭션 데이터를 갖고 있지 않아도, 효율적인 검증이 가능하다는 것이 어떤 뜻인지 조금은 알 것 같다.
앞으로 활용방법에 대해서 더 공부해야겠다.