Bulletproof rewinding proposed (and tested) for a single range proof

[hansieodendaal]

Hi there,

I would like to know how open the dalek-cryptography/bulletproofs maintainers and community are to add Bulletproofs rewinding functionality to the crate.

We use dalek-cryptography/bulletproofs in our project and have a need to do wallet recovery from seed values. I have implemented Bulletproof rewinding in a fork on main that is similar to what other projects have done (e.g. Grin), demonstrated from a user perspective in this test.

The user calls pub fn prove_single_with_rewind_key instead of pub fn prove_single, with two additional parameters, pvt_rewind_key: &Scalar and extra_data: &[u8; 23]. The 23 bytes extra_data can be any message a user wants to embed within the proof. Internally, pvt_rewind_key is converted into a rewind nonce and a private nonce:

rewind_nonce = H( H(pub_key_from_pvt_key(pvt_rewind_key)), commitment)
private_nonce = H( H(pvt_rewind_key), commitment)

With the Party and Dealer's algorithm:

1. a_blinding is replaced by rewind_nonce
2. s_blinding is replaced by XOR(rewind_nonce, merge_into_word(value, extra_data))

1. t_1_blinding is replaced by private_nonce
2. t_2_blinding is replaced by private_nonce

Usage:

• Verifying the proof with pub fn verify_single still works exactly as it did before.
• The owner and delegated 3rd parties can use pub fn get_rewind_nonce_from_pub_key to retrieve rewind_nonce for a specific commitment.
• The owner can use pub fn get_private_nonce_from_pvt_key to retrieve private_nonce for a specific commitment.
• The owner and delegated 3rd parties can use pub fn rewind_single_get_value_only to rewind a proof for a given commitment, to get the value and 23 bytes extra_data only. If the wrong rewind_nonce is provided, garbage data will be returned.
• The owner can use pub fn rewind_single_get_commitment_data to rewind the proof for a given commitment, returning the value, blinding factor and 23 bytes extra_data upon success.

Thank you kindly.

[cathieyun]

Some questions / comments:

1. What is the commitment used to generate rewind_nonce and private_nonce?
2. Is the extra_data value considered public knowledge? Or should it be treated the same way as the private rewind key? Could it be chosen / controlled by a malicious party (can anyone choose what data to include in a proof)? I ask because it looks like sensitive data - it seems possible to leak information about rewind_nonce by choosing extra_data cleverly, or if you have information about extra_data, due to its use in s_blinding. Generally, a_blinding and s_blinding should be entirely independent, since they are blinding factors operating over the same generator (b-tilde). If they are not independent, you can leak information about the values they are blinding.
3. You cannot replace both t_1_blinding and t_2_blinding with the same value, for the same reason as above - they are blinding factors over the same generator, so you would be able to learn information about t1 and t2 if you subtracted the T1 and T2 commitments from each other.

Generally, this seems like a very insecure / dangerous modification to make to the protocol. If you can explain the bigger-picture goal with rewinding, maybe we could suggest a more robust way to go about solving the problem.

[hansieodendaal]

Hi yes, thank you for the really insightful response.

1. What is the commitment used to generate rewind_nonce and private_nonce?

This would be the Pedersen commitment, V_j

2. Is the extra_data value considered public knowledge? Or should it be treated the same way as the private rewind key? Could it be chosen / controlled by a malicious party (can anyone choose what data to include in a proof)?

extra_data is private or can be shared with a trusted 3rd party in the same way one would share the pub_rewind_key, 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 indeed from one of your own commitments V_j.

2. Generally, a_blinding and s_blinding should be entirely independent, since they are blinding factors operating over the same generator (b-tilde). If they are not independent, you can leak information about the values they are blinding.

Yes, this is intended.

3. You cannot replace both t_1_blinding and t_2_blinding with the same value, for the same reason as above - they are blinding factors over the same generator, so you would be able to learn information about t1 and t2 if you subtracted the T1 and T2 commitments from each other.

Yes, I have thought about this, but was not sure. This should definitely be made more secure, and one way could be by providing two private rewind keys, e.g. pvt_rewind_key_1 and pvt_rewind_key_2, to derive private_nonce_1 and private_nonce_2. The first could be used as before for a_blinding and s_blinding, and both could be used in the calculation for T_1 and T_2, where t_1_blinding is replaced by private_nonce_1 and t_2_blinding is replaced by private_nonce_2.

Generally, this seems like a very insecure / dangerous modification to make to the protocol. If you can explain the bigger-picture goal with rewinding, maybe we could suggest a more robust way to go about solving the problem.

This would be very much appreciated.

The main use case has to do with wallet recovery. So 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. With the wallet seed words, the unique deterministic sequence of blinding factors a wallet would produce can be replayed. However, this is not sufficient or practical for wallet recovery. One protocol that can be used in a wallet to enable recovery from Bulletproof rewinding is to derive one or more private rewind keys from the seed words and to use it in every UTXO construction.

A secondary use case would be for trusted 3rd parties to identify spending, by only having access to the public rewind key and embedded extra data.

[burdges]

Could the wallet not merely encrypt messages to itself somewhere?

As an aside, there is no mechanism by which wallets can even observe newer higher speed chains, much less fetch historical data, but addressing that requires other solutions, like anonymous messaging schemes ala mixnets and some storage scheme. I've zero clue about this design or when aynone will really make such solutions work, but it'll be more future proof if you structure things as encrypted messages, and do not assume that wallets can find old transactions.

[hansieodendaal]

Could the wallet not merely encrypt messages to itself somewhere?

This would be a use case for wallet recovery where a user did not make backups.

[hansieodendaal]

Closed in favour of #335.