Re: [bitcoin-dev] Is BIP32's chain code needed?

2020-10-05 Thread Lloyd Fournier via bitcoin-dev
Hi Leonardo,

I can't tell you what the BIP32 author was thinking but if I put
myself in their shoes these are the reasons I might have done it this
way:

1. Use HMAC rather than normal SHA2 -- this is just best practice for
key derivation (even though I don't think it would make a difference
to security if you are strictly following the spec).
2. Use 512-bit rather than 256-bit -- Probably something to do with
(1) -- since I'm using an HMAC I've gotta put something as the key. I
don't want re-use the 256-bits for the secp256k1 secret key for this
since an integer mod q is not the same as 256 random bits (or I don't
want to have to make the argument in the design doc that it actually
is; plus what if someone starts using this for different curve and I'm
not around to tell them no). So I split the 512-bits and use the last
256bits as the key for the child derivation.

I don't think there is any fundamental flaw with what you suggest (I
am doing something similar for a project).  I guess the issues you
pointed out with the scheme were probably not on the author's mind. To
me they don't seem too severe but I haven't spent much time developing
wallets.

LL

On Wed, Sep 30, 2020 at 4:02 AM Leonardo Comandini via bitcoin-dev
 wrote:
>
> Hi all,
>
> BIP32 [1] says: "In order to prevent these from depending solely on the key
> itself, we extend both private and public keys first with an extra 256 bits of
> entropy. This extension, called the chain code...".
>
> My argument is that the chain code is not needed.
> To support such claim, I'll show a schematic of BIP32 operations to be 
> compared
> with an alternative proposal and discuss the differences.
>
> I have two main questions:
> - Is this claim false?
> - Has anyone shared this idea before?
>
> ## BIP32 schematic
>
> Let `G` be the secp256k1 generator.
> Let `i` be the child index.
> Let `(p, P=pG)` and `(p_i, P_i=p_iG)` be the parent and i-th child keypairs
> respectively.
> Let `c` and `c_i` be the corresponding chain codes.
> Let `h1, h2, h3, h4` be hash functions so that the formulae below match the
> definitions given in BIP32 [2].
> Define private and public child derivation as follow:
>
> p_i(p, c, i) = (i < 2^31)  p + h1(c, pG, i)
>(i >= 2^31) p + h2(c, p, i)
>
> c_i(p, c, i) = (i < 2^31)  h3(c, pG, i)
>(i >= 2^31) h4(c, p, i)
>
> P_i(P, c, i) = (i < 2^31)  P + h1(c, P, i)G
>(i >= 2^31) not possible
>
> c_i(P, c, i) = (i < 2^31)  h3(c, P, i)
>(i >= 2^31) not possible
>
> The above formula for unhardened public derivation resembles a pay-to-contract
> [3] scheme.
>
> ## Alternative proposal
>
> Let `h` be an adequately strong hash function which converts its output to
> integer.
> Consider the following derivation scheme:
>
> p_i(p, i) = (i < 2^31)  p + h(pG, i)
> (i >= 2^31) h(p, i)
>
> P_i(P, i) = (i < 2^31)  P + h(P, i)G
> (i >= 2^31) not possible
>
> Which is basically the above one without the chaincode.
>
> ## Considerations
>
> I claim that this has the same properties as BIP32 [4]:
> - The problem of finding `p` given `p_i, i` relies on brute-forcing `h` in the
>   same way the analogous problem relies on brute-forcing `h2` in BIP32.
> - The problem of determining whether `{p_i, i}_i=1..n` are derived from a 
> common
>   parent `p` relies on brute-forcing `h` in the same way the analogous problem
>   relies on brute-forcing `h2` in BIP32.
> - Given `i < 2^31, p_i, P`, an attacker can find `p`. This is analogous to
>   BIP32, where the parent extended pubkey is needed (`P, c`). One could argue
>   that `c` is never published on the blockchain, while `P` may be. On the 
> other
>   hand most wallets either use hardened derivation (so the attack does not 
> work)
>   or derive scriptpubkeys from keys at the same depth (so the parent key is
>   never published on the blockchain).
>   Anyway, if the parent public key is kept as secret as BIP32 extended keys 
> are,
>   then the situation is analogous to BIP32's.
>
> _If_ these claims are correct, the proposed derivation scheme has two main
> advantages:
>
> 1) Shorter backups for public and private derivable keys
>
> Backups are especially relevant for output descriptors. For instance, when 
> using
> a NofM multisig, each participant must backup M-1 exteneded public keys and 
> its
> extended private key, which can be included in an output descriptor. Using the
> proposed derivation reduces the backup size by `~M*32` bytes.
>
> 2) User-friendly backup for child keys
>
> Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They map
> 16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys are at 
> least
> 64(65) bytes (key and chain code), so they cannot be mapped back to a
> mnemonic.
>
> A common wallet setup is (`->` one-way derivation, `<->` two-way mapping):
>
> entropy (16-32 bytes) <-> user-friendly backup
>   -> BIP32 

Re: [bitcoin-dev] Taproot (and graftroot) complexity

2020-09-20 Thread Lloyd Fournier via bitcoin-dev
Hi Jay,

I don't think there's much of a difference in security or privacy.
The advice to avoid key-reuse remains the same and for the same reasons.

LL


On Sat, Sep 19, 2020 at 11:08 PM Jay Berg via bitcoin-dev
 wrote:
>
> Newb here..  don’t know if "in-reply-to" header is misbehaving.
>
> But this is the OP thread:
>
> [bitcoin-dev] Taproot (and graftroot) complexity
> Anthony Towns aj at erisian.com.au
> Mon Feb 10 00:20:11 UTC 2020
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017622.html
>
>  href="mailto:bitcoin-dev%40lists.linuxfoundation.org?Subject=Re:%20Re%3A%20%5Bbitcoin-dev%5D%20Taproot%20%28and%20graftroot%29%20complexity=%3C20200210002011.lelhcdmjejmoh6xv%40erisian.com.au%3E;
>  title="[bitcoin-dev] Taproot (and graftroot) complexity">aj at erisian.com.au
>  
>
> On 9/19/20, 5:35 AM, "bitcoin-dev on behalf of Jay Berg via bitcoin-dev" 
>  bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>
> > At the time you create a utxo, provided you don't reuse keys, all 
> taproot
> > spends are indistinguishable. At the time you spend a taproot utxo,
>
> does reusing keys act differently in taproot than with 
> Pay-to-PubKey-Hash? Or is it the same deal.. same pubkey creates same address?
>
> Question is: is the security/privacy implications worse when reusing 
> pubkeys with taproot?
>
> ty
> jay
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Revisiting squaredness tiebreaker for R point in BIP340

2020-08-13 Thread Lloyd Fournier via bitcoin-dev
Thanks for bringing this discovery up and a big thanks to Peter Dettman for
working on this.

I second what Nadav said. Removing pointless complexity is worth it even at
this stage. I also maintain a non-libsecp implementation of BIP340 etc.
Having two ways to convert an xonly to a point is a pain if you are trying
to maintain type safe apis. If there is no performance penalty (or even a
small one in the short term) to unifying xonly -> point conversion it's
worth it from my perspective.

LL

