11institutetext: Chair of Process and Data Science, RWTH Aachen University,
Aachen, Germany
11email<EMAIL_ADDRESS>22institutetext: Research Center for Information Systems Engineering (LIRIS),
KU Leuven 22email:
<EMAIL_ADDRESS>33institutetext: Heidelberger Druckmaschinen AG, Heidelberg, Germany
44institutetext: Department of Business Informatics and Operations Management,
Ghent University

# Discovering High-Quality Process Models Despite Data Scarcity

Jan Niklas Adams 11 Jari Peeperkorn 22 Tobias Brockhoff 11 Isabelle Terrier 33
Heiko Göhner 33 Merih Seran Uysal 11 Seppe vanden Broucke 4422 Jochen De
Weerdt 22 Wil M.P. van der Aalst 11

###### Abstract

Process discovery algorithms learn process models from executed activity
sequences, describing concurrency, causality, and conflict. Concurrent
activities require observing multiple permutations, increasing data
requirements, especially for processes with concurrent subprocesses such as
hierarchical, composite, or distributed processes. While process discovery
algorithms traditionally use sequences of activities as input, recently
introduced object-centric process discovery algorithms can use graphs of
activities as input, encoding partial orders between activities. As such, they
contain the concurrency information of many sequences in a single graph. In
this paper, we address the research question of reducing process discovery
data requirements when using object-centric event logs for process discovery.
We classify different real-life processes according to the control-flow
complexity within and between subprocesses and introduce an evaluation
framework to assess process discovery algorithm quality of traditional and
object-centric process discovery based on the sample size. We complement this
with a large-scale production process case study. Our results show reduced
data requirements, enabling the discovery of large, concurrent processes such
as manufacturing with little data, previously infeasible with traditional
process discovery. Our findings suggest that object-centric process mining
could revolutionize process discovery in various sectors, including
manufacturing and supply chains.

###### Keywords:

Process Mining Process Discovery Object-Centric Process Mining

##  1 Introduction

Throughout time, business endeavors have been supported by processes, ranging
from bookkeeping to production processes. With the advent of modern
information systems, data traces of process executions are recorded in the
underlying databases [13]. While businesses mostly have some idea of how their
processes look like, analyzing the recorded data allows them to uncover their
real execution. Algorithms transforming the data of process executions, i.e.,
event logs, into process models are called process discovery algorithms [1].

A plethora of process discovery algorithms have been proposed over the last
two decades [8]. Process discovery techniques assume the existence of an
extracted event log composed of a set of event sequences (cases) describing
different process executions. In general, these algorithms project each event
sequence to its activity sequence and aim to uncover the
sequentiality/causality, concurrency, or conflict between activities. While
causality and conflict can be uncovered using relatively few activity
sequences, concurrency needs to be confirmed using a large set of
observations. For example, four concurrent activities could manifest in 24
different sequences, and seven concurrent activities already in 5040 possible
sequences. The number of sequences grows factorial with the number of
concurrent activities. Therefore, larger numbers of concurrent activities
require more observations for process discovery. This becomes infeasible for
large numbers of concurrent activities or event logs with very few cases.

Figure 1: Categorization of different real-life processes based on inter- and
intra-object complexity.

Problems with highly concurrent behavior are especially present in processes
that are composed of multiple, concurrently running and lightly interacting
subprocesses. The amount of interaction between subprocesses is called the
inter-object complexity. High inter-object complexity indicates a tight
coupling between subprocesses, i.e., large amounts of shared control flow. Low
inter-object complexity indicates concurrently running subprocesses. We depict
an overview of typical processes and their inter-object complexity in Fig. 1.
As inter-object complexity only captures control-flow complexity between
subprocesses, we complement this dimension with intra-object complexity,
capturing the control-flow complexity within subprocesses. We collect
descriptions of typical real-life processes from the literature and depict
their mapping onto these two dimensions in Fig. 1. Specifically, we show
processes considered in traditional process mining (workflows like ticketing
processes and business process case management [5, 28]), discrete
manufacturing systems [17] (job shop/mass customization [12], (flexible)
assembly lines [17]), and composite workflows (business process like P2P/O2C
[30], end-to-end order processing [27]), and supply chains [21]. Additionally,
we depict where a traditional, completely linear process would be positioned.

While traditional event logs record cases as sequences of events, Object-
Centric Event Logs (OCELs) [2] encode cases as graphs of events [7],
preserving partial orders between events. By extracting the event data of
compound processes as OCELs instead of traditional event logs, the concurrency
between the subprocesses can be preserved using these graph-based process
executions. Object-centric process discovery was recently introduced [4],
using an OCEL as input and discovering a model composed of multiple
interacting subprocesses. This enables process owners to discover a process
directly from the graph-based process executions, rather than forcing them
into the sequential structure needed for traditional process discovery and
removing concurrency information.

In this paper, we address the following research question: How do data
requirements reduce when using object-centric process discovery instead of
traditional process discovery? Specifically, we want to break down the effect
of employing object-centric discovery for different groups of processes with
respect to their control-flow complexity between and within subprocesses,
mapping the reduction in data requirements back to real-life processes.

We tackle these research questions through two main contributions: First, we
formally define inter- and intra-object complexity and an evaluation framework
that can exactly assess the discovered model quality based on the sample size
of an event log. We instantiate this evaluation framework with 45.000 model
and sample size combinations and compare the quality of the discovered model
between traditional discovery and object-centric discovery. We map the results
back to the dimension of inter- and inter-object complexity and assess which
processes have the highest data requirement reduction when using object-
centric process discovery. Second, we complement this experimental evaluation
with a large-scale case study. Since the experimental evaluation is very
computation heavy, it is only applicable to smaller models. Our case study
shows the successful application of object-centric process discovery on a
large real-life manufacturing process with hundreds of activities. It also
shows that traditional process discovery fails to deliver the same quality.

The remainder of this paper is structured as follows. We introduce the related
work on process discovery and object-centric process mining in Sec. 2. The
preliminaries on traditional and OCELs and discovery are presented in Sec. 3.
We propose an experimental framework comparing discovery on object-centric and
flattened event data in Sec. 4. We discuss these results in Sec. 5. A case
study for the advantages of object-centric discovery is presented in Sec. 6.
We conclude this paper in Sec. 7.

##  2 Related Work

Object-centric process mining addresses the problem of distinguishing multiple
objects involved in a process. These objects can be used to identify
subprocesses. In the past, this problem has extensively been studied from the
modeling side. Different process modeling languages/notations to capture
object-centric processes have been proposed, such as artifact-centric process
models [11], Object-Centric Behavioral Constraints (OCBC) [3], proclets [15],
DB-Nets [23], COA-Nets [16], and t-PNIDs [29]. Some of these modeling
techniques have been accompanied by a data format that is able to capture
event data for processes of this kind. Artifact-centric event logs [24, 22],
and eXtensible Object-Centric event logs XOC [20] have been proposed.
Furthermore, Esser and Fahland have recently proposed a general-purpose graph
database to store object-centric event data [14]. Object-centric process
mining tackles the problem of object-centricity with the modeling language of
object-centric Petri nets [4] and the accompanying data format of OCELs [2].
Both of these approaches have been developed to improve the complexity and
scalability issues of existing modeling and data storage formats.

The core motivation of process discovery is the uncovering of as-is processes
from real-life data. As such, process-discovery techniques aim to connect
event data with process models. For the case of object-centric process mining,
discovery techniques have been proposed for the modeling languages where data
storage formats exist, namely artifact-centric discovery [24] and OCBC
discovery from XOC [19]. Van der Aalst and Berti have introduced a general
approach for discovering object-centric Petri nets from object-centric event
data [4]. Subsequently, these process models are utilized in other data-driven
process mining tasks, such as conformance checking [6] or enhancement [25].
This approach applies a traditional process discovery to each object type and
merges the resulting models at interaction points. Any traditional process
discovery algorithm can be employed in object-centric discovery.

Traditional process discovery describes the problem of mapping a set of
activity sequences to a process model [1]. Many different techniques have been
proposed [8], where the Split Miner [9] and the Inductive Miner [18] remain
among the most popular algorithms. In our paper, we use the inductive miner
due to its guarantee of sound workflow nets for every individual object type.
This paper provides a quantitative and qualitative study as to how much
process discovery results can be improved by individually discovering and
merging process models for each object type rather than discovering one model
on the flattened event data of all object types.

##  3 Traditional and Object-Centric Process Discovery

We introduce the foundations of object-centric and traditional event data and
process discovery in this section. We link OCELs to traditional event logs and
define the flattening of a traditional event log. Analogously, we introduce
object-centric Petri nets and their relationship to traditional Petri nets.

###  3.1 Linking Object-Centric and Traditional Event Data

First, we introduce some notations used throughout this paper. $\mathcal{E}$
is the universe of event identifiers, $\mathcal{OT}$ is the universe of object
types, and $\mathcal{O}$ is the universe of objects. Each object is associated
with exactly one object type through
$\pi_{\mathit{type}}:\mathcal{O}\rightarrow\mathcal{OT}$. $\mathcal{T}$
denotes the universe of event timestamps and $\mathcal{A}$ the universe of
event activities. We denote the powerset of a set $X$, the set of all subsets,
with $\mathcal{P}(X)$. A sequence of length $n\in\mathbb{N}$ orders elements
of a set $X$ and is denoted with $\sigma:\\{1,\ldots,n\\}\rightarrow X$ and
$\sigma=\langle x_{1},\ldots,x_{n}\rangle$. The set of directly follows
relationships in a sequence is denoted by $\mathit{df}(\langle
x_{1},\ldots,x_{n}\rangle)=\\{(x_{i},x_{i}+1)\mid i\in\\{1,\ldots,n-1\\}\\}$.

######  Definition 1 (Object-Centric Event Log)

