The Most Significant Future Risk Around Blockchain: ECDSA

The security world has fallen head over heals for Elliptic Curve Cryptography (ECC) methods, and ECDSA (Elliptic Curve Digital Signature…

The Most Significant Future Risk Around Blockchain: ECDSA … and Meet IOTA

The security world has fallen head over heals for Elliptic Curve Cryptography (ECC) methods, and ECDSA (Elliptic Curve Digital Signature Algorithm) is becoming the standard in creating keys and to sign for transactions. For exchange key it is ECDH (Elliptic Curve Diffie Hellman) that often creates our secure connections.

But quantum computers have both ECC and RSA is their sights. But what’s at risk? Well a core risk is around keys used in ECDSA and the signatures added to the blockchain, including within Ethereum and Bitcoin. With this they use the ECDSA method to create the keys for the wallet and to sign for transactions.

With ECDSA, we create a random 256-bit private key, and then can easily derive our public key. It is then extremely difficult to find the random value which generated the given public key:

The private key is used to sign for transactions, and the public key proves that a given private key has been used. But with Shor’s algorithm we are able to reverse back the private key for any public address, and thus take over control of a person’s wallet.

As an alternative we can use hash-based signature, and which are used by IOTA. They are simpler from ECDSA, but are also quantum robust. For IOTA the method used is the Winternitz one time signature scheme (W-OTS). As it is only used once, we should not sign for a transaction with the same details (and this could be easily spoofed).

Winternitz one time signature scheme (W-OTS)

W-OTS uses relatively small key and signatures sizes, and is thought to be quantum robust. It generates 32×256 bit random private keys. We then have these a number of times, and is defined by a parameter (w). If we use w=8, we hash the private keys by (2w). This creates 32×256 bits public keys. The signature is the created by taking eight bits at a time, and then the 8-bit binary int (n) is subtracted from 256 and the private key is the hashed 256-n times. The signature is then 32 hashes which are derived from random private keys. To verify the signature, the recipient parses the hash of the signature (using 8 bits at a time, and extracting the 8 bit int, n). The signature is then derived from the signature.

The method is:

  • Initially we create 32 256-bit random numbers. These 32 values will be our private key.
  • We then hash each of these values 256 times. These 32 values will be our public key.
  • We now take the message and hash it using SHA-256. This produces 32 8-bit values (N1, N2 … N32).
  • For the signature we take each 8-bit value in the hash of the message, and then hash 256-N times (where N is the value of the 8-bit value).
  • To prove the signature, we take the message and hash it with SHA-256, and then take each 8-bit value. We then hash the 8-bit signature value by the number of times defined by the message hash value (N1, N2..). The result for each operation should equal the public key value.

This is illustrated below:

A sample run which just shows the first few private key and the first public keys:

Hashing number:	256
==== Private key (keep secret) =====
Priv[0]:  bd344c6110628aa38c9b5ca6458bed7b78425b2e82efa0624a578031562f82ee
Priv[1]:  20670af5b1663fa9fad49fab6a692ae5989cff77439f98d2288f173b17a8d99f
Priv[2]:  625aa290fd1f88c930451ff743d5d9ef90e7064368fb23a18c9fd048474818f2
Priv[3]:  ee0e1363cbd5f61017ba27bfe91ec53969d28d143ed59a99efb020941bc4990f
Priv[4]:  ce94d7282ee3f7b05b99768695ff224b5994900c6182dfb89d596d8b7b405ec6
Priv[5]:  d0c59651e951b0bb8d5a2d7b93f6739c9ce4a0c0c0f63bfce23b331b947eb285
==== Public key (show everyone)=====
Pub[0]:  45fdac6339e80cadd1331cce026cd0364ea84146a36f6f3f2449b66fb55a217a
Pub[1]:  184cf92f22072fef078fa4a93ec2044f07ac8b12e326509474209312cace8a5a
Pub[2]:  a47548d4537bd284e7d7f935f41570866d9c6a72c463bb2a2b10c8c7907621f0
Pub[3]:  60395e575522cacb70d866211c64e8a74e562c79d1fffce224d1013d088bf66f
Pub[4]:  8be7b53d5b56e698b8798f2a707fba7b8e417554fd489d74cc40fe8574d7589e
Pub[5]:  9fac35971dae3a5c77ae7b5c720a72f90ee53852668c96c78e095cbb52af20a1
==== Message to sign ===============
Message:	The quick brown fox jumps over the lazy dog
SHA-256:	d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
==== Signature =====================
Sign[0]:	45cb53c5c33af9b20426fd0233fd63d92bf0c2ded367163e6f2f93588a33c6d8
Sign[1]:	e8c35987101f2d11d7056a2fe78069d3ed73aee315ebef8c2d40e04973301c26
Sign[2]:	59220d80b7c958957b28511f4081341cc4a00a0d6d5e1d05351be7dec3ca8aaa
Sign[3]:	72a906d719be18e1592314bf6f6c521a325a9de2b5b9e9e13117bf01b0157f5c
The signature test is  True

A demonstration of the method is given here.

Getting Ready to Tangle

Amir Hagafny [here] defines that there has actually been three generations of cryptocurrency:

  • 1st Generation. These cryptocurrencies, such as Bitcoin, Litecoin, Monero and Bitcoin Cash, basically just store and transfer value, but have suffered from poor scaling and a weak architecture. The overheads involve relatively high transaction fees and transaction times.
  • 2nd Generation. These cryptocurrencies, such as Ether, Neo, and Lisk, have platforms that support decentralised applications (dApps). This generation adds coding and smart contracts, and supports logical operations. A high-level code is then translated into byte code for the Blockchain.
  • 3rd Generation. These cryptocurrencies aim to create properly distributed systems, and many use DAG (Direct Acyclic Graph). A traditional Blockchain just sequentially stores transactions and which can take some time to create a consensus through the building of blocks. With DAG, each of the transactions becomes a block, and it thus speeds up the consensus mechanisms.

Many of new cryptocurrencies differ greatly from Bitcoin. Ripple, for example, is not like Bitcoin, and is used for the fast consensus on money transfers, and which can achieve rates of clearing that approach Visa and Paypal. Another interesting one is IOTA, and it has IoT devices in its sight:

IOTA and DAG

IOTA uses a method called Tangle to create a scaleable infrastructure for transactions. It is likely that the crash is due to the database for Tangle being too large for some hosts, and that they have crashed. The IOTA team are thus busy updating their system to cope with the limits, and also to support more limited devices in the future.

IOTA aims to provide a new foundation for IoT devices and M2M (Machine-to-machine) communications, and overcome many of the existing problems of blockchain. Overall it is described as the:

“Economy of the Future”

and it adds a new innovation of blockless ‘Tangle’, and which has no transactions fees and no limits on scaling. The network transaction speed then grows with new activity, and where it is built around transactions and not miners, and thus does not centralise its activities. As there are no miners, there are no conflicts of interest. As there are no fees, it can also support nano payments (extremely small transactions of crypto currency).

A bit of a tangle

The Tangle uses a DAG (Directed Acyclic Graph) for its infrastructure rather than a blockchain to store its ledger. Blockchain methods have rate limits as nodes must agree to the whole chain (and where forks and branches are discarded), The Tangle supports new branches to be created, and which will eventually merge back again. This supports a faster overall throughput, and for consensus to be built through nodes submitting their transactions, and also checking the validity of recent ones.

In his ground-breaking paper [academic paper], Sergio Demian Lerner outlined that in a DAG there were no fixed blocks, and that each transaction brings with it, its own proof of work. Within this he defined the usage of a fast cache for the most recent transactions, and where older transactions cannot be used as a reference.

Within Tangle a DAG is created and where vertices represent transactions, and edges represent approvals. The first transaction is defined as the genesis, and all the IOTA tokens are created from this. On a new transaction from a node, a new vertex is added to the DAG, along with two previous transactions which it is approving. The approval process means that the node has verified the history of the transactions and that they seem to be valid. This check is normally related to the balance on the accounts, so that there are no double-spends and there are are no bogus transactions. If a transaction is approved by large number of nodes, it is part of the consensus, and then cannot be altered. The amount of work required to create the consensus for a transactions is large, and would require the spamming of the network.

In the example in the paper, Sergio defines the DAG before a join transaction arrives and afterward (see diagram below). The system allows for two conflicting transactions to be included in the DAG-chain, as long as the second does not references the first (see figure below, with transactions 2 and 3). Each transaction then has a confirmation score. As more transactions are added onto one transaction or the other, the confirmation score will increase (a). A transaction will no children will have a score of zero. If a transaction appears twice, the one with the highest score will win. In (d) a new transaction has arrived and which conflicts with transactions 2 and 3.

Still work in progress

IOTA is still under development, and the nodes going off-line are just part of its growing pain. Unfortunately is not quite a proper DAG as it still requires proof-of-work. ByteBall is more closer aligned to DAG [here]. A major selling point for Byteball is that it supports conditional payments, where if a condition is not met by the other party, you will get your money back.

So could DAG solve the current issues with blockchain? Well blockchains needs to overcome the usage of hard forks. It is also under risk from influential miners. And finally … it is a tortoise compared with the hare that is the current payments network.

With Bitcoin consuming the energy of Ireland just to create its consensus mechanism, we need to find new ways of creating our ledger.

Conclusions

IOTA is evolving and building new types of systems. It doesn’t come with the flaws of Bitcoin or Ethereum, and creates a faster consensus and does not require miners to consume vast amounts of energy.

But here’s a sales pitch:

  • IOTA is truly distributed.
  • IOTA has no transaction fees.
  • IOTA has no scaling issues.
  • IOTA has no network scaling problems.
  • IOTA has no miners (and uses transactors rather than miners).
  • IOTA is quantum robust.