Optimize the encoded sizes of notes (multi-notes).

[dpc]

It seems like printing mint notes on QR codes is already kind of meh because a single note doesn't fit even on one readable QR code.

Could we do better?

[dpc]

> fedimint-cli spend 1msat
2023-10-10T18:20:47.975217Z  INFO fedimint_client::sm::executor: Starting state machine executor task
2023-10-10T18:20:47.992923Z  INFO fedimint_cli::client: Spend e-cash operation: 268918d235188e7c116917619bf507f4535d501fa9a51010423287dcaeb52481
2023-10-10T18:20:47.993056Z  INFO fedimint_client: Last client reference dropped, shutting down client task group
2023-10-10T18:20:47.993257Z  INFO fedimint_client::sm::executor: Shutting down state machine executor runner due to shutdown signal
{
  "notes": "kf/I9C5lwlSndrUo7dt5NEVy2Ecb8bx4G5bmbQdtG7ujGhTEaHZNniHnu/pgZ6X0AQEBiqT2DVKCg51ljiQk1NGjDRD2r+cKnq1JQwE2NZcQdLGLU5NLNe5AwmdLIanj2tVRC0mxXBpXNI6dh1lS6KNgPj5X0ZBclEEUMelLFbbh9wQqOhavjMzKF4QUzTQWC+IuxBT8zgmMrVl4mg1lmlyC+w=="
}

[dpc]

pub struct SpendableNote {
    pub note: Note,
    pub spend_key: KeyPair, // 96 bytes
}

pub struct KeyPair([c_uchar; 96]);

Why is it a KeyPair? Couldn't it be a just a secret key? Seems like it's:

pub const SECRET_KEY_SIZE: usize = 32;

?

[dpc]

Do we need a full FederationId?

pub struct OOBNotes {
    pub federation_id: FederationId,  // 48 bytes, it seems.
    pub notes: TieredMulti<SpendableNote>,
}

[dpc]

pub struct TieredMulti<T>(BTreeMap<Amount, Vec<T>>);

If we were to standardize on powers of two https://github.com/fedimint/fedimint/discussions/3327 we could encode Amounts of exponents BTW. Right now each note is 1-8 bytes, while it probably could always be 1 byte.

[dpc]

@wbobeirne Seems like plenty of room for improvement.

[tvolk131]

If we were to standardize on powers of two #3327 we could encode Amounts of exponents

Let me try and flesh out what I think you're describing here, for my own understanding.

Under the hood, we could store an Amount as an integer representing the power (in base-2) rather than the actual number of mSats. So for example:

1 mSat note is stored as 0 2 mSat note is stored as 1 4 mSat note is stored as 2 8 mSat note is stored as 3 16 mSat note is stored as 4 etc...

And whenever we want to get the actual mSat amount, we can take the underlying value x and perform 2^x, thus allowing us to store an Amount using a u8 since the max value of an 8-bit unsigned integer is 255 and 2^255 mSats would be 2.75*10^66 greater than the entire supply of all 21 million coins.

Am I understanding your proposal?

[elsirion]

Why is it a KeyPair? Couldn't it be a just a secret key?

The Encodable impl for KeyPair only serializes the secret key ;) KeyPairs are just nicer to work with for schnorr sigs in libsecp.

A near optimal encoding imo:

• Federation ID checksum: 8bytes or so, sufficiently collision resistant
• Notes Vec instead of TieredMulti (at least for base 2 this is way better): typically 1 byte varint len field
  • Denomination index: 1byte
  • Spend key (KeyPair): 32bytes
  • Mint Signature: 48 bytes
  • Leave out the Nonce which is currently (redundantly) in the Note and amounts to another 32bytes, we can generate it from the spend key

This would give us bags of n notes typically 9+n*81 bytes large, or roughly (9+n*81)/3*4 characters in base64.

When encoding as a QR code (or multiple using qrloop or similar) we should not base64 encode first, since the resulting base64 will be treated as binary again anyway.

