Just like the NIP13 says: you need to "mine" an id for the note that starts with as many zeroes as the difficulty you set. In the relay i just check if the number of zeros matches the mined difficulty.