Skip to content
This repository was archived by the owner on Dec 28, 2023. It is now read-only.

Range Proof

Jump to bottom
Gary Yu edited this page Aug 7, 2018 · 18 revisions

Range Proof is used to prove, with zero-knowledge (i.e. without revealing the amount or the blinding factor), that the value committed to in a given Pedersen Commitment falls within a certain range in [0, 2^64], so that user cannot exploit the blinding to produce overflow attacks, etc.

Why range proof is necessary for each output commitment?

Let's have a simple example to demo it.

Suppose we have a transaction case that Alice spend 3 coins to send Bob 2 coins and get 1 coins change. In this transaction, we have:

  • 1 input commitment: 113*G+3*H, the original UTXO of Alice, used in this transaction as the input.
  • 2 output commitments: 42*G+1*H (the change of Alice), and 99*G+2*H (the output for Bob).
  • 1 transaction kernel, which include 3 parts:
    • msg (a random number in this example).
    • excess (13*G, i.e. k1*G, after splitting the key k = k1 + k2.
    • signature (with private key: 13, i.e. k1.
  • offset: 15, i.e. k2. Note: k=k1+k2=28.

A detail data of this transaction could be like this: (read Transaction Aggregation for the more info about this transaction example.)

  input=113*G+3*H:	Commitment(0955e54cd28baa1416c1f795f6ddba1c2d1f760c9d9b515360ef944babe3eea352)
output1= 99*G+2*H:	Commitment(0878992a66a47907eefad338908cd0a44941aa4219706a2c9d0de2fa0559863eaa)
output2= 42*G+1*H:	Commitment(091c1f29a819b7d3fde56f425692e9cb9a6682ae412a1a1019b3261da6439371e6)

	msg:		Message(d851581d434b9f2718b89f3441b13062e651cdbc4752e99767b706d640ede882)
	excess w/ k1*G:	Commitment(09f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8)
	Signature:	Signature(91bb7da507b3c8b67b0e47e35f1406b5b92381a8edba6b5f9755f79f0555d848bb0b333aa0f6dd67d5fb414620c2d3da74f5f9dce409726b4a89c9ad953ec10e)
	k2:		SecretKey(000000000000000000000000000000000000000000000000000000000000000f)

sum with k2*G verify OK:	output1 + output2 = input + excess + k2*G

Now, let's do a little change on it to create a fraud transaction:)

  • 1 input commitment: 113*G+3*H, the original UTXO of Alice, used in this transaction as the input.
  • 2 output commitments: 42*G-100*H (the change of Alice), and 99*G+103*H (the output for Bob).
  • 1 transaction kernel, which include 3 parts:
    • msg (a random number in this example).
    • excess (13*G, i.e. k1*G, after splitting the key k = k1 + k2.
    • signature (with private key: 13, i.e. k1.
  • offset: 15, i.e. k2. Note: k=k1+k2=28.

A detail data of this transaction could be like this:

  input=113*G+3*H:	Commitment(0955e54cd28baa1416c1f795f6ddba1c2d1f760c9d9b515360ef944babe3eea352)
output1= 99*G+103*H:	Commitment(09c1e7b18f9017d841818216898314e81695a06a345cfcce718eb812f82041fbee)
output2= 42*G-100*H:	Commitment(09c012fc9b667902ffaa392d12b010ff6d79987c6bd0ae1334e969d6c60d16aa58)

	msg:		Message(b03bf2764ac43bdb151ecdbdcb15ff794cadcf95131ebe718b1e27c0780ccb5a)
	excess w/ k1*G:	Commitment(09f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8)
	Signature:	Signature(91dfb90e0516464de3d1ad197d8a1456533fc27b272fc84cde13f6bcdad1b9275cf0715f54069f80bfbd7dd32d8b944006965e40b3d699e8a45a020e356f5f1c)
	k2:		SecretKey(000000000000000000000000000000000000000000000000000000000000000f)
Signature verify OK

sum with k2*G verify OK:	output1 + output2 = input + excess + k2*G

You can run this demo to check the result:

Environment preparation:

$ git clone https://github.com/garyyu/rust-secp256k1-zkp.git
$ cd rust-secp256k1-zkp
$ cargo build --release
Source Code (Click to expand) 

    #[test]
    fn test_demo_fraud_transactions() {
        let secp = Secp256k1::with_caps(ContextFlag::Commit);

        fn commit(value: i64, blinding: SecretKey) -> Commitment {
            let secp = Secp256k1::with_caps(ContextFlag::Commit);
            let v: u64;
            let mut blind = blinding;

            if value >= 0 {
                v = value as u64;
                secp.commit(v, blind).unwrap()
            } else {
                v = -value as u64;
                if blind != ZERO_KEY {
                    blind = secp.blind_sum(vec![], vec![blind]).unwrap();
                }
                let commit = secp.commit(v, blind).unwrap();
                secp.commit_sum(vec![], vec![commit]).unwrap()
            }
        }

        let mut r1 = SecretKey([0;32]);
        let mut r2 = SecretKey([0;32]);
        let mut r3 = SecretKey([0;32]);

        r1.0[31] = 113;     // input
        r3.0[31] = 42;      // for change
        r2.0[31] = 113-42;  // total blinding factor from sender

        // split original r=28 into k1+k2
        let mut k1 = SecretKey([0;32]);
        let mut k2 = SecretKey([0;32]);
        k1.0[31] = 13;
        k2.0[31] = 15;

        let input = commit(3, r1);
        let output1 = commit(103, secp.blind_sum(vec![r2, k1, k2], vec![]).unwrap());
        let output2 = commit(-100, r3);
        let tmp = commit(103, secp.blind_sum(vec![r2, k1], vec![]).unwrap());

        // publish k1*G as excess and k2, instead of (k1+k2)*G
        // k component:
        //     (r2+k1+r3-r1)*G = (113-42+13+42-113)*G = 13*G
        //      ~~~~~ ~~ ~~       ~~~~~~~~~ ~~ ~~~
        // v component:
        //     (103+(-100)-3)*H = 0*H
        //
        let excess = secp.commit_sum(vec![tmp, output2], vec![input]).unwrap();

        println!("  input=113*G+3*H:\t{:?}\noutput1= 99*G+103*H:\t{:?}\noutput2= 42*G-100*H:\t{:?}",
                 input,
                 output1,
                 output2,
        );

        // sign it only with k1 instead of (k1+k2)

        let mut msg = [0u8; 32];
        thread_rng().fill_bytes(&mut msg);
        let msg = Message::from_slice(&msg).unwrap();

        let sig = secp.sign(&msg, &k1).unwrap();

        let pubkey = excess.to_pubkey(&secp).unwrap();

        println!("\n\tmsg:\t\t{:?}\n\texcess w/ k1*G:\t{:?}\n\tSignature:\t{:?}\n\tk2:\t\t{:?}",
                 msg,
                 excess,
                 sig,
                 k2,
        );

        // check that we can successfully verify the signature with the public key
        if let Ok(_) = secp.verify(&msg, &sig, &pubkey) {
            println!("Signature verify OK");
        } else {
            println!("Signature verify NOK");
        }

        if true==secp.verify_commit_sum(
            vec![output1, output2],
            vec![input, excess, commit(0, k2)],
        ){
            println!("\nsum with k2*G verify OK:\toutput1 + output2 = input + excess + k2*G");
        }else{
            println!("\nsum with k2*G verify NOK:\toutput1 + output2 != input + excess + k2*G");
        }
    }

And here is the demo executing command:

$ cargo test test_demo_fraud_transactions -- --nocapture

Explain

  • Look above transaction, because of pedersen commitment's good obscuring function, nobody can know this transaction is a fraud one: Alice only has 3 coins but send Bob 103 coins! and get a negative value -100 as the change output!
  • To avoid such kind of 3 = (-100) + 103 fraud transaction, the range proof is required.

More Interesting Demos

Now let's go to more detail about range proof.

1. A simple demo about creating a Range Proof

Firstly, a simple demo about how to create a range proof. Note: we only demo the Bullet Proof here since it has much smaller size than range proof.

Source Code (Click to expand) 

    #[test]
    fn test_demo_bullet_proof() {

        println!("Demo Bullet Proof without extra message data...\n");

        let secp = Secp256k1::with_caps(ContextFlag::Commit);
        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let commit = secp.commit(value, blinding).unwrap();
        let bullet_proof = secp.bullet_proof(value, blinding, blinding, None);

        println!("Value:\t\t{}\nBlinding:\t{:?}\nCommitment:\t{:?}\n\nBullet Proof:\t{:?}",
                 value,
                 blinding,
                 commit,
                 bullet_proof,
        );

        let proof_range = secp.verify_bullet_proof(commit, bullet_proof, None).unwrap();
        println!("\nVerification:\t{:#?}", proof_range);

        //-----

        println!("\nDemo Bullet Proof with extra message data...\n");

        let extra_data = [0u8;32].to_vec();
        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let commit = secp.commit(value, blinding).unwrap();
        let bullet_proof = secp.bullet_proof(value, blinding, blinding, Some(extra_data.clone()));

        println!("Value:\t\t{}\nBlinding:\t{:?}\nExtra data:\t{:?}\nCommitment:\t{:?}\n\nBullet Proof:\t{:?}",
                 value,
                 blinding,
                 (extra_data),
                 commit,
                 bullet_proof,
        );

        let proof_range = secp.verify_bullet_proof(commit, bullet_proof, Some(extra_data.clone())).unwrap();
        println!("\nVerification:\t{:#?}", proof_range);

        //-----

        println!("\nDemo rewinding. Extracts the value and blinding factor...\n");

        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let nonce = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let commit = secp.commit(value, blinding).unwrap();
        let bullet_proof = secp.bullet_proof(value, blinding, nonce, Some(extra_data.clone()));

        println!("Value:\t\t{}\nBlinding:\t{:?}\nExtra data:\t{:?}\nNonce:\t{:?}\nCommitment:\t{:?}\n\nBullet Proof:\t{:?}",
                 value,
                 blinding,
                 (extra_data),
                 nonce,
                 commit,
                 bullet_proof,
        );

        // Extracts the value and blinding factor from a single-commit rangeproof,
        // given a secret 'nonce'.
        //
        let proof_info = secp.rewind_bullet_proof(commit, nonce, Some(extra_data.clone()), bullet_proof).unwrap();
        println!("\nRewind_bullet_proof:\t{:#?}", proof_info);

        println!("Bullet Proof:\t{:?}",
                 bullet_proof,
        );

        let proof_range = secp.verify_bullet_proof(commit, bullet_proof, Some(extra_data.clone())).unwrap();
        println!("\nVerification:\t{:#?}", proof_range);

    }
Running result: 
$ cargo test test_demo_bullet_proof -- --nocapture

running 1 test
Demo Bullet Proof without extra message data...

Value:		12345678
Blinding:	SecretKey(8d83a0e1840c6363ffe93505bef9eac05b245e475cb280b154b95d96d358db29)
Commitment:	Commitment(085b019489a64283329829e045f41b84a37536ce35c6785427ae48de9601ab930c)

Bullet Proof:	RangeProof(5625ae48b9d57bff0d16d618d7d9a9fcf24b61a8cc6ed2175845c5df7f03ef43cc3cfe2a24d68785f9e
f38c545cac3848d7b0fee626f074b78b5b65d639843d30edd7b4f30ac8aafc41fc6c45d2c9f3ec4f447c212100fa5c4321c18a64b32e72
b146769afb15e3aa4ada12db6873e1f5f491f181b921bd1362c008285d742cde54026958c0db39921ae13daa6bb8251791353fca027388
51a29bd697b23e5b090e13b9320981c8c0d156cf0eb889285e27439466010dc62a3feac04f21af6e8b67ea53ab9ac909555a65045aab29
40bf392ec21d2632d970fab18690a1f0b1a9c6be9e3b4cec806ad2c7606df1385cace3127e40747bfb04d7ed81b2df5b5aa29160580d27
9c2b493af2f034d4d7473fafb91f34cf0d73d7f716eb43bef269fcbec3c8b6f50309a83ac5580d87c31b9426963cd77b46bea6baf7bbf0
be92341eb920d8679e6d705d1d08224b5cbc50a45e776e273cc68f5b257cdc4a0f7e165980201fa9d4dd3f98e3f3b17d1726e9d2a4b373
56d362b9232b95f9557d8102f3b0e954e1daa2e85e8edb13144b2b02844c14f38ac918e95de5592e350c1d0beae8d6ee231a1ba43261b3
9515b775ab1c47444e8bc4cd470a3d1acfda0a55471f4c3ae264ba438084d492175d1707be6bf021495a239bd21047e3d7379ef1c38fb4
5f1e3d5ebfe6bbc96f517d91dc3e4a1d87e3a86b6c6302206acf1c18e905768ca917b0abad775d98c1a8146825eefce5682789d85735a1
3604a4ac0b618726613c4901219868d1f104b8460279e6ca8ce9f02ec575f69c2e6bd68e9ec76019bf9b8a074bc5e1ab92db99c37dc300
f8983a3a390e0632739e7a576b6a1c5efad47f3c696febe4eeb035bc9154cbb604c8bb5a55314aca43283d4bbec56fe2066dc7301f5070
0f72b1d30898711591d37c044f920c3a5a494fe4492a547a9d6e01c82)[675]

Verification:	ProofRange {
    min: 0,
    max: 18446744073709551615
}

Demo Bullet Proof with extra message data...

Value:		12345678
Blinding:	SecretKey(ce01ba875aece831f2c4afe7c442ff3c58a4d416b79b2edfea1e1db656caf07f)
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(09b32ee1b16cfa00659207ac8c2f0c79f172588fc4b9b4b48f220a60f05767015d)

Bullet Proof:	RangeProof(eeda0aba9414f655bc0eecef7dadf2c819d9b24183f7b9b074c8df5ae8546118cff8779cdfa13b3f6cd
3a6bcfdd956048d5449edd02cde5fc2715dbbccaf902c0cf442768716fefe978a0542f3df2493bfbbae4a134e4024d68efb9e8a1f0428b
a150959486c30e2cd491771e2e3ed53120da4b5ea964c69c1de767f330e4b61de9d5e55caaea8a00c070816cfb1318d35959922f66048d
28e9aa46a45e032c240933736eff09c48bb21d7131b94ef97f0491e9fb1419ea76b995107a14495c8120dbdf495898d135a61830f16ef0
bcf6e824781de5809cd08fa3ca512685835d561b7ddfcb5f3ecac1abb0ab90c76edfb20c909c0c171cbd38f7dda048686379c852725f5f
7eb8928c1d39d39ec5f7890e5460c90371173fca88550216c68451ebbece1fd97477b5d2402b3359e13965fa47840f1d487df9dcdc8754
84f1183be13748559bef9d4e4edfbe72d927b7416805e6c0c76449a2db08e51f25503ba2d3e03615c2e45e1e6880328929e56d85d83957
70b10c72039679521328da10d1b50b90a8f63649f6567bf0a77a23824c9c0f544c462c0d9884255505cdfa4755e9b2afb66d94a5ee6b5a
1e7a06248ad938b15c4f4bb21029e5323a947ae460c0cac6c335b0935e23e32fdb0a67761332d4890f8f68ca0e529e8aca7d684bd435e5
c9bb59b9f7a4a29691c3f5cad14cfcf6b8d6935d5316173e8ee4a56cd3900783bbd5cb2ec2a6b3d95f95df99297ae3afd4c3f28c90f13d
6bb0d39603f45174c80ab55665b015ed14c6ec94ce6e4a2e22c318177da1c852c6563578721af5323493545895cebd3dce0035441af82e
986b8095997c09313af5a2b19cbb4ec4943b266e9cffb40103855c226744e413d75cba64d40393dc8cbd65f9d36648db9de77a45f01e66
e81897f67006ecb65539ca6ad7d83898127f61c522c43929445c08cb0)[675]

Verification:	ProofRange {
    min: 0,
    max: 18446744073709551615
}

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

Value:		12345678
Blinding:	SecretKey(db0b9a91256700e2f7d44ab1db154755f9c840d5bae7fcc30eda0d09dac029d7)
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]
Nonce:	SecretKey(ae9f6f0b2764368c1fbf610a355585b17d4f933e75a7b400455f5376c0b7409f)
Commitment:	Commitment(08632015092e65d14d4deb4b825631c8b6ef23b59dcb691f182ddff1864399caa8)

Bullet Proof:	RangeProof(c7b09d32f28087cb40480e03eb9936f0a7a65a365e3be23316a07346e41ebce2f2d39e31ae980d076af
52e37090016811993f437f0d27466e5f8e7613c3c0ce80d885d81f1d7a4d9474a358b577b65eccbae92936ddb8b88b6e71dc5f5e85e7e5
2f24b900b68f5088a041945f53e637ef01d08454ee786ff9fccc263eaefc31faec2d74fcc79e9d04c7136a4789a8397bdb762699fc4503
116e844fb7c1617d9b00959cd1bb00a3dd6f4a2b305440d05b041a53ce5069b637f83d0fc7f079169b56af0d9156e1c28a10ded538819b
9d84e5c43e9fe2788dc8def9cd1d4cddb7739f2adb467ec90728256c3fd6bb3a20dc04bd82237f09cad7e37ccfb91a3ab54b71cd0775b4
13afab97e32e4729bc21dadc2a81ef65fdfd6fe8eeef5b7e824af1c2db510a82dde4d475e6eca47f610c789e27b1643898902fea53baae
b7c461576a6a51022e235499a4127a34aed128fb91d95875d66277367c237ba292211d94214005b4650e40672eb937081fe6251097d4b5
a01e2cd59b55cfca886baafc564293ddfcbe65200c3e58a08385d038d94ca0d2a7a076eaaebaa591d77b74d1ca59e7d741bb3a55cdd01a
f41ea6082e9bd23fefd58403aa0aaff7d7652a7bd4b97c11609a7745742b2f0a3200f1f4083e1e851194836894ed30321808996d1cd724
64b7b897b4d4d2f5dd9677524760425a7da2eaaf172a5a62f674433f90a42ba4b5daf42491c356295850a50185012023fcc3b029c903a5
80e2d4ba6c1f6add65aafc183a9788a58a51313d7b4e9be0023a79b44f6ec2113409a44bd1fbcdab201f1ab1c4ddd2bb1d8867ee91f852
17da5402a9057b6042e7ec59c285a07411d2479a6ec3b0fc007abdd8479aea08b4aee6814d44bb3c56d9c277ba4e17fcc03f2c68c914f7
54bd8d56588972c2d3e265f7d4f1a225acb2bcdc2b34fd5dec7ae3fd8)[675]

Rewind_bullet_proof:	ProofInfo {
    success: true,
    value: 12345678,
    blinding: SecretKey(db0b9a91256700e2f7d44ab1db154755f9c840d5bae7fcc30eda0d09dac029d7),
    message: ProofMessage(),
    mlen: 0,
    min: 0,
    max: 18446744073709551615,
    exp: 0,
    mantissa: 0
}
Bullet Proof:	RangeProof(c7b09d32f28087cb40480e03eb9936f0a7a65a365e3be23316a07346e41ebce2f2d39e31ae980d0
76af52e37090016811993f437f0d27466e5f8e7613c3c0ce80d885d81f1d7a4d9474a358b577b65eccbae92936ddb8b88b6e71dc5f
5e85e7e52f24b900b68f5088a041945f53e637ef01d08454ee786ff9fccc263eaefc31faec2d74fcc79e9d04c7136a4789a8397bdb
762699fc4503116e844fb7c1617d9b00959cd1bb00a3dd6f4a2b305440d05b041a53ce5069b637f83d0fc7f079169b56af0d9156e1
c28a10ded538819b9d84e5c43e9fe2788dc8def9cd1d4cddb7739f2adb467ec90728256c3fd6bb3a20dc04bd82237f09cad7e37ccf
b91a3ab54b71cd0775b413afab97e32e4729bc21dadc2a81ef65fdfd6fe8eeef5b7e824af1c2db510a82dde4d475e6eca47f610c78
9e27b1643898902fea53baaeb7c461576a6a51022e235499a4127a34aed128fb91d95875d66277367c237ba292211d94214005b465
0e40672eb937081fe6251097d4b5a01e2cd59b55cfca886baafc564293ddfcbe65200c3e58a08385d038d94ca0d2a7a076eaaebaa5
91d77b74d1ca59e7d741bb3a55cdd01af41ea6082e9bd23fefd58403aa0aaff7d7652a7bd4b97c11609a7745742b2f0a3200f1f408
3e1e851194836894ed30321808996d1cd72464b7b897b4d4d2f5dd9677524760425a7da2eaaf172a5a62f674433f90a42ba4b5daf4
2491c356295850a50185012023fcc3b029c903a580e2d4ba6c1f6add65aafc183a9788a58a51313d7b4e9be0023a79b44f6ec21134
09a44bd1fbcdab201f1ab1c4ddd2bb1d8867ee91f85217da5402a9057b6042e7ec59c285a07411d2479a6ec3b0fc007abdd8479aea
08b4aee6814d44bb3c56d9c277ba4e17fcc03f2c68c914f754bd8d56588972c2d3e265f7d4f1a225acb2bcdc2b34fd5dec7ae3fd8)
[675]

Verification:	ProofRange {
    min: 0,
    max: 18446744073709551615
}

2. Performance Issue of Range Proof

Both the range proof creation and verification are heavy computation. Let's have a bench test to demo this:

Source Code (Click to expand) 

    #[test]
    fn bench_bullet_proof_wt_extra() {
        const BP_LENGTH: usize = 1_000;

        let secp = Secp256k1::with_caps(ContextFlag::Commit);
        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let commit = secp.commit(value, blinding).unwrap();

        let mut now = SystemTime::now();
        let mut bullet_proof = secp.bullet_proof(value, blinding, blinding, None);

        for _ in 1..BP_LENGTH+1 {
            bullet_proof = secp.bullet_proof(value, blinding, blinding, None);
        }

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} bullet proof)", used_time, BP_LENGTH);
        }

        now = SystemTime::now();
        let mut ok_count = 0;
        for _ in 1..BP_LENGTH+1 {
            let proof_range = secp.verify_bullet_proof(commit, bullet_proof, None).unwrap();
            if proof_range.min==0{
                ok_count += 1;
            }
        }
        println!("verify_bullet_proof ok:\t{}/{}", ok_count, BP_LENGTH);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} verify bullet proof)", used_time, BP_LENGTH);
        }
    }


    #[test]
    fn bench_bullet_proof_with_extra_msg() {
        const BP_LENGTH: usize = 1_000;

        let extra_data = [0u8;64].to_vec();

        let secp = Secp256k1::with_caps(ContextFlag::Commit);
        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let commit = secp.commit(value, blinding).unwrap();

        let mut now = SystemTime::now();
        let mut bullet_proof = secp.bullet_proof(value, blinding, blinding, Some(extra_data.clone()));

        for _ in 1..BP_LENGTH+1 {
            bullet_proof = secp.bullet_proof(value, blinding, blinding, Some(extra_data.clone()));
        }

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} bullet proof with extra msg)", used_time, BP_LENGTH);
        }

        now = SystemTime::now();
        let mut ok_count = 0;
        for _ in 1..BP_LENGTH+1 {
            let proof_range = secp.verify_bullet_proof(commit, bullet_proof, Some(extra_data.clone())).unwrap();
            if proof_range.min==0{
                ok_count += 1;
            }
        }
        println!("verify_bullet_proof ok:\t{}/{}", ok_count, BP_LENGTH);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            println!("spent time:\t{}(s)/({} verify bullet proof with extra msg)", used_time, BP_LENGTH);
        }
    }

