A third party that performs data stream computation is requested to return not only the solution to the computation, but also “annotations” to the original data stream. The annotations are then used by the data owner (in actuality, a “verifier” associated with the data owner) to check the results of the third party's computations. As implemented, the verifier combines the annotations with the original data, performs some computations, and is then assured of the correctness of the provided solution. The cost of verification is significantly lower to the data owner than the cost of fully processing the data “in house”.