[dlc-dev] BLS and announcement free DLCs
Ichiro Kuwahara
kuwahara at cryptogarage.co.jp
Fri Oct 14 07:15:32 CEST 2022
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 think the following suggestions will solve this problem.
—------------------------—------------------------
—------------------------—------------------------
In addition to the encryption of ri (BF-cipher), Alice encrypts si(=y +ri)
in BF-cipher for the same identity (vk, m) as follows.
*Bolded* are my additional suggestions.
1.Commitment
Alice generates random integer ri and creates sym-cipher si=ri+y.
For all i, Alice computes Ri = g・ri.
At this point, Alice sends the λ-many BF-ciphers(encrypted ri and encrypted
si) , the λ-many Ri and the statement Y of adaptor sig to Bob.
2.Cut and choose
Bob randomly samples2 λ/2 pairs
• For all i ∈ [λ/2] not selected by Bob
-Alice sends sym-cipher si and the random coins used to encrypt si in
BF-cipher to Bob.
-Bob checks g・si =? g・ri + g・y
* -Bob recompute the BF ciphertext of si with random coins and verify it.*
• For all j ∈ [λ/2] chosen by Bob
-Alice exposes the corresponding values ri and the random coins used to
encrypt ri in BF-cipher to Bob.
-Bob recompute the BF ciphertext of ri with random coins and verify it.
3.Extraction
・In case m is included i∈ [λ/2] not selected by Bob
Bob decrypt the BF ciphertext to compute ri, extract y = si −ri from it
・In case m is included j∈ [λ/2] chosen by Bob.
Bob decrypts the 2 BF ciphertexts(encrypted ri and encrypted si) to compute
ri and si, extract y = si −ri
※Note that the random coins used to encrypt ri and si in BF-ciphers should
not be the same.
If the random coins are the same, y will be extracted as follows:
y=BFcipher(si) - BFcipher(ri)
—------------------------—------------------------
—------------------------—------------------------
Best,
Ichiro
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/20221014/c6dafb6b/attachment-0001.htm>
More information about the dlc-dev
mailing list