#  Disentangled Unsupervised Image Translation
via Restricted Information Flow

Ben Usman*
Boston University
<EMAIL_ADDRESS>Dina Bashkirova*
Boston University
<EMAIL_ADDRESS>Kate Saenko
Boston University
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
###### Abstract

Unsupervised image-to-image translation methods aim to map images from one
domain into plausible examples from another domain while preserving structures
shared across two domains. In the many-to-many setting, an additional guidance
example from the target domain is used to determine domain-specific attributes
of the generated image. In the absence of attribute annotations, methods have
to infer which factors are specific to each domain from data during training.
Many state-of-art methods hard-code the desired shared-vs-specific split into
their architecture, severely restricting the scope of the problem. In this
paper, we propose a new method that does not rely on such inductive
architectural biases, and infers which attributes are domain-specific from
data by constraining information flow through the network using translation
honesty losses and a penalty on the capacity of domain-specific embedding. We
show that the proposed method achieves consistently high manipulation accuracy
across two synthetic and one natural dataset spanning a wide variety of
domain-specific and shared attributes.

Figure 1:  Problem. An unsupervised many-to-many image translation model must
infer which attributes are target-specific, _e.g_. mustache in (a), and pose
in (c), extract values of these attributes from the “guide”, and apply them
during cross-domain translation. Most state-of-art methods assume that all
variations in colors and textures are target-specific, and fail to generalize
when attributes like background texture, hair color or skin color are varied
in both.

##  1 Introduction

The goal ††* equal contribution of unsupervised image-to-image translation is
to learn a mapping between two sets of images (or two domains) without any
pair supervision. For example, face domains in Figure 1a are defined by gender
and share variability in poses and backgrounds, so a correct cross-domain
mapping must change the face gender, but preserve the pose and the background
of the original. When one domain has some unique attributes absent in the
other domain, like males with and without beards in CelebA [17], the question
of whether the “correct” one-to-one cross-domain mapping should add a beard to
a specific female face does not have a well-defined answer. However, if we
alter the problem definition by providing a “guide” image specifying male-
specific factors, the resulting unsupervised many-to-many translation problem
has a well-defined correct solution: the learned mapping must preserve all
attributes of the source image that are shared across two domains and use
values of attributes unique to the target domain from the guide input (_e.g_.
preserve pose and background of the female source and add a beard from the
male guide in the example above).

Figure 2:  Flaws in existing methods. On Shapes-3D-A [16, 4], all prior
methods fail to either preserve shared attributes of the source (shape, object
color), or apply target-specific attributes of the guide (size, orientation),
or both.

Most state-of-the-art methods for unsupervised many-to-many translation
implicitly assume that the domain-specific variations can be modeled as
“global style” (textures and colors) by hard-coding this assumption into their
architectures via adaptive instance normalization (AdaIN) [13] originally
proposed for style transfer. However, this choice severely restricts the kinds
of problems that can be efficiently solved. More specifically, AdaIN-based
methods [14, 7] inject domain-specific information from the guide image via a
global feature re-normalization that forces colors, textures, and other global
statistics to be always treated as domain-specific factors regardless of their
actual distribution across the two domains. As a result, AdaIN-based methods
change colors and textures of the input to match the guide image during
translation even if colors/textures are varied across both domains and should
not change. For example, background textures in the female-to-male setting
(Figure 1a) vary in both domains, and therefore should be preserved, the same
holds for hair color in the children-to-adults setting (Figure 1c). Even on a
toy perfectly-balanced problem (Figure 2) AdaIN-based methods (_e.g_. MUNIT
[14]) change object color of the input to match the object color of the guide,
even though object color is varied in both domains, and thus should be
preserved.

Autoencoder-based methods [1, 18, 5], on the other hand, preserve shared
information better, but often fail to apply correct domain-specific factors.
For example, DIDD [5] preserved the object color of the source in Fig. 2, but
failed to extract and apply the correct orientation and size from the guide.
Overall, both our experiments and recent advances in evaluation of many-to-
many image translation [4], show that all existing methods generally either
fail to preserve global domain-specific attributes or fail to apply domain-
specific factors well.

In this paper, we propose Restricted Information Flow for Translation (RIFT)
\- a novel approach that does not rely on an inductive bias provided by AdaIN
and achieves high attribute manipulation accuracy across different kinds of
attributes regardless of whether they are shared or domain-specific. As
illustrated in Figure 3, during “brunet male-to-female translation” our method
preserves shared factors (background and pose) of the input male face, and
encodes male-specific attributes (mustache) in a domain-specific embedding to
enable accurate reconstruction of the source image. The core observation at
the heart of our method is that only values of shared attributes (background
and pose) of the source can be encoded naturally in a generated image from the
target domain, whereas source-specific attributes (mustache) can be encoded in
the generated image only by “hiding” them in the form of structured
adversarial noise [3]. With this in mind, we propose using the translation
honesty loss [3] to penalize the model for “hiding” [8] a mustache inside the
generated female image, and the embedding capacity loss to penalize the model
for encoding shared factors into the domain-specific embedding. As a result,
information about the mustache is forced out of the generated female image
into the domain-specific embedding, while information about the pose and
background is forced out of domain-specific embeddings into the translation
result - resulting in proper disentanglement of domain-specific and domain-
invariant factors.

We measure how well RIFT models different kinds of attributes as either shared
or domain-specific across three splits of Shapes-3D [16], SynAction [27] and
Celeb-A [17] following an evaluation protocol similar to the one proposed by
Bashkirova et al. [4]. Our experiments confirm that the proposed method
achieves high attribute manipulation accuracy without relying on an inductive
bias towards treating certain attribute kinds as domain-specific hard-coded
into its architecture.

Figure 3: Overview of the proposed method – RIFT. Source male image and male-
specific factors (green), female guide input and female-specific attributes
(blue), shared attributes (red).

##  2 Related work

#### Image-to-image translation.

In contrast to task-specific image translation methods [6, 12, 21, 25, 10,
28], early unsupervised image-to-image translation methods, such as CycleGAN
[29], and UNIT [19], infer semantically meaningful cross-domain mappings from
arbitrary pairs of semantically related domains without pair supervision.
These methods assume one-to-one correspondence between examples in source and
target domains, which makes the problem ill-posed if at least one of two
domains has some unique domain-specific factors, as we discussed in Section 1.

#### Many-to-many translation.

To account for such domain-specific factors, and to enable control over them
in the translation results, many-to-many image translation methods [14, 1, 7,
20, 18] have been proposed. These methods separate domain-invariant “content”
from domain-specific “style” using separate encoders. Following [4], we avoid
terms “content” and “style” to distinguish general many-to-many translation
from its subtask - style transfer [10].

#### Adaptive instance normalization.

Many state-of-art many-to-many translation methods, such as MUNIT [14], FUNIT
[20] and StarGANv2 [7], use AdaIN [13], originally proposed for style transfer
[10]. More specifically, these methods modulate activations of the decoder
with the domain-specific embedding of the guide. This architectural choice was
shown to limit the range of applications of these methods to cases when
domain-specific information lies within textures and colors [4].

#### Autoencoders.

In contrast, methods like Augmented CycleGAN [1], DRIT++ [18] and Domain
Intersection and Domain Difference (DIDD) [5] rely on embedding losses and
therefore are more general. For example, DIDD forces domain-specific
embeddings of opposite domain to be zero, while DRIT++ uses adversarial
training to make the source and target content embeddings indistinguishable.

#### Cycle losses.

Most methods [14, 1] also use cycle-consistency losses on domain-specific
embeddings to ensure that information extracted from the guidance image is not
ignored during translation, and cycle loss on images to improve semantic
consistency [8]. However, cycle-consistency losses on images have been shown
[8, 3] to force one-to-one unsupervised translation models to “cheat” by
hiding domain-specific attributes into translations.

Overall, prior methods ensure that the guide input modulates the translation
result in some non-trivial way, but, to our knowledge, no prior work
explicitly address adversarial embedding of domain-specific information into
the translated result, or ensures that domain-invariant factors are preserved
during translation, and this work fills this gap.

##  3 Restricted Information Flow for Translation

In this section we first formally introduce the many-to-many image translation
problem, and describe how our method solves it. Our model reconstructs input
images from translation results and domain-specific embeddings as illustrated
in Fig. 3, forcing domain-invariant information out of domain-specific
embedding using capacity losses, and forcing domain-specific information out
from the generated translation using honesty losses.

#### Setup.

Following [14], we assume that we have access to two unpaired image datasets
$A=\\{a_{i}\\}$ and $B=\\{b_{i}\\}$ that share some semantic structure, differ
visually (_e.g_. male and female faces with poses, backgrounds and skin color
varied in both). In addition to that, each domain has some attributes that
vary only within that domain, _e.g_. only males have variation in the amount
of facial hair and only females have variation in the hair color (like in
Figure 1). Our goal is to find a pair of guided cross-domain mappings
$F_{\text{A2B}}:A,B\to B$ and $F_{\text{B2A}}:B,A\to A$ such for any source
inputs $a_{s},b_{s}$ and guide inputs $a_{g},b_{g}$ from respective domains,
resulting guided cross-domain translations
$b^{\prime}=F_{\text{A2B}}(a_{s},b_{g})$ and
$a^{\prime}=F_{\text{B2A}}(b_{s},a_{g})$ look like plausible examples of
respective output domains, share domain-invariant factors with their “source”
arguments ($a_{s}$ and $b_{s}$ respectively) and domain-specific attributes
with their “guidance” arguments ($b_{g}$ and $a_{g}$ respectively). This
general setup covers the absolute majority of real-world image-to-image tasks.
For example, the correct guided female-to-male mapping $F_{\text{B2A}}$
applied to female source image $b_{s}$ and a guide male image $a_{g}$ should
generate a new male image $a^{\prime}$ with pose, background, skin color, and
other shared factors from the female input image $b_{s}$, and facial hair from
the guidance input $a_{g}$, because poses, backgrounds and skin color vary in
both, while facial hair is male-specific.

Figure 4:  Losses used to train RIFT. For illustration purposes, we use
3D-Shapes-A split described in Section 4 and illustrated in Figure 5. When the
model is trained, green arrows carry only B-specific information (floor and
wall color), blue arrows carry only A-specific information (orientation and
size), and red arrows carry information shared across two domains (object
color and shape).

#### Method.

While it might be possible to approximate functions $F_{\text{A2B}}$ and
$F_{\text{B2A}}$ directly, following prior work, we split each one into two
learnable parts: encoders $s_{A}(a),s_{B}(b)$ that extract domain-specific
information from corresponding guide images, and generators
$G_{\text{A2B}}(a,s_{b})$ and $G_{\text{B2A}}(b,s_{a})$ that combine that
domain-specific information with a corresponding source image, as illusrated
in Figure 4. Final many-to-many mappings are just compositions of encoders and
generators:

$\displaystyle F_{\text{A2B}}(a,b)=G_{\text{A2B}}(a,s_{B}(b)),\
F_{\text{B2A}}(b,a)=G_{\text{B2A}}(b,s_{A}(a))$

Our goal is to ensure that encoders $s_{*}$ extract all domain-specific
information from their inputs (and nothing more), and that generators $G_{*}$
use that information, along with domain-invariant factors from their source
inputs to form plausible images from corresponding domains.

#### Noisy cycle consistency loss.

First, to ensure that each attribute of input images is not ignored
completely, (_i.e_. that it is treated as either domain-specific, or domain-
invariant, or both), we use a guided analog of the cycle consistency loss.
This loss ensures that any image translated into a different domain, and
translated back with its original domain-specific embedding is reconstructed
perfectly. Additionally, as the first step towards restricting the amount of
information passed through each branch, we add zero-mean Gaussian noise
($\varepsilon$) of amplitude $\sigma_{s}$ or $\sigma_{g}$ and appropriate
shape to translations and domain-specific embeddings respectively, before
reconstructing images back:

$\displaystyle L_{\text{cyc}}^{A}=\mathbb{E}_{a,b}\ ||a_{\text{cyc}}-a||_{1},\
\ L_{\text{cyc}}^{B}=\mathbb{E}_{b,a}\ ||b_{\text{cyc}}-b||_{1}$
$\displaystyle
a_{\text{cyc}}=G_{\text{B2A}}(G_{\text{A2B}}(a,s_{B}(b)+\varepsilon_{g})+\varepsilon_{s},s_{A}(a)+\varepsilon_{g})$
$\displaystyle
b_{\text{cyc}}=G_{\text{A2B}}(G_{\text{B2A}}(b,s_{A}(a)+\varepsilon_{g})+\varepsilon_{s},s_{B}(b)+\varepsilon_{g})$
$\displaystyle a\sim A,\ b\sim B,\
\varepsilon_{s}\sim\mathcal{N}(0,\sigma_{s}),\
\varepsilon_{g}\sim\mathcal{N}(0,\sigma_{g})$

#### Translation honesty.

Unfortunately, any form of cycle loss encourages the model to “hide” domain-
specific information inside the translated image in the form of structured
adversarial noise [8]. To actively penalize the model for “hiding” the domain-
specific information, such as mustache, inside a generated female image
(instead of putting it into a male-specific embedding $s_{a}$), we use the
guess loss [3]. This loss detects and prevents this so-called “self-
adversarial attack” in the generator by training an additional discriminator
to “guess” which of its two inputs is a cycle-reconstruction and which is the
original image. For example, if the male-to-female generator $G_{\text{A2B}}$
is consistently adversarially embedding mustaches into all generated female
images, then the cycle-reconstructed female $b_{\text{cyc}}$ will also have
traces of an embedded mustache, and will be otherwise be identical to the
input $b$. In this case, the guess discriminator, trained specifically to
detect differences between input images and their cycle-reconstructions, will
detect this hidden signal and penalize the model:

$\displaystyle
L_{\text{guess}}^{A}=[D^{\text{gs}}_{A}(a,a_{\text{cyc}})]^{2}+[1-D^{\text{gs}}_{A}(a_{\text{cyc}},a)]^{2}$
$\displaystyle
L_{\text{guess}}^{B}=[D^{\text{gs}}_{B}(b,b_{\text{cyc}})]^{2}+[1-D^{\text{gs}}_{B}(b_{\text{cyc}},b)]^{2}$

#### Domain-specific channel capacity.

Unfortunately, neither of two losses described above can prevent the model
from learning to embed the entire guide image $a_{g}$ into the domain-specific
embeddings $s_{a}$ and reconstructing it from that embedding in
$G_{\text{B2A}}$, ignoring its first argument completely, _i.e_. just always
producing the guide input exactly. In order to prevent this from happening we
penalize norms of domain-specific embeddings, effectively constraining the
capacity of the resulting channel:

$\displaystyle L_{\text{norm}}^{A}=\mathbb{E}_{a}\ ||s_{A}(a)||_{2}^{2},\ \
L_{\text{norm}}^{B}=\mathbb{E}_{b}\ ||s_{B}(b)||_{2}^{2}$

Intuitively, the mutual information between the input guide image $a_{g}$ and
the predicted translation $a^{\prime}$ corresponds to the maximal amount of
information that an observer could learn about translations $a^{\prime}$ by
observing guides $a_{g}$ if they had infinite amount of examples to learn
from. Formally, using the derivation for the capacity of the additive white
Gaussian noise channel (Sec. 7.1) we can show that:

$\displaystyle\operatorname{MI}(a_{g};a^{\prime})\lesssim\operatorname{dim}(s_{A}(a))\cdot\log_{2}\left(1+L^{A}_{\text{norm}}/\sigma_{g}^{2}\right),$
$\displaystyle\text{ where
}a^{\prime}=G_{\text{B2A}}(b_{s},s_{A}(a_{g})+\varepsilon_{g}),\
\varepsilon_{g}\sim\mathcal{N}(0,\sigma_{g})$

meaning that minimizing $L^{A}_{\text{norm}}$ loss effectively limits the
amount of information from the guide image $a_{g}$ that $G_{\text{A2B}}$ can
access to generate $a^{\prime}$, _i.e_. the effective capacity of the domain-
specific embedding. Note that disabling either the noise ($\sigma_{g}=0$) or
the capacity loss ($L_{\text{norm}}\to\infty$) results in effectively infinite
capacity, so we need both. Intuitively, this bound describes the expected
number of “reliably distinguishable” embeddings that we can pack into a ball
of radius $\sqrt{L^{A}_{\text{norm}}}$ given that each embedding will be
perturbed by Gaussian noise with amplitude $\sigma_{g}$.

#### Realism losses.

Remaining losses are analogous to CycleGAN [19] losses that ensure that output
images lie within respective domains:

$\displaystyle
L_{\text{GAN}}^{A}=[D_{A}(a)]^{2}+\left[1-D_{A}(G_{\text{B2A}}(b,s_{A}(a)+\varepsilon_{s}^{a}))\right]^{2}$
$\displaystyle
L_{\text{GAN}}^{B}=[D_{B}(b)]^{2}+\left[1-D_{B}(G_{\text{A2B}}(a,s_{B}(b)+\varepsilon_{s}^{b}))\right]^{2}$
$\displaystyle L_{\text{idt}}^{A}=\mathbb{E}_{a}\
||G_{\text{B2A}}(a,s_{A}(a)+\varepsilon_{g})-a||_{1},$ $\displaystyle
L_{\text{idt}}^{B}=\mathbb{E}_{b}\
||G_{\text{A2B}}(b,s_{B}(b)+\varepsilon_{g})-b||_{1}$

#### Discriminator losses

We also train discriminator networks $D_{A},D_{B}$ and guess discriminators
$D_{A}^{\text{gs}},D_{B}^{\text{gs}}$ by minimizing corresponding adversarial
LS-GAN [22] losses.

##  4 Experiments

We would like to measure how well each model can generalize across a diverse
set of shared and domain-specific attributes. In this section we discuss
datasets we used and generated to achieve this goal, as well as list baselines
and metrics we used to compare our method to prior work.

Figure 5:  Shapes-3D-ABC splits with respective shared and domain-specific
attributes.

#### Data.

Following the protocol proposed by Bashkirova et al. [4], we re-purposed
existing disentanglement datasets to evaluate the ability of our method to
model different attributes as shared and domain-specific. We used 3D-Shapes
[16], SynAction [27] and CelebA [17]. Unfortunately, among the three, only
3D-Shapes [16] is balanced enough and contains enough labeled attributes to
make it possible to generate and evaluate all methods across several attribute
splits of comparable sizes. For example, if we attempted to build a split of
SynAction with domain-specific pose attribute, the domain with fixed pose
would only contain 90 unique images, which is not sufficient to train an
unsupervised translation network.

#### 3D-Shapes-ABC.

The original 3D-Shapes [16] dataset contains 40k synthetic images labeled with
six attributes: floor, wall and object colors, object shape and object size,
and orientation (viewpoint). There are ten possible values for each color
attribute, four possible values for the shape (cyliner, capsule, box, sphere),
fifteen values for orientation, and eight values for size. We used three
subsets of 3D-Shapes with different attribute splits visualized in Figure 5.
Three resulting domain pairs contained 4.8k/4k, 12k/3.2k, and 12k/6k images
respectively.

#### SynAction.

We used the same [4] split of SynAction [27] \- with background varied in one
domain (nine possible values), identity/clothing varied in the other (ten
possible values), and pose varied in both (real-valued vector). The resulting
dataset contains 5k images in one domain and 4.6k images in the other. We note
that the attribute split of this dataset matches the inductive bias of AdaIN
methods, since the layout (pose) is shared and textures (background, clothing)
are domain-specific in both domains.

#### CelebA.

We used the male-vs-female split proposed by [4] with 25k/25k images, and
evaluated disentanglement of six most visually prominent attributes: pose,
skin and background color (shared attributes, real-valued vectors), male-
specific presence of facial hair (binary), female-specific hair color (three
possible values), and domain-defining gender.

#### Baselines

We compare the proposed method against several state-of-art AdaIN methods,
namely MUNIT [14], StarGANv2 [7], MUNITX [4], and autoencoder-based methods,
namely Domain Intersection and Domain Difference (DIDD) [5], Augmented
CycleGAN [1] and DRIT++ [18]. In what follows we also provide a random
baseline (RAND) that corresponds to selecting and returning a random image
from the target domain.

#### Metrics

In order to evaluate the performance of our method, we measured how well the
domain-specific attributes were manipulated and domain-invariant attributes
were preserved. Following Bashkirova et al. [4] we trained an attribute
classifier $f(x)$, and for each attribute $k$, we measured the its
manipulation accuracy \- the probability of correctly modifying an attribute
across input-guide pairs for which the value of the attribute _must change_ :

$\text{ACC}_{k}^{\text{A}}=p(f_{k}(F_{\text{A2B}}(a,b))=y^{*}_{k}\ |\
f_{k}(a)\neq f_{k}(b))$

where the “correct” attribute value equals $y^{*}_{k}=f_{k}(a)$ for shared
attributes, and $y^{*}_{k}=f_{k}(b)$ otherwise. For real-valued multi-variate
attributes (pose keypoints, background RGB, skin RGB, etc.) we measured the
probability of generating an image with predicted attribute vector closer to
the correct attribute vector $y^{*}_{k}$ then to the incorrect vector:

$\text{ACC}_{k}^{\text{A}}=p(\|f_{k}(F_{\text{A2B}}(a,b))-y^{*}_{k}\|\leq\|f_{k}(F_{\text{A2B}}(a,b))-y^{\prime}_{k}\|)$

where $y^{*}_{k}=f_{k}(a)$ and $y^{\prime}_{k}=f_{k}(b)$ for shared
attributes, and vice-versa otherwise. The manipulation accuracy in the
opposite direction $\text{ACC}_{k}^{\text{B}}$ was estimated analogously. For
Shapes-3D we additionally aggregated results across three splits by averaging
manipulation accuracies across splits in which the given attribute was
shared/common (C) or domain-specific (S). If we introduce the set of all
splits $\mathcal{S}$ and predicates $\operatorname{common(k,s)}$ and
$\operatorname{specific(k,s,\text{dom})}$, and the manipulation accuracy at a
given split $\text{ACC}_{k}^{A}(s)$, aggregated manipulation accuracy can be
defined as follows:

$\displaystyle\text{ACC}_{k}^{S}=\frac{\sum_{d\in\\{\text{A, B}\\}}\sum_{s\in
S}\text{ACC}^{d}_{k}(s)\cdot\operatorname{specific(k,s,d)}}{\sum_{d\in\\{\text{A,
B}\\}}\sum_{s\in S}\operatorname{specific(k,s,d)}}$ (1)
$\displaystyle\text{ACC}_{k}^{C}=\frac{\sum_{d\in\\{\text{A, B}\\}}\sum_{s\in
S}\text{ACC}^{d}_{k}(s)\cdot\operatorname{common(k,s)}}{\sum_{d\in\\{\text{A,
B}\\}}\sum_{s\in S}\operatorname{common(k,s)}}$ (2)

For three splits of 3D-Shapes we also report the relative discrepancy between
domain-specific and domain-invariant manipulation accuracies:

$\displaystyle\text{RD}=100\cdot\frac{\sum_{k}|\text{ACC}^{S}_{k}-\text{ACC}^{C}_{k}|}{\sum_{k}(\text{ACC}^{S}_{k}+\text{ACC}^{C}_{k})}.$
(3)

#### Evaluation.

To compute metrics above, we generated two guided translations per source
image per domain per baseline. We re-ran each method multiple times to account
for poor initialization. We used PoseNet [24] to get ground truth poses for
SynAction, and Ruiz et al. [26] and median background and skin color for
CelebA, see suppl. Fig. 10.

#### Architecture.

We used standard CycleGAN components: pix2pix [15] generators and patch
discriminators with LS-GAN loss [22]. We archived best results when
represented domain-specific embedding vectors as single-channel images, and
made generators and encoders for the same domain (_e.g_. $G_{\text{A2B}}$ and
$s_{A}$) share all but last layers.

##  5 Results

In this section, we first compare our method to prior work both qualitatively
and quantitatively. Then we show what happens if we remove key losses
discussed Section 3. And finally, we discuss implicit assumptions made by our
method, and key challenges that future methods might encounter in further
improving manipulation accuracy across three datasets we used in this paper.

Figure 6: Qualitative results on CelebA. Methods should preserve pose and background of the source, and apply hair color of the female guide (top) and the facial hair of the male guide (bottom).  Method |  3D-Shapes[16]-ABC |  SynAction [27] |  CelebA [17] |
---|---|---|---|---
FC | WC | OC | SZ | SH | ORI | AVG | PS | IDT | BG | AVG | HC | FH | GD | ORI | BG | SC | AVG | AVG
C | S | C | S | C | S | C | S | C | S | C | S | AC$\uparrow$ | RD$\downarrow$ | C | S | S | AC$\uparrow$ | S | S | S | C | C | C | AC$\uparrow$ | AC$\uparrow\\!\\!\pm\\!\sigma$
StarGANv2 | 0 | 99 | 0 | 99 | 0 | 78 | 5 | 56 | 4 | 99 | 0 | 96 | 45 | 97 | 96 | 52 | 99 | 82 | 76 | 15 | 97 | 87 | 11 | 22 | 51 |  59$\pm$20
MUNIT | 5 | 94 | 0 | 99 | 0 | 97 | 59 | 31 | 96 | 58 | 99 | 61 | 58 | 56 | 75 | 28 | 7 | 37 | 45 | 7 | 90 | 89 | 43 | 44 | 53 |  49$\pm$11
MUNITX | 1 | 50 | 2 | 55 | 8 | 28 | 12 | 16 | 95 | 21 | 99 | 7 | 33 | 74 | 93 | 26 | 37 | 52 | 64 | 17 | 75 | 83 | 50 | 43 | 55 |  47$\pm$12
DRIT++ | 7 | 12 | 9 | 19 | 10 | 10 | 27 | 14 | 7 | 15 | 42 | 51 | 18 | 20 | 52 | 6 | 13 | 24 | 23 | 9 | 96 | 89 | 67 | 44 | 55 |  32$\pm$20
AugCycleGAN | 10 | 8 | 10 | 9 | 11 | 7 | 17 | 13 | 30 | 13 | 7 | 7 | 12 | 20 | 90 | 8 | 12 | 37 | 16 | 30 | 98 | 12 | 42 | 40 | 40 |  29$\pm$15
DIDD | 38 | 81 | 29 | 22 | 72 | 18 | 41 | 20 | 87 | 43 | 48 | 34 | 44 | 35 | 89 | 12 | 99 | 67 | 22 | 50 | 91 | 78 | 89 | 56 | 64 |  58$\pm$12
RIFT (ours) | 99 | 45 | 99 | 39 | 92 | 10 | 50 | 23 | 62 | 84 | 98 | 87 | 66 | 33 | 89 | 47 | 99 | 78 | 22 | 35 | 99 | 65 | 83 | 57 | 60 | 68$\pm$9
RAND | 10 | 10 | 10 | 10 | 10 | 10 | 12 | 19 | 24 | 19 | 6 | 6 | 12 | 9 | 50 | 11 | 11 | 24 | 12 | 31 | 99 | 50 | 50 | 50 | 49 |  27$\pm$20
Table 1: Manipulation accuracy for six attributes aggregated across three
splits of Shapes-3D: floor color (FC), wall color (WC), object color (OC),
size (SZ), shape (SH), room orientation (ORI); three attributes in SynAction:
pose (PS), identity/clothing (IDT), background (BG); and six attributes in
CelebA: hair color (HC), facial hair (FH), gender (GD), face orientation
(ORI), background (BG) and skin color (SC). We report per-attribute and
average manipulation accuracies for shared/common (C) or domain-specific (S)
attributes, as well as overall average aggregated manipulation accuracy (AC)
and relative discrepancy (RD) on 3D-Shapes described in Section 4. Table 2
with non-aggregated performance across three splits of 3D-Shapes can be found
in supplementary.

#### Qualitative results.

Figures 9 and 9 show that, in most cases, the proposed method successfully
preserves domain-invariant content and applies domain-specific attributes from
respective domains on 3D-Shapes and SynAction. Figure 6 shows that, on CelebA,
our method preserves poses and backgrounds, and applies hair color better then
other baselines. On 3D-Shapes-A, our method also preserves object color and
applies correct size and orientation better than all alternatives (Figure 2).
A more detailed side-by-side qualitative comparison of generated images across
all baselines and all datasets can be found in supp. Figures 26-36.

#### Quantitative results.

Table 1 shows that our method archives the highest average aggregate
manipulation accuracy across three splits of 3D-Shapes, and second lowest
relative discrepancy (RD) between accuracies of modeling same attributes as
shared and specific across all attributes. On SynAction, that matches the
inductive bias of AdaIN methods, our method performs on-par with AdaIN-based
methods and outperforms all non-AdaIN methods. On CelebA, our method is much
better at preserving background and skin colors then all AdaIN-based methods,
and, in terms of the overall manipulation accuracy is second only to DIDD [5].
Despite high manipulation scores, DIDD generated blurry faces and also
struggled with applying correct hair color, as can be seen in Figure 6 and
supplementary. To sum up, our method achieves best or second-best performance
in each of three dataset, and best performance overall (last column), with
among the lowest discrepancy between per-attribute manipulation accuracies
(RD), and lowest variance across datasets ($\pm\sigma$).

Figure 7:  Ablations. Effects of disabling capacity and honesty losses on
guided translations (top) and guided cycle-reconstructions (bottom) on
Shapes-3D-A. Inputs images from domains A and B, A2B and B2A guided
translations.

#### Ablations.

During B2A translation on Shapes-3D-A the model trained with all losses uses
object color/shape from the source image and floor/wall color from the guide
(Fig. 9). If we remove the penalty on the capacity of domain-specific
embeddings ($L_{\text{norm}}$), the model ignores the source input (Fig.
7a-top). The model encodes all attributes into domain-specific embeddings, and
cycle-reconstructs inputs $a$ and $b$ perfectly from these embeddings (Fig.
7a-bottom), completely ignoring the source input:
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color@cmyk@fill{0.64}{0}{0.95}{0.40}\bm{b}}={\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bm{F_{\text{A2B}}(a,b)}}=b_{\text{cyc}}$.
Removing honesty losses ($L_{\text{guess}}$), on the other hand, results in a
model that ignores the guide input altogether (Fig. 7b-top). The model “hides”
domain-specific information inside generated translations instead of the
domain-specific embeddings, and makes domain-specific embeddings equal zero,
resulting in zero capacity loss $L_{\text{norm}}=0$, and zero cycle
reconstruction loss $L_{\text{cyc}}=0$. For example (Fig. 7b-bottom), the size
and orientation of
${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\pgfsys@color@cmyk@stroke{0.64}{0}{0.95}{0.40}\pgfsys@color<EMAIL_ADDRESS>is hidden inside
${\color[rgb]{0.5,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,1}\pgfsys@color@cmyk@stroke{0.50}{1}{0}{0}\pgfsys@color@cmyk@fill{0.50}{1}{0}{0}\bm{F_{\text{B2A}}(b,a)}}$
in the form of imperceptible adversarial noise and is used to reconstruct
$b_{\text{cyc}}$ perfectly. If mapping $F_{\text{A2B}}$ actually used size and
orientation of $b$ to generate $b_{\text{cyc}}$, it would have also applied
that same size and orientation when generating
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\bm{F_{\text{A2B}}(a,b)}}$,
but it did not - so we conclude that both $F_{\text{A2B}}$ and
$F_{\text{B2A}}$ ignore domain-specific embeddings and embed information
inside generated translations instead. More illustrations in suppl. Figure 11.

#### Challenges.

We identified three major causes of remaining errors that existing methods
fail to handle at the moment, and future researchers will need to address to
make further progress in this task possible. First, some attributes “affect”
very different number of pixels in training images, and as a consequence
contribute very differently to reconstruction losses, making the job of
balancing different loss components much harder. For example, the floor color
in 3D-Shapes “affects” roughly half of all image pixels, whereas size affects
only one tenth of all pixels - resulting in drastically different effective
weights across all losses, especially if both are either domain-specific or
shared at the same time. This explains highest performance of our method on
3D-Shapes-A (in comparison to 3D-Shapes-B,C, see Table 2) which has
“similarly-sized” domain-specific attributes in both domains. The second
challenge is that all datasets contain some attribute combinations that are
almost distinguishable: for example, front-facing boxes and cylinders are
hardly distinguishable in 3D-Shapes, and clothing of people is much less
articulated when they are facing backwards because of shading in SynAction
(see suppl. Figure 12). This explains why our model fails on these cases:
since it can not reliably reconstruct these attributes from such intermediate
translations, it has no incentive to apply correct correct attributes values
to them in the first place. Finally, unevenly distributed shared attributes in
real world in-the-wild datasets (such as CelebA) pose even more serious
challenge rendering the whole many-to-many problem setup not well defined. For
example, if both male and female domains had hair color variation, but males
were mostly brunet with only 3% of blondes, and 50% of females were blondes -
should the model preserve blonde hair when translating females to males and
sacrifice the “realism” of the generated male domain, or should it treat hair-
color as a domain-specific attribute despite variations present in both?

