path: root/4d/57780728fc1542d4848ff69c5a9646763ae9dd

Return-Path: <kristovatlas.lists@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id BE91EBB3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jun 2015 22:09:36 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-la0-f46.google.com (mail-la0-f46.google.com
	[209.85.215.46])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id CEA98240
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jun 2015 22:09:34 +0000 (UTC)
Received: by lagi2 with SMTP id i2so34352321lag.2
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 24 Jun 2015 15:09:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:date:message-id:subject:from:to
	:cc:content-type;
	bh=6sdg8/Fd+e7ODwu5iAWNxuChdsOjvjFA/c9a/vgQLu4=;
	b=pBnPZAjjaZ0XOKS8RxFWcrs9pzk6l8T3jhHMc3AbN/pCZdmYfwSaEE1YtVzJvhGbie
	myzXBZWgHm5UDSxaw+BK7hjBrT0y6t2/4VIuZjdKEPMNw4MT0cku6ttc1zFnN59udV5r
	oBxz22cZ1dychzi30eo7G0aFm8cfSGyiNXa5/hjIF7dzNJC3/EJ8NB4Nmo8MbRCGv4XY
	T8+2kLHS3SvtPU8R3xnDx3uVflCa7NlSRS++SLz673f982a9vlJ27ptB2GLpHjMfm6fn
	YDUP/OBIZkABcyv32IlIUyho1jMLNGBneo6h5zC/Im36qzKIcVN+LE4/4kSE/J/JnaFa
	ApMA==
MIME-Version: 1.0
X-Received: by 10.112.92.99 with SMTP id cl3mr22406590lbb.34.1435183772897;
	Wed, 24 Jun 2015 15:09:32 -0700 (PDT)
Received: by 10.152.163.98 with HTTP; Wed, 24 Jun 2015 15:09:32 -0700 (PDT)
In-Reply-To: <CAGH37S+674cAVC7=WvST_SPkXjfNkzbj7Y_me_M6C+ieHX6EAA@mail.gmail.com>
References: <87k2vhfnx9.fsf@rustcorp.com.au>
	<CAAS2fgRgWZX_O_2O1bgdFd_04xVp5Lnpw4hf=v6RSTXmsbdzPQ@mail.gmail.com>
	<CAGH37S+674cAVC7=WvST_SPkXjfNkzbj7Y_me_M6C+ieHX6EAA@mail.gmail.com>
Date: Wed, 24 Jun 2015 18:09:32 -0400
Message-ID: <CAGH37SJxUsGQU_WjnQE4N3=hPeOtNHUyTStkajeMK6h6OBCjow@mail.gmail.com>
From: Kristov Atlas <kristovatlas.lists@gmail.com>
To: Gregory Maxwell <gmaxwell@gmail.com>
Content-Type: multipart/alternative; boundary=001a11336ee0f8974005194ac261
X-Spam-Status: No, score=-2.7 required=5.0 tests=AC_DIV_BONANZA,BAYES_00,
	DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,HTML_MESSAGE,
	RCVD_IN_DNSWL_LOW autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: Re: [bitcoin-dev] [Bitcoin-development] [RFC] Canonical input and
 output ordering in transactions
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Wed, 24 Jun 2015 22:09:36 -0000

--001a11336ee0f8974005194ac261
Content-Type: text/plain; charset=UTF-8

Following up on this topic...

gmaxwell has reserved BIP 69 for my proposal.

It has been implemented by Electrum in v2.3.2:
https://github.com/spesmilo/electrum/blob/master/RELEASE-NOTES

Rusty has kindly tweaked his original canonical ordering proposal
implementation for Bitcoin Core's wallet client to fit my proposal:
https://github.com/rustyrussell/bitcoin/tree/bip-69 (needs testing)

Outstanding objections appear to me to boil down to two points:

1) Some transactions cannot comply with this BIP because there are input
and/or put index dependencies.

My response: No big deal, it's informational. They simply won't be
compliant with the BIP, and that's fine with me.

2) If we set a standard now for transactions that is not apparently random
ordering from the perspective of passive blockchain observers, transactions
that can't comply with this BIP will stand out. Also, if we change our
collective minds in the future about how ordering should be handled, those
future transactions would stand out. Therefore, the "safe" course of action
is to come up with another scheme that appears to be random ordering from
the perspective of a passive blockchain observer.

My response: Apparently-random but owner-verifiable ordering is doable.
Discussion of this has revolved around what I have called a "sorting key"
-- sort lexicographically, and then reorder according to the bits in a
sorting key that is impossible to predict by an attacker. This means
passive observers cannot determine anything meaningful about the
transaction (e.g. which output is change, information leaked based on utxo
selection algorithm for inputs, etc.) but the owner of the funds and the
sorting key can verify that his transaction matches the canonical
specification. Ideally, I think the key should rotate for each transaction
to avoid the possibility that a static key can link multiple transactions
together. The key should be rotated in such a fashion that the next
iteration is not predictable to anyone except the key holder (e.g. put the
key through a secure pseudo-random function for each new iteration). This
could be done by generating a few bytes of entropy upon wallet creation and
keeping track of the current iteration of rotation. HD wallets could derive
the initial state of the sorting key by deriving it from the HD seed. There
are a variety of schemes that could work here.

My main objection to this family of approaches at present is complexity. I
suspect that many wallet clients will not want to implement the BIP if they
have to maintain a sorting key.

A second objection is that no one will be able to detect anomalies in BIP
compliance except for the sorting key holder. Most users probably will not
bother to verify this. For code reviewers, this means that the sorting key
is yet another aspect of the code base that must be scrutinized to ensure
it is not being used as a covert channel or has been underhandedly weakened
in some fashion.

Also, I will mention an ancillary benefit of a non-random canonical
ordering: it makes unit testing of transactions for Bitcoin wallets simpler.

Given all of the above, I will reiterate my preference to keep the proposal
as it is now. The pull request is here:
https://github.com/bitcoin/bips/pull/157

If there is market demand for it, a separate sorting key-based proposal
could be written which can compete with this BIP and over time successfully
deprecate it. I would currently envision that as an HD BIP with a new
purpose code.

-Kristov


On Mon, Jun 15, 2015 at 12:01 AM, Kristov Atlas <
kristovatlas.lists@gmail.com> wrote:

> On Sun, Jun 14, 2015 at 7:02 PM, Gregory Maxwell <gmaxwell@gmail.com>
> wrote:
>
>> I'm not a great fan of this proposal for two reasons: The first is
>> that the strict ordering requirements is incompatible with future
>> soft-forks that may expose additional ordering constraints. Today we
>> have _SINGLE, which as noted this interacts with poorly, but there
>> have been other constraints proposed that this would also interact
>> with poorly.
>>
>
> I'm not clear on why this is a problem, so long as the canonical ordering
> BIP is *optional*. Unless there is a specific plan to soft fork a change
> that would break the BIP and it is fairly imminent, I see this only as a
> reason not to integrate it into isStandard().
>
>
>> The second is that even absent consensus rules there may be invisible
>> constraints in systems-- e.g. hardware wallets that sign top down, or
>> future transaction covenants that have constraints about ordering,  or
>> proof systems that use (yuck) midstate compression for efficiency. Right
>> now, with random ordering these applications are fairly
>> indistinguishable from other random uses (since their imposed order
>> could come about by chance) but if everyone else was ordered, even if
>> wasn't enforced.. these would be highly distinguishable. Which would
>> be unfortunate.
>
>
> Maybe they shouldn't be doing that. :-P
>
>
>> I think perhaps the motivations here are understated. We have not seen
>> any massive deployments of accidentally broken ordering that I'm aware
>> of-- and an implementation that got this wrong in a harmful way would
>> likely make far more fatal mistakes (e.g. non random private keys).
>>
>
> In my reading of various wallet client sources, it is common that wallet
> clients will use cryptographically weak sources of randomness to sort
> outputs -- that is, the ones that actually bother to randomly sort. I can
> hunt down some examples if this would substantially contribute to the
> discussion.
>
> As an alternative to this proposal the ordering can be privately
>> derandomized in the same way DSA is, to avoid the need for an actual
>> number source.  If getting the randomness right were really the only
>> motivation, I'd suggest we propose a simple derandomized randomization
>> algorithm--- e.g. take the order from (H(input ids||client secret)).
>>
>
> This sounds similar to an idea that Sergio pitched to me privately, which
> was for wallets to have a private sorting key that they can use to sort
> inputs and outputs. However, I suspect that adding yet another key which
> will necessarily require special key rotation rules and maybe special
> backup procedures will mean that this standard will not be widely adopted
> any time soon. Ideally, I'd like to see someone write a different BIP with
> the sorting key idea and let them compete in the wallet client market
> rather than trying to anticipate what is best for all clients and
> distilling two good ideas into one artificially.
>
> -Kristov
>
>

--001a11336ee0f8974005194ac261
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div><div><div><div><div><div><div><div><div><div><div><di=
v><div>Following up on this topic...<br><br></div>gmaxwell has reserved BIP=
 69 for my proposal.<br><br></div>It has been implemented by Electrum in v2=
.3.2: <a href=3D"https://github.com/spesmilo/electrum/blob/master/RELEASE-N=
OTES">https://github.com/spesmilo/electrum/blob/master/RELEASE-NOTES</a><br=
></div><br>Rusty has kindly tweaked his original canonical ordering proposa=
l implementation for Bitcoin Core&#39;s wallet client to fit my proposal: <=
a href=3D"https://github.com/rustyrussell/bitcoin/tree/bip-69">https://gith=
ub.com/rustyrussell/bitcoin/tree/bip-69</a> (needs testing)<br><br></div>Ou=
tstanding objections appear to me to boil down to two points:<br><br></div>=
1) Some transactions cannot comply with this BIP because there are input an=
d/or put index dependencies.<br><br></div>My response: No big deal, it&#39;=
s informational. They simply won&#39;t be compliant with the BIP, and that&=
#39;s fine with me.<br><br></div>2) If we set a standard now for transactio=
ns that is not apparently random ordering from the perspective of passive b=
lockchain observers, transactions that can&#39;t comply with this BIP will =
stand out. Also, if we change our collective minds in the future about how =
ordering should be handled, those future transactions would stand out. Ther=
efore, the &quot;safe&quot; course of action is to come up with another sch=
eme that appears to be random ordering from the perspective of a passive bl=
ockchain observer.<br><br></div>My response: Apparently-random but owner-ve=
rifiable ordering is doable. Discussion of this has revolved around what I =
have called a &quot;sorting key&quot; -- sort lexicographically, and then r=
eorder according to the bits in a sorting key that is impossible to predict=
 by an attacker. This means passive observers cannot determine anything mea=
ningful about the transaction (e.g. which output is change, information lea=
ked based on utxo selection algorithm for inputs, etc.) but the owner of th=
e funds and the sorting key can verify that his transaction matches the can=
onical specification. Ideally, I think the key should rotate for each trans=
action to avoid the possibility that a static key can link multiple transac=
tions together. The key should be rotated in such a fashion that the next i=
teration is not predictable to anyone except the key holder (e.g. put the k=
ey through a secure pseudo-random function for each new iteration). This co=
uld be done by generating a few bytes of entropy upon wallet creation and k=
eeping track of the current iteration of rotation. HD wallets could derive =
the initial state of the sorting key by deriving it from the HD seed. There=
 are a variety of schemes that could work here.<br><br></div>My main object=
ion to this family of approaches at present is complexity. I suspect that m=
any wallet clients will not want to implement the BIP if they have to maint=
ain a sorting key.<br><br></div><div>A second objection is that no one will=
 be able to detect anomalies in BIP compliance except for the sorting key h=
older. Most users probably will not bother to verify this. For code reviewe=
rs, this means that the sorting key is yet another aspect of the code base =
that must be scrutinized to ensure it is not being used as a covert channel=
 or has been underhandedly weakened in some fashion.<br></div><div><br></di=
v>Also, I will mention an ancillary benefit of a non-random canonical order=
ing: it makes unit testing of transactions for Bitcoin wallets simpler.<br>=
<br></div>Given all of the above, I will reiterate my preference to keep th=
e proposal as it is now. The pull request is here: <a href=3D"https://githu=
b.com/bitcoin/bips/pull/157">https://github.com/bitcoin/bips/pull/157</a><b=
r><br></div>If there is market demand for it, a separate sorting key-based =
proposal could be written which can compete with this BIP and over time suc=
cessfully deprecate it. I would currently envision that as an HD BIP with a=
 new purpose code.<br><br></div>-Kristov<br><div><div><div><div><div><div><=
div><div><div><div><div><div><div><div><br></div></div></div></div></div></=
div></div></div></div></div></div></div></div></div></div><div class=3D"gma=
il_extra"><br><div class=3D"gmail_quote">On Mon, Jun 15, 2015 at 12:01 AM, =
Kristov Atlas <span dir=3D"ltr">&lt;<a href=3D"mailto:kristovatlas.lists@gm=
ail.com" target=3D"_blank">kristovatlas.lists@gmail.com</a>&gt;</span> wrot=
e:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-l=
eft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_e=
xtra"><div class=3D"gmail_quote"><span class=3D"">On Sun, Jun 14, 2015 at 7=
:02 PM, Gregory Maxwell <span dir=3D"ltr">&lt;<a href=3D"mailto:gmaxwell@gm=
ail.com" target=3D"_blank">gmaxwell@gmail.com</a>&gt;</span> wrote:<br><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
:1px solid rgb(204,204,204);padding-left:1ex">
I&#39;m not a great fan of this proposal for two reasons: The first is<br>
that the strict ordering requirements is incompatible with future<br>
soft-forks that may expose additional ordering constraints. Today we<br>
have _SINGLE, which as noted this interacts with poorly, but there<br>
have been other constraints proposed that this would also interact<br>
with poorly.<br></blockquote><div><br></div></span><div>I&#39;m not clear o=
n why this is a problem, so long as the canonical ordering BIP is *optional=
*. Unless there is a specific plan to soft fork a change that would break t=
he BIP and it is fairly imminent, I see this only as a reason not to integr=
ate it into isStandard().<br></div><span class=3D""><div>=C2=A0</div><block=
quote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex">

The second is that even absent consensus rules there may be invisible<br>
constraints in systems-- e.g. hardware wallets that sign top down, or<br>
future transaction covenants that have constraints about ordering,=C2=A0 or=
<br>
proof systems that use (yuck) midstate compression for efficiency. Right no=
w, with random ordering these applications are fairly<br>
indistinguishable from other random uses (since their imposed order<br>
could come about by chance) but if everyone else was ordered, even if<br>
wasn&#39;t enforced.. these would be highly distinguishable. Which would<br=
>
be unfortunate.</blockquote><div><br></div></span><div>Maybe they shouldn&#=
39;t be doing that. :-P<br>=C2=A0</div><span class=3D""><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">

I think perhaps the motivations here are understated. We have not seen<br>
any massive deployments of accidentally broken ordering that I&#39;m aware<=
br>
of-- and an implementation that got this wrong in a harmful way would<br>
likely make far more fatal mistakes (e.g. non random private keys).<br></bl=
ockquote><div><br></div></span><div>In my reading of various wallet client =
sources, it is common that wallet clients will use cryptographically weak s=
ources of randomness to sort outputs -- that is, the ones that actually bot=
her to randomly sort. I can hunt down some examples if this would substanti=
ally contribute to the discussion.<br><br></div><span class=3D""><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s=
olid rgb(204,204,204);padding-left:1ex">
As an alternative to this proposal the ordering can be privately<br>
derandomized in the same way DSA is, to avoid the need for an actual<br>
number source.=C2=A0 If getting the randomness right were really the only<b=
r>
motivation, I&#39;d suggest we propose a simple derandomized randomization<=
br>
algorithm--- e.g. take the order from (H(input ids||client secret)).<br></b=
lockquote><div><br></div></span><div>This sounds similar to an idea that Se=
rgio pitched to me privately, which was for wallets to have a private sorti=
ng key that they can use to sort inputs and outputs. However, I suspect tha=
t adding yet another key which will necessarily require special key rotatio=
n rules and maybe special backup procedures will mean that this standard wi=
ll not be widely adopted any time soon. Ideally, I&#39;d like to see someon=
e write a different BIP with the sorting key idea and let them compete in t=
he wallet client market rather than trying to anticipate what is best for a=
ll clients and distilling two good ideas into one artificially.<span class=
=3D"HOEnZb"><font color=3D"#888888"><br><br></font></span></div><span class=
=3D"HOEnZb"><font color=3D"#888888"><div>-Kristov<br></div></font></span></=
div><br></div></div>
</blockquote></div><br></div>

--001a11336ee0f8974005194ac261--