Repository: kaspanet/kaspad
Pull request #1536 (2021-02-17 15:11:47)

Make antiPastHashesBetween return blocks sorted in ghostdag-order
This PR fixes a performance bug in IBD:

Currently IBD synced block bodies in BFS order, validating against their UTXO-Set blocks that would later not be in the selected-parent-chain. Those blocks are then left as virtualDiffParents, forcing us to update diffs between them and virtual until those are merged.

This PR re-orders the list of blocks returned by antiPastHashesBetween to be in an order where the selectedParent is always first, thus he is the only block in it's merge set that will be validated against UTXO-Set.

codecov[bot]: # [Codecov](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=h1) Report
> Merging [#1536](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=desc) (1095aab) into [v0.9.0-dev](https://codecov.io/gh/kaspanet/kaspad/commit/00a023620d95e4d6ecb52c4b9ae2d775a1421a61?el=desc) (00a0236) will **decrease** coverage by `0.15%`.
> The diff coverage is `35.29%`.

[![Impacted file tree graph](https://codecov.io/gh/kaspanet/kaspad/pull/1536/graphs/tree.svg?width=650&height=150&src=pr&token=2FBIEEJTNU)](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=tree)

```diff
@@              Coverage Diff               @@
##           v0.9.0-dev    #1536      +/-   ##
==============================================
- Coverage       61.75%   61.59%   -0.16%     
==============================================
  Files             507      508       +1     
  Lines           19256    19315      +59     
==============================================
+ Hits            11891    11898       +7     
- Misses           5658     5707      +49     
- Partials         1707     1710       +3     
```


| [Impacted Files](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [domain/consensus/test\_consensus.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy90ZXN0X2NvbnNlbnN1cy5nbw==) | `69.81% <ø> (ø)` | |
| [domain/consensus/test\_consensus\_render\_to\_dot.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy90ZXN0X2NvbnNlbnN1c19yZW5kZXJfdG9fZG90Lmdv) | `0.00% <0.00%> (ø)` | |
| [domain/consensus/processes/syncmanager/antipast.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy9wcm9jZXNzZXMvc3luY21hbmFnZXIvYW50aXBhc3QuZ28=) | `42.42% <53.73%> (-3.88%)` | :arrow_down: |
| [...sensus/processes/dagtraversalmanager/block\_heap.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy9wcm9jZXNzZXMvZGFndHJhdmVyc2FsbWFuYWdlci9ibG9ja19oZWFwLmdv) | `82.08% <0.00%> (-8.96%)` | :arrow_down: |
| [...ersselectedchainstore/headersselectedchainstore.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy9kYXRhc3RydWN0dXJlcy9oZWFkZXJzc2VsZWN0ZWRjaGFpbnN0b3JlL2hlYWRlcnNzZWxlY3RlZGNoYWluc3RvcmUuZ28=) | `73.78% <0.00%> (+5.82%)` | :arrow_up: |
| [...ain/consensus/database/binaryserialization/hash.go](https://codecov.io/gh/kaspanet/kaspad/pull/1536/diff?src=pr&el=tree#diff-ZG9tYWluL2NvbnNlbnN1cy9kYXRhYmFzZS9iaW5hcnlzZXJpYWxpemF0aW9uL2hhc2guZ28=) | `100.00% <0.00%> (+50.00%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=footer). Last update [00a0236...7c77cda](https://codecov.io/gh/kaspanet/kaspad/pull/1536?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/domain/consensus/log.go b/domain/consensus/log.go
index 520dcce8..19fbdc9a 100644
--- a/domain/consensus/log.go
+++ b/domain/consensus/log.go
@@ -2,6 +2,8 @@ package consensus
 
 import (
 	"github.com/kaspanet/kaspad/infrastructure/logger"
+	"github.com/kaspanet/kaspad/util/panics"
 )
 
 var log, _ = logger.Get(logger.SubsystemTags.BDAG)
+var spawn = panics.GoroutineWrapperFunc(log)
diff --git a/domain/consensus/processes/syncmanager/antipast.go b/domain/consensus/processes/syncmanager/antipast.go
index e6cce28e..75ee8fcd 100644
--- a/domain/consensus/processes/syncmanager/antipast.go
+++ b/domain/consensus/processes/syncmanager/antipast.go
@@ -1,14 +1,15 @@
 package syncmanager
 
 import (
+	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/utils/hashset"
 	"github.com/pkg/errors"
 )
 
 // antiPastHashesBetween returns the hashes of the blocks between the
 // lowHash's antiPast and highHash's antiPast, or up to
 // `maxBlueScoreDifference`, if non-zero.
+// The result excludes lowHash and includes highHash. If lowHash == highHash, returns nothing.
 func (sm *syncManager) antiPastHashesBetween(lowHash, highHash *externalapi.DomainHash,
 	maxBlueScoreDifference uint64) ([]*externalapi.DomainHash, error) {
 
@@ -17,19 +18,10 @@ func (sm *syncManager) antiPastHashesBetween(lowHash, highHash *externalapi.Doma
 	// highHash's selectedParentChain.
 	// We keep originalLowHash to filter out blocks in it's past later down the road
 	originalLowHash := lowHash
-	for {
-		isInSelectedParentChain, err := sm.dagTopologyManager.IsInSelectedParentChainOf(lowHash, highHash)
-		if err != nil {
-			return nil, err
-		}
-		if isInSelectedParentChain {
-			break
-		}
-		lowBlockGHOSTDAGData, err := sm.ghostdagDataStore.Get(sm.databaseContext, lowHash)
-		if err != nil {
-			return nil, err
-		}
-		lowHash = lowBlockGHOSTDAGData.SelectedParent()
+	var err error
+	lowHash, err = sm.findLowHashInHighHashSelectedParentChain(lowHash, highHash)
+	if err != nil {
+		return nil, err
 	}
 
 	lowBlockGHOSTDAGData, err := sm.ghostdagDataStore.Get(sm.databaseContext, lowHash)
@@ -55,78 +47,138 @@ func (sm *syncManager) antiPastHashesBetween(lowHash, highHash *externalapi.Doma
 		// Using blueScore as an approximation is considered to be
 		// fairly accurate because we presume that most DAG blocks are
 		// blue.
-		iterator, err := sm.dagTraversalManager.SelectedChildIterator(highHash, lowHash)
+		highHash, err = sm.findHighHashAccordingToMaxBlueScoreDifference(lowHash, highHash, maxBlueScoreDifference, highBlockGHOSTDAGData, lowBlockGHOSTDAGData)
 		if err != nil {
 			return nil, err
 		}
-		for ok := iterator.First(); ok; ok = iterator.Next() {
-			highHash, err = iterator.Get()
-			if err != nil {
-				return nil, err
-			}
-			highBlockGHOSTDAGData, err = sm.ghostdagDataStore.Get(sm.databaseContext, highHash)
+	}
+
+	// Collect all hashes by concatenating the merge-sets of all blocks between highHash and lowHash
+	blockHashes := []*externalapi.DomainHash{}
+	iterator, err := sm.dagTraversalManager.SelectedChildIterator(highHash, lowHash)
+	if err != nil {
+		return nil, err
+	}
+	for ok := iterator.First(); ok; ok = iterator.Next() {
+		current, err := iterator.Get()
+		if err != nil {
+			return nil, err
+		}
+		// Both blue and red merge sets are topologically sorted, but not the concatenation of the two.
+		// We require the blocks to be topologically sorted. In addition,  for optimal performance,
+		// we want the selectedParent to be first.
+		// Since the rest of the merge set is in the anticone of selectedParent, it's position in the list does not
+		// matter, even though it's blue score is the highest, we can arbitrarily decide it comes first.
+		// Therefore we first append the selectedParent, then the rest of blocks in ghostdag order.
+		sortedMergeSet, err := sm.getSortedMergeSet(current)
+		if err != nil {
+			return nil, err
+		}
+
+		// append to blockHashes all blocks in sortedMergeSet which are not in the past of originalLowHash
+		for _, blockHash := range sortedMergeSet {
+			isInPastOfOriginalLowHash, err := sm.dagTopologyManager.IsAncestorOf(blockHash, originalLowHash)
 			if err != nil {
 				return nil, err
 			}
-			if highBlockGHOSTDAGData.BlueScore()-lowBlockGHOSTDAGData.BlueScore()+1 > maxBlueScoreDifference {
-				break
+			if isInPastOfOriginalLowHash {
+				continue
 			}
+			blockHashes = append(blockHashes, blockHash)
 		}
 	}
 
-	// Collect every node in highHash's past (including itself) but
-	// NOT in the lowHash's past (excluding itself) into an up-heap
-	// (a heap sorted by blueScore from lowest to greatest).
-	visited := hashset.New()
-	hashesUpHeap := sm.dagTraversalManager.NewUpHeap()
-	queue := sm.dagTraversalManager.NewDownHeap()
-	err = queue.Push(highHash)
+	// The process above doesn't return highHash, so include it explicitly, unless highHash == lowHash
+	if !lowHash.Equal(highHash) {
+		blockHashes = append(blockHashes, highHash)
+	}
+
+	return blockHashes, nil
+}
+
+func (sm *syncManager) getSortedMergeSet(current *externalapi.DomainHash) ([]*externalapi.DomainHash, error) {
+	currentGhostdagData, err := sm.ghostdagDataStore.Get(sm.databaseContext, current)
 	if err != nil {
 		return nil, err
 	}
-	for queue.Len() > 0 {
-		current := queue.Pop()
-		if visited.Contains(current) {
-			continue
+
+	blueMergeSet := currentGhostdagData.MergeSetBlues()
+	redMergeSet := currentGhostdagData.MergeSetReds()
+	sortedMergeSet := make([]*externalapi.DomainHash, 0, len(blueMergeSet)+len(redMergeSet))
+	selectedParent, blueMergeSet := blueMergeSet[0], blueMergeSet[1:]
+	sortedMergeSet = append(sortedMergeSet, selectedParent)
+	i, j := 0, 0
+	for i < len(blueMergeSet) && j < len(redMergeSet) {
+		currentBlue := blueMergeSet[i]
+		currentBlueGhostdagData, err := sm.ghostdagDataStore.Get(sm.databaseContext, currentBlue)
+		if err != nil {
+			return nil, err
 		}
-		visited.Add(current)
-		var isCurrentAncestorOfLowHash bool
-		if current == lowHash {
-			isCurrentAncestorOfLowHash = false
+		currentRed := redMergeSet[j]
+		currentRedGhostdagData, err := sm.ghostdagDataStore.Get(sm.databaseContext, currentRed)
+		if err != nil {
+			return nil, err
+		}
+		if sm.ghostdagManager.Less(currentBlue, currentBlueGhostdagData, currentRed, currentRedGhostdagData) {
+			sortedMergeSet = append(sortedMergeSet, currentBlue)
+			i++
 		} else {
-			var err error
-			isCurrentAncestorOfLowHash, err = sm.dagTopologyManager.IsAncestorOf(current, lowHash)
-			if err != nil {
-				return nil, err
-			}
+			sortedMergeSet = append(sortedMergeSet, currentRed)
+			j++
 		}
-		if isCurrentAncestorOfLowHash {
-			continue
+	}
+	sortedMergeSet = append(sortedMergeSet, blueMergeSet[i:]...)
+	sortedMergeSet = append(sortedMergeSet, redMergeSet[j:]...)
+
+	return sortedMergeSet, nil
+}
+
+func (sm *syncManager) findHighHashAccordingToMaxBlueScoreDifference(lowHash *externalapi.DomainHash,
+	highHash *externalapi.DomainHash, maxBlueScoreDifference uint64, highBlockGHOSTDAGData *model.BlockGHOSTDAGData,
+	lowBlockGHOSTDAGData *model.BlockGHOSTDAGData) (*externalapi.DomainHash, error) {
+
+	if highBlockGHOSTDAGData.BlueScore()-lowBlockGHOSTDAGData.BlueScore() <= maxBlueScoreDifference {
+		return highHash, nil
+	}
+
+	iterator, err := sm.dagTraversalManager.SelectedChildIterator(highHash, lowHash)
+	if err != nil {
+		return nil, err
+	}
+	for ok := iterator.First(); ok; ok = iterator.Next() {
+		highHashCandidate, err := iterator.Get()
+		if err != nil {
+			return nil, err
 		}
-		// Push current to hashesUpHeap if it's not in the past of originalLowHash
-		isInPastOfOriginalLowHash, err := sm.dagTopologyManager.IsAncestorOf(current, originalLowHash)
+		highBlockGHOSTDAGData, err = sm.ghostdagDataStore.Get(sm.databaseContext, highHashCandidate)
 		if err != nil {
 			return nil, err
 		}
-		if !isInPastOfOriginalLowHash {
-			err = hashesUpHeap.Push(current)
-			if err != nil {
-				return nil, err
-			}
+		if highBlockGHOSTDAGData.BlueScore()-lowBlockGHOSTDAGData.BlueScore() > maxBlueScoreDifference {
+			break
 		}
-		parents, err := sm.dagTopologyManager.Parents(current)
+		highHash = highHashCandidate
+	}
+	return highHash, nil
+}
+
+func (sm *syncManager) findLowHashInHighHashSelectedParentChain(
+	lowHash *externalapi.DomainHash, highHash *externalapi.DomainHash) (*externalapi.DomainHash, error) {
+	for {
+		isInSelectedParentChain, err := sm.dagTopologyManager.IsInSelectedParentChainOf(lowHash, highHash)
 		if err != nil {
 			return nil, err
 		}
-		for _, parent := range parents {
-			err := queue.Push(parent)
-			if err != nil {
-				return nil, err
-			}
+		if isInSelectedParentChain {
+			break
 		}
+		lowBlockGHOSTDAGData, err := sm.ghostdagDataStore.Get(sm.databaseContext, lowHash)
+		if err != nil {
+			return nil, err
+		}
+		lowHash = lowBlockGHOSTDAGData.SelectedParent()
 	}
-
-	return hashesUpHeap.ToSlice(), nil
+	return lowHash, nil
 }
 
 func (sm *syncManager) missingBlockBodyHashes(highHash *externalapi.DomainHash) ([]*externalapi.DomainHash, error) {


Test patch:
diff --git a/app/rpc/rpchandlers/get_blocks_test.go b/app/rpc/rpchandlers/get_blocks_test.go
index b01320b2..0a4dd46d 100644
--- a/app/rpc/rpchandlers/get_blocks_test.go
+++ b/app/rpc/rpchandlers/get_blocks_test.go
@@ -1,6 +1,10 @@
 package rpchandlers_test
 
 import (
+	"reflect"
+	"sort"
+	"testing"
+
 	"github.com/kaspanet/kaspad/app/appmessage"
 	"github.com/kaspanet/kaspad/app/rpc/rpccontext"
 	"github.com/kaspanet/kaspad/app/rpc/rpchandlers"
@@ -12,9 +16,6 @@ import (
 	"github.com/kaspanet/kaspad/domain/dagconfig"
 	"github.com/kaspanet/kaspad/domain/miningmanager"
 	"github.com/kaspanet/kaspad/infrastructure/config"
-	"reflect"
-	"sort"
-	"testing"
 )
 
 type fakeDomain struct {
@@ -65,66 +66,79 @@ func TestHandleGetBlocks(t *testing.T) {
 			return antipast
 		}
 
-		upBfsOrder := make([]*externalapi.DomainHash, 0, 30)
-		selectedParent := params.GenesisHash
-		upBfsOrder = append(upBfsOrder, selectedParent)
+		// Create a DAG with the following structure:
+		//          merging block
+		//         /      |      \
+		//      split1  split2   split3
+		//        \       |      /
+		//         merging block
+		//         /      |      \
+		//      split1  split2   split3
+		//        \       |      /
+		//               etc.
+		expectedOrder := make([]*externalapi.DomainHash, 0, 40)
+		mergingBlock := params.GenesisHash
 		for i := 0; i < 10; i++ {
-			parents := make([]*externalapi.DomainHash, 0, 3)
-			for j := 0; j < 4; j++ {
-				blockHash, _, err := tc.AddBlock([]*externalapi.DomainHash{selectedParent}, nil, nil)
+			splitBlocks := make([]*externalapi.DomainHash, 0, 3)
+			for j := 0; j < 3; j++ {
+				blockHash, _, err := tc.AddBlock([]*externalapi.DomainHash{mergingBlock}, nil, nil)
 				if err != nil {
 					t.Fatalf("Failed adding block: %v", err)
 				}
-				parents = append(parents, blockHash)
-				upBfsOrder = append(upBfsOrder, blockHash)
+				splitBlocks = append(splitBlocks, blockHash)
 			}
-			selectedParent, _, err = tc.AddBlock(parents, nil, nil)
+			sort.Sort(sort.Reverse(testutils.NewTestGhostDAGSorter(splitBlocks, tc, t)))
+			restOfSplitBlocks, selectedParent := splitBlocks[:len(splitBlocks)-1], splitBlocks[len(splitBlocks)-1]
+			expectedOrder = append(expectedOrder, selectedParent)
+			expectedOrder = append(expectedOrder, restOfSplitBlocks...)
+
+			mergingBlock, _, err = tc.AddBlock(splitBlocks, nil, nil)
 			if err != nil {
 				t.Fatalf("Failed adding block: %v", err)
 			}
-			upBfsOrder = append(upBfsOrder, selectedParent)
+			expectedOrder = append(expectedOrder, mergingBlock)
 		}
 
 		virtualSelectedParent, err := tc.GetVirtualSelectedParent()
 		if err != nil {
 			t.Fatalf("Failed getting SelectedParent: %v", err)
 		}
-		if !virtualSelectedParent.Equal(upBfsOrder[len(upBfsOrder)-1]) {
-			t.Fatalf("Expected %s to be selectedParent, instead found: %s", upBfsOrder[len(upBfsOrder)-1], virtualSelectedParent)
+		if !virtualSelectedParent.Equal(expectedOrder[len(expectedOrder)-1]) {
+			t.Fatalf("Expected %s to be selectedParent, instead found: %s", expectedOrder[len(expectedOrder)-1], virtualSelectedParent)
 		}
 
 		requestSelectedParent := getBlocks(virtualSelectedParent)
 		if !reflect.DeepEqual(requestSelectedParent.BlockHashes, hashes.ToStrings([]*externalapi.DomainHash{virtualSelectedParent})) {
-			t.Fatalf("TestSyncManager_GetHashesBetween expected %v\n == \n%v", requestSelectedParent.BlockHashes, virtualSelectedParent)
+			t.Fatalf("TestHandleGetBlocks expected:\n%v\nactual:\n%v", virtualSelectedParent, requestSelectedParent.BlockHashes)
 		}
 
-		for i, blockHash := range upBfsOrder {
-			expectedBlocks := filterAntiPast(blockHash, upBfsOrder)
-			// sort the slice in the order GetBlocks is returning them
-			sort.Sort(sort.Reverse(testutils.NewTestGhostDAGSorter(expectedBlocks, tc, t)))
+		for i, blockHash := range expectedOrder {
+			expectedBlocks := filterAntiPast(blockHash, expectedOrder)
 			expectedBlocks = append([]*externalapi.DomainHash{blockHash}, expectedBlocks...)
 
-			blocks := getBlocks(blockHash)
-			if !reflect.DeepEqual(blocks.BlockHashes, hashes.ToStrings(expectedBlocks)) {
-				t.Fatalf("TestSyncManager_GetHashesBetween %d expected %s\n == \n%s", i, blocks.BlockHashes, hashes.ToStrings(expectedBlocks))
+			actualBlocks := getBlocks(blockHash)
+			if !reflect.DeepEqual(actualBlocks.BlockHashes, hashes.ToStrings(expectedBlocks)) {
+				t.Fatalf("TestHandleGetBlocks %d \nexpected: \n%v\nactual:\n%v", i,
+					hashes.ToStrings(expectedBlocks), actualBlocks.BlockHashes)
 			}
 		}
 
-		// Make explitly sure that if lowHash==highHash we get a slice with a single hash.
-		blocks := getBlocks(virtualSelectedParent)
-		if !reflect.DeepEqual(blocks.BlockHashes, []string{virtualSelectedParent.String()}) {
-			t.Fatalf("TestSyncManager_GetHashesBetween expected blocks to contain just '%s', instead got: \n%s", virtualSelectedParent, blocks.BlockHashes)
+		// Make explicitly sure that if lowHash==highHash we get a slice with a single hash.
+		actualBlocks := getBlocks(virtualSelectedParent)
+		if !reflect.DeepEqual(actualBlocks.BlockHashes, []string{virtualSelectedParent.String()}) {
+			t.Fatalf("TestHandleGetBlocks expected blocks to contain just '%s', instead got: \n%v",
+				virtualSelectedParent, actualBlocks.BlockHashes)
 		}
 
-		sort.Sort(sort.Reverse(testutils.NewTestGhostDAGSorter(upBfsOrder, tc, t)))
-		requestAllViaNil := getBlocks(nil)
-		if !reflect.DeepEqual(requestAllViaNil.BlockHashes, hashes.ToStrings(upBfsOrder)) {
-			t.Fatalf("TestSyncManager_GetHashesBetween expected %v\n == \n%v", requestAllViaNil.BlockHashes, upBfsOrder)
+		expectedOrder = append([]*externalapi.DomainHash{params.GenesisHash}, expectedOrder...)
+		actualOrder := getBlocks(nil)
+		if !reflect.DeepEqual(actualOrder.BlockHashes, hashes.ToStrings(expectedOrder)) {
+			t.Fatalf("TestHandleGetBlocks \nexpected: %v \nactual:\n%v", expectedOrder, actualOrder.BlockHashes)
 		}
 
 		requestAllExplictly := getBlocks(params.GenesisHash)
-		if !reflect.DeepEqual(requestAllExplictly.BlockHashes, hashes.ToStrings(upBfsOrder)) {
-			t.Fatalf("TestSyncManager_GetHashesBetween expected %v\n == \n%v", requestAllExplictly.BlockHashes, upBfsOrder)
+		if !reflect.DeepEqual(requestAllExplictly.BlockHashes, hashes.ToStrings(expectedOrder)) {
+			t.Fatalf("TestHandleGetBlocks \nexpected: \n%v\n. actual:\n%v", expectedOrder, requestAllExplictly.BlockHashes)
 		}
 	})
 }
diff --git a/domain/consensus/model/testapi/test_consensus.go b/domain/consensus/model/testapi/test_consensus.go
index a5199145..dd14b532 100644
--- a/domain/consensus/model/testapi/test_consensus.go
+++ b/domain/consensus/model/testapi/test_consensus.go
@@ -1,11 +1,12 @@
 package testapi
 
 import (
+	"io"
+
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
 	"github.com/kaspanet/kaspad/domain/dagconfig"
 	"github.com/kaspanet/kaspad/infrastructure/db/database"
-	"io"
 )
 
 // MineJSONBlockType indicates which type of blocks MineJSON mines
@@ -50,6 +51,8 @@ type TestConsensus interface {
 	MineJSON(r io.Reader, blockType MineJSONBlockType) (tips []*externalapi.DomainHash, err error)
 	DiscardAllStores()
 
+	RenderDAGToDot(filename string) error
+
 	AcceptanceDataStore() model.AcceptanceDataStore
 	BlockHeaderStore() model.BlockHeaderStore
 	BlockRelationStore() model.BlockRelationStore
diff --git a/domain/consensus/processes/syncmanager/syncmanager_test.go b/domain/consensus/processes/syncmanager/syncmanager_test.go
index d01adaa1..41c6dd03 100644
--- a/domain/consensus/processes/syncmanager/syncmanager_test.go
+++ b/domain/consensus/processes/syncmanager/syncmanager_test.go
@@ -1,14 +1,15 @@
 package syncmanager_test
 
 import (
-	"github.com/kaspanet/kaspad/domain/consensus"
-	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/utils/testutils"
-	"github.com/kaspanet/kaspad/domain/dagconfig"
 	"math"
 	"reflect"
 	"sort"
 	"testing"
+
+	"github.com/kaspanet/kaspad/domain/consensus"
+	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/testutils"
+	"github.com/kaspanet/kaspad/domain/dagconfig"
 )
 
 func TestSyncManager_GetHashesBetween(t *testing.T) {
@@ -20,27 +21,40 @@ func TestSyncManager_GetHashesBetween(t *testing.T) {
 		}
 		defer teardown(false)
 
-		upBfsOrder := make([]*externalapi.DomainHash, 0, 30)
-		selectedParent := params.GenesisHash
-		upBfsOrder = append(upBfsOrder, selectedParent)
+		// Create a DAG with the following structure:
+		//          merging block
+		//         /      |      \
+		//      split1  split2   split3
+		//        \       |      /
+		//         merging block
+		//         /      |      \
+		//      split1  split2   split3
+		//        \       |      /
+		//               etc.
+		expectedOrder := make([]*externalapi.DomainHash, 0, 40)
+		mergingBlock := params.GenesisHash
 		for i := 0; i < 10; i++ {
-			parents := make([]*externalapi.DomainHash, 0, 3)
-			for j := 0; j < 4; j++ {
-				blockHash, _, err := tc.AddBlock([]*externalapi.DomainHash{selectedParent}, nil, nil)
+			splitBlocks := make([]*externalapi.DomainHash, 0, 3)
+			for j := 0; j < 3; j++ {
+				splitBlock, _, err := tc.AddBlock([]*externalapi.DomainHash{mergingBlock}, nil, nil)
 				if err != nil {
 					t.Fatalf("Failed adding block: %v", err)
 				}
-				parents = append(parents, blockHash)
-				upBfsOrder = append(upBfsOrder, blockHash)
+				splitBlocks = append(splitBlocks, splitBlock)
 			}
-			selectedParent, _, err = tc.AddBlock(parents, nil, nil)
+			sort.Sort(sort.Reverse(testutils.NewTestGhostDAGSorter(splitBlocks, tc, t)))
+			restOfSplitBlocks, selectedParent := splitBlocks[:len(splitBlocks)-1], splitBlocks[len(splitBlocks)-1]
+			expectedOrder = append(expectedOrder, selectedParent)
+			expectedOrder = append(expectedOrder, restOfSplitBlocks...)
+
+			mergingBlock, _, err = tc.AddBlock(splitBlocks, nil, nil)
 			if err != nil {
 				t.Fatalf("Failed adding block: %v", err)
 			}
-			upBfsOrder = append(upBfsOrder, selectedParent)
+			expectedOrder = append(expectedOrder, mergingBlock)
 		}
 
-		for i, blockHash := range upBfsOrder {
+		for i, blockHash := range expectedOrder {
 			empty, err := tc.SyncManager().GetHashesBetween(blockHash, blockHash, math.MaxUint64)
 			if err != nil {
 				t.Fatalf("TestSyncManager_GetHashesBetween failed returning 0 hashes on the %d'th block: %v", i, err)
@@ -50,15 +64,13 @@ func TestSyncManager_GetHashesBetween(t *testing.T) {
 			}
 		}
 
-		allHashes, err := tc.SyncManager().GetHashesBetween(upBfsOrder[0], upBfsOrder[len(upBfsOrder)-1], math.MaxUint64)
+		actualOrder, err := tc.SyncManager().GetHashesBetween(params.GenesisHash, expectedOrder[len(expectedOrder)-1], math.MaxUint64)
 		if err != nil {
-			t.Fatalf("TestSyncManager_GetHashesBetween failed returning allHashes: %v", err)
+			t.Fatalf("TestSyncManager_GetHashesBetween failed returning actualOrder: %v", err)
 		}
 
-		sort.Sort(sort.Reverse(testutils.NewTestGhostDAGSorter(upBfsOrder, tc, t)))
-		upBfsOrderExcludingGenesis := upBfsOrder[1:]
-		if !reflect.DeepEqual(allHashes, upBfsOrderExcludingGenesis) {
-			t.Fatalf("TestSyncManager_GetHashesBetween expected %v\n == \n%v", allHashes, upBfsOrder)
+		if !reflect.DeepEqual(actualOrder, expectedOrder) {
+			t.Fatalf("TestSyncManager_GetHashesBetween expected: \n%s\nactual:\n%s\n", expectedOrder, actualOrder)
 		}
 	})
 }
diff --git a/domain/consensus/test_consensus.go b/domain/consensus/test_consensus.go
index c0879e63..91a52b52 100644
--- a/domain/consensus/test_consensus.go
+++ b/domain/consensus/test_consensus.go
@@ -2,6 +2,8 @@ package consensus
 
 import (
 	"encoding/json"
+	"io"
+
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
 	"github.com/kaspanet/kaspad/domain/consensus/model/testapi"
@@ -9,7 +11,6 @@ import (
 	"github.com/kaspanet/kaspad/domain/dagconfig"
 	"github.com/kaspanet/kaspad/infrastructure/db/database"
 	"github.com/pkg/errors"
-	"io"
 )
 
 type testConsensus struct {
diff --git a/domain/consensus/test_consensus_render_to_dot.go b/domain/consensus/test_consensus_render_to_dot.go
new file mode 100644
index 00000000..16f078f8
--- /dev/null
+++ b/domain/consensus/test_consensus_render_to_dot.go
@@ -0,0 +1,79 @@
+package consensus
+
+import (
+	"bytes"
+	"fmt"
+	"io"
+	"io/ioutil"
+	"os/exec"
+	"strings"
+)
+
+// RenderDAGToDot is a helper function for debugging tests.
+// It requires graphviz installed.
+func (tc *testConsensus) RenderDAGToDot(filename string) error {
+	dotScript, _ := tc.convertToDot()
+	return renderDotScript(dotScript, filename)
+}
+
+func (tc *testConsensus) convertToDot() (string, error) {
+	var dotScriptBuilder strings.Builder
+	dotScriptBuilder.WriteString("digraph {\n\trankdir = TB; \n")
+
+	edges := []string{}
+
+	blocksIterator, err := tc.blockStore.AllBlockHashesIterator(tc.databaseContext)
+	if err != nil {
+		return "", err
+	}
+
+	for ok := blocksIterator.First(); ok; ok = blocksIterator.Next() {
+		hash, err := blocksIterator.Get()
+		if err != nil {
+			return "", err
+		}
+		dotScriptBuilder.WriteString(fmt.Sprintf("\t\"%s\";\n", hash))
+
+		parents, err := tc.dagTopologyManager.Parents(hash)
+		if err != nil {
+			return "", err
+		}
+
+		for _, parentHash := range parents {
+			edges = append(edges, fmt.Sprintf("\t\"%s\" -> \"%s\";", hash, parentHash))
+		}
+	}
+
+	dotScriptBuilder.WriteString("\n")
+
+	dotScriptBuilder.WriteString(strings.Join(edges, "\n"))
+
+	dotScriptBuilder.WriteString("\n}")
+
+	return dotScriptBuilder.String(), nil
+}
+
+func renderDotScript(dotScript string, filename string) error {
+	command := exec.Command("dot", "-Tsvg")
+	stdin, err := command.StdinPipe()
+	if err != nil {
+		return fmt.Errorf("Error creating stdin pipe: %s", err)
+	}
+	spawn("renderDotScript", func() {
+		defer stdin.Close()
+
+		_, err = io.WriteString(stdin, dotScript)
+		if err != nil {
+			panic(fmt.Errorf("Error writing dotScript into stdin pipe: %s", err))
+		}
+	})
+
+	var stderr bytes.Buffer
+	command.Stderr = &stderr
+	svg, err := command.Output()
+	if err != nil {
+		return fmt.Errorf("Error getting output of dot: %s\nstderr:\n%s", err, stderr.String())
+	}
+
+	return ioutil.WriteFile(filename, svg, 0600)
+}