#### Ethical considerations.

While more precise attribute manipulation models requiring less supervision
might be used for malicious deepfakes [23, 9], they can also be used to remove
biases present in existing datasets [11] to promote fairness in down-stream
tasks [2]. We acknowledge that the CelebA dataset contains many biases (_e.g_.
being predominantly white) and that binary gender labels are problematic.

Figure 8:  Guided translations generated by our method on 3D-Shapes-A. Our
model successfully preserves shared attributes (object color and shape) of the
source image and applies domain-specific attributes of the guide domain
(rotation and size on the left, floor and wall color on the right) in most
cases. It sometimes confuses boxes with cylinders, as discussed in challenges
paragraph.

Figure 9:  Guided translations generated by our method on SynAction. Our model
correctly preserve shared attributes (pose) of the source image and applies
domain-specific attributes of the guide domain (background texture on the
left, clothing/identity colors on the right). It sometimes applies wrong
clothing, especially in extreme poses, as discussed in challenges paragraph.

##  6 Conclusion

In this paper we propose RIFT - a new unsupervised many-to-many image-to-image
translation method that does not rely on an inductive bias hard-coded into its
architecture to determine which attributes are shared and which are domain-
specific, and achieves consistently high attribute manipulation accuracy
across a wide range of datasets with different kinds of domain-specific and
shared attributes, and low discrepancy between manipulation accuracies across
different attributes and datasets. Moreover, on datasets that match the
inductive bias of AdaIN-based methods, the proposed method performs on-par
with AdaIN-based methods. Finally, in this paper we identified three core
challenges that need to be resolved to enable further development of
unsupervised many-to-many image-to-image translation.

## References

  * Almahairi et al. [2018] Amjad Almahairi, Sai Rajeswar, Alessandro Sordoni, Philip Bachman, and Aaron Courville.  Augmented cyclegan: Learning many-to-many mappings from unpaired data.  _arXiv preprint arXiv:1802.10151_ , 2018.
  * Augenstein et al. [2019] Sean Augenstein, H Brendan McMahan, Daniel Ramage, Swaroop Ramaswamy, Peter Kairouz, Mingqing Chen, Rajiv Mathews, et al.  Generative models for effective ml on private, decentralized datasets.  _arXiv preprint arXiv:1911.06679_ , 2019.
  * Bashkirova et al. [2019] Dina Bashkirova, Ben Usman, and Kate Saenko.  Adversarial self-defense for cycle-consistent gans.  _in proceedings of the Thirty Second Conference on Advances in Neural Information Processing Systems_ , 2019.
  * Bashkirova et al. [2022] Dina Bashkirova, Ben Usman, and Kate Saenko.  Evaluation of correctness in unsupervised many-to-many image translation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2022.
  * Benaim et al. [2019] Sagie Benaim, Michael Khaitov, Tomer Galanti, and Lior Wolf.  Domain intersection and domain difference.  In _ICCV_ , 2019.
  * Cao et al. [2017] Yun Cao, Zhiming Zhou, Weinan Zhang, and Yong Yu.  Unsupervised diverse colorization via generative adversarial networks.  In _Joint European conference on machine learning and knowledge discovery in databases_ , pages 151–166. Springer, 2017.
  * Choi et al. [2020] Yunjey Choi, Youngjung Uh, Jaejun Yoo, and Jung-Woo Ha.  Stargan v2: Diverse image synthesis for multiple domains.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8188–8197, 2020.
  * Chu et al. [2017] Casey Chu, Andrey Zhmoginov, and Mark Sandler.  Cyclegan, a master of steganography.  _arXiv preprint arXiv:1712.02950_ , 2017.
  * Citron and Chesney [2018] Danielle K Citron and Robert Chesney.  Disinformation on steroids: The threat of deep fakes.  _Cyber Brief_ , 2018.
  * Gatys et al. [2015] Leon A Gatys, Alexander S Ecker, and Matthias Bethge.  A neural algorithm of artistic style.  _arXiv preprint arXiv:1508.06576_ , 2015.
  * Grover et al. [2019] Aditya Grover, Jiaming Song, Alekh Agarwal, Kenneth Tran, Ashish Kapoor, Eric Horvitz, and Stefano Ermon.  Bias correction of learned generative models using likelihood-free importance weighting.  _arXiv preprint arXiv:1906.09531_ , 2019.
  * Guadarrama et al. [2017] Sergio Guadarrama, Ryan Dahl, David Bieber, Mohammad Norouzi, Jonathon Shlens, and Kevin Murphy.  Pixcolor: Pixel recursive colorization.  _arXiv preprint arXiv:1705.07208_ , 2017.
  * Huang and Belongie [2017] Xun Huang and Serge Belongie.  Arbitrary style transfer in real-time with adaptive instance normalization.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pages 1501–1510, 2017.
  * Huang et al. [2018] Xun Huang, Ming-Yu Liu, Serge Belongie, and Jan Kautz.  Multimodal unsupervised image-to-image translation.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 172–189, 2018.
  * Isola et al. [2017] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1125–1134, 2017.
  * Kim and Mnih [2018] Hyunjik Kim and Andriy Mnih.  Disentangling by factorising.  In _International Conference on Machine Learning_ , pages 2649–2658. PMLR, 2018.
  * Lee et al. [2020] Cheng-Han Lee, Ziwei Liu, Lingyun Wu, and Ping Luo.  Maskgan: Towards diverse and interactive facial image manipulation.  In _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Lee et al. [2019] Hsin-Ying Lee, Hung-Yu Tseng, Qi Mao, Jia-Bin Huang, Yu-Ding Lu, Maneesh Kumar Singh, and Ming-Hsuan Yang.  Drit++: Diverse image-to-image translation viadisentangled representations.  _arXiv preprint arXiv:1905.01270_ , 2019.
  * Liu et al. [2017] Ming-Yu Liu, Thomas Breuel, and Jan Kautz.  Unsupervised image-to-image translation networks.  _arXiv preprint arXiv:1703.00848_ , 2017.
  * Liu et al. [2019] Ming-Yu Liu, Xun Huang, Arun Mallya, Tero Karras, Timo Aila, Jaakko Lehtinen, and Jan Kautz.  Few-shot unsueprvised image-to-image translation.  In _arxiv_ , 2019.
  * Lugmayr et al. [2019] Andreas Lugmayr, Martin Danelljan, and Radu Timofte.  Unsupervised learning for real-world super-resolution.  In _2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW)_ , pages 3408–3416. IEEE, 2019.
  * Mao et al. [2017] Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley.  Least squares generative adversarial networks.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2794–2802, 2017.
  * Nguyen et al. [2019] Thanh Thi Nguyen, Cuong M Nguyen, Dung Tien Nguyen, Duc Thanh Nguyen, and Saeid Nahavandi.  Deep learning for deepfakes creation and detection: A survey.  _arXiv preprint arXiv:1909.11573_ , 2019.
  * Papandreou et al. [2018] George Papandreou, Tyler Zhu, Liang-Chieh Chen, Spyros Gidaris, Jonathan Tompson, and Kevin Murphy.  Personlab: Person pose estimation and instance segmentation with a bottom-up, part-based, geometric embedding model.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 269–286, 2018.
  * Qu et al. [2018] Ying Qu, Hairong Qi, and Chiman Kwan.  Unsupervised sparse dirichlet-net for hyperspectral image super-resolution.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2511–2520, 2018.
  * Ruiz et al. [2018] Nataniel Ruiz, Eunji Chong, and James M. Rehg.  Fine-grained head pose estimation without keypoints.  In _The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops_ , June 2018.
  * Sun et al. [2020] Ximeng Sun, Huijuan Xu, and Kate Saenko.  Twostreamvan: Improving motion modeling in video generation.  In _The IEEE Winter Conference on Applications of Computer Vision_ , pages 2744–2753, 2020.
  * Ulyanov et al. [2016] Dmitry Ulyanov, Vadim Lebedev, Andrea Vedaldi, and Victor S Lempitsky.  Texture networks: Feed-forward synthesis of textures and stylized images.  In _ICML_ , volume 1, page 4, 2016.
  * Zhu et al. [2017] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2223–2232, 2017.

##  7 Supplementary

###  7.1 Derivation of the capacity

Let $A$ and $B$ be arbitrary datasets, $s$ and $G$ be domain-specific
embedding and generator functions, and $a^{\prime}$ be the translation from
source $b$ to domain $A$, guided by the target example $a$. The following
theorem bounds the amount of information about $a$ that $G$ can access to
generate $a^{\prime}$.

######  Theorem 1.

The effective capacity of the guided embedding, _i.e_. the capacity of the
$a\to a^{\prime}$ channel, _i.e_. the mutual information
$\operatorname{MI}(a;a^{\prime})$ is bounded by:

$\displaystyle\operatorname{MI}(a;a^{\prime})\lesssim\operatorname{dim}(s(a))\cdot\log_{2}\left(1+L/\sigma^{2}\right),$
$\displaystyle\text{ where }a^{\prime}=G(b,s(a)+\varepsilon),\
\varepsilon\sim\mathcal{N}(0,\sigma^{2}),$ $\displaystyle\text{ and
}L=\mathbb{E}\|s(a)\|_{2}^{2},\ a\sim A,\ b\sim B$

###### Proof.

First, let us define a Markov chain

$a\to s(a)\to(s(a)+\varepsilon)\to a^{\prime}$

using the data processing inequality twice we can show that

$\operatorname{MI}(a;a^{\prime})\leq\operatorname{MI}(a;s(a)+\varepsilon)\leq\operatorname{MI}(s(a);s(a)+\varepsilon)$

intuitively meaning that the overall pipeline always looses at least as much
information as each of its steps. Then expanding the mutual information in
terms of the differential entropy $h(X)$ gives us

$\displaystyle\operatorname{MI}(s(a);s(a)+\varepsilon)=h(s(a)+\varepsilon)-h(s(a)+\varepsilon|s(a))$
$\displaystyle=h(s(a)+\varepsilon)-h(\varepsilon)$

Since the the second raw moment (aka power) of $s(a)$ is bounded by $L$, the
entropy $h(s(a)+\varepsilon)$ will be maximized if $s(a)$ is a $k$-dimensional
spherical multivariate normal with variance $L$, where
$k=\operatorname{dim}(s(a))$ therefore

$\displaystyle\operatorname{MI}(s(a);s(a)+\varepsilon)\leq
h(\mathcal{N}_{k}(0;L+\sigma^{2}))+h(\mathcal{N}_{k}(0;\sigma^{2}))$
$\displaystyle=\frac{1}{2}\ln\left(\frac{(L+\sigma^{2})^{k}}{\sigma^{2k}}\right)\leq
k\cdot\log_{2}\left(1+L/\sigma^{2}\right).$

∎

Figure 10: Predictions of the attribute regression network on network
predictions on CelebA for hair color (black, brown or blonde), facial hair
(binary), background color (RGB), skin color (RGB), and face orientation (yaw;
pitch; roll).

