NIP-13 - A CPU friendly Proof Of Work algorithm should be preferred.

[FreeTrade]

The current proposal uses SHA256 hashing for POW to incur a cost on a message creator.

For a spammer, this is quite agreeable - he can purchase an ASIC and can churn out spam in a much more efficient way than ordinary users.

Desktop and mobile users take a lot longer to create the equivalent POW - I suspect this will lead to a situation where ordinary users will not be able to create sufficient POW in a reasonable time and would need to purchase the POW from an SHA256 as a service provider.

Better if a CPU friendly POW algorithm were used - this would put desktop/mobile users on a more equal footing with spammers and make it possible for users to create messages without engaging a third party which may be inconvenient or privacy compromising.

[mikedilger]

Or maybe it should be that the POW algorithm is maximally memory-hard like scrypt. There are ASICs for scrypt but they are a lot slower and/or much more expensive.

[FreeTrade]

Or maybe it should be that the POW algorithm is maximally memory-hard like scrypt. There are ASICs for scrypt but they are a lot slower and/or much more expensive.

Yes, memory-hard is advantageous. Scrypt would be an improvement, but I'm thinking state of the art for POW to even things up for ordinary users is probably RandomX. This is the POW used by Monero for ASIC/GPU resistance.

[gkbrk]

Implementing SHA256 is very easy, takes a few lines of code (around 100 in TypeScript), has implementations in every programming language you can think of.

In fact, all components of Nostr are like this currently. secp256k1 can be implemented in little code, going from a TCP socket to a websocket is a few lines of Python etc. In comparison, RandomX includes a lot of different cryptographic algorithms and a bytecode VM on top. Hardly a 100-line project.

If we're moving away from SHA256, I'd recommend something more like Argon2. It has parameters that can be tweaked for memory hardness and compute time, but it is something that can be written and understood easily.

[mikedilger]

sorry my mouse went nuts

[arthurfranca]

There's also network-bound PoW also know as proof of interaction in which the delay/cost comes from the latency between requests/responses. Maybe could use a set of relays as nodes. Just an option if someone wants to take a look at as I have no experience with this.

[majestrate]

Implementing SHA256 is very easy, takes a few lines of code (around 100 in TypeScript), has implementations in every programming language you can think of.

In fact, all components of Nostr are like this currently. secp256k1 can be implemented in little code, going from a TCP socket to a websocket is a few lines of Python etc. In comparison, RandomX includes a lot of different cryptographic algorithms and a bytecode VM on top. Hardly a 100-line project.

If we're moving away from SHA256, I'd recommend something more like Argon2. It has parameters that can be tweaked for memory hardness and compute time, but it is something that can be written and understood easily.

a KDF for proof of work isn't appropriate. unfortunately because of coin world most have not learned that the point of PoW itself is trivial verification with computationally hard generation. a KDF is not that.

i would highly suggest a latency bound solution like @arthurfranca suggests as you can't fake that unless you have a time machine. it's also super fast.

that being said, sha256 itself is fine as a primitive for PoW given that there is much more involved than just a flat hash by itself.

[barkyq]

There's also network-bound PoW also know as proof of interaction in which the delay/cost comes from the latency between requests/responses. Maybe could use a set of relays as nodes. Just an option if someone wants to take a look at as I have no experience with this.

Interesting. Could also have a simple POL (proof of latency) for establishing a websocket connection.

e.g., Relay X only accepts REQ and EVENT messages through a websocket connection from an AUTH'ed user. But Relay X only sends the AUTH challenge after N PING-PONG cycles on the websocket connection (Relay Ping, Client Pong, not the other way around). Prior to successful AUTH, the relay sets the maximum # of bytes read-limit from the client to something very small.

Once a user establishes the websocket connection, it will hopefully be long-lived. Enough to make the latency POW not too frustrating. The websocket could be rate-limited in other ways. If a user pushes excessive EVENTs or makes REQs which return 1000s of events, the relay could just close the websocket and the client has to POL all over again.

Perhaps instead of PING - PONG it could be WAIT - ACK or something, and the WAIT could have a time remaining for clients to display. Also perhaps AUTH should not be piggy-backed like this, and maybe want to let the user AUTH during the WAIT period in case there is a fast-track whitelist.

[AveragePythonEnjoyer29]

Implementing SHA256 is very easy, takes a few lines of code (around 100 in TypeScript), has implementations in every programming language you can think of.

In fact, all components of Nostr are like this currently. secp256k1 can be implemented in little code, going from a TCP socket to a websocket is a few lines of Python etc. In comparison, RandomX includes a lot of different cryptographic algorithms and a bytecode VM on top. Hardly a 100-line project.

If we're moving away from SHA256, I'd recommend something more like Argon2. It has parameters that can be tweaked for memory hardness and compute time, but it is something that can be written and understood easily.

Here's a few good algorithms possible for usage:

• Argon2
• Scrypt
• RandomX

While RandomX is the hardest to implement (guessing from the code) it might promise the most customizability, and seeing as it's ASIC resistant by nature i suppose we won't have any problems with it in the future aswell

However, seeing as the network will grow larger and larger, i think we have to take in thought the environmental concerns. Bitcoin already uses a

Maybe we can implement a different type of proof? This needs some more research

[earonesty]

note: argon2 allows trivial verification as well. and the hash will not need to be "salted" since we're not using it as a kdf. randomx is definitely the worst choice, it's a big fat hack, hard to implement without bugs, and i would never propose to include it an any security product.

[LouisLoyaX]

Perhaps instead of PING - PONG it could be WAIT - ACK or something, and the WAIT could have a time remaining for clients to display. Also perhaps AUTH should not be piggy-backed like this, and maybe want to let the user AUTH during the WAIT period in case there is a fast-track whitelist.

The issue with this is if you are trying to restore a backup of all your events into a new relay it would take forever. If, you have a cryptographic proof that all those events already did their proof-of-work switching between relays is almost inmediate. This is very important for censorship resistantance.

[majestrate]

On Mon, 10 Apr 2023 07:31:00 -0700 Louis Saberhagen ***@***.***> wrote: > Perhaps instead of PING - PONG it could be WAIT - ACK or something, > and the WAIT could have a time remaining for clients to display. > Also perhaps AUTH should not be piggy-backed like this, and maybe > want to let the user AUTH during the WAIT period in case there is a > fast-track whitelist. The issue with this is if you are trying to restore a backup of all your events into a new relay it would take forever. If, you have a cryptographic proof that all those events already did their proof-of-work switching between relays is almost inmediate. This is very important for censorship resistantance.

you could always use bitcoin's top block hash as an unspoofable proof of time. then you can defer submission until the next block which is plenty of cooloff to deter spammers.

…

-- ~jeff

[LouisLoyaX]

TOR Project is moving to CPU Proof-Of-Work to curtail spam/ddos attacks on the network. See PR here.

They are using an algorithm called Equi-X that is simpler and has faster (instant) verification than "Random-X".