Protocol: Light-client friendly storage tracking

[gavofyork]

Use-cases of a node from an external application's point of view fall into two categories: inspection and notification. Light clients, which sync using only the chain of headers and do not generally validate extrinsic data within the block, must have special considerations to ensure they are able to provide both use-cases efficiently.

Inspection (of storage or the chain) is pretty easily provided following the design of Ethereum and Bitcoin before it: full nodes (or even light-nodes that already have the requisite information) may provide proofs on the value of a particular key in storage using only the storage's Merkle-trie root as a priori assumption (which is provided for through a header-sync).

However, notification is more difficult to provide as a low-trust service since proof that a given block does not have an extrinsic which causes a state-change of interest is not efficiently derivable from the storage's Merkle-trie roots. In Ethereum this was addressed through collating a large (2KB) Bloom filter in each block and embedding it in the header. This bloated the header and was ultimately fruitless as the usage of Ethereum ballooned and the Bloom became saturated.

Instead, I propose three mechanisms for addressing state-change notification on Substrate, two of which (the latter two) it makes sense to combine:

• Track last-modification-time entry in storage;
• Provide a Merkle trie root of all modified storage entries, ordered and indexed;
• Provide a hierarchy of Merkle trie roots of all modified storage entries in a series of blocks, ordered and indexed.

Track last-modification-time entry in storage

At present, the storage database is a set of key-value pairs. These pairs are arranged into a Merkle trie and baked into a single "root" hash. This proposal would simply prefix the value with the block number at which the value was last modified.

Synced light-clients could easily query proof-servers on when a storage item of interest last changed. Proof-servers could prove the most recent block (compared to either the head or some block before the head that the light-client knows about) at which the change happened. Light-clients could request a change-log between some begin and end block of one or more storage keys and the proof-server would return a chain of these proofs as irrefutable evidence of all blocks in which one or a number of storage entries changed.

There is one issue with this approach: deleted storage entries would still have a footprint in the database, necessary for recording the block at which it was "last modified" (i.e. deleted) - without this light-clients would lose their ability to query for its historical change log. The (slightly inelegant) workaround to this would be to have special "garbage-collection" blocks in which these zombie entries would be purged from the database (and thus the trie). Light-clients would ensure that they always made at least one change-log request within each of these periods.

This would increase every storage entry in the database by around 32-bytes (for the block number). It wouldn't have much of an effect on the disk i/o and the header size would remain the same. However, for storage with a lot of changes, building and executing these garbage-collection blocks may become a serious efficiently issue.

Ordered, indexed, Merklised per-block change-trie

This proposal creates a new structure that encodes all changes, not dissimilar in spirit to the Bloom filter. This structure takes the form of a trie root build as the mapping of indices to storage keys. The indices are sequential and ordered by storage key. Like the Bloom filter this gives a cryptographic digest of what has changed in the block. Unlike the Bloom filter, a proof that any given key has not changed is not only possible, but also compact.

To provide the proof that a given key didn't change, the proof-server provides the two (Index, Key) entries on either side of the key to be proven was not changed. (A null sentinel index of (ChangedKeyCount, null) would denote the upper end in order to provide a proof should the queried key be greater than the upper limit of modified keys.)

In principle, this trie could also contain a second mapping of (Key, [ ExtrinsicIndex_1, ExtrinsicIndex_2, ... ]) to denote which extrinsic data in the block actually caused the key to be changed.

Extending over ranges

While this allows for efficient proofs that one or more keys were not changed (or, if they were changed, can give the specific extrinsics which caused the change) in any given block, use-cases typically want to ascertain this for a range of blocks.

This structure, however, lends itself to a hierarchical approach: event N blocks, the trie would contain an additional entry ('digest', DigestChangeTrieRoot). DigestChangeTrieRoot would be the root of a similar trie structure, except that it would contain the accumulated modified accounts of the previous N blocks. Rather than containing the series of ExtrinsicIndexs that caused the change of any given key, it would contain the block numbers that caused the change, allowing for the efficient identification of the exact extrinsic through a logarithmic number of queries/proofs.

This structure can be nested and recursed arbitrarily; N might reasonably be either 16, 32 or 256 and be recursed 4, 3, or 2 times accordingly to get a maximum block range that the top-level trie covered to be 32768 or 65536.

Light clients would query proof-servers in batches, hopping over the blocks by the top-level range at a time. Proof-servers would either return with proofs that nothing of interest changed or would return with the sub-ranges where something did change (along with the key that changed there). Light-client would re-query within that subrange, drilling down until they determined the exact set of extrinsics. In principle, this entire query could be prepared on the server-side and a compiled proof of everything built and sent back to the light-client with minimal bandwidth/latency used.

[rphmeier]

This structure takes the form of a trie root build as the mapping of indices to storage keys. The indices are sequential and ordered by storage key

I don't understand this. Is it a mapping of storage_key => ?? or i => storage_key if storage_key was the ith change in the block? In that case, how can it be ordered by storage key? For succinct proofs that something hasn't changed we should just be able to get a proof of non-inclusion if the mapping is keyed by storage key.

Given that I'm having trouble parsing the above, I might be completely off-base here, but it sounds like

A null sentinel index of (ChangedKeyCount, null)

is establishing an upper bound on the number of changes we track per block.
That would defeat the purpose since it would allow plausible omission of data to light clients.

If the changes trie-root mapped key => last_changed where last_changed is the block number it was changed at before, we could request proof of all changes up to some point in history. All of this still relies on the assumption that clients will mostly want to read specific storage entries as opposed to querying functions.

w.r.t. the footprint of deleted entries, that is also true. Given that our security model is weakly subjective we should make the cleanup period fairly long and in accordance with the withdrawal period of a few months or so. I don't think this poses a DoS vector any more so than transfers of 1 stake-unit to tons of unreachable accounts would, although we should also consider garbage collection and rent in that case. Then the question becomes "what's the minimum fee someone has to pay to impose a storage burden of 1 cleanup period"?

[gavofyork]

So suppose that there's a block with a single extrinsic sender = Alice, call = transfer(Bob, 69). There are three changes to storage: twox_128(':staking:balance:<Alice>'), twox_128(':staking:balance:<Bob>') and twox_128(':sys:index:<Alice>'). Let these three expressions evaluate to 0x1111..., 0x2222... and 0x3333... respectively.

Then we build a trie with four key-value pairs:

• (0, 0x1111...)
• (1, 0x2222...)
• (2, 0x3333...)
• (3, 0x)

The keys are just formed by ordering the values and running up from 0. There's a final value to denote the end. If a light-client wished to have proof that Charlie's balance didn't change, they would determine that entry in storage twox_128(':staking:balance:<Charlie>'), (which, for argument's sake evaluates to 0x1234...) then they'd ask a proof-server for a proof of the existence or non-existence of that node in the trie whose root they know via header-sync. An existence proof is trivial. A non-existence proof is also simple: the proof-server would reply with the witness statements for the two entries either side of that value ((0, 0x1111...), (1, 0x2222...)). Since they have consecutive index keys (i.e. 0 and 1), and since the associated storage keys sandwich the storage key we're interested in, and also since we know all index keys are bestowed sequentially on the ordered storage keys, then we can conclude that no storage entry was changed whose key is > 0x1111... and < 0x2222... in this block, including 0x1234... which we're interested in.

[rphmeier]

I see, that makes sense to me now.

I'm not sure that I would necessarily call what's described a compact proof of non-existence. Given an ordinary merkle mapping from A => B, you can prove non-existence of an element a with a single merkle branch (which proves that the lookup terminates before reaching a value). These proofs require two, although they will often share a long common prefix.

The main thing to consider is the complexity of producing such a proof. Doing a binary search from 0 to ChangedKeyCount and finding the ChangedKeyCount will take (log(n))^2 + log(n) db accesses. Evaluating it is only log(n) since we can specify the indices to look at. Creation of the trie is even more expensive, since we need to accumulate all the keys and then sort them before making the trie. This all might end up pretty costly when lots of keys have been changed. With a regular merkle trie, proofs of existence and non-existence will take only log(n) time to create and evaluate. The sorting proof approach does allow for fairly compact proofs of non-alteration for arbitrarily large ranges of keys, but it's difficult to take advantage of that with hashed storage keys.

It's not light-client friendly to require fetching them every block while tracking changes. I'd suggest that the ∆-trie map idx => (key, last_changed) or simply key => last_changed so a light-client starting with a merkle proof of a storage value can get existence proofs only when something changes and be confident that nothing was omitted. This is a sore point in light clients for other blockchains. We don't even have to synchronize the whole header chain if we are subscribed to clients who will push us those which contain relevant changes and we are aware of a validator set persisting up to some point in the future. Then we only need relevant headers and corresponding ∆-trie proofs pushed to us.

If the last_changed for each key is stored in the state trie, extending over hierarchical ranges is only necessary to get over a range if we assume old states to be unavailable, which is plausible. If historical state is available, we can just take hops backwards from the current last_changed to the point in history we are interested in.

[gavofyork]

That idea is covered under the first proposal "Track last-modification-time entry in storage". As mentioned above, keys that were deleted pose a problem. Indeed there is no need for the ordered/indexed Merkle tree for a compact proof of non-existence, but the point about ranges and specification of which items in the range are of interest still stands.

[arkpar]

Could this be solved on the higher level instead? E.g. store a second nonce value with the account which gets incremented every time the balance is changed. Do we really need tracking for all key/values?

[gavofyork]

In general, yes, since much of substrate's logic will depend on being able to track arbitrary storage items, not simply the specific account items.

[NikVolf]

You might also look at SMT:
https://eprint.iacr.org/2016/683.pdf

[gavofyork]

@rphmeier any more to say on this matter? Given the issue with finding non-existence when using "Track last-modification-time entry in storage" strategy, my preference is now firmly with the "Ordered, indexed, Merklised per-block change-trie" proposal, albeit taking into account your point that ordering isn't required for non-existence proofs.

[rphmeier]

@gavofyork what is the ordering/indexing useful for then? in a state with hashed keys the odds of finding a useful yet compact run of keys is tiny. The implementation and computational complexity of building the hierarchical modification tries will require a lot of overhead on full nodes.

Tracking last-modification time makes the most sense to me, since the approach of clearing zombie keys is actually pretty easy. We can maintain a separate set of del:* -> # keys for those which are deleted (# = Number, * = some other key), and wipe those every N blocks (the purpose of moving them to a common-prefixed set is to make deletion fast). We just have to check for a del:* entry when creating a value in a new slot.

[rphmeier]

Quoting from paritytech/polkadot#425 (comment)

In the current model, we only need to test existence of the key in the Merkle tree; if it's there we don't actually need to load the value to know that the proposal "exists". In this new model that's not enough since it might be there but in a zombie "deleted" state - we'll have to load the value (at least the first 4 bytes) to check whether it really is in the trie. That may be problematic to do efficiently without incurring the full cost of the 700KB load.

By separating the deletion tracker we only have to probe for existence as well. Although this might be a moot point, because in practice in substrate, querying existence of a key in the trie actually incurs a load of the value as well, as the postfix of the key is stored within the leaf node itself, along with the value.

[gavofyork]

i really dislike zombie keys and latent cleanups. i think there's enough information on why "Ordered, indexed, Merklised per-block change-trie" extended over ranges is useful and i really don't want to rehash the same points here. i suggest we take this offline and come to consensus.

[rphmeier]

Extending over hierarchical ranges of blocks is useful, but there is no information in this discussion about a proposed use-case of a range-modification proof in a state which makes use of hashed keys, or a fast/storage-efficient algorithm for computing the hierarchical change-set.

[svyatonik]

Merged in #628