summaryrefslogtreecommitdiff
path: root/04/cbcba94b11156d8e7c87d359d817a482fdd329
blob: 726fe01db445692da30f4aff6e1bc74ce5d9f9c7 (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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
Return-Path: <ethan.scruples@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 335F6919
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 28 Jul 2016 16:41:51 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-io0-f173.google.com (mail-io0-f173.google.com
	[209.85.223.173])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 699212AA
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 28 Jul 2016 16:41:50 +0000 (UTC)
Received: by mail-io0-f173.google.com with SMTP id 38so104909394iol.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 28 Jul 2016 09:41:50 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to; 
	bh=SziFRQVFydnm1NRGi6YT3CznUFXkLigg8Y95Xd0mU0E=;
	b=TgpueF+pvYDBG/YFky7kV4qgDc+uMM9dSyhjsgeTTfP5T84hd28z8Ar3VNe+X/zgTg
	ruhfEq9ksNltGK4ZzMuVDR+4atISo9GbO+grJ1RiQ4V6Q2mJYx/Zl0UQqI4lpUbMzWX1
	igZ0L9J2fpCDkNzAq+tc2I9au9Y+zxGmXbRr0GSuQHf16zE0smD+iS5chfeHIHjTBM0s
	9be+CqGzTvT17hmow/i1ESCoraj0h5NwwAYXgzG+fqNjScBJeJFvlPe/9dlRRVYuVkCy
	89YgAwuyPBZ4KTj0AzarnnYVAtxB7UYWsmtlg0l3bkh9dP5d4Ra9g8LDrso5fQEq24m+
	sKFg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to;
	bh=SziFRQVFydnm1NRGi6YT3CznUFXkLigg8Y95Xd0mU0E=;
	b=Yx3PsGkOBhxFjs1vZ47UVi3n3s84Cp7aJDMGrVrmyYaGuCH/lRF6l45SQQxeikZoVy
	bQe2F1n6rTAgLF9A+wZVJNfawA3JX7aL1Vve3/fUnJC1+M4vFCQ0SjKWru8ZjN8cg8xT
	ItydysbTZzMMaGW14jEraoWfywGBAWt3mhu7y+hZ9PPg+c8YjxLsaxw5gj27SwPDthg/
	v2SWJoTiqUsUE2gTNVxZXaKrgXUJp3+aYcy84D8/16d/b/hy3fUvMd+I4K2AUGnWGOnr
	MquWIi6ixa9ypDrFhAQH8VQ0Gead9cmUO8j7IMUJHum7MJLoE+pJ3HXufJFDIpf4L0Oi
	qjPQ==
X-Gm-Message-State: AEkoouv5jmgfO7yXEdonPnl8Ok1c5LcrWs1lLPd8Nn/1GuSkyP+suxfMs6kutTrkqwiWmck/fobGEQtbMSySWA==
X-Received: by 10.107.128.25 with SMTP id b25mr43195864iod.110.1469724109530; 
	Thu, 28 Jul 2016 09:41:49 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.50.80.15 with HTTP; Thu, 28 Jul 2016 09:41:48 -0700 (PDT)
In-Reply-To: <CACiOHGxpTEOzUBovuJstNEVQOpD+Yv0JivuyeOFsba_jhdyydw@mail.gmail.com>
References: <CACiOHGxpTEOzUBovuJstNEVQOpD+Yv0JivuyeOFsba_jhdyydw@mail.gmail.com>
From: Moral Agent <ethan.scruples@gmail.com>
Date: Thu, 28 Jul 2016 12:41:48 -0400
Message-ID: <CACiOHGx6+wW_6iShPvRQWHHXsrdSq7yv3_hxc0xcPzuqPUHuOA@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a113fb596776ec10538b4cf68
X-Spam-Status: No, score=-2.7 required=5.0 tests=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
X-Mailman-Approved-At: Thu, 28 Jul 2016 16:46:30 +0000
Subject: Re: [bitcoin-dev] Reasons to add sync flags to Bitcoin
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: Thu, 28 Jul 2016 16:41:51 -0000

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

If there is concern about the
block-with-valid-header-but-invalid-transactions-spam-attack, I have a
strategy using sync flags that may drastically reduce the problem.

Sync flags documented here:

https://github.com/moral-agent/sync_flags/blob/master/README.md)

The strategy to defeat the above attack is illustrated here:

https://s32.postimg.org/e94tqdqat/sync_flag_invalid_block.png

The key is to relax the requirement that a flag commit to a completely
valid block. The flag is valid if it commits to a valid block header, even
if the block body is invalid.

From the perspective of an individual miner, they can safely commence
mining a flag the moment they obtain (or discover) a valid block header.

As soon as the spam is discovered, miners can choose to either abandon the
flag and return to mining on the previous block, or they can continue
mining on the flag.

It's difficult for me to game out which of these strategies would be
preferable. My first thought is that the miners should have the incentive
to mine whichever option has the fewest miners, which should result in a
50/50 split.

However, the miners who continue mining the flag have a chance of ending up
in a situation where they mine the flag before anyone mines a valid block.
If this happens, it is sub-optimal for them. They can start mining for the
next valid block but if someone else broadcasts a valid block header they
will be in the same pickle that miners under the current protocol are: they
must either keep mining for a valid block, or SPV mine the newly arrived
block while they do validation. The third option, of mining a flag, is not
available to them, because the flag has already been mined for this cycle.

As a result of the above, it may be most rational for miners to (upon
learning that they are mining a flag on top of an invalid block) split
their hashpower unevenly between the flag and continuing to mine for a
valid block. The hashpower split reflects their estimates of the cost of
the above negative outcome. I think the split would be pretty close to
50/50, but deviations from 50/50 would not necessarily be bad. For example,
if they split 52/48, with more hashpower toward finding the valid block
instead of the flag, then that decreases the likelyhood that the flag will
be discovered before the next valid block, which is good for all of the
miners. So it's a nice positive feedback.

*****

This approach mostly neutralizes the harm done by the (currently very rare)
invalid block spam attack. As a kind of amazing side effect, the work done
to produce the spam is incorporated into the blockchain cumulative Proof of
Work, and the spammer is not paid for this contribution.

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

<div dir=3D"ltr"><div class=3D"gmail_extra">If there is concern about the b=
lock-with-valid-header-but-invalid-transactions-spam-attack, I have a strat=
egy using sync flags that may drastically reduce the problem.</div><div cla=
ss=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Sync flags document=
ed here:</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extr=
a"><a href=3D"https://github.com/moral-agent/sync_flags/blob/master/README.=
md">https://github.com/moral-agent/sync_flags/blob/master/README.md</a>)</d=
iv><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">The stra=
tegy to defeat the above attack is illustrated here:</div><div class=3D"gma=
il_extra"><br></div><div class=3D"gmail_extra"><a href=3D"https://s32.posti=
mg.org/e94tqdqat/sync_flag_invalid_block.png">https://s32.postimg.org/e94tq=
dqat/sync_flag_invalid_block.png</a><br></div><div class=3D"gmail_extra"><b=
r></div><div class=3D"gmail_extra">The key is to relax the requirement that=
 a flag commit to a completely valid block. The flag is valid if it commits=
 to a valid block header, even if the block body is invalid.</div><div clas=
s=3D"gmail_extra"><br></div><div class=3D"gmail_extra">From the perspective=
 of an individual miner, they can safely commence mining a flag the moment =
they obtain (or discover) a valid block header.</div><div class=3D"gmail_ex=
tra"><br></div><div class=3D"gmail_extra">As soon as the spam is discovered=
, miners can choose to either abandon the flag and return to mining on the =
previous block, or they can continue mining on the flag.</div><div class=3D=
"gmail_extra"><br></div><div class=3D"gmail_extra">It&#39;s difficult for m=
e to game out which of these strategies would be preferable. My first thoug=
ht is that the miners should have the incentive to mine whichever option ha=
s the fewest miners, which should result in a 50/50 split.</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra">However, the miners w=
ho continue mining the flag have a chance of ending up in a situation where=
 they mine the flag before anyone mines a valid block. If this happens, it =
is sub-optimal for them. They can start mining for the next valid block but=
 if someone else broadcasts a valid block header they will be in the same p=
ickle that miners under the current protocol are: they must either keep min=
ing for a valid block, or SPV mine the newly arrived block while they do va=
lidation. The third option, of mining a flag, is not available to them, bec=
ause the flag has already been mined for this cycle.</div><div class=3D"gma=
il_extra"><br></div><div class=3D"gmail_extra">As a result of the above, it=
 may be most rational for miners to (upon learning that they are mining a f=
lag on top of an invalid block) split their hashpower unevenly between the =
flag and continuing to mine for a valid block. The hashpower split reflects=
 their estimates of the cost of the above negative outcome. I think the spl=
it would be pretty close to 50/50, but deviations from 50/50 would not nece=
ssarily be bad. For example, if they split 52/48, with more hashpower towar=
d finding the valid block instead of the flag, then that decreases the like=
lyhood that the flag will be discovered before the next valid block, which =
is good for all of the miners. So it&#39;s a nice positive feedback.</div><=
div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">*****<br></d=
iv><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">This app=
roach mostly neutralizes the harm done by the (currently very rare) invalid=
 block spam attack. As a kind of amazing side effect, the work done to prod=
uce the spam is incorporated into the blockchain cumulative Proof of Work, =
and the spammer is not paid for this contribution.</div></div>

--001a113fb596776ec10538b4cf68--