Skip to content

Latest commit

 

History

History
826 lines (783 loc) · 40 KB

merkle-proof.org

File metadata and controls

826 lines (783 loc) · 40 KB
Raw

Merkle proof

Concepts and purpose

Merkle tree and transaction hashing

Merkle tree
The Merkle tree is a binary tree where each leaf is a hash of an element from a list of elements e.g. transactions in a block, and every parent node up to the root is a hash of its children. The merkle tree summarizes the list of elements into the single hash of the root in a similar way that a single hash over the whole list of elements, but with considerable benefits in terms of computational efficiency and minimized network transfers. Both the Merkle root and the single hash convert the whole list of elements into a single hash, but the Merkle tree allows for efficient verification of inclusion of elements into the list of elements with minimal computation and network transfers, while the single hash requires hashing the whole list of elements for every element inclusion verification. The efficient verification of inclusion of elements in the list of elements is used in blockchains to securely prove and verify the inclusion of a transaction into the list of transactions of a block, specifically for light clients and wallets. For this purpose the Merkle root of all block transactions is included in the block header. The Merkle tree is used to securely verify the integrity of elements in the list of elements. If the computed Merkle root over the received list of elements does not matches the securely provided Merkle root of the original list of elements, then some received elements are corrupted. This characteristic of the Merkle tree is used in blockchains to ensure integrity of transactions in a block that is propagated through the peer-to-peer network. The Merkle tree allows for efficient identification of differences between two lists of elements. This provides an efficient way to compute minimal differences that have to be transmitted over the network in order to synchronize the two lists of elements. This feature is used in distributed source code version control systems e.g. Git and distributed peer-to-peer networks for file sharing e.g. Torrent

Merkle proof and inclusion verification

Merkle proof
The Merkle proof is a list of hashes with the left or right position indication following the Merkle path of the reversed binary search over the Merkle tree starting for the specific element hash in the leaf position up to the Merkle root. The Merkle proof is used for efficient verification of inclusion of elements into the list of elements. The Merkle proof provides to the verifying party the minimal list of required hashes to compute the Merkle root from the hash of the element whose inclusion in a list of elements has to be verified. The Merkle proof starts from the hash of the element in the leaf position, following missing hashes of sibling nodes on the path of the reverse binary search up to the Merkle root. Each hash has attached a position label that indicates the left or the right child of the Merkle tree. This information is used to verify the provided Merkle proof
Merkle proof verification
In order to verify the inclusion of an element into the list of elements the verifying party only needs to securely receive from a trusted source the hash of the element whose inclusion has to be verified, and the Merkle root of the whole list of elements. The verifying party requests the Merkle proof for the hash of the element from the proving party. The proving party derives the Merkle proof from the Merkle tree and the hash of the requested element. The proving party returns the Merkle proof to the verifying party. The verifying party computes the Merkle root iteratively combining hashes from the provided Merkle proof in the indicated by the position labels order. If the computed Merkle root equals to the Merkle root previously received from a trusted source, then the element is included in the list of elements with the high level of security. If the computed Merkle root is not equal to the Merkle root securely received from a trusted source, either the element is not included in the list of elements or the Merkle proof is incorrectly derived or corrupted. Only the hash of the element and the Merkle root of the whole list of elements has to be received from a trusted source. While the Merkle proof can be received from a less trusted source as it is nearly impossible to counterfeit a correct Merkle proof for a list of elements where the requested element is not included
Merkle proof security
The security of the Merkle proof relies on cryptographic characteristics of the underlying hash function. Specifically, the second pre-image resistance and the collision resistance of the hash function. The second pre-image resistance states that given an input and the hash of the input, it is almost impossible to find another input that has the same hash. The second pre-image resistance makes it very difficult to counterfeit a correct Merkle proof for an element that is not included in the list of elements. The collision resistance states that it is almost impossible to find two different inputs that have the same hash. Collisions are inevitable because the output length is fixed, while the input is arbitrary large. The collision resistance makes it very difficult to find the second different list of elements that satisfies the Merkle proof derived from the Merkle tree of the original list of elements. The deterministic nature of the hash function makes Merkle proofs reproducible and verifiable. The Merkle tree allows securely substitute the whole list of elements with a much smaller tree of hashes that uniquely represents the the original list with the added benefit for the efficient verification of inclusion of elements into the list of elements, the verification of integrity of the list of elements, and the efficient way to synchronize out-of-sync lists of elements by transferring minimal differences between the lists of elements
Merkle proof efficiency
The efficiency of Merkle proof relies on the structure of the underlying binary tree with the logarithmic characteristic of the binary search. To verify the inclusion of an element into the list of elements only a log(N) hashes of the Merkle proof have to be transferred over the network, and only log(N) combinations of hashes have to be performed to compute the Merkle root. When not using the Merkle proof, the whole list of elements has to be transferred over the network, the integrity of the list has to be verified, and only then the inclusion of the element can be checked. This results in much larger network transfers and computation overheads needed to verify the integrity of the whole list of elements

