Switch Commits / Bulletproofs - Status

[yeastplume]

I just wanted an issue open to track the current status of Bulletproofs, bulletproof message and switch commits, and make sure everyone is on the same page as to what's actually in the code (or will be very shortly when #730 (BulletProofs and message hiding within bullet proofs) is committed).

Bulletproofs

Bulletproofs are implemented within our fork of libsecp256k1, although based on a very early, untried and un-reviewed version of @apoelstra's code. The current iteration of the code works and has a few unit tests within both libsecp256k1 and the rust wrapper to exercise them, however I've marked off all of the API functions as deprecated to make the warnings about the pre-production state of this code remain prevalent. Also note that I had to make some changes to the EC Multiplication code within bullet proofs to remain consistent with earlier changes I'd made in our fork to support Aggsig/Schnorr, so any updates to bulletproof code are unlikely to be simple merge (not that updating will be a gigantic task, it just needs some care).

There are 2 main functions, one to create the proof and one verify:

The prove function takes a value, a secret key (blinding factor in our case) a nonce optional extra_data, and a generator and produces a 674 byte proof. I've also modified it to optionally take a message (more about this in a bit). It creates the pedersen commit it works upon internally with these values.

The verify function takes a proof, a pedersen commitment and optional extra_data and returns true if proof demonstrates that the value within the commit is in the range [0..2^64] (and the extra data is correct). It's up to the caller to create this commit correctly with the same value, key and generator passed in initially.

Additionally, I've added an unwind function which takes a proof, a commit, optional extra_data and a 32 bit nonce (which needs to be the same as the original nonce used in order to return the same message) and returns the hidden message. The message hiding and retrieval works as follows:

As part of bulletproof creation, two 32 byte nonces alpha and tau1 are generated using an RNG. These values are then operated upon to create a series of final values that remain publicly available as part of the proof, and can be re-derived from a proof by reversing operations with other available data until you arrive at the original RNG-derived alpha and tau1 values.

The seed passed to the RNG to generate alpha and tau1 is 64 bytes long and composed of:
nonce | sha256(commit|extra_data).

Therefore, if I call unwind with the same nonce and commit used to create the proof, I can seed the RNG with the same values to produce the original values for alpha and tau1.

To embed 64 bytes worth of message in a bulletproof, I can provide as the nonce to the prove function a value that I'll keep around, in our case it will simply be the blinding factor used to create the proof). Then:

• The RNG is seeded with nonce|sha256(commit|extra_data), and creates alpha and tau1.
• I then XOR the first 32 bytes of my message with alpha to create alpha1, the second 32 bytes of my message with tau1 to create tau1_2.
• I then continue to create the bullet proof using alpha1 and tau1_2 instead of the original values.

To unwind the message out, I call unwind with the proof, commit and nonce (which is my secret key/blinding factor again) which:

• Demonstrates the proof is valid for the given commit and proof
• Seeds the RNG using the same nonce|sha256(commit|extra_data) pair I've provided above, and generates the original alpha and tau1.
• Populates the recovery message m as alpha|tau1
• Calculates alpha1 and tau1_2 from the information available in the bulletproof
• XORs m with alpha1 | tau1_2, to give back the original message.

And that is a basic description of what's implemented in the code at the moment.

Two other notes:

• It was possible in the original rangeproof implementation to unwind the value back out from the proof if you have the secret key originally used without having to store the value in the message. However I don't know whether this is possible within bulletproofs, and if so it's currently not implemented.
• If you have the correct commit and proof and extra_data, and attempt to unwind a message out using the wrong nonce, the attempt won't fail, you'll get get gibberish or just wildly incorrect values as you parse back the bytes. Since the message embedding is a simple XOR, it has no way of determining whether the inverse XORing produces what you're expecting.

Switch Commits

With that in mind, the current code implementation just stores a single 64 byte bullet-proof message for an Output, which contains:

• The 8 byte (64 bit) value of the Output (for later recovery during wallet reconstruction)
• 56 bytes of zeroes (to pad to 64 bits)

Now recall that with switch commits, an output is structured as follows:

(vG + bH, blake2(bJ,r))

Where J is a third NUMS generator, r is another wallet-seed derived value and the original commit vG + bH remains perfectly hiding, even in the event of viable quantum calculation. Also note that filling out blake2(bJ,r) is supposed to be completely optional (and unfortunately provides a undesirable storage location).

In the event of a quantum computeageddon, the owner of an output can choose to remain anonymous and never claim ownership of the (still hidden) output, or can choose to reveal bJ and r.. validators can then confirm blake2(bJ,r) matches what's in the switch commit, ownership is proven and amounts can be moved to some other quantum secure mechanism.

The switch commit hash is currently a field of an output, and while it is stored in the txo set and passed around during a transaction, it is not currently included in the output's hash. It is passed in as the extra_data field above, meaning that anyone validating the range proof also needs to have the correct switch commit in order to validate the range proof.

[yeastplume]

Should have gone back and read this issue, and I think I know where the disconnect is now (in my head) #207

Have updated the code and all of this should be complete. Updated above to reflect current status. Will close this issue but it should serve as a reference.