the blockchain, as usual, is not necessary, the header is proof enough on that a penny worth of energy[0] was expended in generating the hash

[0] (or however much energy you want to demand before throwing the message in the spam folder - you just require whatever number of leading zeros in the hash ie crank up the difficulty, bitcoin's innovation was assigning ownership to these proofs-of-work via signatures and implementing a mechanism to update and broadcast that ownership)