Last active
January 24, 2019 21:27
-
-
Save CjS77/b68f2f93c74113abe1b0e053b26d3662 to your computer and use it in GitHub Desktop.
You can't use Curve25519 as is for Pederson commitments
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
[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" |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#[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 | |
} | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 8q. 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 torsioncomponent 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 Curve25519generators, so that the generators are forced into the prime-order
subgroup;
b) Call
.mul_by_cofactor
when comparing the results (which showsthat 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.