Design and implementation

Merkle hash and construction of Merkle tree

Array representation of binary tree
The array representation of a binary tree uses the linear data structure, the array, to store node values for a binary tree. The root of the binary tree is stored in the first position of the array. The two children of the root are stored in the second and the third positions of the array. Next, the children of the first root child are stored in the consecutive array positions and so on. Finally, the leaves of the binary tree are stored at the end of the array, specifically, at starting from the second half of the array. The binary tree is stored in the array sequentially level by level starting from the root down to the leaves. Missing nodes in the binary tree are represented by the default values in the corresponding array positions. The children of a node in the position i are located at the 2i + 1 odd left and the 2i + 2 even right positions. The parent for the odd left child in the position i is located at the (i - 1) / 2 position. The parent for the even right child in the position i is located at the (i - 2) / 2 position. The benefit of the array representation of a binary tree is the compact representation of the binary tree without the overhead of the node links required in the node-based linked representation of the binary tree. Another benefit of the array representation is the fast random access to nodes of the binary tree through the indexing of the array, instead of sequential node-to-node following of links in the linked representation. The next benefit of the array representation is the natural applicability of iterative algorithms that does not consume the call stack, instead of the recursive algorithms that consume the call stack in the case of the linked representation. This implementation of the Merkle tree uses the array representation of the Merkle tree
Merkle hash algorithm
The Merkle hash algorithm constructs the Merkle tree from the list of transactions. The Merkle hash algorithm takes the list of transactions, the typeHash(T) H function to hash a transaction and the pairHash(H, H) H function to combine two hashes of node children in order to produce a parent hash. The Merkle hash algorithm returns the array representation of the constructed Merkle tree as a slice of hashes conforming to the rules of the array representation. The Merkle root is in the first position of the array representation of the Merkle tree. The Merkle hash algorithm is generic. The generic parameters are the type of transactions and the type of hash values e.g. Keccak256, SHA256 that must be comparable. This design allows to apply the Merkle hash algorithm to different types of transactions, and different types of hash functions. Specifically this implementation uses two different hash functions. One hash function is the easy to visualize and debug simple string representation of the hashed value used for learning purposes and testing. The other hash function is the Keccak256 hash function that is used in the implementation of this blockchain, but is much more challenging to debug. The Merkle hash algorithm first checks that the provided list of transactions is not empty. Then the list of transaction hashes is created by applying the type hash function to each transaction in the input list of transactions. Next the length of the array representation of the Merkle tree is calculated, and the Merkle tree array is created. Then the list of transaction hashes if copied into the second half of the Merkle tree array. Next the hashes of transactions are combined in pairs to produce the next level of nodes of the Merkle tree. These nodes are stored just before the list of transaction hashes in the Merkle tree array. The same process iteratively computes hashes of every successive level of parent nodes and stores them just before the nodes of the previous level of the Merkle tree, up until producing the Merkle root in the first position of the Merkle tree array. Hashes of the previous level are needed to construct the next level of nodes in the Merkle tree using the pair hash function. The Merkle hash algorithm
  • Check that the input list of transaction is not empty
  • Produce the list of transaction hashes by applying the type hash function to the input list of transactions
  • Compute the length of the array representation of the Merkle tree
  • Create the array to represent the Merkle tree and initialize the array with default values
  • Copy the list of transaction hashes into the second half of the Merkle tree array
  • Iteratively compute each successive level of nodes by combining pair of hashes from the previous level applying the pair hash function
  • Each next level of nodes is stored in the Merkle tree array just before the previous level of nodes
  • The process of combining pair of hashes continues up until producing the Merkle root in the first position of the Merkle tree array