[dpc]

If we were to standardize on powers of two #3327 we could encode Amounts of exponents

Let me try and flesh out what I think you're describing here, for my own understanding.

Under the hood, we could store an Amount as an integer representing the power (in base-2) rather than the actual number of mSats. So for example:

1 mSat note is stored as 0 2 mSat note is stored as 1 4 mSat note is stored as 2 8 mSat note is stored as 3 16 mSat note is stored as 4 etc...

And whenever we want to get the actual mSat amount, we can take the underlying value x and perform 2^x, thus allowing us to store an Amount using a u8 since the max value of an 8-bit unsigned integer is 255 and 2^255 mSats would be 2.75*10^66 greater than the entire supply of all 21 million coins.

Am I understanding your proposal?

Yes.

[dpc]

pub spend_key: KeyPair, // 96 bytes

Well, actually

impl Encodable for bitcoin::KeyPair {
    fn consensus_encode<W: Write>(&self, writer: &mut W) -> Result<usize, Error> {
        self.secret_bytes().consensus_encode(writer)
    }
}

so no savings here. I discovered it after I actually implemented it. :D

[elsirion]

Under the hood, we could store an Amount as an integer representing the power (in base-2) rather than the actual number of mSats. So for example:

Please don't use powers, we do not save anywhere which base was used to generate our denominations and all we can do is guess and verify. A much simpler approach is ordering all existing denominations and using the index of each. That should be the same for our current standard denominations but won't blow up spectacularly if someone uses non-standard ones.

[dpc]

A much simpler approach is ordering all existing denominations and using the index of each.

Comes at the cost of needing the list of denominations during conversion, but agreed it's more robust at the same encoding footprint, so probably worth it.

[dpc]

Federation ID checksum: 8bytes or so, sufficiently collision resistant

Do we use it only for UX or also for security? For UX probably 4 would be plenty. For security 8B has only 4B of security against birthday attacks... which I don't know if it's OK.

[elsirion]

Do we use it only for UX or also for security?

UX only for now.

[dpc]

In order: original, fed_id_prefix, snote-no-nonce, all

"notes": "kf/I9C5lwlSndrUo7dt5NEVy2Ecb8bx4G5bmbQdtG7ujGhTEaHZNniHnu/pgZ6X0AQEBiqT2DVKCg51ljiQk1NGjDRD2r+cKnq1JQwE2NZcQdLGLU5NLNe5AwmdLIanj2tVRC0mxXBpXNI6dh1lS6KNgPj5X0ZBclEEUMelLFbbh9wQqOhavjMzKF4QUzTQWC+IuxBT8zgmMrVl4mg1lmlyC+w=="
"notes": "kDZuAwEBAdBrqIwRc3GWVTdKgWoWpGSsNb3lYLBHKsy4stBUI5UmljLvjux7kce+MwhYKl4FBNUrpaR83qRDJ98Ii4gZpl5WNTFLSHVaBZOYyoKfMHp4s3QO85GzCV2beKdQ+3weIQ0TRNiSmGnxoNsY0eDZ5bY="
"notes": "hXJ4oRcR5NkaBxZLpbf0CpojFH/vuPCxHDz0PuhVUY+lqk8P6Wle8hHGvbELY/L4AQEBj3Rgkjis+a5zc0GLFmZjPwAQgC60MX8pYhiPXaB14ZCXiGIGJxvhTvPpeB8vpQKKHFBtPCg4sxokJ0nRunbo2Gk9gnsakzaKFB/0Ky7xGA4="
"notes": "lAWLfAEBAZL78Zu5GTi8y45Zd8YGeAun9axirlVCXKMFilM716xxXxAN6i38+h8OapfWKCEBkSu6lWows6ywtqfkfZssuPs8BKKYWhRXxI+PV7kZB2x9"

[elsirion]

I think this can be closed now with #3346 and #3347 merged.