# ZIP 317 enforcement

## Block production

Goals:

* Resistance to denial of service
* Specify a RECOMMENDED algorithm to choose how to select transactions for a block template
* Transactions that represent "typical" usage should not be unduly disadvantaged vs DoS-like transaction behavior
* This is vague

Ideas:
* Delay transactions that pay less then the conventional transaction fee by including them probabilistically.
* This retains compatibility with wallets that are slow to implement the new fee calculation.
* Limit the bandwidth available for denial of service.
* Impose a smaller block size limit than the consensus block size limit
* This reduces the rate of increase of chain space
* Impose a smaller mempool limit
* This reduces the ability of attackers to add extra transactions to the mempool to overcome the block rate-limit

If a DoS attacker makes their transactions indistinguishable from "legitimate" transactions (which requires them to pay the conventional fee), then the best we can do is to include transactions randomly, so that the attacker's transactions take up block space in proportion to how many of them they can get into the block producer's mempool. We can prioritize transactions that pay the conventional fee as 'first' into the block, and rate-limit other transactions.

The current sandblasting is an attack on chain space.

Example situations:

* if all transactions pay at least the conventional fee, then there is no limit on how much of the maximum block size they can take up
* zero-fee transactions do not get into the chain
* if we have half the block filled with CF txns and the remaining txns each pay CF/2, then we use 3/4 of the max block size

## Proposed algorithms

### Algorithm 1

1. For each transaction `tx` in the mempool, calculate `tx.weight = min(tx.fee / conventional_fee(tx), weight_cap)`.
2. Repeat while there is any mempool transaction that pays at least the conventional fee and fits in the block and sigop limit:
a. Pick one of those transactions at random with probability according to its weight, and add it to the block.
3. Let `N` be the number of remaining transactions with `tx.weight < 1`. Calculate their sum of weights, call this `remaining_weight`.
4. Calculate `size_target = size_of_block_so_far + floor(remaining_block_size * (remaining_weight / N))`.
5. Repeat:
a. Pick a transaction with probability according to its weight and add it to the block if it fits in the sigop limit. If that transaction would exceed the `size_target`, stop without adding it.

### Algorithm 2

1. For each transaction `tx` in the mempool, calculate `tx.weight = min(tx.fee / conventional_fee(tx), weight_cap)`.
2. Repeat while there is any mempool transaction that pays at least the conventional fee and fits in the block:
a. Pick one of those transactions at random with probability according to its weight, and add it to the block.
5. Let `total_fees` be the sum of actual fees paid by remaining transactions, and let `total_conventional_fees` be the sum of conventional fees for those transactions.
6. Calculate `size_target = size_of_block_so_far + floor(remaining_block_size * total_fees / total_conventional_fees)`.
5. Repeat:
a. Pick a transaction with probability according to its weight and add it to the block. If that transaction would exceed the `size_target`, stop without adding it.

### Algorithm 3

Define a function $health(txset)$ as $\frac{\sum_{tx \in txset} \mathsf{min}(tx.fee,\, conventional\_fee(tx))}{\sum_{tx \in txset} conventional\_fee(tx)}$, and a constant $health\_threshold = 2/3$ (say).

1. For each transaction $tx$ in the mempool, calculate $tx.weight = \mathsf{min}\left(\frac{tx.fee}{conventional\_fee(tx)}, weight\_cap\right)$.
2. Repeat while there is any mempool transaction that pays at least the conventional fee and fits in the block and sigop limit:
a. Pick one of those transactions at random with probability according to its weight, and add it to the block.
4. For each remaining transaction $tx$ in random order:
a. With probability $1 - tx.weight$, drop $tx$ and continue.
b. If $health(block \;||\; tx) < health\_threshold$, stop.
c. Add it to the block provided that it fits in the block and sigop limit.

### Algorithm 4

Define $unpaid\_actions(tx) = \mathsf{max}\left(0, \mathsf{max}(grace\_actions, tx.logical\_actions) - \mathsf{floor}\left(\frac{tx.fee}{marginal\_fee}\right)\right)$ and a constant `block_unpaid_actions = ?`.

1. For each transaction `tx` in the mempool, calculate `tx.weight = min(tx.fee / conventional_fee(tx), weight_cap)`.
2. Repeat while there is any mempool transaction that pays at least the conventional fee and fits in the block under the sigop limit:
a. Pick one of those transactions at random with probability according to its weight, and add it to the block.
3. Repeat:
a. Pick a remaining transaction with probability according to its weight. Provided the total number of unpaid actions for the block including this transaction would not exceed `block_unpaid_actions`, add it to the block if possible.

Note that "picking a transaction" removes it from the set under consideration, and so the algorithm always terminates.

----
### Previous notes for algorithm 1

#### Implementation
- Even if `tx.weight` is represented as floating point, the sum of `N` `tx.weight` values each `< 1.0` must be `<= N` regardless of evaluation order or rounding, provided that `N <=` the largest exactly representable integer ($2^{24}$ for IEEE `float` and $2^{53}$ for IEEE `double`). This is always the case because the mempool cost limit is 80000000 and each transaction costs at least 4000. Then `remaining_weight / N <= 1.0`, and so `floor(remaining_block_size * (remaining_weight / N)) <= remaining_block_size`. It would however be a reasonable implementation strategy to limit `size_target` to at most `maximum_block_size` for robustness.

#### Rationale
* Regardless of how full the mempool is (according to the ZIP 401 cost limiting), the adversary can only fill a block if `remaining_weight / N` is nearly 1, i.e. if the remaining transactions are paying nearly the conventional fee on average. This is exactly what we want, because then the selected transactions in step 5 will each tend to be paying nearly the conventional fee. (It's possible that some low-fee transactions will get in, but the adversary can't include too many of them because it would pull the average down.)
* The weighting in step 2 does not create a situation where the adversary gains a significant advantage over other users by paying more than the conventional fee. Compare the case where the adversary pays `c` times the conventional fee for one transaction, to that where they pay the conventional fee for `c` transactions. In the former case they are more likely to get *each* transaction into the block relative to competing transactions from other users, *but* those transactions take up less block space. (The adversary's block space usage relative to fee is optimized by using only Orchard Actions in either case, so they take up `c` times less space.) So this is not what the attacker wants; they got a transaction into the block only at the expense of leaving more block space for the other users' transactions.

Ideas:
* Weight transactions inversely proportional to `tx.size / tx.fee`
* Since miners have limited block space, this increases their profits for the block. This situation can be modeled by the Knapsack problem.
* Adding "with probability according to its weight" to step 2 creates a fee market, do we want to do that?
* Maybe proportional to a *capped* weight, say 5 times the conventional fee?

## Relaying