Hey guys! Work continues on conference-related stuff, but we developers are also brewing a few other elixirs of interest.
One of the ideas thrown around the virtual, coffee-stained conference table recently was the use of
quantum-computer-resistant signature algorithms. Without going too deep into concepts tangentially related the matter at hand, hashing functions, due in part to the 'loss' of data that occurs during the function (Imagine a simple example of a 'secret' being the two numbers 12 and 20. A *very* simple, collision-prone, insecure method of verifying those numbers at a later point in time without storing the actual numbers would be to store some mathematical, repeatable function of the two, something such as multiplication. If a person were able to acquire the hash '240' and try to find the original inputs, they would get a ton of matching input pairs: (1, 240), (2, 120), (3, 80), ... (15, 16). This availability of collisions makes the actual function 'lossy'. Such an example is clearly an exploitable system, and is only for visualization purposes. The complex reduction, data loss, and mixing occur primarily through logical (AND, OR, XOR) operations, rolling reels of numbers effecting each other, sponge functions, etc., and make reversing an output back to an input 'impossible'.) are assumed to map inputs to realistically-unique outputs of a (usually) fixed length. As such, they are not prone to math-based attacks from quantum computing algorithms against classical computational encryption algorithms (RSA,
ECDSA...).
What's so important about cryptographic signatures? For the purposes of a terribly inaccurate analogy, imagine your cryptocurrency wallets as a checkbook. You can write an amount, a destination, and a dollar value, but without your signature, the filled-out check has absolutely no ability to actually transfer currency. However, once you put your signature (which is, historically, important since they are *relatively* hard to imitate as well as hard for the signer to deny signing the check) on the check, it can be used to transfer funds. If you wrote a check for $10 to your friend but never submitted it to the bank (blockchain), the money never gets transferred. However, once the check gets cashed by your friend, the funds get transferred from your account to your friend's, and if you later deny signing the check, someone can simply show your signature. Either your signature was compromised, or you signed the document. This is known as a promise of non-repudiation. Signatures on the blockchain work to ensure that anyone can see the balance of an address (to verify you have the money you are trying to spend), but you can only spend money from an address you have control over. Asymmetrical cryptography allows for signatures to be privately generated but publicly verified.
Bitcoin addresses are formed in the following manner:
address = Base58(versionByte + RIPEMD-160(SHA-256(publickey)) + SHA-256(SHA2-56(RIPEMD-160(SHA-256(publickey)))).substring(0, 4)) where ‘+’ represents a concatenation operator. Fun, right? If you prefer a visual simplification:
As such, simply accepting coins at an address does not reveal your public OR private key to the network. As such, the Bitcoin network is unable to differentiate between a valid and an invalid address--the only possible sanity check is a built-in checksum as shown above (the second, partial SHA256D hash appended to the end) which helps to eliminate mistypes. However, due to the nature of hashing functions being assumed to be one-way, the only way we can prove we own such a certain address, when we decide we want to spend the coins, is to publicly reveal the public key. In the absence of an efficient way to factor large numbers (either by an *extremely* unlikely breakthrough in mathematics, or more likely through the practical implementation of Shor's algorithm (or in the case of ECDSA, a modified derivative) or another quantum-computer-algorithm), ECDSA and RSA are extremely secure. However, when very large numbers can be efficiently factored, there are serious concerns about the safety of classic computational cryptography as it exists today. The only way the Bitcoin network would be safe in the event of a quantum computer capable of factoring large numbers would be to switch to a one-time-use address system. Today, one Bitcoin address can send and receive as many transactions as desired with safety. However, due to the nature of address generation above, after the address signs one transaction, the public key is revealed, in order to prove ownership of the address. Until a valid transaction originates from an address, the public key behind the address is safely masked by one-way cryptography (hashing functions). However, upon signing a transaction and broadcasting the public key, quantum computer attacks on that address become possible.
In a post-quantum-computing environment, as soon as an address signs a transaction, and remaining coins on the address are put at risk. As such, the various methods by which Bitcoin addresses are used multiple times today (tip jars, many payment processing services, etc.) would have to transition to a system of one-time address use, which not only decreases the compressibility of the blockchain, but also acts to make the currency harder to use. Imagine having to give your workplace a new bank account to deposit for every payday...
ECDSA has several properties that make it desirable for use in efficient cryptocurrencies: small signature size, fast verification, and small public key size. Additionally, the computational power required for key generation is trivial.
Any alternative to ECDSA aimed at being quantum-computing-resistant must, to avoid blockchain bloat and computational bloat, have relatively small signatures, public keys, and be easy to verify, allowing for network growth. Under the validated assumption that cryptographic one-way algorithms such as the popular SHA-family of hashing functions are secure against quantum-computers based on their reliance on lost data rather than on mathematically-hard problems, signatures built on top of hashing algorithms inherit similar properties. One simple example of such a signature method is the Lamport Signature, which is a one-time signature.
To summarize Lamport (when used with SHA256, and where 'User' refers to a computer generating and using an address):
-> User generates 256 random inputs (preferably somewhat long, and a mix of numbers, letters, symbols, and even non-printable characters if desired)
-> User divides these 256 inputs into 128 pairs of two inputs
-> User hashes each input and stores the hash output
-> User publishes all 256 outputs to the network (for our purposes, consider this group of 256 outputs to be the public key and address!)
-> User signs away coins the network recorded as belonging to the published public key/address by:
--->User writes and hashes a transaction message (simplification: "I sign all 8.3 coins from transaction (TxID) to address (address)")
--->User lays out the SHA256 hash in binary
--->User submitts the corresponding private keys (For example, if they were signing the four bits "0110", they would submit the first (position: zero) private key from the first group, the second (position: one) from the second group, the second (position: one) from the third group, and finally the first (position: zero) from the fourth group) to the network. The network can then hash the private keys and see that they match the public keys, and can also verify that the user signed that particular message by hashing the message, and seeing that only the private keys corresponding to the binary representation of the hash of the message are published, while the others (the 2nd in the 1st set, the 1st in the 2nd set, the 1st in the 3rd set, and the 2nd in the 4th set) are not made public. If the address owner were to sign another message, he or she would have to reveal other parts of their private key, which compromises the security by allowing full sets (rather than one of two hashes in a set) to be published, allowing an attacking party to possibly forge messages. As such, Lamport signatures are one-way, one-use.
Lamport signatures have two
obvious shortcommings: huge public key sizes, and one-time use.
However, the basic logic lamport signatures are based on can be extended in such a way that a Lamport-esque signature scheme can be reduced to a *very* small public key (in some capacity smaller than ECDSA) as well as having reasonable signature sizes (larger than ECDSA, but not large enough to be impractical for blockchain usage). Such implementations use merkle trees to make signatures able to sign huge amounts of transactions (think 2^20 to 2^40, far beyond practical application, and thus not limiting the effectiveness of an address generation/transaction signing algorithm pair) while only adding much size to the blockchain when actually creating a transaction, and when creating a transaction adding what iss still a manageable amount of data. Such a system would allow the network to be resistant to quantum computing attacks against every implemented cryptographic method, and would make addresses reusable, while not drastically increasing the footprint of the blockchain. Optimized versions of such a signing algorithm (such as CMSS and GMSS) offer all of the above properties, and, given an efficient, cryptographically-sane, time-tested hashing algorithm, are extremely secure. GMSS, currently, is mildly impractical due to the time taken to generate private keys, and thus CMSS is the valid, considered option of the pair.
The hashing algorithm can be comprised of several chained hashing algorithms, so that if some of the hashing algorithms were ever cracked, or at the least attacked with some form of reduction function, the network would still be secure, as there would still stand unbreakable links in the signing algorithm due to the unbroken hashing algorithms. For a simplification, imagine I have the ability to perform four processes on a string. I do all four in order, twice, such that I take the output of process one, put it into process two, take that output, into process three, from three to four, then from four to one to two to three back to four, so they are stacked and none end the chain without also appearing elsewhere in the chain. A mild acquaintance of mine knows how to reverse processes four and two, but is unable to undo processes three and one. Given the output, he is able to reverse it from 8 stages to seven stages of length (or how the string of text I had appeared once it went 1->2->3->4->1->2->3 when it was about to enter process four again). From here, he would have to reverse process three in order to continue on. Since he is unable to do so, he is unable to reverse the entire function, despite having a fully functional attack against one of the components. Likewise, if several hashing algorithms are chained together (such as is done in X11/X13/X14/X15/X
), multiple algorithms can be broken without causing insecurities in the currency.
While the isn't the guaranteed be-all-end-all solution to the quantum computing problem, lamport-based signature schemes and other similar schemes based only on the cryptographic integrity intrinsically provided by hashing functions is a promising next step in future-proofing cryptocurrency networks. Such a system also opens the interesting possibility of a tradeoff between computational power to generate a private key, and the security/size of the keypair, though the security offered by a default-parameter implementation of aforementioned algorithms would provide more than sufficient security. 