Running result:

$ cargo test --release bench_bullet_proof_wt_extra -- --nocapture

running 1 test
test bench::tests::bench_bullet_proof_wt_extra ...
spent time:	81(s)/(1000 bullet proof)
verify_bullet_proof ok:	1000/1000
spent time:	40(s)/(1000 verify bullet proof)

$ cargo test --release bench_bullet_proof_with_extra_msg -- --nocapture

running 1 test
test bench::tests::bench_bullet_proof_with_extra_msg ... test bench::tests::bench_bullet_proof_with_extra_msg has been running for over 60 seconds
spent time:	80(s)/(1000 bullet proof with extra msg)
verify_bullet_proof ok:	1000/1000
spent time:	41(s)/(1000 verify bullet proof with extra msg)

From above test results, it need average 40ms for a verification and 80ms for a creation, on a MacBook Air (Early 2015). As a compare, the ECDSA signature spent average 0.14ms for a signature and 0.17ms for a signature verification, on same computer.

That's a little bit higher than expectation! In case of 50 millions of UTXO, that need about 23 days to complete all the range proof verification, on my poor old MacBook Air; suppose a brand new computer is as 5 times faster as mine, that still need 4.6 days!

So, in my view, the current range proof implementation is one of most important bottlenecks for those chains which adopt this range proof scheme.

At least, a multiple threads optimization should be used for range proof verification.

Basics

Researches

Clone this wiki locally