# A Benchmark of Long-tailed Instance Segmentation with Noisy Labels (Short
Version)

Guanlin Li
S-Lab, NTU
<EMAIL_ADDRESS>Guowen Xu
NTU
<EMAIL_ADDRESS>Tianwei Zhang
NTU
<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider the instance segmentation task on a long-tailed
dataset, which contains label noise, i.e., some of the annotations are
incorrect. There are two main reasons making this case realistic. First,
datasets collected from real world usually obey a long-tailed distribution.
Second, for instance segmentation datasets, as there are many instances in one
image and some of them are tiny, it is easier to introduce noise into the
annotations. Specifically, we propose a new dataset, which is a large
vocabulary long-tailed dataset containing label noise for instance
segmentation. Furthermore, we evaluate previous proposed instance segmentation
algorithms on this dataset. The results indicate that the noise in the
training dataset will hamper the model in learning rare categories and
decrease the overall performance, and inspire us to explore more effective
approaches to address this practical challenge. The code and dataset are
available in https://github.com/GuanlinLee/Noisy-LVIS.

##  1 Introduction

Instance segmentation models [HGDG17, WZK+20] provide each pixel in an image a
label to indicate the specific semantic information, which can be seen as a
finer inference of object detection models [RHGS15, LAE+16] and semantic
segmentation models [BKC17, CZP+18]. Most of previous works focus on exploring
more effective algorithms on balanced and clean datasets, such as MS COCO
[LMB+14]. However, instances included in images usually obey a long-tailed
distribution [LGG+17, CWG+19, CJL+19], which means most of the instances
belong to a small part of categories, which are called “head” classes, and few
of instances belong to other categories, which are called “body” and “tail”
classes. If users do not modify the training algorithms to fit an unbalanced
dataset, the model will give higher confidence to the instances from head
classes [LGG+17], which harms the generalizability to the instances from body
and tail classes, causing accuracy decrease. On the other hand, the
annotations for each item in the dataset are usually given by people who are
paid by the big companies, like Google111https://venturebeat.com/ai/probeat-
google-still-needs-you-to-label-photos-for-its-ml/ and
Meta222https://www.reuters.com/article/us-facebook-ai-focus-idUSKCN1SC01T. In
reality, these annotators are not always experts [WRW+09], as the companies
wish to decrease the cost. So, there are usually some wrong labels in the
dataset, called label noise. For example, in Clothing1M [XXY+15] the
percentage of label noise is about 38.5% [SKP+22], and in WebVision [LWL+17]
the label noise ratio is about 20.0% [SKP+22]. If users do not adopt any
approach to mitigate the impact of the label noise, the accuracy of the model
will significantly decrease on the clean test set, because the incorrect
labels can provide wrong supervised information during the training process.
So, there exists a gap which can cause performance drop when users train a
model on a personal dataset, which is unbalanced or contains label noise. To
address the challenges in training a model on long-tailed datasets or noisy
datasets, many studies have been published, recently.

Similar to exploring how to train classifiers on unbalanced datasets, solving
long-tailed challenges in the instance segmentation task raises the attention
of the deep learning community. Different from the classification task on
long-tailed datasets, backgrounds in the instance segmentation datasets always
occupy an overwhelming position, and in foreground, there are head classes and
tail classes, which means blindly adopting approaches in classification tasks
cannot address the problem in instance segmentation. So, there are a series of
new methods [HJT+20, HRCH21, WZZ+21] proposed in solving long-tailed instance
segmentation task, including new data augmentation methods, new model
architectures and new loss functions. These solutions can work well on long-
tailed datasets, without considering the label noise. However, as
aforementioned challenges in deep learning, noise labels are more popular in
instance segmentation datasets, because there are more instances in the
datasets and annotating them exhaustively and precisely is more difficult.
Specifically, the noise in instance segmentation datasets source from two
aspects, i.e., foreground instances missed annotations (false negative
background) and foreground instances mis-annotated into other classes (noisy
label). In this paper, we focus on the latter one, which is a more harmful
type of noise in the dataset. There are numerous studies focusing on
addressing the noisy label problem in classification tasks, such as new model
structures [SF15] and new loss functions [GKS17]. And Yang at el. [YML+20]
propose a two-stage training fashion to overcome the label noise in the
instance segmentation task. On the balanced dataset containing label noise,
adopting such methods can successfully overcome the accuracy drop. However,
they do not consider a more practical setting, i.e., a long-tailed noisy
dataset.

Recently, to fill the gap and make a connection between long-tailed
recognition and noisy label learning, several works [WSTL21, KRC21] combine
long-tailed learning methods and technologies for solving label noise. The
results indicate that this direct solution is helpful to train a model on an
unbalanced dataset containing label noise. However, in the instance
segmentation task, background objects and foreground objects are required to
be handled separately, which is different from the image recognition task,
causing that previous methods for long-tailed recognition and noisy label
learning cannot be applied to this task directly. On the other hand, we find a
lack of relevant datasets, which are both long-tailed and noisy, in the
instance segmentation task. It brings the difficulties for other researchers
to explore approaches to address these practical challenges. So, in this
paper, we attempt to introduce a benchmark for the instance segmentation task
on long-tailed and noisy datasets.

Formally, there are two main contributions in this paper, i.e., introducing a
new long-tailed noisy dataset and systematically evaluating previously
proposed methods on this dataset. Specifically, we build a noisy long-tailed
datasets from the LVIS v1 [GDG19], which is a large vocabulary long-tailed
instance segmentation dataset containing 1,203 different categories for the
foreground objects. We will introduce the details of how we add noisy labels
into the LVIS v1 in Section 3. For our second contribution, we evaluate EQL
[TWL+20], DropLoss [HRCH21] and Seesaw Loss [WZZ+21] on this new dataset under
different noise settings and samplers in Section 4. More evaluation results
will be added in the future. From the results under different noise settings
and samplers, we find that previous proposed long-tailed instance segmentation
losses cannot keep robust under label noise and data sampling methods have a
significant impact on the final results, due to distribution shift caused by
the label noise. We hope this benchmark and the new proposed dataset can
shrink the gap between ideal experimental settings and practical datasets and
bring guides for researchers in further exploration.

##  2 Related Works

###  2.1 LVIS v1

LVIS v1 is a dataset for Large Vocabulary Instance Segmentation, derived from
the Microsoft Common Objects in Context (MS COCO) [LMB+14] with much more
fine-grained annotations, which means that the images in LVIS v1 are the same
as them in the MS COCO, but the categories of each instance in the images are
more precise. Specifically, there are 1,203 different classes in LVIS v1, and
in MS COCO, there are only 80 classes. As a large vocabulary dataset, the
evaluation process must be accurate. To achieve it, the LVIS v1 adopts
positive sets and negative sets for each category333This can cause that some
instances are not annotated and are treated as background. In this paper, we
do not consider the false negative samples’ influence in the training
procedure.. As for the categories in LVIS v1, each of them is a WordNet
[Mil95] synset, i.e., a word sense specified by a set of synonyms and a
definition. Ideally, we can treat the LVIS v1 as an exhaustive and clean long-
tailed dataset. And, we will explore the previous long-tailed segmentation
methods trained on a noisy dataset, i.e., adding symmetry and asymmetry noise
labels into the training set of the LVIS v1.

###  2.2 Long-tailed Instance Segmentation

Compared with the long-tailed object classification task [RYS+20, MJR+21], the
long-tailed instance segmentation task is much closer to the long-tailed
object detection task [TWL+20]. The reason is that the object detection task
can be seen as a sub-task in the instance segmentation task, as some instance
segmentation pipeline first generates bounding boxes for each object and then
generates masks inside the bounding boxes. Because instance segmentation
models need to recognize backgrounds and foregrounds, and generate masks for
each foreground object, background-foreground classification plays a key role.
However, backgrounds occupy an overwhelming number in the dataset, which means
that simply adopting solutions proposed in long-tailed object classification
tasks cannot address the background-foreground classification challenges. In
long-tailed instance segmentation tasks, there are several new proposed
approaches, such as gradient calibration [TWL+20, WZZ+21], two-stage training
[WLK+20], data augmentation [GCS+21], and new model structures [ZHL21]. In
this paper, we mainly consider evaluating loss functions designed for long-
tailed instance segmentation tasks.

###  2.3 Noisy Label Learning

Various approaches have been proposed to address the label noise from
different perspectives, including new model architectures [SF15],
regularization terms [JF18], robust loss functions [GKS17], loss adjustment
[RLA+15] and sample selection [HYY+18]. [SF15] proposed a new model
architecture containing a noise adaptation layer to model the label transition
pattern with a noise transition matrix. Furthermore, a generative
classification layer is found to be more robust against the label noise
[LYL+19]. On the other hand, both adversarial training [GSS15] and label
smoothing [LBMK20], which could be seen as regularization, were found to be
efficient at improving the model’s tolerance to label noise. For the robust
loss functions, [GKS17] proved that the mean absolute error (MAE) loss was
robust to the label noise, but it harmed the model’s generalizability. So, the
generalized cross entropy (GCE) [ZS18] keeping the advantages from cross-
entropy loss and MAE loss is proposed. [PRM+17] proposed a Backward correction
method and a Forward correction method to address the label noise challenge by
adjusting the losses. Furthermore, Bootstrapping [RLA+15] was the first label
refurbishment method to automatically correct the data labels during the
training process. For the sample selection, [HYY+18] adopted two models to
adaptively choose samples to train its peer model based on the value of the
training loss, which was called the Co-teaching method. Combining with semi-
supervised learning, DivideMix [LSH20] trained models on clean dataset and
noisy dataset.

Although there are numerous researches focusing on solving the label noise
problem, most of them are designed for balanced datasets and the image
classification task. In this paper, we first systematically evaluate previous
methods of the instance segmentation task on a noisy long-tailed dataset.

##  3 LVIS v1 with Noise

In this section, we mainly analyze how to add asymmetry (class-related) noise
into the training set of the LVIS v1. Because there are 1203 categories,
analyzing the semantics of each category manually and gathering classes with
similar semantics manually can be impracticable and require a lot of
workloads. We create an automated toolkit, to analyze the semantics based on
WordNet. We will introduce the analyzing process in the follows.

###  3.1 Parse synset Categories

To parse the synset categories in the LVIS v1, we adopt nltk [BKL09], which is
a natural language toolkit. With it, we build a tree to represent the
relations between all categories in the LVIS v1, which can be found in Figure
2. Specifically, the numbers in the child nodes represent how many synset
categories belong to this node, i.e., their hypernyms are this node444We do
not plot the categories as the child nodes, because it needs a tree with depth
18. But the toolkit we provide can plot a tree with arbitrary depths.. We
manually pick 25 hypernyms as super classes and one “others” as a super class
to contain the remaining categories, which do not belong to any of the 25
super classes. Then, we divide categories based on their hypernyms into each
super class, and there is no overlap between different super classes. The
details of the super classes and the number of categories in each super class
can be found in Table 1.

Name of Super Class instrumentality food living_thing commodity Number of
Categories r c f total r c f total r c f total r c f total 150 200 174 524 52
58 29 139 34 60 19 113 23 40 50 113

Name of Super Class natural_object decoration structure communication Number
of Categories r c f total r c f total r c f total r c f total 9 15 14 38 5 10
9 24 8 7 9 24 7 9 7 23

Name of Super Class creation material fabric sheet Number of Categories r c f
total r c f total r c f total r c f total 6 4 7 17 5 5 5 15 1 6 7 14 1 3 9 13

Name of Super Class way strip plaything padding Number of Categories r c f
total r c f total r c f total r c f total 4 3 5 12 0 5 6 11 4 1 4 9 1 2 5 8

Name of Super Class fixture surface measure causal_agent Number of Categories
r c f total r c f total r c f total r c f total 1 0 6 7 4 2 0 6 3 2 1 6 1 2 2
5

Name of Super Class block float line opening Number of Categories r c f total
r c f total r c f total r c f total 2 1 1 4 1 1 2 4 0 2 1 3 0 1 2 3

Name of Super Class arrangement others Total Number of Categories r c f total
r c f total r c f total 0 2 1 3 15 20 30 65 337 461 405 1203

Table 1: Super classes and the number of categories in each super class. We
list the number of rare, common, and frequent categories under each super
class.

###  3.2 Noise Label Generation

To add asymmetry (class-related) noise into the training set of the LVIS v1,
we randomly pick a new category under the same super class to replace the
original label. But, to make the semantics consistency between the original
category and the new one, we only consider categories that do not belong to
the “others”. In Algorithm 1, we describe the process of generating label
noise. The Clean Annotation List $A$ is a list containing all instances’
categories, which has the following format: $A=[3,5,100,102,\dots,90,1000]$.
$A[i]$ represent the $i$-th element in the list $A$. The Super Class
Dictionary $S$ is a dictionary, whose key is the name of the super class name
listed in Table 1, and the value is a list of the categories which belong to
the super class, e.g.,
$S=\\{`\mathrm{instrumentality}^{\prime}:[1,3,10,\dots,900,1200],`\mathrm{food}^{\prime}:[2,7,\dots,1000,1001],\dots,`\mathrm{others}^{\prime}:[90,500,\dots,1203]\\}$.
We randomly sample a value from a uniform distribution $\mathcal{U}(0,1)$
between 0 and 1 to fit the Noise Ratio $p$.

Algorithm 1 Noise Label Generation

1: Input: Clean Annotation List $A$, Noise Ratio $p$, Super Class Dictionary
$S$

2: for $i=0\to(\mathrm{len}(A)-1)$ do

3: $r\leftarrow\mathcal{U}(0,1)$

4: if $r\leq p$ then

5: $s\leftarrow$ super class of category $A[i]$

6: if $s$ is not “others” then

7: $n\leftarrow$ randomly pick a category from $S[s]$

8: $A[i]\leftarrow n$

9: end if

10: end if

11: end for

12: return $A$

##  4 Experiments

###  4.1 Dataset

In this paper, we adopt LVIS v1 to evaluate various methods’ performance under
different noise settings, which contains 100k images for training and 19.8k
images for validation. In LVIS v1, there are 1,203 categories, grouped by
their image frequency: rare (1-10 images in the dataset), common (11-100
images in the dataset) and frequent ($>$100 images in the dataset). For the
label noise, we consider two types of the noise, i.e., symmetric (class-
agnostic) noise and asymmetric (class-related) noise. When adding symmetric
noise into the training set, we randomly pick a label from all 1,203 possible
categories to replace the original label. When adding asymmetric noise, we
follow the steps in Section 3.2. The results of the validation set are
reported from five aspects: average segmentation performance $AP$, average box
performance $AP^{b}$ and average segmentation performance for rare $AP^{r}$,
common $AP^{c}$ and frequent categories $AP^{f}$.

###  4.2 Methods

We evaluate three mainstream long-tailed instance segmentation approaches,
including EQL [TWL+20], DropLoss [HRCH21] and Seesaw Loss [WZZ+21].
Specifically, the implementations of EQL and DropLoss are followed the Gumbel
Optimized Loss [ADNL22], i.e., we replace the original activation function
Sigmoid with Gumbel.

###  4.3 Implementation Details

We adopt mmdetection [CWP+19] and Pytorch [PGM+19] on 4 V100 GPU cards to
implement all experiments. On each GPU card, there are 4 images in one batch.
For all methods, we use Mask R-CNN [HGDG17], in which the ResNet-50 [HZRS16]
with FPN [LDG+17] is the backbone model, and the $2\times$ schedule and the
Normalized Mask [WZZ+21] are adopted to improve the model’s performance. The
model’s details are shown in Table 2. For the training process, we adopt
Stochastic Gradient Descent as our optimizer to train models with 24 epochs.
The learning rate is 0.02, and we decrease it by 0.1 at the 16th epoch and the
22nd epoch. The data augmentations include random horizontal flipping and
multi-scaling, which are consistent with previous works [WZZ+21, ADNL22]. In
inference, we follow the protocol in [WZZ+21], i.e., we resize all images into
1333$\times$800 and use the score thresholds of $10^{-3}$. For sampler, we
consider RFS sampler [GDG19] and Random sampler, respectively.

###  4.4 Results

In Figure 1, we compare the label distribution under different noise settings.
The $x$-axis is the category, which is sorted based on the frequency in the
original training set of the LVIS v1. We keep the same category order in each
image. And the $y$-axis is the number of instances that are annotated as the
corresponding category. Clearly, adding noise will change the label
distribution, thus the RFS sampler, which will over-sample low-frequency
instances, will be influenced by the shifted label distribution.

We first compare the results of Seesaw Loss with the RFS sampler and the
Random sampler in Table 3. For the RFS sampler, we set the over-sample
threshold as 0.001. The results indicate that the RFS sampler can
significantly increase the performance on the clean long-tailed dataset
compared with the Random sampler. When there exist label noise in the dataset,
the improvement obtained from the RFS sampler weakens, which can be the
distribution shift, causing the sampler samples more instance with incorrect
labels.

In Table 4, we present the results under different loss functions, and all of
them are equipped with the RFS sampler. The results indicate that methods
(DropLoss with Gumbel and EQL with Gumbel) with better performance may not be
the best choice for practical when there exists noise in the training labels.
On the other hand, different loss functions have different robustness for the
asymmetric (class-related) noise and symmetric (class-agnostic) noise. For
example, the Seesaw Loss shows more robust under symmetric noise. However, the
DropLoss with Gumbel shows more robust under asymmetric noise. This phenomenon
indicates that designing a loss for long-tailed instance segmentation dataset
with noise is challenging, and it is complex to outperform under all types of
noise.

##  5 Conclusion

In this report, we introduce a tool to automatically analyze the categories in
LVIS v1. With it, we add asymmetric noise into the clean training set to
create noisy datasets with different noise ratios. Then, we evaluate three
mainstream long-tailed instance segmentation loss function on the noisy
datasets containing asymmetric noise and symmetric noise, respectively. The
results indicate that previous long-tailed loss functions lack the robustness
when facing the noisy datasets, and it is important to study how to design new
ones to better fit the label noise.

Method Model Backbone Normalized Mask Normalized Classifier Activation EQL +
Gumbel Mask R-CNN ResNet-50 ✓ ✗ Gumbel DropLoss + Gumbel Mask R-CNN ResNet-50
✓ ✗ Gumbel Seesaw Loss Mask R-CNN ResNet-50 ✓ ✓ Softmax

Table 2: Settings for different methods.

(a) LVIS v1 label distribution.

(b) Asymmetric Noise (0.2).

(c) Asymmetric Noise (0.4).

(d) Symmetric Noise (0.2).

(e) Symmetric Noise (0.4).

Figure 1: Label distribution under different noise settings.

Noise Sampler $AP^{b}$ $AP^{r}$ $AP^{c}$ $AP^{f}$ $AP$ None Random 25.40 14.90
23.30 32.40 25.50 RFS 27.10 18.80 26.60 30.90 26.90 AN (0.2) Random 21.60 5.60
19.60 28.70 20.70 RFS 21.40 5.00 19.40 29.00 20.70 AN (0.4) Random 18.20 4.30
13.90 26.90 17.30 RFS 18.60 4.00 14.70 27.20 17.80 SN (0.2) Random 22.80 7.50
21.10 28.90 21.80 RFS 22.60 6.60 21.40 29.10 21.90 SN (0.4) Random 19.10 2.80
16.00 27.30 18.20 RFS 19.30 3.30 16.40 27.50 18.50

Table 3: Results of Seesaw Loss with different samplers.

Noise Method $AP^{b}$ $AP^{r}$ $AP^{c}$ $AP^{f}$ $AP$ None DropLoss + Gumbel
27.60 19.90 28.00 30.40 27.50 EQL + Gumbel 26.80 17.30 26.70 31.20 26.90
Seesaw Loss 27.10 18.80 26.60 30.90 26.90 AN (0.2) DropLoss + Gumbel 18.90
3.60 16.00 27.70 18.40 EQL + Gumbel 20.00 4.40 16.30 29.70 19.50 Seesaw Loss
21.40 5.00 19.40 29.00 20.70 AN (0.4) DropLoss + Gumbel 14.70 2.30 9.50 25.10
14.30 EQL + Gumbel 15.90 2.30 9.60 27.60 15.40 Seesaw Loss 18.60 4.00 14.70
27.20 17.80 SN (0.2) DropLoss + Gumbel 18.60 3.50 15.30 27.90 18.20 EQL +
Gumbel 19.20 3.30 15.10 29.50 18.70 Seesaw Loss 22.60 6.60 21.40 29.10 21.90
SN (0.4) DropLoss + Gumbel 13.80 1.40 7.50 25.00 13.30 EQL + Gumbel 14.50 1.10
7.40 27.00 14.00 Seesaw Loss 19.30 3.30 16.40 27.50 18.50

Table 4: Results under different noise settings.

Figure 2:

## References

  * [ADNL22] Kostas Alexandridis, Jiankang Deng, Anh Nguyen, and Shan Luo.  Long-tailed Instance Segmentation using Gumbel Optimized Loss.  In Proc. of the ECCV, 2022.
  * [BKC17] Vijay Badrinarayanan, Alex Kendall, and Roberto Cipolla.  Segnet: A deep convolutional encoder-decoder architecture for image segmentation.  IEEE transactions on pattern analysis and machine intelligence, 39(12):2481–2495, 2017.
  * [BKL09] Steven Bird, Ewan Klein, and Edward Loper.  Natural language processing with Python: analyzing text with the natural language toolkit.  ” O’Reilly Media, Inc.”, 2009.
  * [CJL+19] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge J. Belongie.  Class-Balanced Loss Based on Effective Number of Samples.  In Proc. of the CVPR, pages 9268–9277, 2019.
  * [CWG+19] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Aréchiga, and Tengyu Ma.  Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss.  In Proc. of the NeurIPS, pages 1565–1576, 2019.
  * [CWP+19] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, Zheng Zhang, Dazhi Cheng, Chenchen Zhu, Tianheng Cheng, Qijie Zhao, Buyu Li, Xin Lu, Rui Zhu, Yue Wu, Jifeng Dai, Jingdong Wang, Jianping Shi, Wanli Ouyang, Chen Change Loy, and Dahua Lin.  MMDetection: Open mmlab detection toolbox and benchmark.  CoRR, abs/1906.07155, 2019.
  * [CZP+18] Liang-Chieh Chen, Yukun Zhu, George Papandreou, Florian Schroff, and Hartwig Adam.  Encoder-decoder with atrous separable convolution for semantic image segmentation.  In Proc. of the ECCV, pages 801–818, 2018.
  * [GCS+21] Golnaz Ghiasi, Yin Cui, Aravind Srinivas, Rui Qian, Tsung-Yi Lin, Ekin D Cubuk, Quoc V Le, and Barret Zoph.  Simple copy-paste is a strong data augmentation method for instance segmentation.  In Proc. of the CVPR, pages 2918–2928, 2021.
  * [GDG19] Agrim Gupta, Piotr Dollár, and Ross B. Girshick.  LVIS: A Dataset for Large Vocabulary Instance Segmentation.  In Proc. of the CVPR, pages 5356–5364, 2019.
  * [GKS17] Aritra Ghosh, Himanshu Kumar, and P. S. Sastry.  Robust loss functions under label noise for deep neural networks.  In Proc. of the AAAI, pages 1919–1925, 2017.
  * [GSS15] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and Harnessing Adversarial Examples.  In Proc. of the ICLR, 2015.
  * [HGDG17] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proc. of the ICCV, pages 2961–2969, 2017.
  * [HJT+20] Xinting Hu, Yi Jiang, Kaihua Tang, Jingyuan Chen, Chunyan Miao, and Hanwang Zhang.  Learning to segment the tail.  In Proc. of the CVPR, pages 14045–14054, 2020.
  * [HRCH21] Ting-I Hsieh, Esther Robb, Hwann-Tzong Chen, and Jia-Bin Huang.  Droploss for long-tail instance segmentation.  In Proc. of the AAAI, pages 1549–1557, 2021.
  * [HYY+18] Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama.  Co-teaching: Robust training of deep neural networks with extremely noisy labels.  In Proc. of the NeurIPS, pages 8536–8546, 2018.
  * [HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In Proc. of the CVPR, pages 770–778, 2016.
  * [JF18] Simon Jenni and Paolo Favaro.  Deep bilevel learning.  In Proc. of the ECCV, volume 11214, pages 632–648, 2018.
  * [KRC21] Shyamgopal Karthik, Jérôme Revaud, and Boris Chidlovskii.  Learning from long-tailed data with noisy labels.  CoRR, abs/2108.11096, 2021.
  * [LAE+16] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C Berg.  Ssd: Single shot multibox detector.  In Proc. of the ECCV, pages 21–37, 2016.
  * [LBMK20] Michal Lukasik, Srinadh Bhojanapalli, Aditya Krishna Menon, and Sanjiv Kumar.  Does label smoothing mitigate label noise?  In Proc. of the ICML, volume 119, pages 6448–6458, 2020.
  * [LDG+17] Tsung-Yi Lin, Piotr Dollár, Ross B. Girshick, Kaiming He, Bharath Hariharan, and Serge J. Belongie.  Feature pyramid networks for object detection.  In Proc. of the CVPR, pages 936–944, 2017.
  * [LGG+17] Tsung-Yi Lin, Priya Goyal, Ross B. Girshick, Kaiming He, and Piotr Dollár.  Focal Loss for Dense Object Detection.  In Proc. of the ICCV, pages 2999–3007, 2017.
  * [LMB+14] Tsung-Yi Lin, Michael Maire, Serge J. Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick.  Microsoft COCO: common objects in context.  In Proc. of the ECCV, pages 740–755, 2014.
  * [LSH20] Junnan Li, Richard Socher, and Steven C. H. Hoi.  DivideMix: Learning with Noisy Labels as Semi-supervised Learning.  In Proc. of the ICLR, 2020.
  * [LWL+17] Wen Li, Limin Wang, Wei Li, Eirikur Agustsson, and Luc Van Gool.  Webvision database: Visual learning and understanding from web data.  CoRR, abs/1708.02862, 2017.
  * [LYL+19] Kimin Lee, Sukmin Yun, Kibok Lee, Honglak Lee, Bo Li, and Jinwoo Shin.  Robust inference via generative classifiers for handling noisy labels.  In Proc. of the ICML, volume 97, pages 3763–3772, 2019.
  * [Mil95] George A. Miller.  Wordnet: A lexical database for english.  Communications of the ACM, 38(11):39–41, 1995.
  * [MJR+21] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar.  Long-tail learning via logit adjustment.  In Proc. of the ICLR, 2021.
  * [PGM+19] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In Proc. of the NeurIPS, pages 8024–8035. 2019.
  * [PRM+17] Giorgio Patrini, Alessandro Rozza, Aditya Krishna Menon, Richard Nock, and Lizhen Qu.  Making Deep Neural Networks Robust to Label Noise: A Loss Correction Approach.  In Proc. of the CVPR, pages 2233–2241, 2017.
  * [RHGS15] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  Proc. of the NeurIPS, 28, 2015.
  * [RLA+15] Scott E. Reed, Honglak Lee, Dragomir Anguelov, Christian Szegedy, Dumitru Erhan, and Andrew Rabinovich.  Training deep neural networks on noisy labels with bootstrapping.  In Proc. of the ICLR Workshop, 2015.
  * [RYS+20] Jiawei Ren, Cunjun Yu, Shunan Sheng, Xiao Ma, Haiyu Zhao, Shuai Yi, and Hongsheng Li.  Balanced Meta-Softmax for Long-Tailed Visual Recognition.  In Proc. of the NeurIPS, 2020.
  * [SF15] Sainbayar Sukhbaatar and Rob Fergus.  Learning from Noisy Labels with Deep Neural Networks.  In Proc. of the ICLR Workshop, 2015.
  * [SKP+22] Hwanjun Song, Minseok Kim, Dongmin Park, Yooju Shin, and Jae-Gil Lee.  Learning from noisy labels with deep neural networks: A survey.  IEEE Transactions on Neural Networks and Learning Systems, 2022\.  Publisher: IEEE.
  * [TWL+20] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan.  Equalization loss for long-tailed object recognition.  In Proc. of the CVPR, pages 11662–11671, 2020.
  * [WLK+20] Tao Wang, Yu Li, Bingyi Kang, Junnan Li, Junhao Liew, Sheng Tang, Steven Hoi, and Jiashi Feng.  The devil is in classification: A simple framework for long-tail instance segmentation.  In Proc. of the ECCV, pages 728–744, 2020.
  * [WRW+09] Jacob Whitehill, Paul Ruvolo, Tingfan Wu, Jacob Bergsma, and Javier R. Movellan.  Whose Vote Should Count More: Optimal Integration of Labels from Labelers of Unknown Expertise.  In Proc. of the NeurIPS, pages 2035–2043, 2009.
  * [WSTL21] Tong Wei, Jiang-Xin Shi, Wei-Wei Tu, and Yu-Feng Li.  Robust long-tailed learning under label noise.  CoRR, abs/2108.11569, 2021.
  * [WZK+20] Xinlong Wang, Rufeng Zhang, Tao Kong, Lei Li, and Chunhua Shen.  Solov2: Dynamic and fast instance segmentation.  Proc. of the NeurIPS, 33:17721–17732, 2020.
  * [WZZ+21] Jiaqi Wang, Wenwei Zhang, Yuhang Zang, Yuhang Cao, Jiangmiao Pang, Tao Gong, Kai Chen, Ziwei Liu, Chen Change Loy, and Dahua Lin.  Seesaw Loss for Long-Tailed Instance Segmentation.  In Proc. of the CVPR, pages 9695–9704, 2021.
  * [XXY+15] Tong Xiao, Tian Xia, Yi Yang, Chang Huang, and Xiaogang Wang.  Learning from massive noisy labeled data for image classification.  In Proc. of the CVPR, pages 2691–2699, 2015.
  * [YML+20] Longrong Yang, Fanman Meng, Hongliang Li, Qingbo Wu, and Qishang Cheng.  Learning with noisy class labels for instance segmentation.  In Proc. of the ECCV, pages 38–53, 2020.
  * [ZHL21] Yuhang Zang, Chen Huang, and Chen Change Loy.  Fasa: Feature augmentation and sampling adaptation for long-tailed instance segmentation.  In Proc. of the ICCV, pages 3457–3466, 2021.
  * [ZS18] Zhilu Zhang and Mert R. Sabuncu.  Generalized Cross Entropy Loss for Training Deep Neural Networks with Noisy Labels.  In Proc. of the NeurIPS, pages 8792–8802, 2018.


# Birkhoff’s invariant and Thorne’s Hoop Conjecture

G. W. Gibbons
D.A.M.T.P.,
Cambridge,
Wilberforce Road,
Cambridge CB3 0WA,
U.K

###### Abstract

I propose a sharp form of Thorne’s hoop conjecture which relates Birkhoff’s
invariant $\beta$ for an outermost apparent horizon to its $ADM$ mass,
$\beta\leq 4\pi M_{ADM}$. I prove the conjecture in the case of collapsing
null shells and provide further evidence from exact rotating black hole
solutions. Since $\beta$ is bounded below by the length $l$ of the shortest
non-trivial geodesic lying in the apparent horizon, the conjecture implies
$l\leq 4\pi M_{ADM}$. The Penrose conjecture, $\sqrt{\pi A}\leq 4\pi M_{ADM}$,
and Pu’s theorem imply this latter consequence for horizons admitting an
antipodal isometry. Quite generally, Penrose’s inequality and Berger’s
isembolic inequality, $\sqrt{\pi A}\geq{2\over\sqrt{\pi}}i$, where $i$ is the
injectivity radius, imply $4c\leq 2i\leq 4\pi M_{ADM}$, where $c$ is the
convexity radius.

##  1 The Hoop Conjecture

Thorne’s original Hoop Conjecture [1] was that

> Horizons form when and only when a mass $m$ gets compacted into a region
> whose circumference in EVERY direction is $C\leq 4\pi M$.

The capitalization “EVERY ”was intended to emphasis the fact that while the
collapse of oblate shaped bodies the circumferences are all roughly equal, in
the prolate case, a the collapse of a long almost cylindrically shaped body
whose girth was nevertheless small would not necessarily produce a horizon.
However, as proposed, the statement is so imprecise as to render either proof
or disproof impossible. Presumably for the mass we could take the ADM mass,
$M_{ADM}$, but what about the circumference of the hoop? Since Thorne’s
article, there have been many attempts to tighten up the formulation of the
conjecture, the most recent of which is [2] to which the reader is referred
for an extensive list of previous contributions to this question.

The present note was inspired by [3] and in many respects takes forward a
suggestion of Tod [4]. It is closely related to recent work of Yau and others
on the idea of quasi-local mass.

##  2 Birkhoff’s Invariant and Birkhoff’s Theorem

We can assume that the apparent horizon is topologically spherical [6, 7, 8,
9]. In what follows we follow [3] fairly closely. Suppose that
$S=\\{S^{2},g\\}$ is a sphere with arbitrary metric $g$ and
$f:S\rightarrow{{R}}$ a function on $S$ with just two critical points, a
maximum and a minimum. Each level set $f^{-1}(c),\,c\in{{R}}$ has a length
$l(c)$ and for any given function $f$ we define

$\beta(f)={\rm max}_{c}\,l(c)\,.$ (1)

We now define the Birkhoff invariant $\beta(S,g)$ by minimising $\beta(f)$
over all such functions

$\beta=\inf_{f}\beta(f)\,.$ (2)

The intuitive meaning of $\beta$ is the least length of a length of a closed
(elastic) string or rubber band which may be slipped over over the surface $S$
[5]. To understand why, note that each function $f$ gives a foliation of $S$
by a one parameter family of curves $f=c$ which we may think of as the string
or rubber band at each “moment of time ” $c$. $\beta(f)$ is the longest length
of the band during that process. If we change the foliation we can hope to
reduce this longest length and the infinum is the best that we can do. The
phrase “moment of time ”is in quotation marks because we are not regarding $f$
as a physical time function, merely a convenient way of thinking about the
geometry of $S$.

Birkhoff’s Theorem [5] then assures us that there exist a closed geodesic
$\gamma$ on $S$ with length $l(\gamma)=\beta(g)$. Clearly, if $l(g)$ is the
length of the smallest non-trivial closed (i.e periodic) geodesic then

$l(g)\leq\beta(g)\,.$ (3)

It seems therefore that the Birkhoff invariant $\beta(g)$ should be taken as a
precise formulation of Thorne’s rather vague notion of circumference. We shall
proceed on this basis. Thus we make the following

> Conjecture: For an outermost marginally trapped surface $S$ lying in a
> Cauchy hypersurface surface $\Sigma$ with ADM mass $M_{\rm ADM}$ on which
> the Dominant Energy condition holds, then
>
> $\beta(g)\leq 4\pi M_{\rm ADM}\,.$ (4)

In other words, (4) is conjectured to be a necessary condition for a
marginally outermost trapped surface. Bearing in mind Thorne’s comments about
very prolate shaped surfaces for which $\beta(g)$ can be extremely small, it
is not claimed that (4) is a sufficient condition for a closed surface $S$ to
be trapped or marginally.

Clearly, from (3), this form of the hoop conjecture implies

$l(g)\leq 4\pi M_{\rm ADM}\,,$ (5)

and therefore a counter example to (5) would be a counter example to (4).

###  2.1 The Kerr-Newman Horizon

We first test the conjecture on the general charged rotating black hole. In
standard notation, the metric on the horizon is [10]

$g=ds^{2}=(r_{+}^{2}+a^{2})\Bigl{(}(1-x^{2}\sin^{2}\theta)d\theta^{2}+{\sin^{2}\theta
d\phi^{2}\over 1-x^{2}\sin^{2}\theta}\Bigr{)}\,,$ (6)

with

$x^{2}={a^{2}\over r_{+}^{2}+a^{2}}\,.$ (7)

This is clearly foliated by the orbits of the group of rotations generated by
by ${\partial\over\partial\phi}$ and we take $f=\cos\theta$. That is, we are
thinking of the coordinate $\theta$ as a function on $S$. In this case the
greatest length of the small circles, i.e. of the orbits, is $l_{e}$, the
length of the of the equatorial geodesic at $\theta={\pi\over 2}$ and we have

$\beta(\cos\theta)=l_{e}=2\pi(r_{+}+{a^{2}\over r_{+}})=2\pi(2M-{Q^{2}\over
r_{+}})\leq 4\pi M\,.$ (8)

The right hand side of (8) is certainly an upper bound for the Birkhoff
invariant and so the conjecture certainly holds in this case.

However the horizon is prolate in character, in the sense that the polar
circumference $l_{p}$ which is the length of a meridional geodesic $l_{p}$
(i.e. one with $\phi={\rm constant}$ and $\phi={\rm constant}+\pi$ ), is

$l_{p}=\sqrt{r_{+}^{2}+a^{2}}\int^{\pi}_{0}\sqrt{1-x^{2}\sin^{2}\theta}\,d\theta\,.$
(9)

In fact taking $f=\sin\theta\cos\phi$, we have

$\beta(\sin\theta\cos\phi)=l_{p}\,,$ (10)

and since

$\sqrt{r_{+}^{2}+a^{2}}\leq r_{+}+{a^{2}\over r_{+}}\,,$ (11)

we have

$\beta(g)\leq l_{p}\leq l_{e}\leq 4\pi M\,.$ (12)

Despite being prolate, the Gaussian curvature $K$ of the surface is given by

$K={({r_{+}}^{2}+a^{2})(r_{+}^{2}-3a^{2}\cos^{2}\theta)\over({r_{+}}^{2}+a^{2}\cos^{2}\theta)^{3}}\,,$
(13)

and can become negative at the poles $\theta=0,\pi$.

The Kerr-Newman metrics have been generalised to include up to four different
charges associated with four different abelian vector fields [12]. In the
subclass for which only two charges are non-vanishing we can use the results
of [13] to examine the conjecture. The energy momentum tensor of the system
satisfies the Dominant Energy Condition and the horizon geometry may be
extracted from eqn(45) of [13]

$ds^{2}=Wd\theta^{2}+{(r_{+1}r_{+2}+a^{2})^{2}\over
W}\sin^{2}\theta\,d\phi^{2}\,,$ (14)

with

$W=r_{+1}r_{+2}+a^{2}\cos^{2}\theta\,.$ (15)

and

$r_{+1}=r_{+}+2m\sinh^{2}\delta_{1}\,,\qquad
r_{+2}=r_{+}+2m\sinh^{2}\delta_{2}$ (16)

with $r_{+}$ the larger root of $r^{2}-2mr+a^{2}=0$ and $\delta_{1}$ and
$\delta_{2}$ two parameters specifying the two charges. If
$\delta_{1}=\delta_{2}$ we obtain the Kerr-Newman case.

Just as the horizon geometry of the Kerr-Newman solution is isometric to that
of the neutral Kerr, so in this more general case, we find an isometric
horizon geometry. Of course the interpretation of the parameters occurring in
the metric is different, but the geometry is the same. Thus

$\beta(g)\leq l_{p}\leq
l_{e}=2\pi\bigl{(}\sqrt{r_{+1}r_{+2}}+{a^{2}\over\sqrt{r_{+1}r_{+2}}}\bigr{)}\,.$
(17)

Now for positive $x,y,z$,

$xy\leq{1\over 4}(x+y)^{2}\,,\quad\Longrightarrow\quad\sqrt{(z+x)(z+y)}\leq
z+{\textstyle{1\over 2}}(x+y)\,.$ (18)

Thus,

$\sqrt{r_{+1}r_{+2}}\leq
r_{+}+m\bigl{(}\sinh^{2}\delta_{1}+\sinh^{2}\delta_{2}\bigr{)}$ (19)

and

${a^{2}\over\sqrt{r_{+1}r_{+2}}}\leq{a^{2}\over r_{+}}\,,$ (20)

Thus

$\bigl{(}\sqrt{r_{+1}r_{+2}}+{a^{2}\over\sqrt{r_{+1}r_{+2}}}\bigr{)}\leq
r_{+}+m\bigl{(}\sinh^{2}\delta_{1}+\sinh^{2}\delta_{2}\bigr{)}+{a^{2}\over
r_{+}}.$ (21)

But

$2m=r_{+}+{a^{2}\over r_{+}}\,,$ (22)

and the ADM mass is given by

$M_{ADM}=2m+2m\bigl{(}\sinh^{2}\delta_{1}+\sinh^{2}\delta_{2}\bigr{)}$ (23)

Thus

$\beta(g)\leq 4\pi M_{ADM}\,,$ (24)

and the conjecture holds in this case. It would be interesting to check it in
the four charge case, but the algebra appears to be rather more complicated.

##  3 Collapsing Shells and Convex Bodies

There is a class of examples [11] in which a shell of null matter collapses at
the speed of light in which the apparent horizon $S$ may be thought of as a
convex body isometrically embedded in Euclidean space ${{E}}^{3}$. In this
case one has

$8\pi M_{\rm ADM}\geq\int_{S}HdA\,,$ (25)

where $H={\textstyle{1\over 2}}({1\over R_{1}}+{1\over R_{2}})$ is the mean
curvature and $R_{1}$ and $R_{2}$ the principal radii of curvature of $S$ and
$dA$ is the area element on $S$. The right hand side is called the total mean
curvature and it was shown by Álvarez Paiva [3] in this case that

$\beta(g)\leq{\textstyle{1\over 2}}\int_{S}HdA\,.$ (26)

Combining Álvarez Paiva’s (26) with (25) establishes the conjecture (4) in
this case.

In fact the proof is close to the ideas in [4] and so we briefly review it. If
${\bf n}$ is a unit vector we define the height function on
$S\subset{{E}}^{3}$ by

$h={\bf n}.{\bf x}\,,\qquad{\bf x\in S}\,.$ (27)

Let $S_{\bf n}$ be the orthogonal projection of the body $S$ onto a plane with
unit normal ${\bf n}$ and let $C({\bf n})=l(\partial S_{\bf n})$ be the
perimeter of $S_{\bf n}$. Then

$\beta(g)\leq\beta(h)\leq C({\bf n})\,.$ (28)

Now [4]

$\int_{S}HdA={1\over 2\pi}\int_{S^{2}}C({\bf n})d\omega\,,$ (29)

where $d\omega$ is the standard volume element on the round two-sphere $S^{2}$
of unit radius. Thus averaging (28) over $S^{2}$ and using (29) gives (26).

##  4 Shadows and widths

The total mean curvature of a convex surface in Euclidean space has a number
of interpretations. The width $w({\bf n})=w(-{\bf n})$ is the distance between
two parallel tangent planes with normals $\pm{\bf n}$. One has

${1\over 2\pi}\int_{S}HdA=\langle w\rangle={1\over 4\pi}\int_{S}^{2}w({\bf
n})d\omega\,.$ (30)

Thus if

$M={1\over 8\pi}\int_{S}HdA\,,$ (31)

then

$W\geq 4M\geq w$ (32)

where $W$ is the greatest and $w$ the smallest width

Similarly the Tod points out [4] that

${1\over 16\pi}C_{m}\leq M\leq{1\over 4\pi}C_{m}\,,$ (33)

where $C_{m}$ is the largest perimeter of any orthogonal projection of the
body.

##  5 Quasi-local masses

Recent suggestions for a quasi-local mass expression [14, 15, 16, 17, 18] have
involved isometrically embedding the horizon into Euclidean space ${{E}}^{3}$.
This will, by results of Weyl and Pogorelov, certainly be possible if the
Gauss curvature of $S$ is positive. In that case, since the embedding is
isometric, the Birkhoff invariant can be calculated as if the surface is in
flat Euclidean space and the inequality (26) holds. The total mean curvature
$H$ associated with the embedding into ${{E}}^{3}$ also enters into the
suggested expression for the quasi-local mass of a trapped surface,

$4\pi M_{KLY}=\int_{S}\bigl{(}H-\sqrt{2\rho\mu}\bigr{)}dA$ (34)

where $-2\rho$ and $2\mu$ are the expansions of outward and ingoing null
normals, suitably normalised.

Thus it is possible that some progress could be made there. However, as we
have seen above the Gaussian curvature of the Kerr-Newman horizon can become
negative near the poles, and as a consequence it cannot be isometrically
embedded into ${{E}}^{3}$. Ignoring this difficulty for the time being, we
observe that in the time symmetric case for a marginally outer trapped surface

$4\pi M_{KLY}=\int_{S}HdA\leq\beta(g)\,.$ (35)

##  6 Areas

It is now well established that the area $A(g)$ of the outermost marginally
trapped surface should satisfy Penrose’s isoperimetric type conjecture that

$\sqrt{\pi A(g)}\leq 4\pi M_{ADM}\,.$ (36)

Evidently, if we could bound $\beta(g)$ above by by $\sqrt{\pi A(g)}$ we would
have a proof of my version (4) of the hoop conjecture. On the other hand, if
we can bound $\sqrt{\pi A(g)}$ above by $\beta(g)$, then the hoop conjecture
would imply the Penrose conjecture.

This raises the question of what is known about bounds for $A(g)$, $\beta(g)$,
$l(g)$ and other invariants, either for a surface in general, or one with some
additional restrictions.

We begin by noting that the Riemannian metric $g$ on $S$ allows us to define a
distance $d(x,y)=d(y,x),x,y\in S$ which is the infinum of the length of all
curves from $x$ to $y$. Then

$b(x)=\max_{y}\,d(x,y)$ (37)

is the furthest we can get from $x$. We then define

$\displaystyle e(g)$ $\displaystyle=$
$\displaystyle\min_{x}b(x)=\min_{x}\max_{y}d(x,y)$ (38) $\displaystyle E(g)$
$\displaystyle=$ $\displaystyle\max_{x}b(x)=\max_{x}\max_{y}\,d(x,y)$ (39)

Hebda [21] provides a lower bound for $A$:

$\sqrt{A(g)}\geq{1\over\sqrt{2}}\bigl{(}2e(s)-E(g)\bigr{)}\,.$ (40)

Using (36) we get

$4\pi M_{ADM}\geq{\sqrt{\pi\over 2}}\bigl{(}2e(s)-E(g)\bigr{)}\,,$ (41)

For the sphere the right hand side of (40) is $\sqrt{2\pi^{3}}M_{ADM}$ which
is satisfied but not sharp. There seems therefore no reason to choose
$C(g)={\sqrt{\pi\over 2}}\bigl{(}2e(s)-E(g)\bigr{)}$, in order to sharpen
Thorne’s conjecture.

Another lower bound for the area has been given by Croke [22]. If, as above,
$l(g)$ is the length of the shortest non-trivial geodesic on $S$, then Croke
proves that

$\sqrt{A(g)}\geq{1\over 31}l(g)\,.$ (42)

This is again, far from the best possible result, which Croke conjectures to
be

$\sqrt{A(g)}\geq{1\over 3^{1\over 4}2^{{\textstyle{1\over 2}}}}l(g)\,,$ (43)

which is attained for two flat equilateral triangles glued back to back.

If we use (36 ) and (43 we obtain

$\Bigl{(}{\pi^{2}\over 12}\Bigr{)}^{1\over 4}l(g)\leq 4\pi M_{ADM}\,.$ (44)

If one takes $C(g)=l(g)$, then (44) is weaker than Thorne’s suggestion and
taking $C(g)=\Bigl{(}{\pi^{2}\over 12}\Bigr{)}^{1\over 4}l(g)$ looks rather
perverse, and in any case there is a problem about when it is attained.
Moreover, since $\beta(g)\geq l(g)$, we cannot easily relate (44) to my form
of the conjecture (4). Curiously however, for a special class of surfaces, we
can improve considerably on (40) or (44).

###  6.1 Horizons admitting an anti-podal map

Many results for general surfaces rely on on the existence of non-null
homotopic closed curves. For a surface with spherical topology no such curves
exist. However it is possible to restrict attention to the special class of
surfaces for which ${{Z}}_{2}$ acts freely and isometrically such that
$x\rightarrow Ix$. The quotient $S^{2}/I\equiv{{R}P}^{2}$ and Pu provides a
lower bound for$A(S/I)$ in terms of the the systole ${\rm sys}(S/I)$, i.e. the
length of the shortest non-null homotopic curve:

$\sqrt{A(S/I)}\geq\sqrt{2\over\pi}{\rm sys}(S/I)\,.$ (45)

Now the shortest non-null homotopic curve on $S/I$ is a closed geodesic which
lifts to a closed geodesic of twice the length on $S$, thus

${\rm sys}(S/I)=\min_{x}\,d(x,Ix)\leq b(x)\leq e(g)\,,$ (46)

where $b(x)$ and $e(g)$ are taken on the spherical double cover. If, as
before, $l(g)$ is the length of the shortest non-trivial geodesic on $S$, then
for this class of metrics

$\sqrt{A(g)}\geq{2\over\sqrt{\pi}}\,{\rm sys}(S/I)\geq{l(g)\over\sqrt{\pi}}$
(47)

and hence, using (36) we obtain for this class of metrics,

$l(g)\leq 4\pi M_{ADM}\,,$ (48)

i.e. the inequality (5) which is a consequence of my version of the hoop
conjecture (4). Thus no counter example to to my conjecture can be constructed
within the class of horizons admitting an antipodal isometry.

Of course (5) is of the form of Thorne’s suggestion, if we take the
circumference $C=l(g)$. However $l(g)$ does not carry with it the idea of the
least circumference in all directions. I have argued above that it is
$\beta(g)$ which better captures that notion, and so I prefer to think of (5)
of the more basic inequality (4) and the fact that (5) holds in this special
case as a confirmation of the general plausibility of this line of argument.

It will perhaps be felt instructive to recall some of the details of Pu’s
proof. He makes use of the fact that any metric $g$ on ${{R}}{{P}}^{2}$ may be
written as

$ds^{2}=\Omega^{2}(\theta,\phi)\bigl{(}d\theta^{2}+\sin^{2}\theta
d\phi^{2}\bigr{)},$ (49)

where $\Omega(\theta,\phi)=\Omega(\pi-\theta,\phi+\pi)$. Thus

$A(S/I))=\int\Omega^{2}\sin\theta d\theta d\phi,$ (50)

and

${\rm sys}(g)=2\inf_{x}\inf_{\gamma}\int_{\gamma}\Omega d\sigma$

where $\gamma$ is a curve running from $x\equiv(\theta,\phi)$ to
$-x\equiv(\pi-\theta,\phi+\pi)$ and $d\sigma$ is the element of length
calculated using the round metric.

Now Pu considers the effect of averaging the conformal factor $\Omega$ with
respect to the action of $SO(3)$, using the Haar or bi-invariant measure on
$SO(3)$. If the averaged metric, which is of course the round metric, is
$\overline{g}$, one has

$A({\overline{g}})\leq A(g)$ (51)

but

$s({\overline{g}})\geq s(g).$ (52)

Thus the ratio $A/s^{2}$ is never smaller than for the round metric
${\overline{g}}$, and this case it is ${1\over\pi}$ and so his inequality
follows.

###  6.2 Injectivity and Convexity Radii

The mathematical literature on area, the lengths of geodesics etc is often
couched in terms of the injectivity radius $i(g)$ and the convexity radius
$c(g)$. In the sequel we mainly follow the papers of Berger [24, 25, 26]. The
definitions are valid for any dimension.

The injectivity radius $i(x)$ of a point $x\in S$ is the supremum of the
distances out to which which the exponential map is a diffeomorphism onto its
image. The injectivity radius $i(g)$ of the manifold is the infinum over all
points in $S$ of $i(x)$. In the case of an axisymmetric body for which the
metric may be written as

$ds^{2}=R^{2}\Bigl{\\{}d\theta^{2}+a^{2}(\theta)d\phi^{2}\Bigr{\\}}$ (53)

with $R$ an overall constant setting the scale, $0\leq\theta\leq\pi$, the
injectivity radius of the north ($\theta=0$) or south ($\theta=\pi$pole is
${1\over 2}l_{p}=\pi R$ and

$i(g)\leq{1\over 2}l_{p}\,.$ (54)

Now local extrema of $a(\theta)$ correspond to azimuthal geodesics. If the
Gaussian curvature is positive, there will only be one, and define $l_{e}$ as
its length. Otherwise $l_{e}$ as the smallest such length.

$l(g)\leq l_{p}\,,\qquad l(g)\leq l_{e}$ (55)

The convexity radius $c(x)$ of a point $x$ is the largest radius for which the
geodesics ball $B_{c}(x)$ centred on $x$ is geodesically convex, that is every
point in $B_{c}(x)$ is connected by a unique geodesic interval lying entirely
within $B(x)$. The convexity radius $c(g)$ of the manifold is the infinum over
all points in $S$ of $c(x)$. On the round unit-sphere ($R=1$) we have $i=\pi$
and $c={\pi\over 2}$.

Now Berger proves that

$l(g)\geq 2c(g)\,.$ (56)

and hence

$\beta(g)\geq 2c(g)$ (57)

Thus in the case of horizons admitting an antipodal map, we can combine Pu’s
result and (36) to obtain

$2c(g)\leq 4\pi M_{ADM}\,,$ (58)

in the case that my form of the hoop conjecture (4) holds we obtain from (57)
the same result. In fact Klingenberg has shown that either

$l(g)=2i(g)$ (59)

or there is a geodesic segment of length $l(g)$ whose end points are
conjugate. Finally for metrics on $S^{2}$ we have [27, 28] the so-called
isembolic inequality

$\sqrt{\pi A}\geq 2i(g)\geq 4c(g)$ (60)

and hence by (36)

$4\pi M_{ADM}\geq 2i(g)\geq 4c(g)\,.$ (61)

##  7 Higher dimensions

Birkhoff’s invariant has a natural generalisation to higher dimensions (see
e.g. [19] ) In the simplest case of an $n$-dimensional horizon, topologically
equivalent to $S^{n}$, one considers foliations whose leaves are topologically
$S^{n-1}$’s. There is then an obvious generalisation of (4) relating the ADM
mass to the infinum over all foliations of the $(n-1)$-volume of the leaf of
greatest $(n-1)$-volume.

Pu [23] points out the obvious generalisation to metrics on ${{R}}{{P}}^{n}$
which are conformal to the round metric. However except in the case $n=2$, not
every metric on ${{R}}{{P}}^{n}$ is conformal to the flat round metric and so
for $n>2$ this is a very special case. However Berger’s isembolic inequality
does generalise in an obvious way to all dimensions.

Of course it is by now notorious [20] that in five dimensional spacetimes,
horizons need not be topologically spherical and in particular one has black
rings with horizon topology $S^{1}\times S^{2}$. The methods and ideas of [19]
should also be relevant in that case.

Further discussion of the higher dimensional situation will be deferred for a
future publication.

##  8 Acknowledgements

I am grateful to Gabor Domokos for bringing [3] to my attention and hence re-
igniting my interest in these questions. I thank Harvey Reall, Gabriel
Paternain, Chris Pope, Paul Tod and Shing-Tung Yau and Claude Warnick for
helpful comments and suggestions.

## References

  * [1] K S Thorne, Nonspherical Gravitational Collapse: A Short Review  in Magic without Magic ed. J Klauder (San Francisco: Freeman) (1972)
  * [2] J. M. M. Senovilla, A Reformulation of the Hoop Conjecture Europhys. Lett. 81, 20004 (2008) [arXiv:0709.0695 [gr-qc]].
  * [3] J .C. Álvarez Paiva, Total mean curvature and closed geodesics. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 373–377.
  * [4] K. P. Tod, The hoop conjecture and the Gibbons-Penrose construction of trapped surfaces Class Quantum Grav 9 (1992) 1581-1591
  * [5] G. D. Birkhoff, Dynamical systems with two degrees of freedom Trans. Amer. Math. Soc.  18 (1918)
  * [6] S. W. Hawking, Black holes in general relativity. Comm. Math. Phys. 25 (1972), 152-166.
  * [7] G. W. Gibbons, The time symmetric initial value problem for black holes, Commun. Math. Phys. 27 (1972) 87.
  * [8] G. W. Gibbons, Some Aspects of Gravitational Radiation and Gravitational Collapse Ph.D. Thesis, University of Cambridge (1972)
  * [9] S. W. Hawking, The event horizon , in Black holes (Les astres occlus) C. M. and B. De Witt(1973) 1-55
  * [10] L. Smarr, Surface Geometry of Charged Rotating Black Holes, Phys Rev D 7 (1973) 289
  * [11] G. W. Gibbons, Collapsing Shells and the Isoperimetric Inequality for Black Holes, Class. Quant. Grav. 14 (1997) 2905 [arXiv:hep-th/9701049].
  * [12] M. Cvetic and D. Youm, Entropy of Non-Extreme Charged Rotating Black Holes in String Theory, Phys. Rev. D 54, (1996) 2612 [arXiv:hep-th/9603147].
  * [13] Z. W. Chong, M. Cvetic, H. Lu and C. N. Pope, Charged rotating black holes in four-dimensional gauged and ungauged supergravities, Nucl. Phys. B 717 (2005) 246 [arXiv:hep-th/0411045].
  * [14] C. C. Liu and S. T. Yau, New definition of quasilocal mass and its positivity,” Phys. Rev. Lett.  90 (2003) 231102 [arXiv:gr-qc/0303019].
  * [15] C. C. Liu and S. T. Yau, Positivity of quasi-local mass II, J. Amer. Math. Soc. 19 (2006) 181-204 [arXiv:math/0412292].
  * [16] M. T. Wang and S. T. Yau, A generalization of Liu-Yau’s quasi-local mass, [ arXiv:math/0602321].
  * [17] M. T. Wang and S. T. Yau Quasi-local mass in general relativity Phys.Rev.Lett102(2009) 021101 [arXiv:0804.1174[gr-qc]].
  * [18] M. T. Wang and S. T. Yau Isometric embeddings into the Minkoswksi spactime and new quasi-local mass Commun Math Phys  in press [arXiv:0805.1370[math.DG]].
  * [19] T Colding and W.P. Minicozzi II, Width and Finite Extinction Time of Ricci Flow [arXiv:0707.0108 [math.DG]].
  * [20] R. Emparan and H. S. Reall, A rotating black ring in five dimensions, Phys. Rev. Lett.  88 (2002) 101101 [arXiv:hep-th/0110260].
  * [21] J Hebda, Some Lower Bounds for the Area of Surfaces, Inventiones Mathematicae 65 (1982) 485-490
  * [22] C. B. Croke, Area and the length of the shortest geodesic J Differential Geometry 27 (1988) 1-21
  * [23] P.M. Pu, Some inequalities in certain non-orientable Riemannian manifolds, Pacific J Math 2 (1952) 55-71
  * [24] M Berger, Some relations between volume, injectivity radius and convexity radius in Riemannian manifolds, in Cahen and Flato eds. Differential Geometry and Relativity , Dordrecht ( 1976)
  * [25] M Berger, Filling Riemannian manifolds or isosytolic inequalities, in T J Wilmore and N J Hitchin (eds) Global Riemannian Geometry, Ellis-Horwood(1984)
  * [26] M Berger, Riemannian Geometry during the second half of the twentieth century, Jahresber. Deutsh. Math-Verein 100 (1998) 45-208
  * [27] M. Berger and B. Gostiaux, Differential Geometry Manifolds, Curves and Surfaces Graduate Texts in Mathematics 115 Springer-Verlag (1988) section 11.4.4 p.413
  * [28] C Croke, Curvature free volume estimates Inventiones Mathematicae 75(1984) 515-512


# Identifying blockchain-based cryptocurrency accounts using investment
portfolios

Amin Aghaee
Vancouver, BC, Canada
https://aminrd.github.io

###### Abstract

Cryptocurrencies based on decentralized systems, especially blockchain, are
gaining popularity more than ever. Freedom advocates hail blockchain
technology as a breakthrough in digital privacy and internet anonymity.
Unfortunately, after recent studies conducted, it may come as a surprise that
the transactions are, in fact, not always anonymous. In this short paper, the
possibility of identifying a user’s accounts in different cryptocurrencies
given the user’s portfolio of investment gained from social media is
investigated. In this study, the generic elements of blockchain systems are
briefly studied. In section 3, BlockSim which is a tool for simulating
transactions, and an algorithm for answering this question is introduced.

_Keywords_ Blockchain $\cdot$ Cryptocurrency $\cdot$ Identification $\cdot$
Social Media $\cdot$ Approximate Algorithms

##  1 Introduction

A cryptocurrency (also known as crypto) is a digital currency in which
transactions are verified and records maintained by a decentralized system
using cryptography, rather than by a centralized authority. Cryptography
provides a mechanism for securely encoding the rules of a cryptocurrency
system in the system itself. Narayanan et al. (2016) Many recent popular
cryptocurrencies (e.g. Bitcoin, Ethereum, etc.) are decentralized networks
based on blockchain technology.

In recent years, the growth of Bitcoin, Ethereum, and other cryptocurrencies
is a phenomenon that has attracted unprecedented attention. Caporale et al.
(2018) For years, markets and currencies have been controlled by centralized
systems such as governments and central banks. However, the usage of
cryptocurrencies keeps evolving day by day due to some benefits these new
decentralized currencies suggest, such as privacy, security, access, and
efficiency.

In most blockchain systems, especially in cryptocurrencies, all transactions,
the wallet addresses involved are recorded on a public chain and are available
for everyone. Although wallet addresses alone do not disclose identifiable
details, they do provide some information for further investigation. Revealing
some contact-related information and user identifications has gained
attraction in recent years Chang and Svetinovic (2018). Alqassem et al. for
example studied ways for suggesting some techniques for Bitcoin Data analysis
Alqassem et al. (2018).

The effect of social media on almost everything is not deniable these days.
The cryptocurrency market is controlled by many factors including social media
Aggarwal et al. (2019). As an example, many people post the latest trends
related to cryptocurrencies on Reddit, and share their portfolio of investment
on social media. In this paper, the question of whether we can disclose users’
accounts using their portfolio of investment in multiple cryptocurrencies is
investigated.

##  2 Background And Problem Definition

In this section, some public characteristics of a blockchain system are
briefly described. A comprehensive study of blockchain systems is well written
in Bashir (2020). Each blockchain system consists of some fundamental
elements. Some of the generic elements in each blockchain system, or more
specifically in a cryptocurrency blockchain system which is related to this
work are Bashir (2017):

  * •

Addresses: Unique identifiers being assigned to accounts

  * •

Transactions: Information about transferring some value from a source address
to a destination address

  * •

Blocks: Multiple transaction information, the previous and the next block, and
some other meta information are stored in a block

  * •

Distributed consensus: Enables a blockchain system to have a single trusted
history shared between all people and nodes in the network

When user $A$ wants to transfer some value $v$ from his account $a_{A}$ to
another account $a_{B}$ which belongs to user $B$, the following steps happen
Bashir (2017):

  1. 1.

Sender $A$ signs the transaction using his/ her private key

  2. 2.

The transaction information is broadcasted to the network using a specific
algorithm called flooding

  3. 3.

Miner nodes add the information about this transaction to their block

  4. 4.

After a couple of transactions happened, a miner who can provide a proof of
work (PoW), can add a reward value $v_{r}$ to his/ her account $a_{m}$ and
broadcasts the solved problem to the network

  5. 5.

Every other node and miner in the network verify and add the recently solved
block into their block. Thus, the information about the transaction between
accounts $a_{A},a_{B}$ which is inside the recently-solved block is also
broadcasted

  6. 6.

Finally, the value starts to be appeared in $a_{B}$ after between three to six
confirmations

When it comes to privacy protection in a distributed database, blockchain
systems have significant advantages Wang et al. (2020); Zyskind et al. (2015).
The history of all transactions that happened in a public blockchain system is
considered public information and is accessible to everyone. For example, the
history of all transactions in Bitcoin from the first transaction in January
2009 is publicly available. Nonetheless, the public address of the accounts is
stored in the blocks rather than user identities. For instance, you can have
an account in Bitcoin which has a public address that only you and those who
want to send money to you know whose this address belongs to. For other
people, this public address may seem like a series of random numbers.

Nonetheless, the privacy and confidentiality of users is still a debatable
topic that has been studied in recent years (Menegalli-Boggelli (2021); Conti
et al. (2018); Zaghloul et al. (2020); Androulaki et al. (2013)). In this
paper, a case is studied in which the following question is investigated: Are
we able to identify users’ accounts in different cryptocurrencies having their
portfolio of investment? Each user can have one or multiple accounts. In this
paper, we study the simple case of this problem by limiting the number of
accounts users can have in a single cryptocurrency to one. In other words,
every user can hold at most one account in cryptocurrencies such as Bitcoin,
Ethereum, etc.

In order to define the problem officially, let say we have a set of $m$
cryptocurrencies $C=\\{C_{1},C_{2},...,C_{m}\\}$. User $A$ has one account in
each of these cryptocurrencies. $U$’s portfolio of investment is:

$P=\\{\alpha_{1},\alpha_{2},...,\alpha_{m}\\},\forall i\leq i\leq
m:0\leq\alpha_{i}\leq 1,\sum_{i=1}^{m}\alpha_{i}=1$

That means if $v$ is the total investment of user $U$ in all cryptocurrencies,
$\alpha_{1}\times v$ is invested in currency $C_{1}$, $\alpha_{2}\times v$ is
invested in currency $C_{2}$ and etc. User $U$ holds these amounts in accounts
$A_{U}=\\{a_{u}^{1},a_{u}^{2},...,a_{u}^{m}\\}$ where $\forall i:a_{u}^{i}\in
C_{i}$. Finding $A_{U}$ given $P$ is studied in this article.

##  3 BlockSim

One of the challenges of this problem in a real scenario is that we do not
know the account owners of different cryptocurrencies. BlockSim
111https://github.com/aminrd/BlockSim, is a Python package for simulating the
transactions of multiple cryptocurrencies. In BlockSim, you can define:

  * •

User acquisition rate, which is the rate of adding new users to a
cryptocurrency over time

  * •

Number of turns for simulation

  * •

Number of cryptocurrencies in your system

  * •

Number of transactions in each turn in a turn

  * •

Miner rate for each cryptocurrency, which specifies the transaction fee
described in 2

Once these variables are defined, the simulator starts storing the transaction
information into a database, in which records of all simulated users, their
accounts, and all transactions are stored. Note that in a real scenario, since
all transactions of many cryptocurrencies are public, it is possible to go
through the transactions one by one and recreate the database. For example,
let say we have the investment portfolio of a user in Bitcoin, Ethereum, and
Cardano at time $t$. We can start from time $0$ and create three different
databases of $\\{C_{Bitcoin},C_{Ethereum},C_{Cardano}\\}$ each of which
contains multiple accounts. To speed up our process of finding $A_{u}$, we
drop all accounts holding zero balances. It is important to note that, when we
refer to balance in this case, we refer to balances all converted into a
common currency (either a fiat currency or a cryptocurrency) at time $t$ so
that we can compare the value of an account in $C_{Bitcoin}$ to the value of
another account in $C_{Ethereum}$.

Let say a possible answer to the problem given investment portfolio
$P=\\{\alpha_{1},\alpha_{2},...,\alpha_{m}\\}$ is
$A_{U}=\\{a_{u}^{1},a_{u}^{2},...,a_{u}^{m}\\}$. In order to evaluate this
answer and compare it to other answers, we need to define a score. The
following score is proposed:

$score=m-\sum_{a_{i}\in
A_{U}}|\alpha_{i}-\frac{a_{i}\text{.balance}}{\sum_{a\in
A_{U}}a\text{.balance}}|$

A pseudo-code for the algorithm of finding accounts that respect the
investment portfolio is in algorithm 1. The method starts with creating the
databases of all cryptocurrencies from time $0$ to time $t$ sorted by the
number of non-zero-balance accounts. Thus, the first crypto database on the
list is $C^{t}_{sorted}(1)$ that has the least number of accounts. All
accounts in each crypto database are also sorted by balances. Then, for each
account $a\in C^{t}_{sorted}(1)$, other potential accounts in other crypto
databases are looked for. Note that, for each account $a\in C^{t}_{1}$, we are
looking for an account $b\in C^{t}_{i}$ so that
$\frac{a\text{.balance}}{b\text{.balance}}=\frac{\alpha_{1}}{\alpha_{i}}$.
Thus, we know what is the target balance in other crypto databases to look
for. The method for finding one or multiple accounts in a crypto database is
defined in BinaryFind 2.

Input : Portfolio $P=\\{\alpha_{1},\alpha_{2},...,\alpha_{m}\\}$,
Cryptocurrencies $C=\\{C_{1},C_{2},...,C_{m}\\}$, Time $t$, Score Threshold
$S_{t}$

Output : An answer $A^{*}=\\{a^{*}_{1},a^{*}_{2},...,a^{*}_{m}\\}$

1

2$C^{t}\leftarrow$ All cryptocurrencies in $C$ sorted by their number of
accounts at time $t$;

3

4$C^{t}_{sorted}\leftarrow\\{sort(C^{t}_{1}),sort(C^{t}_{2}),...,sort(C^{t}_{m})\\}$
by account balances at time $t$;

5

6$Answers\leftarrow$ an empty set $\\{\\}$ ;

7

8foreach  _$a\in C^{t}_{sorted}(1)$.accounts_ do

9

10 $A_{1}\leftarrow\\{a\\}$ ;

11 for  _$i\in\\{2,3,...,m\\}$ _ do

12 $A_{i}\leftarrow$ BinaryFind($C^{t}_{sorted}(i)$.accounts, $a$.balance
$\times\frac{\alpha_{i}}{\alpha_{1}}$)

13 end for

14 foreach  _$ans\in\\{A_{1}\times A_{2}\times...\times A_{m}\\}$_ do

15 if  _score( $ans$) $\geq S_{t}$_ then

16 $Answers$.add($ans$) ;

17

18 end if

19

20 end foreach

21

22 end foreach

23

24return $\operatorname*{argmax}_{A^{*}}score(A^{*})$ where $A^{*}\in
Answers$;

25

Algorithm 1 Algorithm for finding potential accounts satisfying a portfolio
holder

BinaryFind 2 algorithm is inspired by the binary search method with some
adjustments. The run-time complexity of binary search algorithm on a sorted
list having $n$ elements is $\mathcal{O}(n\log n)$. If the algorithm finds the
target balance in the list of accounts, it returns all accounts having that
balance. If no accounts are found, then at least two accounts as the lower
bound and higher bounds of the target balance would be returned. For instance,
if a list of accounts is:

$\\{(id,balance)^{\prime}s\\}=\\{(1,1.23),(2,3.78),(3,6.0),(4,6.0),(5,7.13),(6,8.2),(7,12.6)\\}$

given a target balance $b=6.6$, the output would be $\\{(3,6.0),(4,6.0)\\}$
and given a target balance $b=7.99$, the output would be
$\\{(5,7.13),(6,8.2)\\}$.

Input : Target balance $b$, Accounts $\\{a_{1},a_{2},...,a_{n}\\}$ sorted by
balances

Output : List of $p$ answers $\\{a^{*}_{1},a^{*}_{2},...,a^{*}_{p}\\}$

1

2if  _$a_{1}\text{.balance} >b$ or $a_{n}\text{.balance}<b$_ then

3 return $\\{\\}$;

4

5 end if

6

7$left,right\leftarrow 1,n$ ;

8

9while  _$right >left$_ do

10 $mid\leftarrow\frac{left+right}{2}$ ;

11 if  _$a_{mid}\text{.balance}==b$_ then

12 $ans\leftarrow\\{a_{mid-l^{*}},...,a_{mid},...,a_{mid+r^{*}}\\}$ where
$\forall a\in ans:a$.balance $==b$;

13 return $ans$

14 end if

15 else if  _$a_{mid}\text{.balance} >b$_ then

16 if  _$right==mid$_ then

17 return $\\{a_{left},...,a_{right}\\}$ ;

18

19 end if

20 else

21 $right\leftarrow mid$;

22

23 end if

24

25 end if

26 else

27 if  _$left==mid$_ then

28 return $\\{a_{left},...,a_{right}\\}$ ;

29

30 end if

31 else

32 $left\leftarrow mid$;

33

34 end if

35

36 end if

37

38 end while

39

Algorithm 2 BinaryFind a target balance in a list of accounts sorted by
balances

After finding all possible accounts in each crypto databases, algorithm 1
creates a set of possible answers derived from the Cartesian product of all
possible accounts $ANS=\\{A_{1}\times A_{2}\times...\times A_{m}\\}$. The
smallest size of $ANS$ is $1$, one average is $2^{m}$ (considering the lower
and upper bounds in BinaryFind’s output) and could be larger if there are many
accounts in each database with exactly equal balances. Then, the score is
computed for each answer in $ANS$, and all answers having scores less than
$S_{t}$ are dropped. Finally, an answer with a maximum score is returned as
the output of this algorithm. A reason for using the score threshold $S_{t}$
is sometimes, multiple possible answers sorted by their scores might be
interested rather than the best answer achieved.

To analyze the complexity of this algorithm, let say $n=\max_{c\in C}size(c)$
where size refers to the number of non-zero-balance accounts in a crypto
database. The method starts by sorting the databases by their sizes in
$\mathcal{O}(m\log m)$. It is clear that $m\ll n$. Thus this part of the
algorithm is negligible. Then, each database is sorted by balances in
$\mathcal{O}(m.n\log n)$. Then BinaryFind is called $m$ times in total
complexity of $\mathcal{O}(m\log n)$. On average, if we assume that there are
$2^{m}$ possible answers to be processed the complexity of the for loop is
$\mathcal{O}(n.m.\log n+n.2^{m})$. Since we know $m\ll n$, the total
complexity of this algorithm would be $\mathcal{O}(m.n\log n)$.

##  4 Case Study

For a case study, a simulation of up to 1000 turns with five simulated
cryptocurrencies was conducted. Each cryptocurrency in this simulation, has a
unique linear formula of user acquisition rate at each turn
$\textit{NewUsers}(t)=\beta_{1}t+\beta_{0}$ with unique miner gifts and
transaction fees. In every turn, all existing users send a random portion of
his/ her balance to a random account in that currency. Summary of results
gained after running Finder method is available in figure 1. In this figure,
the size of $C$ refers to the number of cryptocurrencies or $m$. In this
figure, the normalized scores or $\frac{score}{m}$ are compared. The reason
for using a normalized score is to map the best score obtained from the finder
method between $0$ and $1$. This figure suggests an increasing number of
cryptocurrency accounts in the ratio leads to a higher chance of getting a
better score.

Figure 1: Missing rate vs. size of $C$ on the left, percentile histograms of
normalized scores for different $C$ sizes on the right

In figure 1, the missing rate of different $m$ values is plotted. Missing rate
is the opposite of hitting rate which refers to cases when no solution was
found. Given only one ratio of one type, the missing rate is 100 percent.
There is no practical way to find an account given a single portfolio
$P=\\{1\\}$. This plot also supports the claim that an increasing number of
cryptocurrency accounts in the ratio leads to a higher chance of getting a
better score.

##  5 Conclusion

In this paper, the question of identifying users’ accounts in different
cryptocurrencies given the investment portfolio was studied. This paper
supports the fact claiming cryptocurrencies are not completely anonymous. In
this study, some limitations were considered. For example, one assumption of
this work is that users do not have more than 1 account in a cryptosystem,
while they could have multiple accounts in different cryptosystem. Interesting
problems for further studies could be to discard this limit or to find
probability distributions over all accounts that refer to the confidence level
rather than returning a single answer.

## References

  * Narayanan et al. [2016] Arvind Narayanan, Joseph Bonneau, Edward Felten, Andrew Miller, and Steven Goldfeder.  _Bitcoin and cryptocurrency technologies: a comprehensive introduction_.  Princeton University Press, 2016.
  * Caporale et al. [2018] Guglielmo Maria Caporale, Luis Gil-Alana, and Alex Plastun.  Persistence in the cryptocurrency market.  _Research in International Business and Finance_ , 46:141–148, 2018.
  * Chang and Svetinovic [2018] Tao-Hung Chang and Davor Svetinovic.  Improving bitcoin ownership identification using transaction patterns analysis.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 50(1):9–20, 2018.
  * Alqassem et al. [2018] Israa Alqassem, Iyad Rahwan, and Davor Svetinovic.  The anti-social system properties: Bitcoin network data analysis.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 50(1):21–31, 2018.
  * Aggarwal et al. [2019] Gourang Aggarwal, Vimal Patel, Gaurav Varshney, and Kimberly Oostman.  Understanding the social factors affecting the cryptocurrency market.  _arXiv preprint arXiv:1901.06245_ , 2019.
  * Bashir [2020] Imran Bashir.  _Mastering Blockchain: A deep dive into distributed ledgers, consensus protocols, smart contracts, DApps, cryptocurrencies, Ethereum, and more_.  Packt Publishing Ltd, 2020.
  * Bashir [2017] Imran Bashir.  _Mastering blockchain_.  Packt Publishing Ltd, 2017.
  * Wang et al. [2020] Dan Wang, Jindong Zhao, and Yingjie Wang.  A survey on privacy protection of blockchain: The technology and application.  _IEEE Access_ , 8:108766–108781, 2020.
  * Zyskind et al. [2015] Guy Zyskind, Oz Nathan, et al.  Decentralizing privacy: Using blockchain to protect personal data.  In _2015 IEEE Security and Privacy Workshops_ , pages 180–184. IEEE, 2015.
  * Menegalli-Boggelli [2021] Aaron Menegalli-Boggelli.  Proving ownership of bitcoin-like utxo’s using a zk-snark scheme.  2021\.
  * Conti et al. [2018] Mauro Conti, E Sandeep Kumar, Chhagan Lal, and Sushmita Ruj.  A survey on security and privacy issues of bitcoin.  _IEEE Communications Surveys & Tutorials_, 20(4):3416–3452, 2018.
  * Zaghloul et al. [2020] Ehab Zaghloul, Tongtong Li, Matt W Mutka, and Jian Ren.  Bitcoin and blockchain: Security and privacy.  _IEEE Internet of Things Journal_ , 7(10):10288–10313, 2020.
  * Androulaki et al. [2013] Elli Androulaki, Ghassan O Karame, Marc Roeschlin, Tobias Scherer, and Srdjan Capkun.  Evaluating user privacy in bitcoin.  In _International conference on financial cryptography and data security_ , pages 34–51. Springer, 2013.