# Reducing Latency of DAG-based Consensus in the Asynchronous Setting via the
UTXO Model

Keyang Liu  The University of Tokyo
<EMAIL_ADDRESS>Maxim Jourenko  Tokyo Institute of
Technology
<EMAIL_ADDRESS>Mario Larangeira  Tokyo Institute of
Technology/IOG
<EMAIL_ADDRESS>
###### Abstract

DAG-based consensus has attracted significant interest due to its high
throughput in asynchronous network settings. However, existing protocols such
as DAG-rider (Keidar et al., PODC 2021) and “Narwhal and Tusk” (Danezis et
al., Eurosys 2022) face two undesired practical issues: (1) high transaction
latency and (2) high cost to verify transaction outcomes. To address (1), this
work introduces a novel commit rule based on the Unspent Transaction Output
(UTXO) Data Model, which allows a node to predict the transaction results
before triggering the commitment. We propose a new consensus algorithm named
“Board and Clerk”, which reduces the transaction latency by half for roughly
50% of transactions according to our experiments. As the tolerance for faults
escalates, more transactions can partake in this latency reduction. In
addition, we also propose the Hyper-Block Model with two flexible proposing
strategies to tackle (2): blocking and non-blocking. Using our proposed
strategies, each node first predicts the transaction results if its proposal
is committed and packs this result as a commitment in its proposal. The hyper-
block packs the proposal’s signature, and the consensus layer outputs to prove
the transaction results.

###### Index Terms:

Consensus, Byzantine Fault Tolerant, UTXO.

##  I Introduction

The appearance of blockchain has catalyzed the investigation of secure and
resilient computation within decentralized systems fraught with Byzantine
faults in both Nakamoto consensus and Byzantine Fault Tolerance (BFT)
research. However, many public blockchains, such as Bitcoin [18], rely on
Proof of Work (PoW) and have been criticized due to energy consumption and
constrained transaction throughput. In response to these challenges,
alternative strategies offer a less computationally intensive mechanism. For
example, executing the BFT algorithm based on a committee selected by Proof of
Stack (PoS) has been adopted for balancing throughput and energy consumption.

Numerous asynchronous BFT protocols have been studied in the past, and it
constitutes a committee of nodes that are continuously proposing blocks (or
proposals) and outputting a sequence of valid proposed blocks. Recently,
Directed Acyclic Graph (DAG)-based consensus algorithms such as DAG-rider [11]
and “Narwhal and Tusk” [6] have demonstrated superior efficiency against
existing solutions. However, two shortcomings persist: (1) There is high
latency as one DAG consensus requires seven rounds of communication on
average, and (2) The protocol’s inability to discern failed transactions,
which incurs additional costs (_e.g._ additional communication for signatures
from the committee) for practical application. This work offers a novel means
to order transactions, thus improving BFT protocols’ efficiency by relying on
the UTXO Model.

###  I-A Related Works

#### The BFT Revival

The study of BFT consensus protocols has a long history [4, 22, 8, 20]. These
protocols are proved to tolerate $f$ byzantine faulty nodes among $N$ nodes,
where $f<\frac{N}{3}$. Specifically, asynchronous BFT protocols [10, 15, 14,
13, 11, 6] usually requires all nodes to create proposals concurrently, thus
avoid a single-node failure.

The study of the BFT problem under asynchronous conditions started almost
three decades ago with Ben-Or et al. [1]. Since then, many solutions [15, 14,
23] have been proposed for solving this problem practically under the BFT
framework. In 2021, Keidar et al. [11] proposed DAG-rider, a novel approach
that harnesses the DAG to organize all nodes’ proposals and votes. This idea
uses a growing sub-DAG to amortize the cost of making consensus, thereby
drastically enhancing the speed of the asynchronous BFT algorithm.

Building upon this foundation, Danezis et al. [6] refines this design by
merging the DAG with the gossip protocol to form the Narwhal Memory Pool,
further dispersing the voting cost associated with the following proposal
creation phase and catapults the system’s throughput to a new peak (120K
transactions per second on the Internet). Our work explores further
improvement following these works.

#### The Blockchain UTXO Model

Many Blockchain-based applications adopt the UTXO Model [18], which is an
alternative to the Account Model (_e.g._ , a bank system and Ethereum [21]).
Chakravarty et al. [5] defined the _Extended_ UTXO Model as the stepping stone
to provide smart contract capabilities to the Cardano Blockchain [7, 9].
Despite its wide use in the blockchain setting, to the best of our knowledge,
not many protocols leverage the benefits of the UTXO Model to propose novel
BFT protocol designs. This work showcases this approach by combining the BFT
design and the _Extended_ UTXO Model to achieve better performance.

In the same spirit, Müller et al. [17] proposed a UTXO-based ledger using the
early cited inherent UTXO design parallelism to improve performance, thus
speeding up the consensus process in the blockchain setting. Our work uses a
similar strategy to shorten the latency but for the BFT setting. Although the
UTXO model is widely used for Nakamoto consensus, to our best knowledge, this
is the first work to propose its use in the BFT consensus algorithm design.

###  I-B Our Contributions

This work has two main contributions:

  * 1

We introduce a novel DAG-based commit rule designed explicitly for a UTXO-
based transaction model. We propose a new consensus protocol named “Board and
Clerk” to replace Tusk, effectively reducing transaction latency.

  * 2

We introduce two new proposing flows and the Hyper Block Model designed to
authenticate transaction results, which has zero communication overhead.

More concretely, the DAG-based consensus under asynchronous network conditions
takes seven rounds on average to commit a sub-DAG. We show this latency is not
mandatory for most transactions in our solution. Our work relies on the UTXO
Model and proposes a new commitment rule for reducing transaction latency.
Specifically, we equipped the DAG-based consensus and the Narwhal Memory Pool
from [6] with a new commit rule for transactions under the UTXO Model. This
new commit rule allows us to fast commit the transaction with predictable
results (succeed or failed), reducing the transaction confirmation latency
without harming the correctness property. We propose Board to handle the fast
commitment and change Tusk accordingly as Clerk. Our experiment shows that our
Board and Clerk can achieve better latency than the original Tusk.

Furthermore, DAG-based consensus does not have communication overhead (_i.e._
, there is no additional communication after the DAG is created), which means
the order of transactions is unknown when nodes construct the DAG. This
scenario may lead to the possible commitment of conflicting transactions
(transactions that consume at least one same input, a.k.a. double spending).
Since the consensus does not generate additional signatures after gossiping
proposals, a client faces challenges in substantiating a transaction’s success
without all nodes’ assistance. We propose two strategies to adjust the
proposal flow, ensuring that all nodes can predict all transaction outcomes if
the consensus round picks their proposal. Once the consensus output is
confirmed, any honest node can generate proof to authenticate whether a
transaction was successful according to the corresponding commitment.

###  I-C Organization

Section II provides more details about the problems we will resolve and the
building blocks of our protocol. Sections III and IV thoroughly describe our
protocol. Finally, Section V provides the analysis and experimental results,
whereas our final remarks are in Section VI.

##  II Preliminaries

This section provides an overview of some fundamental concepts we utilize to
describe our protocol. In particular, we revisit the asynchronous DAG-based
BFT protocol design and the UTXO Model, which are the cornerstones of our
proposal.

###  II-A Typical Asynchronous BFT Protocol Setting

A BFT protocol typically proceeds in rounds involving multiple time slots and
message exchanges. There are two types of participants: nodes and workers.
Nodes participate in reaching distributed consensus by exchanging proposals
with other nodes, while workers collect entries and deliver transaction
batches to nodes. Each node has a reliable method for broadcasting messages
[3] and a uniform random coin for reaching consensus [4]. Furthermore, we
assume the network is asynchronous, where messages between participants can
take up to $\Delta$ time slots to be received where $\Delta$ is an unknown
value. Each node knows the total number of participants and their identities,
including their verification keys.

###  II-B DAG-based Asynchronous BFT Protocols

These protocols are round-based distributed processes consisting of the DAG-
making and decision-making phases, as in [6]. Each node receives a batch of
transactions from workers and generates a proposal for consensus with other
nodes. The architecture of a node is depicted in Figure 1. In the later
sections, we denote the Narwhal DAG as DAG.

Figure 1: The communication model of a node in “Narwhal and Tusk” [6]. The
workers in green transferred the concrete transactions. The memory pool, in
yellow, accomplishes the reliable broadcast. The consensus layer only needs
access to the global coin for making decisions.

More concretely, workers of a node will pack clients’ transactions as batches
and broadcast them to workers of other nodes using a Gossip Protocol, such as
the one described in [2]. Upon receiving enough responses from other workers,
the worker sends the batch ID (i.e., hash values of underlying transactions)
to its node.

During the DAG-making phase of round $r$, the node aggregates the batch ID to
create a proposal $P$ and $2f+1$ proposals’ ID from round $r-1$. The node will
use $P$ as input to initiate a Byzantine Reliable Broadcast (RBC) [12]
instance. After this RBC instance is complete, the node stores $P$ in its
Narwhal Memory Pool [6].

In the DAG-making phase, a node engages in at least $2f+1$ RBC instances and,
therefore, stores $2f+1$ proposals. For proposals that contain unknown
batches, the Narwhal asks the worker to synchronize the missing batches before
continuing the RBC instance. The $2f+1$ stored proposals will be linked to its
proposal in the next round. Thus, all proposals within Narwhal are stored as a
round-based DAG, with an edge extending from one proposal to its $2f+1$
ancestors.

The DAG-based consensus algorithm chooses a sub-DAG from the Narwhal during
the decision-making phase to fully utilize the results of the DAG-making
phase. The Tusk consensus [6] randomly chooses one leader every two rounds
from $N$ nodes, based on a universally random coin toss for being the
candidate of a previous round’s leader. If more than $f+1$ proposals link the
selected candidate’s proposal $L$, the protocol commits the sub-DAG linked by
$L$. By leveraging a deterministic stable traversal algorithm, this $L$
uniquely determines the order of proposals within its sub-DAG, thereby
dictating the output of the consensus algorithm.

Via the RBC instances, all honest nodes are assured of sharing an identical
DAG eventually. If a leader’s proposal from round $r$ has been referenced by
$f+1$ proposals in round $r+1$, then the leader’s proposal will always be in
the sub-DAG of the leader of round $r+2$. Conversely, if a leader proposal
receives less than $f+1$ followers, it may not be committed as a leader. This
characteristic ensures the consistency of leader order and inherently verifies
that the traversal of a DAG is deterministic. For a more detailed discussion,
we refer the reader to the full work [6].

Figure 2 illustrates an example of DAG: the leader at round $r-2$ is the
proposal 3-4, which does not have enough following blocks at round $r-1$.
Thus, it cannot be committed as a leader (alert marked). The leader proposal
at round $r$ is proposal 1-6, with two following proposals, which can commit
all proposals in its sub-DAG (check-marked) through a deterministic traverse
algorithm.

Figure 2: An example of proposal committing over DAG. The proposals are
depicted as #node-#round, where #node can be from $0$ to $3$ and round $r=6$.

