Blog

Merkle Bridge

in Blog
Author:

Special thanks to Pierre-Alain Ouvrard

Context

To understand the Merkle Bridge, we should first start by understanding one of its most useful applications: two-way pegged (2WP) asset transfers. The basic idea of a 2WP asset transfer is as follows:

  1. Token is issued on Blockchain A
  2. A transfer request is made to transfer Token to Blockchain B
  3. Token on Blockchain A is locked
  4. A copy of Token is minted on Blockchain B in a 1:1 ratio to the amount that was locked on Blockchain A
  5. The locked Token on Blockchain A can only be unlocked if it’s copy has been burnt on Blockchain B

Currently, the most common way of transferring tokens between blockchains is transferring tokens using multisig operators. Operators will watch transfer events of tokens being sent to their multisig type contract and multi-sign a message that will mint an equivalent amount of tokens on the destination blockchain.

Example implementations are Cosmos’ Peggy.sol contract, which Cosmos’ validators use to transfer assets to other blockchains through the Cosmos Hub. Another example is POA Network’s bridge that transfers tokens between Ethereum and the POA chain. Relaying deposit events to transfer tokens works well for connecting different types of blockchains including UTXO-based blockchains like Bitcoin, blockchains with accounts based on Merkelized state like Ethereum, and blockchains based on accounts without Merkelized state such as EOS.

However, an important limitation of this approach is the cost and security of locking and unlocking assets. Because each user transfer event needs to be multi-signed for minting/unlocking, it means the value being transferred cannot be small as verifying multiple signatures is costly. As a result, there is a trade-off between the decentralization (security) of the bridge (number of validators) and the cost of individual transfers.

This tradeoff can be improved in 2 ways:

  • A liquidity provider makes a large transfer then swaps small amounts of his minted assets.
  • The multisig type contract holding tokens could support batch transfers so that signature verification is done only one time for the whole batch. But this would still be limited as the batches would have to contain only one asset class — a malicious token could revert the whole batch. Finally, the validators need to agree on a set of transfer events to sign which makes the implementation of the multisig operators more complicated.

At AERGO, we are connecting state-Merkelized enterprise sidechains to the public AERGO public chain, so we looked for a more efficient way of bridging two blockchains; by using state Merkle proofs instead of events.

Merkelized State Trie

In order to operate a Merkle Bridge between two blockchains, their state should be Merkelized in a data structure like the AERGO StateTrie (a modified Sparse Merkle Tree) or Ethereum’s modified Patricia Tree. The AERGO StateTrie was released last October 2018 and presented in a previous article.

One of the reasons for using the modified Sparse Merkle Tree (StateTrie) in AERGO is the efficiency and the size of Merkle proofs, which is better than Ethereum’s Patricia tree — less gas is needed to verify proofs and we can allow for smaller transaction sizes. Nevertheless, we will also develop an Ethereum-AERGO Merkle Bridge using both Ethereum Patricia tree and AERGO StateTrie Merkle proofs.

Blockchain state authentication brings consensus safety and enables light client wallets to safely interact with the blockchain. It is a key to blockchain interoperability as it enables any blockchain state to be verified in an application (contract) on another blockchain. The Merkle Bridge currently only supports token and AERGO transfers but other applications are being researched like Oracle data verification and inter-blockchain function calls.

Merkle Bridge Design

Proof of Authority sidechains often use anchoring of their state on a public chain to provide a source of verifiable truth. The Merkle Bridge uses these anchored state roots to allow users to submit proofs of a sidechain’s state.

Benefits include the following:

  • Simple: Bridge operators only need to publish and sign a finalized state root they believe is valid by running a full node
  • Flexibly Decentralized, Secure: State roots can be signed by many more validators during the anchoring period making it more decentralized and secure
  • Resilient: Token transfers cannot be arbitrarily censored without modifying the sidechain state root
  • Cost-Efficient: Microtransfers can be made and the total deposited balance can be minted/unlocked, Merkle proof verification is cheaper than signature verification

Is this similar to Plasma?

This design was inspired from researching Plasma and running into the issue of running contracts on Plasma. The Merkle Bridge is not Plasma because it doesn’t have the same security properties: there is no exit cue to challenge exits from the sidechain, and withdrawing has to be initiated on the sidechain. The security of the Merkle Bridge relies on the decentralization of the anchoring validators. Since an unlimited number of transfers can be made for a single state root, the required number of signatures of that state root can be high. Users don’t need to watch a blockchain for invalid withdrawals and mass exit situations but should trust the decentralized operators.

How does it work?

The proof of concept implementation of the Merkle Bridge between two AERGO blockchains can be found in this repository.

Bridge Operators

They run a full node for each blockchain they are bridging. At regular intervals (perhaps every 10 minutes), they will get the latest finalized state root and register it on the opposite blockchain in the Root and Height state variables of the bridge contract.

function set_root(root, height, signers, signatures)
    assert(height > Height:get() + T_anchor:get(), "Next anchor height not reached")
    old_nonce = Nonce:get()
    message = crypto.sha256(root..tostring(height)..tostring(old_nonce)..ContractID:get().."R")
    assert(validate_signatures(message, signers, signatures), "Failed signature validation")
    Root:set("0x"..root)
    Height:set(height)
    Nonce:set(old_nonce + 1)
end

set_root(…) is called by operators to anchor a new state root

Asset Transfer

To transfer tokens, a user will lock them in the bridge contract and wait for the next anchor on the destination blockchain

