make the commitment hash input extensible

[daira]

There are some proposed features (#344, #608, #716, #718, #782, #794, #829, #830) that might involve adding new fields to the input to a note commitment.

Due to the fix to #738, the commitment is now a full SHA-256 hash, with a lead byte in the input that allows us to change its format if necessary. The only other thing required is that note holders use a more extensible data structure, perhaps one that includes an opaque byte sequence for any extra fields, to store note values. Then, the inputs to the circuit for old and new notes would be the encoded coins rather than the raw fields. (To ensure domain separation with other hash uses, the lead byte should not be arbitrary; we'd have to consider that carefully.) Also the output note plaintext would include the same extension fields as the note commitment input.

The circuit requires specifying the maximum number of SHA-256 input blocks, but does not necessarily need to change otherwise to accommodate a change in the commitment format (provided that the existing fields a_pk, v, ρ, and r stay in the same places). In the current two input blocks, 97 out of 127 bytes are used, so 30 bytes are available before needing to increase the number of blocks. [Edit: see below for updated numbers.]

To do: consider specific potential features, and how much this would help to minimise or eliminate future circuit changes and other compatibility headaches associated with them.

[daira]

I wrote:

In the current two input blocks, 97 out of 127 bytes are used, so 30 bytes are available before needing to increase the number of blocks.

I was mistaken about the number of bytes available; it is 119, due to the 64-bit length field in the SHA-256 padding. Also the number of bytes used has increased to 1+8+32+32+32 = 105, due to r being increased from 192 to 256 bits. So there are now 14 bytes (112 bits) spare. This isn't enough for another secure cryptovalue, but it is enough for an epoch number or timestamp, say.

[daira]

To be clear, the proposal is to make it possible for an upgraded sender to be able to send a new kind of note without necessarily knowing in advance that the recipient's wallet has been upgraded to take into account the new field(s). This might have risks for the recipient, so we'd have to define the recipient's checking of the commitment lead byte to ensure that it rejects or at least warns about notes that it might not be able to spend, if that is the case for a given extension.

[daira]

Since the note plaintext size is fixed, for indistinguishability it would be necessary to increase it by the size of the extension field, i.e. 14 bytes.

[daira]

14 bytes would be enough for #344, #718, #829, and #830 (possibly in combination), but probably not for #608, #716, or #782. #794 is too speculative to tell.

[daira]

In future, one of the reserved bits in the lead byte could indicate whether this is a two-block or three-block commitment hash. That would allow us to maintain validity of two-block notes after a hard fork to support three blocks (and increase the note plaintext size), with no partitioning of the note anonymity set.

I know we're past the spec freeze deadline, but I am increasingly convinced that we should include the 14-byte reserved field in 1.0.

[zookozcash]

What would an implementation of Zcash-protocol-2.0 (the current protocol) do when it receives a note with unexpected (non-0) bits in that 14-byte reserved space? The options seem to be (a) reject that note as not acceptable to it, (b) accept that note. If (a) then that's what we already have, without changing the spec or implementation at this time, right? If (b) then, per #790 (comment), the receiving program would be taking the risk that the sender is tricking the receiver's human into thinking she got paid when in fact she didn't.

[daira]

a) is not quite what we already have, because the note plaintext wouldn't have room for the new fields. It would be possible to maintain indistinguishability by taking that space from the memo field, though.

However, what I'd intended was a variation of b) in which the recipient uses the lead byte to decide whether it is at risk of not being able to spend the note. If it doesn't recognise the lead byte, then it warns the user or ignores the note (I hadn't decided which). That way we'd have a lot of flexibility in designing an extension as to how existing clients would respond to it.

[daira]

Here's how the potential extensions listed above would behave for a ZCP 2.0 client seeing an extended note:

#344: the desired functionality inherently means that the recipient can't spend the note before a given point.

#716 and #718: the recipient would have to have opted in by creating an address that is revocable or will expire, so they can be expected to have wallet support for the extension.

#829: after the design change to support epochs, all notes would have an expiration point. I would expect this change to have been debated well in advance, and it's not dependent on the particular note that is received.

#830: a non-ZEC note can't be spent by a wallet that doesn't support coloured notes. I think people would not expect otherwise.

#608: too general to tell.

#782: the recipient would need to have opted in by creating a private multisig address, so they can be expected to have wallet support for the extension.

[daira]

https://github.com/zcash/zips/commits/790.extensible-commitment.0
(specifically zcash/zips@12e43aa )

[daira]

The above branch takes a much simpler approach: it just extends the lead byte of a note plaintext to 14 zero bytes, as well as adding 14 zero bytes to the commitment input. This sidesteps any issue about what current clients should do, but still allows us to relax the handling of this field easily.

[nathan-at-least]

Brainstorming potential upgrades (given this extension) which do not require circuit changes: one thought is if this field signals some interpretation of the memo field. (It seems a simpler form of future proofing for that case is to just have a version prefix in the memo field starting at 0.)

[daira]

@nathan-at-least We already effectively have a prefix in the memo field: the spec says that if the first byte is >= 0xF5 (i.e. not a valid UTF-8 lead byte), then the memo is not displayed to the user and is some new format.

Edit: however, the memo field is not currently committed to by the note commitment.

[daira]

In the engineering meeting, @ebfull suggested that rather than reserving the 14 bytes in the note plaintext now, we could increase the size of the plaintexts later, on the basis that a circuit change would require a new transaction version in any case.

That's a fairly compelling argument given that all of the extensions mentioned above require circuit changes. The counterargument that the extensibility isn't necessarily limited to features that require circuit changes, is fairly weak.

[daira]

On the other hand, the cost of reserving the field in the plaintexts now is only 26 bytes per JoinSplit. Personally I think that's worth it to reduce future complexity. @zookozcash, what's your opinion?

[daira]

I've concluded that we don't need any spec change now for the commitment hash. We will be able to extend it later (either for specific changes or to make it more extensible) with a hard fork.

[daira]

This is not included in Sapling.

[str4d]

This is being done to Sinsemilla as part of ZSAs (zcash/zips#618).