A system and methods are provided herein for verifying proof of transit of traffic through a plurality of network nodes in a network. In one embodiment, a method is provided in which information is obtained about a packet at a network node in a network. The information includes in-band metadata. Verification information is read from the in-band metadata. The verification information for use in verifying a path of the packet in the network. Updated verification information is generated from the verification information read from the packet. The updated verification information is written to the in-band metadata of the packet, and the packet is forwarded from the network node in the network.