Confirming Birgitta Jónsdóttir
Attending ! |
|
|
|
|
BUMP !
Die deadline rückt näher...
|
|
|
|
Dieser Hardwarewallet ist ja prächtig! Wird es ihn auch in Serienproduktion geben?
Wie läuft denn das Feedback auf der CEBIT?
Das Feedback war eher verhalten. Serienproduktion - na, da brauchen wir erst einmal einen Investor :-) |
|
|
|
|
Aktuell ist das ein GUI Demonstrator. Die Portierung der Krypto läuft noch, ebenso wie die Anbindung an den BTC Client. Stay tuned. :-)
|
|
|
|
|
Die Eckwerte stehen jetzt fest:
Am 20. September finden vormittags das Tutorial und nachmittags der Workshop statt.
Für Beiträge am Workshop gibt es eine Deadline vom 15. 4.
Die Beiträge werden reviewed und erscheinen als Teil der Konferenz Proceedings der GI Jahrestagung.
Benachrichtigung der Autoren über die Annahme erfolgt am 30. 5. und die endgültige Version muss des Beitrags muss am 15. 6. vorliegen.
Es werden Beiträge gesucht.
Fortsetzung folgt.
|
|
|
|
|
Ok, so the core details are fixed by now.
We will have the tutorial on September 20 in the morning.
The workshop will be in the afternoon.
Deadline for submission is April 15 for contributed papers.
Notice to authors will be given on Mai 30.
Final version is due on June 15.
The papers will be reviewed by two referees and accepted papers will be published as part of the conference proceedings.
we are looking forward to many contributed papers of all kinds.
Will keep you posted.
|
|
|
|
|
Dear Bitcoiners,
on September 20 the German city of Braunschweig will host the annual meeting of the German Computer Society (GI). At this event we will present a half day tutorial on Bitcoin and a half day workshop with published academic contributions.
Both events will be mainly english spoken, but german contributions will be accepted as well.
More information will be found here or on a web page currently under development.
Contributors will be:
Clemens Cap, author of a German academic article on Bitcoin in HMD Wirtschaftsinformatik
Kay Hamacher and Stefan Katzenbeisser, who spoke at the 28th CCC event in Berlin on Bitcoin.
Jörn Loviscach, who wrote an article on Bitcoin in c't.
Best regards
Forp.
|
|
|
|
|
Liebe Bitcoin Gemeinde,
am 20. September findet in Braunschweig an der Jahrestagung der deutschen Gesellschaft für Informatik ein halbtägiges Tutorial und ein halbtägiger Workshop zum Thema Bitcoin statt.
Mit von der Partie als Vortragende sind:
Clemens Cap (Autor des Bitcoin Artikels in der HMD Wirtschaftsinformatik Nr. 283)
Kay Hamacher und Stefan Katzenbeisser (Vortragende zu Bitcoin am CCC Jahreskongress in Berlin)
Jörn Loviscach (Autor des c't Artikels zu Bitcoin)
Für den Workshop suchen wir noch Beiträge.
Mehr Informationen dazu folgen hier bzw. stehen demnächst im Netz.
Gruß
Forp
|
|
|
|
This should be easy for kids these days: (Regular money - bitcoin)
It should be easy. It is not. More important: It should be safe. It is not. Even more important: The employer should know how to send me Bitcoin. He does not. Absolutely essential: It should not be gone in case my hardware fails, my room mate catches a virus on a porn site, my cat chews the USB disc. A "real" bank usually does not lose money due to a IT issue. |
|
|
|
The question is very interesting. In my opinion it is a matter of adoption. People are trained to work in exchange for colored pieces of paper. They are accustomed to it (although they protest this custom). Now comes a guy telling you to 1) go to a website (fine) 2) download a program (fine) 3) install the program (ah, hm, well, ok) 4) keep your antivirus up to date (what is antivirus ??) 5) secure your wallet.dat (my WHAT ??) 6) backup your wallet after creation of new private keys (whose private parts  ?) 7) tell your employer to pay to account number (what is that funny string meant to be ??)  not to turn your pc off but to let the bitcoin program shut down properly first ( ) 9) think about wallet security (what ??) 10) update the bitcoin client once in a while (aha ?!?) and finally, when the money is stolen or lost, that it is your fault since you did not properly backup your junk or kept your system secure. Ok. I'd also rather have my colored pieces of paper. We must solve the usability issues of Bitcoin for the end-user, who is not a computer person. |
|
|
|
|
Currently, Bitcoin is sealing transaction histories. If a new installation wants to know if there are coins stored at address X which can be used, it has to download the entire block chain upto the current block and check the history of Bitcoin address X. So, there is a first transaction where this address is used. Then, depending on the user, there are some transactions, and finally we are up to date, knowing the current block. Only then can we decide about the value available at X.
This approach is completely safe, but it has a significant disadvantage. Throughout the game the storage efficiency is getting worse and worse.
There is a different approach, which is sealing state. In this approach every block seals the state of all addresses. If this approach is used, knowledge of the latest block (and proof of its "correctness") would be sufficient to know the amount of money encoded at address X.
Of course, this approach is not really feasible for a number of reasons.
First, a single block would have to contain the information of ALL 500.000 and more addresses, which makes the block quite large and would delay handling and hashing the block.
Second, the proof of "correctness" cannot be properly given, since Bitcoin uses the concept that after a certain block-length after a transaction chances are small that a different, competing transaction might "make it into the longest chain". This concept does not sits well with the concept of having a single latest correct block.
However, we could combine these two aspects.
Do we, in the current moment, still have to keep the information on block, say, 1000? Yes, we have to, since Satoshi mined some coins in block 259 and has not yet used them. So we need this information. But: we could look at all the blocks 1 to 1000. Some coins will have changed owners several times and we do not really need to know the entire history of these coins in their past history. We could replace blocks 1 to 1000 by a new data structure, we might call them a state snapshot, and encode a list of all coins at their current addresses (not keeping their past). As a result, the block chain would become shorter.
Now, we could improve this. Assume the current blocknumber is B. It would suffice, if we kept the last, say, 10.000 blocks (to get the difficulty adaption working smoothly), but all the information from block 1 to block B - 10.000 could be "collected" into a snapsho-like state record.
We would thus combine advantages from two concepts: We have compact storage of that information which we must store and we would keep only so much of the development to ensure that we have the right concept of "longest" chain and to keep difficulty adaption running smoothly.
Any comments on this?
|
|
|
|
|
I took a few days to research this to a bit more detail and I think I have an answer to my original question and to some of the aspects which have been raised in the discussion. I will explain this in some detail using LaTeX syntax. At the end, I will draw a conclusion.
I use the following conventions: There is a set $N$ consisting of control words (aka nonces), which control the non-deterministic part. There is a set $P$ of PoW specifications. There is a result set $R$.
A proof of work is given by two functions $f: N \times P \to R$ and $v: P \times R \to {0,1}$. The PoW to solve is given by an element $p \in P$. The task of the miner is to find a control word or nonce $n \in N$ such that the result $f(n,p)$ satisfies the correctness condition. The latter is determined by evaluating the solution verification function $v$. If $v(p,f(n,p)) = 1$ then the nonce $n$ is a good solution to the problem $p$.
The time to calculate a $f(n,p)$ is given by a function $\tau: N \times P \to {\Bbb R}^+$.
This description models in a sufficiently general fashion a proof-of-work which I use since it helps me to understand the conceptual issues.
To be a more realistic model, think of the set $N$ not only of the set of 32-bit nonces in the sense of the reference implementation but of the set of all possible changes a client can make for winning a block.
In Bitcoin, $N$ is extremely large and the time to calculate $f(n,p)$ is very small (we have to evaluate a SHA). Thus, the proper strategy is to chose an $n \in N$ randomly and to calculate $f(n,p)$. (Note: The miners do not chose the nonce randomly, but in our model $N$ is meant to model the entire variability to solve the PoW, so $N$ is indeed extremly large and if we assume $n$ is selected randomly instead of sequentially, we make a negligible error). Thus, we are doing a large number of experiments with a small chance of success and thus a Poisson distribution is a good guess.
As a result of this observation, we can parallelize a search for a good $n\in N$ over this larger set $N$.
Now let us look at different PoWs, as we discussed them in this thread.
ONE possibility we will consider only for theoretical purposes is that $N$ contains only one element and $f(n,p)$ takes very long to calculate. This corresponds to the completely sequential PoW. There is no chance for parallelization at all. The miner with the fastest CPU wins the block all the time.
ANOTHER possibility would be to consider a set $N$ with a small number of elements, say some 100 or so, where the time to calculate $f(n,p)$ is much longer. In this case, there would be no good parallelization (the maximal degree of parallelization would be 100). So since there are more CPUs then elements in $N$, we will again have the situation that the guy with the fastest 100 machines wins every block. Not what we want.
The second and only other design decision we could change is the time complexity. So, for some $n \in N$ the time to calculate $f(n,p)$ would be smaller and for others it would be larger.
Let us look at the two possible cases here: A small set $N$ and a large set $N$.
For the case of a small set $N$, I can construct the situation I intuitively had in mind when starting this thread. However, as we will see, there is no real benefit. As an example I consider a case where $N$ and $f$ is such, that there are 5 easy and 100 very complicated PoWs. Very complicated would correspond to non-parallelizable. Now assume, there are 2 attackers and 200 honest nodes. Under this assumption, the 200 honest nodes find a solution quickly, where (on the average) the attackers will have a disadvantage. Chances are high that the attackers will end up with the complicated tasks. So even when there are more attackers, they could not really gain something in parallelization, since the attackers are likely to chose from the 100 very complicated tasks. However, when varying the numbers of the example one immediately sees that this effect breaks done, if the number of easy and complicated tasks is different or if some honest nodes turn into attackers. Of course, this is not robust enough to be a suggestion for Bitcoin. However, I can produce the effect of which I intuitively felt it would be possible.
For the case of a large set $N$, every miner would probe some thousand or more elements of $n$. Here, the differences in easy and very complicated work situations are equivalent to a situation where all tasks have the same average time complexity. So, the effect becomes smaller and is no longer noticeable.
I thus come to the conclusion: Yes, we can (quite artificially) produce situations, where a non-parallelizable proof-of-work is of advantage for Bitcoin. However the assumptions needed for obtaining such an advantage are unrealistic and allow other forms of attacks.
The answer thus is: Yes, there is a very good reason that the PoWs in Bitcoin are constructed the way they are constructed - it just took me a few hours to reach that level of understanding.
Thanx for all the contributions to this thread.
|
|
|
|
I'm curious: What's your shutdown point?
I have none. To me, Bitcoin is not a machine which converts electricity into dollars. To me, Bitcoin is * An interesting research topic * A charming community full of good spirits and ideas * and, above all, a great chance for a structural change in the monetary system somewhere down the road. Why should I let my personal greed allow to do damage to these interesting goals? Moreover, I started mining at a time where it was not yet profitable. Why should I stop it now when it loses profitability? Ok. I admit it: My utility bill was higher than I expected.  But I also learned a lot from the community and this is the price to pay. And: I do not have to mine 24 x 7 on all my GPU cards (12 x 7 is fine as well), and in winter I have a clear preference how to produce heat.  |
|
|
|
Even though each miner (or pool) starts at nonce 0 they are using different headers thus won't have the same nonce produce a winning block. I miner which started at last nonce and worked downward wouldn't have any advantage.
Yeah. That's why I added "do not take that dead serious" or so at the end of my post. And, still, it remains an interesting exercise... Assuming all blocks were identical (which they are not) and assuming the system were strictly synchroneous: The guy with the fastest CPU would always make the block, if all would mine from 0 upwards. In this (admittedly fictious and for Bitcoin completely unrealistic) scenario, the joke would really make sense. We cannot think of such aspects often enough, because it is the very detail which, when overlooked, could produce interesting  effects. For example, I was highly sceptical of the anonymity of bitcoin until I checked in the reference code, that the address where you get your change back, really is placed into position 1 or 2 at random... |
|
|
|
Seems to me that the most natural way to write a mining program is to start at nonce 0 and go up.
Your statement exactly is the reason I would not do this as you suggested.  Maybe you know this multi-joke: A guy plays lotto, the one where you have to guess 6 numbers out of 1 - 45. And every week he picks the numbers 1, 2, 3, 4, 5, 6. After a month the lotto vending guy tells him: "Why don't you pick different numbers. 1, 2, 3, 4, 5, 6 - this is such an odd combination. It is really very improbable that exactly this combination is selected. I have been selling lotto tickets now for years and years - and such a combination, I can tell you, will never be coming". If you are a mathematician, this is the first moment of laughter.  So, the player replies: "Well, I am a mathematician, and I can prove that 1, 2, 3, 4, 5, 6 is as probable as is 3, 19, 23, 34, 38, 41. So, the guy continues playing, and, after several years, indeed the numbers 1, 2, 3, 4, 5, 6 are selected. The guy goes to the shop to pick up his money but is very disappointed when he learns that he has to share the prize with 500 other mathematicians who also played 1, 2, 3, 4, 5, 6. In the multi-joke, this is the second moment of laughter. So, that's why I would do it differently Ok. Ok. My remark is not supposed to be taken dead seriously. |
|
|
|
The probability of any nonce being used twice is thus exactly 1 in 2^32 and doesn't change regardlesss of difficulty.
Is this really so easy? The nonce is a criterion for meeting the target. For a low difficulty we have a different target than for a high difficulty. If difficulty is sufficiently high, chances are high that there is NO nonce at all in the range of 1 to 2^32 which meets the target (for this case there are numerous mechanisms in the Bitcoin implementation which deal with nonce overrun and others which ensure that eventually a (different) block will be found). If difficulty is very low, chances are that in said range there are several nonces which meet the target. On the other hand, difficulty currently is so high that we see nonce overrun extremely often, so we might as well understand mining as process which (after overruns and all kinds of stuff which we are not interested in currently) comes up with an arbitrary nonce value in 0 to 2^32-1. So we might as well model it like that. Looks like right now, with high difficulty, your assumption is a good model. And, I think, my statistical guts feeling fell victim of the birthday paradox. If we assume, as in above paragraph, that finding a nonce is an equally distributed selection process in 32 bit space, then having identical nonces in 140.000 blocks is the same as having a hash collision with a 32 bit hash function and 140.000 attempts. According to http://en.wikipedia.org/wiki/Birthday_attack with 110.000 attempts chances are 75% to have at least one collision in this situation. So, actually, it is quite reasonable at block 140.000 to have a small, one digit number of such blocks. Doubt dissmissed. Happy again. |
|
|
|
No need to guess. They are nonces that have generated more than a single solved block.
If I am not completely mistaken, the probability of having such nonces given the current length of the blockchain and the breadth of SHA-256 is...for all realistic purposes zero. Well, not really. I forgot the target. And the difficulty adjustment over time. And that there was a very low difficulty at the beginning. It would be interesting to know the probability of such a thing to happen. I assume this happened in very early blocks? Anyone having the block numbers at hand? (My own block explorer version does not yet support searching on nonces) |
|
|
|
|
Show Posts
