As someone who knows very little about subject, initially it appeared to me as if they were going to present some method to authenticate users without any shared knowledge, which seemed pretty close to magic to me! In fact the tl;dr is that two parties have a shared secret, but effectively they transmit proofs of possession that, statistically, achieve a high probability of being the same secret without needing to transmit it.

Calling this "zero knowledge" is sort of confusing from that perspective, but makes sense once you know what they're solving for.

It's kind of sad that even in an article about zero-knowledge proofs doesn't understand the difference between a zero-knowledge proof, and a proof of knowledge (without the zero-knowledge part). The ladder are usually much simpler than the former, and typically the zero-knowledge part is not necessary.

Good description of the intuition behind zero knowledge proofs is the following: http://pages.cs.wisc.edu/~mkowalcz/628.pdf

Does anyone have a feel for what the performance overhead of zkp authentication would be? Presumably the main cost is having to do lots of round trips?

So basically, it's magic.