Merkle tree

— 2001, Josep Domingo-Ferrer, Mobile Agent Route Protection through Hash-Based Mechanisms, C. Pandu Rangan, Cunsheng Ding (editors), Progress in Cryptology - INDOCRYPT 2001: 2nd International Conference, Proceedings, Volume 2, Springer, LNCS 2247, page 17, The second solution uses Merkle trees and minimizes the cost of route protection by the agent owner, so that a single digital signature suffices to protect the whole route; for hosts along the route, the verification cost is similar to the cost of previous schemes in the literature, namely one digital signature verification per route step.