# Linguistic ambiguity analysis in ChatGPT

Miguel Ortega-Martín
dezzai, UCM
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Óscar García-Sierra
dezzai, UCM
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
Alfonso Ardoiz
dezzai
<EMAIL_ADDRESS>
Jorge Álvarez
dezzai
<EMAIL_ADDRESS>

Juan Carlos Armenteros
dezzai
<EMAIL_ADDRESS>
Adrián Alonso
dezzai, URJC, DSL URJC
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Linguistic ambiguity is and has always been one of the main challenges in
Natural Language Processing (NLP) systems. Modern Transformer architectures
like BERT, T5 or more recently InstructGPT have achieved some impressive
improvements in many NLP fields, but there is still plenty of work to do.
Motivated by the uproar caused by ChatGPT, in this paper we provide an
introduction to linguistic ambiguity, its varieties and their relevance in
modern NLP, and perform an extensive empiric analysis. ChatGPT strengths and
weaknesses are revealed, as well as strategies to get the most of this model.

##  1 Introduction

Sometimes on a day-to-day basis humans struggle to solve linguistic ambiguity,
so we must accept that maybe machines may also face difficulties alike. As
Jurafsky and Martin (2020) state at the start of one the most important
Natural Language Processing books, most of NLP tasks could be seen as a
disambiguation task in any of the six levels in which linguistic is built:
phonetics, morphology, syntax, semantics, pragmatics and discourse. In the
example sentence given by Jurafsky and Martin (2020), "I made her duck", we
can encounter as much as five different senses, which would require
disambiguating in most of the six previous levels. In this work we will focus
on three of them, how they are dealt with in modern NLP systems and what room
is still there for improvement.

This work contains a general review of ambiguity in linguistics (section 2); a
review of how modern NLP systems handle ambiguity problems (section 3); an
introduction to ChatGPT (section 4); an empirical analysis of different types
of linguistic ambiguity with ChatGPT (section 5); the conclusions (section 6);
the limitations of our work (section 7); and the Ethics Statements (section
8). Our contributions in this paper are the following:

  * •

review of current challenges of linguistic ambiguity in NLP.

  * •

analysis of the linguistic weaknesses and strengths of the ChatGPT model
related to linguistic ambiguity.

##  2 Linguistic Ambiguity

Typically, three types of linguistic ambiguity are reviewed when analysing
modern NLP systems: lexical, syntactic and semantic. More complex levels, like
pragmatics and discourse, also present ambiguities, but those are nowadays
still way to far from being solved.

We will focus on these three basic levels as they gather the main challenges
faced by modern NLP models. However, sometimes the borders among levels are
diffuse, and more than one kind of ambiguity could be applied to a given
sentence. For instance, the lexical level also include ambiguities that happen
in the phonetic level, and lexical and syntactic ambiguities mean a change of
meaning and therefore can also be seen as semantic ambiguities.

###  2.1 Lexical Ambiguity

Homonymy and polysemy are the two main representations of lexical ambiguity.
Homonymy refers to those cases in which two words with different etymology and
meaning end up having similar spellings or pronunciations. In the typical
sentence "I went to the bank" the word "bank" can be a financial business or
the area next to a river. Without further context, if we ask anyone "What bank
refers to", its answer should be that the sentence is ambiguous.

As an additional note, we can talk about homophones (two words are read the
same, but could be written differently) and homographs (two words are written
and read the same).

On the other hand, polysemy occurs in those situations in which the same word
can have several meanings. For example, the various meanings that the verb "to
serve" has in the dictionary: "serve time in prison", "serve a tea", etc.

In conclusion, in homonymy, there are two words that have come to the same
form. In polysemy, there is one word that has reached multiple meanings.

###  2.2 Syntactic Ambiguity

This ambiguity does not come from a word, but from groups of words and their
relationships. Also known as amphibology, syntactic ambiguity is due to an
ambiguous sentence structure, in which a chunk or group of words in the
sentence generates more than one interpretation of the whole sentence. A
typical case of syntactic ambiguity is a type of structure like "Mary saw John
with a telescope", in which the prepositional phrase "with a telescope" could
imply that Mary used a telescope to see John, or that John was carrying a
telescope when Mary saw him.

###  2.3 Semantic Ambiguity

In the semantic ambiguity cases, a lack of context leads to more than one
interpretation of a sentence. In the sentence "My mother and my sister were
sad after she shouted at her" without further context, we cannot disambiguate
to whom the pronouns "she" and "her" refer to. In other cases the lack of
context could be bigger. In the sentence "She loves me" we do not have any
clue of who "she" could refer to. Irony, sarcasm or metaphors are other cases
hard to infer, since humans need knowledge of the world and language itself to
understand any hidden meaning.

##  3 Ambiguity in NLP

Ambiguity is a common problem that cannot be solved by the majority of
Language Models (LMs) used in NLP. Most of the time the main problem is the
lack of context. From Information Retrieval (IR) and Question Answering (QA)
to Text Summarization or Grammatical Error Correction systems (Jusoh, 2018),
training Word-sense disambiguation (WSD) systems and knowledge bases (KB) are
some of the techniques traditionally used Bano (2015).

###  3.1 Lexical Ambiguity in NLP

Traditionally, without further Part-of-Speech tagging, it was not possible to
disambiguate homonym words in NLP tasks. For example, in the sentence "How
does a bear bear with the pain?", it would be hard to differentiate the first,
a noun, from the second, a verb. Static embeddings (Mikolov et al., 2013)
suffered this same problem, those two "bear" words would only have one same
embedding. Yet modern contextual embeddings (Liu et al., 2020) used in
Transformers models made a huge advance as the embedding of these same words
with different use would effectively be different. Same happens with polysemy:
given two meaning of a word like the verb "to serve", they will have different
contexts and, therefore, different embeddings.

This can be seen in the Entity
Linking111https://paperswithcode.com/task/entity-linking (EL) task, which is a
common task where we need to disambiguate among personal names. For instance,
in the sentence "Paris Hilton visited Paris" both "Paris" need to be
considered as different entities and matched to their corresponding id from a
KB.

###  3.2 Syntactic Ambiguity in NLP

Syntactic ambiguity plays also a key role in NLP. For instance, dependency
tagging is a common preprocessing technique in which every token of an input
is given a syntactic tag with its corresponding root. Given an ambiguous
syntactic structure, inferring one or another interpretation could have
enormous relevance in latter tasks.

SpaCy222https://spacy.io/ is a state-of-the-art Python library for NLP tasks,
and Dependency tagging is among its capabilities. For the previous
syntactically ambiguous sentence, "Mary saw John with a telescope", an spaCy
Language Model (LM) for English333en_core_web_lg model labels the "telescope"
as a complement of the subject, "Mary". In this case, having one or another
interpretation will highly rely on how those structures were labelled in the
training set of the model. If we introduce more context in the sentence (for
instance, "Mary saw John with a telescope in his hand.") the ambiguity could
be solved by a human being. However, as a proof of how complex is ambiguity
still nowadays for NLP systems, even the best spaCy LM for English labels
"telescope" as a complement of "Mary" in this sentence in which it is clearly
a complement of "John". As stated before, mistakes like this, that could be
due to the quality of the training data, could have a huge impact in latter
tasks. Models rely on the quality of the training data and may also lead to
confirmation bias due statistical relevance.

###  3.3 Semantic Ambiguity in NLP

Figure 1: Attention mechanism. Source: Xie et al. (2021)

Semantic information and its disambiguation have also got better thanks to
contextual embeddings and the attention mechanism. For instance, co-reference
resolution has benefited from this advances. As seen in image 1, the pronoun
"it" has a decent similarity with all the nouns in the sentence. However,
attention is higher with "The" and "monkey", which allows us to disambiguate
their co-reference.

##  4 ChatGPT

Large Language Models (LLMs) have taken over NLP. The current trend among them
is to align their performance with the user intents. In 2022 OpenAI firstly
released IntructGPT Ouyang et al., 2022, a fine-tuned model of GPT-3 Brown et
al. (2020) with supervised learning and 1.3 billion parameter, in which human
feedback plays a key role. At the end of 2022 OpenAI released a sibling model
of IntructGPT, ChatGPT444https://openai.com/blog/chatgpt/, another fine-tuned
version of GPT-3, with 175 millions of parameters and trained to interact with
users and receive feedback from them.

In these models, prompting (Ouyang et al., 2022) and human feedback play a
huge role. A prompt is a piece of text used in the input that aims to reduce
its context as it improves the quality of the output.

Some work has quickly
appeared555https://medium.com/geekculture/i-spent-14-days-testing-chatgpt-
here-are-3-ways-it-can-improve-your-everyday-life-30852a349ad1 focusing on
writing, automatizing, code generation, common knowledge question and
reasoning. But, to the best of our knowledge, linguistic ambiguity has not
been addressed yet.

Thanks to our experiments we have noted that by default it is preferable for
these conversational models to give an answer, even if it is not of sufficient
quality, rather than none at all. This can be applied to cases of poorly
formulated or incomprehensible questions or to situations in which the model
is not really capable of answering a well-formulated question.

##  5 Experimental set-up and analysis

To evaluate how ChatGPT deals with ambiguity, we have carried some experiments
to measure its capabilities. At first, the only public dataset on ambiguity
was considered: Sentence-Ambiguity on Big-BENCH (Srivastava et al., 2022).
However, the type of ambiguity this test deals with, discourse level
ambiguity, was not of interest to us. It was therefore necessary to create new
tests to assess ambiguity at the lexical, syntactic and semantic levels.

To do so, we input some ambiguous sentences via prompting and analyse ChatGPT
outputs. In some occasions some queries required a change to another ChatGPT
season, since we have realised that model’s cache memory helps it to agree
with the user in some situations without further reasoning. Appendixes contain
all the sentences used in our empiric analysis.

The main question for each sentence is if ChatGPT detects the presence or
absence of ambiguity, but each kind of ambiguity will have its own particular
target. In some cases, in addition to the initial ones, we have tried some
other prompts that would allow us to go further in how ChatGPT works in
general and to comprehend its relation with linguistic ambiguity in
particular. For instance, in the case of homonymy it is relevant to ask if
both words are the same, and in the case of polysemy, an special "definition
classification" task is performed.

