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 5, 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.

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
}

Basics

Researches

Clone this wiki locally