Mitigate commit transaction censoring

Current state

Currently, the choice of which commit transactions to include in a block is up to the miner of a block. This opens up the possibility of censoring certain commits. One could choose to get his own commits accepted in a block or to negatively influence the reputation of other nodes by not including their commits.

Idea

Instead of allowing the miner to include a random subset of commits into a block, we could enforce a rule where the sum of the VRF proofs hashes (or commit hashes) should be minimal. This takes away the ability of a malicious miner to select the commits he wants to include, because if there is a better subset of commits, another honest miner will propose a block with the correct subset of commits with a minimized VRF proof sum.

As far as the technical implementation goes, I don't think it is computationally intensive to achieve this. You'd need to sort the vector of commits in remove_commits and add an extra ordering step in compare_block_candidates. This would also enforce choosing blocks with commits over blocks without, which has been proposed in #1827 as a solution to too many empty (censored) blocks, so we'd be catching two birds with one stone.

Discussion points

There is a potential for selfish mining, where a miner can decide to not broadcast his own commit with a small VRF proof to obtain a higher chance of getting his block selected. While this is not impossible, I'm not sure this is a viable (economical) strategy because the miner needs to both be eligible for block mining and data request mining. Furthermore, he can only know his commit transaction is a good one after he has seen blocks (and their included commits) proposed by other miners. I think this is a race to the bottom that cannot really be won, especially because multiple miners could follow the same strategy leading to a status quo again.
What priority should be given to this minimal sum check in compare_block_candidates? You could put it before the reputation check, before the is_active check or before the miner VRF proof check (note that I am using the block comparison strategy from WIP-0009). I'd say the implications are always a bit different (and they definitely need some discussion). The most important implication of placing it before the reputation check is that it forces ARS nodes (whom have the most to gain by censoring other ARS nodes) to be as honest as possible because zero-reputation nodes could also propose a minimal VRF proof commit sum. However, it also increases the number of nodes that could employ the tactic described in point 1.

There are probably other aspects that should be discussed and potential drawbacks which I am currently missing.

If I remember correctly, all the commit transactions should be equally valid to ensure a fair network. This is because if one node is 100% sure that it will be in the committee for a data request (because for example the commit vrf hash is extremely low), then they may coordinate with other nodes and change the result of the data request. So if we want to enforce an order to the commit transactions it should be impossible to guess the "inclusion probability" given a single commit, or given a small subset of commits. Maybe this could be accomplished by using a function of all the commit vrfs in a block, something like hash(vrf1||vrf2||vrf3) as the "order score". Another idea is to enforce an order that depends on the miner pkh, so that different nodes will include different commits, but the order still can be validated. But all of these ideas introduce complexity and attack vectors, so we should be careful. The main problem is that we cannot assume that all the nodes have seen all the commits, so we cannot directly penalize nodes for not including commits.

Regarding 2) I think the priority in compare_block_candidates should be just before the block VRF, so that nodes that are not active and have 0 reputation will never produce better blocks than active nodes. This would allow ARS nodes to perform a censorship attack if they all coordinate, but it won't last long because as soon as a new node enters the ARS the new node will produce better blocks than the rest. Other options would enable attacks similar to what we've seen in #1827, where inactive nodes can produce better blocks than active nodes.

I don't know how likely it is for a node to be 100% convinced his commit will be included, but I understand that it may be necessary for all commits / reveal to have an equal probability as to prevent collusion and data request manipulation.

Maybe this could be accomplished by using a function of all the commit vrfs in a block, something like hash(vrf1||vrf2||vrf3) as the "order score".

I thought about using a more complex function that is hard to predict upfront, but minimizing something like that would essentially transform the node operation to be computationally intensive, which I assume is to be avoided.

The main problem is that we cannot assume that all the nodes have seen all the commits, so we cannot directly penalize nodes for not including commits.

That is true, it is impossible to know if a node has seen all commits, but I'm also not proposing to directly penalize a node, but rather just not allowing them to mint a block with a non-optimal set of commit transactions to mitigate censoring. In my opinion, you are not putting it in any more of disadvantageous position than we already do based on sortition of the VRF proof value.

Regarding 2) I think the priority in compare_block_candidates should be just before the block VRF, so that nodes that are not active and have 0 reputation will never produce better blocks than active nodes. This would allow ARS nodes to perform a censorship attack if they all coordinate, but it won't last long because as soon as a new node enters the ARS the new node will produce better blocks than the rest. Other options would enable attacks similar to what we've seen in #1827, where inactive nodes can produce better blocks than active nodes.

