Sea of Signature Schemes

Cryptocurrency includes the word "crypto" because it uses cryptographic functions to sign and secure transactions.

As we'll be doing throughout this piece, let's defer to a security source for a brief explanation of hash functions: "A cryptographic hash function is an algorithm that takes an arbitrary amount of data input, a credential, and produces a fixed-size output of enciphered text called a hash value, or just 'hash.' That enciphered text can then be stored instead of the password itself, and later used to verify the user."

And now an easy depiction and explanation of a private key signing from Wikipedia:

Alice signs a message—"Hello Bob!"—by appending to the original message a version of the message encrypted with her private key. Bob receives the message, including the signature, and using Alice's public key, verifies the authenticity of the message, i.e. that the signature can be decrypted to match the original message using Alice's public key.


Alice signs a message—"Hello Bob!"—by appending to the original message a version encrypted with her private key. Bob receives both the message and signature. He uses Alice's public key to verify the authenticity of the message, i.e. that the message, decrypted using the public key, exactly matches the original message.

Scrolling through a list of hash functions, it quickly becomes apparent that there are a bunch of functions, and it doesn't make things easier when the naming conventions are this foreign to non-cryptographers. In the class of unkeyed cryptographic hash functions are families like BLAKE, MD, RIPEMD, and SHA. Within SHA are SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, and SHA-3. BLAKE is a similar story with BLAKE-256, BLAKE-512, BLAKE2s, and so on. Other classes like the keyed cryptographic hash functions include names like HMAC and KMAC. Checksums and universal hash function families are two other prominent classes. And that's only the surface layer. Picking out a few of the hash functions and digging deeper reveals names like "quasigroup operation", "Keccak", "HAIFA structure", and "Merkle–Damgård construction". With all of this lingo, it might be easier to understand with simple visuals. Here's what a SHA-256 looks like:

Cryptographic Hashes and Bitcoin | Manning
Credit

In the diagram above, you can see that text inputs are being fed into the SHA256 hash function from the left side. The SHA256 function is spitting out fixed size 256 bit (32 byte) hashes that entirely change when even just one character in the input text is altered.

If you learn better with hands on experiments, here's a great online hash function input/output app that should solidify the concept of hash functions! Type different inputs and notice how the output changes. Click through some of the different hash functions on the right menu bar. Get familiar with this app, because we'll be coming back to it.

With our newfound high level understanding of signature schemes/hash functions, let's dive into hash functions as they pertain to IOTA.

Tradeoffs

Since the beginning, IOTA has required transactions be signed by using a cryptographic signature scheme that's very different from other protocols. The scheme used by IOTA has been touted for its security in the face of quantum-computing. But, every engineering decision is a tradeoff between features. On the one hand, IOTA's chosen signature scheme is quantum-resistant, while on the other hand it means that reusing the same wallet address makes it possible for a malicious onlooker to sign a second transaction out of the reused address with relative ease. Accepting funds at an address that has already been spent from is ill advised in this setup. Quantum-tight security comes at the cost of reduced usability.

No other major blockchains have employed such a unique and quantum-proof signature scheme into their software implementations. Instead, they center their signature schemes around more common non-quantum-resistant solutions. One argument made by proponents of these more common signatures is that quantum computing is still many decades away, and that there's no need to worry about shoring up security against a far off threat so soon. Another is that having to destroy an address after just one outgoing transaction is too burdensome to be realistically useful to humans in everyday commerce.

Example: If I want to post my Bitcoin receive address to accept payments for my plumbing service, I give that address to my customers, receive customer incoming payments, and make outgoing transactions to my accountant and suppliers as necessary. All from the same address. With IOTA, I have to give my customers a new address each time I send an outgoing transaction from my collection address. Receive a payment and need to send a payment of my own to a supplier? As soon as I send my supplier's payment, I have to hope that none of my customers still have/pay my old address, and must provide everyone with new addresses.

Traditional blockchains espouse two very powerful arguments in favor of the non-quantum-proof signature schemes, especially if one is predisposed to disregarding an imminent quantum threat. However, as we'll learn, there might be an ultimate compromise. A best of both worlds situation!

Winternitz one-time signature Scheme (w-OTS)

IOTA uses w-OTS, which is hash based using hash functions like the ones we've discussed above. w-OTS signature scheme uses Keccack-384 as its base hash function (go play with that app some more! Keccack is toward the bottom). Using the w-OTS scheme already differs greatly from the other signature schemes used in the DLT space, but IOTA takes it one step further. It modifies its the Keccack-384 base hash function into Kerl, a hash function that converts into trits rather than bits. The Kerl implementation is surprisingly readable, but it's not necessary to go that far into the weeds unless you really want to.

As we touched on above, there are tradeoffs in the decision to use w-OTS. The negatives are listed on IOTA's github:

  1. Statefulness: w-OTS only allows for one secure signing process (no address reuse)
  2. Size: 1300 to 3900 byte signatures are "rather large"
  3. Speed: The underlying Keccack-384 hash function must be executed 702 times (takes time and energy from your device to sign a transaction)

People who fear quantum actually fear quantum's ability to run Shor's algorithm, which would break many signature schemes that are broadly used today. w-OTS is not one of those schemes, and is unbreakable by a quantum Shor's algorithm. So, the positive in this tradeoff is the retained security in an environment with quantum capability.

Here's a great excerpt from the famous 2011 Buchmann et. al. paper On the Security of the Winternitz One-Time Signature Scheme:

In 1994 Shor presented a quantum algorithm that can be used to solve the factorization and discrete logarithm problems in polynomial time, thus completely breaking RSA and ECDSA. Given the importance of digital signatures, the search for alternative signature schemes that resist attacks arising from algorithmic and technological advances is an important research goal. One promising alternative are hash-based signatures. Their sole security requirement is the existence of hash function families with certain properties. Current research suggests, that the security of hash-based signatures will not be significantly harmed by quantum computer supported attacks. Another benefit of hash-based signature schemes is that they are provably secure in the standard model. A hash-based signature scheme or Merkle signature scheme (MSS) consists of the combination of a one-time signature scheme (OTS) to sign the data and Merkle’s tree authentication scheme which reduces the authenticity of many one-time verification keys to the authenticity of a single public key. Examples for one-time signature schemes are the Lamport-Diffie OTS, the Merkle OTS, the Winternitz OTS, the Bleichenbacher-Maurer OTS, the BiBa OTS, and HORS.

We can see that the lingo is strong here yet again, but let's toss in the first two paragraphs of the paper's results section for readers still following along:

Even more great information on w-OTS can be found in the Post-Quantum Cryptography textbook. If you love math, then page 38 is where you should be jumping in. It's interesting to see the very first sentence about w-OTS talk about the large signature size. "Winternitz" is mentioned 18 time throughout the textbook, but there's only about two pages of mathematical notation on the scheme. We can't recommend reading through it since we haven't done so ourselves, but it's certainly there for the taking for the ambitious patron.

Edwards-curve Digital Signature Algorithm (EdDSA)

We're only going to touch on EdDSA here since it's relevant to IOTA. If you'd like to learn more about elliptic curve cryptography, this article by Nick Sullivan comes highly recommended.

EdDSA is codified here, and a senior research and development engineer at Cisco gives an overview as follows:

There are a number of knobs you can tweak: different curves, different hash functions, and all sorts of fun stuff. I will be focusing specifically on an instantiation of EdDSA called Ed25519, which operates over the edwards25519 elliptic curve. Two specific instantiations of EdDSA are provided in the RFC: Ed25519 and Ed448. Ed25519 is what you're most likely to see in practice.

Ed25519 uses SHA-512 and Curve25519, and has the drawback of being theoretically breakable by a quantum computer running Shor's algorithm

Here's an official list of the advantages of EdDSA. The only bullet point that immediately stands out is #4. EdDSA signatures are an order of magnitude smaller in size than w-OTS signatures:

  • High performance across platforms
  • You don't need to use a unique random number for each signature (avoiding the PS3 problem, where a reused random number exposed Sony's signing key)
  • Side channel resistance
  • Small public keys and signatures (32 and 64 bytes respectively for Ed25519)
  • Formulas are valid for all points on the curve, without exceptions
  • Collision resistance

The bullet points notwithstanding, the overall biggest takeaway is that addresses can be reused if signed by the EdDSA scheme.

Hybrid Approach

In an effort to maintain quantum security but also improve user experience, IOTA began moving toward supporting both of these signature schemes at the end of last year.

The iota.cafe forum has been abuzz with chatter about the signature shakeup.

For readers who are interested in learning more, or even collaborating with the team doing this work, please go visit the R&D forum.

The new hybrid solution promises to avoid any changes to the transaction layout while giving users the option of choosing which signature scheme they want to use. The only potential drawback is that EdDSA is less quantum resistant. However, the IOTA github postulates a potential avenue around that too:

...this issue can be partially mitigated when combined with a commitment scheme: The address is chosen as the hash of the public key, which itself is only revealed during the actual signing process. This way, Shor's algorithm can only be applied after the signed bundle has been issued to the network and therefore effectively making this signature scheme immune against this attack when addresses are not reused.

Dan Simerman has repeatedly said that not having an EdDSA option in IOTA has been holding the project back from large scale institutional adoption in North America. Custodians seem to only be comfortable with EdDSA signature schemes, so they've been averse to onboarding a w-OTS-only IOTA platform. Additionally, users have been required to make a new address each time they send an outgoing transaction, burdening everyday human users. It's true that machines won't suffer from this usability quirk as much as humans which is why it's great to go with a hybrid model - humans, custodians, and financial hubs can get a a comfortable user experience-centered signature scheme. Machines can stick with the hardcore quantum-proof signature schemes. It truly is the best of both worlds.

Privacy Policy