# Predictable universally unique identification of sequential events on
complex objects

Davi Pereira-Santos<EMAIL_ADDRESS>Gabriel Dalforno Silvestre
<EMAIL_ADDRESS>André C. P. L. F. Carvalho<EMAIL_ADDRESS>Instituto de
Ciências Matemáticas e de Computação, Universidade de São Paulo,
Trabalhador São-carlense Av. 400, São Carlos, 13560-970, São Paulo, Brazil

###### Abstract

Universal identifiers and hashing have been widely adopted in computer science
from distributed financial transactions to data science. This is a consequence
of their capability to avoid many shortcomings of relative identifiers, such
as limited scope and the need for central management. However, the current
identifiers in use are isolated entities which cannot provide much information
about the relationship between objects. As an example, if one has both the
identifiers of an object and its transformed version, no information about how
they are related can be obtained without resorting to an authority or
additionally appended information. Moreover, given an input object and an
arbitrarily long sequence of costly steps, one cannot currently predict the
identifier of the outcome without actually processing the entire sequence. The
capability of predicting the resulting identifier and avoiding redundant
calculations is highly desirable in an efficient unmanaged system. In this
paper, we propose a new kind of unique identifier which is calculated from the
list of events that can produce an object, instead of directly identifying it
by content. This provides an identification scheme regardless of the object’s
current existence, thus allowing to inexpensively check for its content in a
database and retrieve it when it has already been calculated before. We
propose these identifiers in the context of abstract algebra, where objects
are represented by elements that can be operated according to useful
properties, such as associativity, order sensitivity when desired, and
reversibility, while simplicity of implementation and strong guarantees are
given by well-known group theory results.

###### keywords:

Web information systems , Methodologies and tools , Data Science tools

> If you don’t know where you want to go, then it doesn’t matter which path
> you take.
>
> Lewis Carroll, Alice in Wonderland

##  1 Introduction

From the scientific binomial nomenclature [11] to national databases of
personal identification numbers, rigorous naming of objects or classes thereof
is an essential step when one intends to model some part of reality. For the
sake of clarity, in this text111Here, we focus on universal identifiers, i.e.,
those which are valid as identity within any scope., we will refer to such
attributed names and respective entities as identifiers and objects. Ideally,
the possession of an identifier would be equivalent to direct access to any
information of interest about its related object. However, there is a trade-
off related to the intended degree of abstraction/simplification. Perfectly
general mapping, i.e., one that serves for all possible purposes, would
contain all information about the object embedded in the identifier. In this
contrived case, the object would need to be represented by itself.
Alternatively, in a completely digital context, a lossless compression of the
object, when possible, could be used as such a perfect identifier. At the
opposite extreme, hash digests or simple nonordinal identification numbers
just show whether two objects are the same or not. This latter extreme would
require a companion database which one needs to resort to if any relevant
information about the object is needed. Some possibilities that lie between
these extremes are enumerated in Section 2 for different amounts of embedded
information.

Ideally, fetching data from a distributed unmanaged environment would only
need a single identifier. This identifier is the key to be provided when
querying databases in the network. However, if the desired object is
necessarily a result of some calculation, it is impossible to directly know
its deterministic identity beforehand without actually performing the
calculation. Traditionally, this is solved by providing the identities of all
parts involved in the output object generation. A simple example is to assign
an identifier to the calculation process and another to the input object
identifier. This pair of identifiers acts as a composite key to query
relational databases. In such a setting, the database needs an internal
structure that takes into account the different entities involved. Additional
complexity is present also from the user interface perspective due to the
different possible amounts of identifiers contained in a query: the output
object identity could be provided directly; or, in its absence, the input
object and its transformation process identities could be provided instead.
Moreover, this solution is not scalable with respect to the number of steps
that can sequentially transform the object, as a variable-length list of
identifiers would have to be included in the query. A traditional scalable
solution requires a more sophisticated database structure and querying
interface, departing from the concept of unmanaged environments - at least in
the sense of freedom and simplicity of implementation.

In this article, we propose a uniform identification approach for data and
processes. A typical storage for this proposal is as simple as key-value
engines, e.g., NoSQL [14] or relational databases with a single table. Both
entities (data and process) are seen as identified objects, where the amount
of values or steps inside each object can be arbitrary. In this scenario,
there is no distinction between data and process from the identification
perspective as any data object results from a process. We build upon this
assumption to set up convenient relationships between identifiers in different
levels during data transformation. For this purpose, we adopt abstract algebra
to operate over identifiers as part of a group. Consequently, well established
mathematical group properties can operate identifiers with sound guarantees
against ambiguity when needed. Applicability of the method is vast, including
data structure libraries, data science and current mainstream technologies
such as content addressable storages [20, 24]. Besides solving the previously
mentioned issues, the proposed approach inherently offers useful additional
functionalities that bring identity handling to a new level of flexibility.
The concepts presented here were implemented in a software
package222https://pypi.org/project/garoupa [19].

Prominent current identification schemes and related work about abstract
algebra are presented in Section 2. A brief overview, the intended scenario of
application (which is also part of our contribution), its requirements,
terminology, and notation are given in Section 3. The proposed method is
defined in Section 4. Finally, a brief comparison between the properties of
alternative abstract algebra groups is presented in Section 5, limitations of
our approach in Section 6 and future work in Section 7.

##  2 Related Work

Most of the existing work on data identification is related to the identifier
presentation, where semantics is often limited to the represented object,
i.e., there is little or no embedded information linking objects within the
identifier. Another type of related work includes groups from abstract algebra
suitable to be used as sets of identifiers that can be combined. Both types
are briefly reviewed in the next two sections.

###  2.1 Representation of identity

Different identifier types contain varying amounts of embedded information.
They can be one of the extremes mentioned in Section 1 or have an intermediate
kind. For instance, the binomial nomenclature provides information about the
taxonomic hierarchy of organisms with descriptive Latin words [11]. These
words can bring additional information like object appearance (species
phenotype), features or some tribute related to the object history (species
discovery), among others. Similarly, standard universally unique identifiers
(UUID) embed different kinds and degrees of information, depending on the
specification version [23]: time and/or local hardware attributes; random or
pseudo-random numbers; and, cryptographic hash of the content of objects. We
are specifically interested in hash-based identifiers (such as UUID versions 3
and 5), because, for a given object, they are deterministic, i.e., independent
of time and place of generation.

Another type of identification is provided by access tokens, which are usually
longer and contain information about user accounts and access permissions to a
given remote service [22]. We will focus on less volatile identifiers. ORCID
and DOI [13, 17] are examples of managed permanent identification systems for
researchers and publications. One application of our proposal is to have some
degree of interoperability with these established managed systems and also
with hash-based systems, e.g., git version control [10].

###  2.2 Abstract algebra

The chronological nature of data processing can be exactly represented by an
expression of juxtaposed identifiers. This sort of syntax appear in several
other contexts such as stack-based processors, reverse Polish notation and
concatenative programming [15]. A major advantage of using expressions is that
they can be reduced, combined or manipulated according to predefined laws.
Therefore, abstract algebra groups can fit exactly the intended task of
flexible identification of objects, provided the group allows arbitrarily long
sequences of operations - including repetitions. While we could not find any
studies on abstract algebra directly focused on our intended setting, adoption
of finite groups for hashing is not new. Incremental hash is the closest task
found in the literature for operating identifiers. This type of hash is more
general than needed here, as it operates text segments of size not previously
defined. A very straightforward implementation for the incremental hashes is
the adoption of the additive group of integers modulo $p$, where $p$ is prime
[4]. However, it is a commutative solution, which is inadequate to
unambiguously represent sequences of identifiers. For instance, consecutive
steps could be represented as a single element resulting from the group
operation applied over their identifiers, but due to the commutative nature of
addition, elements are order-insensitive.

On the other hand, finite non-Abelian groups are suitable for our task as long
as the commutativity degree is low enough or manageable within subgroups [8].
Some examples of non-Abelian finite groups are: symmetric, dihedral,
quartenion, unitriangular matrix, and wreath product of cyclic groups, among
others.

##  3 Overview

The broader context of this work is any application where the combination of
an arbitrary number of identifiers is meaningful. The combination can refer to
a variety of meanings - from a simple unordered collection of objects to a
sequence of events in time. As a motivating example application, we adopted
the common and difficult task of identity attribution to multiple-step multi-
valued data processes and outcomes throughout the text, as shown in Figure 1.

Figure 1: Multi-valued data processing is our motivating example of
application. In this scenario, the relationships between identities define
both the process and the content outcome.

A collection of values is provided as input to a sequence of functions to be
reduced, extended or internally changed. We consider the three-way
identification described as follows as a requirement of our intended target
setting.

A multi-valued data object and the process that can generate it are two
equivalent sources of identity. This is possible because the concept of
process always includes the data generation from the beginning, i.e., even the
inclusion of the first original value is part of the process. Therefore, the
same identifier is obtained from either content or process information. The
third equivalent source of identification is given by the history of
irreducible operations that generated the data object (Section 4.8). Process
and history steps often coincide. Briefly, an identifier can be calculated
from algebraic expressions (Section 3.2) generated under three different
perspectives:

  * 1.

