How do we secretly create a private key so that anyone can donate to the public address yet needs to go to the moon to sweep it?
Private key protocolMay 28, 2018 at 4:25am (Edited 10 months ago)
Quantum key generation - while this is really cool, I know of no way that quantum mechanics could possibly help ensure the general public that the key really is on the surface of the moon and that no copies exist on earth. In most quantum scenarios, Alice and Bob are both trusted parties trying to keep information confidential from eavesdropper Eve. The only thing this kind of quantum mechanism would help with is ensuring that no entity (aliens?) intercepts the private key as we send it to or from a spacecraft. This kind of security would be pretty unnecessary, though it might make for good marketing. We are in a situation where, in the eyes of the public, we are not a trusted party. There is no mechanism to technically prove beyond any doubt that we aren't lying about whatever quantum key generation mechanism we implement. Efforts should instead be focused on reasonably assuring the public that we don't have a copy of the key.
How to get the public to trust us - it is possible to prove beyond a doubt that the private key is on the moon. Simply have the landed spacecraft broadcast a message signed digital signature generated using the private key. Anyone on earth can then look at the telemetry and decrypt the message with the public key see that the digital signature must have been created with the private key (encryption works both ways) as evidence that the private key exists on the moon. This would require that the lunar lander have access to the private key, meaning it could not be simply etched into a piece of metal. It would have to be stored within the electronics payload of the lander. This is useful because it allows us to generate the private key en-route but then there must be a method to reliably store the key for decades in the harsh environment of space. Even if we do manage this, it would be somewhat difficult to provide solid proof that the key has been recorded in a way that will remain intact for decades to come. More difficult still, would be proving that we don't secretly have a copy of the private key here on earth. Although I'm not sure most of the general public would even think of this possibility, most of the reassurances would be political. If, for example, we launch a dedicated lander to the surface of the moon, we could have a crypto security firm audit the code prior to launch. They would then certify that the private key generation works as we claim and that it's not going to spit out something that we secretly have a backup of here on earth. Add to that, the fact that if the money ever moves without someone going to the moon (this would be a highly publicized event), the blockchain will make everyone immediately aware of it and our reputations would be on the line. This is the most secure way I can possibly think of to ensure people that the private key does not have copies on earth but it requires an expensive lander. It may be better to dramatically simplify it and have people trust us on reputation alone.
Key length - In encryption, there is symmetric encryption, which requires the same private key to encrypt and decrypt. There is also asymmetric encryption, which uses a public key to encrypt and a private key to decrypt. Bitcoin and all cryptocurrencies are built on asymmetric encryption, which is much less secure for a given key length compared to symmetric encryption. Bitcoin private keys are typically 256-bit which is fine for typical use but in the case of a several-decade competition to recover a private key from the moon, 256-bit asymmetric encryption is lacking. Ideally, we want to create a private key that has no chance of being broken in the ensuing decades, especially considering the possible rise of quantum computing. In symmetric encryption, the gold standard is 256-bit symmetric (like AES-256), which is widely believed to be unbreakable by any known means. Susinctly put, "there simply isn't enough time nor energy in the universe" to break AES-256. Implementing it incorrectly could lead to vulnerabilities and this isn't to say that there may exist some unknown method to crack AES-256 but presently, proper AES-256 appears to be secure for the next few decades at least. AES-256, however, is symmetric and we need an asymmetric key. NIST guidelines suggest that 15360-bit RSA keys are of equivalent strength to AES-256. So to ensure security for decades to come, we need a 15360-bit private key, which is 60x the length of a typical Bitcoin private key (around 3000 characters in typical Base58 private key format).
Key protocol - with key length decided, we need to decide what protocol to use to generate the private key. There are four things to keep in mind for this.
1) The algorithm needs to be proven. This is the reason for the phrase "don't roll your own crypto", since all kinds of vulnerabilities can crop up without the algorithm being properly vetted by the global community.
2) It needs to be the case that no backdoor exists. It is speculated that some government-created algorithms may have a backdoor vulnerability built in that allows the government entity that created it (NSA for example) to decrypt messages much easier. Bitcoin and most cryptocurrencies are built on non-government-created algorithms.
3) Post-quantum cryptography needs to be considered. It's worth noting that there are no currently known quantum vulnerabilities for algorithms such as lattice-based cryptography but these algorithms are relatively unproven, making it possible that there are vulnerabilities that would make them susceptible to being cracked much quicker. Bitcoin private keys are somewhat quantum-proof, by virtue of the fact that there is no known quantum method to derive a public key from a public address. There is, however, a method to derive a private key from a public key. This is one of the reasons that sharing a public Bitcoin key is discouraged. Rather, Bitcoin users share a public address (derived from the public key). Once a Bitcoin user spends Bitcoin, the public key is necessarily revealed as part of how the blockchain works, hence why most wallets use a change address. After spending Bitcoin, most wallets will move the remaining balance (the change) to a new private key, which has not yet had it's corresponding public key recorded on the blockchain.
4) The key needs to be relatively short for the purpose of space travel. Even 15360 bits is hardly anything for a modern USB drive but the truth is that most storage mediums are fragile and short lived. There is virtually no digital storage medium that allows for the a few kilobytes to survive the harsh conditions of space, much less possible impact with the lunar surface at several kilometers per second. Therefore, the shorter we can make our key, the better. Ethereum uses elliptic-curve cryptography, which is known for being especially secure for a relatively short private key so it would probably be preferable to Bitcoin, though the best approach would be to use an existing algorithm meant for encrypted communications.
Memory bound function for a shorter key - it is rare to find a method of encryption that cannot be cracked faster by just adding more computational power. Typically, a government computer cluster can crack a code much faster than your average home computer, by several orders of magnitude. A memory hard function narrows the gap between the performance of a highly specialized supercomputer and a run of the mill PC. It does this by taking advantage of the fundamental limits of computer memory. I don't quite understand all the details but what this means is that what may take a government computer 1 minute to crack can also be cracked within an hour by my MacBook. Rather than specialized computers having a 1,000,000,000-fold advantage, they might only have a 60x advantage. That said, when you log into Facebook, it needs to be able to authenticate the password nearly instantly. This is the case with almost all modern cryptography applications. This is not the case, however, with our application.
We could use a memory bound function (also known as a memory hard function) so that attempting to claim the lunar private key requires approximately a week (or any amount of time we want) of computational resources, regardless of how powerful the computer is. That way, attempting to break the encryption with brute force becomes impossible, even if there are only 10,000,000 possible keys. In this example, we could have an extremely short private key (maybe only a few characters) while still taking 100,000 years to brute force (1 week * 10,000,000 possible keys). And if someone has retrieved the private key from the moon, asking them to wait a week to claim the prize is a small price to pay for security. I might be way off base here but this seems like a reasonable way to do it if we need the key to be especially short.
May 28, 2018 at 6:58pm
The priority of making this process trustworthy and understandable to the public is dead-on. I agree that the public should consider us as non-trustworthy, as we're setting an example of how this technology lets us transcend those concerns.
Also your quantum bit made me shiver, but I believe point (3) has an error. A bitcoin wallet reduces it's security after making a transaction, not by simply showing the public address alone. The reason for change addresses is to move the funds out of an address that made a transaction.
From https://bitcoin.stackexchange.com/questions/42320/is-that-safe-to-expose-public-key-to-the-mainnet/42330, when you make a transaction you reveal the public key. Yet without making any spends, you'd never reveal the public key and thus would be much more resistant to even quantum hacks.
Regarding point (4), this is why I'm curious about recruiting trusted members of the blockchain ecosystem and do a large key signing ceremony (shamir secret sharing: https://en.wikipedia.org/wiki/Shamir%27sSecret_Sharing) in order to somehow etch the key pair onto a piece of metal.
Yet this method fails to prove it's on the rocket (you can't sign a message) and likely becomes a moot process if you have to etch the keypair onto metal anyways.
Regarding Memory Bound encryption, that sounds incredibly ideal if it's as you explain. We'd need to get someone a bit more knowledgable about the crypto to be sure.
Waiting a week is no big deal if it guarantees the security of the key.
May 29, 2018 at 3:46am
Yep, I think I made some semantics mistakes in there but we're more or less on the same page. The big takeaway is that sending just a Bitcoin private key would maybe be a waste when sending a more secure/useful non-Bitcoin private key might be better in a lot of ways.
Not sure what you mean about shivering but post-quantum is a bit out of my realm so an error is plenty possible. I'm mostly going off what I've discussed with professors and Reddit. As I understand it, security is reduced after a transaction because 1) public key becomes visible and 2) possibility of the private key being intercepted due to user error during the spending process. How else is security reduced? I think we're pretty much on the same page though.
Professor Jeremiah Blocki at Purdue University would be a great person to have help if we send something that's not just a Bitcoin private key. He's who I talked to before.
The ceremony would be cool and definitely good PR but I don't think I understand it enough to know how that process could apply to etching a physical piece of metal.
As for memory bound functions, take a look at the wikipedia page. Looks like it was originally conceived of to prevent email spam. And I think it could work for us as I've described. The question is mainly how future-proof it is and how much of a balance to strike between key length (security) and time required to wait (convenience).