| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Cardano.Crypto.KES.CompactSum
Description
A key evolving signatures implementation.
It is a naive recursive implementation of the sum composition from section 3.1 of the "MMM" paper:
Composition and Efficiency Tradeoffs for Forward-Secure Digital Signatures By Tal Malkin, Daniele Micciancio and Sara Miner https://eprint.iacr.org/2001/034
Specfically we do the binary sum composition directly as in the paper, and then use that in a nested/recursive fashion to construct a 7-level deep binary tree version.
This relies on Cardano.Crypto.KES.CompactSingle for the base case.
Compared to the implementation in Sum, this flavor
stores only one VerKey in the branch node.
Consider the following Merkle tree:
(A)
/
(B) (C)
(D) (E) (F) (G)
^
0 1 2 3
The caret points at leaf node E, indicating that the current period is 1.
The signatures for leaf nodes D through G all contain their respective
DSIGN keys; the signature for branch node B however only holds the signature
for node E, and the VerKey for node D. It can reconstruct its own VerKey
from these two. The signature for branch node A (the root node), then, only
contains the VerKey for node C, and the signature for node B. In other
words, the number of individual hashes to be stored equals the depth of the
Merkle tree. Compare that to the older, naive SumKES, where each branch
node stores two VerKeys: here, the number of keys to store is the depth of
the tree times two.
Note that when we verify such a signature, we need to also compare the ultimate VerKey at the root against the one passed in externally, because all VerKeys until that point have been derived from the (user-supplied, so untrusted) signature. But we only need to do this once, at the tree root, so we split up the verification into two parts: verifying a signature against its embedded VerKey, and comparing that VerKey against the externally supplied target key.
NOTE - some functions in this module have been deliberately marked NOINLINE;
this is necessary to avoid an edge case in GHC that causes the simplifier to
go haywire, leading to a Simplifier ticks exhausted error and very long
compilation times. Worse yet, this error will only appear when compiling
code that depends on this module, not when compiling the module itself.
Synopsis
- data CompactSumKES h d
- data family VerKeyKES v :: Type
- data family SignKeyKES v :: Type
- data family SigKES v :: Type
- type CompactSum0KES d = CompactSingleKES d
- type CompactSum1KES d h = CompactSumKES h (CompactSum0KES d)
- type CompactSum2KES d h = CompactSumKES h (CompactSum1KES d h)
- type CompactSum3KES d h = CompactSumKES h (CompactSum2KES d h)
- type CompactSum4KES d h = CompactSumKES h (CompactSum3KES d h)
- type CompactSum5KES d h = CompactSumKES h (CompactSum4KES d h)
- type CompactSum6KES d h = CompactSumKES h (CompactSum5KES d h)
- type CompactSum7KES d h = CompactSumKES h (CompactSum6KES d h)
Documentation
data CompactSumKES h d #
A composition of two KES schemes to give a KES scheme with the sum of the time periods.
While we could do this with two independent KES schemes (i.e. two types) we only need it for two instances of the same scheme, and we save substantially on the size of the type and runtime dictionaries if we do it this way, especially when we start applying it recursively.
Instances
data family VerKeyKES v :: Type #
Instances
data family SignKeyKES v :: Type #
Instances
data family SigKES v :: Type #
Instances
Type aliases for powers of binary sums
type CompactSum0KES d = CompactSingleKES d #
A 2^0 period KES
type CompactSum1KES d h = CompactSumKES h (CompactSum0KES d) #
A 2^1 period KES
type CompactSum2KES d h = CompactSumKES h (CompactSum1KES d h) #
A 2^2 period KES
type CompactSum3KES d h = CompactSumKES h (CompactSum2KES d h) #
A 2^3 period KES
type CompactSum4KES d h = CompactSumKES h (CompactSum3KES d h) #
A 2^4 period KES
type CompactSum5KES d h = CompactSumKES h (CompactSum4KES d h) #
A 2^5 period KES
type CompactSum6KES d h = CompactSumKES h (CompactSum5KES d h) #
A 2^6 period KES
type CompactSum7KES d h = CompactSumKES h (CompactSum6KES d h) #
A 2^7 period KES