-
Notifications
You must be signed in to change notification settings - Fork 27
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
Protocol: ACL based #16
Comments
Variable names should correspond to Section 5 of the Anonymous Credentials Light (ACL) paper. an open question is how to set up the tag key - seems like we probably just want a NUMS point? for an intuition on the way the blinding works with the tag key, see Abe's paper. it's noteworthy that the blinding/unlinkability is based on computational hardness, so if i'm not mistaken if the coordinator has a quantum computer or the underlying curve is broken then the coordinator would be able to de-anonymize users after the fact, but this doesn't seem like a concern since that would require bitcoin users to move all their funds anyway finally, i don't understand the security proofs of ACL yet, but in the wasabi research club call about it Jonas mentioned the log of the group order needs to be larger than the security parameter. if this is only an issue for soundness then i don't think this is a problem, since a soundness break only leads to blameless DoS, and the coinjoin security model still applies WRT theft. |
I had a mistake in the derivation of terms - since the gamma term (blinding factor) applies to all generators, but the amount only applies to generator , the this would require a combination of sub-amounts that has no 0 terms to avoid cancelling out the gamma terms. So this means that we don't get signatures over commitments that are homomorphic in the amounts as simply as in #10 or #5. |
denotes the different Pedersen commitments and the corresponding signatures the user obtained through the signing protocol. Let be the the set of indices that the user want to sum in a single output and be the desired output amount (note that as per the range proofs over the limited number of summands) To prove a valid sum without revealing the summands, the coordinator needs to ensure that the the product of the commitment is commits to the right value. The user can prove this to the coordinator by producing a group element , such that the coordinator can verify the sum: The user can calculate this because she knows all of the exponents: At output registration time the user submits , and for each the pair . The coordinator verifies the signatures individually, ensuring they haven't been used before, and then computes the product of the commitments and to verify that the sum equation holds. |
About the unused message This paper also presents the ACL protocol with this very minor modification in additive notation, which is probably more readable for bitcoin audiences, where that seems to be standard. |
Hereby a fix for the coin merging protocol is suggested by @nothingmuch and me. Again, we want to prove that the following relation holds between blinded commitments and a specially crafted point on the curve, . One lesson from the attack described above, that we need to constrain the user on how to select , otherwise she could lie about it. Specifically the blinded commitments have the following structure: Note that the user knows all the exponents present in the expression above, however user obviously does not know the discrete logarithms between the generators , because then the commitment scheme would not be computationally binding. The user can therefore create the following terms separately for each : , , . Subsequently the user will prove that each of these terms contain in their exponent without disclosing anything about . Put differently, user proves that the following tuple is a Diffie-Hellman tuple: . After revealing all these elements it is easy to verify the relation we want to prove to the coordinator by checking: With this approach in place we do assume that an appropriate padding scheme is used for the values to have a sufficiently large message space for the values . Otherwise coordinator could just figure out by brute-forcing the exponent. However two crucial questions remain which are not immediate IMO:
Maybe we do not harm neither 1) nor 2) but we additionally need to assume the Diffie-Hellman assumption for the soundness of the coin merging protocol and for the blindness of the ACL scheme to hold. We should try to prove blindness and soundness formally on our own and then see whether we can prove it with these modifications or not. |
i don't think there is a benefit to making that verification equation work on public values. assuming soundness is addressed by these additional relations, i think the sum amount should also be done in zero knowledge, with only |
hmm, maybe i misunderstood:
does this imply the coordinator computes the product out of individual i understood yes (because otherwise padding the amounts would be unnecessary) the reason i expect a single proof to be simpler is that verifying the sum should a single linear constraint on the |
the proof size itself is negligibly larger, but constructing as well as verifying it is still O(N), it's just that the that this work is compressed to only a logarithmic sized verification equation in the end, secondly, it feels a bit crude to me to use a computationally hiding padding scheme when we already have a perfectly hiding i'm still stuck on the homework phase, trying to figure out how to prove the sum of values committed to by a bunch of Pedersen commitments in a sigma protocol, but my understanding is that this isn't very complex, and should naturally compose with the per-credential proofs that relates the zeta terms to the individual amounts? |
I agree. If we can solve it without padding than we can save some dozens of exponentiations from the proof generation time. But still, I hardly doubt that this will be the protocol's bottleneck.
Since the commitment scheme is perfectly binding, then we cannot hope more than a computationally hiding scheme. So this is an inherent limitation we cannot circumvent.
Yeah, let's see if we can improve on this very elementary ZK proof system for coin merging. I agree that there should be a cleaner and more elegant way to achieve the same thing exploiting the nice properties of the blinded commitments. |
why is the commitment scheme perfectly binding? even ignoring gamma, the domain of Pedersen commitments in the attributes is i agree for simple Pedersen hashing with generator |
sorry, i had a very unfortunate brainfart, meant to write "we already have a perfectly hiding commitment scheme", since attributes are a Pedersen commitment. just to be clear, given the choice for this application we should definitely favor perfect hiding to maintain privacy in case of any future crypto break |
Mostly copypasta of #15, but with concrete signature scheme. This protocol is based on the paper: Anonymous Credentials Light (ACL) by Foteini Baldimtsi and Anna Lysyanskaya.
Amount Splitting
User has UTXO with value and wants to split it into outputs with values and such that .
Input Registration
User creates Pedersen Commitments: where . The terms correspond to a single attribute in an ACL signature with an empty message, with a range proofs for each.
The user also needs to prove the sum of the commitments - I think this can just be done revealing and letting the coordinator ensure that the combined commitment is a commitment to the public input amount with this randomness, but if this is problematic for the ACL security proof this can probably be proved in another ways.
From this protocol the user obtains signatures for commitments in a way where the following properties hold:
Output Registration
User can register a desired output for by sending the coordinator
and the sum of their blinding factors(no, but see below).Notice that, the first subscript of is part of the variable name in the paper, while the second one denotes the index of the amount commitment.
Amount Merging
The protocol is the same, except instead of only registering signed zero commitments at output registration, some of those commitments aren't zero, but maybe they were coming from different inputs.
Unlinkability
Since the coordinator cannot recognize the unblinded signatures at output registration, it can only tell they are valid, unlinkability is guaranteed.
Double Spend
Since the unblinded signatures are valid for single blinded commitments only, the coordinator can make sure one signature can only be used once.
The text was updated successfully, but these errors were encountered: