fix: range proof batch verification feature

[garyyu]

For detail, please refer to https://github.com/mimblewimble/grin/issues/1321

This is the major fix to make the rangeproof batch verification work. The main benefit is speed! For example with 1000 range proofs, this batch verification speed is near 50 times faster as the total single range proof verifications.

And this PR also include an important optimization for range proof, use a shared generators, avoid recreating every time.

[garyyu]

And I'm still checking the travis-ci errors, will give new commit to make it pass anyway.

[garyyu]

@jaspervdm Thanks very much! Indeed, I confirm this fix will cause all existing bulletproofs (w/t extra message) on T3 invalid!

Here is my test result, and the test code is here: https://github.com/garyyu/rust-secp256k1-zkp/blob/master/src/demo.rs#L863-L934

$ cargo test --release test_compare_old_bullet_proof -- --nocapture

running 1 test
Compare Bullet Proof between new and old version, w/t extra message...

Value:      12345678
Blinding:   SecretKey(a4445dfb3801571dbf180c0672ebbaf95e34061bd6b5bd8acaaaf042b58b069a)
Commitment: Commitment(09814fcc8147f6873c3c170a04314504dfd6d04d463b8023d95d5e55e80a578cf7)

Bullet Proof Old:   RangeProof(ba749bb00cc1f3df...)[675]
Bullet Proof New:   RangeProof(460ad41e6611a1b0...)[675]

New verification on old proof:  Err(
    InvalidRangeProof
)

New verification on new proof:  Ok(
    ProofRange {
        min: 0,
        max: 18446744073709551615
    }
)

Compare Bullet Proof between new and old version, w/ extra message...

Value:      12345678
Blinding:   SecretKey(b7785a24bf8f42371f43286749c165e26fdeadd59da4d9081cc131e0d21ab975)
Extra data: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Commitment: Commitment(098ddddcf567a9ca7dfa47d6fa0b4f861ed0dae07559349e5af4715143d138ef9c)

Bullet Proof Old:   RangeProof(8ed7a899ab8bd7b5...)[675]
Bullet Proof New:   RangeProof(8ed7a899ab8bd7b5...)[675]

New verification on old proof:  Ok(
    ProofRange {
        min: 0,
        max: 18446744073709551615
    }
)

New verification on new proof:  Ok(
    ProofRange {
        min: 0,
        max: 18446744073709551615
    }
)

Compare rewinding. Extracts the value and blinding factor...

Rewind_bullet_proof on old proof:   Ok(
    ProofInfo {
        success: true,
        value: 12345678,
        blinding: SecretKey(5393a047241131ee6a922e81b7a12275108dfde755d74c354b25c445be74b5fd),
        message: ProofMessage(),
        mlen: 0,
        min: 0,
        max: 18446744073709551615,
        exp: 0,
        mantissa: 0
    }
)

Rewind_bullet_proof on new proof:   Ok(
    ProofInfo {
        success: true,
        value: 12345678,
        blinding: SecretKey(5393a047241131ee6a922e81b7a12275108dfde755d74c354b25c445be74b5fd),
        message: ProofMessage(),
        mlen: 0,
        min: 0,
        max: 18446744073709551615,
        exp: 0,
        mantissa: 0
    }
)

[garyyu]

@ignopeverell warning before using this fix, it's a hard fork for T3!

[yeastplume]

I'm going to take a local copy of this PR and check locally. Sending in values for extra_data will indeed change the proof and verification, but I don't see why it should be necessary to do so in order to get batch validation to work.

[garyyu]

@yeastplume you can test the last part in test_bullet_proof_verify_multi(), if using the empty vector (previously) instead of a null pointer (this version), bullet_proof() created bulletproof can't pass the verify_bullet_proof_multi verification.

[yeastplume]

Okay, it would have been slightly more optimal to send in null instead of an empty vector originally for T3 (and we can fork that easily enough later, I don't think it will have a massive speed impact), but it's perfectly possible to send in a set of empty vectors into the batch verify function rather than null so as not to break consensus. I've tested locally and it seems to work fine.

Let me do some more testing on it and if it validates T3 proofs properly, I'll merge this and make the additional changes on top.

[garyyu]

OK:) That's good you can make it compatible to existing T3 rangeproof.

[yeastplume]

Okay, was able to fully sync and validate with these changes + passing in zero vectors instead of nulls. Will merge then add my changes on top.