PoSt Stamps: proposal for removing VDF

[nicola]

PoSt Stamps

Terrible Interactive PoSt

Intuition: A miner submits a PoSt proof at every block i, using the seed at block i-1.

Problem: The on-chain footprint is 192bytes * number of miners, this is completely impractical.

Next steps: Can we avoid everyone submitting a proof at every block?

Improvement 1: We can submit a commitment to the proof at every block, and generating a snark that proves that all the commitments open to correct proofs! (The on-chain footprint is still very impractical 32bytes * number of miners at every block)!

Improvement 2: We can submit commitments to the proof at every block to a special node which collects all the commitments and puts them in a merkle tree. At the end of the proving period a miner generates a snark showing that at every block they had a valid inclusion proof for their proof. (The on-chain footprint will be a minimum of 32 bytes for the entire network!)

PoSt Stamps

• Stamp: A PoSt stamp Stamp_t is a commitment to an online PoRep proof (a single PoSt epoch).
• Aggregator: A PoSt Aggregator is a special node that collects

Intuition:

• At every block:
  • Each miner runs a single PoSt step (online Proof of Replication) using the seed from the previous block
  • Each miner submits a stamp to the Aggregator
  • The Aggregator build an accumulator and sends an inclusion proof to each miner
• After the proving period:
  • Each miner submit a SNARK that prove that there is a commitment at every block (by proving that it's included in the accumulator block) and that every commitment opens to a correct Proof of Spacetime step

New problems:

• What if the aggregator is offline? Ideally each miner sends their PoSt to multiple aggregators and multiple aggregators submit the proofs on chain.
• What's the incentive for an aggregator to aggregato proofs? Unclear!
• What if an aggregator does not include a proof? A miner should make sure they send it to multiple aggregators :(

[whyrusleeping]

Relevant calculator: https://beta.observablehq.com/d/2c5e782ba61cc522

[lucaniz]

Candidate construction written down with more details during Research Week. Next step is formalizing in the doc.

[whyrusleeping]

You can't guarantee anything will be in 'every block' without hinging the blocks validity on it, and to do that, everyone would need to know who the miner of a given block is before they mine the block, which defeats the point of us having a secret election.

Other questions:

• Who will be an aggregator?
• Why will they be aggregators?
• How does the aggregator get their aggregated stuff into the block?
  • Is it a transaction? Miners can choose to screw with aggregators and delay the inclusion of those proofs (if there is only one aggregator, then the miner wouldnt do that because their proofs would be in that thing too, but only having one aggregator means the aggregator can trivially censor and screw over miners)
• If submitting the aggregate posts is done via a transaction, does the aggregator just have to pay the fees? Do the miners sending them things to aggregate pay them for this in some way?
• What if an aggregator chooses to ignore a miner post?
• does missing one 'stamp' invalidate the miners eventual final post submission?
• there are 2880 blocks per day. If the proving period is one day, then the miners posts snark will have to prove that many merkle paths, and also reference which of the accumulator roots contains the post stamp at each point (Which needs to be a public input, and thats gonna get really expensive)
• has anyone considered the bandwidth costs here? It sounds to me like every single miner is going to be broadcasting a hash at every block, the aggregators are going to be responding with merkle proofs to each miner at every block, and the aggregators are going to be broadcasting a transaction containing that new merkle root at every block. It doesnt seem insane at first glance, but its still significant.

This is a neat idea, but it ignores a lot of the things that make system design in this space hard. There are so many edge cases here that need to be considered, and so many questions that need answers. I'm willing to discuss this more, but the proposal needs a significant amount of additional detail before we can have meaningful discussions about it.

[nicola]

Some notes here after some conversation on different media:

Main attack to the construction:
PoSt Samp is useful to decrease the on-chain footprint for PoSt. However, the security of PoSt stamp depends on Tpoll, the time between two stamps. If Tpoll is ~10mins, every ~10mins every miner must have submitted their commitments to an aggregator and have their aggregated commitments appearing on chain. If someone attacks the network and is able to censor transactions (e.g. a cartel of miner) for more than ~10 minutes, then everyone either looses their power, or they will have to report late post submissions (which sounds like a catastrophic event).

In short, PoSt Stamp is a great idea only if Tpoll is larger than any Tmax time for which an attacker can control the network.

Answers to some of Why's questions:

Who will be an aggregator node? and Why?

Some nodes will be altruistic (we could be running a node), some nodes will be paid via payment channels.

What if an aggregator node chooses to ignore a miner?

Miner picks a different aggregator

Does missing one 'stamp' invalidate the miners eventual final post submission?

No, the miner will have to post on chain a proof that prove correct work until that point, and they will be penalized for late post submission.

If the proving period is one day, then the miners posts snark will have to prove that many merkle paths, and also reference which of the accumulator roots contains the post stamp at each point (Which needs to be a public input, and thats gonna get really expensive)

These would be just a few more merkle trees in the proof, not concerning.

Has anyone considered the bandwidth costs here?

Note that miners don't talk to aggregators at every block, but every Tpoll

Is PoSt stamp any useful?

If Tpoll is short, PoSt stamp is not secure, if Tpoll is large, then it could be a really great solution.

Note that we could be using this in conjunction with the VDF construction in order to reduce the onchain footprint. The VDF would indeed be a tool to increase Tpoll.