Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Investigate BLS Signatures #2504

Open
quentinlesceller opened this issue Jan 31, 2019 · 28 comments
Open

Investigate BLS Signatures #2504

quentinlesceller opened this issue Jan 31, 2019 · 28 comments
Labels

Comments

@quentinlesceller
Copy link
Member

quentinlesceller commented Jan 31, 2019

Opening this issue to gather ressources and discuss the possibility of using BLS signatures in Grin.

Pro

  • Kernel aggregation
  • Simpler multi-signatures schemes.

Cons

  • Loss of the current form of scriptless script
  • Change of security assumption
  • Possibly slower to verify than Schnorr signatures
  • Few available libraries with little code review

Ressources:

@GandalfThePink
Copy link
Contributor

All of the cryptography based on Weil pairings is extremely interesting and I think there is a lot of open potential that should be studied.

However, Grin only uses very simple and well tested cryptographic concepts and I think this should be preserved.

That said I am very interested to explore and discuss. I understand how to build mutlisignatures in BLS, but fail to see how it allows for kernel aggregation. Can you point me to how this can be achieved in an non-interactive way.

@lehnberg
Copy link
Collaborator

lehnberg commented Feb 4, 2019

Relevant forum thread: https://www.grin-forum.org/t/bls-signatures-implementation-from-chia/609

Can you point me to how this can be achieved in an non-interactive way.

@GandalfThePink see here https://eprint.iacr.org/2018/483

@ignopeverell
Copy link
Contributor

@GandalfThePink
Copy link
Contributor

Hi, I have studied BLS signatures a little and then found some interesting ideas that I pursued furhter enabling user-issued assets. If you find any flaws, please let me know. Otherwise I am happy to discuss.

MWpp.pdf

@ignopeverell
Copy link
Contributor

I'll need a couple more reads to fully parse this, especially security arguments, but you tickle me pink Gandalf.

@antiochp
Copy link
Member

Reading through that MWpp.pdf paper. There's a lot to digest in there. Interesting reading.

@lehnberg
Copy link
Collaborator

Ditto. @GandalfThePink, for deeper scrutiny, you might want to consider posting the paper to the MW mailing list.

@0xb100d
Copy link

0xb100d commented Mar 1, 2019

@GandalfThePink public txs take up just as much space on the chain as private ones? Same cutthrough requirements? And public address can send to private address? So you could give someone public address for them to send to you, and then you send it to yourself privacy (which would be simple to interact with onesself).

Also hanging outputs take up space and cannot be pruned right? Is there any way to incentivize people to spend them quickly to minimze the time they are on chain taking up extra space?

@GandalfThePink
Copy link
Contributor

@0xb100d Public transactions would be slightly larger due to the extra address. Immediate through is a good question I have not really thought much about.

You can restore privacy by sending yourself a private transaction from your public address. Best combine 1 public and one private into 2 private and all information is lost.

Hanging outputs are a bit more complex than normal ones. But I think this would not be a big problem since they are still UTXO's. If we want theoretical scaling with the UTXO size then that is perfectly fine. We are just talking about a constant factor. I think there is no simple way to incentivise spending them faster.

@ignopeverell
Copy link
Contributor

ignopeverell commented Mar 5, 2019

Correct me if I'm wrong @GandalfThePink (or anyone else who had a look) but there seems to be an important privacy regression with hanging transactions. Specifically, for the hanging transaction to be published and included in the chain, all output commitments must be known. And until the transaction is finalized they're all of the form C=vL without blinding.

I've tried to see if things could be rearranged a bit but it seems vL will be leaked no matter the arrangement?

@GandalfThePink
Copy link
Contributor

Hi @ignopeverell

can you be a bit more specific. I think it is possible to build private hanging transactions. The only time all commits must be known is when they are also sent offline. In that case the amount must be committed unblinded.
To be more specific, all participants that are offline can only receive unblinded.

@ignopeverell
Copy link
Contributor

@GandalfThePink

To be more specific, all participants that are offline can only receive unblinded.

That's what I meant. For hanging transactions to be included in the chain to be completed later, as you seem to propose in section 4 Building Non-Interactive Transactions and following, their output amounts can't be blinded (yet). This same setup can surely be done off-chain but then you lose most of the advantages of non-interactivity from a user experience standpoint (i.e. user has to be online or an intermediary needs to be involved to keep the hanging transaction).

