From the user side, something like:
Submit at time T a small fixed size (hash) piece of data X you want notarized.
Get back something you can present to others to prove X existed at time T.
(In practice the data likely involves signatures and I'm glosing over matters of how you use them at this layer.)
Now, suppose we want to make a system like this scale without needing a gigantic shared ledger.
The "get back something" above is potentially doing some heavy lifting. You can make the user responsible for carrying a fairly large number of entries as part of their proof, up to a next waypoint where the notary gets one or more other lower-traffic notaries (ones it's probably paying) to notarize its state.
Why is a machine-evaluable identity system interesting to begin with?
For me, it goes back to my thread on the end of Twitter, what is being lost, and what we eventually need to build in its place.
Particularly, the value Twitter had as a unified public social graph of curated trust-as-source-of-information relationships.
The same kind of trust-as-source-of-information has come up in #reprobuilds and software provenance fields.
@dalias
I wrote my master thesis on Reproducible Builds and transparency logs.
There are several papers published on this that I can find if it's of interest :)