Keyset ID V2 #182
No reviewers
Labels
No labels
breaking change
bug
documentation
enhancement
needs discussion
needs implementation
new nut
ready
wallet-only
No milestone
No project
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set.
Reference
forgejo-admin/nuts!182
Loading…
Add table
Add a link
Reference in a new issue
No description provided.
Delete branch "keyset-id-v2"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Summary
This PR introduces Keyset ID v2 (version byte
01) and updates the spec + vectors accordingly.The Keyset ID v2 derivation is designed to be unambiguous across keysets by hashing both the key amounts and keyset metadata.
Changes
Keyset ID v2 (NUT-02)
01(version byte) +SHA256(preimage)(32 bytes)ifield): first 8 bytes of the full keyset ID (hex string length 16)Derivation preimage (v2)
Preimage is constructed as UTF-8 bytes in this exact order:
"{amount}:{pubkey_hex}"amount:pubkey_hexpair with a comma (,)"|unit:{unit}"input_fee_ppkis present and non-zero, append"|input_fee_ppk:{input_fee_ppk}"input_fee_ppkis omitted /null/0, it MUST be omitted from the preimage.final_expiryis present and non-zero, append"|final_expiry:{final_expiry}"Then
id = "01" + sha256(preimage).hexdigest().Deterministic secrets (NUT-13)
00: legacy BIP32 derivation01: HMAC-SHA256 derivationmessage = b"Cashu_KDF_HMAC_SHA256" || keyset_id_bytes || counter_k_bytes || derivation_type_byteSpec/test-vector updates in this PR
tests/02-tests.mdV2 keyset IDs to match the new preimage rules (includinginput_fee_ppkbehavior).02.mdexamples to use fully specified vector keysets (no ellipses), so IDs are verifiable.tests/13-tests.mdV2 secrets/r vectors to match the updated V2 keyset ID.tools/regenerate_vectors.pyto regenerate/sanity-check the affected vectors.Implementation Status
@ -64,0 +74,4 @@An example implementation in Python:```pythonI am wondering ... since we already depend for CBOR (for Token v4), maybe we can use CBOR here too instead of this custom serialization?
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onWhat happens to the tokens when a mint generates a new keyset that collides with the already emitted tokens?
Let's say the old keyset id is
01cb2343...., the tokens use01cbin theifield and then a new keyset is created which has id01cb948.... The chance of this happening is 1:256 (around 0.4%) - if you generate more keysets, the chance is significantly higher.@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onI strongly agree. I think we should leave at least 7 bytes of id in the token, like before.
(e.g.
01cb2343d31f10ff)@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onWhat's the 95% case for how long it takes between a token being created and redeemed (i.e., the proofs in the token swapped)? I guess it's on the order of an hour, maybe longer if you're sending it to a new user who isn't active. What are the realistic odds that a keyset is created that also happens to collide with the same unit within that hour? That's why I thought this was acceptable.
On the other hand, given that this is still only a small reduction in token size, I'm fine with keeping the 7 bytes.
However, as I've stated before, I'm in favor of anything we can do to reduce the token size since it's a common issue. Maybe a compromise of 3 bytes instead of 7 bytes is worth it?
@ -64,0 +74,4 @@An example implementation in Python:```pythonWhat would the structure of the CBOR be?
Thank you!
Please:
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have on8 != 1 + 1
@ -58,3 +58,3 @@#### Keyset ID version#### Keyset ID V2Once optimization could be to changeb"unit:sat"->b"u:sat"or even justb"sat".(Edit: nevermind that, it will all be hashed in the end, so reducing the length of what's inside won't matter)
Might also be worth specifying the unit should be lowercased first.
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onOops. Thanks!
@ -58,3 +58,3 @@#### Keyset ID version#### Keyset ID V2I don't think we have specified the units as case-insensitive yet. We should probably also do that if we include this change, right?
@ -126,3 +170,3 @@},{"id": "0042ade98b2a370a","id": "012fbb01a4e200c76df911eeba3b8fe1831202914b24664f4bccbd25852a6708f8",What happens if a wallet that does not yet support V2 keysets makes a
GET v1/keys/{8-byte-keyset-id}request?@ -126,3 +170,3 @@},{"id": "0042ade98b2a370a","id": "012fbb01a4e200c76df911eeba3b8fe1831202914b24664f4bccbd25852a6708f8",A request with a keyset ID prefix
00should still be supported. A wallet that doesn't support keyset IDs with a prefix of01shouldn't get to where they are making this request since the keyset ID parsing will have already failed if the wallet is checking the version.If a wallet doesn't check the version and sends a request for an 8-byte keyset ID from a token, we can consider having the mint resolve it for the wallet from the URL. But that feels like an optional requirement for the mint.
Does that address your question?
@ -58,3 +58,3 @@#### Keyset ID version#### Keyset ID V2Since the keyset ID commits to the unit, then it would make sense IMO.
If a client derives the keyset ID using a different capitalization, or if the mint changes the capitalization later on, the keyset ID would be invalid.
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onThis seems too vague and leaves room for interpretation. It could simply say that the token must include the first 8 bytes / 16 hex characters of the keyset ID it originates from.
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onWe could make it more explicit and call it
s_idwhich isid_hex[:16]orid_bytes[:8].@ -58,3 +58,3 @@#### Keyset ID version#### Keyset ID V2@callebtc what do you think about units being case-insensitive and hashing the lowercase unit value?
Should we maybe add a paragraph to this that describes the way the Mint handles proofs with Short IDv2?
The Mint calculates each keyset's short IDv2 in addition to IDv2 and uses the short IDv2s for lookups in cases where it receives proofs with short IDv2.
Alternatively a substitution could be performed by the client, but this means that it has to request
v1/keysso it's an additional more request before a swap.Quite honest, I am not sure such small change justifies creating a new keyset version and the headache attached to it.
Maybe we should keep this improvement in mind and apply it together with some future proposal that changes something significant?
@prusnak this was suggested to enable wallets to store proofs without referencing mint URLs. @thesimplekid @ok300 do you think this is still necessary?
The longer keyset ids to reduce the chance of a collision and the keyset expiry are things we've talked about awhile and I would like to see, I think it makes sense to move forward with this. I cant think of anything else we wanted to include that we should hold this for, but if there is I am open to it.
@ -58,3 +58,3 @@#### Keyset ID version#### Keyset ID V2We should specify we hash the lower case.
I agree. This is exactly the kind of change I was mentioning when I said to "justify" creating a new keyset version.
A few NITs, otherwise it's an ACK from me:
The specified behavior is a bit ambiguous in 2 places.
This doesn't say if it's the long or short ID. It should probably say "short ID" or rename the variable to
s_idfor clarity.This makes it sound preferable, but optional to use the shorter
s_idin the proof, whereas the PR text indicates it's mandatory, since the Token size is kept unchanged.@davidcaseria I think it would be better if the long keyset ID was 32-bytes:
CDK draft: https://github.com/cashubtc/cdk/pull/702
Why?
@prusnak For simmetry w.r.t. V1 so that the length is still a power of 2. I think it's less confusing if we keep the same process and only change what is needed to be changed.
It is non-standard and does not bring any single benefit imo. Only headache.
IMO there is an ambiguity in the new spec:
This implies the
Proofs in aTokencould use either the short ID or the long ID.Is there any reason where the long ID makes sense?
If not, I'd suggest to change that
SHOULDto aMUST.The only reason I can think of is to avoid short ID collisions, but that's already covered by another section:
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onAs discussed, the ambiguity mentioned above ( https://github.com/cashubtc/nuts/pull/182#issuecomment-2773223419 ) is intentional and the spec should allow for both short and long Keyset IDs in the
Token.@davidcaseria I re-worded the paragraph that originally confused me. It now spells out in more detail who should use the
s_idwhen.@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onNIT: Duplicate line, it's already included in the last part of the paragraph on L27 above.
Good to merge?? Who's ACK-ing?
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have on@ -64,0 +65,4 @@```1 - sort public keys by their amount in ascending numerical order2 - concatenate each amount and its corresponding lowercase public key hex string (as "amount:publickey_hex") to a single byte array, separating each pair with a comma (",")3 - add the lowercase UTF8-encoded unit string prefixed with "|unit:" to the byte array (e.g. "|unit:sat")@ -20,0 +40,4 @@3. `secret = hmac_digest` and `blinding_factor = hmac_digest % N`.### Code ExamplesIf all do not do this seeds will not be transferable between implementations.
ACK
0f3cef68eacloses #229
Merged in cdk https://github.com/cashubtc/cdk/pull/702
@davidcaseria I think the safest option is to version the secret derivation (like we're doing with the keysets) and then specify that wallets should follow:
This way wallets have immediate way of knowing which derivation to use (or was used, in the case of restore) when generating secrets for a particular keyset, and we eliminate all "counter"-based issues.
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onChange to SHOULD
@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their eShouldn't these both be hmac_digest[:32] as the
derivation_type_bytenow creates different outputs based on derivation type?@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their eYes you're correct.
@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their e@davidcaseria
added test vectors: https://github.com/davidcaseria/nuts/pull/6
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have on@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have onImportant technical note:
You are using hmac-sha512 and then using only the first 256 bits of the result.
If hmac-sha256 is used, then you can use the whole result and sha256 is MUCH more friendly for 32-bit embedded devices such as hardware wallets or smartcards. Furthermore, often these devices contain accelerators for sha256 but not for sha512.
I suggest changing hmac-sha512 to hmac-sha256 for this reason
@ -64,0 +63,4 @@Keyset IDs are derived from public data. To derive the keyset ID of a keyset, execute the following steps:```1 - sort public keys by their amount in ascending numerical ordercan we add delimiters here?
they won't change the size of the result and make it so much better for debugging implementations
example
@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their elet's make it obvious this is a binary zero or one and not ascii zero or one:
Suggesting minor changes.
Updated KDF with hmac_digest_secret and hmac_digest_blinding_factor.
@ -14,9 +14,9 @@ A mint can have multiple keysets at the same time. For example, it could have on@ -64,0 +63,4 @@Keyset IDs are derived from public data. To derive the keyset ID of a keyset, execute the following steps:```1 - sort public keys by their amount in ascending numerical order@ -82,0 +112,4 @@> [!CRITICAL]> Wallet implementations should reject any attempt at importing new keysets which IDs> collide with any of the previously added keysets.why are we calling this
final?@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their e@ -14,3 +14,3 @@The wallet generates a `private_key` derived from a 12-word [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) `mnemonic` seed phrase that the user stores in a secure place. The wallet uses the `private_key`, to derive deterministic values for the `secret` and the blinding factors `r` for every new ecash token that it generates.The wallet generates a `seed` derived from a 12-word [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) `mnemonic` seed phrase that the user stores in a secure place. The wallet uses the `seed`, to derive deterministic values for the `secret` and the blinding factors `r` for every new ecash token that it generates.When I first wrote this what I imagined could happen is at some point we'll want other expiry fields (for example
active_expiryto signal when this keyset is expected to be made inactive).final_expiryis stronger and signals a potential deletion from the DB.This might be a good reason to change to SHA-256.
@ -14,3 +14,3 @@The wallet generates a `private_key` derived from a 12-word [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) `mnemonic` seed phrase that the user stores in a secure place. The wallet uses the `private_key`, to derive deterministic values for the `secret` and the blinding factors `r` for every new ecash token that it generates.The wallet generates a `seed` derived from a 12-word [BIP39](https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki) `mnemonic` seed phrase that the user stores in a secure place. The wallet uses the `seed`, to derive deterministic values for the `secret` and the blinding factors `r` for every new ecash token that it generates.I think this suggestion was nacked in previous conversations.
@davidcaseria https://github.com/davidcaseria/nuts/pull/8
I believe final_expiry should be included in GetKeysResponse. Without it, the user cannot derive the keyset ID directly from this response and is forced to make an additional API call to fetch the keysets.
https://github.com/davidcaseria/nuts/pull/9
Further to @d4rp4t comment, the '/v1/keys' endpoint should ideally return ALL keyset fields for the active or selected keyset... this allows a consumer to call just ONE endpoint and get the full keyset data - fees, expiry, keys etc etc
That way, the '/v1/keysets' endpoint can just be called when historic or inactive keyset data is required
I think this is out of scope for this PR.
Nevertheless: wallets should hit
/keysetsfor metadata, and/keysfor the actual keys.@ -64,0 +63,4 @@Keyset IDs are derived from public data. To derive the keyset ID of a keyset, execute the following steps:```1 - sort public keys by their amount in ascending numerical orderthis should be conditional on whether
final_expiryis set.@ -64,0 +63,4 @@Keyset IDs are derived from public data. To derive the keyset ID of a keyset, execute the following steps:```1 - sort public keys by their amount in ascending numerical orderCommit #
b25abaachanged the keyset ID calculation to include a separator but test vectors and implementations didn't. Needs to be resolved.Commit #
b25abaachanged the keyset ID calculation to include a separator but test vectors and implementations didn't. Needs to be resovled.I propose two mutually exclusive courses of action for resolving #
b25abaaID calculation:Course of action 2 also requires changes across all implementations and test vectors.
This makes sense to me.
I prefer option 2.
If this has been already implemented in CDK or other implementations, I can live with 1. But we should know better and not push discussed drafts into production before they are accepted.
Fair point - was just that adding
final_expiryto keys in this PR reminded me of it.I've raised a seperate issue for consideration: #289
agreed
having two different separators is ugly and we're only going to hash the result anyway.
I'd also vote for 1 in favor of dropping all separators (
,and|).I'm also favorable to 1.
@ -12,11 +12,207 @@ In this document, we describe the process that allows wallets to recover their eredundant comments?
https://github.com/davidcaseria/nuts/pull/11
ACK
1efb5a4b50Update: this comment is now OUTDATED. See @callebtc below
Could we add anactive_at_least_untilfield in active keysets?As the SIG_ALL message change (https://github.com/cashubtc/nuts/pull/302) commits the outputs to a particular keyset, and holders of (partially-) signed transactions might want to be able to hold the transactions for a longer time, they would like some confidence that anactivekeyset in their output will remainactiveOne example of this is the Cashu Channel, where - like in Lightning - you want users to keep their transactions away from mint until their are ready to close the channel.Update: SIG_ALL does not contain the keyset ID anymore, I think we can mark this comment as outdated.
ACK
github.com/cashubtc/nuts@1efb5a4b50ACK https://github.com/cashubtc/nuts/pull/182/commits/9f5a7471523f04e2deab8d3f0a535dc60e3f26cd
ACK
9f5a747152@ -102,12 +323,14 @@ If the wallet used the restore endpoint [NUT-09][09] for regenerating the `Proof### Restoring batchesSeems unnecessary to try both methods, assuming that we transition to the new KDF only for V2 keysets
ACK
97b957304cJust flagging one area of concern.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumThe keyset ID derivation doesn't protect/guarantee the amounts have not been tampered with, only that the amounts are still ordered the same.
What stops a mint from changing the amounts bound to each key to devalue and "inflate" away their liabilities?
eg: 1, 2, 4, 8, 16, 32, 64
could become: 1, 2, 3, 4, 8, 16, 32
or maybe even: 1, 1, 1, 1, 1, 1, 1
Perhaps we should concat all the amounts in order too... or maybe just adding the sum of key amounts would be enough to reduce the risk of serious damage?
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumThis is a really good point. It would change the derivation algorithm and all test vectors etc.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumNot sure what is the state of implementation and mainly usage of Keyset ID v2, but I think it is worth the change if the usage is non-existent or minimal.
If we will be changing this, I would suggest to include my suggestion which was dismissed earlier: https://github.com/cashubtc/nuts/pull/182#discussion_r2306837257
Re: Derivation and invalid results (k > N or k == 0)
Usually you would
k % Nto get the value into range, but because of limitations of some implementations this is not possible. BIP-32 definesI think this should be our default for all derivations too. It requires implementations to bubble up that error to the application layer to properly increment counters (e.g. counter 2 is requested, but produces an invalid result, so counter 3 will be consumed), but that is a sound way to handle this edge case
In an ideal world, we would reduce mod N, which then reduces the failure to
r = 0only, a 1 in 2^256 event equivalent to guessing a private key.But if we cannot do this reliably in all implementations, it may be "prudent" to throw for values > N, specifically in the case of SHA256 digests, as it removes the miniscule risk of some implementations not being able to derive blinding factors for certain hashes... which Murphy's law says will be the most expensive mistake possible.
Maybe that's why BIP32 specified as discard and retry, not reduce %N.
Really wish mod n wasn't an issue, the single subtract is so elegant.
Cross referencing the NUT-00 conventions PR, which currently warns against doing MOD N. https://github.com/cashubtc/nuts/pull/322
Will need to update this if we proceed with the the proposed blinding scheme here.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sum@callebtc @prusnak @robwoodgate https://github.com/a1denvalu3/nutshell/pull/6/changes
I have a sub-branch of my Nutshell IDv2 implementation with the modified derivation scheme and adjusted test vectors IF we want to go ahead with this.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumAnd maybe include the feerate
input_fee_ppkin the id too?In the mint changes the feerate, that might break some pre-signed transactions, and therefore I'd like to discourage changing of feerates.
If a pre-signed swap spends from a keyset, and the mint changes the
input_fee_ppkof that keyset before the swap is executed, the swap might fail because it won't have enough inputs to cover the outputsIf the mint wants to change the feerate, they could de-activate the keyset and create a new keyset with the new feerate
This implies that, if a keyset has no final expiry, then the response must include
final_expiry: null. But I guess we want to make that optional? i.e. wallets won't expect thefinal_expiryfield to be presentCan we make that explicit somewhere here? i.e. The mint may omit
input_fee_ppkif the fee is 0, ormaybemay omit thefinal_expiryif there is no expiryHow about including one v1 keyset in this example response, if only to remind wallet authors that mints are likely to include both v1 and v2 keysets?
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumA bit pedantic, but as the amounts from
/v1/keysare strings, not numbers, we should be clear about the order:@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumyes! we need to add separators if we append the amounts as well, let's combine both changes
that's how we usually indicate that a value is optional through the spec.
is it an equivalent "json" to omit a key if the value is
null? i.e.{a: 1, b: null} == {a: 1}?I think it's fine, since we're deprecating v1 with this.
I think all points should be addressed now.
@callebtc - the changes are looking great. I think we are there!
Just one housekeeping comment - should
verify_02.pybe placed under tools instead of in the root folder?@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumThis would be a deviation from current spec as mints currently are allowed to change fee of a past keysets. Though I'm not sure if nutshell allows it, cdk doesn't it rotates to a new keyset as you suggested but that was an implementation choice not a spec requirement.
I think there are arguments for and against allowing mints to change keyset fees that are unrelated to the id.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumFYI. Calle's latest iteration has fee baked in.
should we add a couple test vectors for the preimage?
ACK @
6e785b2524Epic work, I think this is a much stronger spec now.
@ -64,3 +93,4 @@V1 keysets are 8 bytes long, including a version byte prefix `00`.```1 - sort public keys by their amount in ascending orderLooking at this code it occurred to me, that this works fine only if there are no duplicate entries in key values of
keys. And this seems to be the case sincekeysis expected to be a dict. (otherwise thekeyswould need to be a list of tuples instead of a dict).However, does the keyset spec disallow multiple public keys with the same denomination? I don't think we should allow this, but in that case, we should add this limitation to the keyset spec. Or is such limitation already in the keyset spec?
I think it's worth noting that including the fee in the ID now means that mints cannot change the fee of past keysets. This to some extent reduces the mint's ability to dynamically change fees in response to a DoS, for example, as the first operation will still have the lower fee, only the second operation will incur the higher fee of the new keyset. I am not necessarily against this change; I just think we should be aware of it and make sure we are making this tradeoff intentionally.
@ -56,11 +56,41 @@ Notice that since transactions can spend inputs from different keysets, the sumWe should explicitly mention that these keys must be lowercase because SHA-256 is case-sensitive, while hex is not.