Proof of work and PoST proof generation

Research
1

Our goals for PoST proofs are that 1. we require each smesher to perform a single read pass over all of their PoST data once per epoch, 2. that, other things equal, they be able to easily construct a concise, non-interactive proof of having done this that they can broadcast to the network to prove ongoing eligibility, and 3. that the adversary not be able to “cheat” by being able to generate such a proof without actually having stored (or regenerated) all of the PoST data they claim to have, i.e., that they not be able to successfully generate a valid proof for a larger amount of storage than the data they actually store.

The basic proof generation algorithm is as follows (see also: Summary of suggested protocol for PoST proof / verification):

Parameters:

  • hash_threshold: hash output must be lower than this value in order to be valid
  • num_required_labels: minimum number of labels required to pass the hash_threshold for a given nonce to generate a valid proof
  1. Iterate over sequential nonce values [0…]
  2. Per nonce, perform a single pass over all PoST data (i.e., each label in the tree). Hash each label along with [PoET challenge, nonce] and check if the output is below a certain threshold.
  3. After finding num_required_labels labels, stop iterating and construct a proof. The proof contains the [PoET challenge, nonce] and the set of matching labels.

Note that, in practice, a smesher can and likely will check many nonces in parallel. In general this algorithm is highly parallelizable and different portions of the tree can also be checked in parallel.

The parameters are chosen such that a home smesher running on modest hardware over a small number of storage units needs to check on the order of a few hundred nonces in order to find num_required_labels matching labels. This process (which is of course probabilistic) should take no longer than the PoET cycle gap, i.e., a few hours, in 99% of cases—in other words, except in rare cases where they get unlucky, a home smesher on modest hardware should have plenty of time to run this algorithm, successfully generate a valid PoST proof, publish it to the network, and submit to the next PoET round before it begins. For detailed math on choosing these params, see Analysis for PoST Parameters.

One problem with this design is that an adversary with a lot of compute power can cheaply check many more nonces in parallel than a home smesher. If they check enough nonces they will eventually find one that allows successful generation of a valid proof of having stored N space units even though the adversary has stored a substantially smaller fraction of the data, say, 50-80%. In this way it represents a “back door” way for such an adversary to partially substitute compute for storage (“back door” because it doesn’t involve regeneration of the data itself).

Our proposed solution to this problem is to make nonces expensive. In other words, a small amount of work must be performed for each nonce that’s tried and proofs of work to this effect must be included in the PoST proof. The upside here is that, assuming the amount of required work per nonce is low enough, the honest smesher (who indeed has all of the PoST data they claim to have) only needs to do the work for a few hundred nonces, whereas the dishonest smesher (who has less data than they claim) needs to perform orders of magnitude more work for an arbitrarily large number of nonces (parameterizable). The downside is that it requires all smeshers to do work, on top of the already resource-intensive process of generating PoST proofs and processing many ATXs each epoch that require validating these proofs.

Our proposed solution to this problem is to have the PoET server perform a modest amount of work, upfront and amortized among many smeshers, and to provide a PoW to this effect along with the PoET proof. The PoET server runs on powerful hardware and can do this work far more efficiently than most home smeshers. What’s more, the work can be done after the generation of the PoET proof is completed, during the cycle gap, when the server is otherwise idle.

The PoET server will perform PoW to validate a number of nonces that would allow a home smesher with up to ~4tb of storage space to successfully generate a PoST proof in 99% of cases. In other words, many smeshers can utilize the same PoW, which is in no way bound to a specific smesher ID. We find this number reasonable due to back of the envelope math: we expect the existing PoET servers, even without changes to hardware, to be able to perform this work in under an hour; and, based on HDD read speeds, 4tb is about the maximum amount of space that a smesher can read from a single disk during a cycle gap, i.e., it represents the effective maximum size of a single smesher’s data commitment given the current set of parameters (and without specialized hardware).

Note that the adversary can also grind on the PoET challenge (part of the input to the hash function used to find successful labels in the process of generating the PoST proof), since our PoET construction is currently very grindable. Changing a single label near the end of the proof of sequential work changes the PoET challenge without affecting the validity of the PoET proof itself. We considered designs to make the PoET challenge ungrindable, such as needing to “seal” the PoET proof itself using PoW, but decided that it’s unnecessary on top of the other ideas presented here.

