Davide Frey

Marc X Makkes

Pierre-Louis Roman

François Taïani

Spyros Voulgaris

Dietcoin: shortcutting the Bitcoin verification process for your smartphone

Keywords: blockchain, sharding, UTXO, distributed ledger, cryptocurrency, mobile computing

Blockchains have a storage scalability issue. Their size is not bounded and they grow indefinitely as time passes. As of August 2017, the Bitcoin blockchain is about 120 GiB big while it was only 75 GiB in August 2016. To benefit from Bitcoin full security model, a bootstrapping node has to download and verify the entirety of the 120 GiB. This poses a challenge for low-resource devices such as smartphones. Thankfully, an alternative exists for such devices which consists of downloading and verifying just the header of each block. This partial block verification enables devices to reduce their bandwidth requirements from 120 GiB to 35 MiB. However, this drastic decrease comes with a safety cost implied by a partial block verification. In this work, we enable low-resource devices to fully verify subchains of blocks without having to pay the onerous price of a full chain download and verification; a few additional MiB of bandwidth suffice. To do so, we propose the design of diet nodes that can securely query full nodes for shards of the UTXO set, which is needed to perform full block verification and can otherwise only be built by sequentially parsing the chain.

Dietcoin: court-circuiter la vérification dans Bitcoin pour les téléphones mobiles

Résumé :

Les blockchains telles que Bitcoin passent mal à l'échelle, notamment du fait de leurs besoins important de stockage. Les besoins de stockage d'une blockchain typique ne sont pas limités et croissent indéfiniment. Par exemple, en août 2017, les données contenues dans la blockchain Bitcoin représentaient environ 120 GiB, contre 75 GiB un an auparavant, en août 2016. Pour bénéficier des garanties complètes de sécurité apportées par Bitcoin, un noeud qui rejoint le réseau doit télécharger et vérifier l'intégralité des 120 GiB de données. Cette nécessité pose un défi pour les appareils à faibles ressources tels que les smartphones. Heureusement, une alternative existe pour de tels dispositifs qui consiste à télécharger et à vérifier seulement l'en-tête de chaque bloc de la blockchain. Cette vérification partielle des blocs permet aux appareils de réduire leurs besoins en bande passante de 120 GiB à 35 MiB, mais cette diminution drastique ne permet qu'une vérification partielle des blocs, et diminue grandement les garanties de sécurité offertes aux noeuds qui l'utilisent.

Dans ce travail, nous proposons une approche qui permet aux appareils à faibles ressources de vérifier entièrement des sous-chaînes de blocs sans avoir à payer le prix onéreux d'un téléchargement et d'une vérification complète de la chaîne ; quelques MiB supplémentaires de bande passante suffisent. Pour ce faire, nous proposons d'introduire des noeuds Dietcoin qui sont capables en toute sécurité d'interroger des noeuds exécutant le protocole complet pour obtenir des fragments d'un ensemble appelé UTXO, nécessaire à la vérification complète des blocs.

Mots-clés : blockchain, partitionnement, UTXO, registre distribué, monnaie cryptographique, informatique mobile 1 Trustless Bitcoin Within a decade, blockchains have become extremely popular, and have been used to implement several widely-used crytocurrencies [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], and smart-contract services [START_REF] Dickerson | Adding concurrency to smart contracts[END_REF]. A blockchain implements a tamper-proof distributed ledger in which public transactions can be recorded in a close-toirrevocable manner. Recorded transactions are stored into blocks, which are then incrementally linked (or chained ) in order to form an append-only list. The irrevocability of these chaining mechanisms exploits cryptographic mechanisms and peer-to-peer exchanges. This combination makes it in principle inconceivably hard for individual participants to revoke past transactions (due to the computational cost involved), while it remains possible for any participant to verify the validity of a blockchain's entire history. Verifying a blockchain remains, however, a particularly costly process. The verifying node must first download the entire blockchain, which in many cases has reached a size beyond the communication capabilities of many mobile devices. The Bitcoin blockchain, for instance, had grown to 120 GiB as of August 2017 (Figure 1), and follows an exponential growth, implying the problem can only become more acute.

Once the blockchain has been downloaded, the verifying node must then check its consistency block by block, a lengthy process that can take hours on high-end machines. The exorbitant price of a full chain verification makes it unrealistic for low-resource devices to fully implement a blockchain protocol. Some blockchain systems, such as Bitcoin, therefore enable nodes to perform varying degrees of verification: full nodes verify everything while lightweight nodes only verify a small fraction of the data.

In the case of Bitcoin, this lightweight verification is known as Simplified Payment Verification (SPV for short). SPV nodes only download and verify a much reduced version of the Bitcoin blockchain, comprised only of its block headers, which today only weights 35 MiB (a reduction by three orders of magnitude). This summary version however only contains the chaining information making up the blockchain, not the recorded transactions. This information is sufficient for SPV nodes to verify that the chain's structure is valid (and hence very unlikely to have been created by malicious nodes), but not that a past transaction does exist in the chain. As a result, SPV nodes are vulnerable to attacks in which an attacker leads an SPV node to believe a transaction t has occurred, while t is later on rejected by the system because the funds transferred by t have in fact already been spent (known as a double-spend attack ).

To protect themselves against double-spend attacks, full nodes keep track of unspent funds in a structure known as the set of Unspent TransaCTion Outputs (UTXO set). The UTXO set is unfortunately costly to construct (as this construction requires the entire blockchain), to exchange (currently weighing 1.9 GiB, see Figure 1), and to maintain, which explains why SPV nodes do not use it.

In this report, we propose to bridge the gap between full nodes and SPV nodes by introducing diet nodes, and their associated protocol, Dietcoin. Dietcoin strengthens the security guarantees of SPV nodes by bringing them close to those of full nodes. Dietcoin enables low-resource nodes to verify the transactions contained in a block without constructing a full-fledged UTXO set. In our protocol, diet nodes download from full nodes only the parts of the UTXO set they need in order to verify a transaction of interest. This selective download mechanism must, however, be realized with care. Diet nodes must be able to detect any tampering of the UTXO set itself, at a cost that remains affordable for low-resource devices, both in terms of communication and computing overhead.

The rest of this report is structured as follows. We first present the Bitcoin protocol in more detail (Section 2), and explain the workings of full and SPV nodes. We then detail the design of Dietcoin and diet nodes and discuss the security guarantees they provide (Section 3). Finally, we present related work (Section 4), and conclude (Section 5).

The Bitcoin system

A blockchain is a decentralized ledger composed of blocks containing transactions. The transactions, the blocks, and the resulting chain obey a few core rules that ensure the system remains tamper-proof. Great care is required when modifying these rules, as even minor changes might break the blockchain's properties and its security guarantees. In the following, we first detail the default workings of the Bitcoin blockchain and its rationale 1 . We then build upon these explanations to introduce and justify the changes we are proposing.

Overview

In a blockchain system such as Bitcoin, the blockchain proper ((B k ) k∈Z ≥0 , label 1 in Figure 2) is maintained by a peer-to-peer network of miners. Each block B k links to the previous block B k-1 by including in its header a cryptographic hash that is (i) easy to verify, but (ii) particularly costly to create (this second point is one of the central element of blockchains with open membership, which we will discuss in detail just below). The leftmost block B 0 is known as the Genesis Block : it is the first and oldest block in the blockchain, and it is the only block with no predecessor.

Recording a new transaction

To transfer 8 bitcoins from herself to Bob, the user Alice must first create a valid transaction (label 2 ) that contains information proving she actually owns the 8 bitcoins (with a cryptographic signature using asymmetric keys), and encode the resulting transaction output with Bob's public key (such that, in turn, only Bob will be able to demonstrate ownership of the transaction's output).

Alice then broadcasts this new transaction to the network of miners 3 , in order for it to be included in the blockchain. Before adding Alice's transaction into the blockchain, Miner A first verifies that the transaction is valid (label 4 in Figure 3, details on the transaction verification process will follow in Section 2.2.1-(BV2)).

Miner A then includes Alice's transaction together with other transactions received in parallel into a new block (B 3 , 5 ), and attempts to link it to the current tip of the blockchain. This linkage operation requires Miner A to solve a probabilistically difficult cryptopuzzle 6 that regulates the frequency at which blocks are created (or mined ) by the whole network. (In Bitcoin, this periodicity is set to one block every 10 minutes.) If Miner A succeeds, the new block B 3 is now 1 Blockchains with closed membership or different consensus protocols are not discussed in this section RR n°9162 The new block ultimately reaches Bob 9 , who can check that the transaction has been properly recorded (and can then, for example, sell some goods to Alice).

... þ þ þ B 0 B 1 B 2 B 3 B 0 B 1 B 2 B 3 Bob 9

Irrevocability of deep blocks

Because blocks are produced at a limited rate such that all the miners receive block B k before they can successfully mine a concurrent block B k , honest miners are highly likely to extend the chain when producing a new block, ensuring a consistent system state with high probability. The views of individual miners may however diverge in problematic cases, causing branches to appear. When a branch occurs, miners resolve the divergence by choosing as valid branch the one that was the most difficult to create (details on block difficulty will follow in Section 2.2.1-(BV2)). Blocks that are left out of the chain are said to be orphan.

The risk of being made orphan decreases exponentially as a block lies deeper in a chain, ensuring the practical irrevocability of deep blocks and the transactions they contain. This is illustrated in Figure 4: consider an attacker who wishes to revoke a block B n-k (targeted block), that lies k blocks away from the chain's tip B n . For this attack to succeed, this attacker must produce an alternative subchain (B n-k , .., B n , B n+1 ) that is more difficult to create than the current chain. Producing this subchain is however extremely costly, and takes time which increases the odds that the legitimate chain grows (with a block B n+1 , thus requesting an even more difficult attack subchain) before the attacker succeeds. When the computing power of the attacker is less than half of that of the rest of the network, his probability of success drops exponentially with k.

Inria B n-k-1 B' n-k B n-k B n Current blockchain ... ... ... B' n B' n+1

Hijacking a3empt

Targeted block

Transactions, Blocks, and UTXO set

To benefit from the full security of Bitcoin, Bob should verify the validity of the new block that contains Alice's payment to him (label 9 in Figure 3) in addition to verifying the validity of Alice's transaction. This is because Alice could collude with a miner (or launch herself a miner), and produce an invalid block that she would advertise to Bob. Bitcoin relies on a number of builtin validity checks on blocks and transactions to conduct this verification. However, whereas full nodes exploit all of these checks, Simple Payment Verification nodes (SPV nodes) only perform a limited verification. In the following, we describe the details of these validity checks, we discuss the role of an intermediary set known as the set of Unspent TransaCTion Outputs (UTXO set), and the shortcomings of SPV nodes ensued by the limited verification they perform.

Checking block validity

A block is valid if and only if it meets the following two conditions.

• (BV1) Its header respects the blockchain's Proof-of-Work predicate.

• (BV2) It only contains valid transactions (which we discuss further below).

BV1:

The Proof-of-Work predicate makes it very difficult for malicious actors to alter the blockchain in an attempt to edit the ledger. The Proof-of-Work predicate is used as a lock-in mechanism to anchor blocks in the chain. It is enforced on each block header, whose simplified structure is shown in Figure 5. The header of each block B k points both to the header of the previous block B k-1 (using a hash function, 1 ), and to the transactions contained in the current block B k 2 . To fulfill the Proof-of-Work predicate 4 , a header must contain a nonce 3 such that the hash of the header is less than a difficulty target. The difficulty target is set so that a new block is created every ten minutes by the miners as a whole, regardless of the computation power (the difficulty target is regularly adjusted to cope with changes in their computation power). Finding a nonce respecting the difficulty target is computationally very expensive, as every miner competes to create blocks. This computing cost prevents attackers from easily tampering the chain as they have to recompute fresh nonces for the blocks they wish to replace.

To establish a secure and verifiable link between the header of B k and the corresponding block B k , the pointer to B k 's transactions 2 consists of the root of a Merkle tree. A Merkle tree is a hierarchical hashing mechanism for sets that enables a verifier to efficiently test whether an item (here a transaction) belongs to the set by reconstructing the root of the Merkle tree. Each leaf node in a Merkle tree consists of the hash of an item, while each internal node (including A the root) consists of the hash of its children. This makes it possible to reconstruct the root, and thus verify set membership, using only a logarithmic number of intermediate hashes. In Figure 6 for example, a node can verify the presence of transaction A in the set by (i) downloading the root from a secured communication channel (e.g., the blockchain), and (ii) downloading A and the three intermediate hashes shown in red: H B , H CD and H EF GH , and reconstructing the root from the downloaded hashes. The reconstructed root should match the downloaded one. BV2: In addition to the Proof-of-Work predicate (BV1), all the transactions included in a block must also be valid for the overall block to be valid. Figure 7 shows the validity mechanisms included in a typical Bitcoin transaction. In this example, Alice uses 3 coins she owns (the transaction's inputs 1 ) to pay 7 Bitcoins to Bob, and 4 to Tux (the transaction's outputs 2 ). Only coins created in earlier transactions may be spent: each of Alice's inputs therefore points back to the output of an earlier transaction 3 . To ensure that only the recipients (Bob and Tux) are able to spend the output, each new coin contains an ownership challenge (a hashed public key), that must be solved to spend this coin 4 .

H ABCD H B H C H D H A H AB H EFGH H F H G H H H E H EF H CD H GH H ABCDEFGH B C D E F G H Reconstructed Downloaded Unneeded
Alice's transaction is only valid if the following three conditions are met:

• (TV1) The inputs do exist, and Alice owns them. She can prove her ownership of the inputs by providing a public key matching their ownership challenges 5 , and by signing the new transaction with the corresponding private key2 6 ;

• (TV2) No money is created in the transaction. In effect, the total value of the transaction's inputs must be greater than or equal to that of its outputs:

in∈inputs(t) value(in) ≥ out∈outputs(t) value(out).
The difference value(in) -value(out) is given as a fee to the miner of the block containing the transaction;

• (TV3) The transaction's inputs (tx_ID i , index j ) have not been spent yet (i.e., they do not appear as inputs of any earlier transaction, an attack known as a double spend ).

The set of Unspent TransaCTion Outputs (UTXO set)

While the validity of a block's header (BV1) only requires access to the current block B k , and to the header of its predecessor B k-1 , verifying transactions (BV2) requires a lot more information.

Verifying the ownership challenges of input coins (TV1), and their amount (TV2) requires access to the transactions recorded in earlier blocks. Worse, verifying that inputs coins have not yet been spent (TV3) potentially requires parsing and verifying the entire blockchain.

To avoid performing such a costly operation for each new block, nodes that verify transactions maintain an intermediary set known as the set of Unspent TransaCTion Outputs (UTXO set). The UTXO set contains all the coins that have been created in the chain but not spent in later transactions, it thus contains all the spendable coins.

A node verifying transactions can prevent double spends (TV3) by simply ensuring that all the inputs of a transaction appears in its UTXO set. The UTXO set evolves as new correct blocks are added to the chain: transaction outputs are removed from the set when they are spent, and outputs of new transaction are added to the set.

The limitations of SPV nodes

In spite of its benefits, constructing a local UTXO set is costly: in order to obtain the set, a node must first download the entire chain (120 GiB as of August 2017, see Figure 1) and validate it (a lengthy process that can take hours on high-end machines), even if only the latest block is relevant to its interest.

Because of this cost, Bitcoin supports several levels of verification. Miners and users running full nodes construct the UTXO set and check both block headers (BV1) and transactions (TV1,2,3 and as a result BV2). By performing all the possible checks, full nodes benefit from the maximum security that the Bitcoin system has to offer.

By contrast, Simple Payment Verification nodes (SPV nodes) do not construct the UTXO set. Instead, they only download the chain's block headers (rather than full blocks), and verify that these headers are valid (BV1). With the headers only, SPV nodes are able to verify the well-formedness of the blockchain including the crucial Proof-of-Work predicate that seals the links of the chain.

However, because this verification is only partial, SPV nodes are unable to detect if a new block contains an invalid transaction. This scenario, however probabilistically difficult to accomplish for an attacker, is a vulnerability of SPV nodes. To circumvent this vulnerability, SPV nodes typically wait until miners have created subsequent blocks extending the chain containing a block of interest, which implies that these miners have performed a full verification on it and consider this block as valid.

The need for SPV nodes to wait makes it particularly problematic to use Bitcoin on limited devices (i.e. mobile phones) for everyday transactions. SPV nodes are not even able to check whether the inputs used in a transaction do exist. It also limits the ability of SPV nodes to detect faulty transactions as early as possible, which is an important usability feature of modern payment systems.

In this work, we propose to overcome the inherent limitations of SPV nodes with Dietcoin. Dietcoin enables nodes with limited resources (diet nodes) to benefit from a security level that is close to that of full nodes, at a fraction of the cost required to run full security checks.

The Dietcoin system

To address the vulnerabilities of SPV nodes and to improve the confidence mobile users can have in recent transactions, we propose Dietcoin, an extension to Bitcoin-like blockchains. Although our proposal can be applied to most existing Proof-of-Work blockchains using the UTXO model for coins, we describe Dietcoin in the context of the Bitcoin system as presented in Section 2.

The core of Dietcoin consists of a novel class of nodes, called diet nodes, which provide lowpower devices with the ability to perform full block verification with minimal bandwidth and storage requirements. Instead of having to download and process the entire blockchain to build their own copy of the UTXO set, diet nodes query the UTXO set of full nodes and use it to verify the legitimacy of the transactions they are interested in (as described in Section 2.2.1-(BV2)) and the correctness of the blocks that contain them. This gives diet nodes security properties that sit in between those of full nodes, and those of Bitcoin's SPV nodes.

Consider a user wishing to verify a transaction for the sale of some goods. The user's diet node will initially proceed like a standard SPV node. It will contact a full node to obtain the header of the block that supposedly contains its transaction as well as the corresponding branch of the transaction Merkle tree, to verify that the transaction indeed is included in the block. But while an SPV node would stop at this inclusion check, the diet node continues by verifying both the inclusion and the correctness of all the transactions in the block. To make this possible we introduce the possibility for diet nodes to access the state of the UTXO set of full nodes corresponding to the instant right before the block they want to verify.

Since downloading the entire UTXO set would result in prohibitive bandwidth overhead, as shown in Figure 1, Dietcoin-enabled full nodes split their UTXO set into small shards, enabling diet nodes to download only the shards that are relevant to the transactions in the block.

Inria

To prevent diet nodes from trusting maliciously forged shards, the shard hashes are used as leaves of a Merkle tree, which root is stored in each block. Having the Merkle root stored in blocks enables the UTXO shards to benefit from the same Proof-of-Work protection as transactions.

In addition to the full verification done on the block of their interest B k , diet nodes can increase their trust in B k by fully verifying its previous blocks. By doing so, diet nodes are ensured that none of the l verified blocks contain illegal transactions nor erroneous UTXO Merkle root. To make a diet node trust a forged transaction in block B k , an attacker has to counterfeit the subchain of l + 1 blocks (B k-l , ..., B k ). Thanks to the Proof-of-Work protection, the cost of this attack increases exponentially as l increases linearly.

In the following, we detail the operation of Dietcoin by first describing how full nodes can provide diet nodes with verifiable UTXO shards. Secondly we discuss how miners link blocks to the state of their UTXO set. We then explain how diet nodes can extend the verification process from one block to a subchain of any length. Finally, we detail the operation of diet nodes when verifying transactions.

Sharding the UTXO set

To enable the operation of diet nodes, Dietcoin-enabled full nodes need (i) to provide diet nodes with shards of the UTXO set, while (ii) enabling them to verify that these shards are authentic.

To satisfy (i), Dietcoin-enabled full nodes store the UTXO set resulting from the application of the transactions in each block in the form of shards with a predefined maximum size of 1 KiB (on average, across all shards). The use of shards enables diet nodes to download only the relevant parts of the UTXO set and also limits the storage requirements at full nodes, which only need to store the modified shards for each block to let diet nodes query older versions of the shards. Similarly, the limit of 1 KiB for the size of each shard limits the bandwidth employed by diet nodes in the verification process.

To satisfy (ii), full nodes also maintain a Merkle tree that indexes all the shards of the UTXO set. Using shards also proves advantageous with respect to this Merkle tree. If nodes were to index UTXO entries directly, the continuous changes in the UTXO set would cause the Merkle tree to become quickly unbalanced, leading to performance problems or requiring a potentially costly self-balancing tree. The use of shards, combined with the right sharding strategy, gives the UTXO Merkle tree a relatively constant structure, enabling shards to be updated in place most of the time. Moreover, it makes it possible to predict the size of the UTXO Merkle tree and its incurred overhead, which enables us to better control and balance the storage overhead for full nodes and the bandwidth requirements of diet nodes.

A number of sharding strategies satisfy the requirement of a fixed number of shards. In this work, we use the simplest approach consisting of indexing UTXO entries by their first k bits. This strategy resembles a random approach since the first bits of an UTXO are the transaction hash it references, which value is expected to be random due to the uniformity property of the SHA-256 hash function. This strategy comes with the added advantages of obtaining shards of homogeneous size and a full binary Merkle tree with 2 k leaves.

Keeping in mind the size cap of 1 KiB per shard, k can be adapted locally by each node to cope with the growth of the UTXO set. When the average shard size breaches the cap of 1 KiB, k is incremented by one resulting in (i) halving the average shard size, and (ii) adding one layer to the Merkle tree, doubling its storage footprint in the process.

Linking blocks with the UTXO set

With reference to Figure 8, consider a Dietcoin-enabled miner that is mining block B k , and let UTXO k be the state of the UTXO set after applying all the transactions in B k . The miner stores the root of the UTXO Merkle tree associated with UTXO k as an unspendable output in the first transaction of block B k before trying to solve the Proof-of-Work as shown in Figure 8.

Storing the root of the UTXO Merkle tree in the first transaction of the block does not require any modification to the structure of Bitcoin's blocks. Thus it is possible for Dietcoin-enabled full nodes and miners to co-exist with their legacy Bitcoin counterparts. Dietcoin-enabled full nodes verify the value of the UTXO Merkle root against their own local copy when they verify a block, while legacy Bitcoin nodes simply ignore it. The UTXO Merkle tree provides a computationally efficient way for diet nodes to verify whether the shards they download during the verification process are legitimate and correspond to the current state of the ledger. Still referring to Figure 8, let us consider a diet node d that wishes to verify a transaction in block B k . Node d needs to obtain: block B k , the UTXO Merkle root in block B k-1 , the shards of the UTXO set between the two blocks, and the elements of the associated Merkle tree that are required to verify their legitimacy. It can then verify the shards using the root stored in block B k-1 's first transaction, and use them to verify the correctness of the transactions in B k .

We observe that storing the Merkle-root referring to the state after the block into the block itself forces diet nodes to download two blocks to verify transactions. This makes it inherently harder for an attacker to provide a diet node with a fake block B k because it would need to forge not only block B k but also block B k-1 .

Extended verification

Diet nodes have the ability to extend their confidence in a block by iterating the verification process towards its previous blocks. By doing so, diet nodes ensure the correctness of the UTXO Merkle root present in block B k-1 used to verify the correctness of block B k . The extended verification can be performed on a subchain of any length l provided that the verifying diet node can query UTXO shards of any age. A diet node fully verifying the subchain (B k-l+1 , ..., B k ) can only be tricked into trusting a malicious transaction in block B k if the attacker manages to counterfeit the l + 1 successive blocks starting from B k-l , which becomes exponentially more costly as l increases linearly.

Inria

The block B k-l contains the UTXO Merkle root that serves as a basis for the verification of the consequent blocks. Since the block B k-l is not verified, it is thus trusted by the diet node. A comparison can be made with full nodes where the first block of the chain, the genesis block, is hard-coded and is therefore trusted. By shifting the trust from the genesis block to the block B k-l for diet nodes, Dietcoin effectively shortcuts the verification process.

Picking the value of l exhibits a trade-off between security and verification costs. On one hand choosing a great l draws the behavior of the diet node closer to that of a full node, while on the other hand choosing a small l draws it closer to that of an SPV node. The user can make her decision based on which block depth l is great enough in her opinion such that all blocks prior to B k-l are unlikely to be counterfeited. For instance, a diet node user can choose l such that the trusted block has a block depth of 6 or greater since it is the de facto standard in Bitcoin to consider blocks of depth 6 or greater as secured 3 .

In the case depicted in Figure 8, assuming l = 2, diet node d downloads block B k-1 to verify the transactions and the UTXO Merkle root in B k-1 to further increase its confidence in B k . To verify B k-1 , the diet node uses the UTXO Merkle root in B k-2 .

Detailed Operation

Equipped with the knowledge of Dietcoin's basic mechanisms, we can now detail the verification process carried out by diet nodes. Algorithm 1 depicts the actions taken by a diet node when its user starts the application using Dietcoin and compares it with those taken by legacy SPV clients. Black dotted lines [•] are specific to diet nodes, while hollow dotted lines [•] are common to both diet and SPV nodes.

The algorithm begins when the application using Dietcoin starts and updates its view of the blockchain. In this first part of the algorithm, a diet node behaves exactly in the same manner as an SPV node. First, it issues a query containing the latest known block hash and an obfuscated representation of its own public keys in the form of a bloom filter (lines 4-5). A full node responds to this query by sending a list of all the block headers that are still unknown to the SPV/diet node, together with the transactions matching the SPV/diet node's bloom filter, and the information from the transaction Merkle tree that is needed to confirm their presence in their blocks. Using this information, the SPV/diet node verifies the received headers (including Proof-of-Work verification) and updates its view of the blockchain (line 6).

Since the response from the full node might contain false positives due to the use of a bloom filter for public key obfuscation, the next verification step consists in ensuring that the received transactions match one of the user's public keys (lines 8-9). Once false positives are discarded, the SPV/diet node verifies that the received transactions are in the blocks (line 10-12).

At this point, a standard SPV node simply returns the received transactions to the application (line 14). A diet node, on the other hand, continues the verification process. To this end, the diet node first computes which blocks to fully verify to ensure that (i) no block is fully verified twice (line 17), (ii) old blocks considered by the user as secured enough are not fully verified (parameter maxDepth p , line 17) and (iii) only a subchain of limited length l is fully verified (parameter maxLength p , line 19). If no block is selected for full verification, the diet node falls back to SPV mode (lines 20-21).

To bootstrap the full verification process, the diet node must first download the UTXO Merkle root present in the block prior to the first block to verify (line 23). For each of the selected blocks B k , the diet node downloads from Dietcoin-enabled full nodes (i) the block B k itself (line 25), (ii) the state, before B k , of the UTXO shards associated with both the block's transactions' inputs and outputs (line 26), and (iii) the partial UTXO Merkle tree required to prove the integrity of the downloaded shards (line 26).

Once it has all the data, the diet node proceeds with the verification process. For each block B k , it first verifies that the downloaded UTXO shards match the UTXO Merkle root from the previous block B k-1 (lines 27-29). Then it verifies that the transactions in each block use only available inputs from these shards (lines 32-33), and computes the new state of these shards based on the transactions in B k (lines 34, 36). Finally it verifies that the updated shards lead to the UTXO Merkle root contained in B k (lines 37-39). Once the verification process has terminated, the diet node returns the transactions associated with the local user to the application (line 14).

Related work

Making the UTXO set available for queries between nodes has been discussed several times in the Bitcoin community over the past few years. Bryan Bishop published a comprehensive list of such proposals [START_REF] Bryan | bitcoin-dev] Protocol-Level Pruning[END_REF] that share some of the following goals: (i) enabling faster node bootstrap, (ii) strengthening the security guarantees of lightweight nodes, and (iii) scaling the UTXO set to reduce its storage cost. The primary goal of Dietcoin is to strengthen the security of lightweight nodes. Dietcoin's strongest feature is the ability for diet nodes to efficiently perform subchain verification, as described in Section 3.3, which offers stronger security guarantees than the referenced proposals made by the community. Moreover, even though we focus in this report on the security of lightweight nodes, it is also possible to bootstrap full nodes faster with Dietcoin.

Sharing similar goals with Dietcoin, Andrew Miller [START_REF] Miller | Storing UTXOs in a Balanced Merkle Tree (zero-trust nodes with O(1)-storage)[END_REF] suggests to store in blocks the root of a self-balancing Merkle tree built on top of the UTXO set. In such a system, lightweight nodes only download the UTXOs they need, which results in a lower bandwidth consumption than with shards as we propose it, but at the cost of a greater storage overhead since the stored Merkle tree is larger. Moreover, Dietcoin combines a full, and thus always balanced, Merkle tree built on top of 2 k shards that can each be updated in place as blocks are appended to the chain. This combination of tree stability and updatable shards enables efficient subchain verification, as described in Section 3.3, and adapting this feature to a system using a self-balancing Merkle tree does not seem trivial.

Vault [START_REF] Leung | Vault: Fast bootstrapping for cryptocurrencies[END_REF] also proposes to use Merkle trees to securely record the state of the distributed ledger in recent blocks, and shards this state across nodes, to reduce storage costs. Contrarily to Dietcoin, however, Vault targets balance-based schemes, such as introduced by Ethereum, in blockchains relying on Proof-of-Stake consensus. Vault further stores individual accounts in the Merkle trees, rather than UTXO shards as we do. This represents a different and to some extent orthogonal trade-off to that of Dietcoin, in that Vault chooses to increase the size of Merkle tree witnesses that must be included in transactions, but removes the need for lightweight nodes to download UTXO shards.

Whereas we focus on sharding the resulting state of the blockchain, other systems propose to shard the verification process. Both Elastico [START_REF] Luu | A Secure Sharding Protocol For Open Blockchains[END_REF] and OmniLedger [START_REF] Kokoris-Kogias | OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding[END_REF] proposes a permissionless distributed ledger using multiple classical PBFT consensus protocols each executing within a subset (shard) of nodes.

Elastico limits the number of shards a malicious nodes may join (under different identifies) by tying the shard of a node to the result of a Proof-of-Work puzzle. OmniLedger [START_REF] Kokoris-Kogias | OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding[END_REF] extends the ideas proposed by Elastico [START_REF] Luu | A Secure Sharding Protocol For Open Blockchains[END_REF] to increase the size of the shards (and thus reduce the probability of failures), and allow for cross-shards transactions thanks to a Byzantine shard-atomic commit protocol called Atomix. Both Elastico and OmniLedger use sharding to increase the transaction processing power of a distributed ledger, rather than to improve access and verification of the Inria UTXO set, as we do.

Chainiac [START_REF] Nikitin | CHAINIAC: Proactive Software-Update Transparency via Collectively Signed Skipchains and Verified Builds[END_REF] combines the ideas of skiplists and blockchains to realize skipchains, an authenticated log with both back and forward long-distance links to implement a distributed authenticated software-release ledger. Chainiac relies on digital collective signatures to implement forward links, which are not available in permissionless Proof-of-Work chains such as Bitcoin. Long distance links are particularly well adapted to navigate a well-identified subset of a blockchain (such as a package's releases). They were not however directly designed to handle the kind of dependencies captured by the UTXO model.

An entirely different approach to scaling blockchains for lightweight nodes is the use of Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) [START_REF] Kiayias | Non-interactive proofs of proof-of-work[END_REF] that enable constant size queries. NIPoPoWs strive for minimal cost of proof of inclusion of a transaction in a chain, thus reducing to a minimum the bandwidth requirements of lightweight nodes. NIPoPoWs however do not aim at offering improved security for lightweight nodes as we do with Dietcoin.

Conclusion

In this report, we have presented the design of Dietcoin, that proposes a new form of Bitcoin nodes that strengthens the security guarantees of lightweight SPV nodes by bringing them closer to those of full Bitcoin nodes. The Dietcoin protocol enables low-resource nodes to verify the transactions contained in blocks without constructing a full-fledged UTXO set. In our protocol, diet nodes download from full nodes parts of the UTXO set they need in order to verify a block, or a subchain of blocks, of interest. Diet nodes are able to detect any tampering of the UTXO set itself, at a cost that remains affordable for low-resource devices, both in terms of communication and computing overhead. In our approach, Dietcoin-enabled full nodes split their UTXO set into small shards, and enable diet nodes to download only the shards that are relevant to the transactions in the block, while verifying that these shards do indeed corresponds to the state of the UTXO set for the block they are verifying.

2 . 3 9 3

 239 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Recording a new transaction . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.2 Irrevocability of deep blocks . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Transactions, Blocks, and UTXO set . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Checking block validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 The set of Unspent TransaCTion Outputs (UTXO set) . . . . . . . . . . . 9 The limitations of SPV nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Dietcoin system 10 3.1 Sharding the UTXO set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Linking blocks with the UTXO set . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 Extended verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Detailed Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Figure 1 :

 1 Figure 1: Both the Bitcoin blockchain and the UTXO set have almost tripled in size in the past two years.

Inria

2 B 0 B 1 B 2 BobFigure 2 :

 20122 Figure 2: A blockchain is formed of a sequence of blocks containing transactions. The current state of the blockchain (here (B 0 , B 1 , B 2 )) is stored by each individual miner.

Figure 3 :

 3 Figure 3: To add a new transaction to the current blockchain, a miner first verifies the validity of the transaction. It must then solve a costly cryptopuzzle to encapsulate this transaction in a new block (here B 3 ), before disseminating this block to other miners.

Figure 4 :

 4 Figure 4: Revoking the content of a block B n-k deep in the chain requires constructing a better alternative subchain, which becomes exponentially harder as the block lies deeper.

  hash(B k-1 .header) merkle_h(B k .transac1ons)

tx 2 BFigure 5 :

 25 Figure 5: Content of a block header (simplified).

Figure 6 :

 6 Figure 6: Example of a Merkle tree root reconstruction that only needs log(n) hashes.

Figure 7 :

 7 Figure 7: Structure of a transaction.

Figure 8 :

 8 Figure8: The UTXO set is updated every time a block is validated. For a counterfeited block to be validated by diet nodes, a malicious node has to forge at least two consecutive blocks: the first block B k-1 containing a fake Merkle root of UTXO k-1 , and the second block B k spending fake coins validated by the fake UTXO k-1 .

RR n°9162

Bitcoin uses a scripting language to encode challenges and proofs of ownership, enabling for more complex schemes, but for ease of exposition we limit ourselves to the typical case.Inria

Acknowledgments

This work has been partially funded by the Region of Brittany, France, by the Doctoral school of the University of Brittany Loire (UBL), by the French National Research Agency (ANR) project SocioPlug under contract ANR-13-INFR-0003 (http://socioplug.univ-nantes.fr) and by the SIDN Fonds contract 172027.

bloomFilter(keys)

Compute a bloom filter from keys buildMRoot(hashes)

Compute the Merkle root from hashes getShardKey(txId)

Apply the sharding algorithm to txId height(header) Index of header starting from the genesis block updateMTreeInPlace(MTree, dataset) Update the hashes of MTree with the new value of dataset verifyHeaders(headers)

Add headers to the chain, return the hash of the new chain tip filter ← bloomFilter(pubKeys p )

•5:

({header, txMTree, txs}) ← send queryMerkleBlocks(tipId p , filter)

•6:

tipId p ← verifyHeaders((header))

•7:

for all {header, txMTree, txs} ∈ ({header, txMTree, txs}) do

if ∀k ∈ pubKeys p : k / ∈ {tx.inputs ∪ tx.outputs} then

continue Ignore bloom filter false positives

•10:

assert(∀tx ∈ txs : HASH(tx) ∈ txMTree)

•11:

builtTxMRoot ← buildMRoot(txMTree)

•12:

assert(builtTxMRoot = header.txMRoot)

•13:

verifyBlocksUpTo(height(header))

•14:

callback(txs, header) Callback to app

•15: procedure verifyBlocksUpTo(last)

•16:

Do not verify blocks twice or below maxDepth p

•17:

first ← max(highestVerified p , height(tipId p ) -maxDepth p )

•18:

Verify up to maxLength p blocks

•19:

first ← max(first, last -maxLength p )

•20:

if first ≥ last then The first UTXO Merkle root is not verified

utxoMRoot ← send queryUtxoMRoot(HASH(headerStorep[first]))

•24:

for all blockId of height ∈ [first + 1, last] do

•25:

block ← send queryBlock(blockId)

•26:

{shards, utxoMTree} ← send queryUtxos(blockId)

•27:

assert(∀shard ∈ shards : HASH(shard) ∈ utxoMTree)

•28:

builtUtxoMRoot ← buildMRoot(utxoMTree)

•29:

assert(builtUtxoMRoot = utxoMRoot)

•30:

for all tx ∈ block.transactions do

for all i ∈ tx.inputs do

•32:

shard ← shards[getShardKey(i)]

•33:

assert(i ∈ shard ∧ valid proof of ownership of i)

•34:

shard.remove(i) utxoMTree ← updateMTreeInPlace(utxoMTree, shards)

•38:

utxoMRoot ← buildMRoot(utxoMTree)

•39:

assert(utxoMRoot = block.utxoMRoot)


Farouk Belkadi

Ravi Kumar Gupta

Ekaterini Vlachou

Alain Bernard

Dimitris Mourtis

Linking modular product structure to suppliers' selection through PLM approach: A Frugal innovation perspective

Keywords: PLM, co-evolution, Modular, Supplier selection, frugal innovation

To maintain market share rates, frugal innovation is a main solution for competitive enterprises to meet the customer's needs in different regional markets. The co-evolution of product and production network aims to manage local production sites of the OEM and several collaborative relations between OEM and supplier companies for better management of the project resources in the regional market. Supplier selection and evaluation are among the main factors to be resolved at the earlier stage to guarantee successful results from any OEM-Supplier collaboration. This paper discusses the potential of using a modular-based approach as a kernel methodology to support the co-evolution of product structure and production network definition, especially in the case of supplier selection for frugal innovation perspective. The application of PLM approach to manage interconnected data describing the co-evolution of the product structure and production network is also discussed.

Introduction

In context of hard competitiveness and economic pressures, companies need to reach new markets (i.e. both emerging and mature market) by further sharpening their strategic focus on what customers really need. For this, frugal innovation theory is introduced to explain new market trends and to propose new solutions supporting these evolutions [START_REF] Zeschky | Frugal Innovation in Emerging markets: The case of Mettler Toledo[END_REF]. For Tiwari and Herstatt [START_REF] Tiwari | Frugal Innovation: A Global Networks' Perspective[END_REF], frugal innovation refers to innovative products and services that "seek to minimize the use of material and financial resources in the complete value chain (from development to disposal) with the objective of reducing the cost of ownership while fulfilling or even exceeding certain pre-defined criteria of acceptable quality standards".

This theory results new category of products named "frugal" as an aggregation of the following attributes: Functional to answer the exact customer need by focusing on key product features; Robust with integration of recent technologies and facilities of maintenance high life duration; User-friendly through a simple and easy to use functions and interfaces; Growing through large production volumes enabling economies of scale; Affordable by offering to customer good "value for his money" through adaptable prices according to their socio-economic context; and Local to propose products mainly tailored to local requirements but also built using some production facilities (i.e. suppliers) and components from the targeted market [START_REF] Berger | Frugal Products: Study Results[END_REF].

To develop such kind of products, companies should adopt a customer-driven design process and an optimal co-evolution of the production strategy to reduce manufacturing and logistic costs, taking in consideration the capabilities, constraints and resources available in the targeted market. The design strategy respecting frugal attributes can be conducted through a set of following design actions:

• Design new specific modules or modifying the features of existing ones, • Reuse existing solutions developed by the company in previous projects,

• Use standard modules developed by external suppliers for several products.

The co-evolution of the production network to support the adaptation of an existing product to a new market implies new changes on the production process or on suppliers to cope with new modification in the product structure (it can be the change of one module or modification of some module features). In parallel, the modification of the product structure can be a consequence of using a new module (or technology) proposed by a supplier in the local market which results in the co-evolution of the product structure with the production strategy [START_REF] Arndt | Customer-driven Planning and Control of Global Production Networks -Balancing Standardisation and Regionalisation[END_REF]. The big challenge is then to have an efficient collaboration between the OEM company and all its suppliers.

The co-evolution of the production system should be extended to the production network level that aims to create several collaborative relations between the OEM (Original Equipment Manufacturer) and suppliers' companies for better management of their distinctive skills and resources in the whole production process [START_REF] Hochdörffer | Evaluation of global manufacturing networks -a matter of perspective[END_REF]. Thus, Supplier selection and evaluation are among the main factors to be resolved at the earlier stage to guarantee successful results from any OEM-Supplier collaboration [START_REF] Cheraghi | Critical Success Factors for Supplier Selection: An Update[END_REF].

As per our study, an emerging market's needs can be solved by adapting an existing product and production which are well stablished in westerned and European markets to fulfil regional customer's requirements (new market) especially when the customer belongs to emerging markets (e.g. India, Africa and China). This adaptation of the existing product to emerging market is researched using frugal innovation. Few companies adopted the frugal innovation for the above aspects, but took long time to launch their product in the markets.

The research in ProRegio [7] is to fill these gaps. One part in this research is suppliers' selection respecting the requirements from regional markets and also company's policies.

In this context, this paper discusses the potential of using a modular-based approach as a kernel methodology to support the co-evolution of product structure and production network definition, especially in the case of supplier selection in context of frugal innovation. This approach is mainly suitable for design strategies based on the use of standard modules or the reuse of existing solutions (with possible adaptation). A smart algorithm is used to generate and evaluate the alternative supplier networks.

2 PLM approach for supplier selection

Frugal innovation and suppliers' selection

With respect to the frugal innovation principle, the global modular-based approach should handle the easier interpretation of customer requirements and the identification of only concerned modules to be considered for the customization process [START_REF] Du | Product Families for Mass Customization: Understanding the Architecture[END_REF][START_REF] Mourtzis | The evolution of manufacturing systems: From craftsmanship to the era of customization. Design and Management of Lean Production Systems[END_REF].

The concept of module represents a physical or conceptual grouping of product components to form a consistent unit that can be easily identified and replaced in one product architecture in order to increase product variety and flexible adaptability [START_REF] Jiao | Product Family Design and Platform-based Product Development: State-of-the-art Review[END_REF].

In the proposed frugal innovation process (Figure 1), the designer can propose several alternatives of product modules with specific features to cope with a set of customer requirements. These features concern technical characteristics used for the engineering perspective as well as useful inputs for building the related production network. Each module is identified with all possible production capabilities or suppliers able to provide it with the desired characteristics. The selection of the best alternatives of production systems or suppliers is fulfilled by taking in consideration of different facilities and constraints in the local market to build the global production network. Then the selection of the best module solutions can be obtained as a consequence of selecting the related production systems or suppliers.

Fig 1.

Co-definition of product structure and production network

Production system refers to technological elements (machines and tools), organizational behavior and managing resources within OEM whereas supplier refers to external supplier of product modules and related supports. A supplier can be local or international based on local requirements and product modules characteristics. By fixing the different production systems and suppliers (for final assembly and for the production of modules), the structure of the production network is defined as a combination of the selected items. The expected behavior of the network is obtained by the definition of the global planning and all collaborative processes supporting information and material exchange among these production systems and suppliers. Thus, the assembly process of the whole product structure is obtained according to the global production planning at network level.

Several collaborative relations between the OEM and suppliers are identified in the literature based on the level of integration of the supplier in the final project of the OEM [START_REF] Calvi | How to manage early supplier involvement (ESI) into the new product development process (NPDP): Several lessons from a French study[END_REF]. At the low levels, suppliers are assimilated to simple executors of detailed specifications from the OEM. In more collaboration level, the supplier is more involved in the development project and participates to the definition of the product architecture (1 st rank suppliers).

This nature of collaboration can provide serious advantages for the deployment of frugal innovation strategy in new markets. In this case the OEM will exploit some interesting and innovative solutions proposed by suppliers to design new frugal product or to adapt an existing one to one specific market. By this, the development process will follow a concurrent path in which the selection of the best product modules can be obtained from the identification of the best suppliers respecting the frugal requirements. Supplier selection strategy contributes principally to the improvement of "Robust", ""Affordable" and "Local" attributes since it gives the possibility to the company to: use new solution that can enhance the product quality respecting the target market standard, moderate the cost by selling from competitive suppliers, especially when those ones are coming from the target market.

The concept of product module can be used to connect the product structure to different outputs of the suppliers involved in the related production network. Thus, using product module features combined with additional information from the final assembly process planning and logistic constraints in the local market can give interesting requirements for the evaluation of KPIs (Key performance indicators) useful to get an impartial assessment of potential suppliers' capacities before considering them in the production network.

The mapping of product module features (from product configuration view) to KPIs (suppliers selection view) is presented in Figure 2. The product modules are the products of the suppliers. The decision making for supplier selection and product module selection is based on the mapping between requirements (product module features) and real values of KPIs for the suppliers and their products. Global PLM approach for supplier selection

The role of mapping is to classify all available suppliers according to the matching level between their KPI values (representing real assessment) and product features (representing requirements). Some time, when there are limited possibilities of suppliers to cover the requested module, the mapping table can be used to adapt, if necessary, some product features according to the capacities of the related supplier.

The PLM approach can support the concurrent design process of frugal products and the supplier network through a smart management of product modules and related suppliers alternatives for several product configurations addressed to various markets. This is ensured through an optimal integration, storage and connection of numerous data coming from several applications, including suppliers' selection tools. Indeed, the implementation of PLM approach results from the integration between heterogeneous IT systems such as ERP (Enterprise Resource Planning), PDM (Product Data Management), SCM (Supply Chain management), etc. [START_REF] Bosch-Mauchand | Knowledge based assessment of manufacturing process performance: integration of product lifecycle management and value chain simulation approaches[END_REF].

In the proposal, the supplier selection process is achieved based on several data stored on different business tools. This data is identified and managed in the PLM system as specific features connected to different product modules alternatives. Each module is analyzed to generate supplying requirements. The final decision is the identification of optimal "Modules-Suppliers" combination as fragment co-definition of best product structure and supplier network with respect to frugal attributes.

Product features for supplier selection

To illustrate the proposed principle of solution for the use of modularity for supplier selection problem, an example of concurrent design process of frugal product and identification of possible suppliers for each module is presented in Figure 3. This scenario deals with the case of adapting existing product architecture to a new market based on the capabilities of existing suppliers in the targeted market. Supplier selection strategy based on global modular product design approach

The process starts by the analysis of new market requirements (including specific customer requirements) and then search for existing product structures covering these needs. The analysis of modules functions and features as requirements is used to generate list of possible suppliers. The list of suppliers' alternatives will provide list of possible module alternatives matching with the same functions of the originally design product. Then several alternatives of product structures from the original one (developed in older projects) can be obtained as combination of the product modules proposed by the selected suppliers.

The performance assessment of each alternative will help to fix the best product structure and consequently the best product modules replacing the original ones. In final the list of supplier is fixed as those providing the selected modules.

To perform these decision making processes, additional categories of information should be embedded in the product module concept. The definition of product module through features is to connect different views of the product design and development.

Product module features are defined to translate the regional customer requirements to product design and connect the product design to production planning and supplier network design. The product modules' features are defined to address three categories objectives as inputs for frugal decision making problems regarding the objectives of the global modular product design approach:

• Analyzing customer/market requirements and linking product modules to requested functions in specific product architecture. • Defining modules' parameters and its interfaces to support the design of new product (and related alternatives) as a consistent combination of product modules. • Responding to production strategy (production system and network definition) through a consistent connection of modules to optimal production capabilities.

These three categories of features are used to identify requirements for supplying properties and production planning as well as to refine the selection of product module. From these categories of features, the following Table 1 includes the list of relevant features that should be used as requirements for supplier selection process.

Table 1. List of modules features for supplier selection process

Feature Description

Performance Acceptable standardization and tolerance level for product module performance values, regarding the global product performance. Interfacing Capacity to one module to be interfaced with other ones Interchangeability Capacity for one module to be replaced by one or more other modules from other suppliers but providing similar functions.

Customization

Requested possibility to change some proprieties of the module and level of options proposed in the supplied module. Process position

Connection of the module to different steps of the final assembly process and the level of dependency with the connected modules

Criticality

The importance of the related function regarding its added value to the final product structure. Supplying tolerance Level of request on the supplier in terms of cost, delivery time and confidence level as a consequence of the previous modules' features. Figure 4 illustrates an example of using product module features (green color rectangle) to analyze product life cycle and generate additional Supplying Tolerance Features (inner blue color rectangle), to be considered as requirements for decision criteria for the selection of best suppliers for frugal innovation issue. These supplying decision criteria and/or related KIPs can be used for production network design.

Through the application of the concurrent design of product structure and suppliers' network, conflict can appear from contradictions on results based on analysis of product module features on one side and supplying requirements on the other side, for example a module can have high performance but real risk on delivery time regarding the supplier capacities, especially if the module is requested earlier in the production process. This will imply important delays on the final assembly process of the product. Affordable and growing attributes are seriously affected. Product module features as requirements for supplying decision criteria Figure 5 illustrates such kind of conflicts between product modules "as designed" (inner blue color rectangle) and real modules "as produced by suppliers" (inner green color rectangle). It is shown that the product module "PM1" has product module feature "Criticality" value as "High". PM1.1 is the "Best" implementation and PM1.2 is the "Worst" one according to the related suppliers KPIs. However, PM1.1 presents a low level of interfacing with the PM 2.1 that is the only possible implementation of PM2. The conflict is that if the best product module with high criticality (PM1.1) is selected then supplying of other product module (PM2) is not possible. There are two possibilities to resolve this type of situations either (i) Select the modules to be supplied as per the requested module features and redesign (or reselect new supplier) the product modules which are not possible to be supplied by any existing supplier, or (ii) Relax features' values for the conflicted product module in the requested product. Thus, product module features and KPIs for production network design should be connected together through the PLM approach to evaluate all possible combinations of product-suppliers in the production network. Conflicts possibilities on the co-definition of product structure and supplier network

This connection provides real positive impacts on the frugal attributes. For instance, deciding optimal supplier based not only on its own properties but also on the criticality of the related modules allows managers adapting the balance between product cost and quality by favoring reputable suppliers for the critical modules (high function criticality requesting high quality) even the price is high, and obtaining the less critical modules (less added value for the target market) from low cost suppliers.

Supplier selection and network design method

The supplier selection and network design method should be capable of generating alternative combinations of product-suppliers and evaluate their performance based on multiple and conflicting criteria based on the constrains-suggestions provided by the design during the generation of the different product structures. One of the main challenges during the supplier's selection and the supplier networks design is to select the optimum supplier based on their suitability and their availability. Therefore, the proposed work proposes a smart search algorithm capable of subset of total number of alternative manufacturing network configurations by utilizing three adjustable parameters [START_REF] Chryssolouris | Manufacturing Systems: Theory and Practice[END_REF]. The three control parameters that are utilized are the maximum number of alternatives (MNA) which controls the breadth of the search, the decision horizon (DH) which controls the depth of the search, and the sampling rate (SR) which guides the search towards the high quality branches of the tree of alternatives [START_REF] Mourtzis | A Multi-Criteria Evaluation of Centralized and Decentralized Production Networks in a Highly Customer-Driven Environment[END_REF]. The optimum values of these factors will be obtained through a statistical Design of Experiments (SDoE) [START_REF] Phadke | Quality Engineering Using Robust Design[END_REF].

The main inputs of the proposed algorithm are the various product features generated by the product configuration and the pre-filtered list of suppliers based on their compatibility and their suitability, as well the bill of processes to produce the product modules and in general the final product. The decision-making procedure following by the supplier selection and networks design algorithm is based on resource-task assignment decisions. Considering that, in order to produce a part/module of the product a task should be performed by a resource and the resource belongs to a plant or to a supplier. In case of suppliers the task is directly connected with the supplier.

The main steps of the proposed algorithm the formalization of the alternatives, the criteria determination to satisfy the objectives, the definition of the criteria weights, the calculation of the criteria values and last is the selection of the optimum alternative based on their performance (Figure . 6) [START_REF] Mourtzis | A Multi-Criteria Evaluation of Centralized and Decentralized Production Networks in a Highly Customer-Driven Environment[END_REF][START_REF] Mourtzis | Design and Operation of Manufacturing Networks for Mass Customisation[END_REF].

Multiple and conflicting criteria are considered and are calculated by the smart search algorithm and during the decision making procedure. Production and Transportation Cost, Quality, Lead time, total Energy Consumption, CO2 emissions are among the main criteria considered [START_REF] Mourtzis | F A Toolbox for the Design, Planning and Operation of Manufacturing Networks in a Mass Customisation Environment[END_REF]. To address the need of frugal innovation in the context of the supplier's selection method also the locality of the suppliers is considered as main criterion. Locality shows how close to the targeted market is the supplier. This will contribute to enhance the affordable and local attributes by reducing logistics costs and using existing standards in the target market since the providers are coming from the same market. Moreover, through the consideration of Locality, as criterion, local suppliers can be considered, increasing the market share of local markets.

The total network performance is calculated by measuring defined KPIs. In that stage, also the suggested KPIs, from the product configuration stage, are considered. The final results of the selected network are sending back to the PLM tool in order to fix the different modules of the product and finalize the design of the product. constraints and resources. Global modular approach has been used to support the design and development of frugal product. The application of module concept for frugal innovation perspectives showed the need to re-think the definition of the product model and its integration in future generation of PLM systems. New features should be considered to represent requirements of production from frugal product side and to connect product design to production and supplying strategies Considering product features as decision criteria for supplier selection strategy will contribute to enhance the product frugal attributes, especially affordable, robust and local attributes. This is given through an optimal balance between cost, quality and delivery time requests, assessed separately for each product module according to its criticality in the target market, impact on the global performance and implication on the final assembly process. The logic is that for critical modules, strong trust on suppliers' performance is required. Less important modules or with high interchangeability allow more flexibility on the selection strategy for cost reduction.

The proposed methodology can provide a great advantage to companies that are moving towards frugal innovation concept by providing local, low-cost and affordable products taking into account local customer's requirements. Moreover, through the consideration of Locality, as criterion, during the proposed supplier's selection and networks design tool, local suppliers can be considered, increasing the market share of local markets.

This paper focuses on the conceptual solution instead of presenting the final implementation for industrial use case which is under development. The developed methodology is well appreciated by industrial partners as well as academic partners.

  Fig 2.Global PLM approach for supplier selection

  Fig 3.Supplier selection strategy based on global modular product design approach

  Fig 4.Product module features as requirements for supplying decision criteria

  Fig 5.Conflicts possibilities on the co-definition of product structure and supplier network

Fig 6 .

 6 Fig 6.Supplier selection and network design Algorithm-Smart search algorithm

Acknowledgments. The presented results were conducted within the project "ProRegio" entitled "customer-driven design of product-services and production networks to adapt to regional market requirements". This project has received funding from the European Union's Horizon 2020 program under grant agreement no. 636966. The authors would like thank the industrial partners involved in this research.


come

Atomic layer deposition of boron nitride


Cécile Tannier

About fractal models in urban geography and planning: refuting the aesthetics and the universal norm

Fractal models have been used in urban geography for forty years. Their main applications were for analyzing urban forms but they were also used to simulate urban growth. Research in the field has significantly contributed to better characterise the local and global shape of cities and to better understand their evolutions. Yet concomitantly, one can deplore the circulation of some myths about the interpretation of fractal analysis results and about the possible usage of fractal models for urban analysis and planning. I propose here to undermine some of these myths on the basis on some scientific publications in the field1.

Cities are not fractal.

Indeed, measures of fractal dimensions vary in space: the fractal dimension estimated for a whole city differs from the fractal dimension estimated for its neighbourhoods, each having its own dimension (see e.g. [START_REF] Thomas | Comparing the fractality of European urban neighbourhoods: do national contexts matter[END_REF]). Moreover, considering a given built pattern, the slope of the curve that represents the number of counted elements with respect to the size of the counting window may exhibit local variations (Frankhauser 1998[START_REF] Frankhauser | Comparing the morphology of urban patterns in Europe. A fractal approach[END_REF][START_REF] Tannier | Fractals in Urban Geography: A Theoretical Outline and an Empirical Example[END_REF][START_REF] Thomas | Clustering patterns of urban built-up areas with curves of fractal scaling behaviour[END_REF]. Very early on, pioneer works in geography have insisted on the fact that the fractal dimension is not expected to be constant in reality [START_REF] Goodchild | Fractals and the Accuracy of Geographical Measures[END_REF]; most often, it is constant over a limited range of scales but varies somewhat over successive ranges of scales [START_REF] Lam | On the Issues of Scale, Resolution, and Fractal Analysis in the Mapping Sciences[END_REF][START_REF] White | Urban Systems Dynamics and Cellular Automata: Fractal Structures between Order and Chaos[END_REF].

Consequently, properties of scale-invariance and statistical self-similarity are locally specific but not universal, and concern limited scale ranges. Thus, by definition, cities are not fractal.

Nevertheless, measures of fractal dimension are interesting for geographers as they enable the characterisation of spatial distributions being highly heterogeneous. Indeed, as fractal dimension is determined via counting the elements of a spatial distribution according to several nested spatial resolutions, it informs us about the systematic variations of a given geographical fact through scales. Such variations are not proportional, not linear, and would not be detected when we use other spatial concentration indexes such as density [START_REF] François | Villes, densité et fractalité. Nouvelles représentations de la répartition de la population[END_REF]. In practice with fractal analysis, the starting point is to set the hypothesis that a spatial distribution is scale-invariant (or statistically self-similar). Then deviations to scale-invariance are studied. Such deviations may appear for some scale ranges but not others. Deviations may also vary in space, which allows the identification of spatial differentiations.

2. Evolution of the shape of cities does not comply with a unique model that would finally end in a fractal order state.

For P. [START_REF] Frankhauser | Comparing the morphology of urban patterns in Europe. A fractal approach[END_REF] and N. [START_REF] Salingaros | A universal rule for the distribution of sizes[END_REF], the emergence of fractal urban patterns originates in the combination of two types of processes:

 bottom-up processes resulting from individual actions (for instance, the choice of households to become owner of an individual house in a suburban area) or from collective actions (for instance, actions of local pressure groups according to the Nimby (Not In My Backyard) logic);  top-down processes (i. e. urban and regional planning). For F. [START_REF] Schweitzer | Analysis and Computer Simulation of Urban Cluster Distributions[END_REF], fractal urban patterns emerge from the interaction of contradictory actions at an individual level only, i. e. residential location choices that minimize the distance to both the city centre and the urban boundary (countryside).

Underlying those assumptions is the idea of self-organisation. In a self-organised system, a meso-or macroscopic order emerges from interactions at a microscopic level and constraints in return the future evolutions of the system2. Accordingly, F. [START_REF] Schweitzer | Analysis and Computer Simulation of Urban Cluster Distributions[END_REF] have set the hypothesis that the rank-size distribution of urban built clusters changes in the course of time toward becoming a Pareto distribution. If this hypothesis is confirmed, the conclusion would be that a Pareto exponent indicates the development stage of a city and that the deviations from a Pareto distribution indicates potentials for future urban developments. Yet some empirical research results have infirmed this hypothesis. In particular, L. [START_REF] Benguigui | The Dynamics of the Tel Aviv Morphology[END_REF] have shown that the rank-size distribution of built clusters of the city of Tel Aviv (Israel) followed a Zipf's law from 1935 to 1964 then gradually deviated from it between 1974 and 2000.

Several scholars have also studied the evolution of fractal dimensions of cities in the course of time. Although the comparison of values of fractal dimension obtained for different studies is not possible since the data used and the calculation methods involved are different, we note similar general tendencies. P. [START_REF] Frankhauser | Aspects fractals des structures urbaines[END_REF] calculated an increase of fractal dimension of Berlin (Germany) in the course of time: 1.43 in 1875, 1.54 in 1920, 1.69 in 1945[START_REF] Shen | Fractal Dimension and Fractal Growth of Urbanized Areas[END_REF] calculated an increase of fractal dimension of Baltimore (USA), from 1.015 in 1822 to 1.722 in 1992. An increase of fractal dimension of the built surface has also been shown for the metropolitan area of Basel (Switzerland, France, Germany) between 1882 and 1994 [START_REF] Tannier | Fractals in Urban Geography: A Theoretical Outline and an Empirical Example[END_REF] as well as for the metropolitan area of Lisbon (Portugal) between 1960 and 2004 [START_REF] Encarnação | Fractal cartography of urban areas[END_REF]).

Yet if the evolution of city shapes evolves according to a fractal growth process, their fractal dimension should not change in the course of time, which studies quoted above contradict. An objection can be that these studies consider each city within a spatial extent that is fixed in the course of time and that comprises on the one hand the urban area itself which expands gradually, and on the other hand, its periphery. That's why other studies have considered cities within a study area that expands according to the urbanisation process. For instance, L. Benguigui, D. Czamanski, M. Marinov et J. [START_REF] Benguigui | When and Where Is a City Fractal? Environment and Planning B: Planning and Design[END_REF] have analysed the evolution of Tel Aviv's metropolitan area from 1935 to 1991 taking into account three nested study areas. They have shown that the growth differed for each part of the metropolitan area: the fractal dimension increased at different speed in each part of the metropolitan area; some parts have become "fractal" (i. e. statistically self-similar for a given scale range) earlier than others; and the whole metropolitan area has become "fractal" until the mid 80s.

The fact is that a city does not evolve for centuries according to a fractal growth process that would be unique and that would go on until the achievement of a final "maturity" stage of the urban form. First, rules that determine the location and the shape of new urban developments change in the course of time. Second, the urban sprawl process results in the gradual integration of peripheral built areas (villages, hamlets, diffuse suburban settlements/buildings) within the inner city. Third, an urban built pattern can be deeply modified through destruction and reconstruction (for instance, the re-shaping of Paris during the 19th century, the reconstruction of cities after massive destructions resulting from bombing or natural disasters, or the massive destructions of old built neighbourhoods and the construction of large buildings and skyscrapers in contemporary Chinese cities). Last, we can observe creations ex nihilo of new towns in the periphery of large cities.

3. Nothing proves that fractal urban forms are optimal by nature.

Starting from the statement that a fractal order can emerge at a meso-or macroscopic level from self-organising processes, fractality is sometimes seen as a desirable equilibrium state. « Multifractality represents optimal structure of human geographical systems because a fractal object can occupy its space in the most efficient way. Using the ideas from multifractals to design or plan urban and rural terrain systems, we can make the best of human geographical space » (Chen 2016)3. Thus, if self-organised fractal forms are satisfying (even optimal), urban planning becomes useless (and even annoying) because top-down constraints may engender deviations from fractality (Genre-Grandpierre 2017). Subsequently, deviations from fractality can be seen as signs of dysfunction. For Y. [START_REF] Chen | Multifractal Characterization of Urban Form and Growth: The Case of Beijing[END_REF], for instance, deviations from a multifractal structure of Beijing's urban area denote its decline and the degeneration of the inner city. Yet we have previously seen that shapes of cities and urban built patterns are not fractal. Nonetheless they are not all in decline neither are they all degenerated.

Adopting an organicist point of view, other scholars support the idea that urban planning and design should aim at the creation of fractal forms because such forms exist in nature (in which they spontaneously emerge) and thus are "by nature" virtuous and optimal. Fractals are then raised to a universal aesthetic principle, see e. g. [START_REF] Jiang | A New Kind of Beauty Out of the Underlying Scaling of Geographic Space[END_REF]. Besides the fact that such a principle falls under belief more than science, its adoption leads most often to give more importance to emerging forms than to their generative mechanisms. Resulting models are essentially structural: they take into account neither the real behaviours of individuals (as a result of a combination of aspirations, constraints and available means) nor the strong emergence that characterizes social systems4.

The fact is that functional advantages of realistic fractal urban developments (starting from an existing urban pattern) with respect to non fractal developments are still poorly known because they have rarely been studied until now. However, a shape is not intrinsically optimal: it is optimal only with regards to the processes (i. e. behaviours, practices) that this shape allows to optimise. Moreover, the absolute does not exist in the case of spatial distributions of human settlements because of the diversity of contexts (social, political, economic, natural, etc.) from which results a high diversity of human spatial behaviours and practices.

The "good" fractal dimension for urban planning does not exist.

A same value of fractal dimension can characterise very different urban shapes and can result from generative processes being qualitatively and quantitatively very different [START_REF] Pumain | Commentaire sur le chapitre 3 -Les fractales doivent-elles guider l'aménagement urbain ? In G. Dupuy (dir) Villes, réseaux et transport. Le défi fractal[END_REF]. As a

Most ideas exposed in this blog post are taken from the dissertation entitled "Analysis and simulation of the concentration and the dispersion of human settlements from local to regional scale. Multi-scale and trans-scale models" [In French], chap. 3 "Variation de la concentration et de la dispersion des implantations humaines à travers les échelles : modèles mono-et multi-fractals", pp. 114-175, C.[START_REF] Tannier | Analyse et simulation de la concentration et de la dispersion des implantations humaines -Modèles multi-échelles et trans-échelles[END_REF]. https://tel.archivesouvertes.fr/tel-01668615v1

Additionally, scholars commonly introduce in self-organising models a limiting factor that often corresponds to a maximum city size, which can not be overcome[START_REF] Schweitzer | Analysis and Computer Simulation of Urban Cluster Distributions[END_REF], or to a maximum urbanisation rate[START_REF] Chen | Defining urban and rural regions by multifractal spectrums of urbanization[END_REF].

Y.[START_REF] Chen | Defining urban and rural regions by multifractal spectrums of urbanization[END_REF] goes further as he suggests that the urbanisation process should ideally stop at the stage at which the urbanisation rate L equals 0.618 and the urban-rural ratio (called "golden ratio" in the quoted paper) equals 1.618.

It is possible to distinguish weak emergence, where the macroscopic structures resulting from microscopic behaviours can be observed by an external observer identifying a particular regularity in the observed process, from strong emergence, where the microscopic entities observe themselves the macroscopic structures they have produced and adapt their behaviours accordingly[START_REF] Livet | Ontology, as a mediator for agent-based modeling in social science[END_REF]. Social systems are characterised by a strong emergence: through their membership to a social group or to a place, individuals participate in the creation of collective references that refer to this group or place (weak emergence). In return, the adoption (or not) of these collective references by the group or the individual influences its behaviour (strong emergence).