func MerkleHash[T any, H comparable](
  txs []T, typeHash func(T) H, pairHash func(H, H) H,
) ([]H, error) {
  if len(txs) == 0 {
    return nil, fmt.Errorf("merkle hash: empty transaction list")
  }
  htxs := make([]H, len(txs))
  for i, tx := range txs {
    htxs[i] = typeHash(tx)
  }
  l := int(math.Pow(2, math.Ceil(math.Log2(float64(len(htxs)))) + 1) - 1)
  merkleTree := make([]H, l)
  chd := l / 2
  for i, j := 0, chd; i < len(htxs); i, j = i + 1, j + 1 {
    merkleTree[j] = htxs[i]
  }
  l, par := chd * 2, chd / 2
  for chd > 0 {
    for i, j := chd, par; i < l; i, j = i + 2, j + 1 {
      merkleTree[j] = pairHash(merkleTree[i], merkleTree[i + 1])
    }
    chd /= 2
    l, par = chd * 2, chd / 2
  }
  return merkleTree, nil
}
Transaction hash function
The transaction hash function takes a transaction and returns a hash of the transaction. This implementation uses two different transaction hash functions. One transaction hash function returns the simple string representation of the input value. This transaction hash function is used for learning purposes, testing, debugging, and visual understanding of the internal workings of the Merkle hash, the Merkle prove, and the Merkle verify algorithms. The other transaction hash function is the Keccak256 hash function that is used in the implementation of this blockchain 
// String hash for learning purposes
func typeHashStr(s string) string {
  return s
}
// Keccak256 hash for the blockchain
func NewHash(val any) Hash {
  jval, _ := json.Marshal(val)
  hash := make([]byte, 64)
  sha3.ShakeSum256(hash, jval)
  return Hash(hash[:32])
}
func TxHash(tx SigTx) Hash {
  return NewHash(tx)
}
Pair hash function
The pair hash function combines hashes of a pair of children from the Merkle tree in order to produce the hash of the parent from the next level of nodes of the Merkle tree. This implementation uses two different pair hash functions. One pair hash function is a simple string concatenation of the input hashes. This pair hash function is used for learning purposes, testing, debugging, and visual understanding of the internal workings of the Merkle hash, the Merkle prove, and the Merkle verify algorithms. The combination of input hashes is performed through the concatenation of the string representations of the input hashes. If the hash of the right child is not set and has the default value, the hash of the left child is returned. The other hash function is the Keccak256 hash function that is used in the implementation of this blockchain. If the hash of the right child is not set and has the default value, the hash of the left child is returned 
// String concatenation hash for learning purposes
func pairHashStr(l, r string) string {
  if r == "" {
    return l
  }
  return l + r
}
// Keccak256 hash for the blockchain
func TxPairHash(l, r Hash) Hash {
  var nilHash Hash
  if r == nilHash {
    return l
  }
  return NewHash(l.String() + r.String())
}

Examples of the array representations of the Merkle trees for different input lists of elements using the string hash function and the string concatenation pair hash function

Input list of elementsArray representation of Merkle tree
[1 2 3][123 12 3 1 2 3 _]
[1 2 3 4][1234 12 34 1 2 3 4]
[1 2 3 4 5][12345 1234 5 12 34 5 _ 1 2 3 4 5 _ _ _]
[1 2 3 4 5 6][123456 1234 56 12 34 56 _ 1 2 3 4 5 6 _ _]
[1 2 3 4 5 6 7][1234567 1234 567 12 34 56 7 1 2 3 4 5 6 7 _]
[1 2 3 4 5 6 7 8][12345678 1234 5678 12 34 56 78 1 2 3 4 5 6 7 8]

Merkle prove and derivation of Merkle proof

Merkle proof type
The Merkle proof is a sequence of the proof steps starting from the leaf hash of the specific element, following the missing hashes of sibling nodes on the path of the reverse binary search up until, but not including, the Merkle root. All Merkle proofs start from the hash of the specific element, and end, but do not include, the Merkle root. The Proof type represents a proof step in the Merkle proof of inclusion of the specific element into the list of elements. The proof step contains either a hash of the specific element in the leaf position, or a hash of the combination of hashes of two node children along with the left or right position label of the hash in the Merkle tree. The hash is required to verify the Merkle proof. The position is required to correctly combine hashes of proof steps in the right order during the verification of the Merkle proof. The proof type is generic. The type of the hash value is parameterized. This design allows to use the same Merkle prove algorithm for derivation of Merkle proofs from Merkle trees constructed using different hash functions e.g. Keccak256, SHA256 
type position int

const (
  Left position = 1
  Right position = 2
)

type Proof[H comparable] struct {
  Hash H `json:"hash"`
  Pos position `json:"pos"`
}

func newProof[H comparable](hash H, pos position) Proof[H] {
  return Proof[H]{Hash: hash, Pos: pos}
}
Merkle prove algorithm
The Merkle prove algorithm derives the Merkle proof from the hash of the transaction whose inclusion into the list of transaction has to be proven, and the Merkle tree constructed from the list of transactions. The derived Merkle proof allows a verifying party to securely verify that the requested transaction has been included into the list of transaction of a block, if the computed Merkle root from the provided Merkle proof equals to the Merkle root received from a trusted source. The Merkle proof guides the re-construction of the Merkle root from the hash of the requested transaction by providing the missing hashes of the sibling nodes on the path of the reversed binary search starting from the hash of the transaction in the leaf position and ending, but not including, the Merkle root. The Merkle prove algorithm is generic. The type of the hash value is parameterized. This design allows the Merkle prove algorithm to work without modifications with different Merkle trees produced using different hash functions e.g. Keccak256, SHA256. The derived Merkle proof is also parameterized by the type of the hash value. The Merkle prove algorithm first checks if the input Merkle tree is not empty. Then, the algorithm checks that the hash of the requested transaction is in the second half of the array representation of the provided Merkle tree. If the hash of the transaction is not in the Merkle tree the Merkle proof cannot be derived. Next, the edge cases of the list with one and two transactions (three nodes in the Merkle tree) are handled. Then, the first two steps of the Merkle proof are handled separately because they operate on the same level of the Merkle tree, while all other steps always move one level up until reaching the Merkle root. If the hash of the requested transaction is in the even right position in the Merkle tree, then the odd left sibling hash followed by the transaction hash are included into the Merkle proof. If the hash of the requested transaction is in the odd left position, then the transaction hash followed by the even right sibling hash, if present, are included into the Merkle proof. Next the parent position for the current hash is calculated depending whether the current hash position is even right or odd left following the rules of array representation of the binary tree. When the resulting parent position is even right, the sibling parent position will be odd left in the previous array position. When the resulting parent position is odd left, the sibling parent position will be the even right in the next array position. Finally the sibling parent hash, if present, is included into the Merkle proof with the corresponding position label. Specifically, all even positions are right, and all odd positions are left. The reverse binary search process ends when either the odd left child with the index 1 or the even right child with the index 2 of the Merkle root with the index 0 is reached. The Merkle prove algorithm
  • Check that the provided Merkle tree is not empty
  • Check that the hash of the requested transaction is in the second half of the array representation of the provided Merkle tree
  • Handle the edge cases of the list of one and two transactions
  • Include into the Merkle proof the first two (sometimes one) sibling hashes from the same level of the Merkle tree. One of these hashes will always be the hash of the requested transaction. The other hash may not be present if the input list of transactions did not have a transaction in this position
  • Calculate the position of the parent hash for the current hash
  • Move to the hash of the sibling parent
  • Include the hash of the sibling parent into the Merkle proof with the corresponding position label
  • Stop the process when any of the two children of the Merkle root is reached
func MerkleProve[H comparable](txh H, merkleTree []H) ([]Proof[H], error) {
  if len(merkleTree) == 0 {
    return nil, fmt.Errorf("merkle prove: empty merkle tree")
  }
  start := len(merkleTree) / 2
  i := slices.Index(merkleTree[start:], txh)
  if i == -1 {
    return nil, fmt.Errorf("merkle prove: transaction %v not found", txh)
  }
  i += start
  if len(merkleTree) == 1 {
    return []Proof[H]{newProof(merkleTree[0], Left)}, nil
  }
  if len(merkleTree) == 3 {
    return []Proof[H]{
      newProof(merkleTree[1], Left), newProof(merkleTree[2], Right),
    }, nil
  }
  merkleProof := make([]Proof[H], 0)
  var nilHash H
  if i % 2 == 0 {
    merkleProof = append(merkleProof, newProof(merkleTree[i - 1], Left))
    merkleProof = append(merkleProof, newProof(merkleTree[i], Right))
    i--
  } else {
    merkleProof = append(merkleProof, newProof(merkleTree[i], Left))
    hash := merkleTree[i + 1]
    if hash != nilHash {
      merkleProof = append(merkleProof, newProof(hash, Right))
    }
    i++
  }
  for {
    if i % 2 == 0 {
      i = (i - 2) / 2
    } else {
      i = (i - 1) / 2
    }
    if i % 2 == 0 {
      i--
    } else {
      i++
    }
    hash := merkleTree[i]
    if hash != nilHash {
      if i % 2 == 0 {
        merkleProof = append(merkleProof, newProof(hash, Right))
      } else {
        merkleProof = append(merkleProof, newProof(hash, Left))
      }
    }
    if i == 2 || i == 1 {
      break
    }
  }
  return merkleProof, nil
}

