Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from __future__ import annotations
- from hashlib import new
- from nacl.signing import SigningKey, SignedMessage, VerifyKey
- from secrets import token_bytes
- import nacl.bindings
- """
- Demonstration of Twisted Edwards Curve 2^255-19 digital signature system, its
- properties, and its adaptations. See below sources for more details.
- Ed25519 (RFC 8032): https://www.rfc-editor.org/rfc/rfc8032.html
- Adapters: https://medium.com/crypto-garage/adaptor-signature-schnorr-signature-and-ecdsa-da0663c2adc4
- AMHLs: https://eprint.iacr.org/2018/472
- """
- # helper functions
- def clamp_scalar(scalar: bytes, from_private_key: bool = False) -> bytes:
- """Make a clamped scalar."""
- if type(scalar) is bytes and len(scalar) >= 32:
- x_i = bytearray(scalar[:32])
- elif type(scalar) is SigningKey:
- x_i = bytearray(new('sha512', bytes(scalar)).digest()[:32])
- from_private_key = True
- else:
- raise ValueError('not a SigningKey and not 32+ bytes scalar')
- if from_private_key:
- # set bits 0, 1, and 2 to 0
- # nb: lsb is right-indexed
- x_i[0] &= 0b11111000
- # set bit 254 to 1
- x_i[31] |= 0b01000000
- # set bit 255 to 0
- x_i[31] &= 0b01111111
- return bytes(x_i)
- def H_big(*parts) -> bytes:
- """The big, 64-byte hash function."""
- return new('sha512', b''.join(parts)).digest()
- def H_small(*parts) -> bytes:
- """The small, 32-byte hash function."""
- return nacl.bindings.crypto_core_ed25519_scalar_reduce(H_big(*parts))
- def derive_key_from_seed(seed: bytes) -> bytes:
- """Derive the scalar used for signing from a seed."""
- return clamp_scalar(H_big(seed)[:32], True)
- def aggregate_points(points: list) -> bytes:
- """Aggregate points on the Ed25519 curve."""
- # type checking inputs
- for pt in points:
- if type(pt) is not bytes and type(pt) is not VerifyKey:
- raise TypeError('each point must be bytes or VerifyKey')
- # normalize points to bytes
- points = [pt if type(pt) is bytes else bytes(pt) for pt in points]
- # raise an error for invalid points
- for pt in points:
- if not nacl.bindings.crypto_core_ed25519_is_valid_point(pt):
- raise ValueError('each point must be a valid ed25519 point')
- # compute the sum
- sum = points[0]
- for i in range(1, len(points)):
- sum = nacl.bindings.crypto_core_ed25519_add(sum, points[i])
- return sum
- def xor(b1: bytes, b2: bytes) -> bytes:
- """XOR two equal-length byte strings together."""
- b3 = bytearray()
- for i in range(len(b1)):
- b3.append(b1[i] ^ b2[i])
- return bytes(b3)
- def bytes_are_same(b1: bytes, b2: bytes) -> bool:
- """Timing-attack safe bytes comparison."""
- return len(b1) == len(b2) and int.from_bytes(xor(b1, b2), 'little') == 0
- def hexify(thing):
- """Convert a data structure to something printable."""
- if type(thing) is dict:
- new_thing = {}
- for key in thing:
- value = thing[key]
- key = key.hex() if type(key) is bytes else key
- new_thing[key] = hexify(value)
- return new_thing
- if type(thing) is list:
- return [hexify(t) for t in thing]
- if type(thing) is tuple:
- return tuple([hexify(t) for t in thing])
- if type(thing) is bytes:
- return thing.hex()
- return thing
- # adapter functions
- def public_tweak_adapter(seed: bytes, m: bytes, T: bytes) -> tuple[bytes]:
- """Create a public tweak adapter signature. Return vbalue is (R, T, sa)."""
- x = derive_key_from_seed(seed)
- X = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x) # G^x
- nonce = H_big(seed)[32:]
- r = clamp_scalar(H_small(H_big(nonce, m))) # H(nonce || m)
- R = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(r) # G^r
- RT = aggregate_points((R, T)) # R + t
- ca = clamp_scalar(H_small(RT, X, m)) # H(R + T || X || m)
- sa = nacl.bindings.crypto_core_ed25519_scalar_add(r, nacl.bindings.crypto_core_ed25519_scalar_mul(ca, x)) # r + H(R + T || X || m) * x
- return (R, T, sa)
- def verify_public_tweak_adapter(adapter: tuple[bytes], m: bytes, X: bytes) -> bool:
- """Verify a public tweak adapter is valid for a given message."""
- (R, T, sa) = adapter
- sa_G = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(sa) # sa_G = G^sa
- RT = aggregate_points((R, T)) # R + T
- ca = clamp_scalar(H_small(RT, X, m)) # H(R + T || X || m)
- caX = nacl.bindings.crypto_scalarmult_ed25519_noclamp(ca, X) # X^H(R + T || X || m)
- RcaX = aggregate_points((R, caX)) # R + X^H(R + T || X || m)
- return bytes_are_same(sa_G, RcaX) # G^sa == R + X^H(R + T || X || m)
- def decrypt_public_tweak_adapter(adapter: tuple[bytes], m: bytes, t: bytes) -> SignedMessage:
- """Decrypt a public tweak adapter signature."""
- (R, T, sa) = adapter
- RT = aggregate_points((R, T)) # R + T
- s = nacl.bindings.crypto_core_ed25519_scalar_add(sa, t) # s = sa + t
- sig = SignedMessage(RT + s + m)
- return sig
- # AMHL functions
- # Messy conventions taken directly from the Anonymous Multi-Hop Lock paper
- def sample() -> bytes:
- """Take 1 sample from the domain of the homomorphic one-way function."""
- return clamp_scalar(token_bytes(32))
- def samples(n: int) -> tuple[bytes]:
- """Take n samples from the domain of the homomorphic one-way function."""
- return tuple(sample() for i in range(n))
- def oneway(scalar: bytes) -> bytes:
- """Run the homomorphic one-way function on the input scalar."""
- return nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(scalar)
- def setup(n_users: int) -> tuple[tuple[bytes], tuple[bytes]]:
- """Setup the lock inputs."""
- y = samples(n_users)
- Y = [oneway(y[0])]
- for i, y_i in enumerate(y):
- if i > 0:
- Y.append(aggregate_points((Y[i-1], oneway(y_i))))
- return (y, tuple(Y))
- def scalar_sum(*scalars: tuple[bytes]) -> bytes:
- """Compute the sum of the scalars."""
- sum = scalars[0]
- for i in range(1, len(scalars)):
- sum = nacl.bindings.crypto_core_ed25519_scalar_add(sum, scalars[i])
- return sum
- def setup_for(s: tuple[tuple[bytes], tuple[bytes]], i: int) -> tuple[bytes]:
- """Generate the setup for a particular user given the setup s and
- the user index i.
- """
- if i == 0:
- return (s[0][0],)
- if i == len(s[0]):
- return ((s[1][i-1], 0, 0), scalar_sum(*s[0]))
- return (s[1][i-1], s[1][i], s[0][i])
- def check_setup(s: tuple[bytes], i: int, n: int) -> bool:
- """Verifies the setup for the ith of n users is valid."""
- if i == 0:
- return len(s) == 1 and isinstance(s[0], bytes)
- if i == n:
- return len(s) == 2 and type(s[0]) is tuple and len(s[0]) == 3 and type(s[0][0]) is bytes and type(s[1]) is bytes
- Y_i = aggregate_points((s[0], oneway(s[2])))
- return bytes_are_same(Y_i, s[1])
- def lock(s: tuple) -> tuple[bytes, bool]:
- """Create the lock from the setup."""
- return (s[1], False)
- def release(k: bytes, sI: tuple) -> bytes:
- """Release a left lock given a key from a released intermediate lock."""
- y = sI[2] if type(sI) is tuple else sI
- return nacl.bindings.crypto_core_ed25519_scalar_sub(k, y)
- def verify_lock_key(l: bytes, k: bytes) -> bool:
- """Verify that a key opens a lock."""
- return bytes_are_same(l, oneway(k))
- # tests
- def test_sign_and_verify():
- """Replication of the maths involved in signing and verifying."""
- # set seed and generate key pair from it
- seed = token_bytes(32)
- skey = SigningKey(seed)
- # derive key pair manually
- x = derive_key_from_seed(seed) # clamp(H(seed)[:32])
- X = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x) # G^x
- m = b'hello world'
- # create signature with nacl
- sig = skey.sign(m)
- # create signature manually
- nonce = H_big(seed)[32:]
- r = clamp_scalar(H_small(nonce, m))
- R = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(r) # G^r
- c = clamp_scalar(H_small(R, X, m)) # clamp(H(R || X || m))
- s = nacl.bindings.crypto_core_ed25519_scalar_add(r, nacl.bindings.crypto_core_ed25519_scalar_mul(c, x)) # r + c*x
- nsig = SignedMessage(R + s + m)
- # G, X, R, s, and m are public values
- # c can be derived: H(R || X || m)
- # Therefore, G^s = R * X^c can be verified by anyone
- # But only the holder of x and r can create the signature
- # verify both
- assert bytes_are_same(bytes(sig), bytes(nsig))
- assert skey.verify_key.verify(sig) # s = c*x + r
- assert skey.verify_key.verify(nsig) # G^s = G^(c*x + r) = R * G^(x*c) = R * X^c
- def test_homomorphic_one_way():
- """Test if Ed25519 meets the homomorphic one way condition."""
- x1, x2 = clamp_scalar(token_bytes(32)), clamp_scalar(token_bytes(32))
- y1 = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x1) # G^x1
- y2 = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x2) # G^x2
- # test
- y3_1 = nacl.bindings.crypto_core_ed25519_add(y1, y2) # G^x1 + G^x2
- x3 = nacl.bindings.crypto_core_ed25519_scalar_add(x1, x2) # x1 + x2
- y3_2 = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x3) # G^(x1+x2)
- assert y3_1 == y3_2 # G^x1 * G^x2 = G^(x1+x2) where * denotes group operator
- def test_adapter_signature():
- """Test the construction, unlocking, and verification of adapters.
- For an explanation and possible uses, see this medium article:
- https://medium.com/crypto-garage/adaptor-signature-schnorr-signature-and-ecdsa-da0663c2adc4
- """
- # key pairs and message
- seed1, seed2 = token_bytes(32), token_bytes(32)
- skey = SigningKey(seed1)
- x, t = derive_key_from_seed(seed1), derive_key_from_seed(seed2)
- X = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(x) # G^x
- T = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(t) # G^t
- m = b'txn sending money to counterparty as part of payment route'
- # private key tweaking construction
- # sa = t + r + H(R || X || m) * x
- nonce = H_big(seed1)[32:]
- r = clamp_scalar(H_small(nonce, m))
- R = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(r) # G^r
- c = clamp_scalar(H_small(R, X, m)) # clamp(H(R || X || m))
- tr = nacl.bindings.crypto_core_ed25519_scalar_add(t, r)
- sa = nacl.bindings.crypto_core_ed25519_scalar_add(tr, nacl.bindings.crypto_core_ed25519_scalar_mul(c, x)) # t + r + c*x
- # public values: R, sa, m, X, T
- # sig = (T, R, sa, m)
- # private key tweaking adapter verification
- # sa_G = G^sa
- sa_G = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(sa)
- c = clamp_scalar(H_small(R, X, m)) # clamp(H(R || X || m))
- cX = nacl.bindings.crypto_scalarmult_ed25519_noclamp(c, X)
- TRcX = aggregate_points((T, R, cX))
- assert bytes_are_same(sa_G, TRcX)
- # G^sa == T + R + X^H(R || X || m)
- # private key tweaking signature decryption and verification
- # s = sa - t
- s = nacl.bindings.crypto_core_ed25519_scalar_sub(sa, t)
- sig = SignedMessage(R + s + m)
- assert skey.verify_key.verify(sig)
- # G^(sa - t) == T + R + X^H(R || X || m) - T
- # G^s == R + X^H(R || X || m)
- # public key tweaking construction
- # sa = r + H(R + T || X || m) * x
- RT = aggregate_points((R, T))
- ca = clamp_scalar(H_small(RT, X, m))
- sa = nacl.bindings.crypto_core_ed25519_scalar_add(r, nacl.bindings.crypto_core_ed25519_scalar_mul(ca, x))
- # public values: R, sa, m, X, T
- # ca and RT can be derived from public values
- # sig = (T, R, sa, m)
- # public key tweaking adapter verification
- # sa_G = G^sa
- sa_G = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(sa)
- caX = nacl.bindings.crypto_scalarmult_ed25519_noclamp(ca, X)
- RcaX = aggregate_points((R, caX))
- assert bytes_are_same(sa_G, RcaX)
- # G^sa == R + X^H(R + T || X || m)
- # public key tweaking signature decryption and verification
- # s = sa + t
- s = nacl.bindings.crypto_core_ed25519_scalar_add(sa, t)
- sig = SignedMessage(RT + s + m)
- assert skey.verify_key.verify(sig)
- # G^(sa + t) == R + X^H(R + T || X || m) + T
- # G^s == (R + T) + X^H((R + T) || X || m)
- ...
- def test_AMHL():
- """Test for setup, locking, and release of an Anonymous Multi-Hop
- Lock using the homomorphic qualities of ed25519.
- """
- # first run the initial setup for 5 payers (4 intermediate)
- n = 5
- s = setup(n)
- # validate setups for each user
- for i in range(len(s[0])):
- assert check_setup(setup_for(s, i), i, n)
- # validate releasing of locks from right to left
- s_n = setup_for(s, n)
- k = s_n[1]
- for i in range(n-1, 1, -1):
- s_i = setup_for(s, i)
- r = release(k, s_i)
- assert verify_lock_key(setup_for(s, i-1)[1], r)
- k = r
- def test_AMHL_adapters():
- """Test for combining the AMHL primitive with the adapter signature
- primitive for atomic transaction locking/unlocking. In this case,
- Alice pays Dave through Bob and Carla, with Bob and Carla each
- taking a fee for faciliating the transaction.
- """
- # first run the initial setup for 3 payers (2 intermediate)
- n = 3
- s = setup(n)
- # validate setups for each user
- for i in range(len(s[0])):
- assert check_setup(setup_for(s, i), i, n)
- # Alice setup
- Alice = {
- 'seed' : token_bytes(32),
- 'outbound_txn' : {
- 'm': b'Alice pays Bob 12'
- },
- 'lock': setup_for(s, 0)
- }
- Alice['skey'] = SigningKey(Alice['seed'])
- Alice['vkey'] = Alice['skey'].verify_key
- Alice['x'] = derive_key_from_seed(Alice['seed'])
- Alice['X'] = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(Alice['x'])
- # create adapter
- Alice['outbound_txn']['adapter'] = public_tweak_adapter(Alice['seed'], Alice['outbound_txn']['m'], oneway(Alice['lock'][0]))
- # Bob setup
- Bob = {
- 'seed' : token_bytes(32),
- 'inbound_txn': Alice['outbound_txn'],
- 'outbound_txn' : {
- 'm': b'Bob pays Carla 11'
- },
- 'lock': setup_for(s, 1)
- }
- Bob['skey'] = SigningKey(Bob['seed'])
- Bob['vkey'] = Bob['skey'].verify_key
- Bob['x'] = derive_key_from_seed(Bob['seed'])
- Bob['X'] = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(Bob['x'])
- # verify Bob's left lock is Alice's right lock
- assert bytes_are_same(Bob['lock'][0], oneway(Alice['lock'][0]))
- # verify Alice's adapter
- assert verify_public_tweak_adapter(Bob['inbound_txn']['adapter'], Bob['inbound_txn']['m'], Alice['X'])
- # create adapter
- Bob['outbound_txn']['adapter'] = public_tweak_adapter(Bob['seed'], Bob['outbound_txn']['m'], Bob['lock'][1])
- # Carla setup
- Carla = {
- 'seed' : token_bytes(32),
- 'inbound_txn' : Bob['outbound_txn'],
- 'outbound_txn': {
- 'm': b'Carla pays Dave 10'
- },
- 'lock': setup_for(s, 2)
- }
- Carla['skey'] = SigningKey(Carla['seed'])
- Carla['vkey'] = Carla['skey'].verify_key
- Carla['x'] = derive_key_from_seed(Carla['seed'])
- Carla['X'] = nacl.bindings.crypto_scalarmult_ed25519_base_noclamp(Carla['x'])
- # verify Carla's left lock is Bob's right lock
- assert bytes_are_same(Carla['lock'][0], Bob['lock'][1])
- # verify Bob's adapter
- assert verify_public_tweak_adapter(Carla['inbound_txn']['adapter'], Carla['inbound_txn']['m'], Bob['X'])
- # create adapter
- Carla['outbound_txn']['adapter'] = public_tweak_adapter(Carla['seed'], Carla['outbound_txn']['m'], Carla['lock'][1])
- # Dave setup
- Dave = {
- 'seed' : token_bytes(32),
- 'inbound_txn' : Carla['outbound_txn'],
- 'lock': setup_for(s, 3)
- }
- # verify Dave's left lock is Carla's right lock
- assert bytes_are_same(Dave['lock'][0][0], Carla['lock'][1])
- # verify Carla's adapter
- assert verify_public_tweak_adapter(Dave['inbound_txn']['adapter'], Dave['inbound_txn']['m'], Carla['X'])
- # decrypt adapter paying Dave
- k = Dave['lock'][1]
- Dave['inbound_txn']['signature'] = decrypt_public_tweak_adapter(Dave['inbound_txn']['adapter'], Dave['inbound_txn']['m'], k)
- assert Carla['vkey'].verify(Dave['inbound_txn']['signature'])
- # release lock for Carla
- r = release(k, Carla['lock'])
- assert verify_lock_key(Carla['lock'][0], r) # Carla's left lock == Bob's right lock
- # decrypt adapter paying Carla
- Carla['inbound_txn']['signature'] = decrypt_public_tweak_adapter(Carla['inbound_txn']['adapter'], Carla['inbound_txn']['m'], r)
- assert Bob['vkey'].verify(Carla['inbound_txn']['signature'])
- # release lock for Bob
- r = release(r, Bob['lock'])
- assert verify_lock_key(Bob['lock'][0], r) # Bob's left lock == Alice's right lock
- # decrypt adapter paying Bob
- Bob['inbound_txn']['signature'] = decrypt_public_tweak_adapter(Bob['inbound_txn']['adapter'], Bob['inbound_txn']['m'], r)
- assert Alice['vkey'].verify(Bob['inbound_txn']['signature'])
- # Dave now has a signed transaction paying him from Carla
- # Carla now has a signed transaction paying her from Bob
- # Bob now has a signed transaction paying him from Alice
- # Alice has paid Dave through Bob and Carla
- ...
- def license():
- """Copyleft (c) 2022 k98kurz
- Permission to use, copy, modify, and/or distribute this software
- for any purpose with or without fee is hereby granted, provided
- that the above copyleft notice and this permission notice appear in
- all copies.
- THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
- WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
- WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
- AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
- CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
- OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
- NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
- CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- """
- return license.__doc__
- if __name__ == '__main__':
- for i in range(128):
- test_homomorphic_one_way()
- print('homomorphic one-way function test passed')
- for i in range(128):
- test_sign_and_verify()
- print('signature creation and verification test passed')
- for i in range(128):
- test_adapter_signature()
- print('adapter signature test passed')
- for i in range(128):
- test_AMHL()
- print('anonymous multihop lock test passed')
- for i in range(128):
- test_AMHL_adapters()
- print('AMHL adapter (payment channel routing) test passed')
Add Comment
Please, Sign In to add comment