It is worth noticing that each node will have different views of the DAG at
each round. For example, in Figure 2, node one and node three have different
views at round $r$ _i.e._ , the sub-DAG that leads by proposals 1-6 and 3-6.
We use the term “observation” to denote that a proposal or transaction is in
such a local view, _i.e._ , at round $r$, node 1 observes proposal 0-4 while
node 3 does not.

###  II-C The UTXO Model

The state of a UTXO-based ledger is represented by the set of UTXO that
contain some data $\delta\in\\{0,1\\}^{*}$ as well as a script
$s\in\\{0,1\\}^{*}$. A transaction $t$ consists of (1) a set of inputs that
are references to UTXOs present on the ledger as well as witness data
$w\in\\{0,1\\}^{*}$ and (2) a list of outputs that are newly defined UTXOs.
Moreover, the ledger can define constraints on UTXO $\psi_{u}$ and constraints
on transactions $\psi_{t}$ [5]. A transaction is considered internally valid
if (1) for each of its inputs $i$ holds that
$s_{i}(w_{i},\delta_{i},t)\neq\bot$ where $w_{i}$ is the inputs witness data
and $s_{i},\delta_{i}$ are the referenced UTXOs script and data; (2) for each
UTXO $u$ in its outputs holds that $\psi_{u}(u)\neq\bot$ and (3) that
$\psi_{t}(t)\neq\bot$. A transaction is considered externally valid if all
UTXOs referenced by its inputs are in the ledger’s current state. When a
transaction is successfully committed to the ledger, all UTXOs referenced in
its inputs are removed from the ledger’s state, and all UTXOs in its outputs
are added to the ledger’s state. Two transactions are conflicting if at least
one UTXO is referenced in both transactions’ inputs.

Verifying whether a transaction can be committed to the ledger relies only on
verifying (1) External validity and (2) Internal validity [7]. We note that
internal validity does not depend on the ledger’s global state and can be
verified immediately upon transaction creation. Moreover, while external
validity requires knowledge of the ledger’s state, i.e., which UTXOs are
present, it only relies on a small subset of the UTXOs present on the ledger.
Thus, the external validity of a set of non-conflicting transactions can be
computed in parallel. This inherent parallelism of UTXO-based ledgers is an
advantage to other ledger paradigms and is particularly interesting to this
work.

###  II-D Notation

Table I lists the notations we used in this work:

TABLE I: Table for notations term |  Description
---|---
Tx |  Short for a transaction, A digital exchange of value or information on the blockchain.
TXO |  Short for transaction output, the minimum unit of information on the blockchain. It can only be created by one transaction and consumed by another transaction.
UTXO |  Short for unspent transaction output, the TXO that is not consumed by other transactions.
Batch |  A wrap of transactions for a consensus algorithm.
Proposal |  A wrap of batches and other metadata that is proposed by a node for making consensus in the consensus algorithm.
Node |  Process that participants of the consensus algorithm for the blockchain.
Worker |  Process that collects transactions sent by clients and wraps them as a batch for nodes
Leader |  Leader is a pair of node IDs and rounds, the output of the DAG-based consensus. We abuse this notation for the corresponding proposal
$N$ |  Number of nodes participants in the consensus algorithm
$f$ |  number of maximum allowed byzantine nodes, usually satisfying $3f+1\geq N$

##  III Board and Clerk

We first address the latency issue of existing DAG-based BFT consensus.
According to [6], the average latency of Tusk under an asynchronous setting is
seven asynchronous rounds. Our proposal uses the UTXO model to finalize some
transactions’ results before this number and thus improve the user experience.
Before describing our protocol, we present an initial intuition regarding the
interplay between the DAG data structure and the UTXO Model.

###  III-A Intuition: DAG meets UTXO

Our first proposal is a new transaction commit rule that compares the ordering
decided by the random leader in Tusk. The UTXO Model is designed to support
parallelism, so we do not need a strict sequential order of all transactions.
Considering that workers can ensure internal validity beforehand, the
consensus algorithm only needs to identify double-spending transactions and
agree on which transactions are invalid.

Currently, the existing DAG-based consensus algorithms rely on deterministic
DAG traversal algorithms to determine the transaction order and the external
validity. However, the proposer of the leader proposal often decides the order
almost randomly based on how it arranged the proposals from the previous
round. This approach requires significant work to determine the transaction’s
external validity.

Therefore, we propose a new commit rule that does not rely on the order of
transactions in the batches, making the results of transactions more
predictable before their commitment. We use the parallelism of the UTXO model
in our approach. Given that the proposed phase has checked internal validity,
our commit rule uses the DAG to finalize the external validity independent of
the consensus algorithm. Consequently, any node can be confident about the
results of most transactions (except double-spending transactions) after a
certain number of rounds, which enables them to process the following
transactions and, ultimately, reduce the actual latency of transaction
commitment.

###  III-B Transaction States

We use the transaction state to represent its lifecycle in memory. The states
can be:

  * •

Verified: A received transaction that has passed the internal validity check
by a worker;

  * •

Submitted: A verified transaction included in at least one single proposal;

  * •

Fast-committed: A submitted transaction that will be committed in the future
with a confirmed result;

  * •

Committed: A submitted transaction that the consensus algorithm has committed.

We use the fast-committed state to process transactions and apply changes to
the state before committing them via the consensus algorithm. The fast-
committed transactions use a shorter internal path to execute and enable the
node to verify its following transactions. This feature is especially
advantageous when the consensus algorithm takes a long time to select
appropriate leaders for committing the DAG.

###  III-C The Novel Commit Rule

A local node must determine whether a transaction will succeed or fail to
enable a fast-committed channel. Therefore, a procedure to decide the external
validity of a transaction is required to reduce uncertainty when extending the
DAG. Hence, we have made the following two changes to the proposal flow
compared to Narwhal and Tusk:

  1. 1.

We require that any valid batch of transactions does not contain conflicting
transactions. A batch is a wrapper of transactions that are submitted through
a worker. It is reasonable to assume that the worker has verified all
transactions in the batch, ensuring that transactions spending the same UTXO
are not kept. It should be noted that different batches may have conflicting
transactions since they may come from different workers.

  2. 2.

We require that a node’s proposal for round $r$ always includes its proposal
for round $r-1$. This requirement ensures the basic consistency of the node’s
proposal. If a node’s proposal at round $r$ is committed, so is its proposal
at round $r-1$. This significantly improves the reliability of the projection
of the external validity decision.

Now, we provide some definitions describing our approach to determine external
validity.

###### Definition 1

For a sub-DAG that begins with a node’s proposal at round $r$ containing a
transaction $tx$ for the first time, we say that the node votes for $tx$ at
round $r$.

A node generally votes for a transaction in one of two cases: (1) its proposal
includes the transaction, or (2) its proposal links to a proposal from another
node that already voted for the transaction. The vote is only kept for the
minimum round. To be noticed, a node may vote for conflicting transactions at
the same round; in this case, its vote is counted for both transactions.
Figure 3 shows some typical cases for voting.

Figure 3: Three examples for transaction votes. (a) Node 1 proposes $tx_{1}$
at round 1. Node 0 and Node 2 vote it in round 2, and Node 3 votes in round 3;
(b) Node 3 proposes for $tx_{2}$ in round 1, and Node 2 votes for both
transactions in round 3; (c) Node 2 still votes for $tx_{1}$ and $tx_{2}$ at
round 3.

###### Definition 2

For any set of transactions, we define an ordering relationship $Ord$ such
that there is only one stable sort of the set under $Ord$.

A straightforward example is ordering according to the hexadecimal
representation of transaction IDs.

######  Definition 3 (External Validity-Commit Rule)

For all transactions inside a sub-DAG to be committed by the consensus
algorithm at even rounds, a transaction is successful only if more nodes have
voted for it before any other transactions conflict. In other words, let
$tx.I$ be the inputs of $tx$ and $\mathsf{TX_{S}}$ be the set of all submitted
transactions. We commit $tx$ if:

$\forall tx^{\prime}\in\mathsf{TX_{S}}\;:\;tx^{\prime}.I\cap
tx.I=\varnothing.$

Furthermore, it is also committed if

$|\\{\text{nodes vote tx first}\\}|>|\\{\text{nodes vote }tx^{\prime}\text{
first}\\}|,$

or otherwise if

