[TL;DR]

Here’s my idea to protect POW cryptocurrencies from a quantum attack. I’m posting it here in case I have come up with something novel.
TL;DR Protect crypto transactions from quantum attack by using a “key-pair chain” and timelocks to allow fraudulent transactions to be undone.

Suppose Alice creates a random seed, then uses it to create a public/private key pair. Then she takes this public key and uses it as the seed for a new key pair, and then creates another key pair from the latest public key and so on. She ends up with a list of key pairs, and she uses the last pair to create an address in a crypto-currency.

When Alice spends from her address, someone with a quantum computer cracks her exposed public key, and manages to get a fraudulent transaction published to the blockchain before the real one. This is not a problem as Alice’s address is set up with a time lock, giving a time period where generating key pairs can be used to override any transactions. So Alice just needs to create a new transaction and sign it with her penultimate key pair (with a suitably high fee) to get control of her crypto-coins back.

This technique gives Alice protection against a quantum attack. However the attacker could just try again. To get round this, the keys in the key pair chain are not the same. The key at the end is standard encryption strength, the one before is stronger, and the one before that is even stronger. The original key pair can be an implementation of a quantum ‘safe’  signature (e.g. Lamport signatures). So the attacker knows that if they mange to get their fraudulent transaction published, it will just be replaced with a transaction that is much harder to forge, so it is probably not worth trying.

Note that there is an issue with the transaction fee for the forged transaction. If the miner keeps the fee it can be used as a mechanism to siphon off Alice’s funds. If the fee goes to Alice, then people could use the transaction overrides as a cheap way to put data on the blockchain. So there probably needs to be some sort of compromise or fee restriction.

In summary, this technique allows a cryptocurrency to have the security of large signatures, but without increasing the size of data on the blockchain (unless there is an actual attack). The penalty for this security is an increase in the time receivers have to wait for transactions to confirm.

https://github.com/FarCanary/ElectrumSeedTester
I made a tool to check my Electrum cold wallet is creating the correct addresses. I thought I would make it available to everyone. It's based on Ian Colemans awesome BIP39 tool. It works with Bech32 and legacy seeds, it does a proper electrum checksum, and shows the correct addresses based on the type encoded in the seed. Its a git fork of the BIP39 tool so it should be very easy for people to check what I have changed.

Obviously don't type your real seed into a computer connected to the Internet.



The discussion that lead to this tool:
https://bitcointalk.org/index.php?topic=5107752.msg49655945#msg49655945

Having to rely on a single app to get from my seed to my keys makes me a bit nervous. So it would be nice to have an alternative.

Ian Colemans BIP39 page is very good, however it doesn't work for electrum seeds.
https://iancoleman.io/bip39/

However it seems this page can be easily modified so it does work with electrum:
https://bitcointalk.org/index.php?topic=2373020.0

However this doesn't work with Bech32 addresses - the addresses don't match the electrum wallet.

So does anybody now how to get the Bech32 addresses working?

Thanks.

[TL;DR]

I’ve had some thoughts on stopping 51% attacks, so I thought I’d post them on here to see if I have come up with anything novel.
TL;DR Secure POW blockchain by encoding block hashes in transaction signatures.

Passive Proof Of Stake
A Proposal To Increase The Difficulty of 51% Attacks On Proof of Work Blockchains.


Cryptocurrencies like Bitcoin[1] provide a very secure way to send value over the internet. However they can become vulnerable when a single miner controls more than 50% of the hash rate. This is mainly an issue for smaller ‘market cap’ blockchains with less hashing power, especially with the increasing amount of cloud computing available to rent. This paper describes a simple proposal to make these attacks harder, without changing the structure of the blockchain, and only requiring a small amount of extra work in making and validating transactions and blocks.

Possibly the most revolutionary aspect of the Bitcoin protocol is how it deals with two or more competing versions of the blockchain. How do participants in the network all come to the same decision on which is the correct version? Bitcoin’s answer to this is that participants should simply chose the longest chain. This works because creating a long chain requires a lot of computational work (by design), so it is not feasible for an individual to artificially create a long blockchain unless they have more computing power than the rest of the network put together.

In a simple 51% attack, an attacker will publish a transaction to the network, then secretly make an alternative version of the blockchain with a different version of their transaction. When the initial transaction has been confirmed on the public blockchain, the secret blockchain can be released. The nodes in the network will choose the longest of the two competing chains. As the attacker has more mining power than the rest of the network, their blockchain will be longer, and replace the ‘correct’ version. The attacker will have effectively spent their coin twice - a double spend.