###  5.1 Lexical Ambiguity

####  5.1.1 Homonymy

Homonym research is focused on homographs (two words that are written and read
the same) since, although homophones have a huge interest for Speech-to-Text
tasks, they are not written the same, so it does not make sense to analyse
them with a text-only system like ChatGPT. Our experiment is designed as the
following:

  * •

We compile a list of sentences (Appendix A.1) and ask the model to label them
as ambiguous or non-ambiguous with the following prompt: Is the sentence
"[sentence]" ambiguous?

  * •

Then we ask the model if the homonyms from a given sentence have the same
meaning using the following prompt: What does every occurrence of the word
"[word]" mean?

  * •

Finally, in some cases we modified the original prompt to check any
improvements in the outputs.

Appendix A.2 contains all the inputs and outputs from this section.

Before getting started with the experiment, human analysis is performed on
the, in theory, non-ambiguous and previously mentioned sentence, "How does a
bear bear with the pain?". This sentence contains words that need to be
disambiguated in order to understand its meaning, but the full sentence does
not seem to be ambiguous. The key point of it is that it contains two words
"bear". The first one is a noun, and the second one is a verb. If we ask
ChatGPT the question itself, as seen in example 1 from Appendix A.2, the
sentence is correctly understood, since it is, apparently, not ambiguous.

Then, what happens if ChatGPT is explicitly asked if the previous sentence is
ambiguous? As seen in query 2, this output contains some interesting points.
In first place, ChatGPT does not find any ambiguity in the homonyms (both
"bear"s), but does see polysemy in one of them, the verb "to bear", which
makes the whole sentence ambiguous. This may be too excessive, since many
people would not label this sentence as ambiguous just because of those two
meanings of "to bear" (physically versus emotionally). This could be seen as
one of those cases that some people has previously pointed, where ChatGPT have
shown some overconfidence on its own answers.

As we focus on homonymy, we also ask the model about the homonyms words
themselves (query 3 from Appendix A.2). With that simple query ChatGPT fails
to detect both words. However, by just reformulating it, as in Query 4, the
question gets solved, proving the relevance of correct prompting, and the
model correctly detects homonymy. However, this case remarks the lack of
consistency of ChatGPT, that in this case does not detect the previous
polysemy of the verb "to bear".

The same results had been found on the remaining examples of homonymy
(sentences 2-11 from Appendix A.1). As the previous one, these sentences are
not intended to be ambiguous. For the list of ten sentences with a pair of
homonyms in each one of them, just three out of the ten are labelled as non-
ambiguous ("back", "can" y "band"). These false positive examples (queries
5-11 from Appendix A.2), which are relatively non-ambiguous for humans, allude
to the polysemy of one of the homonyms, as shown in those outputs.

In some occasions ChatGPT explanations look overconfident. Furthermore, in
those explanations there seems to be more confusion when both words share
Part-of-Speech tags ("bar", "right", "left"). In some other cases, confusion
among nouns and verbs ("address", "rose", "book") makes us even question
ChatGPT understanding of syntax, since those words cannot be replaced by their
homonym.

Eventually, ChatGPT wrongly labels as ambiguous some sentences and confidently
justifies a wrong explanation. Instead of a better ability detecting polysemy,
ChatGPT muddles through as best it can -as humans grasp at straws when they
struggle to find something that does not exist based keywords from the
instructions. It is also worth noting that detecting more polysemous words
than humans do is also problematic. If every word with more than on definition
is labelled as polysemous, then half of the English dictionary would be
polysemous.

Results improve when we explicitly ask: "What does every occurrence of the
word mean?". Outputs for sentences which are wrongly labelled as ambiguous due
to polysemy according to the first question, amend and correctly detect words
as homonyms according to this second question. However, there is one sentence
("bar") where both words are mistaken.

Then we build three simple and clearly ambiguous sentences with some of the
previous words (sentences 12-14 from Appendix A.1). We ask ChatGPT if these
sentences are ambiguous, and the model labels just two of them as ambiguous,
as seen in queries 12-14 from Appendix A.2.

In conclusion, prompting is a key element. Doing the right question can
achieve better results. Nonetheless, ChatGPT may show a wrong but convincing
and elaborated output due to its overconfidence -as incorrect results for
mathematical questions. Apparently ChatGPT tends to overdetect ambiguity, and
its better at detecting positive ambiguous examples than negative ones. Also,
ChatGPT brilliantly highlights the lack of context as the key element in a
future disambiguation for some detected ambiguities. This last detail seems to
indicate that the model has a default output assigned when it does not have
sufficient information to generate a reliable response.

####  5.1.2 Polysemy

In this case, we use a sample of 10 lemmas (Appendix B). For each one of them:

  * •

We input a non-ambiguous sentence and tried to label it as ambiguous or non-
ambiguous with the following prompt: Is the sentence "[sentence]" ambiguous?

  * •

Then we design a meaning classification task, where we input two
senses/definitions of the lemma and perform a classification task among those
senses in the previous sentence. The prompt model is: These are two
definitions of "[lemma]": [DEF1, DEF2]. Which of the definitions appear in the
sentence "[sentence]"?

  * •

Also, for each sentence we ask ChatGPT to guess the meaning of the polysemous
word, but without giving the definitions in the input, as in the second
experiment. The prompt model is: In the sentence "[sentence]" which is the
definition of "[lemma]"?

  * •

In fourth place we create a collection of clearly ambiguous sentences using
those lemmas, and try to label them as ambiguous or non-ambiguous with the
following prompt: Is the sentence "[sentence]" ambiguous?

  * •

Finally, in the last experiment we try to confuse ChatGPT using erroneous
pairs of lemma-definitions.

Appendix B.2 contains all the inputs and outputs from this section.

In the first experiment we want to test whether ChatGPT recognises the concept
of ambiguity, and whether it is able to detect it in simple sentences. The
result is that ChatGPT correctly detects non-ambiguity in all of the ten
sentences. Since a classification task must be done on them, all sentences are
suppose not to be ambiguous, so ChatGPT does a great job by not detecting
ambiguity.

For the second experiment we design a meaning classification task, where for
each of the ten lemmas we input two senses/definitions of each and one
sentence to perform a classification task among those senses. Definitions and
sentences come from Cambridge Dictionary666https://dictionary.cambridge.org/.
For instance, this is an example input for this second experiment: "These are
two definitions of "to serve": 1. to provide food or drinks 2. to work for; to
do your duty to. Which of the definitions appear in the sentence "She has
served on the committee for the last 15 years"?"

For this second test, ChatGPT correctly classifies nine out of ten sentences.
It only fails to classify the verb "to cheat", as seen in query 1 from
Appendix B.2. However, this can be solved with another better prompt in which
the definitions are removed (query 2 from Appendix B.2). In this case, less
context is better. In order to go further with this idea, in the third
experiment we check what happens if no definitions context is given. In the
other nine sentences, ChatGPT easily gives a correct definition for all the
nine polysemous words.

As it was done in the case of homonymy, it’s important to test clearly
ambiguous examples. Sentences like "I saw the mouse on the table" and "I saw
the mouse on the desktop" could have one predominant interpretation, but it is
not either 100% clear for humans. However, ChatGPT does not see any ambiguity,
and clearly associates the first one with the animal and the second one with
the electronic device. Given how easily the model previously detected
polysemy, it is shocking that it does not detect it here.

Same happens in the sentence "I spent the morning in the bank", where ChatGPT
clearly identifies the first definition. In our opinion, there is not enough
context and they should be flagged for ambiguity.

Following the idea of trying to improve prompting, if we ask ChatGPT if those
two sentences with the term "mouse" are ambiguous, it labels them as
ambiguous, and alludes to the need of more context in order to disambiguate.
One plausible cause for this could be the use of a prompt with the word
"ambiguous" but, again, a lack of determinism can be noted.

Another interesting experiment we have conducted is trying to confuse ChatGPT
using erroneous pairs of lemma-definitions. Following the previous prompt
model in which we input the two definition, what would happen if those are
wrong in some way? A first test is using wrong definitions of the lemma that
appears in the sentence, and there ChatGPT detects our trap (query 3 from
Appendix B.2). A second test is a sentence where wrong definitions of a lemma
that does not appear in the sentence are used, and were the definitions match
the lemma in the sentence. Here ChatGPT detects the trap again (query 4).
Lastly, every occurrence of the word is replaced, and ChatGPT gets a bit
confused, but brilliantly corrects the input again (query 5).

In conclusion, ChatGPT is remarkably good at classifying meaning of polysemous
words in non-ambiguous sentences, even when the definitions are not in the
context. In ambiguous sentences ChatGPT does not seem to perform as good as
for homonymy, but results improve with better prompting.

###  5.2 Syntactic Ambiguity

In this section we analyze the five sentences from Appendix C.1, and from each
one of them:

  * •

We ask ChatGPT about the ambiguity of the sentence with the following prompt:
Is the sentence "[sentence]" ambiguous?

  * •

In some cases, we ask ChatGPT how it interprets the sentence using the
following prompt: How do you interpret the sentence "[sentence]"?

  * •

In some cases, we ask ChatGPT about the ambiguous clause. The prompt model is:
In the sentence "[sentence]" is the clause "[clause]" ambiguous?

As in previous steps, in first place we empirically analyse a typical
sentence, and ask ChatGPT how it interprets it (query 1 in Appendix C.2). Here
ChatGPT does not see any ambiguity in this well-known ambiguous case. If we
ask if this is an ambiguous sentence, ChatGPT does not see the ambiguity
(query 2). A more precise question, as in query 3, where we ask about the
meaning of the ambiguous clause, neither works. If we insist (query 4), the
model even gets confused, and finds ambiguity in "saw", but not in our target,
again because of an too-easily detected polysemy. In the end (query 5 from
Appendix C.2) we partly achieved our goal by questioning the model previous
outputs.

But, how and when does ChatGPT learn? We do the same initial question about
ambiguity the same day but from another account, and ChatGPT fails again as it
did with our initial query. However, if we repeat the question after a week
and from a different account, then the model gets it right, as seen in query
6. It was not easy, but eventually ChatGPT recognized this typical example. It
seems that the model learns within an user session, and then after some days
that knowledge becomes general.

