Patrick Roberts
email: roberts@shh.mpg.de

Chris Hunt

Manuel Arroyo-Kalin

Damian Evans

Nicole Boivin

The deep human prehistory of global tropical forests and its relevance for modern conservation

Keywords: Anthropocene, Homo sapiens, Tropical forests, Archaeology, Late Pleistocene, Holocene

Significant human impacts on tropical forests have been considered the preserve of recent societies, linked to large-scale deforestation, extensive and intensive agriculture, resource mining, livestock grazing, and urban settlement. Cumulative archaeological evidence now demonstrates, however, that Homo sapiens has actively manipulated tropical forest ecologies for at least 45,000 years. It is clear that these millennia of impacts need to be taken into account when studying and conserving tropical forest ecosystems today. Nevertheless, archaeology has so far provided only limited practical insight into contemporary human-tropical forest interactions. Here, we review significant archaeological evidence for the impacts of past hunter-gatherers, agriculturalists, and urban settlements on global tropical forests. We compare the challenges faced, as well as the solutions adopted, by these groups with those confronting present-day societies, which also rely on tropical forests for a variety of ecosystem services. We emphasise archaeology's importance not only in promoting natural and cultural heritage in tropical forests, but also in taking an active role to inform modern conservation and policy-making.

invitations to tropical forest conservation workshops in Xalapa (2015) and Mexico City (2017). The discussions that took place during these three workshops informed and shaped the early stages of this manuscript. We would also like to extend our thanks

Introduction

By 2050, it is estimated that over half of the world's population will live in the tropics, with many people relying on tropical forests as a source of freshwater, agricultural land, and urban land, as well as timber, medicine, and food [START_REF]State of the Tropics. State of the Tropics 2016 report[END_REF] . The expansion of human populations into tropical forest environments has seen the latter become some of the most threatened ecosystems in the world [START_REF] Gardner | Prospects for tropical forest biodiversity in a human-modified world[END_REF][START_REF] Ghazoul | Tropical rain forest ecology, diversity, and conservation[END_REF] : every day c. 320 km 2 of tropical rainforest is destroyed, significantly impacting human populations along with 135 plant, animal, and insect species [START_REF]Measuring the daily destruction of the world's rainforests[END_REF] . The ongoing viability of dry tropical forests is also under serious threat [START_REF] Dryflor | Plant diversity patterns in neotropical dry forests and their conservation implications[END_REF] . These alterations affect ecosystems that are central to the stability of Earth's atmosphere and climate [START_REF] Martin | On the edge: the state and fate of the world's tropical rainforests[END_REF] , as well as key providers of economic goods and ecosystem services [START_REF] Gardner | Prospects for tropical forest biodiversity in a human-modified world[END_REF] .

Focus on recent impacts to tropical forests has tended to promote these ecosystems as pristine and relatively untouched until recent centuries or even decades. Nevertheless, cumulative archaeological interest, spurred on by the application of novel methods of site discovery [START_REF] Evans | Airborne laser scanning as a method for exploring long-term socio-ecological dynamics in Cambodia[END_REF] , archaeological science research (e.g. [START_REF] Denham | Origins of agriculture at Kuk Swamp in the Highlands of New Guinea[END_REF][START_REF] Barton | The case for rainforest foragers: The starch record at Niah Cave, Sarawak[END_REF][START_REF] Arroyo-Kalin | The Amazonian Formative: crop domestication and anthropogenic soils[END_REF][START_REF] Roberts | Direct evidence for human reliance on rainforest resources in late Pleistocene Sri Lanka[END_REF] ), and palaeoenvironmental reconstruction (e.g. [START_REF] Barker | The 'human revolution' in lowland tropical Southeast Asia: the antiquity and behaviour of anatomically modern humans at Niah Cave (Sarawak, Borneo)[END_REF][START_REF] Hunt | A 50,000-year record of late Pleistocene tropical vegetation and human impact in lowland Borneo[END_REF] ), have increasingly demonstrated tropical forests to be dynamic 'artefacts' of millennia of human-forest interaction [START_REF] Barton | Long-term perspectives on human occupation of tropical rainforests: An introductory overview[END_REF][START_REF] Mcmichael | Ancient human disturbances may be skewing our understanding of Amazonian forests[END_REF] . Attempts to investigate the relationship between, on the one hand, prehistoric fire regime alteration, cultivation [START_REF] Piperno | The Origins of Agriculture in the Lowland Neotropics[END_REF] , extensive sedentary settlement, and enduring landscape modification [START_REF] Arroyo-Kalin | Slash-burn-and-churn: Landscape history and crop cultivation in pre-Columbian Amazonia[END_REF][START_REF] Heckenberger | Pre-Columbian urbanism, anthropogenic landscapes and the future of the Amazon[END_REF] , and, on the other, sustainable past subsistence, water-use, and intensive human occupation, have so far been limited. This is so despite recent calls from UNESCO [START_REF]Exploring Frameworks for Tropical Forest Conservation: managing production and consumption for sustainability[END_REF] , and a broad range of researchers [START_REF]Beyond Tropical deforestation: From tropical deforestation to forest cover dynamics and forest development[END_REF][START_REF] De Dapper | Tropical forests in a changing global context[END_REF] to actively involve archaeologists in conservation and policy-making in tropical forests.

Awareness of long-term anthropogenic impacts to tropical forests has only gradually emerged. As recently as the 1980s and 1990s, anthropologists argued that tropical forests were unattractive environments for human occupation (e.g. [START_REF] Bailey | Hunting and gathering in tropical rain forest; Is it possible?[END_REF] ). This view was further promoted by archaeologists, who, for example, saw tropical forests as barriers to the expansion of Late Pleistocene Homo sapiens foragers [START_REF] Gamble | Timewalkers: The prehistory of global colonization[END_REF] , and also deemed them incapable of supporting agricultural populations [START_REF] Grollemund | Bantu expansion shows that habitat alters the route and pace of human dispersals[END_REF] . This bias has been exacerbated by the generally-poor preservation of organic archaeological remains in tropical forest environments (e.g. [START_REF] Stahl | Archaeology in the lowland American tropics: current analytical methods and recent applications[END_REF] ). Accordingly, scholarly assumptions about the timing of significant anthropogenic impacts on tropical forests generally point to the post-industrial era or, at the earliest, the colonial era of European 'discovery' [START_REF] Hemming | Tree of Rivers: The Story of the Amazon[END_REF][START_REF] Lewis | Defining the Anthropocene[END_REF] . Clearly, the accumulating database of archaeological and palaeoecological evidence for pre-industrial and pre-colonial tropical forest occupation and transformation has not been effectively communicated beyond a restricted set of sub-disciplines (though see [START_REF] Steege | Hyperdominance in the Amazonian Tree Flora[END_REF][START_REF] Mcmichael | Predicting pre-Columbian anthropogenic soils in Amazonia[END_REF][START_REF] Bush | Human disturbance amplifies Amazonian El Nino Southern Oscillation signal[END_REF][START_REF] Levis | Persistent effects of pre-Columbian plant domestication on Amazonian forest composition[END_REF] ). As a consequence, this evidence has only played a small role in discussions about the start date or characteristics of the Anthropocene (e.g. [START_REF] Smith | The onset of the Anthropocene[END_REF] but see [START_REF] Roosevelt | The Amazon and the Anthropocene: 13,000 years of human influence in a tropical rainforest[END_REF] ).

Here, we review evidence that has accumulated, primarily in recent decades, for the long-term human transformation of tropical forest ecosystems. Our review is not exhaustive, but rather seeks to highlight how recent studies, drawing on a suite of new archaeological science and palaeoecological methods, have dramatically altered understanding of tropical forest long-term histories globally. We focus on three modes of human impact that, over the long-term, stack up as broad but non-synchronous phases: a phase marked by deliberate forest burning, species translocation, and management of forest biota; a phase of agricultural cultivation and enduring landscape modification; and a phase of urban occupation and transformation of tropical forests. As will be seen, these modes are not mutually exclusive. We conclude by examining the implications of new archaeological and palaeoecological perspectives on the long-term prehistory of tropical forests for contemporary agendas of conservation, management, and resilience-building.

Early impacts

In the last ten years, the archaeologically-acknowledged start date of human inhabitation of tropical forests has quadrupled in age. There is now clear evidence for the use of tropical forests by our species in Borneo [START_REF] Barker | The 'human revolution' in lowland tropical Southeast Asia: the antiquity and behaviour of anatomically modern humans at Niah Cave (Sarawak, Borneo)[END_REF][START_REF] Hunt | A 50,000-year record of late Pleistocene tropical vegetation and human impact in lowland Borneo[END_REF][START_REF] Barker | Rainforest foraging and Farming in Island Southeast Asia, Vol. 1: The archaeology of the Niah Caves, Sarawak[END_REF] and Melanesia 35 by c. 45 ka; in South Asia by c. 36 ka [START_REF] Perera | People of the ancient rainforest: Late Pleistocene foragers at the Batadombalena rockshelter, Sri Lanka[END_REF] ; and in South America by c. 13 ka [START_REF] Roosevelt | In The First Americans: The Pleistocene Colonization of the New World[END_REF] . There are suggestions of earlier rainforest occupation c. 125 ka in Java [START_REF] Storm | Late Pleistocene Homo sapiens in a tropical rainforest fauna in East Java[END_REF][START_REF] Westaway | Age and biostratigraphic significance of the Punung rainforest fauna, East Java, Indonesia, and implications for Pongo and Homo[END_REF] , c. 60 ka in the Philippines [START_REF] Mijares | New evidence for a 67,000-year-old human presence at Callao Cave, Luzon, Philippines[END_REF] , c. 100 ka in China [START_REF] Liu | The earliest unequivocally modern humans in southern China[END_REF] , and in Africa perhaps from the first appearance of Homo sapiens c. 200 ka [START_REF] Mercader | Forest people: The role of African rainforests in human evolution and dispersal[END_REF] , though further research is required to verify these cases [START_REF] Roberts | Tropical forests and the genus Homo[END_REF] . Early modern humans adapted to diverse tropical forest formations, ranging from the sub-zero temperatures of montane forests to dense, humid, evergreen rainforests, undertaking sophisticated forest mammal hunting and plant processing (e.g. [START_REF] Barker | Archaeological Investigations in the Niah Caves[END_REF] ). Moreover, people did not just adapt passively to these environments, but from the onset modified them in fundamental ways [START_REF] Arroyo-Kalin | The Amazonian Formative: crop domestication and anthropogenic soils[END_REF][START_REF] Gnecco | Against ecological reductionism: Late Pleistocene hunter-gatherers in the tropical forests of northern South America[END_REF] , with outcomes that have affected the natural histories of these forests to the present day.

In Southeast Asia, mounting evidence points to deliberate anthropogenic biomass burning in order to create forest-edge habitats from first human arrival c. 45 ka [START_REF] Hunt | A 50,000-year record of late Pleistocene tropical vegetation and human impact in lowland Borneo[END_REF][START_REF] Summerhayes | Human adaptation and plant use in Highland New Guinea 49,000 to 44,000 years ago[END_REF] (Figure 1). This may reflect reliance on starchy forest edge plants and bearded pig attracted to canopy openings [START_REF] Barker | The 'human revolution' in lowland tropical Southeast Asia: the antiquity and behaviour of anatomically modern humans at Niah Cave (Sarawak, Borneo)[END_REF] . In tropical Australia, the decline of Araucaria and rise of Eucalypts and Casuarina has been correlated with the advent of anthropogenic biomass burning after 40 ka [START_REF] Kershaw | A complete pollen record of the last 230 ka from Lynch's Crater, north-eastern Australia[END_REF][START_REF] Moss | A late Quaternary marine palynological record (oxygen isotope stages 1 to 7) for the humid tropics of northeastern Australia based on ODP site 820[END_REF][START_REF] Bird | Humans, megafauna and environmental change in tropical Australia[END_REF] . Human landscape impacts have also been documented in the montane tropical forests of Highland New Guinea from 45-35 ka, even retarding vegetation re-colonization in the region following the Last Glacial Maximum [START_REF] Fairbairn | Pleistocene occupation of New Guinea's highland and subalpine environments[END_REF] . That early foragers could have played a significant role in reshaping newly colonized landscapes is also supported by evidence that later foragers did. For example, the first colonists of the eastern Caribbean in the mid-Holocene brought their foraging, collecting and hunting lifestyles with them, and engaged in modification and management of tropical ecosystems that is reflected in significant shifts in pollen and phytolith datasets [START_REF] Siegel | Paleoenvironmental evidence for first human colonization of the eastern Caribbean[END_REF] .

Still debated, but potentially even more significant in terms of long-term impact, is human involvement in Late Pleistocene tropical forest megafaunal extinctions, which are argued to have had anthropogenic, climatic or multivariate causes, and to have resulted in major changes to ecosystem structure [START_REF] Moss | A late Quaternary marine palynological record (oxygen isotope stages 1 to 7) for the humid tropics of northeastern Australia based on ODP site 820[END_REF] . While discussions of megafaunal extinctions in tropical forests have been relatively limited, these environments possessed diverse megafauna, which persist in parts of Africa and Asia [START_REF] Malhi | Tropical forests in the Anthropocene[END_REF] . In the New Guinea Highlands there is evidence for megafauna, including extinct marsupials (such as Maokopia ronaldii and Thylogale hopeii), at West Balim River c. 30 ka and at Nombe c. 25 ka, with their gradual demise following human arrival and subsequent biomass burning [START_REF] Fairbairn | Pleistocene occupation of New Guinea's highland and subalpine environments[END_REF][START_REF] Hope | A preliminary report of changing Quaternary mammal faunas in subalpine New Guinea[END_REF] . In the Amazon basin, megafaunal extinctions, such as those of large mastodons (Haplomastodon waringi) and ground sloths (Eremotherium laurillardi), significantly altered biodiversity, vegetation distributions, nutrient cycling and carbon storage in the region, with effects persisting to the present day [START_REF] Doughty | Megafauna extinction, tree species range reduction, and carbon storage in Amazonian forests[END_REF] , though the role of humans in this process has yet to be fully-explored (e.g. [START_REF] Rossetti | Reconstructing habitats in central Amazonia using megafauna, sedimentology, radiocarbon, and isotope analyses[END_REF] ).

Tropical forest foragers also reshaped landscapes through the active long-distance translocation of species. In Melanesia, people translocated small mammals for reliable protein from 20 ka [START_REF] Gosden | Report of the Lapita Homeland Project[END_REF] . The result is that species like bandicoot (Perameles sp.) and cuscus (Phalanger sp.) are now widely distributed across Melanesian islands, including the Bismarck Archipelago, where they are not endemic. Yams (Discorea alata) are present on both sides of the Wallace Line by 45 ka [START_REF] Barker | Rainforest foraging and Farming in Island Southeast Asia, Vol. 1: The archaeology of the Niah Caves, Sarawak[END_REF][START_REF] Paz | Rock shelters, caves, and archaeobotany in island Southeast Asia[END_REF] . By the Terminal Pleistocene or Early Holocene, a web of translocations seems to have carried economically-important plants, including the sago palm (Metroxylon sagu), yams (Discorea alata) and D. hispida, taro (Colocasia esculenta) and swamp taro (Alocasia longiloba), to the coastlands and islands of Southeast Asia, the Philippines, and Wallacea, and possibly also into North Australia [START_REF] Denham | Revisiting an old hypothesis: horticultural experimental in northern Australia[END_REF][START_REF] Denham | Early agriculture and plant domestication in New Guinea and Island Southeast Asia[END_REF][START_REF] Hunt | Early Holocene vegetation, human activity and climate from Loagan Bunut, Sarawak, Malaysian Borneo[END_REF] (Figure 1). Modification of the distribution and density of edible and economic tree species has also been observed among Amazonian hunter-gatherers [START_REF] Balée | Footprints of the forest: Ka'apar ethnobotany -the historical ecology of plant utilization by an Amazonian people[END_REF] .

Farming in the forest

The montane rainforests of New Guinea provide some of the earliest evidence for agricultural experimentation anywhere in the world [START_REF] Denham | Origins of agriculture at Kuk Swamp in the Highlands of New Guinea[END_REF][START_REF] Denham | Early agriculture and plant domestication in New Guinea and Island Southeast Asia[END_REF] . At Kuk Swamp, Terminal Pleistocene human foragers moved and tended tropical plants like yam (Dioscorea sp.), banana (Musa spp.), and taro (Colocasia sp.) until these species were fully 'domesticated' by the Early-Mid Holocene [START_REF] Denham | Origins of agriculture at Kuk Swamp in the Highlands of New Guinea[END_REF][START_REF] Golson | Foraging and Farming: The Evolution of Plant Exploitation[END_REF] . Both recent and ancient agricultural practices in this and other tropical forest regions were, however, combined with hunting/fishing and gathering. For example, while there was large-scale land management at Kuk Swamp, other surrounding sites demonstrate continued evidence for small mammal hunting [START_REF] Gaffney | Crossing the Pleistocene-Holocene transition in the New Guinea Highlands: Evidence from the lithic assemblage of Kiowa rockshelter[END_REF][START_REF] Roberts | Persistent tropical foraging in the highlands of terminal Pleistocene/Holocene New Guinea[END_REF] . Studies of early human activities in rainforest environments have helped to blur the boundaries between tropical forest hunter-gatherers and farmers, revealing sophisticated subsistence practices, such as transplantation and cultivation extending back to at least the early Holocene. Such studies highlight how even these small populations may have altered tropical forest environments (Figure 2).

