The efficiencies of validity proofs