The central goal of data stream algorithms is to process massive streams
of data using sublinear storage space. We study the following
natural question: Can the space usage of such algorithms be further
reduced by enlisting a more powerful ``helper'' who can annotate
the stream as it is read? We do not simply trust the helper, so we
require that the algorithm be convinced of having computed a correct
answer. We show
several upper bounds that achieve a non-trivial tradeoff between the
amount of annotation used and the space required to verify it.  We also
prove lower bounds on such tradeoffs, often nearly matching the upper
bounds, via notions related to Merlin-Arthur communication complexity.
Our results cover the classic data stream problems of selection,
frequency moments, and fundamental graph problems such as
triangle-freeness and connectivity.  
These questions are motivated by work in the database community on
verification and authentication issues that arise when outsourcing
databases or data streams to third parties.