Proof-of-Coverage and PoC Challenges

Helium uses a novel work algorithm called “Proof-of-Coverage” (PoC) to verify that Hotspots are located where they claim (as established in the assert_location transaction when they are first deployed). Put another way, Proof-of-Coverage verifies on an ongoing basis that Hotspots are honestly representing their location and wireless network coverage they are creating from that location.

This section will cover the relationship between PoC and Challenges, how these contribute to a Hotspot’s “score” over time, and how this relates to their ability to earn Helium Tokens.

Why Proof-of-Coverage?

The Helium Network is a physical wireless network that succeeds based on the amount of reliable coverage it can create for users. As such, we needed a proof of work algorithm that was built for this use case. Proof-of-Coverage takes advantage of the unique, undeniable properties of radio frequency (RF) to produce proofs that are meaningful to the Helium Network and its participants.

Specifically, PoC makes use of the following characteristics:

  • RF has limited physical propagation and, therefore, distance;

  • The strength of a received RF signal is inversely proportional to the square of the distance from the transmitter; and

  • RF travels at the speed of light with (effectively) no latency;

Using these properties, the Network is constantly testing Hotspots using a mechanism known as a “PoC Challenge”. (More on these in a moment.)

The ultimate power of Proof-of-Coverage lies in the fact that the data generated by the ongoing proofs and stored in the Helium blockchain is definitive verification of the wireless coverage provided by, and more specifically, the location of, Hotspots on the network.

The Anatomy of a PoC Challenge

Individual Proof-of-Coverage challenges can be viewed in Helium Explorer.

A Helium Proof-of-Coverage shown over a map of San Francisco

Each Challenge has the following set of participants:

  • Challenger - The Hotspot that creates a proof and submits it to the blockchain. Hotspots are rewarded for submitting valid Challenges and, as such, submit as many proofs as the Network will allow. Currently each Hotspot can submit one challenge per 60 blocks (or roughly one per two epochs).

  • Target - Any Hotspot chosen to complete the Challenge (also referred to as a “challengee”). The minimum number of targets per challenge is two; and the maximum number is seven. All targets in any given Challenge are located in the same geography such that they are able to communicate over RF with at least one target. The Targets do not need to be in geographic proximity to the Challenger.

  • Witness - A Hotspot that can verify the existence of the Challenge packet over RF at any stage in the Challenge path. A Witness can also be a Target in any given Challenge.

With this in mind, let’s walk through how a PoC Challenge actually happens on the Helium Network.

Challenge Proof Construction and Initial Target Selection

Since Hotspots are rewarded for submitting challenge proofs and their receipts to the Network, they construct and submit as many as possible. Collectively, Hotspots submitting valid proofs and the associated proof receipts split 1% of all HNT mined each epoch. (See the full HNT reward breakdown here.) As noted above, they are currently allowed to submit a challenge proof roughly once per 60 blocks.

The challenge process begins with the Challenger selecting an initial target Hotspot. The blockchain maintains a discrete probability distribution of Hotspots according to their score that’s used by the Challenger when selecting the initial target. Lower scoring Hotspots have a higher probability of being selected as the initial target because the Network wants to give them the opportunity to increase their score by participating in challenges. Specifically the POC algorithm tries to target Hotspots close to the neutral score (.25) in order to move that score either towards 1.0 or towards 0.0, depending on how they perform.

(See the Hotspot Scoring) for more details on what causes a Hotspot’s score to increase or decrease over time.)

The Challenger first generates an ephemeral public/private key pair to be used in the challenge. A SHA256 digest of the public key and the SHA256 digest of the private key are both submitted, along with the current block hash, as a PoC request. If the request is valid and accepted by the blockchain, the hash of the block that the receipt appears in is combined with the hash of the ephemeral public key and the challenger's identity to generate verifiable entropy. A uniform random number generated via this entropy is then used to select an initial target from the discrete probability distribution of Hotspots.

Constructing The Multi-layer Challenge

