/account.get_exitable_utxos should not call OMG.DB.utxos() directly

[unnawut]

Relates to #1274 (in the sense that fixing this issue, the other issue regarding utxos retrieval is still remaining to be fixed)

RE: #1256 (comment) OMG.DB.utxos() should not be used directly for serving utxos listing due to performance issues

defmodule OMG.Watcher.API.Account do
  # ...
  def get_exitable_utxos(address) do
    # OMG.DB.utxos() takes a while.
    {:ok, utxos} = OMG.DB.utxos()

    OMG.State.Core.standard_exitable_utxos(utxos, address)
  end
end

[pnowosie]

IMHO there is no link between this #1257 and #1274, info’s get_utxos and security’s get_exitable_utxo are different endpoints

[unnawut]

IMHO there is no link between #1257 and this #1274, info’s get_utxos and security’s get_exitable_utxo are different endpoints

Ah sorry I didn't put why I thought they're related. Yup agree that they're different endpoints.

The only relation is that the discussions that took place were on utxos retrieval but there are actually 2 separate places to fix. So adding a relation here so we don't mistake fixing only one issue being "the utxos retrieval issue is solved"

I've added this reasoning to my original reference above. Thanks!

[pnowosie]

Slack discussion leads to a few points already:

• previous purpose of the endpoint was mass-exit scenarios, so performance was not an issue. The limit of the UTXO set, that tests was performed was 10M utxos.
• for larger sets this endpoint might not function at all (http request timeout)
• @boolafish mentioned the Safe exit estimations

Agreed that @InoMurko@pnowosie will follow up to the issue.

[InoMurko]

As discussed in slack, I will not follow up the issue. Papa has been assigned to the issue and he will follow up.

[boolafish]

Don’t forgot previous awesome work from @unnawut .
#1660

The new column family thing looks pretty good to shard by address to increase performance

[pnowosie]

The new column family thing looks pretty good to shard by address

I don't think we should shard by address, it's there to separate logically different thing the way we already use key prefixes.

To summarize:
I'm keen to postpone solution design after we'll receive input from product (proposed by @unnawut) . The points for consideration are:

• remove the endpoint, and make utxo owner responsible of tracking their utxo positions,
• make a more realistic estimate to cardinality of UTXO set. Is it 10M or 2M?
• predefined addresses Watcher would closely watch (which limits endpoint functionality to only these addresses)

[pnowosie]

I investigated endpoint optimization options, here is what I considered.

Assumptions:

• UTXO set belonging to a particular address is small
• Whole UTXO set cardinality is below 10M

Option: Partitioning addresses set

The idea here is to divide address set into N partitions identifiable by partition key derived from the address. Under each partition utxo positions belonging to the addresses of the partition will be stored.
In the terms of key-value store used in Security Watcher, we will store N items (partitions), where key is partition key and a value is a list of utxo positions.

Storage considerations

Limits of the RocksDB

• RocksDB puts a constrain on single value size of 3 GB.
• Max utxo position byte size is 12B (contract structure)

We can store ~250M of utxo positions in the single RocksDB value, so storage engine is not limiting us.

Storage space estimation

Assuming 64-bit utxo position (enough to encode a year of blocks), 65k partitions each of 250 utxo positions adds less than 200MB additional storage space. It corresponds to 60% overestimated UTXO set (16.38M of utxos), the average space consumption should be significantly lower.

List of 250 64-bit utxo position serialized to binary (:erlang.term_to_binary) can be stored in ~2.7kB.

Performance considerations

Here I'm presenting output from a test I've written to measure times of fetching utxo set

Performed tests

Start test with 499_999 utxos and 33_333 addresses.
 ...
Chosen partition of pkey=462 with 11 addresses.
Partition list written in 295μs and read back in 43μs.
Fetched all 168 utxos for addresses group in 2ms.
Filtering list of DB fetched utxos took 24μs.

Start test with 993_731 utxos and 66_248 addresses.
 ...
Chosen partition of pkey=3590 with 15 addresses.
Partition list written in 140μs and read back in 55μs.
Fetched all 224 utxos for addresses group in 5ms.
Filtering list of DB fetched utxos took 29μs.

Start test with 1_000_000 utxos and 66_666 addresses.
 ...
