//! Encrypted structures of the Glycos graph.
//! This module represents ciphertext space of the Glycos graph.
//!
//! One can go from clear text to cipher text space via the Builders in this module, and vice versa
//! using the `decrypt` methods on the cipher text representation.

use std::borrow::Borrow;
use std::fmt;
use std::str;

use bincode::{self, deserialize, serialize};
use bytes::{BufMut, BytesMut};
use ring::{self, aead, rand};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use sha3::{Digest, Sha3_256};
use tiny_keccak::Hasher;

use crate::crypto::ec::*;
use crate::graph::primitives;

#[derive(Debug, Serialize, Deserialize)]
struct SerializableVertex {
    recogniser: [u8; 32],
    owner_recogniser: [u8; 32],
    acl: Vec<([u8; 32], Vec<u8>)>, // TODO: maybe make this generic over slice and vec
    acl_ephemeral: [u8; 32],
    value: Option<(Vec<u8>, Vec<u8>)>,
    clock: u32,
    signature: ([u8; 32], [u8; 32]),
}

/// Represents a sealed vertex.
///
/// It can be opened to a primitive `Vertex` by calling `decrypt`.
#[derive(Clone)]
pub struct Vertex {
    owner: PublicKey,
    owner_recogniser: Recogniser,
    owner_cek: Option<Vec<u8>>,
    recogniser: Recogniser,
    acl: VertexControlList,
    acl_ephemeral: PublicKey,
    value: Option<Vec<u8>>,
    pub clock: u32,
    signature: SchnorrSignature,
}

impl fmt::Debug for Vertex {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(
            f,
            "cryptograph::Vertex {{ {} }}",
            z85::encode(&self.identifier())
        )
    }
}

/// There are two error events in this module.
///
/// There is the case that a vertex or edge cannot be deserialized,
/// and there are all cryptographic errors.
///
/// The cryptographic errors are kept general for security purposes:
/// this way an attacker cannot get feedback if he would get his hands on the error messages.
#[derive(Debug, thiserror::Error)]
pub enum CryptoGraphError {
    #[error("Deserialization error {0}")]
    DeserializationError(#[from] bincode::Error),
    #[error("Cryptographic error {0}")]
    CryptographicError(#[from] ring::error::Unspecified),
}

impl Serialize for Vertex {
    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
        s.serialize_bytes(&self.as_bytes())
    }
}

impl<'s> Deserialize<'s> for Vertex {
    fn deserialize<D: Deserializer<'s>>(deser: D) -> Result<Vertex, D::Error> {
        let bytes = Vec::deserialize(deser)?;
        Ok(Vertex::from_bytes(&bytes).unwrap())
    }
}

pub trait AsOwner {
    fn as_owner_bytes(&self) -> [u8; 32];
}

impl Vertex {
    /// Verifies that the signature of this `Vertex` is correct.
    ///
    /// Returns true when the signature is valid, false otherwise.
    /// Call this method after receiving a vertex, and do not consume it if it's invalid.
    pub fn verify_signature(&self) -> bool {
        let data = signature_data(
            &self.owner_cek,
            &self.owner_recogniser,
            &self.recogniser,
            &self.acl,
            &self.acl_ephemeral,
            &self.value,
            self.clock,
        );
        self.owner.verify(&self.signature, &data)
    }

    /// Checks `sk`'s eligibility for appending to this vertex.
    ///
    /// When eligible, it returns the private key with which an Edge can be created using
    /// `EdgeBuilder`.
    pub fn check_acl(&self, sk: &PrivateKey) -> crate::crypto::Result<Option<PrivateKey>> {
        let recovery = EphemeralKeyRecovery::new(&self.recogniser, sk)?;
        let owner_recovery = EphemeralKeyRecovery::new(&self.owner_recogniser, sk)?;
        match owner_recovery.recognise(&self.owner)? {
            None => recovery.recognise_one(self.acl()),
            found => Ok(found),
        }
    }

    /// Decrypts the vertex *with the knowledge of the ephemeral key*.
    pub fn decrypt_direct(&self, key: &PrivateKey) -> crate::crypto::Result<primitives::Vertex> {
        // There should be a shortcut if coming from `decrypt`...
        let value = if let Some(mut value) = self.value.clone() {
            let public = key.compute_public_key()?;
            let kek = derive_kek(key.agree_with(&self.acl_ephemeral)?);

            let nonce = [0u8; 12];

            let kek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &kek)?);

            let (_, cek) = self
                .acl_cek_iter()
                .find(|(pk, _)| **pk == public)
                .ok_or(::ring::error::Unspecified)?;

            let mut cek = cek.clone();
            let cek = kek.open_in_place(
                aead::Nonce::assume_unique_for_key(nonce),
                aead::Aad::empty(),
                &mut cek,
            )?;
            let cek = aead::LessSafeKey::new(aead::UnboundKey::new(
                ALGORITHM,
                &cek[..ALGORITHM.key_len()],
            )?);

            let len = cek
                .open_in_place(
                    aead::Nonce::assume_unique_for_key(nonce),
                    aead::Aad::empty(),
                    &mut value,
                )?
                .len();
            value.truncate(len - ALGORITHM.tag_len());

            Some(value)
        } else {
            None
        };

        Ok(primitives::Vertex {
            owner: self.owner.clone(),
            value,
            clock: self.clock,
            edge_access_key: Some(key.clone()),
        })
    }

    /// Decrypts this `Vertex` to a `primitives::Vertex`
    /// if `master` is listed in the access control list.
    ///
    /// Otherwise `Err(ring::error::Unspecified)` is returned
    pub fn decrypt(&self, master: &PrivateKey) -> crate::crypto::Result<primitives::Vertex> {
        let key = self.check_acl(master)?;
        let key = key.ok_or(ring::error::Unspecified)?;
        self.decrypt_direct(&key)
    }

    fn acl<'s>(&'s self) -> impl Iterator<Item = &PublicKey> + 's {
        vec![&self.owner].into_iter().chain(self.acl.iter())
    }

    fn acl_cek_iter<'s>(&'s self) -> impl Iterator<Item = (&PublicKey, &Vec<u8>)> + 's {
        vec![(&self.owner, self.owner_cek.as_ref().unwrap())]
            .into_iter()
            .chain(self.acl.cek_iter())
    }

    /// Serializes the edge.
    pub fn as_bytes(&self) -> Vec<u8> {
        let value = self.value.clone().map(|v| {
            let cek = self
                .owner_cek
                .clone()
                .expect("Inconsistent state: value but no owner cek");
            (cek, v)
        });
        serialize(&SerializableVertex {
            recogniser: self.recogniser.bytes(),
            owner_recogniser: self.owner_recogniser.bytes(),
            acl: self
                .acl
                .inner
                .iter()
                .map(|(k, cek)| (k.bytes(), cek.clone()))
                .collect(),
            acl_ephemeral: self.acl_ephemeral.bytes(),
            value,
            clock: self.clock,
            signature: self.signature.bytes(),
        })
        .expect("Could not serialize valid Vertex")
    }

    /// Deserializes the edge.
    pub fn from_bytes(s: &[u8]) -> Result<Vertex, CryptoGraphError> {
        let de = deserialize::<SerializableVertex>(s)?;
        let signature = SchnorrSignature::from_bytes(de.signature);
        let clock = de.clock;
        let (owner_cek, value) = if let Some(v) = de.value {
            (Some(v.0), Some(v.1))
        } else {
            (None, None)
        };

        let acl = VertexControlList {
            inner: de
                .acl
                .into_iter()
                .map(|(k, cek)| {
                    let k = PublicKey::from_bytes(&k)?;
                    Ok((k, cek))
                })
                .collect::<crate::crypto::Result<_>>()?,
        };

        let recogniser = Recogniser::from_bytes(de.recogniser);
        let owner_recogniser = Recogniser::from_bytes(de.owner_recogniser);
        let acl_ephemeral = PublicKey::from_bytes(&de.acl_ephemeral)?;
        let data = signature_data(
            &owner_cek,
            &owner_recogniser,
            &recogniser,
            &acl,
            &acl_ephemeral,
            &value,
            clock,
        );

        Ok(Vertex {
            owner: signature.recover_public_key(data)?,
            owner_recogniser,
            owner_cek,
            recogniser,
            acl,
            acl_ephemeral,
            value,
            clock,
            signature,
        })
    }

    /// Return the identifier
    pub fn identifier(&self) -> [u8; 32] {
        self.owner.identifier()
    }

    // TODO: Edge::to should become identifier, not as_owner_bytes.
    pub fn owner_bytes(&self) -> [u8; 32] {
        self.owner.bytes()
    }
}

impl AsOwner for Vertex {
    fn as_owner_bytes(&self) -> [u8; 32] {
        self.owner_bytes()
    }
}

impl AsOwner for [u8; 32] {
    fn as_owner_bytes(&self) -> [u8; 32] {
        *self
    }
}

impl<'a, T> AsOwner for &'a T
where
    T: AsOwner,
{
    fn as_owner_bytes(&self) -> [u8; 32] {
        (*self).as_owner_bytes()
    }
}

/// A builder for `Vertex`'.
///
/// Building a Vertex takes several distinct steps:
///
/// 1) Generate an owner key (taken care of by `VertexBuilder::new()`);
/// 2) Optionally *permit* access to others;
/// 3) Assign an optional *value*;
/// 4) Sign the vertex (using `VertexBuilder::build()`).
///
/// The signing operation will return the associated owner key.
///
/// # Examples
///
/// ```
/// use glycos::crypto::ec::*;
/// use glycos::graph::cryptograph::*;
///
/// let rng = ring::rand::SystemRandom::new();
/// let alice = PrivateKey::generate(&rng).expect("Generate key");
/// let public = alice.compute_public_key().unwrap();
/// let (v, k): (Vertex, PrivateKey) = VertexBuilder::new(&rng, &public).unwrap()
///     .build(&rng, &alice).unwrap();
///
/// assert_eq!(v.check_acl(&alice).unwrap().unwrap(), k,
///            "`build` should return the owner key.");
/// ```
pub struct VertexBuilder {
    derived_public: PublicKey,
    owner_recogniser: Recogniser,
    derivation_builder: EphemeralKeyDerivationBuilder,
    value: Option<Vec<u8>>,
    owner_cek: Option<Vec<u8>>,
    acl: VertexControlList,
    cek: ContentEncryptionKey,
    kek_ephemeral: PrivateKey,
    clock: u32,
}

impl VertexBuilder {
    /// Start the VertexBuilder process.
    ///
    /// The `master_key` is the public key of the owner of the generated vertex.
    /// The corresponding private key should be provided at the end of the VertexBuilder, in
    /// `VertexBuilder::build()`.
    pub fn new<R: rand::SecureRandom>(
        rng: &R,
        master_key: &PublicKey,
    ) -> crate::crypto::Result<Self> {
        let derivation_builder = EphemeralKeyDerivationBuilder::default(rng)?;
        let derived_public = derivation_builder.derive(master_key)?;
        let owner_recogniser = derivation_builder.finish()?;

        let derivation_builder = EphemeralKeyDerivationBuilder::default(rng)?;
        let mut cek = ContentEncryptionKey::default();
        rng.fill(&mut cek)?;

        let kek_ephemeral = PrivateKey::generate(rng)?;

        Ok(Self {
            derived_public,
            owner_recogniser,
            derivation_builder,
            value: None,
            owner_cek: None,
            acl: VertexControlList::default(),
            cek,
            kek_ephemeral,
            clock: 0,
        })
    }

