Systems, methods, and computer-readable media are provided for network access technology (NAT)-based packet network provenance. In disclosed embodiments, each node in a network encapsulates and/or encodes received packets with network interface information in addition to attestation information. The network interface information indicates a type of NAT used to forward the packet to a next node or hop in a network path. Each node in the network implements protocol stack that includes a multi-interface translation layer below a networking layer and above the layer 2 protocol stacks of various communication protocols. The multi-interface translation layer determines the type of NAT to be used to forward received packets to the next hop, and encapsulates the received packets with an indication of the determined NAT to be used to forward the packet. Other embodiments are disclosed and/or claimed.