The eventual domestication of tropical forest plants and animals, together with the incorporation of plants and animals domesticated outside of tropical forest environments, and the emergence of agricultural systems, reflect new thresholds in the intensifying relationship between humans and tropical forest environments. The scale of human selection on tropical forest species can be seen in the number of them that are central to global cuisine today, including sweet potato, manioc, chilli, black pepper, mango, yams, pineapple and banana [START_REF]Rethinking Agriculture: Archaeological and Ethnoarchaeological Perspectives[END_REF] (Figure 3). While domesticated tropical forest fauna are fewer in number, the now globally-distributed domestic chicken also most likely had a tropical forest origin in the form of the jungle fowl [START_REF] Eriksson | Identification of the yellow skin gene reveals a hybrid origin of the domestic chicken[END_REF] . Despite new crops, however, increasingly settled tropical forest communities also continued to practice the same agro-forestry systems developed by their forebearers, focused on the management of various tree species. For example, the first Polynesian occupants of the Chatham Islands brought with them translocated tree crops, important to arboriculture and agroforestry strategies (with lasting impacts on conservation efforts in these islands) [START_REF] Maxwell | The timing and importance of arboriculture and agroforestry in a temperate East Polynesia Society, the Moriori, Rekohu (Chatham Island)[END_REF] . Likewise stands of Brazil nut (Bertholletia excelsa) in the Amazon closely map onto ancient human settlements [START_REF] Shepard | Made in Brazil": Human Dispersal of the Brazil Nut (Bertholletia excelsa, Lecythidaceae) in Ancient Amazonia[END_REF] , reflecting long-term human interaction with and management of this species.

In addition to species domestication, translocation and clustering, the development of indigenous tropical forest agricultures during the Holocene also led to the intensive manipulation of drainage and the modification of soils. We have already mentioned the distinctive aspects of Early Holocene indigenous agriculture in Melanesia, which involved the formation of drainage ditches in order to prevent waterlogging of soils in planting areas [START_REF] Golson | Foraging and Farming: The Evolution of Plant Exploitation[END_REF] . In Amazonia, evidence from the Llanos de Mojos [START_REF] Lombardo | Pre-Columbian occupation patterns in the eastern plains of the Llanos de Moxos, Bolivian Amazonia[END_REF] and Guyanas 69 highlights how populations adapted to flooding conditions in order to intensify agricultural production. In areas now dominated by tropical rainforest, pre-Columbian settlement and fire-intensive land use practices resulted in the formation of expanses of fertile anthropic soils (Figure 2) known as terras pretas and terras mulatas [START_REF] Arroyo-Kalin | The Amazonian Formative: crop domestication and anthropogenic soils[END_REF][START_REF] Arroyo-Kalin | Slash-burn-and-churn: Landscape history and crop cultivation in pre-Columbian Amazonia[END_REF] . These may have been reutilized as fertile soilscape legacies by populations in the past, just as they are employed in the present.

Over their human history, tropical forests have also been influenced by expansions of neighbouring farming groups and crops. In Amazonia, the adoption of Mesoamerican maize (Zea mays) dates back to at least 6,000 BP [START_REF] Bush | A 6,000 year history of Amazonian maize cultivation[END_REF] and the plant was an important part of regional diets by the late Holocene [START_REF] Hermenegildo | New evidence for subsistence strategies of late pre-colonial societies of the mouth of the Amazon based on carbon and nitrogen isotopic data[END_REF] . In Africa, Bantu agriculturalists farming pearl millet and cattle appear to have expanded into the tropical rainforests of western and central Africa, c. 2.5 ka, when their extent was greatly contracted [START_REF] Grollemund | Bantu expansion shows that habitat alters the route and pace of human dispersals[END_REF] . This expansion is suggested to have resulted in severe erosion and forest fragmentation in eastern and central Africa [START_REF] Bayon | Intensifying weathering and land use in Iron Age Central Africa[END_REF] . Similarly, the arrival of rice and millet agriculture in the tropical forests of Southeast Asia is associated with large-scale forest clearance, particularly within the more deciduous forests to the north of the equatorial belt in mainland Southeast Asia, which would have been easier to burn [START_REF] Bellwood | Cultural and biological differentiation in Peninsular Malaysia: the last 10,000 years[END_REF][74] .

In the Caribbean Archaic and Ceramic periods, meanwhile, communities brought a variety of exogenous domesticates, including wild avocado (Persea americana), manioc (Manihot esculenta), dog (Canis lupus familiaris) and guinea pig (Cavia porcellus), into island tropical forests [START_REF] Fitzpatrick | Human Impacts and Adaptations in the Caribbean Islands: A Historical Ecology Approach[END_REF] . Early Polynesians similarly carried a range of domesticated crops, animals and commensals that have contributed to the alteration of tropical forests across the region [START_REF] Prebble | The late Quaternary decline and extinction of palms on oceanic Pacific islands[END_REF][START_REF] Prebble | Detecting the initial impact of humans and introduced species on island environments in Remote Oceania using palaeoecology[END_REF] . On Tonga, for example, tropical forest tree species declined in abundance following Polynesian colonisation [START_REF] Fall | Altered ecologies: Fire, climate and human influence on terrestrial landscapes[END_REF] . Extinctions also ensued. Estimates suggest that avian extinctions from the tropical Pacific after Polynesian colonisation and prior to European arrival numbered in the hundreds if not thousands [START_REF] Steadman | Extinction and biogeography of tropical Pacific birds[END_REF] .

Nevertheless, outside of more vulnerable island contexts, the adaptation of non-endemic domesticates to tropical forest environments did not generally result in significant or lasting environmental degradation in pre-industrial times. Indeed, most communities entering these habitats were initially at low population densities and appear to have developed subsistence systems that were tuned to their particular environments. This stands in stark contrast to the more recent effects of industrial monoculture and extensive cattle ranching in tropical forest settings. These practices, which induce rampant clearance, reduce biodiversity, provoke soil erosion, and render landscapes more susceptible to the outbreak of wild fires (e.g. [START_REF] Sheil | The impacts and opportunities of oil palm in Southeast Asia: What do we know and what do we need to know? Bogor, Indonesia[END_REF][START_REF] Fearnside | Rainforest burning and the global carbon budgest: biomass, combustion efficiency and charcoal formation in the Brazilian Amazon[END_REF] ), represent some of the greatest dangers facing tropical forests. Pre-industrial farming in tropical forests, which often employed fire in controlled fashion (e.g. [START_REF] Arroyo-Kalin | Slash-burn-and-churn: Landscape history and crop cultivation in pre-Columbian Amazonia[END_REF][START_REF] Iriarte | Fire-free land use in pre-1492 Amazonian savannas[END_REF] ), by contrast, relied on an intimate knowledge of forest dynamics and successful integration within the whole ecological system, and largely appears to have encouraged more flexible and resilient farming systems based around polyculture.

Forests of ruins or sustainable urbanism?

Public perceptions of archaeology in tropical forests often revolve around 'lost' temples that are only now being 'discovered', with romantic visions of vanished cities abandoned to the jungle [START_REF] Preston | Exclusive: Lost City Discovered in the Honduran Rain Forest[END_REF] . In places like Cambodia, however, these perceptions are deeply political and firmly grounded in colonialism [START_REF] Edwards | Cambodge: The Cultivation of a Nation, 1860-1945[END_REF] . Evocative images of the rise, fall and sudden 'collapse' of societies in these environments also owe much to 20 th century archaeological suggestions that large, permanent settlements could not be maintained due to the low fertility of tropical soils [START_REF] Meggers | Environmental limitation on the development of culture[END_REF] . Nevertheless, over the last two decades, archaeological data, including canopy-penetrating LiDAR mapping, have revealed previously unimagined scales of human settlement in the Americas and Southeast Asia [START_REF] Evans | Airborne laser scanning as a method for exploring long-term socio-ecological dynamics in Cambodia[END_REF][START_REF] Fisher | Identifying Ancient settlement patterns through LiDAR in the Mosquaitia region of Honduras[END_REF] . Indeed, extensive settlement networks in the tropical forests of Amazonia, Southeast Asia, and Mesoamerica clearly persisted many times longer than more recent industrial and urban settlements of the modern world have been present in these environments [START_REF] Heckenberger | Pre-Columbian urbanism, anthropogenic landscapes and the future of the Amazon[END_REF][START_REF] Webster | The Fall of the Ancient Maya: Solving the Mystery of the Maya Collapse[END_REF] .

