We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $$\mathcal {F}$$ . This allows a verifier to efficiently verify the correctness of any $$f \in \mathcal {F}$$ evaluated on a batch of n instances $$x_1, \ldots , x_n$$ , while only making $$\lambda $$ calls to an oracle for f (along with $$O(n \lambda )$$ calls to low-complexity helper oracles), for security parameter $$\lambda $$ . We obtain the following positive and negative results: