Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Introduce header revalidation #2520

Closed
mrBliss opened this issue Aug 18, 2020 · 1 comment
Closed

Introduce header revalidation #2520

mrBliss opened this issue Aug 18, 2020 · 1 comment
Assignees
Labels
consensus issues related to ouroboros-consensus optimisation Performance optimisation

Comments

@mrBliss
Copy link
Contributor

mrBliss commented Aug 18, 2020

As mentioned in IntersectMBO/cardano-ledger#1785 (comment), the majority of block replay time is spent in C functions doing crypto checks, see the two top of the profiling report:

COST CENTRE   SRC                                               %time  %alloc
verify        src/Cardano/Crypto/VRF/Praos.hs:(388,1)-(397,33)   46.9    0.1
verify        Crypto/PubKey/Ed25519.hs:(107,1)-(114,30)           6.3    0.0

Both are part of validateHeader, which accounts for 63.2% of the time and 11.6% of the allocations.

Note that this is when we're reapplying blocks, so we know these blocks and thus their headers are already valid. While we already distinguish between block body application and reapplication, we don't do the same thing for block header validation.

Header validation consists of three parts:
https://github.com/input-output-hk/ouroboros-network/blob/cfb465726c9d023ad3ab2a3030d847df27787c3d/ouroboros-consensus/src/Ouroboros/Consensus/HeaderValidation.hs#L474-L492

  1. validateEnvelope, which is cheap, but could be skipped during header revalidation. Maybe leave it in as a basic sanity check?

  2. updateChainDepState, expensive, as Shelley's implementation uses the Prtcl rule, which calls the Overlay rule, which includes pbftVrfChecks (current hotspot) and praosVrfChecks (likely the future hotspot when more decentralised). The Overlay rule also calls the Ocert rule, which does a KES check with verifySignedKES, which is the second verify from the profiling report.

    Both of these checks should not be needed during revalidation. However, the Prtcl rule and its subrules do update some state, i.e., the ChainDepState, so we can't just not call these rules.

    If the ledger provides a version of updateChainDepState (note that this is a function in cardano-ledger-specs, provided exactly to be used for the Shelley implementation of consensus' updateChainDepState function) that skips the VRF and KES checks, we can use that in consensus to speed up header revalidation.

  3. headerStatePush, cheapest of all three and required, as it builds up required state. Must be included in revalidation.

Consensus changes:

  • Introduce the reupdateChainDepState method in the ConsensusProtocol class, similar to updateChainDepState, but its implementation can assume updateChainDepState has been called before with the same header so it can skip the expensive crypto checks. I'm not sure yet whether it will still return an Except or just the updated ChainDepState.
  • Introduce a function called revalidateHeader in Ouroboros.Consensus.HeaderValidation (to be used when reapplying blocks here), which calls validateEnvelope, headerStatePush, and reupdateChainDepState.
@mrBliss mrBliss added consensus issues related to ouroboros-consensus optimisation Performance optimisation priority medium labels Aug 18, 2020
@mrBliss mrBliss self-assigned this Aug 18, 2020
nc6 added a commit to IntersectMBO/cardano-ledger that referenced this issue Aug 18, 2020
Used for IntersectMBO/ouroboros-network#2520

This allows the avoidance of expensive crypto checks during block
reapplication, and shoudl shave something like 60% of the time off of
block reapplication.
@mrBliss mrBliss added this to the S20 2020-08-27 milestone Aug 18, 2020
mrBliss added a commit that referenced this issue Aug 18, 2020
Implements the plan described in #2520.

My block revalidation test went from 1m52s to 45s, which nicely matches the
expected speed-up: header validation took ~60% of the time.
mrBliss added a commit that referenced this issue Aug 18, 2020
Implements the plan described in #2520.

My block revalidation test went from 1m52s to 45s, which nicely matches the
expected speed-up: header validation took ~60% of the time.
iohk-bors bot added a commit that referenced this issue Aug 18, 2020
2521: Introduce header revalidation to speed up Shelley block revalidation r=mrBliss a=mrBliss

Implements the plan described in #2520.

My block revalidation test went from 1m52s to 45s, which nicely matches the
expected speed-up: header validation took ~60% of the time.

Co-authored-by: Thomas Winant <thomas@well-typed.com>
@mrBliss
Copy link
Contributor Author

mrBliss commented Aug 18, 2020

Closed by #2521.

@mrBliss mrBliss closed this as completed Aug 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
consensus issues related to ouroboros-consensus optimisation Performance optimisation
Projects
None yet
Development

No branches or pull requests

1 participant