On Thu, Aug 13, 2020 at 6:29 AM Nadav Kohen via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello Pieter and all,
>
> I am one of the maintainers of Bitcoin-S[1] and I maintain our secp256k1
> bindings (via JNI) as well as our (inefficient) bouncy castle fallback
> implementations of all secp256k1 functionality we depend on including
> Schnorr signatures. In light of this new information that there is no real
> downside to using evenness as the nonce tie-breaker, I am personally very
> in favor of this change as it strictly simplifies things as well as making
> types consistent between nonces and persistent signing keys (I can get rid
> of our SchnorrNonce type :). An additional minor benefit not already
> mentioned is that in places in our codebase where deserialized data is just
> being passed around and not used, we currently require a computation to go
> from a (x-only) SchnorrNonce to an ECPublicKey whereas going from a
> SchnorrPublicKey simply requires pre-pending a 0x02 byte.
>
> I am likely not aware of the entire impact that changing the BIP at this
> stage would have but from my view (of having to update bindings and test
> vectors and my fallback implementation, as well as wanting to get a stable
> branch on secp256k1-zkp containing both ECDSA adaptor signatures and
> Schnorr signatures for use in Discreet Log Contracts), I think this change
> is totally worth it and it will only become harder to make this
> simplification in the future. The schnorrsig branch has not yet been merged
> into secp256k1 (and is nearing this stage I think) and so long as making
> this change doesn't set us back more than a month (which seems unlikely) I
> am personally in favor of making this change. Glad to hear other's thoughts
> on this of course but I figured I'd voice my support :)
>
> Best,
> Nadav
>
> [1] https://github.com/bitcoin-s/bitcoin-s/
>
>
>
> On Wed, Aug 12, 2020 at 2:04 PM Pieter Wuille via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello all,
>>
>> The current BIP340 draft[1] uses two different tiebreakers for conveying
>> the Y coordinate of points: for the R point inside signatures squaredness
>> is used, while for public keys evenness is used. Originally both used
>> squaredness, but it was changed[2] for public keys after observing this
>> results in additional complexity for compatibility with existing systems.
>>
>> The reason for choosing squaredness as tiebreaker was performance: in
>> non-batch signature validation, the recomputed R point must be verified to
>> have the correct sign, to guarantee consistency with batch validation.
>> Whether the Y coordinate is square can be computed directly in Jacobian
>> coordinates, while determining evenness requires a conversion to affine
>> coordinates first.
>>
>> This argument of course relies on the assumption that determining whether
>> the Y coordinate is square can be done more efficiently than a conversion
>> to affine coordinates. It appears now that this assumption is incorrect,
>> and the justification for picking the squaredness tiebreaking doesn't
>> really exist. As it comes with other trade-offs (it slows down signing, and
>> is a less conventional choice), it would seem that we should reconsider the
>> option of having the R point use the evenness tiebreaker (like public keys).
>>
>> It is late in the process, but I feel I owe this explanation so that at
>> least the possibility of changing can be discussed with all information. On
>> the upside, this was discovered in the context of looking into a cool
>> improvement to libsecp256k1[5], which makes things faster in general, but
>> specifically benefits the evenness variant.
>>
>>
>> # 1. What happened?
>>
>> Computing squaredness is done through the Jacobi symbol (same inventor,
>> but unrelated to Jacobian coordinates). Computing evenness requires
>> converting points to affine coordinates first, and that needs a modular
>> inverse. The assumption that Jacobi symbols are faster to compute than
>> inverses was based on:
>>
>> * A (possibly) mistaken belief about the theory: fast algorithms for both
>> Jacobi symbols and inverses are internally based on variants of the same
>> extended GCD algorithm[3]. Since an inverse needs to extract a full big
>> integer out of the transition steps made in the extgcd algorithm, while the
>> Jacobi symbol just extracts a single bit, it had seemed that any advances
>> applicable to one would be applicable to the 

Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-12 Thread Lloyd Fournier via bitcoin-dev
A quick correction to my post:

>
> Here's where the truly novel part comes in. Ruben solves this by extending
> the standard *TLC contract:
> 1. Bob redeem with secret
> 2. Alice refund after T1
> 3. Bob redeem without secret after T2
>
> This is actually:

1. Bob redeem with redeem secret
2. Alice refund after T1 with refund secret
3. Bob redeem without secret after T2

The fact that Alice reveals a secret when she refunds is crucial.

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] SAS: Succinct Atomic Swap

2020-05-12 Thread Lloyd Fournier via bitcoin-dev
Ruben,

In my opinion, this protocol is theoretical breakthrough as well as a
practical protocol. Well done! I want to try and distil the core abstract
ideas here as they appear to me. From my view, the protocol is a
combination of two existing ideas and one new one:

1. In atomic swaps you can make the refund transaction on one chain
dependent on the refund on the other using secret revelation. Thus only one
chain needs to have a timelock and the other refund can be conditioned on a
secret that is revealed when that first refund goes through. (This idea is
in the monero atomic swap [1]).
2. Secret revelations can be used to give unconstrained spending power to
one party. With an adaptor signature, rather than reveal a decryption key
for another signature, you can just make the decryption key your signing
key in the multisig so when you reveal it with the adaptor signautre the
other party gains full knowledge of the private key for the output and can
spend it arbitrarily. (this is just folklore and already what happens in
HTLCs -- though it looks like lightning people are about to get rid of the
unconstrained spend I think).

The combination of these two ideas is novel in itself. The problem with
idea (2) is that your unconstrained spending power over an output doesn't
matter much if there is a pre-signed refund transaction spending from it --
you still have to spend it before the refund becomes valid. But if you
bring in idea (1)  this problem goes away!
However, you are left with a new problem: What if the party with the
timelock never refunds? Then the funds are locked forever.

Here's where the truly novel part comes in. Ruben solves this by extending
the standard *TLC contract:
1. Bob redeem with secret
2. Alice refund after T1
3. Bob redeem without secret after T2

We might call this a "Forced Refund *TLC". Alice must claim the refund or
lose her money. This forces the refund secret revelation through
punishment. If Alice refuses to refund Bob gets the asset he wanted anyway!

The resulting protocol you get from applying these ideas is three
transactions. At the end, one party has their funds in a non HD key output
but if they want that they can just transfer it to an HD output in which
case you get four transactions again. Thus I consider this to be a strict
improvement over the four transaction protocol. Furthermore, one of the
chains does not need a timelock. This is remarkable as the four transaction
atomic swap is one of the most basic and most studied protocols. I
considered it to be kind of "perfect" in a way. It just goes to show that
this field is still very new and there are still things to discover in what
we think is the most well trodden ground.

I don't want to ignore that Ruben presents us with a two transaction
protocol. He made a nice video explaining it here:
https://www.youtube.com/watch?v=TlCxpdNScCA. It is harder to see the
elegance of the idea in the two tx protocol because it involves revocation
and relative timelocks etc. Actually, it is straightforward to naively
achieve a two tx atomic swap with payment channels:
1. Alice and Bob set up payment channels to each other on different chains
2. They atomic swap the balances of the channels off-chain using HTLCs
using the standard protocol.
3. Since one party exclusively owns the funds in each channel the party
with no funds simply reveals their key in the funding OP_CHECKMULTISIG to
the other
4. Both parties now watch the chain to see if the other tries to post a
commitment transactions.

The advantages that Ruben's two tx protocol has over this is that timelocks
and monitoring is only needed on one of the chains. This is nothing to
scoff at but for me the three tx protocol is the most elegant expression of
the idea and the two tx protocol is a more optimised version that might
make sense in some circumstances.

[1] https://github.com/h4sh3d/xmr-btc-atomic-swap/blob/master/README.md

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] On the scalability issues of onboarding millions of LN mobile clients

2020-05-05 Thread Lloyd Fournier via bitcoin-dev
On Tue, May 5, 2020 at 9:01 PM Luke Dashjr via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Tuesday 05 May 2020 10:17:37 Antoine Riard via bitcoin-dev wrote:
> > Trust-minimization of Bitcoin security model has always relied first and
> > above on running a full-node. This current paradigm may be shifted by LN
> > where fast, affordable, confidential, censorship-resistant payment
> services
> > may attract a lot of adoption without users running a full-node.
>
> No, it cannot be shifted. This would compromise Bitcoin itself, which for
> security depends on the assumption that a supermajority of the economy is
> verifying their incoming transactions using their own full node.
>

Hi Luke,

I have heard this claim made several times but have never understood the
argument behind it. The question I always have is: If I get scammed by not
verifying my incoming transactions properly how can this affect anyone
else? It's very unintuative.  I've been scammed several times in my life in
fiat currency transactions but as far as I could tell it never negatively
affected the currency overall!

The links you point and from what I've seen you say before refer to "miner
control" as the culprit. My only thought is that this is because a light
client could follow a dishonest majority of hash power chain. But this just
brings me back to the question. If, instead of BTC, I get a payment in some
miner scamcoin on their dishonest fork (but I think it's BTC because I'm
running a light client) that still seems to only to damage me. Where does
the side effect onto others on the network come from?

Cheers,

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Mitigating Differential Power Analysis in BIP-340

2020-03-25 Thread Lloyd Fournier via bitcoin-dev
Hi Pieter,

Thanks for the detailed response.


> /secret key/secret keyI'll try to summarize the discussion we had that led
> to this choice, but most of it is on
> https://github.com/sipa/bips/issues/195 if you want the details.


Ahh I can't believe I missed that github issue while searching. I guess I
started reading a paper on DPA and got carried away. I can see you got to
where I was and then went much further including some empirical analysis.
Nice. I agree with the conclusion that xor is more robust than just hashing
randomness in the same block as the secret key.


> Let me first try to address what I think you're overlooking: in a
> BIP32/Taproot like scenario, the private key that goes into the signing
> algorithm functions as *both* secret and known to the attacker. That is to
> say, there is a master secret s, and signing key x that goes into the hash
> is x=s+a (mod n) for some value a that the attacker knows, and can modify
> (he cannot control it directly, but he may be able to grind it to have a
> structure he likes). I believe that means that feeding x to a hash directly
> itself is already a problem, regardless of what else goes into the hash -
> interactions between bits inside the hash operation that all come from x
> itself can leak bit-level information of x.  XORing (or any other simple
> mix operation that does not expose bit-level information) into the private
> key before giving it to a hash function seems like it would address this.
>

This is an subtle point that I didn't cross my mind. My gut feeling is
there isn't even a computational argument to made that what I was
suggesting is secure against DPA in that setting. DPA seems to be a PITA. A
footnote in the BIP with a citation for DPA (the ed25519 one from the issue
is good) and a hint about why you should avoid hashing Bitcoin secret keys
altogether would be good. This brings us to the next point.

It also assumes that somehow the computation of x itself is immune from
> leaks (something you pointed out in a previous e-mail, I noticed).
>

>From my reading of the HMAC papers it seems you might be able to vary the
BIP32 child index derivation to do this attack. Just thinking about it now,
these attacks seem far fetched just because in order for it to be useful
you need to have physical access to the device and to be able to accurately
measure power consumption in high resolution (which I guess you can't do
from a typical USB bus from corrupted software). Then you also need to get
the user to do lots of signing or derivation with their device. I guess a
malicious cable with some way of exfiltrating power consumption could do it.


> I'm happy for any input you may have here. In particular, the recent
> discussions around the interactions between anti-covert channel protection,
> randomness, and the ability to spot check hardware devices may mean we
> should revise the advice to consider not adding randomness unless such a
> anti-covert channel scheme is used.
>

My only comment here is that there will end up being more than one way to
do it and I think what you and your collaborators have put forward is at a
local optimum of design (now that I understand it). Thanks and well done!
It won't be the right optimum for everyone. To me, it seems like a good
place to start. If you develop a decent nonce exfiltration protected
signing protocol later then I don't see why HW wallets wouldn't compete for
favour amongst the community by implementing and updating their devices to
conform to it.

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Mitigating Differential Power Analysis in BIP-340

2020-03-24 Thread Lloyd Fournier via bitcoin-dev
Hi List,

I felt this topic deserved it's own thread but it follows on from the
mailing list post [2] announcing a new PR [1] to change BIP-340 in several
ways, including adding random auxiliary data into the nonce
derivation function. Rather than hashing the randomness with the secret key
and message etc, the randomness is hashed then XOR'd (^) with the secret
key and the result is hashed like so to determine the secret nonce k:

(1) k = H_derive( sec_key ^ H_aux(rand) || pub_key_x || message)

The claim made in the mailing list post is that this is more secure against
"differential power analysis" (DPA) attacks than just doing the simpler and
more efficient:

(2) k = H_derive(sec_key || rand || pub_key_x || message)

The TL;DR here is that I don't think this is the case.

There was no citation for this claim, so I did some digging and found two
papers that seemed like they might be the origin of the idea [3,4] (I had
no idea about these attacks before). A relatively easy to understand
explanation of DPA attacks against is in [3]:

The fundamental principle behind all DPA attacks is that at some point in
> an algorithm’s execution, a function f exists that combines a fixed secret
> value with a variable which an attacker knows. An attacker can form
> hypotheses about the fixed secret value, and compute the corresponding
> output values of f by using an appropriate leakage model, such as the
> Hamming Distance model. The attacker can then use the acquired power
> consumption traces to verify her hypotheses, by partitioning the
> acquisitions or using Pearson’s correlation coefficient. These side-channel
> analysis attacks are aided by knowledge of details of the implementation
> under attack. Moreover, these attacks can be used to validate hypotheses
> about implementation details. In subsequent sections, these side-channel
> analysis attacks are referred to as DPA attacks.


For example, in the original BIP-340 proposal the nonce derivation was
vulnerable to DPA attacks as it was derived simply by doing
H_derive(sec_key || message). Since, the message is known to the attacker
and variable (even if it is not controller by her), the SHA256 compression
function run on (sec_key || message) may leak information about sec_key. It
is crucial to understand that just hashing sec_key before passing it into
the H_derive does *not* fix the problem. Although the attacker would be
unable to find sec_key directly, they could learn H(sec_key) and with that
know all the inputs into H_derive and therefore get the value of the secret
nonce k and from there extract the secret key from any signature made with
this nonce derivation algorithm.

The key thing I want to argue with this post is that there is no advantage
of (1) over (2) against DPA attacks, at least not given my understanding of
these papers. The way the attack in [3] works is by assuming that
operations in the compression function leak the "hamming distance" [5] (HD)
between the static secret thing that is being combined with the variable
public thing. In practice the attack involves many particulars about SHA256
but that is, at a high level, the right way to simplify it I think. The way
the paper suggests to fix the problem is to mask the secret data with
secret randomness before each sensitive operation and then strip off the
secret randomness afterwards. This seems to be the inspiration for the
structure of updated BIP-340 (1), however I don't believe that it provides
any extra protection over (2). My argument is as follows:

Claim A: If the randomness used during signing is kept secret from the
attacker then (2) is secure against DPA.

Since SHA256 has 64-byte blocks the hash H_derive(sec_key || rand ||
pub_key_x || message) will be split up into two 64 byte blocks, one
containing secret data (sec_key || rand) and the other containing data
known to the attacker (pub_key_x || message). The compression function will
run on (sec_key || rand) but DPA will be useless here because the
HD(sec_key, rand) will contain no information about sec_key since rand is
also secret. The output of the compression function on the first block will
be secret but *variable* so the intermediate hash state will not reveal
useful information when compressed with the second block.

Then I thought perhaps (1) is more robust in the case where the randomness
is known by the attacker (maybe the attacker can physically modify the
chipset to control the rng). We'd have to assume that the sec_key ^
H_aux(rand) isn't vulnerable to DPA (the LHS is under the control of the
attacker) to be true. Even under this assumption it turned out not to be
the case:

Claim B: If the randomness used during signing is known to the attacker,
then (1) is not secure against DPA.

In (1)  there are 96 bytes to be hashed and therefore two SHA256 blocks:
(H_aux(sec_key) ^ rand || pub_key_x) and (message). During the first
compression function call the attacker gets the HD of:
HD( sec_key ^ H_aux(rand),  pub_key_x)

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

2020-03-21 Thread Lloyd Fournier via bitcoin-dev
* To protect against differential power analysis, a different way of
> mixing in this randomness is used (masking the private key completely
> with randomness before continuing, rather than hashing them together,
> which is known in the literature to be vulnerable to DPA in some
> scenarios).
>

I think citation for this would improve the spec.

I haven't studied these attacks but it seems to me that every hardware
wallet would be vulnerable to them while doing key derivation. If the
attacker can get side channel information from hashes in nonce derivation
then they can surely get side channel information from hashes in HD key
derivation. It should actually be easier since the master seed is hashed
for anything the hardware device needs to do including signing.

is this the case?

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Hash function requirements for Taproot

2020-03-16 Thread Lloyd Fournier via bitcoin-dev
On Fri, Mar 13, 2020 at 4:04 AM Tim Ruffing  wrote:
>
> I mean, the good thing is that there's a general method to defend
> against this, namely always adding a Merkle root on top. Maybe it's
> useful to make the warning here a litte bit more drastic:
>
https://github.com/sipa/bips/blob/bip-taproot/bip-0341.mediawiki#cite_ref-22-0
> Maybe we could actually mention this in BIP340, too, when we talk about
> key generation,

I missed this note in the BIP. This trick means you get property 2  (covert
taproot) for free if you prove property 3 (second covert taproot). This is
a big improvement as property 2 was dependent on the particulars of the key
generation scheme whereas property 3 is just based on Taproot being a
secure commitment scheme. Nice!

> I agree that modeling it as a commitment scheme is more natural. But I
> think an optimal model would capture both worlds, and would give the
> attacker signing oracles for the inner and the outer key, and an
> commitment opening oracle That is, it would capture that
>  * the ability to obtain signatures for the inner key does not help you
>to forge for the outer key
>  * the ability to obtain signatures for the outer key does not help you
>to open the commitment, and --- if already opened --- do not help
>you to forge for the inner key
>  * the ability to obtain an opening does not help you to forge for
>either key...
>  * etc
>
> I believe that all these properties hold, and I believe this even
> without a formal proof.
>
>
> Still, it would be great to have one. The problem here is really that
> things get complex so quickly. For example, how do you model key
> generation in the game(s) that I sketched above? The traditional way or
> with MuSig. The reality is that we want to have everything combined:
>  * BIP32
>  * MuSig (and variants of it)
>  * Taproot (with scripts that refer to the inner key)
>  * sign-to-contract stuff (e.g., to prevent covert channels with
>hardware wallets)
>  * scriptless scrips
>  * blind signatures
>  * threshold signtures
>  * whatever you can imagine on top of this
>
> It's very cumbersome to come up with a formal model that includes all
> of this. One common approach to protocols that are getting too complex
> is to switch to simpler models, e.g., symbolic models/Dolev-Yao models
> but that's hard here given that we don't have clear layering. Things
> would be easier to analyze if Taproot was really  just a commitment to
> a verification key. But it's more, it's something that's both a
> verification and a commitment. Taproot interferes with Schnorr
> signatures on an algebraic level (not at all black-box), and that's
> actually the reason why it's so powerful and efficient. The same is
> true for almost everything in the list above, and this puts Taproot
> outside the scope of proof assistants for cryptographic protocols that
> work on a symbolic level of abstraction. I really wonder how we can
> handle this better. This would improve our understanding of the
> interplay between various crypto components better, and make it easier
> to judge future proposals on all levels, from consensus changes to new
> multi-signature protocols, etc.
>

I hope we can prove these things in a more modular way without creating a
hybrid scheme with multiple oracles. My hope is that you can prove that any
secure key generation method will be secure once Taproot is applied to it
if it is a secure commitment scheme. This was difficult before I knew about
the empty commitment trick! Although the Taprooted key and the internal key
are algebraically related, the security requirements on the two primitives
(the group and the hash function) are nicely separated. Intuitively,
1. being able to  break the Taproot hash function (e.g. find pre-images)
does not help you forge signatures on any external key; it can only help
you forge fake commitment openings (for the sake of this point assume that
Schnorr uses an unrelated hash function for the challenge).
2. being able solve discrete logarithms doesn't help you break Taproot; it
just helps you forge signatures.

I believe we can formally prove these two points and therefore dismiss the
need for any signing or commitment opening oracles in any security notion
of Taproot:

1. We can dismiss the idea of an adversary that uses a commitment opening
oracle to forge a signature because the commitment opening is not even an
input into the signing algorithm. Therefore it is information theoretically
impossible to learn anything about forging a signature from a Taproot
opening.
2. I think we can dismiss the idea of an adversary that uses a signing
oracle to forge a fake Taproot opening. To see this note that the Taproot
Forge reduction to RPP in my poster actually still holds if the adversary
is given the secret key x (with a few other modifications). In the proof I
kept it hidden just because that seemed more realistic. If we give the
adversary the secret key we can dismiss the idea that a signing 

Re: [bitcoin-dev] Schnorr sigs vs pairing sigs

2020-03-06 Thread Lloyd Fournier via bitcoin-dev
Hi Erik,

There are a strong arguments for and against pairing based sigs in Bitcoin.
One very strong argument in favour over non-deterministic signatures like
Schnorr over BLS is it enables a kind of signature encryption called
"adaptor signatures". This construction is key to many exciting up and
coming layer 2 protocols and isn't possible unless the signature scheme
uses randomness.

self plug: I have a paper on this topic called "One-Time Verifiably
Encrypted Signatures A.K.A Adaptor Signatures"
 https://github.com/LLFourn/one-time-VES/blob/master/main.pdf

LL


On Fri, Mar 6, 2020 at 6:03 AM Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Schnorr sigs rely so heavily on the masking provided by a random
> nonce.   There are so many easy ways to introduce bias (hash + modulo,
> for example).
>
> Even 2 bits of bias can result in serious attacks:
>
> https://ecc2017.cs.ru.nl/slides/ecc2017-tibouchi.pdf
>
> Maybe pairing based sigs  - which are slower - might be both more
> flexible, and better suited to secure implemetnations?
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Hash function requirements for Taproot

2020-03-05 Thread Lloyd Fournier via bitcoin-dev
> I am uncertain what you mean here by "coin-tossing".
> From the comparison to MuSig, I imagine it is an interactive key
generation protocol like this:

> * Everybody generates fresh keypairs.
> * Everybody sends the hash of their pubkey to everyone else.
> * After receiving a hash of pubkey from everyone else, everybody sends
their pubkey to everyone else.
> * They add all their pubkeys to generate the aggregate key (and if using
Taproot, use it as the internal key).

> Is that correct?

Yes exactly. The reason it's called coin tossing is that the resulting key
is guaranteed to be uniformly random (in the random oracle model at least),
so it's like tossing a fair 2^256 sided coin. This is not true in MuSig for
example, where the aggregate key is not guaranteed to be from a uniform
distribution against a malicious party (but still secure as an aggregate
key).

> However, it can generally be pointed out that, before you put anything
into an n-of-n, you would damn well sure want to have *some* assurance that
you can get it out later. So in general you would need coordination and
interaction anyway to arrange getting into an n-of-n in the first place.

Right. Taking your example of a lightning channel, when you set it up I
don't *think* there is a way to use the non-interactivity of MuSig to
remove any rounds of communication to get to the starting state where there
is a channel funding on-chain and both parties have a tx that spends from
it which returns their funds. Doing coin tossing for the aggregate key as
well as the aggregate nonce shouldn't lead to any extra rounds of
communication. The downside of coin tossing is that it requires honest
parties to sample their keys non-deterministically (or at least have a
counter to avoid using the same key twice).

> On the other hand, it would be best to have at least some minimum of
privacy by always interacting over Tor and having a Tor .onion address,
which has absolutely horrid latency because human beings cry when peeling
onions.
> So in general reducing the latency by reducing communication rounds is
better in general.
> Counter to this, assuming you use an n-of-n in an offchain protocol of
some sort, the number of communication rounds to generate the aggregate key
may be dwarfed by the total number of communication rounds to create
signatures to update the offchain protocol.
> Counter counter to this is that one plan for reducing communications
rounds for creating signatures during offchain operation is to (haha) use a
Taproot with an n-of-n internal key and a tapscript that has n
`OP_CHECKSIG` operations, so that for normal operation you just toss
individual signatures at each other but at termination of the offchain
protocol you can do the heavy MuSig-style signing with the n-of-n aggregate
key.

Counter³ to this is that, in the case of lightning, the aggregate key for a
PTLC does not need to be chosen at payment time.  They channel members
could simply use the "master" aggregate key they generated by coin tossing
at the channel's inception and pseudorandomly randomise it every time they
need a new joint key (so the keys do not look related to everyone else on
the chain but you would effectively just be reusing the same public key).

Having said that if there is some advantage to using MuSig in some
particular case I wouldn't hesitate to use it in combination with Taproot.
I don't think the new assumption that I think you have to make wrt to the
hash function really weighs up against most design considerations. In
general, it is probably worth considering whether your protocol actually
benefits from the non-interactivity MuSig gives in the key generation
stage. If it doesn't due to the fact that it doesn't make signing anymore
non-interactive, then coin tossing might be the answer.

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


