Skip to content
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Commit 3adf515

Browse files
committedDec 5, 2014
New post.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
1 parent 2e2f3de commit 3adf515

File tree

1 file changed

+173
-0
lines changed

1 file changed

+173
-0
lines changed
 
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
---
2+
layout: post
3+
commentIssueId: 40
4+
---
5+
6+
One key problem with any system where you only need to know part of
7+
the blocks to contribute, is that you need to be sure that the
8+
information is available: that *someone* can tell you anything you need.
9+
10+
A miner who can hide a corrupt transaction in the blockchain can do a
11+
great deal of damage. If they convince other miners to build on top,
12+
they can out-compete them by revealing the flawed transaction once the
13+
other miners have wasted their time. Or they can include a
14+
transaction, then re-use the same inputs causing a follow-on miner to
15+
create a corrupt block; after confirmation time, they reveal it as a
16+
double-spend.
17+
18+
## Pettycoin's Solution ##
19+
20+
The miner has to know the contents of the last 1024 blocks, and
21+
demonstrates this knowledge by publishing an alternate hash (which
22+
incorporates its own payout address) for each shard of transactions:
23+
for block N-1, N-2, N-4, ... N-1024. It includes one byte of these
24+
hashes in the block header, which costs 40 bytes for the initial
25+
shardsize of 4.
26+
27+
The disadvantage: to prove that this byte is wrong, you need to
28+
publish all the transactions in the particular shard, which is quite
29+
large. This is somewhat helped by the
30+
255-transaction-per-shard-per-block limit.
31+
32+
## Gregory Maxwell's Server Solution ##
33+
34+
In IRC, Gregory Maxwell (@gmaxwell) suggested:
35+
36+
> [...] every block includes a host which promises to serve you the
37+
> data... if you're unable to get it elsewhere, you go get it from
38+
> there. If that host gets dos attacked, well too bad for them.
39+
40+
He suggested using a rateless erasure code to create a server which
41+
cannot hide a malformed transaction, and I've been working on
42+
simulating such a thing.
43+
44+
We assume the transaction data (transactions, plus proofs) has been
45+
batched into N regular elements of (say) 64 bytes.
46+
47+
### Simple Fountain Codes ###
48+
49+
A simple LT fountain code just XORs some random number of elements
50+
together and returns that. The "random number" is biassed to produce
51+
1 often enough to get decoding started, and from there you can work
52+
your way to decoding the pairs, then triples, etc.
53+
54+
A fountain code allows you to recover the entire data set with a few
55+
percent more fountain codes than the data set size; clearly, we don't
56+
want to send so much data with each query, otherwise we'd send the
57+
entire set.
58+
59+
## Example Using Simple Fountain Codes ##
60+
61+
The client supplies two numbers: an offset, and a seed for a PRNG.
62+
The server sends back the element at that offset, then uses the PRNG
63+
to determine another (say) 16 XORed elements. After a number of queries,
64+
all elements can be recovered.
65+
66+
## A Server Which Is Hiding Something ##
67+
68+
Of course, a server hiding something will simply refuse to respond to
69+
any transaction which reveals the flawed element. If it responds to
70+
less than 50% of the queries, it can be assumed that the majority
71+
the miners will regard the block as invalid, and their attack won't succeed.
72+
73+
Unfortunately, using simple fountain codes makes such cheating easy:
74+
any request which wouldn't XOR in the flawed transaction can be safely
75+
served without revealing it, so we need to design our protocol so that
76+
every response includes more than 50% of the elements.
77+
78+
## Modified Fountain Codes ##
79+
80+
Each request has log(N) responses; the first is the element at the
81+
given offset. Then two elements at psuedo-random offsets are XORed
82+
for the second response, four for the third, etc.
83+
84+
I wrote a server simulator which tracks what has been sent out,
85+
refuses to respond if doing so would reveal the randomly-chosen
86+
invalid response. With N=10,000 it starts failing to respond before
87+
5000 queries, as expected.
88+
89+
## A Lying Server ##
90+
91+
A server might actually include an invalid element, rather than lie.
92+
If the invalid element were the first response, that would be
93+
immediately obvious, so it be unable to respond in 1/N cases.
94+
Similarly for any case where other responses would reveal (by
95+
elimination) the inconsistency. A server would work best by lying in
96+
the last response, where half of the N elements are combined together.
97+
98+
Unfortunately, the PRNG makes it difficult to probe for such
99+
inconsistencies. You would identify it eventually, but to send that
100+
set of queries to other nodes would be a very large data transfer.
101+
The PRNG also makes it difficult to reason about finding
102+
inconsistencies.
103+
104+
## A Non-PRNG Response ##
105+
106+
Do we need the PRNG in this case? It seems not, as long as each
107+
response covers over half the elements, and the client chooses the
108+
offset. Assuming a response is still a sequence of XORed exponential
109+
numbers of elements, we just need to decide the algorithm used to
110+
select which elements are XORed. Ideally, we want a pattern where
111+
it's easy to generate overlapping responses to test for
112+
inconsistencies.
113+
114+
After playing with numerous sequences, an increasing distance sequence
115+
turned out to be a nice tradeoff, with offset increasing by 1 every
116+
time, eg. here are the XOR patterns for the first 4 responses for a
117+
query:
118+
119+
`1`
120+
` 22`
121+
` 33 3 3`
122+
` 44 4 4 4 4 4`
123+
...
124+
125+
This is Position(n) = (offset + 1 + (n - 1) * n / 2) % N.
126+
127+
It's fairly easy to generate sequences of queries which can be
128+
combined together to verify each other. In fact, any sequence of
129+
length N can be verified by one request which gets half the length,
130+
and then single requests for the others for (N/2)+1 query responses.
131+
Compare response 3 with response 4; a query at offset+1 will have
132+
response 3 overlap the first four elements of response 4 above.
133+
134+
## A Better Non-PRNG Response ##
135+
136+
If we include a "series offset" parameter (so) in the request, we can could
137+
directly request two parts of any response.
138+
139+
Position(n) = (offset + 1 + (n+so - 1) * (n+so) / 2) % N.
140+
141+
Eg, with so=4:
142+
` 1 1 1 1`
143+
144+
Given the correct offset parameter, this could be made to align with
145+
the second half of response 4.
146+
147+
## Bringing It All Together ##
148+
149+
Rather than rely on good behavior or random nodes doing audits, we
150+
should have miners include server responses which cover a random
151+
transaction in their coinbase: these would be chosen by H(prev-block |
152+
coinbase-outputs), so it would be different for each miner. There
153+
should be one of these for the previous block (a quick audit), and
154+
another for some older block (to allow propogation of any proofs there
155+
are problems).
156+
157+
The server can be outsourced by the miner, but would need to sign the
158+
responses (otherwise you can't complain if it lies to you). A miner
159+
wouldn't need to query the server if it knew enough to generate the
160+
response itself, but it should probably do so anyway, asynchronously,
161+
to keep the system honest.
162+
163+
## Summary ##
164+
165+
The Maxwell proposal is very different from current bitcoin. It would
166+
remove miners from having to know everything about the block they are
167+
mining (of course, someone would have to supply them with the UTXO
168+
proofs in that case). It still remains to be shown that there isn't a
169+
technique whereby over half the network can be mislead, using a
170+
combination of lying and omission.
171+
172+
Still, this is the only solution I am aware of which doesn't require
173+
full miner knowledge, and that's definite progress.

0 commit comments

Comments
 (0)
Please sign in to comment.