Implement prepend signatures in c++/python, update python implementat…

…ion, fix bug (#57) * Implement prepend signatures in c++/python bindings, update python binding and readme * Readme change, python bindings fix * Fix python bindings test, and attempt to fix ci build * Fix memory leak in threshold * Add prepend methods to pure python impl
Chia-Network · Apr 30, 2019 · 802bc2b · 802bc2b
1 parent d18d2e0
commit 802bc2b
Show file tree

Hide file tree

Showing 21 changed files with 999 additions and 434 deletions.
diff --git a/README.md b/README.md
@@ -11,7 +11,7 @@ Features:
 * Non-interactive signature aggregation on identical or distinct messages
 * Aggregate aggregates (trees)
 * Efficient verification (only one pairing per distinct message)
-* Security against rogue public key attack
+* Security against rogue public key attack, using aggregation info, or proof of possession
 * Aggregate public keys and private keys
 * M/N threshold keys and signatures using Joint-Feldman scheme
 * HD (BIP32) key derivation
@@ -197,6 +197,23 @@ pkChild.Serialize(buffer1);
 skChild.Serialize(buffer2);
 ```
 
+#### Prepend PK method
+```c++
+// Can use proofs of possession to avoid keeping track of metadata
+PrependSignature prepend1 = sk1.SignPrepend(msg, sizeof(msg));
+PrependSignature prepend2 = sk2.SignPrepend(msg, sizeof(msg));
+
+std::vector<PublicKey> prependPubKeys = {pk1, pk2};
+uint8_t messageHash[BLS::MESSAGE_HASH_LEN];
+Util::Hash256(messageHash, msg, sizeof(msg));
+std::vector<const uint8_t*> hashes = {messageHash, messageHash};
+
+std::vector<PrependSignature> prependSigs = {prepend1, prepend2};
+PrependSignature prependAgg = PrependSignature::Aggregate(prependSigs);
+
+prependAgg.Verify(hashes, prependPubKeys);
+```
+
 ### Build
 Cmake, a c++ compiler, and python3 (for bindings) are required for building.
 ```bash

diff --git a/SPEC.md b/SPEC.md
@@ -236,12 +236,21 @@ newAggInfo.remove((messageHashesToRemove[i], pubKeysToRemove[i] for i in range(l
 return (aggSig, newAggInfo)
 ```
 
+## Prepend Method
+In order to not have to keep around aggregation info when aggregating, an alternative is to force proof of possession of the pulic key, and aggregate using the simple aggregation scheme (the aggregation tree is flat, and no exponents are used). We can do this by prepending the public key to the message hash:
+
+```python
+prepend_m = hash256(pk + hash256(m)))
+```
+These prepend signatures are incompatible with normal aggregate signatures, and can only be aggregated with other prepend signatures. In the serialization, the second bit of the signature is set to 1 iff the signature is a prepend signature.
+
+
 ## Serialization
 **private key (32 bytes):** Big endian integer.
 
 **pubkey (48 bytes):** 381 bit affine x coordinate, encoded into 48 big-endian bytes. Since we have 3 bits left over in the beginning, the first bit is set to 1 iff y coordinate is the lexicographically largest of the two valid ys. The public key fingerprint is the first 4 bytes of hash256(serialize(pubkey)).
 
-**signature (96 bytes):** Two 381 bit integers (affine x coordinate), encoded into two 48 big-endian byte arrays. Since we have 3 bits left over in the beginning, the first bit is set to 1 iff the y coordinate is the lexicographically largest of the two valid ys. (The term with the i is compared first, i.e 3i + 1 > 2i + 7).
+**signature (96 bytes):** Two 381 bit integers (affine x coordinate), encoded into two 48 big-endian byte arrays. Since we have 3 bits left over in the beginning, the first bit is set to 1 iff the y coordinate is the lexicographically largest of the two valid ys. (The term with the i is compared first, i.e 3i + 1 > 2i + 7). The second bit is set to 1 iff the signature was generated using the prepend method, and should be verified using the prepend method.
 
 
 ## HD keys
@@ -336,4 +345,13 @@ since not all 32 byte sequences are valid BLS private keys
 * esk.privateChild(3).privateChild(17).publicKeyFingerprint
     * 0xff26a31f
 * esk.extendedPublicKey.publicChild(3).publicChild(17).publicKeyFingerprint
-    * 0xff26a31f
+    * 0xff26a31f
+
+### Prepend Signatures
+* sign_prepend([7,8,9], sk1)
+    * sig9:  0xd2135ad358405d9f2d4e68dc253d64b6049a821797817cffa5aa804086a8fb7b135175bb7183750e3aa19513db1552180f0b0ffd513c322f1c0c30a0a9c179f6e275e0109d4db7fa3e09694190947b17d890f3d58fe0b1866ec4d4f5a59b16ed
+* sign_prepend([10,11,12], sk2)
+    * sig10: 0xcc58c982f9ee5817d4fbf22d529cfc6792b0fdcf2d2a8001686755868e10eb32b40e464e7fbfe30175a962f1972026f2087f0495ba6e293ac3cf271762cd6979b9413adc0ba7df153cf1f3faab6b893404c2e6d63351e48cd54e06e449965f08
+* aggregate([sig9, sig9, sig10])
+    * prepend_agg: 0xc37077684e735e62e3f1fd17772a236b4115d4b581387733d3b97cab08b90918c7e91c23380c93e54be345544026f93505d41e6000392b82ab3c8af1b2e3954b0ef3f62c52fc89f99e646ff546881120396c449856428e672178e5e0e14ec894
+* verify_prepend(prepend_agg, [pk1, pk1, pk2], [[7,8,9],[7,8,9],[10,11,12]])
diff --git a/python-bindings/README.md b/python-bindings/README.md
@@ -14,13 +14,16 @@ git submodule update
 pip3 install .
 ```
 
+
 Then, to use:
 
 #### Import the library
 ```python
-import blspy
+from blspy import (PrivateKey, PublicKey, Signature, PrependSignature,
+AggregationInfo, ExtendedPrivateKey, Util)
 ```
 
+
 #### Creating keys and signatures
 ```python
 # Example seed, used to generate private key. Always use
@@ -57,7 +60,7 @@ sig = Signature.from_bytes(sig_bytes)
 ```python
 # Add information required for verification, to sig object
 sig.set_aggregation_info(AggregationInfo.from_msg(pk, msg))
-ok = BLS.verify(sig)
+ok = sig.verify()
 ```
 
 #### Aggregate signatures for a single message
@@ -77,13 +80,13 @@ pk2 = sk2.get_public_key()
 sig2 = sk2.sign(msg)
 
 # Aggregate signatures together
-agg_sig = BLS.aggregate_sigs([sig1, sig2])
+agg_sig = Signature.aggregate([sig1, sig2])
 
 
 # For same message, public keys can be aggregated into one.
 # The signature can be verified the same as a single signature,
 # using this public key.
-agg_pubkey = BLS.aggregate_pub_keys([pk1, pk2], True)
+agg_pubkey = PublicKey.aggregate([pk1, pk2])
 ```
 
 #### Aggregate signatures for different messages
@@ -102,10 +105,10 @@ sig3 = sk3.sign(msg2)
 # They can be noninteractively combined by anyone
 # Aggregation below can also be done by the verifier, to
 # make batch verification more efficient
-agg_sig_l = BLS.aggregate_sigs([sig1, sig2])
+agg_sig_l = Signature.aggregate([sig1, sig2])
 
 # Arbitrary trees of aggregates
-agg_sig_final = BLS.aggregate_sigs([agg_sig_l, sig3])
+agg_sig_final = Signature.aggregate([agg_sig_l, sig3])
 
 # Serialize the final signature
 sig_bytes = agg_sig_final.serialize()
@@ -125,21 +128,21 @@ a_final = AggregationInfo.merge_infos([a1a2, a3])
 
 # Verify final signature using the aggregation info
 agg_sig_final.set_aggregation_info(a_final)
-ok = BLS.verify(agg_sig_final)
+ok = agg_sig_final.verify()
 
 # If you previously verified a signature, you can also divide
 # the aggregate signature by the signature you already verified.
-ok = BLS.verify(agg_sig_l)
+ok = agg_sig_l.verify()
 agg_sig_final = agg_sig_final.divide_by([agg_sig_l])
 
-ok = BLS.verify(agg_sig_final)
+ok = agg_sig_final.verify()
 ```
 
 #### Aggregate private keys
 ```python
 # Create an aggregate private key, that can generate
 # aggregate signatures
-agg_sk = BLS.aggregate_priv_keys([sk1, sk2], [pk1, pk2], True)
+agg_sk = PrivateKey.aggregate([sk1, sk2], [pk1, pk2])
 agg_sk.sign(msg)
 ```
 
@@ -160,3 +163,14 @@ buffer1 = pk_child.serialize() # 93 bytes
 buffer2 = sk_child.serialize() # 77 bytes
 ```
 
+#### Prepend PK method
+```python
+# Can use proofs of possession to avoid keeping track of metadata
+prepend1 = sk1.sign_prepend(msg)
+prepend2 = sk2.sign_prepend(msg)
+
+prepend_agg = PrependSignature.aggregate([prepend1, prepend2])
+
+ok = prepend_agg.verify([Util.hash256(msg), Util.hash256(msg)], [pk1, pk2])
+
+```
diff --git a/python-bindings/pythonbindings.cpp b/python-bindings/pythonbindings.cpp
@@ -28,11 +28,13 @@ PYBIND11_MODULE(blspy, m) {
     py::class_<AggregationInfo>(m, "AggregationInfo")
         .def("from_msg_hash", [](const PublicKey &pk, const py::bytes &b) {
             std::string str(b);
-            return AggregationInfo::FromMsgHash(pk, (const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return AggregationInfo::FromMsgHash(pk, input);
         })
         .def("from_msg", [](const PublicKey &pk, const py::bytes &b) {
             std::string str(b);
-            return AggregationInfo::FromMsg(pk, (const uint8_t*)str.data(), str.size());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return AggregationInfo::FromMsg(pk, input, len(b));
         })
         .def("merge_infos", &AggregationInfo::MergeInfos)
         .def("get_pubkeys", &AggregationInfo::GetPubKeys)
@@ -59,11 +61,13 @@ PYBIND11_MODULE(blspy, m) {
         })
         .def("from_seed", [](const py::bytes &b) {
             std::string str(b);
-            return PrivateKey::FromSeed((const uint8_t*)str.data(), str.size());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return PrivateKey::FromSeed(input, len(b));
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return PrivateKey::FromBytes((const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return PrivateKey::FromBytes(input);
         })
         .def("serialize", [](const PrivateKey &k) {
             uint8_t* output = Util::SecAlloc<uint8_t>(PrivateKey::PRIVATE_KEY_SIZE);
@@ -78,11 +82,23 @@ PYBIND11_MODULE(blspy, m) {
         .def("aggregate", &PrivateKey::Aggregate)
         .def("sign", [](const PrivateKey &k, const py::bytes &msg) {
             std::string str(msg);
-            return k.Sign((const uint8_t*)str.data(), str.size());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return k.Sign(input, len(msg));
         })
         .def("sign_prehashed", [](const PrivateKey &k, const py::bytes &msg) {
             std::string str(msg);
-            return k.SignPrehashed((const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return k.SignPrehashed(input);
+        })
+        .def("sign_prepend", [](const PrivateKey &k, const py::bytes &msg) {
+            std::string str(msg);
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return k.SignPrepend(input, len(msg));
+        })
+        .def("sign_prepend_prehashed", [](const PrivateKey &k, const py::bytes &msg) {
+            std::string str(msg);
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return k.SignPrependPrehashed(input);
         })
         .def(py::self == py::self)
         .def(py::self != py::self)
@@ -94,14 +110,13 @@ PYBIND11_MODULE(blspy, m) {
             return ret;
         });
 
-
     py::class_<PublicKey>(m, "PublicKey")
         .def_property_readonly_static("PUBLIC_KEY_SIZE", [](py::object self) {
             return PublicKey::PUBLIC_KEY_SIZE;
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return PublicKey::FromBytes((const uint8_t*)str.data());
+            return PublicKey::FromBytes(reinterpret_cast<const uint8_t*>(str.data()));
         })
         .def("aggregate", &PublicKey::Aggregate)
         .def("get_fingerprint", &PublicKey::GetFingerprint)
@@ -120,14 +135,13 @@ PYBIND11_MODULE(blspy, m) {
             return "<PublicKey " + s.str() + ">";
         });
 
-
     py::class_<Signature>(m, "Signature")
         .def_property_readonly_static("SIGNATURE_SIZE", [](py::object self) {
             return Signature::SIGNATURE_SIZE;
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return Signature::FromBytes((const uint8_t*)str.data());
+            return Signature::FromBytes(reinterpret_cast<const uint8_t*>(str.data()));
         })
         .def("serialize", [](const Signature &sig) {
             uint8_t* output = new uint8_t[Signature::SIGNATURE_SIZE];
@@ -137,7 +151,7 @@ PYBIND11_MODULE(blspy, m) {
             return ret;
         })
         .def("verify", &Signature::Verify)
-        .def("aggregate", &Signature::AggregateSigs)
+        .def("aggregate", &Signature::Aggregate)
         .def("divide_by", &Signature::DivideBy)
         .def("set_aggregation_info", &Signature::SetAggregationInfo)
         .def("get_aggregation_info", [](const Signature &sig) {
@@ -151,13 +165,53 @@ PYBIND11_MODULE(blspy, m) {
             return "<Signature " + s.str() + ">";
         });
 
+    py::class_<PrependSignature>(m, "PrependSignature")
+        .def_property_readonly_static("SIGNATURE_SIZE", [](py::object self) {
+            return PrependSignature::SIGNATURE_SIZE;
+        })
+        .def("from_bytes", [](const py::bytes &b) {
+            std::string str(b);
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return PrependSignature::FromBytes(input);
+        })
+        .def("serialize", [](const PrependSignature &sig) {
+            uint8_t* output = new uint8_t[PrependSignature::SIGNATURE_SIZE];
+            sig.Serialize(output);
+            py::bytes ret = py::bytes(reinterpret_cast<char*>(output), PrependSignature::SIGNATURE_SIZE);
+            delete[] output;
+            return ret;
+        })
+        .def("verify", [](const PrependSignature &sig, const std::vector<py::bytes> &hashes,
+                           std::vector<PublicKey> &pks) {
+            std::vector<const uint8_t*> converted_hashes;
+            std::vector<std::string> strings;
+            for (const py::bytes &h : hashes) {
+               std::string str(h);
+               strings.push_back(str);
+            }
+            for (uint32_t i = 0; i < strings.size(); i++) {
+               converted_hashes.push_back(reinterpret_cast<const uint8_t*>(strings[i].data()));
+            }
+            return sig.Verify(converted_hashes, pks);
+        })
+        .def("aggregate", &PrependSignature::Aggregate)
+        .def("divide_by", &PrependSignature::DivideBy)
+        .def(py::self == py::self)
+        .def(py::self != py::self)
+        .def("__repr__", [](const PrependSignature &sig) {
+            std::stringstream s;
+            s << sig;
+            return "<PrependSignature " + s.str() + ">";
+        });
+
     py::class_<ChainCode>(m, "ChainCode")
         .def_property_readonly_static("CHAIN_CODE_KEY_SIZE", [](py::object self) {
             return ChainCode::CHAIN_CODE_SIZE;
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return ChainCode::FromBytes((const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return ChainCode::FromBytes(input);
         })
         .def("serialize", [](const ChainCode &cc) {
             uint8_t* output = new uint8_t[ChainCode::CHAIN_CODE_SIZE];
@@ -176,15 +230,14 @@ PYBIND11_MODULE(blspy, m) {
             return ret;
         });
 
-
-
     py::class_<ExtendedPublicKey>(m, "ExtendedPublicKey")
         .def_property_readonly_static("EXTENDED_PUBLIC_KEY_SIZE", [](py::object self) {
             return ExtendedPublicKey::EXTENDED_PUBLIC_KEY_SIZE;
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return ExtendedPublicKey::FromBytes((const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return ExtendedPublicKey::FromBytes(input);
         })
         .def("public_child", &ExtendedPublicKey::PublicChild)
         .def("get_version", &ExtendedPublicKey::GetVersion)
@@ -220,11 +273,13 @@ PYBIND11_MODULE(blspy, m) {
         })
         .def("from_seed", [](const py::bytes &seed) {
             std::string str(seed);
-            return ExtendedPrivateKey::FromSeed((const uint8_t*)str.data(), str.size());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return ExtendedPrivateKey::FromSeed(input, len(seed));
         })
         .def("from_bytes", [](const py::bytes &b) {
             std::string str(b);
-            return ExtendedPrivateKey::FromBytes((const uint8_t*)str.data());
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
+            return ExtendedPrivateKey::FromBytes(input);
         })
         .def("private_child", &ExtendedPrivateKey::PrivateChild)
         .def("public_child", &ExtendedPrivateKey::PublicChild)
@@ -266,6 +321,7 @@ PYBIND11_MODULE(blspy, m) {
     py::class_<Util>(m, "Util")
         .def("hash256", [](const py::bytes &message) {
             std::string str(message);
+            const uint8_t* input = reinterpret_cast<const uint8_t*>(str.data());
             uint8_t output[BLS::MESSAGE_HASH_LEN];
             Util::Hash256(output, (const uint8_t*)str.data(), str.size());
             return py::bytes(reinterpret_cast<char*>(output), BLS::MESSAGE_HASH_LEN);