The goal of this post is to propose a key hierarchy to organise the keys used by RM [1]. Note that this post doesn’t introduce new keys, but only explicitly lists all existing and assumed keys and suggests a standard and secure way to derive them.
Overview
The keys assumed by the RM design can be grouped into 3 categories:
Identity & ownership keys. This group includes identity keys and nullifier keys.
Resource encryption keys. This group includes all keys relevant to resource object encryption
Discovery keys. This group includes all keys relevant to discovery plaintext encryption [2]
Proposed structure
Name
Derivation
Description
Lifetime
Identity key pair (idsk, idpk)
idsk \xleftarrow{R} \mathbb{F}_p, idpk = [idsk] * G
This static key pair serves as the user’s identity. It is used to authorise actions and other keys. It can be represented by a Metamask identity keypair.
sdsk \xleftarrow{R} \mathbb{F}_p, sdpk = [sdsk] * G
This static key pair is used to produce discovery encryption keys
Forever, but should be periodically rotated for forward secrecy
User key uk
uk = (cnk, sepk, sdpk, S), where S = Sign(idsk, (cnk, sdpk, sepk))
User key contains the public nullifier, static encryption, and static discovery keys. Identity secret key is used to sign $cnk, sepk, and sdpk. The key is stored in a map with a key idpk that identifies the user.
Determined by rotation period of cnk, sepk, and sdpk.
Ephemeral encryption key pair (eesk, eepk)
eesk \xleftarrow{R} \mathbb{F}_p, eepk = [eesk]*P
Ephemeral encryption key pair generated by the sender. Used to derive the resource encryption key
Resource symmetric encryption key. Used to encrypt the transmitted resource object
Transaction
Ephemeral discovery key pair (edsk, edpk)
edsk \xleftarrow{R} \mathbb{F}_p, edpk = [edsk]*P
Ephemeral discovery key pair generated by the sender. Used to derive the discovery encryption key
Transaction
Discovery encryption key dek
dek = KDF(DH(sdpk, edsk), edpk)= KDF(DH(sdsk, edpk), edpk)
Discovery symmetric encryption key. Used to encrypt the discovery message
Transaction
The static keys are derived independently and signed by the identity key
The user key, that contains all the public static keys, is assumed to be stored in a lookup table that maps identity public keys to the user key. With the receiver’s user key, the sender can create a resource, encrypt the resource object and the discovery payload for the receiver.
We don’t have to ask for so much randomness when initially generating the keys. We can get some randomness and then use PRF to derive all the keys by changing the domain separator.
The total size of the keys communicated to potential receivers is ~ 33 * 4 (keys) + 64 (signature) = 196 bytes. We generate all static key pairs independently for proper domain separation, which means we can’t derive one from the other. If that is absolutely unacceptable, we can reduce the size by introducing dependency. It will affect security and might additionally break the nice ability to use Metamask keys.
How to send, discover, and receive a resource
Alice knows Bob’s identity idpk_{B} and wants to send him a resource r. To do that, Alice:
Looks up Bob’s user key uk_{B} or uses the user key that she already knows. [5]
Alice sets r.cnk = uk_{B}.cnk
Alice generates an ephemeral encryption key pair (eesk_{A}, eepk_{A})
Alice generates the resource encryption key rek_{AB} = KDF(DH(sepk_{B}, eesk_{A}), eepk_{A}).
Alice encrypts the resource ce = Encrypt(rek_{AB}, r). resourcePayload = [ce, eepk_{A}]
Alice generates an ephemeral discovery key pair (edsk_{A}, edpk_{A})
Alice generates the discovery encryption key dek_{AB} = KDF(DH(sdpk_{B}, edsk_{A}), edpk_{A}).
Alice encrypts the discovery payload cd = Encrypt(dek_{AB}, discoveryMessage). discoveryPayload = [cd, edpk_{A}]
The indexer discovers the transaction by (given sdsk_{B}):
Computing the discovery encryption key dek_{AB} = KDF(DH(edpk_{A}, sdsk_{B}), edpk_{A})
It isn’t an asymmetric key pair, but a pair of keys related to nullifiers. Maybe I shouldn’t call it that. ↩︎
We have agreed to use the same mechanism for discovery encryption as for resource encryption, therefore the key sets are derived exactly the same. ↩︎
The rotation period can be determined by the user. It is a trade-off between the forward secrecy guarantees and convenience. The user also can store their old keys after rotation for a while to be able to decrypt incoming messages. We can also assume the user never rotates their keys for now, but the design allows the rotation. ↩︎
I might have further questions later, just wanted to leave a comment on this (implied) product requirement inquiry:
I think that this is probably acceptable, at least for now, for two reasons:
If users are copying an address anyways (should we want to communicate the keys in that format), they’re copying a string anyways, and the length doesn’t matter too much.
We will likely use lookup tables of various forms, such as the identity → user key lookup table that you specifically mention, and maybe other kinds of namesystems in the future.
On a separate note - I believe I’ve stumbled over an inconsistency in the notation while trying to build the Alice and Bob flow:
Uses the edpk_A as the context for the KDF.
Uses the eepk_A as the context for the KDF.
As everyone here knows, I’m not a cryptographer, so let me know if I’m getting this wrong here. However, if I do replace the indexer KDF context with edpk_A, the flow works.
Maybe it could be a silly question, but I’m trying to understand how the indexer would have access to sdsk_B. In which moment Bob would need to provide it?
Hey Pedro, excellent question! I believe we should create a mapping on the Transaction Service / Local Domain between idpk and sdsk for each user once the user signs up. A bit more on that can be found here.
The comment you quoted is only relevant for the case when we do not want to keep independency of keys, which is not the case, judging from the next comment. If we keep the keys independent (as in the current version of the proposal), the Metamask key pair takes the role of the identity key pair and is used to:
authorise other key pairs when they change
sign whatever data needs to be authorised
That seems to be exactly how Metamask keys are used (although that I’m not an expert in) and how we were planning to use them
As mentioned earlier on Slack, I wanted to bring this specific user flow to your attention.
I believe the main novelty here is that we take the identity key (either from a Passkey or an existing wallet), sign over some message (has to be deterministic, e.g. ‘anoma’), and then take that deterministic signature to create the three static keypairs.
Why would we want this? The deterministic nature of this signature has the awesome benefit of being able to recreate the static keypairs instead of storing them. When the user logs in, they simply need to sign the same message and the web app takes the signature to generate the keys. This obviously requires determinism in the signing mechanisms and from our tests so far, this should be given for Passkeys AND most, perhaps even all, existing wallets (@kike has accompanied the tests on the theoretical side and already looked at the feasibility of the mechanism).
I would like to make sure that this is okay for the MVP and that we don’t oversee any obvious cryptographic blunders here @vveiln. I’d much appreciate your confirmation that this is in accordance with the proposal (module key rotation I guess).
Everything looks good to me. The table is precise, and example steps seem sound.
My main feedback is that it’d be cleaner, and algorithms easy-to-replace in the future, if we describe everything in terms of cryptographic building blocks. As of now we have a mixture with underlying math.
Can the identity keypair be for any for signature scheme? Or do we need to stick to group-based schemes?
The derivation of the symmetric keys is done with the ElGamal-KEM. Can we use any other KEM?[1]
My advise is that whenever possible we switch to post-quantum cryptography. Specially for keying material intended to persist long, such as the identity keypair (idsk,idpk). For the KEMs, perhaps we can’t do it for encryption (due to SNARK circuit constraints) but it may be possible for the discovery keys (?)
Perhaps this is not the goal of this post, in which case we can ignore what I said above and postpone the discussion.
I get the intuition. Just to confirm, is nk used as the PRF seed? And if so, what would be the input to the PRF, a constant value?
Hope it helps!
A nice effect of describing key-hierarchy with KEMs is simplicity: we get rid of the ephemeral keys, only need to use the encap/decap algorithms. ↩︎
Regarding why would be secure using the signature as entropy to derive more keys. The intuition is that if someone can predict the signature on the message without explicitly signing it with your (private) signing key, it would have forged the signature. This constitutes an attack against the EUF-CMA security property of the signature scheme.
I tested empirically that signing in Metamask is deterministic using the etherscan ‘Sign Message’ functionality (can provide more details on the steps, but they are not too complicated).
The current implementation in the arm complies with the descriptions. I just want to confirm a minor detail about symmetric key derivation. Is there a specific reason to include the extra eepk in the KDF when eesk or eepk is already part of the DH and contains the eeps information? The eepk is around 65 bytes and would add two more hashes to the KDF, assuming we use a hash for the KDF.
We are using multiple PRF or KDF functions. Should we add a few bytes as PERSONALIZATION to differentiate them? This way, for example, even with the same public and secret keys in discovery and encryption KDFs, different symmetric keys would be generated. This might be a practical security consideration for implementation.
I’m not sure I like this. It creates a dependency between the identity key and all other keys, which is something I explicitly tried to avoid with this design. If the identity secret key is leaked, all keypairs are compromised since they are deterministically derived from the identity secret key.
Also, even if the attacker is not able to predict the signature, but the signature somehow leaked, it is still enough to derive all keys (except the identity keypair, at least).
If we store the keys and only the identity secret key is leaked, the other keys are not at all affected
I understand this concern. However, my personal take is that if we’re using the keypair of an existing wallet (e.g. MetaMask) as the identity keypair (which I guess is the current plan), leaking the identity secret key would be equivalent to losing full control over the existing wallet anyways. This is a problem that wallets have been dealing with for a long time and you frequently hear about phishing et al attacks. I believe it’s a fair trade-off for the much improved UX and something that users already have to be aware of, so no security overhead either.
I’m not sure how troublesome it would be to leak the signature, i.e. leaking the three keys. Definitely not great but I would argue that the attack surface for leaking the keypairs is larger when we involve different storage layers compared to treating one signature as most precious.
I think the fact that we have privacy as an important principle for Anoma turns into a big deal compromising all of the keys so easily. If this is not very important, we shouldn’t need them in the first place.
Ex: If we deterministically generate all the keys based on a signed message, and the user is scammed by a phishing attack asking to sign the original message, all keys are compromised.
Do I understand correctly that AnomaPay is not only intended to be a payment app but also a wallet app? Because the key hierarchy is not intended to be per app, and if the application defines how the keys are generated, essentially defining key hierarchy, it should be explicit.
The assumption about MetaMask also only holds when we assume that all identities are backed by MetaMask keys, i.e. there is no Anoma native identity generation mechanism.
Why would we have different storage layers and not treating a bundle of private keys as most preious?
I don’t think so. AnomaPay is meant to be a technical demonstration of our ability to execute shielded transfers. What I’ve referred to as ‘embedded anoma wallet’ in previous posts is first and foremost a component which enables the shielded transfers demonstration. We have not (to the best of my knowledge) made any decisions about whether or not we separate the transfer application from the wallet or treat them as application-specific. From a technical perspective, I do not see a reason why the ‘embedded anoma wallet’ couldn’t become some importable widget shared between applications. I wouldn’t say this equates to a standalone product though.
I guess this is in line with my above statement if I understand correctly.
What I meant here is that we need to store the encrypted “key bundle” somewhere. Whether this would be on a blockchain, some local storage, or on a piece of paper. Some people might not use MetaMask, so relying on their decryption API is a bit inflexible (I guess we have already agreed on that). I view the regeneration of the 3 keys based on the already secure identity keypair (assuming it’s the MetaMask [or any other wallets’] keypair already being used with the MetaMask wallet) as cleaner as it concentrates the attack surface on the already secure identity keypair.
this is an amazing proposal and find it very interesting , but my question is how would this scale when resource data becomes huge/highly frequent like in the case of perps?
for a future dev that would be building their apps (new/existing) on Anoma, will tgey need to directly handle this key hierarchy, or will it be abstracted at the sdk layer?
Either way, as a part of building the AnomaPay application, we are implicitly building the key handling mechanism, which doesn’t explicitly belong to the application.
So the argument to not store keys is that not everyone uses MetaMask, but the argument to base our system on the identity keys is that the users will use MetaMask wallet? If users don’t use MetaMask, they do not have decrypt functionality and they also do not get secure storage for their identity keys.
Now a bit more about pros and cons of the proposed change. Pros:
if we rely on an existing wallet for the identity key pair security, we don’t need to store anything else to recover the static keys
Cons:
if the user doesn’t use an existing wallet, we still have to provide the security for the identity key pair. It is cool to focus on the short-term plan, but if we are also assuming that we might extract the wallet mechanism from AnomaPay, that means that the short-term plan will become the long-term plan and the standard for all applications. So we will have to think about identity keypair security on our side at some point.
we bind the lifetime of the static keys to the lifetime of the identity keys (forever). It means, key rotation is not possible, so there is no forward secrecy. It means, if static keys get leaked, the attacker gets access to the whole communication history. The original proposal allows rotating keys without rotating the identity keypair, which, in case the current static key gets leaked, reduces the damage to the lifetime of the current key
since all keys are generated deterministically from the identity key, leaking the identity key means leaking ALL keys and there is no recovery mechanism. All security is based on a single key pair security. With the original proposal, even if the identity key gets leaked, we still can have some recovery properties since the static keys are generated independently. For example, if a user has established communication with the attacked user in the past using the static keys that are still valid and is confident it was the “original” user, they can use these keys to communicate even though the identity key is leaked. Some sort of emergency protocol can happen (e.g., the attacked user can communicate their new identity key to the user). It isn’t extremely reliable and is based on the assumption the party is confident that the prior communication was authentic, but it is much better than having the identity leaked forever without any recovery option
if we want to introduce dependency, I believe we can do it in a way that doesn’t require having a key lookup table, so that the sender can just generate other static public keys from the public identity key. So the security is bad (as described above), but we have extra benefits - we don’t need to communicate public keys. That was my initial idea, but I dropped it due to the security considerations. So from where I stand, by introducing this change, we get minimal benefits at maximal costs.
Thanks for articulating the concerns and pros/cons!
I cannot follow your points here. Yes, not every user uses MetaMask wallet but we do not require anyone to specifically use MetaMask wallet. We’ve tested multiple wallets, e.g. Phantom wallet (widely adopted), and even Passkeys from the Icloud Keychain, and they all generate deterministic signatures, meaning we are not limited to MetaMask wallet.
Yes, if users do not use MetaMask wallet they do not have the decrypt functionality (but I don’t see why the user would still need this functionality). However, they do get secure storage of their identity keys. This is the whole point of wallets, that’s their job, keeping the keys secure. I’m not sure where the notion comes from that existing wallets are failing to keep keys secure. If this would be the case, the entire web3 ecosystem would be in a dire situation. Perhaps I’m misunderstanding something here?
I do agree with the key rotation con but I personally think it’s a worthwhile tradeoff. We are not making decisions about long-term standards here, we’re architecting a technical demo of shielded transfers.
I think we’d better be clear about what decision we’re trying to make here. I don’t think we should try to make a final long or even mid-term decision about key hierarchies yet, for reasons beyond these specific questions – e.g. we’ll probably want a different, more sophisticated shielded sync mechanism in the future. The most urgent decision we need to make is what to do for the AnomaPay demo and Anoma Galileo (what key hierarchy we expect developers of RM apps which run on the EVM PA to use). The AnomaPay demo may use only a subset of the key hierarchy we support for Galileo overall, but it shouldn’t require something completely different.
Before we debate what specific mechanism to use, we should be clear on what the product requirements are. In previous discussions in which I participated, my understanding of the product requirements was that the user needed to be able to use Metamask or another wallet with decrypt functionality. My understanding from reading this thread is that this product requirement has changed, and we now want to support any wallet which can produce signatures (without requiring decrypt functionality), and we do not want to require that the user back up any keys (so the flow should just be “sign in with Metamask/[wallet]”, sign the message, derive keys [somehow]). @maurice Is that accurate?
From my perspective
I think a product requirement that users can “sign in” with any wallet that can produce a signature, and that they don’t need to backup any keys, seems totally reasonable – sounds like a simple UX. Of course, more sophisticated users may be willing to backup keys in return for improved security properties, and we should support this too (not necessarily with AnomaPay, but in the overall key hierarchy design).
I think exactly what keys we derive and how should be evaluated on the basis of cryptographic security, within the constraints of the product requirements. For example, we could probably obtain a form of key rotation by signing over different messages (and thus deriving different keys). Maybe we want to derive just an identity key from the signature, generate other keys independently, and encrypt them to that derived identity (public) key. Generating keys which would need to be backed up somewhere, but where the user can always decrypt them with a key derived from their signature seems compliant with the above product requirement (it’s not really different than decrypting some resources, just part of state sync). etc.
, but my question is how would this scale when resource data becomes huge/highly frequent like in the case of perps?