First draft about the audit proofs

[DangerousFreedom1984]

Hello,
I would like to make some comments about the audit framework currently and ask for a first review for the one in Seraphis.

Legacy:

• I took a deeper look at the issue about the InProofs and I totally agree with your answer. InProofs are working fine as they need to validate the amount in order to create a valid InProof. Also, like the OutProof issue, I don't see any reason for the sender and receiver to collaborate and create a proof that does not correspond to the alleged address. It may be possible but it only proves that the owner received some amount (as he knows the private key of the stealth-address). So I don't see any reason for change it now. Also I didn't find any real case complaints.

• I like your ideas about UnspentProof and SubAddressProof to create an audit framework that you designed for the legacy. Maybe in the future we will have a functionality on the wallet where we specify a period of time and the wallet outputs all the proofs for the incoming and outcoming transactions for an external auditor. My concern here is about the amount of time to validate an UnspentProof like you propose. From the prover side he has to provide all the rings that a stealth-address participated (which could be trivial if your wallet keeps track of that) but from the verifier side he cannot take the word of the prover and verify only in the rings that the prover sent. He would have to scan the whole blockchain and get all the transactions that the specific output (stealth-address) appeared. It looks a bit unfeasibly to me. Am I missing something? Also with Seraphis and more stealth-addresses appearing in ring signatures it seems a bit risky to rely on a proof like that.

Regarding Seraphis:

• I believe it is pretty straight forward to create the SpendProof, InProof and OutProof with the same notion that we have today. Please have a look on the first draft and let me know if I am missing something.

• I am still working on the ReserveProof (also please have a look at the proof in the draft). Maybe there is a way to not leak to the linking_tag and still provide some type of UnspentProof. I don't know yet how.

I may have stated wrong phrases (it might be interesting to discuss the last comments in the ReserveProofs) so I will continue working in the audit proofs but any comment is very welcome to improve this first draft already. If everything seems to be fine, I will move to implementing it.

Thank you!
draft_sp.pdf

[UkoeHB]

He would have to scan the whole blockchain and get all the transactions that the specific output (stealth-address) appeared. It looks a bit unfeasibly to me.

This is not that hard, you just need enough storage and a little program to build a table of onetime addresses mapped to a list of the key images from txs where those onetime addresses were referenced as ring members. Then when validating an UnspentProof you just consult that table. (a little more work would be necessary if you want to do UnspentProofs for a certain range of blocks on-chain)

[DangerousFreedom1984]

Yeah, the execution of UnspentProofs is not that expensive. The problem I see is building this table. How the verifier can build it quickly? The only solution I see is scanning the whole blockchain from the moment that the output was created. Certainly he can't believe that the prover will provide all the information about all the rings that it appeared.

[UkoeHB]

Maybe the verifier can't build it quickly, and that's just the price of using UnspentProofs.

[DangerousFreedom1984]

Ok. I believe it is worth to implement it. But in the verification side would be good to let a message saying that it may take some time to verify :p
I will think about the corresponding proof in Seraphis and write about it soon.

[UkoeHB]

SpendProofSpV1
A more efficient way of doing it would be using the grootle proof to recreate the group signature

This is not sufficient. Grootle proofs only prove membership (and anyone can make a membership proof), they say nothing about whether you own the enotes that were spent. You need to re-create seraphis composition proofs on all the inputs, then check that they verify using the same key images as those from the tx.

OutProofSpV1

You can just publish the enote ephemeral privkey r_t for each non-selfsend output, plus the recipient address. Then the verifier can make a JamtisPaymentProposalV1, covert it to a SpOutputProposalV1, extract the SpEnoteV1 (make_v1_outputs_v1()), and check if the result equals the enote found in the relevant tx (and that the associated enote ephemeral pubkey matches the one from the tx). I'm not sure if there is a way to do it for selfsend enotes without leaking private keys.

InProofSpV1

The Diffie-Hellman stuff is all X25519, so I don't know if you can actually make signatures easily. There is definitely not an extensive X25519 library ready to go for that.

One thing you could do is make a modified seraphis composition proof for the enote. First add an offset x X to the onetime address, then make a composition proof on the modified onetime address and also a Schnorr signature on x X. The offset should ensure the resulting composition proof won't link you to the composition proof you make when you spend that enote (i.e. you are making a fake key image).

If you can make a composition proof then the verifier can assume you also know the amount commitment opening, so there is no need to prove anything about that. EDIT: but you probably want to include the amount and commitment blinding factor so the verifier can learn the enote amount and check the amount commitment.

P.S. It might be better to rename this to SpEnoteOwnershipProofV1.

ReserveProofSpV1

In this case there is no need to make enote images. Just make composition proofs directly on the enotes whose key images you want to expose. The amount commitment blinding factors and amounts can be pasted in the proof explicitly - the verifier recomputes the amount commitments and checks they match with the actual enotes.

[DangerousFreedom1984]

Hello Koe,

SpendProof:
I agree that one has to prove that he knows the private keys to generate the grootle proof + composition proofs. I thought I could be a bit more compact so my reasoning here was: if I can prove that I can recreate the grootle proof exactly as it is (with the same ring members) then the verifier could be sure that I created the transaction since the composition proofs are already validated in the blockchain. The problem here is of course to answer 'how do you prove that it was you that generated this ring signature?' so my idea was to make a proof of knowledge on the image offset 'Q[l] - Q" = -(t_k + t_c) G' (proving that you know t_k and t_c). I thought that practically speaking it would be easier and the signatures shorter (but that doesnt really matter). So we have Option 1) new grootle proof (with same ring members) + new image enote with composition proofs. Option 2) grootle proof + schnorr on the offset. For me both work. Since you implemented all functions to make the proofs, it should be easy doing both ways. I will go for option 1 as you suggest as it seems actually more straightforward.

OutProof:
Yes, like the proof is showing you just have to share the enote ephemeral privkey. I wrote more than I should. Corrected.

InProof:
Oh I see, so there is no definition in your library for the sum of public keys using X25519? Is it the problem? Yes, this is also an alternative like you suggest. I could directly reveal the opening for the amount commitment too. I will think a bit more about what makes more sense to do (implement the missing crypto for X25519 or using this new variant).

ReserveProofs:
Oh, I see the idea. Since the enotes have three bases (which is not specified in the specs that I was using to study) then you can make composition proofs directly on the enotes and prove that you have ownership on them. Cool, thanks.

UnspentProofs:
Please have a look on this scheme I came up with and let me know what you think. I think it is simple and works fine though we have to reveal kbU.

I will think a bit more about the Inproofs and how to integrate it with the Reserve and Unspent proofs. Thank you for reviewing this first draft!
draft_sp_v2.pdf

[UkoeHB]

SpendProof:
Suppose we made a transaction, and want to prove it. (ztm2 pg 76)

The values t_k and t_c are discarded, and definitely won't be recoverable from chain data. They are not necessary anyway. As long as the key image is reproduced then we have proven that our account made the transaction ('I made this tx' is shorthand for 'my wallet made this tx'; there is no way to actually prove a given human made a tx in the first place). Your Option 1 should suffice then (with new random offsets t_k and t_c).

implement the missing crypto for X25519

I strongly discourage this, implementing crypto primitives is a dangerous activity especially if you have limited experience.

UnspentProofs:

Ok, I agree with your approach. Given nominal key image KI':

1. Expose k_g G, (k_x + k_vb) X, (k_u + k_m) U for onetime address Ko. Verify that Ko ?= k_g G + (k_x + k_vb) X + (k_u + k_m) U.
2. crypto::signature() on k_g G
3. sp::MatrixProof for keys {(k_x + k_vb) X, (k_x + k_vb) * KI'} on base keys {X, KI'}
4. sp::MatrixProof for key (k_u + k_m) U on generator U
5. if (k_x + k_vb) * KI' == (k_u + k_m) U then KI' is the key image of Ko

In general I recommend avoiding custom signature schemes where possible. Right now it looks like all you really need for the audit framework is a new Schnorr scheme that will take a user-defined generator/base key. Missing that, you could even abuse sp::DualBaseVectorProof as a temporary solution (just let the second part of the proof equal the first part).

[DangerousFreedom1984]

Cool. Thanks for the answers. I believe we have a minimum consensus about the theoretical framework. I will move to implementing it now.

