5

Ring signatures alone would allow double spending, so Monero (as a result of following the CrpytoNote whitepaper) has to use a 'key image', which is the same across identical transactions and hence causes attempts at double spending to be rejected.

The key image is formed I = x*H(P), with I the key image, x the private key, H a deterministic hash function, and P a ephemeral public key for use in this transaction only.

My question is, in Monero's specific case, what hashing algorithm does H represent?

Improve this question

1 Answer 1

Reset to default
4

Looking at the code, we can see how it's generated.

void crypto_ops::generate_key_image(const public_key &pub, const secret_key &sec, key_image &image) {
    ge_p3 point;
    ge_p2 point2;
    assert(sc_check(&sec) == 0);
    hash_to_ec(pub, point);
    ge_scalarmult(&point2, &sec, &point);
    ge_tobytes(&image, &point2);
  }

The hash_to_ec function is called to hash pub (which is your P) into point, giving us your H(P). Then, scalar multiplication is performed and result passed into point2, which would be your x*H(P). Some transfromation ge_tobytes is applied and the result is passed into image which is your I.

I'm not sure what this ge_tobytes transformation does, though. It could be just changing the format of I in memory. Implementation specific, I suppose.

The hash_to_ec function is presented below.

static void hash_to_ec(const public_key &key, ge_p3 &res) {
    hash h;
    ge_p2 point;
    ge_p1p1 point2;
    cn_fast_hash(std::addressof(key), sizeof(public_key), h);
    ge_fromfe_frombytes_vartime(&point, reinterpret_cast<const unsigned char *>(&h));
    ge_mul8(&point2, &point);
    ge_p1p1_to_p3(&res, &point2);
  }

We see that the cn_fast_hash function is called, which would be the Keccak hash function. After getting the hash h, it is passed through some functions, which I suspect perform scalar multiplication of h with something, but my understanding stops here. This ge_fromfe_frombytes_vartime might be of interest as Shen Noether did a dedicated write-up on it. Also, here we see the importance of using a secure hash function for the key images. Apparently, to do this something after the Keccak is quite important.

Shen Noether's implementation in Python could provide some insights as well, but I'm not sure if it's up to date.

Improve this answer
3
  • Thanks so much! I think ge_tobytes means group element to bytes, so it's just typecasting the input from a group element (or more specifically an elliptic curve point) to a byte array. Thanks again :)
    – bekah
    Commented Nov 25, 2016 at 23:00
  • 1
    @bekah No problem at all! Fyi, I've bumped into something regarding ge_fromfe... which might be of interest as well. Updated the answer.
    – JollyMort
    Commented Nov 26, 2016 at 9:58
  • 1
    See Signature, step 1, Section 3.3 of github.com/kurtmagnus/Monero-RCT-report/blob/master/main.pdf It's essentially private key * Hash_p(public key) (Hash_p is a hash function that returns an EC point)
    – Kurt
    Commented Mar 7, 2018 at 22:52

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.