search

celestiaorg / celestia-core

A fork of CometBFT
Apache License 2.0
491 stars 270 forks source link

Proposal: Immediate execution to accomodate ISRs #463

Closed evan-forbes closed 3 years ago

evan-forbes commented 3 years ago

Summary

Implement immediate execution to accommodate intermediate state roots.

Problem Definition

Intermediate State Roots (ISRs) allow state fraud proofs to be generated for a single transaction, as opposed to generating one for the entire block. Using these more concise proofs is crucial, not only because they will need to be quickly distributed via a p2p network, but also because the intended audience consists of light clients.

Generating the ISRs requires executing the transactions of a given block in the exact order in which they will be finalized. Tendermint’s current deferred execution design does not easily accommodate this, as we need the ISRs for that block to be included in the block data, and transactions are not executed in order until the commit has already been finalized.

One solution, mentioned to me by @liamsi a few months ago but not written down anywhere afaict, is for the proposer to actually execute the transactions and return the ISRs in PreprocessTxs, then not execute them again after finalizing the commit. Other validators/full nodes would either execute each transaction after the commit has been finalized like they do now, or first verifying the ISRs before voting. This change would admittedly be a little hefty, but definitely doable, imho.

To those familiar with the going ons of the future tendermint, this might sound similar to ABCI++. That’s because, at least for our needs, it is! We will eventually use PrepareProposal phase to do something similar to what is described above. The main problem being that ABCI++ is of course not implemented yet. Since it’s so similar though, it should be easy to refactor to it once it is, assuming that we do not simply wait before implementing.

Proposal

Add the intermediate state root to ResponseDeliverTx. 

message ResponseDeliverTx {
  uint32         code       = 1;
  bytes          data       = 2;
  string         log        = 3;  // nondeterministic
  string         info       = 4;  // nondeterministic
  int64          gas_wanted = 5 [json_name = "gas_wanted"];
  int64          gas_used   = 6 [json_name = "gas_used"];
  repeated Event events     = 7
      [(gogoproto.nullable) = false, (gogoproto.jsontag) = "events,omitempty"];
  string codespace = 8;
  bytes intermediate_state_root = 9;
}

The intermediate state root would be filled by modifying the sdk's BaseApp's DeliverTx method to add the current commit using the existing CommitMultiStore. 

isr := app.cms.Commit().Hash

Then we would also modify ResponsePreprocessTxs to include the ResponseDeliverTxs

message ResponsePreprocessTxs {
  repeated bytes            txs      = 1;
  tendermint.types.Messages messages = 2;
  repeated tendermint.types.ResponseDeliverTx deliver_responses = 4;
}

There when would need to change the PreprocessTxs in the app to also run DeliverTx on each of the transactions passed to it.

Finally, we would create a new method for BlockExecutor called ApplyProposalBlock that functions similarly to ApplyBlock, except it wouldn't run DeliverTx

Implementation

There would need to be at least 1 PR in core, the sdk, and the app, but likely more. The PRs should be merged by order of import, core -> sdk -> app

Conclusion

Whether we wait for ABCI++ and the ensuing cosmos-sdk update or not, we will still have to make changes similar to those suggested in the app and the sdk. It should also be noted that it is extremely likely that implementing immediate execution, while doable, will be significantly more involved than described above.

Refs

tracking issue #459 we should probably do #462 first Iff we don't wait for ABCI++ this prop pairs well with #454

liamsi commented 3 years ago

Some context:

nusret1996 commented 3 years ago

This is not urgent for the state fraud proofs. We will proceed assuming deferred execution.

evan-forbes commented 3 years ago

closing for now in favor of #481

hopefully we can revisit this soon with :sparkles: ABCI++ :sparkles: :crossed_fingers:

evan-forbes commented 3 years ago

as a personal note, I also made a very quick and dirty proof of concept to execute multiple transactions without actually writing to state. This would be needed for immediate execution, as validators will have to run each of the proposed transactions in order before voting.

https://github.com/celestiaorg/cosmos-sdk/blob/250965155ce54eb16299edf95a2520c6deed3afe/baseapp/baseapp_test.go#L1010-L1060

evan-forbes commented 3 years ago

another personal note: We don't actually have to do anything special to execute multiple transactions without writing to state. The BaseApp already manages different branches of the state for us. Each call to the DeliverTx method writes to a cached branch of the state that isn't committed to until calling the Commit method.

https://docs.cosmos.network/master/core/baseapp.html#state-updates

https://docs.cosmos.network/master/core/baseapp.html#delivertx-state-updates

liamsi commented 3 years ago

As soon as abci++ lands in tendermint we should try and look into immediate execution (even if we stick to the plan to launch with deferred exec) IMO.