Several challenges face urban populations in tropical forest environments today. For instance, floods and mudslides pose one of the greatest threats to modern urban settlements in tropical settings [START_REF] Larsen | Contemporary human uses of tropical forested watersheds and riparian corridors: ecosystem services and hazard mitigation, with examples from Panama, Puerto Rico, and Venezuela[END_REF] . In 1999, a high-magnitude storm in the Vargas region of northern Venezuela triggered flash floods and mudslides that killed between 10,000 and 15,000 people and destroyed c. 40,000 homes in one of the worst natural disasters in the recorded history of the Americas [START_REF] Larsen | Contemporary human uses of tropical forested watersheds and riparian corridors: ecosystem services and hazard mitigation, with examples from Panama, Puerto Rico, and Venezuela[END_REF] . Past urban populations clearly acknowledged such challenges and worked to mitigate them. For example, communities in and around the great temple-cities of the Angkor period in Cambodia developed large-scale hydrological infrastructure to both ensure access to water and divert excess flow away from settlements [START_REF] Evans | Airborne laser scanning as a method for exploring long-term socio-ecological dynamics in Cambodia[END_REF] (Figure 4). Similarly, archaeological evidence from c. 1.3 ka in Mesoamerica and Southeast Asia suggests both wetland modification and raised fields were deployed to minimize the impact of flooding on settlements [START_REF] Davis-Salazar | Late Classic Maya drainage and flood control at Copan, Honduras[END_REF][START_REF] Mcanany | Bellicose rulers and climatological peril? Retrofitting twenty-first century woes on eighth-century Maya society[END_REF] . Nevertheless, in some cases the ongoing danger of this high water-flow system could not be contained, with disastrous consequences. Such impacts have been observed, for example, in the remains of the settlements of the Khmer Empire, where hydraulic systems ultimately failed [START_REF] Evans | Airborne laser scanning as a method for exploring long-term socio-ecological dynamics in Cambodia[END_REF] . The archaeological record offers both mitigation strategies and cautionary tales.

Another major challenge to sustaining large populations in tropical forest habitats is the soil erosion that results from forest clearance and large-scale agricultural systems [START_REF] Beach | Impacts of the ancient Maya on soils and soil erosion in the central Maya Lowlands[END_REF][START_REF] Labrière | Soil erosion in the humid tropics: A systematic quantitative review[END_REF] . In Mesoamerica, certain Mayan communities appear to have 'gardened' the local forest for their resources rather than practicing forest clearance and monoculture farming [START_REF] Ford | The Maya Forest Garden: Eight Millennia of Sustainable Cultivation of the Tropical Woodlands[END_REF] . This facilitated the long-term sustainable support of large populations. Southern Mayan cities, or at least their ruling elites, perhaps did overstretch under duress from climate change but an overall decrease in population, with perhaps significant effects on the erosive potential of the landscape [START_REF] Beach | Impacts of the ancient Maya on soils and soil erosion in the central Maya Lowlands[END_REF] , occurred alongside increased resilience and population growth in the northern Maya region [START_REF] Mcanany | Bellicose rulers and climatological peril? Retrofitting twenty-first century woes on eighth-century Maya society[END_REF][START_REF] Mcneil | Deforestation, agroforestry, and sustainable land management practices among the Classic period Maya[END_REF] . In Amazonia, dense pre-colonial populations relied on various combinations of fire-intensive cultivation practices, raised agricultural fields, capture and management of aquatic riverine resources, and foraging for wild fauna and plants [START_REF] Arroyo-Kalin | Slash-burn-and-churn: Landscape history and crop cultivation in pre-Columbian Amazonia[END_REF][START_REF] Lombardo | Pre-Columbian occupation patterns in the eastern plains of the Llanos de Moxos, Bolivian Amazonia[END_REF][START_REF] Neves | Handbook of South American archaeology[END_REF] . This agroforestry system helped produce fertile soils and enhanced long-term forest biodiversity. Deforestation appears to have been sufficiently limited that evidence of significant human-induced erosion in Amazonia is so far scant.

Many other archaeological and palaeoecological intersections demonstrate the fine balance between large human populations and their tropical forest environments. For instance, current evidence would suggest that a tendency towards sprawling was already present in early tropical urbanism [START_REF] Fletcher | Low-density, agrarian-based urbanism: A comparative view[END_REF] . This is mirrored to a significant degree in the modern world and is reflected in concerns about the sustainability of sprawling megacities resulting in continual degradation of environments at the ever-expanding urban fringe [START_REF] Simon | Archaeology and contemporary dynamics for more sustainable, resilient cities in the peri-urban interface[END_REF] . The decline of early, low-density megacities with dense urban cores and massive state-sponsored hydraulic infrastructure appears often to have been strongly correlated with climate change [START_REF] Buckley | Climate as a contributing factor in the demise of Angkor, Cambodia[END_REF][START_REF] Lucero | From 'collapse' to urban diaspora: the transformation of low-density, dispersed agrarian urbanism[END_REF] . On the other hand, diversification, decentralization and 'agrarian urbanism' appear to have contributed to overall resilience [100][101] .

The deep history of global tropical forests: implications for the 21 st century

Although tropical forests were once seen as pristine, they are increasingly recognized as an outcome of long-standing human modification, management, and transformation. New methods and emerging datasets are demonstrating unequivocally that their enduring transformation by past human populations has much greater antiquity than previously thought. Yet despite the contemporary threat to tropical forests, and the need for concerted cross-disciplinary efforts to address the challenges they face, growing archaeological datasets have to date played only a relatively minor role in shaping contemporary discussions, debate, and policy making. This is in part a result of limited archaeological survey and exploration of tropical forests relative to other environments. It is also due to the fact that few ecologists and conservationists have engaged with mounting evidence for the long-term human impact of tropical forest environments (however, see [START_REF] Mcmichael | Ancient human disturbances may be skewing our understanding of Amazonian forests[END_REF][START_REF] Levis | Persistent effects of pre-Columbian plant domestication on Amazonian forest composition[END_REF]102 ). Some important strides have nonetheless been made. Increasing numbers of world heritage sites are now being accepted from tropical forest habitats, ranging from early Homo sapiens cave sites in Sri Lanka 103 to large-scale field systems in Bolivia 104 . UNESCO [START_REF]Exploring Frameworks for Tropical Forest Conservation: managing production and consumption for sustainability[END_REF] is now actively seeking to create joint world heritage sites of natural and cultural importance in tropical forest regions so that archaeological sites and their forest contexts are mutually protected within the framework of the UN 2030 Sustainable Development Programme 105 . Ecological restoration projects are also drawing on archaeological data. In the tropical forests of Hawaii, for example, wild flowering plants identified in archaeobotanical assemblages have been successfully reintroduced into regions from which they had been extirpated by the 21 st century 106 . Ancient tropical forest urban centres are also attracting broader attention in terms of their potential to shed light on contemporary challenges. For example, the extensive urban fringes around many ancient tropical forest urban centres are drawing interest within present day urban planning research (e.g. [START_REF] Simon | Archaeology and contemporary dynamics for more sustainable, resilient cities in the peri-urban interface[END_REF] ). The role of such peri-urban interfaces in local resilience, in addressing vulnerability of urban centres to climate change, and in supporting current livelihoods and food security are of increasing interest, with archaeological data from tropical regions providing useful case studies of long-term dynamics [START_REF] Simon | Archaeology and contemporary dynamics for more sustainable, resilient cities in the peri-urban interface[END_REF] . Also of interest have been tropical rainforest anthrosols such as the fertile terra preta soils of the pre-Columbian Amazon. Research into these pre-Columbian soilscape legacies has both encouraged the search for pantropical analogues [107][108] and inspired attempts to recreate similarly fertile soils 109 .

Tropical forest archaeology is now past its pioneering stage. Although its development over the past decades has been enabled by new methods within and beyond the discipline of archaeology, the role of deforestation in revealing previously hidden ancient structures underlines the urgency of drawing on the past to inform present-day policy and planning. This urgency is fully felt by indigenous and traditional populations in tropical regions, many of whose livelihoods and cultural existence is intimately linked to tropical forest environments. For instance, Mbuti populations in Central Africa have been gradually evicted from the tropical evergreen rainforests of this region over the last decade or so 110 , sometimes in the name of nature conservation. This has led not only to loss of traditional ecological knowledge but also to pervasive malnutrition and disease among some populations 111 . In the Brazilian Amazon, the impact of expanding infrastructure on populations is severe 112 and current debates examine the ethics of contract archaeological work in environmental licensing of large-scale infrastructure projects 113 . Threats to indigenous and traditional populations, their livehoods, and their knowledge systems are global in scope and need to be factored into any attempts to marry archaeological practice and policy relating to tropical forests.

