Date: Wed, 21 Aug 2019 04:14:13 +0000
To: Dr Maxim Orlovsky <orlovsky@protonmail.com>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <6o-9VFKLR0h4CUf_fUN1rAqwTTZMlxk2CwwHSbuuvesIapG8ySj4KyHyUmHRh8rf7Lc2urCX8vw7tmlkP60SfvS3VyWnauD25_E8psrcx7I=@protonmail.com>
In-Reply-To: <GJgJhEIXm9MyKb_3kGCd2RdvkVQGHjJIE_lCHtp5hQUt7lHvYl1lXTfgyGwwVC0w9LfeZBf86XEbU694V0EdDrB0HwXa7dMhxD7m5MSUI-g=@protonmail.com>
References: <GJgJhEIXm9MyKb_3kGCd2RdvkVQGHjJIE_lCHtp5hQUt7lHvYl1lXTfgyGwwVC0w9LfeZBf86XEbU694V0EdDrB0HwXa7dMhxD7m5MSUI-g=@protonmail.com>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Storm: escrowed storage and messaging at L2/L3
Precedence: list

Good morning Maxim,

Insufficient/unclear Description of Probabilistic Proof
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D

It seems to me that the probabilistic checkable proof, whose description I =
read naively, is not sufficient to prove the statement:

* The source data is the same as the source data originally stored by Alice=
.

When generating the proof, Bob can use the output of any PRNG as the "sourc=
e data".
If Alice only checks validity of this proof, then it will accept the output=
 of the PRNG as the actual stored data, which from what I understand is not=
 your goal.

The probabilistic checkable proof by itself just proves the statement:

* The encrypted data corresponds to the given plaintext.

So, before Alice sends its local copy of the data to Bob for storage and de=
letes it, Alice must first compute a Merkle Tree of the data chunks and sto=
re the Merkle Tree root (a small 32-byte data).
And the probabilistic checkable proof has to include the Merkle Tree Path p=
roofs of the selected *source* data chunks together with the source chunks.

Similar problems arise in the pay-for-data scheme proposed in Lightning:htt=
ps://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002035.htm=
l
The data provider is trusted to give actual data instead of the output of a=
 PRNG.

In the case of paid storage, Alice had access to the data originally stored=
 (presumably) and can keep a short "checksum" of the original data.

It might be that you imply this in your step 1 for Alice validation of the =
probabilistic checkable proof though it may be better clarified that Alice =
has to keep the Merkle Tree root for the original data it originally reques=
ted:

> With this data Alice will be able to check with this zero-knowledge argum=
ent by:
> 1. Checking Merkle tree paths leading to the chunks and resulting Merkle =
tree root hash to correspond to them

Will the Real Decryption Key Please Stand Up?
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Also, it seems to me that the encryption used must be an asymmetrical encry=
ption.
That is, the encryption and decryption keys must be different, with the enc=
ryption key being a "public" key Bob can safely share with Alice and the de=
cryption key being a "private" key that Bob can share only once it has acqu=
ired its funds.

An issue that arises is: while an HTLC is used to atomically transfer the d=
ecryption key in exchange for payment, what is the assurance given to Alice=
 that the hash of the decryption key is indeed the hash of the decryption k=
ey and not, say, the output of a PRNG?

That is, Bob must prove:

* The given hash h is the hash of the secret decryption key d whose equival=
ent encryption key is e

...while revealing only h and e to Alice.

If there exists some asymmetric encryption using EC (I know of no such, but=
 that is only due to my ignorance), where the decryption key is a scalar an=
d the encryption key is the scalar times the generator then it would be pos=
sible to use 2p-ECDSA / Schnorr Scriptless Script to atomically pay for kno=
wledge of the scalar / decryption key, while knowing the encryption key.
Instead of a hash of the decryption key, Bob sends the encryption key durin=
g setup and Alice and Bob use that in the pointlocked timelocked contract u=
nder Scriptless Script.

Transporting Storm Over Lightning
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D

Of note is that any mechanism that requires multiple participants to put up=
 money into a contract (as in the case of Storm, which requires both the st=
ake from Bob and the reward from Alice to be put into a single timebound HT=
LC) can only live inside a single LN channel and is not transportable acros=
s intermediate nodes.
This is because intermediate nodes potentially become subject to attack in =
case of routing failure.
(Though it *may* be possible to reuse the sketch I give here for HTLC-enfor=
ced publication of combined HTLCs: https://lists.linuxfoundation.org/piperm=
ail/lightning-dev/2019-July/002055.html)

This is part of what makes LN difficult to work with multiple asset types d=
ue to HTLCs naturally forming premium-free American Call Options.
Avoiding premium-free American Call Options is possible by extracting the p=
remium from the receiver and combining it with the money from the exchange,=
 but this again is doable only onchain, or in a single LN channel (meaning =
receivers must centralize around exchanges).

It may be possible to get around this, once Lightning supports payment poin=
ts + scalars, by use of EC magic homomorphisms, though I lack the energy ri=
ght now to go dig up the resources on lightning-dev.
But the storage provider can route a payment to Alice to serve as stake, wh=
ich can be claimed only if knowing some secret, then Alice routes the stake=
+reward to Bob, and use some of the EC magic homomorphism while keeping int=
ermediate nodes unaware.

Regards,
ZmnSCPxj