use crate::{
ed25519,
or::Either,
secp256k1,
secp256k1::fun::{
g,
marker::*,
rand_core::{CryptoRng, RngCore},
s,
subtle::{self, ConditionallySelectable},
Point as PointP, Scalar as ScalarP, G as GP,
},
All, And, Eq, FiatShamir, Or, ProverTranscript, Sigma, Transcript,
};
use alloc::vec::Vec;
use curve25519_dalek::{
constants::ED25519_BASEPOINT_TABLE, edwards::EdwardsPoint as PointQ, scalar::Scalar as ScalarQ,
traits::Identity,
};
use generic_array::typenum::{U252, U31};
static GQ: &'static curve25519_dalek::edwards::EdwardsBasepointTable = &ED25519_BASEPOINT_TABLE;
pub type CoreProof = And<
All<
Or<
And<secp256k1::DLG<U31>, ed25519::DLG<U31>>,
And<secp256k1::DLG<U31>, ed25519::DLG<U31>>,
>,
U252,
>,
And<Eq<secp256k1::DLG<U31>, secp256k1::DL<U31>>, Eq<ed25519::DLG<U31>, ed25519::DL<U31>>>,
>;
const COMMITMENT_BITS: usize = 252;
#[cfg_attr(
feature = "serde",
derive(serde_crate::Serialize, serde_crate::Deserialize),
serde(crate = "serde_crate")
)]
#[derive(Debug, Clone, PartialEq)]
pub struct CrossCurveDLEQProof {
pub sum_blindings: (ScalarP<Public, Zero>, ScalarQ),
pub commitments: Vec<(PointP, PointQ)>,
pub proof: crate::CompactProof<CoreProof>,
}
#[derive(Debug, Clone)]
pub struct CrossCurveDLEQ<T> {
HQ: PointQ,
HP: PointP,
core_proof_system: FiatShamir<CoreProof, T>,
powers_of_two: Vec<(PointP, PointQ)>,
}
impl<T: Transcript<CoreProof> + Default> CrossCurveDLEQ<T> {
pub fn new(HP: PointP, HQ: PointQ) -> Self {
let powers_of_two = core::iter::successors(Some((HP.clone(), HQ.clone())), |(H2P, H2Q)| {
Some((
g!(H2P + H2P).mark::<(Normal, NonZero)>().unwrap(),
(H2Q + H2Q),
))
})
.take(COMMITMENT_BITS)
.collect();
Self {
HP,
HQ,
core_proof_system: FiatShamir::<CoreProof, T>::default(),
powers_of_two,
}
}
pub fn prove(
&self,
secret: &ScalarQ,
rng: &mut (impl CryptoRng + RngCore),
) -> (CrossCurveDLEQProof, (PointP, PointQ))
where
T: ProverTranscript<CoreProof>,
{
assert!(secret.as_bytes()[31] & 0b00010000 == 0);
let secp_secret = {
let mut bytes = secret.to_bytes();
bytes.reverse();
ScalarP::from_bytes(bytes)
.expect("will never overflow since ed25519 order is lower")
.mark::<NonZero>()
.expect("must not be zero")
};
let claim = (g!(secp_secret * GP).mark::<Normal>(), secret * GQ);
let pedersen_blindings = (0..COMMITMENT_BITS)
.map(|_| (ScalarP::random(rng), ScalarQ::random(rng)))
.collect::<Vec<_>>();
let sum_blindings = pedersen_blindings.iter().fold(
(ScalarP::zero(), ScalarQ::zero()),
|(accP, accQ), (rP, rQ)| (s!(accP + rP), accQ + rQ),
);
let sum_blindings = (sum_blindings.0.mark::<Public>(), sum_blindings.1);
let bits = to_bits(secret);
let commitments = self
.powers_of_two
.iter()
.zip(bits.iter())
.zip(pedersen_blindings.iter())
.map(|(((H2P, H2Q), bit), (rP, rQ))| {
let zero_commit_p = g!(rP * GP).mark::<Secret>();
let one_commit_p = g!(zero_commit_p + H2P)
.mark::<NonZero>()
.expect("computationally unreachable since zero_comit_p is random");
let zero_commit_q = rQ * GQ;
let one_commit_q = &zero_commit_q + H2Q;
let bit = subtle::Choice::from(*bit as u8);
(
PointP::conditional_select(
&zero_commit_p.mark::<(Public, Normal)>(),
&one_commit_p.mark::<Normal>(),
bit,
),
PointQ::conditional_select(&zero_commit_q, &one_commit_q, bit),
)
})
.collect::<Vec<_>>();
let statement = self
.generate_statement(&sum_blindings, &claim, &commitments[..])
.expect("statement will be valid since we genreated it ourself");
let proof_witness = (
pedersen_blindings
.into_iter()
.zip(bits.iter())
.map(|((rP, rQ), bit)| match bit {
false => Either::Left((rP, rQ)),
true => Either::Right((rP, rQ)),
})
.collect(),
(secp_secret, secret.clone()),
);
let proof = self
.core_proof_system
.prove(&proof_witness, &statement, Some(rng));
(
CrossCurveDLEQProof {
sum_blindings,
commitments,
proof,
},
claim,
)
}
fn generate_statement(
&self,
(rP, rQ): &(ScalarP<Public, Zero>, ScalarQ),
(XP, XQ): &(PointP, PointQ),
commitments: &[(PointP, PointQ)],
) -> Option<<CoreProof as Sigma>::Statement> {
let commitment_statement = self
.powers_of_two
.iter()
.zip(commitments)
.map(|((H2P, H2Q), (CP, CQ))| {
g!(CP - H2P).mark::<(Normal, NonZero)>().map(|CP_sub_H2P| {
(
(CP.clone(), CQ.clone()),
(CP_sub_H2P, CQ - H2Q),
)
})
})
.collect::<Option<Vec<_>>>()?;
let (sumP, sumQ) = commitments.iter().fold(
(PointP::zero().mark::<Jacobian>(), PointQ::identity()),
|(accP, accQ), (CP, CQ)| (g!(accP + CP), accQ + CQ),
);
let unblindedP = g!(sumP - rP * GP).mark::<(Normal, NonZero)>()?;
let unblindedQ = sumQ - rQ * GQ;
let dleq_G_to_H = (
(XP.clone(), (self.HP.clone(), unblindedP)),
(XQ.clone(), (self.HQ, unblindedQ)),
);
Some((commitment_statement, dleq_G_to_H))
}
#[must_use]
pub fn verify(&self, proof: &CrossCurveDLEQProof, claim: (PointP, PointQ)) -> bool {
if proof.commitments.len() != COMMITMENT_BITS || !claim.1.is_torsion_free() {
return false;
}
let statement = self.generate_statement(&proof.sum_blindings, &claim, &proof.commitments);
match statement {
Some(statement) => self.core_proof_system.verify(&statement, &proof.proof),
None => false,
}
}
}
fn to_bits(secret_key: &ScalarQ) -> [bool; COMMITMENT_BITS] {
let bytes = secret_key.as_bytes();
let mut bits = [false; COMMITMENT_BITS];
let mut index = 0;
for i in 0..32 {
for j in 0..8 {
bits[index + j] = (bytes[i] & (1 << j)) != 0;
if i == 31 && j == 3 {
break;
}
}
index += 8;
}
bits
}
#[cfg(test)]
mod test {
use super::*;
use crate::{
ed25519::test::{ed25519_point, ed25519_scalar},
secp256k1::fun::proptest::point as secp256k1_point,
HashTranscript,
};
use ::proptest::prelude::*;
use rand_chacha::ChaCha20Rng;
use sha2::Sha256;
type Transcript = HashTranscript<Sha256, ChaCha20Rng>;
#[test]
#[should_panic]
fn high_scalar_should_panic() {
let high_scalar = -ScalarQ::one();
let HP = PointP::random(&mut rand::thread_rng());
let HQ = &ScalarQ::random(&mut rand::thread_rng()) * &ED25519_BASEPOINT_TABLE;
let proof_system = CrossCurveDLEQ::<Transcript>::new(HP, HQ);
let _ = proof_system.prove(&high_scalar, &mut rand::thread_rng());
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(3))]
#[test]
fn dl_secp256k1_ed25519_eq(
secret in ed25519_scalar(),
HP in secp256k1_point(),
HQ in ed25519_point(),
) {
let proof_system = CrossCurveDLEQ::<Transcript>::new(HP, HQ);
let (proof, claim) = proof_system.prove(&secret, &mut rand::thread_rng());
assert!(proof_system.verify(&proof, claim));
}
}
#[cfg(feature = "serde")]
proptest! {
#![proptest_config(ProptestConfig::with_cases(3))]
#[test]
fn serialization_roundtrip(
secret in ed25519_scalar(),
HP in secp256k1_point(),
HQ in ed25519_point(),
) {
let proof_system = CrossCurveDLEQ::<Transcript>::new(HP, HQ);
let (proof, _) = proof_system.prove(&secret, &mut rand::thread_rng());
let proof_serialized = bincode::serialize(&proof).unwrap();
let proof_deserialized: CrossCurveDLEQProof =
bincode::deserialize(&proof_serialized).unwrap();
assert_eq!(proof_deserialized, proof);
}
}
}