Version two of network certificate of membership, a much more concise and fast approach.

2 files changed, 152 insertions, 36 deletions

diff --git a/node/Network.cpp b/node/Network.cpp
index 3fd0e428..13086a8e 100644
--- a/node/Network.cpp
+++ b/node/Network.cpp
@@ -41,50 +41,77 @@
 
 namespace ZeroTier {
 
-void Network::Certificate::_shaForSignature(unsigned char *dig) const
+void Network::CertificateOfMembership::addParameter(uint64_t id,uint64_t value,uint64_t maxDelta)
 {
-	SHA256_CTX sha;
-	SHA256_Init(&sha);
-	unsigned char zero = 0;
-	for(const_iterator i(begin());i!=end();++i) {
-		SHA256_Update(&sha,&zero,1);
-		SHA256_Update(&sha,(const unsigned char *)i->first.data(),i->first.length());
-		SHA256_Update(&sha,&zero,1);
-		SHA256_Update(&sha,(const unsigned char *)i->second.data(),i->second.length());
-		SHA256_Update(&sha,&zero,1);
+	_params.push_back(_Parameter(id,value,maxDelta));
+	std::sort(_params.begin(),_params.end(),_SortByIdComparison());
+}
+
+std::string Network::CertificateOfMembership::toString() const
+{
+	uint64_t tmp[3000];
+	unsigned long n = 0;
+	for(std::vector<_Parameter>::const_iterator p(_params.begin());p!=_params.end();++p) {
+		tmp[n++] = Utils::hton(p->id);
+		tmp[n++] = Utils::hton(p->value);
+		tmp[n++] = Utils::hton(p->maxDelta);
+		if (n >= 3000)
+			break; // sanity check -- certificates will never even approach this size
 	}
-	SHA256_Final(dig,&sha);
+	return Utils::hex(tmp,sizeof(uint64_t) * n);
 }
 
-static const std::string _DELTA_PREFIX("~");
-bool Network::Certificate::qualifyMembership(const Network::Certificate &mc) const
+void Network::CertificateOfMembership::fromString(const char *s)
 {
-	// Note: optimization probably needed here, probably via some kind of
-	// memoization / dynamic programming. But make it work first, then make
-	// it fast.
-
-	for(const_iterator myField(begin());myField!=end();++myField) {
-		if (!((myField->first.length() > 1)&&(myField->first[0] == '~'))) { // ~fields are max delta range specs
-			// If they lack the same field, comparison fails.
-			const_iterator theirField(mc.find(myField->first));
-			if (theirField == mc.end())
+	std::string tmp(Utils::unhex(s));
+	_params.clear();
+	const char *ptr = tmp.data();
+	unsigned long remaining = tmp.length();
+	while (remaining >= 24) {
+		_Parameter p;
+		p.id = Utils::ntoh(*((const uint64_t *)(ptr)));
+		p.value = Utils::ntoh(*((const uint64_t *)(ptr + 8)));
+		p.maxDelta = Utils::ntoh(*((const uint64_t *)(ptr + 16)));
+		_params.push_back(p);
+		ptr += 24;
+		remaining -= 24;
+	}
+}
+
+bool Network::CertificateOfMembership::compare(const CertificateOfMembership &other) const
+	throw()
+{
+	unsigned long myidx = 0;
+	unsigned long otheridx = 0;
+
+	while (myidx < _params.size()) {
+		// Fail if we're at the end of other, since this means the field is
+		// missing.
+		if (otheridx >= other._params.size())
+			return false;
+
+		// Seek to corresponding tuple in other, ignoring tuples that
+		// we may not have. If we run off the end of other, the tuple is
+		// missing. This works because tuples are sorted by ID.
+		while (other._params[otheridx].id != _params[myidx].id) {
+			++otheridx;
+			if (otheridx >= other._params.size())
 				return false;
+		}
 
-			const_iterator deltaField(find(_DELTA_PREFIX + myField->first));
-			if (deltaField == end()) {
-				// If there is no delta, compare on simple equality
-				if (myField->second != theirField->second)
-					return false;
-			} else {
-				// Otherwise compare the absolute value of the difference between
-				// the two values against the max delta.
-				int64_t my = Utils::hexStrTo64(myField->second.c_str());
-				int64_t their = Utils::hexStrTo64(theirField->second.c_str());
-				int64_t delta = Utils::hexStrTo64(deltaField->second.c_str());
-				if (llabs((long long)(my - their)) > delta)
-					return false;
-			}
+		// Compare to determine if the absolute value of the difference
+		// between these two parameters is within our maxDelta.
+		uint64_t a = _params[myidx].value;
+		uint64_t b = other._params[myidx].value;
+		if (a >= b) {
+			if ((a - b) > _params[myidx].maxDelta)
+				return false;
+		} else {
+			if ((b - a) > _params[myidx].maxDelta)
+				return false;
 		}
+
+		++myidx;
 	}
 
 	return true;
diff --git a/node/Network.hpp b/node/Network.hpp
index 0cf50e1f..747bb2f4 100644
--- a/node/Network.hpp
+++ b/node/Network.hpp
@@ -28,6 +28,8 @@
 #ifndef _ZT_NETWORK_HPP
 #define _ZT_NETWORK_HPP
 
+#include <stdint.h>
+
 #include <string>
 #include <set>
 #include <map>
@@ -81,6 +83,93 @@ class Network : NonCopyable
 
 public:
 	/**
+	 * Certificate of network membership
+	 *
+	 * The COM consists of a series of three-element 64-bit tuples. These values
+	 * are an id, a value, and a maximum delta. The ID is arbitrary and should be
+	 * assigned using a scheme that makes every ID globally unique for a given
+	 * type of parameter. ID 0 is reserved for the always-present timestamp
+	 * parameter. The value is parameter-specific. The maximum delta is the
+	 * maximum difference that is permitted between two values for determining
+	 * whether a certificate permits two peers to speak to one another. A value
+	 * of zero indicates that the values must equal.
+	 *
+	 * Certificates of membership must be signed by the netconf master for the
+	 * network in question. This permits members to verify these certs against
+	 * the netconf master's public key before testing them.
+	 */
+	class CertificateOfMembership
+	{
+	public:
+		CertificateOfMembership() throw() {}
+		CertificateOfMembership(const char *s) { fromString(s); }
+		CertificateOfMembership(const std::string &s) { fromString(s.c_str()); }
+
+		/**
+		 * Add a paramter to this certificate
+		 *
+		 * @param id Parameter ID
+		 * @param value Parameter value
+		 * @param maxDelta Parameter maximum difference with others
+		 */
+		void addParameter(uint64_t id,uint64_t value,uint64_t maxDelta);
+
+		/**
+		 * @return Hex-serialized representation of this certificate (minus signature)
+		 */
+		std::string toString() const;
+
+		/**
+		 * Set this certificate equal to the hex-serialized string
+		 *
+		 * Invalid strings will result in invalid or undefined certificate
+		 * contents. These will subsequently fail validation and comparison.
+		 *
+		 * @param s String to deserialize
+		 */
+		void fromString(const char *s);
+		inline void fromString(const std::string &s) { fromString(s.c_str()); }
+
+		/**
+		 * Compare two certificates for parameter agreement
+		 *
+		 * This compares this certificate with the other and returns true if all
+		 * paramters in this cert are present in the other and if they agree to
+		 * within this cert's max delta value for each given parameter.
+		 *
+		 * @param other Cert to compare with
+		 * @return True if certs agree and 'other' may be communicated with
+		 */
+		bool compare(const CertificateOfMembership &other) const
+			throw();
+
+	private:
+		struct _Parameter
+		{
+			_Parameter() throw() {}
+			_Parameter(uint64_t i,uint64_t v,uint64_t m) throw() :
+				id(i),
+				value(v),
+				maxDelta(m) {}
+			uint64_t id;
+			uint64_t value;
+			uint64_t maxDelta;
+		};
+
+		// Used with std::sort to ensure that _params are sorted
+		struct _SortByIdComparison
+		{
+			inline bool operator()(const _Parameter &a,const _Parameter &b) const
+				throw()
+			{
+				return (a.id < b.id);
+			}
+		};
+
+		std::vector<_Parameter> _params;
+	};
+
+	/**
 	 * A certificate of network membership for private network participation
 	 *
 	 * Certificates consist of a dictionary containing one or more values with