Figure 11: Additional ablation visualizations on Shapes-3D-A. Without capacity losses (top) the model always embeds the entire guidance image into the domain-specific embedding and ignores the source input. Without honesty losses (bottom) it ignores the guide input and embeds domain-specific information into the translated image to reconstruct it back to minimize the cycle reconstruction losses.  Figure 12: Examples with indistinguishable attributes after translation cause instability in cycle reconstruction. For example, identities of actors with extreme poses are very dark and therefore hard to infer from translation results in SynAction; front-facing boxes and cylinders are almost indistinguishable too.  | Split A | Split B | Split C
---|---|---|---
| A | A | C | B | C | B | A | C | B | C | A | B | C | B | A | A | B | C
| FC | WC | OC | SZ | SH | ORI | FC | WC | OC | SZ | SH | ORI | FC | WC | OC | SZ | SH | ORI
MUNIT | 99 | 99 | 0 | 50 | 96 | 64 | 88 | 0 | 95 | 59 | 15 | 58 | 5 | 99 | 99 | 12 | 99 | 99
MUNITX | 10 | 9 | 8 | 18 | 95 | 8 | 89 | 2 | 11 | 12 | 8 | 6 | 1 | 99 | 45 | 13 | 33 | 99
DRIT | 13 | 16 | 10 | 14 | 7 | 95 | 10 | 9 | 7 | 27 | 8 | 6 | 7 | 21 | 12 | 13 | 22 | 42
AugCycleGAN | 10 | 9 | 11 | 13 | 30 | 7 | 5 | 10 | 5 | 17 | 0 | 7 | 10 | 9 | 9 | 13 | 26 | 7
StarGANv2 | 99 | 99 | 0 | 56 | 4 | 99 | 99 | 0 | 66 | 5 | 99 | 92 | 0 | 99 | 89 | 56 | 99 | 0
DIDD | 99 | 27 | 72 | 12 | 87 | 8 | 62 | 29 | 10 | 41 | 59 | 59 | 38 | 17 | 25 | 28 | 27 | 48
RIFT (ours) | 81 | 68 | 92 | 35 | 62 | 93 | 9 | 99 | 10 | 50 | 69 | 81 | 99 | 10 | 9 | 11 | 98 | 98
RAND | 10 | 9 | 10 | 12 | 24 | 6 | 10 | 10 | 9 | 12 | 25 | 6 | 10 | 10 | 10 | 25 | 12 | 6
Table 2: Per-split attribute manipulation accuracy on 3D-Shapes-ABC with
indicated attribute role (A, B - domain-specific; C - common/shared) across
six attributes floor color (FC), wall color (WC), object color (OC), size
(SZ), shape (SH), room orientation (ORI).

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 13: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 14: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 15: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 16: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 17: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT

Figure 18: Qualitative comparison to existing methods on Shapes-3D-A across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT Figure 19: Qualitative
comparison to existing methods on SynAction across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. The rightmost column shows ground truth predictions for
that domain pair. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT
Figure 20: Qualitative comparison to existing methods on SynAction across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT Figure 21: Qualitative
comparison to existing methods on SynAction across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. The rightmost column shows ground truth predictions for
that domain pair. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT
Figure 22: Qualitative comparison to existing methods on SynAction across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT Figure 23: Qualitative
comparison to existing methods on SynAction across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. The rightmost column shows ground truth predictions for
that domain pair. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT
Figure 24: Qualitative comparison to existing methods on SynAction across
seven methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14],
MUNITX [4], StarGANv2 [7] and the proposed RIFT. The rightmost column shows
ground truth predictions for that domain pair.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFTGT Figure 25: Qualitative
comparison to existing methods on SynAction across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. The rightmost column shows ground truth predictions for
that domain pair. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
26: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure 27: Qualitative
comparison to existing methods on Celeb-A across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
28: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure 29: Qualitative
comparison to existing methods on Celeb-A across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
30: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure 31: Qualitative
comparison to existing methods on Celeb-A across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
32: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure 33: Qualitative
comparison to existing methods on Celeb-A across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
34: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.
inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure 35: Qualitative
comparison to existing methods on Celeb-A across seven methods: Augmented
CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX [4], StarGANv2 [7] and
the proposed RIFT. inputguidanceAugCGDRIT++DIDDMUNITMUNITXStarGANv2RIFT Figure
36: Qualitative comparison to existing methods on Celeb-A across seven
methods: Augmented CycleGAN [1], DRIT++ [18], DIDD [5], MUNIT [14], MUNITX
[4], StarGANv2 [7] and the proposed RIFT.


11institutetext: Kent State University, Kent, OH, 44242, USA
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>and 11email:
<EMAIL_ADDRESS>
# Blockchain in Dynamic Networks

Rachel Bricker  Mikhail Nesterenko  Gokarna Sharma

###### Abstract

We consider blockchain in dynamic networks. We define the Blockchain Decision
Problem. It requires miners that maintain the blockchain to confirm whether a
particular block is accepted. We establish the necessary conditions for the
existence of a solution. We, however, prove that the solution, even under
these necessary conditions is, in general, impossible. We then present two
algorithms that solve the Blockchain Decision Problem under either the
knowledge of the maximum source pool propagation time or the knowledge of the
source pool membership. We evaluate the performance of the two algorithms.

###### Keywords:

Dynamic Networks Blockchain

##  1 Introduction

Blockchain is a means of organizing a decentralized public ledger. The lack of
centralized controller potentially makes the blockchain more resilient to
network failures and attacks. Blockchain is a popular architecture for a
number of applications such as cryptocurrency [17, 22], massive Internet-of-
Things storage [2] and electronic voting [9].

The major problem of maintaining this ledger is for the participants to
achieve consensus on its records despite faults or hostile environment.
Classic robust consensus algorithms [5, 15] use cooperative message exchanges
between peer processes to arrive at a joint decision. However, such algorithms
require that each process is aware of all the other processes in the network.
In a system with flexible membership, such requirement may be excessive. An
alternative is competitive consensus [17] where processes race to have records
that they generated added to the blockchain. This competition does not require
fixed membership and provides defense against attacks and faults.

Ordinarily, the network underlying the blockchain is considered to be always
connected. However, as blockchain finds greater acceptance and new
applications, this assumption may no longer be considered as a given. Instead,
the blockchain operation under less reliable communication conditions needs to
be examined.

A dynamic network assumes that a connection between any two processes may
appear and disappear at any moment. Therefore, the network connectivity graph
changes arbitrarily from one point of the computation to the next. This is the
least restrictive network connectivity assumption. This paper studies
operation of blockchain in dynamic networks.

Related work. An area related to dynamic networks is population protocols,
where passive agents do not control their movement but may exchange
information as they encounter each other. See Michail et al. [16] for an
introduction to the topic. A system with arbitrary link failures was
considered by Santoro and Widmayer [20]. There are several papers that explore
the model of link failures in greater detail [1, 6, 8].

The network that dynamically changes in an arbitrary manner, possibly to the
detriment of the problem to be solved, was first formally studied by O’Dell
and Wattenhofer [18]. This topic is explored in Kuhn et al. [13]. Several
studies [4, 10] investigate reliable broadcast in dynamic networks with
Byzantine faults. There is a large body of literature on cooperative consensus
in dynamic networks [3, 14, 21]. In particular, Winkler et al. [21] explored
the concept of an eventually stably communicating root component necessary for
consensus. This is similar to the concept of source communication pool that we
introduce in this paper.

There are some applied studies [7, 12] that consider the operation of
blockchain that tolerates extensive delays or temporary disconnections. Hood
et al. [11] explored in detail the blockchain operation under network
partitioning.

However, to the best of our knowledge, this paper is the first to study
blockchain in dynamic networks.

Paper organization and contribution. In Section 2, we introduce the notation
and state the Blockchain Decision Problem for dynamic networks: every network
miner needs to confirm the acceptance of each block. In Section 3, we
establish the conditions for blockchain and the dynamic network so that the
problem is at all solvable: there needs to be a single source pool of
continuously interacting miners that propagate the blocks they generate to the
rest of the network and none of the other miners may generate infinitely many
blocks and propagate them back to the source pool. In Section 4, we prove that
in general, even if these conditions are met, the problem is impossible to
solve. Intuitively, miners may not determine when these outside blocks stop
coming. In Section 5, we present two algorithms that solve the problem with
restrictions: _KPT_ – if maximum message propagation time is known to all
miners, _KSM_ – if source pool membership is known to all miners. We evaluate
the performance of the two algorithms in Section 7. We conclude the paper by
Section 8.

##  2 Notation, Definitions and Problem Statement

Network. A network $N$ consists of a fixed number of processes or _miners_.
Each miner has a unique identifier which may or may not be known to the other
miners in the beginning. The network computation proceeds in synchronous
rounds. Miners communicate via message passing over uni-directional links
connecting the sender miner $m_{s}$ and receiver miner $m_{r}$. This is
denoted as $m_{s}\rightarrow m_{r}$. The network is dynamic as links may
appear or disappear. More specifically, at the beginning of each round $i$,
the receiver miner receives all messages sent to it during the previous round,
then carries out calculations and submits messages over the links that exist
in round $i$ to be received in the next round. A _computation_ is a, possibly
infinite, sequence of such rounds.

To simplify the presentation, we first assume that the communication is
instantaneous. That is, all the information sent over the link is received in
the same round. We also assume that arbitrary amount of information may be
communicated in one message. We relax these assumptions later in the paper.

A _journey_ in a computation is a sequence of miners and communication links
$m_{1}\rightarrow\cdots\rightarrow m_{i}\rightarrow m_{i+1}\rightarrow
m_{i+2}\rightarrow\cdots\rightarrow m_{x}$ such that each round $i$ of the
computation, where link $m_{i}\rightarrow m_{i+1}$ exists, precedes the round
with link $m_{i+1}\rightarrow m_{i+2}$. _Journey time_ is the number of
computation rounds between the first and last link in the journey. Note that
journey time may be greater than the total number of links in the journey
since it may take more than one round for each subsequent link in the journey
to appear.

Figure 1: Blockchain notation illustration. Block $g$ is genesis. Block $a$ is
rejected because it is an ancestor to only finitely many blocks.
Alternatively, $a$ belongs to finite branches only. Block $b$ is accepted
since it is an ancestor to infinitely many blocks. That is, $b$ belongs to
infinite branches. Block $a$ is a cousin of block of $b$. In an infinite
blockchain, $b$ is accepted if all its cousin branches are finite.

Blockchain. The introduced terms are illustrated in Figure 1. _Blockchain_ is
a tree of linked _blocks_. Each mined block is unique and can be distinguished
from the others. Further block contents is immaterial. A block may be linked
to a single _parent block_. A _child_ is a block linked to a parent. _Genesis_
is the root of the tree and the only block without a parent. A _leaf_ is the
block with no children. An _ancestor_ of a block $b$ is either a parent of $b$
or, recursively, an ancestor of $b$. A _descendant_ of a block $b$ is any
block whose ancestor is $b$. The _depth_ of a block is the number of its
ancestors.

A _branch_ is the maximal sequence of blocks
$b_{1},\cdots,b_{i},b_{i+1},\cdots$ such that $b_{1}$ is the genesis and for
each $i$, $b_{i}$ is the parent of $b_{i+1}$. By this definition, either a
branch is infinite or it ends with a leaf. Given a block $b$ that belongs to a
branch, all blocks preceding $b$ in this branch are its ancestors and all
blocks following $b$ are its descendants. The _length_ of a finite branch is
the depth of its leaf. The length of an infinite branch is infinite.