This design has the advantage that the difficulty and thus the cost of the required work scales linearly with the total committed storage space; if this were not the case, it would still be more economical for the adversary not to store all of the data.

Note that “industrial” smeshers with >> 4tb of committed storage will still need to perform PoW to validate additional nonces in order to generate valid PoST proofs. Home smeshers will not need to do such work 99% of the time, but 1/100 times they will get unlucky, the set of valid nonces proven by the PoET won’t be sufficient to generate a valid proof, and they’ll need to perform additional PoW. This should take a home smesher with a small number of storage units (say, up to 1tb) running on a modestly powerful system no more than 10-20 minutes.

If we’re unable to add this functionality to PoET prior to genesis then all home smeshers will need to perform PoW once per epoch, at least until this functionality has been added to PoET.

It’s also true that this design incentivizes smeshers with > 4tb of storage to split their identities so that each falls below this threshold, meaning that most of the time they don’t need to do PoW on their own. However, we feel that the 4tb size, while large enough for basically all home smeshers, is small enough that it would be impractical for industrial smeshers to split identities with a very large amount of storage space (on the order of petabytes) into, say, hundreds of units and manage each separately. (They may still want to split large identities for other reasons, such as compartmentalizing disk failures).

In general we feel that this design does not change the existing trust model of the protocol that already exists with PoET. Smeshers trust the PoET server to perform work on their behalf and to honestly provide proofs of that work; they can (and do) submit to many PoET servers in order to minimize the exposure to a PoET server that acts Byzantine, and they are also free to run their own PoET server or do the work themselves if they choose.

With respect to the specific hash function chosen for this PoW, the prime candidate is RandomX from the Monero ecosystem but we haven’t made a final decision yet.

1 Like
2

That’s true as long as we offer subsidized k2pow by our own PoET server, but in the future this issue goes away because the k2pow work will have to be paid for.


But the first question is whether we actually want k2pow that’s not bound to a specific identity.

  • If each k2pow is only valid for the smesher id that computed this k2pow, then it’s a clean protocol, and:
    ** It’s a protocol that’s better in terms of decentralization, because the liveless of each honest miner doesn’t depend on waiting for a response (from a 3rd party) that might never arrive.
    ** But it’s a protocol that’s worse in terms of greenness, because the k2pow computations are done by all the miners instead of being done by a single entity (or relatively few entities).
  • Note that the k2pow issue resembles the sequential PoET work, but it’s somewhat different:
    ** For the sequential PoET work there can be a single output that’s valid for all the miners.
    ** For k2pow, we need different outputs depending on the storage size of the miners.
  • The protocol in which k2pow isn’t bound to a specific identity is significantly less clean, for example if Alice and Bob and Carol are large miners with 32tb each, then Alice can compute k2pow and sell her output to Bob, and then Bob can recoup some of his money by selling Alice’s output to Carol, etc.

I think that the best approach is to bind k2pow to the identity that computed it but allow other identities to make use k2pow that’s not their own for a fee, so that the payment (to the identity that computed the k2pow) is enforced by the core consensus protocol. For example, if Alice computed the k2pow and Bob uses Alice’s k2pow in his PoST proof generation, then 10% of Bob’s ATX reward (or first ballot reward) of the epoch goes to Alice.

3

I’ve been thinking about this more — now I’m not sure it works at all in the simple version. What prevents an adversary that stores only 50% of its claimed data to create a huge number of identities and amortize the PoW cost across them?

It might be possible to solve this by burning the payment for outsourced PoW (or at least part of it). This would mean an adversary that has to do a huge amount of PoW can either choose to amortize the PoW, but burn a lot of funds, or do the PoW separately…

4

@talm yes you’re right, another way to say what you said is that if the adversary has say 32tb storage in total then she can split her identity into 128 identites of the minimal 256gb each, then grind to create a huge number of k2pow outputs, and “sell” all of these outputs to herself (i.e., whenever one of her identities is using one of these k2pow outputs, the core consensus protocol will indeed enforce payment to her “master” id that generated all the k2pow outputs, but it’d just be a dummy transfer of money among her own accounts). If she instead just used a single 32tb identity then the k2pow difficulty threshold that she;d need is 128 greater than the difficulty of 256gb identity, so computing the k2pow with just her “master” 256gb id would be much more beneficial for her.

