Removing global state root

[ilblackdragon]

Idea around figuring out how to remove global state root (and chunk level state roots), removing need to maintain patricia merkle tree between all accounts. While maintaining same level of provability/light client.

Inspired by convo with Fuel network

They are using UTXO model to avoid the need to have global state root

What are problems this would try to solve:
Maintaining large merkle tree that must be updated after processing every chunk
Large Fraud proofs of the whole chunk

Because NEAR already has isolation on the account level, we can consider that last update to the account is an unspent output and each receipt takes last unspent output of that that account and transforms into a new one.

Applying it to NEAR:

• Computation of state root for chunks/blocks is removed
• For each account let’s maintain it’s own state’s root ACC_STATE[account_id][block_id]
• The exact mechanics of maintaining it can be either merkalization of records or just hash the full state if it’s small and used frequently enough.
• A receipt X incoming to account1 in block1, would modify state of this account from where it was modified in the previous block0 ACC_STATE[account1][block0] -> ACC_STATE[account1][block1]
• All the execution results (prev_block_acc_i, ACC_STATE[account_i][block1], logs) get merkelized and the final EXECUTION_ROOT[block1] is stored in next chunk header + block header
• A merkle mountain range of all receipt outputs is updated with all of the receipts outcomes from given chunk
• If an observer sees invalid ACC_STATE for some account in the new chunk, they can create a proof just for that given tx -> outcome, fetching the state of the account prior to that transaction.
• Proof of fetched state for given account_id instead of going to state root, goes from the last execution result, it’s inclusion in the block and that block in the merkle mountain range of the latest block.

Questions:

• how to check if there was a newer transaction that changed given account?
• Maintain a Merkle mountain range of last account states?
• What are the requirements for state sync?

—-

Same:

• Already compute merkle roots on the account state level

Pros:

• Removing log^2(N) reads/writes and log(N)*K of hash computations for maintaining global state root
• Fraud proofs are as big as witness for the single transaction. Fraud proofs are easier as they only need to check on the single tx/account level
• Light clients can verify that

Cons:

• Chunk is larger as it contains additional 32 bytes x number of receipts processed in the last chunk
• Longer proofs for light clients

[mzhangmzz]

Some initial thoughts:

• We will need proof for whether an account exists or not, so we probably still need to maintain some form of merkelized structure for all accounts and include the root of that in each block/chunk.
• For state sync, with the new proposal, each node doesn't need the whole state to process new blocks/chunks, they only need the accounts touched in the block. So nodes don't have to state sync the entire state at once. They need to sync the set of all accounts, which is merkelized, then only sync full account data when they need to, assuming that the number of accounts touched in one chunk is bounded and it is relatively fast to sync data for them.
• This will make storage access much cheaper. Right now, each storage write generate O(N) disk access where N is the depth of the trie node. Using this proposal, if the account is small enough, it becomes essentially constant. For big accounts, we may still need to maintain a trie for them but these separate tries will still be much smaller than the entire state trie we have today. @jakmeier @Longarithm you might find this idea interesting since it will remove TTN cost for small accounts and significantly decrease that for large accounts.

[robin-near]

This is soooo interesting.

We will need proof for whether an account exists or not, so we probably still need to maintain some form of merkelized structure for all accounts and include the root of that in each block/chunk.

• Perhaps we can treat CreateAccount receipts as modifying a special account - call it the account registry - which contains just AccountId -> () mappings (and mayyybe some additional metadata). That can then be the merklized set of existing accounts, and we don't need special handling. It does need to be sharded though.

• Making storage per account also has the advantage that execution of receipts to different accounts can be done in parallel. Well, we maybe already can do that today but at least need to touch the merkle tree synchronously.

• If we store each account separately, then what exactly do we need shards for? How crazy is it to remove sharding altogether, and have each account be its own "shard"? We of course need some assignment of accounts for each validator but maybe that can be done with some kind of hash partitioning (e.g. in this epoch, validator1.near is assigned accounts whose sha3(account_id || seed) (for a random seed for this epoch) has the last 16 bits be in range [57, 1458). ). Not sure how chunks would work but at most they are just a batching of multiple accounts.

[Longarithm]

I'll try to rephrase it to understand the idea better:

Currently we maintain global state root and recompute it for each new chunk. This requires O(N) overhead to recompute it where N is the depth of account.

Instead, each node can locally maintain a mapping from each account key to its state and last block where the account was modified. When new receipt occurs, we easily modify our mapping and append receipt output to merkle tree of existing outputs. The latter one is fast, because we just need a path to the previous receipt output in merkle tree and can keep it in memory. To prove the account state, we prove the last receipt output where account was modified. It can be slow, but it doesn't slow down block/chunk production.

However, I feel that answering the question "how to check if there was a newer transaction that changed given account?" leads to the same bottleneck as we have now. For example, account can be untouched in a year, and if one wants to prove its state, they need to prove that it was untouched in every block during this year.

Maybe we can achieve something if we try different approaches for accounts which are touched rarely or frequently, but I would need to think more about it.

Also I think that we need to treat each contract data key as a separate account, otherwise we will have the same problem for large contract storages (e.g. Sweatcoin).

[robin-near]

However, I feel that answering the question "how to check if there was a newer transaction that changed given account?" leads to the same bottleneck as we have now. For example, account can be untouched in a year, and if one wants to prove its state, they need to prove that it was untouched in every block during this year.

Ahh, yeah you're right. Actually, how would one even prove that an account is untouched in a single block, without listing the whole list of accounts touched by the block? Doesn't seem very trivial - e.g. make a bloom filter and hope to get lucky that the account in question is not in the bloom filter - but it's so much less straight forward than an existence proof. Would seem even harder to do this for multiple blocks (without doing it for each block).

To limit the number of blocks we need to give non-touched proofs for we can just have checkpoints, like compute the global state root every epoch or something. (Not the greatest thing in the world)

Also I think that we need to treat each contract data key as a separate account, otherwise we will have the same problem for large contract storages (e.g. Sweatcoin).

Yeah... I think we need to seriously think about accounts like this (same with Aurora) - they break sharding. But then, splitting their keys into separate accounts would probably mean they may go into different shards, but that breaks the programming model that each account is executed synchronously. Perhaps we can have "app user accounts" which are keyed by (user account id, app account id) which is stored by the user account (consumes storage deposit from the user) but is controlled by the app account (receipts to this account invoke the app account's code). App user accounts are considered separate accounts so a receipt cannot target two such accounts (or another normal account) at once.