grin
grin copied to clipboard
mimblewimble
Investigate BLS Signatures
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:
- List of current implementations: https://github.com/ethereum/eth2.0-pm/issues/13
- BLS Signatures implementation from Chia
- BLS Multi-Signatures With Public-Key Aggregation
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.
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
Relevant paper:
https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
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.
I'll need a couple more reads to fully parse this, especially security arguments, but you tickle me pink Gandalf.
Reading through that MWpp.pdf paper. There's a lot to digest in there. Interesting reading.
Ditto. @GandalfThePink, for deeper scrutiny, you might want to consider posting the paper to the MW mailing list.
@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?
@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.
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?
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.
@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).
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.
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.
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?
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?
Good primer: https://gist.github.com/hermanjunge/3308fbd3627033fc8d8ca0dd50809844
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
@GandalfThePink I read again your research “BLS signatures in Mimblewimble" above: https://github.com/mimblewimble/grin/issues/2504#issuecomment-467446197. 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.
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.
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.
Hello @phyro, why wouldn't BLS allow for full kernel aggregation? AFAIK BLS public keys can also be aggregated
@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.
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?
@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.)
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).
@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.