Revamped reward formula that compensates for wasted ticks

Research
1

Motivation

Suppose first (for the sake of argument) that optimal PoETs are readily available.

  • Meaning that when the miner finishes the linear pass of the PoST proof generation, she can immediately submit her ATX to a PoET server that immedaitely starts performing the sequential work on her ATX.

Suppose first (for simplicity) that all the miners do the linear pass with 100 MiB/s speed with 160 nonces, which succeeds with 98% success probability.

  • If Alice is a small miner with 256 GiB, then she wastes 2560 seconds (42.6 minutes) worth of ticks in every epoch, which is 0.2% of the 336 hours of epoch time.
  • If Bob is a big miner with say 32 TiB, and he wastes 128\cdot 2560=327690 seconds (91 hours) worth of ticks in every epoch, which is 91/336=27% of the epoch time.
  • Under these (unqualified) assumptions, it’d be justified for the reward formula to give Bob 27% more spacetime weight relative to Alice.
    • Because the spacetime weight is determined according to storage*ticks, and Alice has 27% more ticks than Bob in each epoch.
    • Hence, in principle, it’s fair for Bob to earn a higher reward relative to Alice, because Alice recoups the same extra reward by wasting less ticks than Bob.
  • Of course, if we instead assume (say) that all the miners have 500 MiB/s speed with 96 nonces and 90% success probability, then Bob wastes 5.4% of the epoch on his linear pass, so the reward formula should give him 5.4% more weight relative to Alice.

Practical rationale

In the real world we don’t have optimal PoET servers, but still, similarly to the above theoretical considerations, there are practical considerations that justify giving a greater spacetime weight to the larger miners

  • Suppose for instance that the theoretical formula gives 10% more spacetime weight to Bob (with 32 TiB) relative to Alice (with 256 GiB).
  • Suppose that there’s phased PoET with 14 phases (one phase per day).
    • So each phase is 1/14=7% of the epoch.
  • Alice may have inexpensive hardware that allows her 100 GiB/s speed, so her linear pass takes just 42 minutes out of the 24 hours of the phase of the PoET.
  • Suppose that Bob’s speed is 500 GiB/s speed with 64 nonces and 80% success probability, which takes 18 hours (that fits into the 24 hour phase of the PoET).
    • Since Bob won’t have time to attempt another linear pass in the same phase of the PoET, he’d need to skip to the next phase (and lose 7% of the ticks of the epoch) when his PoST proof generation fails. Thus, Bob will probably want to invest in even faster harddrive (so that the linear pass takes less time) and faster CPU (to use more nonces and thereby increase the success probability of the linear pass).
  • Bob’s expenses are higher than Alice’s expenses (because Bob needs stronger hardware in order to fit into the PoET phase), so it’s fair for the reward formula to compensate Bob for his extra costs.
  • Even if Alice and Bob have the same hardware (same intitial investment costs and same operational costs):
    • Bob will spend his resources to obtain k2pow for a rational number of nonces, for example 160 nonces that imply 98% success probability.
    • Alice’s linear pass finishes within a small portion of the length of the PoET phase (e.g., 42 minutes out of 24 hours which is less than 3% of the epoch duration)
      • So Alice is able to perform multiple attempts of PoST proof generation within a single PoET phase, implying that on average she needs spend her resources of relatively few k2pow values.
        • For example, 64 nonces for 80% success probability, and upon failure another 64 nonces, and so on.
          • Which implies an average of 64+0.2\cdot64+0.2\cdot 0.2\cdot 64+0.2\cdot 0.2\cdot 0.2\cdot 64+\ldots=64\cdot5/4=80 nonces.
    • Bob is likely to be able to have only a single attempt of PoST proof generation (and in any case much fewer attempts relative to Alice).
    • When Bob fails to create the PoST proof (e.g. with 2% probability if he has 160 nonce and only a single attempt), he skips to the next PoET phase and thus loses 7% of the ticks of the epoch.
    • Hence, Bob’s amortized amount of wasted ticks is larger than Alice’s.
  • Alice (with 256 GiB storage) may in fact have (near) zero marginal costs because she already had 256 GiB free storage on her computer, unlike Bob (with 32 TiB storage).
    • It’s ok for Alice to make a profit even if she gets a worse deal than Bob.

Overestimates and underestimates

  • Suppose for instance that miners with 32 TiB storage waste approximately 20% of the ticks of the epoch on PoST proof generation (so the reward formula gives 20% extra weight for 32 TiB).miners with 16 TiB storage waste approximately 10% of the epoch on PoST proof generation (so the reward formula gives 10% extra weight for 16 TiB), miners with 8 TiB storage waste approximately 5% of the epoch on PoST proof generation (so the reward formula gives 5% extra weight for 8 TiB), and so on.
  • Suppose that Alice has 16 TiB storage and Bob has 32 TiB storage.
  • Suppose the optimal PoET servers are readily available.
  • Suppose that Alice indeed has 10% wasted ticks and Bob indeed has 20% wasted ticks in each epoch.
    • Alice’s spacetime weight in the reward formula will be 16 \cdot 1.1 \cdot \text{ticks}_\text{alice}, as she deserves.
    • Bob’s spacetime weight in the reward formula will be 32 \cdot 1.2 \cdot \text{ticks}_\text{bob}, as he deserves.
  • Suppose that Alice and Bob are 10% slower than the other miners
    • Alice’s spacetime weight needs to be 16 \cdot 1.11 \cdot \text{ticks}_\text{alice}\ to break even.
    • But Alice’s spacetime weight in the reward formula is still 16 \cdot 1.1 \cdot \text{ticks}_\text{alice}
    • Alice’s rewarded weight is 16 \cdot 0.01 \cdot \text{ticks}_\text{alice}\ less than what she deserves.
    • Bob’s spacetime weight needs to be 32 \cdot 1.22 \cdot \text{ticks}_\text{bob}\ to break even.
    • But Bob’s spacetime weight in the reward formula is still 32 \cdot 1.2 \cdot \text{ticks}_\text{bob}
    • Bob’s rewarded weight is 32 \cdot 0.02 \cdot \text{ticks}_\text{bob}\ less than what he deserves.
  • Suppose that Alice and Bob are 10% faster than the other miners
    • Alice’s spacetime weight needs to be 16 \cdot 1.09 \cdot \text{ticks}_\text{alice}\ to break even.
    • But Alice’s spacetime weight in the reward formula is still 16 \cdot 1.1 \cdot \text{ticks}_\text{alice}
    • Alice’s rewarded weight is 16 \cdot 0.01 \cdot \text{ticks}_\text{alice}\ higher than what she deserves.
    • Bob’s spacetime weight needs to be 32 \cdot 1.18 \cdot \text{ticks}_\text{bob}\ to break even.
    • But Bob’s spacetime weight in the reward formula is still 32 \cdot 1.2 \cdot \text{ticks}_\text{bob}
    • Bob’s rewarded weight is 32 \cdot 0.02 \cdot \text{ticks}_\text{bob}\ higher than what he deserves.
  • Suppose that the reward formula purposefully overestimates by specifying that 32 TiB storage deserves 22% extra weight, 16 TiB deserves 11% extra weight, 8 TiB deserves 5.5% extra weight, and so on.
    • Miners with 32 TiB will gain 2% more than what they deserve.
    • Miners with 16 TiB will gain 1% more than what they deserve.
    • The big miners are unjustly rewarded more than the small miners.
  • Suppose that the reward formula purposefully underestimates by specifying that 32 TiB storage deserves 18% extra weight, 16 TiB deserves 9% extra weight, 8 TiB deserves 4.5% extra weight, and so on.
    • Miners with 16 TiB will lose 2% relative to what they deserve.
    • Miners with 16 TiB will lose 1% relative to what they deserve.
    • The big miners are unjustly damaged the most, the small miners are unjustly damaged the least.
  • Conclusion:
    • If the reward formula errs (on purpose) on the side of giving an x-percentage smaller amount of extra weight (to compensate for wasted ticks) compared to what the miners deserve:
      • The big miners will get an x-percentage worse deal than what’s fair.
      • It’s likely that there’d be more ATX splitting relative to an accurate reward formula.
      • If x is small then there’s likely to be less ATX splitting than in the case that x is large.
      • The smaller miners are happier when x is large, because they get a better deal relative to the large miners.
    • If the reward formula errs (on purpose) on the side of giving an x-percentage greater amount of extra weight (to compensate for wasted ticks) compared to what the miners deserve:
      • The big miners will get an x-percentage better deal than what’s fair.
      • It’s likely that there’d be even less ATX splitting than with an accurate reward formula.
      • The smaller miners are unhappy because the large miners get an unfair advantage (and the large miner have other inherent advantages due to economies of scale).
  • It’s conservative to err on the side of giving a smaller amount of extra weight relative to what the miners deserve.
    • Because we want to encourage small miners to partcipate.
    • In the worst case it’d be the same as without a reward formula that compensates for wasted ticks.

Practical underestimate

  • Right now there isn’t a reward formula that compensates for wasted ticks
    • In the spectrum between overestimate and underestimate, we now err on the side of giving 0% extra weight for wasted ticks, which is the extreme in terms of favoring small miners.
      • So even the big miners prefer to artifically become small miners by splitting their ATX.
  • Suppose that a typical miner with the minimal 256 GiB storage requires 30 minutes for PoST proof generation (i.e., k2pow computation and the linear pass over the storage).
  • By naively extrapolating, the large miner with 32 TiB storage will need 128\cdot30=3840 minutes out of the 14\cdot 24\cdot 60=20160 minutes of the epoch, which is 3840/20160=19% of the epoch.
    • As discussed above, the miner with 32 TiB is likely to waste significantly less than 3840 minutes (47 hours) on PoST proof generation, by investing more in hardware (without such higher costs the 47 hours of wasted ticks figure should be approximately correct).
  • Instead of 19% extra weight for 32 TiB, the reward formula should use a more conservative estimate that errs (on purpose) in favor of small miners.
  • It’s reasonable for the reward formula to give 10% extra weight for 32 TiB, 5% extra weight for 16 TiB, 2.5% extra weight for 8 TiB, and so on.
  • The reward formula shouldn’t disincentivize splitting larger storage sizes (the maximum extra weight should be for 32 TiB), because of the need for 6 bytes (instead of 5 bytes) per index when the storage is larger than 32 TiB, and because of the risk of pooled mining.
    • In fact, we can be even more conservative by setting the maximum in the reward formula to be 16 TiB (that earns 5% extra weight), without a disincentive for splitting one 32 TiB ATX into two 16 TiB ATXs.

The risk of pooled mining

  • Imprudent miners may participate in 32 TiB pool by initializing their labels according to the pubkey of the centralized pool identity,
    • For example, there are 128 members of the 32 TiB pool, each member has 256 GiB that she initialized with the pool’s pubkey, and in every epoch the pool asks each member to perform a linear pass over her local 256 GiB and send the successful indices (if any) to the pool.
    • Since the reward formula gives 10% extra weight for 32 TiB, there’s a higher reward amount to share among the pool members.
  • Technically, this scheme doesn’t need to involve remote distinct individuals as the pool members.
    • If the “pool” operator has her own 32 TiB, that’s split into (say) 128 local computers with 256 GiB each, then she can do the same as a pool with remote participants, and in fact be much more efficient (and will need much less than 128 computers).
      • This allows the operator to lessen the wasted ticks, by performing linear passes (of the PoST proof generation) in parallel.
      • Such a setup is legitimate and encouraged.
    • The pool with distinct remote members allows the operator to earn rewards without having any significant expenses of her own.
      • The remote pool members pay a fee to the operator (out of the earned reward), and receive what’s lefft of the earned reward.
  • Even without a reward formula that compensates for wasted ticks, there are reasons for such a pool (in which the PoST initialization is done by remote members bu only the centralized pool operator has access to the rewards):
    • If Alice has only say 128 GiB of free space, then she cannot create her own standalone ATX (because there’s a hard protoocl rule that requires a minimum of 256 GiB), so instead she can join this pool
    • If Alice has 256 GiB then she still wastes approximately 0.1% of the epoch’s ticks on PoST proof generation, so she can instead split her storage into say 8 portions of 32 GiB each and participate in 8 pools that waste 0.0125% of the epoch’s ticks on PoST proof generation.
    • There’s a fee according to size of the broadcasted ATX (which is effectively the same for all ATXs, regardless of their amount of storage). If the gas price is high then this fee can be significant. If Alice has 256 GiB then she can become a member of say 32 TiB pool (the pool creates a single ATX and pays the broadcasted size fee only once).
    • If Alice has large storage that she’d need to split and fit into multiple PoET phases, she might be better off participating in multiple pools (one pool per PoET phase), in particular if the centralized operator Bob allows her to pay a single fee for participating in his multiple pools.
      • The centralized operator can optimize the members that each pool should be comprised of, to maximize the profits.
    • The pool operator may subsidize the members by offering them a higher reward than they’d earn on their own, in order to obtain more centralized power.
  • Such a pool is flimsy because it’s easy to “attack the attacker”:
    • Attack #1: the attacker joins the pool with many Sybil identities that declare that they have terabytes of storage by actually don’t have any storage whatsoever.
      • To mitigate this attack, the pool can require its users to register by providing a treeless-PoST proof (using a fresh random challenge that the pool operator picked) that they indeed have the storage that they declared, before being accepted as a legitimate member.
      • If the pool doesn’t require the “time” component of the PoST proof for a legitimate registration, then it’s easier for an attacker to join with many Sybil identities by re-using space.
      • This registration process is likely to take a significant amount of time, and only after the registration process is complete the pool operator can submit an ATX to a PoET server and wait 2 weeks before starting to participate (the registration process may cause skipping an epoch even if the pool doesn’t require the “time” component of the PoST proof).
    • Attack #2: the attacker Alice joins with multiple identities, performs legitimate registration for each identity, and later frees up her storage and claims in the subsequent epochs that she failed to find successful indices during her linear passes.
  • In principle, we should design the protocol according to sensible fundamentals, and let the chips fall where they may.
    • For example, charging a fee according to the broadcasted size of the ATX is sensible because the entire network needs to transmit/verify and store forever the ATX data.
      • If the market-based gas price is high, then this fee may make miners believe that it’s more lucrative to participate in a pooled mining scheme.
      • Still, this fee is sensible, so the protocol should do its best to disincentivize pooled mining in spite of this fee.
    • Likewise, the reward formula that compensates for wasted ticks is sensible, because it facilitates a fair reward distribution.
      • Pooled mining should still be disincentivized (this is done in part by choosing x that purposefully errs on the side of underestimating the wasted ticks weight, as discussed above).
  • If the pool charges say 3% fee from its users, then the net reward (that the miner earns by using the pool) is likely to be unattractive from the point of view of rational miners.
    • Especially if we decide that the the maximal extra weight is 5% for 16 TiB.
  • Fundamentally, we should rely on long-term rational miners to execute the protocol.
    • Such miners wouldn’t want to perform PoST initialization using pubkey that they don’t have control over.

Implementation

  • Let x denote the maximal extra weight factor.
  • Let y denote the maximal space units that get extra weight.
    • Reminder: one space unit is 64 GiB
  • For 10% extra weight for 32 TiB, we’d use x=1.1 and y=512
    • So it’s 5% extra weight for 16 TiB ATX, 2.5% extra weight for 8 TiB ATX, 1.25% extra weight for 4 TiB ATX, and so on.
  • If the ATX has z space units, then the extra weight factor is \text{max}(z\cdot x/y, \ x)
    • For example, if z=511 then the extra weight factor is 1.1\cdot 511/512
  • When we calculate the rewards in the UCB:
    • Briefly: instead of using \text{alice\_weight}/\text{total\_weight} in the expression that determines Alice’s reward, it’d instead be (\text{alice\_weight} \cdot \text{alice\_extra\_weight\_factor})/\text{adjusted\_total\_weight}
    • Suppose that Alice,Bob,Carol are the rewarded identities in the UCB.
    • Denote by f_a the extra weight factor \text{max}(z\cdot x/y, \ x) of Alice.
    • Denote by f_b the extra weight factor \text{max}(z\cdot x/y, \ x) of Bob.
    • Denote by f_c the extra weight factor \text{max}(z\cdot x/y, \ x) of Carol.
    • \text{adjusted\_total\_weight} = \text{alice\_weight}\cdot f_a + \text{bob\_weight}\cdot f_b + \text{carol\_weight}\cdot f_c
    • Alice’s adjusted relative weight is \text{alice\_weight}\cdot f_a / \text{adjusted\_total\_weight}
    • Bob’s adjusted relative weight is \text{bob\_weight}\cdot f_b / \text{adjusted\_total\_weight}
    • Carol’s adjusted relative weight is \text{carol\_weight}\cdot f_c / \text{adjusted\_total\_weight}
2

Let me also summarize the landscape of our anti-splitting proposals (the links here have further details but they’re non-public for now):

  1. Increase k2 and thereby lower the k2pow difficulty: the easier k2pow decreases the expected time and variance of PoST proof generation in each epoch.

  2. Increase the k2pow data size and thereby reduce the k2pow variance.

    • There’s no reasonable (non-VDF style) scheme to achieve this (so far).
    • Even if there was, the effect would be less significant relative to the other proposals.

  3. k2pow delegation, which is a win-win.

  4. Reward formula that compensates for wasted ticks, which is superior to our current reward formula (as explained in the OP).

  5. Phased PoET, which is a win-win.

    • For example, if there are 14 PoETs such that one PoET starts on each day, then a miner that fails to produce a proof can re-try in the next PoET phase and thus lose only 1/14 \approx 7\% of the reward.

  6. PoET with early exit points, which is a win-win.

    • The prudent miner can start from an early exit point, and then her PoST proof generation succeeds with a higher probability.
    • The early exit points are also essential as an anti-drift mechanism.

  7. Rational reporting of the storage size: https://community.spacemesh.io/t/tree-free-post-in-more-depth/53/12

    • Possibly by using k2max scheme or variable-quality-with-fixed-k2 scheme.
    • This is a win-win, because it reduces the adversarial advantage relative to the honest miners, which means that we can lower k2 and/or k2pow.