Pedersen Commitment - garyyu/rust-secp256k1-zkp GitHub Wiki
A Pedersen Commitment can be expressed as:
r*G + v*H
Where:
-
r is a private key used as a blinding factor, G is an Elliptic Curve (in the remaining part, we will use abbreviation EC for it) and their product
r*G
is the public key for r on G. - v is the value of an input or output and H is another EC.
Neither v nor r can be deduced, leveraging the fundamental properties of EC Cryptography.
In the confidential transaction design, any value in a transaction will be expressed as a Pedersen Commitment, to obscure the values of the transaction, and then nobody can deduce the real values from the public chain database (i.e Blockchain).
Because of r
's nice function to obscure the v
of the transaction, r
get a nice term name blinding factor.
Let's take a look at what's the exact value of G and H in Pedersen Commitment formula (in this rust-secp256k1-zkp library context):
-
G definition:
- In (X,Y) coordinates form as reference code here:
- X: 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
- Y: 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
- In compressed form as reference code here:
- 0a 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
- In (X,Y) coordinates form as reference code here:
-
H definition:
- In compressed form as reference code here:
- 0b 50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0
- In compressed form as reference code here:
Note:
-
If no special note, the showed hexadecimal serialization in this wiki always in Little Endian format, i.e. Most Significant Byte is showed on left (first).
-
An EC defined as follows:
- {(x,y)∈ℝ^2 | y^2=x^3+ax+b, 4a^3+27b^2≠0} ∪ {0}
- We denote our point at infinity with the symbol 0 (zero). So a point in EC has (X,Y) coordinates, that's why we see GENERATOR_X and GENERATOR_Y in above links, which are X and Y coordinate of the generator G.
-
According to Bitcoin WiKi, above EC base point G is same as Bitcoin.
-
About compressed form of EC point. The EC point (X, Y) serialization is 04+X+Y as uncompressed, and (02+X as compressed if Y is even), and (03+X as compressed if Y is odd). But, wait, why above links show the compressed form of G and H has 0x0a and 0x0b as first byte? instead of 0x02 or 0x03.
Answer to above question:
- For
G
, refer to the source code - For
H
, refer to the source code - There's no direct mapping between
02/03
and the0a/0b
in secp256k1-zkp lib. If Y is Quadratic Residue, it will return8
, because9 ^ 1 = 8
; if commitment's 1st byte is odd (i.e. 9), EC point negation. Quadratic residue is a different concept from Y odd/even. For detail about quadratic residue, you can find it in BIP-Schnorr. I pick a short desciption here:
A product of two numbers is a quadratic residue when either both or none of the factors are quadratic residues. As -1 is not a quadratic residue, and the two Y coordinates corresponding to a given X coordinate are each other's negation, this means exactly one of the two must be a quadratic residue.
H is an alternate secp256k1 generator, used in Elements Alpha. It's computed as the hash of the above G, DER-encoded with 0x04 (uncompressed pubkey) as its flag byte.
G_bytes = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'
H = C.lift_x(int(hashlib.sha256(G_bytes).hexdigest(),16))
To check it:
$ echo "0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8" | xxd -r -p > G.bin
$ openssl dgst -sha256 G.bin
SHA256(G.bin)= 50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0
Let's check it by run a Rust test:
$ git clone --recursive https://github.com/garyyu/rust-secp256k1-zkp.git
$ cd rust-secp256k1-zkp
$ cargo test test_show_g_and_h -- --nocapture
Source Code (Click to expand)
#[test]
fn test_show_g_and_h() {
println!("G in (X,Y) coordinates form:\n\tX={:02x?}\n\tY={:02x?}\n\nG in compressed form:\n\t{:02x?}\n\nH in compressed form:\n\t{:02x?}",
SecretKey(constants::GENERATOR_X),
SecretKey(constants::GENERATOR_Y),
Commitment(constants::GENERATOR_G),
Commitment(constants::GENERATOR_H),
);
}
running 1 test
G in (X,Y) coordinates form:
X=SecretKey(79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
Y=SecretKey(483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)
G in compressed form:
Commitment(0a79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
H in compressed form:
Commitment(0b50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)
Now, let's do some more interesting demos.
What will Pedersen Commitment r*G + v*H
look like if r=0 and v=1,2,3...?
Source Code (Click to expand)
#[test]
fn test_pedersen_zero_r() {
fn commit(value: u64) -> Commitment {
let secp = Secp256k1::with_caps(ContextFlag::Commit);
let blinding = ZERO_KEY;
secp.commit(value, blinding).unwrap()
}
println!("0*G+1*H:\t{:?}\n0*G+2*H:\t{:?}\n0*G+3*H:\t{:?}",
commit(1),
commit(2),
commit(3),
);
}
$ cargo test test_pedersen_zero_r -- --nocapture
running 1 test
0*G+1*H: Commitment(0950929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)
0*G+2*H: Commitment(08fad265e0a0178418d006e247204bcf42edb6b92188074c9134704c8686eed37a)
0*G+3*H: Commitment(085ef47fcde840a435e831bbb711d466fc1ee160da3e15437c6c469a3a40daacaa)
But, again, why above commitment show the compressed form of EC point has 0x08 and 0x9b as first byte? instead of 0x02 or 0x03.
Answer to above question:
- Refer to the source code, 9 (hex
0x09
) represent Y is even, and 8 (hex0x08
) represent Y is odd. That's just a hardcoded definition in this secp256k1-zkp lib.
And then, What will Pedersen Commitment r*G + v*H
look like if v=0 and r=1,2,3...?
Source Code (Click to expand)
#[test]
fn test_pedersen_zero_v() {
fn commit(blinding: SecretKey) -> Commitment {
let secp = Secp256k1::with_caps(ContextFlag::Commit);
secp.commit(0, blinding).unwrap()
}
let mut r1 = SecretKey([0;32]);
let mut r2 = SecretKey([0;32]);
let mut r3 = SecretKey([0;32]);
r1.0[31] = 1;
r2.0[31] = 2;
r3.0[31] = 3;
println!("1*G+0*H:\t{:?}\n2*G+0*H:\t{:?}\n3*G+0*H:\t{:?}",
commit(r1),
commit(r2),
commit(r3),
);
}
$ cargo test test_pedersen_zero_v -- --nocapture
running 1 test
1*G+0*H: Commitment(0879be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
2*G+0*H: Commitment(08c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5)
3*G+0*H: Commitment(09f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9)
What will Pedersen Commitment r*G + v*H
look like if r=0 and v<0? And what's the result of 1*G-5*H
+ 0*G+5*H
? Does their sum equal 1*G+0*H
?
Source Code (Click to expand)
#[test]
fn test_pedersen_zero_neg_v() {
let secp = Secp256k1::with_caps(ContextFlag::Commit);
fn commit(value: i64, one_or_zero_key: bool) -> Commitment {
let secp = Secp256k1::with_caps(ContextFlag::Commit);
let mut blinding = ZERO_KEY;
if one_or_zero_key {
blinding = ONE_KEY;
}
let v :u64;
if value >= 0{
v = value as u64;
secp.commit(v, blinding).unwrap()
}else{
v = -value as u64;
if blinding != ZERO_KEY {
blinding = secp.blind_sum(vec![], vec![blinding]).unwrap();
}
let commit = secp.commit(v, blinding).unwrap();
secp.commit_sum(vec![], vec![commit]).unwrap()
}
}
let commit_1 = commit(-5, false);
let commit_2 = commit(5, false);
println!("0*G-5*H:\t{:?}\n0*G+5*H:\t{:?}\n-(0*G-5*H):\t{:?}",
commit_1,
commit_2,
secp.commit_sum(vec![], vec![commit_1]).unwrap(),
);
println!("\n");
let commit_3 = commit(-5, true);
let commit_4 = commit(5, false);
let commit_5 = commit(0, true);
println!("1*G-5*H:\t{:?}\n0*G+5*H:\t{:?}\n1*G+0*H:\t{:?}\nsum first 2:\t{:?}",
commit_3,
commit_4,
commit_5,
secp.commit_sum(vec![commit_3, commit_4], vec![]).unwrap(),
);
}
$ cargo test test_pedersen_zero_neg_v -- --nocapture
running 1 test
0*G-5*H: Commitment(089e431be0851721f9ce35cc0f718fce7d6d970e3ddd796643d71294d7a09b554e)
0*G+5*H: Commitment(099e431be0851721f9ce35cc0f718fce7d6d970e3ddd796643d71294d7a09b554e)
-(0*G-5*H): Commitment(099e431be0851721f9ce35cc0f718fce7d6d970e3ddd796643d71294d7a09b554e)
1*G-5*H: Commitment(09b218ddacb34d827c71760e601b41d309bc888cf7e3ab7cc09ec082b645f77e5a)
0*G+5*H: Commitment(099e431be0851721f9ce35cc0f718fce7d6d970e3ddd796643d71294d7a09b554e)
1*G+0*H: Commitment(0879be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
sum first 2: Commitment(0879be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)
What's the calculation complexity of a Pedersen Commitment? Let's have a benchmark test.
Source Code (Click to expand)
#[test]
fn bench_generator_h_efficiency() {
const PC_LENGTH: usize = 1000_000;
let secp = Secp256k1::with_caps(ContextFlag::Commit);
/// Generator H' (as compressed curve point (3))
const GENERATOR_H_V2 : [u8;33] = [
0x0a,
0x50, 0x92, 0x9b, 0x74, 0xc1, 0xa0, 0x49, 0x54,
0xb7, 0x8b, 0x4b, 0x60, 0x35, 0xe9, 0x7a, 0x5e,
0x07, 0x8a, 0x5a, 0x0f, 0x28, 0xec, 0x96, 0xd5,
0x47, 0xbf, 0xee, 0x9a, 0xce, 0x80, 0x3a, 0xc0
];
// Creates a pedersen commitment, with another 'H'
fn commit_v2(secp: *const Secp256k1, value: u64, blind: SecretKey) -> Option<Commitment> {
let mut commit = [0; 33];
unsafe {
if (*secp).caps != ContextFlag::Commit {
return None;
}
ffi::secp256k1_pedersen_commit(
(*secp).ctx,
commit.as_mut_ptr(),
blind.as_ptr(),
value,
GENERATOR_H_V2.as_ptr(),
constants::GENERATOR_G.as_ptr(),
)
};
Some(Commitment(commit))
}
let mut r = SecretKey([0;32]);
thread_rng().fill_bytes(&mut r.0);
let value: u64 = 12345678;
//--- H1
let now = SystemTime::now();
for i in 1..PC_LENGTH+1 {
let _commit = secp.commit(value+i as u64, r);
}
if let Ok(elapsed) = now.elapsed() {
let used_time = elapsed.as_secs();
println!("spent time:\t{}(s)/({} pedersen commitment with H1)", used_time, PC_LENGTH);
}
//--- H2
let now = SystemTime::now();
for i in 1..PC_LENGTH+1 {
let _commit = commit_v2(&secp, value+i as u64, r);
}
if let Ok(elapsed) = now.elapsed() {
let used_time = elapsed.as_secs();
println!("spent time:\t{}(s)/({} pedersen commitment with H2)", used_time, PC_LENGTH);
}
}
$ cargo test --release bench_generator_h_efficiency -- --nocapture
running 1 test
test bench::tests::bench_generator_h_efficiency ...
spent time: 252(s)/(1000000 pedersen commitment with H1)
spent time: 252(s)/(1000000 pedersen commitment with H2)
Now let's go the Confidential Transaction to see what magic things Pedersen Commitment can bring!