Nomadic Labs
Nomadic Labs

Tezos calling convention migrating from Breadth-First to Depth-First Order (BFS to DFS)

Summary: If the Florence proposal is adopted, we recommend you do not deploy new Michelson contracts that are dependent on the BFS calling convention. We do not expect this to be a problem in practice. However, those planning on deploying contracts in the near term should check that their contract’s correctness is unaffected by the change in calling convention.

The current calling convention for intercontract calls in Tezos is that they are added to a “first-in, first-out” queue, also called a “BFS” (or “breadth-first”) approach.

The proposed Florence protocol update includes a switch to a “first-in, last-out” convention, also called a “DFS” (“depth-first”) approach.

Early in the history of Tezos, the decision was made to use a BFS calling convention for intercontract calls. This was motivated by theoretical work that appeared to show that BFS would be superior to DFS for this purpose.

However, experience indicates the opposite:

  • the BFS calling convention can confuse some developers and cause errors, and
  • it complicates porting contracts from other chains, where DFS calling conventions dominate.

A number of mechanisms were considered for the Florence proposal to add a DFS calling convention in addition to BFS. However, when mechanisms for backwards compatibility with legacy contracts were considered, subtle bugs were frequently found that would impact the correctness of existing contracts, and which could also render future contracts unsafe.

In practice reasoning about a mixed calling convention is hard, and accordingly the Florence proposal contains a straightforward change to switch the Tezos intercontract calling convention from BFS to DFS.

Replays of on-chain history indicate that this migration does not break the ordinary functionality of any existing live contracts. Because the BFS convention typically provides few useful guarantees, it appears that current contracts deployed on the chain are insensitive to calling order (we speculate that authors just found reasoning about BFS calling order too difficult, so avoided depending on it).

However, new contracts with a calling order dependency might get added to the chain between the injection of Florence and its adoption. Therefore, we recommend you do not add new contracts that depend on BFS calling conventions to the chain — if Florence is adopted, such contracts would break.

Note that, unless you explicitly built a contract to depend on the BFS calling convention, it probably doesn’t.

We will continue to monitor the chain for new contracts that might depend on calling convention ordering, and attempt to contact their authors.

Although this upgrade path is imperfect, it seems the best available option for improving both the smart contract developer experience and the future safety of contracts deployed on the Tezos network. The alternatives would have increased complexity and created unacceptable scope for error.

The BFS calling convention for smart-contract interactions was an unfortunate design flaw. However, Tezos can self-amend and is always evolving, so we in the Tezos community can solve this issue by adopting the Florence amendment through an on-chain vote.