Bip32 (Chia-Network#14)

* Add bip32 keys and test vectors
PoorMansChiaFarm · Sep 4, 2018 · 91e1b8e · 91e1b8e
1 parent c5fb923
commit 91e1b8e
Show file tree

Hide file tree

Showing 12 changed files with 541 additions and 338 deletions.
diff --git a/python-bindings/test.py b/python-bindings/test.py
@@ -118,19 +118,14 @@ def test2():
     message = bytes("this is the message", "utf-8")
     sig = sk.sign(message)
     sig_ser = sig.serialize()
-    print("Sig ser is", sig_ser)
     sig_cp = BLSSignature.from_bytes(sig_ser)
     a1 = AggregationInfo.from_msg(pk, message)
     sig_cp.set_aggregation_info(a1)
     a2 = sig_cp.get_aggregation_info()
     assert(a1 == a2)
-    print(a2)
     sig2 = sk2.sign(message)
 
     assert(sig.size() == 96)
-    print(sig, sig2)
-    print(sig2.serialize())
-    print(sorted([sig, sig2]))
     assert(sig != sig2)
     assert(sig == sig_cp)
 
@@ -145,8 +140,6 @@ def test2():
 
     sk2 = sk
 
-    print(sk)
-
 
 test1()
 test2()

diff --git a/python-impl/README.md b/python-impl/README.md
@@ -6,6 +6,5 @@ as BLS signatures and aggregation. Use for reference / educational purposes only
 For a good introduction to pairings, read [Pairings for Beginners](http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf) by Craig Costello.
 
 ### TODO
-* HD keys
 * Signature division
 * Fast algorithm for final exponentiation
diff --git a/python-impl/aggregation_info.py b/python-impl/aggregation_info.py
@@ -0,0 +1,162 @@
+from util import hash256, hash_pks
+
+
+class AggregationInfo:
+    """
+    AggregationInfo represents information of how a tree of aggregate
+    signatures was created. Different tress will result in different
+    signatures, due to exponentiations required for security.
+
+    An AggregationInfo is represented as a map from (message_hash, pk)
+    to exponents. When verifying, a verifier will take the signature,
+    along with this map, and raise each public key to the correct
+    exponent, and multiply the pks together, for identical messages.
+    """
+    def __init__(self, tree, message_hashes, public_keys):
+        self.tree = tree
+        self.message_hashes = message_hashes
+        self.public_keys = public_keys
+
+    def empty(self):
+        return not self.tree
+
+    def __lt__(self, other):
+        """
+        Compares two AggregationInfo objects, this is necessary for sorting
+        them. Comparison is done by comparing (message hash, pk, exponent)
+        """
+        combined = [(self.message_hashes[i], self.public_keys[i],
+                     self.tree[(self.message_hashes[i], self.public_keys[i])])
+                    for i in range(len(self.public_keys))]
+        combined_other = [(other.message_hashes[i], other.public_keys[i],
+                           other.tree[(other.message_hashes[i],
+                                       other.public_keys[i])])
+                          for i in range(len(other.public_keys))]
+
+        for i in range(len(combined)):
+            if i >= len(combined_other):
+                return False
+            if combined[i] < combined_other[i]:
+                return True
+            if combined_other[i] < combined[i]:
+                return False
+        return True
+
+    @staticmethod
+    def from_msg_hash(public_key, message_hash):
+        tree = {}
+        tree[(message_hash, public_key)] = 1
+        return AggregationInfo(tree, [message_hash], [public_key])
+
+    @staticmethod
+    def from_msg(pk, message):
+        return AggregationInfo.from_msg_hash(pk, hash256(message))
+
+    @staticmethod
+    def simple_merge_infos(aggregation_infos):
+        """
+        Infos are just merged together with no addition of exponents,
+        since they are disjoint
+        """
+        new_tree = {}
+        for info in aggregation_infos:
+            new_tree.update(info.tree)
+        mh_pubkeys = [k for k, v in new_tree.items()]
+
+        mh_pubkeys.sort()
+
+        message_hashes = [message_hash for (message_hash, public_key)
+                          in mh_pubkeys]
+        public_keys = [public_key for (message_hash, public_key)
+                       in mh_pubkeys]
+
+        return AggregationInfo(new_tree, message_hashes, public_keys)
+
+    @staticmethod
+    def secure_merge_infos(colliding_infos):
+        """
+        Infos are merged together with combination of exponents
+        """
+
+        # Groups are sorted by message then pk then exponent
+        # Each info object (and all of it's exponents) will be
+        # exponentiated by one of the Ts
+        colliding_infos.sort()
+
+        sorted_keys = []
+        for info in colliding_infos:
+            for key, value in info.tree.items():
+                sorted_keys.append(key)
+        sorted_keys.sort()
+        sorted_pks = [public_key for (message_hash, public_key)
+                      in sorted_keys]
+        computed_Ts = hash_pks(len(colliding_infos), sorted_pks)
+
+        # Group order, exponents can be reduced mod the order
+        order = sorted_pks[0].value.ec.n
+
+        new_tree = {}
+        for i in range(len(colliding_infos)):
+            for key, value in colliding_infos[i].tree.items():
+                if key not in new_tree:
+                    # This message & pk have not been included yet
+                    new_tree[key] = (value * computed_Ts[i]) % order
+                else:
+                    # This message and pk are already included, so multiply
+                    addend = value * computed_Ts[i]
+                    new_tree[key] = (new_tree[key] + addend) % order
+        mh_pubkeys = [k for k, v in new_tree.items()]
+        mh_pubkeys.sort()
+        message_hashes = [message_hash for (message_hash, public_key)
+                          in mh_pubkeys]
+        public_keys = [public_key for (message_hash, public_key)
+                       in mh_pubkeys]
+        return AggregationInfo(new_tree, message_hashes, public_keys)
+
+    @staticmethod
+    def merge_infos(aggregation_infos):
+        messages = set()
+        colliding_messages = set()
+        for info in aggregation_infos:
+            messages_local = set()
+            for key, value in info.tree.items():
+                if key[0] in messages and key[0] not in messages_local:
+                    colliding_messages.add(key[0])
+                messages.add(key[0])
+                messages_local.add(key[0])
+
+        if len(colliding_messages) == 0:
+            return AggregationInfo.simple_merge_infos(aggregation_infos)
+
+        colliding_infos = []
+        non_colliding_infos = []
+        for info in aggregation_infos:
+            info_collides = False
+            for key, value in info.tree.items():
+                if key[0] in colliding_messages:
+                    info_collides = True
+                    colliding_infos.append(info)
+                    break
+            if not info_collides:
+                non_colliding_infos.append(info)
+
+        combined = AggregationInfo.secure_merge_infos(colliding_infos)
+        non_colliding_infos.append(combined)
+        return AggregationInfo.simple_merge_infos(non_colliding_infos)
+
+
+"""
+Copyright 2018 Chia Network Inc
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+   http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+"""