So, I'm building a system loosely based on the S/Kademlia principles and I have a question.

I generate IDs from hashing a public key such that $ID = H(PK)$. Further, I say that for an ID to be valid the $H(ID) = H(H(PK))$ must start with $z$ leading zeroes.

From this, I have two questions.

  1. Is it ok not to include salt in the PoW scheme, but instead merely generate new keys until the constraints of the scheme have been met?

  2. If I were to trim the ID by only using the $n$ first bits, would the PoW scheme not grant $2^{z/2}$ higher collision resistance, such that the 50% would be $2^{(n/2)+(z/2)}$?

My thinking in the second question is that if $n = 0$ and $z = 256$, even though all keys would generate collisions only after $2^{256/2}$ attempts would there be a 50% chance for satisfying the constraints.

  • $\begingroup$ Salt is free to play, changing PK is not a good idea. How do you define the collision resistance? It is a property of the Hash function not the input space, rather the output size is important. You reduced the double hashing collision. Just consider how easy the collision in $H(PK)$ $\endgroup$
    – kelalaka
    Commented May 10 at 18:06
  • $\begingroup$ Well from my (very limited) understanding, theres a 50% risk of collission for a non-broken hash function with a n-bit digest after $2^{n/2}$ attempts, what with the birthday attack. And hence, since i want to trim the digest, this trimming would make the digest more prone to collision. The reason I want to avoid salt is I do not want to have to transmit it every time verification is needed. Why is it not ok to generate new keys rather than salt? $\endgroup$
    – Lullen
    Commented May 11 at 12:46
  • $\begingroup$ "do not want to have to transmit" - could depending on mutually-known state be an option? such as the current time? $\endgroup$
    – DannyNiu
    Commented May 11 at 13:15
  • 1
    $\begingroup$ Hmm.. Well it migth, but not AFAIK. I should have maybe been clearer on the purpose. Its a p2p system in which every peer has its own ID, verifyable by its public key. The ID is generated once when the peer joins the network. And the PoW is in place to make it harder to perform "sybil-attacks" where one entity may pretend to be multiple. $\endgroup$
    – Lullen
    Commented May 11 at 14:00


Your Answer

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

Browse other questions tagged or ask your own question.