For a new non-colluding node to be able to produce better blocks and (immediately) stop a censorship attack, you have to assume that it is first eligible to produce a block and second that the commits generated by the (set of) nodes are being censored are also the best ones at that moment. This seems like a pretty unlikely chain of events? My proposal of including it earlier in the sortition tries to mitigate the fact that ARS nodes have the most to gain by censoring other ARS nodes and outsider nodes a lot less. If you enforce blocks to contain commits before they can win the selection process, you're mitigating issues like in #1827. I cannot immediately think of another attack vector, but obviously that does not mean there aren't.

In any case, I understand that this would be a pretty significant change that may break the assumptions to guarantee honesty built into the network. It was just a thought I had to tackle commit censoring.

I thought about using a more complex function that is hard to predict upfront, but minimizing something like that would essentially transform the node operation to be computationally intensive, which I assume is to be avoided.

True, that would allow to use more cpu time to find better block candidates, that's the definition of proof of work.

Anyway, let's do some brainstorming. I can think of a safe way to enforce an order of reveal transactions using your idea to minimize the sum of the vrf hashes. Let's imagine a data request that requires 100 witnesses, but there are 200 commits. We can allow miners to include all 200 commits instead of the required 100. Then the witnesses need to include a new vrf proof alongside the reveal transaction. This vrf proof can only be computed after the block with all the commits has been consolidated, let's say it depends on the block vrf hash. Reveals are harder to censor because we currently allow 4 reveal rounds, so an attacker would need to mine 4 consecutive blocks to censor a reveal. In the tally stage we only select the 100 reveals with the lowest vrf hash. The remaining reveals are ignored, as if they had not participated in the data request.

This has many drawbacks: higher block size, another round of expensive vrf verifications, changes to the reveal transaction schema... But I think it simplifies the original problem because we would only need to enforce a maximum number of commits, not a best order of commits.

I'm not exactly following how this mitigates commit transaction censoring? What is stopping a miner from including 190 of 200 commits thereby forcing certain other nodes to not reveal a value? Unless you are suggesting that the miner which includes most commits wins the block mining process?

I'm saying that if we find a way to ensure that the blocks have as many commits as possible, then we could order the commits during the reveal stage and solve the censoring problem. But I don't know how to enforce a maximum number of commits while avoiding the problems 1) and 2), so that proposal alone doesn't solve the problem.

Well, one crazy idea: we could force commit transactions to reference other commit transactions somehow. For example, let's say that every commit transaction must reference 10 other commit transactions to be included in a block. Then, if a miner wants to include one commit it must also include the ones referenced by it. Not sure if this is possible or how would it work, but the idea is that if all the commits are "entangled " together, then it is harder for miners to separate them.

I also would not know how to enforce that except that the miner which includes most commits wins the block.

I like the idea of commit entanglement, but I see not practical implementation of that since it looks a bit like a deadlock scenario. You'd have to wait for commit transactions to be sent through the network and reference those, but at the same time the first commit transactions that appear in the network cannot be valid by definition. Unless you adopt some iterative approach where nodes send multiple commit transactions at different times when they have seen enough commits. I'm also not quite sure how this would work for low-witness DR's (most DR's have 100 witnesses now, but that doesn't mean this will be viable once we have "real" DR traffic).

If I remember correctly, all the commit transactions should be equally valid to ensure a fair network. This is because if one node is 100% sure that it will be in the committee for a data request (because for example the commit vrf hash is extremely low), then they may coordinate with other nodes and change the result of the data request. So if we want to enforce an order to the commit transactions it should be impossible to guess the "inclusion probability" given a single commit, or given a small subset of commits.

I dug a bit deeper into this and checked the number of proposed and included commits for my nodes: it is pretty close to 50%. So, in order to succesfully lie in the current system, you only need to control an amount of nodes generating an eligible VRF proof equal to the number of requested witnesses (since half of your commits will be included and they will create the majority answer). I'm saying only, but of course the odds of that are very small.

Let's assume a minimal VRF sum is enforced. When you generate a commit (in absence of other commits), generating multiple VRF proof so small you can be certain it has a higher than 50% probability of inclusion seems pretty unlikely. You could obviously wait with broadcasting your commit until you have seen a majority of the other commits, but the confidence you're gaining that the majority of your commits will be selected seems not that big compared to the already high baseline. Even if you are 100% certain all of your commits will be included, it does not really change that you need to control a lot of nodes generating enough valid VRF proofs. In summary, I'm not convinced that enforcing the sum of VRF proofs to be minimal really changes the likelihood you can succesfully lie.

All of this is obviously based on me not interpreting the likelihoods incorrectly?

witnet / witnet-rust