Q:

Decentralised user authentication -- possible?

I'm designing a fully distributed P2P messaging application.
Edit: Not just any messaging application -- specifically a public forum. Messages are passed along from neighbour to neighbour, so messages may come in from a peer other than the original author. Secrecy of communication is unimportant. However, verification of the author of a message is vital.
The problem needs an introduction:
In client-server models, each client can be sure that messages' origins are what the message says they are, because there is a "middle man" authentication server that checks that the user's credentials (username, password) match an entry in an internal secret database before relaying the message to the receiving client.
The question is: Can this be implemented in pure P2P?
Suppose each client stores the full set of user credentials. The difference is of course that clients cannot be allowed to view them -- hence they'd be stored in encrypted format. The encrypted credentials would have to be checked for equality against another set of encrypted credentials without ever fully decrypting either set.
Can this be done? Is there a better way?(Remember: 100% P2P. No servers.)

A:

I suggest you look into a model called Web of trust. It's used by for instance PGP to decentralize authentication. 
This quote summarizes it pretty well: 

As time goes on, you will accumulate keys from other people that you may want to designate as trusted introducers. Everyone else will each choose their own trusted introducers. And everyone will gradually accumulate and distribute with their key a collection of certifying signatures from other people, with the expectation that anyone receiving it will trust at least one or two of the signatures. This will cause the emergence of a decentralized fault-tolerant web of confidence for all public keys.

