Date: Sat, 20 Apr 2019 04:45:19 +0000
To: Ruben Somsen <rsomsen@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <IbAS3IZpoD0wJKQvVekHDjHJL0R97CSGKwyy3ScU5yl2NIDSqBsmUJqvU_M7b0MRRu2u9aQXaof0zTs1OC562vkYu8LzV7vSDM6Pj5j55yI=@protonmail.com>
In-Reply-To: <CAPv7TjbbYkXf62ApadMgOLef-Z9xTU1HQy_f+L3vNVUfRhChrw@mail.gmail.com>
References: <CAPv7TjYspkc1M=TKmBK8k0Zy857=bR7jSTarRDCr_5m2ktYHDQ@mail.gmail.com>
	<xqVUmHu0RXeogboFL8ivsZywPQKEqLCsUZTV1NbsxNB4CYqrNqS8TpYsP8PJSowIGUeq8Nu1XPVd9N9Exg5Is11767ytI0Sq4lVp9MGdII4=@protonmail.com>
	<CAEM=y+WVQz5x916sjCjWVmeEbRp4NoTyryxSH7uKNTHYz+Sdnw@mail.gmail.com>
	<xNr214GpQ7_9duD4RV0j2nufLLMff4ipqPcZEAsDIsjLwWDan9UijTADW0iJ76pUuaXgYth_BHla-p6G3SOksaySbDZXKhQPLvIfLqo0JeA=@protonmail.com>
	<CAEM=y+V0tMYBBLJhePfGUzyFNXVe9hr0F3QrX9JYFrDg5N1qXg@mail.gmail.com>
	<SHsLdVIPZcn9yyZN9Hx3moQmWXY-2yC99tEsFllksV-66ZrJNMQfDr0qHK_rCZuBcEa8gIcnThkvgRDkU6BYQ_mxX7JxfI_uM6ndOF26ofk=@protonmail.com>
	<CAPv7TjYeuCA1WDHgEpkN1K8=NM88fw43HJeP5TeRE7q0Q+Chzg@mail.gmail.com>
	<EWP8Pzp8wS_Nh145H_g4w3yJaelXmm6UB12sa8MC2EsMbYFhm53C_kaOvjztksQpCNBBT0D0zuTbKHnEfEatlLKIa3whMlLZrihawZux1UY=@protonmail.com>
	<CAPv7TjbbYkXf62ApadMgOLef-Z9xTU1HQy_f+L3vNVUfRhChrw@mail.gmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Improving SPV security with PoW fraud proofs
Precedence: list

Good morning Ruben,

> Hi ZmnSCPxj,
>
> > There is no safe way to use UTXO sets without identifying who is tellin=
g you those sets are valid, or making it expensive to lie
> > The first option requires trust and is weaker than SPV, the second requ=
ires committing to a proof-of-work
>
> Olaoluwa Osuntokun's BIP157 manages to function without a commitment:
> "If the client receives conflicting filter headers from different
> peers for any block and filter type, it SHOULD interrogate them to
> determine which is faulty."
>
> I am wondering if the same logic can be applied to UTXO sets or the
> fraud proofs I just described.

UTXO sets can only be validated by actually running the entire blockchain, =
i.e. fullnoding.

What BIP157 does is summarize data that is within a block, thus validating =
them can be done simply by downloading the block in question.

UTXO sets summarize data in the entire blockchain, hence proper validation =
requires downloading the entire blockchain.
Thus it cannot be a comparison point.


> > This makes no sense
> > or you trust that every peer you have is not omitting the proof.
>
> It's the latter, you trust every peer you have is not omitting the
> proof. It requires one honest peer. The reason this is acceptable is
> because you're already making that assumption. If none of your peers
> are honest, you have no guarantee of hearing about the chain with the
> most PoW.

But peers can be set up to allow you to hear of all chains while denying yo=
u proof of the invalidity of some UTXO.
This is precisely the "data unavailability claim" that shot down the previo=
us fraud proofs (i.e. absence of proof is not proof of absence, and proof o=
f UTXO validity was defined by proof of absence of any intervening spend of=
 the UTXO).

Perhaps in combination with BIP157/158 it may be possible, if the filters c=
ontain UTXO spends and a BIP158 filter was committed to on-chain.
Then a proof of absence could be done by revealing all the BIP158 filters f=
rom the UTXO creation to the block being validated, as well as the blocks w=
hose BIP158 filters matched the UTXO and revealing that no, they actually d=
o not spend the UTXO.

--

Tangentially, we cannot just magically commit to anything on the blockchain=
.
Header blocks commit to block data and commit to some other header block.
All those header blocks and the block data need to be stored and transmitte=
d over the network somehow, even though they are "only" being committed to.
Thus, if you are adding new information to be committed, that may increase =
the resource usage of fullnodes.

So if UTXO set commitments, or utreexo commitments, or BIP158 filter digest=
s, etc. are committed to in the coinbase, they have to be stored somehow in=
 fullnodes the entire UUTXO set, or the actual utreexo structure, or the ac=
tual BIP158 filter, etc. at each block.
Otherwise it would be pointless to store those commitments since it would n=
ot be possible to somehow acquire the data being committed to after-the-fac=
t.

This is probably still better than BIP37 but we should still be aware the a=
dditional load on fullnodes.

Regards,
ZmnSCPxj