Subject: Re: [bitcoin-dev] Storm: escrowed storage and messaging at L2/L3

From: ZmnSCPxj <[email-masked]>
Date: Wed, 21 Aug 2019 04:14:13 +0000

Good morning Maxim,

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

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 "source 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 deletes it, Alice must first compute a Merkle Tree of the data chunks and store the Merkle Tree root (a small 32-byte data).
And the probabilistic checkable proof has to include the Merkle Tree Path proofs of the selected *source* data chunks together with the source chunks.

Similar problems arise in the pay-for-data scheme proposed in Lightning:https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002035.html
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 requested:

> With this data Alice will be able to check with this zero-knowledge argument 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?
=============================================

Also, it seems to me that the encryption used must be an asymmetrical encryption.
That is, the encryption and decryption keys must be different, with the encryption key being a "public" key Bob can safely share with Alice and the decryption key being a "private" key that Bob can share only once it has acquired its funds.

An issue that arises is: while an HTLC is used to atomically transfer the decryption 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 key 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 equivalent 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 and the encryption key is the scalar times the generator then it would be possible to use 2p-ECDSA / Schnorr Scriptless Script to atomically pay for knowledge of the scalar / decryption key, while knowing the encryption key.
Instead of a hash of the decryption key, Bob sends the encryption key during setup and Alice and Bob use that in the pointlocked timelocked contract under Scriptless Script.

Transporting Storm Over Lightning
=================================

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 stake from Bob and the reward from Alice to be put into a single timebound HTLC) can only live inside a single LN channel and is not transportable across 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-enforced publication of combined HTLCs: https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-July/002055.html)

This is part of what makes LN difficult to work with multiple asset types due to HTLCs naturally forming premium-free American Call Options.
Avoiding premium-free American Call Options is possible by extracting the premium 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 points + scalars, by use of EC magic homomorphisms, though I lack the energy right now to go dig up the resources on lightning-dev.
But the storage provider can route a payment to Alice to serve as stake, which 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 intermediate nodes unaware.

Regards,
ZmnSCPxj