This post describes an attack on the current PoS construction. The attack uses the fact that it is possible to grind over the value for total_pieces without the need to reconstruct the PoS table. Additionally, some issues with the design are presented, as well as a rational strategy for when to replot, also focused on total_pieces.
To mitigate the attack, the recommendation is to integrate total_pieces into the evaluation seed for the PoS table.
- total_pieces is the number of total (recorded-history) pieces of the chain at a given time.
- It is used only for a single task – to place records within sectors. More precisely, given a sector and a sector slot position, farmers derive the record to be placed at the slot by computing
hash(sector_id, i) mod total_pieces, where
iis a sector slot and sector_id is derived from the farmer’s public key and the sector index (a number). Given the result, a non-negative number smaller than total_pieces, we take the corresponding record with this index value (in the global history) and associate it with that slot.
- total_pieces is part of the farmer’s proof (the Solution), as verifiers need to make the same computation.
- PoS tables do not use this value: for each slot position, farmers derive the table’s seed using sector_id and record_position (the specific slot position).
- In particular, PoS tables are independent from the chain history or the actual content of the sector.
- Farmers collect proofs of space within the PoS table, starting at start_index which is set to 0.
We illustrate the attack as follows:
- Suppose the attacker has the entire blockchain history (the entire history is not needed for the attack, but it is a realistic assumption).
- The attacker fixes sector_id, and generates the PoS table for each slot.
- Note: the attacker still hasn’t determined the actual records for the sector, and can now range over different values for total_pieces to obtain different content for the same sector.
- Given a challenge (the current global_challenge), the attacker derives the audit index
jfor the sector (s_bucket_audit_index).
- The attacker evaluates each record (recall that records can be represented as polynomials) at the audit index
j, XORs the result with the corresponding proof of space (if exists), and checks if the result gives a ‘‘winning ticket’’.
- For each such winning ticket, the attacker can range over total_pieces (going down from the current actual total number of pieces) in the aforementioned computation to see if the winning record falls into the desired slot (that corresponds to the PoS table).
- In fact, since the mapping
slot --> recordfollows a simple algebraic formula, the attacker can compute the desired value for total_pieces (if exists), and hope that it falls within the acceptable range (not in the future, and not expired yet). This may even be pre-computed, so the attacker does not have to check all records at all slots.
- Moreover, since start_index is set to 0, the attacker may evaluate all records at the first 50000 (s_buckets_per_sector) inputs in advance, as the overhead of storing this, instead of a degree-32768 polynomial, is small.
Storing the entire history is amortized over all of the attacker’s sectors. For each sector, the attacker needs to store the PoS table (I’m not sure about the actual size compared to the ‘honest plot’ size, but even if larger it should be comparable). The attacker has a wide range to set total_pieces, and each such attempt basically doubles the amount of ‘‘lottery tickets’’, hence doubling the weight of the attacker’s storage.
The crux of this attack is at the observation that the PoS table, an essential piece of the construction, is independent from the sector’s content. Hence, it is recommended to integrate total_pieces into the table’s seed.
Note: in the attack above the farmer stores the PoS table instead of the encoded polynomial. Doing so circumvents the limitation in producing this table on-the-fly, the main reason why it has been introduced in first place.
We come back to the computation
hash(sector_id, i) mod total_pieces, and recall that sector_id is derived by a public key and the sector index, which is a number.
When a sector expires, nothing prevents the farmer from setting exactly the same sector_id for their new plot. Denote the value for total_pieces within this sector by
Suppose that record
r was in the i-th slot for the expired sector. One can ask what the new value for total_pieces, denote it by
tp', should be such that the record
r falls again in the i-th slot. It can be shown that
tp' must be a multiple of
tp. The smallest multiple is 2, so set
tp' = 2*tp, which is also the proposed time (to check when) the original sector expires.
r is not guaranteed to fall within the i-th slot of the new sector, as it can also fall in the
(tp+i)-th slot. However, given that it distributed uniformly, there’s a 50% chance it will fall in the i-th slot.
We see that following this strategy – replotting at times that correspond to twice of the previous total_pieces and with the same sector_id – farmers are expected to keep half of their old plot.
Following the advice above and integrating total_pieces to the PoS table’s seed will also prevent this strategy from working. Moreover, we can make (the currently constant) start_index dynamic. The latter seems like a good idea in general.