The Aergo Merkle Bridge — Explained

TL;DR — The Merkle Bridge is a new design for interoperability between blockchains/sidechains that is simple, decentralized, secure, and cost-effective. It will be used to power inter-chain asset bridging and communication on the Aergo

Aergo is being designed as a broad platform for developers, decentralized application (dApp) builders, system integrators, telcos/hosting providers, enterprises, and SMBs to combine the powerful semantics of blockchain technology with serverless cloud computing on a new open-source enterprise-IT platform that is easy-to-use for all stakeholders.

Aergo could be a productive platform for developers, dApp builders, and system architects to build decentralized applications and protocols on their own dedicated chain. Aergo offers exceptional performance and cost-effectiveness running, for the first time ever, smart contracts written in Lua/SQL, handling data using a hyper-fast database engine, and coding applications using an isomorphic programming model.

Aergo could also provide software infrastructure — an incredibly easy to implement IT solution that organizations can use to share data and functionalities with third-parties in a controlled way — as equal peers. All kinds of organizations, including fintech, government, or enterprise companies, could automate key aspects of their external business processes in an integrated and consistent way while strengthening security. An organization building a use case with other entities could run their own dedicated private chain, and collaborate with third-parties running their own private chains, while settling exchanges or communications using our permissionless-public blockchain.

Technically, Aergo as a platform provides exceptional utility for interoperability between blockchains or sidechains in processes as described above. Such interoperability entails two things. First, authenticating states between distinct chains: this is addressed by our Aergo StateTrie released in October 2018.

Second, and more immediately relevant, facilitating inter-blockchain transfer and communication as addressed by the Aergo Merkle Bridge.

Technical 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.

-- signers is the index of signers in Validators function set_root(root, height, signers, signatures) local block_height = system.getBlockheight() assert(block_height >= (LastAnchor:get() + T_anchor:get()), "Anchoring time not reached") -- check Height so validator is not tricked by signing multiple anchors assert(height > Height:get(), "Height must be higher that previous anchor") LastAnchor:set(block_height) old_nonce = Nonce:get() message = crypto.sha256(root..tostring(height)..tostring(old_nonce)) 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, sender, 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() -- FIXME how can this be hacked with a reentrant call if the token_address is malicious ? if sender == nil then sender = system.getSender() if not contract.call(token_address, "signed_transfer", sender, this_contract, bignum.tostring(bamount), nonce, "0", 0, signature) then error("failed to receive token to lock") end else -- TODO fix standard token, currently doesnt pay fee to tx signer but to caller contract instead if not contract.call(token_address, "signed_transfer", sender, this_contract, bignum.tostring(bamount), nonce, fee, deadline, signature) 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.