Lightweight state checksums in blocks

[realloc]

Lightweight state checksums in blocks

Summary or problem description

Neo3 is declared to be Enterprise ready, however, after discussions with enterprise representatives, we found out that it doesn't meet corporate requirements, that must match with national standard requirements which are in general in sync with Common Criteria (ISO/IEC 15408) international standards.

In short, there are requirements for auditability of changes and records and ability to verify the correctness of data and operations relying on the information from the blockchain itself. Currently it's not possible for Neo.

We propose a set of changes for Neo3.0 that would fulfill those requirements and still keep the Neo's unique value propositions.

Do you have any solution you want to propose?

The main proposal is to have a lightweight state change checksums included in transactions and in block. Proof of concept code can be seen on GitHub: https://github.com/nspcc-dev/state-checksum

Other proposals in this series cover changes for solving issues related to state introduction and inclusion of state information into the block.

Definition of State

We are targeting Neo3, so we can define state for particular Neo Blockchain height as a set of all keys and values of Contract, Storage and OracleResults databases of Neo node. It can be represented as a dump, where all keys are sorted and concatenated with their values and then converted to a byte format.

Each key-value pair can be treated as a separate entity, while only the whole set of such pairs may be called State. Ordering of records is required for having a deterministic way of creating a full state snapshot.

Changes in State

Each transaction is invocation of a Smart Contract, either normal or native one. Smart Contract run leaves side effects, according to our definition of State, they are changes in Key-Value pairs in Node database. Hence, we can define State change after Smart Contract invocation transaction as a set of records identifying which keys were changed, deleted or added.

For Oracle transactions, the side effect will be a record in OracleResults database, which follows the same rules.

State Change's checksum

Because state validation should not affect TPS much, the validation process must be fast and not depend on the total state size. We propose to use cryptographic hash function (SHA256 in our example, but we should consider other options, like homomorphic hashes) to check each key-value change operation in a state change, and then XOR the resulting set to receive the overall change checksum.

The useful property of this approach is that we can XOR all state change checksums from the genesis block and get the correct checksum for the current state. Because XOR is applied to cryptographic hashes, it still gives almost the same collision protection, so it will be hard enough to forge checksum for transactions having wrong state change.

Transaction fields in Block

To let a node verify that it's local State is correct, we need to add state change checksum field to each transaction in Block. This field stores a checksum of a dump of changes in state, made by transaction after it's execution. Because checksum is a XOR of all key-value changes’ hashes, it has constant length and does not depend on the number of key-value pairs affected by transaction’s state change.

When a node verifies transaction, it:

• runs invoked Smart Contract code in VM
• gets State Change,
• calculates State Change's checksum
• compares resulted checksum with transaction's state change hash

If hashes match, it means the local State changes are correct and equal to what was expected after transaction execution. In the same way transaction is verified by Consensus Nodes upon entering the block.

The checksum is not recorded in Transaction when it’s committed to the network, it’s only added in the block, because it depends on the execution order and previous state. For the wallets Transaction operations do not change.

Block Fields

Additionally to Transaction state change checksum, we propose to add Block's State checksum. It will contain XOR of State's Key-Value pairs for the particular blockchain height. Because it's calculated using the same algorithm as transaction state changes, XORing all transaction state changes with previous block's state checksum would give the current block checksum. However, it should be calculated against node's local storage to make sure it's in sync with the others.

This operation doesn’t require to recalculate the whole state hashes, just checksum state change, which is a lightweight XOR of fast hashes over small change set.

Additional proposals to address new issues

• Transactions order and Block generation Transactions order and Block generation #1285
• State snapshots State snapshots and not-so-light nodes #1286
• Backwards Compatibility and bug fixing Backwards compatibility and bug fixing #1287

Neo Version

• Neo 3

Where in the software does this update applies to?

• Consensus
• CLI
• Ledger
• P2P (TCP)
• RPC (HTTP)
• VM

[shargon]

I think that this is a very good feature, but in order to implement it without change the current cosensus mechanism (CN doesn't execute the TX) we must store the previous checksum state (as with the hash), not the current one.

Pros:

• We have the desired integrity.
• 100% compatible with the current consensus.

Cons:

• If we have a bug, we need to trim/drop the last block, because the state will be different than the previous block.

[realloc]

@shargon Maybe it's a good time to alter the consensus mechanism and switch from random state Tx TPS to useful TPS =)

[Tommo-L]

Personally, I like the checksum, if we don't consider state proof path.

[realloc]

We could consider having lightweight checksums in the block for each actual block, and having heavyweight MTP for proof path plus checksum for immutability check off-chain. One of them (checksum or MTP root) has to be in the block anyway.