[Cryptography] Proof of Work is the worst way to do a BlockChain

[Ray Dillinger]

On 02/24/2018 09:22 PM, jamesd at echeque.com wrote:
> On 24/02/2018 12:02, Ray Dillinger wrote:
>> You can check the validity of any proposed transaction by downloading a
>> subset of the block chain rather than the whole thing.  You will need
>> something on the order of the fourth root of all blocks, per block that
>> a txIn being used in the transaction came from, to make sure that it
>> hasn't been spent since it was created.  

> OK. What is your design?  (I have a proof of stake mechanism cooking,
> which solves the miner problem)

It bloats the blocks a bit with additional hashes and lists of
invalidated txIns, but I think it's a net win.


Okay....  we are actually building successively expanding hypercube
Directed Acyclic Graphs, but for the sake of having a vocabulary to talk
about, we can say that we are building "books."  Except, in these books,
each "word" is a block of the block chain.

And the books get steadily larger, so that even a fairly large block
chain ought to fit in a fairly small number of books.

So, in book N, each line has N words, each column has N lines, each page
has N columns, and the book has N pages.  Book N+1 is larger, in each
dimension.  This could be done with more or fewer dimensions but I think
this ought to work fine.

The blocks are multiply linked to each other.  Each block contains the
hashes of the blocks:

immediately previous (previous to it in the same line),
at its same place in the previous line,
at its same place and line in the previous column,
at the same place, line, and column on the previous page,
at the same place, line, column, and page, in the previous book.



Spends cause invalidations of txIns.  Each invalidation is recorded at
the following blocks in the block chain:

In the block where the tx spending it occurs.

In the first block following the spend that has the same place in line
as the tx that created the txIn spent.

In the first block following the spend that has the same position in its
column as the tx that created the txIn spent.

In the first block following the spend that has the same position on its
page as the tx that created the txIn spent.

In the first block following the spend that has the same position in its
book as the tx that created the txIn spent.



Now, an example of how the structure is used:  Alice wants to make a
payment to Bob in the current block, block B.  She has a TxIn that was
created in block A.  In order to know that this payment is valid, Bob
wants to prove that Alice has not already used this txIn in a payment to
Carol in block C.  But Bob has no idea where in the block chain block C
is.   It's okay because he doesn't need to know.

Bob follows links back word-by-word along the current line (which wraps
around if he gets to the beginning) looking for block C until he gets to
the same place in line where the txIn was created.   If he hasn't found
it yet, he starts following links up line-by-line (wraps around to the
bottom, etc) looking for notice of invalidation until he gets to the
same line where the txIn was created.  If he still hasn't found it, he
starts following links back column-by-column until he gets to the same
column where the txIn was created.  If he still hasn't found it, he goes
back page-by-page, and if he reaches the same page in the current book
where the txIn was created, he can start linking back book by book,
checking one word in each book.  Along this path, he's going to hit
block A, where the txIn was created.  He probably won't actually hit
block C.  But if block C exists, he'll find notice that the txIn was
invalidated along this path.


And that's the "vanilla" structure.  There is a likely enhancement that
could be very useful, and an unlikely enhancement that might be worth it
if desperate.

Obviously there are rows of blocks that "point" at things where, in the
previous volume, there are no things.  All the stuff in book 11, column
11 that points at "the same place in book 10" has nothing to point to.
In the first place this is no problem because if there is nothing to
point to there is also no way you need to point there.  In the second
place these hashes are at known locations so they could be used for
other purposes (like an ancillary block containing a database of known
valid TxIns after each page, with a diff after each column - for example).


If you want parallel block formation, you're going to give up the direct
prior-to-successor linkage of word-to-word at the line level, instead
having linkages that skip over a few blocks going back along the chain.
Under parallel block formation, however, you would need a lot of
ancillary rules to keep transactions compatible with only blocks that
are otherwise doomed to conflict (published with the same block number
for example) so that they don't cause train wrecks by getting played
into other blocks.  You would also need to keep your validation code
aware that two blocks are not necessarily part of the same branch until
there is a successor with hash paths that lead through both back into
the rest of the structure. The stuff you have to keep track of to
accommodate parallel block formation is complex, and I wouldn't
recommend it unless it becomes necessary.

				Bear





-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180225/2183895b/attachment.sig>