# A kernel formula for regularized Wasserstein proximal operators

Wuchen Li<EMAIL_ADDRESS>Department of Mathematics, University of
South Carolina, Columbia  ,  Siting Liu<EMAIL_ADDRESS>Department of
Mathematics, University of California, Los Angeles  and  Stanley Osher
<EMAIL_ADDRESS>Department of Mathematics, University of California, Los
Angeles

###### Abstract.

We study a class of regularized proximal operators in Wasserstein-2 space. We
derive their solutions by kernel integration formulas. We obtain the
Wasserstein proximal operator using a pair of forward-backward partial
differential equations consisting of a continuity equation and a Hamilton-
Jacobi equation with a terminal time potential function and an initial time
density function. Following [14, 23], we regularize the PDE pair by adding
forward and backward Laplacian operators. We apply Hopf-Cole type
transformations to rewrite these regularized PDE pairs into forward-backward
heat equations. We then use the fundamental solution of the heat equation to
represent the regularized Wasserstein proximal with kernel integral formulas.
Numerical examples show the effectiveness of kernel formulas in approximating
the Wasserstein proximal operator.

###### Key words and phrases:

Wasserstein proximal operators; Hopf-Cole type transformations; Schrödinger
bridge systems; Heat kernels.

W. Li is supported by AFOSR MURI FA9550-18-1-0502, AFOSR YIP award 2023, and
NSF RTG: 2038080. S. Liu and S. Osher thank the funding from AFOSR MURI
FA9550-18-1-0502 and ONR grants: N00014-18-1-2527, N00014-20-1-2093, and
N00014-20-1-2787.

##  1\. Introduction

Proximal operators are essential tools in optimization. Recently, proximal
operators in probability space equipped with the Wasserstein-2 metric have
shown to be useful in scientific computing [20] and machine learning [4, 21].
The proximal operator in Wasserstein-2 space is called the Wasserstein
proximal operator [1]. An interesting example is the Wasserstein proximal
operator of the Kullback–Leibler (KL) divergence, known as the JKO (Jordan-
Kinderlehrer-Otto) scheme [15]. This has been used to approximate the
Wasserstein gradient flow as a backward Euler scheme in time discretizations.

However, computing the Wasserstein proximal operator requires an optimization
procedure. One has to develop an optimization step to compute or approximate
Wasserstein metrics and energy functionals. This paper proposes an alternative
approach to approximate the Wasserstein proximal operator. We use an optimal
control formulation of the Wasserstein proximal operator, whose minimizer
forms a pair of forward-backward partial differential equations, including
continuity and Hamilton-Jacobi equations. We add forward-backward Laplacian
operators into the PDE system as a regularization. Applying Hopf-Cole type
transformations enables us to rewrite the PDE system into forward-backward
heat equations. Using the fundamental solution of two heat equations, we write
the regularized Wasserstein proximal of linear energy explicitly with a simple
kernel formula. We apply the same idea to the regularized Wasserstein proximal
of nonlinear energy. This turns into a nonlinear integral equation, which can
be solved by simple fixed-point iteration methods.

We now present the approximation of Wasserstein proximal of linear energy
below. Given a probability density function $\rho_{0}$ with the finite second
moment, a bounded potential function $V\in C^{1}(\mathbb{R}^{d})$, and a
scalar constant $T>0$, consider the Wasserstein proximal operator of the
linear energy below:

$\rho_{T}:=\mathrm{WProx}_{T\mathcal{V}}(\rho_{0}):=\arg\min_{q\in\mathcal{P}_{2}(\mathbb{R}^{d})}\quad\int_{\mathbb{R}^{d}}V(x)q(x)dx+\frac{\mathcal{W}(\rho_{0},q)^{2}}{2T}.$

where $\mathcal{W}(\rho_{0},q)$ is the Wasserstein-2 distance between
$\rho_{0}$ and $q$, and the minimization is taken among all probability
density functions $q$ with the finite second moment. We denote the minimizer
$\rho_{T}=q$ as the Wasserstein proximal operator. According to the Benamou-
Brenier formula [3] and simple derivations in section 2, the Wasserstein
proximal operator forms an optimal control problem, whose minimizer satisfies
a forward-backward PDE system:

$\left\\{\begin{aligned}
&\partial_{t}\rho(t,x)+\nabla\cdot\big{(}\rho(t,x)\nabla_{x}\Phi(t,x)\big{)}=0,\\\
&\partial_{t}\Phi(t,x)+\frac{1}{2}\|\nabla_{x}\Phi(t,x)\|^{2}=0,\\\
&\rho(0,x)=\rho_{0}(x),\quad\Phi(T,x)=-V(x).\end{aligned}\right.$ (1)

Here $t\in[0,T]$, and $\rho_{T}$ satisfies the Wasserstein proximal operator
of linear energy.

In this paper, motivated by regularized proximal operators in Euclidean space
[14, 23], we study a regularized PDE system of equation (1). For a constant
scalar $\beta>0$, we have

$\left\\{\begin{aligned}
&\partial_{t}\rho(t,x)+\nabla\cdot\big{(}\rho(t,x)\nabla_{x}\Phi(t,x)\big{)}=\beta\Delta_{x}\rho(t,x),\\\
&\partial_{t}\Phi(t,x)+\frac{1}{2}\|\nabla_{x}\Phi(t,x)\|^{2}=-\beta\Delta_{x}\Phi(t,x),\\\
&\rho(0,x)=\rho_{0}(x),\quad\Phi(T,x)=-V(x).\end{aligned}\right.$ (2)

By applying Hopf-Cole type transformations, we demonstrate that equation (2)
has the solution below:

$\left\\{\begin{aligned}
&\rho(t,x)=(G_{T-t}*e^{-\frac{V}{2\beta}})(x)\cdot(G_{t}*\frac{\rho_{0}}{G_{T}*e^{-\frac{V}{2\beta}}})(x),\\\
&\Phi(t,x)=2\beta\log(G_{T-t}*e^{-\frac{V}{2\beta}})(x).\end{aligned}\right.$

where $*$ is a convolution operator and $G_{t}$ is the scaled heat kernel
denoted as

$G_{t}(x,y):=\frac{1}{\sqrt{(4\pi\beta t)^{d}}}e^{-\frac{\|x-y\|^{2}}{4\beta
t}}.$

In particular, we obtain an integral representation for the terminal density
function:

$\rho(T,x)=\int_{\mathbb{R}^{d}}K(x,y)\rho(0,y)dy,$ (3)

where $K\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ is a
kernel function

$K(x,y):=\frac{e^{-\frac{1}{2\beta}(V(x)+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(z)+\frac{\|z-y\|^{2}}{2T})}dz}.$

For a fixed variable $y\in\mathbb{R}^{d}$, the kernel function $K(x,y)$ is a
Gibbs distribution or softmax function of variable $x$ with constant
$\frac{1}{2\beta}$ and function $V(x)+\frac{1}{2T}\|x-y\|^{2}$. Formula (3) is
a kernel integration representation of the regularized Wasserstein proximal
operator. It could be useful in approximating or computing high-dimensional
sampling problems; see previous studies in [14, 23].

Wasserstein proximal operators have been widely studied [1]. The regularized
Wasserstein proximal dynamics (2) and their Hopf-Cole type transformations
[22] have been widely studied in Schrödinger bridge systems [8, 25, 26] and
Schrödinger equations [5, 22]; see also generalized Hopf-Cole type
transformations [18]. In particular, there are Schrödinger-Follermer
diffusions [11], which are closely related to the equation system (2). We also
remark that the optimal control formulation of the Wasserstein-proximal
operator is a variational problem in potential mean-field games; see [16]. It
has been used in studying and computing particular classes of mean-field
control and mean-field games [12, 13]. Compared to all the above studies, we
study Schrödinger bridge systems with different boundary conditions. It
contains a given initial time density function and a terminal time potential
function, different from fixed initial and terminal time density functions as
in Schrödinger bridge systems. This allows us to obtain a closed-form kernel
integration update, at least for regularized Wasserstein proximal operators of
linear energies. For nonlinear potential energies, our kernel formula also
provides an iterative update to compute Wasserstein proximal operators.

The paper is organized as follows. We introduce Wasserstein proximal operators
of linear energies, their diffusion regularizations, and minimization systems
in section 2. In section 3, we derive the kernel representation of regularized
Wasserstein proximal of linear energies. Finally, we generalize the kernel
formulation for Wasserstein proximal operators of nonlinear energies in
section 4. Numerical experiments of proposed kernel functions are presented in
section 5.

##  2\. Regularized Wasserstein proximal operators of linear energies

In this section, we study a class of mean-field control problems that lead to
regularized proximal operators of linear energies in Wasserstein-2 space. We
derive the minimizing equations, which is a forward-backward PDE system.

###  2.1. Wasserstein proximal operators of linear energies

Consider a linear energy functional

$\mathcal{V}(\rho)=\int_{\mathbb{R}^{d}}V(x)\rho(x)dx,$

where $V\in C^{1}(\mathbb{R}^{d})$ is a given function. Denote a terminal time
$T>0$ and $\rho_{0}\in\mathcal{P}_{2}(\mathbb{R}^{d})$, where
$\mathcal{P}_{2}(\mathbb{R}^{d})$ is the probability density set with finite
second moment. Consider the proximal operator of a linear energy in
Wasserstein-2 space.

$\rho_{T}:=\mathrm{WProx}_{T\mathcal{V}}(\rho_{0}):=\arg\min_{q\in\mathcal{P}_{2}(\mathbb{R}^{d})}\quad\mathcal{V}(q)+\frac{\mathcal{W}(\rho_{0},q)^{2}}{2T}.$
(4)

Here $\mathcal{W}$ denotes the Wasserstein-2 distance between two densities
$\rho^{0}$ and $\rho$; see [1, 24]. Recall that the Wasserstein-2 distance can
be recast as an optimal control problem, known as Benamou-Brenier formula [3].
Consider

$\frac{\mathcal{W}(\rho_{0},q)^{2}}{2T}:=\inf_{\rho,v,\rho_{T}}\quad\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{1}{2}\|v(t,x)\|^{2}\rho(t,x)dxdt,$

where the minimizer is taken among all vector fields
$v\colon[0,T]\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, density functions
$\rho\colon[0,T)\times\mathbb{R}^{d}\rightarrow\mathbb{R}$, such that

$\partial_{t}\rho(t,x)+\nabla\cdot(\rho(t,x)v(t,x))=0,\quad\rho(0,x)=\rho_{0}(x),\quad\rho(T,x)=q(x).$

Wasserstein proximal operators are useful in designing sampling algorithms.
However, the Wasserstein proximal operator (4) does not have a closed-form
update. One needs to apply numerical methods to compute the variational
problem (4).

###  2.2. Regularized Wasserstein proximal operators of linear energies

In this subsection, we consider a regularized Wasserstein proximal operator,
which adds a diffusive term to the continuity equation of the Benamou-Brenier
formula. This regularization forms an interesting mean-field control problem.
We then derive the related minimizing system with initial-terminal conditions.
In the next section, we demonstrate that this minimizing system has a closed-
form kernel representation.

######  Definition 1.

Let $\beta>0$ be a scalar, and $\|\cdot\|$ is the Euclidean norm. Consider the
following mean-field control problem:

$\inf_{\rho,v,q}\quad\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{1}{2}\|v(t,x)\|^{2}\rho(t,x)dxdt+\int_{\mathbb{R}^{d}}V(x)q(x)dx,$
(5)

where the minimizer is taken among all drift vector fields
$v\colon[0,T]\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, density functions
$\rho\colon[0,T)\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ and terminal time
density function $q\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$, such that

$\partial_{t}\rho(t,x)+\nabla\cdot(\rho(t,x)v(t,x))=\beta\Delta\rho(t,x),\quad\rho(0,x)=\rho_{0}(x),\quad\rho(T,x)=q(x).$

We denote the regularized proximal operator as

$\rho_{T}:=\mathrm{WProx}_{T\mathcal{V},\beta}(\rho_{0}),$

where $\rho_{T}$ is the solution for the density function in the variational
problem (5) at time $t=T$.

######  Remark 1.

We note that when $\beta=0$, variational problem (5) is the minimization
problem (4). We add a diffusion into the continuity equation in the
variational problem (5). This forms the regularized Wasserstein proximal
operator.

We next derive the minimization system for mean-field control problem (5).

######  Proposition 2 (Regularized Wasserstein proximal dynamics).

There exists a Lagrange multiplier function
$\Phi\colon[0,T]\times\mathbb{R}^{d}\rightarrow\mathbb{R}$, such that
$(\rho,\Phi)$ satisfies the following forward-backward PDE system.

$\left\\{\begin{aligned}
&\partial_{t}\rho(t,x)+\nabla\cdot\big{(}\rho(t,x)\nabla_{x}\Phi(t,x)\big{)}=\beta\Delta_{x}\rho(t,x),\\\
&\partial_{t}\Phi(t,x)+\frac{1}{2}\|\nabla_{x}\Phi(t,x)\|^{2}=-\beta\Delta_{x}\Phi(t,x),\\\
&\rho(0,x)=\rho_{0}(x),\quad\Phi(T,x)=-V(x).\end{aligned}\right.$ (6)

Here the time variable satisfies $t\in[0,T]$, $\rho(t,x)$ is the density
function, and $\Phi(t,x)$ is the potential function. Equation system (6)
consists of a forward-time Fokker-Planck equation and a backward-time viscous
Hamilton-Jacobi equation (Burgers’ equation). And the terminal time density
function is the regularized Wasserstein proximal density:

$\rho(T,x)=q(x)=\mathrm{WProx}_{T\mathcal{V},\beta}(\rho_{0}).$

###### Proof.

Denote a Lagrange multiplier function $\Phi$. Consider the following saddle
point problem

$\inf_{\begin{subarray}{c}\rho,v,\rho_{T}\end{subarray}}\sup_{\Phi}~{}\mathcal{L}(\rho,v,\rho_{T},\Phi),$

where

$\begin{split}\mathcal{L}(\rho,v,\rho_{T},\Phi):=&\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{1}{2}\|v(t,x)\|^{2}\rho(t,x)dxdt+\int_{\mathbb{R}^{d}}V(x)\rho(T,x)dx\\\
&+\int_{0}^{1}\int_{\mathbb{R}^{d}}\Phi(t,x)\Big{(}\partial_{t}\rho(t,x)+\nabla\cdot(\rho(t,x)v(t,x))-\beta\Delta\rho(t,x)\Big{)}dxdt\\\
=&\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{1}{2}\|v(t,x)\|^{2}\rho(t,x)dxdt+\int_{\mathbb{R}^{d}}V(x)\rho(T,x)dx\\\
&+\int_{\mathbb{R}^{d}}\Phi(T,x)\rho(T,x)dx-\int_{\mathbb{R}^{d}}\Phi(0,x)\rho(0,x)dx\\\
&+\int_{0}^{1}\int_{\mathbb{R}^{d}}\Big{(}-\partial_{t}\Phi(t,x)\rho(t,x)-(\nabla\Phi(t,x),v(t,x))\rho(t,x)-\beta\Phi(t,x)\Delta\rho(t,x)\Big{)}dxdt.\end{split}$

The saddle point system satisfies

$\left\\{\begin{aligned} &\frac{\delta}{\delta v}\mathcal{L}=0,\\\
&\frac{\delta}{\delta\Phi}\mathcal{L}=0,\\\
&\frac{\delta}{\delta\rho}\mathcal{L}=0,\\\
&\frac{\delta}{\delta\rho_{T}}\mathcal{L}=0.\end{aligned}\right.\quad\Rightarrow\quad\left\\{\begin{aligned}
&\rho(v-\nabla\Phi)=0,\\\ &\partial_{t}\rho+\nabla\cdot(\rho
v)-\beta\Delta\rho=0,\\\ &\frac{\|v\|^{2}}{2}-\partial_{t}\Phi-\nabla\Phi\cdot
v-\beta\Delta\Phi=0\\\ &\Phi(T,x)+V(x)=0.\end{aligned}\right.$

Substituting $v=\nabla\Phi$ into the third equality, we derive two PDEs (6).
Thus, we denote $q(x)=\rho(T,x)$. ∎

######  Remark 2.

We repeat that $\rho_{T}=\mathrm{WProx}_{T\mathcal{V},\beta}(\rho_{0})$, where
$\rho_{T}(x)=\rho(T,x)$ represents the density function at the terminal time
$t=T$ in PDE system (6).

##  3\. Kernel formulation

In this section, we derive $\rho_{T}$ with a kernel function (14). We solve a
pair of forward-backward PDE system involving a viscous Hamilton-Jacobi
equation with a fixed terminal time boundary condition. By using a Hopf-Cole
type transformation, we rewrite the PDEs into forward-backward heat equations
with nonlinear initial-terminal time conditions. Thus we solve the original
PDE system (6).

######  Proposition 3 (Hopf-Cole type transformations).

Define a pair of variables $(\eta,\hat{\eta})$ as

$\eta(t,x)=e^{\frac{\Phi(t,x)}{2\beta}},\quad\hat{\eta}(t,x)=\rho(t,x)e^{-\frac{\Phi(t,x)}{2\beta}}.$
(7)

I.e.,

$\Phi(t,x)=2\beta\log\eta(t,x),\quad\rho(t,x)=\eta(t,x)\hat{\eta}(t,x).$

Then equation (6) in term of $(\eta,\hat{\eta})$ satisfies forward-backward
heat equations with a nonlinear initial-terminal time boundary condition:

$\left\\{\begin{aligned}
&\partial_{t}\hat{\eta}(t,x)=\beta\Delta_{x}\hat{\eta}(t,x),\\\
&\partial_{t}\eta(t,x)=-\beta\Delta_{x}\eta(t,x),\\\
&\eta(0,x)\hat{\eta}(0,x)=\rho_{0}(x),\quad\eta(T,x)=e^{\frac{\Phi(T,x)}{2\beta}}=e^{-\frac{V(x)}{2\beta}}.\end{aligned}\right.$
(8)

###### Proof.

The proof follows from classical calculations in Hopf-Cole type
transformations. For completeness of paper, we present the derivation of
forwrad-backward heat equations (8). Denote
$\eta(t,x)=e^{\frac{\Phi(t,x)}{2\beta}}$. Then

$\partial_{t}\eta=\partial_{t}(e^{\frac{\Phi(t,x)}{2\beta}})=\frac{1}{2\beta}e^{\frac{\Phi}{2\beta}}\partial_{t}\Phi.$

And

$\begin{split}\Delta\eta=&\nabla\cdot(\nabla\eta)=\nabla\cdot(\frac{1}{2\beta}e^{\frac{\Phi}{2\beta}}\nabla\Phi)\\\
=&\frac{1}{2\beta}(\nabla
e^{\frac{\Phi}{2\beta}},\nabla\Phi)+\frac{1}{2\beta}e^{\frac{\Phi}{2\beta}}\Delta\Phi\\\
=&\frac{1}{(2\beta)^{2}}e^{\frac{\Phi}{2\beta}}\|\nabla\Phi\|^{2}+\frac{1}{2\beta}e^{\frac{\Phi}{2\beta}}\Delta\Phi\\\
=&\frac{1}{2\beta^{2}}e^{\frac{\Phi}{2\beta}}\Big{(}\frac{1}{2}\|\nabla\Phi\|^{2}+\beta\Delta\Phi\Big{)}.\end{split}$

From the viscous Hamilton-Jacobi equation (6), we have

$\partial_{t}\eta+\beta\Delta\eta=0.$

Denote $\hat{\eta}(t,x)=\rho(t,x)e^{-\frac{\Phi(t,x)}{2\beta}}$. Then

$\begin{split}\partial_{t}\hat{\eta}=&e^{-\frac{\Phi}{2\beta}}\Big{\\{}\partial_{t}\rho-\rho\frac{1}{2\beta}\partial_{t}\Phi\Big{\\}}.\end{split}$

And

$\begin{split}\nabla\hat{\eta}=&\nabla(\rho
e^{-\frac{\Phi}{2\beta}})=\nabla\rho e^{-\frac{\Phi}{2\beta}}+\rho\nabla
e^{-\frac{\Phi}{2\beta}}\\\ =&\nabla\rho
e^{-\frac{\Phi}{2\beta}}-\frac{1}{2\beta}\rho\nabla\Phi
e^{-\frac{\Phi}{2\beta}}.\end{split}$

Hence

$\begin{split}\Delta\hat{\eta}=&\nabla\cdot(\nabla\hat{\eta})=\nabla\cdot(\nabla\rho
e^{-\frac{\Phi}{2\beta}}-\frac{1}{2\beta}\rho\nabla\Phi
e^{-\frac{\Phi}{2\beta}})\\\ =&\Delta\rho
e^{-\frac{\Phi}{2\beta}}+(\nabla\rho,\nabla
e^{-\frac{\Phi}{2\beta}})-\frac{1}{2\beta}(\nabla\rho,\nabla\Phi)e^{-\frac{\Phi}{2\beta}}-\frac{1}{2\beta}\rho\Delta\Phi
e^{-\frac{\Phi}{2\beta}}-\frac{1}{2\beta}\rho(\nabla\Phi,\nabla
e^{-\frac{\Phi}{2\beta}})\\\ =&\Delta\rho
e^{-\frac{\Phi}{2\beta}}-\frac{1}{\beta}(\nabla\rho,\nabla\Phi)e^{-\frac{\Phi}{2\beta}}-\frac{1}{2\beta}\rho\Delta\Phi
e^{-\frac{\Phi}{2\beta}}+\frac{1}{(2\beta)^{2}}\rho\|\nabla\Phi\|^{2}\\\
=&e^{-\frac{\Phi}{2\beta}}\Big{\\{}\Delta\rho-\frac{1}{\beta}\nabla\cdot(\rho\nabla\Phi)+\frac{1}{2\beta}\rho\Delta\Phi+\frac{1}{4\beta^{2}}\rho\|\nabla\Phi\|^{2}\Big{\\}}\\\
=&\frac{1}{\beta}e^{-\frac{\Phi}{2\beta}}\Big{\\{}\partial_{t}\rho-\frac{1}{2\beta}\rho\partial_{t}\Phi\Big{\\}},\end{split}$

where we use the fact
$\nabla\cdot(\rho\nabla\Phi)=(\nabla\rho,\nabla\Phi)+\rho\Delta\Phi$. Hence we
have

$\partial_{t}\hat{\eta}-\beta\Delta\hat{\eta}=0.$

∎

We next apply the heat kernel to represent the solution of PDE system (8).
From equation (7), we can derive solutions $\rho(t,x)$ and $\Phi(t,x)$ in
terms of $\rho_{0}(x)$ and $V(x)$.

######  Proposition 4 (Kernel solutions).

Denote a scaled heat kernel function:

$G_{t}(x,y):=\frac{1}{\sqrt{(4\pi\beta t)^{d}}}e^{-\frac{\|x-y\|^{2}}{4\beta
t}},\quad t\in(0,T].$

Assume that

$\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(z)+\frac{\|z-y\|^{2}}{2T})}dz<+\infty.$

Then the following solutions hold.

$\left\\{\begin{aligned}
&\rho(t,x)=(G_{T-t}*e^{-\frac{V}{2\beta}})(x)\cdot(G_{t}*\frac{\rho_{0}}{G_{T}*e^{-\frac{V}{2\beta}}})(x),\\\
&\Phi(t,x)=2\beta\log(G_{T-t}*e^{-\frac{V}{2\beta}})(x).\end{aligned}\right.$
(9)

So

$\rho(t,x)=\frac{1}{{(4\pi\beta\frac{t(T-t)}{T}})^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}(V(z)+\frac{\|x-z\|^{2}}{2(T-t)}+\frac{\|x-y\|^{2}}{2t})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(\tilde{y})+\frac{\|y-\tilde{y}\|^{2}}{2T})}d\tilde{y}}\rho(0,y)dydz,$
(10)

and

$\Phi(t,x)=2\beta\log\Big{(}\int_{\mathbb{R}^{d}}\frac{1}{(4\pi\beta(T-t))^{\frac{d}{2}}}e^{-\frac{1}{2\beta}(V(y)+\frac{\|x-y\|^{2}}{2(T-t)})}dy\Big{)}.$
(11)

###### Proof.

Denote $\eta_{t}(x)=\eta(t,x)$. From $\partial_{t}\eta+\beta\Delta\eta=0$, we
have

$\displaystyle\eta(t,x)=(G_{T-t}*\eta_{T})(x)=(G_{T-t}*e^{-\frac{V}{2\beta}})(x).$
(12)

When $t=0$, we have

$\eta(0,x)=(G_{T}*\eta_{T})(x)=(G_{T}*e^{-\frac{V}{2\beta}}).$

From the initial time boundary condition
$\rho_{0}(x)=\eta(0,x)\hat{\eta}(0,x)$, we have

$\hat{\eta}(0,x)=\frac{\rho(0,x)}{\eta(0,x)}=\frac{\rho_{0}(x)}{(G_{T}*\eta_{T})(x)}=\frac{\rho_{0}(x)}{(G_{T}*e^{-\frac{V}{2\beta}})(x)}.$

And from $\partial_{t}\hat{\eta}-\beta\Delta\hat{\eta}=0$, we have

$\hat{\eta}(t,x)=(G_{t}*\hat{\eta}_{0})(x)=(G_{t}*\frac{\rho_{0}}{G_{T}*e^{-\frac{V}{2\beta}}})(x).$
(13)

Plugging solution (12) and (13) into Hopf-Cole transformation (7), we obtain

$\rho(t,x)=\eta(t,x)\cdot\hat{\eta}(t,x)=(G_{T-t}*e^{-\frac{V}{2\beta}})(x)\cdot(G_{t}*\frac{\rho_{0}}{G_{T}*e^{-\frac{V}{2\beta}}})(x),$

and

$\Phi(t,x)=2\beta\log\eta(t,x)=2\beta\log(G_{T-t}*e^{-\frac{V}{2\beta}})(x).$

∎

In particular, we represent the solution $\rho(T,x)$ by an integral kernel
formula.

######  Proposition 5.

$\rho(T,x)=\int_{\mathbb{R}^{d}}K(x,y,\beta,T,V)\rho(0,y)dy,$

where
$K\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}_{+}\times\mathbb{R}_{+}\times
C^{1}(\mathbb{R}^{d})\rightarrow\mathbb{R}$ is the kernel function

$K(x,y,\beta,T,V):=\frac{e^{-\frac{1}{2\beta}(V(x)+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(z)+\frac{\|z-y\|^{2}}{2T})}dz}.$
(14)

###### Proof.

We apply $t=T$ in update (9) for the density function. ∎

######  Remark 3.

One can check that $\rho(t,x)$ in formula (10) is a probability density
function. I.e., $\rho(t,x)\geq 0$, and $\int_{\mathbb{R}^{d}}\rho(t,x)dx=1$.
The fact that $\int_{\mathbb{R}^{d}}\rho(t,x)dx$ is independent of $t$ follows
the first equation in (6). In detail, formula (10) can be recast as

$\rho(t,x)=\frac{1}{{(4\pi\beta\frac{t(T-t)}{T}})^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}(V(z)+\frac{\|y-z\|^{2}}{2T})}e^{-\frac{1}{2\beta}\frac{\|x-\frac{tz+(T-t)y}{T}\|^{2}}{2\frac{(T-t)t}{T}}}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(\tilde{y})+\frac{\|y-\tilde{y}\|^{2}}{2T})}d\tilde{y}}\rho(0,y)dydz.$

