[Deprecated]Darwinia 1.0 Bridge Proposal
Parity Bridges Common parity-bridges-common
By introducing a PARENT_MMR_ROOT digest in each block header, each finalized header can be used to finalize previous history block headers as MMR Root can be seen as a blockchain history commitment.
The pallet for generate this MMR ROOT Digest is in Darwinia Common Library: https://github.com/darwinia-network/darwinia-common/tree/master/frame/header-mmr
With the assumption that:
- Source substrate chain support this pallet
- The grandpa set are changing periodically
We can improve and simplify current header relay design by introducing a super lightclient design which does not need to relay every header and can achieve relay on demand.
We can skip useless headers and finalize the required header(used for later message/event verification) by grouping the proofs, including the grandpa Justifications and mmr proofs.
This proof is not straightforward because it has to handle the grandpa authorities set changes, but providing additional grandpa justification to finalize intermediate signal headers, we can handle it. For details please refer. Header Relay Proof for substrate-substrate bridge
The block header relay design is described as follows:
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.
With the new design, the super grandpa light client on target chain does not include each block header, so storage proof is not enough for verifying against the light client because the header which includes the storage root could not exist on target chain.
But remember that we have MMR root in the header which can finalize previous header, if we enhance the event relay(verify) proof by adding two more data:
- The header contains the storage root for verifying the storage proof.
- The mmr proof that the header is included in the MMR root which is already relayed into the target chain’s super grandpa light client.
Before we describe the detail algorithm, we can take a look at the cross-chain receipt/event verification codes from Darwinia’s Eth-Sub Bridge which are also using super light client with MMR enabled.
Verifying Ethereum Receipt Proof with (EthereumReceiptProof, EthereumHeader, MMRProof):
Verifying Darwinia/Substrate Storage/Event Proof with (StorageProof, Header, MMRProof, Key)
The message relay design is described as follows:
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 storage 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.
- 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.
- 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.
S2S Grandpa Justification Optimization Using BEEFY
Problem: Too large Justification and proof data due to large amounts of validators/authorities.
Solution: Improve this by compressing the justification using a merkle root of a tree of signatures, and interactively verify it using random challenges from light client on the target chain.
For details, refer rationale section of BEEFY
Because the gas fee to verify grandpa ed25519 justification is too high, so we have to replace it with using an ecdsa authority as a replacement of grandpa justification as in Ethereum smart contracts, verifying ecdsa authorities is cheaper.
Implementation Reference:
Grandpa alike authorities replacement: https://github.com/darwinia-network/darwinia-common/tree/master/frame/bridge/relay-authorities
Super light client on Ethereum: https://github.com/darwinia-network/darwinia-bridge-on-ethereum
And we took a look into BEEFY, found that it could be very useful and may share the same envision.
Besides, BEEFY also introduces ideas of using MMR, merkle root and random challenge mechanism to resolve the problem of too many grandpa authorities. As we know in Kusama, there could be 600+ validators/authorities, these could mean large Justification data which is too expensive to transmit and verify.
https://github.com/paritytech/grandpa-bridge-gadget/blob/master/docs/beefy.md