Improvements to the SyncState protocol

[igamigo]

SyncState

The SyncState endpoint is the main endpoint utilized by clients to get data related to blocks and the MMR. It is the main gateway for clients to synchronize in order to maintain a valid view of the chain. Up until recently, this process would work something like the following:

• The caller sends a request to the RPC server. It contains:
  • block_num: Latest block known to the caller
  • account_ids: List of account IDs that the caller is interested in
  • note_tags: List of tags that the caller is looking for
  • nullifiers: List of nullifier of notes for which the caller wants updates
• The server returns a response that contains the first block header where the note tree contains a note that matches any of the request's note_tags:
  • chain_tip: Latest block in the chain
  • block_header: Contains a specific block header
  • mmr_delta: Contains the MMR delta to update the caller's MMR, from the child of request.block_num until the response's block_header.block_num
  • accounts: Contains updated account data (ID, block number and account hash) for any account in request.accounts
  • transactions: List of transaction IDs, alongside account IDs that match any of the request's account_ids
  • notes: List of note inclusion proofs that belong to notes created by any of the request's account_ids, or notes that have tags that match any of the request's note_tags. These proofs validate against the block header's note root
  • nullifiers: List of nullifiers that match any of the request's nullifiers, alongside the block number in which they were spent
    If no block matches against the caller's request, the block header for the current chain tip is returned
• The caller can now update its own PartialMmr by instantiating the latest known peaks (corresponds to the MMR at the parent of the latest block number), adding the latest known block number, and then applying response.mmr_delta

The above can be executed in a loop until the caller reaches the chain tip.
Some details worth noting here:

• The main value of SyncState is getting MMR-related data. A user can know all details of a Note and have a valid inclusion proof against the block header's note root, but it also needs the block header itself alongside an MMR authentication path to execute a transaction that consumes it
  -request.nullifiers are prefixes of the actual identifiers that the caller is interested in (16-bit). Additionally request.note_tags are 32-bit identifiers (which in turn can contain a subset of the account ID's). This allows for matching against a larger set of identifiers which provides privacy. This means that as callers, we can receive a bunch of MMR-related data that we don't care about. For instance, we might be expecting the inclusion of a specific private note of which the note tag matches some other set of notes. Callers are then responsible of filtering the data (eg, this may require analyzing data and figuring out if our account could possibly consume these notes, etc.)
• If a new note was received for a single SyncState step, the caller can add its nullifier to the request.nullifiers field on subsequent sync requests before reaching the chain tip in order to reflect that the caller now wants to know if this note was consumed. Same applies for request.note_tags: If the caller was expecting an imported note to be recorded on-chain, its note_tag may be taken out from the request on successive requests.

SyncNotes

There is also another syncing endpoint: SyncNotes. This endpoint was introduced to support scenarios related to sharing notes between clients. For example, a case where $Client A$ wants to share a private note (NoteFile::NoteDetails) to $Client B$ can be divided in two different scenarios:

• $Client B$'s latest known block number is lower than the NoteFile::NoteDetails's expected block number. This client can now add the note's tag to the list of tags and SyncState will eventually yield this note's inclusion details alongside MMR data
• $Client B$'s latest known block number is higher than the block number where the note was included. SyncState does not have a way to support this. The client could run GetNotesById, but this leaks data and would also lack the block header with the MMR inclusion proof (for which GetBlockHeaderByNumber could be used).

In the second case, we can use SyncNotes to request specific note tags added from a starting block, and receive a note inclusion proof with the related MMR/block data.

CheckNullifiersByPrefix

This is the last related RPC endpoint. This one essentially receives a list of nullifier prefixes, and returns a list of consumed nullifiers.
Initially this was also introduced to support scenarios related to importing (similar to the above): If the importing user's client is behind relative the note's inclusion block, the nullifier will naturally be received on SyncState. However, if the client has moved past the note's inclusion block, the nullifier might have already been included in the chain and the user would have no way of knowing this based on SyncState alone.

Recent changes

Recently, there were some changes to enable streaming SyncState responses (#174). One consequence of streaming responses from the node is that the caller cannot modify the request.nullifiers between sync state steps anymore, because a single request yields multiple streamed/pushed responses.
To account for this, it was decided that we could remove nullifiers from SyncState requests and responses. The client could then stream sync state responses, and once this process is done, they can call CheckNullifiersByPrefix to request all nullifiers at once (#707 and #713) starting from request.block_num.

The probability of a 16-bit prefix matching a random nullifier is 1 / 2^16. If you have N blocks, M requested prefixes, and K nullifiers per block, the expected number of matches is N * M * K / 2^16.

Assuming 32 bytes per nullifiers: A lower bound of 500 nullifiers per block matching against 10 prefixes yields roughly 0.076 matches per block. Syncing over a day of blocks (~3 blocks per second, 28,880 blocks per day), this becomes ~2,200 matches or ~70 KB.
A higher bound (1,000 nullifiers per block with 50 prefixes, 10x the previous scenario) gives about ~22,000 matches for a day of blocks, or ~704 KB. An average scenario between these two would be around around ~9,900 matches/day, so ~316 KB.

There might be something I'm missing in terms of the math (and maybe the estimates are not realistic at all), but it's something we want to keep in mind when comparing the new approach to the old one:

• In the new approach the data transmission is split up into two requests: one streamed SyncState request and one CheckNullifiersByPrefix request. As analyzed above, these could be within the 0.5-1 MB range regularly, which does not seem desirable.
• The old approach, on the other hand, solves everything with multiple SyncState responses. Responses are smaller because there are as many requests as there are matching blocks between request.block_num and the chain tip (in turn, these are based exclusively on whether request.note_tags match or any of the request.account_ids created a note)

The implications here affect mostly the node in the sense that the database is now required to handle two distinct data retrieval patterns. With the new approach, the streaming SyncState responses remain comparatively small, but the CheckNullifiersByPrefix request can return a large, aggregated set of data if many nullifiers match the requested prefixes (and if we are requesting data starting from an early block number). This shift may lead to increased I/O, locked DB, and processing overhead on the node's database. As a result, we might want to analyze additional indexing, caching, or query optimizations (both at the RPC and DB level) to ensure that the node can efficiently serve this data without it becoming abottleneck.

So overall, it might not be entirely clear whether the recent changes make sense in terms of optimizing the whole flow. Some alternatives that we could explore and that were briefly discussed before:

• Trying to leverage Bloom filters
• Splitting up endpoints further instead of working around SyncState, maybe having one for accounts, one for notes, one for nullifiers. They could probably work independently and the client would have to be responsible of bookkeeping to make sure data is coherent. Each should probably have from-to parameters.
• Could nullifier prefixes be made larger in order to match against a smaller set?
• Paginate responses somehow. For instance, we could return data up to a maximum amount of blocks

There are tradeoffs to each of these and so, while designs should be discussed we also probably want to be able to measure the impact of any changes in the design overall

[Mirko-von-Leipzig]

Caution

Disclaimer: my current (likely incorrect) understanding of the issue.

---

Does the following statement cover the requirements:

Enable syncing some subset of chain state to a specific block number.

and this our current design dilemma

How to perform this efficiently for recent blocks without forcing sync to step through the entire chain history. Which is very inefficient for small accounts/state aka when to use delta's versus an entire state at once.

Secondary issue is large public accounts versus small ones. This seems to imply we need streaming regardless of how we solve the previous issue.

Thirdly, how can the client update their query as they learn of new data without missing things.

---

I'm hopeful we can carve out a sensible design by adding some restrictions. e.g. you can't target ancient block heights, only the most recent N blocks.

[Mirko-von-Leipzig]

Why are only note and nullifier queries considered for privacy, but not accounts and transactions that target them?

[bobbinth]

Account state syncing

This is not directly related to the current sync endpoints, but if we do decide to split the state sync into 3 different endpoints, we'll need to sync account states separately. But even without this, we need to figure out how to handle account syncing, especially when account state could be large.

We currently have 3 endpoints related to account syncing:

• GetAccountDetails - which returns a full Account object for public accounts. This is not really something we can support as account states get bigger.
• GetAccountProofs - which returns a partial information about the account. This includes account header, account storage, account code, and account witness (i.e., an inclusion proof against the chain MMR). It can also include a select set of storage map entries, if requested by the user.
• GetAccountStateDelta - as far as I know, this endpoint is currently not used. It is supposed to return account state delta between two block numbers, but I'm actually unsure whether it fully works.

Overall, I think we should get rid of GetAccountDetails and GetAccountStateDelta endpoints, and replace them with a modified GetAccountProofs endpoint (which we should rename into GetAccountDetails) and a couple other more specialized endpoint.

The new GetAccountDetails endpoint

As mentioned above, this could be similar to our current GetAccountProofs endpoint, but with the following modifications:

• This endpoint would be per-account (i.e., we'd be requesting data for a single account at a time).
• For public accounts, it would always return account header, storage header, and account code (if different from the specified code commitment).
• It would be "smarter" in how it returns storage map data. Specifically, if a storage map contains a small number of entries, it would just send all the entries rather than storage map proofs for each entry. What this small number is, would need to be estimated, but my guess is that it'll be somewhere around a couple dozen or maybe even more.

One thing we should think through is how to impose limits that make sure the responses for this request don't get too big (e.g., say under 100KB). Assuming account code will be limited to at most 64KB, the only part of the response that could push us over it is the requested key-value entries. Maybe we could limit that part of the response to something like 32KB.

Note that this endpoint would still return the latest account state info (i.e., from the latest committed block).

Syncing storage maps

One of the things missing from the above endpoint is the ability to sync storage maps, especially if an account has large storage maps that don't fit into the response size constraints. For this, we could provide a separate endpoint called SyncStorageMaps. The request for this endpoint could look something like this:

message SyncStorageMapsRequest {
    // block number to start syncing from
    fixed32 block_num = 1;
    
    // Account for which we want to sync storage maps
    AccountId account_id = 2;

    // Indexes of storage slots for which to return the data
    repeated uint32 storage_slots = 3;
}

The response to this request will contain update tuples for the requested storage slots:

message SyncStorageMapsResponse {
    repeated StorageMapUpdate updates = 1;
}

message StorageMapUpdate {
    uint32 slot_idx = 1;
    Digest key = 2;
    Digest value = 3;

    // Block number at which the above key was set to the above value.
    fixed32 block_num = 4;
}

The returned updates would always contain the latest value for a given key. So, for example, if we have the following sequence of map updates:

• Block 1: insert(key = A, value = X)
• Block 2: insert(key = B, value = Y)
• Block 3: insert(key = A, value = Z)

The returned updates would be:

• (key = B, value = Y, block_num = 2)
• (key = A, value = Z, block_num = 3)

The endpoint needs to guarantee that if it returns an update for block $x$, then the response all updates for block $x$. The naive way to do that is to send updates for a single block, but that's not very efficient and we should be able to come up with something better.

The main reason for this guarantee is so that the user would be able to make a subsequent request with a block_num set to that greatest block_num from the previous response +1 and get the next set of updates.

With this setup, once the user syncs to the chain tip, they are guaranteed to have the latest state of the storage maps, and after this point, they can always apply the updates incrementally to get the sate of the map at a given block height. This is very nice because we can use the same mechanism to achieve several goals (assuming, of course, I didn't make a logical error somewhere):

• We can incrementally sync very large storage maps.
• The client can determine the commitment to a storage map at a given block height.
• The node does not need to keep track of historical storage map data (besides adding block_num to every storage map entry).

The main downside of this approach (as far as I can see) is that if a value for a given key set to an EMPTY_VALUE, we still need to keep it in the database. But I'm treating this as a necessary evil at this point, and maybe later on we can find out how to deal with this.

Syncing account vault

Syncing the vault could work very similarly to the storage map syncing. The main difference here is that for assets we don't get keys and values automatically, and so we'll need to derive the manually (this is straight-forward to do). So, the returned account vault updates could look like:

message AccountVaultUpdate {
    Digest vault_key = 1;
    Digest asset = 2;

    // Block number at which the above vault key had the specified asset stored under it.
    fixed32 block_num = 3;
}

This works well for fungible assets as we just update the state of the asset under the same key as the balance changes, but for non-fungible assets we'll run into the same issue as I described above with clearing storage slots. Specifically, If a non-fungible asset is removed form the vault, we'll need to keep the (vault_key=A, asset=EMPTY) entry in the DB forever. But again, maybe there is some solution to this we can come up with later.

---

Would appreciate review of the above logic. If there are no major holes, we can convert this to an issue.

[drahnr]

CC @drahnr work on this this week

[Mirko-von-Leipzig]

@bobbinth replying out-of-thread to split the topics up a bit.

EMTPY_VALUE musings (not important now)

The main downside of this approach (as far as I can see) is that if a value for a given key set to an EMPTY_VALUE, we still need to keep it in the database. But I'm treating this as a necessary evil at this point, and maybe later on we can find out how to deal with this.

I don't see a way around this while keeping delta/incremental semantics. One could set an upper time bound using epochs similarly to the nullifiers. Though one can probably argue that by the time that rolls around we should have cold storage for deadish accounts which would be more impactful than clearing a couple of rows.

The storage impact of something like this is hard to estimate since it will depend on the fee economics on clearing data out. Usually the main impact is on storage proofs and not on flat storage as we have here, so I don't think it should be a problem for a while.

[Mirko-von-Leipzig]

Syncing maps

I think the idea sounds great.

We could probably elide the block number from StorageMapUpdate and return the latest block number since that's effectively what the caller would be doing. Or is there additional use case from knowing the specific block at the caller's side?

message SyncStorageMapsResponse {
    repeated StorageMapUpdate updates = 1;
    fixed32 chain_tip = 2;
}

message StorageMapUpdate {
    uint32 slot_idx = 1;
    Digest key = 2;
    Digest value = 3;
}

[bobbinth]

I did consider that but I thought the deletion logic wouldn't scale well since it needs to check every entry.

I wonder if we could make the delete more efficient at the expense of insert. For example, we could add something like is_last_update to every map update to make it look something like:

(account_id, slot_index, key, value, block_num, is_last_update)

Then, on insert we'd be basically doing two things:

• Setting is_last_update to NULL for any record with the same (account_id, slot_idx, key) combination.
• Inserting a new record with is_last_update = 1 (or w/e value).

Then, in the delete query we could just use WHERE is_last_update = NULL.

[Mirko-von-Leipzig]

Then, in the delete query we could just use WHERE is_last_update = NULL.

I think this doesn't work because we need it to only delete once the new update reaches N blocks ago. Or maybe more visually:

                        Set of blocks we keep
                        and their perceived values

| ancient history ..... |  0  |  1  | ... |  N  |
|      x                |  x  |  x  |  x  |  x  |     Single old entry with value x
|      x                |  x  |  x  |  x  |  y  |     Tick, new value inserted, must keep both
|      x                |  x  |  x  |  y  |  y  |     Tick, still both required
|      x                |  x  |  y  |  y  |  y  |     Tick, still both required
|                       |  y  |  y  |  y  |  y  |     Tick, can delete x now

How about this. We keep the main table with only the latest values. Whenever we insert an item, we move the replaced value into a 2ndary table and importantly mark it with the current block number (not when it was created). This 2ndary table can be cleaned rather easily then with DELETE WHERE block_number < chain_tip-N. It will also be size bound to only the last N block's of deltas. This also allows for trivial EMPTY_VALUE tracking - if the insert did not replace anything then move the empty value into the 2ndary table.

In theory we could also find a way to make this all a single table, but I'm not entirely sure that's a good idea. The inserts statement would be fairly complex imo, and the deletes would have a much much larger table to crawl through (the entire state vs the last N blocks).

[bobbinth]

I think this doesn't work because we need it to only delete once the new update reaches N blocks ago.

Right, I should have been more precise - the condition for the delete query would be:

WHERE is_last_update = NULL AND block_num < chain_tip-N

Or did I miss something here as well?

How about this. We keep the main table with only the latest values. Whenever we insert an item, we move the replaced value into a 2ndary table and importantly mark it with the current block number (not when it was created). This 2ndary table can be cleaned rather easily then with DELETE WHERE block_number < chain_tip-N. It will also be size bound to only the last N block's of deltas. This also allows for trivial EMPTY_VALUE tracking - if the insert did not replace anything then move the empty value into the 2ndary table.

Conceptually, I like it - though I still need to wrap my head around how querying these tables would work. It seems to me that to build a response we'd need to look into both tables, right? And also, to do pagination correctly, wouldn't we need to keep the mutation block number as well (perhaps in a separate field)?

[Mirko-von-Leipzig]

It seems to me that to build a response we'd need to look into both tables, right?

Correct, this can be done with one of

• joining the tables
• coalescing the values
• move the logic to rust side (but this is not great if we do postgres)

And also, to do pagination correctly, wouldn't we need to keep the mutation block number as well (perhaps in a separate field)?

Hmm. Probably yes. Although maybe a join and choosing the correct thing(s) to order by is good enough.

I think we would have to write out the queries fully for every situation, and the indices before we would really know which option is better. For the short term maybe we go with your suggestion and keep an eye on block inserts and RPC query times? If performance becomes an issue we revisit this.

[Mirko-von-Leipzig]

In my head it makes sense that splitting out the smaller, more mutable set would perform better. But databases are complex and indices already kinda sort of act like a split out table so maybe its just silly to do it manually :)

[bobbinth]

Once we have #1185 and #1186 implemented, I think we'll be in a good position to finish this refactoring. Specifically, we'll have the following endpoints to help us sync the state of the client:

• CheckNullifiersByPrefix - for syncing nullifier info (maybe we should rename this into SyncNullifiers).
• SyncNotes - for syncing notes (by note tag).
• SyncState - for syncing notes (by tag and sender), account updates, transactions, and chain MMR data.
• GetAccountProof, SyncAccountVault, and SyncStorageMaps for syncing details of public accounts.

Out of these SyncState is probably doing too much work and it is difficult to estimate the size of the response it may return (in theory, the response size could be very large). I think we could simplify this. As mentioned above, it does 4 things:

1. It retrieves notes by tag and by sender. The first part already overlaps with SyncNotes.
2. It allows the client to update its partial MMR.
3. It retrieves info about whether an account we are interested in has been updated.
4. It retrieves info about transactions executed against the specified accounts.

I think there are two things we can change about this:

• Move responsibility for MMR data into SyncNotes (maybe as optionally-returned data).
• Replace SyncState with a new SyncTransactions endpoint.

The new SyncTransactions endpoint would take a list of account IDs as input, and would return a list of transaction headers. The request message for this endpoint could look like so:

message SyncTransactionsRequest {
    // Block number from which to start sync (i.e., transactions before this block would not be returned)
    fixed32 block_from = 1;

    // A list of accounts against which the requested transactions have been executed.
    repeated AccountId account_ids = 2;
}

And the response message could look like so:

message SyncTransactionsResponse {
    // The block number of the last transaction included in this response.
    fixed32 block_num = 1;

    // Chain tip at the moment of the request.
    fixed32 chain_tip = 2;

    // Headers of the transactions that were executed against the specified accounts
    repeated TransactionHeader = 3;
}

// This message differs slightly from the `TransactionHeader` struct in miden-base in that it includes
// block_num and more data about output notes - but maybe that's fine.
message TranactionHeader {
    // ID of the account against which the transaction was executed
    AccountId accountId = 1;

    // Block number at which the transaction was included into the chain.
    fixed32 block_num = 2;

    // Commitment to the account state before the transaction was executed.
    Digest initial_state_commitment = 3;

    // Commitment to the account state after the transaction was executed.
    Digest final_state_commitment = 4;
  
    // A list of nullifiers for notes consumed by the transaction.
    repeated Nullifier input_notes = 5;

    // Info about notes created in the transaction.
    repeated NoteSyncRecord output_notes = 6;
}

This should cover all the data reaming from the removal of SyncState. Specifically:

1. This would give a all the same transaction info.
2. This info includes all info about account state updates (i.e., the info we currently have in AccountSummary).
3. This info would also contain all note data by sender (which is missing from the note SyncNotes endpoint).

cc @igamigo in case I'm missing something.

[igamigo]

I think this is very equivalent to what we have now, with some minor differences, like the fact that you would not get MMR data for output notes created by any of the senders specified in SyncTransactionsRequest.account_ids. I don't think this is bad, though (and may even be better). Tagging @tomyrd to see if he has any opinions on this as well. Overall, we should be able to replace the internals of the sync process with these new endpoints.

[tomyrd]

Yes, the sync process internals are already separated into very similar sections (account_sync, note_sync, etc.) so it shouldn't be much of a problem.

like the fact that you would not get MMR data for output notes created by any of the senders specified in SyncTransactionsRequest.account_ids

In the implementation mentioned above, I would think this information will come via NoteSync if we add the relevant tags to the request.

[bobbinth]

In the implementation mentioned above, I would think this information will come via NoteSync if we add the relevant tags to the request.

This could work, but then the note data returned in the above description of the TransactionSync would be largely redundant. This may also result in querying for more tags than we actually need to.

Maybe an alternative approach would be to include some MMR-specific data in the TransactionSync response? e.g., maybe MMR paths for the returned nodes would be sufficient?

[igamigo]

Returning authentication paths could be sufficient. We'd have to SyncNotes first to update the MMR and then we could start tracking previous blocks given by SyncTransactions.

I wonder however if we want to always get MMR data for notes that a local account created though. As long as we get a NoteInclusionProof, then most of the usecases are unlocked (ie you can easily verify that the note was added to a block and export it, etc.). If the user still wants to consume the note with the same account, we should be able to get the block's authentication path separately with the GetBlockHeaderByNumber call.

[bobbinth]

Yes, agreed - I think we may not need this data during sync process and if we do need later on, we can always get it as you've suggested.