Fast PoET could prevent voting by honest smeshers

Research
1

During yesterday’s dev sync we came to discuss an issue with the way we limit voting for blocks based on tick height.

The original concern came from Dmitry, when NJ mentioned that he’s using his self-hosted PoET, that’s ~4x as fast as the cloud hosted one and not available to other smeshers, on the testnet. Dmitry worried that this would cause other smeshers on the testnet to not be able to vote on blocks anymore, due to our rule preventing smeshers from voting on blocks in their future.

Currently this is not happening, as far as we know. This is probably because he publishes his ATXs around the same time as everyone else, so other nodes are picking his ATXs as positioning ATXs. This is due to logic in the node for picking the highest ATX.

Kimmy then raised the concern that if he happened to publish his ATXs after everyone already submitted challenges to the PoET, they wouldn’t be able to use him for positioning, causing their ATXs to have lower tick heights than his positioning ATX (his own previous ATX).

This would mean that any block for which he contributed a proposal would be “in the future” for all other smeshers and they wouldn’t be able to vote for (or against) it. We use the highest positioning ATX height of all contributors to a block as the block height.

This initially seemed to only be a problem if someone has a private PoET that’s more than twice as fast as any publicly available PoET and ATXs using it are published late in the epoch. However, Piers highlighted that, even with a PoET that’s just slightly faster, this attack can be achieved, if the attacker keeps their ATXs private, using them for positioning and only publishing the chain of ATXs when they have a positioning ATX that’s ahead in tick height than all other smeshers’ current ATX.

Proposed Solutions

Using the Median Height of Proposals for a Block

The set of proposals that are integrated into a block are randomly sampled from the population of smeshers. If a smesher controls a small part of weight they won’t be able to contribute half the weight to a block with non-negligible probability. By considering the median (per unit of weight) proposal’s base tick height (the height of its positioning ATX) as the block’s height, we make it considerably less likely for an attacker, who doesn’t control a majority of the weight, to block honest smeshers from voting on a block.

This should be trivial to implement.

Preventing Voting for Future Proposals in Hare

The issue arises from the selective application of the rule to “prevent voting on future messages”. We apply it to ballots applying an opinion on blocks, but not Hare participants voting for proposals. This means honest participants would aid an attacker causing a block to have a future height, that those same honest participants then won’t be able to vote for.

By preventing Hare participants from voting on proposals that are in their future, we would prevent the highest included proposal from being in the future for a majority of Hare participants. Since the Hare committee is guaranteed to have an honest majority (with probability 1-2^{-40}), it prevents a dishonest smesher from carrying out this attack, under our assumptions.

The rule would be implemented similarly to blocks: we compare a proposal author’s base tick height (height of its positioning ATX) with the voter’s actual height. If the voter’s actual height is greater than the proposal’s base height - they can vote for it in Hare. In other words, if a proposal doesn’t have f+1-k supporters in the Hare with a tick height greater than it’s base height, it’s not considered validated by the Hare, its transactions won’t be incorporated into the block and the smesher will not receive a reward.

Further Discussion

Lane raised the issue that someone with a faster PoET would also have a greater weight than their space would normally get, but I don’t consider this a problem, since our definition of “no more than ⅓ dishonest” refers to weight. So, yes, an adversary could invest in making a faster PoET so they need less than a ⅓ of space for an attack, but this is not necessarily cheaper, easier or new. This would affect our assumptions anywhere in the protocol and not just for this new attack.

I’m not saying it’s not true or not dangerous, only that it’s orthogonal.

My proposed mitigations mean that an attacker controlling a PoET 2x the speed of public PoETs would still need to control >⅙ of space to carry out an attack (like before we discovered this issue).

1 Like
2

couple of questions

Using the Median Height of Proposals for a Block

what prevents me from setting active set to a very low value so that my identity is eligible for creating a proposal in every single epoch? this way if average is 50, i can make 51 smallest identities, and get my height selected

Preventing Voting for Future Proposals in Hare

maybe it was true before as well, but doesn’t it incentivize majority to sit on the same slow poet and censor everyone with a fast one? at what point they will be allowed to use fast poet?

3

If the adversary has a significantly faster “hidden” PoET, this definitely violates our security assumptions, and can lead to even worse attacks if the adversary can keep the PoET hidden and faster than honest parties over a long period of time (for example, they can launch a concentration attack even with much less than 1/6th of the space).

However, mitigating a slightly faster PoET, I think @noam’s mitigations sound generally like a good idea. I think it might be enough to implement only the second one (I need to think a bit more about whether using the median rather than maximum tick-height could present any problems).

To @dmitry’s point, I think this should actually incentivize users with a fast poet to publish their ATXs early (allowing honest users to use them for positioning). They will still gain an advantage in the rewards due to the weight (since they get more ticks then users with a slower PoET).

Every user is guaranteed a proposal in every epoch, regardless of the active set size. The active set is actually there to prevent an adversary from generating too few proposals, and thus concentrating their weight unfairly.

When we calculate a median, it’s a weighted median, so it doesn’t matter how parties split their weight between different proposals in the same layer.

4

To summarize the discussion we just had in the research call: we implement only the second mitigation and this is enough to address this issue.

We’re assuming that honest smeshers won’t use a private PoET that’s >2x as fast as any public PoET, because that could hurt the honest smeshers that do it. If someone has a private PoET that’s >2x as fast as any public PoET it enables other nasty attacks regardless, so we should try to make public PoETs fast enough regardless of this.

5

We discussed with @noam all the possible ways of implementing this new rule at the Hare level. Our conclusion is that the only adjustment we want to add to Hare is the following extra processing step:

  • at the formation of a PRE-ROUND message, the smesher filters-out all proposals that would violate “Voting rule #2”

