5 ms·

I think some of this is kind of wrong. Mostly the claim that "The Difficulty is Intergalactic" is just flat wrong. Consider a miner on mars with 10% of the has

by rocqua 9y ago

I think some of this is kind of wrong. Mostly the claim that "The Difficulty is Intergalactic" is just flat wrong. Consider a miner on mars with 10% of the hash-rate on earth. Lets say the light delay from earth to mars is 10 minutes (it is 14 on average). Now, suppose mars has last seen block B_0 and it was mined on earth (as would happen most often due to 90% of the hash rate being there). We will call E_1 the next block found if only earth were to mine, and M_1 the block for mars. Now, mars has two really big dis-advantages. First of all, earth gets to see B_0 ten minutes before mars does. So, earth can start mining a lot earlier. Second of all, when mars does find a block, but earth finds a block 10 minutes later, earth is going to orphan the martian block. So, if mars has fewer than 20 minutes of advantage over earth, there is a very good chance any block they find won't matter. Now, I suppose if the hash-rate is more spread-out over multiple planets, and one planet isn't dominating things might work out. But we might also see consensus break down. I might sit down and do the rigorous math on that tommorow, just to see what happens. (Other minor nitpicks) > SHA is Memoryless and Progress-Free Technically false, because memory-less processes have positive probabilty of yielding no block after 2^256 tries, whereas for sha-256 using brute force, this probability is totally 0. I don't think this matters at the current hash-rate though. (our current hashrate covers about (2.5 * 10^-53)% of the entire output space every 10 minutes.) > Trying a SHA Makes You a Participant Only if you would actually submit your hash if you found a match. The same holds for the prime-factorization example. If I happen to factor a huge number and tell no-one I haven't contributed.

icebraining 9y ago
Now, I suppose if the hash-rate is more spread-out over multiple planets, and one planet isn't dominating things might work out. But we might also see consensus break down. I'm no expert, but wouldn't it just be a matter of increasing the target time to solve each block? An solar-system-wide blockchain might need to take a few hours rather than ten minutes between each block, but it should still work.
- rocqua 9y ago
  Yeah, but it is quite interesting what the relevant target times are. Does a 10 minute delay require something like a 10 or 20 minute target time to keep consensus or is it more like 2 hours or even a day? How does is this effected by the ratio of hash-rates over the planets? What happens when you have clusters (say earth - moon and mars - phobos)? In any case, if the target times need to increase by too much, things become infeasible. And I'd guess that at any given target time, there is distance from earth where computations no longer contribute to the hash-rate on earth. Thus, the claim that 'the hash-rate is universal' would be false.
  - icebraining 9y ago
    Intuitively, for two planets, I'd say you need the delay to be inside (some percentile of) the variation between the time taken by each block, so that a planet has the chance to "leap ahead" of the other. So if a block takes X minutes with a 20% variation at, say, 95th percentile, and the inter-planet latency is 10 minutes, then I think the target time (X) must be more than 100 minutes, so that if Earth mined the last block, Mars can receive it 10 minutes late and still have a chance of mining it first and reporting it back before Earth finds it. But I'm probably totally wrong :)
    - incompatible 9y ago
      Earth would presumably still have the majority of the miners, so once they'd found a block they'd have a consensus. They'd ignore a block received from Mars that didn't build on that block. Mars wouldn't be able to do the same to Earth.
      - icebraining 9y ago
        Right, the majority of time, that's what would happen. But sometimes, Earth would mine a block, send it to Mars and immediately start working on the next one, and yet Mars would win it simply because they got lucky enough to find the solution first, despite having a 20m handicap. And then Earth would have to get lucky (which would be easier, since they have more miners, but that's OK). My idea is just that if you increase the target time quite a bit, Mars would get lucky more often. In fact, this already happens: if an European miner wins a block, then why don't other European miners always win the subsequent blocks, since their latency to the winner is lower than American or Chinese miners? It's because the few miliseconds extra are not relevant when a block takes 10m on average to find. My idea is just to increase the target time so that the 20mins latency are also not relevant.
gtrubetskoy 9y ago
>> Mostly the claim that "The Difficulty is Intergalactic" is just flat wrong. (I wrote the article) - I see your point, but I think the article is still correct. Now communicating the winning block is a problem, as you pointed out, so as a miner on Mars you're at a disadvantage, but that statistically the probability of solving the puzzle remains same regardless of your location in the universe is still true. As someone else pointed out - for the intergalactic version we'd need an interval much longer than 10 minutes. This is why 10 minutes was chosen by Satoshi probably - it's plenty of time for everyone to communicate the solved block, yet not too terribly long in "human time".
- rocqua 9y ago
  Hi, I hope my tone wasn't too grating. I stand by my point though, for the purpose of totally ordering blocks, the difficulty is not intergalactic because a solution on mars is much less useful than a solution on earth. The problem here is time-delay preventing simultaneity. This is the same problem that block chain time-stamping hopes to solve. Thus it seems unfair to me to ignore this problem. I wonder how tight the 10 minute mark is at the moment. I imagine there might be nodes that are 5 seconds apart on the network. Maybe even more when we have backhoe outages. How much lower could the 10 minutes be before we start seeing to many orphans even on earth?
  - aey 9y ago
    I am working on a project that’s cryptographically encoding passage of time as data, with a millisecond resolution. https://github.com/solana-labs/solana https://github.com/solana-labs/solana As long as the fabrication process is the same you can have high confidence at time and order of events that are far apart.
  - gtrubetskoy 9y ago
    > the difficulty is not intergalactic because a solution on mars is much less useful than a solution on earth We're talking apples and oranges, I don't think there is a disagreement - I was only saying that the statistical problem is "intergalactic", not that how it's used in Bitcoin is useful across galaxies. The fact that the probability of the outcome is same across the whole universe is what I found particularly remarkable.
deleted 9y ago
[deleted]
snissn 9y ago
I think you'd want a Mars chain and an earth chain and have cross chain swaps for payments between planets
hinkley 9y ago
When Mars successfully mines a block in time the latency cancels out doesn’t it? Because now they know the next block ten minutes before everyone else.
- Dylan16807 9y ago
  It's the total delay that matters. 10 minutes each way is functionally equivalent to 20 minutes earth-to-mars delay plus 0 minutes mars-to-earth delay. Or vice versa. There's no way to cancel out a single leg, because from the point of view of the computers it's impossible to know how long each leg is.
gtrubetskoy 9y ago
>> SHA is Memoryless and Progress-Free > Technically false, because memory-less processes have positive probabilty of yielding no block after 2^256 tries, whereas for sha-256 using brute force, this probability is totally 0. I don't think this matters at the current hash-rate though. You may be right about my use of "memoryless", though it won't matter at any hashrate :) "...brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space" (B. Schneier "Applied Cryptography").
- AstralStorm 9y ago
  That depends on how much quantum computing would speed up the collision search.
- rocqua 9y ago
  I totally agree, in practice sha-256 is just memoryless. Based on the current hash rate it would be about 10^40 life-times-of-the-universe to cover all possible hashes presuming no collisions.
mrb 9y ago
«for sha-256 using brute force, this probability is totally 0» It's not zero. It's very small, but not zero. The difference between being "theoretically exactly zero" and "very small" (yet practically zero) is why we can say SHA-256 is memoryless.
- rocqua 9y ago
  But sha-256 is actually memory-full. Or rather, lets model sha-256 as a random oracle. Moreover, lets assume there is an input that leads sha-256 to be our target (so the probability of finding a solution isn't 0 at all). Take the shortest input that meets our target, and call it L. Now, brute-force try all inputs up to length L. You know have P(find solution after 2^L tries) = 1. This cannot happen for a memoryless process. If you pick your inputs randomly, it remains a memoryless process.
  - mrb 9y ago
    «lets assume there is an input that leads sha-256 » Your assumption is wrong. Theoretically, there might be no inputs that are solutions to the PoW. Of course in practice there are almost always a large number of solutions, but again the theoretical possibility of it is why it is correct to say the PoW is memoryless. Even if theoretically there was always a solution, there is no way to iterate sequentially over all inputs because after iterating over 2^32 nonces, miners have to change the 256-bit merkel root, which is effectively random. This aspect alone makes mining memoryless.

by rocqua 9y ago

icebraining 9y ago

Now, I suppose if the hash-rate is more spread-out over multiple planets, and one planet isn't dominating things might work out. But we might also see consensus break down. I'm no expert, but wouldn't it just be a matter of increasing the target time to solve each block? An solar-system-wide blockchain might need to take a few hours rather than ten minutes between each block, but it should still work.

rocqua 9y ago
Yeah, but it is quite interesting what the relevant target times are. Does a 10 minute delay require something like a 10 or 20 minute target time to keep consensus or is it more like 2 hours or even a day? How does is this effected by the ratio of hash-rates over the planets? What happens when you have clusters (say earth - moon and mars - phobos)? In any case, if the target times need to increase by too much, things become infeasible. And I'd guess that at any given target time, there is distance from earth where computations no longer contribute to the hash-rate on earth. Thus, the claim that 'the hash-rate is universal' would be false.
- icebraining 9y ago
  Intuitively, for two planets, I'd say you need the delay to be inside (some percentile of) the variation between the time taken by each block, so that a planet has the chance to "leap ahead" of the other. So if a block takes X minutes with a 20% variation at, say, 95th percentile, and the inter-planet latency is 10 minutes, then I think the target time (X) must be more than 100 minutes, so that if Earth mined the last block, Mars can receive it 10 minutes late and still have a chance of mining it first and reporting it back before Earth finds it. But I'm probably totally wrong :)
  - incompatible 9y ago
    Earth would presumably still have the majority of the miners, so once they'd found a block they'd have a consensus. They'd ignore a block received from Mars that didn't build on that block. Mars wouldn't be able to do the same to Earth.
    - icebraining 9y ago
      Right, the majority of time, that's what would happen. But sometimes, Earth would mine a block, send it to Mars and immediately start working on the next one, and yet Mars would win it simply because they got lucky enough to find the solution first, despite having a 20m handicap. And then Earth would have to get lucky (which would be easier, since they have more miners, but that's OK). My idea is just that if you increase the target time quite a bit, Mars would get lucky more often. In fact, this already happens: if an European miner wins a block, then why don't other European miners always win the subsequent blocks, since their latency to the winner is lower than American or Chinese miners? It's because the few miliseconds extra are not relevant when a block takes 10m on average to find. My idea is just to increase the target time so that the 20mins latency are also not relevant.