Chosen partition of pkey=462 with 14 addresses.
Partition list written in 293μs and read back in 30μs.
Fetched all 210 utxos for addresses group in 4ms.
Filtering list of DB fetched utxos took 23μs.

Start test with 1_111_111 utxos and 74_074 addresses.
 ...
Chosen partition of pkey=462 with 9 addresses.
Partition list written in 126μs and read back in 35μs.
Fetched all 140 utxos for addresses group in 4ms.
Filtering list of DB fetched utxos took 11μs.

Start test with 1_995_995 utxos and 133_066 addresses.
 ...
Chosen partition of pkey=12995 with 13 addresses.
Partition list written in 133μs and read back in 36μs.
Fetched all 196 utxos for addresses group in 5ms.
Filtering list of DB fetched utxos took 9μs.

Start test with 4_444_479 utxos and 296_298 addresses.
 ...
Chosen partition of pkey=12995 with 10 addresses.
Partition list written in 137μs and read back in 24μs.
Fetched all 98 utxos for addresses group in 9ms.
Filtering list of DB fetched utxos took 6μs.

Start test with 4_999_975 utxos and 333_331 addresses.
 ...
Chosen partition of pkey=462 with 11 addresses.
Partition list written in 288μs and read back in 29μs.
Fetched all 112 utxos for addresses group in 4ms.
Filtering list of DB fetched utxos took 8μs.

Start test with 10_099_555 utxos and 673_303 addresses.
 ...
Chosen partition of pkey=48585 with 10 addresses.
Partition list written in 158μs and read back in 62μs.
Fetched all 196 utxos for addresses group in 4ms.
Filtering list of DB fetched utxos took 24μs.

Test description
For a given utxos count it picks number of addresses that each owns ~15 utxos. Then generates utxo set and propagates it to the DB. Number of partitions is chosen at ~10% of addresses count.
Then partition is picked with about average addresses distribution uniq_addr / partition_count
For the chosen partition initial UTXO set is filtered to get all utxo positions belonging to the addresses in the partition.
Then the list of position is written to DB under the partition key and retrieved back to measure a time.
Finally all utxos are retrieved from the UTXO set with utxo position from the above list.
Utxos are fitered to to select only ones belonging to particular address from the partition.

Outcomes
Because the partition count is chosen that utxo position list for each partition is relatively small 150-250 utxos. The total number of UTXO set does not affect the performance of filtering utxos by the address, only partition size matters.

• Write and read single partition data is below 0.3ms worst and 0.2ms avg
• Fetching all utxos for the partition is 5ms avg
• Filtering utxos for particular address is neglible

Partitioning strategy

Because addresses are generated at random we can assume uniform distribution of the addresses in the address space. Therefore calculating partition key from the formula:
partition_key := k_bits of address modulo N, where N is desired partition count
would lead to uniform distribution of the addresses through the partitions.

For simplicity we can choose partition_key := first_2_bytes of address to have a 65 536 partitions at maximum.

I considered also consistent hashing for a partition strategy but it gain us nothing. Even if we would like to adjust partition count it will lead to change of each partition. So I think simpler strategies are more suitable here.

Solution draft

First of all please mind this is just supportive endpoint of security Watcher which aims to remind the address owner the utxo positions (s)he owns. Awared owner can skip this step and start exit utxos by the position right away. This endpoint was never meant to be be used for transacting.

The following draft is trying to answer performance issues while support the entire address space. Other options were mentioned in other options

Lets assume we have a function:

  partition_key(address :: address_t)  :: positive_integer

which assigns each address in the system to one of N partitions.

Next, lets compute a mapping address => [ utxo_position ] which can be derived from the UTXO set (here is an inspiration)

and then compute the mapping ownership_list :: partition_key => [ utxo_position ]

Additional data in RocksDB

For each of N partition store in RocksDB N ☝️ ownership lists , where key is a partition_key (integer) and a value is binary form of elixir list of utxo's encoded positions (list of integers).

How to filter utxos owned by address

This is the functionality behind account.get_exitable_utxos endpoint.

Given

• the address,

Result

• the Utxo position list owned by the address

Algorithm