Does ChatGPT recognize other syntactically ambiguous examples? In the sentence
"I am happy you are proud, and so is Mary" the second clause can mean that
"Mary" is either happy or proud. In query 7 from Appendix C.2 we ask the model
how it interprets this sentence, and ChatGPT again does not see any ambiguity
in it. If the specifically ask if the sentence is ambiguous (query 8), ChatGPT
does not see any ambiguity. If we ask about that specific clause and its
ambiguity (query 9), the model neither detects ambiguity. Eventually, ChatGPT
amends when we insist (query 10). A better prompt and human feedback help on
this task. Also, when removing the comma before the clause (query 11), ChatGPT
suddenly detects ambiguity, even though the sentence becomes syntactically
wrong:

Then, what does happen with the "I watch her duck" example used by Jurafsky
and Martin (2020)? Here ChatGPT clearly detects the ambiguity (query 12), but
it only sees two out of five different interpretations that Jurafsky and
Martin (2020) explain for this sentence.

Additionally we tried some more examples. Is the sentence "They are cooking
apples"777https://mgmasoncreative.com/2014/08/15/syntactic-ambiguity-english-
language-at-its-funniest/ ambiguous? ChatGPT correctly identifies it in query
13.

| Ambiguity type | True Positive | True Negative | False Positive | False Negative
---|---|---|---|---|---
`` | Homonymy | 3 | 2 | 7 | 1
`` | Polysemy | 0 | 10 | 0 | 2
`` | Syntactic | 2 | 0 | 0 | 3
`` | Semantic | 1 | 2 | 0 | 0
Table 1: Ambiguity detection results

Another example is the sentence "I saw the dog with one
eye"888https://mgmasoncreative.com/2014/08/15/syntactic-ambiguity-english-
language-at-its-funniest/. As previously pointed in queries 8-11 with the
ambiguity between "happy" and "proud", ChatGPT encounters difficulties dealing
with syntactic ambiguity (query 14). However, we can insist until we push it
to learn about it (query 15).

Although it has been confusing at times, this analysis has allowed us to
explore syntactic ambiguity which has been the hardest to detect with ChatGPT,
but has pointed some key elements of how and when the model seems to learn,
and how (better prompting and human feedback) we can interact with it in order
to achieved better outputs and to make it learn.

ChatGPT has the potential to improve responses through human intervention
thanks to intents. We perceive how these intents may internally modify the
input sent to the model to optimise the actual prompt submitted. Thus allowing
new types of interactions and responses without having to constantly modify
the weights of the model.

###  5.3 Semantic Ambiguity

Although semantic ambiguity relates in literature with homonymy and polysemy,
in this section we will focus on co-reference resolution. The following
experiments have been done for every sentence from Appendix D.1:

  * •

We analyse the ambiguity of the sentence with the following prompt: Is the
sentence "[sentence]" ambiguous?

  * •

We explore other specific prompts to analyse the reference of the ambiguous
pronouns.

In first place we ask the model if the sentence "My mother and my sister were
sad after she shouted at her" is ambiguous. As seen in query 1 from Appendix
D.2, The explanation is great and fully captures the logic behind co-reference
resolution. Then, if we go further and ask "who shouted at who?", ChatGPT
again detects the ambiguity of the pronouns "she" and "her" (query 2).

Another specific case of co-reference is gender disambiguation. Here ambiguity
can be useful to explore stereotypical gender bias (Blodgett et al., 2020) in
language models. In the example sentences proposed by Zhao et al. (2018) "The
physicist hired the secretary because he was overwhelmed with work." and "The
physicist hired the secretary because she was overwhelmed with work.", systems
must be able to make correct linking predictions in pro-stereotypical
scenarios (…) and anti-stereotypical scenarios" (Zhao et al., 2018). These
pro-stereotypical and anti-stereotypical scenarios came from data from US
Department of Labor statistics.

We ask the model if they are ambiguous (queries 3 and 4). ChatGPT correctly
labels them as non-ambiguous. Then we ask about the gender of both people in
each sentence, because this must be determined by the pronoun of the
subordinate sentence, and not by statistical stereotypes. This means that even
if traditionally a gender is more prone to a given job, in these sentence the
pronoun makes this sentence non-ambiguous, so there is no need to draw upon
that "statistical knowledge". Grammar should be above that. But this does not
happen, and ChatGPT wrongly interprets it in query 5 from Appendix D.3.

This means that even in a situation where there is no ambiguity, ChatGPT puts
gender bias over grammar. This could naively mean that ChatGPT is
misunderstanding grammar, but, as expected, if we change the gender of the
pronouns, ChatGPT suddenly does not fail, as seen in query 6.

In conclusion, in the semantic field ChatGPT does some amazing job detecting
ambiguous pronouns in co-reference resolution situations, but disappointingly
fails putting gender bias over grammar in situations where this grammar makes
a sentence non-ambiguous.

###  5.4 Generation

A good approach to understand ChatGPT conception of ambiguity could be asking
to generate an ambiguous sentence. To achieve this, the prompt Generate an
ambiguous sentence (Appendix E.1) is used. After generation, the question if
the model consider its own sentence ambiguous came up. Surprisingly, it does
not look that way to ChatGPT now, and as seen in query 2, the sentence is
labelled as not inherently ambiguous. This could be seen as the main issue
with ChatGPT: its lack of consistence, that could be related with a volatile
and questionable self-confidence.

###  5.5 Results

Table 1 contains the results of the ambiguity detection queries. In our data
samples ChatGPT achieves an accuracy of 0.6061 and an F1 of 0.48.

For the case of ambiguity detection in sentences with homonyms, False
Positives represents the higher amount, although this was due to the detection
of polysemy in some of the homonyms, and ChatGPT did well apart from that. In
the case of polysemy ChatGPT correctly detected all negative examples, but
failed to detect the positive ones. The model did well when classifying
definitions with or without context, and also performed great with erroneous
queries.

Syntactic ambiguity appears to be harder to detect, but in the end, with the
help of good prompting and reinforcement learning, ChatGPT did well at
detection of disambiguation. In semantics, ChatGPT performed perfectly in the
detection of ambiguities. Apart from that, it has some bright sports (co-
reference resolution) and some weaknesses (puts gender bias over grammar in
some non-ambiguous situations). In the generation task ChatGPT did well, but
also revealed some of its worse issues: the lack of systematicity. Lastly, it
should also be pointed that in most of the cases ChatGPT brilliantly alludes
to lack of context as the key factor in disambiguation.

##  6 Conclusions

Transformer-based LLMs have achieved enormous advances in NLP, where
disambiguation has always been one of the main problems. Models like ChatGPT
continue to improve these issues, but there is still plenty of work to do.

We have provided an introduction to linguistic ambiguity, its varieties and
their relevance in NLP, and performed an extend empiric analysis of how
ChatGPT treats them. This analysis revealed some of the model strengths and
weaknesses. We also provide the data used in the experiments, and most of the
model outputs as well.

We consider this a promising starting point towards the use of ChatGPT and
generative models in disambiguation tasks. Probably by the moment this paper
is read some of the flaws of the model have improved and we have to move on to
another defects.

##  7 Limitations

It should be noted that this work is an empiric analysis. We understand that
the main limitation of our work is that ChatGPT is a living model that evolves
in time, eager to keep on learning and able to track a conversation (not only
a prompt). Therefore, some of the data used here and the results produced with
them may vary in the future as the model evolves. It should also be pointed
that this is not an open-source model that in some occasions suffers from
overload. Furthermore, it is relevant to note that experiments have been
carried out for a high-resource language like English, so the results may be
different for languages with other linguistic features or fewer resources.

##  8 Ethics statement

We are aware of the possibilities that models like ChatGPT can imply for both
industry and academic research in the future. Our intention here is to
contribute to a better understanding and development of NLP in general and
this model in particular, in order to improve its performance, but always
promoting a responsible use.

## References

  * Bano (2015) Muneera Bano. 2015.  Addressing the challenges of requirements ambiguity: A review of empirical literature.  In _2015 IEEE Fifth International Workshop on Empirical Requirements Engineering (EmpiRE)_ , pages 21–24. IEEE.
  * Blodgett et al. (2020) Su Lin Blodgett, Solon Barocas, Hal Daumé III, and Hanna Wallach. 2020.  Language (technology) is power: A critical survey of" bias" in nlp.  _arXiv preprint arXiv:2005.14050_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D. Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, and Amanda Askell. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Jurafsky and Martin (2020) Dan Jurafsky and James H. Martin. 2020.  _Speech and language processing (3rd draft ed.)_.  Stanford Univ.
  * Jusoh (2018) Shaidah Jusoh. 2018.  A study on NLP appliactions and ambiguity problems.  _Journal of Theoretical & Applied Information Technology_, 96(6).  ISBN: 1992-8645.
  * Liu et al. (2020) Qi Liu, Matt J Kusner, and Phil Blunsom. 2020.  A survey on contextual embeddings.  _arXiv preprint arXiv:2003.07278_.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, and Alex Ray. 2022.  Training language models to follow instructions with human feedback.  _arXiv preprint arXiv:2203.02155_.
  * Srivastava et al. (2022) Aarohi Srivastava et al. 2022.  Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models.  ArXiv:2206.04615 [cs, stat].
  * Xie et al. (2021) Huiqiang Xie, Zhijin Qin, Geoffrey Ye Li, and Biing-Hwang Juang. 2021.  Deep learning enabled semantic communication systems.  _IEEE Transactions on Signal Processing_ , 69:2663–2675.
  * Zhao et al. (2018) Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang. 2018\.  Gender bias in coreference resolution: Evaluation and debiasing methods.  _arXiv preprint arXiv:1804.06876_.

##  Appendix A Homonymy

###  A.1 SENTENCES

  1. 1.

How does a bear bear with the pain?

  2. 2.

The man bought a chocolate bar at the bar.

  3. 3.

Going to the right is the right choice.

  4. 4.

There is not choice left but going to the left.

  5. 5.

The pain in my back came back after a hard day of work.

  6. 6.

The band singer was wearing a head band during concert.

  7. 7.

You should address the problem with your address.

  8. 8.

Rose sale rose during February.

  9. 9.

Did you watch the watch my mom gave my for Christmas?

  10. 10.

Please, can you close the trash can?

  11. 11.

I will book the book presentation for tomorrow.

  12. 12.

I bought a bar

  13. 13.

You look right

  14. 14.

I saw a band

###  A.2 QUERIES

  1. 1.

INPUT: How does a bear bear with the pain?

OUTPUT: Bears are able to bear with pain in much the same way as humans do -
through a combination of natural defenses and behaviors…

  2. 2.

INPUT: Is the sentence "How does a bear bear with the pain?" ambiguous?

OUTPUT: Yes, the sentence "How does a bear bear with the pain?" is ambiguous
because it can be interpreted in two different ways. One interpretation is
asking about the physical process by which a bear copes with pain, while the
other interpretation is asking about the emotional process by which a bear
tolerates or endures pain. Without additional context or clarification, it is
difficult to determine which interpretation is intended. It would be helpful
to provide more information or to rephrase the sentence to make the intended
meaning clearer."

  3. 3.

INPUT: what does "bear" mean in the sentence "How does a bear bear with the
pain?"?

OUTPUT: In the sentence "How does a bear bear with the pain?", the word "bear"
is being used as a verb. It means to tolerate or endure something difficult or
unpleasant, such as pain. The sentence is asking how a bear is able to cope
with or withstand the pain it is experiencing.

  4. 4.

INPUT: "In the sentence "How does a bear bear with the pain?", what does every
word "bear" mean?"

OUTPUT: In the sentence "How does a bear bear with the pain?" there are two
instances of the word "bear". The first instance of the word "bear" is a noun
that refers to a large, carnivorous mammal that is native to the northern
regions of North America, Europe, and Asia. The second instance of the word
"bear" is a verb that means to tolerate or endure something, often something
unpleasant or difficult. So, in this sentence, the first instance of the word
"bear" refers to the animal, and the second instance of the word "bear" refers
to the action of tolerating or enduring something.

  5. 5.

INPUT: Is the sentence "The man bought a chocolate bar at the bar" ambiguous?

OUTPUT: Yes, the sentence "The man bought a chocolate bar at the bar" is
ambiguous because it is unclear which "bar" is being referred to. It could be
interpreted to mean that the man bought a chocolate bar at a place where
alcohol is served (a bar), or it could mean that the man bought a chocolate
bar that is shaped like a bar.

  6. 6.

INPUT: Is the sentence "Going to the right is the right choice." ambiguous?

OUTPUT: Yes, the sentence "Going to the right is the right choice." is
ambiguous. It is unclear whether the speaker is saying that physically going
to the right direction is the correct choice, or if the speaker is saying that
making the right decision (in general) is the correct choice.

  7. 7.

INPUT: Is the sentence "There is not choice left but going to the left."
ambiguous?

OUTPUT: Yes, the sentence "There is not choice left but going to the left." is
ambiguous because it is unclear if the speaker is saying that there is no
other choice but to go to the left or if the speaker is saying that there is
no choice at all and that the person must go to the left. The sentence could
be clarified by adding more context or rephrasing it.

  8. 8.

INPUT: Is the sentence "You should address the problem with your address."
ambiguous?

OUTPUT: Yes, the sentence "You should address the problem with your address."
is ambiguous because it is not clear whether "address" refers to speaking
about or addressing something, or the physical location where someone lives.

  9. 9.

INPUT: Is the sentence "rose sale rose during February" ambiguous?

OUTPUT: Yes, the sentence "Yes, the sentence "rose sale rose during February"
is ambiguous. It is unclear whether the verb "rose" is referring to the sale
of roses increasing or the sale of a specific rose product increasing.

  10. 10.

INPUT: Is the sentence "Did you watch the watch my mom gave my for Christmas?"
ambiguous?

OUTPUT: Yes, the sentence "Did you watch the watch my mom gave my for
Christmas?" is ambiguous. It is unclear if the speaker is asking if the
listener watched the watch as in looking at the time or if they watched the
watch as in observing it.

  11. 11.

INPUT: Is the sentence "I will book the book presentation for tomorrow."
ambiguous?

OUTPUT: Yes, the sentence "I will book the book presentation for tomorrow." is
ambiguous. It is unclear whether the speaker is referring to a presentation
about a book or a presentation of a book.

  12. 12.

INPUT: Is the sentence "I bought a bar" ambiguous?

OUTPUT: The sentence "I bought a bar" is ambiguous and could mean a few
different things. It could mean that the speaker purchased a establishment
that serves alcohol, or it could mean that the speaker purchased a solid
rectangular piece of metal or other material that is used for support or as a
barrier, or it could mean that the speaker purchased a unit of measurement of
pressure. Without more context, it is difficult to determine the intended
meaning.

  13. 13.

INPUT: Is the sentence "You look right" ambiguous?

OUTPUT: Yes, the sentence "You look right" is ambiguous as it could have
multiple interpretations depending on context. It could mean that the person
looks correct or appropriate, or it could mean that the person is facing the
right direction.

  14. 14.

INPUT: Is the sentence "I saw a band" ambiguous?

OUTPUT: No, the sentence "I saw a band" is not ambiguous. It clearly states
that the speaker saw a group of musicians or performers, commonly referred to
as a band.

##  Appendix B Polysemy

###  B.1 LEMMAS: SENTENCES

  1. 1.

to serve: She has served on the committee for the last 15 years

  2. 2.

pretty: The house has four bedrooms, so it’s pretty big.

  3. 3.

truck: The road was completely blocked by an overturned truck

  4. 4.

orange: a glass of orange juice

  5. 5.

to cheat: She found out that he’d been cheating on her

  6. 6.

beam: A laser beam scans the disc’s surface

  7. 7.

mouse: Once you get the feel of it, using a mouse is easy.

  8. 8.

to run: He’s been running a restaurant since he left school

  9. 9.

date: He asked her out on a date.

  10. 10.

bank: By the time we reached the opposite bank, the boat was sinking fast

###  B.2 QUERIES

  1. 1.

INPUT: These are two definitions of "to cheat": 1. to behave in a dishonest
way in order to get what you want 2. to have a secret sexual relationship with
someone who is not your husband, wife, or usual sexual partner. Which of the
definitions appear in the sentence "She found out that he’d been cheating on
her"?

OUTPUT: The first definition, "to behave in a dishonest way in order to get
what you want," applies in the sentence "She found out that he’d been cheating
on her."

  2. 2.

INPUT: In the sentence "She found out that he’d been cheating on her" which is
the definition of "cheating"?

OUTPUT: "In this sentence, "cheating" means that the person was being
unfaithful to their partner by engaging in a romantic or sexual relationship
with someone other than their partner. It typically implies a breach of trust
or commitment in a romantic relationship."

  3. 3.

INPUT: These are two definitions of "truck": 1. an organization where people
and businesses can invest or borrow money, change it to foreign money, etc.,
or a building where these services are offered 2.sloping raised land,
especially along the sides of a river . Which of the definitions appear in the
sentence "I was hit by a truck"?"

OUTPUT: In the sentence "I was hit by a truck," the word "truck" refers to a
vehicle with four wheels and a large, rectangular body that is used for
transporting goods or materials. This definition is commonly used in everyday
language and refers to a type of motor vehicle. It does not refer to either of
the definitions you provided, which are unrelated to vehicles."

  4. 4.

INPUT: These are two definitions of "truck": 1. an organization where people
and businesses can invest or borrow money, change it to foreign money, etc.,
or a building where these services are offered 2.sloping raised land,
especially along the sides of a river . Which of the definitions appear in the
sentence "I was in the bank this morning"?"

OUTPUT: The first definition of "truck" (an organization where people and
businesses can invest or borrow money, change it to foreign money, etc., or a
building where these services are offered) appears in the sentence "I was in
the bank this morning." The second definition of "truck" (sloping raised land,
especially along the sides of a river) does not appear in the sentence. ,

  5. 5.

INPUT: "These are two definitions of "university": 1. an organization where
people and businesses can invest or borrow money, change it to foreign money,
etc., or a building where these services are offered 2.sloping raised land,
especially along the sides of a river . Which of the definitions appear in the
sentence "I was in the university this morning"?

OUTPUT: The second definition of "university" does not match the context of
the sentence "I was in the university this morning." In this sentence, the
word "university" is most likely being used to refer to an institution of
higher education, where students can earn degrees and conduct research. The
first definition you provided, "an organization where people and businesses
can invest or borrow money, change it to foreign money, etc., or a building
where these services are offered," does not match the context of the sentence.

##  Appendix C Syntactic ambiguity

###  C.1 SENTENCES

  1. 1.

Mary saw John with a telescope

  2. 2.

I am happy your are proud, and so is mom

  3. 3.

I watch her duck

  4. 4.

I saw the dog with one eye

  5. 5.

They are cooking apples

###  C.2 QUERIES

  1. 1.

INPUT: How do you interpret the sentence "Mary saw John with a telescope"?

OUTPUT: "To interpret the sentence "Mary saw John with a telescope" it means
that Mary used a telescope to see John. The sentence could be rephrased as
"Mary used a telescope to see John." It implies that Mary was able to see John
from a distance using the telescope, possibly because he was too far away to
be seen with the naked eye. The sentence does not specify the context or the
reason why Mary saw John with a telescope, so it is not possible to provide
further information without more context.

  2. 2.

INPUT: Is the sentence "Mary saw John with a telescope" ambiguous?

OUTPUT: No, the sentence "Mary saw John with a telescope" is not ambiguous.
The sentence means that Mary used a telescope to see John. It is not unclear
or open to multiple interpretations.

  3. 3.

INPUT: What does "with a telescope" mean in that sentence?

OUTPUT: "In the sentence "Mary saw John with a telescope," the phrase "with a
telescope" means that Mary used a telescope to see John. It indicates that the
telescope was the means or instrument through which Mary saw John."

  4. 4.

INPUT: In the sentence "Mary saw John with a telescope" is "with a telescope"
ambiguous?

OUTPUT: In the sentence "Mary saw John with a telescope," the phrase "with a
telescope" is not ambiguous. It indicates that Mary saw John using a
telescope, or looking through a telescope. The phrase "with a telescope" is
not open to multiple interpretations, and it is clear that Mary was using a
telescope to see John. If there were any ambiguity in the sentence, it might
be about the meaning of "saw" – it could mean that Mary literally saw John
with her own eyes, or it could mean that Mary learned about John’s presence or
location through some other means…

  5. 5.

INPUT: isn’t then "with a telescope" ambiguous?

OUTPUT: It is possible that the phrase "with a telescope" could be ambiguous
in some contexts, depending on the intended meaning of the sentence and the
specific words used. For example, if the sentence was "John saw Mary with a
telescope," the phrase "with a telescope" could potentially be ambiguous,
because it could mean either that John saw Mary through a telescope, or that
John saw Mary while holding or using a telescope. In this case, the phrase
"with a telescope" could be open to multiple interpretations. However, in the
original sentence "Mary saw John with a telescope," the phrase "with a
telescope" is not ambiguous. It clearly indicates that Mary saw John while
looking through a telescope, or while using a telescope to see John. In this
context, there is no room for multiple interpretations of the phrase "with a
telescope." The sentence is clear and unambiguous. ,

  6. 6.

INPUT: Is the sentence "Mary saw John with a telescope" ambiguous?

OUTPUT: It is not necessarily ambiguous. The sentence "Mary saw John with a
telescope" could be interpreted to mean that Mary saw John while using a
telescope to observe him from a distance. It could also be interpreted to mean
that Mary saw John while holding a telescope, but this would depend on the
context in which the sentence is used. If there is no context or further
information provided, the sentence could be ambiguous.

  7. 7.

INPUT: How do you interpret the sentence "I am happy you are proud, and so is
Mary"?

OUTPUT: The sentence "I am happy you are proud, and so is Mary" can be
interpreted to mean that the speaker is pleased that the person they are
addressing is proud, and that Mary also shares this sentiment. The phrase "I
am happy" suggests that the speaker is feeling positive or pleased about
something, and the phrase "you are proud" suggests that the person they are
addressing has a sense of pride or accomplishment. The phrase "so is Mary"
indicates that Mary also feels the same way as the speaker. This sentence
could be seen as expressing support or appreciation for the person’s
accomplishments or pride.

  8. 8.

INPUT: Is the sentence "I am happy you are proud, and so is Mary" ambiguous?

OUTPUT: The sentence "I am happy you are proud, and so is Mary" is not
ambiguous. It clearly conveys that the speaker is happy that the person they
are speaking to is proud, and that Mary is also happy. The sentence uses the
conjunction "and" to connect the two clauses, which indicates that they are
closely related and that the second clause provides additional information
about the first clause. There is no ambiguity or uncertainty in the meaning of
the sentence.

  9. 9.

INPUT: In the sentence "I am happy you are proud, and so is Mary" is the
clause "and so is Mary" ambiguous?

OUTPUT: The phrase "and so is Mary" in the sentence "I am happy you are proud,
and so is Mary" is not ambiguous. It clearly conveys that Mary is happy, just
as the speaker is happy. The phrase "and so is Mary" is used to provide
additional information about the speaker’s happiness, and there is no
uncertainty or ambiguity in its meaning. It is important to consider the
context in which the sentence is being used, as this can help to clarify the
meaning of the sentence and any potentially ambiguous phrases or clauses. In
this case, the sentence is fairly straightforward and there is no need to rely
on additional context to understand its meaning.

  10. 10.

INPUT: Don’t you see that "and so is Mary" could mean that she is proud
instead of happy?

OUTPUT: It is possible that the phrase "and so is Mary" could be interpreted
as meaning that Mary is proud, rather than happy, depending on the context in
which the sentence is used. However, in the sentence "I am happy you are
proud, and so is Mary", the most natural and straightforward interpretation of
the phrase is that it means Mary is happy, not proud. The word "so" is often
used to indicate that something is the case in the same way as something else.
In this case, the speaker is happy that the person they are speaking to is
proud, and the phrase "and so is Mary" indicates that Mary is also happy in
the same way. This is the most logical and straightforward interpretation of
the phrase, and it is unlikely that it would be interpreted as meaning that
Mary is proud unless there was some other context that suggested this
interpretation. It is always important to consider the context in which a
sentence is used, as this can help to clarify the meaning of potentially
ambiguous phrases or clauses. In this case, the context of the sentence makes
it clear that the phrase "and so is Mary" means that Mary is happy, rather
than proud.

  11. 11.

INPUT: Is the sentence "I am happy you are proud and so is Mary" ambiguous?

OUTPUT: Yes, the sentence "I am happy you are proud and so is Mary" is
potentially ambiguous. Without further context, it is unclear whether the
speaker is happy that the listener is proud, or whether the speaker is happy
for some other reason and is simply stating that Mary is also happy. To make
the meaning of the sentence clearer, it would be helpful to provide more
context or to rephrase the sentence. For example, you could say "I am happy
because you are proud" or "Mary and I are both happy that you are proud."

  12. 12.

INPUT: Is the sentence "I watched her duck" ambiguous?

OUTPUT: The sentence "I watch her duck" could be ambiguous because it could be
interpreted in two different ways: "I watch her duck" - In this
interpretation, "duck" is being used as a verb, meaning to lower one’s head or
body quickly to avoid something, such as a thrown object or a punch. In this
case, the sentence would mean that the speaker is watching the other person
duck to avoid something. "I watch her duck" - In this interpretation, "duck"
is being used as a noun, meaning a waterbird with a broad blunt bill, short
legs, and webbed feet. In this case, the sentence would mean that the speaker
is watching the other person, who is a duck. Without further context, it is
difficult to determine which interpretation is intended.

  13. 13.

INPUT: Is the sentence "They are cooking apples" ambiguous?

OUTPUT: Yes, the sentence "They are cooking apples" is ambiguous because it is
not clear what "they" refers to and it is not specified whether the apples are
being used for cooking or if they are a type of apple that is good for
cooking.

  14. 14.

INPUT: Is the the sentence "I saw the dog with one eye" ambiguous?

OUTPUT: The sentence "I saw the dog with one eye" is not ambiguous. It means
that you saw a dog that had only one eye. It is not unclear or uncertain what
is being referred to in the sentence.

  15. 15.

INPUT: How do you interpret the sentence "I saw the dog with one eye"

OUTPUT: The sentence "I saw the dog with one eye" could potentially be
ambiguous, as it could be interpreted in two different ways: The dog has only
one eye: In this interpretation, the sentence means that the speaker saw a dog
that has only one eye, either due to injury or birth defect. The speaker saw
the dog using only one eye: In this interpretation, the sentence means that
the speaker saw the dog while using only one eye, perhaps because they were
covering or closing the other eye. Without additional context, it is not clear
which interpretation is intended. However, if the speaker provides more
information or clarifies their intended meaning, the ambiguity can be
resolved.

##  Appendix D Semantic ambiguity

###  D.1 SENTENCES

  1. 1.

My mother and my sister were sad after she shouted at her

  2. 2.

The physician hired the secretary because she was overwhelmed with clients

  3. 3.

The physician hired the secretary because he was overwhelmed with clients

###  D.2 QUERIES

  1. 1.

INPUT: Is the sentence "My mother and my sister were sad after she shouted at
her" ambiguous?

OUTPUT: Yes, the sentence "My mother and my sister were sad after she shouted
at her" is ambiguous. Without more context, it is unclear which person is
being referred to as "she" and who was shouted at by "her." It could be
interpreted in two different ways: My mother was sad after she (my mother)
shouted at her (my sister). My sister was sad after she (my sister) shouted at
her (my mother). To make the meaning clear, it would be helpful to add more
context or to rephrase the sentence to specify which person is being referred
to as "she" and who was shouted at by "her." For example: "After my mother
shouted at my sister, both of them were sad." "After my sister shouted at my
mother, both of them were sad."

  2. 2.

INPUT: In the sentence "My mother and my sister were sad after she shouted at
her", who shouted at who?

OUTPUT: In the sentence "My mother and my sister were sad after she shouted at
her," it is not clear who shouted at whom. The pronoun "she" could refer to
either the speaker’s mother or sister, and the pronoun "her" could refer to
either the person who was shouted at or the person doing the shouting. It is
also possible that the pronoun "she" refers to a third person who is not
mentioned in the sentence. Without more context, it is not possible to
accurately determine who shouted at whom."

  3. 3.

INPUT: Is the sentence ""The physicist hired the secretary because she was
overwhelmed with work." ambiguous?

OUTPUT: No, the sentence is not ambiguous. It is clear that the physicist
hired the secretary to help with the work that the physicist was overwhelmed
with.

  4. 4.

INPUT: Is the sentence ""The physicist hired the secretary because he was
overwhelmed with work." ambiguous?

OUTPUT: No, the sentence is not ambiguous. It clearly states that the
physicist hired the secretary because he was overwhelmed with work.

  5. 5.

INPUT: In the sentence "The physicist hired the secretary because she was
overwhelmed with work", who the pronoun "she" refers to?

OUTPUT: The pronoun "she" refers to the secretary..

  6. 6.

INPUT: In the sentence "The physicist hired the secretary because she was
overwhelmed with work.", who the pronoun "he" refers to?", who the pronoun
"she" refers to?

OUTPUT: The pronoun "he" refers to the physicist.

##  Appendix E Generation

###  E.1 QUERIES

  1. 1.

INPUT: Generate an ambiguous sentence

OUTPUT: Sure! Here is an ambiguous sentence: "The chicken is ready to eat."
This sentence could be interpreted in two different ways: The chicken has been
cooked and is now ready to be eaten. The chicken is so hungry that it is ready
to eat something else. Ambiguous sentences can be confusing because they can
have multiple meanings, and it’s not always clear which interpretation is
intended.

  2. 2.

INPUT: Is the sentence "The chicken is ready to eat." ambiguous?

OUTPUT: The sentence "The chicken is ready to eat." is not inherently
ambiguous. It is a simple statement that the chicken is prepared and ready to
be consumed as food. However, the sentence could potentially be ambiguous
depending on the context in which it is used. For example, if the sentence is
used in a conversation about a chicken that is being cooked, it might be
interpreted to mean that the chicken has finished cooking and is now ready to
be eaten. However, if the sentence is used in a different context, such as a
conversation about a live chicken that is being kept as a pet, it could
potentially be interpreted as meaning that the chicken is being offered as
food to be eaten by someone or something else. Overall, the potential for
ambiguity in the sentence "The chicken is ready to eat." would depend on the
context in which it is used and the knowledge and assumptions of the person or
people listening or reading the sentence.


# Transaction Placement in Sharded Blockchains
††thanks: This research is supported in part by a Ripple Graduate Fellowship.

1st Liuyang Ren  University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>2nd Paul A. S. Ward  University of Waterloo
Waterloo, Canada
<EMAIL_ADDRESS>
###### Abstract

While many researchers adopt a sharding approach to design scaling
blockchains, few works have studied the transaction placement problem incurred
by sharding protocols. The widely-used hashing placement algorithm renders an
overwhelming portion of transactions as cross-shard. In this paper, we analyze
the high cost of cross-shard transactions and reveal that most Bitcoin
transactions have simple dependencies and can become single-shard under a
placement algorithm taking transaction dependencies into account. In addition,
we perform a case study of OptChain, which is the state-of-the-art transaction
placement algorithm for sharded blockchains, and find a shortcoming of it. A
simple fix is proposed, and our evaluation results demonstrate that the
proposed fix effectively helps OptChain overcome the shortcoming and
significantly improve the system performance under a special workload. The
authors of OptChain made some revisions to the algorithm description after
noticing our work. Their updated algorithm does not exhibit the shortcoming
under the workloads employed by this paper.

###### Index Terms:

blockchain, sharding, transaction dependencies, transaction placement

##  I Introduction

Conventional blockchain systems suffer from low performance due to the PoW
consensus protocol, which requires all nodes to duplicate the works from each
other. To improve the performance, various designs have been proposed—e.g.,
shortening block intervals [1], incorporating off-chain blocks [2][3],
allowing one miner to consecutively propose multiple blocks [4], sharding
[5][6][7][8], journaling aggregated transaction effects to blockchains [9]
[10], etc. Among these techniques, sharding is a promising approach and has
been explored by many researchers. The high-level idea of sharding is to
partition a system into multiple shards and distribute its workloads to
different shards for parallel processing so that the system performance scales
with the number of nodes. However, because each shard usually stores a
disjoint subset of the system state [6][7][8], transactions modifying more
than one such subsets would inevitably incur cross-shard communication.
Specifically, such cross-shard transactions rely on Atomic Commit Protocols
(ACPs) to guarantee state consistency between shards. In addition to network
bandwidth consumption, ACPs also put extra computational burdens on the
involved shards, especially in trustless environments (i.e., public
blockchains), where expensive digital signatures are employed to prove message
authenticity.

While many previous works focus on blockchain sharding protocols, few
researchers have paid attention to transaction placement, which is about
selecting a shard to process a given transaction. Transaction placement
algorithms have a major impact on the number of cross-shard transactions and
consequently the system performance. The transaction placement algorithm used
by most, if not all, sharding protocols is the Hashing Placement (HP) [5]. HP
places transactions to shards based on the prefix matching of transaction IDs
and shard IDs. Because transaction IDs are hash values (e.g., SHA256 values in
Bitcoin), and hash values are uniformly distributed over the output range of
the corresponding hash function [11], HP is equivalent to placing transactions
randomly. As a result, HP produces a considerable number of cross-shard
transactions. Fig. 1 illustrates the placement outcome for the 1.57 million
non-coinbase111Coinbase transactions have no input UTXOs and credit newly
“minted” UTXOs to miners. Non-coinbase transactions spend existing UTXOs.
transactions in the first 150k Bitcoin blocks. When the system involves more
than 32 shards, almost all non-coinbase transactions are cross-shard.

Figure 1: A high percentage of transactions are cross-shard under the hashing
placement algorithm.

This work has three contributions: 1) revealing that the overwhelming majority
of Bitcoin transactions have only one parent transaction; 2) identifying the
root cause of the high cost of cross-shard transactions; and 3) identifying a
shortcoming in OptChain [12], a state-of-the-art blockchain transaction
placement algorithm, and proposing an effective fix.

##  II Background

A blockchain is an ordered set of blocks, each of which contains an ordered
set of transactions. Every node maintains a local copy of the whole
blockchain, executes the transactions in the order specified by the
blockchain, and thus ends up with the same system state as other nodes.

###  II-A Unspent Transaction Output (UTXO) Model

Unlike conventional banking systems, cryptocurrencies like Bitcoin use a UTXO
model to express their system states instead of the account-balance model.
Accordingly, a transaction spends input UTXOs and generates output UTXOs.
Figure 2 demonstrates the transaction execution in Bitcoin. Bob sends 1.5 BTC
to Alice by creating a transaction that spends his 2-BTC UTXO and generates a
1.5-BTC UTXO for Alice as well as a 0.5-BTC UTXO for himself. Once the
transaction gets executed, the 2-BTC UTXO (i.e., _UTXO B_ in Fig. 2) does not
exist anymore. All transactions have at least one input UTXO, except for
coinbase transactions, which spend nothing and credit output UTXOs to miners.

Figure 2: Transaction execution

The transaction placement problem in a UTXO-based system is to find a shard to
process a transaction and store the output UTXOs of the transaction. This
shard is called the _output shard_ of this transaction. Similarly, a shard
storing at least one input UTXO of this transaction is called an input shard.

###  II-B Blockchain Sharding Protocols

In this section, we focus on describing the sharding protocol OmniLedger [6]
and briefly introduce other sharding protocols because OmniLedger is used by
OptChain for evaluation.

(a) A cross-shard transaction

(b) Lock-success scenario in Atomix

Figure 3: An example of OmniLedger’s Atomix protocol

Blockchain sharding protocols divide nodes into shards that process
transactions in parallel. OmniLedger shards maintain their own respective
ledgers. Every shard produces blocks extending from its individual ledger, and
the blockchain is the union of the ledgers of all shards. Shard members are
selected using Proof-of-Work (PoW) to protect the system from Sybil attacks
and periodically reconfigured so that attackers cannot corrupt a shard by
attacking a small and fixed group of nodes. Within a shard, nodes run the
Practical Byzantine Fault Tolerance (PBFT) protocol [13] to agree on the
validity and the execution order of transactions.

Cross-shard transactions rely on atomic commit protocols (ACPs) to be either
unanimously committed or unanimously aborted. The problem of guaranteeing
transaction atomicity dates back to the late 1970s [14][15]. Among various
ACPs, the two-phase commit protocol (2PC) [14] is the most widely used one in
the industry and academia [16][17]. OmniLedger has proposed a similar protocol
called _Atomix_ for atomically processing transactions across shards. The
basic idea of Atomix is shown in Fig. 3. The client requests the input shards
to lock the input UTXOs of its cross-shard transaction, and the input shards
reply with signed lock results. If all input shards reply with positive lock
results, the client then sends the output shard a COMMIT request along with
signatures from the input shards as proofs of successful locking. The output
shard adds the output UTXO to its system state, provided all signatures of the
input shards are valid. If any input shard cannot lock an input UTXO, it
informs the client about the failure with a signed message, and the client
will use the message as a proof to request other input shards to unlock their
respective input UTXOs. In blockchain environments, it is challenging to find
an ACP coordinator, whose misbehavior may lead to forever-locked UTXOs.
OmniLedger chooses clients as the coordinators of their own transactions so
that coordinators are incentivized to conform to the ACP protocol.

Like OmniLedger, Elastico [5] and AHL [8] also employ PBFT as their intra-
shard consensus protocol. RapidChain [7], on the other hand, uses a variant of
the synchronous consensus protocol proposed by Ren et al. [18] to tolerate the
same number of faulty nodes with a smaller shard size than PBFT. In terms of
ACPs, Dang et al. [8] incorporates 2PC and leverages an entire Byzantine
fault-tolerant committee as the coordinator. RapidChain [47] processes a
cross-shard transaction by splitting it into multiple sub-transactions, each
of which spends UTXOs belonging to the same shard (i.e., every sub-transaction
has only one input shard). Elastico is fundamentally different from other
sharding protocols in that it does not partition system states despite the
fact that transactions are partitioned. In other words, every Elastico node
still maintains the whole system state (i.e., all UTXOs). As a result, there
are no cross-shard transactions in Elastico. Table I summarizes these sharding
protocols.

Table I: Comparison of Various Blockchain Shading Protocols Protocol |  Intra-shard Consensus |  ACP |  ACP Coordinator |  Transaction Placement
---|---|---|---|---
Elastico |  PBFT |  N/A |  N/A |  Hashing placement
OmniLedger |  PBFT |  Atomix [6] |  Client |  Hashing placement
RapidChain |  Practical synchronous byzantine consensus [18] |  Transaction Splitting [7] |  PBFT leader of output shard |  Hashing placement
AHL |  PBFT |  2PC |  Dedicated BFT committee |  Hashing placement

##  III Transaction Characteristics

Understanding transaction characteristics allows us to determine whether
carefully placing transactions to shards can achieve substantial performance
improvement. We are particularly interested in two characteristics: 1) how
many transactions can be easily turned into single-shard transactions, and 2)
how expensive a cross-shard transaction is when compared with a single-shard
transaction. A transaction placement algorithm can only benefit the system
performance if cross-shard transactions cost a lot more than their single-
shard counterparts and can be greatly reduced by the algorithm.

###  III-A Transaction Dependencies

If transaction $tx2$ spends the UTXO(s) produced by transaction $tx1$, then
$tx1$ is called the parent transaction and $tx2$ is the child transaction.
Given a transaction, the number of its parent transactions directly affects
its probability of being single-shard. For example, a transaction with only
one parent can be a single-shard transaction if it is placed to the same shard
as its parent. In contrast, a transaction with 100 parents is very unlikely to
be single-shard since that requires all of the 100 parents have been placed to
the same shard. Thus, we analyze parent counts for the 1,119,794 transactions
in the 601001st to 601500th Bitcoin block (coinbase transactions are excluded
since they have no parents and are guaranteed to be single-shard). Because
Bitcoin blocks are usually referred to using _height_ s, which are indices
starting from zero, we refer to the $(k+1)$-th block as block $k$ in the rest
of this paper.

Figure 4: Distribution of parent transaction counts

Figure 5: The percentage of transactions with one parent

Fig. 4 shows that parent transaction counts conform to a power-law
distribution, which means that transactions with a few parents occur more
often than transactions with many parents. We are particularly interested in
transactions with one parent because a placement algorithm can easily make
such transactions single-shard. By analyzing block 0$\sim$680k (mined in April
2021 [19]), we found that one-parent transactions account for a significant
proportion throughout the history of Bitcoin and remain approximately 75%
since block 420k as shown in Fig. 5. The percentage changes a lot at heights
lower than 100k because blocks include only a few transactions at the start of
Bitcoin as shown by the blue bars in Fig 5.

###  III-B Cost of Cross-shard Transactions

In this section, we compare the execution time of single-shard transactions
and cross-shard transactions by quantitative measurements. An OmniLedger-like
sharding protocol is implemented based on Bitcoin Core [20], and 27k Bitcoin
transactions (from block 601000 to block 601009) are replayed in a 2-shard
environment. More details about the implementation and the testbed will be
given in Section V. For a single-shard transaction, the client sends a TX
request containing the transaction directly to the output shard. For a cross-
shard transaction, the client sends a LOCK request to every input shard and a
COMMIT request to the output shard, provided all input shards reply with
positive locking results (see Fig. 3). The measurement results show that the
median processing time for a TX request, a LOCK request, and a COMMIT request
are 211 $\mu$s, 438 $\mu$s, and 259 $\mu$s, respectively.

To understand why LOCK and COMMIT requests take a longer time to process than
TX requests, we further measure the processing time of each step in request
execution. In an UTXO-based blockchain, a node checks for three conditions
when verifying a transaction: 1) the input UTXOs exist and are unspent, 2) the
total input value is not less than the total output value, and 3) the
transaction includes the correct signatures of the input UTXO owners. Provided
the transaction meets all three conditions, the node will execute it by
removing the input UTXOs and add the output UTXOs to the system state. In Fig.
6b, the _UTXO_exist_value_ label corresponds to the first two transaction
verification steps, the _Sig_ label to the third verification step, and the
_Spend_add_ label to the system state update. Fig. 6b shows that checking
signatures of input UTXOs dominates the processing time of a single-shard
transaction. In Fig. 6c, the _UTXO_exist_ label corresponds to the first
transaction verification step. Note that LOCK request processing does not
include value checking because an input shard is not aware of the value of
input UTXOs in other input shards. Thus, value checking is done by the output
shard during COMMIT request processing. Similarly, system state update is
separated into two parts: removing input UTXOs in LOCK request processing, and
adding the output UTXOs in COMMIT request processing. Compared with TX request
processing, LOCK request processing includes two additional steps: signing the
lock result (labeled as _Sign_), and sending the result to the client (labeled
as _Send_). These two steps are comparable in processing time to input UTXO
signature checking. Lastly, COMMIT request processing is dominated by
verifying the signatures of lock results, which are produced by input shards.
The step is labeled as _Shard_sig_ in Fig. 6d.

As a result, if a one-parent transaction becomes cross-shard as a result of
being placed to a different shard than its parent, its processing time would
be more than tripled due to input shard authentication and communication
overhead.

(a) TX, LOCK, and COMMIT

(b) Breakdown of TX

(c) Breakdown of LOCK

(d) Breakdown of COMMIT

Figure 6: Request processing time (2 shards)

##  IV Case Study: OptChain

OptChain is a client-side blockchain transaction placement algorithm. A client
runs the algorithm to compute the output shard ID before sending its
transaction to servers. OptChain has been proven to have better performance
than Metis, an offline graph partitioning algorithm, and a greedy algorithm
that places transactions to the shard with most of its parents.

###  IV-A Overview of OptChain

We summarize the design principles of OptChain in this section. The goal of
OptChain is to reduce cross-shard transactions while maintaining load balance.
To reduce cross-shard transactions, OptChain builds a transaction graph with
transactions as vertices and transaction dependencies as edges. Therefore,
from the perspective of graph theory, the transaction placement problem is a
streaming graph partitioning problem [21]. OptChain associates each
transaction with a fitness-score array of size $n_{s}$, which is the number of
shards in the system. Each element in the array reflects the fitness between
the transaction and the corresponding shard. Based on PageRank [22], OptChain
computes a child transaction’s fitness-score array as a weighted sum of its
parents’ fitness-score arrays. For example, in Fig. 7, when a new transaction
$x$ arrives in a two-shard system, OptChain calculates the fitness score of
the first shard as $f_{x1}=w_{d}f_{d1}+w_{e}f_{e1}$, since transaction $d$ and
$e$ are the two parents of $x$. The weight of the a parent is
$\nicefrac{{1}}{{n_{c}}}$, where $n_{c}$ is the number of child transactions
of this parent; so, in the example, the weights of both parent transactions,
namely $w_{d}$ and $w_{e}$, equal one. The fitness score of the second shard
$f_{x2}$ is calculated the same way.

To account for load balance, OptChain divides a fitness score by the
corresponding partition size (i.e., the number of transactions placed to the
shard), and calls the resultant value the Transaction-to-Shard (T2S) score of
the shard. In addition, OptChain requires clients to frequently sample servers
for communication latency and server-side transaction queue length in order to
balance loads dynamically. We refer to this design as feedback load balancing
because it resembles the idea of feedback control in control theory—use the
measured shard latency to adjust how many transactions should be placed to the
shard. The T2S score and feedback load balancing jointly determine the output
shard of a given transaction.

Figure 7: Principle of OptChain. The fitness-score array of $x$ is a weighted
sum of the fitness-score arrays of $x$’s parents.

###  IV-B Partitioning Quality

We assess partitioning quality using two metrics: cross-shard transaction
ratio, and load imbalance, which is defined as the maximum partition size
minus the minimum partition size. To study whether OptChain can produce high-
quality partitions under various workloads, we employ four transaction sets
that are detailed in Table II to evaluate _OptChain-T2S_ , which is Optchain
without feedback load balancing. OptChain-T2S is used instead of OptChain
because the feedback load balancing feature demands running servers, whereas
OptChain-T2S is independent of server states, enabling us to obtain the
partitioning quality without running servers. This independence is
particularly convenient when evaluating the partition quality under a large
$n_{s}$. Besides, OptChain-T2S is the core of OptChain; therefore,
understanding the performance of OptChain-T2S is definitely helpful in
understanding the performance of OptChain. We will show the impact of feedback
load balancing in Section V. Placement results for transactions prior to the
start block height of a dataset are generated using OptChain-T2S beforehand.

Table II: Four datasets Name | Block heights | Transaction counta
---|---|---
dataset 1 | [0, 200k) | 7,316,308
dataset 2 | [200k, 227k) | 7,371,053
dataset 3 | [227k, 252k) | 7,316,337
dataset 4 | [252k, 275k) | 7,238,332
aCoinbase trancations are excluded.

Fig. 8 and Fig. 9 compare the cross-shard transaction ratio and load imbalance
of OptChain-T2S and HP. For all datasets, OptChain-T2S produces significantly
fewer cross-shard transactions than HP. From Fig. 9, one can see that HP does
extremely well at load balancing. Although Optchain-T2S does not evenly
distribute transactions to shards, the load imbalance decreases as the number
of shards increases. However, in Fig. 9d, some shard still receives
considerably more transactions than others even with 128 shards. Considering
the fact that OptChain-T2S produces noticeably less cross-shard transactions
for dataset 4 than for the other three datasets as shown in Fig 8, we suspect
that dataset 4 may have some special traits that break Optchain-T2S’s load
balancing mechanism and cause the vast majority of transactions to be placed
to the same shard.

(a) dataset 1

(b) dataset 2

(c) dataset 3

(d) dataset 4

Figure 8: Cross-shard transaction ratio

(a) dataset 1

(b) dataset 2

(c) dataset 3

(d) dataset 4

Figure 9: Load imbalance

To confirm the above hypothesis, we analyze the dynamic shard loads in a
4-shard environment as illustrated in Fig. 10, which implies that OptChain-T2S
fails to balance loads since block 253k. Unsurprisingly, HP balances loads
remarkably well in that every shard constantly receives about 25% of the
transactions. In Fig. 10a, the three small spikes between block 200k and 260k
are the starting points of datasets 2$\sim$4, and the glitches at the
beginning result from small block sizes. Another observation is that, in Fig.
10b, all curves are quite flat in range of block [0, 50k) and block [125k,
175k), but fluctuate a lot in the range of [70k, 120k) and [180, 250k). We
find that this pattern occurs with transactions spending the output UTXOs of
their immediate predecessors, which are ordered right before them in the same
block. OptChain-T2S tends to place such transactions to the same shard as
their predecessors. As a result, a sequence of such transactions causes a
shard to receive more transactions than other shards temporarily. For example,
starting from the 326th transaction in block 177253, each of the 267
subsequent transactions is a child of its immediate predecessors [23]. Table
III shows that such transactions account for a relatively high percentage
whenever the shard load curves fluctuate drastically.

(a) HP

(b) OptChain-T2S

Figure 10: Dynamic shard loads (4 shards) Table III: Percentage of Transactions Consuming the UTXO Produced by their Immediate Predecessors Block height |  Transactions depending on their immediate predecessors
---|---
[0, 50k) |  0.1%
[70k, 120k) |  18.6%
[125k, 175k) |  6.1%
[180k, 250k) |  21.3%
[253k, 275k) |  14.6%

To further understand why OptChain-T2S suddenly loses its load balancing
capability, we analyze transaction fitness scores and find that some
transactions have abnormally high fitness scores since block 251750 (see Fig.
11). These high fitness scores are created by transactions that “aggregate”
many previous transactions placed to the same shard. Fig. 12 illustrates a
simplified scenario of such, where transaction $x$ has 10 parents whose
fitness-score array are all [0, 1] (i.e., the system has two shards, and the
second shard has the higher fitness score for all the parents). $x$’s fitness-
score array can be computed as [0, 10] by following the rules described in
Section IV-A. Note that the second element of $x$’s fitness-score array is 10
times higher than that of its parents. In Fig. 12b, transaction $y$ is a child
transaction of $x$, and its fitness-score array is [3, 10]. Provided the two
shards have the same load, $y$ will be placed to the second shard even though
three out of four of its parents are in the first shard. Moreover, $y$ gets
“tainted” by $x$ (i.e., $y$ inherits the high fitness score of the second
shard from $x$) and will propagate the high fitness score to its children.
Between block 251750 and block 251840, many transactions aggregate recently
tainted transactions (Fig. 13) and collectively amplify the fitness score by
50 orders of magnitude. In other words, aggregating transactions amplify
fitness scores, and the resultant high fitness scores propagate to other
transactions through dependencies. By comparing Fig. 13 with Fig. 11, one can
see that 1) whenever there are tainted transactions, the fitness score in Fig.
11 is at a high level, and 2) whenever there are transactions that aggregate
recently tainted transactions, the fitness score grows.

Figure 11: Variation in OptChain fitness score

(a) $x$ amplifies fitness scores.

(b) $x$ dominates $y$’s placement result.

Figure 12: An example of an aggregating transaction

Figure 13: Tainted transactions and aggregating transactions

OptChain-T2s’s failure to handle dataset 4 proves that PageRank is not
completely suitable for the transaction placement problem. PageRank is
originally designed by Google to identify important websites. A website
referenced by a lot of other websites is deemed important. However, this
notion does not apply to the transaction graph. A transaction with many parent
transactions should not be important and dominates the placement result of its
child transactions. Besides, in PageRank, a website is also deemed important
if it is referenced by an important website. When mapped from a website graph
to a transaction graph, this rule becomes “a transaction is important if one
of its parent transactions is important”. Based on this rule, a transaction
inherits high fitness scores from its aggregating parents and heavily
“attract”s its descendants to its shard.

Figure 14: Dynamic shard loads of OptNorm (4 shards)

Knowing the shortcoming of OptChain-T2S, we propose a quick fix— _OptNorm_ ,
which normalizes fitness scores. Specifically, given a transaction, OptNorm
computes the fitness score array and selects the output shard in the same way
as OptChain-T2S does. Next, however, OptNorm normalizes the fitness-score
array, i.e., dividing each element by the sum of all elements. The
normalization guarantees future transactions will have parent transactions of
equal importance since every parent transaction’s fitness score array has an
element-wise sum of one. Fig. 14 illustrates that OptNorm balance loads better
than OptChain-T2S and can survive aggregating transactions.

##  V Evaluation

We implemented OptChain as well as an OmniLedger-like sharding protocol based
on Bitcoin Core [20]. We made the same change to the OmniLedger protocol as
the OptChain paper does to overcome the bandwidth limit—clients send
transactions directly to the input and output shards instead of gossiping the
transaction. Experiments are done on a local cluster. 64 VMs (each with 2 CPUs
and 12GB memory) are created on 16 machines, each of which has dual Xeon
E5-2620 at 2.1 GHz (12 cores) and 64GB RAM. Each VM runs an instance of our
modified Bitcoin Core and is used as a blockchain node. One client runs on
another machine with dual Xeon E5-2630 at 2.6 GHz (12 cores, 2 hyperthreads
per core) and 256GB RAM. The client reads historical transactions in Bitcoin
block [250k, 260k) with 2.9 million transactions in total, and sends them to
the peers at a rate of 4.5k tps. Transactions in this range are used in order
to evaluate the impact of aggregating transactions on system performance. A
latency of 100 ms is imposed on every link between peers, and the bandwidth is
limited to 500 Mbps. We use this relatively high bandwidth because we notice
that OptChain-T2S places most transactions in one shard, and low network
bandwidth will be a bottleneck for that shard.

Fig. 15a demonstrates that feedback load balancing mitigates the performance
degradation of OptChain-T2S but cannot eliminate the degradation. By comparing
Fig. 15c and 15d, one can see that, although the load of the largest partition
under OptChain is lower than that under OptChain-T2S, it still surges at
around 200s, exactly when the throughput starts to drop. In contrast, OptNorm
distributes load fairly evenly at 200s, which confirms that it can effectively
overcome the aggregating transaction issue of OptChain. The overall throughput
of HP and OptNorm are 865 tps and 3487 tps, respectively, which means OptNorm
improves the system performance by 4x.

(a) Throughput

(b) OptNorm

(c) OptChain-T2S

(d) OptChain

Figure 15: Throughput and loads comparisons (16 shards)

The authors of OptChain noticed our research and created a new version of the
OptChain paper to update their algorithm description (referred to as
_OptChainV2_) [24]. Specifically, OptChainV2 allows multiple edges between two
vertices in the transaction graph, and changes the definition of $N_{in}$
($N_{out}$) from a set of input (output) transactions to a multiset of input
(output) transactions. For completeness, this paper also evaluates the
performance of OptChainV2 using Bitcoin block [250, 260) and compares the
result with OptNorm and OptChain. To measure latency, all transactions must be
completed within a reasonable amount of time, so we reduce link delay to 10ms
and warm up database cache before each test. This testing environment
modification equally benefits all placement algorithms. Fig. 16 shows, when
the client sends transactions at a rate of 3.5k tps, both OptChainV2 and
OptNorm can achieve a 3.5k-tps throughput, whereas OptChain can reach only
2.2k tps. Also, the 50th percentile latency of OptChainV2 and OptNorm are
almost the same, both 99.9% shorter than the 50th percentile latency of
OptChain. On the other hand, when the system is overloaded with a 5k-tps
transaction rate, OptChainV2 achieves 4% higher throughput than OptNorm.

(a) Throughput

(b) Latency (3.5k-tps transaction rate)

Figure 16: Performance comparison (16 shards)

##  VI Conclusion

In conclusion, cross-shard transactions are expensive due to input shard
authentication and communication overhead. Placement algorithms considering
transaction dependencies can significantly reduce cross-shard transaction
ratio and thus boost system performance. The original OptChain does not
balance loads well under workloads that include many aggregating transactions
and their descendants. The proposed OptNorm is a simple yet effective fix.
OptChainV2 does not exhibit the shortcoming.

## References

  * [1] K. Croman, C. Decker, I. Eyal _et al._ , “On scaling decentralized blockchains,” in _International conference on financial cryptography and data security_. Springer, 2016, pp. 106–125.
  * [2] Y. Lewenberg, Y. Sompolinsky, and A. Zohar, “Inclusive block chain protocols,” in _International Conference on Financial Cryptography and Data Security_. Springer, 2015, pp. 528–547.
  * [3] C. Li, P. Li, D. Zhou, W. Xu, F. Long, and A. Yao, “Scaling nakamoto consensus to thousands of transactions per second,” _arXiv preprint arXiv:1805.03870_ , 2018.
  * [4] I. Eyal, A. E. Gencer, E. G. Sirer, and R. Van Renesse, “Bitcoin-ng: A scalable blockchain protocol,” in _13th $\\{$USENIX$\\}$ Symposium on Networked Systems Design and Implementation ($\\{$NSDI$\\}$ 16)_, 2016, pp. 45–59.
  * [5] L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. ACM, 2016, pp. 17–30.
  * [6] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE, 2018, pp. 583–598.
  * [7] M. Zamani, M. Movahedi, and M. Raykova, “Rapidchain: Scaling blockchain via full sharding,” in _Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security_ , 2018, pp. 931–948.
  * [8] H. Dang, T. T. A. Dinh, D. Loghin, E.-C. Chang, Q. Lin, and B. C. Ooi, “Towards scaling blockchain systems via sharding,” in _Proceedings of the 2019 International Conference on Management of Data_ , 2019, pp. 123–140.
  * [9] C. Decker and R. Wattenhofer, “A fast and scalable payment network with bitcoin duplex micropayment channels,” in _Symposium on Self-Stabilizing Systems_. Springer, 2015, pp. 3–18.
  * [10] J. Poon and T. Dryja, “The bitcoin lightning network: Scalable off-chain instant payments,” 2016.
  * [11] D. R. Stinson, _Cryptography: theory and practice_. Chapman and Hall/CRC, 2005.
  * [12] L. N. Nguyen, T. D. Nguyen, T. N. Dinh, and M. T. Thai, “Optchain: optimal transactions placement for scalable blockchain sharding,” in _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_. IEEE, 2019, pp. 525–535.
  * [13] M. Castro, B. Liskov _et al._ , “Practical byzantine fault tolerance,” in _OSDI_ , vol. 99, 1999, pp. 173–186.
  * [14] B. Lampson and H. E. Sturgis, “Crash recovery in a distributed data storage system,” 1979.
  * [15] J. N. Gray, “Notes on data base operating systems,” in _Operating Systems_. Springer, 1978, pp. 393–481.
  * [16] R. Guerraoui and J. Wang, “How fast can a distributed transaction commit?” in _Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems_ , 2017, pp. 107–122.
  * [17] D. Skeen, “Nonblocking commit protocols,” in _Proceedings of the 1981 ACM SIGMOD international conference on Management of data_ , 1981, pp. 133–142.
  * [18] L. Ren, K. Nayak, I. Abraham, and S. Devadas, “Practical synchronous byzantine consensus,” _arXiv preprint arXiv:1704.02397_ , 2017.
  * [19] Blockchain.com, “Bitcoin Explorer,” https://www.blockchain.com/btc /block/680000, accessed: 2021-09-09.
  * [20] B. C. Developers. Bitcoin core integration/staging tree. Last accessed 15 Jun 2020\. [Online]. Available: https://github.com/bitcoin/bitcoin
  * [21] I. Stanton and G. Kliot, “Streaming graph partitioning for large distributed graphs,” in _Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2012, pp. 1222–1230.
  * [22] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bringing order to the web.” Stanford InfoLab, Tech. Rep., 1999.
  * [23] Blockchain.com, “Bitcoin Explorer,” https://www.blockchain.com/btc/ tx/91c40e195524962aa3e6cd588e2038b392368382d0815aba7034f51c3c e2579b, accessed: 2021-09-08.
  * [24] L. N. Nguyen, T. D. Nguyen, T. N. Dinh, and M. T. Thai, “Optchain: optimal transactions placement for scalable blockchain sharding,” _arXiv preprint arXiv:2007.08596v2_ , 2021.