Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.216.48 as permitted sender)
	client-ip=209.85.216.48; envelope-from=etotheipi@gmail.com;
	helo=mail-qa0-f48.google.com; 
Message-ID: <516EFBB8.8060805@gmail.com>
Date: Wed, 17 Apr 2013 15:44:56 -0400
From: Alan Reiner <etotheipi@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
	rv:17.0) Gecko/20130329 Thunderbird/17.0.5
MIME-Version: 1.0
To: bitcoin-development@lists.sourceforge.net
References: <CANEZrP1yKeQMayFHsEUWtA3=q+v5rPAutjzEFVVHopPGNZ4jGQ@mail.gmail.com>
	<453bfc69-b2ab-4992-9807-55270fbda0db@email.android.com>
	<CANEZrP0z6W0ZDsytQ7Rcqb5L6rswn1wv8cbR7c383Dmpzu+gyg@mail.gmail.com>
In-Reply-To: <CANEZrP0z6W0ZDsytQ7Rcqb5L6rswn1wv8cbR7c383Dmpzu+gyg@mail.gmail.com>
Content-Type: multipart/alternative;
	boundary="------------000300000603010002000707"
Subject: Re: [Bitcoin-development] Anti DoS for tx replacement
Precedence: list

This is a multi-part message in MIME format.
--------------000300000603010002000707
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

One of the big topics of recent past on IRC is "malleability" of
transactions:  to what extent can someone /else /change your signed
transaction without affecting its validity?  In the past I used to
consider this just annoying, but not so malicious.  But in terms of HFT,
it sounds like malicious behavior is possible:

To recap the procedure:

(1)  Alice creates a transaction, Tx1, for 10 BTC to a 2-of-2-{Alice,
Bob} address.  It has a locktime of 30 days in the future.
(2)  Before signing the transaction, she gets Bob to sign a transaction,
Tx2, from 2-of-2-{Alice, Bob} back to herself.   That transaction
references the Tx1 by hash.
(3)  Any time in the next 30 days, Alice can sign an alternate Tx2
transactions reducing the amount returned to self and increasing amount
to Bob, as a method of paying Bob more.  Bob doesn't need to broadcast
anything except for the last one, 29 days later.

It was originally conceived that Bob couldn't do anything malicious,
because Alice gets Bob to sign Tx2-spending-Tx1 before she gives him
Tx1.  The problem is that Bob can follow her process, then
broadcast/mine Tx1' (Tx1-prime), which has a different number of 0x00
pad bytes in the signatures, or "flips the sign" of one of the s-values
in the signature, thus changing the hash of Tx1.

By doing this, Bob has now created a transaction, Tx1', that Tx2 no
longer returns to Alice.  It's not flat-out theft, because Tx1 still
sends to a 2-of-2 address requiring both of their signatures.  But Bob
didn't risk anything to do this, besides his reputation/trust.  He now
has Alice's money locked and can hold it for ransom, since she needs his
signature to do move it.  He could offer his signature for half of it.

Of course, these types of HFT contracts will usually be between parties
that have some mutual respect/history.  Thus, they are not usually
zero-trust.   But we should find a way to try to close that, if
possible.  For instance, if the malleability was reduced to one bit, you
could just have Bob sign two different transactions before Alice
broadcasts Tx1.  The two tx would be from either variant.  But I know
there's too many bits of malleability in the transaction serialization
for that to work.  Is there any way to avoid this?

-Alan


On 04/17/2013 05:48 AM, Mike Hearn wrote:
> When this system was first being discussed, Gavin was concerned that
> miner incentives were to ignore replacements because it meant extra
> work and the replacement might have equal or lower fees than before
> (or indeed, no fees). He proposed two solutions: one is to
> progressively raise the fee on each replacement. The other is to
> specify lock time in terms of blocks and then step it backwards once
> for each replacement, thus ensuring that by replacing the transaction
> you get to claim any attached fee earlier.
>
> It should be apparent that both solutions can be implemented by
> whichever application is running the contract - the core Bitcoin
> network and software is agnostic either way.
>
> Now, Gavin and I disagreed on whether this would actually be
> necessary. As I already pointed out, both solutions seriously reduce
> the utility of HFT because they limit how often you can update the
> contract. Instead of an online game billing you per second, maybe it
> can only do it per minute or per 10 minutes with the lock time
> solution because otherwise you run out of blocks, and with
> ever-increasing fees perhaps the contract becomes too expensive to
> justify after a while.
>
> So it'd be nice if this ended up not being necessary. Experience
> indicates that rational miners typically don't pursue a short-termist
> profit-at-any-cost agenda - free transactions have always been
> included in blocks, miners include transactions even though you could
> avoid a lot of complexity by just not including any at all, etc. Some
> miners like BTC Guild have actually sacrificed significant amounts of
> money for the good of the system. You can see this in terms of
> rational self interest - miners earn Bitcoins thus it's in their
> interest for Bitcoins to be as useful as possible, as that is what
> gives them value. Or you can see it in terms of ideologically-driven
> altruism. Or both.
>
> If I were to implement an application that used tx replacement, I
> would probably start with replacements that don't change the fees and
> don't count down the lock time field. We can then observe whether
> miners bother changing their software to behave differently, or
> whether the inherent utility of the application is enough to convince
> them to play by the default rules. Ideally at least one application
> made possible by this feature is a "killer app" - something so useful
> / unique / compelling that people want to obtain Bitcoin just to use
> it. If someone can find such an app, then rational miners should want
> tx replacement to work as reliably as possible because it boosts the
> value of their earnings.
>
> There are some other misc details - reactivation requires that we bump
> the protocol version and start relaying non-final transactions to new
> nodes again. Those nodes should relay replacements but not let them
> enter wallets unless/until the wallet software itself can handle them
> better, for instance, by communicating via APIs anticipated
> confirmation times. This is something for individual wallet APIs to
> handle on their own, and just ignoring non-final transactions is a
> perfectly workable approach for Bitcoin-Qt.
>
>
> ------------------------------------------------------------------------------
> Precog is a next-generation analytics platform capable of advanced
> analytics on semi-structured data. The platform includes APIs for building
> apps and a phenomenal toolset for data science. Developers can use
> our toolset for easy data analysis & visualization. Get a free account!
> http://www2.precog.com/precogplatform/slashdotnewsletter
>
>
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development


--------------000300000603010002000707
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

<html>
  <head>
    <meta content="text/html; charset=ISO-8859-1"
      http-equiv="Content-Type">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    One of the big topics of recent past on IRC is "malleability" of
    transactions:&nbsp; to what extent can someone <i>else </i>change your
    signed transaction without affecting its validity?&nbsp; In the past I
    used to consider this just annoying, but not so malicious.&nbsp; But in
    terms of HFT, it sounds like malicious behavior is possible:<br>
    <br>
    To recap the procedure:<br>
    <br>
    (1)&nbsp; Alice creates a transaction, Tx1, for 10 BTC to a
    2-of-2-{Alice, Bob} address.&nbsp; It has a locktime of 30 days in the
    future.<br>
    (2)&nbsp; Before signing the transaction, she gets Bob to sign a
    transaction, Tx2, from 2-of-2-{Alice, Bob} back to herself.&nbsp;&nbsp; That
    transaction references the Tx1 by hash.<br>
    (3)&nbsp; Any time in the next 30 days, Alice can sign an alternate Tx2
    transactions reducing the amount returned to self and increasing
    amount to Bob, as a method of paying Bob more.&nbsp; Bob doesn't need to
    broadcast anything except for the last one, 29 days later.<br>
    <br>
    It was originally conceived that Bob couldn't do anything malicious,
    because Alice gets Bob to sign Tx2-spending-Tx1 before she gives him
    Tx1.&nbsp; The problem is that Bob can follow her process, then
    broadcast/mine Tx1' (Tx1-prime), which has a different number of
    0x00 pad bytes in the signatures, or "flips the sign" of one of the
    s-values in the signature, thus changing the hash of Tx1.<br>
    <br>
    By doing this, Bob has now created a transaction, Tx1', that Tx2 no
    longer returns to Alice.&nbsp; It's not flat-out theft, because Tx1 still
    sends to a 2-of-2 address requiring both of their signatures.&nbsp; But
    Bob didn't risk anything to do this, besides his reputation/trust.&nbsp;
    He now has Alice's money locked and can hold it for ransom, since
    she needs his signature to do move it.&nbsp; He could offer his signature
    for half of it.<br>
    <br>
    Of course, these types of HFT contracts will usually be between
    parties that have some mutual respect/history.&nbsp; Thus, they are not
    usually zero-trust.&nbsp;&nbsp; But we should find a way to try to close that,
    if possible.&nbsp; For instance, if the malleability was reduced to one
    bit, you could just have Bob sign two different transactions before
    Alice broadcasts Tx1.&nbsp; The two tx would be from either variant.&nbsp; But
    I know there's too many bits of malleability in the transaction
    serialization for that to work.&nbsp; Is there any way to avoid this?<br>
    <br>
    -Alan<br>
    <br>
    <br>
    <br>
    <div class="moz-cite-prefix">On 04/17/2013 05:48 AM, Mike Hearn
      wrote:<br>
    </div>
    <blockquote
cite="mid:CANEZrP0z6W0ZDsytQ7Rcqb5L6rswn1wv8cbR7c383Dmpzu+gyg@mail.gmail.com"
      type="cite">
      <div dir="ltr">When this system was first being discussed, Gavin
        was concerned that miner incentives were to ignore replacements
        because it meant extra work and the replacement might have equal
        or lower fees than before (or indeed, no fees). He proposed two
        solutions: one is to progressively raise the fee on each
        replacement. The other is to specify lock time in terms of
        blocks and then step it backwards once for each replacement,
        thus ensuring that by replacing the transaction you get to claim
        any attached fee earlier.
        <div>
          <br>
        </div>
        <div style="">It should be apparent that both solutions can be
          implemented by whichever application is running the contract -
          the core Bitcoin network and software is agnostic either way.</div>
        <div style=""><br>
        </div>
        <div style="">Now, Gavin and I disagreed on whether this would
          actually be necessary. As I already pointed out, both
          solutions seriously reduce the utility of HFT because they
          limit how often you can update the contract. Instead of an
          online game billing you per second, maybe it can only do it
          per minute or per 10 minutes with the lock time solution
          because otherwise you run out of blocks, and with
          ever-increasing fees perhaps the contract becomes too
          expensive to justify after a while.</div>
        <div style=""><br>
        </div>
        <div style="">So it'd be nice if this ended up not being
          necessary. Experience indicates that rational miners typically
          don't pursue a short-termist profit-at-any-cost agenda - free
          transactions have always been included in blocks, miners
          include transactions even though you could avoid a lot of
          complexity by just not including any at all, etc. Some miners
          like BTC Guild have actually sacrificed significant amounts of
          money for the good of the system. You can see this in terms of
          rational self interest - miners earn Bitcoins thus it's in
          their interest for Bitcoins to be as useful as possible, as
          that is what gives them value. Or you can see it in terms of
          ideologically-driven altruism. Or both.</div>
        <div style=""><br>
        </div>
        <div style="">If I were to implement an application that used tx
          replacement, I would probably start with replacements that
          don't change the fees and don't count down the lock time
          field. We can then observe whether miners bother changing
          their software to behave differently, or whether the inherent
          utility of the application is enough to convince them to play
          by the default rules. Ideally at least one application made
          possible by this feature is a "killer app" - something so
          useful / unique / compelling that people want to obtain
          Bitcoin just to use it. If someone can find such an app, then
          rational miners should want tx replacement to work as reliably
          as possible because it boosts the value of their earnings.</div>
        <div style=""><br>
        </div>
        <div style="">There are some other misc details - reactivation
          requires that we bump the protocol version and start relaying
          non-final transactions to new nodes again. Those nodes should
          relay replacements but not let them enter wallets unless/until
          the wallet software itself can handle them better, for
          instance, by communicating via APIs anticipated confirmation
          times. This is something for individual wallet APIs to handle
          on their own, and just ignoring non-final transactions is a
          perfectly workable approach for Bitcoin-Qt.</div>
      </div>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">------------------------------------------------------------------------------
Precog is a next-generation analytics platform capable of advanced
analytics on semi-structured data. The platform includes APIs for building
apps and a phenomenal toolset for data science. Developers can use
our toolset for easy data analysis &amp; visualization. Get a free account!
<a class="moz-txt-link-freetext" href="http://www2.precog.com/precogplatform/slashdotnewsletter">http://www2.precog.com/precogplatform/slashdotnewsletter</a></pre>
      <br>
      <fieldset class="mimeAttachmentHeader"></fieldset>
      <br>
      <pre wrap="">_______________________________________________
Bitcoin-development mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-development@lists.sourceforge.net</a>
<a class="moz-txt-link-freetext" href="https://lists.sourceforge.net/lists/listinfo/bitcoin-development">https://lists.sourceforge.net/lists/listinfo/bitcoin-development</a>
</pre>
    </blockquote>
    <br>
  </body>
</html>

--------------000300000603010002000707--