Skip to content

Instantly share code, notes, and snippets.

@CjS77
Last active January 24, 2019 21:27
Show Gist options
  • Save CjS77/b68f2f93c74113abe1b0e053b26d3662 to your computer and use it in GitHub Desktop.
Save CjS77/b68f2f93c74113abe1b0e053b26d3662 to your computer and use it in GitHub Desktop.
You can't use Curve25519 as is for Pederson commitments
[package]
name = "dalek-demo"
version = "0.1.0"
authors = ["CjS77"]
edition = "2018"
[dependencies]
digest = "0.7.6"
rand = "0.5.5"
curve25519-dalek = "1.0.2"
sha2 = "0.7.1"
#[cfg(test)]
mod test {
use curve25519_dalek::constants::{ RISTRETTO_BASEPOINT_POINT, ED25519_BASEPOINT_COMPRESSED};
use curve25519_dalek::edwards::{ EdwardsPoint, CompressedEdwardsY};
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::ristretto::RistrettoPoint;
use sha2::{Sha256, Digest, Sha512};
use rand;
#[test]
/// if C1 = v1.G + k1.H and C2 = v2.G + k2.H, then C1 + C2 = (v1+v2).G + (k1+k2).H
fn test_edwards() {
let mut rng = rand::rngs::OsRng::new().unwrap();
let v = nums_generator();
for _ in 0..100 {
let v1 = Scalar::random(&mut rng);
let v2 = Scalar::random(&mut rng);
let v_sum = v1 + v2;
let k1 = Scalar::random(&mut rng);
let k2 = Scalar::random(&mut rng);
let k_sum = k1 + k2;
let c1 = (v1 * v[0]) + (k1 * v[1]);
let c2 = (v2 * v[0]) + (k2 * v[1]);
let c_sum = c1 + c2;
let c_calc = (v_sum * v[0]) + (k_sum * v[1]);
assert_eq!(c_sum, c_calc);
}
}
#[test]
fn test_ristretto() {
let mut rng = rand::rngs::OsRng::new().unwrap();
let v = nums_ristretto();
for _ in 0..100 {
let v1 = Scalar::random(&mut rng);
let v2 = Scalar::random(&mut rng);
let v_sum = v1 + v2;
let k1 = Scalar::random(&mut rng);
let k2 = Scalar::random(&mut rng);
let k_sum = k1 + k2;
let c1 = v1 * v[0] + k1 * v[1];
let c2 = v2 * v[0] + k2 * v[1];
let c_sum = &c1 + &c2;
let c_calc = v_sum * v[0] + k_sum*v[1];
assert_eq!(c_sum, c_calc);
}
}
fn nums_generator() -> Vec<EdwardsPoint> {
let mut b = ED25519_BASEPOINT_COMPRESSED.to_bytes();
let mut result = Vec::new();
for _ in 0..10 {
let tmp = Sha256::digest(&b[..]);
b.copy_from_slice(&tmp);
//println!("{:?}", b);
let y = CompressedEdwardsY::from_slice(&b[..]);
match y.decompress() {
None => {},
Some(p) => {
result.push(p);
},
}
}
result
}
fn nums_ristretto() -> Vec<RistrettoPoint> {
let mut v = RISTRETTO_BASEPOINT_POINT.compress().to_bytes();
let mut result = Vec::new();
let mut a: [u8; 64] = [0; 64];
for _ in 0..10 {
let b = Sha512::digest(&v[..]);
a.copy_from_slice(&b);
let y = RistrettoPoint::from_uniform_bytes(&a);
//println!("{:?}", y.compress());
result.push(y);
v = y.compress().to_bytes();
}
result
}
}
running 2 tests
test test::test_edwards ... FAILED
test test::test_ristretto ... ok
failures:
---- test::test_edwards stdout ----
thread 'test::test_edwards' panicked at 'assertion failed: `(left == right)`
left: `EdwardsPoint{
X: FieldElement64([1531707007258719, 1258946037969784, 243556379571174, 1945072435110807, 284700417697730]),
Y: FieldElement64([1435024719969155, 1332736115257686, 1215739453577767, 2080738175871499, 516662332011323]),
Z: FieldElement64([411225951725971, 1911884897179498, 1014602146587710, 1278358449903002, 1233262859830505]),
T: FieldElement64([1510852185061147, 1805175996069192, 343000094183791, 170068099261104, 1254313934314330])
}`,
right: `EdwardsPoint{
X: FieldElement64([1153684776183548, 2157636384973933, 231026727972195, 196244963240251, 1242503449948005]),
Y: FieldElement64([1635148797106791, 287035736056550, 1562419854368087, 1366521906342930, 2000083184571540]),
Z: FieldElement64([57072789377721, 1747821635757225, 1614093566043302, 1788025640736557, 60766675597696]),
T: FieldElement64([937163208295048, 789617646879995, 17635268886177, 10385686617732, 1837339077287886])
}`', src/lib.rs:30:13
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.
failures:
test::test_edwards
test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out
@CjS77
Copy link
Author

CjS77 commented Jan 21, 2019

The gist does the following:
Using curve25519-dalek v1.0.2:

  • Generate a set of "NUMS" points on the curve by sequentially hashing the base point.
  • Calculate 2 commitment using two of the points: Ci = vi.G + ki.H using random scalars.
  • Check that C_1 + C_2 = (v_1 + v_2).G + (k_1 + k_2).H

This works using the RistrettoPoint implementation, but fails for EdwardsPoints.

@CjS77
Copy link
Author

CjS77 commented Jan 22, 2019

Henry de Valence pointed out the issue with this code:

So the problem is related to cofactors. Let q be the order of the
ristretto255 group and the order of the prime-order subgroup of
Curve25519.

For operations in the ristretto255 group or in the prime-order
subgroup of Curve25519, the scalars are computed mod q, which is what
the curve25519-dalek Scalar type does.

But the full Curve25519 group has order 8q, so the scalars for the
full Curve25519 group need to be computed mod 8
q. The NUMS
generators that you construct for Curve25519 don't lie in the
prime-order subgroup (to check this, try
assert!(v[0].is_torsion_free())), so they have an extra torsion
component tagging along.

The scalar arithmetic is performed mod q, so the prime-order part of
the result is computed correctly, but the torsion component isn't.
The test will pass if you do either of these things:

a) Call .mul_by_cofactor when constructing the Curve25519
generators, so that the generators are forced into the prime-order
subgroup;
b) Call .mul_by_cofactor when comparing the results (which shows
that the prime-order part is computed correctly, while the torsion
part isn't).

As you can see, the cofactor 8 of Curve25519 causes some subtle
problems, which is why I would not recommend building Pedersen
commitments using Curve25519, and suggest using ristretto255 instead.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment