Add State Root in Neo

[ZhangTao1596]

Summary or problem description

The roles of state root:

1. It ensures the consistency of the ledger information of each node, not just the consistency of the blocks.
2. Using the MPT method to generate the state root can provide a proof of path, and provides a way to verify the correct execution of a transaction for light nodes, cross-chain.

In #385, we have discussed the details about the advantages and disadvantages of putting the state root in the block header and p2p messages. Considering that the upgrade of neo-vm will cause state changes, it has been finally decided to put the state root in the p2p message to complete decoupling, so that during the upgrade, the state root is updated while preserving the blocks.

Thanks to @erikzhang @igormcoelho @lock9 @jsolman @shargon for the discussion in #385 #901 and #302. Now we can discuss the specific solutions.

Do you have any solution you want to propose?

Issues

• State may change during neo upgrade. (It implies that the latest state is more reliable than before)

• State validators can be different from block validators. When the validator changes, the signature verification of the old state will not be able to be verified by the nearest validator.

• Nodes may send fault state root messages.

• If the state consensus is coupled with block consensus, when upgrading neo-vm, will lead to block consensus waiting for state consensus to complete.

Goals

• Decoupling state and block
• Upgradable state
• Decoupling state consensus with block consensus

Structure of state root

One-to-one correspondence between state root and block

• Version: version of state, this may change after upgrade.
• Index: block index.
• StateRoot: state root of index for the corresponding block.
• Consensus: multi-sig address of validators. It indicates which validators verified the state root.
• Witness: signature of validators

When there are multiple state roots of the same block, the state root signed by subsequent validators is more effective. In case of the validator is the same, the state root with the higher version number has the higher effectiveness.

consensus

roles:

• State root validation
• Supports vm upgrade. The state of the corresponding confirmed block may be changed after the vm upgrade. The state root can be updated without changing the confirmed block.
• Minimizes the impact on existing consensus and block synchronization speed

We propose three solutions here.

Solution 1: Extend the existing consensus message to support three types of consensus content: block, state root, both block and state root

When state and block both have synchronized, the state root and block will be approved in the same consensus message. Otherwise, state root and block will be in different consensus processes.

1. Changes of consensus

   a) Adds state root part in PrepareRequest
   
   b) Adds signature of state root in Commit message
   

2. Upgrade
   If the upgrade will cause state changes, then upgrade the version number of the state root. At this time, block consensus and state consensus will be performed separately. Only when the state consensus reaches the latest block height, the two processes can be merged in one process.

Solution 2: Using another dbft process for state root consensus

1. Changes of consensus

   a) Add state consensus message
   

   b) message body
   

2. Upgrade
   If the upgrade will cause state changes, then upgrade the version number of the state root. During the process of resynchronizing block, if the consensus nodes find the state root inconsistent with the previous one, it will trigger the state root consensus and broadcast the latest state root.

Solution 3: The consensus node signs the current state root and broadcasts it after the block generated.

1. There is no change in consensus process, just adding one p2p message of state root with signature.
   

Nodes can determine the state root after they have collected enough signatures.

2. Upgrade
   If the upgrade results in state changes, then upgrade the state root version number. During the process of resynchronizing block, if a state root is inconsistent with the previous one, the consensus node will directly broadcast its signature without having to perform consensus with other consensus nodes.

Comparison of the three solutions

Risks

1. Suppose we want to upgrade neo-vm and reconfirm all state roots after running NEO3 for one year. If block time is 15s, assuming that each state root needs 1s to reach consensus, it takes about 24 days to reconfirm all state roots. This period of time will affect the use of related functions. This is why we prefer to reconfirm different state root and support consensus for multiple state roots at the same time.
2. The Solution 3 will increase the node memory and even be attacked by malicious messages. Nodes need to collect the signature of the consensus node. If a single consensus node create a single prioritized message that can never collect enough signatures for nodes, the other nodes will have to store all messages since they does not know which priority message will be collected.
3. For Solution 1 and Solution 2, they can support multi-process consensus of state root. Because the block is synchronized first, once the block synchronization completed, the condition of the state root can be meet, but this will introduce more consensus messages.

p2p messages and sync

state root sync

Principles when a node obtains a official state root:

• The state root confirmed by the newly selected consensus node has the higher priority
• If the state root is confirmed by the same consensus node, the state root with the higher version has the higher priority
• The state root with the high priority will replace those with the lower priority

The node uses state_height to indicate that it confirms the height of the state. After synchronizing the block, it will calculate the state root by itself and compare it with the state root signed by the consensus node. If the state root is consistent, the state_height increases.
Otherwise, set state_height to the index where state root starts to be unconsistent with the official state root. But node can still broadcast the official state root.

For a new node when synchronizing the block and state, it is necessary to first synchronize the block and calculate the local state root information, and then synchronize the state information signed by consensus nodes. At the same time,

1. Using the consensus of the state root to verify whether the state root is valid.
2. Comparing whether the state root calculated by the local node for the block is consistent with the synchronized state root. If they are not consistent, stop the verification service.

p2p message

1. Add LastStateIndex in ping payload
   

2. Add state type in invmessage and add GetStateRoots and StateRoot payload

• GetStateRoots payload
  

• StateRoot payload
  

Neo Version

• Neo 3

Which modules does this update apply to?

• Consensus
• Ledger
• P2P (TCP)

Next Step

If you support solution 1, vote 👍 and give your reasons.
If you support solution 2, vote ❤️ and give your reasons.
If you support solution 3, vote 🎉 and give your reasons.
If you have other solutions, you can comment in this issue and open a new issue addressing the design of your solution if necessary. We will update your solution in the issue if the design is quite complete.

[shargon]

1 - because is easier, simpler and produce less overload.

[longfeiWan9]

Some projects are waiting for this StateRoot eagerly. And it is a hug blocker for Neo NOT providing stateRoot. So it is awesome to see the progress on it ..

Please, please move forward with the solution and implementation. 💯 :)

Vote for solution 3. Simply to implement and do not bring too much burden to CN.

[vncoelho]

I vote for solution 3, however, the description and proposal can still be improved. Perhaps we do not even need a new message. We could add in the PrepReq as a non-signed part of it, then, a normal flow as today can be kept.

[ZhangTao1596]

@erikzhang What's your opinion, dalao?

[ZhangTao1596]

Maybe we can combine Solution1 and Solution3. Consensus nodes confirm block and state root together of new block. At the same time, if there are previously unconfirmed state root, consensus nodes send their signature.

[ZhangTao1596]

There are two issues that have not been fully resolved, if the state root has changed after the upgrade.

1. How to generate a new state root chain with signatures?

• If use consensus or broadcast signature, a large number of p2p messages will be generated, and it will take a lot of time
• If use manual offline signature, which means that collect the signature of the state root from other consensus nodes, and then export the complete state root by manual. However, this method is somewhat inconvenient to operate.

2. How to sync to other nodes?

• Broadcast new state root in batches, there will be a lot of p2p messages

[ZhangTao1596]

Appending

Because each full node will generate an local StateRoot chain, using the latest StateRoot signed by the latest consensus to verify with the latest stateRoot of the local can ensure the consistency of the local state and the state of the consensus node. Therefore, the node only needs to store the latest StateRoot , and does not need to store the historical StateRoot.

1. Wether the consensus node is upgraded or not, they can continue to confirm the latest state, and do not need to re-confirm the previous state. Therefore, we add PreHash in every StateRoot body to check historical states.
2. The node always uses the latest StateRoot for verification.
3. The user or light node can only use the latest StateRoot for query and verification. The full node cannot provide verification of the previous state, as they don't store old state.

Since it is no longer necessary to re-sign the previous StateRoot, we recommend Solution 1, impovement and details as following.

Structure

• Version: Version of state root.
• Index: Block index.
• PreHash: Hash of last StateRoot, calculate from Version, Index, Prehash, StateRoot.
• StateRoot: The StateRoot of specific index block.
• Consensus: Multi-sig address of validators. It indicates which validators verified the StateRoot.
• Witness: Signature of validator

Consensus

The StateRoot and block will be confirmed in the same consensus message.

1. Add State relating part in PrepareRequest

2. Add extra signature of state in Commit message

3. When consensus process finished, consensus nodes will relay Block and StateRoot

Node Sync

When receiving the latest StateRoot message, the node will first verify its legitimacy, and then compare the local PreHash and StateRoot. If they are equal, it means that the current state of the node is consistent with the consensus node, and the StateHeight is setted to the current block height.

Upgrade

Background: When upgrade consensus, a new node is first deployed to synchronize the block to the latest height, then the old node is closed, and a validator wallet is opened in the new node to start consensus.

Consensus nodes always treat their local state as correct. They use their local StateRoot to proposal or check other validator's proposal. If more than (n-1)/3 consensus nodes' StateRoot are different from others, consensus won't be reached.

Plan

I will complete this feature in 4 individual steps (pull request)

1. Implement build in MPT. I can refer rodoufu's work. Merkle Patricia Tries (2x) neo-modules#97
2. Add StateRoot in blockchain module.
3. Add StateRoot in ConsensusContext and add p2p messages support.
4. Add rpc interface for proof of path.

@erikzhang @igormcoelho @vncoelho @shargon
I think this is my final solution. Can you guys please take a look and show your opinions?

[ZhangTao1596]

@erikzhang @igormcoelho @vncoelho @shargon
Can you please take a look and share your opinions?

[shargon]

Can you please take a look and share your opinions?

I am not very fan of send the state root by p2p, I prefer to write the previous state in the next block.

[vncoelho]

@KickSeason, NeoResearch has been studying the situation with care, in particular, because it is a critical decision that implicates in many other important features for the NEO ecosystem.
We have been conducting some studies on the topics aligned with the idea and vision @erikzhang provided.

[igormcoelho]

@KickSeason Sorry for the long time waiting, complicated month(s) here in Brazil.
Just to quickly highlight: we need at least 15 secs (~1 block time) to validate state, otherwise we severely harm scalability. I think that's what you're proposing, right? To use dbft to validate state on next consensus round, regarding current state (prevBlock) that should be the same on all CN.
Besides that, the Block message itself can carry the statehash, just not in its header, may as an appendix. Distributing only statehash on p2p is more complicated than just sending the block with the latest validated hash (at that height). Is it more or less correct?
Regarding the code, I'll try to review asap, to see which structure you've decided for MPT.

[roman-khimov]

Linking #1526 discussion there as it's directly related and IMO has a better option of storing state root for the previous block in the header.