For clarity, we summarized both tick-based voting rules on the following picture:

tick-height-voting-rules
tick-height-voting-rules1920×1370 165 KB

6

can you share the alternatives of voting against a proposal in hare other than not including in the preround?

7

We didn’t explore this all the way to map out the issues, but ideally, we would prevent voting for future proposals not only in the pre-round, but everywhere. E.g. when a leader creates a Hare proposal and then validate it before voting for the proposal later in Hare. Possibly, we could have said that we must have f+1-k commit messages that can vote for a given block proposal for it to be considered accepted by the Hare.

We decided that the added complexity of touching more of Hare internals wouldn’t be worth the added security. Added security, because with the currently proposed design, if an adversary is able to dominate the pre-round they can undo this mitigation and create a Hare-generated block that others can’t vote for. The reason we feel that this is fine is that if they’re able to create a “future” proposal and also dominate the pre-round of the Hare, and the only “reward” they get is creating an empty layer - it seems like they could use this power to do worse things.

8

can you share the alternatives of voting against a proposal in hare other than not including in the preround?

In general I can see 3 ways of changing Hare implementation so to materialize the idea of Noam’s tick-height-based condition:

  1. Changing both formation and validation of a PRE-ROUND message.
  2. Changing the way we interpret a safe-value-proof in the PROPOSAL round
  3. Combination of both changes above.

For Genesis, I suggest option (1) as the way to go. At least this is my current state-of-mind.

Below I describe these changes in more detail.

Pre-round message formation

Before the change, Node comes up with a proposal applying the following steps:

  • taka a snapshot of the collection of proposal ids observed in this layer so far
  • pick a subset of proposals from this collection (using some randomized selection algorithm - the details of this algorithm are not important at this point)
  • form a PRE-ROUND message enumerating the subset (every proposal is referenced by its hash value)

After the change, the sequence would be:

  • taka a snapshot of the collection of proposal ids observed in this layer so far
  • filter this collection using the condition myTickHeight >= proposal.atx.baseTickHeight (i.e. only elements for which the condition is TRUE will be left)
  • pick a subset of proposals from this collection (using the same randomized selection algorithm are previously)
  • form a PRE-ROUND message enumerating the subset (every proposal is referenced by its hash value)

Pre-round message validation

When a PRE-ROUND message arrives, it should be validated to check if the creator was honestly following rules of the protocol. The tick-height condition can be indeed checked by any node receiving a PRE-ROUND message.

Assume the following (simplified) structure of Hare pre-round message:

struct PreRoundMessage {
    creator: SmesherId,
    epoch: Long,
    layer: Long,
    eligibilityProof: EligibilityProof,
    listOfProposals: Array[Hash],
    msgSignature: Ed25519Sig
}

Assume a single ATX has structure:

struct ATX {
    tickCount: Long,
    tickHeight: Long,
    positioningATX: Hash
}

Assume a proposal has structure:

struct Proposal {
    creator: SmesherId,
    transactions: Array[Hash],
    signature: Ed25519Sig
}

Assume the following functions are available (and give access to the local database of a Node):

fun findATX(id: SmesherId, epoch: Long): ATX
fun findATX(hash: Hash): ATX
fun findCachedProposal(layer: LayerId, proposalId: Hash): Proposal

The relevant checking loop would work as follows:

fun checkPreRoundMessageForTickCountCompatibility(msg: PreRoundMessage): Boolean {
    val tickHeightOfMessageCreator: Long = findATX(msg.creator, msg.epoch).tickHeight
    for p <-  msg.listOfProposals {
        val proposal: Proposal = findCachedProposal(msg.layer, p)
        val atxOfProposalAuthor: ATX = findATX(proposal.creator, msg.epoch)
        val hisBaseATX: ATX = findATX(atxOfProposalAuthor.positioningATX)
        val hisBaseTickTime: Long = hisBaseATX.tickHeight
        if (hisBaseTickTime) > tickHeightOfMessageCreator)
            return false
    }
    return true
}

Changed interpretation of SVP in PROPOSAL round

In the PROPOSAL round, a leader attempts forming a SVP (safe value proof). After successful formation of SVP, a PROPOSAL message is broadcast.

On receiving, a PROPOSAL message becomes the source of the commit-candidate, i.e. the best-so-far candidate for the consensus outcome. The commit candidate is calculated differently depending on the type of SVP that arrived.

We have 2 types of SVP:

struct BootstrapSVP {
    iteration: Int,
    statusMessages: Set[Message.Status],
    magmaSet: CollectionOfMarbles
}

struct ProperSVP {
    iteration: Int,
    statusMessages: Set[Message.Status],
    magicMessage: Message.Status
}

Currently, the consensus candidate for BootstrapSVP is calculated as the sum of all marbles in status messages included in the SVP.

After the change, the consensus candidate for BootstrapSVP would be calculated as as a subset of this sum, including only marbles with sufficient (f+k-1) support by tick-compatible status messages.

Where the “tick-compatible” is of course defined such that a status message (considered a “vote” in this case) is tick-compatible with a marble (marble and proposal are synonyms in this context) if tick-height of the status message is equal or bigger than base-tick-height of the marble.

9

the research meeting on Mar. 9 2023 concluded that there is no need to validate incoming preround messages. hare validity will make sure such proposals will not be selected if all honest parties vote (select preround proposals) according to their tick heights.

10

Using the Median Height of Proposals for a Block
is not yet implemented

Preventing Voting for Future Proposals in Hare
is implemented in [Merged by Bors] - hare: do not vote for future proposals by countvonzero · Pull Request #4121 · spacemeshos/go-spacemesh · GitHub

11

this thread is hereby concluded as implemented.