Identity loading and validation

9 files changed, 466 insertions, 5 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 66406b1..77c775f 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -7,6 +7,7 @@ set(CMAKE_CXX_EXTENSIONS OFF)
 
 find_package(Threads REQUIRED)
 find_package(ZLIB REQUIRED)
+find_package(OpenSSL REQUIRED)
 find_library(B2_LIBRARY b2 REQUIRED)
 
 add_subdirectory(src)
diff --git a/include/erebos/identity.h b/include/erebos/identity.h
new file mode 100644
index 0000000..7b66d82
--- /dev/null
+++ b/include/erebos/identity.h
@@ -0,0 +1,23 @@
+#pragma once
+
+#include <erebos/storage.h>
+
+namespace erebos {
+
+class Identity
+{
+public:
+	static std::optional<Identity> load(const Ref &);
+	static std::optional<Identity> load(const std::vector<Ref> &);
+
+	std::optional<std::string> name() const;
+	std::optional<Identity> owner() const;
+
+private:
+	struct Priv;
+	const std::shared_ptr<const Priv> p;
+	Identity(const Priv * p): p(p) {}
+	Identity(std::shared_ptr<const Priv> && p): p(std::move(p)) {}
+};
+
+}
diff --git a/include/erebos/storage.h b/include/erebos/storage.h
index ae899f5..ea0e894 100644
--- a/include/erebos/storage.h
+++ b/include/erebos/storage.h
@@ -14,6 +14,7 @@ class Storage;
 class Digest;
 class Ref;
 class Object;
+template<typename T> class Stored;
 
 class Storage
 {
@@ -45,6 +46,8 @@ public:
 	explicit Digest(const std::string &);
 	explicit operator std::string() const;
 
+	const std::array<uint8_t, size> & arr() const { return value; }
+
 	bool operator==(const Digest & other) const { return value == other.value; }
 	bool operator!=(const Digest & other) const { return value != other.value; }
 	bool operator<(const Digest & other) const { return value < other.value; }
@@ -81,21 +84,28 @@ public:
 	class Item {
 	public:
 		typedef std::variant<
+			std::monostate,
 			int,
 			std::string,
 			std::vector<uint8_t>,
 			Ref> Variant;
 
+		Item(const std::string & name):
+			Item(name, std::monostate()) {}
 		Item(const std::string & name, Variant value):
 			name(name), value(value) {}
 		Item(const Item &) = default;
 		Item & operator=(const Item &) = delete;
 
+		operator bool() const;
+
 		std::optional<int> asInteger() const;
 		std::optional<std::string> asText() const;
 		std::optional<std::vector<uint8_t>> asBinary() const;
 		std::optional<Ref> asRef() const;
 
+		template<typename T> std::optional<Stored<T>> as() const;
+
 	private:
 		friend class Record;
 		std::string name;
@@ -111,8 +121,8 @@ public:
 	std::vector<uint8_t> encode() const;
 
 	const std::vector<Item> & items() const;
-	std::optional<Item> item(const std::string & name) const;
-	std::optional<Item> operator[](const std::string & name) const;
+	Item item(const std::string & name) const;
+	Item operator[](const std::string & name) const;
 	std::vector<Item> items(const std::string & name) const;
 
 private:
@@ -158,6 +168,7 @@ public:
 
 	static std::optional<Object> decode(Storage, const std::vector<uint8_t> &);
 	std::vector<uint8_t> encode() const;
+	static std::optional<Object> load(const Ref &);
 
 	std::optional<Record> asRecord() const;
 	std::optional<Blob> asBlob() const;
@@ -169,4 +180,87 @@ private:
 	Variants content;
 };
 
+template<typename T>
+std::optional<Stored<T>> Record::Item::as() const
+{
+	if (auto ref = asRef())
+		return Stored<T>::load(ref.value());
+	return std::nullopt;
+}
+
+template<typename T>
+class Stored
+{
+	Stored(Ref ref, std::shared_ptr<T> val): ref(ref), val(val) {}
+public:
+	static std::optional<Stored<T>> load(const Ref &);
+
+	bool operator==(const Stored<T> & other) const
+	{ return ref.digest() == other.ref.digest(); }
+	bool operator!=(const Stored<T> & other) const
+	{ return ref.digest() != other.ref.digest(); }
+	bool operator<(const Stored<T> & other) const
+	{ return ref.digest() < other.ref.digest(); }
+	bool operator<=(const Stored<T> & other) const
+	{ return ref.digest() <= other.ref.digest(); }
+	bool operator>(const Stored<T> & other) const
+	{ return ref.digest() > other.ref.digest(); }
+	bool operator>=(const Stored<T> & other) const
+	{ return ref.digest() >= other.ref.digest(); }
+
+	const T & operator*() const { return *val; }
+	const T * operator->() const { return val.get(); }
+
+	std::vector<Stored<T>> previous() const;
+	bool precedes(const Stored<T> &) const;
+
+	const Ref ref;
+	const std::shared_ptr<T> val;
+};
+
+template<typename T>
+std::optional<Stored<T>> Stored<T>::load(const Ref & ref)
+{
+	if (auto val = T::load(ref))
+		return Stored(ref, std::make_shared<T>(val.value()));
+	return std::nullopt;
+}
+
+template<typename T>
+std::vector<Stored<T>> Stored<T>::previous() const
+{
+	auto rec = ref->asRecord();
+	if (!rec)
+		return {};
+
+	auto sdata = rec->item("SDATA").asRef();
+	if (sdata) {
+		auto drec = sdata.value()->asRecord();
+		if (!drec)
+			return {};
+
+		std::vector<Stored<T>> res;
+		for (const auto & i : drec->items("SPREV"))
+			if (auto x = i.as<T>())
+				res.push_back(*x);
+		return res;
+	}
+
+	std::vector<Stored<T>> res;
+	for (auto & i : rec->items("PREV"))
+		if (auto x = i.as<T>())
+			res.push_back(*x);
+	return res;
+}
+
+template<typename T>
+bool Stored<T>::precedes(const Stored<T> & other) const
+{
+	for (const auto & x : other.previous()) {
+		if (*this == x || precedes(x))
+			return true;
+	}
+	return false;
+}
+
 }
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))