1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
// Copyright 2019-2024 ChainSafe Systems
// SPDX-License-Identifier: Apache-2.0, MIT
//! This is an empty module for documentation purposes.
//!
//! Documentation of core concepts belong in-tree (in `/src`).
//!
//! Unless it better fits on a specific component, this module is a the place for
//! documentation about:
//! - The current behavior of Forest
//! - Filecoin concepts
//!
//! Documentation that doesn't fit the above should be in `/documentation`:
//! - User-facing guides.
//! - Developer _process_ guides, i.e memory profiling, release checklists.
/// This is a ground-up introduction to the different kinds of snapshot files,
/// covering:
/// 1. [Actors in Filecoin](#actors).
/// 2. [The Filecoin Blockchain](#the-filecoin-blockchain)
/// 3. [The Filecoin State Tree](#the-filecoin-state-tree)
/// 4. (Finally) [snapshots](#snapshots)
///
/// # Actors
///
/// The Filecoin Virtual Machine (FVM) hosts a number of _actors_.
/// These are objects that maintain and mutate internal state, and communicate
/// by passing messages.
///
/// An example of an actor is the [`cron`](fil_actors_shared::v11::runtime::builtins::Type::Cron)
/// actor.
/// Its [internal state](fil_actor_cron_state::v11::State) is a to-do list of
/// other actors to invoke every epoch.
///
/// See [the Filecoin docs](https://docs.filecoin.io/basics/the-blockchain/actors)
/// for more information about actors.
///
/// # The Filecoin blockchain
///
/// Filecoin consists of a blockchain of `messages`.
/// Listed below are the core objects for the blockchain.
/// Each one can be addressed by a [`Cid`](cid::Cid).
///
/// - [`Message`](crate::shim::message::Message)s are statements of messages between
/// the actors.
/// They describe and (equivalently) represent a change in _the state tree_ (see below).
/// See [`apply_block_messages`](crate::state_manager::apply_block_messages) to learn
/// more.
/// Messages may be [signed](crate::message::SignedMessage).
/// - `Message`s are grouped into [`Block`](crate::blocks::Block)s, with a single
/// [`header`](crate::blocks::RawBlockHeader).
/// These are what are mined by miners to get `FIL` (money).
/// They define an [_epoch_](crate::blocks::RawBlockHeader::epoch) and a
/// [_parent tipset_](crate::blocks::RawBlockHeader::parents).
/// The _epoch_ is a monotonically increasing number from `0` (genesis).
/// - `Block`s are grouped into [`Tipset`](crate::blocks::Tipset)s.
/// All blocks in a tipset share the same `epoch`.
///
/// ```text
/// ┌───────────────────────────────┐
/// │ BlockHeader { epoch: 0, .. } │ // The genesis block/tipset
/// ┌● └───────────────────────────────┘
/// ~
/// └──┬───────────────────────────────┐
/// │ BlockHeader { epoch: 10, .. } │ // The epoch 10 tipset - one block with two messages
/// ┌● └┬──────────────────────────────┘
/// │ │
/// │ │ "I contain the following messages..."
/// │ │
/// │ ├──────────────────┐
/// │ │ ┌──────────────┐ │ ┌───────────────────┐
/// │ └►│ Message: │ └►│ Message: │
/// │ │ Afri -> Bob │ │ Charlie -> David │
/// │ └──────────────┘ └───────────────────┘
/// │
/// │ "my parent is..."
/// │
/// └──┬───────────────────────────────┐
/// │ BlockHeader { epoch: 11, .. } │ // The epoch 11 tipset - one block with one message
/// ┌● └┬──────────────────────────────┘
/// │ │ ┌────────────────┐
/// │ └►│ Message: │
/// │ │ Eric -> Frank │
/// │ └────────────────┘
/// │
/// │ // the epoch 12 tipset - two blocks, with a total of 3 messages
/// │
/// ├────────────────────────────────────┐
/// └──┬───────────────────────────────┐ └─┬───────────────────────────────┐
/// │ BlockHeader { epoch: 12, .. } │ │ BlockHeader { epoch: 12, .. } │
/// ┌● └┬──────────────────────────────┘ └┬─────────────────────┬────────┘
/// ~ │ ┌───────────────────────┐ │ ┌─────────────────┐ │ ┌──────────────┐
/// └►│ Message: │ └►│ Message: │ └►│ Message: │
/// │ Guillaume -> Hailong │ │ Hubert -> Ivan │ │ Josh -> Kai │
/// └───────────────────────┘ └─────────────────┘ └──────────────┘
/// ```
///
/// The [`ChainMuxer`](crate::chain_sync::ChainMuxer) receives two kinds of [messages](crate::libp2p::PubsubMessage)
/// from peers:
/// - [`GossipBlock`](crate::blocks::GossipBlock)s are descriptions of a single block, with the `BlockHeader` and `Message` CIDs.
/// - [`SignedMessage`](crate::message::SignedMessage)s
///
/// It assembles these messages into a chain to genesis.
///
/// Filecoin implementations store all the above in the `ChainStore`, per
/// [the spec](https://github.com/filecoin-project/specs/blob/936f07f9a444036fe86442c919940ea0e4fb0a0b/content/systems/filecoin_nodes/repository/ipldstore/_index.md?plain=1#L43-L50).
///
/// # The Filecoin state tree
///
/// `Message`s describe/represent mutations in the [`StateTree`](crate::shim::state_tree::StateTree),
/// which is a representation of all Filecoin state at a point in time.
/// For each actor, the `StateTree` holds the CID for its state: [`ActorState.state`](fvm4::state_tree::ActorState::state).
///
/// Actor state is serialized and stored as [`Ipld`](libipld::Ipld).
/// Think of this as "JSON with links ([`Cid`](cid::Cid)s)".
/// So the `cron` actor's state mentioned above will be ultimately serialized into `Ipld`
/// and stored in the `StateStore`, per
/// [the spec](https://github.com/filecoin-project/specs/blob/936f07f9a444036fe86442c919940ea0e4fb0a0b/content/systems/filecoin_nodes/repository/ipldstore/_index.md?plain=1#L43-L50).
///
/// It isn't feasible to create a new copy of actor states whenever they change.
/// That is, in a fictional [^1] example of a `cron` actor, starting with a [`crontab`](https://man7.org/linux/man-pages/man5/crontab.5.html)
/// with 10 items, mutation of the state should _not_ simply duplicate the state:
/// ```text
/// Previous state Current state
/// ┌───────────────────────┐ ┌───────────────────────┐
/// │Crontab │ │Crontab │
/// │1. Get out of bed │ │1. Get out of bed │
/// │2. Shower │ │2. Shower │
/// │... │ │... │
/// │10. Take over the world│ │10. Take over the world│
/// └───────────────────────┘ │11. Throw a party │
/// └───────────────────────┘
/// ```
/// But should instead be able to refer to the previous state:
/// ```text
/// Previous state Current state
/// ┌───────────────────────┐ ┌─────────────────┐
/// │Crontab │◄─┤(See CID...) │
/// │1. Get out of bed │ ├─────────────────┤
/// │2. Shower │ │11. Throw a party│
/// │... │ └─────────────────┘
/// │10. Take over the world│
/// └───────────────────────┘
/// ```
/// And removal of e.g the latest entry works similarly, _orphaning_ the removed
/// item.
/// ```text
/// Previous state Orphaned item Current state
/// ┌───────────────────────┐ ┌────────────┐
/// │Crontab │◄──────────────────────┤(See CID...)│
/// │1. Get out of bed │ ┌─────────────────┐ └────────────┘
/// │2. Shower │ │11. Throw a party│
/// │... │ └─────────────────┘
/// │10. Take over the world│
/// └───────────────────────┘
/// ```
///
/// [^1]: The real `cron` actor doesn't mutate state like this.
///
/// Data structures that reach into the past of the `StateStore` like this are:
/// - ["AMT"](fil_actors_shared::fvm_ipld_amt), a list.
/// - ["HAMT"](fil_actors_shared::fvm_ipld_hamt), a map.
///
/// Therefore, the Filecoin state is, indeed, a tree of IPLD data.
/// It can be addressed by the root of the tree, so it is often referred to as
/// the _state root_.
///
/// We will now introduce some new terminology given the above information.
///
/// With respect to a particular IPLD [`Blockstore`](fvm_ipld_blockstore::Blockstore):
/// - An item such a list is _fully inhabited_ if all its recursive
/// [`Ipld::Link`](libipld::Ipld::Link)s exist in the blockstore.
/// - Otherwise, an item is only _partially inhabited_.
/// The links are said to be "dead links".
///
/// With respect to a particular `StateTree`:
/// - An item is _orphaned_ if it is not reachable from the current state tree
/// through any links.
///
/// # Snapshots
///
/// Recall that for each message execution, the state tree is mutated.
/// Therefore, each epoch is associated with a state tree after execution,
/// and a [_parent state tree_](crate::blocks::RawBlockHeader::state_root).
///
/// ```text
/// // state after execution of
/// // all messages in that epoch
/// ┌───────────────────────────────┐ ┌────────────┐
/// │ BlockHeader { epoch: 0, .. } │ │ state root ├──► initial actor states...
/// ┌● └───────────────────────────────┘ └────────────┘ ▲ ▲
/// ~ // links to redundant data ─● │ │
/// └──┬───────────────────────────────┐ ┌────────────┐ │ │
/// │ BlockHeader { epoch: 11, .. } │ │ state root ├─┬► actor state ─► AMT │
/// ┌● └┬──────────────────────────────┘ └────────────┘ ~ │
/// │ │ ┌─────────┐ └► actor state ─► HAMT ┘
/// │ └►│ Message │ │
/// │ └─────────┘ ▼
/// ├──┬───────────────────────────────┐ // new data in this epoch ─● IPLD
/// │ │ BlockHeader { epoch: 12, .. } │
/// │ └┬─────────────┬────────────────┘
/// │ │ ┌─────────┐ │ ┌─────────┐
/// │ └►│ Message │ └►│ Message │
/// │ └─────────┘ └─────────┘ ~ ~
/// └──┬───────────────────────────────┐ ┌────────────┐ │ │
/// │ BlockHeader { epoch: 12, .. } │ │ state root ├─┬► actor state ─► AMT │
/// ┌● └┬──────────────────────────────┘ └────────────┘ ~ │
/// ~ │ ┌─────────┐ └► actor state ─► HAMT ┘
/// └►│ Message │
/// └─────────┘
/// ```
///
/// We are now ready to define the different snapshot types for a given epoch N.
/// - A _lite snapshot_ contains:
/// - All block headers from genesis to epoch N.
/// - For the last W (width) epochs:
/// - The _fully inhabited_ state trees.
/// - The messages.
/// - For epochs 0..N-W, the state trees will be dead or partially inhabited.
/// - A _full snapshot_ contains:
/// - All block headers from genesis to epoch N.
/// - The fully inhabited state trees for epoch 0..N
/// - A _diff snapshot_ contains:
/// - For epoch N-W..N:
/// - The block headers.
/// - The messages.
/// - New data in that epoch, which will be partially inhabited
///
/// Successive diff snapshots may be concatenated:
/// - From genesis, to produce a full snapshot.
/// - From a lite snapshot, to produce a successive lite snapshot.
mod snapshots {}