Repository: summa-tx/bitcoin-spv (language: rust)

Issue:
`verifyHash256Merkle` allows existence proofs for the same leaf in multiple locations in the tree
#### Description

`BTCUtils.verifyHash256Merkle` is used by `ValidateSPV.prove` to validate a transaction's existence in a Bitcoin block. The function accepts as input a `_proof` and an `_index`. The `_proof` consists of, in order: the transaction hash, a list of intermediate nodes, and the merkle root.

The proof is performed iteratively, and uses the `_index` to determine whether the next proof element represents a "left branch" or a "right branch:"

https://github.com/summa-tx/bitcoin-spv/blob/f5e4da091a1c97e6432c2d70eba434edb189f919/solidity/contracts/BTCUtils.sol#L574-L586

If `_idx` is even, the computed hash is placed before the next proof element. If `_idx` is odd, the computed hash is placed after the next proof element. After each iteration, `_idx` is decremented by `_idx /= 2`.

Because `verifyHash256Merkle` makes no requirements on the size of `_proof` relative to `_index`, it is possible to pass in invalid values for `_index` that prove a transaction's existence in multiple locations in the tree.

#### Examples

By modifying existing tests, we showed that any transaction can be proven to exist at at least one alternate index. This alternate index is calculated as `(2 ** treeHeight) + prevIndex` - though other alternate indices are possible. The modified test is below:

```
it('verifies a bitcoin merkle root', async () => {
  for (let i = 0; i < verifyHash256Merkle.length; i += 1) {
    const res = await instance.verifyHash256Merkle(
      verifyHash256Merkle[i].input.proof,
      verifyHash256Merkle[i].input.index
    ); // 0-indexed
    assert.strictEqual(res, verifyHash256Merkle[i].output);

    // Now, attempt to use the same proof to verify the same leaf at
    // a different index in the tree:
    let pLen = verifyHash256Merkle[i].input.proof.length;
    let height = ((pLen - 2) / 64) - 2;

    // Only attempt to verify roots that are meant to be verified
    if (verifyHash256Merkle[i].output && height >= 1) {
      let altIdx = (2 ** height) + verifyHash256Merkle[i].input.index;

      const resNext = await instance.verifyHash256Merkle(
        verifyHash256Merkle[i].input.proof,
        altIdx
      );

      assert.strictEqual(resNext, verifyHash256Merkle[i].output);

      console.log('Verified transaction twice!');
    }
  }
});
```

#### Recommendation

Use the length of `_proof` to determine the maximum allowed `_index`. `_index` should satisfy the following criterion: `_index < 2 ** (_proof.length.div(32) - 2)`.

Note that subtraction by 2 accounts for the transaction hash and merkle root, which are assumed to be encoded in the proof along with the intermediate nodes.



Discussion / hints:

Fix patch:
diff --git a/c/csrc/btcspv.c b/c/csrc/btcspv.c
index 8d95d103..48fbb444 100644
--- a/c/csrc/btcspv.c
+++ b/c/csrc/btcspv.c
@@ -183,7 +183,7 @@ byte_view_t btcspv_extract_input_tx_id_le(const_view_t *tx_in) {
   return tx_id_le;
 }
 