Examples of the correct Merkle proofs for each element of different input lists of elements using the string hash function and the string concatenation pair hash function. Each Merkle proof is a sequence of hashes labeled with the left (L) or the right (R) position needed for the verification of the Merkle proof

Tree (1) [1]
Proof 1 [1-L] valid

Tree (2) [12 1 2]
Proof 1 [1-L 2-R] valid
Proof 2 [1-L 2-R] valid

Tree (3) [123 12 3 1 2 3 _]
Proof 1 [1-L 2-R 3-R] valid
Proof 2 [1-L 2-R 3-R] valid
Proof 3 [3-L 12-L] valid

Tree (4) [1234 12 34 1 2 3 4]
Proof 1 [1-L 2-R 34-R] valid
Proof 2 [1-L 2-R 34-R] valid
Proof 3 [3-L 4-R 12-L] valid
Proof 4 [3-L 4-R 12-L] valid

Tree (5) [12345 1234 5 12 34 5 _ 1 2 3 4 5 _ _ _]
Proof 1 [1-L 2-R 34-R 5-R] valid
Proof 2 [1-L 2-R 34-R 5-R] valid
Proof 3 [3-L 4-R 12-L 5-R] valid
Proof 4 [3-L 4-R 12-L 5-R] valid
Proof 5 [5-L 1234-L] valid

Tree (6) [123456 1234 56 12 34 56 _ 1 2 3 4 5 6 _ _]
Proof 1 [1-L 2-R 34-R 56-R] valid
Proof 2 [1-L 2-R 34-R 56-R] valid
Proof 3 [3-L 4-R 12-L 56-R] valid
Proof 4 [3-L 4-R 12-L 56-R] valid
Proof 5 [5-L 6-R 1234-L] valid
Proof 6 [5-L 6-R 1234-L] valid

Tree (7) [1234567 1234 567 12 34 56 7 1 2 3 4 5 6 7 _]
Proof 1 [1-L 2-R 34-R 567-R] valid
Proof 2 [1-L 2-R 34-R 567-R] valid
Proof 3 [3-L 4-R 12-L 567-R] valid
Proof 4 [3-L 4-R 12-L 567-R] valid
Proof 5 [5-L 6-R 7-R 1234-L] valid
Proof 6 [5-L 6-R 7-R 1234-L] valid
Proof 7 [7-L 56-L 1234-L] valid

Tree (8) [12345678 1234 5678 12 34 56 78 1 2 3 4 5 6 7 8]
Proof 1 [1-L 2-R 34-R 5678-R] valid
Proof 2 [1-L 2-R 34-R 5678-R] valid
Proof 3 [3-L 4-R 12-L 5678-R] valid
Proof 4 [3-L 4-R 12-L 5678-R] valid
Proof 5 [5-L 6-R 78-R 1234-L] valid
Proof 6 [5-L 6-R 78-R 1234-L] valid
Proof 7 [7-L 8-R 56-L 1234-L] valid
Proof 8 [7-L 8-R 56-L 1234-L] valid

Tree (9) [123456789 12345678 9 1234 5678 9 _ 12 34 56 78 9 _ _ _ 1 2 3 4 5 6 7 8 9 _ _ _ _ _ _ _]
Proof 1 [1-L 2-R 34-R 5678-R 9-R] valid
Proof 2 [1-L 2-R 34-R 5678-R 9-R] valid
Proof 3 [3-L 4-R 12-L 5678-R 9-R] valid
Proof 4 [3-L 4-R 12-L 5678-R 9-R] valid
Proof 5 [5-L 6-R 78-R 1234-L 9-R] valid
Proof 6 [5-L 6-R 78-R 1234-L 9-R] valid
Proof 7 [7-L 8-R 56-L 1234-L 9-R] valid
Proof 8 [7-L 8-R 56-L 1234-L 9-R] valid
Proof 9 [9-L 12345678-L] valid

Merkle verify and inclusion verification