gtrubetskoy 9y ago

>> Mostly the claim that "The Difficulty is Intergalactic" is just flat wrong. (I wrote the article) - I see your point, but I think the article is still correct. Now communicating the winning block is a problem, as you pointed out, so as a miner on Mars you're at a disadvantage, but that statistically the probability of solving the puzzle remains same regardless of your location in the universe is still true. As someone else pointed out - for the intergalactic version we'd need an interval much longer than 10 minutes. This is why 10 minutes was chosen by Satoshi probably - it's plenty of time for everyone to communicate the solved block, yet not too terribly long in "human time".

rocqua 9y ago
Hi, I hope my tone wasn't too grating. I stand by my point though, for the purpose of totally ordering blocks, the difficulty is not intergalactic because a solution on mars is much less useful than a solution on earth. The problem here is time-delay preventing simultaneity. This is the same problem that block chain time-stamping hopes to solve. Thus it seems unfair to me to ignore this problem. I wonder how tight the 10 minute mark is at the moment. I imagine there might be nodes that are 5 seconds apart on the network. Maybe even more when we have backhoe outages. How much lower could the 10 minutes be before we start seeing to many orphans even on earth?
- aey 9y ago
  I am working on a project that’s cryptographically encoding passage of time as data, with a millisecond resolution. https://github.com/solana-labs/solana https://github.com/solana-labs/solana As long as the fabrication process is the same you can have high confidence at time and order of events that are far apart.
- gtrubetskoy 9y ago
  > the difficulty is not intergalactic because a solution on mars is much less useful than a solution on earth We're talking apples and oranges, I don't think there is a disagreement - I was only saying that the statistical problem is "intergalactic", not that how it's used in Bitcoin is useful across galaxies. The fact that the probability of the outcome is same across the whole universe is what I found particularly remarkable.

deleted 9y ago

[deleted]

snissn 9y ago

I think you'd want a Mars chain and an earth chain and have cross chain swaps for payments between planets

hinkley 9y ago

When Mars successfully mines a block in time the latency cancels out doesn’t it? Because now they know the next block ten minutes before everyone else.

Dylan16807 9y ago
It's the total delay that matters. 10 minutes each way is functionally equivalent to 20 minutes earth-to-mars delay plus 0 minutes mars-to-earth delay. Or vice versa. There's no way to cancel out a single leg, because from the point of view of the computers it's impossible to know how long each leg is.

gtrubetskoy 9y ago

>> SHA is Memoryless and Progress-Free > Technically false, because memory-less processes have positive probabilty of yielding no block after 2^256 tries, whereas for sha-256 using brute force, this probability is totally 0. I don't think this matters at the current hash-rate though. You may be right about my use of "memoryless", though it won't matter at any hashrate :) "...brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space" (B. Schneier "Applied Cryptography").

AstralStorm 9y ago
That depends on how much quantum computing would speed up the collision search.
rocqua 9y ago
I totally agree, in practice sha-256 is just memoryless. Based on the current hash rate it would be about 10^40 life-times-of-the-universe to cover all possible hashes presuming no collisions.

mrb 9y ago

«for sha-256 using brute force, this probability is totally 0» It's not zero. It's very small, but not zero. The difference between being "theoretically exactly zero" and "very small" (yet practically zero) is why we can say SHA-256 is memoryless.

rocqua 9y ago
But sha-256 is actually memory-full. Or rather, lets model sha-256 as a random oracle. Moreover, lets assume there is an input that leads sha-256 to be our target (so the probability of finding a solution isn't 0 at all). Take the shortest input that meets our target, and call it L. Now, brute-force try all inputs up to length L. You know have P(find solution after 2^L tries) = 1. This cannot happen for a memoryless process. If you pick your inputs randomly, it remains a memoryless process.
- mrb 9y ago
  «lets assume there is an input that leads sha-256 » Your assumption is wrong. Theoretically, there might be no inputs that are solutions to the PoW. Of course in practice there are almost always a large number of solutions, but again the theoretical possibility of it is why it is correct to say the PoW is memoryless. Even if theoretically there was always a solution, there is no way to iterate sequentially over all inputs because after iterating over 2^32 nonces, miners have to change the 256-bit merkel root, which is effectively random. This aspect alone makes mining memoryless.