Ещё до создания биткойна придумали Proof of work для почты. Кто хочет отправить письмо выполняет сложную и бесполезную вычислительную задачу которую легко проверить.
Сейчас бы я сделал протокол что к письму прикреплялись монета. Если спам то она просто не возвращалась .