  A central problem in proof-theory is that of finding criteria for identity of
proofs, that is, for when two distinct formal derivations can be taken as
denoting the same logical argument. In the literature one finds criteria which
are either based on proof normalization (two derivations denote the same proofs
when they have the same normal form) or on the association of formal
derivations with graph-theoretic structures (two derivations denote they same
proof when they are associated with the same graph). In this paper we argue for
a new criterion for identity of proofs which arises from the interpretation of
formal rules and derivations as natural transformations of a suitable kind. We
show that the naturality conditions arising from this interpretation capture in
a uniform and elegant ways several forms of "rule-permutations" which are found
in proof-systems for propositional, first- and second-order logic.