A _trunk_ of two branches is their longest shared prefix. Thus, the trunk of
any two branches is at least the genesis. A branch is a trunk of itself. The
blocks of the trunk belong to the branches that share this trunk. Consider a
block $b$ that does not belong to the shared trunk of the two branches.
_Cousins_ of $b$ are the blocks that belong to these branches but neither
descendants nor ancestors of $b$. These blocks belong to a _cousin branch_.

Each miner in the network stores all the blockchain blocks known to it. That
is, miners maintain local copies of the blockchain. In the beginning of each
computation, each miner stores the same genesis. Due to the haphazard link
appearance in a dynamic network, local copies of the blockchain may be out of
sync.

In an arbitrary round, a miner $m$ may generate or _mine_ a new block $b$
linked to the longest branch of the local copy of the blockchain. If $m$ has
several branches of the same length, the new block may be mined on any one of
them. Multiple processes may mine blocks in the same round. Once linked, the
sender sends its entire copy of the blockchain to the receiver. We discuss how
to limit the amount of transmitted information later in the paper. By this
operation, the number of children for any block, i.e. the arity of the
blockchain, is at most $|N|$.

We place few assumptions on the relationship between the relative speed of
communication and block mining. However, we assume the following fairness:
throughout the computation, a miner either receives infinitely many new blocks
or mines infinite many blocks itself. A miner subject to this assumption is a
_fair miner_ , it is an _unfair miner_ otherwise.

The Blockchain Decision Problem. A block is _accepted_ if it is the ancestor
of all but finitely many blocks. A block is _rejected_ if it is the ancestor
of finitely many blocks.

In the attempt to agree on the common state of the blockchain, each miner
decides whether the block is accepted by outputting a _confirm_ decision. The
decision about block rejection is implied and is not required. To arrive at
this decision, the miners may store and exchange arbitrary information. We use
the term computation for block mining and blockchain maintenance as well as
for the operation of the algorithm that allows the miners to output decision
about the blocks of this blockchain. We formulate the decision problem as
follows.

######  Definition 1 (The Blockchain Decision Problem _BDP_)

A solution to the Blockchain Decision Problem satisfies the following
properties:

Decision:

each miner eventually confirms every accepted block;

Confirmation Validity:

each miner confirms only accepted blocks.

##  3 Decisive Computations

Globally decisive computations. A computation is _globally decisive_ if every
block of its blockchain is uniquely categorized: either accepted or rejected
but not both at once.

###### Lemma 1

The blockchain of a globally decisive computation has exactly one infinite
branch.

To put the lemma another way: in a decisive computation, all branches except
for one are finite.

###### Proof

The blockchains that do not conform to the conditions of the lemma either have
no infinite branches or have more than one. If a blockchain does not have
infinite branches at all, then it has a finite number of blocks. In this case,
every block $b$ is the ancestor of finitely many blocks. That is, $b$ is
rejected. However, $b$ is also an ancestor of all but finitely many blocks.
That is, $b$ is also simultaneously accepted. In a globally decisive
computation, a block may be either accepted or rejected but not both.

Let us consider the second case of a blockchain not conforming to the
conditions of the lemma: it has multiple infinite branches. Let block $b$
belong to one such branch but not to the shared trunk of all the branches.
Since $b$ belongs to an infinite branch, it is an ancestor to an infinite
number of blocks. Therefore, $b$ is not rejected. However, there are infinite
number of blocks in the infinite cousin branches, i.e. the branches to which
$b$ does not belong. That is, $b$ is not an ancestor to an infinite number of
blocks. Hence, $b$ is not accepted either.

That is, a blockchain with unique categorization of acceptance of rejection
has exactly one infinite branch. A computation must have such a blockchain to
be decisive. The lemma follows. $\Box$

Mining pools. In a certain computation, a _mining pool_ $M$ is a maximal set
of miners such that each miner $m\in M$ has an infinite number of journeys to
every other miner in $M$. That is, each miner in a pool is reachable from
every other miner in this pool infinitely often. If, for some miner $m$, there
are no other miners that are mutually reachable infinitely often, then $m$
forms a pool by itself.

A pool graph $\cal PG$ for a computation $C$ is a static directed graph formed
as follows. Each node in $\cal PG$ corresponds to a mining pool in $C$. An
edge from node $P_{1}\in\cal PG$ to node $P_{2}\in\cal PG$ exists if there is
an infinite number of edges from miners of pool $P_{1}$ to the miners of the
pool $P_{2}$.

Let us observe that any pool graph $\cal PG$ is a DAG. Indeed, if there is
cycle in $\cal PG$, then any miner $m_{1}$ has an infinite number of journeys
to any other miner $m_{2}$ in this cycle. Since mining pools are maximal,
these miners belong to the same pool. If $\cal PG$ has a path from pool
$P_{1}$ to pool $P_{2}$, then any miner $m_{1}\in P_{1}$ has an infinite
number of journeys to any miner $m_{2}\in P_{2}$. If it does not, then the
number of journeys between $P_{1}$ and $P_{2}$ is finite.

A node in a static graph is a source if it has no incoming edges. Since a DAG
has no cycles, it has at least one source. A _source pool_ is a pool that
corresponds to a source in $\cal PG$. An infinite branch _belongs_ to a pool
if it contains a suffix of blocks where every block is mined by a member of
this pool.

###### Lemma 2

If the blockchain of a computation contains an infinite branch, this branch
belongs to a single pool.

###### Proof

Assume that there is a computation $C$ whose blockchain has an infinite branch
$BR$ that does not belong to a single pool. That is, branch $BR$ contains
infinitely many blocks mined by miners in at least two separate pools $P_{1}$
and $P_{2}$. The pool graph $\cal PG$ of $C$ contains no cycles. That means
that there is a path from one pool to the other but not back. Suppose, without
loss of generality, that there is no path from $P_{1}$ to $P_{2}$. This means
that there is a finite number of journeys from miners of $P_{1}$ to $P_{2}$ in
$C$. Let round $r$ be the last round of $C$ that contains the journey from
$P_{1}$ to $P_{2}$. However, there are infinitely many blocks in $BR$ that are
mined by miners in $P_{1}$ and in $P_{2}$. Consider two blocks $b_{1}$ and
$b_{2}$ of $BR$ mined after round $r$ such that $b_{1}$ is mined by miner
$m_{1}\in P_{1}$ and $b_{2}$ by miner $m_{2}\in P_{2}$. Moreover, $b_{1}$ is
the ancestor of $b_{2}$. If this is the case, there is a journey from $m_{1}$
to $m_{2}$ in $C$. However, we assumed that there are no such journeys after
round $r$ in $C$. That is, our assumption is incorrect and $C$ does not exist.
This proves the lemma. $\Box$

Locally decisive computations. A computation is _locally decisive_ if it is
globally decisive and each miner receives every accepted block.

###### Lemma 3

In a locally decisive computation, infinite branches belong to a source pool.

###### Proof

Assume that there is a locally decisive computation $C$ whose blockchain
contains an infinite branch $BR$ that does not belong to source pools of $C$.
According to Lemma 2, $BR$ belongs to some pool $P$. Since the pool graph of
$C$ is a DAG, it must have a source pool $SP$. A source pool has a finite
number of journeys from the miners outside itself.

Computation $C$ is locally decisive. This means that all miners, including the
miners in $SP$, receive all blocks in $BR$. Yet, $BR$ is infinite. This means
that there are infinitely many journeys from miners in $P$ to the miners in
$SP$. This means, contrary to our initial assumption, that $SP$ is not a
source pool. $\Box$

###### Lemma 4

In a locally decisive computation, there is a single source pool.

###### Proof

Assume the opposite: there is a locally decisive computation $C$ with at least
two source pools: $SP_{1}$ and $SP_{2}$. Since a locally decisive computation
is also a globally decisive computation, according to Lemma 1, $C$ contains a
single infinite branch. According to Lemma 2, this branch belongs to a single
pool and, according to Lemma 3, this pool is a source. That is, the infinite
branch belongs to either $SP_{1}$ or $SP_{2}$. Let it be $SP_{1}$. This means
that miners of $SP_{1}$ mine infinitely many blocks that belong to the
infinite branch. Since $C$ is globally decisive, these blocks are accepted.

However, $SP_{2}$ is also a source, this means that it has a finite number of
journeys from miners outside itself. Yet, since $C$ is locally decisive, the
miners in $SP_{2}$ need to receive the infinite number of blocks mined in
$SP_{1}$. That is, there are infinite number of journeys from the miners of
$SP_{1}$ to the miners of $SP_{2}$. That is, $SP_{2}$ is not a source. $\Box$

The following theorem summarizes the results proven in Lemmas 1, 2, 3 and 4.

###### Theorem 3.1

If a computation is globally and locally decisive, then it has exactly one
infinite branch and one source pool. Moreover, this infinite branch belongs to
this source pool.

##  4 Impossibility

In a solution to the Blockchain Decision Problem, every miner is required to
confirm each accepted block. Theorem 3.1 states necessary conditions for the
possibility of the solution. Yet, even if these conditions are satisfied, a
miner may make a mistake. Indeed, assume a miner $m$ determines that a certain
block $b$ belongs to the longest branches of all processes in the source pool.
Miner $m$ confirms it. Yet, a non-source pool miner may later mine a longer
cousin branch to $b$, communicate it to the source pool forcing rejection of
$b$. This makes $m$’s confirmation incorrect. Even though, by definition of
the source pool, such links from the outside happen only finitely many times,
the time they stop is not predictable. This makes the solution, in the general
case, impossible. The below theorem formalizes this intuition.

###### Theorem 4.1

There does not exist a solution to the Blockchain Decision Problem even for
globally and locally decisive computations.

###### Proof

Assume there is an algorithm $A$ that solves _BDP_ for globally and locally
decisive computations. Consider a globally and locally decisive computation
$C_{x}$ which contains mining pools $P_{1}$ and $P_{2}$ such that $P_{1}$ is
the source pool.

Since $C_{x}$ is globally and locally decisive, according to Theorem 3.1, it
has a single infinite branch, a single source pool and the branch belongs to
this source pool. This means that there are infinite number of blocks in the
infinite branch. All these blocks are accepted. After some round $r_{1}$ they
must be mined in $P_{1}$. Let block $b$ be one such block. Since the
computation is locally decisive, $b$ has to reach miners in $P_{2}$. The
Decision Property of _BDP_ requires that all miners eventually confirm
accepted blocks. This means that miners of $P_{2}$ have to eventually confirm
$b$. Let $r_{2}$ be the round where some miner $m_{2}\in P_{2}$ confirms $b$
in $C_{x}$.

Consider a computation $C_{y}$ that has an extra pool $P_{3}$. Communication
in $C_{y}$ is as follows. Miners of pool $P_{3}$ have no links to the outside
miners until round $r_{2}$. Since the miners of $P_{3}$ do not influence other
miners, we construct $C_{y}$ such that up to the round $r_{2}$, the actions of
miners of $P_{1}$ and of $P_{2}$ are the same as in $C_{x}$. This includes
$m_{2}$ confirming block $b$. We construct the remainder of $C_{y}$ as
follows. Miners of $P_{3}$ have only outgoing links to miners of $P_{1}$ and
$P_{2}$ for the remainder of $C_{y}$. That is, $P_{3}$ is a source. We
construct $C_{y}$ to be locally and globally decisive. That is, we make
$P_{3}$ its own single infinite branch.

By construction, miners of $P_{1}$ never send messages to miners of $P_{3}$.
This means that block $b$ mined in $P_{2}$ does not reach $P_{3}$. Hence, $b$
does not belong to the infinite branch. Therefore, $b$ is rejected. However,
miner $m_{2}$ confirms it in $C_{x}$ and, therefore, in $C_{y}$. This is
contrary to the Confirmation Validity property of _BDP_ , which stipulates
that miners may confirm only accepted blocks. Thus, despite our initial
assumption, algorithm $A$ does not solve the Blockchain Decision Problem.
Hence, the theorem. $\Box$

##  5 Solutions

Previously, we considered completely formed infinite blockchain trees.
However, to solve the Blockchain Decision Problem, individual miners have to
make decisions whether a particular block is accepted or rejected on the basis
of a tree that is not yet complete. Moreover, a miner may not be aware of some
already mined blocks due to propagation delays. To describe this uncertainty,
we introduce additional notation.

A branch $BR$ is _dead_ if all miners are mining on cousin branches longer
than $BR$. A branch is _live_ otherwise. Notice that once a branch is dead, it
may not become live. Thus, a block belongs to dead branches only, it is
rejected. In an infinite computation, a block is accepted if it belongs to all
infinite branches. To put another way, a block is accepted if all its cousin
branches are dead. The algorithms in this section exploit the miners’ ability
to detect dead branches to confirm accepted blocks.

Per Theorem 4.1, the solution to the Blockchain Decision Problem is impossible
if non-source-pool miners are able to send their mined blocks to the source
pool. We, therefore, consider the following restriction. A mining pool is
_initially closed_ if its members do not have incoming edges from non-pool
members. If source pool is initially closed, to evaluate whether the branch is
dead, it is sufficient to consider blocks generated by source pool miners
only.

Known propagation time. Let $m$ be an arbitrary miner in the source pool.
_Source pool propagation time_ $PT$ is the time of the longest journey from
$m$ to any other miner in the network. If $PT$ is fixed, it takes at most $PT$
rounds for a message sent by $m$ to reach all miners. If $PT$ is known, the
solution to _BDP_ seems straightforward as dead branches eventually become
shorter than live ones. However, this solution is not immediate since, even
with fixed $PT$, the length difference between live branches may be
arbitrarily large. Indeed, a miner may mine a number of blocks extending its
branch length significantly. However, other miners may subsequently mine on
their branches catching up and keeping their branches live.

1

2Constants:

3 $p$ // miner identifier

4 $PT$ // source pool propagation time, integer

5 Variables:

6 $T$ // blockchain tree, initially genesis

$L$ // set of tuples $\langle b,l\rangle$, where $b\in T$ and $l$ is either
accept or reject initially $\varnothing$, if $b\in T$ and $b\not\in L$, then
$b$ is unlabeled

7 Actions:

8 if  _mined block $b$_ then

9 add $b$ to $T$

10if  _available link to miner $q$_ then

11 send $T$ to $q$

12if  _receive $T_{q}$ from miner $q$_ then

13 merge $T$ and $T_{q}$

14if  _exists unlabeled $b_{1}$ such that for every $BR(b_{1})$, there is a
cousin bock $b_{2}$ such that $depth(b_{2})>BR(b_{1})$ for at least $2\cdot
PT$ rounds_ then

15 add $\langle b_{1},\textnormal{{reject}}\rangle$ to $L$

16if  _exists unlabeled $b$ such that for its every cousin $c$: $\langle
c,\textnormal{{reject}}\rangle\in L$ _ then

17 add $\langle b,\textnormal{{accept}}\rangle$ to $L$

18 confirm $b$

Algorithm 1 Known Source Pool Propagation Time Algorithm KPT.

Instead, to detect a dead branch, the algorithm that solves _BDP_ , relies on
the branch length difference over a certain period of time. We call this
algorithm _KPT_. Its code is shown in Figure 1. The algorithm operates as
follows. Each miner $p$ maintains the local copy of the blockchain tree $T$
and a set of per-block labels $L$ where it stores decisions whether the block
is accepted or rejected. If the decision is not reached, the block is
unlabeled. Once block $b$ is mined, it is added to the tree $T$. If a link to
some miner $q$ appears, miner $p$ sends its entire blockchain to $q$.

The decisions are reached as follows. An unlabeled block $b_{1}$ is labeled
rejected if for its every branch $BR(b_{1})$ the following happens. There is a
cousin block $b_{2}$ such that the depth of $b_{2}$ is greater than the length
of this branch $BR(b_{1}$) for at least $2\cdot PT$ rounds. An unlabeled block
$b$ is accepted if all its cousins are rejected. In the latter case, $b$ is
confirmed.

###### Lemma 5

Let, at some round $r$, some miner $m$ observe that there is a block $b$ whose
depth is greater than the length of its cousin branch $BR$. If $b$’s depth is
still greater than the length of $BR$ at round $r+2\cdot PT$, then $BR$ is
dead.

###### Proof

Assume block $b$ is mined by miner $m_{b}$ of the source pool in round
$r_{b}$. Since the maximum source pool propagation time $PT$ is fixed, in
round $r_{b}+PT$ every miner receives $b$. If there is a branch $BR$ that is
shorter than the depth of $m_{b}$ in round $r_{b}+PT$, then every miner
$m_{c}$ that mines on branch $BR$ or shorter branches, switches to a branch
that contains $b$ or a longer branch. That is, $BR$ is dead by $r_{b}+PT$.
Therefore, blocks may be mined on $BR$ no longer than round $r_{b}+PT$. It
takes any block at most $PT$ rounds to propagate to all miners in the network.

Let us consider an arbitrary miner $m$. Since $b$ is mined in round $r_{b}$,
the earliest round when $m$ may receive $b$ is also $r_{b}$. That is, if some
miner $m$ observes that there is a block whose depth is greater than some
branch for $2\cdot PT$ rounds, then this branch is dead. $\Box$

###### Theorem 5.1

Known Source Pool Propagation Time Algorithm KPT solves the Blockchain
Decision Problem with initially closed source pool.

###### Proof

Let us consider the Confirmation Validity Property of _BDP_. According to
Lemma 5, If $PT$ is known and if miner $p$ observes that some block is deeper
than the height of a branch for longer than $2\cdot PT$ rounds, then this
branch is dead. If some block belongs to dead branches only, it is rejected.
This is the exact condition under which blocks are labeled rejected in _KPT_ ,
see Line 1. If all cousins are rejected, the block is accepted. This is how
the is block is labeled accepted and confirmed in _KPT_ , see Line 1. To put
another way, _KPT_ confirms only accepted blocks which satisfies the
Confirmation Validity Property of _BDP_.

Let us now discuss the Decision Property and show that every accepted block is
eventually confirmed. Indeed, according to Lemma 5, a miner determines that a
branch is dead in at most $2\cdot PT$ rounds. A block is rejected once all
branches that it belongs to are dead. That is, a block rejection is determined
in this many rounds after the last branch of the block is dead.

A block is labeled accepted and then confirmed after all its cousins are
rejected. To put another way, a block is accepted after at most $2\cdot PT$
rounds of the rejection of the last cousin block. This proves that all
accepted blocks are eventually confirmed and _KPT_ satisfies the Decision
Property of _BDP_. $\Box$

Let us describe a couple of simple enhancements of _KPT_. Since miners never
make mistakes in their classification of reject and accept, a miner may send
its label set $L$ to help its neighbors make their decisions faster. Also, a
miner may determine dead branches quicker if each block is labeled with the
round of its mining. In this case, to ascertain that a certain branch $BR$ is
dead, it is sufficient to check if there is a cousin block $b_{2}$ such that
$BR$ does not outgrow $b_{2}$ for $PT$ rounds.

Known source pool membership. Miner _position_ in a blockchain tree is the
block on which it is currently mining. Note that the depth of a miner’s
position throughout the computation may only increase. Once it is observed
that all source pool miners moved to positions longer than a particular
branch, the source pool miners may not mine on this branch. That is, the
branch is dead. We state this formally in the following lemma.

###### Lemma 6

If some miner $m$ observes that there is a branch $BR$ such that the depth of
the position of every source pool miner is greater than the length of $BR$,
then $BR$ is dead.

1

2Constants:

3 $p$ // miner identifier

4 $SM$ // set of ids of source pool miners

5 Variables:

6 $T$ // blockchain tree, initially genesis

$P$ // set of tuples $\langle b,m\rangle$, where $b\in T$ and $m\in SM$,
initially $\varnothing$, positions of source pool miners

$L$ // set of tuples $\langle b,l\rangle$, where $b\in T$ and $l$ is either
accept or reject initially $\varnothing$, if $b\in T$ and $b\not\in L$, then
$b$ is unlabeled, block labels

7 Actions:

8 if  _mined block $b$_ then

9 add $b$ to $T$

10 if  _$p\in SM$_ then

11 update $p$’s entry in $P$ to $\langle b,p\rangle$

12

13if  _available link to miner $q$_ then

14 send $T,P$ to $q$

15if  _receive $T_{q},P_{q}$ from miner $q$_ then

16 merge $T$ and $T_{q}$, merge $P$ and $P_{q}$

17 if  _$p\in SM$_ then

18 let $b$ be the deepest block in $T$

19 update $p$’s entry in $P$ to $\langle b,p\rangle$

20

21if  _exists unlabeled $b_{1}$ such that for every $BR(b_{1})$, for all $m\in
SM$ there exists $\langle b_{2},m\rangle\in P$ such that
$depth(b_{2})>BR(b_{1})$_ then

22 add $\langle b_{1},\textnormal{{reject}}\rangle$ to $L$

23if  _exists unlabeled $b$ such that all cousins of $b$ are reject_ then

24 add $\langle b,\textnormal{{accept}}\rangle$ to $L$

25 confirm $b$

Algorithm 2 Known Source Pool Membership Algorithm KSM.

Determining source pool miner positions directly from mined blocks in the
blockchain is not always possible: some source pool miner, even if it is fair,
may never mine a block if it keeps receiving longer branches. Instead, the
below algorithm relies on miners directly reporting their positions. We call
this algorithm _KSM_. Its code is shown in Figure 2. Similar to _KPT_ , it
maintains the blockchain tree $T$ and a set of accept/reject labels per each
block $L$. Besdies those, _KSM_ also maintains set $P$ where it records the
positions of all miners in the source pool. Each miner sends its collected
positions together with the blockchain along all outgoing links. A block is
rejected if all its branches are shorter than the known positions of the
source pool miners. Note that non-source pool miners may still mine on the
dead branches and extend them. However, since the source pool is closed and
the source pool miners never see these non-source pool generated blocks, they
are never added to the live branches. The block labeling is similar to _KPT_.
Once the dead branches are determined and the rejected blocks are labeled, the
blocks whose cousins are dead are accepted and confirmed. The correctness
argument is similar to that of _KPT_. It is stated in Theorem 5.2.

