Null Block spacing

[whyrusleeping]

In an earlier understanding of EC, we (really just me, but nobody corrected me) said that null blocks could be created by simply incrementing a counter. Further research pointed out that we need to ensure that the null blocks have the same delay as a normal block, i.e. you can't mine a block on top of a null block in the same time it takes to mine a block without a null block. This is important to limit the predictability of the randomness of EC, and also to drastically reduce the likelyhood that people try to fork in their favor.

Also, ideally, the work you put in trying to mine a block can be reused to try mining on top of a null block. So that failing to mine a block, then mining a block on top of a null block only takes 2T, and not 3T (where T is the block spacing delay).

One fairly simply way off the top of my head to do this would be to make the 'ticket' in the block an array, and have multiple segments of the ticket chain in that array for null blocks. That way, when you check the ticket for a block, and you see that you lose, you can reuse that ticket (which was expensive to create) for mining a 'null' block.

[sternhenri]

If I understand things correctly, you think it should be 2T and not 3T in that the empty block mining should be made to take T (as a real block would) but should not take 2T (as in wasted mining to find losing ticket + empty block mining (T)). That is to say publishing an empty block can be done within same period as publishing a winning block, but provably made to take T Q1: Beyond it slowing our work, is there a fundamental reason this should not happen (with regards to correctness), or it's simply suboptimal (which I agree with)?

Thereafter, the proposed solution is to have generated tickets be arrays (which are publicly posted on the chain) so that in T0 miner mines Ticket[], checks Ticket[0], and if loses publishes a null block with Ticket[1], that everyone can verify took T (ticket generation time) to generate. Is this what you mean?

Q2: One question we can ask is: Is the complexity of array tickets worth the optimization in the case of null blocks? (ie space spent on the array across the chain vs actual expected slowdown of 3T empty block mining)

Also, I am wondering: if null blocks are now "authenticated" using the second slot in the ticket (maybe we can make tickets tuples), doesn't that somehow imply that the block has a "leader" of sorts in that everyone's tickets will be different, so now the block itself has to be signed so the ticket can be checked... So the block isn't really empty anymore... It just doesn't carry messages or a coinbase?

Any reason miners would not publish their empty blocks in this scheme, or on the contrary seek to publish their own rather than someone else's (ie reject another's null block to publish my own) -> Q3: can I grind using null blocks?

[sternhenri]

put another way, we want mine(lose/null) + mine again == mine (win) + mine again >= 2T vs mine(lose) + mine(null) + mine again == 3T which is to say that work to check whether mining was successful should be reusable to publish a null block (that nonetheless could not have been published without ticket generation)

[sternhenri]

So a few confusions on my part arose from this in convo with @whyrusleeping, namely around a few simple facts:

1. You don't publish null blocks, you simply need to publish proof that your winning block (whatever epoch it finally does come in) was mined atop a (or multiple) null block(s) (to account for the time needed to generate the appropriate proof). Put another way `null blocks don’t actually exist as an independent structure. There isn't some "empty block thing" that you propagate out (needless overhead). Those ‘physical null blocks’ are just be a parent hash, and a ticket (or multiple), so a verifier can attest to the fact that you generated x nulls before winning.

In that sense, we should understand the following: sans optimization Why proposes above, the sequence: I mine once, and fail (takes T) then try and mine on a null block and fail (total of 3T now) then try and mine on two null blocks and succeed should take 6T.

Put another way:

mine() -> Fail                                       | T
mine(mine(null)) -> Fail                      | +2T = 3T
mine(mine(mine(null))) -> succeed  | +3T = 6T

This is because mine(null) is deterministic (not readily apparent when you assume there's actual publishing of empty blocks happening).

===

So what we have is two changes:

1. output_ticket, win <- mine(input_ticket) regardless of whether mining leads to a win will output a ticket that can be used to mine atop an empty block (rather than what used to happen which was win <- mine(input_ticket) which would have required a follow up mine(null) now replaced by mine(output_ticket)
2. In turn, the space for tickets in the block header becomes an array rather than a value, so you can include all necessary tickets to prove you took appropriate time to finally win. e.g you might have in the block header [output_ticket_2, output_ticket_1, output_ticket_0] where this happened:

   
   output_ticket_0, lose <- mine(input_ticket)     | T
   output_ticket_1, lose <- mine(output_ticket_0) | +T = 2T
   output_ticket_2, win <- mine(output_ticket_1) | +T = 3T

Finally this conversation sparked another necessary detail:
*All tickets in the array should be signed by the same miner*, any out_of_band ticket exchanges enabling a miner to parallelize nulls by running multiple identities (say), or grind that way. Ie. whilst work should be reusable between mines, it should not be reusable between users.

To answer my questions:
Q1: not just suboptimal but impractical to dedicate CPUs for every null block, or to have to waste n epochs per null block (on a single CPU)
Q2: header only grows if we have null blocks, which is fine
Q3: no longer relevant with confusion clears up.

Further this should not impact any likelihood of block withholding (Ie if instead of mining on top of someone else's winning ticket, I can now mine atop my output_ticket (losing), why wouldn't i keep doing this?) because nothing has fundamentally changed, it's a question of weight in both cases, people will choose the chain of wins since they will be heavier.

[nicola]

Quick note (I didn't dive in depth in this conversation). Considering block propagation time, we need to make sure that we wait for enough time to have received blocks from the rest of the network.

In the honest/malicious setting, we make sure that malicious cannot go faster than time, because honest participants will reject their blocks (because they are in the future) and in my opinion we should define security in this setting. In addition, we could enforce running a VDF to strengthen this security, but gentle reminder here: vdfs have a known time and an Amax (the speed at which adversary can go ~10x faster), this means that VDF won't help much in practice, in case of malicious attackers, unless we make the waiting 10x slower for everyone, which would make it really slow for everyone (not reccomended).

My 2c: define security in honest/malicious (so it's easy to reason about it), strengthen security with VDF (without making blocktime 10x faster)

My 2c version 2: avoid VDFs.

[sternhenri]

Aligned with what you're saying Nicola. Also linking to https://github.com/filecoin-project/specs/pull/116 which I'll complete and merge shortly!

[nicola]

PR is merged, closing the issue https://github.com/filecoin-project/specs/pull/116