[JAVA] Merkle Tree Bottom-Up 구현 / 머클트리 구현

블록체인의 작업증명은 거래(트랜잭션)이 주어지면, 해당 거래를 가지고 블록을 만들 수 있는지 확인해야 한다. 주어진 거래와 같은 블록을 이루는 거래들을 이용하여 해당 블록의 Hash값과 일치하는지 확인해야 하는데, 이 때 머클트리를 활용한다.

머클트리

머클트리는 위 이미지와 같이 생겼는데, 거래 정보는 Leaf Nodes를 구성하고, 해당 거래 정보의 부모들은 각 자식들을 Hash 한 값이 된다. 이렇게 쭉쭉 타고 올라가 결국 root값 또한 root의 자식들을 hash한 값으로 이루어진다.
또한 Merkle Tree는 생성된 후에 값이 변조되면 안되기 때문에, 오직 getRoot()라는 method만 가진다. (블록체인에서 블록의 수정은 불가능하기 때문이다.)
Merkle Tree를 정말 트리로 구성하여 삽입, 수정, 삭제 등의 기능을 구현해도 되지만, 이는 Java의 자료구조에서 다룰 것이고, 오늘은 블록체인의 Merkle Tree이기 때문에 단순 삽입을 통한 merkle Tree를 구성하게 하겠다.

---

블록으로 만들려고 하는 상황중 가장 좋은 경우는 트랜잭션의 갯수가 2^n꼴로, 이진트리를 만들었을 때 모든 leaf노드들을 트랜잭션으로 만들 수 있을때는 가장 편하다. 받아들인 트랜잭션(거래)들을 모두 leaf 노드로 설정하고, 부모를 만들어 나가며 root값을 찾으면 되기 때문이다.

거래의 수가 홀수라면 어떻게?

내가 가지고 있는 홀수 개의 수로 머클트리를 만들어야 할때는, 간단하게 다음과 같이 해결할 수 있다.

짝이 없는 거래(마지막 홀수번째)는 자신을 이용하여 해쉬한다.

짝이 없는 거래, 마지막 홀수번째 거래의 경우에는 자기 자신을 한번 더 사용하여 해시값을 만들면 된다.
이 아이디어를 응용해 보면, 2^n꼴이 아닌, 짝수개의 트랜잭션은 어떻게 하면 될까? 다음 그림을 보고 힌트를 찾길 바란다.

짝수개 머클트리

그림상 2번 Hash가 (1, 2)라 되어 있는데 오타다. Hash(3, 4)가 2번 동그라미가 되어야 한다.

---

머클트리 구현 아이디어

머클트리는 Binary Tree형 자료구조이다. 그리고 실제 데이터 삽입은 단말 노드에서만 이루어진다. 즉 머클트리는 기존 트리처럼 Top-Down 형식의 구현이 아니라 Bottom-Up 형식으로 구현하면 된다.
그리고 블록체인의 각 블록은 머클트리의 루트값만 가지고 있으면 된다. 바꿔 생각해보면, 만약 블록체인이 머클트리를 이루는 모든 해쉬값을 갖고 있으면 추적할 수 있게 되는것이고, 이는 보안상 구멍이 될 수 있는 것이다. 누구든 해당 블록을 만드는 각 트랜잭션을 만들 수 있게 되고, 그를 바탕으로 누가 어떤 거래를 했는지 알 수 있게 되는 것이다.
따라서 머클트리는 각 depth간 모든 해쉬 정보를 갖고 있을 필요가 없으며, 머클트리를 검증하기 위한 각 계층의 해쉬값을 Peer들에게 요청하면 되는것이다.
다시 본론으로 돌아와서 머클트리는 따라서 Root값만 가지고 있으면 된다. 그렇기 때문에 Tree의 모든 특성을 반드시 갖고 있어야 하는것은 아니다.
Bottom-Up 구현을 따라서 ArrayList를 이용해 구현해 볼 것이다.

위 사진을 보고 어느정도 이해가 가는가?

---

머클트리와 관련하여 어떻게 머클트리가 생겼는지 알 수 있지만, 실제로 구현하는데에는 어려움이 있을 수 있다. 이전에 작성한 ArrayList와 마찬가지로 기본 아이디어만 본 포스트에서 구현하고, 활용과 응용은 직접 하시길 바란다.

---

위 이미지를 보면 알겠지만, ArrayList에 거래를 집어 넣고, 2개씩 끊어 Hash를 진행하면 된다. 함수 하나로 서론에서 말한 세가지 경우를 모두 처리하는 코드를 만들 수 있지만, 세 방향 모두 나눠서 진행할 것이다.
우선 완벽히 Full Binary Tree를 이룰 수 있을때에 대한 구현 방법이다. 이 경우는 정말 쉬운데, 아래 사진에서 처럼 두개 씩 끊어 Hash를 진행하고, List의 가장 마지막에 오는 녀석이 머클트리의 Root 값이 된다.

private static int getDepth(int size) { return (int) (Math.log10(size) / Math.log10(2)); } public String createBinaryRoot(ArrayList<MerkleNode<Object>> merkleNodes) { int size = 0; int depth = getDepth(merkleNodes.size()); ArrayList<String> datas = new ArrayList<String>(); datas.clear(); for(int i = depth; i > 0; i--) { for(int j = datas.size() % (int) (Math.pow(2, i)); j < (int) (Math.pow(2, i)); j += 2) { if(i == depth) { datas.add(new Crypto().doHash(merkleNodes.get(j).getData().toString() + merkleNodes.get((j+1)).getData().toString())); }else if(i == 1){ datas.add(new Crypto().doHash(datas.get(datas.size()-2) + datas.get(datas.size()-1))); }else { datas.add(new Crypto().doHash(datas.get(j) + datas.get((j+1)))); } } } size = datas.size(); return datas.get(size-1); }

본 코드는 정말 "아이디어의 기초"를 표현하기 위한 코드이다. depth를 구해서 얼마만큼 Hash를 진행하여야 머클트리가 완성되는지를 표현하였다. depth를 다른시각으로 보면 level이 되고, level만큼 부모를 만들어야 root가 되는지 알 수 있기 때문이다. (이진 트리는 log2n 만큼의 depth를 갖고, 따라서 getDepth 함수는 정말 수학식을 나타낸 것이다.)
i가 depth부터 시작하는 이유는 bottomUp 이기 때문에, 아래에서부터 위로 만들기 위함이다.
j는 현재 내가 만들고 있는 List의 사이즈를 2^depth로 나누었을때 나머지인데, 그 이유는 다음과 같다.

총 depth가 4인 트리에서, depth 2에 대해 만들기 시작했을 때, depth 3에는 데이터가 8개 존재한다.
또한 hash를 시작해야 하는 List의 인덱스는 0인데, 그 이유는 List에는 방금 막 만든 해시값들만 담겨있기 때문이다. Depth 2에 대해서 해시가 모두 끝났으면, depth 1로 올라오게 되고, 이 때 hash를 시작해야 하는 인덱스는 9이다. 이 때 List의 사이즈는 12이고, i는 2(최초 depth는 4이고, i가 2번 반복했다. 따라서 4-2=2)가 된다.
즉 12 % 4 = 8이 되고, 0~8에 존재하는 원소는 9개이기 때문에 우리가 찾고자하는 인덱스 9가 된다.

for(int j~) 부분을 보게되면, 우리가 만든 List에서 해당하는 index에 대해 Hash를 진행하고 있는것을 확인할 수 있다.
if(i == 1)인 부분은, i가 1, 즉 root의 자식 노드들이 되고, 따라서 hash를 진행할 때 size -2, size -1을 통해 마지막 두 Hash값에 대해 Hash를 진행하면 Root 값이 나오게 된다.

---

거래가 홀수개

private String createOddRoot(ArrayList<MerkleNode<Object>> merkleNodes) { int size = 0; int depth = getDepth(merkleNodes.size())+1; System.out.println("depth: " + depth); ArrayList<String> datas = new ArrayList<String>(); datas.clear(); int start = 0; int last = merkleNodes.size(); for(int i = depth; i > 0; i--) { start = (i == depth || (i == depth-1) ? 0 : last); last = (i == depth ? merkleNodes.size() : datas.size()); for(int j = start; j < last; j += 2) { if(i == depth) { datas.add( new Crypto().doHash(merkleNodes.get(j).getData().toString() + merkleNodes.get(( (j==last-1 ? (j) : (j+1)) )).getData().toString()) ); } else { datas.add( new Crypto().doHash(datas.get(j) + datas.get( (j==last-1 ? (j) : (j+1)) )) ); } } } size = datas.size(); return datas.get(size-1); }

거래가 홀수일 때는 j의 반복자 시작과 마지막을 잘 설정해주면 된다.
홀수개에 대하여 시작 부분은 최초 트랜잭션을 받아오는 부분과, 그 다음 부분은 모두 0부터 시작하면 된다. 그 이유는 최초 List가 비어있고, 전달받은 거래들에서 데이터를 가져오기 때문이고, 최초 부모들을 만들기 성공했다면, 우리가 만든 List의 0번부터 해시를 진행해야 하기 때문이다.
그 이외의 경우에는 이전 반복자의 last값이 시작값이 되는데, 해시를 시작해야하는 인덱스 번호가 곧 지난번의 마지막 인덱스 이후이기 때문이다. 또한 해당하는 인덱스의 값은 이전 반복자에서 분명히 만들어 졌기 때문에, 이렇게 사용할 수 있는 것이다.
last의 경우, 최초에는 내가 가지고 있는 거래의 수 만큼 해시를 진행해야하고, 그게 아니라면 만들어진 List의 사이즈만큼 만들어야 하기 때문이다.
중요한것은, Hash를 만들 때, 원소가 한개이냐(마지막 홀수번째 원소)만 확인하면 된다.
만약 그렇다면, 본인을 한번 더 사용하면 된다.

datas.add( new Crypto().doHash(datas.get(j) + datas.get( (j==last-1 ? (j) : (j+1)) )) );

---

머클트리는 생각보다 간단하지만, 간단한 만큼 자료가 많지 않아서 어떻게 접근해야 할까 고민하는 사람이 많은 것 같다.
따라서 본 게시글에서는 머클트리는 이루는 기초적인 방향과 이를 바탕으로 한 기초적인 방법을 다루어봤다.
Full Binary Tree가 아닌 짝수 개를 갖는 코드는 위에서 준 힌트와 Odd를 확인해보면 쉽게 만들 수 있다.\
머클트리를 만드는 자세한 방법은 JAVA에서 다루도록 하겠다.