Archaeological and palaeoecological data relating to ancient tropical forest problematizes the notion of any return to pristine conditions. If past human populations have in many cases altered tropical forests in ways that have rendered them more useable for human inhabitationimproving ecosystem services in modern parlancethen perhaps restoration is a problematic goal, at least if such practices are aimed at restoring to some 'original' condition. Archaeological research instead promotes recognition and in some cases conservation of 'novel ecosystems' 114-115 that have helped to sustain human populations over the long-term. The championing of novel ecosystems, and abandonment of traditional conservation goals are controversial ideas, but clearly amongst a number of key debates that archaeologists might usefully weigh in on as part of wider, interdisciplinary discussions about tropical forests.

In conclusion, we suggest that emerging understanding of the long-term history of tropical forests points to a number of core recommendations. Foremost amongst these is that indigenous and traditional peoples -whose ancestors' systems of production and knowledge are slowly being decoded by archaeologistsshould be seen as part of the solution and not one of the problems of sustainable tropical forest development. Second, there is a need for greater dissemination of the findings of archaeology beyond the discipline in order to enable broader understanding of long-term human alteration of tropical forest regions, and informed consideration of its implications. Third, we should continue to advance along the path of more regular and intensive exchange between archaeologists, ecologists, anthropologists, biologists, and geographers, engaging beyond academia with international bodies such as UNESCO and FAO [START_REF]Exploring Frameworks for Tropical Forest Conservation: managing production and consumption for sustainability[END_REF][START_REF]Beyond Tropical deforestation: From tropical deforestation to forest cover dynamics and forest development[END_REF][START_REF] De Dapper | Tropical forests in a changing global context[END_REF][116][117] .To this end, we advocate holding further regular meetings dedicated to a holistic and pantropical approach to the study of the archaeology of tropical forest biomes, as well as undertaking to achieve broader engagement between archaeologists and stakeholders. [START_REF] Summerhayes | Human adaptation and plant use in Highland New Guinea 49,000 to 44,000 years ago[END_REF] , and Westaway et al. [START_REF] Westaway | Age and biostratigraphic significance of the Punung rainforest fauna, East Java, Indonesia, and implications for Pongo and Homo[END_REF] .

Figures

Figure 2.

A model of anthropic impact on tropical forest environments based on Amazonia. A) Prehuman tropical forest with natural gap dynamics, including megafaunal impacts, B) Nomadic foraging groups utilizing plant (including tree) and animal resources and, where desirable, forming gaps through forest burning, C) Initial sedentism with house gardens and slight soil modification, D) Increased sedentism and population growth with corresponding soil modification, swidden plots, slash and burn impacts, the small re-growth of trees on old plots. E) Abandonment leading to forest re-growth and the legacy of anthropic soils. Note the central role played by aquatic resources and alluvial environments for the selection of appropriate environments for human inhabitation.

Figure 3 .

 3 Figure 3. Map of the temporal and geographical origins of selected domesticated plant and animal resources coming from tropical forest regions during the Early (11,000-8,200 ka), Middle (8,200-4,200 ka) and Late Holocene (4,200 ka onwards). Temporal periods have been defined on the basis of Walker et al. 123 Temporal and geographical information comes from Pearsall 124. , Clement et al. 125. , Piperno 126 , Denham 58 , Kingwell-Banham and Fuller 127. , Storey et al. 128 , Fuller and Hildebrand 129 , . Hunt and Rabett 119 , and Nagarajan et al. 130 .

Figure 4 .

 4 Figure 4. Lidar-derived bare earth model of urban and hydraulic infrastructure at a city on Phnom Kulen, ~35 km north of Angkor Wat. Penny et al. 131 have shown that the area that our figure shows was subject to intensive land use for several centuries between the 8 th and 12 th centuries CE, punctuated by episodes of severe erosion.

:

  Figure 1. Figure 1. Tropical Australasia showing sites with reasonably certain modern human presence, sites where there is vegetation disturbance by fire atypical of the longer Pleistocene record, or where humans are directly implicated, and locations with evidence for economically useful plants found both sides of the biogeographical discontinuity of the Wallace Line. Top: Late Pleistocene, Bottom: Early Holocene 11,000-5,000 BP. The figure is compiled based on data from Barker et al. 118 , Denham 58 , Hunt et al. 13 , Hunt and Premathilake 59 , Hunt and Rabett 119 , Marwick et al. 120 Mijares et al. 40 ,Moss and Kershaw 47 , Paz 56 , Kershaw et al. 121 , van der Kaars et al. 122 , Storm et al. 38 , Summerhayes et al.

Acknowledgments:

We would like to thank the participants for the Pantropica, 2016 workshop, funded and hosted by the Department of Archaeology at the Max Planck Institute for the Science of Human History, Jena, for taking part in an international meeting devoted to the global archaeology of rainforest environments. We would also like to thank Nuria Sanz, and the UNESCO office in Mexico, for

to Nina Hofer for her help with Figures 1, 2 and 3. DE's contribution, and Nina Hofer's contribution to the illustrations, was funded by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 639828) in partnership with the APSARA National Authority and the Ministry of Culture and Fine Arts, Cambodia. We also thank the Max Planck Institute for the Science of Human History, Jena for the ongoing funding of PR and NB.

N.B. We use "ka" to denote thousands of calibrated/uncalibrated years ago. Where this refers to radiocarbon dates this is equivalent to calibrated years BP.

Author contributions: P.R. conceived of the manuscript, wrote the manuscript, and conceived of and produced Figures 2 and3. C.H. wrote the manuscript and conceived of and produced Figure 1. M.A.K. wrote the manuscript and conceived of and produced Figures 2 and3. D.E. wrote the manuscript and conceived of and produced Figures 3 and4. N.B. conceived of the manuscript, wrote the manuscript, and conceived of Figures 2 and3.

The authors declare no competing financial interest or any other conflict of interest.


Emmanuelle Anceaume

Marina Papatriantafilou

Maria Potop-Butucaru

Philippas Tsigas

Distributed Ledger Register: From Safe to Atomic

This paper continues the recent line of academic effort dedicated to formalizing distributed ledgers. This work is the first one to propose a specification of distributed ledger register that matches the Lamport hierarchy from safe to atomic. Moreover, we propose implementations of distributed ledger registers with safe, regular and atomic guaranties in a model of communication specific to distributed ledgers technology that we also formalize. Then, we propose an implementation of a distributed ledger register that satisfies the atomic specification and the k-consistency property that characterises the permissionless distributed blockchains such as Bitcoin and Ethereum.

Introduction

The blockchain is probably one of the hottest and most transformative topic in the current digital landscape. The bitcoin crypto-currency [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], the leading application of the blockchain technology, has shown remarkably steady, and as such is often cited as the universal solution for managing a broad range of information.

A permissionless blockchain (or distributed ledger) is commonly presented as "an immutable distributed ledger with decentralised control", i.e., a continuously growing list of records that mimics the functioning of a traditional ledger, namely transparency and falsification-proof of documentation. However, a distributed ledger evolves in an untrusted and open environment. By entrusted, one means an environment in which participants cannot rely on a (shared or centralized) third authority to check and validate all the information that is contained in the blockchain. By open, one means an environment in which (non trustworthy) participants are free to join and leave the system at any time, and as often as they wish. To guarantee transparency and falsification-proof of information, the blockchain must be publicly accessible and consistently updated by every participant.

Distributed ledgers, beyond their incontestable qualities such as decentralisation, simple design and relatively easy use, are neither riskless nor free of limitation. The point is that an increasing number of areas promote the use of distributed ledgers for the development of their applications, and undeniably, the properties enjoyed by these technologies should be studied to fit such applications requirements, together with their relationships with blockchain-based applications.

Such challenges can be mitigated by laying down the theoretical foundations of distributed ledgers. Links between the distributed computing theory and distributed ledger has been pioneered by Garay et al [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF]. The main focus of the distributed community [START_REF] Cachin | Blockchain -From the Anarchy of Cryptocurrencies to the Enterprise (Keynote Abstract)[END_REF][START_REF] Decker | Bitcoin Meets Strong Consistency[END_REF][START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF][START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF][START_REF] Herlihy | Blockchains and the logic of accountability: Keynote address[END_REF][START_REF] Kokoris-Kogias | Enhancing bitcoin security and performance with strong consistency via collective signing[END_REF][START_REF] Pass | Analysis of the blockchain protocol in asynchronous networks[END_REF] has so far been the distributed ledger agreement aspects. Our paper investigates consistency properties of the distributed ledger technology to identify connections between this technology and read-write registers. This connection is important because it will help us for making possible to argue about the correctness of the ledger itself but also for the applications that will use it. We thus do need to deeply understand and formulate the properties of the state of distributed ledgers. In a previous work [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF], it was proven that the state of popular blockchain ledgers can be described as regular read-write registers. Regular registers provide weak guarantees that are not easy for the application programmer to use for building correct applications on top of those registers. More significantly they do not compose. Atomicity or linearizability is a state property that is composable [START_REF] Herlihy | Concurrency and availability as dual properties of replicated atomic data[END_REF], and thus would allow the combination of multiple distributed ledgers, and has clear strong semantics. Atomicity has been adopted as the standard property to have in the development of parallel and distributed systems. Previous work [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] left open the question of proposing distributed ledger registers with atomic semantics. In [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] the authors prove that Bitcoin and Ethereum verify only the specification of a distributed ledger register with regular semantic.

