Why the path in Salty Creator does not need a separator

[SmithSamuelM]

Why the path in Salty Creator does not need a separator

The two numbers ridx and kidx when converted to hex strings with no zero pre-padding and concatened togther as ridx+kidx where + represents concatenation have the following properties:

Properties

For simplicity we abbreviate for any partition j, that ridxj.kidxj be represented as rj and kidxj be represented by kj. So we have rj.kj.

For all partitions j

1 . kj and rj are each non zero prepadded hex strings. So there are no interior zeros between the least significant hex digit of rj and the most significant hex digit of kj
2. kj starts at 0 and is strictly monotonically increasing by at least 1 but may increase by more than 1.
3. rj starts at 0 and is strictly montonically increasing by 1 and no more than 1..
4. This means that for any pair of rj and kj, kj >= rj
5. and for any two of partitions of the form (r1, k1) and (r2, k2) where r2 > r1 then k2>k1
6. any set of two partitions (r1, k1) and (r2, k2) then the length of r1 <> length of r2 and the length of k1 <> length of k2 otherwise 1 and 2 are the same partition.
7. for any set of two partitions (r1, k1) and (r2, k2) where the length of r1 is greater than the length of r2 then necessarily the length of k1 must be less then the length of k2 but this violates 5 above. QED. It is not possible to have two mutually ambiguous partitions and hence no separator is needed. Thus the code is not a bug. Its a feature because the path length is minimally sufficient in length and therefore follows the KERI design principle of minimally sufficient means.

Discussion:

Every new establishment event after the inception must use at least one new key which increments kidx by at least one for every increment of 1 of ridx. If the event is multisig then kidx is incremented by the number of sigs less one. The inception event has ridx ==0. So at inception kidx >=0 and therefore kidx >= ridx even for single sig. And every establishment event increments kidx at least by 1 and more if any are multisig.

So given the properties above it means that for a path of a given length with separator shown as per the example given for this issue of 1.11 being ambiguous with 11.1 we have

1.11 is possible but
11.1 is impossible so there is no ambiguity when removing the separator.

This is true in general of
2.22 versus 22.2 etc.

To generalize the proof, Suppose us say we have some string of hex digits of any length , such as, xxxxxx.

The question is for any given hex string made from concatenating two hex strings where neither of the hex strings has zero prepadding are there at least two different ways to partition that concatenated string into two parts where the front part is ridx and the back part is kidx and the integer value of each part satisfies the properties above:

The answer is no.

Proof:

Obviously any partition where the length of ridx is longer than kidx violates kidx >= ridx. So we only need to consider partitions where the length of ridx <= length of kidx .

Suppose we have the sequence x1,x2,x3,x4 where each xi is a hex digit from [0-1,a-f] and given any partition the most significant hex digit or each part must be not be 0.

For a length of 4, we have the following two partition choices:

1. x1.x2x3x4

2. x1x2.x3x4

So because length of r1 is less than length of r2 then we have r2 > r1 but because the length of k2 is less than the length of k1 we have necessarily that k2 < k1 which violates property 5 above. Therefore both partitions can not be valid for the same KEL.

To generalize, for any string of a given length that satisfies the properties above and given any two partitions of that string, then both partitions cannot satisfy all the properties above because an increase/decrease in the length of a given partition rj relative to the other partition commensurately results in a decrease/increase in the length of kj relative to the other partition such that property 5 is violated.

So NOT a bug and no need to change the code.

[SmithSamuelM]

The analysis above is incomplete becasue it does analyze the possiblity of multisig > 16 which would require more than one hex digit for the code index i. So for completeness I include that as well here.

The exact code is

path = "{}{:x}{:x}".format(stem, ridx, kidx + i)

For any given KEL the stem is assumed to unique (the default is the prefix index pidx, which monotonically increases in order of creation of a given identifier prefix for a kel, so we can ignore the stem portion.

Basically the addition of each index adds 1 to the kidx which creates a new kidx but the properties of kidx relative to ridx still apply its just that we have multiple effective kidx for any ridx but they are still are strictly monotonic. Still the only way for two concatenated strings to match with ambiguity is if they do not have the same ridx.

However just for the sake of completeness, what if there are more than 16 multisig codes at a given event which would mean that the effective kidx for any given ridx could be of two lengths. So in the following analysis I generalize to the case where instead of adding the index to increase the int value of kidx, I concatenate the hex value of the index i. This covers the worst-case scenario where the number of codes is large enough to change the length of the hex str representation of the kidx.

Discussion:

Thei or index at the end is a zero based index into the list of codes for a given set of keys at a given establishment event.
So we extend our representation as follows: Let ij represent the max index of the jth event

This gives us the following properties:

8. kj+1 = kj + len(code list) = kj + max(i) + 1 = kj + ij + 1
9. length of kj >= length of kn for j > n

This means that any subsequent kj must be larger than the sum of the number of codes in all prior events which means that its length as a hex string must be greater than or equal to the length of any prior kn.

Now we have the concatenated string.

rj.kj.ij

Suppose we want to have two strings in the same KEL that are equal and that satsify all 9 properties.

lets start with a simple case with the minimum size of 3 hex characters (separators added to show the parts)

x.x.x

Obviously there can only be one since by virtue of strict monotonicity the first two parts rj and kj cannot ever be equal for two different events. The only variability is that the length of ij varies based on the number of codes in a given event. So if we have more than 16 codes we can get 2 or more digits for ij. This gives some flexibility in creating strings that may match.

Let there be given two potential events kn and kj where j > n. Ambiguity arises IFF the concatenated strings rn,kn.in == rj.kj.ij. This requires that the length of rn.kn.in equals the length of rj.kj.ij. Using the properties above we also have the length constraints that the length of rj >= length of rn and the length of kj >= length of kn.

So lets se if we can construct any two strings in the sequence for a given KEL that satisfy our constraints and could produce ambiguity.

Consider for example:

x.x.xx and x.xx.x

But since the length of rj == length of rn and by string monotonicity rj > rn the first digit must be different between the two strings so no ambiguity possible.

Indeed in general this means the length of rj must be > length of rn for there to be any possibility of a match (ambiguity).

So we try

x.x.xx and xx.x.x
But this violates 8 and 9 above since a two digit in added to a one digit kn must result in at least a two digit kj for j>n. Not only this but a two digit rj requires that kj be at least two digits.

So we try
x.x.xx and xx.xx.x but the lengths don't match

The only possible strings after x.x.xx that could be a match and satisfy the constraints must be at least 5 digits long, violating the constraint that the strings be of the same length.

Proof:
If one adds an extra digit to in to increase the length of string rn.kn.in to account for the fact that rj must be one digit longer than rn, then because of conditions 1- 9 above one must also increase the length of string kj relative kn by at least one digit which increases the length of string rj.kj.ij by at least 2 digits thereby forcing rj.kj.ij to be longer than rn.kn.in in every case. QED by contradiction. So, there is no ambiguity possible.