function lock(receiver, amount, token_address, nonce, signature, fee, deadline)
    local bamount = bignum.number(amount)
    local b0 = bignum.number(0)
    assert(address.isValidAddress(receiver), "invalid address format: " .. receiver)
    assert(MintedTokens[token_address] == nil, "this token was minted by the bridge so it should be burnt to transfer back to origin, not locked")
    assert(bamount > b0, "amount must be positive")

    -- Lock assets/aer in the bridge
    if system.getAmount() ~= "0" then
        assert(token_address == "aergo", "for safety and clarity don't provide a token address when locking aergo bits")
        assert(system.getAmount() == bignum.tostring(bamount), "for safety and clarity, amount must match the amount sent in the tx")
   else
        this_contract = system.getContractID()
        if fee == nil then
            sender = system.getSender()
            if not contract.call(token_address, "signed_transfer", sender, this_contract, bignum.tostring(bamount), nonce, signature, "0", 0) then
                error("failed to receive token to lock")
            end
        else
            -- the owner of tokens doesn't pay aer fees, lock is called by a broadcaster
            if not contract.call(token_address, "signed_transfer", receiver, this_contract, bignum.tostring(bamount), nonce, signature, fee, deadline) then
                error("failed to receive token to lock")
            end
        end
    end

    -- Add locked amount to total
    local account_ref = receiver .. token_address
    local old = Locks[account_ref]
    local locked_balance
    if old == nil then
        locked_balance = bamount
    else
        locked_balance = bignum.number(old) + bamount
    end
    Locks[account_ref] = bignum.tostring(locked_balance)
    -- TODO add event
    return token_address, bamount
end

lock(…) records the total balance deposited by the user.

The user’s wallet will read the new anchored state root (Root, Height) on the destination blockchain and request a Merkle proof of inclusion of his locked balance for that state root to a full node. A user’s locked balance is recorded in the Locks state mapping where keys are the account reference for a token. The account reference is the concatenation of the user address and the token address.

# addr2 : bridge address on the destination chain
# query the last merged state of blockchain 1 onto blokchain 2.
height_proof_2 = aergo2.query_sc_state(addr2, ["_sv_Height"])
last_merged_height2 = int(height_proof_2.var_proofs[0].value)
# get inclusion proof of lock in last merged block
merge_block1 = aergo1.get_block(block_height=last_merged_height2)
account_ref = receiver + token_origin
# get the proof of locked balance for account_ref
lock_proof = aergo1.query_sc_state(addr1, ["_sv_Locks-" + account_ref],
                                   root=merge_block1.blocks_root_hash,
                                   compressed=False)

Creating the Merkle proof of locked balance

The user’s wallet can then make a transaction on the destination blockchain to mint his tokens. The user cannot mint more than the total amount deposited and recorded by the contract.

function mint(receiver, balance, token_origin, merkle_proof)
    local bbalance = bignum.number(balance)
    local b0 = bignum.number(0)
    assert(address.isValidAddress(receiver), "invalid address format: " .. receiver)
    assert(bbalance > b0, "minteable balance must be positive")

    -- Verify merkle proof of locked balance
    local account_ref = receiver .. token_origin
    local balance_str = "\""..bignum.tostring(bbalance).."\""
    if not _verify_mp(merkle_proof, "Locks", account_ref, balance_str, Root:get()) then
        error("failed to verify deposit balance merkle proof")
    end

    -- Calculate amount to mint
    local to_transfer
    minted_so_far = Mints[account_ref]
    if minted_so_far == nil then
        to_transfer = bbalance
    else
        to_transfer  = bbalance - bignum.number(minted_so_far)
    end
    assert(to_transfer > bignum.number(0), "make a deposit before minting")

    -- Deploy or get the minted token
    local mint_address
    if BridgeTokens[token_origin] == nil then
        -- Deploy new minteable token controlled by bridge
        mint_address, success = _deploy_minteable_token()
        if not success then error("failed to create token contract") end
        BridgeTokens[token_origin] = mint_address
        MintedTokens[mint_address] = token_origin
    else
        mint_address = BridgeTokens[token_origin]
    end

    -- Record total amount minted
    Mints[account_ref] = bignum.tostring(bbalance)

    -- Mint tokens
    if not contract.call(mint_address, "mint", receiver, bignum.tostring(to_transfer)) then
        error("failed to mint token")
    end
    -- TODO add event
    return mint_address, to_transfer
end

mint(…) verifies the deposit Merkle proof and mints the right quantity of tokens. If a token was never minted, a new pegged token contract is deployed.

If the bridge operators anchor a new state root before the user mints his balance, the user’s wallet can simply create a new Merkle proof for the newly anchored state root: minting/unlocking has to be done within the anchoring period.

The user’s wallet repeats the same process for burning tokens before unlocking them on the origin blockchain.

For details about the Merkle proof verification in the Merkle Bridge contract see this previous article.

Conclusion

The Merkle Bridge behaves like a multisig contract that signs a sidechain state root instead of individual transactions and users can make a withdrawal by proving their state. The main benefit is that the token custody is much more decentralized and simple to operate than usual multisig contracts. Asset transfers are the first usage, but being able to prove anything about another blockchain’s state is a powerful thing which enables other applications.

Other ideas could be developed to make the anchoring more secure and decentralized, for example, bonded validators, a challenging period to cancel a state root anchor. Anchoring an invalid state root requires 2/3 of the validators to be corrupted. Those validators can be the sidechain POA block producers but also some official legal entities, bonded entities.

I hope you found this interesting! Feedback and contributions are welcome.

Prev
AERGO 20 Feb 2019 AMA Transcript
Next
AERGO v0.12.0 Release (Testnet Update)
Menu