The full solution as you said is that the core consensus protocol will burn a portion of the payment, and transfer the remaining portion to the id that created the k2pow (as the incentive/reward). This partial-burn approach isn’t new, it has been used in PoStake protocols and other protocols before.

5

Outline of the core protocol for delegated k2pow:

  1. k2hash includes the miner_id and miner_fee arguments:
while k2hash(k2pow, ch, nonce_group, miner_id, miner_fee) >= K2_DIFFICULTY
  k2pow := k2pow + 1

  1. Every ATX includes k2pow_fee field field that specifies the proportional payment that this miner requests for using her k2pow
    ** This field can be 1 byte, where for approx 50% it will specify k2pow_fee=127 which implies 127/255, but for more precision we can use 2 bytes (which is enough precision in this context) where k2pow_fee=32767 for approx 50% will implies 32767/65535

  2. Every ATX may also need to k2pow_id field that specifies the miner_id that created the k2pow
    ** If we use 2-byte precision for k2pow_fee then we can use the MSB of k2pow_fee to specify whether k2pow_id should be included in the ATX
    *** If the first byte of k2pow_fee is 0xFF then k2pow_id is excluded from the ATX encoding, implying that k2pow_id is the same as the miner_id that created this ATX (the implicit k2pow_id and explicit k2pow_fee will be given as input to k2hash for verification).
    *** If the first byte of k2pow_fee isn’t 0xFF then we deserialize two bytes as uint16 and bitwise-AND them with 0x7FFF and divide by 32767 to get the proportional fee, and also deserialize the k2pow_id next.

  3. Both k2pow_fee and k2pow_id fields don’t need to be directly in the signed data of the ATX, instead only k2pow itself is in the signed data, and k2pow_fee,k2pow_id are aux data that k2pow commits to.
    ** This is similar to the PoET proof where the ATX signs only the hash of the PoET proof (the preimage of this hash is sent only when requested), but here even if only our PoET server computes k2pow (for all the miners) it won’t be the same as the PoET reference because there are multiple nonce_groups (for example if our PoET computes 8 nonce groups for 128 nonces in total, then there are 8 different k2pow hashes and for each of the 8 we’d want to store only one master copy and deduplicate the rest).
    ** It’s still worth it to have the efficient encoding of k2pow_fee,k2pow_id using the aforementioned 0xFF byte (rather than relying only on deduplication, which won’t be effective anymore if there’s a market of k2pow providers), since k2pow_fee,k2pow_id will need to be sent for any ATX that needs to be verified in a syandalone fashion. Alsi it’s better to feed shorter days to k2hash() in each attempt.

  4. When miner Alice performs PoST proof generation, she can either compute the k2pow herself and then the k2pow_id of her ATX will be her own alice_id and she’d keep her entire reward, or she can use say Bob’s k2pow and then the k2pow_id field of her ATX will be k2pow_id=bob_id
    ** Let BURN_K2 be immutable protocol parameter that’s in consensus, for example BURN_k2 = !0%
    ** Let R denote the reward that Alice is supposed to earn for her first ballot of the epoch (or for her ATX reward after we implement ATX rewards).
    ** If k2pow_id != alice_id then R*BURN_K2 is burned and R*(1-BURN_K2)*(k2pow_fee&0x7FFF)/32767 is transferred to k2pow_id (the new reward amounts for alice_id and bob_id aren’t explicitly recorded in the UCB, specifically Bob’s identity might not be listed in the UCB at all).
    *** For every ballot b of Alice, if the voting weight of b is w_b assuming k2pow_id == alice_id , then when k2pow_id != alice_id the voting weight of b becomes w_b * BURN_K2

  • Side note: it’s problematic to put k2pow_fee only in the first ATX of the identity (and exclude k2pow_fee from the k2hash args), both because of dishonest miner who might double-sign and cause consensus failures, and because we want to allow miners to quickly modify the fee that they charge in a costless fashion, and because we don’t want to perform the extra query in each ATX verification.

