Solidity에서 머클 트리를 구현하는 방법

머클 트리는 대규모 데이터 구조의 내용을 효율적이고 안전하게 검증할 수 있는 이진 트리입니다. 이 트리의 개념은 1982년 미국의 암호학자인 Ralph Merkle이 제안하고 특허를 받았습니다.

해시의 길이는 입력 데이터의 양에 관계없이 동일하게 유지됩니다. 리프 정점에는 데이터 블록의 해시가 포함되는 반면, 내부 정점에는 두 하위 정점에 값을 추가한 해시가 포함됩니다. 결과적으로 루트 정점은 전체 데이터 세트의 해시로 구성됩니다.

이론

처음에는 어떤 식으로든 서로 관련되지 않은 데이터 세트가 있습니다. (트랜잭션 블록체인의 맥락에서) 각 데이터 블록에 대해 블록의 해시를 계산해야 합니다. 데이터 블록의 수는 2^N 이어야 합니다. 왜냐하면 트리가 구축될 때 이전 블록은 각 반복마다 쌍으로 해싱되기 때문입니다. 그런 다음 한 쌍의 해시가 함께 그룹화되고 이를 기반으로 새 해시가 생성됩니다. 해싱은 각 수준에서 그룹화할 항목이 있는 한 계속되며, 루트 해시(머클 루트)를 얻을 수 있는 쌍이 하나만 남으면 중지됩니다.

H(1-2) = keccak256(H(1) + H(2))

H(3-4) = keccak256(H(3) + H(4))

H(5-6) = keccak256(H(5) + H(6))

H(7-8) = keccak256(H(7) + H(8))

H(1-2-3-4) = keccak256(H(1-2) + H(3-4))

H(5-6-7-8) = keccak256(H(5-6) + H(7-8))

H(1-2-3-4-5-6-7-8) = keccak256(H(1-2-3-4) + H(5-6-7-8))

루트가 있으면 데이터의 유효성을 검사할 수 있습니다. 루트 해시가 원래 해시와 일치하면 모든 것이 정상이며 데이터가 유효합니다. 트리 구조에 특정 데이터가 존재하는지 효율적으로 확인하는 것도 가능하다.

H2 해시가 트리에 존재하는지 확인하고 싶다고 가정해 보겠습니다. 증명은 H1 , H3-4 , H5-6-7-8 데이터 배열입니다. 이러한 해시 덕분에 루트 해시를 재구성할 수 있습니다.

H(1-2-3-4-5-6-7-8) = keccak256(keccak256(keccak256(H(1) + H(2)) + H(3-4)) + H(5-6-7-8))

그런 다음 결과 해시를 원본 해시와 비교합니다. 일치하면 해시 H2 가 트리에 존재한다는 의미입니다.

관행

이제 Solidity에서 Merkle 트리와 데이터 유효성 검사를 구현하는 방법을 살펴보겠습니다.

단순화를 위해 트랜잭션 배열과 해시 배열을 블록체인에 직접 작성하겠습니다. 32바이트의 해시를 반환하는 내장 keccak256 함수를 사용할 것이므로 해시 배열의 데이터 유형은 bytes32 가 됩니다. 배열에는 동적 길이도 있습니다. 일반적으로 해시 배열의 길이는 생성된 해시를 보유하므로 트랜잭션 배열의 길이와 동일하지 않습니다. 길이를 미리 계산할 수 있지만 코드 단순화를 위해 그렇게 하지 않습니다. 원하는 경우 이러한 각 배열을 public 설정하고 트랜잭션의 해시를 읽을 수 있습니다.

생성자에서 hashes 생성합니다. 첫 번째 단계는 루프에 transactions 포함된 블록의 해시를 계산하는 것입니다. 그런 다음 트리의 각 수준에서 해시 수가 2배로 줄어듭니다. 해시를 해시 배열에 저장하므로 인덱스 오프셋을 별도로 저장해야 합니다. 해시를 계산하고 추가할 때 몇 가지 요소를 사용하므로 내부 루프의 반복자는 2씩 증가합니다. 이번에는 abi.encodePacked 에서 인덱스를 올바르게 설정할 각각 2개의 해시를 추가합니다. 왼쪽 요소의 경우 – 현재 이동 오프셋 값 + 현재 트리 수준의 인덱스, 오른쪽 요소의 경우 – 동일 + 1.

그래서 우리는 트리를 만들었지만 관심은 데이터를 검증하는 데 있습니다. 이를 위해 트랜잭션과 해당 인덱스를 사용하는 validateTransaction 함수를 작성해 보겠습니다. 불행하게도 Solidity에는 배열에 대한 find 메소드가 없으므로 트랜잭션 인덱스를 전달하는 것이 더 쉽습니다.

먼저 거래의 해시를 계산하고 일련의 증명을 만들어 보겠습니다. 트랜잭션 배열의 길이에 따라 증명 수를 찾고 proofsIndexes 의 길이를 설정합니다. 그런 다음 트리의 각 수준에서 hashes 의 오프셋을 염두에 두고 오른쪽 또는 왼쪽 요소를 취하여 인덱스에 따라 필요한 요소를 찾습니다. 그런 다음 증명 인덱스 배열을 살펴보고 패리티 인덱스를 확인하고 요소가 쌍에서 왼쪽인지 오른쪽인지에 따라 해시를 계산합니다. 마지막으로 결과 해시를 루트 해시와 비교하고 결과를 반환합니다.

애플리케이션

블록체인에는 머클 트리를 적용하는 여러 가지 방법이 있습니다.

• 트랜잭션 저장 : 예를 들어 비트코인에서 트랜잭션 블록은 해당 트랜잭션의 merkle_root만 저장합니다. 이렇게 하면 블록 크기와 네트워크 부하가 줄어듭니다. 일정 개수의 트랜잭션이 누적되면 공간 절약을 위해 오래된 트랜잭션을 삭제하는 것이 가능하지만 블록 자체는 트리의 루트만 저장하기 때문에 변경되지 않습니다.
• 채굴 : 비트코인 블록은 블록 헤더와 거래 목록의 두 부분으로 구성됩니다. 매번 트랜잭션 해시를 다시 계산할 필요가 없도록 머클 트리에 정렬한 후 전체 블록이 아닌 블록 헤더를 해시하고 임의의 논스 번호를 가져옵니다. 블록이 다른 노드로 전송되면 트랜잭션 목록의 루트를 계산하여 헤더의 루트와 일치하지 않으면 블록이 거부됩니다.
• 검증 : 검증의 핵심은 블록체인 전체를 다운로드하지 않고도 감사하는 것입니다. 프로세스가 대폭 단순화되었으며, 데이터에 대한 정보를 공개하지 않고도 데이터의 존재 여부를 확인할 수 있어 민감한 정보를 확인하는 데 유용할 수 있습니다.

요약

머클 트리가 없으면 블록체인은 너무 번거로울 수 있으며 머클 증명을 통해 데이터 신뢰성을 비용 효율적으로 확인할 수 있습니다.

머클 트리는 트랜잭션을 효율적으로 저장하기 위해 블록체인(예: 비트코인, 이더리움)에서 적극적으로 사용되지만 이것이 유일한 응용 프로그램은 아닙니다. 예를 들어, FTX 거래소가 붕괴된 후 많은 거래소에서는 머클 트리를 활용하는 예비금 증명 메커니즘을 구현했습니다.