[bitcoin-dev] Hash function requirements for Taproot

2020-03-04 Thread Lloyd Fournier via bitcoin-dev
Hi List,

I recently presented a poster at the Financial Cryptography conference
'2020 which you can find here:
https://github.com/LLFourn/taproot-ggm/blob/master/main.pdf.  It attempts
to show the security requirements for the tweak hash function in Taproot.
In this post I'll give a long description of it but first let me tl;dr:

Taproot requires no new assumptions of SHA256 over what are already made by
Schnorr signatures themselves with one exception: when using a
non-interactive key generation protocol to produce a Taproot internal key
(e.g MuSig). To prove security in this scenario we need a make an
additional assumption about SHA256: as well as being collision resistant
(i.e. find two hashes h_1 - h_2 = 0), it must satisfy a more general kind
of collision resistance where it is hard to find h_1 - h_2 = d for *any d*
when the adversary is challenged to find h_1 and h_2 with random prefixes.
This is obviously a plausible assumption. Put informally, it says that zero
is not a special case where finding collisions is difficult but rather
solving the 2-sum problem is hard for all values of d (when challenged with
random prefixes).

Now the long version.

My motivation for creating this poster came from questions I had after
discussions in Taproot Study Group #18 (this study group initiative was a
great idea btw). The main question I had was "Why is Taproot binding?" i.e.
why is it true that I can only commit to one Merkle root. Isn't it possible
that a malicious party could produce a second covert Taproot spend that
none of the other parties to the output agreed to? I submitted a poster
proposal to FC to force myself to get to the bottom of it.

The premise of the poster is to use the Generic Group Model to try and
figure out how the hash function would have to fail for Taproot to be
insecure. Most of the poster is taken up cartoon reductions I made to
remind myself as to why what I was saying might be true. They are
incomplete and difficult to parse on their own so hopefully this post is a
useful companion to them.

=== The Security of Taproot ===

There are three scenarios/games we must consider when asking whether
Taproot is secure in the context of Bitcoin:

1. Taproot Forge: Forging taproot spends must be hard. The adversary must
not be able to take a public key off the blockchain and produce a forged
Taproot spend from it.
2. Covert Taproot: When an adversary is executing a multi-party key
generation protocol (e.g. MuSig) it should be hard for them to produce a
covert malicious Taproot spend from the joint key  i.e. when honest parties
think there is no Taproot on a key there shouldn't be any Taproot on the
key. Note this is not guaranteed to be hard by 1 being hard.
3. Second Covert Taproot: Like 2, except that if honest parties agree to a
Taproot spend then the adversary shouldn't be able to generate a second
Taproot spend they are unaware of.

Properties (1) and (2) can be argued succinctly if we just prove that
Taproot is a secure commitment scheme. It should be clear that if a Taproot
external key T = X + H(X||m)*G is a secure commitment scheme (Hiding and
Binding) to any arbitrary message m, then it is a secure commitment scheme
to a Merkle root. If so, then properties (1) and (3) hold. (1) holds
because if you can create an opening to a commitment not generated by you,
you either broke hiding (if your opening is the same as the honest one) or
broke binding (if it's different). (3) holds because you must have broken
binding as there are now two openings to the same commitment.

Property (2) is more difficult to argue as it depends on the multi-party
key generation protocol. Case in point: Taproot is completely broken when
combined with a proof of knowledge key generation protocol where along with
their public keys each party provides a proof of knowledge of the secret
key. Where X_1 is the key of the honest party, the malicious party can
choose their key X_2 to be G*H(X_1 || m) where m is a malicious Merkle
root. Clearly the malicious party has a covert Taproot for X = X_1 + X_2
and can produce a proof of knowledge for X_2.

Given this definition of security, we now move onto how we should model the
problem to prove they hold.

=== Generic Group Model vs Random Oracle Model ===

For practical cryptographic schemes you often have to idealise one of its
components to prove it secure. The most popular candidate for idealisation
is the hash function in the Random Oracle Model (ROM), which idealises a
hash function as a "random oracle", a black box which spits out random
values for each input. For example, the original "forking lemma" proof by
Pointcheval and Stern [1] shows the Schnorr signature scheme is unforgeable
in this model if the discrete logarithm problem is hard. In other words,
idealising the hash function allows us to isolate what security assumptions
we are making about the group (e.g. the discrete logarithm problem being
hard in it).

But what if we want to know what assumptions we 

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

2020-02-26 Thread Lloyd Fournier via bitcoin-dev
> Correct, except that the speedup from is_even(y) over
is_quadratic_residue(y) affects signing and not keypair generation.

Isn't this the same thing since in the spec it generates the public key in
the signing algorithm? If you pre-generate public key and pass it in there
would be no speedup to signing that I can see.

> It's not clear why removing these features from the spec would be an
improvement.

It could just be me but "here's the most minimal signing algorithm, you can
add things in these ways to make it more robust  in some settings" is more
intuitive than "here's the most robust signing algorithm, you can remove
these things in these ways if they don't apply to your setting". I see your
point that if it is likely to be misused then maybe the latter is
preferable.

LL

On Thu, Feb 27, 2020 at 2:33 AM Jonas Nick  wrote:

> > Let me put change (1) into my own words.
>
> Correct, except that the speedup from is_even(y) over
> is_quadratic_residue(y)
> affects signing and not keypair generation.
>
> > With change (2), I feel like including this auxiliary random data is
> overkill
> > for the spec. [...] I feel similarly about hashing the public key to get
> the
> > nonce.
>
> It's not clear why removing these features from the spec would be an
> improvement.
> The BIP follows a more reasonable approach: it specifies a reasonably
> secure
> signing algorithm and provides the rationale behind the design choices.
> This
> allows anyone to optimize for their use case if they choose to do so.
> Importantly, "reasonably secure" includes misuse resistance which would be
> violated if the pubkey was not input to the nonce generation function.
>
> > Perhaps they even deserve their own BIP?
>
> Yes, a standard for nonce exfiltration protection and MuSig would be
> important
> for compatibility across wallets.
>
>
> On 2/26/20 4:20 AM, Lloyd Fournier via bitcoin-dev wrote:
> > Hi Pieter,
> >
> > Let me put change (1) into my own words. We are already computing affine
> > coordinates since we store public keys as the affine x-coordinate. It is
> > faster to compute is_even(y) than is_quadratic_residue(y) so we get a
> speed
> > up here during keypair generation. In the verification algorithm, we do
> the
> > following for the public key  x_only => affine + negate if not is_even(y)
> > => jacobian. The minor slowdown in verification comes from the extra
> > evenness check and possible negation which we didn't have to be done in
> the
> > previous version. This seems like a reasonable change if it makes things
> > easier for existing code bases and infrastructure.
> >
> > With change (2), I feel like including this auxiliary random data is
> > overkill for the spec. For me, the main point of the spec is the
> > verification algorithm which actually affects consensus. Providing a note
> > that non-deterministic signatures are preferable in many cases and here's
> > exactly how you should do that (hash then xor with private key) is
> > valuable. In the end, people will want several variations of the signing
> > algorithm anyway (e.g. pass in public key with secret key) so I think
> > specifying the most minimal way to produce a signature securely is the
> most
> > useful thing for this document.
> >
> > I feel similarly about hashing the public key to get the nonce. A note in
> > the alternative signing section that "if you pass the public key into
> > `sign` along with the secret key then you should do hash(bytes(d) ||
> > bytes(P) || m)" would suffice for me.
> >
> > Despite only being included in the alternative signing section, I it
> would
> > be nice to have a few of test vectors for these alternative methods
> anyway.
> > Perhaps they even deserve their own BIP?
> >
> > Cheers,
> >
> > LL
> >
> >
> > On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
> > bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> >> Hello list,
> >>
> >> Despite saying earlier that I expected no further semantical changes
> >> to BIP 340-342, I've just opened
> >> https://github.com/bitcoin/bips/pull/893 to make a number of small
> >> changes that I believe are still worth making.
> >>
> >> 1. Even public keys
> >>
> >> Only one change affects the validation rules: the Y coordinate of
> >> 32-byte public keys is changed from implicitly square to implicitly
> >> even. This makes signing slightly faster (in the microsecond range),
> >> though also verification negligibly slower (in the nanoseco

Re: [bitcoin-dev] BIP 340 updates: even pubkeys, more secure nonce generation

2020-02-25 Thread Lloyd Fournier via bitcoin-dev
Hi Pieter,

Let me put change (1) into my own words. We are already computing affine
coordinates since we store public keys as the affine x-coordinate. It is
faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed
up here during keypair generation. In the verification algorithm, we do the
following for the public key  x_only => affine + negate if not is_even(y)
=> jacobian. The minor slowdown in verification comes from the extra
evenness check and possible negation which we didn't have to be done in the
previous version. This seems like a reasonable change if it makes things
easier for existing code bases and infrastructure.

With change (2), I feel like including this auxiliary random data is
overkill for the spec. For me, the main point of the spec is the
verification algorithm which actually affects consensus. Providing a note
that non-deterministic signatures are preferable in many cases and here's
exactly how you should do that (hash then xor with private key) is
valuable. In the end, people will want several variations of the signing
algorithm anyway (e.g. pass in public key with secret key) so I think
specifying the most minimal way to produce a signature securely is the most
useful thing for this document.

I feel similarly about hashing the public key to get the nonce. A note in
the alternative signing section that "if you pass the public key into
`sign` along with the secret key then you should do hash(bytes(d) ||
bytes(P) || m)" would suffice for me.

Despite only being included in the alternative signing section, I it would
be nice to have a few of test vectors for these alternative methods anyway.
Perhaps they even deserve their own BIP?

Cheers,

LL


On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello list,
>
> Despite saying earlier that I expected no further semantical changes
> to BIP 340-342, I've just opened
> https://github.com/bitcoin/bips/pull/893 to make a number of small
> changes that I believe are still worth making.
>
> 1. Even public keys
>
> Only one change affects the validation rules: the Y coordinate of
> 32-byte public keys is changed from implicitly square to implicitly
> even. This makes signing slightly faster (in the microsecond range),
> though also verification negligibly slower (in the nanosecond range).
> It also simplifies integration with existing key generation
> infrastructure. For example BIP32 produces public keys with known
> even/oddness, but squaredness would need to be computed separately.
> Similar arguments hold for PSBT and probably many other things.
>
> Note that the Y coordinate of the internal R point in the signature
> remains implicitly square: for R the squaredness gives an actual
> performance gain at validation time, but this is not true for public
> keys. Conversely, for public keys integration with existing
> infrastructure matters, but R points are purely internal.
>
> This affects BIP 340 and 341.
>
> 2. Nonce generation
>
> All other semantical changes are around more secure nonce generation
> in BIP 340, dealing with various failure cases:
>
> * Since the public key signed for is included in the signature
> challenge hash, implementers will likely be eager to use precomputed
> values for these (otherwise an additional EC multiplication is
> necessary at signing time). If that public key data happens to be
> gathered from untrusted sources, it can lead to trivial leakage of the
> private key - something that Greg Maxwell started a discussion about
> on the moderncrypto curves list:
> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
> believe it should therefore be best practice to include the public key
> also in the nonce generation, which largely mitigates this problem.
>
> * To protect against fault injection attacks it is recommended to
> include actual signing-time randomness into the nonce generation
> process. This was mentioned already, but the update elaborates much
> more about this, and integrates this randomness into the standard
> signing process.
>
> * To protect against differential power analysis, a different way of
> mixing in this randomness is used (masking the private key completely
> with randomness before continuing, rather than hashing them together,
> which is known in the literature to be vulnerable to DPA in some
> scenarios).
>
> 3. New tagged hash tags
>
> To make sure that any code written for the earlier BIP text fails
> consistently, the tags used in the tagged hashes in BIP 340 are
> changed as well.
>
> What do people think?
>
> --
> Pieter
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] [Annoucement] Discreet Log Contract Protocol Specification

2020-01-28 Thread Lloyd Fournier via bitcoin-dev
Hi Chris,

This is a really exciting effort. I hope I will be able to contribute to
it. I was wondering if you had seen the idea that DLCs can be done in only
two transaction using Schnorr[1]. I also think this can be done in Bitcoin
as it is today using ECDSA adaptor signatures [2]. In my mind, the adaptor
signature protocol is both easier to specify and implement on top of being
cheaper and more private.

LL

[1] https://lists.launchpad.net/mimblewimble/msg00485.html
[2]
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-November/002316.html

On Tue, Jan 14, 2020 at 2:12 AM Chris Stewart via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi all,
>
> Suredbits and Crypto Garage have begun to work on a specification for
> using discreet log contracts  in a
> safe, private and interoperable way. We are writing to the mailing list to
> inform and solicit feedback for the protocol specification so that we can
> -- as a community -- agree on a common standard to use Bitcoin oracles.
>
> Our goal is to end up with a set of documents like the BIPs (Bitcoin
> Improvement Proposals) and BOLTs (Basis of Lightning Technology) so that
> others that wish to use the technology can easily write software to
> integrate into the protocol.
>
> A secondary goal of ours is to remain compatible with standards used by
> other bitcoin related protocols (like Lightning) so that every future
> bitcoin related protocol can reach for a “toolbox” of agreed standards for
> things like funding transactions and closing transactions. We want to avoid
> reinventing the wheel where possible and allow for library developers to
> re-use software to hook into many bitcoin related protocols.
>
> You can find the specification repository here:
>
> https://github.com/discreetlogcontracts/dlcspecs/
>
> For more information on DLCs:
>
> [1] - https://adiabat.github.io/dlc.pdf
>
> [2] - https://cryptogarage.co.jp/p2pd/
>
> [3] -
> https://suredbits.com/discreet-log-contracts-part-1-what-is-a-discreet-log-contract/
>
> [4] -
> https://blockstream.com/2019/04/19/en-transacting-bitcoin-based-p2p-derivatives/
>
> [5] - https://dci.mit.edu/smart-contracts
>
> -Chris
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Composable MuSig

2019-12-08 Thread Lloyd Fournier via bitcoin-dev
Hi ZmnSCPxj,

I think you're idea of allowing multiple Rs is a fine solution as it
would essentially mean that you were just doing a three party MuSig
with more specific communication structure. As you mentioned, this is
not quite ideal though.

> It seems to me that what is needed for a composable MuSig is to have a 
> commitment scheme which is composable.

Maybe. Showing certain attacks don't work is a first step. It would
take some deeper analysis of the security model to figure out what
exactly the MuSig requires of the commitment scheme.

> To create a commitment `c[A]` on the point A, such that `A = a * G`, the 
> committer:
>
> * Generates random scalars `r` and `m`.
> * Computes `R` as `r * G`.
> * Computes `s` as `r + h(R | m) * a`.
> * Gives `c[A]` as the tuple `(R, s)`.

This doesn't look binding. It's easy to find another ((A,a),m) which
would validate against (R,s). Just choose m and choose a = (s - r)
h(R||m)^-1.

Cheers,

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Composable MuSig

2019-12-01 Thread Lloyd Fournier via bitcoin-dev
Hi ZmnSCPxj,

> > Just a quick note: I think there is a way to commit to a point properly 
> > with Pedersen commitments. Consider the following:
> > COM(X) = (y*G + z*H, y*G + X)  where y and z are random and the opening is 
> > (y,z,X).  This seems to be a  unconditionally hiding and computationally 
> > binding homomorphic commitment scheme to a point based on the DL problem 
> > rather than DDH.
>
> So the Pedersen commitment commits to a tweak on `X`, which is revealed later 
> so we can un-tweak `X`.
> Am I correct in assuming that you propose to use `X` for the contribution to 
> `R` for a participant?
> How is it different from using ElGamal commitments?

Yes. It's not significantly different. It is unconditionally hiding
rather than binding (ElGamal is unconditionally binding). I just
thought of it while reading your post so I mentioned it. The real
question is what properties does the commitment scheme need to be
appropriate for MuSig R coin tossing?
In the security proof, the commitment hash is modelled as a random
oracle rather than as an abstract commitment scheme. I wonder if any
MuSig author has an opinion on whether the H_com interaction can be
generalised to a commitment scheme with certain properties (e.g
equivocal, extractable). By the looks of it, the random oracle is
never explicitly programmed except with randomly generated values so
maybe there is hope that a non ROM commitment scheme can do the job. I
guess the reduction would then be to either breaking the discrete
logarithm problem OR some property of the commitment scheme.

Cheers,

LL
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] Composable MuSig

2019-11-29 Thread Lloyd Fournier via bitcoin-dev
Hi ZmnSCPxj,

Very interesting problem.

Just a quick note: I think there is a way to commit to a point properly
with Pedersen commitments. Consider the following:
COM(X) = (y*G + z*H, y*G + X)  where y and z are random and the opening is
(y,z,X).  This seems to be a  unconditionally hiding and computationally
binding homomorphic commitment scheme to a point based on the DL problem
rather than DDH.

LL

On Mon, Nov 25, 2019 at 10:00 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> So I heard you like MuSig.
>
>
> Introduction
> 
>
> Previously on lightning-dev, I propose Lightning Nodelets, wherein one
> signatory of a channel is in fact not a single entity, but instead an
> aggregate:
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-October/002236.html
>
> Generalizing:
>
> * There exists some protocol that requires multiple participants agreeing.
>   * This can be implemented by use of MuSig on the public keys of the
> participants.
> * One or more of the participants in the above protocol is in fact an
> aggregate, not a single participant.
>   * Ideally, no protocol modification should be needed to support such
> aggregates, "only" software development without modifying the protocol
> layer.
>   * Obviously, any participant of such a protocol, whether a direct
> participant, or a member of an aggregated participant of that protocol,
> would want to retain control of its own money in that protocol, without
> having to determine if it is being Sybilled (and all other participants are
> in fact just one participant).
>   * Motivating example: a Lightning Network channel is the aggregate of
> two participants, the nodes creating that channel.
> However, with nodelets as proposed above, one of the participants is
> actually itself an aggregate of multiple nodelets.
> * This requires that a Lightning Network channel with a MuSig address,
> to have one or both participants, be potentially an aggregate of two or
> more nodelet participants, e.g. `MuSig(MuSig(A, B), C)`
>
> This is the "MuSig composition" problem.
> That is, given `MuSig(MuSig(A, B), C)`, and the *possibility* that in fact
> `B == C`, what protocol can A use to ensure that it uses the three-phase
> MuSig protocol (which has a proof of soundness) and not inadvertently use a
> two-phase MuSig protocol?
>
> Schnorr Signatures
> ==
>
> The scheme is as follows.
>
> Suppose an entity A needs to show a signature.
> At setup:
>
> * It generates a random scalar `a`.
> * It computes `A` as `A = a * G`, where `G` is the standard generator
> point.
> * It publishes `A`.
>
> At signing a message `m`:
>
> * It generates a random scalar `r`.
> * It computes `R` as `R = r * G`.
> * It computes `e` as `h(R | m)`, where `h()` is a standard hash function
> and `x | y` denotes the serialization of `x` concatenated by the
> serialization of `y`.
> * It computes `s` as `s = r + e * a`.
> * It publishes as signature the tuple of `(R, s)`.
>
> An independent validator can then get `A`, `m`, and the signature `(R, s)`.
> At validation:
>
> * It recovers `e[validator]` as so: `e[validator] = h(R | m)`
> * It computes `S[validator]` as so: `S[validator] = R + e[validator] * A`.
> * It checks if `s * G == S[validator]`.
>   * If `R` and `s` were indeed generated as per signing algorithm above,
> then:
> * `S[validator] = R + e[validator] * A`
> * `== r * G + e[validator] * A`; subbstitution of `R`
> * `== r * G + h(R | m) * A`; substitution of `e[validator]`
> * `== r * G + h(R | m) * a * G`; substitution of `A`.
> * `== (r + h(R | m) * a) * G`; factor out `G`
> * `== (r + e * a) * G`; substitution of `h(R | m)` with `e`
> * `== s * G`; substitution of `r + e * a`.
>
> MuSig
> =
>
> Under MuSig, validation must remain the same, and multiple participants
> must provide a single aggregate key and signature.
>
> Suppose there exist two participants A and B.
> At setup:
>
> * A generates a random scalar `a` and B generates a random scalar `b`.
> * A computes `A` as `A = a * G` and B computes `B` as `B = b * G`.
> * A and B exchange `A` and `B`.
> * They generate the list `L`, by sorting their public keys and
> concatenating their representations.
> * They compute their aggregate public key `P` as `P = h(L) * A + h(L) * B`.
> * They publish the aggregate public key `P`.
>
> Signing takes three phases.
>
> 1.  `R` commitment exchange.
>   * A generates a random scalar `r[a]` and B generates a random scalar
> `r[b]`.
>   * A computes `R[a]` as `R[a] = r[a] * G` and B computes `R[b]` as `R[b]
> = r[b] * G`.
>   * A computes `h(R[a])` and B computes `h(R[b])`.
>   * A and B exchange `h(R[a])` and `h(R[b])`.
> 2.  `R` exchange.
>   * A and B exchange `R[a]` and `R[b]`.
>   * They validate that the previous given `h(R[a])` and `h(R[b])` matches.
> 3.  `s` exchange.
>   * They compute `R` as `R = R[a] + R[b]`.
>   * They compute `e` as `h(R | m)`.
>   * A computes 

Re: [bitcoin-dev] BIPable-idea: Consistent and better definition of the term 'address'

2019-10-10 Thread Lloyd Fournier via bitcoin-dev
Hi Thread,

This may not be the most practical information, but there actually did
exist an almost perfect analogy for Bitcoin addresses from the ancient
world: From wikipedia https://en.wikipedia.org/wiki/Bulla_(seal)

"Transactions for trading needed to be accounted for efficiently, so the
clay tokens were placed in a clay ball (bulla), which helped with
dishonesty and kept all the tokens together. In order to account for the
tokens, the bulla would have to be crushed to reveal their content. This
introduced the idea of impressing the token onto the wet bulla before it
dried, to insure trust that the tokens hadn't been tampered with and for
anyone to know what exactly was in the bulla without having to break it."

You could only use the bulla once because it had to be destroyed in order
to get the tokens out! I think there are even examples of bulla with a kind
of "signature" on them (an imprint with the seal of a noble family etc).

"send me a Bitcoin bulla" has a nice ring to it!

Sincerely,

LL





On Fri, Oct 11, 2019 at 2:44 AM Emil Engler via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> * Sorry if this mail was sent multiple times, my E-Mail client went crazy *
>
> Thanks for all your feedback.
> I came to the decision to write a BIP for this, even if it might not be
> implemented by many wallets, a standardization is never wrong and this
> would be the first step in the correct direction for better on-chain
> privacy.
>
> However currently we still need a good term for the 'address' replacement.
>
> The current suggestions are:
> * Invoice ID
> * Payment Token
> * Bitcoin invoice (address)
> * Bitcoin invoice (path)
>
> Because of the LN term invoice I really like the term 'Bitcoin Invoice'
> by Chris Belcher.
>
> So how do find a consensus about these terms?
>
> Greetings
> Emil Engler
> ___
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev


Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

2019-10-06 Thread Lloyd Fournier via bitcoin-dev
Hi Thread,

I made a reply to the OP but didn't "reply all" so it just went directly to
Ethan. Since the comments were interesting I'll attempt to salvage them by
posting them in full:

== Lloyd's post ==
Hi Ethan,

I'd be interested to know what protocols you need OP_CAT for. I'm trying to
figure out if there really exists any script based protocol that doesn't
have a more efficient scriptless counterpart.  For example,
A²L[1] achieves the same thing as Tumblebit but requires no script. I can
imagine paying based on a merkle path could be useful, but a protocol was
recently suggested on lightning-dev [2] that does this but without OP_CAT
(and without any script!).


[1] https://eprint.iacr.org/2019/589.pdf
[2]
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html
(*I linked to the wrong thread in the original email*).

LL

== Ethan's response ==
Hi Lloyd,

Thanks for your response. I am not sure if you intended to take this off
list or not.

I plan to at some point to enumerate in detail protocols that OP_CAT would
benefit. A more important point is that OP_CAT is a basic building block
and that we don't know what future protocols it would allow. In my own
research I have avoiding going down certain paths because it isn't worth
the time to investigate knowing that OP_CAT wouldn't make the protocol
practical.

In regards to scriptless scripts they almost always require an interactive
protocol and sometimes ZKPs. A2L is very impressive but like TumbleBit it
places a large burden on the developer. Additionally I am aware of no way
to reveal a subset of preimages with scriptless scripts, do a conditioned
reveal i.e. these preimages can only spend under these two pubkeys and
timelockA where after timelockZ this other pubkey can spend without a
preimages. Scriptless scripts are a fantastic tool but they shouldn't be
the only tool that we have.

I'm not sure I follow what you are saying with [2]

This brings me back a philosophical point:
Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

I really appreciate your comments.

Thanks,
Ethan
==

*Back to normal thread*

Hi Ethan,

Thanks for the insightful reply and sorry for my mailing list errors.

> I plan to at some point to enumerate in detail protocols that OP_CAT
would benefit.

Sweet. Thanks.

> Additionally I am aware of no way to reveal a subset of preimages with
scriptless scripts, do a conditioned reveal i.e. these preimages can only
spend under these two pubkeys and timelockA where after timelockZ this
other pubkey can spend without a preimages. Scriptless scripts are a
fantastic tool but they shouldn't be the only tool that we have.

Yes. With adaptor signatures there is no way to reveal more than one
pre-image; you are limited to revealing a single scalar. But you can have
multiple transactions spending from the same output, each with a different
set of scriptless conditions (absolute time locks, relative time locks and
pre-image reveal). This is enough to achieve what I think you are
describing. FWIW there's a growing consensus that you can do lightning
without script [1]. Perhaps we can't do everything with this technique. My
current focus is figuring out what useful things we can't do like this
(even if we were to go wild and add whatever opcodes we wanted). So far it
looks like covenants are the main exception.

> I'm not sure I follow what you are saying with [2]

That is perfectly understandable as I linked the wrong thread (sorry!).
Here's the right one:
https://www.mail-archive.com/lightning-dev@lists.linuxfoundation.org/msg01427.html

I was pointing to the surprising result that you can actually pay for a
merkle path with a particular merkle root leading to a particular leaf that
you're interested in without validating the merkle path on chain (e.g.
OP_CAT and OP_SHA256). The catch is that the leaves have to be pedersen
commitments and you prove the existence of your data in the merkle root by
showing an opening to the leaf pedersen commitment. This may not be general
enough to cover every merkle tree use case (but I'm not sure what those
are!).

> This brings me back a philosophical point:
> Bitcoin should give people basic tools to build protocols without first
knowing what all those protocols are especially when those tools have very
little downside.

This is a really powerful idea. But I've started feeling like you have to
just design the layer 2 protocols first and then design layer 1! It seems
like almost every protocol that people want to make requires very
particular fundamental changes: SegWit for LN-penalty and NOINPUT for eltoo
for example. On top of that it seems like just having the right signature
scheme (schnorr) at layer 1 is enough to enable most useful stuff in an
elegant way.

[1]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-September/017309.html

Cheers,

LL

On 

Re: [bitcoin-dev] OP_LOOKUP_OUTPUT proposal

2019-08-12 Thread Lloyd Fournier via bitcoin-dev
Hello Runchao and ZmnSCPxj,

I think we can simplify the explanation here by not using joint signatures
and payment channel like constructions. ZmnSCPxj's more complex
construction could be more dynamic and practical in some settings but at
least for me it gets in the way of capturing how this relatively simple
idea works.
Here's my attempt at distilling the idea:

Step 0: Alice and Bob negotiate the parameters (timeouts, refund/redeem
pubkeys, the collateral amounts and inputs/outputs for the WTJ-HTLC)

=== Step 1 ===
 Alice signs and broadcasts the BTC-HTLC and sends signature(s) on her
input(s) to the WJT-HLTC to Bob.
Note:
1. She does not need to wait for the BTC-HTLC to confirm before she sends
her signature(s).
2. There is no benefit to Alice in delaying at this point

=== Step 2 ===
Upon receiving Alice's input signature(s) and seeing the BTC-HTLC with
sufficient confirmations, Bob completes the transaction by supplying his
own signature(s) and broadcasts it.

Note:
1. Bob's ability to delay at this point shouldn't be considered an option.
Alice may withdraw her offer by double spending her one of her inputs to
the WTJ-HTLC. Alice's ability to cancel the offer and take back BTC after
the timeout proves there is no option (options cannot be cancelled)
2. In this plain construction Alice should cancel promptly (if she doesn't
see the WTJ-HTLC within the next 1 or 2 blocks for example)
3. You could even extend this protocol  to specify that Bob send signatures
on his inputs the WTJ-HTLC immediately to Alice. If he refuses Alice can
cancel within a second or two.

=== Step 3 ===
Upon seeing the WTJ-HTLC get sufficient confirmations, Alice takes the
funds (including her collateral back) by revealing the secret.

Note:
1. If she doesn't redeem the HTLC she loses her collateral. Assuming the
loss of the collateral overwhelms any gain she could experience from the
delaying her decision and she operates in her own financial interest she
redeems it immediately.

Step 4 is as usual.

At each step there is no unfair advantage to either party (at least if we
idealise the blockchains somewhat and assume that neither party can
influence which transactions get into which block etc etc).

ZmnSCPxj,

Thanks for continuing to spread this idea!
I'm still not sure about your "two hashes" approach to lightning but I hope
to get to the bottom of it soon by describing how I think it should work
more formally somewhere. Will post to lightning-dev when I do :)

LL

On Mon, Aug 12, 2019 at 4:06 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Runchao,
>
>
> Sent with ProtonMail Secure Email.
>
> ‐‐‐ Original Message ‐‐‐
> On Monday, August 12, 2019 11:19 AM, Runchao Han 
> wrote:
>
> > Good morning ZmnSCPxj,
> >
> > Sorry for the ambiguity of my last email. It was Sunday and I wrote it
> in 1 min on my bed. Let me elaborate what we are thinking of here.
> >
> > ## Analysis on the protocol from Fournier et al.
> >
> > In this protocol, Bob participates in the swap following the steps below:
> >
> > 1. Alice and Bob creates a payment channel on WJT blockchain.
> > 2. Bob creates the WJT transaction using the joint account of Alice and
> Bob, including 1) Bob's input of 1,000,000 WJT, 2) Alice’s input for the
> 10,000 WJT premium. This transaction should be signed by both Alice and Bob
> in order to be valid.
> > 3. Bob signs the WJT transaction and sends the WJT transaction to Alice.
> > 4. Alice signs this WJT transaction. At this stage, Alice has both the
> valid BTC transaction and the valid WJT transaction.
> > 5. Alice broadcasts both the BTC transaction and the WJT transaction.
>
> Incorrect.
>
> The order is below.
> I add also the behavior when the protocol is stalled such that a step is
> not completed.
>
> 1.  Alice broadcasts and confirms a BTC transaction paying an HTLC,
> hashlock Bob, Timelock Alice.
> * Alice is initiating the protocol via this step, thus non-completion
> of this step is simply not performing the protocol.
> 2.  Alice informs the BTC transaction to Bob.
> * If Alice does not perform this, Bob does not know it and Alice
> locked her own money for no reason.
> 3.  Alice and Bob indicate their inputs for the WJT-side funding
> transaction.
> * If Alice does not perform this, it aborts the protocol and Alice
> locked her own money for no reason.
> * If Bob does not perform this, it aborts the protocol and Bob turns
> down the opportunity to earn 10,000 WJT (opportunity cost).
> 4.  Alice and Bob exchange signatures for the WJT-side claim transaction
> which spends the funding transaction via the hashlock side and gives
> 1,000,000 WJT to payout to Alice and 10,000 WJT premium to Bob.
> Order does not matter as funding  tx is still unsigned.
> * If Alice does not perform this, it aborts the protocol and Alice
> locked her own money for no reason.
> * If Bob does not perform this, it aborts the protocol and Bob turns
> down