SerializedPublicKey

[Kixunil]

There was discussion in #1084 about what should this type do. My intention was (and still is) for it to be just a bunch of bytes just like Box<[u8]> without heap allocation - a replacement for Vec<u8> returned from to_bytes(). The original idea was solely to improve serialization performance by avoiding allocations and perhaps allow no-alloc in the future.

There were some ideas that it could do something more. Methods for hashing seem reasonable to me but there are even more exotic ideas that I don't find appealing.

Example implementation of my idea

[junderw]

From the other thread:

Kixunil: I only want SerializedPublicKey to be a bunch of bytes similar to Box<[u8]> (yep, not even Vec) with the only difference being it's not heap allocated. The fact that it happens to provide ordering that happens to be in line with Core/BIP-67 is a nice side effect.

The more we discussed SerializedPublicKey the more I lost sight of its usefulness.

In the context of SortKey PR I thought "ok, so this is an alternative for SortKey + alpha" and I tried to figure out what that "alpha" was and ended up just getting lost.

I think it might be best to go over what bitcoin:PublicKey does/doesn't do and what SerializedPublicKey should/shouldn't do.

Just because it's not really a debate I'll start off with listing what bitcoin::PublicKey does/doesn't do.

• bitcoin::PublicKey
  1. Does
     1. Guarantee it holds a valid point (paying for validation up front)
     2. Create instance from secp256k1::PublicKey OR PrivateKey OR reader/slice (fallible, as it uses secp256k1::PublicKey::from_slice which returns a Result)
     3. Get keyhash and witnesskeyhash (uses serialize*())
     4. Get Vec<u8> serialization / write to writer (uses serialize*())
  2. Doesn't
     1. Follow expected Ord behavior compared to other parts of the bitcoin ecosystem
        • This is semi-solved by using the to_sort_key() from my PR with a sort_by_key() type method on slice.
     2. Have DER serialized bytes in its data structure or in any sort of cache.

If we can agree on this, I would be interested in everyone's thoughts on what a potential SerializedPublicKey should/shouldn't do/be.

It seems like the main point of change is ii. b. with ii. a. being a bonus side effect.

But what kinds of methods / properties should it have and why would that be useful? (psuedo-code examples of a short use case might help visualize)

[apoelstra]

Bear in mind that we could obviously implement Ord by serializing the keys inside of the cmp method. This would be really slow compared to just memcmp'ing a byte array (an additional 20-30 nanoseconds per comparison, I think, on my system) but very fast in an absolute sense.

Validating/deserializing a public key, to contrast, is around 7 microseconds, so 30x slower.

I think your summary is good @junderw. The benefit of SerializedPublicKey would be (a) to cache the serialization, and maybe (b) to provide a type that does not validate the key, for performance reasons and to emulate Core's behavior (not validating keys until it needs to do so in order to validate a signature...then blaming the signature if the key is bad).

I think Core's behavior is dumb but the performance benefit is undeniable.

[Kixunil]

@junderw nice list of properties!

I tried to figure out what that "alpha" was and ended up just getting lost.

For me it's just avoiding allocation in serialization. bitcoin::PublicKey doesn't provide a heap-allocation-free serialization method. IOW serializing it is costly and requires use of the alloc crate.

SerializedPublicKey is a complete, Rust-idiomatic solution to the problem I describe and happens to be naturally useful as a sort key with the only additional requirement being a reasonably simple manual implementation of Ord/ParialOrd.

I never intended to use it for anything else but if people will find it useful I'm open to hash methods and perhaps even constructing it with light validation (would need discussion later).

I propose to only implement minimal API for now, until people actually need more:

• as_slice() method
• Deref, AsRef, Borrow
• All impls that are normally derived, except Default; comparisons/Hash implemented manually
• owned and borrowed IntoIterator, iter() method
• IntoIter with the same API as alloc::vec::IntoIter (including as_slice())
• Display as hex

I think Core's behavior is dumb but the performance benefit is undeniable.

Agreed and interestingly there's a case where something like this is actually preferred: in Lightning it's much better to process graph without key (node ID) validation. But the keys there are always compressed, so this is out-of-scope here.

[apoelstra]

Ah, I understand, I missed the fact that serialization in our current API requires allocation, and that SerializedPublicKey would cleanly resolve that.

Not to add another point of argument, but I wonder whether SerializedPublicKey belongs in rust-secp or in rust-bitcoin..

[junderw]

Isn't to_bytes the only allocation?

[apoelstra]

@junderw yes...and it is the only way to get a serialized public key.

[Kixunil]

@apoelstra AFAIR rust-secp doesn't provide any serialization with dynamic length but an argument could be made that it could be handy for some people.

@junderw yes. Vec always indicates allocation.

[apoelstra]

@Kixunil we do actually, we have a SerializedSignature type which is essentially the same thing you are proposing, but for signatures :)

[Kixunil]

Sorry, I meant serialization of a key.