Calculating SAIDS with Blade3-256 - nuance

[carlyh-micb]

One important note, I realize when I tried to use an online Blade3-256 hashing function that there are actually multiple options when hashing and I couldn't actually get the exact same digest, some characters were mismatched (see the picture below). There is obviously some kind of nuance with regards to hashing algorithms and it would be good to document this in the OCA specification.

https://emn178.github.io/online-tools/blake3/

[blelump]

The way we calculate the digest is also CESR-specific. Let's go step by step over an example (given in JavaScript):

1. Assume the payload is abcd.
2. await blake3(Buffer.from("abcd", "utf-8")) => jJyYgYBdGoRxAtekLli5kNCI3YioT3MU1xyDgQdXHys=. The same digest is returned from https://emn178.github.io/online-tools/blake3/ for abcd.
3. In CESR (that SAID is also using for encoding), we're not interested in raw output but in output that can be divided by 24. This is to support framing in CESR for all its primitives.
4. The length of jJyYgYBdGoRxAtekLli5kNCI3YioT3MU1xyDgQdXHys= (after decoding back to bytes) is 32 bytes. 32*8, we get 256 bits and then divide by 24: 10.666666666666666. 11*24 (=264) is the number of bits we're looking for to encoding. All we have to do is prepend the 32 bytes (256 bits) with 1 additional byte (8 bits) – in this case.
5. We then concat the bytes from await blake3(Buffer.from("abcd", "utf-8")) with one byte representing 0: Buffer.concat([Buffer.from([0]), raw])
6. Final result: AIycmIGAXRqEcQLXpC5YuZDQiN2IqE9zFNccg4EHVx8r . When we replace A with E (the Blake3 code), we get exactly the same output as from https://said.argo.colossi.network/ .

[carlyh-micb]

These are great details that I think should be included in the OCA specification.

Should we could discuss using something without the additional CESR complexity and just a raw hashing algorithm? I think benefits and trade-offs should be clear and an excellent topic for DSWG.

What about if someone wants to use a different hashing algorithm? Will they be required to follow similar instructions and will those instructions be documented? Or if we only document Blade3-256 and note that the OCA specification is prepared for other hashing algorithms in the future which can be added to OCA-spec as needed and not need a new version of OCA-spec for these additions.

[swcurran]

Given that there is no need for using CESR or worrying about the length of hashes falling on bit boundaries, why is the OCA spec following/using CESR that standard?

Since the Blake3 hashing algorithm was not accepted by NIST and there are far fewer libraries in various languages vs. SHA hashing, why use it?

That said — if this all gets documented cleanly in the OCA spec so that an independent implementation can be defined, all good. Documented means the permitted hashing algorithm(s), how the hashing algorithm can be detected (to allow for future evolution of the spec), steps to hash, and steps to verify.

I infer from the first line that the canonicalization approach is as follows and needs also to be in the spec:

1. Start with JSON input.
2. Place the string “####…” in all places the hash will go (usually, just 1).
3. Recursively sort the JSON struct alphabetically by item.
4. Remove all of the extraneous whitespace in the JSON.

I would recommend (although presumably it is too late) to:

