Based on comment:

Validating a signature should be relatively cheap, but I'm assuming this will happen within BlockHeader itself (since the signature will be in the block header).

Validating the rest would be relatively expensive:

Verifying the ZKP itself will probably be 10 - 20 ms.
We'll also need to compute the output note tree root, transaction commitment, account update commitment, and nullifier commitment. Depending on the number of transactions and their complexity, this could also be pretty significant (probably also on the order of 10 - 20 ms - though, would be good to test this at some point).
Not in this PR, but we should probably add ProvenBlock::validate() method to make sure the structure is consistent. Let's create an issue for this (unless we have one already).