use std::borrow::{Borrow,BorrowMut};
use std::collections::HashMap;
use std::iter::{once};
use super::*;
use super::single::SignedMessage;
use super::verifiers::verify_with_distinct_messages;
#[derive(Clone)]
pub struct BatchAssumingProofsOfPossession<E: EngineBLS> {
messages_n_publickeys: HashMap<Message,PublicKey<E>>,
signature: Signature<E>,
}
impl<E: EngineBLS> BatchAssumingProofsOfPossession<E> {
pub fn new() -> BatchAssumingProofsOfPossession<E> {
BatchAssumingProofsOfPossession {
messages_n_publickeys: HashMap::new(),
signature: Signature(E::SignatureGroup::zero()),
}
}
pub fn add_signature(&mut self, signature: &Signature<E>) {
self.signature.0.add_assign(&signature.0);
}
pub fn add_message_n_publickey(&mut self, message: &Message, publickey: &PublicKey<E>) {
self.messages_n_publickeys.entry(*message)
.and_modify(|pk0| pk0.0.add_assign(&publickey.0) )
.or_insert(*publickey);
}
pub fn aggregate<'a,S>(&mut self, signed: &'a S)
where
&'a S: Signed<E=E>,
<&'a S as Signed>::PKG: Borrow<PublicKey<E>>,
{
let signature = signed.signature();
for (message,pubickey) in signed.messages_and_publickeys() {
self.add_message_n_publickey(message.borrow(),pubickey.borrow());
}
self.add_signature(&signature);
}
}
impl<'a,E: EngineBLS> Signed for &'a BatchAssumingProofsOfPossession<E> {
type E = E;
type M = &'a Message;
type PKG = &'a PublicKey<Self::E>;
type PKnM = ::std::collections::hash_map::Iter<'a,Message,PublicKey<E>>;
fn messages_and_publickeys(self) -> Self::PKnM {
self.messages_n_publickeys.iter()
}
fn signature(&self) -> Signature<E> { self.signature }
fn verify(self) -> bool {
verify_with_distinct_messages(self,true)
}
}
fn slice_eq_bytewise<T: PartialEq<T>>(x: &[T], y: &[T]) -> bool {
if x.len() != y.len() { return false; }
if ::std::ptr::eq(x,y) { return true; }
x == y
}
pub trait ProofsOfPossession<E: EngineBLS> {
fn agreement(&self, other: &Self) -> bool;
type Signers: Borrow<[u8]>+BorrowMut<[u8]>+Clone+Sized;
fn new_signers(&self) -> Self::Signers;
fn lookup(&self, index: usize) -> Option<PublicKey<E>>;
fn find(&self, publickey: &PublicKey<E>) -> Option<usize>;
}
fn chunk_lookups<E,PoP>(proofs_of_possession: &PoP, offset: usize) -> u8
where E: EngineBLS, PoP:ProofsOfPossession<E>
{
(0..8).into_iter().fold(0u8, |b,j| {
let i = 8*offset + j;
let pk = proofs_of_possession.lookup(i)
.filter(|pk| {
let bb = Some(i) == proofs_of_possession.find(&pk);
debug_assert!(bb , "Incorrect ProofsOfPossession implementation with duplicate publickeys" );
bb
});
b | pk.map_or(0u8, |_| 1u8 << j)
})
}
impl<E,V> ProofsOfPossession<E> for V
where
E: EngineBLS,
V: ::std::ops::Deref<Target=[PublicKey<E>]>
{
fn agreement(&self, other: &Self) -> bool {
slice_eq_bytewise(self.deref(),other.deref())
}
type Signers = Box<[u8]>;
fn new_signers(&self) -> Self::Signers {
vec![0u8; (self.deref().len() + 7) / 8].into_boxed_slice()
}
fn lookup(&self, index: usize) -> Option<PublicKey<E>> {
self.deref().get(index).cloned()
}
fn find(&self, publickey: &PublicKey<E>) -> Option<usize> {
self.deref().iter().position(|pk| *pk==*publickey)
}
}
#[derive(Debug)]
pub enum PoPError {
BadPoP(&'static str),
MismatchedMessage,
RepeatedSigners,
}
impl ::std::fmt::Display for PoPError {
fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
use self::PoPError::*;
match self {
BadPoP(s) => write!(f, "{}", s),
MismatchedMessage => write!(f, "Cannot aggregate distinct messages with only a bit field."),
RepeatedSigners => write!(f, "Cannot aggregate due to duplicate signers."),
}
}
}
impl ::std::error::Error for PoPError {
fn description(&self) -> &str {
use self::PoPError::*;
match self {
BadPoP(s) => s,
MismatchedMessage => "Cannot aggregate distinct messages with only a bit field.",
RepeatedSigners => "Cannot aggregate due to duplicate signers",
}
}
fn cause(&self) -> Option<&::std::error::Error> { None }
}
pub struct BitPoPSignedMessage<E: EngineBLS, POP: ProofsOfPossession<E>> {
proofs_of_possession: POP,
signers: <POP as ProofsOfPossession<E>>::Signers,
message: Message,
signature: Signature<E>,
}
impl<'a,E,POP> Clone for BitPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>+Clone,
{
fn clone(&self) -> BitPoPSignedMessage<E,POP> {
BitPoPSignedMessage {
proofs_of_possession: self.proofs_of_possession.clone(),
signers: self.signers.clone(),
message: self.message,
signature: self.signature.clone(),
}
}
}
impl<'a,E,POP> Signed for &'a BitPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>,
{
type E = E;
type M = Message;
type PKG = PublicKey<E>;
type PKnM = ::std::iter::Once<(Message, PublicKey<E>)>;
fn messages_and_publickeys(self) -> Self::PKnM {
let mut publickey = E::PublicKeyGroup::zero();
for i in 0..8*self.signers.borrow().len() {
if self.signers.borrow()[i / 8] & (1 << (i % 8)) != 0 {
let pop_pk = self.proofs_of_possession.lookup(i).unwrap();
if Some(i) != self.proofs_of_possession.find(&pop_pk) {
debug_assert!(false, "Incorrect ProofsOfPossession implementation with duplicate publickeys" );
continue;
}
publickey.add_assign(&pop_pk.0);
}
}
once((self.message.clone(), PublicKey(publickey)))
}
fn signature(&self) -> Signature<E> { self.signature }
fn verify(self) -> bool {
verify_with_distinct_messages(self,true)
}
}
impl<E,POP> BitPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>,
{
pub fn new(proofs_of_possession: POP, message: Message) -> BitPoPSignedMessage<E,POP> {
let signers = proofs_of_possession.new_signers();
let signature = Signature(E::SignatureGroup::zero());
BitPoPSignedMessage { proofs_of_possession, signers, message, signature }
}
fn add_points(&mut self, publickey: PublicKey<E>, signature: Signature<E>) -> Result<(),PoPError> {
let i = self.proofs_of_possession.find(&publickey)
.ok_or(PoPError::BadPoP("Mismatched proof-of-possession")) ?;
if self.proofs_of_possession.lookup(i) != Some(publickey) {
return Err(PoPError::BadPoP("Invalid ProofsOfPossession implementation with missmatched lookups"));
}
let b = 1 << (i % 8);
let s = &mut self.signers.borrow_mut()[i / 8];
if *s & b != 0 { return Err(PoPError::RepeatedSigners); }
*s |= b;
self.signature.0.add_assign(&signature.0);
Ok(())
}
pub fn add(&mut self, signed: &SignedMessage<E>) -> Result<(),PoPError>
{
if self.message != signed.message {
return Err(PoPError::MismatchedMessage);
}
self.add_points(signed.publickey,signed.signature)
}
pub fn merge(&mut self, other: &BitPoPSignedMessage<E,POP>) -> Result<(),PoPError> {
if self.message != other.message {
return Err(PoPError::MismatchedMessage);
}
if ! self.proofs_of_possession.agreement(&other.proofs_of_possession) {
return Err(PoPError::BadPoP("Mismatched proof-of-possession"));
}
for (offset,(x,y)) in self.signers.borrow().iter().zip(other.signers.borrow()).enumerate() {
if *x & *y != 0 { return Err(PoPError::RepeatedSigners); }
if *y & ! chunk_lookups(&self.proofs_of_possession, offset) != 0 {
return Err(PoPError::BadPoP("Absent signer"));
}
}
for (x,y) in self.signers.borrow_mut().iter_mut().zip(other.signers.borrow()) {
*x |= y;
}
self.signature.0.add_assign(&other.signature.0);
Ok(())
}
}
pub struct CountPoPSignedMessage<E: EngineBLS, POP: ProofsOfPossession<E>> {
proofs_of_possession: POP,
signers: Vec<<POP as ProofsOfPossession<E>>::Signers>,
message: Message,
signature: Signature<E>,
pub max_duplicates: usize,
}
impl<'a,E,POP> Clone for CountPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>+Clone,
{
fn clone(&self) -> CountPoPSignedMessage<E,POP> {
CountPoPSignedMessage {
proofs_of_possession: self.proofs_of_possession.clone(),
signers: self.signers.clone(),
message: self.message,
signature: self.signature.clone(),
max_duplicates: self.max_duplicates,
}
}
}
impl<'a,E,POP> Signed for &'a CountPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>,
{
type E = E;
type M = Message;
type PKG = PublicKey<E>;
type PKnM = ::std::iter::Once<(Message, PublicKey<E>)>;
fn messages_and_publickeys(self) -> Self::PKnM {
let mut publickey = E::PublicKeyGroup::zero();
for signers in self.signers.iter().rev().map(|signers| signers.borrow()) {
publickey.double();
for i in 0..8*signers.len() {
if signers[i / 8] & (1 << (i % 8)) != 0 {
let pop_pk = self.proofs_of_possession.lookup(i).unwrap();
if Some(i) != self.proofs_of_possession.find(&pop_pk) {
debug_assert!(false, "Incorrect ProofsOfPossession implementation with duplicate publickeys" );
continue;
}
publickey.add_assign(&pop_pk.0);
}
}
}
once((self.message.clone(), PublicKey(publickey)))
}
fn signature(&self) -> Signature<E> { self.signature }
fn verify(self) -> bool {
verify_with_distinct_messages(self,true)
}
}
impl<E,POP> CountPoPSignedMessage<E,POP>
where
E: EngineBLS,
POP: ProofsOfPossession<E>,
{
pub fn new(proofs_of_possession: POP, message: Message) -> CountPoPSignedMessage<E,POP> {
let signers = vec![proofs_of_possession.new_signers(); 1];
let signature = Signature(E::SignatureGroup::zero());
let max_duplicates = 16;
CountPoPSignedMessage { proofs_of_possession, signers, message, signature, max_duplicates }
}
fn reserve_depth(&mut self, count: usize) {
let l = 0usize.leading_zeros() - count.leading_zeros();
if l as usize <= self.signers.len() { return; }
let l = l as usize - self.signers.len();
self.signers.reserve(l);
for _i in 0..l {
self.signers.push(self.proofs_of_possession.new_signers());
}
}
fn trim(&mut self) {
let empty = |s: &POP::Signers| s.borrow().iter().all(|b| *b == 0u8);
let c = self.signers.len() - self.signers.iter().rev().take_while(|s| empty(&*s)).count();
self.signers.truncate(c)
}
fn test_count(&self, count: usize) -> Result<(),PoPError> {
if count >= self.max_duplicates || count >= usize::max_value() {
return Err(PoPError::RepeatedSigners);
}
Ok(())
}
fn get_count(&self, index: usize) -> usize {
let mut count = 0;
for signers in self.signers.iter().rev().map(|signers| signers.borrow()) {
count *= 2;
if signers[index / 8] & (1 << (index % 8)) != 0 {
count += 1;
}
}
count
}
fn set_count(&mut self, index: usize, mut count: usize) {
self.reserve_depth(count);
for signers in self.signers.iter_mut().map(|signers| signers.borrow_mut()) {
if count & 1usize != 0 {
signers[index / 8] |= 1 << (index % 8);
} else {
signers[index / 8] &= ! (1 << (index % 8));
}
count /= 2;
}
}
fn add_points(&mut self, publickey: PublicKey<E>, signature: Signature<E>) -> Result<(),PoPError> {
let i = self.proofs_of_possession.find(&publickey)
.ok_or(PoPError::BadPoP("Mismatched proof-of-possession")) ?;
if self.proofs_of_possession.lookup(i) != Some(publickey) {
return Err(PoPError::BadPoP("Invalid ProofsOfPossession implementation with missmatched lookups"));
}
let count = self.get_count(i) + 1;
self.test_count(count) ?;
self.set_count(i,count);
self.signature.0.add_assign(&signature.0);
Ok(())
}
pub fn add(&mut self, signed: &SignedMessage<E>) -> Result<(),PoPError>
{
if self.message != signed.message {
return Err(PoPError::MismatchedMessage);
}
self.add_points(signed.publickey,signed.signature)
}
pub fn add_bitpop(&mut self, other: &BitPoPSignedMessage<E,POP>) -> Result<(),PoPError> {
if self.message != other.message {
return Err(PoPError::MismatchedMessage);
}
if ! self.proofs_of_possession.agreement(&other.proofs_of_possession) {
return Err(PoPError::BadPoP("Mismatched proof-of-possession"));
}
let os = other.signers.borrow();
for offset in 0..self.signers[0].borrow().len() {
if self.signers.iter().fold(os[offset], |b,s| b | s.borrow()[offset])
& ! chunk_lookups(&self.proofs_of_possession, offset) != 0u8
{
return Err(PoPError::BadPoP("Absent signer"));
}
for j in 0..8 {
let mut count = self.get_count(8*offset+j);
if os[offset] & (1 << j) != 0 { count += 1; }
self.test_count(count) ?;
}
}
for index in 0..8*self.signers[0].borrow().len() {
let count = self.get_count(index);
if os[index / 8] & (1 << (index % 8)) != 0 { self.set_count(index,count+1); }
}
self.signature.0.add_assign(&other.signature.0);
Ok(())
}
pub fn merge(&mut self, other: &CountPoPSignedMessage<E,POP>) -> Result<(),PoPError> {
if self.message != other.message {
return Err(PoPError::MismatchedMessage);
}
if ! self.proofs_of_possession.agreement(&other.proofs_of_possession) {
return Err(PoPError::BadPoP("Mismatched proof-of-possession"));
}
for offset in 0..self.signers[0].borrow().len() {
if self.signers.iter().chain(&other.signers).fold(0u8, |b,s| b | s.borrow()[offset])
& ! chunk_lookups(&self.proofs_of_possession, offset) != 0u8
{
return Err(PoPError::BadPoP("Absent signer"));
}
for j in 0..8 {
let index = 8*offset+j;
self.test_count( self.get_count(index).saturating_add(other.get_count(index)) )?;
}
}
for index in 0..8*self.signers[0].borrow().len() {
self.set_count(index, self.get_count(index) + other.get_count(index));
}
self.signature.0.add_assign(&other.signature.0);
Ok(())
}
}
#[cfg(test)]
mod tests {
use rand::{thread_rng};
use super::*;
#[test]
fn proofs_of_possession() {
let msg1 = Message::new(b"ctx",b"some message");
let msg2 = Message::new(b"ctx",b"another message");
let k = |_| Keypair::<ZBLS>::generate(thread_rng());
let mut keypairs = (0..4).into_iter().map(k).collect::<Vec<_>>();
let pop = keypairs.iter().map(|k| k.public).collect::<Vec<_>>();
let dup = keypairs[3].clone();
keypairs.push(dup);
let sigs1 = keypairs.iter_mut().map(|k| k.sign(msg1)).collect::<Vec<_>>();
let mut bitpop1 = BitPoPSignedMessage::<ZBLS,_>::new(pop.clone(),msg1);
assert!( bitpop1.verify() );
for (i,sig) in sigs1.iter().enumerate().take(2) {
assert!( bitpop1.add(sig).is_ok() == (i<4));
assert!( bitpop1.verify() );
}
let mut bitpop1a = BitPoPSignedMessage::<ZBLS,_>::new(pop.clone(),msg1);
for (i,sig) in sigs1.iter().enumerate().skip(2) {
assert!( bitpop1a.add(sig).is_ok() == (i<4));
assert!( bitpop1a.verify() );
}
assert!( bitpop1.merge(&bitpop1a).is_ok() );
assert!( bitpop1.merge(&bitpop1a).is_err() );
assert!( verifiers::verify_unoptimized(&bitpop1) );
assert!( verifiers::verify_simple(&bitpop1) );
assert!( verifiers::verify_with_distinct_messages(&bitpop1,false) );
let sigs2 = keypairs.iter_mut().map(|k| k.sign(msg2)).collect::<Vec<_>>();
let mut bitpop2 = BitPoPSignedMessage::<ZBLS,_>::new(pop.clone(),msg2);
for sig in sigs2.iter().take(3) {
assert!( bitpop2.add(sig).is_ok() );
}
assert!( bitpop1.merge(&bitpop2).is_err() );
let mut multimsg = BatchAssumingProofsOfPossession::<ZBLS>::new();
multimsg.aggregate(&bitpop1);
multimsg.aggregate(&bitpop2);
assert!( multimsg.verify() );
assert!( verifiers::verify_unoptimized(&multimsg) );
assert!( verifiers::verify_simple(&multimsg) );
assert!( verifiers::verify_with_distinct_messages(&multimsg,false) );
let oops = Keypair::<ZBLS>::generate(thread_rng()).sign(msg2);
assert!( bitpop1.add_points(oops.publickey,oops.signature).is_err() );
let mut countpop1 = CountPoPSignedMessage::<ZBLS,_>::new(pop.clone(),msg1);
assert!(countpop1.signers.len() == 1);
assert!( countpop1.verify() );
assert!( countpop1.add_bitpop(&bitpop1).is_ok() );
assert!(bitpop1.signature == countpop1.signature);
assert!(countpop1.signers.len() == 1);
assert!(bitpop1.messages_and_publickeys().next() == countpop1.messages_and_publickeys().next() );
assert!( countpop1.verify() );
for (i,sig) in sigs1.iter().enumerate().take(3) {
assert!( countpop1.add(sig).is_ok() == (i<4));
assert!( countpop1.verify() );
}
assert!( countpop1.add_bitpop(&bitpop1a).is_ok() );
assert!( countpop1.add_bitpop(&bitpop1a).is_ok() );
assert!( countpop1.add_bitpop(&bitpop2).is_err() );
let countpop2 = countpop1.clone();
assert!( countpop1.merge(&countpop2).is_ok() );
assert!( verifiers::verify_unoptimized(&countpop1) );
assert!( verifiers::verify_simple(&countpop1) );
assert!( verifiers::verify_with_distinct_messages(&countpop1,false) );
countpop1.max_duplicates = 4;
assert!( countpop1.merge(&countpop2).is_err() );
}
}