---
title: Legacy WOTS for binary input
tags: RFC, draft
---

+ Feature name: `binary-wots`
+ Start date: (fill me in with today's date, YYYY-MM-DD)
+ RFC PR: [iotaledger/protocol-rfcs#0000](https://github.com/iotaledger/protocol-rfcs/pull/0000)

# Summary

The current version of IOTA protocol uses a variant of the [Winternitz](https://doi.org/10.1007/0-387-34805-0_21) one-time signature scheme (WOTS) to assure the authenticity of transactions. It aims to strike a balance between signature size and amount of computations and uses [Kerl](https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md) as a ternary hash function for all operations. With [Chrysalis](https://roadmap.iota.org/chrysalis), it will be possible to issue binary transactions of arbitrary size. This RFC presents a proposal to adapt the existing WOTS mechanism to binary input. In order to avoid the migration of private keys, this proposal is 100% compatible with the current scheme and current private keys will still result in the same addresses.

# Motivation

In the current IOTA protocol, the bundle hash is computed by applying the Kerl hash function to the bundle essence. This results in a 243-trit hash that is then signed using WOTS. Due to the compatibility requirement for this proposal, the actual signature scheme cannot be modified. For these parts, the RFC just documents the existing scheme for completeness reasons. The computation of the input message hash (the counterpart to the current bundle hash), however, must be adapted in order to be able to generate a compatible hash for arbitrary sized binary transactions. As such, existing libraries and implementations should be able to reuse code for address generation, signing and verification, only the input message hash computation needs to be adapted to the proposed way.

In the current scheme, the bundle essence is not signed directly, but first hashed using Kerl. Kerl consists of a) a ternary-binary conversion b) the computation of the Keccak-384 hash and c) a final binary-ternary conversion. In order to adapt this for arbitrary sized binary input, the first step is skipped and the entire transaction is absorbed by Keccak-384. The steps b) and c) remain completely unchanged.
Then, a normalization operation is performed on the resulting hash. This means that the sum of its balanced base-27 representations has to be equal to 0. This normalization serves a similar purpose as the checksum in other Winternitz schemes and prevents an attacker from producing forgeries. The main intuition here is that an adversary can always compute forward in the hash chains. However, moving forward for one segment while at the same time keeping the sum to 0 would require moving back for a different segment. In this case, an adversary would have to break the preimage resistance of the hash function, which is infeasible.