Outline of our PoET with subsidized k2pow:

  1. Let POET_K2MAX denote the K2 difficulty that corresponds to the maximum ATX storage size that our PoET subsidizes, for example 2tb max storage.
  2. Let POET_K2NONCES denote the number of nonce groups that our PoET subsidizes, for example POET_K2NONCES=8 for 128 nonces (8 groups of 16 nonces each).
  3. After the sequential work is done, the PoET server immediately publishes it and begins to compute the POET_K2NONCES values of k2pow with POET_K2MAX difficulty for each value.
  4. After the POET_K2NONCES are computed, the PoET server publishes the POET_K2NONCES values.
6

As @talm pointed out today, it’s superior that we also reduce the voting weight of an ATX that uses k2pow of another identity, to mitigate attacks by an adversary who’s willing to forgo rewards.

Note that we should still burn the reward (rather than give the reward proportionally according to the reduced weight), otherwise if say all the miners are using delegated k2pow then none of them loses money (and if say there’s a single delegator Alice and everyone else uses her k2pow then Alice recoups the reward from the delegated identities due to the proportional reward formula).

So I edited the above spec in step 4 with *** to reflect this.

7

we can’t issue rewards directly to the miner public key. miner_id either needs to have an atx, but this is not needed in this case. or miner_id should be an account address that vm can understand

8

@dmitry per https://community.spacemesh.io/t/cost-of-raw-storage/89/34 the miner_id and account_address should be linked (directly or with extra rules). Anyway, for k2pow delegation it’s indeed good to use an account_address, and the protocol needs to lookup whether the ATX has the same coinbase (reward address) as this account_address (if they’re different then some of the reward must be burned according to the BURN_K2 protocol parameter, if they’re the same then no reward gets burned at all).

9

Tal noticed that the above k2pow delegation mechanism is too naive and thus broken in terms of security:

  • We indeed force the miner Alice to pay+burn an appropriate fee the k2pow that was generated (by someone else) on the single nonce that she ends up using, but we don’t enforce anything regarding all the nonces that are available to her while she’s performing the linear pass for the PoST proof generation.
  • This means that Alice can try a very high number of nonces (using k2pow values that she didn’t generate herself) during the linear pass, and therefore she can keep a relatively small portion of her storage and still succeed in the PoST proof generation.
    • Alice’s payment for the single k2pow (that she ended up using) is small relative to her savings in terms of storage that’s freed up.

This situation is in fact even worse than what Tal described:

  • Suppose that all the identities that generate k2pow (as a service that others can purchase) are totally honest.
  • But there’s a free market for selling k2pow values, so there are many identities that wish to sell their k2pow.
  • The rational Alice can use these many k2pow values (from the different honest identities) during her PoST proof generation, and thus keep a relatively small portion of her storage.

The high-level idea of what I think is the best solution:

  1. Require the miner to register in advance to the k2pow delegation service.
    • This ensures that any miner can use k2pow values that were generated by only one specific identity.
  2. Disallow many nonce_group indices for any specific challenge.
    • This ensures that any honest identity that generates k2pow can only generate a few k2pow values.
  3. Enforce a malfeasance proof for an identity that generated k2pow for more than one challenge.
    • If a dishonest identity generated too many k2pow values, and these k2pow values ended up being used by valid ATXs, then it will be detected and redressed.
  • The combination of the above three properties imply that a rational miner Alice won’t enjory an advantage (with regard to PoST proof generation) due to k2pow delegation, because Alice will be able to use only the limited amount of k2pow values that a single identity generated.

