Enable use of VRF batch verification crypto from Conway era onward

[nfrisby]

The crypto team has (re-)prepared newer versions of the VRF and KES algorithms/formats for use in eras after Babbage (ie starting with Conway after the Chang HF). This is materialised as three PI objectives that will involve Consensus:

1. VRF batch-compatibility (requires HF)
2. KES secure forgetting
3. KES signature size reduction (requires HF)

The goal of this issue is to implement batch VRF verification in consensus.

This implies:

• Adapting consensus to be able to use different crypto for VRF verification depending on the era
• Actually calling the batch VRF function from new crypto libraries

[nfrisby]

For reference, this is a previous, backed out PR that might be relevant, or point to relevant upstream commits: PR IntersectMBO/ouroboros-network#3801

[nfrisby]

To clarify, the Crypto team has three PI objectives that will involve Consensus:

• KES secure forgetting
• VRF batch-compatibility (requires HF)
• KES signature size reduction (requires HF)

If I understand correctly, this Issue pertains only to the second to; it does not involve secure forgetting.

[ghost]

From @nfrisby

This Issue tracks the Consensus team's work to integrate those changes into the Conway branch. I think the main challenge will be choosing how to increase the expressiveness of the CardanoBlock type to have varying crypto c arguments to the ShelleyBlocks within the list of eras argument to HardForkBlock. Byron through Babbage will use c1 and Conway will use c2. It should be just a bit more bookkeeping and maybe a few careful placed ~ constraints, but that's all.

[ghost]

I tried latest solution proposed by @yogeshsajanikar in IntersectMBO/ouroboros-network#4151 and it does not work nicely. While I was able to modify O.C.C.Block easily to introduce the type families providing an additional level of indirection to resolve the actual crypto used, I got bitten by this error in the O.C.C.CanHardFork module:

src/Ouroboros/Consensus/Cardano/CanHardFork.hs:308:42: error:
    • Illegal type synonym family application ‘StdCrypto
                                                 c’ in instance:
        CanHardFork (CardanoEras c)
    • In the instance declaration for ‘CanHardFork (CardanoEras c)’
    |
308 | instance CardanoHardForkConstraints c => CanHardFork (CardanoEras c) where
    |                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^

[ghost]

Introducing an additional type variable to CardanoEras promises to be extremely annoying and impactful across the codebase as this implies modifying this type and every other type derived from it (eg. CardanoBlock) everywhere. What I am currently investigating is whether or not this dispatching could not be done at a lower level, eg. at the point where the crypto is used.
Ideally, because we have ProtoCrypto proto and EraCrypto era type families around, it would be nice if I could somehow override those for the ConwayEra (and future) cases where a different crypto is needed.

[ghost]

I have tried several approaches which all failed, following discussions with @dnadales and @nfrisby, starting top-down from the definition of CardanoEras:

• Monomorphising only ConwayEra blocks
• Using type family to add an extra level of indirection leads into issues with class instances not accepting type family instances in the LHS
• Turning into a linked list of cryptos does not seem to work either esp. in the transition functions

So there is a unit test in place that should fail and then succeed at some point when implementing correctly the dispatching but I wasn't able to have it implemented, and I think the crux of the issue is that the consensus code does not control how the crypto (for VRF and KES at least) is related to each era as this is defined in the ledger. So this points back to cardano-ledger#3262 PR which aims at splitting the Crypto class in 2, one for hashes and signatures, the other one for VRF and KES which has a very limited use in ledger and probably should be moved to consensus anyway.

@lehins insisted on the potential impact of what we are doing here in the cardano-node codebase as StandardCrypto is used all over the place (>350 occurrences) so this is another thing to keep in mind.

I still very much would like to find a way to introduce stronger boundaries between consensus types and ledger types so that those kind of changes could be less impactful and more easily implemented in a modular way.

[ghost]

Rebasing PR 3262 on newest ledger is not trivial and I am still failing to understand why this change in ledger is needed on the consensus side. Or rather, I feel that if this change is really needed, then something is wrong in our architecture and we should fix that, which might be the point of 3262 but then we should clarify the scope of this work.

[ghost]

It's already been a couple of weeks since I have started working on this, and it's time to take step back and distill what I learn about the problem and the potential solutions. The introductory comment to this issue defines the goal and frame it in the broader context of support for Conway era and new cryptography implementations improving security.

This is probably old news to most but here is what I learnt. The whole consensus code is currently parameterised over a single Crypto c variable which is passed to all important data structures, most notably the block, headers, transactions...

• The core of it all is the Crypto type-class which is defined in the cardano-ledger codebase and provides 5 type families for various crypto primitive types. The instance of those types are tied to implementation of various crypto type-classes like VRFAlgorithm, HashAlgorithm... In the context of this issue we need to inject 2 different instances of Crypto (or a refinement of this, see below): StandardCrypto where type VRF StandardCrypto = PraosVRF and BatchCrypto where type VRF BatchCrypto = PraosBatchCompatVRF
  • Note that while the cardano-crypto-class and cardano-crypto-tpraos packages provide type-classes that abstract the concrete implementation of crypto primitives (most often backed up on libsodium) and are parameterised for some specific type of crypto (eg. VRF, KES, Hash...), the ledger redefines a lot of similar functions types in terms of Crypto class, hiding the type family used
• The entry point is located in the O.C.C.Block module which defines the structure of each eras' block.
• The ShelleyBlock is parameterised by both an instance of ConsensusProtocol (either a Praos c or TPraos c) and a ledger Era with the constraint that both ProtoCrypto and EraCrypto be identical
• CardanoEras are used mainly to provide a "concrete" instance of CanHardFork which defines all the translation functions that are needed for hard forks: Translating various parts of the state, selecting chain across hard forks, injecting transactions. This module also defines pairwise translation functions for each pair of eras it has to cross
• Depending on the part of the code, either the ProtoCrypto or the EraCrypto's Crypto instances are used to provide access to crypto functions for everything like signatures, hashing, verifications...
• At the lowest level, each ConsensusProtocol instance defines what it means to verify blocks, update chain state, etc.

What I have done/attempted so far, along with some comments about it:

• There is a unit test that's currently failing and is supposed to assert the correct "dispatching"
• I have started over from Block several times trying to find different ways of providing different eras with different cryptos:
  • The solution that's been proposed in Groom Issue 4150, VRF and KES ouroboros-network#4151 is appealing: Provide a CryptoVersions type class encapsulating two or more versions of cryptos defined as type families so that we can keep a single type parameters in CardanoEras that will be instantiated with an empty crypto type whose CryptoVersions instance resolve to relevant concrete cryptos.
  • However, this failed to compile because GHC does not accept type families in the head of type class instances and I did not know how to solve the issue when I faced it
  • So I ended up implementing the dumb solution of providing 2 crypto parameters to CardanoEras which worked mostly ok except when it came to the definition of CanHardFork
• To be able to define CanHardFork with some era transition requiring 2 cryptos, I needed to define a TranslateProto (Praos c1) (Praos c2) which works fine given the VRF keys are identical between the 2 cryptos
• In general, the only difference between the current and future VRF crypto is in the Proof which is packed with the CertifiedVRF, everything is compatible and the cardano-crypto-tpraos package provides conversion functions where needed. The CertifiedVRF appears in the BlockHeader of Praos but is never stored in the ledger state nor in the transactions which is good because we don't translate blocks.
  • This observation implies that future changes to the crypto should follow a similar pattern: Anything that's stored in the LedgerState or Tx must be convertible across successive eras and cryptos. We must preserve backward compatibility forever.
• I have also tried to attack the problem from the other side, eg. introduce a HeaderCrypto type class that would seemingly make it easier to handle different cryptos across eras but I am unsure this change is really critical. It's definitely an improvement as it decouples the part that will change from the part that's guaranteed to stay constant (basic Hash functions and key formats), but for the purpose of handling multiple crypto in consensus I think we can work with the Crypto we have now and do the split later

So the current situation is that I am blocked in CanHardFork on various translations issues:

