A service receives from a sender service a digital message and a corresponding trace, which includes an ordered set of digital signatures of one or more services that participated in causing the service to receive the digital message. The trace may further specify an ordering of the one or more services, which may be generated according to the order of participation of these one or more services. The service may compare the received trace to recorded message paths to determine whether the ordering specified within the trace is valid. If the ordering is valid, the service may use one or more digital certificates to further verify the digital signatures included within the trace. If the service determines that these digital signatures are also valid, the service may process the message.