The full spec:

  • Each miner Alice registers in advance the single identity (account address) whose k2pow she may want to use.
    • It’s healthy for Alice to assume that she needs to be ready to perform the k2pow computation on her own in certain situations.
      • Specifically, if single k2pow id that Alice registered in advance is the id of a PoET server, and in the last epoch Alice also submitted her ATX to backup PoET servers in case it turns out that her preferred PoET server didn’t produce the PoSW proof, then she will need to perform the k2pow herself in the case that her preferred PoET server died.
  • The protocol limits the allowed nonce_group indices, for example if 160 nonces is the maximum (for success probability that’s higher than 98%), then the only nonce group indices that are allowed are between 0 and 9 (for 10 nonce groups and 10x16=160 nonces in total).
    • This restriction is only with regard to delegated k2pow.
      • If Alice generates k2pow for herself, she is allowed to use any arbitrarily high nonce_group index.
        • This is natural in case Alice fails in the linear pass of the PoST proof generation, and wishes to perform another linear pass with fresh k2pow values (without grinding on the PoET output).
  • If there’s evidence that an identity Eve performed k2pow on two PoET outputs (two ch challenge values) then this constitutes a malfeasance proof::
    • The id of Eve is canceled.
    • Additionally, it’s possible ot require any account that wishes to delegate k2pow to always have at least X coins balance, and confiscate these X or more coins upon evidence of malfeasance.
    • The ATXs that used the k2pow of Eve are still valid, but won’t be listed in honest tortoise proposals (pblocks) to receive ATX reward (which is say 10% of the total reward in the epoch), and pblocks that list such ATXs are voted against by honest hare participants.
      • Prudent miners should be careful not to use k2pow of an untrustworthy identity.
      • This is par for the course with k2pow delegation, otherwise a single malicious identity will be the only one who’s punished after she grinds on PoET outputs and provides many nonces to many other ATXs.
  • The k2pow values that Eve generates must contain data that only Eve is able to create.
    • Otherwise, somebody else can grind on the PoET and generate k2pows values that are bound to Eve’s identitiy.
    • One simple way to do it is that the ATX must include ed25519 signature by Eve on ch, but only in an ATX of someone other than Eve (the ATX of Eve herself doesn’t need this ed25519 signature).
  • Naively, the above would still allow the rational miner Alice to double the amount of nonces that are available to her during the PoST proof generation:
    • Alice will register in advance to obtain 160 nonces from Eve, but also generate (say) 160 nonces herself, and use the 320 nonces during the linear pass.
      • Effectively having 160 nonces for free.
    • The non-naive protocol rules:
      • If Alice isn’t registered to k2pow delegation (meaning that she must generate k2pow on her own), then she doesn’t pay any fees for the k2pow in her ATX.
      • If Alice is registered to k2pow delegation (by specifying e.g. Eve’s account), and ends up using her own k2pow in her ATX, then she burns a fee that’s double the amount that she’d burn by using Eve’s k2pow.
        • Instead of doubling the burned amount, it’s possible to take an accurate fee by including Eve’s k2pow in Alice’s ATX, or take the median k2pow fee of the previous epoch.
      • Thus, if Alice uses the 160+160 nonces, then she already paid (using energy consumption) for her own 160 nonces, and will pay for Eve’s 160 nonces if she ends up using them.
  • The original spec didn’t tackle how to pay Eve for all the nonces that she provided.
    • Eve maybe produced k2pow values for only 64 nonces, or perhaps 128 nonces, or the maximum 160 nonces, but when Alice uses a single nonce_group of Eve’s it’s unknown how many k2pow values Eve has actually given.
    • The simplest way to tackle this is to assume a free market in which the identities that produce the k2pow values are supposed to give the maximum (say for 160 nonces), and if an identity gives less than the maximum then it incentivizes miners to register to a competitor identity.
10

should the miner register every epoch? and how does the registration happen? in miner’s previous atx?

Enforce a malfeasance proof for an identity that generated k2pow for more than one challenge

the identity that generates the k2pow also needs to a valid ATX / miner id in order to sell the k2pow it generates? does that mean that people may generate minimum unit identity just so they can sell k2pow?

11

I think that it’s best that the data (that’s committed via a hash) that the miner submits to the PoET will specify the account address of the k2pow delegation identity (if this account address is blank then the miner must compute k2pow on her own, we need at least 1 bit flag to encode whether it’s blank). The advantage of this is that the miner can use k2pow delegation even for her first ATX (i.e., she will never need to compute k2pow on her own).
It’s possible to optimize by using flag=0 for blank, flag=1 for explicit account address, and flag=2 to lookup (recursively) the account address according to the miner’s previous ATX.

We can require valid ATX and/or the “X coins balance” rule (mentioned above).
There’s something natural about having a valid ATX, because the identity of this valid ATX can use her k2pow for free (and then delegate it to others), but “having” doesn’t nessecarily imply “requiring”.
To keep it simple we can require only the “X coins balance” rule, so that for example a PoET server that also offers k2pow delegation service won’t need to have its own valid ATX in every epoch.

12

The protocol limits the allowed nonce_group indices, for example if 160 nonces is the maximum (for success probability that’s higher than 98%), then the only nonce group indices that are allowed are between 0 and 9 (for 10 nonce groups and 10x16=160 nonces in total).

