We propose a new approach, proof-carrying data (PCD), which circumnavigates the threat of faults and leakage by reasoning about properties of the output data, independently of the preceding computation. In PCD, the system designer prescribes the desired properties of the computation's outputs. Corresponding proofs are attached to every message flowing through the system, and are mutually verified by the system's components. Each such proof attests that the message's data and all of its history comply with the specified properties.
We construct a general protocol compiler that generates, propagates and verifies such proofs of compliance, while preserving the dynamics and efficiency of the original computation. Our main technical tool is the cryptographic construction of short non-interactive arguments (computationally-sound proofs) for statements whose truth depends on "hearsay evidence": previous arguments about other statements. To this end, we attain a particularly strong proof of knowledge.
We realize the above, under standard cryptographic assumptions, in a model where the prover has black-box access to some simple functionality — essentially, a signature card.