On-chain gated computing by patching the control flow of arbitrary smart contracts

Layer 2
1

On-chain gated computing by patching the control flow of arbitrary smart contracts

The problem

Imagine the problem space layer-2 solutions have to face.
For example: to make it possible to run arbitrary smart contracts on layer-2 and allowing
the computation and outcome of these contracts to be verifiable on the root-chain;
ideally in a permissionless way and without any sort of ‘special’ authorities or governance protocols.

Solutions we have right now for this are systems like solEVM-enfocer or any truebit like verification game,
but they come with it’s own problems, the biggest one being the time it takes to decide on disputes -
intending to resolve computation in a on-chain verification game protocol.

This cripples layer-2 solutions because it becomes easy to block/delay finalization of side-chain Blocks on
the root-chain Plasma-style bridge contract. The only reason for this is the big complexity and therefore time
it takes to resolve a dispute.

Theory for a potentially better system

If we think about executing contracts that are easily exceeding the root-chain block gas limit,
one possible solution is to write the contracts in a resumable way - to gain the ability to execute
a programm in a chunkable way. But this is a complex task and does not scale in practice for every contract.

Let’s assume a general chunkable/gated computing model:

  • Stop the execution at any point in (the EVM run-)time,
  • Checkpoint the execution environment (stack, memory, etc).
  • Save it somewhere and resume the execution at a later time.

Like the suspend-to-ram or deep sleep mode of your favourite computing machine.

Analogy:
The flow of a river that we can suspend or resume depending on a condition.

  • Gated

Layer-2 Example

A potential layer-2 solution could use that in the following way:

  • Allowing users to submit the solution/outcome of executing a block.
    We assume good faith and provide incentives that submitting the correct solution (a solution no-one challenges because it is correct)
    provides the solver or potential challengers with positive or negative financial outcomes.
  • Having the ability that any honest user can challenge a solution by invoking the execution of that block
    on the root-chain in one or more transactions until the execution is resolved/done.

TL;DR
We assume at least one honest user always challenges incorrect solutions buy executing the compution in one or more transactions and
gaining the bond from the solver after the execution was executed on-chain.

How - Patching arbitray smart contracts to own the control flow

With the above in mind, the layer-2 root-chain Bridge-contract that manages the state of the side-chain
can analize and patch arbitray smart contracts to ‘hijack’ the control flow of the program and therefore
provide a controlled and verifiable way to execute a transaction in chunks by deploying a patched version
of a smart contract with checkpoints and functionality like intercepting calls to other contracts inside that
arbitrary contract to provide custom functionality or state checks.

That checkpointing function or let’s name it a retpoline - a term VM & Kernel developers are propably aware of.
In a nutshell, we patch the bytecode by adding and/or changing control flow instructions like JUMP
and therefore gaining the ability for code execution inside a (potentially untrusted) EVM context.
In this case, the retpoline is Bridge-controlled code that watches for gas usage to know when to stop execution and
overriding instructions like CALL to provide chain-specific functionality.

Now, gate your feedback :smile:

2 Likes
2

I think the idea of pausing execution with the ability to resume later is interesting, and it may be especially applicable for transactions that simply can’t fit within a single block. However, in the general case I think it adds more complexity than using intermediate roots. For example:

Some L2 construction does off-chain processing on a state tree S_0 to come up with a new state tree S_n. S_0 \to S_n may be too large to verify on the root chain, but it could be chunked into intermediate state roots that can be verified on chain. So instead of only posting roots of S_0 and S_n on chain the L2 operator would post roots of S_0, S_1, ... , S_n. The L2 construction would just need to define running out of gas for any transition S_i \to S_{i+1} as malicious.

Since the only verification that needs to be run on chain is the state transition between the last valid state and the first invalid state, this should scale for most types of transactions.

2 Likes
3

can you explain this more? The verification of computation is only relevant on exit, and Plasma exits give you plenty of time (3.5-7 days). So how are blocks hindered? :grinning:

4

how expensive (gas) would something like this be? :thinking:

5

Full ack. it is easier to use intermediate state-roots if the constrains on the side-chain are that a valid transaction by definition can always be validated on the root-chain.

Even if the design of the layer-2 chain does not require to ‘chunk’ computation, the patching model allows to intercept CALL-opcodes and other custom operations that the bridge contract can deploy and call into. This was my initial issue to make that more efficient without bundling & running a complete EVM interpreter inside the EVM runtime itself.

6

Plasma was just a pointer. In my example I assume that each Block has to be validated on-chain if someones doesn’t agree with the submitted block solution :slight_smile:

7

Good question.

If we account for things like copying the target code into memory, processing it, creating a new version, deploying it, calling the patched contract and once we are done SELFDESTRUCT the contract. That may not be necessarily cheaper nor more expensive, but that relies heavily on the target contract’s runtime characteristics and on the contract size.

I will let you know once I know more by writing a proof of concept, but I’m heavily loaded with tasks so I will not be able to work on this in the next 2-3 weeks.

The most important thing is that this doesn’t need a long-running truebit-like game and
the problem with denial of service attacks of many solutions <-> disputes.

8

I wrote a proof of concept earlier than I expected :slight_smile:,
the process of patching the bytecode (overwriting jumps), looking for opcodes to replace and finally deploy them inside a contract with CREATE costs about:

7.916.300 gas for the whole transaction.
Original bytecode length (included in calldata of the transaction): 6096 bytes.
With a resulting patched bytecode length of 6156 bytes.

There is room for improvement :smirk:.

I published the PoC here:

with a simple test-case here:

1 Like
9

wow, so that is NOT exactly a huge contract: https://github.com/NutBerry/stack/blob/d861030a3c0c91f498dcd6c965faee6e2059a496/contracts/mocks/TestGatedComputing.sol
:thinking:

10

:laughing: Yep, that one is small. The cost for that is 128.903 gas