Re: [bitcoin-dev] Should Graftroot be optional?
On Thu, May 31, 2018 at 05:25:04PM -0700, Pieter Wuille via bitcoin-dev wrote: > The best argument for why Graftroot does not need to be optional I > think was how Greg put it: "since the signer(s) could have signed an > arbitrary transaction instead, being able to delegate is strictly less > powerful.". This seems persuasive to me. I think you could implement graftroot in a way that makes this explicit: * A graftroot input has >=2 items on the witness stack, a signature, a script (S), and possibly witness elements for the script. The signature has a SIGHASH_GRAFTROOT bit set. * To validate the signature, a virtual transaction is constructed: nVersion = 1 locktime = 0 inputs = [(txhash, txoutidx, 0, "", 0x)] outputs = [(txvalue, len(S), S)] locktime = 0 The signature is then checked against the virtual transaction. * If the signature is valid, the virtual transaction is discarded, and the script and witness elements are checked against the original tx. I think this approach (or one like it) would make it clear that graftroot is a simple optimisation, rather than changing the security parameters. Some caveats: * You'd presumably want to disallow signatures with SIGHASH_GRAFTROOT from being used in signatures in scripts, so as not to end up having to support recursive graftroot. * Checking the script/witness against the original transaction instead of the virtual one cheats a bit, but something like it is necessary to ensure locktime/csv checks in the script S behave sanely. You could have the virtual transaction be treated as being confirmed in the same block as the original transaction instead though, I think. * You would need to use SIGHASH_NOINPUT (or similar) in conjuction to allow graftroot delegation prior to constructing the tx (otherwise the signature would be committing to txhash/txoutidx). BIP118 would still commit to txvalue, but would otherwise work fine, I think. Cheers, aj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP 174 thoughts
Hey Andrew, If I'm reading the spec right: the way it is designed right now, you could create hundreds of thousands of zero bytes in the input or output key-value arrays. As far as I can tell this would be considered valid, as it is simply a large array of empty dictionaries. Is this right? I'm worried about buffer overflows in cases where someone sends a large blob of zeros to an unsuspecting implementation. Also, the extensibility section reads: > Additional key-value maps with different types for the key-value pairs > can be added on to the end of the format. "different types for the key-value pairs", is this referring to new types beyond the current global, input and output types? > The number of each map that follows must be specified in the globals > section Is this out of date? Since there is only one type in the global section now (tx). > so that parsers will know when to use different definitions of the > data types I'm not sure what this means. Thanks! Will -- https://jb55.com ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP 174 thoughts
Hi William, Andrew, list, As noted by William there are some types missing in the global-types definition, because the number of each map for I/O must be known to the parser in order to use the correct definitions for the types. At the moment a parser reading a key-value record does not know whether it should read it as per-input type or per-output, a way to address this is to declare in advance the number of maps and ensure they are ordered (inputs first). If you haven't already worked out some types for that i propose using: Number of inputs - key (None, only the type): PSBT_GLOBAL_INPUT_NUMBER = 0x01 - value: Varint Number of outputs - key (none, only the type): PSBT_GLOBAL_OUTPUT_NUMBER = 0x02 - value: Varint On another note I think we can set a hard limit on the size of the PSBT, currently is 'legal' to produce a very large PSBT with an excessive number of Inputs and Outputs. By excessive I mean that even in the best case scenario (using the smallest possible scriptPubKey as in P2WPKH) it is possible to create a PSBT that would certainly create an invalid transaction (because of its size) when finalized. I haven't found anything related to this in the previous discussions, please ignore this if it was already proposed/discussed. Cheers, Andrea. ‐‐‐ Original Message ‐‐‐ On June 27, 2018 8:09 AM, William Casarin via bitcoin-dev wrote: > > > Hey Andrew, > > If I'm reading the spec right: the way it is designed right now, you > > could create hundreds of thousands of zero bytes in the input or output > > key-value arrays. As far as I can tell this would be considered valid, > > as it is simply a large array of empty dictionaries. Is this right? I'm > > worried about buffer overflows in cases where someone sends a large blob > > of zeros to an unsuspecting implementation. > > Also, the extensibility section reads: > > > Additional key-value maps with different types for the key-value pairs > > > > can be added on to the end of the format. > > "different types for the key-value pairs", is this referring to new > > types beyond the current global, input and output types? > > > The number of each map that follows must be specified in the globals > > > > section > > Is this out of date? Since there is only one type in the global section > > now (tx). > > > so that parsers will know when to use different definitions of the > > > > data types > > I'm not sure what this means. > > Thanks! > > Will > > > > > https://jb55.com > > 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] BIP 174 thoughts
hello, On 26.6.2018 22:30, Pieter Wuille wrote: >> (Moreover, as I wrote previously, the Combiner seems like a weirdly >> placed role. I still don't see its significance and why is it important >> to correctly combine PSBTs by agents that don't understand them. If you >> have a usecase in mind, please explain. > > Forward compatibility with new script types. A transaction may spend > inputs from different outputs, with different script types. Perhaps > some of these are highly specialized things only implemented by some > software (say HTLCs of a particular structure), in non-overlapping > ways where no piece of software can handle all scripts involved in a > single transaction. If Combiners cannot deal with unknown fields, they > won't be able to deal with unknown scripts. Record-based Combiners *can* deal with unknown fields. Either by including both versions, or by including one selected at random. This is the same in k-v model. > combining must be done independently by Combiner implementations for > each script type involved. As this is easily avoided by adding a > slight bit of structure (parts of the fields that need to be unique - > "keys"), this seems the preferable option. IIUC, you're proposing a "semi-smart Combiner" that understands and processes some fields but not others? That doesn't seem to change things. Either the "dumb" combiner throws data away before the "smart" one sees it, or it needs to include all of it anyway. > No, a Combiner can pick any of the values in case different PSBTs have > different values for the same key. That's the point: by having a > key-value structure the choice of fields can be made such that > Combiners don't need to care about the contents. Finalizers do need to > understand the contents, but they only operate once at the end. > Combiners may be involved in any PSBT passing from one entity to > another. Yes. Combiners don't need to care about the contents. So why is it important that a Combiner properly de-duplicates the case where keys are the same but values are different? This is a job that, AFAICT so far, can be safely left to someone along the chain who understands that particular record. Say we have field F(key,value), and several Signers produce F(1,1), F(1,2), F(1,3). A key-based Combiner will pick exactly one to pass along. A record-based Combiner will pass all three. It seems that you consider the latter PSBT "invalid". But it is well formed and doesn't contain duplicate records. A Finalizer, or a different Combiner that understands field F, can as well have the rule "throw away all but one" for this case. To repeat and restate my central question: Why is it important, that an agent which doesn't understand a particular field structure, can nevertheless make decisions about its inclusion or omission from the result (based on a repeated prefix)? Actually, I can imagine the opposite: having fields with same "key" (identifying data), and wanting to combine their "values" intelligently without losing any of the data. Say, two Signers producing separate parts of a combined-signature under the same common public key? > In case of BIP32 derivation, computing the pubkeys is possibly > expensive. A simple signer can choose to just sign with whatever keys > are present, but they're not the only way to implement a signer, and > even less the only software interacting with this format. Others may > want to use a matching approach to find keys that are relevant; > without pubkeys in the format, they're forced to perform derivations > for all keys present. I'm going to search for relevant keys by comparing master fingerprint; I would expect HWWs generally don't have index based on leaf pubkeys. OTOH, Signers with lots of keys probably aren't resource-constrained and can do the derivations in case of collisions. Also, you need to do the derivation and checking anyway, because what if there is a mismatch between the key and the value? I liked @achow101's idea about supporting non-derived keys, but I assumed that you would match them based on the master fingerprint too? I wouldn't be against including the full master public key (probably without chaincode) instead of the fingerprint, as you proposed earlier. But including both the leaf pubkey and the fingerprint seems weird. > If you take the records model, and then additionally drop the > whole-record uniqueness constraint, yes, though that seems pushing it > a bit by moving even more guarantees from the file format to > application level code. The "file format" makes no guarantees, because the parsing code and application code is the same anyway. You could say I'm proposing to separate these concerns ;) regards m. signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP 174 thoughts
hello, On 26.6.2018 18:58, William Casarin wrote: > as a data point, I was able to build a simple serializer[1] in about an > afternoon. I would much prefer to use this lib in say, clightning (my > original goal), without having to have the larger protobuf dependency. To drive my point home, here's a PR converting the `writer` part of your code to a protobuf-compatible version. It took me less than an hour to write, the bigger part of which was spent orienting myself in unfamiliar code. I assume I could do `reader` in less than that, if your deserialization code was complete. https://github.com/jb55/libpsbt/pull/3/files This code produces PSBTs that my "bip174 playground" can correctly parse. regards m. > > Cheers, > > [1] https://github.com/jb55/libpsbt > > > -- > https://jb55.com > signature.asc Description: OpenPGP digital signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] BIP 174 thoughts
On Wed, Jun 27, 2018, 07:04 matejcik wrote: > hello, > > On 26.6.2018 22:30, Pieter Wuille wrote: > >> (Moreover, as I wrote previously, the Combiner seems like a weirdly > >> placed role. I still don't see its significance and why is it important > >> to correctly combine PSBTs by agents that don't understand them. If you > >> have a usecase in mind, please explain. > > > > Forward compatibility with new script types. A transaction may spend > > inputs from different outputs, with different script types. Perhaps > > some of these are highly specialized things only implemented by some > > software (say HTLCs of a particular structure), in non-overlapping > > ways where no piece of software can handle all scripts involved in a > > single transaction. If Combiners cannot deal with unknown fields, they > > won't be able to deal with unknown scripts. > > Record-based Combiners *can* deal with unknown fields. Either by > including both versions, or by including one selected at random. This is > the same in k-v model. > Yes, I wasn't claiming otherwise. This was just a response to your question why it is important that Combiners can process unknown fields. It is not an argument in favor of one model or the other. > combining must be done independently by Combiner implementations for > > each script type involved. As this is easily avoided by adding a > > slight bit of structure (parts of the fields that need to be unique - > > "keys"), this seems the preferable option. > > IIUC, you're proposing a "semi-smart Combiner" that understands and > processes some fields but not others? That doesn't seem to change > things. Either the "dumb" combiner throws data away before the "smart" > one sees it, or it needs to include all of it anyway. > No, I'm exactly arguing against smartness in the Combiner. It should always be possible to implement a Combiner without any script specific logic. > No, a Combiner can pick any of the values in case different PSBTs have > > different values for the same key. That's the point: by having a > > key-value structure the choice of fields can be made such that > > Combiners don't need to care about the contents. Finalizers do need to > > understand the contents, but they only operate once at the end. > > Combiners may be involved in any PSBT passing from one entity to > > another. > > Yes. Combiners don't need to care about the contents. > So why is it important that a Combiner properly de-duplicates the case > where keys are the same but values are different? This is a job that, > AFAICT so far, can be safely left to someone along the chain who > understands that particular record. > That's because PSBTs can be copied, signed, and combined back together. A Combiner which does not deduplicate (at all) would end up having every original record present N times, one for each copy, a possibly large blowup. For all fields I can think of right now, that type of deduplication can be done through whole-record uniqueness. The question whether you need whole-record uniqueness or specified-length uniqueness (=what is offered by a key-value model) is a philosophical one (as I mentioned before). I have a preference for stronger invariants on the file format, so that it becomes illegal for a PSBT to contain multiple signatures for the same key for example, and implementations do not need to deal with the case where multiple are present. It seems that you consider the latter PSBT "invalid". But it is well > formed and doesn't contain duplicate records. A Finalizer, or a > different Combiner that understands field F, can as well have the rule > "throw away all but one" for this case. > It's not about considering. We're writing a specification. Either it is made invalid, or not. In a key-value model you can have dumb combiners that must pick one of the keys in case of duplication, and remove the necessity of dealing with duplication from all other implementations (which I consider to be a good thing). In a record-based model you cannot guarantee deduplication of records that permit repetition per type, because a dumb combiner cannot understand what part is supposed to be unique. As a result, a record-based model forces you to let all implementations deal with e.g. multiple partial signatures for a single key. This is a minor issue, but in my view shows how records are a less than perfect match for the problem at hand. To repeat and restate my central question: > Why is it important, that an agent which doesn't understand a particular > field structure, can nevertheless make decisions about its inclusion or > omission from the result (based on a repeated prefix)? > Again, because otherwise you may need a separate Combiner for each type of script involved. That would be unfortunate, and is very easily avoided. Actually, I can imagine the opposite: having fields with same "key" > (identifying data), and wanting to combine their "values" intelligently > without losing any of the data. Say, two
Re: [bitcoin-dev] BIP 174 thoughts
Hi, On June 26, 2018 11:09 PM, William Casarin wrote: > > > Hey Andrew, > > If I'm reading the spec right: the way it is designed right now, you > > could create hundreds of thousands of zero bytes in the input or output > > key-value arrays. As far as I can tell this would be considered valid, > > as it is simply a large array of empty dictionaries. Is this right? I'm > > worried about buffer overflows in cases where someone sends a large blob > > of zeros to an unsuspecting implementation. No, that is incorrect. That whole paragraph is actually outdated, it was intended for the possibility of adding output maps, which we have already done. I have removed it from the BIP. However, it is possible for a PSBT to contain very large unknown key-value pairs which could potentially cause a problem. But I do not think that large PSBTs should really be a problem as they are really something that the user has to enter rather than something received remotely without user interaction. On June 27, 2018 6:39 AM, Andrea via bitcoin-dev wrote: > > > Hi William, Andrew, list, > > As noted by William there are some types missing in the global-types > definition, because the number of each map for I/O must be known to the > parser in order to use the correct definitions for the types. At the moment a > parser reading a key-value record does not know whether it should read it as > per-input type or per-output, a way to address this is to declare in advance > the number of maps and ensure they are ordered (inputs first). If you haven't > already worked out some types for that i propose using: > Parsers actually do know because that information is present in the unsigned transaction at the beginning of each PSBT. Since each input and output must be accounted for, a parser can just parse the unsigned transaction and from there it can know how many inputs and outputs to expect. If it sees more or less, it should throw an error as the transaction is invalid. Of course this implies that implementations will need to parse the unsigned transaction, but not all actually need to. Combiners do not need to, they just need to merge the maps together and follow the key uniqueness rule. They don't really need to know or care about the number of inputs and outputs, just that the PSBTs being merged share the same unsigned transaction and have the same number of maps. Other roles need to understand the unsigned transaction anyways, so they still need to parse it thus this isn't really a problem for those roles. > > On another note I think we can set a hard limit on the size of the PSBT, > currently is 'legal' to produce a very large PSBT with an excessive number of > Inputs and Outputs. By excessive I mean that even in the best case scenario > (using the smallest possible scriptPubKey as in P2WPKH) it is possible to > create a PSBT that would certainly create an invalid transaction (because of > its size) when finalized. I haven't found anything related to this in the > previous discussions, please ignore this if it was already proposed/discussed. > I don't think such a limitation is practical or useful. A transaction can currently have, at most, ~24000 inputs and ~111000 outputs (+/- a few hundred) which is well beyond any useful limit. Additionally, such limits may not be as extensible for future work. It is hard to determine what is a reasonable limit on transaction size, and I don't think it is useful to have a limit. At worst we would simply create an invalid transaction if it were too large. Andrew ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
