summaryrefslogtreecommitdiff
path: root/6f/f6f71a9a698ebf2c50d0c486ef4508e28d6257
blob: 7d8a414b9757766963cc53a918a144277f37226c (plain)
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
Return-Path: <peter_r@gmx.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 677A0279
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 30 Aug 2015 17:00:41 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mout.gmx.net (mout.gmx.net [212.227.15.18])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BCEDE1E8
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun, 30 Aug 2015 17:00:40 +0000 (UTC)
Received: from [192.168.50.29] ([69.50.179.106]) by mail.gmx.com (mrgmx002)
	with ESMTPSA (Nemesis) id 0LsCdj-1YZ9Hm3O6p-013t9W for
	<bitcoin-dev@lists.linuxfoundation.org>; Sun, 30 Aug 2015 19:00:38 +0200
From: Peter R <peter_r@gmx.com>
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047"
Message-Id: <32D6AD7B-5EA2-4FC3-AB5A-A43C7482F2F9@gmx.com>
Date: Sun, 30 Aug 2015 10:00:37 -0700
To: "bitcoin-dev@lists.linuxfoundation.org Dev"
	<bitcoin-dev@lists.linuxfoundation.org>
Mime-Version: 1.0 (Mac OS X Mail 6.6 \(1510\))
X-Mailer: Apple Mail (2.1510)
X-Provags-ID: V03:K0:Qpla54Uuo41qk6fC+5nWafemtyhpkr9osqKs02o1gBij4+qtnpf
	vJRs4LeWrZoWLJYjhglrtcfYJ7WFDMnYl3ilPnZD1dkrSG/wCJWwiKW9jaWjsBGEgs/teWk
	Uthuv2dXJg4nD6p4nq7QAq4j3PRYHqlOvqZc5PXlkettWFyPRYKzy7AtXCt371L80wxZlrv
	yK1UgCYCfk9uHPHPX39Ew==
X-UI-Out-Filterresults: notjunk:1;V01:K0:u7Skr1+o1rk=:O/CpxJRoVZgbIfXj4AOsse
	5A7ntw1JK9DAZvNYFiCRR1hYRiVsh2qUOWmZ2nJqJ2v/FaW0cYOBFlIb4U3+aGyrXvXjli9o5
	+2z0cTD8ZWe6SYkKMautPWWgRs2aEM8IoyOK2i1sG4n6lWgSlB18Os3DO2NfRz84cAIMiFBZt
	sYxr9xKIwCtNzSR9vjp8YEDbpMb2aHdKa5pvUS7sPxLnzuWKywkJV6YYty4dPj+Njy4gzS98C
	Bb6FmMnr7MlPOAtrG1pp6QQ76jz1vM9LQMaVD1yksXkyqJaK9xE2cMaQ4zWaD7ZsOBcq9VKG9
	t4+CEO6ly/cKDFJTtvdOKnGHBuYGcqp+CU5sm08SWuY8nKHlgePc6FGFCqW6/XmOoalrin5ri
	2Df/rKrxPK/Ehbx+fBiCOEI8olleeddXrh/tVdFtO3dZ4j8dfguy4xvtncFptta2qxANr0TCu
	Fm0xewtyDhedRfv4zCqEwoThNDo765h+DyGNPOLHJ1Msz3/YosQsnwr2uZZyKlkkzNlLXQeCd
	GB62tAv0Ho9LwiccJB9brmLzvxcdgeb2Os+bQL4fwC2OpZXnY1WDkfI99sMg2tZ3v5x2Rcf8n
	BLVzOX8HKi7685W7YCPtZFFfi/VFUasMll7SSRm5xXj8V0FaDZ4/YatxvdxvXPvR7wco+cQAC
	OU1TNypBraztF5z4g/+wclUWn9u7ZA4SAHSLoWCM8os07HHZqx6/85RXweefrUO2Gynhl55Mz
	pQs+1bMVGz0jmjRjJWwCETlqNlrpYH0WM6XCtc8zqb3JwA8zzIhw3HMwkyI7I+Dbzh/wpkt1F
	NxrtmLWKfkSP8mix5dzpm17s1pMWNV4XIvBALnFWkabfu7HTtw=
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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
Subject: [bitcoin-dev]  Unlimited Max Blocksize (reprise)
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: Sun, 30 Aug 2015 17:00:41 -0000


--Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

Hello Tom, Daniele --

Thank you Tom for pointing out the knapsack problem to all of us.  I =
will include a note about it when I make the other corrections to the =
Fee Market paper.

I agree with what Daniele said previously.  The other "non-greedy" =
solutions to the knapsack problem are most relevant when one is choosing =
from a smaller number of items where certain items have a size similar =
to the size of the knapsack itself.  For example, these other solutions =
would be useful if transactions were often 50 kB, 100 kB, 400 kB in =
size, and we were trying to find the optimal TX set to fit into a 1 MB =
block. =20

However, since the average transaction size is ~500 bytes, even with a =
block size limit of 1 MB, we are looking at up to 2000 transactions.  =
The quantization effects become small.  Rather than 22 triangles as =
shown in Fig. 3 (http://imgur.com/rWxZddg), there are hundreds or a few =
thousands, and we can reasonably approximate the discrete set of points =
as a continuous curve.  Like Daniele pointed out, the greedy algorithm =
assumed in the paper is asymptotically optimal in such a case.

Best regards,
Peter=

--Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=us-ascii

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html =
charset=3Dus-ascii"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hello =
Tom, Daniele --<div><br></div><div>Thank you Tom for pointing out the =
knapsack problem to all of us. &nbsp;I will include a note about it when =
I make the other corrections to the Fee Market =
paper.</div><div><br></div><div>I agree with what Daniele said =
previously. &nbsp;The other "non-greedy" solutions to the knapsack =
problem are most relevant when one is choosing from a smaller number of =
items where certain items have a size similar to the size of the =
knapsack itself. &nbsp;For example, these other solutions would be =
useful if transactions were often 50 kB, 100 kB, 400 kB in size, and we =
were trying to find the optimal TX set to fit into a 1 MB block. =
&nbsp;<div><br></div><div>However, since the average transaction size is =
~500 bytes, even with a block size limit of 1 MB, we are looking at up =
to 2000 transactions. &nbsp;The quantization effects become small. =
&nbsp;Rather than 22 triangles as shown in Fig. 3 (<a =
href=3D"http://imgur.com/rWxZddg">http://imgur.com/rWxZddg</a>), there =
are hundreds or a few thousands, and we can reasonably approximate the =
discrete set of points as a continuous curve. &nbsp;Like Daniele pointed =
out, the greedy algorithm assumed in the paper is asymptotically optimal =
in such a case.</div><div><br></div><div>Best =
regards,</div><div>Peter</div></div></body></html>=

--Apple-Mail=_765913D6-131B-4EA8-9579-2ABAD12D3047--