    /// Builds a VertexBuild from an existing vertex.
    ///
    /// **This destroys the current ACL**, since this cannot be recovered!
    /// Use `VertexBuilder::permit()` to reinstantiate.
    ///
    /// **This operation also destroys all edges**,
    /// rebuild them using EdgeBuilder!
    pub fn update_vertex<R: rand::SecureRandom>(
        rng: &R,
        v: &Vertex,
        sk: &PrivateKey,
    ) -> crate::crypto::Result<Self> {
        // XXX With some kind of state machine, we should be able to avoid operations
        // when they are not necessary.
        let derivation_builder = EphemeralKeyDerivationBuilder::default(rng)?;
        let mut cek = ContentEncryptionKey::default();
        rng.fill(&mut cek)?;

        let kek_ephemeral = PrivateKey::generate(rng)?;

        let b = Self {
            derived_public: v.owner.clone(),
            owner_recogniser: v.owner_recogniser.clone(),
            derivation_builder,
            value: None,
            owner_cek: None,
            acl: VertexControlList::default(),
            cek,
            kek_ephemeral,
            clock: v.clock + 1,
        };

        let decrypted = v.decrypt(&sk)?;
        let b = if let Some(value) = decrypted.value {
            b.value(value)?
        } else {
            b
        };

        Ok(b)
    }

    /// Set the **optional** value of the Vertex to a binary string.
    ///
    /// # Examples
    ///
    /// ```
    /// use glycos::crypto::ec::*;
    /// use glycos::graph::cryptograph::*;
    ///
    /// let rng = ring::rand::SystemRandom::new();
    /// let alice = PrivateKey::generate(&rng).expect("Generate key");
    /// let public = alice.compute_public_key().unwrap();
    /// let (v, k): (Vertex, PrivateKey) = VertexBuilder::new(&rng, &public).unwrap()
    ///     .value(b"foaf:Person").unwrap()
    ///     .build(&rng, &alice).unwrap();
    /// ```
    pub fn value<Val: AsRef<[u8]>>(mut self, v: Val) -> crate::crypto::Result<Self> {
        let v = v.as_ref();
        let mut value = vec![0u8; v.len() + ALGORITHM.tag_len()];
        value[0..v.len()].clone_from_slice(v);

        let nonce = [0u8; 12];
        let cek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &self.cek)?);
        cek.seal_in_place_append_tag(
            aead::Nonce::assume_unique_for_key(nonce),
            aead::Aad::empty(),
            &mut value,
        )?;

        self.value = Some(value);
        self.owner_cek = Some(self.encrypt_cek(&self.derived_public)?);
        Ok(self)
    }

    /// Permit Bob to append data to this vertex
    pub fn permit(mut self, bob: &PublicKey) -> crate::crypto::Result<Self> {
        let bob = self.derivation_builder.derive(bob)?;

        let encrypted_cek = self.encrypt_cek(&bob)?;

        self.acl.add(bob, encrypted_cek);
        Ok(self)
    }

    /// Permit many to append data to this vertex
    pub fn permit_many<Acl, Key>(mut self, keys: Acl) -> crate::crypto::Result<Self>
    where
        Key: Borrow<PublicKey>,
        Acl: AsRef<[Key]>,
    {
        for k in keys.as_ref() {
            self = self.permit(k.borrow())?;
        }
        Ok(self)
    }

    fn encrypt_cek(&self, bob: &PublicKey) -> crate::crypto::Result<Vec<u8>> {
        let agreed = self.kek_ephemeral.agree_with(bob)?;
        let kek = derive_kek(agreed);
        let kek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &kek)?);
        let mut encrypted_cek = vec![0u8; self.cek.len() + ALGORITHM.tag_len()];
        encrypted_cek[0..self.cek.len()].clone_from_slice(&self.cek);
        let nonce = [0u8; 12];
        kek.seal_in_place_append_tag(
            aead::Nonce::assume_unique_for_key(nonce),
            aead::Aad::empty(),
            &mut encrypted_cek,
        )?;
        Ok(encrypted_cek)
    }

    /// Finish the Vertex.
    ///
    /// The passed private key should be the corresponding `PrivateKey` to the `PublicKey` passed
    /// in `VertexBuilder::new()`.
    pub fn build<R: rand::SecureRandom>(
        self,
        rng: &R,
        sk: &PrivateKey,
    ) -> crate::crypto::Result<(Vertex, PrivateKey)> {
        let derived_recogniser = self.derivation_builder.finish()?;
        let derived_private = EphemeralKeyRecovery::new(&self.owner_recogniser, sk)
            .unwrap()
            .recognise(&self.derived_public)?
            .ok_or(ring::error::Unspecified)?;

        let acl_ephemeral = self.kek_ephemeral.compute_public_key()?;
        let data = signature_data(
            &self.owner_cek,
            &self.owner_recogniser,
            &derived_recogniser,
            &self.acl,
            &acl_ephemeral,
            &self.value,
            self.clock,
        );
        let signature = derived_private.sign(rng, &data)?;

        Ok((
            Vertex {
                owner: self.derived_public,
                owner_recogniser: self.owner_recogniser,
                owner_cek: self.owner_cek,
                recogniser: derived_recogniser,
                acl: self.acl,
                acl_ephemeral,
                value: self.value,
                clock: self.clock,
                signature,
            },
            derived_private,
        ))
    }
}

