Implement warp sync provider

[EclesioMeloJunior]

Description

The warp sync protocols allow nodes to retrieve blocks from remote peers where authority set changes occurred

ref 4.8.5. Warp Sync

The warp sync provider should implement the following interface

type WarpSyncProvider interface {
    // Generate proof starting at given block hash. The proof is accumulated until maximum proof
    // size is reached.
    generate(startHeader: *types.Header) (encodedProof []byte, err error)

    // Get current list of authorities. This is supposed to be genesis authorities when starting sync.
    current_authorities() []types.Authorities
}

It is implemented inside the grandpa package, the generate method should return an SCALE encoded payload of the following struct

type WarpSyncFragment struct {
  // The last block that the given authority set finalized. This block should contain a digest
  // signaling an authority set change from which we can fetch the next authority set.
  header types.Header

  // A justification for the header above which proves its finality. In order to validate it the
  // verifier must be aware of the authorities and set id for which the justification refers to.
  justification types.GrandpaJustification
}

type WarpSyncProof struct {
  proofs []WarpSyncFragment

  // indicates whether the warp sync has been completed
  isFinished bool
}

Some things to considerate:

• The argument startHeader should not be greater than the current highest finalized header
• The argument startHeader should point to a canonical header (already imported block stored in the database)

Here is a suggested implementation based on substrate

func GenerateProof(state BlockState, begin types.Hash, authoritySetChanges ...) (*WarpSyncProof, error) {
     // check if begin hash is a canonical block

     // allChangesSince should exclude the begin block
     // and return the blocks header
     setChanges := authoritySetChanges.allChangesSince(begin)

     proofsEncodedLen := 0
     proofs := make([]WarpSyncFragment, 0)
     limitReached = false
     for _, header := range setChanges {
         // the header should contains a standard scheduled change
         // otherwise  the set must have changed through a forced changed, 
         // in which case we stop collecting proofs as the chain of trust in authority handoffs was broken.

         justification := // get the justification of such block
         fragment := WarpSyncFragment { header: header, justification: justification }

         // check the proof size
         const MAX_WARP_SYNC_PROOF_SIZE = 8 * 1024 * 1024;

         encodedFragment := scale.Marshal(fragment)
         if proofsEncodedLen + encodedFragment >= MAX_WARP_SYNC_PROOF_SIZE {
            limitReached = true;
            break
         }
     }

     // in substrate if the limit is not reached then they retrieve the latest (best) justification
     // and append in the proofs
     if !limitReached { ... }
}

One thing to considerate is:

• How can we retrieve all the authority changes that happens since the beging hash? Can we do that in a single database interaction? can we store them in a fast layer? substrate uses a struct called AuthoritySetChanges, looks like this slice keeps in the mem for the lifetime of the application.

/// Tracks historical authority set changes. We store the block numbers for the last block
/// of each authority set, once they have been finalized. These blocks are guaranteed to
/// have a justification unless they were triggered by a forced change.
#[derive(Debug, Encode, Decode, Clone, PartialEq)]
pub struct AuthoritySetChanges<N>(Vec<(u64, N)>);