0054-h3dex-targeting.md

HIP-54: H3Dex-based PoC Targeting

• Author(s): @Vagabond, @vihu, @abhay (hashc0de), et al
• Start Date: 2022-02-02
• Category: Technical
• Original HIP PR: #342
• Tracking Issue: #347

Summary

This HIP serves as both an explanation of the current Proof-of-Coverage (PoC) targeting behaviour as well as a proposal for a more scalable replacement using an H3-based index. We are proposing it as a HIP to communicate and acknowledge that this is a change to the current implementation but we believe it still falls within the original intent of PoC.

Motivation

The current targeting mechanism relies on a global list of asserted Hotspots. This list, as the network grows, is increasingly expensive to maintain and examine. Additionally, this list does not support garbage collection, so inactive Hotspots are counted towards targeting probability, leading to targeting skew in hexes with many inactive Hotspots.

An example of such mis-targeting is here.

The goal of this proposed work is to maintain the existing targeting semantics as closely as possible but rework them to operate on a more scalable data structure. A secondary goal is to reduce the active use of this edge case in order to enable more frequent PoC activity in an area. We don't believe this particular edge case is being exploited in a widespread manner (although we do see a few instances of it). With the publishing of this HIP, however, we believe it may become more interesting to arbitrageurs.

Stakeholders

All Hotspot owners are directly affected by this HIP. It should improve fairness in targeting for PoC but may affect those Hotspot deployers who are taking advantage of the current mis-targeting behaviour.

Detailed Explanation

We will begin by explaining the current targeting behaviour and then explain the proposed changes.

The first thing to grasp here is that the poc_request is non user submissible. It is generated by the miner itself. It depends on the poc_challenge_interval chain variable which determines if the miner is eligible to write a challenge to the blockchain.

Steps leading up to targeting:

1. If the criteria for poc_request are satisfied, the Challenger will try to construct a poc_request txn. This involves getting the hash of the block at which said miner is eligible to issue a request and the public key of the Challenger.

2. The create_request function (in miner_poc_statem.erl) then constructs a poc_request txn by first creating an ephemeral ecc_compact keypair, hashing the secret key and also hashing the public key, and putting both in the request transaction. The secret is then stored in local state to be used later. This completes the request phase.

3. Next the Challenger waits for the poc_request txn to appear in a block (assuming the poc_request was valid). Once it's seen in a block, the incoming block hash for the poc_request txn is also stored in the local state. At this point the Challenger moves to the targeting phase by supplying entropy used for randomizing the target Hotspot (Challengee). The entropy is a combination of the secret, the hash of the request block and the public key of the Challenger. Thus, the entropy is unpredictably random, but deterministic, implying that nobody can know what the entropy is until it appears.

4. Once in targeting phase:

• A list of all the populated hexes (at h3 resolution 5) is fetched from the Ledger.
• A random state is initialized using the incoming entropy and the Challenger's public key
• An initial h3 hex zone is selected using an Inverse Cumulative Distribution Function (ICDF) using random state and the hex list
• Random state is also stored for future computation

5. Once an initial h3 hex (zone) is selected, it starts a recursive target selection mechanism which operates upon the following filters:

