[Cryptography] DAG vs Blockchain

[Natanael]

Den tis 30 jan. 2018 19:21 skrev Ray Dillinger <bear at sonic.net>:

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

Posting this because I found it relevant;

Somebody just claimed to have a scheme for proving non-knowledge, in
limited settings. Unfortunately it doesn't seem applicable to this problem
domain, but nevertheless it's an interesting claim:

https://eprint.iacr.org/2018/896

> Intuitively, it seems impossible, since one can always pretend to be
ignorant. We explore the settings in which one could give a convincing
proof of ignorance.

> We are interested in the setting where a prover can generate an instance
x along with a corresponding proof of ignorance on her own. For example,
suppose there is a way for Alice to sample an instance x through a
“provably random process”. Then Alice can convince a verifier that she does
not know a witness for x (assuming the language is hard on average). In
some sense, a proof of ignorance is a proof that the instance x has been
generated correctly with “good” randomness.

This rather seems applicable to the type of schemes where one would use
nothing-up-my-sleeve numbers, or "trustless setup", and not something as
open and ambiguous as knowledge of branches. Unfortunately, that latter
class of problem might be impossible to solve.

>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20190110/f17e5cea/attachment.html>