Updated: Bulletproof rewinding proposed for a single range proof

[hansieodendaal]

This is a proposal to add Bulletproofs rewinding functionality to the Bulletproofs crate as a user option. (updates #329)

We use dalek-cryptography/bulletproofs in our Mimblewimble implementation project and have a need to do wallet recovery from seed values. The proposal for the Bulletproof rewinding scheme is implemented here, in a fork on main, and demonstrated from a user perspective in this test.
Note: This proposal is similar to what has been proposed and implemented for Grin, as discussed here.

Three additional parameters are introduced when creating a proof for a value commitment:

• pvt_rewind_key: &Scalar;
• pvt_blinding_key: &Scalar and
• proof_message: &[u8; 23].

The 23 bytes worth of proof message can be any message a user wants to embed within the proof. Internally the two private keys, in combination with the value commitment, are converted into two rewind nonces and two blinding nonces:

rewind_nonce_1 = H( H(pub_key_from_pvt_key(pvt_rewind_key)), value_commitment)
rewind_nonce_2 = H( H(pub_key_from_pvt_key(pvt_blinding_key)), value_commitment)
blinding_nonce_1 = H( H(pvt_rewind_key), value_commitment)
blinding_nonce_2 = H( H(pvt_blinding_key), value_commitment)

With the Party and Dealer's algorithm:

1. a_blinding is replaced by rewind_nonce_1
2. s_blinding is replaced by XOR(rewind_nonce_2, merge_into_word(value, proof_message))

1. t_1_blinding is replaced by blinding_nonce_1
2. t_2_blinding is replaced by blinding_nonce_2

Usage:

• The user calls a new function called prove_single_with_rewind_key, instead of prove_single, with the three additional parameters to create the proof.
• Verifying the proof with pub fn verify_single still works exactly as it did before.
• Rewinding a Bulletproof can take place according to one or both of these processes:
  • A - peak value: firstly to return the value and proof message only [returning garbage data if the wrong rewind nonces are provided], or,
  • B - rewind fully: secondly to return the value, blinding factor and proof message [returning an error if the wrong rewind and blinding nonces are provided].
• The public rewind keys can be shared with a 3rd party. The owner and/or delegated 3rd party can then use these keys in conjunction with a specific value commitment to calculate candidate rewind nonces for its proof. The returned proof message from the first rewind step can be used to narrow down the probability that the particular proof belongs to a specific collection.
• The owner alone will be able to use both sets of pub-pvt key pairs in conjunction with a specific value commitment to calculate candidate rewind and blinding nonces for its proof. The second rewind step will reveal the details of the value commitment and proof message if successful.

Notes:

• The main use case has to do with wallet recovery. A user would normally have a backup of their unique wallet seed words somewhere, but could more easily lose their entire wallet without having made any backups or only having old backups. If a wallet can derive one or more sets of private keys from the seed words and use them in every UTXO construction as proposed, it can enable wallet recovery using Bulletproof rewinding.
• A secondary use case would be for trusted 3rd parties to identify spending, by only having access to the public rewind key and the embedded proof message.
• The use for this protocol, as opposed to simply revealing the original value along with the blinding factor to whoever wants the plain value, is to protect the UTXO. In Mimblewimble, if the value commitment can be opened, it can be spent without the owners knowledge.
• The proof message is private or can be shared with a trusted 3rd party in the same way one would share the public rewind keys, but not common public knowledge. It is totally arbitrary, but known data, to enable identifying beyond a doubt if the returned value v_j is from a specific collection of value commitments V_j.
• This scheme has been improved in what has been presented in Bulletproof rewinding proposed (and tested) for a single range proof #329, by not using the same rewind nonce for a_blinding and s_blinding nor the same blinding nonce for t_1_blinding and t_2_blinding.

[delta1]

Hi @cathieyun @isislovecruft @hdevalence - do you have any feedback on this proposal please? We would be very grateful to hear your thoughts 🙏

[cathieyun]

Do you have a proof of security for the updated scheme? Given that in the previous scheme I could find a vulnerability within a few minutes, I am a bit skeptical with this update but don't have the time to dig into it.

[hansieodendaal]

Hi there, no proof of security, no yet anyway, just improved as per your previous comments. The question that remains is if Bulletproofs rewinding is fundamentally flawed or if such a scheme as this can be made into a proper solution.