[Blockchain] MerkleTree 코드 분석 및 구현 with Java

최근 개인 프로젝트를 진행하면서 Merkle Tree를 직접 구현해서 사용할 일이 생겼다. 파일 공유 서비스를 만들고 있는데 기존에 있었던 Merkle Tree 의 개념은 대용량 파일을 전송할때 응용해볼까 생각하고 있고 그 외에 개인적으로 MerkleTree 개념 자체를 새롭게 응용해서 FileTree라는걸 만들어볼까 생각하고 있다. 

 

우선 개념부터 살펴보자. 

 

Merkle Tree는 일종의 해쉬 트리라고도 말할 수 있는데 개념이 워낙 간단해서 그냥 각 트리의 노드에 Hash값을 저장하는데 left와 right 자식의 Hash값을 더하여 Hash한 값을 그 부모가 다시 갖고 있는 구조이다. 즉 이렇게 거슬러 올라가면 root에 가서는 한개의 Hash 값이 나올 것이고 이 값은 leaf부터 hashing을 하면서 거슬러 올라온 구조이기 때문에 leaf 에 있는 요소 중 혹은 그 중간 레벨에 있는 노드들 중  단 하나의 hash값이 변경되면 root의 hash 값도 바뀐다는 아이디어에 근거한 것이다. 즉 그 의미는 감지가능하다는 뜻이다.

 

이야기를 들어보면 금방 감이 올텐데 값이 바뀐 것을 감지할 수 있으며 동시에 아래 레벨에 존재하는 요소 중 하나가 바뀌면 결국 root 의 값이 바뀐다는 강력한 integrity check를 보장한다. (그래서 블록체인에서도 쓰이긴 하지만 원래 쓰였던 곳은 파일 공유를 진행할때 대용량의 파일을 block 단위로 잘라서 각 block들을 leafnode에 우선적으로 hashing 시킨 뒤 최종 root 해쉬를 얻어내서 나중에 무결성 검사를 할때 쓰인다고 한다.)

 

물론 블록체인에서 쓰이는 핵심적인 개념이고 이것을 응용해볼 수 있는 방법을 찾기 위해 개인 프로젝트에 적용하려고 하고 있다. 

 

대략적인 개념을 알아보았으니 이제 실제 코드를 보면서 설명을 진행하겠다. 

 

코드가 그다지 많지 않으니 트리 구현과 관련된 핵심 부분만 살펴보면 단번에 감을 잡을 수 있을 것이다. 

 

우선 트리의 요소를 나타내는 Node 클래스를 살펴보자. 일반적인 트리를 구현할때와 마찬가지로 left와 right로 구성되어있음을 볼 수 있다. 물론 값 대신에 hash를 들고 있는 것을 알 수 있을 것이다. 그냥 트리를 구성하는 Node라는 것을 아는 정도로 이해하고 넘어가도 된다. 

package org.imageghost.Wallet.MerkleTree;

public class Node {
    public Node left;
    public Node right;
    public String hash;

    public Node(Node left, Node right, String hash){
        this.left = left;
        this.right = right;
        this.hash = hash;
    }

    public Node getLeft() {
        return left;
    }

    public Node getRight() {
        return right;
    }

    public String getHash() {
        return hash;
    }

    public void setHash(String hash) {
        this.hash = hash;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

 

핵심 코드를 살펴보기 앞서 먼저 Hash를 생성하는 코드도 잠시 살펴보겠다. 그냥 Hash를 만드는 코드 정도로 이해하고 넘어가도 된다. 

 

참고로 SHA-256 을 사용하고 있다. 그리고 UTF-8로 잡고 있는데 오늘 교수님이 하시는 말씀을 들어보니 예전에는 UTF-8외에 다른 charSet들을 워낙 중구난방으로 써왔는데 최근에는 거의 UTF-8로 통일되어서 그냥 거의 다 UTF-8로 잡아준다고 한다. 

package org.imageghost.Wallet.MerkleTree;

import org.apache.commons.codec.binary.Hex;

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class HashAlgorithm {
    public static String generateHash(String originalString){
        MessageDigest md = null;
        try {
            md = MessageDigest.getInstance("SHA-256");
            md.update(originalString.getBytes("UTF-8"));
        }catch(NoSuchAlgorithmException e){
            e.printStackTrace();
        } catch (UnsupportedEncodingException e) {
            throw new RuntimeException(e);
        }
        return new String(Hex.encodeHexString(md.digest()));
    }
}

 

이제 아래의 코드가 가장 핵심적인 코드이다. 이 코드가 어떻게 돌아가는지 안다면 머클트리의 핵심을 파악한 것이다. (사실 머클트리를 이해하는 것이 이진트리를 이해하는 것과 별 차이가 없다고 생각한다. 내용물을 어떻게 가져가느냐의 차이말고는 거의 아무런 차이도 없다고 생각하다. )

 

package org.imageghost.Wallet.MerkleTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class MerkleTree {
    public static Node generateTree(ArrayList<String> dataBlocks){
        ArrayList<Node> childNodes = new ArrayList<>();
        for(String message: dataBlocks){
            childNodes.add(new Node(null, null, HashAlgorithm.generateHash(message)));
        }
        return buildTree(childNodes);
    }

    public static Node buildTree(ArrayList<Node> children){
        ArrayList<Node> parents = new ArrayList<>();
        while(children.size() != 1){
            int index = 0, length = children.size();
            while(index < length){
                Node leftChild = children.get(index);
                Node rightChild = null;

                if((index + 1) < length){
                    rightChild = children.get(index + 1);
                }else{
                    rightChild = new Node(null, null, leftChild.getHash());
                }
                String parentHash = HashAlgorithm.generateHash(leftChild.getHash() + rightChild.getHash());
                parents.add(new Node(leftChild, rightChild, parentHash));
                index += 2;
            }
            children = parents;
            parents = new ArrayList<>();
        }
        return children.get(0);
    }

    public static void printLevelOrderTraversal(Node root){
        if(root == null){
            return;
        }
        if((root.getLeft() == null && root.getRight() == null)){
            System.out.println(root.getHash());
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);

        while(!queue.isEmpty()){
            Node node = queue.poll();
            if (node != null) {
                System.out.println(node.getHash());
            }else{
                System.out.println();
                if(!queue.isEmpty()){
                    queue.add(null);
                }
            }

            if(node != null && node.getLeft() != null){
                queue.add(node.getLeft());
            }

            if(node != null && node.getRight() != null){
                queue.add(node.getRight());
            }
        }
    }
}

 

generateTree 메서드부터 설명하겠다. 외부로부터 dataBlocks를 ArrayList로 받게 된다. 이 데이터블락은 실제 데이터라고 보면 된다. 그리고 이 arrayList는 절대 leaf node 가 아니다. 이 데이터블락이 곧장 leaf node 가 된다고 생각하는 순간 머클 트리의 개념에 오해가 생긴다. 루프를 돌면서 childNode에 add 를 해주고 있는데 generateHash를 통해 각 블락들을 해쉬화해서 추가해주는 것이 보일 것이다. 즉 실제 데이터 블락들을 hash 해준 값들이 머클 트리의 가장 아래 leaf node 가 되는 것이다. 그렇게 각 블락들을 해쉬해주고 난 뒤 buildTree 를 통해 실제 머클 트리를 생성하는 과정을 거치게 된다. 

 

이제 buildTree에 대해서 알아보자. 진짜 핵심 코드이다. (먼저 생성한 leaf부터 root까지 쭉 쌓아올리는 과정이라고 생각하면 쉬울 것이다.)

while 문을 먼저 돌게 되는데 왜 1까지 limit을 걸어놨을까? 우리는 root 노드를 생성한 순간 더 이상 그 과정을 진행하지 않아도 되기 때문이다. root 까지 생성했으면 거기서 끝인 것이다. 그렇게 해당 while을 돌 것인데 내부적으로 또 while이 존재한다. index가 length보다 작을때까지 돌겠다는 조건인데 이 것은 해당 레벨에 횡으로 존재하는 모든 node들에 대한 처리를 진행하는 logic임을 알 수 있다.

 

leftChild를 해당 index대로 생성하고 rightChild는 일단 null로 둔다. 

 

이후 index +1 이 length 보다 작다면 index +1 에 해당하는 요소를 rightChild로 가져간다. 그런데 else 가 참 흥미롭다. new Node를 하는데 왜 leftChild.getHash()를 가져다가 진행할까라는 생각이 든다. 그렇다면 이제 첫 leafNode의 block이 홀수일 경우를 생각해보자. 마지막에는 leftNode 밖에 존재하지 않는다. 그러니 그냥 rightNode를 leftChild의 hash로 가져가고 parents노드에는 leftNode의 해시값 + leftNode의 해시값으로 해쉬를 해서 가져가겠다는 의미로 해석할 수 있다. 다른 방안이 있을까? Null값 혹은 다른 Default값을 미리 지정해놓고 해쉬할 수도 없고 어찌되었든 해쉬값은 필요한데 이를 위해서 그걸 그냥 요소 하나가 있는 child에서 parent를 생성하기 위해서는 leftChild 쪽의 hash를 두번 쓰는것이다.

마지막 요소일 경우를 check하면서 따로 예외적인 logic을 하나 더 만들어서 진행하기 보다는 이편이 조금 더 성능적으로 낫다는 생각이 든다. 

 

그렇게 횡으로 나아가면서 해당 레벨의 node에 대한 작업을 진행하는데 이때 parents에 추가해준다. 즉 점점 root 쪽으로 가까워지는 것이다. 그리고 내부 while 을 돌면 children = parents 가 있는데 이제 이 parents를 child 로 가정하고 방금 했던 logic을 다시 수행하겠다는 뜻이다. 쭉 진행하고 나면 outer while loop 의 1보다 작거나 같을때의 조건에 걸려서 결국 루트의 요소만 얻게 되는 것이다.

 

printLevelOrderTraversal 이라는 메서드도 있는데 보면 알겠지만 postorder로 순회하면서 트리의 값들을 찍어주는 코드이다. 별반 어려울 내용없는 그냥 print log를 위한 메서드라고 보면 된다. 없어도 된다.

물론 직접 찍어보고 싶으면 들고 있어도 된다. 

 

이제 개인적으로 작성한 테스트코드를 보자. 

 

설명한 것처럼 dataBlocks에 실제 데이터를 넣어두고 generateTree에 전달한다. 결국 내부적으로 buildTree에 의해서 root트리의 Node가 최종적으로 우리에게 전달될 것이다. 

 

그리고 우리는 우리가 직접 각 레벨에 해당하는 해쉬값들을 leaf부터 생성하여 인위적으로 root를 테스트코드 내에서 도출하고 그 값을 buildTree를 해서 생성된 root의 해쉬값과 비교하고 있다. 

 

테스트를 돌려보면 success가 나오고 머클 트리가 문제없이 작동함을 알 수 있다. 

package org.imageghost.Test;

import org.imageghost.Wallet.MerkleTree.HashAlgorithm;
import org.imageghost.Wallet.MerkleTree.MerkleTree;
import org.imageghost.Wallet.MerkleTree.Node;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;

public class MerkleTreeTest {

    @Test
    public void 머클트리_생성_테스트(){
        // given
        ArrayList<String> dataBlocks = new ArrayList<>();
        dataBlocks.add("Captain America");
        dataBlocks.add("Iron Man");
        dataBlocks.add("God of thunder");
        dataBlocks.add("Doctor strange");

        // when
        Node root = MerkleTree.generateTree(dataBlocks);
        MerkleTree.printLevelOrderTraversal(root);

        String level1_val1 = HashAlgorithm.generateHash("Captain America");
        String level1_val2 = HashAlgorithm.generateHash("Iron Man");
        String level1_val3 = HashAlgorithm.generateHash("God of thunder");
        String level1_val4 = HashAlgorithm.generateHash("Doctor strange");

        String level2_val1 = HashAlgorithm.generateHash(level1_val1 + level1_val2);
        String level2_val2 = HashAlgorithm.generateHash(level1_val3 + level1_val4);

        String level3_val1 = HashAlgorithm.generateHash(level2_val1 + level2_val2); // root

        // then
        Assert.assertNotNull(root);
        Assert.assertEquals(level3_val1, root.getHash());
    }
}

 

아래는 테스트 결과로 얻을 수 있는 출력 로그이다. 

 

 

 

위에서 보여진 코드들은 모두 아래 블로그에서 얻을 수 있었다. (이후 FileTree를 만들면서 개인적 취향에 맞게 수정하고 있는 중이다.) 감사합니다.  

---

블록체인은 참 신기한 개념이라고 생각한다. 블록체인이 완벽한 기술이라고는 생각하지 않는다. 분명 모순과 결함이 많다. 그럼에도 불구하고 기술의 흥망과는 별개로 블록체인에서 차용한 기술들이 굉장히 흥미로운 기교들이라고 생각한다. 물론 블록체인의 미래가 어둡다고 생각하지는 않는다. 하지만 현 상황에서 개선되지 않는다면 필연적으로 어두운 미래가 될 것이라고 생각한다.

 

분명 고쳐야할 부분들이 있다. 개인적으로 고치고 싶은 부분들도 있다.(브런치에 작성한 글에서도 언급했지만 개인적으로 생각하길 블록체인의 기본 가정부터 잘못되었다. 이기적인 존재를 가정한 상태에서 이후의 모든 개념이 틀어졌다고 생각한다.)

 

아직은 실력과 지식이 부족해서 내가 어느 부분을 건드리고 어떤 사이드 프로젝트를 진행하면서 풀고자 하는 문제를 풀 수 있을지 감이 잡히진 않는다. 그래서 일단은 익명성을 보장해줄 수 있는 파일 공유 서비스를  만들고 있다. 최대한 내가 배웠던 개념들을 활용해보고자 하기 위함이다. 그냥 배웠던 내용들 중에서 재밌다고 느꼈던 내용들은 죄다 구현해서 붙이고 있다. 

 

아래 블로그가 큰 도움이 되었다. 감사합니다. 조만간 FileTree를 완성한다면! 아니 실제로 구현이 가능하다면! 새로 포스팅을 올리도록 하겠다. 

 

https://www.pranaybathini.com/2021/05/merkle-tree.html

Merkle Tree: Implementation in java and its real world applications