An object-centric event log is a tuple $L=(E,\allowbreak
O\allowbreak,OT,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$
consisting of

  * $\bullet$

events $E\subseteq\mathcal{E}$, objects $O\subseteq\mathcal{O}$, object types
$OT=\\{\pi_{\mathit{type}}(o)\mid o\in O\\}$,

  * $\bullet$

activities $\pi_{\mathit{act}}:E\rightarrow\mathcal{A}$, timestamps
$\pi_{\mathit{time}}:E\rightarrow\mathcal{T}$, and

  * $\bullet$

ordering $\pi_{\mathit{trace}}:O\rightarrow E^{*}$ mapping each object to a
sequence of events such that $\forall_{o\in
O}\;\pi_{\mathit{trace}}(o)=\langle
e_{1},\ldots,e_{n}\rangle\wedge\forall_{i\in\\{1,\ldots,n-1\\}}\;\pi_{\mathit{time}}(e_{i})\leq\pi_{\mathit{time}}(e_{i+1})$

Each event is linked to objects $\pi_{\mathit{obj}}(e)=\\{o\in O\mid
e\in\pi_{\mathit{trace}}(o)\\}$.

Figure 2: An object-centric event log (a) and its flattened counterpart (b).

An example of an OCEL is depicted in Fig. 2. Each row is an event associated
with objects of different types, an activity, and a timestamp. Each object is
associated with a sequence of events, e.g.,
$\pi_{\mathit{trace}}(\mathit{Tire2})=\langle e_{2},e_{7},e_{10}\rangle$.

A traditional event log is a special case of an OCEL where objects are all of
the same type and an event is associated with exactly one object.

######  Definition 2 (Traditional Event Log)

An object-centric event log $L{=}(E,\allowbreak O,\allowbreak
OT,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$ is a
traditional event log iff $|OT|{=}1\wedge\forall_{e\in
E}|\pi_{\mathit{obj}}(e)|{=}1$.

An event log consists of different executions of the same process. Each
execution contains multiple events. In traditional process mining, a process
execution is called a case and is a sequence of events for one object. We
generalize this notion such that a process execution is a graph of events for
multiple, connected objects [7]. The graph describes a partial order of events
induced by the precedence constraints of each $\pi_{\mathit{trace}}$ of the
involved objects.

######  Definition 3 (Process Executions [7])

Let $L=(E,\allowbreak
O\allowbreak,OT,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$
be an object-centric event log. The object graph of object co-appearances is
defined by $\mathit{OG}_{L}=(O,I)$ with $I=\\{\\{o,o^{\prime}\\}\mid o\neq
o^{\prime}\wedge\exists_{e\in
E}\;\\{o,o^{\prime}\\}\subseteq\pi_{\mathit{obj}}(e)\\}$. The set of
interdependent object sets are the connected components of the object graph
$\mathit{cc}(L)=\\{O^{\prime}\subseteq O\mid O^{\prime}\text{ form a connected
component in }\mathit{OG}_{L}\\}$. One set of dependent objects
$X\in\mathit{cc}(L)$ spans a process execution. A process execution is a graph
$p_{X}=(E_{X},D_{X})$ of nodes $E_{X}=\\{e\in E\mid\pi_{\mathit{obj}}(e)\cap
X\neq\emptyset\\}$ and edges $D_{X}=\\{(e,e^{\prime})\in E_{X}\times
E_{X}\mid\exists_{o\in
X}\;(e,e^{\prime})\in\mathit{df}(\pi_{\mathit{trace}}(o))\\}$. The set of all
process executions of an event log is defined by $\mathit{px}(L)=\\{p_{X}\mid
X\in\mathit{cc}(L)\\}$.

Figure 3: Top: A graph-based process execution from the object-centric event
log of Fig. 2 a) and the sequential process execution from the flattened,
traditional event log of Fig. 2 b). Bottom: The process models discovered from
both of these process executions.

The upper left part of Fig. 3 contains an example of the object-centric
process execution contained in Fig. 2. The process execution shows the
production of different parts that run concurrently and are assembled in a
bottom-up way.

An OCEL can be transformed into the traditional event log format by flattening
[2] it. This involves the choice of a case notion and the sequentializing of
events for each object of that case notion. The case notion can be chosen
freely, typically either a single object type is chosen or a set of connected
objects. Flattening transforms a graph-based structure of process executions
into a less expressive sequential structure of process execution, therefore,
some information loss will never be preventable. We choose to flatten with all
connected objects, i.e., flattening a process execution from a graph into a
sequence. By doing this, we prevent events from disappearing or being
duplicated as it would be the case if one would flatten on a single object
type [2].

######  Definition 4 (Flattening)

Let $L=(E,\allowbreak
O\allowbreak,OT,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$
be an object-centric event log. $L^{\mathit{flat}}=(E,\allowbreak
O^{\prime}\allowbreak,OT^{\prime},\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}}^{\prime})$
is the flattened event log with three modified elements:

  * $\bullet$

a new, single object type $OT^{\prime}=\\{ot\\}$ for an
$ot\in\mathcal{OT}\wedge ot\notin OT$.

  * $\bullet$

new object identifiers
$O^{\prime}\subseteq\\{o\in\mathcal{O}\mid\pi_{\mathit{type}}(o)\in
OT^{\prime}\\}$ associated with the objects of the process executions
$\mathit{cc}(L)$ through a bijection
$\pi_{\mathit{flat}}:O^{\prime}\rightarrow\mathit{cc}(L)$.

  * $\bullet$

event sequences for the new objects
$\pi_{\mathit{trace}}^{\prime}(o^{\prime})=\langle e_{1},\ldots,e_{n}\rangle$
with
$\\{e_{1},\ldots,e_{n}\\}=\bigcup_{o\in\pi_{\mathit{flat}}(o^{\prime})}\pi_{\mathit{trace}}(o)$
and $\pi_{\mathit{time}}(e_{1})\leq\cdots\leq\pi_{\mathit{time}}(e_{n})$ for
$o^{\prime}\in O^{\prime}$.

We show the flattened event log in Fig. 2 b). The corresponding process
execution, a sequence, is depicted in the upper right of Fig. 3. The
concurrency information from the graph-based process execution is lost when
flattening to a sequence.

###  3.2 Object-Centric Process Models

A process can be represented as a process model, typically a Petri net.
Object-centric processes are represented using an object-centric Petri net
[4], a Petri net with places of different types and variable arcs which are
able to consume more than one token.

######  Definition 5 (Object-Centric Petri Net)

An object-centric Petri net is a tuple
$\mathit{OCPN}=(P,\pi_{\mathit{pt}},F_{\mathit{var}})$ of

  * $\bullet$

a Petri net $P=(T,P,F,l)$ consisting of transitions $T$, places $P$, arcs
$F\subseteq(T\times P)\cup(P\times T)$, and a labeling function
$l:T\nrightarrow\mathcal{A}$,

  * $\bullet$

a type function mapping each place to an object type
$\pi_{\mathit{pt}}:P\rightarrow\mathcal{OT}$, and

  * $\bullet$

a set of variable arcs $F_{\mathit{var}}\subseteq F$.

We define the following notations for object-centric Petri nets:

  * $\bullet$

the preset of a transition ${\bullet}t{=}\\{p{\in}P\mid(p,t){\in}F\\}$ for
$t\in T$.

  * $\bullet$

the postset of a transition $t{\bullet}{=}\\{p{\in}P\mid(t,p){\in}F\\}$ for
$t\in T$.

  * $\bullet$

$tpl(t){=}\\{\pi_{pt}(p)\mid p{\in}{\bullet}t{\cup}t{\bullet}\\}$ are the
object types associated to transition $t\in T$.

  * $\bullet$

$tpl_{nv}(t){=}\\{\pi_{pt}(p){\mid}p{\in}P\wedge\\{(p,t),(t,p)\\}{\cap}(F{\setminus}F_{\textit{var}}){\neq}\emptyset\\}$
are the object types with non-variable arcs associated to transition $t\in T$.

An example of an object-centric Petri net is depicted in the lower left of
Fig. 3. Places of different types are depicted with different colors, variable
arcs are depicted with double lines. Please note that we dropped the output
places of an object type’s last transition for presentation purposes.

Analogously to object-centric and traditional event logs, a traditional Petri
net is a special case of an object-centric Petri net where all places have the
same type and no variable arcs exist. The bottom right of Fig. 3 depicts a
traditional Petri net.

######  Definition 6 (Traditional Petri Net)

An object-centric Petri net
$\mathit{OCPN}=(P,\pi_{\mathit{pt}},F_{\mathit{var}})$ is a traditional Petri
net iff $|\mathit{range}(\pi_{\mathit{pt}})|=1\wedge
F_{\mathit{var}}=\emptyset$.

We describe the state of an object-centric Petri net with a marking.

######  Definition 7 (Marking)

Let $\mathit{OCPN}=((T,P,F,l),\pi_{\mathit{pt}},F_{\mathit{var}})$ be an
object-centric Petri net. A token associates an object with a place. The set
of tokens is define by $Q_{\mathit{OCPN}}=\\{(p,o)\in
P\times\mathcal{O}\mid\pi_{\mathit{pt}}(p)=\pi_{\mathit{type}}(o)\\}$. A
marking is a multiset of tokens $M\in\mathcal{B}(Q_{\mathit{OCPN}})$.

Given a marking, a transition can be enabled. If it is enabled, it can be
executed. The execution of a transition is bound to objects. These are
consumed in the input places and produced in the output places.

######  Definition 8 (Binding Execution)

Let $\mathit{OCPN}=((T,P,F,l),\pi_{\mathit{pt}},F_{\mathit{var}})$ be an
object-centric Petri net. $B_{\mathit{OCPN}}{=}\\{(t,b)\in
T{\times}(\mathcal{OT}{\nrightarrow}\mathcal{P}(\mathcal{O}))\mid
dom(b){=}tpl(t)\wedge\forall_{ot{\in}tpl_{nv}(t)}|b(ot)|{=}1\\}$ defines the
set of all possible bindings. The consumed tokens of a binding
$(t,b){\in}B_{\mathit{OCPN}}$ are defined by
$cons(t,b){=}[(p,o){\in}Q_{\mathit{OCPN}}\mid p{\in}{\bullet}t\wedge
o{\in}b(\pi_{\mathit{pt}}(p))]$ and the produced tokens are defined by
$prod(t,b){=}[(p,o){\in}Q_{\mathit{OCPN}}\mid p{\in}t{\bullet}\wedge
o{\in}b(\pi_{\mathit{pt}}(p))]$. A binding $(t,b){\in}B$ in marking
$M\in\mathcal{B}(Q_{\mathit{OCPN}})$ is enabled if $cons(t,b)\leq M$.
Executing an enabled binding in $M$ leads to marking
$M^{\prime}{=}M-cons(t,b)+prod(t,b)$. Executing an enabled binding $(t,b)\in
B_{\mathit{OCPN}}$ in marking $M$ is denoted with
$M{\xrightarrow{(t,b)}}M^{\prime}$. Multiple subsequent enabled bindings can
be encoded as a binding sequence
$\sigma{=}\langle(t_{1},b_{1}),\ldots,(t_{n},b_{n})\rangle{\in}B_{\mathit{OCPN}}^{*}$.
A sequence that starts in marking $M_{0}$ and results in marking $M_{n}$ is
encoded as $M_{0}{\xrightarrow[]{\sigma}}M_{n}$.

To define a process model that allows certain behavior, we need start and end
points. These are sets of marking for an object-centric Petri net.

######  Definition 9 (Accepting Object-Centric Petri Net)

Let $\mathit{OCPN}=((T,P,\allowbreak F,\allowbreak
l),\pi_{\mathit{pt}},F_{\mathit{var}})$ be an object-centric Petri net and let
$M_{\mathit{init}},M_{\mathit{final}}\subseteq\mathcal{B}(Q_{\mathit{OCPN}})$
be initial and final markings of the object-centric Petri net.
$\mathit{OCPN}_{A}=(\mathit{OCPN},\allowbreak
M_{\mathit{init}},M_{\mathit{final}})$ is an accepting object-centric Petri
net.

All binding sequences that lead from an initial marking to a final marking
define the possible end-to-end behavior of the accepting object-centric Petri
net. We define the language of the accepting object-centric Petri net as the
set of all possible visible loop-free label sequences in the end-to-end
behavior of the object-centric Petri net. In this way, we exclude binding
sequences with loops that would render the language of the model infinite.

######  Definition 10 (Petri Net Language)

Let $\mathit{OCPN}_{A}=(\mathit{OCPN},M_{\mathit{init}},M_{\mathit{final}})$
be an accepting object-centric Petri net. All loop-free valid binding
sequences of the object-centric Petri net are given by
$S(\mathit{OCPN}_{A})=\\{\langle(t_{1},b_{1}),\ldots,(t_{n},b_{n})\rangle\in
B_{\mathit{OCPN}}^{*}\mid\exists_{M_{i}\in
M_{\mathit{init}}}\;\exists_{M_{f}\in
M_{\mathit{final}}}\;M_{i}{\xrightarrow{(t_{1},b_{1})}}\cdots{\xrightarrow{(t_{n},b_{n})}}M_{f}\wedge\forall_{i,j\in\\{1,\ldots,n\\}\wedge
i\neq j}M_{i}\neq M_{j}\\}$. The language of the object-centric Petri net is
the set of visible transition firing sequences $\Sigma(OCPN_{A})=\\{\langle
l(t_{1}),\ldots,l(t_{n})\rangle\mid\langle(t_{1},b_{1}),\ldots,(t_{n},b_{n})\rangle\in
S(\mathit{OCPN}_{A})\\}$

An accepting object-centric Petri net can be discovered from an OCEL using the
general approach introduced by van der Aalst and Berti [4]. A Petri net is
discovered for each object type. Given the cardinalities of different objects,
the individual Petri nets are merged into one object-centric Petri net,
connecting the individual nets at interconnecting transitions (transitions
including multiple object types). Place types and variable arcs are assigned
according to the types and cardinalities stemming from the individual subnets.

######  Definition 11 (Process Discovery)

Let $L=(E,\allowbreak
OT\allowbreak,O,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$
be an object-centric event log. A process discovery algorithm
$d(L)=\mathit{OCPN}_{A}$ returns an accepting object-centric Petri net for the
object-centric event log.

This general approach discovers a traditional Petri net if a traditional event
log is the input. The object-centric Petri nets in Fig. 3 are discovered from
the OCEL and the flattened event log of Fig. 2.

###  3.3 Inter- and Intra-Object Complexity

In this section, we formally define the inter- and intra-object complexity
which were already informally introduced in the introduction. We later use
these dimensions in our experimental framework to differentiate which process
characteristics and, therefore, which real-life processes benefit most from
employing object-centric discovery.

######  Definition 12 (Inter-Object Complexity)

Let $\mathit{OCPN}_{A}=(((T,P,F,l),\pi_{\mathit{pt}},\allowbreak
F_{\mathit{var}}),M_{\mathit{init}},\allowbreak M_{\mathit{final}})$ be an
accepting object-centric Petri net. We define the following model attributes:

  * $\bullet$

$\mathit{numt}(\mathit{OCPN}_{A})=|\\{t\in T\mid t\in\mathit{dom}(l)\\}|$ the
number of non-silent transitions,

  * $\bullet$

$\mathit{numot}(\mathit{OCPN}_{A})=|\mathit{range}(\pi_{\mathit{pt}})|$ the
number of object types, and

  * $\bullet$

$\mathit{inter}(\mathit{OCPN}_{A})=\frac{1}{\mathit{max}(1,|OT|-1)}\frac{\sum_{t\in
T}|\\{\pi_{\mathit{pt}}(p)\mid p\in\bullet t\\}|-1}{|T|}$ is the inter-object
complexity of the model.

The inter-object complexity is defined as the amount of shared transitions
between objects. The more transitions are shared between objects, the more the
object’s control flows are interwoven with each other. Based on the
definition, we make two observations.

###### Observation 3.1

High inter-object complexities point to many shared transitions. In the
extreme case, all objects share all transitions. This would make objects
redundant, as they all describe the same control flow. Only one object is
necessary to encode the control flow, i.e., a process with an inter-object
complexity of 1 is equivalent to a traditional process described by a Petri
net.

###### Observation 3.2

A traditional process has an inter-object complexity of 1, as the single
object of the process is involved in all transitions.

The inter-object complexity only describes the complexity of control flow
between objects. To fully capture the complexity of the control flow, we
further define the intra-object-complexity, capturing the control flow within
objects.

######  Definition 13 (Intra-Object Complexity)

Let $\mathit{OCPN}_{A}=(((T,P,F,l),\allowbreak\pi_{\mathit{pt}},\allowbreak
F_{\mathit{var}}),\allowbreak M_{\mathit{init}},\allowbreak
M_{\mathit{final}})$ be an accepting object-centric Petri net. For an object
type $\mathit{ot}\in\mathit{range}(\pi_{\mathit{pt}})$, we retrieve the subnet
$\mathit{OCPN}_{A,\mathit{ot}}=(P_{\mathit{ot}},T_{\mathit{ot}},F_{\mathit{ot}},l_{\mathit{ot}})$
with

  * $\bullet$

$P_{\mathit{ot}}=\\{p\in P\mid\pi_{\mathit{pt}}(p)=\mathit{ot}\\}$,

  * $\bullet$

$T_{\mathit{ot}}=\\{t\in T\mid\exists_{p\in\bullet t\cup
t\bullet}\;\pi_{\mathit{pt}}(p)=\mathit{ot}\\}$,

  * $\bullet$

$F_{\mathit{ot}}=\\{(s,t)\in F\mid(s\in P_{\mathit{ot}}\wedge t\in
T_{\mathit{ot}})\vee(s\in T_{\mathit{ot}}\wedge t\in P_{\mathit{ot}})\\}$, and

  * $\bullet$

$l_{\mathit{ot}}(t)=l(t)$ for $t\in T_{\mathit{ot}}$.

We define the intra-object complexity for an individual type as
$\mathit{tioc}(\mathit{OCPN}_{A,\mathit{ot}})=\frac{|\Sigma(\mathit{OCPN}_{A,\mathit{ot}})|}{\mathit{numt}(\mathit{OCPN}_{A,\mathit{ot}})!}$.
The intra-object complexity of the model is defined as the average intra-
object complexity of all object types
$\mathit{intra}(\mathit{OCPN}_{A})=\frac{1}{\mathit{numot}(\mathit{OCPN}_{A})}\cdot\sum_{\mathit{ot}\in\mathit{range}(\pi_{\mathit{pt}})}\mathit{tioc}(\mathit{OCPN}_{A,\mathit{ot}})$.

The intra-object complexity quantifies the objects’ average deviation from a
completely linear control flow. An intra-object complexity of 0 means that all
objects follow a strictly linear control flow, while an intra-object
complexity of 1 means that all objects would have a completely concurrent
control flow.

##  4 Experimental Framework

Figure 4: Experimental framework. We generate many different system models
with varying characteristics.

This section introduces the experimental setup to compare process discovery on
object-centric and flattened event data which is depicted in Fig. 4. The
experimental framework consists of three steps: Model generation, event log
sampling, and discovery quality assessment.

#### Model Generation

Figure 5: Distribution of generated model characteristics and example models
for different combinations.

We use a process model called the system model resembling a ground truth
process. To cover a wide range of combinations of inter- and intra-object
complexity, we generate a large set of different models. We depict the
distribution of our generated system model along with some exemplary models in
Fig. 5. In total, we have randomly generated 44570 system models with 6-8
visible activities (additionally, they can have silent transitions to model
AND constructs) and two object types. These models do not have loops, as this
would conflict with the next part of the framework, the event log sampling. We
address this limitation in the threats to validity section at the end of Sec.
5. The model sizes are limited to maximum 8 visible transitions, as larger
models would produce so many possible traces that an exact computation of the
model language, as described in the next section, would become infeasible.
However, we complement the experiments with a case study on a large production
process, showing the applicability and improvements of discovery also for very
large models.

#### Event Log Sampling

We extract an event log by sampling from the language of the system model. To
do so, we compute the language of the system model, i.e., all possible process
executions. We sample a subset of this language to simulate extracting an
event log that only contains a part of the possible behavior.

######  Definition 14 (Event Log Extraction)

Let $\mathit{OCPN}_{A}{=}(\mathit{OCPN},M_{\mathit{init}},\allowbreak
M_{\mathit{final}})$ be an accepting object-centric Petri net and $s\in[0,1]$
be an extraction sampling rate.
$\mathit{sample}(\mathit{OCPN}_{A},s)\subseteq\Sigma(OCPN_{A})$ samples a
subset of the Petri net language corresponding to the sampling rate $s$. The
language subset is mapped to an OCEL by
$\mathit{gen}(\mathit{sample}(\mathit{OCPN}_{A},s),\mathit{OCPN}_{A})=(E,\allowbreak
O\allowbreak,OT,\pi_{\mathit{act}},\pi_{\mathit{time}},\pi_{\mathit{trace}})$.

The presented approach allows us to quantify a sampling rate, i.e., how much
of the possible model behavior is contained in the event log. Since we
computed the full system model language, we can also compare the language of a
discovered model to the language of a system model, quantifying how well the
discovered model corresponds to the ground-truth system model given the
sampling rate. This is explained in the next paragraph

#### Quantifying Discovered Model Quality

We compare the quality of discovered process models from the object-centric
and flattened event logs. Starting from the OCEL, we discover a model before
and after flattening the event log using Inductive Miner [18]. The model
quality is defined as the recall/precision of the discovered model language
with respect to the language of the system model. When the model is discovered
from a sampled event log of the system model, the fitness defined here also
measures the generalization capabilities of the discovery technique [26].

######  Definition 15 (Model Quality)

Let $\mathit{OCPN}_{A}=(\mathit{OCPN},M_{\mathit{init}},M_{\mathit{final}})$
be a system model and $s\in[0,1]$ be a sampling rate. The sampled OCEL is
given by
$L=d(\mathit{gen}(\mathit{sample}(\allowbreak\mathit{OCPN}_{A},s),\mathit{OCPN}_{A})$.
The discovered model on the object-centric event log is denoted with
$\mathit{OCPN}^{d}_{A}=d(L)$ and the discovered model on the flattened event
log is denoted with
$\mathit{OCPN}^{\mathit{flat},d}_{A}=d(L^{\mathit{flat}})$. For any of the two
discovered models
$\mathit{PN}\in\\{\mathit{OCPN}^{d},\mathit{OCPN}^{\mathit{flat},d}\\}$, we
define the fitness
$\mathit{fit}(\mathit{OCPN}_{A},\allowbreak\mathit{PN})=\allowbreak\frac{|\Sigma(\mathit{OCPN}_{A})\cap\Sigma(\mathit{PN})|}{|\Sigma_{d}(\mathit{OCPN}_{A})|}$
and the precision
$\mathit{prec}(\mathit{OCPN}_{A},\allowbreak\mathit{PN})=\frac{|\Sigma(\mathit{OCPN}_{A})\cap\Sigma(\mathit{PN})|}{|\Sigma(\mathit{PN})|}$.

Using this setup, we retrieve the discovered model quality for traditional and
object-centric process discovery for different combinations of inter-object
complexity, intra-object complexity, and sample sizes.

##  5 Experimental Results

We present our experimental results in this section. The implementation is
publicly available111https://github.com/jn-adams/ObjectCentricDiscovery. We
present the dependency between discovered model quality and event log sample
size for traditional and object-centric discovery on system models with
varying inter- and intra-object complexity, as described in Sec. 4. The
results are depicted in Fig. 6 (fitness) and Fig. 7 (precision).

Figure 6: Discovered model fitness depending on the sample size of the event
log for the four different quadrants of our process taxonomy.

Figure 7: Discovered model precision depending on the sample size of the event
log for the four different quadrants of our process taxonomy.

We split the models according to their characteristics using low/high inter-
and intra-object complexity. The decision for low and high values are made
according to Fig. 5, i.e., an inter-object complexity of more than 0.2 is
considered high and an intra-object complexity of less than 0.15 is considered
to be low. We choose both values for the following reasons: First, high inter-
object complexity indicates high redundancies between object types, i.e., the
system model is behaviorally very close to a traditional Petri net. By
choosing a low threshold we single out system models that are significantly
different from traditional process models. Second, high intra-object
complexity models indicate a lack of structure in the process, i.e., no order
is enforced. By choosing a low threshold, we can single out system models that
show high degrees of sequentiality in one bin and less structured models in
the other bin.

The highest quality differences can be observed when the system model exhibits
low levels of inter-object complexity, especially when the intra-object
complexity is also low, i.e., each object has a relatively sequential path and
only some interaction points with other objects. In this case, the average
fitness of the discovered process model for extracted OCELs with a low sample
rate is already 0.9. The fitness of the discovered model from the flattened
event log is very low, starting at almost 0. Mapping this back to the initial
taxonomy depicted in Fig. 1, object-centric discovery can significantly reduce
the data required for manufacturing processes, supply chains, and composite
workflows. Especially for processes with relatively sequential subprocesses,
like assembly lines, object-centric discovery allows for discovery with much
less data compared to traditional discovery. This means, that discovery for
larger models, which was prohibitive due to the data requirements in
traditional discovery, is now enabled using object-centric discovery. We will
also see this in the case study in Sec. 6. Models with high inter-object
complexity cannot benefit that much from switching to object-centric
discovery. Since high inter-object complexity points to redundant control
flows and is, in the extreme case, equivalent to traditional process models,
these results are not surprising. It is notable, that – within this evaluation
– object-centric discovery does not worsen results.

When considering the precision of discovered models, the quality differences
are larger for models with high intra-object complexity, although precision
levels for low intra-object complexity are, generally, higher. This can be
explained by low levels of intra-object complexity allowing more concurrent
behavior, such that the discovery of flower-like models will be more precise
than for more restrictive system models. In general, we observe that the high
amounts of sequences produced by concurrent behavior push the discovery
algorithm to discover flower models for the flattened event logs,
significantly reducing the precision.

###  5.1 Threats to Validity

As our experimental framework computes the exact languages of the models, it
is computationally quite demanding, leading us to restrict the system model
generation in two major ways: without loops and only limited to eight visible
transitions. These are also the main limitations of this experimental
framework: First, our results cannot be generalized to process models
containing many loops. Second, our generated models only cover relatively
small models of 8 visible transitions. While the results are already very
clear and the difference should only increase for larger models, our
experiments cannot prove this claim. Therefore, we complement the experiments
with a case study performing object-centric discovery on a large-scale
production process and comparing the results to traditional process discovery.
We aim to mitigate the limitations of our experimental framework using this
case study, as it shows that object-centric discovery is feasible for large
processes and provides better results than traditional discovery.

##  6 Case Study

Figure 8: Discovered process model of a production process using an OCEL.
Different components follow their individual paths and are assembled into a
merged component.

We use object-centric event data from a production process in the German
manufacturing company Heidelberger Druckmaschinen AG [10]. The confidential
original event log contains hundreds of process executions with more than 800
activities. Object-centric discovery can be applied to the original event log,
however, the resulting visualization is too large for human comprehension.
Therefore, we limit our analysis to a subprocess of 105 activities. Our sublog
contains 13 process executions. We, first, apply object-centric process
discovery and, second, flatten the event log and apply traditional process
discovery. Even though we do not know the true ground truth process to provide
an exact sample rate, it would be close to 0 given the large number of
concurrent activities and the low number of process executions. The results
are depicted in Fig. 8 and Fig. 9.

The structure of the process can be rediscovered using object-centric
discovery: Individual concurrent object paths are visible, ending up in one
assembly activity that combines individual components into an output
component. This output component follows its individual path afterward. The
low number of process executions is not an issue when using object-centric
discovery, it can still rediscover the concurrency between objects. This is
not the case for process discovery on flattened event data. The flattened
process discovery algorithm shows a flower model, i.e., the structure of the
process is completely lost. Furthermore, it is generally infeasible to expect
that a flattened event log would contain enough process executions such that
concurrency could completely be rediscovered: 100 partly concurrent activities
can generate a large number of possible activity sequences, such that the data
requirements of traditional process discovery would be beyond any feasible
amount of produced products, i.e., the available sample size.

Figure 9: Discovered process model of a production process using the flattened
object-centric event log. The process is mostly a flower model and the
screenshot only shows part of the width of this flower model.

##  7 Conclusion

In this paper, we investigated the data requirement reduction that object-
centric process discovery yields over traditional discovery. We categorize
different real-life processes according to control-flow complexity across and
within subprocesses, and formally define these dimensions. We define an
experimental framework that generates models across these dimensions and
assess the reduction in data requirements when using object-centric discovery
over traditional discovery. We can show that the data requirements are
drastically reduced, especially for low inter-object complexity processes
models like production processes or supply chains. To address limitations of
the experimental framework w.r.t. the size of generated models we complement
our evaluation with a large-scale production process case study. We show, that
object-centric discovery captures the production process much better than
traditional process discovery. In this case, the data requirements of
traditional discovery would even exceed the number of produced items,
rendering traditional process discovery infeasible. Our results have
significant implications for the application of process discovery to large-
scale processes: Areas once infeasible for discovery due to large data
requirements are now accessible using object-centric process mining. This will
foster the adaption of process discovery in the future.

##  8 Acknowledgments

We thank the Alexander von Humboldt (AvH) Stiftung for supporting our
research. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany’s Excellence Strategy—EXC-2023 Internet of
Production—390621612.

## References

  * [1] van der Aalst, W.M.P.: Process Mining - Data Science in Action, Second Edition. Springer (2016). https://doi.org/10.1007/978-3-662-49851-4
  * [2] van der Aalst, W.M.P.: Object-centric process mining: Dealing with divergence and convergence in event data. In: SEFM. pp. 3–25. Springer (2019). https://doi.org/10.1007/978-3-030-30446-1_1
  * [3] van der Aalst, W.M.P., Artale, A., Montali, M., Tritini, S.: Object-centric behavioral constraints: Integrating data and declarative process modelling. In: Description Logics. CEUR-WS.org (2017)
  * [4] van der Aalst, W.M.P., Berti, A.: Discovering object-centric Petri nets. Fundam. Informaticae 175(1-4), 1–40 (2020). https://doi.org/10.3233/FI-2020-1946
  * [5] van der Aalst, W.M.P., van Dongen, B.F., Herbst, J., Maruster, L., Schimm, G., Weijters, A.J.M.M.: Workflow mining: A survey of issues and approaches. Data Knowl. Eng. 47(2), 237–267 (2003). https://doi.org/10.1016/S0169-023X(03)00066-1
  * [6] Adams, J.N., van der Aalst, W.M.P.: Precision and fitness in object-centric process mining. In: ICPM. pp. 128–135. IEEE (2021). https://doi.org/10.1109/ICPM53251.2021.9576886
  * [7] Adams, J.N., Schuster, D., Schmitz, S., Schuh, G., van der Aalst, W.M.P.: Defining cases and variants for object-centric event data. In: (ICPM). pp. 128–135 (2022). https://doi.org/10.1109/ICPM57379.2022.9980730
  * [8] Augusto, A., Conforti, R., Dumas, M., Rosa, M.L., Maggi, F.M., Marrella, A., Mecella, M., Soo, A.: Automated discovery of process models from event logs: Review and benchmark. IEEE Trans. Knowl. Data Eng. 31(4), 686–705 (2019). https://doi.org/10.1109/TKDE.2018.2841877
  * [9] Augusto, A., Conforti, R., Dumas, M., Rosa, M.L., Polyvyanyy, A.: Split miner: automated discovery of accurate and simple business process models from event logs. Knowl. Inf. Syst. 59(2), 251–284 (2019). https://doi.org/10.1007/s10115-018-1214-x
  * [10] Brockhoff, T., Uysal, M.S., Terrier, I., Göhner, H., van der Aalst, W.M.P.: Analyzing multi-level bom-structured event data. In: ICPM Workshops. pp. 47–59. Springer (2021). https://doi.org/10.1007/978-3-030-98581-3_4
  * [11] Cohn, D., Hull, R.: Business artifacts: A data-centric approach to modeling business operations and processes. IEEE Data Eng. Bull. 32(3), 3–9 (2009)
  * [12] Da Silveira, G., Borenstein, D., Fogliatto, F.S.: Mass customization: Literature review and research directions. International Journal of Production Economics 72(1), 1–13 (2001). https://doi.org/https://doi.org/10.1016/S0925-5273(00)00079-7
  * [13] Dumas, M., Rosa, M.L., Mendling, J., Reijers, H.A.: Fundamentals of Business Process Management, Second Edition. Springer (2018). https://doi.org/10.1007/978-3-662-56509-4
  * [14] Esser, S., Fahland, D.: Multi-dimensional event data in graph databases. J. Data Semant. 10(1-2), 109–141 (2021). https://doi.org/10.1007/s13740-021-00122-1
  * [15] Fahland, D.: Describing behavior of processes with many-to-many interactions. In: PETRI NETS. pp. 3–24. Springer (2019). https://doi.org/10.1007/978-3-030-21571-2_1
  * [16] Ghilardi, S., Gianola, A., Montali, M., Rivkin, A.: Petri nets with parameterised data - modelling and verification. In: Business Process Management - 18th International Conference, BPM 2020, Seville, Spain, September 13-18, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12168, pp. 55–74. Springer (2020). https://doi.org/10.1007/978-3-030-58666-9_4
  * [17] Kim, Y., Lee, J.: Manufacturing strategy and production systems: An integrated framework. Journal of Operations Management 11(1), 3–15 (1993). https://doi.org/https://doi.org/10.1016/0272-6963(93)90029-O
  * [18] Leemans, S.J.J., Fahland, D., van der Aalst, W.M.P.: Discovering block-structured process models from event logs - A constructive approach. In: PETRI NETS. pp. 311–329. Springer (2013). https://doi.org/10.1007/978-3-642-38697-8_17
  * [19] Li, G., de Carvalho, R.M., van der Aalst, W.M.P.: Automatic discovery of object-centric behavioral constraint models. In: BIS. pp. 43–58. Springer (2017). https://doi.org/10.1007/978-3-319-59336-4_4
  * [20] Li, G., de Murillas, E.G.L., de Carvalho, R.M., van der Aalst, W.M.P.: Extracting object-centric event logs to support process mining on databases. In: CAiSE Forum. pp. 182–199. Springer (2018). https://doi.org/10.1007/978-3-319-92901-9_16
  * [21] Milgate, M.: Supply chain complexity and delivery performance: an international exploratory study. Supply chain management: An international Journal 6(3), 106–118 (2001)
  * [22] Moctar-M’Baba, L., Assy, N., Sellami, M., Gaaloul, W., Nanne, M.F.: Extracting artifact-centric event logs from blockchain applications. In: SCC. pp. 274–283. IEEE (2022). https://doi.org/10.1109/SCC55611.2022.00048
  * [23] Montali, M., Rivkin, A.: Db-nets: On the marriage of colored Petri nets and relational databases. Trans. Petri Nets Other Model. Concurr. 12, 91–118 (2017). https://doi.org/10.1007/978-3-662-55862-1_5
  * [24] Nooijen, E.H.J., van Dongen, B.F., Fahland, D.: Automatic discovery of data-centric and artifact-centric processes. In: BPM Workshops. pp. 316–327. Springer (2012). https://doi.org/10.1007/978-3-642-36285-9_36
  * [25] Park, G., Adams, J.N., van der Aalst, W.M.P.: Opera: Object-centric performance analysis. In: ER. vol. 13607, pp. 281–292. Springer (2022). https://doi.org/10.1007/978-3-031-17995-2_20
  * [26] Polyvyanyy, A., Moffat, A., García-Bañuelos, L.: Bootstrapping generalization of process models discovered from event data. In: CAiSE. pp. 36–54. Springer (2022). https://doi.org/10.1007/978-3-031-07472-1_3
  * [27] Schuh, G., Gützlaff, A., Cremer, S., Schmitz, S., Ayati, A.: A data model to apply process mining in end-to-end order processing processes of manufacturing companies. In: IEEM. pp. 151–155. IEEE (2020). https://doi.org/10.1109/IEEM45057.2020.9309946
  * [28] Weerdt, J.D., Wynn, M.T.: Foundations of process event data. In: Process Mining Handbook, pp. 193–211. Springer (2022). https://doi.org/10.1007/978-3-031-08848-3_6
  * [29] van der Werf, J.M.E.M., Rivkin, A., Polyvyanyy, A., Montali, M.: Data and process resonance - identifier soundness for models of information systems. In: PETRI NETS. pp. 369–392. Springer (2022). https://doi.org/10.1007/978-3-031-06653-5_19
  * [30] Zeng, S., Melville, P., Lang, C.A., Boier-Martin, I.M., Murphy, C.: Using predictive analysis to improve invoice-to-cash collection. In: SIGKDD. pp. 1043–1050. ACM (2008). https://doi.org/10.1145/1401890.1402014


Dietcoin: shortcutting the Bitcoin verification process for your smartphone

Davide Frey††thanks: Univ Rennes, Inria, CNRS, IRISA, France, Marc X.
Makkes††thanks: Vrije Universiteit Amsterdam, The Netherlands, Pierre-Louis
Roman00footnotemark: 0,
François Taïani00footnotemark: 0, Spyros Voulgaris††thanks: Athens University
of Economics and Business, Greece

Project-Teams WIDE

Research Report n° 9162 — March 2018 — ?? pages

Abstract:  Blockchains have a storage scalability issue. Their size is not
bounded and they grow indefinitely as time passes. As of August 2017, the
Bitcoin blockchain is about 120 GiB big while it was only 75 GiB in August
2016. To benefit from Bitcoin full security model, a bootstrapping node has to
download and verify the entirety of the 120 GiB. This poses a challenge for
low-resource devices such as smartphones. Thankfully, an alternative exists
for such devices which consists of downloading and verifying just the header
of each block. This partial block verification enables devices to reduce their
bandwidth requirements from 120 GiB to 35 MiB.

However, this drastic decrease comes with a safety cost implied by a partial
block verification. In this work, we enable low-resource devices to fully
verify subchains of blocks without having to pay the onerous price of a full
chain download and verification; a few additional MiB of bandwidth suffice. To
do so, we propose the design of diet nodes that can _securely_ query full
nodes for shards of the UTXO set, which is needed to perform full block
verification and can otherwise only be built by sequentially parsing the
chain.

Key-words:  blockchain, sharding, UTXO, distributed ledger, cryptocurrency,
mobile computing

Dietcoin: court-circuiter la vérification dans Bitcoin pour les téléphones
mobiles

Résumé :

Les blockchains telles que Bitcoin passent mal à l’échelle, notamment du fait
de leurs besoins important de stockage. Les besoins de stockage d’une
blockchain typique ne sont pas limités et croissent indéfiniment. Par exemple,
en août 2017, les données contenues dans la blockchain Bitcoin représentaient
environ 120 GiB, contre 75 GiB un an auparavant, en août 2016. Pour bénéficier
des garanties complètes de sécurité apportées par Bitcoin, un nœud qui rejoint
le réseau doit télécharger et vérifier l’intégralité des 120 GiB de données.
Cette nécessité pose un défi pour les appareils à faibles ressources tels que
les smartphones. Heureusement, une alternative existe pour de tels dispositifs
qui consiste à télécharger et à vérifier seulement l’en-tête de chaque bloc de
la blockchain. Cette vérification partielle des blocs permet aux appareils de
réduire leurs besoins en bande passante de 120 GiB à 35 MiB, mais cette
diminution drastique ne permet qu’une vérification partielle des blocs, et
diminue grandement les garanties de sécurité offertes aux nœuds qui
l’utilisent.

Dans ce travail, nous proposons une approche qui permet aux appareils à
faibles ressources de vérifier entièrement des sous-chaînes de blocs sans
avoir à payer le prix onéreux d’un téléchargement et d’une vérification
complète de la chaîne ; quelques MiB supplémentaires de bande passante
suffisent. Pour ce faire, nous proposons d’introduire des nœuds Dietcoin qui
sont capables _en toute sécurité_ d’interroger des nœuds exécutant le
protocole complet pour obtenir des fragments d’un ensemble appelé UTXO,
nécessaire à la vérification complète des blocs.

Mots-clés :  blockchain, partitionnement, UTXO, registre distribué, monnaie
cryptographique, informatique mobile

###### Contents

  1. 1 Trustless Bitcoin
  2. 2 The Bitcoin system
    1. 2.1 Overview
      1. 2.1.1 Recording a new transaction
      2. 2.1.2 Irrevocability of deep blocks
    2. 2.2 Transactions, Blocks, and UTXO set
      1. 2.2.1 Checking block validity
      2. 2.2.2 The set of Unspent TransaCTion Outputs (UTXO set)
    3. 2.3 The limitations of SPV nodes
  3. 3 The Dietcoin system
    1. 3.1 Sharding the UTXO set
    2. 3.2 Linking blocks with the UTXO set
    3. 3.3 Extended verification
    4. 3.4 Detailed Operation
  4. 4 Related work
  5. 5 Conclusion

##  1 Trustless Bitcoin

Within a decade, blockchains have become extremely popular, and have been used
to implement several widely-used crytocurrencies [1], and smart-contract
services [2]. A blockchain implements a _tamper-proof distributed ledger_ in
which public transactions can be recorded in a close-to-irrevocable manner.
Recorded transactions are stored into _blocks_ , which are then incrementally
linked (or _chained_) in order to form an append-only list. The irrevocability
of these chaining mechanisms exploits cryptographic mechanisms and peer-to-
peer exchanges. This combination makes it in principle inconceivably hard for
individual participants to revoke past transactions (due to the computational
cost involved), while it remains possible for any participant to verify the
validity of a blockchain’s entire history.

Verifying a blockchain remains, however, a particularly costly process. The
verifying node must first download the entire blockchain, which in many cases
has reached a size beyond the communication capabilities of many mobile
devices. The Bitcoin blockchain, for instance, had grown to 120 GiB as of
August 2017 (Figure 1), and follows an exponential growth, implying the
problem can only become more acute.

Once the blockchain has been downloaded, the verifying node must then check
its consistency block by block, a lengthy process that can take hours on high-
end machines. The exorbitant price of a full chain verification makes it
unrealistic for low-resource devices to fully implement a blockchain protocol.
Some blockchain systems, such as Bitcoin, therefore enable nodes to perform
varying degrees of verification: _full nodes_ verify everything while
lightweight nodes only verify a small fraction of the data.

Figure 1: Both the Bitcoin blockchain and the UTXO set have almost tripled in
size in the past two years.

In the case of Bitcoin, this lightweight verification is known as _Simplified
Payment Verification_ (SPV for short). SPV nodes only download and verify a
much reduced version of the Bitcoin blockchain, comprised only of its block
headers, which today only weights 35 MiB (a reduction by three orders of
magnitude). This summary version however only contains the chaining
information making up the blockchain, not the recorded transactions. This
information is sufficient for SPV nodes to verify that the chain’s structure
is valid (and hence very unlikely to have been created by malicious nodes),
but not that a past transaction does exist in the chain. As a result, SPV
nodes are vulnerable to attacks in which an attacker leads an SPV node to
believe a transaction $t$ has occurred, while $t$ is later on rejected by the
system because the funds transferred by $t$ have in fact already been spent
(known as a _double-spend attack_).

To protect themselves against double-spend attacks, full nodes keep track of
unspent funds in a structure known as the set of _Unspent TransaCTion Outputs_
(UTXO set). The UTXO set is unfortunately costly to construct (as this
construction requires the entire blockchain), to exchange (currently weighing
1.9 GiB, see Figure 1), and to maintain, which explains why SPV nodes do not
use it.

In this report, we propose to bridge the gap between full nodes and SPV nodes
by introducing _diet nodes_ , and their associated protocol, _Dietcoin_.
Dietcoin strengthens the security guarantees of SPV nodes by bringing them
close to those of full nodes. Dietcoin enables low-resource nodes to verify
the transactions contained in a block without constructing a full-fledged UTXO
set. In our protocol, diet nodes download from full nodes only the parts of
the UTXO set they need in order to verify a transaction of interest. This
selective download mechanism must, however, be realized with care. Diet nodes
must be able to detect any tampering of the UTXO set itself, at a cost that
remains affordable for low-resource devices, both in terms of communication
and computing overhead.

The rest of this report is structured as follows. We first present the Bitcoin
protocol in more detail (Section 2), and explain the workings of full and SPV
nodes. We then detail the design of Dietcoin and diet nodes and discuss the
security guarantees they provide (Section 3). Finally, we present related work
(Section 4), and conclude (Section 5).

##  2 The Bitcoin system

A blockchain is a _decentralized ledger_ composed of blocks containing
transactions. The transactions, the blocks, and the resulting chain obey a few
core rules that ensure the system remains _tamper-proof_. Great care is
required when modifying these rules, as even minor changes might break the
blockchain’s properties and its security guarantees.

In the following, we first detail the default workings of the Bitcoin
blockchain and its rationale111Blockchains with closed membership or different
consensus protocols are not discussed in this section. We then build upon
these explanations to introduce and justify the changes we are proposing.

###  2.1 Overview

Figure 2: A blockchain is formed of a sequence of blocks containing
transactions. The current state of the blockchain (here $(B_{0},B_{1},B_{2})$)
is stored by each individual miner.

In a blockchain system such as Bitcoin, the blockchain proper
($(B_{k})_{k\in\mathbb{Z}_{\geq 0}}$, label 1 in Figure 2) is maintained by a
peer-to-peer network of miners. Each block $B_{k}$ links to the previous block
$B_{k-1}$ by including in its header a cryptographic hash that is _(i)_ easy
to verify, but _(ii)_ particularly costly to create (this second point is one
of the central element of blockchains with open membership, which we will
discuss in detail just below). The leftmost block $B_{0}$ is known as the
_Genesis Block_ : it is the first and oldest block in the blockchain, and it
is the only block with no predecessor.

####  2.1.1 Recording a new transaction

Figure 3: To add a new transaction to the current blockchain, a miner first
verifies the validity of the transaction. It must then solve a costly
cryptopuzzle to encapsulate this transaction in a new block (here $B_{3}$),
before disseminating this block to other miners.

To transfer 8 bitcoins from herself to Bob, the user Alice must first create a
valid transaction (label 2) that contains information proving she actually
owns the 8 bitcoins (with a cryptographic signature using asymmetric keys),
and encode the resulting transaction output with Bob’s public key (such that,
in turn, only Bob will be able to demonstrate ownership of the transaction’s
output).

Alice then broadcasts this new transaction to the network of miners 3, in
order for it to be included in the blockchain. Before adding Alice’s
transaction into the blockchain, Miner A first verifies that the transaction
is valid (label 4 in Figure 3, details on the transaction verification process
will follow in Section 2.2.1-(BV2)).

Miner A then includes Alice’s transaction together with other transactions
received in parallel into a new block ($B_{3}$, 5), and attempts to link it to
the current tip of the blockchain. This linkage operation requires Miner A to
solve a probabilistically difficult cryptopuzzle 6 that regulates the
frequency at which blocks are created (or _mined_) by the whole network. (In
Bitcoin, this periodicity is set to one block every 10 minutes.) If Miner A
succeeds, the new block $B_{3}$ is now linked to the existing block chain
$(B_{0},B_{1},B_{2})$, and is disseminated to the other miners 7. When a miner
receives a new block (here Miner B), it checks that the transactions included
are valid, along with the cryptopuzzle 8, before including the new block in
its local copy of the blockchain. The new block ultimately reaches Bob 9, who
can check that the transaction has been properly recorded (and can then, for
example, sell some goods to Alice).

####  2.1.2 Irrevocability of deep blocks

Because blocks are produced at a limited rate such that all the miners receive
block $B_{k}$ before they can successfully mine a concurrent block
$B_{k^{\prime}}$, honest miners are highly likely to extend the chain when
producing a new block, ensuring a consistent system state with high
probability. The views of individual miners may however diverge in problematic
cases, causing branches to appear. When a branch occurs, miners resolve the
divergence by choosing as valid branch the one that was the most difficult to
create (details on block difficulty will follow in Section 2.2.1-(BV2)).
Blocks that are left out of the chain are said to be _orphan_.

Figure 4: Revoking the content of a block $B_{n-k}$ deep in the chain requires
constructing a better alternative subchain, which becomes exponentially harder
as the block lies deeper.

The risk of being made orphan decreases exponentially as a block lies deeper
in a chain, ensuring the _practical irrevocability_ of deep blocks and the
transactions they contain. This is illustrated in Figure 4: consider an
attacker who wishes to revoke a block $B_{n-k}$ (targeted block), that lies
$k$ blocks away from the chain’s tip $B_{n}$. For this attack to succeed, this
attacker must produce an alternative subchain
$(B^{\prime}_{n-k},..,B^{\prime}_{n},B^{\prime}_{n+1})$ that is more difficult
to create than the current chain. Producing this subchain is however extremely
costly, and takes time which increases the odds that the legitimate chain
grows (with a block $B_{n+1}$, thus requesting an even more difficult attack
subchain) before the attacker succeeds. When the computing power of the
attacker is less than half of that of the rest of the network, his probability
of success drops exponentially with $k$.

###  2.2 Transactions, Blocks, and UTXO set

To benefit from the full security of Bitcoin, Bob should verify the validity
of the new block that contains Alice’s payment to him (label 9 in Figure 3) in
addition to verifying the validity of Alice’s transaction. This is because
Alice could collude with a miner (or launch herself a miner), and produce an
invalid block that she would advertise to Bob. Bitcoin relies on a number of
built-in validity checks on blocks and transactions to conduct this
verification. However, whereas _full nodes_ exploit all of these checks,
_Simple Payment Verification nodes_ (SPV nodes) only perform a limited
verification. In the following, we describe the details of these validity
checks, we discuss the role of an intermediary set known as the set of
_Unspent TransaCTion Outputs_ (UTXO set), and the shortcomings of SPV nodes
ensued by the limited verification they perform.

####  2.2.1 Checking block validity

A block is valid if and only if it meets the following two conditions.

  * •

(BV1) Its header respects the blockchain’s _Proof-of-Work predicate_.

  * •

(BV2) It only contains valid transactions (which we discuss further below).

BV1: The Proof-of-Work predicate makes it very difficult for malicious actors
to alter the blockchain in an attempt to edit the ledger. The Proof-of-Work
predicate is used as a lock-in mechanism to anchor blocks in the chain. It is
enforced on each block header, whose simplified structure is shown in Figure
5. The header of each block $B_{k}$ points both to the header of the previous
block $B_{k-1}$ (using a hash function, 1), and to the transactions contained
in the current block $B_{k}$ 2.

Figure 5: Content of a block header (simplified).

To fulfill the Proof-of-Work predicate 4, a header must contain a _nonce_ 3
such that the hash of the header is less than a _difficulty target_. The
difficulty target is set so that a new block is created every ten minutes by
the miners as a whole, regardless of the computation power (the difficulty
target is regularly adjusted to cope with changes in their computation power).
Finding a nonce respecting the difficulty target is computationally very
expensive, as every miner competes to create blocks. This computing cost
prevents attackers from easily tampering the chain as they have to recompute
fresh nonces for the blocks they wish to replace.

To establish a secure and verifiable link between the header of $B_{k}$ and
the corresponding block $B_{k}$, the pointer to $B_{k}$’s transactions 2
consists of the root of a Merkle tree. A Merkle tree is a hierarchical hashing
mechanism for sets that enables a verifier to efficiently test whether an item
(here a transaction) belongs to the set by reconstructing the root of the
Merkle tree. Each leaf node in a Merkle tree consists of the hash of an item,
while each internal node (including the root) consists of the hash of its
children. This makes it possible to reconstruct the root, and thus verify set
membership, using only a logarithmic number of intermediate hashes. In Figure
6 for example, a node can verify the presence of transaction $A$ in the set by
_(i)_ downloading the root from a secured communication channel (e.g., the
blockchain), and _(ii)_ downloading $A$ and the three intermediate hashes
shown in red: $H_{B}$, $H_{CD}$ and $H_{EFGH}$, and reconstructing the root
from the downloaded hashes. The reconstructed root should match the downloaded
one.

Figure 6: Example of a Merkle tree root reconstruction that only needs
$log(n)$ hashes.

BV2: In addition to the Proof-of-Work predicate (BV1), all the transactions
included in a block must also be valid for the overall block to be valid.
Figure 7 shows the validity mechanisms included in a typical Bitcoin
transaction. In this example, Alice uses 3 coins she owns (the transaction’s
inputs 1) to pay 7 Bitcoins to Bob, and 4 to Tux (the transaction’s outputs
2).

Only coins created in earlier transactions may be spent: each of Alice’s
inputs therefore points back to the output of an earlier transaction 3. To
ensure that only the recipients (Bob and Tux) are able to spend the output,
each new coin contains an ownership challenge (a hashed public key), that must
be solved to spend this coin 4.

Alice’s transaction is only valid if the following three conditions are met:

  * •

(TV1) The inputs do exist, and Alice owns them. She can prove her ownership of
the inputs by providing a public key matching their ownership challenges 5,
and by signing the new transaction with the corresponding private
key222Bitcoin uses a scripting language to encode challenges and proofs of
ownership, enabling for more complex schemes, but for ease of exposition we
limit ourselves to the typical case. 6 ;

  * •

(TV2) No money is created in the transaction. In effect, the total value of
the transaction’s inputs must be greater than or equal to that of its outputs:

$\sum_{\begin{subarray}{c}\mathit{in}\in\mathsf{inputs}(t)\end{subarray}}{\mathsf{value}(\mathit{in})}\geq\sum_{\begin{subarray}{c}\mathit{out}\in\mathsf{outputs}(t)\end{subarray}}{\mathsf{value}(\mathit{out})}.$

The difference
$\sum{\mathsf{value}(\mathit{in})}-\sum{\mathsf{value}(\mathit{out})}$ is
given as a fee to the miner of the block containing the transaction;

  * •

(TV3) The transaction’s inputs $(\mathsf{tx\\_ID}_{i},\mathsf{index}_{j})$
have not been spent yet (i.e., they do not appear as inputs of any earlier
transaction, an attack known as a _double spend_).

Figure 7: Structure of a transaction.

####  2.2.2 The set of Unspent TransaCTion Outputs (UTXO set)

While the validity of a block’s header (BV1) only requires access to the
current block $B_{k}$, and to the header of its predecessor $B_{k-1}$,
verifying transactions (BV2) requires a lot more information. Verifying the
ownership challenges of input coins (TV1), and their amount (TV2) requires
access to the transactions recorded in earlier blocks. Worse, verifying that
inputs coins have not yet been spent (TV3) potentially requires parsing and
verifying the entire blockchain.

To avoid performing such a costly operation for each new block, nodes that
verify transactions maintain an intermediary set known as the set of _Unspent
TransaCTion Outputs_ (UTXO set). The UTXO set contains all the coins that have
been created in the chain but not spent in later transactions, it thus
contains all the spendable coins.

A node verifying transactions can prevent double spends (TV3) by simply
ensuring that all the inputs of a transaction appears in its UTXO set. The
UTXO set evolves as new correct blocks are added to the chain: transaction
outputs are removed from the set when they are spent, and outputs of new
transaction are added to the set.

###  2.3 The limitations of SPV nodes

In spite of its benefits, constructing a local UTXO set is costly: in order to
obtain the set, a node must first download the entire chain (120 GiB as of
August 2017, see Figure 1 and validate it (a lengthy process that can take
hours on high-end machines), even if only the latest block is relevant to its
interest.

Because of this cost, Bitcoin supports several levels of verification.
_Miners_ and users running _full nodes_ construct the UTXO set and check both
block headers (BV1) and transactions (TV1,2,3 and as a result BV2). By
performing all the possible checks, full nodes benefit from the maximum
security that the Bitcoin system has to offer.

By contrast, _Simple Payment Verification_ nodes (SPV nodes) do not construct
the UTXO set. Instead, they only download the chain’s block headers (rather
than full blocks), and verify that these headers are valid (BV1). With the
headers only, SPV nodes are able to verify the well-formedness of the
blockchain including the crucial Proof-of-Work predicate that seals the links
of the chain.

However, because this verification is only partial, SPV nodes are unable to
detect if a new block contains an invalid transaction. This scenario, however
probabilistically difficult to accomplish for an attacker, is a vulnerability
of SPV nodes. To circumvent this vulnerability, SPV nodes typically wait until
miners have created subsequent blocks extending the chain containing a block
of interest, which implies that these miners have performed a full
verification on it and consider this block as valid.

The need for SPV nodes to wait makes it particularly problematic to use
Bitcoin on limited devices (i.e. mobile phones) for everyday transactions. SPV
nodes are not even able to check whether the inputs used in a transaction do
exist. It also limits the ability of SPV nodes to detect faulty transactions
as early as possible, which is an important usability feature of modern
payment systems.

In this work, we propose to overcome the inherent limitations of SPV nodes
with _Dietcoin_. Dietcoin enables nodes with limited resources (_diet nodes_)
to benefit from a security level that is close to that of full nodes, at a
fraction of the cost required to run full security checks.

##  3 The Dietcoin system

To address the vulnerabilities of SPV nodes and to improve the confidence
mobile users can have in recent transactions, we propose Dietcoin, an
extension to Bitcoin-like blockchains. Although our proposal can be applied to
most existing Proof-of-Work blockchains using the UTXO model for coins, we
describe Dietcoin in the context of the Bitcoin system as presented in Section
2.

The core of Dietcoin consists of a novel class of nodes, called _diet nodes_ ,
which provide low-power devices with the ability to perform _full block
verification_ with minimal bandwidth and storage requirements. Instead of
having to download and process the entire blockchain to build their own copy
of the UTXO set, diet nodes query the UTXO set of full nodes and use it to
verify the legitimacy of the transactions they are interested in (as described
in Section 2.2.1-(BV2)) and the correctness of the blocks that contain them.
This gives diet nodes security properties that sit in between those of full
nodes, and those of Bitcoin’s SPV nodes.

Consider a user wishing to verify a transaction for the sale of some goods.
The user’s diet node will initially proceed like a standard SPV node. It will
contact a full node to obtain the header of the block that supposedly contains
its transaction as well as the corresponding branch of the transaction Merkle
tree, to verify that the transaction indeed is included in the block. But
while an SPV node would stop at this inclusion check, the diet node continues
by verifying both the inclusion and the correctness of all the transactions in
the block. To make this possible we introduce the possibility for diet nodes
to access the state of the UTXO set of full nodes corresponding to the instant
right before the block they want to verify.

Since downloading the entire UTXO set would result in prohibitive bandwidth
overhead, as shown in Figure 1, Dietcoin-enabled full nodes split their UTXO
set into small shards, enabling diet nodes to download only the shards that
are relevant to the transactions in the block.

To prevent diet nodes from trusting maliciously forged shards, the shard
hashes are used as leaves of a Merkle tree, which root is stored in each
block. Having the Merkle root stored in blocks enables the UTXO shards to
benefit from the same Proof-of-Work protection as transactions.

In addition to the full verification done on the block of their interest
$B_{k}$, diet nodes can increase their trust in $B_{k}$ by fully verifying its
previous blocks. By doing so, diet nodes are ensured that none of the $l$
verified blocks contain illegal transactions nor erroneous UTXO Merkle root.
To make a diet node trust a forged transaction in block $B_{k}$, an attacker
has to counterfeit the subchain of $l+1$ blocks $(B_{k-l},...,B_{k})$. Thanks
to the Proof-of-Work protection, the cost of this attack increases
exponentially as $l$ increases linearly.

In the following, we detail the operation of Dietcoin by first describing how
full nodes can provide diet nodes with verifiable UTXO shards. Secondly we
discuss how miners link blocks to the state of their UTXO set. We then explain
how diet nodes can extend the verification process from one block to a
subchain of any length. Finally, we detail the operation of diet nodes when
verifying transactions.

###  3.1 Sharding the UTXO set

To enable the operation of diet nodes, Dietcoin-enabled full nodes need _(i)_
to provide diet nodes with shards of the UTXO set, while _(ii)_ enabling them
to verify that these shards are authentic.

To satisfy _(i)_ , Dietcoin-enabled full nodes store the UTXO set resulting
from the application of the transactions in each block in the form of shards
with a predefined maximum size of 1 KiB (on average, across all shards). The
use of shards enables diet nodes to download only the relevant parts of the
UTXO set and also limits the storage requirements at full nodes, which only
need to store the modified shards for each block to let diet nodes query older
versions of the shards. Similarly, the limit of 1 KiB for the size of each
shard limits the bandwidth employed by diet nodes in the verification process.

To satisfy _(ii)_ , full nodes also maintain a Merkle tree that indexes all
the shards of the UTXO set. Using shards also proves advantageous with respect
to this Merkle tree. If nodes were to index UTXO entries directly, the
continuous changes in the UTXO set would cause the Merkle tree to become
quickly unbalanced, leading to performance problems or requiring a potentially
costly self-balancing tree. The use of shards, combined with the right
sharding strategy, gives the UTXO Merkle tree a relatively constant structure,
enabling shards to be updated in place most of the time. Moreover, it makes it
possible to predict the size of the UTXO Merkle tree and its incurred
overhead, which enables us to better control and balance the storage overhead
for full nodes and the bandwidth requirements of diet nodes.

A number of sharding strategies satisfy the requirement of a fixed number of
shards. In this work, we use the simplest approach consisting of indexing UTXO
entries by their first $k$ bits. This strategy resembles a random approach
since the first bits of an UTXO are the transaction hash it references, which
value is expected to be random due to the uniformity property of the SHA-256
hash function. This strategy comes with the added advantages of obtaining
shards of homogeneous size and a full binary Merkle tree with $2^{k}$ leaves.

Keeping in mind the size cap of 1 KiB per shard, $k$ can be adapted locally by
each node to cope with the growth of the UTXO set. When the average shard size
breaches the cap of 1 KiB, $k$ is incremented by one resulting in _(i)_
halving the average shard size, and _(ii)_ adding one layer to the Merkle
tree, doubling its storage footprint in the process.

###  3.2 Linking blocks with the UTXO set

With reference to Figure 8, consider a Dietcoin-enabled miner that is mining
block $B_{k}$, and let $\textsc{UTXO}_{k}$ be the state of the UTXO set after
applying all the transactions in $B_{k}$. The miner stores the root of the
UTXO Merkle tree associated with $\textsc{UTXO}_{k}$ as an unspendable output
in the first transaction of block $B_{k}$ before trying to solve the Proof-of-
Work as shown in Figure 8. Storing the root of the UTXO Merkle tree in the
first transaction of the block does not require any modification to the
structure of Bitcoin’s blocks. Thus it is possible for Dietcoin-enabled full
nodes and miners to co-exist with their legacy Bitcoin counterparts.

Dietcoin-enabled full nodes verify the value of the UTXO Merkle root against
their own local copy when they verify a block, while legacy Bitcoin nodes
simply ignore it.

Figure 8: The UTXO set is updated every time a block is validated. For a
counterfeited block to be validated by diet nodes, a malicious node has to
forge at least two consecutive blocks: the first block $B_{k-1}$ containing a
fake Merkle root of $\textsc{UTXO}_{k-1}$, and the second block $B_{k}$
spending fake coins validated by the fake $\textsc{UTXO}_{k-1}$.

The UTXO Merkle tree provides a computationally efficient way for diet nodes
to verify whether the shards they download during the verification process are
legitimate and correspond to the current state of the ledger. Still referring
to Figure 8, let us consider a diet node $d$ that wishes to verify a
transaction in block $B_{k}$. Node $d$ needs to obtain: block $B_{k}$, the
UTXO Merkle root in block $B_{k-1}$, the shards of the UTXO set between the
two blocks, and the elements of the associated Merkle tree that are required
to verify their legitimacy. It can then verify the shards using the root
stored in block $B_{k-1}$’s first transaction, and use them to verify the
correctness of the transactions in $B_{k}$.

We observe that storing the Merkle-root referring to the state after the block
into the block itself forces diet nodes to download two blocks to verify
transactions. This makes it inherently harder for an attacker to provide a
diet node with a fake block $B_{k}$ because it would need to forge not only
block $B_{k}$ but also block $B_{k-1}$.

###  3.3 Extended verification

Diet nodes have the ability to extend their confidence in a block by iterating
the verification process towards its previous blocks. By doing so, diet nodes
ensure the correctness of the UTXO Merkle root present in block $B_{k-1}$ used
to verify the correctness of block $B_{k}$. The extended verification can be
performed on a subchain of any length $l$ provided that the verifying diet
node can query UTXO shards of any age. A diet node fully verifying the
subchain $(B_{k-l+1},...,B_{k})$ can only be tricked into trusting a malicious
transaction in block $B_{k}$ if the attacker manages to counterfeit the $l+1$
successive blocks starting from $B_{k-l}$, which becomes exponentially more
costly as $l$ increases linearly.

The block $B_{k-l}$ contains the UTXO Merkle root that serves as a basis for
the verification of the consequent blocks. Since the block $B_{k-l}$ is not
verified, it is thus trusted by the diet node. A comparison can be made with
full nodes where the first block of the chain, the genesis block, is hard-
coded and is therefore trusted. By shifting the trust from the genesis block
to the block $B_{k-l}$ for diet nodes, Dietcoin effectively shortcuts the
verification process.

Picking the value of $l$ exhibits a trade-off between security and
verification costs. On one hand choosing a great $l$ draws the behavior of the
diet node closer to that of a full node, while on the other hand choosing a
small $l$ draws it closer to that of an SPV node. The user can make her
decision based on which block depth $l$ is great enough in her opinion such
that all blocks prior to $B_{k-l}$ are unlikely to be counterfeited. For
instance, a diet node user can choose $l$ such that the trusted block has a
block depth of 6 or greater since it is the de facto standard in Bitcoin to
consider blocks of depth 6 or greater as
secured333https://bitcoin.org/en/developer-guide#verifying-payment.

In the case depicted in Figure 8, assuming $l=2$, diet node $d$ downloads
block $B_{k-1}$ to verify the transactions and the UTXO Merkle root in
$B_{k-1}$ to further increase its confidence in $B_{k}$. To verify $B_{k-1}$,
the diet node uses the UTXO Merkle root in $B_{k-2}$.

###  3.4 Detailed Operation

Equipped with the knowledge of Dietcoin’s basic mechanisms, we can now detail
the verification process carried out by diet nodes. Algorithm 1 depicts the
actions taken by a diet node when its user starts the application using
Dietcoin and compares it with those taken by legacy SPV clients. Black dotted
lines [$\bullet$] are specific to diet nodes, while hollow dotted lines
[$\circ$] are common to both diet and SPV nodes.

The algorithm begins when the application using Dietcoin starts and updates
its view of the blockchain. In this first part of the algorithm, a diet node
behaves exactly in the same manner as an SPV node. First, it issues a query
containing the latest known block hash and an obfuscated representation of its
own public keys in the form of a bloom filter (lines 4-5). A full node
responds to this query by sending a list of all the block headers that are
still unknown to the SPV/diet node, together with the transactions matching
the SPV/diet node’s bloom filter, and the information from the transaction
Merkle tree that is needed to confirm their presence in their blocks. Using
this information, the SPV/diet node verifies the received headers (including
Proof-of-Work verification) and updates its view of the blockchain (line 6).

Since the response from the full node might contain false positives due to the
use of a bloom filter for public key obfuscation, the next verification step
consists in ensuring that the received transactions match one of the user’s
public keys (lines 8-9). Once false positives are discarded, the SPV/diet node
verifies that the received transactions are in the blocks (line 10-12).

At this point, a standard SPV node simply returns the received transactions to
the application (line 14). A diet node, on the other hand, continues the
verification process. To this end, the diet node first computes which blocks
to fully verify to ensure that _(i)_ no block is fully verified twice (line
17), _(ii)_ old blocks considered by the user as secured enough are not fully
verified (parameter $\mathsf{maxDepth}_{p}$, line 17) and _(iii)_ only a
subchain of limited length $l$ is fully verified (parameter
$\mathsf{maxLength}_{p}$, line 19). If no block is selected for full
verification, the diet node falls back to SPV mode (lines 20-21).

To bootstrap the full verification process, the diet node must first download
the UTXO Merkle root present in the block prior to the first block to verify
(line 23). For each of the selected blocks $B_{k}$, the diet node downloads
from Dietcoin-enabled full nodes _(i)_ the block $B_{k}$ itself (line 25),
_(ii)_ the state, before $B_{k}$, of the UTXO shards associated with both the
block’s transactions’ inputs and outputs (line 26), and _(iii)_ the partial
UTXO Merkle tree required to prove the integrity of the downloaded shards
(line 26).

Once it has all the data, the diet node proceeds with the verification
process. For each block $B_{k}$, it first verifies that the downloaded UTXO
shards match the UTXO Merkle root from the previous block $B_{k-1}$ (lines
27-29). Then it verifies that the transactions in each block use only
available inputs from these shards (lines 32-33), and computes the new state
of these shards based on the transactions in $B_{k}$ (lines 34, 36). Finally
it verifies that the updated shards lead to the UTXO Merkle root contained in
$B_{k}$ (lines 37-39). Once the verification process has terminated, the diet
node returns the transactions associated with the local user to the
application (line 14).

##  4 Related work

Making the UTXO set available for queries between nodes has been discussed
several times in the Bitcoin community over the past few years. Bryan Bishop
published a comprehensive list of such proposals [3] that share some of the
following goals: _(i)_ enabling faster node bootstrap, _(ii)_ strengthening
the security guarantees of lightweight nodes, and _(iii)_ scaling the UTXO set
to reduce its storage cost. The primary goal of Dietcoin is to strengthen the
security of lightweight nodes. Dietcoin’s strongest feature is the ability for
diet nodes to efficiently perform subchain verification, as described in
Section 3.3, which offers stronger security guarantees than the referenced
proposals made by the community. Moreover, even though we focus in this report
on the security of lightweight nodes, it is also possible to bootstrap full
nodes faster with Dietcoin.

Sharing similar goals with Dietcoin, Andrew Miller [4] suggests to store in
blocks the root of a self-balancing Merkle tree built on top of the UTXO set.
In such a system, lightweight nodes only download the UTXOs they need, which
results in a lower bandwidth consumption than with shards as we propose it,
but at the cost of a greater storage overhead since the stored Merkle tree is
larger. Moreover, Dietcoin combines a full, and thus always balanced, Merkle
tree built on top of $2^{k}$ shards that can each be updated in place as
blocks are appended to the chain. This combination of tree stability and
updatable shards enables efficient subchain verification, as described in
Section 3.3, and adapting this feature to a system using a self-balancing
Merkle tree does not seem trivial.

Vault [5] also proposes to use Merkle trees to securely record the state of
the distributed ledger in recent blocks, and shards this state across nodes,
to reduce storage costs. Contrarily to Dietcoin, however, Vault targets
balance-based schemes, such as introduced by Ethereum, in blockchains relying
on Proof-of-Stake consensus. Vault further stores individual accounts in the
Merkle trees, rather than UTXO shards as we do. This represents a different
and to some extent orthogonal trade-off to that of Dietcoin, in that Vault
chooses to increase the size of Merkle tree witnesses that must be included in
transactions, but removes the need for lightweight nodes to download UTXO
shards.

Whereas we focus on sharding the resulting state of the blockchain, other
systems propose to shard the verification process. Both Elastico [6] and
OmniLedger [7] proposes a permissionless distributed ledger using multiple
classical PBFT consensus protocols each executing within a subset (shard) of
nodes.

Elastico limits the number of shards a malicious nodes may join (under
different identifies) by tying the shard of a node to the result of a Proof-
of-Work puzzle. OmniLedger [7] extends the ideas proposed by Elastico [6] to
increase the size of the shards (and thus reduce the probability of failures),
and allow for cross-shards transactions thanks to a Byzantine shard-atomic
commit protocol called _Atomix_. Both Elastico and OmniLedger use sharding to
increase the transaction processing power of a distributed ledger, rather than
to improve access and verification of the UTXO set, as we do.

Chainiac [8] combines the ideas of skiplists and blockchains to realize
_skipchains_ , an authenticated log with both back and forward long-distance
links to implement a distributed authenticated software-release ledger.
Chainiac relies on digital collective signatures to implement forward links,
which are not available in permissionless Proof-of-Work chains such as
Bitcoin. Long distance links are particularly well adapted to navigate a well-
identified subset of a blockchain (such as a package’s releases). They were
not however directly designed to handle the kind of dependencies captured by
the UTXO model.

An entirely different approach to scaling blockchains for lightweight nodes is
the use of Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) [9] that enable
constant size queries. NIPoPoWs strive for minimal cost of proof of inclusion
of a transaction in a chain, thus reducing to a minimum the bandwidth
requirements of lightweight nodes. NIPoPoWs however do not aim at offering
improved security for lightweight nodes as we do with Dietcoin.

##  5 Conclusion

In this report, we have presented the design of Dietcoin, that proposes a new
form of Bitcoin nodes that strengthens the security guarantees of lightweight
SPV nodes by bringing them closer to those of full Bitcoin nodes. The Dietcoin
protocol enables low-resource nodes to verify the transactions contained in
blocks without constructing a full-fledged UTXO set. In our protocol, diet
nodes download from full nodes parts of the UTXO set they need in order to
verify a block, or a subchain of blocks, of interest. Diet nodes are able to
detect any tampering of the UTXO set itself, at a cost that remains affordable
for low-resource devices, both in terms of communication and computing
overhead. In our approach, Dietcoin-enabled full nodes split their UTXO set
into small shards, and enable diet nodes to download only the shards that are
relevant to the transactions in the block, while verifying that these shards
do indeed corresponds to the state of the UTXO set for the block they are
verifying.

## Acknowledgments

This work has been partially funded by the Region of Brittany, France, by the
Doctoral school of the University of Brittany Loire (UBL), by the French
National Research Agency (ANR) project _SocioPlug_ under contract
ANR-13-INFR-0003 (http://socioplug.univ-nantes.fr) and by the SIDN Fonds
contract 172027.

## References

  * [1] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008. [Online]. Available: http://www.cryptovest.co.uk/resources/Bitcoin%20paper%20Original.pdf
  * [2] T. D. Dickerson, P. Gazzillo, M. Herlihy, and E. Koskinen, “Adding concurrency to smart contracts,” in _ACM Symposium on Principles of Distributed Computing, PODC_ , 2017, pp. 303–312. [Online]. Available: http://doi.acm.org/10.1145/3087801.3087835
  * [3] B. Bryan, “[bitcoin-dev] Protocol-Level Pruning,” Nov. 2017. [Online]. Available: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-November/015297.html
  * [4] A. Miller, “Storing UTXOs in a Balanced Merkle Tree (zero-trust nodes with O(1)-storage),” Aug. 2012, https://bitcointalk.org/index.php?topic=101734.0.
  * [5] D. Leung, A. Suhl, Y. Gilad, and N. Zeldovich, “Vault: Fast bootstrapping for cryptocurrencies,” Cryptology ePrint Archive, Report 2018/269, 2018, https://eprint.iacr.org/2018/269.
  * [6] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A Secure Sharding Protocol For Open Blockchains,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’16. New York, NY, USA: ACM, 2016, pp. 17–30. [Online]. Available: http://doi.acm.org/10.1145/2976749.2978389
  * [7] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_ , vol. 00, San Francisco, May 2018, pp. 19–34. [Online]. Available: doi.ieeecomputersociety.org/10.1109/SP.2018.000-5
  * [8] K. Nikitin, E. Kokoris-Kogias, P. Jovanovic, N. Gailly, L. Gasser, I. Khoffi, J. Cappos, and B. Ford, “CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds,” in _26th USENIX Security Symposium (USENIX Security 17)_. Vancouver, BC: USENIX Association, 2017, pp. 1271–1287. [Online]. Available: https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/nikitin
  * [9] A. Kiayias, A. Miller, and D. Zindros, “Non-interactive proofs of proof-of-work,” Tech. Rep. 963, 2017. [Online]. Available: https://eprint.iacr.org/2017/963

$\mathrm{bloomFilter}(\mathsf{keys})$ | Compute a bloom filter from $\mathsf{keys}$
---|---
$\mathrm{buildMRoot}(\mathsf{hashes})$ | Compute the Merkle root from $\mathsf{hashes}$
$\mathrm{getShardKey}(\mathsf{txId})$ | Apply the sharding algorithm to $\mathsf{txId}$
$0pt(\mathsf{header})$ | Index of $\mathsf{header}$ starting from the genesis block
$\mathrm{updateMTreeInPlace}(\mathsf{MTree},\mathsf{dataset})$ | Update the hashes of $\mathsf{MTree}$ with the new value of $\mathsf{dataset}$
$\mathrm{verifyHeaders}(\mathsf{headers})$ | Add $\mathsf{headers}$ to the chain, return the hash of the new chain tip
Algorithm 1 – SPV [$\circ$] and Diet [$\circ\bullet$] node $p$ (compacted)

1:$\textbf{parameters:}~{}\circ\mathsf{pubKeys}_{p},\bullet~{}\mathsf{maxDepth}_{p},\bullet~{}\mathsf{maxLength}_{p}$

2:$\textbf{global
variables:}~{}\circ\mathsf{headerStore}_{p},\circ~{}\mathsf{tipId}_{p},\bullet~{}\mathsf{highestVerified}_{p}$

$\circ$3:procedure updateChain( ) $\triangleright$ App interface

$\circ$4:
$\mathsf{filter}\leftarrow\mathrm{bloomFilter}(\mathsf{pubKeys}_{p})$

$\circ$5:
$(\\{\mathsf{header},\mathsf{txMTree},\mathsf{txs}\\})\leftarrow\textbf{send}~{}\textsc{queryMerkleBlocks}(\mathsf{tipId}_{p},\mathsf{filter})$

$\circ$6:
$\mathsf{tipId}_{p}\leftarrow\mathrm{verifyHeaders}((\mathsf{header}))$

$\circ$7: for all
$\\{\mathsf{header},\mathsf{txMTree},\mathsf{txs}\\}\in(\\{\mathsf{header},\mathsf{txMTree},\mathsf{txs}\\})$
do

$\circ$8: if $\forall
k\in\mathsf{pubKeys}_{p}:k\notin\\{\mathsf{tx.inputs}\cup\mathsf{tx.outputs}\\}$
then

$\circ$9: continue $\triangleright$ Ignore bloom filter false positives

$\circ$10:
$\textbf{assert}(\forall\mathsf{tx}\in\mathsf{txs}:\mathrm{HASH}(\mathsf{tx})\in\mathsf{txMTree})$

$\circ$11:
$\mathsf{builtTxMRoot}\leftarrow\mathrm{buildMRoot}(\mathsf{txMTree})$

$\circ$12: $\textbf{assert}(\mathsf{builtTxMRoot}=\mathsf{header.txMRoot}$)

$\bullet$13: $\textsc{verifyBlocksUpTo}(0pt(\mathsf{header}))$

$\circ$14: $\textbf{callback}(\mathsf{txs},\mathsf{header}$) $\triangleright$
Callback to app

$\bullet$15:procedure verifyBlocksUpTo($\mathsf{last}$)

$\bullet$16: $\triangleright$ Do not verify blocks twice or below
$\mathsf{maxDepth}_{p}$

$\bullet$17:
$\mathsf{first}\leftarrow\textbf{max}(\mathsf{highestVerified}_{p},0pt(\mathsf{tipId}_{p})-\mathsf{maxDepth}_{p})$

$\bullet$18: $\triangleright$ Verify up to $\mathsf{maxLength}_{p}$ blocks

$\bullet$19:
$\mathsf{first}\leftarrow\textbf{max}(\mathsf{first},\mathsf{last}-\mathsf{maxLength}_{p})$

$\bullet$20: if $\mathsf{first}\geq\mathsf{last}$ then

$\bullet$21: return $\triangleright$ Fallback to SPV mode

$\bullet$22: $\triangleright$ The first UTXO Merkle root is not verified

$\bullet$23:
$\mathsf{utxoMRoot}\leftarrow\textbf{send}~{}\textsc{queryUtxoMRoot}(\mathrm{HASH}(\mathsf{headerStore}_{p}[\mathsf{first}]))$

$\bullet$24: for all $\mathsf{blockId}$ of height
$\in[\mathsf{first}+1,\mathsf{last}]$ do

$\bullet$25:
$\mathsf{block}\leftarrow\textbf{send}~{}\textsc{queryBlock}(\mathsf{blockId})$

$\bullet$26:
$\\{\mathsf{shards},\mathsf{utxoMTree}\\}\leftarrow\textbf{send}~{}\textsc{queryUtxos}(\mathsf{blockId})$

$\bullet$27:
$\textbf{assert}(\forall\mathsf{shard}\in\mathsf{shards}:\mathrm{HASH}(\mathsf{shard})\in\mathsf{utxoMTree})$

$\bullet$28:
$\mathsf{builtUtxoMRoot}\leftarrow\mathrm{buildMRoot}(\mathsf{utxoMTree})$

$\bullet$29: $\textbf{assert}(\mathsf{builtUtxoMRoot}=\mathsf{utxoMRoot})$

$\bullet$30: for all $\mathsf{tx}\in\mathsf{block.transactions}$ do

$\bullet$31: for all $\mathsf{i}\in\mathsf{tx.inputs}$ do

$\bullet$32:
$\mathsf{shard}\leftarrow\mathsf{shards}[\mathrm{getShardKey}(\mathsf{i})]$

$\bullet$33: $\textbf{assert}(\mathsf{i}\in\mathsf{shard}\wedge\text{valid
proof of ownership of }\mathsf{i})$

$\bullet$34: $\mathsf{shard}.\mathrm{remove}(\mathsf{i})$

$\bullet$35: for all $\mathsf{o}\in\mathsf{tx.outputs}$ do

$\bullet$36:
$\mathsf{shards}[\mathrm{getShardKey}(\mathsf{o})].\mathrm{add}(\mathsf{o})$

$\bullet$37:
$\mathsf{utxoMTree}\leftarrow\mathrm{updateMTreeInPlace}(\mathsf{utxoMTree},\mathsf{shards})$

$\bullet$38:
$\mathsf{utxoMRoot}\leftarrow\mathrm{buildMRoot}(\mathsf{utxoMTree})$

$\bullet$39:
$\textbf{assert}(\mathsf{utxoMRoot}=\mathsf{block}.\mathsf{utxoMRoot})$

$\bullet$40: $\mathsf{highestVerified}_{p}\leftarrow 0pt(\mathsf{blockId})$