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

Range Proof

Jump to bottom
Gary Yu edited this page Apr 28, 2019 · 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.

The original paper "Bulletproofs: Short Proofs for Confidential Transactions and More" is here.

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 --recursive 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(5625ae48b9d57bff...)[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(eeda0aba9414f655...)[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(c7b09d32f28087cb...)[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(c7b09d32f28087cb...)[675]

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

2. Performance Test of Single 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!

That's why a Batch Verification is needed! According to this announcement at Feb 21, 2018 by Andrew Poelstra:

Note that we have introduced two similar but separate concepts: aggregation is when a prover combines multiple rangeproofs into one, while batching is when a verifier checks multiple separate proofs at once.

This means that two 64-bit rangeproofs can be validated in under 2.7 ms, or 1.3 ms per range. A thousand rangeproofs can be validated in 239 ms, or 0.24 ms per range, which is a 23x improvement over the old proofs. But it still gets better, because of aggregation. A thousand 8-fold aggregates (so 8000 ranges total) can be validated in 588 ms, or 74 microseconds per range, or a 78x improvement over the old rangeproofs.

3. Batch Verification of Range Proof

Let's have a bench test to demo this batch verification:

Source Code (Click to expand) 

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

        let mut commits:Vec<Commitment> = vec![];
        let mut proofs:Vec<RangeProof> = vec![];

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

        let mut now = SystemTime::now();

        for i in 1..BP_LENGTH+1 {
            commits.push(secp.commit(value + i as u64, blinding).unwrap());
            proofs.push(secp.bullet_proof(value + i as u64, blinding, blinding, None));
        }

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

        now = SystemTime::now();
        let proof_range = secp.verify_bullet_proof_multi(commits, proofs, None);
        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            let used_time_subsec_millis = elapsed.subsec_millis();
            println!("spent time:\t{}.{:0<3}(s)/(1 batch verify for {} bullet proofs)",
                     used_time, used_time_subsec_millis, BP_LENGTH);
        }
        println!("\nproof_range:\t{:#x?}", proof_range.unwrap());
    }

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

        let mut commits:Vec<Commitment> = vec![];
        let mut proofs:Vec<RangeProof> = vec![];
        let mut extra_data_vec = vec![];

        let secp = Secp256k1::with_caps(ContextFlag::Commit);
        let blinding = SecretKey::new(&secp, &mut OsRng::new().unwrap());
        let value = 12345678;
        let mut extra_data = [0u8;64];
        thread_rng().fill_bytes(&mut extra_data);

        let mut now = SystemTime::now();

        for i in 1..BP_LENGTH+1 {
            commits.push(secp.commit(value + i as u64, blinding).unwrap());
            extra_data_vec.push(extra_data.to_vec().clone());

            proofs.push(secp.bullet_proof(
                value + i as u64,
                blinding,
                blinding,
                Some(extra_data.to_vec().clone())));
        }

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            let used_time_subsec_millis = elapsed.subsec_millis();
            println!("spent time:\t{}.{:0<3}(s)/({} bullet proof creation w/ extra data)",
                     used_time, used_time_subsec_millis, BP_LENGTH);
        }

        now = SystemTime::now();
        let proof_range = secp.verify_bullet_proof_multi(
            commits,
            proofs,
            Some(extra_data_vec.clone()));

        if let Ok(elapsed) = now.elapsed() {
            let used_time = elapsed.as_secs();
            let used_time_subsec_millis = elapsed.subsec_millis();
            println!("spent time:\t{}.{:0<3}(s)/(1 batch verify for {} bullet proofs w/ extra data)",
                     used_time, used_time_subsec_millis, BP_LENGTH);
        }
        println!("\nproof_range:\t{:#x?}", proof_range.unwrap());
    }

Running result:

$ cargo test --release bench_bulletproof_batch_verify -- --nocapture

running 1 test
test bench::tests::bench_bulletproof_batch_verify ...
spent time:	81.144(s)/(1000 bullet proof creation w/t extra message)
spent time:	0.844(s)/(1 batch verify for 1000 bullet proofs w/t extra message)

proof_range:	ProofRange {
    min: 0x0,
    max: 0xffffffffffffffff
}
test bench::tests::bench_bulletproof_batch_verify ... ok

$ cargo test --release bench_bulletproof_with_extra_batch_verify -- --nocapture

running 1 test
test bench::tests::bench_bulletproof_with_extra_batch_verify ... test bench::tests::bench_bulletproof_with_extra_batch_verify has been running for over 60 seconds
spent time:	82.608(s)/(1000 bullet proof creation w/ extra data)
spent time:	0.816(s)/(1 batch verify for 1000 bullet proofs w/ extra data)

proof_range:	ProofRange {
    min: 0x0,
    max: 0xffffffffffffffff
}
test bench::tests::bench_bulletproof_with_extra_batch_verify ... ok

The 1st bench test is for batch verification on 1000 range proof without extra message data; and 2nd bench test is almost same but with 64 bytes extra message data in each range proof.

Based on this bench test demo result, we can say the batch verification performance is amazing! From 40ms to 0.8ms, that's near 50 times faster than the single verification!

4. Range Proof Aggregation

Note that there're two similar but separate concepts: aggregation is when a prover combines multiple rangeproofs into one, while batching is when a verifier checks multiple separate proofs at once.

Aggregation can help in 2 aspects: smaller average size of rangeproof per-commitment, and of course faster average verification time.

Source Code (Click to expand)

https://github.com/garyyu/rust-secp256k1-zkp/blob/master/src/demo.rs#L936-L959

Running result: 
$ cargo test --release test_demo_aggregated_bullet_proof  -- --nocapture

running 1 test
Demo Bullet Proof Aggregation w/o extra message data...

Values:		[
    12345678,
    87654321
]
Blinds:	[
    SecretKey(c284a256a7b86f2caa86fc3fecf075a0bbcf4865fe2180533554f342d5c45257),
    SecretKey(5d41b9840022925a979af89d0c5109f89e1e20751733fbd1b0ed700971e87e5f)
]
Commits:	[
    Commitment(0992bc124b4e6697e17994d135bf0412d2e47e15ceb361191c6c502771466cf0ff),
    Commitment(0936dcf255cf139713b9bc485fbd590a3e1a81c3f0a8d91df4317d93c32f234fb6)
]

Bullet Proof:	RangeProof(c71f8f3bc1541548b66dc26b27209a53500b4f96e17df93d4d7f8553...)[739]

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

Basics

Researches

Clone this wiki locally