Bridge Action ID

History of the concept

The concept of asset duplication prevention was present in various contexts before the emergence of Web3. In traditional finance and accounting, preventing asset duplication has long been a crucial principle to ensure the accuracy of financial records.

However, the very concept of blockchain is centered around the tools preventing users' voluntary asset minting or duplicating. Every chain begins with a genesis state, where a limited number of accounts have some assets. What follows is a history of user inputs and ledger or smart contracts' outputs carefully validated by the nodes ensuring everybody plays by the rules.

In the context of Bitcoin or v1.o of Ethereum, for example, the prevention of asset duplication is primarily achieved through a distributed ledger. Each transaction is verified and recorded by a network of nodes. Each transaction includes inputs and outputs associated with unique digital signatures. The combination of these inputs and outputs and their associated digital signatures are used to create a unique transaction ID.

Once a transaction is verified and recorded on the blockchain, it cannot be modified or duplicated. It means that each Bitcoin unit can only be owned by one person or entity at a time. The network would immediately detect any attempt to duplicate or counterfeit the Bitcoin. In addition to the blockchain, Bitcoin relies on a consensus mechanism called proof-of-work to prevent asset duplication. This mechanism requires nodes on the network to perform complex calculations to verify transactions and earn newly minted Bitcoin units. It makes it computationally expensive to attempt to create fake transactions or duplicate Bitcoin units, as it would require enormous computing power.

XP.NETWORK implementation

Following the principle of asset duplication prevention as a part of the multilayer security system, we ensure the assets are available to the users in one place at a time only. For example, if an NFT minted on Ethereum is bridged to MultiversX, the token on Ethereum is locked in the bridge contract. The only NFT available to the users for transferring, trading, staking, etc., is on MultiversX.

Because different blockchains are asynchronous and ignorant of each other's existence, the bridge fills the gap by emitting its transaction or actionIds in the smart contracts orchestrating the work of token contracts and the off-chain oracle validators.

The bridge contract keeps track of all the outgoing and incoming transactions. The outgoing transactions are incremented (actionId++;) every time users interact with the contract by calling its functions. The external transactions are stored in a mapping ensuring O(1) access complexity to prevent duplicate transactions.

Current Implementation

When bridging between 2 chains, action ID is straightforward to implement. However, when 30+ chains are involved, the chance of collision grows, exponentially increasing the possibility of broken transactions and stuck assets.

The initial implementation of the action ID transformation to make each "foreign" action ID unique looked like this:

// Szudzik elegant pair
function pairAction(x: bigint, y: bigint): bigint {
    return x >= y ? x * x + x + y : x + y * y;
}

actionId = new BigNumber(
    pairAction(BigInt(act), BigInt(emitter.chainNonce)).toString()
);

Here x = act is the action ID generated on the chain of origin, and y = emitter.chainNonce is the internal bridge unique chain identifier. Knowing that at the time of writing, the chain nonces range from 2-37, the smallest possible value is 2, and the greatest is infinity. While $x <= y$, there is a zero chance of collision. However, when $x > y$, the collision probability can be approximated as $(m^2 - m) / n$, where m is the number of possible output values, and n is the number of possible input values.

before the number of transactions between the bridged chains reaches $38^2=1,444$ the chances of collision is approximately $1/1,700,376$ or ~$~1.7e-6$

Alternative implementation we are considering:

To decrease the probability of foreign action ID collision, the formula can be transformed to:

import { ethers } from "ethers";

type numstring = number | string;

const actionIdDigest = (
    fromChain: numstring,
    toChain: numstring,
    originActionId: numstring
) => {
    const unhashed = `${fromChain}-${toChain}-${originActionId}`
    return ethers.keccak256(
        Buffer.from(unhashed, 'hex')
    )
}

// Example
const result = actionIdDigest(
    4,  // BSC
    7,  // Polygon
    215 // actionId on BSC
)

console.log(result);
// Output:
// 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470

The major improvement is the substantial collision rate reduction. SHA3 generally offers $2^{n/2}$ collision resistance. There are several types of SHA3 - SHA3-224, SHA3-256, SHA3-384, and SHA3-512. Keccak256 is another name for SHA3-256. It means the chance of collision is $2^{-128}$ or 2.9387359e-39.