-void btcspv_extract_extract_input_tx_id_be(uint256 hash, const_view_t *tx_in) {
+void btcspv_extract_input_tx_id_be(uint256 hash, const_view_t *tx_in) {
   const_view_t le = btcspv_extract_input_tx_id_le(tx_in);
   buf_rev(hash, le.loc, le.len);
 }
diff --git a/c/csrc/btcspv.h b/c/csrc/btcspv.h
index 6066fee7..20bf029f 100644
--- a/c/csrc/btcspv.h
+++ b/c/csrc/btcspv.h
@@ -186,7 +186,7 @@ byte_view_t btcspv_extract_input_tx_id_le(const_view_t *tx_in);
 /// @param input     The input
 /// @warning         overwrites `hash`
 /// @warning         caller must ensure `hash` is allocated and can hold 32 bytes
-void btcspv_extract_extract_input_tx_id_be(uint256 hash, const_view_t *tx_in);
+void btcspv_extract_input_tx_id_be(uint256 hash, const_view_t *tx_in);
 
 /// @brief           Extracts the LE tx input index from the input in a tx
 /// @note            4 byte tx index
@@ -351,6 +351,7 @@ void btcspv_hash256_merkle_step(uint8_t *result, const_view_t *a,
 /// @param proof     The proof. Tightly packed LE sha256 hashes. The last hash is the root
 /// @param index     The index of the leaf
 /// @return          true if the proof is valid, else false
+/// @warning         `index` is not a reliable indicator of location within a block.
 bool btcspv_verify_hash256_merkle(const_view_t *proof, uint32_t index);
 
 /// @brief                  performs the bitcoin difficulty retarget
diff --git a/golang/btcspv/bitcoin_spv.go b/golang/btcspv/bitcoin_spv.go
index c0f6b896..844b01f7 100644
--- a/golang/btcspv/bitcoin_spv.go
+++ b/golang/btcspv/bitcoin_spv.go
@@ -251,7 +251,7 @@ func ExtractOpReturnData(output []byte) ([]byte, error) {
 	}
 
 	dataLen := int(output[10])
-	if dataLen + 8 + 3 > len(output) {
+	if dataLen+8+3 > len(output) {
 		return nil, errors.New("Malformatted data. Read overrun")
 	}
 
@@ -422,7 +422,8 @@ func hash256MerkleStep(a []byte, b []byte) Hash256Digest {
 	return Hash256(c)
 }
 
-// VerifyHash256Merkle checks a merkle inclusion proof's validity
+// VerifyHash256Merkle checks a merkle inclusion proof's validity.
+// Note that `index` is not a reliable indicator of location within a block.
 func VerifyHash256Merkle(proof []byte, index uint) bool {
 	var current Hash256Digest
 	idx := index
diff --git a/golang/cli/prove.go b/golang/cli/prove.go
index 75b87c5f..0b62081b 100644
--- a/golang/cli/prove.go
+++ b/golang/cli/prove.go
@@ -7,6 +7,7 @@ import (
 )
 
 // Prove checks the validity of a merkle proof
+// Note that `index` is not a reliable indicator of location within a block.
 func Prove(
 	version []byte,
 	vin []byte,
diff --git a/js/src/BTCUtils.js b/js/src/BTCUtils.js
index ce240b2e..20262c0a 100644
--- a/js/src/BTCUtils.js
+++ b/js/src/BTCUtils.js
@@ -658,8 +658,9 @@ export function hash256MerkleStep(a, b) {
 
 /**
  *
- * Verifies a Bitcoin-style merkle tree
+ * Verifies a Bitcoin-style merkle tree.
  * Leaves are 0-indexed.
+ * Note that `index` is not a reliable indicator of location within a block.
  *
  * @param {Uint8Array}    proof The proof. Tightly packed LE sha256 hashes.
  *                        The last hash is the root
diff --git a/js/src/ValidateSPV.js b/js/src/ValidateSPV.js
index 1e81b236..e403d50c 100644
--- a/js/src/ValidateSPV.js
+++ b/js/src/ValidateSPV.js
@@ -20,7 +20,8 @@ import * as utils from './utils';
 
 /**
  *
- * Validates a tx inclusion in the block
+ * Validates a tx inclusion in the block.
+ * Note that `index` is not a reliable indicator of location within a block.
  *
  * @param {Uint8Array}    txid The txid (LE)
  * @param {Uint8Array}    merkleRoot The merkle root (as in the block header)
diff --git a/python/btcspv/utils.py b/python/btcspv/utils.py
index fe308060..94948968 100644
--- a/python/btcspv/utils.py
+++ b/python/btcspv/utils.py
@@ -6,6 +6,7 @@ def verify_proof(proof: bytes, index: int) -> bool:
     Verifies a hash256 merkle proof.
     The proof is encoded as a bytestring. The first 32 bytes are the leaf hash,
     the last 32 bytes are the roothash.
+    Note that `index` is not a reliable indicator of location within a block.
     Args:
         proof (bytes): The merkle proof as a bytestring
         index   (int): The 0-indexed position of the leaf in the leafset
diff --git a/python/btcspv/validate_spv.py b/python/btcspv/validate_spv.py
index 26870d4d..c74c0c18 100644
--- a/python/btcspv/validate_spv.py
+++ b/python/btcspv/validate_spv.py
@@ -82,7 +82,10 @@ def extract_prev_block_be(header: bytes) -> bytes:
 def prove(
     txid: bytes, merkle_root: bytes, intermediate_nodes: bytes, index: int) \
         -> bool:
-    '''Validates a tx inclusion in the block'''
+    '''
+    Validates a tx inclusion in the block.
+    Note that `index` is not a reliable indicator of location within a block.
+    '''
     if txid == merkle_root and index == 0 and len(intermediate_nodes) == 0:
         return True
 
diff --git a/rust/src/btcspv.rs b/rust/src/btcspv.rs
index d9bbbf67..a95d2511 100644
--- a/rust/src/btcspv.rs
+++ b/rust/src/btcspv.rs
@@ -595,6 +595,7 @@ pub fn hash256_merkle_step(a: &[u8], b: &[u8]) -> Hash256Digest {
 
 /// Verifies a Bitcoin-style merkle tree.
 /// Leaves are 0-indexed.
+/// Note that `index` is not a reliable indicator of location within a block.
 ///
 /// # Arguments
 ///
diff --git a/rust/src/validatespv.rs b/rust/src/validatespv.rs
index 99942144..9d83f62b 100644
--- a/rust/src/validatespv.rs
+++ b/rust/src/validatespv.rs
@@ -7,6 +7,7 @@ use crate::types::{Hash256Digest, InputType, OutputType, RawHeader, SPVError};
 use crate::utils;
 
 /// Evaluates a Bitcoin merkle inclusion proof.
+/// Note that `index` is not a reliable indicator of location within a block.
 ///
 /// # Arguments
 ///
diff --git a/solidity/contracts/ValidateSPV.sol b/solidity/contracts/ValidateSPV.sol
index a594385b..ebb8b091 100644
--- a/solidity/contracts/ValidateSPV.sol
+++ b/solidity/contracts/ValidateSPV.sol
@@ -35,6 +35,7 @@ library ValidateSPV {
     }
 
     /// @notice                     Validates a tx inclusion in the block
+    /// @dev                        `index` is not a reliable indicator of location within a block
     /// @param _txid                The txid (LE)
     /// @param _merkleRoot          The merkle root (as in the block header)
     /// @param _intermediateNodes   The proof's intermediate nodes (digests between leaf and root)
diff --git a/solidity/contracts/ValidateSPVDelegate.sol b/solidity/contracts/ValidateSPVDelegate.sol
index 33e83a9a..4e078be7 100644
--- a/solidity/contracts/ValidateSPVDelegate.sol
+++ b/solidity/contracts/ValidateSPVDelegate.sol
@@ -20,6 +20,7 @@ library ValidateSPVDelegate {
     }
 
     /// @notice                 Valides a tx inclusion in the block
+    /// @dev                    `index` is not a reliable indicator of location within a block.
     /// @param _txid            The txid (LE)
     /// @param _merkleRoot      The merkle root
     /// @param _proof           The proof (concatenated LE hashes)


Test patch: