Quantum Computer Proofing for ECDSA Transactions ------------------------------------------------ An issue that threatens the very use of ECDSA is that future Quantum Computers might be able to determine the private key for any published public key (in very little time at all). This would mean that any standard sort of transaction that includes a public key and a digital signature could be in danger of being replaced by one or more alternative txs that are created as soon as an attacker has seen a tx (but presumably prior to the tx being confirmed which is known as a "double spend attack"). As QC is not known to provide any significant benefit to "reversing a secure hash" (such as SHA256) then this can provide a potential method of preventing such QC "double spend attacks". The approach described with this document requires the publishing of the final hash in a "hash chain" before any QC powerful enough to be able to determine a private key from a public key exists (so would need to be implemented sooner rather than later to be an effective solution if the approach described in this document were to be adopted). It should also be noted that once funds have been locked with a hash chain then they can be securely transfered to another such hash chain without being concerned about QC attacks (even if they can crack private keys in the future). Assuming we trust that no QC can currently determine a private key from a public key then we can now create a tx that includes the relevant public key and an ECDSA signature with the tx content being the final hash from a hash chain of a certain length (10 being used for the purpose of this document). This tx does not spend the funds at all but effectively marks them as being locked by the hash chain. For the first hash in the chain it would be recommended to hash a securely generated random value. The following is a sample hash chain of length ten: 7f42fac9c9ffa658d50f3ef52de8443779f58473f8dff0f7a8e3ae9eff209e77 (first hash) 1d8197f27bbb39dc9f75e7ddf42f061c7a06def30e4d63acbd01a1c0d79b6949 d0eb5995bcabf2d403e0a8013a0c2f968bfdb6d336ad50b56f103debfedc2705 83c1b5999f542d154ef14c0e5164eb32849da6002548c959ab073291c17ec75c ce2d14c6ddb3064f9353eeb09d23dd0a21d78ee7a58c182e7531bcba34e5dbb4 2d65506ff759625987a715f472f2d7178470b18f43b76bb4732dd79c903a9ba7 0358c490d322c17181bee054457639552608706bbc7e05be6d78aee6aa357990 e397422a62cb8d7a9f87c3c9d7b03ea477f47f688d6718d225ff729c79965384 2a0fffc1dd588fefce424864f765ba645060d39e04d4775c0361604e6aefb42c 430b326b28b50e6bae02b0517c46574c457477303e6f96e9d1d09d291f548fa3 (final hash) The secret reveal approach used in things like HTLC smart contracts operates in a similar manner but does not have multiple distinct stages (whereas this approach has four) each of which is a separate transaction (apart from Stage 1 which can actually be included in Stage 4). It should be understood that standard HTLC contracts would not be secure from the QC double spend attack described previously. The four steps for this approach are as follows: Stage 1: Lock Funds with a Hash Chain (either done before QC can crack private keys or as part of Stage 4) Stage 2: Commitment To Transfer (XOR combination of first hash and transfer content plus second last hash) Stage 3: Prepare To Transfer (the reveal of the third last hash flags that the last tx has been confirmed) Stage 4: Transfer Ownersip (provides the transfer content and the first hash in the chain for verification) The following is an outline of what a stage 1 tx would look like: 430b326b28b50e6bae02b0517c46574c457477303e6f96e9d1d09d291f548fa3 (final hash) For the stage 2 tx we will need to have the actual ownership transfer information (which for Bitcoin would be the transaction output information and could include the final hash of another hash chain to ensure the funds are kept safe from QC attacks). For the sake of simplicity we will assume that this information is simply the word "hello". The SHA256 digest of this is "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824" and if we then also use the very first hash from the hash chain we had initially generated and perform just a simple XOR between every hex digit you get "53b0b773964f0556f3e705dfe851a6a962e39a2fe778b2a9dbe79dfc6cab0653" which can be published in our commitment tx. It should be noted that this value has no meaning on its own and carries very little information for analysis (the zero values will identify digits that are identical in both hashes but even that would not be of any real help to either break the hash chain or determine the content). 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824 hello 7f42fac9c9ffa658d50f3ef52de8443779f58473f8dff0f7a8e3ae9eff209e77 (first hash) 53b0b773964f0556f3e705dfe851a6a962e39a2fe778b2a9dbe79dfc6cab0653 XORed values We would combine this XOR hash with the second last hash in the hash chain as a simple proof that will not be able to be published prior to this tx being broadcast (although other nonsense commitment txs could still end up being created by QC attackers and inserted into blocks even before the "real" commitment tx is confirmed). The stage 2 tx will thus look something like the following: 53b0b773964f0556f3e705dfe851a6a962e39a2fe778b2a9dbe79dfc6cab0653 XORed values 2a0fffc1dd588fefce424864f765ba645060d39e04d4775c0361604e6aefb42c (ninth hash) Once this transaction has been confirmed then it must be followed by a prepare to transfer tx (which provides the eighth hash in the hash chain as proof). The stage 3 tx will thus look something like the following: e397422a62cb8d7a9f87c3c9d7b03ea477f47f688d6718d225ff729c79965384 (eighth hash) The purpose of the stage three transaction is to restrict/limit which commitment txs to test against in order to determine whether an "ownership transfer" tx is valid (otherwise it might still be possible for bad actors to insert a double spend commitment tx along with its rogue ownership transfer tx). By having these two steps before the hash chain is revealed the hash chain owner can be sure (up to how many confirmations they wish to wait for) that any small re-org will not affect the ownership transfer. Finally once the stage 3 transaction has been confirmed the stage 4 tx can be broadcast which simply contains the first hash in the hash chain together with the actual release of ownership information (which this sample uses the value "hello" to represent). The stage 4 tx will thus look something like the following: hello 7f42fac9c9ffa658d50f3ef52de8443779f58473f8dff0f7a8e3ae9eff209e77 (first hash) By hashing the content ("hello" for this case) and XORing it with the first hash in the hash chain we will be able to find a matching commitment tx that had occurred in a block prior to the stage 3 tx (with the first of any matching matching commitment tx being considered proof that the ownership transfer is valid). As the first hash cannot have been known prior to its publication and this publication will only happen after the stage 3 transaction locked any stage 2 transactions that had been published it would simply be impossible that a valid rogue stage 2 transaction will be found in the blockchain prior to the stage 3 transaction (even though invalid ones could appear assuming a QC attacker had cracked the private key and published them). This approach does assume that a "deep re-org" will not occur and its security therefore is dependant upon exactly how many confirmations could occur between the 3rd and 4th stage txs. Copyright (c) 2018 CIYAM Developers. Usage of this information is granted and acknowledgement is appreciated.