# Light client bridge

Light client bridge will relay every block from source chain to target chain, normally for asset transfer just need to lock asset in some backing module or smart contract in source chain and mint the mapping asset in target chain

## Components

Since the chain cannot directly access each other, the cross-chain data submission needs to be completed by a third party. This third party is the bridge relayers.
Anyone can become a bridge relayer, and the bridge relayer obtains income by completing the relay task between the bridges. This incentive can promote the stable existence of bridge relayers to ensure the bridge’s regular operation.


## Reference Implementation

Actually Parity officially provide a poc project illustrated in [poa-eth guidance]( https://github.com/paritytech/parity-bridges-common/blob/master/docs/poa-eth.md)

## Challenges

- [grandpa signature verification](https://github.com/svyatonik/substrate-bridge-sol/blob/master/substrate-bridge.sol) : too expensive
- [eip 665](https://eips.ethereum.org/EIPS/eip-665 ) : not ready

## Merkle Mountain Ranges

Merkle mountain ranges are just merkle trees with an efficient append operation. leaf nodes contais block header in chain，super light client not nessessary to download all the block heades，e.g. only data marked as following is required to download from full node to verify transaction in leaf index 15 is valid


### MMR proof

build merkle proof of leaf node including 3 steps:

- build merkle proof of nodes from leaf to peak
- add proof of right peaks
- add proof of left peaks from right to left

### MMR root

Node(p) = Blake2b(m | Node(left_child(p)) | Node(right_child(p)))

## MMR in substrate

pub trait MmrApi<Hash: codec::Codec> {
    /// Generate MMR proof for a leaf under given index.
    #[skip_initialize_block]
    fn generate_proof(leaf_index: u64) -> Result<(EncodableOpaqueLeaf, Proof<Hash>), Error>;

    /// Verify MMR proof against on-chain MMR.
    ///
    /// Note this function will use on-chain MMR root hash and check if the proof
    /// matches the hash.
    /// See [Self::verify_proof_stateless] for a stateless verifier.
    #[skip_initialize_block]
    fn verify_proof(leaf: EncodableOpaqueLeaf, proof: Proof<Hash>) -> Result<(), Error>;

    /// Verify MMR proof against given root hash.
    ///
    /// Note this function does not require any on-chain storage - the
    /// proof is verified against given MMR root hash.
    ///
    /// The leaf data is expected to be encoded in it's compact form.
    #[skip_initialize_block]
    fn verify_proof_stateless(root: Hash, leaf: EncodableOpaqueLeaf, proof: Proof<Hash>)
        -> Result<(), Error>;
}

impl pallet_mmr::Config for Runtime {
    const INDEXING_PREFIX: &'static [u8] = b"mmr";
    type Hashing = Keccak256;
    type Hash = <Keccak256 as traits::Hash>::Output;
    type OnNewRoot = mmr_common::DepositBeefyDigest<Runtime>;
    type WeightInfo = ();
    type LeafData = mmr_common::Pallet<Runtime>;
}

## [Beefy protocol](https://github.com/paritytech/grandpa-bridge-gadget/blob/master/docs/beefy.md)

To overcome the difficulty with GRANDPA finality proofs a separate round of BFT agreement is required where each voter will be voting on the MMR root of the latest block finalized by GRANDPA which using ECDSA for easier Ethereum compatibility and steps as following:

- listen to GRANDPA finality notifications
- finalize new blocks and start a new BEEFY round for:

last_block_with_signed_mmr_root + NextPowerOfTwo((last_finalized_block - last_block_with_signed_mmr_root) / 2)

- fetch the MMR root for the given block (currently from a header digest)
- create a BEEFY commitment where the payload is the signed MMR root for the given block

struct Commitment<BlockNumber, Payload> {
    //mmr root
    payload: Payload,
    block_number: BlockNumber,
    //from session modules
    validator_set_id: ValidatorSetId,
}

- gossip our vote and listen for any votes for that round, waiting until received > 2/3.

### Beefy in polkadot runtime

    //start beefy(current only in rococo service)
    let beefy_params = beefy_gadget::BeefyParams {
    client,
    backend,
    key_store: keystore.clone(),
    network: network.clone(),
    signed_commitment_sender,
    min_block_delta: 4,
    prometheus_registry: prometheus_registry.clone(),
};

// Start the BEEFY bridge gadget.
task_manager.spawn_essential_handle().spawn_blocking(
    "beefy-gadget",
    beefy_gadget::start_beefy_gadget::<_, _, _, _>(beefy_params),
);

impl mmr_common::Config for Runtime {
	type BeefyAuthorityToMerkleLeaf = mmr_common::UncompressBeefyEcdsaKeys;
	type ParachainHeads = Paras;
}

### Integrate MMR with Beefy

/// A BEEFY consensus digest item with MMR root hash.
pub struct DepositBeefyDigest<T>(sp_std::marker::PhantomData<T>);

impl<T> pallet_mmr::primitives::OnNewRoot<beefy_primitives::MmrRootHash> for DepositBeefyDigest<T> where
	T: pallet_mmr::Config<Hash = beefy_primitives::MmrRootHash>,
	T: pallet_beefy::Config,
{
	fn on_new_root(root: &<T as pallet_mmr::Config>::Hash) {
		let digest = sp_runtime::generic::DigestItem::Consensus(
			beefy_primitives::BEEFY_ENGINE_ID,
			parity_scale_codec::Encode::encode(
				&beefy_primitives::ConsensusLog::<<T as pallet_beefy::Config>::BeefyId>::MmrRoot(*root)
			),
		);
		<frame_system::Pallet<T>>::deposit_log(digest);
	}
}


# Snowfork Bridge

[Snowbridge](https://github.com/Snowfork/snowbridge) has a layered architecture with a seperation between low level bridge functionality, mid level trust functionality and high level application functionality.


## Trust Layer

### [Ethereum MPT verification in Substrate](https://github.com/Snowfork/snowbridge/tree/main/parachain/pallets/verifier-lightclient)

// Validate an Ethereum header&ethash proof for import
fn validate_header_to_import(header: &EthereumHeader, proof: &[EthashProofData]) -> DispatchResult {
  ...
}

### [Beefy light client smart contract in Ethereum](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/BeefyLightClient.sol)

## Bridge Layer

guarantee basic deliverability and replay protection and with incentivized bridge adding a strict message ordering channels in both directions.

### Ethereum → Substrate
There is a channel for sending Polkadot RPCs out from Ethereum to Polkadot via events. It consists of [OutboundChannel contract on the Ethereum side](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/BasicOutboundChannel.sol) and a corresponding [InboudChannel on the parachain side](https://github.com/Snowfork/snowbridge/blob/main/parachain/pallets/basic-channel/src/inbound/mod.rs), workflow as following:


### Substrate → Ethereum
There is a [OutboundChannel on the parachain side](https://github.com/Snowfork/snowbridge/blob/main/parachain/pallets/basic-channel/src/outbound/mod.rs) for sending Ethereum RPCs out from the parachain to Ethereum. It is responsible for accepting requests from other pallets and parachains for messages to be sent over to the correspongding [InboundChannel smart contract](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/BasicInboundChannel.sol)

## App layer and Relayer Implementation

Ethereum → Substrate Relayer is pretty straightforward so just skip and jump to Substrate → Ethereum part

start from invoking app requests (e.g lock polkadot dot asset ) into [Parachain Message Commitments](https://snowbridge-docs.snowfork.com/concepts/components#parachain-message-commitment) that will be included in the parachain header. With the help of [Commitment Relayer Worker](https://github.com/Snowfork/snowbridge/tree/main/relayer/workers/parachaincommitmentrelayer) The ethereum channel then processes those commitments and verifies them via the [Polkadot and Parachain Light Client Verifier](https://snowbridge-docs.snowfork.com/concepts/polkadot-light-client-verifier/) to extract Ethereum RPCs. Those Ethereum RPCs are then routed to their target contract by calling that contract.

Workflow as following:

### 1. Following MMR Roots from Polkadot Relay Chain

The first step for trustless verification of our bridge on Ethereum starts with following the Polkadot relay chain via following new BEEFY MMR roots (as mentioned above) as they are produced and verifying their validity. Their validity is verified by checking that they are signed by the correct set of Polkadot validators.


### two phase commit

#### [Beefy light client contract](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/BeefyLightClient.sol)

first convert the initial signature array to some folded bit set structure to save storage resource

function createInitialBitfield(uint256[] calldata bitsToSet, uint256 length)
        public
        pure
        returns (uint256[] memory)
{
    return Bitfield.createBitfield(bitsToSet, length);
}

and in second phase only sample some required signatures to save computing resource

function createRandomBitfield(uint256 id)
        public
        view
        returns (uint256[] memory)
{
    ValidationData storage data = validationData[id];

    /**
     * @dev verify that block wait period has passed
     */
    require(
        block.number >= data.blockNumber + BLOCK_WAIT_PERIOD,
        "Error: Block wait period not over"
    );

    uint256 numberOfValidators = validatorRegistry.numOfValidators();

    return
        Bitfield.randomNBitsWithPriorCheck(
            getSeed(data),
            data.validatorClaimsBitfield,
            requiredNumberOfSignatures(numberOfValidators),
            numberOfValidators
        );
}

#### [Beefy Relayer Worker](https://github.com/Snowfork/snowbridge/tree/main/relayer/workers/beefyrelayer)

func (li *BeefyEthereumListener) pollEventsAndHeaders(ctx context.Context, descendantsUntilFinal uint64) error {
	headers := make(chan *gethTypes.Header, 5)

	li.ethereumConn.GetClient().SubscribeNewHead(ctx, headers)

	for {
		select {
		case <-ctx.Done():
			li.log.Info("Shutting down listener...")
			return ctx.Err()
		case gethheader := <-headers:
			blockNumber := gethheader.Number.Uint64()

                    //submit initial beefy witness verification 
                       li.forwardWitnessedBeefyJustifications()
			li.processInitialVerificationSuccessfulEvents(ctx, blockNumber)
 
                     //submit CompleteSignatureCommitment            
			li.forwardReadyToCompleteItems(ctx, blockNumber, descendantsUntilFinal)
			li.processFinalVerificationSuccessfulEvents(ctx, blockNumber)
		}
	}
}

        case msg := <-wr.beefyMessages:
        switch msg.Status {
        case store.CommitmentWitnessed:
            err := wr.WriteNewSignatureCommitment(ctx, msg)
            if err != nil {
                wr.log.WithError(err).Error("Error submitting message to ethereum")
            }
        case store.ReadyToComplete:
            err := wr.WriteCompleteSignatureCommitment(ctx, msg)
            if err != nil {
                wr.log.WithError(err).Error("Error submitting message to ethereum")
            }
        }
    }

### beefy verification messages and logs

#### Witnessed new BEEFY commitment

time="2021-07-28T22:22:29+08:00" level=info msg="Witnessed a new BEEFY commitment: 0x0918d959c5c72fb7fb591d0daf1c387429d71e623817354b9406675db24580971104000000000000000000000c0172ceb1d311e4ce503e79a12d7c911e786c15726d4f6e3e6143b6aede3aa2ccd72a9decbaf60d28aca5cf03631978f5b8bc9a4873df929b5de81bc3e1ad4dfda90101d04bb1b500d0ec6c508826f37181e8ee2c076ca805acba3a14e04ec1845722be29035cb5559154a108253b0a6662aee97c8a059d7a90fdc8a5b509c67ba345b300015fb62ab653388e9f836a902541b578f4ea1c2249dd7473acf7ff201e5aa2fc6a430d072d9d14f2c96da6e52cb07ac2ee575fed8276e2da96d4847e2b21e5a11501" signedCommitment.Commitment.BlockNumber=1041 

#### Generate MMR Proof

time="2021-07-28T22:22:29+08:00" level=info msg="Generated MMR Proof" BlockHash=0x2282ac222e1338416f128d219e06ce2d99f097a922a25d66ada474900fd61473 Leaf.BeefyNextAuthoritySet.ID=1 Leaf.BeefyNextAuthoritySet.Len=3 Leaf.BeefyNextAuthoritySet.Root=0x76aceff742e34d03bedbb6e888b7614ef3373e8f018c8ec3aac6f68260b28d95 Leaf.Hash=0x0a73bbc6ef102961fa9835b553282d405bc686f7f2851cdd25728118f8c9c55b Leaf.ParachainHeads=0x39a50879f917a3a3f935c919e8ba37002f38e0ea1ad39ee0169bf1f11443ef41 Leaf.ParentNumber=1040 Proof.Items="[0xf369932f1c946d84145000de3801e8a6ba763310788450aa627e6a4452b04c10 0x75cb9f51b689f43cbf46ad3d983221641c9d9349b901ccc89b854a91f9255b85]" Proof.LeafCount=1041 Proof.LeafIndex=1040 worker=beefy-relayer

#### New Signature Commitment transaction

time="2021-07-28T22:22:29+08:00" level=info msg="New Signature Commitment transaction submitted" BlockNumber=1041 msg.CommitmentHash=0xc07b3296a4f1dfb1ed76835722ab7fd1fabccd629af4374c73270f1949d83fcd msg.ValidatorPublicKey=0xE04CC55ebEE1cBCE552f250e85c57B70B2E2625b msg.ValidatorSignatureCommitment=0x72ceb1d311e4ce503e79a12d7c911e786c15726d4f6e3e6143b6aede3aa2ccd72a9decbaf60d28aca5cf03631978f5b8bc9a4873df929b5de81bc3e1ad4dfda91c txHash=0xa22898d1a2795c2468cf81de116ae74a8684f179ade03e53bc99fd8caa7d25e8 worker=beefy-relayer

#### Complete Signature Commitment transaction

time="2021-07-28T22:23:10+08:00" level=info msg="Complete Signature Commitment transaction submitted" hashedLeaf=0x7b277392fc8c7536cdc0e652871bf81ada297b0cb404dd8fc8e3bf2c9446181f hexEncodedLeaf=0xc101100400000a73bbc6ef102961fa9835b553282d405bc686f7f2851cdd25728118f8c9c55b39a50879f917a3a3f935c919e8ba37002f38e0ea1ad39ee0169bf1f11443ef4101000000000000000300000076aceff742e34d03bedbb6e888b7614ef3373e8f018c8ec3aac6f68260b28d95 json="{\"id\":102,\"commitment\":{\"payload\":\"0x0918d959c5c72fb7fb591d0daf1c387429d71e623817354b9406675db2458097\",\"blockNumber\":1041,\"validatorSetId\":0},\"validatorProof\":{\"signatures\":[\"0xd04bb1b500d0ec6c508826f37181e8ee2c076ca805acba3a14e04ec1845722be29035cb5559154a108253b0a6662aee97c8a059d7a90fdc8a5b509c67ba345b31b\"],\"positions\":[1],\"publicKeys\":[\"0x25451a4de12dccc2d166922fa938e900fcc4ed24\"],\"publicKeyMerkleProofs\":[[\"0xaeb47a269393297f4b0a3c9c9cfd00c7a4195255274cf39d83dabc2fcc9ff3d7\",\"0x8a9925b606d0feb8d05dd650de4bdcce204f188b36b554ba55b53008a1f56532\"]]},\"latestMMRLeaf\":{\"parentNumber\":1040,\"parentHash\":\"0x0a73bbc6ef102961fa9835b553282d405bc686f7f2851cdd25728118f8c9c55b\",\"parachainHeadsRoot\":\"0x39a50879f917a3a3f935c919e8ba37002f38e0ea1ad39ee0169bf1f11443ef41\",\"nextAuthoritySetId\":1,\"nextAuthoritySetLen\":3,\"nextAuthoritySetRoot\":\"0x76aceff742e34d03bedbb6e888b7614ef3373e8f018c8ec3aac6f68260b28d95\"},\"mmrProofItems\":[\"0xf369932f1c946d84145000de3801e8a6ba763310788450aa627e6a4452b04c10\",\"0x75cb9f51b689f43cbf46ad3d983221641c9d9349b901ccc89b854a91f9255b85\"]}" worker=beefy-relayer

#### ContractNewMMRRoot

time="2021-07-28T22:23:16+08:00" level=info msg="Found 1 BeefyLightClient ContractNewMMRRoot events on block 1070" worker=parachain-commitment-relayer
time="2021-07-28T22:23:16+08:00" level=info msg="Witnessed a new MMRRoot event" beefyBlockNumber=1041 ethereumBlockNumber=1070 ethereumTxHash=0x5e0a072d0507e11a1d3ef5ea0f9aa00b78c7d9490edf560f714731dbdc8fe423 worker=parachain-commitment-relayer

when parachain-commitment-relayer receives the `ContractNewMMRRoot` event which means the block is beefy finalized in ethereum and could be used to verify the parachain individual bridge messages

#### [Beefy light client smart contract](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/BeefyLightClient.sol)

[Polkadot Relay Chain Interactive Update Protocol](
https://snowbridge-docs.snowfork.com/concepts/polkadot-light-client-verifier/interactive-protocol)

### 2. Applying New Relay Chain MMR Updates
These verified relay chain MMR updates contain [validator set updates](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/ValidatorRegistry.sol) and parachain header updates. Then use them to update knowledge about Polkadot validators and to extract and follow new headers of Snowbridge parachain blocks.

### 3. Bridge Messages Verification
Lastly, with these verified parachain blocks, using a [Parachain light client](https://github.com/Snowfork/snowbridge/blob/main/ethereum/contracts/ParachainLightClient.sol) with the previous Parachain Commitments to verify individual bridge messages.