This phase of the challenge begins with the Challenger selecting a target, followed by set of Hotspots known by the blockchain to be within a continuous radio network of said target. Challenge packets are transmitted over RF using the Hotspot’s on-board sub GHz radio, so the distance between any two targets must be achievable using this RF link. A Hotspot’s location is established in the assert location transaction used when deployed.

Once complete, the Challenger constructs a multi-layer challenge packet that is to be completed by the challenge targets. This multi-layer packet is essentially an “envelope of envelopes”, with each layer of the packet only decryptable by its intended target. The innermost packet layer is then created and added to the challenge packet, encrypted using the Diffie-Hellman exchange of the public key of the final target (accessible via the blockchain) and the ephemeral private key. This layer creation and encryption process repeats for each target in the challenge list until the complete challenge packet has been completed.

As an additional measure the PoC packet is encrypted and decrypted in such a way that the length of the packet remains constant at each layer. This means that no target along the path (other than the first hop) knows its position in the path, or if it is the final hop.

Creating the Proof

With the multi-layer challenge packet created it is then delivered to the initial target via the Helium Peer-to-Peer Network. The initial target receives the challenge packet, decrypts the outermost layer using its private key and the ephemeral public key for this challenge (this ephemeral public key appears in the PoC packet and the receiving Hotspot can inspect the blockchain for an active PoC receipt with the corresponding SHA256 of the ephemeral key), and immediately broadcasts the resultant packet to the Helium Network. Although this packet only has one intended target (which is unknown to the sender), it’s likely that any number proximate geographic Hotspots will hear it. (Hotspots that hear challenges packets but that cannot decrypt them are called “Witnesses.” More on these below.)

When the intended target receives the packet, it records both the time of arrival and the signal strength of the packet. If it’s able to decrypt the packet, it creates a signed receipt that includes both the time of arrival and the signal strength data, and signs it with its private key. Finally, it sends this signed receipt back to the original Challenger (which is looked up via the SHA256 of the ephemeral key to find the challenger) via the Helium Network, and broadcasts the remainder of the challenge packet over the Helium wireless link to its geographic peers. This process continues until all targets in the challenge path have sent signed receipts back to the challenger, or the challenge fails. The final layer of the onion is intentionally padded so that no challengee knows if they are the last hop in the path. And because the final challengee transmits the challenge packet to other Hotspots, this packet can be witnessed.

The Role of Witnesses

As mentioned above, during the course of a given challenge, a Hotspot may hear a PoC challenge packet but not be able to decrypt it if it’s not the intended recipient. These Hotspots are known as “witnesses” and still have immense value in the Helium Network and the Proof-of-Coverage system. Collectively witnesses earn 9% of all the Helium token rewards produced each epoch.

Witnesses bolster the strength of the Helium Network by attesting to the existence of challenge packets. It’s analogous to witnessing a car crash from the sidewalk. Though you weren’t involved directly, you can report what happened to the authorities when they need details. This is what a Witness does for challenges. When an active challenge packet arrives that they can’t decrypt, they record the SHA256 of the packet they saw, along with the time of arrival and signal strength, and report this back to the Challenger. The Challenger then includes this receipt, if valid, in the completed challenge proof. Witnesses don't know if the packet they're witnessing is valid or corrupt. Only the Challenger is able to make this determination.

Though witnesses are not required for a successful proof, they are likely to be present. Currently there is a limit of five witnesses per challenge packet layer. A target in a proof can also serve as a witness for challenge packets transmitted by targets other than itself. You can see Witnesses in action using the Helium Explorer or in the Challenges section of the Helium Mobile Wallet.

Verifying the Proof

Once the Challenger has the complete set of receipts from the proof targets, or the elapsed time since the challenge was issued has passed the upper time bound, the Proof-of-Coverage is considered complete. At this point, the challenger then submits the proof receipt as a transaction to the blockchain to be verified by the current consensus group. Because the steps taken by the Challenger to construct and complete the proof are deterministic and easily reproduced, members of the consensus group can verify the legitimacy of the proof. Specifically the Challenger reveals the secret ephemeral key it used for both obtaining the original PoC request and for encrypting each layer of the challenge packet. This crucial information, which has been hidden until the receipt is published, allows the re-creation of the deterministic entropy.

