Header Relay Proof for substrate-substrate bridge

[hackfisher]

General

Grandpa authorities are split into different rounds(aka. GrandpaSetId), round are auto increasing number. For each round there exists a Header, which includes a Grandpa Log Digest, defining following ScheduledChange, to indicate the scope start point and members of next Set, start_point = header.height + delay

/// A scheduled change of authority set.
#[cfg_attr(feature = "std", derive(Serialize))]
#[derive(Clone, Eq, PartialEq, Encode, Decode, RuntimeDebug)]
pub struct ScheduledChange<N> {
	/// The new authorities after the change, along with their respective weights.
	pub next_authorities: AuthorityList,
	/// The number of blocks to delay.
	pub delay: N,
}

Util the next ScheduledChange signaled by some Header, and end before the next round start.

The chain will use the grandpa justification to finalize specific header, the struct of Justification is like following:

#[derive(Clone, Encode, Decode, PartialEq, Eq, Debug)]
pub struct GrandpaJustification<Block: BlockT> {
   round: u64,
   pub(crate) commit: Commit<Block>,
   votes_ancestries: Vec<Block::Header>,
}

Terminology

Hs(next_round = i) is the Header signal the ScheduleChange for the next round, its round id is i.
J(r = i, H) is the grandpa justification to finalize Header H using round i.

Note that the round and signatures in the Justification must match with related round's authorities, height of header to finalized must between the round's scope(Hs(next_round=r).height + delay(r) <= ? < Hs(next_round=r+1).height + delay(r+1))

Example:

Source Chain:

Hs(nr=99)    ...   Hs(nr=100)    ...   Hs(nr=101)    ...   Header

Header.height >= Hs(nr=101).height + delay(101), and < Hs(nr=102).height + delay(102) (TODO: Question 1)

Target Chain:

Finalized Header is between Hs(nr=99) and Hs(nr=100)

Current_Finalized_Round = 99

What's the proof bridge relayer need to generate to finalize Header?

It should be
Proof

(
Header, J(r = 101, Header),
[
( Hs(nr=100), J(r=99, H where Hs(nr=100) <=H.height < Hs(nr=100) + delay(100)),
( Hs(nr=101), J(r=100, H where Hs(nr=101) <=H.height < Hs(nr=101) + delay(101))
]
)

Question 1:

How the target chain verify that Header.height >= Hs(nr=101).height + delay(101), and < Hs(nr=102).height + delay(102) if we can not tell the max length of specific round.

Which means, some relayer can use some justification generated by ancient outdated authority set (by bribing) to finalize some source chain header on target chain, because we can not tell how many Hs(nr=?) exists exactly before Header.

To resolve this, we can use some practical methods including max round length settings(usually 1 Era) and add assumption that ancient outdated authority set are not easy to be bribed. Update Hs with more frequency can also help reduce risk.

[boundless-forest]

How the target chain verify that Header.height >= Hs(nr=101).height + delay(101), and < Hs(nr=102).height + delay(102) if we can not tell the max length of specific round.

The key point to finish this verification is to switch to the correct next Authority set list at Hs(nr=101).height + delay(101) account to Hs(nr=101) pre-pending changes set.

because we can not tell how many Hs(nr=?) exists exactly before Header.

In current bridges-common, multiple scheduled changes on the same branch are not allowed when verifying block header in the target chain. Refer to this test for more detailed info https://github.com/paritytech/parity-bridges-common/blob/master/modules/substrate/src/fork_tests.rs#L169

[hackfisher]

Related: paritytech/parity-bridges-common#263

[boundless-forest]

1. Header Relay Design With MMR

The first problem with on-demand relay header is how the Target chain can get the latest authority set changes in a timely manner, as opposed to relaying each header continuously. If this is not possible, then the Target chain cannot verify the correctness of the block. Our solution to this problem is to hard-code a session length that is as consistent as possible with the period of authority set changes. As shown in the figure above, suppose the session length of the source chain is 15 blocks, i.e., the authority set change is theoretically performed every 15 blocks. As an intermediary, relay requests a block from the source chain every 15 block lengths, and then does a justification verification on the requested block.

If the verification fails, the block will not be finalized even if it is relayed to the target chain. The relayer needs to backtrack in the Source chain to find a block that passes both checks and then proceed to the next step.

Assuming that a block passes the verification, it means that the block has met the basic requirements for relay to target chain. Another requirement is that the relayer needs to check the header log with the scheduledChange from all blocks between the finalized height of the target chain and the check passed height because this log contains the list of authority sets for the next session. If a scheduledChange is found, it needs to be submitted to the Target chain along with the header.

2. Message Relay Design With MMR

According to the above header-relay design, the Source chain light client on the Target chain no longer saves every header, so the message relay protocol also needs to be modified. The relayer has to submit to the Target chain not only the block hash and proof of the message call, but also the block header of the block where the message call is made, a block header with a future finalized height, and Justification and MMR proof. Only when all these materials are available, the Target chain can verify the authenticity of the message and execute it on the Target chain side.

Call validation is divided into two parts.

1. Block verification

The correctness of the block is checked using the MMR feature, which is why we need a future high level block and Justification in the message relay.

2. Call validation

After the block is successfully validated on the target chain side, the call validation process uses the features of MPT, which is the same as the original parity-bridges-common.

[hackfisher]

This is the summary and answer of the question in title, moving to wiki:

https://github.com/darwinia-network/darwinia/wiki/Darwinia-Bridge-Proposal