first commit

5 files changed, 739 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..3e023e0
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,58 @@
+include ../mcl/common.mk
+LIB_DIR=lib
+OBJ_DIR=obj
+EXE_DIR=bin
+
+SRC_SRC=bls.cpp
+TEST_SRC=bls_test.cpp
+#SAMPLE_SRC=
+
+CFLAGS+=-I../mcl/include
+##################################################################
+BLS_LIB=$(LIB_DIR)/libbls.a
+all: $(BLS_LIB)
+
+LIB_OBJ=$(OBJ_DIR)/bls.o
+
+$(BLS_LIB): $(LIB_OBJ)
+	-$(MKDIR) $(@D)
+	$(AR) $@ $(LIB_OBJ)
+
+MCL_LIB=../mcl/lib/libmcl.a
+
+$(MCL_LIB):
+	$(MAKE) -C ../mcl
+
+##################################################################
+
+VPATH=test sample src
+
+.SUFFIXES: .cpp .d .exe
+
+$(OBJ_DIR)/%.o: %.cpp
+	-$(MKDIR) $(@D)
+	$(PRE)$(CXX) $(CFLAGS) -c $< -o $@ -MMD -MP -MF $(@:.o=.d)
+
+$(EXE_DIR)/%.exe: $(OBJ_DIR)/%.o $(BLS_LIB) $(MCL_LIB)
+	-$(MKDIR) $(@D)
+	$(PRE)$(CXX) $< -o $@ $(BLS_LIB) $(LDFLAGS) -lmcl -L../mcl/lib
+
+SAMPLE_EXE=$(addprefix $(EXE_DIR)/,$(SAMPLE_SRC:.cpp=.exe))
+sample: $(SAMPLE_EXE) $(BLS_LIB)
+
+TEST_EXE=$(addprefix $(EXE_DIR)/,$(TEST_SRC:.cpp=.exe))
+test: $(TEST_EXE)
+	@echo test $(TEST_EXE)
+	@sh -ec 'for i in $(TEST_EXE); do $$i|grep "ctest:name"; done' > result.txt
+	@grep -v "ng=0, exception=0" result.txt || echo "all unit tests are ok"
+
+clean:
+	$(RM) $(BLS_LIB) $(OBJ_DIR)/* $(EXE_DIR)/*.exe $(GEN_EXE) $(ASM_SRC) $(ASM_OBJ) $(LIB_OBJ) $(LLVM_SRC)
+
+ALL_SRC=$(SRC_SRC) $(TEST_SRC) $(SAMPLE_SRC)
+DEPEND_FILE=$(addprefix $(OBJ_DIR)/, $(ALL_SRC:.cpp=.d))
+-include $(DEPEND_FILE)
+
+# don't remove these files automatically
+.SECONDARY: $(addprefix $(OBJ_DIR)/, $(ALL_SRC:.cpp=.o))
+ 
diff --git a/include/bls.hpp b/include/bls.hpp
new file mode 100644
index 0000000..5288da0
--- /dev/null
+++ b/include/bls.hpp
@@ -0,0 +1,101 @@
+#pragma once
+/**
+	@file
+	@brief BLS threshold signature on BN curve
+	@author MITSUNARI Shigeo(@herumi)
+	@license modified new BSD license
+	http://opensource.org/licenses/BSD-3-Clause
+*/
+#include <vector>
+#include <string>
+#include <iosfwd>
+
+namespace bls {
+
+namespace impl {
+
+struct PublicKey;
+struct PrivateKey;
+struct Sign;
+
+} // bls::impl
+
+void init();
+
+class Sign {
+public:
+	impl::Sign *self_;
+	int id_;
+	friend class PublicKey;
+	friend class PrivateKey;
+	template<class G, class T>
+	friend void LagrangeIntepolation(G& r, const T& vec);
+public:
+	Sign();
+	~Sign();
+	Sign(const Sign& rhs);
+	Sign& operator=(const Sign& rhs);
+	void setStr(const std::string& str);
+	void getStr(std::string& str) const;
+	bool operator==(const Sign& rhs) const;
+	bool operator!=(const Sign& rhs) const { return !(*this == rhs); }
+	int getId() const { return id_; }
+	friend std::ostream& operator<<(std::ostream& os, const Sign& s);
+	friend std::istream& operator>>(std::istream& is, Sign& s);
+
+	/*
+		recover sign from k signVec
+	*/
+	void recover(const std::vector<Sign>& signVec);
+};
+
+class PublicKey {
+	impl::PublicKey *self_;
+	int id_;
+	friend class PrivateKey;
+public:
+	PublicKey();
+	~PublicKey();
+	PublicKey(const PublicKey& rhs);
+	PublicKey& operator=(const PublicKey& rhs);
+	void setStr(const std::string& str);
+	void getStr(std::string& str) const;
+	bool operator==(const PublicKey& rhs) const;
+	bool operator!=(const PublicKey& rhs) const { return !(*this == rhs); }
+	int getId() const { return id_; }
+	friend std::ostream& operator<<(std::ostream& os, const PublicKey& pub);
+	friend std::istream& operator>>(std::istream& is, PublicKey& pub);
+	bool verify(const Sign& sign, const std::string& m) const;
+};
+
+class PrivateKey {
+	impl::PrivateKey *self_;
+	int id_; // master if id_ = 0, shared if id_ > 0
+	template<class G, class T>
+	friend void LagrangeIntepolation(G& r, const T& vec);
+public:
+	PrivateKey();
+	~PrivateKey();
+	PrivateKey(const PrivateKey& rhs);
+	PrivateKey& operator=(const PrivateKey& rhs);
+	void setStr(const std::string& str);
+	void getStr(std::string& str) const;
+	bool operator==(const PrivateKey& rhs) const;
+	bool operator!=(const PrivateKey& rhs) const { return !(*this == rhs); }
+	int getId() const { return id_; }
+	friend std::ostream& operator<<(std::ostream& os, const PrivateKey& prv);
+	friend std::istream& operator>>(std::istream& is, PrivateKey& prv);
+	void init();
+	void getPublicKey(PublicKey& pub) const;
+	void sign(Sign& sign, const std::string& m) const;
+	/*
+		k-out-of-n secret sharing of privateKey
+	*/
+	void share(std::vector<PrivateKey>& prvVec, int n, int k);
+	/*
+		recover privateKey from k prvVec
+	*/
+	void recover(const std::vector<PrivateKey>& prvVec);
+};
+
+} // bls
diff --git a/readme.md b/readme.md
new file mode 100644
index 0000000..59ec541
--- /dev/null
+++ b/readme.md
@@ -0,0 +1,31 @@
+# BLS threshold signature
+
+An implementation of BLS threshold signature
+
+# Installation Requirements
+
+Create a working directory (e.g., work) and clone the following repositories.
+```
+mkdir work
+cd work
+git clone git://github.com/herumi/xbyak.git
+git clone git://github.com/herumi/cybozulib.git
+git clone git://github.com/herumi/mcl.git
+git clone git://github.com/herumi/bls.git
+```
+
+# Build and test
+To make lib/libbls.a and test, run
+```
+cd bls
+make test
+```
+
+# License
+
+modified new BSD License
+http://opensource.org/licenses/BSD-3-Clause
+
+# Author
+
+MITSUNARI Shigeo(herumi@nifty.com)
diff --git a/src/bls.cpp b/src/bls.cpp
new file mode 100644
index 0000000..2d6598d
--- /dev/null
+++ b/src/bls.cpp
@@ -0,0 +1,395 @@
+/**
+	@file
+	@author MITSUNARI Shigeo(@herumi)
+	@license modified new BSD license
+	http://opensource.org/licenses/BSD-3-Clause
+*/
+#include <bls.hpp>
+#include <mcl/bn.hpp>
+#include <cybozu/crypto.hpp>
+#include <cybozu/random_generator.hpp>
+#include <vector>
+#include <string>
+
+typedef mcl::FpT<mcl::FpTag, 256> Fp;
+typedef mcl::bn::BNT<Fp> BN;
+typedef BN::Fp2 Fp2;
+typedef BN::Fp6 Fp6;
+typedef BN::Fp12 Fp12;
+typedef BN::G1 G1;
+typedef BN::G2 G2;
+typedef std::vector<int> IntVec;
+
+struct FrTag;
+typedef mcl::FpT<FrTag, 256> Fr;
+typedef std::vector<Fr> FrVec;
+
+
+#define PUT(x) std::cout << #x << "=" << x << std::endl;
+
+static cybozu::RandomGenerator& getRG()
+{
+	static cybozu::RandomGenerator rg;
+	return rg;
+}
+
+namespace bls {
+
+void init()
+{
+	BN::init(mcl::bn::CurveFp254BNb);
+	G1::setCompressedExpression();
+//	G2::setCompressedExpression();
+	Fr::init(BN::param.r.get_str());
+}
+
+static const G2& getQ()
+{
+	static const G2 Q(
+		Fp2("12723517038133731887338407189719511622662176727675373276651903807414909099441", "4168783608814932154536427934509895782246573715297911553964171371032945126671"),
+		Fp2("13891744915211034074451795021214165905772212241412891944830863846330766296736", "7937318970632701341203597196594272556916396164729705624521405069090520231616")
+	);
+	return Q;
+}
+
+static void hash(Fp& t, const std::string& m)
+{
+	std::string digest = cybozu::crypto::Hash::digest(cybozu::crypto::Hash::N_SHA256, m);
+	t.setArrayMask(digest.c_str(), digest.size());
+}
+
+static void mapToG1(G1& P, const Fp& t)
+{
+	static mcl::bn::MapTo<Fp> mapTo;
+	mapTo.calcG1(P, t);
+}
+
+static void HashAndMapToG1(G1& P, const std::string& m)
+{
+	Fp t;
+	hash(t, m);
+	mapToG1(P, t);
+}
+
+struct Polynomial {
+	FrVec c; // f[x] = sum_{i=0}^{k-1} c[i] x^i
+	void init(const Fr& s, int k)
+	{
+		if (k < 2) throw cybozu::Exception("Polynomial:init:bad k") << k;
+		c.resize(k);
+		c[0] = s;
+		for (size_t i = 1; i < c.size(); i++) {
+			c[i].setRand(getRG());
+		}
+	}
+	// y = f(id)
+	void eval(Fr& y, int id) const
+	{
+		if (id == 0) throw cybozu::Exception("Polynomial:calc_f:i is zero");
+		if (c.size() < 2) throw cybozu::Exception("Polynomial:calc_f:bad size") << c.size();
+		const Fr x(id);
+		y = c[c.size() - 1];
+		for (int i = (int)c.size() - 2; i >= 0; i--) {
+			y *= x;
+			y += c[i];
+		}
+	}
+};
+
+/*
+	delta_{i,S}(0) = prod_{j != i} S[j] / (S[j] - S[i]) = a / b
+	where a = prod S[j], b = S[i] * prod_{j != i} (S[j] - S[i])
+*/
+static void calcDelta(FrVec& delta, const IntVec& S)
+{
+	const size_t k = S.size();
+	if (k < 2) throw cybozu::Exception("BLS:calcDelta:bad size") << k;
+	delta.resize(k);
+	Fr a = S[0];
+	for (size_t i = 1; i < k; i++) {
+		a *= S[i];
+	}
+	for (size_t i = 0; i < k; i++) {
+		Fr b = S[i];
+		for (size_t j = 0; j < k; j++) {
+			if (j != i) {
+				int v = S[j] - S[i];
+				if (v == 0) throw cybozu::Exception("bls:calcDelta:S has same id") << i << j;
+				b *= v;
+			}
+		}
+		delta[i] = a / b;
+	}
+}
+
+template<class G, class T>
+void LagrangeIntepolation(G& r, const T& vec)
+{
+	IntVec S(vec.size());
+	for (size_t i = 0; i < vec.size(); i++) {
+		S[i] = vec[i].getId();
+	}
+	FrVec delta;
+	calcDelta(delta, S);
+
+	r.clear();
+	G t;
+	for (size_t i = 0; i < delta.size(); i++) {
+		G::mul(t, vec[i].self_->get(), delta[i]);
+		r += t;
+	}
+}
+
+namespace impl {
+
+struct Sign {
+	G1 sHm; // s Hash(m)
+	const G1& get() const { return sHm; }
+};
+
+struct PublicKey {
+	G2 sQ;
+	void init(const Fr& s)
+	{
+		G2::mul(sQ, getQ(), s);
+	}
+	bool verify(const Sign& sign, const std::string& m) const
+	{
+		G1 Hm;
+		HashAndMapToG1(Hm, m); // Hm = Hash(m)
+		Fp12 e1, e2;
+		BN::pairing(e1, getQ(), sign.sHm); // e(Q, s Hm)
+		BN::pairing(e2, sQ, Hm); // e(sQ, Hm)
+		return e1 == e2;
+	}
+};
+
+struct PrivateKey {
+	Fr s;
+	const Fr& get() const { return s; }
+	void init()
+	{
+		s.setRand(getRG());
+	}
+	void getPublicKey(PublicKey& pub) const
+	{
+		pub.init(s);
+	}
+	void sign(Sign& sign, const std::string& m) const
+	{
+		G1 Hm;
+		HashAndMapToG1(Hm, m);
+		G1::mul(sign.sHm, Hm, s);
+	}
+};
+
+} // mcl::bls::impl
+
+Sign::Sign()
+	: self_(new impl::Sign())
+	, id_(0)
+{
+}
+
+Sign::~Sign()
+{
+	delete self_;
+}
+
+Sign::Sign(const Sign& rhs)
+	: self_(new impl::Sign(*rhs.self_))
+	, id_(rhs.id_)
+{
+}
+
+Sign& Sign::operator=(const Sign& rhs)
+{
+	*self_ = *rhs.self_;
+	id_ = rhs.id_;
+	return *this;
+}
+
+void Sign::setStr(const std::string& str)
+{
+	std::istringstream iss(str);
+	iss >> *this;
+}
+
+void Sign::getStr(std::string& str) const
+{
+	std::ostringstream oss(str);
+	oss << *this;
+	str = oss.str();
+}
+
+bool Sign::operator==(const Sign& rhs) const
+{
+	return id_ == rhs.id_ && self_->sHm == rhs.self_->sHm;
+}
+
+std::ostream& operator<<(std::ostream& os, const Sign& s)
+{
+	return os << s.id_ << ' ' << s.self_->sHm;
+}
+
+std::istream& operator>>(std::istream& os, Sign& s)
+{
+	return os >> s.id_ >> s.self_->sHm;
+}
+
+void Sign::recover(const std::vector<Sign>& signVec)
+{
+	G1 sHm;
+	LagrangeIntepolation(sHm, signVec);
+	self_->sHm = sHm;
+	id_ = 0;
+}
+
+PublicKey::PublicKey()
+	: self_(new impl::PublicKey())
+	, id_(0)
+{
+}
+
+PublicKey::~PublicKey()
+{
+	delete self_;
+}
+
+PublicKey::PublicKey(const PublicKey& rhs)
+	: self_(new impl::PublicKey(*rhs.self_))
+	, id_(rhs.id_)
+{
+}
+
+PublicKey& PublicKey::operator=(const PublicKey& rhs)
+{
+	*self_ = *rhs.self_;
+	id_ = rhs.id_;
+	return *this;
+}
+
+void PublicKey::setStr(const std::string& str)
+{
+	std::istringstream iss(str);
+	iss >> *this;
+}
+
+void PublicKey::getStr(std::string& str) const
+{
+	std::ostringstream oss(str);
+	oss << *this;
+	str = oss.str();
+}
+
+bool PublicKey::operator==(const PublicKey& rhs) const
+{
+	return id_ == rhs.id_ && self_->sQ == rhs.self_->sQ;
+}
+
+std::ostream& operator<<(std::ostream& os, const PublicKey& pub)
+{
+	return os << pub.id_ << ' ' << pub.self_->sQ;
+}
+
+std::istream& operator>>(std::istream& is, PublicKey& pub)
+{
+	return is >> pub.id_ >> pub.self_->sQ;
+}
+
+bool PublicKey::verify(const Sign& sign, const std::string& m) const
+{
+	return self_->verify(*sign.self_, m);
+}
+
+PrivateKey::PrivateKey()
+	: self_(new impl::PrivateKey())
+	, id_(0)
+{
+}
+
+PrivateKey::~PrivateKey()
+{
+	delete self_;
+}
+
+PrivateKey::PrivateKey(const PrivateKey& rhs)
+	: self_(new impl::PrivateKey(*rhs.self_))
+	, id_(rhs.id_)
+{
+}
+
+PrivateKey& PrivateKey::operator=(const PrivateKey& rhs)
+{
+	*self_ = *rhs.self_;
+	id_ = rhs.id_;
+	return *this;
+}
+
+void PrivateKey::setStr(const std::string& str)
+{
+	std::istringstream iss(str);
+	iss >> *this;
+}
+
+void PrivateKey::getStr(std::string& str) const
+{
+	std::ostringstream oss(str);
+	oss << *this;
+	str = oss.str();
+}
+
+bool PrivateKey::operator==(const PrivateKey& rhs) const
+{
+	return id_ == rhs.id_ && self_->s == rhs.self_->s;
+}
+
+void PrivateKey::init()
+{
+	self_->init();
+}
+
+void PrivateKey::getPublicKey(PublicKey& pub) const
+{
+	self_->getPublicKey(*pub.self_);
+	pub.id_ = id_;
+}
+
+std::ostream& operator<<(std::ostream& os, const PrivateKey& prv)
+{
+	return os << prv.id_ << ' ' << prv.self_->s;
+}
+
+std::istream& operator>>(std::istream& is, PrivateKey& prv)
+{
+	return is >> prv.id_ >> prv.self_->s;
+}
+
+void PrivateKey::sign(Sign& sign, const std::string& m) const
+{
+	self_->sign(*sign.self_, m);
+	sign.id_ = id_;
+}
+
+void PrivateKey::share(std::vector<PrivateKey>& prvVec, int n, int k)
+{
+	if (id_ != 0) throw cybozu::Exception("bls:PrivateKey:share:already shared") << id_;
+	Polynomial poly;
+	poly.init(self_->s, k);
+	prvVec.resize(n);
+	for (int i = 0; i < n; i++) {
+		int id = i + 1;
+		poly.eval(prvVec[i].self_->s, id);
+		prvVec[i].id_ = id;
+	}
+}
+
+void PrivateKey::recover(const std::vector<PrivateKey>& prvVec)
+{
+	Fr s;
+	LagrangeIntepolation(s, prvVec);
+	self_->s = s;
+	id_ = 0;
+}
+
+} // bls
diff --git a/test/bls_test.cpp b/test/bls_test.cpp
new file mode 100644
index 0000000..1dd3b65
--- /dev/null
+++ b/test/bls_test.cpp
@@ -0,0 +1,154 @@
+#include <bls.hpp>
+#include <cybozu/test.hpp>
+#include <iostream>
+
+CYBOZU_TEST_AUTO(bls)
+{
+	bls::init();
+	bls::PrivateKey prv;
+	prv.init();
+	{
+		std::string str;
+		prv.getStr(str);
+		bls::PrivateKey prv2;
+		prv2.setStr(str);
+		CYBOZU_TEST_EQUAL(prv, prv2);
+	}
+	bls::PublicKey pub;
+	prv.getPublicKey(pub);
+	{
+		std::string str;
+		pub.getStr(str);
+		bls::PublicKey pub2;
+		pub2.setStr(str);
+		CYBOZU_TEST_EQUAL(pub, pub2);
+	}
+	for (int i = 0; i < 5; i++) {
+		std::string m = "hello";
+		m += char('0' + i);
+		bls::Sign s;
+		prv.sign(s, m);
+		CYBOZU_TEST_ASSERT(pub.verify(s, m));
+		CYBOZU_TEST_ASSERT(!pub.verify(s, m + "a"));
+		{
+			std::string str;
+			s.getStr(str);
+			bls::Sign s2;
+			s2.setStr(str);
+			CYBOZU_TEST_EQUAL(s, s2);
+		}
+	}
+}
+
+CYBOZU_TEST_AUTO(k_of_n)
+{
+	bls::init();
+	const std::string m = "abc";
+	const int n = 5;
+	const int k = 3;
+	bls::PrivateKey prv0;
+	prv0.init();
+	bls::Sign s0;
+	prv0.sign(s0, m);
+	bls::PublicKey pub0;
+	prv0.getPublicKey(pub0);
+	CYBOZU_TEST_ASSERT(pub0.verify(s0, m));
+
+	std::vector<bls::PrivateKey> allPrvVec;
+	prv0.share(allPrvVec, n, k);
+	CYBOZU_TEST_EQUAL(allPrvVec.size(), n);
+	for (int i = 0; i < n; i++) {
+		CYBOZU_TEST_EQUAL(allPrvVec[i].getId(), i + 1);
+	}
+
+	std::vector<bls::Sign> allSignVec(n);
+	for (int i = 0; i < n; i++) {
+		CYBOZU_TEST_ASSERT(allPrvVec[i] != prv0);
+		allPrvVec[i].sign(allSignVec[i], m);
+		bls::PublicKey pub;
+		allPrvVec[i].getPublicKey(pub);
+		CYBOZU_TEST_ASSERT(pub != pub0);
+		CYBOZU_TEST_ASSERT(pub.verify(allSignVec[i], m));
+	}
+
+	/*
+		3-out-of-n
+		can recover
+	*/
+	std::vector<bls::PrivateKey> prvVec(3);
+	for (int a = 0; a < n; a++) {
+		prvVec[0] = allPrvVec[a];
+		for (int b = a + 1; b < n; b++) {
+			prvVec[1] = allPrvVec[b];
+			for (int c = b + 1; c < n; c++) {
+				prvVec[2] = allPrvVec[c];
+				bls::PrivateKey prv;
+				prv.recover(prvVec);
+				CYBOZU_TEST_EQUAL(prv, prv0);
+			}
+		}
+	}
+	{
+		/*
+			n-out-of-n
+			can recover
+		*/
+		bls::PrivateKey prv;
+		prv.recover(allPrvVec);
+		CYBOZU_TEST_EQUAL(prv, prv0);
+	}
+	/*
+		2-out-of-n
+		can't recover
+	*/
+	prvVec.resize(2);
+	for (int a = 0; a < n; a++) {
+		prvVec[0] = allPrvVec[a];
+		for (int b = a + 1; b < n; b++) {
+			prvVec[1] = allPrvVec[b];
+			bls::PrivateKey prv;
+			prv.recover(prvVec);
+			CYBOZU_TEST_ASSERT(prv != prv0);
+		}
+	}
+	/*
+		3-out-of-n
+		can recover
+	*/
+	std::vector<bls::Sign> signVec(3);
+	for (int a = 0; a < n; a++) {
+		signVec[0] = allSignVec[a];
+		for (int b = a + 1; b < n; b++) {
+			signVec[1] = allSignVec[b];
+			for (int c = b + 1; c < n; c++) {
+				signVec[2] = allSignVec[c];
+				bls::Sign s;
+				s.recover(signVec);
+				CYBOZU_TEST_EQUAL(s, s0);
+			}
+		}
+	}
+	{
+		/*
+			n-out-of-n
+			can recover
+		*/
+		bls::Sign s;
+		s.recover(allSignVec);
+		CYBOZU_TEST_EQUAL(s, s0);
+	}
+	/*
+		2-out-of-n
+		can't recover
+	*/
+	signVec.resize(2);
+	for (int a = 0; a < n; a++) {
+		signVec[0] = allSignVec[a];
+		for (int b = a + 1; b < n; b++) {
+			signVec[1] = allSignVec[b];
+			bls::Sign s;
+			s.recover(signVec);
+			CYBOZU_TEST_ASSERT(s != s0);
+		}
+	}
+}