From this formula, we directly observe that $\rho(t,x)$ is a probability
density function.

######  Remark 4.

We remark that $\Phi(t,x)$ in equation (11) is a solution for the viscous
Hamilton-Jacobi equation, and
$\nabla_{x}\Phi(0,x)=2\beta\nabla_{x}\log(G_{T}*e^{-\frac{V}{2\beta}})(x)$
approximates the proximal operator of $V(x)$ in Euclidean space; see [14, 23].

######  Remark 5.

We remark that Hopf-Cole type transformations have been used in studying
Schrödinger bridge systems [8, 18, 19, 25, 26]. One can construct Schrödinger-
Föllmer diffusion processes [11], which have applications in global
optimization problems [10]. However, we are using different initial-terminal
boundary conditions in the usual Schrödinger bridge systems with fixed initial
and terminal densities. The proposed system (6) has fully closed-form
solutions in both density function $\rho$ and potential function $\Phi$. The
regularized Wasserstein proximal of linear energies have closed-form
representations. Our approach can also work for nonlinear energies. See
equations (16), (17) in the next section.

We also present an analytical example of the integral kernel formula in
Proposition 5.

######  Example 1.

Consider

$V(x)=\frac{1}{2}\|x-x_{0}\|^{2},$

where $x_{0}\in\mathbb{R}^{d}$ is a fixed vector. From (11), we have

$\begin{split}\Phi(t,x)=&2\beta\log\Big{(}\int_{\mathbb{R}^{d}}\frac{1}{(4\pi\beta(T-t))^{\frac{d}{2}}}e^{-\frac{1}{2\beta}(\frac{\|y-x_{0}\|^{2}}{2}+\frac{\|x-y\|^{2}}{2(T-t)})}dy\Big{)}\\\
=&\beta d\log\frac{1}{T-t+1}-\frac{\|x-x_{0}\|^{2}}{2(T-t+1)}.\end{split}$

From (10), we have

$\begin{split}\rho(t,x)=&\frac{1}{{(4\pi\beta\frac{t(T-t)}{T}})^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}(\frac{1}{2}\|z-x_{0}\|^{2}+\frac{\|x-z\|^{2}}{2(T-t)}+\frac{\|x-y\|^{2}}{2t})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(\frac{1}{2}\|\tilde{y}-x_{0}\|^{2}+\frac{\|y-\tilde{y}\|^{2}}{2T})}d\tilde{y}}\rho_{0}(y)dydz\\\
=&\frac{1}{{(4\pi\beta\frac{t(T-t+1)}{T+1}})^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}e^{-\frac{1}{4\beta\frac{t(T-t+1)}{T+1}}(x-\frac{\frac{y}{t}+\frac{x_{0}}{T-t+1}}{\frac{1}{t}+\frac{1}{T-t+1}})^{2}}\rho_{0}(y)dy.\end{split}$

From (14), we obtain

$\begin{split}\rho(T,x)=&\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}(\frac{1}{2}\|x-x_{0}\|^{2}+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(\frac{1}{2}\|z-x_{0}\|^{2}+\frac{\|z-y\|^{2}}{2T})}dz}\rho_{0}(y)dy\\\
=&\frac{1}{{(4\pi\beta\frac{T}{T+1}})^{\frac{d}{2}}}\int_{\mathbb{R}^{d}}e^{-\frac{1}{4\beta\frac{T}{T+1}}(x-\frac{\frac{y}{T}+x_{0}}{\frac{1}{T}+1})^{2}}\rho_{0}(y)dy.\end{split}$

##  4\. Regularized Wasserstein proximal operators of general energies

In this section, we study the regularized Wasserstein proximal operator of
general energy functionals.

Consider a functional
$\mathcal{F}\colon\mathcal{P}_{2}(\mathbb{R}^{d})\rightarrow\mathbb{R}$. We
study the proximal operator of energy $\mathcal{F}$ in Wasserstein-2 space.

$\rho_{T}=\mathrm{WProx}_{\mathcal{F}}(\rho_{0}):=\arg\min_{q\in\mathcal{P}_{2}(\mathbb{R}^{d})}\quad\mathcal{F}(q)+\frac{\mathcal{W}(\rho_{0},q)^{2}}{2T}.$

Computing the Wasserstein proximal operator usually requires an optimization
step. Instead, we study a regularized optimal control problem.

######  Definition 6.

Denote $\beta>0$ as a scalar. Consider the following mean-field control
problem:

$\inf_{\rho,v,q}\quad\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{1}{2}\|v(t,x)\|^{2}\rho(t,x)dxdt+\mathcal{F}(q),$
(15)

where the minimizer is taken among all vector fields
$v\colon[0,T]\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, density functions
$\rho\colon[0,T)\times\mathbb{R}^{d}\rightarrow\mathbb{R}$ and terminal time
density function $q\colon\mathbb{R}^{d}\rightarrow\mathbb{R}$, such that

$\partial_{t}\rho(t,x)+\nabla\cdot(\rho(t,x)v(t,x))=\beta\Delta\rho(t,x),\quad\rho(0,x)=\rho_{0}(x),\quad\rho(T,x)=q(x).$

We denote the regularized proximal operator as

$\rho_{T}:=\mathrm{WProx}_{T\mathcal{F},\beta}(\rho_{0}),$

where $\rho_{T}$ is the solution of density function in variational problem
(15) at time $t=T$.

We can also represent the approximate proximal operator in a kernel
representation.

######  Proposition 7.

Denote the $L^{2}$ first variation of functional $\mathcal{F}$ as

$\frac{\delta}{\delta\rho}\mathcal{F}(\rho)(x)=F(x,\rho).$

Then

$\rho(T,x)=\int_{\mathbb{R}^{d}}K(x,y,\beta,T,\rho_{T})\rho(0,y)dy,$ (16)

where we define a kernel function
$K\colon\mathbb{R}^{d}\times\mathbb{R}^{d}\times\mathbb{R}_{+}\times\mathbb{R}_{+}\times\mathcal{P}_{2}(\mathbb{R}^{d})\rightarrow\mathbb{R}$
as

$K(x,y,\beta,T,\rho_{T}):=\frac{e^{-\frac{1}{2\beta}(F(x,\rho_{T})+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(F(z,\rho_{T})+\frac{\|z-y\|^{2}}{2T})}dz}.$
(17)

###### Proof.

The proof follows from those in sections 2 and 3. We only need to replace
$V(x)$ by $\frac{\delta}{\delta\rho}\mathcal{F}(\rho)(x)=F(x,\rho)$. ∎

######  Remark 6.

We remark that for a general functional $\mathcal{F}(\rho)$, the kernel
formula $K$ depends on $\rho_{T}$. We no longer have an explicit expression of
$\rho_{T}$. Instead, we make use of equation (16).

###  4.1. Examples

In this section, we present some examples of kernel representations. Consider
an energy functional

$\mathcal{F}(\rho)=\int_{\mathbb{R}^{d}}V(x)\rho(x)dx+\frac{1}{2}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}W(x-y)\rho(x)\rho(y)dxdy+\int_{\mathbb{R}^{d}}U(\rho(x))dx,$

where $V\in C^{1}(\mathbb{R}^{d};\mathbb{R})$, $W\in
C^{1}(\mathbb{R}^{d};\mathbb{R})$ is an interaction kernel function, with
$W(z)=W(-z)$, $z\in\mathbb{R}^{d}$, and $U\in
C^{1}(\mathbb{R}^{d};\mathbb{R})$ is an internal potential function. The
$L^{2}$ first variation of $\mathcal{F}(\rho)$ satisfies

$F(x,\rho)=\frac{\delta}{\delta\rho}\mathcal{F}(\rho)(x)=V(x)+(W*\rho)(x)+U^{\prime}(\rho(x)).$

Thus the kernel function (17) satisfies

$K(x,y,\beta,T,\rho_{T}):=\frac{e^{-\frac{1}{2\beta}(V(x)+(W*\rho_{T})(x)+U^{\prime}(\rho_{T}(x))+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(V(z)+(W*\rho_{T})(z)+U^{\prime}(\rho_{T}(z))+\frac{\|z-y\|^{2}}{2T})}dz}.$

And the regularization Wasserstein proximal equation forms

$\rho_{T}(x)=\int_{\mathbb{R}^{d}}K(x,y,\beta,T,\rho_{T})\rho_{0}(y)dy.$

We next present some examples for equation (16) and kernel function (17).

######  Example 2.

Let $V=U=0$. Then the kernel function (17) satisfies

$K(x,y,\beta,T,\rho_{T}):=\frac{e^{-\frac{1}{2\beta}((W*\rho_{T})(x)+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}((W*\rho_{T})(z)+\frac{\|z-y\|^{2}}{2T})}dz}.$

And the regularized Wasserstein proximal equation satisfies

$\rho_{T}(x)=\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}((W*\rho_{T})(x)+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}((W*\rho_{T})(z)+\frac{\|z-y\|^{2}}{2T})}dz}\rho_{0}(y)dy.$

######  Example 3.

Let $V=W=0$. Then the kernel function (17) satisfies

$K(x,y,\beta,T,\rho_{T}):=\frac{e^{-\frac{1}{2\beta}(U^{\prime}(\rho_{T}(x))+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(U^{\prime}(\rho_{T}(z))+\frac{\|z-y\|^{2}}{2T})}dz}.$

And the regularized Wasserstein proximal equation satisfies

$\rho_{T}(x)=\int_{\mathbb{R}^{d}}\frac{e^{-\frac{1}{2\beta}(U^{\prime}(\rho_{T}(x))+\frac{\|x-y\|^{2}}{2T})}}{\int_{\mathbb{R}^{d}}e^{-\frac{1}{2\beta}(U^{\prime}(\rho_{T}(z))+\frac{\|z-y\|^{2}}{2T})}dz}\rho_{0}(y)dy.$

##  5\. Numerical Experiments

In this section, we conduct several computational examples to numerically
verify the kernel formulations (14) and (17). We also discuss a fixed point
iteration algorithm that uses the kernel formulation to calculate the
Wasserstein proximal operator of general functionals.

###  5.1. Validation the kernel formulation with optimization method

####  5.1.1. Solve the equivalent variational problem via primal-dual hybrid
gradient (PDHG) method

To numerically verify kernel formulations, we compute the mean-field control
problem (15) via the primal-dual hybrid gradient approach. By introducing the
flux variable $m=\rho v$, we can rewrite the mean-field control problem as the
following constrained optimization problem:

$\inf_{\rho,m,q}\quad\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{\|m(t,x)\|^{2}}{2\rho(t,x)}dxdt+\mathcal{F}(q),$
(18)

such that

$\partial_{t}\rho(t,x)+\nabla\cdot
m(t,x)=\beta\Delta\rho(t,x),\quad\rho(0,x)=\rho_{0}(x),\quad\rho(T,x)=q(x).$

By introducing a Lagrangian multiplier $\Phi$, we write optimization problem
(18) into the following saddle point problem:

$\inf_{\begin{subarray}{c}\rho,m,q\\\ \rho(0,\cdot)=\rho_{0}(\cdot)\\\
\rho(T,\cdot)=q(\cdot)\end{subarray}}\sup_{\Phi}\quad\mathcal{L}(\rho,m,q,\Phi),$
(19)

where

$\begin{split}\mathcal{L}(\rho,m,q,\Phi):=&\quad\int_{0}^{T}\int_{\mathbb{R}^{d}}\frac{\|m(t,x)\|^{2}}{2\rho(t,x)}dxdt+\mathcal{F}(q)\\\
&+\int_{0}^{T}\int_{\mathbb{R}^{d}}\Phi(t,x)\Big{(}\partial_{t}\rho(t,x)+\nabla\cdot
m(t,x)-\beta\Delta\rho(t,x)\Big{)}dxdt.\end{split}$ (20)

Saddle point problem (19) is convex in $(\rho,m,q)$ and concave in $(\Phi)$.
We can directly apply the primal-dual hybrid gradient method (PDHG) [6] to
solve problem (19). The algorithm takes proximal updates in the primal
variables $(\rho,m,q)$ and the dual variables $(\Phi)$ iteratively, with extra
extrapolating steps. For more details on using the PDHG algorithm to solve
mean-field control problems, we refer to [17].

####  5.1.2. Discretization Scheme

For simplicity, we consider a one dimensional finite domain $\Omega=[-b,b]$
with the periodic boundary condition. In the following examples, we set up a
large enough finite spatial domain with density $\rho$ vanishing near the
boundary. We use a uniform mesh for both spatial and time intervals, with
$h_{x}=\frac{2b}{N_{x}},h_{t}=\frac{T}{N_{T}}$, for $N_{x},N_{T}>0$, and
$(t_{l},x_{j})=(lh_{t},jh_{x}-b)$, for $l=0,\cdots,N_{t}$,
$j=0,\cdots,N_{x}-1$. For variables $\rho,\Phi,q$, we denote the following
grid point approximation:

$\displaystyle\rho_{j}^{l}=\rho(t_{l},x_{j}),\;\quad\Phi_{j}^{l}=\Phi(t_{l},x_{j}),\;\quad
q_{j}=q(x_{j}).$

As for the flux variable $m$, we denote

$\displaystyle m_{j}^{l}=[m_{j}^{+,l}+m_{j}^{-,l}],\quad
m_{j}^{+,l}:=\left(m(t_{l},x_{j})\right)^{+},\quad
m_{j}^{-,l}:=-\left(m(t_{l},x_{j})\right)^{-};$
$\displaystyle\|m_{j}^{l}\|^{2}=\left(m_{j}^{+,l}\right)^{2}+\left(m_{j}^{-,l}\right)^{2},\quad\nabla_{x}\cdot
m_{j}^{l}=\frac{m_{j}^{+,l}-m_{j-1}^{+,l}}{h_{x}}+\frac{m_{j+1}^{-,l}-m_{j}^{-,l}}{h_{x}},$

where $u^{+}:=\max(u,0)$ and $u^{-}=u^{+}-u$. We discretize the above
variational problem with the finite difference method and obtain the following
first-order scheme:

$\displaystyle\hat{\mathcal{L}}(\rho,m,\Phi,q)=$ $\displaystyle\quad
h_{t}h_{x}\sum_{\begin{subarray}{c}1\leq l\leq N_{t}\\\ 1\leq j\leq
N_{x}\end{subarray}}\left(\frac{\|m_{j}^{l}\|^{2}}{2\rho_{j}^{l}}\right)+\hat{\mathcal{F}}(q)$
$\displaystyle+h_{t}h_{x}\sum_{\begin{subarray}{c}0\leq l\leq N_{t}-1\\\ 1\leq
j\leq
N_{x}\end{subarray}}\Phi^{l}_{j}\left(\dfrac{\rho^{l+1}_{j}-\rho^{l}_{j}}{h_{t}}+{\nabla_{x}\cdot
m_{j}^{l+1}}-\beta\frac{\rho^{l+1}_{j+1}+\rho^{l+1}_{j-1}-2\rho^{l+1}_{j}}{h_{x}^{2}}\right).$

More specifically, we consider the discretized energy functional
$\hat{\mathcal{F}}$ as below:

$\displaystyle\hat{\mathcal{F}}(q)=h_{x}\sum_{\begin{subarray}{c}1\leq j\leq
N_{x}\end{subarray}}\left(V(x_{j})q_{j}+U\left(q_{j}\right)\right)+\frac{h_{x}^{2}}{2}\sum_{\begin{subarray}{c}1\leq
i\leq N_{x}\\\ 1\leq j\leq
N_{x}\end{subarray}}\left(W(x_{i}-x_{j})q_{i}q_{j}\right).$

Here, we denote $\rho_{M}^{T}(x):=\rho(T,x)$ and use it to compare with the
solution obtained from the kernel formulation.

As for computation using kernel formulation, we use the Riemann sum. Taking
the linear energy functional as an example, i.e.,
$\mathcal{F}(\rho)=\int_{\Omega}V(x)\rho(x)dx$, the kernel function in
equation (14) can be approximated by the following form:

$K(x_{i},y_{j},\beta,T,V)=\frac{e^{-\frac{1}{2\beta}(V(x_{i})+\frac{\|x_{i}-y_{j}\|^{2}}{2T})}}{h_{x}\sum_{\begin{subarray}{c}1\leq
k\leq
N_{x}\end{subarray}}e^{-\frac{1}{2\beta}(V(z_{k})+\frac{\|z_{k}-y_{j}\|^{2}}{2T})}}.$

Hence the solution $\rho(T,x_{i})$ via kernel integral formula can be
expressed as

$\rho(T,x_{i})=h_{x}\sum_{\begin{subarray}{c}1\leq j\leq
N_{x}\end{subarray}}K(x_{i},y_{j},\beta,T,V)\rho(0,y_{j}).$

From now on, we denote $\rho_{K}^{T}(x):=\rho(T,x)$.

####  5.1.3. Example A

In the first example, we consider the regularized Wasserstein proximal
operator of linear energy $\mathcal{F}(\rho)=\int_{\Omega}V(x)\rho(x)dx$. For
example parameters, we have the following setup:

$\displaystyle b=5,T=0.2,\beta=0.25,$ $\displaystyle
V(x)=e^{-\frac{(x+0.25)^{2}}{0.5}},$
$\displaystyle\rho_{0}(x)=\frac{1}{\sigma_{0}\sqrt{2\pi}}e^{-\frac{\left(x-0.25\right)^{2}}{2\sigma_{0}^{2}}},\;\sigma_{0}=0.1.$

By applying different meshes $N_{x},N_{t}$, we record the difference between
$\rho_{M}^{T}$ (obtained via the optimization approach) and $\rho_{K}^{T}$
(obtained via the kernel formula). From Table 1, we observe the consistent
convergence as refining the mesh grid, which suggests that our kernel formula
is precise when the energy functional is of linear form. In Figure 1, we show
the numerical solutions of Example A.

$h_{x}$ | $0.0625$ | $0.05$ | $0.0313$
---|---|---|---
$\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ | $0.0016$ | $0.0011$ | $0.0007$
Table 1. Record of $\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ with different
meshes of Example A. Figure 1. Numerical results for Example A. On the left,
we show the time evolution of $\rho(t,x)$ over the time interval $[0,0.2]$. On
the right, we vary the coefficient $T=0.1,0.2,0.5$ to see how the parameter
$T$ affects the regularized Wasserstein proximal operator and its resulting
density distribution.

####  5.1.4. Example B

We now consider
$\mathcal{F}(\rho)=\frac{1}{2}\int_{\Omega}\int_{\Omega}W(x-y)\rho(x)\rho(y)dxdy$,
where the energy functional is quadratic on $\rho$. Specifically, we have

$\displaystyle b=5,T=0.1,\beta=0.1,$ $\displaystyle
W(x-y)=\lambda_{W}(x-y)^{2},\;\lambda_{W}=0.2,$
$\displaystyle\rho_{0}(x)=\frac{1}{\sigma_{0}\sqrt{2\pi}}e^{-\frac{\left(x-0.5\right)^{2}}{2\sigma_{0}^{2}}},\;\sigma_{0}=0.1.$

With mesh $N_{x}$, we first solve the corresponding variational problem and
obtain $\rho_{M}^{T}$. Then we apply the kernel formulation to obtain

$\displaystyle\rho_{K}^{T}(x)=\int_{\Omega}K(x,y,\beta,T,\rho_{M}^{T})\rho_{0}(y)dy.$

By varying the mesh, we obtained the difference
$\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ converges to $0$ with the order
$O(h_{x})$. See Table 2. This observation suggests that the kernel formulation
could be applied to the computation of Wasserstein proximal of interaction
energy.

$h_{x}$ | $0.0625$ | $0.05$ | $0.0313$
---|---|---|---
$\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ | $6.3e-4$ | $4.6e-4$ | $3.1e-4$
Table 2. Record of $\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ with different
meshes of Example B.

####  5.1.5. Example C

In this example, we consider the energy being the Kullback–Leibler (KL)
divergence, i.e.,
$\mathcal{F}(\rho)=\lambda_{F}\int_{\Omega}\rho(x)\log(\frac{\rho(x)}{\rho_{F}(x)})dx$.
In detail, the example parameters are as follows:

$\displaystyle b=5,T=0.2,\beta=0.1,\lambda_{F}=0.1,$
$\displaystyle\rho_{F}(x)=\frac{1}{\sigma_{F}\sqrt{2\pi}}e^{-\frac{x^{2}}{2\sigma_{F}^{2}}},\;\sigma_{F}=0.4,$
$\displaystyle\rho_{0}(x)=\frac{1}{\sigma_{0}\sqrt{2\pi}}e^{-\frac{\left(x-0.5\right)^{2}}{2\sigma_{0}^{2}}},\;\sigma_{0}=0.2.$

To avoid numerical instability, we also modify the KL divergence with

$\displaystyle\mathcal{F}(\rho)=\lambda_{F}\int_{\Omega}\rho(x)\log(\frac{\rho(x)+\epsilon}{\rho_{F}(x)+\epsilon})dx,\;\epsilon=1e-4.$

Similarly to Example B, we first solve the corresponding mean-field control
problem with solution $\rho_{M}^{T}$. Via kernel formulation, we arrive at
$\rho_{K}^{T}(x)=\int_{\Omega}K(x,y,\beta,T,\rho_{M}^{T})\rho_{0}(y)dy$. By
refining the mesh, we observe the consistent convergence of numerical
solutions. See Table 3. This numerical result also suggests that, with proper
regularization parameters, the kernel formula of the regularized Wasserstein
proximal operator is valid for general functions. We present the regularized
Wasserstein proximal and the time-evolution of $(\rho(t,\cdot),\Phi(t,\cdot))$
in Figure 2.

$h_{x}$ | $0.0625$ | $0.05$ | $0.0313$
---|---|---|---
$\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ | $2.5e-4$ | $1.7e-4$ | $7.8e-5$
Table 3. Record of $\|\rho_{K}^{T}-\rho_{M}^{T}\|_{L^{2}}$ with different
meshes of Example C. Figure 2. Numerical results for Example C. On the left,
we show the time evolution of $\rho(t,x)$ over the time interval $[0,0.2]$. On
the right, we plot the example parameters $\rho_{0},\rho_{F}$, the mean-field
control problem solution $\rho_{M}^{T}$, and the density $\rho_{K}^{T}(x)$
obtained via the kernel formulation.

###  5.2. A fixed-point type iterative approach to compute the regularized
Wasserstein proximal

For general functional $\mathcal{F}(\rho)$, the kernel formulation can be
modified as a fixed point map, i.e.,

$\displaystyle\rho_{itr}^{n}(x)=\int_{\Omega}K(x,y,\beta,T,\rho_{itr}^{n-1})\rho_{0}(y)dy,\quad
n=1,2,...,N.$ (21)

Such an iteration scheme can efficiently calculate the regularized Wasserstein
proximal operator.

We provide a numerical example to show that, with proper regularization
($\beta>0$), the scheme (21) is a fixed point iteration. Moreover, its limit
is the solution to the regularized Wasserstein proximal.

We first consider the regularized Wasserstein proximal from Example C in
section 5.1.5. To apply the fixed point iteration, we fix the mesh size
$h_{x}$ and set $\rho_{itr}^{0}=\rho_{0}$ as the initialization. Then we apply
the scheme (21) via a Riemann summation. To check if the fixed point iteration
limit is the regularized Wasserstein proximal, we compute the scheme (21) with
different mesh $N_{x}$ and compare it with the solution of the corresponding
variational problem. Table 4 suggests that the limit point of the iteration
(21) matches nicely. We also present the iteration details in Figure 3, which
shows the fast convergence of the fixed point iteration.

$h_{x}$ | $0.0625$ | $0.05$ | $0.0313$
---|---|---|---
$\|\rho_{itr}^{20}-\rho_{M}^{T}\|_{L^{2}}$ | $1.2e-2$ | $9.5e-3$ | $6.4e-3$
Table 4. Record of $\|\rho_{itr}^{20}-\rho_{M}^{T}\|_{L^{2}}$ with different
meshes of Example 3 using the fixed-point iteration. Figure 3. Numerical
results for the fixed-point iteration. On the left, we plot the difference in
two adjacent iterations, i.e., $\|\rho_{itr}^{n}-\rho_{itr}^{n-1}\|_{L^{2}}$
for the first $20$ iterations. On the right, we plot some intermediate points
of the iteration process. We observe that at the $5$th iteration, the density
profile is already very close to the limit in the $L^{2}$ norm.

Let us consider another example with
$\mathcal{F}(\rho)=0.5\int_{\Omega}\rho(x)^{2}dx$, and apply the fixed-point
iteration (21). For other parameters, we set

$\displaystyle b=5,T=1,\beta=0.25,$
$\displaystyle\rho_{0}(x)=\frac{1}{\sigma_{0}\sqrt{2\pi}}e^{-\frac{\left(x-0.5\right)^{2}}{2\sigma_{0}^{2}}},\;\sigma_{0}=0.1.$

Numerical results are shown in Figure 4. We also compare the fixed-point
iterations using the kernel formula with the density $\rho_{M}^{T}$ obtained
by solving the corresponding variational problem (18). These solutions match
pretty well after $40$ steps of the fixed-point iteration.

Figure 4. Numerical results for the fixed-point iteration of functional
$\mathcal{F}(\rho)=0.5\int_{\Omega}\rho(x)^{2}dx$. In the left figure, we plot
the difference between two adjacent iterations. In the right figure, we plot
the density profiles of some intermediate iteration processes and observe that
the limit of the fixed point scheme converges to $\rho_{M}^{T}$.

## References

  * [1] L. Ambrosio, N. Gigli and G. Savaré.  Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics ETH Zurich, Birkhauser Verlag, Basel, 2nd ed. 2008.
  * [2] J. Backhoff, G. Conforti, I. Gentil, and C. Leonard.  The mean field Schrödinger problem: ergodic behavior, entropy estimates and functional inequalities.  Probability Theory and Related Fields, 178:475–530, 2020.
  * [3] J.D. Benamou and Y. Brenier.  A Computational Fluid Mechanics Solution to the Monge-Kantorovich Mass Transfer Problem.  Numerische Mathematik, 84(3):3750–393, 2000.
  * [4] E. Bernton.  Langevin Monte Carlo and JKO splitting.  Proceedings of the 31st Conference On Learning Theory, PMLR 75:1777-1798, 2018.
  * [5] T. Bonnemain, T. Gobron, and D. Ullmo.  Lax connection and conserved quantities of quadratic mean field games.  J. Math. Phys, 62, 083302, 2021.
  * [6] A. Chambolle and T. Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  J. Math. Imaging Vision., 40(1):120-145, 2011.
  * [7] P. Chaudhari, A. Oberman, S. Osher, S. Soatto and G. Carlier.  Deep relaxation: partial differential equations for optimizing deep neural networks.  Res Math Sci, 5, 30, 2018.
  * [8] Y. Chen, T. Georgiou, and M. Pavon.  On the Relation Between Optimal Transport and Schrödinger Bridges: A Stochastic Control Viewpoint.  J Optim Theory Appl, 169:671–691, 2016.
  * [9] G. Conforti.  A second order equation for Schrödinger bridges with applications to the hot gas experiment and entropic transportation cost.  Probability Theory and Related Fields, 174, 1–47, 2019.
  * [10] Y. Dai, Y. Jiao, L. Kang, X. Lu, and J. Yang.  Global Optimization via Schrödinger-Föllmer Diffusion.  arXiv:2111.00402, 2021.
  * [11] H. Föllmer.  Random fields and diffusion processes.  In École d’Été de Probabilités de Saint-Flour XV–XVII, 1985–87, volume 1362 of Lecture Notes in Math., pages 101–203. Springer, Berlin, 1988.
  * [12] O. Guéant.  Mean field games equations with quadratic Hamiltonian: a specific approach.  Mathematical Models and Methods in Applied Sciences, Vol. 22, No. 09, 1250022, 2012.
  * [13] O. Guéant, J.M. Lasry, and P.L. Lions.  Mean Field Games and Applications.  In: Paris-Princeton Lectures on Mathematical Finance, 2010.
  * [14] H. Heaton, S.W. Fung, and S. Osher.  Global Solutions to Nonconvex Problems by Evolution of Hamilton-Jacobi PDEs.  arXiv:2202.11014, 2022.
  * [15] R. Jordan, D. Kinderlehrer, and F. Otto.  The Variational Formulation of the Fokker–Planck Equation.  SIAM Journal on Mathematical Analysis, Vol. 29, Iss. 1, 1998.
  * [16] J. M. Lasry, and P. L. Lions.  Mean field games.  Japanese Journal of Mathematics, 2, 229-260, 2007.
  * [17] S. Liu, M. Jacobs, W. Li, L. Nurbekyan, and S. Osher.  Computational Methods for First-Order Nonlocal Mean Field Games with Applications  SIAM Journal on Numerical Analysis, Vol. 59, 2639-2668,2021.
  * [18] F. Leger, and W. Li.  Hopf–Cole transformation via generalized Schrödinger bridge problem.  Journal of Differential Equations, Volume 274, 788–827, 2021.
  * [19] C. Léonard.  A survey of the Schrödinger problem and some of its connections with optimal transport.  Discrete and Continuous Dynamical Systems, 34(4):1533–1574, 2013\.
  * [20] W. Li, J. Lu, and L. Wang.  Fisher information regularization schemes for Wasserstein gradient flows.  Journal of Computational Physics, Volume 416, 109449, 2020.
  * [21] A. Lin, W. Li, S. Osher, and G. Montufar.  Wasserstein Proximal of GANs.  Geometric Science of Information, pp 524-533, 2021.
  * [22] E. Nelson.  Quantum Fluctuations.  Princeton series in physics. Princeton University Press, Princeton, N.J, 1985.
  * [23] S. Osher, H. Heaton, and S.W. Fung.  A Hamilton-Jacobi-based Proximal Operator.  arXiv:2211.12997, 2022.
  * [24] C. Villani.  Optimal Transport: Old and New.  Number 338 in Grundlehren Der Mathematischen Wissenschaften. Springer, Berlin, 2009.
  * [25] K. Yasue.  Stochastic calculus of variations.  Journal of Functional Analysis, 41(3):327–340, 1981.
  * [26] J. C. Zambrini.  Variational processes and stochastic versions of mechanics.  J. Math. Phys., 27(9):2307–2330, 1986.


# Towards Efficient Data Management
For IPFS-based Applications

Vero Estrada-Galiñanes VEG<EMAIL_ADDRESS>is Research Scientist at
EPFL, Switzerland Ahmad ElRouby AE is Master Student at EPFL, Switzerland Léo
Marc-André Theytaz LMAT is Master Student at EPFL, Switzerland

###### Abstract

Inefficient data management has been the Achilles heel of blockchain-based
decentralized applications (dApps). An off-chain storage layer, which lies
between the application and the blockchain layers, can improve space
efficiency and data availability with erasure codes and decentralized
maintenance. This paper presents two fundamental components of such storage
layer designed and implemented for the IPFS network. The IPFS Community is a
component built on top of the IPFS network that encodes and decodes data
before uploading to the network. Since data is encoded with alpha entanglement
codes, the solution requires less storage space than the native IPFS solution
which replicates data by pinning content with the IPFS Cluster. To detect and
repair failures in a timely manner, we introduce the monitoring and repair
component. This novel component is activated by any node and distributes the
load of repairs among various nodes. These two components are implemented as
pluggable modules, and can, therefore, be easily migrated to other distributed
file systems by adjusting the connector component.

##  1 Introduction

The emerging Web 3.0 (Web3) movement [1] has the ambition of re-decentralizing
web platforms and applications. Towards this end, many blockchain-based
decentralized applications (dApps) and web3 technologies are designed with
decentralized architectures that include a layer for distributed ledger
technologies (DLTs). A caveat is that their blueprint usually omits or
trivializes the storage layer and the components that are needed to manage
data availability efficiently.

Blockchains, a kind of DLT, need to be considered carefully for the need of
reliably storing data and making it available to users. Replacing a
traditional database for a blockchain makes sense to guarantee data integrity
and content redundancy when mutually mistrusting entities need to interact and
change the state of the system without using a third party[2]. Even if
blockchain technologies can be used in several use cases, they are not a
feasible solution for several applications. One problem is that the cost of
on-chain data is high and volatile. In Ethereum [8], this cost is usually
quantified in terms of the gas cost.

The gas cost for on-chain data is only the tip of the iceberg. A typical
blockchain-based solution requires and excessive amount of network resources
such computation and memory. The number of content replicas cannot be
controlled, any node that downloads the blockchain is storing a replica. On
plus, the more resources we asked from blockchain nodes, the more is the risk
of centralization because a small operator may not be able to run a node that
fulfill the requirements. Resource mismanagement can trigger further problems.
For example, Cryptokitties [9], now an outdated game application, at its peak
of popularity has congested the Ethereum network and raised the gas price
affecting the whole ecosystem.

One way to address scalability and speed issues inherent in the original
blockchain design (Layer 1) is to process transactions off the main blockchain
as in Layer 2 solutions such as the Lightning network and rollups. Layer 2
solutions are designed to operate on top of a Layer 1 blockchain. Another
approach is to use a decentralized peer-to-peer network such as the
InterPlanetary File System (IPFS) [6] to store data off-chain. For example, a
large file can be stored in IPFS while alleviating the storage requirements in
the blockchain by solely requiring on-chain storage of its IPFS content
identifier (CID). When considering these solutions, the blueprint for a
scalable decentralized architecture includes the application, the storage
layer, and the L1/L2 blockchains.

Examples of decentralized storage network layers are Arweave, IPFS, Storj, and
Swarm. These networks are designed to store any kind of unstructured and semi-
structured data (videos, images, JSON files, etc). Databases have been built
on top to tolerate structure data and queries. The most relevant functionality
of these networks is to add redundancy by storing the content in multiple
nodes. The replicas are added to increase the probability that the content is
available when a user requests it. But n-way replication is not space
efficient, even if the number of copies can be controlled by the network. On
top, storing multiple replicas does not guarantee content availability. At
least one of the nodes responsible of the replicas need to be online but also
the metadata to access that node needs to be available. Any reliable system
needs some failure detection mechanism and repairs to maintain file
availability. Inefficient data management has been the Achilles heel of dApps.

This paper presents self-organizing tools for encoding, decoding, and
maintaining redundancy levels to facilitate efficient data management in a
decentralized storage network. Our work is built on top of the IPFS network,
which is self-defined as an “open system to manage data without a central
server.” Although IPFS introduces various components to manage data, it does
not have any native solution for erasure coding data and maintenance. Instead
IPFS relies on replication, that can be managed by third party pinning
services or in a self-organized manner with the IPFS Cluster tool.

The contributions of this work include: 1) An investigation on multiple
approaches to store encoded data and the rationale of using alpha entanglement
(AE) codes. 2) The design and development of a component built on top of the
IPFS Cluster that encodes and decodes data while improving the space
efficiency of the network (IPFS Community). And, 3) the design and development
of a self-organized tool to repair missing files collaboratively.

