mirror of
https://github.com/kaspanet/kaspad.git
synced 2025-08-13 22:23:15 +00:00
e5598c15a7
* add p2p v5 which is currently identical to v4 * set all internal imports to v5 * wip * set default version to 5 * protobuf gen for new ibd chain locator * wire for new ibd chain locator types * new ibd shared block algo -- only basic test passing * address the case where pruning points disagree, now both IBD tests pass * protobuf gen for new past diff request message * wire for new request past diff message * handle and flow for new request past diff message - logic unimplemented yet * implement ibd sync past diff of relay and selected tip * go fmt * remove unused methods * missed one err check * addressing simple comments * apply the traversal limit logic and sort headers * rename pastdiff -> anticone * apply Don't relay blocks in virtual anticone #1970 to v5 * go fmt * Fixed minor comments * Limit the number of chain negotiation restarts
78 lines
2.1 KiB
Go
78 lines
2.1 KiB
Go
package dagtraversalmanager
|
|
|
|
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"
|
|
)
|
|
|
|
func (dtm *dagTraversalManager) AnticoneFromVirtualPOV(stagingArea *model.StagingArea, blockHash *externalapi.DomainHash) (
|
|
[]*externalapi.DomainHash, error) {
|
|
|
|
virtualParents, err := dtm.dagTopologyManager.Parents(stagingArea, model.VirtualBlockHash)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return dtm.AnticoneFromBlocks(stagingArea, virtualParents, blockHash, 0)
|
|
}
|
|
|
|
func (dtm *dagTraversalManager) AnticoneFromBlocks(stagingArea *model.StagingArea, tips []*externalapi.DomainHash,
|
|
blockHash *externalapi.DomainHash, maxTraversalAllowed uint64) (
|
|
[]*externalapi.DomainHash, error) {
|
|
|
|
anticone := []*externalapi.DomainHash{}
|
|
queue := tips
|
|
visited := hashset.New()
|
|
|
|
traversalCounter := uint64(0)
|
|
for len(queue) > 0 {
|
|
var current *externalapi.DomainHash
|
|
current, queue = queue[0], queue[1:]
|
|
|
|
if visited.Contains(current) {
|
|
continue
|
|
}
|
|
|
|
visited.Add(current)
|
|
|
|
currentIsAncestorOfBlock, err := dtm.dagTopologyManager.IsAncestorOf(stagingArea, current, blockHash)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
if currentIsAncestorOfBlock {
|
|
continue
|
|
}
|
|
|
|
blockIsAncestorOfCurrent, err := dtm.dagTopologyManager.IsAncestorOf(stagingArea, blockHash, current)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
// We count the number of blocks in past(tips) \setminus past(blockHash).
|
|
// We don't use `len(visited)` since it includes some maximal blocks in past(blockHash) as well.
|
|
traversalCounter++
|
|
if maxTraversalAllowed > 0 && traversalCounter > maxTraversalAllowed {
|
|
return nil, errors.Wrapf(model.ErrReachedMaxTraversalAllowed,
|
|
"Passed max allowed traversal (%d > %d)", traversalCounter, maxTraversalAllowed)
|
|
}
|
|
|
|
if !blockIsAncestorOfCurrent {
|
|
anticone = append(anticone, current)
|
|
}
|
|
|
|
currentParents, err := dtm.dagTopologyManager.Parents(stagingArea, current)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
for _, parent := range currentParents {
|
|
queue = append(queue, parent)
|
|
}
|
|
}
|
|
|
|
return anticone, nil
|
|
}
|