In the current protocol, this normalization procedure is usually combined is usually combined with an iterative incrementation of the `obsoleteTag` field in the bundle in order to mitigate the so-called [M-Bug](https://medium.com/iota-demystified/exploring-the-iota-signing-process-eb142c839d7f). Furthermore, variants have been proposed where random `obsoleteTag` values are selected until the hash happens to be normalized. This renders an explicit normalization unnecessary.
With Chrysalis, the transactions (see [Draft RFC-0018](https://github.com/luca-moser/protocol-rfcs/blob/signed-tx-payload/text/0000-signed-transaction-payload/0000-signed-transaction-payload.md)) no longer contain such a field. It is therefore natural to introduce a `nonce` field in addition to the actual signature returned by the signer. However, this nonce does not only help to prevent the M-bug in the same way as before, it can also be used to improve the security of the hash function by randomizing the input messages that are signed. There are a few steps in the scheme where the entropy of the input message hash is reduced:
- The 48-byte (≈ 242.27 trits) entropy of the Keccak hash is truncated to 242 trits.
- The normalization is not bijective and reduces the possible hash space further. The number of normalized 81-trit hashes is about a factor of 1000× smaller than all possible 81-trit values.
- The applied normalization algorithm leads to a strong bias on the first few trytes of the resulting hash. This particular bias reduces the security against collision attacks even further, to about 138-bit.

Due to these limitations, it is very reasonable to try to strengthen the security against collision attacks by letting the signer randomize the hash with 128-bits of entropy. In this case, instead of finding just a single collision and passing this unmodified to the signer, an adversary would have to find many collisions to hit the same random 128 bits controlled by the signer. This severely weakens collision attack vectors and strengthens the signature. It does not provide any protection against preimage attacks, but due to the general [birthday attack](https://en.wikipedia.org/wiki/Birthday_attack) and due to the explicit normalization, collisions are more relevant for the overall security. The randomization is performed by using a secure keyed hash function, where the random 128-bit nonce is used as the key.

# Detailed design

## Signature Scheme

The signature scheme used by IOTA is a WOTS variant with the following parameters

ℓ = <big>⌈</big>n / log₃(w)<big>⌉</big>,

where n denotes the number of trits to sign (n = 81) and the Winternitz parameter w is set to 27.

Since Kerl is used as the one-way function for the W-OTS chains, the keys and signatures consist of multiple parts of 243 trits each. These parts are called _segments_. A block of ℓ=27 segments is called a _fragment_.

The signature scheme supports the _security levels_ 1, 2 and 3. This value corresponds to the number of fragments considered; e.g. for security level 1, the signature consists of one fragment and signs the first 81 trits (the remaining trits of the input message hash are ignored), while security level 2 signs 162 trits.

In the following, we will describe each step of the signature scheme and how it can be applied to sign arbitrary sized binary input:

#### Address generation

For the desired security level s, generate s secret key fragments

sk = (sk₁, …,sk_27·s)

The corresponding public key is then computed by applying the chained Kerl hash function to each segment of the secret key fragments:

pk = (pk₁, …,pk_27·s) = <big>(</big>Kerl²⁶(sk₁), …,Kerl²⁶(sk_27·s)<big>)</big>

Note, that this public key is never shared. It is only used to compute the digests for each fragment:

d_j = Kerl(pk_27j-26 || … || pk_27j), j=1…s

Finally, the address corresponding to the secret key sk is the Kerl hash of the concatenated digests for each security level:

addr = Kerl(d₁ || … || d_s)

#### Signing

First, a 128-bit random nonce is generated to be used as the randomization element r of the hash.
Then, an arbitrary sized input m is signed by hashing it together with the randomization element using Keccak-384, i.e. Keccak-384(r || m). The resulting 48-byte hash is then converted into 81 balanced base-27 numbers each representing an integer value between -13 and 13. For this, we use the same conversion that is also part of Kerl (as described in the [Encoding section](https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md#trits---bytes-encoding) of the Kerl specification). These converted values are then converted into a normalized representation by following the algorithm as described in [Normalization](#Normalization). The resulting normalized base-27 message hash is truncated to 27·s digits, denoted by N = N₁, …, N_27·s.

The signature is then created by hashing the corresponding i-th segment of the secret key N_i number of times using Kerl. This results in s signature fragments:

σ = (σ₁, …, σ_27·s) = <big>(</big>Kerl^{(13 - N₁)}(sk₁), …, Kerl^{(13 - N_27·s)}(sk_27·s)<big>)</big>

The computed signature σ together with the chosen nonce r are finally returned as the signature.

#### Verification

First, the normalized base-27 hash N = N₁, …, N_27·s is computed from the input message m and the provided r just as described in [Signing](#Signing). Then, the public key segments are are computed by hashing the corresponding segment of the signature the remaining number of times to reach 26:

(pk₁, … ,pk_27·s) = <big>(</big>Kerl^{(13 + N₁)}(σ₁), …, Kerl^{(13 + N_27·s)}(σ_27·s)<big>)</big>

The result is then hashed using Kerl to compute the digests for each fragment:

d_j = Kerl(pk_27j-26 || … || pk_27j), j=1…s

Finally, the address can be computed from these digests and checked against the address in the transaction:

addr = Kerl(d₁ || … || d_s)

#### Normalization

The normalization is applied for each third (i.e. 27 elements) of the balanced base-27 hash M in {-13,…,13}⁸¹ separately. It uses the following algorithm:

function Normalize(M)
  for j ← 1 to 3
    a ← sum(M[27*j-26 to 27*j])
    for i ← 27*j-26 to 27*j
      if a > 0 then
        d ← min{a, M[i] + 13}
      else
        d ← max{a, M[i] - 13}
      M[i] ← M[i] - d
      a ← a - d

#### Multi-Signature addresses

The signature scheme allows for K-of-K [multisignatures](https://en.wikipedia.org/wiki/Multisignature). The main intuition here is that the fragments are completely independent: Multiple parties can generate private key fragments only sharing the corresponding digest with each other. The address then corresponds to addr = Kerl(d₁ || … || d_n), where n is the number of total fragments supplied by all of the participants. Since all the digests are known to each participant, the address can be computed and validated independently.
The only slight extension to the scheme described above, is to effectively allow more than three signature fragments. In this case during signing and verification, a potential 4th fragment corresponds to the values N₁, …, N₂₇ of the balanced base-27 hash, a 5th fragment to N₂₈, …, N₅₄ and so forth until all fragments have been processed. The resulting signature is only valid, if each of the provided fragments is valid. This results in an K-of-K scheme.

The process of generating the actual multisignature essentially remains unchanged and is beyond the scope of this document. In order to agree on a secure randomization element r, the participants should deploy a commit-reveal scheme for their "part" of r, exactly how it has been proposed for `ObsoleteTag` or `BundleNonce` in the legacy scheme.

### Example

- Private key (6561-tryte):

KWUUZYQFLOIH9ZRTIXBYEFDGEECDPDFPKCMJAGBWPKMATSTPZNYVNNAJOVSKDOUJOMWXPZWYBAHXQJQT9DQCUQXSDDASVRLMVXCUYRVXYFIQXWX9LOCKKIUIPZDZEBFYJRNRLKINKQDWLAZYJBWBVSNHBHFZGNKIZXM99OZONCK9UIOIRHODRWACFIQUMZRBH9PAHCWAVERDJLTEBHXXEBOQZYUBCZUZYNGBMESJPEJXLSDHGHCCTKKVEDOCFLIPHK9BIMTXSIPSNJQAOYKGOEYBVHLDNKLRGAZQJZWHZHFTAAGT9XQTOOOXADREHVXAOORDCNQOBUXXAMYDLRUI9MGYYXYLLINKOURUZQABHNNTMVVBNVRNDUNXNNGABTSJBYVIHWVVMMLMFKC99GPRX99FJQAKKWFZWQPCDVUUB9HDGNPIU9OXMUEXUVYWCYNGCXGVYFBRNKAFOBHETVNMYGJALOKIWVSQLCDVNDQBAIZMMMQIHIMF9USKWUTPWPIYM9QWCO9LRYWVZPPYSQSBBIGBVZQZWCFHSZDE999AIHWHIZUTKJDVH9ZFSX9APQ9YVQJESTPRQLYUYF9ESLKPZXSFVUDSFOACKBZGKUWHAOHMDB99EPCUPTDXMWQHSKHMVVMLSJ9XRQNSULWUQFDJBWSKYOCIMCZGQWLLVPZRCUZ9WRAMARU9QJTE9LGQKKVFNPODGRPZTWKNUSUQSFKTJJN9DDRSOMHPBYTRMTRVYSSXSGLVFCGDCYGXTWSVPMODE9YYKKEISEGOHNZUIBEDGWPVZZKZNMRED9XGBOUOZYXFA9H9MKW9NLBKGFCXDVNPURMLBQUZZVEOMVKWDWSTAYVICBGWGCRTTBBUCTNJRFBGVDAHYKP9NBVRXWXTGFZNPTQVZJAZUJSZJSA9WUFTUGSE9CKBPKNQZNGBKYVWKDVVGNPAJBIHSNWRSXBKSXYHEBQUXBOEDNZXNUCRW9EXAKLIVIBPHMZPQMDHPEPGTMZVMAFVVGEQTAELIXIBQXC9EZJXZYMNTQUIER9NENM9YKZ9SKVMYIACRXBVMPNZBCXMDF9NOFSPFYMGCTWW9VGATQWBKQQAKEPK9LAC9WCDEDRPKXFYAUACKGGUONJNVHCZTYITWPLCNQHEWRPEECEIUYBSASCHIYGEFNSBPABTHSUNEREFPMKRZWWRBVGXLNMVF9GGKSWBERALWB9INJZHQ9VSVNKMBMKKLFCUDLQUSVANUKGWYKCREYRABV9QJKQIISHFLPTZXOONJIYLJZNSAR9BBKYOSLNKUZFCBSMUJAPASVAHKNFJZHM9JHHPN9AXMMGKKTO9TKUKCFVMNJIUDLSA9FWYDYOVERMHBVDQFD9VTNBQXAAKDQSMAZPSWDEVLZUSVNLKMXLLRCRHENUOLTFVNYQANAKZOTAZGBGFK9QYARECOVTXAEJTRSHRPVWNBWKCHYYYWWFNYBPRCHTVREWJNAUKBYESVEHCSPYGZZNUHAVMVFXULVKEGUKQ9SYKISAYTR9ZEQK9QORWUMUEBKWCFCZFRNDUIL9JWNHHKKCGDJJOWNUZSNWYZPKZ9QIJ9LMWPERKMAKPBTOVKFWKDNAG9ILJFHXHYKFWJOIYKZJJDCLKOKLVBATRIJAFRHHRCGEHGPHSLZNMQE99DJNGFZHRUNFVGLZWFNLMSVNIIQLNCJISRYRA9QUUWWNLFUFVVBWHSUHNPSUJNFAOGOPRGLMVFPMRGYJ9AVLSYAMWZAILWJFSXFCRYMVMN9PKRPWBIXNBQHB9CDGQFSZQVKRGDVLKEVBIDWKTCZCCQTUATMHOSWSPRHUJSJPXJQADBXVQBOBWAOGLJ9TMWMIDPUNLCTZ9RQZECIBYJJENB9VQZHAPPHBYLPHIFGLXLQUGZBKOLIGZJUNJXBN9OKEGYPLTYGXSZBKSNTBPXIVVCDFQGYOCLNSRBAREQOJSUJMZ9URIRBFWYAVBPYEXDDVQLVFOKWTPKNBWDAYNLI9AVMARHQLVJQUPTJEJDOTEGYGJDH9JOOZIXSRWIPVJRBM9ECHNLXCXHGJVD9GDFNXXBRAVTRMVR9VLSLLMLCLGAPOBRQZRCHHKKDWUVMKXJCWWZ9OSASYOHYZFORFMVZBK9HCAOMKO9WRWCBDAQXHHMKTCOBDRTQYRZ9QRSGHB9GVSQVHZOFHUSHEDWAXZHEKTUIFLAULUSATLMBH9VDFJRLHJ9KUNGIPCSCVKMCKCUJFC9PGDQJULKTQOFVSLHVAKHYZYRPKGDPDDNIAKVOFEVOKPUNMUXIIOIGSEMZKOAVCTHBPVOXFHFKWEZPHPK9ZGBEXVXNNPSBNHMMDIJJZHI9ZDMVBWZSEOZIGWYL9QQLACWYYGDGRRGWHDQCMFFEYJBUWGCCEUAGTYACAZTBGZRZCS9QAKJVEGT9NBLFVSNQRKMDMXKCBIPMOSNKG9LIWWMFXLISAP9EADUBYSJDRJWPSGPPYNKZICGQXLB9KPDAL9EGHBCTWJNIUDYGEPJODXRGUWAYPTBDSQWAIGATSYYTEGYE9QTNGUQOFVMEDOZEOZSRNFTIARWKBCJBSQXZRD9USMTGJMAGHMDXHWR9NSJYFMOMMDOPAQGRDOMKPJLRCLVEPVXKKEVHESLGCNQSHNOHM9BOGNEVAZJDKSHQDTRXNQPPXPWOKPBYMIZYVPI9STBNBOAWQNEFNZYCVUASIKQYWZSQWOKIZTSAZM9GU9YJOVXDVYZ9W9VSHPNOIGKRISD9MF9YTMWDBRYOBFMQPOLITWRILHZSDJXDUDSBBIPWLSECNKHCOAHXKBBDKYAOFJXTXUYQAFVKORYGQNJDOYHDYONMTJKLOHOGBGNOHKGAPQ9MENUKCBNCTFIBZAZYRLEFZMYSHLRWFBAG9YHZZ9MRHHSA9KOVY9NNSJZE99VPLGMYZTDPGCKVRBIFHJUWDINSYEHIYRPSUFXIKMGKRINR9JHNJRYQVNJUPLKMEUYAEJ9HPGCKJMLBQNXTNZHXXLCXCYFRGKWGRLTGZXGADBSASQACEJZGDBKGTQIZMBGLDGRTH9NNBTDVMATXFEVDWIQ9KBZVDSZAPSVLOZ9YTATBEMFJZYSFVJQIUONFXBNDSYRHIQBXMIN9TAR9ESBCIKXAGSTAFVAQRUDRSWQXQOTBYSUCDQHJMFNNDGAATNGCEILFFWXSA9XBCZLBNBBIDQLSQFU9JFAHFKDLSNDNTPOLYTCTRTHKMXTMGUDZEXJFJADKLCLTNNBFFYMMYHQJWVDEUGKUKQNAZB9NNVEVHNMSNI9OKDT9O9NJHJV9YYWVZQDQQTPGVCGDNXPWOUXUWDLPBVMOKC9XFKRCNCVYIXOGBVTPMWDUBHAYVNTUYZLREFGI9FQ9TGYYQKYPXGV9TXWNLZYKAXYHJIDCSAWWQKLSOWOZOTBJOZUWHVSGBLRLZLFBYSIGSJQ9IVDCICXUWAQWVBDTWZWEFLUJAXARQFNGYBUY9RDF9VNJTFQMMYWIAKWVNPHNYHGCCJCGRZD9CHLRNRKRSVOZYZGMPJFPDFWPFIEVFUQ9A9HVBGBOJUQGHDTDICBQHKDDERFPQOENXVLMAKELMYFIGDJPJQHPZOXLTDIQODHKVGOTJDXAEIIJHESIFO9VRKXXFXE9DHZ9OB9KKOJXYXTMFASAVHLJLLOTCGZXHZVPYO9UXOHBQOEVRGWARSFPIFCZOBQSITYZL9WJAGGUUPRIMFW9LAFCMOB9SXFVXJCNEVKCWGDPGBUIZZDLNMQNYPLWESEVMLUNSQGZBROUKEFJJ9Y9NRZMQYIMKISZRKHTQIPTZCFBFLVHGNFMOJKLIHHMHGKMRHFLHCMIFJAMEOREBUGTQXPJPMGJVRCYIRRLRGRGCJSGM9WOTOLRUNESV9GHXSYXQSBMRMDEQPWMCQQWZZUH9ABBSOXTQVKGKCBUTSDGXXUFWPLO9JLDGZT9ZLKNMGJEEPCUMWCLST9ZMWGMQEWIRQSJRWHLEZOWHXZBIPUG9YC9SRTKRJXKZPOLMZFQPKJKIBQ9ND9TESYBRZLMTWGURTGUXVVW9MAHAVMQTUOHZOLUD9CCYGHPGHYMKCBWZEFRXTYVEGGFFWHRELBJBKHAGYNQGXZASHD9NTWVCFUMKIJFCUWHIXKYDWXGKEJRPYYICWTOOFAAPPTZ9BWCGTUDJYRZ9DEJWDFWCFMWVCRWLPPNQDDGMHFEHRZDHNWTRZBFRJYUDUDSBLPCSUUAOAV9XXYDYBQQCKEILXJHDVBRFEYLHXXQEE9PBHMKPKXNHEWPFAZXU9FCAZCCINBNRLH9TWTFZTDUYGUTD9PPFB9ZKJDDKEYOGWGAMZS9LEXPYRFGKLUPHXECQ99ANLVYIEUEFCCWIIIUGPBZWLKUOYI9ZVEVGQWVWWLXGM9CRHKUYJNJRTTAVAJKYXCOASHI9LQCEGXHWPPWOL9HOJMR9EEDLLYAGLBOZHZCWZJUEQVXASRTPZWNB9ZLBD9KDVJZWWNLXREBHNFARZFCNONPRYZQU9NVWEYNEBJSOJHQGBPCECSNBBRHWNAILQUPMMDITTAZPIOYANUSUZMIKCTNAMO9CAGDXOC9CXFLUTKYWOEAERKDZTIFE9KLJINQTE9VRTCJRUMTKXVVHNMVWKESJAWPUIVLV9UAQWLEZXCTUQU9JLKVCMVPQDQEAFMUXVOXXJNYVJUMHJBFGQ9FIRGWKSLPYVNNODSIFHGRVKJJDQFJH9KHUTGFZSNBUBFUWBKYUWJWCDTBLXZKYAWSGRNPIQUDVVXD9DTMDRHPWVU9NACEEHTMIYDPQKMGRAJYSUW9NXE9APXFPCFKRAEG9EW9PSBHZFDQCSCSTQEMALWS9VN9HAIQMXMJLAXEBYSOSQBUVNLGUYGUFQUZBLTF9GUGNYXZUTRYUSUYQOMSTDKIH9PIPYJV9CTPMXYBROMUPWVEGKKYRNWJPCDH9IRFQJLBPQFFTXDFTMJFCUSW9GSFHFNPXZWCKF9N9VUVUIURGHMLBYVWNYPN9KPVKADYXHFINZZWRUAFUPI9HRYMCNPIHKNSLHQHHLGJWPJQSROPSUOMR9FNQPKCZQWUDCAUQIOKORL9SMKOLHYJAAFPKXTRXPTJTBCHONTCCOTGLXWO9ROB9QHSIUTHUQRLPNCSMNTDXVUNIBMVIDECXHGUNCFFFAUCAHFXCRKCBGK9LCNX9U9RLEYCCQMRVDLXXQTAQ9PYBCTZAIQCGL9PY9KOPVLJWVGHMIAL9VSBIAESQIXHEP9FSYQWTQOQQZCJPBTSUDHCYWMZXWTVRVUWAMQDOSNITLOPRVHMBYPPSNZKWQYMTVLRHWVXUWMTXLHAULAI9NGXPBRBP9PZSGQWKBKJSKSNJIBNUEHEMWQABRZPPWT9HKAMIWSOOE9FDBADIVQVSVPUDH9MKP99UXXQCGRTONEBQBLKXZXUR9UHQQQTOTYWGUFYXFX9OCOSFXLLYRPZXGSJKCCNDRRWTCDXVFYLTGDKUM9Q9MNMJOZOQVIQQ99CDATJAWPFCHMJZRSNADVRDYFBFV9IFFIBIHULCKPQFJFPVKJMXXESLXUMYXPNUDOCLXR9S9WKZKOYFV9AQQBWDJYIUKICSOQVXYYIDHV9GANMM9HQYGJFPVAPROFAAIREYYXOVCQXWUKYIQUUUWCXAVIQPIRFHFGGOBE9VAXSXXFPUAKNPHEUEGSRFAKAVVQNYLMBZPZ9WL9RZNSLMKUOL9NBNGLWXMSYATIXHUAESVBPOOEBFQIAXRONQY9OSLOLTDIMMUDYHYUVEMPQRTIDRRXCHTSTS9EQYJXNVQLCRFEGCCKESCVLA9NQABUGTMGQOPBWXWWBSYRXVDIDOJSBIAKKCLXO9AWXXSBMMSZDCMUBYVXPTANHQGBLUSHJTOYY9HSBXSMUSKCMQDZFJWZZEIBGBKMPRYFABGQULPJTXTCUVUDHFSVLOVURTZ9YVIHZBLYPGBOYEBDFRZRGWUP9NKORXNUVCULWTRKLYRBWDCVFEC9ML9VUVAZLAAISSK9LVMPMWWNJQ9MD9ZQKDESNKRTGFOTTDVTLGOKRERBPDXTXFRIKCRBQEZRWXQASJNP9UUXEQPCOUT9NZNWASUI9OIBBZAYDYQSSBMYWAYGIFMSWC9NVTWECETSUBIKWHNEJSQGTCXCHYXAROROJJPPTLWNENOBX9WLYJHMYLDEFBDKKSNCQHIOVRJJCHJKNCUIJAZOXNYWVRQCC9XZL9CSDIVARKWCESWCJGNJJGJ9IKPBZSJWICURGBGWNQYXNNWLFJHMWWIWKQNFQIXEEATBJDWUIXMVUYKEWVU9YGOVCPODDI99WVYIDCENNZLOKD9ZOYN9IKH9GZDYHHVASZZR9TLVUKYYV9CSWMJTP9RQATWW9ZZMYPPXELKCTNBF9XEAPBAQEVBGJH9JUR9HL9NQHBZDPVDGAQLXDAEYNUWGQIMRMSIOBNERUNRTETLTN9CJRINFISJECEENNMZYXIORQGWUEWPFJTWWDPF9WKZYCXWRLKNDDOHDVOWGBAO9DIZTECCILOQXGVTSKQI9TNUALPSJCHXVPAQX

- Input message m: `48656c6c6f2c20576f726c6421`
- Randomization element r (16-byte): `000102030405060708090a0b0c0d0e0f`
- Input message hash:
- Keccak-384(r || m) (48-byte): `e992bab93a9450bd9c4ee3a65f3251353207974ef5a877effda6d4a52e5010ae622127d52be251450584c8b1ab7f4b8b`
- Normalized base-27 (81-tryte): `[-13 -13 -8 4 -8 3 1 4 4 -1 2 -5 3 -4 12 -13 13 6 -12 -8 9 7 2 -8 9 1 13 -7 -8 -5 10 6 -3 -6 12 -9 -5 7 0 6 0 -4 9 -13 6 -5 5 -11 2 8 -13 4 1 13 -13 -13 2 -1 1 -3 -8 2 -11 8 -10 4 1 9 -2 12 11 11 -6 -7 8 -1 12 -7 4 -2 -1]`
- Signature (6561-tryte):

RSTY9WUJGJZMPMYGNWBEFM9YTIV9SWWUCLEATDPIERQEWNVEFMDNVIQYNPVCNNOTTAAGFLQ9APPUUPFYWVFJHHZNWUTQ9GOYEROOCFQIKGUIYRTBDTEGHDACLKXIZVDSEKM9YYFQHXPQWMGYGSWBXBHUPL9NJOGC9WMTGVSMFNFDNFNBQCRVWUNDAWAA9UUYLXRMGLRHGSFKJSIEDYRMAUYCAEOIO9FAJX9WVXUDQSJXEGSSDXZCNUNCLWFDWZDWEPCZOAEFYHFHP9ZQSORMYUPMVMBUUWJTHBKLVAIKSQVTY9CMYVNDCCHNDR9P9WFZJCQXMSGFUASIPTGHXEJGAAKMJQFGBHWMXKURZJGWOGLKN9ZOOJLUCXBEFIDJRNAGJN9POHVBHRJXMBNUFIHLWUBJN9LDBFRLTUH9HCGHYMXZZQGDEFRIJRBOYKJWMZCDNQBDAXKSLZER9GA9GCTZSDHZGSGMZO9URGQZFZPKYOULGOCYNFASZFWFPNKAMPKCBAXWFPVBTWUPYQCFYZWPCNNKQIGTCHPUUEOQQV9XYZXRSJNAFWXEPVWLENKFDUTNGIJCQREBBHIQIXZFPNNLPQMVWE9ZMHKRGPBNJOYCEZRVNZDHDWAJEQHHUZFQQHWAWNKCXMZDHEVAKSCPOOBBKMDWGXQURWNYWJVWGUETQUSPBHRHQLHXBXDUXBTHXTVDSJSFDGSVDJLHVWVZWELKBNNTWAWKMZERZRIFNGHEK9LACJEXVIARKLGYZFUSUTMMPLNJQMCT9NJQAZCYZSTYEQYLDXJBVOPBZMRNRRECBAEHHZVNOROOQTIEHIAVWQSEWADI9GCSNKXVP9LSDTBXCFHDQMEGMXYPSW9TSBJI9GPXFWAQNMRIAZMETAYXHIIAUQBAWDBDOKTSNLOYTYBJLBYGAZZRECBJVCZYCNCTJFGXFH9PZ9WJBCFWYDH9YLO9SUCQVLBNBFTDCIMKDFMAYGJIKXRFNJYUZTTRXRPHMPFYGZEIJYKJRXETUSCSXEXFMZLC9VSCZGLPJFCJLRKTWSBSQFRHCTLA9XTGFJUSTWOCYLBMQWBFGRXXOOFTVJVPV9OYQWOCGMIZFPUBHSJLXPZIYOSPVH9UGVSTURRYTOTOXDNWQJAP9F9VYHX9SMUOWOZFESKRUZJSVKIAHIYKOQG9SKAHVGNOBAEMQ9RKODIMNFLYZXCOUSDQGYCMT9CKIWCWYVLGAW9HPIEVHFMZ9ASUIYVCW9ZVKIXRSGPKAXPABIOWCADMD9FGCQMPQGAMISJAKLEJOBBDQBDDBSMUJAPASVAHKNFJZHM9JHHPN9AXMMGKKTO9TKUKCFVMNJIUDLSA9FWYDYOVERMHBVDQFD9VTNBQXAAKDLPXDSPQZ9ZVCZB9S9GL9WRVGKUGM99OKCQJYLGBSTBKQSWFEUBWO9ZAUKXRJTHRQRETPGJRJBPNXXSMPWDGKSCEODTOCFAMUNPIPBGHHJAZYYOTMKXJPCXRVVMSTWTQFKMZLIKHPXAKLEFCHKEDNWRBMZWCHQPXTIZFXZUVXFKFJZGPRVMMFMU9FAFJEHJGMOVLDFXLCZDMLLYXHXEMTLQ9WIUECTYPWGGKWF9HNSZEYTGZYAOZZL9PO99FEJNAGPNKNJYRSHUFPMKRLUARXZTPMXQRYS9MEGUFWTRLRYXDKZAQNAODGNUQCGWMBD9JQZAR9MWQGFGWPUMHRBLCZNQIIYPRPWMUGCDNNKLDNKSIAKWX9EMNFKUOTKHDZVXMEJOLHIRXGNGANKKJGWEFVALY9ZPFFJVPP9MTNLJSLJDDROXSMDBBHZMNZYNCUMTKBU9IXGCOVN9XLIZVCPTWMYE9RBNUAGKGVCFNFNDYKWBLYMXVHQFMANS9WA9OMEOZHZEPDCBFEHPJ9YXERFJWOMQJDGUCIKEFIDXPMYYOKFNEHAVAHHDPNBVCRVLZSAXGPATDXLJZUYSPHAWPEFWALQIASSHVCKFXLIPTQTENBTBPHAOPGMQSOEXIRCB9XEBCK9XKFCCWXLRDVZFZZ9TDQWTXMSCYVPVMLK9VEOQFPBEPUAGIFGYTLOVHABJYXDKGEJTE9XFUEZJDEIHKDJBTVWZPYYWWZ9OSASYOHYZFORFMVZBK9HCAOMKO9WRWCBDAQXHHMKTCOBDRTQYRZ9QRSGHB9GVSQVHZOFHUSHEDWAXSYLHGUUGQWW9AAXCGBTZ9BJQWWDJMEQGSMOKOULXJCAKRIJOAHHJYEEORFNIYLLXMGNFL9CUYJSQWBTA9UAQX9EVHCRBFUOJQJBHSEAVXNNOOEG9ZBDRQKIPWHLAZVAEXHIRWRVLKTYPAZYD9PMJLANAKGQONWLDLWXRSFJWEXFTRFSNUXSYM9HONSBBZXEHYXKPLBIPIOYXIHRILYPAGTD9FNXNOGKPCPISFFCPGOZMEFQS9JAHU9DDDBD9XZBEAFVHUYCQENYVBJDW9YFRN9HYKZAKFGWGIEGXOQ9JABFEZVDSLNT9AVI9XDLAFLXDZCFDPRTTX9DWURJILUOTJTOHGDFG9DVQAXPXIJIHHSSB9TVYUPISZEYBIUCXFFYFMSVSKNFECTLIIXNOPNIVDBUTDBJTCMRCXYWSLSZZQLWEAPNARGXCDFKE9WCGRGHQRNSAGBNTLIWCHACJFFGWMVIMAYSS9IN9OYGN9CPRYCSXFGSIVZAEZM9PNGI9ZFSDYMBD9NDBRAWLXXPGB9MRNGSYFQR9MCBA9ZWBJMMZDUCTMCWHFGCVKLDKNFHREPXYBJDZWYYPVNIU9RAUTEJXIFUHGESGADBOXNYARALXSGHYUOLVTGDXQJSENJYQIVOSTQP9BEEZOGYQKAXQEBTVFYLT9BWRNZERNTUPRLYRYHEZW9WNUPWMZMIWYMK9NNQZJBBEKAZPYQINHXURNREQUGMOXPFQWKBKKUYSU9GHLLLIWTGVI9PXPWL9UGGHBEWUCWAQ9FBEUMTZANFHYYBE9CFZOMPPWDTNESQDEAPJSZZLQDBCPMQCJHCQHVYDTLLBHTAUDNMPGQYTBIYSPXCWOABZIIAPNQIMFECAAMRELGUBMFROADKOYNHYRUZQFABTREPEABDVTDOLXQXWJEIHFROOCEZUOENSREGXFJOXKT9HOFCXJAQGNFHIYJFB9WXLZIIKYMCLDOMCGSRXAJLXONCUZBNGHEAIHFMZWYVWZPEEOAQMLQCUAFLPTNOG9UZOCMZGL9MGOYRJAKEOGLALGHAC9EZSDQHODCMSDEON9OGZYUHKGHTSWICTNPZYAUFVJCQ9ZHQLAMZUIXIMSNPRJRZSGFEOILQPWVI9PBRYXFMBAYBKBJKSJSQKKWILPDZHYMXXLZBNBIRHZXBQPJERJYTFNIOGROYEEJVFSPY9IWCHOYURN9DCEZEXZHIZFHWBDTARNSLWQCLZCURTWNIUKE9AZVRKPPKYXCHMDNTYHBJHZIZXFVJ9SKSGAALJBKTLIBFJGXFVWVOHMBMWUAFFXWBPJXCZHVN9PTOYNDPLFKIUZEWTO9XSIMCWRJUSEEJDH9GJRARSIALKKE9ODQJJGTBUFCSGDHUODLNQRHAZHSYKQKFOPQELNPSJIGTMCZSCGYNUIAKNQVCMSQQYQWT9LZKZNFDYJXDEH9SKRYO9KZWQKAQAHBUQIBCBWAKUWXTLVFSASHYCSBUIKQWOJUNUPBGJMHSCEQAFHWSRFHXNHZVXKGE9JWCCIPLSFSTTWBUBDQBIEUNSFGAVIEEJHFNGMQXPHOFIKEAZUIKLOJ9OESOSXZAXUNWXXMAYPRVOYYVSGYB9UPBHFZHTKXFVNCBXESZZPPPCIDGSOTRQWPDGZZ9Z9ZTYSXPNWFISNKKYEFZH9HARTHGUEJVJWXRYHBJCIECSXPQOIWFUJQAYYOISGZSLVSEPSJSQNJZZULEY9TATXQCE9FOLRYOBC9KU9NMGXIOHFRUZKRZKBG9CSTOQXZBEKQHRHCEUZXVXKDMQNRSLMLJIMPQBNVB9PRSJAYCOCDKCIILKBQMDSIXDQXNDNPAAPLFQOUQSHLVME9PSSFJCTUGBHDXILRWGGG9WWFWOMMYXFIADEPLYMKZFOOBRV9WZLAFQR99TVROWHQLYOALPRASLIHUS9CKBJTXENAMHKOLCFGNHORQFTRSAWZOLLSAHHRVWQBAVRBSJIFIJFUKHORORGBPKBSSFJOBIYOTDLCFF9WVNCASPLHD9FWWNCUTZVWHXEOSPNDXFZHUIYVDHXOLDMTPEWGPVFLPUUSPNMMTZVXKNPENMTCMRPGDTR9DYPIUIBSQYHVRAMYNRLH9TWTFZTDUYGUTD9PPFB9ZKJDDKEYOGWGAMZS9LEXPYRFGKLUPHXECQ99ANLVYIEUEFCCWIIIUGPBZBMIW9IONAJEXOELGIEEGTVRFNMVLXUSUYVPINRRTIJKZHNFGPVAZRQLTOHUWZDGXQZFETWQ9QZTC9MZQXCCVJTB9RVMAFMDMKQPDJRXTJREZFKBBKIYFHOIQPNPJCKOCKWOFGHGIVC9SQNEDNCVYRJPH99SWZOYANZRILKGOXNYLFLAKMRQXEQPOORLWQTWGBMPQFEFKEQRCMHTMGZBVJJRXAIEIRSQJVXNARWSKGIMQHLIAVNDFP9BSVNPLEHABGMACETQGHFBOODQGR999QVKWHFVDF9CUOZE9SGUNIHCBLZPPKZQPDJJJTYBBSVBULCYDKKA9MGZSFABTKLAWPV9OEWYFGFDEBWVCQQ9MRP9JZKHFHQUBSXKZKGWCXPJSE9AXYZQSONBJC9PLTVTHDCLRFCNABKWMVFQLCS9THLECFMXYOPPKCPULTSWOTXXBNVFMVCGI9EOQJNKJBIWBYABMKFAVBQGDNQOAKZDGOZDXFDAO9JYKRACWGYIRKXNOZKWKEMNLGOHOMIJGDBTEDEMRQXKOLEU9JZT9JLQ9HVFYS9FWUMVXWXBNNXKHAYEMBNFWJNOQBTQFGCOKRFLJUOYNDGMOIQNAVTPAJCKTFNNGOZZGOMKPATHGPMMEFJFTAOQOQVJWIG9HMPPYNAXPFPHCNGEWSOZ9BEQLMTSDNXNWPDMDHTCGZMMOXKWPHEEUWUFWGNKHSZENMDXBXGYLTXTLCWPHBZBRFB9GYDGDQ9UPMJUCARFJVCOBZZOUWZKOTAPQYSGWFCZEZSJI9VWZDMQOHABCVM9GVHGAOQCTE9CRO9VPHTN9BVSFXKIKFRTLCLXXTLORDUFKRJCIVKJHHJGJOJBOOAHIVBEYEDCE9FRV9MODHRMAJRDYWQZLSMGCQNEPLRLJBE9STFTORZBVDS9J9LSBSPLDKFXFPNZWMEEMNNQTFKDFJFFBTMCBNZKENLSJGVBBHPZXDG9GKTFHHLU9NICHTY9JTVLGYZLFWRIJGACXFEZNFYIKGRYSJJEWOQELJBSTVDRFATSKWALZRFDUZILHDQIFYWTWFFERXLSHVWCKD9NHKXSLDWAMGP9CHHQFLVVVQQMHFECEGRVDQJIRK9JYAHHTFYBAMCYAFKQTT9HGUCBKJKNCUCWYS9MXUDEUUOBFWJDVTFU9CDUPKKOBFPYUFTLYMGPIMAK9XZHZLBIZSFJNSBYMBLMNBDXLQFLXOBQYFEPJFIZXWEQAQRDBFPCJDDFTRSVWLJIWBSWZIVGLGGVCFZ9IL99PULQMJ9BDUEILQRBJ99NDLPLMPXRVUGGQMTJFQJ9MXGWBGAPSZYKJVRVCT9UWRGDHBTSOJRHA9S9CHPUENFXPRELJBHKJQ9APZNEPWBLUMIEIFXQJUBOFNLHERNK9WZ9LFHCBMAEIMZQIKMMLRQGPQ9XXQ9GNLYHWHWRYMNBMFWRGALYMBIYQKDU9TWAZAW9ZTLYWTUDGEOBVBZVZVCDELSPVNDRRRVRXQWEBVJECMMNOOPIXWLXMOJNP9QFIHLUYACIUMEWEKLGIOGHIRHTUFBCPSJIBLJPSTKAT9YKRCIRVYAMMYFZOEGQWYFAAOTUJFQYJDFACEQ9DFKEJBWDHFPEDJLSH9O9NOAWIZWOJTPKNLZEFRRTLEINECVDUYZWCBOEEHJYLPBFTLUKROZGIXAGUPMGM9GPHHTOSRJEOAXQGGNFIRETYNOHWEZMDMOG9HWYUNJKGFOFBSRGNRPQELCQLCGJUWSVPB9OQPSLINFAYMLHYIDLRBJZSJCGHJDI9IUMSDFHGKOTTAOHUDBPTJE9GLQYYIBSKQ9TRVXFMPFEPM9KNXNNXQDAXT9DRJXZRVGKTK9LNENWPAAKUEVQGMMEU9MSTJRKYULSOTVL9PMBHZYKMRKYFAHCKBBXGWFMQDNP9UGGFRZVBPOIM9YD9VKJHZUSBIYCBPDTBKWVLSPULGYJMMQXJVIYSRR9WTQKNWSUGHLZIPCATPBLZZHQN9M9QPUFYQLESHAZENVR9CSNBYP9HJXXZPZRDO9FFRYPAEGE9XEKKYQNIUWXICVZJPSBGUUPKZG9ZJS9RRIBPWIMYEIBTHHYTEMR9TCYBPCURNSPCDRKH9TPIIZZDEFKONYLLILKENEIYYRULXGFOCPOGYNQINCPCXMMECALXSXMCFVSKDZEHXDJNUD9

> Example Go implementation in [wollac/iota-crypto-demo](https://github.com/Wollac/iota-crypto-demo):
> - WOTS computation: [pkg/wots](https://github.com/Wollac/iota-crypto-demo/blob/master/pkg/wots/wots.go)

## Encoding

There are essentially three different options how to encode the signatures consisting of several ternary Kerl hashes to convert them from ternary to binary:
1. Convert the entire signature using the `t5b1` encoding.
2. Remove the 243rd trit (always zero) from each segment and then convert the result using the `t5b1` encoding.
3. Convert each 243-trit segment to 48-bytes by applying the `convertToBytes` step as described in the [Kerl spec](https://github.com/iotaledger/kerl/blob/master/IOTA-Kerl-spec.md#trits---bytes-encoding).

The first encoding is the most straightforward, but it also results in the largest signatures with ⌈n · 27 · 243 / 5⌉ bytes for n fragments. This encoding is malleable and, in order to prevent this, the node implementations must verify that a) each 243rd trit is always 0 and b) that the correct zero-padding has been applied to reach a multiple of 5. This complicates the decoding especially since an incorrect validation could result in a security issue.

The second encoding is very similar to the first, but the signatures are shorter with ⌈n · 27 · 242 / 5⌉ bytes for n fragments. This saves 16 bytes for security level 3 signatures and even more for longer multisignatures. It also simplifies the validation, as the 243rd trit will always be zero by definition.

The third option is the most compact and probably the most performant encoding. It results in n · 27 · 48 bytes, which is even 49 bytes shorter for three fragments. To prevent malleability, the validation must include a check, whether the last trit in each 48-byte segment is not set, i.e. whether the corresponding signed 384-bit integer is in <big>[</big>-⌊3²⁴² / 2⌋, ⌊3²⁴² / 2⌋<big>]</big>. After this validation check, the segments could then be directly absorbed by Keccak-384 instead of requiring an additional ternary-binary conversion. Also, the encoded 48-byte segments can be computed directly from the Keccak-384 hash by adding or subtracting, respectively, 3²⁴² from its 48 bytes without any ternary conversion.

# Drawbacks

- This proposal introduces an additional randomization element r, which needs to be generated and transmitted together with actual signature. However, the additional security gain and rendering chosen message attacks infeasible should justify the additional 16 bytes.
- The bundle length in the current protocol is unlimited, which effectively allows for arbitrarily large signatures. In order to fully implement this, we would need to also support arbitrarily large messages. As an example, for a 5-party security level 3 signature the message size would grow to about 20 KB.
- The proposed solution by itself does not offer a protection against the M-bug. Integrating a mitigation mechanism inside the actual signature scheme, would not be possible without changing the address generation. It is also important to note that this bug stems from an insecure private key derivation, which is not part of the signing protocol but on the client side. Using a correct and secure derivation is strongly favorable to altering the signature scheme.
When it is still necessary to sign with a private key suffering from the M-bug, the randomization element r can be altered until the corresponding normalized hash does not contain any values of 13, i.e. `M`. The is essentially the same as modifying `ObsoleteTag`, which is the current default M-bug mitigation.

# Rationale and alternatives

The premise of this proposal is that the signature scheme should be compatible with existing keys and addresses. Therefore, other more secure variants of Winternitz schemes (e.g. like [LM-OTS](https://tools.ietf.org/html/rfc8554) or [WOTS+](https://tools.ietf.org/html/rfc8391)) have not been considered. However, modifications of the calculation of the input message hash are possible:
- Any other cryptographic hash function with an output of at least 48 bytes can be used. The rest of the signature scheme exclusively relies on the SHA-3 competition winner Keccak which provides the highest security standards. Computing the input message hash differently, would require the addition of a different hash function. This would needlessly complicate the implementation of the signature scheme, as it would entail two completely different hash functions.
- The base-27 conversion of the Keccak-384 hash could be adapted to increase the entropy of the input message hash. In particular, using Keccak-512 or an alternative hash with at least 49-byte output, would increase the entropy of the input message hash (prior to normalization) to full 243 trits. However, the described conversion has already been implemented and tested in the context of Kerl. Therefore, it seems like increasing the entropy only by a factor of 3× does not justify the additional complexity in the implementation.
- The explicit normalization of the input message hash could be replaced by generating a new randomization element r until the hash happens to be normalized. This would remove the biased normalization that has a higher chance of collisions than random normalized hashes that would be the result. However, this approach would require a substantial amount of work to "mine" such a normalized hash: For security level 3 this would require about 1,000,000 iterations in expectation. This would drastically increase the number of computations required to produce a signature.

# Unresolved questions

- Select an [encoding](#Encoding) that provides an acceptable compromise between encoded length, performance and implementation overhead.
- What is the best length of the randomization element r? The size of r has a direct impact on the susceptibility against collision attacks and, thus, the security of the signature scheme. 128-bit is only the third of the entropy provided by a Keccak-384 hash. However, as the base-27 conversion and the normalization reduce this entropy considerably, having full 384-bit of entropy would not be necessary. Another option would be to make the length of r depending on the security level, maybe 64-bit per level. In this case a keyed hash function must be used that is also secure with respect to dynamic length keys.