fn signature_data(
    owner_cek: &Option<Vec<u8>>,
    owner_recogniser: &Recogniser,
    recogniser: &Recogniser,
    acl: &VertexControlList,
    acl_ephemeral: &PublicKey,
    value: &Option<Vec<u8>>,
    clock: u32,
) -> BytesMut {
    // (ACL, value, clock)
    let mut data = BytesMut::with_capacity(
        owner_cek.as_ref().map(Vec::len).unwrap_or(0)
        + 32 // Recogniser
        + 32 // Recogniser
        + acl.size()
        + 32 // ACL ephemeral
        + value.as_ref().map(Vec::len).unwrap_or(0)
        + 4,
    );

    if let Some(owner_cek) = owner_cek {
        data.extend(owner_cek);
    }

    data.extend(&owner_recogniser.bytes());
    data.extend(&recogniser.bytes());
    for (key, cek) in acl.cek_iter() {
        data.extend(&key.bytes());
        data.extend(cek);
    }
    data.extend(&acl_ephemeral.bytes());

    if let Some(value) = value {
        data.extend(value);
    }
    data.put_u32_le(clock);
    data
}

#[derive(Clone, Debug, Default, PartialEq, Eq)]
struct VertexControlList {
    inner: Vec<(PublicKey, Vec<u8>)>,
}

impl VertexControlList {
    pub fn size(&self) -> usize {
        self.inner
            .iter()
            .fold(32 * self.inner.len(), |sum, (_pk, v)| sum + v.len())
    }

    pub fn add(&mut self, bob: PublicKey, cek: Vec<u8>) {
        self.inner.push((bob, cek));
    }

    pub fn iter<'s>(&'s self) -> impl Iterator<Item = &PublicKey> + 's {
        self.inner.iter().map(|(k, _cek)| k)
    }

    pub fn cek_iter<'s>(&'s self) -> impl Iterator<Item = (&PublicKey, &Vec<u8>)> + 's {
        self.inner.iter().map(|(k, cek)| (k, cek))
    }
}

static ALGORITHM: &aead::Algorithm = &aead::CHACHA20_POLY1305;
const EDGE_HKDF_INFO: &[u8] = &[0x65, 0x64, 0x67, 0x65];
fn derive_kek(agreed: [u8; 32]) -> Vec<u8> {
    // XXX: Maybe update to cSHAKE some day.
    let mut shake = tiny_keccak::Shake::v256();
    shake.update(EDGE_HKDF_INFO);
    shake.update(&agreed);
    let mut kek = vec![0u8; ALGORITHM.key_len()];
    shake.finalize(&mut kek);
    kek
}

type ContentEncryptionKey = [u8; 256 / 8];

/// Represents a sealed `Edge` from a `Vertex` \\(V_a\\) to \\(V_b\\).
/// \\(V_a\\) and \\(V_b\\) are *a priori* unknown; the `Edge` can be opened through `Edge::decrypt`.
///
/// Creating a new `Edge` can be done through `EdgeBuilder`.
#[derive(Clone)]
pub struct Edge {
    acl_ephemeral: PublicKey,
    acl: Vec<(PublicKey, Vec<u8>)>,
    spo: Vec<u8>,
    signature: AbeRingSignature,
}

