Transaction Aggregation - garyyu/rust-secp256k1-zkp GitHub Wiki

Transaction Aggregation, or Combination, is the idea of Mimblewimble protocol. To quote the original here:

Now, creating transactions in this manner supports OWAS already. To show this, suppose we have two transactions that have a surplus k1*G and k2*G, and the attached signatures with these. Then you can combine the lists of inputs and outputs of the two transactions, with both k1*G and k2*G to the mix, and voilá! is again a valid transaction. From the combination, it is impossible to say which outputs or inputs are from which original transaction.

Let's continue using the example in Confidential Transaction third demo and taking into account the Kernel Offset of "Subset-Sum" Problem.

Suppose we have 2 transactions. And for 1st transaction, it's the 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, see detail in "Subset-Sum" Problem).
    • signature (with private key: 13, i.e. k1 see detail in "Subset-Sum" Problem).
  • offset: 15, i.e. k2. Note: k=k1+k2=28.

For 2nd transaction, suppose a case that Carol spend 10 coins to send David 6 coins and get 4 coins change. In this transaction, we have:

  • 1 input commitment: 205*G+10*H, the original UTXO of Carol, used in this transaction as the _input.
  • 2 output commitments: 68*G+4*H (the change of Carol), and 216*G+6*H (the output for David).
  • 1 transaction kernel, which include 3 parts:
    • msg (a random number in this example).
    • excess (55G, i.e. k1G, after splitting the key k = k1 + k2).
    • signature (with private key: 55, i.e. k1).
  • offset: 24, i.e. k2. Note: k=k1+k2=79.

Now, according to combination idea of Mimblewimble protocol, we will mix all these and check if the "combined one" is still a valid 'transaction' (two transactions are combined as one Aggregated Transaction!)

Run Code to Check

Let's check details by run the following Rust test step by step.

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_aggregate_transactions() {
        let secp = Secp256k1::with_caps(ContextFlag::Commit);

        fn commit(value: u64, blinding: SecretKey) -> Commitment {
            let secp = Secp256k1::with_caps(ContextFlag::Commit);
            secp.commit(value, blinding).unwrap()
        }

        //------	transaction 1		-----//

        println!("\nFirst transaction...\n");

        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(2, secp.blind_sum(vec![r2, k1, k2], vec![]).unwrap());
        let output2 = commit(1, r3);
        let tmp = commit(2, secp.blind_sum(vec![r2, k1], vec![]).unwrap());

        // publish k1*G as excess and k2, instead of (k1+k2)*G
        let excess = secp.commit_sum(vec![tmp, output2], vec![input]).unwrap();

        println!("  input=113*G+3*H:\t{:?}\noutput1= 99*G+2*H:\t{:?}\noutput2= 42*G+1*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],
        ){
            println!("\n\"subset sum\" verify OK:\toutput1+output2 = input+excess");
        }else{
            println!("\n\"subset sum\" verify NOK:\toutput1+output2 != input+excess");
        }

        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");
        }

        //------	transaction 2		-----//

        println!("\nSecond transaction...\n");

        let mut new_r1 = SecretKey([0;32]);
        let mut new_r2 = SecretKey([0;32]);
        let mut new_r3 = SecretKey([0;32]);

        new_r1.0[31] = 205;     // input
        new_r3.0[31] = 68;      // for change
        new_r2.0[31] = 205-68;  // total blinding factor from sender

        // split original r=79 into k1+k2
        let mut new_k1 = SecretKey([0;32]);
        let mut new_k2 = SecretKey([0;32]);
        new_k1.0[31] = 55;
        new_k2.0[31] = 24;

        let new_input = commit(10, new_r1);
        let new_output1 = commit(6, secp.blind_sum(vec![new_r2, new_k1, new_k2], vec![]).unwrap());
        let new_output2 = commit(4, new_r3);
        let new_tmp = commit(6, secp.blind_sum(vec![new_r2, new_k1], vec![]).unwrap());

        // publish k1*G as excess and k2, instead of (k1+k2)*G
        let new_excess = secp.commit_sum(vec![new_tmp, new_output2], vec![new_input]).unwrap();

        println!("  input=205*G+10*H:\t{:?}\noutput1= 216*G+6*H:\t{:?}\noutput2= 68*G+4*H:\t{:?}",
                 new_input,
                 new_output1,
                 new_output2,
        );

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

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

        let new_sig = secp.sign(&new_msg, &new_k1).unwrap();

        let new_pubkey = new_excess.to_pubkey(&secp).unwrap();

        println!("\n\tmsg:\t\t{:?}\n\texcess w/ k1*G:\t{:?}\n\tSignature:\t{:?}\n\tk2:\t\t{:?}",
                 new_msg,
                 new_excess,
                 new_sig,
                 new_k2,
        );

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

        if true==secp.verify_commit_sum(
            vec![new_output1, new_output2],
            vec![new_input, new_excess],
        ){
            println!("\n\"subset sum\" verify OK:\toutput1+output2 = input+excess");
        }else{
            println!("\n\"subset sum\" verify NOK:\toutput1+output2 != input+excess");
        }

        if true==secp.verify_commit_sum(
            vec![new_output1, new_output2],
            vec![new_input, new_excess, commit(0, new_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");
        }

        //------	aggregate transactions		-----//

        println!("\naggregate these 2 transactions...\n");

        println!(" input1=113*G+3*H:\t{:?}\n input2=205*G+10*H:\t{:?}\noutput1= 99*G+2*H:\t{:?}\noutput2= 42*G+1*H:\t{:?}",
                 input,
                 new_input,
                 output1,
                 output2,
        );
        println!("output3= 216*G+6*H:\t{:?}\noutput4= 68*G+4*H:\t{:?}",
                 new_output1,
                 new_output2,
        );
        println!("\n\tmsg1:\t\t{:?}\n\texcess1:\t{:?}\n\tSignature1:\t{:?}",
                 msg,
                 excess,
                 sig,
        );
        println!("\n\tmsg2:\t\t{:?}\n\texcess2:\t{:?}\n\tSignature1:\t{:?}\n\n\tsum(k2):\t{:?}",
                 new_msg,
                 new_excess,
                 new_sig,
                 secp.blind_sum(vec![k2, new_k2], vec![]).unwrap(),
        );

        // now let's check this "aggregated transaction":

        if true==secp.verify_commit_sum(
            vec![output1, output2, new_output1, new_output2],
            vec![input, new_input, excess, new_excess,
                 commit(0, secp.blind_sum(vec![k2, new_k2], vec![]).unwrap())],
        ){
            println!("\ntotal sum balance verify OK:\toutput1 + output2 + output3 + output4 = input1 + input2 + excess1 + excess2 + sum(k2)*G");
        }else{
            println!("\ntotal sum balance verify NOK:\toutput1 + output2 + output3 + output4 = input1 + input2 + excess1 + excess2 + sum(k2)*G");
        }
    }

And here is the running result:

$ cargo test test_demo_aggregate_transactions -- --nocapture

running 1 test

First transaction...

  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)
Signature verify OK

"subset sum" verify NOK:	output1+output2 != input+excess

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

Second transaction...

  input=205*G+10*H:	Commitment(0877002121931aabc3292b8e9393023f08ab00c7d5fdd47572da39c5e226928125)
output1= 216*G+6*H:	Commitment(08d9acf8d6d6ef15d62cd389c956d91c46599de6ec7764ee31c9ba121e42326815)
output2= 68*G+4*H:	Commitment(092b84cd39df4ca9a270c4a12363db74e89ff61566e7cedf26fb98fd2570e1e261)

	msg:		Message(2e2b2c3fae2ba16dcf72835544139831783bf8705c7e5d705b8405696e8750dd)
	excess w/ k1*G:	Commitment(09caf754272dc84563b0352b7a14311af55d245315ace27c65369e15f7151d41d1)
	Signature:	Signature(aba17806e85372cf375edcce298ada9adff43c61f73bb8dfbb74e9c95894288760283da534b44be0d0edb1cd8151165ffadf38ae269da86a661e1acfe0e4927e)
	k2:		SecretKey(0000000000000000000000000000000000000000000000000000000000000018)
Signature verify OK

"subset sum" verify NOK:	output1+output2 != input+excess

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

aggregate these 2 transactions...

 input1=113*G+3*H:	Commitment(0955e54cd28baa1416c1f795f6ddba1c2d1f760c9d9b515360ef944babe3eea352)
 input2=205*G+10*H:	Commitment(0877002121931aabc3292b8e9393023f08ab00c7d5fdd47572da39c5e226928125)
output1= 99*G+2*H:	Commitment(0878992a66a47907eefad338908cd0a44941aa4219706a2c9d0de2fa0559863eaa)
output2= 42*G+1*H:	Commitment(091c1f29a819b7d3fde56f425692e9cb9a6682ae412a1a1019b3261da6439371e6)
output3= 216*G+6*H:	Commitment(08d9acf8d6d6ef15d62cd389c956d91c46599de6ec7764ee31c9ba121e42326815)
output4= 68*G+4*H:	Commitment(092b84cd39df4ca9a270c4a12363db74e89ff61566e7cedf26fb98fd2570e1e261)

	msg1:		Message(d851581d434b9f2718b89f3441b13062e651cdbc4752e99767b706d640ede882)
	excess1:	Commitment(09f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8)
	Signature1:	Signature(91bb7da507b3c8b67b0e47e35f1406b5b92381a8edba6b5f9755f79f0555d848bb0b333aa0f6dd67d5fb414620c2d3da74f5f9dce409726b4a89c9ad953ec10e)

	msg2:		Message(2e2b2c3fae2ba16dcf72835544139831783bf8705c7e5d705b8405696e8750dd)
	excess2:	Commitment(09caf754272dc84563b0352b7a14311af55d245315ace27c65369e15f7151d41d1)
	Signature1:	Signature(aba17806e85372cf375edcce298ada9adff43c61f73bb8dfbb74e9c95894288760283da534b44be0d0edb1cd8151165ffadf38ae269da86a661e1acfe0e4927e)

	sum(k2):	SecretKey(0000000000000000000000000000000000000000000000000000000000000027)

total sum balance verify OK:	output1 + output2 + output3 + output4 = input1 + input2 + excess1 + excess2 + sum(k2)*G

As you see on the last line of above demo result, eventually this "aggregated transaction" has 2 inputs, 4 outputs, 2 excess, and 2 messages + 2 signature, and last one: 1 sum(k2). And this aggregated transaction total sum balance is OK, that means, it's still ONE valid transaction.

Next page we will come to transaction cut-through topic.

⚠️ **GitHub.com Fallback** ⚠️