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

Reserved network values MUST NOT be encoded until this specification assigns them.

A Custom networks value allows any user to stand up a custom network and create did:btcr2 identifiers on it. Anyone encountering such an identifier has to know the details of the network (e.g., the challenge and seed nodes for a custom signet) to use it. This means:

• The interpretation of a custom value is by mutual agreement between the parties issuing did:btcr2 identifiers and those resolving them.
• Other users may use the same value, and their did:btcr2 identifiers will not be interoperable in each other’s networks.

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 ³ to produce the method-specific-id, which MUST be lowercase. 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:".)

The method-specific-id MUST be lowercase. Decode it as a Bech32m encoded string ³ to retrieve the unencoded data bytes and the 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 handled according to its row in Table 1: Network Values:
  • A named network value (0..5) maps to its network_name. network_name SHOULD be returned to the caller including additional type information using symbolic names that can be represented as integer values.
  • A Reserved value (6..11) MUST be rejected until this specification assigns it a network_name.
  • A Custom networks value (12..15) SHOULD be rejected when the implementation does not support a custom network for that value. What it means to support a custom network is implementation-defined.
• 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.

Decoding inverts encoding exactly: passing the version_number, network_name, and key_or_hash produced by this algorithm to the DID-BTCR2 Identifier Encoding algorithm MUST reproduce the identical did:btcr2 identifier string.

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:

Throughout this section, hash() denotes SHA-256 [SHA256] over a byte array, and concat() (equivalently, the + operator) concatenates byte arrays, not strings. The base64url [RFC4648] encoded fields of an SMT Proof (data structure) (id, nonce, updateId, collapsed, and the entries of hashes) MUST be decoded to their raw bytes before being used in any of these operations.

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 n in 0..=255 {
  z = hash(concat(z, z));
  cachedZero[n] = 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) for update inclusion or hash(hash(proof.nonce)) for non-inclusion — 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 = if let Some(updateId) = proof.updateId {
  hash(concat(hash(proof.nonce), updateId))
} else {
  hash(hash(proof.nonce))
};

let index = hash(did);

for n in 0..=255 {
  let i = 255 - n;

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

  if index.bitAt(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). ↩

3. The method-specific-id MUST be conformant to Bech32m [BIP350], which extends Bech32 [BIP173]. On encode, pad the final 5-bit group with zero bits; on decode, an incomplete final group MUST be 4 bits or fewer, MUST be all zeros, and is discarded. ↩ ↩2