API: Fix prove bug on API (#3632)

## Summary

This PR fixes a bug on algod's API. When a tree contains a missing child (not a full tree), the api handler omits this from the proof response and leads to a root mismatch 

## Test Plan
Add unit tests as well as convert the e2e to test this edge case.

4 files changed, 102 insertions, 17 deletions

diff --git a/crypto/merklearray/proof.go b/crypto/merklearray/proof.go
index c4f35a304..ed05b76e6 100644
--- a/crypto/merklearray/proof.go
+++ b/crypto/merklearray/proof.go
@@ -82,3 +82,17 @@ func (p *SingleLeafProof) GetFixedLengthHashableRepresentation() []byte {
 func (p *SingleLeafProof) ToProof() *Proof {
 	return &p.Proof
 }
+
+// GetConcatenatedProof concats the verification path to a single slice
+// This function converts an empty element in the path (i.e occurs when the tree is not a full tree)
+// into a sequence of digest result of zero.
+func (p *SingleLeafProof) GetConcatenatedProof() []byte {
+	digestSize := p.HashFactory.NewHash().Size()
+	proofconcat := make([]byte, digestSize*int(p.TreeDepth))
+	for i := 0; i < int(p.TreeDepth); i++ {
+		if p.Path[i] != nil {
+			copy(proofconcat[i*digestSize:(i+1)*digestSize], p.Path[i])
+		}
+	}
+	return proofconcat
+}
diff --git a/crypto/merklearray/proof_test.go b/crypto/merklearray/proof_test.go
index 17498e3f8..547268515 100644
--- a/crypto/merklearray/proof_test.go
+++ b/crypto/merklearray/proof_test.go
@@ -132,3 +132,85 @@ func TestProofSerializationOneLeafTree(t *testing.T) {
 	}
 
 }
+
+func TestConcatenatedProofsMissingChild(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	a := require.New(t)
+
+	array := make(TestArray, 7)
+	for i := 0; i < 7; i++ {
+		crypto.RandBytes(array[i][:])
+	}
+
+	tree, err := Build(array, crypto.HashFactory{HashType: crypto.Sha512_256})
+	a.NoError(err)
+
+	p, err := tree.ProveSingleLeaf(6)
+	a.NoError(err)
+
+	newP := SingleLeafProof{Proof: Proof{TreeDepth: p.TreeDepth, Path: []crypto.GenericDigest{}, HashFactory: p.HashFactory}}
+
+	computedPath := recomputePath(p)
+
+	newP.Path = computedPath
+	err = Verify(tree.Root(), map[uint64]crypto.Hashable{6: array[6]}, newP.ToProof())
+	a.NoError(err)
+}
+
+func TestConcatenatedProofsFullTree(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	a := require.New(t)
+
+	array := make(TestArray, 8)
+	for i := 0; i < 8; i++ {
+		crypto.RandBytes(array[i][:])
+	}
+
+	tree, err := Build(array, crypto.HashFactory{HashType: crypto.Sha512_256})
+	a.NoError(err)
+
+	p, err := tree.ProveSingleLeaf(6)
+	a.NoError(err)
+
+	newP := SingleLeafProof{Proof: Proof{TreeDepth: p.TreeDepth, Path: []crypto.GenericDigest{}, HashFactory: p.HashFactory}}
+
+	computedPath := recomputePath(p)
+
+	newP.Path = computedPath
+	err = Verify(tree.Root(), map[uint64]crypto.Hashable{6: array[6]}, newP.ToProof())
+	a.NoError(err)
+}
+
+func TestConcatenatedProofsOneLeaf(t *testing.T) {
+	partitiontest.PartitionTest(t)
+	a := require.New(t)
+
+	array := make(TestArray, 1)
+	crypto.RandBytes(array[0][:])
+
+	tree, err := Build(array, crypto.HashFactory{HashType: crypto.Sha512_256})
+	a.NoError(err)
+
+	p, err := tree.ProveSingleLeaf(0)
+	a.NoError(err)
+
+	newP := SingleLeafProof{Proof: Proof{TreeDepth: p.TreeDepth, Path: []crypto.GenericDigest{}, HashFactory: p.HashFactory}}
+
+	computedPath := recomputePath(p)
+
+	newP.Path = computedPath
+	err = Verify(tree.Root(), map[uint64]crypto.Hashable{0: array[0]}, newP.ToProof())
+	a.NoError(err)
+}
+
+func recomputePath(p *SingleLeafProof) []crypto.GenericDigest {
+	var computedPath []crypto.GenericDigest
+	proofconcat := p.GetConcatenatedProof()
+	for len(proofconcat) > 0 {
+		var d crypto.Digest
+		copy(d[:], proofconcat)
+		computedPath = append(computedPath, d[:])
+		proofconcat = proofconcat[len(d):]
+	}
+	return computedPath
+}
diff --git a/daemon/algod/api/server/v2/handlers.go b/daemon/algod/api/server/v2/handlers.go
index f93467e80..f8f84392c 100644
--- a/daemon/algod/api/server/v2/handlers.go
+++ b/daemon/algod/api/server/v2/handlers.go
@@ -388,20 +388,15 @@ func (v2 *Handlers) GetProof(ctx echo.Context, round uint64, txid string, params
 				return internalError(ctx, err, "building Merkle tree", v2.Log)
 			}
 
-			proof, err := tree.Prove([]uint64{uint64(idx)})
+			proof, err := tree.ProveSingleLeaf(uint64(idx))
 			if err != nil {
 				return internalError(ctx, err, "generating proof", v2.Log)
 			}
 
-			proofconcat := make([]byte, 0)
-			for _, proofelem := range proof.Path {
-				proofconcat = append(proofconcat, proofelem[:]...)
-			}
-
 			stibhash := block.Payset[idx].Hash()
 
 			response := generated.ProofResponse{
-				Proof:     proofconcat,
+				Proof:     proof.GetConcatenatedProof(),
 				Stibhash:  stibhash[:],
 				Idx:       uint64(idx),
 				Treedepth: uint64(proof.TreeDepth),
diff --git a/test/e2e-go/features/transactions/proof_test.go b/test/e2e-go/features/transactions/proof_test.go
index 462f80f40..118e725f7 100644
--- a/test/e2e-go/features/transactions/proof_test.go
+++ b/test/e2e-go/features/transactions/proof_test.go
@@ -50,6 +50,7 @@ func TestTxnMerkleProof(t *testing.T) {
 	partitiontest.PartitionTest(t)
 	defer fixtures.ShutdownSynchronizedTest(t)
 
+	t.Parallel()
 	a := require.New(fixtures.SynchronizedTest(t))
 
 	var fixture fixtures.RestClientFixture
@@ -76,7 +77,8 @@ func TestTxnMerkleProof(t *testing.T) {
 
 	// Transfer some money to acct0, as well as other random accounts to
 	// fill up the Merkle tree with more than one element.
-	for i := 0; i < 10; i++ {
+	// we do not want to have a full tree in order the catch an empty element edge case
+	for i := 0; i < 5; i++ {
 		accti, err := client.GenerateAddress(walletHandle)
 		a.NoError(err)
 
@@ -87,14 +89,6 @@ func TestTxnMerkleProof(t *testing.T) {
 	tx, err := client.SendPaymentFromUnencryptedWallet(baseAcct, acct0, 1000, 10000000, nil)
 	a.NoError(err)
 
-	for i := 0; i < 10; i++ {
-		accti, err := client.GenerateAddress(walletHandle)
-		a.NoError(err)
-
-		_, err = client.SendPaymentFromUnencryptedWallet(baseAcct, accti, 1000, 10000000, nil)
-		a.NoError(err)
-	}
-
 	txid := tx.ID()
 	confirmedTx, err := fixture.WaitForConfirmedTxn(status.LastRound+10, baseAcct, txid.String())
 	a.NoError(err)
@@ -128,7 +122,7 @@ func TestTxnMerkleProof(t *testing.T) {
 	elems[proofresp.Idx] = &element
 	err = merklearray.Verify(blk.TxnRoot.ToSlice(), elems, &proof)
 	if err != nil {
-		t.Logf("blk.TxnRoot : %v \nproof path %v \ndepth: %d \nStibhash %v", blk.TxnRoot.ToSlice(), proof.Path, proof.TreeDepth, proofresp.Stibhash)
+		t.Logf("blk.TxnRoot : %v \nproof path %v \ndepth: %d \nStibhash %v\nIndex: %d", blk.TxnRoot.ToSlice(), proof.Path, proof.TreeDepth, proofresp.Stibhash, proofresp.Idx)
 		a.NoError(err)
 	}