Bitcoin Forum
January 17, 2015, 02:08:56 AM *
News: ♦♦ Users of Bitcoin Core on Linux must not upgrade to the latest OpenSSL. More info.
 
  Home Help Search Donate Login Register  
  Show Posts
Pages: 1 ... 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 [65] 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 ... 272
1281  Economy / Speculation / Re: URGENT, Bitcoin is on the verge of collapse !!! on: October 04, 2014, 06:15:24 PM
I have one question about that though, if miners quit because its not profitable to mine, would that not open up the network and make it that much weaker? I mean easier to attack is what I am getting at... so would that not be counter productive?

As I understand it, it makes it easier for an independent entity to amass more hashpower than the entire network combined, at which point they would have a chance to double-spend coins (a "51% attack").  Worse, the mining equipment that has been turned off for being unprofitable could be used for that attack (or could be bought, well below cost, by someone who intends to do that attack).

If the mining equipment cannot recover the electricity cost, at current market price, even miners who believe that bitcoin will eventually "go to the moon" will prefer to turn the equipment off, and buy bitcoins on the market with the money they would spend on electricity otherwise.  Few people would keep losing money every day just to protect some worthy project.  Very few investors would tolerate such a decision from the managers of a company they invested in.
1282  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 04, 2014, 04:47:26 PM
AFAIK, it is not correct to say that "merchants immediately convert BTC to dollars".  They generally get dollars through bank transfer.  It is the payment processor (BitPay, CoinBase, ...) that sells the coins.

Merchants may have the option to receive the bitcoins; but, given the price decline, I doubt that any use that option.
1283  Bitcoin / Hardware / Re: BFL fucked us over again on: October 04, 2014, 04:12:52 PM
And, there you have it! John Mutrux, Jody Drake's cohort, continues receiving his $21/hr, while Jody cried to the FTC that she's in dire need of living expenses, further taking monies rightfully owned to BFL investomers.
If I understand correctly, the judge unblocked a couple thousand dollars each for Jody and Sonny; and those "critical employees" work and are paid on a hourly basis, if and when the receiver decides so.  Perhaps to keep the manufacture going?  Perhaps to recover databases and documents?

1284  Bitcoin / Project Development / Re: [ESHOP launched] Trezor: Bitcoin hardware wallet on: October 04, 2014, 04:01:13 PM
I would guess that the code above is a manual translation into python-like language of some part of the executable binary  extracted from the bootloader.
How do you come to this conclusion?  Its just python code that verifies signatures on a firmware image.  nothing more.
The poster offered that pseudo-code as evidence that he did reverse-engineer the bootloader.  That is all. Anyone who can get the binary out of the Trezor can check whether that part of the binary corresponds to that pseudo-code. 

That pseudo-code alone does not prove that the poster reverse-engineered the entire binary code (but if that pseudo-code is the output of a disassembler, surely he did).  It does not prove that the bootloader has no backdoor (one must check the whole binary for that).  It does not prove that the official firmware is not malicious.  I
1285  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 04, 2014, 03:29:56 PM
The thing is it's NOT old coins. None of the old chaps is selling right now.

Just because the coins moved recently, it does not mean that they were bought recently.

Some owners of old cheap coins must have moved them to an exchange at some point, but withdrew them when MtGOX started failing, and people realized that exchanges were not safe places to keep your one's hoard.

Other old owners may have moved their coins to new addresses for safety or other reasons.

If someone pays a small amount out of a large input, and sends the change-back to a different address, the age of those the change-back coins will be reset for the purposes of the change-back formula, correct?  What if the change-back is sent to the same address?

Finally, it seems that there is a lot of "fake" volume on the blockchain (coins moving between addresses belonging to the same person), perhaps from tumbling or hotwallet/coldwallet flow.  For that reason, if someone sells a thousand 2011  coins, thus destroying a million bitcoin-days, he will barely make a blip on the chart (which oscillates between 2 million and 15 million BTC-days destroyed per day).  If old owners have been selling a couple thousand old coins every day, we would not see it there.
1286  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 04, 2014, 07:54:36 AM
Anyway, clearly the adoption is slowing down or the new comers think Bitcoin is overvalued
Demand for use as currency in payments (a) seems to be much smaller than demand for hoarding (b) and speculation (c).  If there was only demand (a), the price would probably be 10$ or less.  The drop in price since the all-time high is mainly due to drop in demands (b) and/or (c).
1287  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 04, 2014, 06:56:12 AM
OKCoin just dipped to 2200 CNY, below the low of Apr/11 (2212).  Still 200 CNY above above the low of Dec/18 (2010).
Ditto for Huobi.
1288  Alternate cryptocurrencies / Altcoin Discussion / Re: The Monero Free For All Thread on: October 04, 2014, 06:35:35 AM
The universe has no edge
Yes, it is a very dull place, mostly.
1289  Bitcoin / Project Development / Re: [ESHOP launched] Trezor: Bitcoin hardware wallet on: October 04, 2014, 06:31:33 AM
for what it's worth as an independant audit, the bootloader functionally does what it's supposed to do and doesn't contain a backdoor.
(+ proof of RE)
The bootloader is written in Python? I'm a bit surprised about that.

