Common coin in private network

[skhoroshavin]

This is actually a question about protocol, not an issue. Also 3 months ago I asked same question here, but there was no response yet.

I think I do understand why threshold signatures are needed for common coin in case of open message exchange in public network, where some malicious party can intercept, read and delay them in some smart way. But is cooperative calculation of common coin value is really needed in a network where all nodes are connected only by p2p encrypted channels? Can some kind of hash-based pseudorandom sequence (or just round robin) be used if there is no way for a third party to decrypt messages between any two given nodes unless one of them voluntarily disclose them?

I'm asking because lifting requirement for threshold crypto could simplify honeybadger a lot and make it even more attractive as a PBFT replacement in private or permissioned networks.

[afck]

I'd say it's not so much about encrypted connections as about whether any of the validators could be malicious. If you can fully trust all the nodes in the network, you only need a fault tolerant algorithm, not a Byzantine fault tolerant (BFT) one. That probably applies to most private networks. And to some permissioned ones, where all the parties fully trust each other.

But the Honey Badger is a BFT protocol, and all of its subprotocols are designed for that setting, including the common coin: If some participants are not trusted, generating random values that can't be easily manipulated turns out to be a difficult problem. Threshold signatures are one solutions to it. Another example is Randao's approach.

[skhoroshavin]

Probably I didn't explain my point well enough. As far as I understand (and my understanding might be completely wrong) HoneyBadger makes an assumption that there could be some adversary who can intercept, read and delay any message between any two nodes, so if this adversary knows values of common coins he can influence outcome of binary agreement. However, if nodes use peer-to-peer encryption then no adversary can read messages between honest nodes even if they communicate over public network, like internet, so adversary doesn't know which messages to delay in order to influence BA outcome even if he knows value of common coin. This scenario doesn't mean that nodes actually trust each other, actually there could be some malicious nodes, but they don't seem to be able to influence processing. Am I missing something?

[afck]

Even if we don't make that assumption, a pseudorandom sequence or a fixed coin schedule could still be known in advance by the adversary, couldn't it?
I don't think the decision to use threshold cryptography for the common coin was made specifically with unencrypted connections in mind, and I don't see how encrypted connections make the randomness problem much easier.

[skhoroshavin]

Even if we don't make that assumption, a pseudorandom sequence or a fixed coin schedule could still be known in advance by the adversary, couldn't it?

Yes, but if adversary doesn't know which votes are sent by honest nodes then it doesn't matter whether he knows next coin value - he still doesn't know which of encrypted messages to delay to influence BA outcome.

[afck]

All messages in the Binary Agreement protocol are multicast: they are sent to everyone, so the adversary will know what the honest nodes are voting anyway.

Take a look at this attack scenario, for example: amiller/HoneyBadgerBFT#59
This was an actual bug in the algorithm that we had to fix in the implementation. If I'm not mistaken, the attack would work again if the coin was pseudorandom.

[skhoroshavin]

Thanks for the link, I'll study it.

In the meantime, I think probably I'm starting to understand. If there is a malicious node cooperating with malicious scheduler then following scenario might be possible:

• scheduler can pause all communication except with malicious node
• nodes broadcast votes, but only malicious node gets them (and communicates to scheduler)
• scheduler unpauses messages from nodes that sent "right" votes

However if channels are properly encrypted then it should be impossible to tell boundaries of messages, so scheduler could not understand when it should pause communication.

[afck]

Sure, but even if one particular attack scenario is not feasible in practice, we still want a rigorous proof of the protocol's liveness. If we had such a proof that didn't require a cryptographic common coin, we'd probably remove the coin code completely.

[afck]

Closing this; feel free to reopen if you have any follow-up questions.