# did:merkle

aka One Time Merkle Proofs for less correlatable Credentials
aka One Time Revealable Credentials

by
[Joe Andrieu (Legendary Requirements)]([e-mail]),
[Frederic Martin (myDid)]([e-mail]),
[Imad El Aouny (myDid)]([e-mail]),
[Lohan Spies (DIDx]([e-mail])[ / IOHK)]([e-mail])

License [CC-BY 4.0](https://creativecommons.org/licenses/by/4.0/)

Group credentials offer an opportunity for privacy preserving verification of group membership.

## Same Credential to a all members of a group

We want to issue the exact same VC to all members of a group so that each VC reveals no information about who is a member of the group. We propose to do this by issuing a VC with subject id of the Merkle root of cryptographic identifiers controlled by various group members. Upon presentation of that VC to a Verifier, group membership can be verified by testing that the cryptographic id that signs the VP is in the merkle tree. We create a did:merkle and merkleProof proof type so that the VC is issued to did:merkle and the VP includes TWO proofs. One is the traditional tamper-evident signature. The second is the merkleProof. For additional correlation protection, the issuer may include multiple cryptographic ids for each recipient, allowing recipients to use different proofs with different verifiers. This solution is cryptosuite agnostic and does not depend on novel cryptography such as group signatures (or ZKP methods).

Anti-correlation feature is the combined result of provable group membership and multiple proofs per member.

## Option: Different credentials to different members of a group

As we issue a credential to the Merkle root of a Merkle tree of members, is is possible to use a Merkle root of a Merkle tree for credential attributes and values.

>This won't be the main subject of this paper. A separated document will be proposed later about using a "second Merkle tree for credentials".

## Creative Brief

### Audience
Technical: Developers, Standards advocates
Practical: Regulators, Product Managers, CEOs

### Change in behavior
We want readers to adopt this technology for appropriate use cases. Secondarily, we want them to contribute to a conversation about how to better support individuals in their group interactions.

### Key Points
1. Mathematically, anonymity can be expressed as the degree to which an partially identified party can be confused with other parties.
2. Group membership is proven without revealing the members of the group
3. The same Verifiable Credential is issued to all members of the group, making the group membership aspects of the VC devoid of any personal data and personally identifiable information. Issuers must take care to not put other personal data in the shared VC.
4. Uses well-proven, tested cryptography
5. VC issuers embed multiple cryptographic identifiers for each member to enable different proofs for different verifiers. This is a flexible policy choice by the issuer.
6. Wallets need to track with proofs have been distributed to minimize re-use.
7. Issuers may support automated refresh properties
8. Issuers can selectively revoke the VC for particular members
9. An Account Extended Public Key can be given by the holder to the issuer so the issuer can derive HD pub keys on his side (and be reassured these keys are belonging/linked to the same holder, or at least the same "seed")
10. Implementation Guidance
a. Wallets would benefit from using HDKeys for generating the ids used in the merkle tree.
11. Opportunities for future evolution
a.Use HDKeys in the merkle tree (so wallets give the issuer a master pubkey rather than individual keys)
b. Additional claim content could be indexed in the merkletree
c. A did:indirectMerkle could allow a decentralized registry to provide the "current" merkle root

### Output
1. DID Specification
2. Revocation Specification for Group VC: Member Revocation
3. White paper on using did:merkle to improve privacy for VCs related to group membership

## DID Method Name
A merkle DID is immutable and cannot be updated or deactivated.

The namestring that shall identify this DID `method-name` is: `merkle`.

A DID that uses this method MUST begin with the following prefix `did:merkle`. The prefix string MUST be in lowercase. The remainder of the DID after the prefix, is specified below:

### Method Specific Identifier
The DID merkle method-specific identifier (merkleroot-id) is made up of a root hash of a merkle-tree.

### merkle DID method syntax

merkle-did         = "did:merkle:" merkleroot-id
merkleroot-id =    *( *idchar ":" ) 1*idchar
idchar             = ALPHA / DIGIT / "." / "-" / "_" / pct-encoded
pct-encoded        = "%" HEXDIG HEXDIG

### Examples of `did:merkle` identifiers

An example of a DID merkle:

did:merkle:7Tqg6BwSSWapxgUDm9KKgg

An example of a DID merkle URL (used for verifying membership)

did:merkle:7Tqg6BwSSWapxgUDm9KKgg?leaf=did:example:abc&proof=hash1:hash2:hash3#key1

The fragment, if any, is applied to the resource at the leaf.

## Multihash
https://github.com/multiformats/multihash

<varint hash function code><varint digest size in bytes><hash function output>

NOTE: TURN INTO ABNF
https://datatracker.ietf.org/doc/html/draft-snell-multihash-00

   varint-terminator = %x00-7f
   varint-continuation = %x80-ff
   unsigned-varint = *8varint-continuation varint-terminator

## Multibase
https://github.com/multiformats/multibase

base-identifier = <ascii character>
multibase = base-identifier {base-encoded-data}

## DID Documents
A DID Document associated with a merkle DID is deterministically generated to enable DID-aware software to verify actions taken by a member of the group. The [representation of a when requested for production](https://www.w3.org/TR/did-core/#representations) MUST meet the DID Core specification.

### Deterministic DID Document
**Example 1**

{
  "@context": "https://www.w3.org/ns/did/v1",
  "id" : "did:merkle:zH3C2AVvLMv6gmMNam3uVAjZpfkcJCwDwnZn6z3wXmqPV"
}

## Key Agreement
It's not clear we can do classic key agreement as a verification relationship because we are not able to perform encryption or decryption just because we have the did:merkle. In an interactive situation, a controller **could** give the did:merkle along with a merkle_path and their key to enable encryption... but if you are already in an interactive engagement, one can just first prove membership by authentication, then bootstrap a key for encryption/decryption.

## VC Issued to a did:merkle group

Inside example below:
* **did:ex:italy** is the did of the issuer, it can be any form of did (ex: did\:key:ab37dfa[...])
* **"citizenship": "it"** are the attribute and value commonly shared by all members of the group (they all have italian citizenship)
* **did:merkle:zH3C2AVvL[...]** is the did for the group of holders

{
  "@context": [
    "https://www.w3.org/2018/credentials/v1",
    "https://www.w3.org/2018/credentials/examples/v1",
  ],
  "type": [
    "VerifiableCredential"
  ],
  "issuer": "did:ex:italy",
  "issuanceDate": "2010-01-01T19:23:24Z",
  "credentialSubject": {
    "@context": "https://github.com/WebOfTrustInfo/rwot11-the-hague/raw/master/draft-documents/didmerkle/context",
    "id": "did:merkle:zH3C2AVvLMv6gmMNam3uVAjZpfkcJCwDwnZn6z3wXmqPV",
    "citizenship": "it"
  },
  "proof": {
    "type": "RsaSignature2018",
    "created": "2017-06-18T21:19:10Z",
    "proofPurpose": "assertionMethod",
    "verificationMethod": "did:ex:italy#key-1",
    "proof": "eyJhbGciOiJSUzI1NiIsImI2NCI6ZmFsc2UsImNyaXQiOlsiYjY0Il19..TCYt5XsITJX1CxPCT8yAV-TVkIEq_PbChOMqsLfRoPsnsgw5WEuts01mq-pQy7UJiN5mgRxD-WUcX16dUEMGlv50aqzpqh4Qktb3rk-BuQy72IFLOqV0G_zS245-kronKb78cPN25DGlcTwLtjPAYuNzVBAh4vGHSrQyHUdBBPM"
  }
}

## VP (with VC) presented by a member of a did:merkle group

{
  "@context" : ["https://www.w3.org/2018/credentials/v1"],
  "type" : "VerifiablePresentation",
  "verifiableCredential" : {
      "@context": [
        "https://www.w3.org/2018/credentials/v1",
        "https://www.w3.org/2018/credentials/examples/v1"
      ],
      "type": [
        "VerifiableCredential"
      ],
      "issuer": "did:ex:italy",
      "issuanceDate": "2010-01-01T19:23:24Z",
      "credentialSubject": {
        "@context": "https://github.com/WebOfTrustInfo/rwot11-the-hague/raw/master/draft-documents/didmerkle/context",
        "id": "did:merkle:zH3C2AVvLMv6gmMNm3uVAjZpfkcJCwDwnZn6z3wXmqPV",
        "citizenship": "it"
      },
      "proof": {
        "type": "RsaSignature2018",
        "created": "2017-06-18T21:19:10Z",
        "proofPurpose": "assertionMethod",
        "verificationMethod": "did:ex:italy#key-1",
        "proof": "eyJhbGciOiJSUzI1NiIsImI2NCI6ZmFsc2UsImNyaXQiOlsiYjY0Il19..TCYt5XsITJX1CxPCT8yAV-TVkIEq_PbChOMqsLfRoPsnsgw5WEuts01mq-pQy7UJiN5mgRxD-WUcX16dUEMGlv50aqzpqh4Qktb3rk-BuQy72IFLOqV0G_zS245-kronKb78cPN25DGlcTwLtjPAYuNzVBAh4vGHSrQyHUdBBPM"
      }
  },
  "proof": {
    "type": "RsaSignature2018",
    "created": "2018-09-14T21:19:10Z",
    "proofPurpose": "authentication",
    "verificationMethod": "did:merkle:zH3C2AVvLMv6gmMNm3uVAjZpfkcJCwDwnZn6z3wXmqPV?leaf=did:key:abc&path=hash1:hash2:hash3", 
    "challenge": "1f44d55f-f161-4938-a659-f8026467f126",
    "domain": "4jt78h47fh47",
    "jws": "eyJhbGciOiJSUzI1NiIsImI2NCI6ZmFsc2UsImNyaXQiOlsiYjY0Il19..kTCYt5
      XsITJX1CxPCT8yAV-TVIw5WEuts01mq-pQy7UJiN5mgREEMGlv50aqzpqh4Qq_PbChOMqs
      LfRoPsnsgxD-WUcX16dUOqV0G_zS245-kronKb78cPktb3rk-BuQy72IFLN25DYuNzVBAh
      4vGHSrQyHUGlcTwLtjPAnKb78"
  }
}

## VC Issued by a member of a did:merkle group
(not quite complete)

{
  "@context": [
    "https://www.w3.org/2018/credentials/v1",
    "https://www.w3.org/2018/credentials/examples/v1"
  ],
  "type": [
    "VerifiableCredential"
  ],
  "issuer": "did:merkle:zH3C2AVvLMv6gmMNam3uVAjZpfkcJCwDwnZn6z3wXmqPV?did=XYZ&proof=123",
  "issuanceDate": "2010-01-01T19:23:24Z",
  "credentialSubject": {
    "@context":"https://github.com/WebOfTrustInfo/rwot11-the-hague/raw/master/draft-documents/didmerkle/context",
    "id": "did:merkle:zH3C2AVvLMv6gmMNam3uVAjZpfkcJCwDwnZn6z3wXmqPV",
    "citizenship": "it"
  },
  "proof": [
    {
      "type": "merkleProof",
      "created": "2017-06-18T21:19:10Z",
      "proofPurpose": "assertionMethod",
      "verificationMethod": "did:merkle:abc?did=XYZ#proof-1",
      "signature": "eyJhbGciOiJSUzI1NiIsImI2NCI6ZmFsc2UsImNyaXQiOlsiYjY0Il19..TCYt5XsITJX1CxPCT8yAV-TVkIEq_PbChOMqsLfRoPsnsgw5WEuts01mq-pQy7UJiN5mgRxD-WUcX16dUEMGlv50aqzpqh4Qktb3rk-BuQy72IFLOqV0G_zS245-kronKb78cPN25DGlcTwLtjPAYuNzVBAh4vGHSrQyHUdBBPM"
    },
    {
      "type": "RsaSignature2018",
      "created": "2017-06-18T21:19:10Z",
      "proofPurpose": "assertionMethod",
      "verificationMethod": "did:merkle:abc?did=XYZ#key-1",
      "merkleProof": "eyJhbGciOiJSUzI1NiIsImI2NCI6ZmFsc2UsImNyaXQiOlsiYjY0Il19TCYt5XsITJX1CxPCT8yAV-TVkIEq_PbChOMqsLfRoPsnsgw5WEuts01mq-pQy7UJiN5mgRxD-WUcX16dUEMGlv50aqzpqh4Qktb3rk-BuQy72IFLOqV0G_zS245-kronKb78cPN25DGlcTwLtjPAYuNzVBAh4vGHSrQyHUdBBPM"
    }
  ]
}

## DID transaction operations

### Create DID
Steps to create a merkle DID:

                               ┌(Hash 0-0-0)─< did:key:JulietPubKey1
                    ┌(Hash 0─0)┤     
                    │          └(Hash 0─0-1)─< did:key:FedericoPubKey1
           ┌(Hash 0)┤  
           │        │          ┌(Hash 0─1-0)─< did:key:JulietPubKey2
           │        └(Hash 0-1)┤     
  (Merkle  │                   └(Hash 0─1-1)─< did:key:MarioPubKey1
─- Root  --┤  
   Hash)   │                   ┌(Hash 1-0-0)─< did:key:JulietPubKey3
           │        ┌(Hash 1-0)┤     
           │        │          └(Hash 1-0-1)─< did:key:MarioPubKey2
           └(Hash 1)┤  
                    │          ┌(Hash 1-1-0)─< did:key:MarioPubKey3
                    └(Hash 1-1)┤
                               └(Hash 1-1-1)─< did:key:FedericoPubKey2 

1. Holders share a set of `n` public keys or DIDs with the issuer
2. The issuer decide the batch size for issuance of the group credential
3. Once all holders `n` public keys or DIDs are collected the issuer generates a merkle-tree where each leave in the merkle-tree represents a hash of a single public key or DID
4. The issuer use the merkle-root hash as the DID identifier
5. The merkle DID can now be constructed by appending the merkle-root hash to `did:merkle`
6. Merkle DID example: `did:merkle:abc`

### Resolve DID

### Update DID
Merkle DIDs are immutable and cannot be updated.

### Deactivate DID
Merkle DIDs are immutable and cannot be deactivated.

## Security Considerations
1. Hash algorithm being used and security issues with MD5 as example

## Privacy Considerations
1. Issuers must ensure that no PII is exposed via the verifiable credential issued to the group
2. The quality of the Merkle tree has to be assured by the issuer (high number of different people and keys)

## References

## TODO:
1. optional: if we want to federate more users inside updated merkle tree, we may define new ways to sent new updated merkle proofs to existing users.

as an example :
- Sophia can use her first key (did\:key:SophiaPubKey1) to show only her nationality
- she will provide:
- merkle proof for leaf H0-1-1
- content of leaf H0-1-1
- signature of the VP with the provided SophiaPubKey1

- Sophia can use her second key (did\:key:SophiaPubKey2) to show only her birthplace
- she will provide :
- merkle proof for leaf H1-1-0
- content of the leaf
- signature of the VP with the provided SophiaPubKey2

# Separate trees
[Note my examples ignore @context, type, and other JSON-LD bureaucracy.]
In the case as presented (Sophia & Lars), we do not have group semantics. That is, there is no commonality between the claims of Lars and Sophia, and no additional anonymity gained by sharing the same VC.

Therefore, we have two different VCs (A,B) with two different trees(A1, A2, B1,B2), each.

**[Note that in the previous example, we don't have examples of VCs and VPs. I'm assuming there is just one VC that has everything in it. And somehow, it is issued by an authority that is acceptable for asserting the nationality and birthplace of both Swedish and Spanish citizens (a use case I don't find aligned with my notions of authority).]**

In the first, we have a group of SU citizens, born in Karlstad
They get `VC-A` that looks like this:

{
  "credentialSubject": {
    "id":"groupRootG1",
    "claimRoot" : "claimRoot1",
  },
  "proof": {
      [signed by Swedish govt]
  }
}

The second group is comprised of Spanish Citizens, born in Madrid. They get a `VC-B` that looks like this:

{
  "credentialSubject": {
    "id":"groupRootG2",
    "claimRoot" : "claimRoot2",
  },
  "proof": {
      [signed by Spanish govt]
  }
}

This is a core notion behind the privacy engineering of VCs. Individuals control the flow of information about them by explicitly controlling (through participation in) the distribution of VCs about them. That is, the initial recipients of the above credentials *are* the members of the group. Nobody else gets these VCs. These members then get to selectively disclose some attributes of their VC to the parties they want to share that information with.

These group roots contain the keys of members of the group

> note : add other branches with another member inside the tree exampels below to avoid misconception that there are only several keys of the same person in it

--(groupRoot G1-0)-- ┌(G1-1) - did:key:Lars1
                     └(G1-2) - did:key:Lars2

--(groupRoot G2-0)-- ┌(G2-1) - did:key:Sophia1
                     └(G2-2) - did:key:Sophia2
                    

The claimroots are constructed as follows

--(claimRoot C1-0)-- (C1-1) - "citizenship":"SU",
                  -- (C1-2) - "birthplace":"Karlstad"
                  
--(claimRoot C2-0)-- (C2-1) - "citizenship":"ES",
                  -- (C2-2) - "birthplace":"Madrid"

In short, all of the members in `G1` can selectively disclose any of the claims in `C1` and all the members in `G2` can selectively disclose any of the claims in `C2`.

Membership `G1` does not enable disclosing claims from `C2` and reciprically, membership in `G2` does not enable disclosing claims from `C1`.

The start of the privacy management is that only recipients get their VCs.

Note also, that all recipients ALSO need to know the entire merkle tree (so they can generate proofs and leafs for VPs)

This leads to the following VP1 from Lars (showing his citizenship using `did:key:lars1`)

{
  verifiableCredential: [
    { 
      "credentialSubject": {
        "id":"did:merkle:[G1-0]",
        "claimRoot" : "[C1-0]"
      },
      "proof": {
        [signed by Swedish govt]
      }
    },{
      "derivedCredential": {
        "id":"did:merkle:[G1-0]",
        "leaf":"citizenship:SU",
        "proof":"[C1-0]:[C1-1]"
      }
    }
  ],
  "proof":{
    "type": "Ed25519Signature2020",
    "created": "2022-02-25T14:58:43Z",
    "verificationMethod":"did:[G1-0]?leaf=did:key:Lars1?proof=[G1-0][G1-1]#key1",
    "proofPurpose": "authentication",
    "proofValue": "zyrpmzxPy2fDzqv9Pgr4XBzX2rys1FDuLNkYRVmhXuyype8fB44qNX8mNnXf99i7x1eSpLdYKNhEKknEJmdGfQ4w"
    }
}

Note the proof in the VP establishes the VP was signed by a member of the group thanks to the meaning of "leaf" and "proof" query parameters.

And this VP2 from Lars (showing his birthplace using `did:key:lars2`)

{
  verifiableCredential: [
    { 
      "credentialSubject": {
        "id":"did:merkle:[G1-0]",
        "claimRoot" : "[C1-0]"
      },
      "proof": {
        [signed by Swedish govt]
      }
    },{
      "derivedCredential": {
        "id":"did:merkle:[G1-2]",
        "leaf":"birthplace:Karlstad",
        "proof":"[C1-0]:[C1-2]"
      }
    }],
    "proof":{
        "type": "Ed25519Signature2020",
        "created": "2022-02-25T14:58:43Z",
        "verificationMethod":"did:[G1-0]?leaf=did:key:Lars2?proof=[G1-0][G1-2]#key1",
        "proofPurpose": "authentication",
        "proofValue": "zyrpmzxPy2fDzqv9Pgr4XBzX2rys1FDuLNkYRVmhXuyype8fB44qNX8mNnXf99i7x1eSpLdYKNhEKknEJmdGfQ4w"
    }
}