Shielded Kudos Pt. 2: Verifying Constraint Authorship

Applications
1

In this post I’m analysing the guarantees we get from the proposed authorship verification mechanism for receive and intent logics.

Why do we need to prove authorship?

In the proposed design, for the transfer and swap transaction functions the KL logic verifies that the receiver authored the predicates associated with them:

  • transfer TF - receive logic
  • swap TF - intent logic

In the transfer case, the receive logic associated with the receiver is triggered by the sender (we are trying to avoid requiring the receiver being online to authorise the receive). In the swap case, the intent logic is triggered by whomever initiates the swap. We often imagine it being the user themselves, but the user might also delegate this requirement.

In case the [receive or intent] logic is triggered not by the author of the logic, it must be proven that the logic being triggered is indeed associated with the author (the prover acts on behalf of the author).

The proposed solution

It is already described in the main post, here - with a bit more details.

The proposed mechanism is as follows: the author signs the logic L using their identity keypair (the ephemerality of which is out of scope of this post). The prover fetches the logic L and the signature S and proves, as a part of the mandatory KL logic, that the logic is associated with the receiver’s identity public key pk.

Role Known parameters
Author (sk, pk), L, S
Prover pk, L, S
Verifier pk, S
  • Constraint: SignatureScheme.Verify(S, L, pk) = True
  • Instance: pk, S
  • Witness: L

The signature leaks information

.. might be the first thing you think about, at least I did. The ways to deal with it depend on how the prover gets the logic in the first place. But first of all, let’s make it clear: we are talking about leaking information to observers, not the prover (prover knows it all).

1. The logic is public

In that case the signature doesn’t leak much - the logic is public anyway.

2. The logic is not known to the prover

To allow receivers to transfer kudos to the receiver without requiring receiver’s online presence, we must give them access to the logic so that they could trigger it.

3. The logic is communicated [semi-] privately

  1. If the signature is static and deterministic, it leaks some information because the witness is the same every time the prover proves the receive logic compliance. In the function privacy setting, I think, it doesn’t leak much since it isn’t even clear input to what logic this is, but this is a layman’s judgement.
  2. The signature can be re-randomised by the sender (I guess), but the sender is not directly incentivised to do that.
    1. We can enforce some re-randomisation by requiring the senders use their identity to re-randomise the signature, but that only allows us to make sure that different senders make the signature look different.
    2. Another way would be to tie re-randomisation algorithm to both the sender’s identity and some verifiable and constantly changing variable, such as time. It might end up being predictable since time is predictable, but the guarantees we get depend on how reversible re-randomisation process is (how much we can infer about the signature knowing what randomness we used).
    3. If the receiver is sometimes online, they can update the signature periodically. In that case it must be enforced that the previous signature value cannot be used anymore
  3. Hiding the signature under a commitment could help a bit, but if the commitment is static as well, the problem is just transferred here instead.

Conclusion

I wrote this post to make it explicit what we get and what trade-offs we make to achieve our goal. If we can improve it - great, but I think the trade-offs are within the range of acceptable, given our priorities (conditional receive, less online time for the receiver, reasonable privacy). Further analysis won’t hurt.

TL; DR

  1. Signatures help to prove authorship of the [receive or intent] logic
  2. The prover must know the receive logic of the sender
  3. The signature leaks some information to the observers. The ways to reduce it include re-randomisation based on the sender’s identity and time, or periodic signature update when the receiver is online, with invalidation of the previous value
  4. Static values reduce privacy but allow the receiver to not have to be online often
2

Would it be possible to fully flesh out the instances/witness for the shielded case for the setting described in your other post? In the same action, “there are two persistent kudo resources (one consumed, and another created with receiver’s public key pk), and one created ephemeral resource with the receive logic L signed with pk”.

image
image792×655 97.2 KB

The quoted statement above seems to have inter-dependent resources (the two created resources) so what would be the instance of the proof and where from is retrieved in the action?

According to the specs, a resource logic prover has as instance the commitment of the resource (the tag), and possibly extra data in applicationData[tag] of the action it belongs to. Does this means a resource logic can only reason about the resource it belongs to, but not about other resources? In which case seems difficult to have inter-dependent resources.

3

I’m currently working on that.

No, the logic takes multiple inputs, including tags of all other resources (just not specified as self). The witness contains resource objects of all resources from the same action, so the logic can reason about all resources in the action

4

Thanks for the clarification. (Might be worth clarifying this in the specs too.)

If we can take the two resources as the witness, and the two commitments as the instance, then why redefining them? The logic could inspect the persistent created resource to get pk, inspect the ephemeral created resource to get S and L, and then verify the signature S on L with pk.

I think I’ll wait until you specify what you have in mind :slight_smile:

5

It is written in the specs: Instance 3 and 4 are the tags of the other resources in the action, Witness 1 and 2 are the resource objects.

S is not intended to be a part of any resource, but maybe we could indeed put it in the value of the ephemeral resource. I didn’t think of that, but I will think about it when specifying how those logics work.

To address the more general question: I’m just zooming in that specific question of signature verification mechanism. Specifying which part of the input is available to the prover, which - to verifier, and what the constraint is. I think it is worthy to explicitly specify these details and not keep them in the head.

It is in some sense redundant (because this constraint is a part of the KL logic), but my personal preference is to extract things that require more thinking into separate posts to give them the deserved attention and not get distracted by the complexity of the whole thing.

6

Indeed, you are right. I misread it.

OK, I thought it was part of the receive authorization resource (4 bullet point of the explanation in the quoted picture). But pk it is part of the persistent created resource, so could be moved to the witness (?)

Thanks for your quick responses anyway. As I said, I’d better wait until you work out the instance/witness detail to avoid distractions.

1 Like
7

I think you are right. In the KL logic (I just posted it) it isn’t a part of the instance.

8

yes, pk is from value of resource.
I’m confused the signature is in the instance, which would definitely leak the identity. The pk is already tied to the value. Shouldn’t the signature also be part of the witness?

9

I didn’t put it in the witness in this post because otherwise a malicious prover can reuse any other signature signed by this public key. I couldn’t come up with a way to fix that. Specifically, if we expect the user to sign both receive logic and intent logic, the signatures can be reused. I believe in the function privacy case this won’t leak information, but I agree that exposing the signature is bad. Do you see a way around it?

10

I’m afraid function privacy doesn’t conceal instances in logic. The instances in logic proofs are also part of function privacy proofs.

Signature verification constraints bind signatures to specific messages (receive logic or intent logic). Is it possible to abuse the signature? With the same key pair (sk and pk), signing for receive logic and intent logic results in two different signatures. If the signature is misused, the verification constraints will reject it. Specifically, only a valid tuple (pk, L, S) can pass the signature verification. The pk and L are determined by the Kudo resource. No malicious (pk, L, S’) will succeed. Only another valid (pk, L’, S’) works, but this indicates a different Kudo resource for another receiving rule or application as L changes.

Btw, do we have any out-of-circuit checks on the signature?

11

It doesn’t conceal the instances, but it hides the function, so it is not possible to say if the bytes we are passing are a signature or something else.

Yeah, but in this case we would like to hide both the message and the signature.

The circuit is not supposed which L and S are the right ones

L is not determined by the resource, it is a receive/intent logic that is not explicitly exposed to the kudo resource.

12

Not at the moment.

I think the difficulty here is that we would like to keep the logic L private from the general observer, but the pair (L, S) should be accessible by the prover / set of authorised provers.

13

Sorry, I assumed the L is part of value along with the pk. Is there any reason why it shouldn’t be? I think it can address the problem of exposing signature. If L isn’t from the resource, (L, S) could still be abused even with the signature in instances, since out-of-circuit checks on the signature aren’t possible as you also mentioned.

14

The sender puts pk in the resource to identify the receiver. The person who puts the L in that same resource would also be the sender. It doesn’t give us any advantage over not putting L anywhere and just verifying the signature, I think.

15

I don’t think so.
pk and L in the value prevent malicious senders from creating unexpected resources for receivers. Malicious senders must use a valid tuple (pk, L, S). I assume L/L' includes constraints for the receiver’s requirements and are both valid. For example, the receiver expects (pk, L, S). Only the correct (pk, L, S) works for the current created Kudo resource. If (pk, L', S') is misused, L' will reject it by checking constraints on the Kudo resource. If L' also succeeds, it means the current created resource satisfies both L/L'.

If L is not in the value or from the resource, how do we ensure the correct L is triggered? I thought at least we need check the value (L_vk) of the Kudo resource and the current vk in L logic, or are there other methods to ensure this?

16

I might be wrong. If L is in the value, the resource determines the L, but L is still set by the sender. If not, L is specified in other witnesses by the sender. Both approaches seem almost identical.

Proper constraints in L can help prevent malicious senders from creating unexpected resources for receivers. If (pk, L, S) and (pk, L’, S’) are both valid, and the receiver expects resources satisfying (pk, L, S), a well-designed L’ should reject the misuse (pk, L’, S’) by the sender through constraint checks on the expected Kudo resource. But this is about how to design a solid logic.

The only benefit of including L_vk in the value is to allow additional constraints in L logic or other logic using Kudo resources as a witness if needed. However, this seems redundant since L_vk is already constrained in KL.

1 Like
17

What benefits can we gain by putting the signatures to instances if we can’t have out-of-circuit checks on the signatures?

18

I think I misspoke. I think we can check the signature, but only by those who already know it can do it. E.g., I imagine that the receiver might post their (L, S) pair somewhere where a group of senders can access it. In that case, both the receiver and all of the senders can verify that the signature corresponds to the logic. Something like that.

19

Did I misunderstand sth?

This proposal checks the constraint of sig.verify(S, L, pk) and triggers L in KL. Senders fetch (S, L, pk) from receivers or where they post it.

pk comes from the resource’s value, and L is a witness in KL. I was convinced that including L in the value or not does not make a big difference.

You noted that S being in instances could leak information. If we dont have out-of-circuit checks for S, can we include S as a witness? The out-of-circuit checks refer to validator’s checks on the instances when verifying tx. The statement is: there exists a valid tuple (S, L, pk) and L is triggered in KL. Is there any reason to put the S in instances?

20

In that case any pair (S, L) signed by pk works, which we might not want. I can imagine pk being used multiple times, e.g., the user’s receive policy changes and they sign a new logic (S’, L’). In case S is in the witness, both pairs verify. If S is exposed, there is a simple (but not too privacy-preserving) way to detect misbehaviour.

If we can make sure that all other signatures ever produced by this key are not valid anymore somehow, then it isn’t a problem