process - general sequence of identifiers representing the steps intended by
the user;

  * 2.

data - sequence of identifiers representing values; and,

  * 3.

history - detailed sequence of identifiers representing the actually performed
(atomic) steps.

###  3.1 Terminology

Information is often organized into multiple parts in many contexts. We adopt
a collection of values to this end, e.g., tuples. Each processing step is a
function that transforms a collection of values. For the sake of simplicity,
we often refer to the collection as a tuple, but the collection can have
another type of structure such as a key-value map or a set. There is no
distinction between an original (i.e., non-transformed) value and the function
that inserts that value at the identification level. This is a consequence of
the three-way identification mentioned at the beginning of the Section 3,
i.e., a value and its insertion function have the same identifier. However, in
this text, we make the distinction between value and function identifiers to
be able to provide more meaningful examples. Both entities are identifiable
objects represented in our proposed abstract algebra group by value-elements
and function-elements. The adopted notation consider all objects as functions,
indistinguishably (Section 3.2).

An element has either original or composite nature. Singletons (i.e.,
$1$-tuples) and original functions are similar in the sense that they are
atomic objects, i.e., their respective elements are not a result of group
operations, because they do not represent a combination of objects. For
instance, a function written by a programmer or a file with temperature
measurements are original objects. Their corresponding group elements would be
generated directly from a hashing algorithm, or arbitrarily provided by the
programmer. On the other hand, a composite element would be generated when the
file is transformed by a function that converts Celsius degrees to Fahrenheit.
In this case, the resulting value-element is generated by the group operation
over the identifiers of the function and the file. This example is expressed
as an algebraic expression in the Section 3.2. Finally, a removal identifier
represents the removal of a value by its position in a tuple, or by its
name/key on a map.

###  3.2 Notation

Given the finite set $\bm{\mathrm{U}}$ of identifiers and set $\mathfrak{O}$
of objects, the function $\varphi\colon\bm{\mathrm{U}}\to\mathfrak{O}$ maps
identifiers to objects. This function can be considered surjective for
practical purposes and is hypothetically defined here just for convenience and
is actually an impossible333 Computationally intractable (or unsolvable, when
collisions are taken into account).  function because it represents hash
reversion of original elements and reverse mapping for composite elements.
Moreover, for the sake of simplicity, we call hash the function
$\gamma\colon\mathfrak{O}\to\bm{\mathrm{U}}$ defined as $\gamma=\varphi^{-1}$.
The disjoint union
$\bm{\mathrm{U}}=\mathfrak{V}\sqcup\mathfrak{F}\sqcup\\{\phi\\}$ represents
different categories of identifiable objects, respectively bound to groups of
adjacent letters from the Latin alphabet for convenience, except for $\phi$ as
a special reserved symbol:

  * 1.

General elements

$a,b,c,d\in\bm{\mathrm{U}}$;

  * 2.

Singletons, larger tuples and removed values
($\mathfrak{V}=\mathfrak{V}^{1}\sqcup\mathfrak{V}^{2,3\cdots}\sqcup\mathfrak{V}^{\times}$)

$x,y,z,w\in\mathfrak{V}^{1}$;

$u,v\in\mathfrak{V}^{2,3\cdots}$;

$\overset{\times}{x},\overset{\times}{y},\overset{\times}{z},\overset{\times}{w}\in\mathfrak{V}^{\times}\implies
x,y,z,w\in\mathfrak{V}^{1}$;

  * 3.

Original and composite functions
($\mathfrak{F}=\mathfrak{F}^{1}\sqcup\mathfrak{F}^{2,3\cdots}$)

$f,g,h\in\mathfrak{F}^{1}$; and,

$s\in\mathfrak{F}^{2,3\cdots}$.

  * 4.

Empty tuple/Identity function/Zero element

$\phi\in\bm{\mathrm{U}}$;

Resuming the example from Section 3.1, the conversion of temperature data in a
file identified by $x$ from Celsius to Fahrenheit through the function
identified by $f$ would be represented by $xf$. The expression $xf$ represents
the application of the function $\varphi(f)$ to the value $\varphi(x)$. If
other functions were to be applied, such as $\varphi(g)$ followed by the
insertion of an additional value $\varphi(y)$, the resulting identifier would
be represented by the sequence of group operations $xfgy$. Similarly, a multi-
valued data $\varphi(u)=\langle\varphi(x),\varphi(y)\rangle$ is also
represented by a product of identifiers: $u=xy$. Tuple identifiers are
operable by function-elements, similar to any other value-element: $uf=xyf$.
When the function generates a new value $\varphi(z)$, it extends the input
tuple. We derive a formula for adding new identifiers ($z$ in the example)
which is consistent with the identifier of the resulting tuple (Section 4.3).
Finally, some additional definitions are provided in the next sections.

####  3.2.1 Group and order

Given a set $\bm{\mathrm{G}}$ of identifiers and an operator $\cdot$, we refer
to the group $\langle\bm{\mathrm{G}},\cdot\rangle$ just as $\bm{\mathrm{G}}$.
The minimum non-trivial element order (Section 3.4.2) of $\bm{\mathrm{G}}$ is
represented by $\Omega(\bm{\mathrm{G}})$, and the order of an element
$a\in\bm{\mathrm{G}}$ is given by $\omega(a)$. The symbols $\bm{\mathrm{Z}}$
and $\bm{\mathrm{H}}$ are, respectively, the center and the maximal Abelian
subgroup of $\bm{\mathrm{G}}$. In this context, two properties on
commutativity are convenient to represent unordered values: $am=ma\forall
a\in\bm{\mathrm{G}},m\in\bm{\mathrm{Z}}$; and, $xy=yx\forall
x,y\in\bm{\mathrm{H}}$.

####  3.2.2 Identity element

The identity element $\phi$ represents both the empty tuple and the
reflexive444 Here, the term reflexive function is preferred over identity
function to avoid confusion with the identity element of a group.  function,
since neither of them change the tuple. In other words, when $\varphi(\phi)$
is considered as a null value, $xy\phi$ represents the inclusion of nothing
into a tuple, whereas when $\varphi(\phi)$ is considered as the reflexive
function $r(o)=o,o\in\mathfrak{O}$, the expression $xy\phi$ represents the
application of the function $r$. In both cases, the result is the same at the
object level:
$\langle\varphi(x),\varphi(y)\rangle\mathop{\raisebox{0.0pt}[3.5764pt][0.0pt]{\scalebox{0.6}[1.0]{\hbox{\set@color$\displaystyle\frown\hskip
1.0pt$}}}}\displaylimits\langle\phantom{|}\rangle=r(\langle\varphi(x),\varphi(y)\rangle)=\langle\varphi(x),\varphi(y)\rangle$.

####  3.2.3 Tuple-expression equivalence

Given a finite sequence of $k$ elements
$a_{1},a_{2},a_{3},\cdots,a_{k}\in\bm{\mathrm{U}}$, we define the tuple-
expression equivalence as $\langle a_{1},a_{2},a_{3},\cdots,a_{k}\rangle\equiv
a_{1}a_{2}a_{3}\cdots a_{k}$. This equivalence comes from the factual equality
$\varphi(\langle x,y\rangle)=\langle\varphi(x),\varphi(y)\rangle$ implicit in
the relationship between value objects - consequence of the three-way
identification requirement (beginning of Section 3). Additionally, the
equivalence is convenient when dealing with the Cartesian product between two
or more sets of identifiers (Section 4.6), allowing a direct map between
tuples and expressions.

####  3.2.4 Removal identifier

A removal identifier $\delta_{i}$ (or, $\delta_{\eta}$ for maps) is expected
to be provided as a means to represent the removal of a value by its position
$i$ in the data tuple (or, by its name $\eta$ in a map). For instance, when
$\delta_{2}$ (or $\delta_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>y\vphantom{I}}} }}}$) is applied to an expression $xyz$, a placeholder
$\varphi(\overset{\times}{y})$ is created in the resulting tuple:
$\langle\varphi(x),\varphi(\overset{\times}{y}),\varphi(z)\rangle$. Therefore,
$xyz\delta_{2}=xyz\delta_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>y\vphantom{I}}} }}}=x\overset{\times}{y}z$, where $\lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>is the name associated to the value $\varphi(y)$ in a map, and
$\overset{\times}{y}$ represents its absence. As a consequence,
$\varphi(\overset{\times}{y})$ is an object with no content, i.e.,
$\varphi(\overset{\times}{y})=\varphi(\phi)$. Such a placeholder is needed for
consistency between the expression and its represented output object as
explained in Section 4.3.6.

###  3.3 Compatibility

Compatibility is an important requirement for wide adoption of any
identification scheme as it allows for direct data exchange between new and
legacy systems. A current de facto standard is the 40-digit hexadecimal
digest. Often called hexdigests, they are base-16 identifiers composed only by
numbers and lower case letters up to the letter f. We adopt a specific
typeface for them, e.g.: [border-color=lightgray,
rounded,tight,padding=1pt,1pt] ea035db8b34a60ed5cbeaf568672a8f68aa1a39bI .
Hashing algorithms, for instance SHA-1 [26, 1], have been used to generate
hexdigests, and are capable of uniquely identifying an object for most
practical purposes [18].

Textual representation is convenient for digests because it is limited to
characters that do not lead to encoding incompatibility across different
software and hardware platforms. These characters are explicitly allowed by
official specification, and considered safe for use in uniform resource
identifiers (URI) [6]. URIs are a good example of critical application
regarding compatibility as they are at the core of Internet communication.
Apart from letters and numbers, some extra characters are considered safe by
the specification: [border-color=lightgray, rounded,tight,padding=1pt,1pt] -I
, [border-color=lightgray, rounded,tight,padding=1pt,1pt] .I , [border-
color=lightgray, rounded,tight,padding=1pt,1pt] _I and [border-
color=lightgray, rounded,tight,padding=1pt,1pt] ~I . Unfortunately, the
character [border-color=lightgray, rounded,tight,padding=1pt,1pt] ~I becomes
percent-encoded in some contexts [7]. This amounts to a total of 65 safe
characters, allowing for a base-64 alphabet, which is convenient to represent
identifiers from a large set. Therefore, we define the representational limit
of base-64 as a requirement for our intended setting. It represents more
objects than the 40-digit hexadecimal digest format without incurring in extra
digits. We take advantage of such a property combined with the fact that the
base-16 alphabet is a subset of the base-64 alphabet, as shown in Section 4.1.

###  3.4 Robustness

Each abstract algebra group has particularities that can affect the
feasibility of the identification system. Therefore, we define a common set of
requirements for the candidate group in the next sections. Except for the
computational cost, other requirements are expressed in terms of iterations
until failure. Probability of failure is given when applicable. For instance,
on average, an unmalicious collision occurs in 128-bit hashing algorithms such
as MD5 [21] after generating about $2.2\cdot 10^{19}$ hashes555 According to
the approximate formula for the birthday attack for 128 bits: $P_{n}\approx
1-e^{(-n^{2}+n)/2^{129}}$. , considering a perfect balance [5]. Conversely,
the collision probability of a random pair is $2^{-128}\approx 2.9\cdot
10^{-39}$.

Finally, cryptographic properties are not considered as requirements here.
While they may be found to hold to some extent depending on the application,
we anticipate that the identity of an applied function, depending on the group
and elements choice, is not guaranteed to be completely hidden in the
resulting element. For instance, an operation between elements
$a\in\bm{\mathrm{H}}$ and $b\notin\bm{\mathrm{H}}$ results in an element
$ab\notin\bm{\mathrm{H}}$ whose identifier is partly identical to the
identifier of $a$ due to the fact that $\bm{\mathrm{H}}$ is a group by itself.
As a consequence, operations involving its elements can only affect the part
of the identifier that refers to $\bm{\mathrm{H}}$, leaving the remaining
digits unchanged.

####  3.4.1 Commutability

In order to represent a sequence of events unambiguously, the operation over
identifiers in the candidate group $\bm{\mathrm{G}}$ must not commute.
Although the odds of sampling the same pair of elements twice and using each
of them in a distinct ordering is sufficiently remote when they come from a
uniform distribution, it is a matter of concern when the set of effectively
used identifiers is very small relatively to $|\bm{\mathrm{G}}|$. This is more
noticeable for function-elements as functions are expected to be reused, often
as part of a long composition. Such a reduced set implies the existence of
recurring elements, which increases the odds of a sub-expression
$ab\in\bm{\mathrm{G}}$ and its reverse $ba$ being used in the same
application. In this case, the ambiguity arises when $\varphi(ab)$ and
$\varphi(ba)$ are different objects. Hence, absence of ambiguity among pairs
is important to ensure that any expression, regardless of length, is also
unambiguous, e.g., $abc\neq acb\neq\cdots\neq cba$. Similarly, a sequence with
more than two identifiers is ambiguous if it contains at least one explicit or
implicit operation that commutes. For instance, the expression $abc$ has two
implicit elements $c,d\in\bm{\mathrm{G}}$: $c=ab$ and $d=bc$. Despite being
implicit, they should also not commute with any adjacent element in the
expression.

In the general case, the number of implicit and explicit operations in a
sequence is $\binom{l+1}{3}$. Let $P_{c}(\bm{\mathrm{G}})$ be the commuting
probability of a random pair sampled from $\bm{\mathrm{G}}$. The probability
$P_{m}$ of creating an ambiguous random expression with size $l$ is given by
Equation 1.

$\displaystyle P_{m}(\bm{\mathrm{G}},l)$
$\displaystyle=\min\left\\{1,~{}P_{c}(\bm{\mathrm{G}})\cdot\binom{l+1}{3}\right\\}$
(1)

Therefore, on average, an ambiguous expression is expected after $n$ samples
given by Equation 2, where the complementary probability is
$\overline{P}_{m}(\bm{\mathrm{G}},l)=1-P_{m}(\bm{\mathrm{G}},l)$.

(2) $\displaystyle\overline{P}(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>of n events\vphantom{I}}}})$
$\displaystyle=1-\overline{P}_{m}(\bm{\mathrm{G}},l)^{n}=0.5\implies
n=\underset{\overline{P}_{m}(\bm{\mathrm{G}},l)}{\log}~{}0.5$

####  3.4.2 Element Order

The order of a group element defines the limit on the number of times it can
be operated with itself before the result becomes the identity element. For a
practical extreme example of repetition, let $\varphi(g),g\in\mathfrak{F}^{1}$
be a function with the only purpose of incrementing a value object to count
how many times a function $\varphi(f),f\in\mathfrak{F}^{1}$ is applied to a
tuple $\varphi(u),u\in\mathfrak{V}^{2,3,\cdots}$. This leads to the expression
$ufg$ at the first iteration - as expected. After $t$ iterations the
expression becomes $u[fg]^{t}$. The inequality $t<\omega(fg)$ must be
respected, otherwise the expression becomes ambiguous:
$u[fg]^{t}=u[fg]^{t\bmod\omega(fg)}$. Ideally, the minimum non-trivial element
order $\Omega(\bm{\mathrm{G}})$ would be large enough to make it impossible to
overflow the limit imposed by the order $\omega$ of an element in a real
application. Depending on the application, when there are none or few
repetitions, very small $\Omega(\bm{\mathrm{G}})$ values are still suitable.

####  3.4.3 Compatibility Gap

Many groups do not fit into the representational limits imposed by the current
binary-oriented hardware. We define
$\xi_{\beta}(\bm{\mathrm{G}})=1-|\bm{\mathrm{G}}|\cdot 2^{-\beta}$ as the
compatibility gap of a group $\bm{\mathrm{G}}$ in relation to the expected
size $2^{\beta}$, which is the representational limit of $\beta$ bits. The gap
can be avoided through representational constraints at the digest level
(compatibility trick in Section 4.1); at the group level via direct product to
reduce it; or, probabilistically, if $\xi_{\beta}(\bm{\mathrm{G}})$ is
negligible.

####  3.4.4 Computational Cost

Multi-valued data is usually handled in memory as structures such as lookup
tables or lists. The extra processing overhead added by the identification
handling should be negligible when compared with the actual core data
processing in a given task. We would not expect the operation over identifiers
to have a significant difference in processing time when compared, e.g., to a
conventional hash applied to the structured content. This is a conservative
reference, but reasonable, as both current and proposed methods aim to provide
identification - despite the broader context and flexibility of the setting we
address. As a conservative reference, hashing small texts through MD5 takes
approximately $1.6\mu s$ in current hardware666 Time measured for hashing 1kiB
of data using Python 3.8.5 and processor Intel i7-8565U at 1.80GHz. . A more
realistic reference would consider the computational cost of constantly
hashing potentially large contents after each data modification. In such a
case, the cost of an algebra-based solution is comparatively negligible.

##  4 Proposed Method

We propose a partly hash-based UUID that includes the definition of an
operation to combine an arbitrary number of (potentially ordered) identifiers.
The use of a hashing algorithm from the literature for original values, and
the adoption of a group from abstract algebra fulfill this goal and enables
appealing incidental possibilities, such as reversibility and associativity.
The format of the identifier provided as input to the operation is backwards-
compatible with current UUID specification as long as the identifier is
represented in the standard hexadecimal format. Similarly, the output from the
operation can be directly fed into systems that handle or store standard UUIDs
as text.

Unfortunately, the groups whose size fits all elements exactly into a binary
representation behave poorly regarding commutativity and/or repetition of
operations. Therefore, we propose a simple compatibility trick to overcome the
need for a perfect match between group order and binary representation. It can
keep the digest size within the same number of digits even though the number
of bits is larger. This increases the group order, improving its robustness to
viable levels. We consider using 160 bits the most recommended choice,
targeting compatibility with 40-digit hashes as shown in Section 4.1. We name
it UT40.4 and propose it as a parameterized UUID version referring to: the
chosen group (UT); the size of the digest in digits (40); and, the value (4)
of a specific parameter of the unitriangular matrix group (details in Section
4.2). For the sake of brevity, the examples in this article are focused on
version UT40.4, intended to be compatible with most systems in use today. We
provide a reference implementation containing also two additional versions
with distinct digest sizes: UT32.4 and UT64.4 [19].

###  4.1 Identifier choice

We propose a trick to address the need for a larger identifier space without
losing compatibility. Its principle is to consider textual digests the only
legitimate type of representation of an identifier, ignoring how it would be
expressed as bytes or as a number. This brings independence from the actual
memory size/disposition needed to store it. Therefore, while a usual 160-bit
hexadecimal digest is represented by 40 digits from the alphabet [border-
color=lightgray, rounded,tight,padding=1pt,1pt] 0123456789abcdefI , the same
40 digits could represent a 240-bit base-64 digest using the alphabet [border-
color=lightgray, rounded,tight,padding=1pt,1pt]
0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-.I . Besides
allowing data exchange from/to hexadecimal systems, the greater number of bits
the trick provides prompts for a larger and, therefore, more robust group. At
the binary level, the chosen group has a size that fits within 30 bytes.
Different bases for each interval of textual identifiers are defined for the
sake of convenience when importing identifiers from legacy systems (A). In
short, the proposed identification scheme supports as input the following
intervals of identifiers, where $p=2^{40}\texttt{-}87$ is a prime number
corresponding to the UT40.4 version.

  * 1.

All base-16 identifiers (most used);

  * 2.

All base-62 identifiers (often used);

  * 3.

Additionally:

All 239-bit identifiers, i.e., 30 bytes with zero at the most significant bit;

All 39-digit base-64 identifiers, i.e., the most significant digit is [border-
color=lightgray, rounded,tight,padding=1pt,1pt] 0I ;

  * 4.

In the limit:

All base-64 identifiers in the interval $[0;p^{6}-1]$;

  * 5.

Special cases (more about order-sensitivity in Section 4.5):

Operating an identifier from the interval $[0;p-1]$ is order-insensitive;

Operations within the interval $[0;p^{4}-1]$ are order-insensitive; and,

Reserved prefixed identifiers, described as follows.

Elements from the larger order-insensitive subgroup only commute among
themselves. Their number amounts to about $2^{160}$ for version UT40.4 which
is conveniently representable by 40 hexadecimal digits. Thus, multiple
identifier can be imported from legacy systems and operated without imposing
any order on them. While the proposed group accepts many input formats, the
result of any further operation will always produce 240-bit base-64
identifiers.

The identifier $\rho=\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>and subsequent lexicographic elements are reserved to decompose a value-
element resulting from the application of a function that returns multiple
values (Section 4.3). Other identifiers, prefixed by [border-color=lightgray,
rounded,tight,padding=1pt,1pt] \--------------------I , are reserved for
removal identifiers (Section 3.2). They are padded with repetitions of the
digit [border-color=lightgray, rounded,tight,padding=1pt,1pt] .I until the
start of a numeric index or an alphanumeric name.

Original value-elements are generated by the first 239 bits of BLAKE3 hashing
algorithm [16] modulo $p^{4}$. Any other algorithm could be used, but we
specify one here as a reference to ensure all original values will produce
consistent identifiers across different systems. Additionally, BLAKE3 is
multithreaded and among the faster cryptographic hashing algorithms currently.
According to its authors, it is considered safe for all security purposes,
despite the adoption of less rounds than its conservative predecessor [2].
Function-elements can be generated in the same way as value-elements, i.e.,
through BLAKE3 hashing, except by not applying modulo $p^{4}$. The binary
content can be, e.g., the abstract syntax tree of the implemented function,
its bytecode, or a binary string containing a fully qualified name of the
function along with the parameters used. The uniqueness of function-elements
depends on this choice.

Software systems that require an identification scheme are often ported to
different languages and platforms. In this case, all versions of a function
can, and should, certainly share the same identifier, provided one can ensure
they perform the exact same transformation on data.

###  4.2 Group choice

After considering the properties of all groups enumerated in Section 2.2, we
opted for a unitriangular matrix group [27]. Ideally, the group order would be
a power of $2^{8}$ or, at least, a power of $2^{1}$, due to the
representational limitation imposed by computational bytes and bits,
respectively. However, commutativity and element orders are compromised in
such groups when compared to groups of odd order as far as we can tell from
the studied groups (Section 2.2). Additionally, Cauchy theorem states that at
last one element would have prime order $p$ if $p$ divides the group order
[9], including $p=2$. As a consequence, we resort to the compatibility trick
(Section 4.1) to allow the adoption of a group with order that is not exactly
a power of $2^{8}$, but it is a sufficient approximation.

Let $p$ be a prime number and $\bm{\mathrm{UT}}^{4}_{p}$ be the set of all
$4\times 4$ unitriangular matrices with entries in the field $\mathbb{F}_{p}$.
For the sake of simplicity, we refer to the group
$\langle\bm{\mathrm{UT}}^{4}_{p},\cdot\rangle$ just as
$\bm{\mathrm{UT}}^{4}_{p}$, where the operator $\cdot$ (or juxtaposition) is
the usual matrix multiplication modulo $p$. Accordingly, an arbitrary element
$a\in\bm{\mathrm{UT}}^{4}_{p}$ is defined by Equation 3.

$a=\begin{pmatrix}1&e_{12}&e_{13}&e_{14}\\\ 0&1&e_{23}&e_{24}\\\
0&0&1&e_{34}\\\ 0&0&0&1\end{pmatrix},\;\;e_{ij}\in\mathbb{F}_{p}$ (3)

Each matrix cell has $p$ possible values, which implies
$|\bm{\mathrm{UT}}^{4}_{p}|=p^{6}$. Therefore, the group UT40.4 has
$p=2^{40}\texttt{-}87$ to approximate the 240 bits needed by 40 base-64
digits. An advantage of this group is that all non-trivial elements have order
$p$ if $p\geq 5$. The commutativity degree of each group can be calculated
from the ratio between its number of conjugacy classes and its order [8, 25],
as shown in Equation 4.

$\displaystyle P_{c}(\bm{\mathrm{UT}}^{4}_{p})$
$\displaystyle=\frac{2p^{3}+p^{2}-2p}{p^{6}}$ (4) $\displaystyle
P_{c}(\bm{\mathrm{UT}}^{4}_{2^{32}\texttt{-}5})$ $\displaystyle\approx
2.5\cdot 10^{-29}$ i$\triangleleft$iUT32.4 $\displaystyle
P_{c}(\bm{\mathrm{UT}}^{4}_{2^{40}\texttt{-}87})$ $\displaystyle\approx
1.5\cdot 10^{-36}$ i$\triangleleft$iUT40.4 $\displaystyle
P_{c}(\bm{\mathrm{UT}}^{4}_{2^{64}\texttt{-}59})$ $\displaystyle\approx
3.2\cdot 10^{-58}$ i$\triangleleft$iUT64.4

Equation 5 defines a mapping $m\colon\bm{\mathrm{UT}}^{4}_{p}\to\mathbb{Z}$ to
represent elements according to the intervals introduced in Section 4.1:

$m(a)=e_{34}*p^{5}+e_{12}*p^{4}+e_{24}*p^{3}+e_{23}*p^{2}+e_{13}*p+e_{14}$ (5)

where $a$ and $e$ are defined in Equation 4. This setting groups commutative
elements at the lower range. Finally, the digest lexicographic order does not
follow the mapping order. Each identifier, instead, is composed of one or two
different bases to increase compatibility as shown in A. Textual
representation (base-16 or base-64) follow the little-endian encoding (most
significant digit to the right) to ensure that visually adjacent elements are
actually distant from each other according to the mapping cited above. This
choice favors unique digits at the left of the identifier and also defines
reserved elements $\rho_{\texttt{+}i}$ that are distinct in the part of the
identifier corresponding to elements in
$\bm{\mathrm{G}}\setminus\bm{\mathrm{H}}$.

###  4.3 Multi-valued data

In this section, we present design choices related to the representation of
objects and handling of multi-valued data that enable algebraic expressions to
cover most data processing workflows. Specifically, we target the
informational equivalence of possessing a data object and knowing its
generating process. Thus, identification can be conveniently obtained in two
independent ways (aside from history mentioned in Section 3):

  * 1.

from data \- the identifier results from operating the internal $k$ value-
elements of a multi-valued data object $\varphi(u),u\in\mathfrak{V}^{k}$;

  * 2.

from process \- the identifier results from operating the $t$ identifiers of
the steps within the composite function $\varphi(s),s\in\mathfrak{F}^{t}$ that
generate $\varphi(u)$.

Except for the reflexive function $\phi$ and asynchronous identifiers (Section
4.9) which can represent metadata, all functions are expected to affect parts
of the data tuple. Unneeded values present at the tuple are expected to be
ignored by the function and to be kept at the output tuple. Maps (lookup
tables) are more informative than tuples, and, therefore, they are also
considered as a possible type of input data structure in a separate section
(Section 4.4).

####  4.3.1 Insertion

A relevant feature of our proposed method is the possibility to simplify the
representation of values and functions by considering both as functions. A
value-element represents a value, but it can also be seen as its insertion
function, as illustrated by Content 3 in Figure 1. The insertion of a value
$\varphi(y)$ into a tuple $\langle\varphi(x)\rangle$ has the same
representation regardless of it being interpreted as a function application or
as a composite value expression: $xy$. Therefore, a multi-valued data
$\varphi(u),u\in\mathfrak{V}^{2}$ with two values $\varphi(x)$ and
$\varphi(y)$ can be seen as a composition of insertion functions: $u=xy$.

####  4.3.2 Single value creation

The only difference between insertion and creation, from the output tuple
perspective, is that the former extends the tuple to the right, while the
latter extends it to the left. Such distinct outcomes are due to the fact that
the former has no input, while the latter is dependent on the content of the
tuple. For instance, when the tuple extension results from a function
$\varphi(f)$ dependent on input values, a right extension would lead to the
problematic implication $xf=xy\implies y=f$. Clearly, $y$ would always be the
same in this case, even when different input values are provided to
$\varphi(f)$. On the other hand, the adopted convention correctly leads to a
$y$ that depends on $x$: $xf=yx\implies y=xfx^{-1}$. For the same reason,
(creation) functions must have a non-commuting identifier, i.e.,
$f\in\bm{\mathrm{G}}\setminus\bm{\mathrm{H}}$.

####  4.3.3 Multiple values creation

When a function $\varphi(g)$ generates new values, e.g., $\varphi(z)$ and
$\varphi(w)$, it also extends the tuple
$\varphi(u)=\langle\varphi(x),\varphi(x)\rangle$ to the left as explained in
Section 4.3.2:
$\varphi(g)[\varphi(u)]=\varphi(g)[\varphi(xy)]=\langle\varphi(z),\varphi(w),\varphi(x),\varphi(y)\rangle$.
At the expression level, the same pattern for single value creation emerges:
$ug=xyg=zwxy\implies zw=xyg[xy]^{-1}$. However, the elements $z$ and $w$ are
not defined. Therefore, the element $zw$ must be decomposed in two different
factors. The general case for multiple values is solved as follows.

Let $\varphi(v),v\in\mathfrak{V}^{2,3\cdots}$ be a multi-valued data object
and $\varphi(f),f\in\mathfrak{F}^{1}$ be a function that returns $k$ values.
Their respective elements $x_{i}\in\bm{\mathrm{G}},0\leq i<k-1$ are calculated
according to Equation 6, where element $\rho_{\texttt{+}i}\in\bm{\mathrm{G}}$
represents the special $i$th element after the reserved element $\rho$
(Section 4.1) in digest-based lexicographic order.

$\displaystyle\begin{split}\left.\begin{array}[]{r@{\mskip\thickmuskip}l}\begin{aligned}
\bm{x}&=vfv^{-1}\\\ \bm{x}&=\prod\limits_{j=1}^{k}x_{j}\\\
x_{i+1}&=\bm{x}\rho_{\texttt{+}i}\end{aligned}\mskip 5.0mu plus
5.0mu\end{array}\right\\}\quad\implies\quad\begin{array}[]{r@{\mskip\thickmuskip}l}x_{k}\mskip
5.0mu plus
5.0mu&=\left(\prod\limits_{j=1}^{k-1}x_{j}\right)^{-1}\bm{x}\end{array}\end{split}$
(6)

####  4.3.4 Substitution

When a function $f$ replaces a value $\varphi(x)$ by $\varphi(x)^{\prime}$,
the new value-element can be derived from the expression, e.g.:
$xyf=x^{\prime}y\implies x^{\prime}=xyfy^{-1}$. When a function creates and
also replaces multiple values, identifiers of replaced and created values are
appended to the left of the unchanged elements, creating the expression
according to the factorization explained in Section 4.3.3. Insertion functions
cannot replace existing values.

####  4.3.5 Removal by identity

From the process point of view, depending on internal data identifiers to be
able to perform an operation has no use. However, if one has access to the
container object, internal values can be removed while keeping consistency
between data and process identifiers.

Value-object removal from the tuple right extremity is trivial. It is
sufficient to apply the inverse of the chosen element to obtain the expression
for the remaining data, e.g.: $xyy^{-1}=x$; or, $x^{-1}xy=y$. When the value
is in the middle of the tuple, all identifiers from the extremity up to the
chosen element must be known so they can be removed and reinserted afterwards.
For instance, the expression $a=xyzw[yzw]^{-1}zw$ represents the removal of
value $\varphi(y)$ from $\varphi(xyzw)$, leading to $a=xzw$.

Removal by identity is not traceable in history when performed at any place
other than the right extremity of the tuple. This is due to the nature of
process expressions which, aside from the exception of unordered elements, are
chronologically ordered from left to right. Traceability is only possible
while process and history are consistent. In this context, one cannot edit the
process expression other than right-appending elements (or their inverses).
Otherwise, history would need to be rewritten to keep consistency, which would
clearly undermine the possibility of a reliable audit.

####  4.3.6 Removal by index

Removal by index does not depend on either content or identity of data
objects. It is a function object such as any other transformation step. The
identifier $\sigma_{i}$ has the parameter $i$ indicating the position in the
tuple where a value should be removed. Although more realistic than removal by
identity, removal by index has a more complex implementation that requires a
placeholder $\overset{\times}{w}$ for a removed value
$\varphi(w),w\in\mathfrak{F}^{1}$(Section 3.2.4). An example is given as
follows, showing why this is the case.

Let the removal of the second element from the tuple
$\langle\varphi(x),\varphi(y)\rangle$ be the desired operation. If a
placeholder is not used, this would result in the implication
$xy\delta_{2}=x\implies\delta_{2}=y^{-1}$, which is impossible in practice,
since only the index is available, not the identifier $y$. The function-
element $\delta_{2}$ cannot be defined in terms of identifiers. It is an
identifier itself, that uniquely identifies a removal operation that could be
applied to any tuple with a suitable length. On the other hand, when a
placeholder is employed, the symbol $\overset{\times}{y}$ can be the free
variable, as shown by the implication
$xy\delta_{2}=x\overset{\times}{y}\implies\overset{\times}{y}=y\delta_{2}$.

Despite being algebraically possible, removal by identifier and by index are
not robust solutions. Additionally, operations in tuples in general, including
removal by index, can lead to operational mistakes due to the dependence on
how values are ordered along indexes. Therefore, when handling tuples, the
possibility of removing values could ideally be suppressed depending on the
application. A map is a better structure for multi-valued data objects,
presented in the Section 4.4.

###  4.4 Map

Here, a map is a structure where textual keys point to their respective
values. This enables the use of functions dependent on keys instead of
indexes. An immediate advantage is to provide protection against arbitrarily
ordered objects and to offer more flexibility for the disposition of the
entries in a data object. Tuple operations described in previous sections
still apply for maps. Removal by index also applies, provided the map is
order-sensitive. Removal by name follows the same mechanism as explained in
Section 4.3.6.

Order-insensitive maps have the convenience of having a single identifier for
different arrangements of the same content. For instance, in most
applications, e.g., dealing with original value-elements
$x,y,z\in\mathfrak{V}^{1}$, the inequality $xyz\neq yzx$ brings no advantage.
This is actually detrimental for original values as it means that each
permutation of the entries will have a different, redundant, identifier
assigned. The only difference between them is the order in which the values
were inserted. In this context, maps enable the adoption of commutative
elements, e.g., $x,y,z\in\bm{\mathrm{H}}\setminus\bm{\mathrm{Z}}$ to represent
a collection of original value-elements $xyz=xzy=zxy=\cdots$ without
redundancy while still keeping order in relation to a derived value-element
$w\in\bm{\mathrm{G}}\setminus\bm{\mathrm{H}}$. The following equations would
hold as expected: $xyzw=xzyw=zxyw$; and, $xyzw\neq xwyz\neq wxyz$.

An important requirement for this solution is to always have the key embedded
into original value-elements. Otherwise, two different key-value pairs, e.g.,
$\langle\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{x1\vphantom{I}}}},\varphi(x)\rangle$
and $\langle\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{x2\vphantom{I}}}},\varphi(x)\rangle$
would have the same identifier due to the coinciding content $\varphi(x)$.
Ideally, the embedding should not affect the order-sensitivity of the map
entries, but it still have to represent key-value pairs unambiguously. Putting
the key into the expression as an unordered element would not be a valid
solution, e.g.: $[a\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{a\vphantom{I}}}})][b\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{b\vphantom{I}}}})]$
would be the same as $[b\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{a\vphantom{I}}}})][a\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{b\vphantom{I}}}})]$.
One could avoid implying this equality by hashing the key as an ordered
element, but it would impose order to the entry, which is also detrimental to
the purpose of inserting original values in any order. Therefore, an embedding
mechanism that preserves the order-sensitivity while keeping key-value
relationships is needed.

