Purpose

Proof-of-work (PoW) in Dscuss is used for resistance against flooding. PoW is just a guint64 number, which is sent along with users' public key. Hash of user's public key plus PoW must has a determined number of leading zero bits (see below). It should be hard to find such a PoW, and peers are forced to do this work before participating in discussion, otherwise their messages will be dropped.

Math

Average time to find a PoW is

Tavg = C * 2 ^ n

Where C is a constant, which depends on peer's CPU performance and n is the number of leading zeros in the resulting hash.

T is, of course, a random variable and has a geometric distribution. Tavg is the expected value of this variable. The real distribution of time to find a 20-bit (as an example) PoW is shown on the histogram below. The histogram is drawn for 10,000 values.

Histogram

The number of required leading zero bits is set to 30 for the proof-of-concept version. In this case, Tavg is about 1.5 hours on Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz.

The selected hashing function is PBKDF2 with 1 iteration and SHA512. TBD: consider switching to scrypt for the first release version.