Grading ATXs for the Active Set

Research
1

In every epoch, there comes a time when the sheep must be separated from the goats, the wheat from the chaff, and the apples from the oranges. In other words: to determine which ATXs were created by honest users in good faith, and which were generated by a malicious adversary bent on evil.

Sadly, this task is beyond mere Spacemesh nodes. But we can do almost as well, by introducing some shades of gray into our decisions.

Protocol Rules

ATX Grades

We grade ATXs on a scale of 0 to 2, based on when the ATXs were received (where 0 is definitely evil, and 2 is “as good as we can get”). Let s be the start of the epoch.

  • Grade 2. The ATX was received at time t<s-4\delta, and no equivocation proof was received for that id until time s.
  • Grade 1. The ATX was received at time t<s-3\delta before the start of the epoch, and no equivocation proof was received by time s-\delta.
  • Grade 0. The ATX was received at time t\ge s-3\delta, or an equivocation proof was received by time s-\delta.

First-Ballot Generation

When choosing ATXs to include in their active set, parties will only include ATXs with grade 2.

Proposal voting

Parties will only vote for a proposal whose corresponding active set has grades 1 or 2.

Intuition

The idea behind the grading scheme is that it satisfies the following invariants:

  1. If any honest party gave an ATX grade 2, then every honest party will give it grade at least 1. The reason is that if party A received the ATX at time t_A < s-4\delta, then party B will have received it by time t_B\le t_A+\delta < s-3\delta. On the other hand, since A did not receive an equivocation proof by time s, B cannot have received an equivocation proof by time s-\delta.

  2. If any honest party gave an ATX grade \ge 1, then every honest party will have received this ATX before receiving an equivocation proof for this ID. This is because if A received the ATX at time t_A<s-3\delta, and did not receive an equivocation by time s-\delta, then B must have received it at time t_B<t_A+\delta < s-2\delta, and could not have received an equivocation proof by time s-2\delta.

Since an honest party only includes grade-2 ATXs in their active set, then every honest party will vote for this proposal (since the ATXs are guaranteed to have grade 1 or 2 by invariant (1) ). By Hare validity, this means every honest proposal will be included in the final accepted set of proposals.

On the other hand, if a proposal has an ATX with an equivocating id, such that at least one honest party did not receive this ATX (because it received an equivocation proof first), then no honest party will vote for this proposal — since by invariant (2), it can’t have grade \ge 1 for any honest party. By Hare validity, this means such a proposal will never be in the final accepted set of proposals. Thus, every ATX in the active set is known to all honest parties.

1 Like
2

two questions:

  • for new node syncing, the ATXs received timestamps are always late. it may cause the network to reject their first proposal
  • when nodes that happen to miss the first successful hare round of the epoch, they need to sync the active set from peers. @noam suggested to put this active set in the block certificate for syncing. does that work?
3

We count nodes that weren’t online for long enough before they publish a proposal as malicious. If the node does this, it might “lose” its proposal – but I think that’s a reasonable incentive to make sure your node is online for a long-enough period before you’re eligible.

The active set is determined by the contents of the block — so if the first hare round terminated successfully, any node that has the block can compute the active set (taking the union of the active sets in the ballots corresponding to the rewarded proposers in that block).

I don’t think there’s a need to add any additional information to the block certificate.

4

we don’t currently remember/record the set of hare output for a given layer. so we still need to somehow persist the hare output and make it available during sync. since we are already syncing block certificate from peers, it seems a natural place to also record the set of hare output that generated the block.

5

I think I’m missing something. The active set is recorded in the block, which we do sync. What information are we lacking that needs to be added to the block certificate?

6

ok. if the design is to record the active set in the block, then it will work.
the code currently doesn’t record the active set in the block. the block only has transactions and rewards at the moment.

on the other hand, i thought it’d be space-efficient to save it in the block certificate, as those active set isn’t useful after the epoch (+shifting) passed. we can prune block certificate after hdist has passed.

7

The active set is implicitly recorded in the block — it doesn’t require additional information to be stored.
The explicit information recorded in the block is the list of proposer IDs that get rewarded (i.e., those that were agreed upon by the Hare).

This list is used to compute the active set in the following way. Denote the proposer IDs in the first block by id_1,\dotsc,id_n:

  • From proposer id_j, take the first ballot published by id_j, in this epoch, and let S_j be the active set that is recorded in that ballot.
  • The “final” active set is \bigcup_{j=1}^n S_j — that is, the union of the active sets referenced by the proposers in the first block of the epoch.
8

in the block rewards we only record the coinbase addresses, not the proposer IDs.

9

Isn’t the mapping from ID to coinbase in the ATX?

10

the mapping from ATXID → coinbase address is recorded yes.
but from coinbase address → ATXID is not. presumably multiple ATXs can use the same coinbase address.

11

So why not just record the ID in the the block instead of the coinbase? This gives enough information to recover both the active set and the coinbase addresses, without increasing communication or storage.

12

yes. doable. only that the rewards are dished out in the VM.
not sure whether we will/should have access to mesh data inside VM (in the future)

@dmitry can you comment?

back when we were discussing this format, i recall @noam also had opinions about storing ATXID in the block rewards. don’t remember tho.

13

yes. doable. only that the rewards are dished out in the VM.
not sure whether we will/should have access to mesh data inside VM (in the future)

i don’t think that we should read atxs in the vm. but it seems just a question of the proper interface that will keep vm correctly isolated

1 Like
14

In any case the VM will not have access to the raw block, right? So we can expose smesher ID and coinbase information inside the VM as we deem fit. I’m not terribly worried about this.