Merkle verify algorithm
The Merkle verify algorithm checks the Merkle proof for the inclusion of the specific transaction into the list of transactions of a block. The Merkle verify algorithm takes the hash of the transaction, the Merkle proof, the Merkle root received from a trusted source, and the pair hash function. If the Merkle proof is correct, then the specific transaction is included into the list of transactions of a block. The Merkle proof algorithm is generic. The type of the hash value is parameterized. This design allows to verify Merkle proofs derived from Merkle trees constructed using different hash functions e.g. Keccak256, SHA256. The Merkle verify algorithms first checks that the hash of the requested transaction is in the provided Merkle proof. If the hash is not found in the Merkle proof, than the verification fails. Next the first proof step, which will always be in the left position is taken as the initial hash. Then each successive proof step starting from the second is iteratively applied to the last computed hash in the correct order indicated by the left or right position labels of the proof step until consuming all proof steps from the Merkle proof. The resulting final hash is the computed Merkle root. The computed Merkle root is compared with the Merkle root received from a trusted source. If the computed Merkle root equals to the Merkle root received from a trusted source, that the verification of the Merkle proof is successful, the requested transaction is included into the list of transactions of a block. The Merkle verify algorithm
  • Check that the hash of the requested transaction is in the Merkle proof
  • Start computing the Merkle root from the first hash of the Merkle proof
  • Iteratively apply each successive hash in the correct order indicated by the position label of the proof step to the last computed hash until consuming all proof steps, and, finally, producing the computed Merkle hash
  • If the computed Merkle hash is equal to the Merkle hash received from a trusted source, then the verification is successful, and the transaction is included in the list of transactions of a block
func MerkleVerify[H comparable](
  txh H, merkleProof []Proof[H], merkleRoot H, pairHash func(H, H) H,
) bool {
  i := slices.IndexFunc(merkleProof, func(proof Proof[H]) bool {
    return proof.Hash == txh
  })
  if i == -1 {
    return false
  }
  hash := merkleProof[0].Hash
  for i := 1; i < len(merkleProof); i++ {
    proof := merkleProof[i]
    if proof.Pos == Left {
      hash = pairHash(proof.Hash, hash)
    } else {
      hash = pairHash(hash, proof.Hash)
    }
  }
  return hash == merkleRoot
}

gRPC TxProve method

The gRPC Tx service provides the TxProve method to derive the Merkle proof for the hash of the requested transaction. The interface of the service

message TxProveReq {
  string Hash = 1;
}

message TxProveRes {
  bytes MerkleProof = 1;
}

service Tx {
  rpc TxProve(TxProveReq) returns (TxProveRes);
}

The implementation of the TxProve method

  • Create the iterator over the blocks in the local block store
  • Defer closing the iterator
  • Iterate over each block in the local block store in order. For each block
    • Iterate over each transaction of the confirmed block. For each transaction
      • If the list of transactions of the current block contains the transaction with the requested transaction hash, derive the Merkle proof for the requested transaction hash
        • Create the Merkle tree for the list of transactions of the current block by applying the Merkle hash algorithm
        • Derive the Merkle proof for the requested transaction hash from the constructed Merkle tree by applying the Merkle prove algorithm
        • Encode and return the derived Merkle proof to the caller
      • If the requested transaction hash is not found in any block in the local block store, return the transaction not found error
func (s *TxSrv) TxProve(
  _ context.Context, req *TxProveReq,
) (*TxProveRes, error) {
  blocks, closeBlocks, err := chain.ReadBlocks(s.blockStoreDir)
  if err != nil {
    return nil, status.Errorf(codes.NotFound, err.Error())
  }
  defer closeBlocks()
  for err, blk := range blocks {
    if err != nil {
      return nil, status.Errorf(codes.Internal, err.Error())
    }
    for _, tx := range blk.Txs {
      if tx.Hash().String() == req.Hash {
        merkleTree, err := chain.MerkleHash(
          blk.Txs, chain.TxHash, chain.TxPairHash,
        )
        if err != nil {
          return nil, status.Errorf(codes.Internal, err.Error())
        }
        merkleProof, err := chain.MerkleProve(tx.Hash(), merkleTree)
        if err != nil {
          return nil, status.Errorf(codes.Internal, err.Error())
        }
        jmp, err := json.Marshal(merkleProof)
        if err != nil {
          return nil, status.Errorf(codes.Internal, err.Error())
        }
        res := &TxProveRes{MerkleProof: jmp}
        return res, nil
      }
    }
  }
  return nil, status.Errorf(
    codes.NotFound, fmt.Sprintf("transaction %v not found", req.Hash),
  )
}

gRPC TxVerify method

The gRPC Tx service provides the TxVerify method to verify the provided Merkle proof for the hash of the requested transaction against the Merkle root received from a trusted source, and check whether the requested transaction is included into the list of transactions of a block. The interface of the service

