use core::borrow::{Borrow}; use std::collections::BTreeMap;
use merlin::Transcript;
use curve25519_dalek::constants;
use curve25519_dalek::ristretto::{CompressedRistretto,RistrettoPoint};
use curve25519_dalek::scalar::Scalar;
use super::*;
use crate::context::SigningTranscript;
use crate::errors::MultiSignatureStage;
fn commit_public_keys<'a,I>(keys: I) -> Transcript
where I: Iterator<Item=&'a PublicKey>
{
let mut t = Transcript::new(b"MuSig-aggregate-public_key");
for pk in keys {
t.commit_point(b"pk-set", pk.as_compressed() );
}
t
}
fn compute_weighting(mut t: Transcript, pk: &PublicKey) -> Scalar {
t.commit_point(b"pk-choice", pk.as_compressed() );
t.challenge_scalar(b"")
}
pub trait AggregatePublicKey {
fn weighting(&self, choice: &PublicKey) -> Option<Scalar>;
fn public_key(&self) -> PublicKey;
}
impl<K,V> AggregatePublicKey for BTreeMap<K,V>
where K: Borrow<PublicKey>+Ord
{
fn weighting(&self, choice: &PublicKey) -> Option<Scalar> {
if ! self.contains_key(choice) { return None; }
let t0 = commit_public_keys( self.keys().map(|pk| pk.borrow()) );
Some(compute_weighting(t0, choice))
}
fn public_key(&self) -> PublicKey {
let t0 = commit_public_keys( self.keys().map(|pk| pk.borrow()) );
let point = self.keys().map(|pk| {
let pk = pk.borrow();
compute_weighting(t0.clone(), pk) * pk.as_point()
}).sum();
PublicKey::from_point(point)
}
}
pub struct AggregatePublicKeySlice<'a,K>(&'a [K])
where K: Borrow<PublicKey>;
pub fn aggregate_public_key_from_slice<'a>(public_keys: &'a mut [PublicKey])
-> Option<AggregatePublicKeySlice<'a,PublicKey>>
{
if public_keys.len() == 1 { return None; }
public_keys.sort_unstable();
if public_keys.windows(2).any(|x| x[0]==x[1]) { return None; }
Some(AggregatePublicKeySlice(public_keys))
}
pub fn aggregate_public_key_from_refs_slice<'a>(public_keys: &'a mut [&'a PublicKey])
-> Option<AggregatePublicKeySlice<'a,&'a PublicKey>>
{
if public_keys.len() == 1 { return None; }
public_keys.sort_unstable();
if public_keys.windows(2).any(|x| x[0]==x[1]) { return None; }
Some(AggregatePublicKeySlice(public_keys))
}
pub fn aggregate_public_key_from_sorted_slice<'a,K>(public_keys: &'a mut [K])
-> Option<AggregatePublicKeySlice<'a,K>>
where K: Borrow<PublicKey>+PartialOrd<K>
{
if public_keys.len() == 1 { return None; }
if public_keys.windows(2).any(|x| x[0] >= x[1]) { return None; }
Some(AggregatePublicKeySlice(public_keys))
}
impl<'a,K> AggregatePublicKey for AggregatePublicKeySlice<'a,K>
where K: Borrow<PublicKey>+PartialEq<K>
{
fn weighting(&self, choice: &PublicKey) -> Option<Scalar> {
if self.0.iter().any(|pk| pk.borrow() == choice) { return None; }
let t0 = commit_public_keys( self.0.iter().map(|pk| pk.borrow()) );
Some(compute_weighting(t0, choice))
}
fn public_key(&self) -> PublicKey {
let t0 = commit_public_keys( self.0.iter().map(|pk| pk.borrow()) );
let point = self.0.iter().map(|pk| {
let pk = pk.borrow();
compute_weighting(t0.clone(), pk) * pk.as_point()
} ).sum();
PublicKey::from_point(point)
}
}
const COMMITMENT_SIZE : usize = 16;
#[derive(Debug,Clone,Copy,PartialEq,Eq)]
pub struct Commitment(pub [u8; COMMITMENT_SIZE]);
impl Commitment {
#[allow(non_snake_case)]
fn for_R(R: &CompressedRistretto) -> Commitment {
let mut t = Transcript::new(b"MuSig-commitment");
t.commit_point(b"no",R);
let mut commit = [0u8; COMMITMENT_SIZE];
t.challenge_bytes(b"",&mut commit[..]);
Commitment(commit)
}
}
#[allow(non_snake_case)]
#[derive(Debug,Clone,Copy,PartialEq,Eq)]
enum CoR {
Commit(Commitment), Reveal { R: RistrettoPoint }, Cosigned { s: Scalar }, Collect { R: RistrettoPoint, s: Scalar },
}
impl CoR {
#[allow(non_snake_case)]
fn set_revealed(&mut self, R: CompressedRistretto) -> SignatureResult<()> {
let commitment = Commitment::for_R(&R);
let R = R.decompress().ok_or(SignatureError::PointDecompressionError) ?;
match self.clone() { CoR::Collect { .. } => panic!("Internal error, set_reveal during collection phase."),
CoR::Cosigned { .. } => panic!("Internal error, cosigning during reveal phase."),
CoR::Commit(c_old) =>
if c_old==commitment { *self = CoR::Reveal { R };
Ok(())
} else {
let musig_stage = MultiSignatureStage::Commitment;
Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: false, })
},
CoR::Reveal { R: R_old } =>
if R_old == R { Ok(()) } else { let musig_stage = MultiSignatureStage::Reveal;
Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: true, })
}, }
}
#[allow(non_snake_case)]
fn set_cosigned(&mut self, s: Scalar) -> SignatureResult<()> {
match self {
CoR::Collect { .. } => panic!("Internal error, set_cosigned during collection phase."),
CoR::Commit(_) => {
let musig_stage = MultiSignatureStage::Reveal;
Err(SignatureError::MuSigAbsent { musig_stage, })
},
CoR::Reveal { .. } => {
*self = CoR::Cosigned { s };
Ok(())
},
CoR::Cosigned { s: s_old } =>
if *s_old==s { Ok(()) } else {
let musig_stage = MultiSignatureStage::Cosignature;
Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: true, })
},
}
}
}
#[allow(non_snake_case)]
pub struct MuSig<T: SigningTranscript,S> {
t: T,
Rs: BTreeMap<PublicKey,CoR>,
stage: S
}
impl<T: SigningTranscript,S> MuSig<T,S> {
pub fn public_keys(&self, require_reveal: bool) -> impl Iterator<Item=&PublicKey> {
self.Rs.iter().filter_map( move |(pk,cor)| match cor {
CoR::Commit(_) => if require_reveal { None } else { Some(pk) },
CoR::Reveal { .. } => Some(pk),
CoR::Cosigned { .. } => Some(pk),
CoR::Collect { .. } => Some(pk),
} )
}
fn compute_public_key(&self, require_reveal: bool) -> PublicKey {
let t0 = commit_public_keys(self.public_keys(require_reveal));
let point = self.public_keys(require_reveal).map( |pk|
compute_weighting(t0.clone(), pk) * pk.as_point()
).sum();
PublicKey::from_point(point)
}
pub fn public_key(&self) -> PublicKey
{ self.compute_public_key(true) }
pub fn expected_public_key(&self) -> PublicKey
{ self.compute_public_key(false) }
#[allow(non_snake_case)]
fn compute_R(&self) -> CompressedRistretto {
let R: RistrettoPoint = self.Rs.iter().filter_map( |(_pk,cor)| match cor {
CoR::Commit(_) => None,
CoR::Reveal { R } => Some(R),
CoR::Cosigned { .. } => panic!("Internal error, compute_R called during cosigning phase."),
CoR::Collect { R, .. } => Some(R),
} ).sum();
R.compress()
}
}
pub trait TranscriptStages {}
impl<'k> TranscriptStages for CommitStage<'k> {}
impl<'k> TranscriptStages for RevealStage<'k> {}
impl<T: SigningTranscript, S: TranscriptStages> MuSig<T,S> {
pub fn transcript(&mut self) -> &mut T { &mut self.t }
}
impl Keypair {
#[allow(non_snake_case)]
pub fn musig<'k,T: SigningTranscript>(&'k self, t: T) -> MuSig<T,CommitStage<'k>>
{
let r_me = t.witness_scalar(&[&self.secret.nonce]);
let R_me = &r_me * &constants::RISTRETTO_BASEPOINT_TABLE;
let mut Rs = BTreeMap::new();
Rs.insert(self.public, CoR::Reveal { R: R_me.clone() });
let stage = CommitStage { keypair: self, r_me, R_me: R_me.compress() };
MuSig { t, Rs, stage, }
}
}
#[allow(non_snake_case)]
pub struct CommitStage<'k> {
keypair: &'k Keypair,
r_me: Scalar,
R_me: CompressedRistretto,
}
impl<'k,T: SigningTranscript> MuSig<T,CommitStage<'k>> {
pub fn our_commitment(&self) -> Commitment {
Commitment::for_R(&self.stage.R_me)
}
pub fn add_their_commitment(&mut self, them: PublicKey, theirs: Commitment)
-> SignatureResult<()>
{
let theirs = CoR::Commit(theirs);
use std::collections::btree_map::Entry::*;
match self.Rs.entry(them) {
Vacant(v) => { v.insert(theirs); () },
Occupied(o) =>
if o.get() != &theirs {
let musig_stage = MultiSignatureStage::Commitment;
return Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: true, });
},
}
Ok(())
}
#[allow(non_snake_case)]
pub fn reveal_stage(self) -> MuSig<T,RevealStage<'k>> {
let MuSig { t, Rs, stage: CommitStage { keypair, r_me, R_me, }, } = self;
MuSig { t, Rs, stage: RevealStage { keypair, r_me, R_me, }, }
}
}
#[allow(non_snake_case)]
pub struct RevealStage<'k> {
keypair: &'k Keypair,
r_me: Scalar,
R_me: CompressedRistretto,
}
#[derive(Debug,Clone,Copy,PartialEq,Eq)]
pub struct Reveal(pub [u8; 32]);
impl<'k,T: SigningTranscript> MuSig<T,RevealStage<'k>> {
pub fn our_reveal(&self) -> Reveal {
Reveal(self.stage.R_me.to_bytes())
}
pub fn add_their_reveal(&mut self, them: PublicKey, theirs: Reveal)
-> SignatureResult<()>
{
use std::collections::btree_map::Entry::*;
match self.Rs.entry(them) {
Vacant(_) => {
let musig_stage = MultiSignatureStage::Commitment;
Err(SignatureError::MuSigAbsent { musig_stage, })
},
Occupied(mut o) => o.get_mut().set_revealed(CompressedRistretto(theirs.0))
}
}
#[allow(non_snake_case)]
pub fn add_trusted(&mut self, them: PublicKey, theirs: Reveal)
-> SignatureResult<()>
{
let R = CompressedRistretto(theirs.0).decompress()
.ok_or(SignatureError::PointDecompressionError) ?;
let theirs = CoR::Reveal { R };
use std::collections::btree_map::Entry::*;
match self.Rs.entry(them) {
Vacant(v) => { v.insert(theirs); () },
Occupied(o) =>
if o.get() != &theirs {
let musig_stage = MultiSignatureStage::Reveal;
return Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: true, });
},
}
Ok(())
}
#[allow(non_snake_case)]
pub fn cosign_stage(mut self) -> MuSig<T,CosignStage> {
self.t.proto_name(b"Schnorr-sig");
let pk = self.public_key().as_compressed().clone();
self.t.commit_point(b"pk",&pk);
let R = self.compute_R();
self.t.commit_point(b"no",&R);
let t0 = commit_public_keys(self.public_keys(true));
let a_me = compute_weighting(t0, &self.stage.keypair.public);
let c = self.t.challenge_scalar(b""); let s_me = &(&c * &a_me * &self.stage.keypair.secret.key) + &self.stage.r_me;
let MuSig { t, mut Rs, stage: RevealStage { .. }, } = self;
*(Rs.get_mut(&self.stage.keypair.public).expect("Rs known to contain this public; qed")) = CoR::Cosigned { s: s_me.clone() };
MuSig { t, Rs, stage: CosignStage { R, s_me }, }
}
}
#[allow(non_snake_case)]
pub struct CosignStage {
R: CompressedRistretto,
s_me: Scalar,
}
#[derive(Debug,Clone,Copy,PartialEq,Eq)]
pub struct Cosignature(pub [u8; 32]);
impl<T: SigningTranscript> MuSig<T,CosignStage> {
pub fn our_cosignature(&self) -> Cosignature {
Cosignature(self.stage.s_me.to_bytes())
}
pub fn add_their_cosignature(&mut self, them: PublicKey, theirs: Cosignature)
-> SignatureResult<()>
{
let theirs = Scalar::from_canonical_bytes(theirs.0)
.ok_or(SignatureError::ScalarFormatError) ?;
use std::collections::btree_map::Entry::*;
match self.Rs.entry(them) {
Vacant(_) => {
let musig_stage = MultiSignatureStage::Reveal;
Err(SignatureError::MuSigAbsent { musig_stage, })
},
Occupied(mut o) => o.get_mut().set_cosigned(theirs)
}
}
pub fn cosigned(&self) -> impl Iterator<Item=&PublicKey> {
self.Rs.iter().filter_map( |(pk,cor)| match cor {
CoR::Commit(_) => None,
CoR::Reveal { .. } => None,
CoR::Cosigned { .. } => Some(pk),
CoR::Collect { .. } => panic!("Collect found in Cosign phase.")
} )
}
pub fn uncosigned(&self) -> impl Iterator<Item=&PublicKey> {
self.Rs.iter().filter_map( |(pk,cor)| match cor {
CoR::Commit(_) => None,
CoR::Reveal { .. } => Some(pk),
CoR::Cosigned { .. } => None,
CoR::Collect { .. } => panic!("Collect found in Cosign phase."),
} )
}
#[allow(non_snake_case)]
pub fn sign(&self) -> Option<Signature> {
if self.uncosigned().last().is_some() { return None; }
let s: Scalar = self.Rs.iter()
.filter_map( |(_pk,cor)| match cor {
CoR::Commit(_) => None,
CoR::Reveal { .. } => panic!("Internal error, MuSig<T,CosignStage>::uncosigned broken."),
CoR::Cosigned { s, .. } => Some(s),
CoR::Collect { .. } => panic!("Collect found in Cosign phase."),
} ).sum();
Some(Signature { s, R: self.stage.R, })
}
}
#[allow(non_snake_case)]
pub fn collect_cosignatures<T: SigningTranscript>(mut t: T) -> MuSig<T,CollectStage> {
t.proto_name(b"Schnorr-sig");
MuSig { t, Rs: BTreeMap::new(), stage: CollectStage, }
}
pub struct CollectStage;
impl<T: SigningTranscript> MuSig<T,CollectStage> {
#[allow(non_snake_case)]
pub fn add(&mut self, them: PublicKey, their_reveal: Reveal, their_cosignature: Cosignature)
-> SignatureResult<()>
{
let R = CompressedRistretto(their_reveal.0).decompress()
.ok_or(SignatureError::PointDecompressionError) ?;
let s = Scalar::from_canonical_bytes(their_cosignature.0)
.ok_or(SignatureError::ScalarFormatError) ?;
let cor = CoR::Collect { R, s };
use std::collections::btree_map::Entry::*;
match self.Rs.entry(them) {
Vacant(v) => { v.insert(cor); () },
Occupied(o) =>
if o.get() != &cor {
let musig_stage = MultiSignatureStage::Reveal;
return Err(SignatureError::MuSigInconsistent { musig_stage, duplicate: true, });
},
}
Ok(())
}
#[allow(non_snake_case)]
pub fn signature(&self) -> Signature {
let R = self.compute_R();
let s: Scalar = self.Rs.iter()
.map( |(_pk,cor)| match cor {
CoR::Collect { s, .. } => s,
_ => panic!("Reached CollectStage from another stage"),
} ).sum();
Signature { s, R, }
}
}
#[cfg(test)]
mod tests {
use std::vec::Vec;
use rand::prelude::*;
use super::*;
#[test]
fn aggregation_btreeemap_vs_slice() {
let mut csprng = thread_rng();
let mut vec: Vec<PublicKey> = (0..16).map(|_| SecretKey::generate(&mut csprng).to_public()).collect();
let btm: BTreeMap<PublicKey,()> = vec.iter().map( |x| (x.clone(),()) ).collect();
debug_assert_eq!(
btm.public_key(),
aggregate_public_key_from_slice(vec.as_mut_slice()).unwrap().public_key()
);
}
#[test]
fn multi_signature() {
let mut csprng = thread_rng();
let keypairs: Vec<Keypair> = (0..16).map(|_| Keypair::generate(&mut csprng)).collect();
let t = signing_context(b"multi-sig").bytes(b"We are legion!");
let mut commits: Vec<_> = keypairs.iter().map( |k| k.musig(t.clone()) ).collect();
for i in 0..commits.len() {
let r = commits[i].our_commitment();
for j in commits.iter_mut() {
assert!( j.add_their_commitment(keypairs[i].public.clone(),r)
.is_ok() != (r == j.our_commitment()) );
}
}
let mut reveal_msgs: Vec<Reveal> = Vec::with_capacity(commits.len());
let mut reveals: Vec<_> = commits.drain(..).map( |c| c.reveal_stage() ).collect();
for i in 0..reveals.len() {
let r = reveals[i].our_reveal();
for j in reveals.iter_mut() {
j.add_their_reveal(keypairs[i].public.clone(),r).unwrap();
}
reveal_msgs.push(r);
}
let pk = reveals[0].public_key();
let mut cosign_msgs: Vec<Cosignature> = Vec::with_capacity(reveals.len());
let mut cosigns: Vec<_> = reveals.drain(..).map( |c| { assert_eq!(pk, c.public_key()); c.cosign_stage() } ).collect();
for i in 0..cosigns.len() {
assert_eq!(pk, cosigns[i].public_key());
let r = cosigns[i].our_cosignature();
for j in cosigns.iter_mut() {
j.add_their_cosignature(keypairs[i].public.clone(),r).unwrap();
}
cosign_msgs.push(r);
assert_eq!(pk, cosigns[i].public_key());
}
let mut c = collect_cosignatures(t.clone());
for i in 0..cosigns.len() {
c.add(keypairs[i].public.clone(),reveal_msgs[i].clone(),cosign_msgs[i].clone()).unwrap();
}
let signature = c.signature();
assert!(pk.verify(t,&signature));
for i in 0..cosigns.len() {
assert_eq!(pk, cosigns[i].public_key());
assert_eq!(signature, cosigns[i].sign().unwrap());
}
}
}