Our contribution. This paper extends the work of [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] in several ways. First, we propose a specification of distributed ledger register that matches the Lamport hierarchy [START_REF] Lamport | On inter-process communications, part I: basic formalism and part II: algorithms[END_REF] from safe to atomic. Furthermore, we propose an implementation of the distributed ledger register that verify safe, regular and atomic semantics in a model of communication specific to distributed ledgers technology ( [START_REF] Decker | Information propagation in the bitcoin network[END_REF]) where the system provides a broadcast primitive satisfying ∆-delivery (if a node invokes broadcast(m) then every correct node eventually delivers m within ∆ time units). Then we propose an implementation of a distributed ledger register that satisfies the atomic specification and the k-consistency property defined in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] to mimic permissionless distributed blockchains.

Paper Roadmap Section 2 presents briefly the characteristics of permissionless blockchains (e.g Bitcoin or Ethereum). Section 4 presents the computational model. Section 5 provides a brief summary of shared registers and their specification. In Section 6 we specify the Distributed Ledger Register and propose implementations of Distributed Ledger Register satisfying safe, regular and atomic semantic. Section 7 makes the connection between the Distributed Ledger Register specification defined in Section 6 and distributed ledgers. Section 8 concludes and presents open problems.

In 2008, Satoshi Nakamoto, a pseudonymous author, published a white paper describing the Bitcoin network, a way to create, distribute and manage a currency that does not rely on a trusted third party [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF]. Since then many crypto-currencies have been proposed, including the popular Ethereum [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF]. A permissionless blockchain is commonly presented as "an immutable append only ledger publicly readable and writable". By immutable append only ledger it is meant a continuously growing list of appended records (or blocks) that mimics the functioning of a traditional ledger, namely transparency and falsification-proof of documentation.

From an implementation point of view, each entity of the system locally maintains its own copy of the ledger. Each newly created block cryptographically depends on the current local ledger. Once created it is propagated within the system. Since blocks can be created concurrently, two or more blocks can reference the very same parent block, and hence the creation of a tree with several chains. This situation is known as ledger fork. In a chain of blocks, each block references an earlier block by inserting a cryptographic link to this earlier block in its header. This forms a tree of blocks, rooted at the genesis block, in which a branch is a path from a leaf block to the root of the tree. Each branch, taken in isolation, represents a consistent history of the crypto-currency system, that is, does not internally contain any conflicting transactions -double-spending transactions. On the other hand, any two branches of the tree do not need to be consistent with each other. The reason is that, at any time, each node of the system selects the best chain, a unique branch to represent the history of the crypto-systemthis branch being the longest one of the tree, or equivalently the one that required the most important quantity of work. The best chain in Bitcoin corresponds to the longest chain starting from the genesis block of the distributed ledger (the blockchain is bootstrapped with the genesis block), while in Ethereum, the best chain is the heaviest one. The level of confirmation of a block b belonging to the best chain of the distributed ledger is equal to the number of blocks included in the best chain starting from b. We say that a transaction is deeply confirmed once it reaches such a confirmation level.

Garay and Kiayias [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF] have characterized Bitcoin blockchain via its quality and its common prefix properties. Specifically, they have shown that, by keeping the creation rate of blocks very low with respect to their propagation time in the network (i) if the adversary controls no more than 1/3 of the network hashing power then it provably controls less than a majority of the blocks in the blockchain and, (ii) if the adversary controls no more than 1/2 of the network hashing power then the blockchains maintained by any two honest nodes possess a large common prefix (up to the last k appended blocks), and the probability that they are not mutual prefix of each other decays exponentially in k.

In [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF] the authors extract Bitcoin backbone and define invariant that this protocol has to satisfy in order to verify with high probability an eventual consistent prefix. This line of work has been continued by [START_REF] Pass | Fruitchains: A fair blockchain[END_REF]. However, to the best of our knowledge, no other previous attempt proposed a consistency unified framework and hierarchy capturing both Consensus-based and proof-of-work based blockchains. In [START_REF] Abraham | The blockchain consensus layer and BFT[END_REF], the authors present a study about the relationships between Byzantine fault tolerant consensus and distributed blockchains. In order to abstract out the proof-of-work mechanism the authors propose a specific oracle, in the same spirit of our oracle abstraction, but more specific than ours, since it makes a direct reference to proof-of-work properties. In parallel and independently of our work, [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] proposes a formalization of distributed ledgers modeled as an ordered list of records. The authors propose three consistency criteria: eventual consistency, sequential consistency and linearizability. Interestingly, they show that a distributed ledger that provides eventual consistency can be used to solve the consensus problem. These findings confirm our results about the necessity of Consensus to solve Strong Prefix. In [START_REF] Girault | Monotonic prefix consistency in distributed systems[END_REF] the authors present an implementation of the Monotonic Prefix Consistency (MPC) criterion and showed that no criterion stronger than MPC can be implemented in a partition-prone message-passing system. On the other hand, the proposed formalization does not propose weaker consistency semantics more suitable for proof-of-work blockchains as BitCoin. In [START_REF] Anceaume | Blockchain abstract data type[END_REF], the authors propose a new data type to formally model distributed ledgers and their behavior at runtime. They provide consistency criteria to capture the correct behavior of current blockchain proposals in a unified framework. It is already known that some blockchain implementations solve eventual consistency of an append-only queue using Consensus [START_REF] Androulaki | Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains[END_REF][START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF]. However, Bitcoin [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System[END_REF] and Ethereum [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF] that technically do not solve Consensus need to be characterized from the point of view of the consistency guaranties that they are able to offer. The question is about the consistency criterion of blockchains as Bitcoin [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System[END_REF] and Ethereum [START_REF] Wood | Ethereum: A secure decentralised generalised transaction ledger[END_REF] that technically do not solve Consensus, and their relation with Consensus in general. The first work that addressed this open question was proposed by [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF]. They proposed to connect distributed registers theory to distributed ledgers. They introduce the notion of Distributed Ledger Register (DLR) were the value of the register has a tree topology instead of a single value as in the classical theory of distributed registers. The nodes of the tree are blocks of transactions cryptographically linked. This work has been further extended in [START_REF] Anceaume | Blockchain abstract data type[END_REF]. They specify the consistency guarantees offered by various ledgers at runtime. A distributed ledger is the composition of two finite state automata enriched with a consistency criteria that specifies the behavior of the ledger in presence of concurrency. The first automaton, called blocktree abstract data type, describes the transition of the tree of blocks of when read and append of new blocks are executed. The second automaton, called token oracle, captures the cryptographical process, proof-of-work, specific to permissionless ledgers that condition the append of new blocks. Furthermore, [START_REF] Anceaume | Blockchain abstract data type[END_REF] proposes necessary conditions to implement a blocktree abstract data type and the study of consensus number of token oracle. This line of research paves the way to automatic design of distributed ledgers.

In their mutual objective to contribute in the provision of a proper formulation of distributed ledgers in terms of shared objects, the authors of [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] open a line of work complementary to the one presented in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] and the extension presented in the current paper. In [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] the ledger object is a totally ordered sequence of blocks (or records) while [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] and the current work consider a tree of blocks that specify both permissioned and permissionless ledgers. The work proposed in [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] was continued in [START_REF] Anta | Atomic appends: Selling cars and coordinating armies with multiple distributed ledgers[END_REF] by defining Multi-Distributed Ledger Objects (MDLO), which is the result of aggregating multiple Distributed Ledger Objects satisfying the definition proposed in [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF]. In Section 8 we will discuss the research directions opened by [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF][START_REF] Anceaume | Blockchain abstract data type[END_REF][START_REF] Anta | Atomic appends: Selling cars and coordinating armies with multiple distributed ledgers[END_REF][START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] and the current work.

Computational Model

We model the system as a partially synchronous distributed system composed of an arbitrary finite number of nodes, such that each node has enough computation resources to mine blocks.

Each node is a state machine, whose state, called "local state", is defined by the current values of its local variables. A configuration of the system is composed of the local state of each node in the system. The passage of time is measured by a fictional global clock. Nodes do not have access to the fictional global time. At each time t, each node is characterised by its local state.

It is assumed that the system has a built-in communication abstraction, denoted broadcast, that allows nodes to communicate by exchanging messages via broadcast() and deliver() operations. This communication abstraction is defined by the following properties.

-∆-delivery. There exists ∆ > 0 such that if a node invokes broadcast(m) then every correct node eventually delivers m within ∆ time units. -Validity. If a correct node delivers a message m from p then p has previously invoked broadcast(m).

By correct node, we mean a node that follows the prescribed protocols. We suppose on the other hand that some of them can suffer arbitrary failuressuch nodes are called incorrect. For instance, an incorrect node can manipulate the communication primitive by broadcasting inconsistent messages, or by not broadcasting messages or by stopping its execution. We assume that less than a third of the computational power of the system is owned by incorrect nodes. We do not make any restrictions regarding incorrect users.

Background on Distributed Registers

This section recalls the main properties of classical distributed read-write registers.

A distributed read-write register REG is a shared variable accessed by a set of processes through two operations, namely REG.write() and REG.read().

Informally, the REG.write() operation updates the value stored in the shared variable while the REG.read() obtains the value contained in the shared variable. Every operation issued on a register is, generally, not instantaneous and can be characterised by two events occurring at its boundaries: an invocation event and a reply event. Both events occur at two different instants with respect to the fictional global time: the invocation event of an operation op (i.e., op = REG.write() or op = REG.read()) occurs at the invocation time denoted by t B (op) and the reply event of op occurs at the reply time denoted by t E (op).

Given two operations op and op on a register, we say that op precedes op (op ≺ op ) if and only if t E (op) < t B (op ). If op does not precede op and op does not precede op, then op and op are concurrent (noted op||op ). In case of concurrency while accessing the shared variable, the meaning of last written value becomes ambiguous. Depending on the semantics of the operations, three types of registers have been defined by Lamport [START_REF] Lamport | On inter-process communications, part I: basic formalism and part II: algorithms[END_REF]: safe, regular and atomic.

An operation op is terminated if both the invocation event and the reply event occurred (i.e., the process executing the operation does not crash between the invocation time and the reply time). A terminated operation can either be successful and thus returns true or can return abort when, for example, some operational conditions are not met. More details will be given in Section 7. On the other hand, an operation that does not terminate is called failed.

The semantic of a distributed read-write register (simply called read-write register) can be classified as safe, regular or atomic [START_REF] Lamport | On inter-process communications, part I: basic formalism and part II: algorithms[END_REF]. The safe register ensures that a read which does not overlap with a write returns the last completed write. The result of a read overlapping a write can be any value from the register domain. The regular register verifies the safe semantic when reads are not concurrent with writes. For reads concurrent with writes the read will return either the last written value or the value of the concurrent write. A safe distributed register REG is defined by the following properties:

-Liveness: Any invocation of REG.write() or REG.read() eventually terminates. -Safety: A REG.read() operation returns the last value written before its invocation (i.e. the value written by the latest REG.write() preceding this REG.read() operation), or any value of the register domain in case the REG.read() operation is concurrent to a REG.write() operation.

A regular distributed register REG is defined by the following properties:

-Liveness: Any invocation of REG.write() or REG.read() eventually terminates. -Safety: A REG.read() operation returns the last value written before its invocation (i.e. the value written by the latest REG.write() preceding this REG.read() operation), or a value written by a REG.write() operation concurrent with it.

An atomic register is a regular register that satisfies the no new/old inversion property defined as follows:

no new/old inversion: For any two read operations, the set of writes that do not strictly follow either of them must be perceived by both reads as occurring in the same order.

6 From Classical Distributed Registers to Distributed Ledger Registers

Interestingly enough, neither safety, regularity nor atomicity of distributed shared registers capture the behaviour of distributed ledgers. Classically, values written in a register are potentially independent, and during the execution, the size of the register remains the same. In contrast, a new block cannot be written in the blockchain if it does not depend on the previous one, and successive writings in the blockchain increase its size. Interestingly, blockchains behavior has some similarities with the stabilizing registers, line of research pioneered by [START_REF] Hoepman | Self-stabilization of wait-free shared memory objects[END_REF]. Looking at the stabilizing register, it implements some type of eventual consistency, in the sense that, there exists a prefix of the system execution for which there are no guarantees on the value of the shared register: register semantics hold only from a certain time in the execution. In contrast, the prefix of the blockchain eventually converges at every entity, while no guarantees hold for the last created blocks.

In [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] we have proposed a new register called the Distributed Ledger Register (DLR). However, the specification proposed in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] is tailored for Bitcoin and Ethereum as we further discuss in Section 7. In the following we refine this specification in order to match as closely as possible the classical distributed registers hierarchy.

The Distributed Ledger Register (DLR) has a tree structure, whose root is the genesis block, and where each branch is a sequence of blocks. The value of DLR is the best chain of the tree. The best chain(T B) is a chain in the tree T B that satisfies some predicate: the longest sequence of blocks, starting from the root (as in the case of Bitcoin) or the heaviest chain the tree (as in the case of Ethereum). The value of the DLR is called a blockchain and is denoted by B. The DLR is equipped with write and read operations. The DLR.write operation allows any process to append to the value of DLR a block b. The DLR.read() operation allows any miner to retrieve the value of DLR.

In the following, we present the implementations of the distributed ledger register that satisfy safe, regular and atomic semantics assuming the communication abstraction satisfies the ∆-delivery property (i.e. there exists ∆ > 0 such that if a process invokes broadcast(m) then every correct process eventually delivers m within ∆ time units.)

Safe Distributed Ledger Register

We propose an implementation of the Single Writer Multiple Reader (SWMR) Distributed Ledger Register that respects the safe semantic.

A safe distributed ledger register DLR is defined by the following properties:

-Liveness: Any invocation of DLR.write() or DLR.read() eventually terminates.

-Safety: A DLR.read() operation returns a chain B such that B has a prefix B 1 whose last(B 1 ) is the last value DLR.written before its invocation (i.e. the value DLR.written by the latest DLR.write() preceding this DLR.read() operation), or any value of the register domain in case the DLR.read() operation is concurrent to a DLR.write() operation. Note that in the case of a DLR register a value in the register domain may be any distributed ledger. ------------------ Proof. Let r be a DLR.read() operation issued by a process p. Let w be the last DLR.write before r and no concurrent DLR.write is executed with r. Let B be the chain broadcast by w. Since r starts after w returns and w waits ∆ before returning, then p receives B, and returns it.

Regular Distributed Ledger Register

A regular distributed ledger register DLR is defined by the following properties:

-Liveness: Any invocation of DLR.write() or DLR.read() eventually terminates.

-Safety: A DLR.read() operation returns a chain B such that B has a prefix B 1 whose last(B 1 ) is the last value DLR.written before its invocation (i.e. the value DLR.written by the latest DLR.write() preceding this DLR.read() operation), or a value DLR.written by a DLR.write() operation concurrent with it.

We propose an implementation of a SWMR Distributed Ledger Register that satisfies the regular semantic. ------------------- Proof. Algorithm 2 implements a safe register. Let r be a DLR.read() operation issued by process p such that r happened after some DLR.write() operation w. Let B be the chain broadcast during w. Since p waits ∆ time units before returning then p received B before returning. Hence p returns the last DLR.written value. We now prove that in presence of a concurrent DLR.write() operation, a DLR.read() operation returns either the concurrent DLR.written value or the previous one. Let r be a DLR.read() operation issued by some process p such that r is concurrent with a DLR.write() operation w 1 and let w be the last DLR.write() operation that precedes both w 1 and r. Let B be the chain broadcast by w. Since w 1 starts with a DLR.read() operation then chain B 1 broadcast by w 1 has B as prefix (by the safe property of the register). Operation r receives B (since r happened after w), hence the tree structure maintained by p has been updated with B. If p received B 1 then p updated its tree with B 1 hence its best chain now is B 1 . Hence, p returns either B or B 1 which are the result of the last DLR.write() or a concurrent DLR.write() operation.

Atomic Distributed Ledger Register

An atomic distributed ledger register is a regular distributed ledger register that verifies the no new/old inversion property defined as follows:

no new/old inversion: For any two DLR.read() operations r 1 and r 2 such that r 1 happens before r2 then the distributed ledger returned by r2 has the distributed ledger returned by r 1 as prefix.

In the following we first propose an implementation of the SWMR Atomic Distributed Ledger Register, and then an implementation of the MWMR Atomic Distributed Ledger Register, that is a DLR register that can be DLR.written (and DLR.read) by multiple processes. -------------------(09) upon deliver(<propose B>) [START_REF] Eyal | Bitcoin-NG: A scalable blockchain protocol[END_REF] update tree(T B, B) Fig. 3. DLR.read() and DLR.write() operations of the SWMR Atomic DLR register.

