9·
2 months agoSkew binary trees. They’re an immutable data structure combining the performance characteristics of lists (O(1) non-amortized push/pop) and b-trees (log(N) lookup and updates)
They use a sequence of complete trees, cleverly arranged using skew binary numbers so that adding an element never causes cascading updates.
In practice they’re superseded by relaxed radix balanced trees.
The server still has to send its own key, so that part is bigger. They’re making up the space by replacing traditional CA signatures and intermediate certificates with merkle tree hash-based signatures.
Raw number of bytes can’t be directly compared between cryptography schemes, cryptographic hashes make very efficient use of space and don’t have the same quantum weaknesses that old public key cryptography has. The quantum-unsafe RSA signatures being replaced are about 256 bytes, the new ML-DSA signatures are about 2400 bytes, and SHA-256 Merkle tree references are 32 bytes for the same level of security and quantum-proofness.