Mart Krupovic
email: krupovic@pasteur.fr

Valerian V Dolja

Eugene V Koonin
email: e.v.k.koonin@ncbi.nlm.nih.gov

Origin of viruses: primordial replicators recruiting capsids from hosts

Viruses are ubiquitous parasites of cellular life and the most abundant biological entities on earth. It is widely accepted that viruses are polyphyletic but a consensus scenario for their ultimate origin(s) is still lacking. Traditionally, three different scenarios have been considered for the origin of viruses: descent from primordial, pre-cellular genetic elements, reductive evolution from cellular ancestors, and escape of genes from cellular hosts achieving partial replicative autonomy and becoming parasitic genetic elements. These three classical scenarios give different timelines for the origin of viruses and do not explain the provenance of the two key functional modules that are responsible, respectively, for virus genome replication and virion morphogenesis. Here we outline a 'chimeric' scenario under which different types of primordial, selfish replicons gave rise to viruses by recruiting host proteins for virion formation. We also propose that new groups of viruses have repeatedly emerged at all stages of the evolution of life, often, through the displacement of ancestral structural and genome replication genes.

[H1] Introduction

Viruses are the most abundant biological entities on our planet and have major roles in global ecology and evolution of the biosphere [START_REF] Danovaro | Virus-mediated archaeal hecatomb in the deep seafloor[END_REF][START_REF] Chow | Biogeography of Viruses in the Sea[END_REF][START_REF] Cobián Güemes | Viruses as Winners in the Game of Life[END_REF][START_REF] Koonin | A virocentric perspective on the evolution of life[END_REF] . All cellular organisms, with the possible exception of some intracellular parasitic bacteria, harbour distinctive repertoires of viruses, that is, obligate intracellular genetic parasites that package their genomes into virus particles (virions) [START_REF] Raoult | Redefining viruses: lessons from Mimivirus[END_REF] . The ubiquity of viruses, combined with the theoretical argument that genetic parasites will inevitably emerge in replicator systems [START_REF] Koonin | Inevitability of the emergence and persistence of genetic parasites caused by evolutionary instability of parasite-free states[END_REF][START_REF] Iranzo | Inevitability of Genetic Parasites[END_REF] , implies that the entire course of the evolution of life is actually a story of virus-host coevolution [START_REF] Koonin | A virocentric perspective on the evolution of life[END_REF][START_REF] Koonin | Viruses and mobile elements as drivers of evolutionary transitions[END_REF][START_REF] Forterre | The major role of viruses in cellular evolution: facts and hypotheses[END_REF][START_REF] Frank | Co-option of endogenous viral sequences for host cell function[END_REF] . Accordingly, evolution of life cannot be understood without elucidating the origin(s) of viruses, yet, these origins currently remain mysterious.

Historically, three distinct scenarios of virus origin have been considered [START_REF] Forterre | The origin of viruses and their possible roles in major evolutionary transitions[END_REF][12][START_REF] Sapp | The prokaryote-eukaryote dichotomy: meanings and mythology[END_REF][START_REF] Flugel | The precellular scenario of genovirions[END_REF][START_REF] Forterre | The origin of viruses[END_REF][START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Morse | The evolutionary biology of viruses[END_REF] (Figure 1). According to the 'primordial virus world' or 'virus early' hypothesis, viruses are direct descendants of the first replicons that existed during the pre-cellular stage of the evolution of life. By contrast, in the 'reductive virus origin' or 'regression' scenario, viruses are the ultimate products of degeneration of ancestral cells that have lost their autonomy and transitioned to obligate intracellular parasitism. Finally, in the 'escaped genes' scenario, viruses evolved on multiple, independent occasions in different cellular organisms from host genes that acquired the capacity for (quasi)autonomous, selfish replication and infectivity. Accordingly, escaped bacterial, archaeal and eukaryotic genes are thought to have given rise to bacterial, archaeal and eukaryotic viruses, respectively. The three scenarios seem to be mutually exclusive with respect to the origin of any particular group of viruses but different groups of viruses potentially could have evolved via different routes. Over the years, all three scenarios have been revised, elaborated, temporarily abandoned, and revisited.

Viruses use, effectively, all possible strategies of genome replication and expression, with different nucleic acid forms (single-stranded or double-stranded RNA or DNA) as the genome that is incorporated into virions. This diversity of genomic strategies in viruses contrasts with the uniformity observed in cellular organisms and seems to be most compatible with the possibility that the virus world descended directly from a pre-cellular stage of evolution [START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Holmes | What does virus evolution tell us about virus origins?[END_REF] . By contrast, the discovery of protist-infecting giant viruses rival bacteria and archaea in terms of genome and particle size, and encode a variety of translation system components [START_REF] Abrahao | Tailed giant Tupanvirus possesses the most complete translational apparatus of the known virosphere[END_REF]20 inspired a revival of the regression hypothesis [START_REF] Abergel | The rapidly expanding universe of giant viruses: Mimivirus, Pandoravirus, Pithovirus and Mollivirus[END_REF][START_REF] Nasir | A phylogenomic data-driven exploration of viral origins and evolution[END_REF][START_REF] Colson | Mimivirus: leading the way in the discovery of giant viruses of amoebae[END_REF][START_REF] Abrahao | The analysis of translation-related gene set boosts debates around origin and evolution of mimiviruses[END_REF] . Finally, an updated version of the escape hypothesis posits that the first viruses 'escaped' not from modern but from primordial cells, predating the last universal cellular ancestor [START_REF] Forterre | Viruses: Essential Agents of Life[END_REF] .

Formulating falsifiable hypotheses that would allow one to discriminate among the three scenarios of virus origin is no easy task. However, if clues are to be found, these likely will emerge from homologous relationships between virus and cellular host genes. Many virus genes, especially, in large viruses with double-stranded (ds) DNA genomes, have readily identifiable cellular homologs. However, most of these genes encode proteins that are involved in various forms of virus-host interactions, are conserved only among closely related viruses and seem to be relatively late acquisitions 20,[START_REF] Fridman | A myovirus encoding both photosystem I and II proteins enhances cyclic electron flow in infected Prochlorococcus cells[END_REF][START_REF] Roux | Ecogenomics and potential biogeochemical impacts of globally abundant ocean viruses[END_REF][START_REF] Pushkarev | A distinct abundant group of microbial rhodopsins discovered using functional metagenomics[END_REF][START_REF] Ahlgren | Discovery of several novel, widespread, and ecologically distinct marine Thaumarchaeota viruses that encode amoC nitrification genes[END_REF] . Thus, these genes reflect important aspects of virus evolution but are of little direct relevance for virus origins.

To explore the origins of viruses, it is necessary to investigate the provenance of the core virus genes that are responsible for the key virus-specific functions. A typical virus genome encompasses two core modules that consist, respectively, of genes encoding proteins required for genome replication and proteins involved in virion formation (hereafter we will call these replication module and morphogenetic module, respectively). In small viruses, these core modules include all or most of their genes whereas in large viruses, the core genes only represent a small fraction of their gene repertoire [START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Iranzo | The Double-Stranded DNA Virosphere as a Modular Hierarchical Network of Gene Sharing[END_REF] . Understanding the origin of any virus group requires elucidation of the evolutionary roots of both core modules [START_REF] Koonin | Origins and evolution of viruses of eukaryotes: The ultimate modularity[END_REF][START_REF] Krupovic | Order to the viral universe[END_REF] . In this Opinion article, we review the evidence on the origins of the replication and morphogenetic modules of the most common and diverse groups of viruses, and we develop arguments for the emergence of the two core modules. We propose that the virus replication machinery arose from the primordial pool of genetic elements whereas the structural proteins seem to have been acquired from hosts at different stages of evolution, leading to a chimeric origin of viruses.

[H1] Origin of virus replication modules

Viral replication proteins often have no closely related homologs in extant cellular organisms with sequenced genomes [START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF] . Thus, it has been suggested that many of these proteins evolved in the precellular world [START_REF] Koonin | A virocentric perspective on the evolution of life[END_REF][START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF] or in primordial, now extinct, cellular lineages [START_REF] Forterre | The origin of viruses and their possible roles in major evolutionary transitions[END_REF][START_REF] Forterre | Viruses: Essential Agents of Life[END_REF][START_REF] Forterre | Three RNA cells for ribosomal lineages and three DNA viruses to replicate their genomes: a hypothesis for the origin of cellular domain[END_REF] . The list of the hallmark virus replication genes is short but spans multiple, diverse groups of viruses and related mobile genetic elements (MGEs) (Box 1). The prototypical virus replication hallmarks are the homologous RNAdependent RNA polymerases (RdRp) and reverse transcriptases (RT) that, respectively, mediate the replication of all classes of RNA viruses and reverse-transcribing viruses as well as retroelements. Other hallmarks include a distinct superfamily of helicases, often fused to primases, protein-primed DNA polymerases, and the endonuclease involved in the initiation of rolling circle DNA replication (RCRE).

These hallmark proteins have only distant homologs in cellular organisms but are prevalent in capsidless MGEs (Box 1).

The RdRps and the RTs are particularly notable as potential relics of the primordial replicator pool. These enzymes catalyze RNA replication via RNA or DNA intermediates and these reaction contribute to specialized functions in cellular organisms (such as telomere biogenesis in eukaryotes [START_REF] Autexier | The structure and function of telomerase reverse transcriptase[END_REF] ) but not the cellular genome replication [START_REF] Velthuis | Common and unique features of viral RNA-dependent polymerases[END_REF][START_REF] Venkataraman | RNA Dependent RNA Polymerases: Insights from Structure, Function and Evolution[END_REF] . The RdRps and RTs share the structural fold of the main catalytic domain with the DNA-dependent DNA polymerases that are involved in the replication of the genomes of archaea, eukaryotes and many dsDNA viruses as well as the RCRE and archaeo-eukaryotic primases (AEPs) [START_REF] Mönttinen | Common Structural Core of Three-Dozen Residues Reveals Intersuperfamily Relationships[END_REF][START_REF] Iyer | Origin and evolution of the archaeo-eukaryotic primase superfamily and related palm-domain proteins: structural insights and new members[END_REF] , which are also commonly found in DNA viruses and plasmids from all three domains of cellular life [START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF][START_REF] Iyer | Origin and evolution of the archaeo-eukaryotic primase superfamily and related palm-domain proteins: structural insights and new members[END_REF][START_REF] Kazlauskas | Novel Families of Archaeo-Eukaryotic Primases Associated with Mobile Genetic Elements of Bacteria and Archaea[END_REF] . This so-called 'palm' fold is related to the RNA-recognition motif (RRM) domain, one of the most common RNA-binding domains that is involved in various RNA biogenesis processes in all forms of cellular life [START_REF] Clery | RNA recognition motifs: boring? Not quite[END_REF] .

We hypothesize that RRM was one of the earliest protein domains to evolve and was central to the origin and early evolution of both RNA and DNA replication (Figure 2). The origin of the RRM is likely to be rooted in the primordial RNA world [START_REF] Gilbert | Origin of life: The RNA world[END_REF] where it would serve as a cofactor to ribozymes including hypothetical ribozyme replicases. Subsequently, the RRM evolved a range of enzymatic functions, most notably, those of RdRp and RT. Although it is not clear which virus polymerase is older (ancestral), it has been suggested that virus RdRps could have evolved from a common ancestor shared with the RTs of group II introns [START_REF] Wolf | Origins and Evolution of the Global RNA Virome[END_REF]44 , a highly diverse class of mobile retroelements that are widespread in bacterial genomes [START_REF] Mcneil | Group II introns: versatile ribozymes and retroelements[END_REF] . Indeed, RTs of group II introns are believed to be ancestral to the RTs of eukaryotic retroelements and reverse-transcribing viruses, and among virus RdRps, display closest sequence similarity to those of bacterial positive-sense RNA viruses (family Leviviridae) [START_REF] Wolf | Origins and Evolution of the Global RNA Virome[END_REF] . As a rule, RNA replication and reverse transcription are absent in cells revealing fundamental differences between cellular and viral life styles. The only known exceptions to this rule are telomerases and eukaryotic RdRps involved in the formation of telomeres and small RNAs (as a part of RNA interference and the antiviral response), respectively. Notably, cellular RdRps are not homologous to the viral enzymes and have the so-called double-psi barrel fold that is unrelated to the RRM and is instead homologous to the core catalytic domains of the DNA-dependent RNA polymerases that are involved in transcription in all domains of cellular life [START_REF] Iyer | Evolutionary connection between the catalytic subunits of DNA-dependent RNA polymerases and eukaryotic RNA-dependent RNA polymerases and the origin of RNA polymerases[END_REF][START_REF] Salgado | The structure of an RNAi polymerase links RNA silencing and transcription[END_REF] .

Many bacterial and archaeal viruses do not encode identifiable replicative enzymes of their own, apparently, having lost the primordial, RRM-based ones. Instead, these viruses rely on the host replication machinery, which is often, but not always, recruited to the virus genomes by various virusencoded proteins [START_REF] Weigel | Bacteriophage replication modules[END_REF] . In many cases, horizontally acquired cellular genes encode key components of the replisome, in particular, helicases and primases [START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF] , that are responsible for the replisome assembly at the origin of replication. However, apart from a small minority of bacterial dsDNA viruses that possess replicative enzymes homologous to bacterial DNA polymerase III (family C) [START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF] , there is no alternative to the RRM domain as the main replicative moiety of viruses and MGEs, indicating that the RRM is indeed the major legacy of the primordial pool of genetic elements.

The potential competing scenario that postulates escape(s) of the RRM domain(s) from modern-type cells at later stages of evolution seems far less likely. The primary argument against this scenario is that three key replicative enzymes found in broad classes of viruses and MGEs, namely, RdRp, RT and proteinprimed DNA polymerase, have no counterparts in modern cells other than those that clearly were acquired from selfish elements such as, for example, the eukaryotic telomerase that originates from the RT of prokaryotic group II introns [START_REF] Novikova | Mobile Group II Introns as Ancestral Eukaryotic Elements[END_REF][START_REF] Agrawal | Forks in the tracks: Group II introns, spliceosomes, telomeres and beyond[END_REF] . The RRM domains, especially, the enzymatically active versions, possess readily recognizable sequence signatures, and therefore, origin of the virus replicative enzymes from undetected cellular ancestors is highly unlikely.

At present, we only have vague ideas on the pre-cellular stages of evolution. However, at least three aspects can be assumed logically. First, primordial genetic elements had small genomes; conceivably, soon after the advent of translation, most replicons resembled modern small viruses, encoding only one to a few proteins [START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Holmes | What does virus evolution tell us about virus origins?[END_REF] . Second, the pool of primordial replicators necessarily included genetic parasites. Not only are such parasites ubiquitous in the modern biosphere, but a strong theoretical argument suggests that their emergence is an intrinsic feature of evolving replicators. In mathematical models of replicator evolution, stable equilibria necessarily include parasitic genetic elements [START_REF] Koonin | Inevitability of the emergence and persistence of genetic parasites caused by evolutionary instability of parasite-free states[END_REF][START_REF] Iranzo | Inevitability of Genetic Parasites[END_REF] . To put the argument in a deliberately simplistic form, as soon as there is a resource that potentially can be exploited without investing in it (such as the translation system), parasites (cheaters) that hijack that resource instead of replenishing it will necessarily evolve. However, it is important to emphasize that viruses do not typically turn into ultimate parasites but rather retain some components of the replication machinery that control genome replication and maintain the partial autonomy of virus reproduction. Third, within the RNA world and during the transition to the DNA-RNA-protein world, these elements would use different forms of nucleic acids including single-stranded and double-stranded RNA as well as emerging ssDNA and dsDNA genomes. Effectively, all possible forms of genomes would be tried out at this stage, in part, because diversification of the genomic strategy is one of the means to limit the deleterious effects of genetic parasites [START_REF] Takeuchi | On the origin of DNA genomes: evolution of the division of labor between template and catalyst in model replicator systems[END_REF] . Admittedly, the RNA world is a hypothesis but, to our knowledge, it is the only one that resolves, at least conceptually, the chicken and egg problem that seems to doom any other scenario of the origin of nucleic acid-protein reproducers and is, furthermore, compatible with the growing body of experimental results on versatile catalytic activities of ribozymes 52,53 . Further, it is useful to note that the scenario of early evolution outlined here is not contingent on any specific form of compartmentalization that would confine the primordial replicator pool. It is negligible for our line of argument whether this pool evolved in inorganic compartments or lipid membrane-bounded vesicles, which might be called protocells [START_REF] Joyce | Protocells and RNA Self-Replication[END_REF][START_REF] Lancet | Systems protobiology: origin of life in lipid catalytic networks[END_REF][START_REF] Mulkidjanian | Origin of first cells at terrestrial, anoxic geothermal fields[END_REF][START_REF] Martin | Hydrothermal vents and the origin of life[END_REF][START_REF] Koonin | On the origin of genomes and cells within inorganic compartments[END_REF] .

Thus, one of the few claims we can confidently make about the primordial genetic pool is that it was replete with diverse, competing, 'virus-like' genetic elements, some of which exploited resources produced by others. But, were there viruses, that is, genetic parasites that encode not only components of the replication machinery but also proteins required for virion formation? Indeed, the ability to form a virion is often considered a signature of the viral state that distinguishes viruses from other MGEs [START_REF] Bamford | Do viruses form lineages across different domains of life?[END_REF][START_REF] Forterre | Cellular domains and viral lineages[END_REF] . The role of the virion in a virus reproduction cycle includes both protection of the genome while outside a host cell and delivery of the genome into the cell. The entry function typically involves interaction between the virus particle and a receptor on the cell surface. The relevance of this function at the stage of the primordial genetic pool is uncertain because no valid data on the nature of the compartments that hosted that pool exists. However, the protective role of virus particles could be potentially important at this early stage of evolution. The virion could both stabilize the viral genome in adverse physicochemical conditions and protect it from targeted degradation by competing replicons. Given this apparently plausible hypothesis for the origin of viruses in the pre-cellular era, the problem becomes, primarily, empirical: can we trace the origin of virion components, and in particular, capsid proteins?

[H1] Diversity of virus capsids

About 60% of the recognized virus taxa have icosahedral capsids, which is unsurprising because the icosahedron has the largest volume to surface area ratio, closest to that of a sphere, the most thermodynamically favorable three-dimensional shape, and generates the maximum enclosed volume for shells comprised of a given size subunit [START_REF] Caspar | Physical principles in the construction of regular viruses[END_REF][START_REF] Crick | Structure of small viruses[END_REF] . 50-90% of virus particles detected in the global marine virosphere have an average diameter of 50 nm and belong to the icosahedral tailless morphotype [START_REF] Brum | Global morphological analysis of marine viruses shows minimal regional variation and dominance of non-tailed viruses[END_REF] . The vast majority of the remaining 10-50% are bacterial and archaeal viruses with icosahedral capsids and helical tails (order Caudovirales). Apart from icosahedra, numerous viruses, especially, those infecting plants and archaea, have elongated, rod-shaped or filamentous capsids [START_REF] Solovyev | Helical capsids of plant viruses: architecture with structural lability[END_REF][START_REF] Dimaio | A virus that infects a hyperthermophile encapsidates A-form DNA[END_REF][START_REF] Ptchelkine | Unique architecture of thermophilic archaeal virus APBV1 and its genome packaging[END_REF][START_REF] Zamora | Potyvirus virion structure shows conserved protein fold and RNA binding site in ssRNA viruses[END_REF][START_REF] Dimaio | The molecular basis for flexibility in the flexible filamentous plant viruses[END_REF] whereas others, such as numerous negative-strand RNA viruses of animals, have helical nucleocapsids [START_REF] Sun | Bunyavirales ribonucleoproteins: the viral replication and transcription machinery[END_REF][START_REF] Sun | A versatile building block: the structures and functions of negativesense single-stranded RNA virus nucleocapsid proteins[END_REF][START_REF] Jamin | Nonsegmented Negative-Sense RNA Viruses-Structural Data Bring New Insights Into Nucleocapsid Assembly[END_REF] . Finally, there is a long 'tail' of odd-shaped virions such as those found in numerous viruses of hyperthermophilic archaea [START_REF] Prangishvili | The enigmatic archaeal virosphere[END_REF] . Thus, the diversity of widespread shapes among viral capsids is quite limited. But what about the major structural proteins that form these viral particles? Analysis of the evolutionary relationships between capsid proteins (CPs) and especially, their origins is a non-trivial task due to the rapid sequence divergence among these proteins. Sequence conservation among the CPs drops off rapidly even at short evolutionary distances because, in this case, selection maintains primarily the structural fold rather than the sequence 73 . Accordingly, structural comparisons of the CPs are far more informative than even the most sensitive sequence comparisons [START_REF] Greene | The CATH domain structure database: new protocols and classification levels give a more comprehensive resource for exploring evolution[END_REF] . Such structural comparisons have uncovered far reaching structural unity between the CPs of diverse viruses that infect hosts from different domains and kingdoms of cellular life 73,[START_REF] Krupovic | Double-stranded DNA viruses: 20 families and only five different architectural principles for virion assembly[END_REF][START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . The number of structural folds, at least, widespread ones, represented in viral CPs is fairly small. For example, for viruses with dsDNA genomes from 20 families that account for a large part of the virosphere only 5 distinct structural folds of the CPs have been discovered [START_REF] Krupovic | Double-stranded DNA viruses: 20 families and only five different architectural principles for virion assembly[END_REF] . Furthermore, small viruses with ssRNA and ssDNA genomes share homologous CPs [START_REF] Krupovic | Networks of evolutionary interactions underlying the polyphyletic origin of ssDNA viruses[END_REF] . Such findings demonstrate the antiquity of the CPs and evolutionary connections between the respective viruses, which can reflect both ancient common ancestry and horizontal gene exchange 73,[START_REF] Krupovic | Double-stranded DNA viruses: 20 families and only five different architectural principles for virion assembly[END_REF][START_REF] Rossmann | Icosahedral RNA virus structure[END_REF] .

The other side of the coin, however, is that similar capsid geometries do not necessarily reflect homologous relationships between viruses [START_REF] Moreira | Ten reasons to exclude viruses from the tree of life[END_REF] : for example, icosahedral capsids emerged at least 11 times during virus evolution from unrelated CPs with drastically different folds, from all-α to all-β [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . Viral CPs forming helical (nucleo)capsids are equally diverse [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . This observation is crucial for understanding the evolution of CPs because it refutes the hypothesis that the same fold, such as the jelly-roll fold, which is most common among icosahedral viruses [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF][START_REF] Rossmann | Icosahedral RNA virus structure[END_REF] , could evolve by convergence, driven by geometrical constraints on the capsid [START_REF] Moreira | Ten reasons to exclude viruses from the tree of life[END_REF] . Furthermore, not all folds that are known to produce icosahedral shells are used by viruses for capsid formation. For example, bacterial microcompartments and certain enzymes, such as luminazine synthase, assemble into icosahedral cages but their shell proteins are structurally unrelated to known viral proteins [START_REF] Sasaki | Structure and assembly of scalable porous protein cages[END_REF][START_REF] Ladenstein | The lumazine synthase/riboflavin synthase complex: shapes and functions of a highly variable enzyme system[END_REF][START_REF] Kerfeld | Bacterial microcompartments[END_REF][START_REF] Krupovic | Cellular origin of the viral capsid-like bacterial microcompartments[END_REF] . Thus, the extant number of capsid protein folds in the virosphere likely represents the number of distinct occasions on which the capsids have evolved rather than the limits of the folding space.

[H1] Cellular ancestry of capsids

Most of the viral CPs do not have easily detectable homologs among cellular proteins [START_REF] Cheng | 3rd. Viral capsid proteins are segregated in structural fold space[END_REF] , raising difficult questions about their origins. One possible scenario involves de novo origin of the CPs in the genomes of primordial selfish replicons through mechanisms such as overprinting and diversification [START_REF] Sabath | Evolution of viral proteins originated de novo by overprinting[END_REF] . Alternatively, CPs evolved from ancestral proteins that originally performed cellular functions but were subsequently recruited for capsid formation and underwent substantial acceleration of evolution.

Notwithstanding this apparent fast evolution of virus structural proteins, our recent comprehensive analysis of the evolutionary connections of the major virion proteins, including capsid, nucleocapsid and matrix proteins, using sensitive methods for sequence and structure comparison, indicates that many CPs evolved from ancestral cellular proteins on multiple, independent occasions [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . The natural history of the jelly-roll fold illustrates well both multiple cellular origins and the subsequent extent of evolution (Figure 3). The single jelly-roll (SJR) is the most common fold in viral CPs, forming capsids in viruses from about one third of virus families, mostly in eukaryotic ssRNA and ssDNA viruses. High-resolution CP structures are available for many SJR-CPs 73,78 , and searching protein structure databases with these structures as queries revealed numerous and diverse homologs from bacteria, archaea and eukaryotes 76 . The cellular SJR domains are functionally diverse, including a variety of carbohydrate-binding proteins 86 , nucleoplasmins or nucleophosmins [START_REF] Eitoku | Histone chaperones: 30 years from isolation to elucidation of the mechanisms of nucleosome assembly and disassembly[END_REF] and various proteins of the tumor necrosis factor (TNF) superfamily [START_REF] Locksley | The TNF and TNF receptor superfamilies: integrating mammalian biology[END_REF] . Although obtaining a robust phylogenetic tree for the SJR domain might not be feasible due to the lack of sufficient sequence conservation, clustering by structural similarity suggests two or three independent points of origin for the SJR-CPs, possibly, from carbohydrate-binding proteins. Indeed, some of the cellular SJR proteins, such as the TNF homologs, can assemble into structures resembling virus particles [START_REF] Liu | Crystal structure of sTALL-1 reveals a virus-like assembly of TNF family ligands[END_REF] . Furthermore, ancestral viruses would benefit substantially from capture of a carbohydrate-binding protein that provides both genome protection and receptor-binding capacity. Accordingly, many extant viruses bind to specific glycan receptors directly through the SJR-CP [START_REF] Shen | Terminal N-linked galactose is the primary receptor for adeno-associated virus 9[END_REF][START_REF] Neu | Viruses and sialic acids: rules of engagement[END_REF][START_REF] Maginnis | Virus-Receptor Interactions: The Key to Cellular Invasion[END_REF][START_REF] Liu | Sialic acid-dependent cell entry of human enterovirus D68[END_REF] . The proposed direction of SJR recruitment, from cells to viruses, appears far more likely than the reverse direction, given the wide spread and functional diversity of the SJR protein in diverse cellular life forms and by contrast, their paucity among bacterial and archaeal viruses. Notably, whereas structural comparisons suggest the monophyly of SJR-CPs of eukaryotic ssRNA and ssDNA viruses, the SJR-CPs of bacterial microviruses and sphaerolipoviruses have been apparently acquired independently of each other and of eukaryotic viruses [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . Within the eukaryotic positive-sense RNA viruses, SJR-CP evolution is largely congruent with the RdRp evolution, complemented by horizontal transfer of SJR-CP genes that is particularly frequent among the smallest RNA and DNA viruses [START_REF] Koonin | Origins and evolution of viruses of eukaryotes: The ultimate modularity[END_REF][START_REF] Wolf | Origins and Evolution of the Global RNA Virome[END_REF][START_REF] Krupovic | Networks of evolutionary interactions underlying the polyphyletic origin of ssDNA viruses[END_REF][START_REF] Shi | Redefining the invertebrate RNA virosphere[END_REF] . Gene gain and loss analysis has suggested that the SJR-CP was ancestral in the eukaryotic RNA virome but subsequently was replaced, on many independent occasions, with various non-homologous capsid and nucleocapsid proteins, and even lost in some virus groups, leading to the emergence of capsidless 'viruses' [START_REF] Wolf | Origins and Evolution of the Global RNA Virome[END_REF] .

The second most prevalent class of viral CPs includes the double jelly-roll (DJR) fold that consists of two consecutive SJRs [START_REF] Benson | Does common architecture reveal a viral lineage spanning all three domains of life?[END_REF] . The DJR-CP is found in about 10% of known virus taxa, including numerous dsDNA viruses that infect bacteria, archaea and eukaryotes. Most of the ubiquitous, icosahedral, tailless dsDNA phages detected in marine environments [START_REF] Brum | Global morphological analysis of marine viruses shows minimal regional variation and dominance of non-tailed viruses[END_REF] likely have capsids assembled from the DJR-CP [START_REF] Kauffman | A major lineage of non-tailed dsDNA viruses as unrecognized killers of marine bacteria[END_REF] . This possibility is reinforced by the recent discovery of the remarkable diversity of DJR-encoding bacterial and archaeal viruses in viromes and microbial (meta)genomes [START_REF] Yutin | Vast diversity of prokaryotic virus genomes encoding double jelly-roll major capsid proteins uncovered by genomic and metagenomic sequence analysis[END_REF] . No DJR proteins of cellular origin have been detected suggesting that the DJR CP evolved from a SJR-CP by gene duplication in an ancestral virus genome [START_REF] Abrescia | Insights into virus evolution and membrane biogenesis from the structure of the marine lipid-containing bacteriophage PM2[END_REF] . Bacterial and archaeal viruses that belong to the family Sphaerolipoviridae might represent an intermediate step on the evolutionary path from SJR to the DJR capsids [START_REF] Rissanen | Bacteriophage P23-77 capsid protein structures reveal the archetype of an ancient branch from a major virus lineage[END_REF]100 . These viruses have two SJR-CPs that form homo-and heterodimers and the vertical orientation of the β-strands in the capsids matches DJR-CPs but differs from that of SJR-CPs of small RNA and DNA viruses 73 . Consistent with a SJR-CP gene duplication giving rise to the DJR-CP, the two CPs of sphaerolipoviruses show a closer structural similarity to each other than to any other CPs [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF]100 . Among the SJR-CPs, those of sphaerolipoviruses are weakly similar to homologs from other viruses and instead cluster with nucleoplasmins and nucleophosmins, which implies independent origin from a cellular SJR ancestor [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] .

We have also identified several other cases of apparent evolution of major virion proteins via recruitment of ancestral cellular proteins. For example, the CPs of alphaviruses evolved from a chymotrypsin-like protease closely related to the polyprotein-processing protease of flaviviruses [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF]101 , whereas the nucleocapsid protein of reverse-transcribing viruses of the recently introduced order Ortervirales 102 originated from a zinc-knuckle domain that is widespread in functionally diverse cellular proteins [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . In archaea, one of the nucleocapsid proteins of tristromaviruses has evolved from a truncated Cas4-like nuclease 103 . Similarly, matrix proteins, which form a protein layer between the nucleocapsid and the viral envelope, of arenaviruses, mononegaviruses and retroviruses evolved from the zinc-binding RING domain, cyclophilins and a DNA-binding domain of integrases, respectively [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF] . Furthermore, the pan-eukaryotic fusogen HAP2 has been recently shown to be homologous to class II viral fusion proteins [104][105][106] , which in many RNA viruses assemble into an external icosahedral shell 107,108 . Although the directionality of evolution is still debated in this case, given the ubiquity of HAP2 in eukaryotes in contrast to the limited distribution of class II fusogens in viruses, a cellular origin seems more likely, with viruses acquiring the fusogenic capacity at a later stage. Together with the evolutionary scenarios for the jelly-roll CPs outlined above, all these cases convey the same message, that of multiple origins of major virion proteins from cellular ancestors.

Virus capsid proteins apparently evolved from cellular ancestors at different stages of evolution, from early ones, shortly after the emergence of modern-type cells, to comparatively late stages, after the origin of eukaryotes or even the origin of animals. Although pinpointing the times at which distinct lineages of virus capsid proteins emerged is not an easy task, important clues can be derived from the host ranges of the extant viruses. Given the high prevalence of the SJR and DJR CPs among viruses infecting all three domains of cellular life, these proteins most likely emerged during or shortly after the advent of modern-type bacterial and archaeal cells. By contrast, the exclusive yet ubiquitous presence of reverse-transcribing viruses in eukaryotes implies that the nucleocapsid and capsid domains of the Gag polyprotein were acquired by ancestral reverse-transcribing virus at an early stage of eukaryogenesis 109 . Furthermore, the matrix protein domain, which is specific to members of the family Retroviridae, was likely appended to the Gag polyprotein following the divergence of retroviruses from other orterviruses, probably after the emergence of vertebrates. The apparent absence of negative-sense RNA viruses in bacteria, archaea and protists, which contrasts with their high prevalence in animals, strongly suggests that these viruses and their particular nucleocapsids co-emerged with metazoa and later spread to plants 110,111 . A similar scenario is likely for the recruitment of protease as the CP by alphaviruses [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF]101 and of the RING domain by arenaviruses, whose host ranges are limited to animals.

The hypothesis that cellular proteins can be recruited to function as virus CPs draws additional support from recent breakthroughs in computational modeling of large protein assemblies, protein engineering and laboratory evolution experiments. Artificial, megadalton-scale two-component, 120-subunit icosahedral protein complexes have been designed computationally 112 and, following introduction of positively charged residues on the inner surface of the shells, these cages could encapsidate their own mRNA genomes 113 . Importantly, under selective pressure, such nucleoprotein assemblies quickly evolved for improved genome packaging, stability, and in vivo circulation time, all properties relevant for natural virions. A similar result was obtained with the naturally occurring, non-viral icosahedral shells of lumazine synthase from Aquifex aeolicus 114 . Appending a cationic peptide to the lumazine synthase enabled specific recognition of packaging signals on cognate mRNAs and subsequent evolutionary optimization led to virus-like capsids that were large enough to accomodate the cognate full-length RNA genome in vivo and protected the cargo RNA molecules from nucleases 114 . These studies demonstrate the relative ease of the emergence of virus-like entities from artificial, computationally designed as well as natural non-viral proteins.

Admittedly, the likely cellular ancestors are not detectable for all virus structural proteins so far, including several widespread varieties. In particular, the capsid proteins of the highly abundant tailed bacterial and archaeal viruses have cellular homologs that form intracellular nanocompartments in many bacteria and archaea, known as encapsulins 115 . In this case, there is no evidence of the direction of evolution and a cellular origin remains a distinct possibility. For capsid proteins of rod-shaped and filamentous plant viruses as well as the capsid protein of most viruses of hyperthermophilic archaea, no cellular homologs have been identified. De novo origin of some of these 'orphan' virion proteins cannot be discarded as a distinct route of virus evolution. Nevertheless, overall, the exaptation of cellular proteins seems to be a common theme.

[H1] The fourth path for virus origin: an amalgam of the primordial and escaped genes scenarios

The analyses of the evolution of the replicative and structural modules of viruses discussed above suggest a 'chimeric' scenario for the origin of viruses, which is distinct from each of the three traditional scenarios (Figure 1) but combines features of the primordial and escaped genes scenarios (Figure 4). In this model, the pre-cellular and early cellular stages of evolution include various forms of parasitic replicators with RNA and DNA genomes. Emergence of such selfish elements seems to be an intrinsic feature of replicator systems [START_REF] Koonin | Inevitability of the emergence and persistence of genetic parasites caused by evolutionary instability of parasite-free states[END_REF][START_REF] Iranzo | Inevitability of Genetic Parasites[END_REF] . At those early stages of evolution, the reproduction strategies of the parasitic elements resembled those of present day plasmids and transposons. Highly conserved transposases are widely represented in all cellular organisms 116 , suggesting that integration into the host genome is an ancient strategy of genetic parasites. There is no evidence that the key replication proteins of small selfish replicators, such as RdRp, RT or RCRE, were ever encoded by bona fide cellular genes, and the same seems to apply to transposases. Thus, the replication modules of viruses seem to originate from the primordial genetic pool although the long course of their subsequent evolution involved many displacements by replicative genes from their cellular hosts. This evidence in support of the primordial origins of the key components of the virus replication machinery contrasts the findings on the provenance of the components of the translation system (along with numerous other proteins of diverse functions) encoded by giant viruses [START_REF] Abrahao | Tailed giant Tupanvirus possesses the most complete translational apparatus of the known virosphere[END_REF][START_REF] Abrahao | The analysis of translation-related gene set boosts debates around origin and evolution of mimiviruses[END_REF] . Although the cell regression scenario of virus origin has been boosted by the discovery of these genes, detailed phylogenetic analyses suggest incremental, convergent capture of the translation-related genes from different eukaryotic hosts during the evolution of different giant viruses from smaller virus ancestors 20,117 . This scenario is further supported by the recent discovery of multiple ribosomal protein genes in several bacterial viruses with moderately-sized genomes 118 . Thus, the evolution of giant viruses, irrespective of the numerous interesting and puzzling aspects of their genome layout and biology, can be accommodated in the evolutionary scenario proposed here. Also, no evidence exists for the possible origin of viruses from intracellular parasitic bacteria. As intracellular parasitic or symbiotic bacteria have evolved numerous times and have independently given rise to extremely reduced forms, including organelles 119,120 , the absence of bacteria-derived viruses suggests that the evolutionary path from a cell to a virus is impracticable.

The first CPs -and hence the first true viruses -most likely evolved as a result of recruitment of carbohydrate-binding or nucleic acid-binding proteins from cells that were advanced enough to encode multiple proteins with these functions. As most common viral capsids have simple, symmetrical, thermodynamically favorable shapes, such as icosahedra or helices, the structural transitions involved in the recruitment of cellular proteins as CPs could have been relatively minor. The multiple recruitments of unrelated proteins as CPs forming icosahedral capsids seem to support this view. Another argument for easy formation of capsid-like structures is the recruitment of two distinct proteins as structural units for capsid-like intracellular microcompartments [START_REF] Krupovic | Cellular origin of the viral capsid-like bacterial microcompartments[END_REF] . Recent results from experimental evolution of virus-like particles through relatively small modification of cellular enzymes, primarily by introduction of positively charge residues interacting with nucleic acids, further reinforce this line of argument 114 .

As emphasized above, genetic parasites are an integral feature of replicator systems and, accordingly, of all cellular life forms. These parasites are fundamentally diverse, spanning a wide range of relationships with the host, ranging from symbiotic, such as many plasmids and moderate, integrating viruses, to extremely aggressive, such as numerous lytic viruses 121,122 . Our current model posits that genetic parasites started out as relatively cooperative commensals or symbionts but, subsequently, on multiple occasions, recruited cellular structural proteins to evolve into elaborate selfish agents employing diverse but, generally, highly efficient reproduction strategies. The tight evolutionary link between viruses and capsidless MGEs is the core of our model of virus origin and is amply supported by comparative analysis of contemporary genetic parasites in all domains of cellular life [START_REF] Krupovic | Networks of evolutionary interactions underlying the polyphyletic origin of ssDNA viruses[END_REF]123,124 .

Box 1. Hallmark viral replication genes.

Virus hallmark genes encode key proteins involved in genome replication and virion morphogenesis. These genes have no close homologs in cellular life forms but are shared by diverse viruses, and connect the evolutionary network in the virus world [START_REF] Koonin | The ancient Virus World and evolution of cells[END_REF][START_REF] Iranzo | The Double-Stranded DNA Virosphere as a Modular Hierarchical Network of Gene Sharing[END_REF] . For example, the network of dsDNA viruses is held together by 14 hallmark genes, including those encoding different families of major capsid proteins, genome packaging ATPases, virion maturation proteases and various proteins involved in viral genome replication [START_REF] Iranzo | The Double-Stranded DNA Virosphere as a Modular Hierarchical Network of Gene Sharing[END_REF] . The reach of replication genes is particularly broad and connects not only viruses with different nucleic acid types but also links viruses and non-viral MGEs. Most notable are 5 broadly distributed virus hallmark genes involved in genome replication (Figure ; structures are colored by secondary structure: α-helices, red; β-strands, blue; random coil, grey). RdRp is universally conserved across RNA viruses and, for this virus type, can be considered a universal marker equivalent to the 16S ribosomal RNA genes of cellular organisms (RdRp of poliovirus (PDB id: 1ra7) is shown in the figure). Indeed, RdRp allows studying the evolution of all RNA viruses in a single framework, despite the vast diversity of these viruses in other functional modules, most notably, those for morphogenesis [START_REF] Wolf | Origins and Evolution of the Global RNA Virome[END_REF] . RTs (catalytic fragment of Moloney murine leukemia virus RT (PDB id: 1mml) is shown in the figure) are encoded by all reverse-transcribing viruses with both RNA and DNA genomes (the latter sometimes unofficially referred to as the 'pararetroviruses') 102 . Unlike RdRps, RTs are not restricted to viruses but are found across a wide range of archaeal, bacterial and eukaryotic non-viral MGEs, including group II introns, diversity-generating retroelements (DGR), LINE, DIRS retrotransposons, retrons, retro-plasmids and others 123,125,126 . Furthermore, RTs have been recruited by cellular organisms on multiple independent occasions to perform specialized functions not linked with genome replication, for example, as telomerases [START_REF] Autexier | The structure and function of telomerase reverse transcriptase[END_REF] . Protein-primed family B DNA polymerases (PolBs; pPolB of bacteriophage phi29 (PDB id: 2py5) is shown in the figure) are homologous to the RNA-primed PolBs responsible for genome replication of archaea, eukaryotes and large dsDNA viruses. However, they have unique subdomains for strand displacement, a function performed by a helicase during cellular DNA replication, and are primed by a protein covalently attached to the termini of linear viral genomes rather than by an RNA primer. These polymerases are found in viruses with small-to-moderately-sized dsDNA or ssDNA genomes (10-50 kbp) [START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF] and besides viruses, also in linear cytoplasmic and mitochondrial plasmids of fungi and plants and in transposon-like elements called casposons 127,128 . Rolling-circle replication endonucleases (RCRE) of the HUH superfamily 129 are among the most widely spread replication proteins of viruses with small dsDNA and especially ssDNA genomes infecting hosts in all three domains of life [START_REF] Krupovic | Networks of evolutionary interactions underlying the polyphyletic origin of ssDNA viruses[END_REF]130 (RCRE of porcine circovirus 2 (PDBid: 2hw0) is shown in figure). Homologous RCRE are responsible for the replication of plasmids and transposition of certain transposons in bacteria, archaea, and eukaryotes 129 . Notably, in polyomaviruses and papillomaviruses (dsDNA genomes), the ancestral RCRE has lost the catalytic activity and now binds the replication origin [START_REF] Koonin | Origins and evolution of viruses of eukaryotes: The ultimate modularity[END_REF] . Finally, hexameric superfamily 3 helicases (S3H; S3H of bovine papillomavirus type 1 (PDB id: 5a9k) is shown in figure) are involved in the replication of a wide range of viruses with ssRNA, ssDNA and dsDNA genomes, which range in size from 2 kbp in circoviruses to more than 1 Mbp in mimiviruses. The S3H domain is often fused to other functional domains involved in genome replication, including RCRE (in ssDNA viruses, polyomaviruses and papillomaviruses) and AEP or DnaG-like primases (in diverse dsDNA viruses) [START_REF] Kazlauskas | The logic of DNA replication in double-stranded DNA viruses: insights from global analysis of viral genomes[END_REF][START_REF] Iyer | Origin and evolution of the archaeo-eukaryotic primase superfamily and related palm-domain proteins: structural insights and new members[END_REF][START_REF] Krupovic | Networks of evolutionary interactions underlying the polyphyletic origin of ssDNA viruses[END_REF] . Similar multidomain proteins containing the S3H domain are also abundant in diverse bacterial and archaeal plasmids [START_REF] Kazlauskas | Novel Families of Archaeo-Eukaryotic Primases Associated with Mobile Genetic Elements of Bacteria and Archaea[END_REF] . The distribution of the hallmark replication proteins in both viruses and non-viral MGEs illuminates the evolutionary connection between the two classes of genetic parasites and suggests that evolutionary transitions between the two are possible and likely had a key role in the emergence of the first viruses. A potential ongoing transition of a non-viral MGE into a virus is exemplified by a plasmid from an Antarctic haloarchaeon that uses specialized membrane vesicles to disseminate and infect plasmid-free cells 131 .

Box Figure.

Figures and legends

Figure 1. The three major scenarios for the origin of viruses. The 'virus early' hypothesis (top) assumes that viruses evolved from early replicative elements that preceded the first cellular life forms. The 'regression' hypothesis (middle) suggests that viruses emerged through the degeneration of cells that then assumed a parasitic lifestyle. Finally, the 'escaped genes' hypothesis (bottom) proposes that cellular genes acquired the ability for 'selfish' replication and spread.

Figure 2 .

 2 Figure 2. Evolution of viral and cellular replication modules from the ancestral RNA recognition motif. The RNA recognition motif (RRM) is one of the most common RNA-binding domains and occurs in all forms of cellular life. Structurally related domains are widespread in many viruses and mobile genetic elements. Replication enzymes containing this module include RT, reverse transcriptase; RdRp, RNAdependent RNA polymerase; RCRE, rolling circle replication initiation endonuclease; PolA and PolB, DNAdependent DNA polymerases of families A and B, respectively; and AEP, archaeo-eukaryotic primase. The schematic of the catalyzed reaction is shown for each enzyme, with red and green wavy lines representing DNA and RNA strands, respectively. Topologies of the proteins are shown with arrows for βstrands and green rectangles for α-helices, whereas larger insertions are depicted with yellow rectangles.Red, green and orange circles represent catalytic Asp, His and Tyr residues, respectively. In bacteria, PolA participates in the replication of the lagging DNA strand by connecting Okazaki fragments and in various repair processes, whereas in certain viruses, it functions as the replicative DNA polymerase that was also recruited from a bacteriophage for mitochondrial genome replication in eukaryotes 132 .

Figure 3 .

 3 Figure 3. Major structural virus proteins and their cellular homologs. Many viral proteins that contribute to forming virions likely are derived from cellular carbohydrate-binding or nucleic acid-binding proteins, although some cellular proteins, as in the case of chymotrypsin-like proteases, are initially recruited to function as viral enzymes and only subsequently adapted for virion formation. SINV C, capsid protein of Sindbis virus (genus Alphavirus, family Togaviridae; PDB id: 1wyk); HIV-1 NC, nucleocapsid protein of human immunodeficiency virus 1 (family Retroviridae; PDB id: 1a1t); LASV Z, matrix protein Z of Lassa virus (family Arenaviridae; PDB id: 5i72); EBOV M, matrix protein of Ebola virus (family Filoviridae; PDB id: 1h2c); MMTV MA, matrix protein of mouse mammary tumor virus (family Retroviridae; PDB id: 4zv5); SPMV CP, single jelly-roll capsid protein of satellite panicum mosaic virus (genus Papanivirus; PDB id: 1stm); HCV NS3, non-structural protein 3 of hepatitis C virus (family Flaviviridae; PDB id: 1rgq); Lin28, human pluripotency factor Lin28 (PDB id: 2li8); RING, RING domain of ubiquitin ligase E3 (PDB id: 4v3l); Cyclophilin C (PDB id: 2rmc); Y-INT NTD, N-terminal domain of a tyrosine superfamily integrase (PDB id: 2a3v); CBM, carbohydrate binding motif (PDB id: 4d3l). All structures are colored using the rainbow scheme from blue (N terminus) to red (C terminus).

Acknowledgments

EVK is supported through the intramural program of the U.S. National Institutes of Health. MK was supported by l'Agence Nationale de la Recherche (ANR) (France) project ENVIRA (#ANR-17-CE15-0005-01).

All authors researched data for the article, contributed substantially to discussion of content, wrote the article and reviewed or edited the manuscript before submission.

Author contributions

Conflicts of interest

The authors declare no conflicts of interest.

Publisher's statement

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Reviewer information

Nature Reviews Microbiolog thanks Raul Andino, Purificación López-García, Didier Raoult and Yong-Zhen Zhang for their contribution to the peer review of this work.

ToC blurb

The origin of viruses is an unsolved, controversial question. In this Opinion article, Krupovic, Dolja and Koonin propose a new scenario for the origin of viruses based on primordial, selfish replicators acquiring structural proteins from cells, enabling them to form virions.


Marianna Belotti
email: marianna.belotti@caissedesdepots.fr

Stefano Moretti
email: stefano.moretti@dauphine.fr

Paolo Zappalà
email: paolo.zappala@lip6.fr

Rewarding miners: bankruptcy situations and pooling strategies

Keywords: Blockchain, Mining, Mining Pool, Reward, Bankruptcy Situation

In Proof-of-Work (PoW) based blockchains (e.g., Bitcoin), mining is the procedure through which miners can gain money on regular basis by finding solutions to mathematical crypto puzzles (i.e., full solutions) which validate blockchain transactions. In order to reduce the uncertainty of the remuneration over time, miners cooperate and form pools.

Each pool receives rewards which have to be split among pool's participants. The objective of this paper is to find an allocation method, for a mining pool, aimed at redistributing the rewards among cooperating miners and, at the same time, preventing some malicious behaviours of the miners.

) have proposed a rewarding mechanism that is incentive compatible, ensuring that miners have an advantage to immediately report full solutions to the pool. However, such a mechanism encourages a harmful inter-pool behaviour (i.e., pool hopping) when the reward results insufficient to remunerate pool miners, determining a loss in terms of pool's computational power.

By reinterpreting the allocation rules as outcomes of bankruptcy situations, we define a new rewarding system based on the well-studied Constrained Equal Losses (CEL) rule that maintains the incentive compatible property while making pool hopping less advantageous.

Introduction

In the blockchain systems transactions are collected in blocks, validated and published on the distributed ledger. Nakamoto [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF] proposed a Proof-of-Work system based on Back's Hashcash algorithm [START_REF] Back | Hashcash -a denial of service counter-measure[END_REF] that validates blocks and chains them one to another. The Proof-of-Work system requires finding an input of a predefined one-way function (e.g., hash function) generating an output that meets the difficulty target. More precisely, the goal for the block validators (miners) is to find a numerical value (nonce) that added to an input data string and "hashed" gives an output which is lower than the predefined threshold. A miner who finds a full solution (i.e., a nonce meeting the difficulty target) broadcasts it across the network.

Miners compete to be the first to find a full solution in order to publish the block and gain a reward consisting in new minted crypto-currencies. Mining is a competitive crypto puzzle (a mining race) that participants try to solve as fast as possible. The difficulty D of the crypto puzzle limits the rate at which new transaction blocks are generated by the blockchain (e.g., it takes approximately 10 minutes to find a full solution in the Bitcoin network). This difficulty value is adjusted periodically in order to meet the established validation rate. At the time of writing, in order to validate a block in the Bitcoin blockchain, miners needs to generate (on average) a number D = 15, 47T of hashes.

Mining is a procedure through which miners can gain a substantial amount of money. Nowadays, due to the high difficulty values, solo miners (i.e., miners who work alone with a personal device) find a full solution with a time variance range of billions of years. Small miners survive in this new industry by joining mining pools. A mining pool is a cooperative approach in which multiple miners share their efforts (i.e., their computational power) in order to validate blocks and gain rewards. Once a full solution is found, pool's reward is split among the miners. In this way small miners, instead of waiting for years to be rewarded, gain a fraction of the reward on a regular basis.

Miners' reward is based on their contribution in finding a full solution. In order to give proof of their work, miners submit to the pool partial solutions, i.e., nonces that do not meet the original threshold, but a higher one. The solutions of this easier crypto puzzle are considered "near to valid" solutions and called shares. For those blockchains that adopt a SHA-256 function, every hash value (i.e., output of the hash function) is a full solution with probability 1 2 32 D , and each hash has a probability of 1 2 32 to be a share. Hence, a share is a full solution with probability p := 1 D . Miners are rewarded according to the number of shares that they provide. Whenever a share is also a full-solution a block is validated and the pool gains a reward that is split among pool participants according to the number of shares that they have reported.

Mining pools are managed by a pool manager that establishes the way in which miners should be rewarded. Each pool adopts its own rewarding system. There exist several rewarding approaches that can be more or less attractive to miners (see for instance [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF]).

Mining pool attacks

An attack to a mining pool refers to any miner's behavior which differs from the default practice (the honest one) and that jeopardizes the collective welfare of the pool. Rosenfeld provided in [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF] an overview of the possible malicious behaviours regarding pools whose profitability depends on their own rewarding mechanism. Miners may attack their pool at the time of reporting their Proof-of-Work. More precisely they can (i ) delay in reporting a share (i.e., block withholding) and/or (ii ) report a share elsewhere (i.e., pool-hopping).

The former is a practice consisting in delaying in reporting shares and full solutions to a mining pool. This practice implies delaying a block validation and the consequent possession of the reward, that in some cases may be profitable for attackers. Pool-hopping consists in an attack where miners "hop" from a pool to another one according to pools' attractiveness.

Related works on rewarding mechanisms

The problem for a pool manager is to establish how to redistribute the rewards among pool participants in order to prevent malicious behaviours (as the ones listed above). In other words, the pool manager must choose an "appropriate" rewarding mechanism preventing (possibly, all) different types of attacks. Concerning the block withholding practice, Schrivers et al. [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] make use of non-cooperative game theory to propose a rewarding mechanism (denoted as incentive compatible) that prevents this attack. This specific rewarding system is robust against malicious actions operated inside a pool, however it does not behave as well in an inter-pool environment since it cannot prevent pool-hopping. In this case, Rosenfeld [START_REF] Rosenfeld | Analysis of bitcoin pooled mining reward systems[END_REF] shows that malicious miners can gain at the expenses of the honest ones, who receive a lower reward than the expected one. In [START_REF] Lewenberg | Bitcoin mining pools: A cooperative game theoretic analysis[END_REF] the authors use cooperative games to prove that pool-hopping is not preventable, thus mining pools are not stable coalitions.

Our contribution. Starting from the model in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF], the goal of this work is to propose an alternative incentive compatible rewarding mechanism discouraging the pool-hopping practice. By reinterpreting the reward function in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] as an outcome of a bankruptcy situation, we construct, analyze and test a new rewarding mechanism adoptable by pools to remunerate contributing miners.

The paper is structured as follows. Section 2 presents the basic model for mining pool and some definitions about bankruptcy situations. In Section 3, we introduce a reward function from the literature, we compare it with a new one (based on a modified version of the CEL rule for bankruptcy situation) and we show that the two are equivalent with respect to incentives in reporting shares or full solutions. Then, in Section 4, we compare these two methods from a multi-pool perspective by showing (also with the aid of simulations) that the CEL-based reward function performs better than the one from the literature in discouraging miners to hop from a pool to another. Section 5 concludes the paper.

Preliminaries

The model

Let N = {1, . . . , n} be a finite set of miners. Time is split into rounds, i.e., the period it takes any of the miner in the pool to find a full solution. During a round miners participate in the mining race and report their shares (and the full solution) to the pool manager. Once the full solution is submitted, the pool manager broadcasts the information to the network and receives the block reward B. Then, the pool manager redistributes the block reward B among the miners according to a pre-defined reward function. The round is then concluded and a new one starts. For the sake of simplicity we set B = 1.

The situation is represented by the vector s = (s 1 , s 2 , ..., s n ) ∈ N N , defined as history transcript, that contains the number of shares s i reported by each miner i ∈ N in a round. Letting S = i∈N s i be the total number of reported shares, the reward function R : N N → [0, 1] n , according to [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF], is a function assigning to each history transcript s an allocation of the reward (R 1 (s), . . . , R n (s)), where R i denotes the fraction of reward gained by the single miner i ∈ N and i∈N R i = B = 1.

Following the approach in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF], under the assumption of rationality, miners want to maximize their individual revenues over time. Let K be the numbers of rounds that have been completed at time t and let s j be the transcript history for any round j ∈ K. Given a reward function R, a miner i ∈ N will adopt a strategy (i.e., the number of reported shares at each round j) aimed at maximizing her total reward given by

lim t→+∞ j∈K R i (s j ),
where a strategy affects both the number of completed rounds and the number of reported shares.

In [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF], a reward function R is said to be incentive compatible if each miner's best response strategy is to immediately report to the pool a share and a full solution. Assuming that (i) one single pool represents the total mining power (normalized to 1) of the network and that (ii) each miner i ∈ N has a fraction α i of the hashing power, then the probability for a miner i to find a full solution is α i . Under this assumption, Schrijvers et al. [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] show that a miner i ∈ N has an incentive to immediately report her shares if and only if the reward function R is monotonically increasing (i.e., R i (s + e i ) > R i (s) for all history transcripts s, where e i = (e i 1 , . . . , e i n ) ∈ {0, 1} N is a vector such that e i j = 0 for each j ∈ N \{i} and e i i = 1.). Moreover, they show that a miner i ∈ N , finding a full solution at time t, has an incentive to immediately report it if and only if the following condition holds:

n j=1 α j • R i (s t + e j ) -R i (s t ) ≤ E s [R i (s)] D (1)
for all vectors of mining powers (α i ) n i=1 and all history transcripts s t , where E s [R i (s)] is the expected reward for miner i over all possible history transcripts. Condition (1) results from the comparison of the withholding strategy -i.e., s:S=1 P(find s)

• R i (s t + s) -with the honest one -i.e., R i (s t ) + Es[Ri(s)] Es[S]
-knowing the fact that the total number of submitted shares in a round, S = i∈N s i , follows a geometrical distribution of parameter p = 1 D (i.e., the probability for a share to be a full solution), where D is the difficulty of the crypto puzzle. Therefore, the value of the parameter D corresponds to the average number of submitted shares in a round.

Bankruptcy situations

We now provide some game-theoretical basic definitions. A bankruptcy situation arises whenever there are some agents claiming a certain amount of a divisible estate, and the sum of the claims is larger than the estate. Formally, a bankruptcy situation on the set N consists of a pair (c, E) ∈

R N × R with c i ≥ 0 ∀i ∈ N and 0 < E < i∈N c i = C.
The vector c represents agents' demands (each agent i ∈ N claims a quantity c i ) and E is the estate that has to be divided among them (and it is not sufficient to satisfy the total demand C).

We denote by B N the class of all bankruptcy situations (c,

E) ∈ R N × R with 0 < E < i∈N c i
A solution (also called allocation rule or allocation method ) for bankruptcy situations on N is a map f : B N → R N assigning to each bankruptcy situation in B N an allocation vector in R N , which specifies the amount

f i (c, E) ∈ R of the estate E that each agent i ∈ N receives in situation (c, E).
A well-known allocation rule in the literature is the Constrained Equal Losses (CEL) rule, which is defined in the following definition (see, for instance, [START_REF] Herrero | The three musketeers: four classical solutions to bankruptcy problems[END_REF][START_REF] Thomson | Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: an update[END_REF] for more details on bankruptcy situations and the CEL rule).

Definition 1 (Constrained equal losses rule (CEL)). For each bankruptcy situation (c, E) ∈ B N , the constrained equal losses rule is defined as CEL i (c, E) = max(c i -λ, 0) where the parameter λ is such that i∈N max(c i -λ, 0) = E.

Incentive Compatible Reward Functions

Schrijvers et al. [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] introduce a reward mechanism that fulfills the property of incentive compatibility using the identity of the full solution discoverer w. Given a vector e w = (e w 1 , . . . , e w n ) ∈ {0, 1} N such that e w i = 0 for each i ∈ N \ {w} and e w w = 1, the incentive compatible reward function R is the following:

R i (s; w) =      si D + e w i 1 -S D , if S < D si S , if S ≥ D ∀i ∈ N, (2)
where s i is the number of shares reported by miner i, S is the total number of reported shares in a round and D is the crypto puzzle difficulty. This function rewards miner i proportionally to the submitted shares in the case S ≥ D. On the other hand, in the case S < D, each miner receives a fixed reward-per-share equal to 1 D and the discoverer w of the full solution receives, in addition, all the remaining amount 1 -S D . So, in both cases, i∈N R i (s; w) = B = 1. Roughly speaking, the reward function R is the combination of two distinct allocation methods. In a short round, i.e., when the total amount of reported shares is smaller than the difficulty D of the original problem, the reward function allocates a fixed amount-per-share to all agents equal to 1 D , but the agent w who finds a solution is rewarded with an extra prize. Instead, in a long round, i.e., when the total amount of reported shares exceeds the difficulty of the problem, the reward function allocates the reward proportionally to the individual shares.

Remunerating miners in a per-share fashion, for long rounds, would lead pool going bankrupt since the reward B results insufficient to pay out all the reported shares. For long rounds, the rewarding mechanism proposed in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] is nothing more than a solution to a bankruptcy situation.

Therefore, it is possible to create new reward functions by simply substituting in long rounds (i.e., in bankruptcy situations) different bankruptcy solutions.

Let us now create a new rewarding mechanism based on the CEL rule defined in Section 2.2 and let us compare the properties of the two allocation methods in long rounds. In order to preserve incentive compatibility we define a CEL-based reward function.

Definition 2. Given the identity of the full solution discoverer w, the CEL-based reward function R is defined as follows:

R i (s; w) =      si D + e w i 1 -S D , if S < D e w i D + max si D -λ, 0 , λ : i max si D -λ, 0 = 1 -1 D , if S ≥ D ∀i ∈ N,
where e w = (e w 1 , . . . , e w n ) ∈ {0, 1} N is a vector such that e w w = 1 and e w i = 0 ∀i ∈ N \ {w}, s i is the number of shares reported by miner i, S = i∈N s i is the total number of reported shares in a round and D is the crypto puzzle difficulty.

We assign to agent w, who finds the solution during a long round, an extra prize of By Definition 2, now λ = 0.3 and we have that: R((2, 7, 8); 1) = (0.1, 0, 0) + CEL((0.2, 0.7, 0.8), 0.9) = (0.1, 0, 0) + (0, 0.4, 0.5) = (0.1, 0.4, 0.5).

In order to prove that the CEL-based rule is incentive compatible we need to present some preliminary results. More precisely, to express Condition [START_REF] Back | Hashcash -a denial of service counter-measure[END_REF] for this new reward function we need to focus on the parameter λ of the definition. This parameter depends on miners' demands and it changes value from round to round. It is important to analyze how the parameter varies if an additional share is found. Let us denote by: (i) λ 1 the value of the parameter λ when miner i finds the full solution and immediately reports it to the pool and, (ii) λ 2 the value of the parameter after delaying in reporting the full solution by one additional share. By convention, if miner i finds the additional share the parameter is denoted as λ 1 2 , while if any other miner finds it we have λ 2 2 .

By analyzing the different values of the parameter λ it is possible to derive the following result:

Proposition 1. Let us consider CEL i (c, E) = max(c i -λ 1 , 0) and CEL i (c + e j , E) = max(c i - λ 2 , 0). For each (c, E) ∈ B N , i, j ∈ N we have that λ 1 ≤ λ 2 .
Proof. Let us report the efficiency condition for the two allocations:

max(c j -λ 1 , 0) + i∈N \{j} max(c i -λ 1 , 0) = max(c j + 1 -λ 2 , 0) + i∈N \{j} max(c i -λ 2 , 0). If c j ≤ λ 1 , efficiency condition implies that i∈N \{j} max(c i -λ 1 , 0) ≥ i∈N \{j} max(c i -λ 2 , 0).
Hence, λ 1 ≤ λ 2 . For c j > λ 1 let us assume, by contradiction, that λ 1 > λ 2 . The assumption implies that i∈N \{j} max(c i -λ 1 , 0) ≤ i∈N \{j} max(c i -λ 2 , 0). However, max(c j -λ 1 , 0) = c j -λ 1 < c j -λ 2 < c j + 1 -λ 2 = max(c j + 1 -λ 2 , 0) and this leads to contradiction.

Corollary 1. Given the situation of Proposition 1 we have that:

λ 2 -1 D ≤ λ 1 ≤ λ 2 .
Now, we are ready to prove the incentive compatibility of the new reward function based on the CEL rule.

Proposition 2. The CEL-based reward function R of Definition 2 satisfies the property of incentive compatibility.

Proof. Let us write down Condition (1) for R:

α i 1 D + max s i + 1 D -λ 1 2 , 0 - 1 D -max s i D -λ 1 , 0 + (1 -α i ) max s i D -λ 2 2 , 0 - 1 D -max s i D -λ 1 , 0 ≤ E s [ R i (s; w)] D .
Since the average reward E s [ R i (s; w)] is positive, the right hand side is positive. Therefore, the condition is fulfilled if the left hand side is not positive.

Due to Proposition 1 and Corollary 1 we have that:

si D -λ 2 2 ≤ si D -λ 1 ≤ si+1 D -λ 1 2
. If all the terms in the form max(•, 0) are positive, then the condition is fulfilled:

α i 1 D -λ 1 2 + λ 1 + (1 -α i ) -λ 2 2 - 1 D + λ 1 ≤ max(α i , 1 -α i )(-λ 1 2 -λ 2 2 + 2λ 1 ) ≤ 0. If si D -λ 2 2 ≤ 0 ≤ si D -λ 1 we get: α i 1 D -λ 1 2 + λ 1 + (1 -α i ) - s i D - 1 D + λ 1 ≤ max(α i , 1 -α i )(-λ 1 2 - s i D + 2λ 1 ) ≤ 0. If si D -λ 1 ≤ 0 ≤ si+1 D -λ 1 2
we get:

α i s i + 1 D -λ 1 2 + (1 -α i ) - 1 D ≤ max(α i , 1 -α i ) s i D -λ 1 2 ≤ max(α i , 1 -α i ) s i D -λ 1 ≤ 0.
In the end, if all the terms in the form max(•, 0) are equal to 0, then the condition is fulfilled, since the left hand side is negative.

A multi-pool analysis

Pool-hopping consists of a practice in which miners leave a pool to join another one that is considered more attractive in terms of remuneration. More precisely, during a round a miner performing pool hopping (i.e., a hopper ) stops submitting shares to the pool she was working with at the beginning of the round and starts submitting shares to a different one. A hopper leaves, during a mining race, a pool entering (or already in) a long round for a pool that is currently in a short round. The hopping miner receives an increasing reward from the brand new pool (in short round) and a decreasing reward from the pool left (facing a bankruptcy situation where the resource B is insufficient to remunerate the working miners).

In a multi-pool framework, the total mining power of the network is represented by different mining pools each with its own computational power. Differently from Section 2.1, each miner i ∈ N is characterized by α i that now represents a fraction of the pool hashing rate. Indeed, in the single-pool framework, we denote with α i the fraction of the total hashing power.

Hopping affects the actual rewards of a pool. If a miner performs pool hopping the pool loses computational power and so on average the full solution is found later, i.e., the rounds become longer.

In our multi-pool analysis, we assume that pool hopping is performed at the very beginning of a long round and that miners hop between two pools adopting the same rewarding mechanism.

Every mean denoted as E[•] is considered conditioned to the fact that the miner is in a long round:

E s [•|S > D]
. From now on, we mark with an asterisk ( * ) every variable defining the reward of miners once pool hopping is performed.

Hopping Analysis on Schrijver's Rewarding Function

When miner i is remunerated with reward function R her incentive to perform pool hopping can be measured as the difference between (i) the average reward when hopping E[R * i ] and (ii) the average reward E[R i ] when working for the pool: Proof. As shown in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF], the average reward of an honest miner i ∈ N , i.e., not hopping, is:

δ hop := E[R * i ] -E[R i ].
E[R i ] = α i .
A hopper (hopping at time t) receives an increasing reward from the new pool in a short round and a decreasing one from the pool left. The sum of the two represents the total reward. On average at the end of a short round (S = D) a miner has found α i • D shares. The round finishes after D + t shares are found, with t ∈ [0, +∞), hence the reward for the miner who performs pool hopping is the following:

E[R * i ] = ∞ t=0 α i t D + α i D D + t p (1 -p ) t > α i 1 -α i > α i ,
where p = 1-αi D is the probability that a share found by an honest miner is a full solution, t is the time taken by an honest miner (working for the old pool) to find a new share and R * i is the reward obtained by a miner who hops from a pool rewarding with R to another pool using the same reward function. Hence, the incentive to perform pool hopping is always positive:

δ hop = E[R * i ] -E[R i ] > α i -α i = 0.
A second result deriving from Proposition 3 is the fact that, on average, the hopping miners gain more than their hashing ratio α i . This has been empirically verified on the Bitcoin network in [START_REF] Belotti | Bitcoin pool-hopping detection[END_REF]. The average reward for a hopper, between pools adopting R, can be analytically computed according to the following result.

Proposition 4. The average reward of miner i ∈ N hopping between two different pools remunerating miners according to the reward function R is the following:

E[R * i ] = α i 1 -α i + α * i ,
where

α * i = α i (1 -α i )e 1-αi (-Ei(α i -1)) with Ei(x) = x -∞ e t
t denoting the exponential integral.

Proof. On average, a miner with computational power α i who performs pool hopping receives:

E[R * i ] = ∞ t=0 α i t D p (1 -p ) t + ∞ t=0 α i D D + t p (1 -p ) t .
The first term represents the reward received by the new pool in short round that can be easily computed as follows:

α i D ∞ t=0 t • p (1 -p ) t = α i D • D 1 -α i = α i 1 -α i .
The second term (denoted as α * i ) corresponds to the reward assigned by the pool left by the hopping miner. In order to compute this term we need to consider an approximation for D → ∞:

α * i = ∞ t=0 α i D D + t 1 -α i D 1 - 1 -α i D t ≈ α i (1 -α i )e 1-αi ∞ t=D 1 t e -1-α i D t .
The computations can be solved by defining:

f (x) := lim D→∞ f D (x) = lim D→∞ ∞ t=D 1 t e -tx D .
Using Lebesgue's theorem and given the constraint lim x→∞ f (x) = 0 we get:

f (x) = -Ei(-x).
Hence:

α * i ≈ α i (1 -α i )e 1-αi f (1 -α i ) = α i (1 -α i )e 1-αi (-Ei(α i -1)).
Thanks to the result provided by Proposition 4 we note that the shares submitted in the pool left by the hopping miner (α * i ) represent an important part of her average reward. More precisely, for values of α i < 0.39, α * i is more than the 50% of the average reward a miner would have got by not leaving the pool (i.e., her computational power α i ). For instance, if a miner has α i = 0.2 as computational power, she will get α * i ≈ 0.11.

Hopping Analysis on CEL-based Rewarding Function

Following similar arguments, we can analyze the incentive to perform pool hopping when adopting the CEL-based rule R. We can, then, compare the results obtained for the reward function R with the ones provided by R. We denote as β i the average reward of function R (corresponding to α i for function R) that can be computed as follows since the probability for a miner i to find a full solution and to receive the extra prize 1 D is α i :

β i = E[ R i ] = α i D + E max s i D -λ, 0 λ : i max s i D -λ, 0 = 1 - 1 D .
Like in Section 4.1, let us define the incentive to perform pool hopping

δ hop := E[ R * i ] -E[ R i
] and let us compute the average reward received by a hopper:

E[ R * i ] = ∞ t=0 α i t D + max α i D D -λ, 0 p (1 -p ) t = α i 1 -α i + E [max(α i -λ, 0)] ,
where p = 1-αi D , t is the time taken by an honest miner to find a new share and R * i is the reward obtained by a hopping miner. Analogously to α * i for function R, we denote by β * i the reward given by the pool the hopper left:

β * i = E [max(α i -λ, 0)] .
Hence we have that:

δ hop = E[ R * i ] -E[ R i ] = α i 1 -α i + β * i -β i .

Comparison of the two Rewarding Functions in a multi-pool framework

We have, now, the metrics to compare the performance of the reward functions R and R in hopping situations. Both rewarding systems present an incentive to hop in long rounds, however the miner rewarded with the CEL-based reward function are less incentivized. It is possible to compare the incentives δ hop , δhop given by the two functions R, R through the variables introduced in Section 4.2 since:

δhop ≤ δ hop ⇔ β i -β * i ≥ α i -α * i .
In order to show that the hopping incentive for the CEL-based reward function is lower with respect to the incentive given by R it is sufficient to prove that

β i -β * i ≥ α i -α * i .
Proposition 5. Let N be the ordered set of miners:

α 1 ≤ α 2 ≤ • • • ≤ α n ,
let us define α >i := j>i α j , as the global computational powers of the miners that are more powerful than α i . Then,

β i -β * i ≥ α i -α * i if (1 -α i )(α >i -α i )e -αi+(α>i-αi) -1 (-Ei(α i -1)) ≥ 1 where Ei(•) is the exponential integral function.
Proof. Given the definitions of β i and β * i :

β i = α i D + ∞ t=0 max α i + α i t D -λ, 0 p(1 -p) t and β * i = ∞ t=0 max (α i -λ, 0) p (1 -p ) t ,
let us recall that p = 1 D is the probability for a share to be a full solution and that p = 1-αi D represents the probability for a share reported by an honest miner to be a full solution.

For t → ∞ (i.e., for very long rounds) the function max(•, 0) either tends to 0 or to 1 since in long rounds eventually the most powerful miner is receiving all the reward (max(•, 0) → 1) and the other miners are receiving none of it (max(•, 0) → 0). The limit value 0 is reached for t = γ i • D, where γ i ∈ R ∪ {+∞} is defined as follows; γ i := argmin γ { αit D -λ < 0, ∀t ≥ γD}. Roughly speaking, γ i • D represents the number of shares after which miner i is not rewarded.

Hence, it is possible to rewrite β i and β * i in this form:

β i = α i D + γiD t=0 α i + α i t D -λ p(1 -p) t and β * i = γiD t=0 (α i -λ) p (1 -p ) t .
The value of γ i might change if the miner is performing pool hopping, but for the sake of simplicity we approximate by considering the same γ i in both cases.

Assuming that t λ • p(1 -p) t ≈ t λ • p (1 -p ) t we can approximate the difference between β i and β * i as follows:

β i -β * i ≈ α i D + γiD t=0 α i t D p(1 -p) t .
Due to the value of the difficulty D, we can consider the limit for D → ∞, then:

β i -β * i ≈ α i D + γiD k=0 α i k D 1 D e -k/D = α i D + α i 1 D 2 γiD k=0 ke -k/D → α i (1 -e -γi (1 + γ i )).
Let us now compute explicitly γ i . If i = N (i.e., α i = argmax j {α j }) then γ i = ∞. Otherwise at time t = γ i • D the miners who receive a positive reward are all the j ∈ N : α j > α i , i.e., all the ones having larger computational power than i. According to the CEL rule definition we get the following balance equation:

j>i α j 1 + t D -λ = 1 - 1 D ≈ 1.
Since the time t = γ i • D is the moment when the value max(α i (1 + t D ) -λ, 0) turns from positive to null, we can say that α i (1 + t D ) -λ ≈ 0. Therefore we have that:

j>i α j 1 + t D -α i 1 + t D = 1.
Replacing the value of t with γ i • D we get (α >i -(N -i)α i )(1 + γ i ) = 1, then:

γ i = ((α >i -(N -i)α i ) -1 -1).
Now we can find a lower bound for γ i (since N -i ≥ 1) and so for β i -β * i :

γ i ≥ γi := ((α >i -α i ) -1 -1) =⇒ β i -β * i ≥ α i (1 -e -γi (1 + γi )).

The sufficient condition for β

i -β * i ≥ α i -α * i is: α i (1 -e -γi (1 + γi ) ≥ α i -α * i .
We get the statement of the proposition by replacing γi and α * i with their explicit formulas.

Thanks to Proposition 5, given miner i's hashing ratio (i.e., α i ) and the power of the miners who are stronger than i (i.e., α >i ), we can check whether R is giving a lower hopping incentive than the one given by R (i.e., check whether δhop ≤ δ hop ) by simply applying the sufficient condition introduced above that we denote as f (α i , α >i ):

f (α i , α >i ) := (1 -α i )(α >i -α i )e -αi+(α>i-αi) -1 (-Ei(α i -1)) ≥ 1.
Let us analyze the hopping performance of R and R in the following example.

Example 2. Given 5 miners ordered according to their hash rates: α 1 = 0.10 α 2 = 0.15, α 3 = 0.20, α 4 = 0.25, α 5 = 0.30, using the condition provided by Proposition 5 we get:

• f (α 1 , α >1 ) = f (0.10, 0.90) = 0.59 < 1, miner 1 has a greater incentive to perform pool hopping if rewarded with R rather than with R;

• f (α 2 , α >2 ) = f (0.15, 0.75) = 0.66 < 1, miner 2 has a greater incentive to perform pool hopping if rewarded with R rather than with R;

• f (α 3 , α >3 ) = f (0.20, 0.55) = 1.24 > 1, miner 3 has a greater incentive to hop if rewarded with R rather than with R;

• f (α 4 , α >4 ) = f (0.25, 0.30) > 10 6 > 1, miner 4 has a greater incentive to hop if rewarded with R rather than with R;

• f (α 5 , α >5 ) = f (0.30, 0) → ∞ > 1, miner 5 has a really low incentive to perform pool hopping if rewarded with R.

We can see that miners representing the 75% of the pool's computational power have a lower incentive to perform pool hopping when the CEL-based rewarding mechanism is adopted.

By analyzing function f (•, α >i ) -i.e., fixing α >i -we can identify the cases in which δhop ≤ δ hop (where R performs better than R). For instance, f (•, α >i ) > 1 for every α >i < 0.4, means that with R not only the miners representing the most powerful 40% of the pool have a lower incentive to perform pool hopping, but also the miner i who just follows in the ranking.

To compare the two reward functions, it is necessary to estimate the percentage of miners who have a lower incentive to perform pool hopping. In Example 2 this percentage is p(α = {0.1, 0.15, 0.2, 0.25, 0.3}) = 75%. Formally we would like to estimate:

p(α) := i α i • 1 {βi-β * i ≥αi-α * i } .
We know that p(α) > 40% thanks to the analysis of function f . In order to get a better idea of the range of the value of function p we perform a simulation.

Simulation. Due to the unpredictability of α, we assume that it comes from a random distribution.

More precisely, given X i ∼ U [0, 1], α i is defined as follows: α i := Xi j Xj . We run a simulation with 100 different samples of α for n miners, with n ∈ {3, 10, 20, 30, 50}, and estimate the CDF of p n (α) for every n. We compute explicitly β i and β * i , without using the approximation above introduced. The functions p n (α) have almost always values over 0.5 (i.e., in just two cases out of 100 with n = 3, p 3 (α) achieves value between 0.47 and 0.5). This means that in most of the cases the majority of the miners have a lower incentive to perform pool-hopping with R rather than R.

Conclusion

The paper analyzes the robustness of two different rewarding mechanisms in both intra-pool and inter-pool environments. Schrijvers et al. introduce in [START_REF] Schrijvers | Incentive compatibility of bitcoin mining pool reward functions[END_REF] a reward function R that is incentive compatible. However, this rule gives miners an incentive to leave pools in long rounds to join pools in short rounds that adopt the same rewarding system (i.e., pool-hopping).

By reinterpreting R, in long rounds, as an allocation rule for a bankruptcy situation, we create a new rewarding function R inspired to the well-known Constrained Equal Loss (CEL) rule.

We show that this CEL-based rule is incentive compatible as R but it provides to most of the miners a lower incentive to perform pool hopping in long rounds. In conclusion, if a pool wants to tackle this issue, the proposed rewarding function R is the one to be recommended.

1 1 D 1 D 1 D 1 . 1 .

 111111 D to add to the allocation established by the classical CEL rule for the bankruptcy situation (c, E) = • s, 1 -e w i D , with the estate reduced by 1 D . More precisely, in long rounds R i (s; w) = • s, 1 -e w i D . In other words, it means that 1 is added to the count of the shares s i reported by the full solution discoverer w. If the value si D -λ is negative, by default, the agent w is receiving . This incentive is sufficient to make the reward function incentive compatible. Before proving this statement, let us compare the allocations provided by the classical CEL rule and R through an example with n = 3, D = 10 and E = Example Given the following bankruptcy situation: s = (2, 7, 8), miner 1 finds the full solution (w = 1) and (c, E) = ((0.2, 0.7, 0.8), 1). By Definition 1, it is easy to check that λ = 0.25, hence: CEL(c, E) = (0, 0.45, 0.55). Now, consider the new CEL-based rule R, a prize of 1 D = 0.1 is allocated to miner 1, and a new bankruptcy situation (c, E ) arises where the estate is reduced by 0.1; (c, E ) = ((0.2, 0.7, 0.8), 0.9).

Proposition 3 .

 3 The reward function R proposed by Schrijvers et. al. always gives miners a positive incentive δ hop > 0 to perform pool hopping.

Fig. 1 .

 1 Fig. 1. CDF of every pn(α), with n ∈ {3, 10, 20, 30, 50}.