##  2 IPFS: A Primer on its Reliability

The InterPlanetary File System (IPFS) is a decentralized peer-to-peer file-
sharing protocol, facilitating the distribution and retrieval of files within
a network architecture devoid of centralized control mechanisms. This system
is increasingly integral to dApps developments within the domain of Web3
technologies, offering a novel approach to data storage and access that
diverges from traditional centralized data storage models. IPFS enhances the
efficiency and speed of data sharing across a distributed network, thereby
addressing significant challenges associated with data sovereignty and access
latency [3].

IPFS is conceptualized as a foundational infrastructure for Web3 applications,
necessitating high levels of reliability and availability to support the
operational demands of decentralized networks. Despite its innovative
contributions to decentralized file storage and access, IPFS encounters
several notable challenges that warrant further research and solutions. These
challenges include a limited broader adoption, uncertainties regarding the
protocol’s scalability and performance under conditions of increased network
load, concerns related to user accessibility and interface usability, and
complexities associated with the upload process for large data files.

Some of the core components of IPFS relevant to this work are the distributed
hash table (DHT), the Merkle Directed Acyclic Graph (DAG), and the pinning
service provided by the IPFS Cluster. The DHT is a distributed key-value
storage system, which provides IPFS with distributed storage. The Merkle DAG
is a tree-like data structure used to ensure the integrity and verifiability
of files stored in IPFS. Files added to IPFS are divided into blocks and put
together in a Merkle DAG. The root hash is included in the content identifier
(CID) which is used to access and route to the file via the DHT. Following
this structure, files are immutable, and CIDs serve for integrity checks. By
default, the file has only one replica that resides in the local IPFS node.
IPFS disseminates provider records upon file upload. These records facilitate
the discovery process within the network, enabling other users to locate and
retrieve files from the hosting node. To locate and announce content, IPFS
uses the Kademlia DHT [7]. Users may choose to become additional providers of
a file, increasing its availability and resilience within the network,
particularly for content that is in high demand or not supported by sufficient
hosting resources. The IPFS Cluster is a tool to create a private network of
IPFS nodes that replicates content and interacts with the IPFS public network
through proxies.

