[bitcoin-dev] Is BIP32's chain code needed?
Hi all,
BIP32 [1] says: "In order to prevent these from depending solely on the key
itself, we extend both private and public keys first with an extra 256 bits
of
entropy. This extension, called the chain code...".
My argument is that the chain code is not needed.
To support such claim, I'll show a schematic of BIP32 operations to be
compared
with an alternative proposal and discuss the differences.
I have two main questions:
- Is this claim false?
- Has anyone shared this idea before?
## BIP32 schematic
Let `G` be the secp256k1 generator.
Let `i` be the child index.
Let `(p, P=pG)` and `(p_i, P_i=p_iG)` be the parent and i-th child keypairs
respectively.
Let `c` and `c_i` be the corresponding chain codes.
Let `h1, h2, h3, h4` be hash functions so that the formulae below match the
definitions given in BIP32 [2].
Define private and public child derivation as follow:
p_i(p, c, i) = (i < 2^31) p + h1(c, pG, i)
(i >= 2^31) p + h2(c, p, i)
c_i(p, c, i) = (i < 2^31) h3(c, pG, i)
(i >= 2^31) h4(c, p, i)
P_i(P, c, i) = (i < 2^31) P + h1(c, P, i)G
(i >= 2^31) not possible
c_i(P, c, i) = (i < 2^31) h3(c, P, i)
(i >= 2^31) not possible
The above formula for unhardened public derivation resembles a
pay-to-contract
[3] scheme.
## Alternative proposal
Let `h` be an adequately strong hash function which converts its output to
integer.
Consider the following derivation scheme:
p_i(p, i) = (i < 2^31) p + h(pG, i)
(i >= 2^31) h(p, i)
P_i(P, i) = (i < 2^31) P + h(P, i)G
(i >= 2^31) not possible
Which is basically the above one without the chaincode.
## Considerations
I claim that this has the same properties as BIP32 [4]:
- The problem of finding `p` given `p_i, i` relies on brute-forcing `h` in
the
same way the analogous problem relies on brute-forcing `h2` in BIP32.
- The problem of determining whether `{p_i, i}_i=1..n` are derived from a
common
parent `p` relies on brute-forcing `h` in the same way the analogous
problem
relies on brute-forcing `h2` in BIP32.
- Given `i < 2^31, p_i, P`, an attacker can find `p`. This is analogous to
BIP32, where the parent extended pubkey is needed (`P, c`). One could
argue
that `c` is never published on the blockchain, while `P` may be. On the
other
hand most wallets either use hardened derivation (so the attack does not
work)
or derive scriptpubkeys from keys at the same depth (so the parent key is
never published on the blockchain).
Anyway, if the parent public key is kept as secret as BIP32 extended keys
are,
then the situation is analogous to BIP32's.
_If_ these claims are correct, the proposed derivation scheme has two main
advantages:
1) Shorter backups for public and private derivable keys
Backups are especially relevant for output descriptors. For instance, when
using
a NofM multisig, each participant must backup M-1 exteneded public keys and
its
extended private key, which can be included in an output descriptor. Using
the
proposed derivation reduces the backup size by `~M*32` bytes.
2) User-friendly backup for child keys
Most wallets use user-friendly backups, such as BIP39 [5] mnemonics. They
map
16-32 bytes of entropy to 12-24 words. However BIP32 exteneded keys are at
least
64(65) bytes (key and chain code), so they cannot be mapped back to a
mnemonic.
A common wallet setup is (`->` one-way derivation, `<->` two-way mapping):
entropy (16-32 bytes) <-> user-friendly backup
-> BIP32 extended key (64-65 bytes)
-> BIP32 extended child keys (64-65 bytes)
With the proposed derivation, it would be possible to have:
derivable private key (32 bytes) <-> user-friendly backup
-> derivable public key (33 bytes) <-> user-friendly backup
-> derivable child keys (32-33 bytes) <-> user-friendly backup
This would allow having mnemonics for subaccount keys.
## References
[1] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki
[2] h1, h2, h3 and h4 can be defined as follows
Ip(c, p, i) = (i >= 2^31) HMAC-SHA512(c, 0x00 || ser256(p) || ser32(i))
(i < 2^31) HMAC-SHA512(c, pG || ser32(i))
IP(c, P, i) = (i >= 2^31) not possible
(i < 2^31) HMAC-SHA512(c, P || ser32(i))
h1(c, P, i) = parse256(IP(c, P, i)[:32])
h2(c, p, i) = parse256(Ip(c, p, i)[:32])
h3(c, P, i) = IP(c, P, i)[32:]
h4(c, p, i) = Ip(c, p, i)[32:]
[3] https://blockstream.com/sidechains.pdf Appendix A
[4] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki#security
[5] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
--
Leonardo
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Hey Frank, Firstly, I must commend you on two very good questions. The reason why I chose to maximize the value is because I approached this as an optimization problem to be solved with a genetic algorithm, and it fit with my internal model of a kind of relay race that moves forward faster. When confronted with the paradox of one side of the solution being minimized and the other being maximized I thought to myself that a paradox leading to determinism was beautiful... But it doesn't have to be this way. Part 2 of your question - what about the inevitable march of difficulty? And here is where how we quantify fitness starts to matter. Your right to point this out condition, maximizing the non-zero value means that re-org during an epoch won't optimize for having a trailing zero, which is a conflict that I see now must be avoided. The solution is to always choose the smallest, and the summation of all contestant chains must also be minimized. This approach would then be compatible with an Epoch - so much so that it would not impeed the use of a continuous difficulty function that pegs a solution at a range of non-zero values which would avoid a discrete cliff by requiring a whole extra zero. We need not be a victim of an early implementation - a continuous difficulty function would add stability to the network and this is worth unlocking. With added determinism and a continuous epoch, the network will be a lot more stable. At this point very little is stopping us from speeding up block creation times. PoS networks are proving that conformations can be a minute or less - why not allow for a block formation time that is 6 or 12 times faster than the current target and have 1/6th (or 1/12th) of the subsidy to keep an identical inflation target. … The really interesting part is the doors that this patch opens. Bitcoin is the best network, we have the most miners and we as developers have the opportunity to build an even better system - all with incremental soft-forks - which is so exciting. What I am proposing is a patch that is ~100 lines of code and is fully compatible with the current Bitcoin network - because I am running a node with my changes on the network, and the more miners who adopt my patch the more lucky we will become. Thank you everyone, Mike On Mon, Sep 28, 2020, 7:18 PM Franck Royer via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > > On Fri, 25 Sep 2020 at 22:09, Mike Brooks via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > [snip] > >> The solution above also has 19 prefixed zeros, and is being broadcast for >> the same blockheight value of 639254 - and a fitness score of 1.282. With >> Nakamoto Consensus both of these solutions would be equivalent and a given >> node would adopt the one that it received first. In Floating-Post Nakamoto >> Consensus, we compare the fitness scores and keep the highest. In this >> case no matter what happens - some nodes will have to change their tip and >> a fitness test makes sure this happens immediately. >> > > Hi Mike, > > Any reason why you decided to consider the higher value the "fittest" one > instead of keeping in line with the difficulty algorithm where smallest > values, prefixed with more zeroes, are considered more valuable/difficult? > > Also, can you elaborate if anything special would happen if the > competitive chains were created around a difficulty adjustment? > > Cheers, Franck > > [snip] > ___ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Floating-Point Nakamoto Consensus
Good Afternoon, Re: [bitcoin-dev] Floating-Point Nakamoto Consensus I note that the discussion thread for this proposal has previously received HARD_NAK I note in the whitepaper the following basic introduction of need: >As a result anode will simply adopt the first solution seen, creating a kind >of race condition. The said race condition, it is not noted, is 'self-resolving' with the network adopting the longest chain with the highest proof of work as any contentious tip is built on. This is the proper reason for waiting for two confirmations for a transaction as a minimum proof of its inclusion in the blockchain (without fraud), and for waiting for six confirmations before considering that a transaction is 'final'. I take it that your work is intended to allow the network to decide immediately without waiting for a chain to be further extended, in that case, the solution should be as noted elsewhere to accept the higher proof of work with the greater precision proof. When comparing two competing blocks there is an indirect reference to a higher proof of work due to the greater precision in the block hash, although the answer could have been arrived with fewer attempts. As it is, the total proof of work is not directly calculated but is evaluated as the chain with more blocks being the chain with more proof-of-work, whereas in the cases two blocks are received as alternates extending the same chain tip there is currently no method of comparison to determine which of the blocks, and the correct tip is not chosen without further proof-of-work to extend a tip. Resolving this reduces the network expense of reorganisation in ordinary conditions but in the case of a network-split resolves nothing. KING JAMES HRMH Great British Empire Regards, The Australian LORD HIS EXCELLENCY JAMES HRMH (& HMRH) of Hougun Manor & Glencoe & British Empire MR. Damian A. James Williamson Wills et al. Willtech www.willtech.com.au www.go-overt.com and other projects earn.com/willtech linkedin.com/in/damianwilliamson m. 0487135719 f. 61261470192 From: bitcoin-dev on behalf of Mike Brooks via bitcoin-dev Sent: Friday, 25 September 2020 5:40 AM To: bitcoin-dev Subject: [bitcoin-dev] Floating-Point Nakamoto Consensus Hey Everyone, A lot of work has gone into this paper, and the current revision has been well received and there is a lot of excitement on this side to be sharing it with you today. There are so few people that truly understand this topic, but we are all pulling in the same direction to make Bitcoin better and it shows. It is wildly underrated that future proofing was never really a consideration in the initial design - but here we are a decade later with amazing solutions like SegWit which gives us a real future-proofing framework. The fact that future-proofing was added to Bitcoin with a softfork gives me goosebumps. I'd just like to take the time to thank the people who worked on SegWit and it is an appreciation that comes up in conversation of how difficult and necessary that process was, and this appreciation may not be vocalized to the great people who worked on it. The fact that Bitcoin keeps improving and is able to respond to new threats is nothing short of amazing - thank you everyone for a great project. This current proposal really has nothing to do with SegWit - but it is an update that will make the network a little better for the future, and we hope you enjoy the paper. PDF: https://github.com/in-st/Floating-Point-Nakamoto-Consensus/blob/master/Floating-Point%20Nakamoto%20Consensus.pdf Pull Request: https://github.com/bitcoin/bitcoin/pull/19665/files --- Floating-Point Nakamoto Consensus Abstract — It has been shown that Nakamoto Consensus is very useful in the formation of long-term global agreement — and has issues with short-term disagreement which can lead to re-organization (“or-org”) of the blockchain. A malicious miner with knowledge of a specific kind of denial-of-service (DoS) vulnerability can gain an unfair advantage in the current Bitcoin network, and can be used to undermine the security guarantees that developers rely upon. Floating-Point Nakamoto consensu makes it more expensive to replace an already mined block vs. creation of a new block, and by resolving ambiguity of competition solutions it helps achieve global consumers more quickly. A floating-point fitness test strongly incentivises the correct network behavior, and prevents disagreement from ever forming in the first place. Introduction The Bitcoin protocol was created to provide a decentralized consensus on a fully distributed p2p network. A problem arises when more than one proof-of-work is presented as the next solution block in the blockchain. Two solutions of the same height are seen as authoritative equals which is the basis of a growing disagreement. A node will adopt the first solution seen, as both
