Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Generating deterministic private spend keys for subwallets #831

Closed
zpalmtree opened this issue Jun 7, 2019 · 24 comments · Fixed by #944
Closed

Generating deterministic private spend keys for subwallets #831

zpalmtree opened this issue Jun 7, 2019 · 24 comments · Fixed by #944
Assignees

Comments

@zpalmtree
Copy link
Collaborator

@zpalmtree zpalmtree commented Jun 7, 2019

This is an idea I've been pondering for some time, and @ExtraHash brought it up independently the other day, so I think it warrants some discussion.

As you may know, when we generate a multi wallet container, we use one, shared, private view key, and multiple, randomly generated spend keys (Aside from the first wallets private spend key, which while randomly generated - is hashed to produce the private view key)

Now, this works fine - The shared private view key enables us to scan multiple wallets at the same speed as a single wallet.

However, if we want to restore our subwallets, we have an issue - We need to store every private spend key in an external store, say, a database. It's not a massive amount of data - but it does complicate things.

The private spend key is usually represented as a 64 char hex string, but it corresponds to a 32 byte key - or a 256 bit integer. As we know, this is equal to a point on the ed25519 ecliptic curve. I also believe that all ed25519 keys must be a multiple of 8 - to fall upon the curve.

So, I propose that after generating our initial private spend key, we generate subsequent keys by simply adding 8 to this private spend key, the next key by adding 8 to this key, and so on. This will allow us to then restore all our wallets with only the private view key, the initial private spend key, and the number of wallets required.

I am a little cautious that there could be some possible privacy or security implications of this.

Also, we would need some way in the wallet to track our current curve offset - We could simply start with the root key, and keep generating until we find a key we have not generated yet, but this could cause issues if the user desires 'deleted' wallets to be skipped over.
Adding an offset counter would require altering the wallet structure, however, since it would just be an optional field, would not really be disruptive.

@zpalmtree

This comment has been minimized.

Copy link
Collaborator Author

@zpalmtree zpalmtree commented Jul 4, 2019

Bump

@ExtraHash

This comment has been minimized.

Copy link
Contributor

@ExtraHash ExtraHash commented Jul 5, 2019

this is still something i'm planning on implementing in my wallet, i still need to add the subaddress stuff to the js backend so i can start experimenting though

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 5, 2019

I found an article the other day regarding how to properly do this in a safe way. 90% sure I bookmarked it for this thread. I’ll find the bookmark, post it here, and provide a summary. IIRC, simply adding 8 to the key isn’t the best way to do this.

@ExtraHash

This comment has been minimized.

Copy link
Contributor

@ExtraHash ExtraHash commented Jul 26, 2019

bump, did you ever find that summary?

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 26, 2019

bump, did you ever find that summary?

Yes. Now it's lost again.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 30, 2019

Okay, I found the article I was thinking of and it didn’t address this like I thought it did. I’m good to proceed with the proposed unless other objections are given.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 30, 2019

Actually, I take that back. If a +8 subwallet is compromised an attacker simply needs to walk up and down the line to discover additional key pairs that may contain funds.

However, (example) if we concat the private spend key and public spend key and hash the result then use that as the seed for the next subwallet private spend key, we turn it into a one-way calculation thereby reducing the attack vector in half. An attacker could still work their way into additional subwallets but could never (computationally restrictive) work their way back to the original key pair or any subwallets before the compromised subwallet.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 30, 2019

but wait... there’s more it can be 0 way.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 30, 2019

Option 1

Math

Let H = arbitrary one-way hash method (or KDF)
Let R = sc_reduce32 method
Let C = string concatenation method
Let S = wallet seed (in a deterministic wallet, this is the private spend key)
Let A = private spend key
Let a = public spend key
Let B = next private spend key

B = R(H(C(A,a,S)))

Explanation

This generates the next private spend key B by concatenating the current private spend key A with the current public spend key a and the wallet seed S then feeding it through the hash (or KDF) method H and running the sc_reduce32 method R to arrive at the new private spend key B. Therefore, if a subwallet is compromised, the attacker cannot step down (-1) in the subwallets because it is computationally infeasible and cannot step forward without S. This is okay because if they have S they have the keys to the kingdom anyways. As such, this limits the attack vector to a singular key pair.

Pros

  • Uses existing crypto operations
  • Simple to implement
  • Provides excellent security between private spend keys

Caveat

  • Subwallets must always be restored in order (ex. n, n+1, n+2, n+3, etc).
    * Wallets without seeds cannot be used.

Option 2

Math

Let H = arbitrary one-way hash method (or KDF) where the second argument is the number of iterations to use
Let R = sc_reduce32 method
Let S = wallet seed (in a deterministic wallet, this is the private spend key)
Let n = the 0-based index of the private spend key in the wallet structure (>=1 is a subwallet)
Let B = next private spend key

