Try NatureHacker's Free Organic Teeth Powder!
Proof of Individual Work (PoIW) or Proof of Small Work (PoSW) or Proof of Tiny Work (PoTW) or U (micro) Proof of Work (uPoW) or You Proof of Work (YouPoW)
The future is proof of work.
I want to make a search engine where you have to prove you (or someone else) do work to boost your URL in the search engine algorithm. Here are some ways I have described to do this.
1. Proof of Burn - Proving that you sent an amount (specified or not) of cryptocurrency such as monero or bitcoin to a unusable address.
2. Proof of Captcha - Proving that you are "human" - in reality a proof of "human" work (PoHW).
3. Proof of Hits - Proving that your post is popular.
The great thing about all of these methods to boost your (or someone else's) URL in search rankings is they are anonymous and don't require things that law enforcement would want to scrape out of our open source database unlike mobile or email or IP verification.
Another new proof of work is described here. I will call it Proof of Individual Work.
4. Proof of Individual Work - Proving that "you" did an intensive "cpu" operation.
"CPU" can be any type of machine work, but preferably cpu since graphics cards and asic's are in limited supply and also have limited use compared to CPU's. Almost everyone on the planet has access to a cpu.
"You" can be anyone who believes in the thing (in this example; URL) to expend work to promote it.
What is the difference between proof of individual work (PoIW) compared to standard proof of work (PoW)? PoIW can (but doesn't have to be) be done by your very own computer. PoW is basically a socialized work. Your computer will virtually assuredly never win a proof of work challenge. This isn't so bad since you can trade someone who was lucky enough to win a PoW challenge and get a little bit of cryptocurrency from them which you can subsequently burn and provide proof that you did that (proof of burn) to raise your URL ranking in the search algorithm (or any other use). So proof of burn becomes a sort of individualized proof of work that mimics PoIW.
So then what is the difference between Proof of Burn (PoB) and Proof of Individual Work (PoIW)?
Firstly PoIW doesn't require you to acquire cryptocurrency. Why does this matter? It is very hard to trade something you have for cryptocurrency with an anonymous person. Since they are anonymous firstly you probably will have a hard time figuring out what they want to trade for a bit of their currency. What this does is create a really big problem. This problem is that bitcoin or any cryptocurrency wants to be traded autonomously so what this means is it will almost always trade for government backed currency or any other form of global reserve currency almost exclusively. So the whole point of bitcoin becomes moot when it can only be traded for Central Banker Digits (US dollars or equivalent). Another way to get a little piece of cryptocurrency is to join a socialized pool. Again this is putting your machine in a situation where it is dependent on a socialized system which you may or may not want to be a part of. Pool's are counter to the "one cpu one vote" vision of cryptocurrency and can be used to centralize control of the cryptocurrency.
So how does PoIW break us out of the cryptocurrency paradigm to prove work? Because we can give an individual computer a task that they can complete in a reasonable time frame to prove they did work. How do we do that? One method is we can generate a random number of sufficient length (starting with perhaps 116 digits) where the computer in question can return to us the prime factors of the number. Prime factorization of numbers over 100 digits is known to not gain significant speed up from gpu's or asic's because it requires a General Number Field Sieve (GNFS). When the factors are found and returned to us we can verify that each factor found is prime with a primality test (which should only take fractions of a second for factors of this size) and validate that all the factors multiplied together gives the random number we gave them to factor. Within under a second we can verify that they completed the work we gave them, all without having to require cryptocurrency.
Now the biggest vulnerability in this process of PoIW is the generating of the random number. Firstly the random number may not be exactly random and vulnerabilities can be found in that. Secondly the generation of the random number is centralized by the server so could be open to abuse of the server owner. How can we generate a true random number? For this we have to go back to cryptocurrency I believe to give us a true random number that everyone can agree is random. To do this we can simply look at the latest merkle root of a block of a cryptocurrency and hash it with a hashing algorithm into the length we want (say 116 digits) or hash it into a larger number than we want then truncate down to the digit count we want.
So for example taking the monero blockchain as an example; the central authority (server) could look at the merkle root of the latest monero block, hash it with SHA-384 and convert to base 10 (decimal) which is 116 digits then present this number to the person who wants to boost their URL so they can factor it for us.
Now we have a problem. Say 2 people are trying to boost their URL at the same time. Hashes are deterministic so both of these people will have the same number to factor. Again we are back to the cryptocurrency problem since this is no longer an individualized proof of work and only one person can prove their work. What can we do?
Well we can allow people to select their own unique, one time use, nonce. So they will, for example, take their nonce and multiply it by the merkle root of the latest monero block, then hash that in SHA-384, then present to the server the prime factors of that number. This would work since the server can then check that the arbitrary nonce that the person selected, multiplied by the merkle root is equal to the number that the person factored, and the factors themselves can be checked for primality and that they indeed multiply to give the number.
Great. Now we have this proof of individual work. And as long as our database doesn't say that someone else has factored that same number and claimed the URL boost, then this person will get it, no matter how long they take to find the prime factorization. The only downside to this is the person can continually change their nonce to try to get an "easy" number to factor - say a number where the only factors are 2's or something therefore nullifying the whole prime factorization favoring CPU's over ASIC's in the first place. One way to get around this problem (this problem I will term "nonce flipping" or "nonce forcing" or "nonce grinding") is to require that the number of prime factors of their number be within a set range. "Easy" to factor numbers will tend to have a high number of factors or a low number of factors. And/or we can require that the prime factorization gives numbers with certain length factors. So say for 116 digit length number to factor, we can require that at least one of the factors is at least say 50 digits long. And/or we can say there must be between 7 and 15 prime factors, and/or that a certain number of the prime factors must be unique. The downside of this is that even if the person factors the number the "right" way that the number may just not meet the requirements of the PoIW and you would have to try again. Hopefully we can tune this so that the average time to find a solution to the problem on a modern computer is within a given time frame, say 5-10 minutes or whatever range we want.
--------------
Example parameters: (what I will likely start with and tweak if needed)
1. 116 digit number from SHA-384 truncated to 101 digits (335 bits)
2. No prime factors can be larger than 51 digits long (so an "RSA number" could work)
3. All prime factors must be distinct
For #2 this prevents "a prime number multiplied by 2 that gives the number" since it would be too fast to just find that a factor was 2 then perform a primality test on the remaining number and find it was prime.
For #3 this prevents a number like 120000000000...0000 that has a ton of (non-distinct) factors.
my estimate is this would take no more than 4 factoring attempts on average (more likely closer to 2 factoring attempts at a total of ~3 hours processing time) to find a prime factorization that satisfies all these parameters. A fast way to cut down on non distinct factors is make sure the number is not divisible by multiple 2's, 3's, 5's, or 7's before trying to factor farther. If it is, change your nonce to roll a different number to factor.
will take around 14 hours to factor a 116 digit number on a modern ryzen
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E384%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E384%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
if we truncated to 100 digits it would be about an hour
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E330%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E330%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
101 digits 335 bits, ~1.5 hours
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E335%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E335%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
------------------
Nice, so now we have an individualized proof of work so that a person can prove they completed an intensive CPU process to say they deserve their URL to be boosted. Well we still may have a slight problem. Say I don't have the only search engine index that works like this. The person can simply complete one of these proof of works and then get his URL boosted on my engine and also on another engine at the same time. So now the proof of work is not really valid since only say half the work was actually done for my search engine. How do we make sure that the work is only done on our search engine? One way is that we (the search engine or any other organization of course) give our own nonce. So there would be our nonce, the person's nonce, the merkle root of the current external system state like current monero block, and the SHA-384 hash of all of that. This isn't so bad of an option because the person can still keep re-rolling his own nonces as required but chances are the centralized nonces will not be the same between my search engine and the other guy's search engine. Also there is no way for us, the central power, to give "good or bad" nonces to someone to effect how easy it is for them to factor since both the merkel root and the hashing algorithm and the person's own nonce are out of our control.
Also just to be sure that our given nonce doesn't ever line up with another search engines given nonce, we could set a time limit of say 1-7 days for the answer to be found after we issue the nonce for the current merkle root. The longer we can allow the person to have, the better to allow a person to use something like a raspberry pi if they want.
So I think we have a workable solution for Proof of Individual Work. Of course this can be done with typical sha-256 or other hashing algorithm instead of the prime number factorization but I think we should prefer algorithms that are hard to speed up with gpu's, fpga's, and asic's.
how long to factor a number
https://math.stackexchange.com/questions/1640930/how-long-does-the-general-number-field-sieve-actually-take
instructions per second of various processors
https://en.wikipedia.org/wiki/Instructions_per_second
Some example factorizations of 50 digit numbers
near half-digit gives 7 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485779652341111242122636475869052346
nearly half digit gives 5 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485870652442112242122436475869052346
same 6 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485870902442312242122436475869052346
2 distinct, does not satisfy req
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112242676485779453342111242122636425469052346
Proof of Individual Work (PoIW) or Proof of Small Work (PoSW) or Proof of Tiny Work (PoTW) or U (micro) Proof of Work (uPoW) or You Proof of Work (YouPoW)
The future is proof of work.
I want to make a search engine where you have to prove you (or someone else) do work to boost your URL in the search engine algorithm. Here are some ways I have described to do this.
1. Proof of Burn - Proving that you sent an amount (specified or not) of cryptocurrency such as monero or bitcoin to a unusable address.
2. Proof of Captcha - Proving that you are "human" - in reality a proof of "human" work (PoHW).
3. Proof of Hits - Proving that your post is popular.
The great thing about all of these methods to boost your (or someone else's) URL in search rankings is they are anonymous and don't require things that law enforcement would want to scrape out of our open source database unlike mobile or email or IP verification.
Another new proof of work is described here. I will call it Proof of Individual Work.
4. Proof of Individual Work - Proving that "you" did an intensive "cpu" operation.
"CPU" can be any type of machine work, but preferably cpu since graphics cards and asic's are in limited supply and also have limited use compared to CPU's. Almost everyone on the planet has access to a cpu.
"You" can be anyone who believes in the thing (in this example; URL) to expend work to promote it.
What is the difference between proof of individual work (PoIW) compared to standard proof of work (PoW)? PoIW can (but doesn't have to be) be done by your very own computer. PoW is basically a socialized work. Your computer will virtually assuredly never win a proof of work challenge. This isn't so bad since you can trade someone who was lucky enough to win a PoW challenge and get a little bit of cryptocurrency from them which you can subsequently burn and provide proof that you did that (proof of burn) to raise your URL ranking in the search algorithm (or any other use). So proof of burn becomes a sort of individualized proof of work that mimics PoIW.
So then what is the difference between Proof of Burn (PoB) and Proof of Individual Work (PoIW)?
Firstly PoIW doesn't require you to acquire cryptocurrency. Why does this matter? It is very hard to trade something you have for cryptocurrency with an anonymous person. Since they are anonymous firstly you probably will have a hard time figuring out what they want to trade for a bit of their currency. What this does is create a really big problem. This problem is that bitcoin or any cryptocurrency wants to be traded autonomously so what this means is it will almost always trade for government backed currency or any other form of global reserve currency almost exclusively. So the whole point of bitcoin becomes moot when it can only be traded for Central Banker Digits (US dollars or equivalent). Another way to get a little piece of cryptocurrency is to join a socialized pool. Again this is putting your machine in a situation where it is dependent on a socialized system which you may or may not want to be a part of. Pool's are counter to the "one cpu one vote" vision of cryptocurrency and can be used to centralize control of the cryptocurrency.
So how does PoIW break us out of the cryptocurrency paradigm to prove work? Because we can give an individual computer a task that they can complete in a reasonable time frame to prove they did work. How do we do that? One method is we can generate a random number of sufficient length (starting with perhaps 116 digits) where the computer in question can return to us the prime factors of the number. Prime factorization of numbers over 100 digits is known to not gain significant speed up from gpu's or asic's because it requires a General Number Field Sieve (GNFS). When the factors are found and returned to us we can verify that each factor found is prime with a primality test (which should only take fractions of a second for factors of this size) and validate that all the factors multiplied together gives the random number we gave them to factor. Within under a second we can verify that they completed the work we gave them, all without having to require cryptocurrency.
Now the biggest vulnerability in this process of PoIW is the generating of the random number. Firstly the random number may not be exactly random and vulnerabilities can be found in that. Secondly the generation of the random number is centralized by the server so could be open to abuse of the server owner. How can we generate a true random number? For this we have to go back to cryptocurrency I believe to give us a true random number that everyone can agree is random. To do this we can simply look at the latest merkle root of a block of a cryptocurrency and hash it with a hashing algorithm into the length we want (say 116 digits) or hash it into a larger number than we want then truncate down to the digit count we want.
So for example taking the monero blockchain as an example; the central authority (server) could look at the merkle root of the latest monero block, hash it with SHA-384 and convert to base 10 (decimal) which is 116 digits then present this number to the person who wants to boost their URL so they can factor it for us.
Now we have a problem. Say 2 people are trying to boost their URL at the same time. Hashes are deterministic so both of these people will have the same number to factor. Again we are back to the cryptocurrency problem since this is no longer an individualized proof of work and only one person can prove their work. What can we do?
Well we can allow people to select their own unique, one time use, nonce. So they will, for example, take their nonce and multiply it by the merkle root of the latest monero block, then hash that in SHA-384, then present to the server the prime factors of that number. This would work since the server can then check that the arbitrary nonce that the person selected, multiplied by the merkle root is equal to the number that the person factored, and the factors themselves can be checked for primality and that they indeed multiply to give the number.
Great. Now we have this proof of individual work. And as long as our database doesn't say that someone else has factored that same number and claimed the URL boost, then this person will get it, no matter how long they take to find the prime factorization. The only downside to this is the person can continually change their nonce to try to get an "easy" number to factor - say a number where the only factors are 2's or something therefore nullifying the whole prime factorization favoring CPU's over ASIC's in the first place. One way to get around this problem (this problem I will term "nonce flipping" or "nonce forcing" or "nonce grinding") is to require that the number of prime factors of their number be within a set range. "Easy" to factor numbers will tend to have a high number of factors or a low number of factors. And/or we can require that the prime factorization gives numbers with certain length factors. So say for 116 digit length number to factor, we can require that at least one of the factors is at least say 50 digits long. And/or we can say there must be between 7 and 15 prime factors, and/or that a certain number of the prime factors must be unique. The downside of this is that even if the person factors the number the "right" way that the number may just not meet the requirements of the PoIW and you would have to try again. Hopefully we can tune this so that the average time to find a solution to the problem on a modern computer is within a given time frame, say 5-10 minutes or whatever range we want.
--------------
Example parameters: (what I will likely start with and tweak if needed)
1. 116 digit number from SHA-384 truncated to 101 digits (335 bits)
2. No prime factors can be larger than 51 digits long (so an "RSA number" could work)
3. All prime factors must be distinct
For #2 this prevents "a prime number multiplied by 2 that gives the number" since it would be too fast to just find that a factor was 2 then perform a primality test on the remaining number and find it was prime.
For #3 this prevents a number like 120000000000...0000 that has a ton of (non-distinct) factors.
my estimate is this would take no more than 4 factoring attempts on average (more likely closer to 2 factoring attempts at a total of ~3 hours processing time) to find a prime factorization that satisfies all these parameters. A fast way to cut down on non distinct factors is make sure the number is not divisible by multiple 2's, 3's, 5's, or 7's before trying to factor farther. If it is, change your nonce to roll a different number to factor.
will take around 14 hours to factor a 116 digit number on a modern ryzen
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E384%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E384%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
if we truncated to 100 digits it would be about an hour
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E330%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E330%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
101 digits 335 bits, ~1.5 hours
https://www.wolframalpha.com/input/?i=%28%28exp%281.902*%28%28ln%282%5E335%29%29%5E%281%2F3%29%29*%28%28ln%28ln%282%5E335%29%29%29%5E%282%2F3%29%29%29%29%2F%2810%5E12%29%29%2F3600
------------------
Nice, so now we have an individualized proof of work so that a person can prove they completed an intensive CPU process to say they deserve their URL to be boosted. Well we still may have a slight problem. Say I don't have the only search engine index that works like this. The person can simply complete one of these proof of works and then get his URL boosted on my engine and also on another engine at the same time. So now the proof of work is not really valid since only say half the work was actually done for my search engine. How do we make sure that the work is only done on our search engine? One way is that we (the search engine or any other organization of course) give our own nonce. So there would be our nonce, the person's nonce, the merkle root of the current external system state like current monero block, and the SHA-384 hash of all of that. This isn't so bad of an option because the person can still keep re-rolling his own nonces as required but chances are the centralized nonces will not be the same between my search engine and the other guy's search engine. Also there is no way for us, the central power, to give "good or bad" nonces to someone to effect how easy it is for them to factor since both the merkel root and the hashing algorithm and the person's own nonce are out of our control.
Also just to be sure that our given nonce doesn't ever line up with another search engines given nonce, we could set a time limit of say 1-7 days for the answer to be found after we issue the nonce for the current merkle root. The longer we can allow the person to have, the better to allow a person to use something like a raspberry pi if they want.
So I think we have a workable solution for Proof of Individual Work. Of course this can be done with typical sha-256 or other hashing algorithm instead of the prime number factorization but I think we should prefer algorithms that are hard to speed up with gpu's, fpga's, and asic's.
how long to factor a number
https://math.stackexchange.com/questions/1640930/how-long-does-the-general-number-field-sieve-actually-take
instructions per second of various processors
https://en.wikipedia.org/wiki/Instructions_per_second
Some example factorizations of 50 digit numbers
near half-digit gives 7 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485779652341111242122636475869052346
nearly half digit gives 5 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485870652442112242122436475869052346
same 6 distinct
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112142576485870902442312242122436475869052346
2 distinct, does not satisfy req
https://www.wolframalpha.com/input/?i=prime+factorization+of+11112112242676485779453342111242122636425469052346
No comments:
Post a Comment
Thank you for your feedback! Sharing your experience and thoughts not only helps fellow readers but also helps me to improve what I do!