Romain Beauxis
email: beauxis@lix.polytechnique.fr

Konstantinos Chatzikokolakis

Catuscia Palamidessi
email: catuscia@lix.polytechnique.fr

Prakash Panangaden
email: prakash@cs.mcgill.ca

Formal Approaches to Information-Hiding (Tutorial)

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

During the last decade, internet activities have become an important part of many people's lives. As the number of these activities increases, there is a growing amount of personal information about the users that is stored in electronic form and that is usually transferred using public electronic means. This makes it feasible and often easy to collect, transfer and process a huge amount of information about a person. As a consequence, the need for mechanisms to protect such information is compelling.

A recent example of such privacy concerns are the so-called "biometric" passports. These passports, used by many countries and required by all visa waiver travelers to the United States, include a RFID chip containing information about the passport's owner. These chips can be read wirelessly without any contact with the passport and without the owner even knowing that his passport is being read. It is clear that such devices need protection mechanisms to ensure that the contained information will not be revealed to any non-authorized person.

In general, privacy can be defined as the ability of users to stop information about themselves from becoming known to people other than those they choose to give the information to. We can further categorize privacy properties based on the nature of the hidden information. Data protection usually refers to confidential data like the credit card number. Anonymity, on the other hand, concerns the identity of the user who performed a certain action. Unlinkability refers to the link between the information and the user, and unobservability regards the actions of a user.

Information-hiding protocols aim at ensuring a privacy property during an electronic transaction. For example, the voting protocol Foo 92 ( [START_REF] Fujioka | A practical secret voting scheme for large scale elections[END_REF]) allows a user to cast a vote without revealing the link between the voter and the vote. The anonymity protocol Crowds ( [START_REF] Reiter | Crowds: anonymity for Web transactions[END_REF]) allows a user to send a message on a public network without revealing the identity of the sender.

Several anonymity protocols use randomized primitives to obtain the obfuscation of the information to be protected. This is the case, for instance, of the Dining Cryptographers [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], which use coin-flipping, Crowds [START_REF] Reiter | Crowds: anonymity for Web transactions[END_REF] and Onion Routing [START_REF] Syverson | Anonymous connections and onion routing[END_REF], which select randomly another user of the network to forward the message to, and Freenet [START_REF] Clarke | Freenet: A distributed anonymous information storage and retrieval system[END_REF]. In this survey, we restrict our attention to the case in which the use of randomization is critical to achieve the intended security properties.

The possibilistic approaches

These are by far the approaches which have been explored the most in literature. Various formal definitions and frameworks for analyzing information-hiding have been developed. Some examples of these approaches are those based on epistemic logic ( [START_REF] Syverson | Group principals and the formalization of anonymity[END_REF][START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF]), on "function views" ( [START_REF] Hughes | Information hiding, anonymity and privacy: a modular approach[END_REF]), and on process-calculi ( [START_REF] Schneider | CSP and anonymity[END_REF][START_REF] Ryan | Modelling and Analysis of Security Protocols[END_REF]). Here we focus on the last kind of approach.

Often possibilistic approaches rely on nondeterminism: a protocol provides protection if the set of possible observable outcomes is saturated with respect to the secrets. More precisely, if in one computation the instance of the secret to protect is s and the observable outcome is o, then for every other instance s ′ there must be a computation where, with secret s ′ , the observable is still o. Formally:

f -1 (f (P )) ∼ P
where P is the protocol, and f is a relabeling function that maps all the secrets into a dummy, and ∼ is a chosen equivalence relation [START_REF] Schneider | CSP and anonymity[END_REF].

A related approach is the one by [START_REF] Delaune | Verifying properties of electronic voting protocols[END_REF][START_REF] Delaune | Coercion-resistance and receipt-freeness in electronic voting[END_REF], where the authors specify privacy in electronic voting (protection of the secrecy of the vote) as the property that if we swap the way in which two users, A and B, vote, then the resulting system is weakly bisimilar to the original one. Formally:

C[A[a/v]|B[b/v]] ≈ C[A[a/v]|B[b/v]]
where a, b represent the votes of A and B respectively, and the context C[ ] represents the rest of the protocol.

This kind of approach is reasonable, as long as the protocols of interest do not involve the use of randomization. In case they do, then we have a problem, because the pure possibilistic approach is unable to cope with probabilities. So, the choice is either to move to a probabilistic approach, or to try to abstract from probabilities. The second choice is explored in [START_REF] Schneider | CSP and anonymity[END_REF]: In that paper, the authors replace probabilistic choice by nondeterministic choice, and then apply the usual possibilistic definition.

We now illustrate the above idea on the example of the dining cryptographers.

The dining cryptographers' problem

This problem, described by Chaum in [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], involves a situation in which three cryptographers are dining together. At the end of the dinner, each of them is secretly informed by the master whether he should pay the bill or not. So, either the master will pay, or he will ask one of the cryptographers to pay. The cryptographers, or some external observer, would like to find out whether the payer is one of them or the master. However, if the payer is one of them, the cryptographers wish to maintain anonymity over the identity of the payer. Of course, we assume that the master himself will not reveal this information, and also we want the solution to be distributed, i.e. communication can be achieved only via message passing, and there is no central memory or central 'coordinator' which can be used to find out this information.

A possible solution to this problem, described in [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], is the following: Each cryptographer tosses a coin, which is visible to himself and to his neighbor to the right. Each cryptographer then observes the two coins that he can see, and announces agree or disagree. If a cryptographer is not paying, he will announce agree if the two sides are the same and disagree if they are not. However, if he is paying then he will say the opposite. It can be proved that if the number of disagrees is even, then the master is paying; otherwise, one of the cryptographers is paying. Furthermore, if one of the cryptographers is paying, then neither an external observer nor the other two cryptographers can identify, from their individual information, who exactly is paying.

In order to specify formally the protocol, we use a probabilistic version of the πcalculus, π p , which is essentially the π-calculus enriched with a probabilistic choice operator ⊕ p . For a precise definition of the semantics of π p we refer to [START_REF] Chatzikokolakis | A framework for analyzing probabilistic protocols and its application to the partial secrets exchange[END_REF].

The protocol can be described as the parallel composition of the master process Master, the cryptographers processes Crypt i , of the coin processes Coin h , and of a Master = m0 0 . m1 0 . m2 0 ⊕p 1. The dining cryptographers protocol expressed in πp. 2. The nondeterministic version of the dining cryptographers protocol expressed in π.

L 2 0 pim0+i 1 . m1+i 0 . m2+i 0 Crypt i = ci,i(x0) . ci,i+1(x1) . mi(x) . pay i x . outi x0 + x1 + x Coin h = c h-1,h 0 . c h,h 0 ⊕p h c h-1,h 1 . c h,h 1 Collect = out0(y0) . out1(y1) . out2(y2) . outall y0, y1, y2 DC = (ν c)(ν m)(ν out)(Master | Q i Crypt i | Q h Coin h | Collect) Table
Master = m0 0 . m1 0 . m2 0 + P 2 0 pim0+i 1 . m1+i 0 . m2+i 0 Crypt i = ci,i(x0) . ci,i+1(x1) . mi(x) . pay i x . outi x0 + x1 + x Coin h = c h-1,h 0 . c h,h 0 ⊕p h c h-1,h 1 . c h,h 1 Collect = out0(y0) . out1(y1) . out2(y2) . outall y0, y1, y2 DC = (ν c)(ν m)(ν out)(Master | Q i Crypt i | Q h Coin h | Collect) Table
process Collect1 whose purpose is to collect all the declarations of the cryptographers, and output them in the form of a tuple. See Table 1. In this protocol, the secret actions are pay i x , and the observable actions are outall y 0 , y 1 , y 2 .

Nondeterministic version of the dining cryptographers

In the approach of [START_REF] Schneider | CSP and anonymity[END_REF] the dining cryptographers are formalized as a purely nondeterministic system: the coins are approximated by nondeterministic coins, and the choice on who pays the bill is also nondeterministic. The specification of the solution can be given in π-calculus as illustrated in Table 2 (in the original work [START_REF] Schneider | CSP and anonymity[END_REF] the authors used CSP [START_REF] Hoare | Communicating Sequential Processes[END_REF]).

Let f be the function f (pay i ) = pay and f (α) = α for all the other actions. It is possible to check that f -1 (f (DC))) ∼ T DC, where we recall that ∼ T stands for trace equivalence. Hence the nondeterministic notion of anonymity, as defined at the beginning of this section, is satisfied.

As a consequence of approximating the coins by nondeterministic coins, we cannot differentiate between a fair coin and a biased one. However, it is evident that the fairness of the coins is essential to ensure the anonymity property in the system, as illustrated by the following example.

Example 1. Assume that, whenever a cryptographer pays, an external observer obtains almost always one of the three outcomes represented in Figure 2, where a stands for agree and d for disagree. More precisely, assume that these three outcomes appear with a frequency of 33% each, while the missing configuration, d, a, a, appears with a frequency of only 1%. What can the observer deduce? By examining all possible cases, it is easy to see that the coins must be biased, and more precisely, Coin 0 and Coin 1 must produce almost always head, and Coin 2 must produce almost always tail (or viceversa). From this estimation, it is immediate to conclude that, in the first case, the payer is almost for sure Crypt 1 , in the second case Crypt 2 , and in the third case Crypt 0 .

In the situation illustrated in the above example, clearly, the system does not provide anonymity. However the nondeterministic definition of anonymity is still satisfied (and it is satisfied in general, as long as "almost always" is not "always", i.e. the fourth configuration d, a, a also appears, from time to time). The problem is that the nondeterministic definition can only express whether or not it is possible to have a particular outcome, but cannot express whether one outcome is more likely than the other.

The probabilistic approaches

The probabilistic approaches have been investigated in particular in the field of anonymity, and almost exclusively in the strongest form, namely to express the property that the observables reveal no (quantitative) information about the secrets (strong anonymity).

There are essentially three probabilistic notions considered in literature: one based on the equality of the a posteriori probabilities, one based on the equality between the a posteriori probability and the a priori probability, and one based on the equality of the likelyhoods. All of them involve the notion of conditional probability p(a|b), which represents the probability of the event a, given the event b. We recall the equality known as Bayes theorem:

p(a|b) = p(b|a) p(a) p(b)
These probabilistic notions also require that the secrets are mutually exclusive events, and that s p(s) = 1. The same for the observables.

Equality of the a posteriori probabilities The idea is to say that a system is strongly secure if, for any observable o, the a posteriori probability of a secret s (namely p(s|o)) is the same as the a posteriori probability of any other secret s ′ . Formally:

p(s|o) = p(s ′ |o)
for all observables o, and secrets s and s ′

This is similar to the definition of strong anonymity by Halpern and O'Neill [START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF], although their setting is different, being based on a probabilistic version of epistemic logic.

Equality of the a posteriori and a priori probabilities The idea is to say that a system is strongly secure if, for any observable o, the a posteriori probability of a secret s is the same as its a priori one. In other words, the observation does not add anything to the expectation that the secret is s. Formally:

p(s|o) = p(s)
for all observables o, and secrets s

This is the definition of anonymity adopted by Chaum in [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF]. He also proved that the DC satisfies it if the coins are fair. Halpern and O'Neill also consider a similar property in their epistemological setting, and they call it conditional anonymity [START_REF] Halpern | Anonymity and information hiding in multiagent systems[END_REF].

Equality of the likelihoods

The idea is to say that a system is strongly secure if, for any observable o, the likelihood of a secret s given o (namely p(o|s)) is the same as the same as the likelihood of any other secret s ′ . Formally:

p(o|s) = p(o|s ′ )
for all observables o, and secrets s and s ′

This was proposed as definition of strong anonymity by Bhargava and Palamidessi [START_REF] Bhargava | Probabilistic anonymity[END_REF].

Comparison

It is easy to see that definitions Definition (3) has the advantage that it makes clear that depends only on the protocol, not in the distribution on the secrets, and, more important, it does extend in a natural way to the case in which the choice of the secret is done nondeterministically. See [START_REF] Bhargava | Probabilistic anonymity[END_REF] for more details.

Concerning definition (1), it probably looks at a first site the most natural, but it actually turns out to be too strong. that one is strictly stronger than (2) and (3). In fact it is equivalent to (2) and (3), plus the condition that the probability distribution of the secrets is uniform, namely

p(s) = p(s ′ )
for all secrets s and s ′ It is interesting to notice that (4) can be split in two orthogonal properties: one which depends only in the protocol ( (3) ), and one which depends only in the distribution on the secrets ( (4) ).

In our opinion condition (4) is not a suitable condition for defining the notion of protection provided by a protocol, because it only depends on the distribution on the secret data, which can be influenced by the users, but not by the protocol. We believe that a good notion of protection should abstract from such distribution. In this sense we consider (1) too strong.

There are also weaker notions of protection, still based on the comparison between conditional probabilities, which have been investigated in literature. In particular, Rubin and Reiter proposed the concepts of possible innocence and of probable innocence [START_REF] Reiter | Crowds: anonymity for Web transactions[END_REF]. See also [START_REF] Chatzikokolakis | Probable innocence revisited[END_REF] for a generalization of the latter.

The need for formalizing weaker forms of protection comes from the fact that the strong properties discussed above are almost never achieved in practice. Hence the need to express in a quantitative way the degree of protection. Researchers have been exploring for suitable notions within the well-extablished fields of Information Theory and of Statistics.

Information theory

Recently it has been observed that at an abstract level information-hiding protocols can be viewed as channels in the information-theoretic sense. A channel consists of a set of input values S, a set of output values O (the observables) and a transition matrix which gives the conditional probability p(o|s) of producing o as the output when s is the input. In the case of protocols for information hiding, S contains the secret information that we want to protect and O the facts that the attacker can observe.

Let us revise some of the basic concepts of Information Theory: Let X be a random variable. The entropy H(X) of X is defined as

H(X) = - x∈X p(x) log p(x)
The entropy measures the uncertainty of a random variable. It takes its maximum value log |X | when X's distribution is uniform and its minimum value 0 when X is constant. We usually take the logarithm with a base 2 and measure entropy in bits. Roughly speaking, m bits of entropy means that we have 2 m values to choose from, assuming a uniform distribution.

The relative entropy or Kullback-Leibler distance between two probability distributions p, q on the same set X is defined as

D(p q) = x∈X p(x)log p(x) q(x)
It is possible to prove that D(p q) is always non-negative, and it is 0 if and only if p = q. Now let X, Y be random variables. The conditional entropy H(X|Y ) is

H(X|Y ) = - y∈Y p(y) x∈X p(x|y) log p(x|y)
Conditional entropy measures the amount of uncertainty of X when Y is known. It can be shown that 0 ≤ H(X|Y ) ≤ H(X). It takes its maximum value H(X) when Y reveals no information about X, and its minimum value 0 when Y completely determines the value of X.

Comparing H(X) and H(X|Y ) gives us the concept of mutual information I(X; Y ), which is defined as

I(X; Y ) = H(X) -H(X|Y )
Mutual information measures the amount of information that one random variable contains about another random variable. In other words, it measures the amount of uncertainty about X that we lose when observing Y . It can be shown that it is symmetric (I(X; Y ) = I(Y ; X)) and that 0 ≤ I(X; Y ) ≤ H(X).

The maximum mutual information between X and Y over all possible distributions p(x) is known as the channel's capacity:

C = max p(x) I(X; Y )
The capacity of a channel gives the maximum rate at which information can be transmitted using this channel.

In the following we recall some of the notions of protection, based on informationtheoretic notions, which have been proposed in literature.

In [START_REF] Serjantov | Towards an information theoretic metric for anonymity[END_REF][START_REF] Díaz | Towards measuring anonymity[END_REF] the authors propose a notion of anonymity based on the entropy of the users. The idea is to represent the lack of information that an attacker has about the secrets. Note that this is not in line with our point of view: in our opinion the interesting thing is to model the capability of the protocol to conceal the secret information despite of the observables that are made available to the attacker.

Zhu and Bettati propose in [START_REF] Zhu | Anonymity vs. information leakage in anonymity systems[END_REF] a definition of anonymity based on mutual information.

In [START_REF] Moskowitz | Covert channels and anonymizing networks[END_REF][START_REF] Moskowitz | Quasi-anonymous channels[END_REF] the authors study the ability to have covert communication as a result of non-perfect anonymity. In [START_REF] Moskowitz | Quasi-anonymous channels[END_REF] the authors suggest that the channel's capacity can be used as an asymptotic measure of the worst-case loss of anonymity.

In [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] we explore the implications of adopting the (converse of the) notion of capacity as measure of the degree of protection, and we introduce a more general concept that we call conditional capacity.

Note that the capacity is an abstraction of mutual information obtained by maximizing over the possible input distributions. As a consequence, we get a measure that depends only on the protocol and not on the input distribution, which is an advantage with respect to the mutual-information approach because in general we don't know the input distribution, and it also may change over time. Of course, in case we know the input distribution, then the mutual-information approach is more precise because it gives the exact loss of anonymity for the specific situation.

In [START_REF] Deng | Measuring anonymity with relative entropy[END_REF] the authors use the Kullback-Leibler distance to perform a metric analysis of anonymity.

In [START_REF] Clarkson | Belief in information flow[END_REF] the authors define as information leakage the difference between the a priori accuracy of the guess of the attacker, and the a posteriori one, after the attacker has made his observation. The accuracy of the guess is defined as the Kullback-Leibler distance between the belief (which is a weight attributed by the attacker to each input hypothesis) and the true distribution on the hypotheses.

In the field of information flow and non-interference there is a line of research which is closely related. There have been various works [START_REF] Mclean | Security models and information flow[END_REF][START_REF] Gray | Toward a mathematical foundation for information flow security[END_REF][START_REF] Clark | Quantitative analysis of the leakage of confidential data[END_REF][START_REF] Clark | Quantified interference for a while language[END_REF][START_REF] Lowe | Quantifying information flow[END_REF][START_REF] Boreale | Quantifying information leakage in process calculi[END_REF] in which the high information and the low information are seen as the input and output respectively of a channel. From an abstract point of view, the setting is very similar; technically it does not matter what kind of information we are trying to conceal, what is relevant for the analysis is only the probabilistic relation between the input and the output information.

Hypothesis testing

In information-hiding systems the attacker finds himself in the following scenario: he cannot directly detect the information of interest, namely the actual value of the random variable S ∈ S, but he can discover the value of another random variable O ∈ O which depends on S according to a known conditional distribution. This kind of situation is quite common also in other disciplines, like medicine, biology, and experimental physics, to mention a few. The attempt to infer S from O is called hypothesis testing (the "hypothesis" to be validated is the actual value of S), and it has been widely investigated in statistics.

In this section we discuss possible methods by which an adversary can try to infer the secrets from the observables, and consider the corresponding probability of error, that it, the probability that the adversary draws the wrong conclusion. We regard the probability of error as a representative of the degree of protection provided by the protocol, and we study its properties with respect to the associated matrix.

We start by recalling the notion of decision function, which represent the guess the adversary makes about the secrets, for each observable: a decision function is simply any function f : O → S.

The probability of error associated to a decision function f is the probability of guessing the wrong hypothesis by using f , averaged on all possible observables. In general the probability of error depends on the input distribution and on the channel's matrix. We will use the notation P(f, M, p) to represent the probability of error associated to the decision function f , the channel's matrix M , and the input distribution p. The following characterization of P(f, M, p) is well-known in literature, see for instance [START_REF] Cover | Elements of Information Theory[END_REF].

P(f, M, p) = 1 - O p(o|f (o))p f (o) (5)
Given a channel (S, O, M ), the best decision function that the adversary can use, namely the one that minimizes the probability of error, is the one associated to the so-called MAP rule, which prescribes to choose the hypothesis s which has Maximum Aposteriori Probability (for a given o ∈ O), namely the s for which p(s|o) is maximum. The fact that the MAP rule represent the 'best bet' of the adversary is rather intuitive, and well known in literature. We refer to [START_REF] Cover | Elements of Information Theory[END_REF] for a formal proof.

The MAP rule is used in the so-called Bayesian approach to hypothesis testing, and the corresponding probability of error is also known as Bayes risk. We will denote it by P MAP (M, p). The following characterization is an immediate consequence of (5) and of the Bayes theorem p(s|o) = p(o|s)p s /p(o).

P MAP (M, p) = 1 - O max s (p(o|s)p s )
In [START_REF]Compositional Methods for Information-Hiding[END_REF] we have proposed to express the degree of protection Pt provided by a protocol T in terms of the probability of error of the corresponding matrix M (T ):

Pt MAP (T, p) = P MAP (M (T ), p)
The problem with the MAP rule is that it assumes that the input distribution is known to the adversary. This is often not the case, so it is natural to try to approximate it with some other rule. One such rule is the so-called ML rule, which prescribes to choose the s which has Maximum Likelihood (for a given o ∈ O), namely the s for which p(o|s) is maximum. The name comes from the fact that p(o|s) is called the likelihood of s given o. We will denote the corresponding probability of error by P ML (M, p). The following characterization is an immediate consequence of [START_REF] Clarke | Freenet: A distributed anonymous information storage and retrieval system[END_REF].

P ML (M, p) = 1 - O max s (p(o|s))p s
It has been shown (see for instance [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF]) that under certain conditions on the matrix, the ML rule approximates indeed the MAP rule, in the sense that by repeating the protocol the adversary can make the probability of error arbitrarily close to 0, with either rule.

We have also explored, in [START_REF]Compositional Methods for Information-Hiding[END_REF], the possibility of defining the degree of protection provided by a term T under the ML rule as P ML (M (T ), p), but it did not seem reasonable to give a definition that depends on the input distribution, since the main reason to apply a non-Bayesian approach is that we do not know the input distribution. Instead, we have defined the degree of protection associated to a process term as the average probability of error with respect to all possible distributions p:

Pt ML (T ) = (m -1)! p P ML (M (T ), p) d p
In previous definition, (m -1)! represents a normalization function:

1 (m-1)! is the hyper-volume of the domain of all possible distributions p on S, namely the (m -1)dimensional space of points p such that 0 ≤ p s ≤ 1 and 0 ≤ s∈S p s = 1 (where m is the cardinality of S).

Fortunately, it turns out that this definition is equivalent to a much simpler one: the average value of the probability of error, under the Maximum Likelihood rule, can be obtained simply by computing P ML on the uniform distribution p u = ( 1 m , 1 m , . . . , 1 m ):

Pt ML (T ) = min ζ∈A P ML (M ζ (T ), p u )
We believe that the probability of error is a central notion for information-hiding, and we expect that it will be thoroughly explored in the next future.

In [START_REF] Chatzikokolakis | Probability of error in informationhiding protocols[END_REF] we have characterized the Bayes risk in terms of the solution of certain systems of equations derived from the matrix of the channel. This has lead to an algorithm to compute the maximum value of the Bayes risk. Furthermore, it has allowed us to improve functional bounds on the Bayes risk.

In [START_REF]Compositional Methods for Information-Hiding[END_REF] we have studied how the operators of π p affect the probability of error. In particular, we have characterized constructs that have the property of not decreasing the degree of protection, and that can therefore be considered safe in the modular construction of protocols. As a case study, we apply these techniques to the Dining Cryptographers, and we are able to derive a generalization of Chaum's strong anonymity result for the Dining Criptographers. More precisely, we have shown that the Dining Cryptographers on an arbitrary graph (where the nodes are the cryptographers and the arcs are the coins) is strongly anonymous if and only there is a spanning tree formed entirely of fair coins.

Computing the matrix associated to a protocol

In this section we show how to compute the matrix associated to a protocol specified in π p , using our (very preliminary) π p model checker VAMP (http://vamp.gforge. inria.fr/).

We consider the protocol for the DC represented in Table 1. Assume we want to compute p(o|s i ), where s i represents the fact that the cryptographer i is the payer, and o is of the form outall y o , y 1 , y 2 . We redefine the Master to be m i 1 . m i+1 0 . m i+2 0 Then, we run the resulting process DC in VAMP, with query o. VAMP gives as result the (unconditional) probability of executing o in the new specification, which corresponds to the conditional probability p(o|s i ) in the original specification.

We have computed various channel matrices, for different values of the probability p that a coin gives heads (we assume that each coin is biased in the same way). The results are shown in Fig. 3.

Finally, from the matrix, we can compute the capacity. This can be done, in general, by using the Arimoto-Blahut approximation algorithm, or, under certain symmetry conditions, we can apply a formula (see [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF] for more details).

In this case we could apply the formula because the conditions are satisfied. The resulting graph is displayed in Fig. 4. As expected, when p = 0.5 the protocol is strongly anonymous and the relative loss of anonymity is 0. When p approaches 0 or 1, the attacker can deduce the identity of the payer with increasingly high probability, so the capacity increases. In the extreme case where the coins are totally biased the attacker can be sure about the payer, and the capacity takes its maximum value of log 3.

Fig. 1 .

 1 Fig. 1. Chaum's protocol for the dining cryptographers [3].

Fig. 2 .

 2 Fig. 2. Illustration of Example 1: the results that are observed with high frequency.

( 2 )

 2 and (3) are equivalent. In fact: (2) ⇒ (3) ) p(o|s) = p(s|o) p(o) p(s) by Bayes theorem = p(o) by (2) = p(s ′ |o) p(o) p(s ′ ) by (2) = p(o|s ′ ) by Bayes theorem (2) ⇐ (3) ) We prove that p(o|s) = p(o) for all observables o, and secrets s. From this it is immediate to derive (2) by applying Bayes theorem. p(o) = s p(o and s) by the disjointness of the secrets = s p(o|s) p(s) by definition of conditional probability = p(o|s) s p(s) by (3) = p(o|s) since s p(s) = 1

( 1 )

 1 ⇒ (4) ) p(s) = o p(s and o) by the disjointness of the secrets = o p(s|o) p(o) by definition of conditional probability= o p(s ′ |o) p(o) by (1) = o p(s ′ and o) = p(s ′ ) (1) ⇒ (3) ) p(o|s) = p(s|o) p(o) p(s) by Bayes theorem = p(s ′ |o) p(o) p(s) by (1) = p(s ′ |o) p(o) p(s ′ ) by (4) = p(o|s ′ ) by Bayes theorem (1) ⇐ (3),(4)) p(s|o) = p(o|s) p(s) p(o) by Bayes theorem = p(o|s ′ ) p(s) p(o) by (3) = p(o|s ′ ) p(s ′ ) p(o) by (4) = p(s ′ |o) by Bayes theorem

Fig. 3 . 9 Fig. 4 .

 394 Fig.3. The channel matrices for probability of heads p = 0.5, p = 0.6, p = 0.7, p = 0.8, and p = 0.9

⋆ This work has been partially supported by the INRIA DREI Équipe Associée PRINTEMPS and by the INRIA ARC project ProNoBiS.

The presence of the process Collect is due to technical reasons that have to do with the control of the power of the scheduler, and are out of the scope of this paper.


Mikael Pontarp
email: mikael.pontarp@biol.lu.se

Lynsey Bunnefeld

Juliano Sarmento Cabral

Rampal S Etienne

Susanne A Fritz

Rosemary Gillespie

Catherine H Graham

Oskar Hagen

Florian Hartig

Shan Huang

Roland Jansson

Odile Maliet

Loïc Pellissier

Thiago F Rangel

David Storch

Thorsten Wiegand

Allen H Hurlbert

The Latitudinal Diversity Gradient: Novel Understanding through Mechanistic Eco-evolutionary Models

Keywords: latitudinal diversity gradient -novel understanding through mechanistic eco-evolutionary models diversity-patterns, mechanistic-modeling, ecology, evolution, biogeography, macroecology

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Outstanding Questions

What are the underlying causes of the latitudinal diversity gradient (LDG)? Multiple hypotheses have been formulated to answer this question but a consensus remains elusive, partly due to hidden assumptions that are associated with these primarily verbal hypotheses.

What key processes, describing how organisms interact with their biotic and abiotic environment, are necessary and sufficient for modeling biodiversity patterns associated with the LDG? We argue for eco-evolutionary processes: selection, dispersal, ecological drift, and speciation, but researchers need to explore the tradeoffs associated with modeling these processes in greater or lesser detail.

How are eco-evolutionary simulation models best confronted with empirical data (e.g. phylogenies, species ranges, rank abundances, and functional trait distributions)? Pattern oriented modeling and novel Bayesian statistics may be the key for such a quantification of the link between process and LDG patterns.

Outstanding Questions

Abstract

The latitudinal diversity gradient (LDG) is one of the most widely studied patterns in ecology, yet no consensus has been reached about its underlying causes. We argue that the reasons are the verbal nature of existing hypotheses, the failure to mechanistically link interacting ecological and evolutionary processes to the LDG, and the fact that empirical patterns are often consistent with multiple explanations. To address this issue, we synthesize current LDG hypotheses, uncovering their eco-evolutionary mechanisms, hidden assumptions, and commonalities. Furthermore, we propose mechanistic eco-evolutionary modeling and an inferential approach that makes use of geographic, phylogenetic, and trait-based patterns to assess the relative importance of different processes for generating the LDG.

State of the art and calls for novel mechanistic approaches

The increase in species diversity from the poles to the equator, commonly referred to as the latitudinal diversity gradient (LDG), is one of the most pervasive [START_REF] Hillebrand | On the generality of the latitudinal diversity gradient[END_REF][START_REF] Mannion | The latitudinal biodiversity gradient through deep time[END_REF] and widely debated biological patterns, with at least 26 listed hypotheses associated with it [START_REF] Lomolino | Biogeography: biological diversity across space and time[END_REF][START_REF] Fine | Ecological and evolutionary drivers of geographic variation in species diversity[END_REF][START_REF] Currie | Predictions and tests of climate-based hypotheses of broad-scale variation in taxonomic richness[END_REF]. These hypotheses can be classified into three higher-level categories related to latitudinal variation in ecological limits (See Glossary), diversification rates, and time for species accumulation (Table 1). Empirical evidence seems compatible with many of these hypotheses. For example, species richness is correlated with purported proxies for ecological limits such as net primary productivity [START_REF] Hawkins | Productivity and history as predictors of the latitudinal diversity gradient of terrestrial birds[END_REF][START_REF] Valentine | A twofold role for global energy gradients in marine biodiversity trends[END_REF][START_REF] Fritz | Twenty-million-year relationship between mammalian diversity and primary productivity[END_REF], diversification rate can vary latitudinally due to gradients in temperature [START_REF] Rohde | Latitudinal gradients in species-diversity -the search for the primary cause[END_REF][START_REF] Ricklefs | Global variation in the diversification rate of passerine birds[END_REF], and diversity is greatest in regions where diversification has occurred over a longer period [START_REF] Mittelbach | Evolution and the latitudinal diversity gradient: speciation, extinction and biogeography[END_REF][START_REF] Wiens | Niche conservatism as an emerging principle in ecology and conservation biology[END_REF][START_REF] Marin | Evolutionary time drives global tetrapod diversity[END_REF]. These and similar studies have improved our understanding of the LDG and macroevolutionary patterns in general, but the diffuse support for different hypotheses reveals a lack of consensus and points to challenges in testing and evaluating these hypotheses.

We argue that reconciling the causes of the LDG requires moving beyond verbal chains of logic, which are inherently prone to error with respect to how assumptions result in their predicted effect [START_REF] Servedio | Not just a theory-the utility of mathematical models in evolutionary biology[END_REF], and towards a more formal and mechanistic framework. Verbal hypotheses often contain hidden assumptions that go untested and lack specificity with respect to the mechanistic underpinning of relevant ecological and evolutionary processes.

Verbal hypotheses also tend to focus on a single driver to predict just one or a few patterns related to that driver. Consequently, these predictions alone may not be sufficient to distinguish competing hypotheses [START_REF] Grimm | Pattern-oriented modeling of agent-based complex systems: lessons from ecology[END_REF][START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF]. A more explicit description of the processes underlying all hypotheses will generate a wider range of predictions which can be used to disentangle possibly non-mutually exclusive hypotheses and evaluate the relative importance of these processes.

We, therefore, call for a transformation in the way biologists think about and study the LDG.

The classification of hypotheses (Table 1) is an important first step, but it does not resolve the difficulty of identifying and quantifying the relative strength of the processes underlying the LDG. We propose moving towards a mechanistic framework, founded on key processes that describe how individual organisms interact with their biotic and abiotic environments, and how these interactions scale up to result in the LDG and other secondary biodiversity patterns. Ultimately, revealing the nature of these eco-evolutionary processes will yield more insight than continuing to argue about non-mutually exclusive LDG hypotheses.

Examining the LDG through the lens of mechanistic macroecology

Key processes across levels of biological organization

We recognize four key processes, as defined by [START_REF] Vellend | The Community of Ecological Communities[END_REF], that necessarily underpin the LDG and thus should be included as components of any LDG model that aims to capture variation in species richness, abundance, and composition over a spatially and temporally variable environment: 1) selection, 2) ecological drift, 3) dispersal, and 4) speciation. Selection, drift, and dispersal can all influence the birth, death, and movement of individuals over small spatial and temporal scales. Selection (sensus [START_REF] Vellend | The Community of Ecological Communities[END_REF]) encompasses any process that results in the differential survival and reproduction of individuals, based on how environmental filtering [START_REF] Kraft | Community assembly, coexistence and the environmental filtering metaphor[END_REF] and biotic interactions select for specific traits. Ecological drift manifests itself via stochastic variation in the births and deaths of individuals. Dispersal of individuals is influenced by the spatial structure of the landscape as well as individual dispersal capabilities and can lead to species colonizing new regions. Each of these individual-level ecological and microevolutionary processes is propagated throughout higher levels of biological organization, resulting in discrete patterns at the level of populations, species, and communities (Figure 1).

Over longer timescales, environmental conditions have fluctuated with glacial/interglacial oscillations, cooler and warmer periods in Earth's history, orogenic events, volcanic activity, and shifts in tectonic plates, all of which can affect diversity dynamics [START_REF] Leprieur | Plate tectonics drive tropical reef biodiversity dynamics[END_REF][START_REF] Badgley | Biodiversity and topographic complexity: modern and geohistorical perspectives[END_REF][START_REF] Pellissier | Are global hotspots of endemic richness shaped by plate tectonics?[END_REF]. At these spatial and temporal scales selection, ecological drift, and dispersal determine where species or even whole clades are able to persist geographically and how traits evolve. Species that become poorly adapted to the environment or that are poor competitors for resources are expected to have low fitness and ultimately go extinct, reflecting critical eco-evolutionary feedbacks [START_REF] Urban | Evolving metacommunities: toward an evolutionary perspective on metacommunities[END_REF][START_REF] Urban | Community monopolization: local adaptation enhances priority effects in an evolving metacommunity[END_REF]. Speciation becomes especially relevant with increasing temporal and spatial scales. The details of how speciation occurs are complex and the critical question in a LDG context becomes how and why speciation mode or rate varies along geographic gradients. All of the processes described above necessarily interact with each other and with the spatiotemporal environment, resulting in the broad range of geographic and phylogenetic biodiversity patterns that we observe today. As highlighted below, these processes can help us compare and disentangle LDG hypotheses.

Classical LDG hypotheses revisited

Characterizing LDG hypotheses based on the key processes described above helps to clarify the internal logic of those hypotheses, and highlights how they differ. All hypotheses invoke an explicit driver or condition that varies latitudinally (Figure 1), but considering the processes related to this driver, often below the level of biological organization at which the hypothesis was formulated, can reveal previously unrecognized assumptions and predictions.

Below we discuss four examples, chosen to represent hypotheses invoking variation in limits, rates, and time. These examples may also serve as a guide for better understanding other hypotheses.

The more individuals hypothesis

The "more individuals hypothesis" invokes latitudinal variation in ecological limits and a positive relationship between the number of species and resource availability [START_REF] Storch | The more-individuals hypothesis revisited: the role of community abundance in species richness regulation and the productivity-diversity relationship[END_REF]. If resources are finite and a zero-sum constraint on the total amount of biomass or individuals applies, any increase in diversity over time results in a decrease in average biomass or abundance per species. Extinction rates will thus be diversity-dependent and richness will be regulated around some equilibrial value that scales with the total number of individuals that can be supported [START_REF] Storch | The more-individuals hypothesis revisited: the role of community abundance in species richness regulation and the productivity-diversity relationship[END_REF][START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF]. This hypothesis implicitly invokes interspecific competition and the resultant allocation of resources across species (Table 1). The argument does not invoke selection (Fig. 1) and can be applied equally to ecologically neutral or non-neutral species. An important and unstated assumption is that the response of the biota to environmental change is fast enough that richness is at equilibrium across the latitudinal gradient.

The seasonality hypothesis

The seasonality hypothesis argues that the within-year environmental stability of the tropics results in either greater diversification rates or higher ecological limits via increased niche packing (Table 1 and Fig. 1). The first argument suggests that in the less seasonal tropics, organisms experience a smaller range of conditions and hence evolve narrower thermal niches compared to the temperate zone. The idea that "mountain passes are higher in the tropics" [START_REF] Janzen | Why mountain passes are higher in tropics[END_REF] suggests that dispersal barriers were effectively greater there, increasing the chance of population divergence and allopatric speciation [START_REF] Ghalambor | Are mountain passes higher in the tropics? Janzen's hypothesis revisited[END_REF][START_REF] Sheldon | Fifty years of mountain passes: a perspective on Dan Janzen's classic article[END_REF]. Selection thus dictates the environmental conditions that a species can tolerate, but it is speciation rate that varies with latitude and ultimately generates the LDG. The second version of the seasonality hypothesis suggests that stability-driven specialization promotes intense niche packing, and hence more species can coexist in the tropics [START_REF] Macarthur | Geographical ecology[END_REF][START_REF] Ben-Eliahu | A comparison between species diversities of polychaetes from tropical and temperate structurally similar rocky inter-tidal habitats[END_REF]. Species are then hypothesized to evolve narrower resource breadths rather than narrow thermal niches, assuming that resources are limited and that diversity actually emerges from niche packing [START_REF] Macarthur | Geographical ecology[END_REF] (Table 1, Figure 1). Implicit in both hypotheses is a performance tradeoff between specialists and generalists, such that specialists evolve and outcompete generalists in aseasonal environments.

The temperature-dependent speciation rates hypothesis

The hypothesis that higher temperature elevates evolutionary rates has been used to explain global diversity patterns in both land and sea [START_REF] Antonelli | An engine for global plant diversity: highest evolutionary turnover and emigration in the American tropics[END_REF][START_REF] Rabosky | An inverse latitudinal gradient in speciation rate for marine fishes[END_REF]. One version of the hypothesis [START_REF] Allen | Kinetic effects of temperature on rates of genetic divergence and speciation[END_REF] follows from the metabolic theory of ecology [START_REF] Brown | Toward a metabolic theory of ecology[END_REF], stating that temperature positively affects all biological rates including mutation rates, which can lead to speciation and ultimately diversity accumulation. This assumes that speciation rates directly follow from mutation rates, which may be problematic if other factors (e.g. existence of geographic barriers, assortative mating) are limiting speciation. The hypothesis makes no specific predictions regarding selection or dispersal. Importantly, this hypothesis could be invoked in either an equilibrium or non-equilibrium world. In a non-equilibrium world, speciation rates alone could explain variation in richness between regions if all regions were similarly old, and extinction rates were equal across regions [START_REF] Ricklefs | Global variation in the diversification rate of passerine birds[END_REF]. In an equilibrium world, increased speciation rates in the tropics can lead to higher equilibrium richness, as in Hubbell [START_REF] Hubbell | The unified neutral theory of biodiversity and biogeography[END_REF] neutral model of biodiversity.

The tropical niche conservatism hypothesis

The tropical niche conservatism hypothesis [START_REF] Wiens | Historical biogeography, ecology and species richness[END_REF][START_REF] Wiens | Niche conservatism: Integrating evolution, ecology, and conservation biology[END_REF] states that diversity is higher in the tropics because of the infrequency of colonisations of the cooler temperate zone by a tropical ancestor due to strongly conserved thermal niches and tropical origins of most taxa, and hence the longer time available for diversification in the tropics. The hypothesis assumes that, barring major disturbances or climatic shifts, species richness will continue to increase unbounded over time [START_REF] Wiens | Niche conservatism: Integrating evolution, ecology, and conservation biology[END_REF]. This hypothesis has only ever been formulated at the species level, and yet it inherently implies a particular set of rules by which individuals interact with the environment and each other. Selection by the environment is by definition strong, with individuals unable to survive and reproduce under conditions different from their optima, and evolution of a new optimum is rare. Less obvious are the implications of the hypothesis for resource competition between individuals. Unbounded, or diversity-independent, diversification is only possible in the absence of an overarching zero-sum constraint [START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF]. The absence of such a constraint implies that while the population size of a species might be affected by the fit between the environment and environmental performance traits, it is independent of the population sizes of potential competitors and of interspecific competition more broadly.

The utility of a mechanistic framework

The examples presented above illustrate three insights gained by adopting a generalized ecoevolutionary framework. First, many of the fundamental rules by which organisms are assumed to interact with each other and with their environment will be qualitatively similar regardless of LDG hypothesis. For example, individual survival and reproduction must be functions of how well adapted the individuals are to their environment relative to their intraand interspecific competitors. Second, latitudinal differences in ecological limits, diversification rates, and time for diversification may emerge via different mechanisms integrated into the same framework. For example, diversification rates may be higher due to the temperature-dependence of mutation rates [START_REF] Rohde | Latitudinal gradients in species-diversity -the search for the primary cause[END_REF][START_REF] Gillooly | Linking global patterns in biodiversity to evolutionary dynamics using metabolic theory[END_REF] or due to the increased reproductive isolation in aseasonal environments [START_REF] Ghalambor | Are mountain passes higher in the tropics? Janzen's hypothesis revisited[END_REF][START_REF] Jocque | Climatic control of dispersal-ecological specialization trade-offs: a metacommunity process at the heart of the latitudinal diversity gradient?[END_REF]. Third, although each hypothesis invokes a primary driver or process, we have shown that these hypotheses also make unstated assumptions about other processes and mechanisms which need to be considered in concert to fully understand the emergence of the LDG and other macroecological and macroevolutionary patterns.

Mechanistic eco-evolutionary models as a quantitative tool for understanding LDG patterns

The mechanistic framing of processes that underpin the LDG naturally facilitates the translation from heuristic thinking to mechanistic eco-evolutionary models (Box 1). We believe that building these models will be essential to making progress on the LDG and biodiversity patterns in general because they allow quantitative analyses and predictions of the various secondary patterns. Secondary patterns are key for more powerful inference about the origin of species richness patterns. Below we provide concrete examples of components of a mechanistic LDG model and associated patterns followed by a discussion about how to use such a model for inference with the available data.

Mechanistic models for studying the LDG

The spatiotemporal environmental template

The basic driver of an LDG model is the spatiotemporal environmental template. It can be viewed as the theater in which the eco-evolutionary play unfolds, and the spatiotemporal variation in that template (Earth's climatic, geologic, and tectonic history) may be as critical to emergent diversity patterns as the mechanisms and processes governing how organisms interact and evolve [START_REF] Dynesius | Evolutionary consequences of changes in species' geographical distributions driven by Milankovitch climate oscillations[END_REF][START_REF] Rangel | Modeling the ecology and evolution of biodiversity: Biogeographical cradles, museums, and graves[END_REF][START_REF] Davies | Neutral biodiversity theory can explain the imbalance of phylogenetic trees but not the tempo of their diversification[END_REF]. Explaining the LDG with eco-evolutionary simulation models, therefore, benefits from suitable paleoenvironmental reconstructions [START_REF] Descombes | Linking species diversification to palaeo-environmental changes: a process-based modelling approach[END_REF] and the integration of global data sets on continental topography and paleoshorelines [START_REF] Muller | Long-term sea-level fluctuations driven by ocean basin dynamics[END_REF][START_REF] Chalmandrier | Comparing spatial diversification and meta-population models in the Indo-Australian Archipelago[END_REF].

Trait-based local population dynamics

Traits are essential for individual survival and reproduction (fitness) and mechanistic models that include interactions of organismal traits and the abiotic and biotic environment, below the level of species (i.e. at the individual, population or metapopulational level), is thus appropriate. Local population dynamics can, for example be assumed to be trait-dependent [START_REF] Brännström | Modelling the ecology and evolution of communities: a review of past achievements, current efforts, and future promises[END_REF][START_REF] Cabral | Linking ecological niche, community ecology and biogeography: insights from a mechanistic niche model[END_REF]. One set of traits might determine an organism's fitness dictated by the abiotic environment, a different set of traits may influence relative fitness associated with the suite of potential competitors present at any point in time [START_REF] Pontarp | The origin of species richness patterns along environmental gradients: uniting explanations based on time, diversification rate and carrying capacity[END_REF]. Such a modeling approach requires making basic assumptions that facilitate the link between environmental conditions, available resources, and ecological interactions, and population dynamics then emerge from those assumptions.

Spatial and eco-evolutionary metacommunity dynamics

For modeling eco-evolutionary metacommunity dynamics, trait-based models need to be implemented in a larger spatial context, allowing individuals to disperse over geographically relevant extents. Metacommunity dynamics will arise from eco-evolutionary feedbacks between dispersing individuals and recipient communities within the context of the spatiotemporal template [START_REF] Urban | The evolution of species interactions across natural landscapes[END_REF]. Evolutionary dynamics result from natural selection by both abiotic and biotic conditions, ecological drift, dispersal, and speciation. Speciation can be modeled using a phenomenological approach or more complex allele-based models in which phenotypic trait variability is completely or partially heritable and the accumulation of genetic incompatibilities may drive differentiation of daughter species (Box 2). Each of these modeling components is necessary for capturing the suite of processes invoked by LDG hypotheses (Box 1), they can be modeled with varying degrees of complexity and they come with a set of low-level assumptions that need to be clearly stated (Box 2).

Understanding patterns and inferring processes

Above we have shown that a mechanistic mindset is useful to better understand the internal logic and consequences of the different hypotheses, as well as the interactions among them. In addition, a mechanistic model can clarify the biodiversity patterns expected under different combinations of spatiotemporal environmental templates, biotic interactions, and other ecoevolutionary rules [e.g. [START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF][START_REF] Pontarp | The origin of species richness patterns along environmental gradients: uniting explanations based on time, diversification rate and carrying capacity[END_REF][START_REF] Roy | Origination, extinction, and dispersal: Integrative models for understanding present-day diversity gradients[END_REF]. This ability to simulate very different worldviews of how the LDG arises (e.g., "ecological limits", "niche conservatism", etc.) within the same comparative framework is a critical element of our approach as different types of processes modeled with varying degrees of mechanistic detail can be explored and contrasted.

Ultimately, we need mechanistic models to understand the details of the emerging ecoevolutionary patterns at a sufficient resolution to be able to quantitatively confront them with data. The more secondary patterns (e.g. phylogenies, species ranges, distributions of abundance or functional traits) that can be modeled, the greater the diagnostic power of the model for exploring parameter space and for inferring the strength and interactions of different processes. The examination of these patterns will also point to the type of data that will be most valuable for reliable inference of a given process [START_REF] Pontarp | Community trait overdispersion due to trophic interactions: concerns for assembly process inference[END_REF].

While we believe that confronting different model scenarios with multiple observed patterns (described in Box 3) is the only way to make progress in understanding the LDG, we realize that substantial conceptual, statistical, and computational challenges are associated with this task [START_REF] Connolly | Process, Mechanism, and modeling in macroecology[END_REF]. The complexity of the suggested models often makes it difficult to understand the consequences of the underlying assumptions. Ways of overcoming such challenges are to build on known ecological models (e.g. Lotka-Volterra equations) and evolutionary theory (e.g. Adaptive Dynamics theory) that has been studied extensively. The models should also be built and analyzed in a sequential manner of increased complexity to shed light on the consequences of the key model assumptions and their interactions. While it is not our aim to detail these and other methodological challenges here, we nevertheless highlight two basic inferential approaches that seem particularly promising. First, qualitative matching of multiple patterns gives an indication of whether the modeled processes can produce the patterns that we observe [START_REF] Grimm | Pattern-oriented modeling of agent-based complex systems: lessons from ecology[END_REF][START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF][START_REF] Rangel | Modeling the ecology and evolution of biodiversity: Biogeographical cradles, museums, and graves[END_REF][START_REF] Cabral | Mechanistic simulation models in macroecology and biogeography: state-of-art and prospects[END_REF]. Pattern matching is conceptually straightforward and easily allows combining the LDG with multiple observed secondary patterns to compare alternative model or parameter choices. Second, models like the ones suggested above can be fitted to a range of patterns in data using simulation-based methods such as Approximate Bayesian Computation [START_REF] Sisson | Sequential Monte Carlo without likelihoods[END_REF][START_REF] Beaumont | Approximate Bayesian Computation in Evolution and Ecology[END_REF][START_REF] Hartig | Statistical inference for stochastic simulation models -theory and application[END_REF][START_REF] Blum | A comparative review of dimension reduction methods in Approximate Bayesian Computation[END_REF] or synthetic likelihood [START_REF] Wood | Statistical inference for noisy nonlinear ecological dynamic systems[END_REF][START_REF] Hartig | Technical note: Approximate Bayesian parameterization of a process-based tropical forest model[END_REF]. Regardless of which inferential approach is used, any empirical patterns that a model is unable to reproduce can be instructive in the iterative process of model improvement.

Concluding remarks

Progress in understanding the processes that underlie LDG patterns and associated diversity patterns has been slow (see also Outstanding Questions). We repeat calls for a transition in biodiversity research, translating verbal models into a unified mechanistic framework that can be implemented in quantitative computer simulations [START_REF] Connolly | Process, Mechanism, and modeling in macroecology[END_REF][START_REF] Cabral | Mechanistic simulation models in macroecology and biogeography: state-of-art and prospects[END_REF][START_REF] Gotelli | Patterns and causes of species richness: a general simulation model for macroecology[END_REF]. In such a framework, researchers can focus on measuring and inferring the ecological and evolutionary processes that govern the interaction of organisms with each other and their environment in time and space, which must ultimately underpin the LDG. By applying this framework, hidden assumptions in current hypotheses are exposed, revealing how the hypotheses relate to each other and how they might be distinguished (Table 1, Figure 1). More importantly, this framework is a roadmap for flexible eco-evolutionary simulation models (Box 1-2) that can generate a rich set of empirical patterns from the same underlying processes. We believe that this ability to produce multiple diagnostic patterns will be crucial for inference (Box 3), and ultimately for converting the available data into new knowledge about macroecology and macroevolution. Challenges associated with model construction and the way models are confronted with data will arise, but such challenges are inherent and inevitable to all sciences that deal with complex systems. We are confident that, with time, these challenges can be addressed, and models combining realistic spatiotemporal environmental templates with trait based eco-evolutionary implementation under an iterative procedure of model design, evaluation and improvement, will advance our understanding and quantitative inference of the processes underlying the LDG.

Box 1 (text) Box 1. An LDG simulation model in action

Any simulation model of the processes that result in patterns at the biogeographic scale [e.g. but subject to selection). The difference between a species' thermal optimum and the temperature of the region determines that species' local population size. Species may experience implicit competition via a regional zero-sum constraint, and the probability of speciation, dispersal, and extinction are each functions of regional population size. The simulation results in spatial richness patterns, regional trait distributions, and a phylogenetic tree (Figure I.C).

The simulation model was run under different parameter combinations that mimic distinct LDG hypotheses ("Niche Conservatism", "Ecological Limits", "Diversification Rates"), and the emergent geographic, trait and phylogenetic data were used to derive further metrics and patterns that provide diagnostic support for each hypothesis (Figure I.D, only two patterns shown). Simulated and observed patterns were compared informally. This study demonstrated the utility of comparing expectations for multiple hypotheses, confirming that many patterns like the diversity gradient itself and measures of phylogenetic tree imbalance were shared across hypotheses. Conversely, patterns like the relationship between speciation rate and latitude or mean root distance and richness were potentially diagnostic of the processes that generated them [START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF].

While exemplifying many of the desirable properties of a mechanistic model for the LDG, there are several ways in which the model in Hurlbert and Stegen [START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF][START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF] could be improved.

First, the geographic representation of the model was a simple one-dimensional spatial gradient with no long-term climate dynamics. Second, the model has no means of representing a trophic niche in particular, or niche specialization in general, both of which are invoked by various LDG hypotheses (Table 1). Third, speciation is modeled as a point mutation process which may impact simulated phylogenetic patterns (Box 2). Finally, to make more quantitative inferences about the support for the respective hypotheses, a formal statistical parameter estimation, and model selection would be desirable [START_REF] Cabral | Mechanistic simulation models in macroecology and biogeography: state-of-art and prospects[END_REF][START_REF] Csillery | Approximate Bayesian Computation (ABC) in practice[END_REF][START_REF] Van Der Plas | A new modeling approach estimates the relative importance of different community assembly processes[END_REF]. We discuss methods of fitting empirical patterns to simulations in Box 3.

Box 2 (text) Box 2: Modeling decisions: the example of speciation

Modeling each of the components in Box 1, Figure IA requires a wealth of implementation decisions. These decisions may have consequences for how well a given hypothesis is represented, and what types of patterns emerge. As an example, we consider the case of speciation, which can be modeled with varying degrees of complexity [START_REF] Rundell | Adaptive radiation, nonadaptive radiation, ecological speciation and nonecological speciation[END_REF], from a purely phenomenological approach to more complex allele-based models. For example, spatial processes combined with drift may induce speciation through Dobzhansky-Müller Incompatibilities [START_REF] Orr | The evolution of postzygotic isolation: accumulating Dobzhansky-Muller incompatibilities[END_REF] while abiotic and ecological factors can induce disruptive selection and speciation both in allopatry [e.g. [START_REF] Rangel | Modeling the ecology and evolution of biodiversity: Biogeographical cradles, museums, and graves[END_REF][START_REF] Etienne | The neutral theory of biodiversity with random fission speciation[END_REF] or sympatry [e.g. 66, 67]. For complete divergence and the formation of proper (biological) species, mechanisms for reproductive isolation, including sexual selection and assortative mating, also adds to the complexity.

After making decisions about what speciation mode to model (e.g. sympatric versus allopatric), modelers face a range of implementation choices from purely phenomenological models of point mutation speciation as in Box 1 to more mechanistic models, where species diversification emerges from evolved trait divergence [START_REF] Pontarp | The origin of species richness patterns along environmental gradients: uniting explanations based on time, diversification rate and carrying capacity[END_REF][START_REF] Gavrilets | Dynamic patterns of adaptive radiation[END_REF][START_REF] De Aguiar | Global patterns of speciation and diversity[END_REF][START_REF] Pontarp | The biogeography of adaptive radiations and the geographic overlap of sister species[END_REF], or the accumulation of genetic differences that arise as a function of vicariant events or divergent selection (Figure I). These implementation decisions can impact emergent phylogenetic patterns. For example, Davies et al [START_REF] Davies | Neutral biodiversity theory can explain the imbalance of phylogenetic trees but not the tempo of their diversification[END_REF] showed that measures of tree imbalance and branch stemminess were sensitive to whether speciation occurred via point mutation or various types of range fission.

More generally, to draw a reliable inference, researchers should assess their possible implementation options and evaluate the sensitivity of the patterns of interest to these choices. Some patterns will inevitably be more sensitive to implementation decisions than the others.

For example, the topology of a phylogeny captures the relative branching pattern but is agnostic about branch lengths, and so topology may be less sensitive than branch length-based metrics to decisions that affect the timing and rate of speciation events. When attempting to infer process from empirical data, patterns sensitive to those implementation decisions should either be disregarded, or the implementation decision itself can be included as alternative submodels that are then inferred by data. A more general discussion of fitting models to data is provided in Box 3.

Box 3 (text) Box 3. Inference

Possibly the most crucial step in using mechanistic eco-evolutionary models for inference about the origin of the LDG is the way we confront them to data, for example, to compare In detail, however, there are various challenges to achieve correct inference. How to weigh the different patterns, and account for their uncertainty, is one of them [START_REF] Keenan | The model-data fusion pitfall: assuming certainty in an uncertain world[END_REF][START_REF] Kuppel | What can we learn from multi-data calibration of a process-based ecohydrological model[END_REF]. Another challenge is how to deal with uncertainties in parameters and subprocesses. As most model parameters cannot be measured directly, any model comparison has to account for their uncertainty, such that the support assigned to any of the model alternatives is not contingent on arbitrary parameter choices. One possibility would be to test whether output patterns are dependent on model parameters and only use patterns that are independent for inference about the model alternatives. However, that would likely severely reduce the number of patterns that can be used for inference. A better, albeit computationally more expensive alternative, is to use techniques of inverse modeling to calibrate each model alternative [e.g. 56], and then compare their support using established statistical model selection methods that account for parameter uncertainty (e.g. the Bayes factor; Figure I). This more complete approach to model comparison is also the preferred solution in other research fields dealing with comparable problems (large complex system, no replicate observation), such as cosmological models of the early Universe [START_REF] Trotta | Bayes in the sky: Bayesian inference and model selection in cosmology[END_REF]. Another solution would be to avoid the model selection problem altogether, and instead phrase the inferential problem as a problem of parameter inference for a "supermodel" that includes all the possible pathways (i.e. model alternatives) and processes leading to the LDG, and through which we estimate relative strength of each pathway, instead of testing fixed hypotheses.

Glossary Box

Approximate Bayesian Computation (ABC): a simulation-based approach to create approximate likelihoods for model selection and parameter estimation of complex models, possibly with multiple data sources.

Diversification rate: the net rate of production of new lineages, i.e. the difference between origination and extinction rate. It usually applies to species (i.e. speciation minus extinction rate) but can be equally applied to higher or lower taxonomic levels.

Ecological limits: a limit to the number of individuals and/or taxa that can coexist within an ecosystem due to abiotic settings and biotic interactions such as competition for limited resources.

Ecological processes: interactions between individuals of the same or different species driving the dynamics of populations, communities and ecosystems within an ecological timescale, typically within a few generations of the focal organisms.

Eco-evolutionary processes: the interplay of ecological and evolutionary processes that violate the assumption that timescales of ecological and evolutionary processes can be separated; ecological processes affect evolution and vice versa.

Environmental filtering: the differential establishment, persistence, or performance of a species determined by that species' ability to tolerate a given set of abiotic conditions.

Evolutionary processes: any processes leading to genetic changes in populations driving lineage divergence and persistence within an evolutionary time scale, typically spanning many generations. Mechanisms: a system of causally interacting parts or sub-processes (e.g. ecological interactions) that constitute some process (e.g. eco-evolutionary process). Secondary biodiversity patterns: spatial, temporal, phylogenetic or trait-based diversity patterns that emerge from the same ecological and evolutionary processes as the LDG.

Table 1. Overview of the main hypotheses proposed for explaining the LDG in recent reviews, categorized by the drivers, assumptions, and rationales they invoke. These hypotheses can be classified according to three categories: ecological limits, diversification rates, and time for species accumulation. Some hypotheses invoke multiple distinctive (but not mutually exclusive) mechanisms and so are repeated in multiple categories. We also distinguish the primary cause of the diversity difference between tropical (t) and non-tropical (n) regions (as parameter indices) from secondary causes that may be explicitly or implicitly stated in the hypothesis. Subfigures illustrate the three main hypotheses categories that predict the LDG (parameters: K, carrying capacity or limit on the number of individuals or species; 𝜆, speciation rate; 𝜇, extinction rate; c, colonization rate; t, time). λt > λn, μt < μn

Ecological limits

More individuals: carrying capacity [START_REF] Storch | The more-individuals hypothesis revisited: the role of community abundance in species richness regulation and the productivity-diversity relationship[END_REF][START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF] Total amount of resources or energy More specialization [START_REF] Abrams | Monotonic or Unimodal Diversity Productivity Gradients -What Does Competition Theory Predict[END_REF][START_REF] Srivastava | Why more productive sites have more species: An experimental test of theory using tree-hole communities[END_REF] Resource availability Zero-sum dynamics at equilibrium due to competition Larger niche space in the tropics can be partitioned more finely.

Seasonality: coexistence [START_REF] Macarthur | Geographical ecology[END_REF][START_REF] Ben-Eliahu | A comparison between species diversities of polychaetes from tropical and temperate structurally similar rocky inter-tidal habitats[END_REF] Seasonality Zero-sum dynamics at equilibrium due to competition; trade-offs Higher specialization in the more stable tropics allows greater niche packing.

K t K n

Climatic stability: equilibrium [START_REF] Janzen | Why mountain passes are higher in tropics[END_REF][START_REF] Dynesius | Evolutionary consequences of changes in species' geographical distributions driven by Milankovitch climate oscillations[END_REF] Environmental stability (decadal to millennial) between generalists and specialists Temperaturedependent speciation [START_REF] Rohde | Latitudinal gradients in species-diversity -the search for the primary cause[END_REF][START_REF] Allen | Kinetic effects of temperature on rates of genetic divergence and speciation[END_REF] Temperature

No assumption about equilibrium Higher temperature in the tropics increases metabolic rates and mutation rates, and decreases generation times.

Primary: λt > λn

Diversification rates

More individuals: more mutations [START_REF] Rosenzweig | Species diversity in space and time[END_REF][START_REF] Stevens | Diversification rates increase with population size and resource concentration in an unstructured habitat[END_REF]

Geographic area and resource availability

No assumption about equilibrium Higher resource availability in the tropics supports higher population density and hence more total mutations per unit time.

Seasonality: speciation [START_REF] Ghalambor | Are mountain passes higher in the tropics? Janzen's hypothesis revisited[END_REF][START_REF] Sheldon | Fifty years of mountain passes: a perspective on Dan Janzen's classic article[END_REF] Seasonality and topographic relief

No assumption about equilibrium Mountain passes are "higher" in the less seasonal tropics leading to greater isolation and allopatric speciation.

Biotic interactions [START_REF] Schemske | Is There a Latitudinal Gradient in the Importance of Biotic Interactions?[END_REF][START_REF] Dobzhansky | Evolution in the tropics[END_REF] Resource availability and environmental stability

No assumption about equilibrium Stronger biotic interactions (e.g. competition and predation) among species in the more stable tropics increase speciation rates. Key processes across levels of biological organization. Illustration of our framework spanning external drivers that are associated with the spatiotemporal environment, the ecoevolutionary processes that are thought to be central to the LDG, and the emergent diagnostic patterns. We consider four key eco-evolutionary processes: selection, dispersal, ecological drift (eventually resulting in extinction), and speciation [START_REF] Vellend | The Community of Ecological Communities[END_REF]; they are shown relative to spatial, temporal, and biological scales (e.g. local vs. regional, population-level vs. continentlevel). Five example hypotheses from the three categories of LDG hypotheses are mapped onto this framework with their specific drivers, processes and emergent patterns (hypothesis names and categories as in Table 1). For each hypothesis, we show only the primary driverprocess pathway identified in Table 1 (see main text for more detailed explanation of the mapped examples).

Figure I (in Box 1)

An example of an eco-evolutionary simulation model in an LDG context. A) Process classes suggested for any eco-evolutionary model of the LDG. Text inside each wedge describes how the process was modeled in [START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF] and [START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF]. B) A flowchart outlining the processes in [START_REF] Hurlbert | When should species richness be energy limited, and how would we know?[END_REF] and [START_REF] Hurlbert | On the processes generating latitudinal richness gradients: identifying diagnostic patterns and predictions[END_REF], with model components colored as in (A).

52, 60 ]

 60 must incorporate several fundamental processes (Figure I.A). Hurlbert and Stegen [16, 25] provide one example of such an eco-evolutionary simulation model in an LDG context (Figure I.B). In the model, species have different thermal optima (initially assigned randomly,

  alternative parameterizations and model structures. Starting from a set of alternative model formulations (Box 1, Figure I.A), we can compare the patterns produced by the model alternatives to observed patterns (Box 1, Figure I.B). The alternative model formulations may correspond to particular hypotheses, as shown in the figure, or to different parts of parameter space independent of existing hypotheses. The fit to the different patterns can be combined and weighted, or assessed independently, to identify the support for the different alternatives, or specific model inadequacies that need to be addressed (Box 1, Figure I.C).

Mechanistic macroecology :

 macroecology The study of mechanisms describing how individual organisms interact with their biotic and abiotic environments, and how these mechanisms scale up to result in macroecological patterns, including the LDG and other secondary biodiversity patterns. Mechanistic model: Mechanistic models may vary in complexity and detail, but in the context of the LDG, such a model should at a minimum specify the mechanisms by which the processes of selection, dispersal, ecological drift, and speciation operate on individuals, populations, or species. Niche conservatism: the tendency for descendant lineages or species to retain their ancestral niche. Pattern-oriented modeling: a modeling approach where multiple patterns observed in real systems at different hierarchical levels and scales are used systematically to optimize model complexity and to reduce uncertainty.

  dynamics at equilibrium due to competition Larger area or total resource amount in the tropics can support more individuals, determining the maximum number of viable populations and therefore species.Primary: Kt > Kn Secondary:

  equilibrium; trade-off More stable tropical habitats decrease stochastic extinction and select for competitive ability over

  environments Older tropical environments allow more time for more clades to originate or colonize. Primary: tt > tn Secondary: λt > λn

Figure 1 (

 1 Figure 1 (in main text)

  (C) Example simulation output displaying species richness along a spatial gradient, the distribution of species' thermal trait optima at three locations along the spatial gradient (dotted vertical lines indicate the actual temperature in those regions), and a phylogeny with branch color denoting speciation rate estimates (from low blue to high red values) from BAMM [85]. (D) Diagnostic model outputs for three different LDG hypotheses. NC -niche conservatism; EL -ecological limits; DR -diversification rates (see Table 1 for details). Patterns shown are: upper panel, temporal variation of the correlation between species richness in a region and time since the region was colonized (simulations with tropical clade origin in red, temperate clade origin in blue); lower panel, phylogenies color-coded by instantaneous speciation rate as in (C).

Figure I (in Box 2 )

 2 Figure I (in Box 2)

Figure I (in Box 3 )Figure 1 (

 31 Figure I (inBox 3)

Acknowledgments

This paper is an outcome of the sELDiG working group kindly supported by sDiv, the Synthesis Centre of the German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig (DFG FZT 118). SH thanks the Alexander von Humboldt Foundation for funding support through a postdoctoral fellowship; SAF was funded by the German Research Foundation (DFG FR 3246/2-1). DS was supported by the Czech Science Foundation (grant no. 16-26369S).

Simulation model: a set of rules (usually formulated in a programming language) governing the dynamics of artificial entities that reflect individuals, populations, or communities.