Correct; the public keys need to be both aggregated and hashed in sequence.
The recommended BLS curves are much larger in size than secp256k1 in order to safely accomodate the pairing; for instance 48 bytes for BLS12-381.
2 Likes
Thanks. So closer to a 50% size reduction at the cost of some additional computation. Not sure how much additional computation yet, but probably enough to make it not worthwhile unless we also get non-interaction.
I believe it still might be possible to get non-interactive transactions though. Iām working through the finer details now to make sure pruning is unaffected, and all data is appropriately committed to (non-malleable), and then I will share the design. 
1 Like
If a Grin transaction is built non-interactively without revealing information that could cause the security or privacy of the transacting parties to be compromised, for example by using ZEXE (Zero knowledge EXEcution), what is leaked/exposed?
In a keybase grincoin.teams.node_dev#research discussion, phyro wondered whether MW could have built in protection against rogue key attacks on kernel aggregation and I thought that since
sum of UTXO commitments ==
sum of kernel commitments + kerneloffset * G + (height+1) * 60e9 * H
the former being rogue-key-proof (because utxo range proofs are also proofs of knowledge of blinding factor) should make the latter rogue-key-proof as well.
So one may not need to store all the public excesses after all.
I hope some cryptographer like Andrew Poelstra or Dan Boneh can weigh in on thisā¦
3 Likes
That would make it more interesting. It would be especially cool if we could also move the fee and lock height outside of the kernel. Iām thinking this might enable us to have the same message for all the commitment signatures and hence make it possible to use the āsimpler testā (3) in [1] to verify?
With regards to moving fees and lock_height, maybe we could use the 20 bytes in the bulletproof to do some magic and put stuff there or commit to it? Another reason we might want to also research this option is that if the aggregation is indeed possible, having:
- a single kernel public key
- a single kernel signature
- a single message
also improves privacy due to not leaking data of approx. number of transactions which right now is the number of kernel commitments in the block and without removing also the fees and lock_height, it would still be possible to derive the number of transactions from the ānumber of messagesā. Imagine how cool it would be to make it impossible to measure the actual usage even when Grin grows.
[1] https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html#mjx-eqn-eqaggsame
2 Likes
What is the motivation behind storing the public excess in the first place?
Regardless, storage is more space efficient with validity proofs, as demonstrated by ZK Sync and Coda Protocol.
Computational re-execution in a replicated state machine makes no sense if it can be avoided. Only the state needs to be replicated for guaranteed safety and liveness.
Validation of each state transition is more efficient with a short recursive proof, with fast verification time. Proof generation is computationally heavy but only performed once per block. BLS signature verification replicated by every node will in aggregate consume more CPU/GPU in a decentralised network.
Am I understanding correctly that in your opinion recursive proofs like Halo make other validation mechanisms somewhat redundant?
Iām not sure thatās correct if one can aggregate both public key and signatures and the message that was signed was always the same, but Iām not a cryptographer so itās best to wait for the opinion of others. I would love if you expanded a bit on this for those of us that are not that well trained in this.
Of course, will do my best to provide some context!
My first question was mostly directed to anyone involved with building the current design, or someone who have acquired that knowledge later on. Not sure who all of these wizards are!
In my following statement, iām arguing that regardless if public excess storage is required or not, replacing signatures with validity proofs over a zkp friendly curve is still more space efficient.
The idea of replacing signatures with validity proofs have been successfully implemented by Coda Protocol. It is also the core component of ZK Sync, an account based implementation of ZK Rollup. I would say it is a proven concept by now.
Coda Protocol refers to their stateless client as the āblockchainā, which is a bit confusing. It is no longer clear what the definition of a blockchain isā¦ A replicated state machine canāt be confused with a stateless client though, so it could be argued that it is a more meaningful term for referring to a blockchain?
As @lehnberg pointed out wrt this post, in summary āThe ambition is to solidify Grinās foundation throughout the course of 2020 and make it easier to build on in future years.ā. What Iām trying to convey, is that a switch to a zkp friendly curve could have several potential benefits. Among these are:
-
Syncing time could be reduced to a few minutes, even with BTCās UTXO set.
-
IBD could be as quick as a downloading a torrent file containing outputs without signatures.
-
Output linkability could potentially be solved with the āZK ZK Rollupā concept.
-
New ways of doing non-interactive transaction building would also be possible.
1 Like
For a more in-depth read, check this paper where Dan Boneh and the inventor of the Roll_up, Barry Whitehat, formalizes further advancements in this area.
āThis reduces the on-chain work to simply verifying a succinct proof that transaction processing was done correctly. In practice, verifiable outsourcing of state updates is done by updating the leaves of a Merkle tree, recomputing the resulting Merkle root, and proving using a SNARK that the state update was done correctly.ā
I prefer the idea of providing validity proofs on top of the current kernel history, perhaps as some 3rd party service. Clients then have the option of doing the current full verification, or to bypass most of it with a recent validity proof.
Advantages:
This keeps our core consensus layer relatively simple and limits the scope of bugs.
It maintains compatibility with hundreds of other secp256k1 based blockchains, allowing for atomic swaps based on adaptor signatures, and integration in decentralized exchanges.
As better and better zkp schemes are developed in the coming years, we can easily update the optional proofs without risk of consensus bugs.
Disadvantages:
The current curve and the blake2b hashing function are zkp unfriendly, so the added-on proofs will be very expensive to compute. That will reduce their frequency to perhaps once a week or once a month, and will require some beefy hardware to run on.
2 Likes
This one is false.
Compatibility with other blockchains is not inherently curve bound. This assumption is wrong.
If a specific chain donāt have a suitable precompile for interoperability, a third chain can be used as an intermediary for atomic swaps.
Rollup is already being implemented by several decentralised exchanges. Validity proofs solves critical problems with traditional atomic swaps and allows for more flexible inter-blockchain-communication (IBC), as well as improved privacy and scalability.
While I agree with the conservative stance wrt changing consensus and limiting the scope of bugs, I think it is important to challenge and verify all claims of advantages and disadvantages in this discussion.
If Bulletproofs can be used as a non-recursive validity proof with cut-through on secp256k1, that would be really cool.
Grin is not well integrated with the larger blockchain ecosystem, as it stands today. I think it would be a mistake to hold on to misguided assumptions about interoperability.
Not sure if @tromp is claiming that cross curve adaptor sig swaps are not possible, or that atomic swaps are not possible without persisting signatures on-chain. Either way, both statements are incorrect.
Atomic swaps based on time-locks are slow and suffers from āthe free option problemā. Decentralised exchanges with universal interoperability, like RenVM, are more likely to attract liquidity.
Cross-chain Rollup with in-/validity proofs is also a possibility that would enable improved interoperability.
I think theyāre highly non-trivial at best, judging from these still incomplete attempts by Monero:
2 Likes
So the way I see it, it seems like grins very well integrated, probably actually the most well integrated coin. Consider the followingā¦
I think bitcoin will have some logic added to it soon in the schoor/taproot update. I think it will allow for logic like: If āXā occurs, Then send āY amount of bitcoin to Z addressā.
So in terms of swaps, Bob says 'X amnt bitcoins will be sent to address A if this Y amnt of grin are sent to address B. Alice could encrypt a grin transaction file for the amount requested and broadcast that itās being sent to address B. If certain conditions are met, the encrypted transaction file could be unlocked with a key allowing bob to finalize and receive his grin. The release of that encryption key to bob so he can finalize and actually receive his grin could be dependent on if the bitcoin were confirmed to be sent to Bobās address A.
Thatās why having a coin where the receiver has to agree to receive is a feature not a bug. So not only is grin well integrated, itās actually going be integral to the whole ecosystem.
1 Like
Atomic swaps between Grin and other secp256k1 coins would use adapter signatures as explained in
and which Jasper vd Maarel demonstrated on testnet.
2 Likes
TBH Iām trying to understand what a discrete logarithm is (please donāt explain). Iāll figure it out eventually.
BLS aggregation helps with storage but it seems to suffer during verification, see āPairing is not so efficientā in https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
Each individual signature is a lot slower to validate, but if you aggregate them all into one, then itās only a single signature validation, so it has the potential to be faster.
To add to the existing list of downsides of BLS signatures:
they donāt easily support payment proofs.