#grin2020 Roadmap - calling for blog posts with ideas

In terms of pros, it’s been said that supporting BLS signatures would enable:

  1. Transactions to be created non-interactively, i.e. no communication between sender S and recipient R required for a valid transaction to be built;
  2. All transaction kernels (moving forward from that point on) to be aggregated into a single kernel.

In terms of cons, I understand that:

  1. Additional hardness assumptions would be added so that Grin would no longer have the same security assumptions as Bitcoin.
  2. Adaptor signatures (scriptless scripts) would not work with BLS. Even if there are efforts to figure out how to support this, they have not been confirmed to work yet. This means things like atomic swaps and lightning-network style scaling on L2 might not be possible in the future.
  3. There’s added complexity in terms of supporting two signatures (Schnorr + BLS), there’s added effort in terms of building/integrating a BLS library where there currently is no standard, and added risk in terms of getting something wrong in the implementation process where there’s not been an implementation in production yet.

In addition, there’s an open question in terms of how to best introduce the signatures and (any) migration process. A turnstile approach has been mentioned in the past, but I don’t think there’s been an actual proposal yet for how this would work in practice.

What else is there in terms of pros/cons/questions that I’ve failed to include above? For the record, I don’t think it’s been established yet whether the above claims are factually correct.

2 Likes

I think item 2 is misleading. A kernel consists of several parts: a public excess, a message (usually including a fee, and an optional lock height), a nonce commitment, and the actual signature scalar.

With BLS there are no nonces, and the signature scalar becomes a signature curve point.

Even with BLS, one still needs to store all the public excesses (i.e. public keys), and all the messages. For each unique message, one can then aggregate their signature curve points into a single one.

Overall this appears to be at best a small constant factor reduction in size and processing.

2 Likes

That’s great to get clarified, @tromp.

With regards to point 1, I think there was some questions around that as well? I saw some discussion in the keybase chat recently but can’t find it now. Was it ever established to what degree transactions would be non-interactive under BLS? @jaspervdm @david

Assuming we don’t want to put additional data on-chain, you might be able to reduce transaction building to a single trip, i.e. S->R instead of S->R->S, but not better than that. We are still limited by the bulletproof, which can only be generated by the receiver.

I think the main question right now is if at our current point in time it would make sense to dedicate our limited resources to BLS.
Grin has been relying only on “established” cryptography, based on ECDLP. Using BLS would be a significant departure from that, pairing based crypto is less mature and “battle-tested”. In addition we would have to indefinitely support 2 crypto libraries simultaneously that use different curves and devise a way to allow users to transfer between them.

Edit; oh i see daniel already did a good job of summarising the downsides :slight_smile:

1 Like

I’ll have to re-read the Gandalf the Pink proposal, but I think the idea behind hanging transactions was that the bulletproofs would be added when spending, essentially making them part of the input instead of the output.

For scriptless scripts, one possibility is to support them with lesser security properties by including an additional signature that’s pruned after the horizon. It’s debatable whether that provides enough security, and can be made to work.

The biggest point to be made is we won’t know what’s possible until we actually fully investigate the consequences of BLS, and try to design a system that uses them. It appears to me that some have already written them off, while others believe they will solve everything, but I don’t think any of us have done enough legwork to come to any such conclusions.

2 Likes

Not going to be saying much new here, but just going to summarise my understanding and position on any potential BLS signature research.

First, I think we need to split off consideration of the Pink Paper for the time being and set it to one side. It is definitely of value and of it does indeed outlines exciting possibilities, but it’s still an unreviewed proposal based on a theoretical foundation (e.g. a Grin or Grin-like chain that already incorporates BLS) that doesn’t currently exist. I’d see it as an potential example of something that might be enabled by Grin+BLS, but designing or planning to it right now is putting the cart several miles before the horse.

That foundation is what we’d be looking to establish via any BLS research we’d be undertaking at this time. As has been said before (but I’ll outline for the purpose of my point,) the immediate implications of changing the underlying cryptography to a pairing-friendly curve and incorporating BLS are:

  • The ability for a secure single-trip (A->B) transaction creation that doesn’t leak private keys. (This is actually possible today if participants are willing to expose their keys to the other party). The main advantage BLS gives over Schnorr is that no exchange of nonces is required among all parties before the partial sigs can be created, enabling the A to include a partial sig in the transaction sent to B. That’s really about it. edit: (Not without further research on how to construct this, see thread below)
  • Being a step closer to kernel aggregation, (but not all the way there)

That, in my mind, is it for the time being. Incorporating BLS will not magically give us ‘non-interactive transactions’, (though it may facilitate future schemes that can try to emulate them,). It could remove some friction from the transaction creation process, a not-insignificant benefit.

However, the main downsides of trying to bung this into Grin as it stands are many (and have all been stated before):

  • Having to maintain 2 separate crypto implementations
  • BLS requires the use of pairing-based cryptography, which is immature as a field of study and very immature in terms of usable implementations, which means massive risk for anyone relying on them for secure applications. It would be highly irresponsible of us to suddenly expose all of the value locked up in Grin in this manner.
  • Having to reconcile pairing-based outputs with secp256k1 outputs (the whole foundation of MW is summing outputs together, and you can’t meaningfully sum elements across 2 separate fields) I can’t even begin to imagine how we’d deal with that.

On balance, I don’t see the immediate benefits (slightly easier transactions, slightly slimmer kernel set and only nebulous possibilities of future benefits) being worth this pain and risk exposure for all Grin users.

If I were to start a Grin+BLS research project right now, what I would be doing is forking Grin and replacing the underlying crypto primitives with the most mature paring-based curve implementation available. (This in itself would be a very time-consuming and resource intensive project, don’t forget all of the work that’s gone into implementing the MW primitives on top of libsecp256k1.) Then I would be replacing the current transaction-building protocol with a single-trip A->B protocol based on BLS.

I would not even attempt to think about how to incorporate all of this into Grin at the outset, and would be exclusively focused on a new testing chain that only uses bleeding-edge and largely untested and unhardened paring-based crypto. I would thus call it ‘Grinsecure’, because nobody would have any idea whether it’s supposed to be more secure or less secure than Grin, which would accurately reflect reality.

This would be entirely, 100% a ‘Grin Labs’ (n.b. this doesn’t actually exist) research project intended to explore pairing-based crypto, the possibilities enabled by BLS signatures, and not in any way intended for use as a new currency or ‘Grin 2’. As I said, trying to bung untested-crypto into Grin for some small and less-then-tangible benefits would be grossly negligent toward anyone who’s put any value at all into Grin.

Perhaps would-be fork authors should take note: instead of forking Grin and changing the economics, try forking Grin and changing the underlying cryptography in this manner, then you’d be adding something of great value from a research perspective that the community could get behind (even though you’d be putting users at great risk if you ever tried to launch an actual currency).

But for now, what I’ve just described is as far as I’d be willing to advocate for exploring BLS currently. Whether this is worth it given our limited resources is hard to say. If we were a corporation with an Advanced Research department, it would be a no-brainer, in our situation, it’s not such a slam-dunk.

1 Like

There’s also the loss of adaptive signatures, which we rely on for doing atomic swaps.

What data would be transmitted if Alice wants to pay Bob, assuming for simplicity no change and no fee?

I haven’t put tons of thought into the exact scheme, but I was assuming something along the lines of inputs (or sum of inputs) + amount + sig(fee) + pubkey, main difference being sig can be aggregated later without a nonce having to passed around. Or is this grossly mistaken? edit: would need to be inputs, not the sum if bob is finalizing

Let’s say Alice has input C=r*G+v*H, and pays v - fee to Bob.
Then what is the pubkey that Alice signs for?

Okay that leaks privacy pretty fundamentally and you’ve caught me out. As I said I haven’t spent any time thinking about details of the scheme.

Do you not believe it possible to create an A->B scheme that doesn’t leak private keys using BLS?

edit: now I am starting to think about it a bit harder… :D… you’d still need to adapt the private key from the commit somehow to conceal it from B, but in such a way that B could still sum but without revealing how it was adapted…

I haven’t made up my mind yet, but it certainly seems like a nontrivial problem…

Indeed, going to go think about this properly now. So I’m embarrassingly corrected and the A->B transaction workflow is a possible as opposed to a certain benefit.

In this context, what is the definition of leaking/exposing private keys here?

This is important because the private keys in question can still be used for secure, trustless and private transaction building without requiring interaction from the private key owner for each transaction.

Assume the private keys in question are generated on a Trezor and securely communicated to a trustless authentication layer that only relies on Sigma protocol based zero knowledge proofs. So far, we are only trusting our Trezor hardware/firmware and DDH assumptions for the security of our private keys in question. Still, we can use these private keys for transaction building without requiring further interactions from the private key owner.

You’re providing a signature using the excess value of all your inputs/outputs as the private key. If I A sends the transaction to B with their inputs + part sig + pubkey, they’re essentially providing the private key, meaning B now has control over that particular set of inputs without necessarily needing to complete the transaction. Anyone can intercept that transaction and spend it, B could also spend it and plausibly claim they never received the transaction.

The current Schnorr tx implementation isn’t based on ‘just Schnorr’, it uses a construction that conceals everyone’s private keys using the additive properties of Schnorr sigs to create a final signature without anyone exposing the private key for their input/output set to anyone else. This comes at the cost of needing further rounds of communication where each party needs to choose a random nonce needed by all parties before they can construct their partial signatures.

So BLS on its own doesn’t provide anything other over Schnorr in this case other than the ability for each party to create a partial sig without needing to know the sum of everyone’s nonces. But the only thing you can sign with is your private key which is your excess value, which you really can’t mask from other parties without some method of concealment that would rely on pre-establishing something with the other party anyhow. So there are no benefits to BLS on its own over just sending your private key for your part of the transaction around.

I am not arguing BLS v.s. Schnorr.

Your definition of exposing the private key is not clear.

Would you consider the private keys to be leaked/exposed in my example?

No, I would not. To be clear, the only thing a user exposes is their part of the transaction’s excess value, which == the private key used to sign for an individuals inputs in the transaction. While these doesn’t correspond directly to keys derived from a wallet (those would be the individual blinding factors within commits, which aren’t exposed), exposing this is still very bad for the reasons stated earlier.

If the integrity of this is also protected by Sigma protocol based zkps, with the same security assumptions that are protecting the private keys, what is the difference?

The security assumptions doesn’t change because of these requirements as defined by the grin-wallet implementation.

Assume Alice sends 16 groth to Bob non-interactively via lelantus-mw, what is leaked/exposed by your definition?

I’m starting to look into BLS now, and I don’t understand this claim. With the modified BLS scheme[1][2], you can also aggregate public keys if messages are the same. So, lets assume you have a block full of plain kernels (no lock heights). For simplicity, let’s assume each has the same fee. Then the message for those transactions are the same.

I’m notoriously bad at parsing and understanding math notation, but from what I can tell, key aggregation in BLS is still just the point addition of each public key. So you should be able to sum all kernel commitments to get the total kernel commitment for the block, and you should be able to aggregate the signatures to get the total signature for the block. And that, along with the inputs, outputs+BPs, and knowledge of the total fee, should be enough to verify the block.

I have a few ideas of how to handle different fees to get them all in the same form, but I want to make sure everything I’ve said is correct so far, because it certainly seems like we should be able to get rid of kernels entirely for standard transactions. I’m sure I’m just missing some important nuance though.

[1] BLS Multi-Signatures With Public-Key Aggregation
[2] https://eprint.iacr.org/2018/483.pdf

I think I can answer my own question now. To prevent rogue key attacks, it seems like each public key must be known. So, assuming all plain kernels with the same fee, the best we could do is reduce the kernels to 33 bytes - about 1/3 the current size. Still a huge reduction, but probably can’t completely eliminate them.

1 Like