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
|
Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
helo=mx.sourceforge.net)
by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <gcbd-bitcoin-development@m.gmane.org>)
id 1RrZgI-0005sR-MF for bitcoin-development@lists.sourceforge.net;
Sun, 29 Jan 2012 18:40:50 +0000
Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of m.gmane.org
designates 80.91.229.3 as permitted sender)
client-ip=80.91.229.3;
envelope-from=gcbd-bitcoin-development@m.gmane.org;
helo=plane.gmane.org;
Received: from plane.gmane.org ([80.91.229.3])
by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:AES256-SHA:256)
(Exim 4.76) id 1RrZgH-0003CC-Ey
for bitcoin-development@lists.sourceforge.net;
Sun, 29 Jan 2012 18:40:50 +0000
Received: from list by plane.gmane.org with local (Exim 4.69)
(envelope-from <gcbd-bitcoin-development@m.gmane.org>)
id 1RrZg6-0001RQ-5D for bitcoin-development@lists.sourceforge.net;
Sun, 29 Jan 2012 19:40:38 +0100
Received: from c-24-12-223-106.hsd1.il.comcast.net ([24.12.223.106])
by main.gmane.org with esmtp (Gmexim 0.1 (Debian))
id 1AlnuQ-0007hv-00 for <bitcoin-development@lists.sourceforge.net>;
Sun, 29 Jan 2012 19:40:38 +0100
Received: from tyrell.elden by c-24-12-223-106.hsd1.il.comcast.net with local
(Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00
for <bitcoin-development@lists.sourceforge.net>;
Sun, 29 Jan 2012 19:40:38 +0100
X-Injected-Via-Gmane: http://gmane.org/
To: bitcoin-development@lists.sourceforge.net
From: Elden Tyrell <tyrell.elden@gmail.com>
Date: Sun, 29 Jan 2012 12:40:23 -0600
Message-ID: <jg43qn$jbn$1@dough.gmane.org>
References: <CAE98tO0Nh=L2mSy-MzEW7o+0=Tzivw0zj8cG8e1EscmW0C0kBg@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
X-Complaints-To: usenet@dough.gmane.org
X-Gmane-NNTP-Posting-Host: c-24-12-223-106.hsd1.il.comcast.net
User-Agent: Unison/2.1.6
X-Spam-Score: -0.3 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(tyrell.elden[at]gmail.com)
-0.0 SPF_HELO_PASS SPF: HELO matches SPF record
0.0 DKIM_ADSP_CUSTOM_MED No valid author signature, adsp_override is
CUSTOM_MED
-0.0 T_RP_MATCHES_RCVD Envelope sender domain matches handover relay
domain
-0.0 SPF_PASS SPF: sender matches SPF record
1.2 NML_ADSP_CUSTOM_MED ADSP custom_med hit,
and not from a mailing list
X-Headers-End: 1RrZgH-0003CC-Ey
Subject: Re: [Bitcoin-development] [PROPOSAL] Merkle tree of unspent
transactions (MTUT),
for serverless thin clients and self-verifiable prunned blockchain.
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sun, 29 Jan 2012 18:40:50 -0000
On 2012-01-23 20:00:59 -0600, Alberto Torres said:
> This proposal describes how to add a hash-tree based check in the
> blockchain that allows to verify if a transaction is unspent without
> downloading and checking all the blockchain. The idea is not new, but
> at the time of this writing there isn't any technical description of
> how this should be done.
Thanks for writing this up (it's high time somebody did). I like your
acronym, but shouldn't it be "MTUO" since you spend *outputs* rather
than *transactions*? A transaction can have multiple outputs, some of
which are spent and others which aren't.
I've added a link to your proposal on the
https://en.bitcoin.it/wiki/Thin_Client_Security wiki page.
> Once 55% of blocks includes a valid MTUT hash in a 2-week timespan,
> they should reject any block with an invalid (i.e. probably malicious)
> MTUT hash block while accepting blocks without MTUT.
Just like OP_EVAL/p2sh, this creates the (small) risk of a blockchain split.
Unlike adding a new transaction type, here it's possible to eliminate
this risk: give each MTUT an additional "prev" pointer (hash of some
prior block) which points to the latest prior block with a correct
MTUT. This produces a "chain within the chain" of blocks that have
valid MTUTs. Hostile miners are free to add bogus-MTUT-blocks; those
bogus blocks will simply never be included in the "inner chain", just
like invalid blocks mined by hostile miners are never included in the
blockchain. By downloading the last day's worth of blocks (which is
not much data at all), a client can see which "inner chain" the
majority of the hashpower believed during the last 24 hours. This
eliminates the need for a vote in any specific block -- in effect you
get a "rolling election".
This "inner chain" approach can be broadened to a K-ary tree by
including K-many prior-block pointers. With one of these in every
block (and sensible choices) you wind up with
O(log_K(chain_length))-operation hash-secure access to arbitrary blocks
in the middle of the chain. This is an important building block for
ultra-high-security thin clients. Even if only a 1/K of the network's
hashpower starts adding these pointers the worst-case number of
operations needed to reach an arbitrary block will still converge
(though much more slowly) towards this ideal.
- e
|
