Технология блокчейн основана на принципе доказательства работой «Proof-ofwork». Суть данного принципа состоит в том, что некоторое событие (например, перевод денежных средств с одного счета на другой) становится значимым только после того, как оно подтверждено определенным объемом вычислительной работы. Соответственно возникает потребность в вычислительных задачах, над которыми такую работу можно производить, причем на решение этих задач будет тратиться практически вся вычислительная мощность блокчейн-сети. На сегодня в качестве таких задач получили распространение «хэш-головоломки» – задачи поиска битовой строки с хэшем, удовлетворяющим определенным условиям. Существенным недостатком хэш-головоломок является отсутствие у них какого-либо полезного применения за пределами технологии блокчейн. В работе описываются подходы к решению задачи «Useful Proof-of-work for blockchains», а именно предлагается рассматривать в качестве вычислительных задач для доказательства работой возникающие на практике индивидуальные представители NP-полных задач, которые могут решаться, например, SAT- или LLL-решателями. Отдельной проработки требует вопрос об использовании FPT-задач. Предлагаемый подход позволяет обеспечить следующие свойства вычислительных задач для доказательства работой: полезность, управляемость сложностью задач (через изменение размерности, выбор задач определенного вида, указание точности необходимого решения), массовость. При этом допускается, что не каждая решенная задача может оказаться полезной, однако предоставляется возможность решать с помощью технологии блокчейн задачи, возникающие на практике. Кроме прочего, таким образом становится возможным сопоставить стоимость виртуальной криптовалюты через затраты электроэнергии при ее генерации с практическим результатом от решения вычислительных задач. Наиболее трудными вопросами в контексте рассматриваемого подхода являются реализация связи событий и задач, обеспечивающих эти события вычислительной работой, и реализация системы анализа сложности задач. Статью следует воспринимать как программу исследований, поскольку многие технические детали требуют отдельной проработки.