message TxVerifyReq {
  string Hash = 1;
  bytes MerkleProof = 2;
  string MerkleRoot = 3;
}

message TxVerifyRes {
  bool Valid = 1;
}

service Tx {
  rpc TxVerify(TxVerifyReq) returns (TxVerifyRes);
}

The implementation of the TxProve method

  • Decode the provided hash of the requested transaction, the Merkle proof, and the Merkle root
  • Verify that the provided Merkle proof for the requested transaction hash is correct, and confirm that the requested transaction is included in the list of transactions of a block
func (s *TxSrv) TxVerify(
  _ context.Context, req *TxVerifyReq,
) (*TxVerifyRes, error) {
  txh, err := chain.DecodeHash(req.Hash)
  if err != nil {
    return nil, status.Errorf(codes.InvalidArgument, err.Error())
  }
  var merkleProof []chain.Proof[chain.Hash]
  err = json.Unmarshal(req.MerkleProof, &merkleProof)
  if err != nil {
    return nil, status.Errorf(codes.InvalidArgument, err.Error())
  }
  merkleRoot, err := chain.DecodeHash(req.MerkleRoot)
  if err != nil {
    return nil, status.Errorf(codes.InvalidArgument, err.Error())
  }
  valid := chain.MerkleVerify(txh, merkleProof, merkleRoot, chain.TxPairHash)
  res := &TxVerifyRes{Valid: valid}
  return res, nil
}

Testing and usage

Testing Merkle hash, prove, and verify

The TestMerkleHashProveVerify testing process

  • Generate lists of transactions starting from [“1”] to [“1”..”9”] inclusive. For each list of transactions
    • Construct the Merkle tree for the generated list of transactions using the provided transaction hash function and the pair hash function
    • Print the array representation of the constructed Merkle tree
    • Start iterating over the transactions from the generated transaction list. For each transaction
      • Derive the Merkle proof for the transaction hash from the constructed Merkle tree
      • Print the derived Merkle proof
      • Verify the derived Merkle proof for the transaction hash and the constructed Merkle root
      • Verify that the derived Merkle proof is correct
go test -v -cover -coverprofile=coverage.cov ./... -run MerkleHashProveVerify

Testing gRPC TxProve and TxVerify methods

The TestTxProveVerify testing process

  • Create and persist the genesis
  • Create the state from the genesis
  • Create several confirmed blocks on the state and on the local block store
  • Set up the gRPC server and client
  • Create the gRPC transaction client
  • Get the initial owner account from the genesis
  • Search transactions by the sender account address that equals to the initial owner account address
  • Verify that all transactions are found
  • Correct Merkle proofs
    • Call the TxProve method to derive the Merkle proof for the requested transaction hash
    • Call the TxVerify method to verify the derived Merkle proof for the requested transaction hash and the provided Merkle root
    • Verify that Merkle proofs for all found transactions are correct
  • Incorrect Merkle proofs
    • Call the TxProve method to derive the Merkle proof for the requested transaction hash
    • Call the TxVerify method to verify the derived Merkle proof for the requested transaction hash and the provided Merkle root
    • Verify that Merkle proofs for the invalid Merkle root are incorrect
go test -v -cover -coverprofile=coverage.cov ./... -run TxProveVerify

Using tx prove and tx verify commands

The gRPC TxProve and the TxVerify methods are exposed through the CLI. Sign and send transactions to the bootstrap node. Search the confirmed transactions at the bootstrap node. Request the Merkle poofs for the found transactions, and verify the Merkle proofs for all found transactions. Confirm the inclusion of all found transactions into the list of transactions of the corresponding blocks

  • Initialize the blockchain by starting the bootstrap node with parameters for the blockchain initial configuration 
    set boot localhost:1122
set authpass password
set ownerpass password
rm -rf .keystore* .blockstore* # cleanup if necessary
./bcn node start --node $boot --bootstrap --authpass $authpass \
  --ownerpass $ownerpass --balance 1000
  • Create and persist a new account to the local key store of the bootstrap node (in a new terminal) 
    ./bcn account create --node $boot --ownerpass $ownerpass
# acc 0a6c57d451f561d6baefe35bba47f8dd682b31da27f0dfdedc646648ea5d12ba
  • Define a shell function to create, sign, and send a transaction 
    function txSignAndSend -a node from to value ownerpass
  set tx (./bcn tx sign --node $node --from $from --to $to --value $value \
    --ownerpass $ownerpass)
  echo SigTx $tx
  ./bcn tx send --node $node --sigtx $tx