$\begin{split}&tx>_{Ord}tx^{\prime},\\\ &|\\{\text{nodes vote tx
first}\\}|=|\\{\text{nodes vote tx' first}\\}|.\\\ \end{split}$

Definition 3 allows for a deterministic outcome of the transaction’s external
validity. Transactions without conflicts are committed directly. For
transactions with conflicts, we commit according to the votes from nodes, and
any tie will be resolved by the deterministic order $Ord$ (given by Definition
2).

Compared to [6], we only change the commit rule. This new commit rule enables
the node to pre-compute the votes for each transaction before the consensus
decides the leader. We present Theorem 1 in the center of our proposal
correctness. Here, a node observes a transaction when a proposal that contains
that transaction has been added to its DAG.

###### Theorem 1

When a node added a proposal $p$ to its DAG at an odd round $r$, if a
transaction $tx$ has more than $2f+1$ votes from nodes and no valid
conflicting transactions were observed, then $tx$ will eventually be committed
as a successful transaction according to Definition 3.

###### Proof:

Recall that Definition 3 states that a transaction that has been included in
more nodes earlier than other conflicting transactions will be committed, and
the consensus layer commits a leader proposal only if $f+1$ proposals have
included it in the next odd round.

Firstly, we demonstrate that the transaction will eventually be committed. As
there are at least $2f+1$ nodes whose proposals indicate they have voted for
the transaction $tx$, any proposal at round $r+1$ will contain the
transaction. Thus, $tx$ will be committed by some proposal eventually.

Next, we show this transaction will be committed successfully. If any proposal
is to be committed before round $r$, it must have $f+1$ subsequent proposals,
and thus, it will be in the sub-DAG starting from $p$. Hence, the node will
observe any valid conflicting transaction that can be committed before round
$r$. If a proposal $p^{\prime}$ after round $r$ is selected as a leader, then
its sub-DAG will have at least $2f+1$ proposals from round $r$, which implies
that at most $f$ nodes will vote for conflicting transactions while at least
$f+1$ will vote for $tx$. According to our commit rule, $p^{\prime}$ can only
commit $tx$. ∎

A proposal in an even round cannot trigger fast-commit since its vote on that
round may not impact the leader’s choice in the same round. The leader may
encounter a tied vote in its sub-DAG case and commit a different transaction.
According to Theorem 1, we can define the fast commit rule.

######  Definition 4 (Fast Commit Rule)

A transaction is fast committed with a successful result at an odd round if
$2f+1$ nodes have voted it and no valid conflicting transactions are observed.

This fast commit rule is derived from our new commit rule and Theorem 1, which
does not affect the security claim of Tusk. Estimating the expected latency
reduction using this fast commit rule is non-trivial. According to our
experiments in section V, we can reduce about half of the transactions’
latency by 50%, i.e., an average 25% latency reduction.

###  III-D Our Construction: Board and Clerk

We propose a new consensus algorithm called “Board and Clerk” to replace Tusk
for applying our new commit rule. At a high level, Board decides on
transaction results and fast-commit transactions, and Clerk agrees on the
formal commitment. The algorithm operates as follows: After Narwhal commits a
proposal, Board counts the votes from that proposal, keeps it in storage, and
fast commits transactions if possible. Once the algorithm reaches the commit
rule (_i.e._ when processing a proposal of even round $r>4$), Clerk uses a
global coin to select the leader. If the leader is valid according to the DAG,
Clerk will output all uncommitted proposals from the leader’s sub-dag, and
Board can compute the transaction result accordingly for commitment.

Board stores all the vote results and conflict information. More specifically,
Board stores a map of {transaction Id: vote record} and a map of {batch: vote
record}. Each vote record is a hash map between {node Id: round} that records
the round number that a node voted for the element (transaction or batch). We
use Board.AddTxVotes and Board.AddBatchVotes functions to denote updating the
vote (insert the round for the node ID).

Board provides two open APIs: first, when a new proposal is added to the DAG,
Board counts votes for the author node. Since proposals are added to the DAG
after its ancestors, the first vote from a node to an element is always
smaller than the later votes from that node to the same element. Algorithm 1
highlights the flow for counting transactions’ votes, which triggers the fast
commitment channel.

Algorithm 1 Algorithm for counting transaction votes

1:Proposal P

2:function Board.Process(P)

3: Initiate list B

4: P.round $\rightarrow$ round

5: P.author $\rightarrow$ voter

6: for batch in P.batches do

7: if !Board.HaveSeen(batch) then

8: add the batch in B

9: end if

10: end for

11: for batch in B do

12: for tx in batch do

13: Board.Add(tx.txos, tx)

14: if Any TXO has more than one tx then

15: Add tx to conflicted set

16: end if

17: end for

18: Board.AddTxVotes(batch.txs, voter, round)

19: end for$\triangleright$ Counting Votes for sub-dag proposal

20: P.parents $\rightarrow$ C

21: while C is not empty do

22: C.Pop() $\rightarrow$ parent

23: Board.AddBatchVotes(parent.batches, voter, round)

24: if any vote changed then $\triangleright$ new batch

25: C.Concat(parent.parents)

26: Board.AddTxVotes(batch.txs, voter, round)

27: end if

28: end while

29: if round is odd then $\triangleright$ Fast Commit

30: Filter out transactions that are not conflicted and have more than 2f+1
votes.

31: Fast commit those transactions

32: end if

33:end function

To aid the decision process of transaction states, we utilize internal states.
To achieve this, we require the storage of node votes for different batches
and transactions, with the added benefit of serving as a shortcut to avoid
duplicated batches. Additionally, we must maintain records of conflicting
transactions and the existing TXO-TX pairs, thus preventing the missing of any
vital information regarding conflicts. To ensure smooth operation, we also use
a cache to store transactions fast-committed to reject later conflicting
transactions.

The second API for the Board is triggered when Clerk commits a sub-DAG by the
consensus, resulting in Board committing all transactions in the sub-DAG as
required. Since the consensus algorithm only decides the leader for the
previous round, we cannot directly use the latest vote counts, which include
votes that are not to be committed. To avoid recounting votes, we define a
frontier for each proposal.

###### Definition 5

A frontier $F$ of a proposal $p$ is a map between node IDs and their latest
proposal round in the sub-DAG that begins with $p$.

We can remove the vote records after the corresponding round in the frontier
since the current commitment will not include those vote records. The flow for
counting transaction results is outlined in Algorithm 2.

Algorithm 2 Algorithm for getting transaction results of a sub-DAG

1:A list of proposals P

2:A set of successful transactions ST and a set of failed transactions FT

3:function Board.Commit(P)

4: Init empty ST, FT

5: Set T as a list of all uncommitted TXs in the sub-DAG of P

6: Board.ConflictedTX() $\longrightarrow$ CT $\triangleright$ CT is the
dictionary of conflicted TXO and its conflicted transaction pair according to
TXO-TXs

7: T.IntersectWith(CT.values) $\longrightarrow$ TxToProcess

8: if TxToProcess = $\phi$ then $\triangleright$ We can directly commit all as
success

9: ST.Add(T)

10: Return ST, FT

11: else

12: ST.Add(T.Except(TxToProcess))

13: end if

14: Set M as a map of $<$TXO,TX$>$ with values from TxToProcess

15: M.sortbyKey() $\triangleright$ use a stable sort

16: Compute frontier $F(P)$

17: for (txo,txs) in M do

18: Prune transaction vote records by F and remove vote records from nodes
that are not earliest.

19: Sort txs with vote counts and $Ord$

20: Push the first tx in txs to ST and the remaining to FT

21: for (txo’, txs’) in M do $\triangleright$ We need to check if other
conflicted sets have been affected by this result

22: if tx contains txo’ then

23: Push other tx’ in txs’ to FT

24: end if

25: txs’ = txs’.disjoint(txs)

26: end for

27: end for

28: Fast Commit other transactions according to ST, FT $\triangleright$ Some
transactions might meet the fast commit rule by now, (_e.g._ , the conflicted
$tx$ is failed) or it is not processed now but doomed to fail (_e.g._ , the
conflicted $tx$ is succeeded now)

29: Board.CleanUp

30: Return ST, FT

31:end function

###  III-E Theoretical Analysis

This work inherits the adversary model from Tusk [6]. Given $n$ parties in an
asynchronous network of our consensus algorithm, a computationally bounded
adversary can corrupt up to $f<n/3$ parties, denoted as faulty nodes. Our
protocol shares the same rule for committing leader block as Tusk [6], which
allows our protocol to have the same security and liveness claim. The
transaction result is determined by Algorithm 2, which is deterministic
according to the sequence of the leader block. Therefore, our protocol is as
secure and live as Tusk [6].

Compared to Tusk, our protocol introduces additional computation and storage
costs to reduce the latency of fast-committed transactions. Generally, Board
needs an additional space linear to the number of transactions for storing
votes. Algorithm 1 requires vote updating for each batch and transaction,
which is linear to the number of nodes $N$ given the transaction number is
also linear to the number of proposers. Algorithm 2 introduces a computation
overhead of $O(m^{2})$ for $m$ conflicted transactions. This overhead is
negligible since $m$ is relatively small compared to the total transaction
number. Some additional trade-off between computation and storage is possible.
For example, in Algorithm 1, we use additional batch votes to filter out
transactions with new votes. When committing proposals. Nodes running our
protocol need more memory and computation power than Tusk. In the experiment
section (Figure 6), we will see the formal block latency of our protocol has
little difference with Tusk if the computation and memory are not the
bottlenecks.

##  IV Hyper-Block Model

Our second proposal is a Hyper-Block Model that allows for generating proofs
for transaction results. Our solution adheres to the architecture demonstrated
in Figure 1 and integrates the fast-commit rules from Definition 4. Previous
DAG-based consensus protocols focus on creating consensus by ordering
transactions such that proof of whether transactions were included in the DAG
and which conflicting transactions succeed or fail is available only after a
DAG is formed. The purpose of the Hyper-Block model is to create such proof
for the status of a transaction in parallel to form the DAG, thus reducing the
latency between the commitment and the inclusion of a transaction in the
consensus. Note that our approach does not produce any communication overhead
such that its impact on the performance of DAG creation is minimal.

At a high level, a hyper-block consists of three parts: 1) proof of
leadership, 2) a commitment to batches in the sub-DAG, and 3) a commitment to
the failed transaction set. The consortium will sign all contents to enable
any client to use the hyper-block and verify whether its transaction is
correct. The commitment of the set can be any proper cryptographic aggregator
that satisfies the requirements. Specifically, each proof of transaction
result contains three parts.

  * •

Block membership: Proof that the transaction is in a batch contained by a
hyper-block;

  * •

Result Proof: A demonstration of whether the transaction is a member or non-
member of the corresponding failed transaction set in the hyper-block;

  * •

Leadership Proof: Proof of leadership for the protocol.

The primary technical challenge arises from preparing the hyper-block without
disrupting the consensus protocol, which only decides the leader proposal
index. To overcome this problem, we need to accomplish two tasks: Firstly, we
need to obtain the transaction results to commit the failed transactions.
Secondly, we must ensure that byzantine nodes cannot forge a hyper-block that
validates a failed transaction.

We propose two strategies to achieve this: 1) A blocking strategy that
synchronizes the DAG and consensus layers to execute a process similar to a
view-change in other BFT protocols, and 2) a non-blocking strategy that
commits all possible and valid output paths through the consensus algorithm.

Here we list some sub-functions we use in our blocking and non-blocking
algorithms, along with implementation remarks:

  * •

MakeProposal: Take a round $r$ as inputs and return a proposal $p$ that
patches at least $2f+1$ proposals from the previous round and a bundle of
batches received from its workers;

  * •

TakeLeader: Take a round $r$ as inputs, await the consensus layer output the
leader of round $r$. If the leader is not in the DAG, recursively outputs the
latest leader in the DAG;

  * •

SimulateCommit: Take a proposal and the previous leader as input. It outputs a
list of committed batches and a set of failed transaction IDs. The flow is
almost the same as Algorithm 2 without side effects, thus should be
implemented as a function of Board;

  * •

CommitList: Take a list as input and return one value as output commitment. It
can be implemented as a cryptographic accumulator that supports both
membership and non-membership proof;

  * •

AttachWitness: Including some witnesses to a proposal $p$ for acquiring
signatures.

Now, we thoroughly detail both strategies.

###  IV-A The Blocking Strategy

The blocking strategy modifies the clerk consensus algorithm and proposes
rules. For the consensus algorithm, if the first proposal of an odd round of
$r\geq 5$ is added to the DAG, the consensus layer will automatically trigger
the protocol to select the leader for the round $r-1$.

Secondly, when the proposer initiates a proposal for any even round of
$r+1>4$, it will first collect batches and wrap them properly. Next, the
proposer will block the proposal and await the selection of a leader from
round $r-1$. After the proposer becomes aware of the selection of the round
leader, it will simulate the transaction results of its proposal as if this
proposal is committed to the future leader. This simulation will compute the
corresponding failed transaction commitment and batch set commitment.
Subsequently, the two commitments are wrapped together with the proposal and
dispatched to the broadcast phase. The flow for the proposing process is
presented in Algorithm 3.

Algorithm 3 Blocking algorithm for proposing

1:Round $r$

2:Proposal $p$ for round $r$

3:function Proposer.Proposing($r$)

4: MakeProposal($r$) $\longrightarrow p$

5: TakeLeader($r-2$).await() $\longrightarrow L$

6: Board.SimulateCommit($p,L$) $\longrightarrow(B,F)$

7: CommitList($F$) $\longrightarrow wf$

8: CommitList($B$) $\longrightarrow wb$

9: AttachWitness($p$,$wb,wf$)

10: Return $p$

11:end function

Upon receiving the proposal from the other nodes, the initial action is to
verify the DAG history and confirm the correct calculation of the failed
transaction commitment. Confirmation is done by signing the proposal ID, the
commitment of failed transactions, and the commitment of batch set. The signed
information is used to generate the certificate of the proposal in the DAG.
Once the proposal is successfully committed to a leader, each node
independently assembles the hyperblock by fetching this signature and the
output of the consensus layer.

Our blocking strategy does not affect the security claims of the Tusk
algorithm, as the election process is independent.

###### Remark 1

The counting process can be accelerated for efficiency by utilizing dynamic
programming methods to cache the votes for conflicted transactions (M in line
13 of Algorithm 2). The cached outcome can later be removed after the
commitment of corresponding leaders.

###  IV-B The Non-Blocking Strategy

In an asynchronous network setting, waiting for the consensus layer results in
the blocking strategy may not be tolerable. Therefore, we propose a non-
blocking strategy to minimize the potential delays due to the network.

We use a commit and prove flow technique to create the hyperblock in the non-
blocking strategy. The proposer maintains a leader DAG by the present DAG. The
difference is that the leader DAG comprises proposals only for even rounds
(_i.e._ , rounds for selecting leaders). Every two proposals are connected
only if they are connected in the DAG. Moreover, whenever a leader is chosen
for a round $r$, the proposals other than the selected one are removed from
the leader DAG instantaneously. The leader DAG can be seen as comprising all
the probable leader proposals of the current DAG.

In the leader DAG, we store batch and failed transaction commitments. Each
proposal has a vector for these two commitments; every position in the vector
reflects a path in the leader DAG from the current proposal to the previously
committed leader (if the leader is not in the DAG), given that the
corresponding proposals on the path are chosen as the leaders for the
corresponding rounds.

Figure 4 shows an instance of a leader DAG and its verification path based on
the consensus layer results. When proposing for round 10, we assume the
leaders of round 4,6 are known(checked), and the leader of round 8 is unknown
(question marked). The new proposal at round 10 has four possible cases for
the round leader at round 8. It will create corresponding commits and form
them as a vector for proposing. For proposals at round 8, which already know
the leader of round 6 (checked), Node 2 will contain a commitment for it and
be used by the proposer in round 10. On the other hand, Node 3 has not yet
seen proposals 2-6, so its commitment to the older leader 1-4 (checked) will
be used for proposing. If the 2-8 is the eventual new leader, the black line
represents the commitments that all users eventually use.

Figure 4: An example of a leader DAG. The dark line represents the path of
final commitment, and the gray lines represent the candidates’ paths during
proposing.

We require that a leader DAG supports the following functions: First,
Candidates($r$) returns a list of candidates leaders for round $r$. If the
leader is not selected, it should be all proposals in round $r$ plus
Candidate($r-2$) in a recursive way. Second, Add($p,V$) adds the proposal $p$
to the leader DAG with a vector $V$ of commitment of batches and transactions.
In addition, the leader DAG should also support some clean-up functions to
remove non-leader or committed proposals accordingly.

The proposal contains the vector created according to the paths of the leader
DAG. After receiving a proposal, a node verifies the vector and then commits
it as a Merkle tree, sending the root’s signature as evidence back to the
proposer. This evidence, along with the consensus layer output, will
eventually be used to verify the correctness of the batch commitment and the
failed transactions commitment made by the node if this proposal is the
leading one in the future. Algorithm 4 outlines the proposal procedure in the
non-blocking strategy.

Algorithm 4 Non-Blocking algorithm for proposing

1:Round $r$, Leader DAG $LD$

2:Proposal $p$ for round $r$

3:function Proposer.Proposing($r,LD$)

4: MakeProposal($r$) $\longrightarrow p$

5: Initiate a vector $V$

6: for $L$ in $LD$.candidates($r-2$) do

7: Board.SimulateCommit($p,L$) $\longrightarrow(B,F)$

8: CommitList($F$) $\longrightarrow wf$

9: CommitList($B$) $\longrightarrow wb$

10: $V$.Push($wf,wb$)

11: end for

12: $LD$.Add($p,V$)

13: AttachWitness($p$,$V$)

14: Return $p$

15:end function

###  IV-C Theoretical Analysis

Both strategies only add one commitment for successful and failed transactions
to the proposal. Narwhal will collect sufficient signatures for the proposal,
including this commitment, so nodes can prove the result of arbitrary
transactions through this commitment(_e.g._ , proving a transaction has a
valid open to the successful or failed set). In the non-blocking strategy, the
prover must provide additional proof of the previous leader since it commits
all possible results for different leaders.

Since both strategies are deterministic processes, each proposal’s
communication overhead is just $O(1)$. Algorithm 2 dominates the computational
complexity of both the blocking and non-blocking strategies. For the blocking
strategy, it should be noted that this process triggers at least $2f+1$
simulations during the RBCs phases of each round. However, the result can be
cached for the formal commit process. Unlike the blocking strategy, the non-
blocking strategy involves a polynomial scale of possible paths to commit.
However, in practice, if the leader of round $r-4$ is evident by round $r$,
the proposer needs to calculate at most $2f+2$ possibilities for its vector,
given that each proposal’s commitment at round $r-2$ is already confirmed.
Thus, the total computation cost for each leader round is at most $O(n^{2})$
in this case.

###### Remark 2

Practically, we can hybrid non-blocking and blocking strategies. We can safely
choose the non-blocking strategy when there are no or limited conflict
transactions. Once the conflicted transaction increases, a blocking strategy
can cool down the proposing phase and reduce the computation overhead.

##  V Implementation and Evaluation

In this section, we estimate the latency reduction of our Board and Clerk
scheme and compare it with existing protocols. The Hyper-Block Model is
omitted since it is a pure gain of function that relies on heavier local
computation. The main target of our experiment is to demonstrate how fast
commit rule can affect the latency under different TPS, number of nodes, and
number of faulty nodes. Since our scheme does not introduce communication
overhead, we can estimate all these factors in a cheaper local testbed
experiment. We have implemented Board and Clerk based on the code base of
MystenLabs[16].

Our implementation solely modifies the local execution flow without
introducing additional communication costs. Thus, we only perform local tests
to evaluate the latency reduction achieved by our algorithm. Our Clerk
algorithm follows the original Tusk to commit the block [6]. To compare the
results, we analyze the performance of our algorithm against Tusk’s and
Bullshark’s [19]. Bullshark is a variant of Tusk optimized for the partial
synchronous setting.

The simulation was conducted on a desktop machine with an Intel i7-13700K CPU,
32GB DDR5 memory, and 2TB SSD storage. We test different TPS for a 4-node
system, and Figure 5 illustrates our latency reduction in both the
asynchronous setting (top), where $\Delta$ is unknown, and the partial-
synchronous setting (bottom), where it is known and used as the timeout
parameter. In Figure 5, the latency is measured by the end-to-end time between
the client’s submission of transactions and the node processing them and
updating the state. The clerk (block marked) line shows the latency of
transactions that are not fast-committed. The clerk-fc (plus marked) line
shows the latency of fast-committed transactions.

Figure 5: TPS-Latency graph (top: asynchronous setting, bottom: partial
synchronous setting).

We draw two observations from this result: First, our algorithm keeps the
regular commitment time compared to the original Tusk protocol. In addition,
our fast commitment channel reduces the latency by nearly 50%, outperforming
even the Bullshark protocol in partially synchronous settings. We observe this
50% latency reduction even when increasing the number of nodes. This reduction
is near-optimal because the vote-based BFT consensus needs at least $3$
rounds. Given that Tusk’s average latency is $7$ rounds, and our scheme only
commits on odd rounds, 50% latency reduction is near optimal.

Second, our algorithm reaches the computation power bottleneck earlier than
other protocols. It happens at an estimated 64K input TPS. This is attributed
to the increased metadata handling and transaction commitment on Board. In
Figure 5, this bottleneck manifests as a latency increase at the rightmost
point for the orange and red curves. Despite this, our additional load yields
substantial gains in reduced latency and check of external validity, which
Tusk and Bullshark will accomplish afterward. We predict that realistic
network delay and node capability make this bottleneck more challenging.
Considering that TPS does not affect our metrics, the following tests used a
load of 200 TPS to reduce the computation load.

The fast-commitment rate, defined as the ratio of fast-committed transactions
to all transactions, is another significant metric for our scheme. Although
not depicted in Figure 5, the fast-commitment rate remains steady at
approximately 50% of all transactions until reaching the computational
bottleneck. This outcome aligns with our expectation that the fast-commitment
rate should correlate solely with the network topology, _i.e._ , the committee
size and number of faulty nodes.

The scalability test in Figure 6 offers an alternative perspective by varying
the number of nodes. Generally, the fast-commitment rate positively correlates
with the maximum $f$ and slightly negatively correlates with $N$. When
$N\in\\{4,5,6\\}$, we have $f=1$, and the fast-commitment rate is around 50%
of all transactions. While $N\in\\{7,8,9\\}$, we have $f=2$, which greatly
improves the fast-commitment rate to a level of around 70% of all
transactions. This is because these additional nodes in the system may not
contribute to leader selection but still help to increase the number of
transaction votes.

Figure 6: Formal latency and fast-committed rate changed according to the
number of nodes.

The faulty node test depicted in Figure 7 provides the most compelling
evidence. In this test, we gradually shut down nodes within an 8-node system.
It was observed that the fast-commitment rate gradually decreased in response
to node shutdowns. Ultimately, the rate reached zero, indicating that no
transactions could employ the fast commitment channel when nodes reach
consensus every two rounds. We omit simulation for Byzantine faulty nodes.
This is because the reliable broadcast protocol in the Narwhal memory pool
will not accept proposals from byzantine nodes. Therefore, byzantine nodes are
the same as crashed nodes for Board and Clerk.

Figure 7: Formal latency and fast-committed rate changed according to the
number of faulty nodes.

The scalability test shows that the latency of Clerk’s formal commitment
escalates more rapidly than that of the Tusk algorithm when scaling nodes.
This outcome is anticipated, given that Board must manage an increased volume
of votes and the corresponding counting process. It is also noteworthy that
dummy transactions, which may be introduced due to concerns about Byzantine
nodes, can further reduce the fast-commit latency as more proposals will
include the transaction and increase the number of votes. Last, our Clerk
implementation is a modification on Tusk for asynchronous settings. However,
we can also use the partial synchronous setting and implement Clerk, based on
Bullshark, reducing the latency of non-fast-committed transactions while
keeping our fast-commitment channel advantages.

##  VI Conclusion

In our research, we introduce a new method for improving the latency of the
Narwhal-based consensus algorithm. We propose the Board and Clerk Protocol as
an efficient consensus algorithm for blockchain-aided systems that rely on the
UTXO Model. Our algorithm’s foundation is a novel commit rule, combined with a
fast-commitment channel, which collectively can reduce the latency of a
minimum of 50% of transactions without incurring additional communication
overhead. Our performed experimental results indicate that our protocol
effectively leverages redundant nodes and transactions to minimize latency.
Given that this redundancy originates from security requirements, the latency
reduction essentially incurs without extra costs if the node computational
power is not a limiting factor.

Furthermore, we outlined two strategies for achieving verifiable transaction
outcomes without necessitating an increase in communication rounds. We regard
this characteristic of our research as a crucial feature that a public
blockchain system based on a consortium should support.

Lastly, we hope our proposal may motivate researchers to explore the
possibility of using the underlying data model to augment consensus algorithms
akin to our UTXO-enhanced consensus algorithm.

## Acknowledgment

This work was sponsored by JST SPRING, Grant Number JPMJSP2108; JSPS KAKENHI,
Grant Number JP23KJ0385 and JP21K11882; JST CREST, Grant Number JPMJCR2113.

## References

  * [1] M. Ben-Or, B. Kelmer, and T. Rabin, “Asynchronous secure computations with optimal resilience (extended abstract),” in _Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing - PODC ’94_. ACM Press, 1994, p. 183–192.
  * [2] E. Bortnikov, M. Gurevich, I. Keidar, G. Kliot, and A. Shraer, “Brahms: byzantine resilient random membership sampling,” in _Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing_ , ser. PODC ’08. Association for Computing Machinery, 2008, p. 145–154.
  * [3] G. Bracha and S. Toueg, “Asynchronous consensus and broadcast protocols,” _Journal of the ACM_ , vol. 32, no. 4, p. 824–840, 1985.
  * [4] M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” _ACM Transactions on Computer Systems_ , vol. 20, no. 4, p. 398–461, Nov 2002.
  * [5] M. M. T. Chakravarty, J. Chapman, K. MacKenzie, O. Melkonian, M. Peyton Jones, and P. Wadler, “The extended utxo model,” in _Financial Cryptography and Data Security_ , ser. Lecture Notes in Computer Science, vol. 12063. Springer International Publishing, 2020, p. 525–539.
  * [6] G. Danezis, L. Kokoris-Kogias, A. Sonnino, and A. Spiegelman, “Narwhal and tusk: a dag-based mempool and efficient bft consensus,” in _Proceedings of the Seventeenth European Conference on Computer Systems_ , Mar 2022, p. 34–50.
  * [7] B. David, P. Gazi, A. Kiayias, and A. Russell, “Ouroboros praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain,” in _Advances in Cryptology – EUROCRYPT 2018, Part II_ , ser. Lecture Notes in Computer Science, J. B. Nielsen and V. Rijmen, Eds., vol. 10821\. Tel Aviv, Israel: Springer, Heidelberg, Germany, Apr. 29 – May 3, 2018, pp. 66–98.
  * [8] S. Duan and H. Zhang, “Foundations of dynamic bft,” in _2022 IEEE Symposium on Security and Privacy (SP)_ , May 2022, p. 1317–1334.
  * [9] C. Foundation, “Cardano Hub,” https://www.cardano.org/, 2018, [Online; accessed 28-March-2018].
  * [10] B. M. Kapron, D. Kempe, V. King, J. Saia, and V. Sanwalani, “Fast asynchronous byzantine agreement and leader election with full information,” _ACM Transactions on Algorithms_ , vol. 6, no. 4, pp. 68:1–68:28, Sep 2010.
  * [11] I. Keidar, E. Kokoris-Kogias, O. Naor, and A. Spiegelman, “All you need is dag,” in _Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing_ , ser. PODC’21. Association for Computing Machinery, Jul 2021, p. 165–175.
  * [12] L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” _ACM Trans. Program. Lang. Syst._ , vol. 4, no. 3, p. 382–401, jul 1982\.
  * [13] C. Liu, S. Duan, and H. Zhang, “Epic: Efficient asynchronous bft with adaptive security,” in _2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_ , Jun 2020, p. 437–451.
  * [14] Y. Lu, Z. Lu, Q. Tang, and G. Wang, “Dumbo-mvba: Optimal multi-valued validated asynchronous byzantine agreement, revisited,” in _Proceedings of the 39th Symposium on Principles of Distributed Computing_ , ser. PODC ’20. Association for Computing Machinery, Jul 2020, p. 129–138.
  * [15] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The honey badger of bft protocols,” in _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’16. Association for Computing Machinery, Oct 2016, p. 31–42. [Online]. Available: https://doi.org/10.1145/2976749.2978399
  * [16] mystenLabs contributors. (2023) Narwhal. [Online]. Available: https://github.com/MystenLabs/narwhal
  * [17] S. Müller, A. Penzkofer, N. Polyanskii, J. Theis, W. Sanders, and H. Moog, “Reality-based utxo ledger,” _arXiv:2205.01345_ , May 2022, arXiv:2205.01345 [cs]. [Online]. Available: http://arxiv.org/abs/2205.01345
  * [18] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” _Decentralized Business Review_ , p. 21260, 2008.
  * [19] A. Spiegelman, N. Giridharan, A. Sonnino, and L. Kokoris-Kogias, “Bullshark: Dag bft protocols made practical,” in _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , ser. CCS ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 2705–2718.
  * [20] X. Sui, S. Duan, and H. Zhang, “Marlin: Two-phase bft with linearity,” in _2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)_. IEEE, Jun 2022, p. 54–66. [Online]. Available: https://ieeexplore.ieee.org/document/9833790/
  * [21] G. Wood, “Ethereum: A secure decentralised generalised transaction ledger,” _Ethereum project yellow paper_ , vol. 151, pp. 1–32, 2014.
  * [22] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, “Hotstuff: Bft consensus with linearity and responsiveness,” in _Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing_ , ser. PODC ’19. Association for Computing Machinery, Jul 2019, p. 347–356.
  * [23] H. Zhang and S. Duan, “Pace: Fully parallelizable bft from reproposable byzantine agreement,” in _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security-CCS22_ , 2022, p. 23.


# Method for tilt correction of calibration lines in high resolution spectra

Tanya Das  Indian Institute of Astrophysics, Bangalore, India  University of
Calcutta, JD-2 Salt Lake, Kolkata 750098, India  Corresponding author:
<EMAIL_ADDRESS>Ravinder K. Banyal  Indian Institute of Astrophysics,
Bangalore, India

###### Abstract

Technological advancement has led to improvement in the design capabilities of
astronomical spectrographs, allowing for high precision spectroscopy, thereby
expanding the realms of observational astronomy. High-resolution spectrographs
use Echelle grating that operates in higher orders, giving more detailed
spectra. Often, curvature and tilted lines are observed in the spectra,
arising due to the design trade-offs of the respective spectrographs. Removal
of these artifacts can help avoid wrong flux calculation and line centroid
position misinterpretation, which can aid in a better prediction of the
wavelength calibration model. In this paper we present a post-processing
technique that we developed to correct the observed curvature and tilt in the
spectra. We have demonstrated the correction technique on Fabry-Perot and Th-
Ar calibration spectra obtained from Hanle Echelle Spectrograph (HESP),
Magellan Inamori Kyocera Echelle (MIKE) spectrometer and X-shooter
spectrograph.

††journal: ao

##  1 Introduction

Spectroscopy is a key method for monitoring and analyzing the physical and
chemical properties of astronomical objects. Measurement of the dark matter
content of galaxies and their clusters [1], estimation of the mass of stellar
systems [2], determination of the age of stars [3], identification of chemical
composition, temperature and other parameters by studying the strength of
spectral features [4] and radial velocity measurements to determine the
presence of planets around stars [5] are the primary fields of application for
spectroscopy.

Spectrographs are instruments used to observe the spectrum of astrophysical
objects. Usually, conventional low-resolution spectrographs are compact and
light weight. They are directly attached to Cassegrain focus of the telescope
behind the primary mirror. The direct interface with telescope makes it easier
to focus the star light directly onto the spectrograph slit. However, high-
resolution Echelle spectrographs (typically $R\gtrsim 50,000$) tend to be
bulky and require larger space. In such cases, spectrograph is decoupled from
the main telescope and placed on a stable Nasmyth platform or sometimes housed
in a separate room. A tertiary mirror can be used to steer the telescope beam
onto the Nasmyth focus. Alternatively, fibers are deployed to collect the
light from telescope focal plane and deliver it to the spectrograph slit. A
diverging beam from the slit is collimated and then passed onto the dispersing
element. A diffraction grating is used in most spectrographs to disperse the
light from the target object into its component wavelengths. A collimated beam
incident on the grating ensures that different wavelengths are dispersed at
distinct angles. The camera optics then focuses the dispersed light on to a
charged coupled device (CCD), where it is recorded for further analysis.

In contrast to their low-resolution counterparts, high-resolution
spectrographs employ Echelle grating for use in higher diffraction order,
thereby providing more details about spectral features and giving resolution
up to R = 150,000. Echelle gratings have large blaze angles, typically between
50∘-75∘, providing dispersion at higher angles, and optimized to concentrate
maximum efficiency in a specific direction. At higher orders, they offer
substantial overlap, causing the longer wavelength of a higher order to
overlap with the following order’s shorter wavelength. A cross disperser, like
a prism or a grating, is used to separate the overlapping orders in spatial
direction to achieve a wider spectral coverage.

Stellar spectra consist of both absorption and emission lines, whose precise
position is determined by converting the pixels into the wavelength scale.
This step is described as wavelength calibration, which utilizes known
laboratory sources such as Th-Ar or advanced techniques such as Fabry-Perot
(FP) etalon [6], Iodine cell [7], and laser frequency comb [8].

The benefits provided by echelle spectrographs also come with some
shortcomings and design constraints. In order to accommodate the spectra
effectively on the detector, optical components, such as slit or camera, are
often adjusted, leading to the introduction of artifacts and aberration like
distortion, defocus and tilted lines. The grating also introduces an out-of-
plane gamma angle, along with cross disperser prism, which induces tilt in the
spectral lines [9]. Neglecting these factors may lead to addition of errors.

The tilt in calibration and spectral lines is also introduced by imperfections
resulting from various trade offs in the spectrograph design. Curvature in the
spectrograph orders can arise due to the cross disperser, whose dispersion
direction is perpendicular to the Echelle grating. The tilt in individual
lines in the spectrum are caused due to the cross disperser and Echelle
grating working on two different planes (operating in quasi-Littrow mode).
Generally, the binning of data is done normal to the dispersion axis, and
hence if the tilt in spectral lines is not considered, the resulting 1D data
may show an increase in the FWHM of the lines and also cause blending in some
cases. This is because, in the case of tilted lines, the intensity is
distributed over several pixels, which, when binned along the slit direction,
gives a broadened line and wrong flux values, as shown in figure 1. The
broadened spectral line also results in the degradation of spectral
resolution. The tilt in the slit image at the detector is a function of
wavelength [10]. It also compromises the attainable accuracy in RV
measurements if not adequately taken care of or modelled out by the extraction
software [11]. Disentangling the tilt related shifts in line centroid position
from the RV shift is essential for RV studies. The point spread function (PSF)
is predominantly the response of the instrument to a monochromatic light or a
point source. The instrumental aberrations of the system already broaden the
energy distribution in the PSF. The tilt is an artifact of the system, which
causes further broadening of the line. Removal of this artifact can hence
facilitate the effort of predicting instrument PSF by removing one of the
dependent factors, in cases where it is necessary to generate a PSF map of the
instrument and its variation during an observation run. Measuring the tilt can
also help in the study and estimation of instrument aberrations, for example,
a better prediction of distortion in the system.

Figure 1: A cartoon depicting the effect of tilt on the FWHM of the lines.

In this paper, we are using FP and Th-Ar calibration data to assess and remove
the tilt and curvature being introduced by the instrument. Since FP is a
stable source that provides several continuous lines of equal intensity, it
helps in better estimation and elimination of these artifacts, thereby
resulting in a better prediction of the wavelength calibration model. We have
designed and developed an FP based wavelength calibration system [12]. The
system was tested on Hanle Echelle Spectrograph (HESP), where the artifacts of
the instrument often show up in the FP spectra. Spectrographs like Magellan
Inamori Kyocera Echelle (MIKE) spectrometer [13] and X-shooter [14] show
highly tilted spectral lines due to the quasi-Littrow configuration. The tilt
removal algorithm developed as part of this study has been tested on X-Shooter
and MIKE Th-Ar calibration data. A general review of the existing methods
adopted for curvature and tilt correction in Echelle spectra is presented in
2. The proposed methodology and algorithm are described in section 3. Results
from the correction algorithm have been presented in section 4 followed by a
summary of this work in section 5.

##  2 Review of existing techniques for tilt and curvature removal

In order to obtain calibrated science quality data, the two-dimensional
spectrograms obtained from the spectrograph have to be processed and the
spectrum extracted. Software like IRAF [15, 16] can be used for general
reduction purpose. Many spectrographs have dedicated state of the art pipeline
for preparation and reduction of the 2D spectra. A brief description of the
method adopted in X-Shooter and MIKE pipeline will be discussed in this
section, along with a new algorithm called PyReduce developed for the same
purpose.

Figure 2: Zoomed in Th-Ar calibration spectra from X-shooter showing highly
curved orders along with large tilt in spectral lines.

X-Shooter is a single target spectrograph of medium resolution (R$\sim$
4000-17000), installed at the Cassegrain focus of ESO’s Very Large Telescope
(VLT) [17]. The output of this spectrograph consists of highly curved orders
with tilted spectral lines, shown in figure 2. Due to this, special measures
are taken for wavelength calibration and optimal extraction of the spectra, as
described in [18, 19]. X-Shooter pipeline is written in ANSI C. Separate
pinhole mask arc frames are taken for computation of initial guess for
wavelength solution and determine spatial and wavelength scale calibrations. A
polynomial interpolation, constructed using multi-pinhole frame, is used for
transforming detector coordinates into a function of wavelength (determined by
the guess solution), order number and position on the slit that allows the
removal of order curvature and line tilts. The physical model of the
instrument can also be used to determine the wavelength position on detector.
Finally, the detector pixels are oversampled in 2D and linear interpolation is
used to find the slit profile which is then collapsed over user defined slits.
A detailed description of the entire pipeline can be found in [20].

The Magellan Inamori Kyocera Echelle (MIKE) is a high resolution, double
echelle spectrograph installed on the Magellan II telescope at Las Campanas
Observatory, Chile. Figure 3 shows the Th-Ar calibration spectra as captured
in the red arm for a slit size of 0.7 inches. A dedicated pipeline is
available for data reduction [21] using IDL with a Python alternative. After
the standard image processing involving overscan removal and flat fielding, a
2D wavelength image is generated by using Th-Ar arc frame to derive a 1D
wavelength solution along the center of each order. For each order, the high
SNR arc lines are identified and their tilt is measured as a function of
wavelength and echelle order. The centroid of each line is traced across the
order and best fit line for each arc line is used to calculate the slope. A 2D
Legendre polynomial is fit to the calculated slopes for every order and the
slope values interpolated from the solution for areas with less density of Th-
Ar lines. A unique wavelength is assigned to the center of all the pixels
falling within the echelle order by using the derived wavelength solution and
the arc line tilts. This is done across full CCD pixels and a wavelength image
is generated which is finally used in the optimal extraction of the orders. A
similar method is adopted by MAGE Spectral Extractor (MASE) [22].

Figure 3: Zoomed in Th-Ar calibration spectra from red channel of MIKE at 0.7"
slit setting, showing tilted lines.

The new REDUCE package [23] adds to the earlier version of the developed
package [24] by incorporating tilted and curved slit images. The method
follows a slit decomposition algorithm, where the 2D image of the spectral
order is represented by slit illumination and spectrum, sampled on the
detector. The shape of slit image is modelled by taking strong and unblended
emission lines in a wavelength calibrated spectrum and fitting a 2D Gaussian
to each of the line image. The tilt and curvature variations across the order
is combined by fitting a polynomial and interpolating to all the columns.
Optimal extraction is then performed keeping in mind the calculated tilt and
curvature.

HESP is a high-resolution general purpose spectrograph installed on the 2m
Himalayan Chandra Telescope (HCT), located at Indian Astronomical Observatory
(IAO), Hanle, at an altitude of 4500 m above sea level. HESP covers a
wavelength range of 350-1000 nm and has been designed to carry out a wide
variety of scientific studies, including the ability to conduct RV studies of
exoplanet host stars [25]. It provides two modes of operation, low-resolution
mode offering a resolution of R=30000 and high-resolution mode, which uses an
image slicer, giving a resolution of R=60000. A passively stabilized FP based
wavelength calibration system has been installed on HESP spectrograph [26].
The FP spectra obtained in high-resolution mode (R=60,000), is shown in figure
4. IRAF and a Python based pipeline, which does not incorporate tilt
correction, is used for reduction of data obtained from the spectrograph.

Figure 4: FP spectra observed at R=60000.The FP setup operates at a
temperature of 19∘C $\pm$ 0.05∘C and under a presure of 0.025 mbar. Top panel:
Full two dimensional spectra. Bottom panel: Zoomed-in version showing part of
the spectra and the slicer image.[27]

##  3 Methodology and algorithm

We have developed a routine that corrects the curvature in spectra and removes
the tilt of the individual spectral lines. Image processing tools in Python,
namely, Scikit-Image [28] and OpenCV [29] were used for this purpose.

###  3.1 Aperture Tracing

The first step in the process is to identify the position of all the apertures
in the spectra. The position of all these apertures are saved as higher-order
polynomials (2 or above), depending on which, the apertures are then
extracted. This is called tracing of the apertures, and a continuous spectrum
like that of a flat lamp is used for this purpose. Tracing of apertures was
performed following the routines described in CERES [30].

###  3.2 Order extraction

After all the apertures were traced, the apertures are extracted in the next
step. The aperture size ($apsize$) was chosen based on the extent of every
aperture in the cross dispersion direction. While choosing the aperture size,
the inter-order separation in the spectra is kept in mind in order to avoid
any overlapping of the mask with consequent orders. Intensity values in the
aperture were extracted by creating a mask using Bivariate Spline [31] and
sampling at every 0.5 pixels. Mask extent was decided from $(y0-apsize/2)$ to
$(y0+apsize/2)$ in step size of 0.5, where y0 is the traced polynomial. An
example of the traced mask is shown in figure 5.

Figure 5: Aperture extraction mask, in red, over plotted on the spectra, for
one particular aperture. There is no overlap of the mask with neighbouring
orders.

###  3.3 Curvature removal

Correction of the tilt in individual spectral lines should be preceded by
curvature and global tilt removal, if any. For removing the curvature and
straightening the new array, extracted points were stored in a separate array
row-wise. The intensity data extracted from the first row was stored in the
first row of the new array and so on. Stacking each straightened aperture in
order of their extraction reproduced the entire spectra without the curvature
as shown in figure 6.

Figure 6: Section of the stacked apertures to show the curvature correction.

###  3.4 Tilt calculation and removal

The tilt is now computed in curvature removed results. Routine was tested on
both FP and Th-Ar calibration frames (in X-Shooter and MIKE). Since the
spectra have lines with distinguishable edges, we have used the Canny edge
detection technique [32] for determining the boundaries of each tilted line.
The correction was performed individually on each aperture. The selection,
tilt calculation and correction procedures are entirely automated. The
algorithm for tilt correction is as follows:

  * •

Load the required aperture and take a central y-cut through the middle of the
aperture.

  * •

Smoothen the data obtained from y-cut using Gaussian smoothening. Detect the
peak values in smoothened data and save the x-position corresponding to the
peaks. This generates position information for all the lines present.

  * •

Calculate the difference between adjacent peak positions. This gives the
separation between two peaks. Take the median value of differences obtained.
Construct a boundary array with $xpeakposition$ $\pm$ $median/2$ being edge
positions. This is done to avoid overlapping of each FP line boundary when the
final corrected array is reconstructed.

  * •

Use the boundary array to construct a box and isolate the region of interest
in a separate array. Calculate the y-extent of the separated box to include
areas with FP data present and avoid background noise.

  * •

Since Th-Ar spectra does not have equally spaced lines of uniform intensity,
mean thresholding is performed, and a binary image is generated, example of
which is shown in figure 7. The transitions from 0 to 1 and vice versa
determine the boundary array values mentioned in the previous step.

Figure 7: Binary thresholding performed on one of the apertures of X-Shooter
Th-Ar calibration frame. This is done to detect medium SNR lines. Top:
Original extracted aperture. Bottom: Result of binary thresholding.

  * •

The centroid and tilt angle are determined using function region prop in
Scikit processing package on each calibration line. The centroid value is
taken as the reference position (x0,y0).

  * •

Every pixel is shifted with respect to the reference position (x0, y0)
determined above, using Eq. 1 [33, 34]. Function warp in the scikit-image
processing tool is used for shifting pixels according to the calculated
$x_{s}$ value.

$x_{s}=x^{\prime}-(y^{\prime}-y_{0})\times slope\,,$ (1)

  * •

The result of the algorithm applied on one tilted line is shown in figure 8.
Top panel shows the corrected image and bottom panel shows the effect of
correction on the FWHM of the line. The corrected line is stitched into the
reconstructed main array using the boundary values determined before. This is
done to make sure that the FSR of the data is not altered.

(a) Tilt correction for single line

(b) 1D binned plot

Figure 8: Representation of tilt correction. (a) Correction algorithm
performed on one Th-Ar line to show how the tilt is removed. Original line
shows the tilted line and corrected line is the result after correcting for
tilt. (b) Binning done across y-axis to generate 1D plot for both the lines.
It can be observed that the tilt correction drastically reduces the line-width
from 12.44 before correction to 6.14 after correction.

##  4 Results

The developed method has been tested on Fabry-Perot calibration spectra of
HESP. For X-shooter and MIKE, Th-Ar calibration spectra were used.

###  4.1 HESP

The FP calibration frame of HESP has been shown in figure 4. Tilt calculation
is preceded by curvature removal and global tilt correction described in the
previous section. FP lines exist across 22 orders of the spectra, and in
figure 9 we show the representative plots for six orders: two top orders, two
central orders and two bottom orders. The calculated tilt for FP lines is
plotted along with a linear fit to the points. In HESP, we do not see a smooth
variation in tilt angle after removal of curvature. As illustrated in figure
9, the weak trend in the data, however, is still visible from small but non-
zero slopes of the best fit lines seen in different orders. The wavelength
dependence of tilt is indicated by the slope of the linear fit to the tilt
values, which increases from lower-order ($7.75\text{\times}{10}^{-6}$ for
order 25) to higher order ($1.46\text{\times}{10}^{-5}$ for order 46). The
tilt values are more scattered because the HESP design does not introduce a
large tilt in the individual lines, causing the noise level in the spectra to
come into the picture. For spectrographs in which it is known that the design
introduces appreciable tilt, the scatter in the tilt angles are less, as will
be seen in forthcoming sections.

Figure 9: Tilt angle variation of FP lines across several spectrograph orders.
The solid black line shows a linear fit to the data, and the dotted line shows
a two sigma clipping boundary. Any point outside this boundary is rejected as
an outlier during the fit. The scatter in the plot indicates the low tilt
value in HESP spectra.

Figure 10 shows the uncorrected and corrected orders, plotted along with their
similarity and difference image for one order. Structural Similarity Index
(SSIM) is used to determine the similarity between two images, +1 indicating
the most similar images and -1 indicating the images are very different [35].
SSIM image and difference image are computed between the original order and
corrected order.

Figure 10: Zoomed in view of one tilt corrected FP spectral order, taken with
HESP. Original order is the image before tilt correction. Corrected order is
the image after correction. SSIM image shows the similarity image, 1 being the
parts where the images are similar. The similarity index for the order shown
is 0.987469. The difference image shows the normalized mathematical difference
computed between two images, 0 being no difference regions.

Since HESP does not show any visible tilt, the FWHM of each FP line across the
order is plotted in figure 11 before and after the correction. The number of
lines that show a decrease in FWHM is determined and the finesse is
calculated. Not all the FP lines show a decrease in FWHM, especially the lines
at edges, which can show an increase. This is because of low SNR at the edges
due to the non-uniform illumination of the detector. Hence the correction is
not performed effectively at these regions. The FWHM and finesse values for
the six plotted orders are tabulated in table 1.

Table 1: Summarised result from tilt correction on HESP data. Order no. |  Original mean finesse |  Corrected mean finesse |  Total peaks |  Peaks with increased FWHM |  Peaks with decreased FWHM
---|---|---|---|---|---
25 |  2.161 |  2.175 |  360 |  75 |  285
26 |  2.250 |  2.300 |  355 |  45 |  310
34 |  2.053 |  2.151 |  309 |  2 |  307
35 |  2.057 |  2.115 |  304 |  14 |  290
44 |  2.291 |  2.326 |  254 |  11 |  243
46 |  2.257 |  2.387 |  243 |  0 |  243

Figure 11: Comparison of FWHM of FP lines across an order before and after
tilt correction. Values marked with blues stars show the FWHM of lines before
correction. Values marked with red circles show the FWHM values of the same
lines after correction.

###  4.2 X-shooter

Th-Ar calibration frames have been used to test the tilt correction algorithm.
Unlike FP, Th-Ar does not provide equispaced lines of uniform intensity, which
makes line detection across the order tricky. The method applies well on high
to medium SNR arc lines. Figure 12 shows the images of uncorrected and
corrected orders, plotted along with their similarity image and difference
image calculated between the original order and the corrected order.

(a) Order 9:SSIM=0.778193

(b) Order 10: SSIM=0.749655

Figure 12: Tilt correction of Th-Ar spectra taken with X-Shooter. (a) Original
spectrum before the tilt correction. (b) Th-Ar spectrum after tilt correction.
(c) SSIM image showing the similarity image. The regions with highest
similarity in the images corresponds to 1. (d) Difference image shows the
normalized mathematical difference computed between two images, 0 being no
difference regions. The similarity index is mentioned for each order.

X-shooter introduces visible tilts in the spectra, with the tilt amplitude
being $\sim$ 1.5-2 times the HESP tilt values. Hence the calculated tilt shows
less scatter than in HESP. Figure 13 shows the comparison between the slope
values before and after correction. Most of the outliers in the data coincide
with low SNR lines.

Figure 13: Slope values plotted for the uncorrected (black stars) Th-Ar lines
and the corrected lines (red circles) for X-Shooter. The uncorrected slope
values follow a clear trend. The scatter arises due to the attempt to
calculate slopes of low SNR lines. The slope of the Th-Ar lines has been
reduced after correction, the only deviation arising around the low SNR lines.

###  4.3 MIKE

Since Th-Ar spectra do not share the same properties as FP spectra, only high
to medium SNR lines are detected and corrected. We have performed the analysis
on both blue and red channels of the spectrograph and data with slit settings
of 2", 0.7" and 0.35" and will be presenting results of all the settings
mentioned for the top, middle and bottom order. Figure 14 shows the corrected
and difference images for the mentioned slit settings of spectra in the red
channel. The tilt in lines before and after correction is visible in the
figure. Figure 15 shows the slope values before correction and after
correction for spectra with 2" slit width. Figure 16 shows the corrected slope
values for 0.7” slit data. The corrected slope values for 0.35” slit setting
is plotted in figure 17. All the corrected slope plots are shown for both blue
and red channels.

(a) 2" slit width Order 21:SSIM=0.933707

(b) 0.7" slit width Order 21: SSIM=0.946387

(c) 0.35" slit width Order 21: SSIM=0.944193

Figure 14: Tilt correction of Th-Ar spectra for different slit width setting
of MIKE in red channel. (a) The image of order before tilt correction. (b) The
image of same order after correction. (c) SSIM image shows the similarity
image, 1 being the areas with maximum similarity. (d) Difference image shows
the normalized mathematical difference computed between two images, 0 being no
difference regions.

Figure 15: Slope values plotted for the uncorrected (black stars) Th-Ar lines
and the corrected lines (red circles) for 2" slit setting of MIKE. The
uncorrected slope values show a clear trend. The slope of the Th-Ar lines has
been reduced after correction. The scatter in data is due to the attempt to
calculate and correct for the low SNR lines.

Figure 16: Slope values plotted for the uncorrected (black stars) Th-Ar lines
and the corrected lines (red circles) for 0.7" slit setting of MIKE. The
uncorrected slope values show a clear trend. The slope of the Th-Ar lines has
been reduced after correction. The scatter in data is due to the attempt to
calculate and correct for the low SNR lines.

Figure 17: Slope values plotted for the uncorrected (black stars) Th-Ar lines
and the corrected lines (red circles) for 0.35" slit setting of MIKE. The
uncorrected slope values show a clear trend. The slope of the Th-Ar lines has
been reduced after correction. The scatter in data is due to the attempt to
calculate and correct for the low SNR lines.

Figure 18 shows comparison between the FWHM of extracted Th-Ar lines by MIKE
pipeline ($lw1$) and by the discussed algorithm ($lw2$). The difference
between $lw1$ and $lw2$ has also been plotted, a positive difference obtained
when $lw1$ is greater than $lw2$. The values have been calculated for one
order of Th-Ar spectrum obtained in red channel using slit widths of 0.35”,
0.7” and 2”. For 0.35” and 0.7” slit widths, the pipeline gives 19% $\pm$ 7%
and 11% $\pm$ 4% mean reduction in the FWHM of the Th-Ar lines respectively.
For the same slit widths, the discussed algorithm gives 20% $\pm$ 7% and 10%
$\pm$ 4% mean reduction in the FWHM respectively.

Figure 18: Performance of the developed algorithm with respect to MIKE
pipeline. The blue triangles represent the FWHM of uncorrected tilted lines.
The black crosses indicate FWHM of lines obtained after reduction with MIKE
pipeline. The red circles indicate the FWHM of lines obtained after reduction
with our algorithm. The green stars indicate the FWHM differences between the
MIKE pipeline and our algorithm.

##  5 Summary

Analysis of the FP spectra acquired through HESP led us to the observation of
discrepancies between the expected FP line FWHM (obtained with FTS) and the
FWHM of the lines obtained with the spectrograph. This motivated us to examine
the factors that can cause the increase in line-width. Performance of the FP
degrades over the years due to deterioration of the optical coating. An
additional reason for the increase in line-width was found to be the tilt in
the FP lines, caused due to curvature in the orders. The HESP design does not
introduce any significant tilt in the data. Hence it is not visually
discernible in the spectra. Although the amount of the tilt is small, it is
important to take care of this artifact in post-processing in order to
maintain the performance of FP.

Tilted lines in echelle spectra are artifacts often introduced by the
curvature in spectra or due to the design of the spectrograph itself. It is
essential to eliminate this artifact in order to avoid the introduction of any
errors in the data while post-processing. A possible way is to avoid binning
the data and analyzing the flux at a single-pixel location. However, this
technique will result in lesser flux values and hence less SNR in the data.
Binning the 2D spectrum in the usual way is done vertically, i.e. along the
slit direction. When a tilted line is binned vertically, it results in wrong
flux values at each binned pixel as well as a decrease in spectral resolution
due to broadening of the line, and hence wrong wavelength when the final
calibration is performed. The tilt is not constant and varies as a function of
wavelength across the spectra. This also affects the accuracy with which we
can determine the centroid positions of spectral lines, which is crucial in
the case of high precision RV studies. To avert the miscalculations arising
from binning a tilted line vertically, either the binning could be performed
along an oblique axis or a simpler way is to find out the obliquity of each
spectral line and correct for it. We employ the latter method to remove the
tilt by automating the detection of each spectral line, computing the line’s
slant, and then compensating for it, so that the standard post-processing
techniques can be applied as usual.

We present in this paper a simple algorithm for curvature and tilt correction
in high-resolution spectra. The algorithm is written in Python and uses image
processing techniques for finding individual line slant values and correcting
for them. We have demonstrated the algorithm on FP calibration spectra from
HESP. A total of 6624 FP lines were detected across 22 orders, and a reduction
in FWHM of 5417 lines was observed after using the tilt correction algorithm
along with an overall improvement in the finesse value from 2.167 to 2.208. In
order to ascertain the capability of the algorithm, we looked into
spectrographs with highly tilted lines and performed the tilt corrections on
the Th-Ar calibration spectra from X-shooter and MIKE. We noticed visual
improvement in tilts of the lines after the application of the algorithm. We
also calculated the tilt values of each line before and after correction and
found a reduction in the absolute value of the slope after correction, thereby
indicating the efficacy of the algorithm. The main limitation of the algorithm
is the ability to deal with low SNR/faint lines (SNR<6) and blended lines in
Th-Ar spectra since it has been developed, keeping in mind the uniform line
density provided by FP or LFC. We are looking into it as part of a future
upgrade. Authors can be contacted to avail the code.

Funding This project is supported by Science and Engineering Research Board
(SERB), Department of Science and Technology (DST), India, under grant no.
EMR/2014/000941.

Acknowledgments The authors want to acknowledge Mr S. Sriram for the advice
and technical support provided by him. The authors also thank Dr. Martin Dubs
for his help and suggestions and Dr. Rebecca Bernstein for providing us with
MIKE data. X-shooter study is based on data obtained from the ESO Science
Archive Facility under request number 609319.

Disclosures The authors declare no conflicts of interest.

Data Availability Statement Data underlying the results presented in this
paper for X-shooter are publicly available on ESO Archive. The data for HESP
and MIKE is not publicly available at this time but may be obtained from the
authors upon reasonable request.

