Hybrid signatures: Combining WOTS with hashed public keys

🌌 Research Experimental
1

The authenticity of a bundle in IOTA is assured by signing the bundle hash with the private keys corresponding to all input addresses. This is done using W-OTS resulting in a 2187 trytes signatureMessageFragment per security level.
However, this signature can be changed to hashed public keys without any changes to the transaction format or any other parts of the protocol than the actual signing:

  • Create an Ed25519 key pair of a 32 bytes public key and a 64 bytes private key. Hash the public key using Keccak-384, the resulting 48 bytes are then converted into a regular 81-tryte address using this algorithm.
    (The same conversion is also used as part of the Kerl hash function.)
  • To create a signature for that address, convert the 243 trits (or 81 trytes) bundle hash to 48 bytes using the mentioned conversion.
  • Create the 64-byte signature of those 48 bytes.
  • Compute the ternary encoding of the 32-byte public key by encoding 1 byte into 2 trytes. The resulting 64 trytes as well as the corresponding 128-tryte encoding of the signature are added into the signatureMessageFragment. The rest of the field (1995 trytes) is filled with 9.
  • Before the resulting transaction is sent over the network fast and lossless data compression should be applied to drastically reduce the redundant information.
    (Even the most simple version of run-length encoding (RLE) will reduce the size of the resulting transaction to less than 1000 trytes.)
    However, in order to bring the transaction size even further down, a custom transaction layout for that signature scheme could be used.
2

Is my assumption correct, that if Ed25519 is used, there’s no need to “normalize” the bundle hash?

3

Correct. The normalization is only needed for W-OTS.
It doesn’t hurt to have a normalized hash, but as this adds additional overhead and decreases the hash-space it seems better to just not do it in this case.

4

Also, of course, it is no issue to have an ‘M’ in the (normalized) hash, if this approach is used instead of W-OTS.

5

As the hash function in Ed25519 is SHA-512, it does not make much sense to restrict ourselves to the chunk size of 48 bytes. Therefore, it would be faster to not use the bigint encoding of the 243-trit bundle hash into 48 bytes, but using the faster 5 trits per byte conversion currently used in the IO.
However, if the runtime difference is not that relevant, it might be more consistent to use the same conversion method for the address as well as the bundle hash just as described above.

6

We can leave all this ternary stuff if we’re doing this change no?
Just go full binary

7

What about protections against replay attacks?

We will need nonce like in Ethereum?

8

In general, yes! But the idea of this approach was to be least disruptive as possible: it uses the same address format, it uses the same (ternary) bundle hash, it uses the same ternary transaction layout, etc.

Changing all of this might be the cleaner solution, but its also most definitely the much more extensive solution

9

Writing reasons why to switch to binary. Not trying to convince anyone, not sure I managed to convince myself, but just for the sake of documentation:

  • Users can know by looking at the address what type of signature is needed
  • Transaction layout may still have to change a bit due to addition of nonce for reusable address
  • Someone trying to crack an arbitrary address will now have more directions of attack (even though bundles that were never signed with PKC are still quantum proof)
  • Better performance due to less conversions
10

You are right, the account based model is subject to replay attacks. Actually, this is also true for the current network, if balances are not spend completely.
So, unless this is combined with a switch to UTXO (which renders replay attacks impossible as inputs are only allowed to be spend once), we would probably need some form of transaction counter for each account.

11

UTXO or nonce. I understood UTXO is good for coordicide, do we also want to do it on mainnet?

By the way, another way to get rid of replays maybe is to make the bundle essence encompass the entire transaction… So each time you replay the node will think it has received an old bundle.

I don’t know if it is a good idea what I just said, you’re disabling reattachments… You’re also not letting attachment timestamp be provided by a 3rd party. Just wanted us to start thinking on other options besides UTXO and nonce.

12
  • UTXO is complicated but definitely a very good solution as it completely eliminates replays (while still allowing re-attachments).
  • “Nonce” works (Etherium is the living proof) but they require to store the last used count for every spent address, even across snapshots. Unfortunately, this sounds like the current SpentAddresses. There are ways to discard (and thus allow replay attacks) once the balance is below a threshold value, but this sounds like very difficult UX for example.
  • Including Trunk and Branch in the bundle essence (and thus effectlively disabling re-attachments for anyone but the original issuer) does not offer a sufficient protection as the bundle can still be replayed with the same Brach and Trunk and then promoted (at least if it is not belowMaxDepth).
  • Signing everything should work, as only the exact same bundle can be replayed with gets filtered out. Again, in this case re-attachments can only be performed by the issuer, which could be a very reasonable compromise as this is anyway the case in 99% and especially in combination with the Conflict White Flag, re-attachment are hardly necessary.
13

UTXO is complicated but definitely a very good solution as it completely eliminates replays (while still allowing re-attachments).

While UTXO would be the best solution, it probably isn’t for the current situation, in which we can’t have such enormous breaking changes in the mainnet, without a big overhaul of client libs etc. So basically this idea falls flat on the feasibility to be able to implement it in a timely fashion.

“Nonce” works (Etherium is the living proof) but they require to store the last used count for every spent address, even across snapshots. Unfortunately, this sounds like the current SpentAddresses. There are ways to discard (and thus allow replay attacks) once the balance is below a threshold value, but this sounds like very difficult UX for example.

I think the counter (nonce) approach is the most sensible one for the current situation. While it is true that keeping an additional counter per ledger entry - and therefore the entire entry indefinitely, even if the balance is zero - is similar to storing spent addresses, in praxis it will still lead to less addresses which have to persisted overall, because Ed25519 signed transfers no longer automatically mean that a new address has to be persisted (you also made that point on Discord Wolfgang).

Of course, as before, people can still create dust by simply issuing transactions which deposit 1i on X addresses, so nothing really changes in that regard.

Signing everything should work, as only the exact same bundle can be replayed with gets filtered out. Again, in this case re-attachments can only be performed by the issuer, which could be a very reasonable compromise as this is anyway the case in 99% and especially in combination with the Conflict White Flag , re-attachment are hardly necessary.

Approach 4 from my PoV doesn’t work, because you can’t really sign every field of a transaction.
Issuing a bundle consists of following steps:

  1. Create input and output transactions without any signature
  2. Compute the bundle hash out of the essence data (address, value, obsolete tag, timestamp, current index and last index) of all transactions within the bundle
  3. Create a signature on each input transaction signing the bundle hash
  4. Execute tip-selection on a node to get trunk and branch
  5. Do Proof-of-Work which computes a PoW nonce which leads the transaction hash to fulfill the MWM. In this step, we start from the head transaction (last index) and chain the bundle transaction through the trunk field with each other. (the tail transaction (index zero) is PoWed the last)
  6. Broadcast the bundle

The idea behind signing everything within a transaction is to ensure, that the same transaction wouldn’t be applied twice (?), as it would result to the same transaction hash, however, even if trying signing everything, one still couldn’t sign the nonce, because it is the last step of the bundle creation procedure, meaning we can’t sign something which isn’t computed yet. Therefore one could still reattach the bundle, even if not in possession of the private key.

Perhaps however, one can switch out steps 3 with 5, so that instead of actually creating a PoW nonce after signing, we sign as the last step (signing-within-PoW) (which means that creating the signature becomes part of the PoW process):

  1. …
  2. …
  3. Execute tip-selection
  4. Starting at the head transaction: we set the trunk and branch accordingly, then:
    1. mutate the nonce
    2. generate an Ed25519 signature of all the fields within the transaction
    3. check whether MWM is fulfilled (if not, repeat step 1-2)
  5. Now repeat the same for the remaining transactions in order to get the finalized bundle

At the end of this process, we have a bundle, which in its entirety is signed, so reattaching it wouldn’t work, because an adversary can’t create a valid signature. Additionally, reattaching the origin bundle doesn’t work, because reattaching in this case would just mean rebroadcasting the same exact bundle and would stop at the first node, which already received the first broadcasted instance.

Verifying the bundle would be different than with WOTS signatures, because instead of just grabbing the essence data of out every transaction within the bundle, every transaction contains a signature:

  1. Compute the bundle hash out of the essence data of every transaction within the bundle
  2. If the bundle hash doesn’t correspond to what is within all the transactions, the bundle is already invalid.
  3. Verify the signatures within each transaction. (Note that within Ed25519, the address is a hash of the public key and the public key is embedded in the signature). Theoretically the public key has to only reside in one transaction within the bundle.

OR actually (I’m writing text as I’m thinking)

Instead of signing every transaction individually, the tail transaction can sign the hashes of all other transactions within the bundle, and we apply the signing-within-PoW only for the tail transaction. Note that signing-within-PoW ensures that the issuer actually did PoW.

However, I’m sure that signing as part of the PoW process, is probably computationally too expensive to make sense.

Anyway…@wollac, did you have an idea in mind how signing the entire bundle would/should have worked?

2 Likes