Lemma 3. Algorithm 3 implements a SWMR Atomic Distributed Ledger Register.

Proof. From Lemma 2 it trivially follows that Algorithm 3 satisfies the SWMR Regular DLR specification. Consider two DLR.read() operations r 1 and r 2 such that r 1 happens before r 2 . Let w be the last DLR.write() operation before r 1 , and w 1 be a DLR.write() operation concurrent with both r 1 and r 2 . Assume r 1 received the distributed ledger B broadcast during w 1 . Since r 2 happens after r 1 (hence after ∆ time units after the broadcast of B), then r 2 received B. Hence, Algorithm 3 satisfies no new/old inversion property. Lemma 4. Algorithm 4 implements a MWMR Atomic Distributed Ledger Register.

Proof. By Lemma 3 Algorithm 4 verifies the SWMR atomic register specification since it behaves exactly as Algorithm 3 except that the "wait ∆" line (line 8) has been added. Note that it has no impact in a single writer setting. Consider two concurrent DLR.write() operations w 1 and w 2 . Let w be the last DLR.write() operation that happens before both w 1 and w 2 (i.e., no DLR.write() operation happens between w and w 1 and w 2 ). Let B be the chain written by w. Let B 1 be the chain broadcast by w 1 and B 2 be the chain broadcast by w 2 . By definition B is prefix of both B 1 and B 2 . Both w 1 and w 2 update their local tree with the chains B 1 and B 2 and wait ∆ time units before returning. Let r be a read that happens after w 1 and w 2 . The process p that issues r waits ∆ before returning. Hence, p updates its local tree with both B 1 and B 2 and returns the best chain between B 1 and B 2 .

Distributed Ledger Register and Permissionless Blockchain Systems

In this section, we refine the specification of the Distributed Ledger Register proposed in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] that mimics the behaviour of the Bitcoin and Ethereum distributed ledger (i.e., Bitcoin blockchain). We recall the functioning of Bitcoin. As described in the introduction, each miner needs to locally manage a data structure from which it can extract the blockchain. Specifically, this data structure is a tree, denoted by T B, and the blockchain, denoted by B, is the longest chain in this tree. By construction, the root of T B is the genesis block, a common block for all the miners. In terms of read and write operations, the blockchain protocol informally translates as follows: When a miner wishes to create a new block, it first invokes a read operation on T B. This read returns the longest chain of T B, denoted by B. From B, the miner creates its new block, appends it to B, and broadcasts B in the system (see [START_REF] Garay | The bitcoin backbone protocol: Analysis and applications[END_REF] for details). Note that from a practical point of view, only the new block is broadcast to the system, and if necessary miners wait from their neighbours for blocks in B they are not aware of. As recalled in Section 2, the level of confirmation k of a block b in a blockchain provides guarantees on the likelihood that b can be pruned from the blockchain. The blockchain properties are closely related to the value of k. Therefore, in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] is introduced the notion of k-valid write. Definition below is just a refinement of the definition proposed in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] considering that write operation is invoked with a block as parameter and not a chain.

Definition 1 (k-valid write). Operation DLR.write(b) is k-valid if and only if there exist a time t > 0 and an integer k > 0 such that a virtual DLR.read() invoked at time t > t after the invocation of DLR.write(b) returns a chain B such that ∃B prefix of B and length(B ) ≥ length(B) + k and the last block of B is b, where function length(B) returns the number of blocks that compose chain B.

Operation write(b) returns true if write(b) is k-valid otherwise it returns abort. As described in Section 2 the value of k depends on the proportion β of malicious miners in the system. It has been shown by Nakamoto [START_REF] Nakamoto | Bitcoin: A peer-to-peer electronic cash system[END_REF], that if the proportion β of malicious miners is ≤ 10%, then with probability ≤ 0.1%, a transaction can be rejected if its level of confirmation in a local copy of the blockchain is less than or equal to than 6.

The presence of the genesis block is very similar to the classical assumption in registers theory which states that before the first read at least one virtual write operation happened. Therefore, for the distributed ledger register we consider that before the first read there was at least a virtual k-valid write.

A ledger multi-reader multi-writer register defined in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] that mimics Bitcoin/Ethereum has the following specification.

-Liveness Any invocation of a DLR.write(b) or a DLR.read() terminates.

-k-consistency Any DLR.read() returns a value B such that ∃B prefix of B with last(B ) is the value of the register written by the last k-valid DLR.write() operation that precedes DLR.read().

In the following we propose to extend the implementation of an atomic DLR register in order to verify the k-consistency property specified above. Lemma 5. Algorithm 5 verifies the specification of SWMR Atomic Distributed Ledger Registers.

Proof. Consider an execution of Algorithm 5 such that any DLR.write() operation is followed by at least k DLR.write() operations. Let w 1 and r 1 be respectively a DLR.write() and DLR.read() operations such that r 1 happens after w 1 and no DLR.write() operation is concurrent with r 1 . Let B be the chain broadcast by w 1 . Since r 1 happens after w 1 and r 1 returns only after ∆ time units and the propagation of B takes at most ∆ time units then r 1 returns B. We now prove that in any execution of Algorithm 5 there is no new/old inversion. Consider two DLR.read() operations r 1 and r 2 such that r 1 happens before r 2 . Let w be the DLR.write() operation before r 1 and w 1 be a concurrent operation with both r 1 and r 2 . Assume r 1 received the blockchain broadcast during w 1 . Let B be this blockchain. Since r 2 happens after r 1 (hence ∆ time units after the broadcast of B by r 1 ), then r 2 received B. Hence, Algorithm 5 verifies no new/old inversion property. Lemma 6. Algorithm 5 verifies the specification of MWMR Atomic Distributed Ledger Registers. -------------------

Conclusions and Future directions

Recently several academic studies have been devoted to the formal specification of distributed ledgers [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF][START_REF] Anceaume | Blockchain abstract data type[END_REF][START_REF] Anta | Atomic appends: Selling cars and coordinating armies with multiple distributed ledgers[END_REF][START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF]. Our work continues this effort and extends the previous work in several ways. Our work is the first one to propose a specification of distributed ledger register that matches the Lamport hierarchy [START_REF] Lamport | On inter-process communications, part I: basic formalism and part II: algorithms[END_REF] from safe to atomic registers. We have proposed new algorithms to implement distributed ledger registers with safe, regular and atomic guarantees on top of a broadcast primitive specific to distributed ledgers [START_REF] Decker | Information propagation in the bitcoin network[END_REF]. We have also formalized this primitive. Then, we have proposed an implementation of a distributed ledger register that satisfies the atomic specification and the k-consistency property that characterizes the permissionless distributed blockchains such as Bitcoin and Ethereum as proved in [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF]. Therefore, we respond to an open problem raised by [START_REF] Anceaume | Bitcoin a distributed shared register[END_REF] where it has been proven that Bitcoin and Ethereum implement a distributed ledger register verifying only regular semantics. It should be noted that our work is complementary to the work proposed in [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] that focuses only on ledger objects that consist in a totally ordered sequence of blocks (or records). Unifying our framework with the one proposed in [START_REF] Anta | Formalizing and implementing distributed ledger objects[END_REF] and extending it to multi-objects operations [START_REF] Anta | Atomic appends: Selling cars and coordinating armies with multiple distributed ledgers[END_REF] is an interesting open direction. Moreover, connecting this new framework with the runtime specification proposed in [START_REF] Anceaume | Blockchain abstract data type[END_REF] in order to automatically design and verify distributed ledgers algorithms with various semantics is an interesting and important open research direction.

Fig. 1 .Lemma 1 .

 11 Fig. 1. DLR.read() and DLR.write() operations of the Safe Distributed Ledger Register.

Operation

  DLR.read () is % issued by a reader % (01) wait ∆ (02) return(best chain(T B) ) Operation DLR.write (b) is % issued by a writer % (03) B = DLR.read() (04) append b to B (05) broadcast (<propose B>) (06) update tree(T B, B) (07) return true

Operation

  DLR.read () is % issued by a reader % (01) broadcast (<propose best chain(T B) >) (02) wait ∆ (03) return(best chain(T B) ) Operation DLR.write (b) is % issued by a writer % (04) B = DLR.read() (05) append b to B (06) broadcast (<propose B>) (07) update tree(T B, B) (08) return true -

OperationFig. 4 .

 4 Fig. 4. DLR.read() and DLR.write() operations of the MWMR Atomic DLR register.

Fig. 5 . 1 . 7 .

 517 Fig. 5. DLR.read() and DLR.write() operations of the MWMR Atomic Distributed Ledger Register satisfying k-consistency property.