Handling 96 bits with Minisketch

[aymericcousaert]

I am wondering how I can extend Minisketch to support 96 bits. Maybe you can help me understand what are the SQR_TABLE, the QRT_TABLE, the typedef RecLinTrans<.> and how to fill them up ? Thank you

[sipa]

This would require a significant change, as there is no integer datatype that holds >64 bits. We'd need a pair of 2 ints, overloaded to support XOR and a few other things, plus tables of it, ... The SQR_TABLE and others are all generated by the sage script; we'd need to update that as well.

However, if there is a good use case for supporting 96 bit fields, I'm happy to work on that.

[aymericcousaert]

Thanks for the details. Perhaps a triplet of uint32_t could be used ?

A 96 bits minisketch would be useful to hold both timestamp and short_channel_id and allow faster sync for lightning nodes, right ?

[sipa]

I know nothing about Lightning.

Yeah, a triplet of 32-bit ints would probably work, but be slower.

[gmaxwell]

@aymericcousaert see the provided protocol design tips: https://github.com/sipa/minisketch/blob/master/doc/protocoltips.md

In a reconciliation protocol you will almost always want to use keys no longer than is needed to make collisions between distinct items negligibly likely for both performance and communications cost reasons. If your natural keys are larger than that, you'll want to shrink them via hashing.

If you have auxiliary data which you might want to carry with your items (like metadata that might influence your syncing priorities) which itself is non-uniform enough or large enough to not be a good part of the key, a protocol should probably provide the aux data using an additional round trip. if a round trip isn't possible an erasure code can, i suggested previously that minisketch might want to provide one (esp since it would share most of the code, and can be used to make group reconcillation more efficient by using it to network-code a sketch). This can save a lot of bandwidth: Say 30 bits are enough for unambiguous reconciliation but to know if you will accept an item you also need a 32 byte public key. You know the keys already for the items you have. Say you have 100 items the far end lacks and the far end has 100 keys you lack. if the pubkeys are included directly in the sketch you'll expend 7150 bytes on the sketch, if the pubkeys are requested with another round trip or using an erasure code you'll need only 750+3200=3950 bytes.

Support for larger keys would be good for a few applications: keys as large as 128 bits might be needed in some reconciliation applications to make collision probabilities negligible for applications with really big databases or robust against adversarial inputs when salted hashing isn't possible. Keys 128-512 bits (or bigger?) might be needed for some applications that are relying on the information theoretic properties of sketches (e.g. DCnets, or biometrics).

Support for multi-word operations might also radically improve performance on 32-bit hardware for 32-64 bit keys, which are currently pretty slow on hardware that doesn't have native 64-bit integers.

[adamierymenko]

Recent GCC and Clang support uint128_t. Then there's Rust which also supports 128-bit types natively in the language. Those would be options if you want.