"Subset Sum" Problem - garyyu/rust-secp256k1-zkp GitHub Wiki
As pointed by andytoshi here about a minor mistake in Mimblewimple Paper:
I think Voldemort made a minor mistake here -- it's possible to unlink transactions because the original transactions' commitments sum to these "excess" kG, which get included in the block unchanged. If someone can find subsets of inputs and outputs that sum to the original kG values, they can successfully untangle the transactions. (This is the "subset sum" problem, which is NP hard, so maybe it'll take some grinding, but for small transactions it's probably doable.)
There's an easy fix, add a second explicit k' value, construct transactions so that the excess is (k + k')G, and when merging transactions people can directly sum all the k' values. After this summing the transactions really are inseparable.
Posting this here so hopefully it doesn't get lost. :) Not sure where errata should go for an anonymously posted paper.
Now let's do a demo how to split the excess into (k1+k2)G
. If you're new to Confidential Transaction, please read it before this.
As andytoshi proposed, a simple fix solution is: publish k1*G
and k2
, sign with k1*G
but make the transaction excess be (k1 + k2)*G
, and when combining transactions all the k2
just get added together.
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
Suppose there is a transaction that Alice has 3 coins and give Bob 2 coins and get 1 coin as change. For example:
-
113*G+3*H
is the input commitment of this transaction, which was the UTXO(Unspent Transaction Output) of Alice before this transaction, so Alice know privacy informations of this commitment:r=113
andv=3
. -
42*G+1*H
is the change output commitment, since in this example Alice only send Bob 2 coins and has 1 coin change return in this transaction. -
71
is the simple arithmetic result from113-42=71
, only Alice know these two values (113
and42
). To create this transaction, Alice must tell Bob this total blinding factor71
: r-value of change minus r-values of inputs. -
99*G+2*H
is the output commitment of Bob, this commitment becomes Bob's UTXO and Bob is the only owner of this UTXO. The value99
is the simple arithmetic result from71+28=99
, and71
is known for Bob just because Alice tell him,28
is Bob chosen private key and Bob himself surely know it.
(The following steps are different parts from Confidential Transaction third demo)
- For solving "Subset-Sum" problem, Bob split his private key 28 into 2 part:
k1=13
andk2=15
. - When Bob do the signature, he use k1(
13
) as private key instead of k1+k2(28
). - Instead of using
28*G
as the excess to publish together with the signature and message, Bob usek1*G
(i.e.13*G
) as the excess. - Finally, in published Transaction Kernel, there're 3 parts:
- message (same as third demo)
- excess (
13*G
, i.e.k1*G
) - signature (by private key
13
)
- Input commitment and outputs commitment are same as third demo.
Source Code (Click to expand)
#[test]
fn test_pedersen_subset_sum_problem_fix() {
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()
}
let mut r1 = SecretKey([0;32]);
let mut r2 = SecretKey([0;32]);
let mut r3 = SecretKey([0;32]);
let mut r4 = SecretKey([0;32]);
r1.0[31] = 113;
r2.0[31] = 71;
r3.0[31] = 42;
r4.0[31] = 28;
let input = commit(3, r1);
let output1 = commit(2, secp.blind_sum(vec![r2, r4], vec![]).unwrap());
let output2 = commit(1, r3);
let excess = secp.commit_sum(vec![output1, 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
let mut msg = [0u8; 32];
thread_rng().fill_bytes(&mut msg);
let msg = Message::from_slice(&msg).unwrap();
let sig = secp.sign(&msg, &r4).unwrap();
let pubkey = excess.to_pubkey(&secp).unwrap();
println!("\n\tmsg:\t\t{:?}\n\texcess:\t\t{:?}\n\tSignature:\t{:?}",
msg,
excess,
sig,
);
// 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");
}
//------ "Subset Sum" problem fixing -----//
println!("\n\"Subset Sum\" Problem Fixing...");
// 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 new_output1 = commit(2, secp.blind_sum(vec![r2, k1, k2], vec![]).unwrap());
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 new_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,
new_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 new_sig = secp.sign(&msg, &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{:?}",
msg,
new_excess,
new_sig,
k2,
);
// check that we can successfully verify the signature with the public key
if let Ok(_) = secp.verify(&msg, &new_sig, &new_pubkey) {
println!("Signature verify OK");
} else {
println!("Signature verify NOK");
}
if true==secp.verify_commit_sum(
vec![new_output1, output2],
vec![input, new_excess],
){
println!("\n\"subset sum\" verify OK:\toutput1+output2 = input+excess");
}else{
println!("\n\"subset sum\" verify NOK:\toutput1+output2 != input+excess");
}
}
And here is the running result:
$ cargo test test_pedersen_subset_sum_problem_fix -- --nocapture
running 1 test
input=113*G+3*H: Commitment(0955e54cd28baa1416c1f795f6ddba1c2d1f760c9d9b515360ef944babe3eea352)
output1= 99*G+2*H: Commitment(0878992a66a47907eefad338908cd0a44941aa4219706a2c9d0de2fa0559863eaa)
output2= 42*G+1*H: Commitment(091c1f29a819b7d3fde56f425692e9cb9a6682ae412a1a1019b3261da6439371e6)
msg: Message(4b188aa0721dc561c5c4ab65af687aaea12fc3f047c631c242d5141d72b36215)
excess: Commitment(0955eb67d7b7238a70a7fa6f64d5dc3c826b31536da6eb344dc39a66f904f97968)
Signature: Signature(fc22fa177634dc324efbd8613421f8b96c04d8e8bda34fffd71104f5ae98ccecd24bdab521d9069edb6d0f74e7cf9eebbc1811742dca6970f39f90b999da1f5f)
Signature verify OK
"subset sum" verify OK: output1+output2 = input+excess
"Subset Sum" Problem Fixing...
input=113*G+3*H: Commitment(0955e54cd28baa1416c1f795f6ddba1c2d1f760c9d9b515360ef944babe3eea352)
output1= 99*G+2*H: Commitment(0878992a66a47907eefad338908cd0a44941aa4219706a2c9d0de2fa0559863eaa)
output2= 42*G+1*H: Commitment(091c1f29a819b7d3fde56f425692e9cb9a6682ae412a1a1019b3261da6439371e6)
msg: Message(38f2795140828f849c51cc0e6db5e1cc3f1caa2eb4811b853e92b675a413de2a)
excess w/ k1*G: Commitment(09f28773c2d975288bc7d1d205c3748651b075fbc6610e58cddeeddf8f19405aa8)
Signature: Signature(14420981bdb46c30dae11fc4db7e7c8f2b097500ad944a78c528bbe8d5bf1fa0f9f2961d386b050a73121a4b49c7d4db19a4fbb3a2b856c9835caed7e0b3b521)
k2: SecretKey(000000000000000000000000000000000000000000000000000000000000000f)
Signature verify OK
"subset sum" verify NOK: output1+output2 != input+excess
As you see on the last line of above demo result, eventually when these inputs, outputs and excess are included into a block, "Subset Sum" will always fail because excess published is k1*G
instead of (k1+k2)*G
. So, "Subset Sum" problem fixed.
Note:
- The consequent impact is: a new field
k2
has to be included in the transaction data. In Grin project, this is the first data element of Grin Transaction data structure, but with nameoffset
instead ofk2
. - Generally, Grin project(1st Mimblewimble protocol implementation) use exact same fix solution as described here, but with a special name
Kernel Offset
, you can read the detail here.
Now we will go to Transaction Aggregation topic in next page.