However if each transaction contains a hash of a recent block, and is only considered valid if it is put in the blockchain after that block, then the attacker will only be able to put a few of the public transactions into their secret blockchain. It would be easy to tell the difference between the attacking chain and the public chain, as the public chain will have far more transactions. This system can be thought of as being ‘passive proof of stake’, where each person making a transaction is effectively voting on the blockchain they want to support, but these stakeholders play no role in creating the blocks. (The stake holders in a standard proof of stake blockchain play an active role in creating the blocks[2])

Obviously the attacker could make their own transactions to fake the kind of transactions that happen in the public blockchain. To chose the ‘correct’ chain, the network needs a way to analyse the competing chains and give them a score. The chain with the highest score is selected with others being thrown away. For example a simple scoring system would be the number of blocks multiplied by the number of coins affected by transactions in the chain. This means that an attacker would need control of a lot of coins to fake the transactions convincingly, and someone with a lot invested in a network is unlikely to want to attack that network. Much more complex scoring functions could be made, based on statistical analysis of the chains. However this is probably application dependent, and outside the scope of this document.

The implementation described above would be more secure than a standard proof of work blockchain. However if a 51% attack was successful then potentially thousands of transactions would become invalid, and it would not be possible to re-add them to the blockchain. The blocks they referenced would no longer exist. Consequently, referencing a previous block should be optional, and transactions that do reference a previous block should contain two signatures. One with and one without the reference. Then if the worst happens the signature without the reference can be used. The scoring function for choosing a branch should ignore transactions that don’t have a block reference, as an attacker could easily copy them.

Adding an extra hash to every transaction would cause a significant increase in blockchain data. Fortunately this data can be completely stripped out of the transaction before it is added to the blockchain as it can be recreated using the blockchain and the transaction signature. This involves guessing which of the recent blocks a transaction was linked with until one is found that passes the signature test. This guessing process can be greatly optimised by sorting the transactions based on which block they have referenced (e.g. Most transactions will use the same block as the previous one, so will be easy to guess). The number of signature tests required to validate a block will be N+M compared to N for a standard cryptocurrency (where N is the number of transactions, and M is the maximum allowable age of a referenced block in blocks). As M can be chosen to be much less than N, the number of signature tests should only increase by a few percent.

If it is known that a blockchain is in danger of being attacked, large stakeholders can choose to secure the network by moving their funds, giving the public chain a higher score. This would be a good option for exchanges as they are the most likely targets of double spends, and they tend to have large amounts of cryptocurrency. It may be desirable to reward large transactions like this in order to encourage them. For example each block could award a fraction of the mining reward to the highest value transaction of funds that have been untouched for a set time. This could be limited to transactions with a single output to avoid confusion on where the reward should go. Miners that try to exclude high value transactions to get the reward for themselves run the risk of their block being rejected in favour of one with a higher score. Miners will have an advantage as they will be able to see the other transactions in the block before they decide whether to add theirs, or not. However this should not harm the network, and can be considered a perk of being a miner.

Some additional points:

• It should be possible to implement Passive Proof of Stake using soft forks.
• As Passive Proof of Stake increases the security of the blockchain, less proof of work is needed, potentially allowing lower mining rewards and lower energy usage.
• In an extreme implementation the blockchain would be secured entirely by proof of stake, with proof of work just used to control the rate that new blocks are created.
• When making a transaction, the age of the block referenced can be chosen. Using an older block will ensure the signature is not tied to a discarded branch. A newer block will secure the blockchain better.
• If two competing blocks are created roughly simultaneously, the score function can be used to decide which one should be selected.
• Miners have an incentive to include transactions with block references as it makes their branch stronger.
• Transactions with block references are more likely to be accepted onto the blockchain, so users have an incentive to use them.
• A more sophisticated scoring system would be to score each transaction based on its value, how long since the inputs were last used, and how recent the block that it references is. The score for a block is then the sum of its transaction scores, plus an amount for the block, and a chain’s score is the sum of its block scores.
• Block hashes encoded in transaction signatures can be used for replay protection.
• A potential downside is that this proposal makes it easier for someone with a very large amount of cryptocurrency to launch a 51% attack. However it would be against the interests of a large stake holder to attack the thing that they have a stake in.
• A ‘light’ wallet provider may be able to trick people into supporting a secret blockchain. However interested parties can monitor popular wallets and take appropriate action if they detect a problem.

References
[1] Nakamoto, Satoshi (31 October 2008). "Bitcoin: A Peer-to-Peer Electronic Cash System"
[2] https://en.wikipedia.org/wiki/Proof-of-stake