mesh hash resolution with peers

[countvonzero]

design discussion

spacemeshos/SMIPS#51
spacemeshos/SMIPS#60

implementation plan

fetch

add the following to fetch interface

type MeshHashRequest struct {
    From, To     types.LayerID
    Delta, Steps uint32
}

type MeshHashes struct {
    Layers []types.LayerID
    Hashes []types.Hash32
}

type EpochData struct {
    Beacon types.Beacon
    Weight uint64
    AtxIDs []types.ATXID
}

type layerFetcher interface {
    Peers() []p2p.Peer
    PeerEpochInfo(context.Context, p2p.Peer, types.EpochID) (*fetch.EpochData, error)
    PeerMeshHashes(context.Context, p2p.Peer, *fetch.MeshHashRequest) (*fetch.MeshHashes, error)
}

syncer

syncer periodically check peers’ agreement on the mesh hash (aka aggregated hash) along with its layer opinions.

given a list of opinions for layer N from peers, syncer first finds those that differ from the node’s mesh hash at layer N-1. for those peers. pseudo code below:

getMeshAgreement(lid types.LayerID, opinions []*fetch.LayerOpinion) (*fetch.LayerOpinion, error) {
    maxIgnoredWeight uint64
    candidate LayerOpinion
    for opn in opinions {
        if opn.meshHash == nodeMeshHash {
            // update last agreement with peer
            forkFinder.UpdateAgreement(opn.Peer(), lid.Sub(1))
        else {
            epochData = fetch.PeerEpochInfo()
            missing = set_diff(peerAtxIDs, nodeAtxIDs)  // in peerAtxIDs but not in nodeAtxIDs
            err = fetchATX(missing)
            if err {
                // if the node cannot download the ATXs claimed by this peer, 
                // it does not trust this peer's mesh
                continue
            }
            ignoredWeight = total_weight(missing)
            if ignoredWeight > maxIgnoredWeight {
                maxIgnoredWeight = ignoredWeight
                candidate = opn
            }
        }
    }
    
    threshold := (nodeEpochWeight + maxIgnoredWeight).Fraction(s.conf.TortoiseGlobalThreshold)
    if nodeEpochWeight > threshold {
        // the node should still be confident of its mesh
        return nil, nil
    }

    // find the divergent layer and adopt the peer's mesh from there
    fork = forkFinder.FindFork(candidate.Peer(), to, candidate.PrevAggHash)
    adoptPeerMesh(ctx, candidate.Peer(), fork.Add(1), lid.Sub(1))
    // clear the agreement cache after importing new opinions
    s.forkFinder.Purge(true)
    return candidate, nil
}

fork finder

add the following to facilitate finding divergent layer with peers.

type layerHash struct {
    lid     types.LayerID
    hash    types.Hash32
    created time.Time
}

type ForkFinder struct {
    logger           log.Log
    db               *sql.Database
    fetcher          layerFetcher
    // max number of hashes requested from peer in a request
    maxHashesInReq   uint32
    // any cached peer hash will be purged after this duration if the peer is no longer the node's peer list
    maxStaleDuration time.Duration

    mu          sync.Mutex
    // caches the last agreed hash with peer
    agreedPeers map[p2p.Peer]*layerHash
}

// FindFork finds the divergent layer with peer between the last agreed layer and the layer where
// difference is detected.
FindFork(peer p2p.Peer, diffLid types.LayerID, diffHash types.Hash32) (types.LayerID, error) {
}

// UpdateAgreement updates the last layer that node and peer agreed on the mesh hash.
UpdateAgreement(peer p2p.Peer, lid types.LayerID, hash types.Hash32) {
}

basic algorithm

• LA: latest agreement layer, fall back to genesis layer if not available
• OD: oldest disagreement layer
• for each request to peer, make sure the boundary hashes are not changed, as the peer can be going through reorg during the requests
• the number of hashes requested each time is bounded by maxHashesInReq. based on that, calculate the delta layers in each step, and the number of steps between LA and OD to get maxHashesInReq of hashes in requests.

example

assuming

• 3 layers per epoch
• maxHashesInReq is 5
• node and peer X forked at layer 35:
• LA: N/A
• OD: 50

the resulting requests with peer X are

• req 0: [5, 19, 33, 47, 50] -> LA: 33, OD: 47
• req 1: [33, 37, 41, 45, 47] -> LA: 33, OD: 37
• req 2: [33, 34, 35, 36, 37] -> LA: 35, OD: 36 -> fork: 35

adopting a peer's mesh

as per #3573, tortoise will be changed to such that as long as tortoise is fed with new data it will change opinion on the previous layers

assuming syncer decides to adopt the mesh from a confident peer from layer F+1 to N-1, it will first fetch the missing ATXs, and ballots/blocks layer by layer from F+1.

data

• for every new ATX received after its publish epoch
  • call tortoise OnAtx(atx) handler
• for every ballot that reference an ignored ATX
  • call tortoise OnBallot(ballot) handler
  • set the ballot weight to 0 (similar to an malicious ballot)
• all blocks are fetched and saved as usual (call OnBlock(block))

opinions

as per #3573, for genesis, full tortoise using 10 000 layers as a sliding window is completely viable to run. therefore importing opinions from confident peers are not relevant (importing opinions is only relevant for verifying tortoise).

as a result, in the event of network rejoin from a 30/70 split, nodes on the 70-split will remain confident. nodes on the 30-split will do full vote counting on ballots in both sides (self-healing without voting by coin flip) and reach the same mesh hash as the 70-split nodes.

[countvonzero]

this issue is broken down to the following smaller issues:
#2523 separate fetching of layer hash and block IDs
#2524 add aggregated hashes in layer response
#2347 Message server should support error streams
#2526 implement hash resolution in message server
#2525 implement hash resolution in layerfetch
#2527 implement syncer code that drives hash resolution

[countvonzero]

@dshulyak please review the implementation plan described in the issue. thank you.

the requirements on tortoise hopefully is subset of #3573

[dshulyak]

i will take a look, but just a note that tortoise.Rerun is completely removed in the upcoming changes.
as long as tortoise is fed with new data it will change opinion on the previous layers

[dshulyak]

couple of other more general notes:

• there is no need to make any of the tortoise changes described here
• mesh hash resolution should download missing ballots and atxs and fed them to OnAtx (without ignore boolean) and OnBallot handler

so basically there is no need for a distinct thing as tortoise rerun, rerun will be a part of the regular tortoise flow. this is how recovery from 50/50 partition looks like https://github.com/dshulyak/go-spacemesh/blob/rerun-within-window/tortoise/tortoise_test.go#L1563-L1582 . i will be opening prs at the start of the week.

adopting opinion is also not very relevant, i suggest we don't do it for genesis. full tortoise using 10 000 layers as a sliding window is completely viable to run.

[countvonzero]

there is no need to make any of the tortoise changes described here

yay.

mesh hash resolution should download missing ballots and atxs and fed them to OnAtx (without ignore boolean) and OnBallot handler

ok.

adopting opinion is also not very relevant, i suggest we don't do it for genesis. full tortoise using 10 000 layers as a sliding window is completely viable to run.

so essentially, in a 30/70 split, all nodes in 30-split will enter self-healing. correct?

[dshulyak]

so essentially, in a 30/70 split, all nodes in 30-split will enter self-healing. correct?

30-split will count votes in full mode (e.g from both sides) at some point and after that vote consistently with 70-split. but there should be no voting using coin