• compute partition key using partition_key function,
• then fetch the ownership list by the partition key from the RocksDB,
• then fetch the utxos from RocksDB identifiable by the utxo positions from the ownership list using `OMG.DB.batch_get,
• finally filter the utxo list by the address to get the resulting utxos.

How to keep ownership lists up-to-date

We need to update each ownership list with newly created utxos just after new block is consumed by a Watcher. DB updates with newly created utxo as well as spend utxo positions are keep up-to-date in State.Core.utxo_db_updates.

If we'd like to update partitions while applying the block, we are missing information about spent utxo owner (which is available only when transaction is executed on state). However keeping spent utxo positions in the partition is not much issue because we need then retrieve utxo from the state to check the owner, so it won't introduce more burden than consuming additional space. What's more usually one of the transaction outputs will contain the owner of the spent utxo, so most of the cases we will manage to clear spent positions.

[InoMurko]

Hey @pnowosie good stuff! Are there any drawbacks?

[pnowosie]

Results are very promising.
The drowbacks I can imagine are

• we need to estimate a foreseen UTXO set cardinality and then reason about avg number of utxos that each address can own and then estimate a address' partition count,
• natural way to implement this solution is to update the partition lists during block application, this extends a Watcher's full sync time
• implementation can be tricky we need to remember that not all positions in the list will have the record in UTXO set.

UPDATE [@pnowosie]: I missed some drowbacks related to the observability and the need of rebalace... more in the below comment

[InoMurko]

I have a couple of questions I can't answer from the above @pnowosie.
How does searching for an output actually work? What data do you need? How do you pick a key to find what to spend?

What amount of partitions is this aiming at?

The idea is to have partitions evenly spread accross keys because if every key takes a fair share (lets say 10 keys), then in theory you should access the DB 10x faster. But if partitions are not evenly spread, then you can get skewed partitions (in our case, you'd have large amount of UTXOs under one key and less under others). Is this addressed?
Sometimes this happens and a rebalancing is needed. As said, if partitions are not spread evenly.

[pnowosie]

How does searching for an output actually work?

I'll work more to describe solution more clearly in the post above (in "Solution Draft")

What amount of partitions is this aiming at?

I'd say in the proposed solution there are 2 kinds of parameters

1. Number of partitions (related to unique addresses (keys) count in the system)
2. Max size of the utxo positions list in the partition. (related to avg number of utxos belonging to the address)

Both are related to the protocol bottleneck which is exitability, so the constraint is the total number of UTXOs.
Also number of unique addresses in the system which have (at least) 1 UTXO contribute to the above constraint. We have some estimation of it in Safe exit estimations

I don't have the answer to the above points 1 & 2, I stated my assumptions that the number of utxos belonging to each address is small (which should be also the account's owner focus). This points me to additional drawbacks I missed:

🔗 More drawbacks

• a need to have metrics of the mechanism:
  • number of partitions
  • number of partitions hit by the block consumption,
  • max & avg size of the position lists of the partitions (or more info about distribution of the sizes)
• a need to rebalance
  • if the avg position list size grows the answer is easy - increase the partitions count
  • if there are anomalies in the utxo distribution - the remedy would need more investigation
• only real usage data tell us how solution is working and the possible ways to improve it

if every key takes a fair share ..., then in theory you should access the DB nx faster

Actually it is much more faster than iterating through entire UTXO set and filter by the owner, because we fetch utxos by the key (OMG.DB.batch_get). However if one partition contributes to the significant percent of the whole UTXO set it makes no sense as you pointed out and then we need to understand why such case happened and then try to answer appropriately.

🙏 Thank you for the constructive feadback ❗

[boolafish]

Whole UTXO set cardinality is below 10M

BTW, it will be nice to have some documentation or investigation on the impact of UTXO set actually goes over that. I think there are two possibility that this will happen:

1. Users actually don't care or not aware of the safe exit size exists (Plasma is complex...)
2. In our current research, it actually looks quite positive to have dynamic exit period based on exit pressure. If that get finalized, the utxo capped can be larger in the future. I still think current 10M assumption is fine and probably more than what will be needed. But would be nice to understand the implications.

[InoMurko]

Solution draft
First of all please mind this is just supportive endpoint of security Watcher which aims to remind the address owner the utxo positions (s)he owns. Awared owner can skip this step and start exit utxos by the position right away. This endpoint was never meant to be be used for transacting.

I don't quite get ... why don't we partition UTXOs generally in the Watcher? I don't think it's viable to maintain two UTXO ledgers the way this is suggesting (partitioning just for this endpoint and having the utxo set under the rocksdb key utxo).

[pnowosie]

why don't we partition UTXOs generally in the Watcher? I don't think it's viable to maintain two UTXO ledgers the way this is suggesting

Not the UTXO set is partitioned here, I'm introducing here partitioning the address space to allow for quick(er) filtering UTXO by address (for the sake of the mentioned endpoint).

UPDATE [@pnowosie]: We agreed this approach makes a need to update two datasets: UTXO and address partitions, this is the meaning of two UTXO ledgers above

[unnawut]

Pasting my inputs from slack:

From user perspective I can think of 2 opposite user groups that relate to this:

1. Exchanges and enterprises: They’ll have addresses added and removed frequently because of new users and address rotation. But they also do not wish to tune things too much at this stage so they will default back to tracking all addresses.
2. Traders/arbitrageurs/smaller users: They serve themselves so they would not be adding/removing addresses too often. But they’re less likely to setup their own watcher and would rely on exchanges or other services, etc.

---

So given that there’s no supporting data that users will adopt it + the added complexity, I would say we can safely put aside interested_addresses for utxos for at least a year or more and a more general optimization for all addresses should good enough for a big while.

[InoMurko]

Let me provide a brief recap of the possible approaches and the discussion we had today:

1. The most obvious one is: can we just delete this because our data service is able to provide the information in question?
   The answer is no. And confirmed with @unnawut.
   Reason: If we turn off our data service and the chain goes byzantine the participant needs to exit his funds. The process of exiting funds is first extracting the UTXOs and then calling /utxo.get_exit_data and then going to Ethereum. So watcher exposing this information is part of the security protocol, so to say.
   Work impact:
   Deleting is fun if we could.

2. The second proposal is what @pnowosie intially proposed.
   Watcher would maintain two UTXO ledgers (albeit with different data structures).
   The first one is the standard one we currently use. Which if you imagine a KV store every UTXO in existence is behind a key called utxo: "utxoi", defined in @keys_prefixes in OMG.DB.RocksDB.Core.
   The second one is a partitioned utxo (just the position though) with the partition key being the "address space" (a chunk of it).

The core problem with this endpoint currently is that when you're looking up UTXOs from an account there's a lot you need to scan (imagine 10M utxos, mentioned previously)
More about the approach in the comment above: #1257 (comment)

Additionally to the linked text and paragraph: How to keep ownership lists up-to-date, there's an important bit that's not emphasized enough, which is, that maintaining two ledgers is not explicit to the programmer. In other words - the programmer needs to be aware at all times that there are two UTXO ledgers he needs to update. Calls for consistency problems in my opinion.

Work impact:
The compexity is not huge. But there are uncertainties (as outlined in @pnowosie text). Deposits, exits, transactions need to update both ledgers. Roughly a few weeks of work.

3. The third proposal is a spin on @pnowosie proposal.
   So instead of maintaining two ledgers, we partition the main one. There's quite a lot of resource on this topic under "bitcoin sharding". @pnowosie current assigment is to figure out if we can apply the bitcoin research into the way watcher maintains its utxo ledger.
   The main difference is that this would generally improve the performance of accessing UTXOs in the DB, not only on this specific endpoint!
   Work impact will be assed once the research part is concluded.

4. Fourth option is not viable with the current endpoint. Which is not really a problem. We leave /account.get_exitable_utxos as is and build new endpoints that are generally safer. If you're using old software, it's your fault mentality.
   These three new APIs are (perhaps read this with REST in your head, yuuck json rpc):
   This is really just to show an example. None of this is confirmed!
   PUT v2/account.track with specified "address value"
   DELETE v2/account.track with specified "address value"
   GET v2/account.get_exitable_utxos

The flow is as follows.

• a customer recognizes his account and sets the address by calling the first endpoint.
  This would need to do the following (in the backend):

1. from the current ledger, find all utxos beloning to the address above and move them under the address key
2. subscribe to all UTXO ledger changes for this specific address (for example, if there's a deposit from this address, make sure you push the UTXOs in the separate address key as well - similarly for spending, exiting...).
3. if you exit your funds from a specific address you can call the DELETE endpoint and basically drop the bucket and unsubscribe from the UTXO change events.

It seems like a very cool approach, but the current codebase is very much not event based and does not provide much reliable pub/sub. So the work impact is quite substantial (refactoring and then implementation).

He he, brevity was a lie.

[unnawut]

@InoMurko Thanks for the summary! 💪 The summary looks good to me. While the 3rd option research is happening, I can explore the 4th option from usage side. So some follow up questions for the 4th option:

1. Does it also have the "two UTXO ledgers" issue as the 2nd option?
2. How to handle get utxos for addresses that have not been registered. E.g. empty or error response?
3. Any idea on the performance impact, e.g. if it's a blocking operation and how long, to register a new address? Especially if the address is not new and there are already utxos scattered in it? Not needing exact numbers but knowing the factors that could influence the perf would be good.

[pnowosie]

Update to point 3 of the recap

First I'll describe a proposition which is step back from the partitioning proposition described above. It's simple additional mapping address => [utxo position] without partition function and all drawbacks partitioning approach brings with it.

Proposition 0

Let's introduce new dictionary

address_to_utxopos := #{ address_t() => list(pos_integer) }

where key is 20-bytes Ethereum address and value contains list of all utxo positions owned by the address.
You might already recall this is similar to described above but keys are particular addresses instead of partitions derived from the addresses (step back).
For the sake of completeness let us add that address_to_utxopos can be calculated from UTXO set. I'm leaving the algorithm for the curious reader 😂.

Storage considerations

Because Utxo has single owner, above address_to_utxopos collection has upper bound of UTXO set cardinality.
Assuming 10M 20-bytes addresses with a value of one 12B encoded utxo position + list encoding overhead, gives

kv_item_byte_size = 20 + 12 + 6 = 38 B
total_10M = ~ 362.40 MB

Performance considerations

We can assume that fetching utxo list by address is as fast as fetching the ownership_list from the previous proposition.

• Write and read single partition address data is below 0.3ms worst and 0.2ms avg
• Fetching all utxos for the partition address is 5ms avg
• Filtering utxos for particular address is neglible it already contains addresses positions

Given full block of 65 535 transactions is consumed 4 output each, just fetching data to update address_to_utxopos data takes:

65535 * 4 * 5.3 ms ~= 1389 s ~= 21 minutes 

Please mind it's the theoretical worse case forecast, it would be worth to check in the practice. Switching from in-memory UTXO set to RocksDB baked does not impact performance significantly. 👐

Optimizations ideas

You might ask why in the above calculation I considered only outputs (newly created utxos we need to add to owner addresses. What about spent inputs - shouldn't we remove them from the list as well?

Not really, hence it is important to add new utxo positions. Spent ones won't mess much besides occupying additional disk space, corresponding utxos from UTXO set will be deleted anyway. Further clean up can be done in the background job.

👍 Gains & Drawbacks 👎

Drawbacks

• Possible consistency problems due the need to maintain two related data sets.
• More storage consumed than in partitioned approach (mostly contributed by keys)
• Metric collection to observe how updating additional dataset impacts block application

Gains

• Simple and natural approach (implementation, maintenance ...)
• No need to tweak partition size and rebalance a dataset
• Supports the address tracking idea described in p. 4 of recap

I need to emphasize the fact that separate mapping for addresses does not impact the ability and performance of retrieving utxos by position. This is going to change... 👇

Conclusion

We can see that approach described in Proposition 0 will address issues of the get_exitable_utxos endpoint. It is conceptually simpler and easier to implement. It is also easier to infer about the performance and the limits of the solution.

Also we already show how to further optimize towards partitioning approach described above. Additional mapping was also implemented in ERC-721 to retrieve tokens owned by the address.

Option (kind of sharding approach)

I do not recommend the following approach, it's described here to demonstrate that we can further merge UTXO set and the Proposition 0's address_to_utxopos collection to eliminate data consistency drawbacks. It might serve as an inspiration to propose an improvements to the partitioning approaches.

Dataset construction

Let's create a dictionary

utxo_owners :: #{ address_t => #{ Utxo.Position.t() => Utxo_t() } }

Further we can apply partition function to the address to switch to the partitioned approach.

By constructing this dataset we will loose the ability to quickly fetch the utxo by the position. This means the need to rewrite the existing data fetching functionality.

Conclusion

It's obvious that the following dataset will resolve performance issues of the get_exitable_utxos endpoint.
It is the closest to sharding scenarios I found that could potentially work, however I'm unable to find the dataset which will enable quick searching by the utxo position and the address.

How it would serve the other scenarios

1. Transaction stateful validation

• recover address from the 1st signature
• try to get utxos by the input positions stored the address's list
• continue with next signature
  if we fail to collect all utxos included in the tx inputs - it means either the missing input was already spent or the signer is not the owner of the input

2. Get data for standard exit
   Because std exit can be started only by the utxo owner, we can assume that /utxo.get_exit_data endpoint would require not only the utxo position but also the owner address and then Watcher can check in the utxo_owners that utxo exists.

...

I'm not going to analyze the other scenarios. It is obvious that the approach is lacking the flexibility and will not allow to address future requirements.

[pnowosie]

Regarding the theoretical worst case forecast I provided above, @unnawut pointed my attention it might doesn't make any sense.

• First of all full-block of unique output owners means there at least 262k addresses which is a lot.
• Instead of fetching address after address we can get advantage from DB.batch_get
• Moving UTXO set from memory to RocksDB does not impact performance much (TODO: link needed ⛓️ )

[pnowosie]

Recap from conversation off-:octocat:

[originally @unnawut, @pnowosie recalled from his memory] With the proposition 0 described above can we switch on address tracking (see p. 4) later if we gain enough scale that we need to deal storage consuption increament?

Yes, with the proposed dataset we can reduce the addresses only to the tracked ones later to save disk space on instances there is such a need. Also our global Watcher deployment should continue to handle all addresses.

[@InoMurko] did you write down anywhere what we talked about it review of bitcoins sharding? Please be elaborate in what it means, what it does... it’s way easier to communicate if you overcommunicate, say things that are completely evident to you, but perhaps not to others.

Good point 👍 👏 . What I've learnt about Bitcoin partitioning strategies which are either based on partitioning the address space or utxo set was that the goal is to split the large network into smaller pieces (shards). Shards then operate separately and participants needs to store only shard's data to validate the subnetwork (hence the miners needs still keep entire network's data to mine blocks).
Returning to my research our goal was to find a partition strategy to allow better search capabilities on utxo set without keeping separate supportive datasets (aka indices) which hurts the code maintainability.
To satisfy such requirement I failed to find such partitioning. I've found very similar use case in ERC-721 where authors introduced additional dictionary.

[InoMurko]

sharding is another name for partitioning. so when I mentioned Bitcoins sharding I of course didn’t mean we would

• use their mining capabilities or mining complexity
• validations

The point was to see how they split the UTXO set into shards (partitions) so that they maintain optimal balance on these shards (partitions). Their shards (partitions) would be a way how we define the key (partitioning/sharding) function in:

• rocksdb
• multiple childchain postgres instances

So if you have more information about their sharding/partitioning, I would love to read it. Naturally, this would mean stripping out the bitcoin complexity of validation and mining (since we could have a distributed network but NOT a decentralized network (there are no byzantine cases, all participants are honest)).

[InoMurko]

One of the benefits of partitioning is parallelism. In our case that's not the case because RocksDB is single threaded.
Anyhow, if you define a good partitioning key, the access to data can definitely be faster using RocksDB. Since the amount of space it needs to scan is overall smaller. You can actually have a very large amount of partitions (in rocksdb terms they're just keys!!!)

I actually think this proposal is what we should do: #1257 (comment)

But instead of maintaining two "ledgers" we refactor the current storage to use just the partitioned one.
Comments?

[boolafish]

But instead of maintaining two "ledgers" we refactor the current storage to use just the partitioned one.

how.....do you do that though?

BTW, also want to bring this out early before any design is committed. In ALD, owner address is actually being abstracted under certain output type. So just want to mention that even if we would like to partition with address, it should better be first under certain output type. So it will be more like output type X --> go to the address partitioned DB for output type X.

[InoMurko]

if output type is a problem wouldn't this work too?
f(address) -> shard(N) -> (and if we imagine a PG column output type X) -> select outputs

Now this is under the assumption that what you're saying @boolafish means that a new output type means that you have N number of UTXO sets, correct? Currently, adding a new output type means two UTXO sets. Payment type v1 and the new one, right?

how.....do you do that though?

Well it's pretty simple, I think, lol.
If I describe one flow it's this:

• block getter gets a new block with transactions from childchain
• when applying the transactions:
  all inputs and the witnesses -> [{f(witness), blknum, txindex, oindex}, {f(witness), blknum, txindex, oindex}, {f(witness), blknum, txindex, oindex},...] ++
  all outputs -> [{f(owner.addr), currency, amount}, {f(owner.addr), currency, amount}, {f(owner.addr), currency, amount},...].

So for the example above, when you write to rocksdb, you write under 6 differen keys (that is, if the hashing function redirects the addresses into 6 different shards (keys!!!).

I hope this makes sense. If not, I need to POC to explain it better perhaps? :D Or think about an example more.

[boolafish]

as discussed as slack, the problem is ALD does not have the assumption "owner address" would definitely exists for all output type. It is on each output type to define what should be their data structure. ALD only asked for a output type field enable further dispatchment to different modules/codes/data.

It does not mean we cannot shard with address, just we need to design the DB to be first dispatching with output type, and then the output type can be using a sharded DB.

[pnowosie]

I actually think this proposal is what we should do: #1257 (comment)

I'll start with proposition 0 and then we can consider move next step...

But instead of maintaining two "ledgers" we refactor the current storage to use just the partitioned one.

I think I already elaborated I have found no single ledger solution. Can you describe how we proceed with the refactor?
We need fast utxo retrieval by position (safe option). We can use witness (signature) and compute owner address to find utxo from "new, single ledger" but I'm little scary that we could miss a flow that we have just utxo position.

[InoMurko]

Can you pls repeat what the problem is with just one?

[pnowosie]

Here is my recap of the Bitcoin (or more specifically UTXO-based ledger) sharding technics which will hopefully helps to answer to the comment.

As @InoMurko stated in the mentioned comment, sharding is a huge space of research which also needs to address security concerns like shard overtaking (similar to 51% attack), cross-shard transactions and so on.
My brief lookups was biased by this particular problem. I assumed only storage sharding (assuming Watcher validates all of the network transactions) and the findings were evaluated with transaction structure and RocksDB limitations in mind.

UTXO ledger sharding technics

1. Based on owner address

This is quite interesting approach but also has its drawbacks. It's interesting because theoretically leads to balanced utxo distribution. Also because the transaction usually spends single owner funds all inputs should be in the same partition. What's more it allows to take advantage of the usage patterns, e.g. addresses that initiate large amount of transactions.

Drawbacks lies in the payment transaction structure which identifies inputs by utxo position, and the owner can be identified by the transaction hash and the signature (by computationally expensive recovering owner address). This means large and risky refactor of the Watcher codebase.
Also @boolafish pointed out that ALD does not assume the ownership of the output

Readings

• This article further proposes network split by the amount of the token

2. Based on utxo identifier

This approach isn't something we can implement immediately. It assumes that utxo is identified by the pair:
{tx_hash, output_index} and the partition key be e.g. the of most significant bits of the transaction's hash.
I believe that early ALD work assumes we switch to this utxo identifier (❓) also it will allow to identify mempool transactions outputs the same way.

As a simple idea for ledger partitioning given the utxo position we're using now we might consider
{hash(blknum, tx_index), output_index} and the partition key of MSB of the hash value. This approach can be easier applied to our ledger storage model, however it does not address the performance issue with the endpoint (main topic).

Readings

• Ostraka scalling. Authors made a claims regarding cross-shard communication which is worth to take a look regards to chch2 effort.

During the investigation I also briefly skimmed following papers. They are focused on the full sharding details that provide limited usefulness in our case. To name a few sharding protocols working on UTXO ledger model: RapidChain, OmniLedger, Elastico...

Papers

• Divide and Scale: Formalization of Distributed Ledger Sharding Protocols
  Provides nice, high-level overview of UTXO-based sharding algorithms, such as OmniLedger, RapidChain, Elastico, Monoxide, ChainSpace and enumerating their properties.

• Analysing and Improving Shard Allocation Protocols for Sharded Blockchains
  Introduced formalism to shard allocation protocol. Provides analysis and comparison of existing sharding algorithms: Elastico, Omniledger, Chainspace, RapidChain and Monoxide. Pseudo-code implementation of the algorithms. As an improvement the Wormhole algorithm is described.

• Towards Scaling Blockchain Systems via Sharding
  Quite nice, high-level introduction to blockchain sharding with comparison to distributed database sharding and showing the challenges in the blockchain world.