Bitcoin Forum
June 21, 2024, 11:16:40 PM *
News: Latest Bitcoin Core release: 27.0 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1]
1  Bitcoin / Project Development / Re: Momentum Proof-of-Work Bounty - 30 BTC on: October 20, 2013, 05:41:55 PM

I had considered the potential for such a design.  DHT will not perform well enough, you would need 100BT ethernet or perhaps gigabit before the hash table could be filled quickly enough.  From what I can tell a SUPER COMPUTER with a ton of RAM and high-speed interconnects would give you the best performance.   Here is the difference, such a super computer could be built from commodity parts.     


Well, if the hash is so fast you could just collaborate by splitting the birthday space in N ranges and each computer just throws away any result that isn't in its range. This trades hashing speed for memory, so works with rather than against your pow.

What range do you suggest for N and how fast is the hash?
This should be possible to test.

Any time you throw away hashes because they fall outside of your memory range you move the computational complexity from the p(n) curve to the q(n) curve in my white paper.  You save on memory but the cost is far greater.   Memory and CPU power must always be paired proportionally or you will have idle memory or waisted CPU cycles.



The problem with your p(n) and q(n) curves are that they measure the probability of at least one match. What we really want to measure is the expected number of matches since due to a difficulty setting having more than one match is important. This is what gives a relationship of number of hashes/second * amount of RAM. Even if we only increase the hashes/second by a factor of two we still get twice as many matches giving linear scaling in exactly the same way as just using whatever birthdayhash algorithm you choose by itself.
2  Bitcoin / Project Development / Re: Momentum Proof-of-Work Bounty - 30 BTC on: October 19, 2013, 04:24:31 AM
But you can still gain linear increases in matches with just increasing the hashrate so at the very least you can just have an ASIC or GPU that hashes and sends the results to a CPU that manages the memory and checks for matches. GPUs will still be crazy good for it since they could hash 100s of times faster than the CPU and with 2-3GB of memory on board, the CPU would need too much memory to pull even. I think a GPU/CPU hybrid would be best in class until ASICs with the GPU doing mostly hashing and then sending the results to system RAM and the CPU which checks for matches.

With this linear increase just by increasing the hashrate the Momentum ASICs will be at least as good as the scrypt and probably much better since they could just extend an off the self system with lots of RAM and use a CPU to manage the hashtable and match checking part. Design might be a bit harder, but that's just a short term concern.
3  Bitcoin / Project Development / Re: Momentum Proof-of-Work Bounty - 30 BTC on: October 19, 2013, 03:03:44 AM
Once the RAM is full everything is a read so it'll be perfectly parallel with some negligible constant time overhead.

Improvements against scrypt for the birthdayhash will help a bit, but like you said any tricks generally translate fine into ASICs.

For your example, since the mac pro has 16 times more RAM and hashing power it will be exactly 16^2 or 256 times better. Well worth the 50x cost. Since this is quadratic it will just get worse when you get into 128GB servers.

I like the elegance of having the RAM be the main resource for hashing, but I think we have a ways to go before making it practical. I'll keep thinking about it.

Nathaniel
4  Bitcoin / Bitcoin Discussion / Re: Momentum Proof-of-Work on: October 19, 2013, 12:23:58 AM
Just saw retep's post. I think we reached similar conclusions for somewhat different reasons. Both probably valid.

Here's the link to my argument in the project thread: https://bitcointalk.org/index.php?topic=313479.msg3365654#msg3365654

Still yours is an interesting idea that I'll keep in mind.


Nathaniel
5  Bitcoin / Project Development / Re: Momentum Proof-of-Work Bounty - 30 BTC on: October 19, 2013, 12:16:22 AM
bytemaster,

First, I think the idea is quite interesting and novel. Let me summarize what you are proposing to make sure we’re on the same page. Then, I will raise my concerns with the current proposal (partly in hopes of collecting a bounty and partly because it’s a really cool idea that could be the grounds for some interesting new cryptocurrencies).

The question is whether the Momentum or scrypt give worse performance increases for specialized hardware design over typical commodity hardware already in the hands of users.

Paraphrase of your section 3 in the paper with some notes:
Take data D (transactions, previous block hash, etc), calculate H = Hash(D).
Find nonce A and nonce B such that BirthdayHash(A+H) == BirthdayHash(B+H) (in practice a nonce C, D, etc could also be required to match)
If Hash(H+A+B) < TargetDifficulty then you win.


My argument against Momentum compared to scrypt:
The way you describe the algorithm and present it in the paper is all in terms of finding pairs of birthdays that match from a large set and the probability of finding a match. While this is the intuition behind the idea of how you can require lots of RAM while still being able to verify a correct answer quickly, it does not show the real goal of a miner. A miner does not want to find one match, but as many matches as possible. This is because a miner wants as many chances at finding a hash under the difficulty as possible. When looking at number of matches, we should talk in terms of expected value.

Note that since Hash() is supposed to be trivially fast and is called so much less than other functions I just assume we have an oracle that gives us a win or loss answer for each match for clarity even though technically each match hash to be Hash(H + A + B) to determine if it’s a winner. For the rest of this explanation I’ll just talk in terms of expected matches.

Let B = the number of ‘birthdays’ (hashspace of BirthdayHash).
Let S = the number of BirthdayHash(nonce+H) stored in RAM.
Let M = maximum number that S can be given a particular system’s RAM.

If we find a new BirthdayHash(A + H), the expected number of matches ( BirthdayHash(A+H)==BirthdayHash(B+H) ) = S / B

Now we calculate the total number of expected matches during a time frame (average block creation time for instance). we take the number of BirthdayHash() we compute in that time (N). S will increase from 0 to N unless M<N, meaning we do not have enough RAM to store N results.

N * Mean(S) / B = Total expected matches
If M>=N:
Mean(S) = (1 + 2 + 3 + … + N)/N = (N+1)/2
If N<M:
Mean(S) = ((1 + 2 + 3 + … + M) + M(N-M) )/N = M, if N >> M

If M>=N: Then the system scales the same as scrypt just with the amount of hashes so I make an scrypt ASIC until N>M. At this point they would be the same basically.

If N > M but not by much: Keep deploying scrypt ASICs even though there is a minor hit once RAM is full it doesn’t hurt too bad yet. If the goal is to land in this small sliver, I think that will be very hard to predict where it will be ahead of time and will likely vary drastically between CPU/GPU/ASIC so even hitting it right on for one may miss the others.

If N >> M:
This is when the lack of RAM kills straight scrypt ASICs as a possibility so I assume this is the scenario that Momentum is designed and would be tweaked to get into.
Now the expected value is: N * M / B = Total expected matches

This means that two variables affect the total amount of mining: N the number of BirthdayHash() computed per time and M which is basically the amount of RAM. The fundamental problem I see here is that we now have quadratic scaling with increased resources rather than linear.
For example:
You have a standard system that performs N BirthdayHash() and has M RAM which then expects N*M/B matches. Someone who buys a system that costs five times as much now has 5N*5M/B matches or 25 times as much output while only paying 5 times as much.

With off the shelf hardware there will be a natural limit on RAM perhaps such that the cost increases dramatically as people have to start buying high end servers, but custom ASICs can use standard commodity RAM and while no doubt they would face some scaling and bus issues, even if ASIC makers could achieve a few multiples of the amount of RAM normal users have it would multiply by the amount of hashing power. At the same time, even if RAM isn’t increased past commodity systems, if ASIC makers can use just as much RAM as commodity systems, they can still add the same multiplier as a straight scrypt ASIC would as just increasing the number of hashes per second still scales the number of matches linearly. For this reason I believe that Momentum is worse than scrypt in terms of customized hardware in the long run. In the short term, such hardware would no doubt be harder to design than just scrypt ASICs.

Another interesting piece of the algorithm to look at is the number of nonces that have to have matching birthdays. Scaling this up to 3 or 4+ shouldn’t affect the fundamental hashes per second * RAM scaling (I don’t have time to do the math but each should be so reliant on the pair matching as to be almost identically) although it will affect the storage strategy and how you use the RAM. In fact once the number of birthdays all matching is greater than 2, pools could use this to gain advantage. Consider a pool that in addition to hashing on the same block also share any partial matches (when BirthdayHash(A+H) ==BirthdayHash(B+H) and you need C and D matching as well). Each user of the pool can then improve their odds by saving partial matches and junking some single results they had. In this scenario it makes since to join the largest pool who gives you better partial matches so your expected matches also go up increasing your contribution. This is a dangerous incentive as even with BTC we have seen some large pools without any particular incentive beyond lower variance.


All that said, it is an interesting idea and I’ll keep thinking about ways to utilize/improve it. It’s also quite possible that I’ve misunderstood your algorithm so let me know what you think. These are the kinds of ideas that we need to share and discuss in order to build new innovative cryptocurrencies and improve upon existing ones.

Let me know if anything is unclear. I'm not sure how this board does math notation.


Thanks,

Nathaniel

6  Economy / Securities / Re: [LABCOIN] IPO [BTCT.CO] - Details/FAQ and Discussion (ASIC dev/sales/mining) on: October 18, 2013, 03:09:25 PM
Sounds like it is time for us to focus on one message: "return the remaining IPO funds now."

We all knew the risks going in and one of those risks was poor management. If labcoin gives a reasonable account for spent coins and returns the rest to shareholders, then this will end as well as it can at this point. If not, I suggest those in China/Hong Kong start the process of reporting to law enforcement as a scam. I think we just need to stay on message: "return the remaining funds immediately, liquidate assets, and close down or prepare to face fraud charges."

They have had plenty of time to explain with evidence, but have chosen not to. All the speculation in this thread both towards worst outcomes and best outcomes will just distract and give labcoin more time to mess around making the situation worse.

I'll start.

Labcoin return the remaining funds immediately and close down or prepare to face fraud charges.
7  Economy / Auctions / Re: 150 direct Asicminer shares 3 day auction on: May 08, 2013, 08:50:15 PM
50 @ 1.3
8  Economy / Auctions / Re: 150 direct Asicminer shares 3 day auction on: May 08, 2013, 08:02:32 PM
50 @ 1.27
9  Economy / Auctions / Re: 150 direct Asicminer shares 3 day auction on: May 07, 2013, 07:36:10 PM
50 @ 1.22
10  Economy / Auctions / Re: [2 days]: [100 direct ASICMINER shares] on: May 07, 2013, 02:09:08 AM
50 @ 1.22
11  Alternate cryptocurrencies / Altcoin Discussion / Re: WTB 100k ChinaCoins(CHCs!!) on: May 03, 2013, 11:47:48 PM
Thanks.

Status: 17 confirmations, broadcast through 42 nodes
Date: 5/3/2013 19:36
To: trade CYkRjL5hommywVczwhECgL7zt49e2J3zzp
Debit: -802.90 CNC
Transaction fee: -4.40 CNC
Net amount: -807.30 CNC
Transaction ID: b3dc21381e2ca9cba01a724e0f317435338e33aff17f858878d06f4205f15215

Status: 1/unconfirmed
Date: 5/3/2013 19:39
From: unknown
To: LNeDtzeynmESurZBbwVos9QMytydGgdZKb (yours, label: ltcmine and notrollin and coinotron)
Credit: 16.00 LTC
Net amount: +16.00 LTC
Transaction ID: f7f5bc543d881cbd1420da5456bffc2480ce436ac8ae57f20a25c304e4cf6f73
12  Alternate cryptocurrencies / Altcoin Discussion / Re: MC2: A democratic cryptocurrency based on a hybrid PoW/PoS system on: April 20, 2013, 01:17:19 AM
Also just to clarify, I just registered this forum account but have been using bitcoin for almost 2 years now. See my post history for proof.
13  Alternate cryptocurrencies / Altcoin Discussion / Re: MC2: A democratic cryptocurrency based on a hybrid PoW/PoS system on: April 20, 2013, 01:16:06 AM
First, I just want to say that I applaud Tacotime's acknowledgement of how a coin should be released especially with all these silly copycat alt coins that provide nothing novel being spammed almost daily now. Litecoin has shown the advantages of alternative hashing algorithms, but I also concur that a more in depth look at optimizing a coin for GPU mining above all else is key. If GPU mining is able to be protected as the best way to mine a coin then this provides the best decentralization as gamers will always be a huge distribution of hashing power whereas ASICs and FPGAs will always be skewed towards a relatively few individuals/groups with significant capital (not that GPU mining farms are impossible just that even a few thousand GPU farms will pale in comparison to the gaming community).

Now, while just optimizing the hashing algorithm provides a useful trait for a new coin, I suggest that we take this opportunity and add a few additional key traits to the new coin to provide utility to the community well beyond any current cryptocurrency. In order of importance I suggest the following additional key features:

Distributed Exchange
Distributed exchange is perhaps the killer feature that everyone is talking about often with unrealistic expectations. Obviously we cannot solve the problem of converting fiat directly into cryptocurrency, but I believe we can provide a decentralized exchange mechanism that only relies on outside trusted parties for a final withdrawal or deposit of fiat. My suggestion has two main features. First, we incorporate the colored coins idea (https://docs.google.com/document/d/1AnkP_cVZTCMLIzw4DvsW6M8Q2JC0lIzrTLuoWu2z1BE/edit?pli=1) to allow any outside party to create and sign particular coins as having some additional meaning (in the fiat use case that would be some amount of USD for instance). Second, we create a new type of transaction that posts an offer to the network to exchange some number of new(whatever our new currency is called)coins for a certain number of colored coins properly signed by an entity or set of entities or vice versa. Once the network sees offers that match, a transaction is recorded in the block chain that atomically transfers ownership to each party. (TODO optimize incentives for miners to match offers well through transaction fees etc.)

I would also like to see a way to exchange with other cryptocurrency directly, but this has many additional hurdles such as requiring all nodes or at least miners to keep other block chains in memory and possible denial of service attacks from people accepting offers and not sending the BTC or LTC agreed upon.

Built in P2Pool type mining option
The P2Pool project epitomizes the distributed nature and serves as an important bulwark against a few popular pools from having a huge influence on block chains. I suggest we incorporate this option directly into the client. This also will give users a no hassle option to mine and receive coins out of the box without dealing with pool registration and the risk of them being hacked.

Built in GPU mining option
I suggest we bundle and integrate a graphical interface such that novice users can easily mine with their GPU with just the normal official client. Combined with the above P2Pool suggestion this should further democratize mining making it as user friendly as possible to novice users.

Zerocoin anonymization
http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf
While this may yet be too computationally and space intensive for now, I think we should at least consider the possibility of implementing this state of the art crypto work. It is going to be presented at the top academic conference in computer security this May. Read the paper for details, but the gist is that you can truly anonymize the coins such that no one can match the input and outputs of transactions. The main disadvantage it has for bitcoin is that the protocol would have to be accepted by all the users, but if we incorporate this by default in the client from the start we solve that problem. There is some concern about how heavyweight the crypto is so that will have to be considered.

0-confirmation double spend resistance
The normal defense against a double spend is to wait for a number of confirmations such that an attacker will have to have close to or more than 51% of the hashing power of the network. This is a very strong guarantee and works well for transactions of any amount, but comes at the cost of waiting for at least 1 block. For asynchronous transactions such as online purchases where product is eventually shipped after some delay this is almost no cost at all, but in the scenario where a user wants to use bitcoin like cash for an in store purchase and walk out with merchandise, this wait time greatly exceeds that of a 1 second credit card processing wait.

This is as far as I know a novel idea that I came up with to partially address wait time. A transaction with zero confirmations can easily be double spent. I propose that if multiple transactions are floating in the network waiting to be confirmed into the next block and there are conflicts among them (double spends) that as long as each transaction by itself would be valid that instead of choosing one the network writes both into the block and destroys the coins involved. While the merchant would still lose the coins so would the attacker removing the incentive to double spend. Now of course for large transactions one would still be ill advised to accept 0 confirmations, this destroys the incentive for a casual theft of small amounts. I think this could be especially useful for payment processors like bitinstant when people use it on their phones to pay for food or beer as if they left immediately after, there is a significant delay before anyone would be aware of the zero confirmation double spend.



I am also available to contribute some time to design/programming. I think this should be a significant undertaking with as many people involved as possible to really create a significant contribution to the cryptocurrency community. Anything halfhearted or just an incremental improvement will not make much difference. I'd rather not have a slew of alternative currencies that slowly build on each other, but rather a significant leap forward with real testing and new features.

Let me know if anything is unclear. I'll try to answer any questions although most of these ideas are preliminary so lots of work in finalizing an actual working implementation is yet to be done. I do believe that all these suggestions are quite practical if we have enough programmers volunteer to create and test them.

Nathaniel
14  Other / Beginners & Help / Re: Quad HD 7970 Bitcoin Miner - PSU Req.? on: April 20, 2013, 12:16:47 AM
Anyone have numbers on the 7970s overclocked mining litecoins? I'm hoping that an 800W PSU will be enough, but it looks like I might need 850W.
15  Other / Beginners & Help / Re: Introduce yourself :) on: April 20, 2013, 12:10:39 AM
Hi! I'm Nathaniel. Long time lurker getting another post in the newbie forum Smiley

16  Other / Beginners & Help / Re: p2pool, LTC and high transaction fees on: April 20, 2013, 12:09:20 AM
You can just reduce the transaction fee paid in Settings -> Options. Note that if you set a low transaction fee that the transaction may take longer to be put into a block.
17  Other / Beginners & Help / Re: LTC Mining profitable on: April 20, 2013, 12:04:11 AM
It's still about 4-5 times the cost of electricity at $0.11/kWh so if you already have cards then you might as well mine. Difficulty will likely double once the bitcoin asics force all the GPU miners over to litecoin.
18  Other / Beginners & Help / Re: Whitelist Requests (Want out of here?) on: April 20, 2013, 12:01:21 AM
I have used bitcoin for almost 2 years now and am now joining the forum to contribute/refine altcoin ideas particular towards building a distributed exchange mechanism. Please let me leave the newbie area without having to make 4 more silly posts Smiley

Here's my 1 year and 11month old address, which I am signing this message with.
16EeLa9BrZc1A4sasztaRdnfp3aU8DmuVC

http://blockchain.info/address/16EeLa9BrZc1A4sasztaRdnfp3aU8DmuVC

Thanks,

Nathaniel
Message signature: G0alpKJP6s+sRA7pkEhi/dkfVToQayz/UC1Uco4meT0S2M5C8rOIIAx9CMxQmeYRvreGrOHbtf8Ad0WxPA+Gr60=
19  Other / Beginners & Help / Re: Mt.Gox Verification Speculation on: April 19, 2013, 11:52:34 PM
FYI I just got verified after a week or so from position 14000ish. Although I had an older (almost 1 year) account, but I'm not sure if they prioritize those. I mainly set it back up in order to cash out a bit to buy more mining equipment.
Pages: [1]
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!