B(n) = R(H(S, n + 1))

Explanation

Much like we currently use the wallet seed S to calculate the private spend key of our first wallet today, this method continues this path relatively unaltered. Every subwallet private spend key is calculated by KDF methods based upon it's index within the wallet structure n plus 1 if using cn_fast_hash to avoid collision with the view keys. As it is wholly reliant on the seed itself, there is no correlation between one subwallet private spend key in either direction as reversing the key back to its seed is computationally infeasible and going deeper n+1 in the wallet is impossible as its based upon the seed. Again, as in option # 1, if the attacker has S they will still have keys to the kingdom which is a given.

Pros

  • Uses existing crypto operations
  • Simple to implement
  • Provides excellent security between private spend keys
  • Can restore any subwallet private spend key quickly without recomputing every private spend key between 0 and the subwallet index n.

Caveat

* Wallets without seeds cannot be used.

@zpalmtree

This comment has been minimized.

Copy link
Collaborator Author

@zpalmtree zpalmtree commented Jul 30, 2019

Nice summary.

Caveat

  • Wallets without seeds cannot be used.

I'm not sure why this would matter - Assuming seed refers to a primary, private spend key, derived from the shared private view key.
We're not using any of these properties in the proposed function - so why would a deterministic 'seed' based wallet be required, as opposed to just having a random private spend and private view?

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 30, 2019

Nice summary.

Caveat

  • Wallets without seeds cannot be used.

I'm not sure why this would matter - Assuming seed refers to a primary, private spend key, derived from the shared private view key.
We're not using any of these properties in the proposed function - so why would a deterministic 'seed' based wallet be required, as opposed to just having a random private spend and private view?

Corrected. I must not have had enough coffee this morning.

@ExtraHash

This comment has been minimized.

Copy link
Contributor

@ExtraHash ExtraHash commented Jul 30, 2019

it seems like option 2 is the better choice to me.

@SoreGums

This comment has been minimized.

Copy link
Collaborator

@SoreGums SoreGums commented Jul 31, 2019

looks good - having actually gone through the bips

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki

how come these schemes don't work?

they have kinds of addresses for a purpose (private/public | used inside the wallet/given out expecting people to send to them). these would simply be addresses over here, so not seeing why these don't work here

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Jul 31, 2019

https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

Got the cliff notes on this one? Some of what I'm saying below also plays a role here if I understand it correctly.

https://github.com/bitcoin/bips/blob/master/bip-0044.mediawiki

If I'm reading this right, this is talking about scanning for funds destined for sub-addresses; however, it does assume that the blockchain in question is transparent and thus the computational cost in doing so is marginal at worst. Creating additional sub-addresses is quick such that you can easily scan for transactions destined for sub-wallets 0-20 (example) with no noticeable performance impact as the transaction details have no privacy. If we can agree that my understanding of the document is correct then this document is not applicable based solely on the fact that we employ ring signatures and fungibility functions that result in the scanning of transactions for "our" funds is no longer a near zero-cost computation. As such, it is common for us to reuse the view keys while only changing the spend keys in each subwallet to help reduce the calculation cycles required to discover funds for a wallet container with multiple wallets.

Most of the logic in the linked BIP proposals are based on the fact that the chain is entirely transparent so they have the benefit of scanning for transactions that belong to "us" being a relatively simple calculation. Given that our chain is not transparent the same principles may or may not apply.

Make sense?

@SoreGums

This comment has been minimized.

Copy link
Collaborator

@SoreGums SoreGums commented Aug 2, 2019

hmm i see we check all transactions with the view key and that would then build the balance up. since transaction amounts aren't really tied to an address explicitily, it is all about the "do you have the private key for this output to then feed into an input on the next tranasaction"

that does not work well with the mentioned bips idea's of a way to organise a HD wallet.

I liked the concept of single seed, n accounts, m addresses though. it's pretty useful for one time use addresses, which seems to be a motivating aspect of wanting multiple addresses per wallet container in the first place.

I guess if someone wanted to have multiple accounts in the same container they could spin different view keys from the inital seed.

Do you think that is something to be included here? Allow for n accounts (different view keys derived from source seed)

makes it a bit clumsy to support as the user might create 5 such accounts and not do any transactions in accounts 2,3 & 4, before they did tranascations in account 5 (so if it were done automatically might get to block 500 to find account 2 is used, yet missed all the transactions in blocks 300-350 for account 5), thus the user needs to say up front that they used 5 in order to scan with 5x view keys when importing from scratch. which will slow things down, however if they want this feature anyway they will have to spin 5 containers so what is the difference??

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Aug 2, 2019

Do you think that is something to be included here? Allow for n accounts (different view keys derived from source seed)

