Satyanad Kichenassamy
email: kichenas@mis.mpg.de.

Instability of pole singularities for the Chazy equation

Keywords: numbers: 02, 30, Hq To appear in: The Chazy equation

We prove that the negative resonances of the Chazy equation (in the sense of Painlevé analysis) can be related directly to its group-invariance properties. These resonances indicate in this case the instability of pole singularities. Depending on the value of a parameter in the equation, an unstable isolated pole may turn into the familiar natural boundary, or split into several isolated singularities. In the first case, a convergent series representation involving exponentially small corrections can be given. This reconciles several earlier approaches to the interpretation of negative resonances. On the other hand, we also prove that pole singularities with the maximum number of positive resonances are stable. The proofs rely on general properties of nonlinear Fuchsian equations.

Introduction

The method of pole expansions is a versatile tool for the investigation of singularities of ODE and PDE. Going as far back as the work of Briot and Bouquet, and Kowalewska, this method acquired new significance when it was found that symmetry reductions of equations integrable by inverse scattering usually have the Painlevé property in the strong sense: all of their movable singularities are described by the method of pole expansions [START_REF] Ablowitz | Exact linearization of a Painlevé transcendent[END_REF][START_REF] Ablowitz | A connection between nonlinear evolution equations and ordinary differential equations of P-type, I[END_REF]. Conversely the inverse scattering transform suggested new approaches to the study of the Painlevé equations themselves.

We are interested in the case of the Chazy equation

y ′′′ -2yy ′′ + 3y ′2 = 0, (1)
where this method apparently fails to provide information on the general solution of the equation under consideration, because the pole expansion has fewer free parameters than the order of the equation, and therefore does not seem to represent the general solution. The simplest issue is this: the Chazy equation has order three and possesses the exact solution -6/x.

However, this is, up to translations, the only solution with a simple pole. The 'pole expansion' reduces in this case to its first term. This solution should be embedded in a three-parameter family of solutions: the fact that there is only a one-parameter family of solutions with simple poles shows that simple poles are unstable under perturbation, but does not give further information. (More background information on the Chazy equation is given in section 1.3 below.) Kruskal (see [START_REF] Kruskal | Analytic and asymptotic methods for nonlinear singularity analysis, a review and extension of tests for the Painlevé property[END_REF]) suggested that the failure of the pole expansion was due to the omission of exponentially small terms in the expansion of the general solution y(x). Furthermore, this representation should not be valid in a full neighborhood of x = 0 in general, but only in a sector, as in the case of expansions near an irregular singular point. It turns out in this case that the expansion in powers of exponentials is convergent, which is not expected at an irregular singularity. On the other hand, the perturbative approach [START_REF] Fordy | Analysing negative resonances in the Painlevé test[END_REF][START_REF] Conte | A perturbative Painlevé approach to nonlinear differential equations[END_REF], shows that there is a formal series solution y(x; ε) = y(x) + εy 1 (x) + . . ., which does contain the full number of arbitrary parameters. Also, the perturbative approach accounts for the apparent paradox that the solutions of the linearized equation have solutions which are more singular than any actual solution of the equation: they are related to the variation of free parameters in the general solution, at a fixed location away from the singularity. However, all of the terms in the expansion in powers of ε have only power singularities, and do not contain exponential terms. There is also no indication that the actual solution cannot be continued around the singularity.

Another difficulty comes from the general 'class XII' equation of Chazy:

y ′′′ -2yy ′′ + 3y ′2 = E(6y ′ -y 2 ) 2 , (2)
where E = 4/(36 -k 2 ), with k ≥ 0, omitting the 'complementary terms.' This equation has the same special solution, but the general solution can be completely different, and is in fact rational for some values of k. It is possible for the simple pole to split into two or more poles by perturbation. This effect cannot be captured adequately in a series representation in powers of x: take a solution with two poles at x = 0 and x = α. The radius of convergence of a pole expansion around x = 0 cannot be greater than |α|, and therefore tends to zero if there is a confluence of the two singularities (α → 0). The perturbative approach can correctly describe what happens at a fixed location away from the singularities, but its asymptotics as x → 0 do not describe the singularity correctly. This can be seen in the treatment of the first example of section 5 in [START_REF] Conte | A perturbative Painlevé approach to nonlinear differential equations[END_REF] where the confluence can only be ascertained by explicitly summing the pole expansion. We address these difficulties as follows:

(i) In considering the perturbative solution y(x; ε), it is not permissible to exchange the limits x → 0 and ε → 0. This explains why no exponential terms are generated there.

(ii) To recover the results of the perturbative approach from the exponential expansion, it is necessary to vary the free parameters in a very particular way, which we relate to the group invariance of the Chazy equation.

(iii) It is possible to describe confluence phenomena analytically by means of a Cole-Hopf transformation: if u(x; ε) is an analytic family of functions where a pair of simple zeros coalesces at x = 0, the family u ′ /u has a confluence of poles. Note that we can allow u to be analytic in both arguments, whereas the pole expansion of u ′ /u would have a vanishingly small radius of convergence, as explained above.

It is convenient to describe all of the above issues as relating to the stability of singular behavior, because of the close similarity to the stability of solitary waves in nonlinear wave equations. Note that some authors (in particular Bureau) define a 'stable equation' as one which possesses the Painlevé property. We are interested in a different issue, namely whether the leading asymptotics of a particular solution of an ODE or PDE are stable under perturbation of the solution. Consider for instance real-valued solutions of the equation

u tt -u xx -u yy = e u ,
which has the special solution e u = 2/t 2 ; then [START_REF] Kichenassamy | The blow-up problem for exponential nonlinearities[END_REF] all nearby solutions are such that e u has an expansion in powers of T and T ln T , where T = t -ψ(x, y), with ψ small, and the first term is ln(2/T 2 ). It is not possible to exclude logarithms in general, but the leading order of the singularity remains the same. The singularity of the solution ln(2/t 2 ) would be termed 'stable' in the sense of the present paper.

The main technical tool in the proofs of our results is the Fuchsian algorithm ([20, 24] and earlier references therein). The basic step is to show that the method of pole expansions for ODE or PDE amounts to seeking solutions of a nonlinear ordinary or partial differential equation with a regular singularity, which may include logarithmic terms. As far as the present discussion is concerned, note that several authors (in particular, Bureau, see also Conte, Fordy and Pickering [START_REF] Conte | A perturbative Painlevé approach to nonlinear differential equations[END_REF]) have identified ARS-WTC resonances with the indices of a linear Fuchsian ODE, and have observed in many cases that the linearization of the equation itself is Fuchsian. On the other hand, we have shown, see e.g. [START_REF] Kichenassamy | The structure of WTC expansions and applications[END_REF], that under very general circumstances, the equation itself can be reduced to a nonlinear Fuchsian ODE or PDE, without linearizing. We have also shown that the initial-value problem for Fuchsian PDE can be solved in both the analytic and non-analytic cases. The Chazy equation itself can be reduced to Fuchsian form in several different ways, see the proofs of theorems 7 and 8. The Fuchsian algorithm is not restricted to 'integrable' problems, but is in fact useful in analyzing singularity formation in more general nonlinear wave equations, see [START_REF] Kichenassamy | The blow-up problem for exponential nonlinearities[END_REF][START_REF] Kichenassamy | WTC expansions and non-integrable equations[END_REF][START_REF] Kichenassamy | Analytic description of singularities in Gowdy spacetimes[END_REF]. Of course, in the linear case, none of the above issues arises: if a linear equation has solutions with leading order x ν 1 , x ν 2 ,. . . , the general solution is simply a linear combination of these, and its singular behavior is apparent. Confluence of singularities of linear Fuchsian equations involves varying the coefficients of the equation, rather than perturbing one solution of a fixed equation.