I agree that implementing new crypto should be avoided. I will use your recommendation for the Inproofs but could you tell me exactly the problem with X25519? Btw, I just saw that bulletproofs_plus2.cpp is still using addKeys2, which we know that is wrong for some cases that should never be there but anyway I think it is better to use addKeys. Could you change it later?

About the UnspentProofs, yeah, that's the idea. But I believe I can make a big Schnorr like I wrote. I will look your answer again when I'm implementing it.

[UkoeHB]

the problem with X25519?

"There is definitely not an extensive X25519 library ready to go for that."

Btw, I just saw that bulletproofs_plus2.cpp is still using addKeys2, which we know that is wrong for some cases that should never be there but anyway I think it is better to use addKeys

There is nothing wrong with addKeys2(). bulletproofs_plus2.cpp is just a copy of bulletproofs_plus.cpp with minor changes related to the seraphis transcript utility and multiexp utility. When copying code like this, it is important to minimize the diffs.

But I believe I can make a big Schnorr like I wrote.

Sure you can do it, but don't do it unless you need to (you don't in this case).

[UkoeHB]

Here's a summary of updated proofs. I note the minimum pieces required for a proof, although additional context/tracking information might be required (i.e. to help verifiers identify what enote or tx the proof is about). These assume some jamtis updates are implemented.

• address ownership proof: prove that an address is owned by the prover (or the prover is cooperating with the owner, which is equivalent); must include a custom message provided by the verifier in some way (otherwise this proof says nothing about the person who transmits the proof)
  • prover: addr = K_1 OR K_s = k_vb X + k_m U, composition proof on addr with offset k_g_offset = Hn(addr) added in like addr += k_g_offset G (composition proofs require a non-zero G component), custom message m_custom
  • verifier: validate the composition proof
• address index proof: prove that an address was constructed from an index j
  • prover: K_s = k_vb X + k_m U, j, H_32[s_ga](j), K_1
  • verifier: recompute K_1 from the other pieces
• enote ownership proof: prove an enote is owned by an address K_1
  • prover: q, K_1, Ko
  • verifier: recompute the enote's onetime address Ko from the other pieces (works for both normal and selfsend enotes)
  • disclaimer: this does not prove that the owner of address K_1 can actually spend the enote. q could be computed in violation of the jamtis spec, in which case the owner of K_1 may never recover the enote and so the funds are effectively burned.
• enote amount proof: prove an enote has a particular amount a
  • prover: a, x, C
  • verifier: recompute the enote's amount commitment C from the other pieces
• enote key image proof: prove a key image KI corresponds to a particular onetime address Ko
  • prover: composition proof on Ko
  • verifier: validate proof
• enote unspent proof: prove an enote was not spent by a particular tx input with key image KI
  • use technique described here
• funded tx proof: prove that you funded a particular tx (without exposing the tx inputs)
  • prover: produce a new masked onetime address K"_new = t_k_new G + Ko, make a composition proof on K"_new signing a custom message m_custom provided by the verifier
  • verifier: check the proof and that the proof's key image matches the tx input (note: no need to recreate the grootle proofs, you just need to sign a message authenticating yourself as the tx funder)
  • note: there is currently no way to show the input amount without revealing which enote was spent unless you remember/cached the tx input's amount mask t_c and can provide a, x + t_c to a verifier in an enote amount proof to reproduce the input's masked commitment C"
• enote sent proof: prove an enote was sent to a particular address K_1
  • use an enote ownership proof (note: instead of exposing the enote ephemeral privkey xr as recommended here, which doesn't work for selfsend enotes) + enote amount proof
• reserve proof: prove you have X available funds
  • prover: enote ownership proof + enote amount proof + enote key image proof for each enote you want to expose; include an address ownership proof for each K_1 that owns at least one enote in the reserve proof (they need to sign a custom message provided by the verifier)
  • verifier: check the proofs, check that the enotes exist on-chain (check each onetime address and amount commitment pair), look up key images to see if they are on-chain

[UkoeHB]

These proofs have been implemented in the seraphis_main/sp_knowledge_proof_* files based on an initial draft provided by @DangerousFreedom1984 in this PR.