1. Remove the need to make the placeholder (“####…”) the same length as the resulting hash, since that is unnecessary, will change if new hash algorithms are permitted, and kind of annoying.
2. For steps 3 and 4, use JSON Canonicalization Scheme, since that is a standardized version of the two steps.

[blelump]

Please find this discussion as a continuation of the OCA v1 design choices topic. It is discussed here and there, so the open discussion should address (at least some) of the questions.

@swcurran, it is perfectly fine if you want to use SHA instead of BLAKE. Use the SHA hashing algorithm and prepend the digest with the proper letter. For the record:

E	Blake3-256 Digest	1		44
F	Blake2b-256 Digest	1		44
G	Blake2s-256 Digest	1		44
H	SHA3-256 Digest	1		44
I	SHA2-256 Digest	1		44

[swcurran]

So the expectation is any OCA parser MUST support all of the “permitted” hashing algorithms, and that is the list? I suspect that means a lot of extra dependencies. If that is what the spec says, that is OK — although not ideal.

My suggestion (and what we do in the DID TDW spec) is to keep the prepending flag (which is what the “multihash” standard defines — but with a much larger list of hash algorithms), but to specify that OCA Bundles creators MUST use a (ideally) just one hash algorithm (preferrably sha-256) — or at most an option or two. That reduces the number of dependencies an implementation needs to include — reducing the dependabot updates needed. A later version of the spec might add newer, better algorithms, and deprecate older ones.

And all of this needs to be added to the spec.

[blelump]

In the OCA spec, we say that the OCA Object identifier is SAID. What will come as refinement (clarification) in v1.1 of the spec is that all objects are SADs(self-addressing data). SAID presumes specific algorithms that are sufficient for the current needs. SAID doesn't support all the algorithms as Multihash does because SAID is pragmatic. If it's not needed, why bother? This "not needed" argument is significant because we don't have to support old or legacy systems. We started Green Field to benefit from what is available now or in the future (SAID will get proper letters then).

As discussed in #59, we made design choices and onboarded SAID. We cannot narrow the list of hashing algorithms to just one for the same reason git did not do it in the past with SHA1 and is now stuck with it: We want to be forward-compatible. We are specifically interested in the first and second pre-image resistance for any hashing algorithm in OCA, and historically, MD5 and SHA1 were found to lack these properties. SAID solves not only this, but also specifies how to make it self-referential (embeddable in the document it refers to).

[carlyh-micb]

I love new ways and greenfield, I am looking for a defensible, pragmatic and clear benefit of using SAIDs vs multihash and the JSON canonicalization method.

For the calculations of the hashing, I had indeed gone through Sam Smith's documentation (which is very much in flux since it has changed standards body hosting at least once). Even after going through that method I still apparently hadn't dug deep enough because E is not just the Blake3-256 Digest, it apparently has a bunch of additional processing. I don't think it is a good idea to point to Sam's most recent documentation as the source, it is confusing, a work in progress and any user would really have to dig.

How does OCA benefit from using CESR. Can this be articulated? Could we write out a detailed, non-normative description of exactly how you calculate SAIDs for two hashing examples and that the official method is Sam Smith's documentation? Currently the weakest part of the specification is canonicalization and digests; that OCA is all about cryptographic reproducibility but it is very hard to verify (except to depend on a few experts to do it for you) and rather than going a standard route that can be easily reproduced by others we went the less documented, less used and more difficult to figure out CESR route without (yet) being able to articulate the clear benefits of that. Could we be ready for CESR and use it in v3 or v4 of OCA-spec? I'm not against CESR at all, I am suggesting a different timing.

[blelump]

@carlyh-micb , please use the #59 discussion to continue discussing the design choices, i.e., these CESR-related. We can answer the questions there.

CESR looks complex because it's a clever protocol. SAID isn't technically CESR but uses CESR concepts, i.e., the code table and the encoding process described in the 2nd post above.

[swcurran]

We seem to be talking past each other @blelump re: how to declare what hash algorithms are allowed and how to detect which one was actually used. My points:

• The OCA spec (not the SAID spec) should define what hash algorithms are allowed to be used, and that list should be updated with each version of OCA as it is determined that better algorithms are available. That said, the list in the spec should be as small as possible to reduce the dependencies needed.
• Multihash and the prefix used by SAID are for the same purpose. I’m just suggesting using multihash because it is used for more widely.

Writing this I realize that there should be another requirement. Each OCA Document should have to declare what version of the OCA spec that was used in creating the document. That will ensure that both evolutions of the spec. and backwards compatibility can be managed in real deployments.

However — the most important point. Whatever you decide to do with hashing and SAD generation — please put it in the spec. We can’t do anything until that is done.

[carlyh-micb]

Stephen, I posted something in the discussions earlier, not sure if you saw it.

I will note that you can tell what version you are in because each overlay is versioned.

"type": "spec/capture_base/1.0",
"type": "spec/overlays/unit/1.0",
"type": "spec/overlays/entry_code/1.0",
"type": "spec/overlays/entry/1.0",

Are examples of valid overlays (v1.0). It looks like you could even have a schema with a mix of versions of overlays.

I don't think there is a version for the entire schema bundle, which makes sense if it supports versions at the level of overlay.

[carlyh-micb]

Stephen, I posted something in the discussions earlier, not sure if you saw it.

I will note that you can tell what version you are in because each overlay is versioned.

"type": "spec/capture_base/1.0", "type": "spec/overlays/unit/1.0", "type": "spec/overlays/entry_code/1.0", "type": "spec/overlays/entry/1.0",

Are examples of valid overlays (v1.0). It looks like you could even have a schema with a mix of versions of overlays.

I don't think there is a version for the entire schema bundle, which makes sense if it supports versions at the level of overlay.

After discussing this at ADC - is the version number here the version number for the overlay (according to the spec) or is it the version of the content of the overlay and the user can change the versions?!!!

[blelump]

Stephen, I posted something in the discussions earlier, not sure if you saw it.
I will note that you can tell what version you are in because each overlay is versioned.
"type": "spec/capture_base/1.0", "type": "spec/overlays/unit/1.0", "type": "spec/overlays/entry_code/1.0", "type": "spec/overlays/entry/1.0",
Are examples of valid overlays (v1.0). It looks like you could even have a schema with a mix of versions of overlays.
I don't think there is a version for the entire schema bundle, which makes sense if it supports versions at the level of overlay.

After discussing this at ADC - is the version number here the version number for the overlay (according to the spec) or is it the version of the content of the overlay and the user can change the versions?!!!

There's no reason to keep each OCA Object versioned separately, as it is now defined in the spec. The serialization scheme ensures the v attribute at the beginning that describes the serialized content's (Bundle) major and minor semantic versions. If any OCA Object changes, the semantic version of the Bundle must also change -- it's otherwise unknown whether the parser can parse it. However, how to version the community overlays concept remains an open topic.

[kentbull]

To clarify things I will respond to each of @blelump's and @swcurran's comments inline. While you must understand a bare minimum of CESR-style encoding of a SAID to maintain interoperability with CESR SAIDs you don't have to know or implement all of CESR in order to have a CESR-compliant SAID. It is entirely possible to create non-CESR compliant SAIDs as well if you want to completely omit any CESR-related concepts. To get many of the same benefits you would need to come up with your own scheme for signifying specific types of digests and pad character sizes.

You can see my short SAID implementation called saidify of about 525 lines of Typescript showing a minimal implementation of CESR code tables.

Michael's process is correct. I will restate it briefly for clarity.
Michael correctly wrote:

1. Assume the payload is abcd.
2. await blake3(Buffer.from("abcd", "utf-8")) => jJyYgYBdGoRxAtekLli5kNCI3YioT3MU1xyDgQdXHys=. The same digest is returned from https://emn178.github.io/online-tools/blake3/ for abcd.
3. In CESR (that SAID is also using for encoding), we're not interested in raw output but in output that can be divided by 24. This is to support framing in CESR for all its primitives.
4. The length of jJyYgYBdGoRxAtekLli5kNCI3YioT3MU1xyDgQdXHys= (after decoding back to bytes) is 32 bytes. 328, we get 256 bits and then divide by 24: 10.666666666666666. 1124 (=264) is the number of bits we're looking for to encoding. All we have to do is prepend the 32 bytes (256 bits) with 1 additional byte (8 bits) – in this case.
5. We then concat the bytes from await blake3(Buffer.from("abcd", "utf-8")) with one byte representing 0: Buffer.concat([Buffer.from([0]), raw])
6. Final result: AIycmIGAXRqEcQLXpC5YuZDQiN2IqE9zFNccg4EHVx8r . When we replace A with E (the Blake3 code), we get exactly the same output as from https://said.argo.colossi.network/ .

This can be simplified to:

1. Start with any arbitrary JSON payload that includes an empty attribute for your SAID, say the "d" field for now.
2. Place the correctly sized pad string "####..." in the SAID field, "d" here. This size is read from the CESR master code table and corresponds to the type of digest you produce, 'E' for our case here of Blake3-256. This type of digest requires a 44 character length (33 byte) Base64URLSafe resulting encoding, 32 bytes for the digest and 1 byte for the prefixed derivation code.
3. Create a digest (Blake3-256, Blake2b-256, SHA3, SHA2, etc.) of the raw, serialized JSON bytes preserving some reproducible field order whether insertion order or some other canonical order. The digest is typically a 32 byte digest (256 bits). The field order varies between organization. CESR uses insertion order, though you can use whatever order you want as long as you are consistent.
4. Align the digest to a 24 bit boundary with pre-padded zero bytes.
   You need to get to a multiple of 24 since that is the least common multiple between the Base64 character bit count and a byte bit count.
   Here that means 33 bytes, or 264 bits, meaning 44 Base64URLSafe characters.
5. Replace any pre-paded "A" (zero bit) Base64 characters with the correct CESR derivation code from the CESR master code table, in this case replacing a single 'A' with 'E' for Blake3-256. SHA3-256 would be 'H'.\

   AJymtAC4piy_HkHWRs4JSRv0sb53MZJr8BQ4SMixXIVJ
   ↓
   EJymtAC4piy_HkHWRs4JSRv0sb53MZJr8BQ4SMixXIVJ
   

Stephen:

1. Start with JSON input.
2. Place the string “####…” in all places the hash will go (usually, just 1).
3. Recursively sort the JSON struct alphabetically by item.
   This sorting is not strictly necessary, though is compatible with CESR-encoded SAID. I know you aren't using KERI, though just FYI since OCA is integrating with KERI: alphabetic encoding will break anything using KERI since KERI data structures have a specific insertion order that is not alphabetical. This order is specified in section 7 of the ToIP KERI specification.
4. Remove all of the extraneous whitespace in the JSON.
   Yes, this is implied with JSON serialization. Raw digests should only ever be computed on a compact, no-whitespace JSON

You are missing the digest, alignment, and derive steps in your process.

So Michael is correct:

CESR looks complex because it's a clever protocol. SAID isn't technically CESR but uses CESR concepts, i.e., the code table and the encoding process described in the #58 (comment) above.

SAID uses CESR-style self-framing derivation codes as well as the 24-bit alignment strategy to ensure composability of cryptographic primitives in a byte stream.

And Stephen, regarding

I would recommend (although presumably it is too late) to:

1. Remove the need to make the placeholder (“####…”) the same length as the resulting hash, since that is unnecessary, will change if new hash algorithms are permitted, and kind of annoying.

I understand how it could be seen as annoying to change the length of the placeholder yet there are a host of important benefits for stream parsers when you make the placeholder the same length of the resulting digest. When you keep the placeholder and the digest the same length then that means that the size of the overall SAIDified data structure remains the same pre- and post-saidification. This fixed size enables incremental, efficient parsing of a byte stream since you can parse one by one due to a TLV encoding scheme and this fixed size also supports pipelining where you can hand off these incrementally received cryptographic primitives off to separate CPU cores for efficient parsing.

2. For steps 3 and 4, use JSON Canonicalization Scheme, since that is a standardized version of the two steps.

This should work for anything that is not KERI or insertion ordered. There is a good argument for insertion ordering for some use cases and there are similarly good arguments for alphabetical ordering for other use cases. I personally favor insertion ordering because it allows for developer and user friendly natural field orderings, though some people prefer alphabetical ordering in order to simplify debates and decision making.

And @carlyh-micb, regarding your question about using CESR,

How does OCA benefit from using CESR. Can this be articulated?

You don't have to use all of CESR for SAIDs, though since HCF is building on top of CESR then you can leverage all of its benefits including cryptographic agility, data efficiency with incremental parsing, pipelining, and a very compact encoding format.

Could we write out a detailed, non-normative description of exactly how you calculate SAIDs for two hashing examples and that the official method is Sam Smith's documentation?

I show how to calculate Blake3, Blake2, SHA3, and SHA2 digests (hashes) with SAIDify:

• here how to calculate a Blake3-256 digest
• here how to calculate a Blake2-256 digest
• here how to calculate a SHA3-256 digest
• here how to calculate a SHA2-256 digest

I have a longer explanation targeting programmers here detailing the steps to produce a SAID and the supporting concepts of 24-bit boundary alignment. Beware, it's a bit of a read.

[kentbull]

Michael's process is correct.

In a second review of Michael's process he is missing a key part of the Base64 encoding process that CESR uses. His Blake3 digest of jJyYgYBdGoRxAtekLli5kNCI3YioT3MU1xyDgQdXHys= contains an equals sign '=' which would never occur in a valid CESR encoding of a SAID because prior to creating a digest for a SAID the value is always pre-padded with zero bytes to align on a 24-bit boundary. Equals signs '=' only occur when a Base64 encoded value is not aligned on a 24-bit boundary because Base64 encoding is supposed to always produce 24-bit aligned values whether CESR or not.

What CESR does is repurpose the space that would have been taken up by equals sign ('=') padding characters for derivation codes that allow you to look up the type and length of a cryptographic primitive by reading only the front bytes of an encoded primitive and then take the observed type, read the code table entry to get the length (size) of the primitive, and then strip exactly that number of bytes from the incoming byte stream. This is why CESR is a TLV (type, length, value) encoding scheme.

The use of a prefixed, TLV, self-framing encoding scheme with 24-bit boundary alignments provides composability including layered hierarchical composability which enables really cool things like indexed signatures and group count codes, among other things.

[blelump]

thanks @kentbull . For your information, the Human Colossus Foundation provides a fully-fledged JS client calculating SAID that is exposed here. Both the source of the WEB page and the library are publicly available. The documentation level needs to be improved, but we always welcome contributions in this area.