A system and methods are provided for verifying proof of transit of network traffic through a plurality of network nodes in a network. Information is obtained about a packet at a network node in a network. The information may include in-band metadata of the packet. Verification information is read from in-band metadata of the packet. Updated verification information is generated from the verification information read from the packet and based on configuration information associated with the network node. The updated verification information is written back to the in-band metadata in the packet. The packet is forwarded from the network node in the network.