Challenge Rewards Require Receipts

In order for a Challenger to be rewarded for their proof, the receipt of that proof must be successully received by the blockchain.

Hotspot Scoring

A Hotspot’s score is a measure of the Network’s confidence in the asserted location of that Hotspot. The Helium Network is continually questioning the true position of Hotspots using PoC Challenges. Most importantly, activities that produce higher scores correlate with more token rewards for a given Hotspot.

Hotspots are scored from 0.0 to 1.0 (displayed as 0 to 100 in various places like the Dashboard), with 0.0 being the lowest and 1.0 being the highest possible score. Each new hotspot starts with a neutral score of 0.25 when it is added to the blockchain.

Once deployed, Hotspots are eligible for being challenged based on their score. How they perform in these challenges will affect their score dramatically.

  • Successfully verifying location via passing a challenge causes a score to increase.

  • Conversely, failing to verify location results in a lower score.

Additionally, to keep scores fair, there is a constant "gravity" effect which continuously pulls the Hotspots towards the neutral score of 0.25. Doing so, we avoid Hotspots forever remaining on the top or on the bottom of the 0 - 1.0 score scale.

  • If a Hotspot has a stable internet connection but is never challenged - which is possible if it has no geographic peers - its score will remain at the neutral 0.25 level

Hotspots with higher scores are more likely to be chosen for a Consensus Group, thus making them eligible to earn mining rewards for that epoch. Members of the Consensus Group split 6% of all the tokens created each epoch for tasks such as validating transactions and publishing new blocks to the blockchain. So it pays to be at the top, but the network does what it can to make it, well, challenging.

What is my Hotspot's score?

Currently we do not display scores in the Helium Mobile Wallet App. However, you can view your Hotspot's score in the Helium Explorer. Scores are also returned by the Helium Blockchain API.

Challenge Failure Modes and Score Implications

Challenges fail frequently. Here is a list of common PoC Challenge Failure Modes, their typical causes, and how this affects a participating Hotspot’s score. In any given challenge that does not complete, it’s likely you’ll see more than one of these failure modes appear.

Initial Target Not Challenged

In this scenario, the Challenger submitted a valid PoC challenge to the blockchain which was then sent to the initial target and subsequently received by this targt via its Internet connection (often referred to "P2P"). From there, the target is responsible for decrypting the challenge packet, sending a receipt back to the Challenger, and broadcasting the challenge packet with one less layer of encryption to other Hotspots in range via its RF link.

Proof-of-Coverage is all about proving the location of Hotspot using its wireless capabilities. And since the initial target receives the challenge packet via its Internet connection, simply decrypting it and responding over this link doesn't provide any meaningful data about the Helium coverage that Hotspot might be providing. So, in order for the initial challenge target to successfully pass a challenge, the blockchain must have verifiable proof that it was successful in broadcasting the challenge packet over RF. This proof comes in the form of witnesses and/or the next Hotspot in the challenge path successfully responding with a receipt.

However, when the Helium blockchain does not have definitive proof the challenge packet was transmitted, we categorize it as "Initial Target Not Challenged." In this failure mode, no Hotspots are penalized.

Failed Challenge

Here, a Hotspot is believed to have received the multilayer challenge packet over RF from the previous Hotspot in the challenge path, but has failed to complete the packet decryption and response. In this failure mode, only the Hotspot that fails the challenge will see their score decrease.

Not Challenged

When this happens, a Hotspot that’s a predetermined participant in a PoC challenge was never given the opportunity to complete it because either a) the Initial Target was never challenged or b) a Hotspot earlier in the path formally failed its portion of the challenge. In this scenario, any Hotspot that was “Not Challenged” will not see their score decreased.