| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Ouroboros.Consensus.Peras.Weight
Description
Data structure for tracking the weight of blocks due to Peras boosts.
Synopsis
- data PerasWeightSnapshot blk
- emptyPerasWeightSnapshot ∷ PerasWeightSnapshot blk
- mkPerasWeightSnapshot ∷ StandardHash blk ⇒ [(Point blk, PerasWeight)] → PerasWeightSnapshot blk
- perasWeightSnapshotToList ∷ PerasWeightSnapshot blk → [(Point blk, PerasWeight)]
- addToPerasWeightSnapshot ∷ StandardHash blk ⇒ Point blk → PerasWeight → PerasWeightSnapshot blk → PerasWeightSnapshot blk
- prunePerasWeightSnapshot ∷ SlotNo → PerasWeightSnapshot blk → PerasWeightSnapshot blk
- isEmptyPerasWeightSnapshot ∷ PerasWeightSnapshot blk → Bool
- weightBoostOfPoint ∷ StandardHash blk ⇒ PerasWeightSnapshot blk → Point blk → PerasWeight
- weightBoostOfFragment ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) ⇒ PerasWeightSnapshot blk → AnchoredFragment h → PerasWeight
- totalWeightOfFragment ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) ⇒ PerasWeightSnapshot blk → AnchoredFragment h → PerasWeight
- takeVolatileSuffix ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) ⇒ PerasWeightSnapshot blk → SecurityParam → AnchoredFragment h → AnchoredFragment h
PerasWeightSnapshot type
data PerasWeightSnapshot blk Source #
Data structure for tracking the weight of blocks due to Peras boosts.
Instances
Construction
emptyPerasWeightSnapshot ∷ PerasWeightSnapshot blk Source #
An empty PerasWeightSnapshot not containing any boosted blocks.
mkPerasWeightSnapshot ∷ StandardHash blk ⇒ [(Point blk, PerasWeight)] → PerasWeightSnapshot blk Source #
Create a weight snapshot from a list of boosted points with an associated weight. In case of duplicate points, their weights are combined.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>snap = mkPerasWeightSnapshot weights>>>snap[(Point Origin,PerasWeight 3),(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 4),(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
Conversion
perasWeightSnapshotToList ∷ PerasWeightSnapshot blk → [(Point blk, PerasWeight)] Source #
Return the list of boosted points with their associated weight, sorted based on their point. Does not contain duplicate points.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>snap = mkPerasWeightSnapshot weights>>>perasWeightSnapshotToList snap[(Point Origin,PerasWeight 3),(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 4),(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
Insertion
addToPerasWeightSnapshot ∷ StandardHash blk ⇒ Point blk → PerasWeight → PerasWeightSnapshot blk → PerasWeightSnapshot blk Source #
Add weight for the given point to the PerasWeightSnapshot. If the point
already has some weight, it is added on top.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) ] :}
>>>snap0 = mkPerasWeightSnapshot weights>>>snap0[(Point Origin,PerasWeight 3),(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 2)]
>>>snap1 = addToPerasWeightSnapshot (BlockPoint 3 "bar") (PerasWeight 2) snap0>>>snap1[(Point Origin,PerasWeight 3),(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 2),(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
>>>snap2 = addToPerasWeightSnapshot (BlockPoint 2 "foo") (PerasWeight 2) snap1>>>snap2[(Point Origin,PerasWeight 3),(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 4),(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
Pruning
prunePerasWeightSnapshot ∷ SlotNo → PerasWeightSnapshot blk → PerasWeightSnapshot blk Source #
Prune the given PerasWeightSnapshot by removing the weight of all blocks
strictly older than the given slot.
This function is used to get garbage-collect boosted blocks blocks which are older than our immutable tip as we will never adopt a chain containing them.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>snap = mkPerasWeightSnapshot weights
>>>prunePerasWeightSnapshot (SlotNo 2) snap[(Point (At (Block {blockPointSlot = SlotNo 2, blockPointHash = "foo"})),PerasWeight 4),(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
>>>prunePerasWeightSnapshot (SlotNo 3) snap[(Point (At (Block {blockPointSlot = SlotNo 3, blockPointHash = "bar"})),PerasWeight 2)]
Query
isEmptyPerasWeightSnapshot ∷ PerasWeightSnapshot blk → Bool Source #
Check whether the snapshot contains weights for any blocks.
>>>isEmptyPerasWeightSnapshot emptyPerasWeightSnapshotTrue
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>snap = mkPerasWeightSnapshot weights
>>>isEmptyPerasWeightSnapshot snapFalse
weightBoostOfPoint ∷ StandardHash blk ⇒ PerasWeightSnapshot blk → Point blk → PerasWeight Source #
Get the weight boost for a point, or otherwise.mempty :: PerasWeight
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>snap = mkPerasWeightSnapshot weights
>>>weightBoostOfPoint snap (BlockPoint 2 "foo")PerasWeight 4
>>>weightBoostOfPoint snap (BlockPoint 2 "baz")PerasWeight 0
weightBoostOfFragment ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) ⇒ PerasWeightSnapshot blk → AnchoredFragment h → PerasWeight Source #
Get the weight boost for a fragment, ie the sum of all
weightBoostOfPoint for all points on the fragment (excluding the anchor).
Note that this quantity is relative to the anchor of the fragment, so it should only be compared against other fragments with the same anchor.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>:{snap = mkPerasWeightSnapshot weights foo = HeaderFields (SlotNo 2) (BlockNo 1) "foo" bar = HeaderFields (SlotNo 3) (BlockNo 2) "bar" frag0 :: AnchoredFragment (HeaderFields Blk) frag0 = Empty AnchorGenesis :> foo :> bar :}
>>>weightBoostOfFragment snap frag0PerasWeight 6
Only keeping the last block from frag0:
>>>frag1 = AF.anchorNewest 1 frag0>>>weightBoostOfFragment snap frag1PerasWeight 2
Dropping the head from frag0, and instead adding an unboosted point:
>>>frag2 = AF.dropNewest 1 frag0 :> HeaderFields (SlotNo 4) (BlockNo 2) "baz">>>weightBoostOfFragment snap frag2PerasWeight 4
totalWeightOfFragment ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) ⇒ PerasWeightSnapshot blk → AnchoredFragment h → PerasWeight Source #
Get the total weight for a fragment, ie the length plus the weight boost
(weightBoostOfFragment) of the fragment.
Note that this quantity is relative to the anchor of the fragment, so it should only be compared against other fragments with the same anchor.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] :}
>>>:{snap = mkPerasWeightSnapshot weights foo = HeaderFields (SlotNo 2) (BlockNo 1) "foo" bar = HeaderFields (SlotNo 3) (BlockNo 2) "bar" frag0 :: AnchoredFragment (HeaderFields Blk) frag0 = Empty AnchorGenesis :> foo :> bar :}
>>>totalWeightOfFragment snap frag0PerasWeight 8
Only keeping the last block from frag0:
>>>frag1 = AF.anchorNewest 1 frag0>>>totalWeightOfFragment snap frag1PerasWeight 3
Dropping the head from frag0, and instead adding an unboosted point:
>>>frag2 = AF.dropNewest 1 frag0 :> HeaderFields (SlotNo 4) (BlockNo 2) "baz">>>totalWeightOfFragment snap frag2PerasWeight 6
Arguments
| ∷ (StandardHash blk, HasHeader h, HeaderHash blk ~ HeaderHash h) | |
| ⇒ PerasWeightSnapshot blk | |
| → SecurityParam | The security parameter |
| → AnchoredFragment h | |
| → AnchoredFragment h |
Take the longest suffix of the given fragment with total weight
(totalWeightOfFragment) at most k. This is the volatile suffix of blocks
which are subject to rollback.
If the total weight of the input fragment is at least k, then the anchor of
the output fragment is the most recent point on the input fragment that is
buried under at least weight k (also counting the weight boost of that
point).
See mkPerasWeightSnapshot for context.
>>>:{weights :: [(Point Blk, PerasWeight)] weights = [ (BlockPoint 2 "foo", PerasWeight 2) , (GenesisPoint, PerasWeight 3) , (BlockPoint 3 "bar", PerasWeight 2) , (BlockPoint 2 "foo", PerasWeight 2) ] snap = mkPerasWeightSnapshot weights foo = HeaderFields (SlotNo 2) (BlockNo 1) "foo" bar = HeaderFields (SlotNo 3) (BlockNo 2) "bar" frag :: AnchoredFragment (HeaderFields Blk) frag = Empty AnchorGenesis :> foo :> bar :}
>>>k1 = SecurityParam $ knownNonZeroBounded @1>>>k3 = SecurityParam $ knownNonZeroBounded @3>>>k6 = SecurityParam $ knownNonZeroBounded @6>>>k9 = SecurityParam $ knownNonZeroBounded @9
>>>AF.toOldestFirst $ takeVolatileSuffix snap k1 frag[]
>>>AF.toOldestFirst $ takeVolatileSuffix snap k3 frag[HeaderFields {headerFieldSlot = SlotNo 3, headerFieldBlockNo = BlockNo 2, headerFieldHash = "bar"}]
>>>AF.toOldestFirst $ takeVolatileSuffix snap k6 frag[HeaderFields {headerFieldSlot = SlotNo 3, headerFieldBlockNo = BlockNo 2, headerFieldHash = "bar"}]
>>>AF.toOldestFirst $ takeVolatileSuffix snap k9 frag[HeaderFields {headerFieldSlot = SlotNo 2, headerFieldBlockNo = BlockNo 1, headerFieldHash = "foo"},HeaderFields {headerFieldSlot = SlotNo 3, headerFieldBlockNo = BlockNo 2, headerFieldHash = "bar"}]