Transactions order and Block generation

[realloc]

This proposal is closely related to #1284.

Transactions order and Block generation

To be able to verify State changes at each step, transaction execution order must be strictly defined. Transactions must be executed exactly in the order they appear in the Block. This guaranties double-spend protection, as transactions are verified on entering the block.

The other very important improvement is the increase of Successful TPS. Right now in Neo3-preview most of transactions would most probably just fail and, while having good overall TPS, the resulting successful TPS may be extremely low or, sometimes, even zero. Our talks to different enterprise representatives show that they don't care about TPS in general, but about successful useful TPS. This proposal solves failing Tx issue, increasing actual successful and useful TPS rate.

When composing a block, we evaluate it's value. The more TXs with higher fee the block has, the more valuable it is. So in case when CN has two equally valid block candidates, it would choose the one with higher value. In other words, CNs will try to fill the block with the maximum number of TXes having maximal fee in sum.

This means there will be no Verified Transactions pool as it is now. All valid transactions would be considered equal candidates for entering the block and Consensus Node is responsible for finding the best combination. It may be a computationally hard problem, so Consensus Node may propose not the best block, but a good enough one, correct, and on time.

Technically forming a block becomes a Knapsack Problem solving. Because Knapsack Problem solving approaches are well studied, there are a few ways to optimize this process and make new Block generation process fast enough and meeting any time limit requirements.

Block Proposals from CN Backup and ordinary nodes

Because forming a block becomes a Knapsack Problem solving, we propose to let other nodes in the network, not only the Primary CN, to propose their solutions to improve blocks quality. As soon as the newly agreed block becomes available, every node may start combining transactions from Memory Pool to get the block containing maximal number of transactions with maximum value. Such blocks would be broadcast to Consensus Nodes and stored in some buffer. Primary Consensus Node for this round just takes the best candidate or tries to generate its own combination. The reward for the block should be shared with the node that generated the best block proposal.

To avoid flooding network with block proposals, only best known blocks should be forwarded by nodes. If the node sees that there is a better block in it's local cache it just drops the bad proposal. So only a small number of best block candidates will be broadcast.

To prevent malicious nodes to drop someone else's better offer or to alienate it, the contents of the block candidate can be encrypted and the block's value field could be compared using homomorphic crypto-scheme.

This mechanism would motivate regular nodes to keep their local State valid and detect any anomalies promptly.

[lock9]

Hello @realloc,
Wouldn't it be possible for a node to always propose a block with an additional transaction, making his block always "the best option"?
If we have 10 transactions with 10 gas, if I send a block with these 10 transactions plus one transaction with 0.00000001 gas, won't it make my block to be chosen?

[realloc]

If block candidates are broadcast in unencrypted form, nothing stops an intermediate node from improving the block. That's the point, at the end CN will get the best candidate. But, most probably, block contents should be encrypted to let only the Primary CN and few Backup CNs to decrypt it's contents so that intermediate node could only compare block values, maybe without even revealing actual value by using homomorphic compare operations.

Returning to the case you've mentioned, each node proposing a block would try to pack as much transactions as possible until the block size limit is hit. Hence, most probably there will be no place in the proposed block to just add one more Tx. If there is a place for one more Tx, then the new block is better and, indeed, should be chosen instead of previous proposal.

[Tommo-L]

In other words, CNs will try to fill the block with the maximum number of TXes having maximal fee in sum.

dBFT2.0 is the way, right?

Block Proposals from CN Backup and ordinary nodes

If we treat Transaction as a small block, is there any big difference with current approach?

[realloc]

dBFT2.0 is the way, right?

Not exactly. Current dBFT2.0 doesn't consider the TX execution result, it just takes top N TXs from the list sorted by fee, as I remember.

In this proposal we suggest not to just take top N, but to select the best combination of transactions, seeing how the TXs order will affect the TXs execution result and the resulting "price" of the block.

If we treat Transaction as a small block, is there any big difference with current approach?

I think I don't understand the question. Could you please clarify?

[igormcoelho]

As I understood this, it's a logical proposal to try to maximize spent gas cost (maybe at minimal time?), but I dont believe its actually possible to solve such problems in such small time gaps, between block proposals. Because every change in tx order may affect the results of other transactions, requiring fresh restart for every possible order... @vncoelho and I mostly worked with optimization and metaheuristics over all our lifes, and for all algorithms I know, I really dont imagine one strategy that could do these things so fast, and also guarantee that p2p would actually deliver in time. And if it doesn't, it's wasted efforts, right?

[roman-khimov]

First of all, it's about including only real successful transactions into the block. We can include a gazillion of transactions into blocks, but if all of them fail --- the chain didn't do anything useful, all of this time/space is just wasted. But to ensure that we're only including successful transactions we need to execute them first, that's obvious.

This then raises a question of possible permutations with the solution to spread this work among all network's nodes (making running full non-CN node a bit more useful) and just confirm and accept the best combination at CN level. It's possible to do that, but I agree that there will be some performance impact.

At the same time (keep in mind that this was written almost a year ago for more enterprisy/private network scenarios) I see now that this probably contradicts some basic Neo 3 assumptions like users always paying for their transactions irrespective of result of these transactions. Absent this mechanism one could flood the network with failing transactions and waste a lot of bandwidth/CPU power to process them without paying (as they won't be included in blocks with this scheme) and it's a problem for public network.

[roman-khimov]

As explained in #1285 (comment) the "include successful transactions" goal can't be achieved and proposals from ordinary nodes are a completely different story (related to #2029). Therefore, I'm closing this one.