Recovery Secret Seed

[nathan-at-least]

This feature allows a 'recovery secret seed' with these features:

• the seed is relatively small (eg less than a few kb).
• users can export a seed from a wallet.
• the seed can be imported into a wallet.
• any funds spent or received and all memo's received are available in the importing wallet, even if one or more wallets have been sending and receiving funds in the interim between export/import of the seed.

Questions:

• should the seed be per-address, or all addresses in a wallet?

Implementation:

• This would require deterministic generation of all necessary secrets from a seed.
• Deterministic secrets derivation may be more vulnerable to state rollbacks where reusing derived secrets leads to compromises, so we need to be vigilant against that.

[tromer]

It's desirable for the recovery seed to also provide full selective-disclosure functionality for interim transactions.

[nathan-at-least]

@daira suggests a way to enable users to have forward secrecy by rotating their backup secrets:

Forward secrecy doesn't preclude deterministic wallets, but it does preclude "flat" derivation schemes (i.e. schemes in which all keys are derived directly from a single generator key), and it requires that the generator key evolve over time. (So, any backup of the phrase representation should be regularly updated over time, and earlier copies destroyed.) Regularly creating new wallets manually is not a good implementation of this; it should be automatic and routine.

@daira, would it be accurate to say that feature could be built on a layer above a 'stateless / static derivation seed' scheme described in this ticket?

[tromer]

Forward unspendability and forward transaction confidentiality (as defined by @daira in #18 (comment)) seem at odds with reusable long-term addresses.

If I receive a payment to my long-term public payment address, I should be able to decipher and spend it, no matter how many times the generator seed has been rotated in the meanwhile. Naively, this means I can also decipher and spend old transactions sent to that address, so both of the above properties are violated.

The closest thing I can think of, which doesn't break long-term addresses, is:

• At every rotation of the generator seed:
  1. Transfer all extant balances to new addresses generated from the new seed.
  2. For each "legacy" address (one that's derived from an old generator seed), take its secret key and derive a punctured secret key that can decrypt any ciphertext except the ones already received. This requires a puncturable encryption scheme (a la @matthewdgreen and @imichaelmiers, http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=7163033).
  3. Keep and back up the punctured secret keys, and the new generator seed. Destroy the old generator seed, and the legacy secret keys from before the (latest) puncturing.
• Whenever receiving a payment to a legacy address for which you have just the punctured key, transfer the funds immediately to an address derived from the current generator seed.

Problems:

1. Requires changing the encryption scheme to a puncturable one.
2. The backup size grows with the number of legacy addresses (because we keep each punctured key separately), and moreover with the number of transactions sent to legacy addresses (because in the aforementioned puncturable encryption scheme, the secret key's size grows linearly with the number of punctured ciphertexts; this seems inherent, by a compressibility argument).
3. Forward unspendability is imperfect, because whenever new funds are sent to the address, there's a window window of opportunity when they can be stolen by someone in possession of an old (hence unpunctured) generator seed.

[daira]

I think forward unspendability and transaction confidentiality are compatible with long-term addresses if you change the encryption scheme to a time-based forward-secure one. That is, the sender of a transaction derives a public key for the current epoch from the long-term address, and the recipient derives a corresponding private key using a one-way function. I believe there are proposals for suitable forward-secure schemes using pairings, e.g. Canetti et al's scheme, and probably more efficient ones since then [edit: such as Lu and Li's scheme].

[daira]

If you link the time periods to block chain height, then you can absolutely prevent the problem of encryptions with old keys that puncturable encryption is trying to address, because it's possible for the zk-SNARK circuit to enforce that the ciphertext has been encrypted to the correct period (this is essentially the same as #718). Then, after scanning all the blocks up to the end of the period (plus a margin to account for block chain reorgs), the recipient can be certain that they've received the corresponding funds. So now they can send those funds to themself at an address for a later period, confirm that transaction, back up the new HD root key, and delete the key for the old period.

[daira]

(BTW, I am not suggesting that we should block support for recovery seeds on changing the encryption scheme, just pointing out that these goals are not incompatible.)

[daira]

@nathan-at-least wrote:

@daira, would it be accurate to say that feature could be built on a layer above a 'stateless / static derivation seed' scheme described in this ticket?

It might have to use a specific derivation scheme designed for the purpose. However, I don't think there's any harm in implementing an opt-in hierarchical wallet scheme similar to BIP32 and then designing a new one later that supports forward security as well.

[tromer]

About forward-secure schemes with blockheight-dependent ciphertexts: this may break schemes that rely on "floating" transactions that are communicated between peers but not immediately posted on the blockchain. To the extent that such schemes even work with JoinSplits, they'd also need to be analyzed to see if a target blockheight can be fixed in advance.

[imichaelmiers]

You can do loosely time dependent forward security. http://cs.jhu.edu/~imiers/pdfs/forwardsec.pdf The problem is even if the ciphertext is forward secure, for zcash you must store its contents until you spend the coin. This limits the upside of forward secrecy severely

[tromer]

@imichaelmiers, by "loosely time dependent forward security", do you mean puncturable encryption? That's discussed above (#2038 (comment)).

[imichaelmiers]

Well you can combine the two is the point. But readying back on context, I don't think that helps at all.

[daira]

@tromer wrote:

About forward-secure schemes with blockheight-dependent ciphertexts: this may break schemes that rely on "floating" transactions that are communicated between peers but not immediately posted on the blockchain.

That depends on how long time periods are, and whether there's a delay before deleting the private key for a period.

[nuttycom]

Complete as of zcashd v4.7.0