Aside from doing the same work X% of the time I can think of only one other option. The network could be overloaded with additional nodes such that it would also compute some function on the input data with the known output. For example a hashing function. Having said that, single pass does not strike me as a particularly useful unit of work. You would want to batch the samples, and that leads back to a strategy of verifying a portion of them based on the host trust metric.