use crate::{
Error, MergePair, NodeData, NodeId, ObjectId, Owner, Provenance, Result, TransactionId,
WriterId,
model::{MAX_ITEMS, MAX_STRING_BYTES, MAX_TRANSACTION_BYTES},
};
use chrono::{DateTime, Utc};
use ed25519_dalek::{Signature, Signer, SigningKey, Verifier, VerifyingKey};
use sha2::{Digest, Sha256};
use std::collections::BTreeSet;
const HEADER: &[u8; 10] = b"KWTX\0\x01\0\0\0\0";
const SIGNATURE_LENGTH: usize = 64;
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct ObjectDeclaration {
pub id: ObjectId,
pub length: u64,
pub sha256: [u8; 32],
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct NodeOperation {
pub id: NodeId,
pub data: NodeData,
}
#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct UnsignedTransaction {
pub writer: WriterId,
pub committed_at: DateTime<Utc>,
pub heads: Vec<TransactionId>,
pub provenance: Provenance,
pub merge_pairs: Vec<MergePair>,
pub objects: Vec<ObjectDeclaration>,
pub creates: Vec<NodeOperation>,
pub updates: Vec<NodeOperation>,
pub connections: Vec<(NodeId, NodeId)>,
}
#[derive(Clone, Debug)]
pub(crate) struct ParsedTransaction {
pub id: TransactionId,
pub unsigned: UnsignedTransaction,
}
pub(crate) fn object_hash(bytes: &[u8]) -> [u8; 32] {
Sha256::digest(bytes).into()
}
pub(crate) fn build_signed(
transaction: &UnsignedTransaction,
signing_key: &SigningKey,
) -> Result<Vec<u8>> {
validate_unsigned(transaction)?;
if transaction.writer != WriterId(signing_key.verifying_key().to_bytes()) {
return Err(Error::invalid_input(
"transaction writer does not match the signing key",
));
}
let mut bytes = encode_unsigned(transaction)?;
let signature = signing_key.sign(&bytes);
bytes.extend_from_slice(&signature.to_bytes());
if bytes.len() > MAX_TRANSACTION_BYTES {
return Err(Error::invalid_input("canonical transaction is too large"));
}
Ok(bytes)
}
pub(crate) fn parse_signed(bytes: &[u8]) -> Result<ParsedTransaction> {
if bytes.len() > MAX_TRANSACTION_BYTES {
return Err(Error::invalid_transaction("transaction is too large"));
}
if bytes.len() < HEADER.len() + SIGNATURE_LENGTH {
return Err(Error::invalid_transaction("transaction is truncated"));
}
let signature_offset = bytes.len() - SIGNATURE_LENGTH;
let unsigned_bytes = &bytes[..signature_offset];
let signature = Signature::from_bytes(
bytes[signature_offset..]
.try_into()
.map_err(|_| Error::invalid_transaction("invalid signature length"))?,
);
let unsigned = decode_unsigned(unsigned_bytes)?;
validate_unsigned(&unsigned).map_err(|error| match error {
Error::InvalidInput(message) => Error::invalid_transaction(message),
other => other,
})?;
if encode_unsigned(&unsigned)? != unsigned_bytes {
return Err(Error::invalid_transaction(
"transaction bytes are not canonical",
));
}
let verifying_key = VerifyingKey::from_bytes(&unsigned.writer.0)
.map_err(|_| Error::invalid_transaction("writer public key is invalid"))?;
verifying_key
.verify(unsigned_bytes, &signature)
.map_err(|_| Error::invalid_transaction("Ed25519 signature is invalid"))?;
Ok(ParsedTransaction {
id: TransactionId::for_signed_bytes(bytes),
unsigned,
})
}
fn validate_unsigned(transaction: &UnsignedTransaction) -> Result<()> {
transaction.provenance.validate()?;
strict_sorted(&transaction.heads, "heads")?;
strict_sorted(&transaction.merge_pairs, "merge pairs")?;
strict_sorted_by(&transaction.objects, |value| value.id, "objects")?;
strict_sorted_by(&transaction.creates, |value| value.id, "creates")?;
strict_sorted_by(&transaction.updates, |value| value.id, "updates")?;
strict_sorted(&transaction.connections, "connections")?;
let created = transaction
.creates
.iter()
.map(|operation| operation.id)
.collect::<BTreeSet<_>>();
let updated = transaction
.updates
.iter()
.map(|operation| operation.id)
.collect::<BTreeSet<_>>();
if !created.is_disjoint(&updated) {
return Err(Error::invalid_input(
"one transaction cannot create and update the same node",
));
}
for pair in &transaction.merge_pairs {
if pair.first >= pair.second {
return Err(Error::invalid_input("merge pair is not canonical"));
}
}
for operation in transaction.creates.iter().chain(transaction.updates.iter()) {
operation.data.validate()?;
strict_sorted(&operation.data.objects, "node object references")?;
}
for collection_length in [
transaction.heads.len(),
transaction.merge_pairs.len(),
transaction.objects.len(),
transaction.creates.len(),
transaction.updates.len(),
transaction.connections.len(),
] {
if collection_length > MAX_ITEMS {
return Err(Error::invalid_input(
"canonical collection exceeds the item limit",
));
}
}
Ok(())
}
fn strict_sorted<T: Ord>(values: &[T], name: &str) -> Result<()> {
if values.windows(2).any(|pair| pair[0] >= pair[1]) {
Err(Error::invalid_input(format!(
"{name} must be sorted and unique"
)))
} else {
Ok(())
}
}
fn strict_sorted_by<T, K: Ord + Copy>(
values: &[T],
key: impl Fn(&T) -> K,
name: &str,
) -> Result<()> {
if values.windows(2).any(|pair| key(&pair[0]) >= key(&pair[1])) {
Err(Error::invalid_input(format!(
"{name} must be sorted and unique"
)))
} else {
Ok(())
}
}
fn encode_unsigned(transaction: &UnsignedTransaction) -> Result<Vec<u8>> {
let mut writer = Writer::default();
writer.bytes(HEADER);
writer.bytes(&transaction.writer.0);
writer.datetime(transaction.committed_at);
writer.vector(&transaction.heads, |writer, value| {
writer.bytes(&value.0);
Ok(())
})?;
writer.provenance(&transaction.provenance)?;
writer.vector(&transaction.merge_pairs, |writer, pair| {
writer.bytes(&pair.first.0);
writer.bytes(&pair.second.0);
Ok(())
})?;
writer.vector(&transaction.objects, |writer, object| {
writer.bytes(&object.id.0);
writer.u64(object.length);
writer.bytes(&object.sha256);
Ok(())
})?;
writer.vector(&transaction.creates, Writer::node_operation)?;
writer.vector(&transaction.updates, Writer::node_operation)?;
writer.vector(&transaction.connections, |writer, (from, to)| {
writer.bytes(&from.0);
writer.bytes(&to.0);
Ok(())
})?;
Ok(writer.output)
}
fn decode_unsigned(bytes: &[u8]) -> Result<UnsignedTransaction> {
let mut reader = Reader::new(bytes);
if reader.take(HEADER.len())? != HEADER {
return Err(Error::invalid_transaction(
"unsupported transaction magic or version",
));
}
let writer = WriterId(reader.array()?);
let committed_at = reader.datetime()?;
let heads = reader.vector(|reader| Ok(TransactionId(reader.array()?)))?;
let provenance = reader.provenance()?;
let merge_pairs = reader.vector(|reader| {
Ok(MergePair {
first: TransactionId(reader.array()?),
second: TransactionId(reader.array()?),
})
})?;
let objects = reader.vector(|reader| {
Ok(ObjectDeclaration {
id: ObjectId(reader.array()?),
length: reader.u64()?,
sha256: reader.array()?,
})
})?;
let creates = reader.vector(Reader::node_operation)?;
let updates = reader.vector(Reader::node_operation)?;
let connections =
reader.vector(|reader| Ok((NodeId(reader.array()?), NodeId(reader.array()?))))?;
if !reader.remaining().is_empty() {
return Err(Error::invalid_transaction(
"canonical transaction has trailing bytes",
));
}
Ok(UnsignedTransaction {
writer,
committed_at,
heads,
provenance,
merge_pairs,
objects,
creates,
updates,
connections,
})
}
#[derive(Default)]
struct Writer {
output: Vec<u8>,
}
impl Writer {
fn bytes(&mut self, bytes: &[u8]) {
self.output.extend_from_slice(bytes);
}
fn u8(&mut self, value: u8) {
self.output.push(value);
}
fn u32(&mut self, value: u32) {
self.bytes(&value.to_be_bytes());
}
fn u64(&mut self, value: u64) {
self.bytes(&value.to_be_bytes());
}
fn i64(&mut self, value: i64) {
self.bytes(&value.to_be_bytes());
}
fn datetime(&mut self, value: DateTime<Utc>) {
self.i64(value.timestamp());
self.u32(value.timestamp_subsec_nanos());
}
fn string(&mut self, value: &str) -> Result<()> {
let length = u32::try_from(value.len())
.map_err(|_| Error::invalid_input("canonical string is too large"))?;
self.u32(length);
self.bytes(value.as_bytes());
Ok(())
}
fn vector<T>(
&mut self,
values: &[T],
mut write_item: impl FnMut(&mut Self, &T) -> Result<()>,
) -> Result<()> {
let length = u32::try_from(values.len())
.map_err(|_| Error::invalid_input("canonical vector is too large"))?;
self.u32(length);
for value in values {
write_item(self, value)?;
}
Ok(())
}
fn provenance(&mut self, provenance: &Provenance) -> Result<()> {
self.string(&provenance.author)?;
self.string(&provenance.source)?;
self.datetime(provenance.source_created_at);
self.string(&provenance.data)
}
fn node_operation(&mut self, operation: &NodeOperation) -> Result<()> {
self.bytes(&operation.id.0);
self.node_data(&operation.data)
}
fn node_data(&mut self, data: &NodeData) -> Result<()> {
self.string(&data.short_name)?;
self.string(&data.short_description)?;
self.string(&data.long_description)?;
match data.owner {
Owner::Unowned => self.u8(0),
Owner::SelfNode => self.u8(1),
Owner::Node(id) => {
self.u8(2);
self.bytes(&id.0);
}
}
for connection in data.fixed_connections {
match connection {
None => self.u8(0),
Some(id) => {
self.u8(1);
self.bytes(&id.0);
}
}
}
self.vector(&data.objects, |writer, object| {
writer.bytes(&object.0);
Ok(())
})
}
}
struct Reader<'a> {
input: &'a [u8],
offset: usize,
}
impl<'a> Reader<'a> {
fn new(input: &'a [u8]) -> Self {
Self { input, offset: 0 }
}
fn remaining(&self) -> &'a [u8] {
&self.input[self.offset..]
}
fn take(&mut self, length: usize) -> Result<&'a [u8]> {
let end = self
.offset
.checked_add(length)
.ok_or_else(|| Error::invalid_transaction("canonical length overflow"))?;
if end > self.input.len() {
return Err(Error::invalid_transaction(
"truncated canonical transaction",
));
}
let bytes = &self.input[self.offset..end];
self.offset = end;
Ok(bytes)
}
fn array<const N: usize>(&mut self) -> Result<[u8; N]> {
self.take(N)?
.try_into()
.map_err(|_| Error::invalid_transaction("invalid fixed-width field"))
}
fn u8(&mut self) -> Result<u8> {
Ok(self.array::<1>()?[0])
}
fn u32(&mut self) -> Result<u32> {
Ok(u32::from_be_bytes(self.array()?))
}
fn u64(&mut self) -> Result<u64> {
Ok(u64::from_be_bytes(self.array()?))
}
fn i64(&mut self) -> Result<i64> {
Ok(i64::from_be_bytes(self.array()?))
}
fn datetime(&mut self) -> Result<DateTime<Utc>> {
DateTime::from_timestamp(self.i64()?, self.u32()?)
.ok_or_else(|| Error::invalid_transaction("timestamp is outside the supported range"))
}
fn string(&mut self) -> Result<String> {
let length = self.u32()? as usize;
if length > MAX_STRING_BYTES {
return Err(Error::invalid_transaction("canonical string exceeds 1 MiB"));
}
String::from_utf8(self.take(length)?.to_vec())
.map_err(|_| Error::invalid_transaction("canonical string is not UTF-8"))
}
fn vector<T>(&mut self, mut read_item: impl FnMut(&mut Self) -> Result<T>) -> Result<Vec<T>> {
let count = self.u32()? as usize;
if count > MAX_ITEMS {
return Err(Error::invalid_transaction(
"canonical vector exceeds the item limit",
));
}
let mut values = Vec::with_capacity(count.min(self.remaining().len()));
for _ in 0..count {
values.push(read_item(self)?);
}
Ok(values)
}
fn provenance(&mut self) -> Result<Provenance> {
Ok(Provenance {
author: self.string()?,
source: self.string()?,
source_created_at: self.datetime()?,
data: self.string()?,
})
}
fn node_operation(&mut self) -> Result<NodeOperation> {
Ok(NodeOperation {
id: NodeId(self.array()?),
data: self.node_data()?,
})
}
fn node_data(&mut self) -> Result<NodeData> {
let short_name = self.string()?;
let short_description = self.string()?;
let long_description = self.string()?;
let owner = match self.u8()? {
0 => Owner::Unowned,
1 => Owner::SelfNode,
2 => Owner::Node(NodeId(self.array()?)),
_ => return Err(Error::invalid_transaction("unknown owner tag")),
};
let mut fixed_connections = [None; 3];
for slot in &mut fixed_connections {
*slot = match self.u8()? {
0 => None,
1 => Some(NodeId(self.array()?)),
_ => return Err(Error::invalid_transaction("unknown fixed-connection tag")),
};
}
let objects = self.vector(|reader| Ok(ObjectId(reader.array()?)))?;
Ok(NodeData {
short_name,
short_description,
long_description,
owner,
fixed_connections,
objects,
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use chrono::TimeZone;
fn fixture() -> (UnsignedTransaction, SigningKey) {
let signing_key = SigningKey::from_bytes(&[7; 32]);
let timestamp = Utc.timestamp_opt(1_700_000_000, 123).unwrap();
(
UnsignedTransaction {
writer: WriterId(signing_key.verifying_key().to_bytes()),
committed_at: timestamp,
heads: Vec::new(),
provenance: Provenance {
author: "Kennedy".into(),
source: "wire-golden".into(),
source_created_at: timestamp,
data: "fixed".into(),
},
merge_pairs: Vec::new(),
objects: vec![ObjectDeclaration {
id: ObjectId([1, 2, 3, 4, 5, 6]),
length: 3,
sha256: object_hash(b"abc"),
}],
creates: vec![NodeOperation {
id: NodeId([6, 5, 4, 3, 2, 1]),
data: NodeData {
short_name: "Node".into(),
short_description: "short".into(),
long_description: "long description".into(),
owner: Owner::SelfNode,
fixed_connections: [None; 3],
objects: vec![ObjectId([1, 2, 3, 4, 5, 6])],
},
}],
updates: Vec::new(),
connections: Vec::new(),
},
signing_key,
)
}
#[test]
fn canonical_round_trip_is_deterministic() {
let (transaction, signing_key) = fixture();
let first = build_signed(&transaction, &signing_key).unwrap();
assert_eq!(first, build_signed(&transaction, &signing_key).unwrap());
assert_eq!(&first[..10], b"KWTX\0\x01\0\0\0\0");
let parsed = parse_signed(&first).unwrap();
assert_eq!(parsed.unsigned, transaction);
assert_eq!(parsed.id, TransactionId::for_signed_bytes(&first));
}
#[test]
fn tampering_and_noncanonical_order_are_rejected() {
let (mut transaction, signing_key) = fixture();
let mut signed = build_signed(&transaction, &signing_key).unwrap();
let last = signed.len() - 1;
signed[last] ^= 1;
assert!(parse_signed(&signed).is_err());
transaction.heads = vec![TransactionId([2; 32]), TransactionId([1; 32])];
assert!(build_signed(&transaction, &signing_key).is_err());
}
}