I would guess that the code above is a manual translation into python-like language of some part of the executable binary  extracted from the bootloader.
1290  Alternate cryptocurrencies / Altcoin Discussion / Re: The Monero Free For All Thread on: October 04, 2014, 05:48:53 AM
Did you miss the entire discussion about permutations of consecutive independent trials (i.e. not separated by 65 minutes each)?

If someone is causing the block rate to be higher than one per minute, that should be detected by counting blocks in some long interval (say, 10 hours) .

Afaics, that won't help you identify an intentional segregation of fast and slow blocks to manipulate the 80/20 discard window of the CN difficulty adjustment algorithm.

If the block rate is OK but the suspicion is that the timing of blocks is being manipulated, that should be detected by plotting a histogram of block-to-block gaps, or of number of blocks in successive 2 minute intervals, again over a long enough period.

I don't see how that will identify an intentional segregation since the 80/20 discard is relative to its own statistics? Do you mean comparing histogram histories?

Computing the probability of a certain complicated pattern occurring, after seeing it occur, is a tricky business.  The chance of my mother marrying my father was one in two billions or so; that does not mean that my mere existence is a sign that something fishy is going one with the universe...

You said you read the upthread discussion, yet you continue the strawman. My point was to refute the anti-FUD-campaign which was turning into a Monica Lewinsky or Steve Jobs denial, "no malfunction in our devices"[1].

[1] "don't touch it that way"

Sorry, I know practically nothing about the Monero protocol, so I cannot say anything useful about the "attack"  specifically.  (The continuous difficulty adjustment and the 20% outlier rejection filter seem to make it hard to model statistically.  If the difficulty gets adjusted diring the data collection interval, one cannot assume that block finding is a Poisson process; unless the event times are remapped to a suitable variable-rate clock.)

I was only commenting on the suggestion (perhaps not even by you, it is hard to keep track of the debate) that the occurence of a pattern that has very low probability of occurring is evidence of manipulation.  It may be evidence, if the probability analysis is properly done, but it is very easy to slip and see manipulation where there isn't.

The mistake is easy to make if one takes a complicated pattern that has occurred.  Others have pointed out that fallacy.  If the pattern covers a dozen consecutive events, its probability will be very low -- but some pattern must occur at every point,so nothing strange there.
1291  Alternate cryptocurrencies / Altcoin Discussion / Re: The Monero Free For All Thread on: October 04, 2014, 02:28:56 AM
You also didn't see the point of complexity theory.

Continuind my earlier post:

I emphasize that this is an academic discussion that has no practical consequence except to show that theory has nothing to say on the robustness of SHA256.

Two theoretical fields were used in your post: the theory of complexity classes (P, NP and all that) and big-O analysis.  Neither can be applied to SHA256.

First, both theories only apply to problems where the size n of the input is variable and unbounded; and they consider what happens in the limit when n tends to infinity.  If n is bounded, no matter how big, all the definitions collapse and every problem is not only polynomial, but can be solved in O(1) time.  

In fact, if you cannot let n go to infinity, strictly speaking you cannot even apply the definitions; you get barred at the door.  

But suppose you generalize the problem in such a way that the input size n can go to infinity, and you can analyze its complexity as "polynomial" or "exponential" or "O(n2)".   Still, these results will not say anything about the cost for any specific n, such as n = 256 bits.  

You cannot tell whether an algorithm runs in O(1) time or requires exponential time by looking at what it does forany finite set of inputs; and vice-versa.  

One can easily define two algorthms A0 and B0 such that A0 runs in O(1) time, B0 runs in exponential time, but A0 and B0 give the same output for every input with size n below 10500.  One can easily define two functions F0 and G0, where F0 can be computed in O(1) time while G0 requires exponential time, but such that F0(x) = G0(x) for every input x whose size n is less than 10500.  These are trivial exercises, that do not require any arguments or ideas more complicated than the definitions.

In a previous post you told how replacing an O(n^k) algorithm by an O(log n) one made a huge difference in running time.  I have a few such success stories myself. (Back in 1979, when working as a part-time programer for an egineering firm, I saved a large govt-funded project by substituting an O(1) table lookup for an O(n) search in a COBOL program, with n about 1000, after even the COBOL experts from IBM Brazil had failed to make the program run fast enough.  I never again got so much praise in my life.  Cheesy)

However, justifying those successes in terms of asymptotic (big-O) analysis or P-vs-NP is wrong, because that kind of analysis does not actually let you conclude anything about the actual running time on a specific application.  It is like the explanation of the successful businessman in the old joke at the end of this post.

Your wrote:
The definition of polynomial time is precisely the time complexity class O(nk).

The relevance is that for NP complexity class, very small increases in n causes exponential (not polynomial) increases in computation cost.

If the best known inversions of SHA256 are NP, then NP is relevant because it means there is some smallish value of n for which no inversion is practical. Afaics, this is what complexity theory gains us.

The first sentence is correct, the other two are dead wrong.

First, a formal nit:  the class NP contains P, and no one knows whether NP is equal to P or not. Therefore, proving that something is in NP does not prove that it is not P, and even proving that it is "NP-complete" (which is what people usually mean when they lazily say just "NP") does not prove that it is not P.  

Also another nit: there are many classes of asymptotic complexities between "polynomial" and "exponential", so "not polynomial" includes for example algorithms that run in O(n log log log log n) time, which for some problems would be very interesting indeed.  

The terms "exponential" and "polynomial" can be applied to the increase in running time only when they can be applied to the running time itself; that is, if there is a problem size variable n that can grow without bounds.  And, even then, they describe how the cost increases when n tends to infinity.  I repeat: those terms are meaningless if the size n is bounded (and doubly so if n is fixed).

Strictly by the definitions, the "Bitcoin Mining Problem" (BMP), the partial inversion of SHA256, is O(1), because it does not matter what the algorithm outputs when n is not 256.  Hence, strictly by the definitions, BMP is in P, and therefore is in NP; but is not NP-complete.  And, indeed, it could be solved by a giant table.  Of course, that table is too big to be built in practice; but that obstacle is not relevant for the theory.

I am not aware of any theory that would give a useful estimate of the practical difficulty of solving some problem with fixed-size inputs, like the BMP.  At best, one can prove theoretically that a certain specific shortcut will not work; but there is no way to prove that there are no practical shortcuts.  The only "proof" that BMP is hard is that many people have tried to find such a practical shortcut, for many years, with no success.

It is a terrible misconception to think that "exponential cost" is bigger (or grows faster) than "polynomial cost".  That is true only for "sufficiently large n", but the theory does not say when n is "sufficiently large"; it could be true only for n greater than 10500.  See the example algorithms A0 and B0 above, and the functions F0 and G0 above.  There is nothing in the theory that justifies saying that the breakpoint is "smallish".

You may object that examples like F0 and G0 are contrived and unreal.  But my statement remains correct even if the costs grow smoothly with n, according to some simple formulas.  Suppose that algorithm A1 finishes after 10200×n operations, algorithm B1 finishes after 10×n50 operations, and algorithm C1 finishes after 10×1.00000000000001n operations, all three formulas being exact (up to rounding) and valid for all inputs.  By the definitions, A1 runs in polynomial, O(n) time; B1 is polynomial too, with O(n50) time; nd C1 is exponential.  According to the "polynomial good, exponential bad" mantra, algorithm A1 should be better than B1, which should be better than C1.  However, plug n = 1000 in those formulas, and you get exactly the opposite order -- and only C1 will be fast enough to use.  

There are some very important real problems where the algorithms with best asymptotic complexity lose in practice to algorithms that in theory are much worse.   I recall that, perhaps 10 years ago, two students from India found a polynomial-time algorithm to decide whether a number is composite.  At the time, their algorithm ran in O(n14) time, where n is the number of bits in the input.  It was a great result for the theory; but, for the sizes n that are relevant to cryptography, their algorithm was much slower than the super-polynmial algorithms that crypto people were using.  (It may have been improved since then, I haven't checked.)

The Closest Point Problem (CPP) is like this: given a fixed set S of n sites (points) in a square, and then a series of query points, find for each query q the site p in S that is nearest to q.  One solution is to scan the set S each time; the query cost then is proportional to n. A more efficient solution begins by preprocessing S into a quad-tree Q: the square is divided into 4 smaller squares, and some of these are divided in turn, recursively; until each square has at most 1 site.   Then one can find the nearest site to a given query q by sweeping down through this tree of nested squares.  Theory says that, once the quad-tree Qis built, each query can be processed in O(log n) expected time (with some reasonable assumptions on the distribution of S).

The quad-tree method works well for points in a square, and the same idea can be used if the sites are scattered inside a cube, or a hipercube of any dimension d.  Theory says that the expected query cost remains O(log n), for any d. I have seen several computer scientists and students who, trusting that "O(log n) is much better than O(n)", tried to use this  method for things like pattern matching, where each site is an observed pattern, represented by a point in some high-dimensional space.  Only to find that, for that application, the quad-tree method is often much slower than plain sequential search.

It turns out that the quad-tree begins to work only if the number of sites n is at least 2d.  It works quite well for n = 1000 and d = 2 or 3; but, for  d = 30, it is a total waste of time unless n is a lot greater than a billion.  Not "smallish" at all...

The big-O notation was invented by pure mathematicians, to describe the limiting behavior of functions from reals to reals, such as the solutions of differential equations.  It was adapted to algorithm analysis by Don Knuth, IIRC.  However, for Knuth it was only a working tool, that would give an idea of the type of formula that had to be determined.  For example, if the number t(n) of inner block executions was found to be O(n2), one could write t(n) ≤ A n2 + B n + C, and then look for suitable values of A, B, and C.  If t(n) was found to be exponential, one would look for a formula like t(n) ≤ A × Bn. An so on.

However, finding those constants requires lots of boring algebra, so Knuth's lazy followers tacitly agreed that finding the big-O of the running time was good enough.  And then came the really lazy ones, who decided that "polynomial time" was all one needed to know.
1292  Bitcoin / Bitcoin Discussion / Re: US Marshall's Bitcoin Auction Results on: October 03, 2014, 06:45:43 PM
We know [ Tim Draper ] didn't pay far under market because of what one of the losing bidders divulged.

I am aware of someone revealing a bid in the 400--500$ range.  (The market price at the time was over 600$.)  Were there other cases of people declaring their bids?

Somehow Tim Draper's face reminds me of Eike Batista, formerly the richest man in Brazil, whose net worth fell from plus 34 billion US$ to minus 1 billion in less than two years:

http://oglobo.globo.com/economia/eike-tem-patrimonio-liquido-de-us-1-bilhao-negativo-13968641

http://www.tylatin.org/extras/cb2.html
https://www.youtube.com/watch?v=0Nn3PcESF7w
1293  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 03, 2014, 06:19:08 PM
Man...these dumps! Where do these coins keep coming from!
2011-2012?
Possible, if they were bought below 20$ the sellers are still making a nice profit.
But they had so much time to sell at 1,000$, then at 800$, 600$, 500$...
Doesn't look so
https://blockchain.info/charts/bitcoin-days-destroyed
Change that plot to log scale.  You will see that the number of bitcoin-days destroyed per day varies roughly between 2 million and 15 million.  (On my screen, that range of 13 million BTC spans about 5 millimeters on the vertical scale.)

Indeed, since the total transaction output volume is around 500'000 BTC per day, it follows that bitcoins that are being moved today were last moved 4 to 30 days ago, *on the average*.

However, if someone moves to an exchange a pack of 1'000 BTC that he acquired 1000 days ago (in early 2012),  that would be only 1 million bitcoin-days destroyed.  It would be practically invisible on that plot.  And everybody knows that a 20'000 BTC hoard must be sold gradually --- and that one should never deposit into an exchange more than what is needed for immediate trading...

The point is that  the "bitcoin-days destroyed" plot will not tell us whether old-timers are dumping or not.
1294  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 03, 2014, 04:48:18 PM
The next 24 hours will be critical for what the BTC price will be tomorrow.
1295  Economy / Speculation / Re: Wall Observer BTC/USD - Bitcoin price movement tracking & discussion on: October 03, 2014, 04:41:36 PM
sw movie.  Grin
I saw that Star Wars movie too.  IIRC, Satoshi Nakamoto lived in that hole.
1296  Bitcoin / Hardware / Re: BFL fucked us over again on: October 03, 2014, 04:16:52 PM
Sorry, I misunderstood a post there.  I thought that the issue was clients publishing the identity of BFL staff; I see now that it was the opposite.  That is bad if done by mistake; and [ no-word-for-it ] if done intentionally, for the purpose of "punishing" a customer who "complains too much".
1297  Bitcoin / Hardware / Re: BFL fucked us over again on: October 03, 2014, 02:44:22 PM
No more Doxxing Josh, SLok or BCP ok?

Quote
PROHIBITION ON RELEASE OF CONSUMER INFORMATION

IT IS FURTHER ORDERED that, except as required by a law enforcement agency,
law, regulation or court order, Defendants, and their officers, agents, servants, employees, and
attorneys, and all other persons in active concert or participation with any of them who receive
actual notice of this Order by personal service or otherwise, are temporarily restrained and
enjoined from disclosing, using, or benefiting from consumer information, including the name,
address, telephone number, email address, social security number, other identifying information,
or any data that enables access to a consumer’s account (including a credit card, bank account, or
other financial account), of any person which any Defendant obtained prior to entry of this Order
in connection with the sale of any merchandise or contract.

I want you all to call Xian01 by his real name here again I fucking double dare you.

And that goes for ANYONE who registered on the BFL forums they would be in heap of trouble should they do that again. Good luck playing that game again. Ouch.

That order applies to consumer data being disclosed by the people who have access to such data by work or by being active agents in the investigation: BFL staff, law officers, attorneys, service suppliers etc.

The situation is not symmetric.  Clients of a business that sells to the public have the right to know the identity of managers; especially if they have to pay first.  And the order does not apply to names revealed in other contexts for other reasons by other people.
1298  Alternate cryptocurrencies / Altcoin Discussion / Re: The Monero Free For All Thread on: October 03, 2014, 07:45:16 AM
You also didn't see the point of complexity theory.

For some 20 years of my life I thought of myself as a theoretical computer scientist.  I plead guilty of having told many students the things you are trying to tell me now: that complexity theory is extremely relevant to computer programming, that O(n log n) is better than O(n^2), that NP is probably more difficult than P, that polynomial is more efficient than exponential, etc. 

But all of that is false; and, moreover, it is trivially false, it follows directly from the definitions.

I stand by what I wrote: neither complexity analysis (P, NP, and all that) nor big-O analysis have anything to say about the hardness of SHA-256.  Those concepts apply only to problems where the input size n is unbounded, they only tell you what happens as n goes to infnity -- and that has no relation to what happens for any specific finite n.

I could go on, but I need some sleep.  Will continue tomorrow.  But, anyway, I stress that this issue has no impact whatsoever on your work, on the security of SHA256, or any actual application.  It just takes away one argument that some people may have thought they had.  Fortunately the robustness of SHA256 was not proved with theory, but with many years of experimental tests. 
1299  Other / Off-topic / Re: Answer the question above with a question. on: October 03, 2014, 05:31:48 AM
So what about now?
I don't know; does anyone care about mistletoe?
Don't you think that's a strange question?
Don't you think one of the fun in this thread is to ask strange questions?
Would lead carbide be a more fun topic than mistletoe berries?
But yet, wouldn't we all be better off if we just talked about our favorite colors?
Is there a color that is not splendid in some context?
1300  Bitcoin / Hardware / Re: BFL fucked us over again on: October 03, 2014, 05:08:46 AM
As for other uses of mining chips: I believe they can be handy for certain kinds of cryptanalysis.  Say that you know the precise contents of a document (e.g. a webpage, an automatic email, a PDF form, etc.)  except for one variable field (PIN, password, CC number, bank account, crypto key, ...) and you know the SHA256 hash of the document.  Then you can discover that unknown field by brute-force enumeration of all possible values and computing the respective hashes.

With a 1 GH/s chip you could recover a 9-digit PIN or a 5-character password from that data in about one second, a 6-character password in few days, etc. . With a 100 TH/s installation you could crack an 8-character password in a few seconds, etc.
This betrays rather complete lack of understanding of Bitcoin mining. Explanation for the beginners:

https://bitcointalk.org/index.php?topic=214313.msg2320409#msg2320409

What is it that I did not understand? Did you read the premise of my post above?
Pages: 1 ... 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 [65] 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 ... 272
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!