[Cryptography] DAG vs Blockchain

[Ray Dillinger]

On 01/29/2018 07:08 PM, Alfie John wrote:
> On Mon, Jan 29, 2018 at 05:20:51PM +0100, Natanael wrote:
>> In terms of acyclic graphs, there exists no way to completely prove
>> non-knowledge. You can only prove non-existence of conflicts within
>> branches which you admit to knowing about, but since you can't be expected
>> to know all branches it is likewise impossible to produce meaningful proofs
>> of knowing there's no conflicting doublespend transaction.
>> There's no well known / well defined domain / space of what dataset in
>> which you would show non-existence.
> 
> This.
> 
> Looking for alternatives to Proof of Work, I bumped into Byteball and Stellar.
> Reading both their whitepapers, I still didn't see how doulbespend was solved
> as PoNK* wasn't addressed.
> 
> * Proof of Non-Knowledge is a great Litmus Test for future proposed solutions.
> 
>> At best you can have a challenge-response protocol where both parties show
>> what branches they admit to knowing, and then a ZKP would be generated
>> which cover those branches. This is only a complete proof if the given
>> combined sets of branches is complete.
> 
> I like where this is going.

My thought had been more in the line of simple topology and duplication.
Each block would be part of a 'tree' with root at the genesis/root node,
and at each layer of the tree the blocks are linked together.

Each block would be required to re-record any transactions that had
occurred in the most recent "fringe", the leading N digits of any of
whose txIn IDs matched those of its own block ID (where N is the current
tree level).  Each block would also be permitted to record any new
transactions.

The idea being that in order to check the validity of a txIn, you
can jump links sideways to the branch where it would be re-recorded,
then rootward to the creating transaction's layer, then sideways again
to the block containing the creating transaction itself. If you haven't
found a payment spending that txIn, then it doesn't exist.

The completist will continue rootward from there to the genesis block.

This could result in some transactions being recorded many times.  But
it would guarantee a log2(blocks) path to check the validity of any
txIn, without creating any 'bottleneck' blocks or any blocks that give
anyone special motives to manipulate or control.


				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/20180130/6a939034/attachment.sig>