Identity loading and validation

6 files changed, 346 insertions, 3 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 00a2cdc..090ec66 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -3,5 +3,7 @@ include_directories(
 )
 
 add_library(erebos
+	identity
+	pubkey
 	storage
 )
diff --git a/src/identity.cpp b/src/identity.cpp
new file mode 100644
index 0000000..0160a69
--- /dev/null
+++ b/src/identity.cpp
@@ -0,0 +1,146 @@
+#include "identity.h"
+
+#include <algorithm>
+#include <set>
+
+using namespace erebos;
+
+using std::async;
+using std::nullopt;
+using std::set;
+
+optional<Identity> Identity::load(const Ref & ref)
+{
+	return Identity::load(vector { ref });
+}
+
+optional<Identity> Identity::load(const vector<Ref> & refs)
+{
+	vector<Stored<Signed<IdentityData>>> data;
+	data.reserve(refs.size());
+
+	for (const auto & ref : refs) {
+		auto d = Stored<Signed<IdentityData>>::load(ref);
+		if (!d)
+			return nullopt;
+		data.push_back(*d);
+	}
+
+	if (auto ptr = Priv::validate(data))
+		return Identity(ptr);
+	return nullopt;
+}
+
+optional<string> Identity::name() const
+{
+	return p->name.get();
+}
+
+optional<Identity> Identity::owner() const
+{
+	return p->owner;
+}
+
+optional<IdentityData> IdentityData::load(const Ref & ref)
+{
+	auto rec = ref->asRecord();
+	if (!rec)
+		return nullopt;
+
+	vector<Stored<Signed<IdentityData>>> prev;
+	for (auto p : rec->items("SPREV"))
+		if (const auto & x = p.as<Signed<IdentityData>>())
+			prev.push_back(x.value());
+
+	auto keyIdentity = rec->item("key-id").as<PublicKey>();
+	if (!keyIdentity)
+		return nullopt;
+
+	return IdentityData {
+		.prev = std::move(prev),
+		.name = rec->item("name").asText(),
+		.owner = rec->item("owner").as<Signed<IdentityData>>(),
+		.keyIdentity = keyIdentity.value(),
+		.keyMessage = rec->item("key-msg").as<PublicKey>(),
+	};
+}
+
+bool Identity::Priv::verifySignatures(const Stored<Signed<IdentityData>> & sdata)
+{
+	if (!sdata->isSignedBy(sdata->data->keyIdentity))
+		return false;
+
+	for (const auto & p : sdata->data->prev)
+		if (!sdata->isSignedBy(p->data->keyIdentity))
+			return false;
+
+	if (sdata->data->owner &&
+			!sdata->isSignedBy(sdata->data->owner.value()->data->keyIdentity))
+		return false;
+
+	for (const auto & p : sdata->data->prev)
+		if (!verifySignatures(p))
+			return false;
+
+	return true;
+}
+
+shared_ptr<Identity::Priv> Identity::Priv::validate(const vector<Stored<Signed<IdentityData>>> & sdata)
+{
+	for (const auto & d : sdata)
+		if (!verifySignatures(d))
+			return nullptr;
+
+	auto p = new Priv {
+		.data = sdata,
+	};
+	shared_ptr<Priv> ret(p);
+
+	auto ownerProp = p->lookupProperty([]
+			(const IdentityData & d) { return d.owner.has_value(); });
+	if (ownerProp) {
+		auto owner = validate({ *ownerProp.value()->owner });
+		if (!owner)
+			return nullptr;
+		p->owner.emplace(Identity(owner));
+	}
+
+	p->name = async(std::launch::deferred, [p] () -> optional<string> {
+		if (auto d = p->lookupProperty([] (const IdentityData & d) { return d.name.has_value(); }))
+			return d.value()->name;
+		return nullopt;
+	});
+
+	return ret;
+}
+
+optional<Stored<IdentityData>> Identity::Priv::lookupProperty(
+		function<bool(const IdentityData &)> sel) const
+{
+	set<Stored<Signed<IdentityData>>> current, prop_heads;
+
+	for (const auto & d : data)
+		current.insert(d);
+
+	while (!current.empty()) {
+		Stored<Signed<IdentityData>> sdata =
+			current.extract(current.begin()).value();
+
+		if (sel(*sdata->data))
+			prop_heads.insert(sdata);
+		else
+			for (const auto & p : sdata->data->prev)
+				current.insert(p);
+	}
+
+	for (auto x = prop_heads.begin(); x != prop_heads.end(); x++)
+		for (auto y = std::next(x); y != prop_heads.end();)
+			if (y->precedes(*x))
+				y = prop_heads.erase(y);
+			else
+				y++;
+
+	if (prop_heads.begin() != prop_heads.end())
+		return (*prop_heads.begin())->data;
+	return nullopt;
+}
diff --git a/src/identity.h b/src/identity.h
new file mode 100644
index 0000000..d31951f
--- /dev/null
+++ b/src/identity.h
@@ -0,0 +1,38 @@
+#pragma once
+
+#include <erebos/identity.h>
+#include "pubkey.h"
+
+using std::function;
+using std::optional;
+using std::string;
+using std::vector;
+
+namespace erebos {
+
+class IdentityData
+{
+public:
+	static optional<IdentityData> load(const Ref &);
+
+	const vector<Stored<Signed<IdentityData>>> prev;
+	const optional<string> name;
+	const optional<Stored<Signed<IdentityData>>> owner;
+	const Stored<PublicKey> keyIdentity;
+	const optional<Stored<PublicKey>> keyMessage;
+};
+
+class Identity::Priv
+{
+public:
+	vector<Stored<Signed<IdentityData>>> data;
+	shared_future<optional<string>> name;
+	optional<Identity> owner;
+
+	static bool verifySignatures(const Stored<Signed<IdentityData>> & sdata);
+	static shared_ptr<Priv> validate(const vector<Stored<Signed<IdentityData>>> & sdata);
+	optional<Stored<IdentityData>> lookupProperty(
+			function<bool(const IdentityData &)> sel) const;
+};
+
+}
diff --git a/src/pubkey.cpp b/src/pubkey.cpp
new file mode 100644
index 0000000..3247ce2
--- /dev/null
+++ b/src/pubkey.cpp
@@ -0,0 +1,59 @@
+#include "pubkey.h"
+
+#include <stdexcept>
+
+using std::unique_ptr;
+using std::runtime_error;
+using std::string;
+
+using namespace erebos;
+
+optional<PublicKey> PublicKey::load(const Ref & ref)
+{
+	auto rec = ref->asRecord();
+	if (!rec)
+		return nullopt;
+
+	if (auto ktype = rec->item("type").asText())
+		if (ktype.value() != "ed25519")
+			throw runtime_error("unsupported key type " + ktype.value());
+
+	if (auto pubkey = rec->item("pubkey").asBinary())
+		return PublicKey(EVP_PKEY_new_raw_public_key(EVP_PKEY_ED25519, nullptr,
+					pubkey.value().data(), pubkey.value().size()));
+
+	return nullopt;
+}
+
+optional<Signature> Signature::load(const Ref & ref)
+{
+	auto rec = ref->asRecord();
+	if (!rec)
+		return nullopt;
+
+	auto key = rec->item("key").as<PublicKey>();
+	auto sig = rec->item("sig").asBinary();
+
+	if (!key || !sig)
+		return nullopt;
+
+	return Signature {
+		.key = key.value(),
+		.sig = sig.value(),
+	};
+}
+
+bool Signature::verify(const Ref & ref) const
+{
+	unique_ptr<EVP_MD_CTX, void(*)(EVP_MD_CTX*)>
+		mdctx(EVP_MD_CTX_create(), &EVP_MD_CTX_free);
+	if (!mdctx)
+		throw runtime_error("failed to create EVP_MD_CTX");
+
+	if (EVP_DigestVerifyInit(mdctx.get(), nullptr, EVP_md_null(),
+				nullptr, key->key.get()) != 1)
+		throw runtime_error("failed to initialize EVP_MD_CTX");
+
+	return EVP_DigestVerify(mdctx.get(), sig.data(), sig.size(),
+			ref.digest().arr().data(), Digest::size) == 1;
+}
diff --git a/src/pubkey.h b/src/pubkey.h
new file mode 100644
index 0000000..7fe37ec
--- /dev/null
+++ b/src/pubkey.h
@@ -0,0 +1,87 @@
+#pragma once
+
+#include "storage.h"
+
+#include <openssl/evp.h>
+
+using std::nullopt;
+using std::optional;
+using std::shared_ptr;
+
+namespace erebos {
+
+class PublicKey
+{
+	PublicKey(EVP_PKEY * key):
+		key(key, EVP_PKEY_free) {}
+public:
+	static optional<PublicKey> load(const Ref &);
+	const shared_ptr<EVP_PKEY> key;
+};
+
+class SecretKey
+{
+	SecretKey(EVP_PKEY * key, const Stored<PublicKey> & pub):
+		key(key, EVP_PKEY_free), pub(pub) {}
+
+private:
+	const shared_ptr<EVP_PKEY> key;
+	Stored<PublicKey> pub;
+};
+
+class Signature
+{
+public:
+	static optional<Signature> load(const Ref &);
+
+	bool verify(const Ref &) const;
+
+	Stored<PublicKey> key;
+	vector<uint8_t> sig;
+};
+
+template<typename T>
+class Signed
+{
+public:
+	static optional<Signed<T>> load(const Ref &);
+
+	bool isSignedBy(const Stored<PublicKey> &) const;
+
+	const Stored<T> data;
+	const vector<Stored<Signature>> sigs;
+};
+
+template<typename T>
+optional<Signed<T>> Signed<T>::load(const Ref & ref)
+{
+	auto rec = ref->asRecord();
+	if (!rec)
+		return nullopt;
+
+	auto data = rec->item("SDATA").as<T>();
+	if (!data)
+		return nullopt;
+
+	vector<Stored<Signature>> sigs;
+	for (auto item : rec->items("sig"))
+		if (auto sig = item.as<Signature>())
+			if (sig.value()->verify(data.value().ref))
+				sigs.push_back(sig.value());
+
+	return Signed {
+		.data = data.value(),
+		.sigs = sigs,
+	};
+}
+
+template<typename T>
+bool Signed<T>::isSignedBy(const Stored<PublicKey> & key) const
+{
+	for (const auto & sig : sigs)
+		if (sig->key == key)
+			return true;
+	return false;
+}
+
+}
diff --git a/src/storage.cpp b/src/storage.cpp
index 2e7feb7..d549959 100644
--- a/src/storage.cpp
+++ b/src/storage.cpp
@@ -22,6 +22,7 @@ using std::copy;
 using std::holds_alternative;
 using std::ifstream;
 using std::make_shared;
+using std::monostate;
 using std::nullopt;
 using std::runtime_error;
 using std::shared_ptr;
@@ -268,6 +269,11 @@ const Object * Ref::operator->() const
 }
 
 
+Record::Item::operator bool() const
+{
+	return !holds_alternative<monostate>(value);
+}
+
 optional<int> Record::Item::asInteger() const
 {
 	if (holds_alternative<int>(value))
@@ -351,16 +357,16 @@ const vector<Record::Item> & Record::items() const
 	return *ptr;
 }
 
-optional<Record::Item> Record::item(const string & name) const
+Record::Item Record::item(const string & name) const
 {
 	for (auto item : *ptr) {
 		if (item.name == name)
 			return item;
 	}
-	return nullopt;
+	return Item("", monostate());
 }
 
-optional<Record::Item> Record::operator[](const string & name) const
+Record::Item Record::operator[](const string & name) const
 {
 	return item(name);
 }
@@ -486,6 +492,11 @@ vector<uint8_t> Object::encode() const
 	return res;
 }
 
+optional<Object> Object::load(const Ref & ref)
+{
+	return *ref;
+}
+
 optional<Record> Object::asRecord() const
 {
 	if (holds_alternative<Record>(content))