impl PartialEq for Edge {
    fn eq(&self, other: &Edge) -> bool {
        self.acl_ephemeral == other.acl_ephemeral
    }
}

#[derive(Debug, Serialize, Deserialize)]
struct SerializableEdge {
    acl_ephemeral: [u8; 32],
    acl: Vec<([u8; 32], Vec<u8>)>,
    spo: Vec<u8>,
    signature: Vec<u8>,
}

impl fmt::Debug for Edge {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "Edge {{ ACL with {} elements }}", self.acl.len())
    }
}

impl Serialize for Edge {
    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
        s.serialize_bytes(&self.as_bytes())
    }
}

impl<'s> Deserialize<'s> for Edge {
    fn deserialize<D: Deserializer<'s>>(deser: D) -> Result<Edge, D::Error> {
        let bytes = Vec::deserialize(deser)?;
        Ok(Edge::from_bytes(&bytes).unwrap())
    }
}

impl Edge {
    /// With the correct `PrivateKey` retrieved through the associated `Vertex`'s `check_acl()`
    /// method, this decrypts the sealed `Edge` to a `primitives::Edge`.
    pub fn decrypt(&self, sk: &PrivateKey) -> crate::crypto::Result<primitives::Edge> {
        let pk = sk.compute_public_key()?;
        let &(_, ref cek) = self
            .acl
            .iter()
            .find(|(acl_pk, _)| *acl_pk == pk)
            .ok_or(::ring::error::Unspecified)?;

        let kek = derive_kek(sk.agree_with(&self.acl_ephemeral)?);
        let kek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &kek)?);

        let nonce = [0u8; 12];
        let mut cek = cek.clone();
        let cek = kek.open_in_place(
            aead::Nonce::assume_unique_for_key(nonce),
            aead::Aad::empty(),
            &mut cek,
        )?;

        let mut spo = self.spo.clone();
        let cek = aead::LessSafeKey::new(aead::UnboundKey::new(
            ALGORITHM,
            &cek[..ALGORITHM.key_len()],
        )?);
        let plaintext = cek.open_in_place(
            aead::Nonce::assume_unique_for_key(nonce),
            aead::Aad::empty(),
            &mut spo,
        )?;
        let plaintext = &plaintext[..plaintext.len() - ALGORITHM.tag_len()];

        let subject = &plaintext[0..32];
        let subject = PublicKey::from_bytes(subject)?;
        let object = &plaintext[32..64];
        let object = PublicKey::from_bytes(object)?;
        let predicate = &plaintext[64..];
        let predicate = str::from_utf8(predicate).expect("BUG").into();
        Ok(primitives::Edge {
            subject,
            predicate,
            object,
        })
    }

    pub fn vertex_keys(&self) -> impl Iterator<Item = [u8; 32]> + '_ {
        self.acl.iter().map(|&(ref pk, _)| {
            let digest = Sha3_256::digest(&pk.bytes());
            let mut res = [0u8; 32];
            res.copy_from_slice(&digest);
            res
        })
    }

    pub fn key(&self) -> [u8; 32] {
        let digest = Sha3_256::digest(&self.spo);
        let mut res = [0u8; 32];
        res.copy_from_slice(&digest);
        res
    }

    /// Serializes the `Edge`.
    pub fn as_bytes(&self) -> Vec<u8> {
        serialize(&SerializableEdge {
            acl_ephemeral: self.acl_ephemeral.bytes(),
            acl: self
                .acl
                .iter()
                .map(|&(ref pk, ref val)| (pk.bytes(), val.clone()))
                .collect(),
            spo: self.spo.clone(),
            signature: self.signature.serialize(),
        })
        .expect("Could not serialize Edge")
    }

    /// Deserializes an `Edge` from a vector of bytes.
    pub fn from_bytes<B: AsRef<[u8]>>(bytes: B) -> Result<Edge, CryptoGraphError> {
        let e = deserialize::<SerializableEdge>(bytes.as_ref())?;

        Ok(Edge {
            acl_ephemeral: PublicKey::from_bytes(&e.acl_ephemeral)?,
            acl: e
                .acl
                .into_iter()
                .map(|(pk, val)| (PublicKey::from_bytes(&pk).expect("Invalid public key"), val))
                .collect(),
            spo: e.spo,
            signature: AbeRingSignature::deserialize(e.signature)?,
        })
    }

    /// Verifies that the signature of this `Edge` is correct.
    ///
    /// Returns true when the signature is valid, false otherwise.
    /// Call this method after receiving an edge, and do not consume it if it's invalid.
    pub fn verify_signature(&self) -> bool {
        let mut data = BytesMut::with_capacity(
            self.acl.iter().map(|(_key, cek)| cek.len()).sum::<usize>() + self.spo.len(),
        );
        for (_key, cek) in self.acl.iter() {
            data.extend(cek);
        }
        data.extend(&self.spo);
        self.signature.verify(&data)
    }

    /// Verifies whether `v` is the valid subject of this Edge.
    pub fn verify_is_subject(&self, v: &Vertex) -> bool {
        let v_acl: Vec<_> = v.acl().collect();
        let e_acl: Vec<_> = self.acl.iter().map(|a| &a.0).collect();
        self.verify_signature() && v_acl == e_acl
    }
}

/// Builder for Edges.
/// The process of creating an `Edge` is a bit more involved than for Vertices,
/// although the interface is very alike.
///
/// 1) Select the `from` and `to` edges.
/// 2) Add the mandatory `label`;
///
/// Before adding from, to, and label, the `build` method *will not be available* at compile time.
///
/// # Examples
///
/// ```
/// use glycos::crypto::ec::*;
/// use glycos::graph::cryptograph::*;
///
/// let rng = ring::rand::SystemRandom::new();
/// let alice = PrivateKey::generate(&rng).expect("Generate key");
/// let public = alice.compute_public_key().unwrap();
/// let (v, k) = VertexBuilder::new(&rng, &public).unwrap()
///     .build(&rng, &alice).unwrap();
/// let (v2, _k) = VertexBuilder::new(&rng, &public).unwrap()
///     .value("foaf:Person").unwrap()
///     .build(&rng, &alice).unwrap();
///
/// let e = EdgeBuilder::default()
///     .from(&v)
///     .to(&v2)
///     .label("a")
///     .build(&rng, &k).unwrap();
/// ```
pub struct EdgeBuilder<'r, F, T, L> {
    from: F,
    ring_builder: Vec<&'r PublicKey>,
    to: T,
    label: L,
}

impl<'r> Default for EdgeBuilder<'r, (), (), ()> {
    fn default() -> EdgeBuilder<'r, (), (), ()> {
        EdgeBuilder {
            from: (),
            ring_builder: vec![],
            to: (),
            label: (),
        }
    }
}

impl<'r, F, T, L> EdgeBuilder<'r, F, T, L> {
    /// Sets \\(V_a\\) in the Edge \\(V_a \rightarrow V_b\\).
    pub fn from(self, vertex: &'r Vertex) -> EdgeBuilder<'r, [u8; 32], T, L> {
        let EdgeBuilder {
            to,
            label,
            mut ring_builder,
            ..
        } = self;
        ring_builder.extend(vertex.acl());
        EdgeBuilder {
            from: vertex.owner.bytes(),
            to,
            label,
            ring_builder,
        }
    }

    /// Sets \\(V_b\\) in the Edge \\(V_a \rightarrow V_b\\).
    pub fn to<V: AsOwner>(self, vertex: V) -> EdgeBuilder<'r, F, [u8; 32], L> {
        let EdgeBuilder {
            from,
            label,
            ring_builder,
            ..
        } = self;
        EdgeBuilder {
            to: vertex.as_owner_bytes(),
            from,
            label,
            ring_builder,
        }
    }