Honestly, no. When reusing the same view keys and only changing the spend keys, we're able to scan transactions quickly as they only have to be scanned once. If we used n view keys, then the scan time per transaction output increases by a factor of n. If, for example, the user has 5 view keys in use in the same wallet, then we'd have to scan each output 5 times. That's very computationally expensive. It also adds complexity to the code that given the fact that they can spin up 5 wallets instead thereby making it not worth adding or supporting in my opinion.

It's far easier and computationally less expensive to change the spend key only as we do now. The question is, simply put, how do we do that in a deterministic way instead of using a random key pair for each new spend key set to facilitate easier restoration of subwallets?

@azalanwashere

This comment has been minimized.

Copy link

@azalanwashere azalanwashere commented Aug 2, 2019

If, for example, the user has 5 view keys in use in the same wallet, then we'd have to scan each output 5 times. That's very computationally expensive. It also adds complexity to the code that given the fact that they can spin up 5 wallets instead thereby making it not worth adding or supporting in my opinion.

all good. seems that if the feature is desired the people will have to figure out their own way of managing and dealing with separate view/spend key pairs at scale in their own bespoke system.

that resolves the query of "what about the way bitcoin/others do it that follow bip33/44"

am building a larger than normal operation where i need multiple accounts/separate wallets and was looking for a deterministic solution. probably go with something custom then instead of wallet-api.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Aug 21, 2019

If we're all in agreement, I think this one is the winner aye?

Option 2

Math

Let H = KDF method where the second argument is the number of iterations to use
Let R = sc_reduce32 method
Let S = wallet seed (in a deterministic wallet, this is the private spend key)
Let n = the 0-based index of the private spend key in the wallet structure (>=1 is a subwallet)
Let B = next private spend key

B(n) = R(H(S, n + 1))

Explanation

Much like we currently use the wallet seed S to calculate the private spend key of our first wallet today, this method continues this path relatively unaltered. Every subwallet private spend key is calculated by KDF methods based upon it's index within the wallet structure n plus 1 if using cn_fast_hash to avoid collision with the view keys. As it is wholly reliant on the seed itself, there is no correlation between one subwallet private spend key in either direction as reversing the key back to its seed is computationally infeasible and going deeper n+1 in the wallet is impossible as its based upon the seed. Again, as in option # 1, if the attacker has S they will still have keys to the kingdom which is a given.

Pros

  • Uses existing crypto operations
  • Simple to implement
  • Provides excellent security between private spend keys
  • Can restore any subwallet private spend key quickly without recomputing every private spend key between 0 and the subwallet index n.
@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Aug 30, 2019

Message above has been updated to clarify that a KDF (ex. PBKDF2 or some other method) must be used for H. Using straight cn_fast_hash in a loop with iterations results in the ability of simply hashing the spend key once and getting the next key.

On first pass, even a simple KDF such as:

function kdf(privateKey, subWalletIndex) {
  const idx = subWalletIndex % privateKey.length
  const subWalletSeed = privateKey.substring(idx) + privateKey.substring(0, idx)
  return cn_fast_hash(subWalletSeed)
}

Appears to prevent the issue. More testing to follow.

@ExtraHash

This comment has been minimized.

Copy link
Contributor

@ExtraHash ExtraHash commented Sep 26, 2019

Bump

@zpalmtree

This comment has been minimized.

Copy link
Collaborator Author

@zpalmtree zpalmtree commented Sep 27, 2019

I think it's worth noting that you will no longer be able to distribute the private keys to the first wallet generated, since this is the 'seed' for all other subwallets. I wonder if there is a good way to prevent developers who are not aware of this from shooting themselves in the foot.

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Sep 27, 2019

Not unless we don’t use the seed for the first private spend key which breaks old wallet restoration.

We can put a note in documentation to watch your toes :)

@brandonlehmann

This comment has been minimized.

Copy link
Collaborator

@brandonlehmann brandonlehmann commented Sep 27, 2019

Plausible implementation in: turtlecoin/turtlecoin-utils@c46dab4

@SoreGums

This comment has been minimized.

Copy link
Collaborator

@SoreGums SoreGums commented Sep 27, 2019

I wonder if there is a good way to prevent developers who are not aware of this from shooting themselves in the foot.

not really - RTFM is about all there is. devs being n00bs are always going to get owned in crypto, that's just how it is. we want sovereignty over this stuff then own it. Else stay away and go to a third party that does whatever they want, aka the status quo.

@brandonlehmann brandonlehmann self-assigned this Nov 16, 2019
brandonlehmann added a commit that referenced this issue Nov 16, 2019
…enerates new deterministic subwallet keys as defined in #831
brandonlehmann added a commit that referenced this issue Nov 23, 2019
…enerates new deterministic subwallet keys as defined in #831
brandonlehmann added a commit that referenced this issue Nov 23, 2019
…enerates new deterministic subwallet keys as defined in #831
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.