This looks like it's lifting the requirement for DiffIDs to be SHA-256. That might be useful, but seems orthogonal enough to the ChainID definition that it should be part of a separate PR.

That is not a requirement.

That is not a requirement.

With the old wording (“A layer DiffID is a SHA256 digest”) it certainly seems like using a sha256 digest is a requirement. Regardless of the original intent, clarifying this point seems orthogonal to documenting the chain ID. But shrug, I'm not a maintainer.

SHA256 was just inherited from the original description of Docker's use. Best to not mention specific hashes except where explicitly required to avoid this type of uncertainty for future readers.

If we're making (or clarifying) that the algorithm isn't fixed, then I'd also recommend using “a digest” instead of “the digest”, because the different algorithm choices allow multiple valid digests for the same content (e.g. sha256:2c26b46b68ffc68ff99b453c1d30413413422d706483bfa0f98a5e886266e7ae and sha512:f7fbba6e0636f890e56fbbf3283e524c6fa3204ae298382d624741d0dc6638326e282c41be5e4254d8820772c5518a2c5a8c0c7f7eda19594a7eb539453e1ed7 are both valid digests for foo).

"the digest" refers to "the digest" of the layer.

"the digest" refers to "the digest" of the layer.

A given layer can have multiple digests (see my foo example). That means that an indefinite article is more appropriate than a definite article. Wikipedia gives the following example:

Likewise,

Give me the book.

refers to a specific book whose identity is known or obvious to the listener; as such it has a markedly different meaning from

Give me a book.

which uses an indefinite article, which does not specify what book is to be given.

In this case, the lack of an algorithm requirement means that there are several potential digests (one for each possible algorithm identifier), and we are not specifying which of those digests is intended (all are equally legal).

Digest(content) is not well defined. I think you need the signature to be Digest(algorithm, content). For example:

Digest("sha256", ChainID(L₀|...|Lₙ₋₁) + " " + DiffID(Lₙ))

Otherwise the ChainID could be the result of different algorithm choices at each stage, and the final ChainID digest only identifies the algorithm for the final digest.

No, it is well-defined.

No, it is well-defined.

Here's an explicit example. Consider the following DiffID array:

[
  "sha256:b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c",
  "sha256:7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730",
  "sha256:bf07a7fbb825fc0aae7bf4a1177b2b31fcf8a3feeaf7092761e18c859ee52a9c"
]

Your PR makes it very clear that ChainID(L₀) is sha256:b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c. Good.

Now say the chain ID implementation decides to take a sha256 digest to get ChainID(L₀|L₁) They get:

Digest("sha256", "sha256:b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c sha256:7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730")
  = sha256:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804

Good. Say they decided to use sha512:

Digest("sha512", "sha256:b5bb9d8014a0f9b1d61e21e796d78dccdf1352f23cd32812f4850b878ae4944c sha256:7d865e959b2466918c9863afca942d0fb89d7c9ac0c99bafc3749504ded97730")
  = sha512:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804

Also good. Clearly not the same as the sha256 version, but the algorithm identifier makes that clear.

Moving on to ChainID(L₀|L₁|L₂), say both parties decide to use sha256. The fellow who used sha256 for ChainID(L₀|L₁) gets:

Digest("sha256", "sha256:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804 sha256:bf07a7fbb825fc0aae7bf4a1177b2b31fcf8a3feeaf7092761e18c859ee52a9c")
  = sha256:d4fb205067a0e6ccee30f4c08bcd7e7a7b2f60f49efcdab0f00139198e51eea1

And the fellow who used sha512 for ChainID(L₀|L₁) gets:

Digest("sha256", "sha512:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804 sha256:bf07a7fbb825fc0aae7bf4a1177b2b31fcf8a3feeaf7092761e18c859ee52a9c")
  = sha256:d58dac7b666551a5ddaa5598e792035607a2611f29ad37082881a5bd1f462f49

That's two possible sha256:… values for ChainID(L₀|L₁|L₂) (sha256:d4… and sha256:d5…), so the chain ID is not well defined. In order to get a well-defined ChainID, you need to either:

a. Require a particular algorithm identifier for all chainID digests (this is independent of the algorithm identifier used for the diffIDs themselves) or
b. Require chainID implementations to not swap algorithms as they process additional entries.

(a) could be phrased as:

ChainID(L₀|...|Lₙ₋₁|Lₙ) = Digest("sha256", ChainID(L₀|...|Lₙ₋₁) + " " + DiffID(Lₙ))

and (b) could be phrased as:

ChainID(algo, L₀) = DiffID(L₀)
ChainID(algo, L₀|...|Lₙ₋₁|Lₙ) = Digest(algo, ChainID(algo, L₀|...|Lₙ₋₁) + " " + DiffID(Lₙ))

where the algo argument has no effect on the L₀ case.

@wking this is defining the mathematical formula for a digest and reasoning behind it. Defining the algorithm or making requirements about algorithms matching is unrelated to the definition of a chain ID.

This is a perfectly valid chain id as the properties are reserved.

Digest("sha256", "sha512:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804 sha256:bf07a7fbb825fc0aae7bf4a1177b2b31fcf8a3feeaf7092761e18c859ee52a9c")

The processing creating the chain ID is also responsible for providing the diff IDs, the algorithms of those diff digests are completely irrelevant to the chain id computation and the algorithm used for the end chain ID does not need to match the diff IDs. The chain ID algorithm can be set by the implementation of the chain ID and as with all cases where a digest is used, no algorithm should be preferred by specification.

@wking this is defining the mathematical formula for a digest and reasoning behind it.

Agreed.

Defining the algorithm or making requirements about algorithms matching is unrelated to the definition of a chain ID.

I agree that defining SHA-256 is unrelated, but I don't agree that algorithm selection is unrelated to the chainID definition.

This is a perfectly valid chain id as the properties are reserved.

Digest("sha256", "sha512:edf2182426048661521fe12414e289f2187c9cb6df93bd05c17bb424b7c40804 sha256:bf07a7fbb825fc0aae7bf4a1177b2b31fcf8a3feeaf7092761e18c859ee52a9c")

I'm unclear on what you mean by “the properties are reserved”.

The processing creating the chain ID is also responsible for providing the diff IDs…

This is not necessarily true. DiffIDs are part of the distributed config, so they are created by the config author. ChainIDs may be created by the config author (in which case your statement is true), but they may also be created by the config consumer (e.g. for identifying directories with unpacked/applied stacks of layers) and in that case your statement is false.

…the algorithms of those diff digests are completely irrelevant to the chain id computation and the algorithm used for the end chain ID does not need to match the diff IDs.

Agreed.

The chain ID algorithm can be set by the implementation of the chain ID and as with all cases where a digest is used, no algorithm should be preferred by specification.

That sounds like an argument for the ChainID(algo, L₀|...|Lₙ₋₁|Lₙ) phrasing I recommended. Without that, there is no way to consistently check a claimed chainID. Using my example values, it's not clear how, you could verify that a ChainID(L₀|L₁|L₂) of sha256:d58dac7b666551a5ddaa5598e792035607a2611f29ad37082881a5bd1f462f49 was accurate unless you guessed (somehow) that the creator had used sha512 for the ChainID(L₀|L₁) digest.

Leaving the algorithm choice unrestricted (and thus allowing algorithm swaps), means that there is no guess-free way of validating ChainID(L₀|…|Lₙ) for n > 1. You could define ChainID that way, but when ChainID(algo, L₀|...|Lₙ₋₁|Lₙ) avoids that limitation so easily, I don't see why we wouldn't want to use it.

@wking You are assigning uncertainty where there is none. I please ask that you take time to understand the subject before commenting with authority. If there are questions you have, please don't be afraid to ask, but please pose them as questions.

I also believe that you are misunderstanding the notation. First off, the expression L₀|…|Lₙ abstracts the subsequent application of layers. In other words, the file system state. In this context, we actually define the DiffID in terms of the changeset, rather the contents of diff_ids, which may be used but is not required. How you arrive at the result of the DiffID is part of the implementation. The implementation provided here operate directly on an analogous array, but making this work in practice does require this.

Either way, the ChainID isn't transmitted, so local implementations can choose specifics, while still allowing implementations that select DiffID, ChainID and Digest carefully to yield compatible results.

How you arrive at the result of the DiffID is part of the implementation.
…
Either way, the ChainID isn't transmitted, so local implementations can choose specifics…

Then why bother defining it at all? Can't we just point out that using a hash of the final layer is (obviously?) not unique to one particular array of layers and is a property shared by all arrays ending with that layer. I don't see the point of spending ~50 lines defining and explaining ChainID if the end result is “but you're free to pick a lot of the unspecified parameters, including the DiffID(Lᵢ) algorithm and digest hash, so don't expect your ChainIDs to match anyone else's”.

You can avoid defining | and just define ChainID to act on an array of strings. In the common case, these strings will be digests over the uncompressed layer (i.e. DiffIDs), but there's no reason to limit the chain ID to those cases when it only complicates the definition.

You can avoid defining | and just define ChainID to act on an array of strings.

But that is not the definition of a ChainID.

You can avoid defining | and just define ChainID to act on an array of strings.

But that is not the definition of a ChainID.

Not as your PR stands with 0fa3cc5, but with a string-based ChainID definition, it's easy enough to couple back in your choice of DiffID(…) implementation:

ChainID([DiffID(L₀), DiffID(L₁), …, DiffID(Lₙ)])

On the other hand, it's clearly impossible to decouple the ChainID from layers if you require the arguments to be layers ;).

Your implementation seems to agree by accepting Digests and then treating them as opaque strings. There is nothing layer-specific in the current identity/chainid.go code, and I like that, and think the Markdown definition should follow that example.

This paragraph doesn't add anything to the earlier definition that I can see. There's already enough going on here that I don't think repeating that definition here adds anything, so I'd like to drop this paragraph.

It is called adding context. For those unfamiliar with recursion, or who practice literate reading, this is very helpful. It helps to assign an english meaning to an otherwise obtuse syntax.

It helps to assign an english meaning to an otherwise obtuse syntax.

So keep this version and drop the earlier version? The earlier version is not much more compact than this paragraph, so if it is obtuse in any way I don't see the point of including it.

Different people understand things it different ways.

nit: Switching from Lᵢ to A/B/C seems unnecessary. I'd just stick with the subscripted L throughout.

This is a specific example verses a generic case.

“A, B, C” is not a specific example. A specific example would be “the array of strings ["a", "b", "c"] or (if you prefer restricting ChainID to layers) “the array of layers ["<inline tar-a>", "<inline tar-b>", "<inline tar-c>"]”. If you go with the latter, I recommend using very tiny tarballs ;).

These two paragraphs seem like they could be clarified. How about something like:

The final string Lₙ in an array of strings [L₀, L₁, …, Lₙ] is not sufficient to uniquely identify the array, because many arrays might end in the same value. For example ["a", "b"], and ["a", "c", "b"] both end in b.

Then follow up with your next paragraph reiterating that the ChainID depends on all of the strings in the array, so the ChainIDs of ["a", "b"], and ["a", "c", "b"] will be different.

You keep trying to model this as an array of strings. It is not.

You keep trying to model this as an array of strings. It is not.

Hashing anything is an operation on byte strings. If you want to keep the DiffID(Lᵢ) algorithm unspecified, you can accomplish that in the array-of-strings context by using ChainID([DiffID(L₀), DiffID(L₁), …, DiffID(Lₙ)]), which I think is better separation of concerns than baking an undefined DiffID(Lᵢ) algorithm into the ChainID definition.

Hopefully? If there is any doubt, can we just use real values. With the array-of-strings formulation, you can use:

ChainID(["a", "b", "c"]) = Digest(Digest("a" + " " + "b") + " " + "c")
  = Digest("sha256:01186fcf04b4b447f393e552964c08c7b419c1ad7a25c342a0b631b1967d3a27" + " " + "c")
  = "sha256:638db252c0d891abd09b138672c11c4b4fb984121019bf1d526e200d704325d0"

Which has the additional benefit of being an easy unit test for any ChainID implementations.

We are being hopeful about understanding of the reader, not the result.

It is clear that "hopeful" is the right sentiment, as I know of at least one reader who is struggling here.

We are being hopeful about understanding of the reader, not the result.

Right. That's a sign that we doubt the clarity of the current wording, so we should hunt for wording that is clear enough to make us not doubt the reader's understanding.

@wking Everyone else I have shown this to seems to understand.

Everyone else I have shown this to seems to understand.

I'd still prefer real values. But if many people understand, and only one does not understand, and you feel like there is no room for clarification to help that remaining person, I think that's enough reason to drop this sentence. Letting them know that you hope they will understand is unlikely to impact their understanding. And while we hope readers understand everything in the spec, I think it's appropriate that we don't burn a line saying “We hope you understand this specification” in spec.md.

It's not that I don't feel there is no room for clarification. It's that within a day of submitting this PR, which is not contentious at all, you have made upwards of 30 comments on it.

I can't tell if you are trying to slow OCI down for nefarious purposes or genuinely think your helping.

I don't think otherwise, … adds anything and would like to drop it. It looks like it is attempting to argue “if ChainID(C) = ChainID(A|B|C), then ChainID(C) = DiffID(C), so… something”. However, ChainID(C) = DiffID(C) is true (it's the L₀ case). Seeing the (true) ChainID(C) = DiffID(C) right next to “could not be true” is just confusing. What is true is that, baring some unlikely hash collisions, ChainID(C) != ChainID(A|B|C). And I think the earlier ChainID(A|B|C) expansion into constituent digests makes that clear enough on its own.

It mirrors the structure of the definition, the prose description and

You need to differentiate between "I don't understand the implications of this equality" from "I don't understand the strength or reasoning behind these implications".

The whole point here is that DiffID(C) is insufficient to identify the application of A|B|C, and thus ChainID(C) is insufficient. So, we have defined ChainID(A|B|C) to allow this.

However, ChainID(C) = DiffID(C) is true (it's the L₀ case).

This is not the L₀ case. This is why we revert the to lettering to make this clear. C represents an independent change set.

The whole point here is that DiffID(C) is insufficient to identify the application of A|B|C, and thus ChainID(C) is insufficient.

ChainID(C) is sufficient to identify the layer array [C] (and in that case it is clear that ChainID(C) = DiffID(C). ChainID(A|B|C) is sufficient to identify the layer array [A, B, C], and it's not clear to me why anyone would attempt to identify that array with ChainID(C).

it's not clear to me why anyone would attempt to identify that array with ChainID(C).

In fact, ChainID(C) = ChainID(∅|C). It is the chain id for identifying the application of C to the empty file system.

If these aspects aren't clear to you, why are commenting with such authority? It seems like you don't have a basic understand of this problem or its solution, yet you are attempting to comment on it as if you have a full understanding or even expertise on the matter. I don't mind further clarifying this, but it makes it hard to have a conversation when you pose your attempt to understand as contrarian statements.

it's not clear to me why anyone would attempt to identify that array with ChainID(C).

In fact, ChainID(C) = ChainID(∅|C)…

To have ∅|C you'd need an empty-tar layer. And ChainID(C) = DiffID(C) ≠ Digest(DiffID(∅) + " " + DiffID(C)) = ChainID(∅|C). There may be some benefit to a ChainID definition that is based on the assembled filesystem (you get the same ChainID for A|B|C and D|E if the resulting filesystems happen to be identical), but any ChainID that is defined recursively on the constituent layers is not actually based on the resulting filesystem.

It is the chain id for identifying the application of C to the empty file system.

This is true for ChainID(C), but that's not what ChainID(∅|C) is (ChainID(∅|C) identifies applying the ∅ layer to an empty filesystem, and then applying C to that) . And either way, I still don't see why anyone would be using this to identify the layer array [A, B, C].

If these aspects aren't clear to you, why are commenting with such authority?

Because I think these aspects are clear to me?

I don't mind further clarifying this, but it makes it hard to have a conversation when you pose your attempt to understand as contrarian statements.

I think pushing back on “this doesn't make sense to me” is a good way to have a discussion that gets us to agreement. There are alternatives though. For example, I could file a PR with my own take on clarifying ChainID (although it would be very similar to my December comment). If that seems like it would be more productive, let me know. But unless we find a way focus on the places where we aren't currently seeing eye to eye, I don't know how we'll resolve those differences.

∅|C = C