Comments (17)
Transcluding essence of comment from other discussion thread:
Immediate execution is needed for certain fee models, including Ethereum-style unused-gas refunds and in-protocol non-proportional fee burning.
- Gas refunds: block producers don't know how much gas a transaction will actually pay unless they execute it immediately.
- Fee burning: every byte in a block and every operation needs to be paid for with burned fees. This means invalid transactions can't be included in blocks, which by definition precludes deferred execution.
Fee burning is especially important, and seeing a rise in usage in modern blockchain designs because it provides a sink for coins, instead of only the sources that the original Bitcoin design has (new coin issuance with block rewards). Sinks are invaluable as they create intrinsic demand for the coin (much like how taxes cannot be supplanted by printing money).
from celestia-core.
High level (and unfinished) overview on state execution and what places would need changes in tendermint to execute Txs (and update the AppHash/state root) in the same block.
Problem
Why bother and change the current model?
In the current execution model, blocks are executed against the app only after they are committed. Full block verification (incl. state) always needs access to transactions of the previous block:
state(1) = InitialState
state(h+1) <- Execute(state(h), ABCIApp, block(h))
For more info on Execute see: https://docs.tendermint.com/master/spec/blockchain/blockchain.html#execution
This causes all sorts of confusion when implementing an app module on top of this logic. In the context of LazyLedger particularly but basically in any chain / application where we want to generate fraud proofs the "one off" between block height and state height causes further issues. First, (state) fraud proofs are also generated one-off, meaning their generation is also delayed one block. Second, this means light clients that want to verify a fraud proof need to wait for and download an extra block/header as they will find the updated root only there. In this model a light client that receives a (state) fraud proof for block at height h from a (full) node would need to verify that against the block h-1 as the Tx are included in the previous block.
Why changing the current model might still be undesired?
The more changes we add to the current tendermint codebase, the more lazyledger-core diverges from tendermint, the more time consuming it will be to keep up with (critical) fixes from upstream. While it is true that we will make changes to Tendermint anyways, the changes regarding the execution model might be less contained and touch not a single but several go packages.
Changes
Theoretically changing Tendermint to immediate seems trivial: during the consensus steps of a round (propose, prevote, precommit), we need to update the state root before we proceed further (IMO the earlier we do so, the better). Practically, the changes will certainly be a bit more elaborate.
Another weirdness of the current implementation is that Block execution can happen from two different places: either from the Consensus or the Blockchain Reactor. At the same time the Blockchain reactor can modify the state of the consensus reactor (NOTE: This design deserves a proper review and refactoring independent from what we are trying to achieve here...). Block execution modifies the mempool and both the mempool as well as block execution itself have read/write access to the app via ABCI.
"Seal Phase"
Once all transactions for the current height are executed, we need to update the state root (aka AppHash in tendermint). (For the lack of a better name, let's call this seal phase for now).
We need to figure out when it’s reasonable (and safe to do this). My understanding is that we could execute *before *we even propose a block (first step) and there is no reason to wait until the before the precommit. As both @ebuchman and @zmanian suggested to do this before the precommit instead. So I’m probably missing something important here...
A high level overview of the tendermint steps:
(Image credits: https://docs.google.com/presentation/d/1k0CbJQBHoMJkuOXdAKHFw9dcaXES_3dFYnCp1I1bm2M/edit#slide=id.g3acacab17a_0_528)
Note that all steps come with timeouts which are critical for the consensus to make progress. It is critical that these timeouts need to be generous enough that we don’t end up timing out and skipping rounds without making any real progress. Hence, we might have to increase the timeout in between steps where execution happens. IMO the block is proposed directly with all Tx executed and state root up to date. This means increasing timeout_propose. Of course this can mean the nodes might execute blocks which don’t end up being committed to (and waste valuable computing time) but I don’t think this will be a problem in practice.
Consensus Reactor
This is where the meat is. We need to teach the reactor to only propose blocks with state roots updated according to the current transactions included in that block. (See the tendermint spec and the code for more details.)
Currently, the BlockExecutor runs on Commit and updates the mempool. The executor gets called by the blockchain reactor (which is a mess, e.g. look at this). The current battle tested blockchain reactor (used in the hub) is v0 and I’ve hoped we can avoid touching it. We could peek into the refactored versions (v1 and v2) in case the changes we need to make exceed a few lines.
Replay
Need to update replay logic accordingly. Here and in a few other places where blocks are replayed.
Blockchain Reactor
- TODO: Do we still need block execution in pool routine?
Mempool
What do we do with CheckTx?
- TODO
Gas Model
The current Gas model relies on running CheckTx (via ABCI). Tx are added to the mempool as a mempoolTx with gasWanted set to the corresponding ResponseCheckTx’s GasWanted.
My understanding is that we’d rather want users to pay only for the gas that was actually consumed instead of refunding unused gas (see this issue).
Validator Updates
Currently validator sets are tracked in this way by tendermint: transactions that affect the validator set proposed in block H will be committed in the block H+1, and therefore block H+2 will be committed by the new val set.
As state gets executed immediately, validator changes also happen immediately. This has two implications: first, we can get rid of Header.ValidatorHash as it isn’t the app’s output from the previous block anymore (and it simply represents the current validators that signed the block). The current validators (of height H) can be part of the state root.
Similarly Header.NextValidatorsHash needs to be changed to point to the validator set that will commit the next block H+1.
These changes substantially change the light-client model (see the spec for more details on the current model).
ABCI
ABCI connects the tendermint state machine with the application (this is the actual business logic state machine; e.g. in LazyLedger the app would be the PoS logic).
TODO
RPC
The light client uses 2 RPC end-points to get the signed headers and validator sets for given heights. Need to update the validator endpoint according to above changes to the validator sets tracked in the header/state:
https://docs.tendermint.com/master/rpc/#/Info/validators
This should be a very simple change as the RPC only reads
Further Note on dependencies between different components
This diagram illustrates read/write access of components to different kinds of state:
(Thanks to Sean aka @brapse for the diagram)
The problem here is that some of the read/write access above happens in go-routines and access is often guarded via mutexes. We have to be careful not to modify this in a way that could deadlock.
Voiced concerns
or you have to add a "block sealing" phase where the proposal block is updated with the
execution results before precommit, which can have subtle effects on round skipping logic
…
There might also be a DoS concern with the current gas model (as we have to run the Tx first).
from celestia-core.
When I wrote this issue V2 didn't seem ready (I even had a branch which deleted the other reactors; but back then tendermint didn't seem to make blocks 😬 I was in touch with @erikgrinaker, can't remember what the issue was)
v2 had a race condition where it tried to switch to the consensus reactor before it had been hooked up to the switch, and then just silently gave up on everything. It also had an issue with spinning on closed channels, using 100% CPU. The former has been fixed on master
by the changes introduced by state sync, but a separate fix hasn't been backported to 0.33.x. The channel spinning has been backported though.
from celestia-core.
Does this really matter though? If it only costs them what's used, and they only get paid for that, isn't it fine?
It's not, actually! Consider the case where there are three txs:
gas price | gas limit | |
---|---|---|
tx_1 |
1000 |
100 |
tx_2 |
900 |
50 |
tx_3 |
900 |
50 |
with a block gas limit of 100
. Without executing any transactions, the first one looks like it'd be the most profitable to include. But if that transaction only used 1
gas while the others used the full 50
, then clearly it would have been better to make a block with the last two transactions.
Eg. for ETH miners, my understanding is they take whats in their mempool, sort by gasprice, and execute until they get to the gas limit.
That's right, and you can't do this unless you immediately execute transactions.
Can't we ensure in CheckTx that users have enough balance to send two txs with full fee burning? Or is there some other sort of dependency between the txs that could invalidate the second tx only after full execution?
The first transaction could empty the user's account, making the second one invalid.
Also, one possible but maybe hacky approach at least to these fee issues is by doing full execution in CheckTx
I mean, if you just make CheckTx do full execution then that does kind of get you close to immediate execution, sure. There's still the issue of the appHash
/ stateRoot
being off by one.
from celestia-core.
The first transaction could empty the user's account, making the second one invalid.
Usually CheckTx is designed to check things that could decrement the users balance. So in principle this kind of thing shouldn't happen, but of course in practice if control over account funds are eg given to a contract then all bets are off.
I mean, if you just make CheckTx do full execution then that does kind of get you close to immediate execution, sure. There's still the issue of the appHash / stateRoot being off by one.
Good to know we at least have a stop gap. Fascinating to explore these boundaries of ABCI. The current design has lasted almost 5 years now, might be time to really rethink things for the next 5.
As for the off-by-one, that's more of a convenience issue right now since clients have to download an extra block? Or is there something more fundamental?
from celestia-core.
I'm 99% sure that Libra does immediate execution and invests a fairly large amount of code speculating execution states if multiple competing proposals exist at any height.
If we are executing blocks then ABCI will need the ability to potential abort an execution and revert state.
from celestia-core.
Thanks for this write up! Just a couple thoughts/questions:
which is a mess, e.g. look at this
LOL this is why we rewrote the blockchain reactor. Probably best to focus on v2 ...
we can get rid of Header.ValidatorHash as it isn’t the app’s output from the previous block anymore (and it simply represents the current validators that signed the block). The current validators (of height H) can be part of the state root.
I don't think we should get rid of Header.ValidatorHash. We want Tendermint light clients to work independent of any application, so saying "it can be part of the state root" doesn't help because then the pure Tendermint light client needs to be able to read arbitrary application roots.
Immediate execution is needed for certain fee models
Can't all of this still be done, just off-by-one?
Correct proposers should never include invalid txs in the first place (if CheckTx is written correctly), so apps can just punish proposers that do by slashing. And otherwise can't fee burning and gas refunds just happen as part of execution after the block is committed?
from celestia-core.
Is there any difference for this between the Go and Rust implementations of Tendermint?
from celestia-core.
The tendermint-rs repository doesn't contain a fullnode implementation yet. But the implementation aims to be compatible to the go one. (So the answer will be no unless we can merge our changes upstream of course).
I think there is another implementation in Rust by Codechain. Might be a good idea to look into that too.
from celestia-core.
I'm also dropping @adlerjohn's summary on how we can do fraud proofs in the current model:
Summary for keeping deferred execution:
- Invalid transactions (i.e. that modify the LL state) can be included in blocks, as we don't require non-proposers to immediately validate transactions.
- Block proposers can figure out if appropriate fees are paid, as fee payment is a predicate.
- In block n, transactions are included. In block n+1, the intermediate state roots for block n are included.
- If a transaction is invalid, then the pre- and post- intermediate state roots should be identical (i.e. the transactions is a no-op).
- If a transaction is invalid and the pre- and post- intermediate state roots aren't identical, then that's an invalid block, and provable with a fraud proof.
Since transactions and intermediate state roots aren't interleaved, but rather in separate reserved namespaces in the NMT, it's trivial to just shift which block the intermediate state roots are for.
from celestia-core.
Can't all of this still be done, just off-by-one?
Not in an incentive-compatible manner.
In the case of gas refunds, the block proposer doesn't know how much gas a transaction will actually use (and thus, how much they'll actually get paid) unless they execute it immediately. So checking for transaction validity (does this user have enough balance to pay for the transaction's gas limit) is sufficient for safety but not incentive-compatibility.
In the case of fee burning (or invalid transactions in general), block proposers can't include two transactions from the same account in the same block without executing them immediately. So proposers that do immediate execution have access to more transactions to potentially include in their blocks (i.e. more profit), and so all proposers will do immediate execution. Since every validator can be a proposer eventually, every validator will therefore do immediate execution all the time too. Not accounting for this in-protocol means smaller validators that can't afford to do immediate execution will eventually get pushed out by bigger validators.
from celestia-core.
LOL this is why we rewrote the blockchain reactor. Probably best to focus on v2 ...
When I wrote this issue V2 didn't seem ready (I even had a branch which deleted the other reactors; but back then tendermint didn't seem to make blocks 😬 I was in touch with @erikgrinaker, can't remember what the issue was). We are planning to switch as soon as possible though: #13
I don't think we should get rid of Header.ValidatorHash. We want Tendermint light clients to work independent of any application, so saying "it can be part of the state root" doesn't help because then the pure Tendermint light client needs to be able to read arbitrary application roots.
I guess in the light of using tendermint (consensus) for LL where (tendermint) application state is not arbitrary in the sense that we optimize for one minimal core application (and devs will write their application logic client side / using some exec environment). But that also means that we can't use the tendermint light client as is (and just add a data availability) but need to re-write some of the core logic there too.
from celestia-core.
In the case of gas refunds, the block proposer doesn't know how much gas a transaction will actually use (and thus, how much they'll actually get paid) unless they execute it immediately.
Does this really matter though? If it only costs them what's used, and they only get paid for that, isn't it fine? As long as the block gas limit is also based on what's actually used, which is maybe the real issue here: cosmos/cosmos-sdk#2150
Eg. for ETH miners, my understanding is they take whats in their mempool, sort by gasprice, and execute until they get to the gas limit. But they wouldn't like execute a transaction, realize the total gas used is too low, and then roll it back and try another one.
In the case of fee burning (or invalid transactions in general), block proposers can't include two transactions from the same account in the same block without executing them immediately.
Not sure I understand. We currently support multiple txs from the same account in a single block by making sure CheckTx is smart enough for it. Why would fee burning be any different? Can't we ensure in CheckTx that users have enough balance to send two txs with full fee burning? Or is there some other sort of dependency between the txs that could invalidate the second tx only after full execution?
from celestia-core.
Also, one possible but maybe hacky approach at least to these fee issues is by doing full execution in CheckTx (?!)
from celestia-core.
As for the off-by-one, that's more of a convenience issue right now since clients have to download an extra block? Or is there something more fundamental?
I have to think about this some more, but I don't see any inherent issue other than light clients having to wait for and download an extra block (and, you know, being hacky, which is a big issue 😂). Technically, if you're using state transition fraud proofs, then the last intermediate state root is the state root after applying all the transactions in the block, so light clients can just use that instead of the Tendermint appHash
.
One issue might be timing. The current timeouts between each stage of the Tendermint consensus process assume that transaction execution is pipelined. But I guess that's a system parameter, so not tied to Tendermint itself.
from celestia-core.
ref: tendermint/tendermint#7898
from celestia-core.
We decided this is out of scope at least until abci++ lands in tendermint for real. We can reconsider this next year.
from celestia-core.
Related Issues (20)
- Only reap txs that have been in the proposer’s mempool for a configurable amount of time.
- Add a high priority proposal txs channel in CAT
- Add more peers only to the mempool reactor
- Ask for wants from the first peer that gossips the compact block
- Distribute block data in compact blocks as block parts
- Upgrade to CometBFT v0.34.33
- Use `go.mod` go version in CI HOT 1
- Difference between `Validate` and `Verify` in `ShareProof` and `RowProof` HOT 3
- Return more information if `ShareProof` and `RowProof` verification failed
- Return a new file when reading trace files
- Sending messages slows to a crawl when connecting more peers. HOT 2
- Increase MaxBlockSizeBytes to 128 MiB in a release of the celestia-core HOT 1
- Peers disconnect frequently despite running default software HOT 1
- Benchmark the consensus reactor HOT 1
- Do we check this? i.e. rp.EndRow > rp.StartRow. If not, do we want to check this? HOT 2
- Consistent row proof range
- govulncheck fails on main branch HOT 1
- Expand TxStatus to include rejected transactions
- Remove v0 mempool HOT 2
- TestTxPool_ConcurrentlyAddingTx is flaky
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from celestia-core.