@GandalfThePink
Copy link
Contributor

I think there is a way to blind it even in that case.

The problem is that in order to blind the sender must be able to generate valid signatures. And that is easily avoided by simply not blinding. But in fact the output could be blinded by a shared secret. We already know a public key of the receiver. Assuming that the sender also commits to a public key, a shared secret is quickly established and that secret can be signed for by the sender or the receiver alone.

Now in order to spend the output, both the private key and the shared secret is needed, which means that only the receiver can spend it. And in case of conflict for third party verification, the sender can also generate proof that the blinding is in fact to a shared secret. I.e. the sender can prove that the receiver can spend the output.

@ignopeverell
Copy link
Contributor

Sorry for taking so long to follow-up. Can you elaborate on the setup of that shared secret? If both public keys are known, it doesn't seem it can easily be done securely.

@GandalfThePink
Copy link
Contributor

Dont worry about taking some time. I am more than happy that you find my idea useful at all and are even taking some time to look into it.

I only recently started to study cryptography in detail so there may be some obvious things I am missing. I was under the assumption that given P_A = k_A G and P_B = k_B G, S = k_A k_B G is a suitable shared secret. Is there a known attack on this?

@fresheneesz
Copy link
Contributor

Is there any way to incentivize people to spend them quickly to minimize the time they are on chain taking up extra space?

I can think of a way. Would it be possible to construct these payments such that they require a constantly increasing minimum fee in order to spend? This increase would reflect the cost of keeping it around on the chain unaggregated. It should have a limit to how high the minimum-fee can get that is related to the size of the transaction, so that it wouldn't be possible for this mechanism to cause the transaction to become not worth spending (and thus stay on the chain forever). Maybe limit this minimum to 50% of the transaction value.

Let's say the starting minimum punishment is 0, and rises at a continuous rate of the median fee in the last block every 10 days. There are three scenarios:

Scenario 1: Receiver spends it quickly, and incurs no effective punishment. For example, if the receiver spends the transaction within 1 day, the minimum fee almost definitely isn't higher than the receiver would have used anyway.

Scenario 2: Receiver doesn't spend it particularly fast or slowly. For example, if the receiver spends it in 15 days, the minimum fee would probably have gone up to about 1.5 times the usual median fee, which might be more than the receiver would have otherwise spent. So a small extra fee is paid, which compensates (the world) for taking up extra space on the blockchain that long.

Scenario 3: Receiver doesn't spend it until after the minimum fee is reached. For example, if the receiver spends it in 2 years, the minimum-fee limit might have been reached and so the receiver will pay a much higher fee than they otherwise would have.

It seems like this should be possible simply by requiring the minimum fee in the protocol rules. Is there any technical barrier I'm not aware of that would prevent implementing this?

@lehnberg
Copy link
Collaborator

lehnberg commented Nov 14, 2019

@lehnberg
Copy link
Collaborator

Question related to BLS standardisation asked in Chia's dev channel on keybase:

lehnberg
2:05 PM - 11 Dec
Hello all! Are Chia involved in the attempts to standardize BLS sigs? [0] I note that the Algorand Python ref implementation [1] uses finite field from the Chia C++ library, just wondering if the two teams are co-operating and whether there are any (known) noteworthy differences int he implementations aside from the programming languages. Thanks!

[0] https://www.algorand.com/resources/blog/first-release-bls-library
[1] https://github.com/algorand/bls_sigs_ref

bramcohen
2:59 AM - 12 Dec
@lehnberg Yeah it's based in part on our BLS library and we're planning on switching to the standard when it's ready. Dan Boneh is writing the standard and he's an advisor who I talk to all the time

@lehnberg
Copy link
Collaborator

lehnberg commented Jan 9, 2020

https://hackmd.io/@benjaminion/H1lkISO3JU

BLS12-381 For The Rest Of Us

@garyyu
Copy link
Contributor

garyyu commented Jan 21, 2020

@GandalfThePink I read again your research “BLS signatures in Mimblewimble" above: #2504 (comment). I look into your non-interactive transaction proposal, but I don’t find the range proof part, how do you create the range proof for your non-ingteractive transaction output?

Without the knowledge of the receiver's private key, I think there's no way to produce the range proof for the non-interactive transaction output.

@mmaker
Copy link

mmaker commented Jan 2, 2022

Hey, I just wanted to contribute to the discussion here by saying that a long time ago we had already thought about Mimblewimble with BLS signatures, and we had also managed to prove its security. https://eprint.iacr.org/2018/1039

In particular, we cover some of the details that you already have discussed here, but formally.
I'm not sure if you guys in the meantime converged on something, or if you need help understanding what are the security and efficiency trade-offs.

@phyro
Copy link
Member

phyro commented Jan 2, 2022

Hi @mmaker , thanks for reaching out and letting us know about it as well as the kind offer. I'm not a cryptographer, but I did follow the discussion around this a bit so I'll write what I remember. At the end, we mostly agreed that switching to BLS is not something we want to do - at least not for the moment. A big reason for this was the change in the assumption it brings and the added complexity of having to support two different schemes (we'd need to keep Schnorr around for validating the past). The switch would not allow us to "merge kernels" as some have thought at first, but rather it would reduce their size to about 1/3 (signature merging and leaving public keys intact - not merged). This also comes at the cost of removing the ability to support something like scriptless scripts if I recall correctly although I'm not entirely sure. Later on we also found that there's a way to do half-aggregation on Schnorr which might allow us to bring the size of a kernel to 2/3 without new assumptions/schemes, but it would again come at the expense of scripting support - at least the Adaptor signatures would not be possible without some modifications.
The current view is that relying on the assumptions that have been around longer might be better. We've also been thinking that it might be best to offer further sync compaction at the level outside of the chain. So rather than replacing the kernels, we could build an IVC proof from them to allow for a near instant trustless verification of the kernels without changing the chain for those that want it. This allows us to keep the simplicity/safety of the kernels while allowing for experiments using newer and more complex crypto on top of it.

@JoseSK999
Copy link

Hello @phyro, why wouldn't BLS allow for full kernel aggregation? AFAIK BLS public keys can also be aggregated

@phyro
Copy link
Member

phyro commented Jan 1, 2023

@JoseSK999 not sure I'll recall correctly the discussions the community had, but I think it was concluded you can do rogue key attack on the aggregate. I only managed to find this on the forum https://forum.grin.mw/t/aggregating-bls-signatures/7480 unfortunately, but I'm not expert on this unfortunately.

@mmaker
Copy link

mmaker commented Jan 2, 2023

Verification of BLS signatures indeed requires all public keys -- and aggregating them simply by adding up all public keys leads to a rogue key attack. However, if we accept SPV security for the old blocks (like what Litecoin is currently doing) then probable we can hope to achieve some compression?

@mmaker
Copy link

mmaker commented Jan 2, 2023

@phyro: sorry for the late response to your message. I don't really understand the argument you're trying to bring. You highlight the value of relying on the assumptions that have been around longer, but you mention IVC proofs, whose security is not at all well understood and security cannot really be proven?

I'd be curious to know how much of the support of scriptless scripts can be maintained in BLS signatures. Where can I find information about scriptless scripts in the current version of Grin? I tried to go over to https://docs.grin.mw/wiki/transactions/contracts/. Is this what you are talking about? (there's some mistakes there, reporting them in a separate issue.)

@tromp
Copy link
Contributor

tromp commented Jan 2, 2023

IVC is not going to replace the MW UTXO set + kernel history sync; rather it's an optional (outside consensus model) accelerated sync for ppl willing to trade off security for speed (much like SPV).

@phyro
Copy link
Member

phyro commented Jan 2, 2023

@mmaker no worries. Tromp already answered the IVC part. I agree it's better to build such systems on top as you don't introduce new assumption on the core protocol and can also iterate faster because the cost of switching between different schemes/ideas becomes negligible.

Regarding scriptless scripts, I don't think we use these today much, but we can't really know :) The option is there however. Tarilabs has a good description of scriptless scripts and describes some constructs like Adaptor signatures here https://tlu.tarilabs.com/cryptography/introduction-to-scriptless-scripts . To be honest, I'm not really familiar with BLS so I can't give you an accurate answer. My understanding at the time was that because BLS sigs are not linear, the trick Adaptor signatures use can't be done on BLS sigs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests