<div dir="auto"><div><br><div class="gmail_quote"><div dir="ltr">Den tis 30 jan. 2018 19:21 skrev Ray Dillinger <<a href="mailto:bear@sonic.net" target="_blank" rel="noreferrer">bear@sonic.net</a>>:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><br>
On 01/29/2018 07:08 PM, Alfie John wrote:<br>
> On Mon, Jan 29, 2018 at 05:20:51PM +0100, Natanael wrote:<br>
>> In terms of acyclic graphs, there exists no way to completely prove<br>
>> non-knowledge. You can only prove non-existence of conflicts within<br>
>> branches which you admit to knowing about, but since you can't be expected<br>
>> to know all branches it is likewise impossible to produce meaningful proofs<br>
>> of knowing there's no conflicting doublespend transaction.<br>
>> There's no well known / well defined domain / space of what dataset in<br>
>> which you would show non-existence.<br>
><br>
> This.<br>
><br>
> Looking for alternatives to Proof of Work, I bumped into Byteball and Stellar.<br>
> Reading both their whitepapers, I still didn't see how doulbespend was solved<br>
> as PoNK* wasn't addressed.<br>
><br>
> * Proof of Non-Knowledge is a great Litmus Test for future proposed solutions.<br>
><br>
>> At best you can have a challenge-response protocol where both parties show<br>
>> what branches they admit to knowing, and then a ZKP would be generated<br>
>> which cover those branches. This is only a complete proof if the given<br>
>> combined sets of branches is complete.<br>
><br>
> I like where this is going.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto"><span style="font-family:sans-serif">Posting this because I found it relevant;</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">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:</span><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif"><a href="https://eprint.iacr.org/2018/896" target="_blank" rel="noreferrer">https://eprint.iacr.org/2018/896</a><br></div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">> 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.</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">> 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.</div><div dir="auto" style="font-family:sans-serif"><br></div><div dir="auto" style="font-family:sans-serif">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. </div></div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div></div>