We propose a lifting mechanism based on category theory to map both key and
value to a non-commutative subgroup $\bm{\mathrm{L}}\subset\bm{\mathrm{G}}$
where they are combined through an order-sensitive operation and the result is
mapped back to $\bm{\mathrm{H}}$. The lifting to the subgroup is formed by
switching positions of the matrix cells $e_{23}$ and $e_{12}$ according to the
definitions in Equation 3. The unlifting is done by switching the same cells.
For illustration, let $\hat{~}{}c$ be the lifted version of
$c\in\bm{\mathrm{H}}\setminus\bm{\mathrm{Z}}$. The expression
$\hat{~}{}[\hat{~}{}a\hat{~}{}\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{a\vphantom{I}}}})]\hat{~}{}[\hat{~}{}b\hat{~}{}\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{b\vphantom{I}}}})]$
is different from $\hat{~}{}[\hat{~}{}b\hat{~}{}\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{a\vphantom{I}}}})]\hat{~}{}[\hat{~}{}a\hat{~}{}\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{b\vphantom{I}}}})]$
as expected. Additionally, this choice avoids keeping several identifiers for
the same content in the database, because $x$ refers to the actual content,
while $x\gamma(\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color@gray@fill{.25}\texttt{a\vphantom{I}}}})$
refers to the pair key-value. The hashing of the key is replaced by a
convenient conversion from text to digest detailed in B.

###  4.5 Nested data objects

While flat data structures are sufficient for most applications, nested
structures can potentially represent data with unlimited complexity. However,
a nested data structure such as
$\varphi(u)=\langle\varphi(x),\langle\varphi(y),\varphi(z)\rangle,\varphi(w)\rangle$
leads to an ambiguous identifier $xyzw$ that could represent the same data in
a flat structure:
$\varphi(u)\neq\langle\varphi(x),\varphi(y),\varphi(z),\varphi(w)\rangle$.
Here, we consider the use of maps as part of the solution. The inner map
identifier would be generated in a similar manner to that of an original value
(Section 4.4), i.e., embedding the key through lifting:
$u=x\hat{~}{}\\{\hat{~}{}[yz]\hat{~}{}\gamma(\eta)\\}w$ where $\eta$ is the
key of the inner map for the previous example.

###  4.6 Parameterized functions

Functions can be parameterized. For instance, a parameter could be a constant
indicating the names of input and output values: $xyf_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>x\vphantom{I}}} }}\to\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>z\vphantom{I}}} }}}$. Different parameter values usually imply different
function identifiers, e.g., $g_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>s=1\vphantom{I}}} }}}\neq g_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>s=2\vphantom{I}}} }}}$. Let the sets $F,G$ be identifiers for all possible
parameterizations of the functions $\varphi(f),\varphi(g)$, respectively. The
set of identifiers for all possible composite functions of $\varphi(g)_{*}$
with $\varphi(f)_{*}$ can be expressed by the Cartesian product $H=F\times G$.
The tuple-expression equivalence (Section 3.2) means that $H$ is a set of
parameterized $[fg]_{*}$ expressions that is ultimately a set of identifiers.
For the sake of convenience, when the different alternatives for a specific
position in the set expression includes parameterizations of more than one
function, it can be represented by the plus sign, meaning “union of sets”,
e.g.: $(F+G)\times H$. Set expressions are useful to describe a sequence of
events without knowing the parameter values a priori.

A current widespread example of sequence of parameterized functions is a
machine learning workflow. Each step can be modeled as an identified function:
acquisition, cleansing, partition, scaling, enhancement, prediction,
evaluation, etc. If on one hand, an expression of identifiers can be
simplified, resulting in the predicted identifier for the future outcome; on
the other hand, a set expression such as the previously mentioned Cartesian
product, when simplified, results in a set of outcome identifiers.

###  4.7 Functional Paradigm

The proposed notation for multi-valued data enables the representation of
partial function application [12]. A function $\varphi(f_{\text{
\lfbox[border-color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>x\vphantom{I}}} }},\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>y\vphantom{I}}} }},\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>z\vphantom{I}}} }}\to\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>z\vphantom{I}}} }}})$ expects three values, but can be partially applied to
any sequence of values starting from the rightmost value. For instance, if
$\varphi(f)$ is applied to two values, the identifier $yzf$ represents an
intermediate function $\varphi(g_{\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>x\vphantom{I}}} }}\to\text{ \lfbox[border-
color=lightgray,tight,padding={0.6pt,-2.5pt}]{
{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>z\vphantom{I}}} }}})$ that could be reused when applied to different
$\varphi(x)$ values.

Moreover, representing a data flow as an expression of identifiers makes it
possible to adopt lazy structures, avoiding duplicate calculations to a great
extent. When the expression is solved, the resulting identifier is the exact
identity of the data object, before any calculation within the flow is
started. One can also establish the identity of each value in the outcome by
following the definitions from the previous sections.

###  4.8 History

Some applications require all performed steps of a process to be registered in
detail for audit purposes. In this case, the data structure would keep track
of every modification since the creation of the original value-object. A list
of identifiers is usually sufficient for such a goal. This list is updated
after each atomic transformation. Some items in the list can be sets, when
elements from $\bm{\mathrm{H}}$ are present, to reflect commuting
subexpressions. Other items can be tuples, when composite functions are
present. For instance, the history $\langle\\{x,y\\},\langle
g,h\rangle,w\rangle$ accounts for: value-elements $x,y$ that are order-
insensitive; a function composition $\varphi(h)\circ\varphi(g)$; and, a value
insertion $\varphi(w)$.

Dynamic functions, i.e., functions that dynamically apply different substeps
according to the input content, can also contribute informatively to the
history while keeping a predictable output identifier. In such a case, an
extra identifier is needed as an adaptor within the expression. For instance,
$\varphi(f)$ can choose to apply $\varphi(g)$, $\varphi(h)$ or both depending
on the input value, e.g., $\varphi(x_{1})$ or $\varphi(x_{2})$. Supposing
$\varphi(x_{1})$ triggers the application of $\varphi(h)$, and
$\varphi(x_{2})$ triggers $\varphi(gh)$, adaptors $\bar{f}_{1}$ and
$\bar{f}_{2}$ would keep consistency between process and history as follows:
$x_{1}f=x_{1}h\bar{f}_{1}\implies\bar{f}_{1}=h^{-1}f$; and,
$x_{2}f=x_{2}gh\bar{f}_{2}\implies\bar{f}_{2}=[gh]^{-1}f$.

###  4.9 Asynchronous Identifier

Finally, group $\bm{\mathrm{UT}}^{4}_{2^{40}\texttt{-}87}$ has a maximal
Abelian subgroup with order $|\bm{\mathrm{Z}}|=2^{40}-87$. Identifiers from
$\bm{\mathrm{Z}}$ always produce the same result regardless of the point at
which it is inserted into the expression. This property can be useful to
represent metadata or any type of step that has no relationship of dependence
with any other step.

##  5 Comparison

We could not find any proposal in the literature that could be directly
compared to our method. This is mostly because the originality of the work
includes the stated problem/scenario itself, whose applicability is broader
than ordinary identification. However, we can compare
$\bm{\mathrm{UT}}^{4}_{2^{40}\texttt{-}87}$ to alternative groups.

Symmetric groups denoted by $\bm{\mathrm{S}}_{n}$ and General Linear groups
denoted by $\bm{\mathrm{GL}}_{n,q}$ are common examples of finite non-Abelian
groups. Both have a large proportion of elements with order 2, which makes
them unfeasible for our setting. Some Dihedral groups denoted by
$\bm{\mathrm{D}}_{2n}$ have no compatibility gap:
$\forall\beta\in\mathbb{N},\exists n\in\mathbb{N}$ such that
$\xi_{\beta}(\bm{\mathrm{D}}_{2n})=0$. Special Linear groups denoted by
$\bm{\mathrm{SL}}_{n,q}$, where elements are matrices whose determinant is
equal to the unit of the field $\mathbb{F}_{q}$, can have a low compatibility
gap and low commuting probability as shown in Table 1.

Table 1: Compatibility gap ($\xi_{192}$), commuting probability ($P_{c}$) and
minimum non-trivial element order ($\Omega$) for the groups studied as
candidates for $\bm{\mathrm{U}}$. Non-integer values are approximated.

$\bm{\mathrm{G}}$ | $\xi_{192}(\bm{\mathrm{G}})$ | $P_{c}(\bm{\mathrm{G}})$ | $\Omega(\bm{\mathrm{G}})$
---|---|---|---
$\bm{\mathrm{S}}_{46}$ | 0.123 | $1.92\cdot 10^{-53}$ | 2
$\bm{\mathrm{A}}_{46}$ | 0.561 | $1.92\cdot 10^{-53}$ | 2
$\bm{\mathrm{D}}_{2^{192}}$ | 0 | $3.98\cdot 10^{-59}$ | 2
$\bm{\mathrm{GL}}_{3,2642239}$ | $2.40\cdot 10^{-5}$ | $2.94\cdot 10^{-39}$ | 2
$\bm{\mathrm{GL}}_{4,4093}$ | 0.012 | $4.52\cdot 10^{-44}$ | 2
$\bm{\mathrm{SL}}_{3,16777213}$ | $1.43\cdot 10^{-6}$ | $2.67\cdot 10^{-51}$ | 2
$\bm{\mathrm{SL}}_{4,7129}$ | 0.010 | $5.80\cdot 10^{-47}$ | 2
$\bm{\mathrm{W}}_{2,7}\times\bm{\mathrm{W}}_{2,13}\times\bm{\mathrm{W}}_{2,23}$ | 0.998 | $2.28\cdot 10^{-7\phantom{8}}$ | 7
$\bm{\mathrm{UT}}^{4}_{2^{32}\texttt{-}5}$ | $6.98\cdot 10^{-9}$ | $2.52\cdot 10^{-29}$ | $2^{32}\texttt{-}5$
$\bm{\mathrm{UT}}^{4}_{2^{40}\texttt{-}87}$ | $(4.75\cdot 10^{-10})^{*}$ | $1.50\cdot 10^{-36}$ | $2^{40}\texttt{-}87$

  * 1.

*Value refers to $\xi_{240}$.

However, neither $\bm{\mathrm{D}}_{2n}$ nor $\bm{\mathrm{SL}}_{n,q}$ have a
high $\Omega$. Therefore, based on the Lagrange Theorem, we narrowed the
options down to non-Abelian $p$-groups. As a result, we studied Sylow
$p$-subgroups of both $\bm{\mathrm{S}}_{n}$ and $\bm{\mathrm{GL}}_{n,p}$. If
$n=p^{k}$, then the Sylow $p$-subgroup of $\bm{\mathrm{S}}_{n}$ is the
iterated wreath product of the cyclic group $\mathbb{Z}_{p}$ defined in
Equation 7.

$W_{k,p}=\underbrace{\mathbb{Z}_{p}\wr\mathbb{Z}_{p}\wr\dots\wr\mathbb{Z}_{p}}_{k\;\text{times}}$
(7)

This group has a minimum non-trivial order equal to $p$. However, the group
order $|W_{k,p}|=p^{\frac{p^{k}-1}{p-1}}$ grows exponentially with $p$. This
implies that low $p$ values are needed, implying in low orders. Furthermore,
the compatibility gap and the commuting probability are also relatively high
as shown in Table 1.

Finally, the Sylow $p$-subgroup $\bm{\mathrm{UT}}^{4}_{p}$ of
$\bm{\mathrm{GL}}{4,p}$, has a good balance of properties. It has a low
compatibility gap and commuting probability along with a high minimum non-
trivial order. Moreover, its implementation is simple as the operations are
performed over small matrices.

##  6 Limitations

Some design choices were made looking for the simplest solution. However, some
of them were arbitrary and can be changed if any unforeseen limitation is
found in the future.

###  6.1 Reference elements

The choice of $\rho=\lfbox[border-
color=lightgray,rounded,tight,padding={1pt,1pt}]{\footnotesize{\color[rgb]{.25,.25,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.25,.25}\pgfsys@color@gray@stroke{.25}\pgfsys@color<EMAIL_ADDRESS>and its lexicographic successors $\rho_{\texttt{+}i}$ as a reference to find
factors to compose a multi-valued data creation (Section 4.3.3) is solely
based on representational convenience as the symbol [border-color=lightgray,
rounded,tight,padding=1pt,1pt] -I is outside the base-62 range of characters
and can be regarded as “internal use only”. This choice has high probability
of being equivalent to choosing other elements, due to the nature of the group
$\bm{\mathrm{UT}}^{4}_{p}$. However, some investigation about the properties
of those specific elements could help to identify any side effect when using
them, specially regarding corner cases, e.g., when a massive amount of values
is created at once. Despite being a sequence of successive digests in
alphabetical order, the corresponding elements are orders of magnitude distant
from each other due to the intentional adoption of the little-endian encoding
(Section 4.2).

###  6.2 Operations

The left insertion convention (Section 4.3.2) implies that a new value-element
$z$ produced by the application of a function-element $f$ over
$u\in\mathfrak{V}^{2,3\cdots}$ is defined by $z=ufu^{-1}$. This leads to the
output tuple $\varphi(uf)=\varphi(\langle ufu^{-1},u\rangle)$. At the present,
we do not see any ambiguity in $\varphi(uf)$. However, we cannot anticipate
all outcomes for every possible application.

The proposed method would be more algebraically flexible if it had two
operations ($+$ and $\cdot$) with the distributive property over the finite
set of elements. Unfortunately, it is theoretically impossible to define a
non-commutative finite division ring according to the Wedderburn little
theorem [3].

###  6.3 Group

We do not expect binary digests are used, but some points are worth of notice
if this is the case. While the group
$\bm{\mathrm{UT}}^{4}_{2^{40}\texttt{-}87}$ handles 240-bit digests, it can
only accept elements with a lexicographic rank lesser than $p^{6}$, which is
not an exact power of 2: $2^{239}<p^{6}<2^{240}$. The same constraint applies
for creating a commuting element $x\in\bm{\mathrm{H}}$. Its rank should be
lesser than $p^{4}$. Additionally, when importing binary data from legacy
systems, the inequality $2^{159}<p^{4}<2^{160}$ should be taken into account.
In both cases, the rank should not be less than $p$ (to skip
$\bm{\mathrm{Z}}$, the center of the group), where elements would commute with
any other in $\bm{\mathrm{G}}$. Analogous inequalities hold for 384-bit
digests ($p=2^{64}\texttt{-}59$), whose upper limits are 384 and 256 bits,
respectively.

The first commuting pair of elements is expected, on average, after $2.1\cdot
10^{48}$ samples for UT40.4 (Section 3.4). Conversely, expressions are limited
in length by Equation 1 to avoid ambiguity777 Avoiding ambiguity only makes
sense when a limited set of group elements is effectively used along the
existence of an application. Otherwise, every expression is guaranteed to have
many algebraically equivalent expressions. . For instance, more than $3\cdot
10^{15}$ expressions with length $10^{7}$ will be sampled, on average, before
the first ambiguous one is produced according to Equation 2. This is a
comfortable limit as the length for expressions in most applications will
probably be in the order of a hundred or less elements. Finally, the minimum
order $\Omega(\bm{\mathrm{UT}}^{4}_{p})$ limits the number of repeated
operations by $p$, which is above $1.1\cdot 10^{12}$.

###  6.4 Scenario

Some limitations are intrinsic of our intended application scenario. We
adopted the textual digest as the only legitimate format to exchange
identifiers between systems. This allows a hexdigest such as [border-
color=lightgray, rounded,tight,padding=1pt,1pt]
ffffffffffffffffffffffffffffffffffffffffI to be used directly as input to our
base-64 proposed identification scheme. Naturally, the binary representation
differs in most cases as the bases are not the same. This requires caution if
one needs to compare digests in other formats. Additionally, this option for
textual representation can add a small, mostly negligible, overhead due to
conversion between formats.

Function $\varphi$ is not bijective, i.e., the same object can happen to be
identified by more than one identifier. While uncommon, two different
sequences can produce the same object. Since our approach actually identifies
the process, not just its current resulting object at hand, it is impossible
to guarantee that such a result is unique. This is not a problem for any of
the intended uses for our scheme, but should be taken into account if a
specific application produces many similar objects and storing space is a
strong priority. In such a case, storing the object alongside its hash is
recommended to identify it also by content. A lookup table linking all its
identities to the hash would avoid redundant content entries in the database.
It is important to notice that the possibility of redundant calculations
remains. This is the expected behavior and intrinsically unsolvable by any
identification schema of choice, given the nature of the scenario.

###  6.5 Other

The suggested hashing algorithm BLAKE3 can process trillions of petabytes,
which is a comfortable limit for current computational needs for a single
value.

##  7 Future Work

We intend to explore some new possibilities that $5\times 5$ matrices provide,
e.g., additional useful subgroups and lower commutability, despite having a
considerably lower minimum order as a downside:
$\Omega(\bm{\mathrm{UT}}^{5}_{p})\approx 1.7\cdot 10^{7}$ for 40 digits.
Regarding the present group ($\bm{\mathrm{UT}}^{4}_{p}$), which is based on
$4\times 4$ matrices, we plan to perform an empirical evaluation of the
proposed scheme by creating a very small group of identifiers and generating
identification expressions exhaustively from it. This approach would enable us
to discover unexpected artifacts such as a collision/ambiguity rate above
acceptable levels under certain circumstances; or, to identify new important
limits of the present scheme, among other possibilities. Another possible
study is to explore formal aspects in detail in a complementary article.

##  8 Conclusion

In this article, we presented a new scenario for identification systems with
an abstract algebra based solution. Groups from algebra showed to be specially
suitable due to their incidental useful properties for the task of
identification. They have an identity element that can represent any operation
that does not change data such as: storing; logging; or, any monitoring step.
They are associative, thus representing a composition of several functions as
a single identifier. Their non-commutative elements can represent
chronologically ordered events. The commutative subgroups are also useful as
they reduce multiplicity of identities for segments within expressions that do
not need ordering, such as original values. Invertibility can be used to
revert an operation or to solve an equation where the source, the process or
the outcome are unknown. Finally, operations are always closed, i.e., no
expression can produce an element outside the finite initial set of
identifiers.

We targeted the scenario where multi-valued data objects are built or
transformed by a sequence of functions. In this scenario, one can determine
the identity of the outcome (or of any value within it) by operating directly
on the identifiers from three independent sources of algebraic expressions:
the process; the history; or, the internal resulting identifiers. This
flexibility extends current UUID solutions in novel directions that are only
marginally explored in this article.

We presented $\bm{\mathrm{UT}}^{4}_{p}$ as a concrete group for our scheme.
Three versions were implemented in software: UT32.4, UT40.4 and UT64.4. The
proposed method is simple enough to be easily implemented by third parties and
also for other programming languages.

##  9 CRediT Author Statement

Davi Pereira-Santos: Conceptualization, Investigation, Software, Validation,
Writing, Review & Editing. Gabriel Dalforno Silvestre: Formal analysis,
Software (alternative groups), Writing (part of sections 4.2 and 5). André C.
P. L. F. Carvalho: Supervision, Funding acquisition, Resources, Review &
Editing.

##  10 Acknowledgment

This work was supported by CNPq and FAPESP [grant numbers 2013/07375-0,
2019/01735-0 (CEPID CeMEAI)]. We are also grateful for the initial advice from
Mark Gritter and Jyrki Lahtonen in some topics of group theory.

##  Appendix A Hexdigest Compatibility

Two ranges of identifiers are relevant from the compatibility perspective - as
shown in Table 2. The range of hybrid elements is compatible with hexdigests
containing one suppressed digit; the range of order-sensitive elements is
compatible with hexdigests and base-62 digests. One digit is suppressed in
different positions at the digests of unordered and hybrid elements to avoid
ambiguity between elements of the three types, and also to separate digits
from different bases. The placeholder _ replaces the suppressed digit and its
position (or absence) indicates the type of the element. This choice allows to
import the same hexdigest as a commutative or non-commutative element. Non-
commutative elements are prioritized in this design because they have the most
general type, i.e., they can be used as commutative ones by mistake without
ambiguity while this would not hold for the opposite choice. As a minor side
effect, commutative elements keep only 31 of their original digits due to
suppression.

Table 2: Identifier ranges according to element type. All range types contain
a subset of hexadecimal digests to provide compatibility.

Group |  Element Type |  LRI | Digest Range (UT32.4) | Base |
---|---|---|---|---|---
G |  H |  Z |  identity |  $0$ |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] 0000000000000000000000000000000000000000I | – |
unord. |  $[1;p[$ |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] 0_100000000_____________________________I $\cdots$ | 16_16 |
[border-color=lightgray, rounded,tight,padding=1pt,1pt] 0_fffffffff_____________________________I $\cdots$ |
[border-color=lightgray, rounded,tight,padding=1pt,1pt] f_8afffffff_____________________________I |
|  hybrid |  $[p;p^{4}[$ |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] 00_1000000000000000000000000000000000000I $\cdots$ | 64_16 |
|  [border-color=lightgray, rounded,tight,padding=1pt,1pt] ff_fffffffffffffffffffffffffffffffffffffI $\cdots$ |
|  [border-color=lightgray, rounded,tight,padding=1pt,1pt] .._87c2a630003eec7dffff561b0000004aeffffI |  |
|  |  ordered |  $[p^{4};p^{6}[$ |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] 1000000000000000000000000000000000000000I $\cdots$ | 64 |
|  |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] ffffffffffffffffffffffffffffffffffffffffI $\cdots$ |
|  |  [border-color=lightgray, rounded,tight,padding=1pt,1pt] g-8KOjCQREq2Vz8VTc30gLMd..vvX6000ov.....I |

  * LRI

Lexicographic Rank.

  * Z

Group center.

  * H

Maximal Abelian subgroup.

  * G

All elements.

  * –

Not applicable.

##  Appendix B Key-Digest Conversion

Map keys can be directly used as identifiers within certain constraints.
Elements in $\bm{\mathrm{H}}\setminus\bm{\mathrm{Z}}$ have only the two left
most digits of the identifier able to accommodate any letter. Therefore, keys
with more than 2 letters should have the rest of them converted to hexadecimal
and be padded with [border-color=lightgray, rounded,tight,padding=1pt,1pt] 0I
. Keys with a single letter are concatenated to [border-color=lightgray,
rounded,tight,padding=1pt,1pt] -I .

## References

  * [1] Abdulaziz Ali Alkandari, Imad Fakhri Al-Shaikhli, and Mohammad A Alahmad.  Cryptographic hash function: A high level view.  In 2013 International Conference on Informatics and Creative Multimedia, pages 128–134. IEEE, 2013.
  * [2] Jean-Philippe Aumasson, Samuel Neves, Zooko Wilcox-O’Hearn, and Christian Winnerlein.  Blake2: simpler, smaller, fast as md5.  In International Conference on Applied Cryptography and Network Security, pages 119–135. Springer, 2013.
  * [3] John Bamberg and Tim Penttila.  Completing segre’s proof of wedderburn’s little theorem.  Bulletin of the London Mathematical Society, 47(3):483–492, 2015\.
  * [4] Mihir Bellare, Oded Goldreich, and Shafi Goldwasser.  Incremental cryptography: The case of hashing and signing.  In Annual International Cryptology Conference, pages 216–233. Springer, 1994.
  * [5] Mihir Bellare and Tadayoshi Kohno.  Hash function balance and its impact on birthday attacks.  In International conference on the theory and applications of cryptographic techniques, pages 401–418. Springer, 2004.
  * [6] Tim Berners-Lee, Roy Fielding, and Larry Masinter.  Rfc2396: Uniform resource identifiers (uri): generic syntax, 1998.
  * [7] Tim Berners-Lee, Roy Fielding, Larry Masinter, et al.  Uniform resource identifiers (uri): Generic syntax, 1998.
  * [8] Anna Castelaz.  Commutativity degree of finite groups.  PhD thesis, Wake Forest University, 2010.
  * [9] Augustin-Louis Cauchy.  Mémoire sur les arrangements que l’on peut former avec des lettres données, et sur les permutations ou substitutionsa l’aide desquelles on passe d’un arrangementa un autre.  Exercises d’Analyse et de Mathématiques Physiques, 3:151–242, 1844.
  * [10] Scott Chacon and Ben Straub.  Pro git.  Springer Nature, 2014.
  * [11] Joel Cracraft.  Species concepts and speciation analysis.  In Current ornithology, pages 159–187. Springer, 1983.
  * [12] Benjamin Goldberg.  Detecting sharing of partial applications in functional programs.  In Conference on Functional Programming Languages and Computer Architecture, pages 408–425. Springer, 1987.
  * [13] Laurel L Haak, Martin Fenner, Laura Paglione, Ed Pentz, and Howard Ratner.  Orcid: a system to uniquely identify researchers.  Learned Publishing, 25(4):259–264, 2012.
  * [14] Jing Han, Ee Haihong, Guan Le, and Jian Du.  Survey on nosql database.  In 2011 6th international conference on pervasive computing and applications, pages 363–366. IEEE, 2011.
  * [15] Dominikus Herzberg and Tim Reichert.  Concatenative programming-an overlooked paradigm in functional programming.  In International Conference on Software and Data Technologies, volume 1, pages 257–262. SCITEPRESS, 2009.
  * [16] Jack O’Connor, Jean-Philippe Aumasson, Samuel Neves, and Zooko Wilcox-O’Hearn.  BLAKE3 one function, fast everywhere.  https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf, 2020\.  [Online; accessed 06-Jun-2021].
  * [17] Norman Paskin.  Digital object identifier (doi®) system.  Encyclopedia of library and information sciences, 3:1586–1592, 2010\.
  * [18] Jacques Patarin and Audrey Montreuil.  Benes and butterfly schemes revisited.  In International Conference on Information Security and Cryptology, pages 92–116. Springer, 2005.
  * [19] Davi Pereira-Santos and Gabriel Dalforno.  Garoupa.  https://doi.org/10.5281/zenodo.5501845, September 2021.
  * [20] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Shenker.  A scalable content-addressable network.  In Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, pages 161–172, 2001.
  * [21] Ronald Rivest and S Dusse.  The md5 message-digest algorithm, 1992.
  * [22] Ravi S Sandhu.  Role-based access control.  In Advances in computers, volume 46, pages 237–286. Elsevier, 1998\.
  * [23] International Telecommunication Union.  Object Identifiers (OID) and Registration Authorities Recommendations.  https://www.itu.int/ITU-T/studygroups/com17/oid.html, 2009.  [Online; accessed 01-April-2021].
  * [24] Wil Van Der Aalst.  Data science in action.  In Process mining, pages 3–23. Springer, 2016.
  * [25] Antonio Veralopez and JM Arregi.  Some algorithms for the calculation of conjugacy classes in the sylow p-subgroups of gl (n, q).  Journal of Algebra, 177(3):899–925, 1995.
  * [26] Xiaoyun Wang, Andrew C Yao, and Frances Yao.  Cryptanalysis on sha-1.  In Cryptographic Hash Workshop hosted by NIST, 2005.
  * [27] AJ Weir.  Sylow p-subgroups of the general linear group over finite fields of characteristic p.  Proceedings of the American Mathematical Society, 6(3):454–464, 1955.