tlnbase: compact commitment secret storage - electrum - Electrum Bitcoin wallet
HTML git clone https://git.parazyd.org/electrum
DIR Log
DIR Files
DIR Refs
DIR Submodules
---
DIR commit cf82150aab0b288a2c24f27812ba88a0d7a37793
DIR parent c5fb090e5c5d13bbb1d694c54b0c4773760febec
HTML Author: Janus <ysangkok@gmail.com>
Date: Wed, 9 May 2018 21:43:15 +0200
lnbase: compact commitment secret storage
Diffstat:
M lib/lnbase.py | 67 ++++++++++++++++++++++++++++++-
M lib/tests/test_lnbase.py | 429 +++++++++++++++++++++++++++++++
2 files changed, 494 insertions(+), 2 deletions(-)
---
DIR diff --git a/lib/lnbase.py b/lib/lnbase.py
t@@ -319,6 +319,20 @@ def derive_blinded_pubkey(basepoint, per_commitment_point):
k2 = ser_to_point(per_commitment_point) * bitcoin.string_to_number(bitcoin.sha256(per_commitment_point + basepoint))
return point_to_ser(k1 + k2)
+def shachain_derive(element, toIndex):
+ """ compact per-commitment secret storage, taken from lnd """
+ fromIndex = element.index
+ positions = derive_bit_transformations(fromIndex, toIndex)
+ buf = bytearray(element.secret)
+ for position in positions:
+ byteNumber = position // 8
+ bitNumber = position % 8
+ buf[byteNumber] ^= 1 << bitNumber
+ h = bitcoin.sha256(buf)
+ buf = bytearray(h)
+
+ return ShachainElement(index=toIndex, secret=bytes(buf))
+
def get_per_commitment_secret_from_seed(seed: bytes, i: int, bits: int = 47) -> bytes:
"""Generate per commitment secret."""
t@@ -328,7 +342,9 @@ def get_per_commitment_secret_from_seed(seed: bytes, i: int, bits: int = 47) ->
if i & mask:
per_commitment_secret[bitindex // 8] ^= 1 << (bitindex % 8)
per_commitment_secret = bytearray(bitcoin.sha256(per_commitment_secret))
- return bytes(per_commitment_secret)
+ bajts = bytes(per_commitment_secret)
+ assert shachain_derive(ShachainElement(index=0, secret=seed), i).secret == bajts
+ return bajts
def overall_weight(num_htlc):
t@@ -1127,7 +1143,6 @@ class Peer(PrintError):
)
)
-
def on_commitment_signed(self, payload):
self.print_error("commitment_signed", payload)
channel_id = int.from_bytes(payload['channel_id'], 'big')
t@@ -1546,4 +1561,52 @@ def process_onion_packet(onion_packet: OnionPacket, associated_data: bytes,
are_we_final = False
return ProcessedOnionPacket(are_we_final, hop_data, next_onion_packet)
+def count_trailing_zeros(index):
+ """ BOLT-03 (where_to_put_secret) """
+ try:
+ return list(reversed(bin(index)[2:])).index("1")
+ except ValueError:
+ return 48
+
+ShachainElement = namedtuple("ShachainElement", ["secret", "index"])
+class RevocationStore:
+ """ taken from lnd """
+ def __init__(self):
+ self.buckets = {}
+ self.index = 2**48 - 1
+ def set_index(self, index):
+ self.index = index
+ def add_next_entry(self, hsh):
+ new_element = ShachainElement(index=self.index, secret=hsh)
+ bucket = count_trailing_zeros(self.index)
+ for i in range(0, bucket):
+ if i not in self.buckets: return
+ this_bucket = self.buckets[i]
+ e = shachain_derive(new_element, this_bucket.index)
+
+ if e != this_bucket:
+ return "hash is not derivable: {} {} {}".format(bh2u(e.secret), bh2u(this_bucket.secret), this_bucket.index)
+ self.buckets[bucket] = new_element
+ self.index -= 1
+ return
+
+def get_prefix(index, position):
+ """ taken from lnd """
+ mask = (1<<64)-1 - ((1<<position)-1)
+ return index & mask
+
+def derive_bit_transformations(fromm, to):
+ """ taken from lnd """
+ positions = []
+ if fromm == to: return positions
+
+ zeros = count_trailing_zeros(fromm)
+ if fromm > (1<<64)-1: raise Exception("fromm too big")
+ if fromm != get_prefix(to, zeros):
+ raise Exception("prefixes are different, indexes are not derivable")
+
+ for position in range(zeros, -1, -1):
+ if to >> position & 1 == 1:
+ positions.append(position)
+ return positions
DIR diff --git a/lib/tests/test_lnbase.py b/lib/tests/test_lnbase.py
t@@ -7,6 +7,7 @@ from lib.lnbase import make_commitment, get_obscured_ctn, Peer, make_offered_htl
from lib.lnbase import secret_to_pubkey, derive_pubkey, derive_privkey, derive_blinded_pubkey, overall_weight
from lib.lnbase import make_htlc_tx_output, make_htlc_tx_inputs, get_per_commitment_secret_from_seed
from lib.lnbase import make_htlc_tx_witness, OnionHopsDataSingle, new_onion_packet, OnionPerHop
+from lib.lnbase import RevocationStore, derive_bit_transformations
from lib.transaction import Transaction
from lib import bitcoin
import ecdsa.ellipticcurve
t@@ -383,3 +384,431 @@ class Test_LNBase(unittest.TestCase):
processed_packet = lnbase.process_onion_packet(packet, associated_data, privkey)
self.assertEqual(hops_data[i].per_hop.to_bytes(), processed_packet.hop_data.per_hop.to_bytes())
packet = processed_packet.next_packet
+
+ def test_shachain_producer(self):
+ from collections import namedtuple
+ tests = []
+ DeriveTest = namedtuple("DeriveTest", ["name", "fromm", "to", "position", "should_fail"])
+ tests.append(DeriveTest("zero 'from' 'to'", 0, 0, [], False))
+ tests.append(DeriveTest("same indexes #1", 0b100, 0b100, [], False))
+ tests.append(DeriveTest("same indexes #2", 0b1, 0b0, None, True))
+ tests.append(DeriveTest("test seed 'from'", 0b0, 0b10, [1], False))
+ tests.append(DeriveTest("not the same indexes", 0b1100, 0b0100, None, True))
+ tests.append(DeriveTest("'from' index greater than 'to' index", 0b1010, 0b1000, None, True))
+ tests.append(DeriveTest("zero number trailing zeros", 0b1, 0b1, [], False))
+ for test in tests:
+ try:
+ pos = derive_bit_transformations(test.fromm, test.to)
+ if test.should_fail:
+ raise Exception("test did not fail")
+ self.assertEqual(test.position, pos)
+ except:
+ if not test.should_fail:
+ raise Exception(test.name)
+
+ def test_shachain_store(self):
+ tests = [
+ {
+ "name": "insert_secret correct sequence",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1" +\
+ "a8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab2" +\
+ "1e9b506fd4998a51d54502e99116",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "c65716add7aa98ba7acb236352d665cab173" +\
+ "45fe45b55fb879ff80e6bd0c41dd",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "969660042a28f32d9be17344e09374b37996" +\
+ "2d03db1574df5a8a5a47e19ce3f2",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "a5a64476122ca0925fb344bdc1854c1c0a59" +\
+ "fc614298e50a33e331980a220f32",
+ "successful": True
+ },
+ {
+ "index": 281474976710648,
+ "secret": "05cde6323d949933f7f7b78776bcc1ea6d9b" +\
+ "31447732e3802e1f7ac44b650e17",
+ "successful": True
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #1 incorrect",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "02a40c85b6f28da08dfdbe0926c53fab2d" +\
+ "e6d28c10301f8f7c4073d5e42e3148",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659" +\
+ "c1a8b4b5bec0c4b872abeba4cb8964",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #2 incorrect (#1 derived from incorrect)",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "02a40c85b6f28da08dfdbe0926c53fab2de6" +\
+ "d28c10301f8f7c4073d5e42e3148",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "dddc3a8d14fddf2b68fa8c7fbad274827493" +\
+ "7479dd0f8930d5ebb4ab6bd866a3",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22a" +\
+ "b21e9b506fd4998a51d54502e99116",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #3 incorrect",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1" +\
+ "a8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "c51a18b13e8527e579ec56365482c62f180b" +\
+ "7d5760b46e9477dae59e87ed423a",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab2" +\
+ "1e9b506fd4998a51d54502e99116",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #4 incorrect (1,2,3 derived from incorrect)",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "02a40c85b6f28da08dfdbe0926c53fab2de6" +\
+ "d28c10301f8f7c4073d5e42e3148",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "dddc3a8d14fddf2b68fa8c7fbad274827493" +\
+ "7479dd0f8930d5ebb4ab6bd866a3",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "c51a18b13e8527e579ec56365482c62f18" +\
+ "0b7d5760b46e9477dae59e87ed423a",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "ba65d7b0ef55a3ba300d4e87af29868f39" +\
+ "4f8f138d78a7011669c79b37b936f4",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "c65716add7aa98ba7acb236352d665cab1" +\
+ "7345fe45b55fb879ff80e6bd0c41dd",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "969660042a28f32d9be17344e09374b379" +\
+ "962d03db1574df5a8a5a47e19ce3f2",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "a5a64476122ca0925fb344bdc1854c1c0a" +\
+ "59fc614298e50a33e331980a220f32",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "05cde6323d949933f7f7b78776bcc1ea6d9b" +\
+ "31447732e3802e1f7ac44b650e17",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #5 incorrect",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1a" +\
+ "8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab21" +\
+ "e9b506fd4998a51d54502e99116",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "631373ad5f9ef654bb3dade742d09504c567" +\
+ "edd24320d2fcd68e3cc47e2ff6a6",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "969660042a28f32d9be17344e09374b37996" +\
+ "2d03db1574df5a8a5a47e19ce3f2",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #6 incorrect (5 derived from incorrect)",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1a" +\
+ "8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab21" +\
+ "e9b506fd4998a51d54502e99116",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "631373ad5f9ef654bb3dade742d09504c567" +\
+ "edd24320d2fcd68e3cc47e2ff6a6",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "b7e76a83668bde38b373970155c868a65330" +\
+ "4308f9896692f904a23731224bb1",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "a5a64476122ca0925fb344bdc1854c1c0a59f" +\
+ "c614298e50a33e331980a220f32",
+ "successful": True
+ },
+ {
+ "index": 281474976710648,
+ "secret": "05cde6323d949933f7f7b78776bcc1ea6d9b" +\
+ "31447732e3802e1f7ac44b650e17",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #7 incorrect",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1a" +\
+ "8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab21" +\
+ "e9b506fd4998a51d54502e99116",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "c65716add7aa98ba7acb236352d665cab173" +\
+ "45fe45b55fb879ff80e6bd0c41dd",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "969660042a28f32d9be17344e09374b37996" +\
+ "2d03db1574df5a8a5a47e19ce3f2",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "e7971de736e01da8ed58b94c2fc216cb1d" +\
+ "ca9e326f3a96e7194fe8ea8af6c0a3",
+ "successful": True
+ },
+ {
+ "index": 281474976710648,
+ "secret": "05cde6323d949933f7f7b78776bcc1ea6d" +\
+ "9b31447732e3802e1f7ac44b650e17",
+ "successful": False
+ }
+ ]
+ },
+ {
+ "name": "insert_secret #8 incorrect",
+ "inserts": [
+ {
+ "index": 281474976710655,
+ "secret": "7cc854b54e3e0dcdb010d7a3fee464a9687b" +\
+ "e6e8db3be6854c475621e007a5dc",
+ "successful": True
+ },
+ {
+ "index": 281474976710654,
+ "secret": "c7518c8ae4660ed02894df8976fa1a3659c1a" +\
+ "8b4b5bec0c4b872abeba4cb8964",
+ "successful": True
+ },
+ {
+ "index": 281474976710653,
+ "secret": "2273e227a5b7449b6e70f1fb4652864038b1" +\
+ "cbf9cd7c043a7d6456b7fc275ad8",
+ "successful": True
+ },
+ {
+ "index": 281474976710652,
+ "secret": "27cddaa5624534cb6cb9d7da077cf2b22ab21" +\
+ "e9b506fd4998a51d54502e99116",
+ "successful": True
+ },
+ {
+ "index": 281474976710651,
+ "secret": "c65716add7aa98ba7acb236352d665cab173" +\
+ "45fe45b55fb879ff80e6bd0c41dd",
+ "successful": True
+ },
+ {
+ "index": 281474976710650,
+ "secret": "969660042a28f32d9be17344e09374b37996" +\
+ "2d03db1574df5a8a5a47e19ce3f2",
+ "successful": True
+ },
+ {
+ "index": 281474976710649,
+ "secret": "a5a64476122ca0925fb344bdc1854c1c0a" +\
+ "59fc614298e50a33e331980a220f32",
+ "successful": True
+ },
+ {
+ "index": 281474976710648,
+ "secret": "a7efbc61aac46d34f77778bac22c8a20c6" +\
+ "a46ca460addc49009bda875ec88fa4",
+ "successful": False
+ }
+ ]
+ }
+ ]
+
+ for test in tests:
+ old_receiver = None
+ receiver = None
+ for insert in test["inserts"]:
+ old_receiver = receiver
+ receiver = RevocationStore()
+ secret = bytes.fromhex(insert["secret"])
+ if not insert["successful"]:
+ receiver.set_index(old_receiver.index)
+ receiver.buckets = old_receiver.buckets
+ secret = secret[::-1]
+
+ err = receiver.add_next_entry(secret)
+ if isinstance(err, str):
+ if insert["successful"]:
+ raise Exception("Failed ({}): error was received but it shouldn't: {}".format(test["name"], err))
+ else:
+ if not insert["successful"]:
+ raise Exception("Failed ({}): error wasn't received".format(test["name"]))
+
+ print("Passed ({})".format(test["name"]))