Add `ProvenanceStorageInterface` as discussed during backend design

Rework backend-related classes to properly use the new interface. Adapt tests to the new structure as well.

Depends on !55 (closed)

---

Migrated from D5947 (view on Phabricator)