Algorithms

These algorithms are referenced throughout this specification.

DID-BTCR2 Identifier Encoding

Any errors encountered during this algorithm MUST raise an INVALID_DID error.

A did:btcr2 identifier is created from three arguments: version_number, network_name and key_or_hash (Genesis Bytes).

key_or_hash MUST be one of the supported Genesis Bytes variants defined in the Terminology chapter and MUST be representable as a 33-byte secp256k1 public key or a 32-byte SHA-256 hash. Implementations SHOULD require key_or_hash to include additional type information that clearly distinguishes between the supported Genesis Bytes variants. This type information determines how the identifier is encoded.

The version_number value MUST be 1, declaring the encoding follows this specification.

The network_name value declares which Bitcoin network anchors the identifier. Implementations SHOULD require network_name to include additional type information using symbolic names that MUST be representable as integer values listed in the following table:

Table 1: Network Values

Introduce btcr2_version as version_number - 1 (i.e., 0). Combine btcr2_version in the low ¹ nibble and network_value in the high ¹ nibble into a single byte value.

Append key_or_hash to the first byte to produce the unencoded data bytes. Its format is:

Table 2: Unencoded Data Bytes

Encode the unencoded data bytes with Bech32m [BIP350] to produce the method-specific-id. Use "k" as the hrp for key-based key_or_hash and "x" as the hrp for Genesis Document-based key_or_hash.

Prefix the method-specific-id with the string "did:btcr2:" to produce the final did:btcr2 identifier.

DID-BTCR2 Identifier Decoding

Any errors encountered during this algorithm MUST raise an INVALID_DID error.

Parsing a did:btcr2 identifier produces three values: version_number, network_name, and key_or_hash (Genesis Bytes).

A did:btcr2 identifier MUST be processed according to the DID Resolution Algorithm [DID-RESOLUTION] to retrieve the did:btcr2 DID Method-specific ID method-specific-id. (I.e., the first 10 characters in the string MUST be exactly "did:btcr2:".)

Decode the method-specific-id as a Bech32m encoded string [BIP350] to retrieve the unencoded data bytes and hrp. Parse the unencoded data bytes according to Table 2: Unencoded Data Bytes to retrieve the btcr2_version, network_value and genesis_bytes.

• btcr2_version MUST be 0. Introduce version_number as btcr2_version + 1. I.e., version_number MUST be returned to the caller as a type that can be represented as the value 1.
• network_value MUST be one of the values in Table 1: Network Values. network_name SHOULD be returned to the caller including additional type information using symbolic names that can be represented as integer values.
• The hrp MUST be either "k" or "x".

If the hrp is "k" (key-based btcr2:did identifier), key_or_hash MUST be genesis_bytes interpreted as a 33-byte SEC encoded secp256k1 public key.

If the hrp is "x" (Genesis Document-based btcr2:did identifier), key_or_hash MUST be genesis_bytes interpreted as a 32-byte SHA-256 hash of a Genesis Document.

JSON Document Hashing

• Encode the document using JCS [RFC8785].
• Hash the encoded document with SHA-256 [SHA256].

SMT Proof Verification

To verify the inclusion or non-inclusion of a DID in the SMT Proof, perform the following steps:

Construct a hashed-zero cache. Two zero leaves are hashed together by concatenating the value 0 with itself for the bottom level, and then hashed again with its next sibling, also itself, at each level up the tree. Each computed hash value can be cached in an array.

let cachedZero = [];
let z = 0;
for i in 0..=255 {
  z = hash(concat(z, z));
  cachedZero[i] = z;
}

The SMT Proof (data structure) is verified by walking the tree starting from the leaf node value, given by hash(hash(proof.nonce) + proof.updateId), to the root proof.id. Walking the tree means hashing sibling hashes from proof.hashes concatenated with a candidate hash to construct each node value. Each bit within the leaf node index (given by hash(did)) informs the algorithm which side of the concatenation operation the sibling hash belongs on: 0 for left, 1 for right.

The tree is “optimized” by collapsing empty nodes. (See Appendix: Optimized Sparse Merkle Tree Implementation for definition of “optimized”.) Each bit within proof.collapsed informs the algorithm whether to take the next sibling hash from proof.hashes (0) or use a hashed zero from the current height of the tree (1).

The last step is asserting that the computed candidate hash is equivalent to proof.id (the Merkle root).

let candidateHash = hash(concat(hash(proof.nonce), proof.updateId))
let index = hash(did)
for n in 0..=255 {
  let i = 255 - n;

  let siblingHash = if proof.collapsed[i] == 1 {
    cachedZero[n]
  } else {
    proof.hashes.pop_front()
  };

  if index[i] == 1 {
    candidateHash = hash(concat(siblingHash, candidateHash));
  } else {
    candidateHash = hash(concat(candidateHash, siblingHash));
  }
}

return candidateHash == proof.id;

1. Little Endian. ↩ ↩2

2. The “Index” is a Little Endian bit count starting from 0 on the left and ending in 263 or 271 on the right (inclusive). ↩