Deterministic computations

Background: If you have started to look into the Coinweb protocol, you will see that we talk a lot about deterministic computations. The reason for this is that one of the main objectives behind the Coinweb protocol is to enable deterministic computations across large numbers of independent blockchains.

What is deterministic computation and why it is essential

"A deterministic computation is a computation that given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states."

This simply means that a computation, for example, a smart contract execution, will always produce the same output if the input is the same.

The definition of deterministic computation is very simple, but the implications of this property are very powerful. We will go through why the deterministic property is so important and how it differs from non-deterministic computations. We will also see how we can make dApps and blockchains more valuable by making more computations deterministic.

An easy way to see why the deterministic property is useful for blockchain computations is to consider an opposite scenario, where the computations are not deterministic. In that case, a smart contract could give different results each time it was executed, even if the inputs were the same. For blockchains, this would be a disaster, it would be impossible for the blockchain nodes in the network to determine the correct state since there would be no way to prove if the result of a computation is correct or not.

A slight variation to the scenario would be a blockchain system where computations gave the same result most of the time, but not always. Depending on how often there would be variations in the result, one could see that such a system could still work. However, it would mean that the users of the blockchain would have to account for the risk of an unexpected result every time they interacted with the system. The risk of unexpected results would also affect dApp developers. Let's say a dApp developer wanted to build a dApp for staking LP tokens, this dApp would first accumulate the risk that its interaction with the LP token contract gave an unexpected result. Then it would add the risk of its own contract giving unexpected results for every contract execution. If another dApp developer decides to build another dApp on top of this dApp again, that new dApp would accumulate all the risk for unexpected results from the dApps below.

Risk accumulates with increased complexity

As we can see from the last example, if the computations are not deterministic, the risk of unexpected results grows with the complexity of the computations. Adding more dApps on top of each other increases the complexity of the computations and at some point, the accumulated risks become unacceptable for end-users and no further complexity can be added and still be useful.

If the computations in blockchain from the example above had been deterministic instead of non-deterministic, there would be no risk of unexpected results. Without those risks, more complex dApps can be created. The dApps become more composable, allowing them to be used as building blocks in more and more complex structures. For end-users, this means that they can interact with other blockchain users in more and more complex ways, unlocking more use cases and value streams.

Deterministic computations in L1

Computations in L1 blockchains become deterministic because the nodes all run software that follows the same rules. The nodes can verify the correctness of other nodes by comparing the results of their computations. To do these comparisons, blockchain nodes use cryptographic functions that can create unique "fingerprints" for sets of data. These "fingerprints" are very secure, and in practice impossible to forge. L1 blockchains use distributed consensus algorithms such as proof of work, or proof of stake to enable the nodes of the network to agree on which input to process.* Since nodes all run software that follows the same rules, and they have agreed to process the same input, the resulting output of their computations will be the same for all honest nodes. (After agreeing on the input, it is essential that no other data is added to the computation.) The output is appended to the existing blockchain data, which determines the new state of the blockchain. After processing a block, all nodes in the network should eventually be replicas of each other, all having the same state (this might not happen immediately).

As mentioned above, cryptographic functions are used by nodes to prove and verify that they have the same state as other nodes.

*(Most L1 networks require all nodes to also perform all of the deterministic computations to verify the result, which is not necessary. This causes problems, as discussed here )

Properties of cryptographic functions

Cryptographic functions are mathematical constructs based on different mathematical formulas that make it possible to create hard, verifiable proof that certain information is true or not. These proofs can be called hard because they can ultimately be broken down into fundamental mathematical axioms. This hard link to mathematical proofs combined with deterministic computation is what makes it possible to create complex interwoven structures of smart contracts that still can be relied upon and used to securely transfer value between users of blockchain dApps.

Extending deterministic computations to include data from many independent blockchains.

If a deterministic computation could accept input from many different blockchains, it would mean that dApps and data from these blockchains could be combined into even more complex smart contract structures, allowing users from many different blockchains interact and exchange value with more users and in more useful ways.

A requirement for this to be possible is that the hard mathematical proofs from the L1 blockchains can be linked through equally hard mathematical proofs between the blockchains.

To maintain the deterministic property, it is also essential that no additional information is added, outside the information already provable in L1.

