Add Warp Verification Results to Block instead of using Predicate

[aaronbuchwald]

Problem: Processing Historical Blocks with Warp

Avalanche Warp Messaging leverages the P-Chain to provide read access to the validator set of every Subnet on Avalanche. To provide a canonical view for verifying Avalanche Warp Messages, each block is included within a BlockContext provided by the ProposerVM: https://github.com/ava-labs/avalanchego/blob/master/vms/proposervm/README.md.

The current implementation provides the PChainHeight used by the ProposerVM to validate the block. Warp message verification verifies all messages as being signed by a sufficient portion of stake of the validator set using the validator set provided by the P-Chain at that height.

However, the P-Chain does not and should not be required to provide permanent archival support (the ability to lookup the state at any point in its history) efficiently since this would drastically increase the requirements for validating the primary network and to validate warp messages.

The problem is that if a block occurs on Subnet-EVM at height 1000 that references P-Chain height 1100, then in the future when validators bootstrap the network they may not have an easy lookup to verify the warp messages were valid.

Therefore, in order to handle re-processing warp messages that depend on historical P-Chain states at some point in the future, we need to provide an alternative to a permanent archival P-Chain index.

Current Implementation: Precompile Predicates

Currently, Subnet-EVM supports historical verification of Avalanche Warp Messages by including a predicate encoded in the access list of transactions. The predicate is verified before executing the transaction and the transaction is not considered valid to be included in a block if the predicate fails verification.

Since the predicate must have passed verification for the warp message to be included in a block, when we re-process historical blocks we can simply assume that the predicate was validated correctly by the validator set of the network when it was first processed and we don't need to deal at all with warp messages that failed verification.

Pros:

• Simple and easy to reason about within the EVM
• No need to perform warp message verification during the EVM's execution (we do it in advance)
• All warp messages are declared in the block. As a result, we don't need to execute the block to know what warp messages need to be verified throughout its execution. This means warp messages can be verified in parallel prior to entering the EVM's execution (or concurrently with EVM execution as a further optimization)

Cons:

• Potential DoS vector if Warp message verification is expensive
• complexity: which alternative is the simplest and easiest to reason about?

Alternative: Stapling Results to Block

The alternative as implemented in HyperSDK is to staple the results of each warp message that gets verified throughout the VM's execution into the block itself. This ensures that when re-processing a historical block, every warp message that is referenced throughout the VM's execution has its result (success/failure) encoded and present in the block, so that the VM can use the "remembered" result of warp message verification.

Pros:

• Avoids encoding the predicate in the transaction, which should make it easier to use warp precompile (encode as calldata argument to precompile as opposed to a special case use of transaction access list)
• Avoids potential DoS vector from an added verification step to transaction verification

Cons:

• Warp messages are no longer declared in advance so the block builder needs to perform warp message verification serially as messages are referenced throughout EVM execution
• Complexity: which alternative is the simplest and easiest to reason about?

[aaronbuchwald]

Going to try the implementation strategy:

Each predicate will optionally return a Result. Each transaction encodes this as its own map of results to be encoded in the block header (precompileAddress -> Result).
The miner will check predicates for each transaction and generate a map for each one that gets included in the block.
If the transaction is dropped so is the result, if the transaction is included it gets added to the list just like any other.
In commitTransactions, we serialize this result and encode it in the header. We will additionally call a setter on the StateDB to populate the results for the EVM to use throughout its execution.

During verify, we will modify the pre-verify check to call CheckPredicates for each transaction in parallel, wait for all of them to complete, and verify the result against the header.Extra data.

Pros:

• we can parallelize both the block builder and verify path, so that we can make warp verification as cheap as possible
• removes mempool DoS vector
• since predicate does not result in dropping transactions, we can potentially do more work inside of the predicate and support multiple warp messages per transaction

Cons:

• this generalizes a lot of stuff that we will probably only use for Warp, hopefully the generalization provides better abstraction
• potentially more complex solution

[aaronbuchwald]

Addressed by #823

[cam-schultz]

In the issue description, one of the pros of the block stapling approach is that it Avoids encoding the predicate in the transaction, which should make it easier to use warp precompile (encode as calldata argument to precompile as opposed to a special case use of transaction access list)

However, I see that the warp message bytes are still stored in the access list in the tx that calls getVerifiedWarpMessage:
https://github.com/ava-labs/subnet-evm/blob/master/x/warp/contract_warp_handler.go#L54
https://github.com/ava-labs/subnet-evm/blob/master/core/state/statedb.go#L1264

Did the implementation end up diverging from the description, or am I misunderstanding something?