Synthetic randomness for batch verification

[real-or-random]

After we have switched to recommending synthetic randomness for nonces, I propose to do the same for the randomness used in batch verification. Currently we derive the randomness deterministically from the inputs to the batch verification algorithm.

Mixing in real randomness avoids that the result of the batch verification algorithm is entirely predictably to an attacker. There will be sets of signatures that contain invalid signatures but still pass batch verification. If our hash function is good, these can be found only with negligible probability, so this is not an issue per se. But adding real randomness provides defense in depth and makes this attack impossible. This also prevents attempts to exploit such an attack to split the chain between one set of nodes with some PRG X and another set of nodes with some different PRG Y.

Moreover, when I say these inputs can only found with negligible probability, then this relies on an argument that is nowhere written up properly. It appears to be true and I think I have a simple proof but as far as I know, we're to first to specify such an algorithm. Independently of this, we should add a proof sketch to a footnote. (I can do this). But even if we have this argument written up, adding real randomness is defense in depth, and bring us back to "standard" batch verification, where the coefficients are random and which has been looked at often enough,.

I don't any of these points is a must-have. But given that adding real randomness is so cheap (and we can make it optional), I think we should do it. It's also easy to write in the BIP because we have some text already for nonces and we can mostly refer to this.

[sipa]

This makes sense to me.

[jonasnick]

👍