At first glance, keeping computations on data from different blockchains deterministic might seem impossible. Firstly, the nodes that agree on the inputs for the data are not the same, or even communicating with each other between different blockchain networks. A Bitcoin node will not care about Ethereum transactions and vice versa. This means that there is no agreement between the networks on what their common output should be. They care only about inputs and outputs within the same network. To make things even more complicated, the nodes within one network can also disagree on which input should be accepted, causing different nodes to temporarily have different states, following the same rules for processing, but with different inputs to the computation.

The second problem is to verify the information between the blockchains, if a smart contract on Blockchain A is to verify the state of Blockchain B, it somehow needs to get access to the information in Blockchain B. The nodes of the different blockchains do not talk to each other, so they can neither send nor receive any information to the other Blockchain without a third-party actor relaying information between them. Adding a third party to relay information between the blockchains allows additional information to be added to the computation and destroys the deterministic property. Even if the third party is a blockchain or validator network with its own cryptographic proofs, those proofs are external to the L1 proof chain and will be invalidated in the case of any delayed discrepancies between the blockchains, retrospectively changing the inputs to the cross-chain computations on one chain without the possibility of altering the output on the other. This will lead to the accumulated risk problems discussed in the first chapter.

The solutions

As we can see from the sections above, two problems must be solved for the deterministic property to be maintained for computations with inputs from independent blockchains. (And 2 problems to be solved for the system to be useful) For a system to maintain the deterministic property of computation between different blockchains:

1. There must be a way to prove and verify information between the blockchains without using L1 smart contracts or external relayers.
2. If one blockchain retrospectively changes state, the computation must remain deterministic even if the input changes.

For the system to be useful:

3. Retrospective state changes must not accumulate across the system and make it unstable.
4. **Cross-chain operations must be executed instantly for end users, similar to regular block confirmation time in L1 **

Solution to problem 1. Proving and verifyng information between the blockchains without using L1 smart contracts or external relayers: The solution here is to move the computation as well as the verification out of the L1 blockchains. This is the only way to create a consistent and scalable interoperability layer between blockchains. Coinweb does this by using RDoC (Refereed Delegation of Computation). What RDoC does in short, is to use cryptographic functions to link the hard proofs within each L1 to each other and also verify the results of the computations in the Coinweb layer without adding any additional inputs to the inputs coming from the L1's. In this way, the computations maintain the hard mathematical provability coming from the L1 chains.

Solution to problem 2. Keeping computations deterministic despite retrospective state changes in L1: To keep determinism despite changing inputs it is necessary to allow L2 computations to reorg in the same way as on L1 blockchains. If the input changes, so will the computation. If this is not allowed, the state of the system will diverge from the L1 state and accumulate instabilities from the L1 blockchains over time. This is a weakness with current interoperability solutions and the subject of criticism of many interoperability projects. This is one of the fundamental problems that Coinweb solves, so this criticism can no longer be applied to interoperability projects in general.

Solution to problem 3. Avoiding instabilities in L1 blockchains to propagate and accumulate with increasing number of chains: To solve this problem, there is an important property of blockchains that should be considered. It is that for each new block that is confirmed, the probability of older blocks being removed is reduced. The probability of a block being removed can be set to an arbitrarily low value, just by waiting for more blocks to be confirmed on top of it. The same applies to the probability of L1 instabilities propagating in an L2 computational layer. By applying a weighted State propagation graph to the interchain information exchange, even with a relatively modest requirement for block confirmations, the probability of multi-step instability propagation can be set lower than the probability of individual L1 reorgs. Read more about Coinweb's consistent interchain settlement layer here

Solution to problem 4. Instant cross-chain operations for end users: The solution to this problem already exists in the form of cross-chain liquidity providers earning fees from expediting cross-chain operations for end users. A current problem for all operators in this market is that they depend on off-chain applications(multi-sig bridges,oracles, relayers etc) not bound by the strong security guarantees of the L1 blockchains. These off-chain applications also break the deterministic property, reducing the composability of dApps between blockchains. With current solutions, the cross-chain operations become the weak links, which translates directly to higher costs and less room for innovation. Since Coinweb's cross-chain operations are consistent and deterministic, all the additional risks and costs added by the off-chain applications disappear. The cross-chain market operators can now operate at the same security level as L1 dApps, giving them considerable competitive advantages compared to building on risk-prone off-chain applications. You can read more about the cross-chain information market here.