3

For research purposes, I want to know the following:

  1. What is the exact size of the set of already spent key images and how it can be checked? Do we need to download the Monero blockchain to get the size?
  2. Using the is_key_image_spent api, we can check if a key image is a member of the set of already spent key images or not. Can this set be made a zero-knowledge set using some accumulator so that a zero-knowledge set membership or non-membership proof can be given for a particular group element (key image) bypassing this api? Does there exist any accumulator suitable for this purpose?

Thanks in advance for your insights.

Improve this question

2 Answers 2

Reset to default
3
  1. Each transaction input has a key image, and there are around 2.1 inputs per transaction on average. So, the 'key image set' is around 2x the number of transactions on-chain.
  2. I do not believe a zero-knowledge proof is currently available, although you may find the description of a hypothetical 'unspent proof' in section 8.1.5 of Zero to Monero 2 is in the right direction.
Improve this answer
3
  • Thanks for the answer @koe. What is the total number of transactions on-chain so far? Also, is there any difficulty to implement UnspentProve, particularly in ReserveProof?
    – trijia
    Commented Jul 24, 2020 at 6:48
  • 1
    I think it's on the order of 10-20mill. Hopefully UnspentProofs can be implemented in Monero at some point, although when that would happen is hard to say. They aren't incredibly difficult to implement, but not super easy either.
    – koe
    Commented Jul 24, 2020 at 7:36
  • 2
    I see 41103595 outputs (output_txs), 35830737 spent keys (spent_keys) and 10325681 txs (tx_indices) in the database right this moment.
    – jtgrassie
    Commented Jul 24, 2020 at 7:55
2

What is the exact size of the set of already spent key images and how it can be checked? Do we need to download the Monero blockchain to get the size?

Yes, you'd need to download the blockchain. Once you have synced the blockchain, you can obtain the count of spent key images by inspecting the database like:

mdb_stat -s spent_keys ~/.bitmonero/lmdb/
...
Entries: 35830820

Using the is_key_image_spent api, we can check if a key image is a member of the set of already spent key images or not. Can this set be made a zero-knowledge set...

Key images already provide a form of zero-knowledge proof - proof that there is no double-spend without divulging which output is being spent. Each ring of outputs (so tx inputs) has a key image which is unique to one of the outputs in the ring but crucially doesn't divulge which is the actual output being spent.

Improve this answer
2
  • I agree that the key images provide a form of zkp. But for reserve proof, the prover needs to reveal key images for unspent outputs. This is detrimental to the privacy for future transaction. This makes proving a one-time address unspent without revealing the key image important. UnspentProof as suggested by @Koe is a solution to this problem. I was initially wondering about existence of any zero-knowledge accumulator using which we could show that a key image has not appeared without revealing it. I am still curious to know about any such accumulator which could be used for this purpose.
    – trijia
    Commented Jul 24, 2020 at 12:50
  • I have never heard about an accumulator for key images, and I'm not even sure what that would look like.
    – koe
    Commented Jul 25, 2020 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.