Improved bulletproof rewind scheme

[jaspervdm]

Edit 2019-06-10: rename nonce_A -> rewind_nonce, nonce_B -> private_nonce, small change message contents
Edit 2019-05-25: fixed some inaccuracies
Edit 2019-05-22: clarified nonce_B for child wallets

I would like to propose a new scheme for hiding information inside the Bulletproof, that will increase wallet flexibility.

Recap

For context I will briefly explain relevant parts of the Bulletproof generation process:

• The user generates 4 secret variables (seeded with a nonce): alpha, rho, tau_1 and tau_2.
• They calculate mu = alpha + rho*x, where x is a verifier challenge (it is derived from hashing public data)
• They calculate tau_x = tau_2*x^2 + tau_1*x + z^2*gamma (*), where z is again a verifier challenge and gamma is the secret key of the commit
  The final proof contains (among other things) mu and tau_x.

In the current generation scheme, the nonce for the 4 secret variables is given by something like H(root_key|commit). However, mu is actually replaced with

mu' = mu + path|v

where v is the amount.

A wallet can find its own outputs by going through each UTXO bulletproof and

• Calculate the nonce and from that derive mu to find the amount v and derivation path by subtracting its mu from the mu' in the BP
• Find the secret key by solving (*) for gamma, using the calculated tau_1, tau_2 and the tau_x encoded in the proof
• If gamma*G + v*H is equal to the original commit, we know the output belongs to us (with extremely high probability).

There are several downsides to this method:

1. To find your outputs, you need to know the root_key, so there is no possibility for watch-only or child wallets
2. Rewinding exposes the private key, so even if we fixed the first issue by using H(root_key) in the nonce, we are left with a similar issue
3. Introducing different wallet types, such as watch-only, child wallets or changing the switch commitment scheme will create a grinding problem

New scheme

In an attempt to solve these issues, here is a proposal for a new scheme. To prevent having to grind the old and new scheme, I suggest that any output created after the first hard fork be created with this scheme.

First we generate 2 nonces:

rewind_nonce = H(H(pub_root_key), commit)
private_nonce = H(H(root_key), commit)

We use rewind_nonce to derive alpha and rho, and private_nonce to derive tau_1 and tau_2. This immediately solves problem 1) and 2) in the list.
We also replace mu with

mu' = mu + flags|path|v

Where flags are 4 bytes: 0|type|switch_commitment_scheme|derivation_depth. The first byte is reserved for future use (hence the 0), the 2nd byte can be used to indicate different wallet types (regular, child wallet, musig), the 3rd byte can be used for different switch commitment types (0 for none, 1 for the current one) and the final byte is used to store the level of the derivation path (assumed to be 3 in the old scheme). There should be enough room to encode all this information, since the path is 16 bytes and v is 8 bytes, while mu can contain nearly 32.

Wallet restore

For a wallet to find their own outputs, they need to know the extended public key. They calculate mu and from this find flags|path|v. This operation will be successful for all outputs, but we can quickly discard most of them, namely the ones with unknown flag bytes. The left over ones are candidates for which we can use the derivation path and the extended public key (or secret key in the case of a hardened path), together with the amount to derive the candidate commitment. If the commitment matches the original, we know the output belongs to us. This solves problem 3) in the list.

Conclusion

This enables different kind of wallets:

• Regular wallets: they are of course still possible, everything is still derived from the seed
• Child wallets: give out H(pub_root_key) and the extended secret child key. They should use some other value for private_nonce, for example H(H(child_key), commit). Children will be able to detect/create/spend their own outputs. Parents can detect/create/spend all of their child wallets. When scanning the chain children will detect candidate outputs from other children but there is some deniability here.
• Watch-only wallets: give out pub_root_key. This will allow users to detect their outputs, but not spend them
• Multisig wallets: multisig users can use a common nonce to find the outputs owned by them

One thing to note is that the watch-only and multisig wallets are harder to use in combination with switch commitments, but I think not impossible. It would require knowing an additional extended public key, one that uses J instead of G as generator point.

Any comments and suggestions are welcome! This idea has been brewing in my mind for a while and I think it will work pretty well, but I might have missed some downsides or problems.

[chisa0a]

Awesome work!

One thing to note is that the watch-only and multisig wallets are harder to use in combination with switch commitments ... It would require knowing an additional extended public key, one that uses J instead of G as generator point.

Why is knowledge of J generator required, and what makes this difficult re: watch-only + multisig? Is section 4 from the Bulletproof paper the relevant background reading?

[jaspervdm]

