Challenges in Understanding Spectrum of Integrity/Inspection/Validation/Verification/Confirmation/Revocation

(this is a pre-draft of a post to be an issue on https://github.com/w3c/vc-data-model/issues/ or possibly added to https://github.com/w3c/vc-data-model/issues/58 once it is more thought out)

As evidenced by the failure of polling in the W3C Verifiable Claims WG last week on the name of the role of Validator vs. Inspector, and the lively discussion in the WG meeting today https://www.w3.org/2017/07/11-vcwg-minutes.html, we lack a really good model for describing the multiple actions that happen in our verifiable claim architecture, in particular when blockchain-based DIDs are being used.

In addition, our whole industry has been terribly bad at the practical considerations as to the issues of how revocation should be designed. I personally have experienced this with SSL/TLS, which for almost a decade and a half had only lip-service support of revocation, and even now is still being challenged to deploy more advanced solutions

So I want to walk through DID:BTCR from the vantage point of a number of steps that fall into the Integrity/Inspection/Validation/Verification/Confirmation/Revocation spectrum of roles.

First, please forgive in advance the specific words I'm using below — they are used more to signify the different placeholders as opposed to a well thought out proposal as which words should be used.

In our #RebootingWebOfTrust User Story Alice, our pseudo-anonymous programmer. daughter of immigrants, has heard that Bob, a refugee advocate has a need a mobile phone app. Fearing that her own extended family might be harmed if she is revealed to be helping Bob, she wishes to introduce herself and present credentials that she is qualified for the work, but remain pseudo-anonymous.

So first she establishes a DID and self-signed DDO. She has a professional colleague and friend Donna with a public persona (i.e. not anonymous) who indirectly knows Bob through yet another colleague (i.e. Bob & Donna share a trust network but connected by multiple-degrees of separation).

Donna issues a Verifiable Claim that she "knows" Alice and she is willing to attest to her competence in mobile development, which Donna gives a signed copy of back to Alice. Alice counter-signs this claim and adds it to her DDO (this is something unique to the very self-sovereign BTCR method, and may not apply to other methods).

Alice then sends a response to Bob's request for programming assistance, along with the claim issued by Donna.

Now we dive into some mechanics:

Bob receives this offer from Alice (possibly itself a self-signed claim) along with the claim issued by Donna. The first thing his software does is do an INTEGRITY CHECK of the claim itself. Is it properly formed? Has it expired? Is it properly signed by the issuer? Is it properly countersigned by the subject? If it fails any of these INTEGRITY CHECKS, Bob will not even know about it, and the whole message and claims will be rejected.

The next thing the software MAY do is INSPECT INTO the claim the DID number found in Donna claim. This will typically be automatic, but if Bob is hyper-concerned about internet traffic correlation (as he is advocating against a nation-state) it may require a human to decide if they wish to proceed further. But Bob is an EU citizen and feels sufficiently protected, so his software is set to INSPECT INTO automatically.

The first DID is Donna's. His software INSPECTS INTO the Bitcoin Blockchain for the appropriate transaction, and then looks at the first TXOUT of that transaction to see if it has been spent. In this case, it has, so this transaction cannot be VALIDATED. However, it has not failed, so the software now goes forward to that new transaction (the "tip" of the DID chain).

This time the software INSPECTS INTO this transaction's first TXOUT, and is not spent and there is a properly formatted op_return pointing to a DDO, which reside's on Donna's github account. The software now INSPECTS INTO and finds the DDO.

Now the the software does an INTEGRITY CHECK on the DDO, and if is, then it VALIDATES the DDO by comparing it to the control key that is found from signature used to send transaction to the Bitcoin Blockchain that the INSPECTION CHECK revealed. If they match, both the DID and the DDO are now VALIDATED.

However, the claim itself was not signed by the control key so it is not VALIDATED yet. So the software INSPECTS INTO the DDO, and finds another key (either looking through all the appropriately listed keys, or possibly because of a hint added in the claim). If the signature on the claim matches, now the claim issuer is VALIDATED.

However, the claim makes a statement to yet other DID, so it not yet VERIFIED, only VALID. The software must now do the same set of operations on Alice's DID to INSPECT INTO her DID and determine if it too can be VALIDATED.

Finally, if both the issuer's DID and subject's DID are VALID, (which includes the previous INTEGRITY CHECK of Donna's claim and Alice's countersignature of Donna's signature on the claim) the claim is now VERIFIED (thus it is called a "Verifiable Claim").

However, this verified claim is not yet CONFIRMED. In order to be CONFIRMED, Bob's Web-of-Trust CONFIRMATION criteria needs to be met. In this case, Donna" is a third-degree connection, making Alice** a fourth-degree connection. Over half of the world is a fourth-degree connection!

In this case, the software kicks out the claim for Bob to make a decision on (i.e. the claim and DIDs are both VALIDATED and VERIFIED, but not CONFIRMED). He decides to look further into what Donna is willing to share in her DID. In this case, Donna is vaguely known to him ("a familiar stranger") and her github repository is active and has a long history of mobile development. He looks now at what Alice shares in her DID, and it is almost nothing, and has no personal info. However, her response to his request for proposal is interesting, and he hasn't found anyone yet, so he decides to CONFIRM and accept this claim to give her a trial.

If Alice fails her trial, Bob will change his criteria to never waste any time on her again, or even possibly never even bother to look at CONFIRMING any more Donna's claims (a locally-negative trust, but is non-transitive to others in the self-sovereign scenario required by the BTC method).

However, Alice doesn't fail her trial, and later Bob issues her a new claim saying that he also liked Alice's work, and maybe even issues a claim that countersigns Donna's original claim, showing appreciation for Donna's good recommendation.

(the next section will discuss when things go wrong, aka REVOCATION)

BTW, the logic of my ordering of these different spectrum words started with the name of the working group, Verifiable Claims.

INTEGRITY CHECK includes malformation and cryptographic signature or proof checks - this is defined by the signature system spec
INSPECT INTO means looking inside for something and then going outside to get it — this is defined by the data model spec
VALIDATION means that the conform to rules of the DID spec and the specific DID method.
VERIFICATION means that that everything is self-consistently INTEGRAL, the INSPECTIONS reveal no problems with VALIDITY, and thus the whole can be VERIFIED.
CONFIRMATION relies of the VERIFIABLE CLAIMS to then make possibly more human judgements on different trust models to be used by the Web-Of-Trust. It also somewhat analogous to Bitcoin's terminology, where transactions require multiple CONFIRMATIONS.
REVOCATION deals with the edge cases where things go wrong. There may need to be processes associated with "where things go wrong" at each the stages above, as revocation currently may be an overloaded term.

The topic of revocation will be much harder to define — in fact, we probably need as many stages and roles for it alone as the above has about the spectrum from integrity to confirmation.

What they all the forms of revocation have in common is to help us with deal with the edge cases when things can go wrong.

The simplest case should be expiration. However, does the fact that someone have a certificate that says they were married in 2018 and the claim expired in 2028 and the issuer isn't around anymore (or doesn't issue marriage certs to gay couples anymore) mean that the claim is invalid? Or that the college course I took on English History is no longer valid? Or maybe the Javascript course I took SHOULD be invalid because no one uses version 8 anymore. Especially in a world where we can now do time stamps, what does an old but expired claim mean? Who decides — the issuer, the subject, or the holder that the claim was given to?

What if it isn't precisely expiration, but that various conditions of the issuer or other requirements are no longer true, but not entirely false? A subscription has expired, but the check is on the way. A continuing education requirement didn't happen, but is in progress? Something is being disputed in court of law. Then there there may be requirements that the holder has that are higher than that of the issuer? Or that the holder of the claim don't care about X and Y, but do care about Z?

One suggestion by many cryptographers is to move toward very short lived keys, or even keys that are used only once. Tricks like HD keys and different forms of blinding can allow this. But then in Verifiable Claims, there is a value to persistence and an appropriate latency where holders may "hold" on to claims for some time, and the benefits of this architecture of holding may be lost if they essential have to recheck too often.

Another use case that should be easier is what to do when a key is compromised. Clearly ideally the key should be rotated so that no new claims are issued, and that can be a step in the INTEGRITY CHECK and INSPECTION tasks above. But the real challenge is what does that mean for various parties that relied on those keys in the past? Does everyone who got a diploma in 2020 have to get a new one when the key was compromised in 2022? What happens if a key can't be rotated? It is a difficult challenge now when you have a hierarchy of keys and a high level one is compromised, but a web-of-trust may be more complex due to the intertwining of claims and counterclaims. Can I countersign your claim, then revoke it, and hurt your claim?

Another challenge is when the keys are all valid, but fraud or faulty evidence is involved. That information revealed didn't conform to HIPPA or other privacy laws, etc. How do the parties notify each other? As Peter Wuille said in #2 and covered again in #25 censorship resistance is very important to revocation.

Another challenge is that of changes, of requirements, of affiliation, superseded, cease of operation, etc. In my own case, I taught for 5 years for a leading graduate school in sustainable business. Along the way, it change it's name from bgi.edu to pinchot.edu, and according the rules of .edu, you can't have two domains, so no forwarding of emails was allowed. Now the school has been acquired by presidio.edu, an entirely different legal organization, and all my mail to both academic email address now all bounce, and all staff at the original institution are gone (the admin offices moved from Seattle to SF). It is hard enough for me as a former staff, but what about the 14 years of graduates of the school, which was prestigious for its type, accredited, etc. when you can't even go to the website listed on their diplomas? Some is true for former employees, change of roles, etc. and apply to issuers, subjects, and holders.

In most cases it is issuers that revoke, but in self-sovereign identity, where a subject has more equality with an issuer, a subject may wish to revoke. In the even more radical self-sovereign BTCR method, all claims must also be countersigned by the subject, what happens when the subject wants to revoke an issuers claim? How do they notify all the holders?

With multisig, we also have the ability to have our peers revoke our claims. I could set it up such that if 2/3rds of my peers see my digital world misbehaving, and thus evidence of a compromise (of my keys or my mind), they could rotate my keys to a guardian until we figure out what went wrong.

If the goal of revocation is to help deal with the edge case, they ideally should also allow the "human" element to be able to step in. We don't want the tyranny of the algorithm in all cases. If there is a volcanic disruption in Seattle or a hurricane in Miami, we don't want a bunch of revocations forcing house liens and compounding the problems that the residents who are recovering are having.

Finally, revocation can be an attack vector for bad actors. How do we prevent that? What about sybil attacks? Ransomware? In the case of BTCR, bad actors can also be state actors. What if China tells a bunch of their citizens and companies to revoke claims, but the EU says no. Who do you listen to?

I'm fairly sure that I've not covered the whole breadth of the issues possible with revocation, and I certainly don't have any easy answers, but I hope this is a good start toward thinking about the problem.

(The next section will discuss what might be possible for Revocation for the initial implementation of BTCR)

In our user story of Alice, the Syrian Hacker Army is targeting her as the author of an Android app that helps Syrian refugees communicate with the families back home and send them care packages through a random peer-to-peer network of people sharing their car trunk capacity. An Uber of small gifts, an AirBNB of trunk space.

Alice has been careful with her cryptographic keys, but she has prepared herself. The special set of public keys that are associated with this app are listed in her DDO, and she has a password protected QR-code of the owner key for the current DID and DDO, but the control keys to update the DDO to a new transaction is with a friend in England locked on a hard drive.

Unfortunately, while traveling through Turkey, Alice's laptop is stolen. She is suspicious that someone might be targeting her.

The first thing she could do is just revoke and abandon the DID by simply spending the tip address. However, she doesn't have the control keys to enable that DID control key rotation transaction—they are in England. She does however hold the current owner key, so she can use that to update the DDO object that might be a possibly compromised key. She puts a "hold" notice in the DDO, and adds a timestamp to warn people to no longer rely on values in the current DID transaction until resolved, and wait for the new transaction on the tip.

When she returns home to England, she spends the tip, revoking the old owner key, and enrolling the old control key as the new owner key. A new address is posted which will be the next control key and the new "tip".

She now updates the DDO itself, signing it with the owner key just enrolled. She has no evidence of any key compromise yet, but she in her DDO that only claims issued her using her revoked old owner key are valid if they were dated before the time the key was stolen, and that any claimants should request to update claims if possible. As all of her claims are timestamps, there is no way for someone to fake a claim even if they break her old key, as the signature may be valid, but the timestamp is not.

It is also possible that she could have set up her control key to be 2 of 4 multisig, with keys held by her trusted colleagues Bob, Carol and Donna. In this case, if two of them observed bad behavior in claims being issued by the old DID/DDO, or if she was able to call at least two of them, they could immediately rotate the control keys, and give her the new control key when she gets home. She maybe even already has the new control key, at it could have been generated by an xpub her friends share (however, this technique does require two transactions rather than one for every control key rotation).

Finally, at some point in the future she passes this mobile project on to another team to develop, and she gracefully "retires" the DID/DDO pair with a gentle revocation and no new possible control key. However, all of her non-expiring claims are still valid — she didn't issue many, but a few are important and they need to remain.

A reminder: there will likely in time be other specific techniques for doing revocation, see #2 and #25.

A question for @jandrieu: I know that you like to keep your 15 step use cases to be technology-agnostic, but what steps in your model am I missing from the above?

I'd love to get from our graphic facilitators a little graphic image based on the stories above for each of your 15 steps, and present those 15 steps and how they work with the current BTCR concept as a slide deck.

@ChristopherA I'll dive into the mapping to 15 steps later tonight, but I wanted to suggest a distinction that I hope will help reduce the complexity of revocations.

Without some sort of general knowledge engine, aka, AI, we can never algorithmically know if any given statement is true or justified or appropriate. We may be able to tell if it is intended as a statement of fact rather than opinion through semantic analysis or rigorous RDF predicates, but in essence, the merit of a "statement" that is the payload of a verifiable claim is not algorithmically auditable.

What we can do is verify the integrity of the payload. That is, that the payload is, to all algorithmic tests, the payload that was published by the author and remains unrevoked. Or to use VC terms, the statement is verifiably the same as the one made by issuer (as defined as the controller of the issuer's keys) and none of the optional revocation mechanisms show it revoked.

The distinction I suggest is that revocation should only be applied to the verification of the integrity of the payload, and never to the integrity, validity, applicability, or truth of the statement.

So your questions:

However, does the fact that someone have a certificate that says they were married in 2018 and the claim expired in 2028 and the issuer isn't around anymore (or doesn't issue marriage certs to gay couples anymore) mean that the claim is invalid?

It means the claim can no longer be verified. It's like presenting an expired insurance card to a cop in a traffic stop. It doesn't mean anything about whether or not there is currently valid insurance. Just that the credential presented is not itself verifiable proof of current insurance. Because of the risk of compromised keys, it should, in fact be treated as a non-statement, a no-op. However, it may be useful forensically to seek out alternative proof of valid insurance. For example, the insurance company and contract id may still be sufficient for looking up a current verifiable claim. So it isn't completely useless.

Or that the college course I took on English History is no longer valid?

That begs the question of what "valid" means. For VC conversations, I'm extremely careful about using valid to mean well-formed in terms of the data-model and verified to mean algorithmically tested (based on the signature and revocation method).

To say that the course is invalid, begs a further question. Valid for what?

I had a circuitous route through my undergraduate degree and there was an "understood" rule that courses taken over ten years ago were no longer valid for graduation requirements. There was also an explicit rule that one could graduate under any catalog under which they were a student. Turns out the graduation requirements changed during my 13 year adventure. Because of fears that my early coursework might not be valid, I was accommodating rather than confrontational with the Registrar when reviewing my graduation requirements, which mean I took a few extra courses not in the original requirements. I didn't argue about my right to graduate under the older catalogs and she never brought up my "invalid" courses.

The point of that entire story is that the merit of a given statement is entirely contextual and beyond the scope of what verifiable claims can address. What we can do is verify the payload in question was both initially issued by someone with the keys to sign the claim and that since then, no one with the appropriate revocation authority has revoked that claim.

That's it.

Anything beyond the verification and revocation mechanism is policy and context.

That said, I do think there is a place for a general policy hook in both credentials and entity profiles. I raised this issue in https://github.com/w3c/vc-data-model/issues/48 In brief, issuers should be able to specify terms of use of a credential, which are signed (and hence verifiable) and holders should similarly be able to specify terms of use for an entity profile.

The question of what those terms are and how we specify them is a whole other question.

That suggests strongly to me that any notion of expiry of a claim--outside the terms of use--should only be treated as a component in the verification of the claim and not the expiration of the statement.

For example, for the insurance case, I may have a VC that is short-lived because it's tied to having paid my insurance this month. It may contain a credential describing an insurance policy that expires next year. The short-lived claim expiry should apply only to its acceptability by an inspector, independent of the expiration of the underlying policy as represented in the credential. Once the VC is accepted by the inspector, they may then choose to rely on the expiration in the payload for triggering a notification that I need to renew my proof of insurance. If I were to present that original VC after the short-lived expiry, it should be treated by the inspector just as if the cryptographic check of the signature failed.

After sleeping on it, I think we also need to bring up the update/amend techniques. I raised this a year ago in the VCTF, but didn't get traction on it.

However, if DIDs are specifically designed to enable updating DDOs without changing the URL (and they are), and if DDOs are verifiable claims (and that has been proposed), then we are explicitly building an architecture to update claims.

Yes, the operation is most likely replace, but this entire function has been adopted without a deep discussion of what it would mean to amend/replace a claim.

A key distinction from revocation is that this is revocation with a replacement. So that a recipient of the amended claim, when checking for revocation, could retrieve the replacement claim. Currently, other than the implicit relationship of dereferencing DIDs to get a "current" DDO and the reciprocal DID entry in the DDO, we don't have any discussion about this replacement architecture.

We ran into this with Joram 1.0.0, as he changed camps and the new pharmacist didn't find his prescription because of filters limiting his search to 'scripts from his camp. He updated the data store (somehow) so that future prescription searches would find the new one, and somehow, magically, the prior 'script was no longer valid for fulfilment.

A key question is whether or not the Holder has any role in this update. Perhaps it is the Holder's job to check the revocation/update status before giving a VC to an inspector and if they fail to do that, the claim is always subject to updates (potentially leaking unintended information). Or we could make the case that the ONLY operation is revocation, but I think that misses some use cases where we want a consistent identifier to always resolve to the latest claim, even if it has changed. Like with a DDO.

Of course, with DDOs, the holder and issuer are identical, so the self-referential loop from DID->DDO->DID enforces currency.

But what about other use cases?

In my view, I don't think DDOs should be claims, but rather, they may embed (or link to) credentials that contain claims.

When dereferencing a DID, you get a DDO, which is a document that contains a graph (or RDF dataset) where the main node in the graph lists relationships (RDF predicates) between the entity the DID identifies and other nodes or literals. One such relationship could be a list of credentials belonging to the entity. These credentials may be self-issued (where the issuer is the DID entity and is identified by its DID) or they may be issued by a third party.

In other words, a DDO is just an "Entity Profile" from the Verifiable Claims Data Model. It is one view of the entity identified by the DID (a self-sovereign, self-reported view) -- and it may contain credentials that include verifiable claims that assert the properties and values found in the profile.

I'm short on time this week so I can't elaborate much further at the moment, but I wanted to put this out there.

That sounds right, @dlongley

This issue was moved to WebOfTrustInfo/rebooting-the-web-of-trust-fall2017#12

WebOfTrustInfo / btcr-hackathon-2017

Challenges in Understanding Spectrum of Integrity/Inspection/Validation/Verification/Confirmation/Revocation #33