• Filter out any inactive gateways (those which haven't been challenged in a long time decided by the poc_v4_target_challenge_age chain variable).
• Do not target the Challenger Hotspot itself (this is obvious).
• Do not target Hotspots which do not have relevant capability. Each Hotspot in the ledger has a mode defined in blockchain_caps.hrl.

6. Once there is a filtered list of eligible targets, it re-runs the ICDF with the updated Random state and finds a Hotspot to Challenge.

Note, critically, that inactive Hotspots are removed at step 5, but only after the initial h3 hex has been selected. This is what leads to the skew towards hexes with substantial numbers of inactive Hotspots. For historical context, this implementation was designed when the network was significantly smaller and there was a sparser distribution of Hotspots deployed.

After the "list of all the populated hexes'' in the ledger, mentioned at step 4 above, was added to the ledger, another piece of information, called the H3Dex, was added to the ledger to improve performance of HIP17. The H3Dex, short for H3 inDex, is an arrangement of H3 indices formatted in such a way that they can be iterated over with a ranged iterator so that any Hotspots inside that hex, of an arbitrary resolution, can be queried. This is superior in several ways to the older "hexes" list:

• It can be updated granularly
• It can be queried efficiently
• It does not require the entire list to be read into memory to be used

However, it shared the flaw with the hexes list in that it, too, had no garbage collection for inactive Hotspots. The HIP17 code also did inactive Hotspot filtering.

As noted above, as the network has grown, storing all 500,000+ Hotspots in a single list has become infeasible. Updating that list on a Hotspot location assert has become one of the most expensive single operations on the chain today. The H3Dex, which is updated at the same time, updates typically in orders of magnitude less time.

Therefore, the core developers have been discussing for some time the proposal to replace the current targeting with something that can use the more efficient H3Dex.

Essentially the steps outlined above remain the same except for step 4. Step 4 is replaced by the following:

• A set of poc_target_pool_size populated hexes is selected randomly, using the challenge entropy, from the h3dex. poc_target_pool_size is a new chain variable.
• The set of populated h3 hexes is weighted by their active population counts and an ICDF is run as before in step 4

At this point the code continues with step 5, although the inactive Hotspot filtering is removed since it's no longer needed.

Now, randomly selecting from a set of populated hexes, without examining the entire set, is a bit more complicated than it appears. Essentially all the populated hexes at a fixed resolution, the existing chain variable poc_target_hex_parent_res, are iterated and stored in h3 order, keyed by their position in the list, into the ledger. This allows a relatively simple random selection by simply taking a random number between 0 and N, where N is the count of populated Hotspots at the poc_target_hex_parent_res resolution. When new hexes are populated or unpopulated (the population goes from 0 to something, or from something to 0), the random lookup table is recalculated. With a relatively low poc_target_hex_parent_res this is very infrequent.

The second complexity here is how to garbage collect the h3dex without causing a performance problem. The current implementation uses PoC receipts to GC the first N Challengee locations for the first PoC receipts in a block. This is deterministic and cheap and should cover all challenged hexes over time. Another possible option is to do some GC as a side effect of HIP17 calculations.

This proposal is currently implemented in blockchain-core#1173 and blockchain-core#1214.

Drawbacks

The only known drawback is a slight change in targeting selection semantics because an ICDF over all populated hexes is no longer used. This is expected to average out over time, but testing for biases and presentation of results will be done and added to the HIP here.

Rationale and Alternatives

This design was considered superior to some alternatives because it uses an existing data structure that the ledger already tracks and uses and does not add any excessive additional computation. It does require a new chain variable which will require all nodes (Hotspots, Validators, Routers, ETLs, Nodes, etc) to update.

Alternatives to this design were improving the hexes list in the ledger somehow or adding an entirely new structure to track hex populations for targeting. Neither was as optimal as moving more code to using an existing, superior data structure, as well as adding garbage collection to that existing data structure which should be able to improve HIP17 calculation performance as well.

The list continues to grow, continues to become more expensive to interact with, targeting becomes more and biased by inactive Hotspots.

Unresolved Questions

The other mechanics of targeting are considered out of bounds. This HIP aims to maintain existing behaviour as much as possible and simply improve performance and scalability.

Deployment Impact

Normal users should not expect to see a measurable impact, other than improvements to chain performance.

There is not a large amount of information about the targeting in the documentation, indeed this HIP attempts to improve the situation. Any existing documentation should be updated to reference this HIP.

It is backwards compatible. It will be activated by a chain variable which will trigger the creation of the lookup indices and begin the garbage collection. The existing hexes list can remain active on the ledger while the stability of the new system is verified. Once the update has been verified the old hexes list can be deactivated/removed by a subsequent chain variable or ledger upgrade hook.

Code could also be written to re-calculate the hexes list on a downgrade back to the old behaviour.

Success Metrics

The community should notice an improvement in the performance of validating and absorbing blocks and more expected targeting distributions.