Cyril Grunspan
email: cyril.grunspan@devinci.fr

Gabriel Lehéricy
email: gabriel.lehericy@devinci.fr

Ricardo Pérez-Marco
email: ricardo.perez.marco@gmail.com

Ant Routing scalability for the Lightning Network

Keywords: Bitcoin, Lightning Network, Ant Routing, AVL Trees

come

Introduction

The Lightning Network was introduced in order to address Bitcoin scalability [START_REF] Poon | The bitcoin Lightning Netwgoogleork: scalable off-chain instant payment[END_REF]. It consist on a "layer 2"-network set on top of Bitcoin's network which facilitates micro-payments between bitcoin users without needing to broadcast the transaction on the blockchain.

The Lightning Network is not a complete graph, but has the property of channel composition. This allows any user on the network to make secure payments to any other node in the same connected component of the network, even when no direct payment channel exists. For example, assume that Alice and Bob are both LN users, but have no direct payment channel between them. Now assume that there is a third user, Charlie, who has a direct channel with Alice and a direct channel with Bob. Then Alice can pay to Bob via Charlie: Alice sends the payment to Charlie, who will then forward it to Bob. All these payments are realized in a secured way by the protocol of channel composition. This allows any LN node to send money to any other LN node when the network is connected.

Obviously this requires finding a payment route from Alice to Bob, hence the need for a good routing algorithm. Ideally, one wants to have a routing algorithm which is safe, decentralized, anonymous, and only requires minimum knowledge of the network from all participants. In [START_REF] Grunspan | Double spend races[END_REF], the authors proposed a new routing algorithm, called Ant Routing. Ant Routing is a completely decentralized routing algorithm which does not require beacon nodes nor routing tables. Instead, each node of the network executes the exact same task which requires no knowledge of the topology of the network. Moreover, it is worth noting that using Ant Routing on the lightning network would have a positive impact on fees. Indeed, unlike the current routing mechanism in use, ant routing does not allow for a node to ask for fees proportional to the transaction amount. This also strengthens the network's decentralization.

The goal of this article is to estimate the performance of Ant Routing, and propose more precise and efficient implementation. In particular, we investigate if this routing algorithm is compatible with the original ambition of the Lightning Network to solve Bitcoin scalability at planetary level, hence providing an instantaneous decentralized global payment network. In practice, the question is whether Ant Routing algorithm can allow the network to sustain several thousands of transactions per second. This article gives a positive answer to this question. The conservative estimates presented in Sections 6 and 9 show that Ant Routing can sustain more than 10.000 transactions per second.

The paper is organized as follows. In Section 2, we give an overview of routing protocols which have been proposed for the Lightning Network and of algorithms based on ant behavior. Section 3 explains the ant routing protocol. We start by briefly recalling the rough ideas of ant routing as presented in [START_REF] Grunspan | Double spend races[END_REF]. We then give a more detailed description of the Ant Routing protocol. In particular, we give a precise list of data that must be kept in memory and a list of tasks performed by nodes. In Section 5 we estimate the duration for seeds to be kept in memory. In section 6 we give a general argument to determine network capacity for networks with a similar structure than Bitcoin. This argument applies to Ant Routing provided that the local process time for transactions in the nodes is neglectable or of the same order of magnitude than the propagation time across the network. We propose efficient local algorithms and run simulations. In Section 7, we review AVL trees, which is the data structure used for the Ant Routing implementation. In Section 8, we propose a concrete implementation of Ant Routing. Finally, in Section 9 we estimate the computing time and memory usage. Putting together these results, we conclude by an estimate on the number of transactions per second that the proposed implementation of Ant Routing can sustain.

Overview of routing proposals and existing ant algorithms

The white paper for the Lightning Network is sketchy about routing and no specific routing protocol is proposed [START_REF] Poon | The bitcoin Lightning Netwgoogleork: scalable off-chain instant payment[END_REF]. The authors believe that routing tables are necessary, and in fact, it seems every routing protocol proposed for the Lightning Network prior to [START_REF] Grunspan | Double spend races[END_REF] makes use of routing tables. We review in this section some of these proposals. A review of routing solutions for the lightning network can also be found in [START_REF] Shivanand | Coordinate Routing in the Lightning Network[END_REF]. One should keep in mind that, in accordance to Bitcoin philosophy, one wishes the Lightning Network to remain decentralized and to preserve confidentiality of payments.

One major constraint for routing in the Lightning Network is to find a path with sufficient capacity. It seems natural to try to solve this problem via a distributed max-flow approach which computes the path with the largest capacity [START_REF] Awerbuch | Reducing complexities of the distributed max-flow and breadth-firstsearch algorithms by means of network synchronization[END_REF][START_REF] Lester | Maximal Flow Through a Network[END_REF][START_REF] Wilf | Algorithms and complexity[END_REF]. However, max-flow routing performs poorly for large network, as its run time growths quadratically on the number of channels [START_REF] Wilf | Algorithms and complexity[END_REF]. Another possibility is to use beacons instead. A beacon is a special node whose role is to enhance the other nodes' visibility of the network and help them in route computation. One example of an algorithm which uses beacons is Flare [START_REF] Prihodko | Flare: An approach to routing in Lightning Network[END_REF]. Another classical approach to routing is landmark routing. Landmark routing has been adapted to payment network in algorhitms such as SilentWhispers [START_REF] Malavolta | Silentwhispers: Enforcing security and privacy in decentralized credit networks[END_REF]. The idea of landmark routing is to compute a route from the source to the destination via a previously chosen node, called a landmark, which is usually a highly connected node. The main drawback of having a system rely on landmarks or beacons is the potential threat to decentralization, as well as its fragility to attacks.

Another approach to routing is embedding-based routing. The idea is to embed nodes into a vector space such that the hop distance between nodes is reflected by their distance in the vector space. For routing, the source node chooses the neighbor whose vector representation is the closest to the vector representation of the destination node. Each node in the path then repeats this strategy. This requires regularly updating information about the network. An example of such routing algorithm is Speedy Murmurs, which is based on Voute [START_REF] Roos | Anonymous addresses for efficient and resilient routing in f2f over-lays[END_REF][START_REF] Roos | Settling payments fast and private: Efficient decentralized routing for path-based transactions[END_REF].

Recent attention has been given to payment routing solutions that keep channels balanced. Keeping channels balanced is considered important in the current conception of the Lightning Network1 : if a channel becomes too unbalanced, then payment can only flow in one direction, and this restricts payment routes that can no longer use that channel. In [START_REF] Sivaraman | Routing cryptocurrency with the spider network[END_REF], the authors introduce an interesting idea which considers channels' balance for route seclection called Spider. More precisely, Spider splits payments into several smaller payments, each of which can be sent through a different route. The route for each of these payment is chosen to optimize the re-balancing of unbalanced channels.

Note that all of these routing strategies either require giving some nodes a special role (as a landmark or a beacon) or require each node to keep some knowledge of the network topology. This knowledge is a vector of attack for the Lightning Network. One of the reasons for the proposal of Ant Routing is to obfuscate the topology of the network: It requires no landmark and requires no knowledge on the topology, while at the same time preserves anonymity and decentralization. The decentralization of the algorithm is achieved by making every node play exactly the same role in the routing process and using only knowledge about its neighbors.

The algorithm is inspired by the behavior of ants. Ant colonies have raised the interested of ethologists by their ability to optimize their route from nest to food source. Although each ant individually seems to follow a random motion, their collective behavior finds efficiently the shortest path from their nest to a food source. This is achieved through a "stygmergic" communication of the ants with their environment through pheromones [START_REF] Dorigo | Ant Colony Optimization[END_REF]. More precisely, each walking ant leaves a trail of pheromone, which has the attracts other ants to its path.