## References

  * [1] N. R. Napolitano, A. J. Romanowsky, and C. Tortora, “The central dark matter content of early-type galaxies: scaling relations and connections with star formation histories,” Monthly Notices of the Royal Astronomical Society 405, 2351–2371 (2010).
  * [2] D. D. Kelson, G. D. Illingworth, P. G. van Dokkum, and M. Franx, “The evolution of early-type galaxies in distant clusters iii ${M/L_{v}}$ ratios in the z=0.33 cluster cl 1358+62,” The Astrophysical Journal 531, 184–199 (2000).
  * [3] A. Bik, T. Henning, A. Stolte, W. Brandner, D. A. Gouliermis, M. Gennaro, A. Pasquali, B. Rochau, H. Beuther, N. Ageorges, W. Seifert, Y. Wang, and N. Kudryavtseva, “AGE SPREAD IN w3 MAIN: LARGE BINOCULAR TELESCOPE/LUCI NEAR-INFRARED SPECTROSCOPY OF THE MASSIVE STELLAR CONTENT,” The Astrophysical Journal 744, 87 (2011).
  * [4] A. Bhowmick, G. Pandey, and D. L. Lambert, “Detection of Fluorine in Hot Extreme Helium Stars,” The Astrophysical Journal 891, 40 (2020).
  * [5] A. P. Hatzes, “The radial velocity method for the detection of exoplanets,” in _Methods of Detecting Exoplanets: 1st Advanced School on Exoplanetary Science,_ V. Bozza, L. Mancini, and A. Sozzetti, eds. (Springer International publishing, 2016).
  * [6] F. Wildi, F. Pepe, B. Chazelas, G. L. Curto, and C. Lovis, “A Fabry-Perot calibrator of the HARPS radial velocity spectrograph: performance report,” in _Ground-based and Airborne Instrumentation for Astronomy III,_ vol. 7735International Society for Optics and Photonics (SPIE, 2010), pp. 1853 – 1863.
  * [7] G. W. Marcy and R. P. Butler, “Precision radial velocities with an iodine absorption cell,” Publications of the Astronomical Society of the Pacific 104, 270 (1992).
  * [8] M. T. Murphy, T. Udem, R. Holzwarth, A. Sizmann, L. Pasquini, C. Araujo-Hauck, H. Dekker, S. D’Odorico, M. Fischer, T. W. Hänsch, and A. Manescau, “High-precision wavelength calibration of astronomical spectrographs with laser frequency combs,” Monthly Notices of the Royal Astronomical Society 380, 839–847 (2007).
  * [9] S. Chamarthi, R. K. Banyal, S. Sriram, and G. Pandey, “Stability analysis of vbt echelle spectrograph for precise radial velocity measurements,” Journal of Optics 47, 195–201 (2018).
  * [10] L. B. Robinson and D. W. Latham, “Present and future the ninth santa cruz summer workshop in astronomy and astrophysics, july 13–july 24, 1987, lick observatory,” in _Instrumentation for Ground-Based Optical Astronomy,_ L. B. Robinson, ed. (Springer-Verlag New York, 1988).
  * [11] M. J. Ireland, M. White, J. P. Bento, T. Farrell, K. Labrie, L. Luvaul, J. G. Nielsen, and C. Simpson, “Data reduction software for the Gemini high resolution optical spectrograph,” in _Software and Cyberinfrastructure for Astronomy V,_ vol. 10707 J. C. Guzman and J. Ibsen, eds., International Society for Optics and Photonics (SPIE, 2018), pp. 864 – 873\.
  * [12] T. Das, R. K. Banyal, S. Kathiravan, T. Sivarani, and R. B., “Development of a stabilized Fabry-Perot based wavelength calibrator for precision Doppler spectroscopy,” in _Ground-based and Airborne Instrumentation for Astronomy VII,_ vol. 10702International Society for Optics and Photonics (SPIE, 2018), pp. 1899 – 1909.
  * [13] R. Bernstein, S. A. Shectman, S. M. Gunnels, S. Mochnacki, and A. E. Athey, “MIKE: a double-echelle spectrograph for the Magellan Telescopes at Las Campanas Observatory,” in _Instrument Design and Performance for Optical/Infrared Ground-based Telescopes,_ vol. 4841 M. Iye and A. F. M. Moorwood, eds., International Society for Optics and Photonics (SPIE, 2003), pp. 1694 – 1704.
  * [14] S. D’Odorico, H. Dekker, R. Mazzoleni, J. Vernet, I. Guinouard, P. Groot, F. Hammer, P. K. Rasmussen, L. Kaper, R. Navarro, R. Pallavicini, C. Peroux, and F. M. Zerbi, “X-shooter UV- to K-band intermediate-resolution high-efficiency spectrograph for the VLT: status report at the final design review,” in _Ground-based and Airborne Instrumentation for Astronomy,_ vol. 6269International Society for Optics and Photonics (SPIE), pp. 993 – 1002\.
  * [15] D. Tody, “The IRAF Data Reduction and Analysis System,” in _Instrumentation in astronomy VI,_ vol. 627 of _Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series_ D. L. Crawford, ed. (1986), p. 733.
  * [16] D. Tody, “IRAF in the Nineties,” in _Astronomical Data Analysis Software and Systems II,_ vol. 52 of _Astronomical Society of the Pacific Conference Series_ R. J. Hanisch, R. J. V. Brissenden, and J. Barnes, eds. (1993), p. 173.
  * [17] Vernet, J., Dekker, H., D´Odorico, S., Kaper, L., Kjaergaard, P., Hammer, F., Randich, S., Zerbi, F., Groot, P. J., Hjorth, J., Guinouard, I., Navarro, R., Adolfse, T., Albers, P. W., Amans, J.-P., Andersen, J. J., Andersen, M. I., Binetruy, P., Bristow, P., Castillo, R., Chemla, F., Christensen, L., Conconi, P., Conzelmann, R., Dam, J., De Caprio, V., De Ugarte Postigo, A., Delabre, B., Di Marcantonio, P., Downing, M., Elswijk, E., Finger, G., Fischer, G., Flores, H., François, P., Goldoni, P., Guglielmi, L., Haigron, R., Hanenburg, H., Hendriks, I., Horrobin, M., Horville, D., Jessen, N. C., Kerber, F., Kern, L., Kiekebusch, M., Kleszcz, P., Klougart, J., Kragt, J., Larsen, H. H., Lizon, J.-L., Lucuix, C., Mainieri, V., Manuputy, R., Martayan, C., Mason, E., Mazzoleni, R., Michaelsen, N., Modigliani, A., Moehler, S., Møller, P., Norup Sørensen, A., Nørregaard, P., Péroux, C., Patat, F., Pena, E., Pragt, J., Reinero, C., Rigal, F., Riva, M., Roelfsema, R., Royer, F., Sacco, G., Santin, P., Schoenmaker, T., Spano, P., Sweers, E., Ter Horst, R., Tintori, M., Tromp, N., van Dael, P., van der Vliet, H., Venema, L., Vidali, M., Vinther, J., Vola, P., Winters, R., Wistisen, D., Wulterkens, G., and Zacchei, A., “X-shooter, the new wide band intermediate resolution spectrograph at the eso very large telescope,” A $\&$ A 536, A105 (2011).
  * [18] P. Goldoni, F. Royer, P. François, M. Horrobin, G. Blanc, J. Vernet, A. Modigliani, and J. Larsen, “Data reduction software of the X-shooter spectrograph,” in _Ground-based and Airborne Instrumentation for Astronomy,_ vol. 6269 I. S. McLean and M. Iye, eds., International Society for Optics and Photonics (SPIE, 2006), pp. 822 – 832.
  * [19] P. Goldoni, F. Royer, M. Horrobin, P. François, L. Guglielmi, R. Haigron, J. Vernet, A. Modigliani, and P. Bristow, “Results of X-shooter data reduction software on laboratory frames,” in _Ground-based and Airborne Instrumentation for Astronomy II,_ vol. 7014 I. S. McLean and M. M. Casali, eds., International Society for Optics and Photonics (SPIE, 2008), pp. 2004 – 2014.
  * [20] A. Modigliani, P. Goldoni, F. Royer, R. Haigron, L. Guglielmi, P. François, M. Horrobin, P. Bristow, J. Vernet, S. Moehler, F. Kerber, P. Ballester, E. Mason, and L. Christensen, “The X-shooter pipeline,” in _Observatory Operations: Strategies, Processes, and Systems III,_ vol. 7737 of _Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series_ D. R. Silva, A. B. Peck, and B. T. Soifer, eds. (2010), p. 773728.
  * [21] R. M. Bernstein, S. M. Burles, and J. X. Prochaska, “Data reduction with the MIKE spectrometer,” Publications of the Astronomical Society of the Pacific 127, 911–930 (2015).
  * [22] J. J. Bochanski, J. F. Hennawi, R. A. Simcoe, J. X. Prochaska, A. A. West, A. J. Burgasser, S. M. Burles, R. A. Bernstein, C. L. Williams, and M. T. Murphy, “MASE: A New Data-Reduction Pipeline for the Magellan Echellette Spectrograph,” Publications of the Astronomical Society of the Pacific 121, 1409 (2009).
  * [23] N. Piskunov, A. Wehrhahn, and T. Marquart, “Optimal extraction of echelle spectra: Getting the most out of observations,” A&A 646, A32 (2021).
  * [24] Piskunov, N. E. and Valenti, J. A., “New algorithms for reducing cross-dispersed echelle spectra*,” A&A 385, 1095–1106 (2002).
  * [25] S. Sriram, A. Kumar, A. Surya, T. Sivarani, S. Giridhar, S. Kathiravan, M. N. Anand, D. Jones, D. Grobler, R. Jakobsson, A. Chanumolu, A. Unni, A. Dorje, T. Dorje, and T. Gyalson, “Hanle echelle spectrograph: design and performance,” in _Proc. SPIE,_ vol. 10702 (2018), pp. 2007 – 2021.
  * [26] T. Das, R. K. Banyal, T. Sivarani, and B. Ravindra, “Development of a stabilized fabry–perot etalon based calibrator for hanle echelle spectrograph,” Appl. Opt. 59, 5464–5472 (2020).
  * [27] T. Das, R. K. Banyal, T. Sivarani, and S. Sriram, “Using a passively stabilized Fabry-Perot etalon for determining instrumental artifacts in a spectrograph,” in _Ground-based and Airborne Instrumentation for Astronomy VIII,_ vol. 11447 C. J. Evans, J. J. Bryant, and K. Motohara, eds., International Society for Optics and Photonics (SPIE, 2020), pp. 901 – 911\.
  * [28] S. Van der Walt, J. L. Schönberger, J. Nunez-Iglesias, F. Boulogne, J. D. Warner, N. Yager, E. Gouillart, and T. Yu, “scikit-image: image processing in python,” PeerJ 2, e453 (2014).
  * [29] G. Bradski, “The OpenCV Library,” Dr. Dobb’s Journal of Software Tools (2000).
  * [30] “Ceres: A set of automated routines for echelle spectra,” Publications of the Astronomical Society of the Pacific 129, 1–18 (2017).
  * [31] T. Zhou and M.-J. Lai, “Scattered data interpolation by bivariate splines with higher approximation order,” Journal of Computational and Applied Mathematics 242, 125 – 140 (2013).
  * [32] J. Canny, “A computational approach to edge detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8, 679–698 (1986).
  * [33] M. Dubs and P. Schlatter, “A practical method for the analysis of meteor spectra,” WGN, Journal of the International Meteor Organization 43, 94–101 (2015).
  * [34] M. Dubs and K. Maeda, “Calibration of meteor spectra,” in _International Meteor Conference Egmond, the Netherlands, 2-5 June 2016,_ A. Roggemans and P. Roggemans, eds. (2016), p. 65.
  * [35] Z. Wang, A. Bovik, H. Sheikh, and E. Simoncelli, “Image quality assessment: from error visibility to structural similarity,” IEEE Transactions on Image Processing 13, 600–612 (2004).