ouroboros-consensus-0.1.0.1: Consensus layer for the Ouroboros blockchain protocol
Safe Haskell None
Language Haskell2010

Ouroboros.Consensus.Storage.ChainDB.Impl.Paths

Synopsis

LookupBlockInfo

type LookupBlockInfo blk = HeaderHash blk -> Maybe ( BlockInfo blk) Source #

Return the block info for the block with the given hash. Return Nothing when not in the VolatileDB.

Candidates

extendWithSuccessors :: forall blk. HasHeader blk => ( ChainHash blk -> Set ( HeaderHash blk)) -> LookupBlockInfo blk -> ChainDiff ( HeaderFields blk) -> NonEmpty ( ChainDiff ( HeaderFields blk)) Source #

Extend the ChainDiff with the successors found by maximalCandidates .

In case no successors were found, the original ChainDiff is returned as a singleton.

In case successors were found, the original ChainDiff is not included, only its extensions.

Only the longest possible extensions are returned, no intermediary prefixes of extensions.

maximalCandidates Source #

Arguments

:: forall blk. ( ChainHash blk -> Set ( HeaderHash blk)) 
filterByPredecessor
-> Point blk 
B
-> [ NonEmpty ( HeaderHash blk)]

Each element in the list is a list of hashes from which we can construct a fragment anchored at the point B .

Compute the maximal candidates starting at the specified point

As discussed in the Consensus Report, the set of maximal candidates doesn't include prefixes.

PRECONDITION: the block to which the given point corresponds is part of the VolatileDB.

The first element in each list of hashes is the hash after the specified hash. Thus, when building fragments from these lists of hashes, they fragments must be anchored at the specified hash, but not contain it.

NOTE: it is possible that no candidates are found, but don't forget that the chain (fragment) ending with B is also a potential candidate.

Path

data Path blk Source #

A path through the VolatileDB from a StreamFrom to a StreamTo .

Invariant: the AnchoredFragment (oldest first) constructed using the blocks corresponding to the points in the path will be valid, i.e., the blocks will fit onto each other.

Constructors

NotInVolatileDB ( RealPoint blk)

The end point ( StreamToInclusive end ) was not part of the VolatileDB.

CompletelyInVolatileDB [ RealPoint blk]

A complete path, from start point to end point was constructed from the VolatileDB. The list contains the points from oldest to newest.

  • If the lower bound was StreamFromInclusive pt , then pt will be the first element of the list.
  • If the lower bound was StreamFromExclusive pt , then the first element of the list will correspond to the first block after pt .
  • If the upper bound was StreamToInclusive pt , then pt will be the last element of the list.
PartiallyInVolatileDB ( HeaderHash blk) [ RealPoint blk]

Only a partial path could be constructed from the VolatileDB. The missing predecessor could still be in the ImmutableDB. The list contains the points from oldest to newest.

  • The first element in the list is the point for which no predecessor is available in the VolatileDB. The block corresponding to the point itself, is available in the VolatileDB.
  • The first argument is the hash of predecessor, the block that is not available in the VolatileDB.

Note: if the lower bound is exclusive, the block corresponding to it doesn't have to be part of the VolatileDB, it will result in a StartToEnd .

The same invariants hold for the upper bound as for StartToEnd .

Instances

Instances details
HasHeader blk => Eq ( Path blk) Source #
Instance details

Defined in Ouroboros.Consensus.Storage.ChainDB.Impl.Paths

Methods

(==) :: Path blk -> Path blk -> Bool Source #

(/=) :: Path blk -> Path blk -> Bool Source #

HasHeader blk => Show ( Path blk) Source #
Instance details

Defined in Ouroboros.Consensus.Storage.ChainDB.Impl.Paths

Methods

showsPrec :: Int -> Path blk -> ShowS Source #

show :: Path blk -> String Source #

showList :: [ Path blk] -> ShowS Source #

computePath :: forall blk. HasHeader blk => LookupBlockInfo blk -> StreamFrom blk -> StreamTo blk -> Maybe ( Path blk) Source #

Construct a path backwards through the VolatileDB.

We walk backwards through the VolatileDB, constructing a Path from the StreamTo to the StreamFrom .

If the range is invalid, Nothing is returned.

See the documentation of Path .

Reverse path

data ReversePath blk Source #

A reverse path through the VolatileDB starting at a block in the VolatileDB until we reach genesis or leave the VolatileDB.

Constructors

StoppedAtGenesis

The path stopped at genesis

StoppedAt ( HeaderHash blk) BlockNo

The path stopped at this hash, which is the hash of the predecessor of the last block in the path (that was still stored in the VolatileDB).

The block corresponding to the predecessor is not stored in the VolatileDB. Either because it is missing, or because it is old and has been garbage collected.

Since block numbers are consecutive, we subtract 1 from the block number of the last block to obtain the block number corresponding to this hash.

EBBs share their block number with their predecessor: 

block:         regular block 1 | EBB | regular block 2
block number:                X |   X | X + 1

So when the hash refers to regular block 1, we see that the successor block is an EBB and use its block number without subtracting 1.

Edge case: if there are two or more consecutive EBBs, we might predict the wrong block number, but there are no consecutive EBBs in practice, they are one epoch apart.

( ReversePath blk) ::> ( HeaderFields blk, IsEBB )

Snoc: the block with the given HeaderFields is in the VolatileDB. We also track whether it is an EBB or not.

NOTE: we are intentionally lazy in the spine, as constructing the path requires lookups in the VolatileDB's in-memory indices, which are logarithmic in the size of the index.

computeReversePath Source #

Arguments

:: forall blk. LookupBlockInfo blk
-> HeaderHash blk

End hash

-> Maybe ( ReversePath blk)

Reverse path from the end point to genesis or the first predecessor not in the VolatileDB. Nothing when the end hash is not in the VolatileDB.

Lazily compute the ReversePath that starts (i.e., ends) with the given HeaderHash .

Reachability

isReachable Source #

Arguments

:: forall blk. ( HasHeader blk, GetHeader blk)
=> LookupBlockInfo blk
-> AnchoredFragment ( Header blk)

Chain fragment to connect the point to

-> RealPoint blk
-> Maybe ( ChainDiff ( HeaderFields blk))

Try to connect the point P to the chain fragment by chasing the predecessors.

When successful, return a ChainDiff : the number of blocks to roll back the chain fragment to the intersection point and a fragment anchored at the intersection point containing the HeaderFields corresponding to the blocks needed to connect to P . The intersection point will be the most recent intersection point.

Returns Nothing when P is not in the VolatileDB or when P is not connected to the given chain fragment.

POSTCONDITION: the returned number of blocks to roll back is less than or equal to the length of the given chain fragment.

Note that the number of returned points can be smaller than the number of blocks to roll back. This means P is on a fork shorter than the given chain fragment.

A ChainDiff is returned iff P is on the chain fragment. Moreover, when the number of blocks to roll back is also 0, it must be that P is the tip of the chain fragment.

When the suffix of the ChainDiff is non-empty, P will be the last point in the suffix.