  Network coding achieves optimal throughput in multicast networks. However,
throughput optimality \emph{relies} on the network nodes or routers to code
\emph{correctly}. A Byzantine node may introduce junk packets in the network
(thus polluting downstream packets and causing the sinks to receive the wrong
data) or may choose coding coefficients in a way that significantly reduces the
throughput of the network.
  Most prior work focused on the problem of Byzantine nodes polluting packets.
However, even if a Byzantine node does not pollute packets, he can still affect
significantly the throughput of the network by not coding correctly. No
previous work attempted to verify if a certain node \emph{coded correctly using
random coefficients} over \emph{all} of the packets he was supposed to code
over.
  We provide two novel protocols (which we call PIP and Log-PIP) for detecting
whether a node coded correctly over all the packets received (i.e., according
to a random linear network coding algorithm). Our protocols enable any node in
the network to examine a packet received from another node by running a
"verification test". With our protocols, the worst an adversary can do and
still pass the packet verification test is in fact equivalent to random linear
network coding, which has been shown to be optimal in multicast networks. Our
protocols resist collusion among nodes and are applicable to a variety of
settings.
  Our topology simulations show that the throughput in the worst case for our
protocol is two to three times larger than the throughput in various
adversarial strategies allowed by prior work. We implemented our protocols in
C/C++ and Java, as well as incorporated them on the Android platform (Nexus
One). Our evaluation shows that our protocols impose modest overhead.
