1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8222BED0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jan 2018 21:31:02 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua0-f193.google.com (mail-ua0-f193.google.com
[209.85.217.193])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1F6EDCA
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jan 2018 21:31:02 +0000 (UTC)
Received: by mail-ua0-f193.google.com with SMTP id i5so1362922uai.10
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 Jan 2018 13:31:02 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:sender:in-reply-to:references:from:date:message-id
:subject:to:cc;
bh=mAot3WNMUmPfV7843o1te2CrQgrYVgKzI3RO+iMNxQI=;
b=pmTtnJ4smnobKBf8u1TIcpEtnwyE/M9A9yA+kUCtA63s1GNNin8P2z4NDxUYOWmDnQ
C6lJyEdbV0GWH0hmzmY+3I6UNrVr8CSF/+ZwPNxwDxq6rdUIOk3jYnTDpa60pF/GlcmT
CH4Du+Dsr+W47qfeO8M9zwceeUT03uLyxfjbdfmLGBvc/me6RtPozurJ95h8MyLs0yX8
S90ap8/kPmWAFnxpw8nSLG4FBVOMtMIfs+/IotLZ0d0xoHxVqdWAe1gF1CAizHqaiWmi
A66+mnFGrQB2UeGH8fNf9bDg992nCazQaZCYG4L+GkwHLUiF6Gy5XEADqi2FSzB8pvIw
Mokg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
:date:message-id:subject:to:cc;
bh=mAot3WNMUmPfV7843o1te2CrQgrYVgKzI3RO+iMNxQI=;
b=JaaHzwnsnnvqgVYc6ZHKR+ague7Vwe1SwwMPfHKTnvJ83JTRmc2rSP+2on0gSUsPrV
zogQWtGaC5K1ys8hTZwQ9o2hpztHp68RyI9/F6jZTaHsPUVuIsxs4V8Nzcplb/kADiV3
WXlUZmYh15gZ5ZGjlxtqVOrqBDa0UEfU0mfah6ZM/wuK6a+kZzyoP5LUVqxpNLwcDuna
fCKSQiU7gaVnFBcBWbIf5q5EqqFmawQ6+9xbyNEnisLw0i9iD5SlYc2Q/zJhR98igG2g
RI7jxHS3u4EALdW0gsVUG7OZL5Rra1qiB+gmCVtf1OkGPLIznUR4weTtNnRtZdBcFGEl
zc0g==
X-Gm-Message-State: AKwxyteOKmJWxiSMs2Bz9zH8CEepFHyW8zCxZ879ztgQtJ2Bc9/wtuge
b/CxNlUKqjT4fSVNlHaJ/+LdY6yjMSp1jlGjGTk=
X-Google-Smtp-Source: AH8x226G1s5yaGEG/fRdlMDFAIRxVZisNUlg0Q2wCa/SrmX2no5hCR5WEh16wIMRayDceBiQotlycGD5EgEUsgulNoo=
X-Received: by 10.176.83.76 with SMTP id y12mr3367325uay.109.1516743060748;
Tue, 23 Jan 2018 13:31:00 -0800 (PST)
MIME-Version: 1.0
Sender: gmaxwell@gmail.com
Received: by 10.103.78.155 with HTTP; Tue, 23 Jan 2018 13:31:00 -0800 (PST)
In-Reply-To: <20180122200023.GA1055@savin.petertodd.org>
References: <M8yPGuNmrXfNNwrYDDLpTVb__BhGysVW060Cq_tMc-AC6F7pKd1Vvb4wWbpmhhEvfoQ7fn-EcgfxRwJSVkFAZ5x57hg9XxpdZlDPi2IBJZg=@protonmail.com>
<20180122200023.GA1055@savin.petertodd.org>
From: Gregory Maxwell <greg@xiph.org>
Date: Tue, 23 Jan 2018 21:31:00 +0000
X-Google-Sender-Auth: 3IRzODpEY4jlF2iTtgJl4XDrxNY
Message-ID: <CAAS2fgSJ=2GaX-fNRyZhwD=g6=v524hnD-dCqJicC-ak+La4PA@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Transaction Merging (bip125 relaxation)
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol 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: Tue, 23 Jan 2018 21:31:02 -0000
On Mon, Jan 22, 2018 at 8:00 PM, Peter Todd via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Most transactions don't have change?! Under what circumstance? For most
> use-cases the reverse is true: almost all all transactions have change, because
> it's rare for the inputs to exactly math the requested payment.
It's quite easy to get no change with a not-dumb algorithm selecting
coins if you have a decent number of outputs well under the value
you're paying.
The number of ways n choose m combines grows exponentially, and you
only need to get close enough over the right value so that you're
paying excess fees equal or less than the cost of the change (which
should include the current cost output itself as well as estimated
cost of the future signature to spend it).
Achow101 and Murch have code to implement an efficient algorithm for
finding these solutions for Bitcoin core which will hopefully get in
soon.
|