[dlc-dev] BLS and announcement free DLCs

[Lloyd Fournier]

Hey Ichiro,

Thanks for reading the paper and for the detailed question. My response
below.

On Fri, 14 Oct 2022 at 13:15, Ichiro Kuwahara <kuwahara at cryptogarage.co.jp>
wrote:

> Hi Lloyd, thank you for your interesting proposal,I really enjoyed reading
> the paper:)
>
>
> I have some suggestions for cut and choose techniques, please let me know
> your thoughts.
>
> The following is a quote from *the "Verifiable Witness Encryption." *chapter
> of the paper.
>
> *>If all these checks pass, Bob is guaranteed that there exists at least
> one well-formed BF ciphertext among those λ/2 not opened by Alice:meaning
> that it encrypts rk such that sk = rk+y for some k. Thus, when Olivia
> attests m, Bob can decrypt the k-th BF ciphertext to compute rk, extract y
> = sk −rk from it and then use it to get σ from the pre-signature σˆ
> following the adaptor signature scheme.*
>
> IIUC, the following extraction is possible only if the olivia attest m
> which is included in i ∈ [λ/2] not selected by Bob.
>
> * extract y = si −ri*
>
> If Olivia attests m which is included in j ∈ [λ/2] chosen by Bob, Bob
> can’t  extract y because he doesn't get sk(sym-cipher) from Alice.
>


I didn't understand the problem. The task of this section is to verifiably
encrypt a scalar to a particular value of m e.g. m = 0 or m = 1 or m =
"hello world". All the ciphertexts are allegedly encrypting the same value
to the revelation of a signature on that single value of m. Does this make
sense? It seems like you are thinking that multiple values of m are being
encrypted to on either side of the selection.

Cheers,

LL


> 2022年8月19日(金) 12:15 Lloyd Fournier via dlc-dev <dlc-dev at mailmanlists.org>:
>
>> Hi again,
>>
>> I've just made the benchmark repos for the paper public.
>>
>> Here's the one for the BLS:
>> https://github.com/LLFourn/dlc-verifiable-encryption-bls
>> Here's the one using a simpler non-pairng attestation scheme on
>> ristretto:
>> https://github.com/LLFourn/dlc-verifiable-encryption-non-pairing
>>
>> I don't think we used the ristretto one in the paper. What it shows is
>> how fast things could be with a non-pairing attestation but using the same
>> verifiable protocol. Of course, it is cheating a bit because it's using a
>> heavily optimised curve and implementation. On the other hand there is no
>> theoretical reason you couldn't have an oracle using a ristretto based
>> attestation scheme and encrypt secp256k1 scalars to the anticipation points
>> (other than it being bad taste).
>>
>> Let me know if there are any questions. Sorry in advance about the poor
>> quality of the code. It is strictly for benchmarking only. I hope to build
>> a more production ready API and implementation in the coming months.
>> Hopefully I'll be able to make the curves themselves generic so it just
>> handles the cut-and-choose verifiable encryption part of the thing and you
>> can BYO your own points/scalars.
>>
>> Cheers,
>>
>> LL
>>
>> On Fri, 12 Aug 2022 at 11:46, Lloyd Fournier <lloyd.fourn at gmail.com>
>> wrote:
>>
>>> I want to follow up on an idea.
>>> During our last call Nadav mentioned the "smart contracts unchained"
>>> idea https://zmnscpxj.github.io/bitcoin/unchained.html.
>>>
>>> This brings up an interesting point: if the users agree on the outcome
>>> of the outsourced smart contract they don't even need to contact the
>>> trusted service.
>>> The same thing is true here. In the BLS scheme in the cooperative case
>>> you would need zero requests to the oracle. This is great news for privacy.
>>>
>>> To take an example, consider that we have a CFD style contract on BXBT
>>> implemented using a WASM smart contract. When I want to settle the contract
>>> I can first visit bitmex.com/api, get the relevant HTTP response, run
>>> it through our WASM contract program locally and see what CET gets
>>> activated. I then send a request to my counterpary to do the same. If we
>>> agree we settle the contract without ever contacting the oracle at all.
>>> This changes the privacy assessment for the scheme very favorably. In the
>>> expected case the users now have perfect privacy from the oracle. Of course
>>> now the users will now contact bitmex.com/api themselves which leaks to
>>> bitmex that you are interested in BXBT at a certain time. This seems like a
>>> much better situation though. Requesting stuff from an API endpoint seems
>>> like a very innocus thing to do and does not imply you are doing any kind
>>> of contract (at least in this example many apps gather data from these
>>> APIs).
>>>
>>> This is really cool since it means the oracle cannot even ballpark how
>>> many people are using their service!
>>>
>>> LL
>>>
>>> PS the paper has been updated now: https://eprint.iacr.org/2022/499
>>>
>>> On Mon, 8 Aug 2022 at 15:36, Lloyd Fournier <lloyd.fourn at gmail.com>
>>> wrote:
>>>
>>>> Hi dlc-dev,
>>>>
>>>> As many of you know, we've been working on how to do DLCs with batch
>>>> cut-and-choose verifiable encryption as opposed to adaptor signatures[1].
>>>> The recent breakthrough we've had is to optimize the protocol sufficiently
>>>> to bring Bitcoin DLCs with a BLS signature oracle into the realm of
>>>> practicality. To ballpark the performance, to batch verifiably encrypt 2048
>>>> schnorr signatures to the attestation of one 2048 outcomes attested via the
>>>> revelation of 11 BLS signatures (one for each bit) takes around 2.57s on my
>>>> laptop (1.7s with pre-processing) with 30bit statistical security.
>>>>
>>>> There's a lot more to say on performance and a few optimizations left
>>>> to make but for the sake of argument let's call that "practical" or at
>>>> least close to it. One optimization I'll ask you to keep in mind is that I
>>>> think the protocol can get a roughly 50% speedup if the payout function is
>>>> monotone because you only need to do verifiable encryption for either the 1
>>>> or the 0 values (not both) in the bit decomposed attestation.
>>>>
>>>> What are the implications of BLS attestations being practical? The
>>>> obvious thing is that we'd be able to get rid of the nonces in the oracle
>>>> announcement because BLS signatures do not require randomness. Just by
>>>> knowing the oracle's public key you'd be able to create a DLC on any event
>>>> as long as you know the oracle will attest to it. Ok but so what? You'd
>>>> still have to query the oracle to see if and how they're going to attest to
>>>> that thing right? On the surface it seems like this wouldn't even save a
>>>> single HTTP query.
>>>>
>>>> It turns out that getting rid of the nonces has huge implications.
>>>> Consider a completely new kind of oracle that doesn't have announcements.
>>>> It just has a single HTTP POST endpoint: "/attest".
>>>> Let's say you want the oracle to attest to the price of BXBT on BitMEX
>>>> at 2022-08-03T12:00:00.000Z. In the POST body you'd send something like:
>>>>
>>>> {
>>>>     "input" : {
>>>>          "url":  "'
>>>> https://www.bitmex.com/api/v1/instrument/compositeIndex?symbol=.BXBT&startTime=2022-08-03T12:00:00.000Z
>>>> ",
>>>>          "kind" : "jq",
>>>>          "filter": ".[]|select(.timestamp ==
>>>> \"2022-08-03T12:00:00.000Z\")|select(.symbol == \".BXBT\")|.lastPrice >
>>>> 23000 | round",
>>>>     },
>>>>     "output" : {
>>>>         "kind" : "bit-decomposition",
>>>>         "n_bits" : 20
>>>>     }
>>>> }
>>>>
>>>> The oracle -- at the time of your request -- would go to bitmex.com/api
>>>> and fetch the JSON result and apply the jq filter to extract the desired
>>>> value. If you're playing at home this would output:
>>>>
>>>> $ curl -sSL '
>>>> https://www.bitmex.com/api/v1/instrument/compositeIndex?symbol=.BXBT&startTime=2022-08-03T12:00:00.000Z'
>>>> | jq '.[]|select(.timestamp == "2022-08-03T12:00:00.000Z")|select(.symbol
>>>> == ".BXBT")|.lastPrice | round'
>>>> 23409
>>>>
>>>> And so the oracle would -- on the spot -- generate 20 BLS signatures
>>>> for each of the 20 big-endian bits of 23409 i.e. 00000101101101110001.
>>>> Each BLS signature would be made over the request, the bit position and
>>>> the bit value. Having the request in there is key as it allows you to
>>>> anticipate the BLS signature for either bit value ahead of making the query.
>>>>
>>>> I believe this is a huge improvement over the current oracle model.
>>>> Let's look at how this would impact DLC developers and users.
>>>>
>>>> ### Oracles more powerful and much simpler
>>>>
>>>> The key thing to note is that in the above example the oracle doesn't
>>>> need to know about BitMEX, BXBT ahead of time. It can attest to anything on
>>>> the web. It could even attest to values in HTML pages using css selectors
>>>> etc.
>>>> Users could bet on literally any information that can be
>>>> authoritatively sourced on the web (don't do wikipedia!)
>>>>
>>>> The main objection to this might be that oracles shouldn't just take
>>>> whatever is on the web and attest to it: an oracle should be responsible
>>>> for the correctness of its attestations and not pass the blame to a website.
>>>> I don't think this makes sense because (1) grabbing stuff from the web
>>>> is what oracles are doing in practice. (2) There is no primary source for
>>>> BXBT (for example) other than that URL (3) there is no reason in the model
>>>> that users couldn't request the oracle gather data from multiple sources
>>>> and average them or check that at least 3 out of 5 agree etc (4) an oracle
>>>> oracle publishing their own authoritative outcomes for specific events
>>>> perfectly compatible with this model.
>>>>
>>>> The major benefit of this model for oracle implementation is that they
>>>> can be completely stateless. Those of you that run oracles will understand
>>>> what quality of life improvement this is. For users the main benefit is
>>>> application developers being able to add new things to bet on without an
>>>> oracle having to announce that event. I also like that the thing you are
>>>> betting on is completely unambiguous so you can do away with the "bounded
>>>> error" stuff in the current spec.
>>>>
>>>> ### Oracles can process the web data before attestation
>>>>
>>>> Imagine if instead of using jq as in the above example the oracle
>>>> allowed specifying a WASM binary to process the HTTP response(s).
>>>> User applications could then code powerful processing logic that would
>>>> output a bit array. Consider that:
>>>>
>>>> 1. The WASM program could process data from multiple sources and apply
>>>> totally custom logic before outputting the final value (thresholds,
>>>> averages etc)
>>>> 2. Rather than outputting an "outcome" value like 23409 (price of
>>>> bitcoin) in the example, the WASM could map this price directly to CET
>>>> values. So if you wanted to have 1024 different CETs for the range between
>>>> Bitcoin 10k <-> 100k the WASM could map the value 23409 and simply output
>>>> the interval. e.g. (23_409 - 10_000)/(100_000 - 10_000)/(1024 - 1)) ~ 152
>>>> and so the oracle would attest to 152 instead of 23_409. This would mean
>>>> that there's a 1-to-1 mapping between attestation and CET.
>>>> 3. The "payout" function for the processed outcome could always be made
>>>> monotone and therefore very simple to deal with (and the optimization I
>>>> mentioned at the start always applies).
>>>>
>>>> Point (1) is really important for Itchysat's[2] use case where it needs
>>>> to check that during the course of a DLC that the value never went above or
>>>> below a certain value in addition to getting the settlement value. Right
>>>> now (as I understand it) they create a new pre-signed transaction for every
>>>> minute that the contract is alive to enforce this. It'd be great to remove
>>>> this and let the oracle attest to a boolean based on whether the price went
>>>> below at any interval by checking all the values in the BitMEX API used
>>>> above.
>>>>
>>>> Point (2) would in my mind completely remove the need for the following
>>>> specification documents. The logic contained within them would be in the
>>>> domain of the WASM program that the oracle runs before outputting the
>>>> attestation which is agreed by both parties at the application layer.
>>>>
>>>> 1.
>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/PayoutCurve.md
>>>>
>>>> 2.
>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/NumericOutcome.md
>>>>
>>>> 3.
>>>> https://github.com/discreetlogcontracts/dlcspecs/blob/master/NumericOutcomeCompression.md
>>>>
>>>> There is a downside to this idea in that users are leaking the oracle
>>>> more information about their contract than in the present model. Right now
>>>> you are leaking at least the event but not what the combination of events
>>>> are being used and not how you are mapping the outcomes to payout
>>>> intervals. Leaking the payout intervals could be a bad mistake because if a
>>>> related transaction goes on chain you could check that the value in CET
>>>> output is divisible by the payput interval to attempt to link it. Three are
>>>> simple ways to obfuscate this linkage in practice (an exercise I'll leave
>>>> to the reader!). There might be others I haven't thought of.
>>>>
>>>> There is also a downside for oracles in that you have to attest to
>>>> things as an anonymous user demands. You would need to take care to protect
>>>> against DoS by not creating too many signatures and not letting the WASM
>>>> programs run too long. For reference a BLS signature takes around 1ms to
>>>> create on my laptop.
>>>>
>>>> ### BLS signatures can do non-interactive threshold attestation
>>>>
>>>> Our protocol [1] allows for doing t-of-n DLC protocol where the time
>>>> complexity is roughly linear in n (in fact sublinear). So with 2048 CETs it
>>>> takes 2.57s for one oracle but for a 5-out-of-10 it takes about 21s.
>>>> This part of the protocol is also compatible with non-BLS attestations.
>>>> However BLS allows for creating a threshold amongst committee members
>>>> non-interactively. That is, if 10 oracles agreed to form a group with a
>>>> threshold of 5 by generating their keys together using an interactive
>>>> protocol it would be possible to use this committee as a single oracle and
>>>> therefore not have any performance loss. Each oracle could also be used
>>>> individually with the same key but if five signatures were fetched from the
>>>> 10 oracles you could compute the signature from under the group's aggregate
>>>> key.
>>>> Technically this is possible with non-BLS schemes (i.e. FROST) but it
>>>> would require the 5 oracles to interact during the attestation so not
>>>> really practical in the same way.
>>>>
>>>> ---
>>>>
>>>> I am really excited about this but I'll leave the technical side there
>>>> for now. I feel that this is the right way to link the external world to
>>>> Bitcoin. Let me know what you think.
>>>>
>>>> Cheers,
>>>>
>>>> LL
>>>>
>>>> PS the code for the benchmarking isn't public rn because I couldn't
>>>> change the visibility because of 2FA issues. Will fix soon. Also the paper
>>>> at [1] is the the process of being updated to include the new performance
>>>> gains.
>>>>
>>>> [1]: https://eprint.iacr.org/2022/499
>>>> [2]: https://www.itchysats.network/
>>>>
>>>>
>> dlc-dev mailing list
>> dlc-dev at mailmanlists.org
>> https://mailmanlists.org/mailman/listinfo/dlc-dev
>>
>
>
> --
>
> ----------------------------------------------------------------------
> 桑原 一郎
> Ichiro Kuwahara
> Lead Researcher
> Crypto Garage, Inc.
>
> Mail:     kuwahara at cryptogarage.co.jp
> Tel:       +81-3-5656-2410
> Mobile: +81-70-7469-8774
> ----------------------------------------------------------------------
> Address: DG Bldg., 3-5-7 Ebisu Minami, Shibuya-ku,
>                Tokyo 150-0022, Japan
> Web:       https://cryptogarage.co.jp/
> ----------------------------------------------------------------------
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailmanlists.org/pipermail/dlc-dev/attachments/20221017/9b9476a2/attachment-0001.htm>