search

helium / HIP

Helium Improvement Proposals
Apache License 2.0
583 stars 407 forks source link

HIP14: Proof-of-Coverage Ripple Method #50

Closed jamiew closed 2 years ago

jamiew commented 4 years ago

Author: @anthonyra Initial PR: https://github.com/helium/HIP/pull/47 Category: Technical

Rendered view: https://github.com/helium/HIP/blob/master/0014-poc-ripple-method.md

Summary: The current Proof-of-Coverage allows for Virtual Machine (VM) farms or hotspot farms that have been engineered to maximize return of rewards without providing benefit to the network. This HIP proposes a different method to to determine Proof-of-Coverage, by seperating the network into islands that are based on the geolocation of hotspots and their associated witness lists.

Carniverous19 commented 4 years ago

I have an implementation question on this, in your Ripple Effect section (describing how the new PoC would work) you say:

  1. The Pebble hotspots receive the envelope 4.i. They sign the envelope with their Island Hex and broadcast it via RF (LoRa)
  2. There are two options for the hotspots that receive that broadcasted envelope 5.i. The receiving hotspot is the opposite Pebble hotspot, in this case the envelope will be able to be decrypted and sent back to the challenger 5.ii. The receiving hotspot is not the opposite Pebble hotspot, in this case it performs step (4.i)

Would this cause a broadcast storm? Say a hotspot with lots of witnesses is the first hotspot to transmit in a challenge (for example Dry-Daisy-Tortoise). Its likely all of its witnesses but one would not satisfy 5.i and therefore they would run 5.ii meaning they sign the envelope and broadcast, you would have ~50 hotspots all broadcasting at once? Looking at the following Limitations section, None of these witnesses would be in the same res 8 hex as Dry-Daisy-Tortoise so wouldn't drop for that reason and if Dry-Daisy-Tortoise is the initial target, there are no other observed island hexs in this challenge so it none would be dropped for that reason.

anthonyra commented 4 years ago

The thing to remember is that it will still be limited by the size of the island. The max size is 7 hexs. Building out these islands will be the initial growing pain. However, this limitation would keep the island small and limit the size of the 'broadcast storm'. There will be an initial flood but if you had 1000 devices in the same area what is the big deal with 50 hotspots sending packets?

The model (it doesn't incorporate the age of hotspot currently) but it indicates that 10 hotspots would be within the island that Dry-Daisy-Tortoise resides in.

Carniverous19 commented 4 years ago

Ok I've spent like an hour reading and Im getting more confused... 😄

Let me try to get the basics here.

Carniverous19 commented 4 years ago

The model (it doesn't incorporate the age of hotspot currently) but it indicates that 10 hotspots would be within the island that Dry-Daisy-Tortoise resides in.

How do you get to 10 hotspots? Dry Daisy has like 40-50 witnesses? and per step 7 in Island Construction:

you repeat step 2-5 for all witness hotspots.

That means you repeat step 2-5 for at minimum all of Dry-Daisy's witnesses + any other hotspots in the same res8 hex as Dry-Daisy.

Also in your Island construction section I don't see how the size of the island is limited? Where does that come in to play when constructing an island?

anthonyra commented 4 years ago
  • What is a pebble? and more importantly how does it differ from other hotspots in the island? In your definition you say a Pebble is selected by the challenger to start a ripple so that sounds like there is only one pebble hotspot per challenge but then later on it looks like there are many. I suggest the term Pebble needs to be expanded / clarified

The definition in the HIP: Pebble (challengee) - Selected by the challenger to start the ripple. Minimum of 2 all must be in a different Island Hex

  • Does this create a path (ordered list of hotspots) like the current PoC? Based on your illustration there seems to be a target (blue hotspot in upper left of Figure 1-1). An orange "Target" hotspot that isn't defined or mentioned in the Ripple Effect section.

The original proposal had pebbles and targets but later I realized that they are one and the same. It looks like I'll be needing to comb through the proposal again to clear up any 'missed' reference to targets to include the diagrams that I used. For a ripple there will be a minimum of two pebbles (starting hotspots or origin hotspots) I liked calling them pebbles for the ripple effect that is being emulated with this method.

The end goal is to create a chain of hotspot signatures based on their path the packet took to cross the island. It's pretty similar to the PoC path today however it's not predetermined. If the packet makes it to the other pebble (target) then it will be considered an acceptable chain. If it doesn't then it's dropped.

  • In Ripple Effect, I think the re-use of the term Pebble makes things confusing. THe challenger sends a packet to Pebble hotspots (why plural? does it just send to the first hotspot?) I am assuming this initial target transmits and then a Pebble receives it? Also in 5.ii. It says if a hotspot is not the "opposite pebble" it will go to 4. which says a "pebble" receives? So its not the opposite pebble, is a pebble, but not a generic hotspot in teh island?

Pebble is meant to be the starting hotspot for the ripple. If it's too confusing then I will have to re-write to clear up the explanation. The proposal requires two pebbles (the original proposal had a pebble and a target but was changed since neither should know if they were the pebble or the target) for the validation process.

The challenger sends the request to the pebble via p2p. The pebble receives the packet from the challenger since that packet can't be decrypted except by a different pebble than it needs to forward that packet via RF to try and find the other pebble(s). It has the ability to work with more than 2 pebbles but I think there are more cons than pros to doing so but I left it open for discussion.

I can see clarification is needed and I appreciate the feedback. Since there's going be two pebbles for each challenge to an island there's the one that the packet originates from (received via p2p from challenger) and then a chain is built via RF until the other pebble is reached (this pebble then can send it back to the challenger or straight to the Consensus Group)

A simple chain would look like Pebble(start) => Hotspot(1) => Hotspot(n) => Pebble(target, final)

anthonyra commented 4 years ago

The model (it doesn't incorporate the age of hotspot currently) but it indicates that 10 hotspots would be within the island that Dry-Daisy-Tortoise resides in.

How do you get to 10 hotspots? Dry Daisy has like 40-50 witnesses? and per step 7 in Island Construction:

you repeat step 2-5 for all witness hotspots.

That means you repeat step 2-5 for at minimum all of Dry-Daisy's witnesses + any other hotspots in the same res8 hex as Dry-Daisy.

Also in your Island construction section I don't see how the size of the island is limited? Where does that come in to play when constructing an island?

This section is in need of attention because at the beginning of writing this HIP the process that the network would use to actually create these islands was unknown. The process listed in the current section describes how the models shown were generated and not how the islands should be generated for the actual proposal.

For clarification, the original proposal was to create witness driven islands that would then be challenged as a group. Upon building out the proposal it was apparent that if not limited by size the resulting packet broadcasts would quickly get out of hand. Therefore, limitations were established and I don't think properly documented (some in the wrong place) to draw the applicable picture that I've envisioned. However, I didn't want to delay providing my idea due to not having a perfect idea. For, in the end, it might not even be the one picked but could spark or guide the actual proposal to the better answer.

I really do appreciate the feedback and I'll be working on v2.0 which should be clearer and more concise and hopefully less confusing.

Carniverous19 commented 4 years ago

No problem its making a bit more sense.

Ok so only the starting and ending endpoints are pebbles and are pre-determined none of the middle hotspots are pre-determined an can be any hotspot in any island hex or does each island hex have a pebble? When would there be more than 2 pebbles?

I think it would be helpful to show (either in figures or in prose). What happens if there are other hotspots in island hexs, For example, take your ideal ripple figures but with 4 hotspots in each island hex. (Will all hotspots not in the originating hex transmit or only those designated on the path?). Also what happens if hotspots not in the island receive a transmission? Like if there was a challenge in the middle unshaded hex or off to the side. I think its important to make clear that your figure steps don't happen in order and may in fact happen simultaneously.

Overall, I like this approach or ones like this that look at overall network behavior to evaluate validity and health. I do think this can be done with the data collected during beaconing- it doesn't have to drive how and when hotspots transmit as long as it has a sufficient dataset to evaluate island performance. In fact this is what you are doing now when you look at current multihop data to build island and test your proposal. Like if you guaranteed every hotspot transmitted every epoch and you gathered who witnessed each transmission that's plenty of data to evaluate performance in an island. It makes this a lot simpler as its an algorithm that runs on the CG and just looks at recent activity in the ledger to grade islands or hotspots. It would be worth looking at your ripple method from that perspective. I also think it will work much better in practice, there are lots of implementation details I worry about such as dropping packets transmitted from island hexs you already heard is probably too restrictive you may be dropping chains that haven't been observed yet. For example if there is an island with 5 hexs A, B, C, D, E and you are challenging from A->E. If chain A->D->E gets observed first you then block A->C->D->E or A->B->D->E from getting through?

anthonyra commented 4 years ago

Ok so only the starting and ending endpoints are pebbles and are pre-determined none of the middle hotspots are pre-determined an can be any hotspot in any island hex or does each island hex have a pebble? When would there be more than 2 pebbles?

I believe the ideal would be a max of two pebbles for simplicity reasons since the more pebbles the more acceptable chains exist to be captured. The more pebbles would just increase the chance of not selecting the same account hotspots in the island (which if this was a concern I feel account limitations would be an easier limit to set then increasing the pebble count).

You’re also correct that pebbles are pre-determined and the hotspots in between are not pre-determined. I also feel that due to all the factors naturally with RF that perfect # of chains will be in fact the goal but more likely the results of gaming. However, real world data is needed to prove this.

I agree that it would be beneficial to show what happens when more hotspots are found in an island hex. I’ve been meaning to do that but it takes time to hand draw the combinations (wish I knew how to do computer simulations) but it’ll essentially turns into a race atleast as it’s currently written. The reason is the # of broadcasts. Right now there would be 240 if it’s determined that it can increase than the race can be expanded. Meaning that instead of the first hotspot in the hex being the one able to sign more would be able to be signed.

jamiew commented 3 years ago

@anthonyra this HIP has become stale and we are planning to close if no other updates. Thanks!

anthonyra commented 3 years ago

@anthonyra this HIP has become stale and we are planning to close if no other updates. Thanks!

I've been patiently awaiting PoCv11, however I think the newest version of this diverges so much from HIP-14 that it might be best to archive this thread and I'll submit a new HIP for the revision. Thanks for the ping!

jamiew commented 2 years ago

Closing stale HIP. Thank you for the submission. Please re-open if it gets revisited