add draft for DFS

This TZIP corresponds to MR: (tezos!2420 (merged)).

The examples would be clearer if there was a direct indication as to which operation is DFS and which is BFS. Right now this is only indicated in the header which is a bit confusing. You could prepend of "!" for instance (because the DFS operation needs to be done now!) e.g. "op 3| 3a, !3 (closed)b, 3c, !3 (closed)d"

added 1 commit

• c6a9a311 - add draft_dfs.md

Compare with previous version

added 9 commits

• c6a9a311...e32cf7f7 - 8 commits from branch tzip:master
• 6220de42 - add draft_dfs.md

Compare with previous version

added 1 commit

• fbc4200c - add draft_dfs.md

Compare with previous version

added 73 commits

• fbc4200c...b99c8acb - 72 commits from branch tzip:master
• 97d94081 - add draft_dfs.md

Compare with previous version

approved this merge request

added 1 commit

• dae087d5 - add draft_dfs.md

Compare with previous version

approved this merge request

added 4 commits

• dae087d5...1f83a367 - 3 commits from branch tzip:master
• 9f6a5492 - add draft_dfs.md

Compare with previous version

added 1 commit

• d582a59b - add draft_dfs.md

Compare with previous version

(I wonder where discussion of TZIPs is supposed to take place?)

For contracts, the change is adding new instructions without changing the fundamental architecture. It's backward compatible.

It seems important to note that the existence of MAKE_DFS destroys some guarantees which, theoretically, contracts might currently rely on...

In particular, as noted by @e-mishura in the "Concurrency, BFS vs DFS" Agora thread, the current BFS order guarantees that if a contract emits [op1; op2], the two ops will be handled consecutively. Perhaps most importantly, the contract itself cannot be invoked in between op1 and op2.

In the presence of MAKE_DFS, the contract invoked by op1 can use MAKE_DFS to cause arbitrarily many other operations to be handled before op2, and in particular might "re-enter" the original contract before op2.

Does anyone rely on these properties today? I don't know... It seems doubtful.

Can any real use case for BFS guarantees be reasonably implemented in a different way in the presence of MAKE_DFS? I don't know...?

One example theoretical use case is rafoo's response in the Problems with Balance thread:

A point that seems often overlooked when implementing smart-contract interactions in Tezos is that BFS provides atomicity guarantees. If contract B sends more than a single transaction in its operation list, it has the guarantee that nothing happens in between and I claim that this provides a way to correctly implement the contract logic that we want for contract B by performing the balance check after the transfer to the potential attacker.

...but it seems like this can be addressed more simply by maintaining a local "effective balance" in storage. (Or perhaps by patching Tezos somehow...)

Does anyone rely on these properties today? I don't know... It seems doubtful.

Something that we can easily measure is how common it is for Tezos smart contracts to output more than one operation.

I have just talked with @arvidnl about this, Dexter does this (send several operations) in several entrypoints. For example when a liquidity provider removes liquidity he or she receives both tez and FA1.2 tokens so the Dexter contract emits two operations one to the address of the liquidity provider and one to the address of the associated FA1.2 contract. Unfortunately the call to the untrusted address (the liquidity provider) seems to go first so a malicious liquidity provider could use the new DFS feature to inject a DFS reentrent call and access the Dexter contract in a state that is currently not accessible. It is not clear that this can be exploited to break Dexter but I find this alarming.

You could access the Dexter contract after it's credited the liquidity provider their tez but before its credited them with their FA1.2 contract. The state of the Dexter contract is consistent at this point. Either the FA2 deposit will succeed or it won't. The only possible hiccup would be asking the Dexter contract to synchronize its balance with the FA1.2 contract, but that is disallowed unless called from an implicit account, precisely to avoid these kinds of shenanigans.

I do agree that it's cutting a bit close though. What do you propose?

So I have two possible fixes for this. Both rely on disallowing contracts from making DFS calls, but in different ways.

1. Version contracts. If you are called by a legacy contract and try to call MAKE_DFS, execution fails.

2. Introduce an opcode called ALLOW_DFS which must be called on an operation that is emitted by a contract for the code called by this operation to successfully use MAKE_DFS

Both ideas are similar. Given that legacy contracts don't use MAKE_DFS, it means the behavior is similar to 1 (unless they are updated with a lambda, but that seems fine). The second idea has the benefit that it's potentially useful for future contracts to disallow dfs calls in their children.

@rafoo_ Even if this malicious liquidity provider emitted operations that it flagged as DFS, if Dexter continued making its calls in legacy BFS fashion it can still be positive that they will be executed one after the other.

I think the problem you are describing becomes an issue when the original call to Dexter that resulted in the two operations (first to liquidity provider, second to fa1.2) is labeled DFS. If this is the case, then it will force Dexter's first emitted operation to be DFS against its intention, possibly resulting in unintended reentrance. Using BFS+contexts as @klakplok discussed fixes this problem. Even if the original call to Dexter is labeled as contextual, its emitted operations are still executed BFS style as it intended because being contextual just means an operation gets its own execution queue.

I suggest the Michelson instruction should be MAKE_CONTEXTUAL instead to clear this up.

Even if this malicious liquidity provider emitted operations that it flagged as DFS, if Dexter continued making its calls in legacy BFS fashion it can still be positive that they will be executed one after the other.

One after the other yes, but it no longer has the guarantee that they are executed one right after the other as the first call could insert a DFS call, in particular a DFS call to Dexter itself. That is the crux of the argument.

If this is the case, then it will force Dexter's first emitted operation to be DFS against its intention

No, this not what this patch implements. In this patch every contract chooses explicitly and independently how its emitted operations behave, and a DFS results in a new queue being created.

Hi, I would like to clarify and then present an idea for a longer term idea.

Clarification: There are two basic mechanisms discussed, which I think are orthogonal: BFS/DFS and CONTEXT/NOCONTEXT.

• BFS/DFS. Essentially, "create a BFS operation" is to add an operation at the end of the queue (FIFO) of operations. "Create a DFS operation" is to add an operation at the beginning of the queue (so it will be taken next, like in LIFO). Tezos was purely BFS and this discussion verses about mixing BFS and DFS options.
• CONTEXT/NOCONTEXT. A "context" is meant to be an atomic execution. Everything in the context will be executed before everything after the context. If a call is executed contextually then every sub-operation will be executed before the context ends. Since sub-operations can be BFS/DFS (previous point) this requires a fresh queue for the context. With contexts, the data struct will be a stack of queues. Starting a context pushes an empty queue, finishing a context pops the empty queue. Contexts are nice for developing reusable code because they create isolation and one can "prove" a contract with subcontracts correct and isolate it against interleaving attacks.

Longer term The argument about Dexter presented by @rafoo_ is in favor of the isolation BFS creates as the developer that generates [AB] could assume that there is nothing between A and B. I want to introduce the idea of "bundles". When justified as @rafoo_ [AB] means that A and B are tightly bundled. Expressing a tight bundle should force the runtime system to respect this constraint. However, most of the time bundles are not tight and the system could run things between A and B if the [AB] is not declared "tight". This could allow DFS and BFS to coexist.

However, the idea that I really like is that a tight bundle [AB] means that the execution of B should be semantically equivalent to having nothing between A and B. However, A could still be contextual and have children, or create a DFS child (in both cases the children would run before B), as long as B runs exactly as if nothing happened between A and B. This can be easily checked at runtime, and fail if the context declared by A and the tight bundle [AB] happened to be incompatible in the execution.

So I have two possible fixes for this. Both rely on disallowing contracts from making DFS calls, but in different ways.

• Version contracts. If you are called by a legacy contract and try to call MAKE_DFS, execution fails.
• Introduce an opcode called ALLOW_DFS which must be called on an operation that is emitted by a contract for the code called by this operation to successfully use MAKE_DFS

I think either solution would make the addition of DFS operations much safer. Both are technically doable, I prefer the former because it puts less burden on the contract developer.

Not sure where to discuss the spec.

I'm a bit late to the discussion, but I saw variants presented in the discussions around this topic, and the motivation behind the choice of variant is not provided.

The two variats that were best described in https://forum.tezosagora.org/t/concurrency-bfs-vs-dfs-and-a-proposal/1994/14 by Eli Guenzburger are BFS+DFS and BFS+context.

AFAIU, it seems to me that the variant implemented is what Cesar Sanchez labelled "Mixed First Search" in the Agora conversation. It's none of the two variants illustrated by Eli Guenzburger, and it's one that breaks assumptions of current contracts (since the decision to disrupt the current transaction flow to insert new transactions in the middle is taken by the callee and not the caller).

A small change in what you implemented could turn this implementation into BFS+context. The main difference is that the flag is observed when the operation is executed, instead of when it's emitted.

The structure is now a stack of queues.

Operations have a flag, that is read after their execution, conditioning the treatment of their emitted operations:
- if the flag is not set, emitted operations are pushed in the order of the list, at the end of the top queue.
- if the flag is set, emitted operations are pushed in the order of the list, in a newly pushed queue.



Example 3. The internal operations, !3b, !3d, are contextual. The others are not.

    +------------+------------------+-------------------------------------+
    | executing  | emissions        | resulting stack + queue of op       |
    +------------+------------------+-------------------------------------+
    | op 3       | 3a, !3b, 3c, !3d | [ [ 3a, !3b, 3c, !3d ] ]            |
    | op 3a      | 3ai, 3aj         | [ [ !3b, 3c, !3d, 3ai, 3aj ] ]      |
    | op !3b     | 3bi              | [ [ 3bi ], [ 3c, !3d, 3ai, 3aj ] ]  |
    | op 3bi     |                  | [ [ 3c, !3d, 3ai, 3aj ] ]           |
    | op 3c      |                  | [ [ !3d, 3ai, 3aj ] ]               |
    | op !3d     |                  | [ [ 3ai, 3aj ] ]                    |
    | op 3ai     |                  | [ [ 3aj ] ]                         |
    | op 3aj     |                  | []                                  |
    +------------+------------------+-------------------------------------+

Something along the lines of what you implemented would be unavoidable if we were switching to actual sync calls (w/ return value), but since your proposal keeps the asynchronous paradigm, I wonder if the BFS+context variant wouldn't be more natural and less breaking, as it preserves the order of emitted operations.

I just replayed the past discussions in fast forward so it's very, very possible that I missed important discussions. It's to be noted that albeit these variants look fairly similar, they seem to have different expressive power, and I don't fully realize how so.

On a more cosmetic point of view, maybe, an alternative solution (to flagging the operations and putting both DFS and BFS in the same list) that would make the order clearer is to allow contracts to return a pair of lists of operations, (DFS, BFS). Was this considered?

On a more cosmetic point of view, maybe, an alternative solution (to flagging the operations and putting both DFS and BFS in the same list) that would make the order clearer is to allow contracts to return a pair of lists of operations, (DFS, BFS). Was this considered?

It is not so cosmetic; in the current proposal, BFS is the default and the developer have to opt-in for DFS whereas if we put two lists there is no default.

Is this intended to be transitive? I can write a contract and I have control over DFS/BFS order of all the operations and their internal operations? If so it seems like a contract developer would have even less guarantees about the operation ordering and would need to design it even more defensively.

I think that it is not transitive. Whoever creates the sub-operations chooses BFS or DFS for each, with no implication for the sub-operation children. For contexts, similarly, if A runs contextually, A's children need not be contextual with each other.

mentioned in merge request tezos!2420 (merged)

added 32 commits

• d582a59b...369bbed9 - 30 commits from branch tzip:master
• 5ebeffbf - add draft_dfs.md
• b3ba1da2 - modify exec ordering

Compare with previous version

added 1 commit

• 06cbbb4f - update draft_dfs.md

Compare with previous version

This tizp is updated with

1. the running ordering of DFS
2. adding the permission for running DFS.

added 1 commit

• 3f178d24 - update the description of test case draft_dfs.md

Compare with previous version

Was ALLOW_DFS_IN_CHILDREN discussed somewhere?

I don't get it. If the permission is transitive, the guarantee which the permission is supposed to maintain will be lost.

(It might be nice if the TZIP's rationale section were not missing.)

I agree, it needs to be non-transitive otherwise an attacker can simply bypass this protection.

I was confused.

The new implementation (in the MR) is like "BFS+contexts", as klakplok mentioned above. And, indeed, as klakplok mentioned, this implementation already preserves the specific guarantee we were thinking about when first discussing ALLOW_DFS: when a legacy contract emits more than one op, they will be applied consecutively.

The latest draft implements a different kind of DFS permission, designed to preserve more guarantees. A root op (implicit sender) has the DFS permission, and it may be passed on to descendants, using ALLOW_DFS. If the permission is not passed along to a child, no MAKE_DFS ops in the child's subtree can succeed. In the current draft, using ALLOW_DFS in that subtree has no effect.

This ALLOW_DFS has some vague intuitive appeal. The descendant ops from a legacy contract, its subtree, will all be BFS.

However, it is still possible for DFS operations to be interleaved among a legacy contract's subtree, because BFS does not provide subtree isolation. I do believe it possible to exploit this to create a "bounty" contract which is unclaimable today, but becomes claimable under the current draft. Whether there could be any realistic problem like this, I don't know.

Another possible worry is that DFS ops could be interleaved between a legacy contract and its first emitted op. I don't have a hypothetical example broken by this yet. (I'd bet there is one, but I won't bet that it is realistic.)

So, I wonder if maybe ALLOW_DFS should be redesigned again.

Or maybe it can just be removed... If the problems ALLOW_DFS does prevent are more likely than others, maybe it is worth its costs. I don't know.

(Totally wrong example here deleted, sorry.)