Elision in DID documents

This document outlines a mechanism that could enable elision of certain aspects of a DID document. The core idea is that we can define and register new types in the DID Extensions registry for elided content such as verification methods and service endpoints while still being conformant with the DID core data model.

For example we could define and register the type ElidedMultikey.

ElidedMultikey

An ElidedMultikey is a type of verification method. Instead of including the verification material in directly publicKeyMultibase a SHA256 hash of the verification material (including the multikey prefix) is first computed and then the bytes are multibase encoded using base58-btc.

Question: Should we just reuse the publicKeyMultibase value, or define a new property e.g. elidedMultibase.

An ElidedMultikey can be converted into a Multikey if an entity knows the verification material that was elided. First they check the elided publicKeyMultibase value matches the verification material. Then if equal, they substitute the ElidedMultikey verification method for a Multikey verification method using the verification material.

More precisely we can define two algorithms elide and reveal:

Elide Multikey

Takes as inputs a multikey verification method, vm and returns the corresponding ElidedMultkey verification method.

Set elidedVm to a copy of vm
Set pkMultibase to vm.publicKeyMultibase
Set keyBytes to the multbase decoding of pkMultibase
Set elidedBytes to the SHA256 hash of keyBytes
Set elidedMultibase to the base58-btc multibase encoding of elidedBytes
Set elidedVm.publicKeyMultibase to elidedMultibase
Return elidedVm

Reveal Multikey

Takes as inputs an ElidedMultikey verification method, elidedVm, an a publicKeyMultibase and returns the corresponding Multikey verification method.

Set elidedKeyBytes to the multibase decoding of elidedVm.publicKeyMultibase
Set keyBytes to the multibase decoding of publicKeyMultbase
Set hashKeyBytes to the SHA256 hash of keyBytes
If hashKeyBytes != keyBytes throw an InvalidElidedKey error
Set vm to a copy of elidedVm
Set vm.publicKeyMultibase to publicKeyMultibase
Return vm

Comments

A similar algorithm would be trivial for seviceEndpoints, modulo representing the hash as a URI.
This feels very similar to Bitcoin addresses. A Bitcoin address is a hash of a public key, at least some of them (P2PKH).
This has some implications for resolution, but I think this could be supported with DID Resolution Options similar to how we have thinking of sidecar. I.e. you have to know privately the key that was elided in a verification method, how you learn this is out of scope.
1. One option could be for this information to be added to the signature, again this is similar to Bitcoin.
Christopher wondered how this might support salts for the hashes. My initial thought is that would just be additional data that the revealing party would be required to know

An alternative

An alternative approach might be to define a verification method type ElidedVM or something. Instead of the elided value being the just the publicKeyMultibase, it could be the hash of the entire verification method object which I guess would need to be canonicalized first.

This would be a more generic and flexible approach, so maybe it is better. Not sure.

21/03/24 Update

Reacting to Christophers use case

The first use case is in support of principles of key separation and unnecessary disclosure of correlatable public keys. Best practices of key separation means not using the same keys for everything, and even further, if you have multiple devices, having different keys for each device. For instance, each of my development machines have their own set public keys, one for each proof-purpose which they support. I should not have to disclose all of my public keys for all of my device — instead, only when they are needed for their proof-purpose. With elision, I can commit to a public key and a proof purpose, but only reveal it to a verifier when they need it, and only cthe key that they need to verify. They can know it was committed previously, and that it should be accepted on the ~same trust level as the keys they've already accepted, as they were all committed together.

To achieve this, we would want to elide many keys in a single verification method. I think the proposed ElidedMultikey approach could adapted using merkle trees, such that a elided verificationMethod is a merkle root for a tree of keys.

The idea is still that given some set of data, it is possible to reveal a Multikey verification method that can be verified as being in the DID document. Then proof verification can proceed using that Multikey. In this case the set of data would be the a multikey AND a merkle proof.

Note, this is very similar to how Taproot works. Taproot, is a root of a taptree. A tree of scripts, that can be revealed along with a proof path. That way, you can commit to many different Bitcoin scripts and only reveal certain scripts at spend time.

For example, we could define a VM type ElidedMerkleMultikey, or something …

Elided Merkle Multikey

To generate a verificationMethod of the type ElidedMerkleMultikey, you would follow roughly these steps.

Generate all (pk,sk) key pairs you wish to elide within the VM
Construct a merkle tree, such that the leaves are the sha256 hash of the byte representation of the public key, pk, prepended with the correct multikey header bytes. Store the leaf index in the merkle tree for each public key
Compute the merkle root of the tree
Multibase encode the merkle root using base58-btc
Construct the verification method as follows:

{
    "id": "did:example:123#key1",
    "type": "ElidedMerkleMultikey",
    "merkleRootMultibase": <merkle-root>
}

Generating Proofs

To use one of the keys to generate a Data Integrity proof, you use the key as if it were a Multikey and follow whatever Data Integrity cryptosuite algorithm. However, when it comes to identifying the verification method used to generate the proof you must pass in the additional data. Maybe this could be done using query parameters?

The data that needs to be passed is:

A representation of the public key committed within the merkle tree
A proof path for that public key that can be verified against the merkle root

Imagine these are both base58-btc multibase encoded. Then perhaps we can use query parameters to identify this key?

For example

did:example:123#key1?multikey=<key_encoding>&merkleProof=<merkle_proof_encoding>

If that is the case, then the proof object would look something like this:

{
    "type": "DataIntegrityProof",
    "cryptosuite": "bip340-jcs-2025",
    "created": "2023-02-24T23:36:38Z",
    "verificationMethod": "did:example:123#key1?multikey=<key_encoding>&merkleProof=<merkle_proof_encoding>",
    "proofPurpose": "assertionMethod",
    "proofValue": "z3P1WFufkFdaA9HM9jd4SYrGFbYYKzymhoYoqLHSG2zVfhjaTXFtdiQ1EwBt8X11x6rPccMdQxmhcYTfd6btY2nWt"
}

I guess the verificationMethod id string might get quite large, depending how big the merkle tree is. But I think it is manageable.

Verifying a proof

Verifying this proof is relatively simple. The verifier just needs to be able to dereference the verificationMethod property to get a Multikey verification method and continue as normal.

So how might we derefence did:example:123#key1?multikey=<key_encoding>&merkleProof=<merkle_proof_encoding>

Some high level steps:

Resolve the DID document for did:example:123
Dereference the resource identified by did:example:123#key1?multikey=<key_encoding>&merkleProof=<merkle_proof_encoding>

This would involve, finding the verificationMethod at #key1, which is

{
    "id": "did:example:123#key1",
    "type": "ElidedMerkleMultikey",
    "merkleRootMultibase": <merkle-root>
}

Then attempting to reveal the elided Multikey using the multikey and merkleProof provided by the query. If successful, the result of dereferencing could look like this:

{
    "id": "did:example:123#key1?multikey=<key_encoding>&merkleProof=<merkle_proof_encoding>",
    "type": "Multikey",
    "publicKeyMultibase": <publicKey>
}