The nonce_group is already limited to 0-255 in the k2pow algorithm. The input to k2pow is [7B k2pow_nonce; 1B nonce_group; 8B challenge; 32B minerID].

Given that Eve can only create the k2pow for 1 Poet proof, we would probably need to create a service that first gathers proofs from all known poets, selects the best proof, and creates a k2pow for it.

It would mitigate the problem that the k2pow is created for a different poet proof than Alice wants to use (because it’s always the best available poet proof and it makes no sense for Alice to use a different poet proof). Assuming that the Eve service knows about the best poet service.

But still, the Eve service is the single point of failure. When it fails, all smeshers that depend on it will need to do the k2pow themself. If there are a lot of them (likely it would be most of the smeshers?) and they are not ready (for example, their HW is not good enough) it might cause degradation in the network because they will not create POST on time (they will fall through to the next phase shift if there are phased poets).

1 Like
13

@Bartosz If/when we upgrade to support k2pow delegation this input will need to be modified (to include miner_fee etc.), but the 1 byte for nonce_group should remain as it is of course (as mentioned above, if the miner is unlucky and needs to try more k2pow values on her own, then she should have “unlimited” nonce_group attempts). The 256x16=4096 nonces that the 1 byte allows isn’t “unlimited”, but in practice it’s way more than what anyone would ever need.

Yes, this is a good idea.

Technically speaking, this “single point of failure” (SPoF) is stricly better than not having this SPoF, because with this SPoF all the miners by default aren’t using k2pow delegation (just as the situation is today) and they can continue not to use k2pow delegation atll if that’s what they wish, but if a miner does wish to use this SPoF then she can and then in the worst case she should be ready to perform the k2pow on her own.

Practically speaking, you may be right in case miners become complacent and just assume that the k2pow delegation will always work, and when it suddenly doesn’t it turns out that they fail to do it on their own.
Therefore, it’d be nice if our software offers by default a simple test to the user to benchmark whether her hardware indeed generates the minimal k2pow in approximately 150 seconds or less on a single core.
It shouldn’t be regarded as a big deal because it’s automatic behavior of the miner’s software without any human intervention (if the k2pow delegation service is unresponsive beyond a deadline then the software starts to generate the k2pow on its own).

An alternative to all of this is to say that k2pow is easy enough for small miners (only takes a few minutes at the most), and for sharks it’s a relatively a minor aspect of their entire opearion, so it’s ok not to have k2pow delegation at all.

But again, offering the ability to use k2pow delegation is strictly superior to not offering it.
I think that the important thing is to optimize the happy flow, in which mostly everyone will use k2pow delegation without worrying about their CPU usage, and the entire ecosystem is significantly more green. In the unhappy flow there’s the danger that things will go wrong due to complacency, but then things will recover (we have self-healing) and maybe the complacent miners will learn their lesson.

The only other alternative (that we know of so far) is to increase the complexity of systemic parameters, i.e., much greater ATX size and verification complexity (instead of the 37 scrypt values that we have now, and maybe we will need k3 too). However, it’s nicer that each miner will do something that’s a little more costly locally on her machine, and then the entire system’s communication/storage/verification complexities can be low (in particular, the happy flow is much nicer).

14

so if we don’t enforce the k2pow generator to have an valid ATX, how do we generate a malfeasance proof that’s verifiable? and this means now and malicious identity can be a coinbase address (instead of a public key)?

15

I suppose that the simplest way is a special transaction (that’s put into the UCB like any other transaction) that confiscates the X (or more) coins of the dishonest account.

16

The above solution is insecure against an adversary that creates an alternative history. This is because we can only cancel the identity of the single creator of the k2pow, we cannot cancel those who buy the k2pow (because if we did then this single identity could equivocate in the future and thereby cancel many honest identities), and while denying the rewards in the current timeframe is indeed a countermeasure against imprudent miners that buy k2pow from a malicious identity, this countermeasture doesn’t work against an adversary that creates say an entire alternative history in secret.
Obviously we shouldn’t use this solution, because it’s pointless to make other parts of the protocol secure against an adversary (with 1/3 of the total spacetime resources) but be vulnerable to the such an adversary just because of k2pow delegation.

I think that the following is the only way to do k2pow delegation securely: