Title: Proof-of-work
Summary: Details about proof-of-work implementation.
Copyright: (c) 2014 Vitaly Minko
Content is available under GNU Free Documentation License 1.3 and
Creative Commons Attribution-Share Alike 3.0 Unported License
Date: 08 Sep 2014
Web: http://vminko.org/dscuss/pow
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][geom].
_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][hist]
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][scrpt] for the first release version.
[geom]: https://en.wikipedia.org/wiki/Geometric_distribution
[scrpt]: http://en.wikipedia.org/wiki/Scrypt
[hist]: /storage/dscuss/illustrations/20bit_pow_histogram.png