Grin: Investigate BLS Signatures

[quentinlesceller]

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

[GandalfThePink]

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]

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]

Relevant paper:

https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html

[GandalfThePink]

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]

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

[antiochp]

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

[lehnberg]

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

[0xb100d]

@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]

@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]

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]

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]

@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]

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]

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]

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]

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]

Good primer: https://gist.github.com/hermanjunge/3308fbd3627033fc8d8ca0dd50809844

[lehnberg]

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]

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

BLS12-381 For The Rest Of Us

[garyyu]

@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.