Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Antoine Guellier
email: antoine.guellier@irisa.fr

Romaric Ludinard
email: romaric.ludinard@imt-atlantique.fr

UTXOs as a proof of membership for Byzantine Agreement based Cryptocurrencies

The presence of forks in permissionless blockchains is a recurrent issue. So far this has been handled either a posteriori, through local arbitration rules (e.g., "keep the branch which has required the most computational power") which are applied once a fork is present in the blockchain, or a priori, via a Byzantine resilient agreement protocol periodically invoked by a committee of well identified and online nodes. In the former case, local arbitration rules guarantee that if they are correctly applied by a majority of the users of the system, then with high probability forks are progressively resolved, while in latter case, the sequence of Byzantine resilient agreements decide on the unique sequence of blocks to be appended to the blockchain. The question we may legitimately ask is the following one: To prevent the period of uncertainty inherent to optimistic-based solutions, are we doomed to rely on the decisions made by a unique committee whose members are already actively involved in the creation of blocs ? We negatively answer this question by presenting a solution that combines the best features of optimistic and pessimistic approaches: we leverage the presence of users and the "public-key as identities" principle to make users self-organize in small Byzantine resilient committees "around" each new object (i.e., blocks and transactions) to decide on their validity. Once validated, objects can be pushed in the network, appended to the blockchain without fearing any fork nor double spending attacks: we guarantee a "0"-confirmation delay. Additionally, our solution mitigates selfish attacks. We are not aware of any solutions enjoying such features.

I. INTRODUCTION

Blockchains, also called distributed ledgers, initially appeared as the technological solution for the deployment of the Bitcoin digital cryptocurrency system, a secure system, usable by anyone, in a peer-to-peer way, with no trusted third party whatsoever. Blockchains achieve the impressive result of constructing a persistent, distributed, append-only log of transactions, and publicly auditable and writable by anyone in case of permissionless (i.e., public) blockchains. Construction of distributed ledgers typically relies on a sophisticated orchestration of cryptographic primitives, agreement algorithms, and broadcast communication primitives.

To face recurrent double-spending attacks -which are inherent to digital cash systems -blockchains are built so that their records (i.e blocks of transactions) are totally and securely ordered. So far, two main designs exist to totally and securely order blocks: the optimistic and the pessimistic approaches. The optimistic approach mainly consists in regularly running elections among a subset of the nodes of the system (i.e., miners), at the outcome of which, leaders (i.e., successful miners) properly and securely gathers transactions into blocks, with the hope that no concurrent blocks already exist in the system. Transient inconsistencies (i.e., the presence of concurrent forks) are locally handled, but at the expense of a substantially long block confirmation time. For instance Bitcoin guarantees that if a block has been stored for more than one hour in any local copy of the ledger, then it will remain there forever, and at the very same position in the local copies maintained at all the nodes of the system. This holds with very high probability even if up to 10% of the miners are malicious. More recently Ethereum [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF] and Spectre [START_REF] Sompolinsky | SPECTRE: A fast and scalable cryptocurrency protocol[END_REF] have succeeding in decreasing the block confirmation time but at the expense of more involved arbitration rules. The second approach, which we call pessimistic, aims at preventing forks from happening so that once recorded in the ledger, a block will never be pruned. This is achieved by relying on Byzantine resilient agreement algorithms (e.g. [START_REF] Castro | Practical Byzantine Fault Tolerance[END_REF], [START_REF] Kotla | Zyzzyva: Speculative Byzantine Fault Tolerance[END_REF]) fed with all the currently submitted transactions. An already impressive amount of work has been focusing on the properties of those algorithms to securely and totally order transactions in distributed ledgers, but the foremost difference that exists among all these works is related to the essential notion of identity. In consortium blockchains, including RedBelly [START_REF] Crain | Leader/Randomization/Signature)-free Byzantine Consensus for Consortium Blockchains[END_REF] and HyperLedger [START_REF] Androulaki | Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains[END_REF], participants -those who control and manage copies of the blockchain -form a clique of carefully selected institutions with appropriate permissions. In Byzantine-based permissionless blockchains, such as PeerCensus [START_REF] Decker | Bitcoin Meets Strong Consistency[END_REF], Bizcoin [START_REF] Kogias | Enhancing bitcoin security and performance with strong consistency via collective signing[END_REF], or BitcoinNG [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF], those in charge of executing the Byzantine resilient agreement algorithms are selected among all the successful miners. Note that one may be careful in the way miners are selected to form the Byzantine algorithms committees not to violate the system safety [START_REF] Anceaume | Safety Analysis of Bitcoin Improvement Proposals[END_REF].

To summarize, the pessimistic approach achieves an irrevocable decision on the next block to be appended to the permissionless ledger at the cost of running a Byzantinetolerant algorithm among several hundred of nodes for each created block. The optimistic approach guarantees that in presence of forks on the ledger the probability that a given branch will remain in the ledger increases exponentially with the number of blocks appended after it.

Very recently, an elegant pessimistic-based approach to mitigate the presence of blockchain forks has appeared with Algorand [START_REF] Gilad | Algorand: Scaling byzantine agreements for cryptocurrencies[END_REF]. In Algorand, members of the Byzantinetolerant algorithm are selected no more proportionally to their computational power, but proportionally to their stake. Among them, a leader is elected, the one with the largest stake, and handles all the currently submitted transactions. Algorand guarantees that in periods of strong synchrony, the blockchain correctly grows (absence of forks and double-spending), while in presence of variable communication delays, growth is not guaranteed.

In this paper, we propose a solution that borrows ingredients of both approaches to guarantee that once a block, mined in isolation, is declared valid by the system, then it cannot be confronted with any other conflicting block, and thus will irremediably be registered in the ledger. Our solution also guarantees that double-spending attacks are detected and prevented once any conflictual transaction is submitted to the peer-to-peer network. Hence, once a transaction is declared valid by the system, then it cannot be confronted with any other conflicting transaction, relieving sellers of any fraud.

The block validation protocol and the transaction validation one are essential in our design. The core of both protocols relies on Byzantine agreements (BA). BA allows the block validation protocol to reach an agreement on the unique block that can reference an earlier block in the blockchain, and allows the transaction validation protocol to reach an agreement on the unique transaction that can redeem all the unspent transaction outputs (UTXOs) referenced as its inputs. In contrast to all the pessimistic approaches described above (and to the best of our knowledge to all them), BAs are executed "around" the objects to be validated. It briefly means that, when a newly created transaction is submitted to the peer-to-peer network for validation, the transaction validation protocol is executed by a subset of users randomly chosen among those that are (logically) close to the UTXOs referenced in the input of the transaction. Participation of those randomly chosen users is publicly verifiable by anyone. Similarly, when a newly created block is submitted to the network, the block validation protocol is executed by a subset of users randomly chosen among those that are (logically) close to the predecessor block referenced by this block. Participation of those users is also publicly verifiable. As an additional consequence of our design, selfish attacks are mitigated. Since a selfish miner can not create a block without disclosing it, no one is able to built a private sequence of blocks in order to prune the tail of the blockchain. Finally, beyond giving users an incentive to correctly behave, relying on their participation to execute Byzantine agreement protocols allows for greater equality in the management of the blockchain. By the "locality" principle of the validation protocols, participation in the execution of a Byzantine agreement protocol is de facto temporary and unfrequent.

The remainder of the paper is organized as follows. Section II describes the computational and system model adopted in this work and then presents the main features of blocks and transactions in Bitcoin. Section III presents a brief survey of some of the attempts that have been made at solving Bitcoin issues. Section IV presents the key elements that we leverage to derive our solution. Section V describes the orchestration of these elements to validate blocks and transactions. Section VI and Section VII detail implementations of both protocols. Finally, Section VIII concludes.

II. MODEL, TRANSACTIONS AND BLOCKS

A. Model

We assume a large, finite yet unbounded set Π of nodes whose composition may change over time. Nodes communicate with each other through unreliable channels, meaning that messages can be lost, altered, duplicated or reordered. We assume the existence of a finite but unknown upper-bound on message propagation time, which fits the the partial synchrony model [START_REF] Dwork | Consensus in the Presence of Partial Synchrony[END_REF].

We suppose that a bounded proportion µ, with µ ≤ 1/3 of the nodes in Π are Byzantine (i.e., behave arbitrarily, either in collusion or on their own to maximize some utility function of their choice). All the other nodes are said correct or honest. We assume that nodes have access to basic cryptographic functions, including a cryptographic hash function h -modeled as a random oracle -and an asymmetric signature scheme -that allows nodes to generate public and secret key pairs (p r , s r ), to compute signatures σ r,h(d) on messages d, and to verify the authenticity of a signature. These primitives are assumed to be safe -i.e., forging signatures, and finding hash collisions, pre-image or second pre-image is impossible. By these properties, each object o of the system -i.e., UTXO (for unspent transaction output), transaction and block -is assumed to be uniquely identified.

We assume that correct nodes use their cryptographic keys in a safe way, i.e. they do not disclose, share or drop their secret keys. As a consequence, their identity can not be spoofed and their received coins cannot be stolen. We do not suppose the existence of any trusted public key infrastructure (PKI) to establish nodes identities. Finally, we assume that each object o is well-formed. For example, a transaction can be rejected (by a correct node) only if that transaction tries to double-spend inputs and not e.g. because a script is not correctly written.

B. Transactions and blocks

Prior to describing our solution, let us first recall some background on transactions and blocks manipulated in most of the cryptosystems that derive from Bitcoin. A transaction is made of two sets, the input set denoted by I and the output one denoted by O. Set I contains the set of outputs, credited by previous transactions, that the creator of the transaction wishes to spend, together with the proof that she is allowed to redeem each of those outputs. The output set O contains transferred coins, together with the challenges that will allow their owners to redeem those coins.

Transactions outputs are locked with a challenge and redeemed in subsequent transactions by providing the appropriate response. Different types of scripts exist in Bitcoin, but the most common one is the PAY-TO-PUBKEY-HASH script. 1In that script, the challenge embeds the hash value h = h(p r ) of a public key p r and the response of the challenge contains the public key p r together with the signature σ r signed with the secret key associated to p r . Thus the only user able to provide the appropriate values of σ r and p r is the effective owner of the transaction output, that is the owner of the UTXO. As a consequence, double spending attacks can only be launched by (malicious) users that create distinct transactions redeeming exactly one of their transaction outputs.

Once created, a transaction is submitted to the peer-to-peer network. Each node of the network should check the validity of the transaction prior to propagating it to its neighborhood. Informally, a transaction T = (I, O) is locally valid at node p if p has received all the transactions that have credited all the inputs in I and for all i ∈ I, i is not in a double-spending situation.

Input i ∈ I is in a double-spending situation if p is aware of transaction T = (I , O ) such that i ∈ I ∩ I = ∅.
Transaction T = (I, O) is conflict-free if none of the inputs of T is involved in a double-spending situation and all of the transactions that credited T 's inputs are conflict-free. By construction, the induction is finite at least in Bitcoin, because money is created only through coinbase transactions, which are by definition conflict-free [START_REF] Anceaume | Safety Analysis of Bitcoin Improvement Proposals[END_REF].

Blocks are created by successful miners, a subset of the nodes involved in the proof-of-work competition. The incentive to participate to such a competition is provided by a reward given to each successful miner. This reward is made of a fixed amount of coins (in Bitcoin, the reward is currently equal to 12.5 bitcoins) and a fee associated to each transaction contained in the newly created block. This reward is inserted in the output of a particular transaction, called the coinbase transaction. Note that coinbase transactions do not have inputs.

A block is made of two parts: the header and the payload. The payload contains a unique coinbase transaction and a list of valid transactions. The header of the block contains several fields among which the reference to its parent block (hence the blockchain), a proof-of-work, that is a nonce such that the hash of the block matches a given target (in Bitcoin, this target is calibrated so that the mean generation time of a block is equal to 10 minutes), and the fingerprint of the payload. In the following, we refer by b = (h(b ), c(b)), a block with a parent block reference h(b) and a payload c(b).

When a transaction T is included in a block b, it is said confirmed by all the peers that accept that block in their local copy of the blockchain. The level of confirmation of transaction T is the number of blocks included in the blockchain starting from b; by extension, a 0 confirmation level means that the transaction has not yet been included in the blockchain. To limit double-spending attacks, Bitcoin recommends that sellers do not provide their goods in exchange of a transaction before it becomes deeply-confirmed. Actually, Nakamoto [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] as well as subsequent studies [START_REF] Garay | The Bitcoin Backbone Protocol: Analysis and Applications[END_REF], [START_REF] Karame | Misbehavior in Bitcoin: A Study of Double-Spending and Accountability[END_REF], [START_REF] Miller | Anonymous byzantine consensus from moderately-hard puzzles: A model for bitcoin[END_REF] have shown that if the computational power of malicious miners is equal to 10% of the whole computational power, then with probability less than 0.1%, a transaction can be rejected if its level of confirmation in a local copy of the blockchain is less than 5.

In the following, we say that a transaction is deeply confirmed once it reaches such a confirmation level.

Most of the permissionless blockchain-based cryptosystems guarantee the following two properties:

• Safety If a transaction T is deeply confirmed by some correct node, then no transaction conflicting with T will ever be deeply confirmed by any correct node. • Liveness A conflict-free transaction will eventually be deeply confirmed in the blockchain of all correct nodes at the same height in the blockchain. I case of a blockchain fork, some blocks can be invalidated and the level of confirmation of their transactions can decrease, especially if the conflicting branch contains a conflicting transaction. This deters the use of Bitcoin for fast payment, as the expected time for a deep confirmation is approximately one hour. Fast payment are used in most everyday life situations, where the time between buying and consuming the goods is in the order of minutes. This impracticality motivates this work.

In the present paper, by preventing double-spending attacks and blockchain forks we aim at strengthening the safety property as follows:

• Strong Safety If a transaction T is confirmed by some correct node, then no transaction conflicting with T will ever be confirmed by any correct node. The strong safety property ensures that whenever a transaction T has been included in a block, no other block will ever contain a transaction conflicting with T . An immediate and important consequence of this property is the capability blockchain-based cryptosystems to safely handle fast payments. The remaining of the paper is devoted to the implementation of this property.

III. RELATED WORK

Bitcoin [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] is seen as the pioneer of cryptocurrencies. Since its inception, several altcoins [START_REF] Ahamad | A Survey on Crypto Currencies[END_REF] have emerged. The GHOST protocol [START_REF] Sompolinsky | Accelerating Bitcoin's Transaction Processing[END_REF] proposes a different rule to solve blockchain forks, based on the number of blocks contained in each blockchain subtree (in case of consecutive forks). Recent works have focused on Bitcoin modeling and evaluation. Authors of [START_REF] Miller | Anonymous byzantine consensus from moderately-hard puzzles: A model for bitcoin[END_REF] prove that the Bitcoin protocol achieves consensus with high probability, while [START_REF] Garay | The Bitcoin Backbone Protocol: Analysis and Applications[END_REF] show that peers participating in the Bitcoin network agree on a common prefix for the transaction history, both in failure-free environments. In contrast, authors of [START_REF] Karame | Double-spending Fast Payments in Bitcoin[END_REF], [START_REF] Karame | Misbehavior in Bitcoin: A Study of Double-Spending and Accountability[END_REF] focused on adversarial environments. These works study the feasibility of double spending attacks and their detection. Several studies have shown that Bitcoin behaves quite well in failure-free environments [START_REF] Miller | Anonymous byzantine consensus from moderately-hard puzzles: A model for bitcoin[END_REF] but is vulnerable to some attacks such as the double-spending one [START_REF] Karame | Misbehavior in Bitcoin: A Study of Double-Spending and Accountability[END_REF]. Several attempts to fix it have been published, using a leader [START_REF] Decker | Bitcoin Meets Strong Consistency[END_REF], [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF], [START_REF] Kogias | Enhancing bitcoin security and performance with strong consistency via collective signing[END_REF], or forming local committees to run consensus algorithms at the local level [START_REF] Luu | SCP: a computationally-scalable Byzantine consensus protocol for blockchains[END_REF] but these proposals encounter various scalability or security issues which make them unusable. Specifically, Bitcoin-NG [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF], PeerCensus [START_REF] Decker | Bitcoin Meets Strong Consistency[END_REF], and BizCoin [START_REF] Kogias | Enhancing bitcoin security and performance with strong consistency via collective signing[END_REF], have proposed to rely exclusively on miners to take in charge the full process of validation and confirmation to guarantee that all the operations triggered on the transactions are atomically consistent. Atomic consistency guarantees that all the updates on shared objects are perceived in the same order by all entities of the system. In all these protocols, time is divided into epochs. An epoch ends when a miner successfully generates a new block. This miner becomes the leader of the subsequent epoch. Each of these solutions rely on a dedicated set E , with ∈ {1, w, ∞}. This set is built along consecutive epochs as follows. At epoch k, if |E | < , the new leader is added to E . Otherwise, the leader at epoch k + 1is removed from E and the new leader is added. Once set E reaches size , it remains at constant size . Strong consistency is implemented in these protocols by different means. In Bitcoin-NG, it is achieved by delegating the validation process to E 1 , i.e. the leader of the current epoch. In PeerCensus it is implemented by relying on Byzantine Fault Tolerant consensus protocols (e.g. [START_REF] Castro | Practical Byzantine Fault Tolerance[END_REF], [START_REF] Guerraoui | The Next 700 BFT Protocols[END_REF], [START_REF] Kotla | Zyzzyva: Speculative Byzantine Fault Tolerance[END_REF]) run by E ∞ (recall that it contains all the miners that successfully generated a block). Finally, BizCoin leverages both ideas using the leader and a consensus run by E w . In all these protocols, members of E , with ∈ {1, w, ∞}, are entitled to validate and confirm issued transactions and blocks and to disseminate them so that each peer integrates them in its local blockchain. It has been shown in a previous paper [START_REF] Anceaume | Safety Analysis of Bitcoin Improvement Proposals[END_REF] that none of the studied solutions enhances Bitcoin's behavior. Beyond the complexity introduced by the consensus executions, the main issue comes from the fact that all important decisions of Bitcoin are solely under the responsibility of (a quorum of) miners, and the membership of the quorum is decided by the quorum members. This magnifies the power of malicious miners.

Very recently, an elegant pessimistic-based approach to mitigate the presence of blockchain forks has appeared with Algorand [START_REF] Gilad | Algorand: Scaling byzantine agreements for cryptocurrencies[END_REF]. In Algorand, members of the Byzantinetolerant algorithm (BA*) are selected no more proportionally to their computational power, but proportionally to their stake. Among them, a leader is elected, the one with the largest stake, and handles all the currently submitted transactions. Algorand guarantees that in periods of strong synchrony, the blockchain correctly grows (absence of forks and double-spending), while in presence of variable communication delays, growth is not guaranteed.

The current paper improves upon a previous work in which the idea of validating transactions and blocks as early as possible was introduced [START_REF] Lajoie-Mazenc | Handling bitcoin conflicts through a glimpse of structure[END_REF]. To cope with the risk of Sybil attacks, participants to BA committees in [START_REF] Lajoie-Mazenc | Handling bitcoin conflicts through a glimpse of structure[END_REF] have to solve a computational puzzle to create their current identities [START_REF] Luu | SCP: a computationally-scalable Byzantine consensus protocol for blockchains[END_REF], which in expectation makes the number of identities per node proportional to its computational power. In the present solution, we rely on UTXOs owners to participate to BA committees for the following reasons. First by relying on the public key as identity principle, anyone can easily verify BA committees membership, and second by relying on the fact that UTXOs are one shot objects (i.e., once debited an UTXO does not exist anymore), an induced churn is generated allowing honest participants to escape poisoning attacks by moving to a new region of the system, and preventing malicious nodes from staying indefinitely long in the same region of the system, healing the system from eclipse attacks.

IV. A SET OF INGREDIENTS

The main objectives of our solution are twofold: (i) the guarantee that only non conflictual objects -blocks and transactions -are validated and propagated in the system in order to prevent arbitration rules from being applied a posteriori and, (ii) the execution of the block and transaction validation process over distinct committees to mitigate adversarial behaviors (collusion and eclipse attacks) and to improve the system scalability. Our solution relies on the orchestration of the following ingredients.

Byzantine agreement (BA).

The first ingredient we use to implement the validation process is Byzantine agreement. Informally, Byzantine agreement (BA) is a communication protocol enabling a set of committee members, each of which holds a possibly different initial value, to agree on a single value v. Such an agreement is reached by all honest members, that is, by those who scrupulously follow the protocol despite the fact that a minority of the members are malicious and can deviate from the protocol in an arbitrary and coordinated manner.

Distributed Hash Table (DHT).

The second ingredient of our solution is a distributed hash table. Recall that DHTs build their topology according to structured graphs, and for most of them, the following principles hold: the identifier space, e.g., the set of 256-bit strings, is partitioned among all the nodes of the system, and nodes self-organize within the graph according to a distance function D based on node identifiers (e.g. two nodes are neighbors if their identifiers share some common prefix), plus possibly other criteria such as geographical distance. Example of DHTs are [START_REF] Ratnasamy | A Scalable Content-addressable Network[END_REF], [START_REF] Stoica | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications[END_REF], [START_REF] Maymounkov | Kademlia: A peer-to-peer information system based on the xor metric[END_REF], [START_REF] Rowstron | Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems[END_REF]. For resiliency reasons, each vertex of the graph can be a set or a cluster of nodes. Basically, nodes sharing a common prefix gather together into clusters, and clusters selforganize into a graph topology, for instance an hypercube. By running distributed algorithms inside each cluster, clusterbased DHTs can be made robust to high churn [START_REF] Heilman | Eclipse Attacks on Bitcoin's Peer-to-Peer Network[END_REF] and adversarial attacks [START_REF] Anceaume | PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn[END_REF].

Cluster-based DHT. In the following we use PeerCube, a cluster-based DHT to implement the validation protocols [START_REF] Anceaume | PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn[END_REF]. Briefly, PeerCube is a DHT that conforms to an hypercube. Vertices of the hypercube are clusters of nodes. Each cluster is dynamically formed by gathering nodes that are close to each other according to a distance function D applied on the bit string identifier space. Distance D consists in computing the numerical value of the "exclusive or" (XOR) of bit strings.

Thus identifiers that have longer prefix in common are closer to each other, and for any point p and distance ∆ there is exactly one point q such that D(p, q) = ∆ (which does not hold for the Hamming distance). Nodes whose identities share a common prefix gather together within the same cluster. Each cluster is uniquely identified with a label that characterizes the position of the cluster in the overall hypercubic topology. The label of a cluster is defined as the shortest common prefix shared by all the users of that cluster such that the non-inclusion property is satisfied. The non-inclusion property guarantees that a cluster label never matches the prefix of another cluster label, and thus ensures that each identifier belongs to at most one cluster. The length a cluster label, i.e. the number of bits of that label, is called the dimension of the cluster. In the following, notation d-cluster denotes a cluster of dimension d. Dimension determines an upper bound on the number of links a cluster has with other cluster of the DHT, i.e. the number of its neighbors. Clusters self-organize into a hypercubic topology, such that the position of a cluster into the hypercube is determined by its label. Ideally the dimension of each cluster C should be equal to some value d to conform to a perfect d-hypercube. However, due to the fact that nodes join and leave the system at anytime, and their identifiers are random bit strings, then cluster membership evolve, and thus clusters may grow or shrink more rapidly than others. In the meantime, cluster size are bounded. Whenever the size of C exceeds a given value S max , C splits into clusters of higher dimensions, and whenever the size of C falls under a given size of S min nodes, C merges with other clusters into a single new cluster of lower dimension. Members of each cluster run Byzantine agreement protocols to guarantee that the functioning of the DHT is correct despite targeted attacks [START_REF] Anceaume | Performance evaluation of large-scale dynamic systems[END_REF]. This is achieved by partitioning each cluster into two sets, core members and spare members. The number of core members is at any time kept constant to handle a proportion µ of malicious nodes, while the spare set gathers all the other node of the cluster, and by doing so handle the churn without impacting the topology of the hypercube [START_REF] Anceaume | PeerCube: A Hypercube-Based P2P Overlay Robust against Collusion and Churn[END_REF].

"Public keys as identities" principle. The third ingredient of our solution is to use (verification) public keys as user identities. This means that users can use their public keys as a reference to them. Digital signatures enables this because one has the ability to verify the validity of an information based on the public key, information, and signature. This principle is at the core of challenges present in transactions to redeem coins of UTXOs, and as detailed below we deeply use the unique association UTXO/identity as a proof of membership for BA.

V. DISTRIBUTED HASH TABLE HAS A SUPPORT FOR RUNNING DISTINCT INSTANCES OF BYZANTINE

AGREEMENTS

We now describe how the above ingredients are orchestrated to validate transactions and blocks.

BA committee members are the owners of UTXOs. BA committee members are the owner of UTXOs, that is the users of the cryptocurrency system -this clearly differs from most of the BA-based blockchains in which BA protocols are executed by the successful miners. Note that as each user may own a multitude of UTXOs (i.e. may have a multitude of identities), a user may belong to several distinct BA committees. As will de described in the following, any committee member may prove its right to belong to a given committee by exhibiting a digital signature that verifies an UTXO that has never been redeemed so far.

BA committees as vertices of the DHT. To cope with the thousands of transactions to be validated per day, a multitude of BA protocols are run in parallel, each one sitting at the vertices of PeerCube. Thus a BA committee is identified by a unique label, which is the shortest common prefix shared by all the users (i.e. UTXOs owners) of that BA committee. Validation of each transaction T is handled by a specific BA committee, the one whose label is a prefix of T identifier -the identifier of a transaction is equal to its hash. Recall that by construction, PeerCube guarantees that any identifier belongs to a single cluster. In the following the BA committee to which T is affected is called T referee. Similarly, validation of a block is handled by a unique BA committee. However, in contrast to transactions, the referee of a block B is the BA committee whose label is a prefix of B predecessor (Recall that blocks form a chain by pointing to a predecessor).

UTXOs to prevent targeted attacks. It is very important to understand that, since UTXOs are one shot objects -that is UTXOs are debited once and then disappear -the presence of users in committees is verifiable. Anyone in the system can check that some user is allowed to participate to the execution of BA in a given cluster by just checking in her blockchain that the identity of that user, that is its public key, and thus its UTXO has never been redeemed so far. This feature is important as it is a very efficient way to prevent targeted attacks, attacks in which collusion of malicious nodes devise strategies to progressively take the leadership of a targeted region by staying longer than honest nodes [START_REF] Awerbuch | Group spreading: A protocol for provably secure distributed name service[END_REF], [START_REF] Anceaume | Performance evaluation of large-scale dynamic systems[END_REF]. By the second pre-image property of public keys, it is also very difficult for malicious nodes to generate identities that allow them to choose their positions so as to form collusions inside committees.

VI. TRANSACTION VALIDATION PROTOCOL

The purpose of the transaction validation protocol is to prevent double spending attacks by ensuring that concurrent transactions do not try to use common inputs. Say differently, its objective is to guarantee that at any time at most one transaction can redeem all the UTXOs referenced in its input set.

If we make an analogy between transaction inputs and objects, and an analogy between using an input and writing an object, then we can refer to database systems, in which exclusive access to objects is obtained by asking each transaction to explicitly lock objects it accesses using some single object locking mechanism. Yet, unless care is taken, locking objects one by one may cause deadlocks. As the application we consider involves different nodes spread over a large area, it is not advisable to rely on having all of them conform to the same locking strategies. Moreover, from a performance viewpoint, it may be impossible to run deadlock detection and prevention protocols assuming independent object locking. In the following we propose a transaction validation protocol that provides the equivalent of an atomic locking mechanism for all of the inputs of each issued transaction.

Formally, our transaction validation protocol implements two methods, grantInputs and release, that both accept a transaction T = (I, O) as parameter. The grantInputs method returns with GRANTED or DENIED. When an invocation returns with GRANTED, we say that the method exclusively grants the inputs in I to T or, in short, that T has been GRANTED. Once T has been GRANTED, for any subsequent transaction T conflicting with T , the service returns DENIED. T can invoke the release method only if T has not been granted. Otherwise it has no effect.

The transaction validation protocol prevents double spending attacks if the following three properties are met: As evoked above, the referee of each transaction T = (I, O) is the BA committee whose label share a common prefix with T . Let us call it pi T . pi T is in charge of invoking the grantInputs method for T and possibly the release method if T has not been granted. Granting a transaction means granting all the inputs of the transactions. Thus similarly to the referee of a transaction T = (I, O), each input i ∈ I of T has a referee. we call it UTXO referee, which is the BA committee whose label is a prefix of i ∈ I. Let us call it pi i .

Therefore, when a user creates a transaction T = (I, O), it submits T to PeerCube that routes T to its referee pi T . For each input i ∈ I of T , pi T asks an exclusive lock at the referee pi i of each input i ∈ I, in an order that corresponds to the lexicographical order of the input IDs. If the lock is DENIED for at least one of these inputs, pi T releases all previously obtained locks (by proving to each of these referees that a conflicting transaction T has already been GRANTED). Otherwise, after obtaining all locks, a GRANTED status is returned to pi T . Thus, similarly to transaction referees, UTXO referees are characterized by the following properties: The correctness and, in particular, the lack of deadlocks, result from the fact that objects are always obtained in lexicographical order. A lock can be implemented using a combination of Test-and-Set and Reset primitives. The referee pi i that wishes to lock input i ∈ I, first checks the value of a binary register. When this value is 0, it modifies the register to 1 and uses the lock. Releasing a lock is done by resetting to 0 the register value. The fact that T has been granted the lock on each input i ∈ I is proven by pi i 's signature. Each signature is bundled with the identity of the signer. Note that Bitcoin transactions can easily be extended to accommodate this process: the referee pi T of transaction T = (I, O) computes a group signature S (e.g. [START_REF] Boldyreva | Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme[END_REF]) using the signatures of each input referee pi i i∈I and its own signature and appends it, along with everything needed to verify this group signature, to a specific validation output o added to the set of outputs O of transaction T = (I, O). Any node can easily verify that transaction T = (I, O) has been GRANTED by checking the signatures S added by referee pi T .

Referees are incentivized by introducing a validation fee. A fair and easy way to share the validation output is to randomly pick one of the referees and give it the entire reward. This requires seeding a random number generator in a publicly verifiable way, and for example with an information that can only be published after the transaction validation protocol has returned, like the hash of the block in which the transaction is included.

VII. BLOCK VALIDATION PROTOCOL

By following exactly the same validation transaction principle, BA committees are exploited to prevent blockchain forks, that is ensure that any validated block has at most one valid block as immediate successor. It is achieved by providing a method grantBlock that accepts a block b = (h(b), c(b )) as parameter. This method returns with GRANTED or DENIED. When an invocation returns with GRANTED, we say that the method validates block b as the unique successor of block b, i.e. block b is granted for h(b). This method has to satisfy the three following properties:

•

  Safety: If a transaction T = (I, O) is exclusively granted the inputs in I, then no other transaction T = (I , O ) is exclusively granted the inputs in I with I ∩ I = ∅. • Liveness: Each invocation of the grantInputs method eventually returns. • Non triviality: If there exists an invocation of the grantInputs method with T = (I, O), and no other transaction T = (I , O ) with I ∩ I = ∅ is exclusively granted the inputs in I then T is granted exclusively all the inputs in I.

•

  Safety: if an UTXO u is spent by a transaction T = (I, O), u ∈ I, then no other transaction T = (I , O ), u ∈ I can spend u, i.e. T is considered as invalid.• Liveness: Each invocation of the grantUTXO method eventually returns. • Non triviality: If there exists an invocation of the grantUTXO method for an UTXO u ∈ I with T = (I, O), and no other transaction T = (I , O ) with u ∈ I ∩ I is exclusively granted the inputs in I then u is granted exclusively for T . Protocol 1 is the pseudo-code run by the referee of a transaction to orchestrate the grant requests on the involved UTXOs referees as described in the pseudo-code of Protocol 2.

•

  Safety: If a block b = (h(b), c(b )) is granted for h(b), then no other block b = (h(b), c(b )) is granted for h(b). • Liveness: Each invocation of the grantBlock method eventually returns. • Non triviality: If there exists an invocation of the grantBlock method with b = (h(b), c(b )), and no

Note that different Bitcoin verification scripts exist and some of them do not rely on cryptography (ANYONE-CAN-SPEND) or do not ensure a unique recipient (ANYONE-CAN-SPEND, TRANSACTION PUZZLE). In the following, we will consider only PAY-TO-PUBKEY-HASH scripts.

Therefore, when a miner creates a block B it submits a grantBlock request for B to PeerCube that routes it to its referee pi B . The request is granted if pi B has never granted such a request before. Protocol 3 is the pseudo-code of the block validation protocol.

To summarize, the validation protocols guarantee via BA committees tessellated at the vertices of a DHT that that a transaction is validated only if it is the only one to redeem each of its inputs, and a block is validated if it is the unique successor of its predecessor. This is achieved by relying on the ephemeral participation of UTXOs owners as BA committees members. Indeed once an UTXO has been granted by a committee, that UTXO does not exist anymore, and thus its owner leaves the BA committee, and joins the BA committees Protocol 2: UTXO conflict handling protocol whose labels prefix the newly created UTXOs. This is very important to prevent eclipse attacks, that is strategies which allows the adversary to stay forever at the same position in order to progressively eclipse honest nodes around it.

VIII. CONCLUSION

In this paper we have presented a new idea to prevent both blockchain forks and double spending attacks, without relying on successful miners to impose a total ordering on the blocks they have mined. Our design relies on the ephemeral participation of UTXO owners, and exploits both the scalability and robustness properties of cluster-based DHTs and the "public key as identity" principle. Those ingredients allow us to introduce a small amount of synchronization, soon enough in the validation process, to guarantee that sellers can to deliver their good as soon as the transaction has been validated by the system. Fast payments transactions are thus no more an issue. The same level of local synchronization heals the Bitcoin system from blockchain forks, and selfish mining. We are currently evaluating the performance of our design through an implementation that we have deployed over several hundred nodes. Preliminary results are very promising.


Sarah Hank
email: hank.sarah@gmail.com

S L Gavrilyuk
email: sergey.gavrilyuk@univ-amu.fr

Nicolas Favrie
email: nicolas.favrie@univ-amu.fr

Jacques Massoni
email: jacques.massoni@univ-amu.fr

Impact simulation by an Eulerian model for interaction of multiple elastic-plastic solids and fluids

Impact simulation by an Eulerian model for interaction of multiple elastic-plastic solids and fluids

Sarah Hank, Sergey Gavrilyuk, Nicolas Favrie, Jacques Massoni

Introduction

Solid-fluid interactions in the case of extreme deformations appear in many industrial applications (blast effects on structures, hypervelocity impacts,...). This kind of problems may involve high pressures and strain rates as well as a high density ratio. The hyperelastic models [START_REF] Godunov | Elements of continuum mechanics[END_REF][START_REF] Kluth | Perfect plasticity and hyperelastic models for isotropic materials[END_REF][START_REF] Godunov | Elements of continuum mechanics and conservation laws[END_REF][START_REF] Miller | A high-order Eulerian Godunov method for elastic-plastic flow in solids[END_REF][START_REF] Plohr | A conservative formulation for plasticity[END_REF][START_REF] Merzhievsky | The role of numerical simulation in the study of highvelocity impact[END_REF][START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF] for which the stress tensor is defined in terms of a stored energy function are well adapted to treat accurately such problems. The hyperelastic models are conservative by construction. They are also objective and thermodynamically consistent. In this paper, a multi-component hyperelastic Eulerian formulation is used to compute several impact test cases [START_REF] Hank | Modeling hyperelasticity in non equilibrium multiphase flows[END_REF]. The modelling is based on a 'diffuse interfaces method' which was developed for multi-component fluids [START_REF] Abgrall | Discrete equations for physical and numerical compressible multiphase mixtures[END_REF][START_REF] Saurel | A multiphase model for compressible flows with interfaces, shocks, detonation waves and cavitation[END_REF][START_REF] Saurel | A multiphase model for compressible flows with interfaces, shocks, detonation waves and cavitation[END_REF] and generalized to the case of interaction of multiple solids and fluids [START_REF] Favrie | Diffuse interface model for compressible fluid-compressible elasticplastic solid interaction[END_REF][START_REF] Ndanou | Multi-solid and multi-fluid diffuse interface model: Applications to dynamic fracture and fragmentation[END_REF]. Relaxation terms for an accurate description of plastic transformations proposed in solids in [START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF] have been added. No hardening parameter is used to deal with the evolution of the yield strength.

The paper is organized as follows. In Section 2, the mathematical model is presented. In Section 3, the numerical method is briefly described. Two test cases are studied in Section 4. In particular, a symmetric copper rod impact is computed and compared to the experimental data provided in [START_REF] Forde | Symmetrical Taylor impact studies of copper[END_REF]. Then, a low velocity clay suspension impact is studied and compared to the experimental results obtained in [START_REF] Luu | Drop impact of yield-stress fluids[END_REF].

Viscoplastic model 2.1 Eulerian multi-component formulation of hyperelasticity

Hyperelasticity models have been intensively studied in the past few years [START_REF] Godunov | Elements of continuum mechanics[END_REF][START_REF] Godunov | Elements of continuum mechanics and conservation laws[END_REF][START_REF] Godunov | Thermodynamically consistent nonlinear model of elastoplastic Maxwell medium[END_REF][START_REF] Barton | An Eulerian finite-volume scheme for large elastoplastic deformations in solids[END_REF][START_REF] Miller | A high-order Eulerian Godunov method for elastic-plastic flow in solids[END_REF][START_REF] Kluth | Perfect plasticity and hyperelastic models for isotropic materials[END_REF][START_REF] Merzhievsky | The role of numerical simulation in the study of highvelocity impact[END_REF][START_REF] Plohr | A conservative formulation for plasticity[END_REF][START_REF] Ghaisas | High-order Eulerian methods for elastic-plastic flow in solids and coupling with fluid flows[END_REF][START_REF] Ortega | Numerical simulation of elasticplastic solid mechanics using an Eulerian stretch tensor approach and HLLD Riemann solver[END_REF][START_REF] Brauer | A Cartesian scheme for compressible multimaterial models in 3D[END_REF]. In this paper, we consider a modified conservative formulation adapted to the case of isotropic solids. The Eulerian formulation of the multi-component hyperelasticity proposed in [START_REF] Favrie | Solid-fluid diffuse interface model in cases of extreme deformations[END_REF][START_REF] Favrie | Diffuse interface model for compressible fluid-compressible elasticplastic solid interaction[END_REF][START_REF] Ndanou | Multi-solid and multi-fluid diffuse interface model: Applications to dynamic fracture and fragmentation[END_REF]] is considered. The numerical algorithm for solving this model is based on the generalization of the discrete equations method developed earlier for multi-component fluids in [START_REF] Abgrall | Discrete equations for physical and numerical compressible multiphase mixtures[END_REF][START_REF] Saurel | A multiphase Godunov method for compressible multifluid and multiphase flows[END_REF][START_REF] Saurel | A multiphase model for compressible flows with interfaces, shocks, detonation waves and cavitation[END_REF] and multi-component solids [START_REF] Hank | Modeling hyperelasticity in non equilibrium multiphase flows[END_REF].

As we deal with non-equilibrium flows, each component admits its own equation of state with its own stress tensor. This approach allows us to treat configurations involving several solids and fluids. The discrete equations are obtained by integrating the conservation laws over a multiphase control volume. The general model is written hereafter for the phase k (in 1D case for the sake of simplicity).

                                                       ∂α k ∂t + u I ∂α k ∂x = 0, ∂(αρ) k ∂t + ∂(αρu) k ∂x = 0, ∂(αρu) k ∂t + ∂(αρu 2 -ασ 11 ) k ∂x = -σ 11,I ∂α k ∂x , ∂(αρv) k ∂t + ∂(αρuv) k ∂x + ∂(-ασ 12 ) k ∂x = -σ 12,I ∂α k ∂x , ∂(αρw) k ∂t + ∂(αρuw) k ∂x + ∂(-ασ 13 ) k ∂x = -σ 13,I ∂α k ∂x , ∂(αρE) k ∂t + ∂(αρEu -ασ 11 u -ασ 12 v -ασ 13 w) k ∂x = -(σ 11,I u I + σ 12,I v I + σ 13,I w I ) ∂α k ∂x , ∂(αa β ) k ∂t + ∂(αa β u) k ∂x + (αb β ) k ∂v k ∂x + (αc β ) k ∂w k ∂x = 0, β = 1, 2, 3 ∂b β k ∂t + u k ∂b β k ∂x = 0, β = 1, 2, 3 ∂c β k ∂t + u k ∂c β k ∂x = 0, β = 1, 2, 3. (1)
Here, for k th phase: α k is the volume fraction, ρ k is the phase density,

u k = (u k , v k , w k ) T is the velocity field, σ k is the stress tensor: σ k = S k -p k I, (2)
where S k is the deviatoric part of the stress tensor and p k is the thermodynamical pressure. As the model belongs to the class of hyperelastic models, the stress tensor can be expressed as the variation of the internal energy (their exact expressions are given in the following subsection). The evolution equations of hyperelasticity are written for deformation measures (in particular, for the Finger tensor defined below). E k is the total energy associated to the phase k and is given by the following expression:

E k = ∥u k ∥ 2 2 + e k (η k , G k ), (3)
where η k is the entropy of the phase k and G k is the Finger tensor. The exact expressions of e k (η k , G k ) in (3) will be given in the next subsection.

The variables with subscripts 'I' are the 'interface' variables. They are obtained directly when solving the Riemann problem. The model is thermodynamically consistent and satisfies the second principle of thermodynamics. The proof is not straightforward. Nevertheless, the thermodynamic consistency has been verified on numerical test cases (for example, a shock wave propagation in a media in presence of material interfaces). In the right hand side of the system (1), non conservative terms are present: these terms exist if the volume fraction gradient is non zero.

The geometric variables a β k , b β k , c β k related to the deformation gradient will now be defined. To simplify the presentation, we will not further use in this section the subscript k for unknowns. Let us define the Finger tensor G as the inverse of the left Cauchy-Green tensor B: G=B -1 . The Finger tensor can also be expressed in the form:

G = 3 ∑ β=1 e β ⊗ e β , e β = (a β , b β , c β ) T , e β = ∇X β , β = 1, 2, 3, F -T = (e 1 , e 2 , e 3 ).

2

Here X β are the Lagrangian coordinates, the gradient is taken with respect to the Eulerian coordinates, F is the deformation gradient. In the next subsection the equation of state is presented, allowing the system closure. Different relaxation phenomena can easily be added into the model (pressure and velocity relaxation, phase transitions...).

System closure

The closure of the system is performed by using an equation of state presented in a separable form [START_REF] Gavrilyuk | Modelling wave dynamics of compressible elastic materials[END_REF]:

e(η, G) = e h (ρ, η) + e e (g), g = G |G| 1/3 , ( 4
)
where |G| denotes the determinant of the tensor G. This formulation has been used in particular in [START_REF] Favrie | Solid-fluid diffuse interface model in cases of extreme deformations[END_REF][START_REF] Favrie | Diffuse interface model for compressible fluid-compressible elasticplastic solid interaction[END_REF][START_REF] Favrie | A thermodynamically compatible splitting procedure in hyperelasticity[END_REF][START_REF] Ndanou | The piston problem in hyperelasticity with the stored energy in separable form[END_REF]. With such a formulation, the pressure is determined only by the hydrodynamic part of internal specific energy e h (ρ, η). The deviatoric part of the stress tensor can be expressed using the shear part of the specific internal energy e e (g). The hydrodynamic part of the energy satisfies the Gibbs identity:

θdη = de h + pdτ,
where τ is the specific volume (τ = 1/ρ) and θ is the temperature. The expression of the deviatoric part of the stress tensor S is:

S = -2ρ ∂e e ∂G G.
The hydrodynamic part of the internal specific energy is taken as the stiffened gas equation of state:

e h (ρ, p) = p + γp ∞ ρ(γ -1) . (5)
In [START_REF] Gavrilyuk | An example of a one-parameter family of rank-one convex stored energies for isotropic compressible solids[END_REF], a family of rank-one convex stored energies for isotropic compressible solids with a single parameter (denoted by ã) is proposed:

e e (G) = µ 4ρ 0 ( 1 -2ã 3 j 2 1 + ãj 2 + 3(ã -1) ) , j m = tr(g m ), m = 1, 2, 3. (6)
Here, µ is the shear modulus of the considered material and ρ 0 is the reference density. Using the criterion proposed in [START_REF] Ndanou | Criterion of hyperbolicity in hyperelasticity in the case of the stored energy in separable form[END_REF][START_REF] Gavrilyuk | An example of a one-parameter family of rank-one convex stored energies for isotropic compressible solids[END_REF], it has been proven that with the equations of state ( 5) and ( 6), the equations are hyperbolic for any ã such that -1 ≤ ã ≤ 0.5. The relation [START_REF] Favrie | Dynamics of shock waves in elastic-plastic solids[END_REF] involves the following expression for the deviatoric part:

S = -µ ρ ρ 0 ( 1 -2ã 3 j 1 { g - j 1 3 I } + ã { g 2 - j 2 3 I }) . ( 7
)
One can notice that for the value ã = -1, the equation of state describes neo-Hookean solids. Its expression is the following:

e e (G) = µ 4ρ 0 ( j 2 1 -j 2 -6 ) . ( 8
)
The energy ( 8) is, in particular, suitable for the description of jelly-type materials. In the case of metals, the value ã = 0.5 can be chosen, where the equation of state becomes:

e e (G) = µ 8ρ 0 (j 2 -3) . ( 9
)

Viscoplasticity modelling

An important class of hyperbolic models describing the plastic behavior of materials under large stresses has been proposed, for example in [START_REF] Godunov | Elements of continuum mechanics[END_REF][START_REF] Godunov | Elements of continuum mechanics and conservation laws[END_REF][START_REF] Godunov | Thermodynamically consistent nonlinear model of elastoplastic Maxwell medium[END_REF][START_REF] Barton | An Eulerian finite-volume scheme for large elastoplastic deformations in solids[END_REF]. An extension of this approach has been proposed in [START_REF] Favrie | Solid-fluid diffuse interface model in cases of extreme deformations[END_REF][START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF][START_REF] Favrie | Dynamics of shock waves in elastic-plastic solids[END_REF][START_REF] Ndanou | Multi-solid and multi-fluid diffuse interface model: Applications to dynamic fracture and fragmentation[END_REF] to include material yield criteria (Von Mises). The relaxation terms are constructed in such a way that they are compatible with the mass conservation law and consistent with the second law of thermodynamics. The Von Mises yield limit is reached at the end of the relaxation step. The built model belongs to Maxwell type model, where the intensity of the shear stress decreases during the relaxation.

We use the formulation proposed in [START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF]. The governing equations for e β are now written as follows:

De β Dt + ( ∂u ∂x
) T e β = - 1 τ rel Re β , ( 10
)
where τ rel corresponds to a relaxation time and R is a symmetric tensor (R = R T ). As the Finger tensor G is linked to the local cobasis e β , it is possible to write the governing equation for G by using [START_REF] Gavrilyuk | An example of a one-parameter family of rank-one convex stored energies for isotropic compressible solids[END_REF].

DG Dt + ( ∂u ∂x ) T G + G ( ∂u ∂x ) = - 1 τ rel (GR + RG) . ( 11
)
In [START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF], an expression has been proposed for the tensor R. This expression ensures the thermodynamic compatibility of the model: R = -aS, with S being the deviatoric part of the stress tensor derived from ( 6):

S = -µ ρ ρ 0 ( 1 -2ã 3 j 1 { g - j 1 3 I } + ã { g 2 - j 2 3 I }) . ( 12
)
The relaxation step is performed after the hyperbolic step: there is no space variation during the relaxation process. The derivative D/Dt should be replaced by the partial derivative with respect to time:

D Dt = ∂ ∂t .
In the following, we write

∂ ∂t = d dt .
We have to solve the following relaxation equation for each cell:

dG dt = a τ rel (GS + SG) = 2a τ rel (GS) . ( 13
)

Von Mises yield criterion

The Von Mises criterion implies that the material starts to yield when the corresponding yield function (noted f (S)) becomes positive:

f (S) = S : S - 2 3 σ 2 Y , ( 14
)
Here σ Y is the yield strength. When the yield function is negative, the material has an elastic behavior. In this case, the relaxation time τ rel becomes infinite. If the yield function is positive we have to relax the deformations in such a way that at the end of the relaxation step, the yield surface is recovered.

The value of a is taken as,

a = 1 2 (S : S) 1/2 . ( 15
)
The following expression for the relaxation time is used [START_REF] Favrie | Mathematical and numerical model for nonlinear viscoplasticity[END_REF]:

1 τ rel =            1 τ 0 ( S : S -2 3 σ 2 Y σ 2 Y )n , if S : S -2 3 σ 2 Y σ 2 Y > 0, 0, if S : S -2 3 σ 2 Y σ 2 Y ≤ 0.
The values of the characteristic time τ 0 and the exponent n will be chosen latter. This expression is analogous to the Odquist law [START_REF] Lemaitre | Mécanique des matériaux solides[END_REF].

Numerical treatment

It has been proven that system (1) is hyperbolic when closed by the equation of state ( 5) and ( 6) ( [START_REF] Ndanou | The piston problem in hyperelasticity with the stored energy in separable form[END_REF], [START_REF] Gavrilyuk | An example of a one-parameter family of rank-one convex stored energies for isotropic compressible solids[END_REF]). The full system admits 7 characteristic eigenfields corresponding to 2 longitudinal waves, 4 shear waves and a contact discontinuity. The resolution of the Riemann problem is not straightforward. In order to simplify the resolution of the Riemann problem, a numerical splitting is performed for the full system. This method has been proposed in [START_REF] Favrie | A thermodynamically compatible splitting procedure in hyperelasticity[END_REF]. The full system is split in three sub-models, each of them is hyperbolic. The first sub-system deals with the longitudinal waves and the contact discontinuity while other sub-systems deal with the shear waves. The numerical splitting simplifies the solution of the Riemann problem at each cell edges. Indeed, as each sub-model admits the propagation of three waves. An HLLC type Riemann solver can be considered to compute fluxes. The details of the splitting for the multi-component case and multi-dimensional case are presented in [START_REF] Hank | Modeling hyperelasticity in non equilibrium multiphase flows[END_REF]. The three sub-models are written hereafter (in one dimensional case).

                                                       ∂α k ∂t + u I ∂α k ∂x = 0 ∂(αρ) k ∂t + ∂(αρu) k ∂x = 0 ∂(αρu) k ∂t + ∂(αρu 2 -ασ 11 ) k ∂x = -σ 11,I ∂α k ∂x ∂(αρv) k ∂t + ∂(αρuv) k ∂x = 0 ∂(αρw) k ∂t + ∂(αρuw) k ∂x = 0 ∂(αρE) k ∂t + ∂(αρEu -ασ 11 u) k ∂x = -σ 11,I u I ∂α k ∂x ∂(αa β ) k ∂t + ∂(αa β u) k ∂x = 0, β = 1, 2, 3, ∂b β k ∂t + u k ∂b β k ∂x = 0, β = 1, 2, 3, ∂c β k ∂t + u k ∂c β k ∂x = 0, β = 1, 2, 3. (16)
System ( 16) deals with the longitudinal waves and the contact discontinuity. The variables with the subscript 'I' are used to identify the interface variables. These interface quantities are obtained by solving the Riemann problem. The longitudinal sound speed is given by the following expression:

c L k = ∂p k ∂ρ k η k - ∂S 11k ∂ρ k - 1 ρ k 3 ∑ β=1 ∂S 11k ∂a β k a β k . ( 17
)
The sub-systems for transverse waves are:

                                                       ∂α k ∂t = 0 ∂(αρ) k ∂t = 0 ∂(αρu) k ∂t = 0 ∂(αρv) k ∂t - ∂(ασ 12 ) k ∂x = -σ 12I ∂α k ∂x ∂(αρw) k ∂t = 0 ∂(αρE) k ∂t + ∂(-ασ 12 v) k ∂x = -σ 12I v I ∂α k ∂x ∂(αa β ) k ∂t + (αb β ) k ∂v k ∂x = 0, β = 1, 2, 3 ∂b β k ∂t = 0, β = 1, 2, 3 ∂c β k ∂t = 0, β = 1, 2, 3 ,                                                        ∂α k ∂t = 0 ∂(αρ) k ∂t = 0 ∂(αρu) k ∂t = 0 ∂(αρv) k ∂t = 0 ∂(αρw) k ∂t - ∂(ασ 13 ) k ∂x = -σ 13I ∂α k ∂x ∂(αρE) k ∂t + ∂(-ασ 13 w) k ∂x = -σ 13I w I ∂α k ∂x ∂(αa β ) k ∂t + (αc β ) k ∂w k ∂x = 0, β = 1, 2, 3 ∂b β k ∂t = 0, β = 1, 2, 3 ∂c β k ∂t = 0, β = 1, 2, 3 (18)
The expressions of the transverse sound speeds are given hereafter:

c t1 k = - 1 ρ k 3 ∑ β=1 ∂S 12k ∂a β k b β k , c t2 k = √ - 1 ρ k ∂S 13k ∂a β k c β k . ( 19
)
Both sub-systems [START_REF] Lemaitre | Mécanique des matériaux solides[END_REF] deal with the shear waves and can be solved simultaneously. The three submodels correspond to the continuous limit of the discrete models obtained by integrating the pure solid equations over a multiphase control volume. Each sub-system is hyperbolic (see [START_REF] Hank | Modeling hyperelasticity in non equilibrium multiphase flows[END_REF] for details). The integration scheme is a first order finite volume Godunov type scheme. The fluxes must be calculated at each cell edges. To do this, a HLLC type solver is used [START_REF] Toro | Riemann solvers and numerical methods for fluid dynamics: a practical introduction[END_REF].

After the hyperbolic step solving ( 16), [START_REF] Lemaitre | Mécanique des matériaux solides[END_REF], relaxation terms are treated. A fourth order Runge-Kutta scheme is considered because of the stiffness of the right-hand side terms. Two versions of the code have been developed: a 3D code and 2D axi-symmetric version, both are parallel. The parallelization is performed using the domain decomposition method and using the openMPI library (open source Message Passing Interface).

Validations

The aim of this section is the validation of the elastic-plastic model. Two test cases are considered in this section: high and low velocity impacts.

Impact of a copper rod

The plastic deformation induced by the normal impact of a rod is a classical problem of impact solid dynamics ( [START_REF] Taylor | The testing of materials at high rates of loading[END_REF][START_REF] Taylor | The use of flat-ended projectiles for determining dynamic yield stress. I. Theoretical considerations[END_REF]). We use experimental data provided in [START_REF] Forde | Symmetrical Taylor impact studies of copper[END_REF], where a symmetric rod-on-rod impact has been studied. Symmetric rod-on-rod impact at velocity V is equivalent to a "classical" impact at velocity V /2. Symmetric impact allows us not to consider properties of the impacted surface which can be important in the case of the "classical" Taylor impact.

Initial configuration

The initial configuration is presented in Figure 1 cells. The final physical time is 368 µs. We are interested in the study of the temporal evolution of the shape of the copper rod. The numerical results are then compared to those of [START_REF] Forde | Symmetrical Taylor impact studies of copper[END_REF] wherein the authors measure the copper rod radius as a function of the distance from the impact interface. Two materials are used for these computations: copper and air. Physical characteristics of both components are given in table 1.

Material γ P ∞ (GP a) µ (GP a) σ Y (M P a) ρ 0 (kg/m 3 ) τ 0 (s) n Copper 4.54
29.9 60 450 8924 6.10 -6 2 Air

: stiffened gas parameters and physical characteristics of copper and air.

The properties of the stiffened gas equation of state are determined by using the Russian Shock wave database www.ficp.ac.ru/rusbank/.

Simulation results

The available experimental data are given up to 68 µs. We have made the choice to perform the simulation until the stationary state would be reached. This allows us to measure the final dimensions of the rod (final length, final undeformed length) and especially to compare with the Taylor theory.

Comparison with the experimental results

The rod profiles obtained at different instants are compared to those given in [START_REF] Forde | Symmetrical Taylor impact studies of copper[END_REF], where the authors present high speed photograph of the rod-on-rod impact. The rod profiles are extracted at various time instants from the moment of impact, as a function of the distance from the impact interface. In Figure 2, the experimental results are compared to the numerical ones. The numerical profiles are obtained by extracting the contours of copper volume fractions. The value 0.5 of these contours corresponds to the position of the copper/air interface.

The results presented in Figure 2 show a good agreement, particularly regarding the global shape of the rod. The rod radius at the impact is under-evaluated by the model, especially during the first instants, when the deformation is mainly located near the impact interface. The gap between experimental results and numerical results decreases with time. The gap can be explained by the fact that we did not use work-hardening in the elastic-plastic model. Nevertheless, the error is quite small, just about 1 mm. In Figure 3, the rod radius at the impact interface is plotted as a function of time as well as the rod total length. The final radius is reached after 100 µs, its value is 10.74 mm, the total rod length tends to the value of 73.1 mm. The qualitative evolution of the copper rod profile is presented in order to appreciate the deformation induced by the impact. The Figure 4 shows the deformation of the copper rod due to the impact at different instants. It allows us to notice the appearance of the 'shoulders' on the rod shape (see the rod shape at instant 128µs in Figure 4). The rod shape tends to a stationary state after about 200 µs. It is interesting to compare the resulting final dimensions with the Taylor analysis [START_REF] Taylor | The use of flat-ended projectiles for determining dynamic yield stress. I. Theoretical considerations[END_REF]. Let L 1 be the final length of the rod and X the undeformed rod length. The Taylor theory links the final rod dimensions to features of the impact:

σ Y ρ p V 2 = L -X 2(L -L 1 ) 1 L/X ( 20
)
The simulation gives the following values : L 1 = 73.1mm and X = 39mm. It gives us :

L -X 2(L -L 1 ) 1 L/X ≈ 1.04.
The gap between the theoretical value and the calculated one is equal to 6.8 per cent.

Impact of a jelly-like material

Studied configuration

In this simulation, a sample of clay suspension of diameter D normally impacts a flat rigid surface. This kind of impact has been studied, in particular, in [START_REF] Luu | Drop impact of yield-stress fluids[END_REF]. Experiments were made on different surface types (smooth glass surface and super hydrophobic surface). In this paper, we extract the results associated to the bentonite impacting a smooth glass surface. In particular, we are interested in the final diameter of the impacting drop. The studied configuration is presented in L 0 as the diameter of the equivalent sphere of the same volume. Two materials are present in this this configuration : the clay suspension cylinder (bentonite) and surrounded air. The corresponding material parameters are given in Table 2. The initial diameter of the cylinder is equal to 14 mm. The associated value of L 0 is 15.08 mm. The experimental results show a quasi-linear behavior of the maximal spread factor with respect to the impact velocity. The aim is then to see if the elastic-plastic model can reproduce this evolution.

Numerical results

Several simulations has been performed with various values of the impact velocity (1 m/s, 2 m/s, 3m/s, 4m/s). The results of these computations are summarized in Figure 6 where the numerical results are compared to those of [START_REF] Luu | Drop impact of yield-stress fluids[END_REF]. The numerical results are in a good agreement with the experimental ones. The points corresponding to the numerical results follow a straight line.

Let us define the time T 0 such that,

T 0 = L 0 V 0 (21)
Here L 0 is the characteristic dimension of the droplet, and V 0 is the impact velocity. The dimensionless time is then given by t/T 0 , where t corresponds to the physical time. Figure 7 shows the qualitative comparison of the numerical results with the experimental ones at several time instants (t/T 0 = 0.07, t/T 0 = 0.3 t/T 0 = 0.6, t/T 0 = 0.8). validated on impact experiments involving impact velocities varying from 1 m/s to 200 m/s. Very different materials were considered: clay suspension and copper. The numerical solution is in a good agreement with the experimental data. The developed numerical model is also able to describe more complex phenomena like cracks formation and spallation in materials. These results will be presented in future publications.

SolidFigure 1 :

 1 Figure 1: Studied configuration: the impact of a copper rod on a solid wall is performed. The impact velocity is 197.5 m/s. The rod diameter is D = 10 mm and the length L = 100 mm.

Figure 2 :

 2 Figure 2: The copper rod radius is plotted as a function of the distance from the impact interface at several instants.

Figure 3 :

 3 Figure 3: Time evolution of the rod radius at the impact interface between 0 µs and 368 µs.

Figure 4 :

 4 Figure4: The copper rod is presented at several instants from the moment of the impact, 0 µs, 32 µs, 64 µs, 96 µs, 128 µs, 160 µs, 192 µs and 320 µs. The shape of the rod changes during the impact and tends to a stationary state. The formation of "shoulders" (of a new "inflection" point at the rod shape) can clearly be observed at the instant 128 µs.

Figure 5 .Figure 5 :

 55 Figure 5: Studied configuration: the impact of a clay suspension cylinder at the velocity V.

2 :

 2 Materialγ P ∞ (GP a) µ (P a) σ Y (P a) ρ 0 (kg/m 3 ) τ 0 (s) stiffened gas parameters and features of the clay suspension and air.

Acknowledgements

We thank Y. Forterre for providing us the experimental data, and P. Le Tallec and P. H. Maire for useful discussion. This work was partially supported by l'Agence Nationale de la Recherche, France (grant numbers ANR-14-ASTR-0016-01, ANR-11-LABX-0092, and ANR-11-IDEX-0001-02).

Figure 6: The maximal spread factor L m /L 0 as a function of the impact velocity in the case of a bentonite drop impacting smooth glass surface (comparison with the experimental data of [START_REF] Luu | Drop impact of yield-stress fluids[END_REF]).

Figure 7: Comparison between the experimental results (at the top) with the numerical results (at the bottom) for several time instants of t/T 0 (t/T 0 = 0.07, t/T 0 = 0.3 t/T 0 = 0.6, t/T 0 = 0.8). The velocity impact is equal to 2 m/s.

The initial shape of the 'numerical' drop (see Figure 5) is not exactly the same one compared to the real drop. The real drop is generated by a syringe driver and falls then freely under gravity. This can explain a 'pointed' crest observable on the real drop. The dynamic behaviour of the bentonite drop is well reproduced by the simulation. A good agreement with the experimental results can be observed, both for the maximal spread factor (Figure 6) and for the form of the drop (Figure 7).

Conclusion

A visco-plastic Eulerian hyperbolic model is proposed. A simulation tool has been was developed to model simultaneously an arbitrary number of materials of different nature (fluids and solids). It is


S Calvez
email: scalvez@laas.fr

G Lafleur

A Larrue

P.-F Calmon

A Arnoult

O Gauthier-Lafaye

G Almuneau

AlOx/AlGaAs technology for multi-plane integrated photonic devices

Keywords: III-V semiconductor oxidation, anisotropy, microdisk resonators

The III-V semiconductor /oxide technology has become the standard fabrication technique for Vertical-Cavity Surface-Emitting Lasers. Current research aims to further enhance the performance of these emitters and diversify the range of devices that can be made using this technology.

In this paper, we present a new model of the oxidation process which includes the anisotropic behaviour observed during conventional lateral oxidation. Furthermore, we demonstrate that this technology can be used as an innovative method to make micro-disk resonators with vertically-coupled access waveguides, an approach which can be generalised to fabricate other types of multi-plane photonic devices.

INTRODUCTION

The oxidation of III-V semiconductors is a process which selectively transforms high-aluminium-containing semiconductor alloys of high index of refraction (n AlAs ~2.9) into aluminium oxide (AlOx), an insulator with lower index of refraction (n AlOx ~1.6). Initially considered as a degradation and failure mechanism [START_REF] Dallesasse | III-V Oxidation: Discoveries and Applications in Vertical-Cavity Surface-Emitting Lasers[END_REF], this process has since then gained recognition and wide commercial success for its use in the fabrication of Vertical-Cavity Surface-Emitting Lasers where laterally-oxidized buried layers set the electrical injection profile and define the emission spatial mode content [START_REF] Choquette | Advances in selective wet oxidation of AlGaAs alloys[END_REF]. Recently, the research in this field has been primarily concerned with further expanding the capabilities of these oxide-confined VCSELs by improving their performance, for instance by increasing their modulation bandwidth thanks to multi-oxide layers [START_REF] Chang | Efficient, High-Data-Rate, Tapered Oxide-Aperture Vertical-Cavity Surface-Emitting Lasers[END_REF], or by extending their wavelength coverage to the mid-infrared region [START_REF] Laaroussi | Oxide confinement and high contrast grating mirrors for Mid-infrared VCSELs[END_REF]. However, a secondary strand of research activities on III-V semiconductor/AlOx technology has also emerged with the objective to further exploit the oxidation process [START_REF] Dallesasse | Oxidation of Al-bearing III-V materials: A review of key progress[END_REF] in wider range of devices including nonlinear optical converters [START_REF] Fiore | Phase matching using an isotropic nonlinear optical material[END_REF][7], transistor lasers [START_REF] Walter | Laser operation of a heterojunction bipolar light-emitting transistor[END_REF] or photovoltaic cells [START_REF] Pan | High efficiency group iii-v compound semiconductor solar cell with oxidized window layer[END_REF].

In this article, we present our recent contributions to the latter research strand. In particular, we report the characterisation and the analysis of the anisotropy of the oxide formation in AlGaAs. We also show how this technology can be exploited to create multiple-plane photonic devices and, more specifically, microdisk resonators that vertically-coupled to their access waveguides.

ALGAAS WET OXIDATION: AN ANISOTROPIC PROCESS

To-date, the oxidation of Al-containing III-V semiconductors (and AlGaAs in particular) has mostly been considered as an isotropic process. As a result, the oxidation of a thin (typically <100nm thick) layer is commonly treated as a one-dimensional phenomenon during which the lateral position of the oxide/semiconductor interface evolves as a function of the oxidation time. In essence, the established models are all based on the empirical law established by Deal and Grove [START_REF] Deal | General Relationship for the Thermal Oxidation of Silicon[END_REF] for the planar oxidation of silicon. Refinements have been added to take into account the effect of the finite thickness of the layer to be oxidized [START_REF] Osinski | Temperature and thickness dependence of steam oxidation of AlAs in cylindrical mesa structures[END_REF][12] and, to an extent, to include the first-order modification of the process dynamics resulting from the continuously varying perimeter of the oxide/semiconductor interface as the oxidation progresses [START_REF] Osinski | Temperature and thickness dependence of steam oxidation of AlAs in cylindrical mesa structures[END_REF][12] [START_REF] Alonzo | Effect of cylindrical geometry on the wet thermal oxidation of AlAs[END_REF].

A few reports have however highlighted that the process is actually anisotropic [START_REF] Vaccaro | AlAs oxidation process in GaAs/AlGaAs/AlAs heterostructures grown by molecular beam epitaxy on GaAs (n11) A substrates[END_REF][15] [START_REF] Chouchane | Local stressinduced effects on AlGaAs/AlOx oxidation front shape[END_REF] although evidence of this fact could also be found in earlier work [START_REF] Huffaker | Native-oxide defined ring contact for low threshold vertical-cavity lasers[END_REF] [START_REF] Choquette | Advances in selective wet oxidation of AlGaAs alloys[END_REF]. In particular, P.O. Vaccaro et al observed that oxidized thin AlGaAs layers on (110) and (311)-oriented GaAs substrates present an in-plane three-fold-symmetry anisotropy [START_REF] Vaccaro | AlAs oxidation process in GaAs/AlGaAs/AlAs heterostructures grown by molecular beam epitaxy on GaAs (n11) A substrates[END_REF] [START_REF] Koizumi | Lateral wet oxidation of AlAs layer in GaAs/AlAs heterostructures grown by MBE on GaAs (n11) A substrates[END_REF]. We have also shown that the oxidation of (~500nm)-thick layers of AlGaAs on conventional (100)-GaAs substrates leads to tapered vertical profiles [START_REF] Chouchane | Local stressinduced effects on AlGaAs/AlOx oxidation front shape[END_REF] whose tapered angle is attributed to the embedded strain resulting from the AlOx (~7%-)reduced volume compared to the AlGaAs material.

Here, we draw the attention to the in-plane anisotropy observed upon oxidation of thin (68nm-thick) Al 0.98 Ga 0.02 As layers on (100)-oriented GaAs wafers and propose an extension of the model of the oxidation process to render this anisotropic behaviour.

To begin with, Figure 1 presents a sequence of infrared microscope images of the lateral oxidation of a 35µmdiameter disk from the edges a dry-etched circular mesa [START_REF] Almuneau | Real-time in situ monitoring of wet thermal oxidation for precise confinement in VCSELs[END_REF]. The sample was oxidised at 400°C in a reduced pressure environment (~0.5 atm.), using a H 2 /N 2 /H 2 O gas steam mixture generated by an evaporator-mixer system operating at 95°C. In the pictures, the [0 -1 1]-oriented sample cleaved edge is set along the horizontal axis and the oxide part appears in white while the remaining (central) AlAs section is light grey. This change in intensity is induced by the change in the multilayer stack reflectivity at the observation wavelength (790 nm) and is caused by the modification of the optical path in the Al 0.98 Ga 0.02 As/AlOx layer upon oxidation. It can clearly be observed that the oxidation of the circular mesa tends towards a diamond-shaped aperture (t ox >100 min), highlighting that the process is indeed anisotropic with a faster reaction rate along the {0 -1 0} directions. To more accurately reproduce this anisotropic oxidation, we simulate the oxidation using a truly bi-dimensional model where the oxidation process is considered to be the combination of an anisotropic reaction, which takes place at the oxide-semiconductor interface, and an isotropic diffusion process which accounts for the transfer of the reactants (and As-based by products) from the outer part of the mesa to the reaction interface (and viceversa).

Figure 2 shows the calculated oxidation contours (with a diffusion coefficient D=20µm 2 /min, a fast reaction rate coefficient k max =0.12 µm/min and anisotropic factor a aniso =0.1) corresponding to the experimental oxidation process presented in Figure 1. The visual agreement between experimental data and numerical simulations confirms the appropriateness of the developed model.

VERTICALLY-COUPLED MICRODISK RESONATORS

The ability to predict and in-situ monitor the oxidation of III-V compounds opens an avenue to realise photonic devices relying on oxidation patterns of greater complexity than VCSELs [START_REF] Dallesasse | III-V Oxidation: Discoveries and Applications in Vertical-Cavity Surface-Emitting Lasers[END_REF] or straight waveguides [START_REF] Dallesasse | Oxidation of Al-bearing III-V materials: A review of key progress[END_REF]. As an proof of principle, we have recently made microdisk resonators with vertically-coupled access waveguides [START_REF] Calvez | Vertically Coupled Microdisk Resonators Using AlGaAs/AlOx Technology[END_REF]. The AlGaAs multi-layer stack is, in this case, constituted of two coupled GaAs waveguides whose coupling layer vertical structure includes two Al 0.98 Ga 0.02 As layers to be oxidized. The lower layer permits the introduction of the lateral confinement required to establish a buried rib-type access waveguide while the upper layer serves to significantly reduce the vertical coupling between the resonator and the remaining underlying slab waveguide. The transmission characteristics of a 75µm-diameter microdisk (see Figure 2) revealed a Q factor of ~4610 for the fundamental whispering gallery modes of the microdisk, corresponding to an attenuation coefficient in the disk of ~4.8 cm -1 and a coupling factor to the access waveguide of 64.8%.

CONCLUSIONS

We have reported a new model of the oxidation of III-V semiconductor that takes into account the anisotropy of the process and demonstrated that this technology can be used to create multi-plane photonic devices via the fabrication of micro-disk resonators with vertically-coupled access waveguides.

Figure 1 :

 1 Figure 1: Sequence of infrared images of the anisotropic lateral oxidation of a 35µm-diameter disk mesa.

Figure 2 :

 2 Figure 2: Sequence of calculated two-dimensional oxidation profiles (in red) of a 35µm-diameter disk (blue mesa) for regularly separated oxidation times ranging from 0 to 2 hours

Figure 3 :

 3 (a) Composite (IR, visible) image of a 75µm-diameter microdisk resonator coupled to its access waveguide. (b) Transmission characteristic of this device.

ACKNOWLEDGEMENTS

The authors would like to acknowledge that this work was partly supported by the Centre National d'Etudes Spatial (CNES) and the French RENATECH network of micro-fabrication facilities.