Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 12/20/2013 11:48 AM, Gregory Maxwell wrote: > A couple very early comments— I shared some of these with you on > IRC but I thought I'd post them to make them more likely to not get > lost. I got the inputs from IRC, but thank you for posting to the list so that others can see and review. > Whats a VARCHAR() A zero terminated string? A length prefixed > string? How is the length encoded? Hopefully not in a way that > has redundancy, since things that don't survive a serialization > round trip is a major trap. A length-prefixed string, using the shortest representation VARINT for the length. Same as how scripts are serialized in transactions. > Is the 'middle' the best place for the extradata? Have you > contemplated the possibility that some applications might use > midstate compression? Yes I considered midstate compression which is why the branch hashes come last, but "extra" was an oversight. In every application I've considered it's either not used (and therefore a single byte), or updated whenever the node or its children updates. Honestly I don't expect midestate compression to offer much since in the nodes that are updated frequently it is unlikely that there will be enough static data at the front to fill even a 512 bit block of the smaller hash function. But it doesn't hurt to prepare just in case. I'll move it to the end. > On that general subject, since the structure here pretty much > always guarantees two compression function invocations. SHA512/256 > might actually be faster in this application. Yes, this is a great suggestion. Moving to SHA-512/256 will let most inner nodes fit inside a single block, so long as the "extra" field is not too long. Also apparently SHA-512 is faster on 64-bit CPUs, which is a nice advantage. I didn't know that. I'm concerned about speed but I did not go with a faster hash function because users are more likely to have hardware acceleration for the SHA-2 family. > Re: using sha256 instead of sha256^2, we need to think carefully > about the implications of Merkle-Damgard generic length extension > attacks. It would be unfortunately to introduce them here, even > though they're currently mostly theoretical for sha256. The serialization format encodes lengths in such a way that you cannot extend the data structure merely by appending bits. You would have to change the prior, already hashed bits as well. I believe this makes it immune to length extension attacks. > WRT hash function performance, hash functions are so ludicrously > fast (and will be more so as processors get SHA2 instructions) that > the performance of the raw compression function would hardly ever > be a performance consideration unless you're using a slow > interpreted language (... and that sounds like a personal problem > to me). So I don't think CPU performance should be a major > consideration in this BIP. Well.. the UTXO tree is big. Let's assume 5,000 transactions per block, with an average of 3 inputs/outputs per transaction. This is close to the worst-case scenario with the current block size. That's 15,000 insert, update, or delete operations. The number of hashes required when level-compression is used is log2 the number of items in the tree, which for bitcoin is currently about 2.5 million transactions. So that's about ~21 hashes per input/ouput, or 315,000 hash operations. A CPU is able to do about 100,000 hashes per second per core, that'll probably take about a second on a modern 4- or 8-core machine. For updatable proofs, the number of hash operations is equal to the number of bits in the key, which for the validation index is always 256. That means 3.84 million hashes, or about 10 seconds on a 4-core machine. The numbers for the wallet index are worse, as it scales with the number of outputs, which is necessarily larger, and the keys are longer. This is not an insignificant cost in the near term, although it is the type of operation that could be easily offloaded to a GPU or FPGA. > What I do think should be a consideration is the cost of > validating the structure under a zero-knowledge proof. An example > application is a blind proof for a SIN or a proof of how much coin > you control... or even a proof that a block was a correctly > validated one, and in these cases additional compression function > calls are indeed pretty expensive. But they're not the only cost, > any conditional logic in the hash tree evaluation is expensive, and > particular, I think that any place where data from children will be > combined with a variable offset (especially if its not word > aligned) would potentially be rather expensive. This is something I know less about, and I welcome constructive input. There is *no* reason that the hash serialization needs to have fancy space-saving features. You could even make the SIG_HASH node serialization into fixed-size, word-aligned data structures. But this is absolutely not my field, an
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
On Thu, Dec 19, 2013 at 5:47 PM, Mark Friedenbach wrote: > Hello fellow bitcoin developers. Included below is the first draft of > a BIP for a new Merkle-compressed data structure. The need for this > data structure arose out of the misnamed "Ultimate blockchain > compression" project, but it has since been recognized to have many > other applications. A couple very early comments— I shared some of these with you on IRC but I thought I'd post them to make them more likely to not get lost. Whats a VARCHAR() A zero terminated string? A length prefixed string? How is the length encoded? Hopefully not in a way that has redundancy, since things that don't survive a serialization round trip is a major trap. Is the 'middle' the best place for the extradata? Have you contemplated the possibility that some applications might use midstate compression? On that general subject, since the structure here pretty much always guarantees two compression function invocations. SHA512/256 might actually be faster in this application. Re: using sha256 instead of sha256^2, we need to think carefully about the implications of Merkle-Damgard generic length extension attacks. It would be unfortunately to introduce them here, even though they're currently mostly theoretical for sha256. WRT hash function performance, hash functions are so ludicrously fast (and will be more so as processors get SHA2 instructions) that the performance of the raw compression function would hardly ever be a performance consideration unless you're using a slow interpreted language (... and that sounds like a personal problem to me). So I don't think CPU performance should be a major consideration in this BIP. What I do think should be a consideration is the cost of validating the structure under a zero-knowledge proof. An example application is a blind proof for a SIN or a proof of how much coin you control... or even a proof that a block was a correctly validated one, and in these cases additional compression function calls are indeed pretty expensive. But they're not the only cost, any conditional logic in the hash tree evaluation is expensive, and particular, I think that any place where data from children will be combined with a variable offset (especially if its not word aligned) would potentially be rather expensive. I'm unconvinced about the prefix tree compressed applications, since they break compact update proofs. If we used them in the Bitcoin network they could only be used for data where all verifying nodes had all their data under the tree. I think they add a lot of complexity to the BIP (esp from people reading the wrong section), so perhaps they should be split into another document? In any case, I want to thank you for talking the time to write this up. You've been working on this stuff for a while and I think it will be lead to useful results, even if we don't end up using how it was originally envisioned. -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 (Sorry Peter, this was meant for the whole list:) On 12/20/2013 05:17 AM, Peter Todd wrote: > I've thought about this for awhile and come to the conclusion that > UTXO commitments are a really bad idea. I myself wanted to see them > implemented about a year ago for fidelity bonded banks, but I've > changed my mind and I hope you do too. > > They force miners and every full node with SPV clients to store the > entire UTXO set in perpetuity. This is incorrect. If the slower proof-updatable hashes are used, then mining only requires what I've called "operational proofs" to be attached to received transactions and blocks. Access to the UTXO set is required to make new transactions, at least for the outputs of the transaction, but I do not believe this is as significant a problem as you do. It is a service that can be outsourced for a minimal fee - include an explicit output of the necessary amount to a scriptPubKey specified by the archival node, and they will make sure the proper proofs are attached. > This is bad by itself, but then they make it even worse by making > Bitcoin really useful and convenient to use as a decentralized > database; UTXO commitments make it easy and convenient to > implement systems like Namecoin on top of Bitcoin, yet we don't > have the UTXO expiration that might make such uses reasonable. > Right now the UTXO set is reasonable small - ~300MB - but that can > and will change if we make it an attractive way to store data. > UTXO commitments do exactly that. You might have to explain this to me, but it is not clear to me how the validation index could be twisted into providing a Namecoin-like system. Or the address index either, which I presume is what you are referring to. Namecoin works by assigning domains to outputs, and then tracking ownership and configuration of that domain through chains of outputs. But the UTXO set doesn't contain connecting information. At best all it would be is a glorified, and expensive time-stamper, unattractive because there are already better solutions. > You're also *not* giving users what they actually want: the > transactions associated with their wallets. Even though Electrum > could easily work via a pure UTXO database they implemented > transaction lookup instead; Electrum servers cough up every > transaction associated with a user's wallet. If you're going to do > that, it's just as easy to do per-block lookup trees which don't > force the UTXO set to be stored. At the cost of having the supposedly lightweight client query for each of its coins on every single block, to construct a negative proof-of-spend. > There's also a more subtle issue: the security model of UTXO > commitments sucks. It encourages wallets to essentially trust > single confirmations because it's unlikely that nodes will want to > store the multiple copies of the UTXO set required to provide > proof of multiple confirmations. Basically the issue is when you > start your wallet you get a proof of UTXO set for the most recent > block; that's just one confirmation. To get more confirmations you > have to wait for subsequent blocks, checking the set on each block. > Per block indexes on the other hand naturally lead wallets to > count confirmations properly. I don't think this is true, or at least you are not considering available optimizations. You certainly don't need to store multiple copies of the UTXO set. I'm a little confused as to the exact situation you are describing. When a key is loaded into a wallet, or a wallet comes online after a significant absence, it looks for coins in the current UTXO set. If any coins are found, their attached transaction record has a block height field, so the confirmation count can be derived from that. As blocks go by that count is naturally increased. I'm not sure how this is different from the current situation. -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJStI9aAAoJEAdzVfsmodw4IooP/1uK9cvP1vxXyQRbAHf9oFXw AmZ8p1+t8f6MHUpjkv/Xn0poFNU8qSnNz65drQdq8ErcJnqe4V3Wt6G32/uCxvZs 6AX6bRYQIfhHY0DBPgfacO5/ALdlnS4NdjWFCA5hHDgLd30BpbU1WK1ze985TXrd +ucQkzcMYEDW2lb+sFvfhpi9ZPFd34ZrNzH//oS794eYKWAmj7jXqdgxk5AKat61 Xileq5beE4xom3pChXc3PtIJKsoil5SjE20/FW52wcCdyaEFG0kwl937pEGjQnlP mylK/ilfZ6cvRC8MmVnl/6AC4V2hjB4Ncej03jG3JI2FdaJEOHuHg0uh8/Zl1I4A YVIKyrHQhQb/VGsfXtW3zokHzDeEtJwlx+PPFaLc9QurFirNjSnenhbw4Vpbg3Xt dH1Qd9xWcT85a19Oz8Q4rt3z7UmX9J/geZrUHCuPtr47yXU0e1Cc6ZP9zDYNtfKU q6MjNZiaLJ/Wp0n4IeQ/4/wqy0rM/psP9i5d6IdP96tayVM9aKj5Lh9lU/Od5wGO 2PPB4kvhJfMbx3o+S7UK5vra7ysZzULpoVGDpUR3xRM72l//vlNhSLK5nILVO3r8 sIC5+3WoZLUKvuNo45/BDxXHZajrWLCU84WrwHVm1u7SHfBQcoES/rhcx2zlgyx0 /Iwxsgb7Fznl+eM2bEpZ =TtaV -END PGP SIGNATURE- -- Rapidly troubleshoot problems before they affect your
Re: [Bitcoin-development] [unSYSTEM] DarkWallet Best Practices
I’m inclined to agree, as this was discussed on multiple occasions and seems to fix a lot of the address re-use problems. With hot topics like “coin validation”, I think it’s important to highlight the privacy that generating fresh addresses from public extended keys grants us. Also thinking about implications regarding non-merchant use of Payment Protocol, encouraging the exchange of extended public keys instead of a single address could be a boon for Payment Protocol to actually be useful for users. Initially, the idea was that the merchant would generate a new address from an extended key and include that in the Payment Request. How do we handle pushing the extended public key down to the wallet itself? Do we just shoehorn the exchange of keys into the Payment Protocol itself via a special tag or would this require more substantive change? Services could develop to facilitate the exchange (acting as a sort of “PP gateway”) or wallet software might be able to directly communicate, perhaps by exchanging PGP-encrypted files in Payment Protocol format via Bluetooth, AirDrop, email, BitMessage, or whatever future communications channel comes into being. Thanks again to Peter for putting together a consolidated list of topics! Taylor On Dec 19, 2013, at 2:40 PM, caedes wrote: > I feel it's missing mention of using (or not) *extended public keys* > from bip 32 to share multiple addresses in one go, so regular payments > can be done without asking for further addresses. Also since whoever has > the extended key can generate public keys this might help P2SH where the > public key is also needed. -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Payment processors that support testnet?
Are there any bitcoin to fiat currency processors (like bitpay, coinbase, etc) that allow testing using the bitcoin testnet? It seems most of the credit card payment processor apis have features to allow developers to do testing without 'real money', what's the equivalent of this for bitcoin when you need to do end-to-end testing that goes from BTC to a USD or EU denominated bank accound? -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Censorship-resistance via timelock crypto for embedded consensus systems
Embedded consensus systems such as Mastercoin face the risk that the data they need to embed in the host consensus system will be subject to censorship. This censorship can take two forms: whitelists and blacklists. The former we can't do anything about, however the latter requires someone to identify the data-carrying transactions that are to be blacklisted. Embedding data steganographically in transactions is known to be possible in ways that can-not be detected. Even if P2SH^2 (1) is implemented data can be hidden in pubkeys in P2SH scriptSigs, either by using unused pubkeys in CHECKMULTISIG transactions with a simple transform(2) to turn arbitrary data into valid-looking pubkeys, or with some ECC math even usable pubkeys can have data hidden in them.(3) However these methods are unsuitable if the data needs to be provably made public; without the encryption key the data is securely hidden. Almost all consensus systems rely on proof-of-publication(4) and even if the encryption keys are later made public - perhaps by broadcasting them on a P2P network - we've only shifted the problem to proving that the keys were released. Of course, if we then publish them via our host consensus system, *that* act of publishing can itself be censored! Timelock cryptography offers a solution to this problem. Let S(n, k) be a sequential-hard strengthening function that takes key k and number of rounds n, outputting k'. A suitable S() might be the scrypt function. Let E(d, k) be a symmetric encryption algorithm. Finally let H(m) be a cryptographic hash function. To hide data D in a transaction we set k to some random and publicly known value in the transaction and compute k'=S(n, k) and D'=E(D, k') Then D' is hidden in the transaction, perhaps in an unused pubkey of a CHECKMULTISIG scriptPubKey. Our intended audience can also calculate k' from the public data, and thus recover D in time ~t, thus we know that after time ~t has elapsed all participants in the system can reliably come to consensus. However miners and other parties who may wish to censor D face a dilemma: If they repeat the calculation for every transaction that may be hiding data they delay all transactions for all users. In addition miners have a financial incentive to defect and mine transactions without checking for hidden data. Practical Considerations Efforts should be made to limit the scope of possible transactions as much as possible to reduce the computation required, e.g. by restricting the search space to only transactions with scriptPubKeys starting with some short prefix. This is a balance between computation and censorship resistance. Consideration needs to be made as to how the data will be validated as part of the embedded consensus system, for instance via a checksum or cryptographic signature. Participates in the embedded consensus system should share k' keys among each other to reduce overall effort. This ties back to validation: it must not be possible to distribute a fake k' undetectably. Picking n, and thus the time taken, is a balance. Also there should be some mechanism to update n as technological improvements warrant. Along those lines this method works best when t can be large and immediate consensus is not required. A suitable use-case could be a key-value consensus system for name information where mappings are infrequently changed. The source of k should be such that k' can be computed in advance, however only by the sender. For instance simply using the first txin hash allows the attacker to compute k' in advance themselves. A better choice would be the first (real) pubkey in a scriptPubKey, a value we can both compute in advance, yet is not known publicly. Censorship resistant voting === With due care the scheme can be used to allow for censorship-resistant voting. While previously it was believed that miners would inevitably be able to censor any voting scheme - with the exception of certain special cases(5) - provided that the financial incentive to collect fees outweighs the incentive to not count votes we have strong censorship resistance with strong consensus in a fixed amount of time. 1) Gregory Maxwell, [Bitcoin-development] To prevent arbitrary data storage in txouts — The Ultimate Solution, https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg01987.html 2) Peter Todd, Re: MasterCoin: New Protocol Layer Starting From “The Exodus Address”, https://bitcointalk.org/index.php?topic=265488.msg3377058#msg3377058 3) ByteCoin, Untraceable transactions which can contain a secure message are inevitable, https://bitcointalk.org/index.php?topic=5965.0 4) Peter Todd, [Bitcoin-development] Disentangling Crypto-Coin Mining: Timestamping, Proof-of-Publication, and Validation, http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03307.html 5) John Dillon, Proposal: We should vote on the blocksize limit w
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
On Fri, Dec 20, 2013 at 03:21:38AM -0800, Mark Friedenbach wrote: > Hi Jeremy, Let's give a preview of the application-oriented BIPs I > mentioned: > > Stateless validation and mining involves prefixing transaction and > block messages with proofs of their UTxO state changes. These are the > "operational proofs" I describe in the draft, and they work on prefix > trees whose root hashes committed to the coinbase in a soft-fork > upgrade of the validation rules. > > "Ultimate blockchain compression" involves consensus over an address > index, which can be queried over the p2p network by lightweight nodes. > The structure of the index is an authenticated prefix tree, and the > results of such a query is an an inclusion proof. I've thought about this for awhile and come to the conclusion that UTXO commitments are a really bad idea. I myself wanted to see them implemented about a year ago for fidelity bonded banks, but I've changed my mind and I hope you do too. They force miners and every full node with SPV clients to store the entire UTXO set in perpetuity. This is bad by itself, but then they make it even worse by making Bitcoin really useful and convenient to use as a decentralized database; UTXO commitments make it easy and convenient to implement systems like Namecoin on top of Bitcoin, yet we don't have the UTXO expiration that might make such uses reasonable. Right now the UTXO set is reasonable small - ~300MB - but that can and will change if we make it an attractive way to store data. UTXO commitments do exactly that. You're also *not* giving users what they actually want: the transactions associated with their wallets. Even though Electrum could easily work via a pure UTXO database they implemented transaction lookup instead; Electrum servers cough up every transaction associated with a user's wallet. If you're going to do that, it's just as easy to do per-block lookup trees which don't force the UTXO set to be stored. There's also a more subtle issue: the security model of UTXO commitments sucks. It encourages wallets to essentially trust single confirmations because it's unlikely that nodes will want to store the multiple copies of the UTXO set required to provide proof of multiple confirmations. Basically the issue is when you start your wallet you get a proof of UTXO set for the most recent block; that's just one confirmation. To get more confirmations you have to wait for subsequent blocks, checking the set on each block. Per block indexes on the other hand naturally lead wallets to count confirmations properly. IMO you should take this technology to Namecoin instead. For them the fast lookups are probably worth the trade-offs, and they expire domains so the total set size doesn't grow unbounded. -- 'peter'[:-1]@petertodd.org 00028fd077fb1e33e942e3e875aa29cec134fed89d650242c577 signature.asc Description: Digital signature -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
On Fri, Dec 20, 2013 at 03:10:50AM -0800, Mark Friedenbach wrote:
> On 12/20/2013 02:48 AM, Peter Todd wrote:
> > On Thu, Dec 19, 2013 at 05:47:52PM -0800, Mark Friedenbach wrote:
> >> This BIP describes the authenticated prefix tree and its many
> >> variations in terms of its serialized representation. Additional
> >> BIPs describe the application of authenticated prefix trees to
> >> such applications as committed indices, document time-stamping,
> >> and merged mining.
> >
> > Could you expand more on how prefix trees could be used for
> > time-stamping and merged mining?
>
> The root hash of a prefix tree is placed in the coinbase at a location
> standardized by convention.
Right, last txout in an OP_RETURN like we discussed.
> For document time-stamping, the key can be
> the hash of the document.
Don't you mean the value is the hash of the document and the key is
irrelevant?
> For merged mining, the key is the hash of
> the genesis block of the altchain, and the value is the hash of the
> aux-pow (for p2pool, the share hash).
What's the advantage over the direction-based system I proposed before?
Seems to me the code required to validate the proof is significantly
more complex in your scheme.
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03149.html
> In the system I have in mind this adds 43 bytes to the coinbase
> transaction,
By 43 bytes you mean the whole op_return txout right?
> > dict = AuthTree() dict['Curie'] = VARINT(1898)
> > dict('Einstein') = VARINT(1905) dict['Fleming'] =
> > VARINT(1928) dict['中本'] = VARINT(2009)
> >
> > I'd be inclined to leave the unicode out of the code examples as
> > many editors and shells still don't copy-and-paste it nicely. Using
> > it in BIP documents themselves is fine and often has advantages re:
> > typesetting, but using it in crypto examples like this just makes
> > it harder to reproduce the results by hand unnecessarily.
>
> Thanks for the feedback, I rather agree. When I was creating that
> example for some reason I wanted the right branch of the root node to
> be used, which is difficult when only 7-bit ASCII keys are used. But I
> don't think the illustrative point I had in mind ended up being
> particularly relevant, so I'll rework it.
That example is python, so I'd suggest just using escape sequences
myself. You probably also should include the "b" prefix to make the
strings explicitly binary for py3 compatibility, ie dict[b'\xbe\xef']
--
'peter'[:-1]@petertodd.org
000216e3750a9ad9584395352d728a3c543844eab3bfc9ce1073
signature.asc
Description: Digital signature
--
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 Hi Jeremy, Let's give a preview of the application-oriented BIPs I mentioned: Stateless validation and mining involves prefixing transaction and block messages with proofs of their UTxO state changes. These are the "operational proofs" I describe in the draft, and they work on prefix trees whose root hashes committed to the coinbase in a soft-fork upgrade of the validation rules. "Ultimate blockchain compression" involves consensus over an address index, which can be queried over the p2p network by lightweight nodes. The structure of the index is an authenticated prefix tree, and the results of such a query is an an inclusion proof. Document time-stamping and this new method of merged mining use the same structure: a prefix tree whose root hash value is committed to a pruneable output of the coinbase transaction. Document timestamp proofs and merged mining proof-of-works are inclusion proofs over this tree. I hope that shows how the BIP directly affects interoperability of the bitcoin protocol and clients which use these applications. I released this BIP first to get some feedback on the structure itself, which will be used by all of the application-specific BIPs which follow. Stepping back and speaking generically, the purpose of a BIP as I see it is to standardize details which affect interoperability between clients. In fact, at a cursory glance only about half of the BIPs deal with protocol issues directly - the rest deal with local / user-interface issues like key derivation or JSON-RPC APIs. Even if none of the applications involved protocol changes, I still think BIPs like this would be of value in that they serve to standardize things which are or will seek to become commonly used and widely implemented. Cheers, Mark On 12/19/2013 10:48 PM, Jeremy Spilman wrote: > Wow there's a lot here to think about. I'm pretty sure I haven't > grasped the full implications yet. > > I see it proposes to also introduce additional BIPs describing the > use of the data stucture for stateless validation & mining, the UBC > address index for "SPV+" operating modes, document timestamping and > merged mining. > > Can the BIP stand alone as a BIP without some specific changes to > the protocol or end-user accessible features defined within it? It > seems like an extremely useful data stucture, but as I understand > it the purpose of BIPS is defining interoperability points, not > implementation details? > > Unless the tree itself is becoming part of the protocol, seems like > its spec, test vectors, and reference implementation can live > elsewhere, but I would love to read about BIPS which use this tree > to accomplish some amazing scalability or security benefits. > -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJStChCAAoJEAdzVfsmodw42DcQAIlgkukh5K/XYloIiT5pgaHS xCZXtOvxpNUep8x35rvEO1ePjvPvUkbUE2jRw2se1rSMkhzw3PpHHtXV/gIOGqUe WVKeeIM5pZX56sEcEdUQ1pTwB2rmtSNeyCuHl8fLatk8eLhcAHcpv/7esLuAjWCr EE840s8+q3ltuzKi3nqxK84bwIohgSMKhncfonNp5lMAtug8Itqopq3DPDoxwiK/ qUwSz5UCEMH6oNHnywzhKGUhBErqo4q8IgAKcZYBZZ9n4BRjf4ngoCw9n5wCef8v tyTvwrg0nSQTQa67cg7RCsY7SisrI9gaMvCYTSvEMKdw9X0aqAX1p0yZpTbV+dIr Q2ZT6gJmg2sD22zKY1/58oq+PiNO+nRS81OG2znZofsIfhOVW0bIZAQ8+zZtFW40 vXxMuHCNieCK8e7f9A6LLv/Zz7rmNxdQ6cHBEL1nIs1Y4d1FpHJVI2LHi54QmVXf C5PKF/e7K2eD3LZMNxS818rZaiJJ7qmpjS3rkG2owHyJHEhBJIlkYXfI1YCraT+b R5AzAh2Oz0Nyb5ChP2VSaecJNjGvRMo7Z6HCytmgAGOEcDDZkxSv0kkprbvchqXx XziFgA4iSajBKYWPiPLGMADfMPT6zd4fhDjyaN8+LPO3d3ZK1VwmQDLRQ3DxfeIP RgchHR/pS77XI7hCFwtN =ao17 -END PGP SIGNATURE- -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
On Thu, Dec 19, 2013 at 05:47:52PM -0800, Mark Friedenbach wrote:
> This BIP describes the authenticated prefix tree and its many
> variations in terms of its serialized representation. Additional BIPs
> describe the application of authenticated prefix trees to such
> applications as committed indices, document time-stamping, and merged
> mining.
Could you expand more on how prefix trees could be used for
time-stamping and merged mining?
> >>> dict = AuthTree()
> >>> dict['Curie'] = VARINT(1898)
> >>> dict('Einstein') = VARINT(1905)
> >>> dict['Fleming'] = VARINT(1928)
> >>> dict['中本'] = VARINT(2009)
I'd be inclined to leave the unicode out of the code examples as many
editors and shells still don't copy-and-paste it nicely. Using it in BIP
documents themselves is fine and often has advantages re: typesetting,
but using it in crypto examples like this just makes it harder to
reproduce the results by hand unnecessarily.
--
'peter'[:-1]@petertodd.org
0002d7a0c56ae2c5b2b3322d5017cfef847455d4d86a6bc12280
signature.asc
Description: Digital signature
--
Rapidly troubleshoot problems before they affect your business. Most IT
organizations don't have a clear picture of how application performance
affects their revenue. With AppDynamics, you get 100% visibility into your
Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro!
http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk___
Bitcoin-development mailing list
Bitcoin-development@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] bitcoin-qt
On Fri, Dec 20, 2013 at 8:49 AM, Chris Evans wrote: > maybe make it so bitcoin.conf settings can be edited with in the app > instead of external editor, and make it easier to enable rpc server mode... > You can help me and diapolo a lot by testing his pull request to add a few options to the options dialog (and improve the dialog in general), https://github.com/bitcoin/bitcoin/pull/3347 It doesn't add the RPC settings though. As Mark says, it's dangerous to make it too easy to shoot yourself in the foot. Wladimir -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] bitcoin-qt
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 JSON-RPC is a huge security risk. It's perfectly reasonable that enabling it requires some technical mumbo-jumbo. Are there specific configuration settings that you would like to see exposed by the GUI? On 12/19/2013 11:49 PM, Chris Evans wrote: > maybe make it so bitcoin.conf settings can be edited with in the > app instead of external editor, and make it easier to enable rpc > server mode... -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.14 (GNU/Linux) Comment: GPGTools - http://gpgtools.org Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/ iQIcBAEBAgAGBQJSs/e3AAoJEAdzVfsmodw4mEkP/3XdrWMoly5t2ALN/YAj1QCv nviQfzcv7vQKEO1ZnLMmyo1npIMRf5UqZCD6kfWS7g4vtEHjP2KNQXdwcNkDPbdL 7BjHGHghoGfjPosTz2HV8I79g+6o+f9KCYxUz56dRVs1eNjF/QAMKbHY5M2QD7UZ 3BVxdEGD2UkIN89dUSq+Ljrt+ugPlOYFiehrLhOSqYTLtoG2von7JQR8q6HRKmzC hWSuT20aV66VL03ps5Dt/c8NVr0p0nNYRVY1vPzkcjN+1UpMBUvgn8E2d5XrchD+ uqTeWCMv2bhmFTr0qaVQwBY5Et5q6/OBJbWcF02qFq0/hy/SuZPIp/5fZEOuSpns /QJRGRyMLtCpRH4iNxlhcZeiQs8MoV02AHYiSN/9Z9yZDEBZkpbKO9Ce6S0GwmEX iXeloVaIil5dqtr8P9aWXW12jgohGy84oFGwK0Bxrk+HfT04OCSU0lqjRQVFzfdl /K0jqgRdrXZz2wQYOO6+GjQvb8CP/7WfRxivKqcKdQT9CrsW+DvgaAkTy3tBJcel aGrPynsNnDdatXK0Nyhirn/gSvxSW/Z2x2CIaPCq+jw4HrnmJu+j5AXcD8yKo8+c FsTap1/TXeFPcDP6B7eUT+nV+hR6qXYLOuHpFwbTvt/8SJ0jAgj9Yhyq8PmL4rok mdrqhFHk3i/RMYqGK59Q =WCub -END PGP SIGNATURE- -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal: Authenticated prefix trees
Wow there's a lot here to think about. I'm pretty sure I haven't grasped the full implications yet. I see it proposes to also introduce additional BIPs describing the use of the data stucture for stateless validation & mining, the UBC address index for "SPV+" operating modes, document timestamping and merged mining. Can the BIP stand alone as a BIP without some specific changes to the protocol or end-user accessible features defined within it? It seems like an extremely useful data stucture, but as I understand it the purpose of BIPS is defining interoperability points, not implementation details? Unless the tree itself is becoming part of the protocol, seems like its spec, test vectors, and reference implementation can live elsewhere, but I would love to read about BIPS which use this tree to accomplish some amazing scalability or security benefits. -- Rapidly troubleshoot problems before they affect your business. Most IT organizations don't have a clear picture of how application performance affects their revenue. With AppDynamics, you get 100% visibility into your Java,.NET, & PHP application. Start your 15-day FREE TRIAL of AppDynamics Pro! http://pubads.g.doubleclick.net/gampad/clk?id=84349831&iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