Some of the ongoing research and development efforts aim at enhancing protocol
efficiency, user experience, and overall system scalability. Addressing these
limitations is paramount to fully leveraging IPFS’s potential in supporting
the decentralized web and fostering the growth of dApps reliant on robust,
decentralized data storage solutions. In this section, we discuss the IPFS
perspective with regard to reliability, the concept of pinning and the IPFS
Cluster component. More insights about the IPFS monitoring metrics, failure
detection, and the data allocation procedure are given in the Appendix
appendix A.

###  2.1 Reliability

IPFS operates on a content-addressable storage model, meaning that content is
retrieved based on its hash rather than its location. While this model
enhances privacy and security, ensuring that content remains accessible
without centralized control, it also introduces challenges in content
persistence and availability. Specifically, if a file is not actively hosted
by a node in the network, it may become inaccessible to other users. Unlike
traditional web hosting, where a central server ensures content availability,
IPFS relies on the network’s nodes to voluntarily host and share content. This
decentralized nature poses potential issues:

  1. 1.

Persistence: Content might become unavailable if no node chooses to host it or
if the hosting nodes go offline. This is particularly problematic for less
popular or older content that may not be actively accessed or maintained.

  2. 2.

Replication and Redundancy: Effective strategies for content replication and
redundancy are necessary to prevent data loss and ensure high availability,
which requires coordination and cooperation across the network.

  3. 3.

Incentivization: Mechanisms to incentivize nodes hosting and sharing content
are required to ensure that data remains accessible over time. While solutions
like Filecoin [5] have emerged to address this by creating a market for
storage, its effectiveness and integration within the broader IPFS ecosystem
continue to be areas of active research.

IPFS has implemented a design decision that, while advancing its efficiency
and privacy objectives, introduces certain operational complexities.
Specifically, newly uploaded files are initially stored exclusively on the
uploader’s local IPFS daemon (node). This model protects user privacy by
preventing the storage of data on potentially insecure nodes. The node
operator has control over their node’s content, offering a safeguard against
the involuntary hosting of undesirable files.

###  2.2 Content Persistence via Pinning

IPFS uses a garbage collection to automatically reclaim memory by eliminating
content that is no longer used. Node operators can choose to make content
persistent by “pinning” it. Pinned content is not removed from the local cache
during garbage collection. Although pinned content may be considered as
“reliably stored”, that is not a precise definition. If the local node is
offline, the content will not be accessible. Additionally, pinning can be done
remotely with third-party services. The remote pinning ensures that data
persists on IPFS even when the local node goes offline or fails. Another
alternative is the IPFS Cluster, a self-organizing tool for content
persistence among multiple IPFS nodes. Our work seeks to complement the
functionalities enabled by the IPFS Cluster.

###  2.3 Replication

IPFS does not enforces any replication mechanisms to protect content. As we
discussed in the previous subsection, content that resides on a single node
does not have protection against failures. Also, IPFS lacks of a reliability
mechanism to replace missing copies of a file without another peer accessing
the data. There is no way for a peer in IPFS to improve its file’s lifetime if
nobody else downloads it, which limits the reliability offered by the system.
This is where the IPFS Cluster can help.

###  2.4 IPFS Cluster

The IPFS Cluster enables collaboration between IPFS nodes and provides fault
tolerance by allocating, replicating, and tracking a global pin-set
distributed among multiple IPFS nodes. The pin replication is handled with the
Raft consensus [12].

Let us break down the steps that peers must go through when pinning a file.
Initially, the interested user will pin the file on its own IPFS node. The
pinning operation takes an optional replication factor as an argument or takes
the default configuration value. This number indicates how many peers must be
selected (the desired total number of replicas in the network). Then, an
allocation procedure (described in Appendix A.3) will locally produce a list
of peers responsible for storing the file. The pinning initiator submits this
list, along with other information, to the consensus component. Once the
consensus validates this update, it integrates the global pinset and triggers
a tracking operation at each peer. This operation asks each peer to check if
it is responsible of storing and tracking this file. If so, the peer will pin
the file on its IPFS node and start tracking it to react in case of failures.
Afterwards, IPFS-Cluster continuously monitors its peers to maintain the
appropriate replication factor even in the face of peer departures or
failures.

##  3 Proposed IPFS Community

This section describes the high-level architecture of the proposed IPFS-based
storage layer. This layer falls between dApps and L1/L2 blockchains. It relies
on the IPFS network and the IPFS Cluster to handle the uploading and
downloading of data and parity blocks, but further enables the capabilities by
maintaining state through a daemon running in the background and allowing
collaboration between community nodes. The collaborative aspect allows for
faster and deeper repairs while monitoring improves block availability.

For clarity we describe our goals, a strawman and the improved proposal to
align better with our goals. We also describe the rationale behind the chosen
encoding algorithm.

###  3.1 Strawman

Our main goal is to increase file reliability in IPFS without increasing
storage overhead. For that, we need to replace the replication mechanism with
encoding data, particularly AE codes (in section 3.4 we explain why we choose
these codes).

We can now discuss a few approaches for achieving our goal: (i) use a remote
pinning service, (ii) building on top of the IPFS Cluster, or (iii)
reengineering IPFS.

Solution (i) introduces an extra burden on users, i.e., users have to set up
and possibly pay for the service. Users need to trust the third party.
Meanwhile, how service providers store the user-uploaded data is out of our
control. Service providers are free to use any redundancy schema that they
have at hand, and deliver it to the users. As a result, we consider this
solution less optimal.

Solution (ii) turns the IPFS Cluster into our main entry point of interaction
with the outside world. Our solution would send “entangled blocks” to the
cluster and the cluster would allocate them to cluster member nodes. Members
shall trust each other.

Solution (iii) would provide a seamless user experience with IPFS taking care
of the content entanglement. Independently of how the entanglement is done
(file-wise entanglement or cross-file entanglement) this solution may require
excessive reengineering work without knowing if the changes would be accepted
by the IPFS core team.

As a compromise, we seek for solution (ii), which uses IPFS Cluster as the
underlying mechanism to distribute entangled blocks. It is more flexible than
solution (i) since we can tailor our own logic on top, and it is more feasible
than reengineering IPFS.

Figure 1: Strawman IPFS Community Architecture.

To introduce the design of the IPFS Community, we begin with a simple strawman
illustrated in fig. 1 and described below. An IPFS Cluster node runs on top of
an IPFS node. IPFS Cluster nodes themselves do not store the file content; it
instructs the IPFS node to do so. The connection between different IPFS
Cluster nodes is only privately known. On the other hand, IPFS nodes are all
publicly available, meaning that contents stored in them could be accessed by
others. Unless the node operator limits the accessibility of the IPFS nodes.

To simplify the implementation of this idea, this strawman uses a metafile.
The metafile contains information related to the encoding/decoding process. In
the native IPFS solution, the user only provides the file CID to download a
file. To be able to profit of the additional redundancy added with the encoded
data, our strawman requires that the user provides the metafile as well as the
CID. If the original files are missing, the download procedure will try to
fetch the entanglement and restore the original file.

The IPFS Community has three major components, eDAG-Coder, Repairer, and
Connector, each of them responsible for different functionalities. The user
interacts with the IPFS community with a CLI interface. When we upload a file
into IPFS, a Merkle DAG is created as discussed in Section 2. The eDAG-Coder
takes the DAG as input and entangles its block components to create $\alpha$
entangled DAGs (eDAGs). The encoding parameter $\alpha$ is specified by the
user to indicate the desired redundancy factor. The repairer component is a
complement to the downloader. If some or all blocks of a file are missing, the
repair process attempts to recover the file using the entangled DAGs. We
assume both one IPFS Cluster instance and one IPFS instance run locally. The
IPFS Cluster nodes interact with IPFS using its exposed APIs. The IPFS Cluster
instance connects to cluster member nodes, while the IPFS instance connects to
the IPFS public network. The Connector connects the IPFS Community to the
running IPFS Cluster and IPFS instances. The IPFS Community uses the IPFS
Cluster and the IPFS node as tools to deliver the service; it does not change
their internal logic.

The following steps occur when uploading a file: (1) A user uploads a file
through the IPFS community. The file is handled by the local IPFS to create a
Merkle DAG where the leaves are the data blocks that form the file. (2) The
eDAG-Coder retrieves all the blocks back to entangled them together,
generating entangled blocks. (3) The eDAG-Coder uploads the entangled blocks
to the local IPFS, making them locally available. (4) The eDAG-Coder pins the
entangled content via the IPFS Cluster’s API, making the blocks remotely
available. (5) The user receives the file CID and the metafile CID.

The following steps occur when downloading a file using: (1) A user input the
file’s CID and the metafile CID. The metafile CID is optional but useful for
repair missing data. (2) When doing repairs, the eDAG-Coder triggers the
building of a lattice (related to the AE code algorithm) based on the
information provided in the metafile, e.g., the total number of data blocks.
(3) The lattice requests any additional desired block from the IPFS network.
(4) The Repairer repairs missing blocks using the additional blocks. (5) The
user obtains the requested file.

###  3.2 Challenges

The metafile of our strawman, from now on also referred as _IPFS-community
0.5v_ , contains all the entanglement configuration parameters and file
information relevant to the Repairer, as well as a mapping between the
lattices indexes and the CIDs for data/entangled blocks. This approach
introduces an additional complexity for the user, who needs to keep the
metafile, limits the repairs to only users who have the metafile, and requires
additional space overhead (something that we want to avoid). According to our
estimations (see Appendix appendix C) for 300 nodes, 1000 files that generate
200 blocks each, the metafile generated when the encoding parameter $\alpha=3$
would require approx. 9 GB. This space requirement would increase further, the
more nodes and files were added to the system. The takeaway is that our final
design must not use a metafile.