• Oddly enough, changes I made broke the translation from Byron to Shelley because of not unified type variables
• I don't know how to translate tx ids and txs
• I don't know how to translate the ledger state

The latter two might entail changes in the ledger code but the crypto should be compatible anyway so perhaps the changes would be minimal?

[ghost]

With @amesgen and @dnadales we were able to make good progress and get to the point where CanHardFork compiles with some hopefully mundane and boilerplate undefineds left to translate ledger state and transactions across eras with different crypto.
Then the next big step is fixing the crypto type variables handling in the Node module which ties everything together and handles configuration.

Key takeaways:

• Having a single crypto parameter on CardanoEra with proper type families for instantiation at proper eras would definitely be better and this seems actually doable with some proper constraints
• Translation of ledger types would probably be mostly obsoleted by separation of Crypto and HeaderCrypto as the latter is the main moving part. Still, we store information about VRF (keys?) in ledger state might still require conversion
• ShelleyBlock could be properly aliased per era to simplify some declarations
• HotKey module depends on Crypto. Like VRF from praos, it should probably depend on lower level types from cardano-crypto-class in order to remove or simplify the need to translate between cryptos when the types are ultimately identical
• There are dependencies on genesisShelley which should be simplified or replaced with dependencies on the content of GenesisShelley which is mostly independent on crypto

[lehins]

we store information about VRF (keys?) in ledger state might still require conversion

Keys are stored in the ledger state, only the hashes of the keys. So, if new batch compat VRF crypto keys are compatible in binary form, then no translation is necessary. It looks like they are compatible, but I might be missing some context: https://github.com/input-output-hk/cardano-base/blob/2c1486e0bcece554b46a05d4fbefb13cbe673630/cardano-crypto-praos/src/Cardano/Crypto/VRF/Praos.hs#L427-L431

[ghost]

@lehins They are indeed identical but the typechecker is still unhappy, I have had to walk the various data structures to be able to convert between 2 crypto types even though the representations are the same. I may be missing something obvious but I could not appease the type gods otherwise.

[ghost]

Latest status: Most packages of the branch compile and o-c-c-test run, however they still fail because I am not able to use 2 different cryptos with the generators, so I may have done something wrong somewhere, perhaps a rogue equality constraint or something.

[ghost]

If anyone wants to pick this up before next week, here is the current situation:

• CardanoEras and related types (eg. CardanoBlock, CardanoHeader are parameterised by 2 type variables denoting standard crypto and new crypto for Conway era. This is suboptimal but can be fixed later once everything works,
• The T.O.C.C.Crypto test does not pass as there seems to be some constraint somewhere enforcing the 2 cryptos to be equal,
• There are bunch of translateXXX functions for ledger data structures scattered all over the place. Those should either be grouped somewhere, perhaps in a dedicated TranslateCrypto module, or disappear once we have HeaderCrypto in place (?),
• I did not bother enforcing proper formatting,
• I made various changes here and there to make the compiler happy (eg. introduce some instances, remove some dependencies on Crypto...) and also make the code more understandable to in places where I hit the SOP wall. In particular I deleted ShelleyBased module which had a very generic overShelleyXXX function that was used only once and actually needed different functions on different eras which precluded the use of HO mapping.

[abailly]

Thanks to @nfrisby's sharp eye and deep expertise, I was able to solve the c1 ~ c2 spurious constraint problem I was blocked on. Turns out I threw in some VerKeyDSIGN c1 ~ VerKeyDSIGN c2 constraint which implied c1 ~ c2 because of injectivity where it was not strictly needed (can't remember why I did this, perhaps followed GHC's suggestions...).

So I now have a branch that nearly could work as is and enables different VRF crypto for Conway than we now have in Babbage, albeit with some abuse of translateXXX functions to transform ledger state and blocks from one era to the other. I think I will try to finish that version so that we at least have a "Dirt road solution" before we move to using HeaderCrypto which should be introduced by Yogesh in cardano-ledger thanks to this PR

[ghost]

Blocked on IntersectMBO/cardano-ledger#3388 and repository migration

[dnadales]

At the moment we do not have this among our priorities, so we're putting this on hold.