@chisa0a Switch commitments offset the blinding factor with H(xG+vH | xJ). With a watch-only or a multisig you usually only know total public key xG (derived from the extended public key(s), but this is not enough to calculate the extra term, for which you need xJ as well. With a customized BIP32 hasher I think we can derive it, but I haven't thought too deeply about it.

[tromp]

Would it make sense to generalize to

nonce_A = H(H(root_key|i_A)|commit)
nonce_B = H(H(root_key|i-B)|commit)

where i_A and i_B default to 0 and 1 (or 1 and 2 as you have) but could be chosen larger if the user wants to obfuscate her rewind info some more, at the cost of having to grind more if she can't remember the exact values used, but only an upper bound?

[garyyu]

@jaspervdm nice design 👍

---

1st question regarding

For a wallet to find their own outputs, they need to know H(root_key|1) and an extended public key.

Without telling H(root_key|2) (i.e. without knowing nonce_B), does the rewind still work?
Should it be like this?

nonce_A = H(H(root_key)|1|commit)
nonce_B = H(H(root_key)|2|commit)

---

2nd, (suggestion instead of question) regarding:

nonce_A = H(H(root_key|1)|commit)
nonce_B = H(H(root_key|2)|commit)

May I suggest use root_public_key instead of root_key?

nonce_A = H(H(root_key*G|1)|commit)
nonce_B = H(H(root_key*G|2)|commit)

nothing special but like the concept of PublicKeyHash 😄

[jaspervdm]

@tromp I'm not convinced we should. It would complicate the code (we have to implement the grinding) and UX but in my opinion there is not a very clear upside. Anyone that doesn't want their outputs detected by others just shouldn't give out their H(root_key|1). But if more people think its a good idea we can add it.

@garyyu Thanks!
Regarding your first suggestion: a full rewind consists of two parts, 1) using mu (meaning rho and alpha) to find the amount and derivation path 2) using tau_1 and tau_2 to find the secret key. By using a different nonce for both of them, we can make sure we don't expose the secret key, but still are able to detect if an output belongs to the wallet. If we implemented your suggestion, anyone that can detect outputs (because he knows H(root_key)), would also be able to spend them, because he can use the same hash to calculate the nonce_B and use equation (*) to find the secret key. This means we can't have child wallets or watch only wallets

Unfortunately the second suggestion would also break the scheme in a similar way, since a watch only wallet would know root_key*G, meaning they could calculate nonce_B and steal outputs.

[yeastplume]

Okay, sorry it took me a bit to get through it, had to go through the existing implementation in secp-zkp to remind myself exactly what's going on.

Very good improvement to what's there. It's still relatively simple and shouldn't be too difficult to implement, with the only real downside being a slight optional loss of privacy on the root wallet owner's side. I still very much wish we could store the restore information somewhere other than the bullet proof, but that's a problem for another day.

If nobody finds any major issues with this over the next few days, I'm happy to start working towards getting this in for 1.1.0. If you wanted to insert support for the new scheme on the libsecp side and I can make the needed changes in grin-wallet and grin, that might work. But if you're too busy I can handle all of it, just let me know.

[jaspervdm]

Thanks for checking. I am happy to do the libsecp side of things, will get started on it this week. To be sure, we should include it in v2.0.0, not v1.1.0 right?

[yeastplume]

Definitely, yes, and obviously targeting the hard fork block (all outputs before use old rewind scheme, all outputs after use new one).

[DavidBurkett]

Just a quick reminder that there's not really an easy way to enforce all new transactions using the new rewind scheme. There could be pre-fork slates that get finalized post-fork. The only way to actually mandate that would be on the wallet side, by bumping slate version post-HF and not accepting old slates after the hardfork block.

[yeastplume]

Depending on what we end up tweaking for the HF, it could definitely be the case that we invalidate old transactions. Think we need to discuss/clarify exactly what will change for the HF

[ignopeverell]

Great scheme, 👍 No particular remark or concern beyond what's been discussed, we should prolly start on a wiki page listing what we're breaking for the 2.0.0 HF, so we don't forget anything.

[jimpo]

Cool. A few questions/comments:

• Why does a watch-only wallet need an extended public key if it has H(root_key|1)?
• Am I right in thinking that a watch-only wallet can can't receive new transactions either, since that would require the secret key?
• How does a child wallet compute nonce_B for its own transactions without root_key or H(root_key|2)?
• You write "When scanning the chain children will detect candidate outputs from other children but there is some deniability here." What do you mean by deniability here? It seems like any child wallet can see all outputs for the whole parent wallet? Or is there some other information it would need in addition to H(root_key|1)?

[jaspervdm]

@jimpo

1. The wallet will do a rewind on any output. So each output will have a candidate amount and derivation path. The only way to know for sure if the output belongs to the wallet is if we can reproduce the commitment by calculating P+vH where P is the public key derived from the extended key and v the amount.
2. Yes, that is correct.
3. It doesn't. We don't use nonce_B for any rewinds, so the precise form of nonce_B is not important, what is important is that it is distinct from nonce_A. So for child wallets we could use H(child_ext_secret_key|2) for example. I will update the original issue with this, thanks for the feedback.
4. If the flags have correct values and the identifier "looks good" there is a high probability that the output belongs to the parent wallet. But to be sure the output belongs to the parent, you would need to know the extended public key of the other children and try to reproduce its commitment (see 1)).

[jimpo]

Ah, thank you. Just to make sure I'm clear on this: in the current scheme, gamma is found by rewinding, whereas in this new proposal, gamma is derived from the extended secret key and the derivation path, which is itself found by rewinding?

[jaspervdm]

In practice currently gamma is re-derived using the derivation path, but right now you could find gamma by rewinding, which is something this proposal would prevent.

[lehnberg]

we should prolly start on a wiki page listing what we're breaking for the 2.0.0 HF, so we don't forget anything.

@ignopeverell I made an effort to start this, all please feel free to contributing and help with this: https://github.com/mimblewimble/docs/wiki/Release-planning

[hansieodendaal]

Hi @jaspervdm, we are trying to do something similar to what you have done here. If you have a moment, I would appreciate any comments you may have on the issue I registered with Dalek: dalek-cryptography/bulletproofs#335.
Thanks!