The method of pole expansions

The principle of the method is familiar: given an equation, substitute for the unknown u a series of the form:

u = x ν j≥0 u j x j , (3)
and identify like powers of x. This determines first ν and u 0 , hence the leading balance u ∼ u 0 x ν . The other coefficients are usually determined by a recurrence relation of the form

Q(j)u j = F j (u 0 , . . . , u j-1 ). ( 4
)
The zeros of Q are called resonances.

When Q(j) = 0 and F j also vanishes, the coefficient u j is arbitrary. If Q(j) = 0 but F j does not vanish, the series (3) must be corrected by the addition of logarithmic terms, and one can predict their form rather precisely [START_REF] Kichenassamy | The structure of WTC expansions and applications[END_REF]. The requirement that no logarithmic terms are needed sets rather strong constraints on the equation; this observation was one of the ingredients of the 'Painlevé test' in its original form, because many symmetry reductions of integrable equations do have this property. We do not discuss the modern status of this test, referring the reader to recent reviews [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF][START_REF] Clarkson | The Painlevé-Kowalewski and poly-Painlevé tests for integrability[END_REF][START_REF] Kichenassamy | Nonlinear Wave Equations[END_REF][START_REF] Kruskal | Analytic and asymptotic methods for nonlinear singularity analysis, a review and extension of tests for the Painlevé property[END_REF] and their references. The method can be extended to partial differential equations, in which case it is known as the WTC method [START_REF] Weiss | The Painlevé property for partial differential equations[END_REF][START_REF] Kichenassamy | The structure of WTC expansions and applications[END_REF].

Therefore, as far as this paper is concerned, the upshot is that singularities of the form (3) are expected to be stable under perturbations, in the sense defined below, provided that the series (3) has the maximum number of arbitrary constants in it: any nearby solution must have a singularity of the same type, with a possible shift in location.

Stability of singular behavior

The stability of a singular solution will be defined by analogy with the case of orbital stability of solitary waves in translation-invariant problems: a solitary wave u is (orbitally) stable if any perturbation of the initial condition for a solitary wave generates a solution which remains close to the orbit of u under translations. Thus, in the case of the Korteweg-de Vries (KdV) equation, an initial condition close to a one-soliton leads to a solution which remains close to the set of all translates of this soliton (see Strauss [START_REF] Strauss | Nonlinear Wave Equations[END_REF][START_REF] Strauss | Stability, instability and regularity of nonlinear waves[END_REF], Bona, Souganidis and Strauss [START_REF] Bona | Stability and instability of solitary waves of KdV type[END_REF] for the KdV case, and their references; further results for KdV-like equations are also found in [START_REF] Pego | On asymptotic stability of solitary waves[END_REF]).

We encounter a comparable situation for movable singularities of differential equations: if an equation is translation-invariant, we expect that a small perturbation of any solution, in a domain away from the singularity, will in general result in a shift in the singularity location. This should be distinguished from a possible change in the type of singularity.

As an example with a simple closed-form solution, consider the equation

du/dx = 2xu 2 ,
and let us focus on real solutions to fix ideas; a similar discussion could be made for complex solutions as well. The general solution is

u(x) = 1 c -x 2 ,
where c is a real constant, and consider small values of c. If c is positive, we have two stable single poles: a slight change in the value of, say, u(1) = 1/(c -1), results in a small change in the value of c, hence a small shift of the pole. However, if c = 0, we obtain an unstable double pole for x = 0, because a small change in the value of u(1) causes the pole either to disappear, or to break up into two simple poles, depending on whether c becomes negative or positive.

In the Chazy case, we will be interested in the stability of exact solutions of the form a/x in some fixed disk D around the origin. Fix also some nonzero value ξ in D. We will say that the singularity is stable if any solution with Cauchy data at ξ close to those of a/x, must have an expansion

a/(x -x 0 ) + j≥0 u j (x -x 0 ) j valid in D.
We could allow logarithmic terms in the series, but they will not be needed. We therefore require a simple pole to perturb to another simple pole. An example of an unstable situation would be the case in which a small change in the data at ξ causes the pole to turn into a natural boundary, or to split into several poles.

The Chazy equation

We recall here some background information on eq. ( 1). The Chazy equation came up in the course of Chazy's extension of Painlevé's program to third-order equations [START_REF] Chazy | Sur les équations différentielles dont l'intégrale génerale est uniforme et admet des singularités essentielles mobiles[END_REF][START_REF] Chazy | Sur les équations différentielles dont l'intégrale génerale possède une coupure essentielle mobile[END_REF][START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF]. It is actually one of the 'class XII' equations [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF]. It is closely related to a system considered by Halphen, and its general solution can be parametrized using the solutions of a hypergeometric equation if k > 0, and the Airy equation if k = 0 (see Clarkson and Olver [START_REF] Clarkson | Symmetry and the Chazy equation[END_REF], Ablowitz and Clarkson [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF], and their references).

The modern interest in this equation comes from the fact that it arises as a reduction of self-dual Yang-Mills equations with an infinite-dimensional gauge group [START_REF] Ablowitz | Reductions of self-dual Yang-Mills fields and classical systems[END_REF][START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF][START_REF] Takhtajan | A simple example of modular forms as tau-functions for integrable equations[END_REF]. It arises in connection with one of the special reductions of Einstein's equations in a Bianchi IX space-time. It can be given a commutator representation. A particular solution is 1 2

d dx ln ∆(x),
where ∆(x) is the discriminant modular form (see Takhtajan [START_REF] Takhtajan | A simple example of modular forms as tau-functions for integrable equations[END_REF], Bureau [START_REF] Bureau | Integration of some nonlinear systems of differential equations[END_REF][START_REF] Bureau | Sur des systèmes non linéaires du troisième ordre et les équations différentielles associées[END_REF], and Chazy [START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF] for the relation to modular forms, and Koblitz [START_REF] Koblitz | Introduction to Elliptic Curves and Modular Forms[END_REF] for background material on modular forms). This solution has the real axis as a natural boundary. It generates a three-parameter family of solutions through an SL(2) action which maps solutions to solutions: more precisely, if y(x) is a solution, so is

ad -bc (cx + d) 2 y( ax + b cx + d ) - 6c cx + d (5)
for any choice of the complex parameters a, b, c and d, subject to ad -bc = 0. There are effectively only three parameters, since scaling the parameters by a common factor does not generate a new solution. The transformed solution has, in general, a circular natural boundary. The relation of the Chazy equation to the Schwarzian derivative and invariants of SL(2) actions was elucidated by Clarkson and Olver [START_REF] Clarkson | Symmetry and the Chazy equation[END_REF], who showed how to use the group action to obtain the general solution, despite the fact that the symmetry group is not solvable.

On the other hand, the method of pole expansions generates exact solutions which have no natural boundary at all, namely

- 6 x -x 0 + A (x -x 0 ) 2 ,
where A is arbitrary. This is a two-parameter deformation of the solution -6/x.

The problem is to decide the stability of the solution -6/x.

A similar problem arises for the general class XII equation, for which we have the solutions [START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF][START_REF] Sidorevich | A nonlinear third order differential equation[END_REF]:

k -6 2(x -a) - k + 6 2(x -b) ,
where a and b are arbitrary. One recovers the solution -6/x by confluence of a and b.

The resonances corresponding to the singularities a and b are (-1, 1, k) and (-k, -1, 1) respectively.

Earlier approaches

1. Linearization. The method of Fordy and Pickering [START_REF] Fordy | Analysing negative resonances in the Painlevé test[END_REF] considers perturbations of the solution -6/x of the form

- 6 x + εu 1 (x) + ε 2 u 2 (x) + . . . (6)
and shows that one can compute the u k recursively by solving linear equations involving the linearization of the Chazy equation at the reference solution -6/x. This linearization reads

(D + 2)(D + 3)(D + 4)v = 0,
where D = xd/dx, and the corrections are sums of increasingly high powers of 1/x and x.

The advantage of this method is that the new series does contain three arbitrary parameters, which can be identified with the three parameters required to describe the general solution of the linearized equation.

The solutions of the linearization are more singular than -6/x, but this does not mean that the equation itself has more singular solutions: for example, we have

- 6 x -ε = - 6 x (1 + ε/x + ε 2 /x 2 + . . .).
Since the series converges only for |x| > ε, the series does not provide information on the behavior of this solution as x approaches zero. In fact, x = 0 is a regular point for ε = 0. Similarly, the series ( 6) is not expected to converge for x and ε small without any further restriction, since this would predict that pole singularities perturb to Laurent expansions defined in a full neighborhood of x = 0, and such expansions do not allow for the formation of a small natural boundary near the origin.

2. Exponentially small corrections. Kruskal considered the general solution as a perturbation of the solution -6/x + A/x 2 . In this case, the linearized equation reads

(x(D + 4) -2A)(D + 2)(D + 3)v = 0,
where again D = xd/dx, and has therefore an exponential solution which involves exp(-2A/x). The appearance of non-Fuchsian terms was to be expected from the fact that the leading balance, for a second-order pole, does not involve the top-order derivatives. He derived systematically a representation of the general solution in the form

- 6 x + A x 2 (1 + k exp(-2A/x) + . . .),
which, after including a parameter for translations, contains three parameters, but is defined at best in a sector in which the exponential is small. This sector has maximal angle π, and this restriction corresponds to the fact that the solution cannot be continued around the singularity at x = 0 in general, but has a natural boundary which is a circle (or a line) through x = 0. This representation can be checked directly in this special case using the general solution [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF]. One can see by inspection that as A approaches zero, the natural boundary is a small circle which shrinks to a point. However, it is not clear how to account for resonance -3 in this context, even though the solution thus obtained does contain three arbitrary parameters. Indeed, if we differentiate the expansion with respect to A or k and set A = 0, we cannot generate a function with a fourth-order pole at the origin, as was possible in the linearization approach. As we will see, it is possible to recover the fourth-order pole by using a simultaneous variation of all three parameters.

Remarks.

Two other approaches to the interpretation of missing parameters in pole expansions are as follows.

(1) The fact that some equations have two Painlevé series with leading orders of the form a/x and na/x where n is an integer suggests that the second series results from the confluence of n singularities of the first type (see Adler and van Moerbeke [5], Ercolani and Siggia [START_REF] Ercolani | The Painlevé property and integrability[END_REF], Flaschka et al., [START_REF] Flaschka | Integrability[END_REF], among others). However, as noted above, it remained difficult to obtain an analytical representation of confluence, because the pole expansion near one of the singularities has a shrinking radius of convergence.

(2) It is possible to seek solutions in powers of s = 1/x rather than x. In that case, negative resonances become positive resonances of the equation in the s variable. Such a series already appears in Chazy [START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF]. However, this solution is only defined for x large, and there may be one or more natural boundaries which separate the domain of existence of this solution from the origin. Also, this interpretation is not applicable if there are both positive and negative resonances.

Results of this paper

The necessary reconciliation of the linearization and exponential approaches, for equations ( 1) and ( 2) for k = 2, 3, 4, 5, is obtained through the results below.

a. (Theorems 1 and 9) Pole expansions with the maximum number of arbitrary parameters represent stable singularities. This applies to the solution (k -6)/2x.

b. (Theorems 2-4) Any equation with the group invariance property of the equation ( 5) has a one-parameter family of solutions y(x; ε) such that

y(x; 0) = - 6 x ; ∂y ∂ε (x; 0) = const. x -1+r
for each negative resonance r (i.e., for r = -1, -2 or -3). The perturbative expansion follows. This argument applies to both (1) and (2). c. (Theorem 5) Conversely, if an equation has the solution -6/x, it cannot have the SL(2) action ( 5) if the resonances do not include -1, -2 and -3. The existence of a full expansion of y(x; ε) also follows from our proof.

d. (Theorem 6) If there is a solution with branching involving x k , the group invariance proves the existence of pole-like singularities with resonances -1 and -k.

e. (Theorem 7) In the case of (1), as ε increases from zero, the isolated pole is unstable and goes into a circular natural boundary of small radius. However, the general solution is still described in terms of a convergent series of exponentials; this follows from the fact that even though the linearization of the equation can be non-Fuchsian, there still is a reduction to a nonlinear Fuchsian equation.

f. (Theorem 8) In the case of (2), for k = 2, 3, 4 and 5, the isolated pole does not turn into a natural boundary, but rather splits into a finite number of poles. However, the confluence pattern is restricted: all poles except one at most must coalesce. If all confluence patterns had been allowed, the resonances of the solution -(k + 6)/2x would have included all the negative integers from -k to -1. The confluence is described analytically by representing the solution in terms of u ′ /u, where u is analytic in a fixed domain which includes both coalescing singularities. This paper was motivated by M. D. Kruskal's questions on the relation between the nonlinear Fuchsian approach to WTC expansion in [START_REF] Kichenassamy | The structure of WTC expansions and applications[END_REF][START_REF] Kichenassamy | Nonlinear Wave Equations[END_REF], and the problem of negative resonances. I am also grateful to him for sharing with me his own results on this problem.

Nonlinear Fuchsian equations

We collect here a few results on Fuchsian equations which are used later. We also include a proof of the stability of polar singularities with the maximum number of arbitrary coefficients in their expansion (3), which is similar in spirit to, but considerably simpler than the result of [START_REF] Kichenassamy | The blow-up problem for exponential nonlinearities[END_REF], because of the fact that we are dealing here with an ODE rather than a PDE.

Existence results for Fuchsian ODE

A nonlinear Fuchsian equation has the general form

P (D)u(x) = xF [x, u, Du, . . . , D m-1 u], (7)
where D = xd/dx, and P is a polynomial of degree m. There are similar definitions and results for systems, but they will not be needed here.

If the zeros of P all have negative real parts, there is precisely one solution of this equation which vanishes for x = 0, and it is given by a convergent series in powers of x near x = 0. The proof is by iteration in a space of analytic functions, and is in this sense constructive. In particular, it could in principle be used to generate the coefficients of the expansion of the solution, but it is in practice quite cumbersome to do so.

The convergence of WTC expansions follows from the fact (see [START_REF] Kichenassamy | Nonlinear Wave Equations[END_REF]) that it is possible to allow u to depend on additional 'transverse' variables, provided that spatial derivatives terms are multiplied by appropriate powers of t, see [START_REF] Kichenassamy | WTC expansions and non-integrable equations[END_REF][START_REF] Kichenassamy | The structure of WTC expansions and applications[END_REF]. This condition is satisfied in a remarkably large number of cases.

We will meet in section 3 an equation of the form

P (D)Du = xF, (8)
where P and F are as above. To reduce this situation to the the case of ( 7), let us write u = a + xv(x), where a is arbitrary. One can write

xF = xF [0, a, 0, . . .] + x 2 G[x, v, Dv, . . . , D m-1 v],
for some function G. The equation now becomes, after division by x,

Q(D)v := P (D + 1)(D + 1)v = F [0, a, 0, . . .] + xG,
where the zeros of Q all have negative real parts. We now replace v by v -b, for a suitable constant b, to annihilate the first term on the right-hand side. In this way, we reduced the problem to an equation of the form [START_REF] Bureau | Integration of some nonlinear systems of differential equations[END_REF], and we conclude that there is a unique solution v which vanishes at the origin. Therefore, for any a, there is a unique analytic solution of (8) which satisfies u(0) = a.

Stability and parameter dependence

We now prove a stability result for pole singularities of an equation with the maximum number of coefficients in their pole expansions. This result makes rigorous the intuitive argument to the effect that a series which contains as many free parameters as there are Cauchy data must represent the general solution locally.

To prove the result, one must show that these parameters are not redundant. We achieve this by a reduction to the implicit function theorem. An example of a redundant parametrization is the two-parameter family of series:

u(x; ε, η) = j≥0 η j (x -ε) j+1 . ( 9
)
The parameters ε and η are redundant, because u(x; ε, η) = 1/(x -ε -η): the pairs (ε, η) with the same value of ε + η all define the same function.

To fix ideas, let us consider an autonomous equation of the form

(d/dx) m u = f (u, . . . , u (m-1) ), (10)
where f is, say, a polynomial. Let u(x -x 0 , c 1 , . . . , c m-1 ) be a family of solutions, which depends analytically on (x 0 , c 1 , . . . , c m-1 ) for |x 0 | and |c k | < a and 0 < |x -x 0 | < b, for some positive a and b. We have the following result: Theorem 1. Assume that ∂u/∂x 0 , ∂u/∂c 1 ,. . . , ∂u/∂c m-1 form a linearly independent set of solutions of the linearization of [START_REF] Chazy | Sur les équations différentielles dont l'intégrale génerale est uniforme et admet des singularités essentielles mobiles[END_REF]. Then u(x -x 0 , c 1 , . . . , c m-1 ) is a local representation of the general solution. In particular, the assumption holds for any pole expansion with the maximum number of parameters if ν = 0.

Remarks: (1) If ν = 0, we are in the case of the Cauchy problem, and the series for the solution contains m + 1 parameters, namely the location of the initial point and the m Cauchy data. These data are clearly redundant.

(2) In the case of ( 9), the representation is redundant because ∂u/∂ε = ∂u/∂η.

Proof: Consider the reference solution U = u(x, 0, . . . , 0) for definiteness. Given any point x 1 with 0 < |x 1 | < b, we consider ϕ : (x 0 , c 1 , . . . , c m-1 ) → (u(x 1 ), u ′ (x 1 ), . . . , u (m-1) (x 1 )), where u(x 1 ) = u(x 1 -x 0 , c 1 , . . . , c m-1 ), and similarly for the derivatives of u. Applying the inverse function theorem to this map near (x 0 , 0, . . . , 0), we conclude that any set of Cauchy data close to the data of U at x 1 coincides with the Cauchy data of a member of our family, QED.

To prove that the linear independence condition holds in the context of the theorem, it suffices to consider the family u(x -x 0 , c 1 , . . . , c m-1 ), where the c l 's are the arbitrary coefficients in the expansion of u. The functions ∂u/∂x 0 , ∂u/∂c l are derivatives of families of solutions, and are therefore themselves solutions of the linearized equation. It is easy to see that these derivatives all have different leading behaviors at x = x 0 , and are therefore linearly independent, QED.

The transformation formula and negative resonances

Statement of results

Consider any equation which admits the transformation formula (5). Assume that any uniform limit of analytic solutions is also a solution. This assumption is clear for ODEs; it will allow us to extend (5) to some cases when the transformation (ax + b)/(cx + d) is non-invertible, by viewing it as a limit of invertible transformations.

Let y(x) be any solution. We wish to prove that there are families of solutions y(x; ε, r) such that y(x; 0, r) = -6/x and dy dε (x; 0, r) = x -1+r

for r = -1, -2 and -3. This will account for the three 'negative resonances.' It will be apparent from the proofs that y(x; ε; r) can in fact be expanded to higher order, and that the coefficients of the higher-order terms are increasingly more singular in x.

We find that the construction is possible provided that it is possible to prescribe y, y ′ , y ′′ arbitrarily at one point. This construction precisely fails for the non-generic solutions -6/x + A/x 2 . The fact that the resonance structure can be derived on the sole basis of the representation formula implies conversely that if we have an equation with a different resonance structure, it cannot admit the transformation formula (5).

Fix a solution y(x) which is analytic near x = 0. Consider the family

y(x; ε) = - 6 x -η + µ (x -η) 2 y( -µ x -η ), (11)
where η and µ depend on ε, and are assumed to be small as ε → 0. This is a special case of the transformation (5).

Our results are as follows.

Theorem 2. If µy(0) -6η = ε, and µ and η are proportional to ε, y(x; 0) = -6/x and dy dε (x; 0) = 1/x 2 .

Theorem 3. Assume µy(0) -6η = 0, but 6y ′ (0) -y(0) 2 = 0. Then, if µ and η are both proportional to ε 1/2 , we have y(x; 0) = -6/x and dy dε (x; 0) = c/x 3 , where c = 0.

Theorem 4. Assume µy(0) -6η = 0 and 6y ′ (0) -y(0) 2 = 0, but y ′′ -yy ′ + y 3 /9 = 0 when x = 0. Then, if µ and η are both proportional to ε 1/3 , we have y(x; 0) = -6/x and dy dε

(x; 0) = c/x 4 ,
where c = 0.

Theorem 5. If an equation of order three or higher, to which the Cauchy existence theorem applies, admits the special solution y = -6/x, and if the linearization of the equation at this solution does not have 1/x 2 , 1/x 3 and 1/x 4 among its solutions, then the given equation cannot admit the SL(2) action ( 5).

The restriction that the solution y(x) be analytic is essential. In fact, we can obtain quite different results if y admits branching: Theorem 6. If there is a solution of the form y(x) = x -1 h(x k ), where h is analytic, k > 0, and h(0) = (k -6)/2, there exist two families of solutions, y 1 (x; ε) and y 2 (x; ε), such that

y 1 (x; 0) = y 2 (x; 0) = - k + 6 2x ,
and dy 1 dε (x; 0) = c/x 2 and dy 2 dε (x; 0) = c/x k+1 .

Remarks

1. If we take y = -6/(x -x 0 ), theorems 2 and 3 do not apply.

2. If we take y = -6/(x -x 0 ) + A/(x -x 0 ) 2 , theorem 3 applies, but theorem 4 does not. Indeed, in this case,

y ′ -y 2 /6 = -A 2 (x -x 0 ) -4 /6, (12)
and

y ′′ -yy ′ + y 3 /9 = (d/dx -(2/3)y)(y ′ -y 2 /6) = A 3 (x -x 0 ) -6 /9. (13)
It is therefore not possible to make (12) vanish without having A = 0-in which case (13) vanishes as well. One can rephrase the assumption in theorem 4 by saying that we require y ′ = y 2 /6 but y ′′ = y 3 /18, for x = 0. 3. Theorems 2, 3 and 4 all apply, for example, when there is a solution for every choice of y(0), y ′ (0) and y ′′ (0). The result therefore holds for any third-order autonomous equation, hence for both equations (1) and ( 2) which, as we show in section 4, have completely different singularity structures.

4.

It follows from theorem 8 below that theorem 6 applies to equations [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF]. A result similar to theorem 5 could of course be stated for this situation.

5. An example to illustrate theorem 5 is the equation

y ′′′ = 2yy ′′ -3y ′2 + cy ′ (6y ′ -y 2 )
which has the solution -6/x, but where the resonance equation is (r + 1)[(r + 2)(r + 3) -36c] = 0. -2 and -3 are therefore both resonances only if c = 0. We conclude, without computing the symmetry group of the equation, that this equation does not admit the transformation law ( 5) if c = 0.

Proofs

Let us begin with a computation which is used in the proofs of the first three theorems. Any solution y(x) generates the one-parameter family of solutions

y(x; ε) = - 6 x -η(ε) + µ(ε) (x -η(ε)) 2 y(- µ(ε) x -η(ε)
).

If x is fixed and nonzero, and if µ and η are small as ε → 0, we can expand this solution in the form

y(x; ε) = -6 x + µy -6η x 2 + µ(2ηy -µy ′ ) -6η 2 x 3 + x -4 [-6η 3 + µ(3η 2 y -3ηµy ′ + µ 2 2 y ′′ )] + O(η 4 , η 3 µ, η 2 µ 2 , ηµ 3 , µ 4 ),
where y, y ′ ,. . . stand for y(0), y ′ (0),. . . Any such family has the property that y(x; 0) = -6/x. Furthermore, it is clear that the above expansion could be pushed to all orders, and that the coefficients of the higher order terms contain higher and higher powers of 1/x.

Proof of Th. 2: If we take µ and η proportional to ε, in such a way that µy(0) -6η ∼ ε, we have ∂y/∂ε = 1/x 2 for ε = 0.

Proof of Th. 3: If we take µ and η proportional to ε 1/2 , in such a way that µy(0) -6η = 0, and if y is such that 6y ′ (0) = y(0) 2 , we have ∂y/∂ε = const./x 3 for ε = 0.

Proof of Th. 4: If we take µ and η proportional to ε, in such a way that µy(0) -6η = 0, and assume that 6y ′ (0) -y(0) 2 = 0, but y ′′ -yy ′ + y 3 /9 = 0 for x = 0, we find that ∂y/∂ε = const./x 4 for ε = 0. This proves theorems 2, 3 and 4. Proof of Th. 5: Consider an equation F [u] = 0 of order three or higher with such a group action. Solving the Cauchy problem, we can construct solutions to which each of theorems 1, 2 and 3 apply. Consequently, there are differentiable families of solutions y(x; ε) as in these theorems. Since F [y(x; ε)] is identically zero, we have

0 = d dε F [y(x; ε)] ε=0 = F ′ [-6/x]( dy dε (x; 0)),
where F ′ denotes the linearization of F . We conclude that this linearized equation must admit the three solutions 1/x m , m = 2, 3 and 4. If these three functions do not solve the linearization, there can be no such group action, QED.

The specific coefficients of the group action are not essential to the result: only the existence of an expansion of families of solutions matters.

Proof of Th. 6: The solution y(x) in the statement of the theorem is constructed in theorem 8.

From y, we construct the one-parameter family:

y 2 (x; ε) = - 6 x - 1 x h( ε x k ), using (5) for the inversion x → ε 1/k /x.
Letting ε → 0, we find that -(6 + h(0))/x = -(k + 6)/2x must be a solution. We now define

y 1 (x; ε) = - k + 6 x -ε .
The properties listed in the theorem are now readily verified.

Instability of isolated poles

Results

Even though the construction of the perturbation expansion of solutions close to -6/x can be made solely on the basis of the group action on solutions, the singularities which arise by perturbation of simple poles are different for ( 1) and ( 2). We know that perturbation series near a single pole do not allow an analytical description of confluence phenomena. However, even though a function such as (x -a) -1 + (x -b) -1 is not jointly analytic in x, a and b small, it is the logarithmic derivative of (x -a)(x -b) which is perfectly well-behaved. More generally, we show that a Cole-Hopf transformation provides an analytical description of confluence phenomena in the Chazy equation. More precisely, Theorem 7. For any constant a, equation (1) has precisely one solution of the form y(x) = u ′ /2u with u(x) = e x (1 + e x w(e x )), where w is analytic when its argument is small, and w(0) = a. Using transformations (5), this solution generates a one-parameter family of perturbations of -6/x, with a natural boundary shrinking to a point as the parameter vanishes. Their asymptotics at the boundary are those suggested by the method of exponential corrections.

For equation ( 2), we have Theorem 8. Let a be a constant. For k = 0 or 1, equation ( 2) has a unique solution of the form

y(x) = x -1 h(x k ),
where h is analytic when its argument is small, h(0) = (k -6)/2, and h ′ (0) = a. If k = 2, 3, 4 or 5, this solution is rational. Using transformations (5), this solution generates a one-parameter family of perturbations of -6/x, where all poles, except possibly one, cluster at the origin as the parameter vanishes.

Thus, -6/x is unstable; the next result shows that (k -6)/2x is stable, but -(k + 6)/2x is unstable: Theorem 9. For k = 2, 3, 4, 5, there is a three-parameter family of solutions of (2) which contains the solution (k -6)/2x. These parameters are in correspondence with the Cauchy data at a nearby regular point. Solutions with leading term -(k + 6)/2x on the other hand are unstable under perturbation: they arise from the confluence of all singularities save one.

Remarks

1. Since equation ( 14) below admits the discriminant modular form ∆ as a special solution [START_REF] Rankin | The construction of automorphic forms from the derivatives of a given form[END_REF], Theorem 7 provides a proof that ∆ is entirely determined by the first two terms of its expansion in powers of q = exp(2πix). Its reduction to Fuchsian form implies in particular a (perhaps new) recurrence relation on the coefficients of ∆, that is, on the Ramanujan τ function. On the other hand. our proof does not make use of any properties of modular forms, and therefore suggests that some of the phenomena found in the Chazy equation are of wider significance.

2. The existence of rational solutions and the observation that a Cole-Hopf transformation simplifies some of the issues is found in Chazy [START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF].

Proofs

For clarity, some tedious but straightforward computations have been omitted; we sometimes found it convenient to perform some of the verifications using a symbolic manipulation package.

Proof of Th. 7: Let y be a solution of [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF]. Let

y = u ′ 2u .
We find that u satisfies:

u 3 u (4) -5u 2 u ′ u (3) - 3 2 u 2 u ′′2 + 12uu ′2 u ′′ - 13 2 u ′4 = 0. ( 14
)
If u is a solution, so is

(cx + d) -12 u( ax + b cx + d ).
Since e x is an exact solution of this equation, we seek solutions of the form e x v(e x ).

Note that u = exp(2bx) leads to y = b, that is, to constant solutions of (1). We make change of variables z = e x , and let D := zd/dz = d/dx. This turns ( 14) into a Fuchsian equation for v(z) = u(z)/z:

v 3 (D + 1) 4 v -5v 2 (D + 1)v(D + 1) 3 v - 3 2 v 2 (D + 1) 2 v + 12v[(D + 1)v] 2 (D + 1) 2 v - 13 2 [(D + 1)v] 4 = 0.
Letting v(z) = 1 + zw(z), we find that w satisfies an equation of the form

(D + 1) 3 Dw = zG[z, w, Dw, D 2 w, D 3 w].
It follows that there is exactly one solution with w(0) = a, and that it is given by a convergent series in z near z = 0. Coming back to x, we have obtained a solution of the desired form, given by a series of exponentials which converges at least for Re x < -ρ for some finite ρ. We know in fact that ρ is equal to zero for the case u = ∆(ix). This completes the proof of the claims regarding the family of exponential solutions.

Next, let us take the case when the solution y has the real axis for a natural boundary, to fix ideas.

Consider the transformation (5) generated by x → εx/(x -iε), which maps the real axis to the circle (Γ ε ) of center ε/2 and radius ε. The solution y(x) generates the one-parameter family of solutions:

y(x; ε) = - 6 x -iε - iε 2 (x -iε) 2 y( εx x -iε ),
which are defined outside (Γ ε ). As ε → 0, we see that the natural boundary shrinks to a point, and that the solutions y(x; ε) converge, uniformly on any disk at positive distance from the origin, to the solution -6/x. However, the limits ε → 0 and x → 0 do not commute; in fact, y(x; ε) is not defined in a full neighborhood of x = 0 for all small values of ε.

This completes the proof of theorem 7. Proof of Th. 8: Let y be a solution of [START_REF] Ablowitz | Solitons, Nonlinear Evolution Equations, and Inverse Scattering[END_REF]. Let

y = k -6 2 u ′ u .
We find that u satisfies:

uu (4) -(k -2)u ′ u ′′′ + 3k(k -2) 2(k + 6) u ′′2 = 0. ( 15
)
If u is a solution, so is

(cx + d) 12/(6-k) u( ax + b cx + d ).
The first part of the theorem follows from general results on nonlinear Fuchsian equations. Let us seek y in the form Let us now focus on k = 2, 3, 4, 5. In each case, there is a polynomial solution of [START_REF] Ercolani | The Painlevé property and integrability[END_REF], which generates the desired solutions using the SL(2) action [START_REF] Chazy | Sur les équations différentielles du troisième ordre et d'ordre supérieur dont l'intégrale générale a ses points critiques fixes[END_REF]. In fact, we have with N = 1 + (k + 6)/(6 -k) = 12/(6 -k). Note that u is analytic near x = 0 even when the a j tend to zero. The relation between linearized solutions and possible confluence patterns is given by the following:

Lemma 10. If we can choose the pole locations such that a j = ε 1/m b j , where j b q j vanishes for q < m, but is nonzero if q = m, then y(x; ε) = -6 x + const. ε x 1+m (1 + o(1)). In other words, we have a resonance at -m. Since the possible pole locations are obtained by applying homographic transformations to the zeros of a fixed function, not all pole configurations are possible.

The lemma follows by direct computation.

If all the poles are equal to zero, we recover y = -6/x; if they are all zero except for one which we let tend to infinity, we obtain the solution -(k + 6)/x. If all poles but one are sent to infinity, we obtain the solution (k -6)/x. It is apparent that the first two solutions are unstable.

Let us now show that there cannot be any other type of confluence. Assume that there is a family of homographic transformations, depending on a parameter ε, under which two distinct poles a 1 and a 2 tend to zero while two other poles a 3 and a 4 remain fixed at nonzero (distinct) locations. We do not restrict the location of any additional poles. The anharmonic ratio of (a 1 , a 2 , a 3 , a 4 ) tends to 1. But it is also independent of ε; it is therefore identically equal to 1. This implies that a 1 = a 2 for all ε: a contradiction. Therefore, if there is such a confluence, all poles except one at most, must cluster at the same point.

Proof of Th. 9: The stability statements have already been proved in the course of the proof of the previous theorem. Since the solution (k -6)/2x has two positive resonances, namely 1 and k, we expect to be able to conclude using theorem 1. There are in fact no logarithms in the pole expansion, but this does not follow from theorem 7, which only generates a one-parameter solution corresponding to the resonance k: to generate the complete solution, we need to check that the resonance 1 is compatible. It is convenient to do so using the group action. More precisely, the solution y = x -1 h(x k ) generates the solutions

- 6ε 1 + εx + h(x k /(1 + εx) k ) x(1 + εx) ,
which contain the additional parameter ε. Adding the translation parameter, we obtain a three-parameter family to which theorem 1 applies; this completes the proof.

  y(x) = x -1 (a + bz + w(z)z 2 ), where z = x k , a = (k -6)/2 and b is arbitrary. Letting zd/dz = D, we find, after substitution into the equation and some algebra, that w satisfies an equation of the form(D + 1)(k(D + 2) + 1)(k(D + 2) -1)w = zF [z, w, Dw, D 2 w].It follows that there is precisely one solution of the form y = h(x k )/x if we specify h(0) = (k -6)/2 and h ′ (0) = b. This proves the first part of the theorem. If b = 0, we find w ≡ 0.

u

  = (x -a 1 ) . . . (x -a N )


Pierre Civit

Seth Gilbert

Vincent Gramoli

Rachid Guerraoui

Jovan Komatovic

Consensus Byzantin Responsable Optimal

Il est connu que la propriété d'accord du problème du consensus byzantin entre 𝑛 processus peut être violée dans un système non-synchrone si le nombre 𝑡 de processus défectueux dépasse 𝑡 0 = ⌈𝑛/3⌉ -1 [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]. Dans cet article, nous étudions le problème du consensus byzantin responsable (accountable) qui se doit de (i) résoudre le consensus byzantin dans le scénario optimiste où 𝑡 ≤ 𝑡 0 et (ii) de permettre aux processus corrects d'obtenir une preuve indéniable de culpabilité de 𝑡 0 + 1 processus fautifs dans le pire des cas, où des processus corrects sont en désaccord. Nous présentons ainsi ABC : une transformation simple mais efficace de tout protocole de consensus byzantin en une version responsable. ABC introduit un surcoût de (1) seulement deux tours de communication et 𝑂 (𝑛 2 ) bits échangés supplémentaires dans le scénario optimiste, et (2) trois tours de communication et 𝑂 (𝑛 3 ) bits échangés supplémentaires sinon. En appliquant notre transformation à un algorithme de consensus byzantin quadratique (il en existe et sont optimaux en complexité en bits échangés), le résultat obtenu est prouvé optimal.

Mots-clefs : responsabilité, détection, fautes Byzantines, incitatifs, systèmes distribués

Problem Description

Consensus problem [START_REF] Marshall | Reaching agreement in the presence of faults[END_REF] is one of the most studied problem in distributed computing. This task consists in having a set Ψ = {𝑃 1 , ..., 𝑃 𝑛 } of 𝑛 processes, communicating by exchanging messages through a non-synchronous † reliable point-to-point network, that have to agree on a common value. That is, every process 𝑖 proposes a value and eventually decides (at most once) a value s. t. the following properties hold: -(Liveness) Termination: Every correct process eventually decides. -(Safety) Agreement: All correct processes decide the same value. -(Safety) Validity: ‡ If all processes are correct and propose the same value, only that value can be decided by a correct process. It has been shown [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF] that no non-synchronous algorithm can ensure the conjunction of the aforementioned properties if the number 𝑡 of Byzantine processes (that can perform arbitrary faults, deviating from their prescribed protocols) exceeds the threshold 𝑡 0 = ⌈𝑛/3⌉ -1, even if an idealised PKI (digital signatures) is assumed, as we do, where each message sent by process 𝑝 is properly authenticated. Furthermore, it is impossible [START_REF] Civit | Polygraph: Accountable byzantine agreement[END_REF] to ensure a gracefully degraded version that would ensure (i) Safety and Liveness for 𝑡 ≤ 𝑡 0 and (ii) Safety only for 𝑡 > 𝑡 0 .

This limitation motivated researchers to investigate accountable variants of this problem [CGG21, SWN + 21] that consist in (1) solving consensus when 𝑡 ≤ 𝑡 0 , and (2) allowing all correct participants to eventually obtain undeniable proof of culpability against 𝑡 0 + 1 Byzantine processes in case of safety violation (𝑡 > 𝑡 0 ). This second property is slightly different from the completeness, ensured by Peer-Review [START_REF] Haeberlen | PeerReview: Practical accountability for distributed systems[END_REF], where every Byzantine process is eventually suspected forever by at least one correct process. We say that a set †. Non-synchronous systems include: asynchronous systems, where the bound on message delivery time does not exist, and partially synchronous systems [START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF], where the (potentially unknown) bound holds only eventually after a (potentially unknown) global stabilization time (GST).

‡. this property is often called weak validity w.r. S of properly authenticated messages sent by a process 𝑃 𝑖 is a proof of culpability of 𝑃 𝑖 if there does not exist an execution 𝑒 of the system where (1) 𝑃 𝑖 sends all the messages from the S set, and (2) 𝑃 𝑖 is correct.

Observe that a proof of culpability of a process contains messages signed by the process with its PKI private key. Indeed, the PKI private key of a correct process is never revealed Accountability in distributed systems is important since it discourages bad behavior. If malicious behavior is guaranteed to result in apprehension and punishment, malicious processes are much less likely to carry out an attack in the first place, thus strengthening the security of the system.

All previous works employed sophisticated mechanisms for obtaining accountability instead of treating the base consensus protocol as a "black box", thus obtaining simpler and more efficient accountable Byzantine consensus protocols. table 1 compares accountable Byzantine consensus protocols obtained by ABC with the existing alternatives. The metric used in table 1 is the communication complexity which is the maximum number of signed messages sent by all correct processes after GST combined across all executions of the system.

Algorithm 1 Intuition Behind Transformation

function 𝑝𝑟𝑜 𝑝𝑜𝑠𝑒(𝑣) do ⊲ bc is any Byzantine consensus protocol 𝑣 ′ ← bc.propose(𝑣) broadcast [CONFIRM, 𝑣 ′ ] wait for 𝑛 -𝑡 0 [CONFIRM, 𝑣 ′ ] return 𝑣 ′
The generic transformation ABC proposed by this paper owns its simplicity and efficiency to the observation that the composition presented in algorithm 1 solves the Byzantine consensus problem when 𝑡 ≤ 𝑡 0 . Indeed, if the number of faults does not exceed 𝑡 0 , all processes eventually broadcast and receive 𝑛 -𝑡 0 matching CON-FIRM messages. However, the important mechanism illustrated in algorithm 1 is that faulty processes must send conflicting CONFIRM messages in order to cause disagreement. Indeed, a disagreement between two correct processes 𝑃 𝑖 and 𝑃 𝑗 that would respectively decide 𝑣 𝑖 and 𝑣 𝑗 with 𝑣 𝑖 ≠ 𝑣 𝑗 , would imply the reception of 𝑛 -𝑡 0 [CONFIRM, 𝑣 𝑖 ] messages by 𝑃 𝑖 and 𝑛 -𝑡 0 [CONFIRM, 𝑣 𝑗 ] messages by 𝑃 𝑗 . So at least 2(𝑛 -𝑡 0 ) -𝑛 = 𝑡 0 + 1 Byzantine processes sent both [CONFIRM, 𝑣 𝑖 ] and [CONFIRM, 𝑣 𝑗 ]. Hence, whenever correct processes disagree, they only need to exchange received CONFIRM messages to obtain accountability in the form of 𝑡 0 + 1 pairs of conflicting signed CONFIRM messages with different values 𝑣 𝑖 and 𝑣 𝑗 from as many Byzantine processes. Indeed, a correct process never sends two conflicting CONFIRM messages since the original Byzantine consensus protocol allow him to decide at most only once.

Roadmap We devote remaining sections to our transformation. Specifically, we first introduce the novel accountable confirmer problem (section 2), the crucial building block of ABC. Then, we present ABC and state its correctness and complexity (section 3). Finally, we conclude the paper in section 4.

Accountable Confirmer

The accountable confirmer problem is a distributed problem defined among 𝑛 processes. The problem is associated with parameter 𝑡 0 = ⌈𝑛/3⌉ -1 emphasizing that some properties are ensured only if the number Formatting a submission for AlgoTel of faulty processes does not exceed 𝑡 0 . Accountable confirmer exposes the following interface: (1) request submit(𝑣) -a process submits value 𝑣; invoked at most once, (2) indication confirm(𝑣 ′ ) -a process confirms value 𝑣 ′ ; triggered at most once, and (3) indication detect(𝐹, proof ) -a process detects processes from the set 𝐹 such that proof represents a proof of culpability of all processes that belong to 𝐹; triggered at most once. The following properties are ensured: -Terminating Convergence: If the number of faulty processes does not exceed 𝑡 0 and all correct processes submit the same value, then that value is eventually confirmed by every correct process. -Agreement: If the number of faulty processes does not exceed 𝑡 0 , then no two correct processes confirm different values. -Validity: Value confirmed by a correct process was submitted by a correct process.

-Accountability: If two correct processes confirm different values, then every correct process eventually detects at least 𝑡 0 + 1 faulty processes and obtains a proof of culpability of all detected processes. Terminating convergence ensures that, if (1) the number of faults does not exceed 𝑡 0 , and (2) all correct processes submit the same value, then all correct processes eventually confirm that value § . Agreement stipulates that no two correct processes confirm different values if the system is not corrupted (even if submitted values of correct processes differ). Validity ensures that any confirmed value is submitted by a correct process. Finally, accountability ensures detection of 𝑡 0 + 1 faulty processes by every correct process whenever correct processes confirm different values.

Algorithm 2 ABC Transformation -Code For Process 𝑃 𝑖 1: Implements: Implementation We now give a naive and very informal implementation of the accountable confirmer problem that suffers from a 𝑂 (𝑛 3 ) complexity even when 𝑡 ≤ 𝑡 0 . An optimization obtaining a 𝑂 (𝑛 2 ) complexity when 𝑡 ≤ 𝑡 0 is available in long version of the paper [CGG + ]. ¶ .

Each process initially broadcasts the value it submitted in a SUBMIT message: the SUBMIT message contains the value signed with the PKI private key of the sender.

Once a process receives such a SUBMIT message, the process (1) checks whether the message is properly signed, (2) verifies the signature, and (3) checks whether the received value is equal to its submitted value. If all of these checks pass, the process stores the entire message with its signature. Once a process stores signatures from (at least) 𝑛 -𝑡 0 processes, the process combine the received signatures into a full certificate which is simply the concatenation of the submitted value and the 𝑛-𝑡 0 associated signatures. Then, the process confirms its submitted value and finally informs other processes about its confirmation by broadcasting the full certificate.

Finally, once a process receives two conflicting full certificates, the process obtains a proof of culpability of (at least) 𝑡 0 + 1 faulty processes, which ensures accountability.

Indeed, each full certificate contains 𝑛-𝑡 0 properly authenticated messages: every process whose message is in the two conflicting full certificates is faulty and these messages represent a proof of its misbehavior (recall that no faulty process ever obtains the PKI private key of a correct process).

This algorithm (resp. its optimization in [CGG + ]) solves the accountable confirmer problem with: §. Note that it is not guaranteed that any correct process eventually confirms a value if correct processes submit different values (even if the number of faulty processes does not exceed 𝑡 0 ).

¶. The optimization takes benefits from (𝑛 -𝑡 0 , 𝑛) threshold signature scheme where the cost of asynchronous distributed key generation (ADKG) is assumed to be amortized.

  instance ac 7: upon event ⟨abc, Propose | proposal⟩ do 8: trigger ⟨bc, Propose | proposal⟩ 9: upon event ⟨bc, Decide | decision⟩ do 10: trigger ⟨ac, Submit | decision⟩ 11: upon event ⟨ac, Confirm | confirmation⟩ do 12: trigger ⟨abc, Decide | confirmation⟩ 13: upon event ⟨ac, Detect | 𝐹, proof ⟩ do 14: trigger ⟨abc, Detect | 𝐹, proof ⟩

TABLE 1 :

 1 Overview of the main properties of existing accountable Byzantine consensus protocols. We consider worst-case communication complexities (after Global Stabilisation Time (GST)[START_REF] Dwork | Consensus in the presence of partial synchrony[END_REF]) in all columns. Worst-case communication complexity (after GST) of a Byzantine consensus protocol is bounded by the 𝑂 (𝑛 2 ) Dolev-Reischuk bound. The accountability threshold is the number of tolerated Byzantine processes to provide accountability.

	Base Consensus Protocol	Communication Complexity of the Base Consensus Protocol	Communication Complexity of the Accountable Variant in the Common Case	Accountability Threshold	Paper
	HotStuff [YMR + 19]	𝑂 (𝑛 3 )	𝑂 (𝑛 3 )	2𝑛/3	[SWN + 21]
	Binary DBFT [CGLR18]	𝑂 (𝑛 3 )	𝑂 (𝑛 4 )	𝑛	[CGG21]
	Multivalue DBFT [CGLR18]	𝑂 (𝑛 4 )	𝑂 (𝑛 4 )	𝑛	[CGG21]
	Any	𝑋	𝑋	𝑛	this paper

t. alternative properties like external validity or strong validity. The choice of such a validity property does not impact this work.

-𝑂 (𝑛 3 ) (resp. 𝑂 (𝑛 2 )) communication complexity in the common case, and -𝑂 (𝑛 3 ) communication complexity in the degraded case.

BC + Accountable Confirmer = ABC

We now define our ABC transformation (algorithm 2), the main contribution of our work. ABC is built on the observation that any Byzantine consensus protocol paired with accountable confirmer solves the accountable Byzantine consensus problem.

Theorem 1 algorithm 2 solves the accountable Byzantine consensus problem with 𝑂 (𝑛 2 ) additional bits of information exchanged when 𝑡 ≤ 𝑡 0 .

Finally, we note that ABC does not worsen the communication complexity of any Byzantine consensus protocol. It is well-known that any protocol that solves the Byzantine consensus problem incurs quadratic communication complexity due to the Dolev-Reischuk lower bound [START_REF] Dolev | Bounds on information exchange for byzantine agreement[END_REF]. Given the fact that accountable confirmer has quadratic communication complexity in the common case, every Byzantine consensus protocol retains its complexity after our transformation.

Corollary 1 Let Π be a Byzantine consensus protocol with the communication complexity 𝑋 Π . Let Π 𝐴 be a protocol obtained by applying ABC to Π. Then, Π 𝐴 solves the Byzantine consensus problem with the communication complexity 𝑋 Π .

Conclusion

We presented the first generic transformation to obtain optimal Accountable Byzantine Consensus. This transformation can naturally be applied to randomized consensus, reliable-broadcast and consistent-broadcast.