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
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id AD20B7A4
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 May 2017 20:43:48 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f44.google.com (mail-wm0-f44.google.com [74.125.82.44])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id AB8531AE
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 May 2017 20:43:47 +0000 (UTC)
Received: by mail-wm0-f44.google.com with SMTP id d127so42004928wmf.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 23 May 2017 13:43:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=NtTX/N+bBKmDRnQvHxJsqYlyG7kDz8Q1PtZAZqXQ4n4=;
b=fZoZD80ROfNu6kCPA+faWeBBH0HReqXu7yyhX8ElGPmuBpUTnr036eT+GaW9GJdx+5
e49YRVk/UKqjtNl4lFjOHDlN2CFhJV4bMa6LpRurNw0ralIW/mMohFZGpVizuJt/WiSB
NJu35f5Pkjt0zrKsf4k0Z2b2P/SVdN7TeU1djCOqLcVAA4glEgrBeYxKNoYDmw7q1hW5
4pG56Q3sUqoyT/5/Mx8uK9xVgoWEOc9V0msNZbxteJsTYTltQVQfpssNNO6vErYI8M0U
EHzBEP9veLleygf4DU6GcYwUFjooBHj0MIX1LBwTdHd23rH5JvnywDBsTCVe47z1EE1Y
IpEA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=NtTX/N+bBKmDRnQvHxJsqYlyG7kDz8Q1PtZAZqXQ4n4=;
b=LNsiwxQ47/whzC83ZUV9mt8uXGriGM6qadUnWVR/1PlBiPvmTjAANP65uXbuubq7r+
2I4UnJLbHK5KQTI2qt7WADjqL5LrDjJQKLMJtUuDHcCE+feySQvmtBZyDQ5S1vBwC1sd
uiwjH7oK3C/tRIYSIGXUzBAvFbhm67GFh8IkwZ/lW45F4kmTiR8iR2nrybJkGImaLtnI
yVpW390nNSE3/S8N3soKgI1g7ks+32tNoZreZVK32xNg415cIKY5u5F3PZNe8Ib6P4ql
N0r+ZJk7+Bg6oSKgGftAcy1zfooSmK524kaWSYiVdR+Y60QMaD/Jw90dgo2wOOAEE4M6
WZEQ==
X-Gm-Message-State: AODbwcDHSZEmW8OQwKvUAAispy4IwG1qRWLyNO9Z3K4WOF4KYly5KfOP
yFVIWRX4MuRF3281UxjKVEbngAl9Ug==
X-Received: by 10.80.152.112 with SMTP id h45mr13334228edb.103.1495572226336;
Tue, 23 May 2017 13:43:46 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.80.135.79 with HTTP; Tue, 23 May 2017 13:43:45 -0700 (PDT)
In-Reply-To: <8760gs2n7v.fsf@rustcorp.com.au>
References: <CAPg+sBgruEiXya6oFy6VpmR1KPDebjeGDtZZU+facZx5=L_a5w@mail.gmail.com>
<CT3GNfkLsQJyM0EmWXc3HBmnW1h2iptP0SohZnXZfZPffoVmcofD8fs_E3kV5PuFL0pQSQwwk_FyR-8-wdANf15NE8UElNWqcEcc5Ql3n8M=@protonmail.com>
<CAAS2fgTif+Y6VzFG+w7W+CY1+D_roCqGyy392qB2KcDPGpVeiw@mail.gmail.com>
<20170516110104.GA5564@fedora-23-dvm>
<CAPg+sBjJLbhj71Epv=Qfc8HgJhSreN6BOmLkDkvcEGvPwxDNbg@mail.gmail.com>
<CAAS2fgQKOKY6DEwY3ycMjysU5Xf2UUE+k=vg2ekkAMO7KG3Gsw@mail.gmail.com>
<8760gs2n7v.fsf@rustcorp.com.au>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 23 May 2017 13:43:45 -0700
Message-ID: <CAPg+sBgW7paof_rLunoDYJL_WXn7mYuHanuka8a_x0oE2LjwSQ@mail.gmail.com>
To: Rusty Russell <rusty@rustcorp.com.au>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, 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
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Rolling UTXO set hashes
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 May 2017 20:43:48 -0000
On Mon, May 22, 2017 at 9:47 PM, Rusty Russell <rusty@rustcorp.com.au> wrote:
> Gregory Maxwell via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> writes:
>> On Tue, May 16, 2017 at 6:17 PM, Pieter Wuille <pieter.wuille@gmail.com> wrote:
>>> just the first - and one that has very low costs and no normative
>>> datastructures at all.
>>
>> The serialization of the txout itself is normative, but very minimal.
>
> I do prefer the (2) approach, BTW, as it reuses existing primitives, but
> I know "simpler" means a different thing to mathier brains :)
Oh, I didn't mean it that way at all. (1) is simpler to get decent
performance out of. Implementing (1) using any language that has big
integer support or can link against GMP is likely going to be faster
than the fastest possible implementation of (2).
> Since it wasn't explicit in the proposal, I think the txout information
> placed in the hash here is worth discussing.
>
> I prefer a simple txid||outnumber[1], because it allows simple validation
> without knowing the UTXO set itself; even a lightweight node can assert
> that UTXOhash for block N+1 is valid if the UTXOhash for block N is
> valid (and vice versa!) given block N+1. And miners can't really use
> that even if they were to try not validating against UTXO (!) because
> they need to know input amounts for fees (which are becoming
> significant).
>
> If I want to hand you the complete validatable UTXO set, I need to hand
> you all the txs with any unspent output, and some bitfield to indicate
> which ones are unspent.
That seems to completely defeat the purpose... if I want to give you a
UTXO set, and prove its correctness wrt the hash you know... I need to
remember the full transactions those outputs came from?
> OTOH, if you serialize more (eg. ...||amount||scriptPubKey ?), then the UTXO
> set size needed to validate the utxohash is a little smaller: you need
> to send the txid, but not the tx nVersion, nLocktime or inputs. But in a
> SegWit world, that's actually *bigger* AFAICT.
That's an interesting idea, but I believe you're forgetting:
* The size of txin prevout/nsequence, which is typically larger than
txouts (even when excluding scriptSig/witness data).
* The size of spent txouts for transactions with unspent outputs left.
* The fact that you can deduplicate the txids for txn that have
multiple unspent outputs in the UTXO set serialization, even if that
txid is repeated in the rolling hash computation.
The construction I was considering and benchmarking is using 256-bit
truncated SHA512(256bit txid || 32bit voutindex || 1bit coinbase ||
31bit height || CTxOut output) as secp256k1 X coordinate, or as key to
seed a ChaCha20 PRNG whose outputs is the 3072-bit MuHash number. The
reason for using SHA512 is that it can process most UTXOs in a single
transformation (as opposed to SHA256 which will almost always need 2).
The reason for using ChaCha20 is that it's incredibly fast for
producing much data when a key is already known. An alternative is
using SHAKE256 for the whole construction (as it both takes an
arbitrary amount of data, and produces an arbitrary length hash) - but
it's a bit slower.
> Thanks,
> Rusty.
>
> [1] I think you could actually use txid^outnumber, and if that's not a
> curve point SHA256() again, etc. But I don't think that saves any
> real time, and may cause other issues.
That just seems scary to me...
--
Pieter
|