end
  • Create, sign, and send a transaction transferring funds between the initial owner account from the genesis and the new account 
    set acc1 66d614174909403746df7c3222cd74ca386995e4de11cfc99ca1efe548d33105
set acc2 0a6c57d451f561d6baefe35bba47f8dd682b31da27f0dfdedc646648ea5d12ba
txSignAndSend $boot $acc1 $acc2 2 $ownerpass
# SigTx {"from":"66d614174909403746df7c3222cd74ca386995e4de11cfc99ca1efe548d33105","to":"0a6c57d451f561d6baefe35bba47f8dd682b31da27f0dfdedc646648ea5d12ba","value":2,"nonce":1,"time":"2024-11-09T10:27:12.871221439+01:00","sig":"V7WHwt0hOvpI+d6RJErDiO45zj3rzmrb3Yaf1YTVc+d1LUwQhdTtz3OKmvD02jtVkG+DQeUYH9SaxcFd/wsl0gA="}
# tx 4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb
txSignAndSend $boot $acc2 $acc1 1 $ownerpass
# SigTx {"from":"0a6c57d451f561d6baefe35bba47f8dd682b31da27f0dfdedc646648ea5d12ba","to":"66d614174909403746df7c3222cd74ca386995e4de11cfc99ca1efe548d33105","value":1,"nonce":1,"time":"2024-11-09T10:27:12.921031364+01:00","sig":"/V/bwvTnYWnU4GrYvDOp44P1rx6sQZl7b9NXiNefcopqqWOsMyZuUAo00hURL2BWs1xUw24U/7gAvHX+FLg2IwA="}
# tx bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e
  • Search the confirmed transactions involving the initial owner account from the genesis 
    ./bcn tx search --node localhost:1122 --account $acc1
# blk 50de747a5fd220d8c847c2e7fe1e10d4c6915a555f04b9f843c1773a90b9b253
# mrk c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
# tx  4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb
# tx  4312eb8: 66d6141 -> 0a6c57d        2        1    blk    1   50de747   mrk c39f778
# blk 50de747a5fd220d8c847c2e7fe1e10d4c6915a555f04b9f843c1773a90b9b253
# mrk c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
# tx  bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e
# tx  bd84970: 0a6c57d -> 66d6141        1        1    blk    1   50de747   mrk c39f778
  • Define a shell function to request the Merkle proof for the specific transaction hash and verify the Merkle proof which, in turn, confirms the inclusion of the transaction into the list of transactions of a block 
    function txProveAndVerify -a prover verifier hash mrkroot
  set mrkproof (./bcn tx prove --node $prover --hash $hash)
  echo MerkleProof $mrkproof
  echo MerkleRoot $mrkroot
  ./bcn tx verify --node $verifier --hash $hash \
    --mrkproof $mrkproof --mrkroot $mrkroot
end
  • Request the Merkle proof and verify the Merkle proof for all found transactions. Confirm the inclusion of all found transactions in the list of transactions of the corresponding blocks 
    set tx1 4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb
set mrk1 c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
set tx2 bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e
set mrk2 c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
txProveAndVerify $boot $boot $tx1 $mrk1
# MerkleProof [{"hash":"4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb","pos":1},{"hash":"bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e","pos":2}]
# MerkleRoot c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
# tx 4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb valid
txProveAndVerify $boot $boot $tx2 $mrk2
# MerkleProof [{"hash":"4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb","pos":1},{"hash":"bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e","pos":2}]
# MerkleRoot c39f7787a0e1ad825964226031d1ede60f4a8546ce4a5f724321b22ffc3c7394
# tx bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e valid
  • Confirm that the Merkle proof for a transaction with an invalid Merkle root is incorrect 
    set invalidMrk 6040ff5315af566ed974a737dbf460f04e73c9a713ef494e9baacfe7dd5dc8f1
txProveAndVerify $boot $boot $tx1 $invalidMrk
# MerkleProof [{"hash":"4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb","pos":1},{"hash":"bd849704122be82ee588c2abfacb8e12fb5bac0916356babcdb2b1683bbc684e","pos":2}]
# MerkleRoot 6040ff5315af566ed974a737dbf460f04e73c9a713ef494e9baacfe7dd5dc8f1
# tx 4312eb8f506a00c4f4f111ea8b318a871615115e5b1a49f14784c5f90a04baeb INVALID