pull down to refresh
1331 sats \ 1 reply \ @shafemtol 17 Dec \ on: [Bitcoin Puzzle] Probability of private key collisions, part 1 bitcoin
This is what's known as the birthday problem.
For two private keys, the probability of the two not colliding is
where
The probability of a private key collision is the complement of this:
Due to the large
For
This is because
Given
With a private key space of
For there to be a 0.1% chance of a collision among all the generated keys, each person would have to generate approximately
For comparison, bitcoin miners have performed a total of approximately
South Korea's Yoon says he will lift martial law after parliament vote
South Korean President Yoon Suk Yeol said on Wednesday he would move to lift a martial law declaration he had imposed just hours before, honoring a parliamentary vote against the measure.
He's got to be toast, though
Interesting developments
From https://xcancel.com/minjoo_hongtae:
Dec 3, 2024 · 4:02 PM UTC 우원식 국회의장, 비상계엄해제 선포 Speaker of the National Assembly Woo Won-shik declares lifting of martial law
Dec 3, 2024 · 4:05 PM UTC 현 시각부로 비상계엄에 동조하는 군인은 내란죄로 처벌할 수 있다고 합니다. It is said that as of now, soldiers who support martial law can be punished for sedition.
Dec 3, 2024 · 4:07 PM UTC 국회의장 "원내에 있는 군인들은 모두 국회 밖으로 나가라" Speaker of the National Assembly: "All soldiers in the National Assembly, get out of the National Assembly."
Dec 3, 2024 · 4:13 PM UTC 계엄군, 국회 내에서 철수중 Martial law troops withdraw from the National Assembly
Dec 3, 2024 · 4:23 PM UTC형법 제87조(내란) 대한민국 영토의 전부 또는 일부에서 국가권력을 배제하거나 국헌을 문란하게 할 목적으로 폭동을 일으킨 자는 다음 각 호의 구분에 따라 처벌한다.
- 우두머리는 사형, 무기징역 또는 무기금고에 처한다.
- 모의에 참여하거나 지휘하거나 그 밖의 중요한 임무에 종사한 자는 사형, 무기 또는 5년 이상의 징역이나 금고에 처한다. 살상, 파괴 또는 약탈 행위를 실행한 자도 같다.
- 부화수행(附和隨行)하거나 단순히 폭동에만 관여한 자는 5년 이하의 징역이나 금고에 처한다.
Article 87 of the Criminal Act (Internal Rebellion) A person who causes a riot in all or part of the territory of the Republic of Korea with the purpose of excluding state power or disrupting the Constitution shall be punished according to the following categories:
- The leader shall be punished by death, life imprisonment, or life imprisonment.
- A person who participates in or commands a conspiracy or engages in other important duties shall be punished by death, life imprisonment, or imprisonment for not less than five years. The same shall apply to a person who commits an act of murder, destruction, or plunder.
- A person who accompanies or simply participates in a riot shall be punished by imprisonment or imprisonment for not more than five years.
Dec 3, 2024 · 4:27 PM UTC 계엄선포 과정이 내란에 해당할 수 있다는 전문가들의 분석이 나오고 있습니다. Experts are analyzing that the process of declaring martial law could be considered a civil war.
Dec 3, 2024 · 4:31 PM UTC 윤석열 대통령의 비상계엄선포 과정에서 국회에게 통고하는 과정이 생략되며 윤석열 대통령의 탄핵요건이 갖춰지게 되었다는 분석이 나오고 있습니다. There is analysis that the process of notifying the National Assembly during President Yoon Seok-yeol's declaration of martial law was omitted, and thus the grounds for impeachment of President Yoon Seok-yeol have been met.
Dec 3, 2024 · 4:34 PM UTC 국방부 관계자가 조금 전 "계엄사령부는 계속 유지할 것"이라 밝혔습니다. A Defense Ministry official said earlier that "martial law command will remain in place."
Dec 3, 2024 · 4:36 PM UTC 국회가 계엄 해제를 요구하더라도 대통령이 계엄을 해제하지 않으면 계엄사령부를 해제할 수 없다고 합니다. Even if the National Assembly demands the lifting of martial law, it is said that the martial law command cannot be lifted unless the president lifts martial law.
Dec 3, 2024 · 4:38 PM UTC 대통령의 계엄해제가 없었기 때문에, 현재의 치안/행정은 군이 통제할 수 있는 상황이라고 합니다. Because the president did not lift martial law, the current security/administration situation is said to be under the military's control.
Dec 3, 2024 · 4:49 PM UTC 윤석열 대통령이 계엄을 해제하지 않을 경우 군경이 즉시 대통령을 체포할 수 있다고 합니다. It is said that if President Yoon Seok-yeol does not lift martial law, the military and police can immediately arrest the president.
Dec 3, 2024 · 5:00 PM UTC 일부 경찰/군인들이 국회의원의 국회 출입을 막으면서 내란죄가 성립되었다는 분석입니다. The analysis is that the crime of sedition was committed when some police officers/soldiers blocked members of the National Assembly from entering the National Assembly. https://youtube.com/watch?v=t4GUJACCqN4&t=6s
The FUD is that TPS is what matters. A transaction could be anything from a single payment to a massive coinjoin. Usable capacity should be measured in terms of transfers rather than transactions.
If we define a coin transfer as spending one coin and creating one new coin, then the coin transfer capacity is roughly:
1000000 / 600 / (input_vsize + output_vsize) coin transfers per secondAssuming all P2WPKH, that's:
1000000 / 600 / (68 + 31) = 16.8 ctpsAnd assuming all Taproot:
1000000 / 600 / (57.5 + 43) = 16.6 ctpsThat is the on-chain transfer capacity if we assume a constant UTXO set size.
In the future, full-aggregation CISA can save up to 16 vB per input, giving:
1000000 / 600 / (57.5 - 16 + 43) = 19.7 ctpsFor getting new users into Bitcoin, the real limit is the rate at which new UTXOs can be made. The size of a Taproot or P2WSH output, such as that needed for a Lightning channel, is 43 vB. Thus the limit for the number of outputs per second is:
1000000 / 600 / 43 = 38.8 outputs per secondInput/output sizes from Bitcoin Optech Transaction size calculator
AIUI, the scam works by scammers sending the victim a small amount "from" an address that has been brute-forced to look like some other address that the victim intends to send their money to.
Reading the explanation, I was surprised how that would work, as normally you shouldn't even see a "from" address on incoming payments in any Bitcoin wallet software, because there really is no "from" address in Bitcoin.
But apparently this was with some kind of "wrapped BTC" on Ethereum, where I'm guessing this scam works better.
An Electrum user having the same problem suggests to me that it could be an issue with the Electrum server.
Is your Sparrow wallet set up to connect to an Electrum server? If so, have you tried connecting to a different server?
Back in February last year I started trying to save testnet from the block storms, modifying my CPU miner to set a timestamp 2 hours into the future on the penultimate block within each difficulty period. Thus the network would be safe from accidental block storms for 2 hours and deliberate block storms for 20 minutes. The hope would be that this would be long enough for an ASIC miner to find a block and thus keep the network safe for the following difficulty period.
I also argued for a soft fork to fix the block storm issue (Lopp had claimed that fixing it required a hard fork).
I didn't run the miner the whole time, so I missed the difficulty adjustment quite a few times, but I do believe I prevented a block storm or two.
Then back in March/April when I was looking to see if it was time to start the miner again, I saw the testnet blocks and mempool were full of crap transactions, so I gave up on the project of trying to save testnet.
Thinking about the timestamp overflow issue a bit further, it could have been implemented as a soft fork by exploiting Bitcoin's time warp bug. By my calculations this could extend the lifespan of the existing chain by some 240 thousand years.
However, after the activation of BIP113 in 2016, a time warp exploit is no longer a viable option as there's no way to do make timelocked transactions with a far-future timestamp spendable at the appropriate time.
But that part could be addressed with a forced soft fork at worst. So my point still stands ("tis but a scratch!"): Bitcoin will "never" need a hard fork.
I had forgotten about the timestamp overflow issue, but that would be the kind of hard fork Bitcoin would need if it would ever need one.
That kind of hard fork doesn't necessarily have the same problem that most other hard forks would have, though. At some point it would be completely impossible to progress on the old chain. If the fork activates at that point, there's no actual chain split, old nodes will simply be stuck on an old block.
In practice such a hard fork would be more similar to a forced soft fork.
Bitcoin will never need a hard fork, but if it will need one, it will be a security related one.
In a hard fork, old nodes will stop following the same chain as forked nodes (if there are miners among the old nodes, there will be a chain split). However, virtually any change can in one way or another be implemented as a soft fork, where old nodes and new nodes still follow the same chain (at least as long as the majority of hash power implements the fork).
Post-quantum signature schemes can be soft-forked in as a new script version, just like what was done for Taproot.
A sudden and complete break of the secp256k1 curve could arguably be a good opportunity for a hard fork, if only to force everyone to upgrade their nodes lest they risk revealing the keys to still-unspent P2PKH/P2WPKH coins through their thence insecure public keys. A fork could then require proof of an OTS-style timestamp (from several hundreds or thousands of blocks prior) of a commitment to spend such coins before allowing them to be spent.
Looking at the transactions, pretty much all of them contain an
OP_RETURN output. From what I've gathered, there's supposedly some new kind of shitcoinery that's been activated since block 840000.I've always thought of "halvening" as a mostly tongue-in-cheek portmanteau of "halving" and "happening".
I modified the search function to search a random, representative subset of the search space, so that the total number of valid 12-word sets can be accurately estimated without an exhaustive search.
In 133 CPU-minutes I searched 1/10,000 of the space. My original goal of an exhaustive search would thus have taken 924 CPU-days, so I'm not going to attempt that.
The search returned got 67,672,354 unique 12-word sets that match the scrambled letters. That means the total number of unique matching 12-word sets is about 677 thousand million. Each one of these sets has 479 million possible permutations. That gives a total of 324 million million million possible word sequences. Of these, 1 in 16 will pass the 4-bit SHA-256 checksum, making a valid mnemonic. Each valid mnemonic must have its master private key derived, which involves 2048 iterations of HMAC-SHA512.
The expected number of SHA-512 operations required to find the correct private key is around 21 thousand million million million, or 2^74. That is comparable to the work currently required to mine a Bitcoin block, about 2^78 SHA-256 operations.
For comparison, given 24 unique words of a 24-word mnemonic in random order, the expected number of SHA-512 operations required to find the correct private key is 2^85, i.e. 2000 times higher.
So my conclusion remains: Finding the seed is probably doable with specialized hardware, but it is nowhere near cost-effective at a 100k sat prize even discounting the hardware cost.
Another hint:
@LaserEyesLeah I assumed no repeated words to make it easier to code. I found 565 sets of words that are scrambles of the given letters. Each of these 565 sets has 479 million possible orders. It is crackable but someone would have to be highly motivated.
@asanoha_gold Replying to @LaserEyesLeah No repeated words! Thank you for checking! What do you think the reward would have to be to make it worth it?
I take this to mean that there are 12 unique words, no duplicates. That seems to reduce the number of unordered combinations by approximately 20 to 40 percent.
Also, someone tell LaserEyesLeah they need to check the truncated forms of longer words as well, blowing the number 565 up by a factor of several million :)
One potentially real case would be one in which a Cryptosteel or equivalent has broken apart and scattered the individual letters, leaving only a few initial letters from each row still intact. That would result in a much smaller search space.
So far I've found ~1000 million matching unordered combinations, still far from complete. Search is returning about 1 million new combinations per minute.
There was a new hint published giving what is presumably the master public key:
zpub6rW2NmPTbNjFkng8Do79zp4zkstGtaCont5drCZCbPfNuQsVU6N8Qguf8PmoYKaDoJtgH8Dehvk6ukGbBzHKyEYrZUeuS1zvn8BNcGEH6tj
Currently I'd estimate an exhaustive search of all permutations of all possible word combinations to take at least 2^67 SHA-512 operations. The expected number of operations needed to find the correct seed would be half that, i.e. at least 2^66 operations.
For comparison, mining a single Bitcoin block currently takes about 2^78 SHA-256 operations. That's up to 4000 times as many operations. That's with specialized hardware, and SHA-256 might take a little less work compared to SHA-512, and the prize is higher, currently at least 6.25 BTC.
So finding the seed is probably doable, but not cost-effective at a 100k sat prize.
Had to record a video of the output during search.
Still going at 64 million unordered combinations so far, no end in sight.
After optimizing the search function to achieve a speedup of several orders of magnitude, I'm currently running it against the full wordlist.
It's even worse than I thought. So far it's found more than 20 million possible unordered combinations, and there's a lot more to go. It's crazy to watch all the results scrolling across the screen.