    /// Sets the mandatory edge label in the labeled graph.
    pub fn label<Label: AsRef<str>>(self, label: Label) -> EdgeBuilder<'r, F, T, Label> {
        let EdgeBuilder {
            from,
            to,
            ring_builder,
            ..
        } = self;
        EdgeBuilder {
            from,
            ring_builder,
            to,
            label,
        }
    }
}

impl<'r, L: AsRef<str>> EdgeBuilder<'r, [u8; 32], [u8; 32], L> {
    /// Build the actual Edge.
    ///
    /// The secret key should come from `VertexBuilder::build()` or equivalently from
    /// `Vertex::check_acl()`.
    pub fn build<R: rand::SecureRandom>(
        self,
        rng: &R,
        sk: &PrivateKey,
    ) -> crate::crypto::Result<Edge> {
        // XXX: can we have the ring signer as field of EdgeBuilder?
        // May be cleaner, but have to find a way to remove sk's
        // public key from it (or not add it in the first place)
        //
        // If we want this really fancy, compile time check would be
        // *awesome*

        let signing_public_key = sk.compute_public_key()?;
        let mut signer = AbeRingSigner::default();
        let mut data = BytesMut::default();

        let EdgeBuilder {
            from,
            to,
            label,
            ring_builder,
        } = self;

        let public_key_in_ring = ring_builder
            .iter()
            .enumerate()
            .find(|(_i, key)| ***key == signing_public_key)
            .map(|(i, _key)| i)
            .unwrap_or_else(|| ring_builder.len());

        debug_assert!(
            public_key_in_ring < ring_builder.len(),
            "Signing ring with illegal key!"
        );

        let keys: Vec<_> = ring_builder
            .clone()
            .into_iter()
            .filter(|key| **key != signing_public_key)
            .collect();

        signer.push_many(keys, rng)?;

        // Calculate key/ACL
        let mut cek = ContentEncryptionKey::default();
        rng.fill(&mut cek)?;

        let ephemeral = PrivateKey::generate(rng)?;

        // XXX: check ring_builder for duplicates, since that would imply (nonce, key) reuse.
        let nonce = [0u8; 12];
        let acl = ring_builder
            .iter()
            .map(|&pk| {
                let agreed = ephemeral.agree_with(pk)?;

                // Expand key
                let kek = derive_kek(agreed);

                // Use kek to encrypt and authenticate the cek
                let kek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &kek)?);
                let mut encrypted_cek = vec![0u8; cek.len() + ALGORITHM.tag_len()];
                encrypted_cek[0..cek.len()].clone_from_slice(&cek);
                kek.seal_in_place_append_tag(
                    aead::Nonce::assume_unique_for_key(nonce),
                    aead::Aad::empty(),
                    &mut encrypted_cek,
                )?;
                Ok((pk.clone(), encrypted_cek))
            })
            .collect::<crate::crypto::Result<Vec<(PublicKey, Vec<u8>)>>>()?;

        // Encrypt s, p, o
        let label = label.as_ref();
        // XXX: distinguishability on ciphertext length
        let mut spo = vec![0u8; from.len() + to.len() + label.len() + ALGORITHM.tag_len()];
        spo[0..from.len()].clone_from_slice(&from);
        spo[from.len()..from.len() + to.len()].clone_from_slice(&to);
        spo[from.len() + to.len()..from.len() + to.len() + label.len()]
            .clone_from_slice(label.as_bytes());

        let cek = aead::LessSafeKey::new(aead::UnboundKey::new(ALGORITHM, &cek)?);
        cek.seal_in_place_append_tag(
            aead::Nonce::assume_unique_for_key(nonce),
            aead::Aad::empty(),
            &mut spo,
        )?;

        for (_key, cek) in acl.iter() {
            data.extend(cek);
        }
        data.extend(&spo);
        let signature = signer.finish(sk, public_key_in_ring, rng, &data)?;

        let e = Edge {
            acl_ephemeral: ephemeral.compute_public_key()?,
            acl,
            spo,
            signature,
        };
        Ok(e)
    }
}

#[cfg(test)]
#[path = "cryptograph_tests.rs"]
mod tests;