Definitions and Notations — Recap
-
Tick count: the number of PoET ticks in an ATX’s PoST proof (i.e., should correspond to one “epoch’s worth” of PoET work)
-
Positioning ATX: an ATX (supposedly in the previous epoch) whose ID gets included in the PoET challenge for the ATX’s PoST proof.
Honest nodes always choose the ATX with the highest tick-height as their Positioning ATX.
A special Golden Positioning ATX with a hardcoded ID can be used instead of a real ATX (this should only happen in the first epoch in which ATXs are generated). Thus, every ATX has a chain of Positioning ATXs that terminates in the Golden Positioning ATX.
-
Tick height: the sum of tick counts in the Positioning ATX chain, including the tick-count for the ATX itself. (The Golden Positioning ATX has a tick-count of 0).
-
Base height: the tick-height of the Positioning ATX.
-
Full ATX weight: the tick-count of the ATX multiplied by the ATX space.
-
Full ballot weight: the full ATX weight divided by the number of ballots declared in the epoch.
Problem Summary
The problem we’re trying to solve is that an adversary can choose an “early” positioning ATX, and work for an arbitrarily long time to create an ATX with a arbitrarily large tick-count (and thus arbitrarily large weight). Although the total resources used by the adversary in each epoch are small, this concentrates all the ATX weight into a single epoch, so the single ATX could have an arbitrarily large fraction of the total epoch weight.
Solution Idea
The main idea, is that, for each block, we compute the block height such that it is approximately the same as the base height for honest ATXs in that epoch. We can now define:
-
Block-relative ATX tick-count: For an ATX with tick-height h_a and tick-count t_a relative to a block with block-height h_b, the block-relative ATX tick-count is
t_{rel}=\max(0, \min(t_a, h_a - h_b)) -
Block-relative ATX weight: The block-relative tick-count \times the ATX space
-
Block-relative ballot weight: The block-relative ATX weight divided by the number of declared ballots in that epoch.
By using the block-relative ballot weight instead of the full ballot weight, ATXs with an early base don’t get extra weight.
Of course, there are still several issues that need to be addressed:
- How do we set the block height?
- Is there consensus on this?
- What about the Hare?
Here’s an idea for how to compute and record the block height without getting into circular dependencies.
High-Level Overview
- The block height will be the minimum base height of the ATXs corresponding to the proposals that were used to construct it
- Hare participants will vote against any proposal whose tick count is more than twice their own tick count, or whose tick height is less than their base height.
- This assumes honest nodes have PoET speeds within a factor of 2, so honest parties will never fall afoul of these rules.
The intuition is that an adversary will be able to concentrate at most two epochs worth of weight, since if it tries to make the block-height earlier, its tick-count will be too large, and all honest parties will vote against its proposal. Since an adversary can already concentrate two epochs worth of weight (by starting at the beginning of epoch i and running poet until near the end of epoch i+1), the situation isn’t worse.
On the other hand, all honest proposals will be accepted, so they will all get their full weight (and future honest ballots won’t have base height much lower than the minimum honest proposal height).
(I think we can tradeoff security for the honest PoET difference by making the rules more stringent: e.g., if honest parties vote against proposals with tick-count more than (1+\epsilon) times their own tick-count, we’d need to assume honest PoET speeds are within a factor of (1+\epsilon), but correspondingly reduce the adversarial advantage.)
Details
Hare Participation
Since we’re using the Hare to agree on the block height, it’s important to ensure that we can select Hare participants fairly without having to recursively use this solution. To do this, for the purposes of Hare selection, we assume each ATX in the Hare active set has exactly 1 unit of time (i.e., its weight is equal to its space). This means the concentration attack is ineffective against the Hare.
On the other hand, an adversary can create ATXs with a very small tick-count, but they would still count as a whole epoch’s worth of weight. I think this is ok, because it can’t reuse the same identity multiple times in an epoch, and creating a new identity using the same space is more expensive than storing the data for an entire epoch.
Optional
If we want to be extra sure (or if there’s some attack I’m not thinking of at the moment), we can add an additional rule to the grading scheme for Hare Active Set selection:
- Give grade 0 to ATXs whose tick count is less than c_1 > \frac{1}{2} of my own tick count
- Give grade 1 to ATXs with tick count between c_1 and c_2=\sqrt{c_1} of my own tick count
- Give grade 2 to ATXs with tick count at least c_2 of my own tick count
The values 1/2<c_1<c_2 imply assumptions about PoET speed differences between honest parties. We need to assume that for every two honest parties A and B, it always holds that A's tick-count is at least c_2=\sqrt{c_1} > \sqrt{1/2} > 0.70 times B's tick-count; this implies that if B gave grade 2 to an ATX, A gave that ATX grade at least 1.
The grading criterion ensures that each ATX in the active set must have used more than half an epoch’s worth of PoET ticks.
Preventing Block-Injection
Our current rule is that lowest-height valid block in each layer is the “active” block for that layer (i.e., the only one that is executed). The reason for this is than an adversary in the future can creates a block in a past epoch, but with a high block-height, such that no old ballot can vote against it. Thus, a short period of dishonest majority can let the adversary create a valid block arbitrarily far in the past. The “lowest block height” rule ensures that such a block won’t change history, since it will have a higher block-height than the “real” historical block.
However, we now have to be careful that the “early base” concentration attack doesn’t allow the adversary to add their own block with a low block-height to the current layer (which would then become the active block). IIRC, this is something we’ve talked about in the past, but I’m not sure the solution is implemented: Every ballot with tick-height h is considered a vote against every block in a future layer whose block-height h_b<h.
This means that if an adversary tries to inject a block with a low block-height, it will immediately be rejected (since all ballots whose tick-height is above this block’s base-height will be voting against it including blocks in previous layers.
Empty layers
IIRC, we currently signify a vote for an empty layer by voting for a special “empty-layer” block-id. Of course, in this case, we don’t have an explicit block-height and can’t encode one.
I think it’s actually ok to give the “empty layer block” lock-height 0 as far as voting is concerned, but treat it as \infty for the purposes of the active block rule (and with the caveat that only ballots in future layers can vote for it). Essentially, this means every ballot votes with its full weight for the empty layer, but if both the empty layer and another block are valid, the other block will be active.
(IIRC, this is what we currently do anyway).
The intuition is that the empty layer vote is really shorthand for “vote against all blocks in this layer”. If another block is valid in the layer, this means that it’s margin must be positive — so it can’t be that “vote against all blocks” is really valid — the only reason it would appear to be so is if we overestimated the vote weight (e.g., by counting the full weight of adversarial ballots who are not allowed to vote against blocks in this layer with their entire weight).
We do need to check whether this could cause problems with the verifying tortoise…
Let’s first confine ourselves to non-hardfork methods and see whether the best that we come up with (which so far is the preemptive empty block injection) is pleasant enough.