Substrate HeaderChain implementation

[tomusdrw]

Initial version of Substrate headerchain (grandpa light-client) using the interface from #204. Should not attempt to unify Ethereum & Substrate initially, fine to be incomplete.

The pallet should be responsible for managing forks and tracking all the mappings required by #204 interface. It would be ideal if it could be re-used with different headers formats and verification mechanisms - i.e. to plug in another network (say Substrate + Babe (no grandpa) or Eth + PoW or BTC) should only require adhering to some interface like this (just a sketch/proposal, not a requirement):

/// basic (cheap) verification of the header
fn verify_header(Self::Header, &CustomStorage) -> bool;
/// import header against latest state.
fn import_header(Self::Header, &mut CustomStorage) -> { finalize, enact, retract };
/// Check proof correctness.
fn verify_proof(Self::Proof, &mut CustomStorage);

CustomStorage should be a chain-specific store for things like ValidatorSets, header extra data, etc. All the things that are not tracked by #204

[tomusdrw]

Updated proposal for providing chain-specific types & verifications:

// contains instructions to the upper module what should happen with the headers.
struct ImportOutcome<HeaderId> {
 finalize: Vec<HeaderId>,
 enact: Vec<HeaderId>,
 retract: Vec<HeaderId>,
}

/// T type will give us access to underlying header storage (might be a different trait)
trait ChainVerifier<T: HeaderChain> {
/// Header type
type Header;
/// Extra data for header import (may contain finality proof, receitps, etc)
type HeaderImportExtraData;
/// A way to access custom storage items that are needed by this particular implementation
type CustomStorage;
/// Supported proof kinds
type Proof;
/// A proof error type
type ProofError: core::fmt::Debug;

/// basic (cheap) verification of the header
fn verify_header(Self::Header, Option<Self::HeaderImportExtraData>, &Self::CustomStorage) -> bool;
/// import header against latest state - this should verify finality internally already.
fn import_header(Self::Header, Option<Self::HeaderImportExtraData> &mut Self::CustomStorage) -> ImportOutcome;
/// Check proof correctness (custom storage mutable to allow for caches)
fn verify_proof(Self::Proof, &mut Self::CustomStorage) -> Result<(), Self::ProofError>;
}


/// And the implementation could look like this:
mod impl {
  trait SubstrateExtraStorage<C: ChainVerifier> {
    fn insert_authority_set(&mut self, ...);
  }

  enum Proof {
    TransactionProof(Vec<u8>),
  }

  struct SubstrateLikeChain;
  impl<T: HeaderChain> ChainVerifier<T> for SubstrateLikeChain {
    type Header = sp_core::generic::Header<...>;
    type HeaderImportExtraData = GrandpaFinalityProof;
    type CustomStorage = Box<dyn SubstrateExtraStorage<Self>>;
    type Proof = Proof;
    type ProofError = String;
  
    fn verify_header(h: Self::Header, Option<Self::HeaderImportExtraData>, &Self::CustomStorage) -> bool {
      // Check that it's latest (although that could done externally in the generic bridge pallet, but it's header to show how to access the storage)
      if T::last_finalized_number() > h.number() {
         false
      } else {
         true
      }
    }
    fn import_header(Self::Header, Option<Self::HeaderImportExtraData>, s: &mut Self::CustomStorage) -> ImportOutcome {
         // TODO: verify header, finality proof (optional), check the authority set, enact the authority set if it changes,
         /// mark some more blocks as finalized, etc.
         s.insert_authority_set(...);
         ImportOutcome {
            ...
         }
    }
    fn verify_proof(proof: Self::Proof, p: &mut Self::CustomStorage) -> Result<(), Self::ProofError> {
          let { header_hash, transaction_proof } = extract_tx_proof(proof)?;
          let header = T::header_by_hash(header_hash);
          if verify_merkle_proof(header.extrinsics_root, transaction_proof) { 
             Ok(())
          } else {
             Err("Invalid Proof")
          }
    }
  }
}

[tomusdrw]

IMHO closed through multiple PRs to substrate pallet. We can make it more generic and abstract in the future, but it deserves a new issue, since this one is outdated.