###### Theorem 5.2

Known Source Pool Membership Algorithm KSM solves the Blockchain Decision
Problem with initially closed source pool.

Observe that in _KSM_ , all miners know the source pool membership. Thus, a
miner that is not in the source pool knows that all the blocks that it mines
are rejected. So this miner may either not mine its own blocks at all or
discard them as soon as they are mined.

##  6 Extensions and Optimizations

The algorithm presentation and discussion in the previous sections focused on
simplicity. However, there are optimizations that can be implemented to make
the algorithms more applicable and more generic. We are going to list them
here.

In the previous section, we assumed that the pool is initially closed.
However, both algorithms could be modified to operate correctly if there is a
known upper bound when the source pool is closed. That is, all miners are
aware of the round number after which there are no incoming links for source
pool miners from non-source pool miners.

Also, we assumed that each miner is sending the entire copy of its blockchain.
This is unnecessary. First, with no modifications, both algorithms operate
correctly even if each miner sends only its longest branch. That is, the
branch that it is currently mining on. However, further sending optimization
is possible. Observe that the operation of the algorithms hinges on the miners
communicating infinitely often. Thus, if a miner keeps track of the blocks it
already sent, it is sufficient to send only the oldest, i.e. the deepest
unsent block over each link. With this modification, the two algorithms, _KPT_
and _KSM_ , transmit only $\log N$ bytes in every message. That is, the two
algorithms use constant size messages.

We assumed that link communication is instantaneous. However, the algorithms
remain correct even if a message in each link is delayed for arbitrary time.

It is interesting to consider message loss. If there is fair message loss that
allows ultimate progress, the two algorithms operate correctly if each miner
sends the entire blockchain or the longest branch in every message. However,
since the feedback communication between receiver and sender is not
guaranteed, we suspect that constant message size algorithm for either known
pool membership or known propagation time does not exist.

##  7 Performance Evaluation

For our performance evaluation studies, we used QUANTAS abstract simulator
[19]. We generated dynamic topologies as follows. The maximum number of
potential neighbors $mx\leq|N|-1$ was fixed. Each round, for every miner, the
number of actual neighbors was selected uniformly at random from $0$ to $mx$;
the neighbor identifiers were also selected randomly. Miners generated blocks
at the rate of $2.5\%$.

Figure 2: Acceptance rate change as source pool membership is modified: complete network from rounds $0$ to $99$, $25\%$ from $100$ to $199$, and complete network thereafter. |  Figure 3: Confirmation time vs. maximum neighborhood size.
---|---

In the first experiment, we studied the dynamics of block acceptance as the
source pool membership changed. The results are shown in Figure 3. We ran the
computations for $300$ rounds. In the first $100$ rounds, the neighbors were
selected from the whole network. That is, the complete network was the source
pool. In the second $100$ rounds, $\lfloor 25\rfloor\%$ of miners were
selected to be the source pool. Specifically, the source pool miners may
connect to arbitrary neighbors, i.e. they have no connection restrictions. The
remaining miners may connect only to non-source pool miners. In the remaining
$100$, the restrictions were lifted and all miners formed the single source
pool again.

In a particular state of the computation, some block is accepted if it is in
the longest branch of every miner. That is, every miner is mining on top of
this block. The _acceptance rate_ is the ratio of accepted vs. generated
blocks. We ran experiments for the network size of $100$, $250$ and $500$
miners. We did $10$ experiments per network size and averaged our results.

The results indicate that, as the source pool size is restricted, the block
acceptance rate declines. This is due to the source pool neighbors not
receiving the blocks from non-source pool neighbors. The acceptance rate
sharply rises as the the source pool is enlarged to incorporate all miners and
long chains of blocks mined outside the source pool are propagated throughout
the network. The acceptance rate is lower in the networks of larger size.
Indeed, as more concurrent blocks are generated, fewer of them are accepted.

In the next experiment, we observed how the neighborhood size affects the time
it takes our algorithms to confirm the blocks. We implemented _KSM_ and _KPT_
and measured their confirmation time. The _confirmation time_ for a particular
block is the number of rounds from the round when the block was generated till
the round when the last miner outputs the confirmation decision. We counted
confirmation time for accepted blocks only. We varied the maximum number of
neighbors $mx$ and observed average confirmation time for _KSM_ and _KPT_. The
network size was $100$, the source pool was fixed at $75$ miners.

Algorithm _KPT_ , needs maximum propagation time _PT_ to be known in advance.
To determine _PT_ we ran preliminary computations. For a fixed $mx$, we
computed _PT_ by running $100$ computations with this $mx$ and computing the
longest recorded propagation time. These preliminary computation lengths were
set between $10,000$ and $15,000$ rounds. Then, for measurement computations,
to collect sufficiently many confirmed blocks, we set computation lengths to
$12\cdot PT$ rounds. We ran $10$ experiments per data point.

The results are shown in Figure 3. They indicate that, as the maximum possible
number of neighbors increases, the blocks are propagating faster and the
confirmation time drops. Perhaps surprisingly, _KSM_ performed better because
each miner can confirm a block as soon as it receives the data from all the
known source pool miners, while, in _KPT_ , a miner has to wait for twice the
maximum propagation time _PT_. This holds even though we ran preliminary
computations to select the shortest possible maximum propagation time _PT_.

Figure 4: Acceptance Rate vs. maximum neighborhood size. |  Figure 5: Confirmation time vs. network size.
---|---

For the same experiment, we computed average acceptance rate. We show the
results in Figure 5. Algorithm _KSM_ has lower confirmation time and,
therefore, higher acceptance rate.

In the final experiment, we observed the performance of the two algorithms as
the network scale changes. The number of source pool members is fixed at
$\lfloor 75\rfloor\%$ of the network size. The computation lengths were set to
$12\cdot PT$ rounds. We ran $10$ computations per data point. The results are
shown in Figure 5. As the network scale increases, $mx$ increases also. This
increases the number of potential journeys and decreases $PT$, which, in turn,
decreases the confirmation time of _KPT_ that depends on $PT$. _KSM_ exhibits
the opposite dynamics. With larger scale, the number of source pool miners
increases also. This makes _KSM_ run slightly slower as every miner has to
wait to hear from a greater number of source pool miners.

Our performance evaluation shows that _KSM_ outperforms _KPT_ under all
conditions. Therefore, _KPT_ should be considered only when the source pool
membership is not available and _KSM_ is not implementable.

##  8 Conclusion

In this paper, we studied the operation of blockchain in dynamic networks. We
explored how blockchain behaves at the boundaries of connectivity: where
message delay and miner participation is tenuous while connection and
communication speeds vary greatly. We believe this contributes to the
knowledge of blockchain as a construct and helps engineers to design
blockchain for high-stress, uncertain communication environments.

## References

  * [1] Y. Afek and E. Gafni.  Asynchrony from synchrony.  In International Conference on Distributed Computing and Networking, pages 225–239. Springer, 2013.
  * [2] O. Alphand, M. Amoretti, T. Claeys, S. Dall’Asta, A. Duda, G. Ferrari, F. Rousseau, B. Tourancheau, L. Veltri, and F. Zanichelli.  Iotchain: A blockchain security architecture for the internet of things.  In WCNC, pages 1–6. IEEE, 2018.
  * [3] M. Biely, P. Robinson, and U. Schmid.  Agreement in directed dynamic networks.  In International Colloquium on Structural Information and Communication Complexity, pages 73–84. Springer, 2012.
  * [4] S. Bonomi, G. Farina, and S. Tixeuil.  Reliable broadcast in dynamic networks with locally bounded byzantine failures.  In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 170–185. Springer, 2018.
  * [5] M. Castro and B. Liskov.  Practical byzantine fault tolerance and proactive recovery.  ACM Trans. Comput. Syst., 20(4):398–461, Nov. 2002.
  * [6] B. Charron-Bost and A. Schiper.  The heard-of model: computing in distributed systems with benign faults.  Distributed Computing, 22(1):49–71, 2009.
  * [7] X. Cong, L. Zi, and D.-Z. Du.  Dtnb: A blockchain transaction framework with discrete token negotiation for the delay tolerant network.  IEEE Transactions on Network Science and Engineering, 8(2):1584–1599, 2021.
  * [8] E. Coulouma, E. Godard, and J. Peters.  A characterization of oblivious message adversaries for which consensus is solvable.  TCS, 584:80–90, 2015.
  * [9] P. Grontas and A. Pagourtzis.  Blockchain, consensus, and cryptography in electronic voting.  Homo Virtualis, 2(1):79–100, 2019.
  * [10] R. Guerraoui, J. Komatovic, P. Kuznetsov, Y.-A. Pignolet, D.-A. Seredinschi, and A. Tonkikh.  Dynamic byzantine reliable broadcast.  In 24th International Conference on Principles of Distributed Systems, 2021.
  * [11] K. Hood, J. Oglio, M. Nesterenko, and G. Sharma.  Partitionable asynchronous cryptocurrency blockchain.  In 2021 IEEE International Conference on Blockchain and Cryptocurrency (ICBC), pages 1–9. IEEE, 2021.
  * [12] Y. Hu, A. Manzoor, P. Ekparinya, M. Liyanage, K. Thilakarathna, G. Jourjon, and A. Seneviratne.  A delay-tolerant payment scheme based on the ethereum blockchain.  IEEE Access, 7:33159–33172, 2019.
  * [13] F. Kuhn, N. Lynch, and R. Oshman.  Distributed computation in dynamic networks.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 513–522, 2010.
  * [14] F. Kuhn, Y. Moses, and R. Oshman.  Coordinated consensus in dynamic networks.  In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 1–10, 2011.
  * [15] L. Lamport, R. Shostak, and M. Pease.  The byzantine generals problem.  ACM Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
  * [16] O. Michail, I. Chatzigiannakis, and P. Spirakis.  New models for population protocols.  Synthesis Lectures on Distributed Computing Theory, 2(1):1–156, 2011.
  * [17] S. Nakamoto.  Bitcoin: A peer-to-peer electronic cash system,”, 2008.
  * [18] R. O’Dell and R. Wattenhofer.  Information dissemination in highly dynamic graphs.  In Proceedings of the 2005 joint workshop on Foundations of mobile computing, pages 104–110, 2005.
  * [19] J. Oglio, K. Hood, M. Nesterenko, and S. Tixeuil.  Quantas: Quantitative user-friendly adaptable networked things abstract simulator.  arXiv preprint arXiv:2205.04930, 2022.
  * [20] N. Santoro and P. Widmayer.  Time is not a healer.  In Annual Symposium on Theoretical Aspects of Computer Science, pages 304–313. Springer, 1989.
  * [21] K. Winkler, M. Schwarz, and U. Schmid.  Consensus in rooted dynamic networks with short-lived stability.  Distributed Computing, 32(5):443–458, 2019.
  * [22] G. Wood.  Ethereum: A secure decentralized generalized transaction ledger.  Ethereum project yellow paper, 151:1–32, 2014.