Intriguing concept, but malicious is orthogonal to illegal, although they are often correlated.<p>Namely, in several jurisdictions, including the one that the paper is presented in, (D)DOS is illegal -- a different point to debate -- making this <i>particular</i> proof-of-work <i>both</i> malicious and illegal.<p>A more intriguing one would be one that's merely (debatably) malicious but not <i>per se</i> illegal, like, say, password hash cracking, which is similar enough to existing PoW schemes to make feasible.