The author of [START_REF] Dorigo | Ant Colony Optimization[END_REF] and [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents in[END_REF] describes the following experiment to explain this remarkable observed ant optimization behavior. We study an ant colony connected to a food source by two paths, a short and a longer one. At the outset of the experiment, each ant walks in a random direction, choosing each path randomly with equal probability. As they walk, the ants leave a pheromone trail behind. Because ants will travel faster on the shorter path than on the longer one, pheromones accumulate faster on the shorter path. The concentration of pheromone on the shorter path increases, so does the probability that ants to choose this path. This leads to a positive feedback, and eventually few ants will choose the longer path.

The author of [START_REF] Dorigo | Ant Colony Optimization[END_REF] had the idea to simulate this ant behavior with a multi-agent stochastic learning model to solve optimization problems. An application to network routing problems is given in chapter 6 of [START_REF] Dorigo | Ant Colony Optimization[END_REF].

The Ant Routing algorithm is inspired from these ant behavior models, but there are some major differences with the routing propositions in [START_REF] Dorigo | Ant Colony Optimization[END_REF] and [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents in[END_REF]. Our algorithm is simpler and deterministic, and not probabilistic. It only uses the idea of leaving pheromones to trace a path, but does not consider accumulation of pheromones on a path. Eventually, the model could be enhanced taking into account pheromone accumulation to improve the efficiency. The paths are not chosen randomly. The pheromones are flooding the network. Also, apparently the applications of ant algorithms to routing problems in [START_REF] Dorigo | Ant Colony Optimization[END_REF] and [START_REF] Dorigo | Ant system: optimization by a colony of cooperating agents in[END_REF] use routing tables, which we want to avoid.

Ant routing protocol

We briefly recall the main ideas of ant routing as presented in [START_REF] Grunspan | Double spend races[END_REF]. We assume that Alice and Bob both have a node on the Lightning Network and they have a direct communication channel but not necessarily a payment channel. Alice wants to pay Bob via the Lightning Network, so they need to find a payment route in the Lightning Network.

Alice and Bob start by agreeing on a random number S, chosen big enough to avoid collisions. Alice creates the number S(0) = 0 S and Bob creates the number S(1) = 1 S. S(0) and S(1) are called pheromone seeds. Alice and Bob send their respective seeds to the network through their neighbors. Pheromone seeds propagate on the network being successively forwarded by all nodes to their neighbors. When S(0) and S(1) meet at some node we have a match. Each pheromone seed is forwarded with a counter associated. This counter is increased by 1 at each hop. If a node receives the same pheromone seed several times, then only the pheromone seed with lower counter is stored and forwarded. The nodes keep track from whom they received the stored seeds. When we have a match, the node where it occurs creates matched seeds M (0) and M (1), and sents back to the respective neighbors from whom he received S(0) and S [START_REF] Adelson-Velski | An algorithm for the organization of information[END_REF]. Nodes receiving a matched seed forward them in the same way, and after a finite number of steps, bounded by the counters, the matched seeds reach Alice and Bob.

After some time, Alice will receive several matched seeds, each corresponding to a payment route. Alice is free to choose any of these matched seed as a payment route. Note that, in order to preserve anonimity, it is desirable for Alice to choose a route with at least two intermediary nodes. She selects one, by a selection algorithm that she is free to decide. Creates a confirmed seed C and sends C back to her neighbor from whom she received the matched seed. Nodes forward confirmed seed they receive as for matched seeds. Hence, the confirmed seed will reach Bob though a unique path. Once Bob has received C, he informs Alice and she can proceed with the payment. The payment is then done via this path.

Notice that this "path discovering algorithm" finds a connecting path without anyone knowing this path. The only knowledge the participating nodes have is about their neighbors, and they don't even know if these are Alice or Bob.

During the pheromone phase, a node may be tempted to cheat with the counter in order to make the path more attractive. For this reason, we require a verification phase after the confirmation phase and before the payment. The point of this verification phase is to check that no node on the path indicated by C has cheated with the counter. This can be done in the following way: during the confirmation phase, each node, starting from Alice neighbor, is asked to generate a random number. This random number is appended to a list l, which lists all the random numbers from previous nodes. Then the nodes forwards l along with C to the next node. When C and l reach Bob, Bob sends l back and communicates the list of random numbers to Alice. The nodes forward it back only if their random number is in the list. Then l can only reach back Alice through the nodes in the path if nobody has cheated on the counter.

We make precise the task done by the nodes in the protocol. It is important to note that all nodes, apart from Alice and Bob in their payment, execute the same task. Moreover, the nodes have no knowledge about the topology of the network. The only topological information a node needs is who are its direct neighbors.

We list in the next section which data the nodes must keep in memory, and which must be relayed (Section 3.1). We then give the algorithms that the nodes perform in each phase of the ant routing protocol: the pheromone phase, the match phase, the confirmation phase and the counter check phase (Section 3.2).

Memory data

Each node allocates some memory space for the routing task. This memory space contains three trees. The first one is used to store pheromone seeds, the second one for matched seeds, and the third one for confirmation seeds. When she starts her routing task, Alice creates a fourth tree in her memory, which we call the special match tree. This tree will be destroyed once Alice has completed her payment. This tree is used to store the matched seeds created from her own pheromone seed. These matches are therefore stored separately from other matched seeds.

Each seed comes with some data. More precisely, for each pheromone seed P , a node stores:

(1) The pheromone seed P .

(2) A counter c.

(3) The id s of the node from which it received the seed .

(4) The remaining fees f : at the start, Alice chooses a maximal amount f max of fees which she is willing to pay for the transaction. If g denotes the sum of all the fees of all nodes through which the seed has traveled, then the remaining fees f is f = f max -g.

(5) The amount a of the transaction.

All this information is required for the functioning of the ant routing algorithm. The id s is needed for the "match" phase, when the matched seed will have to trace the way back to Alice. The amount of the transaction is used by the relaying nodes to select channels with sufficient funds. The remaining fees are used by Alice at the start of the confirmation phase in her choice of the matched seed. Finally, the counter is used to tame the flood of data on the network (see section 3.2).

The node keeps s to itself to preserve anonymity. The nodes also relay one extra piece of information which is not stored in memory: a timestamp t, which is decided upon by Alice at the creation of the seed. This timestamp allows the node to know the age of the seed, which is necessary information so that the the node knows when to remove the seed from its memory. Pheromone seeds are therefore forwarded as messages of the form: (P, c, f, a, t) (pheromone seed, counter, remaining fees, payment amount and timestamp).

For each matched seed M , the node stores the following items:

(1) A "match identifier" Id.

(2) The "target" of the match, which is the name of the next node in the path from Alice to Bob which M indicates.

The number Id is a random number generated at the creation of the match. Its purpose is to distinguish between different matches which may have been created from the same pheromone seed. Note that it is not necessary to store M itself, although M needs to be forwarded. There are also four extra pieces of information which need to be forwarded but do not have to be kept in memory. These are:

(1) Two counters c and C. The counter C gives the number of intermediate nodes from Alice to Bob in the path indicated by M . The counter c is decreased by 1 at each hop. Its purpose is to be compared with the counter of the pheromone seed associated to M (see section 3.2 below).

(2) The total remaining fees F associated to M . We have F = 2f max -G, where G denotes the sum of all fees from Alice to Bob in the path indicated by M . The purpose of F is to be transmitted to Alice, so that she can choose the path with the lowest fees.

(3) A timestamp t, which is the timestamp of the corresponding pheromone seed.

Therefore, matched seeds are forwarded to other nodes via a message of the form (M, Id, c, C, F, t). Note that, in Alice's special match tree, F and C are also stored.

A confirmation seed is simply a random number Id. For each confirmation seed, the node stores:

(1) An identifier Id. This is the identifier of the matched seed chosen by Alice.

(2) The "target", i.e. the next node in the path from Alice to Bob.

(3) An integer check. This is a randomly generated integer meant for the final counter check phase.

Confirmed seeds are forwarded in messages of the form (Id, l, t), where l is a list of integers and t is the timestamp of the corresponding pheromone seed. More precisely, l is the list of the "check" integers of all preceding nodes.

Remark 3.1:

The node does not store the timestamp of a given seed. However, the location of a given seed in memory depends on its timestamp t. Indeed, we will see in Section 8 that seeds are stored in several trees, each of which corresponds to a time interval to which the seed's timestamp belongs. It follows that, in order to find a seed in its memory, the node needs to know the associated timestamp. This explains why the timestamp also has to be forwarded with each type of seed.

Algorithms

The ant routing protocol has four phases: the "pheromone" phase, the "match" phase, the "confirmation" phase and the "counter check" phase. We now describe these phases one by one in this order. Alice chooses two random numbers S and c 0 , the timestamp t, and the maximal amount of fees f max which she is willing to pay, and communicates to Bob this data. The number S will be used to form the pheromone seeds and c 0 will be used the starting value for the counter2 . The purpose of choosing a random number as the starting value of the counter is to preserve Alice's and Bob's anonymity. If we start the counter at 0, then the neighbors of ALice and Bob will know that they are originating the transaction. The timestamp t serves as the time at which Alice and Bob broadcast their pheromone seeds.

Assume that S, c 0 and t have been agreed upon by Alice and Bob, and that Alice has chosen f max . Alice then creates P (0) := 0 S and stores the information (P (0), c 0 , 0, f max , a) in her pheromone tree, where a denotes the amount of money which she wants to send Bob. The "0" indicates that the seed has no sender, so the seed originates from Alice. Similarly, Bob creates P (1) := 1 S and stores the information (P (1), c 0 , 0, f max , a) in his pheromone tree. At time t, Alice sends the message (P (0), c 0 , f max , a, t) to all her neighbors, and Bob sends the message (P (1), c 0 , f max , a, t) to all his neighbors. After this initial step, the nodes will keep forwarding P (0) and P (1) until matches occur, increasing the counter by 1 at each hop. In general, the same node will receive the same pheromone seed several times coming from different paths. However, after a pheromone seed has been received the first time, then the node will only broadcast new arrivals of the same seed if the counter of the newly arrived seed is smaller than the counter of the previously received seed. This reduces the amount of information sent through the network and makes sure that Alice only receives the shortest route proposals.

Each node substracts its own fees from the remaining fees before forwarding the seed. A node only has knowledge of remaining fees, and does not know f max . This makes it extremely difficult for intermediary nodes to deduce from the fees any information about the sender or receiver of the payment, thus preserving Alice's and Bob's anonymity.

Here is an algorithm describing the work of a node upon receiving a pheromone seed from node s in the form of a message (P, c, f, a, t). We denote by g the fees of the node performing the task. P denotes the conjugate of P , i.e P (0) = P (1) and P (1) = P (0).

Algorithm 1: treatment of pheromone seeds

The function create_and_send_match() used above starts the match phase of the ant routing protocol. A matched seed has the form M (0) := 0 P (0) or M (1) := 0 P (1), where P (0) and P (1) are pheromone seeds. M (0) is sent back to Alice, and M (1) is sent back to Bob. Assume (P (0), c, s, f, a) and (P (1), c , s , f , a) are both in memory, and denote by g the fees of the node where the match occurs. Then the function create_and_send_match(P ) does the following:

if f + f -g ≥ 0 then
Set M (0) := 0 P (0), M (1) := 0 P (1). Generate a random number Id; ,Id,c,C,F,t), it looks for the corresponding P ( ) in its memory and checks that the counter associated to P ( ) is equal to c -1. If this is the case, then the node retrieves the sender s of P ( ) and forwards M ( ) to s. If the counter associated to P ( ) does not agree with c -1, this means that, before receiving M , the node has received a new instance of P ( ) with lower counter. But then the information associated to P ( ) in the node's memory do not correspond to the information associated to M ( ), and thus M ( ) must be discarded. However, the node will eventually receive a new instance of M ( ) with new information.

Set F := f + f -g; Set C := c + c + 1; Store (Id,
Here is the algorithm for the treatment of matched seeds. The input is a message of the form (M ( ), Id, c, C, F, t) received from node y, and g denotes the fees of the node performing the task:

if = 0 then Look for P (0) in memory. if (P (0), c , s, f, a) is in memory then if c = c -1 then Exit program; if s = 0 then
Store (Id, y, C, F ) in the special match tree else Store (Id, y) in the general match tree; Send (M ( ),

Id, c -1, C, F ) to s. if = 1 then Look for P (1) in memory. if (P (1), c , s, f, a) is in memory then if c = c -1 then Exit program; Store (Id, s) in memory. if s = 0 then Send (M ( ), Id, c -1, C, F, t) to s.

Algorithm 3: Treatment of matched seeds

After some time, Alice will have received several matched seeds, stored in her special match tree. She now chooses one (say, the one with the lowest fees), which is stored as (Id, y, C, F ). Note that Alice can recover the amount of fees she will have to pay by computing 2f max -F . This number is bounded by 2f max , but not by f max . If Alice is not willing to pay up to 2f max in fees, then she can choose to replace f max by fmax 2 at the beginning of the pheromone phase. To launch the confirmation phase, Alice generates a list of random numbers l 0 , which will serve for the final counter check. Alice then sends the confirmation seed (Id, l := l 0 , t) to y. This starts the confirmation phase of the ant routing protocol.

Here is the algorithm performed by a node after receiving the confirmation seed (Id, l, t):

Look for the match identifier Id in the match tree; if (Id, s) is in the match tree and s = 0 then Generate a random integer check.

Append check to l. Store (Id, s, check) in the confirmation tree; Send (Id, l, t) to s;

Algorithm 4: Treatment of confirmed seeds Remember that the "s" in the matched seed (Id, s, t) refers to the sender of the pheromone seed from which Id was made, and that s = 0 only for Bob and Alice. Therefore, the "s = 0" clause in algorithm 4 states that the algorithm is executed by every intermediary node but not by Bob. When Bob receives (Id, l, t), then Bob sends l to Alice. Alice then checks that the number of random numbers which were appended to l is equal to C -2c 0 (note that the number of intermediary nodes between Alice and Bob is C -2c 0 ). If this is not the case, this means that one of the nodes on the route indicated by Id is a cheater. Alice then chooses another route: she chooses another "Id" seed in her special match memory and starts a new confirmation phase with this new "Id".

If the number of random numbers appended to l matches C, then Alice removes l 0 from l. She appends a new list of random numbers l 1 at the end of l and sends (Id, l, t) to y. Then each node on the path checks that the first number in l is the one that they generated, i.e each node follows the following algorithm: Look for Id in the confirmation tree; if (Id, s, check) is in the confirmation tree and s = 0 then if check = l[0] then Remove check from l; Send (Id, l, t) to s;

Algorithm 5: counter check round

When Bob receives (Id, l, t), he sends a message to Alice telling her that she can proceed with the payment. Note that the list l 1 that has been appened to l at the start of the counter check round is here so that nodes don't know the lenght of the payment route. In particular, no node knows that Alice is paying Bob. Remark 3.2: One way of reducing the workload on the network would be to use a variant of the ant routing algorithm which we just presented. In this variant, only Alice, and not Bob, sends pheromone seeds. Bob then waits until he receives the pheromone seed from Alice. Bob may receive several seeds, each indicating a different route. Bob can then communicate the information he has on each of these routes to Alice, who then chooses one of them. Bob then creates the match himself from the pheromone seed chosen by Alice, and sends the matched seed back to Alice though the chosen route.

Note that this variant is only viable if Alice trusts Bob. Indeed, since Bob knows the remaining fees for each seed he receives, he could cheat Alice by taking all the remaining fees for himself.

Robustness of ant routing

Payment routing depending on knowledge of the network threatens decentralization. If knowledge of the network is required for payment, some nodes may choose to delegate the task of gathering knowledge to other nodes. This can lead to the emergence of "hub" nodes which centralize most routing tasks, with most nodes at the periphery. In particular, the use of landmarks encourages this process. This type of network is easy to disrupt: if all payments depend on a small group of nodes, then one only needs to neutralize these nodes to incapacitate the whole network.

An important advantage of the ant routing algorithm is its total decentralization. All nodes in the network performs the exact same task and obey the exact same rules. To have the same protocol rules for all nodes is an important key idea of decentralization. Ant routing requires no knowledge of the geometry of the network, which prevents the emergence of "hub" nodes. This makes the network particularly resilient to attacks: even if an attacker neutralizes a larger part of the network, the remaining part can still function normally provided it remains connected.

It is worth noting that the main reason for the high failure rate of the current routing algorithm in the lightning network is the fact that nodes who compute payment routes only know the capacities of the channels on the network, but they do not know their balances. As a consequence, the paying node often ends up choosing a route which cannot relay the payment due to insufficient available funds in one direction [START_REF] Nowostawski | Imbalance measure and proactive channel rebalancing algorithm for the Lightning Network[END_REF]. Ant routing solves this problem by making sure that every channel on the path has sufficient funds in the desired direction. Indeed, during the pheromone phase, a node will forward the seed to a neighbor only if the funds available on their channel is sufficient. As a consequence, Alice knows that, for every match which she receives, the channels on the path indicated by the match have enough funds to forward her payment.

Note also that ant routing addresses some concerns about the privacy of lightning transactions which have been raised in [START_REF] Beres | Benczur A Cryptoeconomic Traffic Analysis of Bitcoins Lightning Network[END_REF]. The authors of [START_REF] Beres | Benczur A Cryptoeconomic Traffic Analysis of Bitcoins Lightning Network[END_REF] noticed that many LN transactions only have one intermediary node between payer and payee, which means that the intermediary node knows their identities. Ant routing solves this problem by offering several possible path to Alice. Thanks to the counter, Alice knows the length of each path indicated by a match, and she can choose a path of length at least 3 if she wants to preserve her privacy.

A malicious node may attempt to disturb the network by cheating on the counter. Indeed, a malicious node may add a negative counter to a pheromone seed to make the path more attractive. Setting very small fees also increases the chances of Alice choosing this path. The malicious node could then refuse to transmit the payment, thus disturbing the network. Note however that, thanks to the counter check phase which we added at the end of ant routing, Alice will discover the presence of a malicious node before sending the payment. Because the ant routing algorithm usually returns several matched seeds to Alice, she can then choose another route, avoiding the malicious node. If Alice sees that the confirmation phase, the counter check phase or the payment itself did not terminate successfully, she can send a message to the other nodes of the path to warn them of the presence of a malicious node. If a node notices frequent problems with attempted payments through one of its neighbors, it can decide to stop forwarding pheromone seeds throught him or even to close the payment channel. In this way, the malicious node will eventually be de facto isolated and rejected from the network, and will not be able to disturb it any longer. The same will happen with a denial of service attack by nodes that respect all the rules of the protocol but in the last moment refuse to collaborate in establishing the payment. Therefore, each node has interest in keeping historical data and statistics on the performance of its neighbors to avoid being connected to dishonest nodes. In this sense, the network behaves more like an ant colony since the traces left by older payments will reinforce the best neighbors.

Life time of seeds

The seeds are only useful for the routing task for a transaction, and must therefore be kept only a short time in memory. This raises the question of the life time of seeds: how long should the seeds be kept in memory? They need to be kept long enough to allow the routing task to be completed, but as short as possible in order to reduce memory usage.

To determine the optimal seed life time, we need an estimate of how long it will take to Alice to receive matched seeds. This depends on the bandwith for data propagation on the Lightning Network. We can have an approximate estimate using the Bitcoin network as a proxy for the lightning network. Both networks are topologically of the same nature, more precisely, they are well-connected networks. Also seeds in ant routing do propagate faster through the network than bitcoin transaction on the Bitcoin network. This is due to the fact that pheromone seeds are much smaller than bitcoin transactions, but also because the local node process of transactions in Bitcoin nodes is much heavier than the process of pheromone seeds. It follows that the speed of transaction propagation on the Bitcoin network gives us a generous upper bound on the speed of pheromone propagation on the Lightning Network. We found on [19] that, in 2014, it took around 0.8 seconds for a transaction to reach 50% of the nodes in the Bitcoin network. This is in accordance with [START_REF] Naumenko | Bandwidthefficient transaction relay in Bitcoin[END_REF] (See their fig. 16). It follows that we make the conservative assumption that in average a pheromone seed reaches 50% of nodes in 0.8 seconds. Assuming the initial independence of propagation of Alice and Bob seed, for a given node, the probability to have a match after 0.8 seconds is 0.5 2 = 0.25 and the probability that there is a match somewhere in the network after 0.8 seconds is 1 -0.75 N where N is the number of nodes. For N ≥ 32, this probability is more than 99.99%. Now, if we assume that both Alice's pheromone and Bob's pheromone have reached 10% of the nodes in 0.5 seconds, then, the probability to have a match at this date is 1 -0.99 N which is greater than 99.99% when N ≥ 1000 which is already the case today. The exact distribution of the time it takes to have a first match depends on the network topology, but in view of these numbers it is reasonable to assume the expected unmatched time cycle of a pheromone seed to be about 0.5 seconds. Obviously, this may be higher when Alice or Bob do have a bad connectivity to the network, but this situation is neglectable if the average node is well connected as we assume. Note also that this estimate implies that the expected duration time for the whole routing task to be completed is less than 1 second.

A general maximum capacity estimate

We can develop the previous argument using the Bitcoin network as a proxy for estimating the maximum network capacity of an arbitrary network with similar characteristics. We first estimate in an elementary way the maximum network capacity of the Bitcoin network. We assume instant propagation of the data across the network and that the local nodes workload time for the propagation of a transaction is neglectable. The estimate remains valid if there is no lag caused by the local workload of nodes. We consider several random variables, for t ≥ 0,

• N (t) number of blocks mined by the network at time t, N (0) = 0.

• L(t) number of transactions created by the network at time t, L(0) = 0.

• M (t) mempool size in Bytes at time t, M (0) = M 0 .

• B(b) size in Bytes of the block number b.

• m(x) size in Bytes of transaction x.

• t(x) time when transaction x was created.

Note that L, M , N are random process, and L, N are Poisson processes [START_REF] Grunspan | Ant routing algorithm for the Lightning Network[END_REF]. The distribution of M (t) depends on the network condition. At t = 0 we start counting blocks B 1 , B 2 , . . . and transactions created x 1 , x 2 , . . . from this moment and the initial condition M (0) = M 0 . We have

M (t) = M 0 + L(t) k=1 m(x k ) - N (t) k=1 B(b k ) .
In the steady regime of maximum capacity, M (t) is constant, M (t) = M 0 . Taking expected values in the precedent equation, we get, using Wald's Theorem, B max m 0 τ 0 where l 0 is the maximum number of transactions per second, B max is the maximum block size, m 0 is the average size of a transaction, and τ 0 is the average inter-block time.

0 = E[L(t)]E[m] -E[N (t)]E[B] thus E[L(t)] = E[N (t)]E[B] E[m] We have, E[N (t)] = t/τ
The arguments given to derive the above formula are quite general and apply to any network with similar characteristics as the Bitcoin network.

Application (Bitcoin network):

We can apply the precedent formula to the Bitcoin network. We have τ 0 = 10 min (slightly smaller when difficulty is increasing). Also, before segwit improvement and neglecting the block header size of 80B, B max = 1 MB. Typical Bitcoin transactions have a size of m 0 = 250 B. We remind that one bitcoin transaction can contain several financial transactions and the size depends sensitively in the number of inputs and outputs. From this we get l BTC = 6.67 tx/sec for the maximum number of typical transactions per second in the Bitcoin network. The minimal size of a transaction is 61 B (or 63 B for a coinbase transaction, but this is neglectable, see [START_REF] Giorgiadis | How many transactions per second can bitcoin really handle ? Theoretically[END_REF]) then we get l BTC = 27.3 tx/sec Application (Monero network): Our formula applies directly. The maximum block size is set to M 0 = 1 MB, the current average size of a transaction is m 0 = 550 B and the average interblock time of τ 0 = 120 sec. Our formula gives l XMR = 15.15 tx/sec for the maximum number of transactions per second in the Monero network.

Application (Ethereum network):

We apply the precedent ideas to the Ethereum network. The Ethereum protocol imposes no size limit on blocks or transactions, but the miners set a gas limit G max for the blocks, currently set at G max = 10 7 units of gas, that is the total sum of gas for the transactions in the block. The gas of a transaction roughly measures the complexity of the computations in the smart contracts in Ethereum transactions. Indeed one line of code costs 1 gas unit, hence there is some correlation between the gas of a transaction and its size. But the proper metric to measure the network capacity is by using our formula where we replace the B max by G max , and m 0 by the average gas g 0 required by a transaction. The formula for the maximum number of transactions per second is

l ET H = G max g 0 τ 0
We currently have τ 0 = 15 sec. Observe that the full capacity of the network can be reached by a maximum of basic transactions with minimal gas, or by a few transactions with maximal gas. For g 0 = g min = 21.000 we have

l ET H = 31.75 tx/sec
For g 0 = g max = 200.000 we have

l ET H = 3.33 tx/sec
Currently, the observed historical maximum block size, according to the block explorer Etherscan, is 36 630 B. Note that this represents 1.46 MB size per 10 min. The average Ethereum transactions size is about m 0 = 500 B (not counting data volume necessary for the smart contract). with these figures, applying our formula we get

l ET H = 4.88 tx/sec
for the maximum number of transaction per seconds assuming a maximum size block of 36 630B. Obviously this size limit is not set by the protocol, but the practical limit has the same order of magnitude. Ethereum has similar scaling problems than Bitcoin, and this is reflected by the current heavy size of its full blockchain.

Application (Ant Routing): The same argument leading to the formula applies to the Lightning Network running the Ant Routing protocol. This time we denote by M 0 is the maximum size of the local mempool at each node. Let µ 0 the average size of data propagated through all the network for each transactions, essentially unmatched and matched pheromone seeds so µ 0 100 B. Let η the average life time of most data in the Lightning network, we can take the conservative figure of η = 2 sec. We have, l AR = M 0 τ 0 η for the number of transactions per second of the Lightning Network running on Ant Routing. For the conservative figures choosen, we have

l AR = M 0 200
For example, for a modest mempool of M 0 = 20 MB we get l AR = 10.000 tx/sec As we will see in the next sections, the numerical simulations of the local process time of seeds at nodes allow for a flow of 10 6 tx/sec with no impact on the propagation and matching time, thus the network can process an order of 10 6 tx/sec.

AVL trees

In this section we describe the structure we choose in later sections to implement the ant routing protocol: AVL trees. AVL trees were introduced in [START_REF] Adelson-Velski | An algorithm for the organization of information[END_REF] We first fix some notations. If T is a binary tree, we denote by h(T ) the height of T . If x is a node of T , we denote by T x the subtree of T generated by x. T l x denotes the subtree generated by the left child of x, and T r

x denotes the subtree of T generated by the right child of x. If x has no left child (respectively, right child), we say that its left child (respectively, right child) is NULL.

A binary search tree is a binary tree T such that:

1. Every node of T is labelled with an integer.

2. For every nodes x, y of T respectively labeled by the integers n and m, we have

y ∈ T l x ⇒ m < n and y ∈ T r x ⇒ m > n. If T is a binary search tree, we say that T is balanced if for every x ∈ T , |h(T l x ) -h(T r x )| ≤ 1.
An AVL tree is a balanced binary search tree. The following is a look-up algorithm for a binary search tree. It takes an integer n as entry, and returns the node of T labeled by n if it exists, and returns NULL if no node of T is labeled by n. Once the lookup is done, insertion in a binary search tree can be done fast. Here

T 2 T 1 y z T 3 T 2 T 1 Right rotation z y T 1 T 2 T 3 y z T 3 T 2 T 1 Left rotation
Assume that T is balanced, and assumed that we now insert w in T following algorithm 7. Assume further that, after this insertion, T has become unbalanced. We can re-balance T by performing rotations on certain nodes of T . Starting from w, move up towards the root of T . We denote by z the first unbalanced node which we encounter on this path. Let y be the heigher child of z and x the heigher child of y. There are four possible configurations for the relative positions of x, y and z, as shown by Figure 3. To each configuration, we associate a sequence of rotations, shown in Figure 3. These rotations transform T z into a balanced tree. It is easy to show that the new tree obtained from T z by these rotations has the same height as T z had before inserting w. Since T was balanced before inserting w, it follows that T is again balanced once the rotations have been performed.

T 3 x T 1 T 2 y z T 4 T 3 x T 1 T 2 Right rotation z T 4 y T 3 x T 1 T 2 z T 4 x T 3 y T 2 T 1 Left rotation x z y T 3 T 4 T 2 T 1 Right rotation z y T 1 T 4 x T 2 T 3 z x T 1 y T 2 T 3 T 4 Right rotation x y z T 3 T 4 T 2 T 1 z y T 1 T 4 x T 2 T 3 y x T 4 T 3 z T 1 T 2 Left rotation
Here is a modified version of algorithm 7 which gives the insertion algorithm for AVL trees:

Implementation of ant routing

We saw earlier that the main task of a node is to manage a set of seeds. The node must frequently operate a look-up on its set of stored seeds and sometimes insert a new seed. It is therefore important to use a data structure allowing fast look-up and insertion. For this reason, we chose AVL trees as the base structure for storing seeds.

A node must store three types of seeds: pheromone, matched and confirmed. Each of these is stored in a separate tree.

We focus on how pheromone seeds are stored and managed. Let η be the life time of seeds (in seconds), and set k := η 0.1 . Pheromone seeds are stored in a tree T . The root of T has k + 1-many children. Each of these children is the root of an AVL tree. We denote by T 0 , T 1 , . . . , T k these subtrees of T . Each T i corresponds to a time interval I i := [t 0 + i * 0.1, t 0 + (i + 1) * 0.1[. A seed with timestamp t is stored in the tree T i such that t ∈ I i . If the node receives a seed with a timestamp outside of the time interval [t 0 , t 0 + (k + 1) * 0.1[, then the seed is discarded. At time t 1 := t 0 + (k + 1) * 0.1, the node erases the tree T 0 , which contains seeds older than η, and creates a new tree T k+1 . This new tree will contain the seeds with timestamp in [t 1 , t 1 + 0.1[. At time t 1 + 0.1, the node will erase T 1 , create T k+2 , and the process continues.

Each T i is an AVL tree labeled by seeds. Each node of the tree contains the following fields:

• An integer seed. This is the random number S chosen by Alice and Bob. This also serves as the label of the node.

• An integer amount, indicating the amount of the transaction.

• A boolean pheromone0. The value is true if and only if P (0) has been received.

• A boolean pheromone1. The value is true if and only if P (1) has been received.

• An integer f ees0, giving the remaining fees associated to P (0) if P (0) was received, and set to 0 otherwise.

• An integer f ees1, giving the remaining fees associated to P (1) if P (1) was received, and set to 0 otherwise.

• An integer counter0. This is the counter associated to P (0), set to 0 if P (0) was never received.

• An integer counter1. This is the counter associate to P (1), set to 0 if P (1) was never received.

• An integer sender0. This is the node which sent P (0), set to 0 if P (0) was never received.

• An integer sender1. This is the node which sent P (1), set to 0 if P (1) was never received.

• A pointer lef t_child.

• A pointer right_child.

This describes the pheromone tree. The match tree is built in a similar way. The only difference between pheromone and match trees resides in the structure of the nodes. In the match tree, each tree T i is labeled with a match identifier Id. Each node of T i contains the following fields:

• An integer Id (match identifier).

• An integer target.

• A pointer lef t_child.

• A pointer right_child.

The confirmation tree is similar to the pheromone and the match tree, except for the structure of nodes. Each node of the confirmation tree contains the following fields:

• An integer Id (match identifier).

• An integer target.

• An integer check.

• A pointer lef t_child.

• A pointer right_child.

We now give an estimate of the memory space used by the seeds with this implementation. The following 2N . We have n = λη, where λ is the rate of incoming transactions and η the life time of seeds. If we take λ = 10000 and η = 2, then we get n = 20000. For seeds of length 8 Bytes we have N = 2 64 . Therefore, the probability of having a collision at a given time is p (20000) . The probability of having a collision in 100

years is then 1 -(1 -(20000) 2 2 65
) 3600×24×31×12×100 , which is approximately 3%. If one wishes to improve these odds, one can increase the length of seeds to 9 Bytes. In that case, the probability of having a collision in 100 years is 1

-(1 - (20000) 2 2 82
) 3600×24×31×12×100 , which is approximately 2.10 -5 . Note that the simulations whose results we present in Section 9 were done with seeds of size 8 Bytes. However, increasing the length of seeds to 9 Bytes will have a negligeable effect on the computation time needed for the treatment of seeds. Now let us compute the total memory M taken in one node for the routing task. For one routing task, a node stores at most one pheromone seed and one confirmed seed, but potentially several matched seeds. Therefore, The memory taken in a node for one routing task is upper-bounded by 34 + 25r + 33 Bytes, where r is the number of matched received. Let λ be the rate of transactions, i.e. the average number of transactions performed on the network at each second. Then the number of seeds kept in memory by a node is at most λη, where η is the life time of seeds, so the maximal amount of memory taken is λη(34 + 25r + 33)).

We argued above that we can expect to set η := 2. Setting λ = 10000, we get a M = 20000 × (67 + 25r). For smaller, less connected nodes, r should take small values. For r ≤ 8, we get 2MB≤ M ≤ 4MB. For bigger nodes, r may take bigger values, in which case we get (for r > 8) M 500000r = 0.5rMB.

Finally, we want to estimate the necessary bandwidth for the propagation of pheromones. Remember that pheromone seeds are relayed as messages of the form (P, c, f, a, t) (see Section 3.1). The size in Bytes of one such message is given by the following table :   pheromone seed counter fees amount timestamp total 8

1 4 4 1 16
With a transaction rate of λ = 10000, this means we need a bandwidth of 16 × 10000 Bytes per second, i.e 160kB/s. The parameter amount above is the amount of the transaction. By comparison with the Bitcoin network, 16 Bytes is half the size of the hash of a Bitcoin transaction that is sent to nodes in an "inventory message" to announce a new transaction. See [START_REF] Naumenko | Bandwidthefficient transaction relay in Bitcoin[END_REF][START_REF] Bakshi | TxProbe: Discovering Bitcoin's Network Topology Using Orphan Transactions[END_REF] for details on bitcoin transactions propagation. Remark 8.1: Note that a standard timestamp like the unix timestamp is 4 Bytes long. However, we propose here to use timestamps of length 1 Byte. Here is how we think timestamps should work in ant routing: each timestamp indicates a time interval of 0.1 seconds modulo 20 seconds. Since there are only 200 such time intervals within 20 seconds, 1 Byte is enough to express every possible timestamp. We argue that these small timestamps are enough to make ant routing function. Because seeds are stored in trees each corresponding to a time interval of 0.1 seconds, it is indeed enough to have timestamps with precision 0.1 second. Moreover, we argued in section 5 that the life time of seeds can be chosen to be 2 seconds. This means that every seed can be removed after staying more than 2 seconds in memory. It follows that couting timestamps modulo 20 seconds is engouh to manage seeds.

Estimating scalability

We address now the following question: is the ant routing protocol compatible with the goal of solving bitcoin's scalability problem? In other words, how many routing requests per second can the network process using ant routing? In view of the arguments given in section 6, we answer this question by computing the time taken by a node to process all incoming routing requests. This is given by formula (2) below, which depends on the rate λ of transactions. In section 9.2, we give the numerical values for the parameters appearing in formula (2), which we obtained experimentally. This allows us to give a numerical estimate of the maximal transaction rate which the network can sustain.

Formula

We now want to estimate the time taken by a node to perform the routing task. We showed in Section 7 that look-up and insertion in an AVL tree both run in logarithmic time. The operation of deleting a tree is linear in N . We respectively denote by α, β and γ the numbers such that, for an AVL tree T with N -many nodes, look-up in T runs in α log 2 (N ) seconds, Insertion in T runs in β log 2 (N ) seconds, and deleting the whole tree takes γN seconds.

Let us estimate the time taken by a node to process all pheromone seeds for one routing task. We denote by λ the rate of transactions, i.e. the number of transactions performed per second. In our implementation of ant routing given in Section 8, the tree containing pheromone seeds is split into k + 1-many subtrees. We can assume that the routing tasks arrive at a constant rate, so that each subtree has the same number of nodes. In that case, each subtree has λ 10 -many nodes. The node will only have to perform one insertion of pheromone seed, but may have to perform several look-ups. Let p be the number of look-ups to be performed. Then the total time taken to process the pheromone seeds of one routing task is pα log 2 ( λ 10 ) + β log 2 ( λ 10 ). Now let us consider the match phase. Now the trees containing the matches are labelled by the identifier Id of the match. In general, a node may receive several matches produced by the same pheromone seed. Denote by m the average number of matches created by one pheromone seed and received by a node. The node will need to perform m-many insertions (one for each match received) on the match tree, but only one look-up (the look-up will be performed during the confirmation phase). The total time taken to process matched seeds is on average α log 2 (m λ 10 ) + mβ log 2 (m λ 10 ). Finally, the confirmation seed only needs one insertion and one look-up (the look-up is actually performed during the counter check phase). Note that, for a given transaction, only very few nodes will actually have to process a confirmation seed. Let c denote the probability that a node receives a confirmation seed. The time to process confirmed seeds is then on average c(α log 2 (c λ 10 ) + β log 2 (c λ 10 )). The total time to process one routing task is therefore on average:

Now let us estimate the total time that a node must dedicate to the routing task to process all the routing demands that arise in the span of one second. The node has to process on average λ-many routing tasks, so the time taken to process seeds is λT (λ). We must also take into account the time taken to clean old seeds. This is done by deleting a tree every 0.1 seconds. The time dedicated to cleaning the mempool is therefore γλ(1 + m + c). Thus, the total time dedicated to the ant routing algorithm is

T (λ) := λ(T (λ) + γ(1 + m + c)) (2)
Now we just need to estimate the value of the coefficients α, β, γ, p, m, c.

Experimental result

We do determine α, β and γ experimentally. We have implemented the work of a node with a C program following Section 8. Our program treats seeds stored in an AVL tree. We use a look-up and insertion algorithm in our program that is a recursive Implementation of algorithms 6 and 8. Our program first randomly generates a mempool of a given size N . The program then inserts a new randomly generated seed in the tree and records the time it takes to the program to perform this insertion. We ran the program for different values of N in the range from 100 to 100000. For each N , we ran a Montecarlo simulation executing the program with 1000 trials. We also did the same for the tasks of look-up and cleaning of the mempool. The experimental results are shown in Figure 4 below. This allowed us to estimate the values of α, β and γ appearing in formula [START_REF] Awerbuch | Reducing complexities of the distributed max-flow and breadth-firstsearch algorithms by means of network synchronization[END_REF]. Experimentally, we find α = 0.7 × 10 -6 , β = 1.1 × 10 -6 and γ = 8.2 × 10 -8 . Now we come back to formula [START_REF] Awerbuch | Reducing complexities of the distributed max-flow and breadth-firstsearch algorithms by means of network synchronization[END_REF]. We can now determine the maximum number of routing tasks which a node can perform per second. In other words, the maximum λ such that T (λ) < 1. The value of this maximal λ depends on parameters p, m and c. Note that these parameters essentially depend on the centrality and connectivity of the node.

For most nodes, we can assume that c is negligible, and that m = 1 on average, so it remains to determine p. It is established in [START_REF] Seres | Topological analysis of Bitcoin's Lightning Network[END_REF] that the average number of channels per node is 7. This means that p is bounded by 8. In the worst case, we thus have T (λ) = (8α + 2β) log 2 ( λ 10 ) = 7.8 log 2 ( λ 10 )10 -6 and T (λ) = λ(7.8 log 2 ( λ 10 )10 -6 + 8.2 × 10 -8 × 2). We find λ max 12500.

Remark 9.1:

• This result means that an average node can process up 12500 tx per second. However, it is important to note that it is not necessary that all nodes process all incoming routing tasks. Indeed, since the network is well-connected, a routing task should still be completed successfully even if only 50 percent of the network is performing the task. This means that we can hope that the network could sustain up to 25000 tx per second.

• The above estimate is valid for nodes with low or average connectivity. However, for big nodes, p can be much higher, the value of c might be non-negligible, and m might take an average value higher than 1. It would take a deeper analysis of the network to estimate the capacity of these nodes to process all incoming routing tasks.

The C code used in this section for estimating the capacity of Ant Routing algorithm is available at : https://github.com/gabrielLehericy/Ant-routing-simulation

  0 where τ 0 is the average inter-block time. At steady maximum capacity regime E[B] is constant and equal to the maximum block size, E[B] = B max . Let m 0 = E[m] the expected size of a transaction. These calculations show the following result: Theorem 6.1 With the previous assumptioons, at steady maximum capacity regime for typical transactions we have l 0 =

input:Algorithm 6 :

 6 Integer n, tree T output : lookup(n, T ):=the node of T labeled by n if it exists, "NULL" otherwise Set node := root(T ); while node = N U LL do if n < label(node) then node := lef t_child(node); else if n > label(node) then node := right_child(node); else return node; end Return node; Look-up algorithm for binary search tree.

Figure 2 :

 2 Figure 2: Rotations at node z.

Figure 3 :

 3 Figure 3: Rebalancing the tree

2

 2

T

  (λ) := (pα + β) log 2 ( λ 10 ) + (α + mβ) log 2 (m λ 10 ) + c(α + β) log 2 (c λ 10 )

Figure 4 :

 4 Figure 4: Insertion, look-up and cleaning time depending on the size of the mempool

  1}. The counter c is decreased by 1 at each hop. When a node receives a matched seed (M ( )

s ) in the match tree; Send (M (0), Id, c, C, F, t) to s; Send (M (1), Id, c , C, F, t) to s ; Algorithm 2: Match creation Matched seeds are forwarded as messages of the form (M ( ), Id, c, C, F, t), ∈ {0,

  table gives the size in Bytes of a node of each tree: Note also that biggest nodes have around 100 neighbors, which is why 1 Byte is enough to store the sender or target. Pointers typically have size 8 Bytes, which is why a tree node needs 16 Bytes to store the addresses of its children. We can check if the length of 8 Bytes for seeds is sufficient to avoid collisions. We can estimate the probability of collisions occuring by using an approximation formula of the birthday problem. If n is the number of seeds simultaneously present in the network and N the number of all possible seeds, then the probability p of having a collision at a given time is p

	seed counter amount fees sender/target children check total
	pheromone 8	1	4	4	1	16	0	34
	match	8	0	0	0	1	16	0	25
	confirmation 8	0	0	0	1	16	8	33
	n 2

A network with only one directional channels is theoretically more limited, but in practical terms can be useful since most of the channels are used unidirectionnally.

The value of c0 can be chosen between 2 6 = 64 and 2 7 = 128. By doing this, we only dedicate 1 Byte to the counter, but still allow for 128 intermediary nodes between Alice and Bob, which is enough.

Acknowledgement

The two first authors were partially supported by the FUI Moneytrack project joined between INRIA and Pôle Universitaire Léonard de Vinci.

Now we discuss the run time of these algorithms. Let N be the number of nodes in T . If T is not assumed to be balanced, then in the worst case algorithms 6 and 7 could run in time O(N ). However, if T is an AVL tree, then algorithms 6 and 7 are guaranteed to run in time O(log 2 (N )).

Algorithm 7 is a naive insertion algorithm. This naive algorithm could be problematic, as it takes no account of the height of the newly generated tree and could thus result in an unbalanced tree if repeated enough times. This means we cannot use algorithm 7 for insertion in AVL trees. Fortunately, there is a workaround to this problem. More precisely, we can slightly change the insertion algorithm so that the tree remains balanced. We now describe the insertion algorithm for AVL trees. We first need to explain how an unbalanced tree can be rebalanced.

Re-balancing a tree is done via operations on the tree called rotations. A rotation at a node z is one of the two operations shown in Figure 2

Algorithm 8: AVL insertion

Now let us compute the running time of this algorithm. The algorithm starts with the naive insertion, which runs in time O(log 2 (N )). We then have to move back up the tree to update the heights of each node until we find the first unbalanced node. In the worst case, this is done in time O(log 2 (N )). Finally, the rotation operations are done in O(1) time. Therefore, this algorithm runs in time O(log 2 (N )). This shows that AVL trees allow for fast look-up and insertion; more precisely, these operations are performed in logarithmic time.


Yiming Wu
email: wu@sap.ist.i.kyoto-u.ac.jp

Tristan Carsault
email: carsault@ircam.fr

Kazuyoshi Yoshii
email: yoshii@sap.ist.i.kyoto-u.ac.jp

Automatic Chord Estimation Based on a Frame-wise Convolutional Recurrent Neural Network with Non-Aligned Annotations

Keywords: Automatic chord estimation, forced alignment, HMM, CNN, and RNN

Automatic Chord Estimation Based on a Frame-wise

Convolutional Recurrent Neural Network with Non-Aligned Annotations

I. INTRODUCTION

Harmonic progression is an important property of music in western music theory, which provides rich information about the characteristics of the musical work. In the Music Information Retrieval (MIR) community, Automatic Chord Estimation (ACE) [START_REF] Müller | Fundamentals of music processing: Audio, analysis, algorithms, applications[END_REF] has been a long-lasting research theme. Modelling and automating the estimation process has still been a challenging task due to the complexity of music signals and the implicit relationships between the chord labels.

A standard approach to ACE is to extract acoustic features that represent the harmonic characteristics of music signals and then train some machine learning models in a data-driven manner. Although the performance of ACE has recently been improved remarkably [START_REF] Mcvicar | Automatic chord estimation from audio: A review of the state of the art[END_REF], conventional studies stand on the assumption that time-aligned chord annotations are available as supervised data. Producing such annotations is costly, since manual chord annotation requires careful judgments based on knowledge on musical theories, and time alignments have to be carefully given to each chord symbol. This makes it difficult to extend the scale of supervised data efficiently, and the limitation becomes especially distinct when Deep Neural Networks (DNNs) are introduced for estimating the posteriors.

In automatic speech recognition (ASR), which has a similar task formulation, a recognition model is typically trained on weaker labelled data. Only a sequence of symbols (phonemes or words) is given for the audio signal of each utterance without any time alignment information. In order to train a DNN model such as the HMM-DNN hybrid model [START_REF] Hinton | Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups[END_REF] into the framework of ASR, the annotated symbols are firstly aligned to frame-wise acoustic feature sequences with a trained HMM (forced-alignment). Then a DNN is trained for accurately estimating the label posteriors at each frame.

Inspired by such an approach to ASR, in this paper we propose an ACE method based on a two-step training strategy (Fig. 1). Our method extracts frame-wise chroma vectors from music signals by using a state-of-the-art DNN-based feature extractor [START_REF] Wu | Automatic audio chord recognition with MIDI-trained deep feature and BLSTM-CRF sequence decoding model[END_REF]. In the training phase, an HMM that represents chord labels as latent and feature vectors as observed variables is trained for estimating the time alignment between a feature sequence and the corresponding non-aligned chord annotations (Fig. 2). A frame-wise classifier based on a Convolutional Recurrent Neural Network (CRNN) is then trained on the timealigned pairs of feature sequences and chord label sequences. In the test phase, the trained classifier is used for estimating the posterior probabilities of chord labels at each frame from a given music signal and another HMM is used for estimating the optimal path of chord labels.

The main contribution of this paper is to show that nonaligned chord annotations are useful for effectively training machine-learning based ACE models. Furthermore, we show that by using a sufficient amount of training data with nonaligned annotations, the trained DNN model can reach or even outperform the DNN models trained with only ground-truth time-aligned chord annotations. To the best of our knowledge, this is the first attempt in ACE to train DNN model on nonaligned chord annotations.

II. RELATED WORK Some common methodologies have been developed in order to extract effective harmonic features from the audio signal. The chroma vector, which indicates the relative intensities of chromatic pitch classes in each audio frame [START_REF] Fujishima | Realtime chord recognition of musical sound: A system using common lisp music[END_REF], is the most representative and has been widely employed. Based on the characteristics of harmonic structures in the frequency domain, many effective techniques to extract chroma features have been proposed (e.g., [START_REF] Mauch | Approximate note transcription for the improved identification of difficult chords[END_REF], [START_REF] Gómez | Tonal description of music audio signals[END_REF]). Furthermore, data-driven approaches have recently been considered to be promising [START_REF] Wu | Automatic audio chord recognition with MIDI-trained deep feature and BLSTM-CRF sequence decoding model[END_REF], [START_REF] Korzeniowski | Feature learning for chord recognition: The deep chroma extractor[END_REF], [START_REF] Humphrey | Learning a robust Tonnetz-space transform for automatic chord recognition[END_REF].

The core of ACE is to model the translation process from a frame-level domain (harmonic features) to a symbol-level domain (chord labels). Conventionally, the relationships between a feature sequence and a chord label sequence is modeled by a Hidden Markov Model (HMM) [START_REF] Mauch | Approximate note transcription for the improved identification of difficult chords[END_REF], [START_REF] Chen | Chord recognition using duration-explicit hidden Markov models[END_REF]. However, since Humphrey and Bello [START_REF] Humphrey | Rethinking automatic chord recognition with convolutional neural networks[END_REF] proposed a Convolutional Neural Network (CNN) model, discriminative methods that use DNNs for directly estimating a sequence of the posterior probabilities of chord labels have gained a lot of attention [START_REF] Sigtia | Audio chord recognition with a hybrid recurrent neural network[END_REF], [START_REF] Korzeniowski | A fully convolutional deep auditory model for musical chord recognition[END_REF],

A common approach is to estimate the posterior probabilities at the frame level directly from low-level time-frequency representations such as Short-Time Fourier Transform (STFT) or Constant-Q Transform (CQT) spectrograms rather than handcrafted features. A musically-meaningful design of the output of a DNN based on chord theory [START_REF] Mcfee | Structured training for large-vocabulary chord recognition[END_REF], [START_REF] Carsault | Using musical relationships between chord labels in automatic chord extraction tasks[END_REF] and an evenchance training scheme [START_REF] Deng | Large vocabulary automatic chord estimation with an even chance training scheme[END_REF] can improve the performance of ACE, especially when a large chord vocabulary is used and the frequencies of chords are heavily biased. Another approach is to estimate the posterior probabilities at the symbol level. Deng and Kwok [START_REF] Deng | A hybrid Gaussian-HMM-deep learning approach for automatic chord estimation with very large vocabulary[END_REF] proposed a method that uses a pre-trained HMM for estimating chord boundaries and then uses a DNN for estimating a chord for each segment consisting of multiple frames. This method is better at estimating seventh chords than frame-level ACE models.

The conventional methods mentioned above make use of carefully time-aligned chord annotations as supervising data. A number of time-aligned annotation datasets have been released for training and evaluating those models. In the datasets used in MIREX evaluation, for example, more than 1000 annotated pieces are available in total. Considering the other successful domains such as ASR, the amount of the training data is still comparatively small. It is thus natural to expect that there is still room for improving the performance of ACE if a larger amount of training data would be available.

III. PROPOSED METHOD

This section describes the proposed method of ACE based on a CRNN trained from non-aligned chord annotations.

A. Problem Specification

Let X = {x 1 , • • • , x N }
be a frame-level sequence of acoustic features extracted from a music signal, where x n ∈ R D is a D-dimensional feature vector and N is the number of time frames. Let Z = {z 1 , • • • , z N } be a sequence of chord labels, where z n ∈ {0, 1} K is a one-hot vector indicating a chord label in a chord vocabulary of size K. The task of statistical ACE is defined as follows:

Z * = argmax Z p(Z|X), (1)
where Z * is the optimal sequence of chord labels that maximizes the posterior probability p(Z|X).

In this task, we need to estimate both chord symbols and boundaries. Typically, p(Z|X) is evaluated by aligning Z with X at the frame level and estimating the frame-wise posterior probability p(z n |x n ). This is the main reason why time alignment information is required for training an ACE model.

As a primordial step, a DNN-based feature extractor proposed by Wu [4] is used for extracting a sequence of chroma vectors

F = {f 1 , • • • , f N } from the 5-channel Harmonic CQT (HCQT) [18] representation Q = {q 1 , • • • , q N }
of a music signal, where f n ∈ R 36 is a 36-dimensional vector representing the relative intensities of the 12 chromatic pitch classes in lower, middle, and higher frequency ranges, respectively, and q n ∈ R 5×96 is the HCQT coefficients. Each x n contains the two representations of the frame n, i.e., x n = {f n , q n }.

B. HMM-Based Forced Alignment

To synchronize non-aligned chord annotations with a feature sequence F at the frame level, we formulate a frame-wise HMM that represents Z and F as latent and observed variables, respectively, as follows: where z 0 is a dummy state. In this paper we use a von Mises-Fisher distribution as the emission distribution as follows:

p(F, Z) = N n=1 p(z n |z n-1 )p(f n |z n ), (2)
p(f n |z n ) = K k=1 vMF(f n |µ k , λ k ) z nk , (3)
where µ k ∈ R 36 satisfying ||µ k || = 1 and λ k > 0 are a mean direction vector and a concentration parameter, respectively. f n is obtained by scaling f n to satisfy ||f n || = 1. The transition distribution is given by

p(z n |z n-1 ) = K k=1 K k =1 π z n-1,k z nk kk , (4)
where π kk is the transition probability from chord k to chord k . Since this HMM is a frame-level model, the self-transition probabilities are considered to be close to 1. Given a feature sequence F with non-aligned chord annotations (Fig. 2), we estimate a chord sequence Z that maximizes the posterior probability p(Z|F) ∝ p(F, Z). Since the chord transitions in Z are specified by the annotations, in this paper we train a left-to-right HMM by using a Viterbi algorithm. After the HMM is initialized, the HMM searches the optimal state transitions for F and updates the parameters µ, λ, and π in a way of maximum likelihood estimation. These two steps are iterated for several times until convergence. An example of such forced alignment is shown in Fig. 3. Since the likelihood p(f n |z n ) is ambiguous, it is difficult to estimate a sequence of chord labels with the ordinary unconstrained Viterbi algorithm. Nonetheless, when the order of chord symbols is constrained, the HMM can perform the forced alignment accurately. This fact leads to our motivation to train a powerful DNN for ACE based on the annotations aligned by the HMM instead of directly using the HMM for ACE.

C. CRNN-Based Chord Estimation

We use a Convolutional Recurrent Neural Network (CRNN) for estimating a sequence of the posterior probabilities of chord labels Y = {y 1 , • • • , y N } from X. In this study, the chord vocabulary consists of six triad types such as maj, min, diminished, augmented, sus2, and sus4. The output size of the last layer is thus 73 (72 triads plus a no-chord label), i.e., y n ∈ R 73 . As shown in Table I, the two representations F and Q are processed separately at the bottom layers, with a CRNN for Q and a multi-layer bi-directional LSTM network for F. The convolutional layers dealing with the spectrogram Q consists of 10 stacked residual blocks [START_REF] He | Deep residual learning for image recognition[END_REF] with two convolutional layers. The outputs of the two networks are concatenated at the top layer to calculate the final output Y.

The CRNN is trained in a standard way. More specifically, the cross-entropy loss between the target binary sequence Z and the output sequence Y is iteratively minimized by using Adam optimizer [START_REF] Kingma | Adam: A method for stochastic optimization[END_REF]. To improve the generalization capability of the CRNN, we propose a data augmentation technique. In each iteration, the feature sequence F and the corresponding target label sequence Z are pitch-shifted by a random number (up to 12) of semitones. Note that the input spectrogram Q is not shifted. This operation is expected to act as a strong regularization during the training process, encouraging the convolutional layers to focus on the shapes of chords (i.e., chord types) rather than actual pitch information when processing the spectrogram.

D. HMM-Based Postprocessing

The final step of the proposed ACE method is to estimate a sequence of chord symbols with boundary information from a sequence of the frame-wise posterior probabilities of chord labels Y estimated by the CRNN. This is a common smoothing step of existing HMM-based systems [START_REF] Chen | Chord recognition using duration-explicit hidden Markov models[END_REF]. More specifically, we formulate an HMM that has chord labels Z as latent variables and outputs the posterior probabilities Y. The transition probabilities are given by π. Using the Viterbi algorithm, the optimal sequence Z * can be obtained.

An example of the estimated posterior probabilities Y and the final outputs Z * is shown in Fig 4 . Short-duration outliers cannot be avoided if the label with the maximum probability is selected in each frame. The postprocessing step can reduce these outliers and obtain more natural results. IV. EVALUATION This section reports a comparative experiment conducted for evaluating the proposed weakly-supervised method in comparison with the completely supervised method.

A. Experimental Conditions

The frame-level accuracy of ACE for each musical piece is measured by comparing the ground-truth and estimated chord sequences with mir eval library [START_REF] Raffel | mir eval: A transparent implementation of common MIR metrics[END_REF]. The average performance is calculated over the piece-wise accuracies weighed by the numbers of time frames of the musical pieces. We define two different chord vocabularies: the Majmin vocabulary that consists of major (maj) and minor (min) triads plus no chord (25 classes), and the Triads vocabulary that additionally includes augmented (aug), suspended (sus2 and sus4), diminished (dim) triads plus no chord (73 classes).

For evaluation, we use both the Isophonics dataset consisting of 220 songs of Queen, Zweieck, and The Beatles [START_REF] Harte | Towards automatic extraction of harmony information from music signals[END_REF] and the RWC popular music dataset consisting of 100 Japanese popular songs [START_REF] Goto | RWC music database: Popular, classical, and jazz music databases[END_REF] with chord annotations, i.e., 320 songs in total. All the annotations are time-aligned so that the performance can be measured. To investigate the impact of increasing the amount of supervising data for the proposed method, we additionally use as a larger dataset with non-aligned annotations a subset of the Mcgill Billboard dataset [START_REF] Burgoyne | An expert ground truth set for audio chord recognition and music analysis[END_REF] consisting of 731 pieces that are disjoint with the Isophonics and RWC datasets. Using these datasets, we design three different training configurations. In any configuration, the performance is measured on the Isophonics+RWC dataset by performing 5fold cross validation.

1) Isophonics+RWC (time-aligned): The CRNN is trained on the ground-truth time-aligned annotations without using the HMM-based forced alignment. 2) Isophonics+RWC (non-aligned): This is the same as the Isophonics+RWC configuration except that the CRNN is trained on the non-aligned chord annotations by using the HMM-based forced alignment.

B. Experimental Results

The experimental results are listed in Table II. Comparing the first two rows, we observe that when the Isophonics+RWC dataset is used as training data, the weakly supervised method based on the forced-aligned annotations only slightly underperformed the supervised method based on the ground-truth annotations. When the Isophonics+RWC+Billboard dataset with non-aligned annotations are used as training data, the weakly supervised method performed even better than the completely supervised method. This shows that the performance of ACE obtained by the proposed method depends on the size of nonaligned training data, and that the performance limitation of the HMM-based forced alignment can be mitigated by collecting a sufficient amount of weakly-annotated data.

In all cases, the average accuracy of the forced alignment is around 88.5% for the Isophonics dataset and around 86.5% for the RWC dataset. Since the CRNN is trained to emulate the alignment behavior of the HMM, it is natural to think that the accuracy of ACE is upper bounded by the forced alignment accuracy. In fact, interestingly, the weakly-supervised method is still competitive to the state-of-the-art conventional models in estimating chord sequences for unseen data.

The performance differences between the two metrics (Majmin and Triads) are almost the same in all methods. For the Fig. 5. The confusion matrix over the 12 root notes and that over the 6 chord types. In the left matrix, the comparison is done over all frames, while in the right matrix the comparison is done for time frames where the chord roots are correctly estimated.

Isophonics and RWC datasets, the performance differences are around 3% and around 5%, respectively. This indicates that the ability of classifying rarely-used triads other than maj and min is scarcely improved, even though the amount of training data is increased and the regularization technique is used for the training. The confusion matrices are shown in Fig. 5. The CRNN is excellent at estimating the frequently-used maj and min triads, while unreliable in estimating the other triads. In the whole dataset, the total duration of aug or sus2 is nearly 10 minutes, dim is around 20 minutes, and sus4 is up to 1.4 hours. We find that the CRNN trained in the proposed strategy is relatively good at estimating dim, is slightly worse for sus4, and fails to recognize aug and sus2.

The main limitation of the common approach to ACE based on the one-octave chromatic representation is that some chords are hard to distinguish in principle. The pitch classes of sus2 chords, for example, are a subset of those of 9th chords, which are regarded as maj chords in the standard Triads condition. The same is true for sus4 and 11th chords. A reason why the accuracy on dim is better than that on sus4, even though dim appear much less frequently, would be that dim and aug chords are less ambiguous. In addition to the heavily biased distribution of chord types, such ambiguity is considered to affect the accuracy when the traditional flat classification scheme is used, as suggested in [START_REF] Humphrey | Four timely insights on automatic chord estimation[END_REF]. One solution is to fully consider a wider range of octaves instead of compressing frequency spectra into one octave. In chord theory, rare triads are considered to play unique roles in chord progressions, e.g., a sus4 chord implies that a maj chord with the same root note comes next. A language model of chord progressions would be effective to solve the ambiguity.

V. CONCLUSION

This paper proposed a two-step training method that trains a CRNN-based chord estimation model with non-aligned chord annotations, based on an HMM-based forced alignment model that recovers the time alignments of the annotations. We experimentally showed that the model trained in the proposed method is competitive to the ones trained on time-aligned an-notations, and can even outperform the completely supervised model by using a larger amount of non-aligned data. Our study opens up a door to make full use of non-aligned data that can be collected easily from the Web, but has not conventionally been used. To make the estimation results more accurate and musically natural, we plan to integrate a symbol-wise chord language model with the frame-wise estimation model.

Fig. 1 .

 1 Fig. 1. The proposed training strategy based on an HMM for forced alignment and a DNN for automatic chord estimation.

Fig. 2 .

 2 Fig. 2. Time-aligned and non-aligned chord labels. In time-aligned labels, the start and end timing of each chord are annotated in seconds.

Fig. 3 .

 3 Fig. 3. An example of the HMM-based forced alignment. From top to bottom, a sequence of the likelihoods over chord labels, the optimal path estimated by the HMM, the ground-truth time-aligned sequence of chord labels are shown. Chord labels other than major and minor triads are omitted.

Fig. 4 .

 4 Fig. 4. An example of the HMM-based postprocessing. From top to bottom, a sequence of the posterior probabilities over chords estimated by the CRNN, a sequence of chord labels obtained by the frame-wise argmax operation, that obtained by the HMM, and the ground-truth label sequence.

3 )

 3 Isophonics+RWC+Billboard (non-aligned): The CRNN is trained on a larger amount of non-aligned chord annotations (Isophonics+RWC+Billboard dataset) by using the HMM-based forced alignment. In each fold, 80% of the Isophonics+RWC dataset and the Billboard dataset are used for training the CRNN. For comparison, we test two existing ACE methods: a) Chordino [6]: This is a method based on an HMM using the NMF-chroma feature, which is available as a VAMP plugin. As a baseline, we use this method with a pretrained model to analyze the Isophonics+RWC datasets without performing cross-fold validation. b) CNN-CRF [13]: This is the state-of-the-art method based on a fully convolutional acoustic model combined with a conditional random field (CRF), We use a reference code implemented by the author according to the original paper. Since the method estimates major/minor triads only, the scores for Triads are not available.

TABLE I CONFIGURATION

 I OF THE PROPOSED CRNN. The output of each convolutional layer is activated with the ReLU function and then batch-normalized.

	Input: F(N × 36)	Input: Q(N × 5 × 96)
		Convolution 64 × 15 × 3
		Convolution 256 × 3 × 3
		max pooling 3 × 3
		Residual block:
	Bi-directional LSTM ([Convolution 256 × 5 × 5] ×2)
	128 units	×10
	×3 layers	Max pooling 3 × 4
		Convolution 256 × 15 × 7
		Bi-directional LSTM
		128 units
		×4 layers
		Concatenate
	Fully-connected 256 × 73

*

TABLE II EXPERIMENTAL

 II RESULTS ON THE ISOPHONICS AND RWC DATASETS (%).

		Isophonics	RWC
		Majmin Triads Majmin Triads
	Isophonics+RWC (time-aligned annotations)	83.31	79.92	82.24	76.73
	Isophonics+RWC (non-aligned annotations)	82.49	79.44	80.53	76.40
	Isophonics+RWC+Billboard (non-aligned annotations)	83.46	79.94	82.21	76.74
	Chordino [6]	72.21	74.24	78.78	73.66
	CNN-CRF [13]	84.22	N/A	81.68	N/A

ACKNOWLEDGMENT This work was supported in part by JST ACCEL No. JP-MJAC1602, JSPS KAKENHI No. 16H01744, No. 16J05486, and No. 19H04137, Kayamori Foundation, and the Kyoto University Foundation.