###  3.3 Design Overview

Our starting point is the IPFS Community v0.5 strawman. To add capabilities,
the IPFS Community requires a stateful design. A daemon running in the
background allows collaboration between community nodes and performs all
operations on behalf of the user. Collaborations contribute to efficient and
deeper repairs (using locality for single repairs but expanding repairs in
cases with large amount of failures). The daemon continuously monitor the
status of the files and a failure detection mechanism that triggers preventive
repairs when detecting important loss of blocks.

As a result, our proposed solution, from now on referred as IPFS community
1.0v can profit from multiple peers collaborating in a file repair processes,
which balances network traffic and speeds up the recovery of blocks (see
Section 6.3). The storage overhead caused by the metafile was reduced by
creating our key data structure, the $\alpha$ entangled Merkle DAGs (see 3.5).

Figure 2: Design Architecture: IPFS Community Node

As outlined in figure 2, the architecture of a single _IPFS community 1.0v_
node consists of the following: (1) Command Line Interface: An interface that
provides the user with the ability to upload, download, repair files as well
as starting a daemon in the background to perform all the required operations.
(2) IPFS: Each community node relies on an IPFS peer node running on the same
machine to which it forwards the requests for uploading and downloading blocks
from the network. (3) IPFS Cluster: This component ensures that given at least
one copy of a pinned block, it will be replicated according to the specified
configurations. It maintains a pinset and runs the consensus algorithm to make
sure all nodes have the same view of the pinset. (4) Connector: It maintains
connections with the IPFS and IPFS cluster nodes. It also handles all
communication required to perform any operation that involves either of these
two components. (5) eDAG-Code: It uses AE codes to generate entangled blocks
taking as input data blocks of a specific file. (6) Upload: It handles the
file uploading process to IPFS, generating the entangled blocks through the
eDAG-Coder, and creating entangled Merkle DAGs use for the repair mechanism.
(7) Download: It requests data from IPFS, and subsequently returns the file to
the requesting user in case of success, or starts a limited repair process in
case of missing data blocks. (8) Repair: Essentially, it orchestrates all
needed steps to successfully recover a file given the possibility and allowed
repair depth (more about this later). (9) Monitoring: It runs in the
background. This component monitors files under its responsibility to
determine their status and triggers repair when deemed necessary. (10)
Collaborative Repair: It coordinates between different peers to distribute the
load for a deep repair of a certain file.

###  3.4 Key Algorithm: AE Codes

Our proposed solution relies on AE codes [11]. For more detail on how the AE
codes work we refer the reader to the original publication. In this section we
will elaborate on the decision of using AE Codes and address the following
questions: (1) Why not replication? (2) Why not traditional erasure codes?

Distributed systems can increase reliability and fault tolerance by storing
data replicas across multiple storage devices or locations. Redundancy
prevents errors when a component is malfunctioning, there are transmission
errors, or the node is not available. But using replication for decentralized
solutions is not scalable in the long term. As a method to create redundancy,
n-way replication is not space efficient. In addition, popular content
triggers the creation of an excessive amount of replicas, congesting the
network, and filling up memory space while leaving unpopular or ignored
content without sufficient protection.

In a trustless distributed environment, the mechanism that guarantees data
integrity is fundamental. While the correctness of replicas can be verified
with a quorum consensus mechanism in a distributed system, off-chain storage
systems provide other options. In the context of IPFS, data integrity refers
to the assurance that data has not been tampered with or altered in an
unauthorized manner from the time it was published to the time it is accessed.
To retrieve data, IPFS relies on content addressing, a method where each piece
of content is given a unique CID that contains a cryptographic hash of the
content itself. The use of CIDs ensures that references to data are immutable
and independent of their location. If content is changed or updated, it
receives a new CID, preserving the integrity of the original data. This means
that the CID changes if even a small part of the content is altered, ensuring
that any modification to the data results in a different identifier. This
prevents unauthorized alterations since any change to the content would be
easily detectable due to the change in its CID.

CIDs can be verified directly by a user instead of the need to trust a
consensus committee. When data is retrieved using a CID, the IPFS node can
verify that the content matches the request by computing the cryptographic
hash of the received content and comparing it to the requested CID. If the
computed hash and the CID match, it confirms that the content has not been
altered, ensuring its integrity. The cryptographic nature of CIDs makes it
computationally infeasible to reverse-engineer the content from the CID or to
create content that would match a specific CID. This property is essential for
preventing tampering, as any attempt to alter the content would be easily
detectable by anyone verifying the data against its CID.

The Merkle DAG structure allows each node to link to other nodes using their
CIDs. Because these links are based on the content’s hash, they are immutable
— altering the content at any point in the DAG would require changing all
subsequent CIDs, making unauthorized alterations easily detectable. Complex
data structures, such as files or directories, can be represented as a
hierarchy of Merkle DAG nodes.

AE codes add extra layer for integrity protection with the created
interdependencies between data and entangled blocks. The decoder algorithm can
use different blocks to generate the same output. If that output is different,
it becomes evident that something went wrong.

Traditional erasure codes, such as Reed Solomon, does not have this additional
layer for data integrity protection. When a file is distributed among network
nodes, repairing missing chunks with erasure code requires more bandwidth. The
problem is particularly relevant when repairing single failures. Thus, a
decentralized repair mechanism does not make any difference. On the contrary,
the node in charge of repairs need to get all the needed blocks from the
network and recover the file locally. While this can work for streaming
applications, it is not a good option for random access and decentralized
monitoring and maintenance of the storage network layer.

###  3.5 Key Data Structure: Entangled Merkle DAGs

In our strawman, entangled blocks were uploaded to the IPFS network as single
files. This individual entangled blocks were worthless without the information
contained in the metafile. To enable seamless repairs, our solution embeds
this information inside the IPFS hash tree, also known as Merkle DAG. Merkle
Trees play a crucial role in how data is structured in modern decentralized
storage systems to enable efficient content verification.

Thus, we replace the metafile for a more efficient data structure. The
entanglement process will generate a Merkle DAG for all the relevant entangled
blocks, aka eDAG, to a particular “strand direction.” A strand and the strand
direction are concepts related to the AE codes. The parameter $\alpha$
indicates the total number of strands directions. By creating $\alpha$ eDAGs,
the system has multiple ways of repairing the file. First, the repair process
can use any of the $\alpha$ eDAGs, since each of them is self-contained and
can be used to recover the file by sequentially xoring the entangled blocks
that form the chosen eDAG. Alternatively, multiple eDAGs can be used in
combination to repair a large number of missing blocks. Entangled Merkle Trees
were introduced by [10]. In this work, we adapted the structure to the
specifics of the IPFS Merkle DAG.

##  4 IPFS Community Implementation

The project was implemented during two semesters (28 weeks). The codebase has
integrated more than 14k lines of code written in Golang, NodeJS, and Python
and is open-sourced 111https://github.com/dedis/student_23_ipfs_reliability.

The starting point is the command line interface (cli), with its main command:

⬇

$ daemon –cluster-ip <ci> –cluster-port <cp>

–community-ip <ip> –port <p> –discovery <server>

–ipfs-ip <ip_ipfs> –ipfs-port <port_ipfs>

is responsible for running the daemon that is used for multiple purposes as
described earlier. The command requires information about the ip address and
the port on which the daemon would run. Information regarding the IPFS and
IPFS cluster nodes are also required. Finally the full address of the
discovery address should be provided.

###  4.1 Upload: File Entanglement

The file entanglement is done during the file upload process initiated through
the command line interface according to encoding parameters specified by the
user. The output of the process are the Merkle DAG for the data file and
$\alpha$ Merkle DAGs constructed with the entangled blocks.

⬇

$ upload –address <community_address:port> –alpha <a_AE>

–p <p_AE> –s <s_AE> –direct-replication <replication_factor>

–replication <rf_intermediate_nodes_EMTs>

###  4.2 Download: File Repairs

Another integral operation provided is the ability to download and perform
limited repairs to recover a file. The main goal of this operation is to
provide the user with either the recovered file or an error with minimal
perceived latency.

The successfully recovery of the file in this case is limited by the repair
depth specified by the user. The depth refers to how far we use a particular
eDAG to recover a missing block before giving up (it indicates how many
entangled blocks are recursively used to repair a file). After this step, we
either have the complete file or not. Repaired blocks are uploaded to IPFS
again. The download service returns the download data to the original
requester if recovery was possible or an error otherwise.

⬇

$ download –address <ip:port_community_node> –depth <depth>

–metacid <metadata_CID> –output <path_downloaded_file>

–upload-recovery <bool_upload_recovered_blocks_back_to_IPFS>

##  5 Collaborative Repairs

The goal of collaborative repairs is to distribute the load of maintaining
file redundancy among peers. The benefits are to speed up the process and
require less computer resources per peer. Additionally, we can also increase
the depth of the repair, i.e., more entangled blocks that can be used to
repair a particular failure, improving the utilization of the existing
redundancy.

In this section, we describe how we managed to attain this goal. The figure 3
shows an overview of the flow for running collaborative repair. The blue cubes
in it represent the _IPFS community 1.0v_ node we built which in our case
should run alongside an IPFS, and an IPFS-Cluster node on the same machine. It
is important however to note that they don’t necessarily have to run on the
machine in which case the discovery service was deemed necessary. The
discovery service allows the community nodes to query the peers available on
the private network and provides mapping from cluster nodes to community
nodes. The discovery service runs in the background with a fixed hostname that
is used by community nodes on startup to advertise their addresses. This
solution was motivated by the timing constraints of the project. In order to
relate IPFS-Community and IPFS-Cluster nodes together as well as benefit from
the existing network parts of IPFS-Cluster in a short amount of time, we
centralized the discovery service. It then performs regular health
checks222These checks are solely for the purpose of delivering correct network
addresses, and not related to data monitoring. according to a pre-defined
interval to make sure that its view of the system is correct.

Figure 3: Collaborative Repair

The repair flow includes seven steps.  1. The collaborative repair in this
diagram was triggered by a user for demonstrative purposes only. However, in
reality, the repair is triggered by the failure detection service running in
the Community node, or a failed download for a particular file where the
repair with limited depth was not enough.  2. The node on which the
collaborative repair was triggered should now be referred to as the
coordinator. The coordinator starts by fetching the metadata from the IPFS
network. It then starts to recursively traverse the original merkle tree of
the file. For every missing non-leaf tree node, the coordinator attempts to
recover in the background with a strand depth pre-defined in the system’s
configuration. In case of failure, the repair is aborted, and the system
reports the operation a failure. However, if all intermediate tree nodes were
recovered successfully, the coordinator will then try to fetch all leaf nodes.
All leaf nodes that were unavailable will then be added to a list. If all node
are available, then the coordinator reports the success of recovery process
and returns the file.  3. The coordinator then queries the discovery service
for available peers. A peer-to-peer membership algorithm would have been
required without the discovery service.  4. The coordinator then chooses a
specific number of peers (which is passed as an argument or pre-defined in the
configuration) for the collaborative repair process, splits the unavailable
leaf nodes amongst them, and then forwards them to these peers.  5. Each peer
now with a list of nodes (or data blocks) missing from the network, starts
their recovery process. Individually, each peer runs multiple instances of
recovery for the missing nodes and awaits the result.  6. The final result for
each missing node (or data block) is then packaged as a response and sent back
to the coordinator, where it re-assembles the file if the process was
successful.  7. Finally, the coordinator asynchronously sends back the final
state of the process to the requesting service.

##  6 Evaluation

We evaluate the IPFS Community with a detailed experimental evaluation. We use
a network with 20 IPFS nodes, IPFS cluster, IPFS community nodes. All
experiments were repeated 10 times and use AE codes with coding parameters:
$\alpha$=3, s=5, p=5. The default fize size for uploads/downloads is 25 MB.

###  6.1 Environment Setup

All experiments were carried out on an Ubuntu 22.04 running on a 16-core AMD
Ryzen 9 5950X 3.4 GHz with a total of 64 Gigabytes of RAM. This setting allows
to run multiple instances, one for each peer, on a single machine. We use
Jinja2 library to generate different configurations for testing. We rely on
docker compose to handle the creation of peer instances and managing the
networking interfaces between them.

###  6.2 Recovering Data: Replication vs eDAGs

We run experiments with the strawman design to compare the recovery rates of
AE codes with replication. Results are not included due to space reasons and
are similar to those found in the literature [10]. Contrary to the strawman
design, the eDAGs that replace the metafile introduce another failure domain,
in which a missing intermediate node in the Merkle tree would completely
hinder the recovery process. Those nodes are protected with additional
replication specified by the user. We run experiments to compare the
likelihood of recovering data either partially or fully using replication
(R=3,5,7) and eDAGs implemented in the IPFS Community. Results are presented
in Figure 4.

Figure 4: Average percentage of recovered blocks given a percentage of peer
failure

###  6.3 Performance Evaluation for Collaborative Repairs

We compare performance of collaborative repairs against single peer repair
using identical parameters. Single repair total time refers to the total time
taken to recover the file, and on the collaborative repair’s side, the total
time taken from finding which blocks are missing, distributing the failures
across the peers, waiting for all peers to finish and finally reporting the
success of the operation. End-to-end the procedure is the same since the goal
was to determine how long it would take to finish the repair process for a
single file. In addition, we compare the average processing time for each peer
which is expected be lower in the collaborative mode since each peer is only
repairing a fraction of the file. Finally, to determine the bandwidth overhead
of both methods, we compare firstly the total number of blocks downloaded over
the network for each method, as well as the average blocks downloaded per
peer.

Measurements for the impact of repair depth and more figures appear in the
Appendix appendix D. The Appendix also includes measurements for the impact of
repair depth. We summarize here the key takeaways:

  1. 1.

On average, total repair time in collaborative repair is significantly lower
than its counterpart in single repair, especially with higher failure rates.

  2. 2.

On average, each peer would spend considerably less time repairing the file on
the network compared to a node performing the repair alone.

  3. 3.

The average number of blocks downloaded over the network per peer is much
lower in the case of collaborative repair over single repair due to the fact
that collaborating peers only need to repair a fraction of the data.

  4. 4.

On average, the total bandwidth used over the network downloading blocks is
much higher in the case of collaborative repair. This can be attributed to the
fact that a single node doesn’t need to download the same block twice,
however, multiple peers attempting to repair a single file will have
overlapping blocks through the repair process, forcing them to download the
same block multiple times.

##  7 Conclusion

Merkle DAGs are a core concept for decentralized systems, not only for storage
networks like IPFS, but also at the core of technologies like git, bitcoin and
dat. This work explores resource efficient data management methods for off-
chain data using entangled Merkle DAGs and collaborative repairs. Our results
demonstrate significant space savings and a promising failure detection and
repair mechanism to persist content in decentralized networks, thereby laying
a solid foundation for future research and developments. These advancements
not only contribute to IPFS but also could benefit a wide range of
decentralized applications.

##  8 Acknowledgement

We thank Qiyuan Liang and Yuening Yang for their early contributions to the
project. This work was supported in part by the Initiative for
Cryptocurrencies and Contracts (IC3) at Cornell Tech in partnership with
Ethereum, Grant No. 10232.

## References

  * [1] Ray, Partha Pratim  “Web3: A comprehensive review on background, technologies, applications, zero-trust architectures, challenges and future directions.”  Internet of Things and Cyber-Physical Systems (2023) https://doi.org/10.1016/j.iotcps.2023.05.003
  * [2] Wüst, Karl and Gervais, Arthur  “Do you need a blockchain?”  2018 IEEE Crypto Valley Conference on Blockchain Technology (CVCBT)  45–54 https://doi.org/10.1109/CVCBT.2018.00011
  * [3] Daniel, Erik and Tschorsch, Florian  “IPFS and friends: A qualitative comparison of next generation peer-to-peer data networks.”  2022 IEEE Communications Surveys & Tutorials,  24 1 31–52 https://doi.org/10.1109/COMST.2022.3143147
  * [4] Protocol Labs  “IPFS Cluster - Automated data availability and redundancy on IPFS.” https://ipfscluster.io/documentation
  * [5] Benet, Juan and Greco, Nicola  “Filecoin: A decentralized storage network.”  Protocol Labs Whitepaper 2018 https://filecoin.io/filecoin.pdf
  * [6] Benet, Juan  “IPFS-content addressed, versioned, p2p file system.”  Whitepaper 2014 https://doi.org/10.48550/arXiv.1407.3561
  * [7] Maymounkov, Petar and Mazieres, David  “Kademlia: A peer-to-peer information system based on the xor metric.”  IEEE International Workshop on Peer-to-Peer Systems 53–65 Springer 2002 https://doi.org/10.1007/3-540-45748-8_5
  * [8] Buterin, Vitalik and others  “Ethereum.”  Whitepaper 2014 https://ethereum.org/en/whitepaper
  * [9] Jiang, Xin-Jian and Liu, Xiao Fan  “Cryptokitties transaction network analysis: The rise and fall of the first blockchain game mania.”  Frontiers in Social Physics 2021 Volume 9 2021 https://doi.org/10.3389/fphy.2021.631665
  * [10] Nygaard, Racin and Estrada-Galiñanes, Vero and Meling, Hein  “Snarl: Entangled merkle trees for improved file availability and storage utilization.”  Proceedings of the 22nd International Middleware Conference 236–247 2021 https://doi.org/10.1145/3464298.3493397
  * [11] Estrada-Galiñanes, Vero and Miller, Ethan and Felber, Pascal and Pâris, Jehan-François  “Alpha entanglement codes: practical erasure codes to archive data in unreliable environments.”  2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) 183–194 https://doi.org/10.1109/DSN.2018.00030
  * [12] Ongaro, Diego and Ousterhout, John  “In search of an understandable consensus algorithm.”  2014 USENIX Annual Technical conference (USENIX ATC 14) 305–319 https://www.usenix.org/conference/atc14/technical-sessions/presentation/ongaro

##  Appendix A More Insights about IPFS

###  A.1 Monitoring

In order to detect failures, peers must monitor each other. IPFS-Cluster peers
do so using a Pub-Sub system within their _monitor_ component. A common topic
is set up to share metrics with each other at regular intervals. Each metric
has a TTL, and fresh metrics will be sent after half of the smallest TTL
duration (among all shared metric types) using a timer based on the OS clock.
For example, the TTL for a ”freespace” metric is 30 seconds by default.

###  A.2 Metrics

Metrics are used to share information about peers. Those have a type, a value,
an expiration date (in Unix time), a weight, and a ”partitionable” attribute.
It allows peers to handle the information they receive in the correct way. The
metrics used in IPFS-Cluster have the following types:

  * •

freespace/reposize: Indicates how much free space the IPFS node has/the used
space reported by IPFS.

  * •

numpin: Indicates the number of items this peer is pinning.

  * •

pinqueue: Indicates the number of pending pins at this peer.

  * •

tag:tag_name: Can indicate anything to help declustering the allocation
process. For example, metric name ”tag:region” with value ”Florida” would
indicate that the peer’s server is located in Florida. The administrator of
the IPFS-Cluster can set the tag name and values in each peer’s configuration.

The partitionable attribute optimizes the allocation process by only allowing
meaningful partitions. When selecting peers to replicate a file, it makes
sense to spread the storage as much as possible. Targeting peers with
different characteristics (such as a ”tag:region” for example) will
declusterize the allocation to improve reliability. Some metrics give insights
of (de-)correlation between peers, and others help to rank peers based on
their capabilities. For example, _freespace_ is a non-partitionable metric,
and will only be used to sort peers and pick the ones with the most freespace
available.

###  A.3 Allocation procedure

The allocation procedure seeks to distribute data across the best available
peers, reducing the risk of single point of failure that would cause data
loss. This procedure outputs the list of peers across the cluster that will
pin the file on their IPFS node. To decide which ones will be selected, the
node takes multiple variables into account:

  * •

min/max replication factors (default or user-selected)

  * •

the user-set allocations (overriding the allocation procedure)

  * •

metrics about the other peers based on the configuration of the allocator
(_allocate_by_)

  * •

potential existing allocations (if the CID was already pinned).

###  A.4 Failure Detection

Careful allocation and monitoring contributes to prevent file loss and that
the system degrades. The risk of file loss increases with every replica that
becomes unavailable. When a peer does not receive an up-to-date metric before
the metric expiration time333IPFS-Cluster use OS clock time and assumes
negligible clock drift for the timeouts to be fixed., it raises an alert.
Peers will then verify in the global pin-set if the node they suspect to have
failed was in the allocation list of a pin. If so, the closest alive peer to
the failed peer will trigger an operation to re-pin the file.

In case every peer which had pinned this file were to disconnect at the same
time, the re-pin operation would fail, as the original data would be nowhere
to be found. More replicas reduce this risk by increasing reliability at a
high cost. Given the constraints of limited storage capacity, exploring
alternative methods to enhance reliability presents a compelling opportunity.

##  Appendix B Failure Detection in the IPFS Community

IPFS-Community offers storage reliability with redundancy in the format of AE
codes to reduce the storage overhead of simply replicating a file multiple
times. To do so, parities resulting of the entanglements and data blocks are
pinned at the IPFS-Cluster layer with a replication factor of 1. While the
blocks are tracked, there is no guaranteed way to recover such blocks if a
peer goes offline. The repair mechanism using AE codes allows for missing
blocks while still recovering the original file, but the maximum number of
missing blocks tolerated depends on the AE parameters $\alpha$, $s$ and $p$.
Our goal is thus to detect those losses before the file becomes irrecoverable
and trigger preventive repairs in batches to optimize the repair costs.

###  B.1 Monitoring nodes

Before triggering preventive repairs, block losses have to be detected. To
achieve this goal, some peers must actively monitor the network and look after
failures. In order to select these _monitor nodes_ , we will reuse the
allocation process of IPFS-Cluster. Indeed, when a file is added through IPFS-
Community, root nodes of the different parity trees will be pinned to IPFS-
Cluster. If monitoring is requested for a file, the peers selected during the
allocation process to pin the strand roots will be designated as _monitor
nodes_. In Figure 5 we can see how the monitoring is put in place:

Figure 5: High level monitoring set-up

  1. 1.

The command line interface uploads the file to IPFS and parities to IPFS-
Cluster which results in allocation processes.

  2. 2.

If monitoring is requested, the CLI will ask a Community node to initiate the
monitoring.

  3. 3.

The Community node initiating the monitoring gets the allocation list for each
strand root of the entangled file.

  4. 4.

The initiator sends a request to start the monitoring to the _monitor nodes_
present in the allocation list.

  5. 5.

Finally, the _monitor nodes_ can start checking for the presence of blocks for
this file and trigger repairs when deemed necessary.

The implementation of _IPFS community 0.5v_ is a command line tool that
interacts with IPFS and IPFS-Cluster nodes. To allow for active monitoring, in
_IPFS community 1.0v_ we add a community node on top of each IPFS-Cluster
node. After uploading a file with _IPFS community 1.0v_ , peers selected to
track strands’ root will get a request at their Community node to start
looking after missing blocks. Each _monitor node_ will be tasked to: 1. Get a
view of the cluster and files (failed regions, failed blocks, time between
block failures, …), 2. Heuristically check that blocks of the monitored files
are present, 3. Trigger preventive repairs if a criticality threshold is
crossed, and 4. Sharing views and restarting444Assuming that a crash of the
Community node implies a crash of the corresponding Cluster node, a re-pinning
operation will be triggered if the Cluster node was responsible for pinning
blocks. If it pinned a strand root, it means we have to restart monitoring at
another Community node. monitoring upon failure.

##  Appendix C Metafile Overhead Calculations

To estimate the additional storage related to the metafile we use the
following equation:

$Total\ Storage=F\times N\times((1+\alpha)\times(B\times c))$ (1)

where:

  * •

[$F$] is the total number of files uploaded to the network.

  * •

[$N$] is the number of peers on the network.

  * •

[$B$] is the number of blocks the file was split into.

  * •

[$\alpha$] is the encoding parameter.

  * •

[$c$] is the constant number of bytes (40 bytes) for each map entry when
mapping the 64-bit lattice ID to a 256-bit HASH.

##  Appendix D Performance Evaluations Insights

We compare different metrics for single and collaborative repairs using
depth=5, 7, and 10. The figures show the average and standard deviation values
of all data.

(a) Depth 5

(b) Depth 7

(c) Depth 10

Figure 6: Average total time to recover a file

(a) Depth 5

(b) Depth 7

(c) Depth 10

Figure 7: Average time per peer to recover a file

(a) Depth 5

(b) Depth 7

(c) Depth 10

Figure 8: Average total number of blocks downloaded

(a) Depth 5

(b) Depth 7

(c) Depth 10

Figure 9: Average total number of blocks downloaded per peer