public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [bitcoin-dev] Transition to post-quantum
@ 2018-02-12 14:13 Tristan Hoy
  2018-02-12 15:50 ` Tim Ruffing
  0 siblings, 1 reply; 12+ messages in thread
From: Tristan Hoy @ 2018-02-12 14:13 UTC (permalink / raw)
  To: bitcoin-dev

[-- Attachment #1: Type: text/plain, Size: 1068 bytes --]

Hi all,

Recently I've been exploring what a post-quantum attack on Bitcoin would
actually look like, and what options exist for mitigating it.

I've put up a draft of my research here:
https://medium.com/@tristanhoy/11271f430c41

In summary:
1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are scalable
2) This is a rapidly advancing space and committment to a specific
post-quantum DSA now would be premature
3) I've identified a strategy (solution 3 in the draft) that mitigates
against the worst case scenario (unexpectedly early attack on ECDSA)
without requiring any changes to the Bitcoin protocol or total committment
to a specific post-quantum DSA that will likely be superseded in the next
3-5 years
4) This strategy also serves as a secure means of transferring balances
into a post-quantum DSA address space, even in the event that ECDSA is
fully compromised and the transition is reactionary

The proposal is a change to key generation only and will be implemented by
wallet providers.

Feedback would be most appreciated.

Regards,

Tristan

[-- Attachment #2: Type: text/html, Size: 1791 bytes --]

^ permalink raw reply	[flat|nested] 12+ messages in thread

• * Re: [bitcoin-dev] Transition to post-quantum
    2018-02-12 14:13 [bitcoin-dev] Transition to post-quantum Tristan Hoy
  @ 2018-02-12 15:50 ` Tim Ruffing
    2018-02-12 21:32   ` Tristan Hoy
    0 siblings, 1 reply; 12+ messages in thread
  From: Tim Ruffing @ 2018-02-12 15:50 UTC (permalink / raw)
    To: bitcoin-dev
  
  Hi Tristan,
  
  Regarding the "Post-Quantum Address Recovery" part (I haven't read the
  other parts), you may be interested in my message to the list from last
  month and the rest of the thread:
  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015659.html
  
  This is an approach which aims to avoid the issues that you've
  mentioned in your blog post.
  
  Best,
  Tim
  
  On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
  > Hi all,
  > 
  > Recently I've been exploring what a post-quantum attack on Bitcoin
  > would actually look like, and what options exist for mitigating it.
  > 
  > I've put up a draft of my research here: https://medium.com/@tristanh
  > oy/11271f430c41 
  > 
  > In summary:
  > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
  > scalable
  > 2) This is a rapidly advancing space and committment to a specific
  > post-quantum DSA now would be premature
  > 3) I've identified a strategy (solution 3 in the draft) that
  > mitigates against the worst case scenario (unexpectedly early attack
  > on ECDSA) without requiring any changes to the Bitcoin protocol or
  > total committment to a specific post-quantum DSA that will likely be
  > superseded in the next 3-5 years
  > 4) This strategy also serves as a secure means of transferring
  > balances into a post-quantum DSA address space, even in the event
  > that ECDSA is fully compromised and the transition is reactionary
  > 
  > The proposal is a change to key generation only and will be
  > implemented by wallet providers.
  > 
  > Feedback would be most appreciated.
  > 
  > Regards,
  > 
  > Tristan
  > _______________________________________________
  > bitcoin-dev mailing list
  > bitcoin-dev@lists•linuxfoundation.org
  > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
  
  
  ^ permalink raw reply	[flat|nested] 12+ messages in thread

• • * Re: [bitcoin-dev] Transition to post-quantum
      2018-02-12 15:50 ` Tim Ruffing
    @ 2018-02-12 21:32   ` Tristan Hoy
      2018-02-13  6:46     ` Tim Ruffing
      0 siblings, 1 reply; 12+ messages in thread
    From: Tristan Hoy @ 2018-02-12 21:32 UTC (permalink / raw)
      To: Tim Ruffing, Bitcoin Protocol Discussion
    
    [-- Attachment #1: Type: text/plain, Size: 3065 bytes --]
    
    Hi Tim,
    
    Just read through your post, thanks for the heads up - I only just joined
    this mailing list.
    
    In a post-quantum world, your second "d" type transaction is completely
    forgeable, which means it is vulnerable to front-running. An adversary
    capable of breaking ECDSA needs only listen for these transactions, obtain
    "classic_sk" and then use a higher fee (or relationship with a miner) to
    effectively turn your original "d" transaction into a double-spend, with
    the forged transaction sending all your funds to the adversary.
    
    I'm pretty confident that a PQ DSA is required to prevent front-running,
    and that no "commit-reveal" scheme will be secure without one.
    
    The other issue with your approach is that if it is rolled out today, it
    will effectively double transaction volumes - this is what I tried to solve
    in solutions 2 and 3 in my article by instead modifying the address
    generation process.
    
    Regards,
    
    Tristan
    
    On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <
    bitcoin-dev@lists•linuxfoundation.org> wrote:
    
    > Hi Tristan,
    >
    > Regarding the "Post-Quantum Address Recovery" part (I haven't read the
    > other parts), you may be interested in my message to the list from last
    > month and the rest of the thread:
    > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/
    > 2018-January/015659.html
    >
    > This is an approach which aims to avoid the issues that you've
    > mentioned in your blog post.
    >
    > Best,
    > Tim
    >
    > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev wrote:
    > > Hi all,
    > >
    > > Recently I've been exploring what a post-quantum attack on Bitcoin
    > > would actually look like, and what options exist for mitigating it.
    > >
    > > I've put up a draft of my research here: https://medium.com/@tristanh
    > > oy/11271f430c41
    > >
    > > In summary:
    > > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
    > > scalable
    > > 2) This is a rapidly advancing space and committment to a specific
    > > post-quantum DSA now would be premature
    > > 3) I've identified a strategy (solution 3 in the draft) that
    > > mitigates against the worst case scenario (unexpectedly early attack
    > > on ECDSA) without requiring any changes to the Bitcoin protocol or
    > > total committment to a specific post-quantum DSA that will likely be
    > > superseded in the next 3-5 years
    > > 4) This strategy also serves as a secure means of transferring
    > > balances into a post-quantum DSA address space, even in the event
    > > that ECDSA is fully compromised and the transition is reactionary
    > >
    > > The proposal is a change to key generation only and will be
    > > implemented by wallet providers.
    > >
    > > Feedback would be most appreciated.
    > >
    > > Regards,
    > >
    > > Tristan
    > > _______________________________________________
    > > bitcoin-dev mailing list
    > > bitcoin-dev@lists•linuxfoundation.org
    > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
    > _______________________________________________
    > bitcoin-dev mailing list
    > bitcoin-dev@lists•linuxfoundation.org
    > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
    >
    
    [-- Attachment #2: Type: text/html, Size: 4487 bytes --]
    
    ^ permalink raw reply	[flat|nested] 12+ messages in thread

  • • * Re: [bitcoin-dev] Transition to post-quantum
        2018-02-12 21:32   ` Tristan Hoy
      @ 2018-02-13  6:46     ` Tim Ruffing
        2018-02-13 10:06       ` Tristan Hoy
        0 siblings, 1 reply; 12+ messages in thread
      From: Tim Ruffing @ 2018-02-13  6:46 UTC (permalink / raw)
        To: Bitcoin Protocol Discussion
      
      On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
      > In a post-quantum world, your second "d" type transaction is
      > completely forgeable, which means it is vulnerable to front-running.
      > An adversary capable of breaking ECDSA needs only listen for these
      > transactions, obtain "classic_sk" and then use a higher fee (or
      > relationship with a miner) to effectively turn your original "d"
      > transaction into a double-spend, with the forged transaction sending
      > all your funds to the adversary.
      
      That's not true. The d(ecommit) transaction, or better let's call it
      "decommit step" of a two-step transaction does not specify the effects
      (output script). This is what I denote by "tx" in the writeup, and it's
      already fixed by the c(ommit) step.
      
      So yes, if the user finally reveals
        d  = classic_pk||Sign(classic_sk, tx)
      a quantum attacker can indeed forge
        d' = classic_pk||Sign(classic_sk, tx') 
      for tx' != tx of his choice. But that won't help him, because the first
      valid c step in the chain is for tx and not for tx'.
      
      > The other issue with your approach is that if it is rolled out today,
      > it will effectively double transaction volumes - this is what I tried
      > to solve in solutions 2 and 3 in my article by instead modifying the
      > address generation process.
      
      Yep, it needs two entries in the blockchain, and that does not mean
      that it doubles the data. It will need some more bytes in the
      blockchain but also proper PQ-transactions could need more bytes in the
      blockchain, so I don't think that's the major issue.
      
      
      > 
      > Regards,
      > 
      > Tristan
      > 
      > On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
      > -dev@lists•linuxfoundation.org> wrote:
      > > Hi Tristan,
      > > 
      > > Regarding the "Post-Quantum Address Recovery" part (I haven't read
      > > the
      > > other parts), you may be interested in my message to the list from
      > > last
      > > month and the rest of the thread:
      > > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
      > > y/015659.html
      > > 
      > > This is an approach which aims to avoid the issues that you've
      > > mentioned in your blog post.
      > > 
      > > Best,
      > > Tim
      > > 
      > > On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
      > > wrote:
      > > > Hi all,
      > > >
      > > > Recently I've been exploring what a post-quantum attack on
      > > Bitcoin
      > > > would actually look like, and what options exist for mitigating
      > > it.
      > > >
      > > > I've put up a draft of my research here: https://medium.com/@tris
      > > tanh
      > > > oy/11271f430c41
      > > >
      > > > In summary:
      > > > 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
      > > > scalable
      > > > 2) This is a rapidly advancing space and committment to a
      > > specific
      > > > post-quantum DSA now would be premature
      > > > 3) I've identified a strategy (solution 3 in the draft) that
      > > > mitigates against the worst case scenario (unexpectedly early
      > > attack
      > > > on ECDSA) without requiring any changes to the Bitcoin protocol
      > > or
      > > > total committment to a specific post-quantum DSA that will likely
      > > be
      > > > superseded in the next 3-5 years
      > > > 4) This strategy also serves as a secure means of transferring
      > > > balances into a post-quantum DSA address space, even in the event
      > > > that ECDSA is fully compromised and the transition is reactionary
      > > >
      > > > The proposal is a change to key generation only and will be
      > > > implemented by wallet providers.
      > > >
      > > > Feedback would be most appreciated.
      > > >
      > > > Regards,
      > > >
      > > > Tristan
      > > > _______________________________________________
      > > > bitcoin-dev mailing list
      > > > bitcoin-dev@lists•linuxfoundation.org
      > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
      > > _______________________________________________
      > > bitcoin-dev mailing list
      > > bitcoin-dev@lists•linuxfoundation.org
      > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
      > 
      > 
      
      
      ^ permalink raw reply	[flat|nested] 12+ messages in thread

    • • * Re: [bitcoin-dev] Transition to post-quantum
          2018-02-13  6:46     ` Tim Ruffing
        @ 2018-02-13 10:06       ` Tristan Hoy
          2018-02-15 15:59         ` Tim Ruffing
          0 siblings, 1 reply; 12+ messages in thread
        From: Tristan Hoy @ 2018-02-13 10:06 UTC (permalink / raw)
          To: bitcoin-dev
        
        On 13/02/2018 5:46 PM, Tim Ruffing via bitcoin-dev wrote:
        > On Tue, 2018-02-13 at 08:32 +1100, Tristan Hoy wrote:
        >> In a post-quantum world, your second "d" type transaction is
        >> completely forgeable, which means it is vulnerable to front-running.
        >> An adversary capable of breaking ECDSA needs only listen for these
        >> transactions, obtain "classic_sk" and then use a higher fee (or
        >> relationship with a miner) to effectively turn your original "d"
        >> transaction into a double-spend, with the forged transaction sending
        >> all your funds to the adversary.
        > That's not true. The d(ecommit) transaction, or better let's call it
        > "decommit step" of a two-step transaction does not specify the effects
        > (output script). This is what I denote by "tx" in the writeup, and it's
        > already fixed by the c(ommit) step.
        >
        > So yes, if the user finally reveals
        >    d  = classic_pk||Sign(classic_sk, tx)
        > a quantum attacker can indeed forge
        >    d' = classic_pk||Sign(classic_sk, tx')
        > for tx' != tx of his choice. But that won't help him, because the first
        > valid c step in the chain is for tx and not for tx'.
        Thank you for clarifying, I should have caught that.
        
        >> The other issue with your approach is that if it is rolled out today,
        >> it will effectively double transaction volumes - this is what I tried
        >> to solve in solutions 2 and 3 in my article by instead modifying the
        >> address generation process.
        > Yep, it needs two entries in the blockchain, and that does not mean
        > that it doubles the data. It will need some more bytes in the
        > blockchain but also proper PQ-transactions could need more bytes in the
        > blockchain, so I don't think that's the major issue.
        >
        The worst-case outcome is that ECDSA is broken before PQ addresses are 
        rolled out. There is no reactive response to this - all the existing 
        ECDSA addresses will be compromised. A proactive measure is required, 
        and it should be deployed sooner rather than later.
        
        Any two-step approach adopted now as a proactive measure will not only 
        bloat the blockchain, it will also double the effective confirmation 
        time - for all transactions between now and when PQ addresses are rolled 
        out, which seems unlikely to happen in the next 5 years. The bloat will 
        be permanent.
        
        Either way, would you mind if I included your approach in the article, 
        with credit? I will seek your review before publishing.
        
        >> Regards,
        >>
        >> Tristan
        >>
        >> On Tue, Feb 13, 2018 at 2:50 AM, Tim Ruffing via bitcoin-dev <bitcoin
        >> -dev@lists•linuxfoundation.org> wrote:
        >>> Hi Tristan,
        >>>
        >>> Regarding the "Post-Quantum Address Recovery" part (I haven't read
        >>> the
        >>> other parts), you may be interested in my message to the list from
        >>> last
        >>> month and the rest of the thread:
        >>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Januar
        >>> y/015659.html
        >>>
        >>> This is an approach which aims to avoid the issues that you've
        >>> mentioned in your blog post.
        >>>
        >>> Best,
        >>> Tim
        >>>
        >>> On Tue, 2018-02-13 at 01:13 +1100, Tristan Hoy via bitcoin-dev
        >>> wrote:
        >>>> Hi all,
        >>>>
        >>>> Recently I've been exploring what a post-quantum attack on
        >>> Bitcoin
        >>>> would actually look like, and what options exist for mitigating
        >>> it.
        >>>> I've put up a draft of my research here: https://medium.com/@tris
        >>> tanh
        >>>> oy/11271f430c41
        >>>>
        >>>> In summary:
        >>>> 1) None of the recommended post-quantum DSAs (XMSS, SPHINCS) are
        >>>> scalable
        >>>> 2) This is a rapidly advancing space and committment to a
        >>> specific
        >>>> post-quantum DSA now would be premature
        >>>> 3) I've identified a strategy (solution 3 in the draft) that
        >>>> mitigates against the worst case scenario (unexpectedly early
        >>> attack
        >>>> on ECDSA) without requiring any changes to the Bitcoin protocol
        >>> or
        >>>> total committment to a specific post-quantum DSA that will likely
        >>> be
        >>>> superseded in the next 3-5 years
        >>>> 4) This strategy also serves as a secure means of transferring
        >>>> balances into a post-quantum DSA address space, even in the event
        >>>> that ECDSA is fully compromised and the transition is reactionary
        >>>>
        >>>> The proposal is a change to key generation only and will be
        >>>> implemented by wallet providers.
        >>>>
        >>>> Feedback would be most appreciated.
        >>>>
        >>>> Regards,
        >>>>
        >>>> Tristan
        >>>> _______________________________________________
        >>>> bitcoin-dev mailing list
        >>>> bitcoin-dev@lists•linuxfoundation.org
        >>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
        >>> _______________________________________________
        >>> bitcoin-dev mailing list
        >>> bitcoin-dev@lists•linuxfoundation.org
        >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
        >>
        > _______________________________________________
        > bitcoin-dev mailing list
        > bitcoin-dev@lists•linuxfoundation.org
        > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
        
        
        
        ^ permalink raw reply	[flat|nested] 12+ messages in thread

      • • * Re: [bitcoin-dev] Transition to post-quantum
            2018-02-13 10:06       ` Tristan Hoy
          @ 2018-02-15 15:59         ` Tim Ruffing
            2018-02-15 20:27           ` Natanael
            0 siblings, 1 reply; 12+ messages in thread
          From: Tim Ruffing @ 2018-02-15 15:59 UTC (permalink / raw)
            To: bitcoin-dev
          
          First of all, there is indeed an issue in my proposal:
          
          The idea was to include a classic signature to make sure that, if (for
          whatever reason) you have revealed classic_pk already.
          
          However, the problem is that if you have revealed classic_pk, then
          everybody can effectively prevent you from spending the funds as you
          wish by just including the first commit entry with an arbitrary tx in
          the blockchain. That's bad obviously.
          
          Here is a fixed variant, which does not only work with normal P2PKH but
          1) supports basically with any (hash-based) addresses, for which the
          preimage has not been revealed and 2) does not change the conditions
          under which a UTXO can be spent.
          
          Setup
          =====
          We will need multiple hash functions KDF, H, and authenticated
          symmetric encryption Enc/Dec.
          
          Let's assume we have an UTXO with address addr = H_addr(chal), where
          chal is a challenge, i.e., typically a scriptPubKey (what I called
          classic_pk initially) and H_addr is the hash function used to form
          addresses. (If there are multiple UTXO sharing the same address, they
          can be spent simultaneously with this approach.) To spend this UTXO
          with a transaction tx, the user performs the following two steps.
          
          Note that -- in contrast to my earlier emails -- tx is assumed to
          include a solution to the challenge in its input, i.e., a string which
          proves that you are allowed to spend the UTXO (typically a scriptSig). 
          
          Commit step
          ===========
          Derive a symmetric key k = KDF(chal).
          
          Create and publish a commitment in the blockchain that references the
          UTXO as inputs and contains the following data: 
                c = Enc(k, tx)
          
          Wait until c is confirmed. (If it does not confirm, send it again as
          usual.)
          
          Decommit step
          =============
          Create and publish a decommitment with the following data:
                d = chal
          
          Consensus rules
          ===============
          A decommitment d = chal spends a UTXO with address H_addr(chal), if
          there exists a commitment c in the blockchain which references the UTXO
          and which is the first commitment (among all referencing the UTXO) in
          the blockchain such that
          1. k = KDF(chal) correctly decrypts Dec(k, c)
              and
          2. tx = Dec(k, c) is a valid transaction to spend UTXO 
          
          The UTXO is spent as described by tx.
          Commitments never expire.
          
          The second condition covers that tx contains a classic signature under
          the public key specified in chal in normal P2PKH addresses.
          
          The trick here is that the encryption ensures that the user commits to
          tx (including the classic signature) already in the commit step, while
          still keeping the decommitment unique. If I'm not mistaken, this scheme
          is a variant of Adam Back's proposal for committed transactions from
          2013, which he invented for an entirely different goal, namely
          censorship resistance:
          https://bitcointalk.org/index.php?topic=206303.msg2162962#msg2162962
          
          (Adam noted the similarity of the problems on Twitter recently:
          https://twitter.com/adam3us/status/948219461345075201)
          
          The above variant is pretty simple. If it really works and is secure,
          it has the advantage over Adam's proposal that it does not rely on
          ECDSA specifically and can be used for any address type. 
          
          The aforementioned thread in the Bitcoin forum discusses the main
          problem of an approach like that: Everybody can flood the blockchain
          with commitments. Of course, one can require fees to create
          commitments, but that's pretty ugly: If this UTXO is the only money you
          have, then you need to borrow some to pay the transaction fees upfront.
          But this may be the price you need to pay for recovery. This can be
          acceptable, because recovery should be the exception (see below).
          
          On Tue, 2018-02-13 at 21:06 +1100, Tristan Hoy via bitcoin-dev wrote:
          > The worst-case outcome is that ECDSA is broken before PQ addresses
          > are 
          > rolled out. There is no reactive response to this - all the existing 
          > ECDSA addresses will be compromised. A proactive measure is
          > required, 
          > and it should be deployed sooner rather than later.
          
          The proposal above does not require any changes to existing ECDSA
          addresses, so there is no need to change something now already. 
          
          At some point in the future, PQ addresses will be deployed. And at some
          (potentially different) point in the future, we should deploy a
          solution to recover UTXOs. But there's no need to do this today. A
          recovery solution can be deployed even when DLOG has been broken
          already -- not optimal but possible.
          
          > 
          > Any two-step approach adopted now as a proactive measure will not
          > only 
          > bloat the blockchain, it will also double the effective confirmation 
          > time - for all transactions between now and when PQ addresses are
          > rolled 
          > out, which seems unlikely to happen in the next 5 years. The bloat
          > will 
          > be permanent.
          > 
          
          I don't think that's true due to the situation I describe above. We
          don't need to act now.
          
          And even if we act now, i.e., even if we enable the above proposal (or
          any other protocol that enables recovery of UTXOs with addresses)
          today, people are not forced to use it. As long as ECDSA and the other
          schemes we use today remain secure, people can and will continue to
          perform conventional transactions. Ideally, people will need a recovery
          protocol only for those UTXOs which they haven't touched for years and
          have forgotten to convert to PQ in time.
          
          You mentioned confirmation time. A nice thing is that the above
          protocol does not double confirmation times. The sender needs to wait
          for confirmation of the commitment. But as soon as the commitment is
          confirmed, double-spending is excluded already, because the sender is
          committed to the transaction. So the recipient does not need to wait
          for confirmation of the decommitment. As soon as the recipient sees the
          decommitment, everything is good. (If the decommitment is not
          confirmed, the recipient can just re-broadcast it.)
          
          In practice, we could even go further and call the transaction done
          after the commitment is confirmed and the sender sends the data for the
          second step to the recipient off-chain. Only when the recipient wants
          to spend the funds again, the recipient will reveal this data.
          
          The fact that double-spending is excluded after the first step is
          confirmed, is exactly what makes the protocol secure against quantum
          attackers who want to steal the money. As soon as the user reveals the
          ECDSA public key, a quantum attacker has access to all secrets: The
          attacker knows the preimage of the hash can compute the secret key.
          So from this point on, there is no hope that we can distinguish the
          honest user from the attacker. But since the correct transaction has
          been committed to the blockchain, and cannot be changed anymore, we
          don't need to distinguish the honest user from the attacker.
          
          > Either way, would you mind if I included your approach in the
          > article, 
          > with credit? I will seek your review before publishing.
          
          Sure, feel free to include. You don't need to seek my review but I can
          certainly have a look if desired.
          
          Tim
          
          
          ^ permalink raw reply	[flat|nested] 12+ messages in thread

        • • * Re: [bitcoin-dev] Transition to post-quantum
              2018-02-15 15:59         ` Tim Ruffing
            @ 2018-02-15 20:27           ` Natanael
              2018-02-15 21:57             ` Tim Ruffing
              0 siblings, 1 reply; 12+ messages in thread
            From: Natanael @ 2018-02-15 20:27 UTC (permalink / raw)
              To: Tim Ruffing, Bitcoin Dev
            
            [-- Attachment #1: Type: text/plain, Size: 2243 bytes --]
            
            Den 15 feb. 2018 17:00 skrev "Tim Ruffing via bitcoin-dev" <
            bitcoin-dev@lists•linuxfoundation.org>:
            
            
            Consensus rules
            ===============
            A decommitment d = chal spends a UTXO with address H_addr(chal), if
            there exists a commitment c in the blockchain which references the UTXO
            and which is the first commitment (among all referencing the UTXO) in
            the blockchain such that
            1. k = KDF(chal) correctly decrypts Dec(k, c)
                and
            2. tx = Dec(k, c) is a valid transaction to spend UTXO
            
            The UTXO is spent as described by tx.
            Commitments never expire.
            
            
            I addressed this partially before, and this is unfortunately incomplete.
            
            Situation A: Regardless of expiration of commitments, we allow doubles. (Or
            no doubles allowed, but commitments expire.)
            
            If I can block your transaction from confirming (censorship), then I can
            make my own commitment + transaction. The miners will see two commitments
            referencing the same UTXO - but can see only one transaction which match a
            valid challenge and spends them, which is mine. You gained nothing from the
            commitment.
            
            Situation B: We don't allow conflicting commitments, and they never expire.
            I can now freeze everybody's funds trivially with invalid commitments,
            because you can't validate a commitment without seeing a valid transaction
            matching it - and exposing an uncommitted transaction breaks the security
            promise of commitments.
            
            Any additional data in the commitment but hash it the transaction is
            pointless, because the security properties are the same. You can't freeze
            an UTXO after only seeing a commitment, and for any two conflicting
            transactions you may observe it does not matter at all if one references
            UTXO:s or not since you already know both transactions' commitment ages
            anyway. Oldest would win no matter the additional data.
            
            Commitments work when the network can't easily be censored for long enough
            to deploy the attack (at least for 2-3 blocks worth of time). They fail
            when the attacker is capable of performing such an attack.
            
            As I said previously, the only completely solid solution in all
            circumstances is a quantum resistant Zero-knowledge proof algorithm, or
            some equivalent method of proving knowledge of the key without revealing
            any data that enables a quantum attack.
            
            [-- Attachment #2: Type: text/html, Size: 3211 bytes --]
            
            ^ permalink raw reply	[flat|nested] 12+ messages in thread

          • • * Re: [bitcoin-dev] Transition to post-quantum
                2018-02-15 20:27           ` Natanael
              @ 2018-02-15 21:57             ` Tim Ruffing
                2018-02-15 22:44               ` Natanael
                0 siblings, 1 reply; 12+ messages in thread
              From: Tim Ruffing @ 2018-02-15 21:57 UTC (permalink / raw)
                To: Bitcoin Dev
              
              On Thu, 2018-02-15 at 21:27 +0100, Natanael wrote:
              > I addressed this partially before, and this is unfortunately
              > incomplete.
              > 
              > Situation A: Regardless of expiration of commitments, we allow
              > doubles. (Or no doubles allowed, but commitments expire.) 
              > 
              > If I can block your transaction from confirming (censorship), then I
              > can make my own commitment + transaction. The miners will see two
              > commitments referencing the same UTXO - but can see only one
              > transaction which match a valid challenge and spends them, which is
              > mine. You gained nothing from the commitment.
              
              Yes, I assume situation A: 
                * commitments never expire
                * and there is no limit on the number of commitment for the same UTXO
              
              As I understand, you mean "decommitment" when you say "transaction".
              Please correct me if I'm wrong. I'll stick with "decommitment".
              
              Let's assume the attacker blocks the decommitment by the honest user,
              inserts his own malicious commitment and his own decommitment, which
              should be valid for the malicious commitment. Then the miners will see
              two commitments (the earlier commitment by the honest user and the
              later one by the attacker).
              
              Also, the miners will indeed see one valid decommitment. This
              decommitment may have been sent by the attacker but it's the preimage
              chal of the address, because otherwise it's not valid for the malicious
              commitment. But if the decommitment is chal, then this decommitment is
              also valid for the commitment of the honest user, which is earliest
              additionally. So the honest commitment wins. The attacker does not
              succeed and everything is fine.
              
              The reason why this works:
              There is only one unique decommitment for the UTXO (assuming H_addr is
              collision-resistant). The decommitment does not depend on the
              commitment. The attacker cannot send a different decommitment, just
              because there is none.
              
              Maybe I'm wrong and I just don't understand your attack. In this case,
              please explain it more detail.
              
              Regards,
              Tim
              
              
              ^ permalink raw reply	[flat|nested] 12+ messages in thread

            • • * Re: [bitcoin-dev] Transition to post-quantum
                  2018-02-15 21:57             ` Tim Ruffing
                @ 2018-02-15 22:44               ` Natanael
                  2018-02-15 22:45                 ` Natanael
                  2018-02-15 23:44                 ` Tim Ruffing
                  0 siblings, 2 replies; 12+ messages in thread
                From: Natanael @ 2018-02-15 22:44 UTC (permalink / raw)
                  To: Tim Ruffing, Bitcoin Dev
                
                [-- Attachment #1: Type: text/plain, Size: 1623 bytes --]
                
                Den 15 feb. 2018 22:58 skrev "Tim Ruffing via bitcoin-dev" <
                bitcoin-dev@lists•linuxfoundation.org>:
                
                
                Also, the miners will indeed see one valid decommitment. This
                decommitment may have been sent by the attacker but it's the preimage
                chal of the address, because otherwise it's not valid for the malicious
                commitment. But if the decommitment is chal, then this decommitment is
                also valid for the commitment of the honest user, which is earliest
                additionally. So the honest commitment wins. The attacker does not
                succeed and everything is fine.
                
                The reason why this works:
                There is only one unique decommitment for the UTXO (assuming H_addr is
                collision-resistant). The decommitment does not depend on the
                commitment. The attacker cannot send a different decommitment, just
                because there is none.
                
                
                If your argument is that we publish the full transaction minus the public
                key and signatures, just committing to it, and then revealing that later
                (which means an attacker can't modify the transaction in advance in a way
                that produces a valid transaction);
                
                Allowing expiration retains insecurity, while allowing expiration makes it
                a trivial DoS target.
                
                Anybody can flood the miners with invalid transaction commitments. No miner
                can ever prune invalid commitments until a valid transaction is finalized
                which conflicts with the invalid commitments. You can't even rate limit it
                safely.
                
                Like I said in the other thread, this is unreasonable. It's much more
                practical with  simple hash commitment that you can "fold away" in a Merkle
                tree hash and which you don't need to validate until the full transaction
                is published.
                
                [-- Attachment #2: Type: text/html, Size: 2448 bytes --]
                
                ^ permalink raw reply	[flat|nested] 12+ messages in thread

              • • * Re: [bitcoin-dev] Transition to post-quantum
                    2018-02-15 22:44               ` Natanael
                  @ 2018-02-15 22:45                 ` Natanael
                    2018-02-15 23:44                 ` Tim Ruffing
                    1 sibling, 0 replies; 12+ messages in thread
                  From: Natanael @ 2018-02-15 22:45 UTC (permalink / raw)
                    To: Tim Ruffing, Bitcoin Dev
                  
                  [-- Attachment #1: Type: text/plain, Size: 204 bytes --]
                  
                  Small correction, see edited quote
                  
                  Den 15 feb. 2018 23:44 skrev "Natanael" <natanael.l@gmail•com>:
                  
                  Allowing expiration retains insecurity, while *NOT* allowing expiration
                  makes it a trivial DoS target.
                  
                  [-- Attachment #2: Type: text/html, Size: 601 bytes --]
                  
                  ^ permalink raw reply	[flat|nested] 12+ messages in thread

                • * Re: [bitcoin-dev] Transition to post-quantum
                    2018-02-15 22:44               ` Natanael
                    2018-02-15 22:45                 ` Natanael
                  @ 2018-02-15 23:44                 ` Tim Ruffing
                    2019-10-24 15:34                   ` Erik Aronesty
                    1 sibling, 1 reply; 12+ messages in thread
                  From: Tim Ruffing @ 2018-02-15 23:44 UTC (permalink / raw)
                    To: Natanael, Bitcoin Dev
                  
                  On Thu, 2018-02-15 at 23:44 +0100, Natanael wrote:
                  > If your argument is that we publish the full transaction minus the
                  > public key and signatures, just committing to it, and then revealing
                  > that later (which means an attacker can't modify the transaction in
                  > advance in a way that produces a valid transaction);
                  
                  Almost. Actually we reveal the entire transaction later. 
                  
                  > 
                  > [...] while *NOT* allowing expiration makes it a trivial DoS target. 
                  > 
                  > Anybody can flood the miners with invalid transaction commitments. No
                  > miner can ever prune invalid commitments until a valid transaction is
                  > finalized which conflicts with the invalid commitments. You can't
                  > even rate limit it safely. 
                  
                  Yes, that's certainly true. I mentioned that issue already. 
                  
                  You can rate limit this: The only thing I see is that one can require
                  transaction fees even for commitments. That's super annoying, because
                  you need a second (PQ-)UTXO just to commit. But it's not impossible.
                  
                  You can call this impractical and this may well be true. But what will
                  be most practical in the future depends on many parameters that are
                  totally unclear at the moment, e.g., the efficiency of zero-knowledge
                  proof systems. Who knows?
                  
                  If you would like to use zero-knowledge proofs to recover an UTXO with
                  an P2PKH address, you need to prove in zero-knowledge that you know
                  some secret key x such that H(g^x)=addr. That seems plausible. But
                  P2PKH is by far the simplest example. For arbitrary scripts, this can 
                  become pretty complex and nasty, even if our proof systems and machines
                  are fast enough.
                  
                  
                  
                  ^ permalink raw reply	[flat|nested] 12+ messages in thread

                • • * Re: [bitcoin-dev] Transition to post-quantum
                      2018-02-15 23:44                 ` Tim Ruffing
                    @ 2019-10-24 15:34                   ` Erik Aronesty
                      0 siblings, 0 replies; 12+ messages in thread
                    From: Erik Aronesty @ 2019-10-24 15:34 UTC (permalink / raw)
                      To: Tim Ruffing via bitcoin-dev
                    
                    - It would be hard to prove you have access to an x that can produce
                    H(g^x) in a way that doesn't expose g^x and isn't one of those slow,
                    interactive bit-encryption algorithms.
                    
                    - Instead a simple scheme would publish a transaction to the
                    blockchain that lists:
                         - pre-quantum signature
                         - hash of post-quantum address
                    
                    - Any future transactions would require both the pre *and*
                    post-quantum signatures.
                    
                    That scheme would need to be implemented sufficient number of years
                    before quantum became a pressing issue, but it's super simple,
                    spam-proof (requires fees), and flexible enough that it can change as
                    post-quantum addressing improves.
                    
                    Imagine there are 2 quantum addressing schemes in order of discovery.
                    
                    1. Soft-fork 1 accepts the first scheme and people begin publishing
                    PRE/POST upgrades.
                    2. Discovery is made that shows a second scheme has smaller
                    transactions and faster validation.
                    3. Soft-fork 2 refuses to accept upgrades to the first scheme in
                    transactions beyond a certain block number in order to improve
                    performance.
                    
                    
                    
                    
                    
                    
                    On Thu, Feb 15, 2018 at 6:44 PM Tim Ruffing via bitcoin-dev
                    <bitcoin-dev@lists•linuxfoundation.org> wrote:
                    >
                    > On Thu, 2018-02-15 at 23:44 +0100, Natanael wrote:
                    > > If your argument is that we publish the full transaction minus the
                    > > public key and signatures, just committing to it, and then revealing
                    > > that later (which means an attacker can't modify the transaction in
                    > > advance in a way that produces a valid transaction);
                    >
                    > Almost. Actually we reveal the entire transaction later.
                    >
                    > >
                    > > [...] while *NOT* allowing expiration makes it a trivial DoS target.
                    > >
                    > > Anybody can flood the miners with invalid transaction commitments. No
                    > > miner can ever prune invalid commitments until a valid transaction is
                    > > finalized which conflicts with the invalid commitments. You can't
                    > > even rate limit it safely.
                    >
                    > Yes, that's certainly true. I mentioned that issue already.
                    >
                    > You can rate limit this: The only thing I see is that one can require
                    > transaction fees even for commitments. That's super annoying, because
                    > you need a second (PQ-)UTXO just to commit. But it's not impossible.
                    >
                    > You can call this impractical and this may well be true. But what will
                    > be most practical in the future depends on many parameters that are
                    > totally unclear at the moment, e.g., the efficiency of zero-knowledge
                    > proof systems. Who knows?
                    >
                    > If you would like to use zero-knowledge proofs to recover an UTXO with
                    > an P2PKH address, you need to prove in zero-knowledge that you know
                    > some secret key x such that H(g^x)=addr. That seems plausible. But
                    > P2PKH is by far the simplest example. For arbitrary scripts, this can
                    > become pretty complex and nasty, even if our proof systems and machines
                    > are fast enough.
                    >
                    > _______________________________________________
                    > bitcoin-dev mailing list
                    > bitcoin-dev@lists•linuxfoundation.org
                    > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
                    
                    
                    ^ permalink raw reply	[flat|nested] 12+ messages in thread

end of thread, other threads:[~2019-10-24 15:34 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-02-12 14:13 [bitcoin-dev] Transition to post-quantum Tristan Hoy
2018-02-12 15:50 ` Tim Ruffing
2018-02-12 21:32   ` Tristan Hoy
2018-02-13  6:46     ` Tim Ruffing
2018-02-13 10:06       ` Tristan Hoy
2018-02-15 15:59         ` Tim Ruffing
2018-02-15 20:27           ` Natanael
2018-02-15 21:57             ` Tim Ruffing
2018-02-15 22:44               ` Natanael
2018-02-15 22:45                 ` Natanael
2018-02-15 23:44                 ` Tim Ruffing
2019-10-24 15:34                   ` Erik Aronesty

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox