A decentralized key-value store that is tolerant to an active adversary is not a "very simple problem". A block-chain is actually a reasonable solution for this, see [1].

Not to say it's perfect, for sure.

[1]: http://blog.printf.net/articles/2015/05/29/announcing-gittor...