Token Space Efficiency Enhancement

[lollerfirst]

I'd like to discuss an improvement that would enhance space efficiency in tokens.

From NUT-00, a token is composed like this:

{
  "token": [
    {
      "mint": str,
      "proofs": Array<Proof>
    },
    ...
  ],
  "unit": str <optional>,
  "memo": str <optional>
}

Where the bulk of it is in "proofs" which is a Array<Proof> and Proof:

{
  "amount": int, 
  "id": hex_str,
  "secret": str,
  "C": hex_str
}

I note that it is redundant to include a "C" for every proof. Instead -when generating a token- the wallet could sum up all the C of all the proofs the user intends to send: C_tot = C_0 + C_1 + ... + C_n Then we could have the token modified as follows:

{
  "token": [
    {
      "mint": str,
      "proofs": Array<Proof>
    },
    ...
  ],
  "C_tot": str <optional>,
  "unit": str <optional>,
  "memo": str <optional>
}

Where C_tot is the x-only hex representation of the previously discussed cumulative pubkey C_tot . And Proof modified as follows:

{
  "amount": int, 
  "id": hex_str,
  "secret": str
}

For the receiver of this new token, nothing changes: he will still send these proofs to the mint to have them molten or swapped.

The mint, however, would have to slightly adjust its way of verifying the proofs:

k_0 * hash_to_curve(x_0) + k_1 * hash_to_curve(x_1) + ... + k_n * hash_to_curve(x_n) == C_tot

where k_* are the keys for the respective amounts and denominations, and x_* are the secrets.

Thoughts?

[lollerfirst]

Just to keep this updated (even though it probably will never see the light of day).

As @conduition promptly pointed out, curve point additions weight in on the performance of the mint. So then I proposed instead of C_tot being the cumulative sum, let's have C_tot = Hash(C_0 || C_1 || ... || C_n) and it should work about the same.

[lollerfirst]

The main disadvantage of this hack is the inability to compose the DLEQ proofs the same way. That means it cannot be used offline.

[conduition]

I benchmarked a few different approaches to proof aggregation in Rust using libsecp256k1 bindings and the k256 crate, and curve point addition actually turned out to be only barely slower than hashing (a factor of 1.5x - 2.0x), regardless of how many proofs are being verified. Any claims we make about performance should always be done on a per-implementation basis, but I think in general point addition is a very cheap operation across most implementations so using that for the spec seems reasonable to me.

Point addition also has the advantage of being aggregatable: A client could receive, say, 10 tokens separately, and aggregate all ten C_tot values together in a single swap request to claim them. If the swap request fails, they can retry each individually to root out the invalid one. Hashes cannot be aggregated and so the receiver would always need 10 separate swap requests to claim all 10 tokens (or else we'd need to modify NUT-03 in an undesirable way to support it)

@lollerfirst is correct regarding offline verification. This seems like it should be a relatively simple thing for clients though: Proof aggregation or DLEQ, your tokens can use one but not the other.