|
| 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