A first device in a network issues a proof-of-work challenge to a second device in the network. The second device computes a cryptographic function result to satisfy a criterion indicated in the challenge. The second device returns a challenge response comprising inputs to the cryptographic function that the second device used to compute the cryptographic function result satisfying the criterion. The first device, upon receiving the challenge response, verifies that the inputs to the cryptographic function yield a result satisfying the criterion. Responsive to verifying the challenge response, the first device updates a blockchain based upon the challenge response.